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_address_of
] = "&"
69 const char *pet_op_str(enum pet_op_type op
)
74 const char *pet_type_str(enum pet_expr_type type
)
76 return type_str
[type
];
79 enum pet_op_type
pet_str_op(const char *str
)
83 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
84 if (!strcmp(op_str
[i
], str
))
90 enum pet_expr_type
pet_str_type(const char *str
)
94 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
95 if (!strcmp(type_str
[i
], str
))
101 /* Construct a pet_expr from an access relation.
102 * By default, it is considered to be a read access.
104 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
106 isl_ctx
*ctx
= isl_map_get_ctx(access
);
107 struct pet_expr
*expr
;
111 expr
= isl_calloc_type(ctx
, struct pet_expr
);
115 expr
->type
= pet_expr_access
;
116 expr
->acc
.access
= access
;
122 isl_map_free(access
);
126 /* Construct a unary pet_expr that performs "op" on "arg".
128 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
129 struct pet_expr
*arg
)
131 struct pet_expr
*expr
;
135 expr
= isl_alloc_type(ctx
, struct pet_expr
);
139 expr
->type
= pet_expr_unary
;
142 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
145 expr
->args
[pet_un_arg
] = arg
;
153 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
155 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
156 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
158 struct pet_expr
*expr
;
162 expr
= isl_alloc_type(ctx
, struct pet_expr
);
166 expr
->type
= pet_expr_binary
;
169 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
172 expr
->args
[pet_bin_lhs
] = lhs
;
173 expr
->args
[pet_bin_rhs
] = rhs
;
182 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
184 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
185 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
187 struct pet_expr
*expr
;
189 if (!cond
|| !lhs
|| !rhs
)
191 expr
= isl_alloc_type(ctx
, struct pet_expr
);
195 expr
->type
= pet_expr_ternary
;
197 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
200 expr
->args
[pet_ter_cond
] = cond
;
201 expr
->args
[pet_ter_true
] = lhs
;
202 expr
->args
[pet_ter_false
] = rhs
;
212 /* Construct a call pet_expr that calls function "name" with "n_arg"
213 * arguments. The caller is responsible for filling in the arguments.
215 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
218 struct pet_expr
*expr
;
220 expr
= isl_alloc_type(ctx
, struct pet_expr
);
224 expr
->type
= pet_expr_call
;
226 expr
->name
= strdup(name
);
227 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
228 if (!expr
->name
|| !expr
->args
)
229 return pet_expr_free(expr
);
234 /* Construct a pet_expr that represents the double "d".
236 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
238 struct pet_expr
*expr
;
240 expr
= isl_calloc_type(ctx
, struct pet_expr
);
244 expr
->type
= pet_expr_double
;
250 void *pet_expr_free(struct pet_expr
*expr
)
257 for (i
= 0; i
< expr
->n_arg
; ++i
)
258 pet_expr_free(expr
->args
[i
]);
261 switch (expr
->type
) {
262 case pet_expr_access
:
263 isl_map_free(expr
->acc
.access
);
268 case pet_expr_double
:
270 case pet_expr_binary
:
271 case pet_expr_ternary
:
279 static void expr_dump(struct pet_expr
*expr
, int indent
)
286 fprintf(stderr
, "%*s", indent
, "");
288 switch (expr
->type
) {
289 case pet_expr_double
:
290 fprintf(stderr
, "%g\n", expr
->d
);
292 case pet_expr_access
:
293 isl_map_dump(expr
->acc
.access
);
294 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
296 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
297 "", expr
->acc
.write
);
298 for (i
= 0; i
< expr
->n_arg
; ++i
)
299 expr_dump(expr
->args
[i
], indent
+ 2);
302 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
303 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
305 case pet_expr_binary
:
306 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
307 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
308 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
310 case pet_expr_ternary
:
311 fprintf(stderr
, "?:\n");
312 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
313 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
314 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
317 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
318 for (i
= 0; i
< expr
->n_arg
; ++i
)
319 expr_dump(expr
->args
[i
], indent
+ 2);
324 void pet_expr_dump(struct pet_expr
*expr
)
329 /* Does "expr" represent an access to an unnamed space, i.e.,
330 * does it represent an affine expression?
332 int pet_expr_is_affine(struct pet_expr
*expr
)
338 if (expr
->type
!= pet_expr_access
)
341 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
348 /* Return 1 if the two pet_exprs are equivalent.
350 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
354 if (!expr1
|| !expr2
)
357 if (expr1
->type
!= expr2
->type
)
359 if (expr1
->n_arg
!= expr2
->n_arg
)
361 for (i
= 0; i
< expr1
->n_arg
; ++i
)
362 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
364 switch (expr1
->type
) {
365 case pet_expr_double
:
366 if (expr1
->d
!= expr2
->d
)
369 case pet_expr_access
:
370 if (expr1
->acc
.read
!= expr2
->acc
.read
)
372 if (expr1
->acc
.write
!= expr2
->acc
.write
)
374 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
376 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
380 case pet_expr_binary
:
381 case pet_expr_ternary
:
382 if (expr1
->op
!= expr2
->op
)
386 if (strcmp(expr1
->name
, expr2
->name
))
394 /* Add extra conditions on the parameters to all access relations in "expr".
396 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
397 __isl_take isl_set
*cond
)
404 for (i
= 0; i
< expr
->n_arg
; ++i
) {
405 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
411 if (expr
->type
== pet_expr_access
) {
412 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
414 if (!expr
->acc
.access
)
422 return pet_expr_free(expr
);
425 /* Modify all access relations in "expr" by calling "fn" on them.
427 struct pet_expr
*pet_expr_foreach_access(struct pet_expr
*expr
,
428 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
436 for (i
= 0; i
< expr
->n_arg
; ++i
) {
437 expr
->args
[i
] = pet_expr_foreach_access(expr
->args
[i
], fn
, user
);
439 return pet_expr_free(expr
);
442 if (expr
->type
== pet_expr_access
) {
443 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
444 if (!expr
->acc
.access
)
445 return pet_expr_free(expr
);
451 /* Modify all expressions of type pet_expr_access in "expr"
452 * by calling "fn" on them.
454 struct pet_expr
*pet_expr_foreach_access_expr(struct pet_expr
*expr
,
455 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
463 for (i
= 0; i
< expr
->n_arg
; ++i
) {
464 expr
->args
[i
] = pet_expr_foreach_access_expr(expr
->args
[i
],
467 return pet_expr_free(expr
);
470 if (expr
->type
== pet_expr_access
)
471 expr
= fn(expr
, user
);
476 /* Modify the given access relation based on the given iteration space
478 * If the access has any arguments then the domain of the access relation
479 * is a wrapped mapping from the iteration space to the space of
480 * argument values. We only need to change the domain of this wrapped
481 * mapping, so we extend the input transformation with an identity mapping
482 * on the space of argument values.
484 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
487 isl_map
*update
= user
;
490 update
= isl_map_copy(update
);
492 dim
= isl_map_get_space(access
);
493 dim
= isl_space_domain(dim
);
494 if (!isl_space_is_wrapping(dim
))
498 dim
= isl_space_unwrap(dim
);
499 dim
= isl_space_range(dim
);
500 dim
= isl_space_map_from_set(dim
);
501 id
= isl_map_identity(dim
);
502 update
= isl_map_product(update
, id
);
505 return isl_map_apply_domain(access
, update
);
508 /* Modify all access relations in "expr" based on the given iteration space
511 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
512 __isl_take isl_map
*update
)
514 expr
= pet_expr_foreach_access(expr
, &update_domain
, update
);
515 isl_map_free(update
);
519 /* Construct a pet_stmt with given line number and statement
520 * number from a pet_expr.
521 * The initial iteration domain is the zero-dimensional universe.
522 * The name of the domain is given by "label" if it is non-NULL.
523 * Otherwise, the name is constructed as S_<id>.
524 * The domains of all access relations are modified to refer
525 * to the statement iteration domain.
527 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
528 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
530 struct pet_stmt
*stmt
;
540 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
544 dim
= isl_space_set_alloc(ctx
, 0, 0);
546 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
548 snprintf(name
, sizeof(name
), "S_%d", id
);
549 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
551 dom
= isl_set_universe(isl_space_copy(dim
));
552 sched
= isl_map_from_domain(isl_set_copy(dom
));
554 dim
= isl_space_from_range(dim
);
555 add_name
= isl_map_universe(dim
);
556 expr
= expr_update_domain(expr
, add_name
);
560 stmt
->schedule
= sched
;
563 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
564 return pet_stmt_free(stmt
);
569 return pet_expr_free(expr
);
572 void *pet_stmt_free(struct pet_stmt
*stmt
)
579 isl_set_free(stmt
->domain
);
580 isl_map_free(stmt
->schedule
);
581 pet_expr_free(stmt
->body
);
583 for (i
= 0; i
< stmt
->n_arg
; ++i
)
584 pet_expr_free(stmt
->args
[i
]);
591 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
598 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
599 fprintf(stderr
, "%*s", indent
, "");
600 isl_set_dump(stmt
->domain
);
601 fprintf(stderr
, "%*s", indent
, "");
602 isl_map_dump(stmt
->schedule
);
603 expr_dump(stmt
->body
, indent
);
604 for (i
= 0; i
< stmt
->n_arg
; ++i
)
605 expr_dump(stmt
->args
[i
], indent
+ 2);
608 void pet_stmt_dump(struct pet_stmt
*stmt
)
613 void *pet_array_free(struct pet_array
*array
)
618 isl_set_free(array
->context
);
619 isl_set_free(array
->extent
);
620 isl_set_free(array
->value_bounds
);
621 free(array
->element_type
);
627 void pet_array_dump(struct pet_array
*array
)
632 isl_set_dump(array
->context
);
633 isl_set_dump(array
->extent
);
634 isl_set_dump(array
->value_bounds
);
635 fprintf(stderr
, "%s %s\n", array
->element_type
,
636 array
->live_out
? "live-out" : "");
639 /* Construct a pet_scop with room for n statements.
641 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
644 struct pet_scop
*scop
;
646 scop
= isl_calloc_type(ctx
, struct pet_scop
);
650 space
= isl_space_params_alloc(ctx
, 0);
651 scop
->context
= isl_set_universe(isl_space_copy(space
));
652 scop
->context_value
= isl_set_universe(space
);
653 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
654 if (!scop
->context
|| !scop
->stmts
)
655 return pet_scop_free(scop
);
662 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
664 return scop_alloc(ctx
, 0);
667 /* Update "context" with respect to the valid parameter values for "access".
669 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
670 __isl_take isl_set
*context
)
672 context
= isl_set_intersect(context
,
673 isl_map_params(isl_map_copy(access
)));
677 /* Update "context" with respect to the valid parameter values for "expr".
679 * If "expr" represents a ternary operator, then a parameter value
680 * needs to be valid for the condition and for at least one of the
681 * remaining two arguments.
682 * If the condition is an affine expression, then we can be a bit more specific.
683 * The parameter then has to be valid for the second argument for
684 * non-zero accesses and valid for the third argument for zero accesses.
686 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
687 __isl_take isl_set
*context
)
691 if (expr
->type
== pet_expr_ternary
) {
693 isl_set
*context1
, *context2
;
695 is_aff
= pet_expr_is_affine(expr
->args
[0]);
699 context
= expr_extract_context(expr
->args
[0], context
);
700 context1
= expr_extract_context(expr
->args
[1],
701 isl_set_copy(context
));
702 context2
= expr_extract_context(expr
->args
[2], context
);
708 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
709 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
710 zero_set
= isl_map_params(access
);
711 context1
= isl_set_subtract(context1
,
712 isl_set_copy(zero_set
));
713 context2
= isl_set_intersect(context2
, zero_set
);
716 context
= isl_set_union(context1
, context2
);
717 context
= isl_set_coalesce(context
);
722 for (i
= 0; i
< expr
->n_arg
; ++i
)
723 context
= expr_extract_context(expr
->args
[i
], context
);
725 if (expr
->type
== pet_expr_access
)
726 context
= access_extract_context(expr
->acc
.access
, context
);
730 isl_set_free(context
);
734 /* Update "context" with respect to the valid parameter values for "stmt".
736 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
737 __isl_take isl_set
*context
)
741 for (i
= 0; i
< stmt
->n_arg
; ++i
)
742 context
= expr_extract_context(stmt
->args
[i
], context
);
744 context
= expr_extract_context(stmt
->body
, context
);
749 /* Construct a pet_scop that contains the given pet_stmt.
751 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
753 struct pet_scop
*scop
;
758 scop
= scop_alloc(ctx
, 1);
760 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
764 scop
->stmts
[0] = stmt
;
773 /* Construct a pet_scop that contains the arrays and the statements
774 * in "scop1" and "scop2".
776 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
777 struct pet_scop
*scop2
)
780 struct pet_scop
*scop
;
782 if (!scop1
|| !scop2
)
785 if (scop1
->n_stmt
== 0) {
786 pet_scop_free(scop1
);
790 if (scop2
->n_stmt
== 0) {
791 pet_scop_free(scop2
);
795 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
799 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
800 scop1
->n_array
+ scop2
->n_array
);
803 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
805 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
806 scop
->stmts
[i
] = scop1
->stmts
[i
];
807 scop1
->stmts
[i
] = NULL
;
810 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
811 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
812 scop2
->stmts
[i
] = NULL
;
815 for (i
= 0; i
< scop1
->n_array
; ++i
) {
816 scop
->arrays
[i
] = scop1
->arrays
[i
];
817 scop1
->arrays
[i
] = NULL
;
820 for (i
= 0; i
< scop2
->n_array
; ++i
) {
821 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
822 scop2
->arrays
[i
] = NULL
;
825 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
826 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
828 pet_scop_free(scop1
);
829 pet_scop_free(scop2
);
832 pet_scop_free(scop1
);
833 pet_scop_free(scop2
);
837 void *pet_scop_free(struct pet_scop
*scop
)
843 isl_set_free(scop
->context
);
844 isl_set_free(scop
->context_value
);
846 for (i
= 0; i
< scop
->n_array
; ++i
)
847 pet_array_free(scop
->arrays
[i
]);
850 for (i
= 0; i
< scop
->n_stmt
; ++i
)
851 pet_stmt_free(scop
->stmts
[i
]);
857 void pet_scop_dump(struct pet_scop
*scop
)
864 isl_set_dump(scop
->context
);
865 isl_set_dump(scop
->context_value
);
866 for (i
= 0; i
< scop
->n_array
; ++i
)
867 pet_array_dump(scop
->arrays
[i
]);
868 for (i
= 0; i
< scop
->n_stmt
; ++i
)
869 pet_stmt_dump(scop
->stmts
[i
]);
872 /* Return 1 if the two pet_arrays are equivalent.
874 * We don't compare element_size as this may be target dependent.
876 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
878 if (!array1
|| !array2
)
881 if (!isl_set_is_equal(array1
->context
, array2
->context
))
883 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
885 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
887 if (array1
->value_bounds
&&
888 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
890 if (strcmp(array1
->element_type
, array2
->element_type
))
892 if (array1
->live_out
!= array2
->live_out
)
894 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
900 /* Return 1 if the two pet_stmts are equivalent.
902 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
906 if (!stmt1
|| !stmt2
)
909 if (stmt1
->line
!= stmt2
->line
)
911 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
913 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
915 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
917 if (stmt1
->n_arg
!= stmt2
->n_arg
)
919 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
920 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
927 /* Return 1 if the two pet_scops are equivalent.
929 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
933 if (!scop1
|| !scop2
)
936 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
938 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
941 if (scop1
->n_array
!= scop2
->n_array
)
943 for (i
= 0; i
< scop1
->n_array
; ++i
)
944 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
947 if (scop1
->n_stmt
!= scop2
->n_stmt
)
949 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
950 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
956 /* Prefix the schedule of "stmt" with an extra dimension with constant
959 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
964 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
965 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
967 return pet_stmt_free(stmt
);
972 /* Prefix the schedules of all statements in "scop" with an extra
973 * dimension with constant value "pos".
975 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
982 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
983 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
985 return pet_scop_free(scop
);
991 /* Data used in embed_access.
992 * extend adds an iterator to the iteration domain
993 * var_id represents the induction variable of the corresponding loop
995 struct pet_embed_access
{
1000 /* Embed the access relation in an extra outer loop.
1002 * We first update the iteration domain to insert the extra dimension.
1004 * If the access refers to the induction variable, then it is
1005 * turned into an access to the set of integers with index (and value)
1006 * equal to the induction variable.
1008 * If the induction variable appears in the constraints (as a parameter),
1009 * then the parameter is equated to the newly introduced iteration
1010 * domain dimension and subsequently projected out.
1012 * Similarly, if the accessed array is a virtual array (with user
1013 * pointer equal to NULL), as created by create_test_access,
1014 * then it is extended along with the domain of the access.
1016 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
1019 struct pet_embed_access
*data
= user
;
1020 isl_id
*array_id
= NULL
;
1023 access
= update_domain(access
, data
->extend
);
1025 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1026 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1027 if (array_id
== data
->var_id
||
1028 (array_id
&& !isl_id_get_user(array_id
))) {
1029 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1030 access
= isl_map_equate(access
,
1031 isl_dim_in
, 0, isl_dim_out
, 0);
1032 if (array_id
!= data
->var_id
)
1033 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1034 isl_id_copy(array_id
));
1036 isl_id_free(array_id
);
1038 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1040 access
= isl_map_equate(access
,
1041 isl_dim_param
, pos
, isl_dim_in
, 0);
1042 access
= isl_map_project_out(access
, isl_dim_param
, pos
, 1);
1044 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1045 isl_id_copy(data
->var_id
));
1050 /* Embed all access relations in "expr" in an extra loop.
1051 * "extend" inserts an outer loop iterator in the iteration domains.
1052 * "var_id" represents the induction variable.
1054 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1055 __isl_take isl_map
*extend
, __isl_keep isl_id
*var_id
)
1057 struct pet_embed_access data
= { .extend
= extend
, .var_id
= var_id
};
1059 expr
= pet_expr_foreach_access(expr
, &embed_access
, &data
);
1060 isl_map_free(extend
);
1064 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1065 * "dom" and schedule "sched". "var_id" represents the induction variable
1068 * The iteration domain and schedule of the statement are updated
1069 * according to the iteration domain and schedule of the new loop.
1070 * If stmt->domain is a wrapped map, then the iteration domain
1071 * is the domain of this map, so we need to be careful to adjust
1074 * If the induction variable appears in the constraints (as a parameter)
1075 * of the current iteration domain or the schedule of the statement,
1076 * then the parameter is equated to the newly introduced iteration
1077 * domain dimension and subsequently projected out.
1079 * Finally, all access relations are updated based on the extra loop.
1081 struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
, __isl_take isl_set
*dom
,
1082 __isl_take isl_map
*sched
, __isl_take isl_id
*var_id
)
1093 if (isl_set_is_wrapping(stmt
->domain
)) {
1098 map
= isl_set_unwrap(stmt
->domain
);
1099 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1100 ran_dim
= isl_space_range(isl_map_get_space(map
));
1101 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1102 isl_set_universe(ran_dim
));
1103 map
= isl_map_flat_domain_product(ext
, map
);
1104 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1105 isl_id_copy(stmt_id
));
1106 dim
= isl_space_domain(isl_map_get_space(map
));
1107 stmt
->domain
= isl_map_wrap(map
);
1109 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1110 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1112 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1113 isl_id_copy(stmt_id
));
1114 dim
= isl_set_get_space(stmt
->domain
);
1117 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1119 stmt
->domain
= isl_set_equate(stmt
->domain
,
1120 isl_dim_param
, pos
, isl_dim_set
, 0);
1121 stmt
->domain
= isl_set_project_out(stmt
->domain
,
1122 isl_dim_param
, pos
, 1);
1125 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1126 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1127 isl_dim_in
, stmt_id
);
1129 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1131 stmt
->schedule
= isl_map_equate(stmt
->schedule
,
1132 isl_dim_param
, pos
, isl_dim_in
, 0);
1133 stmt
->schedule
= isl_map_project_out(stmt
->schedule
,
1134 isl_dim_param
, pos
, 1);
1137 dim
= isl_space_map_from_set(dim
);
1138 extend
= isl_map_identity(dim
);
1139 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1140 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1141 isl_map_get_tuple_id(extend
, isl_dim_out
));
1142 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1143 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1144 isl_map_copy(extend
), var_id
);
1145 stmt
->body
= expr_embed(stmt
->body
, extend
, var_id
);
1148 isl_id_free(var_id
);
1150 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1152 return pet_stmt_free(stmt
);
1153 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1154 return pet_stmt_free(stmt
);
1158 isl_map_free(sched
);
1159 isl_id_free(var_id
);
1163 /* Embed the given pet_array in an extra outer loop with iteration domain
1165 * This embedding only has an effect on virtual arrays (those with
1166 * user pointer equal to NULL), which need to be extended along with
1167 * the iteration domain.
1169 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1170 __isl_take isl_set
*dom
)
1172 isl_id
*array_id
= NULL
;
1177 if (isl_set_has_tuple_id(array
->extent
))
1178 array_id
= isl_set_get_tuple_id(array
->extent
);
1180 if (array_id
&& !isl_id_get_user(array_id
)) {
1181 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1182 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1185 isl_id_free(array_id
);
1194 /* Project out all unnamed parameters from "set" and return the result.
1196 static __isl_give isl_set
*set_project_out_unnamed_params(
1197 __isl_take isl_set
*set
)
1201 n
= isl_set_dim(set
, isl_dim_param
);
1202 for (i
= n
- 1; i
>= 0; --i
) {
1203 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1205 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1211 /* Update the context with respect to an embedding into a loop
1212 * with iteration domain "dom" and induction variable "id".
1214 * If the current context is independent of "id", we don't need
1216 * Otherwise, a parameter value is invalid for the embedding if
1217 * any of the corresponding iterator values is invalid.
1218 * That is, a parameter value is valid only if all the corresponding
1219 * iterator values are valid.
1220 * We therefore compute the set of parameters
1222 * forall i in dom : valid (i)
1226 * not exists i in dom : not valid(i)
1230 * not exists i in dom \ valid(i)
1232 * If there are any unnamed parameters in "dom", then we consider
1233 * a parameter value to be valid if it is valid for any value of those
1234 * unnamed parameters. They are therefore projected out at the end.
1236 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1237 __isl_keep isl_set
*dom
, __isl_keep isl_id
*id
)
1241 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1245 context
= isl_set_from_params(context
);
1246 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1247 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1248 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1249 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1250 context
= isl_set_params(context
);
1251 context
= isl_set_complement(context
);
1252 context
= set_project_out_unnamed_params(context
);
1256 /* Embed all statements and arrays in "scop" in an extra outer loop
1257 * with iteration domain "dom" and schedule "sched".
1258 * "id" represents the induction variable of the loop.
1260 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1261 __isl_take isl_map
*sched
, __isl_take isl_id
*id
)
1268 scop
->context
= context_embed(scop
->context
, dom
, id
);
1272 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1273 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1275 isl_map_copy(sched
), isl_id_copy(id
));
1276 if (!scop
->stmts
[i
])
1280 for (i
= 0; i
< scop
->n_array
; ++i
) {
1281 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1283 if (!scop
->arrays
[i
])
1288 isl_map_free(sched
);
1293 isl_map_free(sched
);
1295 return pet_scop_free(scop
);
1298 /* Add extra conditions on the parameters to iteration domain of "stmt".
1300 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1301 __isl_take isl_set
*cond
)
1306 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1311 return pet_stmt_free(stmt
);
1314 /* Add extra conditions on the parameters to all iteration domains.
1316 * A parameter value is valid for the result if it was valid
1317 * for the original scop and satisfies "cond" or if it does
1318 * not satisfy "cond" as in this case the scop is not executed
1319 * and the original constraints on the parameters are irrelevant.
1321 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1322 __isl_take isl_set
*cond
)
1329 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1330 scop
->context
= isl_set_union(scop
->context
,
1331 isl_set_complement(isl_set_copy(cond
)));
1332 scop
->context
= isl_set_coalesce(scop
->context
);
1333 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1337 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1338 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1339 isl_set_copy(cond
));
1340 if (!scop
->stmts
[i
])
1348 return pet_scop_free(scop
);
1351 /* Make the statements "stmt" depend on the value of "test"
1352 * being equal to "satisfied" by adjusting stmt->domain.
1354 * We insert an argument corresponding to a read to "test"
1355 * from the iteration domain of "stmt" in front of the list of arguments.
1356 * We also insert a corresponding output dimension in the wrapped
1357 * map contained in stmt->domain, with value set to "satisfied".
1359 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1360 __isl_take isl_map
*test
, int satisfied
)
1371 if (isl_set_is_wrapping(stmt
->domain
))
1372 map
= isl_set_unwrap(stmt
->domain
);
1374 map
= isl_map_from_domain(stmt
->domain
);
1375 map
= isl_map_insert_dims(map
, isl_dim_out
, 0, 1);
1376 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1377 map
= isl_map_set_dim_id(map
, isl_dim_out
, 0, id
);
1378 map
= isl_map_fix_si(map
, isl_dim_out
, 0, satisfied
);
1379 dom
= isl_set_universe(isl_space_domain(isl_map_get_space(map
)));
1380 test
= isl_map_apply_domain(test
, isl_map_from_range(dom
));
1382 stmt
->domain
= isl_map_wrap(map
);
1384 ctx
= isl_map_get_ctx(test
);
1386 stmt
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1390 struct pet_expr
**args
;
1391 args
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + stmt
->n_arg
);
1394 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1395 args
[1 + i
] = stmt
->args
[i
];
1400 stmt
->args
[0] = pet_expr_from_access(isl_map_copy(test
));
1408 return pet_stmt_free(stmt
);
1411 /* Make all statements in "scop" depend on the value of "test"
1412 * being equal to "satisfied" by adjusting their domains.
1414 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1415 __isl_take isl_map
*test
, int satisfied
)
1422 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1423 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
1424 isl_map_copy(test
), satisfied
);
1425 if (!scop
->stmts
[i
])
1433 return pet_scop_free(scop
);
1436 /* Add all parameters in "expr" to "dim" and return the result.
1438 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
1439 __isl_take isl_space
*dim
)
1445 for (i
= 0; i
< expr
->n_arg
; ++i
)
1447 dim
= expr_collect_params(expr
->args
[i
], dim
);
1449 if (expr
->type
== pet_expr_access
)
1450 dim
= isl_space_align_params(dim
,
1451 isl_map_get_space(expr
->acc
.access
));
1455 isl_space_free(dim
);
1456 return pet_expr_free(expr
);
1459 /* Add all parameters in "stmt" to "dim" and return the result.
1461 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
1462 __isl_take isl_space
*dim
)
1467 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
1468 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
1469 dim
= expr_collect_params(stmt
->body
, dim
);
1473 isl_space_free(dim
);
1474 return pet_stmt_free(stmt
);
1477 /* Add all parameters in "array" to "dim" and return the result.
1479 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1480 __isl_take isl_space
*dim
)
1485 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
1486 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
1490 isl_space_free(dim
);
1491 return pet_array_free(array
);
1494 /* Add all parameters in "scop" to "dim" and return the result.
1496 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1497 __isl_take isl_space
*dim
)
1504 for (i
= 0; i
< scop
->n_array
; ++i
)
1505 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1507 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1508 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1512 isl_space_free(dim
);
1513 return pet_scop_free(scop
);
1516 /* Add all parameters in "dim" to all access relations in "expr".
1518 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1519 __isl_take isl_space
*dim
)
1526 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1528 expr_propagate_params(expr
->args
[i
],
1529 isl_space_copy(dim
));
1534 if (expr
->type
== pet_expr_access
) {
1535 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1536 isl_space_copy(dim
));
1537 if (!expr
->acc
.access
)
1541 isl_space_free(dim
);
1544 isl_space_free(dim
);
1545 return pet_expr_free(expr
);
1548 /* Add all parameters in "dim" to the domain, schedule and
1549 * all access relations in "stmt".
1551 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1552 __isl_take isl_space
*dim
)
1557 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
1558 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1559 isl_space_copy(dim
));
1560 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
1562 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1565 isl_space_free(dim
);
1568 isl_space_free(dim
);
1569 return pet_stmt_free(stmt
);
1572 /* Add all parameters in "dim" to "array".
1574 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1575 __isl_take isl_space
*dim
)
1580 array
->context
= isl_set_align_params(array
->context
,
1581 isl_space_copy(dim
));
1582 array
->extent
= isl_set_align_params(array
->extent
,
1583 isl_space_copy(dim
));
1584 if (array
->value_bounds
) {
1585 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1586 isl_space_copy(dim
));
1587 if (!array
->value_bounds
)
1591 if (!array
->context
|| !array
->extent
)
1594 isl_space_free(dim
);
1597 isl_space_free(dim
);
1598 return pet_array_free(array
);
1601 /* Add all parameters in "dim" to "scop".
1603 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1604 __isl_take isl_space
*dim
)
1611 for (i
= 0; i
< scop
->n_array
; ++i
) {
1612 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1613 isl_space_copy(dim
));
1614 if (!scop
->arrays
[i
])
1618 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1619 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1620 isl_space_copy(dim
));
1621 if (!scop
->stmts
[i
])
1625 isl_space_free(dim
);
1628 isl_space_free(dim
);
1629 return pet_scop_free(scop
);
1632 /* Update all isl_sets and isl_maps in "scop" such that they all
1633 * have the same parameters.
1635 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1642 dim
= isl_set_get_space(scop
->context
);
1643 dim
= scop_collect_params(scop
, dim
);
1645 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
1646 scop
= scop_propagate_params(scop
, dim
);
1651 /* Check if the given access relation accesses a (0D) array that corresponds
1652 * to one of the parameters in "dim". If so, replace the array access
1653 * by an access to the set of integers with as index (and value)
1656 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1657 __isl_take isl_space
*dim
)
1659 isl_id
*array_id
= NULL
;
1662 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1663 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1664 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1666 isl_space_free(dim
);
1669 isl_id_free(array_id
);
1673 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1675 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1676 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1679 isl_id_free(array_id
);
1681 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1682 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1687 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1688 * in "dim" by a value equal to the corresponding parameter.
1690 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1691 __isl_take isl_space
*dim
)
1698 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1700 expr_detect_parameter_accesses(expr
->args
[i
],
1701 isl_space_copy(dim
));
1706 if (expr
->type
== pet_expr_access
) {
1707 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1708 isl_space_copy(dim
));
1709 if (!expr
->acc
.access
)
1713 isl_space_free(dim
);
1716 isl_space_free(dim
);
1717 return pet_expr_free(expr
);
1720 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1721 * in "dim" by a value equal to the corresponding parameter.
1723 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1724 __isl_take isl_space
*dim
)
1729 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1730 isl_space_copy(dim
));
1732 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1735 isl_space_free(dim
);
1738 isl_space_free(dim
);
1739 return pet_stmt_free(stmt
);
1742 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1743 * in "dim" by a value equal to the corresponding parameter.
1745 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1746 __isl_take isl_space
*dim
)
1753 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1754 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1755 isl_space_copy(dim
));
1756 if (!scop
->stmts
[i
])
1760 isl_space_free(dim
);
1763 isl_space_free(dim
);
1764 return pet_scop_free(scop
);
1767 /* Replace all accesses to (0D) arrays that correspond to any of
1768 * the parameters used in "scop" by a value equal
1769 * to the corresponding parameter.
1771 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1778 dim
= isl_set_get_space(scop
->context
);
1779 dim
= scop_collect_params(scop
, dim
);
1781 scop
= scop_detect_parameter_accesses(scop
, dim
);
1786 /* Add all read access relations (if "read" is set) and/or all write
1787 * access relations (if "write" is set) to "accesses" and return the result.
1789 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1790 int read
, int write
, __isl_take isl_union_map
*accesses
)
1799 for (i
= 0; i
< expr
->n_arg
; ++i
)
1800 accesses
= expr_collect_accesses(expr
->args
[i
],
1801 read
, write
, accesses
);
1803 if (expr
->type
== pet_expr_access
&&
1804 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
1805 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1806 accesses
= isl_union_map_add_map(accesses
,
1807 isl_map_copy(expr
->acc
.access
));
1812 /* Collect and return all read access relations (if "read" is set)
1813 * and/or all write * access relations (if "write" is set) in "stmt".
1815 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1816 int read
, int write
, __isl_take isl_space
*dim
)
1818 isl_union_map
*accesses
;
1823 accesses
= isl_union_map_empty(dim
);
1824 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1825 accesses
= isl_union_map_intersect_domain(accesses
,
1826 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1831 /* Collect and return all read access relations (if "read" is set)
1832 * and/or all write * access relations (if "write" is set) in "scop".
1834 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1835 int read
, int write
)
1838 isl_union_map
*accesses
;
1843 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1845 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1846 isl_union_map
*accesses_i
;
1847 isl_space
*dim
= isl_set_get_space(scop
->context
);
1848 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1850 accesses
= isl_union_map_union(accesses
, accesses_i
);
1856 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1858 return scop_collect_accesses(scop
, 1, 0);
1861 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1863 return scop_collect_accesses(scop
, 0, 1);
1866 /* Collect and return the union of iteration domains in "scop".
1868 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
1872 isl_union_set
*domain
;
1877 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
1879 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1880 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
1881 domain
= isl_union_set_add_set(domain
, domain_i
);
1887 /* Collect and return the schedules of the statements in "scop".
1888 * The range is normalized to the maximal number of scheduling
1891 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
1894 isl_map
*schedule_i
;
1895 isl_union_map
*schedule
;
1896 int depth
, max_depth
= 0;
1901 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1903 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1904 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
1905 if (depth
> max_depth
)
1909 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1910 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
1911 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
1912 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
1914 for (j
= depth
; j
< max_depth
; ++j
)
1915 schedule_i
= isl_map_fix_si(schedule_i
,
1917 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
1923 /* Does expression "expr" write to "id"?
1925 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
1930 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1931 int writes
= expr_writes(expr
->args
[i
], id
);
1932 if (writes
< 0 || writes
)
1936 if (expr
->type
!= pet_expr_access
)
1938 if (!expr
->acc
.write
)
1940 if (!isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
))
1943 write_id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
1944 isl_id_free(write_id
);
1949 return write_id
== id
;
1952 /* Does statement "stmt" write to "id"?
1954 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
1956 return expr_writes(stmt
->body
, id
);
1959 /* Is there any write access in "scop" that accesses "id"?
1961 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
1968 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1969 int writes
= stmt_writes(scop
->stmts
[i
], id
);
1970 if (writes
< 0 || writes
)
1977 /* Reset the user pointer on all parameter ids in "set".
1979 static __isl_give isl_set
*set_anonymize(__isl_take isl_set
*set
)
1983 n
= isl_set_dim(set
, isl_dim_param
);
1984 for (i
= 0; i
< n
; ++i
) {
1985 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_param
, i
);
1986 const char *name
= isl_id_get_name(id
);
1987 set
= isl_set_set_dim_name(set
, isl_dim_param
, i
, name
);
1994 /* Reset the user pointer on all parameter ids in "map".
1996 static __isl_give isl_map
*map_anonymize(__isl_take isl_map
*map
)
2000 n
= isl_map_dim(map
, isl_dim_param
);
2001 for (i
= 0; i
< n
; ++i
) {
2002 isl_id
*id
= isl_map_get_dim_id(map
, isl_dim_param
, i
);
2003 const char *name
= isl_id_get_name(id
);
2004 map
= isl_map_set_dim_name(map
, isl_dim_param
, i
, name
);
2011 /* Reset the user pointer on all parameter ids in "array".
2013 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2018 array
->context
= set_anonymize(array
->context
);
2019 array
->extent
= set_anonymize(array
->extent
);
2020 if (!array
->context
|| !array
->extent
)
2021 return pet_array_free(array
);
2026 /* Reset the user pointer on all parameter ids in "access".
2028 static __isl_give isl_map
*access_anonymize(__isl_take isl_map
*access
,
2031 access
= map_anonymize(access
);
2036 /* Reset the user pointer on all parameter ids in "stmt".
2038 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2047 stmt
->domain
= set_anonymize(stmt
->domain
);
2048 stmt
->schedule
= map_anonymize(stmt
->schedule
);
2049 if (!stmt
->domain
|| !stmt
->schedule
)
2050 return pet_stmt_free(stmt
);
2052 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2053 stmt
->args
[i
] = pet_expr_foreach_access(stmt
->args
[i
],
2054 &access_anonymize
, NULL
);
2056 return pet_stmt_free(stmt
);
2059 stmt
->body
= pet_expr_foreach_access(stmt
->body
,
2060 &access_anonymize
, NULL
);
2062 return pet_stmt_free(stmt
);
2067 /* Reset the user pointer on all parameter ids in "scop".
2069 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2076 scop
->context
= set_anonymize(scop
->context
);
2077 scop
->context_value
= set_anonymize(scop
->context_value
);
2078 if (!scop
->context
|| !scop
->context_value
)
2079 return pet_scop_free(scop
);
2081 for (i
= 0; i
< scop
->n_array
; ++i
) {
2082 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2083 if (!scop
->arrays
[i
])
2084 return pet_scop_free(scop
);
2087 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2088 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2089 if (!scop
->stmts
[i
])
2090 return pet_scop_free(scop
);
2096 /* Given a set "domain", return a wrapped relation with the given set
2097 * as domain and a range of dimension "n_arg", where each coordinate
2098 * is either unbounded or, if the corresponding element of args is of
2099 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2101 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
2102 unsigned n_arg
, struct pet_expr
**args
,
2103 __isl_keep isl_union_map
*value_bounds
)
2108 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
2110 map
= isl_map_from_domain(domain
);
2111 space
= isl_map_get_space(map
);
2112 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2114 for (i
= 0; i
< n_arg
; ++i
) {
2116 struct pet_expr
*arg
= args
[i
];
2120 map_i
= isl_map_universe(isl_space_copy(space
));
2121 if (arg
->type
== pet_expr_access
) {
2123 id
= isl_map_get_tuple_id(arg
->acc
.access
, isl_dim_out
);
2124 space2
= isl_space_alloc(ctx
, 0, 0, 1);
2125 space2
= isl_space_set_tuple_id(space2
, isl_dim_in
, id
);
2126 vb
= isl_union_map_extract_map(value_bounds
, space2
);
2127 if (!isl_map_plain_is_empty(vb
))
2128 map_i
= isl_map_intersect_range(map_i
,
2133 map
= isl_map_flat_range_product(map
, map_i
);
2135 isl_space_free(space
);
2137 return isl_map_wrap(map
);
2140 /* Data used in access_gist() callback.
2142 struct pet_access_gist_data
{
2144 isl_union_map
*value_bounds
;
2147 /* Given an expression "expr" of type pet_expr_access, compute
2148 * the gist of the associated access relation with respect to
2149 * data->domain and the bounds on the values of the arguments
2150 * of the expression.
2152 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
2154 struct pet_access_gist_data
*data
= user
;
2157 domain
= isl_set_copy(data
->domain
);
2158 if (expr
->n_arg
> 0)
2159 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
2160 data
->value_bounds
);
2162 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
, domain
);
2163 if (!expr
->acc
.access
)
2164 return pet_expr_free(expr
);
2169 /* Compute the gist of the iteration domain and all access relations
2170 * of "stmt" based on the constraints on the parameters specified by "context"
2171 * and the constraints on the values of nested accesses specified
2172 * by "value_bounds".
2174 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2175 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2180 struct pet_access_gist_data data
;
2185 data
.domain
= isl_set_copy(stmt
->domain
);
2186 data
.value_bounds
= value_bounds
;
2187 if (stmt
->n_arg
> 0)
2188 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
2190 data
.domain
= isl_set_intersect_params(data
.domain
,
2191 isl_set_copy(context
));
2193 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2194 stmt
->args
[i
] = pet_expr_foreach_access_expr(stmt
->args
[i
],
2195 &access_gist
, &data
);
2200 stmt
->body
= pet_expr_foreach_access_expr(stmt
->body
,
2201 &access_gist
, &data
);
2205 isl_set_free(data
.domain
);
2207 space
= isl_set_get_space(stmt
->domain
);
2208 if (isl_space_is_wrapping(space
))
2209 space
= isl_space_domain(isl_space_unwrap(space
));
2210 domain
= isl_set_universe(space
);
2211 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2212 if (stmt
->n_arg
> 0)
2213 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
2215 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2217 return pet_stmt_free(stmt
);
2221 isl_set_free(data
.domain
);
2222 return pet_stmt_free(stmt
);
2225 /* Compute the gist of the extent of the array
2226 * based on the constraints on the parameters specified by "context".
2228 static struct pet_array
*array_gist(struct pet_array
*array
,
2229 __isl_keep isl_set
*context
)
2234 array
->extent
= isl_set_gist_params(array
->extent
,
2235 isl_set_copy(context
));
2237 return pet_array_free(array
);
2242 /* Compute the gist of all sets and relations in "scop"
2243 * based on the constraints on the parameters specified by "scop->context"
2244 * and the constraints on the values of nested accesses specified
2245 * by "value_bounds".
2247 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
2248 __isl_keep isl_union_map
*value_bounds
)
2255 scop
->context
= isl_set_coalesce(scop
->context
);
2257 return pet_scop_free(scop
);
2259 for (i
= 0; i
< scop
->n_array
; ++i
) {
2260 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
2261 if (!scop
->arrays
[i
])
2262 return pet_scop_free(scop
);
2265 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2266 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
2268 if (!scop
->stmts
[i
])
2269 return pet_scop_free(scop
);
2275 /* Intersect the context of "scop" with "context".
2276 * To ensure that we don't introduce any unnamed parameters in
2277 * the context of "scop", we first remove the unnamed parameters
2280 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
2281 __isl_take isl_set
*context
)
2286 context
= set_project_out_unnamed_params(context
);
2287 scop
->context
= isl_set_intersect(scop
->context
, context
);
2289 return pet_scop_free(scop
);
2293 isl_set_free(context
);
2294 return pet_scop_free(scop
);