2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
46 #include "value_bounds.h"
48 /* pet_scop with extra information that is used during parsing and printing.
50 * In particular, we keep track of conditions under which we want
51 * to skip the rest of the current loop iteration (skip[pet_skip_now])
52 * and of conditions under which we want to skip subsequent
53 * loop iterations (skip[pet_skip_later]).
55 * The conditions are represented as index expressions defined
56 * over a zero-dimensional domain. The index expression is either
57 * a boolean affine expression or an access to a variable, which
58 * is assumed to attain values zero and one. The condition holds
59 * if the variable has value one or if the affine expression
60 * has value one (typically for only part of the parameter space).
62 * A missing condition (skip[type] == NULL) means that we don't want
65 * Additionally, we keep track of the original input file
66 * inside pet_transform_C_source.
71 isl_multi_pw_aff
*skip
[2];
75 /* Construct a pet_stmt with given domain, location and statement
76 * number from a pet_expr.
77 * The input domain is anonymous and is the same as the domains
78 * of the access expressions inside "expr".
79 * These domains are modified to include the name of the statement.
80 * This name is given by "label" if it is non-NULL.
81 * Otherwise, the name is constructed as S_<id>.
83 struct pet_stmt
*pet_stmt_from_pet_expr(__isl_take isl_set
*domain
,
84 __isl_take pet_loc
*loc
, __isl_take isl_id
*label
, int id
,
85 __isl_take pet_expr
*expr
)
87 struct pet_stmt
*stmt
;
92 isl_multi_pw_aff
*add_name
;
95 if (!domain
|| !loc
|| !expr
)
98 ctx
= pet_expr_get_ctx(expr
);
99 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
104 snprintf(name
, sizeof(name
), "S_%d", id
);
105 label
= isl_id_alloc(ctx
, name
, NULL
);
107 domain
= isl_set_set_tuple_id(domain
, label
);
108 space
= isl_set_get_space(domain
);
109 space
= pet_nested_remove_from_space(space
);
110 sched
= isl_map_universe(isl_space_from_domain(isl_space_copy(space
)));
111 ma
= pet_prefix_projection(space
, isl_space_dim(space
, isl_dim_set
));
113 add_name
= isl_multi_pw_aff_from_multi_aff(ma
);
114 expr
= pet_expr_update_domain(expr
, add_name
);
117 stmt
->domain
= domain
;
118 stmt
->schedule
= sched
;
121 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
122 return pet_stmt_free(stmt
);
126 isl_set_free(domain
);
133 void *pet_stmt_free(struct pet_stmt
*stmt
)
140 pet_loc_free(stmt
->loc
);
141 isl_set_free(stmt
->domain
);
142 isl_map_free(stmt
->schedule
);
143 pet_expr_free(stmt
->body
);
145 for (i
= 0; i
< stmt
->n_arg
; ++i
)
146 pet_expr_free(stmt
->args
[i
]);
153 /* Return the iteration space of "stmt".
155 * If the statement has arguments, then stmt->domain is a wrapped map
156 * mapping the iteration domain to the values of the arguments
157 * for which this statement is executed.
158 * In this case, we need to extract the domain space of this wrapped map.
160 __isl_give isl_space
*pet_stmt_get_space(struct pet_stmt
*stmt
)
167 space
= isl_set_get_space(stmt
->domain
);
168 if (isl_space_is_wrapping(space
))
169 space
= isl_space_domain(isl_space_unwrap(space
));
174 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
181 fprintf(stderr
, "%*s%d\n", indent
, "", pet_loc_get_line(stmt
->loc
));
182 fprintf(stderr
, "%*s", indent
, "");
183 isl_set_dump(stmt
->domain
);
184 fprintf(stderr
, "%*s", indent
, "");
185 isl_map_dump(stmt
->schedule
);
186 pet_expr_dump_with_indent(stmt
->body
, indent
);
187 for (i
= 0; i
< stmt
->n_arg
; ++i
)
188 pet_expr_dump_with_indent(stmt
->args
[i
], indent
+ 2);
191 void pet_stmt_dump(struct pet_stmt
*stmt
)
196 /* Allocate a new pet_type with the given "name" and "definition".
198 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
199 const char *definition
)
201 struct pet_type
*type
;
203 type
= isl_alloc_type(ctx
, struct pet_type
);
207 type
->name
= strdup(name
);
208 type
->definition
= strdup(definition
);
210 if (!type
->name
|| !type
->definition
)
211 return pet_type_free(type
);
216 /* Free "type" and return NULL.
218 struct pet_type
*pet_type_free(struct pet_type
*type
)
224 free(type
->definition
);
230 struct pet_array
*pet_array_free(struct pet_array
*array
)
235 isl_set_free(array
->context
);
236 isl_set_free(array
->extent
);
237 isl_set_free(array
->value_bounds
);
238 free(array
->element_type
);
244 void pet_array_dump(struct pet_array
*array
)
249 isl_set_dump(array
->context
);
250 isl_set_dump(array
->extent
);
251 isl_set_dump(array
->value_bounds
);
252 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
253 array
->element_is_record
? " element-is-record" : "",
254 array
->live_out
? " live-out" : "");
257 /* Alloc a pet_scop structure, with extra room for information that
258 * is only used during parsing.
260 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
262 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
265 /* Construct a pet_scop with room for n statements.
267 * Since no information on the location is known at this point,
268 * scop->loc is initialized with pet_loc_dummy.
270 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
273 struct pet_scop
*scop
;
275 scop
= pet_scop_alloc(ctx
);
279 space
= isl_space_params_alloc(ctx
, 0);
280 scop
->context
= isl_set_universe(isl_space_copy(space
));
281 scop
->context_value
= isl_set_universe(space
);
282 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
283 if (!scop
->context
|| !scop
->stmts
)
284 return pet_scop_free(scop
);
286 scop
->loc
= &pet_loc_dummy
;
292 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
294 return scop_alloc(ctx
, 0);
297 /* Update "context" with respect to the valid parameter values for "access".
299 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
300 __isl_take isl_set
*context
)
302 context
= isl_set_intersect(context
,
303 isl_map_params(isl_map_copy(access
)));
307 /* Update "context" with respect to the valid parameter values for "expr".
309 * If "expr" represents a conditional operator, then a parameter value
310 * needs to be valid for the condition and for at least one of the
311 * remaining two arguments.
312 * If the condition is an affine expression, then we can be a bit more specific.
313 * The parameter then has to be valid for the second argument for
314 * non-zero accesses and valid for the third argument for zero accesses.
316 static __isl_give isl_set
*expr_extract_context(__isl_keep pet_expr
*expr
,
317 __isl_take isl_set
*context
)
321 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
323 isl_set
*context1
, *context2
;
325 is_aff
= pet_expr_is_affine(expr
->args
[0]);
329 context
= expr_extract_context(expr
->args
[0], context
);
330 context1
= expr_extract_context(expr
->args
[1],
331 isl_set_copy(context
));
332 context2
= expr_extract_context(expr
->args
[2], context
);
338 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
339 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
340 zero_set
= isl_map_params(access
);
341 context1
= isl_set_subtract(context1
,
342 isl_set_copy(zero_set
));
343 context2
= isl_set_intersect(context2
, zero_set
);
346 context
= isl_set_union(context1
, context2
);
347 context
= isl_set_coalesce(context
);
352 for (i
= 0; i
< expr
->n_arg
; ++i
)
353 context
= expr_extract_context(expr
->args
[i
], context
);
355 if (expr
->type
== pet_expr_access
)
356 context
= access_extract_context(expr
->acc
.access
, context
);
360 isl_set_free(context
);
364 /* Update "context" with respect to the valid parameter values for "stmt".
366 * If the statement is an assume statement with an affine expression,
367 * then intersect "context" with that expression.
368 * Otherwise, intersect "context" with the contexts of the expressions
371 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
372 __isl_take isl_set
*context
)
376 if (pet_stmt_is_assume(stmt
) &&
377 pet_expr_is_affine(stmt
->body
->args
[0])) {
378 isl_multi_pw_aff
*index
;
382 index
= stmt
->body
->args
[0]->acc
.index
;
383 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
384 cond
= isl_set_params(isl_pw_aff_non_zero_set(pa
));
385 return isl_set_intersect(context
, cond
);
388 for (i
= 0; i
< stmt
->n_arg
; ++i
)
389 context
= expr_extract_context(stmt
->args
[i
], context
);
391 context
= expr_extract_context(stmt
->body
, context
);
396 /* Construct a pet_scop that contains the given pet_stmt.
398 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
400 struct pet_scop
*scop
;
405 scop
= scop_alloc(ctx
, 1);
409 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
413 scop
->stmts
[0] = stmt
;
414 scop
->loc
= pet_loc_copy(stmt
->loc
);
417 return pet_scop_free(scop
);
426 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
427 * does it represent an affine expression?
429 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
433 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
440 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
442 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
443 __isl_take isl_set
*dom
)
446 pa
= isl_set_indicator_function(set
);
447 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
451 /* Return "lhs || rhs", defined on the shared definition domain.
453 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
454 __isl_take isl_pw_aff
*rhs
)
459 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
460 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
461 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
462 isl_pw_aff_non_zero_set(rhs
));
463 cond
= isl_set_coalesce(cond
);
464 return indicator_function(cond
, dom
);
467 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
468 * ext may be equal to either ext1 or ext2.
470 * The two skips that need to be combined are assumed to be affine expressions.
472 * We need to skip in ext if we need to skip in either ext1 or ext2.
473 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
475 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
476 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
479 isl_pw_aff
*skip
, *skip1
, *skip2
;
483 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
485 if (!ext1
->skip
[type
]) {
488 ext
->skip
[type
] = ext2
->skip
[type
];
489 ext2
->skip
[type
] = NULL
;
492 if (!ext2
->skip
[type
]) {
495 ext
->skip
[type
] = ext1
->skip
[type
];
496 ext1
->skip
[type
] = NULL
;
500 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
501 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
502 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
503 isl_error_internal
, "can only combine affine skips",
506 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
507 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
508 skip
= pw_aff_or(skip1
, skip2
);
509 isl_multi_pw_aff_free(ext1
->skip
[type
]);
510 ext1
->skip
[type
] = NULL
;
511 isl_multi_pw_aff_free(ext2
->skip
[type
]);
512 ext2
->skip
[type
] = NULL
;
513 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
514 if (!ext
->skip
[type
])
519 pet_scop_free(&ext
->scop
);
523 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
524 * where type takes on the values pet_skip_now and pet_skip_later.
525 * scop may be equal to either scop1 or scop2.
527 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
528 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
530 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
531 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
532 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
534 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
535 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
539 /* Update start and end of scop->loc to include the region from "start"
540 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
541 * does not have any offset information yet and we simply take the information
542 * from "start" and "end". Otherwise, we update loc using "start" and "end".
544 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
545 unsigned start
, unsigned end
)
550 if (scop
->loc
== &pet_loc_dummy
)
551 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
554 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
557 return pet_scop_free(scop
);
562 /* Update start and end of scop->loc to include the region identified
565 struct pet_scop
*pet_scop_update_start_end_from_loc(struct pet_scop
*scop
,
566 __isl_keep pet_loc
*loc
)
568 return pet_scop_update_start_end(scop
, pet_loc_get_start(loc
),
569 pet_loc_get_end(loc
));
572 /* Replace the location of "scop" by "loc".
574 struct pet_scop
*pet_scop_set_loc(struct pet_scop
*scop
,
575 __isl_take pet_loc
*loc
)
580 pet_loc_free(scop
->loc
);
590 /* Does "implication" appear in the list of implications of "scop"?
592 static int is_known_implication(struct pet_scop
*scop
,
593 struct pet_implication
*implication
)
597 for (i
= 0; i
< scop
->n_implication
; ++i
) {
598 struct pet_implication
*pi
= scop
->implications
[i
];
601 if (pi
->satisfied
!= implication
->satisfied
)
603 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
613 /* Store the concatenation of the implications of "scop1" and "scop2"
614 * in "scop", removing duplicates (i.e., implications in "scop2" that
615 * already appear in "scop1").
617 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
618 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
625 if (scop2
->n_implication
== 0) {
626 scop
->n_implication
= scop1
->n_implication
;
627 scop
->implications
= scop1
->implications
;
628 scop1
->n_implication
= 0;
629 scop1
->implications
= NULL
;
633 if (scop1
->n_implication
== 0) {
634 scop
->n_implication
= scop2
->n_implication
;
635 scop
->implications
= scop2
->implications
;
636 scop2
->n_implication
= 0;
637 scop2
->implications
= NULL
;
641 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
642 scop1
->n_implication
+ scop2
->n_implication
);
643 if (!scop
->implications
)
644 return pet_scop_free(scop
);
646 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
647 scop
->implications
[i
] = scop1
->implications
[i
];
648 scop1
->implications
[i
] = NULL
;
651 scop
->n_implication
= scop1
->n_implication
;
652 j
= scop1
->n_implication
;
653 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
656 known
= is_known_implication(scop
, scop2
->implications
[i
]);
658 return pet_scop_free(scop
);
661 scop
->implications
[j
++] = scop2
->implications
[i
];
662 scop2
->implications
[i
] = NULL
;
664 scop
->n_implication
= j
;
669 /* Combine the offset information of "scop1" and "scop2" into "scop".
671 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
672 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
674 if (scop1
->loc
!= &pet_loc_dummy
)
675 scop
= pet_scop_update_start_end_from_loc(scop
, scop1
->loc
);
676 if (scop2
->loc
!= &pet_loc_dummy
)
677 scop
= pet_scop_update_start_end_from_loc(scop
, scop2
->loc
);
681 /* Construct a pet_scop that contains the offset information,
682 * arrays, statements and skip information in "scop1" and "scop2".
684 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
685 struct pet_scop
*scop2
)
688 struct pet_scop
*scop
= NULL
;
690 if (!scop1
|| !scop2
)
693 if (scop1
->n_stmt
== 0) {
694 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
695 pet_scop_free(scop1
);
699 if (scop2
->n_stmt
== 0) {
700 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
701 pet_scop_free(scop2
);
705 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
709 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
710 scop1
->n_array
+ scop2
->n_array
);
713 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
715 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
716 scop
->stmts
[i
] = scop1
->stmts
[i
];
717 scop1
->stmts
[i
] = NULL
;
720 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
721 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
722 scop2
->stmts
[i
] = NULL
;
725 for (i
= 0; i
< scop1
->n_array
; ++i
) {
726 scop
->arrays
[i
] = scop1
->arrays
[i
];
727 scop1
->arrays
[i
] = NULL
;
730 for (i
= 0; i
< scop2
->n_array
; ++i
) {
731 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
732 scop2
->arrays
[i
] = NULL
;
735 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
736 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
737 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
738 scop
= scop_combine_skips(scop
, scop1
, scop2
);
739 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
741 pet_scop_free(scop1
);
742 pet_scop_free(scop2
);
745 pet_scop_free(scop1
);
746 pet_scop_free(scop2
);
751 /* Apply the skip condition "skip" to "scop".
752 * That is, make sure "scop" is not executed when the condition holds.
754 * If "skip" is an affine expression, we add the conditions under
755 * which the expression is zero to the iteration domains.
756 * Otherwise, we add a filter on the variable attaining the value zero.
758 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
759 __isl_take isl_multi_pw_aff
*skip
)
768 is_aff
= multi_pw_aff_is_affine(skip
);
773 return pet_scop_filter(scop
, skip
, 0);
775 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
776 isl_multi_pw_aff_free(skip
);
777 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
778 scop
= pet_scop_restrict(scop
, zero
);
782 isl_multi_pw_aff_free(skip
);
783 return pet_scop_free(scop
);
786 /* Construct a pet_scop that contains the arrays, statements and
787 * skip information in "scop1" and "scop2", where the two scops
788 * are executed "in sequence". That is, breaks and continues
789 * in scop1 have an effect on scop2.
791 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
792 struct pet_scop
*scop2
)
794 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
795 scop2
= restrict_skip(scop2
,
796 pet_scop_get_skip(scop1
, pet_skip_now
));
797 return pet_scop_add(ctx
, scop1
, scop2
);
800 /* Construct a pet_scop that contains the arrays, statements and
801 * skip information in "scop1" and "scop2", where the two scops
802 * are executed "in parallel". That is, any break or continue
803 * in scop1 has no effect on scop2.
805 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
806 struct pet_scop
*scop2
)
808 return pet_scop_add(ctx
, scop1
, scop2
);
811 void *pet_implication_free(struct pet_implication
*implication
)
818 isl_map_free(implication
->extension
);
824 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
827 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
831 pet_loc_free(scop
->loc
);
832 isl_set_free(scop
->context
);
833 isl_set_free(scop
->context_value
);
835 for (i
= 0; i
< scop
->n_type
; ++i
)
836 pet_type_free(scop
->types
[i
]);
839 for (i
= 0; i
< scop
->n_array
; ++i
)
840 pet_array_free(scop
->arrays
[i
]);
843 for (i
= 0; i
< scop
->n_stmt
; ++i
)
844 pet_stmt_free(scop
->stmts
[i
]);
846 if (scop
->implications
)
847 for (i
= 0; i
< scop
->n_implication
; ++i
)
848 pet_implication_free(scop
->implications
[i
]);
849 free(scop
->implications
);
850 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
851 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
856 void pet_type_dump(struct pet_type
*type
)
861 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
864 void pet_implication_dump(struct pet_implication
*implication
)
869 fprintf(stderr
, "%d\n", implication
->satisfied
);
870 isl_map_dump(implication
->extension
);
873 void pet_scop_dump(struct pet_scop
*scop
)
876 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
881 isl_set_dump(scop
->context
);
882 isl_set_dump(scop
->context_value
);
883 for (i
= 0; i
< scop
->n_type
; ++i
)
884 pet_type_dump(scop
->types
[i
]);
885 for (i
= 0; i
< scop
->n_array
; ++i
)
886 pet_array_dump(scop
->arrays
[i
]);
887 for (i
= 0; i
< scop
->n_stmt
; ++i
)
888 pet_stmt_dump(scop
->stmts
[i
]);
889 for (i
= 0; i
< scop
->n_implication
; ++i
)
890 pet_implication_dump(scop
->implications
[i
]);
893 fprintf(stderr
, "skip\n");
894 isl_multi_pw_aff_dump(ext
->skip
[0]);
895 isl_multi_pw_aff_dump(ext
->skip
[1]);
899 /* Return 1 if the two pet_arrays are equivalent.
901 * We don't compare element_size as this may be target dependent.
903 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
905 if (!array1
|| !array2
)
908 if (!isl_set_is_equal(array1
->context
, array2
->context
))
910 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
912 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
914 if (array1
->value_bounds
&&
915 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
917 if (strcmp(array1
->element_type
, array2
->element_type
))
919 if (array1
->element_is_record
!= array2
->element_is_record
)
921 if (array1
->live_out
!= array2
->live_out
)
923 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
925 if (array1
->declared
!= array2
->declared
)
927 if (array1
->exposed
!= array2
->exposed
)
933 /* Return 1 if the two pet_stmts are equivalent.
935 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
939 if (!stmt1
|| !stmt2
)
942 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
944 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
946 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
948 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
950 if (stmt1
->n_arg
!= stmt2
->n_arg
)
952 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
953 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
960 /* Return 1 if the two pet_types are equivalent.
962 * We only compare the names of the types since the exact representation
963 * of the definition may depend on the version of clang being used.
965 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
967 if (!type1
|| !type2
)
970 if (strcmp(type1
->name
, type2
->name
))
976 /* Return 1 if the two pet_implications are equivalent.
978 int pet_implication_is_equal(struct pet_implication
*implication1
,
979 struct pet_implication
*implication2
)
981 if (!implication1
|| !implication2
)
984 if (implication1
->satisfied
!= implication2
->satisfied
)
986 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
992 /* Return 1 if the two pet_scops are equivalent.
994 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
998 if (!scop1
|| !scop2
)
1001 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1003 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1006 if (scop1
->n_type
!= scop2
->n_type
)
1008 for (i
= 0; i
< scop1
->n_type
; ++i
)
1009 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1012 if (scop1
->n_array
!= scop2
->n_array
)
1014 for (i
= 0; i
< scop1
->n_array
; ++i
)
1015 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1018 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1020 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1021 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1024 if (scop1
->n_implication
!= scop2
->n_implication
)
1026 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1027 if (!pet_implication_is_equal(scop1
->implications
[i
],
1028 scop2
->implications
[i
]))
1034 /* Does the set "extent" reference a virtual array, i.e.,
1035 * one with user pointer equal to NULL?
1036 * A virtual array does not have any members.
1038 static int extent_is_virtual_array(__isl_keep isl_set
*extent
)
1043 if (!isl_set_has_tuple_id(extent
))
1045 if (isl_set_is_wrapping(extent
))
1047 id
= isl_set_get_tuple_id(extent
);
1048 is_virtual
= !isl_id_get_user(id
);
1054 /* Intersect the initial dimensions of "array" with "domain", provided
1055 * that "array" represents a virtual array.
1057 * If "array" is virtual, then We take the preimage of "domain"
1058 * over the projection of the extent of "array" onto its initial dimensions
1059 * and intersect this extent with the result.
1061 static struct pet_array
*virtual_array_intersect_domain_prefix(
1062 struct pet_array
*array
, __isl_take isl_set
*domain
)
1068 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1069 isl_set_free(domain
);
1073 space
= isl_set_get_space(array
->extent
);
1074 n
= isl_set_dim(domain
, isl_dim_set
);
1075 ma
= pet_prefix_projection(space
, n
);
1076 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1078 array
->extent
= isl_set_intersect(array
->extent
, domain
);
1080 return pet_array_free(array
);
1085 /* Intersect the initial dimensions of the domain of "stmt"
1088 * We take the preimage of "domain" over the projection of the
1089 * domain of "stmt" onto its initial dimensions and intersect
1090 * the domain of "stmt" with the result.
1092 static struct pet_stmt
*stmt_intersect_domain_prefix(struct pet_stmt
*stmt
,
1093 __isl_take isl_set
*domain
)
1102 space
= isl_set_get_space(stmt
->domain
);
1103 n
= isl_set_dim(domain
, isl_dim_set
);
1104 ma
= pet_prefix_projection(space
, n
);
1105 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1107 stmt
->domain
= isl_set_intersect(stmt
->domain
, domain
);
1109 return pet_stmt_free(stmt
);
1113 isl_set_free(domain
);
1114 return pet_stmt_free(stmt
);
1117 /* Intersect the initial dimensions of the domain of "implication"
1120 * We take the preimage of "domain" over the projection of the
1121 * domain of "implication" onto its initial dimensions and intersect
1122 * the domain of "implication" with the result.
1124 static struct pet_implication
*implication_intersect_domain_prefix(
1125 struct pet_implication
*implication
, __isl_take isl_set
*domain
)
1134 space
= isl_map_get_space(implication
->extension
);
1135 n
= isl_set_dim(domain
, isl_dim_set
);
1136 ma
= pet_prefix_projection(isl_space_domain(space
), n
);
1137 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1139 implication
->extension
=
1140 isl_map_intersect_domain(implication
->extension
, domain
);
1141 if (!implication
->extension
)
1142 return pet_implication_free(implication
);
1146 isl_set_free(domain
);
1147 return pet_implication_free(implication
);
1150 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1152 * The extents of the virtual arrays match the iteration domains,
1153 * so if the iteration domain changes, we need to change those extents too.
1155 struct pet_scop
*pet_scop_intersect_domain_prefix(struct pet_scop
*scop
,
1156 __isl_take isl_set
*domain
)
1163 for (i
= 0; i
< scop
->n_array
; ++i
) {
1164 scop
->arrays
[i
] = virtual_array_intersect_domain_prefix(
1165 scop
->arrays
[i
], isl_set_copy(domain
));
1166 if (!scop
->arrays
[i
])
1170 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1171 scop
->stmts
[i
] = stmt_intersect_domain_prefix(scop
->stmts
[i
],
1172 isl_set_copy(domain
));
1173 if (!scop
->stmts
[i
])
1177 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1178 scop
->implications
[i
] =
1179 implication_intersect_domain_prefix(scop
->implications
[i
],
1180 isl_set_copy(domain
));
1181 if (!scop
->implications
[i
])
1182 return pet_scop_free(scop
);
1185 isl_set_free(domain
);
1188 isl_set_free(domain
);
1189 return pet_scop_free(scop
);
1192 /* Prefix the schedule of "stmt" with an extra dimension with constant
1195 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1200 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1201 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1202 if (!stmt
->schedule
)
1203 return pet_stmt_free(stmt
);
1208 /* Prefix the schedules of all statements in "scop" with an extra
1209 * dimension with constant value "pos".
1211 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1218 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1219 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1220 if (!scop
->stmts
[i
])
1221 return pet_scop_free(scop
);
1227 /* Given a set with a parameter at "param_pos" that refers to the
1228 * iterator, "move" the iterator to the first set dimension.
1229 * That is, essentially equate the parameter to the first set dimension
1230 * and then project it out.
1232 * The first set dimension may however refer to a virtual iterator,
1233 * while the parameter refers to the "real" iterator.
1234 * We therefore need to take into account the affine expression "iv_map", which
1235 * expresses the real iterator in terms of the virtual iterator.
1236 * In particular, we equate the set dimension to the input of the map
1237 * and the parameter to the output of the map and then project out
1238 * everything we don't need anymore.
1240 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1241 int param_pos
, __isl_take isl_aff
*iv_map
)
1243 isl_map
*map
, *map2
;
1244 map
= isl_map_from_domain(set
);
1245 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1246 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1247 map2
= isl_map_from_aff(iv_map
);
1248 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1249 map
= isl_map_apply_range(map
, map2
);
1250 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1251 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1252 return isl_map_domain(map
);
1255 /* Data used in embed_access.
1256 * extend adds an iterator to the iteration domain (through precomposition).
1257 * iv_map expresses the real iterator in terms of the virtual iterator
1258 * var_id represents the induction variable of the corresponding loop
1260 struct pet_embed_access
{
1261 isl_multi_pw_aff
*extend
;
1266 /* Given an index expression, return an expression for the outer iterator.
1268 static __isl_give isl_aff
*index_outer_iterator(
1269 __isl_take isl_multi_pw_aff
*index
)
1272 isl_local_space
*ls
;
1274 space
= isl_multi_pw_aff_get_domain_space(index
);
1275 isl_multi_pw_aff_free(index
);
1277 ls
= isl_local_space_from_space(space
);
1278 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1281 /* Replace an index expression that references the new (outer) iterator variable
1282 * by one that references the corresponding (real) iterator.
1284 * The input index expression is of the form
1286 * { S[i',...] -> i[] }
1288 * where i' refers to the virtual iterator.
1290 * iv_map is of the form
1294 * Return the index expression
1296 * { S[i',...] -> [i] }
1298 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1299 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1304 aff
= index_outer_iterator(index
);
1305 space
= isl_aff_get_space(aff
);
1306 iv_map
= isl_aff_align_params(iv_map
, space
);
1307 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1309 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1312 /* Given an index expression "index" that refers to the (real) iterator
1313 * through the parameter at position "pos", plug in "iv_map", expressing
1314 * the real iterator in terms of the virtual (outer) iterator.
1316 * In particular, the index expression is of the form
1318 * [..., i, ...] -> { S[i',...] -> ... i ... }
1320 * where i refers to the real iterator and i' refers to the virtual iterator.
1322 * iv_map is of the form
1326 * Return the index expression
1328 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1331 * We first move the parameter to the input
1333 * [..., ...] -> { [i, i',...] -> ... i ... }
1337 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1339 * and then combine the two to obtain the desired result.
1341 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1342 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1344 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1347 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1348 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1349 isl_dim_param
, pos
, 1);
1351 space
= isl_space_map_from_set(space
);
1352 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1353 iv_map
= isl_aff_align_params(iv_map
, space
);
1354 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1355 ma
= isl_multi_aff_flat_range_product(
1356 isl_multi_aff_from_aff(iv_map
), ma
);
1357 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1362 /* Does the index expression "index" reference a virtual array, i.e.,
1363 * one with user pointer equal to NULL?
1364 * A virtual array does not have any members.
1366 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1371 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1373 if (isl_multi_pw_aff_range_is_wrapping(index
))
1375 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1376 is_virtual
= !isl_id_get_user(id
);
1382 /* Does the access relation "access" reference a virtual array, i.e.,
1383 * one with user pointer equal to NULL?
1384 * A virtual array does not have any members.
1386 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1391 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1393 if (isl_map_range_is_wrapping(access
))
1395 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1396 is_virtual
= !isl_id_get_user(id
);
1402 /* Embed the given index expression in an extra outer loop.
1403 * The domain of the index expression has already been updated.
1405 * If the access refers to the induction variable, then it is
1406 * turned into an access to the set of integers with index (and value)
1407 * equal to the induction variable.
1409 * If the accessed array is a virtual array (with user
1410 * pointer equal to NULL), as created by create_test_index,
1411 * then it is extended along with the domain of the index expression.
1413 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1414 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1416 isl_id
*array_id
= NULL
;
1419 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1420 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1421 if (array_id
== data
->var_id
) {
1422 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1423 } else if (index_is_virtual_array(index
)) {
1425 isl_multi_pw_aff
*mpa
;
1427 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1428 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1429 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1430 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1431 isl_id_copy(array_id
));
1433 isl_id_free(array_id
);
1435 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1436 isl_dim_param
, data
->var_id
);
1438 index
= index_internalize_iv(index
, pos
,
1439 isl_aff_copy(data
->iv_map
));
1440 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1441 isl_id_copy(data
->var_id
));
1446 /* Embed the given access relation in an extra outer loop.
1447 * The domain of the access relation has already been updated.
1449 * If the access refers to the induction variable, then it is
1450 * turned into an access to the set of integers with index (and value)
1451 * equal to the induction variable.
1453 * If the induction variable appears in the constraints (as a parameter),
1454 * then the parameter is equated to the newly introduced iteration
1455 * domain dimension and subsequently projected out.
1457 * Similarly, if the accessed array is a virtual array (with user
1458 * pointer equal to NULL), as created by create_test_index,
1459 * then it is extended along with the domain of the access.
1461 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1462 struct pet_embed_access
*data
)
1464 isl_id
*array_id
= NULL
;
1467 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1468 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1469 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
1470 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1471 access
= isl_map_equate(access
,
1472 isl_dim_in
, 0, isl_dim_out
, 0);
1473 if (array_id
== data
->var_id
)
1474 access
= isl_map_apply_range(access
,
1475 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1477 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1478 isl_id_copy(array_id
));
1480 isl_id_free(array_id
);
1482 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1484 isl_set
*set
= isl_map_wrap(access
);
1485 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1486 access
= isl_set_unwrap(set
);
1488 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1489 isl_id_copy(data
->var_id
));
1494 /* Given an access expression, embed the associated access relation and
1495 * index expression in an extra outer loop.
1497 * We first update the domains to insert the extra dimension and
1498 * then update the access relation and index expression to take
1499 * into account the mapping "iv_map" from virtual iterator
1502 static __isl_give pet_expr
*embed_access(__isl_take pet_expr
*expr
, void *user
)
1504 struct pet_embed_access
*data
= user
;
1506 expr
= pet_expr_cow(expr
);
1507 expr
= pet_expr_access_update_domain(expr
, data
->extend
);
1511 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
1512 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
1513 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1514 return pet_expr_free(expr
);
1519 /* Embed all access subexpressions of "expr" in an extra loop.
1520 * "extend" inserts an outer loop iterator in the iteration domains
1521 * (through precomposition).
1522 * "iv_map" expresses the real iterator in terms of the virtual iterator
1523 * "var_id" represents the induction variable.
1525 static __isl_give pet_expr
*expr_embed(__isl_take pet_expr
*expr
,
1526 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1527 __isl_keep isl_id
*var_id
)
1529 struct pet_embed_access data
=
1530 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1532 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1533 isl_aff_free(iv_map
);
1534 isl_multi_pw_aff_free(extend
);
1538 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1539 * "dom" and schedule "sched". "var_id" represents the induction variable
1540 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1541 * That is, it expresses the iterator that some of the parameters in "stmt"
1542 * may refer to in terms of the iterator used in "dom" and
1543 * the domain of "sched".
1545 * The iteration domain and schedule of the statement are updated
1546 * according to the iteration domain and schedule of the new loop.
1547 * If stmt->domain is a wrapped map, then the iteration domain
1548 * is the domain of this map, so we need to be careful to adjust
1551 * If the induction variable appears in the constraints (as a parameter)
1552 * of the current iteration domain or the schedule of the statement,
1553 * then the parameter is equated to the newly introduced iteration
1554 * domain dimension and subsequently projected out.
1556 * Finally, all access relations are updated based on the extra loop.
1558 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1559 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1560 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1566 isl_multi_pw_aff
*extend
;
1571 if (isl_set_is_wrapping(stmt
->domain
)) {
1576 map
= isl_set_unwrap(stmt
->domain
);
1577 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1578 ran_dim
= isl_space_range(isl_map_get_space(map
));
1579 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1580 isl_set_universe(ran_dim
));
1581 map
= isl_map_flat_domain_product(ext
, map
);
1582 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1583 isl_id_copy(stmt_id
));
1584 dim
= isl_space_domain(isl_map_get_space(map
));
1585 stmt
->domain
= isl_map_wrap(map
);
1587 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1588 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1590 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1591 isl_id_copy(stmt_id
));
1592 dim
= isl_set_get_space(stmt
->domain
);
1595 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1597 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1598 isl_aff_copy(iv_map
));
1600 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1601 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1602 isl_dim_in
, stmt_id
);
1604 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1606 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1607 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1608 stmt
->schedule
= isl_set_unwrap(set
);
1611 dim
= isl_space_map_from_set(dim
);
1612 extend
= isl_multi_pw_aff_identity(dim
);
1613 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
1614 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
1615 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
1616 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1617 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1618 isl_multi_pw_aff_copy(extend
),
1619 isl_aff_copy(iv_map
), var_id
);
1620 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1623 isl_id_free(var_id
);
1625 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1627 return pet_stmt_free(stmt
);
1628 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1629 return pet_stmt_free(stmt
);
1633 isl_map_free(sched
);
1634 isl_aff_free(iv_map
);
1635 isl_id_free(var_id
);
1639 /* Embed the given pet_array in an extra outer loop with iteration domain
1641 * This embedding only has an effect on virtual arrays (those with
1642 * user pointer equal to NULL), which need to be extended along with
1643 * the iteration domain.
1645 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1646 __isl_take isl_set
*dom
)
1648 isl_id
*array_id
= NULL
;
1652 if (!extent_is_virtual_array(array
->extent
)) {
1657 array_id
= isl_set_get_tuple_id(array
->extent
);
1658 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1659 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1661 return pet_array_free(array
);
1669 /* Update the context with respect to an embedding into a loop
1670 * with iteration domain "dom" and induction variable "id".
1671 * "iv_map" expresses the real iterator (parameter "id") in terms
1672 * of a possibly virtual iterator (used in "dom").
1674 * If the current context is independent of "id", we don't need
1676 * Otherwise, a parameter value is invalid for the embedding if
1677 * any of the corresponding iterator values is invalid.
1678 * That is, a parameter value is valid only if all the corresponding
1679 * iterator values are valid.
1680 * We therefore compute the set of parameters
1682 * forall i in dom : valid (i)
1686 * not exists i in dom : not valid(i)
1690 * not exists i in dom \ valid(i)
1692 * Before we subtract valid(i) from dom, we first need to substitute
1693 * the real iterator for the virtual iterator.
1695 * If there are any unnamed parameters in "dom", then we consider
1696 * a parameter value to be valid if it is valid for any value of those
1697 * unnamed parameters. They are therefore projected out at the end.
1699 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1700 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
1701 __isl_keep isl_id
*id
)
1706 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1710 context
= isl_set_from_params(context
);
1711 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1712 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1713 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1714 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
1715 context
= isl_set_preimage_multi_aff(context
, ma
);
1716 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1717 context
= isl_set_params(context
);
1718 context
= isl_set_complement(context
);
1719 context
= pet_nested_remove_from_set(context
);
1723 /* Update the implication with respect to an embedding into a loop
1724 * with iteration domain "dom".
1726 * Since embed_access extends virtual arrays along with the domain
1727 * of the access, we need to do the same with domain and range
1728 * of the implication. Since the original implication is only valid
1729 * within a given iteration of the loop, the extended implication
1730 * maps the extra array dimension corresponding to the extra loop
1733 static struct pet_implication
*pet_implication_embed(
1734 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1742 map
= isl_set_identity(dom
);
1743 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1744 map
= isl_map_flat_product(map
, implication
->extension
);
1745 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1746 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1747 implication
->extension
= map
;
1748 if (!implication
->extension
)
1749 return pet_implication_free(implication
);
1757 /* Embed all statements and arrays in "scop" in an extra outer loop
1758 * with iteration domain "dom" and schedule "sched".
1759 * "id" represents the induction variable of the loop.
1760 * "iv_map" maps a possibly virtual iterator to the real iterator.
1761 * That is, it expresses the iterator that some of the parameters in "scop"
1762 * may refer to in terms of the iterator used in "dom" and
1763 * the domain of "sched".
1765 * Any skip conditions within the loop have no effect outside of the loop.
1766 * The caller is responsible for making sure skip[pet_skip_later] has been
1767 * taken into account.
1769 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1770 __isl_take isl_aff
*sched
, __isl_take isl_aff
*iv_map
,
1771 __isl_take isl_id
*id
)
1776 sched_map
= isl_map_from_aff(sched
);
1781 pet_scop_reset_skip(scop
, pet_skip_now
);
1782 pet_scop_reset_skip(scop
, pet_skip_later
);
1784 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1788 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1789 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1790 isl_set_copy(dom
), isl_map_copy(sched_map
),
1791 isl_aff_copy(iv_map
), isl_id_copy(id
));
1792 if (!scop
->stmts
[i
])
1796 for (i
= 0; i
< scop
->n_array
; ++i
) {
1797 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1799 if (!scop
->arrays
[i
])
1803 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1804 scop
->implications
[i
] =
1805 pet_implication_embed(scop
->implications
[i
],
1807 if (!scop
->implications
[i
])
1812 isl_map_free(sched_map
);
1813 isl_aff_free(iv_map
);
1818 isl_map_free(sched_map
);
1819 isl_aff_free(iv_map
);
1821 return pet_scop_free(scop
);
1824 /* Add extra conditions on the parameters to the iteration domain of "stmt".
1826 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1827 __isl_take isl_set
*cond
)
1832 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1837 return pet_stmt_free(stmt
);
1840 /* Add extra conditions to scop->skip[type].
1842 * The new skip condition only holds if it held before
1843 * and the condition is true. It does not hold if it did not hold
1844 * before or the condition is false.
1846 * The skip condition is assumed to be an affine expression.
1848 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1849 enum pet_skip type
, __isl_keep isl_set
*cond
)
1851 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1857 if (!ext
->skip
[type
])
1860 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1861 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1862 isl_error_internal
, "can only restrict affine skips",
1863 return pet_scop_free(scop
));
1865 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1866 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1867 cond
= isl_set_copy(cond
);
1868 cond
= isl_set_from_params(cond
);
1869 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1870 skip
= indicator_function(cond
, dom
);
1871 isl_multi_pw_aff_free(ext
->skip
[type
]);
1872 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1873 if (!ext
->skip
[type
])
1874 return pet_scop_free(scop
);
1879 /* Add extra conditions on the parameters to all iteration domains
1880 * and skip conditions.
1882 * A parameter value is valid for the result if it was valid
1883 * for the original scop and satisfies "cond" or if it does
1884 * not satisfy "cond" as in this case the scop is not executed
1885 * and the original constraints on the parameters are irrelevant.
1887 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1888 __isl_take isl_set
*cond
)
1892 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1893 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1898 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1899 scop
->context
= isl_set_union(scop
->context
,
1900 isl_set_complement(isl_set_copy(cond
)));
1901 scop
->context
= isl_set_coalesce(scop
->context
);
1902 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1906 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1907 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1908 isl_set_copy(cond
));
1909 if (!scop
->stmts
[i
])
1917 return pet_scop_free(scop
);
1920 /* Insert an argument expression corresponding to "test" in front
1921 * of the list of arguments described by *n_arg and *args.
1923 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1924 __isl_keep isl_multi_pw_aff
*test
)
1927 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1933 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1938 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
1941 for (i
= 0; i
< *n_arg
; ++i
)
1942 ext
[1 + i
] = (*args
)[i
];
1947 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1954 /* Look through the applications in "scop" for any that can be
1955 * applied to the filter expressed by "map" and "satisified".
1956 * If there is any, then apply it to "map" and return the result.
1957 * Otherwise, return "map".
1958 * "id" is the identifier of the virtual array.
1960 * We only introduce at most one implication for any given virtual array,
1961 * so we can apply the implication and return as soon as we find one.
1963 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1964 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1968 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1969 struct pet_implication
*pi
= scop
->implications
[i
];
1972 if (pi
->satisfied
!= satisfied
)
1974 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1979 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1985 /* Is the filter expressed by "test" and "satisfied" implied
1986 * by filter "pos" on "domain", with filter "expr", taking into
1987 * account the implications of "scop"?
1989 * For filter on domain implying that expressed by "test" and "satisfied",
1990 * the filter needs to be an access to the same (virtual) array as "test" and
1991 * the filter value needs to be equal to "satisfied".
1992 * Moreover, the filter access relation, possibly extended by
1993 * the implications in "scop" needs to contain "test".
1995 static int implies_filter(struct pet_scop
*scop
,
1996 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
1997 __isl_keep isl_map
*test
, int satisfied
)
1999 isl_id
*test_id
, *arg_id
;
2006 if (expr
->type
!= pet_expr_access
)
2008 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2009 arg_id
= pet_expr_access_get_id(expr
);
2010 isl_id_free(arg_id
);
2011 isl_id_free(test_id
);
2012 if (test_id
!= arg_id
)
2014 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2015 is_int
= isl_val_is_int(val
);
2017 s
= isl_val_get_num_si(val
);
2026 implied
= isl_map_copy(expr
->acc
.access
);
2027 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2028 is_subset
= isl_map_is_subset(test
, implied
);
2029 isl_map_free(implied
);
2034 /* Is the filter expressed by "test" and "satisfied" implied
2035 * by any of the filters on the domain of "stmt", taking into
2036 * account the implications of "scop"?
2038 static int filter_implied(struct pet_scop
*scop
,
2039 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2047 if (!scop
|| !stmt
|| !test
)
2049 if (scop
->n_implication
== 0)
2051 if (stmt
->n_arg
== 0)
2054 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2055 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2058 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2059 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2060 test_map
, satisfied
);
2061 if (implied
< 0 || implied
)
2065 isl_map_free(test_map
);
2066 isl_map_free(domain
);
2070 /* Make the statement "stmt" depend on the value of "test"
2071 * being equal to "satisfied" by adjusting stmt->domain.
2073 * The domain of "test" corresponds to the (zero or more) outer dimensions
2074 * of the iteration domain.
2076 * We first extend "test" to apply to the entire iteration domain and
2077 * then check if the filter that we are about to add is implied
2078 * by any of the current filters, possibly taking into account
2079 * the implications in "scop". If so, we leave "stmt" untouched and return.
2081 * Otherwise, we insert an argument corresponding to a read to "test"
2082 * from the iteration domain of "stmt" in front of the list of arguments.
2083 * We also insert a corresponding output dimension in the wrapped
2084 * map contained in stmt->domain, with value set to "satisfied".
2086 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2087 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2093 isl_pw_multi_aff
*pma
;
2094 isl_multi_aff
*add_dom
;
2096 isl_local_space
*ls
;
2102 space
= pet_stmt_get_space(stmt
);
2103 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2104 space
= isl_space_from_domain(space
);
2105 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2106 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2107 ls
= isl_local_space_from_space(isl_space_domain(space
));
2108 for (i
= 0; i
< n_test_dom
; ++i
) {
2110 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2112 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2114 isl_local_space_free(ls
);
2115 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2117 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2121 isl_multi_pw_aff_free(test
);
2125 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2126 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
2128 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2130 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2133 isl_multi_pw_aff_free(test
);
2136 isl_multi_pw_aff_free(test
);
2137 return pet_stmt_free(stmt
);
2140 /* Does "scop" have a skip condition of the given "type"?
2142 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2144 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2148 return ext
->skip
[type
] != NULL
;
2151 /* Does "scop" have a skip condition of the given "type" that
2152 * is an affine expression?
2154 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2156 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2160 if (!ext
->skip
[type
])
2162 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2165 /* Does "scop" have a skip condition of the given "type" that
2166 * is not an affine expression?
2168 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2170 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2175 if (!ext
->skip
[type
])
2177 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2183 /* Does "scop" have a skip condition of the given "type" that
2184 * is affine and holds on the entire domain?
2186 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2188 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2194 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2195 if (is_aff
< 0 || !is_aff
)
2198 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2199 set
= isl_pw_aff_non_zero_set(pa
);
2200 is_univ
= isl_set_plain_is_universe(set
);
2206 /* Replace scop->skip[type] by "skip".
2208 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2209 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2211 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2216 isl_multi_pw_aff_free(ext
->skip
[type
]);
2217 ext
->skip
[type
] = skip
;
2221 isl_multi_pw_aff_free(skip
);
2222 return pet_scop_free(scop
);
2225 /* Return a copy of scop->skip[type].
2227 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2230 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2235 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2238 /* Assuming scop->skip[type] is an affine expression,
2239 * return the constraints on the parameters for which the skip condition
2242 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2245 isl_multi_pw_aff
*skip
;
2248 skip
= pet_scop_get_skip(scop
, type
);
2249 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2250 isl_multi_pw_aff_free(skip
);
2251 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2254 /* Return the identifier of the variable that is accessed by
2255 * the skip condition of the given type.
2257 * The skip condition is assumed not to be an affine condition.
2259 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2262 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2267 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2270 /* Return an access pet_expr corresponding to the skip condition
2271 * of the given type.
2273 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2276 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2279 /* Drop the the skip condition scop->skip[type].
2281 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2283 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2288 isl_multi_pw_aff_free(ext
->skip
[type
]);
2289 ext
->skip
[type
] = NULL
;
2292 /* Make the skip condition (if any) depend on the value of "test" being
2293 * equal to "satisfied".
2295 * We only support the case where the original skip condition is universal,
2296 * i.e., where skipping is unconditional, and where satisfied == 1.
2297 * In this case, the skip condition is changed to skip only when
2298 * "test" is equal to one.
2300 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2301 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2307 if (!pet_scop_has_skip(scop
, type
))
2311 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2313 return pet_scop_free(scop
);
2314 if (satisfied
&& is_univ
) {
2315 isl_multi_pw_aff
*skip
;
2316 skip
= isl_multi_pw_aff_copy(test
);
2317 scop
= pet_scop_set_skip(scop
, type
, skip
);
2321 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2322 "skip expression cannot be filtered",
2323 return pet_scop_free(scop
));
2329 /* Make all statements in "scop" depend on the value of "test"
2330 * being equal to "satisfied" by adjusting their domains.
2332 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2333 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2337 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2338 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2343 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2344 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2345 isl_multi_pw_aff_copy(test
), satisfied
);
2346 if (!scop
->stmts
[i
])
2350 isl_multi_pw_aff_free(test
);
2353 isl_multi_pw_aff_free(test
);
2354 return pet_scop_free(scop
);
2357 /* Add all parameters in "expr" to "space" and return the result.
2359 static __isl_give isl_space
*expr_collect_params(__isl_keep pet_expr
*expr
,
2360 __isl_take isl_space
*space
)
2366 for (i
= 0; i
< expr
->n_arg
; ++i
)
2367 space
= expr_collect_params(expr
->args
[i
], space
);
2369 if (expr
->type
== pet_expr_access
)
2370 space
= isl_space_align_params(space
,
2371 isl_map_get_space(expr
->acc
.access
));
2375 pet_expr_free(expr
);
2376 return isl_space_free(space
);
2379 /* Add all parameters in "stmt" to "space" and return the result.
2381 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2382 __isl_take isl_space
*space
)
2387 return isl_space_free(space
);
2389 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2390 space
= isl_space_align_params(space
,
2391 isl_map_get_space(stmt
->schedule
));
2392 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2393 space
= expr_collect_params(stmt
->args
[i
], space
);
2394 space
= expr_collect_params(stmt
->body
, space
);
2399 /* Add all parameters in "array" to "space" and return the result.
2401 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2402 __isl_take isl_space
*space
)
2405 return isl_space_free(space
);
2407 space
= isl_space_align_params(space
,
2408 isl_set_get_space(array
->context
));
2409 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2414 /* Add all parameters in "scop" to "space" and return the result.
2416 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2417 __isl_take isl_space
*space
)
2422 return isl_space_free(space
);
2424 for (i
= 0; i
< scop
->n_array
; ++i
)
2425 space
= array_collect_params(scop
->arrays
[i
], space
);
2427 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2428 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2433 /* Add all parameters in "space" to the domain, schedule and
2434 * all access relations in "stmt".
2436 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2437 __isl_take isl_space
*space
)
2444 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2445 isl_space_copy(space
));
2446 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2447 isl_space_copy(space
));
2449 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2450 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2451 isl_space_copy(space
));
2455 stmt
->body
= pet_expr_align_params(stmt
->body
, isl_space_copy(space
));
2457 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2460 isl_space_free(space
);
2463 isl_space_free(space
);
2464 return pet_stmt_free(stmt
);
2467 /* Add all parameters in "space" to "array".
2469 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2470 __isl_take isl_space
*space
)
2475 array
->context
= isl_set_align_params(array
->context
,
2476 isl_space_copy(space
));
2477 array
->extent
= isl_set_align_params(array
->extent
,
2478 isl_space_copy(space
));
2479 if (array
->value_bounds
) {
2480 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2481 isl_space_copy(space
));
2482 if (!array
->value_bounds
)
2486 if (!array
->context
|| !array
->extent
)
2489 isl_space_free(space
);
2492 isl_space_free(space
);
2493 return pet_array_free(array
);
2496 /* Add all parameters in "space" to "scop".
2498 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2499 __isl_take isl_space
*space
)
2506 for (i
= 0; i
< scop
->n_array
; ++i
) {
2507 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2508 isl_space_copy(space
));
2509 if (!scop
->arrays
[i
])
2513 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2514 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2515 isl_space_copy(space
));
2516 if (!scop
->stmts
[i
])
2520 isl_space_free(space
);
2523 isl_space_free(space
);
2524 return pet_scop_free(scop
);
2527 /* Update all isl_sets and isl_maps in "scop" such that they all
2528 * have the same parameters.
2530 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2537 space
= isl_set_get_space(scop
->context
);
2538 space
= scop_collect_params(scop
, space
);
2540 scop
->context
= isl_set_align_params(scop
->context
,
2541 isl_space_copy(space
));
2542 scop
= scop_propagate_params(scop
, space
);
2544 if (scop
&& !scop
->context
)
2545 return pet_scop_free(scop
);
2550 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2551 * in "space" by a value equal to the corresponding parameter.
2553 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2554 __isl_take isl_space
*space
)
2559 stmt
->body
= pet_expr_detect_parameter_accesses(stmt
->body
,
2560 isl_space_copy(space
));
2562 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2565 isl_space_free(space
);
2568 isl_space_free(space
);
2569 return pet_stmt_free(stmt
);
2572 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2573 * in "space" by a value equal to the corresponding parameter.
2575 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2576 __isl_take isl_space
*space
)
2583 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2584 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2585 isl_space_copy(space
));
2586 if (!scop
->stmts
[i
])
2590 isl_space_free(space
);
2593 isl_space_free(space
);
2594 return pet_scop_free(scop
);
2597 /* Replace all accesses to (0D) arrays that correspond to any of
2598 * the parameters used in "scop" by a value equal
2599 * to the corresponding parameter.
2601 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2608 space
= isl_set_get_space(scop
->context
);
2609 space
= scop_collect_params(scop
, space
);
2611 scop
= scop_detect_parameter_accesses(scop
, space
);
2616 /* Add the access relation of the access expression "expr" to "accesses" and
2617 * return the result.
2618 * The domain of the access relation is intersected with "domain".
2619 * If "tag" is set, then the access relation is tagged with
2620 * the corresponding reference identifier.
2622 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2623 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2627 access
= pet_expr_access_get_may_access(expr
);
2628 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
2630 access
= pet_expr_tag_access(expr
, access
);
2631 return isl_union_map_add_map(accesses
, access
);
2634 /* Add all read access relations (if "read" is set) and/or all write
2635 * access relations (if "write" is set) to "accesses" and return the result.
2636 * The domains of the access relations are intersected with "domain".
2637 * If "tag" is set, then the access relations are tagged with
2638 * the corresponding reference identifiers.
2640 * If "must" is set, then we only add the accesses that are definitely
2641 * performed. Otherwise, we add all potential accesses.
2642 * In particular, if the access has any arguments, then if "must" is
2643 * set we currently skip the access completely. If "must" is not set,
2644 * we project out the values of the access arguments.
2646 static __isl_give isl_union_map
*expr_collect_accesses(
2647 __isl_keep pet_expr
*expr
, int read
, int write
, int must
, int tag
,
2648 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2655 return isl_union_map_free(accesses
);
2657 for (i
= 0; i
< expr
->n_arg
; ++i
)
2658 accesses
= expr_collect_accesses(expr
->args
[i
],
2659 read
, write
, must
, tag
, accesses
, domain
);
2661 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2662 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
2663 (!must
|| expr
->n_arg
== 0)) {
2664 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
2670 /* Collect and return all read access relations (if "read" is set)
2671 * and/or all write access relations (if "write" is set) in "stmt".
2672 * If "tag" is set, then the access relations are tagged with
2673 * the corresponding reference identifiers.
2674 * If "kill" is set, then "stmt" is a kill statement and we simply
2675 * add the argument of the kill operation.
2677 * If "must" is set, then we only add the accesses that are definitely
2678 * performed. Otherwise, we add all potential accesses.
2679 * In particular, if the statement has any arguments, then if "must" is
2680 * set we currently skip the statement completely. If "must" is not set,
2681 * we project out the values of the statement arguments.
2683 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2684 int read
, int write
, int kill
, int must
, int tag
,
2685 __isl_take isl_space
*dim
)
2687 isl_union_map
*accesses
;
2693 accesses
= isl_union_map_empty(dim
);
2695 if (must
&& stmt
->n_arg
> 0)
2698 domain
= isl_set_copy(stmt
->domain
);
2699 if (isl_set_is_wrapping(domain
))
2700 domain
= isl_map_domain(isl_set_unwrap(domain
));
2703 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
2706 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
2707 must
, tag
, accesses
, domain
);
2708 isl_set_free(domain
);
2713 /* Is "stmt" an assignment statement?
2715 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2719 if (stmt
->body
->type
!= pet_expr_op
)
2721 return stmt
->body
->op
== pet_op_assign
;
2724 /* Is "stmt" a kill statement?
2726 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2730 if (stmt
->body
->type
!= pet_expr_op
)
2732 return stmt
->body
->op
== pet_op_kill
;
2735 /* Is "stmt" an assume statement?
2737 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2741 return pet_expr_is_assume(stmt
->body
);
2744 /* Compute a mapping from all arrays (of structs) in scop
2745 * to their innermost arrays.
2747 * In particular, for each array of a primitive type, the result
2748 * contains the identity mapping on that array.
2749 * For each array involving member accesses, the result
2750 * contains a mapping from the elements of any intermediate array of structs
2751 * to all corresponding elements of the innermost nested arrays.
2753 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
2756 isl_union_map
*to_inner
;
2758 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2760 for (i
= 0; i
< scop
->n_array
; ++i
) {
2761 struct pet_array
*array
= scop
->arrays
[i
];
2763 isl_map
*map
, *gist
;
2765 if (array
->element_is_record
)
2768 map
= isl_set_identity(isl_set_copy(array
->extent
));
2770 set
= isl_map_domain(isl_map_copy(map
));
2771 gist
= isl_map_copy(map
);
2772 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2773 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2775 while (set
&& isl_set_is_wrapping(set
)) {
2779 id
= isl_set_get_tuple_id(set
);
2780 wrapped
= isl_set_unwrap(set
);
2781 wrapped
= isl_map_domain_map(wrapped
);
2782 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2783 map
= isl_map_apply_domain(map
, wrapped
);
2784 set
= isl_map_domain(isl_map_copy(map
));
2785 gist
= isl_map_copy(map
);
2786 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2787 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2797 /* Collect and return all read access relations (if "read" is set)
2798 * and/or all write access relations (if "write" is set) in "scop".
2799 * If "kill" is set, then we only add the arguments of kill operations.
2800 * If "must" is set, then we only add the accesses that are definitely
2801 * performed. Otherwise, we add all potential accesses.
2802 * If "tag" is set, then the access relations are tagged with
2803 * the corresponding reference identifiers.
2804 * For accesses to structures, the returned access relation accesses
2805 * all individual fields in the structures.
2807 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2808 int read
, int write
, int kill
, int must
, int tag
)
2811 isl_union_map
*accesses
;
2812 isl_union_set
*arrays
;
2813 isl_union_map
*to_inner
;
2818 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2820 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2821 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2822 isl_union_map
*accesses_i
;
2825 if (kill
&& !pet_stmt_is_kill(stmt
))
2828 space
= isl_set_get_space(scop
->context
);
2829 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
2831 accesses
= isl_union_map_union(accesses
, accesses_i
);
2834 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2835 for (i
= 0; i
< scop
->n_array
; ++i
) {
2836 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2837 arrays
= isl_union_set_add_set(arrays
, extent
);
2839 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2841 to_inner
= compute_to_inner(scop
);
2842 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2847 /* Collect all potential read access relations.
2849 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2851 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
2854 /* Collect all potential write access relations.
2856 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2858 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
2861 /* Collect all definite write access relations.
2863 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2865 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
2868 /* Collect all definite kill access relations.
2870 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2872 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
2875 /* Collect all tagged potential read access relations.
2877 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2878 struct pet_scop
*scop
)
2880 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
2883 /* Collect all tagged potential write access relations.
2885 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2886 struct pet_scop
*scop
)
2888 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
2891 /* Collect all tagged definite write access relations.
2893 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2894 struct pet_scop
*scop
)
2896 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
2899 /* Collect all tagged definite kill access relations.
2901 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2902 struct pet_scop
*scop
)
2904 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
2907 /* Collect and return the union of iteration domains in "scop".
2909 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2913 isl_union_set
*domain
;
2918 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2920 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2921 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2922 domain
= isl_union_set_add_set(domain
, domain_i
);
2928 /* Collect and return the schedules of the statements in "scop".
2929 * The range is normalized to the maximal number of scheduling
2932 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2935 isl_map
*schedule_i
;
2936 isl_union_map
*schedule
;
2937 int depth
, max_depth
= 0;
2942 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2944 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2945 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2946 if (depth
> max_depth
)
2950 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2951 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2952 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2953 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2955 for (j
= depth
; j
< max_depth
; ++j
)
2956 schedule_i
= isl_map_fix_si(schedule_i
,
2958 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2964 /* Add a reference identifier to all access expressions in "stmt".
2965 * "n_ref" points to an integer that contains the sequence number
2966 * of the next reference.
2968 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2975 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2976 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2978 return pet_stmt_free(stmt
);
2981 stmt
->body
= pet_expr_add_ref_ids(stmt
->body
, n_ref
);
2983 return pet_stmt_free(stmt
);
2988 /* Add a reference identifier to all access expressions in "scop".
2990 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2999 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3000 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
3001 if (!scop
->stmts
[i
])
3002 return pet_scop_free(scop
);
3008 /* Reset the user pointer on all parameter ids in "array".
3010 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3015 array
->context
= isl_set_reset_user(array
->context
);
3016 array
->extent
= isl_set_reset_user(array
->extent
);
3017 if (!array
->context
|| !array
->extent
)
3018 return pet_array_free(array
);
3023 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3025 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3034 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
3035 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
3036 if (!stmt
->domain
|| !stmt
->schedule
)
3037 return pet_stmt_free(stmt
);
3039 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3040 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
3042 return pet_stmt_free(stmt
);
3045 stmt
->body
= pet_expr_anonymize(stmt
->body
);
3047 return pet_stmt_free(stmt
);
3052 /* Reset the user pointer on the tuple ids and all parameter ids
3055 static struct pet_implication
*implication_anonymize(
3056 struct pet_implication
*implication
)
3061 implication
->extension
= isl_map_reset_user(implication
->extension
);
3062 if (!implication
->extension
)
3063 return pet_implication_free(implication
);
3068 /* Reset the user pointer on all parameter and tuple ids in "scop".
3070 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3077 scop
->context
= isl_set_reset_user(scop
->context
);
3078 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
3079 if (!scop
->context
|| !scop
->context_value
)
3080 return pet_scop_free(scop
);
3082 for (i
= 0; i
< scop
->n_array
; ++i
) {
3083 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3084 if (!scop
->arrays
[i
])
3085 return pet_scop_free(scop
);
3088 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3089 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3090 if (!scop
->stmts
[i
])
3091 return pet_scop_free(scop
);
3094 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3095 scop
->implications
[i
] =
3096 implication_anonymize(scop
->implications
[i
]);
3097 if (!scop
->implications
[i
])
3098 return pet_scop_free(scop
);
3104 /* Compute the gist of the iteration domain and all access relations
3105 * of "stmt" based on the constraints on the parameters specified by "context"
3106 * and the constraints on the values of nested accesses specified
3107 * by "value_bounds".
3109 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3110 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3118 domain
= isl_set_copy(stmt
->domain
);
3119 if (stmt
->n_arg
> 0)
3120 domain
= isl_map_domain(isl_set_unwrap(domain
));
3122 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3124 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3125 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
3126 domain
, value_bounds
);
3131 stmt
->body
= pet_expr_gist(stmt
->body
, domain
, value_bounds
);
3135 isl_set_free(domain
);
3137 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
3138 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3139 if (stmt
->n_arg
> 0)
3140 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
3142 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3144 return pet_stmt_free(stmt
);
3148 isl_set_free(domain
);
3149 return pet_stmt_free(stmt
);
3152 /* Compute the gist of the extent of the array
3153 * based on the constraints on the parameters specified by "context".
3155 static struct pet_array
*array_gist(struct pet_array
*array
,
3156 __isl_keep isl_set
*context
)
3161 array
->extent
= isl_set_gist_params(array
->extent
,
3162 isl_set_copy(context
));
3164 return pet_array_free(array
);
3169 /* Compute the gist of all sets and relations in "scop"
3170 * based on the constraints on the parameters specified by "scop->context"
3171 * and the constraints on the values of nested accesses specified
3172 * by "value_bounds".
3174 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3175 __isl_keep isl_union_map
*value_bounds
)
3182 scop
->context
= isl_set_coalesce(scop
->context
);
3184 return pet_scop_free(scop
);
3186 for (i
= 0; i
< scop
->n_array
; ++i
) {
3187 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3188 if (!scop
->arrays
[i
])
3189 return pet_scop_free(scop
);
3192 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3193 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3195 if (!scop
->stmts
[i
])
3196 return pet_scop_free(scop
);
3202 /* Intersect the context of "scop" with "context".
3203 * To ensure that we don't introduce any unnamed parameters in
3204 * the context of "scop", we first remove the unnamed parameters
3207 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3208 __isl_take isl_set
*context
)
3213 context
= pet_nested_remove_from_set(context
);
3214 scop
->context
= isl_set_intersect(scop
->context
, context
);
3216 return pet_scop_free(scop
);
3220 isl_set_free(context
);
3221 return pet_scop_free(scop
);
3224 /* Drop the current context of "scop". That is, replace the context
3225 * by a universal set.
3227 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3234 space
= isl_set_get_space(scop
->context
);
3235 isl_set_free(scop
->context
);
3236 scop
->context
= isl_set_universe(space
);
3238 return pet_scop_free(scop
);
3243 /* Append "array" to the arrays of "scop".
3245 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3246 struct pet_array
*array
)
3249 struct pet_array
**arrays
;
3251 if (!array
|| !scop
)
3254 ctx
= isl_set_get_ctx(scop
->context
);
3255 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3259 scop
->arrays
= arrays
;
3260 scop
->arrays
[scop
->n_array
] = array
;
3265 pet_array_free(array
);
3266 return pet_scop_free(scop
);
3269 /* Create an index expression for an access to a virtual array
3270 * representing the result of a condition.
3271 * Unlike other accessed data, the id of the array is NULL as
3272 * there is no ValueDecl in the program corresponding to the virtual
3274 * The index expression is created as an identity mapping on "space".
3275 * That is, the dimension of the array is the same as that of "space".
3276 * Currently, the array starts out as a scalar, but grows along with the
3277 * statement writing to the array in pet_scop_embed.
3279 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
3285 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
3286 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
3287 space
= isl_space_map_from_set(space
);
3288 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3289 return isl_multi_pw_aff_identity(space
);
3292 /* Add an array with the given extent (range of "index") to the list
3293 * of arrays in "scop" and return the extended pet_scop.
3294 * "int_size" is the number of bytes needed to represent values of type "int".
3295 * The array is marked as attaining values 0 and 1 only and
3296 * as each element being assigned at most once.
3298 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
3299 __isl_take isl_multi_pw_aff
*index
, int int_size
)
3303 struct pet_array
*array
;
3306 if (!scop
|| !index
)
3309 ctx
= isl_multi_pw_aff_get_ctx(index
);
3310 array
= isl_calloc_type(ctx
, struct pet_array
);
3314 access
= isl_map_from_multi_pw_aff(index
);
3315 array
->extent
= isl_map_range(access
);
3316 space
= isl_space_params_alloc(ctx
, 0);
3317 array
->context
= isl_set_universe(space
);
3318 space
= isl_space_set_alloc(ctx
, 0, 1);
3319 array
->value_bounds
= isl_set_universe(space
);
3320 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
3322 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
3324 array
->element_type
= strdup("int");
3325 array
->element_size
= int_size
;
3326 array
->uniquely_defined
= 1;
3328 if (!array
->extent
|| !array
->context
)
3329 array
= pet_array_free(array
);
3331 scop
= pet_scop_add_array(scop
, array
);
3335 isl_multi_pw_aff_free(index
);
3336 return pet_scop_free(scop
);
3339 /* Create and return an implication on filter values equal to "satisfied"
3340 * with extension "map".
3342 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3346 struct pet_implication
*implication
;
3350 ctx
= isl_map_get_ctx(map
);
3351 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3355 implication
->extension
= map
;
3356 implication
->satisfied
= satisfied
;
3364 /* Add an implication on filter values equal to "satisfied"
3365 * with extension "map" to "scop".
3367 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3368 __isl_take isl_map
*map
, int satisfied
)
3371 struct pet_implication
*implication
;
3372 struct pet_implication
**implications
;
3374 implication
= new_implication(map
, satisfied
);
3375 if (!scop
|| !implication
)
3378 ctx
= isl_set_get_ctx(scop
->context
);
3379 implications
= isl_realloc_array(ctx
, scop
->implications
,
3380 struct pet_implication
*,
3381 scop
->n_implication
+ 1);
3384 scop
->implications
= implications
;
3385 scop
->implications
[scop
->n_implication
] = implication
;
3386 scop
->n_implication
++;
3390 pet_implication_free(implication
);
3391 return pet_scop_free(scop
);
3394 /* Given an access expression, check if it is data dependent.
3395 * If so, set *found and abort the search.
3397 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
3401 if (pet_expr_get_n_arg(expr
) > 0) {
3409 /* Does "scop" contain any data dependent accesses?
3411 * Check the body of each statement for such accesses.
3413 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3421 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3422 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
3423 &is_data_dependent
, &found
);
3424 if (r
< 0 && !found
)
3433 /* Does "scop" contain and data dependent conditions?
3435 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3442 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3443 if (scop
->stmts
[i
]->n_arg
> 0)
3449 /* Keep track of the "input" file inside the (extended) "scop".
3451 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3453 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3463 /* Print the original code corresponding to "scop" to printer "p".
3465 * pet_scop_print_original can only be called from
3466 * a pet_transform_C_source callback. This means that the input
3467 * file is stored in the extended scop and that the printer prints
3470 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3471 __isl_take isl_printer
*p
)
3473 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3475 unsigned start
, end
;
3478 return isl_printer_free(p
);
3481 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3482 "no input file stored in scop",
3483 return isl_printer_free(p
));
3485 output
= isl_printer_get_file(p
);
3487 return isl_printer_free(p
);
3489 start
= pet_loc_get_start(scop
->loc
);
3490 end
= pet_loc_get_end(scop
->loc
);
3491 if (copy(ext
->input
, output
, start
, end
) < 0)
3492 return isl_printer_free(p
);