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
] = "=",
66 [pet_op_post_inc
] = "++",
67 [pet_op_post_dec
] = "--",
68 [pet_op_pre_inc
] = "++",
69 [pet_op_pre_dec
] = "--",
70 [pet_op_address_of
] = "&"
73 const char *pet_op_str(enum pet_op_type op
)
78 int pet_op_is_inc_dec(enum pet_op_type op
)
80 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
81 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
84 const char *pet_type_str(enum pet_expr_type type
)
86 return type_str
[type
];
89 enum pet_op_type
pet_str_op(const char *str
)
93 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
94 if (!strcmp(op_str
[i
], str
))
100 enum pet_expr_type
pet_str_type(const char *str
)
104 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
105 if (!strcmp(type_str
[i
], str
))
111 /* Construct a pet_expr from an access relation.
112 * By default, it is considered to be a read access.
114 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
116 isl_ctx
*ctx
= isl_map_get_ctx(access
);
117 struct pet_expr
*expr
;
121 expr
= isl_calloc_type(ctx
, struct pet_expr
);
125 expr
->type
= pet_expr_access
;
126 expr
->acc
.access
= access
;
132 isl_map_free(access
);
136 /* Construct a unary pet_expr that performs "op" on "arg".
138 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
139 struct pet_expr
*arg
)
141 struct pet_expr
*expr
;
145 expr
= isl_alloc_type(ctx
, struct pet_expr
);
149 expr
->type
= pet_expr_unary
;
152 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
155 expr
->args
[pet_un_arg
] = arg
;
163 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
165 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
166 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
168 struct pet_expr
*expr
;
172 expr
= isl_alloc_type(ctx
, struct pet_expr
);
176 expr
->type
= pet_expr_binary
;
179 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
182 expr
->args
[pet_bin_lhs
] = lhs
;
183 expr
->args
[pet_bin_rhs
] = rhs
;
192 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
194 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
195 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
197 struct pet_expr
*expr
;
199 if (!cond
|| !lhs
|| !rhs
)
201 expr
= isl_alloc_type(ctx
, struct pet_expr
);
205 expr
->type
= pet_expr_ternary
;
207 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
210 expr
->args
[pet_ter_cond
] = cond
;
211 expr
->args
[pet_ter_true
] = lhs
;
212 expr
->args
[pet_ter_false
] = rhs
;
222 /* Construct a call pet_expr that calls function "name" with "n_arg"
223 * arguments. The caller is responsible for filling in the arguments.
225 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
228 struct pet_expr
*expr
;
230 expr
= isl_alloc_type(ctx
, struct pet_expr
);
234 expr
->type
= pet_expr_call
;
236 expr
->name
= strdup(name
);
237 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
238 if (!expr
->name
|| !expr
->args
)
239 return pet_expr_free(expr
);
244 /* Construct a pet_expr that represents the double "d".
246 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
248 struct pet_expr
*expr
;
250 expr
= isl_calloc_type(ctx
, struct pet_expr
);
254 expr
->type
= pet_expr_double
;
260 void *pet_expr_free(struct pet_expr
*expr
)
267 for (i
= 0; i
< expr
->n_arg
; ++i
)
268 pet_expr_free(expr
->args
[i
]);
271 switch (expr
->type
) {
272 case pet_expr_access
:
273 isl_map_free(expr
->acc
.access
);
278 case pet_expr_double
:
280 case pet_expr_binary
:
281 case pet_expr_ternary
:
289 static void expr_dump(struct pet_expr
*expr
, int indent
)
296 fprintf(stderr
, "%*s", indent
, "");
298 switch (expr
->type
) {
299 case pet_expr_double
:
300 fprintf(stderr
, "%g\n", expr
->d
);
302 case pet_expr_access
:
303 isl_map_dump(expr
->acc
.access
);
304 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
306 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
307 "", expr
->acc
.write
);
308 for (i
= 0; i
< expr
->n_arg
; ++i
)
309 expr_dump(expr
->args
[i
], indent
+ 2);
312 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
313 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
315 case pet_expr_binary
:
316 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
317 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
318 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
320 case pet_expr_ternary
:
321 fprintf(stderr
, "?:\n");
322 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
323 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
324 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
327 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
328 for (i
= 0; i
< expr
->n_arg
; ++i
)
329 expr_dump(expr
->args
[i
], indent
+ 2);
334 void pet_expr_dump(struct pet_expr
*expr
)
339 /* Does "expr" represent an access to an unnamed space, i.e.,
340 * does it represent an affine expression?
342 int pet_expr_is_affine(struct pet_expr
*expr
)
348 if (expr
->type
!= pet_expr_access
)
351 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
358 /* Return 1 if the two pet_exprs are equivalent.
360 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
364 if (!expr1
|| !expr2
)
367 if (expr1
->type
!= expr2
->type
)
369 if (expr1
->n_arg
!= expr2
->n_arg
)
371 for (i
= 0; i
< expr1
->n_arg
; ++i
)
372 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
374 switch (expr1
->type
) {
375 case pet_expr_double
:
376 if (expr1
->d
!= expr2
->d
)
379 case pet_expr_access
:
380 if (expr1
->acc
.read
!= expr2
->acc
.read
)
382 if (expr1
->acc
.write
!= expr2
->acc
.write
)
384 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
386 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
390 case pet_expr_binary
:
391 case pet_expr_ternary
:
392 if (expr1
->op
!= expr2
->op
)
396 if (strcmp(expr1
->name
, expr2
->name
))
404 /* Add extra conditions on the parameters to all access relations in "expr".
406 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
407 __isl_take isl_set
*cond
)
414 for (i
= 0; i
< expr
->n_arg
; ++i
) {
415 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
421 if (expr
->type
== pet_expr_access
) {
422 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
424 if (!expr
->acc
.access
)
432 return pet_expr_free(expr
);
435 /* Modify all access relations in "expr" by calling "fn" on them.
437 struct pet_expr
*pet_expr_foreach_access(struct pet_expr
*expr
,
438 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
446 for (i
= 0; i
< expr
->n_arg
; ++i
) {
447 expr
->args
[i
] = pet_expr_foreach_access(expr
->args
[i
], fn
, user
);
449 return pet_expr_free(expr
);
452 if (expr
->type
== pet_expr_access
) {
453 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
454 if (!expr
->acc
.access
)
455 return pet_expr_free(expr
);
461 /* Modify all expressions of type pet_expr_access in "expr"
462 * by calling "fn" on them.
464 struct pet_expr
*pet_expr_foreach_access_expr(struct pet_expr
*expr
,
465 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
473 for (i
= 0; i
< expr
->n_arg
; ++i
) {
474 expr
->args
[i
] = pet_expr_foreach_access_expr(expr
->args
[i
],
477 return pet_expr_free(expr
);
480 if (expr
->type
== pet_expr_access
)
481 expr
= fn(expr
, user
);
486 /* Modify the given access relation based on the given iteration space
488 * If the access has any arguments then the domain of the access relation
489 * is a wrapped mapping from the iteration space to the space of
490 * argument values. We only need to change the domain of this wrapped
491 * mapping, so we extend the input transformation with an identity mapping
492 * on the space of argument values.
494 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
497 isl_map
*update
= user
;
500 update
= isl_map_copy(update
);
502 dim
= isl_map_get_space(access
);
503 dim
= isl_space_domain(dim
);
504 if (!isl_space_is_wrapping(dim
))
508 dim
= isl_space_unwrap(dim
);
509 dim
= isl_space_range(dim
);
510 dim
= isl_space_map_from_set(dim
);
511 id
= isl_map_identity(dim
);
512 update
= isl_map_product(update
, id
);
515 return isl_map_apply_domain(access
, update
);
518 /* Modify all access relations in "expr" based on the given iteration space
521 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
522 __isl_take isl_map
*update
)
524 expr
= pet_expr_foreach_access(expr
, &update_domain
, update
);
525 isl_map_free(update
);
529 /* Construct a pet_stmt with given line number and statement
530 * number from a pet_expr.
531 * The initial iteration domain is the zero-dimensional universe.
532 * The name of the domain is given by "label" if it is non-NULL.
533 * Otherwise, the name is constructed as S_<id>.
534 * The domains of all access relations are modified to refer
535 * to the statement iteration domain.
537 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
538 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
540 struct pet_stmt
*stmt
;
550 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
554 dim
= isl_space_set_alloc(ctx
, 0, 0);
556 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
558 snprintf(name
, sizeof(name
), "S_%d", id
);
559 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
561 dom
= isl_set_universe(isl_space_copy(dim
));
562 sched
= isl_map_from_domain(isl_set_copy(dom
));
564 dim
= isl_space_from_range(dim
);
565 add_name
= isl_map_universe(dim
);
566 expr
= expr_update_domain(expr
, add_name
);
570 stmt
->schedule
= sched
;
573 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
574 return pet_stmt_free(stmt
);
579 return pet_expr_free(expr
);
582 void *pet_stmt_free(struct pet_stmt
*stmt
)
589 isl_set_free(stmt
->domain
);
590 isl_map_free(stmt
->schedule
);
591 pet_expr_free(stmt
->body
);
593 for (i
= 0; i
< stmt
->n_arg
; ++i
)
594 pet_expr_free(stmt
->args
[i
]);
601 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
608 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
609 fprintf(stderr
, "%*s", indent
, "");
610 isl_set_dump(stmt
->domain
);
611 fprintf(stderr
, "%*s", indent
, "");
612 isl_map_dump(stmt
->schedule
);
613 expr_dump(stmt
->body
, indent
);
614 for (i
= 0; i
< stmt
->n_arg
; ++i
)
615 expr_dump(stmt
->args
[i
], indent
+ 2);
618 void pet_stmt_dump(struct pet_stmt
*stmt
)
623 void *pet_array_free(struct pet_array
*array
)
628 isl_set_free(array
->context
);
629 isl_set_free(array
->extent
);
630 isl_set_free(array
->value_bounds
);
631 free(array
->element_type
);
637 void pet_array_dump(struct pet_array
*array
)
642 isl_set_dump(array
->context
);
643 isl_set_dump(array
->extent
);
644 isl_set_dump(array
->value_bounds
);
645 fprintf(stderr
, "%s %s\n", array
->element_type
,
646 array
->live_out
? "live-out" : "");
649 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
651 return isl_calloc_type(ctx
, struct pet_scop
);
654 /* Construct a pet_scop with room for n statements.
656 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
659 struct pet_scop
*scop
;
661 scop
= pet_scop_alloc(ctx
);
665 space
= isl_space_params_alloc(ctx
, 0);
666 scop
->context
= isl_set_universe(isl_space_copy(space
));
667 scop
->context_value
= isl_set_universe(space
);
668 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
669 if (!scop
->context
|| !scop
->stmts
)
670 return pet_scop_free(scop
);
677 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
679 return scop_alloc(ctx
, 0);
682 /* Update "context" with respect to the valid parameter values for "access".
684 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
685 __isl_take isl_set
*context
)
687 context
= isl_set_intersect(context
,
688 isl_map_params(isl_map_copy(access
)));
692 /* Update "context" with respect to the valid parameter values for "expr".
694 * If "expr" represents a ternary operator, then a parameter value
695 * needs to be valid for the condition and for at least one of the
696 * remaining two arguments.
697 * If the condition is an affine expression, then we can be a bit more specific.
698 * The parameter then has to be valid for the second argument for
699 * non-zero accesses and valid for the third argument for zero accesses.
701 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
702 __isl_take isl_set
*context
)
706 if (expr
->type
== pet_expr_ternary
) {
708 isl_set
*context1
, *context2
;
710 is_aff
= pet_expr_is_affine(expr
->args
[0]);
714 context
= expr_extract_context(expr
->args
[0], context
);
715 context1
= expr_extract_context(expr
->args
[1],
716 isl_set_copy(context
));
717 context2
= expr_extract_context(expr
->args
[2], context
);
723 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
724 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
725 zero_set
= isl_map_params(access
);
726 context1
= isl_set_subtract(context1
,
727 isl_set_copy(zero_set
));
728 context2
= isl_set_intersect(context2
, zero_set
);
731 context
= isl_set_union(context1
, context2
);
732 context
= isl_set_coalesce(context
);
737 for (i
= 0; i
< expr
->n_arg
; ++i
)
738 context
= expr_extract_context(expr
->args
[i
], context
);
740 if (expr
->type
== pet_expr_access
)
741 context
= access_extract_context(expr
->acc
.access
, context
);
745 isl_set_free(context
);
749 /* Update "context" with respect to the valid parameter values for "stmt".
751 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
752 __isl_take isl_set
*context
)
756 for (i
= 0; i
< stmt
->n_arg
; ++i
)
757 context
= expr_extract_context(stmt
->args
[i
], context
);
759 context
= expr_extract_context(stmt
->body
, context
);
764 /* Construct a pet_scop that contains the given pet_stmt.
766 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
768 struct pet_scop
*scop
;
773 scop
= scop_alloc(ctx
, 1);
775 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
779 scop
->stmts
[0] = stmt
;
788 /* Construct a pet_scop that contains the arrays and the statements
789 * in "scop1" and "scop2".
791 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
792 struct pet_scop
*scop2
)
795 struct pet_scop
*scop
;
797 if (!scop1
|| !scop2
)
800 if (scop1
->n_stmt
== 0) {
801 pet_scop_free(scop1
);
805 if (scop2
->n_stmt
== 0) {
806 pet_scop_free(scop2
);
810 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
814 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
815 scop1
->n_array
+ scop2
->n_array
);
818 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
820 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
821 scop
->stmts
[i
] = scop1
->stmts
[i
];
822 scop1
->stmts
[i
] = NULL
;
825 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
826 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
827 scop2
->stmts
[i
] = NULL
;
830 for (i
= 0; i
< scop1
->n_array
; ++i
) {
831 scop
->arrays
[i
] = scop1
->arrays
[i
];
832 scop1
->arrays
[i
] = NULL
;
835 for (i
= 0; i
< scop2
->n_array
; ++i
) {
836 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
837 scop2
->arrays
[i
] = NULL
;
840 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
841 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
843 pet_scop_free(scop1
);
844 pet_scop_free(scop2
);
847 pet_scop_free(scop1
);
848 pet_scop_free(scop2
);
852 void *pet_scop_free(struct pet_scop
*scop
)
858 isl_set_free(scop
->context
);
859 isl_set_free(scop
->context_value
);
861 for (i
= 0; i
< scop
->n_array
; ++i
)
862 pet_array_free(scop
->arrays
[i
]);
865 for (i
= 0; i
< scop
->n_stmt
; ++i
)
866 pet_stmt_free(scop
->stmts
[i
]);
872 void pet_scop_dump(struct pet_scop
*scop
)
879 isl_set_dump(scop
->context
);
880 isl_set_dump(scop
->context_value
);
881 for (i
= 0; i
< scop
->n_array
; ++i
)
882 pet_array_dump(scop
->arrays
[i
]);
883 for (i
= 0; i
< scop
->n_stmt
; ++i
)
884 pet_stmt_dump(scop
->stmts
[i
]);
887 /* Return 1 if the two pet_arrays are equivalent.
889 * We don't compare element_size as this may be target dependent.
891 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
893 if (!array1
|| !array2
)
896 if (!isl_set_is_equal(array1
->context
, array2
->context
))
898 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
900 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
902 if (array1
->value_bounds
&&
903 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
905 if (strcmp(array1
->element_type
, array2
->element_type
))
907 if (array1
->live_out
!= array2
->live_out
)
909 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
915 /* Return 1 if the two pet_stmts are equivalent.
917 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
921 if (!stmt1
|| !stmt2
)
924 if (stmt1
->line
!= stmt2
->line
)
926 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
928 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
930 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
932 if (stmt1
->n_arg
!= stmt2
->n_arg
)
934 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
935 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
942 /* Return 1 if the two pet_scops are equivalent.
944 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
948 if (!scop1
|| !scop2
)
951 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
953 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
956 if (scop1
->n_array
!= scop2
->n_array
)
958 for (i
= 0; i
< scop1
->n_array
; ++i
)
959 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
962 if (scop1
->n_stmt
!= scop2
->n_stmt
)
964 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
965 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
971 /* Prefix the schedule of "stmt" with an extra dimension with constant
974 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
979 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
980 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
982 return pet_stmt_free(stmt
);
987 /* Prefix the schedules of all statements in "scop" with an extra
988 * dimension with constant value "pos".
990 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
997 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
998 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1000 return pet_scop_free(scop
);
1006 /* Given a set with a parameter at "param_pos" that refers to the
1007 * iterator, "move" the iterator to the first set dimension.
1008 * That is, essentially equate the parameter to the first set dimension
1009 * and then project it out.
1011 * The first set dimension may however refer to a virtual iterator,
1012 * while the parameter refers to the "real" iterator.
1013 * We therefore need to take into account the mapping "iv_map", which
1014 * maps the virtual iterator to the real iterator.
1015 * In particular, we equate the set dimension to the input of the map
1016 * and the parameter to the output of the map and then project out
1017 * everything we don't need anymore.
1019 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1020 int param_pos
, __isl_take isl_map
*iv_map
)
1023 map
= isl_map_from_domain(set
);
1024 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1025 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1026 iv_map
= isl_map_align_params(iv_map
, isl_map_get_space(map
));
1027 map
= isl_map_apply_range(map
, iv_map
);
1028 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1029 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1030 return isl_map_domain(map
);
1033 /* Data used in embed_access.
1034 * extend adds an iterator to the iteration domain
1035 * iv_map maps the virtual iterator to the real iterator
1036 * var_id represents the induction variable of the corresponding loop
1038 struct pet_embed_access
{
1044 /* Embed the access relation in an extra outer loop.
1046 * We first update the iteration domain to insert the extra dimension.
1048 * If the access refers to the induction variable, then it is
1049 * turned into an access to the set of integers with index (and value)
1050 * equal to the induction variable.
1052 * If the induction variable appears in the constraints (as a parameter),
1053 * then the parameter is equated to the newly introduced iteration
1054 * domain dimension and subsequently projected out.
1056 * Similarly, if the accessed array is a virtual array (with user
1057 * pointer equal to NULL), as created by create_test_access,
1058 * then it is extended along with the domain of the access.
1060 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
1063 struct pet_embed_access
*data
= user
;
1064 isl_id
*array_id
= NULL
;
1067 access
= update_domain(access
, data
->extend
);
1069 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1070 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1071 if (array_id
== data
->var_id
||
1072 (array_id
&& !isl_id_get_user(array_id
))) {
1073 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1074 access
= isl_map_equate(access
,
1075 isl_dim_in
, 0, isl_dim_out
, 0);
1076 if (array_id
== data
->var_id
)
1077 access
= isl_map_apply_range(access
,
1078 isl_map_copy(data
->iv_map
));
1080 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1081 isl_id_copy(array_id
));
1083 isl_id_free(array_id
);
1085 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1087 isl_set
*set
= isl_map_wrap(access
);
1088 set
= internalize_iv(set
, pos
, isl_map_copy(data
->iv_map
));
1089 access
= isl_set_unwrap(set
);
1091 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1092 isl_id_copy(data
->var_id
));
1097 /* Embed all access relations in "expr" in an extra loop.
1098 * "extend" inserts an outer loop iterator in the iteration domains.
1099 * "iv_map" maps the virtual iterator to the real iterator
1100 * "var_id" represents the induction variable.
1102 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1103 __isl_take isl_map
*extend
, __isl_take isl_map
*iv_map
,
1104 __isl_keep isl_id
*var_id
)
1106 struct pet_embed_access data
=
1107 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1109 expr
= pet_expr_foreach_access(expr
, &embed_access
, &data
);
1110 isl_map_free(iv_map
);
1111 isl_map_free(extend
);
1115 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1116 * "dom" and schedule "sched". "var_id" represents the induction variable
1117 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1118 * That is, it maps the iterator used in "dom" and the domain of "sched"
1119 * to the iterator that some of the parameters in "stmt" may refer to.
1121 * The iteration domain and schedule of the statement are updated
1122 * according to the iteration domain and schedule of the new loop.
1123 * If stmt->domain is a wrapped map, then the iteration domain
1124 * is the domain of this map, so we need to be careful to adjust
1127 * If the induction variable appears in the constraints (as a parameter)
1128 * of the current iteration domain or the schedule of the statement,
1129 * then the parameter is equated to the newly introduced iteration
1130 * domain dimension and subsequently projected out.
1132 * Finally, all access relations are updated based on the extra loop.
1134 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1135 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1136 __isl_take isl_map
*iv_map
, __isl_take isl_id
*var_id
)
1147 if (isl_set_is_wrapping(stmt
->domain
)) {
1152 map
= isl_set_unwrap(stmt
->domain
);
1153 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1154 ran_dim
= isl_space_range(isl_map_get_space(map
));
1155 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1156 isl_set_universe(ran_dim
));
1157 map
= isl_map_flat_domain_product(ext
, map
);
1158 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1159 isl_id_copy(stmt_id
));
1160 dim
= isl_space_domain(isl_map_get_space(map
));
1161 stmt
->domain
= isl_map_wrap(map
);
1163 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1164 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1166 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1167 isl_id_copy(stmt_id
));
1168 dim
= isl_set_get_space(stmt
->domain
);
1171 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1173 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1174 isl_map_copy(iv_map
));
1176 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1177 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1178 isl_dim_in
, stmt_id
);
1180 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1182 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1183 set
= internalize_iv(set
, pos
, isl_map_copy(iv_map
));
1184 stmt
->schedule
= isl_set_unwrap(set
);
1187 dim
= isl_space_map_from_set(dim
);
1188 extend
= isl_map_identity(dim
);
1189 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1190 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1191 isl_map_get_tuple_id(extend
, isl_dim_out
));
1192 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1193 stmt
->args
[i
] = expr_embed(stmt
->args
[i
], isl_map_copy(extend
),
1194 isl_map_copy(iv_map
), var_id
);
1195 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1198 isl_id_free(var_id
);
1200 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1202 return pet_stmt_free(stmt
);
1203 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1204 return pet_stmt_free(stmt
);
1208 isl_map_free(sched
);
1209 isl_map_free(iv_map
);
1210 isl_id_free(var_id
);
1214 /* Embed the given pet_array in an extra outer loop with iteration domain
1216 * This embedding only has an effect on virtual arrays (those with
1217 * user pointer equal to NULL), which need to be extended along with
1218 * the iteration domain.
1220 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1221 __isl_take isl_set
*dom
)
1223 isl_id
*array_id
= NULL
;
1228 if (isl_set_has_tuple_id(array
->extent
))
1229 array_id
= isl_set_get_tuple_id(array
->extent
);
1231 if (array_id
&& !isl_id_get_user(array_id
)) {
1232 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1233 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1236 isl_id_free(array_id
);
1245 /* Project out all unnamed parameters from "set" and return the result.
1247 static __isl_give isl_set
*set_project_out_unnamed_params(
1248 __isl_take isl_set
*set
)
1252 n
= isl_set_dim(set
, isl_dim_param
);
1253 for (i
= n
- 1; i
>= 0; --i
) {
1254 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1256 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1262 /* Update the context with respect to an embedding into a loop
1263 * with iteration domain "dom" and induction variable "id".
1264 * "iv_map" maps a possibly virtual iterator (used in "dom")
1265 * to the real iterator (parameter "id").
1267 * If the current context is independent of "id", we don't need
1269 * Otherwise, a parameter value is invalid for the embedding if
1270 * any of the corresponding iterator values is invalid.
1271 * That is, a parameter value is valid only if all the corresponding
1272 * iterator values are valid.
1273 * We therefore compute the set of parameters
1275 * forall i in dom : valid (i)
1279 * not exists i in dom : not valid(i)
1283 * not exists i in dom \ valid(i)
1285 * Before we subtract valid(i) from dom, we first need to map
1286 * the real iterator to the virtual iterator.
1288 * If there are any unnamed parameters in "dom", then we consider
1289 * a parameter value to be valid if it is valid for any value of those
1290 * unnamed parameters. They are therefore projected out at the end.
1292 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1293 __isl_keep isl_set
*dom
, __isl_keep isl_map
*iv_map
,
1294 __isl_keep isl_id
*id
)
1298 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1302 context
= isl_set_from_params(context
);
1303 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1304 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1305 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1306 context
= isl_set_apply(context
, isl_map_reverse(isl_map_copy(iv_map
)));
1307 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1308 context
= isl_set_params(context
);
1309 context
= isl_set_complement(context
);
1310 context
= set_project_out_unnamed_params(context
);
1314 /* Embed all statements and arrays in "scop" in an extra outer loop
1315 * with iteration domain "dom" and schedule "sched".
1316 * "id" represents the induction variable of the loop.
1317 * "iv_map" maps a possibly virtual iterator to the real iterator.
1318 * That is, it maps the iterator used in "dom" and the domain of "sched"
1319 * to the iterator that some of the parameters in "scop" may refer to.
1321 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1322 __isl_take isl_map
*sched
, __isl_take isl_map
*iv_map
,
1323 __isl_take isl_id
*id
)
1330 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1334 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1335 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1336 isl_set_copy(dom
), isl_map_copy(sched
),
1337 isl_map_copy(iv_map
), isl_id_copy(id
));
1338 if (!scop
->stmts
[i
])
1342 for (i
= 0; i
< scop
->n_array
; ++i
) {
1343 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1345 if (!scop
->arrays
[i
])
1350 isl_map_free(sched
);
1351 isl_map_free(iv_map
);
1356 isl_map_free(sched
);
1357 isl_map_free(iv_map
);
1359 return pet_scop_free(scop
);
1362 /* Add extra conditions on the parameters to iteration domain of "stmt".
1364 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1365 __isl_take isl_set
*cond
)
1370 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1375 return pet_stmt_free(stmt
);
1378 /* Add extra conditions on the parameters to all iteration domains.
1380 * A parameter value is valid for the result if it was valid
1381 * for the original scop and satisfies "cond" or if it does
1382 * not satisfy "cond" as in this case the scop is not executed
1383 * and the original constraints on the parameters are irrelevant.
1385 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1386 __isl_take isl_set
*cond
)
1393 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1394 scop
->context
= isl_set_union(scop
->context
,
1395 isl_set_complement(isl_set_copy(cond
)));
1396 scop
->context
= isl_set_coalesce(scop
->context
);
1397 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1401 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1402 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1403 isl_set_copy(cond
));
1404 if (!scop
->stmts
[i
])
1412 return pet_scop_free(scop
);
1415 /* Construct a map that inserts a filter value with name "id" and value
1416 * "satisfied" in the list of filter values embedded in the set space "space".
1418 * If "space" does not contain any filter values yet, we first create
1419 * a map that inserts 0 filter values, i.e.,
1421 * space -> [space -> []]
1423 * We can now assume that space is of the form [dom -> [filters]]
1424 * We construct an identity mapping on dom and a mapping on filters
1425 * that inserts the new filter
1428 * [filters] -> [satisfied, filters]
1430 * and then compute the cross product
1432 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1434 static __isl_give isl_map
*insert_filter_map(__isl_take isl_space
*space
,
1435 __isl_take isl_id
*id
, int satisfied
)
1438 isl_map
*map
, *map_dom
, *map_ran
;
1441 if (isl_space_is_wrapping(space
)) {
1442 space2
= isl_space_map_from_set(isl_space_copy(space
));
1443 map
= isl_map_identity(space2
);
1444 space
= isl_space_unwrap(space
);
1446 space
= isl_space_from_domain(space
);
1447 map
= isl_map_universe(isl_space_copy(space
));
1448 map
= isl_map_reverse(isl_map_domain_map(map
));
1451 space2
= isl_space_domain(isl_space_copy(space
));
1452 map_dom
= isl_map_identity(isl_space_map_from_set(space2
));
1453 space
= isl_space_range(space
);
1454 map_ran
= isl_map_identity(isl_space_map_from_set(space
));
1455 map_ran
= isl_map_insert_dims(map_ran
, isl_dim_out
, 0, 1);
1456 map_ran
= isl_map_set_dim_id(map_ran
, isl_dim_out
, 0, id
);
1457 map_ran
= isl_map_fix_si(map_ran
, isl_dim_out
, 0, satisfied
);
1459 map
= isl_map_apply_range(map
, isl_map_product(map_dom
, map_ran
));
1464 /* Insert an argument expression corresponding to "test" in front
1465 * of the list of arguments described by *n_arg and *args.
1467 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
1468 __isl_keep isl_map
*test
)
1471 isl_ctx
*ctx
= isl_map_get_ctx(test
);
1477 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1481 struct pet_expr
**ext
;
1482 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
1485 for (i
= 0; i
< *n_arg
; ++i
)
1486 ext
[1 + i
] = (*args
)[i
];
1491 (*args
)[0] = pet_expr_from_access(isl_map_copy(test
));
1498 /* Make the statement "stmt" depend on the value of "test"
1499 * being equal to "satisfied" by adjusting stmt->domain.
1501 * The domain of "test" corresponds to the (zero or more) outer dimensions
1502 * of the iteration domain.
1504 * We insert an argument corresponding to a read to "test"
1505 * from the iteration domain of "stmt" in front of the list of arguments.
1506 * We also insert a corresponding output dimension in the wrapped
1507 * map contained in stmt->domain, with value set to "satisfied".
1509 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1510 __isl_take isl_map
*test
, int satisfied
)
1515 isl_map
*map
, *add_dom
;
1523 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1524 map
= insert_filter_map(isl_set_get_space(stmt
->domain
), id
, satisfied
);
1525 stmt
->domain
= isl_set_apply(stmt
->domain
, map
);
1527 space
= isl_space_unwrap(isl_set_get_space(stmt
->domain
));
1528 dom
= isl_set_universe(isl_space_domain(space
));
1529 n_test_dom
= isl_map_dim(test
, isl_dim_in
);
1530 add_dom
= isl_map_from_range(dom
);
1531 add_dom
= isl_map_add_dims(add_dom
, isl_dim_in
, n_test_dom
);
1532 for (i
= 0; i
< n_test_dom
; ++i
)
1533 add_dom
= isl_map_equate(add_dom
, isl_dim_in
, i
,
1535 test
= isl_map_apply_domain(test
, add_dom
);
1537 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1544 return pet_stmt_free(stmt
);
1547 /* Make all statements in "scop" depend on the value of "test"
1548 * being equal to "satisfied" by adjusting their domains.
1550 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1551 __isl_take isl_map
*test
, int satisfied
)
1558 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1559 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
1560 isl_map_copy(test
), satisfied
);
1561 if (!scop
->stmts
[i
])
1569 return pet_scop_free(scop
);
1572 /* Add all parameters in "expr" to "dim" and return the result.
1574 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
1575 __isl_take isl_space
*dim
)
1581 for (i
= 0; i
< expr
->n_arg
; ++i
)
1583 dim
= expr_collect_params(expr
->args
[i
], dim
);
1585 if (expr
->type
== pet_expr_access
)
1586 dim
= isl_space_align_params(dim
,
1587 isl_map_get_space(expr
->acc
.access
));
1591 isl_space_free(dim
);
1592 return pet_expr_free(expr
);
1595 /* Add all parameters in "stmt" to "dim" and return the result.
1597 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
1598 __isl_take isl_space
*dim
)
1603 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
1604 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
1605 dim
= expr_collect_params(stmt
->body
, dim
);
1609 isl_space_free(dim
);
1610 return pet_stmt_free(stmt
);
1613 /* Add all parameters in "array" to "dim" and return the result.
1615 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1616 __isl_take isl_space
*dim
)
1621 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
1622 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
1626 isl_space_free(dim
);
1627 return pet_array_free(array
);
1630 /* Add all parameters in "scop" to "dim" and return the result.
1632 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1633 __isl_take isl_space
*dim
)
1640 for (i
= 0; i
< scop
->n_array
; ++i
)
1641 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1643 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1644 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1648 isl_space_free(dim
);
1649 return pet_scop_free(scop
);
1652 /* Add all parameters in "dim" to all access relations in "expr".
1654 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1655 __isl_take isl_space
*dim
)
1662 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1664 expr_propagate_params(expr
->args
[i
],
1665 isl_space_copy(dim
));
1670 if (expr
->type
== pet_expr_access
) {
1671 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1672 isl_space_copy(dim
));
1673 if (!expr
->acc
.access
)
1677 isl_space_free(dim
);
1680 isl_space_free(dim
);
1681 return pet_expr_free(expr
);
1684 /* Add all parameters in "dim" to the domain, schedule and
1685 * all access relations in "stmt".
1687 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1688 __isl_take isl_space
*dim
)
1693 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
1694 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1695 isl_space_copy(dim
));
1696 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
1698 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1701 isl_space_free(dim
);
1704 isl_space_free(dim
);
1705 return pet_stmt_free(stmt
);
1708 /* Add all parameters in "dim" to "array".
1710 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1711 __isl_take isl_space
*dim
)
1716 array
->context
= isl_set_align_params(array
->context
,
1717 isl_space_copy(dim
));
1718 array
->extent
= isl_set_align_params(array
->extent
,
1719 isl_space_copy(dim
));
1720 if (array
->value_bounds
) {
1721 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1722 isl_space_copy(dim
));
1723 if (!array
->value_bounds
)
1727 if (!array
->context
|| !array
->extent
)
1730 isl_space_free(dim
);
1733 isl_space_free(dim
);
1734 return pet_array_free(array
);
1737 /* Add all parameters in "dim" to "scop".
1739 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1740 __isl_take isl_space
*dim
)
1747 for (i
= 0; i
< scop
->n_array
; ++i
) {
1748 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1749 isl_space_copy(dim
));
1750 if (!scop
->arrays
[i
])
1754 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1755 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1756 isl_space_copy(dim
));
1757 if (!scop
->stmts
[i
])
1761 isl_space_free(dim
);
1764 isl_space_free(dim
);
1765 return pet_scop_free(scop
);
1768 /* Update all isl_sets and isl_maps in "scop" such that they all
1769 * have the same parameters.
1771 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1778 dim
= isl_set_get_space(scop
->context
);
1779 dim
= scop_collect_params(scop
, dim
);
1781 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
1782 scop
= scop_propagate_params(scop
, dim
);
1787 /* Check if the given access relation accesses a (0D) array that corresponds
1788 * to one of the parameters in "dim". If so, replace the array access
1789 * by an access to the set of integers with as index (and value)
1792 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1793 __isl_take isl_space
*dim
)
1795 isl_id
*array_id
= NULL
;
1798 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1799 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1800 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1802 isl_space_free(dim
);
1805 isl_id_free(array_id
);
1809 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1811 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1812 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1815 isl_id_free(array_id
);
1817 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1818 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1823 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1824 * in "dim" by a value equal to the corresponding parameter.
1826 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1827 __isl_take isl_space
*dim
)
1834 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1836 expr_detect_parameter_accesses(expr
->args
[i
],
1837 isl_space_copy(dim
));
1842 if (expr
->type
== pet_expr_access
) {
1843 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1844 isl_space_copy(dim
));
1845 if (!expr
->acc
.access
)
1849 isl_space_free(dim
);
1852 isl_space_free(dim
);
1853 return pet_expr_free(expr
);
1856 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1857 * in "dim" by a value equal to the corresponding parameter.
1859 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1860 __isl_take isl_space
*dim
)
1865 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1866 isl_space_copy(dim
));
1868 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1871 isl_space_free(dim
);
1874 isl_space_free(dim
);
1875 return pet_stmt_free(stmt
);
1878 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1879 * in "dim" by a value equal to the corresponding parameter.
1881 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1882 __isl_take isl_space
*dim
)
1889 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1890 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1891 isl_space_copy(dim
));
1892 if (!scop
->stmts
[i
])
1896 isl_space_free(dim
);
1899 isl_space_free(dim
);
1900 return pet_scop_free(scop
);
1903 /* Replace all accesses to (0D) arrays that correspond to any of
1904 * the parameters used in "scop" by a value equal
1905 * to the corresponding parameter.
1907 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1914 dim
= isl_set_get_space(scop
->context
);
1915 dim
= scop_collect_params(scop
, dim
);
1917 scop
= scop_detect_parameter_accesses(scop
, dim
);
1922 /* Add all read access relations (if "read" is set) and/or all write
1923 * access relations (if "write" is set) to "accesses" and return the result.
1925 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1926 int read
, int write
, __isl_take isl_union_map
*accesses
)
1935 for (i
= 0; i
< expr
->n_arg
; ++i
)
1936 accesses
= expr_collect_accesses(expr
->args
[i
],
1937 read
, write
, accesses
);
1939 if (expr
->type
== pet_expr_access
&&
1940 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
1941 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1942 accesses
= isl_union_map_add_map(accesses
,
1943 isl_map_copy(expr
->acc
.access
));
1948 /* Collect and return all read access relations (if "read" is set)
1949 * and/or all write * access relations (if "write" is set) in "stmt".
1951 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1952 int read
, int write
, __isl_take isl_space
*dim
)
1954 isl_union_map
*accesses
;
1959 accesses
= isl_union_map_empty(dim
);
1960 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1961 accesses
= isl_union_map_intersect_domain(accesses
,
1962 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1967 /* Collect and return all read access relations (if "read" is set)
1968 * and/or all write * access relations (if "write" is set) in "scop".
1970 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1971 int read
, int write
)
1974 isl_union_map
*accesses
;
1979 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1981 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1982 isl_union_map
*accesses_i
;
1983 isl_space
*dim
= isl_set_get_space(scop
->context
);
1984 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1986 accesses
= isl_union_map_union(accesses
, accesses_i
);
1992 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1994 return scop_collect_accesses(scop
, 1, 0);
1997 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1999 return scop_collect_accesses(scop
, 0, 1);
2002 /* Collect and return the union of iteration domains in "scop".
2004 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2008 isl_union_set
*domain
;
2013 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2015 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2016 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2017 domain
= isl_union_set_add_set(domain
, domain_i
);
2023 /* Collect and return the schedules of the statements in "scop".
2024 * The range is normalized to the maximal number of scheduling
2027 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2030 isl_map
*schedule_i
;
2031 isl_union_map
*schedule
;
2032 int depth
, max_depth
= 0;
2037 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2039 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2040 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2041 if (depth
> max_depth
)
2045 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2046 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2047 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2048 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2050 for (j
= depth
; j
< max_depth
; ++j
)
2051 schedule_i
= isl_map_fix_si(schedule_i
,
2053 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2059 /* Does expression "expr" write to "id"?
2061 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
2066 for (i
= 0; i
< expr
->n_arg
; ++i
) {
2067 int writes
= expr_writes(expr
->args
[i
], id
);
2068 if (writes
< 0 || writes
)
2072 if (expr
->type
!= pet_expr_access
)
2074 if (!expr
->acc
.write
)
2076 if (!isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
))
2079 write_id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
2080 isl_id_free(write_id
);
2085 return write_id
== id
;
2088 /* Does statement "stmt" write to "id"?
2090 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
2092 return expr_writes(stmt
->body
, id
);
2095 /* Is there any write access in "scop" that accesses "id"?
2097 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
2104 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2105 int writes
= stmt_writes(scop
->stmts
[i
], id
);
2106 if (writes
< 0 || writes
)
2113 /* Reset the user pointer on all parameter ids in "set".
2115 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
2119 n
= isl_set_dim(set
, isl_dim_param
);
2120 for (i
= 0; i
< n
; ++i
) {
2121 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
2122 const char *name
= isl_id_get_name(id
);
2123 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
2130 /* Reset the user pointer on all parameter ids in "map".
2132 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
2136 n
= isl_map_dim(map
, isl_dim_param
);
2137 for (i
= 0; i
< n
; ++i
) {
2138 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
2139 const char *name
= isl_id_get_name(id
);
2140 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
2147 /* Reset the user pointer on all parameter ids in "array".
2149 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2154 array
->context
= set_anonymize(array
->context
);
2155 array
->extent
= set_anonymize(array
->extent
);
2156 if (!array
->context
|| !array
->extent
)
2157 return pet_array_free(array
);
2162 /* Reset the user pointer on all parameter ids in "access".
2164 static __isl_give isl_map
*access_anonymize(__isl_take isl_map
*access
,
2167 access
= map_anonymize(access
);
2172 /* Reset the user pointer on all parameter ids in "stmt".
2174 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2183 stmt
->domain
= set_anonymize(stmt
->domain
);
2184 stmt
->schedule
= map_anonymize(stmt
->schedule
);
2185 if (!stmt
->domain
|| !stmt
->schedule
)
2186 return pet_stmt_free(stmt
);
2188 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2189 stmt
->args
[i
] = pet_expr_foreach_access(stmt
->args
[i
],
2190 &access_anonymize
, NULL
);
2192 return pet_stmt_free(stmt
);
2195 stmt
->body
= pet_expr_foreach_access(stmt
->body
,
2196 &access_anonymize
, NULL
);
2198 return pet_stmt_free(stmt
);
2203 /* Reset the user pointer on all parameter ids in "scop".
2205 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2212 scop
->context
= set_anonymize(scop
->context
);
2213 scop
->context_value
= set_anonymize(scop
->context_value
);
2214 if (!scop
->context
|| !scop
->context_value
)
2215 return pet_scop_free(scop
);
2217 for (i
= 0; i
< scop
->n_array
; ++i
) {
2218 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2219 if (!scop
->arrays
[i
])
2220 return pet_scop_free(scop
);
2223 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2224 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2225 if (!scop
->stmts
[i
])
2226 return pet_scop_free(scop
);
2232 /* Given a set "domain", return a wrapped relation with the given set
2233 * as domain and a range of dimension "n_arg", where each coordinate
2234 * is either unbounded or, if the corresponding element of args is of
2235 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2237 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
2238 unsigned n_arg
, struct pet_expr
**args
,
2239 __isl_keep isl_union_map
*value_bounds
)
2244 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
2246 map
= isl_map_from_domain(domain
);
2247 space
= isl_map_get_space(map
);
2248 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2250 for (i
= 0; i
< n_arg
; ++i
) {
2252 struct pet_expr
*arg
= args
[i
];
2256 map_i
= isl_map_universe(isl_space_copy(space
));
2257 if (arg
->type
== pet_expr_access
) {
2259 id
= isl_map_get_tuple_id(arg
->acc
.access
, isl_dim_out
);
2260 space2
= isl_space_alloc(ctx
, 0, 0, 1);
2261 space2
= isl_space_set_tuple_id(space2
, isl_dim_in
, id
);
2262 vb
= isl_union_map_extract_map(value_bounds
, space2
);
2263 if (!isl_map_plain_is_empty(vb
))
2264 map_i
= isl_map_intersect_range(map_i
,
2269 map
= isl_map_flat_range_product(map
, map_i
);
2271 isl_space_free(space
);
2273 return isl_map_wrap(map
);
2276 /* Data used in access_gist() callback.
2278 struct pet_access_gist_data
{
2280 isl_union_map
*value_bounds
;
2283 /* Given an expression "expr" of type pet_expr_access, compute
2284 * the gist of the associated access relation with respect to
2285 * data->domain and the bounds on the values of the arguments
2286 * of the expression.
2288 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
2290 struct pet_access_gist_data
*data
= user
;
2293 domain
= isl_set_copy(data
->domain
);
2294 if (expr
->n_arg
> 0)
2295 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
2296 data
->value_bounds
);
2298 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
2299 if (!expr
->acc
.access
)
2300 return pet_expr_free(expr
);
2305 /* Compute the gist of the iteration domain and all access relations
2306 * of "stmt" based on the constraints on the parameters specified by "context"
2307 * and the constraints on the values of nested accesses specified
2308 * by "value_bounds".
2310 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2311 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2316 struct pet_access_gist_data data
;
2321 data
.domain
= isl_set_copy(stmt
->domain
);
2322 data
.value_bounds
= value_bounds
;
2323 if (stmt
->n_arg
> 0)
2324 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
2326 data
.domain
= isl_set_intersect_params(data
.domain
,
2327 isl_set_copy(context
));
2329 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2330 stmt
->args
[i
] = pet_expr_foreach_access_expr(stmt
->args
[i
],
2331 &access_gist
, &data
);
2336 stmt
->body
= pet_expr_foreach_access_expr(stmt
->body
,
2337 &access_gist
, &data
);
2341 isl_set_free(data
.domain
);
2343 space
= isl_set_get_space(stmt
->domain
);
2344 if (isl_space_is_wrapping(space
))
2345 space
= isl_space_domain(isl_space_unwrap(space
));
2346 domain
= isl_set_universe(space
);
2347 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2348 if (stmt
->n_arg
> 0)
2349 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
2351 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2353 return pet_stmt_free(stmt
);
2357 isl_set_free(data
.domain
);
2358 return pet_stmt_free(stmt
);
2361 /* Compute the gist of the extent of the array
2362 * based on the constraints on the parameters specified by "context".
2364 static struct pet_array
*array_gist(struct pet_array
*array
,
2365 __isl_keep isl_set
*context
)
2370 array
->extent
= isl_set_gist_params(array
->extent
,
2371 isl_set_copy(context
));
2373 return pet_array_free(array
);
2378 /* Compute the gist of all sets and relations in "scop"
2379 * based on the constraints on the parameters specified by "scop->context"
2380 * and the constraints on the values of nested accesses specified
2381 * by "value_bounds".
2383 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
2384 __isl_keep isl_union_map
*value_bounds
)
2391 scop
->context
= isl_set_coalesce(scop
->context
);
2393 return pet_scop_free(scop
);
2395 for (i
= 0; i
< scop
->n_array
; ++i
) {
2396 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
2397 if (!scop
->arrays
[i
])
2398 return pet_scop_free(scop
);
2401 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2402 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
2404 if (!scop
->stmts
[i
])
2405 return pet_scop_free(scop
);
2411 /* Intersect the context of "scop" with "context".
2412 * To ensure that we don't introduce any unnamed parameters in
2413 * the context of "scop", we first remove the unnamed parameters
2416 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
2417 __isl_take isl_set
*context
)
2422 context
= set_project_out_unnamed_params(context
);
2423 scop
->context
= isl_set_intersect(scop
->context
, context
);
2425 return pet_scop_free(scop
);
2429 isl_set_free(context
);
2430 return pet_scop_free(scop
);
2433 /* Drop the current context of "scop". That is, replace the context
2434 * by a universal set.
2436 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
2443 space
= isl_set_get_space(scop
->context
);
2444 isl_set_free(scop
->context
);
2445 scop
->context
= isl_set_universe(space
);
2447 return pet_scop_free(scop
);