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
] = "=",
70 [pet_op_post_inc
] = "++",
71 [pet_op_post_dec
] = "--",
72 [pet_op_pre_inc
] = "++",
73 [pet_op_pre_dec
] = "--",
74 [pet_op_address_of
] = "&",
75 [pet_op_kill
] = "kill"
78 /* pet_scop with extra information that is used during parsing and printing.
80 * In particular, we keep track of conditions under which we want
81 * to skip the rest of the current loop iteration (skip[pet_skip_now])
82 * and of conditions under which we want to skip subsequent
83 * loop iterations (skip[pet_skip_later]).
85 * The conditions are represented as index expressions defined
86 * over a zero-dimensiona domain. The index expression is either
87 * a boolean affine expression or an access to a variable, which
88 * is assumed to attain values zero and one. The condition holds
89 * if the variable has value one or if the affine expression
90 * has value one (typically for only part of the parameter space).
92 * A missing condition (skip[type] == NULL) means that we don't want
95 * Additionally, we keep track of the original input file
96 * inside pet_transform_C_source.
101 isl_multi_pw_aff
*skip
[2];
105 const char *pet_op_str(enum pet_op_type op
)
110 int pet_op_is_inc_dec(enum pet_op_type op
)
112 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
113 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
116 const char *pet_type_str(enum pet_expr_type type
)
118 return type_str
[type
];
121 enum pet_op_type
pet_str_op(const char *str
)
125 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
126 if (!strcmp(op_str
[i
], str
))
132 enum pet_expr_type
pet_str_type(const char *str
)
136 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
137 if (!strcmp(type_str
[i
], str
))
143 /* Construct an access pet_expr from an access relation and an index expression.
144 * By default, it is considered to be a read access.
146 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
147 __isl_take isl_multi_pw_aff
*index
)
149 isl_ctx
*ctx
= isl_map_get_ctx(access
);
150 struct pet_expr
*expr
;
152 if (!index
|| !access
)
154 expr
= isl_calloc_type(ctx
, struct pet_expr
);
158 expr
->type
= pet_expr_access
;
159 expr
->acc
.access
= access
;
160 expr
->acc
.index
= index
;
166 isl_map_free(access
);
167 isl_multi_pw_aff_free(index
);
171 /* Construct an access pet_expr from an index expression.
172 * By default, the access is considered to be a read access.
174 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
178 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
179 return pet_expr_from_access_and_index(access
, index
);
182 /* Extend the range of "access" with "n" dimensions, retaining
183 * the tuple identifier on this range.
185 * If "access" represents a member access, then extend the range
188 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
192 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
194 if (!isl_map_range_is_wrapping(access
)) {
195 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
199 domain
= isl_map_copy(access
);
200 domain
= isl_map_range_factor_domain(domain
);
201 access
= isl_map_range_factor_range(access
);
202 access
= extend_range(access
, n
);
203 access
= isl_map_range_product(domain
, access
);
206 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
211 /* Construct an access pet_expr from an index expression and
212 * the depth of the accessed array.
213 * By default, the access is considered to be a read access.
215 * If the number of indices is smaller than the depth of the array,
216 * then we assume that all elements of the remaining dimensions
219 struct pet_expr
*pet_expr_from_index_and_depth(
220 __isl_take isl_multi_pw_aff
*index
, int depth
)
225 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
228 dim
= isl_map_dim(access
, isl_dim_out
);
230 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
231 "number of indices greater than depth",
232 access
= isl_map_free(access
));
234 return pet_expr_from_access_and_index(access
, index
);
236 access
= extend_range(access
, depth
- dim
);
238 return pet_expr_from_access_and_index(access
, index
);
240 isl_multi_pw_aff_free(index
);
244 /* Construct a pet_expr that kills the elements specified by
245 * the index expression "index" and the access relation "access".
247 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
248 __isl_take isl_multi_pw_aff
*index
)
251 struct pet_expr
*expr
;
253 if (!access
|| !index
)
256 ctx
= isl_multi_pw_aff_get_ctx(index
);
257 expr
= pet_expr_from_access_and_index(access
, index
);
261 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
263 isl_map_free(access
);
264 isl_multi_pw_aff_free(index
);
268 /* Construct a unary pet_expr that performs "op" on "arg".
270 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
271 struct pet_expr
*arg
)
273 struct pet_expr
*expr
;
277 expr
= isl_alloc_type(ctx
, struct pet_expr
);
281 expr
->type
= pet_expr_unary
;
284 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
287 expr
->args
[pet_un_arg
] = arg
;
295 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
297 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
298 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
300 struct pet_expr
*expr
;
304 expr
= isl_alloc_type(ctx
, struct pet_expr
);
308 expr
->type
= pet_expr_binary
;
311 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
314 expr
->args
[pet_bin_lhs
] = lhs
;
315 expr
->args
[pet_bin_rhs
] = rhs
;
324 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
326 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
327 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
329 struct pet_expr
*expr
;
331 if (!cond
|| !lhs
|| !rhs
)
333 expr
= isl_alloc_type(ctx
, struct pet_expr
);
337 expr
->type
= pet_expr_ternary
;
339 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
342 expr
->args
[pet_ter_cond
] = cond
;
343 expr
->args
[pet_ter_true
] = lhs
;
344 expr
->args
[pet_ter_false
] = rhs
;
354 /* Construct a call pet_expr that calls function "name" with "n_arg"
355 * arguments. The caller is responsible for filling in the arguments.
357 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
360 struct pet_expr
*expr
;
362 expr
= isl_alloc_type(ctx
, struct pet_expr
);
366 expr
->type
= pet_expr_call
;
368 expr
->name
= strdup(name
);
369 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
370 if (!expr
->name
|| !expr
->args
)
371 return pet_expr_free(expr
);
376 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
378 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
379 struct pet_expr
*arg
)
381 struct pet_expr
*expr
;
386 expr
= isl_alloc_type(ctx
, struct pet_expr
);
390 expr
->type
= pet_expr_cast
;
392 expr
->type_name
= strdup(type_name
);
393 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
394 if (!expr
->type_name
|| !expr
->args
)
406 /* Construct a pet_expr that represents the double "d".
408 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
410 struct pet_expr
*expr
;
412 expr
= isl_calloc_type(ctx
, struct pet_expr
);
416 expr
->type
= pet_expr_double
;
418 expr
->d
.s
= strdup(s
);
420 return pet_expr_free(expr
);
425 struct pet_expr
*pet_expr_free(struct pet_expr
*expr
)
432 for (i
= 0; i
< expr
->n_arg
; ++i
)
433 pet_expr_free(expr
->args
[i
]);
436 switch (expr
->type
) {
437 case pet_expr_access
:
438 isl_id_free(expr
->acc
.ref_id
);
439 isl_map_free(expr
->acc
.access
);
440 isl_multi_pw_aff_free(expr
->acc
.index
);
446 free(expr
->type_name
);
448 case pet_expr_double
:
452 case pet_expr_binary
:
453 case pet_expr_ternary
:
461 static void expr_dump(struct pet_expr
*expr
, int indent
)
468 fprintf(stderr
, "%*s", indent
, "");
470 switch (expr
->type
) {
471 case pet_expr_double
:
472 fprintf(stderr
, "%s\n", expr
->d
.s
);
474 case pet_expr_access
:
475 isl_id_dump(expr
->acc
.ref_id
);
476 fprintf(stderr
, "%*s", indent
, "");
477 isl_map_dump(expr
->acc
.access
);
478 fprintf(stderr
, "%*s", indent
, "");
479 isl_multi_pw_aff_dump(expr
->acc
.index
);
480 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
482 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
483 "", expr
->acc
.write
);
484 for (i
= 0; i
< expr
->n_arg
; ++i
)
485 expr_dump(expr
->args
[i
], indent
+ 2);
488 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
489 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
491 case pet_expr_binary
:
492 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
493 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
494 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
496 case pet_expr_ternary
:
497 fprintf(stderr
, "?:\n");
498 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
499 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
500 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
503 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
504 for (i
= 0; i
< expr
->n_arg
; ++i
)
505 expr_dump(expr
->args
[i
], indent
+ 2);
508 fprintf(stderr
, "(%s)\n", expr
->type_name
);
509 for (i
= 0; i
< expr
->n_arg
; ++i
)
510 expr_dump(expr
->args
[i
], indent
+ 2);
515 void pet_expr_dump(struct pet_expr
*expr
)
520 /* Does "expr" represent an access to an unnamed space, i.e.,
521 * does it represent an affine expression?
523 int pet_expr_is_affine(struct pet_expr
*expr
)
529 if (expr
->type
!= pet_expr_access
)
532 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
539 /* Return the identifier of the array accessed by "expr".
541 * If "expr" represents a member access, then return the identifier
542 * of the outer structure array.
544 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
548 if (expr
->type
!= pet_expr_access
)
551 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
555 space
= isl_map_get_space(expr
->acc
.access
);
556 space
= isl_space_range(space
);
557 while (space
&& isl_space_is_wrapping(space
))
558 space
= isl_space_domain(isl_space_unwrap(space
));
559 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
560 isl_space_free(space
);
565 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
568 /* Align the parameters of expr->acc.index and expr->acc.access.
570 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
574 if (expr
->type
!= pet_expr_access
)
575 return pet_expr_free(expr
);
577 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
578 isl_multi_pw_aff_get_space(expr
->acc
.index
));
579 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
580 isl_map_get_space(expr
->acc
.access
));
581 if (!expr
->acc
.access
|| !expr
->acc
.index
)
582 return pet_expr_free(expr
);
587 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
589 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
593 if (expr
->type
!= pet_expr_access
)
596 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
599 /* Return 1 if the two pet_exprs are equivalent.
601 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
605 if (!expr1
|| !expr2
)
608 if (expr1
->type
!= expr2
->type
)
610 if (expr1
->n_arg
!= expr2
->n_arg
)
612 for (i
= 0; i
< expr1
->n_arg
; ++i
)
613 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
615 switch (expr1
->type
) {
616 case pet_expr_double
:
617 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
619 if (expr1
->d
.val
!= expr2
->d
.val
)
622 case pet_expr_access
:
623 if (expr1
->acc
.read
!= expr2
->acc
.read
)
625 if (expr1
->acc
.write
!= expr2
->acc
.write
)
627 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
629 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
631 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
633 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
635 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
640 case pet_expr_binary
:
641 case pet_expr_ternary
:
642 if (expr1
->op
!= expr2
->op
)
646 if (strcmp(expr1
->name
, expr2
->name
))
650 if (strcmp(expr1
->type_name
, expr2
->type_name
))
658 /* Add extra conditions on the parameters to all access relations in "expr".
660 * The conditions are not added to the index expression. Instead, they
661 * are used to try and simplifty the index expression.
663 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
664 __isl_take isl_set
*cond
)
671 for (i
= 0; i
< expr
->n_arg
; ++i
) {
672 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
678 if (expr
->type
== pet_expr_access
) {
679 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
681 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
682 expr
->acc
.index
, isl_set_copy(cond
));
683 if (!expr
->acc
.access
|| !expr
->acc
.index
)
691 return pet_expr_free(expr
);
694 /* Tag the access relation "access" with "id".
695 * That is, insert the id as the range of a wrapped relation
696 * in the domain of "access".
698 * If "access" is of the form
702 * then the result is of the form
704 * [D[i] -> id[]] -> A[a]
706 static __isl_give isl_map
*tag_access(__isl_take isl_map
*access
,
707 __isl_take isl_id
*id
)
712 space
= isl_space_range(isl_map_get_space(access
));
713 space
= isl_space_from_range(space
);
714 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
715 add_tag
= isl_map_universe(space
);
716 access
= isl_map_domain_product(access
, add_tag
);
721 /* Modify all expressions of type pet_expr_access in "expr"
722 * by calling "fn" on them.
724 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
725 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
733 for (i
= 0; i
< expr
->n_arg
; ++i
) {
734 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
736 return pet_expr_free(expr
);
739 if (expr
->type
== pet_expr_access
)
740 expr
= fn(expr
, user
);
745 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
747 * Return -1 on error (where fn return a negative value is treated as an error).
748 * Otherwise return 0.
750 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
751 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
758 for (i
= 0; i
< expr
->n_arg
; ++i
)
759 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
762 if (expr
->type
== pet_expr_access
)
763 return fn(expr
, user
);
768 /* Modify the access relation and index expression
769 * of the given access expression
770 * based on the given iteration space transformation.
771 * In particular, precompose the access relation and index expression
772 * with the update function.
774 * If the access has any arguments then the domain of the access relation
775 * is a wrapped mapping from the iteration space to the space of
776 * argument values. We only need to change the domain of this wrapped
777 * mapping, so we extend the input transformation with an identity mapping
778 * on the space of argument values.
780 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
782 isl_multi_pw_aff
*update
= user
;
785 update
= isl_multi_pw_aff_copy(update
);
787 space
= isl_map_get_space(expr
->acc
.access
);
788 space
= isl_space_domain(space
);
789 if (!isl_space_is_wrapping(space
))
790 isl_space_free(space
);
792 isl_multi_pw_aff
*id
;
793 space
= isl_space_unwrap(space
);
794 space
= isl_space_range(space
);
795 space
= isl_space_map_from_set(space
);
796 id
= isl_multi_pw_aff_identity(space
);
797 update
= isl_multi_pw_aff_product(update
, id
);
800 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
802 isl_multi_pw_aff_copy(update
));
803 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
804 expr
->acc
.index
, update
);
805 if (!expr
->acc
.access
|| !expr
->acc
.index
)
806 return pet_expr_free(expr
);
811 /* Modify all access relations in "expr" by precomposing them with
812 * the given iteration space transformation.
814 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
815 __isl_take isl_multi_pw_aff
*update
)
817 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
818 isl_multi_pw_aff_free(update
);
822 /* Construct a pet_stmt with given line number and statement
823 * number from a pet_expr.
824 * The initial iteration domain is the zero-dimensional universe.
825 * The name of the domain is given by "label" if it is non-NULL.
826 * Otherwise, the name is constructed as S_<id>.
827 * The domains of all access relations are modified to refer
828 * to the statement iteration domain.
830 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
831 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
833 struct pet_stmt
*stmt
;
837 isl_multi_pw_aff
*add_name
;
843 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
847 dim
= isl_space_set_alloc(ctx
, 0, 0);
849 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
851 snprintf(name
, sizeof(name
), "S_%d", id
);
852 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
854 dom
= isl_set_universe(isl_space_copy(dim
));
855 sched
= isl_map_from_domain(isl_set_copy(dom
));
857 dim
= isl_space_from_domain(dim
);
858 add_name
= isl_multi_pw_aff_zero(dim
);
859 expr
= expr_update_domain(expr
, add_name
);
863 stmt
->schedule
= sched
;
866 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
867 return pet_stmt_free(stmt
);
876 void *pet_stmt_free(struct pet_stmt
*stmt
)
883 isl_set_free(stmt
->domain
);
884 isl_map_free(stmt
->schedule
);
885 pet_expr_free(stmt
->body
);
887 for (i
= 0; i
< stmt
->n_arg
; ++i
)
888 pet_expr_free(stmt
->args
[i
]);
895 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
902 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
903 fprintf(stderr
, "%*s", indent
, "");
904 isl_set_dump(stmt
->domain
);
905 fprintf(stderr
, "%*s", indent
, "");
906 isl_map_dump(stmt
->schedule
);
907 expr_dump(stmt
->body
, indent
);
908 for (i
= 0; i
< stmt
->n_arg
; ++i
)
909 expr_dump(stmt
->args
[i
], indent
+ 2);
912 void pet_stmt_dump(struct pet_stmt
*stmt
)
917 /* Allocate a new pet_type with the given "name" and "definition".
919 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
920 const char *definition
)
922 struct pet_type
*type
;
924 type
= isl_alloc_type(ctx
, struct pet_type
);
928 type
->name
= strdup(name
);
929 type
->definition
= strdup(definition
);
931 if (!type
->name
|| !type
->definition
)
932 return pet_type_free(type
);
937 /* Free "type" and return NULL.
939 struct pet_type
*pet_type_free(struct pet_type
*type
)
945 free(type
->definition
);
951 struct pet_array
*pet_array_free(struct pet_array
*array
)
956 isl_set_free(array
->context
);
957 isl_set_free(array
->extent
);
958 isl_set_free(array
->value_bounds
);
959 free(array
->element_type
);
965 void pet_array_dump(struct pet_array
*array
)
970 isl_set_dump(array
->context
);
971 isl_set_dump(array
->extent
);
972 isl_set_dump(array
->value_bounds
);
973 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
974 array
->element_is_record
? " element-is-record" : "",
975 array
->live_out
? " live-out" : "");
978 /* Alloc a pet_scop structure, with extra room for information that
979 * is only used during parsing.
981 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
983 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
986 /* Construct a pet_scop with room for n statements.
988 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
991 struct pet_scop
*scop
;
993 scop
= pet_scop_alloc(ctx
);
997 space
= isl_space_params_alloc(ctx
, 0);
998 scop
->context
= isl_set_universe(isl_space_copy(space
));
999 scop
->context_value
= isl_set_universe(space
);
1000 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
1001 if (!scop
->context
|| !scop
->stmts
)
1002 return pet_scop_free(scop
);
1009 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
1011 return scop_alloc(ctx
, 0);
1014 /* Update "context" with respect to the valid parameter values for "access".
1016 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
1017 __isl_take isl_set
*context
)
1019 context
= isl_set_intersect(context
,
1020 isl_map_params(isl_map_copy(access
)));
1024 /* Update "context" with respect to the valid parameter values for "expr".
1026 * If "expr" represents a ternary operator, then a parameter value
1027 * needs to be valid for the condition and for at least one of the
1028 * remaining two arguments.
1029 * If the condition is an affine expression, then we can be a bit more specific.
1030 * The parameter then has to be valid for the second argument for
1031 * non-zero accesses and valid for the third argument for zero accesses.
1033 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
1034 __isl_take isl_set
*context
)
1038 if (expr
->type
== pet_expr_ternary
) {
1040 isl_set
*context1
, *context2
;
1042 is_aff
= pet_expr_is_affine(expr
->args
[0]);
1046 context
= expr_extract_context(expr
->args
[0], context
);
1047 context1
= expr_extract_context(expr
->args
[1],
1048 isl_set_copy(context
));
1049 context2
= expr_extract_context(expr
->args
[2], context
);
1055 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
1056 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
1057 zero_set
= isl_map_params(access
);
1058 context1
= isl_set_subtract(context1
,
1059 isl_set_copy(zero_set
));
1060 context2
= isl_set_intersect(context2
, zero_set
);
1063 context
= isl_set_union(context1
, context2
);
1064 context
= isl_set_coalesce(context
);
1069 for (i
= 0; i
< expr
->n_arg
; ++i
)
1070 context
= expr_extract_context(expr
->args
[i
], context
);
1072 if (expr
->type
== pet_expr_access
)
1073 context
= access_extract_context(expr
->acc
.access
, context
);
1077 isl_set_free(context
);
1081 /* Update "context" with respect to the valid parameter values for "stmt".
1083 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
1084 __isl_take isl_set
*context
)
1088 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1089 context
= expr_extract_context(stmt
->args
[i
], context
);
1091 context
= expr_extract_context(stmt
->body
, context
);
1096 /* Construct a pet_scop that contains the given pet_stmt.
1098 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
1100 struct pet_scop
*scop
;
1105 scop
= scop_alloc(ctx
, 1);
1109 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
1113 scop
->stmts
[0] = stmt
;
1117 pet_stmt_free(stmt
);
1118 pet_scop_free(scop
);
1122 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1123 * does it represent an affine expression?
1125 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
1129 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
1136 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1138 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
1139 __isl_take isl_set
*dom
)
1142 pa
= isl_set_indicator_function(set
);
1143 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1147 /* Return "lhs || rhs", defined on the shared definition domain.
1149 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1150 __isl_take isl_pw_aff
*rhs
)
1155 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1156 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1157 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1158 isl_pw_aff_non_zero_set(rhs
));
1159 cond
= isl_set_coalesce(cond
);
1160 return indicator_function(cond
, dom
);
1163 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1164 * ext may be equal to either ext1 or ext2.
1166 * The two skips that need to be combined are assumed to be affine expressions.
1168 * We need to skip in ext if we need to skip in either ext1 or ext2.
1169 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1171 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1172 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1175 isl_pw_aff
*skip
, *skip1
, *skip2
;
1179 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1181 if (!ext1
->skip
[type
]) {
1184 ext
->skip
[type
] = ext2
->skip
[type
];
1185 ext2
->skip
[type
] = NULL
;
1188 if (!ext2
->skip
[type
]) {
1191 ext
->skip
[type
] = ext1
->skip
[type
];
1192 ext1
->skip
[type
] = NULL
;
1196 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1197 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1198 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1199 isl_error_internal
, "can only combine affine skips",
1202 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1203 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1204 skip
= pw_aff_or(skip1
, skip2
);
1205 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1206 ext1
->skip
[type
] = NULL
;
1207 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1208 ext2
->skip
[type
] = NULL
;
1209 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1210 if (!ext
->skip
[type
])
1215 pet_scop_free(&ext
->scop
);
1219 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1220 * where type takes on the values pet_skip_now and pet_skip_later.
1221 * scop may be equal to either scop1 or scop2.
1223 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1224 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1226 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1227 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1228 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1230 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1231 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1235 /* Update scop->start and scop->end to include the region from "start"
1236 * to "end". In particular, if scop->end == 0, then "scop" does not
1237 * have any offset information yet and we simply take the information
1238 * from "start" and "end". Otherwise, we update the fields if the
1239 * region from "start" to "end" is not already included.
1241 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1242 unsigned start
, unsigned end
)
1246 if (scop
->end
== 0) {
1247 scop
->start
= start
;
1250 if (start
< scop
->start
)
1251 scop
->start
= start
;
1252 if (end
> scop
->end
)
1259 /* Does "implication" appear in the list of implications of "scop"?
1261 static int is_known_implication(struct pet_scop
*scop
,
1262 struct pet_implication
*implication
)
1266 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1267 struct pet_implication
*pi
= scop
->implications
[i
];
1270 if (pi
->satisfied
!= implication
->satisfied
)
1272 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1282 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1283 * in "scop", removing duplicates (i.e., implications in "scop2" that
1284 * already appear in "scop1").
1286 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1287 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1294 if (scop2
->n_implication
== 0) {
1295 scop
->n_implication
= scop1
->n_implication
;
1296 scop
->implications
= scop1
->implications
;
1297 scop1
->n_implication
= 0;
1298 scop1
->implications
= NULL
;
1302 if (scop1
->n_implication
== 0) {
1303 scop
->n_implication
= scop2
->n_implication
;
1304 scop
->implications
= scop2
->implications
;
1305 scop2
->n_implication
= 0;
1306 scop2
->implications
= NULL
;
1310 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1311 scop1
->n_implication
+ scop2
->n_implication
);
1312 if (!scop
->implications
)
1313 return pet_scop_free(scop
);
1315 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1316 scop
->implications
[i
] = scop1
->implications
[i
];
1317 scop1
->implications
[i
] = NULL
;
1320 scop
->n_implication
= scop1
->n_implication
;
1321 j
= scop1
->n_implication
;
1322 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1325 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1327 return pet_scop_free(scop
);
1330 scop
->implications
[j
++] = scop2
->implications
[i
];
1331 scop2
->implications
[i
] = NULL
;
1333 scop
->n_implication
= j
;
1338 /* Combine the offset information of "scop1" and "scop2" into "scop".
1340 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1341 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1344 scop
= pet_scop_update_start_end(scop
,
1345 scop1
->start
, scop1
->end
);
1347 scop
= pet_scop_update_start_end(scop
,
1348 scop2
->start
, scop2
->end
);
1352 /* Construct a pet_scop that contains the offset information,
1353 * arrays, statements and skip information in "scop1" and "scop2".
1355 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1356 struct pet_scop
*scop2
)
1359 struct pet_scop
*scop
= NULL
;
1361 if (!scop1
|| !scop2
)
1364 if (scop1
->n_stmt
== 0) {
1365 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1366 pet_scop_free(scop1
);
1370 if (scop2
->n_stmt
== 0) {
1371 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1372 pet_scop_free(scop2
);
1376 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1380 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1381 scop1
->n_array
+ scop2
->n_array
);
1384 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1386 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1387 scop
->stmts
[i
] = scop1
->stmts
[i
];
1388 scop1
->stmts
[i
] = NULL
;
1391 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1392 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1393 scop2
->stmts
[i
] = NULL
;
1396 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1397 scop
->arrays
[i
] = scop1
->arrays
[i
];
1398 scop1
->arrays
[i
] = NULL
;
1401 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1402 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1403 scop2
->arrays
[i
] = NULL
;
1406 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1407 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1408 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1409 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1410 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1412 pet_scop_free(scop1
);
1413 pet_scop_free(scop2
);
1416 pet_scop_free(scop1
);
1417 pet_scop_free(scop2
);
1418 pet_scop_free(scop
);
1422 /* Apply the skip condition "skip" to "scop".
1423 * That is, make sure "scop" is not executed when the condition holds.
1425 * If "skip" is an affine expression, we add the conditions under
1426 * which the expression is zero to the iteration domains.
1427 * Otherwise, we add a filter on the variable attaining the value zero.
1429 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1430 __isl_take isl_multi_pw_aff
*skip
)
1439 is_aff
= multi_pw_aff_is_affine(skip
);
1444 return pet_scop_filter(scop
, skip
, 0);
1446 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1447 isl_multi_pw_aff_free(skip
);
1448 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1449 scop
= pet_scop_restrict(scop
, zero
);
1453 isl_multi_pw_aff_free(skip
);
1454 return pet_scop_free(scop
);
1457 /* Construct a pet_scop that contains the arrays, statements and
1458 * skip information in "scop1" and "scop2", where the two scops
1459 * are executed "in sequence". That is, breaks and continues
1460 * in scop1 have an effect on scop2.
1462 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1463 struct pet_scop
*scop2
)
1465 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1466 scop2
= restrict_skip(scop2
,
1467 pet_scop_get_skip(scop1
, pet_skip_now
));
1468 return pet_scop_add(ctx
, scop1
, scop2
);
1471 /* Construct a pet_scop that contains the arrays, statements and
1472 * skip information in "scop1" and "scop2", where the two scops
1473 * are executed "in parallel". That is, any break or continue
1474 * in scop1 has no effect on scop2.
1476 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1477 struct pet_scop
*scop2
)
1479 return pet_scop_add(ctx
, scop1
, scop2
);
1482 void *pet_implication_free(struct pet_implication
*implication
)
1489 isl_map_free(implication
->extension
);
1495 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1498 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1502 isl_set_free(scop
->context
);
1503 isl_set_free(scop
->context_value
);
1505 for (i
= 0; i
< scop
->n_type
; ++i
)
1506 pet_type_free(scop
->types
[i
]);
1509 for (i
= 0; i
< scop
->n_array
; ++i
)
1510 pet_array_free(scop
->arrays
[i
]);
1513 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1514 pet_stmt_free(scop
->stmts
[i
]);
1516 if (scop
->implications
)
1517 for (i
= 0; i
< scop
->n_implication
; ++i
)
1518 pet_implication_free(scop
->implications
[i
]);
1519 free(scop
->implications
);
1520 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1521 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1526 void pet_type_dump(struct pet_type
*type
)
1531 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1534 void pet_implication_dump(struct pet_implication
*implication
)
1539 fprintf(stderr
, "%d\n", implication
->satisfied
);
1540 isl_map_dump(implication
->extension
);
1543 void pet_scop_dump(struct pet_scop
*scop
)
1546 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1551 isl_set_dump(scop
->context
);
1552 isl_set_dump(scop
->context_value
);
1553 for (i
= 0; i
< scop
->n_type
; ++i
)
1554 pet_type_dump(scop
->types
[i
]);
1555 for (i
= 0; i
< scop
->n_array
; ++i
)
1556 pet_array_dump(scop
->arrays
[i
]);
1557 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1558 pet_stmt_dump(scop
->stmts
[i
]);
1559 for (i
= 0; i
< scop
->n_implication
; ++i
)
1560 pet_implication_dump(scop
->implications
[i
]);
1563 fprintf(stderr
, "skip\n");
1564 isl_multi_pw_aff_dump(ext
->skip
[0]);
1565 isl_multi_pw_aff_dump(ext
->skip
[1]);
1569 /* Return 1 if the two pet_arrays are equivalent.
1571 * We don't compare element_size as this may be target dependent.
1573 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1575 if (!array1
|| !array2
)
1578 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1580 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1582 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1584 if (array1
->value_bounds
&&
1585 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1587 if (strcmp(array1
->element_type
, array2
->element_type
))
1589 if (array1
->element_is_record
!= array2
->element_is_record
)
1591 if (array1
->live_out
!= array2
->live_out
)
1593 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1595 if (array1
->declared
!= array2
->declared
)
1597 if (array1
->exposed
!= array2
->exposed
)
1603 /* Return 1 if the two pet_stmts are equivalent.
1605 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1609 if (!stmt1
|| !stmt2
)
1612 if (stmt1
->line
!= stmt2
->line
)
1614 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1616 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1618 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1620 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1622 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1623 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1630 /* Return 1 if the two pet_types are equivalent.
1632 * We only compare the names of the types since the exact representation
1633 * of the definition may depend on the version of clang being used.
1635 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1637 if (!type1
|| !type2
)
1640 if (strcmp(type1
->name
, type2
->name
))
1646 /* Return 1 if the two pet_implications are equivalent.
1648 int pet_implication_is_equal(struct pet_implication
*implication1
,
1649 struct pet_implication
*implication2
)
1651 if (!implication1
|| !implication2
)
1654 if (implication1
->satisfied
!= implication2
->satisfied
)
1656 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1662 /* Return 1 if the two pet_scops are equivalent.
1664 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1668 if (!scop1
|| !scop2
)
1671 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1673 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1676 if (scop1
->n_type
!= scop2
->n_type
)
1678 for (i
= 0; i
< scop1
->n_type
; ++i
)
1679 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1682 if (scop1
->n_array
!= scop2
->n_array
)
1684 for (i
= 0; i
< scop1
->n_array
; ++i
)
1685 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1688 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1690 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1691 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1694 if (scop1
->n_implication
!= scop2
->n_implication
)
1696 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1697 if (!pet_implication_is_equal(scop1
->implications
[i
],
1698 scop2
->implications
[i
]))
1704 /* Prefix the schedule of "stmt" with an extra dimension with constant
1707 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1712 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1713 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1714 if (!stmt
->schedule
)
1715 return pet_stmt_free(stmt
);
1720 /* Prefix the schedules of all statements in "scop" with an extra
1721 * dimension with constant value "pos".
1723 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1730 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1731 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1732 if (!scop
->stmts
[i
])
1733 return pet_scop_free(scop
);
1739 /* Given a set with a parameter at "param_pos" that refers to the
1740 * iterator, "move" the iterator to the first set dimension.
1741 * That is, essentially equate the parameter to the first set dimension
1742 * and then project it out.
1744 * The first set dimension may however refer to a virtual iterator,
1745 * while the parameter refers to the "real" iterator.
1746 * We therefore need to take into account the affine expression "iv_map", which
1747 * expresses the real iterator in terms of the virtual iterator.
1748 * In particular, we equate the set dimension to the input of the map
1749 * and the parameter to the output of the map and then project out
1750 * everything we don't need anymore.
1752 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1753 int param_pos
, __isl_take isl_aff
*iv_map
)
1755 isl_map
*map
, *map2
;
1756 map
= isl_map_from_domain(set
);
1757 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1758 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1759 map2
= isl_map_from_aff(iv_map
);
1760 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1761 map
= isl_map_apply_range(map
, map2
);
1762 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1763 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1764 return isl_map_domain(map
);
1767 /* Data used in embed_access.
1768 * extend adds an iterator to the iteration domain (through precomposition).
1769 * iv_map expresses the real iterator in terms of the virtual iterator
1770 * var_id represents the induction variable of the corresponding loop
1772 struct pet_embed_access
{
1773 isl_multi_pw_aff
*extend
;
1778 /* Given an index expression, return an expression for the outer iterator.
1780 static __isl_give isl_aff
*index_outer_iterator(
1781 __isl_take isl_multi_pw_aff
*index
)
1784 isl_local_space
*ls
;
1786 space
= isl_multi_pw_aff_get_domain_space(index
);
1787 isl_multi_pw_aff_free(index
);
1789 ls
= isl_local_space_from_space(space
);
1790 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1793 /* Replace an index expression that references the new (outer) iterator variable
1794 * by one that references the corresponding (real) iterator.
1796 * The input index expression is of the form
1798 * { S[i',...] -> i[] }
1800 * where i' refers to the virtual iterator.
1802 * iv_map is of the form
1806 * Return the index expression
1808 * { S[i',...] -> [i] }
1810 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1811 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1816 aff
= index_outer_iterator(index
);
1817 space
= isl_aff_get_space(aff
);
1818 iv_map
= isl_aff_align_params(iv_map
, space
);
1819 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1821 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1824 /* Given an index expression "index" that refers to the (real) iterator
1825 * through the parameter at position "pos", plug in "iv_map", expressing
1826 * the real iterator in terms of the virtual (outer) iterator.
1828 * In particular, the index expression is of the form
1830 * [..., i, ...] -> { S[i',...] -> ... i ... }
1832 * where i refers to the real iterator and i' refers to the virtual iterator.
1834 * iv_map is of the form
1838 * Return the index expression
1840 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1843 * We first move the parameter to the input
1845 * [..., ...] -> { [i, i',...] -> ... i ... }
1849 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1851 * and then combine the two to obtain the desired result.
1853 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1854 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1856 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1859 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1860 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1861 isl_dim_param
, pos
, 1);
1863 space
= isl_space_map_from_set(space
);
1864 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1865 iv_map
= isl_aff_align_params(iv_map
, space
);
1866 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1867 ma
= isl_multi_aff_flat_range_product(
1868 isl_multi_aff_from_aff(iv_map
), ma
);
1869 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1874 /* Does the index expression "index" reference a virtual array, i.e.,
1875 * one with user pointer equal to NULL?
1876 * A virtual array does not have any members.
1878 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1883 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1885 if (isl_multi_pw_aff_range_is_wrapping(index
))
1887 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1888 is_virtual
= !isl_id_get_user(id
);
1894 /* Does the access relation "access" reference a virtual array, i.e.,
1895 * one with user pointer equal to NULL?
1896 * A virtual array does not have any members.
1898 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1903 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1905 if (isl_map_range_is_wrapping(access
))
1907 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1908 is_virtual
= !isl_id_get_user(id
);
1914 /* Embed the given index expression in an extra outer loop.
1915 * The domain of the index expression has already been updated.
1917 * If the access refers to the induction variable, then it is
1918 * turned into an access to the set of integers with index (and value)
1919 * equal to the induction variable.
1921 * If the accessed array is a virtual array (with user
1922 * pointer equal to NULL), as created by create_test_index,
1923 * then it is extended along with the domain of the index expression.
1925 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1926 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1928 isl_id
*array_id
= NULL
;
1931 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1932 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1933 if (array_id
== data
->var_id
) {
1934 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1935 } else if (index_is_virtual_array(index
)) {
1937 isl_multi_pw_aff
*mpa
;
1939 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1940 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1941 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1942 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1943 isl_id_copy(array_id
));
1945 isl_id_free(array_id
);
1947 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1948 isl_dim_param
, data
->var_id
);
1950 index
= index_internalize_iv(index
, pos
,
1951 isl_aff_copy(data
->iv_map
));
1952 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1953 isl_id_copy(data
->var_id
));
1958 /* Embed the given access relation in an extra outer loop.
1959 * The domain of the access relation has already been updated.
1961 * If the access refers to the induction variable, then it is
1962 * turned into an access to the set of integers with index (and value)
1963 * equal to the induction variable.
1965 * If the induction variable appears in the constraints (as a parameter),
1966 * then the parameter is equated to the newly introduced iteration
1967 * domain dimension and subsequently projected out.
1969 * Similarly, if the accessed array is a virtual array (with user
1970 * pointer equal to NULL), as created by create_test_index,
1971 * then it is extended along with the domain of the access.
1973 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1974 struct pet_embed_access
*data
)
1976 isl_id
*array_id
= NULL
;
1979 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1980 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1981 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
1982 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1983 access
= isl_map_equate(access
,
1984 isl_dim_in
, 0, isl_dim_out
, 0);
1985 if (array_id
== data
->var_id
)
1986 access
= isl_map_apply_range(access
,
1987 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1989 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1990 isl_id_copy(array_id
));
1992 isl_id_free(array_id
);
1994 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1996 isl_set
*set
= isl_map_wrap(access
);
1997 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1998 access
= isl_set_unwrap(set
);
2000 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
2001 isl_id_copy(data
->var_id
));
2006 /* Given an access expression, embed the associated access relation and
2007 * index expression in an extra outer loop.
2009 * We first update the domains to insert the extra dimension and
2010 * then update the access relation and index expression to take
2011 * into account the mapping "iv_map" from virtual iterator
2014 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
2017 struct pet_embed_access
*data
= user
;
2019 expr
= update_domain(expr
, data
->extend
);
2023 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
2024 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
2025 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2026 return pet_expr_free(expr
);
2031 /* Embed all access subexpressions of "expr" in an extra loop.
2032 * "extend" inserts an outer loop iterator in the iteration domains
2033 * (through precomposition).
2034 * "iv_map" expresses the real iterator in terms of the virtual iterator
2035 * "var_id" represents the induction variable.
2037 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
2038 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
2039 __isl_keep isl_id
*var_id
)
2041 struct pet_embed_access data
=
2042 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
2044 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
2045 isl_aff_free(iv_map
);
2046 isl_multi_pw_aff_free(extend
);
2050 /* Embed the given pet_stmt in an extra outer loop with iteration domain
2051 * "dom" and schedule "sched". "var_id" represents the induction variable
2052 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
2053 * That is, it expresses the iterator that some of the parameters in "stmt"
2054 * may refer to in terms of the iterator used in "dom" and
2055 * the domain of "sched".
2057 * The iteration domain and schedule of the statement are updated
2058 * according to the iteration domain and schedule of the new loop.
2059 * If stmt->domain is a wrapped map, then the iteration domain
2060 * is the domain of this map, so we need to be careful to adjust
2063 * If the induction variable appears in the constraints (as a parameter)
2064 * of the current iteration domain or the schedule of the statement,
2065 * then the parameter is equated to the newly introduced iteration
2066 * domain dimension and subsequently projected out.
2068 * Finally, all access relations are updated based on the extra loop.
2070 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
2071 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
2072 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
2078 isl_multi_pw_aff
*extend
;
2083 if (isl_set_is_wrapping(stmt
->domain
)) {
2088 map
= isl_set_unwrap(stmt
->domain
);
2089 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
2090 ran_dim
= isl_space_range(isl_map_get_space(map
));
2091 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
2092 isl_set_universe(ran_dim
));
2093 map
= isl_map_flat_domain_product(ext
, map
);
2094 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
2095 isl_id_copy(stmt_id
));
2096 dim
= isl_space_domain(isl_map_get_space(map
));
2097 stmt
->domain
= isl_map_wrap(map
);
2099 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
2100 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
2102 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
2103 isl_id_copy(stmt_id
));
2104 dim
= isl_set_get_space(stmt
->domain
);
2107 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
2109 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
2110 isl_aff_copy(iv_map
));
2112 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
2113 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
2114 isl_dim_in
, stmt_id
);
2116 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
2118 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
2119 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
2120 stmt
->schedule
= isl_set_unwrap(set
);
2123 dim
= isl_space_map_from_set(dim
);
2124 extend
= isl_multi_pw_aff_identity(dim
);
2125 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
2126 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
2127 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
2128 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2129 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
2130 isl_multi_pw_aff_copy(extend
),
2131 isl_aff_copy(iv_map
), var_id
);
2132 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
2135 isl_id_free(var_id
);
2137 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2139 return pet_stmt_free(stmt
);
2140 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2141 return pet_stmt_free(stmt
);
2145 isl_map_free(sched
);
2146 isl_aff_free(iv_map
);
2147 isl_id_free(var_id
);
2151 /* Embed the given pet_array in an extra outer loop with iteration domain
2153 * This embedding only has an effect on virtual arrays (those with
2154 * user pointer equal to NULL), which need to be extended along with
2155 * the iteration domain.
2157 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
2158 __isl_take isl_set
*dom
)
2160 isl_id
*array_id
= NULL
;
2165 if (isl_set_has_tuple_id(array
->extent
))
2166 array_id
= isl_set_get_tuple_id(array
->extent
);
2168 if (array_id
&& !isl_id_get_user(array_id
)) {
2169 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
2170 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
2172 return pet_array_free(array
);
2175 isl_id_free(array_id
);
2184 /* Project out all unnamed parameters from "set" and return the result.
2186 static __isl_give isl_set
*set_project_out_unnamed_params(
2187 __isl_take isl_set
*set
)
2191 n
= isl_set_dim(set
, isl_dim_param
);
2192 for (i
= n
- 1; i
>= 0; --i
) {
2193 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
2195 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
2201 /* Update the context with respect to an embedding into a loop
2202 * with iteration domain "dom" and induction variable "id".
2203 * "iv_map" expresses the real iterator (parameter "id") in terms
2204 * of a possibly virtual iterator (used in "dom").
2206 * If the current context is independent of "id", we don't need
2208 * Otherwise, a parameter value is invalid for the embedding if
2209 * any of the corresponding iterator values is invalid.
2210 * That is, a parameter value is valid only if all the corresponding
2211 * iterator values are valid.
2212 * We therefore compute the set of parameters
2214 * forall i in dom : valid (i)
2218 * not exists i in dom : not valid(i)
2222 * not exists i in dom \ valid(i)
2224 * Before we subtract valid(i) from dom, we first need to substitute
2225 * the real iterator for the virtual iterator.
2227 * If there are any unnamed parameters in "dom", then we consider
2228 * a parameter value to be valid if it is valid for any value of those
2229 * unnamed parameters. They are therefore projected out at the end.
2231 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
2232 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
2233 __isl_keep isl_id
*id
)
2238 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
2242 context
= isl_set_from_params(context
);
2243 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
2244 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
2245 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
2246 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
2247 context
= isl_set_preimage_multi_aff(context
, ma
);
2248 context
= isl_set_subtract(isl_set_copy(dom
), context
);
2249 context
= isl_set_params(context
);
2250 context
= isl_set_complement(context
);
2251 context
= set_project_out_unnamed_params(context
);
2255 /* Update the implication with respect to an embedding into a loop
2256 * with iteration domain "dom".
2258 * Since embed_access extends virtual arrays along with the domain
2259 * of the access, we need to do the same with domain and range
2260 * of the implication. Since the original implication is only valid
2261 * within a given iteration of the loop, the extended implication
2262 * maps the extra array dimension corresponding to the extra loop
2265 static struct pet_implication
*pet_implication_embed(
2266 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
2274 map
= isl_set_identity(dom
);
2275 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
2276 map
= isl_map_flat_product(map
, implication
->extension
);
2277 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
2278 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
2279 implication
->extension
= map
;
2280 if (!implication
->extension
)
2281 return pet_implication_free(implication
);
2289 /* Embed all statements and arrays in "scop" in an extra outer loop
2290 * with iteration domain "dom" and schedule "sched".
2291 * "id" represents the induction variable of the loop.
2292 * "iv_map" maps a possibly virtual iterator to the real iterator.
2293 * That is, it expresses the iterator that some of the parameters in "scop"
2294 * may refer to in terms of the iterator used in "dom" and
2295 * the domain of "sched".
2297 * Any skip conditions within the loop have no effect outside of the loop.
2298 * The caller is responsible for making sure skip[pet_skip_later] has been
2299 * taken into account.
2301 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
2302 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
2303 __isl_take isl_id
*id
)
2310 pet_scop_reset_skip(scop
, pet_skip_now
);
2311 pet_scop_reset_skip(scop
, pet_skip_later
);
2313 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
2317 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2318 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
2319 isl_set_copy(dom
), isl_map_copy(sched
),
2320 isl_aff_copy(iv_map
), isl_id_copy(id
));
2321 if (!scop
->stmts
[i
])
2325 for (i
= 0; i
< scop
->n_array
; ++i
) {
2326 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
2328 if (!scop
->arrays
[i
])
2332 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2333 scop
->implications
[i
] =
2334 pet_implication_embed(scop
->implications
[i
],
2336 if (!scop
->implications
[i
])
2341 isl_map_free(sched
);
2342 isl_aff_free(iv_map
);
2347 isl_map_free(sched
);
2348 isl_aff_free(iv_map
);
2350 return pet_scop_free(scop
);
2353 /* Add extra conditions on the parameters to iteration domain of "stmt".
2355 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
2356 __isl_take isl_set
*cond
)
2361 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
2366 return pet_stmt_free(stmt
);
2369 /* Add extra conditions to scop->skip[type].
2371 * The new skip condition only holds if it held before
2372 * and the condition is true. It does not hold if it did not hold
2373 * before or the condition is false.
2375 * The skip condition is assumed to be an affine expression.
2377 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
2378 enum pet_skip type
, __isl_keep isl_set
*cond
)
2380 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2386 if (!ext
->skip
[type
])
2389 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2390 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2391 isl_error_internal
, "can only resrict affine skips",
2392 return pet_scop_free(scop
));
2394 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2395 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2396 cond
= isl_set_copy(cond
);
2397 cond
= isl_set_from_params(cond
);
2398 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2399 skip
= indicator_function(cond
, dom
);
2400 isl_multi_pw_aff_free(ext
->skip
[type
]);
2401 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2402 if (!ext
->skip
[type
])
2403 return pet_scop_free(scop
);
2408 /* Add extra conditions on the parameters to all iteration domains
2409 * and skip conditions.
2411 * A parameter value is valid for the result if it was valid
2412 * for the original scop and satisfies "cond" or if it does
2413 * not satisfy "cond" as in this case the scop is not executed
2414 * and the original constraints on the parameters are irrelevant.
2416 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2417 __isl_take isl_set
*cond
)
2421 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2422 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2427 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2428 scop
->context
= isl_set_union(scop
->context
,
2429 isl_set_complement(isl_set_copy(cond
)));
2430 scop
->context
= isl_set_coalesce(scop
->context
);
2431 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2435 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2436 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2437 isl_set_copy(cond
));
2438 if (!scop
->stmts
[i
])
2446 return pet_scop_free(scop
);
2449 /* Construct a function that (upon precomposition) inserts
2450 * a filter value with name "id" and value "satisfied"
2451 * in the list of filter values embedded in the set space "space".
2453 * If "space" does not contain any filter values yet, we first create
2454 * a function that inserts 0 filter values, i.e.,
2456 * [space -> []] -> space
2458 * We can now assume that space is of the form [dom -> [filters]]
2459 * We construct an identity mapping on dom and a mapping on filters
2460 * that (upon precomposition) inserts the new filter
2463 * [satisfied, filters] -> [filters]
2465 * and then compute the cross product
2467 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2469 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2470 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2474 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2477 if (isl_space_is_wrapping(space
)) {
2478 space2
= isl_space_map_from_set(isl_space_copy(space
));
2479 ma
= isl_multi_aff_identity(space2
);
2480 space
= isl_space_unwrap(space
);
2482 space
= isl_space_from_domain(space
);
2483 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2486 space2
= isl_space_domain(isl_space_copy(space
));
2487 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2488 space
= isl_space_range(space
);
2489 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2490 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2491 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2492 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2493 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2495 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2496 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2501 /* Insert an argument expression corresponding to "test" in front
2502 * of the list of arguments described by *n_arg and *args.
2504 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2505 __isl_keep isl_multi_pw_aff
*test
)
2508 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
2514 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2518 struct pet_expr
**ext
;
2519 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2522 for (i
= 0; i
< *n_arg
; ++i
)
2523 ext
[1 + i
] = (*args
)[i
];
2528 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2535 /* Make the expression "expr" depend on the value of "test"
2536 * being equal to "satisfied".
2538 * If "test" is an affine expression, we simply add the conditions
2539 * on the expression having the value "satisfied" to all access relations
2540 * and index expressions.
2542 * Otherwise, we add a filter to "expr" (which is then assumed to be
2543 * an access expression) corresponding to "test" being equal to "satisfied".
2545 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2546 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2551 isl_pw_multi_aff
*pma
;
2556 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2560 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2561 isl_multi_pw_aff_free(test
);
2563 cond
= isl_pw_aff_non_zero_set(pa
);
2565 cond
= isl_pw_aff_zero_set(pa
);
2566 return pet_expr_restrict(expr
, isl_set_params(cond
));
2569 ctx
= isl_multi_pw_aff_get_ctx(test
);
2570 if (expr
->type
!= pet_expr_access
)
2571 isl_die(ctx
, isl_error_invalid
,
2572 "can only filter access expressions", goto error
);
2574 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2575 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2576 pma
= insert_filter_pma(space
, id
, satisfied
);
2578 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2580 isl_pw_multi_aff_copy(pma
));
2581 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2582 expr
->acc
.index
, pma
);
2583 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2586 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2589 isl_multi_pw_aff_free(test
);
2592 isl_multi_pw_aff_free(test
);
2593 return pet_expr_free(expr
);
2596 /* Look through the applications in "scop" for any that can be
2597 * applied to the filter expressed by "map" and "satisified".
2598 * If there is any, then apply it to "map" and return the result.
2599 * Otherwise, return "map".
2600 * "id" is the identifier of the virtual array.
2602 * We only introduce at most one implication for any given virtual array,
2603 * so we can apply the implication and return as soon as we find one.
2605 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2606 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2610 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2611 struct pet_implication
*pi
= scop
->implications
[i
];
2614 if (pi
->satisfied
!= satisfied
)
2616 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2621 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2627 /* Is the filter expressed by "test" and "satisfied" implied
2628 * by filter "pos" on "domain", with filter "expr", taking into
2629 * account the implications of "scop"?
2631 * For filter on domain implying that expressed by "test" and "satisfied",
2632 * the filter needs to be an access to the same (virtual) array as "test" and
2633 * the filter value needs to be equal to "satisfied".
2634 * Moreover, the filter access relation, possibly extended by
2635 * the implications in "scop" needs to contain "test".
2637 static int implies_filter(struct pet_scop
*scop
,
2638 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2639 __isl_keep isl_map
*test
, int satisfied
)
2641 isl_id
*test_id
, *arg_id
;
2648 if (expr
->type
!= pet_expr_access
)
2650 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2651 arg_id
= pet_expr_access_get_id(expr
);
2652 isl_id_free(arg_id
);
2653 isl_id_free(test_id
);
2654 if (test_id
!= arg_id
)
2656 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2657 is_int
= isl_val_is_int(val
);
2659 s
= isl_val_get_num_si(val
);
2668 implied
= isl_map_copy(expr
->acc
.access
);
2669 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2670 is_subset
= isl_map_is_subset(test
, implied
);
2671 isl_map_free(implied
);
2676 /* Is the filter expressed by "test" and "satisfied" implied
2677 * by any of the filters on the domain of "stmt", taking into
2678 * account the implications of "scop"?
2680 static int filter_implied(struct pet_scop
*scop
,
2681 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2689 if (!scop
|| !stmt
|| !test
)
2691 if (scop
->n_implication
== 0)
2693 if (stmt
->n_arg
== 0)
2696 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2697 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2700 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2701 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2702 test_map
, satisfied
);
2703 if (implied
< 0 || implied
)
2707 isl_map_free(test_map
);
2708 isl_map_free(domain
);
2712 /* Make the statement "stmt" depend on the value of "test"
2713 * being equal to "satisfied" by adjusting stmt->domain.
2715 * The domain of "test" corresponds to the (zero or more) outer dimensions
2716 * of the iteration domain.
2718 * We first extend "test" to apply to the entire iteration domain and
2719 * then check if the filter that we are about to add is implied
2720 * by any of the current filters, possibly taking into account
2721 * the implications in "scop". If so, we leave "stmt" untouched and return.
2723 * Otherwise, we insert an argument corresponding to a read to "test"
2724 * from the iteration domain of "stmt" in front of the list of arguments.
2725 * We also insert a corresponding output dimension in the wrapped
2726 * map contained in stmt->domain, with value set to "satisfied".
2728 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2729 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2735 isl_pw_multi_aff
*pma
;
2736 isl_multi_aff
*add_dom
;
2738 isl_local_space
*ls
;
2744 space
= isl_set_get_space(stmt
->domain
);
2745 if (isl_space_is_wrapping(space
))
2746 space
= isl_space_domain(isl_space_unwrap(space
));
2747 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2748 space
= isl_space_from_domain(space
);
2749 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2750 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2751 ls
= isl_local_space_from_space(isl_space_domain(space
));
2752 for (i
= 0; i
< n_test_dom
; ++i
) {
2754 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2756 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2758 isl_local_space_free(ls
);
2759 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2761 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2765 isl_multi_pw_aff_free(test
);
2769 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2770 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2771 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2773 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2776 isl_multi_pw_aff_free(test
);
2779 isl_multi_pw_aff_free(test
);
2780 return pet_stmt_free(stmt
);
2783 /* Does "scop" have a skip condition of the given "type"?
2785 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2787 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2791 return ext
->skip
[type
] != NULL
;
2794 /* Does "scop" have a skip condition of the given "type" that
2795 * is an affine expression?
2797 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2799 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2803 if (!ext
->skip
[type
])
2805 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2808 /* Does "scop" have a skip condition of the given "type" that
2809 * is not an affine expression?
2811 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2813 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2818 if (!ext
->skip
[type
])
2820 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2826 /* Does "scop" have a skip condition of the given "type" that
2827 * is affine and holds on the entire domain?
2829 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2831 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2837 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2838 if (is_aff
< 0 || !is_aff
)
2841 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2842 set
= isl_pw_aff_non_zero_set(pa
);
2843 is_univ
= isl_set_plain_is_universe(set
);
2849 /* Replace scop->skip[type] by "skip".
2851 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2852 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2854 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2859 isl_multi_pw_aff_free(ext
->skip
[type
]);
2860 ext
->skip
[type
] = skip
;
2864 isl_multi_pw_aff_free(skip
);
2865 return pet_scop_free(scop
);
2868 /* Return a copy of scop->skip[type].
2870 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2873 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2878 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2881 /* Assuming scop->skip[type] is an affine expression,
2882 * return the constraints on the parameters for which the skip condition
2885 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2888 isl_multi_pw_aff
*skip
;
2891 skip
= pet_scop_get_skip(scop
, type
);
2892 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2893 isl_multi_pw_aff_free(skip
);
2894 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2897 /* Return the identifier of the variable that is accessed by
2898 * the skip condition of the given type.
2900 * The skip condition is assumed not to be an affine condition.
2902 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2905 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2910 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2913 /* Return an access pet_expr corresponding to the skip condition
2914 * of the given type.
2916 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2919 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2922 /* Drop the the skip condition scop->skip[type].
2924 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2926 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2931 isl_multi_pw_aff_free(ext
->skip
[type
]);
2932 ext
->skip
[type
] = NULL
;
2935 /* Make the skip condition (if any) depend on the value of "test" being
2936 * equal to "satisfied".
2938 * We only support the case where the original skip condition is universal,
2939 * i.e., where skipping is unconditional, and where satisfied == 1.
2940 * In this case, the skip condition is changed to skip only when
2941 * "test" is equal to one.
2943 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2944 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2950 if (!pet_scop_has_skip(scop
, type
))
2954 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2956 return pet_scop_free(scop
);
2957 if (satisfied
&& is_univ
) {
2958 isl_space
*space
= isl_multi_pw_aff_get_space(test
);
2959 isl_multi_pw_aff
*skip
;
2960 skip
= isl_multi_pw_aff_zero(space
);
2961 scop
= pet_scop_set_skip(scop
, type
, skip
);
2965 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2966 "skip expression cannot be filtered",
2967 return pet_scop_free(scop
));
2973 /* Make all statements in "scop" depend on the value of "test"
2974 * being equal to "satisfied" by adjusting their domains.
2976 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2977 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2981 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2982 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2987 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2988 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2989 isl_multi_pw_aff_copy(test
), satisfied
);
2990 if (!scop
->stmts
[i
])
2994 isl_multi_pw_aff_free(test
);
2997 isl_multi_pw_aff_free(test
);
2998 return pet_scop_free(scop
);
3001 /* Add all parameters in "expr" to "dim" and return the result.
3003 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
3004 __isl_take isl_space
*dim
)
3010 for (i
= 0; i
< expr
->n_arg
; ++i
)
3012 dim
= expr_collect_params(expr
->args
[i
], dim
);
3014 if (expr
->type
== pet_expr_access
)
3015 dim
= isl_space_align_params(dim
,
3016 isl_map_get_space(expr
->acc
.access
));
3020 pet_expr_free(expr
);
3021 return isl_space_free(dim
);
3024 /* Add all parameters in "stmt" to "dim" and return the result.
3026 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
3027 __isl_take isl_space
*dim
)
3032 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
3033 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
3034 dim
= expr_collect_params(stmt
->body
, dim
);
3038 isl_space_free(dim
);
3039 return pet_stmt_free(stmt
);
3042 /* Add all parameters in "array" to "dim" and return the result.
3044 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
3045 __isl_take isl_space
*dim
)
3050 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
3051 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
3055 pet_array_free(array
);
3056 return isl_space_free(dim
);
3059 /* Add all parameters in "scop" to "dim" and return the result.
3061 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
3062 __isl_take isl_space
*dim
)
3069 for (i
= 0; i
< scop
->n_array
; ++i
)
3070 dim
= array_collect_params(scop
->arrays
[i
], dim
);
3072 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3073 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
3077 isl_space_free(dim
);
3078 pet_scop_free(scop
);
3082 /* Add all parameters in "dim" to all access relations and index expressions
3085 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
3086 __isl_take isl_space
*dim
)
3093 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3095 expr_propagate_params(expr
->args
[i
],
3096 isl_space_copy(dim
));
3101 if (expr
->type
== pet_expr_access
) {
3102 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
3103 isl_space_copy(dim
));
3104 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
3105 isl_space_copy(dim
));
3106 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3110 isl_space_free(dim
);
3113 isl_space_free(dim
);
3114 return pet_expr_free(expr
);
3117 /* Add all parameters in "dim" to the domain, schedule and
3118 * all access relations in "stmt".
3120 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
3121 __isl_take isl_space
*dim
)
3126 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
3127 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
3128 isl_space_copy(dim
));
3129 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
3131 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3134 isl_space_free(dim
);
3137 isl_space_free(dim
);
3138 return pet_stmt_free(stmt
);
3141 /* Add all parameters in "dim" to "array".
3143 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
3144 __isl_take isl_space
*dim
)
3149 array
->context
= isl_set_align_params(array
->context
,
3150 isl_space_copy(dim
));
3151 array
->extent
= isl_set_align_params(array
->extent
,
3152 isl_space_copy(dim
));
3153 if (array
->value_bounds
) {
3154 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
3155 isl_space_copy(dim
));
3156 if (!array
->value_bounds
)
3160 if (!array
->context
|| !array
->extent
)
3163 isl_space_free(dim
);
3166 isl_space_free(dim
);
3167 return pet_array_free(array
);
3170 /* Add all parameters in "dim" to "scop".
3172 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
3173 __isl_take isl_space
*dim
)
3180 for (i
= 0; i
< scop
->n_array
; ++i
) {
3181 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
3182 isl_space_copy(dim
));
3183 if (!scop
->arrays
[i
])
3187 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3188 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
3189 isl_space_copy(dim
));
3190 if (!scop
->stmts
[i
])
3194 isl_space_free(dim
);
3197 isl_space_free(dim
);
3198 return pet_scop_free(scop
);
3201 /* Update all isl_sets and isl_maps in "scop" such that they all
3202 * have the same parameters.
3204 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
3211 dim
= isl_set_get_space(scop
->context
);
3212 dim
= scop_collect_params(scop
, dim
);
3214 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
3215 scop
= scop_propagate_params(scop
, dim
);
3220 /* Check if the given index expression accesses a (0D) array that corresponds
3221 * to one of the parameters in "dim". If so, replace the array access
3222 * by an access to the set of integers with as index (and value)
3225 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
3226 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
3228 isl_local_space
*ls
;
3229 isl_id
*array_id
= NULL
;
3233 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
3234 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
3235 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3237 isl_space_free(space
);
3240 isl_id_free(array_id
);
3244 space
= isl_multi_pw_aff_get_domain_space(index
);
3245 isl_multi_pw_aff_free(index
);
3247 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3249 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
3250 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
3253 isl_id_free(array_id
);
3255 ls
= isl_local_space_from_space(space
);
3256 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
3257 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
3262 /* Check if the given access relation accesses a (0D) array that corresponds
3263 * to one of the parameters in "dim". If so, replace the array access
3264 * by an access to the set of integers with as index (and value)
3267 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
3268 __isl_take isl_space
*dim
)
3270 isl_id
*array_id
= NULL
;
3273 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
3274 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
3275 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
3277 isl_space_free(dim
);
3280 isl_id_free(array_id
);
3284 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
3286 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
3287 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
3290 isl_id_free(array_id
);
3292 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
3293 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
3298 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3299 * in "dim" by a value equal to the corresponding parameter.
3301 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
3302 __isl_take isl_space
*dim
)
3309 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3311 expr_detect_parameter_accesses(expr
->args
[i
],
3312 isl_space_copy(dim
));
3317 if (expr
->type
== pet_expr_access
) {
3318 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
3319 isl_space_copy(dim
));
3320 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
3321 isl_space_copy(dim
));
3322 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3326 isl_space_free(dim
);
3329 isl_space_free(dim
);
3330 return pet_expr_free(expr
);
3333 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3334 * in "dim" by a value equal to the corresponding parameter.
3336 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
3337 __isl_take isl_space
*dim
)
3342 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
3343 isl_space_copy(dim
));
3345 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3348 isl_space_free(dim
);
3351 isl_space_free(dim
);
3352 return pet_stmt_free(stmt
);
3355 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3356 * in "dim" by a value equal to the corresponding parameter.
3358 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
3359 __isl_take isl_space
*dim
)
3366 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3367 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
3368 isl_space_copy(dim
));
3369 if (!scop
->stmts
[i
])
3373 isl_space_free(dim
);
3376 isl_space_free(dim
);
3377 return pet_scop_free(scop
);
3380 /* Replace all accesses to (0D) arrays that correspond to any of
3381 * the parameters used in "scop" by a value equal
3382 * to the corresponding parameter.
3384 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
3391 dim
= isl_set_get_space(scop
->context
);
3392 dim
= scop_collect_params(scop
, dim
);
3394 scop
= scop_detect_parameter_accesses(scop
, dim
);
3399 /* Return the relation mapping domain iterations to all possibly
3400 * accessed data elements.
3401 * In particular, take the access relation and project out the values
3402 * of the arguments, if any.
3404 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
3412 if (expr
->type
!= pet_expr_access
)
3415 access
= isl_map_copy(expr
->acc
.access
);
3416 if (expr
->n_arg
== 0)
3419 space
= isl_space_domain(isl_map_get_space(access
));
3420 map
= isl_map_universe(isl_space_unwrap(space
));
3421 map
= isl_map_domain_map(map
);
3422 access
= isl_map_apply_domain(access
, map
);
3427 /* Return the relation mapping domain iterations to all possibly
3428 * accessed data elements, with its domain tagged with the reference
3431 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
3432 struct pet_expr
*expr
)
3439 access
= pet_expr_access_get_may_access(expr
);
3440 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3445 /* Add the access relation of the access expression "expr" to "accesses" and
3446 * return the result.
3447 * The domain of the access relation is intersected with "domain".
3448 * If "tag" is set, then the access relation is tagged with
3449 * the corresponding reference identifier.
3451 static __isl_give isl_union_map
*expr_collect_access(struct pet_expr
*expr
,
3452 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3456 access
= pet_expr_access_get_may_access(expr
);
3457 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
3459 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3460 return isl_union_map_add_map(accesses
, access
);
3463 /* Add all read access relations (if "read" is set) and/or all write
3464 * access relations (if "write" is set) to "accesses" and return the result.
3465 * The domains of the access relations are intersected with "domain".
3466 * If "tag" is set, then the access relations are tagged with
3467 * the corresponding reference identifiers.
3469 * If "must" is set, then we only add the accesses that are definitely
3470 * performed. Otherwise, we add all potential accesses.
3471 * In particular, if the access has any arguments, then if "must" is
3472 * set we currently skip the access completely. If "must" is not set,
3473 * we project out the values of the access arguments.
3475 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
3476 int read
, int write
, int must
, int tag
,
3477 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3484 return isl_union_map_free(accesses
);
3486 for (i
= 0; i
< expr
->n_arg
; ++i
)
3487 accesses
= expr_collect_accesses(expr
->args
[i
],
3488 read
, write
, must
, tag
, accesses
, domain
);
3490 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
3491 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
3492 (!must
|| expr
->n_arg
== 0)) {
3493 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
3499 /* Collect and return all read access relations (if "read" is set)
3500 * and/or all write access relations (if "write" is set) in "stmt".
3501 * If "tag" is set, then the access relations are tagged with
3502 * the corresponding reference identifiers.
3503 * If "kill" is set, then "stmt" is a kill statement and we simply
3504 * add the argument of the kill operation.
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 statement has any arguments, then if "must" is
3509 * set we currently skip the statement completely. If "must" is not set,
3510 * we project out the values of the statement arguments.
3512 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
3513 int read
, int write
, int kill
, int must
, int tag
,
3514 __isl_take isl_space
*dim
)
3516 isl_union_map
*accesses
;
3522 accesses
= isl_union_map_empty(dim
);
3524 if (must
&& stmt
->n_arg
> 0)
3527 domain
= isl_set_copy(stmt
->domain
);
3528 if (isl_set_is_wrapping(domain
))
3529 domain
= isl_map_domain(isl_set_unwrap(domain
));
3532 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
3535 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
3536 must
, tag
, accesses
, domain
);
3537 isl_set_free(domain
);
3542 /* Is "stmt" a kill statement?
3544 static int is_kill(struct pet_stmt
*stmt
)
3546 if (stmt
->body
->type
!= pet_expr_unary
)
3548 return stmt
->body
->op
== pet_op_kill
;
3551 /* Compute a mapping from all arrays (of structs) in scop
3552 * to their innermost arrays.
3554 * In particular, for each array of a primitive type, the result
3555 * contains the identity mapping on that array.
3556 * For each array involving member accesses, the result
3557 * contains a mapping from the elements of any intermediate array of structs
3558 * to all corresponding elements of the innermost nested arrays.
3560 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
3563 isl_union_map
*to_inner
;
3565 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3567 for (i
= 0; i
< scop
->n_array
; ++i
) {
3568 struct pet_array
*array
= scop
->arrays
[i
];
3570 isl_map
*map
, *gist
;
3572 if (array
->element_is_record
)
3575 map
= isl_set_identity(isl_set_copy(array
->extent
));
3577 set
= isl_map_domain(isl_map_copy(map
));
3578 gist
= isl_map_copy(map
);
3579 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3580 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3582 while (set
&& isl_set_is_wrapping(set
)) {
3586 id
= isl_set_get_tuple_id(set
);
3587 wrapped
= isl_set_unwrap(set
);
3588 wrapped
= isl_map_domain_map(wrapped
);
3589 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
3590 map
= isl_map_apply_domain(map
, wrapped
);
3591 set
= isl_map_domain(isl_map_copy(map
));
3592 gist
= isl_map_copy(map
);
3593 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3594 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3604 /* Collect and return all read access relations (if "read" is set)
3605 * and/or all write access relations (if "write" is set) in "scop".
3606 * If "kill" is set, then we only add the arguments of kill operations.
3607 * If "must" is set, then we only add the accesses that are definitely
3608 * performed. Otherwise, we add all potential accesses.
3609 * If "tag" is set, then the access relations are tagged with
3610 * the corresponding reference identifiers.
3611 * For accesses to structures, the returned access relation accesses
3612 * all individual fields in the structures.
3614 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3615 int read
, int write
, int kill
, int must
, int tag
)
3618 isl_union_map
*accesses
;
3619 isl_union_set
*arrays
;
3620 isl_union_map
*to_inner
;
3625 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3627 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3628 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3629 isl_union_map
*accesses_i
;
3632 if (kill
&& !is_kill(stmt
))
3635 space
= isl_set_get_space(scop
->context
);
3636 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
3638 accesses
= isl_union_map_union(accesses
, accesses_i
);
3641 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
3642 for (i
= 0; i
< scop
->n_array
; ++i
) {
3643 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
3644 arrays
= isl_union_set_add_set(arrays
, extent
);
3646 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
3648 to_inner
= compute_to_inner(scop
);
3649 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
3654 /* Collect all potential read access relations.
3656 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
3658 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
3661 /* Collect all potential write access relations.
3663 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
3665 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
3668 /* Collect all definite write access relations.
3670 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
3672 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
3675 /* Collect all definite kill access relations.
3677 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
3679 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
3682 /* Collect all tagged potential read access relations.
3684 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
3685 struct pet_scop
*scop
)
3687 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
3690 /* Collect all tagged potential write access relations.
3692 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
3693 struct pet_scop
*scop
)
3695 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
3698 /* Collect all tagged definite write access relations.
3700 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
3701 struct pet_scop
*scop
)
3703 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
3706 /* Collect all tagged definite kill access relations.
3708 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
3709 struct pet_scop
*scop
)
3711 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
3714 /* Collect and return the union of iteration domains in "scop".
3716 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3720 isl_union_set
*domain
;
3725 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3727 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3728 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3729 domain
= isl_union_set_add_set(domain
, domain_i
);
3735 /* Collect and return the schedules of the statements in "scop".
3736 * The range is normalized to the maximal number of scheduling
3739 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3742 isl_map
*schedule_i
;
3743 isl_union_map
*schedule
;
3744 int depth
, max_depth
= 0;
3749 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3751 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3752 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3753 if (depth
> max_depth
)
3757 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3758 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3759 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3760 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3762 for (j
= depth
; j
< max_depth
; ++j
)
3763 schedule_i
= isl_map_fix_si(schedule_i
,
3765 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3771 /* Does expression "expr" write to "id"?
3773 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3778 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3779 int writes
= expr_writes(expr
->args
[i
], id
);
3780 if (writes
< 0 || writes
)
3784 if (expr
->type
!= pet_expr_access
)
3786 if (!expr
->acc
.write
)
3788 if (pet_expr_is_affine(expr
))
3791 write_id
= pet_expr_access_get_id(expr
);
3792 isl_id_free(write_id
);
3797 return write_id
== id
;
3800 /* Does statement "stmt" write to "id"?
3802 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3804 return expr_writes(stmt
->body
, id
);
3807 /* Is there any write access in "scop" that accesses "id"?
3809 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3816 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3817 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3818 if (writes
< 0 || writes
)
3825 /* Add a reference identifier to access expression "expr".
3826 * "user" points to an integer that contains the sequence number
3827 * of the next reference.
3829 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3838 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3839 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3840 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3841 if (!expr
->acc
.ref_id
)
3842 return pet_expr_free(expr
);
3847 /* Add a reference identifier to all access expressions in "stmt".
3848 * "n_ref" points to an integer that contains the sequence number
3849 * of the next reference.
3851 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3858 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3859 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3860 &access_add_ref_id
, n_ref
);
3862 return pet_stmt_free(stmt
);
3865 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3867 return pet_stmt_free(stmt
);
3872 /* Add a reference identifier to all access expressions in "scop".
3874 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3883 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3884 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3885 if (!scop
->stmts
[i
])
3886 return pet_scop_free(scop
);
3892 /* Reset the user pointer on all parameter ids in "array".
3894 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3899 array
->context
= isl_set_reset_user(array
->context
);
3900 array
->extent
= isl_set_reset_user(array
->extent
);
3901 if (!array
->context
|| !array
->extent
)
3902 return pet_array_free(array
);
3907 /* Reset the user pointer on all parameter and tuple ids in
3908 * the access relation and the index expressions
3909 * of the access expression "expr".
3911 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3913 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
3914 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
3915 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3916 return pet_expr_free(expr
);
3921 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3923 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3932 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
3933 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
3934 if (!stmt
->domain
|| !stmt
->schedule
)
3935 return pet_stmt_free(stmt
);
3937 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3938 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3939 &access_anonymize
, NULL
);
3941 return pet_stmt_free(stmt
);
3944 stmt
->body
= pet_expr_map_access(stmt
->body
,
3945 &access_anonymize
, NULL
);
3947 return pet_stmt_free(stmt
);
3952 /* Reset the user pointer on the tuple ids and all parameter ids
3955 static struct pet_implication
*implication_anonymize(
3956 struct pet_implication
*implication
)
3961 implication
->extension
= isl_map_reset_user(implication
->extension
);
3962 if (!implication
->extension
)
3963 return pet_implication_free(implication
);
3968 /* Reset the user pointer on all parameter and tuple ids in "scop".
3970 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3977 scop
->context
= isl_set_reset_user(scop
->context
);
3978 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
3979 if (!scop
->context
|| !scop
->context_value
)
3980 return pet_scop_free(scop
);
3982 for (i
= 0; i
< scop
->n_array
; ++i
) {
3983 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3984 if (!scop
->arrays
[i
])
3985 return pet_scop_free(scop
);
3988 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3989 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3990 if (!scop
->stmts
[i
])
3991 return pet_scop_free(scop
);
3994 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3995 scop
->implications
[i
] =
3996 implication_anonymize(scop
->implications
[i
]);
3997 if (!scop
->implications
[i
])
3998 return pet_scop_free(scop
);
4004 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
4005 * then intersect the range of "map" with the valid set of values.
4007 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
4008 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
4013 isl_ctx
*ctx
= isl_map_get_ctx(map
);
4015 id
= pet_expr_access_get_id(arg
);
4016 space
= isl_space_alloc(ctx
, 0, 0, 1);
4017 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
4018 vb
= isl_union_map_extract_map(value_bounds
, space
);
4019 if (!isl_map_plain_is_empty(vb
))
4020 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
4027 /* Given a set "domain", return a wrapped relation with the given set
4028 * as domain and a range of dimension "n_arg", where each coordinate
4029 * is either unbounded or, if the corresponding element of args is of
4030 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
4032 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
4033 unsigned n_arg
, struct pet_expr
**args
,
4034 __isl_keep isl_union_map
*value_bounds
)
4040 map
= isl_map_from_domain(domain
);
4041 space
= isl_map_get_space(map
);
4042 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
4044 for (i
= 0; i
< n_arg
; ++i
) {
4046 struct pet_expr
*arg
= args
[i
];
4048 map_i
= isl_map_universe(isl_space_copy(space
));
4049 if (arg
->type
== pet_expr_access
)
4050 map_i
= access_apply_value_bounds(map_i
, arg
,
4052 map
= isl_map_flat_range_product(map
, map_i
);
4054 isl_space_free(space
);
4056 return isl_map_wrap(map
);
4059 /* Data used in access_gist() callback.
4061 struct pet_access_gist_data
{
4063 isl_union_map
*value_bounds
;
4066 /* Given an expression "expr" of type pet_expr_access, compute
4067 * the gist of the associated access relation and index expression
4068 * with respect to data->domain and the bounds on the values of the arguments
4069 * of the expression.
4071 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
4073 struct pet_access_gist_data
*data
= user
;
4076 domain
= isl_set_copy(data
->domain
);
4077 if (expr
->n_arg
> 0)
4078 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
4079 data
->value_bounds
);
4081 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
4082 isl_set_copy(domain
));
4083 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
4084 if (!expr
->acc
.access
|| !expr
->acc
.index
)
4085 return pet_expr_free(expr
);
4090 /* Compute the gist of the iteration domain and all access relations
4091 * of "stmt" based on the constraints on the parameters specified by "context"
4092 * and the constraints on the values of nested accesses specified
4093 * by "value_bounds".
4095 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
4096 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
4101 struct pet_access_gist_data data
;
4106 data
.domain
= isl_set_copy(stmt
->domain
);
4107 data
.value_bounds
= value_bounds
;
4108 if (stmt
->n_arg
> 0)
4109 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
4111 data
.domain
= isl_set_intersect_params(data
.domain
,
4112 isl_set_copy(context
));
4114 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
4115 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
4116 &access_gist
, &data
);
4121 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
4125 isl_set_free(data
.domain
);
4127 space
= isl_set_get_space(stmt
->domain
);
4128 if (isl_space_is_wrapping(space
))
4129 space
= isl_space_domain(isl_space_unwrap(space
));
4130 domain
= isl_set_universe(space
);
4131 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
4132 if (stmt
->n_arg
> 0)
4133 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
4135 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
4137 return pet_stmt_free(stmt
);
4141 isl_set_free(data
.domain
);
4142 return pet_stmt_free(stmt
);
4145 /* Compute the gist of the extent of the array
4146 * based on the constraints on the parameters specified by "context".
4148 static struct pet_array
*array_gist(struct pet_array
*array
,
4149 __isl_keep isl_set
*context
)
4154 array
->extent
= isl_set_gist_params(array
->extent
,
4155 isl_set_copy(context
));
4157 return pet_array_free(array
);
4162 /* Compute the gist of all sets and relations in "scop"
4163 * based on the constraints on the parameters specified by "scop->context"
4164 * and the constraints on the values of nested accesses specified
4165 * by "value_bounds".
4167 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
4168 __isl_keep isl_union_map
*value_bounds
)
4175 scop
->context
= isl_set_coalesce(scop
->context
);
4177 return pet_scop_free(scop
);
4179 for (i
= 0; i
< scop
->n_array
; ++i
) {
4180 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
4181 if (!scop
->arrays
[i
])
4182 return pet_scop_free(scop
);
4185 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4186 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
4188 if (!scop
->stmts
[i
])
4189 return pet_scop_free(scop
);
4195 /* Intersect the context of "scop" with "context".
4196 * To ensure that we don't introduce any unnamed parameters in
4197 * the context of "scop", we first remove the unnamed parameters
4200 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
4201 __isl_take isl_set
*context
)
4206 context
= set_project_out_unnamed_params(context
);
4207 scop
->context
= isl_set_intersect(scop
->context
, context
);
4209 return pet_scop_free(scop
);
4213 isl_set_free(context
);
4214 return pet_scop_free(scop
);
4217 /* Drop the current context of "scop". That is, replace the context
4218 * by a universal set.
4220 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
4227 space
= isl_set_get_space(scop
->context
);
4228 isl_set_free(scop
->context
);
4229 scop
->context
= isl_set_universe(space
);
4231 return pet_scop_free(scop
);
4236 /* Append "array" to the arrays of "scop".
4238 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
4239 struct pet_array
*array
)
4242 struct pet_array
**arrays
;
4244 if (!array
|| !scop
)
4247 ctx
= isl_set_get_ctx(scop
->context
);
4248 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
4252 scop
->arrays
= arrays
;
4253 scop
->arrays
[scop
->n_array
] = array
;
4258 pet_array_free(array
);
4259 return pet_scop_free(scop
);
4262 /* Create and return an implication on filter values equal to "satisfied"
4263 * with extension "map".
4265 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
4269 struct pet_implication
*implication
;
4273 ctx
= isl_map_get_ctx(map
);
4274 implication
= isl_alloc_type(ctx
, struct pet_implication
);
4278 implication
->extension
= map
;
4279 implication
->satisfied
= satisfied
;
4287 /* Add an implication on filter values equal to "satisfied"
4288 * with extension "map" to "scop".
4290 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
4291 __isl_take isl_map
*map
, int satisfied
)
4294 struct pet_implication
*implication
;
4295 struct pet_implication
**implications
;
4297 implication
= new_implication(map
, satisfied
);
4298 if (!scop
|| !implication
)
4301 ctx
= isl_set_get_ctx(scop
->context
);
4302 implications
= isl_realloc_array(ctx
, scop
->implications
,
4303 struct pet_implication
*,
4304 scop
->n_implication
+ 1);
4307 scop
->implications
= implications
;
4308 scop
->implications
[scop
->n_implication
] = implication
;
4309 scop
->n_implication
++;
4313 pet_implication_free(implication
);
4314 return pet_scop_free(scop
);
4317 /* Given an access expression, check if it is data dependent.
4318 * If so, set *found and abort the search.
4320 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
4332 /* Does "scop" contain any data dependent accesses?
4334 * Check the body of each statement for such accesses.
4336 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
4344 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4345 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
4346 &is_data_dependent
, &found
);
4347 if (r
< 0 && !found
)
4356 /* Does "scop" contain and data dependent conditions?
4358 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
4365 for (i
= 0; i
< scop
->n_stmt
; ++i
)
4366 if (scop
->stmts
[i
]->n_arg
> 0)
4372 /* Keep track of the "input" file inside the (extended) "scop".
4374 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
4376 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4386 /* Print the original code corresponding to "scop" to printer "p".
4388 * pet_scop_print_original can only be called from
4389 * a pet_transform_C_source callback. This means that the input
4390 * file is stored in the extended scop and that the printer prints
4393 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
4394 __isl_take isl_printer
*p
)
4396 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4400 return isl_printer_free(p
);
4403 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
4404 "no input file stored in scop",
4405 return isl_printer_free(p
));
4407 output
= isl_printer_get_file(p
);
4409 return isl_printer_free(p
);
4411 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
4412 return isl_printer_free(p
);