2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012 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 a pet_expr that kills the elements specified by "access".
164 struct pet_expr
*pet_expr_kill_from_access(__isl_take isl_map
*access
)
167 struct pet_expr
*expr
;
169 ctx
= isl_map_get_ctx(access
);
170 expr
= pet_expr_from_access(access
);
174 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
177 /* Construct a unary pet_expr that performs "op" on "arg".
179 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
180 struct pet_expr
*arg
)
182 struct pet_expr
*expr
;
186 expr
= isl_alloc_type(ctx
, struct pet_expr
);
190 expr
->type
= pet_expr_unary
;
193 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
196 expr
->args
[pet_un_arg
] = arg
;
204 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
206 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
207 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
209 struct pet_expr
*expr
;
213 expr
= isl_alloc_type(ctx
, struct pet_expr
);
217 expr
->type
= pet_expr_binary
;
220 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
223 expr
->args
[pet_bin_lhs
] = lhs
;
224 expr
->args
[pet_bin_rhs
] = rhs
;
233 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
235 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
236 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
238 struct pet_expr
*expr
;
240 if (!cond
|| !lhs
|| !rhs
)
242 expr
= isl_alloc_type(ctx
, struct pet_expr
);
246 expr
->type
= pet_expr_ternary
;
248 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
251 expr
->args
[pet_ter_cond
] = cond
;
252 expr
->args
[pet_ter_true
] = lhs
;
253 expr
->args
[pet_ter_false
] = rhs
;
263 /* Construct a call pet_expr that calls function "name" with "n_arg"
264 * arguments. The caller is responsible for filling in the arguments.
266 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
269 struct pet_expr
*expr
;
271 expr
= isl_alloc_type(ctx
, struct pet_expr
);
275 expr
->type
= pet_expr_call
;
277 expr
->name
= strdup(name
);
278 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
279 if (!expr
->name
|| !expr
->args
)
280 return pet_expr_free(expr
);
285 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
287 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
288 struct pet_expr
*arg
)
290 struct pet_expr
*expr
;
295 expr
= isl_alloc_type(ctx
, struct pet_expr
);
299 expr
->type
= pet_expr_cast
;
301 expr
->type_name
= strdup(type_name
);
302 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
303 if (!expr
->type_name
|| !expr
->args
)
315 /* Construct a pet_expr that represents the double "d".
317 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
319 struct pet_expr
*expr
;
321 expr
= isl_calloc_type(ctx
, struct pet_expr
);
325 expr
->type
= pet_expr_double
;
327 expr
->d
.s
= strdup(s
);
329 return pet_expr_free(expr
);
334 void *pet_expr_free(struct pet_expr
*expr
)
341 for (i
= 0; i
< expr
->n_arg
; ++i
)
342 pet_expr_free(expr
->args
[i
]);
345 switch (expr
->type
) {
346 case pet_expr_access
:
347 isl_id_free(expr
->acc
.ref_id
);
348 isl_map_free(expr
->acc
.access
);
354 free(expr
->type_name
);
356 case pet_expr_double
:
360 case pet_expr_binary
:
361 case pet_expr_ternary
:
369 static void expr_dump(struct pet_expr
*expr
, int indent
)
376 fprintf(stderr
, "%*s", indent
, "");
378 switch (expr
->type
) {
379 case pet_expr_double
:
380 fprintf(stderr
, "%s\n", expr
->d
.s
);
382 case pet_expr_access
:
383 isl_id_dump(expr
->acc
.ref_id
);
384 fprintf(stderr
, "%*s", indent
, "");
385 isl_map_dump(expr
->acc
.access
);
386 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
388 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
389 "", expr
->acc
.write
);
390 for (i
= 0; i
< expr
->n_arg
; ++i
)
391 expr_dump(expr
->args
[i
], indent
+ 2);
394 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
395 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
397 case pet_expr_binary
:
398 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
399 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
400 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
402 case pet_expr_ternary
:
403 fprintf(stderr
, "?:\n");
404 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
405 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
406 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
409 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
410 for (i
= 0; i
< expr
->n_arg
; ++i
)
411 expr_dump(expr
->args
[i
], indent
+ 2);
414 fprintf(stderr
, "(%s)\n", expr
->type_name
);
415 for (i
= 0; i
< expr
->n_arg
; ++i
)
416 expr_dump(expr
->args
[i
], indent
+ 2);
421 void pet_expr_dump(struct pet_expr
*expr
)
426 /* Does "expr" represent an access to an unnamed space, i.e.,
427 * does it represent an affine expression?
429 int pet_expr_is_affine(struct pet_expr
*expr
)
435 if (expr
->type
!= pet_expr_access
)
438 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
445 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
447 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
451 if (expr
->type
!= pet_expr_access
)
454 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
457 /* Return 1 if the two pet_exprs are equivalent.
459 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
463 if (!expr1
|| !expr2
)
466 if (expr1
->type
!= expr2
->type
)
468 if (expr1
->n_arg
!= expr2
->n_arg
)
470 for (i
= 0; i
< expr1
->n_arg
; ++i
)
471 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
473 switch (expr1
->type
) {
474 case pet_expr_double
:
475 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
477 if (expr1
->d
.val
!= expr2
->d
.val
)
480 case pet_expr_access
:
481 if (expr1
->acc
.read
!= expr2
->acc
.read
)
483 if (expr1
->acc
.write
!= expr2
->acc
.write
)
485 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
487 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
489 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
493 case pet_expr_binary
:
494 case pet_expr_ternary
:
495 if (expr1
->op
!= expr2
->op
)
499 if (strcmp(expr1
->name
, expr2
->name
))
503 if (strcmp(expr1
->type_name
, expr2
->type_name
))
511 /* Add extra conditions on the parameters to all access relations in "expr".
513 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
514 __isl_take isl_set
*cond
)
521 for (i
= 0; i
< expr
->n_arg
; ++i
) {
522 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
528 if (expr
->type
== pet_expr_access
) {
529 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
531 if (!expr
->acc
.access
)
539 return pet_expr_free(expr
);
542 /* Modify all expressions of type pet_expr_access in "expr"
543 * by calling "fn" on them.
545 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
546 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
554 for (i
= 0; i
< expr
->n_arg
; ++i
) {
555 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
557 return pet_expr_free(expr
);
560 if (expr
->type
== pet_expr_access
)
561 expr
= fn(expr
, user
);
566 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
568 * Return -1 on error (where fn return a negative value is treated as an error).
569 * Otherwise return 0.
571 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
572 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
579 for (i
= 0; i
< expr
->n_arg
; ++i
)
580 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
583 if (expr
->type
== pet_expr_access
)
584 return fn(expr
, user
);
589 /* Modify the access relation of the given access expression
590 * based on the given iteration space transformation.
591 * If the access has any arguments then the domain of the access relation
592 * is a wrapped mapping from the iteration space to the space of
593 * argument values. We only need to change the domain of this wrapped
594 * mapping, so we extend the input transformation with an identity mapping
595 * on the space of argument values.
597 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
599 isl_map
*update
= user
;
602 update
= isl_map_copy(update
);
604 dim
= isl_map_get_space(expr
->acc
.access
);
605 dim
= isl_space_domain(dim
);
606 if (!isl_space_is_wrapping(dim
))
610 dim
= isl_space_unwrap(dim
);
611 dim
= isl_space_range(dim
);
612 dim
= isl_space_map_from_set(dim
);
613 id
= isl_map_identity(dim
);
614 update
= isl_map_product(update
, id
);
617 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, update
);
618 if (!expr
->acc
.access
)
619 return pet_expr_free(expr
);
624 /* Modify all access relations in "expr" based on the given iteration space
627 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
628 __isl_take isl_map
*update
)
630 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
631 isl_map_free(update
);
635 /* Construct a pet_stmt with given line number and statement
636 * number from a pet_expr.
637 * The initial iteration domain is the zero-dimensional universe.
638 * The name of the domain is given by "label" if it is non-NULL.
639 * Otherwise, the name is constructed as S_<id>.
640 * The domains of all access relations are modified to refer
641 * to the statement iteration domain.
643 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
644 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
646 struct pet_stmt
*stmt
;
656 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
660 dim
= isl_space_set_alloc(ctx
, 0, 0);
662 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
664 snprintf(name
, sizeof(name
), "S_%d", id
);
665 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
667 dom
= isl_set_universe(isl_space_copy(dim
));
668 sched
= isl_map_from_domain(isl_set_copy(dom
));
670 dim
= isl_space_from_range(dim
);
671 add_name
= isl_map_universe(dim
);
672 expr
= expr_update_domain(expr
, add_name
);
676 stmt
->schedule
= sched
;
679 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
680 return pet_stmt_free(stmt
);
685 return pet_expr_free(expr
);
688 void *pet_stmt_free(struct pet_stmt
*stmt
)
695 isl_set_free(stmt
->domain
);
696 isl_map_free(stmt
->schedule
);
697 pet_expr_free(stmt
->body
);
699 for (i
= 0; i
< stmt
->n_arg
; ++i
)
700 pet_expr_free(stmt
->args
[i
]);
707 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
714 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
715 fprintf(stderr
, "%*s", indent
, "");
716 isl_set_dump(stmt
->domain
);
717 fprintf(stderr
, "%*s", indent
, "");
718 isl_map_dump(stmt
->schedule
);
719 expr_dump(stmt
->body
, indent
);
720 for (i
= 0; i
< stmt
->n_arg
; ++i
)
721 expr_dump(stmt
->args
[i
], indent
+ 2);
724 void pet_stmt_dump(struct pet_stmt
*stmt
)
729 struct pet_array
*pet_array_free(struct pet_array
*array
)
734 isl_set_free(array
->context
);
735 isl_set_free(array
->extent
);
736 isl_set_free(array
->value_bounds
);
737 free(array
->element_type
);
743 void pet_array_dump(struct pet_array
*array
)
748 isl_set_dump(array
->context
);
749 isl_set_dump(array
->extent
);
750 isl_set_dump(array
->value_bounds
);
751 fprintf(stderr
, "%s %s\n", array
->element_type
,
752 array
->live_out
? "live-out" : "");
755 /* Alloc a pet_scop structure, with extra room for information that
756 * is only used during parsing.
758 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
760 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
763 /* Construct a pet_scop with room for n statements.
765 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
768 struct pet_scop
*scop
;
770 scop
= pet_scop_alloc(ctx
);
774 space
= isl_space_params_alloc(ctx
, 0);
775 scop
->context
= isl_set_universe(isl_space_copy(space
));
776 scop
->context_value
= isl_set_universe(space
);
777 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
778 if (!scop
->context
|| !scop
->stmts
)
779 return pet_scop_free(scop
);
786 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
788 return scop_alloc(ctx
, 0);
791 /* Update "context" with respect to the valid parameter values for "access".
793 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
794 __isl_take isl_set
*context
)
796 context
= isl_set_intersect(context
,
797 isl_map_params(isl_map_copy(access
)));
801 /* Update "context" with respect to the valid parameter values for "expr".
803 * If "expr" represents a ternary operator, then a parameter value
804 * needs to be valid for the condition and for at least one of the
805 * remaining two arguments.
806 * If the condition is an affine expression, then we can be a bit more specific.
807 * The parameter then has to be valid for the second argument for
808 * non-zero accesses and valid for the third argument for zero accesses.
810 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
811 __isl_take isl_set
*context
)
815 if (expr
->type
== pet_expr_ternary
) {
817 isl_set
*context1
, *context2
;
819 is_aff
= pet_expr_is_affine(expr
->args
[0]);
823 context
= expr_extract_context(expr
->args
[0], context
);
824 context1
= expr_extract_context(expr
->args
[1],
825 isl_set_copy(context
));
826 context2
= expr_extract_context(expr
->args
[2], context
);
832 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
833 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
834 zero_set
= isl_map_params(access
);
835 context1
= isl_set_subtract(context1
,
836 isl_set_copy(zero_set
));
837 context2
= isl_set_intersect(context2
, zero_set
);
840 context
= isl_set_union(context1
, context2
);
841 context
= isl_set_coalesce(context
);
846 for (i
= 0; i
< expr
->n_arg
; ++i
)
847 context
= expr_extract_context(expr
->args
[i
], context
);
849 if (expr
->type
== pet_expr_access
)
850 context
= access_extract_context(expr
->acc
.access
, context
);
854 isl_set_free(context
);
858 /* Update "context" with respect to the valid parameter values for "stmt".
860 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
861 __isl_take isl_set
*context
)
865 for (i
= 0; i
< stmt
->n_arg
; ++i
)
866 context
= expr_extract_context(stmt
->args
[i
], context
);
868 context
= expr_extract_context(stmt
->body
, context
);
873 /* Construct a pet_scop that contains the given pet_stmt.
875 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
877 struct pet_scop
*scop
;
882 scop
= scop_alloc(ctx
, 1);
886 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
890 scop
->stmts
[0] = stmt
;
899 /* Does "set" represent an element of an unnamed space, i.e.,
900 * does it represent an affine expression?
902 static int set_is_affine(__isl_keep isl_set
*set
)
906 has_id
= isl_set_has_tuple_id(set
);
913 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
914 * ext may be equal to either ext1 or ext2.
916 * The two skips that need to be combined are assumed to be affine expressions.
918 * We need to skip in ext if we need to skip in either ext1 or ext2.
919 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
921 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
922 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
925 isl_set
*set
, *skip1
, *skip2
;
929 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
931 if (!ext1
->skip
[type
]) {
934 ext
->skip
[type
] = ext2
->skip
[type
];
935 ext2
->skip
[type
] = NULL
;
938 if (!ext2
->skip
[type
]) {
941 ext
->skip
[type
] = ext1
->skip
[type
];
942 ext1
->skip
[type
] = NULL
;
946 if (!set_is_affine(ext1
->skip
[type
]) ||
947 !set_is_affine(ext2
->skip
[type
]))
948 isl_die(isl_set_get_ctx(ext1
->skip
[type
]), isl_error_internal
,
949 "can only combine affine skips",
950 return pet_scop_free(&ext
->scop
));
952 skip1
= isl_set_copy(ext1
->skip
[type
]);
953 skip2
= isl_set_copy(ext2
->skip
[type
]);
954 set
= isl_set_intersect(
955 isl_set_fix_si(isl_set_copy(skip1
), isl_dim_set
, 0, 0),
956 isl_set_fix_si(isl_set_copy(skip2
), isl_dim_set
, 0, 0));
957 set
= isl_set_union(set
, isl_set_fix_si(skip1
, isl_dim_set
, 0, 1));
958 set
= isl_set_union(set
, isl_set_fix_si(skip2
, isl_dim_set
, 0, 1));
959 set
= isl_set_coalesce(set
);
960 isl_set_free(ext1
->skip
[type
]);
961 ext1
->skip
[type
] = NULL
;
962 isl_set_free(ext2
->skip
[type
]);
963 ext2
->skip
[type
] = NULL
;
964 ext
->skip
[type
] = set
;
965 if (!ext
->skip
[type
])
966 return pet_scop_free(&ext
->scop
);
971 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
972 * where type takes on the values pet_skip_now and pet_skip_later.
973 * scop may be equal to either scop1 or scop2.
975 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
976 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
978 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
979 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
980 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
982 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
983 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
987 /* Update scop->start and scop->end to include the region from "start"
988 * to "end". In particular, if scop->end == 0, then "scop" does not
989 * have any offset information yet and we simply take the information
990 * from "start" and "end". Otherwise, we update the fields if the
991 * region from "start" to "end" is not already included.
993 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
994 unsigned start
, unsigned end
)
998 if (scop
->end
== 0) {
1002 if (start
< scop
->start
)
1003 scop
->start
= start
;
1004 if (end
> scop
->end
)
1011 /* Combine the offset information of "scop1" and "scop2" into "scop".
1013 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
1014 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1017 scop
= pet_scop_update_start_end(scop
,
1018 scop1
->start
, scop1
->end
);
1020 scop
= pet_scop_update_start_end(scop
,
1021 scop2
->start
, scop2
->end
);
1025 /* Construct a pet_scop that contains the offset information,
1026 * arrays, statements and skip information in "scop1" and "scop2".
1028 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1029 struct pet_scop
*scop2
)
1032 struct pet_scop
*scop
= NULL
;
1034 if (!scop1
|| !scop2
)
1037 if (scop1
->n_stmt
== 0) {
1038 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
1039 pet_scop_free(scop1
);
1043 if (scop2
->n_stmt
== 0) {
1044 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
1045 pet_scop_free(scop2
);
1049 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
1053 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
1054 scop1
->n_array
+ scop2
->n_array
);
1057 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
1059 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
1060 scop
->stmts
[i
] = scop1
->stmts
[i
];
1061 scop1
->stmts
[i
] = NULL
;
1064 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
1065 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
1066 scop2
->stmts
[i
] = NULL
;
1069 for (i
= 0; i
< scop1
->n_array
; ++i
) {
1070 scop
->arrays
[i
] = scop1
->arrays
[i
];
1071 scop1
->arrays
[i
] = NULL
;
1074 for (i
= 0; i
< scop2
->n_array
; ++i
) {
1075 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
1076 scop2
->arrays
[i
] = NULL
;
1079 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
1080 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
1081 scop
= scop_combine_skips(scop
, scop1
, scop2
);
1082 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
1084 pet_scop_free(scop1
);
1085 pet_scop_free(scop2
);
1088 pet_scop_free(scop1
);
1089 pet_scop_free(scop2
);
1090 pet_scop_free(scop
);
1094 /* Apply the skip condition "skip" to "scop".
1095 * That is, make sure "scop" is not executed when the condition holds.
1097 * If "skip" is an affine expression, we add the conditions under
1098 * which the expression is zero to the iteration domains.
1099 * Otherwise, we add a filter on the variable attaining the value zero.
1101 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
1102 __isl_take isl_set
*skip
)
1110 is_aff
= set_is_affine(skip
);
1115 return pet_scop_filter(scop
, isl_map_from_range(skip
), 0);
1117 skip
= isl_set_fix_si(skip
, isl_dim_set
, 0, 0);
1118 scop
= pet_scop_restrict(scop
, isl_set_params(skip
));
1123 return pet_scop_free(scop
);
1126 /* Construct a pet_scop that contains the arrays, statements and
1127 * skip information in "scop1" and "scop2", where the two scops
1128 * are executed "in sequence". That is, breaks and continues
1129 * in scop1 have an effect on scop2.
1131 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1132 struct pet_scop
*scop2
)
1134 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1135 scop2
= restrict_skip(scop2
,
1136 pet_scop_get_skip(scop1
, pet_skip_now
));
1137 return pet_scop_add(ctx
, scop1
, scop2
);
1140 /* Construct a pet_scop that contains the arrays, statements and
1141 * skip information in "scop1" and "scop2", where the two scops
1142 * are executed "in parallel". That is, any break or continue
1143 * in scop1 has no effect on scop2.
1145 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1146 struct pet_scop
*scop2
)
1148 return pet_scop_add(ctx
, scop1
, scop2
);
1151 void *pet_scop_free(struct pet_scop
*scop
)
1154 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1158 isl_set_free(scop
->context
);
1159 isl_set_free(scop
->context_value
);
1161 for (i
= 0; i
< scop
->n_array
; ++i
)
1162 pet_array_free(scop
->arrays
[i
]);
1165 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1166 pet_stmt_free(scop
->stmts
[i
]);
1168 isl_set_free(ext
->skip
[pet_skip_now
]);
1169 isl_set_free(ext
->skip
[pet_skip_later
]);
1174 void pet_scop_dump(struct pet_scop
*scop
)
1177 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1182 isl_set_dump(scop
->context
);
1183 isl_set_dump(scop
->context_value
);
1184 for (i
= 0; i
< scop
->n_array
; ++i
)
1185 pet_array_dump(scop
->arrays
[i
]);
1186 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1187 pet_stmt_dump(scop
->stmts
[i
]);
1190 fprintf(stderr
, "skip\n");
1191 isl_set_dump(ext
->skip
[0]);
1192 isl_set_dump(ext
->skip
[1]);
1196 /* Return 1 if the two pet_arrays are equivalent.
1198 * We don't compare element_size as this may be target dependent.
1200 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1202 if (!array1
|| !array2
)
1205 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1207 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1209 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1211 if (array1
->value_bounds
&&
1212 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1214 if (strcmp(array1
->element_type
, array2
->element_type
))
1216 if (array1
->live_out
!= array2
->live_out
)
1218 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1220 if (array1
->declared
!= array2
->declared
)
1222 if (array1
->exposed
!= array2
->exposed
)
1228 /* Return 1 if the two pet_stmts are equivalent.
1230 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1234 if (!stmt1
|| !stmt2
)
1237 if (stmt1
->line
!= stmt2
->line
)
1239 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1241 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1243 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1245 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1247 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1248 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1255 /* Return 1 if the two pet_scops are equivalent.
1257 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1261 if (!scop1
|| !scop2
)
1264 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1266 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1269 if (scop1
->n_array
!= scop2
->n_array
)
1271 for (i
= 0; i
< scop1
->n_array
; ++i
)
1272 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1275 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1277 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1278 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1284 /* Prefix the schedule of "stmt" with an extra dimension with constant
1287 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1292 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1293 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1294 if (!stmt
->schedule
)
1295 return pet_stmt_free(stmt
);
1300 /* Prefix the schedules of all statements in "scop" with an extra
1301 * dimension with constant value "pos".
1303 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1310 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1311 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1312 if (!scop
->stmts
[i
])
1313 return pet_scop_free(scop
);
1319 /* Given a set with a parameter at "param_pos" that refers to the
1320 * iterator, "move" the iterator to the first set dimension.
1321 * That is, essentially equate the parameter to the first set dimension
1322 * and then project it out.
1324 * The first set dimension may however refer to a virtual iterator,
1325 * while the parameter refers to the "real" iterator.
1326 * We therefore need to take into account the mapping "iv_map", which
1327 * maps the virtual iterator to the real iterator.
1328 * In particular, we equate the set dimension to the input of the map
1329 * and the parameter to the output of the map and then project out
1330 * everything we don't need anymore.
1332 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1333 int param_pos
, __isl_take isl_map
*iv_map
)
1336 map
= isl_map_from_domain(set
);
1337 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1338 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1339 iv_map
= isl_map_align_params(iv_map
, isl_map_get_space(map
));
1340 map
= isl_map_apply_range(map
, iv_map
);
1341 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1342 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1343 return isl_map_domain(map
);
1346 /* Data used in embed_access.
1347 * extend adds an iterator to the iteration domain
1348 * iv_map maps the virtual iterator to the real iterator
1349 * var_id represents the induction variable of the corresponding loop
1351 struct pet_embed_access
{
1357 /* Given an access expression, embed the associated access relation
1358 * in an extra outer loop.
1360 * We first update the iteration domain to insert the extra dimension.
1362 * If the access refers to the induction variable, then it is
1363 * turned into an access to the set of integers with index (and value)
1364 * equal to the induction variable.
1366 * If the induction variable appears in the constraints (as a parameter),
1367 * then the parameter is equated to the newly introduced iteration
1368 * domain dimension and subsequently projected out.
1370 * Similarly, if the accessed array is a virtual array (with user
1371 * pointer equal to NULL), as created by create_test_access,
1372 * then it is extended along with the domain of the access.
1374 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1376 struct pet_embed_access
*data
= user
;
1378 isl_id
*array_id
= NULL
;
1381 expr
= update_domain(expr
, data
->extend
);
1385 access
= expr
->acc
.access
;
1387 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1388 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1389 if (array_id
== data
->var_id
||
1390 (array_id
&& !isl_id_get_user(array_id
))) {
1391 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1392 access
= isl_map_equate(access
,
1393 isl_dim_in
, 0, isl_dim_out
, 0);
1394 if (array_id
== data
->var_id
)
1395 access
= isl_map_apply_range(access
,
1396 isl_map_copy(data
->iv_map
));
1398 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1399 isl_id_copy(array_id
));
1401 isl_id_free(array_id
);
1403 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1405 isl_set
*set
= isl_map_wrap(access
);
1406 set
= internalize_iv(set
, pos
, isl_map_copy(data
->iv_map
));
1407 access
= isl_set_unwrap(set
);
1409 expr
->acc
.access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1410 isl_id_copy(data
->var_id
));
1411 if (!expr
->acc
.access
)
1412 return pet_expr_free(expr
);
1417 /* Embed all access subexpressions of "expr" in an extra loop.
1418 * "extend" inserts an outer loop iterator in the iteration domains.
1419 * "iv_map" maps the virtual iterator to the real iterator
1420 * "var_id" represents the induction variable.
1422 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1423 __isl_take isl_map
*extend
, __isl_take isl_map
*iv_map
,
1424 __isl_keep isl_id
*var_id
)
1426 struct pet_embed_access data
=
1427 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1429 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1430 isl_map_free(iv_map
);
1431 isl_map_free(extend
);
1435 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1436 * "dom" and schedule "sched". "var_id" represents the induction variable
1437 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1438 * That is, it maps the iterator used in "dom" and the domain of "sched"
1439 * to the iterator that some of the parameters in "stmt" may refer to.
1441 * The iteration domain and schedule of the statement are updated
1442 * according to the iteration domain and schedule of the new loop.
1443 * If stmt->domain is a wrapped map, then the iteration domain
1444 * is the domain of this map, so we need to be careful to adjust
1447 * If the induction variable appears in the constraints (as a parameter)
1448 * of the current iteration domain or the schedule of the statement,
1449 * then the parameter is equated to the newly introduced iteration
1450 * domain dimension and subsequently projected out.
1452 * Finally, all access relations are updated based on the extra loop.
1454 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1455 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1456 __isl_take isl_map
*iv_map
, __isl_take isl_id
*var_id
)
1467 if (isl_set_is_wrapping(stmt
->domain
)) {
1472 map
= isl_set_unwrap(stmt
->domain
);
1473 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1474 ran_dim
= isl_space_range(isl_map_get_space(map
));
1475 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1476 isl_set_universe(ran_dim
));
1477 map
= isl_map_flat_domain_product(ext
, map
);
1478 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1479 isl_id_copy(stmt_id
));
1480 dim
= isl_space_domain(isl_map_get_space(map
));
1481 stmt
->domain
= isl_map_wrap(map
);
1483 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1484 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1486 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1487 isl_id_copy(stmt_id
));
1488 dim
= isl_set_get_space(stmt
->domain
);
1491 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1493 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1494 isl_map_copy(iv_map
));
1496 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1497 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1498 isl_dim_in
, stmt_id
);
1500 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1502 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1503 set
= internalize_iv(set
, pos
, isl_map_copy(iv_map
));
1504 stmt
->schedule
= isl_set_unwrap(set
);
1507 dim
= isl_space_map_from_set(dim
);
1508 extend
= isl_map_identity(dim
);
1509 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1510 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1511 isl_map_get_tuple_id(extend
, isl_dim_out
));
1512 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1513 stmt
->args
[i
] = expr_embed(stmt
->args
[i
], isl_map_copy(extend
),
1514 isl_map_copy(iv_map
), var_id
);
1515 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1518 isl_id_free(var_id
);
1520 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1522 return pet_stmt_free(stmt
);
1523 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1524 return pet_stmt_free(stmt
);
1528 isl_map_free(sched
);
1529 isl_map_free(iv_map
);
1530 isl_id_free(var_id
);
1534 /* Embed the given pet_array in an extra outer loop with iteration domain
1536 * This embedding only has an effect on virtual arrays (those with
1537 * user pointer equal to NULL), which need to be extended along with
1538 * the iteration domain.
1540 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1541 __isl_take isl_set
*dom
)
1543 isl_id
*array_id
= NULL
;
1548 if (isl_set_has_tuple_id(array
->extent
))
1549 array_id
= isl_set_get_tuple_id(array
->extent
);
1551 if (array_id
&& !isl_id_get_user(array_id
)) {
1552 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1553 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1555 return pet_array_free(array
);
1558 isl_id_free(array_id
);
1567 /* Project out all unnamed parameters from "set" and return the result.
1569 static __isl_give isl_set
*set_project_out_unnamed_params(
1570 __isl_take isl_set
*set
)
1574 n
= isl_set_dim(set
, isl_dim_param
);
1575 for (i
= n
- 1; i
>= 0; --i
) {
1576 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1578 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1584 /* Update the context with respect to an embedding into a loop
1585 * with iteration domain "dom" and induction variable "id".
1586 * "iv_map" maps a possibly virtual iterator (used in "dom")
1587 * to the real iterator (parameter "id").
1589 * If the current context is independent of "id", we don't need
1591 * Otherwise, a parameter value is invalid for the embedding if
1592 * any of the corresponding iterator values is invalid.
1593 * That is, a parameter value is valid only if all the corresponding
1594 * iterator values are valid.
1595 * We therefore compute the set of parameters
1597 * forall i in dom : valid (i)
1601 * not exists i in dom : not valid(i)
1605 * not exists i in dom \ valid(i)
1607 * Before we subtract valid(i) from dom, we first need to map
1608 * the real iterator to the virtual iterator.
1610 * If there are any unnamed parameters in "dom", then we consider
1611 * a parameter value to be valid if it is valid for any value of those
1612 * unnamed parameters. They are therefore projected out at the end.
1614 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1615 __isl_keep isl_set
*dom
, __isl_keep isl_map
*iv_map
,
1616 __isl_keep isl_id
*id
)
1620 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1624 context
= isl_set_from_params(context
);
1625 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1626 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1627 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1628 context
= isl_set_apply(context
, isl_map_reverse(isl_map_copy(iv_map
)));
1629 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1630 context
= isl_set_params(context
);
1631 context
= isl_set_complement(context
);
1632 context
= set_project_out_unnamed_params(context
);
1636 /* Embed all statements and arrays in "scop" in an extra outer loop
1637 * with iteration domain "dom" and schedule "sched".
1638 * "id" represents the induction variable of the loop.
1639 * "iv_map" maps a possibly virtual iterator to the real iterator.
1640 * That is, it maps the iterator used in "dom" and the domain of "sched"
1641 * to the iterator that some of the parameters in "scop" may refer to.
1643 * Any skip conditions within the loop have no effect outside of the loop.
1644 * The caller is responsible for making sure skip[pet_skip_later] has been
1645 * taken into account.
1647 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1648 __isl_take isl_map
*sched
, __isl_take isl_map
*iv_map
,
1649 __isl_take isl_id
*id
)
1656 pet_scop_reset_skip(scop
, pet_skip_now
);
1657 pet_scop_reset_skip(scop
, pet_skip_later
);
1659 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1663 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1664 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1665 isl_set_copy(dom
), isl_map_copy(sched
),
1666 isl_map_copy(iv_map
), isl_id_copy(id
));
1667 if (!scop
->stmts
[i
])
1671 for (i
= 0; i
< scop
->n_array
; ++i
) {
1672 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1674 if (!scop
->arrays
[i
])
1679 isl_map_free(sched
);
1680 isl_map_free(iv_map
);
1685 isl_map_free(sched
);
1686 isl_map_free(iv_map
);
1688 return pet_scop_free(scop
);
1691 /* Add extra conditions on the parameters to iteration domain of "stmt".
1693 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1694 __isl_take isl_set
*cond
)
1699 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1704 return pet_stmt_free(stmt
);
1707 /* Add extra conditions to scop->skip[type].
1709 * The new skip condition only holds if it held before
1710 * and the condition is true. It does not hold if it did not hold
1711 * before or the condition is false.
1713 * The skip condition is assumed to be an affine expression.
1715 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1716 enum pet_skip type
, __isl_keep isl_set
*cond
)
1718 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1724 if (!ext
->skip
[type
])
1727 if (!set_is_affine(ext
->skip
[type
]))
1728 isl_die(isl_set_get_ctx(ext
->skip
[type
]), isl_error_internal
,
1729 "can only resrict affine skips",
1730 return pet_scop_free(scop
));
1732 skip
= ext
->skip
[type
];
1733 skip
= isl_set_intersect_params(skip
, isl_set_copy(cond
));
1734 set
= isl_set_from_params(isl_set_copy(cond
));
1735 set
= isl_set_complement(set
);
1736 set
= isl_set_add_dims(set
, isl_dim_set
, 1);
1737 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 0);
1738 skip
= isl_set_union(skip
, set
);
1739 ext
->skip
[type
] = skip
;
1740 if (!ext
->skip
[type
])
1741 return pet_scop_free(scop
);
1746 /* Add extra conditions on the parameters to all iteration domains
1747 * and skip conditions.
1749 * A parameter value is valid for the result if it was valid
1750 * for the original scop and satisfies "cond" or if it does
1751 * not satisfy "cond" as in this case the scop is not executed
1752 * and the original constraints on the parameters are irrelevant.
1754 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1755 __isl_take isl_set
*cond
)
1759 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1760 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1765 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1766 scop
->context
= isl_set_union(scop
->context
,
1767 isl_set_complement(isl_set_copy(cond
)));
1768 scop
->context
= isl_set_coalesce(scop
->context
);
1769 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1773 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1774 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1775 isl_set_copy(cond
));
1776 if (!scop
->stmts
[i
])
1784 return pet_scop_free(scop
);
1787 /* Construct a map that inserts a filter value with name "id" and value
1788 * "satisfied" in the list of filter values embedded in the set space "space".
1790 * If "space" does not contain any filter values yet, we first create
1791 * a map that inserts 0 filter values, i.e.,
1793 * space -> [space -> []]
1795 * We can now assume that space is of the form [dom -> [filters]]
1796 * We construct an identity mapping on dom and a mapping on filters
1797 * that inserts the new filter
1800 * [filters] -> [satisfied, filters]
1802 * and then compute the cross product
1804 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1806 static __isl_give isl_map
*insert_filter_map(__isl_take isl_space
*space
,
1807 __isl_take isl_id
*id
, int satisfied
)
1810 isl_map
*map
, *map_dom
, *map_ran
;
1813 if (isl_space_is_wrapping(space
)) {
1814 space2
= isl_space_map_from_set(isl_space_copy(space
));
1815 map
= isl_map_identity(space2
);
1816 space
= isl_space_unwrap(space
);
1818 space
= isl_space_from_domain(space
);
1819 map
= isl_map_universe(isl_space_copy(space
));
1820 map
= isl_map_reverse(isl_map_domain_map(map
));
1823 space2
= isl_space_domain(isl_space_copy(space
));
1824 map_dom
= isl_map_identity(isl_space_map_from_set(space2
));
1825 space
= isl_space_range(space
);
1826 map_ran
= isl_map_identity(isl_space_map_from_set(space
));
1827 map_ran
= isl_map_insert_dims(map_ran
, isl_dim_out
, 0, 1);
1828 map_ran
= isl_map_set_dim_id(map_ran
, isl_dim_out
, 0, id
);
1829 map_ran
= isl_map_fix_si(map_ran
, isl_dim_out
, 0, satisfied
);
1831 map
= isl_map_apply_range(map
, isl_map_product(map_dom
, map_ran
));
1836 /* Insert an argument expression corresponding to "test" in front
1837 * of the list of arguments described by *n_arg and *args.
1839 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
1840 __isl_keep isl_map
*test
)
1843 isl_ctx
*ctx
= isl_map_get_ctx(test
);
1849 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1853 struct pet_expr
**ext
;
1854 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
1857 for (i
= 0; i
< *n_arg
; ++i
)
1858 ext
[1 + i
] = (*args
)[i
];
1863 (*args
)[0] = pet_expr_from_access(isl_map_copy(test
));
1870 /* Make the expression "expr" depend on the value of "test"
1871 * being equal to "satisfied".
1873 * If "test" is an affine expression, we simply add the conditions
1874 * on the expression have the value "satisfied" to all access relations.
1876 * Otherwise, we add a filter to "expr" (which is then assumed to be
1877 * an access expression) corresponding to "test" being equal to "satisfied".
1879 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
1880 __isl_take isl_map
*test
, int satisfied
)
1890 if (!isl_map_has_tuple_id(test
, isl_dim_out
)) {
1891 test
= isl_map_fix_si(test
, isl_dim_out
, 0, satisfied
);
1892 return pet_expr_restrict(expr
, isl_map_params(test
));
1895 ctx
= isl_map_get_ctx(test
);
1896 if (expr
->type
!= pet_expr_access
)
1897 isl_die(ctx
, isl_error_invalid
,
1898 "can only filter access expressions", goto error
);
1900 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
1901 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1902 map
= insert_filter_map(space
, id
, satisfied
);
1904 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, map
);
1905 if (!expr
->acc
.access
)
1908 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
1915 return pet_expr_free(expr
);
1918 /* Make the statement "stmt" depend on the value of "test"
1919 * being equal to "satisfied" by adjusting stmt->domain.
1921 * The domain of "test" corresponds to the (zero or more) outer dimensions
1922 * of the iteration domain.
1924 * We insert an argument corresponding to a read to "test"
1925 * from the iteration domain of "stmt" in front of the list of arguments.
1926 * We also insert a corresponding output dimension in the wrapped
1927 * map contained in stmt->domain, with value set to "satisfied".
1929 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1930 __isl_take isl_map
*test
, int satisfied
)
1935 isl_map
*map
, *add_dom
;
1943 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1944 map
= insert_filter_map(isl_set_get_space(stmt
->domain
), id
, satisfied
);
1945 stmt
->domain
= isl_set_apply(stmt
->domain
, map
);
1947 space
= isl_space_unwrap(isl_set_get_space(stmt
->domain
));
1948 dom
= isl_set_universe(isl_space_domain(space
));
1949 n_test_dom
= isl_map_dim(test
, isl_dim_in
);
1950 add_dom
= isl_map_from_range(dom
);
1951 add_dom
= isl_map_add_dims(add_dom
, isl_dim_in
, n_test_dom
);
1952 for (i
= 0; i
< n_test_dom
; ++i
)
1953 add_dom
= isl_map_equate(add_dom
, isl_dim_in
, i
,
1955 test
= isl_map_apply_domain(test
, add_dom
);
1957 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1964 return pet_stmt_free(stmt
);
1967 /* Does "scop" have a skip condition of the given "type"?
1969 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1971 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1975 return ext
->skip
[type
] != NULL
;
1978 /* Does "scop" have a skip condition of the given "type" that
1979 * is an affine expression?
1981 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1983 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1987 if (!ext
->skip
[type
])
1989 return set_is_affine(ext
->skip
[type
]);
1992 /* Does "scop" have a skip condition of the given "type" that
1993 * is not an affine expression?
1995 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1997 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2002 if (!ext
->skip
[type
])
2004 aff
= set_is_affine(ext
->skip
[type
]);
2010 /* Does "scop" have a skip condition of the given "type" that
2011 * is affine and holds on the entire domain?
2013 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2015 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2020 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2021 if (is_aff
< 0 || !is_aff
)
2024 set
= isl_set_copy(ext
->skip
[type
]);
2025 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 1);
2026 set
= isl_set_params(set
);
2027 is_univ
= isl_set_plain_is_universe(set
);
2033 /* Replace scop->skip[type] by "skip".
2035 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2036 enum pet_skip type
, __isl_take isl_set
*skip
)
2038 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2043 isl_set_free(ext
->skip
[type
]);
2044 ext
->skip
[type
] = skip
;
2049 return pet_scop_free(scop
);
2052 /* Return a copy of scop->skip[type].
2054 __isl_give isl_set
*pet_scop_get_skip(struct pet_scop
*scop
,
2057 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2062 return isl_set_copy(ext
->skip
[type
]);
2065 /* Return a map to the skip condition of the given type.
2067 __isl_give isl_map
*pet_scop_get_skip_map(struct pet_scop
*scop
,
2070 return isl_map_from_range(pet_scop_get_skip(scop
, type
));
2073 /* Return an access pet_expr corresponding to the skip condition
2074 * of the given type.
2076 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2079 return pet_expr_from_access(pet_scop_get_skip_map(scop
, type
));
2082 /* Drop the the skip condition scop->skip[type].
2084 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2086 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2091 isl_set_free(ext
->skip
[type
]);
2092 ext
->skip
[type
] = NULL
;
2095 /* Make the skip condition (if any) depend on the value of "test" being
2096 * equal to "satisfied".
2098 * We only support the case where the original skip condition is universal,
2099 * i.e., where skipping is unconditional, and where satisfied == 1.
2100 * In this case, the skip condition is changed to skip only when
2101 * "test" is equal to one.
2103 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2104 enum pet_skip type
, __isl_keep isl_map
*test
, int satisfied
)
2110 if (!pet_scop_has_skip(scop
, type
))
2114 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2116 return pet_scop_free(scop
);
2117 if (satisfied
&& is_univ
) {
2118 scop
= pet_scop_set_skip(scop
, type
,
2119 isl_map_range(isl_map_copy(test
)));
2123 isl_die(isl_map_get_ctx(test
), isl_error_internal
,
2124 "skip expression cannot be filtered",
2125 return pet_scop_free(scop
));
2131 /* Make all statements in "scop" depend on the value of "test"
2132 * being equal to "satisfied" by adjusting their domains.
2134 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2135 __isl_take isl_map
*test
, int satisfied
)
2139 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2140 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2145 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2146 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
2147 isl_map_copy(test
), satisfied
);
2148 if (!scop
->stmts
[i
])
2156 return pet_scop_free(scop
);
2159 /* Do the filters "i" and "j" always have the same value?
2161 static int equal_filter_values(__isl_keep isl_set
*domain
, int i
, int j
)
2163 isl_map
*map
, *test
;
2166 map
= isl_set_unwrap(isl_set_copy(domain
));
2167 test
= isl_map_universe(isl_map_get_space(map
));
2168 test
= isl_map_equate(test
, isl_dim_out
, i
, isl_dim_out
, j
);
2169 equal
= isl_map_is_subset(map
, test
);
2176 /* Merge filters "i" and "j" into a single filter ("i") with as filter
2177 * access relation, the union of the two access relations.
2179 static struct pet_stmt
*merge_filter_pair(struct pet_stmt
*stmt
, int i
, int j
)
2187 stmt
->args
[i
]->acc
.access
= isl_map_union(stmt
->args
[i
]->acc
.access
,
2188 isl_map_copy(stmt
->args
[j
]->acc
.access
));
2189 stmt
->args
[i
]->acc
.access
= isl_map_coalesce(stmt
->args
[i
]->acc
.access
);
2191 pet_expr_free(stmt
->args
[j
]);
2192 for (k
= j
; k
< stmt
->n_arg
- 1; ++k
)
2193 stmt
->args
[k
] = stmt
->args
[k
+ 1];
2196 map
= isl_set_unwrap(stmt
->domain
);
2197 map
= isl_map_project_out(map
, isl_dim_out
, j
, 1);
2198 stmt
->domain
= isl_map_wrap(map
);
2200 if (!stmt
->domain
|| !stmt
->args
[i
]->acc
.access
)
2201 return pet_stmt_free(stmt
);
2206 /* Look for any pair of filters that access the same filter variable
2207 * and that have the same filter value and merge them into a single
2208 * filter with as filter access relation the union of the filter access
2211 static struct pet_stmt
*stmt_merge_filters(struct pet_stmt
*stmt
)
2214 isl_space
*space_i
, *space_j
;
2218 if (stmt
->n_arg
<= 1)
2221 for (i
= 0; i
< stmt
->n_arg
- 1; ++i
) {
2222 if (stmt
->args
[i
]->type
!= pet_expr_access
)
2224 if (pet_expr_is_affine(stmt
->args
[i
]))
2227 space_i
= isl_map_get_space(stmt
->args
[i
]->acc
.access
);
2229 for (j
= stmt
->n_arg
- 1; j
> i
; --j
) {
2232 if (stmt
->args
[j
]->type
!= pet_expr_access
)
2234 if (pet_expr_is_affine(stmt
->args
[j
]))
2237 space_j
= isl_map_get_space(stmt
->args
[j
]->acc
.access
);
2239 eq
= isl_space_is_equal(space_i
, space_j
);
2241 eq
= equal_filter_values(stmt
->domain
, i
, j
);
2243 stmt
= merge_filter_pair(stmt
, i
, j
);
2245 isl_space_free(space_j
);
2247 if (eq
< 0 || !stmt
)
2251 isl_space_free(space_i
);
2254 return pet_stmt_free(stmt
);
2260 /* Look for any pair of filters that access the same filter variable
2261 * and that have the same filter value and merge them into a single
2262 * filter with as filter access relation the union of the filter access
2265 struct pet_scop
*pet_scop_merge_filters(struct pet_scop
*scop
)
2272 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2273 scop
->stmts
[i
] = stmt_merge_filters(scop
->stmts
[i
]);
2274 if (!scop
->stmts
[i
])
2275 return pet_scop_free(scop
);
2281 /* Add all parameters in "expr" to "dim" and return the result.
2283 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2284 __isl_take isl_space
*dim
)
2290 for (i
= 0; i
< expr
->n_arg
; ++i
)
2292 dim
= expr_collect_params(expr
->args
[i
], dim
);
2294 if (expr
->type
== pet_expr_access
)
2295 dim
= isl_space_align_params(dim
,
2296 isl_map_get_space(expr
->acc
.access
));
2300 isl_space_free(dim
);
2301 return pet_expr_free(expr
);
2304 /* Add all parameters in "stmt" to "dim" and return the result.
2306 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2307 __isl_take isl_space
*dim
)
2312 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2313 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2314 dim
= expr_collect_params(stmt
->body
, dim
);
2318 isl_space_free(dim
);
2319 return pet_stmt_free(stmt
);
2322 /* Add all parameters in "array" to "dim" and return the result.
2324 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2325 __isl_take isl_space
*dim
)
2330 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2331 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2335 pet_array_free(array
);
2336 return isl_space_free(dim
);
2339 /* Add all parameters in "scop" to "dim" and return the result.
2341 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2342 __isl_take isl_space
*dim
)
2349 for (i
= 0; i
< scop
->n_array
; ++i
)
2350 dim
= array_collect_params(scop
->arrays
[i
], dim
);
2352 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2353 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
2357 isl_space_free(dim
);
2358 return pet_scop_free(scop
);
2361 /* Add all parameters in "dim" to all access relations in "expr".
2363 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
2364 __isl_take isl_space
*dim
)
2371 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2373 expr_propagate_params(expr
->args
[i
],
2374 isl_space_copy(dim
));
2379 if (expr
->type
== pet_expr_access
) {
2380 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
2381 isl_space_copy(dim
));
2382 if (!expr
->acc
.access
)
2386 isl_space_free(dim
);
2389 isl_space_free(dim
);
2390 return pet_expr_free(expr
);
2393 /* Add all parameters in "dim" to the domain, schedule and
2394 * all access relations in "stmt".
2396 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2397 __isl_take isl_space
*dim
)
2402 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
2403 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2404 isl_space_copy(dim
));
2405 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
2407 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2410 isl_space_free(dim
);
2413 isl_space_free(dim
);
2414 return pet_stmt_free(stmt
);
2417 /* Add all parameters in "dim" to "array".
2419 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2420 __isl_take isl_space
*dim
)
2425 array
->context
= isl_set_align_params(array
->context
,
2426 isl_space_copy(dim
));
2427 array
->extent
= isl_set_align_params(array
->extent
,
2428 isl_space_copy(dim
));
2429 if (array
->value_bounds
) {
2430 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2431 isl_space_copy(dim
));
2432 if (!array
->value_bounds
)
2436 if (!array
->context
|| !array
->extent
)
2439 isl_space_free(dim
);
2442 isl_space_free(dim
);
2443 return pet_array_free(array
);
2446 /* Add all parameters in "dim" to "scop".
2448 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2449 __isl_take isl_space
*dim
)
2456 for (i
= 0; i
< scop
->n_array
; ++i
) {
2457 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2458 isl_space_copy(dim
));
2459 if (!scop
->arrays
[i
])
2463 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2464 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2465 isl_space_copy(dim
));
2466 if (!scop
->stmts
[i
])
2470 isl_space_free(dim
);
2473 isl_space_free(dim
);
2474 return pet_scop_free(scop
);
2477 /* Update all isl_sets and isl_maps in "scop" such that they all
2478 * have the same parameters.
2480 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2487 dim
= isl_set_get_space(scop
->context
);
2488 dim
= scop_collect_params(scop
, dim
);
2490 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
2491 scop
= scop_propagate_params(scop
, dim
);
2496 /* Check if the given access relation accesses a (0D) array that corresponds
2497 * to one of the parameters in "dim". If so, replace the array access
2498 * by an access to the set of integers with as index (and value)
2501 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
2502 __isl_take isl_space
*dim
)
2504 isl_id
*array_id
= NULL
;
2507 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
2508 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2509 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
2511 isl_space_free(dim
);
2514 isl_id_free(array_id
);
2518 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
2520 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
2521 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
2524 isl_id_free(array_id
);
2526 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2527 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
2532 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2533 * in "dim" by a value equal to the corresponding parameter.
2535 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
2536 __isl_take isl_space
*dim
)
2543 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2545 expr_detect_parameter_accesses(expr
->args
[i
],
2546 isl_space_copy(dim
));
2551 if (expr
->type
== pet_expr_access
) {
2552 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
2553 isl_space_copy(dim
));
2554 if (!expr
->acc
.access
)
2558 isl_space_free(dim
);
2561 isl_space_free(dim
);
2562 return pet_expr_free(expr
);
2565 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2566 * in "dim" by a value equal to the corresponding parameter.
2568 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2569 __isl_take isl_space
*dim
)
2574 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
2575 isl_space_copy(dim
));
2577 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2580 isl_space_free(dim
);
2583 isl_space_free(dim
);
2584 return pet_stmt_free(stmt
);
2587 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2588 * in "dim" by a value equal to the corresponding parameter.
2590 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2591 __isl_take isl_space
*dim
)
2598 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2599 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2600 isl_space_copy(dim
));
2601 if (!scop
->stmts
[i
])
2605 isl_space_free(dim
);
2608 isl_space_free(dim
);
2609 return pet_scop_free(scop
);
2612 /* Replace all accesses to (0D) arrays that correspond to any of
2613 * the parameters used in "scop" by a value equal
2614 * to the corresponding parameter.
2616 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2623 dim
= isl_set_get_space(scop
->context
);
2624 dim
= scop_collect_params(scop
, dim
);
2626 scop
= scop_detect_parameter_accesses(scop
, dim
);
2631 /* Add all read access relations (if "read" is set) and/or all write
2632 * access relations (if "write" is set) to "accesses" and return the result.
2634 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
2635 int read
, int write
, __isl_take isl_union_map
*accesses
)
2644 for (i
= 0; i
< expr
->n_arg
; ++i
)
2645 accesses
= expr_collect_accesses(expr
->args
[i
],
2646 read
, write
, accesses
);
2648 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2649 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
2650 accesses
= isl_union_map_add_map(accesses
,
2651 isl_map_copy(expr
->acc
.access
));
2656 /* Collect and return all read access relations (if "read" is set)
2657 * and/or all write access relations (if "write" is set) in "stmt".
2659 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2660 int read
, int write
, __isl_take isl_space
*dim
)
2662 isl_union_map
*accesses
;
2667 accesses
= isl_union_map_empty(dim
);
2668 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
2669 accesses
= isl_union_map_intersect_domain(accesses
,
2670 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
2675 /* Collect and return all read access relations (if "read" is set)
2676 * and/or all write access relations (if "write" is set) in "scop".
2678 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2679 int read
, int write
)
2682 isl_union_map
*accesses
;
2687 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2689 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2690 isl_union_map
*accesses_i
;
2691 isl_space
*dim
= isl_set_get_space(scop
->context
);
2692 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
2694 accesses
= isl_union_map_union(accesses
, accesses_i
);
2700 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
2702 return scop_collect_accesses(scop
, 1, 0);
2705 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
2707 return scop_collect_accesses(scop
, 0, 1);
2710 /* Collect and return the union of iteration domains in "scop".
2712 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2716 isl_union_set
*domain
;
2721 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2723 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2724 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2725 domain
= isl_union_set_add_set(domain
, domain_i
);
2731 /* Collect and return the schedules of the statements in "scop".
2732 * The range is normalized to the maximal number of scheduling
2735 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2738 isl_map
*schedule_i
;
2739 isl_union_map
*schedule
;
2740 int depth
, max_depth
= 0;
2745 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2747 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2748 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2749 if (depth
> max_depth
)
2753 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2754 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2755 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2756 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2758 for (j
= depth
; j
< max_depth
; ++j
)
2759 schedule_i
= isl_map_fix_si(schedule_i
,
2761 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2767 /* Does expression "expr" write to "id"?
2769 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
2774 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2775 int writes
= expr_writes(expr
->args
[i
], id
);
2776 if (writes
< 0 || writes
)
2780 if (expr
->type
!= pet_expr_access
)
2782 if (!expr
->acc
.write
)
2784 if (pet_expr_is_affine(expr
))
2787 write_id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
2788 isl_id_free(write_id
);
2793 return write_id
== id
;
2796 /* Does statement "stmt" write to "id"?
2798 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
2800 return expr_writes(stmt
->body
, id
);
2803 /* Is there any write access in "scop" that accesses "id"?
2805 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
2812 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2813 int writes
= stmt_writes(scop
->stmts
[i
], id
);
2814 if (writes
< 0 || writes
)
2821 /* Add a reference identifier to access expression "expr".
2822 * "user" points to an integer that contains the sequence number
2823 * of the next reference.
2825 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
2834 ctx
= isl_map_get_ctx(expr
->acc
.access
);
2835 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
2836 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
2837 if (!expr
->acc
.ref_id
)
2838 return pet_expr_free(expr
);
2843 /* Add a reference identifier to all access expressions in "stmt".
2844 * "n_ref" points to an integer that contains the sequence number
2845 * of the next reference.
2847 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2854 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2855 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
2856 &access_add_ref_id
, n_ref
);
2858 return pet_stmt_free(stmt
);
2861 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_add_ref_id
, n_ref
);
2863 return pet_stmt_free(stmt
);
2868 /* Add a reference identifier to all access expressions in "scop".
2870 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2879 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2880 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2881 if (!scop
->stmts
[i
])
2882 return pet_scop_free(scop
);
2888 /* Reset the user pointer on the tuple id and all parameter ids in "set".
2890 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
2894 n
= isl_set_dim(set
, isl_dim_param
);
2895 for (i
= 0; i
< n
; ++i
) {
2896 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
2897 const char *name
= isl_id_get_name(id
);
2898 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
2902 if (!isl_set_is_params(set
) && isl_set_has_tuple_id(set
)) {
2903 isl_id
*id
= isl_set_get_tuple_id(set
);
2904 const char *name
= isl_id_get_name(id
);
2905 set
= isl_set_set_tuple_name(set
, name
);
2912 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
2914 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
2918 n
= isl_map_dim(map
, isl_dim_param
);
2919 for (i
= 0; i
< n
; ++i
) {
2920 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
2921 const char *name
= isl_id_get_name(id
);
2922 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
2926 if (isl_map_has_tuple_id(map
, isl_dim_in
)) {
2927 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_in
);
2928 const char *name
= isl_id_get_name(id
);
2929 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
2933 if (isl_map_has_tuple_id(map
, isl_dim_out
)) {
2934 isl_id
*id
= isl_map_get_tuple_id(map
, isl_dim_out
);
2935 const char *name
= isl_id_get_name(id
);
2936 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
2943 /* Reset the user pointer on all parameter ids in "array".
2945 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2950 array
->context
= set_anonymize(array
->context
);
2951 array
->extent
= set_anonymize(array
->extent
);
2952 if (!array
->context
|| !array
->extent
)
2953 return pet_array_free(array
);
2958 /* Reset the user pointer on all parameter and tuple ids in
2959 * the access relation of the access expression "expr".
2961 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
2963 expr
->acc
.access
= map_anonymize(expr
->acc
.access
);
2964 if (!expr
->acc
.access
)
2965 return pet_expr_free(expr
);
2970 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2972 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2981 stmt
->domain
= set_anonymize(stmt
->domain
);
2982 stmt
->schedule
= map_anonymize(stmt
->schedule
);
2983 if (!stmt
->domain
|| !stmt
->schedule
)
2984 return pet_stmt_free(stmt
);
2986 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2987 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
2988 &access_anonymize
, NULL
);
2990 return pet_stmt_free(stmt
);
2993 stmt
->body
= pet_expr_map_access(stmt
->body
,
2994 &access_anonymize
, NULL
);
2996 return pet_stmt_free(stmt
);
3001 /* Reset the user pointer on all parameter and tuple ids in "scop".
3003 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3010 scop
->context
= set_anonymize(scop
->context
);
3011 scop
->context_value
= set_anonymize(scop
->context_value
);
3012 if (!scop
->context
|| !scop
->context_value
)
3013 return pet_scop_free(scop
);
3015 for (i
= 0; i
< scop
->n_array
; ++i
) {
3016 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3017 if (!scop
->arrays
[i
])
3018 return pet_scop_free(scop
);
3021 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3022 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3023 if (!scop
->stmts
[i
])
3024 return pet_scop_free(scop
);
3030 /* Given a set "domain", return a wrapped relation with the given set
3031 * as domain and a range of dimension "n_arg", where each coordinate
3032 * is either unbounded or, if the corresponding element of args is of
3033 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3035 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
3036 unsigned n_arg
, struct pet_expr
**args
,
3037 __isl_keep isl_union_map
*value_bounds
)
3042 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
3044 map
= isl_map_from_domain(domain
);
3045 space
= isl_map_get_space(map
);
3046 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
3048 for (i
= 0; i
< n_arg
; ++i
) {
3050 struct pet_expr
*arg
= args
[i
];
3054 map_i
= isl_map_universe(isl_space_copy(space
));
3055 if (arg
->type
== pet_expr_access
) {
3057 id
= isl_map_get_tuple_id(arg
->acc
.access
, isl_dim_out
);
3058 space2
= isl_space_alloc(ctx
, 0, 0, 1);
3059 space2
= isl_space_set_tuple_id(space2
, isl_dim_in
, id
);
3060 vb
= isl_union_map_extract_map(value_bounds
, space2
);
3061 if (!isl_map_plain_is_empty(vb
))
3062 map_i
= isl_map_intersect_range(map_i
,
3067 map
= isl_map_flat_range_product(map
, map_i
);
3069 isl_space_free(space
);
3071 return isl_map_wrap(map
);
3074 /* Data used in access_gist() callback.
3076 struct pet_access_gist_data
{
3078 isl_union_map
*value_bounds
;
3081 /* Given an expression "expr" of type pet_expr_access, compute
3082 * the gist of the associated access relation with respect to
3083 * data->domain and the bounds on the values of the arguments
3084 * of the expression.
3086 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3088 struct pet_access_gist_data
*data
= user
;
3091 domain
= isl_set_copy(data
->domain
);
3092 if (expr
->n_arg
> 0)
3093 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3094 data
->value_bounds
);
3096 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
3097 if (!expr
->acc
.access
)
3098 return pet_expr_free(expr
);
3103 /* Compute the gist of the iteration domain and all access relations
3104 * of "stmt" based on the constraints on the parameters specified by "context"
3105 * and the constraints on the values of nested accesses specified
3106 * by "value_bounds".
3108 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3109 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3114 struct pet_access_gist_data data
;
3119 data
.domain
= isl_set_copy(stmt
->domain
);
3120 data
.value_bounds
= value_bounds
;
3121 if (stmt
->n_arg
> 0)
3122 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3124 data
.domain
= isl_set_intersect_params(data
.domain
,
3125 isl_set_copy(context
));
3127 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3128 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3129 &access_gist
, &data
);
3134 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3138 isl_set_free(data
.domain
);
3140 space
= isl_set_get_space(stmt
->domain
);
3141 if (isl_space_is_wrapping(space
))
3142 space
= isl_space_domain(isl_space_unwrap(space
));
3143 domain
= isl_set_universe(space
);
3144 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3145 if (stmt
->n_arg
> 0)
3146 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3148 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3150 return pet_stmt_free(stmt
);
3154 isl_set_free(data
.domain
);
3155 return pet_stmt_free(stmt
);
3158 /* Compute the gist of the extent of the array
3159 * based on the constraints on the parameters specified by "context".
3161 static struct pet_array
*array_gist(struct pet_array
*array
,
3162 __isl_keep isl_set
*context
)
3167 array
->extent
= isl_set_gist_params(array
->extent
,
3168 isl_set_copy(context
));
3170 return pet_array_free(array
);
3175 /* Compute the gist of all sets and relations in "scop"
3176 * based on the constraints on the parameters specified by "scop->context"
3177 * and the constraints on the values of nested accesses specified
3178 * by "value_bounds".
3180 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3181 __isl_keep isl_union_map
*value_bounds
)
3188 scop
->context
= isl_set_coalesce(scop
->context
);
3190 return pet_scop_free(scop
);
3192 for (i
= 0; i
< scop
->n_array
; ++i
) {
3193 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3194 if (!scop
->arrays
[i
])
3195 return pet_scop_free(scop
);
3198 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3199 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3201 if (!scop
->stmts
[i
])
3202 return pet_scop_free(scop
);
3208 /* Intersect the context of "scop" with "context".
3209 * To ensure that we don't introduce any unnamed parameters in
3210 * the context of "scop", we first remove the unnamed parameters
3213 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3214 __isl_take isl_set
*context
)
3219 context
= set_project_out_unnamed_params(context
);
3220 scop
->context
= isl_set_intersect(scop
->context
, context
);
3222 return pet_scop_free(scop
);
3226 isl_set_free(context
);
3227 return pet_scop_free(scop
);
3230 /* Drop the current context of "scop". That is, replace the context
3231 * by a universal set.
3233 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3240 space
= isl_set_get_space(scop
->context
);
3241 isl_set_free(scop
->context
);
3242 scop
->context
= isl_set_universe(space
);
3244 return pet_scop_free(scop
);
3249 /* Append "array" to the arrays of "scop".
3251 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3252 struct pet_array
*array
)
3255 struct pet_array
**arrays
;
3257 if (!array
|| !scop
)
3260 ctx
= isl_set_get_ctx(scop
->context
);
3261 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3265 scop
->arrays
= arrays
;
3266 scop
->arrays
[scop
->n_array
] = array
;
3271 pet_array_free(array
);
3272 return pet_scop_free(scop
);