2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
41 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
43 static char *type_str
[] = {
44 [pet_expr_access
] = "access",
45 [pet_expr_call
] = "call",
46 [pet_expr_cast
] = "cast",
47 [pet_expr_double
] = "double",
48 [pet_expr_unary
] = "unary",
49 [pet_expr_binary
] = "binary",
50 [pet_expr_ternary
] = "ternary"
53 static char *op_str
[] = {
54 [pet_op_add_assign
] = "+=",
55 [pet_op_sub_assign
] = "-=",
56 [pet_op_mul_assign
] = "*=",
57 [pet_op_div_assign
] = "/=",
58 [pet_op_assign
] = "=",
69 [pet_op_post_inc
] = "++",
70 [pet_op_post_dec
] = "--",
71 [pet_op_pre_inc
] = "++",
72 [pet_op_pre_dec
] = "--",
73 [pet_op_address_of
] = "&",
74 [pet_op_kill
] = "kill"
77 /* pet_scop with extra information that is only used during parsing.
79 * In particular, we keep track of conditions under which we want
80 * to skip the rest of the current loop iteration (skip[pet_skip_now])
81 * and of conditions under which we want to skip subsequent
82 * loop iterations (skip[pet_skip_later]).
84 * The conditions are represented either by a variable, which
85 * is assumed to attain values zero and one, or by a boolean affine
86 * expression. The condition holds if the variable has value one
87 * or if the affine expression has value one (typically for only
88 * part of the parameter space).
90 * A missing condition (skip[type] == NULL) means that we don't want
99 const char *pet_op_str(enum pet_op_type op
)
104 int pet_op_is_inc_dec(enum pet_op_type op
)
106 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
107 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
110 const char *pet_type_str(enum pet_expr_type type
)
112 return type_str
[type
];
115 enum pet_op_type
pet_str_op(const char *str
)
119 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
120 if (!strcmp(op_str
[i
], str
))
126 enum pet_expr_type
pet_str_type(const char *str
)
130 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
131 if (!strcmp(type_str
[i
], str
))
137 /* Construct a pet_expr from an access relation.
138 * By default, it is considered to be a read access.
140 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
142 isl_ctx
*ctx
= isl_map_get_ctx(access
);
143 struct pet_expr
*expr
;
147 expr
= isl_calloc_type(ctx
, struct pet_expr
);
151 expr
->type
= pet_expr_access
;
152 expr
->acc
.access
= access
;
158 isl_map_free(access
);
162 /* Construct an access pet_expr from an index expression.
163 * By default, the access is considered to be a read access.
165 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
169 access
= isl_map_from_multi_pw_aff(index
);
170 return pet_expr_from_access(access
);
173 /* Construct a pet_expr that kills the elements specified by "access".
175 struct pet_expr
*pet_expr_kill_from_access(__isl_take isl_map
*access
)
178 struct pet_expr
*expr
;
180 ctx
= isl_map_get_ctx(access
);
181 expr
= pet_expr_from_access(access
);
185 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
188 /* Construct a unary pet_expr that performs "op" on "arg".
190 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
191 struct pet_expr
*arg
)
193 struct pet_expr
*expr
;
197 expr
= isl_alloc_type(ctx
, struct pet_expr
);
201 expr
->type
= pet_expr_unary
;
204 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
207 expr
->args
[pet_un_arg
] = arg
;
215 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
217 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
218 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
220 struct pet_expr
*expr
;
224 expr
= isl_alloc_type(ctx
, struct pet_expr
);
228 expr
->type
= pet_expr_binary
;
231 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
234 expr
->args
[pet_bin_lhs
] = lhs
;
235 expr
->args
[pet_bin_rhs
] = rhs
;
244 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
246 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
247 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
249 struct pet_expr
*expr
;
251 if (!cond
|| !lhs
|| !rhs
)
253 expr
= isl_alloc_type(ctx
, struct pet_expr
);
257 expr
->type
= pet_expr_ternary
;
259 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
262 expr
->args
[pet_ter_cond
] = cond
;
263 expr
->args
[pet_ter_true
] = lhs
;
264 expr
->args
[pet_ter_false
] = rhs
;
274 /* Construct a call pet_expr that calls function "name" with "n_arg"
275 * arguments. The caller is responsible for filling in the arguments.
277 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
280 struct pet_expr
*expr
;
282 expr
= isl_alloc_type(ctx
, struct pet_expr
);
286 expr
->type
= pet_expr_call
;
288 expr
->name
= strdup(name
);
289 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
290 if (!expr
->name
|| !expr
->args
)
291 return pet_expr_free(expr
);
296 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
298 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
299 struct pet_expr
*arg
)
301 struct pet_expr
*expr
;
306 expr
= isl_alloc_type(ctx
, struct pet_expr
);
310 expr
->type
= pet_expr_cast
;
312 expr
->type_name
= strdup(type_name
);
313 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
314 if (!expr
->type_name
|| !expr
->args
)
326 /* Construct a pet_expr that represents the double "d".
328 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
330 struct pet_expr
*expr
;
332 expr
= isl_calloc_type(ctx
, struct pet_expr
);
336 expr
->type
= pet_expr_double
;
338 expr
->d
.s
= strdup(s
);
340 return pet_expr_free(expr
);
345 void *pet_expr_free(struct pet_expr
*expr
)
352 for (i
= 0; i
< expr
->n_arg
; ++i
)
353 pet_expr_free(expr
->args
[i
]);
356 switch (expr
->type
) {
357 case pet_expr_access
:
358 isl_id_free(expr
->acc
.ref_id
);
359 isl_map_free(expr
->acc
.access
);
365 free(expr
->type_name
);
367 case pet_expr_double
:
371 case pet_expr_binary
:
372 case pet_expr_ternary
:
380 static void expr_dump(struct pet_expr
*expr
, int indent
)
387 fprintf(stderr
, "%*s", indent
, "");
389 switch (expr
->type
) {
390 case pet_expr_double
:
391 fprintf(stderr
, "%s\n", expr
->d
.s
);
393 case pet_expr_access
:
394 isl_id_dump(expr
->acc
.ref_id
);
395 fprintf(stderr
, "%*s", indent
, "");
396 isl_map_dump(expr
->acc
.access
);
397 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
399 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
400 "", expr
->acc
.write
);
401 for (i
= 0; i
< expr
->n_arg
; ++i
)
402 expr_dump(expr
->args
[i
], indent
+ 2);
405 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
406 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
408 case pet_expr_binary
:
409 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
410 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
411 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
413 case pet_expr_ternary
:
414 fprintf(stderr
, "?:\n");
415 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
416 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
417 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
420 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
421 for (i
= 0; i
< expr
->n_arg
; ++i
)
422 expr_dump(expr
->args
[i
], indent
+ 2);
425 fprintf(stderr
, "(%s)\n", expr
->type_name
);
426 for (i
= 0; i
< expr
->n_arg
; ++i
)
427 expr_dump(expr
->args
[i
], indent
+ 2);
432 void pet_expr_dump(struct pet_expr
*expr
)
437 /* Does "expr" represent an access to an unnamed space, i.e.,
438 * does it represent an affine expression?
440 int pet_expr_is_affine(struct pet_expr
*expr
)
446 if (expr
->type
!= pet_expr_access
)
449 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
456 /* Return the identifier of the array accessed by "expr".
458 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
462 if (expr
->type
!= pet_expr_access
)
464 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
467 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
469 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
473 if (expr
->type
!= pet_expr_access
)
476 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
479 /* Return 1 if the two pet_exprs are equivalent.
481 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
485 if (!expr1
|| !expr2
)
488 if (expr1
->type
!= expr2
->type
)
490 if (expr1
->n_arg
!= expr2
->n_arg
)
492 for (i
= 0; i
< expr1
->n_arg
; ++i
)
493 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
495 switch (expr1
->type
) {
496 case pet_expr_double
:
497 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
499 if (expr1
->d
.val
!= expr2
->d
.val
)
502 case pet_expr_access
:
503 if (expr1
->acc
.read
!= expr2
->acc
.read
)
505 if (expr1
->acc
.write
!= expr2
->acc
.write
)
507 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
509 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
511 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
515 case pet_expr_binary
:
516 case pet_expr_ternary
:
517 if (expr1
->op
!= expr2
->op
)
521 if (strcmp(expr1
->name
, expr2
->name
))
525 if (strcmp(expr1
->type_name
, expr2
->type_name
))
533 /* Add extra conditions on the parameters to all access relations in "expr".
535 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
536 __isl_take isl_set
*cond
)
543 for (i
= 0; i
< expr
->n_arg
; ++i
) {
544 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
550 if (expr
->type
== pet_expr_access
) {
551 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
553 if (!expr
->acc
.access
)
561 return pet_expr_free(expr
);
564 /* Modify all expressions of type pet_expr_access in "expr"
565 * by calling "fn" on them.
567 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
568 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
576 for (i
= 0; i
< expr
->n_arg
; ++i
) {
577 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
579 return pet_expr_free(expr
);
582 if (expr
->type
== pet_expr_access
)
583 expr
= fn(expr
, user
);
588 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
590 * Return -1 on error (where fn return a negative value is treated as an error).
591 * Otherwise return 0.
593 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
594 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
601 for (i
= 0; i
< expr
->n_arg
; ++i
)
602 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
605 if (expr
->type
== pet_expr_access
)
606 return fn(expr
, user
);
611 /* Modify the access relation of the given access expression
612 * based on the given iteration space transformation.
613 * If the access has any arguments then the domain of the access relation
614 * is a wrapped mapping from the iteration space to the space of
615 * argument values. We only need to change the domain of this wrapped
616 * mapping, so we extend the input transformation with an identity mapping
617 * on the space of argument values.
619 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
621 isl_map
*update
= user
;
624 update
= isl_map_copy(update
);
626 dim
= isl_map_get_space(expr
->acc
.access
);
627 dim
= isl_space_domain(dim
);
628 if (!isl_space_is_wrapping(dim
))
632 dim
= isl_space_unwrap(dim
);
633 dim
= isl_space_range(dim
);
634 dim
= isl_space_map_from_set(dim
);
635 id
= isl_map_identity(dim
);
636 update
= isl_map_product(update
, id
);
639 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, update
);
640 if (!expr
->acc
.access
)
641 return pet_expr_free(expr
);
646 /* Modify all access relations in "expr" based on the given iteration space
649 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
650 __isl_take isl_map
*update
)
652 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
653 isl_map_free(update
);
657 /* Construct a pet_stmt with given line number and statement
658 * number from a pet_expr.
659 * The initial iteration domain is the zero-dimensional universe.
660 * The name of the domain is given by "label" if it is non-NULL.
661 * Otherwise, the name is constructed as S_<id>.
662 * The domains of all access relations are modified to refer
663 * to the statement iteration domain.
665 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
666 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
668 struct pet_stmt
*stmt
;
678 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
682 dim
= isl_space_set_alloc(ctx
, 0, 0);
684 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
686 snprintf(name
, sizeof(name
), "S_%d", id
);
687 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
689 dom
= isl_set_universe(isl_space_copy(dim
));
690 sched
= isl_map_from_domain(isl_set_copy(dom
));
692 dim
= isl_space_from_range(dim
);
693 add_name
= isl_map_universe(dim
);
694 expr
= expr_update_domain(expr
, add_name
);
698 stmt
->schedule
= sched
;
701 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
702 return pet_stmt_free(stmt
);
707 return pet_expr_free(expr
);
710 void *pet_stmt_free(struct pet_stmt
*stmt
)
717 isl_set_free(stmt
->domain
);
718 isl_map_free(stmt
->schedule
);
719 pet_expr_free(stmt
->body
);
721 for (i
= 0; i
< stmt
->n_arg
; ++i
)
722 pet_expr_free(stmt
->args
[i
]);
729 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
736 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
737 fprintf(stderr
, "%*s", indent
, "");
738 isl_set_dump(stmt
->domain
);
739 fprintf(stderr
, "%*s", indent
, "");
740 isl_map_dump(stmt
->schedule
);
741 expr_dump(stmt
->body
, indent
);
742 for (i
= 0; i
< stmt
->n_arg
; ++i
)
743 expr_dump(stmt
->args
[i
], indent
+ 2);
746 void pet_stmt_dump(struct pet_stmt
*stmt
)
751 struct pet_array
*pet_array_free(struct pet_array
*array
)
756 isl_set_free(array
->context
);
757 isl_set_free(array
->extent
);
758 isl_set_free(array
->value_bounds
);
759 free(array
->element_type
);
765 void pet_array_dump(struct pet_array
*array
)
770 isl_set_dump(array
->context
);
771 isl_set_dump(array
->extent
);
772 isl_set_dump(array
->value_bounds
);
773 fprintf(stderr
, "%s %s\n", array
->element_type
,
774 array
->live_out
? "live-out" : "");
777 /* Alloc a pet_scop structure, with extra room for information that
778 * is only used during parsing.
780 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
782 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
785 /* Construct a pet_scop with room for n statements.
787 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
790 struct pet_scop
*scop
;
792 scop
= pet_scop_alloc(ctx
);
796 space
= isl_space_params_alloc(ctx
, 0);
797 scop
->context
= isl_set_universe(isl_space_copy(space
));
798 scop
->context_value
= isl_set_universe(space
);
799 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
800 if (!scop
->context
|| !scop
->stmts
)
801 return pet_scop_free(scop
);
808 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
810 return scop_alloc(ctx
, 0);
813 /* Update "context" with respect to the valid parameter values for "access".
815 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
816 __isl_take isl_set
*context
)
818 context
= isl_set_intersect(context
,
819 isl_map_params(isl_map_copy(access
)));
823 /* Update "context" with respect to the valid parameter values for "expr".
825 * If "expr" represents a ternary operator, then a parameter value
826 * needs to be valid for the condition and for at least one of the
827 * remaining two arguments.
828 * If the condition is an affine expression, then we can be a bit more specific.
829 * The parameter then has to be valid for the second argument for
830 * non-zero accesses and valid for the third argument for zero accesses.
832 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
833 __isl_take isl_set
*context
)
837 if (expr
->type
== pet_expr_ternary
) {
839 isl_set
*context1
, *context2
;
841 is_aff
= pet_expr_is_affine(expr
->args
[0]);
845 context
= expr_extract_context(expr
->args
[0], context
);
846 context1
= expr_extract_context(expr
->args
[1],
847 isl_set_copy(context
));
848 context2
= expr_extract_context(expr
->args
[2], context
);
854 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
855 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
856 zero_set
= isl_map_params(access
);
857 context1
= isl_set_subtract(context1
,
858 isl_set_copy(zero_set
));
859 context2
= isl_set_intersect(context2
, zero_set
);
862 context
= isl_set_union(context1
, context2
);
863 context
= isl_set_coalesce(context
);
868 for (i
= 0; i
< expr
->n_arg
; ++i
)
869 context
= expr_extract_context(expr
->args
[i
], context
);
871 if (expr
->type
== pet_expr_access
)
872 context
= access_extract_context(expr
->acc
.access
, context
);
876 isl_set_free(context
);
880 /* Update "context" with respect to the valid parameter values for "stmt".
882 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
883 __isl_take isl_set
*context
)
887 for (i
= 0; i
< stmt
->n_arg
; ++i
)
888 context
= expr_extract_context(stmt
->args
[i
], context
);
890 context
= expr_extract_context(stmt
->body
, context
);
895 /* Construct a pet_scop that contains the given pet_stmt.
897 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
899 struct pet_scop
*scop
;
904 scop
= scop_alloc(ctx
, 1);
908 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
912 scop
->stmts
[0] = stmt
;
921 /* Does "set" represent an element of an unnamed space, i.e.,
922 * does it represent an affine expression?
924 static int set_is_affine(__isl_keep isl_set
*set
)
928 has_id
= isl_set_has_tuple_id(set
);
935 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
936 * ext may be equal to either ext1 or ext2.
938 * The two skips that need to be combined are assumed to be affine expressions.
940 * We need to skip in ext if we need to skip in either ext1 or ext2.
941 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
943 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
944 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
947 isl_set
*set
, *skip1
, *skip2
;
951 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
953 if (!ext1
->skip
[type
]) {
956 ext
->skip
[type
] = ext2
->skip
[type
];
957 ext2
->skip
[type
] = NULL
;
960 if (!ext2
->skip
[type
]) {
963 ext
->skip
[type
] = ext1
->skip
[type
];
964 ext1
->skip
[type
] = NULL
;
968 if (!set_is_affine(ext1
->skip
[type
]) ||
969 !set_is_affine(ext2
->skip
[type
]))
970 isl_die(isl_set_get_ctx(ext1
->skip
[type
]), isl_error_internal
,
971 "can only combine affine skips",
972 return pet_scop_free(&ext
->scop
));
974 skip1
= isl_set_copy(ext1
->skip
[type
]);
975 skip2
= isl_set_copy(ext2
->skip
[type
]);
976 set
= isl_set_intersect(
977 isl_set_fix_si(isl_set_copy(skip1
), isl_dim_set
, 0, 0),
978 isl_set_fix_si(isl_set_copy(skip2
), isl_dim_set
, 0, 0));
979 set
= isl_set_union(set
, isl_set_fix_si(skip1
, isl_dim_set
, 0, 1));
980 set
= isl_set_union(set
, isl_set_fix_si(skip2
, isl_dim_set
, 0, 1));
981 set
= isl_set_coalesce(set
);
982 isl_set_free(ext1
->skip
[type
]);
983 ext1
->skip
[type
] = NULL
;
984 isl_set_free(ext2
->skip
[type
]);
985 ext2
->skip
[type
] = NULL
;
986 ext
->skip
[type
] = set
;
987 if (!ext
->skip
[type
])
988 return pet_scop_free(&ext
->scop
);
993 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
994 * where type takes on the values pet_skip_now and pet_skip_later.
995 * scop may be equal to either scop1 or scop2.
997 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
998 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1000 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1001 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
1002 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
1004 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
1005 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
1009 /* Update scop->start and scop->end to include the region from "start"
1010 * to "end". In particular, if scop->end == 0, then "scop" does not
1011 * have any offset information yet and we simply take the information
1012 * from "start" and "end". Otherwise, we update the fields if the
1013 * region from "start" to "end" is not already included.
1015 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
1016 unsigned start
, unsigned end
)
1020 if (scop
->end
== 0) {
1021 scop
->start
= start
;
1024 if (start
< scop
->start
)
1025 scop
->start
= start
;
1026 if (end
> scop
->end
)
1033 /* Does "implication" appear in the list of implications of "scop"?
1035 static int is_known_implication(struct pet_scop
*scop
,
1036 struct pet_implication
*implication
)
1040 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1041 struct pet_implication
*pi
= scop
->implications
[i
];
1044 if (pi
->satisfied
!= implication
->satisfied
)
1046 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
1056 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1057 * in "scop", removing duplicates (i.e., implications in "scop2" that
1058 * already appear in "scop1").
1060 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
1061 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1068 if (scop2
->n_implication
== 0) {
1069 scop
->n_implication
= scop1
->n_implication
;
1070 scop
->implications
= scop1
->implications
;
1071 scop1
->n_implication
= 0;
1072 scop1
->implications
= NULL
;
1076 if (scop1
->n_implication
== 0) {
1077 scop
->n_implication
= scop2
->n_implication
;
1078 scop
->implications
= scop2
->implications
;
1079 scop2
->n_implication
= 0;
1080 scop2
->implications
= NULL
;
1084 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
1085 scop1
->n_implication
+ scop2
->n_implication
);
1086 if (!scop
->implications
)
1087 return pet_scop_free(scop
);
1089 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
1090 scop
->implications
[i
] = scop1
->implications
[i
];
1091 scop1
->implications
[i
] = NULL
;
1094 scop
->n_implication
= scop1
->n_implication
;
1095 j
= scop1
->n_implication
;
1096 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
1099 known
= is_known_implication(scop
, scop2
->implications
[i
]);
1101 return pet_scop_free(scop
);
1104 scop
->implications
[j
++] = scop2
->implications
[i
];
1105 scop2
->implications
[i
] = NULL
;
1107 scop
->n_implication
= j
;
1112 /* Combine the offset information of "scop1" and "scop2" into "scop".
1114 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1115 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1118 scop
= pet_scop_update_start_end(scop
,
1119 scop1
->start
, scop1
->end
);
1121 scop
= pet_scop_update_start_end(scop
,
1122 scop2
->start
, scop2
->end
);
1126 /* Construct a pet_scop that contains the offset information,
1127 * arrays, statements and skip information in "scop1" and "scop2".
1129 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1130 struct pet_scop
*scop2
)
1133 struct pet_scop
*scop
= NULL
;
1135 if (!scop1
|| !scop2
)
1138 if (scop1
->n_stmt
== 0) {
1139 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1140 pet_scop_free(scop1
);
1144 if (scop2
->n_stmt
== 0) {
1145 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1146 pet_scop_free(scop2
);
1150 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1154 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1155 scop1
->n_array
+ scop2
->n_array
);
1158 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1160 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1161 scop
->stmts
[i
] = scop1
->stmts
[i
];
1162 scop1
->stmts
[i
] = NULL
;
1165 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1166 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1167 scop2
->stmts
[i
] = NULL
;
1170 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1171 scop
->arrays
[i
] = scop1
->arrays
[i
];
1172 scop1
->arrays
[i
] = NULL
;
1175 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1176 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1177 scop2
->arrays
[i
] = NULL
;
1180 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
1181 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1182 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1183 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1184 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1186 pet_scop_free(scop1
);
1187 pet_scop_free(scop2
);
1190 pet_scop_free(scop1
);
1191 pet_scop_free(scop2
);
1192 pet_scop_free(scop
);
1196 /* Apply the skip condition "skip" to "scop".
1197 * That is, make sure "scop" is not executed when the condition holds.
1199 * If "skip" is an affine expression, we add the conditions under
1200 * which the expression is zero to the iteration domains.
1201 * Otherwise, we add a filter on the variable attaining the value zero.
1203 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1204 __isl_take isl_set
*skip
)
1212 is_aff
= set_is_affine(skip
);
1217 return pet_scop_filter(scop
, isl_map_from_range(skip
), 0);
1219 skip
= isl_set_fix_si(skip
, isl_dim_set
, 0, 0);
1220 scop
= pet_scop_restrict(scop
, isl_set_params(skip
));
1225 return pet_scop_free(scop
);
1228 /* Construct a pet_scop that contains the arrays, statements and
1229 * skip information in "scop1" and "scop2", where the two scops
1230 * are executed "in sequence". That is, breaks and continues
1231 * in scop1 have an effect on scop2.
1233 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1234 struct pet_scop
*scop2
)
1236 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1237 scop2
= restrict_skip(scop2
,
1238 pet_scop_get_skip(scop1
, pet_skip_now
));
1239 return pet_scop_add(ctx
, scop1
, scop2
);
1242 /* Construct a pet_scop that contains the arrays, statements and
1243 * skip information in "scop1" and "scop2", where the two scops
1244 * are executed "in parallel". That is, any break or continue
1245 * in scop1 has no effect on scop2.
1247 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1248 struct pet_scop
*scop2
)
1250 return pet_scop_add(ctx
, scop1
, scop2
);
1253 void *pet_implication_free(struct pet_implication
*implication
)
1260 isl_map_free(implication
->extension
);
1266 void *pet_scop_free(struct pet_scop
*scop
)
1269 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1273 isl_set_free(scop
->context
);
1274 isl_set_free(scop
->context_value
);
1276 for (i
= 0; i
< scop
->n_array
; ++i
)
1277 pet_array_free(scop
->arrays
[i
]);
1280 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1281 pet_stmt_free(scop
->stmts
[i
]);
1283 if (scop
->implications
)
1284 for (i
= 0; i
< scop
->n_implication
; ++i
)
1285 pet_implication_free(scop
->implications
[i
]);
1286 free(scop
->implications
);
1287 isl_set_free(ext
->skip
[pet_skip_now
]);
1288 isl_set_free(ext
->skip
[pet_skip_later
]);
1293 void pet_implication_dump(struct pet_implication
*implication
)
1298 fprintf(stderr
, "%d\n", implication
->satisfied
);
1299 isl_map_dump(implication
->extension
);
1302 void pet_scop_dump(struct pet_scop
*scop
)
1305 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1310 isl_set_dump(scop
->context
);
1311 isl_set_dump(scop
->context_value
);
1312 for (i
= 0; i
< scop
->n_array
; ++i
)
1313 pet_array_dump(scop
->arrays
[i
]);
1314 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1315 pet_stmt_dump(scop
->stmts
[i
]);
1316 for (i
= 0; i
< scop
->n_implication
; ++i
)
1317 pet_implication_dump(scop
->implications
[i
]);
1320 fprintf(stderr
, "skip\n");
1321 isl_set_dump(ext
->skip
[0]);
1322 isl_set_dump(ext
->skip
[1]);
1326 /* Return 1 if the two pet_arrays are equivalent.
1328 * We don't compare element_size as this may be target dependent.
1330 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1332 if (!array1
|| !array2
)
1335 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1337 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1339 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1341 if (array1
->value_bounds
&&
1342 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1344 if (strcmp(array1
->element_type
, array2
->element_type
))
1346 if (array1
->live_out
!= array2
->live_out
)
1348 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1350 if (array1
->declared
!= array2
->declared
)
1352 if (array1
->exposed
!= array2
->exposed
)
1358 /* Return 1 if the two pet_stmts are equivalent.
1360 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1364 if (!stmt1
|| !stmt2
)
1367 if (stmt1
->line
!= stmt2
->line
)
1369 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1371 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1373 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1375 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1377 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1378 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1385 /* Return 1 if the two pet_implications are equivalent.
1387 int pet_implication_is_equal(struct pet_implication
*implication1
,
1388 struct pet_implication
*implication2
)
1390 if (!implication1
|| !implication2
)
1393 if (implication1
->satisfied
!= implication2
->satisfied
)
1395 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1401 /* Return 1 if the two pet_scops are equivalent.
1403 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1407 if (!scop1
|| !scop2
)
1410 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1412 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1415 if (scop1
->n_array
!= scop2
->n_array
)
1417 for (i
= 0; i
< scop1
->n_array
; ++i
)
1418 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1421 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1423 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1424 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1427 if (scop1
->n_implication
!= scop2
->n_implication
)
1429 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1430 if (!pet_implication_is_equal(scop1
->implications
[i
],
1431 scop2
->implications
[i
]))
1437 /* Prefix the schedule of "stmt" with an extra dimension with constant
1440 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1445 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1446 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1447 if (!stmt
->schedule
)
1448 return pet_stmt_free(stmt
);
1453 /* Prefix the schedules of all statements in "scop" with an extra
1454 * dimension with constant value "pos".
1456 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1463 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1464 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1465 if (!scop
->stmts
[i
])
1466 return pet_scop_free(scop
);
1472 /* Given a set with a parameter at "param_pos" that refers to the
1473 * iterator, "move" the iterator to the first set dimension.
1474 * That is, essentially equate the parameter to the first set dimension
1475 * and then project it out.
1477 * The first set dimension may however refer to a virtual iterator,
1478 * while the parameter refers to the "real" iterator.
1479 * We therefore need to take into account the affine expression "iv_map", which
1480 * expresses the real iterator in terms of the virtual iterator.
1481 * In particular, we equate the set dimension to the input of the map
1482 * and the parameter to the output of the map and then project out
1483 * everything we don't need anymore.
1485 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1486 int param_pos
, __isl_take isl_aff
*iv_map
)
1488 isl_map
*map
, *map2
;
1489 map
= isl_map_from_domain(set
);
1490 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1491 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1492 map2
= isl_map_from_aff(iv_map
);
1493 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1494 map
= isl_map_apply_range(map
, map2
);
1495 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1496 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1497 return isl_map_domain(map
);
1500 /* Data used in embed_access.
1501 * extend adds an iterator to the iteration domain
1502 * iv_map expresses the real iterator in terms of the virtual iterator
1503 * var_id represents the induction variable of the corresponding loop
1505 struct pet_embed_access
{
1511 /* Given an access expression, embed the associated access relation
1512 * in an extra outer loop.
1514 * We first update the iteration domain to insert the extra dimension.
1516 * If the access refers to the induction variable, then it is
1517 * turned into an access to the set of integers with index (and value)
1518 * equal to the induction variable.
1520 * If the induction variable appears in the constraints (as a parameter),
1521 * then the parameter is equated to the newly introduced iteration
1522 * domain dimension and subsequently projected out.
1524 * Similarly, if the accessed array is a virtual array (with user
1525 * pointer equal to NULL), as created by create_test_access,
1526 * then it is extended along with the domain of the access.
1528 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1530 struct pet_embed_access
*data
= user
;
1532 isl_id
*array_id
= NULL
;
1535 expr
= update_domain(expr
, data
->extend
);
1539 access
= expr
->acc
.access
;
1541 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1542 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1543 if (array_id
== data
->var_id
||
1544 (array_id
&& !isl_id_get_user(array_id
))) {
1545 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1546 access
= isl_map_equate(access
,
1547 isl_dim_in
, 0, isl_dim_out
, 0);
1548 if (array_id
== data
->var_id
)
1549 access
= isl_map_apply_range(access
,
1550 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1552 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1553 isl_id_copy(array_id
));
1555 isl_id_free(array_id
);
1557 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1559 isl_set
*set
= isl_map_wrap(access
);
1560 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1561 access
= isl_set_unwrap(set
);
1563 expr
->acc
.access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1564 isl_id_copy(data
->var_id
));
1565 if (!expr
->acc
.access
)
1566 return pet_expr_free(expr
);
1571 /* Embed all access subexpressions of "expr" in an extra loop.
1572 * "extend" inserts an outer loop iterator in the iteration domains.
1573 * "iv_map" expresses the real iterator in terms of the virtual iterator
1574 * "var_id" represents the induction variable.
1576 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1577 __isl_take isl_map
*extend
, __isl_take isl_aff
*iv_map
,
1578 __isl_keep isl_id
*var_id
)
1580 struct pet_embed_access data
=
1581 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1583 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1584 isl_aff_free(iv_map
);
1585 isl_map_free(extend
);
1589 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1590 * "dom" and schedule "sched". "var_id" represents the induction variable
1591 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1592 * That is, it expresses the iterator that some of the parameters in "stmt"
1593 * may refer to in terms of the iterator used in "dom" and
1594 * the domain of "sched".
1596 * The iteration domain and schedule of the statement are updated
1597 * according to the iteration domain and schedule of the new loop.
1598 * If stmt->domain is a wrapped map, then the iteration domain
1599 * is the domain of this map, so we need to be careful to adjust
1602 * If the induction variable appears in the constraints (as a parameter)
1603 * of the current iteration domain or the schedule of the statement,
1604 * then the parameter is equated to the newly introduced iteration
1605 * domain dimension and subsequently projected out.
1607 * Finally, all access relations are updated based on the extra loop.
1609 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1610 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1611 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1622 if (isl_set_is_wrapping(stmt
->domain
)) {
1627 map
= isl_set_unwrap(stmt
->domain
);
1628 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1629 ran_dim
= isl_space_range(isl_map_get_space(map
));
1630 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1631 isl_set_universe(ran_dim
));
1632 map
= isl_map_flat_domain_product(ext
, map
);
1633 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1634 isl_id_copy(stmt_id
));
1635 dim
= isl_space_domain(isl_map_get_space(map
));
1636 stmt
->domain
= isl_map_wrap(map
);
1638 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1639 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1641 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1642 isl_id_copy(stmt_id
));
1643 dim
= isl_set_get_space(stmt
->domain
);
1646 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1648 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1649 isl_aff_copy(iv_map
));
1651 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1652 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1653 isl_dim_in
, stmt_id
);
1655 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1657 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1658 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1659 stmt
->schedule
= isl_set_unwrap(set
);
1662 dim
= isl_space_map_from_set(dim
);
1663 extend
= isl_map_identity(dim
);
1664 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1665 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1666 isl_map_get_tuple_id(extend
, isl_dim_out
));
1667 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1668 stmt
->args
[i
] = expr_embed(stmt
->args
[i
], isl_map_copy(extend
),
1669 isl_aff_copy(iv_map
), var_id
);
1670 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1673 isl_id_free(var_id
);
1675 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1677 return pet_stmt_free(stmt
);
1678 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1679 return pet_stmt_free(stmt
);
1683 isl_map_free(sched
);
1684 isl_aff_free(iv_map
);
1685 isl_id_free(var_id
);
1689 /* Embed the given pet_array in an extra outer loop with iteration domain
1691 * This embedding only has an effect on virtual arrays (those with
1692 * user pointer equal to NULL), which need to be extended along with
1693 * the iteration domain.
1695 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1696 __isl_take isl_set
*dom
)
1698 isl_id
*array_id
= NULL
;
1703 if (isl_set_has_tuple_id(array
->extent
))
1704 array_id
= isl_set_get_tuple_id(array
->extent
);
1706 if (array_id
&& !isl_id_get_user(array_id
)) {
1707 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1708 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1710 return pet_array_free(array
);
1713 isl_id_free(array_id
);
1722 /* Project out all unnamed parameters from "set" and return the result.
1724 static __isl_give isl_set
*set_project_out_unnamed_params(
1725 __isl_take isl_set
*set
)
1729 n
= isl_set_dim(set
, isl_dim_param
);
1730 for (i
= n
- 1; i
>= 0; --i
) {
1731 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1733 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1739 /* Update the context with respect to an embedding into a loop
1740 * with iteration domain "dom" and induction variable "id".
1741 * "iv_map" expresses the real iterator (parameter "id") in terms
1742 * of a possibly virtual iterator (used in "dom").
1744 * If the current context is independent of "id", we don't need
1746 * Otherwise, a parameter value is invalid for the embedding if
1747 * any of the corresponding iterator values is invalid.
1748 * That is, a parameter value is valid only if all the corresponding
1749 * iterator values are valid.
1750 * We therefore compute the set of parameters
1752 * forall i in dom : valid (i)
1756 * not exists i in dom : not valid(i)
1760 * not exists i in dom \ valid(i)
1762 * Before we subtract valid(i) from dom, we first need to substitute
1763 * the real iterator for the virtual iterator.
1765 * If there are any unnamed parameters in "dom", then we consider
1766 * a parameter value to be valid if it is valid for any value of those
1767 * unnamed parameters. They are therefore projected out at the end.
1769 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1770 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
1771 __isl_keep isl_id
*id
)
1776 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1780 context
= isl_set_from_params(context
);
1781 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1782 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1783 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1784 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
1785 context
= isl_set_preimage_multi_aff(context
, ma
);
1786 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1787 context
= isl_set_params(context
);
1788 context
= isl_set_complement(context
);
1789 context
= set_project_out_unnamed_params(context
);
1793 /* Update the implication with respect to an embedding into a loop
1794 * with iteration domain "dom".
1796 * Since embed_access extends virtual arrays along with the domain
1797 * of the access, we need to do the same with domain and range
1798 * of the implication. Since the original implication is only valid
1799 * within a given iteration of the loop, the extended implication
1800 * maps the extra array dimension corresponding to the extra loop
1803 static struct pet_implication
*pet_implication_embed(
1804 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1812 map
= isl_set_identity(dom
);
1813 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1814 map
= isl_map_flat_product(map
, implication
->extension
);
1815 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1816 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1817 implication
->extension
= map
;
1818 if (!implication
->extension
)
1819 return pet_implication_free(implication
);
1827 /* Embed all statements and arrays in "scop" in an extra outer loop
1828 * with iteration domain "dom" and schedule "sched".
1829 * "id" represents the induction variable of the loop.
1830 * "iv_map" maps a possibly virtual iterator to the real iterator.
1831 * That is, it expresses the iterator that some of the parameters in "scop"
1832 * may refer to in terms of the iterator used in "dom" and
1833 * the domain of "sched".
1835 * Any skip conditions within the loop have no effect outside of the loop.
1836 * The caller is responsible for making sure skip[pet_skip_later] has been
1837 * taken into account.
1839 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1840 __isl_take isl_map
*sched
, __isl_take isl_aff
*iv_map
,
1841 __isl_take isl_id
*id
)
1848 pet_scop_reset_skip(scop
, pet_skip_now
);
1849 pet_scop_reset_skip(scop
, pet_skip_later
);
1851 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1855 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1856 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1857 isl_set_copy(dom
), isl_map_copy(sched
),
1858 isl_aff_copy(iv_map
), isl_id_copy(id
));
1859 if (!scop
->stmts
[i
])
1863 for (i
= 0; i
< scop
->n_array
; ++i
) {
1864 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1866 if (!scop
->arrays
[i
])
1870 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1871 scop
->implications
[i
] =
1872 pet_implication_embed(scop
->implications
[i
],
1874 if (!scop
->implications
[i
])
1879 isl_map_free(sched
);
1880 isl_aff_free(iv_map
);
1885 isl_map_free(sched
);
1886 isl_aff_free(iv_map
);
1888 return pet_scop_free(scop
);
1891 /* Add extra conditions on the parameters to iteration domain of "stmt".
1893 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1894 __isl_take isl_set
*cond
)
1899 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1904 return pet_stmt_free(stmt
);
1907 /* Add extra conditions to scop->skip[type].
1909 * The new skip condition only holds if it held before
1910 * and the condition is true. It does not hold if it did not hold
1911 * before or the condition is false.
1913 * The skip condition is assumed to be an affine expression.
1915 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1916 enum pet_skip type
, __isl_keep isl_set
*cond
)
1918 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1924 if (!ext
->skip
[type
])
1927 if (!set_is_affine(ext
->skip
[type
]))
1928 isl_die(isl_set_get_ctx(ext
->skip
[type
]), isl_error_internal
,
1929 "can only resrict affine skips",
1930 return pet_scop_free(scop
));
1932 skip
= ext
->skip
[type
];
1933 skip
= isl_set_intersect_params(skip
, isl_set_copy(cond
));
1934 set
= isl_set_from_params(isl_set_copy(cond
));
1935 set
= isl_set_complement(set
);
1936 set
= isl_set_add_dims(set
, isl_dim_set
, 1);
1937 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 0);
1938 skip
= isl_set_union(skip
, set
);
1939 ext
->skip
[type
] = skip
;
1940 if (!ext
->skip
[type
])
1941 return pet_scop_free(scop
);
1946 /* Add extra conditions on the parameters to all iteration domains
1947 * and skip conditions.
1949 * A parameter value is valid for the result if it was valid
1950 * for the original scop and satisfies "cond" or if it does
1951 * not satisfy "cond" as in this case the scop is not executed
1952 * and the original constraints on the parameters are irrelevant.
1954 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1955 __isl_take isl_set
*cond
)
1959 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1960 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1965 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1966 scop
->context
= isl_set_union(scop
->context
,
1967 isl_set_complement(isl_set_copy(cond
)));
1968 scop
->context
= isl_set_coalesce(scop
->context
);
1969 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1973 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1974 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1975 isl_set_copy(cond
));
1976 if (!scop
->stmts
[i
])
1984 return pet_scop_free(scop
);
1987 /* Construct a map that inserts a filter value with name "id" and value
1988 * "satisfied" in the list of filter values embedded in the set space "space".
1990 * If "space" does not contain any filter values yet, we first create
1991 * a map that inserts 0 filter values, i.e.,
1993 * space -> [space -> []]
1995 * We can now assume that space is of the form [dom -> [filters]]
1996 * We construct an identity mapping on dom and a mapping on filters
1997 * that inserts the new filter
2000 * [filters] -> [satisfied, filters]
2002 * and then compute the cross product
2004 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
2006 static __isl_give isl_map
*insert_filter_map(__isl_take isl_space
*space
,
2007 __isl_take isl_id
*id
, int satisfied
)
2010 isl_map
*map
, *map_dom
, *map_ran
;
2013 if (isl_space_is_wrapping(space
)) {
2014 space2
= isl_space_map_from_set(isl_space_copy(space
));
2015 map
= isl_map_identity(space2
);
2016 space
= isl_space_unwrap(space
);
2018 space
= isl_space_from_domain(space
);
2019 map
= isl_map_universe(isl_space_copy(space
));
2020 map
= isl_map_reverse(isl_map_domain_map(map
));
2023 space2
= isl_space_domain(isl_space_copy(space
));
2024 map_dom
= isl_map_identity(isl_space_map_from_set(space2
));
2025 space
= isl_space_range(space
);
2026 map_ran
= isl_map_identity(isl_space_map_from_set(space
));
2027 map_ran
= isl_map_insert_dims(map_ran
, isl_dim_out
, 0, 1);
2028 map_ran
= isl_map_set_dim_id(map_ran
, isl_dim_out
, 0, id
);
2029 map_ran
= isl_map_fix_si(map_ran
, isl_dim_out
, 0, satisfied
);
2031 map
= isl_map_apply_range(map
, isl_map_product(map_dom
, map_ran
));
2036 /* Insert an argument expression corresponding to "test" in front
2037 * of the list of arguments described by *n_arg and *args.
2039 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
2040 __isl_keep isl_map
*test
)
2043 isl_ctx
*ctx
= isl_map_get_ctx(test
);
2049 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
2053 struct pet_expr
**ext
;
2054 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
2057 for (i
= 0; i
< *n_arg
; ++i
)
2058 ext
[1 + i
] = (*args
)[i
];
2063 (*args
)[0] = pet_expr_from_access(isl_map_copy(test
));
2070 /* Make the expression "expr" depend on the value of "test"
2071 * being equal to "satisfied".
2073 * If "test" is an affine expression, we simply add the conditions
2074 * on the expression have the value "satisfied" to all access relations.
2076 * Otherwise, we add a filter to "expr" (which is then assumed to be
2077 * an access expression) corresponding to "test" being equal to "satisfied".
2079 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
2080 __isl_take isl_map
*test
, int satisfied
)
2090 if (!isl_map_has_tuple_id(test
, isl_dim_out
)) {
2091 test
= isl_map_fix_si(test
, isl_dim_out
, 0, satisfied
);
2092 return pet_expr_restrict(expr
, isl_map_params(test
));
2095 ctx
= isl_map_get_ctx(test
);
2096 if (expr
->type
!= pet_expr_access
)
2097 isl_die(ctx
, isl_error_invalid
,
2098 "can only filter access expressions", goto error
);
2100 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
2101 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2102 map
= insert_filter_map(space
, id
, satisfied
);
2104 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, map
);
2105 if (!expr
->acc
.access
)
2108 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
2115 return pet_expr_free(expr
);
2118 /* Look through the applications in "scop" for any that can be
2119 * applied to the filter expressed by "map" and "satisified".
2120 * If there is any, then apply it to "map" and return the result.
2121 * Otherwise, return "map".
2122 * "id" is the identifier of the virtual array.
2124 * We only introduce at most one implication for any given virtual array,
2125 * so we can apply the implication and return as soon as we find one.
2127 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2128 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2132 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2133 struct pet_implication
*pi
= scop
->implications
[i
];
2136 if (pi
->satisfied
!= satisfied
)
2138 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2143 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2149 /* Is the filter expressed by "test" and "satisfied" implied
2150 * by filter "pos" on "domain", with filter "expr", taking into
2151 * account the implications of "scop"?
2153 * For filter on domain implying that expressed by "test" and "satisfied",
2154 * the filter needs to be an access to the same (virtual) array as "test" and
2155 * the filter value needs to be equal to "satisfied".
2156 * Moreover, the filter access relation, possibly extended by
2157 * the implications in "scop" needs to contain "test".
2159 static int implies_filter(struct pet_scop
*scop
,
2160 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
2161 __isl_keep isl_map
*test
, int satisfied
)
2163 isl_id
*test_id
, *arg_id
;
2170 if (expr
->type
!= pet_expr_access
)
2172 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2173 arg_id
= pet_expr_access_get_id(expr
);
2174 isl_id_free(arg_id
);
2175 isl_id_free(test_id
);
2176 if (test_id
!= arg_id
)
2178 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2179 is_int
= isl_val_is_int(val
);
2181 s
= isl_val_get_num_si(val
);
2190 implied
= isl_map_copy(expr
->acc
.access
);
2191 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2192 is_subset
= isl_map_is_subset(test
, implied
);
2193 isl_map_free(implied
);
2198 /* Is the filter expressed by "test" and "satisfied" implied
2199 * by any of the filters on the domain of "stmt", taking into
2200 * account the implications of "scop"?
2202 static int filter_implied(struct pet_scop
*scop
,
2203 struct pet_stmt
*stmt
, __isl_keep isl_map
*test
, int satisfied
)
2210 if (!scop
|| !stmt
|| !test
)
2212 if (scop
->n_implication
== 0)
2214 if (stmt
->n_arg
== 0)
2217 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2220 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2221 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2223 if (implied
< 0 || implied
)
2227 isl_map_free(domain
);
2231 /* Make the statement "stmt" depend on the value of "test"
2232 * being equal to "satisfied" by adjusting stmt->domain.
2234 * The domain of "test" corresponds to the (zero or more) outer dimensions
2235 * of the iteration domain.
2237 * We first extend "test" to apply to the entire iteration domain and
2238 * then check if the filter that we are about to add is implied
2239 * by any of the current filters, possibly taking into account
2240 * the implications in "scop". If so, we leave "stmt" untouched and return.
2242 * Otherwise, we insert an argument corresponding to a read to "test"
2243 * from the iteration domain of "stmt" in front of the list of arguments.
2244 * We also insert a corresponding output dimension in the wrapped
2245 * map contained in stmt->domain, with value set to "satisfied".
2247 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2248 struct pet_stmt
*stmt
, __isl_take isl_map
*test
, int satisfied
)
2254 isl_map
*map
, *add_dom
;
2262 space
= isl_set_get_space(stmt
->domain
);
2263 if (isl_space_is_wrapping(space
))
2264 space
= isl_space_domain(isl_space_unwrap(space
));
2265 dom
= isl_set_universe(space
);
2266 n_test_dom
= isl_map_dim(test
, isl_dim_in
);
2267 add_dom
= isl_map_from_range(dom
);
2268 add_dom
= isl_map_add_dims(add_dom
, isl_dim_in
, n_test_dom
);
2269 for (i
= 0; i
< n_test_dom
; ++i
)
2270 add_dom
= isl_map_equate(add_dom
, isl_dim_in
, i
,
2272 test
= isl_map_apply_domain(test
, add_dom
);
2274 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2282 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2283 map
= insert_filter_map(isl_set_get_space(stmt
->domain
), id
, satisfied
);
2284 stmt
->domain
= isl_set_apply(stmt
->domain
, map
);
2286 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2293 return pet_stmt_free(stmt
);
2296 /* Does "scop" have a skip condition of the given "type"?
2298 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2300 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2304 return ext
->skip
[type
] != NULL
;
2307 /* Does "scop" have a skip condition of the given "type" that
2308 * is an affine expression?
2310 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2312 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2316 if (!ext
->skip
[type
])
2318 return set_is_affine(ext
->skip
[type
]);
2321 /* Does "scop" have a skip condition of the given "type" that
2322 * is not an affine expression?
2324 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2326 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2331 if (!ext
->skip
[type
])
2333 aff
= set_is_affine(ext
->skip
[type
]);
2339 /* Does "scop" have a skip condition of the given "type" that
2340 * is affine and holds on the entire domain?
2342 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2344 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2349 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2350 if (is_aff
< 0 || !is_aff
)
2353 set
= isl_set_copy(ext
->skip
[type
]);
2354 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 1);
2355 set
= isl_set_params(set
);
2356 is_univ
= isl_set_plain_is_universe(set
);
2362 /* Replace scop->skip[type] by "skip".
2364 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2365 enum pet_skip type
, __isl_take isl_set
*skip
)
2367 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2372 isl_set_free(ext
->skip
[type
]);
2373 ext
->skip
[type
] = skip
;
2378 return pet_scop_free(scop
);
2381 /* Return a copy of scop->skip[type].
2383 __isl_give isl_set
*pet_scop_get_skip(struct pet_scop
*scop
,
2386 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2391 return isl_set_copy(ext
->skip
[type
]);
2394 /* Assuming scop->skip[type] is an affine expression,
2395 * return the constraints on the parameters for which the skip condition
2398 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2403 skip
= pet_scop_get_skip(scop
, type
);
2404 skip
= isl_set_fix_si(skip
, isl_dim_set
, 0, 1);
2405 skip
= isl_set_params(skip
);
2410 /* Return a map to the skip condition of the given type.
2412 __isl_give isl_map
*pet_scop_get_skip_map(struct pet_scop
*scop
,
2415 return isl_map_from_range(pet_scop_get_skip(scop
, type
));
2418 /* Return the identifier of the variable that is accessed by
2419 * the skip condition of the given type.
2421 * The skip condition is assumed not to be an affine condition.
2423 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2426 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2431 return isl_set_get_tuple_id(ext
->skip
[type
]);
2434 /* Return an access pet_expr corresponding to the skip condition
2435 * of the given type.
2437 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2440 return pet_expr_from_access(pet_scop_get_skip_map(scop
, type
));
2443 /* Drop the the skip condition scop->skip[type].
2445 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2447 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2452 isl_set_free(ext
->skip
[type
]);
2453 ext
->skip
[type
] = NULL
;
2456 /* Make the skip condition (if any) depend on the value of "test" being
2457 * equal to "satisfied".
2459 * We only support the case where the original skip condition is universal,
2460 * i.e., where skipping is unconditional, and where satisfied == 1.
2461 * In this case, the skip condition is changed to skip only when
2462 * "test" is equal to one.
2464 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2465 enum pet_skip type
, __isl_keep isl_map
*test
, int satisfied
)
2471 if (!pet_scop_has_skip(scop
, type
))
2475 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2477 return pet_scop_free(scop
);
2478 if (satisfied
&& is_univ
) {
2479 scop
= pet_scop_set_skip(scop
, type
,
2480 isl_map_range(isl_map_copy(test
)));
2484 isl_die(isl_map_get_ctx(test
), isl_error_internal
,
2485 "skip expression cannot be filtered",
2486 return pet_scop_free(scop
));
2492 /* Make all statements in "scop" depend on the value of "test"
2493 * being equal to "satisfied" by adjusting their domains.
2495 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2496 __isl_take isl_map
*test
, int satisfied
)
2500 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2501 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2506 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2507 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2508 isl_map_copy(test
), satisfied
);
2509 if (!scop
->stmts
[i
])
2517 return pet_scop_free(scop
);
2520 /* Add all parameters in "expr" to "dim" and return the result.
2522 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2523 __isl_take isl_space
*dim
)
2529 for (i
= 0; i
< expr
->n_arg
; ++i
)
2531 dim
= expr_collect_params(expr
->args
[i
], dim
);
2533 if (expr
->type
== pet_expr_access
)
2534 dim
= isl_space_align_params(dim
,
2535 isl_map_get_space(expr
->acc
.access
));
2539 isl_space_free(dim
);
2540 return pet_expr_free(expr
);
2543 /* Add all parameters in "stmt" to "dim" and return the result.
2545 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2546 __isl_take isl_space
*dim
)
2551 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2552 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2553 dim
= expr_collect_params(stmt
->body
, dim
);
2557 isl_space_free(dim
);
2558 return pet_stmt_free(stmt
);
2561 /* Add all parameters in "array" to "dim" and return the result.
2563 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2564 __isl_take isl_space
*dim
)
2569 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2570 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2574 pet_array_free(array
);
2575 return isl_space_free(dim
);
2578 /* Add all parameters in "scop" to "dim" and return the result.
2580 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2581 __isl_take isl_space
*dim
)
2588 for (i
= 0; i
< scop
->n_array
; ++i
)
2589 dim
= array_collect_params(scop
->arrays
[i
], dim
);
2591 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2592 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
2596 isl_space_free(dim
);
2597 return pet_scop_free(scop
);
2600 /* Add all parameters in "dim" to all access relations in "expr".
2602 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
2603 __isl_take isl_space
*dim
)
2610 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2612 expr_propagate_params(expr
->args
[i
],
2613 isl_space_copy(dim
));
2618 if (expr
->type
== pet_expr_access
) {
2619 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
2620 isl_space_copy(dim
));
2621 if (!expr
->acc
.access
)
2625 isl_space_free(dim
);
2628 isl_space_free(dim
);
2629 return pet_expr_free(expr
);
2632 /* Add all parameters in "dim" to the domain, schedule and
2633 * all access relations in "stmt".
2635 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2636 __isl_take isl_space
*dim
)
2641 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
2642 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2643 isl_space_copy(dim
));
2644 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
2646 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2649 isl_space_free(dim
);
2652 isl_space_free(dim
);
2653 return pet_stmt_free(stmt
);
2656 /* Add all parameters in "dim" to "array".
2658 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2659 __isl_take isl_space
*dim
)
2664 array
->context
= isl_set_align_params(array
->context
,
2665 isl_space_copy(dim
));
2666 array
->extent
= isl_set_align_params(array
->extent
,
2667 isl_space_copy(dim
));
2668 if (array
->value_bounds
) {
2669 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2670 isl_space_copy(dim
));
2671 if (!array
->value_bounds
)
2675 if (!array
->context
|| !array
->extent
)
2678 isl_space_free(dim
);
2681 isl_space_free(dim
);
2682 return pet_array_free(array
);
2685 /* Add all parameters in "dim" to "scop".
2687 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2688 __isl_take isl_space
*dim
)
2695 for (i
= 0; i
< scop
->n_array
; ++i
) {
2696 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2697 isl_space_copy(dim
));
2698 if (!scop
->arrays
[i
])
2702 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2703 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2704 isl_space_copy(dim
));
2705 if (!scop
->stmts
[i
])
2709 isl_space_free(dim
);
2712 isl_space_free(dim
);
2713 return pet_scop_free(scop
);
2716 /* Update all isl_sets and isl_maps in "scop" such that they all
2717 * have the same parameters.
2719 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2726 dim
= isl_set_get_space(scop
->context
);
2727 dim
= scop_collect_params(scop
, dim
);
2729 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
2730 scop
= scop_propagate_params(scop
, dim
);
2735 /* Check if the given access relation accesses a (0D) array that corresponds
2736 * to one of the parameters in "dim". If so, replace the array access
2737 * by an access to the set of integers with as index (and value)
2740 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
2741 __isl_take isl_space
*dim
)
2743 isl_id
*array_id
= NULL
;
2746 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
2747 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2748 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
2750 isl_space_free(dim
);
2753 isl_id_free(array_id
);
2757 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
2759 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
2760 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
2763 isl_id_free(array_id
);
2765 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2766 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
2771 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2772 * in "dim" by a value equal to the corresponding parameter.
2774 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
2775 __isl_take isl_space
*dim
)
2782 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2784 expr_detect_parameter_accesses(expr
->args
[i
],
2785 isl_space_copy(dim
));
2790 if (expr
->type
== pet_expr_access
) {
2791 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
2792 isl_space_copy(dim
));
2793 if (!expr
->acc
.access
)
2797 isl_space_free(dim
);
2800 isl_space_free(dim
);
2801 return pet_expr_free(expr
);
2804 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2805 * in "dim" by a value equal to the corresponding parameter.
2807 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2808 __isl_take isl_space
*dim
)
2813 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
2814 isl_space_copy(dim
));
2816 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2819 isl_space_free(dim
);
2822 isl_space_free(dim
);
2823 return pet_stmt_free(stmt
);
2826 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2827 * in "dim" by a value equal to the corresponding parameter.
2829 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2830 __isl_take isl_space
*dim
)
2837 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2838 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2839 isl_space_copy(dim
));
2840 if (!scop
->stmts
[i
])
2844 isl_space_free(dim
);
2847 isl_space_free(dim
);
2848 return pet_scop_free(scop
);
2851 /* Replace all accesses to (0D) arrays that correspond to any of
2852 * the parameters used in "scop" by a value equal
2853 * to the corresponding parameter.
2855 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2862 dim
= isl_set_get_space(scop
->context
);
2863 dim
= scop_collect_params(scop
, dim
);
2865 scop
= scop_detect_parameter_accesses(scop
, dim
);
2870 /* Add all read access relations (if "read" is set) and/or all write
2871 * access relations (if "write" is set) to "accesses" and return the result.
2873 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
2874 int read
, int write
, __isl_take isl_union_map
*accesses
)
2883 for (i
= 0; i
< expr
->n_arg
; ++i
)
2884 accesses
= expr_collect_accesses(expr
->args
[i
],
2885 read
, write
, accesses
);
2887 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2888 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
2889 accesses
= isl_union_map_add_map(accesses
,
2890 isl_map_copy(expr
->acc
.access
));
2895 /* Collect and return all read access relations (if "read" is set)
2896 * and/or all write access relations (if "write" is set) in "stmt".
2898 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2899 int read
, int write
, __isl_take isl_space
*dim
)
2901 isl_union_map
*accesses
;
2906 accesses
= isl_union_map_empty(dim
);
2907 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
2908 accesses
= isl_union_map_intersect_domain(accesses
,
2909 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
2914 /* Collect and return all read access relations (if "read" is set)
2915 * and/or all write access relations (if "write" is set) in "scop".
2917 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2918 int read
, int write
)
2921 isl_union_map
*accesses
;
2926 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2928 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2929 isl_union_map
*accesses_i
;
2930 isl_space
*dim
= isl_set_get_space(scop
->context
);
2931 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
2933 accesses
= isl_union_map_union(accesses
, accesses_i
);
2939 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
2941 return scop_collect_accesses(scop
, 1, 0);
2944 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
2946 return scop_collect_accesses(scop
, 0, 1);
2949 /* Collect and return the union of iteration domains in "scop".
2951 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2955 isl_union_set
*domain
;
2960 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2962 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2963 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2964 domain
= isl_union_set_add_set(domain
, domain_i
);
2970 /* Collect and return the schedules of the statements in "scop".
2971 * The range is normalized to the maximal number of scheduling
2974 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2977 isl_map
*schedule_i
;
2978 isl_union_map
*schedule
;
2979 int depth
, max_depth
= 0;
2984 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2986 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2987 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2988 if (depth
> max_depth
)
2992 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2993 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2994 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2995 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2997 for (j
= depth
; j
< max_depth
; ++j
)
2998 schedule_i
= isl_map_fix_si(schedule_i
,
3000 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
3006 /* Does expression "expr" write to "id"?
3008 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
3013 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3014 int writes
= expr_writes(expr
->args
[i
], id
);
3015 if (writes
< 0 || writes
)
3019 if (expr
->type
!= pet_expr_access
)
3021 if (!expr
->acc
.write
)
3023 if (pet_expr_is_affine(expr
))
3026 write_id
= pet_expr_access_get_id(expr
);
3027 isl_id_free(write_id
);
3032 return write_id
== id
;
3035 /* Does statement "stmt" write to "id"?
3037 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
3039 return expr_writes(stmt
->body
, id
);
3042 /* Is there any write access in "scop" that accesses "id"?
3044 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
3051 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3052 int writes
= stmt_writes(scop
->stmts
[i
], id
);
3053 if (writes
< 0 || writes
)
3060 /* Add a reference identifier to access expression "expr".
3061 * "user" points to an integer that contains the sequence number
3062 * of the next reference.
3064 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
3073 ctx
= isl_map_get_ctx(expr
->acc
.access
);
3074 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
3075 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
3076 if (!expr
->acc
.ref_id
)
3077 return pet_expr_free(expr
);
3082 /* Add a reference identifier to all access expressions in "stmt".
3083 * "n_ref" points to an integer that contains the sequence number
3084 * of the next reference.
3086 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
3093 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3094 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3095 &access_add_ref_id
, n_ref
);
3097 return pet_stmt_free(stmt
);
3100 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
3102 return pet_stmt_free(stmt
);
3107 /* Add a reference identifier to all access expressions in "scop".
3109 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
3118 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3119 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3120 if (!scop
->stmts
[i
])
3121 return pet_scop_free(scop
);
3127 /* Reset the user pointer on the tuple id and all parameter ids in "set".
3129 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
3133 n
= isl_set_dim(set
, isl_dim_param
);
3134 for (i
= 0; i
< n
; ++i
) {
3135 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
3136 const char *name
= isl_id_get_name(id
);
3137 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
3141 if (!isl_set_is_params(set
) && isl_set_has_tuple_id(set
)) {
3142 isl_id
*id
= isl_set_get_tuple_id(set
);
3143 const char *name
= isl_id_get_name(id
);
3144 set
= isl_set_set_tuple_name(set
, name
);
3151 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
3153 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
3157 n
= isl_map_dim(map
, isl_dim_param
);
3158 for (i
= 0; i
< n
; ++i
) {
3159 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
3160 const char *name
= isl_id_get_name(id
);
3161 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
3165 if (isl_map_has_tuple_id(map
, isl_dim_in
)) {
3166 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_in
);
3167 const char *name
= isl_id_get_name(id
);
3168 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
3172 if (isl_map_has_tuple_id(map
, isl_dim_out
)) {
3173 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_out
);
3174 const char *name
= isl_id_get_name(id
);
3175 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
3182 /* Reset the user pointer on all parameter ids in "array".
3184 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3189 array
->context
= set_anonymize(array
->context
);
3190 array
->extent
= set_anonymize(array
->extent
);
3191 if (!array
->context
|| !array
->extent
)
3192 return pet_array_free(array
);
3197 /* Reset the user pointer on all parameter and tuple ids in
3198 * the access relation of the access expression "expr".
3200 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
3202 expr
->acc
.access
= map_anonymize(expr
->acc
.access
);
3203 if (!expr
->acc
.access
)
3204 return pet_expr_free(expr
);
3209 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3211 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3220 stmt
->domain
= set_anonymize(stmt
->domain
);
3221 stmt
->schedule
= map_anonymize(stmt
->schedule
);
3222 if (!stmt
->domain
|| !stmt
->schedule
)
3223 return pet_stmt_free(stmt
);
3225 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3226 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3227 &access_anonymize
, NULL
);
3229 return pet_stmt_free(stmt
);
3232 stmt
->body
= pet_expr_map_access(stmt
->body
,
3233 &access_anonymize
, NULL
);
3235 return pet_stmt_free(stmt
);
3240 /* Reset the user pointer on the tuple ids and all parameter ids
3243 static struct pet_implication
*implication_anonymize(
3244 struct pet_implication
*implication
)
3249 implication
->extension
= map_anonymize(implication
->extension
);
3250 if (!implication
->extension
)
3251 return pet_implication_free(implication
);
3256 /* Reset the user pointer on all parameter and tuple ids in "scop".
3258 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3265 scop
->context
= set_anonymize(scop
->context
);
3266 scop
->context_value
= set_anonymize(scop
->context_value
);
3267 if (!scop
->context
|| !scop
->context_value
)
3268 return pet_scop_free(scop
);
3270 for (i
= 0; i
< scop
->n_array
; ++i
) {
3271 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3272 if (!scop
->arrays
[i
])
3273 return pet_scop_free(scop
);
3276 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3277 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3278 if (!scop
->stmts
[i
])
3279 return pet_scop_free(scop
);
3282 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3283 scop
->implications
[i
] =
3284 implication_anonymize(scop
->implications
[i
]);
3285 if (!scop
->implications
[i
])
3286 return pet_scop_free(scop
);
3292 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3293 * then intersect the range of "map" with the valid set of values.
3295 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
3296 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
3301 isl_ctx
*ctx
= isl_map_get_ctx(map
);
3303 id
= pet_expr_access_get_id(arg
);
3304 space
= isl_space_alloc(ctx
, 0, 0, 1);
3305 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
3306 vb
= isl_union_map_extract_map(value_bounds
, space
);
3307 if (!isl_map_plain_is_empty(vb
))
3308 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
3315 /* Given a set "domain", return a wrapped relation with the given set
3316 * as domain and a range of dimension "n_arg", where each coordinate
3317 * is either unbounded or, if the corresponding element of args is of
3318 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3320 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
3321 unsigned n_arg
, struct pet_expr
**args
,
3322 __isl_keep isl_union_map
*value_bounds
)
3328 map
= isl_map_from_domain(domain
);
3329 space
= isl_map_get_space(map
);
3330 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
3332 for (i
= 0; i
< n_arg
; ++i
) {
3334 struct pet_expr
*arg
= args
[i
];
3336 map_i
= isl_map_universe(isl_space_copy(space
));
3337 if (arg
->type
== pet_expr_access
)
3338 map_i
= access_apply_value_bounds(map_i
, arg
,
3340 map
= isl_map_flat_range_product(map
, map_i
);
3342 isl_space_free(space
);
3344 return isl_map_wrap(map
);
3347 /* Data used in access_gist() callback.
3349 struct pet_access_gist_data
{
3351 isl_union_map
*value_bounds
;
3354 /* Given an expression "expr" of type pet_expr_access, compute
3355 * the gist of the associated access relation with respect to
3356 * data->domain and the bounds on the values of the arguments
3357 * of the expression.
3359 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3361 struct pet_access_gist_data
*data
= user
;
3364 domain
= isl_set_copy(data
->domain
);
3365 if (expr
->n_arg
> 0)
3366 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3367 data
->value_bounds
);
3369 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
3370 if (!expr
->acc
.access
)
3371 return pet_expr_free(expr
);
3376 /* Compute the gist of the iteration domain and all access relations
3377 * of "stmt" based on the constraints on the parameters specified by "context"
3378 * and the constraints on the values of nested accesses specified
3379 * by "value_bounds".
3381 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3382 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3387 struct pet_access_gist_data data
;
3392 data
.domain
= isl_set_copy(stmt
->domain
);
3393 data
.value_bounds
= value_bounds
;
3394 if (stmt
->n_arg
> 0)
3395 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3397 data
.domain
= isl_set_intersect_params(data
.domain
,
3398 isl_set_copy(context
));
3400 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3401 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3402 &access_gist
, &data
);
3407 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3411 isl_set_free(data
.domain
);
3413 space
= isl_set_get_space(stmt
->domain
);
3414 if (isl_space_is_wrapping(space
))
3415 space
= isl_space_domain(isl_space_unwrap(space
));
3416 domain
= isl_set_universe(space
);
3417 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3418 if (stmt
->n_arg
> 0)
3419 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3421 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3423 return pet_stmt_free(stmt
);
3427 isl_set_free(data
.domain
);
3428 return pet_stmt_free(stmt
);
3431 /* Compute the gist of the extent of the array
3432 * based on the constraints on the parameters specified by "context".
3434 static struct pet_array
*array_gist(struct pet_array
*array
,
3435 __isl_keep isl_set
*context
)
3440 array
->extent
= isl_set_gist_params(array
->extent
,
3441 isl_set_copy(context
));
3443 return pet_array_free(array
);
3448 /* Compute the gist of all sets and relations in "scop"
3449 * based on the constraints on the parameters specified by "scop->context"
3450 * and the constraints on the values of nested accesses specified
3451 * by "value_bounds".
3453 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3454 __isl_keep isl_union_map
*value_bounds
)
3461 scop
->context
= isl_set_coalesce(scop
->context
);
3463 return pet_scop_free(scop
);
3465 for (i
= 0; i
< scop
->n_array
; ++i
) {
3466 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3467 if (!scop
->arrays
[i
])
3468 return pet_scop_free(scop
);
3471 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3472 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3474 if (!scop
->stmts
[i
])
3475 return pet_scop_free(scop
);
3481 /* Intersect the context of "scop" with "context".
3482 * To ensure that we don't introduce any unnamed parameters in
3483 * the context of "scop", we first remove the unnamed parameters
3486 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3487 __isl_take isl_set
*context
)
3492 context
= set_project_out_unnamed_params(context
);
3493 scop
->context
= isl_set_intersect(scop
->context
, context
);
3495 return pet_scop_free(scop
);
3499 isl_set_free(context
);
3500 return pet_scop_free(scop
);
3503 /* Drop the current context of "scop". That is, replace the context
3504 * by a universal set.
3506 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3513 space
= isl_set_get_space(scop
->context
);
3514 isl_set_free(scop
->context
);
3515 scop
->context
= isl_set_universe(space
);
3517 return pet_scop_free(scop
);
3522 /* Append "array" to the arrays of "scop".
3524 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3525 struct pet_array
*array
)
3528 struct pet_array
**arrays
;
3530 if (!array
|| !scop
)
3533 ctx
= isl_set_get_ctx(scop
->context
);
3534 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3538 scop
->arrays
= arrays
;
3539 scop
->arrays
[scop
->n_array
] = array
;
3544 pet_array_free(array
);
3545 return pet_scop_free(scop
);
3548 /* Create and return an implication on filter values equal to "satisfied"
3549 * with extension "map".
3551 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3555 struct pet_implication
*implication
;
3559 ctx
= isl_map_get_ctx(map
);
3560 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3564 implication
->extension
= map
;
3565 implication
->satisfied
= satisfied
;
3573 /* Add an implication on filter values equal to "satisfied"
3574 * with extension "map" to "scop".
3576 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3577 __isl_take isl_map
*map
, int satisfied
)
3580 struct pet_implication
*implication
;
3581 struct pet_implication
**implications
;
3583 implication
= new_implication(map
, satisfied
);
3584 if (!scop
|| !implication
)
3587 ctx
= isl_set_get_ctx(scop
->context
);
3588 implications
= isl_realloc_array(ctx
, scop
->implications
,
3589 struct pet_implication
*,
3590 scop
->n_implication
+ 1);
3593 scop
->implications
= implications
;
3594 scop
->implications
[scop
->n_implication
] = implication
;
3595 scop
->n_implication
++;
3599 pet_implication_free(implication
);
3600 return pet_scop_free(scop
);