2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 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
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
42 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
44 static char *type_str
[] = {
45 [pet_expr_access
] = "access",
46 [pet_expr_call
] = "call",
47 [pet_expr_cast
] = "cast",
48 [pet_expr_double
] = "double",
49 [pet_expr_unary
] = "unary",
50 [pet_expr_binary
] = "binary",
51 [pet_expr_ternary
] = "ternary"
54 static char *op_str
[] = {
55 [pet_op_add_assign
] = "+=",
56 [pet_op_sub_assign
] = "-=",
57 [pet_op_mul_assign
] = "*=",
58 [pet_op_div_assign
] = "/=",
59 [pet_op_assign
] = "=",
74 [pet_op_post_inc
] = "++",
75 [pet_op_post_dec
] = "--",
76 [pet_op_pre_inc
] = "++",
77 [pet_op_pre_dec
] = "--",
78 [pet_op_address_of
] = "&",
83 [pet_op_assume
] = "assume",
84 [pet_op_kill
] = "kill"
87 /* pet_scop with extra information that is used during parsing and printing.
89 * In particular, we keep track of conditions under which we want
90 * to skip the rest of the current loop iteration (skip[pet_skip_now])
91 * and of conditions under which we want to skip subsequent
92 * loop iterations (skip[pet_skip_later]).
94 * The conditions are represented as index expressions defined
95 * over a zero-dimensiona domain. The index expression is either
96 * a boolean affine expression or an access to a variable, which
97 * is assumed to attain values zero and one. The condition holds
98 * if the variable has value one or if the affine expression
99 * has value one (typically for only part of the parameter space).
101 * A missing condition (skip[type] == NULL) means that we don't want
104 * Additionally, we keep track of the original input file
105 * inside pet_transform_C_source.
107 struct pet_scop_ext
{
108 struct pet_scop scop
;
110 isl_multi_pw_aff
*skip
[2];
114 const char *pet_op_str(enum pet_op_type op
)
119 int pet_op_is_inc_dec(enum pet_op_type op
)
121 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
122 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
125 const char *pet_type_str(enum pet_expr_type type
)
127 return type_str
[type
];
130 enum pet_op_type
pet_str_op(const char *str
)
134 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
135 if (!strcmp(op_str
[i
], str
))
141 enum pet_expr_type
pet_str_type(const char *str
)
145 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
146 if (!strcmp(type_str
[i
], str
))
152 /* Construct an access pet_expr from an access relation and an index expression.
153 * By default, it is considered to be a read access.
155 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
156 __isl_take isl_multi_pw_aff
*index
)
158 isl_ctx
*ctx
= isl_map_get_ctx(access
);
159 struct pet_expr
*expr
;
161 if (!index
|| !access
)
163 expr
= isl_calloc_type(ctx
, struct pet_expr
);
167 expr
->type
= pet_expr_access
;
168 expr
->acc
.access
= access
;
169 expr
->acc
.index
= index
;
175 isl_map_free(access
);
176 isl_multi_pw_aff_free(index
);
180 /* Construct an access pet_expr from an index expression.
181 * By default, the access is considered to be a read access.
183 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
187 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
188 return pet_expr_from_access_and_index(access
, index
);
191 /* Extend the range of "access" with "n" dimensions, retaining
192 * the tuple identifier on this range.
194 * If "access" represents a member access, then extend the range
197 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
201 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
203 if (!isl_map_range_is_wrapping(access
)) {
204 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
208 domain
= isl_map_copy(access
);
209 domain
= isl_map_range_factor_domain(domain
);
210 access
= isl_map_range_factor_range(access
);
211 access
= extend_range(access
, n
);
212 access
= isl_map_range_product(domain
, access
);
215 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
220 /* Construct an access pet_expr from an index expression and
221 * the depth of the accessed array.
222 * By default, the access is considered to be a read access.
224 * If the number of indices is smaller than the depth of the array,
225 * then we assume that all elements of the remaining dimensions
228 struct pet_expr
*pet_expr_from_index_and_depth(
229 __isl_take isl_multi_pw_aff
*index
, int depth
)
234 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
237 dim
= isl_map_dim(access
, isl_dim_out
);
239 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
240 "number of indices greater than depth",
241 access
= isl_map_free(access
));
243 return pet_expr_from_access_and_index(access
, index
);
245 access
= extend_range(access
, depth
- dim
);
247 return pet_expr_from_access_and_index(access
, index
);
249 isl_multi_pw_aff_free(index
);
253 /* Construct a pet_expr that kills the elements specified by
254 * the index expression "index" and the access relation "access".
256 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
257 __isl_take isl_multi_pw_aff
*index
)
260 struct pet_expr
*expr
;
262 if (!access
|| !index
)
265 ctx
= isl_multi_pw_aff_get_ctx(index
);
266 expr
= pet_expr_from_access_and_index(access
, index
);
270 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
272 isl_map_free(access
);
273 isl_multi_pw_aff_free(index
);
277 /* Construct a unary pet_expr that performs "op" on "arg".
279 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
280 struct pet_expr
*arg
)
282 struct pet_expr
*expr
;
286 expr
= isl_alloc_type(ctx
, struct pet_expr
);
290 expr
->type
= pet_expr_unary
;
293 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
296 expr
->args
[pet_un_arg
] = arg
;
304 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
306 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
307 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
309 struct pet_expr
*expr
;
313 expr
= isl_alloc_type(ctx
, struct pet_expr
);
317 expr
->type
= pet_expr_binary
;
320 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
323 expr
->args
[pet_bin_lhs
] = lhs
;
324 expr
->args
[pet_bin_rhs
] = rhs
;
333 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
335 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
336 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
338 struct pet_expr
*expr
;
340 if (!cond
|| !lhs
|| !rhs
)
342 expr
= isl_alloc_type(ctx
, struct pet_expr
);
346 expr
->type
= pet_expr_ternary
;
348 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
351 expr
->args
[pet_ter_cond
] = cond
;
352 expr
->args
[pet_ter_true
] = lhs
;
353 expr
->args
[pet_ter_false
] = rhs
;
363 /* Construct a call pet_expr that calls function "name" with "n_arg"
364 * arguments. The caller is responsible for filling in the arguments.
366 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
369 struct pet_expr
*expr
;
371 expr
= isl_alloc_type(ctx
, struct pet_expr
);
375 expr
->type
= pet_expr_call
;
377 expr
->name
= strdup(name
);
378 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
379 if (!expr
->name
|| !expr
->args
)
380 return pet_expr_free(expr
);
385 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
387 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
388 struct pet_expr
*arg
)
390 struct pet_expr
*expr
;
395 expr
= isl_alloc_type(ctx
, struct pet_expr
);
399 expr
->type
= pet_expr_cast
;
401 expr
->type_name
= strdup(type_name
);
402 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
403 if (!expr
->type_name
|| !expr
->args
)
415 /* Construct a pet_expr that represents the double "d".
417 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
419 struct pet_expr
*expr
;
421 expr
= isl_calloc_type(ctx
, struct pet_expr
);
425 expr
->type
= pet_expr_double
;
427 expr
->d
.s
= strdup(s
);
429 return pet_expr_free(expr
);
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 case pet_expr_binary
:
462 case pet_expr_ternary
:
470 static void expr_dump(struct pet_expr
*expr
, int indent
)
477 fprintf(stderr
, "%*s", indent
, "");
479 switch (expr
->type
) {
480 case pet_expr_double
:
481 fprintf(stderr
, "%s\n", expr
->d
.s
);
483 case pet_expr_access
:
484 if (expr
->acc
.ref_id
) {
485 isl_id_dump(expr
->acc
.ref_id
);
486 fprintf(stderr
, "%*s", indent
, "");
488 isl_map_dump(expr
->acc
.access
);
489 fprintf(stderr
, "%*s", indent
, "");
490 isl_multi_pw_aff_dump(expr
->acc
.index
);
491 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
493 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
494 "", expr
->acc
.write
);
495 for (i
= 0; i
< expr
->n_arg
; ++i
)
496 expr_dump(expr
->args
[i
], indent
+ 2);
499 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
500 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
502 case pet_expr_binary
:
503 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
504 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
505 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
507 case pet_expr_ternary
:
508 fprintf(stderr
, "?:\n");
509 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
510 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
511 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
514 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
515 for (i
= 0; i
< expr
->n_arg
; ++i
)
516 expr_dump(expr
->args
[i
], indent
+ 2);
519 fprintf(stderr
, "(%s)\n", expr
->type_name
);
520 for (i
= 0; i
< expr
->n_arg
; ++i
)
521 expr_dump(expr
->args
[i
], indent
+ 2);
526 void pet_expr_dump(struct pet_expr
*expr
)
531 /* Does "expr" represent an access to an unnamed space, i.e.,
532 * does it represent an affine expression?
534 int pet_expr_is_affine(struct pet_expr
*expr
)
540 if (expr
->type
!= pet_expr_access
)
543 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
550 /* Return the identifier of the array accessed by "expr".
552 * If "expr" represents a member access, then return the identifier
553 * of the outer structure array.
555 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
559 if (expr
->type
!= pet_expr_access
)
562 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
566 space
= isl_map_get_space(expr
->acc
.access
);
567 space
= isl_space_range(space
);
568 while (space
&& isl_space_is_wrapping(space
))
569 space
= isl_space_domain(isl_space_unwrap(space
));
570 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
571 isl_space_free(space
);
576 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
579 /* Align the parameters of expr->acc.index and expr->acc.access.
581 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
585 if (expr
->type
!= pet_expr_access
)
586 return pet_expr_free(expr
);
588 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
589 isl_multi_pw_aff_get_space(expr
->acc
.index
));
590 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
591 isl_map_get_space(expr
->acc
.access
));
592 if (!expr
->acc
.access
|| !expr
->acc
.index
)
593 return pet_expr_free(expr
);
598 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
600 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
604 if (expr
->type
!= pet_expr_access
)
607 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
610 /* Return 1 if the two pet_exprs are equivalent.
612 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
616 if (!expr1
|| !expr2
)
619 if (expr1
->type
!= expr2
->type
)
621 if (expr1
->n_arg
!= expr2
->n_arg
)
623 for (i
= 0; i
< expr1
->n_arg
; ++i
)
624 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
626 switch (expr1
->type
) {
627 case pet_expr_double
:
628 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
630 if (expr1
->d
.val
!= expr2
->d
.val
)
633 case pet_expr_access
:
634 if (expr1
->acc
.read
!= expr2
->acc
.read
)
636 if (expr1
->acc
.write
!= expr2
->acc
.write
)
638 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
640 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
642 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
644 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
646 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
651 case pet_expr_binary
:
652 case pet_expr_ternary
:
653 if (expr1
->op
!= expr2
->op
)
657 if (strcmp(expr1
->name
, expr2
->name
))
661 if (strcmp(expr1
->type_name
, expr2
->type_name
))
669 /* Add extra conditions on the parameters to all access relations in "expr".
671 * The conditions are not added to the index expression. Instead, they
672 * are used to try and simplifty the index expression.
674 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
675 __isl_take isl_set
*cond
)
682 for (i
= 0; i
< expr
->n_arg
; ++i
) {
683 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
689 if (expr
->type
== pet_expr_access
) {
690 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
692 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
693 expr
->acc
.index
, isl_set_copy(cond
));
694 if (!expr
->acc
.access
|| !expr
->acc
.index
)
702 return pet_expr_free(expr
);
705 /* Tag the access relation "access" with "id".
706 * That is, insert the id as the range of a wrapped relation
707 * in the domain of "access".
709 * If "access" is of the form
713 * then the result is of the form
715 * [D[i] -> id[]] -> A[a]
717 static __isl_give isl_map
*tag_access(__isl_take isl_map
*access
,
718 __isl_take isl_id
*id
)
723 space
= isl_space_range(isl_map_get_space(access
));
724 space
= isl_space_from_range(space
);
725 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
726 add_tag
= isl_map_universe(space
);
727 access
= isl_map_domain_product(access
, add_tag
);
732 /* Modify all expressions of type pet_expr_access in "expr"
733 * by calling "fn" on them.
735 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
736 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
744 for (i
= 0; i
< expr
->n_arg
; ++i
) {
745 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
747 return pet_expr_free(expr
);
750 if (expr
->type
== pet_expr_access
)
751 expr
= fn(expr
, user
);
756 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
758 * Return -1 on error (where fn return a negative value is treated as an error).
759 * Otherwise return 0.
761 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
762 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
769 for (i
= 0; i
< expr
->n_arg
; ++i
)
770 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
773 if (expr
->type
== pet_expr_access
)
774 return fn(expr
, user
);
779 /* Modify the access relation and index expression
780 * of the given access expression
781 * based on the given iteration space transformation.
782 * In particular, precompose the access relation and index expression
783 * with the update function.
785 * If the access has any arguments then the domain of the access relation
786 * is a wrapped mapping from the iteration space to the space of
787 * argument values. We only need to change the domain of this wrapped
788 * mapping, so we extend the input transformation with an identity mapping
789 * on the space of argument values.
791 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
793 isl_multi_pw_aff
*update
= user
;
796 update
= isl_multi_pw_aff_copy(update
);
798 space
= isl_map_get_space(expr
->acc
.access
);
799 space
= isl_space_domain(space
);
800 if (!isl_space_is_wrapping(space
))
801 isl_space_free(space
);
803 isl_multi_pw_aff
*id
;
804 space
= isl_space_unwrap(space
);
805 space
= isl_space_range(space
);
806 space
= isl_space_map_from_set(space
);
807 id
= isl_multi_pw_aff_identity(space
);
808 update
= isl_multi_pw_aff_product(update
, id
);
811 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
813 isl_multi_pw_aff_copy(update
));
814 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
815 expr
->acc
.index
, update
);
816 if (!expr
->acc
.access
|| !expr
->acc
.index
)
817 return pet_expr_free(expr
);
822 /* Modify all access relations in "expr" by precomposing them with
823 * the given iteration space transformation.
825 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
826 __isl_take isl_multi_pw_aff
*update
)
828 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
829 isl_multi_pw_aff_free(update
);
833 /* Construct a pet_stmt with given line number and statement
834 * number from a pet_expr.
835 * The initial iteration domain is the zero-dimensional universe.
836 * The name of the domain is given by "label" if it is non-NULL.
837 * Otherwise, the name is constructed as S_<id>.
838 * The domains of all access relations are modified to refer
839 * to the statement iteration domain.
841 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
842 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
844 struct pet_stmt
*stmt
;
848 isl_multi_pw_aff
*add_name
;
854 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
858 dim
= isl_space_set_alloc(ctx
, 0, 0);
860 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
862 snprintf(name
, sizeof(name
), "S_%d", id
);
863 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
865 dom
= isl_set_universe(isl_space_copy(dim
));
866 sched
= isl_map_from_domain(isl_set_copy(dom
));
868 dim
= isl_space_from_domain(dim
);
869 add_name
= isl_multi_pw_aff_zero(dim
);
870 expr
= expr_update_domain(expr
, add_name
);
874 stmt
->schedule
= sched
;
877 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
878 return pet_stmt_free(stmt
);
887 void *pet_stmt_free(struct pet_stmt
*stmt
)
894 isl_set_free(stmt
->domain
);
895 isl_map_free(stmt
->schedule
);
896 pet_expr_free(stmt
->body
);
898 for (i
= 0; i
< stmt
->n_arg
; ++i
)
899 pet_expr_free(stmt
->args
[i
]);
906 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
913 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
914 fprintf(stderr
, "%*s", indent
, "");
915 isl_set_dump(stmt
->domain
);
916 fprintf(stderr
, "%*s", indent
, "");
917 isl_map_dump(stmt
->schedule
);
918 expr_dump(stmt
->body
, indent
);
919 for (i
= 0; i
< stmt
->n_arg
; ++i
)
920 expr_dump(stmt
->args
[i
], indent
+ 2);
923 void pet_stmt_dump(struct pet_stmt
*stmt
)
928 /* Allocate a new pet_type with the given "name" and "definition".
930 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
931 const char *definition
)
933 struct pet_type
*type
;
935 type
= isl_alloc_type(ctx
, struct pet_type
);
939 type
->name
= strdup(name
);
940 type
->definition
= strdup(definition
);
942 if (!type
->name
|| !type
->definition
)
943 return pet_type_free(type
);
948 /* Free "type" and return NULL.
950 struct pet_type
*pet_type_free(struct pet_type
*type
)
956 free(type
->definition
);
962 struct pet_array
*pet_array_free(struct pet_array
*array
)
967 isl_set_free(array
->context
);
968 isl_set_free(array
->extent
);
969 isl_set_free(array
->value_bounds
);
970 free(array
->element_type
);
976 void pet_array_dump(struct pet_array
*array
)
981 isl_set_dump(array
->context
);
982 isl_set_dump(array
->extent
);
983 isl_set_dump(array
->value_bounds
);
984 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
985 array
->element_is_record
? " element-is-record" : "",
986 array
->live_out
? " live-out" : "");
989 /* Alloc a pet_scop structure, with extra room for information that
990 * is only used during parsing.
992 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
994 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
997 /* Construct a pet_scop with room for n statements.
999 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
1002 struct pet_scop
*scop
;
1004 scop
= pet_scop_alloc(ctx
);
1008 space
= isl_space_params_alloc(ctx
, 0);
1009 scop
->context
= isl_set_universe(isl_space_copy(space
));
1010 scop
->context_value
= isl_set_universe(space
);
1011 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
1012 if (!scop
->context
|| !scop
->stmts
)
1013 return pet_scop_free(scop
);
1020 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
1022 return scop_alloc(ctx
, 0);
1025 /* Update "context" with respect to the valid parameter values for "access".
1027 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
1028 __isl_take isl_set
*context
)
1030 context
= isl_set_intersect(context
,
1031 isl_map_params(isl_map_copy(access
)));
1035 /* Update "context" with respect to the valid parameter values for "expr".
1037 * If "expr" represents a ternary operator, then a parameter value
1038 * needs to be valid for the condition and for at least one of the
1039 * remaining two arguments.
1040 * If the condition is an affine expression, then we can be a bit more specific.
1041 * The parameter then has to be valid for the second argument for
1042 * non-zero accesses and valid for the third argument for zero accesses.
1044 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
1045 __isl_take isl_set
*context
)
1049 if (expr
->type
== pet_expr_ternary
) {
1051 isl_set
*context1
, *context2
;
1053 is_aff
= pet_expr_is_affine(expr
->args
[0]);
1057 context
= expr_extract_context(expr
->args
[0], context
);
1058 context1
= expr_extract_context(expr
->args
[1],
1059 isl_set_copy(context
));
1060 context2
= expr_extract_context(expr
->args
[2], context
);
1066 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
1067 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
1068 zero_set
= isl_map_params(access
);
1069 context1
= isl_set_subtract(context1
,
1070 isl_set_copy(zero_set
));
1071 context2
= isl_set_intersect(context2
, zero_set
);
1074 context
= isl_set_union(context1
, context2
);
1075 context
= isl_set_coalesce(context
);
1080 for (i
= 0; i
< expr
->n_arg
; ++i
)
1081 context
= expr_extract_context(expr
->args
[i
], context
);
1083 if (expr
->type
== pet_expr_access
)
1084 context
= access_extract_context(expr
->acc
.access
, context
);
1088 isl_set_free(context
);
1092 /* Update "context" with respect to the valid parameter values for "stmt".
1094 * If the statement is an assume statement with an affine expression,
1095 * then intersect "context" with that expression.
1096 * Otherwise, intersect "context" with the contexts of the expressions
1099 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
1100 __isl_take isl_set
*context
)
1104 if (pet_stmt_is_assume(stmt
) &&
1105 pet_expr_is_affine(stmt
->body
->args
[0])) {
1106 isl_multi_pw_aff
*index
;
1110 index
= stmt
->body
->args
[0]->acc
.index
;
1111 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
1112 cond
= isl_set_params(isl_pw_aff_non_zero_set(pa
));
1113 return isl_set_intersect(context
, cond
);
1116 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1117 context
= expr_extract_context(stmt
->args
[i
], context
);
1119 context
= expr_extract_context(stmt
->body
, context
);
1124 /* Construct a pet_scop that contains the given pet_stmt.
1126 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
1128 struct pet_scop
*scop
;
1133 scop
= scop_alloc(ctx
, 1);
1137 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
1141 scop
->stmts
[0] = stmt
;
1145 pet_stmt_free(stmt
);
1146 pet_scop_free(scop
);
1150 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1151 * does it represent an affine expression?
1153 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
1157 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
1164 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1166 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
1167 __isl_take isl_set
*dom
)
1170 pa
= isl_set_indicator_function(set
);
1171 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1175 /* Return "lhs || rhs", defined on the shared definition domain.
1177 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1178 __isl_take isl_pw_aff
*rhs
)
1183 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1184 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1185 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1186 isl_pw_aff_non_zero_set(rhs
));
1187 cond
= isl_set_coalesce(cond
);
1188 return indicator_function(cond
, dom
);
1191 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1192 * ext may be equal to either ext1 or ext2.
1194 * The two skips that need to be combined are assumed to be affine expressions.
1196 * We need to skip in ext if we need to skip in either ext1 or ext2.
1197 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1199 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1200 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1203 isl_pw_aff
*skip
, *skip1
, *skip2
;
1207 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1209 if (!ext1
->skip
[type
]) {
1212 ext
->skip
[type
] = ext2
->skip
[type
];
1213 ext2
->skip
[type
] = NULL
;
1216 if (!ext2
->skip
[type
]) {
1219 ext
->skip
[type
] = ext1
->skip
[type
];
1220 ext1
->skip
[type
] = NULL
;
1224 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1225 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1226 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1227 isl_error_internal
, "can only combine affine skips",
1230 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1231 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1232 skip
= pw_aff_or(skip1
, skip2
);
1233 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1234 ext1
->skip
[type
] = NULL
;
1235 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1236 ext2
->skip
[type
] = NULL
;
1237 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1238 if (!ext
->skip
[type
])
1243 pet_scop_free(&ext
->scop
);
1247 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1248 * where type takes on the values pet_skip_now and pet_skip_later.
1249 * scop may be equal to either scop1 or scop2.
1251 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1252 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1254 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1255 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1256 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1258 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1259 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1263 /* Update scop->start and scop->end to include the region from "start"
1264 * to "end". In particular, if scop->end == 0, then "scop" does not
1265 * have any offset information yet and we simply take the information
1266 * from "start" and "end". Otherwise, we update the fields if the
1267 * region from "start" to "end" is not already included.
1269 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1270 unsigned start
, unsigned end
)
1274 if (scop
->end
== 0) {
1275 scop
->start
= start
;
1278 if (start
< scop
->start
)
1279 scop
->start
= start
;
1280 if (end
> scop
->end
)
1287 /* Does "implication" appear in the list of implications of "scop"?
1289 static int is_known_implication(struct pet_scop
*scop
,
1290 struct pet_implication
*implication
)
1294 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1295 struct pet_implication
*pi
= scop
->implications
[i
];
1298 if (pi
->satisfied
!= implication
->satisfied
)
1300 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1310 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1311 * in "scop", removing duplicates (i.e., implications in "scop2" that
1312 * already appear in "scop1").
1314 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1315 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1322 if (scop2
->n_implication
== 0) {
1323 scop
->n_implication
= scop1
->n_implication
;
1324 scop
->implications
= scop1
->implications
;
1325 scop1
->n_implication
= 0;
1326 scop1
->implications
= NULL
;
1330 if (scop1
->n_implication
== 0) {
1331 scop
->n_implication
= scop2
->n_implication
;
1332 scop
->implications
= scop2
->implications
;
1333 scop2
->n_implication
= 0;
1334 scop2
->implications
= NULL
;
1338 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1339 scop1
->n_implication
+ scop2
->n_implication
);
1340 if (!scop
->implications
)
1341 return pet_scop_free(scop
);
1343 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1344 scop
->implications
[i
] = scop1
->implications
[i
];
1345 scop1
->implications
[i
] = NULL
;
1348 scop
->n_implication
= scop1
->n_implication
;
1349 j
= scop1
->n_implication
;
1350 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1353 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1355 return pet_scop_free(scop
);
1358 scop
->implications
[j
++] = scop2
->implications
[i
];
1359 scop2
->implications
[i
] = NULL
;
1361 scop
->n_implication
= j
;
1366 /* Combine the offset information of "scop1" and "scop2" into "scop".
1368 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1369 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1372 scop
= pet_scop_update_start_end(scop
,
1373 scop1
->start
, scop1
->end
);
1375 scop
= pet_scop_update_start_end(scop
,
1376 scop2
->start
, scop2
->end
);
1380 /* Construct a pet_scop that contains the offset information,
1381 * arrays, statements and skip information in "scop1" and "scop2".
1383 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1384 struct pet_scop
*scop2
)
1387 struct pet_scop
*scop
= NULL
;
1389 if (!scop1
|| !scop2
)
1392 if (scop1
->n_stmt
== 0) {
1393 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1394 pet_scop_free(scop1
);
1398 if (scop2
->n_stmt
== 0) {
1399 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1400 pet_scop_free(scop2
);
1404 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1408 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1409 scop1
->n_array
+ scop2
->n_array
);
1412 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1414 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1415 scop
->stmts
[i
] = scop1
->stmts
[i
];
1416 scop1
->stmts
[i
] = NULL
;
1419 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1420 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1421 scop2
->stmts
[i
] = NULL
;
1424 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1425 scop
->arrays
[i
] = scop1
->arrays
[i
];
1426 scop1
->arrays
[i
] = NULL
;
1429 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1430 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1431 scop2
->arrays
[i
] = NULL
;
1434 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1435 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1436 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1437 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1438 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1440 pet_scop_free(scop1
);
1441 pet_scop_free(scop2
);
1444 pet_scop_free(scop1
);
1445 pet_scop_free(scop2
);
1446 pet_scop_free(scop
);
1450 /* Apply the skip condition "skip" to "scop".
1451 * That is, make sure "scop" is not executed when the condition holds.
1453 * If "skip" is an affine expression, we add the conditions under
1454 * which the expression is zero to the iteration domains.
1455 * Otherwise, we add a filter on the variable attaining the value zero.
1457 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1458 __isl_take isl_multi_pw_aff
*skip
)
1467 is_aff
= multi_pw_aff_is_affine(skip
);
1472 return pet_scop_filter(scop
, skip
, 0);
1474 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1475 isl_multi_pw_aff_free(skip
);
1476 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1477 scop
= pet_scop_restrict(scop
, zero
);
1481 isl_multi_pw_aff_free(skip
);
1482 return pet_scop_free(scop
);
1485 /* Construct a pet_scop that contains the arrays, statements and
1486 * skip information in "scop1" and "scop2", where the two scops
1487 * are executed "in sequence". That is, breaks and continues
1488 * in scop1 have an effect on scop2.
1490 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1491 struct pet_scop
*scop2
)
1493 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1494 scop2
= restrict_skip(scop2
,
1495 pet_scop_get_skip(scop1
, pet_skip_now
));
1496 return pet_scop_add(ctx
, scop1
, scop2
);
1499 /* Construct a pet_scop that contains the arrays, statements and
1500 * skip information in "scop1" and "scop2", where the two scops
1501 * are executed "in parallel". That is, any break or continue
1502 * in scop1 has no effect on scop2.
1504 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1505 struct pet_scop
*scop2
)
1507 return pet_scop_add(ctx
, scop1
, scop2
);
1510 void *pet_implication_free(struct pet_implication
*implication
)
1517 isl_map_free(implication
->extension
);
1523 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1526 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1530 isl_set_free(scop
->context
);
1531 isl_set_free(scop
->context_value
);
1533 for (i
= 0; i
< scop
->n_type
; ++i
)
1534 pet_type_free(scop
->types
[i
]);
1537 for (i
= 0; i
< scop
->n_array
; ++i
)
1538 pet_array_free(scop
->arrays
[i
]);
1541 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1542 pet_stmt_free(scop
->stmts
[i
]);
1544 if (scop
->implications
)
1545 for (i
= 0; i
< scop
->n_implication
; ++i
)
1546 pet_implication_free(scop
->implications
[i
]);
1547 free(scop
->implications
);
1548 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1549 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1554 void pet_type_dump(struct pet_type
*type
)
1559 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1562 void pet_implication_dump(struct pet_implication
*implication
)
1567 fprintf(stderr
, "%d\n", implication
->satisfied
);
1568 isl_map_dump(implication
->extension
);
1571 void pet_scop_dump(struct pet_scop
*scop
)
1574 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1579 isl_set_dump(scop
->context
);
1580 isl_set_dump(scop
->context_value
);
1581 for (i
= 0; i
< scop
->n_type
; ++i
)
1582 pet_type_dump(scop
->types
[i
]);
1583 for (i
= 0; i
< scop
->n_array
; ++i
)
1584 pet_array_dump(scop
->arrays
[i
]);
1585 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1586 pet_stmt_dump(scop
->stmts
[i
]);
1587 for (i
= 0; i
< scop
->n_implication
; ++i
)
1588 pet_implication_dump(scop
->implications
[i
]);
1591 fprintf(stderr
, "skip\n");
1592 isl_multi_pw_aff_dump(ext
->skip
[0]);
1593 isl_multi_pw_aff_dump(ext
->skip
[1]);
1597 /* Return 1 if the two pet_arrays are equivalent.
1599 * We don't compare element_size as this may be target dependent.
1601 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1603 if (!array1
|| !array2
)
1606 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1608 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1610 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1612 if (array1
->value_bounds
&&
1613 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1615 if (strcmp(array1
->element_type
, array2
->element_type
))
1617 if (array1
->element_is_record
!= array2
->element_is_record
)
1619 if (array1
->live_out
!= array2
->live_out
)
1621 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1623 if (array1
->declared
!= array2
->declared
)
1625 if (array1
->exposed
!= array2
->exposed
)
1631 /* Return 1 if the two pet_stmts are equivalent.
1633 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1637 if (!stmt1
|| !stmt2
)
1640 if (stmt1
->line
!= stmt2
->line
)
1642 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1644 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1646 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1648 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1650 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1651 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1658 /* Return 1 if the two pet_types are equivalent.
1660 * We only compare the names of the types since the exact representation
1661 * of the definition may depend on the version of clang being used.
1663 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1665 if (!type1
|| !type2
)
1668 if (strcmp(type1
->name
, type2
->name
))
1674 /* Return 1 if the two pet_implications are equivalent.
1676 int pet_implication_is_equal(struct pet_implication
*implication1
,
1677 struct pet_implication
*implication2
)
1679 if (!implication1
|| !implication2
)
1682 if (implication1
->satisfied
!= implication2
->satisfied
)
1684 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1690 /* Return 1 if the two pet_scops are equivalent.
1692 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1696 if (!scop1
|| !scop2
)
1699 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1701 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1704 if (scop1
->n_type
!= scop2
->n_type
)
1706 for (i
= 0; i
< scop1
->n_type
; ++i
)
1707 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1710 if (scop1
->n_array
!= scop2
->n_array
)
1712 for (i
= 0; i
< scop1
->n_array
; ++i
)
1713 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1716 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1718 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1719 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1722 if (scop1
->n_implication
!= scop2
->n_implication
)
1724 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1725 if (!pet_implication_is_equal(scop1
->implications
[i
],
1726 scop2
->implications
[i
]))
1732 /* Prefix the schedule of "stmt" with an extra dimension with constant
1735 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1740 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1741 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1742 if (!stmt
->schedule
)
1743 return pet_stmt_free(stmt
);
1748 /* Prefix the schedules of all statements in "scop" with an extra
1749 * dimension with constant value "pos".
1751 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1758 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1759 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1760 if (!scop
->stmts
[i
])
1761 return pet_scop_free(scop
);
1767 /* Given a set with a parameter at "param_pos" that refers to the
1768 * iterator, "move" the iterator to the first set dimension.
1769 * That is, essentially equate the parameter to the first set dimension
1770 * and then project it out.
1772 * The first set dimension may however refer to a virtual iterator,
1773 * while the parameter refers to the "real" iterator.
1774 * We therefore need to take into account the affine expression "iv_map", which
1775 * expresses the real iterator in terms of the virtual iterator.
1776 * In particular, we equate the set dimension to the input of the map
1777 * and the parameter to the output of the map and then project out
1778 * everything we don't need anymore.
1780 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1781 int param_pos
, __isl_take isl_aff
*iv_map
)
1783 isl_map
*map
, *map2
;
1784 map
= isl_map_from_domain(set
);
1785 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1786 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1787 map2
= isl_map_from_aff(iv_map
);
1788 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1789 map
= isl_map_apply_range(map
, map2
);
1790 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1791 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1792 return isl_map_domain(map
);
1795 /* Data used in embed_access.
1796 * extend adds an iterator to the iteration domain (through precomposition).
1797 * iv_map expresses the real iterator in terms of the virtual iterator
1798 * var_id represents the induction variable of the corresponding loop
1800 struct pet_embed_access
{
1801 isl_multi_pw_aff
*extend
;
1806 /* Given an index expression, return an expression for the outer iterator.
1808 static __isl_give isl_aff
*index_outer_iterator(
1809 __isl_take isl_multi_pw_aff
*index
)
1812 isl_local_space
*ls
;
1814 space
= isl_multi_pw_aff_get_domain_space(index
);
1815 isl_multi_pw_aff_free(index
);
1817 ls
= isl_local_space_from_space(space
);
1818 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1821 /* Replace an index expression that references the new (outer) iterator variable
1822 * by one that references the corresponding (real) iterator.
1824 * The input index expression is of the form
1826 * { S[i',...] -> i[] }
1828 * where i' refers to the virtual iterator.
1830 * iv_map is of the form
1834 * Return the index expression
1836 * { S[i',...] -> [i] }
1838 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1839 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1844 aff
= index_outer_iterator(index
);
1845 space
= isl_aff_get_space(aff
);
1846 iv_map
= isl_aff_align_params(iv_map
, space
);
1847 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1849 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1852 /* Given an index expression "index" that refers to the (real) iterator
1853 * through the parameter at position "pos", plug in "iv_map", expressing
1854 * the real iterator in terms of the virtual (outer) iterator.
1856 * In particular, the index expression is of the form
1858 * [..., i, ...] -> { S[i',...] -> ... i ... }
1860 * where i refers to the real iterator and i' refers to the virtual iterator.
1862 * iv_map is of the form
1866 * Return the index expression
1868 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1871 * We first move the parameter to the input
1873 * [..., ...] -> { [i, i',...] -> ... i ... }
1877 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1879 * and then combine the two to obtain the desired result.
1881 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1882 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1884 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1887 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1888 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1889 isl_dim_param
, pos
, 1);
1891 space
= isl_space_map_from_set(space
);
1892 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1893 iv_map
= isl_aff_align_params(iv_map
, space
);
1894 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1895 ma
= isl_multi_aff_flat_range_product(
1896 isl_multi_aff_from_aff(iv_map
), ma
);
1897 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1902 /* Does the index expression "index" reference a virtual array, i.e.,
1903 * one with user pointer equal to NULL?
1904 * A virtual array does not have any members.
1906 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1911 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1913 if (isl_multi_pw_aff_range_is_wrapping(index
))
1915 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1916 is_virtual
= !isl_id_get_user(id
);
1922 /* Does the access relation "access" reference a virtual array, i.e.,
1923 * one with user pointer equal to NULL?
1924 * A virtual array does not have any members.
1926 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1931 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1933 if (isl_map_range_is_wrapping(access
))
1935 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1936 is_virtual
= !isl_id_get_user(id
);
1942 /* Embed the given index expression in an extra outer loop.
1943 * The domain of the index expression has already been updated.
1945 * If the access refers to the induction variable, then it is
1946 * turned into an access to the set of integers with index (and value)
1947 * equal to the induction variable.
1949 * If the accessed array is a virtual array (with user
1950 * pointer equal to NULL), as created by create_test_index,
1951 * then it is extended along with the domain of the index expression.
1953 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1954 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1956 isl_id
*array_id
= NULL
;
1959 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1960 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1961 if (array_id
== data
->var_id
) {
1962 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1963 } else if (index_is_virtual_array(index
)) {
1965 isl_multi_pw_aff
*mpa
;
1967 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1968 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1969 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1970 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1971 isl_id_copy(array_id
));
1973 isl_id_free(array_id
);
1975 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1976 isl_dim_param
, data
->var_id
);
1978 index
= index_internalize_iv(index
, pos
,
1979 isl_aff_copy(data
->iv_map
));
1980 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1981 isl_id_copy(data
->var_id
));
1986 /* Embed the given access relation in an extra outer loop.
1987 * The domain of the access relation has already been updated.
1989 * If the access refers to the induction variable, then it is
1990 * turned into an access to the set of integers with index (and value)
1991 * equal to the induction variable.
1993 * If the induction variable appears in the constraints (as a parameter),
1994 * then the parameter is equated to the newly introduced iteration
1995 * domain dimension and subsequently projected out.
1997 * Similarly, if the accessed array is a virtual array (with user
1998 * pointer equal to NULL), as created by create_test_index,
1999 * then it is extended along with the domain of the access.
2001 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
2002 struct pet_embed_access
*data
)
2004 isl_id
*array_id
= NULL
;
2007 if (isl_map_has_tuple_id(access
, isl_dim_out
))
2008 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2009 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
2010 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2011 access
= isl_map_equate(access
,
2012 isl_dim_in
, 0, isl_dim_out
, 0);
2013 if (array_id
== data
->var_id
)
2014 access
= isl_map_apply_range(access
,
2015 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
2017 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
2018 isl_id_copy(array_id
));
2020 isl_id_free(array_id
);
2022 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
2024 isl_set
*set
= isl_map_wrap(access
);
2025 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
2026 access
= isl_set_unwrap(set
);
2028 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
2029 isl_id_copy(data
->var_id
));
2034 /* Given an access expression, embed the associated access relation and
2035 * index expression in an extra outer loop.
2037 * We first update the domains to insert the extra dimension and
2038 * then update the access relation and index expression to take
2039 * into account the mapping "iv_map" from virtual iterator
2042 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
2045 struct pet_embed_access
*data
= user
;
2047 expr
= update_domain(expr
, data
->extend
);
2051 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
2052 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
2053 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2054 return pet_expr_free(expr
);
2059 /* Embed all access subexpressions of "expr" in an extra loop.
2060 * "extend" inserts an outer loop iterator in the iteration domains
2061 * (through precomposition).
2062 * "iv_map" expresses the real iterator in terms of the virtual iterator
2063 * "var_id" represents the induction variable.
2065 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
2066 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
2067 __isl_keep isl_id
*var_id
)
2069 struct pet_embed_access data
=
2070 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
2072 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
2073 isl_aff_free(iv_map
);
2074 isl_multi_pw_aff_free(extend
);
2078 /* Embed the given pet_stmt in an extra outer loop with iteration domain
2079 * "dom" and schedule "sched". "var_id" represents the induction variable
2080 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
2081 * That is, it expresses the iterator that some of the parameters in "stmt"
2082 * may refer to in terms of the iterator used in "dom" and
2083 * the domain of "sched".
2085 * The iteration domain and schedule of the statement are updated
2086 * according to the iteration domain and schedule of the new loop.
2087 * If stmt->domain is a wrapped map, then the iteration domain
2088 * is the domain of this map, so we need to be careful to adjust
2091 * If the induction variable appears in the constraints (as a parameter)
2092 * of the current iteration domain or the schedule of the statement,
2093 * then the parameter is equated to the newly introduced iteration
2094 * domain dimension and subsequently projected out.
2096 * Finally, all access relations are updated based on the extra loop.
2098 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
2099 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
2100 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
2106 isl_multi_pw_aff
*extend
;
2111 if (isl_set_is_wrapping(stmt
->domain
)) {
2116 map
= isl_set_unwrap(stmt
->domain
);
2117 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
2118 ran_dim
= isl_space_range(isl_map_get_space(map
));
2119 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
2120 isl_set_universe(ran_dim
));
2121 map
= isl_map_flat_domain_product(ext
, map
);
2122 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
2123 isl_id_copy(stmt_id
));
2124 dim
= isl_space_domain(isl_map_get_space(map
));
2125 stmt
->domain
= isl_map_wrap(map
);
2127 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
2128 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
2130 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
2131 isl_id_copy(stmt_id
));
2132 dim
= isl_set_get_space(stmt
->domain
);
2135 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
2137 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
2138 isl_aff_copy(iv_map
));
2140 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
2141 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
2142 isl_dim_in
, stmt_id
);
2144 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
2146 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
2147 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
2148 stmt
->schedule
= isl_set_unwrap(set
);
2151 dim
= isl_space_map_from_set(dim
);
2152 extend
= isl_multi_pw_aff_identity(dim
);
2153 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
2154 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
2155 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
2156 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2157 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
2158 isl_multi_pw_aff_copy(extend
),
2159 isl_aff_copy(iv_map
), var_id
);
2160 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
2163 isl_id_free(var_id
);
2165 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2167 return pet_stmt_free(stmt
);
2168 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2169 return pet_stmt_free(stmt
);
2173 isl_map_free(sched
);
2174 isl_aff_free(iv_map
);
2175 isl_id_free(var_id
);
2179 /* Embed the given pet_array in an extra outer loop with iteration domain
2181 * This embedding only has an effect on virtual arrays (those with
2182 * user pointer equal to NULL), which need to be extended along with
2183 * the iteration domain.
2185 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
2186 __isl_take isl_set
*dom
)
2188 isl_id
*array_id
= NULL
;
2193 if (isl_set_has_tuple_id(array
->extent
))
2194 array_id
= isl_set_get_tuple_id(array
->extent
);
2196 if (array_id
&& !isl_id_get_user(array_id
)) {
2197 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
2198 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
2200 return pet_array_free(array
);
2203 isl_id_free(array_id
);
2212 /* Project out all unnamed parameters from "set" and return the result.
2214 static __isl_give isl_set
*set_project_out_unnamed_params(
2215 __isl_take isl_set
*set
)
2219 n
= isl_set_dim(set
, isl_dim_param
);
2220 for (i
= n
- 1; i
>= 0; --i
) {
2221 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
2223 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
2229 /* Update the context with respect to an embedding into a loop
2230 * with iteration domain "dom" and induction variable "id".
2231 * "iv_map" expresses the real iterator (parameter "id") in terms
2232 * of a possibly virtual iterator (used in "dom").
2234 * If the current context is independent of "id", we don't need
2236 * Otherwise, a parameter value is invalid for the embedding if
2237 * any of the corresponding iterator values is invalid.
2238 * That is, a parameter value is valid only if all the corresponding
2239 * iterator values are valid.
2240 * We therefore compute the set of parameters
2242 * forall i in dom : valid (i)
2246 * not exists i in dom : not valid(i)
2250 * not exists i in dom \ valid(i)
2252 * Before we subtract valid(i) from dom, we first need to substitute
2253 * the real iterator for the virtual iterator.
2255 * If there are any unnamed parameters in "dom", then we consider
2256 * a parameter value to be valid if it is valid for any value of those
2257 * unnamed parameters. They are therefore projected out at the end.
2259 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
2260 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
2261 __isl_keep isl_id
*id
)
2266 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
2270 context
= isl_set_from_params(context
);
2271 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
2272 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
2273 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
2274 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
2275 context
= isl_set_preimage_multi_aff(context
, ma
);
2276 context
= isl_set_subtract(isl_set_copy(dom
), context
);
2277 context
= isl_set_params(context
);
2278 context
= isl_set_complement(context
);
2279 context
= set_project_out_unnamed_params(context
);
2283 /* Update the implication with respect to an embedding into a loop
2284 * with iteration domain "dom".
2286 * Since embed_access extends virtual arrays along with the domain
2287 * of the access, we need to do the same with domain and range
2288 * of the implication. Since the original implication is only valid
2289 * within a given iteration of the loop, the extended implication
2290 * maps the extra array dimension corresponding to the extra loop
2293 static struct pet_implication
*pet_implication_embed(
2294 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
2302 map
= isl_set_identity(dom
);
2303 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
2304 map
= isl_map_flat_product(map
, implication
->extension
);
2305 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
2306 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
2307 implication
->extension
= map
;
2308 if (!implication
->extension
)
2309 return pet_implication_free(implication
);
2317 /* Embed all statements and arrays in "scop" in an extra outer loop
2318 * with iteration domain "dom" and schedule "sched".
2319 * "id" represents the induction variable of the loop.
2320 * "iv_map" maps a possibly virtual iterator to the real iterator.
2321 * That is, it expresses the iterator that some of the parameters in "scop"
2322 * may refer to in terms of the iterator used in "dom" and
2323 * the domain of "sched".
2325 * Any skip conditions within the loop have no effect outside of the loop.
2326 * The caller is responsible for making sure skip[pet_skip_later] has been
2327 * taken into account.
2329 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
2330 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
2331 __isl_take isl_id
*id
)
2338 pet_scop_reset_skip(scop
, pet_skip_now
);
2339 pet_scop_reset_skip(scop
, pet_skip_later
);
2341 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
2345 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2346 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
2347 isl_set_copy(dom
), isl_map_copy(sched
),
2348 isl_aff_copy(iv_map
), isl_id_copy(id
));
2349 if (!scop
->stmts
[i
])
2353 for (i
= 0; i
< scop
->n_array
; ++i
) {
2354 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
2356 if (!scop
->arrays
[i
])
2360 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2361 scop
->implications
[i
] =
2362 pet_implication_embed(scop
->implications
[i
],
2364 if (!scop
->implications
[i
])
2369 isl_map_free(sched
);
2370 isl_aff_free(iv_map
);
2375 isl_map_free(sched
);
2376 isl_aff_free(iv_map
);
2378 return pet_scop_free(scop
);
2381 /* Add extra conditions on the parameters to iteration domain of "stmt".
2383 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
2384 __isl_take isl_set
*cond
)
2389 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
2394 return pet_stmt_free(stmt
);
2397 /* Add extra conditions to scop->skip[type].
2399 * The new skip condition only holds if it held before
2400 * and the condition is true. It does not hold if it did not hold
2401 * before or the condition is false.
2403 * The skip condition is assumed to be an affine expression.
2405 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
2406 enum pet_skip type
, __isl_keep isl_set
*cond
)
2408 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2414 if (!ext
->skip
[type
])
2417 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2418 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2419 isl_error_internal
, "can only resrict affine skips",
2420 return pet_scop_free(scop
));
2422 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2423 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2424 cond
= isl_set_copy(cond
);
2425 cond
= isl_set_from_params(cond
);
2426 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2427 skip
= indicator_function(cond
, dom
);
2428 isl_multi_pw_aff_free(ext
->skip
[type
]);
2429 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2430 if (!ext
->skip
[type
])
2431 return pet_scop_free(scop
);
2436 /* Add extra conditions on the parameters to all iteration domains
2437 * and skip conditions.
2439 * A parameter value is valid for the result if it was valid
2440 * for the original scop and satisfies "cond" or if it does
2441 * not satisfy "cond" as in this case the scop is not executed
2442 * and the original constraints on the parameters are irrelevant.
2444 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2445 __isl_take isl_set
*cond
)
2449 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2450 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2455 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2456 scop
->context
= isl_set_union(scop
->context
,
2457 isl_set_complement(isl_set_copy(cond
)));
2458 scop
->context
= isl_set_coalesce(scop
->context
);
2459 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2463 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2464 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2465 isl_set_copy(cond
));
2466 if (!scop
->stmts
[i
])
2474 return pet_scop_free(scop
);
2477 /* Construct a function that (upon precomposition) inserts
2478 * a filter value with name "id" and value "satisfied"
2479 * in the list of filter values embedded in the set space "space".
2481 * If "space" does not contain any filter values yet, we first create
2482 * a function that inserts 0 filter values, i.e.,
2484 * [space -> []] -> space
2486 * We can now assume that space is of the form [dom -> [filters]]
2487 * We construct an identity mapping on dom and a mapping on filters
2488 * that (upon precomposition) inserts the new filter
2491 * [satisfied, filters] -> [filters]
2493 * and then compute the cross product
2495 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2497 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2498 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2502 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2505 if (isl_space_is_wrapping(space
)) {
2506 space2
= isl_space_map_from_set(isl_space_copy(space
));
2507 ma
= isl_multi_aff_identity(space2
);
2508 space
= isl_space_unwrap(space
);
2510 space
= isl_space_from_domain(space
);
2511 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2514 space2
= isl_space_domain(isl_space_copy(space
));
2515 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2516 space
= isl_space_range(space
);
2517 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2518 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2519 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2520 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2521 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2523 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2524 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2529 /* Insert an argument expression corresponding to "test" in front
2530 * of the list of arguments described by *n_arg and *args.
2532 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2533 __isl_keep isl_multi_pw_aff
*test
)
2536 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
2542 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2546 struct pet_expr
**ext
;
2547 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2550 for (i
= 0; i
< *n_arg
; ++i
)
2551 ext
[1 + i
] = (*args
)[i
];
2556 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2563 /* Make the expression "expr" depend on the value of "test"
2564 * being equal to "satisfied".
2566 * If "test" is an affine expression, we simply add the conditions
2567 * on the expression having the value "satisfied" to all access relations
2568 * and index expressions.
2570 * Otherwise, we add a filter to "expr" (which is then assumed to be
2571 * an access expression) corresponding to "test" being equal to "satisfied".
2573 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2574 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2579 isl_pw_multi_aff
*pma
;
2584 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2588 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2589 isl_multi_pw_aff_free(test
);
2591 cond
= isl_pw_aff_non_zero_set(pa
);
2593 cond
= isl_pw_aff_zero_set(pa
);
2594 return pet_expr_restrict(expr
, isl_set_params(cond
));
2597 ctx
= isl_multi_pw_aff_get_ctx(test
);
2598 if (expr
->type
!= pet_expr_access
)
2599 isl_die(ctx
, isl_error_invalid
,
2600 "can only filter access expressions", goto error
);
2602 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2603 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2604 pma
= insert_filter_pma(space
, id
, satisfied
);
2606 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2608 isl_pw_multi_aff_copy(pma
));
2609 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2610 expr
->acc
.index
, pma
);
2611 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2614 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2617 isl_multi_pw_aff_free(test
);
2620 isl_multi_pw_aff_free(test
);
2621 return pet_expr_free(expr
);
2624 /* Look through the applications in "scop" for any that can be
2625 * applied to the filter expressed by "map" and "satisified".
2626 * If there is any, then apply it to "map" and return the result.
2627 * Otherwise, return "map".
2628 * "id" is the identifier of the virtual array.
2630 * We only introduce at most one implication for any given virtual array,
2631 * so we can apply the implication and return as soon as we find one.
2633 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2634 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2638 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2639 struct pet_implication
*pi
= scop
->implications
[i
];
2642 if (pi
->satisfied
!= satisfied
)
2644 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2649 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2655 /* Is the filter expressed by "test" and "satisfied" implied
2656 * by filter "pos" on "domain", with filter "expr", taking into
2657 * account the implications of "scop"?
2659 * For filter on domain implying that expressed by "test" and "satisfied",
2660 * the filter needs to be an access to the same (virtual) array as "test" and
2661 * the filter value needs to be equal to "satisfied".
2662 * Moreover, the filter access relation, possibly extended by
2663 * the implications in "scop" needs to contain "test".
2665 static int implies_filter(struct pet_scop
*scop
,
2666 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2667 __isl_keep isl_map
*test
, int satisfied
)
2669 isl_id
*test_id
, *arg_id
;
2676 if (expr
->type
!= pet_expr_access
)
2678 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2679 arg_id
= pet_expr_access_get_id(expr
);
2680 isl_id_free(arg_id
);
2681 isl_id_free(test_id
);
2682 if (test_id
!= arg_id
)
2684 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2685 is_int
= isl_val_is_int(val
);
2687 s
= isl_val_get_num_si(val
);
2696 implied
= isl_map_copy(expr
->acc
.access
);
2697 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2698 is_subset
= isl_map_is_subset(test
, implied
);
2699 isl_map_free(implied
);
2704 /* Is the filter expressed by "test" and "satisfied" implied
2705 * by any of the filters on the domain of "stmt", taking into
2706 * account the implications of "scop"?
2708 static int filter_implied(struct pet_scop
*scop
,
2709 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2717 if (!scop
|| !stmt
|| !test
)
2719 if (scop
->n_implication
== 0)
2721 if (stmt
->n_arg
== 0)
2724 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2725 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2728 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2729 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2730 test_map
, satisfied
);
2731 if (implied
< 0 || implied
)
2735 isl_map_free(test_map
);
2736 isl_map_free(domain
);
2740 /* Make the statement "stmt" depend on the value of "test"
2741 * being equal to "satisfied" by adjusting stmt->domain.
2743 * The domain of "test" corresponds to the (zero or more) outer dimensions
2744 * of the iteration domain.
2746 * We first extend "test" to apply to the entire iteration domain and
2747 * then check if the filter that we are about to add is implied
2748 * by any of the current filters, possibly taking into account
2749 * the implications in "scop". If so, we leave "stmt" untouched and return.
2751 * Otherwise, we insert an argument corresponding to a read to "test"
2752 * from the iteration domain of "stmt" in front of the list of arguments.
2753 * We also insert a corresponding output dimension in the wrapped
2754 * map contained in stmt->domain, with value set to "satisfied".
2756 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2757 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2763 isl_pw_multi_aff
*pma
;
2764 isl_multi_aff
*add_dom
;
2766 isl_local_space
*ls
;
2772 space
= isl_set_get_space(stmt
->domain
);
2773 if (isl_space_is_wrapping(space
))
2774 space
= isl_space_domain(isl_space_unwrap(space
));
2775 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2776 space
= isl_space_from_domain(space
);
2777 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2778 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2779 ls
= isl_local_space_from_space(isl_space_domain(space
));
2780 for (i
= 0; i
< n_test_dom
; ++i
) {
2782 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2784 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2786 isl_local_space_free(ls
);
2787 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2789 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2793 isl_multi_pw_aff_free(test
);
2797 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2798 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2799 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2801 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2804 isl_multi_pw_aff_free(test
);
2807 isl_multi_pw_aff_free(test
);
2808 return pet_stmt_free(stmt
);
2811 /* Does "scop" have a skip condition of the given "type"?
2813 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2815 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2819 return ext
->skip
[type
] != NULL
;
2822 /* Does "scop" have a skip condition of the given "type" that
2823 * is an affine expression?
2825 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2827 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2831 if (!ext
->skip
[type
])
2833 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2836 /* Does "scop" have a skip condition of the given "type" that
2837 * is not an affine expression?
2839 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2841 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2846 if (!ext
->skip
[type
])
2848 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2854 /* Does "scop" have a skip condition of the given "type" that
2855 * is affine and holds on the entire domain?
2857 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2859 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2865 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2866 if (is_aff
< 0 || !is_aff
)
2869 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2870 set
= isl_pw_aff_non_zero_set(pa
);
2871 is_univ
= isl_set_plain_is_universe(set
);
2877 /* Replace scop->skip[type] by "skip".
2879 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2880 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2882 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2887 isl_multi_pw_aff_free(ext
->skip
[type
]);
2888 ext
->skip
[type
] = skip
;
2892 isl_multi_pw_aff_free(skip
);
2893 return pet_scop_free(scop
);
2896 /* Return a copy of scop->skip[type].
2898 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2901 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2906 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2909 /* Assuming scop->skip[type] is an affine expression,
2910 * return the constraints on the parameters for which the skip condition
2913 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2916 isl_multi_pw_aff
*skip
;
2919 skip
= pet_scop_get_skip(scop
, type
);
2920 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2921 isl_multi_pw_aff_free(skip
);
2922 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2925 /* Return the identifier of the variable that is accessed by
2926 * the skip condition of the given type.
2928 * The skip condition is assumed not to be an affine condition.
2930 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2933 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2938 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2941 /* Return an access pet_expr corresponding to the skip condition
2942 * of the given type.
2944 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2947 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2950 /* Drop the the skip condition scop->skip[type].
2952 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2954 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2959 isl_multi_pw_aff_free(ext
->skip
[type
]);
2960 ext
->skip
[type
] = NULL
;
2963 /* Make the skip condition (if any) depend on the value of "test" being
2964 * equal to "satisfied".
2966 * We only support the case where the original skip condition is universal,
2967 * i.e., where skipping is unconditional, and where satisfied == 1.
2968 * In this case, the skip condition is changed to skip only when
2969 * "test" is equal to one.
2971 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2972 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2978 if (!pet_scop_has_skip(scop
, type
))
2982 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2984 return pet_scop_free(scop
);
2985 if (satisfied
&& is_univ
) {
2986 isl_space
*space
= isl_multi_pw_aff_get_space(test
);
2987 isl_multi_pw_aff
*skip
;
2988 skip
= isl_multi_pw_aff_zero(space
);
2989 scop
= pet_scop_set_skip(scop
, type
, skip
);
2993 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2994 "skip expression cannot be filtered",
2995 return pet_scop_free(scop
));
3001 /* Make all statements in "scop" depend on the value of "test"
3002 * being equal to "satisfied" by adjusting their domains.
3004 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
3005 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
3009 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
3010 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
3015 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3016 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
3017 isl_multi_pw_aff_copy(test
), satisfied
);
3018 if (!scop
->stmts
[i
])
3022 isl_multi_pw_aff_free(test
);
3025 isl_multi_pw_aff_free(test
);
3026 return pet_scop_free(scop
);
3029 /* Add all parameters in "expr" to "space" and return the result.
3031 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
3032 __isl_take isl_space
*space
)
3038 for (i
= 0; i
< expr
->n_arg
; ++i
)
3039 space
= expr_collect_params(expr
->args
[i
], space
);
3041 if (expr
->type
== pet_expr_access
)
3042 space
= isl_space_align_params(space
,
3043 isl_map_get_space(expr
->acc
.access
));
3047 pet_expr_free(expr
);
3048 return isl_space_free(space
);
3051 /* Add all parameters in "stmt" to "space" and return the result.
3053 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
3054 __isl_take isl_space
*space
)
3059 return isl_space_free(space
);
3061 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
3062 space
= isl_space_align_params(space
,
3063 isl_map_get_space(stmt
->schedule
));
3064 for (i
= 0; i
< stmt
->n_arg
; ++i
)
3065 space
= expr_collect_params(stmt
->args
[i
], space
);
3066 space
= expr_collect_params(stmt
->body
, space
);
3071 /* Add all parameters in "array" to "space" and return the result.
3073 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
3074 __isl_take isl_space
*space
)
3077 return isl_space_free(space
);
3079 space
= isl_space_align_params(space
,
3080 isl_set_get_space(array
->context
));
3081 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
3086 /* Add all parameters in "scop" to "space" and return the result.
3088 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
3089 __isl_take isl_space
*space
)
3094 return isl_space_free(space
);
3096 for (i
= 0; i
< scop
->n_array
; ++i
)
3097 space
= array_collect_params(scop
->arrays
[i
], space
);
3099 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3100 space
= stmt_collect_params(scop
->stmts
[i
], space
);
3105 /* Add all parameters in "space" to all access relations and index expressions
3108 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
3109 __isl_take isl_space
*space
)
3116 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3118 expr_propagate_params(expr
->args
[i
],
3119 isl_space_copy(space
));
3124 if (expr
->type
== pet_expr_access
) {
3125 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
3126 isl_space_copy(space
));
3127 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
3128 isl_space_copy(space
));
3129 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3133 isl_space_free(space
);
3136 isl_space_free(space
);
3137 return pet_expr_free(expr
);
3140 /* Add all parameters in "space" to the domain, schedule and
3141 * all access relations in "stmt".
3143 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
3144 __isl_take isl_space
*space
)
3151 stmt
->domain
= isl_set_align_params(stmt
->domain
,
3152 isl_space_copy(space
));
3153 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
3154 isl_space_copy(space
));
3156 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3157 stmt
->args
[i
] = expr_propagate_params(stmt
->args
[i
],
3158 isl_space_copy(space
));
3162 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(space
));
3164 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3167 isl_space_free(space
);
3170 isl_space_free(space
);
3171 return pet_stmt_free(stmt
);
3174 /* Add all parameters in "space" to "array".
3176 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
3177 __isl_take isl_space
*space
)
3182 array
->context
= isl_set_align_params(array
->context
,
3183 isl_space_copy(space
));
3184 array
->extent
= isl_set_align_params(array
->extent
,
3185 isl_space_copy(space
));
3186 if (array
->value_bounds
) {
3187 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
3188 isl_space_copy(space
));
3189 if (!array
->value_bounds
)
3193 if (!array
->context
|| !array
->extent
)
3196 isl_space_free(space
);
3199 isl_space_free(space
);
3200 return pet_array_free(array
);
3203 /* Add all parameters in "space" to "scop".
3205 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
3206 __isl_take isl_space
*space
)
3213 for (i
= 0; i
< scop
->n_array
; ++i
) {
3214 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
3215 isl_space_copy(space
));
3216 if (!scop
->arrays
[i
])
3220 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3221 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
3222 isl_space_copy(space
));
3223 if (!scop
->stmts
[i
])
3227 isl_space_free(space
);
3230 isl_space_free(space
);
3231 return pet_scop_free(scop
);
3234 /* Update all isl_sets and isl_maps in "scop" such that they all
3235 * have the same parameters.
3237 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
3244 space
= isl_set_get_space(scop
->context
);
3245 space
= scop_collect_params(scop
, space
);
3247 scop
->context
= isl_set_align_params(scop
->context
,
3248 isl_space_copy(space
));
3249 scop
= scop_propagate_params(scop
, space
);
3251 if (scop
&& !scop
->context
)
3252 return pet_scop_free(scop
);
3257 /* Check if the given index expression accesses a (0D) array that corresponds
3258 * to one of the parameters in "dim". If so, replace the array access
3259 * by an access to the set of integers with as index (and value)
3262 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
3263 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
3265 isl_local_space
*ls
;
3266 isl_id
*array_id
= NULL
;
3270 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
3271 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
3272 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3274 isl_space_free(space
);
3277 isl_id_free(array_id
);
3281 space
= isl_multi_pw_aff_get_domain_space(index
);
3282 isl_multi_pw_aff_free(index
);
3284 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3286 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
3287 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
3290 isl_id_free(array_id
);
3292 ls
= isl_local_space_from_space(space
);
3293 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
3294 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
3299 /* Check if the given access relation accesses a (0D) array that corresponds
3300 * to one of the parameters in "dim". If so, replace the array access
3301 * by an access to the set of integers with as index (and value)
3304 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
3305 __isl_take isl_space
*dim
)
3307 isl_id
*array_id
= NULL
;
3310 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
3311 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
3312 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
3314 isl_space_free(dim
);
3317 isl_id_free(array_id
);
3321 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
3323 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
3324 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
3327 isl_id_free(array_id
);
3329 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
3330 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
3335 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3336 * in "dim" by a value equal to the corresponding parameter.
3338 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
3339 __isl_take isl_space
*dim
)
3346 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3348 expr_detect_parameter_accesses(expr
->args
[i
],
3349 isl_space_copy(dim
));
3354 if (expr
->type
== pet_expr_access
) {
3355 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
3356 isl_space_copy(dim
));
3357 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
3358 isl_space_copy(dim
));
3359 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3363 isl_space_free(dim
);
3366 isl_space_free(dim
);
3367 return pet_expr_free(expr
);
3370 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3371 * in "dim" by a value equal to the corresponding parameter.
3373 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
3374 __isl_take isl_space
*dim
)
3379 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
3380 isl_space_copy(dim
));
3382 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3385 isl_space_free(dim
);
3388 isl_space_free(dim
);
3389 return pet_stmt_free(stmt
);
3392 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3393 * in "dim" by a value equal to the corresponding parameter.
3395 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
3396 __isl_take isl_space
*dim
)
3403 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3404 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
3405 isl_space_copy(dim
));
3406 if (!scop
->stmts
[i
])
3410 isl_space_free(dim
);
3413 isl_space_free(dim
);
3414 return pet_scop_free(scop
);
3417 /* Replace all accesses to (0D) arrays that correspond to any of
3418 * the parameters used in "scop" by a value equal
3419 * to the corresponding parameter.
3421 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
3428 dim
= isl_set_get_space(scop
->context
);
3429 dim
= scop_collect_params(scop
, dim
);
3431 scop
= scop_detect_parameter_accesses(scop
, dim
);
3436 /* Return the relation mapping domain iterations to all possibly
3437 * accessed data elements.
3438 * In particular, take the access relation and project out the values
3439 * of the arguments, if any.
3441 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
3449 if (expr
->type
!= pet_expr_access
)
3452 access
= isl_map_copy(expr
->acc
.access
);
3453 if (expr
->n_arg
== 0)
3456 space
= isl_space_domain(isl_map_get_space(access
));
3457 map
= isl_map_universe(isl_space_unwrap(space
));
3458 map
= isl_map_domain_map(map
);
3459 access
= isl_map_apply_domain(access
, map
);
3464 /* Return the relation mapping domain iterations to all possibly
3465 * accessed data elements, with its domain tagged with the reference
3468 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
3469 struct pet_expr
*expr
)
3476 access
= pet_expr_access_get_may_access(expr
);
3477 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3482 /* Add the access relation of the access expression "expr" to "accesses" and
3483 * return the result.
3484 * The domain of the access relation is intersected with "domain".
3485 * If "tag" is set, then the access relation is tagged with
3486 * the corresponding reference identifier.
3488 static __isl_give isl_union_map
*expr_collect_access(struct pet_expr
*expr
,
3489 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3493 access
= pet_expr_access_get_may_access(expr
);
3494 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
3496 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3497 return isl_union_map_add_map(accesses
, access
);
3500 /* Add all read access relations (if "read" is set) and/or all write
3501 * access relations (if "write" is set) to "accesses" and return the result.
3502 * The domains of the access relations are intersected with "domain".
3503 * If "tag" is set, then the access relations are tagged with
3504 * the corresponding reference identifiers.
3506 * If "must" is set, then we only add the accesses that are definitely
3507 * performed. Otherwise, we add all potential accesses.
3508 * In particular, if the access has any arguments, then if "must" is
3509 * set we currently skip the access completely. If "must" is not set,
3510 * we project out the values of the access arguments.
3512 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
3513 int read
, int write
, int must
, int tag
,
3514 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3521 return isl_union_map_free(accesses
);
3523 for (i
= 0; i
< expr
->n_arg
; ++i
)
3524 accesses
= expr_collect_accesses(expr
->args
[i
],
3525 read
, write
, must
, tag
, accesses
, domain
);
3527 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
3528 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
3529 (!must
|| expr
->n_arg
== 0)) {
3530 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
3536 /* Collect and return all read access relations (if "read" is set)
3537 * and/or all write access relations (if "write" is set) in "stmt".
3538 * If "tag" is set, then the access relations are tagged with
3539 * the corresponding reference identifiers.
3540 * If "kill" is set, then "stmt" is a kill statement and we simply
3541 * add the argument of the kill operation.
3543 * If "must" is set, then we only add the accesses that are definitely
3544 * performed. Otherwise, we add all potential accesses.
3545 * In particular, if the statement has any arguments, then if "must" is
3546 * set we currently skip the statement completely. If "must" is not set,
3547 * we project out the values of the statement arguments.
3549 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
3550 int read
, int write
, int kill
, int must
, int tag
,
3551 __isl_take isl_space
*dim
)
3553 isl_union_map
*accesses
;
3559 accesses
= isl_union_map_empty(dim
);
3561 if (must
&& stmt
->n_arg
> 0)
3564 domain
= isl_set_copy(stmt
->domain
);
3565 if (isl_set_is_wrapping(domain
))
3566 domain
= isl_map_domain(isl_set_unwrap(domain
));
3569 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
3572 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
3573 must
, tag
, accesses
, domain
);
3574 isl_set_free(domain
);
3579 /* Is "stmt" a kill statement?
3581 static int is_kill(struct pet_stmt
*stmt
)
3583 if (stmt
->body
->type
!= pet_expr_unary
)
3585 return stmt
->body
->op
== pet_op_kill
;
3588 /* Is "stmt" an assume statement?
3590 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
3592 if (stmt
->body
->type
!= pet_expr_unary
)
3594 return stmt
->body
->op
== pet_op_assume
;
3597 /* Compute a mapping from all arrays (of structs) in scop
3598 * to their innermost arrays.
3600 * In particular, for each array of a primitive type, the result
3601 * contains the identity mapping on that array.
3602 * For each array involving member accesses, the result
3603 * contains a mapping from the elements of any intermediate array of structs
3604 * to all corresponding elements of the innermost nested arrays.
3606 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
3609 isl_union_map
*to_inner
;
3611 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3613 for (i
= 0; i
< scop
->n_array
; ++i
) {
3614 struct pet_array
*array
= scop
->arrays
[i
];
3616 isl_map
*map
, *gist
;
3618 if (array
->element_is_record
)
3621 map
= isl_set_identity(isl_set_copy(array
->extent
));
3623 set
= isl_map_domain(isl_map_copy(map
));
3624 gist
= isl_map_copy(map
);
3625 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3626 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3628 while (set
&& isl_set_is_wrapping(set
)) {
3632 id
= isl_set_get_tuple_id(set
);
3633 wrapped
= isl_set_unwrap(set
);
3634 wrapped
= isl_map_domain_map(wrapped
);
3635 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
3636 map
= isl_map_apply_domain(map
, wrapped
);
3637 set
= isl_map_domain(isl_map_copy(map
));
3638 gist
= isl_map_copy(map
);
3639 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3640 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3650 /* Collect and return all read access relations (if "read" is set)
3651 * and/or all write access relations (if "write" is set) in "scop".
3652 * If "kill" is set, then we only add the arguments of kill operations.
3653 * If "must" is set, then we only add the accesses that are definitely
3654 * performed. Otherwise, we add all potential accesses.
3655 * If "tag" is set, then the access relations are tagged with
3656 * the corresponding reference identifiers.
3657 * For accesses to structures, the returned access relation accesses
3658 * all individual fields in the structures.
3660 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3661 int read
, int write
, int kill
, int must
, int tag
)
3664 isl_union_map
*accesses
;
3665 isl_union_set
*arrays
;
3666 isl_union_map
*to_inner
;
3671 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3673 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3674 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3675 isl_union_map
*accesses_i
;
3678 if (kill
&& !is_kill(stmt
))
3681 space
= isl_set_get_space(scop
->context
);
3682 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
3684 accesses
= isl_union_map_union(accesses
, accesses_i
);
3687 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
3688 for (i
= 0; i
< scop
->n_array
; ++i
) {
3689 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
3690 arrays
= isl_union_set_add_set(arrays
, extent
);
3692 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
3694 to_inner
= compute_to_inner(scop
);
3695 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
3700 /* Collect all potential read access relations.
3702 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
3704 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
3707 /* Collect all potential write access relations.
3709 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
3711 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
3714 /* Collect all definite write access relations.
3716 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
3718 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
3721 /* Collect all definite kill access relations.
3723 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
3725 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
3728 /* Collect all tagged potential read access relations.
3730 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
3731 struct pet_scop
*scop
)
3733 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
3736 /* Collect all tagged potential write access relations.
3738 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
3739 struct pet_scop
*scop
)
3741 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
3744 /* Collect all tagged definite write access relations.
3746 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
3747 struct pet_scop
*scop
)
3749 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
3752 /* Collect all tagged definite kill access relations.
3754 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
3755 struct pet_scop
*scop
)
3757 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
3760 /* Collect and return the union of iteration domains in "scop".
3762 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3766 isl_union_set
*domain
;
3771 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3773 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3774 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3775 domain
= isl_union_set_add_set(domain
, domain_i
);
3781 /* Collect and return the schedules of the statements in "scop".
3782 * The range is normalized to the maximal number of scheduling
3785 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3788 isl_map
*schedule_i
;
3789 isl_union_map
*schedule
;
3790 int depth
, max_depth
= 0;
3795 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3797 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3798 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3799 if (depth
> max_depth
)
3803 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3804 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3805 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3806 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3808 for (j
= depth
; j
< max_depth
; ++j
)
3809 schedule_i
= isl_map_fix_si(schedule_i
,
3811 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3817 /* Does expression "expr" write to "id"?
3819 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3824 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3825 int writes
= expr_writes(expr
->args
[i
], id
);
3826 if (writes
< 0 || writes
)
3830 if (expr
->type
!= pet_expr_access
)
3832 if (!expr
->acc
.write
)
3834 if (pet_expr_is_affine(expr
))
3837 write_id
= pet_expr_access_get_id(expr
);
3838 isl_id_free(write_id
);
3843 return write_id
== id
;
3846 /* Does statement "stmt" write to "id"?
3848 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3850 return expr_writes(stmt
->body
, id
);
3853 /* Is there any write access in "scop" that accesses "id"?
3855 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3862 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3863 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3864 if (writes
< 0 || writes
)
3871 /* Add a reference identifier to access expression "expr".
3872 * "user" points to an integer that contains the sequence number
3873 * of the next reference.
3875 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3884 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3885 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3886 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3887 if (!expr
->acc
.ref_id
)
3888 return pet_expr_free(expr
);
3893 /* Add a reference identifier to all access expressions in "stmt".
3894 * "n_ref" points to an integer that contains the sequence number
3895 * of the next reference.
3897 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3904 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3905 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3906 &access_add_ref_id
, n_ref
);
3908 return pet_stmt_free(stmt
);
3911 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3913 return pet_stmt_free(stmt
);
3918 /* Add a reference identifier to all access expressions in "scop".
3920 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3929 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3930 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3931 if (!scop
->stmts
[i
])
3932 return pet_scop_free(scop
);
3938 /* Reset the user pointer on all parameter ids in "array".
3940 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3945 array
->context
= isl_set_reset_user(array
->context
);
3946 array
->extent
= isl_set_reset_user(array
->extent
);
3947 if (!array
->context
|| !array
->extent
)
3948 return pet_array_free(array
);
3953 /* Reset the user pointer on all parameter and tuple ids in
3954 * the access relation and the index expressions
3955 * of the access expression "expr".
3957 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3959 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
3960 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
3961 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3962 return pet_expr_free(expr
);
3967 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3969 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3978 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
3979 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
3980 if (!stmt
->domain
|| !stmt
->schedule
)
3981 return pet_stmt_free(stmt
);
3983 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3984 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3985 &access_anonymize
, NULL
);
3987 return pet_stmt_free(stmt
);
3990 stmt
->body
= pet_expr_map_access(stmt
->body
,
3991 &access_anonymize
, NULL
);
3993 return pet_stmt_free(stmt
);
3998 /* Reset the user pointer on the tuple ids and all parameter ids
4001 static struct pet_implication
*implication_anonymize(
4002 struct pet_implication
*implication
)
4007 implication
->extension
= isl_map_reset_user(implication
->extension
);
4008 if (!implication
->extension
)
4009 return pet_implication_free(implication
);
4014 /* Reset the user pointer on all parameter and tuple ids in "scop".
4016 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
4023 scop
->context
= isl_set_reset_user(scop
->context
);
4024 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
4025 if (!scop
->context
|| !scop
->context_value
)
4026 return pet_scop_free(scop
);
4028 for (i
= 0; i
< scop
->n_array
; ++i
) {
4029 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
4030 if (!scop
->arrays
[i
])
4031 return pet_scop_free(scop
);
4034 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4035 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
4036 if (!scop
->stmts
[i
])
4037 return pet_scop_free(scop
);
4040 for (i
= 0; i
< scop
->n_implication
; ++i
) {
4041 scop
->implications
[i
] =
4042 implication_anonymize(scop
->implications
[i
]);
4043 if (!scop
->implications
[i
])
4044 return pet_scop_free(scop
);
4050 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
4051 * then intersect the range of "map" with the valid set of values.
4053 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
4054 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
4059 isl_ctx
*ctx
= isl_map_get_ctx(map
);
4061 id
= pet_expr_access_get_id(arg
);
4062 space
= isl_space_alloc(ctx
, 0, 0, 1);
4063 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
4064 vb
= isl_union_map_extract_map(value_bounds
, space
);
4065 if (!isl_map_plain_is_empty(vb
))
4066 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
4073 /* Given a set "domain", return a wrapped relation with the given set
4074 * as domain and a range of dimension "n_arg", where each coordinate
4075 * is either unbounded or, if the corresponding element of args is of
4076 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
4078 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
4079 unsigned n_arg
, struct pet_expr
**args
,
4080 __isl_keep isl_union_map
*value_bounds
)
4086 map
= isl_map_from_domain(domain
);
4087 space
= isl_map_get_space(map
);
4088 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
4090 for (i
= 0; i
< n_arg
; ++i
) {
4092 struct pet_expr
*arg
= args
[i
];
4094 map_i
= isl_map_universe(isl_space_copy(space
));
4095 if (arg
->type
== pet_expr_access
)
4096 map_i
= access_apply_value_bounds(map_i
, arg
,
4098 map
= isl_map_flat_range_product(map
, map_i
);
4100 isl_space_free(space
);
4102 return isl_map_wrap(map
);
4105 /* Data used in access_gist() callback.
4107 struct pet_access_gist_data
{
4109 isl_union_map
*value_bounds
;
4112 /* Given an expression "expr" of type pet_expr_access, compute
4113 * the gist of the associated access relation and index expression
4114 * with respect to data->domain and the bounds on the values of the arguments
4115 * of the expression.
4117 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
4119 struct pet_access_gist_data
*data
= user
;
4122 domain
= isl_set_copy(data
->domain
);
4123 if (expr
->n_arg
> 0)
4124 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
4125 data
->value_bounds
);
4127 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
4128 isl_set_copy(domain
));
4129 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
4130 if (!expr
->acc
.access
|| !expr
->acc
.index
)
4131 return pet_expr_free(expr
);
4136 /* Compute the gist of the iteration domain and all access relations
4137 * of "stmt" based on the constraints on the parameters specified by "context"
4138 * and the constraints on the values of nested accesses specified
4139 * by "value_bounds".
4141 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
4142 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
4147 struct pet_access_gist_data data
;
4152 data
.domain
= isl_set_copy(stmt
->domain
);
4153 data
.value_bounds
= value_bounds
;
4154 if (stmt
->n_arg
> 0)
4155 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
4157 data
.domain
= isl_set_intersect_params(data
.domain
,
4158 isl_set_copy(context
));
4160 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
4161 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
4162 &access_gist
, &data
);
4167 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
4171 isl_set_free(data
.domain
);
4173 space
= isl_set_get_space(stmt
->domain
);
4174 if (isl_space_is_wrapping(space
))
4175 space
= isl_space_domain(isl_space_unwrap(space
));
4176 domain
= isl_set_universe(space
);
4177 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
4178 if (stmt
->n_arg
> 0)
4179 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
4181 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
4183 return pet_stmt_free(stmt
);
4187 isl_set_free(data
.domain
);
4188 return pet_stmt_free(stmt
);
4191 /* Compute the gist of the extent of the array
4192 * based on the constraints on the parameters specified by "context".
4194 static struct pet_array
*array_gist(struct pet_array
*array
,
4195 __isl_keep isl_set
*context
)
4200 array
->extent
= isl_set_gist_params(array
->extent
,
4201 isl_set_copy(context
));
4203 return pet_array_free(array
);
4208 /* Compute the gist of all sets and relations in "scop"
4209 * based on the constraints on the parameters specified by "scop->context"
4210 * and the constraints on the values of nested accesses specified
4211 * by "value_bounds".
4213 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
4214 __isl_keep isl_union_map
*value_bounds
)
4221 scop
->context
= isl_set_coalesce(scop
->context
);
4223 return pet_scop_free(scop
);
4225 for (i
= 0; i
< scop
->n_array
; ++i
) {
4226 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
4227 if (!scop
->arrays
[i
])
4228 return pet_scop_free(scop
);
4231 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4232 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
4234 if (!scop
->stmts
[i
])
4235 return pet_scop_free(scop
);
4241 /* Intersect the context of "scop" with "context".
4242 * To ensure that we don't introduce any unnamed parameters in
4243 * the context of "scop", we first remove the unnamed parameters
4246 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
4247 __isl_take isl_set
*context
)
4252 context
= set_project_out_unnamed_params(context
);
4253 scop
->context
= isl_set_intersect(scop
->context
, context
);
4255 return pet_scop_free(scop
);
4259 isl_set_free(context
);
4260 return pet_scop_free(scop
);
4263 /* Drop the current context of "scop". That is, replace the context
4264 * by a universal set.
4266 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
4273 space
= isl_set_get_space(scop
->context
);
4274 isl_set_free(scop
->context
);
4275 scop
->context
= isl_set_universe(space
);
4277 return pet_scop_free(scop
);
4282 /* Append "array" to the arrays of "scop".
4284 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
4285 struct pet_array
*array
)
4288 struct pet_array
**arrays
;
4290 if (!array
|| !scop
)
4293 ctx
= isl_set_get_ctx(scop
->context
);
4294 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
4298 scop
->arrays
= arrays
;
4299 scop
->arrays
[scop
->n_array
] = array
;
4304 pet_array_free(array
);
4305 return pet_scop_free(scop
);
4308 /* Create and return an implication on filter values equal to "satisfied"
4309 * with extension "map".
4311 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
4315 struct pet_implication
*implication
;
4319 ctx
= isl_map_get_ctx(map
);
4320 implication
= isl_alloc_type(ctx
, struct pet_implication
);
4324 implication
->extension
= map
;
4325 implication
->satisfied
= satisfied
;
4333 /* Add an implication on filter values equal to "satisfied"
4334 * with extension "map" to "scop".
4336 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
4337 __isl_take isl_map
*map
, int satisfied
)
4340 struct pet_implication
*implication
;
4341 struct pet_implication
**implications
;
4343 implication
= new_implication(map
, satisfied
);
4344 if (!scop
|| !implication
)
4347 ctx
= isl_set_get_ctx(scop
->context
);
4348 implications
= isl_realloc_array(ctx
, scop
->implications
,
4349 struct pet_implication
*,
4350 scop
->n_implication
+ 1);
4353 scop
->implications
= implications
;
4354 scop
->implications
[scop
->n_implication
] = implication
;
4355 scop
->n_implication
++;
4359 pet_implication_free(implication
);
4360 return pet_scop_free(scop
);
4363 /* Given an access expression, check if it is data dependent.
4364 * If so, set *found and abort the search.
4366 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
4378 /* Does "scop" contain any data dependent accesses?
4380 * Check the body of each statement for such accesses.
4382 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
4390 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4391 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
4392 &is_data_dependent
, &found
);
4393 if (r
< 0 && !found
)
4402 /* Does "scop" contain and data dependent conditions?
4404 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
4411 for (i
= 0; i
< scop
->n_stmt
; ++i
)
4412 if (scop
->stmts
[i
]->n_arg
> 0)
4418 /* Keep track of the "input" file inside the (extended) "scop".
4420 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
4422 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4432 /* Print the original code corresponding to "scop" to printer "p".
4434 * pet_scop_print_original can only be called from
4435 * a pet_transform_C_source callback. This means that the input
4436 * file is stored in the extended scop and that the printer prints
4439 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
4440 __isl_take isl_printer
*p
)
4442 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4446 return isl_printer_free(p
);
4449 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
4450 "no input file stored in scop",
4451 return isl_printer_free(p
));
4453 output
= isl_printer_get_file(p
);
4455 return isl_printer_free(p
);
4457 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
4458 return isl_printer_free(p
);