2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
42 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
44 static char *type_str
[] = {
45 [pet_expr_access
] = "access",
46 [pet_expr_call
] = "call",
47 [pet_expr_cast
] = "cast",
48 [pet_expr_double
] = "double",
49 [pet_expr_unary
] = "unary",
50 [pet_expr_binary
] = "binary",
51 [pet_expr_ternary
] = "ternary"
54 static char *op_str
[] = {
55 [pet_op_add_assign
] = "+=",
56 [pet_op_sub_assign
] = "-=",
57 [pet_op_mul_assign
] = "*=",
58 [pet_op_div_assign
] = "/=",
59 [pet_op_assign
] = "=",
70 [pet_op_post_inc
] = "++",
71 [pet_op_post_dec
] = "--",
72 [pet_op_pre_inc
] = "++",
73 [pet_op_pre_dec
] = "--",
74 [pet_op_address_of
] = "&",
75 [pet_op_kill
] = "kill"
78 /* pet_scop with extra information that is used during parsing and printing.
80 * In particular, we keep track of conditions under which we want
81 * to skip the rest of the current loop iteration (skip[pet_skip_now])
82 * and of conditions under which we want to skip subsequent
83 * loop iterations (skip[pet_skip_later]).
85 * The conditions are represented as index expressions defined
86 * over a zero-dimensiona domain. The index expression is either
87 * a boolean affine expression or an access to a variable, which
88 * is assumed to attain values zero and one. The condition holds
89 * if the variable has value one or if the affine expression
90 * has value one (typically for only part of the parameter space).
92 * A missing condition (skip[type] == NULL) means that we don't want
95 * Additionally, we keep track of the original input file
96 * inside pet_transform_C_source.
101 isl_multi_pw_aff
*skip
[2];
105 const char *pet_op_str(enum pet_op_type op
)
110 int pet_op_is_inc_dec(enum pet_op_type op
)
112 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
113 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
116 const char *pet_type_str(enum pet_expr_type type
)
118 return type_str
[type
];
121 enum pet_op_type
pet_str_op(const char *str
)
125 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
126 if (!strcmp(op_str
[i
], str
))
132 enum pet_expr_type
pet_str_type(const char *str
)
136 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
137 if (!strcmp(type_str
[i
], str
))
143 /* Construct an access pet_expr from an access relation and an index expression.
144 * By default, it is considered to be a read access.
146 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
147 __isl_take isl_multi_pw_aff
*index
)
149 isl_ctx
*ctx
= isl_map_get_ctx(access
);
150 struct pet_expr
*expr
;
152 if (!index
|| !access
)
154 expr
= isl_calloc_type(ctx
, struct pet_expr
);
158 expr
->type
= pet_expr_access
;
159 expr
->acc
.access
= access
;
160 expr
->acc
.index
= index
;
166 isl_map_free(access
);
167 isl_multi_pw_aff_free(index
);
171 /* Construct an access pet_expr from an index expression.
172 * By default, the access is considered to be a read access.
174 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
178 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
179 return pet_expr_from_access_and_index(access
, index
);
182 /* Construct an access pet_expr from an index expression and
183 * the depth of the accessed array.
184 * By default, the access is considered to be a read access.
186 * If the number of indices is smaller than the depth of the array,
187 * then we assume that all elements of the remaining dimensions
190 struct pet_expr
*pet_expr_from_index_and_depth(
191 __isl_take isl_multi_pw_aff
*index
, int depth
)
197 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
200 dim
= isl_map_dim(access
, isl_dim_out
);
202 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
203 "number of indices greater than depth",
204 access
= isl_map_free(access
));
206 return pet_expr_from_access_and_index(access
, index
);
208 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
209 access
= isl_map_add_dims(access
, isl_dim_out
, depth
- dim
);
210 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
212 return pet_expr_from_access_and_index(access
, index
);
214 isl_multi_pw_aff_free(index
);
218 /* Construct a pet_expr that kills the elements specified by
219 * the index expression "index" and the access relation "access".
221 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
222 __isl_take isl_multi_pw_aff
*index
)
225 struct pet_expr
*expr
;
227 if (!access
|| !index
)
230 ctx
= isl_multi_pw_aff_get_ctx(index
);
231 expr
= pet_expr_from_access_and_index(access
, index
);
235 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
237 isl_map_free(access
);
238 isl_multi_pw_aff_free(index
);
242 /* Construct a unary pet_expr that performs "op" on "arg".
244 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
245 struct pet_expr
*arg
)
247 struct pet_expr
*expr
;
251 expr
= isl_alloc_type(ctx
, struct pet_expr
);
255 expr
->type
= pet_expr_unary
;
258 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
261 expr
->args
[pet_un_arg
] = arg
;
269 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
271 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
272 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
274 struct pet_expr
*expr
;
278 expr
= isl_alloc_type(ctx
, struct pet_expr
);
282 expr
->type
= pet_expr_binary
;
285 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
288 expr
->args
[pet_bin_lhs
] = lhs
;
289 expr
->args
[pet_bin_rhs
] = rhs
;
298 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
300 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
301 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
303 struct pet_expr
*expr
;
305 if (!cond
|| !lhs
|| !rhs
)
307 expr
= isl_alloc_type(ctx
, struct pet_expr
);
311 expr
->type
= pet_expr_ternary
;
313 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
316 expr
->args
[pet_ter_cond
] = cond
;
317 expr
->args
[pet_ter_true
] = lhs
;
318 expr
->args
[pet_ter_false
] = rhs
;
328 /* Construct a call pet_expr that calls function "name" with "n_arg"
329 * arguments. The caller is responsible for filling in the arguments.
331 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
334 struct pet_expr
*expr
;
336 expr
= isl_alloc_type(ctx
, struct pet_expr
);
340 expr
->type
= pet_expr_call
;
342 expr
->name
= strdup(name
);
343 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
344 if (!expr
->name
|| !expr
->args
)
345 return pet_expr_free(expr
);
350 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
352 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
353 struct pet_expr
*arg
)
355 struct pet_expr
*expr
;
360 expr
= isl_alloc_type(ctx
, struct pet_expr
);
364 expr
->type
= pet_expr_cast
;
366 expr
->type_name
= strdup(type_name
);
367 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
368 if (!expr
->type_name
|| !expr
->args
)
380 /* Construct a pet_expr that represents the double "d".
382 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
384 struct pet_expr
*expr
;
386 expr
= isl_calloc_type(ctx
, struct pet_expr
);
390 expr
->type
= pet_expr_double
;
392 expr
->d
.s
= strdup(s
);
394 return pet_expr_free(expr
);
399 void *pet_expr_free(struct pet_expr
*expr
)
406 for (i
= 0; i
< expr
->n_arg
; ++i
)
407 pet_expr_free(expr
->args
[i
]);
410 switch (expr
->type
) {
411 case pet_expr_access
:
412 isl_id_free(expr
->acc
.ref_id
);
413 isl_map_free(expr
->acc
.access
);
414 isl_multi_pw_aff_free(expr
->acc
.index
);
420 free(expr
->type_name
);
422 case pet_expr_double
:
426 case pet_expr_binary
:
427 case pet_expr_ternary
:
435 static void expr_dump(struct pet_expr
*expr
, int indent
)
442 fprintf(stderr
, "%*s", indent
, "");
444 switch (expr
->type
) {
445 case pet_expr_double
:
446 fprintf(stderr
, "%s\n", expr
->d
.s
);
448 case pet_expr_access
:
449 isl_id_dump(expr
->acc
.ref_id
);
450 fprintf(stderr
, "%*s", indent
, "");
451 isl_map_dump(expr
->acc
.access
);
452 fprintf(stderr
, "%*s", indent
, "");
453 isl_multi_pw_aff_dump(expr
->acc
.index
);
454 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
456 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
457 "", expr
->acc
.write
);
458 for (i
= 0; i
< expr
->n_arg
; ++i
)
459 expr_dump(expr
->args
[i
], indent
+ 2);
462 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
463 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
465 case pet_expr_binary
:
466 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
467 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
468 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
470 case pet_expr_ternary
:
471 fprintf(stderr
, "?:\n");
472 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
473 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
474 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
477 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
478 for (i
= 0; i
< expr
->n_arg
; ++i
)
479 expr_dump(expr
->args
[i
], indent
+ 2);
482 fprintf(stderr
, "(%s)\n", expr
->type_name
);
483 for (i
= 0; i
< expr
->n_arg
; ++i
)
484 expr_dump(expr
->args
[i
], indent
+ 2);
489 void pet_expr_dump(struct pet_expr
*expr
)
494 /* Does "expr" represent an access to an unnamed space, i.e.,
495 * does it represent an affine expression?
497 int pet_expr_is_affine(struct pet_expr
*expr
)
503 if (expr
->type
!= pet_expr_access
)
506 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
513 /* Return the identifier of the array accessed by "expr".
515 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
519 if (expr
->type
!= pet_expr_access
)
521 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
524 /* Align the parameters of expr->acc.index and expr->acc.access.
526 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
530 if (expr
->type
!= pet_expr_access
)
531 return pet_expr_free(expr
);
533 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
534 isl_multi_pw_aff_get_space(expr
->acc
.index
));
535 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
536 isl_map_get_space(expr
->acc
.access
));
537 if (!expr
->acc
.access
|| !expr
->acc
.index
)
538 return pet_expr_free(expr
);
543 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
545 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
549 if (expr
->type
!= pet_expr_access
)
552 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
555 /* Return 1 if the two pet_exprs are equivalent.
557 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
561 if (!expr1
|| !expr2
)
564 if (expr1
->type
!= expr2
->type
)
566 if (expr1
->n_arg
!= expr2
->n_arg
)
568 for (i
= 0; i
< expr1
->n_arg
; ++i
)
569 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
571 switch (expr1
->type
) {
572 case pet_expr_double
:
573 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
575 if (expr1
->d
.val
!= expr2
->d
.val
)
578 case pet_expr_access
:
579 if (expr1
->acc
.read
!= expr2
->acc
.read
)
581 if (expr1
->acc
.write
!= expr2
->acc
.write
)
583 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
585 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
587 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
589 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
591 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
596 case pet_expr_binary
:
597 case pet_expr_ternary
:
598 if (expr1
->op
!= expr2
->op
)
602 if (strcmp(expr1
->name
, expr2
->name
))
606 if (strcmp(expr1
->type_name
, expr2
->type_name
))
614 /* Add extra conditions on the parameters to all access relations in "expr".
616 * The conditions are not added to the index expression. Instead, they
617 * are used to try and simplifty the index expression.
619 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
620 __isl_take isl_set
*cond
)
627 for (i
= 0; i
< expr
->n_arg
; ++i
) {
628 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
634 if (expr
->type
== pet_expr_access
) {
635 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
637 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
638 expr
->acc
.index
, isl_set_copy(cond
));
639 if (!expr
->acc
.access
|| !expr
->acc
.index
)
647 return pet_expr_free(expr
);
650 /* Modify all expressions of type pet_expr_access in "expr"
651 * by calling "fn" on them.
653 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
654 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
662 for (i
= 0; i
< expr
->n_arg
; ++i
) {
663 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
665 return pet_expr_free(expr
);
668 if (expr
->type
== pet_expr_access
)
669 expr
= fn(expr
, user
);
674 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
676 * Return -1 on error (where fn return a negative value is treated as an error).
677 * Otherwise return 0.
679 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
680 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
687 for (i
= 0; i
< expr
->n_arg
; ++i
)
688 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
691 if (expr
->type
== pet_expr_access
)
692 return fn(expr
, user
);
697 /* Modify the access relation and index expression
698 * of the given access expression
699 * based on the given iteration space transformation.
700 * In particular, precompose the access relation and index expression
701 * with the update function.
703 * If the access has any arguments then the domain of the access relation
704 * is a wrapped mapping from the iteration space to the space of
705 * argument values. We only need to change the domain of this wrapped
706 * mapping, so we extend the input transformation with an identity mapping
707 * on the space of argument values.
709 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
711 isl_multi_pw_aff
*update
= user
;
714 update
= isl_multi_pw_aff_copy(update
);
716 space
= isl_map_get_space(expr
->acc
.access
);
717 space
= isl_space_domain(space
);
718 if (!isl_space_is_wrapping(space
))
719 isl_space_free(space
);
721 isl_multi_pw_aff
*id
;
722 space
= isl_space_unwrap(space
);
723 space
= isl_space_range(space
);
724 space
= isl_space_map_from_set(space
);
725 id
= isl_multi_pw_aff_identity(space
);
726 update
= isl_multi_pw_aff_product(update
, id
);
729 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
731 isl_multi_pw_aff_copy(update
));
732 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
733 expr
->acc
.index
, update
);
734 if (!expr
->acc
.access
|| !expr
->acc
.index
)
735 return pet_expr_free(expr
);
740 /* Modify all access relations in "expr" by precomposing them with
741 * the given iteration space transformation.
743 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
744 __isl_take isl_multi_pw_aff
*update
)
746 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
747 isl_multi_pw_aff_free(update
);
751 /* Construct a pet_stmt with given line number and statement
752 * number from a pet_expr.
753 * The initial iteration domain is the zero-dimensional universe.
754 * The name of the domain is given by "label" if it is non-NULL.
755 * Otherwise, the name is constructed as S_<id>.
756 * The domains of all access relations are modified to refer
757 * to the statement iteration domain.
759 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
760 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
762 struct pet_stmt
*stmt
;
766 isl_multi_pw_aff
*add_name
;
772 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
776 dim
= isl_space_set_alloc(ctx
, 0, 0);
778 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
780 snprintf(name
, sizeof(name
), "S_%d", id
);
781 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
783 dom
= isl_set_universe(isl_space_copy(dim
));
784 sched
= isl_map_from_domain(isl_set_copy(dom
));
786 dim
= isl_space_from_domain(dim
);
787 add_name
= isl_multi_pw_aff_zero(dim
);
788 expr
= expr_update_domain(expr
, add_name
);
792 stmt
->schedule
= sched
;
795 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
796 return pet_stmt_free(stmt
);
801 return pet_expr_free(expr
);
804 void *pet_stmt_free(struct pet_stmt
*stmt
)
811 isl_set_free(stmt
->domain
);
812 isl_map_free(stmt
->schedule
);
813 pet_expr_free(stmt
->body
);
815 for (i
= 0; i
< stmt
->n_arg
; ++i
)
816 pet_expr_free(stmt
->args
[i
]);
823 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
830 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
831 fprintf(stderr
, "%*s", indent
, "");
832 isl_set_dump(stmt
->domain
);
833 fprintf(stderr
, "%*s", indent
, "");
834 isl_map_dump(stmt
->schedule
);
835 expr_dump(stmt
->body
, indent
);
836 for (i
= 0; i
< stmt
->n_arg
; ++i
)
837 expr_dump(stmt
->args
[i
], indent
+ 2);
840 void pet_stmt_dump(struct pet_stmt
*stmt
)
845 struct pet_array
*pet_array_free(struct pet_array
*array
)
850 isl_set_free(array
->context
);
851 isl_set_free(array
->extent
);
852 isl_set_free(array
->value_bounds
);
853 free(array
->element_type
);
859 void pet_array_dump(struct pet_array
*array
)
864 isl_set_dump(array
->context
);
865 isl_set_dump(array
->extent
);
866 isl_set_dump(array
->value_bounds
);
867 fprintf(stderr
, "%s %s\n", array
->element_type
,
868 array
->live_out
? "live-out" : "");
871 /* Alloc a pet_scop structure, with extra room for information that
872 * is only used during parsing.
874 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
876 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
879 /* Construct a pet_scop with room for n statements.
881 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
884 struct pet_scop
*scop
;
886 scop
= pet_scop_alloc(ctx
);
890 space
= isl_space_params_alloc(ctx
, 0);
891 scop
->context
= isl_set_universe(isl_space_copy(space
));
892 scop
->context_value
= isl_set_universe(space
);
893 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
894 if (!scop
->context
|| !scop
->stmts
)
895 return pet_scop_free(scop
);
902 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
904 return scop_alloc(ctx
, 0);
907 /* Update "context" with respect to the valid parameter values for "access".
909 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
910 __isl_take isl_set
*context
)
912 context
= isl_set_intersect(context
,
913 isl_map_params(isl_map_copy(access
)));
917 /* Update "context" with respect to the valid parameter values for "expr".
919 * If "expr" represents a ternary operator, then a parameter value
920 * needs to be valid for the condition and for at least one of the
921 * remaining two arguments.
922 * If the condition is an affine expression, then we can be a bit more specific.
923 * The parameter then has to be valid for the second argument for
924 * non-zero accesses and valid for the third argument for zero accesses.
926 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
927 __isl_take isl_set
*context
)
931 if (expr
->type
== pet_expr_ternary
) {
933 isl_set
*context1
, *context2
;
935 is_aff
= pet_expr_is_affine(expr
->args
[0]);
939 context
= expr_extract_context(expr
->args
[0], context
);
940 context1
= expr_extract_context(expr
->args
[1],
941 isl_set_copy(context
));
942 context2
= expr_extract_context(expr
->args
[2], context
);
948 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
949 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
950 zero_set
= isl_map_params(access
);
951 context1
= isl_set_subtract(context1
,
952 isl_set_copy(zero_set
));
953 context2
= isl_set_intersect(context2
, zero_set
);
956 context
= isl_set_union(context1
, context2
);
957 context
= isl_set_coalesce(context
);
962 for (i
= 0; i
< expr
->n_arg
; ++i
)
963 context
= expr_extract_context(expr
->args
[i
], context
);
965 if (expr
->type
== pet_expr_access
)
966 context
= access_extract_context(expr
->acc
.access
, context
);
970 isl_set_free(context
);
974 /* Update "context" with respect to the valid parameter values for "stmt".
976 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
977 __isl_take isl_set
*context
)
981 for (i
= 0; i
< stmt
->n_arg
; ++i
)
982 context
= expr_extract_context(stmt
->args
[i
], context
);
984 context
= expr_extract_context(stmt
->body
, context
);
989 /* Construct a pet_scop that contains the given pet_stmt.
991 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
993 struct pet_scop
*scop
;
998 scop
= scop_alloc(ctx
, 1);
1002 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
1006 scop
->stmts
[0] = stmt
;
1010 pet_stmt_free(stmt
);
1011 pet_scop_free(scop
);
1015 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1016 * does it represent an affine expression?
1018 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
1022 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
1029 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1031 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
1032 __isl_take isl_set
*dom
)
1035 pa
= isl_set_indicator_function(set
);
1036 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1040 /* Return "lhs || rhs", defined on the shared definition domain.
1042 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1043 __isl_take isl_pw_aff
*rhs
)
1048 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1049 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1050 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1051 isl_pw_aff_non_zero_set(rhs
));
1052 cond
= isl_set_coalesce(cond
);
1053 return indicator_function(cond
, dom
);
1056 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1057 * ext may be equal to either ext1 or ext2.
1059 * The two skips that need to be combined are assumed to be affine expressions.
1061 * We need to skip in ext if we need to skip in either ext1 or ext2.
1062 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1064 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1065 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1068 isl_pw_aff
*skip
, *skip1
, *skip2
;
1072 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1074 if (!ext1
->skip
[type
]) {
1077 ext
->skip
[type
] = ext2
->skip
[type
];
1078 ext2
->skip
[type
] = NULL
;
1081 if (!ext2
->skip
[type
]) {
1084 ext
->skip
[type
] = ext1
->skip
[type
];
1085 ext1
->skip
[type
] = NULL
;
1089 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1090 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1091 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1092 isl_error_internal
, "can only combine affine skips",
1093 return pet_scop_free(&ext
->scop
));
1095 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1096 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1097 skip
= pw_aff_or(skip1
, skip2
);
1098 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1099 ext1
->skip
[type
] = NULL
;
1100 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1101 ext2
->skip
[type
] = NULL
;
1102 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1103 if (!ext
->skip
[type
])
1104 return pet_scop_free(&ext
->scop
);
1109 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1110 * where type takes on the values pet_skip_now and pet_skip_later.
1111 * scop may be equal to either scop1 or scop2.
1113 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1114 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1116 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1117 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1118 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1120 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1121 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1125 /* Update scop->start and scop->end to include the region from "start"
1126 * to "end". In particular, if scop->end == 0, then "scop" does not
1127 * have any offset information yet and we simply take the information
1128 * from "start" and "end". Otherwise, we update the fields if the
1129 * region from "start" to "end" is not already included.
1131 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1132 unsigned start
, unsigned end
)
1136 if (scop
->end
== 0) {
1137 scop
->start
= start
;
1140 if (start
< scop
->start
)
1141 scop
->start
= start
;
1142 if (end
> scop
->end
)
1149 /* Does "implication" appear in the list of implications of "scop"?
1151 static int is_known_implication(struct pet_scop
*scop
,
1152 struct pet_implication
*implication
)
1156 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1157 struct pet_implication
*pi
= scop
->implications
[i
];
1160 if (pi
->satisfied
!= implication
->satisfied
)
1162 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1172 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1173 * in "scop", removing duplicates (i.e., implications in "scop2" that
1174 * already appear in "scop1").
1176 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1177 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1184 if (scop2
->n_implication
== 0) {
1185 scop
->n_implication
= scop1
->n_implication
;
1186 scop
->implications
= scop1
->implications
;
1187 scop1
->n_implication
= 0;
1188 scop1
->implications
= NULL
;
1192 if (scop1
->n_implication
== 0) {
1193 scop
->n_implication
= scop2
->n_implication
;
1194 scop
->implications
= scop2
->implications
;
1195 scop2
->n_implication
= 0;
1196 scop2
->implications
= NULL
;
1200 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1201 scop1
->n_implication
+ scop2
->n_implication
);
1202 if (!scop
->implications
)
1203 return pet_scop_free(scop
);
1205 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1206 scop
->implications
[i
] = scop1
->implications
[i
];
1207 scop1
->implications
[i
] = NULL
;
1210 scop
->n_implication
= scop1
->n_implication
;
1211 j
= scop1
->n_implication
;
1212 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1215 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1217 return pet_scop_free(scop
);
1220 scop
->implications
[j
++] = scop2
->implications
[i
];
1221 scop2
->implications
[i
] = NULL
;
1223 scop
->n_implication
= j
;
1228 /* Combine the offset information of "scop1" and "scop2" into "scop".
1230 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1231 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1234 scop
= pet_scop_update_start_end(scop
,
1235 scop1
->start
, scop1
->end
);
1237 scop
= pet_scop_update_start_end(scop
,
1238 scop2
->start
, scop2
->end
);
1242 /* Construct a pet_scop that contains the offset information,
1243 * arrays, statements and skip information in "scop1" and "scop2".
1245 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1246 struct pet_scop
*scop2
)
1249 struct pet_scop
*scop
= NULL
;
1251 if (!scop1
|| !scop2
)
1254 if (scop1
->n_stmt
== 0) {
1255 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1256 pet_scop_free(scop1
);
1260 if (scop2
->n_stmt
== 0) {
1261 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1262 pet_scop_free(scop2
);
1266 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1270 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1271 scop1
->n_array
+ scop2
->n_array
);
1274 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1276 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1277 scop
->stmts
[i
] = scop1
->stmts
[i
];
1278 scop1
->stmts
[i
] = NULL
;
1281 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1282 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1283 scop2
->stmts
[i
] = NULL
;
1286 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1287 scop
->arrays
[i
] = scop1
->arrays
[i
];
1288 scop1
->arrays
[i
] = NULL
;
1291 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1292 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1293 scop2
->arrays
[i
] = NULL
;
1296 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1297 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1298 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1299 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1300 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1302 pet_scop_free(scop1
);
1303 pet_scop_free(scop2
);
1306 pet_scop_free(scop1
);
1307 pet_scop_free(scop2
);
1308 pet_scop_free(scop
);
1312 /* Apply the skip condition "skip" to "scop".
1313 * That is, make sure "scop" is not executed when the condition holds.
1315 * If "skip" is an affine expression, we add the conditions under
1316 * which the expression is zero to the iteration domains.
1317 * Otherwise, we add a filter on the variable attaining the value zero.
1319 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1320 __isl_take isl_multi_pw_aff
*skip
)
1329 is_aff
= multi_pw_aff_is_affine(skip
);
1334 return pet_scop_filter(scop
, skip
, 0);
1336 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1337 isl_multi_pw_aff_free(skip
);
1338 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1339 scop
= pet_scop_restrict(scop
, zero
);
1343 isl_multi_pw_aff_free(skip
);
1344 return pet_scop_free(scop
);
1347 /* Construct a pet_scop that contains the arrays, statements and
1348 * skip information in "scop1" and "scop2", where the two scops
1349 * are executed "in sequence". That is, breaks and continues
1350 * in scop1 have an effect on scop2.
1352 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1353 struct pet_scop
*scop2
)
1355 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1356 scop2
= restrict_skip(scop2
,
1357 pet_scop_get_skip(scop1
, pet_skip_now
));
1358 return pet_scop_add(ctx
, scop1
, scop2
);
1361 /* Construct a pet_scop that contains the arrays, statements and
1362 * skip information in "scop1" and "scop2", where the two scops
1363 * are executed "in parallel". That is, any break or continue
1364 * in scop1 has no effect on scop2.
1366 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1367 struct pet_scop
*scop2
)
1369 return pet_scop_add(ctx
, scop1
, scop2
);
1372 void *pet_implication_free(struct pet_implication
*implication
)
1379 isl_map_free(implication
->extension
);
1385 void *pet_scop_free(struct pet_scop
*scop
)
1388 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1392 isl_set_free(scop
->context
);
1393 isl_set_free(scop
->context_value
);
1395 for (i
= 0; i
< scop
->n_array
; ++i
)
1396 pet_array_free(scop
->arrays
[i
]);
1399 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1400 pet_stmt_free(scop
->stmts
[i
]);
1402 if (scop
->implications
)
1403 for (i
= 0; i
< scop
->n_implication
; ++i
)
1404 pet_implication_free(scop
->implications
[i
]);
1405 free(scop
->implications
);
1406 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1407 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1412 void pet_implication_dump(struct pet_implication
*implication
)
1417 fprintf(stderr
, "%d\n", implication
->satisfied
);
1418 isl_map_dump(implication
->extension
);
1421 void pet_scop_dump(struct pet_scop
*scop
)
1424 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1429 isl_set_dump(scop
->context
);
1430 isl_set_dump(scop
->context_value
);
1431 for (i
= 0; i
< scop
->n_array
; ++i
)
1432 pet_array_dump(scop
->arrays
[i
]);
1433 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1434 pet_stmt_dump(scop
->stmts
[i
]);
1435 for (i
= 0; i
< scop
->n_implication
; ++i
)
1436 pet_implication_dump(scop
->implications
[i
]);
1439 fprintf(stderr
, "skip\n");
1440 isl_multi_pw_aff_dump(ext
->skip
[0]);
1441 isl_multi_pw_aff_dump(ext
->skip
[1]);
1445 /* Return 1 if the two pet_arrays are equivalent.
1447 * We don't compare element_size as this may be target dependent.
1449 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1451 if (!array1
|| !array2
)
1454 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1456 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1458 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1460 if (array1
->value_bounds
&&
1461 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1463 if (strcmp(array1
->element_type
, array2
->element_type
))
1465 if (array1
->live_out
!= array2
->live_out
)
1467 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1469 if (array1
->declared
!= array2
->declared
)
1471 if (array1
->exposed
!= array2
->exposed
)
1477 /* Return 1 if the two pet_stmts are equivalent.
1479 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1483 if (!stmt1
|| !stmt2
)
1486 if (stmt1
->line
!= stmt2
->line
)
1488 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1490 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1492 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1494 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1496 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1497 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1504 /* Return 1 if the two pet_implications are equivalent.
1506 int pet_implication_is_equal(struct pet_implication
*implication1
,
1507 struct pet_implication
*implication2
)
1509 if (!implication1
|| !implication2
)
1512 if (implication1
->satisfied
!= implication2
->satisfied
)
1514 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1520 /* Return 1 if the two pet_scops are equivalent.
1522 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1526 if (!scop1
|| !scop2
)
1529 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1531 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1534 if (scop1
->n_array
!= scop2
->n_array
)
1536 for (i
= 0; i
< scop1
->n_array
; ++i
)
1537 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1540 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1542 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1543 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1546 if (scop1
->n_implication
!= scop2
->n_implication
)
1548 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1549 if (!pet_implication_is_equal(scop1
->implications
[i
],
1550 scop2
->implications
[i
]))
1556 /* Prefix the schedule of "stmt" with an extra dimension with constant
1559 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1564 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1565 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1566 if (!stmt
->schedule
)
1567 return pet_stmt_free(stmt
);
1572 /* Prefix the schedules of all statements in "scop" with an extra
1573 * dimension with constant value "pos".
1575 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1582 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1583 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1584 if (!scop
->stmts
[i
])
1585 return pet_scop_free(scop
);
1591 /* Given a set with a parameter at "param_pos" that refers to the
1592 * iterator, "move" the iterator to the first set dimension.
1593 * That is, essentially equate the parameter to the first set dimension
1594 * and then project it out.
1596 * The first set dimension may however refer to a virtual iterator,
1597 * while the parameter refers to the "real" iterator.
1598 * We therefore need to take into account the affine expression "iv_map", which
1599 * expresses the real iterator in terms of the virtual iterator.
1600 * In particular, we equate the set dimension to the input of the map
1601 * and the parameter to the output of the map and then project out
1602 * everything we don't need anymore.
1604 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1605 int param_pos
, __isl_take isl_aff
*iv_map
)
1607 isl_map
*map
, *map2
;
1608 map
= isl_map_from_domain(set
);
1609 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1610 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1611 map2
= isl_map_from_aff(iv_map
);
1612 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1613 map
= isl_map_apply_range(map
, map2
);
1614 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1615 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1616 return isl_map_domain(map
);
1619 /* Data used in embed_access.
1620 * extend adds an iterator to the iteration domain (through precomposition).
1621 * iv_map expresses the real iterator in terms of the virtual iterator
1622 * var_id represents the induction variable of the corresponding loop
1624 struct pet_embed_access
{
1625 isl_multi_pw_aff
*extend
;
1630 /* Given an index expression, return an expression for the outer iterator.
1632 static __isl_give isl_aff
*index_outer_iterator(
1633 __isl_take isl_multi_pw_aff
*index
)
1636 isl_local_space
*ls
;
1638 space
= isl_multi_pw_aff_get_domain_space(index
);
1639 isl_multi_pw_aff_free(index
);
1641 ls
= isl_local_space_from_space(space
);
1642 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1645 /* Replace an index expression that references the new (outer) iterator variable
1646 * by one that references the corresponding (real) iterator.
1648 * The input index expression is of the form
1650 * { S[i',...] -> i[] }
1652 * where i' refers to the virtual iterator.
1654 * iv_map is of the form
1658 * Return the index expression
1660 * { S[i',...] -> [i] }
1662 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1663 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1668 aff
= index_outer_iterator(index
);
1669 space
= isl_aff_get_space(aff
);
1670 iv_map
= isl_aff_align_params(iv_map
, space
);
1671 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1673 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1676 /* Given an index expression "index" that refers to the (real) iterator
1677 * through the parameter at position "pos", plug in "iv_map", expressing
1678 * the real iterator in terms of the virtual (outer) iterator.
1680 * In particular, the index expression is of the form
1682 * [..., i, ...] -> { S[i',...] -> ... i ... }
1684 * where i refers to the real iterator and i' refers to the virtual iterator.
1686 * iv_map is of the form
1690 * Return the index expression
1692 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1695 * We first move the parameter to the input
1697 * [..., ...] -> { [i, i',...] -> ... i ... }
1701 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1703 * and then combine the two to obtain the desired result.
1705 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1706 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1708 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1711 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1712 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1713 isl_dim_param
, pos
, 1);
1715 space
= isl_space_map_from_set(space
);
1716 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1717 iv_map
= isl_aff_align_params(iv_map
, space
);
1718 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1719 ma
= isl_multi_aff_flat_range_product(
1720 isl_multi_aff_from_aff(iv_map
), ma
);
1721 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1726 /* Embed the given index expression in an extra outer loop.
1727 * The domain of the index expression has already been updated.
1729 * If the access refers to the induction variable, then it is
1730 * turned into an access to the set of integers with index (and value)
1731 * equal to the induction variable.
1733 * If the accessed array is a virtual array (with user
1734 * pointer equal to NULL), as created by create_test_index,
1735 * then it is extended along with the domain of the index expression.
1737 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1738 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1740 isl_id
*array_id
= NULL
;
1743 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1744 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1745 if (array_id
== data
->var_id
) {
1746 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1747 } else if (array_id
&& !isl_id_get_user(array_id
)) {
1749 isl_multi_pw_aff
*mpa
;
1751 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1752 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1753 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1754 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1755 isl_id_copy(array_id
));
1757 isl_id_free(array_id
);
1759 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1760 isl_dim_param
, data
->var_id
);
1762 index
= index_internalize_iv(index
, pos
,
1763 isl_aff_copy(data
->iv_map
));
1764 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1765 isl_id_copy(data
->var_id
));
1770 /* Embed the given access relation in an extra outer loop.
1771 * The domain of the access relation has already been updated.
1773 * If the access refers to the induction variable, then it is
1774 * turned into an access to the set of integers with index (and value)
1775 * equal to the induction variable.
1777 * If the induction variable appears in the constraints (as a parameter),
1778 * then the parameter is equated to the newly introduced iteration
1779 * domain dimension and subsequently projected out.
1781 * Similarly, if the accessed array is a virtual array (with user
1782 * pointer equal to NULL), as created by create_test_index,
1783 * then it is extended along with the domain of the access.
1785 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1786 struct pet_embed_access
*data
)
1788 isl_id
*array_id
= NULL
;
1791 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1792 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1793 if (array_id
== data
->var_id
||
1794 (array_id
&& !isl_id_get_user(array_id
))) {
1795 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1796 access
= isl_map_equate(access
,
1797 isl_dim_in
, 0, isl_dim_out
, 0);
1798 if (array_id
== data
->var_id
)
1799 access
= isl_map_apply_range(access
,
1800 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1802 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1803 isl_id_copy(array_id
));
1805 isl_id_free(array_id
);
1807 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1809 isl_set
*set
= isl_map_wrap(access
);
1810 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1811 access
= isl_set_unwrap(set
);
1813 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1814 isl_id_copy(data
->var_id
));
1819 /* Given an access expression, embed the associated access relation and
1820 * index expression in an extra outer loop.
1822 * We first update the domains to insert the extra dimension and
1823 * then update the access relation and index expression to take
1824 * into account the mapping "iv_map" from virtual iterator
1827 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1830 struct pet_embed_access
*data
= user
;
1832 expr
= update_domain(expr
, data
->extend
);
1836 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
1837 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
1838 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1839 return pet_expr_free(expr
);
1844 /* Embed all access subexpressions of "expr" in an extra loop.
1845 * "extend" inserts an outer loop iterator in the iteration domains
1846 * (through precomposition).
1847 * "iv_map" expresses the real iterator in terms of the virtual iterator
1848 * "var_id" represents the induction variable.
1850 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1851 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1852 __isl_keep isl_id
*var_id
)
1854 struct pet_embed_access data
=
1855 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1857 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1858 isl_aff_free(iv_map
);
1859 isl_multi_pw_aff_free(extend
);
1863 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1864 * "dom" and schedule "sched". "var_id" represents the induction variable
1865 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1866 * That is, it expresses the iterator that some of the parameters in "stmt"
1867 * may refer to in terms of the iterator used in "dom" and
1868 * the domain of "sched".
1870 * The iteration domain and schedule of the statement are updated
1871 * according to the iteration domain and schedule of the new loop.
1872 * If stmt->domain is a wrapped map, then the iteration domain
1873 * is the domain of this map, so we need to be careful to adjust
1876 * If the induction variable appears in the constraints (as a parameter)
1877 * of the current iteration domain or the schedule of the statement,
1878 * then the parameter is equated to the newly introduced iteration
1879 * domain dimension and subsequently projected out.
1881 * Finally, all access relations are updated based on the extra loop.
1883 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1884 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1885 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1891 isl_multi_pw_aff
*extend
;
1896 if (isl_set_is_wrapping(stmt
->domain
)) {
1901 map
= isl_set_unwrap(stmt
->domain
);
1902 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1903 ran_dim
= isl_space_range(isl_map_get_space(map
));
1904 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1905 isl_set_universe(ran_dim
));
1906 map
= isl_map_flat_domain_product(ext
, map
);
1907 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1908 isl_id_copy(stmt_id
));
1909 dim
= isl_space_domain(isl_map_get_space(map
));
1910 stmt
->domain
= isl_map_wrap(map
);
1912 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1913 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1915 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1916 isl_id_copy(stmt_id
));
1917 dim
= isl_set_get_space(stmt
->domain
);
1920 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1922 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1923 isl_aff_copy(iv_map
));
1925 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1926 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1927 isl_dim_in
, stmt_id
);
1929 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1931 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1932 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1933 stmt
->schedule
= isl_set_unwrap(set
);
1936 dim
= isl_space_map_from_set(dim
);
1937 extend
= isl_multi_pw_aff_identity(dim
);
1938 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
1939 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
1940 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
1941 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1942 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1943 isl_multi_pw_aff_copy(extend
),
1944 isl_aff_copy(iv_map
), var_id
);
1945 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1948 isl_id_free(var_id
);
1950 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1952 return pet_stmt_free(stmt
);
1953 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1954 return pet_stmt_free(stmt
);
1958 isl_map_free(sched
);
1959 isl_aff_free(iv_map
);
1960 isl_id_free(var_id
);
1964 /* Embed the given pet_array in an extra outer loop with iteration domain
1966 * This embedding only has an effect on virtual arrays (those with
1967 * user pointer equal to NULL), which need to be extended along with
1968 * the iteration domain.
1970 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1971 __isl_take isl_set
*dom
)
1973 isl_id
*array_id
= NULL
;
1978 if (isl_set_has_tuple_id(array
->extent
))
1979 array_id
= isl_set_get_tuple_id(array
->extent
);
1981 if (array_id
&& !isl_id_get_user(array_id
)) {
1982 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1983 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1985 return pet_array_free(array
);
1988 isl_id_free(array_id
);
1997 /* Project out all unnamed parameters from "set" and return the result.
1999 static __isl_give isl_set
*set_project_out_unnamed_params(
2000 __isl_take isl_set
*set
)
2004 n
= isl_set_dim(set
, isl_dim_param
);
2005 for (i
= n
- 1; i
>= 0; --i
) {
2006 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
2008 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
2014 /* Update the context with respect to an embedding into a loop
2015 * with iteration domain "dom" and induction variable "id".
2016 * "iv_map" expresses the real iterator (parameter "id") in terms
2017 * of a possibly virtual iterator (used in "dom").
2019 * If the current context is independent of "id", we don't need
2021 * Otherwise, a parameter value is invalid for the embedding if
2022 * any of the corresponding iterator values is invalid.
2023 * That is, a parameter value is valid only if all the corresponding
2024 * iterator values are valid.
2025 * We therefore compute the set of parameters
2027 * forall i in dom : valid (i)
2031 * not exists i in dom : not valid(i)
2035 * not exists i in dom \ valid(i)
2037 * Before we subtract valid(i) from dom, we first need to substitute
2038 * the real iterator for the virtual iterator.
2040 * If there are any unnamed parameters in "dom", then we consider
2041 * a parameter value to be valid if it is valid for any value of those
2042 * unnamed parameters. They are therefore projected out at the end.
2044 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
2045 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
2046 __isl_keep isl_id
*id
)
2051 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
2055 context
= isl_set_from_params(context
);
2056 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
2057 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
2058 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
2059 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
2060 context
= isl_set_preimage_multi_aff(context
, ma
);
2061 context
= isl_set_subtract(isl_set_copy(dom
), context
);
2062 context
= isl_set_params(context
);
2063 context
= isl_set_complement(context
);
2064 context
= set_project_out_unnamed_params(context
);
2068 /* Update the implication with respect to an embedding into a loop
2069 * with iteration domain "dom".
2071 * Since embed_access extends virtual arrays along with the domain
2072 * of the access, we need to do the same with domain and range
2073 * of the implication. Since the original implication is only valid
2074 * within a given iteration of the loop, the extended implication
2075 * maps the extra array dimension corresponding to the extra loop
2078 static struct pet_implication
*pet_implication_embed(
2079 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
2087 map
= isl_set_identity(dom
);
2088 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
2089 map
= isl_map_flat_product(map
, implication
->extension
);
2090 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
2091 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
2092 implication
->extension
= map
;
2093 if (!implication
->extension
)
2094 return pet_implication_free(implication
);
2102 /* Embed all statements and arrays in "scop" in an extra outer loop
2103 * with iteration domain "dom" and schedule "sched".
2104 * "id" represents the induction variable of the loop.
2105 * "iv_map" maps a possibly virtual iterator to the real iterator.
2106 * That is, it expresses the iterator that some of the parameters in "scop"
2107 * may refer to in terms of the iterator used in "dom" and
2108 * the domain of "sched".
2110 * Any skip conditions within the loop have no effect outside of the loop.
2111 * The caller is responsible for making sure skip[pet_skip_later] has been
2112 * taken into account.
2114 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
2115 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
2116 __isl_take isl_id
*id
)
2123 pet_scop_reset_skip(scop
, pet_skip_now
);
2124 pet_scop_reset_skip(scop
, pet_skip_later
);
2126 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
2130 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2131 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
2132 isl_set_copy(dom
), isl_map_copy(sched
),
2133 isl_aff_copy(iv_map
), isl_id_copy(id
));
2134 if (!scop
->stmts
[i
])
2138 for (i
= 0; i
< scop
->n_array
; ++i
) {
2139 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
2141 if (!scop
->arrays
[i
])
2145 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2146 scop
->implications
[i
] =
2147 pet_implication_embed(scop
->implications
[i
],
2149 if (!scop
->implications
[i
])
2154 isl_map_free(sched
);
2155 isl_aff_free(iv_map
);
2160 isl_map_free(sched
);
2161 isl_aff_free(iv_map
);
2163 return pet_scop_free(scop
);
2166 /* Add extra conditions on the parameters to iteration domain of "stmt".
2168 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
2169 __isl_take isl_set
*cond
)
2174 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
2179 return pet_stmt_free(stmt
);
2182 /* Add extra conditions to scop->skip[type].
2184 * The new skip condition only holds if it held before
2185 * and the condition is true. It does not hold if it did not hold
2186 * before or the condition is false.
2188 * The skip condition is assumed to be an affine expression.
2190 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
2191 enum pet_skip type
, __isl_keep isl_set
*cond
)
2193 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2199 if (!ext
->skip
[type
])
2202 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2203 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2204 isl_error_internal
, "can only resrict affine skips",
2205 return pet_scop_free(scop
));
2207 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2208 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2209 cond
= isl_set_copy(cond
);
2210 cond
= isl_set_from_params(cond
);
2211 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2212 skip
= indicator_function(cond
, dom
);
2213 isl_multi_pw_aff_free(ext
->skip
[type
]);
2214 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2215 if (!ext
->skip
[type
])
2216 return pet_scop_free(scop
);
2221 /* Add extra conditions on the parameters to all iteration domains
2222 * and skip conditions.
2224 * A parameter value is valid for the result if it was valid
2225 * for the original scop and satisfies "cond" or if it does
2226 * not satisfy "cond" as in this case the scop is not executed
2227 * and the original constraints on the parameters are irrelevant.
2229 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2230 __isl_take isl_set
*cond
)
2234 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2235 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2240 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2241 scop
->context
= isl_set_union(scop
->context
,
2242 isl_set_complement(isl_set_copy(cond
)));
2243 scop
->context
= isl_set_coalesce(scop
->context
);
2244 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2248 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2249 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2250 isl_set_copy(cond
));
2251 if (!scop
->stmts
[i
])
2259 return pet_scop_free(scop
);
2262 /* Construct a function that (upon precomposition) inserts
2263 * a filter value with name "id" and value "satisfied"
2264 * in the list of filter values embedded in the set space "space".
2266 * If "space" does not contain any filter values yet, we first create
2267 * a function that inserts 0 filter values, i.e.,
2269 * [space -> []] -> space
2271 * We can now assume that space is of the form [dom -> [filters]]
2272 * We construct an identity mapping on dom and a mapping on filters
2273 * that (upon precomposition) inserts the new filter
2276 * [satisfied, filters] -> [filters]
2278 * and then compute the cross product
2280 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2282 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2283 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2287 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2290 if (isl_space_is_wrapping(space
)) {
2291 space2
= isl_space_map_from_set(isl_space_copy(space
));
2292 ma
= isl_multi_aff_identity(space2
);
2293 space
= isl_space_unwrap(space
);
2295 space
= isl_space_from_domain(space
);
2296 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2299 space2
= isl_space_domain(isl_space_copy(space
));
2300 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2301 space
= isl_space_range(space
);
2302 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2303 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2304 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2305 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2306 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2308 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2309 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2314 /* Insert an argument expression corresponding to "test" in front
2315 * of the list of arguments described by *n_arg and *args.
2317 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2318 __isl_keep isl_multi_pw_aff
*test
)
2321 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
2327 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2331 struct pet_expr
**ext
;
2332 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2335 for (i
= 0; i
< *n_arg
; ++i
)
2336 ext
[1 + i
] = (*args
)[i
];
2341 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2348 /* Make the expression "expr" depend on the value of "test"
2349 * being equal to "satisfied".
2351 * If "test" is an affine expression, we simply add the conditions
2352 * on the expression having the value "satisfied" to all access relations
2353 * and index expressions.
2355 * Otherwise, we add a filter to "expr" (which is then assumed to be
2356 * an access expression) corresponding to "test" being equal to "satisfied".
2358 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2359 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2364 isl_pw_multi_aff
*pma
;
2369 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2373 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2374 isl_multi_pw_aff_free(test
);
2376 cond
= isl_pw_aff_non_zero_set(pa
);
2378 cond
= isl_pw_aff_zero_set(pa
);
2379 return pet_expr_restrict(expr
, isl_set_params(cond
));
2382 ctx
= isl_multi_pw_aff_get_ctx(test
);
2383 if (expr
->type
!= pet_expr_access
)
2384 isl_die(ctx
, isl_error_invalid
,
2385 "can only filter access expressions", goto error
);
2387 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2388 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2389 pma
= insert_filter_pma(space
, id
, satisfied
);
2391 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2393 isl_pw_multi_aff_copy(pma
));
2394 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2395 expr
->acc
.index
, pma
);
2396 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2399 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2402 isl_multi_pw_aff_free(test
);
2405 isl_multi_pw_aff_free(test
);
2406 return pet_expr_free(expr
);
2409 /* Look through the applications in "scop" for any that can be
2410 * applied to the filter expressed by "map" and "satisified".
2411 * If there is any, then apply it to "map" and return the result.
2412 * Otherwise, return "map".
2413 * "id" is the identifier of the virtual array.
2415 * We only introduce at most one implication for any given virtual array,
2416 * so we can apply the implication and return as soon as we find one.
2418 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2419 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2423 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2424 struct pet_implication
*pi
= scop
->implications
[i
];
2427 if (pi
->satisfied
!= satisfied
)
2429 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2434 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2440 /* Is the filter expressed by "test" and "satisfied" implied
2441 * by filter "pos" on "domain", with filter "expr", taking into
2442 * account the implications of "scop"?
2444 * For filter on domain implying that expressed by "test" and "satisfied",
2445 * the filter needs to be an access to the same (virtual) array as "test" and
2446 * the filter value needs to be equal to "satisfied".
2447 * Moreover, the filter access relation, possibly extended by
2448 * the implications in "scop" needs to contain "test".
2450 static int implies_filter(struct pet_scop
*scop
,
2451 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2452 __isl_keep isl_map
*test
, int satisfied
)
2454 isl_id
*test_id
, *arg_id
;
2461 if (expr
->type
!= pet_expr_access
)
2463 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2464 arg_id
= pet_expr_access_get_id(expr
);
2465 isl_id_free(arg_id
);
2466 isl_id_free(test_id
);
2467 if (test_id
!= arg_id
)
2469 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2470 is_int
= isl_val_is_int(val
);
2472 s
= isl_val_get_num_si(val
);
2481 implied
= isl_map_copy(expr
->acc
.access
);
2482 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2483 is_subset
= isl_map_is_subset(test
, implied
);
2484 isl_map_free(implied
);
2489 /* Is the filter expressed by "test" and "satisfied" implied
2490 * by any of the filters on the domain of "stmt", taking into
2491 * account the implications of "scop"?
2493 static int filter_implied(struct pet_scop
*scop
,
2494 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2502 if (!scop
|| !stmt
|| !test
)
2504 if (scop
->n_implication
== 0)
2506 if (stmt
->n_arg
== 0)
2509 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2510 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2513 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2514 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2515 test_map
, satisfied
);
2516 if (implied
< 0 || implied
)
2520 isl_map_free(test_map
);
2521 isl_map_free(domain
);
2525 /* Make the statement "stmt" depend on the value of "test"
2526 * being equal to "satisfied" by adjusting stmt->domain.
2528 * The domain of "test" corresponds to the (zero or more) outer dimensions
2529 * of the iteration domain.
2531 * We first extend "test" to apply to the entire iteration domain and
2532 * then check if the filter that we are about to add is implied
2533 * by any of the current filters, possibly taking into account
2534 * the implications in "scop". If so, we leave "stmt" untouched and return.
2536 * Otherwise, we insert an argument corresponding to a read to "test"
2537 * from the iteration domain of "stmt" in front of the list of arguments.
2538 * We also insert a corresponding output dimension in the wrapped
2539 * map contained in stmt->domain, with value set to "satisfied".
2541 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2542 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2548 isl_pw_multi_aff
*pma
;
2549 isl_multi_aff
*add_dom
;
2551 isl_local_space
*ls
;
2557 space
= isl_set_get_space(stmt
->domain
);
2558 if (isl_space_is_wrapping(space
))
2559 space
= isl_space_domain(isl_space_unwrap(space
));
2560 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2561 space
= isl_space_from_domain(space
);
2562 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2563 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2564 ls
= isl_local_space_from_space(isl_space_domain(space
));
2565 for (i
= 0; i
< n_test_dom
; ++i
) {
2567 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2569 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2571 isl_local_space_free(ls
);
2572 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2574 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2578 isl_multi_pw_aff_free(test
);
2582 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2583 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2584 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2586 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2589 isl_multi_pw_aff_free(test
);
2592 isl_multi_pw_aff_free(test
);
2593 return pet_stmt_free(stmt
);
2596 /* Does "scop" have a skip condition of the given "type"?
2598 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2600 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2604 return ext
->skip
[type
] != NULL
;
2607 /* Does "scop" have a skip condition of the given "type" that
2608 * is an affine expression?
2610 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2612 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2616 if (!ext
->skip
[type
])
2618 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2621 /* Does "scop" have a skip condition of the given "type" that
2622 * is not an affine expression?
2624 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2626 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2631 if (!ext
->skip
[type
])
2633 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2639 /* Does "scop" have a skip condition of the given "type" that
2640 * is affine and holds on the entire domain?
2642 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2644 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2650 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2651 if (is_aff
< 0 || !is_aff
)
2654 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2655 set
= isl_pw_aff_non_zero_set(pa
);
2656 is_univ
= isl_set_plain_is_universe(set
);
2662 /* Replace scop->skip[type] by "skip".
2664 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2665 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2667 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2672 isl_multi_pw_aff_free(ext
->skip
[type
]);
2673 ext
->skip
[type
] = skip
;
2677 isl_multi_pw_aff_free(skip
);
2678 return pet_scop_free(scop
);
2681 /* Return a copy of scop->skip[type].
2683 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2686 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2691 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2694 /* Assuming scop->skip[type] is an affine expression,
2695 * return the constraints on the parameters for which the skip condition
2698 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2701 isl_multi_pw_aff
*skip
;
2704 skip
= pet_scop_get_skip(scop
, type
);
2705 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2706 isl_multi_pw_aff_free(skip
);
2707 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2710 /* Return the identifier of the variable that is accessed by
2711 * the skip condition of the given type.
2713 * The skip condition is assumed not to be an affine condition.
2715 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2718 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2723 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2726 /* Return an access pet_expr corresponding to the skip condition
2727 * of the given type.
2729 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2732 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2735 /* Drop the the skip condition scop->skip[type].
2737 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2739 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2744 isl_multi_pw_aff_free(ext
->skip
[type
]);
2745 ext
->skip
[type
] = NULL
;
2748 /* Make the skip condition (if any) depend on the value of "test" being
2749 * equal to "satisfied".
2751 * We only support the case where the original skip condition is universal,
2752 * i.e., where skipping is unconditional, and where satisfied == 1.
2753 * In this case, the skip condition is changed to skip only when
2754 * "test" is equal to one.
2756 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2757 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2763 if (!pet_scop_has_skip(scop
, type
))
2767 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2769 return pet_scop_free(scop
);
2770 if (satisfied
&& is_univ
) {
2771 isl_space
*space
= isl_multi_pw_aff_get_space(test
);
2772 isl_multi_pw_aff
*skip
;
2773 skip
= isl_multi_pw_aff_zero(space
);
2774 scop
= pet_scop_set_skip(scop
, type
, skip
);
2778 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2779 "skip expression cannot be filtered",
2780 return pet_scop_free(scop
));
2786 /* Make all statements in "scop" depend on the value of "test"
2787 * being equal to "satisfied" by adjusting their domains.
2789 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2790 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2794 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2795 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2800 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2801 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2802 isl_multi_pw_aff_copy(test
), satisfied
);
2803 if (!scop
->stmts
[i
])
2807 isl_multi_pw_aff_free(test
);
2810 isl_multi_pw_aff_free(test
);
2811 return pet_scop_free(scop
);
2814 /* Add all parameters in "expr" to "dim" and return the result.
2816 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2817 __isl_take isl_space
*dim
)
2823 for (i
= 0; i
< expr
->n_arg
; ++i
)
2825 dim
= expr_collect_params(expr
->args
[i
], dim
);
2827 if (expr
->type
== pet_expr_access
)
2828 dim
= isl_space_align_params(dim
,
2829 isl_map_get_space(expr
->acc
.access
));
2833 isl_space_free(dim
);
2834 return pet_expr_free(expr
);
2837 /* Add all parameters in "stmt" to "dim" and return the result.
2839 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2840 __isl_take isl_space
*dim
)
2845 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2846 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2847 dim
= expr_collect_params(stmt
->body
, dim
);
2851 isl_space_free(dim
);
2852 return pet_stmt_free(stmt
);
2855 /* Add all parameters in "array" to "dim" and return the result.
2857 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2858 __isl_take isl_space
*dim
)
2863 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2864 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2868 pet_array_free(array
);
2869 return isl_space_free(dim
);
2872 /* Add all parameters in "scop" to "dim" and return the result.
2874 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2875 __isl_take isl_space
*dim
)
2882 for (i
= 0; i
< scop
->n_array
; ++i
)
2883 dim
= array_collect_params(scop
->arrays
[i
], dim
);
2885 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2886 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
2890 isl_space_free(dim
);
2891 return pet_scop_free(scop
);
2894 /* Add all parameters in "dim" to all access relations and index expressions
2897 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
2898 __isl_take isl_space
*dim
)
2905 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2907 expr_propagate_params(expr
->args
[i
],
2908 isl_space_copy(dim
));
2913 if (expr
->type
== pet_expr_access
) {
2914 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
2915 isl_space_copy(dim
));
2916 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
2917 isl_space_copy(dim
));
2918 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2922 isl_space_free(dim
);
2925 isl_space_free(dim
);
2926 return pet_expr_free(expr
);
2929 /* Add all parameters in "dim" to the domain, schedule and
2930 * all access relations in "stmt".
2932 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2933 __isl_take isl_space
*dim
)
2938 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
2939 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2940 isl_space_copy(dim
));
2941 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
2943 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2946 isl_space_free(dim
);
2949 isl_space_free(dim
);
2950 return pet_stmt_free(stmt
);
2953 /* Add all parameters in "dim" to "array".
2955 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2956 __isl_take isl_space
*dim
)
2961 array
->context
= isl_set_align_params(array
->context
,
2962 isl_space_copy(dim
));
2963 array
->extent
= isl_set_align_params(array
->extent
,
2964 isl_space_copy(dim
));
2965 if (array
->value_bounds
) {
2966 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2967 isl_space_copy(dim
));
2968 if (!array
->value_bounds
)
2972 if (!array
->context
|| !array
->extent
)
2975 isl_space_free(dim
);
2978 isl_space_free(dim
);
2979 return pet_array_free(array
);
2982 /* Add all parameters in "dim" to "scop".
2984 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2985 __isl_take isl_space
*dim
)
2992 for (i
= 0; i
< scop
->n_array
; ++i
) {
2993 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2994 isl_space_copy(dim
));
2995 if (!scop
->arrays
[i
])
2999 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3000 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
3001 isl_space_copy(dim
));
3002 if (!scop
->stmts
[i
])
3006 isl_space_free(dim
);
3009 isl_space_free(dim
);
3010 return pet_scop_free(scop
);
3013 /* Update all isl_sets and isl_maps in "scop" such that they all
3014 * have the same parameters.
3016 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
3023 dim
= isl_set_get_space(scop
->context
);
3024 dim
= scop_collect_params(scop
, dim
);
3026 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
3027 scop
= scop_propagate_params(scop
, dim
);
3032 /* Check if the given index expression accesses a (0D) array that corresponds
3033 * to one of the parameters in "dim". If so, replace the array access
3034 * by an access to the set of integers with as index (and value)
3037 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
3038 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
3040 isl_local_space
*ls
;
3041 isl_id
*array_id
= NULL
;
3045 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
3046 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
3047 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3049 isl_space_free(space
);
3052 isl_id_free(array_id
);
3056 space
= isl_multi_pw_aff_get_domain_space(index
);
3057 isl_multi_pw_aff_free(index
);
3059 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3061 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
3062 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
3065 isl_id_free(array_id
);
3067 ls
= isl_local_space_from_space(space
);
3068 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
3069 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
3074 /* Check if the given access relation accesses a (0D) array that corresponds
3075 * to one of the parameters in "dim". If so, replace the array access
3076 * by an access to the set of integers with as index (and value)
3079 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
3080 __isl_take isl_space
*dim
)
3082 isl_id
*array_id
= NULL
;
3085 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
3086 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
3087 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
3089 isl_space_free(dim
);
3092 isl_id_free(array_id
);
3096 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
3098 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
3099 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
3102 isl_id_free(array_id
);
3104 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
3105 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
3110 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3111 * in "dim" by a value equal to the corresponding parameter.
3113 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
3114 __isl_take isl_space
*dim
)
3121 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3123 expr_detect_parameter_accesses(expr
->args
[i
],
3124 isl_space_copy(dim
));
3129 if (expr
->type
== pet_expr_access
) {
3130 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
3131 isl_space_copy(dim
));
3132 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
3133 isl_space_copy(dim
));
3134 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3138 isl_space_free(dim
);
3141 isl_space_free(dim
);
3142 return pet_expr_free(expr
);
3145 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3146 * in "dim" by a value equal to the corresponding parameter.
3148 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
3149 __isl_take isl_space
*dim
)
3154 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
3155 isl_space_copy(dim
));
3157 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3160 isl_space_free(dim
);
3163 isl_space_free(dim
);
3164 return pet_stmt_free(stmt
);
3167 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3168 * in "dim" by a value equal to the corresponding parameter.
3170 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
3171 __isl_take isl_space
*dim
)
3178 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3179 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
3180 isl_space_copy(dim
));
3181 if (!scop
->stmts
[i
])
3185 isl_space_free(dim
);
3188 isl_space_free(dim
);
3189 return pet_scop_free(scop
);
3192 /* Replace all accesses to (0D) arrays that correspond to any of
3193 * the parameters used in "scop" by a value equal
3194 * to the corresponding parameter.
3196 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
3203 dim
= isl_set_get_space(scop
->context
);
3204 dim
= scop_collect_params(scop
, dim
);
3206 scop
= scop_detect_parameter_accesses(scop
, dim
);
3211 /* Add all read access relations (if "read" is set) and/or all write
3212 * access relations (if "write" is set) to "accesses" and return the result.
3214 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
3215 int read
, int write
, __isl_take isl_union_map
*accesses
)
3224 for (i
= 0; i
< expr
->n_arg
; ++i
)
3225 accesses
= expr_collect_accesses(expr
->args
[i
],
3226 read
, write
, accesses
);
3228 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
3229 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
3230 accesses
= isl_union_map_add_map(accesses
,
3231 isl_map_copy(expr
->acc
.access
));
3236 /* Collect and return all read access relations (if "read" is set)
3237 * and/or all write access relations (if "write" is set) in "stmt".
3239 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
3240 int read
, int write
, __isl_take isl_space
*dim
)
3242 isl_union_map
*accesses
;
3247 accesses
= isl_union_map_empty(dim
);
3248 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
3249 accesses
= isl_union_map_intersect_domain(accesses
,
3250 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
3255 /* Collect and return all read access relations (if "read" is set)
3256 * and/or all write access relations (if "write" is set) in "scop".
3258 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3259 int read
, int write
)
3262 isl_union_map
*accesses
;
3267 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3269 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3270 isl_union_map
*accesses_i
;
3271 isl_space
*dim
= isl_set_get_space(scop
->context
);
3272 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
3274 accesses
= isl_union_map_union(accesses
, accesses_i
);
3280 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
3282 return scop_collect_accesses(scop
, 1, 0);
3285 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
3287 return scop_collect_accesses(scop
, 0, 1);
3290 /* Collect and return the union of iteration domains in "scop".
3292 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3296 isl_union_set
*domain
;
3301 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3303 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3304 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3305 domain
= isl_union_set_add_set(domain
, domain_i
);
3311 /* Collect and return the schedules of the statements in "scop".
3312 * The range is normalized to the maximal number of scheduling
3315 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3318 isl_map
*schedule_i
;
3319 isl_union_map
*schedule
;
3320 int depth
, max_depth
= 0;
3325 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3327 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3328 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3329 if (depth
> max_depth
)
3333 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3334 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3335 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3336 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3338 for (j
= depth
; j
< max_depth
; ++j
)
3339 schedule_i
= isl_map_fix_si(schedule_i
,
3341 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3347 /* Does expression "expr" write to "id"?
3349 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3354 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3355 int writes
= expr_writes(expr
->args
[i
], id
);
3356 if (writes
< 0 || writes
)
3360 if (expr
->type
!= pet_expr_access
)
3362 if (!expr
->acc
.write
)
3364 if (pet_expr_is_affine(expr
))
3367 write_id
= pet_expr_access_get_id(expr
);
3368 isl_id_free(write_id
);
3373 return write_id
== id
;
3376 /* Does statement "stmt" write to "id"?
3378 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3380 return expr_writes(stmt
->body
, id
);
3383 /* Is there any write access in "scop" that accesses "id"?
3385 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3392 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3393 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3394 if (writes
< 0 || writes
)
3401 /* Add a reference identifier to access expression "expr".
3402 * "user" points to an integer that contains the sequence number
3403 * of the next reference.
3405 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3414 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3415 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3416 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3417 if (!expr
->acc
.ref_id
)
3418 return pet_expr_free(expr
);
3423 /* Add a reference identifier to all access expressions in "stmt".
3424 * "n_ref" points to an integer that contains the sequence number
3425 * of the next reference.
3427 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3434 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3435 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3436 &access_add_ref_id
, n_ref
);
3438 return pet_stmt_free(stmt
);
3441 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3443 return pet_stmt_free(stmt
);
3448 /* Add a reference identifier to all access expressions in "scop".
3450 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3459 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3460 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3461 if (!scop
->stmts
[i
])
3462 return pet_scop_free(scop
);
3468 /* Reset the user pointer on the tuple id and all parameter ids in "set".
3470 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
3474 n
= isl_set_dim(set
, isl_dim_param
);
3475 for (i
= 0; i
< n
; ++i
) {
3476 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
3477 const char *name
= isl_id_get_name(id
);
3478 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
3482 if (!isl_set_is_params(set
) && isl_set_has_tuple_id(set
)) {
3483 isl_id
*id
= isl_set_get_tuple_id(set
);
3484 const char *name
= isl_id_get_name(id
);
3485 set
= isl_set_set_tuple_name(set
, name
);
3492 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
3494 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
3498 n
= isl_map_dim(map
, isl_dim_param
);
3499 for (i
= 0; i
< n
; ++i
) {
3500 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
3501 const char *name
= isl_id_get_name(id
);
3502 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
3506 if (isl_map_has_tuple_id(map
, isl_dim_in
)) {
3507 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_in
);
3508 const char *name
= isl_id_get_name(id
);
3509 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
3513 if (isl_map_has_tuple_id(map
, isl_dim_out
)) {
3514 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_out
);
3515 const char *name
= isl_id_get_name(id
);
3516 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
3523 /* Reset the user pointer on the tuple ids and all parameter ids in "mpa".
3525 static __isl_give isl_multi_pw_aff
*multi_pw_aff_anonymize(
3526 __isl_take isl_multi_pw_aff
*mpa
)
3530 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_param
);
3531 for (i
= 0; i
< n
; ++i
) {
3532 isl_id
*id
= isl_multi_pw_aff_get_dim_id(mpa
, isl_dim_param
, i
);
3533 const char *name
= isl_id_get_name(id
);
3534 mpa
= isl_multi_pw_aff_set_dim_name(mpa
,
3535 isl_dim_param
, i
, name
);
3539 if (isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_in
)) {
3540 isl_id
*id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_in
);
3541 const char *name
= isl_id_get_name(id
);
3542 mpa
= isl_multi_pw_aff_set_tuple_name(mpa
, isl_dim_in
, name
);
3546 if (isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
)) {
3547 isl_id
*id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
3548 const char *name
= isl_id_get_name(id
);
3549 mpa
= isl_multi_pw_aff_set_tuple_name(mpa
, isl_dim_out
, name
);
3556 /* Reset the user pointer on all parameter ids in "array".
3558 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3563 array
->context
= set_anonymize(array
->context
);
3564 array
->extent
= set_anonymize(array
->extent
);
3565 if (!array
->context
|| !array
->extent
)
3566 return pet_array_free(array
);
3571 /* Reset the user pointer on all parameter and tuple ids in
3572 * the access relation and the index expressions
3573 * of the access expression "expr".
3575 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3577 expr
->acc
.access
= map_anonymize(expr
->acc
.access
);
3578 expr
->acc
.index
= multi_pw_aff_anonymize(expr
->acc
.index
);
3579 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3580 return pet_expr_free(expr
);
3585 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3587 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3596 stmt
->domain
= set_anonymize(stmt
->domain
);
3597 stmt
->schedule
= map_anonymize(stmt
->schedule
);
3598 if (!stmt
->domain
|| !stmt
->schedule
)
3599 return pet_stmt_free(stmt
);
3601 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3602 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3603 &access_anonymize
, NULL
);
3605 return pet_stmt_free(stmt
);
3608 stmt
->body
= pet_expr_map_access(stmt
->body
,
3609 &access_anonymize
, NULL
);
3611 return pet_stmt_free(stmt
);
3616 /* Reset the user pointer on the tuple ids and all parameter ids
3619 static struct pet_implication
*implication_anonymize(
3620 struct pet_implication
*implication
)
3625 implication
->extension
= map_anonymize(implication
->extension
);
3626 if (!implication
->extension
)
3627 return pet_implication_free(implication
);
3632 /* Reset the user pointer on all parameter and tuple ids in "scop".
3634 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3641 scop
->context
= set_anonymize(scop
->context
);
3642 scop
->context_value
= set_anonymize(scop
->context_value
);
3643 if (!scop
->context
|| !scop
->context_value
)
3644 return pet_scop_free(scop
);
3646 for (i
= 0; i
< scop
->n_array
; ++i
) {
3647 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3648 if (!scop
->arrays
[i
])
3649 return pet_scop_free(scop
);
3652 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3653 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3654 if (!scop
->stmts
[i
])
3655 return pet_scop_free(scop
);
3658 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3659 scop
->implications
[i
] =
3660 implication_anonymize(scop
->implications
[i
]);
3661 if (!scop
->implications
[i
])
3662 return pet_scop_free(scop
);
3668 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3669 * then intersect the range of "map" with the valid set of values.
3671 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
3672 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
3677 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3679 id
= pet_expr_access_get_id(arg
);
3680 space
= isl_space_alloc(ctx
, 0, 0, 1);
3681 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
3682 vb
= isl_union_map_extract_map(value_bounds
, space
);
3683 if (!isl_map_plain_is_empty(vb
))
3684 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
3691 /* Given a set "domain", return a wrapped relation with the given set
3692 * as domain and a range of dimension "n_arg", where each coordinate
3693 * is either unbounded or, if the corresponding element of args is of
3694 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3696 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
3697 unsigned n_arg
, struct pet_expr
**args
,
3698 __isl_keep isl_union_map
*value_bounds
)
3704 map
= isl_map_from_domain(domain
);
3705 space
= isl_map_get_space(map
);
3706 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
3708 for (i
= 0; i
< n_arg
; ++i
) {
3710 struct pet_expr
*arg
= args
[i
];
3712 map_i
= isl_map_universe(isl_space_copy(space
));
3713 if (arg
->type
== pet_expr_access
)
3714 map_i
= access_apply_value_bounds(map_i
, arg
,
3716 map
= isl_map_flat_range_product(map
, map_i
);
3718 isl_space_free(space
);
3720 return isl_map_wrap(map
);
3723 /* Data used in access_gist() callback.
3725 struct pet_access_gist_data
{
3727 isl_union_map
*value_bounds
;
3730 /* Given an expression "expr" of type pet_expr_access, compute
3731 * the gist of the associated access relation and index expression
3732 * with respect to data->domain and the bounds on the values of the arguments
3733 * of the expression.
3735 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3737 struct pet_access_gist_data
*data
= user
;
3740 domain
= isl_set_copy(data
->domain
);
3741 if (expr
->n_arg
> 0)
3742 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3743 data
->value_bounds
);
3745 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
3746 isl_set_copy(domain
));
3747 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
3748 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3749 return pet_expr_free(expr
);
3754 /* Compute the gist of the iteration domain and all access relations
3755 * of "stmt" based on the constraints on the parameters specified by "context"
3756 * and the constraints on the values of nested accesses specified
3757 * by "value_bounds".
3759 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3760 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3765 struct pet_access_gist_data data
;
3770 data
.domain
= isl_set_copy(stmt
->domain
);
3771 data
.value_bounds
= value_bounds
;
3772 if (stmt
->n_arg
> 0)
3773 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3775 data
.domain
= isl_set_intersect_params(data
.domain
,
3776 isl_set_copy(context
));
3778 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3779 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3780 &access_gist
, &data
);
3785 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3789 isl_set_free(data
.domain
);
3791 space
= isl_set_get_space(stmt
->domain
);
3792 if (isl_space_is_wrapping(space
))
3793 space
= isl_space_domain(isl_space_unwrap(space
));
3794 domain
= isl_set_universe(space
);
3795 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3796 if (stmt
->n_arg
> 0)
3797 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3799 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3801 return pet_stmt_free(stmt
);
3805 isl_set_free(data
.domain
);
3806 return pet_stmt_free(stmt
);
3809 /* Compute the gist of the extent of the array
3810 * based on the constraints on the parameters specified by "context".
3812 static struct pet_array
*array_gist(struct pet_array
*array
,
3813 __isl_keep isl_set
*context
)
3818 array
->extent
= isl_set_gist_params(array
->extent
,
3819 isl_set_copy(context
));
3821 return pet_array_free(array
);
3826 /* Compute the gist of all sets and relations in "scop"
3827 * based on the constraints on the parameters specified by "scop->context"
3828 * and the constraints on the values of nested accesses specified
3829 * by "value_bounds".
3831 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3832 __isl_keep isl_union_map
*value_bounds
)
3839 scop
->context
= isl_set_coalesce(scop
->context
);
3841 return pet_scop_free(scop
);
3843 for (i
= 0; i
< scop
->n_array
; ++i
) {
3844 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3845 if (!scop
->arrays
[i
])
3846 return pet_scop_free(scop
);
3849 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3850 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3852 if (!scop
->stmts
[i
])
3853 return pet_scop_free(scop
);
3859 /* Intersect the context of "scop" with "context".
3860 * To ensure that we don't introduce any unnamed parameters in
3861 * the context of "scop", we first remove the unnamed parameters
3864 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3865 __isl_take isl_set
*context
)
3870 context
= set_project_out_unnamed_params(context
);
3871 scop
->context
= isl_set_intersect(scop
->context
, context
);
3873 return pet_scop_free(scop
);
3877 isl_set_free(context
);
3878 return pet_scop_free(scop
);
3881 /* Drop the current context of "scop". That is, replace the context
3882 * by a universal set.
3884 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3891 space
= isl_set_get_space(scop
->context
);
3892 isl_set_free(scop
->context
);
3893 scop
->context
= isl_set_universe(space
);
3895 return pet_scop_free(scop
);
3900 /* Append "array" to the arrays of "scop".
3902 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3903 struct pet_array
*array
)
3906 struct pet_array
**arrays
;
3908 if (!array
|| !scop
)
3911 ctx
= isl_set_get_ctx(scop
->context
);
3912 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3916 scop
->arrays
= arrays
;
3917 scop
->arrays
[scop
->n_array
] = array
;
3922 pet_array_free(array
);
3923 return pet_scop_free(scop
);
3926 /* Create and return an implication on filter values equal to "satisfied"
3927 * with extension "map".
3929 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3933 struct pet_implication
*implication
;
3937 ctx
= isl_map_get_ctx(map
);
3938 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3942 implication
->extension
= map
;
3943 implication
->satisfied
= satisfied
;
3951 /* Add an implication on filter values equal to "satisfied"
3952 * with extension "map" to "scop".
3954 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3955 __isl_take isl_map
*map
, int satisfied
)
3958 struct pet_implication
*implication
;
3959 struct pet_implication
**implications
;
3961 implication
= new_implication(map
, satisfied
);
3962 if (!scop
|| !implication
)
3965 ctx
= isl_set_get_ctx(scop
->context
);
3966 implications
= isl_realloc_array(ctx
, scop
->implications
,
3967 struct pet_implication
*,
3968 scop
->n_implication
+ 1);
3971 scop
->implications
= implications
;
3972 scop
->implications
[scop
->n_implication
] = implication
;
3973 scop
->n_implication
++;
3977 pet_implication_free(implication
);
3978 return pet_scop_free(scop
);
3981 /* Given an access expression, check if it is data dependent.
3982 * If so, set *found and abort the search.
3984 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
3996 /* Does "scop" contain any data dependent accesses?
3998 * Check the body of each statement for such accesses.
4000 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
4008 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4009 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
4010 &is_data_dependent
, &found
);
4011 if (r
< 0 && !found
)
4020 /* Does "scop" contain and data dependent conditions?
4022 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
4029 for (i
= 0; i
< scop
->n_stmt
; ++i
)
4030 if (scop
->stmts
[i
]->n_arg
> 0)
4036 /* Keep track of the "input" file inside the (extended) "scop".
4038 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
4040 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4050 /* Print the original code corresponding to "scop" to printer "p".
4052 * pet_scop_print_original can only be called from
4053 * a pet_transform_C_source callback. This means that the input
4054 * file is stored in the extended scop and that the printer prints
4057 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
4058 __isl_take isl_printer
*p
)
4060 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4064 return isl_printer_free(p
);
4067 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
4068 "no input file stored in scop",
4069 return isl_printer_free(p
));
4071 output
= isl_printer_get_file(p
);
4073 return isl_printer_free(p
);
4075 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
4076 return isl_printer_free(p
);