2 * Copyright 2011 Leiden University. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials provided
14 * with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
20 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
23 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 * The views and conclusions contained in the software and documentation
29 * are those of the authors and should not be interpreted as
30 * representing official policies, either expressed or implied, of
34 #include <isl/constraint.h>
35 #include <isl/union_set.h>
39 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
41 static char *type_str
[] = {
42 [pet_expr_access
] = "access",
43 [pet_expr_call
] = "call",
44 [pet_expr_double
] = "double",
45 [pet_expr_unary
] = "unary",
46 [pet_expr_binary
] = "binary",
47 [pet_expr_ternary
] = "ternary"
50 static char *op_str
[] = {
51 [pet_op_add_assign
] = "+=",
52 [pet_op_sub_assign
] = "-=",
53 [pet_op_mul_assign
] = "*=",
54 [pet_op_div_assign
] = "/=",
55 [pet_op_assign
] = "=",
67 const char *pet_op_str(enum pet_op_type op
)
72 const char *pet_type_str(enum pet_expr_type type
)
74 return type_str
[type
];
77 enum pet_op_type
pet_str_op(const char *str
)
81 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
82 if (!strcmp(op_str
[i
], str
))
88 enum pet_expr_type
pet_str_type(const char *str
)
92 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
93 if (!strcmp(type_str
[i
], str
))
99 /* Construct a pet_expr from an access relation.
100 * By default, it is considered to be a read access.
102 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
104 isl_ctx
*ctx
= isl_map_get_ctx(access
);
105 struct pet_expr
*expr
;
109 expr
= isl_calloc_type(ctx
, struct pet_expr
);
113 expr
->type
= pet_expr_access
;
114 expr
->acc
.access
= access
;
120 isl_map_free(access
);
124 /* Construct a unary pet_expr that performs "op" on "arg".
126 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
127 struct pet_expr
*arg
)
129 struct pet_expr
*expr
;
133 expr
= isl_alloc_type(ctx
, struct pet_expr
);
137 expr
->type
= pet_expr_unary
;
140 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
143 expr
->args
[pet_un_arg
] = arg
;
151 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
153 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
154 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
156 struct pet_expr
*expr
;
160 expr
= isl_alloc_type(ctx
, struct pet_expr
);
164 expr
->type
= pet_expr_binary
;
167 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
170 expr
->args
[pet_bin_lhs
] = lhs
;
171 expr
->args
[pet_bin_rhs
] = rhs
;
180 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
182 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
183 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
185 struct pet_expr
*expr
;
187 if (!cond
|| !lhs
|| !rhs
)
189 expr
= isl_alloc_type(ctx
, struct pet_expr
);
193 expr
->type
= pet_expr_ternary
;
195 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
198 expr
->args
[pet_ter_cond
] = cond
;
199 expr
->args
[pet_ter_true
] = lhs
;
200 expr
->args
[pet_ter_false
] = rhs
;
210 /* Construct a call pet_expr that calls function "name" with "n_arg"
211 * arguments. The caller is responsible for filling in the arguments.
213 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
216 struct pet_expr
*expr
;
218 expr
= isl_alloc_type(ctx
, struct pet_expr
);
222 expr
->type
= pet_expr_call
;
224 expr
->name
= strdup(name
);
225 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
226 if (!expr
->name
|| !expr
->args
)
227 return pet_expr_free(expr
);
232 /* Construct a pet_expr that represents the double "d".
234 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
236 struct pet_expr
*expr
;
238 expr
= isl_calloc_type(ctx
, struct pet_expr
);
242 expr
->type
= pet_expr_double
;
248 void *pet_expr_free(struct pet_expr
*expr
)
255 for (i
= 0; i
< expr
->n_arg
; ++i
)
256 pet_expr_free(expr
->args
[i
]);
259 switch (expr
->type
) {
260 case pet_expr_access
:
261 isl_map_free(expr
->acc
.access
);
266 case pet_expr_double
:
268 case pet_expr_binary
:
269 case pet_expr_ternary
:
277 static void expr_dump(struct pet_expr
*expr
, int indent
)
284 fprintf(stderr
, "%*s", indent
, "");
286 switch (expr
->type
) {
287 case pet_expr_double
:
288 fprintf(stderr
, "%g\n", expr
->d
);
290 case pet_expr_access
:
291 isl_map_dump(expr
->acc
.access
);
292 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
294 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
295 "", expr
->acc
.write
);
296 for (i
= 0; i
< expr
->n_arg
; ++i
)
297 expr_dump(expr
->args
[i
], indent
+ 2);
300 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
301 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
303 case pet_expr_binary
:
304 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
305 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
306 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
308 case pet_expr_ternary
:
309 fprintf(stderr
, "?:\n");
310 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
311 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
312 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
315 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
316 for (i
= 0; i
< expr
->n_arg
; ++i
)
317 expr_dump(expr
->args
[i
], indent
+ 2);
322 void pet_expr_dump(struct pet_expr
*expr
)
327 /* Return 1 if the two pet_exprs are equivalent.
329 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
333 if (!expr1
|| !expr2
)
336 if (expr1
->type
!= expr2
->type
)
338 if (expr1
->n_arg
!= expr2
->n_arg
)
340 for (i
= 0; i
< expr1
->n_arg
; ++i
)
341 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
343 switch (expr1
->type
) {
344 case pet_expr_double
:
345 if (expr1
->d
!= expr2
->d
)
348 case pet_expr_access
:
349 if (expr1
->acc
.read
!= expr2
->acc
.read
)
351 if (expr1
->acc
.write
!= expr2
->acc
.write
)
353 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
355 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
359 case pet_expr_binary
:
360 case pet_expr_ternary
:
361 if (expr1
->op
!= expr2
->op
)
365 if (strcmp(expr1
->name
, expr2
->name
))
373 /* Add extra conditions on the parameters to all access relations in "expr".
375 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
376 __isl_take isl_set
*cond
)
383 for (i
= 0; i
< expr
->n_arg
; ++i
) {
384 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
390 if (expr
->type
== pet_expr_access
) {
391 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
393 if (!expr
->acc
.access
)
401 return pet_expr_free(expr
);
404 /* Modify all access relations in "expr" by calling "fn" on them.
406 static struct pet_expr
*expr_foreach_access(struct pet_expr
*expr
,
407 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
415 for (i
= 0; i
< expr
->n_arg
; ++i
) {
416 expr
->args
[i
] = expr_foreach_access(expr
->args
[i
], fn
, user
);
418 return pet_expr_free(expr
);
421 if (expr
->type
== pet_expr_access
) {
422 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
423 if (!expr
->acc
.access
)
424 return pet_expr_free(expr
);
430 /* Modify the given access relation based on the given iteration space
432 * If the access has any arguments then the domain of the access relation
433 * is a wrapped mapping from the iteration space to the space of
434 * argument values. We only need to change the domain of this wrapped
435 * mapping, so we extend the input transformation with an identity mapping
436 * on the space of argument values.
438 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
441 isl_map
*update
= user
;
444 update
= isl_map_copy(update
);
446 dim
= isl_map_get_space(access
);
447 dim
= isl_space_domain(dim
);
448 if (!isl_space_is_wrapping(dim
))
452 dim
= isl_space_unwrap(dim
);
453 dim
= isl_space_range(dim
);
454 dim
= isl_space_map_from_set(dim
);
455 id
= isl_map_identity(dim
);
456 update
= isl_map_product(update
, id
);
459 return isl_map_apply_domain(access
, update
);
462 /* Modify all access relations in "expr" based on the given iteration space
465 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
466 __isl_take isl_map
*update
)
468 expr
= expr_foreach_access(expr
, &update_domain
, update
);
469 isl_map_free(update
);
473 /* Construct a pet_stmt with given line number and statement
474 * number from a pet_expr.
475 * The initial iteration domain is the zero-dimensional universe.
476 * The name of the domain is given by "label" if it is non-NULL.
477 * Otherwise, the name is constructed as S_<id>.
478 * The domains of all access relations are modified to refer
479 * to the statement iteration domain.
481 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
482 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
484 struct pet_stmt
*stmt
;
494 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
496 return pet_expr_free(expr
);
498 dim
= isl_space_set_alloc(ctx
, 0, 0);
500 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
502 snprintf(name
, sizeof(name
), "S_%d", id
);
503 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
505 dom
= isl_set_universe(isl_space_copy(dim
));
506 sched
= isl_map_from_domain(isl_set_copy(dom
));
508 dim
= isl_space_from_range(dim
);
509 add_name
= isl_map_universe(dim
);
510 expr
= expr_update_domain(expr
, add_name
);
514 stmt
->schedule
= sched
;
517 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
518 return pet_stmt_free(stmt
);
523 void *pet_stmt_free(struct pet_stmt
*stmt
)
530 isl_set_free(stmt
->domain
);
531 isl_map_free(stmt
->schedule
);
532 pet_expr_free(stmt
->body
);
534 for (i
= 0; i
< stmt
->n_arg
; ++i
)
535 pet_expr_free(stmt
->args
[i
]);
542 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
549 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
550 fprintf(stderr
, "%*s", indent
, "");
551 isl_set_dump(stmt
->domain
);
552 fprintf(stderr
, "%*s", indent
, "");
553 isl_map_dump(stmt
->schedule
);
554 expr_dump(stmt
->body
, indent
);
555 for (i
= 0; i
< stmt
->n_arg
; ++i
)
556 expr_dump(stmt
->args
[i
], indent
+ 2);
559 void pet_stmt_dump(struct pet_stmt
*stmt
)
564 void *pet_array_free(struct pet_array
*array
)
569 isl_set_free(array
->context
);
570 isl_set_free(array
->extent
);
571 isl_set_free(array
->value_bounds
);
572 free(array
->element_type
);
578 void pet_array_dump(struct pet_array
*array
)
583 isl_set_dump(array
->context
);
584 isl_set_dump(array
->extent
);
585 isl_set_dump(array
->value_bounds
);
586 fprintf(stderr
, "%s %s\n", array
->element_type
,
587 array
->live_out
? "live-out" : "");
590 /* Construct a pet_scop with room for n statements.
592 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
595 struct pet_scop
*scop
;
597 scop
= isl_calloc_type(ctx
, struct pet_scop
);
601 space
= isl_space_params_alloc(ctx
, 0);
602 scop
->context
= isl_set_universe(isl_space_copy(space
));
603 scop
->context_value
= isl_set_universe(space
);
604 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
605 if (!scop
->context
|| !scop
->stmts
)
606 return pet_scop_free(scop
);
613 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
615 return scop_alloc(ctx
, 0);
618 /* Construct a pet_scop that contains the given pet_stmt.
620 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
622 struct pet_scop
*scop
;
627 scop
= scop_alloc(ctx
, 1);
629 scop
->stmts
[0] = stmt
;
638 /* Construct a pet_scop that contains the arrays and the statements
639 * in "scop1" and "scop2".
641 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
642 struct pet_scop
*scop2
)
645 struct pet_scop
*scop
;
647 if (!scop1
|| !scop2
)
650 if (scop1
->n_stmt
== 0) {
651 pet_scop_free(scop1
);
655 if (scop2
->n_stmt
== 0) {
656 pet_scop_free(scop2
);
660 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
664 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
665 scop1
->n_array
+ scop2
->n_array
);
668 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
670 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
671 scop
->stmts
[i
] = scop1
->stmts
[i
];
672 scop1
->stmts
[i
] = NULL
;
675 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
676 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
677 scop2
->stmts
[i
] = NULL
;
680 for (i
= 0; i
< scop1
->n_array
; ++i
) {
681 scop
->arrays
[i
] = scop1
->arrays
[i
];
682 scop1
->arrays
[i
] = NULL
;
685 for (i
= 0; i
< scop2
->n_array
; ++i
) {
686 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
687 scop2
->arrays
[i
] = NULL
;
690 pet_scop_free(scop1
);
691 pet_scop_free(scop2
);
694 pet_scop_free(scop1
);
695 pet_scop_free(scop2
);
699 void *pet_scop_free(struct pet_scop
*scop
)
705 isl_set_free(scop
->context
);
706 isl_set_free(scop
->context_value
);
708 for (i
= 0; i
< scop
->n_array
; ++i
)
709 pet_array_free(scop
->arrays
[i
]);
712 for (i
= 0; i
< scop
->n_stmt
; ++i
)
713 pet_stmt_free(scop
->stmts
[i
]);
719 void pet_scop_dump(struct pet_scop
*scop
)
726 isl_set_dump(scop
->context
);
727 isl_set_dump(scop
->context_value
);
728 for (i
= 0; i
< scop
->n_array
; ++i
)
729 pet_array_dump(scop
->arrays
[i
]);
730 for (i
= 0; i
< scop
->n_stmt
; ++i
)
731 pet_stmt_dump(scop
->stmts
[i
]);
734 /* Return 1 if the two pet_arrays are equivalent.
736 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
738 if (!array1
|| !array2
)
741 if (!isl_set_is_equal(array1
->context
, array2
->context
))
743 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
745 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
747 if (array1
->value_bounds
&&
748 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
750 if (strcmp(array1
->element_type
, array2
->element_type
))
752 if (array1
->live_out
!= array2
->live_out
)
758 /* Return 1 if the two pet_stmts are equivalent.
760 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
764 if (!stmt1
|| !stmt2
)
767 if (stmt1
->line
!= stmt2
->line
)
769 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
771 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
773 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
775 if (stmt1
->n_arg
!= stmt2
->n_arg
)
777 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
778 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
785 /* Return 1 if the two pet_scops are equivalent.
787 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
791 if (!scop1
|| !scop2
)
794 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
796 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
799 if (scop1
->n_array
!= scop2
->n_array
)
801 for (i
= 0; i
< scop1
->n_array
; ++i
)
802 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
805 if (scop1
->n_stmt
!= scop2
->n_stmt
)
807 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
808 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
814 /* Prefix the schedule of "stmt" with an extra dimension with constant
817 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
822 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
823 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
825 return pet_stmt_free(stmt
);
830 /* Prefix the schedules of all statements in "scop" with an extra
831 * dimension with constant value "pos".
833 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
840 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
841 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
843 return pet_scop_free(scop
);
849 /* Data used in embed_access.
850 * extend adds an iterator to the iteration domain
851 * var_id represents the induction variable of the corresponding loop
853 struct pet_embed_access
{
858 /* Embed the access relation in an extra outer loop.
860 * We first update the iteration domain to insert the extra dimension.
862 * If the access refers to the induction variable, then it is
863 * turned into an access to the set of integers with index (and value)
864 * equal to the induction variable.
866 * If the induction variable appears in the constraints (as a parameter),
867 * then the parameter is equated to the newly introduced iteration
868 * domain dimension and subsequently projected out.
870 * Similarly, if the accessed array is a virtual array (with user
871 * pointer equal to NULL), as created by create_test_access,
872 * then it is extende along with the domain of the access.
874 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
877 struct pet_embed_access
*data
= user
;
878 isl_id
*array_id
= NULL
;
881 access
= update_domain(access
, data
->extend
);
883 if (isl_map_has_tuple_id(access
, isl_dim_out
))
884 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
885 if (array_id
== data
->var_id
||
886 (array_id
&& !isl_id_get_user(array_id
))) {
887 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
888 access
= isl_map_equate(access
,
889 isl_dim_in
, 0, isl_dim_out
, 0);
890 if (array_id
!= data
->var_id
)
891 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
892 isl_id_copy(array_id
));
894 isl_id_free(array_id
);
896 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
898 access
= isl_map_equate(access
,
899 isl_dim_param
, pos
, isl_dim_in
, 0);
900 access
= isl_map_project_out(access
, isl_dim_param
, pos
, 1);
902 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
903 isl_id_copy(data
->var_id
));
908 /* Embed all access relations in "expr" in an extra loop.
909 * "extend" inserts an outer loop iterator in the iteration domains.
910 * "var_id" represents the induction variable.
912 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
913 __isl_take isl_map
*extend
, __isl_keep isl_id
*var_id
)
915 struct pet_embed_access data
= { .extend
= extend
, .var_id
= var_id
};
917 expr
= expr_foreach_access(expr
, &embed_access
, &data
);
918 isl_map_free(extend
);
922 /* Embed the given pet_stmt in an extra outer loop with iteration domain
923 * "dom" and schedule "sched". "var_id" represents the induction variable
926 * The iteration domain and schedule of the statement are updated
927 * according to the iteration domain and schedule of the new loop.
928 * If stmt->domain is a wrapped map, then the iteration domain
929 * is the domain of this map, so we need to be careful to adjust
932 * If the induction variable appears in the constraints (as a parameter)
933 * of the current iteration domain or the schedule of the statement,
934 * then the parameter is equated to the newly introduced iteration
935 * domain dimension and subsequently projected out.
937 * Finally, all access relations are updated based on the extra loop.
939 struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
, __isl_take isl_set
*dom
,
940 __isl_take isl_map
*sched
, __isl_take isl_id
*var_id
)
951 if (isl_set_is_wrapping(stmt
->domain
)) {
956 map
= isl_set_unwrap(stmt
->domain
);
957 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
958 ran_dim
= isl_space_range(isl_map_get_space(map
));
959 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
960 isl_set_universe(ran_dim
));
961 map
= isl_map_flat_domain_product(ext
, map
);
962 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
963 isl_id_copy(stmt_id
));
964 dim
= isl_space_domain(isl_map_get_space(map
));
965 stmt
->domain
= isl_map_wrap(map
);
967 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
968 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
970 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
971 isl_id_copy(stmt_id
));
972 dim
= isl_set_get_space(stmt
->domain
);
975 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
977 stmt
->domain
= isl_set_equate(stmt
->domain
,
978 isl_dim_param
, pos
, isl_dim_set
, 0);
979 stmt
->domain
= isl_set_project_out(stmt
->domain
,
980 isl_dim_param
, pos
, 1);
983 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
984 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
985 isl_dim_in
, stmt_id
);
987 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
989 stmt
->schedule
= isl_map_equate(stmt
->schedule
,
990 isl_dim_param
, pos
, isl_dim_in
, 0);
991 stmt
->schedule
= isl_map_project_out(stmt
->schedule
,
992 isl_dim_param
, pos
, 1);
995 dim
= isl_space_map_from_set(dim
);
996 extend
= isl_map_identity(dim
);
997 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
998 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
999 isl_map_get_tuple_id(extend
, isl_dim_out
));
1000 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1001 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1002 isl_map_copy(extend
), var_id
);
1003 stmt
->body
= expr_embed(stmt
->body
, extend
, var_id
);
1006 isl_id_free(var_id
);
1008 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1010 return pet_stmt_free(stmt
);
1011 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1012 return pet_stmt_free(stmt
);
1016 isl_map_free(sched
);
1017 isl_id_free(var_id
);
1021 /* Embed the given pet_array in an extra outer loop with iteration domain
1023 * This embedding only has an effect on virtual arrays (those with
1024 * user pointer equal to NULL), which need to be extended along with
1025 * the iteration domain.
1027 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1028 __isl_take isl_set
*dom
)
1030 isl_id
*array_id
= NULL
;
1035 if (isl_set_has_tuple_id(array
->extent
))
1036 array_id
= isl_set_get_tuple_id(array
->extent
);
1038 if (array_id
&& !isl_id_get_user(array_id
)) {
1039 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1040 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1043 isl_id_free(array_id
);
1052 /* Embed all statements and arrays in "scop" in an extra outer loop
1053 * with iteration domain "dom" and schedule "sched".
1054 * "var_id" represents the induction variable of the loop.
1056 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1057 __isl_take isl_map
*sched
, __isl_take isl_id
*id
)
1064 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1065 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1067 isl_map_copy(sched
), isl_id_copy(id
));
1068 if (!scop
->stmts
[i
])
1072 for (i
= 0; i
< scop
->n_array
; ++i
) {
1073 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1075 if (!scop
->arrays
[i
])
1080 isl_map_free(sched
);
1085 isl_map_free(sched
);
1087 return pet_scop_free(scop
);
1090 /* Add extra conditions on the parameters to iteration domain of "stmt".
1092 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1093 __isl_take isl_set
*cond
)
1098 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1103 return pet_stmt_free(stmt
);
1106 /* Add extra conditions on the parameters to all iteration domains.
1108 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1109 __isl_take isl_set
*cond
)
1116 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1117 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1118 isl_set_copy(cond
));
1119 if (!scop
->stmts
[i
])
1127 return pet_scop_free(scop
);
1130 /* Make the statements "stmt" depend on the value of "test"
1131 * being equal to "satisfied" by adjusting stmt->domain.
1133 * We insert an argument corresponding to a read to "test"
1134 * from the iteration domain of "stmt" in front of the list of arguments.
1135 * We also insert a corresponding output dimension in the wrapped
1136 * map contained in stmt->domain, with value set to "satisfied".
1138 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1139 __isl_take isl_map
*test
, int satisfied
)
1150 if (isl_set_is_wrapping(stmt
->domain
))
1151 map
= isl_set_unwrap(stmt
->domain
);
1153 map
= isl_map_from_domain(stmt
->domain
);
1154 map
= isl_map_insert_dims(map
, isl_dim_out
, 0, 1);
1155 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1156 map
= isl_map_set_dim_id(map
, isl_dim_out
, 0, id
);
1157 map
= isl_map_fix_si(map
, isl_dim_out
, 0, satisfied
);
1158 dom
= isl_set_universe(isl_space_domain(isl_map_get_space(map
)));
1159 test
= isl_map_apply_domain(test
, isl_map_from_range(dom
));
1161 stmt
->domain
= isl_map_wrap(map
);
1163 ctx
= isl_map_get_ctx(test
);
1165 stmt
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1169 struct pet_expr
**args
;
1170 args
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + stmt
->n_arg
);
1173 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1174 args
[1 + i
] = stmt
->args
[i
];
1179 stmt
->args
[0] = pet_expr_from_access(isl_map_copy(test
));
1187 return pet_stmt_free(stmt
);
1190 /* Make all statements in "scop" depend on the value of "test"
1191 * being equal to "satisfied" by adjusting their domains.
1193 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1194 __isl_take isl_map
*test
, int satisfied
)
1201 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1202 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
1203 isl_map_copy(test
), satisfied
);
1204 if (!scop
->stmts
[i
])
1212 return pet_scop_free(scop
);
1215 /* Add all parameters in "expr" to "dim" and return the result.
1217 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
1218 __isl_take isl_space
*dim
)
1224 for (i
= 0; i
< expr
->n_arg
; ++i
)
1226 dim
= expr_collect_params(expr
->args
[i
], dim
);
1228 if (expr
->type
== pet_expr_access
)
1229 dim
= isl_space_align_params(dim
,
1230 isl_map_get_space(expr
->acc
.access
));
1234 isl_space_free(dim
);
1235 return pet_expr_free(expr
);
1238 /* Add all parameters in "stmt" to "dim" and return the result.
1240 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
1241 __isl_take isl_space
*dim
)
1246 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
1247 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
1248 dim
= expr_collect_params(stmt
->body
, dim
);
1252 isl_space_free(dim
);
1253 return pet_stmt_free(stmt
);
1256 /* Add all parameters in "array" to "dim" and return the result.
1258 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1259 __isl_take isl_space
*dim
)
1264 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
1265 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
1269 isl_space_free(dim
);
1270 return pet_array_free(array
);
1273 /* Add all parameters in "scop" to "dim" and return the result.
1275 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1276 __isl_take isl_space
*dim
)
1283 for (i
= 0; i
< scop
->n_array
; ++i
)
1284 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1286 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1287 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1291 isl_space_free(dim
);
1292 return pet_scop_free(scop
);
1295 /* Add all parameters in "dim" to all access relations in "expr".
1297 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1298 __isl_take isl_space
*dim
)
1305 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1307 expr_propagate_params(expr
->args
[i
],
1308 isl_space_copy(dim
));
1313 if (expr
->type
== pet_expr_access
) {
1314 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1315 isl_space_copy(dim
));
1316 if (!expr
->acc
.access
)
1320 isl_space_free(dim
);
1323 isl_space_free(dim
);
1324 return pet_expr_free(expr
);
1327 /* Add all parameters in "dim" to the domain, schedule and
1328 * all access relations in "stmt".
1330 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1331 __isl_take isl_space
*dim
)
1336 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
1337 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1338 isl_space_copy(dim
));
1339 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
1341 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1344 isl_space_free(dim
);
1347 isl_space_free(dim
);
1348 return pet_stmt_free(stmt
);
1351 /* Add all parameters in "dim" to "array".
1353 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1354 __isl_take isl_space
*dim
)
1359 array
->context
= isl_set_align_params(array
->context
,
1360 isl_space_copy(dim
));
1361 array
->extent
= isl_set_align_params(array
->extent
,
1362 isl_space_copy(dim
));
1363 if (array
->value_bounds
) {
1364 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1365 isl_space_copy(dim
));
1366 if (!array
->value_bounds
)
1370 if (!array
->context
|| !array
->extent
)
1373 isl_space_free(dim
);
1376 isl_space_free(dim
);
1377 return pet_array_free(array
);
1380 /* Add all parameters in "dim" to "scop".
1382 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1383 __isl_take isl_space
*dim
)
1390 for (i
= 0; i
< scop
->n_array
; ++i
) {
1391 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1392 isl_space_copy(dim
));
1393 if (!scop
->arrays
[i
])
1397 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1398 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1399 isl_space_copy(dim
));
1400 if (!scop
->stmts
[i
])
1404 isl_space_free(dim
);
1407 isl_space_free(dim
);
1408 return pet_scop_free(scop
);
1411 /* Update all isl_sets and isl_maps in "scop" such that they all
1412 * have the same parameters.
1414 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1421 dim
= isl_set_get_space(scop
->context
);
1422 dim
= scop_collect_params(scop
, dim
);
1424 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
1425 scop
= scop_propagate_params(scop
, dim
);
1430 /* Check if the given access relation accesses a (0D) array that corresponds
1431 * to one of the parameters in "dim". If so, replace the array access
1432 * by an access to the set of integers with as index (and value)
1435 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1436 __isl_take isl_space
*dim
)
1438 isl_id
*array_id
= NULL
;
1441 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1442 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1443 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1445 isl_space_free(dim
);
1448 isl_id_free(array_id
);
1452 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1454 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1455 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1458 isl_id_free(array_id
);
1460 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1461 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1466 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1467 * in "dim" by a value equal to the corresponding parameter.
1469 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1470 __isl_take isl_space
*dim
)
1477 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1479 expr_detect_parameter_accesses(expr
->args
[i
],
1480 isl_space_copy(dim
));
1485 if (expr
->type
== pet_expr_access
) {
1486 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1487 isl_space_copy(dim
));
1488 if (!expr
->acc
.access
)
1492 isl_space_free(dim
);
1495 isl_space_free(dim
);
1496 return pet_expr_free(expr
);
1499 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1500 * in "dim" by a value equal to the corresponding parameter.
1502 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1503 __isl_take isl_space
*dim
)
1508 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1509 isl_space_copy(dim
));
1511 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1514 isl_space_free(dim
);
1517 isl_space_free(dim
);
1518 return pet_stmt_free(stmt
);
1521 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1522 * in "dim" by a value equal to the corresponding parameter.
1524 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1525 __isl_take isl_space
*dim
)
1532 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1533 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1534 isl_space_copy(dim
));
1535 if (!scop
->stmts
[i
])
1539 isl_space_free(dim
);
1542 isl_space_free(dim
);
1543 return pet_scop_free(scop
);
1546 /* Replace all accesses to (0D) arrays that correspond to any of
1547 * the parameters used in "scop" by a value equal
1548 * to the corresponding parameter.
1550 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1557 dim
= isl_set_get_space(scop
->context
);
1558 dim
= scop_collect_params(scop
, dim
);
1560 scop
= scop_detect_parameter_accesses(scop
, dim
);
1565 /* Add all read access relations (if "read" is set) and/or all write
1566 * access relations (if "write" is set) to "accesses" and return the result.
1568 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1569 int read
, int write
, __isl_take isl_union_map
*accesses
)
1578 for (i
= 0; i
< expr
->n_arg
; ++i
)
1579 accesses
= expr_collect_accesses(expr
->args
[i
],
1580 read
, write
, accesses
);
1582 if (expr
->type
== pet_expr_access
&&
1583 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
1584 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1585 accesses
= isl_union_map_add_map(accesses
,
1586 isl_map_copy(expr
->acc
.access
));
1591 /* Collect and return all read access relations (if "read" is set)
1592 * and/or all write * access relations (if "write" is set) in "stmt".
1594 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1595 int read
, int write
, __isl_take isl_space
*dim
)
1597 isl_union_map
*accesses
;
1602 accesses
= isl_union_map_empty(dim
);
1603 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1604 accesses
= isl_union_map_intersect_domain(accesses
,
1605 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1610 /* Collect and return all read access relations (if "read" is set)
1611 * and/or all write * access relations (if "write" is set) in "scop".
1613 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1614 int read
, int write
)
1617 isl_union_map
*accesses
;
1622 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1624 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1625 isl_union_map
*accesses_i
;
1626 isl_space
*dim
= isl_set_get_space(scop
->context
);
1627 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1629 accesses
= isl_union_map_union(accesses
, accesses_i
);
1635 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1637 return scop_collect_accesses(scop
, 1, 0);
1640 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1642 return scop_collect_accesses(scop
, 0, 1);
1645 /* Collect and return the union of iteration domains in "scop".
1647 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
1651 isl_union_set
*domain
;
1656 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
1658 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1659 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
1660 domain
= isl_union_set_add_set(domain
, domain_i
);
1666 /* Collect and return the schedules of the statements in "scop".
1667 * The range is normalized to the maximal number of scheduling
1670 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
1673 isl_map
*schedule_i
;
1674 isl_union_map
*schedule
;
1675 int depth
, max_depth
= 0;
1680 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1682 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1683 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
1684 if (depth
> max_depth
)
1688 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1689 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
1690 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
1691 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
1693 for (j
= depth
; j
< max_depth
; ++j
)
1694 schedule_i
= isl_map_fix_si(schedule_i
,
1696 schedule
= isl_union_map_add_map(schedule
, schedule_i
);