2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
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_int
] = "int",
53 static char *op_str
[] = {
54 [pet_op_add_assign
] = "+=",
55 [pet_op_sub_assign
] = "-=",
56 [pet_op_mul_assign
] = "*=",
57 [pet_op_div_assign
] = "/=",
58 [pet_op_assign
] = "=",
73 [pet_op_post_inc
] = "++",
74 [pet_op_post_dec
] = "--",
75 [pet_op_pre_inc
] = "++",
76 [pet_op_pre_dec
] = "--",
77 [pet_op_address_of
] = "&",
86 [pet_op_assume
] = "assume",
87 [pet_op_kill
] = "kill"
90 /* pet_scop with extra information that is used during parsing and printing.
92 * In particular, we keep track of conditions under which we want
93 * to skip the rest of the current loop iteration (skip[pet_skip_now])
94 * and of conditions under which we want to skip subsequent
95 * loop iterations (skip[pet_skip_later]).
97 * The conditions are represented as index expressions defined
98 * over a zero-dimensional domain. The index expression is either
99 * a boolean affine expression or an access to a variable, which
100 * is assumed to attain values zero and one. The condition holds
101 * if the variable has value one or if the affine expression
102 * has value one (typically for only part of the parameter space).
104 * A missing condition (skip[type] == NULL) means that we don't want
107 * Additionally, we keep track of the original input file
108 * inside pet_transform_C_source.
110 struct pet_scop_ext
{
111 struct pet_scop scop
;
113 isl_multi_pw_aff
*skip
[2];
117 const char *pet_op_str(enum pet_op_type op
)
122 int pet_op_is_inc_dec(enum pet_op_type op
)
124 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
125 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
128 const char *pet_type_str(enum pet_expr_type type
)
130 return type_str
[type
];
133 enum pet_op_type
pet_str_op(const char *str
)
137 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
138 if (!strcmp(op_str
[i
], str
))
144 enum pet_expr_type
pet_str_type(const char *str
)
148 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
149 if (!strcmp(type_str
[i
], str
))
155 /* Construct an access pet_expr from an access relation and an index expression.
156 * By default, it is considered to be a read access.
158 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
159 __isl_take isl_multi_pw_aff
*index
)
161 isl_ctx
*ctx
= isl_map_get_ctx(access
);
162 struct pet_expr
*expr
;
164 if (!index
|| !access
)
166 expr
= isl_calloc_type(ctx
, struct pet_expr
);
170 expr
->type
= pet_expr_access
;
171 expr
->acc
.access
= access
;
172 expr
->acc
.index
= index
;
178 isl_map_free(access
);
179 isl_multi_pw_aff_free(index
);
183 /* Construct an access pet_expr from an index expression.
184 * By default, the access is considered to be a read access.
186 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
190 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
191 return pet_expr_from_access_and_index(access
, index
);
194 /* Extend the range of "access" with "n" dimensions, retaining
195 * the tuple identifier on this range.
197 * If "access" represents a member access, then extend the range
200 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
204 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
206 if (!isl_map_range_is_wrapping(access
)) {
207 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
211 domain
= isl_map_copy(access
);
212 domain
= isl_map_range_factor_domain(domain
);
213 access
= isl_map_range_factor_range(access
);
214 access
= extend_range(access
, n
);
215 access
= isl_map_range_product(domain
, access
);
218 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
223 /* Construct an access pet_expr from an index expression and
224 * the depth of the accessed array.
225 * By default, the access is considered to be a read access.
227 * If the number of indices is smaller than the depth of the array,
228 * then we assume that all elements of the remaining dimensions
231 struct pet_expr
*pet_expr_from_index_and_depth(
232 __isl_take isl_multi_pw_aff
*index
, int depth
)
237 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
240 dim
= isl_map_dim(access
, isl_dim_out
);
242 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
243 "number of indices greater than depth",
244 access
= isl_map_free(access
));
246 return pet_expr_from_access_and_index(access
, index
);
248 access
= extend_range(access
, depth
- dim
);
250 return pet_expr_from_access_and_index(access
, index
);
252 isl_multi_pw_aff_free(index
);
256 /* Construct a pet_expr that kills the elements specified by
257 * the index expression "index" and the access relation "access".
259 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
260 __isl_take isl_multi_pw_aff
*index
)
263 struct pet_expr
*expr
;
265 if (!access
|| !index
)
268 ctx
= isl_multi_pw_aff_get_ctx(index
);
269 expr
= pet_expr_from_access_and_index(access
, index
);
273 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
275 isl_map_free(access
);
276 isl_multi_pw_aff_free(index
);
280 /* Construct a unary pet_expr that performs "op" on "arg".
282 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
283 struct pet_expr
*arg
)
285 struct pet_expr
*expr
;
289 expr
= isl_alloc_type(ctx
, struct pet_expr
);
293 expr
->type
= pet_expr_op
;
296 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
299 expr
->args
[pet_un_arg
] = arg
;
307 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
309 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
310 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
312 struct pet_expr
*expr
;
316 expr
= isl_alloc_type(ctx
, struct pet_expr
);
320 expr
->type
= pet_expr_op
;
323 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
326 expr
->args
[pet_bin_lhs
] = lhs
;
327 expr
->args
[pet_bin_rhs
] = rhs
;
336 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
338 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
339 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
341 struct pet_expr
*expr
;
343 if (!cond
|| !lhs
|| !rhs
)
345 expr
= isl_alloc_type(ctx
, struct pet_expr
);
349 expr
->type
= pet_expr_op
;
350 expr
->op
= pet_op_cond
;
352 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
355 expr
->args
[pet_ter_cond
] = cond
;
356 expr
->args
[pet_ter_true
] = lhs
;
357 expr
->args
[pet_ter_false
] = rhs
;
367 /* Construct a call pet_expr that calls function "name" with "n_arg"
368 * arguments. The caller is responsible for filling in the arguments.
370 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
373 struct pet_expr
*expr
;
375 expr
= isl_alloc_type(ctx
, struct pet_expr
);
379 expr
->type
= pet_expr_call
;
381 expr
->name
= strdup(name
);
382 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
383 if (!expr
->name
|| !expr
->args
)
384 return pet_expr_free(expr
);
389 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
391 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
392 struct pet_expr
*arg
)
394 struct pet_expr
*expr
;
399 expr
= isl_alloc_type(ctx
, struct pet_expr
);
403 expr
->type
= pet_expr_cast
;
405 expr
->type_name
= strdup(type_name
);
406 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
407 if (!expr
->type_name
|| !expr
->args
)
419 /* Construct a pet_expr that represents the double "d".
421 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
423 struct pet_expr
*expr
;
425 expr
= isl_calloc_type(ctx
, struct pet_expr
);
429 expr
->type
= pet_expr_double
;
431 expr
->d
.s
= strdup(s
);
433 return pet_expr_free(expr
);
438 /* Construct a pet_expr that represents the integer value "v".
440 struct pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
443 struct pet_expr
*expr
;
448 ctx
= isl_val_get_ctx(v
);
449 expr
= isl_calloc_type(ctx
, struct pet_expr
);
453 expr
->type
= pet_expr_int
;
462 struct pet_expr
*pet_expr_free(struct pet_expr
*expr
)
469 for (i
= 0; i
< expr
->n_arg
; ++i
)
470 pet_expr_free(expr
->args
[i
]);
473 switch (expr
->type
) {
474 case pet_expr_access
:
475 isl_id_free(expr
->acc
.ref_id
);
476 isl_map_free(expr
->acc
.access
);
477 isl_multi_pw_aff_free(expr
->acc
.index
);
483 free(expr
->type_name
);
485 case pet_expr_double
:
489 isl_val_free(expr
->i
);
499 static void expr_dump(struct pet_expr
*expr
, int indent
)
506 fprintf(stderr
, "%*s", indent
, "");
508 switch (expr
->type
) {
509 case pet_expr_double
:
510 fprintf(stderr
, "%s\n", expr
->d
.s
);
513 isl_val_dump(expr
->i
);
515 case pet_expr_access
:
516 if (expr
->acc
.ref_id
) {
517 isl_id_dump(expr
->acc
.ref_id
);
518 fprintf(stderr
, "%*s", indent
, "");
520 isl_map_dump(expr
->acc
.access
);
521 fprintf(stderr
, "%*s", indent
, "");
522 isl_multi_pw_aff_dump(expr
->acc
.index
);
523 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
525 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
526 "", expr
->acc
.write
);
527 for (i
= 0; i
< expr
->n_arg
; ++i
)
528 expr_dump(expr
->args
[i
], indent
+ 2);
531 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
532 for (i
= 0; i
< expr
->n_arg
; ++i
)
533 expr_dump(expr
->args
[i
], indent
+ 2);
536 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
537 for (i
= 0; i
< expr
->n_arg
; ++i
)
538 expr_dump(expr
->args
[i
], indent
+ 2);
541 fprintf(stderr
, "(%s)\n", expr
->type_name
);
542 for (i
= 0; i
< expr
->n_arg
; ++i
)
543 expr_dump(expr
->args
[i
], indent
+ 2);
548 void pet_expr_dump(struct pet_expr
*expr
)
553 /* Does "expr" represent an access to an unnamed space, i.e.,
554 * does it represent an affine expression?
556 int pet_expr_is_affine(struct pet_expr
*expr
)
562 if (expr
->type
!= pet_expr_access
)
565 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
572 /* Return the identifier of the array accessed by "expr".
574 * If "expr" represents a member access, then return the identifier
575 * of the outer structure array.
577 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
581 if (expr
->type
!= pet_expr_access
)
584 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
588 space
= isl_map_get_space(expr
->acc
.access
);
589 space
= isl_space_range(space
);
590 while (space
&& isl_space_is_wrapping(space
))
591 space
= isl_space_domain(isl_space_unwrap(space
));
592 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
593 isl_space_free(space
);
598 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
601 /* Align the parameters of expr->acc.index and expr->acc.access.
603 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
607 if (expr
->type
!= pet_expr_access
)
608 return pet_expr_free(expr
);
610 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
611 isl_multi_pw_aff_get_space(expr
->acc
.index
));
612 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
613 isl_map_get_space(expr
->acc
.access
));
614 if (!expr
->acc
.access
|| !expr
->acc
.index
)
615 return pet_expr_free(expr
);
620 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
622 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
626 if (expr
->type
!= pet_expr_access
)
629 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
632 /* Return 1 if the two pet_exprs are equivalent.
634 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
638 if (!expr1
|| !expr2
)
641 if (expr1
->type
!= expr2
->type
)
643 if (expr1
->n_arg
!= expr2
->n_arg
)
645 for (i
= 0; i
< expr1
->n_arg
; ++i
)
646 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
648 switch (expr1
->type
) {
649 case pet_expr_double
:
650 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
652 if (expr1
->d
.val
!= expr2
->d
.val
)
656 if (!isl_val_eq(expr1
->i
, expr2
->i
))
659 case pet_expr_access
:
660 if (expr1
->acc
.read
!= expr2
->acc
.read
)
662 if (expr1
->acc
.write
!= expr2
->acc
.write
)
664 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
666 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
668 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
670 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
672 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
677 if (expr1
->op
!= expr2
->op
)
681 if (strcmp(expr1
->name
, expr2
->name
))
685 if (strcmp(expr1
->type_name
, expr2
->type_name
))
693 /* Add extra conditions on the parameters to all access relations in "expr".
695 * The conditions are not added to the index expression. Instead, they
696 * are used to try and simplify the index expression.
698 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
699 __isl_take isl_set
*cond
)
706 for (i
= 0; i
< expr
->n_arg
; ++i
) {
707 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
713 if (expr
->type
== pet_expr_access
) {
714 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
716 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
717 expr
->acc
.index
, isl_set_copy(cond
));
718 if (!expr
->acc
.access
|| !expr
->acc
.index
)
726 return pet_expr_free(expr
);
729 /* Tag the access relation "access" with "id".
730 * That is, insert the id as the range of a wrapped relation
731 * in the domain of "access".
733 * If "access" is of the form
737 * then the result is of the form
739 * [D[i] -> id[]] -> A[a]
741 static __isl_give isl_map
*tag_access(__isl_take isl_map
*access
,
742 __isl_take isl_id
*id
)
747 space
= isl_space_range(isl_map_get_space(access
));
748 space
= isl_space_from_range(space
);
749 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
750 add_tag
= isl_map_universe(space
);
751 access
= isl_map_domain_product(access
, add_tag
);
756 /* Modify all expressions of type pet_expr_access in "expr"
757 * by calling "fn" on them.
759 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
760 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
768 for (i
= 0; i
< expr
->n_arg
; ++i
) {
769 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
771 return pet_expr_free(expr
);
774 if (expr
->type
== pet_expr_access
)
775 expr
= fn(expr
, user
);
780 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
782 * Return -1 on error (where fn return a negative value is treated as an error).
783 * Otherwise return 0.
785 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
786 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
793 for (i
= 0; i
< expr
->n_arg
; ++i
)
794 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
797 if (expr
->type
== pet_expr_access
)
798 return fn(expr
, user
);
803 /* Modify the access relation and index expression
804 * of the given access expression
805 * based on the given iteration space transformation.
806 * In particular, precompose the access relation and index expression
807 * with the update function.
809 * If the access has any arguments then the domain of the access relation
810 * is a wrapped mapping from the iteration space to the space of
811 * argument values. We only need to change the domain of this wrapped
812 * mapping, so we extend the input transformation with an identity mapping
813 * on the space of argument values.
815 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
817 isl_multi_pw_aff
*update
= user
;
820 update
= isl_multi_pw_aff_copy(update
);
822 space
= isl_map_get_space(expr
->acc
.access
);
823 space
= isl_space_domain(space
);
824 if (!isl_space_is_wrapping(space
))
825 isl_space_free(space
);
827 isl_multi_pw_aff
*id
;
828 space
= isl_space_unwrap(space
);
829 space
= isl_space_range(space
);
830 space
= isl_space_map_from_set(space
);
831 id
= isl_multi_pw_aff_identity(space
);
832 update
= isl_multi_pw_aff_product(update
, id
);
835 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
837 isl_multi_pw_aff_copy(update
));
838 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
839 expr
->acc
.index
, update
);
840 if (!expr
->acc
.access
|| !expr
->acc
.index
)
841 return pet_expr_free(expr
);
846 /* Modify all access relations in "expr" by precomposing them with
847 * the given iteration space transformation.
849 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
850 __isl_take isl_multi_pw_aff
*update
)
852 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
853 isl_multi_pw_aff_free(update
);
857 /* Construct a pet_stmt with given line number and statement
858 * number from a pet_expr.
859 * The initial iteration domain is the zero-dimensional universe.
860 * The name of the domain is given by "label" if it is non-NULL.
861 * Otherwise, the name is constructed as S_<id>.
862 * The domains of all access relations are modified to refer
863 * to the statement iteration domain.
865 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
866 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
868 struct pet_stmt
*stmt
;
872 isl_multi_pw_aff
*add_name
;
878 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
882 dim
= isl_space_set_alloc(ctx
, 0, 0);
884 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
886 snprintf(name
, sizeof(name
), "S_%d", id
);
887 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
889 dom
= isl_set_universe(isl_space_copy(dim
));
890 sched
= isl_map_from_domain(isl_set_copy(dom
));
892 dim
= isl_space_from_domain(dim
);
893 add_name
= isl_multi_pw_aff_zero(dim
);
894 expr
= expr_update_domain(expr
, add_name
);
898 stmt
->schedule
= sched
;
901 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
902 return pet_stmt_free(stmt
);
911 void *pet_stmt_free(struct pet_stmt
*stmt
)
918 isl_set_free(stmt
->domain
);
919 isl_map_free(stmt
->schedule
);
920 pet_expr_free(stmt
->body
);
922 for (i
= 0; i
< stmt
->n_arg
; ++i
)
923 pet_expr_free(stmt
->args
[i
]);
930 /* Return the iteration space of "stmt".
932 * If the statement has arguments, then stmt->domain is a wrapped map
933 * mapping the iteration domain to the values of the arguments
934 * for which this statement is executed.
935 * In this case, we need to extract the domain space of this wrapped map.
937 __isl_give isl_space
*pet_stmt_get_space(struct pet_stmt
*stmt
)
944 space
= isl_set_get_space(stmt
->domain
);
945 if (isl_space_is_wrapping(space
))
946 space
= isl_space_domain(isl_space_unwrap(space
));
951 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
958 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
959 fprintf(stderr
, "%*s", indent
, "");
960 isl_set_dump(stmt
->domain
);
961 fprintf(stderr
, "%*s", indent
, "");
962 isl_map_dump(stmt
->schedule
);
963 expr_dump(stmt
->body
, indent
);
964 for (i
= 0; i
< stmt
->n_arg
; ++i
)
965 expr_dump(stmt
->args
[i
], indent
+ 2);
968 void pet_stmt_dump(struct pet_stmt
*stmt
)
973 /* Allocate a new pet_type with the given "name" and "definition".
975 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
976 const char *definition
)
978 struct pet_type
*type
;
980 type
= isl_alloc_type(ctx
, struct pet_type
);
984 type
->name
= strdup(name
);
985 type
->definition
= strdup(definition
);
987 if (!type
->name
|| !type
->definition
)
988 return pet_type_free(type
);
993 /* Free "type" and return NULL.
995 struct pet_type
*pet_type_free(struct pet_type
*type
)
1001 free(type
->definition
);
1007 struct pet_array
*pet_array_free(struct pet_array
*array
)
1012 isl_set_free(array
->context
);
1013 isl_set_free(array
->extent
);
1014 isl_set_free(array
->value_bounds
);
1015 free(array
->element_type
);
1021 void pet_array_dump(struct pet_array
*array
)
1026 isl_set_dump(array
->context
);
1027 isl_set_dump(array
->extent
);
1028 isl_set_dump(array
->value_bounds
);
1029 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
1030 array
->element_is_record
? " element-is-record" : "",
1031 array
->live_out
? " live-out" : "");
1034 /* Alloc a pet_scop structure, with extra room for information that
1035 * is only used during parsing.
1037 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
1039 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
1042 /* Construct a pet_scop with room for n statements.
1044 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
1047 struct pet_scop
*scop
;
1049 scop
= pet_scop_alloc(ctx
);
1053 space
= isl_space_params_alloc(ctx
, 0);
1054 scop
->context
= isl_set_universe(isl_space_copy(space
));
1055 scop
->context_value
= isl_set_universe(space
);
1056 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
1057 if (!scop
->context
|| !scop
->stmts
)
1058 return pet_scop_free(scop
);
1065 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
1067 return scop_alloc(ctx
, 0);
1070 /* Update "context" with respect to the valid parameter values for "access".
1072 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
1073 __isl_take isl_set
*context
)
1075 context
= isl_set_intersect(context
,
1076 isl_map_params(isl_map_copy(access
)));
1080 /* Update "context" with respect to the valid parameter values for "expr".
1082 * If "expr" represents a conditional operator, then a parameter value
1083 * needs to be valid for the condition and for at least one of the
1084 * remaining two arguments.
1085 * If the condition is an affine expression, then we can be a bit more specific.
1086 * The parameter then has to be valid for the second argument for
1087 * non-zero accesses and valid for the third argument for zero accesses.
1089 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
1090 __isl_take isl_set
*context
)
1094 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
1096 isl_set
*context1
, *context2
;
1098 is_aff
= pet_expr_is_affine(expr
->args
[0]);
1102 context
= expr_extract_context(expr
->args
[0], context
);
1103 context1
= expr_extract_context(expr
->args
[1],
1104 isl_set_copy(context
));
1105 context2
= expr_extract_context(expr
->args
[2], context
);
1111 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
1112 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
1113 zero_set
= isl_map_params(access
);
1114 context1
= isl_set_subtract(context1
,
1115 isl_set_copy(zero_set
));
1116 context2
= isl_set_intersect(context2
, zero_set
);
1119 context
= isl_set_union(context1
, context2
);
1120 context
= isl_set_coalesce(context
);
1125 for (i
= 0; i
< expr
->n_arg
; ++i
)
1126 context
= expr_extract_context(expr
->args
[i
], context
);
1128 if (expr
->type
== pet_expr_access
)
1129 context
= access_extract_context(expr
->acc
.access
, context
);
1133 isl_set_free(context
);
1137 /* Update "context" with respect to the valid parameter values for "stmt".
1139 * If the statement is an assume statement with an affine expression,
1140 * then intersect "context" with that expression.
1141 * Otherwise, intersect "context" with the contexts of the expressions
1144 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
1145 __isl_take isl_set
*context
)
1149 if (pet_stmt_is_assume(stmt
) &&
1150 pet_expr_is_affine(stmt
->body
->args
[0])) {
1151 isl_multi_pw_aff
*index
;
1155 index
= stmt
->body
->args
[0]->acc
.index
;
1156 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
1157 cond
= isl_set_params(isl_pw_aff_non_zero_set(pa
));
1158 return isl_set_intersect(context
, cond
);
1161 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1162 context
= expr_extract_context(stmt
->args
[i
], context
);
1164 context
= expr_extract_context(stmt
->body
, context
);
1169 /* Construct a pet_scop that contains the given pet_stmt.
1171 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
1173 struct pet_scop
*scop
;
1178 scop
= scop_alloc(ctx
, 1);
1182 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
1186 scop
->stmts
[0] = stmt
;
1190 pet_stmt_free(stmt
);
1191 pet_scop_free(scop
);
1195 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1196 * does it represent an affine expression?
1198 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
1202 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
1209 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1211 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
1212 __isl_take isl_set
*dom
)
1215 pa
= isl_set_indicator_function(set
);
1216 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1220 /* Return "lhs || rhs", defined on the shared definition domain.
1222 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1223 __isl_take isl_pw_aff
*rhs
)
1228 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1229 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1230 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1231 isl_pw_aff_non_zero_set(rhs
));
1232 cond
= isl_set_coalesce(cond
);
1233 return indicator_function(cond
, dom
);
1236 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1237 * ext may be equal to either ext1 or ext2.
1239 * The two skips that need to be combined are assumed to be affine expressions.
1241 * We need to skip in ext if we need to skip in either ext1 or ext2.
1242 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1244 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1245 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1248 isl_pw_aff
*skip
, *skip1
, *skip2
;
1252 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1254 if (!ext1
->skip
[type
]) {
1257 ext
->skip
[type
] = ext2
->skip
[type
];
1258 ext2
->skip
[type
] = NULL
;
1261 if (!ext2
->skip
[type
]) {
1264 ext
->skip
[type
] = ext1
->skip
[type
];
1265 ext1
->skip
[type
] = NULL
;
1269 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1270 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1271 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1272 isl_error_internal
, "can only combine affine skips",
1275 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1276 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1277 skip
= pw_aff_or(skip1
, skip2
);
1278 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1279 ext1
->skip
[type
] = NULL
;
1280 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1281 ext2
->skip
[type
] = NULL
;
1282 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1283 if (!ext
->skip
[type
])
1288 pet_scop_free(&ext
->scop
);
1292 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1293 * where type takes on the values pet_skip_now and pet_skip_later.
1294 * scop may be equal to either scop1 or scop2.
1296 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1297 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1299 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1300 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1301 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1303 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1304 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1308 /* Update scop->start and scop->end to include the region from "start"
1309 * to "end". In particular, if scop->end == 0, then "scop" does not
1310 * have any offset information yet and we simply take the information
1311 * from "start" and "end". Otherwise, we update the fields if the
1312 * region from "start" to "end" is not already included.
1314 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1315 unsigned start
, unsigned end
)
1319 if (scop
->end
== 0) {
1320 scop
->start
= start
;
1323 if (start
< scop
->start
)
1324 scop
->start
= start
;
1325 if (end
> scop
->end
)
1332 /* Does "implication" appear in the list of implications of "scop"?
1334 static int is_known_implication(struct pet_scop
*scop
,
1335 struct pet_implication
*implication
)
1339 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1340 struct pet_implication
*pi
= scop
->implications
[i
];
1343 if (pi
->satisfied
!= implication
->satisfied
)
1345 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1355 /* Store the concatenation of the implications of "scop1" and "scop2"
1356 * in "scop", removing duplicates (i.e., implications in "scop2" that
1357 * already appear in "scop1").
1359 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1360 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1367 if (scop2
->n_implication
== 0) {
1368 scop
->n_implication
= scop1
->n_implication
;
1369 scop
->implications
= scop1
->implications
;
1370 scop1
->n_implication
= 0;
1371 scop1
->implications
= NULL
;
1375 if (scop1
->n_implication
== 0) {
1376 scop
->n_implication
= scop2
->n_implication
;
1377 scop
->implications
= scop2
->implications
;
1378 scop2
->n_implication
= 0;
1379 scop2
->implications
= NULL
;
1383 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1384 scop1
->n_implication
+ scop2
->n_implication
);
1385 if (!scop
->implications
)
1386 return pet_scop_free(scop
);
1388 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1389 scop
->implications
[i
] = scop1
->implications
[i
];
1390 scop1
->implications
[i
] = NULL
;
1393 scop
->n_implication
= scop1
->n_implication
;
1394 j
= scop1
->n_implication
;
1395 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1398 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1400 return pet_scop_free(scop
);
1403 scop
->implications
[j
++] = scop2
->implications
[i
];
1404 scop2
->implications
[i
] = NULL
;
1406 scop
->n_implication
= j
;
1411 /* Combine the offset information of "scop1" and "scop2" into "scop".
1413 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1414 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1417 scop
= pet_scop_update_start_end(scop
,
1418 scop1
->start
, scop1
->end
);
1420 scop
= pet_scop_update_start_end(scop
,
1421 scop2
->start
, scop2
->end
);
1425 /* Construct a pet_scop that contains the offset information,
1426 * arrays, statements and skip information in "scop1" and "scop2".
1428 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1429 struct pet_scop
*scop2
)
1432 struct pet_scop
*scop
= NULL
;
1434 if (!scop1
|| !scop2
)
1437 if (scop1
->n_stmt
== 0) {
1438 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1439 pet_scop_free(scop1
);
1443 if (scop2
->n_stmt
== 0) {
1444 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1445 pet_scop_free(scop2
);
1449 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1453 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1454 scop1
->n_array
+ scop2
->n_array
);
1457 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1459 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1460 scop
->stmts
[i
] = scop1
->stmts
[i
];
1461 scop1
->stmts
[i
] = NULL
;
1464 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1465 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1466 scop2
->stmts
[i
] = NULL
;
1469 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1470 scop
->arrays
[i
] = scop1
->arrays
[i
];
1471 scop1
->arrays
[i
] = NULL
;
1474 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1475 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1476 scop2
->arrays
[i
] = NULL
;
1479 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1480 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1481 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1482 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1483 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1485 pet_scop_free(scop1
);
1486 pet_scop_free(scop2
);
1489 pet_scop_free(scop1
);
1490 pet_scop_free(scop2
);
1491 pet_scop_free(scop
);
1495 /* Apply the skip condition "skip" to "scop".
1496 * That is, make sure "scop" is not executed when the condition holds.
1498 * If "skip" is an affine expression, we add the conditions under
1499 * which the expression is zero to the iteration domains.
1500 * Otherwise, we add a filter on the variable attaining the value zero.
1502 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1503 __isl_take isl_multi_pw_aff
*skip
)
1512 is_aff
= multi_pw_aff_is_affine(skip
);
1517 return pet_scop_filter(scop
, skip
, 0);
1519 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1520 isl_multi_pw_aff_free(skip
);
1521 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1522 scop
= pet_scop_restrict(scop
, zero
);
1526 isl_multi_pw_aff_free(skip
);
1527 return pet_scop_free(scop
);
1530 /* Construct a pet_scop that contains the arrays, statements and
1531 * skip information in "scop1" and "scop2", where the two scops
1532 * are executed "in sequence". That is, breaks and continues
1533 * in scop1 have an effect on scop2.
1535 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1536 struct pet_scop
*scop2
)
1538 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1539 scop2
= restrict_skip(scop2
,
1540 pet_scop_get_skip(scop1
, pet_skip_now
));
1541 return pet_scop_add(ctx
, scop1
, scop2
);
1544 /* Construct a pet_scop that contains the arrays, statements and
1545 * skip information in "scop1" and "scop2", where the two scops
1546 * are executed "in parallel". That is, any break or continue
1547 * in scop1 has no effect on scop2.
1549 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1550 struct pet_scop
*scop2
)
1552 return pet_scop_add(ctx
, scop1
, scop2
);
1555 void *pet_implication_free(struct pet_implication
*implication
)
1562 isl_map_free(implication
->extension
);
1568 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1571 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1575 isl_set_free(scop
->context
);
1576 isl_set_free(scop
->context_value
);
1578 for (i
= 0; i
< scop
->n_type
; ++i
)
1579 pet_type_free(scop
->types
[i
]);
1582 for (i
= 0; i
< scop
->n_array
; ++i
)
1583 pet_array_free(scop
->arrays
[i
]);
1586 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1587 pet_stmt_free(scop
->stmts
[i
]);
1589 if (scop
->implications
)
1590 for (i
= 0; i
< scop
->n_implication
; ++i
)
1591 pet_implication_free(scop
->implications
[i
]);
1592 free(scop
->implications
);
1593 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1594 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1599 void pet_type_dump(struct pet_type
*type
)
1604 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1607 void pet_implication_dump(struct pet_implication
*implication
)
1612 fprintf(stderr
, "%d\n", implication
->satisfied
);
1613 isl_map_dump(implication
->extension
);
1616 void pet_scop_dump(struct pet_scop
*scop
)
1619 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1624 isl_set_dump(scop
->context
);
1625 isl_set_dump(scop
->context_value
);
1626 for (i
= 0; i
< scop
->n_type
; ++i
)
1627 pet_type_dump(scop
->types
[i
]);
1628 for (i
= 0; i
< scop
->n_array
; ++i
)
1629 pet_array_dump(scop
->arrays
[i
]);
1630 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1631 pet_stmt_dump(scop
->stmts
[i
]);
1632 for (i
= 0; i
< scop
->n_implication
; ++i
)
1633 pet_implication_dump(scop
->implications
[i
]);
1636 fprintf(stderr
, "skip\n");
1637 isl_multi_pw_aff_dump(ext
->skip
[0]);
1638 isl_multi_pw_aff_dump(ext
->skip
[1]);
1642 /* Return 1 if the two pet_arrays are equivalent.
1644 * We don't compare element_size as this may be target dependent.
1646 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1648 if (!array1
|| !array2
)
1651 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1653 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1655 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1657 if (array1
->value_bounds
&&
1658 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1660 if (strcmp(array1
->element_type
, array2
->element_type
))
1662 if (array1
->element_is_record
!= array2
->element_is_record
)
1664 if (array1
->live_out
!= array2
->live_out
)
1666 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1668 if (array1
->declared
!= array2
->declared
)
1670 if (array1
->exposed
!= array2
->exposed
)
1676 /* Return 1 if the two pet_stmts are equivalent.
1678 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1682 if (!stmt1
|| !stmt2
)
1685 if (stmt1
->line
!= stmt2
->line
)
1687 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1689 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1691 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1693 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1695 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1696 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1703 /* Return 1 if the two pet_types are equivalent.
1705 * We only compare the names of the types since the exact representation
1706 * of the definition may depend on the version of clang being used.
1708 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1710 if (!type1
|| !type2
)
1713 if (strcmp(type1
->name
, type2
->name
))
1719 /* Return 1 if the two pet_implications are equivalent.
1721 int pet_implication_is_equal(struct pet_implication
*implication1
,
1722 struct pet_implication
*implication2
)
1724 if (!implication1
|| !implication2
)
1727 if (implication1
->satisfied
!= implication2
->satisfied
)
1729 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1735 /* Return 1 if the two pet_scops are equivalent.
1737 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1741 if (!scop1
|| !scop2
)
1744 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1746 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1749 if (scop1
->n_type
!= scop2
->n_type
)
1751 for (i
= 0; i
< scop1
->n_type
; ++i
)
1752 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1755 if (scop1
->n_array
!= scop2
->n_array
)
1757 for (i
= 0; i
< scop1
->n_array
; ++i
)
1758 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1761 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1763 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1764 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1767 if (scop1
->n_implication
!= scop2
->n_implication
)
1769 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1770 if (!pet_implication_is_equal(scop1
->implications
[i
],
1771 scop2
->implications
[i
]))
1777 /* Prefix the schedule of "stmt" with an extra dimension with constant
1780 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1785 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1786 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1787 if (!stmt
->schedule
)
1788 return pet_stmt_free(stmt
);
1793 /* Prefix the schedules of all statements in "scop" with an extra
1794 * dimension with constant value "pos".
1796 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1803 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1804 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1805 if (!scop
->stmts
[i
])
1806 return pet_scop_free(scop
);
1812 /* Given a set with a parameter at "param_pos" that refers to the
1813 * iterator, "move" the iterator to the first set dimension.
1814 * That is, essentially equate the parameter to the first set dimension
1815 * and then project it out.
1817 * The first set dimension may however refer to a virtual iterator,
1818 * while the parameter refers to the "real" iterator.
1819 * We therefore need to take into account the affine expression "iv_map", which
1820 * expresses the real iterator in terms of the virtual iterator.
1821 * In particular, we equate the set dimension to the input of the map
1822 * and the parameter to the output of the map and then project out
1823 * everything we don't need anymore.
1825 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1826 int param_pos
, __isl_take isl_aff
*iv_map
)
1828 isl_map
*map
, *map2
;
1829 map
= isl_map_from_domain(set
);
1830 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1831 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1832 map2
= isl_map_from_aff(iv_map
);
1833 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1834 map
= isl_map_apply_range(map
, map2
);
1835 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1836 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1837 return isl_map_domain(map
);
1840 /* Data used in embed_access.
1841 * extend adds an iterator to the iteration domain (through precomposition).
1842 * iv_map expresses the real iterator in terms of the virtual iterator
1843 * var_id represents the induction variable of the corresponding loop
1845 struct pet_embed_access
{
1846 isl_multi_pw_aff
*extend
;
1851 /* Given an index expression, return an expression for the outer iterator.
1853 static __isl_give isl_aff
*index_outer_iterator(
1854 __isl_take isl_multi_pw_aff
*index
)
1857 isl_local_space
*ls
;
1859 space
= isl_multi_pw_aff_get_domain_space(index
);
1860 isl_multi_pw_aff_free(index
);
1862 ls
= isl_local_space_from_space(space
);
1863 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1866 /* Replace an index expression that references the new (outer) iterator variable
1867 * by one that references the corresponding (real) iterator.
1869 * The input index expression is of the form
1871 * { S[i',...] -> i[] }
1873 * where i' refers to the virtual iterator.
1875 * iv_map is of the form
1879 * Return the index expression
1881 * { S[i',...] -> [i] }
1883 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1884 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1889 aff
= index_outer_iterator(index
);
1890 space
= isl_aff_get_space(aff
);
1891 iv_map
= isl_aff_align_params(iv_map
, space
);
1892 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1894 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1897 /* Given an index expression "index" that refers to the (real) iterator
1898 * through the parameter at position "pos", plug in "iv_map", expressing
1899 * the real iterator in terms of the virtual (outer) iterator.
1901 * In particular, the index expression is of the form
1903 * [..., i, ...] -> { S[i',...] -> ... i ... }
1905 * where i refers to the real iterator and i' refers to the virtual iterator.
1907 * iv_map is of the form
1911 * Return the index expression
1913 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1916 * We first move the parameter to the input
1918 * [..., ...] -> { [i, i',...] -> ... i ... }
1922 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1924 * and then combine the two to obtain the desired result.
1926 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1927 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1929 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1932 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1933 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1934 isl_dim_param
, pos
, 1);
1936 space
= isl_space_map_from_set(space
);
1937 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1938 iv_map
= isl_aff_align_params(iv_map
, space
);
1939 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1940 ma
= isl_multi_aff_flat_range_product(
1941 isl_multi_aff_from_aff(iv_map
), ma
);
1942 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1947 /* Does the index expression "index" reference a virtual array, i.e.,
1948 * one with user pointer equal to NULL?
1949 * A virtual array does not have any members.
1951 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1956 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1958 if (isl_multi_pw_aff_range_is_wrapping(index
))
1960 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1961 is_virtual
= !isl_id_get_user(id
);
1967 /* Does the access relation "access" reference a virtual array, i.e.,
1968 * one with user pointer equal to NULL?
1969 * A virtual array does not have any members.
1971 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1976 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1978 if (isl_map_range_is_wrapping(access
))
1980 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1981 is_virtual
= !isl_id_get_user(id
);
1987 /* Embed the given index expression in an extra outer loop.
1988 * The domain of the index expression has already been updated.
1990 * If the access refers to the induction variable, then it is
1991 * turned into an access to the set of integers with index (and value)
1992 * equal to the induction variable.
1994 * If the accessed array is a virtual array (with user
1995 * pointer equal to NULL), as created by create_test_index,
1996 * then it is extended along with the domain of the index expression.
1998 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1999 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
2001 isl_id
*array_id
= NULL
;
2004 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
2005 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
2006 if (array_id
== data
->var_id
) {
2007 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
2008 } else if (index_is_virtual_array(index
)) {
2010 isl_multi_pw_aff
*mpa
;
2012 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
2013 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
2014 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
2015 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
2016 isl_id_copy(array_id
));
2018 isl_id_free(array_id
);
2020 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
2021 isl_dim_param
, data
->var_id
);
2023 index
= index_internalize_iv(index
, pos
,
2024 isl_aff_copy(data
->iv_map
));
2025 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
2026 isl_id_copy(data
->var_id
));
2031 /* Embed the given access relation in an extra outer loop.
2032 * The domain of the access relation has already been updated.
2034 * If the access refers to the induction variable, then it is
2035 * turned into an access to the set of integers with index (and value)
2036 * equal to the induction variable.
2038 * If the induction variable appears in the constraints (as a parameter),
2039 * then the parameter is equated to the newly introduced iteration
2040 * domain dimension and subsequently projected out.
2042 * Similarly, if the accessed array is a virtual array (with user
2043 * pointer equal to NULL), as created by create_test_index,
2044 * then it is extended along with the domain of the access.
2046 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
2047 struct pet_embed_access
*data
)
2049 isl_id
*array_id
= NULL
;
2052 if (isl_map_has_tuple_id(access
, isl_dim_out
))
2053 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2054 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
2055 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2056 access
= isl_map_equate(access
,
2057 isl_dim_in
, 0, isl_dim_out
, 0);
2058 if (array_id
== data
->var_id
)
2059 access
= isl_map_apply_range(access
,
2060 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
2062 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
2063 isl_id_copy(array_id
));
2065 isl_id_free(array_id
);
2067 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
2069 isl_set
*set
= isl_map_wrap(access
);
2070 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
2071 access
= isl_set_unwrap(set
);
2073 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
2074 isl_id_copy(data
->var_id
));
2079 /* Given an access expression, embed the associated access relation and
2080 * index expression in an extra outer loop.
2082 * We first update the domains to insert the extra dimension and
2083 * then update the access relation and index expression to take
2084 * into account the mapping "iv_map" from virtual iterator
2087 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
2089 struct pet_embed_access
*data
= user
;
2091 expr
= update_domain(expr
, data
->extend
);
2095 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
2096 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
2097 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2098 return pet_expr_free(expr
);
2103 /* Embed all access subexpressions of "expr" in an extra loop.
2104 * "extend" inserts an outer loop iterator in the iteration domains
2105 * (through precomposition).
2106 * "iv_map" expresses the real iterator in terms of the virtual iterator
2107 * "var_id" represents the induction variable.
2109 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
2110 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
2111 __isl_keep isl_id
*var_id
)
2113 struct pet_embed_access data
=
2114 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
2116 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
2117 isl_aff_free(iv_map
);
2118 isl_multi_pw_aff_free(extend
);
2122 /* Embed the given pet_stmt in an extra outer loop with iteration domain
2123 * "dom" and schedule "sched". "var_id" represents the induction variable
2124 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
2125 * That is, it expresses the iterator that some of the parameters in "stmt"
2126 * may refer to in terms of the iterator used in "dom" and
2127 * the domain of "sched".
2129 * The iteration domain and schedule of the statement are updated
2130 * according to the iteration domain and schedule of the new loop.
2131 * If stmt->domain is a wrapped map, then the iteration domain
2132 * is the domain of this map, so we need to be careful to adjust
2135 * If the induction variable appears in the constraints (as a parameter)
2136 * of the current iteration domain or the schedule of the statement,
2137 * then the parameter is equated to the newly introduced iteration
2138 * domain dimension and subsequently projected out.
2140 * Finally, all access relations are updated based on the extra loop.
2142 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
2143 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
2144 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
2150 isl_multi_pw_aff
*extend
;
2155 if (isl_set_is_wrapping(stmt
->domain
)) {
2160 map
= isl_set_unwrap(stmt
->domain
);
2161 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
2162 ran_dim
= isl_space_range(isl_map_get_space(map
));
2163 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
2164 isl_set_universe(ran_dim
));
2165 map
= isl_map_flat_domain_product(ext
, map
);
2166 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
2167 isl_id_copy(stmt_id
));
2168 dim
= isl_space_domain(isl_map_get_space(map
));
2169 stmt
->domain
= isl_map_wrap(map
);
2171 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
2172 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
2174 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
2175 isl_id_copy(stmt_id
));
2176 dim
= isl_set_get_space(stmt
->domain
);
2179 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
2181 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
2182 isl_aff_copy(iv_map
));
2184 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
2185 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
2186 isl_dim_in
, stmt_id
);
2188 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
2190 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
2191 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
2192 stmt
->schedule
= isl_set_unwrap(set
);
2195 dim
= isl_space_map_from_set(dim
);
2196 extend
= isl_multi_pw_aff_identity(dim
);
2197 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
2198 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
2199 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
2200 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2201 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
2202 isl_multi_pw_aff_copy(extend
),
2203 isl_aff_copy(iv_map
), var_id
);
2204 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
2207 isl_id_free(var_id
);
2209 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2211 return pet_stmt_free(stmt
);
2212 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2213 return pet_stmt_free(stmt
);
2217 isl_map_free(sched
);
2218 isl_aff_free(iv_map
);
2219 isl_id_free(var_id
);
2223 /* Embed the given pet_array in an extra outer loop with iteration domain
2225 * This embedding only has an effect on virtual arrays (those with
2226 * user pointer equal to NULL), which need to be extended along with
2227 * the iteration domain.
2229 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
2230 __isl_take isl_set
*dom
)
2232 isl_id
*array_id
= NULL
;
2237 if (isl_set_has_tuple_id(array
->extent
))
2238 array_id
= isl_set_get_tuple_id(array
->extent
);
2240 if (array_id
&& !isl_id_get_user(array_id
)) {
2241 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
2242 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
2244 return pet_array_free(array
);
2247 isl_id_free(array_id
);
2256 /* Project out all unnamed parameters from "set" and return the result.
2258 static __isl_give isl_set
*set_project_out_unnamed_params(
2259 __isl_take isl_set
*set
)
2263 n
= isl_set_dim(set
, isl_dim_param
);
2264 for (i
= n
- 1; i
>= 0; --i
) {
2265 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
2267 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
2273 /* Update the context with respect to an embedding into a loop
2274 * with iteration domain "dom" and induction variable "id".
2275 * "iv_map" expresses the real iterator (parameter "id") in terms
2276 * of a possibly virtual iterator (used in "dom").
2278 * If the current context is independent of "id", we don't need
2280 * Otherwise, a parameter value is invalid for the embedding if
2281 * any of the corresponding iterator values is invalid.
2282 * That is, a parameter value is valid only if all the corresponding
2283 * iterator values are valid.
2284 * We therefore compute the set of parameters
2286 * forall i in dom : valid (i)
2290 * not exists i in dom : not valid(i)
2294 * not exists i in dom \ valid(i)
2296 * Before we subtract valid(i) from dom, we first need to substitute
2297 * the real iterator for the virtual iterator.
2299 * If there are any unnamed parameters in "dom", then we consider
2300 * a parameter value to be valid if it is valid for any value of those
2301 * unnamed parameters. They are therefore projected out at the end.
2303 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
2304 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
2305 __isl_keep isl_id
*id
)
2310 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
2314 context
= isl_set_from_params(context
);
2315 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
2316 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
2317 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
2318 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
2319 context
= isl_set_preimage_multi_aff(context
, ma
);
2320 context
= isl_set_subtract(isl_set_copy(dom
), context
);
2321 context
= isl_set_params(context
);
2322 context
= isl_set_complement(context
);
2323 context
= set_project_out_unnamed_params(context
);
2327 /* Update the implication with respect to an embedding into a loop
2328 * with iteration domain "dom".
2330 * Since embed_access extends virtual arrays along with the domain
2331 * of the access, we need to do the same with domain and range
2332 * of the implication. Since the original implication is only valid
2333 * within a given iteration of the loop, the extended implication
2334 * maps the extra array dimension corresponding to the extra loop
2337 static struct pet_implication
*pet_implication_embed(
2338 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
2346 map
= isl_set_identity(dom
);
2347 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
2348 map
= isl_map_flat_product(map
, implication
->extension
);
2349 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
2350 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
2351 implication
->extension
= map
;
2352 if (!implication
->extension
)
2353 return pet_implication_free(implication
);
2361 /* Embed all statements and arrays in "scop" in an extra outer loop
2362 * with iteration domain "dom" and schedule "sched".
2363 * "id" represents the induction variable of the loop.
2364 * "iv_map" maps a possibly virtual iterator to the real iterator.
2365 * That is, it expresses the iterator that some of the parameters in "scop"
2366 * may refer to in terms of the iterator used in "dom" and
2367 * the domain of "sched".
2369 * Any skip conditions within the loop have no effect outside of the loop.
2370 * The caller is responsible for making sure skip[pet_skip_later] has been
2371 * taken into account.
2373 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
2374 __isl_take isl_aff
*sched
, __isl_take isl_aff
*iv_map
,
2375 __isl_take isl_id
*id
)
2380 sched_map
= isl_map_from_aff(sched
);
2385 pet_scop_reset_skip(scop
, pet_skip_now
);
2386 pet_scop_reset_skip(scop
, pet_skip_later
);
2388 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
2392 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2393 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
2394 isl_set_copy(dom
), isl_map_copy(sched_map
),
2395 isl_aff_copy(iv_map
), isl_id_copy(id
));
2396 if (!scop
->stmts
[i
])
2400 for (i
= 0; i
< scop
->n_array
; ++i
) {
2401 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
2403 if (!scop
->arrays
[i
])
2407 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2408 scop
->implications
[i
] =
2409 pet_implication_embed(scop
->implications
[i
],
2411 if (!scop
->implications
[i
])
2416 isl_map_free(sched_map
);
2417 isl_aff_free(iv_map
);
2422 isl_map_free(sched_map
);
2423 isl_aff_free(iv_map
);
2425 return pet_scop_free(scop
);
2428 /* Add extra conditions on the parameters to the iteration domain of "stmt".
2430 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
2431 __isl_take isl_set
*cond
)
2436 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
2441 return pet_stmt_free(stmt
);
2444 /* Add extra conditions to scop->skip[type].
2446 * The new skip condition only holds if it held before
2447 * and the condition is true. It does not hold if it did not hold
2448 * before or the condition is false.
2450 * The skip condition is assumed to be an affine expression.
2452 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
2453 enum pet_skip type
, __isl_keep isl_set
*cond
)
2455 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2461 if (!ext
->skip
[type
])
2464 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2465 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2466 isl_error_internal
, "can only restrict affine skips",
2467 return pet_scop_free(scop
));
2469 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2470 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2471 cond
= isl_set_copy(cond
);
2472 cond
= isl_set_from_params(cond
);
2473 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2474 skip
= indicator_function(cond
, dom
);
2475 isl_multi_pw_aff_free(ext
->skip
[type
]);
2476 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2477 if (!ext
->skip
[type
])
2478 return pet_scop_free(scop
);
2483 /* Add extra conditions on the parameters to all iteration domains
2484 * and skip conditions.
2486 * A parameter value is valid for the result if it was valid
2487 * for the original scop and satisfies "cond" or if it does
2488 * not satisfy "cond" as in this case the scop is not executed
2489 * and the original constraints on the parameters are irrelevant.
2491 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2492 __isl_take isl_set
*cond
)
2496 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2497 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2502 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2503 scop
->context
= isl_set_union(scop
->context
,
2504 isl_set_complement(isl_set_copy(cond
)));
2505 scop
->context
= isl_set_coalesce(scop
->context
);
2506 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2510 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2511 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2512 isl_set_copy(cond
));
2513 if (!scop
->stmts
[i
])
2521 return pet_scop_free(scop
);
2524 /* Construct a function that (upon precomposition) inserts
2525 * a filter value with name "id" and value "satisfied"
2526 * in the list of filter values embedded in the set space "space".
2528 * If "space" does not contain any filter values yet, we first create
2529 * a function that inserts 0 filter values, i.e.,
2531 * [space -> []] -> space
2533 * We can now assume that space is of the form [dom -> [filters]]
2534 * We construct an identity mapping on dom and a mapping on filters
2535 * that (upon precomposition) inserts the new filter
2538 * [satisfied, filters] -> [filters]
2540 * and then compute the cross product
2542 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2544 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2545 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2549 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2552 if (isl_space_is_wrapping(space
)) {
2553 space2
= isl_space_map_from_set(isl_space_copy(space
));
2554 ma
= isl_multi_aff_identity(space2
);
2555 space
= isl_space_unwrap(space
);
2557 space
= isl_space_from_domain(space
);
2558 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2561 space2
= isl_space_domain(isl_space_copy(space
));
2562 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2563 space
= isl_space_range(space
);
2564 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2565 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2566 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2567 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2568 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2570 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2571 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2576 /* Insert an argument expression corresponding to "test" in front
2577 * of the list of arguments described by *n_arg and *args.
2579 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2580 __isl_keep isl_multi_pw_aff
*test
)
2583 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
2589 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2593 struct pet_expr
**ext
;
2594 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2597 for (i
= 0; i
< *n_arg
; ++i
)
2598 ext
[1 + i
] = (*args
)[i
];
2603 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2610 /* Make the expression "expr" depend on the value of "test"
2611 * being equal to "satisfied".
2613 * If "test" is an affine expression, we simply add the conditions
2614 * on the expression having the value "satisfied" to all access relations
2615 * and index expressions.
2617 * Otherwise, we add a filter to "expr" (which is then assumed to be
2618 * an access expression) corresponding to "test" being equal to "satisfied".
2620 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2621 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2626 isl_pw_multi_aff
*pma
;
2631 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2635 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2636 isl_multi_pw_aff_free(test
);
2638 cond
= isl_pw_aff_non_zero_set(pa
);
2640 cond
= isl_pw_aff_zero_set(pa
);
2641 return pet_expr_restrict(expr
, isl_set_params(cond
));
2644 ctx
= isl_multi_pw_aff_get_ctx(test
);
2645 if (expr
->type
!= pet_expr_access
)
2646 isl_die(ctx
, isl_error_invalid
,
2647 "can only filter access expressions", goto error
);
2649 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2650 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2651 pma
= insert_filter_pma(space
, id
, satisfied
);
2653 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2655 isl_pw_multi_aff_copy(pma
));
2656 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2657 expr
->acc
.index
, pma
);
2658 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2661 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2664 isl_multi_pw_aff_free(test
);
2667 isl_multi_pw_aff_free(test
);
2668 return pet_expr_free(expr
);
2671 /* Look through the applications in "scop" for any that can be
2672 * applied to the filter expressed by "map" and "satisified".
2673 * If there is any, then apply it to "map" and return the result.
2674 * Otherwise, return "map".
2675 * "id" is the identifier of the virtual array.
2677 * We only introduce at most one implication for any given virtual array,
2678 * so we can apply the implication and return as soon as we find one.
2680 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2681 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2685 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2686 struct pet_implication
*pi
= scop
->implications
[i
];
2689 if (pi
->satisfied
!= satisfied
)
2691 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2696 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2702 /* Is the filter expressed by "test" and "satisfied" implied
2703 * by filter "pos" on "domain", with filter "expr", taking into
2704 * account the implications of "scop"?
2706 * For filter on domain implying that expressed by "test" and "satisfied",
2707 * the filter needs to be an access to the same (virtual) array as "test" and
2708 * the filter value needs to be equal to "satisfied".
2709 * Moreover, the filter access relation, possibly extended by
2710 * the implications in "scop" needs to contain "test".
2712 static int implies_filter(struct pet_scop
*scop
,
2713 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2714 __isl_keep isl_map
*test
, int satisfied
)
2716 isl_id
*test_id
, *arg_id
;
2723 if (expr
->type
!= pet_expr_access
)
2725 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2726 arg_id
= pet_expr_access_get_id(expr
);
2727 isl_id_free(arg_id
);
2728 isl_id_free(test_id
);
2729 if (test_id
!= arg_id
)
2731 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2732 is_int
= isl_val_is_int(val
);
2734 s
= isl_val_get_num_si(val
);
2743 implied
= isl_map_copy(expr
->acc
.access
);
2744 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2745 is_subset
= isl_map_is_subset(test
, implied
);
2746 isl_map_free(implied
);
2751 /* Is the filter expressed by "test" and "satisfied" implied
2752 * by any of the filters on the domain of "stmt", taking into
2753 * account the implications of "scop"?
2755 static int filter_implied(struct pet_scop
*scop
,
2756 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2764 if (!scop
|| !stmt
|| !test
)
2766 if (scop
->n_implication
== 0)
2768 if (stmt
->n_arg
== 0)
2771 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2772 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2775 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2776 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2777 test_map
, satisfied
);
2778 if (implied
< 0 || implied
)
2782 isl_map_free(test_map
);
2783 isl_map_free(domain
);
2787 /* Make the statement "stmt" depend on the value of "test"
2788 * being equal to "satisfied" by adjusting stmt->domain.
2790 * The domain of "test" corresponds to the (zero or more) outer dimensions
2791 * of the iteration domain.
2793 * We first extend "test" to apply to the entire iteration domain and
2794 * then check if the filter that we are about to add is implied
2795 * by any of the current filters, possibly taking into account
2796 * the implications in "scop". If so, we leave "stmt" untouched and return.
2798 * Otherwise, we insert an argument corresponding to a read to "test"
2799 * from the iteration domain of "stmt" in front of the list of arguments.
2800 * We also insert a corresponding output dimension in the wrapped
2801 * map contained in stmt->domain, with value set to "satisfied".
2803 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2804 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2810 isl_pw_multi_aff
*pma
;
2811 isl_multi_aff
*add_dom
;
2813 isl_local_space
*ls
;
2819 space
= pet_stmt_get_space(stmt
);
2820 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2821 space
= isl_space_from_domain(space
);
2822 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2823 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2824 ls
= isl_local_space_from_space(isl_space_domain(space
));
2825 for (i
= 0; i
< n_test_dom
; ++i
) {
2827 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2829 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2831 isl_local_space_free(ls
);
2832 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2834 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2838 isl_multi_pw_aff_free(test
);
2842 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2843 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2844 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2846 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2849 isl_multi_pw_aff_free(test
);
2852 isl_multi_pw_aff_free(test
);
2853 return pet_stmt_free(stmt
);
2856 /* Does "scop" have a skip condition of the given "type"?
2858 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2860 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2864 return ext
->skip
[type
] != NULL
;
2867 /* Does "scop" have a skip condition of the given "type" that
2868 * is an affine expression?
2870 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2872 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2876 if (!ext
->skip
[type
])
2878 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2881 /* Does "scop" have a skip condition of the given "type" that
2882 * is not an affine expression?
2884 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2886 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2891 if (!ext
->skip
[type
])
2893 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2899 /* Does "scop" have a skip condition of the given "type" that
2900 * is affine and holds on the entire domain?
2902 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2904 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2910 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2911 if (is_aff
< 0 || !is_aff
)
2914 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2915 set
= isl_pw_aff_non_zero_set(pa
);
2916 is_univ
= isl_set_plain_is_universe(set
);
2922 /* Replace scop->skip[type] by "skip".
2924 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2925 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2927 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2932 isl_multi_pw_aff_free(ext
->skip
[type
]);
2933 ext
->skip
[type
] = skip
;
2937 isl_multi_pw_aff_free(skip
);
2938 return pet_scop_free(scop
);
2941 /* Return a copy of scop->skip[type].
2943 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2946 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2951 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2954 /* Assuming scop->skip[type] is an affine expression,
2955 * return the constraints on the parameters for which the skip condition
2958 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2961 isl_multi_pw_aff
*skip
;
2964 skip
= pet_scop_get_skip(scop
, type
);
2965 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2966 isl_multi_pw_aff_free(skip
);
2967 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2970 /* Return the identifier of the variable that is accessed by
2971 * the skip condition of the given type.
2973 * The skip condition is assumed not to be an affine condition.
2975 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2978 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2983 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2986 /* Return an access pet_expr corresponding to the skip condition
2987 * of the given type.
2989 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2992 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2995 /* Drop the the skip condition scop->skip[type].
2997 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2999 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3004 isl_multi_pw_aff_free(ext
->skip
[type
]);
3005 ext
->skip
[type
] = NULL
;
3008 /* Make the skip condition (if any) depend on the value of "test" being
3009 * equal to "satisfied".
3011 * We only support the case where the original skip condition is universal,
3012 * i.e., where skipping is unconditional, and where satisfied == 1.
3013 * In this case, the skip condition is changed to skip only when
3014 * "test" is equal to one.
3016 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
3017 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
3023 if (!pet_scop_has_skip(scop
, type
))
3027 is_univ
= pet_scop_has_universal_skip(scop
, type
);
3029 return pet_scop_free(scop
);
3030 if (satisfied
&& is_univ
) {
3031 isl_multi_pw_aff
*skip
;
3032 skip
= isl_multi_pw_aff_copy(test
);
3033 scop
= pet_scop_set_skip(scop
, type
, skip
);
3037 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
3038 "skip expression cannot be filtered",
3039 return pet_scop_free(scop
));
3045 /* Make all statements in "scop" depend on the value of "test"
3046 * being equal to "satisfied" by adjusting their domains.
3048 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
3049 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
3053 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
3054 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
3059 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3060 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
3061 isl_multi_pw_aff_copy(test
), satisfied
);
3062 if (!scop
->stmts
[i
])
3066 isl_multi_pw_aff_free(test
);
3069 isl_multi_pw_aff_free(test
);
3070 return pet_scop_free(scop
);
3073 /* Add all parameters in "expr" to "space" and return the result.
3075 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
3076 __isl_take isl_space
*space
)
3082 for (i
= 0; i
< expr
->n_arg
; ++i
)
3083 space
= expr_collect_params(expr
->args
[i
], space
);
3085 if (expr
->type
== pet_expr_access
)
3086 space
= isl_space_align_params(space
,
3087 isl_map_get_space(expr
->acc
.access
));
3091 pet_expr_free(expr
);
3092 return isl_space_free(space
);
3095 /* Add all parameters in "stmt" to "space" and return the result.
3097 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
3098 __isl_take isl_space
*space
)
3103 return isl_space_free(space
);
3105 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
3106 space
= isl_space_align_params(space
,
3107 isl_map_get_space(stmt
->schedule
));
3108 for (i
= 0; i
< stmt
->n_arg
; ++i
)
3109 space
= expr_collect_params(stmt
->args
[i
], space
);
3110 space
= expr_collect_params(stmt
->body
, space
);
3115 /* Add all parameters in "array" to "space" and return the result.
3117 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
3118 __isl_take isl_space
*space
)
3121 return isl_space_free(space
);
3123 space
= isl_space_align_params(space
,
3124 isl_set_get_space(array
->context
));
3125 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
3130 /* Add all parameters in "scop" to "space" and return the result.
3132 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
3133 __isl_take isl_space
*space
)
3138 return isl_space_free(space
);
3140 for (i
= 0; i
< scop
->n_array
; ++i
)
3141 space
= array_collect_params(scop
->arrays
[i
], space
);
3143 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3144 space
= stmt_collect_params(scop
->stmts
[i
], space
);
3149 /* Add all parameters in "space" to all access relations and index expressions
3152 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
3153 __isl_take isl_space
*space
)
3160 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3162 expr_propagate_params(expr
->args
[i
],
3163 isl_space_copy(space
));
3168 if (expr
->type
== pet_expr_access
) {
3169 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
3170 isl_space_copy(space
));
3171 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
3172 isl_space_copy(space
));
3173 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3177 isl_space_free(space
);
3180 isl_space_free(space
);
3181 return pet_expr_free(expr
);
3184 /* Add all parameters in "space" to the domain, schedule and
3185 * all access relations in "stmt".
3187 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
3188 __isl_take isl_space
*space
)
3195 stmt
->domain
= isl_set_align_params(stmt
->domain
,
3196 isl_space_copy(space
));
3197 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
3198 isl_space_copy(space
));
3200 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3201 stmt
->args
[i
] = expr_propagate_params(stmt
->args
[i
],
3202 isl_space_copy(space
));
3206 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(space
));
3208 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3211 isl_space_free(space
);
3214 isl_space_free(space
);
3215 return pet_stmt_free(stmt
);
3218 /* Add all parameters in "space" to "array".
3220 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
3221 __isl_take isl_space
*space
)
3226 array
->context
= isl_set_align_params(array
->context
,
3227 isl_space_copy(space
));
3228 array
->extent
= isl_set_align_params(array
->extent
,
3229 isl_space_copy(space
));
3230 if (array
->value_bounds
) {
3231 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
3232 isl_space_copy(space
));
3233 if (!array
->value_bounds
)
3237 if (!array
->context
|| !array
->extent
)
3240 isl_space_free(space
);
3243 isl_space_free(space
);
3244 return pet_array_free(array
);
3247 /* Add all parameters in "space" to "scop".
3249 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
3250 __isl_take isl_space
*space
)
3257 for (i
= 0; i
< scop
->n_array
; ++i
) {
3258 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
3259 isl_space_copy(space
));
3260 if (!scop
->arrays
[i
])
3264 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3265 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
3266 isl_space_copy(space
));
3267 if (!scop
->stmts
[i
])
3271 isl_space_free(space
);
3274 isl_space_free(space
);
3275 return pet_scop_free(scop
);
3278 /* Update all isl_sets and isl_maps in "scop" such that they all
3279 * have the same parameters.
3281 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
3288 space
= isl_set_get_space(scop
->context
);
3289 space
= scop_collect_params(scop
, space
);
3291 scop
->context
= isl_set_align_params(scop
->context
,
3292 isl_space_copy(space
));
3293 scop
= scop_propagate_params(scop
, space
);
3295 if (scop
&& !scop
->context
)
3296 return pet_scop_free(scop
);
3301 /* Check if the given index expression accesses a (0D) array that corresponds
3302 * to one of the parameters in "dim". If so, replace the array access
3303 * by an access to the set of integers with as index (and value)
3306 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
3307 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
3309 isl_local_space
*ls
;
3310 isl_id
*array_id
= NULL
;
3314 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
3315 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
3316 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3318 isl_space_free(space
);
3321 isl_id_free(array_id
);
3325 space
= isl_multi_pw_aff_get_domain_space(index
);
3326 isl_multi_pw_aff_free(index
);
3328 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3330 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
3331 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
3334 isl_id_free(array_id
);
3336 ls
= isl_local_space_from_space(space
);
3337 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
3338 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
3343 /* Check if the given access relation accesses a (0D) array that corresponds
3344 * to one of the parameters in "dim". If so, replace the array access
3345 * by an access to the set of integers with as index (and value)
3348 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
3349 __isl_take isl_space
*dim
)
3351 isl_id
*array_id
= NULL
;
3354 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
3355 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
3356 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
3358 isl_space_free(dim
);
3361 isl_id_free(array_id
);
3365 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
3367 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
3368 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
3371 isl_id_free(array_id
);
3373 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
3374 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
3379 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3380 * in "dim" by a value equal to the corresponding parameter.
3382 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
3383 __isl_take isl_space
*dim
)
3390 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3392 expr_detect_parameter_accesses(expr
->args
[i
],
3393 isl_space_copy(dim
));
3398 if (expr
->type
== pet_expr_access
) {
3399 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
3400 isl_space_copy(dim
));
3401 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
3402 isl_space_copy(dim
));
3403 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3407 isl_space_free(dim
);
3410 isl_space_free(dim
);
3411 return pet_expr_free(expr
);
3414 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3415 * in "dim" by a value equal to the corresponding parameter.
3417 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
3418 __isl_take isl_space
*dim
)
3423 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
3424 isl_space_copy(dim
));
3426 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3429 isl_space_free(dim
);
3432 isl_space_free(dim
);
3433 return pet_stmt_free(stmt
);
3436 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3437 * in "dim" by a value equal to the corresponding parameter.
3439 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
3440 __isl_take isl_space
*dim
)
3447 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3448 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
3449 isl_space_copy(dim
));
3450 if (!scop
->stmts
[i
])
3454 isl_space_free(dim
);
3457 isl_space_free(dim
);
3458 return pet_scop_free(scop
);
3461 /* Replace all accesses to (0D) arrays that correspond to any of
3462 * the parameters used in "scop" by a value equal
3463 * to the corresponding parameter.
3465 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
3472 dim
= isl_set_get_space(scop
->context
);
3473 dim
= scop_collect_params(scop
, dim
);
3475 scop
= scop_detect_parameter_accesses(scop
, dim
);
3480 /* Return the relation mapping domain iterations to all possibly
3481 * accessed data elements.
3482 * In particular, take the access relation and project out the values
3483 * of the arguments, if any.
3485 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
3493 if (expr
->type
!= pet_expr_access
)
3496 access
= isl_map_copy(expr
->acc
.access
);
3497 if (expr
->n_arg
== 0)
3500 space
= isl_space_domain(isl_map_get_space(access
));
3501 map
= isl_map_universe(isl_space_unwrap(space
));
3502 map
= isl_map_domain_map(map
);
3503 access
= isl_map_apply_domain(access
, map
);
3508 /* Return the relation mapping domain iterations to all possibly
3509 * accessed data elements, with its domain tagged with the reference
3512 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
3513 struct pet_expr
*expr
)
3520 access
= pet_expr_access_get_may_access(expr
);
3521 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3526 /* Add the access relation of the access expression "expr" to "accesses" and
3527 * return the result.
3528 * The domain of the access relation is intersected with "domain".
3529 * If "tag" is set, then the access relation is tagged with
3530 * the corresponding reference identifier.
3532 static __isl_give isl_union_map
*expr_collect_access(struct pet_expr
*expr
,
3533 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3537 access
= pet_expr_access_get_may_access(expr
);
3538 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
3540 access
= tag_access(access
, isl_id_copy(expr
->acc
.ref_id
));
3541 return isl_union_map_add_map(accesses
, access
);
3544 /* Add all read access relations (if "read" is set) and/or all write
3545 * access relations (if "write" is set) to "accesses" and return the result.
3546 * The domains of the access relations are intersected with "domain".
3547 * If "tag" is set, then the access relations are tagged with
3548 * the corresponding reference identifiers.
3550 * If "must" is set, then we only add the accesses that are definitely
3551 * performed. Otherwise, we add all potential accesses.
3552 * In particular, if the access has any arguments, then if "must" is
3553 * set we currently skip the access completely. If "must" is not set,
3554 * we project out the values of the access arguments.
3556 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
3557 int read
, int write
, int must
, int tag
,
3558 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
3565 return isl_union_map_free(accesses
);
3567 for (i
= 0; i
< expr
->n_arg
; ++i
)
3568 accesses
= expr_collect_accesses(expr
->args
[i
],
3569 read
, write
, must
, tag
, accesses
, domain
);
3571 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
3572 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
3573 (!must
|| expr
->n_arg
== 0)) {
3574 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
3580 /* Collect and return all read access relations (if "read" is set)
3581 * and/or all write access relations (if "write" is set) in "stmt".
3582 * If "tag" is set, then the access relations are tagged with
3583 * the corresponding reference identifiers.
3584 * If "kill" is set, then "stmt" is a kill statement and we simply
3585 * add the argument of the kill operation.
3587 * If "must" is set, then we only add the accesses that are definitely
3588 * performed. Otherwise, we add all potential accesses.
3589 * In particular, if the statement has any arguments, then if "must" is
3590 * set we currently skip the statement completely. If "must" is not set,
3591 * we project out the values of the statement arguments.
3593 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
3594 int read
, int write
, int kill
, int must
, int tag
,
3595 __isl_take isl_space
*dim
)
3597 isl_union_map
*accesses
;
3603 accesses
= isl_union_map_empty(dim
);
3605 if (must
&& stmt
->n_arg
> 0)
3608 domain
= isl_set_copy(stmt
->domain
);
3609 if (isl_set_is_wrapping(domain
))
3610 domain
= isl_map_domain(isl_set_unwrap(domain
));
3613 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
3616 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
3617 must
, tag
, accesses
, domain
);
3618 isl_set_free(domain
);
3623 /* Is "stmt" an assignment statement?
3625 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
3629 if (stmt
->body
->type
!= pet_expr_op
)
3631 return stmt
->body
->op
== pet_op_assign
;
3634 /* Is "stmt" a kill statement?
3636 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
3640 if (stmt
->body
->type
!= pet_expr_op
)
3642 return stmt
->body
->op
== pet_op_kill
;
3645 /* Is "stmt" an assume statement?
3647 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
3649 if (stmt
->body
->type
!= pet_expr_op
)
3651 return stmt
->body
->op
== pet_op_assume
;
3654 /* Compute a mapping from all arrays (of structs) in scop
3655 * to their innermost arrays.
3657 * In particular, for each array of a primitive type, the result
3658 * contains the identity mapping on that array.
3659 * For each array involving member accesses, the result
3660 * contains a mapping from the elements of any intermediate array of structs
3661 * to all corresponding elements of the innermost nested arrays.
3663 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
3666 isl_union_map
*to_inner
;
3668 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3670 for (i
= 0; i
< scop
->n_array
; ++i
) {
3671 struct pet_array
*array
= scop
->arrays
[i
];
3673 isl_map
*map
, *gist
;
3675 if (array
->element_is_record
)
3678 map
= isl_set_identity(isl_set_copy(array
->extent
));
3680 set
= isl_map_domain(isl_map_copy(map
));
3681 gist
= isl_map_copy(map
);
3682 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3683 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3685 while (set
&& isl_set_is_wrapping(set
)) {
3689 id
= isl_set_get_tuple_id(set
);
3690 wrapped
= isl_set_unwrap(set
);
3691 wrapped
= isl_map_domain_map(wrapped
);
3692 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
3693 map
= isl_map_apply_domain(map
, wrapped
);
3694 set
= isl_map_domain(isl_map_copy(map
));
3695 gist
= isl_map_copy(map
);
3696 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
3697 to_inner
= isl_union_map_add_map(to_inner
, gist
);
3707 /* Collect and return all read access relations (if "read" is set)
3708 * and/or all write access relations (if "write" is set) in "scop".
3709 * If "kill" is set, then we only add the arguments of kill operations.
3710 * If "must" is set, then we only add the accesses that are definitely
3711 * performed. Otherwise, we add all potential accesses.
3712 * If "tag" is set, then the access relations are tagged with
3713 * the corresponding reference identifiers.
3714 * For accesses to structures, the returned access relation accesses
3715 * all individual fields in the structures.
3717 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3718 int read
, int write
, int kill
, int must
, int tag
)
3721 isl_union_map
*accesses
;
3722 isl_union_set
*arrays
;
3723 isl_union_map
*to_inner
;
3728 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3730 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3731 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3732 isl_union_map
*accesses_i
;
3735 if (kill
&& !pet_stmt_is_kill(stmt
))
3738 space
= isl_set_get_space(scop
->context
);
3739 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
3741 accesses
= isl_union_map_union(accesses
, accesses_i
);
3744 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
3745 for (i
= 0; i
< scop
->n_array
; ++i
) {
3746 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
3747 arrays
= isl_union_set_add_set(arrays
, extent
);
3749 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
3751 to_inner
= compute_to_inner(scop
);
3752 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
3757 /* Collect all potential read access relations.
3759 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
3761 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
3764 /* Collect all potential write access relations.
3766 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
3768 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
3771 /* Collect all definite write access relations.
3773 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
3775 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
3778 /* Collect all definite kill access relations.
3780 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
3782 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
3785 /* Collect all tagged potential read access relations.
3787 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
3788 struct pet_scop
*scop
)
3790 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
3793 /* Collect all tagged potential write access relations.
3795 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
3796 struct pet_scop
*scop
)
3798 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
3801 /* Collect all tagged definite write access relations.
3803 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
3804 struct pet_scop
*scop
)
3806 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
3809 /* Collect all tagged definite kill access relations.
3811 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
3812 struct pet_scop
*scop
)
3814 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
3817 /* Collect and return the union of iteration domains in "scop".
3819 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3823 isl_union_set
*domain
;
3828 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3830 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3831 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3832 domain
= isl_union_set_add_set(domain
, domain_i
);
3838 /* Collect and return the schedules of the statements in "scop".
3839 * The range is normalized to the maximal number of scheduling
3842 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3845 isl_map
*schedule_i
;
3846 isl_union_map
*schedule
;
3847 int depth
, max_depth
= 0;
3852 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3854 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3855 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3856 if (depth
> max_depth
)
3860 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3861 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3862 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3863 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3865 for (j
= depth
; j
< max_depth
; ++j
)
3866 schedule_i
= isl_map_fix_si(schedule_i
,
3868 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3874 /* Does expression "expr" write to "id"?
3876 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3881 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3882 int writes
= expr_writes(expr
->args
[i
], id
);
3883 if (writes
< 0 || writes
)
3887 if (expr
->type
!= pet_expr_access
)
3889 if (!expr
->acc
.write
)
3891 if (pet_expr_is_affine(expr
))
3894 write_id
= pet_expr_access_get_id(expr
);
3895 isl_id_free(write_id
);
3900 return write_id
== id
;
3903 /* Does statement "stmt" write to "id"?
3905 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3907 return expr_writes(stmt
->body
, id
);
3910 /* Is there any write access in "scop" that accesses "id"?
3912 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3919 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3920 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3921 if (writes
< 0 || writes
)
3928 /* Add a reference identifier to access expression "expr".
3929 * "user" points to an integer that contains the sequence number
3930 * of the next reference.
3932 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3941 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3942 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3943 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3944 if (!expr
->acc
.ref_id
)
3945 return pet_expr_free(expr
);
3950 /* Add a reference identifier to all access expressions in "stmt".
3951 * "n_ref" points to an integer that contains the sequence number
3952 * of the next reference.
3954 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3961 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3962 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3963 &access_add_ref_id
, n_ref
);
3965 return pet_stmt_free(stmt
);
3968 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3970 return pet_stmt_free(stmt
);
3975 /* Add a reference identifier to all access expressions in "scop".
3977 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3986 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3987 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3988 if (!scop
->stmts
[i
])
3989 return pet_scop_free(scop
);
3995 /* Reset the user pointer on all parameter ids in "array".
3997 static struct pet_array
*array_anonymize(struct pet_array
*array
)
4002 array
->context
= isl_set_reset_user(array
->context
);
4003 array
->extent
= isl_set_reset_user(array
->extent
);
4004 if (!array
->context
|| !array
->extent
)
4005 return pet_array_free(array
);
4010 /* Reset the user pointer on all parameter and tuple ids in
4011 * the access relation and the index expressions
4012 * of the access expression "expr".
4014 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
4016 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
4017 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
4018 if (!expr
->acc
.access
|| !expr
->acc
.index
)
4019 return pet_expr_free(expr
);
4024 /* Reset the user pointer on all parameter and tuple ids in "stmt".
4026 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
4035 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
4036 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
4037 if (!stmt
->domain
|| !stmt
->schedule
)
4038 return pet_stmt_free(stmt
);
4040 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
4041 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
4042 &access_anonymize
, NULL
);
4044 return pet_stmt_free(stmt
);
4047 stmt
->body
= pet_expr_map_access(stmt
->body
,
4048 &access_anonymize
, NULL
);
4050 return pet_stmt_free(stmt
);
4055 /* Reset the user pointer on the tuple ids and all parameter ids
4058 static struct pet_implication
*implication_anonymize(
4059 struct pet_implication
*implication
)
4064 implication
->extension
= isl_map_reset_user(implication
->extension
);
4065 if (!implication
->extension
)
4066 return pet_implication_free(implication
);
4071 /* Reset the user pointer on all parameter and tuple ids in "scop".
4073 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
4080 scop
->context
= isl_set_reset_user(scop
->context
);
4081 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
4082 if (!scop
->context
|| !scop
->context_value
)
4083 return pet_scop_free(scop
);
4085 for (i
= 0; i
< scop
->n_array
; ++i
) {
4086 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
4087 if (!scop
->arrays
[i
])
4088 return pet_scop_free(scop
);
4091 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4092 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
4093 if (!scop
->stmts
[i
])
4094 return pet_scop_free(scop
);
4097 for (i
= 0; i
< scop
->n_implication
; ++i
) {
4098 scop
->implications
[i
] =
4099 implication_anonymize(scop
->implications
[i
]);
4100 if (!scop
->implications
[i
])
4101 return pet_scop_free(scop
);
4107 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
4108 * then intersect the range of "map" with the valid set of values.
4110 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
4111 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
4116 isl_ctx
*ctx
= isl_map_get_ctx(map
);
4118 id
= pet_expr_access_get_id(arg
);
4119 space
= isl_space_alloc(ctx
, 0, 0, 1);
4120 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
4121 vb
= isl_union_map_extract_map(value_bounds
, space
);
4122 if (!isl_map_plain_is_empty(vb
))
4123 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
4130 /* Given a set "domain", return a wrapped relation with the given set
4131 * as domain and a range of dimension "n_arg", where each coordinate
4132 * is either unbounded or, if the corresponding element of args is of
4133 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
4135 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
4136 unsigned n_arg
, struct pet_expr
**args
,
4137 __isl_keep isl_union_map
*value_bounds
)
4143 map
= isl_map_from_domain(domain
);
4144 space
= isl_map_get_space(map
);
4145 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
4147 for (i
= 0; i
< n_arg
; ++i
) {
4149 struct pet_expr
*arg
= args
[i
];
4151 map_i
= isl_map_universe(isl_space_copy(space
));
4152 if (arg
->type
== pet_expr_access
)
4153 map_i
= access_apply_value_bounds(map_i
, arg
,
4155 map
= isl_map_flat_range_product(map
, map_i
);
4157 isl_space_free(space
);
4159 return isl_map_wrap(map
);
4162 /* Data used in access_gist() callback.
4164 struct pet_access_gist_data
{
4166 isl_union_map
*value_bounds
;
4169 /* Given an expression "expr" of type pet_expr_access, compute
4170 * the gist of the associated access relation and index expression
4171 * with respect to data->domain and the bounds on the values of the arguments
4172 * of the expression.
4174 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
4176 struct pet_access_gist_data
*data
= user
;
4179 domain
= isl_set_copy(data
->domain
);
4180 if (expr
->n_arg
> 0)
4181 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
4182 data
->value_bounds
);
4184 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
4185 isl_set_copy(domain
));
4186 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
4187 if (!expr
->acc
.access
|| !expr
->acc
.index
)
4188 return pet_expr_free(expr
);
4193 /* Compute the gist of the iteration domain and all access relations
4194 * of "stmt" based on the constraints on the parameters specified by "context"
4195 * and the constraints on the values of nested accesses specified
4196 * by "value_bounds".
4198 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
4199 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
4203 struct pet_access_gist_data data
;
4208 data
.domain
= isl_set_copy(stmt
->domain
);
4209 data
.value_bounds
= value_bounds
;
4210 if (stmt
->n_arg
> 0)
4211 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
4213 data
.domain
= isl_set_intersect_params(data
.domain
,
4214 isl_set_copy(context
));
4216 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
4217 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
4218 &access_gist
, &data
);
4223 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
4227 isl_set_free(data
.domain
);
4229 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
4230 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
4231 if (stmt
->n_arg
> 0)
4232 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
4234 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
4236 return pet_stmt_free(stmt
);
4240 isl_set_free(data
.domain
);
4241 return pet_stmt_free(stmt
);
4244 /* Compute the gist of the extent of the array
4245 * based on the constraints on the parameters specified by "context".
4247 static struct pet_array
*array_gist(struct pet_array
*array
,
4248 __isl_keep isl_set
*context
)
4253 array
->extent
= isl_set_gist_params(array
->extent
,
4254 isl_set_copy(context
));
4256 return pet_array_free(array
);
4261 /* Compute the gist of all sets and relations in "scop"
4262 * based on the constraints on the parameters specified by "scop->context"
4263 * and the constraints on the values of nested accesses specified
4264 * by "value_bounds".
4266 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
4267 __isl_keep isl_union_map
*value_bounds
)
4274 scop
->context
= isl_set_coalesce(scop
->context
);
4276 return pet_scop_free(scop
);
4278 for (i
= 0; i
< scop
->n_array
; ++i
) {
4279 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
4280 if (!scop
->arrays
[i
])
4281 return pet_scop_free(scop
);
4284 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4285 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
4287 if (!scop
->stmts
[i
])
4288 return pet_scop_free(scop
);
4294 /* Intersect the context of "scop" with "context".
4295 * To ensure that we don't introduce any unnamed parameters in
4296 * the context of "scop", we first remove the unnamed parameters
4299 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
4300 __isl_take isl_set
*context
)
4305 context
= set_project_out_unnamed_params(context
);
4306 scop
->context
= isl_set_intersect(scop
->context
, context
);
4308 return pet_scop_free(scop
);
4312 isl_set_free(context
);
4313 return pet_scop_free(scop
);
4316 /* Drop the current context of "scop". That is, replace the context
4317 * by a universal set.
4319 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
4326 space
= isl_set_get_space(scop
->context
);
4327 isl_set_free(scop
->context
);
4328 scop
->context
= isl_set_universe(space
);
4330 return pet_scop_free(scop
);
4335 /* Append "array" to the arrays of "scop".
4337 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
4338 struct pet_array
*array
)
4341 struct pet_array
**arrays
;
4343 if (!array
|| !scop
)
4346 ctx
= isl_set_get_ctx(scop
->context
);
4347 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
4351 scop
->arrays
= arrays
;
4352 scop
->arrays
[scop
->n_array
] = array
;
4357 pet_array_free(array
);
4358 return pet_scop_free(scop
);
4361 /* Create and return an implication on filter values equal to "satisfied"
4362 * with extension "map".
4364 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
4368 struct pet_implication
*implication
;
4372 ctx
= isl_map_get_ctx(map
);
4373 implication
= isl_alloc_type(ctx
, struct pet_implication
);
4377 implication
->extension
= map
;
4378 implication
->satisfied
= satisfied
;
4386 /* Add an implication on filter values equal to "satisfied"
4387 * with extension "map" to "scop".
4389 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
4390 __isl_take isl_map
*map
, int satisfied
)
4393 struct pet_implication
*implication
;
4394 struct pet_implication
**implications
;
4396 implication
= new_implication(map
, satisfied
);
4397 if (!scop
|| !implication
)
4400 ctx
= isl_set_get_ctx(scop
->context
);
4401 implications
= isl_realloc_array(ctx
, scop
->implications
,
4402 struct pet_implication
*,
4403 scop
->n_implication
+ 1);
4406 scop
->implications
= implications
;
4407 scop
->implications
[scop
->n_implication
] = implication
;
4408 scop
->n_implication
++;
4412 pet_implication_free(implication
);
4413 return pet_scop_free(scop
);
4416 /* Given an access expression, check if it is data dependent.
4417 * If so, set *found and abort the search.
4419 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
4431 /* Does "scop" contain any data dependent accesses?
4433 * Check the body of each statement for such accesses.
4435 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
4443 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4444 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
4445 &is_data_dependent
, &found
);
4446 if (r
< 0 && !found
)
4455 /* Does "scop" contain and data dependent conditions?
4457 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
4464 for (i
= 0; i
< scop
->n_stmt
; ++i
)
4465 if (scop
->stmts
[i
]->n_arg
> 0)
4471 /* Keep track of the "input" file inside the (extended) "scop".
4473 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
4475 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4485 /* Print the original code corresponding to "scop" to printer "p".
4487 * pet_scop_print_original can only be called from
4488 * a pet_transform_C_source callback. This means that the input
4489 * file is stored in the extended scop and that the printer prints
4492 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
4493 __isl_take isl_printer
*p
)
4495 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4499 return isl_printer_free(p
);
4502 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
4503 "no input file stored in scop",
4504 return isl_printer_free(p
));
4506 output
= isl_printer_get_file(p
);
4508 return isl_printer_free(p
);
4510 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
4511 return isl_printer_free(p
);