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
] = "=",
34 const char *pet_op_str(enum pet_op_type op
)
39 const char *pet_type_str(enum pet_expr_type type
)
41 return type_str
[type
];
44 enum pet_op_type
pet_str_op(const char *str
)
48 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
49 if (!strcmp(op_str
[i
], str
))
55 enum pet_expr_type
pet_str_type(const char *str
)
59 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
60 if (!strcmp(type_str
[i
], str
))
66 /* Construct a pet_expr from an access relation.
67 * By default, it is considered to be a read access.
69 struct pet_expr
*pet_expr_from_access(__isl_take isl_map
*access
)
71 isl_ctx
*ctx
= isl_map_get_ctx(access
);
72 struct pet_expr
*expr
;
76 expr
= isl_calloc_type(ctx
, struct pet_expr
);
80 expr
->type
= pet_expr_access
;
81 expr
->acc
.access
= access
;
91 /* Construct a unary pet_expr that performs "op" on "arg".
93 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
96 struct pet_expr
*expr
;
100 expr
= isl_alloc_type(ctx
, struct pet_expr
);
104 expr
->type
= pet_expr_unary
;
107 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
110 expr
->args
[pet_un_arg
] = arg
;
118 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
120 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
121 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
123 struct pet_expr
*expr
;
127 expr
= isl_alloc_type(ctx
, struct pet_expr
);
131 expr
->type
= pet_expr_binary
;
134 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
137 expr
->args
[pet_bin_lhs
] = lhs
;
138 expr
->args
[pet_bin_rhs
] = rhs
;
147 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
149 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
150 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
152 struct pet_expr
*expr
;
154 if (!cond
|| !lhs
|| !rhs
)
156 expr
= isl_alloc_type(ctx
, struct pet_expr
);
160 expr
->type
= pet_expr_ternary
;
162 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
165 expr
->args
[pet_ter_cond
] = cond
;
166 expr
->args
[pet_ter_true
] = lhs
;
167 expr
->args
[pet_ter_false
] = rhs
;
177 /* Construct a call pet_expr that calls function "name" with "n_arg"
178 * arguments. The caller is responsible for filling in the arguments.
180 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
183 struct pet_expr
*expr
;
185 expr
= isl_alloc_type(ctx
, struct pet_expr
);
189 expr
->type
= pet_expr_call
;
191 expr
->name
= strdup(name
);
192 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
193 if (!expr
->name
|| !expr
->args
)
194 return pet_expr_free(expr
);
199 /* Construct a pet_expr that represents the double "d".
201 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double d
)
203 struct pet_expr
*expr
;
205 expr
= isl_calloc_type(ctx
, struct pet_expr
);
209 expr
->type
= pet_expr_double
;
215 void *pet_expr_free(struct pet_expr
*expr
)
222 for (i
= 0; i
< expr
->n_arg
; ++i
)
223 pet_expr_free(expr
->args
[i
]);
226 switch (expr
->type
) {
227 case pet_expr_access
:
228 isl_map_free(expr
->acc
.access
);
233 case pet_expr_double
:
235 case pet_expr_binary
:
236 case pet_expr_ternary
:
244 static void expr_dump(struct pet_expr
*expr
, int indent
)
251 fprintf(stderr
, "%*s", indent
, "");
253 switch (expr
->type
) {
254 case pet_expr_double
:
255 fprintf(stderr
, "%g\n", expr
->d
);
257 case pet_expr_access
:
258 isl_map_dump(expr
->acc
.access
);
259 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
261 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
262 "", expr
->acc
.write
);
263 for (i
= 0; i
< expr
->n_arg
; ++i
)
264 expr_dump(expr
->args
[i
], indent
+ 2);
267 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
268 expr_dump(expr
->args
[pet_un_arg
], indent
+ 2);
270 case pet_expr_binary
:
271 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
272 expr_dump(expr
->args
[pet_bin_lhs
], indent
+ 2);
273 expr_dump(expr
->args
[pet_bin_rhs
], indent
+ 2);
275 case pet_expr_ternary
:
276 fprintf(stderr
, "?:\n");
277 expr_dump(expr
->args
[pet_ter_cond
], indent
+ 2);
278 expr_dump(expr
->args
[pet_ter_true
], indent
+ 2);
279 expr_dump(expr
->args
[pet_ter_false
], indent
+ 2);
282 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
283 for (i
= 0; i
< expr
->n_arg
; ++i
)
284 expr_dump(expr
->args
[i
], indent
+ 2);
289 void pet_expr_dump(struct pet_expr
*expr
)
294 /* Return 1 if the two pet_exprs are equivalent.
296 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
300 if (!expr1
|| !expr2
)
303 if (expr1
->type
!= expr2
->type
)
305 if (expr1
->n_arg
!= expr2
->n_arg
)
307 for (i
= 0; i
< expr1
->n_arg
; ++i
)
308 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
310 switch (expr1
->type
) {
311 case pet_expr_double
:
312 if (expr1
->d
!= expr2
->d
)
315 case pet_expr_access
:
316 if (expr1
->acc
.read
!= expr2
->acc
.read
)
318 if (expr1
->acc
.write
!= expr2
->acc
.write
)
320 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
324 case pet_expr_binary
:
325 case pet_expr_ternary
:
326 if (expr1
->op
!= expr2
->op
)
330 if (strcmp(expr1
->name
, expr2
->name
))
338 /* Add extra conditions on the parameters to all access relations in "expr".
340 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
341 __isl_take isl_set
*cond
)
348 for (i
= 0; i
< expr
->n_arg
; ++i
) {
349 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
355 if (expr
->type
== pet_expr_access
) {
356 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
358 if (!expr
->acc
.access
)
366 return pet_expr_free(expr
);
369 /* Modify all access relations in "expr" by calling "fn" on them.
371 static struct pet_expr
*expr_foreach_access(struct pet_expr
*expr
,
372 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*access
, void *user
),
380 for (i
= 0; i
< expr
->n_arg
; ++i
) {
381 expr
->args
[i
] = expr_foreach_access(expr
->args
[i
], fn
, user
);
383 return pet_expr_free(expr
);
386 if (expr
->type
== pet_expr_access
) {
387 expr
->acc
.access
= fn(expr
->acc
.access
, user
);
388 if (!expr
->acc
.access
)
389 return pet_expr_free(expr
);
395 /* Modify the given access relation based on the given iteration space
397 * If the access has any arguments then the domain of the access relation
398 * is a wrapped mapping from the iteration space to the space of
399 * argument values. We only need to change the domain of this wrapped
400 * mapping, so we extend the input transformation with an identity mapping
401 * on the space of argument values.
403 static __isl_give isl_map
*update_domain(__isl_take isl_map
*access
,
406 isl_map
*update
= user
;
409 update
= isl_map_copy(update
);
411 dim
= isl_map_get_space(access
);
412 dim
= isl_space_domain(dim
);
413 if (!isl_space_is_wrapping(dim
))
417 dim
= isl_space_unwrap(dim
);
418 dim
= isl_space_range(dim
);
419 dim
= isl_space_map_from_set(dim
);
420 id
= isl_map_identity(dim
);
421 update
= isl_map_product(update
, id
);
424 return isl_map_apply_domain(access
, update
);
427 /* Modify all access relations in "expr" based on the given iteration space
430 static struct pet_expr
*expr_update_domain(struct pet_expr
*expr
,
431 __isl_take isl_map
*update
)
433 expr
= expr_foreach_access(expr
, &update_domain
, update
);
434 isl_map_free(update
);
438 /* Construct a pet_stmt with given line number and statement
439 * number from a pet_expr.
440 * The initial iteration domain is the zero-dimensional universe.
441 * The domains of all access relations are modified to refer
442 * to the statement iteration domain.
444 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
, int id
,
445 struct pet_expr
*expr
)
447 struct pet_stmt
*stmt
;
457 stmt
= isl_alloc_type(ctx
, struct pet_stmt
);
459 return pet_expr_free(expr
);
461 dim
= isl_space_set_alloc(ctx
, 0, 0);
462 snprintf(name
, sizeof(name
), "S_%d", id
);
463 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
464 dom
= isl_set_universe(isl_space_copy(dim
));
465 sched
= isl_map_from_domain(isl_set_copy(dom
));
467 dim
= isl_space_from_range(dim
);
468 add_name
= isl_map_universe(dim
);
469 expr
= expr_update_domain(expr
, add_name
);
473 stmt
->schedule
= sched
;
476 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
477 return pet_stmt_free(stmt
);
482 void *pet_stmt_free(struct pet_stmt
*stmt
)
487 isl_set_free(stmt
->domain
);
488 isl_map_free(stmt
->schedule
);
489 pet_expr_free(stmt
->body
);
495 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
500 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
501 fprintf(stderr
, "%*s", indent
, "");
502 isl_set_dump(stmt
->domain
);
503 fprintf(stderr
, "%*s", indent
, "");
504 isl_map_dump(stmt
->schedule
);
505 expr_dump(stmt
->body
, indent
);
508 void pet_stmt_dump(struct pet_stmt
*stmt
)
513 void *pet_array_free(struct pet_array
*array
)
518 isl_set_free(array
->context
);
519 isl_set_free(array
->extent
);
520 isl_set_free(array
->value_bounds
);
521 free(array
->element_type
);
527 void pet_array_dump(struct pet_array
*array
)
532 isl_set_dump(array
->context
);
533 isl_set_dump(array
->extent
);
534 isl_set_dump(array
->value_bounds
);
535 fprintf(stderr
, "%s %s\n", array
->element_type
,
536 array
->live_out
? "live-out" : "");
539 /* Construct a pet_scop with room for n statements.
541 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
543 struct pet_scop
*scop
;
545 scop
= isl_calloc_type(ctx
, struct pet_scop
);
549 scop
->context
= isl_set_universe(isl_space_params_alloc(ctx
, 0));
550 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
551 if (!scop
->context
|| !scop
->stmts
)
552 return pet_scop_free(scop
);
559 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
561 return scop_alloc(ctx
, 0);
564 /* Construct a pet_scop that contains the given pet_stmt.
566 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
568 struct pet_scop
*scop
;
573 scop
= scop_alloc(ctx
, 1);
575 scop
->stmts
[0] = stmt
;
584 /* Construct a pet_scop that contains the statements in "scop1" and "scop2".
586 struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
587 struct pet_scop
*scop2
)
590 struct pet_scop
*scop
;
592 if (!scop1
|| !scop2
)
595 if (scop1
->n_stmt
== 0) {
596 pet_scop_free(scop1
);
600 if (scop2
->n_stmt
== 0) {
601 pet_scop_free(scop2
);
605 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
609 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
610 scop
->stmts
[i
] = scop1
->stmts
[i
];
611 scop1
->stmts
[i
] = NULL
;
614 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
615 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
616 scop2
->stmts
[i
] = NULL
;
619 pet_scop_free(scop1
);
620 pet_scop_free(scop2
);
623 pet_scop_free(scop1
);
624 pet_scop_free(scop2
);
628 void *pet_scop_free(struct pet_scop
*scop
)
634 isl_set_free(scop
->context
);
636 for (i
= 0; i
< scop
->n_array
; ++i
)
637 pet_array_free(scop
->arrays
[i
]);
640 for (i
= 0; i
< scop
->n_stmt
; ++i
)
641 pet_stmt_free(scop
->stmts
[i
]);
647 void pet_scop_dump(struct pet_scop
*scop
)
654 isl_set_dump(scop
->context
);
655 for (i
= 0; i
< scop
->n_array
; ++i
)
656 pet_array_dump(scop
->arrays
[i
]);
657 for (i
= 0; i
< scop
->n_stmt
; ++i
)
658 pet_stmt_dump(scop
->stmts
[i
]);
661 /* Return 1 if the two pet_arrays are equivalent.
663 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
665 if (!array1
|| !array2
)
668 if (!isl_set_is_equal(array1
->context
, array2
->context
))
670 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
672 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
674 if (array1
->value_bounds
&&
675 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
677 if (strcmp(array1
->element_type
, array2
->element_type
))
679 if (array1
->live_out
!= array2
->live_out
)
685 /* Return 1 if the two pet_stmts are equivalent.
687 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
689 if (!stmt1
|| !stmt2
)
692 if (stmt1
->line
!= stmt2
->line
)
694 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
696 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
698 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
704 /* Return 1 if the two pet_scops are equivalent.
706 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
710 if (!scop1
|| !scop2
)
713 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
716 if (scop1
->n_array
!= scop2
->n_array
)
718 for (i
= 0; i
< scop1
->n_array
; ++i
)
719 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
722 if (scop1
->n_stmt
!= scop2
->n_stmt
)
724 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
725 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
731 /* Prefix the schedule of "stmt" with an extra dimension with constant
734 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
739 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
740 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
742 return pet_stmt_free(stmt
);
747 /* Prefix the schedules of all statements in "scop" with an extra
748 * dimension with constant value "pos".
750 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
757 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
758 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
760 return pet_scop_free(scop
);
766 /* Data used in embed_access.
767 * extend adds an iterator to the iteration domain
768 * var_id represents the induction variable of the corresponding loop
770 struct pet_embed_access
{
775 /* Embed the access relation in an extra outer loop.
777 * We first update the iteration domain to insert the extra dimension.
779 * If the access refers to the induction variable, then it is
780 * turned into an access to the set of integers with index (and value)
781 * equal to the induction variable.
783 * If the induction variable appears in the constraints (as a parameter),
784 * then the parameter is equated to the newly introduced iteration
785 * domain dimension and subsequently projected out.
787 static __isl_give isl_map
*embed_access(__isl_take isl_map
*access
,
790 struct pet_embed_access
*data
= user
;
791 isl_id
*array_id
= NULL
;
794 access
= update_domain(access
, data
->extend
);
796 if (isl_map_has_tuple_id(access
, isl_dim_out
))
797 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
798 if (array_id
== data
->var_id
) {
799 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
800 access
= isl_map_equate(access
,
801 isl_dim_in
, 0, isl_dim_out
, 0);
803 isl_id_free(array_id
);
805 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
807 access
= isl_map_equate(access
,
808 isl_dim_param
, pos
, isl_dim_in
, 0);
809 access
= isl_map_project_out(access
, isl_dim_param
, pos
, 1);
811 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
812 isl_id_copy(data
->var_id
));
817 /* Embed all access relations in "expr" in an extra loop.
818 * "extend" inserts an outer loop iterator in the iteration domains.
819 * "var_id" represents the induction variable.
821 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
822 __isl_take isl_map
*extend
, __isl_keep isl_id
*var_id
)
824 struct pet_embed_access data
= { .extend
= extend
, .var_id
= var_id
};
826 expr
= expr_foreach_access(expr
, &embed_access
, &data
);
827 isl_map_free(extend
);
831 /* Embed the given pet_stmt in an extra outer loop with iteration domain
832 * "dom" and schedule "sched". "var_id" represents the induction variable
835 * The iteration domain and schedule of the statement are updated
836 * according to the iteration domain and schedule of the new loop.
838 * If the induction variable appears in the constraints (as a parameter)
839 * of the current iteration domain or the schedule of the statement,
840 * then the parameter is equated to the newly introduced iteration
841 * domain dimension and subsequently projected out.
843 * Finally, all access relations are updated based on the extra loop.
845 struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
, __isl_take isl_set
*dom
,
846 __isl_take isl_map
*sched
, __isl_take isl_id
*var_id
)
853 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
854 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
), stmt
->domain
);
855 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
, isl_id_copy(stmt_id
));
857 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
859 stmt
->domain
= isl_set_equate(stmt
->domain
,
860 isl_dim_param
, pos
, isl_dim_set
, 0);
861 stmt
->domain
= isl_set_project_out(stmt
->domain
,
862 isl_dim_param
, pos
, 1);
865 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
866 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
867 isl_dim_in
, stmt_id
);
869 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
871 stmt
->schedule
= isl_map_equate(stmt
->schedule
,
872 isl_dim_param
, pos
, isl_dim_in
, 0);
873 stmt
->schedule
= isl_map_project_out(stmt
->schedule
,
874 isl_dim_param
, pos
, 1);
877 dim
= isl_space_map_from_set(isl_set_get_space(stmt
->domain
));
878 extend
= isl_map_identity(dim
);
879 extend
= isl_map_remove_dims(extend
, isl_dim_in
, 0, 1);
880 extend
= isl_map_set_tuple_id(extend
, isl_dim_in
,
881 isl_map_get_tuple_id(extend
, isl_dim_out
));
882 stmt
->body
= expr_embed(stmt
->body
, extend
, var_id
);
887 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
888 return pet_stmt_free(stmt
);
892 /* Embed all statements in "scop" in an extra outer loop with iteration domain
893 * "dom" and schedule "sched". "var_id" represents the induction variable
896 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
897 __isl_take isl_map
*sched
, __isl_take isl_id
*id
)
904 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
905 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
907 isl_map_copy(sched
), isl_id_copy(id
));
920 return pet_scop_free(scop
);
923 /* Add extra conditions on the parameters to iteration domain of "stmt".
925 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
926 __isl_take isl_set
*cond
)
931 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
936 return pet_stmt_free(stmt
);
939 /* Add extra conditions on the parameters to all iteration domains.
941 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
942 __isl_take isl_set
*cond
)
949 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
950 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
960 return pet_scop_free(scop
);
963 /* Add all parameters in "expr" to "dim" and return the result.
965 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
966 __isl_take isl_space
*dim
)
972 for (i
= 0; i
< expr
->n_arg
; ++i
)
974 dim
= expr_collect_params(expr
->args
[i
], dim
);
976 if (expr
->type
== pet_expr_access
)
977 dim
= isl_space_align_params(dim
,
978 isl_map_get_space(expr
->acc
.access
));
983 return pet_expr_free(expr
);
986 /* Add all parameters in "stmt" to "dim" and return the result.
988 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
989 __isl_take isl_space
*dim
)
994 dim
= isl_space_align_params(dim
, isl_set_get_space(stmt
->domain
));
995 dim
= isl_space_align_params(dim
, isl_map_get_space(stmt
->schedule
));
996 dim
= expr_collect_params(stmt
->body
, dim
);
1000 isl_space_free(dim
);
1001 return pet_stmt_free(stmt
);
1004 /* Add all parameters in "array" to "dim" and return the result.
1006 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1007 __isl_take isl_space
*dim
)
1012 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->context
));
1013 dim
= isl_space_align_params(dim
, isl_set_get_space(array
->extent
));
1017 isl_space_free(dim
);
1018 return pet_array_free(array
);
1021 /* Add all parameters in "scop" to "dim" and return the result.
1023 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1024 __isl_take isl_space
*dim
)
1031 for (i
= 0; i
< scop
->n_array
; ++i
)
1032 dim
= array_collect_params(scop
->arrays
[i
], dim
);
1034 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1035 dim
= stmt_collect_params(scop
->stmts
[i
], dim
);
1039 isl_space_free(dim
);
1040 return pet_scop_free(scop
);
1043 /* Add all parameters in "dim" to all access relations in "expr".
1045 static struct pet_expr
*expr_propagate_params(struct pet_expr
*expr
,
1046 __isl_take isl_space
*dim
)
1053 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1055 expr_propagate_params(expr
->args
[i
],
1056 isl_space_copy(dim
));
1061 if (expr
->type
== pet_expr_access
) {
1062 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1063 isl_space_copy(dim
));
1064 if (!expr
->acc
.access
)
1068 isl_space_free(dim
);
1071 isl_space_free(dim
);
1072 return pet_expr_free(expr
);
1075 /* Add all parameters in "dim" to the domain, schedule and
1076 * all access relations in "stmt".
1078 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
1079 __isl_take isl_space
*dim
)
1084 stmt
->domain
= isl_set_align_params(stmt
->domain
, isl_space_copy(dim
));
1085 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
1086 isl_space_copy(dim
));
1087 stmt
->body
= expr_propagate_params(stmt
->body
, isl_space_copy(dim
));
1089 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1092 isl_space_free(dim
);
1095 isl_space_free(dim
);
1096 return pet_stmt_free(stmt
);
1099 /* Add all parameters in "dim" to "array".
1101 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
1102 __isl_take isl_space
*dim
)
1107 array
->context
= isl_set_align_params(array
->context
,
1108 isl_space_copy(dim
));
1109 array
->extent
= isl_set_align_params(array
->extent
,
1110 isl_space_copy(dim
));
1111 if (array
->value_bounds
) {
1112 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
1113 isl_space_copy(dim
));
1114 if (!array
->value_bounds
)
1118 if (!array
->context
|| !array
->extent
)
1121 isl_space_free(dim
);
1124 isl_space_free(dim
);
1125 return pet_array_free(array
);
1128 /* Add all parameters in "dim" to "scop".
1130 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
1131 __isl_take isl_space
*dim
)
1138 for (i
= 0; i
< scop
->n_array
; ++i
) {
1139 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
1140 isl_space_copy(dim
));
1141 if (!scop
->arrays
[i
])
1145 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1146 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
1147 isl_space_copy(dim
));
1148 if (!scop
->stmts
[i
])
1152 isl_space_free(dim
);
1155 isl_space_free(dim
);
1156 return pet_scop_free(scop
);
1159 /* Update all isl_sets and isl_maps in "scop" such that they all
1160 * have the same parameters.
1162 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
1169 dim
= isl_set_get_space(scop
->context
);
1170 dim
= scop_collect_params(scop
, dim
);
1172 scop
->context
= isl_set_align_params(scop
->context
, isl_space_copy(dim
));
1173 scop
= scop_propagate_params(scop
, dim
);
1178 /* Check if the given access relation accesses a (0D) array that corresponds
1179 * to one of the parameters in "dim". If so, replace the array access
1180 * by an access to the set of integers with as index (and value)
1183 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1184 __isl_take isl_space
*dim
)
1186 isl_id
*array_id
= NULL
;
1189 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1190 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1191 pos
= isl_space_find_dim_by_id(dim
, isl_dim_param
, array_id
);
1193 isl_space_free(dim
);
1196 isl_id_free(array_id
);
1200 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1202 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1203 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1206 isl_id_free(array_id
);
1208 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1209 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1214 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1215 * in "dim" by a value equal to the corresponding parameter.
1217 static struct pet_expr
*expr_detect_parameter_accesses(struct pet_expr
*expr
,
1218 __isl_take isl_space
*dim
)
1225 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1227 expr_detect_parameter_accesses(expr
->args
[i
],
1228 isl_space_copy(dim
));
1233 if (expr
->type
== pet_expr_access
) {
1234 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1235 isl_space_copy(dim
));
1236 if (!expr
->acc
.access
)
1240 isl_space_free(dim
);
1243 isl_space_free(dim
);
1244 return pet_expr_free(expr
);
1247 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1248 * in "dim" by a value equal to the corresponding parameter.
1250 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
1251 __isl_take isl_space
*dim
)
1256 stmt
->body
= expr_detect_parameter_accesses(stmt
->body
,
1257 isl_space_copy(dim
));
1259 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1262 isl_space_free(dim
);
1265 isl_space_free(dim
);
1266 return pet_stmt_free(stmt
);
1269 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1270 * in "dim" by a value equal to the corresponding parameter.
1272 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
1273 __isl_take isl_space
*dim
)
1280 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1281 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
1282 isl_space_copy(dim
));
1283 if (!scop
->stmts
[i
])
1287 isl_space_free(dim
);
1290 isl_space_free(dim
);
1291 return pet_scop_free(scop
);
1294 /* Replace all accesses to (0D) arrays that correspond to any of
1295 * the parameters used in "scop" by a value equal
1296 * to the corresponding parameter.
1298 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
1305 dim
= isl_set_get_space(scop
->context
);
1306 dim
= scop_collect_params(scop
, dim
);
1308 scop
= scop_detect_parameter_accesses(scop
, dim
);
1313 /* Add all read access relations (if "read" is set) and/or all write
1314 * access relations (if "write" is set) to "accesses" and return the result.
1316 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
1317 int read
, int write
, __isl_take isl_union_map
*accesses
)
1326 for (i
= 0; i
< expr
->n_arg
; ++i
)
1327 accesses
= expr_collect_accesses(expr
->args
[i
],
1328 read
, write
, accesses
);
1330 if (expr
->type
== pet_expr_access
&&
1331 isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
) &&
1332 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)))
1333 accesses
= isl_union_map_add_map(accesses
,
1334 isl_map_copy(expr
->acc
.access
));
1339 /* Collect and return all read access relations (if "read" is set)
1340 * and/or all write * access relations (if "write" is set) in "stmt".
1342 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
1343 int read
, int write
, __isl_take isl_space
*dim
)
1345 isl_union_map
*accesses
;
1350 accesses
= isl_union_map_empty(dim
);
1351 accesses
= expr_collect_accesses(stmt
->body
, read
, write
, accesses
);
1352 accesses
= isl_union_map_intersect_domain(accesses
,
1353 isl_union_set_from_set(isl_set_copy(stmt
->domain
)));
1358 /* Collect and return all read access relations (if "read" is set)
1359 * and/or all write * access relations (if "write" is set) in "scop".
1361 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
1362 int read
, int write
)
1365 isl_union_map
*accesses
;
1370 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1372 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1373 isl_union_map
*accesses_i
;
1374 isl_space
*dim
= isl_set_get_space(scop
->context
);
1375 accesses_i
= stmt_collect_accesses(scop
->stmts
[i
],
1377 accesses
= isl_union_map_union(accesses
, accesses_i
);
1383 __isl_give isl_union_map
*pet_scop_collect_reads(struct pet_scop
*scop
)
1385 return scop_collect_accesses(scop
, 1, 0);
1388 __isl_give isl_union_map
*pet_scop_collect_writes(struct pet_scop
*scop
)
1390 return scop_collect_accesses(scop
, 0, 1);
1393 /* Collect and return the union of iteration domains in "scop".
1395 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
1399 isl_union_set
*domain
;
1404 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
1406 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1407 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
1408 domain
= isl_union_set_add_set(domain
, domain_i
);
1414 /* Collect and return the schedules of the statements in "scop".
1415 * The range is normalized to the maximal number of scheduling
1418 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
1421 isl_map
*schedule_i
;
1422 isl_union_map
*schedule
;
1423 int depth
, max_depth
= 0;
1428 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
1430 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1431 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
1432 if (depth
> max_depth
)
1436 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1437 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
1438 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
1439 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
1441 for (j
= depth
; j
< max_depth
; ++j
)
1442 schedule_i
= isl_map_fix_si(schedule_i
,
1444 schedule
= isl_union_map_add_map(schedule
, schedule_i
);