1 #include <isl/constraint.h>
2 #include <isl/union_set.h>
6 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
8 static char *type_str
[] = {
9 [pet_expr_access
] = "access",
10 [pet_expr_call
] = "call",
11 [pet_expr_double
] = "double",
12 [pet_expr_unary
] = "unary",
13 [pet_expr_binary
] = "binary",
14 [pet_expr_ternary
] = "ternary"
17 static char *op_str
[] = {
18 [pet_op_add_assign
] = "+=",
19 [pet_op_sub_assign
] = "-=",
20 [pet_op_mul_assign
] = "*=",
21 [pet_op_div_assign
] = "/=",
22 [pet_op_assign
] = "=",
33 const char *pet_op_str(enum pet_op_type op
)
38 const char *pet_type_str(enum pet_expr_type type
)
40 return type_str
[type
];
43 enum pet_op_type
pet_str_op(const char *str
)
47 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
48 if (!strcmp(op_str
[i
], str
))
54 enum pet_expr_type
pet_str_type(const char *str
)
58 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
59 if (!strcmp(type_str
[i
], str
))
65 /* Construct a pet_expr from an access relation.
66 * By default, it is considered to be a read access.
68 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
70 isl_ctx
*ctx
= isl_map_get_ctx(access
);
71 struct pet_expr
*expr
;
75 expr
= isl_calloc_type(ctx
, struct pet_expr
);
79 expr
->type
= pet_expr_access
;
80 expr
->acc
.access
= access
;
90 /* Construct a unary pet_expr that performs "op" on "arg".
92 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
95 struct pet_expr
*expr
;
99 expr
= isl_alloc_type(ctx
, struct pet_expr
);
103 expr
->type
= pet_expr_unary
;
106 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
109 expr
->args
[pet_un_arg
] = arg
;
117 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
119 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
120 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
122 struct pet_expr
*expr
;
126 expr
= isl_alloc_type(ctx
, struct pet_expr
);
130 expr
->type
= pet_expr_binary
;
133 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
136 expr
->args
[pet_bin_lhs
] = lhs
;
137 expr
->args
[pet_bin_rhs
] = rhs
;
146 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
148 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
149 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
151 struct pet_expr
*expr
;
153 if (!cond
|| !lhs
|| !rhs
)
155 expr
= isl_alloc_type(ctx
, struct pet_expr
);
159 expr
->type
= pet_expr_ternary
;
161 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
164 expr
->args
[pet_ter_cond
] = cond
;
165 expr
->args
[pet_ter_true
] = lhs
;
166 expr
->args
[pet_ter_false
] = rhs
;
176 /* Construct a call pet_expr that calls function "name" with "n_arg"
177 * arguments. The caller is responsible for filling in the arguments.
179 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
182 struct pet_expr
*expr
;
184 expr
= isl_alloc_type(ctx
, struct pet_expr
);
188 expr
->type
= pet_expr_call
;
190 expr
->name
= strdup(name
);
191 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
192 if (!expr
->name
|| !expr
->args
)
193 return pet_expr_free(expr
);
198 /* Construct a pet_expr that represents the double "d".
200 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
202 struct pet_expr
*expr
;
204 expr
= isl_calloc_type(ctx
, struct pet_expr
);
208 expr
->type
= pet_expr_double
;
214 void *pet_expr_free(struct pet_expr
*expr
)
221 for (i
= 0; i
< expr
->n_arg
; ++i
)
222 pet_expr_free(expr
->args
[i
]);
225 switch (expr
->type
) {
226 case pet_expr_access
:
227 isl_map_free(expr
->acc
.access
);
232 case pet_expr_double
:
234 case pet_expr_binary
:
235 case pet_expr_ternary
:
243 static void expr_dump(struct pet_expr
*expr
, int indent
)
250 fprintf(stderr
, "%*s", indent
, "");
252 switch (expr
->type
) {
253 case pet_expr_double
:
254 fprintf(stderr
, "%g\n", expr
->d
);
256 case pet_expr_access
:
257 isl_map_dump(expr
->acc
.access
);
258 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
260 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
261 "", expr
->acc
.write
);
262 for (i
= 0; i
< expr
->n_arg
; ++i
)
263 expr_dump(expr
->args
[i
], indent
+ 2);
266 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
267 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
269 case pet_expr_binary
:
270 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
271 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
272 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
274 case pet_expr_ternary
:
275 fprintf(stderr
, "?:\n");
276 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
277 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
278 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
281 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
282 for (i
= 0; i
< expr
->n_arg
; ++i
)
283 expr_dump(expr
->args
[i
], indent
+ 2);
288 void pet_expr_dump(struct pet_expr
*expr
)
293 /* Return 1 if the two pet_exprs are equivalent.
295 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
299 if (!expr1
|| !expr2
)
302 if (expr1
->type
!= expr2
->type
)
304 if (expr1
->n_arg
!= expr2
->n_arg
)
306 for (i
= 0; i
< expr1
->n_arg
; ++i
)
307 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
309 switch (expr1
->type
) {
310 case pet_expr_double
:
311 if (expr1
->d
!= expr2
->d
)
314 case pet_expr_access
:
315 if (expr1
->acc
.read
!= expr2
->acc
.read
)
317 if (expr1
->acc
.write
!= expr2
->acc
.write
)
319 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
323 case pet_expr_binary
:
324 case pet_expr_ternary
:
325 if (expr1
->op
!= expr2
->op
)
329 if (strcmp(expr1
->name
, expr2
->name
))
337 /* Add extra conditions on the parameters to all access relations in "expr".
339 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
340 __isl_take isl_set
*cond
)
347 for (i
= 0; i
< expr
->n_arg
; ++i
) {
348 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
354 if (expr
->type
== pet_expr_access
) {
355 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
357 if (!expr
->acc
.access
)
365 return pet_expr_free(expr
);
368 /* Modify all access relations in "expr" by calling "fn" on them.
370 static struct pet_expr
*expr_foreach_access(struct pet_expr
*expr
,
371 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
379 for (i
= 0; i
< expr
->n_arg
; ++i
) {
380 expr
->args
[i
] = expr_foreach_access(expr
->args
[i
], fn
, user
);
382 return pet_expr_free(expr
);
385 if (expr
->type
== pet_expr_access
) {
386 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
387 if (!expr
->acc
.access
)
388 return pet_expr_free(expr
);
394 /* Modify the given access relation based on the given iteration space
396 * If the access has any arguments then the domain of the access relation
397 * is a wrapped mapping from the iteration space to the space of
398 * argument values. We only need to change the domain of this wrapped
399 * mapping, so we extend the input transformation with an identity mapping
400 * on the space of argument values.
402 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
405 isl_map
*update
= user
;
408 update
= isl_map_copy(update
);
410 dim
= isl_map_get_dim(access
);
411 dim
= isl_dim_domain(dim
);
412 if (!isl_dim_is_wrapping(dim
))
416 dim
= isl_dim_unwrap(dim
);
417 dim
= isl_dim_range(dim
);
418 dim
= isl_dim_map_from_set(dim
);
419 id
= isl_map_identity(dim
);
420 update
= isl_map_product(update
, id
);
423 return isl_map_apply_domain(access
, update
);
426 /* Modify all access relations in "expr" based on the given iteration space
429 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
430 __isl_take isl_map
*update
)
432 expr
= expr_foreach_access(expr
, &update_domain
, update
);
433 isl_map_free(update
);
437 /* Construct a pet_stmt with given line number and statement
438 * number from a pet_expr.
439 * The initial iteration domain is the zero-dimensional universe.
440 * The domains of all access relations are modified to refer
441 * to the statement iteration domain.
443 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
, int id
,
444 struct pet_expr
*expr
)
446 struct pet_stmt
*stmt
;
456 stmt
= isl_alloc_type(ctx
, struct pet_stmt
);
458 return pet_expr_free(expr
);
460 dim
= isl_dim_set_alloc(ctx
, 0, 0);
461 snprintf(name
, sizeof(name
), "S_%d", id
);
462 dim
= isl_dim_set_tuple_name(dim
, isl_dim_set
, name
);
463 dom
= isl_set_universe(isl_dim_copy(dim
));
464 sched
= isl_map_from_domain(isl_set_copy(dom
));
466 dim
= isl_dim_from_range(dim
);
467 add_name
= isl_map_universe(dim
);
468 expr
= expr_update_domain(expr
, add_name
);
472 stmt
->schedule
= sched
;
475 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
476 return pet_stmt_free(stmt
);
481 void *pet_stmt_free(struct pet_stmt
*stmt
)
486 isl_set_free(stmt
->domain
);
487 isl_map_free(stmt
->schedule
);
488 pet_expr_free(stmt
->body
);
494 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
499 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
500 fprintf(stderr
, "%*s", indent
, "");
501 isl_set_dump(stmt
->domain
);
502 fprintf(stderr
, "%*s", indent
, "");
503 isl_map_dump(stmt
->schedule
);
504 expr_dump(stmt
->body
, indent
);
507 void pet_stmt_dump(struct pet_stmt
*stmt
)
512 void *pet_array_free(struct pet_array
*array
)
517 isl_set_free(array
->context
);
518 isl_set_free(array
->extent
);
519 isl_set_free(array
->value_bounds
);
520 free(array
->element_type
);
526 void pet_array_dump(struct pet_array
*array
)
531 isl_set_dump(array
->context
);
532 isl_set_dump(array
->extent
);
533 isl_set_dump(array
->value_bounds
);
534 fprintf(stderr
, "%s\n", array
->element_type
);
537 /* Construct a pet_scop with room for n statements.
539 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
541 struct pet_scop
*scop
;
543 scop
= isl_calloc_type(ctx
, struct pet_scop
);
547 scop
->context
= isl_set_universe(isl_dim_set_alloc(ctx
, 0, 0));
548 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
549 if (!scop
->context
|| !scop
->stmts
)
550 return pet_scop_free(scop
);
557 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
559 return scop_alloc(ctx
, 0);
562 /* Construct a pet_scop that contains the given pet_stmt.
564 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
566 struct pet_scop
*scop
;
571 scop
= scop_alloc(ctx
, 1);
573 scop
->stmts
[0] = stmt
;
582 /* Construct a pet_scop that contains the statements in "scop1" and "scop2".
584 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
585 struct pet_scop
*scop2
)
588 struct pet_scop
*scop
;
590 if (!scop1
|| !scop2
)
593 if (scop1
->n_stmt
== 0) {
594 pet_scop_free(scop1
);
598 if (scop2
->n_stmt
== 0) {
599 pet_scop_free(scop2
);
603 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
607 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
608 scop
->stmts
[i
] = scop1
->stmts
[i
];
609 scop1
->stmts
[i
] = NULL
;
612 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
613 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
614 scop2
->stmts
[i
] = NULL
;
617 pet_scop_free(scop1
);
618 pet_scop_free(scop2
);
621 pet_scop_free(scop1
);
622 pet_scop_free(scop2
);
626 void *pet_scop_free(struct pet_scop
*scop
)
632 isl_set_free(scop
->context
);
634 for (i
= 0; i
< scop
->n_array
; ++i
)
635 pet_array_free(scop
->arrays
[i
]);
638 for (i
= 0; i
< scop
->n_stmt
; ++i
)
639 pet_stmt_free(scop
->stmts
[i
]);
645 void pet_scop_dump(struct pet_scop
*scop
)
652 isl_set_dump(scop
->context
);
653 for (i
= 0; i
< scop
->n_array
; ++i
)
654 pet_array_dump(scop
->arrays
[i
]);
655 for (i
= 0; i
< scop
->n_stmt
; ++i
)
656 pet_stmt_dump(scop
->stmts
[i
]);
659 /* Return 1 if the two pet_arrays are equivalent.
661 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
663 if (!array1
|| !array2
)
666 if (!isl_set_is_equal(array1
->context
, array2
->context
))
668 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
670 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
672 if (array1
->value_bounds
&&
673 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
675 if (strcmp(array1
->element_type
, array2
->element_type
))
681 /* Return 1 if the two pet_stmts are equivalent.
683 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
685 if (!stmt1
|| !stmt2
)
688 if (stmt1
->line
!= stmt2
->line
)
690 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
692 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
694 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
700 /* Return 1 if the two pet_scops are equivalent.
702 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
706 if (!scop1
|| !scop2
)
709 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
712 if (scop1
->n_array
!= scop2
->n_array
)
714 for (i
= 0; i
< scop1
->n_array
; ++i
)
715 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
718 if (scop1
->n_stmt
!= scop2
->n_stmt
)
720 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
721 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
727 /* Prefix the schedule of "stmt" with an extra dimension with constant
730 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
735 stmt
->schedule
= isl_map_insert(stmt
->schedule
, isl_dim_out
, 0, 1);
736 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
738 return pet_stmt_free(stmt
);
743 /* Prefix the schedules of all statements in "scop" with an extra
744 * dimension with constant value "pos".
746 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
753 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
754 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
756 return pet_scop_free(scop
);
762 /* Data used in embed_access.
763 * extend adds an iterator to the iteration domain
764 * var_id represents the induction variable of the corresponding loop
766 struct pet_embed_access
{
771 /* Embed the access relation in an extra outer loop.
773 * We first update the iteration domain to insert the extra dimension.
775 * If the access refers to the induction variable, then it is
776 * turned into an access to the set of integers with index (and value)
777 * equal to the induction variable.
779 * If the induction variable appears in the constraints (as a parameter),
780 * then the parameter is equated to the newly introduced iteration
781 * domain dimension and subsequently projected out.
783 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
786 struct pet_embed_access
*data
= user
;
790 access
= update_domain(access
, data
->extend
);
792 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
793 if (array_id
== data
->var_id
) {
794 access
= isl_map_insert(access
, isl_dim_out
, 0, 1);
795 access
= isl_map_equate(access
,
796 isl_dim_in
, 0, isl_dim_out
, 0);
798 isl_id_free(array_id
);
800 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
802 access
= isl_map_equate(access
,
803 isl_dim_param
, pos
, isl_dim_in
, 0);
804 access
= isl_map_project_out(access
, isl_dim_param
, pos
, 1);
806 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
807 isl_id_copy(data
->var_id
));
812 /* Embed all access relations in "expr" in an extra loop.
813 * "extend" inserts an outer loop iterator in the iteration domains.
814 * "var_id" represents the induction variable.
816 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
817 __isl_take isl_map
*extend
, __isl_keep isl_id
*var_id
)
819 struct pet_embed_access data
= { .extend
= extend
, .var_id
= var_id
};
821 expr
= expr_foreach_access(expr
, &embed_access
, &data
);
822 isl_map_free(extend
);
826 /* Embed the given pet_stmt in an extra outer loop with iteration domain
827 * "dom" and schedule "sched". "var_id" represents the induction variable
830 * The iteration domain and schedule of the statement are updated
831 * according to the iteration domain and schedule of the new loop.
833 * If the induction variable appears in the constraints (as a parameter)
834 * of the current iteration domain or the schedule of the statement,
835 * then the parameter is equated to the newly introduced iteration
836 * domain dimension and subsequently projected out.
838 * Finally, all access relations are updated based on the extra loop.
840 struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
, __isl_take isl_set
*dom
,
841 __isl_take isl_map
*sched
, __isl_take isl_id
*var_id
)
848 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
849 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
), stmt
->domain
);
850 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
, isl_id_copy(stmt_id
));
852 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
854 stmt
->domain
= isl_set_equate(stmt
->domain
,
855 isl_dim_param
, pos
, isl_dim_set
, 0);
856 stmt
->domain
= isl_set_project_out(stmt
->domain
,
857 isl_dim_param
, pos
, 1);
860 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
861 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
862 isl_dim_in
, stmt_id
);
864 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
866 stmt
->schedule
= isl_map_equate(stmt
->schedule
,
867 isl_dim_param
, pos
, isl_dim_in
, 0);
868 stmt
->schedule
= isl_map_project_out(stmt
->schedule
,
869 isl_dim_param
, pos
, 1);
872 dim
= isl_dim_map_from_set(isl_set_get_dim(stmt
->domain
));
873 extend
= isl_map_identity(dim
);
874 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
875 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
876 isl_map_get_tuple_id(extend
, isl_dim_out
));
877 stmt
->body
= expr_embed(stmt
->body
, extend
, var_id
);
882 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
883 return pet_stmt_free(stmt
);
887 /* Embed all statements in "scop" in an extra outer loop with iteration domain
888 * "dom" and schedule "sched". "var_id" represents the induction variable
891 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
892 __isl_take isl_map
*sched
, __isl_take isl_id
*id
)
899 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
900 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
902 isl_map_copy(sched
), isl_id_copy(id
));
915 return pet_scop_free(scop
);
918 /* Add extra conditions on the parameters to iteration domain of "stmt".
920 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
921 __isl_take isl_set
*cond
)
926 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
931 return pet_stmt_free(stmt
);
934 /* Add extra conditions on the parameters to all iteration domains.
936 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
937 __isl_take isl_set
*cond
)
944 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
945 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
955 return pet_scop_free(scop
);
958 /* Add all parameters in "expr" to "dim" and return the result.
960 static __isl_give isl_dim
*expr_collect_params(struct pet_expr
*expr
,
961 __isl_take isl_dim
*dim
)
967 for (i
= 0; i
< expr
->n_arg
; ++i
)
969 dim
= expr_collect_params(expr
->args
[i
], dim
);
971 if (expr
->type
== pet_expr_access
)
972 dim
= isl_dim_align_params(dim
,
973 isl_map_get_dim(expr
->acc
.access
));
978 return pet_expr_free(expr
);
981 /* Add all parameters in "stmt" to "dim" and return the result.
983 static __isl_give isl_dim
*stmt_collect_params(struct pet_stmt
*stmt
,
984 __isl_take isl_dim
*dim
)
989 dim
= isl_dim_align_params(dim
, isl_set_get_dim(stmt
->domain
));
990 dim
= isl_dim_align_params(dim
, isl_map_get_dim(stmt
->schedule
));
991 dim
= expr_collect_params(stmt
->body
, dim
);
996 return pet_stmt_free(stmt
);
999 /* Add all parameters in "array" to "dim" and return the result.
1001 static __isl_give isl_dim
*array_collect_params(struct pet_array
*array
,
1002 __isl_take isl_dim
*dim
)
1007 dim
= isl_dim_align_params(dim
, isl_set_get_dim(array
->context
));
1008 dim
= isl_dim_align_params(dim
, isl_set_get_dim(array
->extent
));
1013 return pet_array_free(array
);
1016 /* Add all parameters in "scop" to "dim" and return the result.
1018 static __isl_give isl_dim
*scop_collect_params(struct pet_scop
*scop
,
1019 __isl_take isl_dim
*dim
)
1026 for (i
= 0; i
< scop
->n_array
; ++i
)
1027 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1029 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1030 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1035 return pet_scop_free(scop
);
1038 /* Add all parameters in "dim" to all access relations in "expr".
1040 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1041 __isl_take isl_dim
*dim
)
1048 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1050 expr_propagate_params(expr
->args
[i
],
1056 if (expr
->type
== pet_expr_access
) {
1057 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1059 if (!expr
->acc
.access
)
1067 return pet_expr_free(expr
);
1070 /* Add all parameters in "dim" to the domain, schedule and
1071 * all access relations in "stmt".
1073 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1074 __isl_take isl_dim
*dim
)
1079 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_dim_copy(dim
));
1080 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1082 stmt
->body
= expr_propagate_params(stmt
->body
, isl_dim_copy(dim
));
1084 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1091 return pet_stmt_free(stmt
);
1094 /* Add all parameters in "dim" to "array".
1096 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1097 __isl_take isl_dim
*dim
)
1102 array
->context
= isl_set_align_params(array
->context
,
1104 array
->extent
= isl_set_align_params(array
->extent
,
1106 if (array
->value_bounds
) {
1107 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1109 if (!array
->value_bounds
)
1113 if (!array
->context
|| !array
->extent
)
1120 return pet_array_free(array
);
1123 /* Add all parameters in "dim" to "scop".
1125 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1126 __isl_take isl_dim
*dim
)
1133 for (i
= 0; i
< scop
->n_array
; ++i
) {
1134 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1136 if (!scop
->arrays
[i
])
1140 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1141 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1143 if (!scop
->stmts
[i
])
1151 return pet_scop_free(scop
);
1154 /* Update all isl_sets and isl_maps in "scop" such that they all
1155 * have the same parameters.
1157 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1164 dim
= isl_set_get_dim(scop
->context
);
1165 dim
= scop_collect_params(scop
, dim
);
1167 scop
->context
= isl_set_align_params(scop
->context
, isl_dim_copy(dim
));
1168 scop
= scop_propagate_params(scop
, dim
);
1173 /* Check if the given access relation accesses a (0D) array that corresponds
1174 * to one of the parameters in "dim". If so, replace the array access
1175 * by an access to the set of integers with as index (and value)
1178 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1179 __isl_take isl_dim
*dim
)
1184 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1186 pos
= isl_dim_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1190 isl_id_free(array_id
);
1194 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1196 access
= isl_map_insert(access
, isl_dim_param
, 0, 1);
1197 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1200 isl_id_free(array_id
);
1202 access
= isl_map_insert(access
, isl_dim_out
, 0, 1);
1203 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1208 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1209 * in "dim" by a value equal to the corresponding parameter.
1211 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1212 __isl_take isl_dim
*dim
)
1219 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1221 expr_detect_parameter_accesses(expr
->args
[i
],
1227 if (expr
->type
== pet_expr_access
) {
1228 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1230 if (!expr
->acc
.access
)
1238 return pet_expr_free(expr
);
1241 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1242 * in "dim" by a value equal to the corresponding parameter.
1244 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1245 __isl_take isl_dim
*dim
)
1250 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1253 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1260 return pet_stmt_free(stmt
);
1263 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1264 * in "dim" by a value equal to the corresponding parameter.
1266 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1267 __isl_take isl_dim
*dim
)
1274 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1275 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1277 if (!scop
->stmts
[i
])
1285 return pet_scop_free(scop
);
1288 /* Replace all accesses to (0D) arrays that correspond to any of
1289 * the parameters used in "scop" by a value equal
1290 * to the corresponding parameter.
1292 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1299 dim
= isl_set_get_dim(scop
->context
);
1300 dim
= scop_collect_params(scop
, dim
);
1302 scop
= scop_detect_parameter_accesses(scop
, dim
);
1307 /* Add all read access relations (if "read" is set) and/or all write
1308 * access relations (if "write" is set) to "accesses" and return the result.
1310 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1311 int read
, int write
, __isl_take isl_union_map
*accesses
)
1320 for (i
= 0; i
< expr
->n_arg
; ++i
)
1321 accesses
= expr_collect_accesses(expr
->args
[i
],
1322 read
, write
, accesses
);
1324 if (expr
->type
== pet_expr_access
) {
1325 id
= isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
1327 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1328 accesses
= isl_union_map_add_map(accesses
,
1329 isl_map_copy(expr
->acc
.access
));
1336 /* Collect and return all read access relations (if "read" is set)
1337 * and/or all write * access relations (if "write" is set) in "stmt".
1339 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1340 int read
, int write
, __isl_take isl_dim
*dim
)
1342 isl_union_map
*accesses
;
1347 accesses
= isl_union_map_empty(dim
);
1348 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1349 accesses
= isl_union_map_intersect_domain(accesses
,
1350 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1355 /* Collect and return all read access relations (if "read" is set)
1356 * and/or all write * access relations (if "write" is set) in "scop".
1358 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1359 int read
, int write
)
1362 isl_union_map
*accesses
;
1367 accesses
= isl_union_map_empty(isl_set_get_dim(scop
->context
));
1369 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1370 isl_union_map
*accesses_i
;
1371 isl_dim
*dim
= isl_set_get_dim(scop
->context
);
1372 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1374 accesses
= isl_union_map_union(accesses
, accesses_i
);
1380 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1382 return scop_collect_accesses(scop
, 1, 0);
1385 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1387 return scop_collect_accesses(scop
, 0, 1);
1390 /* Collect and return the union of iteration domains in "scop".
1392 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
1396 isl_union_set
*domain
;
1401 domain
= isl_union_set_empty(isl_set_get_dim(scop
->context
));
1403 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1404 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
1405 domain
= isl_union_set_add_set(domain
, domain_i
);
1411 /* Collect and return the schedules of the statements in "scop".
1412 * The range is normalized to the maximal number of scheduling
1415 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
1418 isl_map
*schedule_i
;
1419 isl_union_map
*schedule
;
1420 int depth
, max_depth
= 0;
1425 schedule
= isl_union_map_empty(isl_set_get_dim(scop
->context
));
1427 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1428 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
1429 if (depth
> max_depth
)
1433 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1434 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
1435 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
1436 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
1438 for (j
= depth
; j
< max_depth
; ++j
)
1439 schedule_i
= isl_map_fix_si(schedule_i
,
1441 schedule
= isl_union_map_add_map(schedule
, schedule_i
);