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 in the given space and with room for n statements.
267 * We currently only take into account the parameters 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 space
= isl_space_params(space
);
286 scop
->context
= isl_set_universe(isl_space_copy(space
));
287 scop
->context_value
= isl_set_universe(space
);
288 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
289 if (!scop
->context
|| !scop
->stmts
)
290 return pet_scop_free(scop
);
292 scop
->loc
= &pet_loc_dummy
;
298 /* Construct a pet_scop in the given space containing 0 statements.
300 struct pet_scop
*pet_scop_empty(__isl_take isl_space
*space
)
302 return scop_alloc(space
, 0);
305 /* Update "context" with respect to the valid parameter values for "access".
307 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
308 __isl_take isl_set
*context
)
310 context
= isl_set_intersect(context
,
311 isl_map_params(isl_map_copy(access
)));
315 /* Update "context" with respect to the valid parameter values for "expr".
317 * If "expr" represents a conditional operator, then a parameter value
318 * needs to be valid for the condition and for at least one of the
319 * remaining two arguments.
320 * If the condition is an affine expression, then we can be a bit more specific.
321 * The parameter then has to be valid for the second argument for
322 * non-zero accesses and valid for the third argument for zero accesses.
324 static __isl_give isl_set
*expr_extract_context(__isl_keep pet_expr
*expr
,
325 __isl_take isl_set
*context
)
329 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
331 isl_set
*context1
, *context2
;
333 is_aff
= pet_expr_is_affine(expr
->args
[0]);
337 context
= expr_extract_context(expr
->args
[0], context
);
338 context1
= expr_extract_context(expr
->args
[1],
339 isl_set_copy(context
));
340 context2
= expr_extract_context(expr
->args
[2], context
);
346 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
347 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
348 zero_set
= isl_map_params(access
);
349 context1
= isl_set_subtract(context1
,
350 isl_set_copy(zero_set
));
351 context2
= isl_set_intersect(context2
, zero_set
);
354 context
= isl_set_union(context1
, context2
);
355 context
= isl_set_coalesce(context
);
360 for (i
= 0; i
< expr
->n_arg
; ++i
)
361 context
= expr_extract_context(expr
->args
[i
], context
);
363 if (expr
->type
== pet_expr_access
)
364 context
= access_extract_context(expr
->acc
.access
, context
);
368 isl_set_free(context
);
372 /* Update "context" with respect to the valid parameter values for "stmt".
374 * If the statement is an assume statement with an affine expression,
375 * then intersect "context" with that expression.
376 * Otherwise, intersect "context" with the contexts of the expressions
379 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
380 __isl_take isl_set
*context
)
384 if (pet_stmt_is_assume(stmt
) &&
385 pet_expr_is_affine(stmt
->body
->args
[0])) {
386 isl_multi_pw_aff
*index
;
390 index
= stmt
->body
->args
[0]->acc
.index
;
391 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
392 cond
= isl_set_params(isl_pw_aff_non_zero_set(pa
));
393 return isl_set_intersect(context
, cond
);
396 for (i
= 0; i
< stmt
->n_arg
; ++i
)
397 context
= expr_extract_context(stmt
->args
[i
], context
);
399 context
= expr_extract_context(stmt
->body
, context
);
404 /* Construct a pet_scop in the given space that contains the given pet_stmt.
406 struct pet_scop
*pet_scop_from_pet_stmt(__isl_take isl_space
*space
,
407 struct pet_stmt
*stmt
)
409 struct pet_scop
*scop
;
412 space
= isl_space_free(space
);
414 scop
= scop_alloc(space
, 1);
418 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
422 scop
->stmts
[0] = stmt
;
423 scop
->loc
= pet_loc_copy(stmt
->loc
);
426 return pet_scop_free(scop
);
435 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
436 * does it represent an affine expression?
438 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
442 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
449 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
451 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
452 __isl_take isl_set
*dom
)
455 pa
= isl_set_indicator_function(set
);
456 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
460 /* Return "lhs || rhs", defined on the shared definition domain.
462 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
463 __isl_take isl_pw_aff
*rhs
)
468 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
469 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
470 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
471 isl_pw_aff_non_zero_set(rhs
));
472 cond
= isl_set_coalesce(cond
);
473 return indicator_function(cond
, dom
);
476 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
477 * ext may be equal to either ext1 or ext2.
479 * The two skips that need to be combined are assumed to be affine expressions.
481 * We need to skip in ext if we need to skip in either ext1 or ext2.
482 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
484 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
485 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
488 isl_pw_aff
*skip
, *skip1
, *skip2
;
492 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
494 if (!ext1
->skip
[type
]) {
497 ext
->skip
[type
] = ext2
->skip
[type
];
498 ext2
->skip
[type
] = NULL
;
501 if (!ext2
->skip
[type
]) {
504 ext
->skip
[type
] = ext1
->skip
[type
];
505 ext1
->skip
[type
] = NULL
;
509 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
510 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
511 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
512 isl_error_internal
, "can only combine affine skips",
515 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
516 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
517 skip
= pw_aff_or(skip1
, skip2
);
518 isl_multi_pw_aff_free(ext1
->skip
[type
]);
519 ext1
->skip
[type
] = NULL
;
520 isl_multi_pw_aff_free(ext2
->skip
[type
]);
521 ext2
->skip
[type
] = NULL
;
522 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
523 if (!ext
->skip
[type
])
528 pet_scop_free(&ext
->scop
);
532 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
533 * where type takes on the values pet_skip_now and pet_skip_later.
534 * scop may be equal to either scop1 or scop2.
536 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
537 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
539 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
540 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
541 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
543 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
544 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
548 /* Update start and end of scop->loc to include the region from "start"
549 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
550 * does not have any offset information yet and we simply take the information
551 * from "start" and "end". Otherwise, we update loc using "start" and "end".
553 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
554 unsigned start
, unsigned end
)
559 if (scop
->loc
== &pet_loc_dummy
)
560 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
563 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
566 return pet_scop_free(scop
);
571 /* Update start and end of scop->loc to include the region identified
574 struct pet_scop
*pet_scop_update_start_end_from_loc(struct pet_scop
*scop
,
575 __isl_keep pet_loc
*loc
)
577 return pet_scop_update_start_end(scop
, pet_loc_get_start(loc
),
578 pet_loc_get_end(loc
));
581 /* Replace the location of "scop" by "loc".
583 struct pet_scop
*pet_scop_set_loc(struct pet_scop
*scop
,
584 __isl_take pet_loc
*loc
)
589 pet_loc_free(scop
->loc
);
599 /* Does "implication" appear in the list of implications of "scop"?
601 static int is_known_implication(struct pet_scop
*scop
,
602 struct pet_implication
*implication
)
606 for (i
= 0; i
< scop
->n_implication
; ++i
) {
607 struct pet_implication
*pi
= scop
->implications
[i
];
610 if (pi
->satisfied
!= implication
->satisfied
)
612 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
622 /* Store the concatenation of the implications of "scop1" and "scop2"
623 * in "scop", removing duplicates (i.e., implications in "scop2" that
624 * already appear in "scop1").
626 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
627 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
634 if (scop2
->n_implication
== 0) {
635 scop
->n_implication
= scop1
->n_implication
;
636 scop
->implications
= scop1
->implications
;
637 scop1
->n_implication
= 0;
638 scop1
->implications
= NULL
;
642 if (scop1
->n_implication
== 0) {
643 scop
->n_implication
= scop2
->n_implication
;
644 scop
->implications
= scop2
->implications
;
645 scop2
->n_implication
= 0;
646 scop2
->implications
= NULL
;
650 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
651 scop1
->n_implication
+ scop2
->n_implication
);
652 if (!scop
->implications
)
653 return pet_scop_free(scop
);
655 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
656 scop
->implications
[i
] = scop1
->implications
[i
];
657 scop1
->implications
[i
] = NULL
;
660 scop
->n_implication
= scop1
->n_implication
;
661 j
= scop1
->n_implication
;
662 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
665 known
= is_known_implication(scop
, scop2
->implications
[i
]);
667 return pet_scop_free(scop
);
670 scop
->implications
[j
++] = scop2
->implications
[i
];
671 scop2
->implications
[i
] = NULL
;
673 scop
->n_implication
= j
;
678 /* Combine the offset information of "scop1" and "scop2" into "scop".
680 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
681 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
683 if (scop1
->loc
!= &pet_loc_dummy
)
684 scop
= pet_scop_update_start_end_from_loc(scop
, scop1
->loc
);
685 if (scop2
->loc
!= &pet_loc_dummy
)
686 scop
= pet_scop_update_start_end_from_loc(scop
, scop2
->loc
);
690 /* Construct a pet_scop that contains the offset information,
691 * arrays, statements and skip information in "scop1" and "scop2".
693 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
694 struct pet_scop
*scop2
)
698 struct pet_scop
*scop
= NULL
;
700 if (!scop1
|| !scop2
)
703 if (scop1
->n_stmt
== 0) {
704 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
705 pet_scop_free(scop1
);
709 if (scop2
->n_stmt
== 0) {
710 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
711 pet_scop_free(scop2
);
715 space
= isl_set_get_space(scop1
->context
);
716 scop
= scop_alloc(space
, scop1
->n_stmt
+ scop2
->n_stmt
);
720 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
721 scop1
->n_array
+ scop2
->n_array
);
724 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
726 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
727 scop
->stmts
[i
] = scop1
->stmts
[i
];
728 scop1
->stmts
[i
] = NULL
;
731 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
732 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
733 scop2
->stmts
[i
] = NULL
;
736 for (i
= 0; i
< scop1
->n_array
; ++i
) {
737 scop
->arrays
[i
] = scop1
->arrays
[i
];
738 scop1
->arrays
[i
] = NULL
;
741 for (i
= 0; i
< scop2
->n_array
; ++i
) {
742 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
743 scop2
->arrays
[i
] = NULL
;
746 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
747 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
748 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
749 scop
= scop_combine_skips(scop
, scop1
, scop2
);
750 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
752 pet_scop_free(scop1
);
753 pet_scop_free(scop2
);
756 pet_scop_free(scop1
);
757 pet_scop_free(scop2
);
762 /* Apply the skip condition "skip" to "scop".
763 * That is, make sure "scop" is not executed when the condition holds.
765 * If "skip" is an affine expression, we add the conditions under
766 * which the expression is zero to the iteration domains.
767 * Otherwise, we add a filter on the variable attaining the value zero.
769 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
770 __isl_take isl_multi_pw_aff
*skip
)
779 is_aff
= multi_pw_aff_is_affine(skip
);
784 return pet_scop_filter(scop
, skip
, 0);
786 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
787 isl_multi_pw_aff_free(skip
);
788 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
789 scop
= pet_scop_restrict(scop
, zero
);
793 isl_multi_pw_aff_free(skip
);
794 return pet_scop_free(scop
);
797 /* Construct a pet_scop that contains the arrays, statements and
798 * skip information in "scop1" and "scop2", where the two scops
799 * are executed "in sequence". That is, breaks and continues
800 * in scop1 have an effect on scop2.
802 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
803 struct pet_scop
*scop2
)
805 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
806 scop2
= restrict_skip(scop2
,
807 pet_scop_get_skip(scop1
, pet_skip_now
));
808 return pet_scop_add(ctx
, scop1
, scop2
);
811 /* Construct a pet_scop that contains the arrays, statements and
812 * skip information in "scop1" and "scop2", where the two scops
813 * are executed "in parallel". That is, any break or continue
814 * in scop1 has no effect on scop2.
816 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
817 struct pet_scop
*scop2
)
819 return pet_scop_add(ctx
, scop1
, scop2
);
822 void *pet_implication_free(struct pet_implication
*implication
)
829 isl_map_free(implication
->extension
);
835 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
838 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
842 pet_loc_free(scop
->loc
);
843 isl_set_free(scop
->context
);
844 isl_set_free(scop
->context_value
);
846 for (i
= 0; i
< scop
->n_type
; ++i
)
847 pet_type_free(scop
->types
[i
]);
850 for (i
= 0; i
< scop
->n_array
; ++i
)
851 pet_array_free(scop
->arrays
[i
]);
854 for (i
= 0; i
< scop
->n_stmt
; ++i
)
855 pet_stmt_free(scop
->stmts
[i
]);
857 if (scop
->implications
)
858 for (i
= 0; i
< scop
->n_implication
; ++i
)
859 pet_implication_free(scop
->implications
[i
]);
860 free(scop
->implications
);
861 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
862 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
867 void pet_type_dump(struct pet_type
*type
)
872 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
875 void pet_implication_dump(struct pet_implication
*implication
)
880 fprintf(stderr
, "%d\n", implication
->satisfied
);
881 isl_map_dump(implication
->extension
);
884 void pet_scop_dump(struct pet_scop
*scop
)
887 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
892 isl_set_dump(scop
->context
);
893 isl_set_dump(scop
->context_value
);
894 for (i
= 0; i
< scop
->n_type
; ++i
)
895 pet_type_dump(scop
->types
[i
]);
896 for (i
= 0; i
< scop
->n_array
; ++i
)
897 pet_array_dump(scop
->arrays
[i
]);
898 for (i
= 0; i
< scop
->n_stmt
; ++i
)
899 pet_stmt_dump(scop
->stmts
[i
]);
900 for (i
= 0; i
< scop
->n_implication
; ++i
)
901 pet_implication_dump(scop
->implications
[i
]);
904 fprintf(stderr
, "skip\n");
905 isl_multi_pw_aff_dump(ext
->skip
[0]);
906 isl_multi_pw_aff_dump(ext
->skip
[1]);
910 /* Return 1 if the two pet_arrays are equivalent.
912 * We don't compare element_size as this may be target dependent.
914 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
916 if (!array1
|| !array2
)
919 if (!isl_set_is_equal(array1
->context
, array2
->context
))
921 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
923 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
925 if (array1
->value_bounds
&&
926 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
928 if (strcmp(array1
->element_type
, array2
->element_type
))
930 if (array1
->element_is_record
!= array2
->element_is_record
)
932 if (array1
->live_out
!= array2
->live_out
)
934 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
936 if (array1
->declared
!= array2
->declared
)
938 if (array1
->exposed
!= array2
->exposed
)
944 /* Return 1 if the two pet_stmts are equivalent.
946 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
950 if (!stmt1
|| !stmt2
)
953 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
955 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
957 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
959 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
961 if (stmt1
->n_arg
!= stmt2
->n_arg
)
963 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
964 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
971 /* Return 1 if the two pet_types are equivalent.
973 * We only compare the names of the types since the exact representation
974 * of the definition may depend on the version of clang being used.
976 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
978 if (!type1
|| !type2
)
981 if (strcmp(type1
->name
, type2
->name
))
987 /* Return 1 if the two pet_implications are equivalent.
989 int pet_implication_is_equal(struct pet_implication
*implication1
,
990 struct pet_implication
*implication2
)
992 if (!implication1
|| !implication2
)
995 if (implication1
->satisfied
!= implication2
->satisfied
)
997 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1003 /* Return 1 if the two pet_scops are equivalent.
1005 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1009 if (!scop1
|| !scop2
)
1012 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1014 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1017 if (scop1
->n_type
!= scop2
->n_type
)
1019 for (i
= 0; i
< scop1
->n_type
; ++i
)
1020 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1023 if (scop1
->n_array
!= scop2
->n_array
)
1025 for (i
= 0; i
< scop1
->n_array
; ++i
)
1026 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1029 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1031 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1032 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1035 if (scop1
->n_implication
!= scop2
->n_implication
)
1037 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1038 if (!pet_implication_is_equal(scop1
->implications
[i
],
1039 scop2
->implications
[i
]))
1045 /* Does the set "extent" reference a virtual array, i.e.,
1046 * one with user pointer equal to NULL?
1047 * A virtual array does not have any members.
1049 static int extent_is_virtual_array(__isl_keep isl_set
*extent
)
1054 if (!isl_set_has_tuple_id(extent
))
1056 if (isl_set_is_wrapping(extent
))
1058 id
= isl_set_get_tuple_id(extent
);
1059 is_virtual
= !isl_id_get_user(id
);
1065 /* Intersect the initial dimensions of "array" with "domain", provided
1066 * that "array" represents a virtual array.
1068 * If "array" is virtual, then We take the preimage of "domain"
1069 * over the projection of the extent of "array" onto its initial dimensions
1070 * and intersect this extent with the result.
1072 static struct pet_array
*virtual_array_intersect_domain_prefix(
1073 struct pet_array
*array
, __isl_take isl_set
*domain
)
1079 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1080 isl_set_free(domain
);
1084 space
= isl_set_get_space(array
->extent
);
1085 n
= isl_set_dim(domain
, isl_dim_set
);
1086 ma
= pet_prefix_projection(space
, n
);
1087 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1089 array
->extent
= isl_set_intersect(array
->extent
, domain
);
1091 return pet_array_free(array
);
1096 /* Intersect the initial dimensions of the domain of "stmt"
1099 * We take the preimage of "domain" over the projection of the
1100 * domain of "stmt" onto its initial dimensions and intersect
1101 * the domain of "stmt" with the result.
1103 static struct pet_stmt
*stmt_intersect_domain_prefix(struct pet_stmt
*stmt
,
1104 __isl_take isl_set
*domain
)
1113 space
= isl_set_get_space(stmt
->domain
);
1114 n
= isl_set_dim(domain
, isl_dim_set
);
1115 ma
= pet_prefix_projection(space
, n
);
1116 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1118 stmt
->domain
= isl_set_intersect(stmt
->domain
, domain
);
1120 return pet_stmt_free(stmt
);
1124 isl_set_free(domain
);
1125 return pet_stmt_free(stmt
);
1128 /* Intersect the initial dimensions of the domain of "implication"
1131 * We take the preimage of "domain" over the projection of the
1132 * domain of "implication" onto its initial dimensions and intersect
1133 * the domain of "implication" with the result.
1135 static struct pet_implication
*implication_intersect_domain_prefix(
1136 struct pet_implication
*implication
, __isl_take isl_set
*domain
)
1145 space
= isl_map_get_space(implication
->extension
);
1146 n
= isl_set_dim(domain
, isl_dim_set
);
1147 ma
= pet_prefix_projection(isl_space_domain(space
), n
);
1148 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1150 implication
->extension
=
1151 isl_map_intersect_domain(implication
->extension
, domain
);
1152 if (!implication
->extension
)
1153 return pet_implication_free(implication
);
1157 isl_set_free(domain
);
1158 return pet_implication_free(implication
);
1161 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1163 * The extents of the virtual arrays match the iteration domains,
1164 * so if the iteration domain changes, we need to change those extents too.
1166 struct pet_scop
*pet_scop_intersect_domain_prefix(struct pet_scop
*scop
,
1167 __isl_take isl_set
*domain
)
1174 for (i
= 0; i
< scop
->n_array
; ++i
) {
1175 scop
->arrays
[i
] = virtual_array_intersect_domain_prefix(
1176 scop
->arrays
[i
], isl_set_copy(domain
));
1177 if (!scop
->arrays
[i
])
1181 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1182 scop
->stmts
[i
] = stmt_intersect_domain_prefix(scop
->stmts
[i
],
1183 isl_set_copy(domain
));
1184 if (!scop
->stmts
[i
])
1188 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1189 scop
->implications
[i
] =
1190 implication_intersect_domain_prefix(scop
->implications
[i
],
1191 isl_set_copy(domain
));
1192 if (!scop
->implications
[i
])
1193 return pet_scop_free(scop
);
1196 isl_set_free(domain
);
1199 isl_set_free(domain
);
1200 return pet_scop_free(scop
);
1203 /* Prefix the schedule of "stmt" with an extra dimension with constant
1206 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1211 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1212 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1213 if (!stmt
->schedule
)
1214 return pet_stmt_free(stmt
);
1219 /* Prefix the schedules of all statements in "scop" with an extra
1220 * dimension with constant value "pos".
1222 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1229 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1230 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1231 if (!scop
->stmts
[i
])
1232 return pet_scop_free(scop
);
1238 /* Given a set with a parameter at "param_pos" that refers to the
1239 * iterator, "move" the iterator to the first set dimension.
1240 * That is, essentially equate the parameter to the first set dimension
1241 * and then project it out.
1243 * The first set dimension may however refer to a virtual iterator,
1244 * while the parameter refers to the "real" iterator.
1245 * We therefore need to take into account the affine expression "iv_map", which
1246 * expresses the real iterator in terms of the virtual iterator.
1247 * In particular, we equate the set dimension to the input of the map
1248 * and the parameter to the output of the map and then project out
1249 * everything we don't need anymore.
1251 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1252 int param_pos
, __isl_take isl_aff
*iv_map
)
1254 isl_map
*map
, *map2
;
1255 map
= isl_map_from_domain(set
);
1256 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1257 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1258 map2
= isl_map_from_aff(iv_map
);
1259 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1260 map
= isl_map_apply_range(map
, map2
);
1261 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1262 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1263 return isl_map_domain(map
);
1266 /* Data used in embed_access.
1267 * extend adds an iterator to the iteration domain (through precomposition).
1268 * iv_map expresses the real iterator in terms of the virtual iterator
1269 * var_id represents the induction variable of the corresponding loop
1271 struct pet_embed_access
{
1272 isl_multi_pw_aff
*extend
;
1277 /* Given an index expression, return an expression for the outer iterator.
1279 static __isl_give isl_aff
*index_outer_iterator(
1280 __isl_take isl_multi_pw_aff
*index
)
1283 isl_local_space
*ls
;
1285 space
= isl_multi_pw_aff_get_domain_space(index
);
1286 isl_multi_pw_aff_free(index
);
1288 ls
= isl_local_space_from_space(space
);
1289 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1292 /* Replace an index expression that references the new (outer) iterator variable
1293 * by one that references the corresponding (real) iterator.
1295 * The input index expression is of the form
1297 * { S[i',...] -> i[] }
1299 * where i' refers to the virtual iterator.
1301 * iv_map is of the form
1305 * Return the index expression
1307 * { S[i',...] -> [i] }
1309 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1310 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1315 aff
= index_outer_iterator(index
);
1316 space
= isl_aff_get_space(aff
);
1317 iv_map
= isl_aff_align_params(iv_map
, space
);
1318 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1320 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1323 /* Given an index expression "index" that refers to the (real) iterator
1324 * through the parameter at position "pos", plug in "iv_map", expressing
1325 * the real iterator in terms of the virtual (outer) iterator.
1327 * In particular, the index expression is of the form
1329 * [..., i, ...] -> { S[i',...] -> ... i ... }
1331 * where i refers to the real iterator and i' refers to the virtual iterator.
1333 * iv_map is of the form
1337 * Return the index expression
1339 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1342 * We first move the parameter to the input
1344 * [..., ...] -> { [i, i',...] -> ... i ... }
1348 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1350 * and then combine the two to obtain the desired result.
1352 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1353 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1355 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1358 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1359 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1360 isl_dim_param
, pos
, 1);
1362 space
= isl_space_map_from_set(space
);
1363 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1364 iv_map
= isl_aff_align_params(iv_map
, space
);
1365 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1366 ma
= isl_multi_aff_flat_range_product(
1367 isl_multi_aff_from_aff(iv_map
), ma
);
1368 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1373 /* Does the index expression "index" reference a virtual array, i.e.,
1374 * one with user pointer equal to NULL?
1375 * A virtual array does not have any members.
1377 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1382 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1384 if (isl_multi_pw_aff_range_is_wrapping(index
))
1386 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1387 is_virtual
= !isl_id_get_user(id
);
1393 /* Does the access relation "access" reference a virtual array, i.e.,
1394 * one with user pointer equal to NULL?
1395 * A virtual array does not have any members.
1397 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1402 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1404 if (isl_map_range_is_wrapping(access
))
1406 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1407 is_virtual
= !isl_id_get_user(id
);
1413 /* Embed the given index expression in an extra outer loop.
1414 * The domain of the index expression has already been updated.
1416 * If the access refers to the induction variable, then it is
1417 * turned into an access to the set of integers with index (and value)
1418 * equal to the induction variable.
1420 * If the accessed array is a virtual array (with user
1421 * pointer equal to NULL), as created by create_test_index,
1422 * then it is extended along with the domain of the index expression.
1424 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1425 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1427 isl_id
*array_id
= NULL
;
1430 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1431 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1432 if (array_id
== data
->var_id
) {
1433 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1434 } else if (index_is_virtual_array(index
)) {
1436 isl_multi_pw_aff
*mpa
;
1438 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1439 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1440 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1441 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1442 isl_id_copy(array_id
));
1444 isl_id_free(array_id
);
1446 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1447 isl_dim_param
, data
->var_id
);
1449 index
= index_internalize_iv(index
, pos
,
1450 isl_aff_copy(data
->iv_map
));
1451 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1452 isl_id_copy(data
->var_id
));
1457 /* Embed the given access relation in an extra outer loop.
1458 * The domain of the access relation has already been updated.
1460 * If the access refers to the induction variable, then it is
1461 * turned into an access to the set of integers with index (and value)
1462 * equal to the induction variable.
1464 * If the induction variable appears in the constraints (as a parameter),
1465 * then the parameter is equated to the newly introduced iteration
1466 * domain dimension and subsequently projected out.
1468 * Similarly, if the accessed array is a virtual array (with user
1469 * pointer equal to NULL), as created by create_test_index,
1470 * then it is extended along with the domain of the access.
1472 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1473 struct pet_embed_access
*data
)
1475 isl_id
*array_id
= NULL
;
1478 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1479 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1480 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
1481 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1482 access
= isl_map_equate(access
,
1483 isl_dim_in
, 0, isl_dim_out
, 0);
1484 if (array_id
== data
->var_id
)
1485 access
= isl_map_apply_range(access
,
1486 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1488 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1489 isl_id_copy(array_id
));
1491 isl_id_free(array_id
);
1493 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1495 isl_set
*set
= isl_map_wrap(access
);
1496 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1497 access
= isl_set_unwrap(set
);
1499 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1500 isl_id_copy(data
->var_id
));
1505 /* Given an access expression, embed the associated access relation and
1506 * index expression in an extra outer loop.
1508 * We first update the domains to insert the extra dimension and
1509 * then update the access relation and index expression to take
1510 * into account the mapping "iv_map" from virtual iterator
1513 static __isl_give pet_expr
*embed_access(__isl_take pet_expr
*expr
, void *user
)
1515 struct pet_embed_access
*data
= user
;
1517 expr
= pet_expr_cow(expr
);
1518 expr
= pet_expr_access_update_domain(expr
, data
->extend
);
1522 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
1523 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
1524 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1525 return pet_expr_free(expr
);
1530 /* Embed all access subexpressions of "expr" in an extra loop.
1531 * "extend" inserts an outer loop iterator in the iteration domains
1532 * (through precomposition).
1533 * "iv_map" expresses the real iterator in terms of the virtual iterator
1534 * "var_id" represents the induction variable.
1536 static __isl_give pet_expr
*expr_embed(__isl_take pet_expr
*expr
,
1537 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1538 __isl_keep isl_id
*var_id
)
1540 struct pet_embed_access data
=
1541 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1543 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1544 isl_aff_free(iv_map
);
1545 isl_multi_pw_aff_free(extend
);
1549 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1550 * "dom" and schedule "sched". "var_id" represents the induction variable
1551 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1552 * That is, it expresses the iterator that some of the parameters in "stmt"
1553 * may refer to in terms of the iterator used in "dom" and
1554 * the domain of "sched".
1556 * The iteration domain and schedule of the statement are updated
1557 * according to the iteration domain and schedule of the new loop.
1558 * If stmt->domain is a wrapped map, then the iteration domain
1559 * is the domain of this map, so we need to be careful to adjust
1562 * If the induction variable appears in the constraints (as a parameter)
1563 * of the current iteration domain or the schedule of the statement,
1564 * then the parameter is equated to the newly introduced iteration
1565 * domain dimension and subsequently projected out.
1567 * Finally, all access relations are updated based on the extra loop.
1569 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1570 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1571 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1577 isl_multi_pw_aff
*extend
;
1582 if (isl_set_is_wrapping(stmt
->domain
)) {
1587 map
= isl_set_unwrap(stmt
->domain
);
1588 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1589 ran_dim
= isl_space_range(isl_map_get_space(map
));
1590 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1591 isl_set_universe(ran_dim
));
1592 map
= isl_map_flat_domain_product(ext
, map
);
1593 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1594 isl_id_copy(stmt_id
));
1595 dim
= isl_space_domain(isl_map_get_space(map
));
1596 stmt
->domain
= isl_map_wrap(map
);
1598 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1599 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1601 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1602 isl_id_copy(stmt_id
));
1603 dim
= isl_set_get_space(stmt
->domain
);
1606 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1608 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1609 isl_aff_copy(iv_map
));
1611 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1612 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1613 isl_dim_in
, stmt_id
);
1615 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1617 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1618 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1619 stmt
->schedule
= isl_set_unwrap(set
);
1622 dim
= isl_space_map_from_set(dim
);
1623 extend
= isl_multi_pw_aff_identity(dim
);
1624 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
1625 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
1626 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
1627 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1628 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1629 isl_multi_pw_aff_copy(extend
),
1630 isl_aff_copy(iv_map
), var_id
);
1631 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1634 isl_id_free(var_id
);
1636 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1638 return pet_stmt_free(stmt
);
1639 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1640 return pet_stmt_free(stmt
);
1644 isl_map_free(sched
);
1645 isl_aff_free(iv_map
);
1646 isl_id_free(var_id
);
1650 /* Embed the given pet_array in an extra outer loop with iteration domain
1651 * "dom". "var_id" represents the induction variable of the loop.
1652 * "iv_map" maps a possibly virtual iterator to the real iterator.
1654 * This embedding only has an effect on virtual arrays (those with
1655 * user pointer equal to NULL), which need to be extended along with
1656 * the iteration domain.
1658 * The induction variable may also appears in the extent (as a parameter)
1659 * due to being introduced by array_restrict.
1660 * If so, then the parameter is equated to the newly introduced iteration
1661 * domain dimension and subsequently projected out.
1663 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1664 __isl_take isl_set
*dom
, __isl_take isl_aff
*iv_map
,
1665 __isl_take isl_id
*var_id
)
1668 isl_id
*array_id
= NULL
;
1672 if (!extent_is_virtual_array(array
->extent
)) {
1674 isl_aff_free(iv_map
);
1675 isl_id_free(var_id
);
1679 array_id
= isl_set_get_tuple_id(array
->extent
);
1680 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1681 pos
= isl_set_find_dim_by_id(array
->extent
, isl_dim_param
, var_id
);
1683 array
->extent
= internalize_iv(array
->extent
, pos
,
1684 isl_aff_copy(iv_map
));
1685 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1687 isl_aff_free(iv_map
);
1688 isl_id_free(var_id
);
1690 return pet_array_free(array
);
1698 /* Update the context with respect to an embedding into a loop
1699 * with iteration domain "dom" and induction variable "id".
1700 * "iv_map" expresses the real iterator (parameter "id") in terms
1701 * of a possibly virtual iterator (used in "dom").
1703 * If the current context is independent of "id", we don't need
1705 * Otherwise, a parameter value is invalid for the embedding if
1706 * any of the corresponding iterator values is invalid.
1707 * That is, a parameter value is valid only if all the corresponding
1708 * iterator values are valid.
1709 * We therefore compute the set of parameters
1711 * forall i in dom : valid (i)
1715 * not exists i in dom : not valid(i)
1719 * not exists i in dom \ valid(i)
1721 * Before we subtract valid(i) from dom, we first need to substitute
1722 * the real iterator for the virtual iterator.
1724 * If there are any unnamed parameters in "dom", then we consider
1725 * a parameter value to be valid if it is valid for any value of those
1726 * unnamed parameters. They are therefore projected out at the end.
1728 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1729 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
1730 __isl_keep isl_id
*id
)
1735 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1739 context
= isl_set_from_params(context
);
1740 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1741 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1742 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1743 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
1744 context
= isl_set_preimage_multi_aff(context
, ma
);
1745 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1746 context
= isl_set_params(context
);
1747 context
= isl_set_complement(context
);
1748 context
= pet_nested_remove_from_set(context
);
1752 /* Update the implication with respect to an embedding into a loop
1753 * with iteration domain "dom".
1755 * Since embed_access extends virtual arrays along with the domain
1756 * of the access, we need to do the same with domain and range
1757 * of the implication. Since the original implication is only valid
1758 * within a given iteration of the loop, the extended implication
1759 * maps the extra array dimension corresponding to the extra loop
1762 static struct pet_implication
*pet_implication_embed(
1763 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1771 map
= isl_set_identity(dom
);
1772 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1773 map
= isl_map_flat_product(map
, implication
->extension
);
1774 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1775 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1776 implication
->extension
= map
;
1777 if (!implication
->extension
)
1778 return pet_implication_free(implication
);
1786 /* Embed all statements and arrays in "scop" in an extra outer loop
1787 * with iteration domain "dom" and schedule "sched".
1788 * "id" represents the induction variable of the loop.
1789 * "iv_map" maps a possibly virtual iterator to the real iterator.
1790 * That is, it expresses the iterator that some of the parameters in "scop"
1791 * may refer to in terms of the iterator used in "dom" and
1792 * the domain of "sched".
1794 * Any skip conditions within the loop have no effect outside of the loop.
1795 * The caller is responsible for making sure skip[pet_skip_later] has been
1796 * taken into account.
1798 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1799 __isl_take isl_aff
*sched
, __isl_take isl_aff
*iv_map
,
1800 __isl_take isl_id
*id
)
1805 sched_map
= isl_map_from_aff(sched
);
1810 pet_scop_reset_skip(scop
, pet_skip_now
);
1811 pet_scop_reset_skip(scop
, pet_skip_later
);
1813 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1817 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1818 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1819 isl_set_copy(dom
), isl_map_copy(sched_map
),
1820 isl_aff_copy(iv_map
), isl_id_copy(id
));
1821 if (!scop
->stmts
[i
])
1825 for (i
= 0; i
< scop
->n_array
; ++i
) {
1826 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1828 isl_aff_copy(iv_map
), isl_id_copy(id
));
1829 if (!scop
->arrays
[i
])
1833 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1834 scop
->implications
[i
] =
1835 pet_implication_embed(scop
->implications
[i
],
1837 if (!scop
->implications
[i
])
1842 isl_map_free(sched_map
);
1843 isl_aff_free(iv_map
);
1848 isl_map_free(sched_map
);
1849 isl_aff_free(iv_map
);
1851 return pet_scop_free(scop
);
1854 /* Add extra conditions on the parameters to the iteration domain of "stmt".
1856 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1857 __isl_take isl_set
*cond
)
1862 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1867 return pet_stmt_free(stmt
);
1870 /* Add extra conditions on the parameters to the extent of "array",
1871 * provided it is a virtual array.
1873 static struct pet_array
*array_restrict(struct pet_array
*array
,
1874 __isl_take isl_set
*cond
)
1878 if (!extent_is_virtual_array(array
->extent
)) {
1883 array
->extent
= isl_set_intersect_params(array
->extent
, cond
);
1885 return pet_array_free(array
);
1893 /* Add extra conditions to scop->skip[type].
1895 * The new skip condition only holds if it held before
1896 * and the condition is true. It does not hold if it did not hold
1897 * before or the condition is false.
1899 * The skip condition is assumed to be an affine expression.
1901 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1902 enum pet_skip type
, __isl_keep isl_set
*cond
)
1904 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1910 if (!ext
->skip
[type
])
1913 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1914 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1915 isl_error_internal
, "can only restrict affine skips",
1916 return pet_scop_free(scop
));
1918 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1919 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1920 cond
= isl_set_copy(cond
);
1921 cond
= isl_set_from_params(cond
);
1922 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1923 skip
= indicator_function(cond
, dom
);
1924 isl_multi_pw_aff_free(ext
->skip
[type
]);
1925 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1926 if (!ext
->skip
[type
])
1927 return pet_scop_free(scop
);
1932 /* Add extra conditions on the parameters to all iteration domains
1933 * virtual array extents and skip conditions.
1935 * A parameter value is valid for the result if it was valid
1936 * for the original scop and satisfies "cond" or if it does
1937 * not satisfy "cond" as in this case the scop is not executed
1938 * and the original constraints on the parameters are irrelevant.
1940 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1941 __isl_take isl_set
*cond
)
1945 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1946 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1951 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1952 scop
->context
= isl_set_union(scop
->context
,
1953 isl_set_complement(isl_set_copy(cond
)));
1954 scop
->context
= isl_set_coalesce(scop
->context
);
1955 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1959 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1960 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1961 isl_set_copy(cond
));
1962 if (!scop
->stmts
[i
])
1966 for (i
= 0; i
< scop
->n_array
; ++i
) {
1967 scop
->arrays
[i
] = array_restrict(scop
->arrays
[i
],
1968 isl_set_copy(cond
));
1969 if (!scop
->arrays
[i
])
1977 return pet_scop_free(scop
);
1980 /* Insert an argument expression corresponding to "test" in front
1981 * of the list of arguments described by *n_arg and *args.
1983 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1984 __isl_keep isl_multi_pw_aff
*test
)
1987 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1993 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1998 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
2001 for (i
= 0; i
< *n_arg
; ++i
)
2002 ext
[1 + i
] = (*args
)[i
];
2007 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
2014 /* Look through the applications in "scop" for any that can be
2015 * applied to the filter expressed by "map" and "satisified".
2016 * If there is any, then apply it to "map" and return the result.
2017 * Otherwise, return "map".
2018 * "id" is the identifier of the virtual array.
2020 * We only introduce at most one implication for any given virtual array,
2021 * so we can apply the implication and return as soon as we find one.
2023 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
2024 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
2028 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2029 struct pet_implication
*pi
= scop
->implications
[i
];
2032 if (pi
->satisfied
!= satisfied
)
2034 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
2039 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
2045 /* Is the filter expressed by "test" and "satisfied" implied
2046 * by filter "pos" on "domain", with filter "expr", taking into
2047 * account the implications of "scop"?
2049 * For filter on domain implying that expressed by "test" and "satisfied",
2050 * the filter needs to be an access to the same (virtual) array as "test" and
2051 * the filter value needs to be equal to "satisfied".
2052 * Moreover, the filter access relation, possibly extended by
2053 * the implications in "scop" needs to contain "test".
2055 static int implies_filter(struct pet_scop
*scop
,
2056 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
2057 __isl_keep isl_map
*test
, int satisfied
)
2059 isl_id
*test_id
, *arg_id
;
2066 if (expr
->type
!= pet_expr_access
)
2068 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
2069 arg_id
= pet_expr_access_get_id(expr
);
2070 isl_id_free(arg_id
);
2071 isl_id_free(test_id
);
2072 if (test_id
!= arg_id
)
2074 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
2075 is_int
= isl_val_is_int(val
);
2077 s
= isl_val_get_num_si(val
);
2086 implied
= isl_map_copy(expr
->acc
.access
);
2087 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
2088 is_subset
= isl_map_is_subset(test
, implied
);
2089 isl_map_free(implied
);
2094 /* Is the filter expressed by "test" and "satisfied" implied
2095 * by any of the filters on the domain of "stmt", taking into
2096 * account the implications of "scop"?
2098 static int filter_implied(struct pet_scop
*scop
,
2099 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2107 if (!scop
|| !stmt
|| !test
)
2109 if (scop
->n_implication
== 0)
2111 if (stmt
->n_arg
== 0)
2114 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
2115 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
2118 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2119 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
2120 test_map
, satisfied
);
2121 if (implied
< 0 || implied
)
2125 isl_map_free(test_map
);
2126 isl_map_free(domain
);
2130 /* Make the statement "stmt" depend on the value of "test"
2131 * being equal to "satisfied" by adjusting stmt->domain.
2133 * The domain of "test" corresponds to the (zero or more) outer dimensions
2134 * of the iteration domain.
2136 * We first extend "test" to apply to the entire iteration domain and
2137 * then check if the filter that we are about to add is implied
2138 * by any of the current filters, possibly taking into account
2139 * the implications in "scop". If so, we leave "stmt" untouched and return.
2141 * Otherwise, we insert an argument corresponding to a read to "test"
2142 * from the iteration domain of "stmt" in front of the list of arguments.
2143 * We also insert a corresponding output dimension in the wrapped
2144 * map contained in stmt->domain, with value set to "satisfied".
2146 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
2147 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2153 isl_pw_multi_aff
*pma
;
2154 isl_multi_aff
*add_dom
;
2156 isl_local_space
*ls
;
2162 space
= pet_stmt_get_space(stmt
);
2163 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
2164 space
= isl_space_from_domain(space
);
2165 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
2166 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
2167 ls
= isl_local_space_from_space(isl_space_domain(space
));
2168 for (i
= 0; i
< n_test_dom
; ++i
) {
2170 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
2172 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
2174 isl_local_space_free(ls
);
2175 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
2177 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
2181 isl_multi_pw_aff_free(test
);
2185 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2186 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
2188 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
2190 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
2193 isl_multi_pw_aff_free(test
);
2196 isl_multi_pw_aff_free(test
);
2197 return pet_stmt_free(stmt
);
2200 /* Does "scop" have a skip condition of the given "type"?
2202 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
2204 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2208 return ext
->skip
[type
] != NULL
;
2211 /* Does "scop" have a skip condition of the given "type" that
2212 * is an affine expression?
2214 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
2216 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2220 if (!ext
->skip
[type
])
2222 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2225 /* Does "scop" have a skip condition of the given "type" that
2226 * is not an affine expression?
2228 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2230 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2235 if (!ext
->skip
[type
])
2237 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2243 /* Does "scop" have a skip condition of the given "type" that
2244 * is affine and holds on the entire domain?
2246 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2248 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2254 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2255 if (is_aff
< 0 || !is_aff
)
2258 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2259 set
= isl_pw_aff_non_zero_set(pa
);
2260 is_univ
= isl_set_plain_is_universe(set
);
2266 /* Replace scop->skip[type] by "skip".
2268 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2269 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2271 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2276 isl_multi_pw_aff_free(ext
->skip
[type
]);
2277 ext
->skip
[type
] = skip
;
2281 isl_multi_pw_aff_free(skip
);
2282 return pet_scop_free(scop
);
2285 /* Return a copy of scop->skip[type].
2287 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2290 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2295 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2298 /* Assuming scop->skip[type] is an affine expression,
2299 * return the constraints on the parameters for which the skip condition
2302 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2305 isl_multi_pw_aff
*skip
;
2308 skip
= pet_scop_get_skip(scop
, type
);
2309 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2310 isl_multi_pw_aff_free(skip
);
2311 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2314 /* Return the identifier of the variable that is accessed by
2315 * the skip condition of the given type.
2317 * The skip condition is assumed not to be an affine condition.
2319 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2322 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2327 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2330 /* Return an access pet_expr corresponding to the skip condition
2331 * of the given type.
2333 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2336 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2339 /* Drop the the skip condition scop->skip[type].
2341 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2343 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2348 isl_multi_pw_aff_free(ext
->skip
[type
]);
2349 ext
->skip
[type
] = NULL
;
2352 /* Make the skip condition (if any) depend on the value of "test" being
2353 * equal to "satisfied".
2355 * We only support the case where the original skip condition is universal,
2356 * i.e., where skipping is unconditional, and where satisfied == 1.
2357 * In this case, the skip condition is changed to skip only when
2358 * "test" is equal to one.
2360 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2361 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2367 if (!pet_scop_has_skip(scop
, type
))
2371 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2373 return pet_scop_free(scop
);
2374 if (satisfied
&& is_univ
) {
2375 isl_multi_pw_aff
*skip
;
2376 skip
= isl_multi_pw_aff_copy(test
);
2377 scop
= pet_scop_set_skip(scop
, type
, skip
);
2381 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2382 "skip expression cannot be filtered",
2383 return pet_scop_free(scop
));
2389 /* Make all statements in "scop" depend on the value of "test"
2390 * being equal to "satisfied" by adjusting their domains.
2392 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2393 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2397 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2398 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2403 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2404 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2405 isl_multi_pw_aff_copy(test
), satisfied
);
2406 if (!scop
->stmts
[i
])
2410 isl_multi_pw_aff_free(test
);
2413 isl_multi_pw_aff_free(test
);
2414 return pet_scop_free(scop
);
2417 /* Add all parameters in "expr" to "space" and return the result.
2419 static __isl_give isl_space
*expr_collect_params(__isl_keep pet_expr
*expr
,
2420 __isl_take isl_space
*space
)
2426 for (i
= 0; i
< expr
->n_arg
; ++i
)
2427 space
= expr_collect_params(expr
->args
[i
], space
);
2429 if (expr
->type
== pet_expr_access
)
2430 space
= isl_space_align_params(space
,
2431 isl_map_get_space(expr
->acc
.access
));
2435 pet_expr_free(expr
);
2436 return isl_space_free(space
);
2439 /* Add all parameters in "stmt" to "space" and return the result.
2441 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2442 __isl_take isl_space
*space
)
2447 return isl_space_free(space
);
2449 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2450 space
= isl_space_align_params(space
,
2451 isl_map_get_space(stmt
->schedule
));
2452 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2453 space
= expr_collect_params(stmt
->args
[i
], space
);
2454 space
= expr_collect_params(stmt
->body
, space
);
2459 /* Add all parameters in "array" to "space" and return the result.
2461 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2462 __isl_take isl_space
*space
)
2465 return isl_space_free(space
);
2467 space
= isl_space_align_params(space
,
2468 isl_set_get_space(array
->context
));
2469 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2474 /* Add all parameters in "scop" to "space" and return the result.
2476 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2477 __isl_take isl_space
*space
)
2482 return isl_space_free(space
);
2484 for (i
= 0; i
< scop
->n_array
; ++i
)
2485 space
= array_collect_params(scop
->arrays
[i
], space
);
2487 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2488 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2493 /* Add all parameters in "space" to the domain, schedule and
2494 * all access relations in "stmt".
2496 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2497 __isl_take isl_space
*space
)
2504 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2505 isl_space_copy(space
));
2506 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2507 isl_space_copy(space
));
2509 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2510 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2511 isl_space_copy(space
));
2515 stmt
->body
= pet_expr_align_params(stmt
->body
, isl_space_copy(space
));
2517 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2520 isl_space_free(space
);
2523 isl_space_free(space
);
2524 return pet_stmt_free(stmt
);
2527 /* Add all parameters in "space" to "array".
2529 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2530 __isl_take isl_space
*space
)
2535 array
->context
= isl_set_align_params(array
->context
,
2536 isl_space_copy(space
));
2537 array
->extent
= isl_set_align_params(array
->extent
,
2538 isl_space_copy(space
));
2539 if (array
->value_bounds
) {
2540 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2541 isl_space_copy(space
));
2542 if (!array
->value_bounds
)
2546 if (!array
->context
|| !array
->extent
)
2549 isl_space_free(space
);
2552 isl_space_free(space
);
2553 return pet_array_free(array
);
2556 /* Add all parameters in "space" to "scop".
2558 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2559 __isl_take isl_space
*space
)
2566 for (i
= 0; i
< scop
->n_array
; ++i
) {
2567 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2568 isl_space_copy(space
));
2569 if (!scop
->arrays
[i
])
2573 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2574 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2575 isl_space_copy(space
));
2576 if (!scop
->stmts
[i
])
2580 isl_space_free(space
);
2583 isl_space_free(space
);
2584 return pet_scop_free(scop
);
2587 /* Update all isl_sets and isl_maps in "scop" such that they all
2588 * have the same parameters.
2590 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2597 space
= isl_set_get_space(scop
->context
);
2598 space
= scop_collect_params(scop
, space
);
2600 scop
->context
= isl_set_align_params(scop
->context
,
2601 isl_space_copy(space
));
2602 scop
= scop_propagate_params(scop
, space
);
2604 if (scop
&& !scop
->context
)
2605 return pet_scop_free(scop
);
2610 /* Add the access relation of the access expression "expr" to "accesses" and
2611 * return the result.
2612 * The domain of the access relation is intersected with "domain".
2613 * If "tag" is set, then the access relation is tagged with
2614 * the corresponding reference identifier.
2616 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2617 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2621 access
= pet_expr_access_get_may_access(expr
);
2622 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
2624 access
= pet_expr_tag_access(expr
, access
);
2625 return isl_union_map_add_map(accesses
, access
);
2628 /* Add all read access relations (if "read" is set) and/or all write
2629 * access relations (if "write" is set) to "accesses" and return the result.
2630 * The domains of the access relations are intersected with "domain".
2631 * If "tag" is set, then the access relations are tagged with
2632 * the corresponding reference identifiers.
2634 * If "must" is set, then we only add the accesses that are definitely
2635 * performed. Otherwise, we add all potential accesses.
2636 * In particular, if the access has any arguments, then if "must" is
2637 * set we currently skip the access completely. If "must" is not set,
2638 * we project out the values of the access arguments.
2640 static __isl_give isl_union_map
*expr_collect_accesses(
2641 __isl_keep pet_expr
*expr
, int read
, int write
, int must
, int tag
,
2642 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2649 return isl_union_map_free(accesses
);
2651 for (i
= 0; i
< expr
->n_arg
; ++i
)
2652 accesses
= expr_collect_accesses(expr
->args
[i
],
2653 read
, write
, must
, tag
, accesses
, domain
);
2655 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2656 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
2657 (!must
|| expr
->n_arg
== 0)) {
2658 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
2664 /* Collect and return all read access relations (if "read" is set)
2665 * and/or all write access relations (if "write" is set) in "stmt".
2666 * If "tag" is set, then the access relations are tagged with
2667 * the corresponding reference identifiers.
2668 * If "kill" is set, then "stmt" is a kill statement and we simply
2669 * add the argument of the kill operation.
2671 * If "must" is set, then we only add the accesses that are definitely
2672 * performed. Otherwise, we add all potential accesses.
2673 * In particular, if the statement has any arguments, then if "must" is
2674 * set we currently skip the statement completely. If "must" is not set,
2675 * we project out the values of the statement arguments.
2677 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2678 int read
, int write
, int kill
, int must
, int tag
,
2679 __isl_take isl_space
*dim
)
2681 isl_union_map
*accesses
;
2687 accesses
= isl_union_map_empty(dim
);
2689 if (must
&& stmt
->n_arg
> 0)
2692 domain
= isl_set_copy(stmt
->domain
);
2693 if (isl_set_is_wrapping(domain
))
2694 domain
= isl_map_domain(isl_set_unwrap(domain
));
2697 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
2700 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
2701 must
, tag
, accesses
, domain
);
2702 isl_set_free(domain
);
2707 /* Is "stmt" an assignment statement?
2709 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2713 if (stmt
->body
->type
!= pet_expr_op
)
2715 return stmt
->body
->op
== pet_op_assign
;
2718 /* Is "stmt" a kill statement?
2720 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2724 if (stmt
->body
->type
!= pet_expr_op
)
2726 return stmt
->body
->op
== pet_op_kill
;
2729 /* Is "stmt" an assume statement?
2731 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2735 return pet_expr_is_assume(stmt
->body
);
2738 /* Compute a mapping from all arrays (of structs) in scop
2739 * to their innermost arrays.
2741 * In particular, for each array of a primitive type, the result
2742 * contains the identity mapping on that array.
2743 * For each array involving member accesses, the result
2744 * contains a mapping from the elements of any intermediate array of structs
2745 * to all corresponding elements of the innermost nested arrays.
2747 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
2750 isl_union_map
*to_inner
;
2752 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2754 for (i
= 0; i
< scop
->n_array
; ++i
) {
2755 struct pet_array
*array
= scop
->arrays
[i
];
2757 isl_map
*map
, *gist
;
2759 if (array
->element_is_record
)
2762 map
= isl_set_identity(isl_set_copy(array
->extent
));
2764 set
= isl_map_domain(isl_map_copy(map
));
2765 gist
= isl_map_copy(map
);
2766 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2767 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2769 while (set
&& isl_set_is_wrapping(set
)) {
2773 id
= isl_set_get_tuple_id(set
);
2774 wrapped
= isl_set_unwrap(set
);
2775 wrapped
= isl_map_domain_map(wrapped
);
2776 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2777 map
= isl_map_apply_domain(map
, wrapped
);
2778 set
= isl_map_domain(isl_map_copy(map
));
2779 gist
= isl_map_copy(map
);
2780 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2781 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2791 /* Collect and return all read access relations (if "read" is set)
2792 * and/or all write access relations (if "write" is set) in "scop".
2793 * If "kill" is set, then we only add the arguments of kill operations.
2794 * If "must" is set, then we only add the accesses that are definitely
2795 * performed. Otherwise, we add all potential accesses.
2796 * If "tag" is set, then the access relations are tagged with
2797 * the corresponding reference identifiers.
2798 * For accesses to structures, the returned access relation accesses
2799 * all individual fields in the structures.
2801 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2802 int read
, int write
, int kill
, int must
, int tag
)
2805 isl_union_map
*accesses
;
2806 isl_union_set
*arrays
;
2807 isl_union_map
*to_inner
;
2812 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2814 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2815 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2816 isl_union_map
*accesses_i
;
2819 if (kill
&& !pet_stmt_is_kill(stmt
))
2822 space
= isl_set_get_space(scop
->context
);
2823 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
2825 accesses
= isl_union_map_union(accesses
, accesses_i
);
2828 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2829 for (i
= 0; i
< scop
->n_array
; ++i
) {
2830 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2831 arrays
= isl_union_set_add_set(arrays
, extent
);
2833 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2835 to_inner
= compute_to_inner(scop
);
2836 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2841 /* Collect all potential read access relations.
2843 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2845 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
2848 /* Collect all potential write access relations.
2850 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2852 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
2855 /* Collect all definite write access relations.
2857 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2859 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
2862 /* Collect all definite kill access relations.
2864 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2866 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
2869 /* Collect all tagged potential read access relations.
2871 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2872 struct pet_scop
*scop
)
2874 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
2877 /* Collect all tagged potential write access relations.
2879 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2880 struct pet_scop
*scop
)
2882 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
2885 /* Collect all tagged definite write access relations.
2887 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2888 struct pet_scop
*scop
)
2890 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
2893 /* Collect all tagged definite kill access relations.
2895 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2896 struct pet_scop
*scop
)
2898 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
2901 /* Collect and return the union of iteration domains in "scop".
2903 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2907 isl_union_set
*domain
;
2912 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2914 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2915 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2916 domain
= isl_union_set_add_set(domain
, domain_i
);
2922 /* Collect and return the schedules of the statements in "scop".
2923 * The range is normalized to the maximal number of scheduling
2926 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2929 isl_map
*schedule_i
;
2930 isl_union_map
*schedule
;
2931 int depth
, max_depth
= 0;
2936 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2938 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2939 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2940 if (depth
> max_depth
)
2944 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2945 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2946 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2947 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2949 for (j
= depth
; j
< max_depth
; ++j
)
2950 schedule_i
= isl_map_fix_si(schedule_i
,
2952 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2958 /* Add a reference identifier to all access expressions in "stmt".
2959 * "n_ref" points to an integer that contains the sequence number
2960 * of the next reference.
2962 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2969 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2970 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2972 return pet_stmt_free(stmt
);
2975 stmt
->body
= pet_expr_add_ref_ids(stmt
->body
, n_ref
);
2977 return pet_stmt_free(stmt
);
2982 /* Add a reference identifier to all access expressions in "scop".
2984 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2993 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2994 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2995 if (!scop
->stmts
[i
])
2996 return pet_scop_free(scop
);
3002 /* Reset the user pointer on all parameter ids in "array".
3004 static struct pet_array
*array_anonymize(struct pet_array
*array
)
3009 array
->context
= isl_set_reset_user(array
->context
);
3010 array
->extent
= isl_set_reset_user(array
->extent
);
3011 if (!array
->context
|| !array
->extent
)
3012 return pet_array_free(array
);
3017 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3019 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
3028 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
3029 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
3030 if (!stmt
->domain
|| !stmt
->schedule
)
3031 return pet_stmt_free(stmt
);
3033 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3034 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
3036 return pet_stmt_free(stmt
);
3039 stmt
->body
= pet_expr_anonymize(stmt
->body
);
3041 return pet_stmt_free(stmt
);
3046 /* Reset the user pointer on the tuple ids and all parameter ids
3049 static struct pet_implication
*implication_anonymize(
3050 struct pet_implication
*implication
)
3055 implication
->extension
= isl_map_reset_user(implication
->extension
);
3056 if (!implication
->extension
)
3057 return pet_implication_free(implication
);
3062 /* Reset the user pointer on all parameter and tuple ids in "scop".
3064 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
3071 scop
->context
= isl_set_reset_user(scop
->context
);
3072 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
3073 if (!scop
->context
|| !scop
->context_value
)
3074 return pet_scop_free(scop
);
3076 for (i
= 0; i
< scop
->n_array
; ++i
) {
3077 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
3078 if (!scop
->arrays
[i
])
3079 return pet_scop_free(scop
);
3082 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3083 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3084 if (!scop
->stmts
[i
])
3085 return pet_scop_free(scop
);
3088 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3089 scop
->implications
[i
] =
3090 implication_anonymize(scop
->implications
[i
]);
3091 if (!scop
->implications
[i
])
3092 return pet_scop_free(scop
);
3098 /* Compute the gist of the iteration domain and all access relations
3099 * of "stmt" based on the constraints on the parameters specified by "context"
3100 * and the constraints on the values of nested accesses specified
3101 * by "value_bounds".
3103 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3104 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3112 domain
= isl_set_copy(stmt
->domain
);
3113 if (stmt
->n_arg
> 0)
3114 domain
= isl_map_domain(isl_set_unwrap(domain
));
3116 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3118 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3119 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
3120 domain
, value_bounds
);
3125 stmt
->body
= pet_expr_gist(stmt
->body
, domain
, value_bounds
);
3129 isl_set_free(domain
);
3131 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
3132 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3133 if (stmt
->n_arg
> 0)
3134 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
3136 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3138 return pet_stmt_free(stmt
);
3142 isl_set_free(domain
);
3143 return pet_stmt_free(stmt
);
3146 /* Compute the gist of the extent of the array
3147 * based on the constraints on the parameters specified by "context".
3149 static struct pet_array
*array_gist(struct pet_array
*array
,
3150 __isl_keep isl_set
*context
)
3155 array
->extent
= isl_set_gist_params(array
->extent
,
3156 isl_set_copy(context
));
3158 return pet_array_free(array
);
3163 /* Compute the gist of all sets and relations in "scop"
3164 * based on the constraints on the parameters specified by "scop->context"
3165 * and the constraints on the values of nested accesses specified
3166 * by "value_bounds".
3168 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3169 __isl_keep isl_union_map
*value_bounds
)
3176 scop
->context
= isl_set_coalesce(scop
->context
);
3178 return pet_scop_free(scop
);
3180 for (i
= 0; i
< scop
->n_array
; ++i
) {
3181 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3182 if (!scop
->arrays
[i
])
3183 return pet_scop_free(scop
);
3186 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3187 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3189 if (!scop
->stmts
[i
])
3190 return pet_scop_free(scop
);
3196 /* Intersect the context of "scop" with "context".
3197 * To ensure that we don't introduce any unnamed parameters in
3198 * the context of "scop", we first remove the unnamed parameters
3201 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3202 __isl_take isl_set
*context
)
3207 context
= pet_nested_remove_from_set(context
);
3208 scop
->context
= isl_set_intersect(scop
->context
, context
);
3210 return pet_scop_free(scop
);
3214 isl_set_free(context
);
3215 return pet_scop_free(scop
);
3218 /* Drop the current context of "scop". That is, replace the context
3219 * by a universal set.
3221 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3228 space
= isl_set_get_space(scop
->context
);
3229 isl_set_free(scop
->context
);
3230 scop
->context
= isl_set_universe(space
);
3232 return pet_scop_free(scop
);
3237 /* Append "array" to the arrays of "scop".
3239 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3240 struct pet_array
*array
)
3243 struct pet_array
**arrays
;
3245 if (!array
|| !scop
)
3248 ctx
= isl_set_get_ctx(scop
->context
);
3249 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3253 scop
->arrays
= arrays
;
3254 scop
->arrays
[scop
->n_array
] = array
;
3259 pet_array_free(array
);
3260 return pet_scop_free(scop
);
3263 /* Create an index expression for an access to a virtual array
3264 * representing the result of a condition.
3265 * Unlike other accessed data, the id of the array is NULL as
3266 * there is no ValueDecl in the program corresponding to the virtual
3268 * The index expression is created as an identity mapping on "space".
3269 * That is, the dimension of the array is the same as that of "space".
3270 * Currently, the array starts out as a scalar, but grows along with the
3271 * statement writing to the array in pet_scop_embed.
3273 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
3279 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
3280 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
3281 space
= isl_space_map_from_set(space
);
3282 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3283 return isl_multi_pw_aff_identity(space
);
3286 /* Add an array with the given extent to the list
3287 * of arrays in "scop" and return the extended pet_scop.
3288 * Specifically, the extent is determined by the image of "domain"
3290 * "int_size" is the number of bytes needed to represent values of type "int".
3291 * The array is marked as attaining values 0 and 1 only and
3292 * as each element being assigned at most once.
3294 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
3295 __isl_take isl_set
*domain
, __isl_take isl_multi_pw_aff
*index
,
3300 struct pet_array
*array
;
3303 if (!scop
|| !domain
|| !index
)
3306 ctx
= isl_multi_pw_aff_get_ctx(index
);
3307 array
= isl_calloc_type(ctx
, struct pet_array
);
3311 access
= isl_map_from_multi_pw_aff(index
);
3312 access
= isl_map_intersect_domain(access
, domain
);
3313 array
->extent
= isl_map_range(access
);
3314 space
= isl_space_params_alloc(ctx
, 0);
3315 array
->context
= isl_set_universe(space
);
3316 space
= isl_space_set_alloc(ctx
, 0, 1);
3317 array
->value_bounds
= isl_set_universe(space
);
3318 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
3320 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
3322 array
->element_type
= strdup("int");
3323 array
->element_size
= int_size
;
3324 array
->uniquely_defined
= 1;
3326 if (!array
->extent
|| !array
->context
)
3327 array
= pet_array_free(array
);
3329 scop
= pet_scop_add_array(scop
, array
);
3333 isl_set_free(domain
);
3334 isl_multi_pw_aff_free(index
);
3335 return pet_scop_free(scop
);
3338 /* Create and return an implication on filter values equal to "satisfied"
3339 * with extension "map".
3341 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3345 struct pet_implication
*implication
;
3349 ctx
= isl_map_get_ctx(map
);
3350 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3354 implication
->extension
= map
;
3355 implication
->satisfied
= satisfied
;
3363 /* Add an implication on filter values equal to "satisfied"
3364 * with extension "map" to "scop".
3366 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3367 __isl_take isl_map
*map
, int satisfied
)
3370 struct pet_implication
*implication
;
3371 struct pet_implication
**implications
;
3373 implication
= new_implication(map
, satisfied
);
3374 if (!scop
|| !implication
)
3377 ctx
= isl_set_get_ctx(scop
->context
);
3378 implications
= isl_realloc_array(ctx
, scop
->implications
,
3379 struct pet_implication
*,
3380 scop
->n_implication
+ 1);
3383 scop
->implications
= implications
;
3384 scop
->implications
[scop
->n_implication
] = implication
;
3385 scop
->n_implication
++;
3389 pet_implication_free(implication
);
3390 return pet_scop_free(scop
);
3393 /* Given an access expression, check if it is data dependent.
3394 * If so, set *found and abort the search.
3396 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
3400 if (pet_expr_get_n_arg(expr
) > 0) {
3408 /* Does "scop" contain any data dependent accesses?
3410 * Check the body of each statement for such accesses.
3412 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3420 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3421 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
3422 &is_data_dependent
, &found
);
3423 if (r
< 0 && !found
)
3432 /* Does "scop" contain and data dependent conditions?
3434 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3441 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3442 if (scop
->stmts
[i
]->n_arg
> 0)
3448 /* Keep track of the "input" file inside the (extended) "scop".
3450 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3452 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3462 /* Print the original code corresponding to "scop" to printer "p".
3464 * pet_scop_print_original can only be called from
3465 * a pet_transform_C_source callback. This means that the input
3466 * file is stored in the extended scop and that the printer prints
3469 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3470 __isl_take isl_printer
*p
)
3472 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3474 unsigned start
, end
;
3477 return isl_printer_free(p
);
3480 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3481 "no input file stored in scop",
3482 return isl_printer_free(p
));
3484 output
= isl_printer_get_file(p
);
3486 return isl_printer_free(p
);
3488 start
= pet_loc_get_start(scop
->loc
);
3489 end
= pet_loc_get_end(scop
->loc
);
3490 if (copy(ext
->input
, output
, start
, end
) < 0)
3491 return isl_printer_free(p
);