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 the outer loop iterators. 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 domain).
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 in the given space and with room for n statements.
267 * The context is initialized as a universe set in "space".
269 * Since no information on the location is known at this point,
270 * scop->loc is initialized with pet_loc_dummy.
272 static struct pet_scop
*scop_alloc(__isl_take isl_space
*space
, int n
)
275 struct pet_scop
*scop
;
280 ctx
= isl_space_get_ctx(space
);
281 scop
= pet_scop_alloc(ctx
);
285 scop
->context
= isl_set_universe(isl_space_copy(space
));
286 scop
->context_value
= isl_set_universe(isl_space_params(space
));
287 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
288 if (!scop
->context
|| !scop
->stmts
)
289 return pet_scop_free(scop
);
291 scop
->loc
= &pet_loc_dummy
;
297 /* Construct a pet_scop in the given space containing 0 statements.
299 struct pet_scop
*pet_scop_empty(__isl_take isl_space
*space
)
301 return scop_alloc(space
, 0);
304 /* Return the constraints on the iteration domain in the access relation
306 * If the corresponding access expression has arguments then the domain
307 * of "access" is a wrapped relation with the iteration domain in the domain
308 * and the arguments in the range.
310 static __isl_give isl_set
*access_domain(__isl_take isl_map
*access
)
314 domain
= isl_map_domain(access
);
315 if (isl_set_is_wrapping(domain
))
316 domain
= isl_map_domain(isl_set_unwrap(domain
));
321 /* Update "context" with the constraints imposed on the outer iteration
322 * domain by "access".
323 * "context" lives in an anonymous space, while the domain of "access"
324 * refers to a particular statement. This reference therefore needs to be
327 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
328 __isl_take isl_set
*context
)
332 domain
= access_domain(isl_map_copy(access
));
333 domain
= isl_set_reset_tuple_id(domain
);
334 context
= isl_set_intersect(context
, domain
);
338 /* Update "context" with the constraints imposed on the outer iteration
341 * "context" lives in an anonymous space, while the domains of
342 * the access relations in "expr" refer to a particular statement.
343 * This reference therefore needs to be stripped off.
345 * If "expr" represents a conditional operator, then a parameter or outer
346 * iterator value needs to be valid for the condition and
347 * for at least one of the remaining two arguments.
348 * If the condition is an affine expression, then we can be a bit more specific.
349 * The value then has to be valid for the second argument for
350 * non-zero accesses and valid for the third argument for zero accesses.
352 static __isl_give isl_set
*expr_extract_context(__isl_keep pet_expr
*expr
,
353 __isl_take isl_set
*context
)
357 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
359 isl_set
*context1
, *context2
;
361 is_aff
= pet_expr_is_affine(expr
->args
[0]);
365 context
= expr_extract_context(expr
->args
[0], context
);
366 context1
= expr_extract_context(expr
->args
[1],
367 isl_set_copy(context
));
368 context2
= expr_extract_context(expr
->args
[2], context
);
374 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
375 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
376 zero_set
= access_domain(access
);
377 zero_set
= isl_set_reset_tuple_id(zero_set
);
378 context1
= isl_set_subtract(context1
,
379 isl_set_copy(zero_set
));
380 context2
= isl_set_intersect(context2
, zero_set
);
383 context
= isl_set_union(context1
, context2
);
384 context
= isl_set_coalesce(context
);
389 for (i
= 0; i
< expr
->n_arg
; ++i
)
390 context
= expr_extract_context(expr
->args
[i
], context
);
392 if (expr
->type
== pet_expr_access
)
393 context
= access_extract_context(expr
->acc
.access
, context
);
397 isl_set_free(context
);
401 /* Update "context" with the constraints imposed on the outer iteration
404 * If the statement is an assume statement with an affine expression,
405 * then intersect "context" with that expression.
406 * Otherwise, intersect "context" with the contexts of the expressions
409 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
410 __isl_take isl_set
*context
)
414 if (pet_stmt_is_assume(stmt
) &&
415 pet_expr_is_affine(stmt
->body
->args
[0])) {
416 isl_multi_pw_aff
*index
;
420 index
= stmt
->body
->args
[0]->acc
.index
;
421 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
422 cond
= isl_pw_aff_non_zero_set(pa
);
423 cond
= isl_set_reset_tuple_id(cond
);
424 return isl_set_intersect(context
, cond
);
427 for (i
= 0; i
< stmt
->n_arg
; ++i
)
428 context
= expr_extract_context(stmt
->args
[i
], context
);
430 context
= expr_extract_context(stmt
->body
, context
);
435 /* Construct a pet_scop in the given space that contains the given pet_stmt.
437 struct pet_scop
*pet_scop_from_pet_stmt(__isl_take isl_space
*space
,
438 struct pet_stmt
*stmt
)
440 struct pet_scop
*scop
;
443 space
= isl_space_free(space
);
445 scop
= scop_alloc(space
, 1);
449 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
453 scop
->stmts
[0] = stmt
;
454 scop
->loc
= pet_loc_copy(stmt
->loc
);
457 return pet_scop_free(scop
);
466 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
467 * does it represent an affine expression?
469 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
473 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
480 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
482 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
483 __isl_take isl_set
*dom
)
486 pa
= isl_set_indicator_function(set
);
487 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
491 /* Return "lhs || rhs", defined on the shared definition domain.
493 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
494 __isl_take isl_pw_aff
*rhs
)
499 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
500 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
501 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
502 isl_pw_aff_non_zero_set(rhs
));
503 cond
= isl_set_coalesce(cond
);
504 return indicator_function(cond
, dom
);
507 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
508 * ext may be equal to either ext1 or ext2.
510 * The two skips that need to be combined are assumed to be affine expressions.
512 * We need to skip in ext if we need to skip in either ext1 or ext2.
513 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
515 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
516 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
519 isl_pw_aff
*skip
, *skip1
, *skip2
;
523 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
525 if (!ext1
->skip
[type
]) {
528 ext
->skip
[type
] = ext2
->skip
[type
];
529 ext2
->skip
[type
] = NULL
;
532 if (!ext2
->skip
[type
]) {
535 ext
->skip
[type
] = ext1
->skip
[type
];
536 ext1
->skip
[type
] = NULL
;
540 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
541 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
542 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
543 isl_error_internal
, "can only combine affine skips",
546 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
547 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
548 skip
= pw_aff_or(skip1
, skip2
);
549 isl_multi_pw_aff_free(ext1
->skip
[type
]);
550 ext1
->skip
[type
] = NULL
;
551 isl_multi_pw_aff_free(ext2
->skip
[type
]);
552 ext2
->skip
[type
] = NULL
;
553 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
554 if (!ext
->skip
[type
])
559 pet_scop_free(&ext
->scop
);
563 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
564 * where type takes on the values pet_skip_now and pet_skip_later.
565 * scop may be equal to either scop1 or scop2.
567 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
568 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
570 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
571 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
572 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
574 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
575 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
579 /* Update start and end of scop->loc to include the region from "start"
580 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
581 * does not have any offset information yet and we simply take the information
582 * from "start" and "end". Otherwise, we update loc using "start" and "end".
584 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
585 unsigned start
, unsigned end
)
590 if (scop
->loc
== &pet_loc_dummy
)
591 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
594 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
597 return pet_scop_free(scop
);
602 /* Update start and end of scop->loc to include the region identified
605 struct pet_scop
*pet_scop_update_start_end_from_loc(struct pet_scop
*scop
,
606 __isl_keep pet_loc
*loc
)
608 return pet_scop_update_start_end(scop
, pet_loc_get_start(loc
),
609 pet_loc_get_end(loc
));
612 /* Replace the location of "scop" by "loc".
614 struct pet_scop
*pet_scop_set_loc(struct pet_scop
*scop
,
615 __isl_take pet_loc
*loc
)
620 pet_loc_free(scop
->loc
);
630 /* Does "implication" appear in the list of implications of "scop"?
632 static int is_known_implication(struct pet_scop
*scop
,
633 struct pet_implication
*implication
)
637 for (i
= 0; i
< scop
->n_implication
; ++i
) {
638 struct pet_implication
*pi
= scop
->implications
[i
];
641 if (pi
->satisfied
!= implication
->satisfied
)
643 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
653 /* Store the concatenation of the implications of "scop1" and "scop2"
654 * in "scop", removing duplicates (i.e., implications in "scop2" that
655 * already appear in "scop1").
657 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
658 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
665 if (scop2
->n_implication
== 0) {
666 scop
->n_implication
= scop1
->n_implication
;
667 scop
->implications
= scop1
->implications
;
668 scop1
->n_implication
= 0;
669 scop1
->implications
= NULL
;
673 if (scop1
->n_implication
== 0) {
674 scop
->n_implication
= scop2
->n_implication
;
675 scop
->implications
= scop2
->implications
;
676 scop2
->n_implication
= 0;
677 scop2
->implications
= NULL
;
681 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
682 scop1
->n_implication
+ scop2
->n_implication
);
683 if (!scop
->implications
)
684 return pet_scop_free(scop
);
686 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
687 scop
->implications
[i
] = scop1
->implications
[i
];
688 scop1
->implications
[i
] = NULL
;
691 scop
->n_implication
= scop1
->n_implication
;
692 j
= scop1
->n_implication
;
693 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
696 known
= is_known_implication(scop
, scop2
->implications
[i
]);
698 return pet_scop_free(scop
);
701 scop
->implications
[j
++] = scop2
->implications
[i
];
702 scop2
->implications
[i
] = NULL
;
704 scop
->n_implication
= j
;
709 /* Combine the offset information of "scop1" and "scop2" into "scop".
711 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
712 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
714 if (scop1
->loc
!= &pet_loc_dummy
)
715 scop
= pet_scop_update_start_end_from_loc(scop
, scop1
->loc
);
716 if (scop2
->loc
!= &pet_loc_dummy
)
717 scop
= pet_scop_update_start_end_from_loc(scop
, scop2
->loc
);
721 /* Construct a pet_scop that contains the offset information,
722 * arrays, statements and skip information in "scop1" and "scop2".
724 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
725 struct pet_scop
*scop2
)
729 struct pet_scop
*scop
= NULL
;
731 if (!scop1
|| !scop2
)
734 if (scop1
->n_stmt
== 0) {
735 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
736 pet_scop_free(scop1
);
740 if (scop2
->n_stmt
== 0) {
741 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
742 pet_scop_free(scop2
);
746 space
= isl_set_get_space(scop1
->context
);
747 scop
= scop_alloc(space
, scop1
->n_stmt
+ scop2
->n_stmt
);
751 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
752 scop1
->n_array
+ scop2
->n_array
);
755 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
757 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
758 scop
->stmts
[i
] = scop1
->stmts
[i
];
759 scop1
->stmts
[i
] = NULL
;
762 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
763 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
764 scop2
->stmts
[i
] = NULL
;
767 for (i
= 0; i
< scop1
->n_array
; ++i
) {
768 scop
->arrays
[i
] = scop1
->arrays
[i
];
769 scop1
->arrays
[i
] = NULL
;
772 for (i
= 0; i
< scop2
->n_array
; ++i
) {
773 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
774 scop2
->arrays
[i
] = NULL
;
777 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
778 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
779 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
780 scop
= scop_combine_skips(scop
, scop1
, scop2
);
781 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
783 pet_scop_free(scop1
);
784 pet_scop_free(scop2
);
787 pet_scop_free(scop1
);
788 pet_scop_free(scop2
);
793 /* Apply the skip condition "skip" to "scop".
794 * That is, make sure "scop" is not executed when the condition holds.
796 * If "skip" is an affine expression, we add the conditions under
797 * which the expression is zero to the iteration domains.
798 * Otherwise, we add a filter on the variable attaining the value zero.
800 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
801 __isl_take isl_multi_pw_aff
*skip
)
810 is_aff
= multi_pw_aff_is_affine(skip
);
815 return pet_scop_filter(scop
, skip
, 0);
817 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
818 isl_multi_pw_aff_free(skip
);
819 zero
= isl_pw_aff_zero_set(pa
);
820 scop
= pet_scop_restrict(scop
, zero
);
824 isl_multi_pw_aff_free(skip
);
825 return pet_scop_free(scop
);
828 /* Construct a pet_scop that contains the arrays, statements and
829 * skip information in "scop1" and "scop2", where the two scops
830 * are executed "in sequence". That is, breaks and continues
831 * in scop1 have an effect on scop2.
833 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
834 struct pet_scop
*scop2
)
836 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
837 scop2
= restrict_skip(scop2
,
838 pet_scop_get_skip(scop1
, pet_skip_now
));
839 return pet_scop_add(ctx
, scop1
, scop2
);
842 /* Construct a pet_scop that contains the arrays, statements and
843 * skip information in "scop1" and "scop2", where the two scops
844 * are executed "in parallel". That is, any break or continue
845 * in scop1 has no effect on scop2.
847 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
848 struct pet_scop
*scop2
)
850 return pet_scop_add(ctx
, scop1
, scop2
);
853 void *pet_implication_free(struct pet_implication
*implication
)
860 isl_map_free(implication
->extension
);
866 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
869 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
873 pet_loc_free(scop
->loc
);
874 isl_set_free(scop
->context
);
875 isl_set_free(scop
->context_value
);
877 for (i
= 0; i
< scop
->n_type
; ++i
)
878 pet_type_free(scop
->types
[i
]);
881 for (i
= 0; i
< scop
->n_array
; ++i
)
882 pet_array_free(scop
->arrays
[i
]);
885 for (i
= 0; i
< scop
->n_stmt
; ++i
)
886 pet_stmt_free(scop
->stmts
[i
]);
888 if (scop
->implications
)
889 for (i
= 0; i
< scop
->n_implication
; ++i
)
890 pet_implication_free(scop
->implications
[i
]);
891 free(scop
->implications
);
892 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
893 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
898 void pet_type_dump(struct pet_type
*type
)
903 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
906 void pet_implication_dump(struct pet_implication
*implication
)
911 fprintf(stderr
, "%d\n", implication
->satisfied
);
912 isl_map_dump(implication
->extension
);
915 void pet_scop_dump(struct pet_scop
*scop
)
918 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
923 isl_set_dump(scop
->context
);
924 isl_set_dump(scop
->context_value
);
925 for (i
= 0; i
< scop
->n_type
; ++i
)
926 pet_type_dump(scop
->types
[i
]);
927 for (i
= 0; i
< scop
->n_array
; ++i
)
928 pet_array_dump(scop
->arrays
[i
]);
929 for (i
= 0; i
< scop
->n_stmt
; ++i
)
930 pet_stmt_dump(scop
->stmts
[i
]);
931 for (i
= 0; i
< scop
->n_implication
; ++i
)
932 pet_implication_dump(scop
->implications
[i
]);
935 fprintf(stderr
, "skip\n");
936 isl_multi_pw_aff_dump(ext
->skip
[0]);
937 isl_multi_pw_aff_dump(ext
->skip
[1]);
941 /* Return 1 if the two pet_arrays are equivalent.
943 * We don't compare element_size as this may be target dependent.
945 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
947 if (!array1
|| !array2
)
950 if (!isl_set_is_equal(array1
->context
, array2
->context
))
952 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
954 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
956 if (array1
->value_bounds
&&
957 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
959 if (strcmp(array1
->element_type
, array2
->element_type
))
961 if (array1
->element_is_record
!= array2
->element_is_record
)
963 if (array1
->live_out
!= array2
->live_out
)
965 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
967 if (array1
->declared
!= array2
->declared
)
969 if (array1
->exposed
!= array2
->exposed
)
975 /* Return 1 if the two pet_stmts are equivalent.
977 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
981 if (!stmt1
|| !stmt2
)
984 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
986 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
988 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
990 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
992 if (stmt1
->n_arg
!= stmt2
->n_arg
)
994 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
995 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1002 /* Return 1 if the two pet_types are equivalent.
1004 * We only compare the names of the types since the exact representation
1005 * of the definition may depend on the version of clang being used.
1007 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1009 if (!type1
|| !type2
)
1012 if (strcmp(type1
->name
, type2
->name
))
1018 /* Return 1 if the two pet_implications are equivalent.
1020 int pet_implication_is_equal(struct pet_implication
*implication1
,
1021 struct pet_implication
*implication2
)
1023 if (!implication1
|| !implication2
)
1026 if (implication1
->satisfied
!= implication2
->satisfied
)
1028 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1034 /* Return 1 if the two pet_scops are equivalent.
1036 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1040 if (!scop1
|| !scop2
)
1043 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1045 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1048 if (scop1
->n_type
!= scop2
->n_type
)
1050 for (i
= 0; i
< scop1
->n_type
; ++i
)
1051 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1054 if (scop1
->n_array
!= scop2
->n_array
)
1056 for (i
= 0; i
< scop1
->n_array
; ++i
)
1057 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1060 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1062 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1063 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1066 if (scop1
->n_implication
!= scop2
->n_implication
)
1068 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1069 if (!pet_implication_is_equal(scop1
->implications
[i
],
1070 scop2
->implications
[i
]))
1076 /* Does the set "extent" reference a virtual array, i.e.,
1077 * one with user pointer equal to NULL?
1078 * A virtual array does not have any members.
1080 static int extent_is_virtual_array(__isl_keep isl_set
*extent
)
1085 if (!isl_set_has_tuple_id(extent
))
1087 if (isl_set_is_wrapping(extent
))
1089 id
= isl_set_get_tuple_id(extent
);
1090 is_virtual
= !isl_id_get_user(id
);
1096 /* Intersect the initial dimensions of "array" with "domain", provided
1097 * that "array" represents a virtual array.
1099 * If "array" is virtual, then We take the preimage of "domain"
1100 * over the projection of the extent of "array" onto its initial dimensions
1101 * and intersect this extent with the result.
1103 static struct pet_array
*virtual_array_intersect_domain_prefix(
1104 struct pet_array
*array
, __isl_take isl_set
*domain
)
1110 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1111 isl_set_free(domain
);
1115 space
= isl_set_get_space(array
->extent
);
1116 n
= isl_set_dim(domain
, isl_dim_set
);
1117 ma
= pet_prefix_projection(space
, n
);
1118 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1120 array
->extent
= isl_set_intersect(array
->extent
, domain
);
1122 return pet_array_free(array
);
1127 /* Intersect the initial dimensions of the domain of "stmt"
1130 * We take the preimage of "domain" over the projection of the
1131 * domain of "stmt" onto its initial dimensions and intersect
1132 * the domain of "stmt" with the result.
1134 static struct pet_stmt
*stmt_intersect_domain_prefix(struct pet_stmt
*stmt
,
1135 __isl_take isl_set
*domain
)
1144 space
= isl_set_get_space(stmt
->domain
);
1145 n
= isl_set_dim(domain
, isl_dim_set
);
1146 ma
= pet_prefix_projection(space
, n
);
1147 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1149 stmt
->domain
= isl_set_intersect(stmt
->domain
, domain
);
1151 return pet_stmt_free(stmt
);
1155 isl_set_free(domain
);
1156 return pet_stmt_free(stmt
);
1159 /* Intersect the initial dimensions of the domain of "implication"
1162 * We take the preimage of "domain" over the projection of the
1163 * domain of "implication" onto its initial dimensions and intersect
1164 * the domain of "implication" with the result.
1166 static struct pet_implication
*implication_intersect_domain_prefix(
1167 struct pet_implication
*implication
, __isl_take isl_set
*domain
)
1176 space
= isl_map_get_space(implication
->extension
);
1177 n
= isl_set_dim(domain
, isl_dim_set
);
1178 ma
= pet_prefix_projection(isl_space_domain(space
), n
);
1179 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1181 implication
->extension
=
1182 isl_map_intersect_domain(implication
->extension
, domain
);
1183 if (!implication
->extension
)
1184 return pet_implication_free(implication
);
1188 isl_set_free(domain
);
1189 return pet_implication_free(implication
);
1192 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1194 * The extents of the virtual arrays match the iteration domains,
1195 * so if the iteration domain changes, we need to change those extents too.
1197 struct pet_scop
*pet_scop_intersect_domain_prefix(struct pet_scop
*scop
,
1198 __isl_take isl_set
*domain
)
1205 for (i
= 0; i
< scop
->n_array
; ++i
) {
1206 scop
->arrays
[i
] = virtual_array_intersect_domain_prefix(
1207 scop
->arrays
[i
], isl_set_copy(domain
));
1208 if (!scop
->arrays
[i
])
1212 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1213 scop
->stmts
[i
] = stmt_intersect_domain_prefix(scop
->stmts
[i
],
1214 isl_set_copy(domain
));
1215 if (!scop
->stmts
[i
])
1219 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1220 scop
->implications
[i
] =
1221 implication_intersect_domain_prefix(scop
->implications
[i
],
1222 isl_set_copy(domain
));
1223 if (!scop
->implications
[i
])
1224 return pet_scop_free(scop
);
1227 isl_set_free(domain
);
1230 isl_set_free(domain
);
1231 return pet_scop_free(scop
);
1234 /* Prefix the schedule of "stmt" with an extra dimension with constant
1237 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1242 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1243 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1244 if (!stmt
->schedule
)
1245 return pet_stmt_free(stmt
);
1250 /* Prefix the schedules of all statements in "scop" with an extra
1251 * dimension with constant value "pos".
1253 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1260 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1261 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1262 if (!scop
->stmts
[i
])
1263 return pet_scop_free(scop
);
1269 /* Prefix the schedule of "stmt" with "sched".
1271 * The domain of "sched" refers the current outer loop iterators and
1272 * needs to be mapped to the iteration domain of "stmt" first
1273 * before being prepended to the schedule of "stmt".
1275 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1276 __isl_take isl_map
*sched
)
1285 space
= pet_stmt_get_space(stmt
);
1286 n
= isl_map_dim(sched
, isl_dim_in
);
1287 ma
= pet_prefix_projection(space
, n
);
1288 sched
= isl_map_preimage_domain_multi_aff(sched
, ma
);
1289 stmt
->schedule
= isl_map_flat_range_product(sched
, stmt
->schedule
);
1290 if (!stmt
->schedule
)
1291 return pet_stmt_free(stmt
);
1295 isl_map_free(sched
);
1299 /* Update the context with respect to an embedding into a loop
1300 * with iteration domain "dom".
1301 * The input context lives in the same space as "dom".
1302 * The output context has the inner dimension removed.
1304 * An outer loop iterator value is invalid for the embedding if
1305 * any of the corresponding inner iterator values is invalid.
1306 * That is, an outer loop iterator value is valid only if all the corresponding
1307 * inner iterator values are valid.
1308 * We therefore compute the set of outer loop iterators l
1310 * forall i: dom(l,i) => valid(l,i)
1314 * forall i: not dom(l,i) or valid(l,i)
1318 * not exists i: dom(l,i) and not valid(l,i)
1322 * not exists i: (dom \ valid)(l,i)
1324 * If there are any unnamed parameters in "dom", then we consider
1325 * a parameter value to be valid if it is valid for any value of those
1326 * unnamed parameters. They are therefore projected out at the end.
1328 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1329 __isl_keep isl_set
*dom
)
1333 pos
= isl_set_dim(context
, isl_dim_set
) - 1;
1334 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1335 context
= isl_set_project_out(context
, isl_dim_set
, pos
, 1);
1336 context
= isl_set_complement(context
);
1337 context
= pet_nested_remove_from_set(context
);
1342 /* Update the implication with respect to an embedding into a loop
1343 * with iteration domain "dom".
1345 * Since embed_access extends virtual arrays along with the domain
1346 * of the access, we need to do the same with domain and range
1347 * of the implication. Since the original implication is only valid
1348 * within a given iteration of the loop, the extended implication
1349 * maps the extra array dimension corresponding to the extra loop
1352 static struct pet_implication
*pet_implication_embed(
1353 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1361 map
= isl_set_identity(dom
);
1362 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1363 map
= isl_map_flat_product(map
, implication
->extension
);
1364 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1365 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1366 implication
->extension
= map
;
1367 if (!implication
->extension
)
1368 return pet_implication_free(implication
);
1376 /* Adjust the context and statement schedules according to an embedding
1377 * in a loop with iteration domain "dom" and schedule "sched".
1379 * Any skip conditions within the loop have no effect outside of the loop.
1380 * The caller is responsible for making sure skip[pet_skip_later] has been
1381 * taken into account.
1383 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1384 __isl_take isl_aff
*sched
)
1389 sched_map
= isl_map_from_aff(sched
);
1394 pet_scop_reset_skip(scop
, pet_skip_now
);
1395 pet_scop_reset_skip(scop
, pet_skip_later
);
1397 scop
->context
= context_embed(scop
->context
, dom
);
1401 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1402 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1403 isl_map_copy(sched_map
));
1404 if (!scop
->stmts
[i
])
1409 isl_map_free(sched_map
);
1413 isl_map_free(sched_map
);
1414 return pet_scop_free(scop
);
1417 /* Add extra conditions to scop->skip[type].
1419 * The new skip condition only holds if it held before
1420 * and the condition is true. It does not hold if it did not hold
1421 * before or the condition is false.
1423 * The skip condition is assumed to be an affine expression.
1425 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1426 enum pet_skip type
, __isl_keep isl_set
*cond
)
1428 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1434 if (!ext
->skip
[type
])
1437 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1438 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1439 isl_error_internal
, "can only restrict affine skips",
1440 return pet_scop_free(scop
));
1442 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1443 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1444 cond
= isl_set_copy(cond
);
1445 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1446 skip
= indicator_function(cond
, dom
);
1447 isl_multi_pw_aff_free(ext
->skip
[type
]);
1448 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1449 if (!ext
->skip
[type
])
1450 return pet_scop_free(scop
);
1455 /* Adjust the context and the skip conditions to the fact that
1456 * the scop was created in a context where "cond" holds.
1458 * An outer loop iterator or parameter value is valid for the result
1459 * if it was valid for the original scop and satisfies "cond" or if it does
1460 * not satisfy "cond" as in this case the scop is not executed
1461 * and the original constraints on these values are irrelevant.
1463 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1464 __isl_take isl_set
*cond
)
1468 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1469 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1474 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1475 scop
->context
= isl_set_union(scop
->context
,
1476 isl_set_complement(isl_set_copy(cond
)));
1477 scop
->context
= isl_set_coalesce(scop
->context
);
1478 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1486 return pet_scop_free(scop
);
1489 /* Insert an argument expression corresponding to "test" in front
1490 * of the list of arguments described by *n_arg and *args.
1492 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1493 __isl_keep isl_multi_pw_aff
*test
)
1496 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1502 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1507 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
1510 for (i
= 0; i
< *n_arg
; ++i
)
1511 ext
[1 + i
] = (*args
)[i
];
1516 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1523 /* Look through the applications in "scop" for any that can be
1524 * applied to the filter expressed by "map" and "satisified".
1525 * If there is any, then apply it to "map" and return the result.
1526 * Otherwise, return "map".
1527 * "id" is the identifier of the virtual array.
1529 * We only introduce at most one implication for any given virtual array,
1530 * so we can apply the implication and return as soon as we find one.
1532 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1533 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1537 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1538 struct pet_implication
*pi
= scop
->implications
[i
];
1541 if (pi
->satisfied
!= satisfied
)
1543 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1548 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1554 /* Is the filter expressed by "test" and "satisfied" implied
1555 * by filter "pos" on "domain", with filter "expr", taking into
1556 * account the implications of "scop"?
1558 * For filter on domain implying that expressed by "test" and "satisfied",
1559 * the filter needs to be an access to the same (virtual) array as "test" and
1560 * the filter value needs to be equal to "satisfied".
1561 * Moreover, the filter access relation, possibly extended by
1562 * the implications in "scop" needs to contain "test".
1564 static int implies_filter(struct pet_scop
*scop
,
1565 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
1566 __isl_keep isl_map
*test
, int satisfied
)
1568 isl_id
*test_id
, *arg_id
;
1575 if (expr
->type
!= pet_expr_access
)
1577 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1578 arg_id
= pet_expr_access_get_id(expr
);
1579 isl_id_free(arg_id
);
1580 isl_id_free(test_id
);
1581 if (test_id
!= arg_id
)
1583 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
1584 is_int
= isl_val_is_int(val
);
1586 s
= isl_val_get_num_si(val
);
1595 implied
= isl_map_copy(expr
->acc
.access
);
1596 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
1597 is_subset
= isl_map_is_subset(test
, implied
);
1598 isl_map_free(implied
);
1603 /* Is the filter expressed by "test" and "satisfied" implied
1604 * by any of the filters on the domain of "stmt", taking into
1605 * account the implications of "scop"?
1607 static int filter_implied(struct pet_scop
*scop
,
1608 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1616 if (!scop
|| !stmt
|| !test
)
1618 if (scop
->n_implication
== 0)
1620 if (stmt
->n_arg
== 0)
1623 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
1624 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
1627 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
1628 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
1629 test_map
, satisfied
);
1630 if (implied
< 0 || implied
)
1634 isl_map_free(test_map
);
1635 isl_map_free(domain
);
1639 /* Make the statement "stmt" depend on the value of "test"
1640 * being equal to "satisfied" by adjusting stmt->domain.
1642 * The domain of "test" corresponds to the (zero or more) outer dimensions
1643 * of the iteration domain.
1645 * We first extend "test" to apply to the entire iteration domain and
1646 * then check if the filter that we are about to add is implied
1647 * by any of the current filters, possibly taking into account
1648 * the implications in "scop". If so, we leave "stmt" untouched and return.
1650 * Otherwise, we insert an argument corresponding to a read to "test"
1651 * from the iteration domain of "stmt" in front of the list of arguments.
1652 * We also insert a corresponding output dimension in the wrapped
1653 * map contained in stmt->domain, with value set to "satisfied".
1655 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
1656 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1662 isl_pw_multi_aff
*pma
;
1663 isl_multi_aff
*add_dom
;
1665 isl_local_space
*ls
;
1671 space
= pet_stmt_get_space(stmt
);
1672 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
1673 space
= isl_space_from_domain(space
);
1674 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
1675 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
1676 ls
= isl_local_space_from_space(isl_space_domain(space
));
1677 for (i
= 0; i
< n_test_dom
; ++i
) {
1679 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1681 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
1683 isl_local_space_free(ls
);
1684 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
1686 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
1690 isl_multi_pw_aff_free(test
);
1694 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1695 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
1697 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
1699 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1702 isl_multi_pw_aff_free(test
);
1705 isl_multi_pw_aff_free(test
);
1706 return pet_stmt_free(stmt
);
1709 /* Does "scop" have a skip condition of the given "type"?
1711 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1713 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1717 return ext
->skip
[type
] != NULL
;
1720 /* Does "scop" have a skip condition of the given "type" that
1721 * is an affine expression?
1723 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1725 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1729 if (!ext
->skip
[type
])
1731 return multi_pw_aff_is_affine(ext
->skip
[type
]);
1734 /* Does "scop" have a skip condition of the given "type" that
1735 * is not an affine expression?
1737 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1739 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1744 if (!ext
->skip
[type
])
1746 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
1752 /* Does "scop" have a skip condition of the given "type" that
1753 * is affine and holds on the entire domain?
1755 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
1757 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1763 is_aff
= pet_scop_has_affine_skip(scop
, type
);
1764 if (is_aff
< 0 || !is_aff
)
1767 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1768 set
= isl_pw_aff_non_zero_set(pa
);
1769 is_univ
= isl_set_plain_is_universe(set
);
1775 /* Replace scop->skip[type] by "skip".
1777 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
1778 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
1780 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1785 isl_multi_pw_aff_free(ext
->skip
[type
]);
1786 ext
->skip
[type
] = skip
;
1790 isl_multi_pw_aff_free(skip
);
1791 return pet_scop_free(scop
);
1794 /* Return a copy of scop->skip[type].
1796 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
1799 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1804 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
1807 /* Assuming scop->skip[type] is an affine expression,
1808 * return the constraints on the outer loop domain for which the skip condition
1811 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
1814 isl_multi_pw_aff
*skip
;
1817 skip
= pet_scop_get_skip(scop
, type
);
1818 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
1819 isl_multi_pw_aff_free(skip
);
1820 return isl_pw_aff_non_zero_set(pa
);
1823 /* Return the identifier of the variable that is accessed by
1824 * the skip condition of the given type.
1826 * The skip condition is assumed not to be an affine condition.
1828 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
1831 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1836 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
1839 /* Return an access pet_expr corresponding to the skip condition
1840 * of the given type.
1842 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
1845 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
1848 /* Drop the the skip condition scop->skip[type].
1850 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
1852 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1857 isl_multi_pw_aff_free(ext
->skip
[type
]);
1858 ext
->skip
[type
] = NULL
;
1861 /* Make the skip condition (if any) depend on the value of "test" being
1862 * equal to "satisfied".
1864 * We only support the case where the original skip condition is universal,
1865 * i.e., where skipping is unconditional, and where satisfied == 1.
1866 * In this case, the skip condition is changed to skip only when
1867 * "test" is equal to one.
1869 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
1870 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1876 if (!pet_scop_has_skip(scop
, type
))
1880 is_univ
= pet_scop_has_universal_skip(scop
, type
);
1882 return pet_scop_free(scop
);
1883 if (satisfied
&& is_univ
) {
1884 isl_multi_pw_aff
*skip
;
1885 skip
= isl_multi_pw_aff_copy(test
);
1886 scop
= pet_scop_set_skip(scop
, type
, skip
);
1890 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
1891 "skip expression cannot be filtered",
1892 return pet_scop_free(scop
));
1898 /* Make all statements in "scop" depend on the value of "test"
1899 * being equal to "satisfied" by adjusting their domains.
1901 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
1902 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1906 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
1907 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
1912 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1913 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
1914 isl_multi_pw_aff_copy(test
), satisfied
);
1915 if (!scop
->stmts
[i
])
1919 isl_multi_pw_aff_free(test
);
1922 isl_multi_pw_aff_free(test
);
1923 return pet_scop_free(scop
);
1926 /* Add all parameters in "expr" to "space" and return the result.
1928 static __isl_give isl_space
*expr_collect_params(__isl_keep pet_expr
*expr
,
1929 __isl_take isl_space
*space
)
1935 for (i
= 0; i
< expr
->n_arg
; ++i
)
1936 space
= expr_collect_params(expr
->args
[i
], space
);
1938 if (expr
->type
== pet_expr_access
)
1939 space
= isl_space_align_params(space
,
1940 isl_map_get_space(expr
->acc
.access
));
1944 pet_expr_free(expr
);
1945 return isl_space_free(space
);
1948 /* Add all parameters in "stmt" to "space" and return the result.
1950 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
1951 __isl_take isl_space
*space
)
1956 return isl_space_free(space
);
1958 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
1959 space
= isl_space_align_params(space
,
1960 isl_map_get_space(stmt
->schedule
));
1961 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1962 space
= expr_collect_params(stmt
->args
[i
], space
);
1963 space
= expr_collect_params(stmt
->body
, space
);
1968 /* Add all parameters in "array" to "space" and return the result.
1970 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
1971 __isl_take isl_space
*space
)
1974 return isl_space_free(space
);
1976 space
= isl_space_align_params(space
,
1977 isl_set_get_space(array
->context
));
1978 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
1983 /* Add all parameters in "scop" to "space" and return the result.
1985 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
1986 __isl_take isl_space
*space
)
1991 return isl_space_free(space
);
1993 for (i
= 0; i
< scop
->n_array
; ++i
)
1994 space
= array_collect_params(scop
->arrays
[i
], space
);
1996 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1997 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2002 /* Add all parameters in "space" to the domain, schedule and
2003 * all access relations in "stmt".
2005 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2006 __isl_take isl_space
*space
)
2013 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2014 isl_space_copy(space
));
2015 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2016 isl_space_copy(space
));
2018 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2019 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2020 isl_space_copy(space
));
2024 stmt
->body
= pet_expr_align_params(stmt
->body
, isl_space_copy(space
));
2026 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2029 isl_space_free(space
);
2032 isl_space_free(space
);
2033 return pet_stmt_free(stmt
);
2036 /* Add all parameters in "space" to "array".
2038 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2039 __isl_take isl_space
*space
)
2044 array
->context
= isl_set_align_params(array
->context
,
2045 isl_space_copy(space
));
2046 array
->extent
= isl_set_align_params(array
->extent
,
2047 isl_space_copy(space
));
2048 if (array
->value_bounds
) {
2049 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2050 isl_space_copy(space
));
2051 if (!array
->value_bounds
)
2055 if (!array
->context
|| !array
->extent
)
2058 isl_space_free(space
);
2061 isl_space_free(space
);
2062 return pet_array_free(array
);
2065 /* Add all parameters in "space" to "scop".
2067 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2068 __isl_take isl_space
*space
)
2075 for (i
= 0; i
< scop
->n_array
; ++i
) {
2076 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2077 isl_space_copy(space
));
2078 if (!scop
->arrays
[i
])
2082 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2083 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2084 isl_space_copy(space
));
2085 if (!scop
->stmts
[i
])
2089 isl_space_free(space
);
2092 isl_space_free(space
);
2093 return pet_scop_free(scop
);
2096 /* Update all isl_sets and isl_maps in "scop" such that they all
2097 * have the same parameters.
2099 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2106 space
= isl_set_get_space(scop
->context
);
2107 space
= scop_collect_params(scop
, space
);
2109 scop
->context
= isl_set_align_params(scop
->context
,
2110 isl_space_copy(space
));
2111 scop
= scop_propagate_params(scop
, space
);
2113 if (scop
&& !scop
->context
)
2114 return pet_scop_free(scop
);
2119 /* Add the access relation of the access expression "expr" to "accesses" and
2120 * return the result.
2121 * The domain of the access relation is intersected with "domain".
2122 * If "tag" is set, then the access relation is tagged with
2123 * the corresponding reference identifier.
2125 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2126 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2130 access
= pet_expr_access_get_may_access(expr
);
2131 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
2133 access
= pet_expr_tag_access(expr
, access
);
2134 return isl_union_map_add_map(accesses
, access
);
2137 /* Add all read access relations (if "read" is set) and/or all write
2138 * access relations (if "write" is set) to "accesses" and return the result.
2139 * The domains of the access relations are intersected with "domain".
2140 * If "tag" is set, then the access relations are tagged with
2141 * the corresponding reference identifiers.
2143 * If "must" is set, then we only add the accesses that are definitely
2144 * performed. Otherwise, we add all potential accesses.
2145 * In particular, if the access has any arguments, then if "must" is
2146 * set we currently skip the access completely. If "must" is not set,
2147 * we project out the values of the access arguments.
2149 static __isl_give isl_union_map
*expr_collect_accesses(
2150 __isl_keep pet_expr
*expr
, int read
, int write
, int must
, int tag
,
2151 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2158 return isl_union_map_free(accesses
);
2160 for (i
= 0; i
< expr
->n_arg
; ++i
)
2161 accesses
= expr_collect_accesses(expr
->args
[i
],
2162 read
, write
, must
, tag
, accesses
, domain
);
2164 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2165 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
2166 (!must
|| expr
->n_arg
== 0)) {
2167 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
2173 /* Collect and return all read access relations (if "read" is set)
2174 * and/or all write access relations (if "write" is set) in "stmt".
2175 * If "tag" is set, then the access relations are tagged with
2176 * the corresponding reference identifiers.
2177 * If "kill" is set, then "stmt" is a kill statement and we simply
2178 * add the argument of the kill operation.
2180 * If "must" is set, then we only add the accesses that are definitely
2181 * performed. Otherwise, we add all potential accesses.
2182 * In particular, if the statement has any arguments, then if "must" is
2183 * set we currently skip the statement completely. If "must" is not set,
2184 * we project out the values of the statement arguments.
2186 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2187 int read
, int write
, int kill
, int must
, int tag
,
2188 __isl_take isl_space
*dim
)
2190 isl_union_map
*accesses
;
2196 accesses
= isl_union_map_empty(dim
);
2198 if (must
&& stmt
->n_arg
> 0)
2201 domain
= isl_set_copy(stmt
->domain
);
2202 if (isl_set_is_wrapping(domain
))
2203 domain
= isl_map_domain(isl_set_unwrap(domain
));
2206 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
2209 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
2210 must
, tag
, accesses
, domain
);
2211 isl_set_free(domain
);
2216 /* Is "stmt" an assignment statement?
2218 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2222 if (stmt
->body
->type
!= pet_expr_op
)
2224 return stmt
->body
->op
== pet_op_assign
;
2227 /* Is "stmt" a kill statement?
2229 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2233 if (stmt
->body
->type
!= pet_expr_op
)
2235 return stmt
->body
->op
== pet_op_kill
;
2238 /* Is "stmt" an assume statement?
2240 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2244 return pet_expr_is_assume(stmt
->body
);
2247 /* Compute a mapping from all arrays (of structs) in scop
2248 * to their innermost arrays.
2250 * In particular, for each array of a primitive type, the result
2251 * contains the identity mapping on that array.
2252 * For each array involving member accesses, the result
2253 * contains a mapping from the elements of any intermediate array of structs
2254 * to all corresponding elements of the innermost nested arrays.
2256 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
2259 isl_union_map
*to_inner
;
2261 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2263 for (i
= 0; i
< scop
->n_array
; ++i
) {
2264 struct pet_array
*array
= scop
->arrays
[i
];
2266 isl_map
*map
, *gist
;
2268 if (array
->element_is_record
)
2271 map
= isl_set_identity(isl_set_copy(array
->extent
));
2273 set
= isl_map_domain(isl_map_copy(map
));
2274 gist
= isl_map_copy(map
);
2275 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2276 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2278 while (set
&& isl_set_is_wrapping(set
)) {
2282 id
= isl_set_get_tuple_id(set
);
2283 wrapped
= isl_set_unwrap(set
);
2284 wrapped
= isl_map_domain_map(wrapped
);
2285 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2286 map
= isl_map_apply_domain(map
, wrapped
);
2287 set
= isl_map_domain(isl_map_copy(map
));
2288 gist
= isl_map_copy(map
);
2289 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2290 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2300 /* Collect and return all read access relations (if "read" is set)
2301 * and/or all write access relations (if "write" is set) in "scop".
2302 * If "kill" is set, then we only add the arguments of kill operations.
2303 * If "must" is set, then we only add the accesses that are definitely
2304 * performed. Otherwise, we add all potential accesses.
2305 * If "tag" is set, then the access relations are tagged with
2306 * the corresponding reference identifiers.
2307 * For accesses to structures, the returned access relation accesses
2308 * all individual fields in the structures.
2310 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2311 int read
, int write
, int kill
, int must
, int tag
)
2314 isl_union_map
*accesses
;
2315 isl_union_set
*arrays
;
2316 isl_union_map
*to_inner
;
2321 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2323 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2324 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2325 isl_union_map
*accesses_i
;
2328 if (kill
&& !pet_stmt_is_kill(stmt
))
2331 space
= isl_set_get_space(scop
->context
);
2332 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
2334 accesses
= isl_union_map_union(accesses
, accesses_i
);
2337 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2338 for (i
= 0; i
< scop
->n_array
; ++i
) {
2339 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2340 arrays
= isl_union_set_add_set(arrays
, extent
);
2342 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2344 to_inner
= compute_to_inner(scop
);
2345 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2350 /* Collect all potential read access relations.
2352 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2354 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
2357 /* Collect all potential write access relations.
2359 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2361 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
2364 /* Collect all definite write access relations.
2366 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2368 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
2371 /* Collect all definite kill access relations.
2373 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2375 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
2378 /* Collect all tagged potential read access relations.
2380 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2381 struct pet_scop
*scop
)
2383 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
2386 /* Collect all tagged potential write access relations.
2388 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2389 struct pet_scop
*scop
)
2391 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
2394 /* Collect all tagged definite write access relations.
2396 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2397 struct pet_scop
*scop
)
2399 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
2402 /* Collect all tagged definite kill access relations.
2404 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2405 struct pet_scop
*scop
)
2407 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
2410 /* Collect and return the union of iteration domains in "scop".
2412 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2416 isl_union_set
*domain
;
2421 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2423 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2424 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2425 domain
= isl_union_set_add_set(domain
, domain_i
);
2431 /* Collect and return the schedules of the statements in "scop".
2432 * The range is normalized to the maximal number of scheduling
2435 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2438 isl_map
*schedule_i
;
2439 isl_union_map
*schedule
;
2440 int depth
, max_depth
= 0;
2445 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2447 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2448 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2449 if (depth
> max_depth
)
2453 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2454 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2455 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2456 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2458 for (j
= depth
; j
< max_depth
; ++j
)
2459 schedule_i
= isl_map_fix_si(schedule_i
,
2461 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2467 /* Add a reference identifier to all access expressions in "stmt".
2468 * "n_ref" points to an integer that contains the sequence number
2469 * of the next reference.
2471 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2478 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2479 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2481 return pet_stmt_free(stmt
);
2484 stmt
->body
= pet_expr_add_ref_ids(stmt
->body
, n_ref
);
2486 return pet_stmt_free(stmt
);
2491 /* Add a reference identifier to all access expressions in "scop".
2493 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2502 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2503 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2504 if (!scop
->stmts
[i
])
2505 return pet_scop_free(scop
);
2511 /* Reset the user pointer on all parameter ids in "array".
2513 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2518 array
->context
= isl_set_reset_user(array
->context
);
2519 array
->extent
= isl_set_reset_user(array
->extent
);
2520 if (!array
->context
|| !array
->extent
)
2521 return pet_array_free(array
);
2526 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2528 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2537 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
2538 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
2539 if (!stmt
->domain
|| !stmt
->schedule
)
2540 return pet_stmt_free(stmt
);
2542 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2543 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
2545 return pet_stmt_free(stmt
);
2548 stmt
->body
= pet_expr_anonymize(stmt
->body
);
2550 return pet_stmt_free(stmt
);
2555 /* Reset the user pointer on the tuple ids and all parameter ids
2558 static struct pet_implication
*implication_anonymize(
2559 struct pet_implication
*implication
)
2564 implication
->extension
= isl_map_reset_user(implication
->extension
);
2565 if (!implication
->extension
)
2566 return pet_implication_free(implication
);
2571 /* Reset the user pointer on all parameter and tuple ids in "scop".
2573 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2580 scop
->context
= isl_set_reset_user(scop
->context
);
2581 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
2582 if (!scop
->context
|| !scop
->context_value
)
2583 return pet_scop_free(scop
);
2585 for (i
= 0; i
< scop
->n_array
; ++i
) {
2586 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2587 if (!scop
->arrays
[i
])
2588 return pet_scop_free(scop
);
2591 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2592 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2593 if (!scop
->stmts
[i
])
2594 return pet_scop_free(scop
);
2597 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2598 scop
->implications
[i
] =
2599 implication_anonymize(scop
->implications
[i
]);
2600 if (!scop
->implications
[i
])
2601 return pet_scop_free(scop
);
2607 /* Compute the gist of the iteration domain and all access relations
2608 * of "stmt" based on the constraints on the parameters specified by "context"
2609 * and the constraints on the values of nested accesses specified
2610 * by "value_bounds".
2612 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2613 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2621 domain
= isl_set_copy(stmt
->domain
);
2622 if (stmt
->n_arg
> 0)
2623 domain
= isl_map_domain(isl_set_unwrap(domain
));
2625 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2627 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2628 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
2629 domain
, value_bounds
);
2634 stmt
->body
= pet_expr_gist(stmt
->body
, domain
, value_bounds
);
2638 isl_set_free(domain
);
2640 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
2641 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2642 if (stmt
->n_arg
> 0)
2643 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
2645 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2647 return pet_stmt_free(stmt
);
2651 isl_set_free(domain
);
2652 return pet_stmt_free(stmt
);
2655 /* Compute the gist of the extent of the array
2656 * based on the constraints on the parameters specified by "context".
2658 static struct pet_array
*array_gist(struct pet_array
*array
,
2659 __isl_keep isl_set
*context
)
2664 array
->extent
= isl_set_gist_params(array
->extent
,
2665 isl_set_copy(context
));
2667 return pet_array_free(array
);
2672 /* Compute the gist of all sets and relations in "scop"
2673 * based on the constraints on the parameters specified by "scop->context"
2674 * and the constraints on the values of nested accesses specified
2675 * by "value_bounds".
2677 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
2678 __isl_keep isl_union_map
*value_bounds
)
2685 scop
->context
= isl_set_coalesce(scop
->context
);
2687 return pet_scop_free(scop
);
2689 for (i
= 0; i
< scop
->n_array
; ++i
) {
2690 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
2691 if (!scop
->arrays
[i
])
2692 return pet_scop_free(scop
);
2695 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2696 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
2698 if (!scop
->stmts
[i
])
2699 return pet_scop_free(scop
);
2705 /* Intersect the context of "scop" with "context".
2706 * To ensure that we don't introduce any unnamed parameters in
2707 * the context of "scop", we first remove the unnamed parameters
2710 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
2711 __isl_take isl_set
*context
)
2716 context
= pet_nested_remove_from_set(context
);
2717 scop
->context
= isl_set_intersect(scop
->context
, context
);
2719 return pet_scop_free(scop
);
2723 isl_set_free(context
);
2724 return pet_scop_free(scop
);
2727 /* Drop the current context of "scop". That is, replace the context
2728 * by a universal set.
2730 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
2737 space
= isl_set_get_space(scop
->context
);
2738 isl_set_free(scop
->context
);
2739 scop
->context
= isl_set_universe(space
);
2741 return pet_scop_free(scop
);
2746 /* Append "array" to the arrays of "scop".
2748 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
2749 struct pet_array
*array
)
2752 struct pet_array
**arrays
;
2754 if (!array
|| !scop
)
2757 ctx
= isl_set_get_ctx(scop
->context
);
2758 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
2762 scop
->arrays
= arrays
;
2763 scop
->arrays
[scop
->n_array
] = array
;
2768 pet_array_free(array
);
2769 return pet_scop_free(scop
);
2772 /* Create an index expression for an access to a virtual array
2773 * representing the result of a condition.
2774 * Unlike other accessed data, the id of the array is NULL as
2775 * there is no ValueDecl in the program corresponding to the virtual
2777 * The index expression is created as an identity mapping on "space".
2778 * That is, the dimension of the array is the same as that of "space".
2780 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
2786 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
2787 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
2788 space
= isl_space_map_from_set(space
);
2789 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
2790 return isl_multi_pw_aff_identity(space
);
2793 /* Add an array with the given extent to the list
2794 * of arrays in "scop" and return the extended pet_scop.
2795 * Specifically, the extent is determined by the image of "domain"
2797 * "int_size" is the number of bytes needed to represent values of type "int".
2798 * The array is marked as attaining values 0 and 1 only and
2799 * as each element being assigned at most once.
2801 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
2802 __isl_take isl_set
*domain
, __isl_take isl_multi_pw_aff
*index
,
2807 struct pet_array
*array
;
2810 if (!scop
|| !domain
|| !index
)
2813 ctx
= isl_multi_pw_aff_get_ctx(index
);
2814 array
= isl_calloc_type(ctx
, struct pet_array
);
2818 access
= isl_map_from_multi_pw_aff(index
);
2819 access
= isl_map_intersect_domain(access
, domain
);
2820 array
->extent
= isl_map_range(access
);
2821 space
= isl_space_params_alloc(ctx
, 0);
2822 array
->context
= isl_set_universe(space
);
2823 space
= isl_space_set_alloc(ctx
, 0, 1);
2824 array
->value_bounds
= isl_set_universe(space
);
2825 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
2827 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
2829 array
->element_type
= strdup("int");
2830 array
->element_size
= int_size
;
2831 array
->uniquely_defined
= 1;
2833 if (!array
->extent
|| !array
->context
)
2834 array
= pet_array_free(array
);
2836 scop
= pet_scop_add_array(scop
, array
);
2840 isl_set_free(domain
);
2841 isl_multi_pw_aff_free(index
);
2842 return pet_scop_free(scop
);
2845 /* Create and return an implication on filter values equal to "satisfied"
2846 * with extension "map".
2848 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
2852 struct pet_implication
*implication
;
2856 ctx
= isl_map_get_ctx(map
);
2857 implication
= isl_alloc_type(ctx
, struct pet_implication
);
2861 implication
->extension
= map
;
2862 implication
->satisfied
= satisfied
;
2870 /* Add an implication on filter values equal to "satisfied"
2871 * with extension "map" to "scop".
2873 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
2874 __isl_take isl_map
*map
, int satisfied
)
2877 struct pet_implication
*implication
;
2878 struct pet_implication
**implications
;
2880 implication
= new_implication(map
, satisfied
);
2881 if (!scop
|| !implication
)
2884 ctx
= isl_set_get_ctx(scop
->context
);
2885 implications
= isl_realloc_array(ctx
, scop
->implications
,
2886 struct pet_implication
*,
2887 scop
->n_implication
+ 1);
2890 scop
->implications
= implications
;
2891 scop
->implications
[scop
->n_implication
] = implication
;
2892 scop
->n_implication
++;
2896 pet_implication_free(implication
);
2897 return pet_scop_free(scop
);
2900 /* Given an access expression, check if it is data dependent.
2901 * If so, set *found and abort the search.
2903 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
2907 if (pet_expr_get_n_arg(expr
) > 0) {
2915 /* Does "scop" contain any data dependent accesses?
2917 * Check the body of each statement for such accesses.
2919 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
2927 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2928 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
2929 &is_data_dependent
, &found
);
2930 if (r
< 0 && !found
)
2939 /* Does "scop" contain and data dependent conditions?
2941 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
2948 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2949 if (scop
->stmts
[i
]->n_arg
> 0)
2955 /* Keep track of the "input" file inside the (extended) "scop".
2957 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
2959 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2969 /* Print the original code corresponding to "scop" to printer "p".
2971 * pet_scop_print_original can only be called from
2972 * a pet_transform_C_source callback. This means that the input
2973 * file is stored in the extended scop and that the printer prints
2976 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
2977 __isl_take isl_printer
*p
)
2979 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2981 unsigned start
, end
;
2984 return isl_printer_free(p
);
2987 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
2988 "no input file stored in scop",
2989 return isl_printer_free(p
));
2991 output
= isl_printer_get_file(p
);
2993 return isl_printer_free(p
);
2995 start
= pet_loc_get_start(scop
->loc
);
2996 end
= pet_loc_get_end(scop
->loc
);
2997 if (copy(ext
->input
, output
, start
, end
) < 0)
2998 return isl_printer_free(p
);