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
35 #include <isl/constraint.h>
36 #include <isl/union_set.h>
40 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
42 static char *type_str
[] = {
43 [pet_expr_access
] = "access",
44 [pet_expr_call
] = "call",
45 [pet_expr_double
] = "double",
46 [pet_expr_unary
] = "unary",
47 [pet_expr_binary
] = "binary",
48 [pet_expr_ternary
] = "ternary"
51 static char *op_str
[] = {
52 [pet_op_add_assign
] = "+=",
53 [pet_op_sub_assign
] = "-=",
54 [pet_op_mul_assign
] = "*=",
55 [pet_op_div_assign
] = "/=",
56 [pet_op_assign
] = "=",
67 [pet_op_post_inc
] = "++",
68 [pet_op_post_dec
] = "--",
69 [pet_op_pre_inc
] = "++",
70 [pet_op_pre_dec
] = "--",
71 [pet_op_address_of
] = "&"
74 /* pet_scop with extra information that is only used during parsing.
76 * In particular, we keep track of conditions under which we want
77 * to skip the rest of the current loop iteration (skip[pet_skip_now])
78 * and of conditions under which we want to skip subsequent
79 * loop iterations (skip[pet_skip_later]).
81 * The conditions are represented either by a variable, which
82 * is assumed to attain values zero and one, or by a boolean affine
83 * expression. The condition holds if the variable has value one
84 * or if the affine expression has value one (typically for only
85 * part of the parameter space).
87 * A missing condition (skip[type] == NULL) means that we don't want
96 const char *pet_op_str(enum pet_op_type op
)
101 int pet_op_is_inc_dec(enum pet_op_type op
)
103 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
104 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
107 const char *pet_type_str(enum pet_expr_type type
)
109 return type_str
[type
];
112 enum pet_op_type
pet_str_op(const char *str
)
116 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
117 if (!strcmp(op_str
[i
], str
))
123 enum pet_expr_type
pet_str_type(const char *str
)
127 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
128 if (!strcmp(type_str
[i
], str
))
134 /* Construct a pet_expr from an access relation.
135 * By default, it is considered to be a read access.
137 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
139 isl_ctx
*ctx
= isl_map_get_ctx(access
);
140 struct pet_expr
*expr
;
144 expr
= isl_calloc_type(ctx
, struct pet_expr
);
148 expr
->type
= pet_expr_access
;
149 expr
->acc
.access
= access
;
155 isl_map_free(access
);
159 /* Construct a unary pet_expr that performs "op" on "arg".
161 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
162 struct pet_expr
*arg
)
164 struct pet_expr
*expr
;
168 expr
= isl_alloc_type(ctx
, struct pet_expr
);
172 expr
->type
= pet_expr_unary
;
175 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
178 expr
->args
[pet_un_arg
] = arg
;
186 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
188 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
189 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
191 struct pet_expr
*expr
;
195 expr
= isl_alloc_type(ctx
, struct pet_expr
);
199 expr
->type
= pet_expr_binary
;
202 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
205 expr
->args
[pet_bin_lhs
] = lhs
;
206 expr
->args
[pet_bin_rhs
] = rhs
;
215 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
217 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
218 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
220 struct pet_expr
*expr
;
222 if (!cond
|| !lhs
|| !rhs
)
224 expr
= isl_alloc_type(ctx
, struct pet_expr
);
228 expr
->type
= pet_expr_ternary
;
230 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
233 expr
->args
[pet_ter_cond
] = cond
;
234 expr
->args
[pet_ter_true
] = lhs
;
235 expr
->args
[pet_ter_false
] = rhs
;
245 /* Construct a call pet_expr that calls function "name" with "n_arg"
246 * arguments. The caller is responsible for filling in the arguments.
248 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
251 struct pet_expr
*expr
;
253 expr
= isl_alloc_type(ctx
, struct pet_expr
);
257 expr
->type
= pet_expr_call
;
259 expr
->name
= strdup(name
);
260 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
261 if (!expr
->name
|| !expr
->args
)
262 return pet_expr_free(expr
);
267 /* Construct a pet_expr that represents the double "d".
269 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
271 struct pet_expr
*expr
;
273 expr
= isl_calloc_type(ctx
, struct pet_expr
);
277 expr
->type
= pet_expr_double
;
283 void *pet_expr_free(struct pet_expr
*expr
)
290 for (i
= 0; i
< expr
->n_arg
; ++i
)
291 pet_expr_free(expr
->args
[i
]);
294 switch (expr
->type
) {
295 case pet_expr_access
:
296 isl_map_free(expr
->acc
.access
);
301 case pet_expr_double
:
303 case pet_expr_binary
:
304 case pet_expr_ternary
:
312 static void expr_dump(struct pet_expr
*expr
, int indent
)
319 fprintf(stderr
, "%*s", indent
, "");
321 switch (expr
->type
) {
322 case pet_expr_double
:
323 fprintf(stderr
, "%g\n", expr
->d
);
325 case pet_expr_access
:
326 isl_map_dump(expr
->acc
.access
);
327 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
329 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
330 "", expr
->acc
.write
);
331 for (i
= 0; i
< expr
->n_arg
; ++i
)
332 expr_dump(expr
->args
[i
], indent
+ 2);
335 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
336 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
338 case pet_expr_binary
:
339 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
340 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
341 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
343 case pet_expr_ternary
:
344 fprintf(stderr
, "?:\n");
345 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
346 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
347 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
350 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
351 for (i
= 0; i
< expr
->n_arg
; ++i
)
352 expr_dump(expr
->args
[i
], indent
+ 2);
357 void pet_expr_dump(struct pet_expr
*expr
)
362 /* Does "expr" represent an access to an unnamed space, i.e.,
363 * does it represent an affine expression?
365 int pet_expr_is_affine(struct pet_expr
*expr
)
371 if (expr
->type
!= pet_expr_access
)
374 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
381 /* Return 1 if the two pet_exprs are equivalent.
383 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
387 if (!expr1
|| !expr2
)
390 if (expr1
->type
!= expr2
->type
)
392 if (expr1
->n_arg
!= expr2
->n_arg
)
394 for (i
= 0; i
< expr1
->n_arg
; ++i
)
395 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
397 switch (expr1
->type
) {
398 case pet_expr_double
:
399 if (expr1
->d
!= expr2
->d
)
402 case pet_expr_access
:
403 if (expr1
->acc
.read
!= expr2
->acc
.read
)
405 if (expr1
->acc
.write
!= expr2
->acc
.write
)
407 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
409 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
413 case pet_expr_binary
:
414 case pet_expr_ternary
:
415 if (expr1
->op
!= expr2
->op
)
419 if (strcmp(expr1
->name
, expr2
->name
))
427 /* Add extra conditions on the parameters to all access relations in "expr".
429 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
430 __isl_take isl_set
*cond
)
437 for (i
= 0; i
< expr
->n_arg
; ++i
) {
438 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
444 if (expr
->type
== pet_expr_access
) {
445 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
447 if (!expr
->acc
.access
)
455 return pet_expr_free(expr
);
458 /* Modify all access relations in "expr" by calling "fn" on them.
460 struct pet_expr
*pet_expr_foreach_access(struct pet_expr
*expr
,
461 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
469 for (i
= 0; i
< expr
->n_arg
; ++i
) {
470 expr
->args
[i
] = pet_expr_foreach_access(expr
->args
[i
], fn
, user
);
472 return pet_expr_free(expr
);
475 if (expr
->type
== pet_expr_access
) {
476 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
477 if (!expr
->acc
.access
)
478 return pet_expr_free(expr
);
484 /* Modify all expressions of type pet_expr_access in "expr"
485 * by calling "fn" on them.
487 struct pet_expr
*pet_expr_foreach_access_expr(struct pet_expr
*expr
,
488 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
496 for (i
= 0; i
< expr
->n_arg
; ++i
) {
497 expr
->args
[i
] = pet_expr_foreach_access_expr(expr
->args
[i
],
500 return pet_expr_free(expr
);
503 if (expr
->type
== pet_expr_access
)
504 expr
= fn(expr
, user
);
509 /* Modify the given access relation based on the given iteration space
511 * If the access has any arguments then the domain of the access relation
512 * is a wrapped mapping from the iteration space to the space of
513 * argument values. We only need to change the domain of this wrapped
514 * mapping, so we extend the input transformation with an identity mapping
515 * on the space of argument values.
517 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
520 isl_map
*update
= user
;
523 update
= isl_map_copy(update
);
525 dim
= isl_map_get_space(access
);
526 dim
= isl_space_domain(dim
);
527 if (!isl_space_is_wrapping(dim
))
531 dim
= isl_space_unwrap(dim
);
532 dim
= isl_space_range(dim
);
533 dim
= isl_space_map_from_set(dim
);
534 id
= isl_map_identity(dim
);
535 update
= isl_map_product(update
, id
);
538 return isl_map_apply_domain(access
, update
);
541 /* Modify all access relations in "expr" based on the given iteration space
544 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
545 __isl_take isl_map
*update
)
547 expr
= pet_expr_foreach_access(expr
, &update_domain
, update
);
548 isl_map_free(update
);
552 /* Construct a pet_stmt with given line number and statement
553 * number from a pet_expr.
554 * The initial iteration domain is the zero-dimensional universe.
555 * The name of the domain is given by "label" if it is non-NULL.
556 * Otherwise, the name is constructed as S_<id>.
557 * The domains of all access relations are modified to refer
558 * to the statement iteration domain.
560 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
561 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
563 struct pet_stmt
*stmt
;
573 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
577 dim
= isl_space_set_alloc(ctx
, 0, 0);
579 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
581 snprintf(name
, sizeof(name
), "S_%d", id
);
582 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
584 dom
= isl_set_universe(isl_space_copy(dim
));
585 sched
= isl_map_from_domain(isl_set_copy(dom
));
587 dim
= isl_space_from_range(dim
);
588 add_name
= isl_map_universe(dim
);
589 expr
= expr_update_domain(expr
, add_name
);
593 stmt
->schedule
= sched
;
596 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
597 return pet_stmt_free(stmt
);
602 return pet_expr_free(expr
);
605 void *pet_stmt_free(struct pet_stmt
*stmt
)
612 isl_set_free(stmt
->domain
);
613 isl_map_free(stmt
->schedule
);
614 pet_expr_free(stmt
->body
);
616 for (i
= 0; i
< stmt
->n_arg
; ++i
)
617 pet_expr_free(stmt
->args
[i
]);
624 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
631 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
632 fprintf(stderr
, "%*s", indent
, "");
633 isl_set_dump(stmt
->domain
);
634 fprintf(stderr
, "%*s", indent
, "");
635 isl_map_dump(stmt
->schedule
);
636 expr_dump(stmt
->body
, indent
);
637 for (i
= 0; i
< stmt
->n_arg
; ++i
)
638 expr_dump(stmt
->args
[i
], indent
+ 2);
641 void pet_stmt_dump(struct pet_stmt
*stmt
)
646 struct pet_array
*pet_array_free(struct pet_array
*array
)
651 isl_set_free(array
->context
);
652 isl_set_free(array
->extent
);
653 isl_set_free(array
->value_bounds
);
654 free(array
->element_type
);
660 void pet_array_dump(struct pet_array
*array
)
665 isl_set_dump(array
->context
);
666 isl_set_dump(array
->extent
);
667 isl_set_dump(array
->value_bounds
);
668 fprintf(stderr
, "%s %s\n", array
->element_type
,
669 array
->live_out
? "live-out" : "");
672 /* Alloc a pet_scop structure, with extra room for information that
673 * is only used during parsing.
675 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
677 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
680 /* Construct a pet_scop with room for n statements.
682 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
685 struct pet_scop
*scop
;
687 scop
= pet_scop_alloc(ctx
);
691 space
= isl_space_params_alloc(ctx
, 0);
692 scop
->context
= isl_set_universe(isl_space_copy(space
));
693 scop
->context_value
= isl_set_universe(space
);
694 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
695 if (!scop
->context
|| !scop
->stmts
)
696 return pet_scop_free(scop
);
703 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
705 return scop_alloc(ctx
, 0);
708 /* Update "context" with respect to the valid parameter values for "access".
710 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
711 __isl_take isl_set
*context
)
713 context
= isl_set_intersect(context
,
714 isl_map_params(isl_map_copy(access
)));
718 /* Update "context" with respect to the valid parameter values for "expr".
720 * If "expr" represents a ternary operator, then a parameter value
721 * needs to be valid for the condition and for at least one of the
722 * remaining two arguments.
723 * If the condition is an affine expression, then we can be a bit more specific.
724 * The parameter then has to be valid for the second argument for
725 * non-zero accesses and valid for the third argument for zero accesses.
727 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
728 __isl_take isl_set
*context
)
732 if (expr
->type
== pet_expr_ternary
) {
734 isl_set
*context1
, *context2
;
736 is_aff
= pet_expr_is_affine(expr
->args
[0]);
740 context
= expr_extract_context(expr
->args
[0], context
);
741 context1
= expr_extract_context(expr
->args
[1],
742 isl_set_copy(context
));
743 context2
= expr_extract_context(expr
->args
[2], context
);
749 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
750 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
751 zero_set
= isl_map_params(access
);
752 context1
= isl_set_subtract(context1
,
753 isl_set_copy(zero_set
));
754 context2
= isl_set_intersect(context2
, zero_set
);
757 context
= isl_set_union(context1
, context2
);
758 context
= isl_set_coalesce(context
);
763 for (i
= 0; i
< expr
->n_arg
; ++i
)
764 context
= expr_extract_context(expr
->args
[i
], context
);
766 if (expr
->type
== pet_expr_access
)
767 context
= access_extract_context(expr
->acc
.access
, context
);
771 isl_set_free(context
);
775 /* Update "context" with respect to the valid parameter values for "stmt".
777 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
778 __isl_take isl_set
*context
)
782 for (i
= 0; i
< stmt
->n_arg
; ++i
)
783 context
= expr_extract_context(stmt
->args
[i
], context
);
785 context
= expr_extract_context(stmt
->body
, context
);
790 /* Construct a pet_scop that contains the given pet_stmt.
792 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
794 struct pet_scop
*scop
;
799 scop
= scop_alloc(ctx
, 1);
801 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
805 scop
->stmts
[0] = stmt
;
814 /* Does "set" represent an element of an unnamed space, i.e.,
815 * does it represent an affine expression?
817 static int set_is_affine(__isl_keep isl_set
*set
)
821 has_id
= isl_set_has_tuple_id(set
);
828 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
829 * ext may be equal to either ext1 or ext2.
831 * The two skips that need to be combined are assumed to be affine expressions.
833 * We need to skip in ext if we need to skip in either ext1 or ext2.
834 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
836 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
837 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
840 isl_set
*set
, *skip1
, *skip2
;
844 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
846 if (!ext1
->skip
[type
]) {
849 ext
->skip
[type
] = ext2
->skip
[type
];
850 ext2
->skip
[type
] = NULL
;
853 if (!ext2
->skip
[type
]) {
856 ext
->skip
[type
] = ext1
->skip
[type
];
857 ext1
->skip
[type
] = NULL
;
861 if (!set_is_affine(ext1
->skip
[type
]) ||
862 !set_is_affine(ext2
->skip
[type
]))
863 isl_die(isl_set_get_ctx(ext1
->skip
[type
]), isl_error_internal
,
864 "can only combine affine skips",
865 return pet_scop_free(&ext
->scop
));
867 skip1
= isl_set_copy(ext1
->skip
[type
]);
868 skip2
= isl_set_copy(ext2
->skip
[type
]);
869 set
= isl_set_intersect(
870 isl_set_fix_si(isl_set_copy(skip1
), isl_dim_set
, 0, 0),
871 isl_set_fix_si(isl_set_copy(skip2
), isl_dim_set
, 0, 0));
872 set
= isl_set_union(set
, isl_set_fix_si(skip1
, isl_dim_set
, 0, 1));
873 set
= isl_set_union(set
, isl_set_fix_si(skip2
, isl_dim_set
, 0, 1));
874 set
= isl_set_coalesce(set
);
875 isl_set_free(ext1
->skip
[type
]);
876 ext1
->skip
[type
] = NULL
;
877 isl_set_free(ext2
->skip
[type
]);
878 ext2
->skip
[type
] = NULL
;
879 ext
->skip
[type
] = set
;
880 if (!ext
->skip
[type
])
881 return pet_scop_free(&ext
->scop
);
886 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
887 * where type takes on the values pet_skip_now and pet_skip_later.
888 * scop may be equal to either scop1 or scop2.
890 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
891 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
893 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
894 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
895 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
897 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
898 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
902 /* Construct a pet_scop that contains the arrays, statements and
903 * skip information in "scop1" and "scop2".
905 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
906 struct pet_scop
*scop2
)
909 struct pet_scop
*scop
;
911 if (!scop1
|| !scop2
)
914 if (scop1
->n_stmt
== 0) {
915 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
916 pet_scop_free(scop1
);
920 if (scop2
->n_stmt
== 0) {
921 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
922 pet_scop_free(scop2
);
926 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
930 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
931 scop1
->n_array
+ scop2
->n_array
);
934 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
936 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
937 scop
->stmts
[i
] = scop1
->stmts
[i
];
938 scop1
->stmts
[i
] = NULL
;
941 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
942 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
943 scop2
->stmts
[i
] = NULL
;
946 for (i
= 0; i
< scop1
->n_array
; ++i
) {
947 scop
->arrays
[i
] = scop1
->arrays
[i
];
948 scop1
->arrays
[i
] = NULL
;
951 for (i
= 0; i
< scop2
->n_array
; ++i
) {
952 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
953 scop2
->arrays
[i
] = NULL
;
956 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
957 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
958 scop
= scop_combine_skips(scop
, scop1
, scop2
);
960 pet_scop_free(scop1
);
961 pet_scop_free(scop2
);
964 pet_scop_free(scop1
);
965 pet_scop_free(scop2
);
969 /* Apply the skip condition "skip" to "scop".
970 * That is, make sure "scop" is not executed when the condition holds.
972 * If "skip" is an affine expression, we add the conditions under
973 * which the expression is zero to the iteration domains.
974 * Otherwise, we add a filter on the variable attaining the value zero.
976 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
977 __isl_take isl_set
*skip
)
985 is_aff
= set_is_affine(skip
);
990 return pet_scop_filter(scop
, isl_map_from_range(skip
), 0);
992 skip
= isl_set_fix_si(skip
, isl_dim_set
, 0, 0);
993 scop
= pet_scop_restrict(scop
, isl_set_params(skip
));
998 return pet_scop_free(scop
);
1001 /* Construct a pet_scop that contains the arrays, statements and
1002 * skip information in "scop1" and "scop2", where the two scops
1003 * are executed "in sequence". That is, breaks and continues
1004 * in scop1 have an effect on scop2.
1006 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1007 struct pet_scop
*scop2
)
1009 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
1010 scop2
= restrict_skip(scop2
,
1011 pet_scop_get_skip(scop1
, pet_skip_now
));
1012 return pet_scop_add(ctx
, scop1
, scop2
);
1015 /* Construct a pet_scop that contains the arrays, statements and
1016 * skip information in "scop1" and "scop2", where the two scops
1017 * are executed "in parallel". That is, any break or continue
1018 * in scop1 has no effect on scop2.
1020 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
1021 struct pet_scop
*scop2
)
1023 return pet_scop_add(ctx
, scop1
, scop2
);
1026 void *pet_scop_free(struct pet_scop
*scop
)
1029 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1033 isl_set_free(scop
->context
);
1034 isl_set_free(scop
->context_value
);
1036 for (i
= 0; i
< scop
->n_array
; ++i
)
1037 pet_array_free(scop
->arrays
[i
]);
1040 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1041 pet_stmt_free(scop
->stmts
[i
]);
1043 isl_set_free(ext
->skip
[pet_skip_now
]);
1044 isl_set_free(ext
->skip
[pet_skip_later
]);
1049 void pet_scop_dump(struct pet_scop
*scop
)
1052 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1057 isl_set_dump(scop
->context
);
1058 isl_set_dump(scop
->context_value
);
1059 for (i
= 0; i
< scop
->n_array
; ++i
)
1060 pet_array_dump(scop
->arrays
[i
]);
1061 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1062 pet_stmt_dump(scop
->stmts
[i
]);
1065 fprintf(stderr
, "skip\n");
1066 isl_set_dump(ext
->skip
[0]);
1067 isl_set_dump(ext
->skip
[1]);
1071 /* Return 1 if the two pet_arrays are equivalent.
1073 * We don't compare element_size as this may be target dependent.
1075 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1077 if (!array1
|| !array2
)
1080 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1082 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1084 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1086 if (array1
->value_bounds
&&
1087 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1089 if (strcmp(array1
->element_type
, array2
->element_type
))
1091 if (array1
->live_out
!= array2
->live_out
)
1093 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1099 /* Return 1 if the two pet_stmts are equivalent.
1101 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1105 if (!stmt1
|| !stmt2
)
1108 if (stmt1
->line
!= stmt2
->line
)
1110 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1112 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1114 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
1116 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1118 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1119 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1126 /* Return 1 if the two pet_scops are equivalent.
1128 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1132 if (!scop1
|| !scop2
)
1135 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1137 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1140 if (scop1
->n_array
!= scop2
->n_array
)
1142 for (i
= 0; i
< scop1
->n_array
; ++i
)
1143 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1146 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1148 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1149 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1155 /* Prefix the schedule of "stmt" with an extra dimension with constant
1158 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1163 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1164 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1165 if (!stmt
->schedule
)
1166 return pet_stmt_free(stmt
);
1171 /* Prefix the schedules of all statements in "scop" with an extra
1172 * dimension with constant value "pos".
1174 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1181 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1182 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1183 if (!scop
->stmts
[i
])
1184 return pet_scop_free(scop
);
1190 /* Given a set with a parameter at "param_pos" that refers to the
1191 * iterator, "move" the iterator to the first set dimension.
1192 * That is, essentially equate the parameter to the first set dimension
1193 * and then project it out.
1195 * The first set dimension may however refer to a virtual iterator,
1196 * while the parameter refers to the "real" iterator.
1197 * We therefore need to take into account the mapping "iv_map", which
1198 * maps the virtual iterator to the real iterator.
1199 * In particular, we equate the set dimension to the input of the map
1200 * and the parameter to the output of the map and then project out
1201 * everything we don't need anymore.
1203 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1204 int param_pos
, __isl_take isl_map
*iv_map
)
1207 map
= isl_map_from_domain(set
);
1208 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1209 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1210 iv_map
= isl_map_align_params(iv_map
, isl_map_get_space(map
));
1211 map
= isl_map_apply_range(map
, iv_map
);
1212 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1213 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1214 return isl_map_domain(map
);
1217 /* Data used in embed_access.
1218 * extend adds an iterator to the iteration domain
1219 * iv_map maps the virtual iterator to the real iterator
1220 * var_id represents the induction variable of the corresponding loop
1222 struct pet_embed_access
{
1228 /* Embed the access relation in an extra outer loop.
1230 * We first update the iteration domain to insert the extra dimension.
1232 * If the access refers to the induction variable, then it is
1233 * turned into an access to the set of integers with index (and value)
1234 * equal to the induction variable.
1236 * If the induction variable appears in the constraints (as a parameter),
1237 * then the parameter is equated to the newly introduced iteration
1238 * domain dimension and subsequently projected out.
1240 * Similarly, if the accessed array is a virtual array (with user
1241 * pointer equal to NULL), as created by create_test_access,
1242 * then it is extended along with the domain of the access.
1244 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
1247 struct pet_embed_access
*data
= user
;
1248 isl_id
*array_id
= NULL
;
1251 access
= update_domain(access
, data
->extend
);
1253 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1254 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1255 if (array_id
== data
->var_id
||
1256 (array_id
&& !isl_id_get_user(array_id
))) {
1257 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1258 access
= isl_map_equate(access
,
1259 isl_dim_in
, 0, isl_dim_out
, 0);
1260 if (array_id
== data
->var_id
)
1261 access
= isl_map_apply_range(access
,
1262 isl_map_copy(data
->iv_map
));
1264 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1265 isl_id_copy(array_id
));
1267 isl_id_free(array_id
);
1269 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1271 isl_set
*set
= isl_map_wrap(access
);
1272 set
= internalize_iv(set
, pos
, isl_map_copy(data
->iv_map
));
1273 access
= isl_set_unwrap(set
);
1275 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1276 isl_id_copy(data
->var_id
));
1281 /* Embed all access relations in "expr" in an extra loop.
1282 * "extend" inserts an outer loop iterator in the iteration domains.
1283 * "iv_map" maps the virtual iterator to the real iterator
1284 * "var_id" represents the induction variable.
1286 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1287 __isl_take isl_map
*extend
, __isl_take isl_map
*iv_map
,
1288 __isl_keep isl_id
*var_id
)
1290 struct pet_embed_access data
=
1291 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1293 expr
= pet_expr_foreach_access(expr
, &embed_access
, &data
);
1294 isl_map_free(iv_map
);
1295 isl_map_free(extend
);
1299 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1300 * "dom" and schedule "sched". "var_id" represents the induction variable
1301 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1302 * That is, it maps the iterator used in "dom" and the domain of "sched"
1303 * to the iterator that some of the parameters in "stmt" may refer to.
1305 * The iteration domain and schedule of the statement are updated
1306 * according to the iteration domain and schedule of the new loop.
1307 * If stmt->domain is a wrapped map, then the iteration domain
1308 * is the domain of this map, so we need to be careful to adjust
1311 * If the induction variable appears in the constraints (as a parameter)
1312 * of the current iteration domain or the schedule of the statement,
1313 * then the parameter is equated to the newly introduced iteration
1314 * domain dimension and subsequently projected out.
1316 * Finally, all access relations are updated based on the extra loop.
1318 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1319 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1320 __isl_take isl_map
*iv_map
, __isl_take isl_id
*var_id
)
1331 if (isl_set_is_wrapping(stmt
->domain
)) {
1336 map
= isl_set_unwrap(stmt
->domain
);
1337 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1338 ran_dim
= isl_space_range(isl_map_get_space(map
));
1339 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1340 isl_set_universe(ran_dim
));
1341 map
= isl_map_flat_domain_product(ext
, map
);
1342 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1343 isl_id_copy(stmt_id
));
1344 dim
= isl_space_domain(isl_map_get_space(map
));
1345 stmt
->domain
= isl_map_wrap(map
);
1347 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1348 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1350 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1351 isl_id_copy(stmt_id
));
1352 dim
= isl_set_get_space(stmt
->domain
);
1355 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1357 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1358 isl_map_copy(iv_map
));
1360 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1361 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1362 isl_dim_in
, stmt_id
);
1364 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1366 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1367 set
= internalize_iv(set
, pos
, isl_map_copy(iv_map
));
1368 stmt
->schedule
= isl_set_unwrap(set
);
1371 dim
= isl_space_map_from_set(dim
);
1372 extend
= isl_map_identity(dim
);
1373 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1374 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1375 isl_map_get_tuple_id(extend
, isl_dim_out
));
1376 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1377 stmt
->args
[i
] = expr_embed(stmt
->args
[i
], isl_map_copy(extend
),
1378 isl_map_copy(iv_map
), var_id
);
1379 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1382 isl_id_free(var_id
);
1384 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1386 return pet_stmt_free(stmt
);
1387 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1388 return pet_stmt_free(stmt
);
1392 isl_map_free(sched
);
1393 isl_map_free(iv_map
);
1394 isl_id_free(var_id
);
1398 /* Embed the given pet_array in an extra outer loop with iteration domain
1400 * This embedding only has an effect on virtual arrays (those with
1401 * user pointer equal to NULL), which need to be extended along with
1402 * the iteration domain.
1404 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1405 __isl_take isl_set
*dom
)
1407 isl_id
*array_id
= NULL
;
1412 if (isl_set_has_tuple_id(array
->extent
))
1413 array_id
= isl_set_get_tuple_id(array
->extent
);
1415 if (array_id
&& !isl_id_get_user(array_id
)) {
1416 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1417 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1420 isl_id_free(array_id
);
1429 /* Project out all unnamed parameters from "set" and return the result.
1431 static __isl_give isl_set
*set_project_out_unnamed_params(
1432 __isl_take isl_set
*set
)
1436 n
= isl_set_dim(set
, isl_dim_param
);
1437 for (i
= n
- 1; i
>= 0; --i
) {
1438 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1440 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1446 /* Update the context with respect to an embedding into a loop
1447 * with iteration domain "dom" and induction variable "id".
1448 * "iv_map" maps a possibly virtual iterator (used in "dom")
1449 * to the real iterator (parameter "id").
1451 * If the current context is independent of "id", we don't need
1453 * Otherwise, a parameter value is invalid for the embedding if
1454 * any of the corresponding iterator values is invalid.
1455 * That is, a parameter value is valid only if all the corresponding
1456 * iterator values are valid.
1457 * We therefore compute the set of parameters
1459 * forall i in dom : valid (i)
1463 * not exists i in dom : not valid(i)
1467 * not exists i in dom \ valid(i)
1469 * Before we subtract valid(i) from dom, we first need to map
1470 * the real iterator to the virtual iterator.
1472 * If there are any unnamed parameters in "dom", then we consider
1473 * a parameter value to be valid if it is valid for any value of those
1474 * unnamed parameters. They are therefore projected out at the end.
1476 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1477 __isl_keep isl_set
*dom
, __isl_keep isl_map
*iv_map
,
1478 __isl_keep isl_id
*id
)
1482 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1486 context
= isl_set_from_params(context
);
1487 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1488 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1489 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1490 context
= isl_set_apply(context
, isl_map_reverse(isl_map_copy(iv_map
)));
1491 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1492 context
= isl_set_params(context
);
1493 context
= isl_set_complement(context
);
1494 context
= set_project_out_unnamed_params(context
);
1498 /* Embed all statements and arrays in "scop" in an extra outer loop
1499 * with iteration domain "dom" and schedule "sched".
1500 * "id" represents the induction variable of the loop.
1501 * "iv_map" maps a possibly virtual iterator to the real iterator.
1502 * That is, it maps the iterator used in "dom" and the domain of "sched"
1503 * to the iterator that some of the parameters in "scop" may refer to.
1505 * Any skip conditions within the loop have no effect outside of the loop.
1506 * The caller is responsible for making sure skip[pet_skip_later] has been
1507 * taken into account.
1509 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1510 __isl_take isl_map
*sched
, __isl_take isl_map
*iv_map
,
1511 __isl_take isl_id
*id
)
1518 pet_scop_reset_skip(scop
, pet_skip_now
);
1519 pet_scop_reset_skip(scop
, pet_skip_later
);
1521 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1525 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1526 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1527 isl_set_copy(dom
), isl_map_copy(sched
),
1528 isl_map_copy(iv_map
), isl_id_copy(id
));
1529 if (!scop
->stmts
[i
])
1533 for (i
= 0; i
< scop
->n_array
; ++i
) {
1534 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1536 if (!scop
->arrays
[i
])
1541 isl_map_free(sched
);
1542 isl_map_free(iv_map
);
1547 isl_map_free(sched
);
1548 isl_map_free(iv_map
);
1550 return pet_scop_free(scop
);
1553 /* Add extra conditions on the parameters to iteration domain of "stmt".
1555 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1556 __isl_take isl_set
*cond
)
1561 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1566 return pet_stmt_free(stmt
);
1569 /* Add extra conditions to scop->skip[type].
1571 * The new skip condition only holds if it held before
1572 * and the condition is true. It does not hold if it did not hold
1573 * before or the condition is false.
1575 * The skip condition is assumed to be an affine expression.
1577 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1578 enum pet_skip type
, __isl_keep isl_set
*cond
)
1580 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1586 if (!ext
->skip
[type
])
1589 if (!set_is_affine(ext
->skip
[type
]))
1590 isl_die(isl_set_get_ctx(ext
->skip
[type
]), isl_error_internal
,
1591 "can only resrict affine skips",
1592 return pet_scop_free(scop
));
1594 skip
= ext
->skip
[type
];
1595 skip
= isl_set_intersect_params(skip
, isl_set_copy(cond
));
1596 set
= isl_set_from_params(isl_set_copy(cond
));
1597 set
= isl_set_complement(set
);
1598 set
= isl_set_add_dims(set
, isl_dim_set
, 1);
1599 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 0);
1600 skip
= isl_set_union(skip
, set
);
1601 ext
->skip
[type
] = skip
;
1602 if (!ext
->skip
[type
])
1603 return pet_scop_free(scop
);
1608 /* Add extra conditions on the parameters to all iteration domains
1609 * and skip conditions.
1611 * A parameter value is valid for the result if it was valid
1612 * for the original scop and satisfies "cond" or if it does
1613 * not satisfy "cond" as in this case the scop is not executed
1614 * and the original constraints on the parameters are irrelevant.
1616 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1617 __isl_take isl_set
*cond
)
1621 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1622 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1627 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1628 scop
->context
= isl_set_union(scop
->context
,
1629 isl_set_complement(isl_set_copy(cond
)));
1630 scop
->context
= isl_set_coalesce(scop
->context
);
1631 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1635 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1636 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1637 isl_set_copy(cond
));
1638 if (!scop
->stmts
[i
])
1646 return pet_scop_free(scop
);
1649 /* Construct a map that inserts a filter value with name "id" and value
1650 * "satisfied" in the list of filter values embedded in the set space "space".
1652 * If "space" does not contain any filter values yet, we first create
1653 * a map that inserts 0 filter values, i.e.,
1655 * space -> [space -> []]
1657 * We can now assume that space is of the form [dom -> [filters]]
1658 * We construct an identity mapping on dom and a mapping on filters
1659 * that inserts the new filter
1662 * [filters] -> [satisfied, filters]
1664 * and then compute the cross product
1666 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1668 static __isl_give isl_map
*insert_filter_map(__isl_take isl_space
*space
,
1669 __isl_take isl_id
*id
, int satisfied
)
1672 isl_map
*map
, *map_dom
, *map_ran
;
1675 if (isl_space_is_wrapping(space
)) {
1676 space2
= isl_space_map_from_set(isl_space_copy(space
));
1677 map
= isl_map_identity(space2
);
1678 space
= isl_space_unwrap(space
);
1680 space
= isl_space_from_domain(space
);
1681 map
= isl_map_universe(isl_space_copy(space
));
1682 map
= isl_map_reverse(isl_map_domain_map(map
));
1685 space2
= isl_space_domain(isl_space_copy(space
));
1686 map_dom
= isl_map_identity(isl_space_map_from_set(space2
));
1687 space
= isl_space_range(space
);
1688 map_ran
= isl_map_identity(isl_space_map_from_set(space
));
1689 map_ran
= isl_map_insert_dims(map_ran
, isl_dim_out
, 0, 1);
1690 map_ran
= isl_map_set_dim_id(map_ran
, isl_dim_out
, 0, id
);
1691 map_ran
= isl_map_fix_si(map_ran
, isl_dim_out
, 0, satisfied
);
1693 map
= isl_map_apply_range(map
, isl_map_product(map_dom
, map_ran
));
1698 /* Insert an argument expression corresponding to "test" in front
1699 * of the list of arguments described by *n_arg and *args.
1701 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
1702 __isl_keep isl_map
*test
)
1705 isl_ctx
*ctx
= isl_map_get_ctx(test
);
1711 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1715 struct pet_expr
**ext
;
1716 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
1719 for (i
= 0; i
< *n_arg
; ++i
)
1720 ext
[1 + i
] = (*args
)[i
];
1725 (*args
)[0] = pet_expr_from_access(isl_map_copy(test
));
1732 /* Make the expression "expr" depend on the value of "test"
1733 * being equal to "satisfied".
1735 * If "test" is an affine expression, we simply add the conditions
1736 * on the expression have the value "satisfied" to all access relations.
1738 * Otherwise, we add a filter to "expr" (which is then assumed to be
1739 * an access expression) corresponding to "test" being equal to "satisfied".
1741 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
1742 __isl_take isl_map
*test
, int satisfied
)
1752 if (!isl_map_has_tuple_id(test
, isl_dim_out
)) {
1753 test
= isl_map_fix_si(test
, isl_dim_out
, 0, satisfied
);
1754 return pet_expr_restrict(expr
, isl_map_params(test
));
1757 ctx
= isl_map_get_ctx(test
);
1758 if (expr
->type
!= pet_expr_access
)
1759 isl_die(ctx
, isl_error_invalid
,
1760 "can only filter access expressions", goto error
);
1762 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
1763 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1764 map
= insert_filter_map(space
, id
, satisfied
);
1766 expr
->acc
.access
= isl_map_apply_domain(expr
->acc
.access
, map
);
1767 if (!expr
->acc
.access
)
1770 if (args_insert_access(&expr
->n_arg
, &expr
->args
, test
) < 0)
1777 return pet_expr_free(expr
);
1780 /* Make the statement "stmt" depend on the value of "test"
1781 * being equal to "satisfied" by adjusting stmt->domain.
1783 * The domain of "test" corresponds to the (zero or more) outer dimensions
1784 * of the iteration domain.
1786 * We insert an argument corresponding to a read to "test"
1787 * from the iteration domain of "stmt" in front of the list of arguments.
1788 * We also insert a corresponding output dimension in the wrapped
1789 * map contained in stmt->domain, with value set to "satisfied".
1791 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1792 __isl_take isl_map
*test
, int satisfied
)
1797 isl_map
*map
, *add_dom
;
1805 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1806 map
= insert_filter_map(isl_set_get_space(stmt
->domain
), id
, satisfied
);
1807 stmt
->domain
= isl_set_apply(stmt
->domain
, map
);
1809 space
= isl_space_unwrap(isl_set_get_space(stmt
->domain
));
1810 dom
= isl_set_universe(isl_space_domain(space
));
1811 n_test_dom
= isl_map_dim(test
, isl_dim_in
);
1812 add_dom
= isl_map_from_range(dom
);
1813 add_dom
= isl_map_add_dims(add_dom
, isl_dim_in
, n_test_dom
);
1814 for (i
= 0; i
< n_test_dom
; ++i
)
1815 add_dom
= isl_map_equate(add_dom
, isl_dim_in
, i
,
1817 test
= isl_map_apply_domain(test
, add_dom
);
1819 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1826 return pet_stmt_free(stmt
);
1829 /* Does "scop" have a skip condition of the given "type"?
1831 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1833 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1837 return ext
->skip
[type
] != NULL
;
1840 /* Does "scop" have a skip condition of the given "type" that
1841 * is an affine expression?
1843 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1845 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1849 if (!ext
->skip
[type
])
1851 return set_is_affine(ext
->skip
[type
]);
1854 /* Does "scop" have a skip condition of the given "type" that
1855 * is not an affine expression?
1857 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1859 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1864 if (!ext
->skip
[type
])
1866 aff
= set_is_affine(ext
->skip
[type
]);
1872 /* Does "scop" have a skip condition of the given "type" that
1873 * is affine and holds on the entire domain?
1875 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
1877 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1882 is_aff
= pet_scop_has_affine_skip(scop
, type
);
1883 if (is_aff
< 0 || !is_aff
)
1886 set
= isl_set_copy(ext
->skip
[type
]);
1887 set
= isl_set_fix_si(set
, isl_dim_set
, 0, 1);
1888 set
= isl_set_params(set
);
1889 is_univ
= isl_set_plain_is_universe(set
);
1895 /* Replace scop->skip[type] by "skip".
1897 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
1898 enum pet_skip type
, __isl_take isl_set
*skip
)
1900 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1905 isl_set_free(ext
->skip
[type
]);
1906 ext
->skip
[type
] = skip
;
1911 return pet_scop_free(scop
);
1914 /* Return a copy of scop->skip[type].
1916 __isl_give isl_set
*pet_scop_get_skip(struct pet_scop
*scop
,
1919 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1924 return isl_set_copy(ext
->skip
[type
]);
1927 /* Return a map to the skip condition of the given type.
1929 __isl_give isl_map
*pet_scop_get_skip_map(struct pet_scop
*scop
,
1932 return isl_map_from_range(pet_scop_get_skip(scop
, type
));
1935 /* Return an access pet_expr corresponding to the skip condition
1936 * of the given type.
1938 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
1941 return pet_expr_from_access(pet_scop_get_skip_map(scop
, type
));
1944 /* Drop the the skip condition scop->skip[type].
1946 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
1948 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1953 isl_set_free(ext
->skip
[type
]);
1954 ext
->skip
[type
] = NULL
;
1957 /* Make the skip condition (if any) depend on the value of "test" being
1958 * equal to "satisfied".
1960 * We only support the case where the original skip condition is universal,
1961 * i.e., where skipping is unconditional, and where satisfied == 1.
1962 * In this case, the skip condition is changed to skip only when
1963 * "test" is equal to one.
1965 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
1966 enum pet_skip type
, __isl_keep isl_map
*test
, int satisfied
)
1972 if (!pet_scop_has_skip(scop
, type
))
1976 is_univ
= pet_scop_has_universal_skip(scop
, type
);
1978 return pet_scop_free(scop
);
1979 if (satisfied
&& is_univ
) {
1980 scop
= pet_scop_set_skip(scop
, type
,
1981 isl_map_range(isl_map_copy(test
)));
1985 isl_die(isl_map_get_ctx(test
), isl_error_internal
,
1986 "skip expression cannot be filtered",
1987 return pet_scop_free(scop
));
1993 /* Make all statements in "scop" depend on the value of "test"
1994 * being equal to "satisfied" by adjusting their domains.
1996 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1997 __isl_take isl_map
*test
, int satisfied
)
2001 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2002 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2007 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2008 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
2009 isl_map_copy(test
), satisfied
);
2010 if (!scop
->stmts
[i
])
2018 return pet_scop_free(scop
);
2021 /* Do the filters "i" and "j" always have the same value?
2023 static int equal_filter_values(__isl_keep isl_set
*domain
, int i
, int j
)
2025 isl_map
*map
, *test
;
2028 map
= isl_set_unwrap(isl_set_copy(domain
));
2029 test
= isl_map_universe(isl_map_get_space(map
));
2030 test
= isl_map_equate(test
, isl_dim_out
, i
, isl_dim_out
, j
);
2031 equal
= isl_map_is_subset(map
, test
);
2038 /* Merge filters "i" and "j" into a single filter ("i") with as filter
2039 * access relation, the union of the two access relations.
2041 static struct pet_stmt
*merge_filter_pair(struct pet_stmt
*stmt
, int i
, int j
)
2049 stmt
->args
[i
]->acc
.access
= isl_map_union(stmt
->args
[i
]->acc
.access
,
2050 isl_map_copy(stmt
->args
[j
]->acc
.access
));
2051 stmt
->args
[i
]->acc
.access
= isl_map_coalesce(stmt
->args
[i
]->acc
.access
);
2053 pet_expr_free(stmt
->args
[j
]);
2054 for (k
= j
; k
< stmt
->n_arg
- 1; ++k
)
2055 stmt
->args
[k
] = stmt
->args
[k
+ 1];
2058 map
= isl_set_unwrap(stmt
->domain
);
2059 map
= isl_map_project_out(map
, isl_dim_out
, j
, 1);
2060 stmt
->domain
= isl_map_wrap(map
);
2062 if (!stmt
->domain
|| !stmt
->args
[i
]->acc
.access
)
2063 return pet_stmt_free(stmt
);
2068 /* Look for any pair of filters that access the same filter variable
2069 * and that have the same filter value and merge them into a single
2070 * filter with as filter access relation the union of the filter access
2073 static struct pet_stmt
*stmt_merge_filters(struct pet_stmt
*stmt
)
2076 isl_space
*space_i
, *space_j
;
2080 if (stmt
->n_arg
<= 1)
2083 for (i
= 0; i
< stmt
->n_arg
- 1; ++i
) {
2084 if (stmt
->args
[i
]->type
!= pet_expr_access
)
2086 if (pet_expr_is_affine(stmt
->args
[i
]))
2089 space_i
= isl_map_get_space(stmt
->args
[i
]->acc
.access
);
2091 for (j
= stmt
->n_arg
- 1; j
> i
; --j
) {
2094 if (stmt
->args
[j
]->type
!= pet_expr_access
)
2096 if (pet_expr_is_affine(stmt
->args
[j
]))
2099 space_j
= isl_map_get_space(stmt
->args
[j
]->acc
.access
);
2101 eq
= isl_space_is_equal(space_i
, space_j
);
2103 eq
= equal_filter_values(stmt
->domain
, i
, j
);
2105 stmt
= merge_filter_pair(stmt
, i
, j
);
2107 isl_space_free(space_j
);
2109 if (eq
< 0 || !stmt
)
2113 isl_space_free(space_i
);
2116 return pet_stmt_free(stmt
);
2122 /* Look for any pair of filters that access the same filter variable
2123 * and that have the same filter value and merge them into a single
2124 * filter with as filter access relation the union of the filter access
2127 struct pet_scop
*pet_scop_merge_filters(struct pet_scop
*scop
)
2134 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2135 scop
->stmts
[i
] = stmt_merge_filters(scop
->stmts
[i
]);
2136 if (!scop
->stmts
[i
])
2137 return pet_scop_free(scop
);
2143 /* Add all parameters in "expr" to "dim" and return the result.
2145 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2146 __isl_take isl_space
*dim
)
2152 for (i
= 0; i
< expr
->n_arg
; ++i
)
2154 dim
= expr_collect_params(expr
->args
[i
], dim
);
2156 if (expr
->type
== pet_expr_access
)
2157 dim
= isl_space_align_params(dim
,
2158 isl_map_get_space(expr
->acc
.access
));
2162 isl_space_free(dim
);
2163 return pet_expr_free(expr
);
2166 /* Add all parameters in "stmt" to "dim" and return the result.
2168 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2169 __isl_take isl_space
*dim
)
2174 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
2175 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
2176 dim
= expr_collect_params(stmt
->body
, dim
);
2180 isl_space_free(dim
);
2181 return pet_stmt_free(stmt
);
2184 /* Add all parameters in "array" to "dim" and return the result.
2186 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2187 __isl_take isl_space
*dim
)
2192 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
2193 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
2197 pet_array_free(array
);
2198 return isl_space_free(dim
);
2201 /* Add all parameters in "scop" to "dim" and return the result.
2203 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2204 __isl_take isl_space
*dim
)
2211 for (i
= 0; i
< scop
->n_array
; ++i
)
2212 dim
= array_collect_params(scop
->arrays
[i
], dim
);
2214 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2215 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
2219 isl_space_free(dim
);
2220 return pet_scop_free(scop
);
2223 /* Add all parameters in "dim" to all access relations in "expr".
2225 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
2226 __isl_take isl_space
*dim
)
2233 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2235 expr_propagate_params(expr
->args
[i
],
2236 isl_space_copy(dim
));
2241 if (expr
->type
== pet_expr_access
) {
2242 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
2243 isl_space_copy(dim
));
2244 if (!expr
->acc
.access
)
2248 isl_space_free(dim
);
2251 isl_space_free(dim
);
2252 return pet_expr_free(expr
);
2255 /* Add all parameters in "dim" to the domain, schedule and
2256 * all access relations in "stmt".
2258 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2259 __isl_take isl_space
*dim
)
2264 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
2265 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2266 isl_space_copy(dim
));
2267 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
2269 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2272 isl_space_free(dim
);
2275 isl_space_free(dim
);
2276 return pet_stmt_free(stmt
);
2279 /* Add all parameters in "dim" to "array".
2281 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2282 __isl_take isl_space
*dim
)
2287 array
->context
= isl_set_align_params(array
->context
,
2288 isl_space_copy(dim
));
2289 array
->extent
= isl_set_align_params(array
->extent
,
2290 isl_space_copy(dim
));
2291 if (array
->value_bounds
) {
2292 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2293 isl_space_copy(dim
));
2294 if (!array
->value_bounds
)
2298 if (!array
->context
|| !array
->extent
)
2301 isl_space_free(dim
);
2304 isl_space_free(dim
);
2305 return pet_array_free(array
);
2308 /* Add all parameters in "dim" to "scop".
2310 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2311 __isl_take isl_space
*dim
)
2318 for (i
= 0; i
< scop
->n_array
; ++i
) {
2319 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2320 isl_space_copy(dim
));
2321 if (!scop
->arrays
[i
])
2325 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2326 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2327 isl_space_copy(dim
));
2328 if (!scop
->stmts
[i
])
2332 isl_space_free(dim
);
2335 isl_space_free(dim
);
2336 return pet_scop_free(scop
);
2339 /* Update all isl_sets and isl_maps in "scop" such that they all
2340 * have the same parameters.
2342 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2349 dim
= isl_set_get_space(scop
->context
);
2350 dim
= scop_collect_params(scop
, dim
);
2352 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
2353 scop
= scop_propagate_params(scop
, dim
);
2358 /* Check if the given access relation accesses a (0D) array that corresponds
2359 * to one of the parameters in "dim". If so, replace the array access
2360 * by an access to the set of integers with as index (and value)
2363 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
2364 __isl_take isl_space
*dim
)
2366 isl_id
*array_id
= NULL
;
2369 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
2370 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
2371 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
2373 isl_space_free(dim
);
2376 isl_id_free(array_id
);
2380 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
2382 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
2383 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
2386 isl_id_free(array_id
);
2388 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
2389 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
2394 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2395 * in "dim" by a value equal to the corresponding parameter.
2397 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
2398 __isl_take isl_space
*dim
)
2405 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2407 expr_detect_parameter_accesses(expr
->args
[i
],
2408 isl_space_copy(dim
));
2413 if (expr
->type
== pet_expr_access
) {
2414 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
2415 isl_space_copy(dim
));
2416 if (!expr
->acc
.access
)
2420 isl_space_free(dim
);
2423 isl_space_free(dim
);
2424 return pet_expr_free(expr
);
2427 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2428 * in "dim" by a value equal to the corresponding parameter.
2430 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2431 __isl_take isl_space
*dim
)
2436 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
2437 isl_space_copy(dim
));
2439 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2442 isl_space_free(dim
);
2445 isl_space_free(dim
);
2446 return pet_stmt_free(stmt
);
2449 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2450 * in "dim" by a value equal to the corresponding parameter.
2452 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2453 __isl_take isl_space
*dim
)
2460 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2461 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2462 isl_space_copy(dim
));
2463 if (!scop
->stmts
[i
])
2467 isl_space_free(dim
);
2470 isl_space_free(dim
);
2471 return pet_scop_free(scop
);
2474 /* Replace all accesses to (0D) arrays that correspond to any of
2475 * the parameters used in "scop" by a value equal
2476 * to the corresponding parameter.
2478 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2485 dim
= isl_set_get_space(scop
->context
);
2486 dim
= scop_collect_params(scop
, dim
);
2488 scop
= scop_detect_parameter_accesses(scop
, dim
);
2493 /* Add all read access relations (if "read" is set) and/or all write
2494 * access relations (if "write" is set) to "accesses" and return the result.
2496 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
2497 int read
, int write
, __isl_take isl_union_map
*accesses
)
2506 for (i
= 0; i
< expr
->n_arg
; ++i
)
2507 accesses
= expr_collect_accesses(expr
->args
[i
],
2508 read
, write
, accesses
);
2510 if (expr
->type
== pet_expr_access
&&
2511 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
2512 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
2513 accesses
= isl_union_map_add_map(accesses
,
2514 isl_map_copy(expr
->acc
.access
));
2519 /* Collect and return all read access relations (if "read" is set)
2520 * and/or all write * access relations (if "write" is set) in "stmt".
2522 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2523 int read
, int write
, __isl_take isl_space
*dim
)
2525 isl_union_map
*accesses
;
2530 accesses
= isl_union_map_empty(dim
);
2531 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
2532 accesses
= isl_union_map_intersect_domain(accesses
,
2533 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
2538 /* Collect and return all read access relations (if "read" is set)
2539 * and/or all write * access relations (if "write" is set) in "scop".
2541 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2542 int read
, int write
)
2545 isl_union_map
*accesses
;
2550 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2552 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2553 isl_union_map
*accesses_i
;
2554 isl_space
*dim
= isl_set_get_space(scop
->context
);
2555 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
2557 accesses
= isl_union_map_union(accesses
, accesses_i
);
2563 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
2565 return scop_collect_accesses(scop
, 1, 0);
2568 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
2570 return scop_collect_accesses(scop
, 0, 1);
2573 /* Collect and return the union of iteration domains in "scop".
2575 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2579 isl_union_set
*domain
;
2584 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2586 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2587 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2588 domain
= isl_union_set_add_set(domain
, domain_i
);
2594 /* Collect and return the schedules of the statements in "scop".
2595 * The range is normalized to the maximal number of scheduling
2598 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2601 isl_map
*schedule_i
;
2602 isl_union_map
*schedule
;
2603 int depth
, max_depth
= 0;
2608 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2610 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2611 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2612 if (depth
> max_depth
)
2616 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2617 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2618 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2619 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2621 for (j
= depth
; j
< max_depth
; ++j
)
2622 schedule_i
= isl_map_fix_si(schedule_i
,
2624 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2630 /* Does expression "expr" write to "id"?
2632 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
2637 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2638 int writes
= expr_writes(expr
->args
[i
], id
);
2639 if (writes
< 0 || writes
)
2643 if (expr
->type
!= pet_expr_access
)
2645 if (!expr
->acc
.write
)
2647 if (!isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
))
2650 write_id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
2651 isl_id_free(write_id
);
2656 return write_id
== id
;
2659 /* Does statement "stmt" write to "id"?
2661 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
2663 return expr_writes(stmt
->body
, id
);
2666 /* Is there any write access in "scop" that accesses "id"?
2668 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
2675 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2676 int writes
= stmt_writes(scop
->stmts
[i
], id
);
2677 if (writes
< 0 || writes
)
2684 /* Reset the user pointer on all parameter ids in "set".
2686 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
2690 n
= isl_set_dim(set
, isl_dim_param
);
2691 for (i
= 0; i
< n
; ++i
) {
2692 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
2693 const char *name
= isl_id_get_name(id
);
2694 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
2701 /* Reset the user pointer on all parameter ids in "map".
2703 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
2707 n
= isl_map_dim(map
, isl_dim_param
);
2708 for (i
= 0; i
< n
; ++i
) {
2709 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
2710 const char *name
= isl_id_get_name(id
);
2711 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
2718 /* Reset the user pointer on all parameter ids in "array".
2720 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2725 array
->context
= set_anonymize(array
->context
);
2726 array
->extent
= set_anonymize(array
->extent
);
2727 if (!array
->context
|| !array
->extent
)
2728 return pet_array_free(array
);
2733 /* Reset the user pointer on all parameter ids in "access".
2735 static __isl_give isl_map
*access_anonymize(__isl_take isl_map
*access
,
2738 access
= map_anonymize(access
);
2743 /* Reset the user pointer on all parameter ids in "stmt".
2745 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2754 stmt
->domain
= set_anonymize(stmt
->domain
);
2755 stmt
->schedule
= map_anonymize(stmt
->schedule
);
2756 if (!stmt
->domain
|| !stmt
->schedule
)
2757 return pet_stmt_free(stmt
);
2759 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2760 stmt
->args
[i
] = pet_expr_foreach_access(stmt
->args
[i
],
2761 &access_anonymize
, NULL
);
2763 return pet_stmt_free(stmt
);
2766 stmt
->body
= pet_expr_foreach_access(stmt
->body
,
2767 &access_anonymize
, NULL
);
2769 return pet_stmt_free(stmt
);
2774 /* Reset the user pointer on all parameter ids in "scop".
2776 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2783 scop
->context
= set_anonymize(scop
->context
);
2784 scop
->context_value
= set_anonymize(scop
->context_value
);
2785 if (!scop
->context
|| !scop
->context_value
)
2786 return pet_scop_free(scop
);
2788 for (i
= 0; i
< scop
->n_array
; ++i
) {
2789 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2790 if (!scop
->arrays
[i
])
2791 return pet_scop_free(scop
);
2794 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2795 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2796 if (!scop
->stmts
[i
])
2797 return pet_scop_free(scop
);
2803 /* Given a set "domain", return a wrapped relation with the given set
2804 * as domain and a range of dimension "n_arg", where each coordinate
2805 * is either unbounded or, if the corresponding element of args is of
2806 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2808 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
2809 unsigned n_arg
, struct pet_expr
**args
,
2810 __isl_keep isl_union_map
*value_bounds
)
2815 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
2817 map
= isl_map_from_domain(domain
);
2818 space
= isl_map_get_space(map
);
2819 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2821 for (i
= 0; i
< n_arg
; ++i
) {
2823 struct pet_expr
*arg
= args
[i
];
2827 map_i
= isl_map_universe(isl_space_copy(space
));
2828 if (arg
->type
== pet_expr_access
) {
2830 id
= isl_map_get_tuple_id(arg
->acc
.access
, isl_dim_out
);
2831 space2
= isl_space_alloc(ctx
, 0, 0, 1);
2832 space2
= isl_space_set_tuple_id(space2
, isl_dim_in
, id
);
2833 vb
= isl_union_map_extract_map(value_bounds
, space2
);
2834 if (!isl_map_plain_is_empty(vb
))
2835 map_i
= isl_map_intersect_range(map_i
,
2840 map
= isl_map_flat_range_product(map
, map_i
);
2842 isl_space_free(space
);
2844 return isl_map_wrap(map
);
2847 /* Data used in access_gist() callback.
2849 struct pet_access_gist_data
{
2851 isl_union_map
*value_bounds
;
2854 /* Given an expression "expr" of type pet_expr_access, compute
2855 * the gist of the associated access relation with respect to
2856 * data->domain and the bounds on the values of the arguments
2857 * of the expression.
2859 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
2861 struct pet_access_gist_data
*data
= user
;
2864 domain
= isl_set_copy(data
->domain
);
2865 if (expr
->n_arg
> 0)
2866 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
2867 data
->value_bounds
);
2869 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
2870 if (!expr
->acc
.access
)
2871 return pet_expr_free(expr
);
2876 /* Compute the gist of the iteration domain and all access relations
2877 * of "stmt" based on the constraints on the parameters specified by "context"
2878 * and the constraints on the values of nested accesses specified
2879 * by "value_bounds".
2881 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2882 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2887 struct pet_access_gist_data data
;
2892 data
.domain
= isl_set_copy(stmt
->domain
);
2893 data
.value_bounds
= value_bounds
;
2894 if (stmt
->n_arg
> 0)
2895 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
2897 data
.domain
= isl_set_intersect_params(data
.domain
,
2898 isl_set_copy(context
));
2900 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2901 stmt
->args
[i
] = pet_expr_foreach_access_expr(stmt
->args
[i
],
2902 &access_gist
, &data
);
2907 stmt
->body
= pet_expr_foreach_access_expr(stmt
->body
,
2908 &access_gist
, &data
);
2912 isl_set_free(data
.domain
);
2914 space
= isl_set_get_space(stmt
->domain
);
2915 if (isl_space_is_wrapping(space
))
2916 space
= isl_space_domain(isl_space_unwrap(space
));
2917 domain
= isl_set_universe(space
);
2918 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2919 if (stmt
->n_arg
> 0)
2920 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
2922 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2924 return pet_stmt_free(stmt
);
2928 isl_set_free(data
.domain
);
2929 return pet_stmt_free(stmt
);
2932 /* Compute the gist of the extent of the array
2933 * based on the constraints on the parameters specified by "context".
2935 static struct pet_array
*array_gist(struct pet_array
*array
,
2936 __isl_keep isl_set
*context
)
2941 array
->extent
= isl_set_gist_params(array
->extent
,
2942 isl_set_copy(context
));
2944 return pet_array_free(array
);
2949 /* Compute the gist of all sets and relations in "scop"
2950 * based on the constraints on the parameters specified by "scop->context"
2951 * and the constraints on the values of nested accesses specified
2952 * by "value_bounds".
2954 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
2955 __isl_keep isl_union_map
*value_bounds
)
2962 scop
->context
= isl_set_coalesce(scop
->context
);
2964 return pet_scop_free(scop
);
2966 for (i
= 0; i
< scop
->n_array
; ++i
) {
2967 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
2968 if (!scop
->arrays
[i
])
2969 return pet_scop_free(scop
);
2972 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2973 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
2975 if (!scop
->stmts
[i
])
2976 return pet_scop_free(scop
);
2982 /* Intersect the context of "scop" with "context".
2983 * To ensure that we don't introduce any unnamed parameters in
2984 * the context of "scop", we first remove the unnamed parameters
2987 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
2988 __isl_take isl_set
*context
)
2993 context
= set_project_out_unnamed_params(context
);
2994 scop
->context
= isl_set_intersect(scop
->context
, context
);
2996 return pet_scop_free(scop
);
3000 isl_set_free(context
);
3001 return pet_scop_free(scop
);
3004 /* Drop the current context of "scop". That is, replace the context
3005 * by a universal set.
3007 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3014 space
= isl_set_get_space(scop
->context
);
3015 isl_set_free(scop
->context
);
3016 scop
->context
= isl_set_universe(space
);
3018 return pet_scop_free(scop
);
3023 /* Append "array" to the arrays of "scop".
3025 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3026 struct pet_array
*array
)
3029 struct pet_array
**arrays
;
3031 if (!array
|| !scop
)
3034 ctx
= isl_set_get_ctx(scop
->context
);
3035 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3039 scop
->arrays
= arrays
;
3040 scop
->arrays
[scop
->n_array
] = array
;
3045 pet_array_free(array
);
3046 return pet_scop_free(scop
);