2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
42 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
44 static char *type_str
[] = {
45 [pet_expr_access
] = "access",
46 [pet_expr_call
] = "call",
47 [pet_expr_cast
] = "cast",
48 [pet_expr_double
] = "double",
49 [pet_expr_unary
] = "unary",
50 [pet_expr_binary
] = "binary",
51 [pet_expr_ternary
] = "ternary"
54 static char *op_str
[] = {
55 [pet_op_add_assign
] = "+=",
56 [pet_op_sub_assign
] = "-=",
57 [pet_op_mul_assign
] = "*=",
58 [pet_op_div_assign
] = "/=",
59 [pet_op_assign
] = "=",
70 [pet_op_post_inc
] = "++",
71 [pet_op_post_dec
] = "--",
72 [pet_op_pre_inc
] = "++",
73 [pet_op_pre_dec
] = "--",
74 [pet_op_address_of
] = "&",
75 [pet_op_kill
] = "kill"
78 /* pet_scop with extra information that is used during parsing and printing.
80 * In particular, we keep track of conditions under which we want
81 * to skip the rest of the current loop iteration (skip[pet_skip_now])
82 * and of conditions under which we want to skip subsequent
83 * loop iterations (skip[pet_skip_later]).
85 * The conditions are represented as index expressions defined
86 * over a zero-dimensiona domain. The index expression is either
87 * a boolean affine expression or an access to a variable, which
88 * is assumed to attain values zero and one. The condition holds
89 * if the variable has value one or if the affine expression
90 * has value one (typically for only part of the parameter space).
92 * A missing condition (skip[type] == NULL) means that we don't want
95 * Additionally, we keep track of the original input file
96 * inside pet_transform_C_source.
101 isl_multi_pw_aff
*skip
[2];
105 const char *pet_op_str(enum pet_op_type op
)
110 int pet_op_is_inc_dec(enum pet_op_type op
)
112 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
113 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
116 const char *pet_type_str(enum pet_expr_type type
)
118 return type_str
[type
];
121 enum pet_op_type
pet_str_op(const char *str
)
125 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
126 if (!strcmp(op_str
[i
], str
))
132 enum pet_expr_type
pet_str_type(const char *str
)
136 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
137 if (!strcmp(type_str
[i
], str
))
143 /* Construct an access pet_expr from an access relation and an index expression.
144 * By default, it is considered to be a read access.
146 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
147 __isl_take isl_multi_pw_aff
*index
)
149 isl_ctx
*ctx
= isl_map_get_ctx(access
);
150 struct pet_expr
*expr
;
152 if (!index
|| !access
)
154 expr
= isl_calloc_type(ctx
, struct pet_expr
);
158 expr
->type
= pet_expr_access
;
159 expr
->acc
.access
= access
;
160 expr
->acc
.index
= index
;
166 isl_map_free(access
);
167 isl_multi_pw_aff_free(index
);
171 /* Construct an access pet_expr from an index expression.
172 * By default, the access is considered to be a read access.
174 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
178 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
179 return pet_expr_from_access_and_index(access
, index
);
182 /* Extend the range of "access" with "n" dimensions, retaining
183 * the tuple identifier on this range.
185 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
189 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
190 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
191 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
196 /* Construct an access pet_expr from an index expression and
197 * the depth of the accessed array.
198 * By default, the access is considered to be a read access.
200 * If the number of indices is smaller than the depth of the array,
201 * then we assume that all elements of the remaining dimensions
204 struct pet_expr
*pet_expr_from_index_and_depth(
205 __isl_take isl_multi_pw_aff
*index
, int depth
)
210 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
213 dim
= isl_map_dim(access
, isl_dim_out
);
215 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
216 "number of indices greater than depth",
217 access
= isl_map_free(access
));
219 return pet_expr_from_access_and_index(access
, index
);
221 access
= extend_range(access
, depth
- dim
);
223 return pet_expr_from_access_and_index(access
, index
);
225 isl_multi_pw_aff_free(index
);
229 /* Construct a pet_expr that kills the elements specified by
230 * the index expression "index" and the access relation "access".
232 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
233 __isl_take isl_multi_pw_aff
*index
)
236 struct pet_expr
*expr
;
238 if (!access
|| !index
)
241 ctx
= isl_multi_pw_aff_get_ctx(index
);
242 expr
= pet_expr_from_access_and_index(access
, index
);
246 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
248 isl_map_free(access
);
249 isl_multi_pw_aff_free(index
);
253 /* Construct a unary pet_expr that performs "op" on "arg".
255 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
256 struct pet_expr
*arg
)
258 struct pet_expr
*expr
;
262 expr
= isl_alloc_type(ctx
, struct pet_expr
);
266 expr
->type
= pet_expr_unary
;
269 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
272 expr
->args
[pet_un_arg
] = arg
;
280 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
282 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
283 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
285 struct pet_expr
*expr
;
289 expr
= isl_alloc_type(ctx
, struct pet_expr
);
293 expr
->type
= pet_expr_binary
;
296 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
299 expr
->args
[pet_bin_lhs
] = lhs
;
300 expr
->args
[pet_bin_rhs
] = rhs
;
309 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
311 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
312 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
314 struct pet_expr
*expr
;
316 if (!cond
|| !lhs
|| !rhs
)
318 expr
= isl_alloc_type(ctx
, struct pet_expr
);
322 expr
->type
= pet_expr_ternary
;
324 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
327 expr
->args
[pet_ter_cond
] = cond
;
328 expr
->args
[pet_ter_true
] = lhs
;
329 expr
->args
[pet_ter_false
] = rhs
;
339 /* Construct a call pet_expr that calls function "name" with "n_arg"
340 * arguments. The caller is responsible for filling in the arguments.
342 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
345 struct pet_expr
*expr
;
347 expr
= isl_alloc_type(ctx
, struct pet_expr
);
351 expr
->type
= pet_expr_call
;
353 expr
->name
= strdup(name
);
354 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
355 if (!expr
->name
|| !expr
->args
)
356 return pet_expr_free(expr
);
361 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
363 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
364 struct pet_expr
*arg
)
366 struct pet_expr
*expr
;
371 expr
= isl_alloc_type(ctx
, struct pet_expr
);
375 expr
->type
= pet_expr_cast
;
377 expr
->type_name
= strdup(type_name
);
378 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
379 if (!expr
->type_name
|| !expr
->args
)
391 /* Construct a pet_expr that represents the double "d".
393 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
395 struct pet_expr
*expr
;
397 expr
= isl_calloc_type(ctx
, struct pet_expr
);
401 expr
->type
= pet_expr_double
;
403 expr
->d
.s
= strdup(s
);
405 return pet_expr_free(expr
);
410 struct pet_expr
*pet_expr_free(struct pet_expr
*expr
)
417 for (i
= 0; i
< expr
->n_arg
; ++i
)
418 pet_expr_free(expr
->args
[i
]);
421 switch (expr
->type
) {
422 case pet_expr_access
:
423 isl_id_free(expr
->acc
.ref_id
);
424 isl_map_free(expr
->acc
.access
);
425 isl_multi_pw_aff_free(expr
->acc
.index
);
431 free(expr
->type_name
);
433 case pet_expr_double
:
437 case pet_expr_binary
:
438 case pet_expr_ternary
:
446 static void expr_dump(struct pet_expr
*expr
, int indent
)
453 fprintf(stderr
, "%*s", indent
, "");
455 switch (expr
->type
) {
456 case pet_expr_double
:
457 fprintf(stderr
, "%s\n", expr
->d
.s
);
459 case pet_expr_access
:
460 isl_id_dump(expr
->acc
.ref_id
);
461 fprintf(stderr
, "%*s", indent
, "");
462 isl_map_dump(expr
->acc
.access
);
463 fprintf(stderr
, "%*s", indent
, "");
464 isl_multi_pw_aff_dump(expr
->acc
.index
);
465 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
467 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
468 "", expr
->acc
.write
);
469 for (i
= 0; i
< expr
->n_arg
; ++i
)
470 expr_dump(expr
->args
[i
], indent
+ 2);
473 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
474 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
476 case pet_expr_binary
:
477 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
478 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
479 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
481 case pet_expr_ternary
:
482 fprintf(stderr
, "?:\n");
483 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
484 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
485 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
488 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
489 for (i
= 0; i
< expr
->n_arg
; ++i
)
490 expr_dump(expr
->args
[i
], indent
+ 2);
493 fprintf(stderr
, "(%s)\n", expr
->type_name
);
494 for (i
= 0; i
< expr
->n_arg
; ++i
)
495 expr_dump(expr
->args
[i
], indent
+ 2);
500 void pet_expr_dump(struct pet_expr
*expr
)
505 /* Does "expr" represent an access to an unnamed space, i.e.,
506 * does it represent an affine expression?
508 int pet_expr_is_affine(struct pet_expr
*expr
)
514 if (expr
->type
!= pet_expr_access
)
517 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
524 /* Return the identifier of the array accessed by "expr".
526 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
530 if (expr
->type
!= pet_expr_access
)
532 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
535 /* Align the parameters of expr->acc.index and expr->acc.access.
537 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
541 if (expr
->type
!= pet_expr_access
)
542 return pet_expr_free(expr
);
544 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
545 isl_multi_pw_aff_get_space(expr
->acc
.index
));
546 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
547 isl_map_get_space(expr
->acc
.access
));
548 if (!expr
->acc
.access
|| !expr
->acc
.index
)
549 return pet_expr_free(expr
);
554 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
556 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
560 if (expr
->type
!= pet_expr_access
)
563 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
566 /* Return 1 if the two pet_exprs are equivalent.
568 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
572 if (!expr1
|| !expr2
)
575 if (expr1
->type
!= expr2
->type
)
577 if (expr1
->n_arg
!= expr2
->n_arg
)
579 for (i
= 0; i
< expr1
->n_arg
; ++i
)
580 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
582 switch (expr1
->type
) {
583 case pet_expr_double
:
584 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
586 if (expr1
->d
.val
!= expr2
->d
.val
)
589 case pet_expr_access
:
590 if (expr1
->acc
.read
!= expr2
->acc
.read
)
592 if (expr1
->acc
.write
!= expr2
->acc
.write
)
594 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
596 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
598 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
600 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
602 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
607 case pet_expr_binary
:
608 case pet_expr_ternary
:
609 if (expr1
->op
!= expr2
->op
)
613 if (strcmp(expr1
->name
, expr2
->name
))
617 if (strcmp(expr1
->type_name
, expr2
->type_name
))
625 /* Add extra conditions on the parameters to all access relations in "expr".
627 * The conditions are not added to the index expression. Instead, they
628 * are used to try and simplifty the index expression.
630 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
631 __isl_take isl_set
*cond
)
638 for (i
= 0; i
< expr
->n_arg
; ++i
) {
639 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
645 if (expr
->type
== pet_expr_access
) {
646 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
648 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
649 expr
->acc
.index
, isl_set_copy(cond
));
650 if (!expr
->acc
.access
|| !expr
->acc
.index
)
658 return pet_expr_free(expr
);
661 /* Modify all expressions of type pet_expr_access in "expr"
662 * by calling "fn" on them.
664 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
665 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
673 for (i
= 0; i
< expr
->n_arg
; ++i
) {
674 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
676 return pet_expr_free(expr
);
679 if (expr
->type
== pet_expr_access
)
680 expr
= fn(expr
, user
);
685 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
687 * Return -1 on error (where fn return a negative value is treated as an error).
688 * Otherwise return 0.
690 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
691 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
698 for (i
= 0; i
< expr
->n_arg
; ++i
)
699 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
702 if (expr
->type
== pet_expr_access
)
703 return fn(expr
, user
);
708 /* Modify the access relation and index expression
709 * of the given access expression
710 * based on the given iteration space transformation.
711 * In particular, precompose the access relation and index expression
712 * with the update function.
714 * If the access has any arguments then the domain of the access relation
715 * is a wrapped mapping from the iteration space to the space of
716 * argument values. We only need to change the domain of this wrapped
717 * mapping, so we extend the input transformation with an identity mapping
718 * on the space of argument values.
720 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
722 isl_multi_pw_aff
*update
= user
;
725 update
= isl_multi_pw_aff_copy(update
);
727 space
= isl_map_get_space(expr
->acc
.access
);
728 space
= isl_space_domain(space
);
729 if (!isl_space_is_wrapping(space
))
730 isl_space_free(space
);
732 isl_multi_pw_aff
*id
;
733 space
= isl_space_unwrap(space
);
734 space
= isl_space_range(space
);
735 space
= isl_space_map_from_set(space
);
736 id
= isl_multi_pw_aff_identity(space
);
737 update
= isl_multi_pw_aff_product(update
, id
);
740 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
742 isl_multi_pw_aff_copy(update
));
743 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
744 expr
->acc
.index
, update
);
745 if (!expr
->acc
.access
|| !expr
->acc
.index
)
746 return pet_expr_free(expr
);
751 /* Modify all access relations in "expr" by precomposing them with
752 * the given iteration space transformation.
754 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
755 __isl_take isl_multi_pw_aff
*update
)
757 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
758 isl_multi_pw_aff_free(update
);
762 /* Construct a pet_stmt with given line number and statement
763 * number from a pet_expr.
764 * The initial iteration domain is the zero-dimensional universe.
765 * The name of the domain is given by "label" if it is non-NULL.
766 * Otherwise, the name is constructed as S_<id>.
767 * The domains of all access relations are modified to refer
768 * to the statement iteration domain.
770 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
771 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
773 struct pet_stmt
*stmt
;
777 isl_multi_pw_aff
*add_name
;
783 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
787 dim
= isl_space_set_alloc(ctx
, 0, 0);
789 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
791 snprintf(name
, sizeof(name
), "S_%d", id
);
792 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
794 dom
= isl_set_universe(isl_space_copy(dim
));
795 sched
= isl_map_from_domain(isl_set_copy(dom
));
797 dim
= isl_space_from_domain(dim
);
798 add_name
= isl_multi_pw_aff_zero(dim
);
799 expr
= expr_update_domain(expr
, add_name
);
803 stmt
->schedule
= sched
;
806 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
807 return pet_stmt_free(stmt
);
816 void *pet_stmt_free(struct pet_stmt
*stmt
)
823 isl_set_free(stmt
->domain
);
824 isl_map_free(stmt
->schedule
);
825 pet_expr_free(stmt
->body
);
827 for (i
= 0; i
< stmt
->n_arg
; ++i
)
828 pet_expr_free(stmt
->args
[i
]);
835 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
842 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
843 fprintf(stderr
, "%*s", indent
, "");
844 isl_set_dump(stmt
->domain
);
845 fprintf(stderr
, "%*s", indent
, "");
846 isl_map_dump(stmt
->schedule
);
847 expr_dump(stmt
->body
, indent
);
848 for (i
= 0; i
< stmt
->n_arg
; ++i
)
849 expr_dump(stmt
->args
[i
], indent
+ 2);
852 void pet_stmt_dump(struct pet_stmt
*stmt
)
857 /* Allocate a new pet_type with the given "name" and "definition".
859 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
860 const char *definition
)
862 struct pet_type
*type
;
864 type
= isl_alloc_type(ctx
, struct pet_type
);
868 type
->name
= strdup(name
);
869 type
->definition
= strdup(definition
);
871 if (!type
->name
|| !type
->definition
)
872 return pet_type_free(type
);
877 /* Free "type" and return NULL.
879 struct pet_type
*pet_type_free(struct pet_type
*type
)
885 free(type
->definition
);
891 struct pet_array
*pet_array_free(struct pet_array
*array
)
896 isl_set_free(array
->context
);
897 isl_set_free(array
->extent
);
898 isl_set_free(array
->value_bounds
);
899 free(array
->element_type
);
905 void pet_array_dump(struct pet_array
*array
)
910 isl_set_dump(array
->context
);
911 isl_set_dump(array
->extent
);
912 isl_set_dump(array
->value_bounds
);
913 fprintf(stderr
, "%s %s\n", array
->element_type
,
914 array
->live_out
? "live-out" : "");
917 /* Alloc a pet_scop structure, with extra room for information that
918 * is only used during parsing.
920 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
922 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
925 /* Construct a pet_scop with room for n statements.
927 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
930 struct pet_scop
*scop
;
932 scop
= pet_scop_alloc(ctx
);
936 space
= isl_space_params_alloc(ctx
, 0);
937 scop
->context
= isl_set_universe(isl_space_copy(space
));
938 scop
->context_value
= isl_set_universe(space
);
939 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
940 if (!scop
->context
|| !scop
->stmts
)
941 return pet_scop_free(scop
);
948 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
950 return scop_alloc(ctx
, 0);
953 /* Update "context" with respect to the valid parameter values for "access".
955 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
956 __isl_take isl_set
*context
)
958 context
= isl_set_intersect(context
,
959 isl_map_params(isl_map_copy(access
)));
963 /* Update "context" with respect to the valid parameter values for "expr".
965 * If "expr" represents a ternary operator, then a parameter value
966 * needs to be valid for the condition and for at least one of the
967 * remaining two arguments.
968 * If the condition is an affine expression, then we can be a bit more specific.
969 * The parameter then has to be valid for the second argument for
970 * non-zero accesses and valid for the third argument for zero accesses.
972 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
973 __isl_take isl_set
*context
)
977 if (expr
->type
== pet_expr_ternary
) {
979 isl_set
*context1
, *context2
;
981 is_aff
= pet_expr_is_affine(expr
->args
[0]);
985 context
= expr_extract_context(expr
->args
[0], context
);
986 context1
= expr_extract_context(expr
->args
[1],
987 isl_set_copy(context
));
988 context2
= expr_extract_context(expr
->args
[2], context
);
994 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
995 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
996 zero_set
= isl_map_params(access
);
997 context1
= isl_set_subtract(context1
,
998 isl_set_copy(zero_set
));
999 context2
= isl_set_intersect(context2
, zero_set
);
1002 context
= isl_set_union(context1
, context2
);
1003 context
= isl_set_coalesce(context
);
1008 for (i
= 0; i
< expr
->n_arg
; ++i
)
1009 context
= expr_extract_context(expr
->args
[i
], context
);
1011 if (expr
->type
== pet_expr_access
)
1012 context
= access_extract_context(expr
->acc
.access
, context
);
1016 isl_set_free(context
);
1020 /* Update "context" with respect to the valid parameter values for "stmt".
1022 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
1023 __isl_take isl_set
*context
)
1027 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1028 context
= expr_extract_context(stmt
->args
[i
], context
);
1030 context
= expr_extract_context(stmt
->body
, context
);
1035 /* Construct a pet_scop that contains the given pet_stmt.
1037 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
1039 struct pet_scop
*scop
;
1044 scop
= scop_alloc(ctx
, 1);
1048 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
1052 scop
->stmts
[0] = stmt
;
1056 pet_stmt_free(stmt
);
1057 pet_scop_free(scop
);
1061 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1062 * does it represent an affine expression?
1064 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
1068 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
1075 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1077 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
1078 __isl_take isl_set
*dom
)
1081 pa
= isl_set_indicator_function(set
);
1082 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
1086 /* Return "lhs || rhs", defined on the shared definition domain.
1088 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
1089 __isl_take isl_pw_aff
*rhs
)
1094 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
1095 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
1096 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
1097 isl_pw_aff_non_zero_set(rhs
));
1098 cond
= isl_set_coalesce(cond
);
1099 return indicator_function(cond
, dom
);
1102 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1103 * ext may be equal to either ext1 or ext2.
1105 * The two skips that need to be combined are assumed to be affine expressions.
1107 * We need to skip in ext if we need to skip in either ext1 or ext2.
1108 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1110 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
1111 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
1114 isl_pw_aff
*skip
, *skip1
, *skip2
;
1118 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
1120 if (!ext1
->skip
[type
]) {
1123 ext
->skip
[type
] = ext2
->skip
[type
];
1124 ext2
->skip
[type
] = NULL
;
1127 if (!ext2
->skip
[type
]) {
1130 ext
->skip
[type
] = ext1
->skip
[type
];
1131 ext1
->skip
[type
] = NULL
;
1135 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
1136 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
1137 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
1138 isl_error_internal
, "can only combine affine skips",
1141 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
1142 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
1143 skip
= pw_aff_or(skip1
, skip2
);
1144 isl_multi_pw_aff_free(ext1
->skip
[type
]);
1145 ext1
->skip
[type
] = NULL
;
1146 isl_multi_pw_aff_free(ext2
->skip
[type
]);
1147 ext2
->skip
[type
] = NULL
;
1148 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1149 if (!ext
->skip
[type
])
1154 pet_scop_free(&ext
->scop
);
1158 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1159 * where type takes on the values pet_skip_now and pet_skip_later.
1160 * scop may be equal to either scop1 or scop2.
1162 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
1163 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1165 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1166 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1167 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1169 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1170 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1174 /* Update scop->start and scop->end to include the region from "start"
1175 * to "end". In particular, if scop->end == 0, then "scop" does not
1176 * have any offset information yet and we simply take the information
1177 * from "start" and "end". Otherwise, we update the fields if the
1178 * region from "start" to "end" is not already included.
1180 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1181 unsigned start
, unsigned end
)
1185 if (scop
->end
== 0) {
1186 scop
->start
= start
;
1189 if (start
< scop
->start
)
1190 scop
->start
= start
;
1191 if (end
> scop
->end
)
1198 /* Does "implication" appear in the list of implications of "scop"?
1200 static int is_known_implication(struct pet_scop
*scop
,
1201 struct pet_implication
*implication
)
1205 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1206 struct pet_implication
*pi
= scop
->implications
[i
];
1209 if (pi
->satisfied
!= implication
->satisfied
)
1211 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1221 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1222 * in "scop", removing duplicates (i.e., implications in "scop2" that
1223 * already appear in "scop1").
1225 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1226 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1233 if (scop2
->n_implication
== 0) {
1234 scop
->n_implication
= scop1
->n_implication
;
1235 scop
->implications
= scop1
->implications
;
1236 scop1
->n_implication
= 0;
1237 scop1
->implications
= NULL
;
1241 if (scop1
->n_implication
== 0) {
1242 scop
->n_implication
= scop2
->n_implication
;
1243 scop
->implications
= scop2
->implications
;
1244 scop2
->n_implication
= 0;
1245 scop2
->implications
= NULL
;
1249 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1250 scop1
->n_implication
+ scop2
->n_implication
);
1251 if (!scop
->implications
)
1252 return pet_scop_free(scop
);
1254 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1255 scop
->implications
[i
] = scop1
->implications
[i
];
1256 scop1
->implications
[i
] = NULL
;
1259 scop
->n_implication
= scop1
->n_implication
;
1260 j
= scop1
->n_implication
;
1261 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1264 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1266 return pet_scop_free(scop
);
1269 scop
->implications
[j
++] = scop2
->implications
[i
];
1270 scop2
->implications
[i
] = NULL
;
1272 scop
->n_implication
= j
;
1277 /* Combine the offset information of "scop1" and "scop2" into "scop".
1279 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1280 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1283 scop
= pet_scop_update_start_end(scop
,
1284 scop1
->start
, scop1
->end
);
1286 scop
= pet_scop_update_start_end(scop
,
1287 scop2
->start
, scop2
->end
);
1291 /* Construct a pet_scop that contains the offset information,
1292 * arrays, statements and skip information in "scop1" and "scop2".
1294 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1295 struct pet_scop
*scop2
)
1298 struct pet_scop
*scop
= NULL
;
1300 if (!scop1
|| !scop2
)
1303 if (scop1
->n_stmt
== 0) {
1304 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1305 pet_scop_free(scop1
);
1309 if (scop2
->n_stmt
== 0) {
1310 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1311 pet_scop_free(scop2
);
1315 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1319 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1320 scop1
->n_array
+ scop2
->n_array
);
1323 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1325 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1326 scop
->stmts
[i
] = scop1
->stmts
[i
];
1327 scop1
->stmts
[i
] = NULL
;
1330 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1331 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1332 scop2
->stmts
[i
] = NULL
;
1335 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1336 scop
->arrays
[i
] = scop1
->arrays
[i
];
1337 scop1
->arrays
[i
] = NULL
;
1340 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1341 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1342 scop2
->arrays
[i
] = NULL
;
1345 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1346 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1347 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1348 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1349 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1351 pet_scop_free(scop1
);
1352 pet_scop_free(scop2
);
1355 pet_scop_free(scop1
);
1356 pet_scop_free(scop2
);
1357 pet_scop_free(scop
);
1361 /* Apply the skip condition "skip" to "scop".
1362 * That is, make sure "scop" is not executed when the condition holds.
1364 * If "skip" is an affine expression, we add the conditions under
1365 * which the expression is zero to the iteration domains.
1366 * Otherwise, we add a filter on the variable attaining the value zero.
1368 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1369 __isl_take isl_multi_pw_aff
*skip
)
1378 is_aff
= multi_pw_aff_is_affine(skip
);
1383 return pet_scop_filter(scop
, skip
, 0);
1385 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1386 isl_multi_pw_aff_free(skip
);
1387 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
1388 scop
= pet_scop_restrict(scop
, zero
);
1392 isl_multi_pw_aff_free(skip
);
1393 return pet_scop_free(scop
);
1396 /* Construct a pet_scop that contains the arrays, statements and
1397 * skip information in "scop1" and "scop2", where the two scops
1398 * are executed "in sequence". That is, breaks and continues
1399 * in scop1 have an effect on scop2.
1401 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1402 struct pet_scop
*scop2
)
1404 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1405 scop2
= restrict_skip(scop2
,
1406 pet_scop_get_skip(scop1
, pet_skip_now
));
1407 return pet_scop_add(ctx
, scop1
, scop2
);
1410 /* Construct a pet_scop that contains the arrays, statements and
1411 * skip information in "scop1" and "scop2", where the two scops
1412 * are executed "in parallel". That is, any break or continue
1413 * in scop1 has no effect on scop2.
1415 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1416 struct pet_scop
*scop2
)
1418 return pet_scop_add(ctx
, scop1
, scop2
);
1421 void *pet_implication_free(struct pet_implication
*implication
)
1428 isl_map_free(implication
->extension
);
1434 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1437 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1441 isl_set_free(scop
->context
);
1442 isl_set_free(scop
->context_value
);
1444 for (i
= 0; i
< scop
->n_type
; ++i
)
1445 pet_type_free(scop
->types
[i
]);
1448 for (i
= 0; i
< scop
->n_array
; ++i
)
1449 pet_array_free(scop
->arrays
[i
]);
1452 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1453 pet_stmt_free(scop
->stmts
[i
]);
1455 if (scop
->implications
)
1456 for (i
= 0; i
< scop
->n_implication
; ++i
)
1457 pet_implication_free(scop
->implications
[i
]);
1458 free(scop
->implications
);
1459 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1460 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1465 void pet_type_dump(struct pet_type
*type
)
1470 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1473 void pet_implication_dump(struct pet_implication
*implication
)
1478 fprintf(stderr
, "%d\n", implication
->satisfied
);
1479 isl_map_dump(implication
->extension
);
1482 void pet_scop_dump(struct pet_scop
*scop
)
1485 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1490 isl_set_dump(scop
->context
);
1491 isl_set_dump(scop
->context_value
);
1492 for (i
= 0; i
< scop
->n_type
; ++i
)
1493 pet_type_dump(scop
->types
[i
]);
1494 for (i
= 0; i
< scop
->n_array
; ++i
)
1495 pet_array_dump(scop
->arrays
[i
]);
1496 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1497 pet_stmt_dump(scop
->stmts
[i
]);
1498 for (i
= 0; i
< scop
->n_implication
; ++i
)
1499 pet_implication_dump(scop
->implications
[i
]);
1502 fprintf(stderr
, "skip\n");
1503 isl_multi_pw_aff_dump(ext
->skip
[0]);
1504 isl_multi_pw_aff_dump(ext
->skip
[1]);
1508 /* Return 1 if the two pet_arrays are equivalent.
1510 * We don't compare element_size as this may be target dependent.
1512 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1514 if (!array1
|| !array2
)
1517 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1519 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1521 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1523 if (array1
->value_bounds
&&
1524 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1526 if (strcmp(array1
->element_type
, array2
->element_type
))
1528 if (array1
->live_out
!= array2
->live_out
)
1530 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1532 if (array1
->declared
!= array2
->declared
)
1534 if (array1
->exposed
!= array2
->exposed
)
1540 /* Return 1 if the two pet_stmts are equivalent.
1542 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1546 if (!stmt1
|| !stmt2
)
1549 if (stmt1
->line
!= stmt2
->line
)
1551 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1553 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1555 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1557 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1559 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1560 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1567 /* Return 1 if the two pet_types are equivalent.
1569 * We only compare the names of the types since the exact representation
1570 * of the definition may depend on the version of clang being used.
1572 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1574 if (!type1
|| !type2
)
1577 if (strcmp(type1
->name
, type2
->name
))
1583 /* Return 1 if the two pet_implications are equivalent.
1585 int pet_implication_is_equal(struct pet_implication
*implication1
,
1586 struct pet_implication
*implication2
)
1588 if (!implication1
|| !implication2
)
1591 if (implication1
->satisfied
!= implication2
->satisfied
)
1593 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1599 /* Return 1 if the two pet_scops are equivalent.
1601 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1605 if (!scop1
|| !scop2
)
1608 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1610 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1613 if (scop1
->n_type
!= scop2
->n_type
)
1615 for (i
= 0; i
< scop1
->n_type
; ++i
)
1616 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1619 if (scop1
->n_array
!= scop2
->n_array
)
1621 for (i
= 0; i
< scop1
->n_array
; ++i
)
1622 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1625 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1627 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1628 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1631 if (scop1
->n_implication
!= scop2
->n_implication
)
1633 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1634 if (!pet_implication_is_equal(scop1
->implications
[i
],
1635 scop2
->implications
[i
]))
1641 /* Prefix the schedule of "stmt" with an extra dimension with constant
1644 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1649 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1650 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1651 if (!stmt
->schedule
)
1652 return pet_stmt_free(stmt
);
1657 /* Prefix the schedules of all statements in "scop" with an extra
1658 * dimension with constant value "pos".
1660 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1667 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1668 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1669 if (!scop
->stmts
[i
])
1670 return pet_scop_free(scop
);
1676 /* Given a set with a parameter at "param_pos" that refers to the
1677 * iterator, "move" the iterator to the first set dimension.
1678 * That is, essentially equate the parameter to the first set dimension
1679 * and then project it out.
1681 * The first set dimension may however refer to a virtual iterator,
1682 * while the parameter refers to the "real" iterator.
1683 * We therefore need to take into account the affine expression "iv_map", which
1684 * expresses the real iterator in terms of the virtual iterator.
1685 * In particular, we equate the set dimension to the input of the map
1686 * and the parameter to the output of the map and then project out
1687 * everything we don't need anymore.
1689 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1690 int param_pos
, __isl_take isl_aff
*iv_map
)
1692 isl_map
*map
, *map2
;
1693 map
= isl_map_from_domain(set
);
1694 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1695 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1696 map2
= isl_map_from_aff(iv_map
);
1697 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1698 map
= isl_map_apply_range(map
, map2
);
1699 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1700 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1701 return isl_map_domain(map
);
1704 /* Data used in embed_access.
1705 * extend adds an iterator to the iteration domain (through precomposition).
1706 * iv_map expresses the real iterator in terms of the virtual iterator
1707 * var_id represents the induction variable of the corresponding loop
1709 struct pet_embed_access
{
1710 isl_multi_pw_aff
*extend
;
1715 /* Given an index expression, return an expression for the outer iterator.
1717 static __isl_give isl_aff
*index_outer_iterator(
1718 __isl_take isl_multi_pw_aff
*index
)
1721 isl_local_space
*ls
;
1723 space
= isl_multi_pw_aff_get_domain_space(index
);
1724 isl_multi_pw_aff_free(index
);
1726 ls
= isl_local_space_from_space(space
);
1727 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1730 /* Replace an index expression that references the new (outer) iterator variable
1731 * by one that references the corresponding (real) iterator.
1733 * The input index expression is of the form
1735 * { S[i',...] -> i[] }
1737 * where i' refers to the virtual iterator.
1739 * iv_map is of the form
1743 * Return the index expression
1745 * { S[i',...] -> [i] }
1747 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1748 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1753 aff
= index_outer_iterator(index
);
1754 space
= isl_aff_get_space(aff
);
1755 iv_map
= isl_aff_align_params(iv_map
, space
);
1756 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1758 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1761 /* Given an index expression "index" that refers to the (real) iterator
1762 * through the parameter at position "pos", plug in "iv_map", expressing
1763 * the real iterator in terms of the virtual (outer) iterator.
1765 * In particular, the index expression is of the form
1767 * [..., i, ...] -> { S[i',...] -> ... i ... }
1769 * where i refers to the real iterator and i' refers to the virtual iterator.
1771 * iv_map is of the form
1775 * Return the index expression
1777 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1780 * We first move the parameter to the input
1782 * [..., ...] -> { [i, i',...] -> ... i ... }
1786 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1788 * and then combine the two to obtain the desired result.
1790 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1791 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1793 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1796 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1797 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1798 isl_dim_param
, pos
, 1);
1800 space
= isl_space_map_from_set(space
);
1801 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1802 iv_map
= isl_aff_align_params(iv_map
, space
);
1803 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1804 ma
= isl_multi_aff_flat_range_product(
1805 isl_multi_aff_from_aff(iv_map
), ma
);
1806 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1811 /* Does the index expression "index" reference a virtual array, i.e.,
1812 * one with user pointer equal to NULL?
1814 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1819 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1821 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1822 is_virtual
= !isl_id_get_user(id
);
1828 /* Does the access relation "access" reference a virtual array, i.e.,
1829 * one with user pointer equal to NULL?
1831 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1836 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1838 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1839 is_virtual
= !isl_id_get_user(id
);
1845 /* Embed the given index expression in an extra outer loop.
1846 * The domain of the index expression has already been updated.
1848 * If the access refers to the induction variable, then it is
1849 * turned into an access to the set of integers with index (and value)
1850 * equal to the induction variable.
1852 * If the accessed array is a virtual array (with user
1853 * pointer equal to NULL), as created by create_test_index,
1854 * then it is extended along with the domain of the index expression.
1856 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1857 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1859 isl_id
*array_id
= NULL
;
1862 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1863 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1864 if (array_id
== data
->var_id
) {
1865 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1866 } else if (index_is_virtual_array(index
)) {
1868 isl_multi_pw_aff
*mpa
;
1870 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1871 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1872 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1873 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1874 isl_id_copy(array_id
));
1876 isl_id_free(array_id
);
1878 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1879 isl_dim_param
, data
->var_id
);
1881 index
= index_internalize_iv(index
, pos
,
1882 isl_aff_copy(data
->iv_map
));
1883 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1884 isl_id_copy(data
->var_id
));
1889 /* Embed the given access relation in an extra outer loop.
1890 * The domain of the access relation has already been updated.
1892 * If the access refers to the induction variable, then it is
1893 * turned into an access to the set of integers with index (and value)
1894 * equal to the induction variable.
1896 * If the induction variable appears in the constraints (as a parameter),
1897 * then the parameter is equated to the newly introduced iteration
1898 * domain dimension and subsequently projected out.
1900 * Similarly, if the accessed array is a virtual array (with user
1901 * pointer equal to NULL), as created by create_test_index,
1902 * then it is extended along with the domain of the access.
1904 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1905 struct pet_embed_access
*data
)
1907 isl_id
*array_id
= NULL
;
1910 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1911 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1912 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
1913 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1914 access
= isl_map_equate(access
,
1915 isl_dim_in
, 0, isl_dim_out
, 0);
1916 if (array_id
== data
->var_id
)
1917 access
= isl_map_apply_range(access
,
1918 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1920 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1921 isl_id_copy(array_id
));
1923 isl_id_free(array_id
);
1925 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1927 isl_set
*set
= isl_map_wrap(access
);
1928 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1929 access
= isl_set_unwrap(set
);
1931 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1932 isl_id_copy(data
->var_id
));
1937 /* Given an access expression, embed the associated access relation and
1938 * index expression in an extra outer loop.
1940 * We first update the domains to insert the extra dimension and
1941 * then update the access relation and index expression to take
1942 * into account the mapping "iv_map" from virtual iterator
1945 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1948 struct pet_embed_access
*data
= user
;
1950 expr
= update_domain(expr
, data
->extend
);
1954 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
1955 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
1956 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1957 return pet_expr_free(expr
);
1962 /* Embed all access subexpressions of "expr" in an extra loop.
1963 * "extend" inserts an outer loop iterator in the iteration domains
1964 * (through precomposition).
1965 * "iv_map" expresses the real iterator in terms of the virtual iterator
1966 * "var_id" represents the induction variable.
1968 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1969 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1970 __isl_keep isl_id
*var_id
)
1972 struct pet_embed_access data
=
1973 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1975 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1976 isl_aff_free(iv_map
);
1977 isl_multi_pw_aff_free(extend
);
1981 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1982 * "dom" and schedule "sched". "var_id" represents the induction variable
1983 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1984 * That is, it expresses the iterator that some of the parameters in "stmt"
1985 * may refer to in terms of the iterator used in "dom" and
1986 * the domain of "sched".
1988 * The iteration domain and schedule of the statement are updated
1989 * according to the iteration domain and schedule of the new loop.
1990 * If stmt->domain is a wrapped map, then the iteration domain
1991 * is the domain of this map, so we need to be careful to adjust
1994 * If the induction variable appears in the constraints (as a parameter)
1995 * of the current iteration domain or the schedule of the statement,
1996 * then the parameter is equated to the newly introduced iteration
1997 * domain dimension and subsequently projected out.
1999 * Finally, all access relations are updated based on the extra loop.
2001 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
2002 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
2003 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
2009 isl_multi_pw_aff
*extend
;
2014 if (isl_set_is_wrapping(stmt
->domain
)) {
2019 map
= isl_set_unwrap(stmt
->domain
);
2020 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
2021 ran_dim
= isl_space_range(isl_map_get_space(map
));
2022 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
2023 isl_set_universe(ran_dim
));
2024 map
= isl_map_flat_domain_product(ext
, map
);
2025 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
2026 isl_id_copy(stmt_id
));
2027 dim
= isl_space_domain(isl_map_get_space(map
));
2028 stmt
->domain
= isl_map_wrap(map
);
2030 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
2031 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
2033 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
2034 isl_id_copy(stmt_id
));
2035 dim
= isl_set_get_space(stmt
->domain
);
2038 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
2040 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
2041 isl_aff_copy(iv_map
));
2043 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
2044 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
2045 isl_dim_in
, stmt_id
);
2047 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
2049 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
2050 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
2051 stmt
->schedule
= isl_set_unwrap(set
);
2054 dim
= isl_space_map_from_set(dim
);
2055 extend
= isl_multi_pw_aff_identity(dim
);
2056 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
2057 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
2058 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
2059 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2060 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
2061 isl_multi_pw_aff_copy(extend
),
2062 isl_aff_copy(iv_map
), var_id
);
2063 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
2066 isl_id_free(var_id
);
2068 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2070 return pet_stmt_free(stmt
);
2071 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2072 return pet_stmt_free(stmt
);
2076 isl_map_free(sched
);
2077 isl_aff_free(iv_map
);
2078 isl_id_free(var_id
);
2082 /* Embed the given pet_array in an extra outer loop with iteration domain
2084 * This embedding only has an effect on virtual arrays (those with
2085 * user pointer equal to NULL), which need to be extended along with
2086 * the iteration domain.
2088 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
2089 __isl_take isl_set
*dom
)
2091 isl_id
*array_id
= NULL
;
2096 if (isl_set_has_tuple_id(array
->extent
))
2097 array_id
= isl_set_get_tuple_id(array
->extent
);
2099 if (array_id
&& !isl_id_get_user(array_id
)) {
2100 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
2101 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
2103 return pet_array_free(array
);
2106 isl_id_free(array_id
);
2115 /* Project out all unnamed parameters from "set" and return the result.
2117 static __isl_give isl_set
*set_project_out_unnamed_params(
2118 __isl_take isl_set
*set
)
2122 n
= isl_set_dim(set
, isl_dim_param
);
2123 for (i
= n
- 1; i
>= 0; --i
) {
2124 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
2126 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
2132 /* Update the context with respect to an embedding into a loop
2133 * with iteration domain "dom" and induction variable "id".
2134 * "iv_map" expresses the real iterator (parameter "id") in terms
2135 * of a possibly virtual iterator (used in "dom").
2137 * If the current context is independent of "id", we don't need
2139 * Otherwise, a parameter value is invalid for the embedding if
2140 * any of the corresponding iterator values is invalid.
2141 * That is, a parameter value is valid only if all the corresponding
2142 * iterator values are valid.
2143 * We therefore compute the set of parameters
2145 * forall i in dom : valid (i)
2149 * not exists i in dom : not valid(i)
2153 * not exists i in dom \ valid(i)
2155 * Before we subtract valid(i) from dom, we first need to substitute
2156 * the real iterator for the virtual iterator.
2158 * If there are any unnamed parameters in "dom", then we consider
2159 * a parameter value to be valid if it is valid for any value of those
2160 * unnamed parameters. They are therefore projected out at the end.
2162 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
2163 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
2164 __isl_keep isl_id
*id
)
2169 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
2173 context
= isl_set_from_params(context
);
2174 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
2175 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
2176 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
2177 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
2178 context
= isl_set_preimage_multi_aff(context
, ma
);
2179 context
= isl_set_subtract(isl_set_copy(dom
), context
);
2180 context
= isl_set_params(context
);
2181 context
= isl_set_complement(context
);
2182 context
= set_project_out_unnamed_params(context
);
2186 /* Update the implication with respect to an embedding into a loop
2187 * with iteration domain "dom".
2189 * Since embed_access extends virtual arrays along with the domain
2190 * of the access, we need to do the same with domain and range
2191 * of the implication. Since the original implication is only valid
2192 * within a given iteration of the loop, the extended implication
2193 * maps the extra array dimension corresponding to the extra loop
2196 static struct pet_implication
*pet_implication_embed(
2197 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
2205 map
= isl_set_identity(dom
);
2206 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
2207 map
= isl_map_flat_product(map
, implication
->extension
);
2208 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
2209 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
2210 implication
->extension
= map
;
2211 if (!implication
->extension
)
2212 return pet_implication_free(implication
);
2220 /* Embed all statements and arrays in "scop" in an extra outer loop
2221 * with iteration domain "dom" and schedule "sched".
2222 * "id" represents the induction variable of the loop.
2223 * "iv_map" maps a possibly virtual iterator to the real iterator.
2224 * That is, it expresses the iterator that some of the parameters in "scop"
2225 * may refer to in terms of the iterator used in "dom" and
2226 * the domain of "sched".
2228 * Any skip conditions within the loop have no effect outside of the loop.
2229 * The caller is responsible for making sure skip[pet_skip_later] has been
2230 * taken into account.
2232 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
2233 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
2234 __isl_take isl_id
*id
)
2241 pet_scop_reset_skip(scop
, pet_skip_now
);
2242 pet_scop_reset_skip(scop
, pet_skip_later
);
2244 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
2248 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2249 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
2250 isl_set_copy(dom
), isl_map_copy(sched
),
2251 isl_aff_copy(iv_map
), isl_id_copy(id
));
2252 if (!scop
->stmts
[i
])
2256 for (i
= 0; i
< scop
->n_array
; ++i
) {
2257 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
2259 if (!scop
->arrays
[i
])
2263 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2264 scop
->implications
[i
] =
2265 pet_implication_embed(scop
->implications
[i
],
2267 if (!scop
->implications
[i
])
2272 isl_map_free(sched
);
2273 isl_aff_free(iv_map
);
2278 isl_map_free(sched
);
2279 isl_aff_free(iv_map
);
2281 return pet_scop_free(scop
);
2284 /* Add extra conditions on the parameters to iteration domain of "stmt".
2286 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
2287 __isl_take isl_set
*cond
)
2292 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
2297 return pet_stmt_free(stmt
);
2300 /* Add extra conditions to scop->skip[type].
2302 * The new skip condition only holds if it held before
2303 * and the condition is true. It does not hold if it did not hold
2304 * before or the condition is false.
2306 * The skip condition is assumed to be an affine expression.
2308 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
2309 enum pet_skip type
, __isl_keep isl_set
*cond
)
2311 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2317 if (!ext
->skip
[type
])
2320 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
2321 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
2322 isl_error_internal
, "can only resrict affine skips",
2323 return pet_scop_free(scop
));
2325 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2326 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
2327 cond
= isl_set_copy(cond
);
2328 cond
= isl_set_from_params(cond
);
2329 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
2330 skip
= indicator_function(cond
, dom
);
2331 isl_multi_pw_aff_free(ext
->skip
[type
]);
2332 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
2333 if (!ext
->skip
[type
])
2334 return pet_scop_free(scop
);
2339 /* Add extra conditions on the parameters to all iteration domains
2340 * and skip conditions.
2342 * A parameter value is valid for the result if it was valid
2343 * for the original scop and satisfies "cond" or if it does
2344 * not satisfy "cond" as in this case the scop is not executed
2345 * and the original constraints on the parameters are irrelevant.
2347 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
2348 __isl_take isl_set
*cond
)
2352 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
2353 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
2358 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
2359 scop
->context
= isl_set_union(scop
->context
,
2360 isl_set_complement(isl_set_copy(cond
)));
2361 scop
->context
= isl_set_coalesce(scop
->context
);
2362 scop
->context
= set_project_out_unnamed_params(scop
->context
);
2366 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2367 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
2368 isl_set_copy(cond
));
2369 if (!scop
->stmts
[i
])
2377 return pet_scop_free(scop
);
2380 /* Construct a function that (upon precomposition) inserts
2381 * a filter value with name "id" and value "satisfied"
2382 * in the list of filter values embedded in the set space "space".
2384 * If "space" does not contain any filter values yet, we first create
2385 * a function that inserts 0 filter values, i.e.,
2387 * [space -> []] -> space
2389 * We can now assume that space is of the form [dom -> [filters]]
2390 * We construct an identity mapping on dom and a mapping on filters
2391 * that (upon precomposition) inserts the new filter
2394 * [satisfied, filters] -> [filters]
2396 * and then compute the cross product
2398 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2400 static __isl_give isl_pw_multi_aff
*insert_filter_pma(
2401 __isl_take isl_space
*space
, __isl_take isl_id
*id
, int satisfied
)
2405 isl_pw_multi_aff
*pma0
, *pma
, *pma_dom
, *pma_ran
;
2408 if (isl_space_is_wrapping(space
)) {
2409 space2
= isl_space_map_from_set(isl_space_copy(space
));
2410 ma
= isl_multi_aff_identity(space2
);
2411 space
= isl_space_unwrap(space
);
2413 space
= isl_space_from_domain(space
);
2414 ma
= isl_multi_aff_domain_map(isl_space_copy(space
));
2417 space2
= isl_space_domain(isl_space_copy(space
));
2418 pma_dom
= isl_pw_multi_aff_identity(isl_space_map_from_set(space2
));
2419 space
= isl_space_range(space
);
2420 space
= isl_space_insert_dims(space
, isl_dim_set
, 0, 1);
2421 pma_ran
= isl_pw_multi_aff_project_out_map(space
, isl_dim_set
, 0, 1);
2422 pma_ran
= isl_pw_multi_aff_set_dim_id(pma_ran
, isl_dim_in
, 0, id
);
2423 pma_ran
= isl_pw_multi_aff_fix_si(pma_ran
, isl_dim_in
, 0, satisfied
);
2424 pma
= isl_pw_multi_aff_product(pma_dom
, pma_ran
);
2426 pma0
= isl_pw_multi_aff_from_multi_aff(ma
);
2427 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(pma0
, pma
);
2432 /* Insert an argument expression corresponding to "test" in front
2433 * of the list of arguments described by *n_arg and *args.
2435 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2436 __isl_keep isl_multi_pw_aff
*test
)
2439 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
2445 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2449 struct pet_expr
**ext
;
2450 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2453 for (i
= 0; i
< *n_arg
; ++i
)
2454 ext
[1 + i
] = (*args
)[i
];
2459 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2466 /* Make the expression "expr" depend on the value of "test"
2467 * being equal to "satisfied".
2469 * If "test" is an affine expression, we simply add the conditions
2470 * on the expression having the value "satisfied" to all access relations
2471 * and index expressions.
2473 * Otherwise, we add a filter to "expr" (which is then assumed to be
2474 * an access expression) corresponding to "test" being equal to "satisfied".
2476 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2477 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2482 isl_pw_multi_aff
*pma
;
2487 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2491 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2492 isl_multi_pw_aff_free(test
);
2494 cond
= isl_pw_aff_non_zero_set(pa
);
2496 cond
= isl_pw_aff_zero_set(pa
);
2497 return pet_expr_restrict(expr
, isl_set_params(cond
));
2500 ctx
= isl_multi_pw_aff_get_ctx(test
);
2501 if (expr
->type
!= pet_expr_access
)
2502 isl_die(ctx
, isl_error_invalid
,
2503 "can only filter access expressions", goto error
);
2505 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2506 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2507 pma
= insert_filter_pma(space
, id
, satisfied
);
2509 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
2511 isl_pw_multi_aff_copy(pma
));
2512 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2513 expr
->acc
.index
, pma
);
2514 if (!expr
->acc
.access
|| !expr
->acc
.index
)
2517 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2520 isl_multi_pw_aff_free(test
);
2523 isl_multi_pw_aff_free(test
);
2524 return pet_expr_free(expr
);
2527 /* Look through the applications in "scop" for any that can be
2528 * applied to the filter expressed by "map" and "satisified".
2529 * If there is any, then apply it to "map" and return the result.
2530 * Otherwise, return "map".
2531 * "id" is the identifier of the virtual array.
2533 * We only introduce at most one implication for any given virtual array,
2534 * so we can apply the implication and return as soon as we find one.
2536 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2537 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2541 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2542 struct pet_implication
*pi
= scop
->implications
[i
];
2545 if (pi
->satisfied
!= satisfied
)
2547 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2552 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2558 /* Is the filter expressed by "test" and "satisfied" implied
2559 * by filter "pos" on "domain", with filter "expr", taking into
2560 * account the implications of "scop"?
2562 * For filter on domain implying that expressed by "test" and "satisfied",
2563 * the filter needs to be an access to the same (virtual) array as "test" and
2564 * the filter value needs to be equal to "satisfied".
2565 * Moreover, the filter access relation, possibly extended by
2566 * the implications in "scop" needs to contain "test".
2568 static int implies_filter(struct pet_scop
*scop
,
2569 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2570 __isl_keep isl_map
*test
, int satisfied
)
2572 isl_id
*test_id
, *arg_id
;
2579 if (expr
->type
!= pet_expr_access
)
2581 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2582 arg_id
= pet_expr_access_get_id(expr
);
2583 isl_id_free(arg_id
);
2584 isl_id_free(test_id
);
2585 if (test_id
!= arg_id
)
2587 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2588 is_int
= isl_val_is_int(val
);
2590 s
= isl_val_get_num_si(val
);
2599 implied
= isl_map_copy(expr
->acc
.access
);
2600 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2601 is_subset
= isl_map_is_subset(test
, implied
);
2602 isl_map_free(implied
);
2607 /* Is the filter expressed by "test" and "satisfied" implied
2608 * by any of the filters on the domain of "stmt", taking into
2609 * account the implications of "scop"?
2611 static int filter_implied(struct pet_scop
*scop
,
2612 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2620 if (!scop
|| !stmt
|| !test
)
2622 if (scop
->n_implication
== 0)
2624 if (stmt
->n_arg
== 0)
2627 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2628 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2631 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2632 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2633 test_map
, satisfied
);
2634 if (implied
< 0 || implied
)
2638 isl_map_free(test_map
);
2639 isl_map_free(domain
);
2643 /* Make the statement "stmt" depend on the value of "test"
2644 * being equal to "satisfied" by adjusting stmt->domain.
2646 * The domain of "test" corresponds to the (zero or more) outer dimensions
2647 * of the iteration domain.
2649 * We first extend "test" to apply to the entire iteration domain and
2650 * then check if the filter that we are about to add is implied
2651 * by any of the current filters, possibly taking into account
2652 * the implications in "scop". If so, we leave "stmt" untouched and return.
2654 * Otherwise, we insert an argument corresponding to a read to "test"
2655 * from the iteration domain of "stmt" in front of the list of arguments.
2656 * We also insert a corresponding output dimension in the wrapped
2657 * map contained in stmt->domain, with value set to "satisfied".
2659 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2660 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2666 isl_pw_multi_aff
*pma
;
2667 isl_multi_aff
*add_dom
;
2669 isl_local_space
*ls
;
2675 space
= isl_set_get_space(stmt
->domain
);
2676 if (isl_space_is_wrapping(space
))
2677 space
= isl_space_domain(isl_space_unwrap(space
));
2678 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2679 space
= isl_space_from_domain(space
);
2680 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2681 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2682 ls
= isl_local_space_from_space(isl_space_domain(space
));
2683 for (i
= 0; i
< n_test_dom
; ++i
) {
2685 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2687 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2689 isl_local_space_free(ls
);
2690 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2692 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2696 isl_multi_pw_aff_free(test
);
2700 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2701 pma
= insert_filter_pma(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2702 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2704 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2707 isl_multi_pw_aff_free(test
);
2710 isl_multi_pw_aff_free(test
);
2711 return pet_stmt_free(stmt
);
2714 /* Does "scop" have a skip condition of the given "type"?
2716 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2718 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2722 return ext
->skip
[type
] != NULL
;
2725 /* Does "scop" have a skip condition of the given "type" that
2726 * is an affine expression?
2728 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2730 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2734 if (!ext
->skip
[type
])
2736 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2739 /* Does "scop" have a skip condition of the given "type" that
2740 * is not an affine expression?
2742 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2744 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2749 if (!ext
->skip
[type
])
2751 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2757 /* Does "scop" have a skip condition of the given "type" that
2758 * is affine and holds on the entire domain?
2760 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2762 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2768 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2769 if (is_aff
< 0 || !is_aff
)
2772 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2773 set
= isl_pw_aff_non_zero_set(pa
);
2774 is_univ
= isl_set_plain_is_universe(set
);
2780 /* Replace scop->skip[type] by "skip".
2782 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2783 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2785 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2790 isl_multi_pw_aff_free(ext
->skip
[type
]);
2791 ext
->skip
[type
] = skip
;
2795 isl_multi_pw_aff_free(skip
);
2796 return pet_scop_free(scop
);
2799 /* Return a copy of scop->skip[type].
2801 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2804 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2809 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2812 /* Assuming scop->skip[type] is an affine expression,
2813 * return the constraints on the parameters for which the skip condition
2816 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2819 isl_multi_pw_aff
*skip
;
2822 skip
= pet_scop_get_skip(scop
, type
);
2823 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2824 isl_multi_pw_aff_free(skip
);
2825 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2828 /* Return the identifier of the variable that is accessed by
2829 * the skip condition of the given type.
2831 * The skip condition is assumed not to be an affine condition.
2833 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2836 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2841 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2844 /* Return an access pet_expr corresponding to the skip condition
2845 * of the given type.
2847 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2850 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2853 /* Drop the the skip condition scop->skip[type].
2855 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2857 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2862 isl_multi_pw_aff_free(ext
->skip
[type
]);
2863 ext
->skip
[type
] = NULL
;
2866 /* Make the skip condition (if any) depend on the value of "test" being
2867 * equal to "satisfied".
2869 * We only support the case where the original skip condition is universal,
2870 * i.e., where skipping is unconditional, and where satisfied == 1.
2871 * In this case, the skip condition is changed to skip only when
2872 * "test" is equal to one.
2874 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2875 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2881 if (!pet_scop_has_skip(scop
, type
))
2885 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2887 return pet_scop_free(scop
);
2888 if (satisfied
&& is_univ
) {
2889 isl_space
*space
= isl_multi_pw_aff_get_space(test
);
2890 isl_multi_pw_aff
*skip
;
2891 skip
= isl_multi_pw_aff_zero(space
);
2892 scop
= pet_scop_set_skip(scop
, type
, skip
);
2896 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2897 "skip expression cannot be filtered",
2898 return pet_scop_free(scop
));
2904 /* Make all statements in "scop" depend on the value of "test"
2905 * being equal to "satisfied" by adjusting their domains.
2907 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2908 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2912 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2913 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2918 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2919 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2920 isl_multi_pw_aff_copy(test
), satisfied
);
2921 if (!scop
->stmts
[i
])
2925 isl_multi_pw_aff_free(test
);
2928 isl_multi_pw_aff_free(test
);
2929 return pet_scop_free(scop
);
2932 /* Add all parameters in "expr" to "dim" and return the result.
2934 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2935 __isl_take isl_space
*dim
)
2941 for (i
= 0; i
< expr
->n_arg
; ++i
)
2943 dim
= expr_collect_params(expr
->args
[i
], dim
);
2945 if (expr
->type
== pet_expr_access
)
2946 dim
= isl_space_align_params(dim
,
2947 isl_map_get_space(expr
->acc
.access
));
2951 pet_expr_free(expr
);
2952 return isl_space_free(dim
);
2955 /* Add all parameters in "stmt" to "dim" and return the result.
2957 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2958 __isl_take isl_space
*dim
)
2963 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2964 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2965 dim
= expr_collect_params(stmt
->body
, dim
);
2969 isl_space_free(dim
);
2970 return pet_stmt_free(stmt
);
2973 /* Add all parameters in "array" to "dim" and return the result.
2975 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2976 __isl_take isl_space
*dim
)
2981 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2982 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2986 pet_array_free(array
);
2987 return isl_space_free(dim
);
2990 /* Add all parameters in "scop" to "dim" and return the result.
2992 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2993 __isl_take isl_space
*dim
)
3000 for (i
= 0; i
< scop
->n_array
; ++i
)
3001 dim
= array_collect_params(scop
->arrays
[i
], dim
);
3003 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3004 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
3008 isl_space_free(dim
);
3009 pet_scop_free(scop
);
3013 /* Add all parameters in "dim" to all access relations and index expressions
3016 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
3017 __isl_take isl_space
*dim
)
3024 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3026 expr_propagate_params(expr
->args
[i
],
3027 isl_space_copy(dim
));
3032 if (expr
->type
== pet_expr_access
) {
3033 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
3034 isl_space_copy(dim
));
3035 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
3036 isl_space_copy(dim
));
3037 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3041 isl_space_free(dim
);
3044 isl_space_free(dim
);
3045 return pet_expr_free(expr
);
3048 /* Add all parameters in "dim" to the domain, schedule and
3049 * all access relations in "stmt".
3051 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
3052 __isl_take isl_space
*dim
)
3057 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
3058 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
3059 isl_space_copy(dim
));
3060 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
3062 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3065 isl_space_free(dim
);
3068 isl_space_free(dim
);
3069 return pet_stmt_free(stmt
);
3072 /* Add all parameters in "dim" to "array".
3074 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
3075 __isl_take isl_space
*dim
)
3080 array
->context
= isl_set_align_params(array
->context
,
3081 isl_space_copy(dim
));
3082 array
->extent
= isl_set_align_params(array
->extent
,
3083 isl_space_copy(dim
));
3084 if (array
->value_bounds
) {
3085 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
3086 isl_space_copy(dim
));
3087 if (!array
->value_bounds
)
3091 if (!array
->context
|| !array
->extent
)
3094 isl_space_free(dim
);
3097 isl_space_free(dim
);
3098 return pet_array_free(array
);
3101 /* Add all parameters in "dim" to "scop".
3103 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
3104 __isl_take isl_space
*dim
)
3111 for (i
= 0; i
< scop
->n_array
; ++i
) {
3112 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
3113 isl_space_copy(dim
));
3114 if (!scop
->arrays
[i
])
3118 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3119 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
3120 isl_space_copy(dim
));
3121 if (!scop
->stmts
[i
])
3125 isl_space_free(dim
);
3128 isl_space_free(dim
);
3129 return pet_scop_free(scop
);
3132 /* Update all isl_sets and isl_maps in "scop" such that they all
3133 * have the same parameters.
3135 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
3142 dim
= isl_set_get_space(scop
->context
);
3143 dim
= scop_collect_params(scop
, dim
);
3145 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
3146 scop
= scop_propagate_params(scop
, dim
);
3151 /* Check if the given index expression accesses a (0D) array that corresponds
3152 * to one of the parameters in "dim". If so, replace the array access
3153 * by an access to the set of integers with as index (and value)
3156 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
3157 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
3159 isl_local_space
*ls
;
3160 isl_id
*array_id
= NULL
;
3164 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
3165 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
3166 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3168 isl_space_free(space
);
3171 isl_id_free(array_id
);
3175 space
= isl_multi_pw_aff_get_domain_space(index
);
3176 isl_multi_pw_aff_free(index
);
3178 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
3180 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
3181 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
3184 isl_id_free(array_id
);
3186 ls
= isl_local_space_from_space(space
);
3187 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
3188 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
3193 /* Check if the given access relation accesses a (0D) array that corresponds
3194 * to one of the parameters in "dim". If so, replace the array access
3195 * by an access to the set of integers with as index (and value)
3198 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
3199 __isl_take isl_space
*dim
)
3201 isl_id
*array_id
= NULL
;
3204 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
3205 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
3206 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
3208 isl_space_free(dim
);
3211 isl_id_free(array_id
);
3215 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
3217 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
3218 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
3221 isl_id_free(array_id
);
3223 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
3224 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
3229 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3230 * in "dim" by a value equal to the corresponding parameter.
3232 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
3233 __isl_take isl_space
*dim
)
3240 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3242 expr_detect_parameter_accesses(expr
->args
[i
],
3243 isl_space_copy(dim
));
3248 if (expr
->type
== pet_expr_access
) {
3249 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
3250 isl_space_copy(dim
));
3251 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
3252 isl_space_copy(dim
));
3253 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3257 isl_space_free(dim
);
3260 isl_space_free(dim
);
3261 return pet_expr_free(expr
);
3264 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3265 * in "dim" by a value equal to the corresponding parameter.
3267 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
3268 __isl_take isl_space
*dim
)
3273 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
3274 isl_space_copy(dim
));
3276 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
3279 isl_space_free(dim
);
3282 isl_space_free(dim
);
3283 return pet_stmt_free(stmt
);
3286 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3287 * in "dim" by a value equal to the corresponding parameter.
3289 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
3290 __isl_take isl_space
*dim
)
3297 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3298 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
3299 isl_space_copy(dim
));
3300 if (!scop
->stmts
[i
])
3304 isl_space_free(dim
);
3307 isl_space_free(dim
);
3308 return pet_scop_free(scop
);
3311 /* Replace all accesses to (0D) arrays that correspond to any of
3312 * the parameters used in "scop" by a value equal
3313 * to the corresponding parameter.
3315 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
3322 dim
= isl_set_get_space(scop
->context
);
3323 dim
= scop_collect_params(scop
, dim
);
3325 scop
= scop_detect_parameter_accesses(scop
, dim
);
3330 /* Return the relation mapping domain iterations to all possibly
3331 * accessed data elements.
3332 * In particular, take the access relation and project out the values
3333 * of the arguments, if any.
3335 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
3343 if (expr
->type
!= pet_expr_access
)
3346 access
= isl_map_copy(expr
->acc
.access
);
3347 if (expr
->n_arg
== 0)
3350 space
= isl_space_domain(isl_map_get_space(access
));
3351 map
= isl_map_universe(isl_space_unwrap(space
));
3352 map
= isl_map_domain_map(map
);
3353 access
= isl_map_apply_domain(access
, map
);
3358 /* Add all read access relations (if "read" is set) and/or all write
3359 * access relations (if "write" is set) to "accesses" and return the result.
3361 * If "must" is set, then we only add the accesses that are definitely
3362 * performed. Otherwise, we add all potential accesses.
3363 * In particular, if the access has any arguments, then if "must" is
3364 * set we currently skip the access completely. If "must" is not set,
3365 * we project out the values of the access arguments.
3367 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
3368 int read
, int write
, int must
, __isl_take isl_union_map
*accesses
)
3375 return isl_union_map_free(accesses
);
3377 for (i
= 0; i
< expr
->n_arg
; ++i
)
3378 accesses
= expr_collect_accesses(expr
->args
[i
],
3379 read
, write
, must
, accesses
);
3381 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
3382 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
3383 (!must
|| expr
->n_arg
== 0)) {
3386 access
= pet_expr_access_get_may_access(expr
);
3387 accesses
= isl_union_map_add_map(accesses
, access
);
3393 /* Collect and return all read access relations (if "read" is set)
3394 * and/or all write access relations (if "write" is set) in "stmt".
3396 * If "must" is set, then we only add the accesses that are definitely
3397 * performed. Otherwise, we add all potential accesses.
3398 * In particular, if the statement has any arguments, then if "must" is
3399 * set we currently skip the statement completely. If "must" is not set,
3400 * we project out the values of the statement arguments.
3402 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
3403 int read
, int write
, int must
, __isl_take isl_space
*dim
)
3405 isl_union_map
*accesses
;
3411 accesses
= isl_union_map_empty(dim
);
3413 if (must
&& stmt
->n_arg
> 0)
3416 domain
= isl_set_copy(stmt
->domain
);
3417 if (isl_set_is_wrapping(domain
))
3418 domain
= isl_map_domain(isl_set_unwrap(domain
));
3420 accesses
= expr_collect_accesses(stmt
->body
,
3421 read
, write
, must
, accesses
);
3422 accesses
= isl_union_map_intersect_domain(accesses
,
3423 isl_union_set_from_set(domain
));
3428 /* Collect and return all read access relations (if "read" is set)
3429 * and/or all write access relations (if "write" is set) in "scop".
3430 * If "must" is set, then we only add the accesses that are definitely
3431 * performed. Otherwise, we add all potential accesses.
3433 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
3434 int read
, int write
, int must
)
3437 isl_union_map
*accesses
;
3438 isl_union_set
*arrays
;
3443 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3445 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3446 isl_union_map
*accesses_i
;
3447 isl_space
*dim
= isl_set_get_space(scop
->context
);
3448 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
3449 read
, write
, must
, dim
);
3450 accesses
= isl_union_map_union(accesses
, accesses_i
);
3453 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
3454 for (i
= 0; i
< scop
->n_array
; ++i
) {
3455 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
3456 arrays
= isl_union_set_add_set(arrays
, extent
);
3458 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
3463 /* Collect all potential read access relations.
3465 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
3467 return scop_collect_accesses(scop
, 1, 0, 0);
3470 /* Collect all potential write access relations.
3472 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
3474 return scop_collect_accesses(scop
, 0, 1, 0);
3477 /* Collect all definite write access relations.
3479 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
3481 return scop_collect_accesses(scop
, 0, 1, 1);
3484 /* Collect and return the union of iteration domains in "scop".
3486 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
3490 isl_union_set
*domain
;
3495 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
3497 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3498 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
3499 domain
= isl_union_set_add_set(domain
, domain_i
);
3505 /* Collect and return the schedules of the statements in "scop".
3506 * The range is normalized to the maximal number of scheduling
3509 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
3512 isl_map
*schedule_i
;
3513 isl_union_map
*schedule
;
3514 int depth
, max_depth
= 0;
3519 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
3521 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3522 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
3523 if (depth
> max_depth
)
3527 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3528 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
3529 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
3530 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
3532 for (j
= depth
; j
< max_depth
; ++j
)
3533 schedule_i
= isl_map_fix_si(schedule_i
,
3535 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3541 /* Does expression "expr" write to "id"?
3543 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3548 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3549 int writes
= expr_writes(expr
->args
[i
], id
);
3550 if (writes
< 0 || writes
)
3554 if (expr
->type
!= pet_expr_access
)
3556 if (!expr
->acc
.write
)
3558 if (pet_expr_is_affine(expr
))
3561 write_id
= pet_expr_access_get_id(expr
);
3562 isl_id_free(write_id
);
3567 return write_id
== id
;
3570 /* Does statement "stmt" write to "id"?
3572 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3574 return expr_writes(stmt
->body
, id
);
3577 /* Is there any write access in "scop" that accesses "id"?
3579 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3586 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3587 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3588 if (writes
< 0 || writes
)
3595 /* Add a reference identifier to access expression "expr".
3596 * "user" points to an integer that contains the sequence number
3597 * of the next reference.
3599 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3608 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3609 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3610 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3611 if (!expr
->acc
.ref_id
)
3612 return pet_expr_free(expr
);
3617 /* Add a reference identifier to all access expressions in "stmt".
3618 * "n_ref" points to an integer that contains the sequence number
3619 * of the next reference.
3621 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3628 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3629 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3630 &access_add_ref_id
, n_ref
);
3632 return pet_stmt_free(stmt
);
3635 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3637 return pet_stmt_free(stmt
);
3642 /* Add a reference identifier to all access expressions in "scop".
3644 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3653 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3654 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3655 if (!scop
->stmts
[i
])
3656 return pet_scop_free(scop
);
3662 /* Reset the user pointer on all parameter ids in "array".
3664 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3669 array
->context
= isl_set_reset_user(array
->context
);
3670 array
->extent
= isl_set_reset_user(array
->extent
);
3671 if (!array
->context
|| !array
->extent
)
3672 return pet_array_free(array
);
3677 /* Reset the user pointer on all parameter and tuple ids in
3678 * the access relation and the index expressions
3679 * of the access expression "expr".
3681 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3683 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
3684 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
3685 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3686 return pet_expr_free(expr
);
3691 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3693 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3702 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
3703 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
3704 if (!stmt
->domain
|| !stmt
->schedule
)
3705 return pet_stmt_free(stmt
);
3707 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3708 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3709 &access_anonymize
, NULL
);
3711 return pet_stmt_free(stmt
);
3714 stmt
->body
= pet_expr_map_access(stmt
->body
,
3715 &access_anonymize
, NULL
);
3717 return pet_stmt_free(stmt
);
3722 /* Reset the user pointer on the tuple ids and all parameter ids
3725 static struct pet_implication
*implication_anonymize(
3726 struct pet_implication
*implication
)
3731 implication
->extension
= isl_map_reset_user(implication
->extension
);
3732 if (!implication
->extension
)
3733 return pet_implication_free(implication
);
3738 /* Reset the user pointer on all parameter and tuple ids in "scop".
3740 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3747 scop
->context
= isl_set_reset_user(scop
->context
);
3748 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
3749 if (!scop
->context
|| !scop
->context_value
)
3750 return pet_scop_free(scop
);
3752 for (i
= 0; i
< scop
->n_array
; ++i
) {
3753 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3754 if (!scop
->arrays
[i
])
3755 return pet_scop_free(scop
);
3758 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3759 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3760 if (!scop
->stmts
[i
])
3761 return pet_scop_free(scop
);
3764 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3765 scop
->implications
[i
] =
3766 implication_anonymize(scop
->implications
[i
]);
3767 if (!scop
->implications
[i
])
3768 return pet_scop_free(scop
);
3774 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3775 * then intersect the range of "map" with the valid set of values.
3777 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
3778 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
3783 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3785 id
= pet_expr_access_get_id(arg
);
3786 space
= isl_space_alloc(ctx
, 0, 0, 1);
3787 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
3788 vb
= isl_union_map_extract_map(value_bounds
, space
);
3789 if (!isl_map_plain_is_empty(vb
))
3790 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
3797 /* Given a set "domain", return a wrapped relation with the given set
3798 * as domain and a range of dimension "n_arg", where each coordinate
3799 * is either unbounded or, if the corresponding element of args is of
3800 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3802 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
3803 unsigned n_arg
, struct pet_expr
**args
,
3804 __isl_keep isl_union_map
*value_bounds
)
3810 map
= isl_map_from_domain(domain
);
3811 space
= isl_map_get_space(map
);
3812 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
3814 for (i
= 0; i
< n_arg
; ++i
) {
3816 struct pet_expr
*arg
= args
[i
];
3818 map_i
= isl_map_universe(isl_space_copy(space
));
3819 if (arg
->type
== pet_expr_access
)
3820 map_i
= access_apply_value_bounds(map_i
, arg
,
3822 map
= isl_map_flat_range_product(map
, map_i
);
3824 isl_space_free(space
);
3826 return isl_map_wrap(map
);
3829 /* Data used in access_gist() callback.
3831 struct pet_access_gist_data
{
3833 isl_union_map
*value_bounds
;
3836 /* Given an expression "expr" of type pet_expr_access, compute
3837 * the gist of the associated access relation and index expression
3838 * with respect to data->domain and the bounds on the values of the arguments
3839 * of the expression.
3841 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3843 struct pet_access_gist_data
*data
= user
;
3846 domain
= isl_set_copy(data
->domain
);
3847 if (expr
->n_arg
> 0)
3848 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3849 data
->value_bounds
);
3851 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
3852 isl_set_copy(domain
));
3853 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
3854 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3855 return pet_expr_free(expr
);
3860 /* Compute the gist of the iteration domain and all access relations
3861 * of "stmt" based on the constraints on the parameters specified by "context"
3862 * and the constraints on the values of nested accesses specified
3863 * by "value_bounds".
3865 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3866 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3871 struct pet_access_gist_data data
;
3876 data
.domain
= isl_set_copy(stmt
->domain
);
3877 data
.value_bounds
= value_bounds
;
3878 if (stmt
->n_arg
> 0)
3879 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3881 data
.domain
= isl_set_intersect_params(data
.domain
,
3882 isl_set_copy(context
));
3884 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3885 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3886 &access_gist
, &data
);
3891 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3895 isl_set_free(data
.domain
);
3897 space
= isl_set_get_space(stmt
->domain
);
3898 if (isl_space_is_wrapping(space
))
3899 space
= isl_space_domain(isl_space_unwrap(space
));
3900 domain
= isl_set_universe(space
);
3901 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3902 if (stmt
->n_arg
> 0)
3903 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3905 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3907 return pet_stmt_free(stmt
);
3911 isl_set_free(data
.domain
);
3912 return pet_stmt_free(stmt
);
3915 /* Compute the gist of the extent of the array
3916 * based on the constraints on the parameters specified by "context".
3918 static struct pet_array
*array_gist(struct pet_array
*array
,
3919 __isl_keep isl_set
*context
)
3924 array
->extent
= isl_set_gist_params(array
->extent
,
3925 isl_set_copy(context
));
3927 return pet_array_free(array
);
3932 /* Compute the gist of all sets and relations in "scop"
3933 * based on the constraints on the parameters specified by "scop->context"
3934 * and the constraints on the values of nested accesses specified
3935 * by "value_bounds".
3937 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3938 __isl_keep isl_union_map
*value_bounds
)
3945 scop
->context
= isl_set_coalesce(scop
->context
);
3947 return pet_scop_free(scop
);
3949 for (i
= 0; i
< scop
->n_array
; ++i
) {
3950 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3951 if (!scop
->arrays
[i
])
3952 return pet_scop_free(scop
);
3955 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3956 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3958 if (!scop
->stmts
[i
])
3959 return pet_scop_free(scop
);
3965 /* Intersect the context of "scop" with "context".
3966 * To ensure that we don't introduce any unnamed parameters in
3967 * the context of "scop", we first remove the unnamed parameters
3970 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3971 __isl_take isl_set
*context
)
3976 context
= set_project_out_unnamed_params(context
);
3977 scop
->context
= isl_set_intersect(scop
->context
, context
);
3979 return pet_scop_free(scop
);
3983 isl_set_free(context
);
3984 return pet_scop_free(scop
);
3987 /* Drop the current context of "scop". That is, replace the context
3988 * by a universal set.
3990 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3997 space
= isl_set_get_space(scop
->context
);
3998 isl_set_free(scop
->context
);
3999 scop
->context
= isl_set_universe(space
);
4001 return pet_scop_free(scop
);
4006 /* Append "array" to the arrays of "scop".
4008 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
4009 struct pet_array
*array
)
4012 struct pet_array
**arrays
;
4014 if (!array
|| !scop
)
4017 ctx
= isl_set_get_ctx(scop
->context
);
4018 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
4022 scop
->arrays
= arrays
;
4023 scop
->arrays
[scop
->n_array
] = array
;
4028 pet_array_free(array
);
4029 return pet_scop_free(scop
);
4032 /* Create and return an implication on filter values equal to "satisfied"
4033 * with extension "map".
4035 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
4039 struct pet_implication
*implication
;
4043 ctx
= isl_map_get_ctx(map
);
4044 implication
= isl_alloc_type(ctx
, struct pet_implication
);
4048 implication
->extension
= map
;
4049 implication
->satisfied
= satisfied
;
4057 /* Add an implication on filter values equal to "satisfied"
4058 * with extension "map" to "scop".
4060 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
4061 __isl_take isl_map
*map
, int satisfied
)
4064 struct pet_implication
*implication
;
4065 struct pet_implication
**implications
;
4067 implication
= new_implication(map
, satisfied
);
4068 if (!scop
|| !implication
)
4071 ctx
= isl_set_get_ctx(scop
->context
);
4072 implications
= isl_realloc_array(ctx
, scop
->implications
,
4073 struct pet_implication
*,
4074 scop
->n_implication
+ 1);
4077 scop
->implications
= implications
;
4078 scop
->implications
[scop
->n_implication
] = implication
;
4079 scop
->n_implication
++;
4083 pet_implication_free(implication
);
4084 return pet_scop_free(scop
);
4087 /* Given an access expression, check if it is data dependent.
4088 * If so, set *found and abort the search.
4090 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
4102 /* Does "scop" contain any data dependent accesses?
4104 * Check the body of each statement for such accesses.
4106 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
4114 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
4115 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
4116 &is_data_dependent
, &found
);
4117 if (r
< 0 && !found
)
4126 /* Does "scop" contain and data dependent conditions?
4128 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
4135 for (i
= 0; i
< scop
->n_stmt
; ++i
)
4136 if (scop
->stmts
[i
]->n_arg
> 0)
4142 /* Keep track of the "input" file inside the (extended) "scop".
4144 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
4146 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4156 /* Print the original code corresponding to "scop" to printer "p".
4158 * pet_scop_print_original can only be called from
4159 * a pet_transform_C_source callback. This means that the input
4160 * file is stored in the extended scop and that the printer prints
4163 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
4164 __isl_take isl_printer
*p
)
4166 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
4170 return isl_printer_free(p
);
4173 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
4174 "no input file stored in scop",
4175 return isl_printer_free(p
));
4177 output
= isl_printer_get_file(p
);
4179 return isl_printer_free(p
);
4181 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
4182 return isl_printer_free(p
);