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
] = "=",
65 [pet_op_address_of
] = "&"
68 const char *pet_op_str(enum pet_op_type op
)
73 const char *pet_type_str(enum pet_expr_type type
)
75 return type_str
[type
];
78 enum pet_op_type
pet_str_op(const char *str
)
82 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
83 if (!strcmp(op_str
[i
], str
))
89 enum pet_expr_type
pet_str_type(const char *str
)
93 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
94 if (!strcmp(type_str
[i
], str
))
100 /* Construct a pet_expr from an access relation.
101 * By default, it is considered to be a read access.
103 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
105 isl_ctx
*ctx
= isl_map_get_ctx(access
);
106 struct pet_expr
*expr
;
110 expr
= isl_calloc_type(ctx
, struct pet_expr
);
114 expr
->type
= pet_expr_access
;
115 expr
->acc
.access
= access
;
121 isl_map_free(access
);
125 /* Construct a unary pet_expr that performs "op" on "arg".
127 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
128 struct pet_expr
*arg
)
130 struct pet_expr
*expr
;
134 expr
= isl_alloc_type(ctx
, struct pet_expr
);
138 expr
->type
= pet_expr_unary
;
141 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
144 expr
->args
[pet_un_arg
] = arg
;
152 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
154 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
155 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
157 struct pet_expr
*expr
;
161 expr
= isl_alloc_type(ctx
, struct pet_expr
);
165 expr
->type
= pet_expr_binary
;
168 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
171 expr
->args
[pet_bin_lhs
] = lhs
;
172 expr
->args
[pet_bin_rhs
] = rhs
;
181 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
183 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
184 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
186 struct pet_expr
*expr
;
188 if (!cond
|| !lhs
|| !rhs
)
190 expr
= isl_alloc_type(ctx
, struct pet_expr
);
194 expr
->type
= pet_expr_ternary
;
196 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
199 expr
->args
[pet_ter_cond
] = cond
;
200 expr
->args
[pet_ter_true
] = lhs
;
201 expr
->args
[pet_ter_false
] = rhs
;
211 /* Construct a call pet_expr that calls function "name" with "n_arg"
212 * arguments. The caller is responsible for filling in the arguments.
214 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
217 struct pet_expr
*expr
;
219 expr
= isl_alloc_type(ctx
, struct pet_expr
);
223 expr
->type
= pet_expr_call
;
225 expr
->name
= strdup(name
);
226 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
227 if (!expr
->name
|| !expr
->args
)
228 return pet_expr_free(expr
);
233 /* Construct a pet_expr that represents the double "d".
235 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
237 struct pet_expr
*expr
;
239 expr
= isl_calloc_type(ctx
, struct pet_expr
);
243 expr
->type
= pet_expr_double
;
249 void *pet_expr_free(struct pet_expr
*expr
)
256 for (i
= 0; i
< expr
->n_arg
; ++i
)
257 pet_expr_free(expr
->args
[i
]);
260 switch (expr
->type
) {
261 case pet_expr_access
:
262 isl_map_free(expr
->acc
.access
);
267 case pet_expr_double
:
269 case pet_expr_binary
:
270 case pet_expr_ternary
:
278 static void expr_dump(struct pet_expr
*expr
, int indent
)
285 fprintf(stderr
, "%*s", indent
, "");
287 switch (expr
->type
) {
288 case pet_expr_double
:
289 fprintf(stderr
, "%g\n", expr
->d
);
291 case pet_expr_access
:
292 isl_map_dump(expr
->acc
.access
);
293 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
295 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
296 "", expr
->acc
.write
);
297 for (i
= 0; i
< expr
->n_arg
; ++i
)
298 expr_dump(expr
->args
[i
], indent
+ 2);
301 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
302 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
304 case pet_expr_binary
:
305 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
306 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
307 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
309 case pet_expr_ternary
:
310 fprintf(stderr
, "?:\n");
311 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
312 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
313 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
316 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
317 for (i
= 0; i
< expr
->n_arg
; ++i
)
318 expr_dump(expr
->args
[i
], indent
+ 2);
323 void pet_expr_dump(struct pet_expr
*expr
)
328 /* Return 1 if the two pet_exprs are equivalent.
330 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
334 if (!expr1
|| !expr2
)
337 if (expr1
->type
!= expr2
->type
)
339 if (expr1
->n_arg
!= expr2
->n_arg
)
341 for (i
= 0; i
< expr1
->n_arg
; ++i
)
342 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
344 switch (expr1
->type
) {
345 case pet_expr_double
:
346 if (expr1
->d
!= expr2
->d
)
349 case pet_expr_access
:
350 if (expr1
->acc
.read
!= expr2
->acc
.read
)
352 if (expr1
->acc
.write
!= expr2
->acc
.write
)
354 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
356 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
360 case pet_expr_binary
:
361 case pet_expr_ternary
:
362 if (expr1
->op
!= expr2
->op
)
366 if (strcmp(expr1
->name
, expr2
->name
))
374 /* Add extra conditions on the parameters to all access relations in "expr".
376 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
377 __isl_take isl_set
*cond
)
384 for (i
= 0; i
< expr
->n_arg
; ++i
) {
385 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
391 if (expr
->type
== pet_expr_access
) {
392 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
394 if (!expr
->acc
.access
)
402 return pet_expr_free(expr
);
405 /* Modify all access relations in "expr" by calling "fn" on them.
407 struct pet_expr
*pet_expr_foreach_access(struct pet_expr
*expr
,
408 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
416 for (i
= 0; i
< expr
->n_arg
; ++i
) {
417 expr
->args
[i
] = pet_expr_foreach_access(expr
->args
[i
], fn
, user
);
419 return pet_expr_free(expr
);
422 if (expr
->type
== pet_expr_access
) {
423 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
424 if (!expr
->acc
.access
)
425 return pet_expr_free(expr
);
431 /* Modify the given access relation based on the given iteration space
433 * If the access has any arguments then the domain of the access relation
434 * is a wrapped mapping from the iteration space to the space of
435 * argument values. We only need to change the domain of this wrapped
436 * mapping, so we extend the input transformation with an identity mapping
437 * on the space of argument values.
439 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
442 isl_map
*update
= user
;
445 update
= isl_map_copy(update
);
447 dim
= isl_map_get_space(access
);
448 dim
= isl_space_domain(dim
);
449 if (!isl_space_is_wrapping(dim
))
453 dim
= isl_space_unwrap(dim
);
454 dim
= isl_space_range(dim
);
455 dim
= isl_space_map_from_set(dim
);
456 id
= isl_map_identity(dim
);
457 update
= isl_map_product(update
, id
);
460 return isl_map_apply_domain(access
, update
);
463 /* Modify all access relations in "expr" based on the given iteration space
466 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
467 __isl_take isl_map
*update
)
469 expr
= pet_expr_foreach_access(expr
, &update_domain
, update
);
470 isl_map_free(update
);
474 /* Construct a pet_stmt with given line number and statement
475 * number from a pet_expr.
476 * The initial iteration domain is the zero-dimensional universe.
477 * The name of the domain is given by "label" if it is non-NULL.
478 * Otherwise, the name is constructed as S_<id>.
479 * The domains of all access relations are modified to refer
480 * to the statement iteration domain.
482 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
483 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
485 struct pet_stmt
*stmt
;
495 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
499 dim
= isl_space_set_alloc(ctx
, 0, 0);
501 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
503 snprintf(name
, sizeof(name
), "S_%d", id
);
504 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
506 dom
= isl_set_universe(isl_space_copy(dim
));
507 sched
= isl_map_from_domain(isl_set_copy(dom
));
509 dim
= isl_space_from_range(dim
);
510 add_name
= isl_map_universe(dim
);
511 expr
= expr_update_domain(expr
, add_name
);
515 stmt
->schedule
= sched
;
518 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
519 return pet_stmt_free(stmt
);
524 return pet_expr_free(expr
);
527 void *pet_stmt_free(struct pet_stmt
*stmt
)
534 isl_set_free(stmt
->domain
);
535 isl_map_free(stmt
->schedule
);
536 pet_expr_free(stmt
->body
);
538 for (i
= 0; i
< stmt
->n_arg
; ++i
)
539 pet_expr_free(stmt
->args
[i
]);
546 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
553 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
554 fprintf(stderr
, "%*s", indent
, "");
555 isl_set_dump(stmt
->domain
);
556 fprintf(stderr
, "%*s", indent
, "");
557 isl_map_dump(stmt
->schedule
);
558 expr_dump(stmt
->body
, indent
);
559 for (i
= 0; i
< stmt
->n_arg
; ++i
)
560 expr_dump(stmt
->args
[i
], indent
+ 2);
563 void pet_stmt_dump(struct pet_stmt
*stmt
)
568 void *pet_array_free(struct pet_array
*array
)
573 isl_set_free(array
->context
);
574 isl_set_free(array
->extent
);
575 isl_set_free(array
->value_bounds
);
576 free(array
->element_type
);
582 void pet_array_dump(struct pet_array
*array
)
587 isl_set_dump(array
->context
);
588 isl_set_dump(array
->extent
);
589 isl_set_dump(array
->value_bounds
);
590 fprintf(stderr
, "%s %s\n", array
->element_type
,
591 array
->live_out
? "live-out" : "");
594 /* Construct a pet_scop with room for n statements.
596 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
599 struct pet_scop
*scop
;
601 scop
= isl_calloc_type(ctx
, struct pet_scop
);
605 space
= isl_space_params_alloc(ctx
, 0);
606 scop
->context
= isl_set_universe(isl_space_copy(space
));
607 scop
->context_value
= isl_set_universe(space
);
608 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
609 if (!scop
->context
|| !scop
->stmts
)
610 return pet_scop_free(scop
);
617 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
619 return scop_alloc(ctx
, 0);
622 /* Construct a pet_scop that contains the given pet_stmt.
624 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
626 struct pet_scop
*scop
;
631 scop
= scop_alloc(ctx
, 1);
633 scop
->stmts
[0] = stmt
;
642 /* Construct a pet_scop that contains the arrays and the statements
643 * in "scop1" and "scop2".
645 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
646 struct pet_scop
*scop2
)
649 struct pet_scop
*scop
;
651 if (!scop1
|| !scop2
)
654 if (scop1
->n_stmt
== 0) {
655 pet_scop_free(scop1
);
659 if (scop2
->n_stmt
== 0) {
660 pet_scop_free(scop2
);
664 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
668 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
669 scop1
->n_array
+ scop2
->n_array
);
672 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
674 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
675 scop
->stmts
[i
] = scop1
->stmts
[i
];
676 scop1
->stmts
[i
] = NULL
;
679 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
680 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
681 scop2
->stmts
[i
] = NULL
;
684 for (i
= 0; i
< scop1
->n_array
; ++i
) {
685 scop
->arrays
[i
] = scop1
->arrays
[i
];
686 scop1
->arrays
[i
] = NULL
;
689 for (i
= 0; i
< scop2
->n_array
; ++i
) {
690 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
691 scop2
->arrays
[i
] = NULL
;
694 pet_scop_free(scop1
);
695 pet_scop_free(scop2
);
698 pet_scop_free(scop1
);
699 pet_scop_free(scop2
);
703 void *pet_scop_free(struct pet_scop
*scop
)
709 isl_set_free(scop
->context
);
710 isl_set_free(scop
->context_value
);
712 for (i
= 0; i
< scop
->n_array
; ++i
)
713 pet_array_free(scop
->arrays
[i
]);
716 for (i
= 0; i
< scop
->n_stmt
; ++i
)
717 pet_stmt_free(scop
->stmts
[i
]);
723 void pet_scop_dump(struct pet_scop
*scop
)
730 isl_set_dump(scop
->context
);
731 isl_set_dump(scop
->context_value
);
732 for (i
= 0; i
< scop
->n_array
; ++i
)
733 pet_array_dump(scop
->arrays
[i
]);
734 for (i
= 0; i
< scop
->n_stmt
; ++i
)
735 pet_stmt_dump(scop
->stmts
[i
]);
738 /* Return 1 if the two pet_arrays are equivalent.
740 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
742 if (!array1
|| !array2
)
745 if (!isl_set_is_equal(array1
->context
, array2
->context
))
747 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
749 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
751 if (array1
->value_bounds
&&
752 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
754 if (strcmp(array1
->element_type
, array2
->element_type
))
756 if (array1
->live_out
!= array2
->live_out
)
762 /* Return 1 if the two pet_stmts are equivalent.
764 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
768 if (!stmt1
|| !stmt2
)
771 if (stmt1
->line
!= stmt2
->line
)
773 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
775 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
777 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
779 if (stmt1
->n_arg
!= stmt2
->n_arg
)
781 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
782 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
789 /* Return 1 if the two pet_scops are equivalent.
791 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
795 if (!scop1
|| !scop2
)
798 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
800 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
803 if (scop1
->n_array
!= scop2
->n_array
)
805 for (i
= 0; i
< scop1
->n_array
; ++i
)
806 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
809 if (scop1
->n_stmt
!= scop2
->n_stmt
)
811 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
812 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
818 /* Prefix the schedule of "stmt" with an extra dimension with constant
821 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
826 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
827 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
829 return pet_stmt_free(stmt
);
834 /* Prefix the schedules of all statements in "scop" with an extra
835 * dimension with constant value "pos".
837 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
844 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
845 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
847 return pet_scop_free(scop
);
853 /* Data used in embed_access.
854 * extend adds an iterator to the iteration domain
855 * var_id represents the induction variable of the corresponding loop
857 struct pet_embed_access
{
862 /* Embed the access relation in an extra outer loop.
864 * We first update the iteration domain to insert the extra dimension.
866 * If the access refers to the induction variable, then it is
867 * turned into an access to the set of integers with index (and value)
868 * equal to the induction variable.
870 * If the induction variable appears in the constraints (as a parameter),
871 * then the parameter is equated to the newly introduced iteration
872 * domain dimension and subsequently projected out.
874 * Similarly, if the accessed array is a virtual array (with user
875 * pointer equal to NULL), as created by create_test_access,
876 * then it is extended along with the domain of the access.
878 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
881 struct pet_embed_access
*data
= user
;
882 isl_id
*array_id
= NULL
;
885 access
= update_domain(access
, data
->extend
);
887 if (isl_map_has_tuple_id(access
, isl_dim_out
))
888 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
889 if (array_id
== data
->var_id
||
890 (array_id
&& !isl_id_get_user(array_id
))) {
891 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
892 access
= isl_map_equate(access
,
893 isl_dim_in
, 0, isl_dim_out
, 0);
894 if (array_id
!= data
->var_id
)
895 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
896 isl_id_copy(array_id
));
898 isl_id_free(array_id
);
900 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
902 access
= isl_map_equate(access
,
903 isl_dim_param
, pos
, isl_dim_in
, 0);
904 access
= isl_map_project_out(access
, isl_dim_param
, pos
, 1);
906 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
907 isl_id_copy(data
->var_id
));
912 /* Embed all access relations in "expr" in an extra loop.
913 * "extend" inserts an outer loop iterator in the iteration domains.
914 * "var_id" represents the induction variable.
916 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
917 __isl_take isl_map
*extend
, __isl_keep isl_id
*var_id
)
919 struct pet_embed_access data
= { .extend
= extend
, .var_id
= var_id
};
921 expr
= pet_expr_foreach_access(expr
, &embed_access
, &data
);
922 isl_map_free(extend
);
926 /* Embed the given pet_stmt in an extra outer loop with iteration domain
927 * "dom" and schedule "sched". "var_id" represents the induction variable
930 * The iteration domain and schedule of the statement are updated
931 * according to the iteration domain and schedule of the new loop.
932 * If stmt->domain is a wrapped map, then the iteration domain
933 * is the domain of this map, so we need to be careful to adjust
936 * If the induction variable appears in the constraints (as a parameter)
937 * of the current iteration domain or the schedule of the statement,
938 * then the parameter is equated to the newly introduced iteration
939 * domain dimension and subsequently projected out.
941 * Finally, all access relations are updated based on the extra loop.
943 struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
, __isl_take isl_set
*dom
,
944 __isl_take isl_map
*sched
, __isl_take isl_id
*var_id
)
955 if (isl_set_is_wrapping(stmt
->domain
)) {
960 map
= isl_set_unwrap(stmt
->domain
);
961 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
962 ran_dim
= isl_space_range(isl_map_get_space(map
));
963 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
964 isl_set_universe(ran_dim
));
965 map
= isl_map_flat_domain_product(ext
, map
);
966 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
967 isl_id_copy(stmt_id
));
968 dim
= isl_space_domain(isl_map_get_space(map
));
969 stmt
->domain
= isl_map_wrap(map
);
971 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
972 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
974 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
975 isl_id_copy(stmt_id
));
976 dim
= isl_set_get_space(stmt
->domain
);
979 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
981 stmt
->domain
= isl_set_equate(stmt
->domain
,
982 isl_dim_param
, pos
, isl_dim_set
, 0);
983 stmt
->domain
= isl_set_project_out(stmt
->domain
,
984 isl_dim_param
, pos
, 1);
987 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
988 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
989 isl_dim_in
, stmt_id
);
991 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
993 stmt
->schedule
= isl_map_equate(stmt
->schedule
,
994 isl_dim_param
, pos
, isl_dim_in
, 0);
995 stmt
->schedule
= isl_map_project_out(stmt
->schedule
,
996 isl_dim_param
, pos
, 1);
999 dim
= isl_space_map_from_set(dim
);
1000 extend
= isl_map_identity(dim
);
1001 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
1002 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
1003 isl_map_get_tuple_id(extend
, isl_dim_out
));
1004 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1005 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1006 isl_map_copy(extend
), var_id
);
1007 stmt
->body
= expr_embed(stmt
->body
, extend
, var_id
);
1010 isl_id_free(var_id
);
1012 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1014 return pet_stmt_free(stmt
);
1015 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1016 return pet_stmt_free(stmt
);
1020 isl_map_free(sched
);
1021 isl_id_free(var_id
);
1025 /* Embed the given pet_array in an extra outer loop with iteration domain
1027 * This embedding only has an effect on virtual arrays (those with
1028 * user pointer equal to NULL), which need to be extended along with
1029 * the iteration domain.
1031 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1032 __isl_take isl_set
*dom
)
1034 isl_id
*array_id
= NULL
;
1039 if (isl_set_has_tuple_id(array
->extent
))
1040 array_id
= isl_set_get_tuple_id(array
->extent
);
1042 if (array_id
&& !isl_id_get_user(array_id
)) {
1043 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1044 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1047 isl_id_free(array_id
);
1056 /* Embed all statements and arrays in "scop" in an extra outer loop
1057 * with iteration domain "dom" and schedule "sched".
1058 * "var_id" represents the induction variable of the loop.
1060 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1061 __isl_take isl_map
*sched
, __isl_take isl_id
*id
)
1068 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1069 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1071 isl_map_copy(sched
), isl_id_copy(id
));
1072 if (!scop
->stmts
[i
])
1076 for (i
= 0; i
< scop
->n_array
; ++i
) {
1077 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1079 if (!scop
->arrays
[i
])
1084 isl_map_free(sched
);
1089 isl_map_free(sched
);
1091 return pet_scop_free(scop
);
1094 /* Add extra conditions on the parameters to iteration domain of "stmt".
1096 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1097 __isl_take isl_set
*cond
)
1102 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1107 return pet_stmt_free(stmt
);
1110 /* Add extra conditions on the parameters to all iteration domains.
1112 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1113 __isl_take isl_set
*cond
)
1120 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1121 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1122 isl_set_copy(cond
));
1123 if (!scop
->stmts
[i
])
1131 return pet_scop_free(scop
);
1134 /* Make the statements "stmt" depend on the value of "test"
1135 * being equal to "satisfied" by adjusting stmt->domain.
1137 * We insert an argument corresponding to a read to "test"
1138 * from the iteration domain of "stmt" in front of the list of arguments.
1139 * We also insert a corresponding output dimension in the wrapped
1140 * map contained in stmt->domain, with value set to "satisfied".
1142 static struct pet_stmt
*stmt_filter(struct pet_stmt
*stmt
,
1143 __isl_take isl_map
*test
, int satisfied
)
1154 if (isl_set_is_wrapping(stmt
->domain
))
1155 map
= isl_set_unwrap(stmt
->domain
);
1157 map
= isl_map_from_domain(stmt
->domain
);
1158 map
= isl_map_insert_dims(map
, isl_dim_out
, 0, 1);
1159 id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1160 map
= isl_map_set_dim_id(map
, isl_dim_out
, 0, id
);
1161 map
= isl_map_fix_si(map
, isl_dim_out
, 0, satisfied
);
1162 dom
= isl_set_universe(isl_space_domain(isl_map_get_space(map
)));
1163 test
= isl_map_apply_domain(test
, isl_map_from_range(dom
));
1165 stmt
->domain
= isl_map_wrap(map
);
1167 ctx
= isl_map_get_ctx(test
);
1169 stmt
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1173 struct pet_expr
**args
;
1174 args
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + stmt
->n_arg
);
1177 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1178 args
[1 + i
] = stmt
->args
[i
];
1183 stmt
->args
[0] = pet_expr_from_access(isl_map_copy(test
));
1191 return pet_stmt_free(stmt
);
1194 /* Make all statements in "scop" depend on the value of "test"
1195 * being equal to "satisfied" by adjusting their domains.
1197 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1198 __isl_take isl_map
*test
, int satisfied
)
1205 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1206 scop
->stmts
[i
] = stmt_filter(scop
->stmts
[i
],
1207 isl_map_copy(test
), satisfied
);
1208 if (!scop
->stmts
[i
])
1216 return pet_scop_free(scop
);
1219 /* Add all parameters in "expr" to "dim" and return the result.
1221 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
1222 __isl_take isl_space
*dim
)
1228 for (i
= 0; i
< expr
->n_arg
; ++i
)
1230 dim
= expr_collect_params(expr
->args
[i
], dim
);
1232 if (expr
->type
== pet_expr_access
)
1233 dim
= isl_space_align_params(dim
,
1234 isl_map_get_space(expr
->acc
.access
));
1238 isl_space_free(dim
);
1239 return pet_expr_free(expr
);
1242 /* Add all parameters in "stmt" to "dim" and return the result.
1244 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
1245 __isl_take isl_space
*dim
)
1250 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
1251 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
1252 dim
= expr_collect_params(stmt
->body
, dim
);
1256 isl_space_free(dim
);
1257 return pet_stmt_free(stmt
);
1260 /* Add all parameters in "array" to "dim" and return the result.
1262 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1263 __isl_take isl_space
*dim
)
1268 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
1269 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
1273 isl_space_free(dim
);
1274 return pet_array_free(array
);
1277 /* Add all parameters in "scop" to "dim" and return the result.
1279 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1280 __isl_take isl_space
*dim
)
1287 for (i
= 0; i
< scop
->n_array
; ++i
)
1288 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1290 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1291 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1295 isl_space_free(dim
);
1296 return pet_scop_free(scop
);
1299 /* Add all parameters in "dim" to all access relations in "expr".
1301 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1302 __isl_take isl_space
*dim
)
1309 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1311 expr_propagate_params(expr
->args
[i
],
1312 isl_space_copy(dim
));
1317 if (expr
->type
== pet_expr_access
) {
1318 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1319 isl_space_copy(dim
));
1320 if (!expr
->acc
.access
)
1324 isl_space_free(dim
);
1327 isl_space_free(dim
);
1328 return pet_expr_free(expr
);
1331 /* Add all parameters in "dim" to the domain, schedule and
1332 * all access relations in "stmt".
1334 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1335 __isl_take isl_space
*dim
)
1340 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
1341 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1342 isl_space_copy(dim
));
1343 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
1345 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1348 isl_space_free(dim
);
1351 isl_space_free(dim
);
1352 return pet_stmt_free(stmt
);
1355 /* Add all parameters in "dim" to "array".
1357 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1358 __isl_take isl_space
*dim
)
1363 array
->context
= isl_set_align_params(array
->context
,
1364 isl_space_copy(dim
));
1365 array
->extent
= isl_set_align_params(array
->extent
,
1366 isl_space_copy(dim
));
1367 if (array
->value_bounds
) {
1368 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1369 isl_space_copy(dim
));
1370 if (!array
->value_bounds
)
1374 if (!array
->context
|| !array
->extent
)
1377 isl_space_free(dim
);
1380 isl_space_free(dim
);
1381 return pet_array_free(array
);
1384 /* Add all parameters in "dim" to "scop".
1386 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1387 __isl_take isl_space
*dim
)
1394 for (i
= 0; i
< scop
->n_array
; ++i
) {
1395 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1396 isl_space_copy(dim
));
1397 if (!scop
->arrays
[i
])
1401 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1402 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1403 isl_space_copy(dim
));
1404 if (!scop
->stmts
[i
])
1408 isl_space_free(dim
);
1411 isl_space_free(dim
);
1412 return pet_scop_free(scop
);
1415 /* Update all isl_sets and isl_maps in "scop" such that they all
1416 * have the same parameters.
1418 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1425 dim
= isl_set_get_space(scop
->context
);
1426 dim
= scop_collect_params(scop
, dim
);
1428 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
1429 scop
= scop_propagate_params(scop
, dim
);
1434 /* Check if the given access relation accesses a (0D) array that corresponds
1435 * to one of the parameters in "dim". If so, replace the array access
1436 * by an access to the set of integers with as index (and value)
1439 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1440 __isl_take isl_space
*dim
)
1442 isl_id
*array_id
= NULL
;
1445 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1446 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1447 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1449 isl_space_free(dim
);
1452 isl_id_free(array_id
);
1456 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1458 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1459 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1462 isl_id_free(array_id
);
1464 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1465 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1470 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1471 * in "dim" by a value equal to the corresponding parameter.
1473 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1474 __isl_take isl_space
*dim
)
1481 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1483 expr_detect_parameter_accesses(expr
->args
[i
],
1484 isl_space_copy(dim
));
1489 if (expr
->type
== pet_expr_access
) {
1490 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1491 isl_space_copy(dim
));
1492 if (!expr
->acc
.access
)
1496 isl_space_free(dim
);
1499 isl_space_free(dim
);
1500 return pet_expr_free(expr
);
1503 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1504 * in "dim" by a value equal to the corresponding parameter.
1506 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1507 __isl_take isl_space
*dim
)
1512 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1513 isl_space_copy(dim
));
1515 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1518 isl_space_free(dim
);
1521 isl_space_free(dim
);
1522 return pet_stmt_free(stmt
);
1525 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1526 * in "dim" by a value equal to the corresponding parameter.
1528 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1529 __isl_take isl_space
*dim
)
1536 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1537 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1538 isl_space_copy(dim
));
1539 if (!scop
->stmts
[i
])
1543 isl_space_free(dim
);
1546 isl_space_free(dim
);
1547 return pet_scop_free(scop
);
1550 /* Replace all accesses to (0D) arrays that correspond to any of
1551 * the parameters used in "scop" by a value equal
1552 * to the corresponding parameter.
1554 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1561 dim
= isl_set_get_space(scop
->context
);
1562 dim
= scop_collect_params(scop
, dim
);
1564 scop
= scop_detect_parameter_accesses(scop
, dim
);
1569 /* Add all read access relations (if "read" is set) and/or all write
1570 * access relations (if "write" is set) to "accesses" and return the result.
1572 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1573 int read
, int write
, __isl_take isl_union_map
*accesses
)
1582 for (i
= 0; i
< expr
->n_arg
; ++i
)
1583 accesses
= expr_collect_accesses(expr
->args
[i
],
1584 read
, write
, accesses
);
1586 if (expr
->type
== pet_expr_access
&&
1587 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
1588 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1589 accesses
= isl_union_map_add_map(accesses
,
1590 isl_map_copy(expr
->acc
.access
));
1595 /* Collect and return all read access relations (if "read" is set)
1596 * and/or all write * access relations (if "write" is set) in "stmt".
1598 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1599 int read
, int write
, __isl_take isl_space
*dim
)
1601 isl_union_map
*accesses
;
1606 accesses
= isl_union_map_empty(dim
);
1607 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1608 accesses
= isl_union_map_intersect_domain(accesses
,
1609 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1614 /* Collect and return all read access relations (if "read" is set)
1615 * and/or all write * access relations (if "write" is set) in "scop".
1617 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1618 int read
, int write
)
1621 isl_union_map
*accesses
;
1626 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1628 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1629 isl_union_map
*accesses_i
;
1630 isl_space
*dim
= isl_set_get_space(scop
->context
);
1631 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1633 accesses
= isl_union_map_union(accesses
, accesses_i
);
1639 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1641 return scop_collect_accesses(scop
, 1, 0);
1644 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1646 return scop_collect_accesses(scop
, 0, 1);
1649 /* Collect and return the union of iteration domains in "scop".
1651 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
1655 isl_union_set
*domain
;
1660 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
1662 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1663 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
1664 domain
= isl_union_set_add_set(domain
, domain_i
);
1670 /* Collect and return the schedules of the statements in "scop".
1671 * The range is normalized to the maximal number of scheduling
1674 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
1677 isl_map
*schedule_i
;
1678 isl_union_map
*schedule
;
1679 int depth
, max_depth
= 0;
1684 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1686 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1687 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
1688 if (depth
> max_depth
)
1692 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1693 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
1694 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
1695 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
1697 for (j
= depth
; j
< max_depth
; ++j
)
1698 schedule_i
= isl_map_fix_si(schedule_i
,
1700 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
1706 /* Does expression "expr" write to "id"?
1708 static int expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
1713 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1714 int writes
= expr_writes(expr
->args
[i
], id
);
1715 if (writes
< 0 || writes
)
1719 if (expr
->type
!= pet_expr_access
)
1721 if (!expr
->acc
.write
)
1723 if (!isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
))
1726 write_id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
1727 isl_id_free(write_id
);
1732 return write_id
== id
;
1735 /* Does statement "stmt" write to "id"?
1737 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
1739 return expr_writes(stmt
->body
, id
);
1742 /* Is there any write access in "scop" that accesses "id"?
1744 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
1751 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1752 int writes
= stmt_writes(scop
->stmts
[i
], id
);
1753 if (writes
< 0 || writes
)