2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
41 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
43 static char *type_str
[] = {
44 [pet_expr_access
] = "access",
45 [pet_expr_call
] = "call",
46 [pet_expr_cast
] = "cast",
47 [pet_expr_double
] = "double",
48 [pet_expr_unary
] = "unary",
49 [pet_expr_binary
] = "binary",
50 [pet_expr_ternary
] = "ternary"
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
] = "=",
69 [pet_op_post_inc
] = "++",
70 [pet_op_post_dec
] = "--",
71 [pet_op_pre_inc
] = "++",
72 [pet_op_pre_dec
] = "--",
73 [pet_op_address_of
] = "&",
74 [pet_op_kill
] = "kill"
77 /* pet_scop with extra information that is only used during parsing.
79 * In particular, we keep track of conditions under which we want
80 * to skip the rest of the current loop iteration (skip[pet_skip_now])
81 * and of conditions under which we want to skip subsequent
82 * loop iterations (skip[pet_skip_later]).
84 * The conditions are represented as index expressions defined
85 * over a zero-dimensiona domain. The index expression is either
86 * a boolean affine expression or an access to a variable, which
87 * is assumed to attain values zero and one. The condition holds
88 * if the variable has value one or if the affine expression
89 * has value one (typically for only part of the parameter space).
91 * A missing condition (skip[type] == NULL) means that we don't want
97 isl_multi_pw_aff
*skip
[2];
100 const char *pet_op_str(enum pet_op_type op
)
105 int pet_op_is_inc_dec(enum pet_op_type op
)
107 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
108 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
111 const char *pet_type_str(enum pet_expr_type type
)
113 return type_str
[type
];
116 enum pet_op_type
pet_str_op(const char *str
)
120 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
121 if (!strcmp(op_str
[i
], str
))
127 enum pet_expr_type
pet_str_type(const char *str
)
131 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
132 if (!strcmp(type_str
[i
], str
))
138 /* Construct a pet_expr from an access relation.
139 * By default, it is considered to be a read access.
141 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
143 isl_ctx
*ctx
= isl_map_get_ctx(access
);
144 struct pet_expr
*expr
;
148 expr
= isl_calloc_type(ctx
, struct pet_expr
);
152 expr
->type
= pet_expr_access
;
153 expr
->acc
.access
= access
;
159 isl_map_free(access
);
163 /* Construct an access pet_expr from an index expression.
164 * By default, the access is considered to be a read access.
166 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
170 access
= isl_map_from_multi_pw_aff(index
);
171 return pet_expr_from_access(access
);
174 /* Construct an access pet_expr from an index expression and
175 * the depth of the accessed array.
176 * By default, the access is considered to be a read access.
178 * If the number of indices is smaller than the depth of the array,
179 * then we assume that all elements of the remaining dimensions
182 struct pet_expr
*pet_expr_from_index_and_depth(
183 __isl_take isl_multi_pw_aff
*index
, int depth
)
189 access
= isl_map_from_multi_pw_aff(index
);
192 dim
= isl_map_dim(access
, isl_dim_out
);
194 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
195 "number of indices greater than depth",
196 access
= isl_map_free(access
));
198 return pet_expr_from_access(access
);
200 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
201 access
= isl_map_add_dims(access
, isl_dim_out
, depth
- dim
);
202 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
204 return pet_expr_from_access(access
);
207 /* Construct a pet_expr that kills the elements specified by "access".
209 struct pet_expr
*pet_expr_kill_from_access(__isl_take isl_map
*access
)
212 struct pet_expr
*expr
;
214 ctx
= isl_map_get_ctx(access
);
215 expr
= pet_expr_from_access(access
);
219 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
222 /* Construct a pet_expr that kills the elements specified by
223 * the index expression "index" and the access relation "access".
225 * We currently ignore "index".
227 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
228 __isl_take isl_multi_pw_aff
*index
)
230 if (!access
|| !index
)
232 isl_multi_pw_aff_free(index
);
233 return pet_expr_kill_from_access(access
);
235 isl_map_free(access
);
236 isl_multi_pw_aff_free(index
);
240 /* Construct a unary pet_expr that performs "op" on "arg".
242 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
243 struct pet_expr
*arg
)
245 struct pet_expr
*expr
;
249 expr
= isl_alloc_type(ctx
, struct pet_expr
);
253 expr
->type
= pet_expr_unary
;
256 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
259 expr
->args
[pet_un_arg
] = arg
;
267 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
269 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
270 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
272 struct pet_expr
*expr
;
276 expr
= isl_alloc_type(ctx
, struct pet_expr
);
280 expr
->type
= pet_expr_binary
;
283 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
286 expr
->args
[pet_bin_lhs
] = lhs
;
287 expr
->args
[pet_bin_rhs
] = rhs
;
296 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
298 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
299 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
301 struct pet_expr
*expr
;
303 if (!cond
|| !lhs
|| !rhs
)
305 expr
= isl_alloc_type(ctx
, struct pet_expr
);
309 expr
->type
= pet_expr_ternary
;
311 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
314 expr
->args
[pet_ter_cond
] = cond
;
315 expr
->args
[pet_ter_true
] = lhs
;
316 expr
->args
[pet_ter_false
] = rhs
;
326 /* Construct a call pet_expr that calls function "name" with "n_arg"
327 * arguments. The caller is responsible for filling in the arguments.
329 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
332 struct pet_expr
*expr
;
334 expr
= isl_alloc_type(ctx
, struct pet_expr
);
338 expr
->type
= pet_expr_call
;
340 expr
->name
= strdup(name
);
341 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
342 if (!expr
->name
|| !expr
->args
)
343 return pet_expr_free(expr
);
348 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
350 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
351 struct pet_expr
*arg
)
353 struct pet_expr
*expr
;
358 expr
= isl_alloc_type(ctx
, struct pet_expr
);
362 expr
->type
= pet_expr_cast
;
364 expr
->type_name
= strdup(type_name
);
365 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
366 if (!expr
->type_name
|| !expr
->args
)
378 /* Construct a pet_expr that represents the double "d".
380 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
382 struct pet_expr
*expr
;
384 expr
= isl_calloc_type(ctx
, struct pet_expr
);
388 expr
->type
= pet_expr_double
;
390 expr
->d
.s
= strdup(s
);
392 return pet_expr_free(expr
);
397 void *pet_expr_free(struct pet_expr
*expr
)
404 for (i
= 0; i
< expr
->n_arg
; ++i
)
405 pet_expr_free(expr
->args
[i
]);
408 switch (expr
->type
) {
409 case pet_expr_access
:
410 isl_id_free(expr
->acc
.ref_id
);
411 isl_map_free(expr
->acc
.access
);
417 free(expr
->type_name
);
419 case pet_expr_double
:
423 case pet_expr_binary
:
424 case pet_expr_ternary
:
432 static void expr_dump(struct pet_expr
*expr
, int indent
)
439 fprintf(stderr
, "%*s", indent
, "");
441 switch (expr
->type
) {
442 case pet_expr_double
:
443 fprintf(stderr
, "%s\n", expr
->d
.s
);
445 case pet_expr_access
:
446 isl_id_dump(expr
->acc
.ref_id
);
447 fprintf(stderr
, "%*s", indent
, "");
448 isl_map_dump(expr
->acc
.access
);
449 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
451 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
452 "", expr
->acc
.write
);
453 for (i
= 0; i
< expr
->n_arg
; ++i
)
454 expr_dump(expr
->args
[i
], indent
+ 2);
457 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
458 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
460 case pet_expr_binary
:
461 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
462 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
463 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
465 case pet_expr_ternary
:
466 fprintf(stderr
, "?:\n");
467 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
468 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
469 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
472 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
473 for (i
= 0; i
< expr
->n_arg
; ++i
)
474 expr_dump(expr
->args
[i
], indent
+ 2);
477 fprintf(stderr
, "(%s)\n", expr
->type_name
);
478 for (i
= 0; i
< expr
->n_arg
; ++i
)
479 expr_dump(expr
->args
[i
], indent
+ 2);
484 void pet_expr_dump(struct pet_expr
*expr
)
489 /* Does "expr" represent an access to an unnamed space, i.e.,
490 * does it represent an affine expression?
492 int pet_expr_is_affine(struct pet_expr
*expr
)
498 if (expr
->type
!= pet_expr_access
)
501 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
508 /* Return the identifier of the array accessed by "expr".
510 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
514 if (expr
->type
!= pet_expr_access
)
516 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
519 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
521 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
525 if (expr
->type
!= pet_expr_access
)
528 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
531 /* Return 1 if the two pet_exprs are equivalent.
533 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
537 if (!expr1
|| !expr2
)
540 if (expr1
->type
!= expr2
->type
)
542 if (expr1
->n_arg
!= expr2
->n_arg
)
544 for (i
= 0; i
< expr1
->n_arg
; ++i
)
545 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
547 switch (expr1
->type
) {
548 case pet_expr_double
:
549 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
551 if (expr1
->d
.val
!= expr2
->d
.val
)
554 case pet_expr_access
:
555 if (expr1
->acc
.read
!= expr2
->acc
.read
)
557 if (expr1
->acc
.write
!= expr2
->acc
.write
)
559 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
561 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
563 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
567 case pet_expr_binary
:
568 case pet_expr_ternary
:
569 if (expr1
->op
!= expr2
->op
)
573 if (strcmp(expr1
->name
, expr2
->name
))
577 if (strcmp(expr1
->type_name
, expr2
->type_name
))
585 /* Add extra conditions on the parameters to all access relations in "expr".
587 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
588 __isl_take isl_set
*cond
)
595 for (i
= 0; i
< expr
->n_arg
; ++i
) {
596 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
602 if (expr
->type
== pet_expr_access
) {
603 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
605 if (!expr
->acc
.access
)
613 return pet_expr_free(expr
);
616 /* Modify all expressions of type pet_expr_access in "expr"
617 * by calling "fn" on them.
619 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
620 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
628 for (i
= 0; i
< expr
->n_arg
; ++i
) {
629 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
631 return pet_expr_free(expr
);
634 if (expr
->type
== pet_expr_access
)
635 expr
= fn(expr
, user
);
640 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
642 * Return -1 on error (where fn return a negative value is treated as an error).
643 * Otherwise return 0.
645 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
646 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
653 for (i
= 0; i
< expr
->n_arg
; ++i
)
654 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
657 if (expr
->type
== pet_expr_access
)
658 return fn(expr
, user
);
663 /* Modify the access relation of the given access expression
664 * based on the given iteration space transformation.
665 * In particular, precompose the access relation with the update function.
667 * If the access has any arguments then the domain of the access relation
668 * is a wrapped mapping from the iteration space to the space of
669 * argument values. We only need to change the domain of this wrapped
670 * mapping, so we extend the input transformation with an identity mapping
671 * on the space of argument values.
673 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
675 isl_multi_pw_aff
*update
= user
;
678 update
= isl_multi_pw_aff_copy(update
);
680 space
= isl_map_get_space(expr
->acc
.access
);
681 space
= isl_space_domain(space
);
682 if (!isl_space_is_wrapping(space
))
683 isl_space_free(space
);
685 isl_multi_pw_aff
*id
;
686 space
= isl_space_unwrap(space
);
687 space
= isl_space_range(space
);
688 space
= isl_space_map_from_set(space
);
689 id
= isl_multi_pw_aff_identity(space
);
690 update
= isl_multi_pw_aff_product(update
, id
);
693 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
694 expr
->acc
.access
, update
);
695 if (!expr
->acc
.access
)
696 return pet_expr_free(expr
);
701 /* Modify all access relations in "expr" by precomposing them with
702 * the given iteration space transformation.
704 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
705 __isl_take isl_multi_pw_aff
*update
)
707 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
708 isl_multi_pw_aff_free(update
);
712 /* Construct a pet_stmt with given line number and statement
713 * number from a pet_expr.
714 * The initial iteration domain is the zero-dimensional universe.
715 * The name of the domain is given by "label" if it is non-NULL.
716 * Otherwise, the name is constructed as S_<id>.
717 * The domains of all access relations are modified to refer
718 * to the statement iteration domain.
720 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
721 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
723 struct pet_stmt
*stmt
;
727 isl_multi_pw_aff
*add_name
;
733 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
737 dim
= isl_space_set_alloc(ctx
, 0, 0);
739 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
741 snprintf(name
, sizeof(name
), "S_%d", id
);
742 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
744 dom
= isl_set_universe(isl_space_copy(dim
));
745 sched
= isl_map_from_domain(isl_set_copy(dom
));
747 dim
= isl_space_from_domain(dim
);
748 add_name
= isl_multi_pw_aff_zero(dim
);
749 expr
= expr_update_domain(expr
, add_name
);
753 stmt
->schedule
= sched
;
756 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
757 return pet_stmt_free(stmt
);
762 return pet_expr_free(expr
);
765 void *pet_stmt_free(struct pet_stmt
*stmt
)
772 isl_set_free(stmt
->domain
);
773 isl_map_free(stmt
->schedule
);
774 pet_expr_free(stmt
->body
);
776 for (i
= 0; i
< stmt
->n_arg
; ++i
)
777 pet_expr_free(stmt
->args
[i
]);
784 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
791 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
792 fprintf(stderr
, "%*s", indent
, "");
793 isl_set_dump(stmt
->domain
);
794 fprintf(stderr
, "%*s", indent
, "");
795 isl_map_dump(stmt
->schedule
);
796 expr_dump(stmt
->body
, indent
);
797 for (i
= 0; i
< stmt
->n_arg
; ++i
)
798 expr_dump(stmt
->args
[i
], indent
+ 2);
801 void pet_stmt_dump(struct pet_stmt
*stmt
)
806 struct pet_array
*pet_array_free(struct pet_array
*array
)
811 isl_set_free(array
->context
);
812 isl_set_free(array
->extent
);
813 isl_set_free(array
->value_bounds
);
814 free(array
->element_type
);
820 void pet_array_dump(struct pet_array
*array
)
825 isl_set_dump(array
->context
);
826 isl_set_dump(array
->extent
);
827 isl_set_dump(array
->value_bounds
);
828 fprintf(stderr
, "%s %s\n", array
->element_type
,
829 array
->live_out
? "live-out" : "");
832 /* Alloc a pet_scop structure, with extra room for information that
833 * is only used during parsing.
835 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
837 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
840 /* Construct a pet_scop with room for n statements.
842 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
845 struct pet_scop
*scop
;
847 scop
= pet_scop_alloc(ctx
);
851 space
= isl_space_params_alloc(ctx
, 0);
852 scop
->context
= isl_set_universe(isl_space_copy(space
));
853 scop
->context_value
= isl_set_universe(space
);
854 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
855 if (!scop
->context
|| !scop
->stmts
)
856 return pet_scop_free(scop
);
863 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
865 return scop_alloc(ctx
, 0);
868 /* Update "context" with respect to the valid parameter values for "access".
870 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
871 __isl_take isl_set
*context
)
873 context
= isl_set_intersect(context
,
874 isl_map_params(isl_map_copy(access
)));
878 /* Update "context" with respect to the valid parameter values for "expr".
880 * If "expr" represents a ternary operator, then a parameter value
881 * needs to be valid for the condition and for at least one of the
882 * remaining two arguments.
883 * If the condition is an affine expression, then we can be a bit more specific.
884 * The parameter then has to be valid for the second argument for
885 * non-zero accesses and valid for the third argument for zero accesses.
887 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
888 __isl_take isl_set
*context
)
892 if (expr
->type
== pet_expr_ternary
) {
894 isl_set
*context1
, *context2
;
896 is_aff
= pet_expr_is_affine(expr
->args
[0]);
900 context
= expr_extract_context(expr
->args
[0], context
);
901 context1
= expr_extract_context(expr
->args
[1],
902 isl_set_copy(context
));
903 context2
= expr_extract_context(expr
->args
[2], context
);
909 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
910 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
911 zero_set
= isl_map_params(access
);
912 context1
= isl_set_subtract(context1
,
913 isl_set_copy(zero_set
));
914 context2
= isl_set_intersect(context2
, zero_set
);
917 context
= isl_set_union(context1
, context2
);
918 context
= isl_set_coalesce(context
);
923 for (i
= 0; i
< expr
->n_arg
; ++i
)
924 context
= expr_extract_context(expr
->args
[i
], context
);
926 if (expr
->type
== pet_expr_access
)
927 context
= access_extract_context(expr
->acc
.access
, context
);
931 isl_set_free(context
);
935 /* Update "context" with respect to the valid parameter values for "stmt".
937 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
938 __isl_take isl_set
*context
)
942 for (i
= 0; i
< stmt
->n_arg
; ++i
)
943 context
= expr_extract_context(stmt
->args
[i
], context
);
945 context
= expr_extract_context(stmt
->body
, context
);
950 /* Construct a pet_scop that contains the given pet_stmt.
952 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
954 struct pet_scop
*scop
;
959 scop
= scop_alloc(ctx
, 1);
963 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
967 scop
->stmts
[0] = stmt
;
976 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
977 * does it represent an affine expression?
979 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
983 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
990 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
992 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
993 __isl_take isl_set
*dom
)
996 pa
= isl_set_indicator_function(set
);
997 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1001 /* Return "lhs || rhs", defined on the shared definition domain.
1003 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1004 __isl_take isl_pw_aff
*rhs
)
1009 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1010 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1011 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1012 isl_pw_aff_non_zero_set(rhs
));
1013 cond
= isl_set_coalesce(cond
);
1014 return indicator_function(cond
, dom
);
1017 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1018 * ext may be equal to either ext1 or ext2.
1020 * The two skips that need to be combined are assumed to be affine expressions.
1022 * We need to skip in ext if we need to skip in either ext1 or ext2.
1023 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1025 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1026 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1029 isl_pw_aff
*skip
, *skip1
, *skip2
;
1033 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1035 if (!ext1
->skip
[type
]) {
1038 ext
->skip
[type
] = ext2
->skip
[type
];
1039 ext2
->skip
[type
] = NULL
;
1042 if (!ext2
->skip
[type
]) {
1045 ext
->skip
[type
] = ext1
->skip
[type
];
1046 ext1
->skip
[type
] = NULL
;
1050 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1051 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1052 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1053 isl_error_internal
, "can only combine affine skips",
1054 return pet_scop_free(&ext
->scop
));
1056 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1057 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1058 skip
= pw_aff_or(skip1
, skip2
);
1059 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1060 ext1
->skip
[type
] = NULL
;
1061 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1062 ext2
->skip
[type
] = NULL
;
1063 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1064 if (!ext
->skip
[type
])
1065 return pet_scop_free(&ext
->scop
);
1070 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1071 * where type takes on the values pet_skip_now and pet_skip_later.
1072 * scop may be equal to either scop1 or scop2.
1074 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1075 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1077 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1078 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1079 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1081 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1082 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1086 /* Update scop->start and scop->end to include the region from "start"
1087 * to "end". In particular, if scop->end == 0, then "scop" does not
1088 * have any offset information yet and we simply take the information
1089 * from "start" and "end". Otherwise, we update the fields if the
1090 * region from "start" to "end" is not already included.
1092 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1093 unsigned start
, unsigned end
)
1097 if (scop
->end
== 0) {
1098 scop
->start
= start
;
1101 if (start
< scop
->start
)
1102 scop
->start
= start
;
1103 if (end
> scop
->end
)
1110 /* Does "implication" appear in the list of implications of "scop"?
1112 static int is_known_implication(struct pet_scop
*scop
,
1113 struct pet_implication
*implication
)
1117 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1118 struct pet_implication
*pi
= scop
->implications
[i
];
1121 if (pi
->satisfied
!= implication
->satisfied
)
1123 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1133 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1134 * in "scop", removing duplicates (i.e., implications in "scop2" that
1135 * already appear in "scop1").
1137 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1138 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1145 if (scop2
->n_implication
== 0) {
1146 scop
->n_implication
= scop1
->n_implication
;
1147 scop
->implications
= scop1
->implications
;
1148 scop1
->n_implication
= 0;
1149 scop1
->implications
= NULL
;
1153 if (scop1
->n_implication
== 0) {
1154 scop
->n_implication
= scop2
->n_implication
;
1155 scop
->implications
= scop2
->implications
;
1156 scop2
->n_implication
= 0;
1157 scop2
->implications
= NULL
;
1161 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1162 scop1
->n_implication
+ scop2
->n_implication
);
1163 if (!scop
->implications
)
1164 return pet_scop_free(scop
);
1166 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1167 scop
->implications
[i
] = scop1
->implications
[i
];
1168 scop1
->implications
[i
] = NULL
;
1171 scop
->n_implication
= scop1
->n_implication
;
1172 j
= scop1
->n_implication
;
1173 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1176 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1178 return pet_scop_free(scop
);
1181 scop
->implications
[j
++] = scop2
->implications
[i
];
1182 scop2
->implications
[i
] = NULL
;
1184 scop
->n_implication
= j
;
1189 /* Combine the offset information of "scop1" and "scop2" into "scop".
1191 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1192 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1195 scop
= pet_scop_update_start_end(scop
,
1196 scop1
->start
, scop1
->end
);
1198 scop
= pet_scop_update_start_end(scop
,
1199 scop2
->start
, scop2
->end
);
1203 /* Construct a pet_scop that contains the offset information,
1204 * arrays, statements and skip information in "scop1" and "scop2".
1206 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1207 struct pet_scop
*scop2
)
1210 struct pet_scop
*scop
= NULL
;
1212 if (!scop1
|| !scop2
)
1215 if (scop1
->n_stmt
== 0) {
1216 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1217 pet_scop_free(scop1
);
1221 if (scop2
->n_stmt
== 0) {
1222 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1223 pet_scop_free(scop2
);
1227 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1231 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1232 scop1
->n_array
+ scop2
->n_array
);
1235 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1237 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1238 scop
->stmts
[i
] = scop1
->stmts
[i
];
1239 scop1
->stmts
[i
] = NULL
;
1242 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1243 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1244 scop2
->stmts
[i
] = NULL
;
1247 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1248 scop
->arrays
[i
] = scop1
->arrays
[i
];
1249 scop1
->arrays
[i
] = NULL
;
1252 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1253 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1254 scop2
->arrays
[i
] = NULL
;
1257 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1258 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1259 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1260 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1261 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1263 pet_scop_free(scop1
);
1264 pet_scop_free(scop2
);
1267 pet_scop_free(scop1
);
1268 pet_scop_free(scop2
);
1269 pet_scop_free(scop
);
1273 /* Apply the skip condition "skip" to "scop".
1274 * That is, make sure "scop" is not executed when the condition holds.
1276 * If "skip" is an affine expression, we add the conditions under
1277 * which the expression is zero to the iteration domains.
1278 * Otherwise, we add a filter on the variable attaining the value zero.
1280 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1281 __isl_take isl_multi_pw_aff
*skip
)
1290 is_aff
= multi_pw_aff_is_affine(skip
);
1295 return pet_scop_filter(scop
, skip
, 0);
1297 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1298 isl_multi_pw_aff_free(skip
);
1299 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1300 scop
= pet_scop_restrict(scop
, zero
);
1304 isl_multi_pw_aff_free(skip
);
1305 return pet_scop_free(scop
);
1308 /* Construct a pet_scop that contains the arrays, statements and
1309 * skip information in "scop1" and "scop2", where the two scops
1310 * are executed "in sequence". That is, breaks and continues
1311 * in scop1 have an effect on scop2.
1313 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1314 struct pet_scop
*scop2
)
1316 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1317 scop2
= restrict_skip(scop2
,
1318 pet_scop_get_skip(scop1
, pet_skip_now
));
1319 return pet_scop_add(ctx
, scop1
, scop2
);
1322 /* Construct a pet_scop that contains the arrays, statements and
1323 * skip information in "scop1" and "scop2", where the two scops
1324 * are executed "in parallel". That is, any break or continue
1325 * in scop1 has no effect on scop2.
1327 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1328 struct pet_scop
*scop2
)
1330 return pet_scop_add(ctx
, scop1
, scop2
);
1333 void *pet_implication_free(struct pet_implication
*implication
)
1340 isl_map_free(implication
->extension
);
1346 void *pet_scop_free(struct pet_scop
*scop
)
1349 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1353 isl_set_free(scop
->context
);
1354 isl_set_free(scop
->context_value
);
1356 for (i
= 0; i
< scop
->n_array
; ++i
)
1357 pet_array_free(scop
->arrays
[i
]);
1360 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1361 pet_stmt_free(scop
->stmts
[i
]);
1363 if (scop
->implications
)
1364 for (i
= 0; i
< scop
->n_implication
; ++i
)
1365 pet_implication_free(scop
->implications
[i
]);
1366 free(scop
->implications
);
1367 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1368 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1373 void pet_implication_dump(struct pet_implication
*implication
)
1378 fprintf(stderr
, "%d\n", implication
->satisfied
);
1379 isl_map_dump(implication
->extension
);
1382 void pet_scop_dump(struct pet_scop
*scop
)
1385 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1390 isl_set_dump(scop
->context
);
1391 isl_set_dump(scop
->context_value
);
1392 for (i
= 0; i
< scop
->n_array
; ++i
)
1393 pet_array_dump(scop
->arrays
[i
]);
1394 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1395 pet_stmt_dump(scop
->stmts
[i
]);
1396 for (i
= 0; i
< scop
->n_implication
; ++i
)
1397 pet_implication_dump(scop
->implications
[i
]);
1400 fprintf(stderr
, "skip\n");
1401 isl_multi_pw_aff_dump(ext
->skip
[0]);
1402 isl_multi_pw_aff_dump(ext
->skip
[1]);
1406 /* Return 1 if the two pet_arrays are equivalent.
1408 * We don't compare element_size as this may be target dependent.
1410 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1412 if (!array1
|| !array2
)
1415 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1417 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1419 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1421 if (array1
->value_bounds
&&
1422 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1424 if (strcmp(array1
->element_type
, array2
->element_type
))
1426 if (array1
->live_out
!= array2
->live_out
)
1428 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1430 if (array1
->declared
!= array2
->declared
)
1432 if (array1
->exposed
!= array2
->exposed
)
1438 /* Return 1 if the two pet_stmts are equivalent.
1440 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1444 if (!stmt1
|| !stmt2
)
1447 if (stmt1
->line
!= stmt2
->line
)
1449 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1451 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1453 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1455 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1457 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1458 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1465 /* Return 1 if the two pet_implications are equivalent.
1467 int pet_implication_is_equal(struct pet_implication
*implication1
,
1468 struct pet_implication
*implication2
)
1470 if (!implication1
|| !implication2
)
1473 if (implication1
->satisfied
!= implication2
->satisfied
)
1475 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1481 /* Return 1 if the two pet_scops are equivalent.
1483 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1487 if (!scop1
|| !scop2
)
1490 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1492 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1495 if (scop1
->n_array
!= scop2
->n_array
)
1497 for (i
= 0; i
< scop1
->n_array
; ++i
)
1498 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1501 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1503 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1504 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1507 if (scop1
->n_implication
!= scop2
->n_implication
)
1509 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1510 if (!pet_implication_is_equal(scop1
->implications
[i
],
1511 scop2
->implications
[i
]))
1517 /* Prefix the schedule of "stmt" with an extra dimension with constant
1520 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1525 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1526 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1527 if (!stmt
->schedule
)
1528 return pet_stmt_free(stmt
);
1533 /* Prefix the schedules of all statements in "scop" with an extra
1534 * dimension with constant value "pos".
1536 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1543 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1544 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1545 if (!scop
->stmts
[i
])
1546 return pet_scop_free(scop
);
1552 /* Given a set with a parameter at "param_pos" that refers to the
1553 * iterator, "move" the iterator to the first set dimension.
1554 * That is, essentially equate the parameter to the first set dimension
1555 * and then project it out.
1557 * The first set dimension may however refer to a virtual iterator,
1558 * while the parameter refers to the "real" iterator.
1559 * We therefore need to take into account the affine expression "iv_map", which
1560 * expresses the real iterator in terms of the virtual iterator.
1561 * In particular, we equate the set dimension to the input of the map
1562 * and the parameter to the output of the map and then project out
1563 * everything we don't need anymore.
1565 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1566 int param_pos
, __isl_take isl_aff
*iv_map
)
1568 isl_map
*map
, *map2
;
1569 map
= isl_map_from_domain(set
);
1570 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1571 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1572 map2
= isl_map_from_aff(iv_map
);
1573 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1574 map
= isl_map_apply_range(map
, map2
);
1575 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1576 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1577 return isl_map_domain(map
);
1580 /* Data used in embed_access.
1581 * extend adds an iterator to the iteration domain (through precomposition).
1582 * iv_map expresses the real iterator in terms of the virtual iterator
1583 * var_id represents the induction variable of the corresponding loop
1585 struct pet_embed_access
{
1586 isl_multi_pw_aff
*extend
;
1591 /* Given an access expression, embed the associated access relation
1592 * in an extra outer loop.
1594 * We first update the iteration domain to insert the extra dimension.
1596 * If the access refers to the induction variable, then it is
1597 * turned into an access to the set of integers with index (and value)
1598 * equal to the induction variable.
1600 * If the induction variable appears in the constraints (as a parameter),
1601 * then the parameter is equated to the newly introduced iteration
1602 * domain dimension and subsequently projected out.
1604 * Similarly, if the accessed array is a virtual array (with user
1605 * pointer equal to NULL), as created by create_test_index,
1606 * then it is extended along with the domain of the access.
1608 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1610 struct pet_embed_access
*data
= user
;
1612 isl_id
*array_id
= NULL
;
1615 expr
= update_domain(expr
, data
->extend
);
1619 access
= expr
->acc
.access
;
1621 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1622 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1623 if (array_id
== data
->var_id
||
1624 (array_id
&& !isl_id_get_user(array_id
))) {
1625 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1626 access
= isl_map_equate(access
,
1627 isl_dim_in
, 0, isl_dim_out
, 0);
1628 if (array_id
== data
->var_id
)
1629 access
= isl_map_apply_range(access
,
1630 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1632 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1633 isl_id_copy(array_id
));
1635 isl_id_free(array_id
);
1637 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1639 isl_set
*set
= isl_map_wrap(access
);
1640 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1641 access
= isl_set_unwrap(set
);
1643 expr
->acc
.access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1644 isl_id_copy(data
->var_id
));
1645 if (!expr
->acc
.access
)
1646 return pet_expr_free(expr
);
1651 /* Embed all access subexpressions of "expr" in an extra loop.
1652 * "extend" inserts an outer loop iterator in the iteration domains
1653 * (through precomposition).
1654 * "iv_map" expresses the real iterator in terms of the virtual iterator
1655 * "var_id" represents the induction variable.
1657 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1658 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1659 __isl_keep isl_id
*var_id
)
1661 struct pet_embed_access data
=
1662 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1664 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1665 isl_aff_free(iv_map
);
1666 isl_multi_pw_aff_free(extend
);
1670 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1671 * "dom" and schedule "sched". "var_id" represents the induction variable
1672 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1673 * That is, it expresses the iterator that some of the parameters in "stmt"
1674 * may refer to in terms of the iterator used in "dom" and
1675 * the domain of "sched".
1677 * The iteration domain and schedule of the statement are updated
1678 * according to the iteration domain and schedule of the new loop.
1679 * If stmt->domain is a wrapped map, then the iteration domain
1680 * is the domain of this map, so we need to be careful to adjust
1683 * If the induction variable appears in the constraints (as a parameter)
1684 * of the current iteration domain or the schedule of the statement,
1685 * then the parameter is equated to the newly introduced iteration
1686 * domain dimension and subsequently projected out.
1688 * Finally, all access relations are updated based on the extra loop.
1690 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1691 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1692 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1698 isl_multi_pw_aff
*extend
;
1703 if (isl_set_is_wrapping(stmt
->domain
)) {
1708 map
= isl_set_unwrap(stmt
->domain
);
1709 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1710 ran_dim
= isl_space_range(isl_map_get_space(map
));
1711 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1712 isl_set_universe(ran_dim
));
1713 map
= isl_map_flat_domain_product(ext
, map
);
1714 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1715 isl_id_copy(stmt_id
));
1716 dim
= isl_space_domain(isl_map_get_space(map
));
1717 stmt
->domain
= isl_map_wrap(map
);
1719 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1720 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1722 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1723 isl_id_copy(stmt_id
));
1724 dim
= isl_set_get_space(stmt
->domain
);
1727 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1729 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1730 isl_aff_copy(iv_map
));
1732 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1733 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1734 isl_dim_in
, stmt_id
);
1736 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1738 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1739 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1740 stmt
->schedule
= isl_set_unwrap(set
);
1743 dim
= isl_space_map_from_set(dim
);
1744 extend
= isl_multi_pw_aff_identity(dim
);
1745 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
1746 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
1747 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
1748 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1749 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1750 isl_multi_pw_aff_copy(extend
),
1751 isl_aff_copy(iv_map
), var_id
);
1752 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1755 isl_id_free(var_id
);
1757 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1759 return pet_stmt_free(stmt
);
1760 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1761 return pet_stmt_free(stmt
);
1765 isl_map_free(sched
);
1766 isl_aff_free(iv_map
);
1767 isl_id_free(var_id
);
1771 /* Embed the given pet_array in an extra outer loop with iteration domain
1773 * This embedding only has an effect on virtual arrays (those with
1774 * user pointer equal to NULL), which need to be extended along with
1775 * the iteration domain.
1777 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1778 __isl_take isl_set
*dom
)
1780 isl_id
*array_id
= NULL
;
1785 if (isl_set_has_tuple_id(array
->extent
))
1786 array_id
= isl_set_get_tuple_id(array
->extent
);
1788 if (array_id
&& !isl_id_get_user(array_id
)) {
1789 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1790 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1792 return pet_array_free(array
);
1795 isl_id_free(array_id
);
1804 /* Project out all unnamed parameters from "set" and return the result.
1806 static __isl_give isl_set
*set_project_out_unnamed_params(
1807 __isl_take isl_set
*set
)
1811 n
= isl_set_dim(set
, isl_dim_param
);
1812 for (i
= n
- 1; i
>= 0; --i
) {
1813 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1815 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1821 /* Update the context with respect to an embedding into a loop
1822 * with iteration domain "dom" and induction variable "id".
1823 * "iv_map" expresses the real iterator (parameter "id") in terms
1824 * of a possibly virtual iterator (used in "dom").
1826 * If the current context is independent of "id", we don't need
1828 * Otherwise, a parameter value is invalid for the embedding if
1829 * any of the corresponding iterator values is invalid.
1830 * That is, a parameter value is valid only if all the corresponding
1831 * iterator values are valid.
1832 * We therefore compute the set of parameters
1834 * forall i in dom : valid (i)
1838 * not exists i in dom : not valid(i)
1842 * not exists i in dom \ valid(i)
1844 * Before we subtract valid(i) from dom, we first need to substitute
1845 * the real iterator for the virtual iterator.
1847 * If there are any unnamed parameters in "dom", then we consider
1848 * a parameter value to be valid if it is valid for any value of those
1849 * unnamed parameters. They are therefore projected out at the end.
1851 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1852 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
1853 __isl_keep isl_id
*id
)
1858 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1862 context
= isl_set_from_params(context
);
1863 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1864 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1865 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1866 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
1867 context
= isl_set_preimage_multi_aff(context
, ma
);
1868 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1869 context
= isl_set_params(context
);
1870 context
= isl_set_complement(context
);
1871 context
= set_project_out_unnamed_params(context
);
1875 /* Update the implication with respect to an embedding into a loop
1876 * with iteration domain "dom".
1878 * Since embed_access extends virtual arrays along with the domain
1879 * of the access, we need to do the same with domain and range
1880 * of the implication. Since the original implication is only valid
1881 * within a given iteration of the loop, the extended implication
1882 * maps the extra array dimension corresponding to the extra loop
1885 static struct pet_implication
*pet_implication_embed(
1886 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1894 map
= isl_set_identity(dom
);
1895 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1896 map
= isl_map_flat_product(map
, implication
->extension
);
1897 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1898 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1899 implication
->extension
= map
;
1900 if (!implication
->extension
)
1901 return pet_implication_free(implication
);
1909 /* Embed all statements and arrays in "scop" in an extra outer loop
1910 * with iteration domain "dom" and schedule "sched".
1911 * "id" represents the induction variable of the loop.
1912 * "iv_map" maps a possibly virtual iterator to the real iterator.
1913 * That is, it expresses the iterator that some of the parameters in "scop"
1914 * may refer to in terms of the iterator used in "dom" and
1915 * the domain of "sched".
1917 * Any skip conditions within the loop have no effect outside of the loop.
1918 * The caller is responsible for making sure skip[pet_skip_later] has been
1919 * taken into account.
1921 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1922 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
1923 __isl_take isl_id
*id
)
1930 pet_scop_reset_skip(scop
, pet_skip_now
);
1931 pet_scop_reset_skip(scop
, pet_skip_later
);
1933 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1937 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1938 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1939 isl_set_copy(dom
), isl_map_copy(sched
),
1940 isl_aff_copy(iv_map
), isl_id_copy(id
));
1941 if (!scop
->stmts
[i
])
1945 for (i
= 0; i
< scop
->n_array
; ++i
) {
1946 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1948 if (!scop
->arrays
[i
])
1952 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1953 scop
->implications
[i
] =
1954 pet_implication_embed(scop
->implications
[i
],
1956 if (!scop
->implications
[i
])
1961 isl_map_free(sched
);
1962 isl_aff_free(iv_map
);
1967 isl_map_free(sched
);
1968 isl_aff_free(iv_map
);
1970 return pet_scop_free(scop
);
1973 /* Add extra conditions on the parameters to iteration domain of "stmt".
1975 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1976 __isl_take isl_set
*cond
)
1981 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1986 return pet_stmt_free(stmt
);
1989 /* Add extra conditions to scop->skip[type].
1991 * The new skip condition only holds if it held before
1992 * and the condition is true. It does not hold if it did not hold
1993 * before or the condition is false.
1995 * The skip condition is assumed to be an affine expression.
1997 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1998 enum pet_skip type
, __isl_keep isl_set
*cond
)
2000 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2006 if (!ext
->skip
[type
])
2009 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2010 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2011 isl_error_internal
, "can only resrict affine skips",
2012 return pet_scop_free(scop
));
2014 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2015 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2016 cond
= isl_set_copy(cond
);
2017 cond
= isl_set_from_params(cond
);
2018 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2019 skip
= indicator_function(cond
, dom
);
2020 isl_multi_pw_aff_free(ext
->skip
[type
]);
2021 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2022 if (!ext
->skip
[type
])
2023 return pet_scop_free(scop
);
2028 /* Add extra conditions on the parameters to all iteration domains
2029 * and skip conditions.
2031 * A parameter value is valid for the result if it was valid
2032 * for the original scop and satisfies "cond" or if it does
2033 * not satisfy "cond" as in this case the scop is not executed
2034 * and the original constraints on the parameters are irrelevant.
2036 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2037 __isl_take isl_set
*cond
)
2041 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2042 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2047 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2048 scop
->context
= isl_set_union(scop
->context
,
2049 isl_set_complement(isl_set_copy(cond
)));
2050 scop
->context
= isl_set_coalesce(scop
->context
);
2051 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2055 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2056 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2057 isl_set_copy(cond
));
2058 if (!scop
->stmts
[i
])
2066 return pet_scop_free(scop
);
2069 /* Construct a function that (upon precomposition) inserts
2070 * a filter value with name "id" and value "satisfied"
2071 * in the list of filter values embedded in the set space "space".
2073 * If "space" does not contain any filter values yet, we first create
2074 * a function that inserts 0 filter values, i.e.,
2076 * [space -> []] -> space
2078 * We can now assume that space is of the form [dom -> [filters]]
2079 * We construct an identity mapping on dom and a mapping on filters
2080 * that (upon precomposition) inserts the new filter
2083 * [satisfied, filters] -> [filters]
2085 * and then compute the cross product
2087 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2089 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2090 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2094 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2097 if (isl_space_is_wrapping(space
)) {
2098 space2
= isl_space_map_from_set(isl_space_copy(space
));
2099 ma
= isl_multi_aff_identity(space2
);
2100 space
= isl_space_unwrap(space
);
2102 space
= isl_space_from_domain(space
);
2103 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2106 space2
= isl_space_domain(isl_space_copy(space
));
2107 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2108 space
= isl_space_range(space
);
2109 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2110 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2111 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2112 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2113 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2115 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2116 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2121 /* Insert an argument expression corresponding to "test" in front
2122 * of the list of arguments described by *n_arg and *args.
2124 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2125 __isl_keep isl_map
*test
)
2128 isl_ctx
*ctx
= isl_map_get_ctx(test
);
2134 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2138 struct pet_expr
**ext
;
2139 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2142 for (i
= 0; i
< *n_arg
; ++i
)
2143 ext
[1 + i
] = (*args
)[i
];
2148 (*args
)[0] = pet_expr_from_access(isl_map_copy(test
));
2155 /* Make the expression "expr" depend on the value of "test"
2156 * being equal to "satisfied".
2158 * If "test" is an affine expression, we simply add the conditions
2159 * on the expression have the value "satisfied" to all access relations.
2161 * Otherwise, we add a filter to "expr" (which is then assumed to be
2162 * an access expression) corresponding to "test" being equal to "satisfied".
2164 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2165 __isl_take isl_map
*test
, int satisfied
)
2170 isl_pw_multi_aff
*pma
;
2175 if (!isl_map_has_tuple_id(test
, isl_dim_out
)) {
2176 test
= isl_map_fix_si(test
, isl_dim_out
, 0, satisfied
);
2177 return pet_expr_restrict(expr
, isl_map_params(test
));
2180 ctx
= isl_map_get_ctx(test
);
2181 if (expr
->type
!= pet_expr_access
)
2182 isl_die(ctx
, isl_error_invalid
,
2183 "can only filter access expressions", goto error
);
2185 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2186 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2187 pma
= insert_filter_pma(space
, id
, satisfied
);
2189 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2190 expr
->acc
.access
, pma
);
2191 if (!expr
->acc
.access
)
2194 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2201 return pet_expr_free(expr
);
2204 /* Look through the applications in "scop" for any that can be
2205 * applied to the filter expressed by "map" and "satisified".
2206 * If there is any, then apply it to "map" and return the result.
2207 * Otherwise, return "map".
2208 * "id" is the identifier of the virtual array.
2210 * We only introduce at most one implication for any given virtual array,
2211 * so we can apply the implication and return as soon as we find one.
2213 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2214 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2218 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2219 struct pet_implication
*pi
= scop
->implications
[i
];
2222 if (pi
->satisfied
!= satisfied
)
2224 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2229 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2235 /* Is the filter expressed by "test" and "satisfied" implied
2236 * by filter "pos" on "domain", with filter "expr", taking into
2237 * account the implications of "scop"?
2239 * For filter on domain implying that expressed by "test" and "satisfied",
2240 * the filter needs to be an access to the same (virtual) array as "test" and
2241 * the filter value needs to be equal to "satisfied".
2242 * Moreover, the filter access relation, possibly extended by
2243 * the implications in "scop" needs to contain "test".
2245 static int implies_filter(struct pet_scop
*scop
,
2246 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2247 __isl_keep isl_map
*test
, int satisfied
)
2249 isl_id
*test_id
, *arg_id
;
2256 if (expr
->type
!= pet_expr_access
)
2258 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2259 arg_id
= pet_expr_access_get_id(expr
);
2260 isl_id_free(arg_id
);
2261 isl_id_free(test_id
);
2262 if (test_id
!= arg_id
)
2264 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2265 is_int
= isl_val_is_int(val
);
2267 s
= isl_val_get_num_si(val
);
2276 implied
= isl_map_copy(expr
->acc
.access
);
2277 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2278 is_subset
= isl_map_is_subset(test
, implied
);
2279 isl_map_free(implied
);
2284 /* Is the filter expressed by "test" and "satisfied" implied
2285 * by any of the filters on the domain of "stmt", taking into
2286 * account the implications of "scop"?
2288 static int filter_implied(struct pet_scop
*scop
,
2289 struct pet_stmt
*stmt
, __isl_keep isl_map
*test
, int satisfied
)
2296 if (!scop
|| !stmt
|| !test
)
2298 if (scop
->n_implication
== 0)
2300 if (stmt
->n_arg
== 0)
2303 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2306 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2307 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2309 if (implied
< 0 || implied
)
2313 isl_map_free(domain
);
2317 /* Make the statement "stmt" depend on the value of "test"
2318 * being equal to "satisfied" by adjusting stmt->domain.
2320 * The domain of "test" corresponds to the (zero or more) outer dimensions
2321 * of the iteration domain.
2323 * We first extend "test" to apply to the entire iteration domain and
2324 * then check if the filter that we are about to add is implied
2325 * by any of the current filters, possibly taking into account
2326 * the implications in "scop". If so, we leave "stmt" untouched and return.
2328 * Otherwise, we insert an argument corresponding to a read to "test"
2329 * from the iteration domain of "stmt" in front of the list of arguments.
2330 * We also insert a corresponding output dimension in the wrapped
2331 * map contained in stmt->domain, with value set to "satisfied".
2333 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2334 struct pet_stmt
*stmt
, __isl_take isl_map
*test
, int satisfied
)
2340 isl_pw_multi_aff
*pma
;
2349 space
= isl_set_get_space(stmt
->domain
);
2350 if (isl_space_is_wrapping(space
))
2351 space
= isl_space_domain(isl_space_unwrap(space
));
2352 dom
= isl_set_universe(space
);
2353 n_test_dom
= isl_map_dim(test
, isl_dim_in
);
2354 add_dom
= isl_map_from_range(dom
);
2355 add_dom
= isl_map_add_dims(add_dom
, isl_dim_in
, n_test_dom
);
2356 for (i
= 0; i
< n_test_dom
; ++i
)
2357 add_dom
= isl_map_equate(add_dom
, isl_dim_in
, i
,
2359 test
= isl_map_apply_domain(test
, add_dom
);
2361 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2369 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2370 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2371 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2373 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2380 return pet_stmt_free(stmt
);
2383 /* Does "scop" have a skip condition of the given "type"?
2385 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2387 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2391 return ext
->skip
[type
] != NULL
;
2394 /* Does "scop" have a skip condition of the given "type" that
2395 * is an affine expression?
2397 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2399 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2403 if (!ext
->skip
[type
])
2405 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2408 /* Does "scop" have a skip condition of the given "type" that
2409 * is not an affine expression?
2411 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2413 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2418 if (!ext
->skip
[type
])
2420 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2426 /* Does "scop" have a skip condition of the given "type" that
2427 * is affine and holds on the entire domain?
2429 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2431 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2437 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2438 if (is_aff
< 0 || !is_aff
)
2441 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2442 set
= isl_pw_aff_non_zero_set(pa
);
2443 is_univ
= isl_set_plain_is_universe(set
);
2449 /* Replace scop->skip[type] by "skip".
2451 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2452 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2454 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2459 isl_multi_pw_aff_free(ext
->skip
[type
]);
2460 ext
->skip
[type
] = skip
;
2464 isl_multi_pw_aff_free(skip
);
2465 return pet_scop_free(scop
);
2468 /* Return a copy of scop->skip[type].
2470 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2473 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2478 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2481 /* Assuming scop->skip[type] is an affine expression,
2482 * return the constraints on the parameters for which the skip condition
2485 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2488 isl_multi_pw_aff
*skip
;
2491 skip
= pet_scop_get_skip(scop
, type
);
2492 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2493 isl_multi_pw_aff_free(skip
);
2494 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2497 /* Return a map to the skip condition of the given type.
2499 __isl_give isl_map
*pet_scop_get_skip_map(struct pet_scop
*scop
,
2502 return isl_map_from_multi_pw_aff(pet_scop_get_skip(scop
, type
));
2505 /* Return the identifier of the variable that is accessed by
2506 * the skip condition of the given type.
2508 * The skip condition is assumed not to be an affine condition.
2510 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2513 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2518 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2521 /* Return an access pet_expr corresponding to the skip condition
2522 * of the given type.
2524 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2527 return pet_expr_from_access(pet_scop_get_skip_map(scop
, type
));
2530 /* Drop the the skip condition scop->skip[type].
2532 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2534 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2539 isl_multi_pw_aff_free(ext
->skip
[type
]);
2540 ext
->skip
[type
] = NULL
;
2543 /* Make the skip condition (if any) depend on the value of "test" being
2544 * equal to "satisfied".
2546 * We only support the case where the original skip condition is universal,
2547 * i.e., where skipping is unconditional, and where satisfied == 1.
2548 * In this case, the skip condition is changed to skip only when
2549 * "test" is equal to one.
2551 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2552 enum pet_skip type
, __isl_keep isl_map
*test
, int satisfied
)
2558 if (!pet_scop_has_skip(scop
, type
))
2562 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2564 return pet_scop_free(scop
);
2565 if (satisfied
&& is_univ
) {
2566 isl_space
*space
= isl_map_get_space(test
);
2567 isl_multi_pw_aff
*skip
;
2568 skip
= isl_multi_pw_aff_zero(space
);
2569 scop
= pet_scop_set_skip(scop
, type
, skip
);
2573 isl_die(isl_map_get_ctx(test
), isl_error_internal
,
2574 "skip expression cannot be filtered",
2575 return pet_scop_free(scop
));
2581 /* Make all statements in "scop" depend on the value of "test"
2582 * being equal to "satisfied" by adjusting their domains.
2584 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2585 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2588 isl_map
*map
= isl_map_from_multi_pw_aff(test
);
2590 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, map
, satisfied
);
2591 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, map
, satisfied
);
2596 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2597 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2598 isl_map_copy(map
), satisfied
);
2599 if (!scop
->stmts
[i
])
2607 return pet_scop_free(scop
);
2610 /* Add all parameters in "expr" to "dim" and return the result.
2612 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2613 __isl_take isl_space
*dim
)
2619 for (i
= 0; i
< expr
->n_arg
; ++i
)
2621 dim
= expr_collect_params(expr
->args
[i
], dim
);
2623 if (expr
->type
== pet_expr_access
)
2624 dim
= isl_space_align_params(dim
,
2625 isl_map_get_space(expr
->acc
.access
));
2629 isl_space_free(dim
);
2630 return pet_expr_free(expr
);
2633 /* Add all parameters in "stmt" to "dim" and return the result.
2635 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2636 __isl_take isl_space
*dim
)
2641 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2642 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2643 dim
= expr_collect_params(stmt
->body
, dim
);
2647 isl_space_free(dim
);
2648 return pet_stmt_free(stmt
);
2651 /* Add all parameters in "array" to "dim" and return the result.
2653 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2654 __isl_take isl_space
*dim
)
2659 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2660 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2664 pet_array_free(array
);
2665 return isl_space_free(dim
);
2668 /* Add all parameters in "scop" to "dim" and return the result.
2670 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2671 __isl_take isl_space
*dim
)
2678 for (i
= 0; i
< scop
->n_array
; ++i
)
2679 dim
= array_collect_params(scop
->arrays
[i
], dim
);
2681 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2682 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
2686 isl_space_free(dim
);
2687 return pet_scop_free(scop
);
2690 /* Add all parameters in "dim" to all access relations in "expr".
2692 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
2693 __isl_take isl_space
*dim
)
2700 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2702 expr_propagate_params(expr
->args
[i
],
2703 isl_space_copy(dim
));
2708 if (expr
->type
== pet_expr_access
) {
2709 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
2710 isl_space_copy(dim
));
2711 if (!expr
->acc
.access
)
2715 isl_space_free(dim
);
2718 isl_space_free(dim
);
2719 return pet_expr_free(expr
);
2722 /* Add all parameters in "dim" to the domain, schedule and
2723 * all access relations in "stmt".
2725 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2726 __isl_take isl_space
*dim
)
2731 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
2732 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2733 isl_space_copy(dim
));
2734 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
2736 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2739 isl_space_free(dim
);
2742 isl_space_free(dim
);
2743 return pet_stmt_free(stmt
);
2746 /* Add all parameters in "dim" to "array".
2748 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2749 __isl_take isl_space
*dim
)
2754 array
->context
= isl_set_align_params(array
->context
,
2755 isl_space_copy(dim
));
2756 array
->extent
= isl_set_align_params(array
->extent
,
2757 isl_space_copy(dim
));
2758 if (array
->value_bounds
) {
2759 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2760 isl_space_copy(dim
));
2761 if (!array
->value_bounds
)
2765 if (!array
->context
|| !array
->extent
)
2768 isl_space_free(dim
);
2771 isl_space_free(dim
);
2772 return pet_array_free(array
);
2775 /* Add all parameters in "dim" to "scop".
2777 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2778 __isl_take isl_space
*dim
)
2785 for (i
= 0; i
< scop
->n_array
; ++i
) {
2786 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2787 isl_space_copy(dim
));
2788 if (!scop
->arrays
[i
])
2792 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2793 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2794 isl_space_copy(dim
));
2795 if (!scop
->stmts
[i
])
2799 isl_space_free(dim
);
2802 isl_space_free(dim
);
2803 return pet_scop_free(scop
);
2806 /* Update all isl_sets and isl_maps in "scop" such that they all
2807 * have the same parameters.
2809 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2816 dim
= isl_set_get_space(scop
->context
);
2817 dim
= scop_collect_params(scop
, dim
);
2819 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
2820 scop
= scop_propagate_params(scop
, dim
);
2825 /* Check if the given access relation accesses a (0D) array that corresponds
2826 * to one of the parameters in "dim". If so, replace the array access
2827 * by an access to the set of integers with as index (and value)
2830 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
2831 __isl_take isl_space
*dim
)
2833 isl_id
*array_id
= NULL
;
2836 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
2837 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2838 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
2840 isl_space_free(dim
);
2843 isl_id_free(array_id
);
2847 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
2849 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
2850 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
2853 isl_id_free(array_id
);
2855 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2856 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
2861 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2862 * in "dim" by a value equal to the corresponding parameter.
2864 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
2865 __isl_take isl_space
*dim
)
2872 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2874 expr_detect_parameter_accesses(expr
->args
[i
],
2875 isl_space_copy(dim
));
2880 if (expr
->type
== pet_expr_access
) {
2881 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
2882 isl_space_copy(dim
));
2883 if (!expr
->acc
.access
)
2887 isl_space_free(dim
);
2890 isl_space_free(dim
);
2891 return pet_expr_free(expr
);
2894 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2895 * in "dim" by a value equal to the corresponding parameter.
2897 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2898 __isl_take isl_space
*dim
)
2903 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
2904 isl_space_copy(dim
));
2906 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2909 isl_space_free(dim
);
2912 isl_space_free(dim
);
2913 return pet_stmt_free(stmt
);
2916 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2917 * in "dim" by a value equal to the corresponding parameter.
2919 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2920 __isl_take isl_space
*dim
)
2927 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2928 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2929 isl_space_copy(dim
));
2930 if (!scop
->stmts
[i
])
2934 isl_space_free(dim
);
2937 isl_space_free(dim
);
2938 return pet_scop_free(scop
);
2941 /* Replace all accesses to (0D) arrays that correspond to any of
2942 * the parameters used in "scop" by a value equal
2943 * to the corresponding parameter.
2945 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2952 dim
= isl_set_get_space(scop
->context
);
2953 dim
= scop_collect_params(scop
, dim
);
2955 scop
= scop_detect_parameter_accesses(scop
, dim
);
2960 /* Add all read access relations (if "read" is set) and/or all write
2961 * access relations (if "write" is set) to "accesses" and return the result.
2963 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
2964 int read
, int write
, __isl_take isl_union_map
*accesses
)
2973 for (i
= 0; i
< expr
->n_arg
; ++i
)
2974 accesses
= expr_collect_accesses(expr
->args
[i
],
2975 read
, write
, accesses
);
2977 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2978 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
2979 accesses
= isl_union_map_add_map(accesses
,
2980 isl_map_copy(expr
->acc
.access
));
2985 /* Collect and return all read access relations (if "read" is set)
2986 * and/or all write access relations (if "write" is set) in "stmt".
2988 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2989 int read
, int write
, __isl_take isl_space
*dim
)
2991 isl_union_map
*accesses
;
2996 accesses
= isl_union_map_empty(dim
);
2997 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
2998 accesses
= isl_union_map_intersect_domain(accesses
,
2999 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
3004 /* Collect and return all read access relations (if "read" is set)
3005 * and/or all write access relations (if "write" is set) in "scop".
3007 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3008 int read
, int write
)
3011 isl_union_map
*accesses
;
3016 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3018 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3019 isl_union_map
*accesses_i
;
3020 isl_space
*dim
= isl_set_get_space(scop
->context
);
3021 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
3023 accesses
= isl_union_map_union(accesses
, accesses_i
);
3029 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
3031 return scop_collect_accesses(scop
, 1, 0);
3034 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
3036 return scop_collect_accesses(scop
, 0, 1);
3039 /* Collect and return the union of iteration domains in "scop".
3041 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3045 isl_union_set
*domain
;
3050 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3052 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3053 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3054 domain
= isl_union_set_add_set(domain
, domain_i
);
3060 /* Collect and return the schedules of the statements in "scop".
3061 * The range is normalized to the maximal number of scheduling
3064 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3067 isl_map
*schedule_i
;
3068 isl_union_map
*schedule
;
3069 int depth
, max_depth
= 0;
3074 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3076 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3077 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3078 if (depth
> max_depth
)
3082 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3083 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3084 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3085 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3087 for (j
= depth
; j
< max_depth
; ++j
)
3088 schedule_i
= isl_map_fix_si(schedule_i
,
3090 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3096 /* Does expression "expr" write to "id"?
3098 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3103 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3104 int writes
= expr_writes(expr
->args
[i
], id
);
3105 if (writes
< 0 || writes
)
3109 if (expr
->type
!= pet_expr_access
)
3111 if (!expr
->acc
.write
)
3113 if (pet_expr_is_affine(expr
))
3116 write_id
= pet_expr_access_get_id(expr
);
3117 isl_id_free(write_id
);
3122 return write_id
== id
;
3125 /* Does statement "stmt" write to "id"?
3127 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3129 return expr_writes(stmt
->body
, id
);
3132 /* Is there any write access in "scop" that accesses "id"?
3134 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3141 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3142 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3143 if (writes
< 0 || writes
)
3150 /* Add a reference identifier to access expression "expr".
3151 * "user" points to an integer that contains the sequence number
3152 * of the next reference.
3154 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3163 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3164 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3165 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3166 if (!expr
->acc
.ref_id
)
3167 return pet_expr_free(expr
);
3172 /* Add a reference identifier to all access expressions in "stmt".
3173 * "n_ref" points to an integer that contains the sequence number
3174 * of the next reference.
3176 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3183 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3184 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3185 &access_add_ref_id
, n_ref
);
3187 return pet_stmt_free(stmt
);
3190 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3192 return pet_stmt_free(stmt
);
3197 /* Add a reference identifier to all access expressions in "scop".
3199 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3208 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3209 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3210 if (!scop
->stmts
[i
])
3211 return pet_scop_free(scop
);
3217 /* Reset the user pointer on the tuple id and all parameter ids in "set".
3219 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
3223 n
= isl_set_dim(set
, isl_dim_param
);
3224 for (i
= 0; i
< n
; ++i
) {
3225 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
3226 const char *name
= isl_id_get_name(id
);
3227 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
3231 if (!isl_set_is_params(set
) && isl_set_has_tuple_id(set
)) {
3232 isl_id
*id
= isl_set_get_tuple_id(set
);
3233 const char *name
= isl_id_get_name(id
);
3234 set
= isl_set_set_tuple_name(set
, name
);
3241 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
3243 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
3247 n
= isl_map_dim(map
, isl_dim_param
);
3248 for (i
= 0; i
< n
; ++i
) {
3249 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
3250 const char *name
= isl_id_get_name(id
);
3251 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
3255 if (isl_map_has_tuple_id(map
, isl_dim_in
)) {
3256 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_in
);
3257 const char *name
= isl_id_get_name(id
);
3258 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
3262 if (isl_map_has_tuple_id(map
, isl_dim_out
)) {
3263 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_out
);
3264 const char *name
= isl_id_get_name(id
);
3265 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
3272 /* Reset the user pointer on all parameter ids in "array".
3274 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3279 array
->context
= set_anonymize(array
->context
);
3280 array
->extent
= set_anonymize(array
->extent
);
3281 if (!array
->context
|| !array
->extent
)
3282 return pet_array_free(array
);
3287 /* Reset the user pointer on all parameter and tuple ids in
3288 * the access relation of the access expression "expr".
3290 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3292 expr
->acc
.access
= map_anonymize(expr
->acc
.access
);
3293 if (!expr
->acc
.access
)
3294 return pet_expr_free(expr
);
3299 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3301 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3310 stmt
->domain
= set_anonymize(stmt
->domain
);
3311 stmt
->schedule
= map_anonymize(stmt
->schedule
);
3312 if (!stmt
->domain
|| !stmt
->schedule
)
3313 return pet_stmt_free(stmt
);
3315 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3316 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3317 &access_anonymize
, NULL
);
3319 return pet_stmt_free(stmt
);
3322 stmt
->body
= pet_expr_map_access(stmt
->body
,
3323 &access_anonymize
, NULL
);
3325 return pet_stmt_free(stmt
);
3330 /* Reset the user pointer on the tuple ids and all parameter ids
3333 static struct pet_implication
*implication_anonymize(
3334 struct pet_implication
*implication
)
3339 implication
->extension
= map_anonymize(implication
->extension
);
3340 if (!implication
->extension
)
3341 return pet_implication_free(implication
);
3346 /* Reset the user pointer on all parameter and tuple ids in "scop".
3348 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3355 scop
->context
= set_anonymize(scop
->context
);
3356 scop
->context_value
= set_anonymize(scop
->context_value
);
3357 if (!scop
->context
|| !scop
->context_value
)
3358 return pet_scop_free(scop
);
3360 for (i
= 0; i
< scop
->n_array
; ++i
) {
3361 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3362 if (!scop
->arrays
[i
])
3363 return pet_scop_free(scop
);
3366 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3367 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3368 if (!scop
->stmts
[i
])
3369 return pet_scop_free(scop
);
3372 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3373 scop
->implications
[i
] =
3374 implication_anonymize(scop
->implications
[i
]);
3375 if (!scop
->implications
[i
])
3376 return pet_scop_free(scop
);
3382 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3383 * then intersect the range of "map" with the valid set of values.
3385 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
3386 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
3391 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3393 id
= pet_expr_access_get_id(arg
);
3394 space
= isl_space_alloc(ctx
, 0, 0, 1);
3395 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
3396 vb
= isl_union_map_extract_map(value_bounds
, space
);
3397 if (!isl_map_plain_is_empty(vb
))
3398 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
3405 /* Given a set "domain", return a wrapped relation with the given set
3406 * as domain and a range of dimension "n_arg", where each coordinate
3407 * is either unbounded or, if the corresponding element of args is of
3408 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3410 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
3411 unsigned n_arg
, struct pet_expr
**args
,
3412 __isl_keep isl_union_map
*value_bounds
)
3418 map
= isl_map_from_domain(domain
);
3419 space
= isl_map_get_space(map
);
3420 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
3422 for (i
= 0; i
< n_arg
; ++i
) {
3424 struct pet_expr
*arg
= args
[i
];
3426 map_i
= isl_map_universe(isl_space_copy(space
));
3427 if (arg
->type
== pet_expr_access
)
3428 map_i
= access_apply_value_bounds(map_i
, arg
,
3430 map
= isl_map_flat_range_product(map
, map_i
);
3432 isl_space_free(space
);
3434 return isl_map_wrap(map
);
3437 /* Data used in access_gist() callback.
3439 struct pet_access_gist_data
{
3441 isl_union_map
*value_bounds
;
3444 /* Given an expression "expr" of type pet_expr_access, compute
3445 * the gist of the associated access relation with respect to
3446 * data->domain and the bounds on the values of the arguments
3447 * of the expression.
3449 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3451 struct pet_access_gist_data
*data
= user
;
3454 domain
= isl_set_copy(data
->domain
);
3455 if (expr
->n_arg
> 0)
3456 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3457 data
->value_bounds
);
3459 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
3460 if (!expr
->acc
.access
)
3461 return pet_expr_free(expr
);
3466 /* Compute the gist of the iteration domain and all access relations
3467 * of "stmt" based on the constraints on the parameters specified by "context"
3468 * and the constraints on the values of nested accesses specified
3469 * by "value_bounds".
3471 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3472 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3477 struct pet_access_gist_data data
;
3482 data
.domain
= isl_set_copy(stmt
->domain
);
3483 data
.value_bounds
= value_bounds
;
3484 if (stmt
->n_arg
> 0)
3485 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3487 data
.domain
= isl_set_intersect_params(data
.domain
,
3488 isl_set_copy(context
));
3490 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3491 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3492 &access_gist
, &data
);
3497 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3501 isl_set_free(data
.domain
);
3503 space
= isl_set_get_space(stmt
->domain
);
3504 if (isl_space_is_wrapping(space
))
3505 space
= isl_space_domain(isl_space_unwrap(space
));
3506 domain
= isl_set_universe(space
);
3507 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3508 if (stmt
->n_arg
> 0)
3509 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3511 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3513 return pet_stmt_free(stmt
);
3517 isl_set_free(data
.domain
);
3518 return pet_stmt_free(stmt
);
3521 /* Compute the gist of the extent of the array
3522 * based on the constraints on the parameters specified by "context".
3524 static struct pet_array
*array_gist(struct pet_array
*array
,
3525 __isl_keep isl_set
*context
)
3530 array
->extent
= isl_set_gist_params(array
->extent
,
3531 isl_set_copy(context
));
3533 return pet_array_free(array
);
3538 /* Compute the gist of all sets and relations in "scop"
3539 * based on the constraints on the parameters specified by "scop->context"
3540 * and the constraints on the values of nested accesses specified
3541 * by "value_bounds".
3543 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3544 __isl_keep isl_union_map
*value_bounds
)
3551 scop
->context
= isl_set_coalesce(scop
->context
);
3553 return pet_scop_free(scop
);
3555 for (i
= 0; i
< scop
->n_array
; ++i
) {
3556 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3557 if (!scop
->arrays
[i
])
3558 return pet_scop_free(scop
);
3561 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3562 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3564 if (!scop
->stmts
[i
])
3565 return pet_scop_free(scop
);
3571 /* Intersect the context of "scop" with "context".
3572 * To ensure that we don't introduce any unnamed parameters in
3573 * the context of "scop", we first remove the unnamed parameters
3576 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3577 __isl_take isl_set
*context
)
3582 context
= set_project_out_unnamed_params(context
);
3583 scop
->context
= isl_set_intersect(scop
->context
, context
);
3585 return pet_scop_free(scop
);
3589 isl_set_free(context
);
3590 return pet_scop_free(scop
);
3593 /* Drop the current context of "scop". That is, replace the context
3594 * by a universal set.
3596 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3603 space
= isl_set_get_space(scop
->context
);
3604 isl_set_free(scop
->context
);
3605 scop
->context
= isl_set_universe(space
);
3607 return pet_scop_free(scop
);
3612 /* Append "array" to the arrays of "scop".
3614 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3615 struct pet_array
*array
)
3618 struct pet_array
**arrays
;
3620 if (!array
|| !scop
)
3623 ctx
= isl_set_get_ctx(scop
->context
);
3624 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3628 scop
->arrays
= arrays
;
3629 scop
->arrays
[scop
->n_array
] = array
;
3634 pet_array_free(array
);
3635 return pet_scop_free(scop
);
3638 /* Create and return an implication on filter values equal to "satisfied"
3639 * with extension "map".
3641 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3645 struct pet_implication
*implication
;
3649 ctx
= isl_map_get_ctx(map
);
3650 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3654 implication
->extension
= map
;
3655 implication
->satisfied
= satisfied
;
3663 /* Add an implication on filter values equal to "satisfied"
3664 * with extension "map" to "scop".
3666 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3667 __isl_take isl_map
*map
, int satisfied
)
3670 struct pet_implication
*implication
;
3671 struct pet_implication
**implications
;
3673 implication
= new_implication(map
, satisfied
);
3674 if (!scop
|| !implication
)
3677 ctx
= isl_set_get_ctx(scop
->context
);
3678 implications
= isl_realloc_array(ctx
, scop
->implications
,
3679 struct pet_implication
*,
3680 scop
->n_implication
+ 1);
3683 scop
->implications
= implications
;
3684 scop
->implications
[scop
->n_implication
] = implication
;
3685 scop
->n_implication
++;
3689 pet_implication_free(implication
);
3690 return pet_scop_free(scop
);