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>
44 /* pet_scop with extra information that is used during parsing and printing.
46 * In particular, we keep track of conditions under which we want
47 * to skip the rest of the current loop iteration (skip[pet_skip_now])
48 * and of conditions under which we want to skip subsequent
49 * loop iterations (skip[pet_skip_later]).
51 * The conditions are represented as index expressions defined
52 * over a zero-dimensional domain. The index expression is either
53 * a boolean affine expression or an access to a variable, which
54 * is assumed to attain values zero and one. The condition holds
55 * if the variable has value one or if the affine expression
56 * has value one (typically for only part of the parameter space).
58 * A missing condition (skip[type] == NULL) means that we don't want
61 * Additionally, we keep track of the original input file
62 * inside pet_transform_C_source.
67 isl_multi_pw_aff
*skip
[2];
71 /* Construct a pet_stmt with given line number and statement
72 * number from a pet_expr.
73 * The initial iteration domain is the zero-dimensional universe.
74 * The name of the domain is given by "label" if it is non-NULL.
75 * Otherwise, the name is constructed as S_<id>.
76 * The domains of all access relations are modified to refer
77 * to the statement iteration domain.
79 struct pet_stmt
*pet_stmt_from_pet_expr(isl_ctx
*ctx
, int line
,
80 __isl_take isl_id
*label
, int id
, struct pet_expr
*expr
)
82 struct pet_stmt
*stmt
;
86 isl_multi_pw_aff
*add_name
;
92 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
96 dim
= isl_space_set_alloc(ctx
, 0, 0);
98 dim
= isl_space_set_tuple_id(dim
, isl_dim_set
, label
);
100 snprintf(name
, sizeof(name
), "S_%d", id
);
101 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, name
);
103 dom
= isl_set_universe(isl_space_copy(dim
));
104 sched
= isl_map_from_domain(isl_set_copy(dom
));
106 dim
= isl_space_from_domain(dim
);
107 add_name
= isl_multi_pw_aff_zero(dim
);
108 expr
= pet_expr_update_domain(expr
, add_name
);
112 stmt
->schedule
= sched
;
115 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
116 return pet_stmt_free(stmt
);
125 void *pet_stmt_free(struct pet_stmt
*stmt
)
132 isl_set_free(stmt
->domain
);
133 isl_map_free(stmt
->schedule
);
134 pet_expr_free(stmt
->body
);
136 for (i
= 0; i
< stmt
->n_arg
; ++i
)
137 pet_expr_free(stmt
->args
[i
]);
144 /* Return the iteration space of "stmt".
146 * If the statement has arguments, then stmt->domain is a wrapped map
147 * mapping the iteration domain to the values of the arguments
148 * for which this statement is executed.
149 * In this case, we need to extract the domain space of this wrapped map.
151 __isl_give isl_space
*pet_stmt_get_space(struct pet_stmt
*stmt
)
158 space
= isl_set_get_space(stmt
->domain
);
159 if (isl_space_is_wrapping(space
))
160 space
= isl_space_domain(isl_space_unwrap(space
));
165 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
172 fprintf(stderr
, "%*s%d\n", indent
, "", stmt
->line
);
173 fprintf(stderr
, "%*s", indent
, "");
174 isl_set_dump(stmt
->domain
);
175 fprintf(stderr
, "%*s", indent
, "");
176 isl_map_dump(stmt
->schedule
);
177 pet_expr_dump_with_indent(stmt
->body
, indent
);
178 for (i
= 0; i
< stmt
->n_arg
; ++i
)
179 pet_expr_dump_with_indent(stmt
->args
[i
], indent
+ 2);
182 void pet_stmt_dump(struct pet_stmt
*stmt
)
187 /* Allocate a new pet_type with the given "name" and "definition".
189 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
190 const char *definition
)
192 struct pet_type
*type
;
194 type
= isl_alloc_type(ctx
, struct pet_type
);
198 type
->name
= strdup(name
);
199 type
->definition
= strdup(definition
);
201 if (!type
->name
|| !type
->definition
)
202 return pet_type_free(type
);
207 /* Free "type" and return NULL.
209 struct pet_type
*pet_type_free(struct pet_type
*type
)
215 free(type
->definition
);
221 struct pet_array
*pet_array_free(struct pet_array
*array
)
226 isl_set_free(array
->context
);
227 isl_set_free(array
->extent
);
228 isl_set_free(array
->value_bounds
);
229 free(array
->element_type
);
235 void pet_array_dump(struct pet_array
*array
)
240 isl_set_dump(array
->context
);
241 isl_set_dump(array
->extent
);
242 isl_set_dump(array
->value_bounds
);
243 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
244 array
->element_is_record
? " element-is-record" : "",
245 array
->live_out
? " live-out" : "");
248 /* Alloc a pet_scop structure, with extra room for information that
249 * is only used during parsing.
251 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
253 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
256 /* Construct a pet_scop with room for n statements.
258 static struct pet_scop
*scop_alloc(isl_ctx
*ctx
, int n
)
261 struct pet_scop
*scop
;
263 scop
= pet_scop_alloc(ctx
);
267 space
= isl_space_params_alloc(ctx
, 0);
268 scop
->context
= isl_set_universe(isl_space_copy(space
));
269 scop
->context_value
= isl_set_universe(space
);
270 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
271 if (!scop
->context
|| !scop
->stmts
)
272 return pet_scop_free(scop
);
279 struct pet_scop
*pet_scop_empty(isl_ctx
*ctx
)
281 return scop_alloc(ctx
, 0);
284 /* Update "context" with respect to the valid parameter values for "access".
286 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
287 __isl_take isl_set
*context
)
289 context
= isl_set_intersect(context
,
290 isl_map_params(isl_map_copy(access
)));
294 /* Update "context" with respect to the valid parameter values for "expr".
296 * If "expr" represents a conditional operator, then a parameter value
297 * needs to be valid for the condition and for at least one of the
298 * remaining two arguments.
299 * If the condition is an affine expression, then we can be a bit more specific.
300 * The parameter then has to be valid for the second argument for
301 * non-zero accesses and valid for the third argument for zero accesses.
303 static __isl_give isl_set
*expr_extract_context(struct pet_expr
*expr
,
304 __isl_take isl_set
*context
)
308 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
310 isl_set
*context1
, *context2
;
312 is_aff
= pet_expr_is_affine(expr
->args
[0]);
316 context
= expr_extract_context(expr
->args
[0], context
);
317 context1
= expr_extract_context(expr
->args
[1],
318 isl_set_copy(context
));
319 context2
= expr_extract_context(expr
->args
[2], context
);
325 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
326 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
327 zero_set
= isl_map_params(access
);
328 context1
= isl_set_subtract(context1
,
329 isl_set_copy(zero_set
));
330 context2
= isl_set_intersect(context2
, zero_set
);
333 context
= isl_set_union(context1
, context2
);
334 context
= isl_set_coalesce(context
);
339 for (i
= 0; i
< expr
->n_arg
; ++i
)
340 context
= expr_extract_context(expr
->args
[i
], context
);
342 if (expr
->type
== pet_expr_access
)
343 context
= access_extract_context(expr
->acc
.access
, context
);
347 isl_set_free(context
);
351 /* Update "context" with respect to the valid parameter values for "stmt".
353 * If the statement is an assume statement with an affine expression,
354 * then intersect "context" with that expression.
355 * Otherwise, intersect "context" with the contexts of the expressions
358 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
359 __isl_take isl_set
*context
)
363 if (pet_stmt_is_assume(stmt
) &&
364 pet_expr_is_affine(stmt
->body
->args
[0])) {
365 isl_multi_pw_aff
*index
;
369 index
= stmt
->body
->args
[0]->acc
.index
;
370 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
371 cond
= isl_set_params(isl_pw_aff_non_zero_set(pa
));
372 return isl_set_intersect(context
, cond
);
375 for (i
= 0; i
< stmt
->n_arg
; ++i
)
376 context
= expr_extract_context(stmt
->args
[i
], context
);
378 context
= expr_extract_context(stmt
->body
, context
);
383 /* Construct a pet_scop that contains the given pet_stmt.
385 struct pet_scop
*pet_scop_from_pet_stmt(isl_ctx
*ctx
, struct pet_stmt
*stmt
)
387 struct pet_scop
*scop
;
392 scop
= scop_alloc(ctx
, 1);
396 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
400 scop
->stmts
[0] = stmt
;
409 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
410 * does it represent an affine expression?
412 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
416 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
423 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
425 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
426 __isl_take isl_set
*dom
)
429 pa
= isl_set_indicator_function(set
);
430 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
434 /* Return "lhs || rhs", defined on the shared definition domain.
436 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
437 __isl_take isl_pw_aff
*rhs
)
442 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
443 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
444 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
445 isl_pw_aff_non_zero_set(rhs
));
446 cond
= isl_set_coalesce(cond
);
447 return indicator_function(cond
, dom
);
450 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
451 * ext may be equal to either ext1 or ext2.
453 * The two skips that need to be combined are assumed to be affine expressions.
455 * We need to skip in ext if we need to skip in either ext1 or ext2.
456 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
458 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
459 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
462 isl_pw_aff
*skip
, *skip1
, *skip2
;
466 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
468 if (!ext1
->skip
[type
]) {
471 ext
->skip
[type
] = ext2
->skip
[type
];
472 ext2
->skip
[type
] = NULL
;
475 if (!ext2
->skip
[type
]) {
478 ext
->skip
[type
] = ext1
->skip
[type
];
479 ext1
->skip
[type
] = NULL
;
483 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
484 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
485 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
486 isl_error_internal
, "can only combine affine skips",
489 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
490 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
491 skip
= pw_aff_or(skip1
, skip2
);
492 isl_multi_pw_aff_free(ext1
->skip
[type
]);
493 ext1
->skip
[type
] = NULL
;
494 isl_multi_pw_aff_free(ext2
->skip
[type
]);
495 ext2
->skip
[type
] = NULL
;
496 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
497 if (!ext
->skip
[type
])
502 pet_scop_free(&ext
->scop
);
506 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
507 * where type takes on the values pet_skip_now and pet_skip_later.
508 * scop may be equal to either scop1 or scop2.
510 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
511 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
513 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
514 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
515 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
517 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
518 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
522 /* Update scop->start and scop->end to include the region from "start"
523 * to "end". In particular, if scop->end == 0, then "scop" does not
524 * have any offset information yet and we simply take the information
525 * from "start" and "end". Otherwise, we update the fields if the
526 * region from "start" to "end" is not already included.
528 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
529 unsigned start
, unsigned end
)
533 if (scop
->end
== 0) {
537 if (start
< scop
->start
)
546 /* Does "implication" appear in the list of implications of "scop"?
548 static int is_known_implication(struct pet_scop
*scop
,
549 struct pet_implication
*implication
)
553 for (i
= 0; i
< scop
->n_implication
; ++i
) {
554 struct pet_implication
*pi
= scop
->implications
[i
];
557 if (pi
->satisfied
!= implication
->satisfied
)
559 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
569 /* Store the concatenation of the implications of "scop1" and "scop2"
570 * in "scop", removing duplicates (i.e., implications in "scop2" that
571 * already appear in "scop1").
573 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
574 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
581 if (scop2
->n_implication
== 0) {
582 scop
->n_implication
= scop1
->n_implication
;
583 scop
->implications
= scop1
->implications
;
584 scop1
->n_implication
= 0;
585 scop1
->implications
= NULL
;
589 if (scop1
->n_implication
== 0) {
590 scop
->n_implication
= scop2
->n_implication
;
591 scop
->implications
= scop2
->implications
;
592 scop2
->n_implication
= 0;
593 scop2
->implications
= NULL
;
597 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
598 scop1
->n_implication
+ scop2
->n_implication
);
599 if (!scop
->implications
)
600 return pet_scop_free(scop
);
602 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
603 scop
->implications
[i
] = scop1
->implications
[i
];
604 scop1
->implications
[i
] = NULL
;
607 scop
->n_implication
= scop1
->n_implication
;
608 j
= scop1
->n_implication
;
609 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
612 known
= is_known_implication(scop
, scop2
->implications
[i
]);
614 return pet_scop_free(scop
);
617 scop
->implications
[j
++] = scop2
->implications
[i
];
618 scop2
->implications
[i
] = NULL
;
620 scop
->n_implication
= j
;
625 /* Combine the offset information of "scop1" and "scop2" into "scop".
627 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
628 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
631 scop
= pet_scop_update_start_end(scop
,
632 scop1
->start
, scop1
->end
);
634 scop
= pet_scop_update_start_end(scop
,
635 scop2
->start
, scop2
->end
);
639 /* Construct a pet_scop that contains the offset information,
640 * arrays, statements and skip information in "scop1" and "scop2".
642 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
643 struct pet_scop
*scop2
)
646 struct pet_scop
*scop
= NULL
;
648 if (!scop1
|| !scop2
)
651 if (scop1
->n_stmt
== 0) {
652 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
653 pet_scop_free(scop1
);
657 if (scop2
->n_stmt
== 0) {
658 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
659 pet_scop_free(scop2
);
663 scop
= scop_alloc(ctx
, scop1
->n_stmt
+ scop2
->n_stmt
);
667 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
668 scop1
->n_array
+ scop2
->n_array
);
671 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
673 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
674 scop
->stmts
[i
] = scop1
->stmts
[i
];
675 scop1
->stmts
[i
] = NULL
;
678 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
679 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
680 scop2
->stmts
[i
] = NULL
;
683 for (i
= 0; i
< scop1
->n_array
; ++i
) {
684 scop
->arrays
[i
] = scop1
->arrays
[i
];
685 scop1
->arrays
[i
] = NULL
;
688 for (i
= 0; i
< scop2
->n_array
; ++i
) {
689 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
690 scop2
->arrays
[i
] = NULL
;
693 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
694 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
695 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
696 scop
= scop_combine_skips(scop
, scop1
, scop2
);
697 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
699 pet_scop_free(scop1
);
700 pet_scop_free(scop2
);
703 pet_scop_free(scop1
);
704 pet_scop_free(scop2
);
709 /* Apply the skip condition "skip" to "scop".
710 * That is, make sure "scop" is not executed when the condition holds.
712 * If "skip" is an affine expression, we add the conditions under
713 * which the expression is zero to the iteration domains.
714 * Otherwise, we add a filter on the variable attaining the value zero.
716 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
717 __isl_take isl_multi_pw_aff
*skip
)
726 is_aff
= multi_pw_aff_is_affine(skip
);
731 return pet_scop_filter(scop
, skip
, 0);
733 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
734 isl_multi_pw_aff_free(skip
);
735 zero
= isl_set_params(isl_pw_aff_zero_set(pa
));
736 scop
= pet_scop_restrict(scop
, zero
);
740 isl_multi_pw_aff_free(skip
);
741 return pet_scop_free(scop
);
744 /* Construct a pet_scop that contains the arrays, statements and
745 * skip information in "scop1" and "scop2", where the two scops
746 * are executed "in sequence". That is, breaks and continues
747 * in scop1 have an effect on scop2.
749 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
750 struct pet_scop
*scop2
)
752 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
753 scop2
= restrict_skip(scop2
,
754 pet_scop_get_skip(scop1
, pet_skip_now
));
755 return pet_scop_add(ctx
, scop1
, scop2
);
758 /* Construct a pet_scop that contains the arrays, statements and
759 * skip information in "scop1" and "scop2", where the two scops
760 * are executed "in parallel". That is, any break or continue
761 * in scop1 has no effect on scop2.
763 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
764 struct pet_scop
*scop2
)
766 return pet_scop_add(ctx
, scop1
, scop2
);
769 void *pet_implication_free(struct pet_implication
*implication
)
776 isl_map_free(implication
->extension
);
782 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
785 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
789 isl_set_free(scop
->context
);
790 isl_set_free(scop
->context_value
);
792 for (i
= 0; i
< scop
->n_type
; ++i
)
793 pet_type_free(scop
->types
[i
]);
796 for (i
= 0; i
< scop
->n_array
; ++i
)
797 pet_array_free(scop
->arrays
[i
]);
800 for (i
= 0; i
< scop
->n_stmt
; ++i
)
801 pet_stmt_free(scop
->stmts
[i
]);
803 if (scop
->implications
)
804 for (i
= 0; i
< scop
->n_implication
; ++i
)
805 pet_implication_free(scop
->implications
[i
]);
806 free(scop
->implications
);
807 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
808 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
813 void pet_type_dump(struct pet_type
*type
)
818 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
821 void pet_implication_dump(struct pet_implication
*implication
)
826 fprintf(stderr
, "%d\n", implication
->satisfied
);
827 isl_map_dump(implication
->extension
);
830 void pet_scop_dump(struct pet_scop
*scop
)
833 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
838 isl_set_dump(scop
->context
);
839 isl_set_dump(scop
->context_value
);
840 for (i
= 0; i
< scop
->n_type
; ++i
)
841 pet_type_dump(scop
->types
[i
]);
842 for (i
= 0; i
< scop
->n_array
; ++i
)
843 pet_array_dump(scop
->arrays
[i
]);
844 for (i
= 0; i
< scop
->n_stmt
; ++i
)
845 pet_stmt_dump(scop
->stmts
[i
]);
846 for (i
= 0; i
< scop
->n_implication
; ++i
)
847 pet_implication_dump(scop
->implications
[i
]);
850 fprintf(stderr
, "skip\n");
851 isl_multi_pw_aff_dump(ext
->skip
[0]);
852 isl_multi_pw_aff_dump(ext
->skip
[1]);
856 /* Return 1 if the two pet_arrays are equivalent.
858 * We don't compare element_size as this may be target dependent.
860 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
862 if (!array1
|| !array2
)
865 if (!isl_set_is_equal(array1
->context
, array2
->context
))
867 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
869 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
871 if (array1
->value_bounds
&&
872 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
874 if (strcmp(array1
->element_type
, array2
->element_type
))
876 if (array1
->element_is_record
!= array2
->element_is_record
)
878 if (array1
->live_out
!= array2
->live_out
)
880 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
882 if (array1
->declared
!= array2
->declared
)
884 if (array1
->exposed
!= array2
->exposed
)
890 /* Return 1 if the two pet_stmts are equivalent.
892 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
896 if (!stmt1
|| !stmt2
)
899 if (stmt1
->line
!= stmt2
->line
)
901 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
903 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
905 if (!pet_expr_is_equal(stmt1
->body
, stmt2
->body
))
907 if (stmt1
->n_arg
!= stmt2
->n_arg
)
909 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
910 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
917 /* Return 1 if the two pet_types are equivalent.
919 * We only compare the names of the types since the exact representation
920 * of the definition may depend on the version of clang being used.
922 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
924 if (!type1
|| !type2
)
927 if (strcmp(type1
->name
, type2
->name
))
933 /* Return 1 if the two pet_implications are equivalent.
935 int pet_implication_is_equal(struct pet_implication
*implication1
,
936 struct pet_implication
*implication2
)
938 if (!implication1
|| !implication2
)
941 if (implication1
->satisfied
!= implication2
->satisfied
)
943 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
949 /* Return 1 if the two pet_scops are equivalent.
951 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
955 if (!scop1
|| !scop2
)
958 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
960 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
963 if (scop1
->n_type
!= scop2
->n_type
)
965 for (i
= 0; i
< scop1
->n_type
; ++i
)
966 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
969 if (scop1
->n_array
!= scop2
->n_array
)
971 for (i
= 0; i
< scop1
->n_array
; ++i
)
972 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
975 if (scop1
->n_stmt
!= scop2
->n_stmt
)
977 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
978 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
981 if (scop1
->n_implication
!= scop2
->n_implication
)
983 for (i
= 0; i
< scop1
->n_implication
; ++i
)
984 if (!pet_implication_is_equal(scop1
->implications
[i
],
985 scop2
->implications
[i
]))
991 /* Prefix the schedule of "stmt" with an extra dimension with constant
994 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
999 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1000 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1001 if (!stmt
->schedule
)
1002 return pet_stmt_free(stmt
);
1007 /* Prefix the schedules of all statements in "scop" with an extra
1008 * dimension with constant value "pos".
1010 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1017 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1018 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1019 if (!scop
->stmts
[i
])
1020 return pet_scop_free(scop
);
1026 /* Given a set with a parameter at "param_pos" that refers to the
1027 * iterator, "move" the iterator to the first set dimension.
1028 * That is, essentially equate the parameter to the first set dimension
1029 * and then project it out.
1031 * The first set dimension may however refer to a virtual iterator,
1032 * while the parameter refers to the "real" iterator.
1033 * We therefore need to take into account the affine expression "iv_map", which
1034 * expresses the real iterator in terms of the virtual iterator.
1035 * In particular, we equate the set dimension to the input of the map
1036 * and the parameter to the output of the map and then project out
1037 * everything we don't need anymore.
1039 static __isl_give isl_set
*internalize_iv(__isl_take isl_set
*set
,
1040 int param_pos
, __isl_take isl_aff
*iv_map
)
1042 isl_map
*map
, *map2
;
1043 map
= isl_map_from_domain(set
);
1044 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
1045 map
= isl_map_equate(map
, isl_dim_in
, 0, isl_dim_out
, 0);
1046 map2
= isl_map_from_aff(iv_map
);
1047 map2
= isl_map_align_params(map2
, isl_map_get_space(map
));
1048 map
= isl_map_apply_range(map
, map2
);
1049 map
= isl_map_equate(map
, isl_dim_param
, param_pos
, isl_dim_out
, 0);
1050 map
= isl_map_project_out(map
, isl_dim_param
, param_pos
, 1);
1051 return isl_map_domain(map
);
1054 /* Data used in embed_access.
1055 * extend adds an iterator to the iteration domain (through precomposition).
1056 * iv_map expresses the real iterator in terms of the virtual iterator
1057 * var_id represents the induction variable of the corresponding loop
1059 struct pet_embed_access
{
1060 isl_multi_pw_aff
*extend
;
1065 /* Given an index expression, return an expression for the outer iterator.
1067 static __isl_give isl_aff
*index_outer_iterator(
1068 __isl_take isl_multi_pw_aff
*index
)
1071 isl_local_space
*ls
;
1073 space
= isl_multi_pw_aff_get_domain_space(index
);
1074 isl_multi_pw_aff_free(index
);
1076 ls
= isl_local_space_from_space(space
);
1077 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1080 /* Replace an index expression that references the new (outer) iterator variable
1081 * by one that references the corresponding (real) iterator.
1083 * The input index expression is of the form
1085 * { S[i',...] -> i[] }
1087 * where i' refers to the virtual iterator.
1089 * iv_map is of the form
1093 * Return the index expression
1095 * { S[i',...] -> [i] }
1097 static __isl_give isl_multi_pw_aff
*replace_by_iterator(
1098 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_aff
*iv_map
)
1103 aff
= index_outer_iterator(index
);
1104 space
= isl_aff_get_space(aff
);
1105 iv_map
= isl_aff_align_params(iv_map
, space
);
1106 aff
= isl_aff_pullback_aff(iv_map
, aff
);
1108 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1111 /* Given an index expression "index" that refers to the (real) iterator
1112 * through the parameter at position "pos", plug in "iv_map", expressing
1113 * the real iterator in terms of the virtual (outer) iterator.
1115 * In particular, the index expression is of the form
1117 * [..., i, ...] -> { S[i',...] -> ... i ... }
1119 * where i refers to the real iterator and i' refers to the virtual iterator.
1121 * iv_map is of the form
1125 * Return the index expression
1127 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1130 * We first move the parameter to the input
1132 * [..., ...] -> { [i, i',...] -> ... i ... }
1136 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1138 * and then combine the two to obtain the desired result.
1140 static __isl_give isl_multi_pw_aff
*index_internalize_iv(
1141 __isl_take isl_multi_pw_aff
*index
, int pos
, __isl_take isl_aff
*iv_map
)
1143 isl_space
*space
= isl_multi_pw_aff_get_domain_space(index
);
1146 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
1147 index
= isl_multi_pw_aff_move_dims(index
, isl_dim_in
, 0,
1148 isl_dim_param
, pos
, 1);
1150 space
= isl_space_map_from_set(space
);
1151 ma
= isl_multi_aff_identity(isl_space_copy(space
));
1152 iv_map
= isl_aff_align_params(iv_map
, space
);
1153 iv_map
= isl_aff_pullback_aff(iv_map
, isl_multi_aff_get_aff(ma
, 0));
1154 ma
= isl_multi_aff_flat_range_product(
1155 isl_multi_aff_from_aff(iv_map
), ma
);
1156 index
= isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
1161 /* Does the index expression "index" reference a virtual array, i.e.,
1162 * one with user pointer equal to NULL?
1163 * A virtual array does not have any members.
1165 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff
*index
)
1170 if (!isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1172 if (isl_multi_pw_aff_range_is_wrapping(index
))
1174 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1175 is_virtual
= !isl_id_get_user(id
);
1181 /* Does the access relation "access" reference a virtual array, i.e.,
1182 * one with user pointer equal to NULL?
1183 * A virtual array does not have any members.
1185 static int access_is_virtual_array(__isl_keep isl_map
*access
)
1190 if (!isl_map_has_tuple_id(access
, isl_dim_out
))
1192 if (isl_map_range_is_wrapping(access
))
1194 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1195 is_virtual
= !isl_id_get_user(id
);
1201 /* Embed the given index expression in an extra outer loop.
1202 * The domain of the index expression has already been updated.
1204 * If the access refers to the induction variable, then it is
1205 * turned into an access to the set of integers with index (and value)
1206 * equal to the induction variable.
1208 * If the accessed array is a virtual array (with user
1209 * pointer equal to NULL), as created by create_test_index,
1210 * then it is extended along with the domain of the index expression.
1212 static __isl_give isl_multi_pw_aff
*embed_index_expression(
1213 __isl_take isl_multi_pw_aff
*index
, struct pet_embed_access
*data
)
1215 isl_id
*array_id
= NULL
;
1218 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
))
1219 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1220 if (array_id
== data
->var_id
) {
1221 index
= replace_by_iterator(index
, isl_aff_copy(data
->iv_map
));
1222 } else if (index_is_virtual_array(index
)) {
1224 isl_multi_pw_aff
*mpa
;
1226 aff
= index_outer_iterator(isl_multi_pw_aff_copy(index
));
1227 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1228 index
= isl_multi_pw_aff_flat_range_product(mpa
, index
);
1229 index
= isl_multi_pw_aff_set_tuple_id(index
, isl_dim_out
,
1230 isl_id_copy(array_id
));
1232 isl_id_free(array_id
);
1234 pos
= isl_multi_pw_aff_find_dim_by_id(index
,
1235 isl_dim_param
, data
->var_id
);
1237 index
= index_internalize_iv(index
, pos
,
1238 isl_aff_copy(data
->iv_map
));
1239 index
= isl_multi_pw_aff_set_dim_id(index
, isl_dim_in
, 0,
1240 isl_id_copy(data
->var_id
));
1245 /* Embed the given access relation in an extra outer loop.
1246 * The domain of the access relation has already been updated.
1248 * If the access refers to the induction variable, then it is
1249 * turned into an access to the set of integers with index (and value)
1250 * equal to the induction variable.
1252 * If the induction variable appears in the constraints (as a parameter),
1253 * then the parameter is equated to the newly introduced iteration
1254 * domain dimension and subsequently projected out.
1256 * Similarly, if the accessed array is a virtual array (with user
1257 * pointer equal to NULL), as created by create_test_index,
1258 * then it is extended along with the domain of the access.
1260 static __isl_give isl_map
*embed_access_relation(__isl_take isl_map
*access
,
1261 struct pet_embed_access
*data
)
1263 isl_id
*array_id
= NULL
;
1266 if (isl_map_has_tuple_id(access
, isl_dim_out
))
1267 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1268 if (array_id
== data
->var_id
|| access_is_virtual_array(access
)) {
1269 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1270 access
= isl_map_equate(access
,
1271 isl_dim_in
, 0, isl_dim_out
, 0);
1272 if (array_id
== data
->var_id
)
1273 access
= isl_map_apply_range(access
,
1274 isl_map_from_aff(isl_aff_copy(data
->iv_map
)));
1276 access
= isl_map_set_tuple_id(access
, isl_dim_out
,
1277 isl_id_copy(array_id
));
1279 isl_id_free(array_id
);
1281 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, data
->var_id
);
1283 isl_set
*set
= isl_map_wrap(access
);
1284 set
= internalize_iv(set
, pos
, isl_aff_copy(data
->iv_map
));
1285 access
= isl_set_unwrap(set
);
1287 access
= isl_map_set_dim_id(access
, isl_dim_in
, 0,
1288 isl_id_copy(data
->var_id
));
1293 /* Given an access expression, embed the associated access relation and
1294 * index expression in an extra outer loop.
1296 * We first update the domains to insert the extra dimension and
1297 * then update the access relation and index expression to take
1298 * into account the mapping "iv_map" from virtual iterator
1301 static struct pet_expr
*embed_access(struct pet_expr
*expr
, void *user
)
1303 struct pet_embed_access
*data
= user
;
1305 expr
= pet_expr_access_update_domain(expr
, data
->extend
);
1309 expr
->acc
.access
= embed_access_relation(expr
->acc
.access
, data
);
1310 expr
->acc
.index
= embed_index_expression(expr
->acc
.index
, data
);
1311 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1312 return pet_expr_free(expr
);
1317 /* Embed all access subexpressions of "expr" in an extra loop.
1318 * "extend" inserts an outer loop iterator in the iteration domains
1319 * (through precomposition).
1320 * "iv_map" expresses the real iterator in terms of the virtual iterator
1321 * "var_id" represents the induction variable.
1323 static struct pet_expr
*expr_embed(struct pet_expr
*expr
,
1324 __isl_take isl_multi_pw_aff
*extend
, __isl_take isl_aff
*iv_map
,
1325 __isl_keep isl_id
*var_id
)
1327 struct pet_embed_access data
=
1328 { .extend
= extend
, .iv_map
= iv_map
, .var_id
= var_id
};
1330 expr
= pet_expr_map_access(expr
, &embed_access
, &data
);
1331 isl_aff_free(iv_map
);
1332 isl_multi_pw_aff_free(extend
);
1336 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1337 * "dom" and schedule "sched". "var_id" represents the induction variable
1338 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1339 * That is, it expresses the iterator that some of the parameters in "stmt"
1340 * may refer to in terms of the iterator used in "dom" and
1341 * the domain of "sched".
1343 * The iteration domain and schedule of the statement are updated
1344 * according to the iteration domain and schedule of the new loop.
1345 * If stmt->domain is a wrapped map, then the iteration domain
1346 * is the domain of this map, so we need to be careful to adjust
1349 * If the induction variable appears in the constraints (as a parameter)
1350 * of the current iteration domain or the schedule of the statement,
1351 * then the parameter is equated to the newly introduced iteration
1352 * domain dimension and subsequently projected out.
1354 * Finally, all access relations are updated based on the extra loop.
1356 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1357 __isl_take isl_set
*dom
, __isl_take isl_map
*sched
,
1358 __isl_take isl_aff
*iv_map
, __isl_take isl_id
*var_id
)
1364 isl_multi_pw_aff
*extend
;
1369 if (isl_set_is_wrapping(stmt
->domain
)) {
1374 map
= isl_set_unwrap(stmt
->domain
);
1375 stmt_id
= isl_map_get_tuple_id(map
, isl_dim_in
);
1376 ran_dim
= isl_space_range(isl_map_get_space(map
));
1377 ext
= isl_map_from_domain_and_range(isl_set_copy(dom
),
1378 isl_set_universe(ran_dim
));
1379 map
= isl_map_flat_domain_product(ext
, map
);
1380 map
= isl_map_set_tuple_id(map
, isl_dim_in
,
1381 isl_id_copy(stmt_id
));
1382 dim
= isl_space_domain(isl_map_get_space(map
));
1383 stmt
->domain
= isl_map_wrap(map
);
1385 stmt_id
= isl_set_get_tuple_id(stmt
->domain
);
1386 stmt
->domain
= isl_set_flat_product(isl_set_copy(dom
),
1388 stmt
->domain
= isl_set_set_tuple_id(stmt
->domain
,
1389 isl_id_copy(stmt_id
));
1390 dim
= isl_set_get_space(stmt
->domain
);
1393 pos
= isl_set_find_dim_by_id(stmt
->domain
, isl_dim_param
, var_id
);
1395 stmt
->domain
= internalize_iv(stmt
->domain
, pos
,
1396 isl_aff_copy(iv_map
));
1398 stmt
->schedule
= isl_map_flat_product(sched
, stmt
->schedule
);
1399 stmt
->schedule
= isl_map_set_tuple_id(stmt
->schedule
,
1400 isl_dim_in
, stmt_id
);
1402 pos
= isl_map_find_dim_by_id(stmt
->schedule
, isl_dim_param
, var_id
);
1404 isl_set
*set
= isl_map_wrap(stmt
->schedule
);
1405 set
= internalize_iv(set
, pos
, isl_aff_copy(iv_map
));
1406 stmt
->schedule
= isl_set_unwrap(set
);
1409 dim
= isl_space_map_from_set(dim
);
1410 extend
= isl_multi_pw_aff_identity(dim
);
1411 extend
= isl_multi_pw_aff_drop_dims(extend
, isl_dim_out
, 0, 1);
1412 extend
= isl_multi_pw_aff_set_tuple_id(extend
, isl_dim_out
,
1413 isl_multi_pw_aff_get_tuple_id(extend
, isl_dim_in
));
1414 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1415 stmt
->args
[i
] = expr_embed(stmt
->args
[i
],
1416 isl_multi_pw_aff_copy(extend
),
1417 isl_aff_copy(iv_map
), var_id
);
1418 stmt
->body
= expr_embed(stmt
->body
, extend
, iv_map
, var_id
);
1421 isl_id_free(var_id
);
1423 for (i
= 0; i
< stmt
->n_arg
; ++i
)
1425 return pet_stmt_free(stmt
);
1426 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
1427 return pet_stmt_free(stmt
);
1431 isl_map_free(sched
);
1432 isl_aff_free(iv_map
);
1433 isl_id_free(var_id
);
1437 /* Embed the given pet_array in an extra outer loop with iteration domain
1439 * This embedding only has an effect on virtual arrays (those with
1440 * user pointer equal to NULL), which need to be extended along with
1441 * the iteration domain.
1443 static struct pet_array
*pet_array_embed(struct pet_array
*array
,
1444 __isl_take isl_set
*dom
)
1446 isl_id
*array_id
= NULL
;
1451 if (isl_set_has_tuple_id(array
->extent
))
1452 array_id
= isl_set_get_tuple_id(array
->extent
);
1454 if (array_id
&& !isl_id_get_user(array_id
)) {
1455 array
->extent
= isl_set_flat_product(dom
, array
->extent
);
1456 array
->extent
= isl_set_set_tuple_id(array
->extent
, array_id
);
1458 return pet_array_free(array
);
1461 isl_id_free(array_id
);
1470 /* Project out all unnamed parameters from "set" and return the result.
1472 static __isl_give isl_set
*set_project_out_unnamed_params(
1473 __isl_take isl_set
*set
)
1477 n
= isl_set_dim(set
, isl_dim_param
);
1478 for (i
= n
- 1; i
>= 0; --i
) {
1479 if (isl_set_has_dim_name(set
, isl_dim_param
, i
))
1481 set
= isl_set_project_out(set
, isl_dim_param
, i
, 1);
1487 /* Update the context with respect to an embedding into a loop
1488 * with iteration domain "dom" and induction variable "id".
1489 * "iv_map" expresses the real iterator (parameter "id") in terms
1490 * of a possibly virtual iterator (used in "dom").
1492 * If the current context is independent of "id", we don't need
1494 * Otherwise, a parameter value is invalid for the embedding if
1495 * any of the corresponding iterator values is invalid.
1496 * That is, a parameter value is valid only if all the corresponding
1497 * iterator values are valid.
1498 * We therefore compute the set of parameters
1500 * forall i in dom : valid (i)
1504 * not exists i in dom : not valid(i)
1508 * not exists i in dom \ valid(i)
1510 * Before we subtract valid(i) from dom, we first need to substitute
1511 * the real iterator for the virtual iterator.
1513 * If there are any unnamed parameters in "dom", then we consider
1514 * a parameter value to be valid if it is valid for any value of those
1515 * unnamed parameters. They are therefore projected out at the end.
1517 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1518 __isl_keep isl_set
*dom
, __isl_keep isl_aff
*iv_map
,
1519 __isl_keep isl_id
*id
)
1524 pos
= isl_set_find_dim_by_id(context
, isl_dim_param
, id
);
1528 context
= isl_set_from_params(context
);
1529 context
= isl_set_add_dims(context
, isl_dim_set
, 1);
1530 context
= isl_set_equate(context
, isl_dim_param
, pos
, isl_dim_set
, 0);
1531 context
= isl_set_project_out(context
, isl_dim_param
, pos
, 1);
1532 ma
= isl_multi_aff_from_aff(isl_aff_copy(iv_map
));
1533 context
= isl_set_preimage_multi_aff(context
, ma
);
1534 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1535 context
= isl_set_params(context
);
1536 context
= isl_set_complement(context
);
1537 context
= set_project_out_unnamed_params(context
);
1541 /* Update the implication with respect to an embedding into a loop
1542 * with iteration domain "dom".
1544 * Since embed_access extends virtual arrays along with the domain
1545 * of the access, we need to do the same with domain and range
1546 * of the implication. Since the original implication is only valid
1547 * within a given iteration of the loop, the extended implication
1548 * maps the extra array dimension corresponding to the extra loop
1551 static struct pet_implication
*pet_implication_embed(
1552 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1560 map
= isl_set_identity(dom
);
1561 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1562 map
= isl_map_flat_product(map
, implication
->extension
);
1563 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1564 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1565 implication
->extension
= map
;
1566 if (!implication
->extension
)
1567 return pet_implication_free(implication
);
1575 /* Embed all statements and arrays in "scop" in an extra outer loop
1576 * with iteration domain "dom" and schedule "sched".
1577 * "id" represents the induction variable of the loop.
1578 * "iv_map" maps a possibly virtual iterator to the real iterator.
1579 * That is, it expresses the iterator that some of the parameters in "scop"
1580 * may refer to in terms of the iterator used in "dom" and
1581 * the domain of "sched".
1583 * Any skip conditions within the loop have no effect outside of the loop.
1584 * The caller is responsible for making sure skip[pet_skip_later] has been
1585 * taken into account.
1587 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1588 __isl_take isl_aff
*sched
, __isl_take isl_aff
*iv_map
,
1589 __isl_take isl_id
*id
)
1594 sched_map
= isl_map_from_aff(sched
);
1599 pet_scop_reset_skip(scop
, pet_skip_now
);
1600 pet_scop_reset_skip(scop
, pet_skip_later
);
1602 scop
->context
= context_embed(scop
->context
, dom
, iv_map
, id
);
1606 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1607 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1608 isl_set_copy(dom
), isl_map_copy(sched_map
),
1609 isl_aff_copy(iv_map
), isl_id_copy(id
));
1610 if (!scop
->stmts
[i
])
1614 for (i
= 0; i
< scop
->n_array
; ++i
) {
1615 scop
->arrays
[i
] = pet_array_embed(scop
->arrays
[i
],
1617 if (!scop
->arrays
[i
])
1621 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1622 scop
->implications
[i
] =
1623 pet_implication_embed(scop
->implications
[i
],
1625 if (!scop
->implications
[i
])
1630 isl_map_free(sched_map
);
1631 isl_aff_free(iv_map
);
1636 isl_map_free(sched_map
);
1637 isl_aff_free(iv_map
);
1639 return pet_scop_free(scop
);
1642 /* Add extra conditions on the parameters to the iteration domain of "stmt".
1644 static struct pet_stmt
*stmt_restrict(struct pet_stmt
*stmt
,
1645 __isl_take isl_set
*cond
)
1650 stmt
->domain
= isl_set_intersect_params(stmt
->domain
, cond
);
1655 return pet_stmt_free(stmt
);
1658 /* Add extra conditions to scop->skip[type].
1660 * The new skip condition only holds if it held before
1661 * and the condition is true. It does not hold if it did not hold
1662 * before or the condition is false.
1664 * The skip condition is assumed to be an affine expression.
1666 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1667 enum pet_skip type
, __isl_keep isl_set
*cond
)
1669 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1675 if (!ext
->skip
[type
])
1678 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1679 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1680 isl_error_internal
, "can only restrict affine skips",
1681 return pet_scop_free(scop
));
1683 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1684 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1685 cond
= isl_set_copy(cond
);
1686 cond
= isl_set_from_params(cond
);
1687 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1688 skip
= indicator_function(cond
, dom
);
1689 isl_multi_pw_aff_free(ext
->skip
[type
]);
1690 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1691 if (!ext
->skip
[type
])
1692 return pet_scop_free(scop
);
1697 /* Add extra conditions on the parameters to all iteration domains
1698 * and skip conditions.
1700 * A parameter value is valid for the result if it was valid
1701 * for the original scop and satisfies "cond" or if it does
1702 * not satisfy "cond" as in this case the scop is not executed
1703 * and the original constraints on the parameters are irrelevant.
1705 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1706 __isl_take isl_set
*cond
)
1710 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1711 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1716 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1717 scop
->context
= isl_set_union(scop
->context
,
1718 isl_set_complement(isl_set_copy(cond
)));
1719 scop
->context
= isl_set_coalesce(scop
->context
);
1720 scop
->context
= set_project_out_unnamed_params(scop
->context
);
1724 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1725 scop
->stmts
[i
] = stmt_restrict(scop
->stmts
[i
],
1726 isl_set_copy(cond
));
1727 if (!scop
->stmts
[i
])
1735 return pet_scop_free(scop
);
1738 /* Insert an argument expression corresponding to "test" in front
1739 * of the list of arguments described by *n_arg and *args.
1741 static int args_insert_access(unsigned *n_arg
, struct pet_expr
***args
,
1742 __isl_keep isl_multi_pw_aff
*test
)
1745 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1751 *args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
1755 struct pet_expr
**ext
;
1756 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + *n_arg
);
1759 for (i
= 0; i
< *n_arg
; ++i
)
1760 ext
[1 + i
] = (*args
)[i
];
1765 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1772 /* Look through the applications in "scop" for any that can be
1773 * applied to the filter expressed by "map" and "satisified".
1774 * If there is any, then apply it to "map" and return the result.
1775 * Otherwise, return "map".
1776 * "id" is the identifier of the virtual array.
1778 * We only introduce at most one implication for any given virtual array,
1779 * so we can apply the implication and return as soon as we find one.
1781 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1782 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1786 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1787 struct pet_implication
*pi
= scop
->implications
[i
];
1790 if (pi
->satisfied
!= satisfied
)
1792 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1797 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1803 /* Is the filter expressed by "test" and "satisfied" implied
1804 * by filter "pos" on "domain", with filter "expr", taking into
1805 * account the implications of "scop"?
1807 * For filter on domain implying that expressed by "test" and "satisfied",
1808 * the filter needs to be an access to the same (virtual) array as "test" and
1809 * the filter value needs to be equal to "satisfied".
1810 * Moreover, the filter access relation, possibly extended by
1811 * the implications in "scop" needs to contain "test".
1813 static int implies_filter(struct pet_scop
*scop
,
1814 __isl_keep isl_map
*domain
, int pos
, struct pet_expr
*expr
,
1815 __isl_keep isl_map
*test
, int satisfied
)
1817 isl_id
*test_id
, *arg_id
;
1824 if (expr
->type
!= pet_expr_access
)
1826 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1827 arg_id
= pet_expr_access_get_id(expr
);
1828 isl_id_free(arg_id
);
1829 isl_id_free(test_id
);
1830 if (test_id
!= arg_id
)
1832 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
1833 is_int
= isl_val_is_int(val
);
1835 s
= isl_val_get_num_si(val
);
1844 implied
= isl_map_copy(expr
->acc
.access
);
1845 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
1846 is_subset
= isl_map_is_subset(test
, implied
);
1847 isl_map_free(implied
);
1852 /* Is the filter expressed by "test" and "satisfied" implied
1853 * by any of the filters on the domain of "stmt", taking into
1854 * account the implications of "scop"?
1856 static int filter_implied(struct pet_scop
*scop
,
1857 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1865 if (!scop
|| !stmt
|| !test
)
1867 if (scop
->n_implication
== 0)
1869 if (stmt
->n_arg
== 0)
1872 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
1873 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
1876 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
1877 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
1878 test_map
, satisfied
);
1879 if (implied
< 0 || implied
)
1883 isl_map_free(test_map
);
1884 isl_map_free(domain
);
1888 /* Make the statement "stmt" depend on the value of "test"
1889 * being equal to "satisfied" by adjusting stmt->domain.
1891 * The domain of "test" corresponds to the (zero or more) outer dimensions
1892 * of the iteration domain.
1894 * We first extend "test" to apply to the entire iteration domain and
1895 * then check if the filter that we are about to add is implied
1896 * by any of the current filters, possibly taking into account
1897 * the implications in "scop". If so, we leave "stmt" untouched and return.
1899 * Otherwise, we insert an argument corresponding to a read to "test"
1900 * from the iteration domain of "stmt" in front of the list of arguments.
1901 * We also insert a corresponding output dimension in the wrapped
1902 * map contained in stmt->domain, with value set to "satisfied".
1904 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
1905 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1911 isl_pw_multi_aff
*pma
;
1912 isl_multi_aff
*add_dom
;
1914 isl_local_space
*ls
;
1920 space
= pet_stmt_get_space(stmt
);
1921 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
1922 space
= isl_space_from_domain(space
);
1923 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
1924 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
1925 ls
= isl_local_space_from_space(isl_space_domain(space
));
1926 for (i
= 0; i
< n_test_dom
; ++i
) {
1928 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1930 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
1932 isl_local_space_free(ls
);
1933 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
1935 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
1939 isl_multi_pw_aff_free(test
);
1943 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1944 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
1946 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
1948 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1951 isl_multi_pw_aff_free(test
);
1954 isl_multi_pw_aff_free(test
);
1955 return pet_stmt_free(stmt
);
1958 /* Does "scop" have a skip condition of the given "type"?
1960 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1962 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1966 return ext
->skip
[type
] != NULL
;
1969 /* Does "scop" have a skip condition of the given "type" that
1970 * is an affine expression?
1972 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1974 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1978 if (!ext
->skip
[type
])
1980 return multi_pw_aff_is_affine(ext
->skip
[type
]);
1983 /* Does "scop" have a skip condition of the given "type" that
1984 * is not an affine expression?
1986 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1988 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1993 if (!ext
->skip
[type
])
1995 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2001 /* Does "scop" have a skip condition of the given "type" that
2002 * is affine and holds on the entire domain?
2004 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2006 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2012 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2013 if (is_aff
< 0 || !is_aff
)
2016 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2017 set
= isl_pw_aff_non_zero_set(pa
);
2018 is_univ
= isl_set_plain_is_universe(set
);
2024 /* Replace scop->skip[type] by "skip".
2026 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2027 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2029 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2034 isl_multi_pw_aff_free(ext
->skip
[type
]);
2035 ext
->skip
[type
] = skip
;
2039 isl_multi_pw_aff_free(skip
);
2040 return pet_scop_free(scop
);
2043 /* Return a copy of scop->skip[type].
2045 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2048 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2053 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2056 /* Assuming scop->skip[type] is an affine expression,
2057 * return the constraints on the parameters for which the skip condition
2060 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2063 isl_multi_pw_aff
*skip
;
2066 skip
= pet_scop_get_skip(scop
, type
);
2067 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2068 isl_multi_pw_aff_free(skip
);
2069 return isl_set_params(isl_pw_aff_non_zero_set(pa
));
2072 /* Return the identifier of the variable that is accessed by
2073 * the skip condition of the given type.
2075 * The skip condition is assumed not to be an affine condition.
2077 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2080 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2085 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2088 /* Return an access pet_expr corresponding to the skip condition
2089 * of the given type.
2091 struct pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2094 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2097 /* Drop the the skip condition scop->skip[type].
2099 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2101 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2106 isl_multi_pw_aff_free(ext
->skip
[type
]);
2107 ext
->skip
[type
] = NULL
;
2110 /* Make the skip condition (if any) depend on the value of "test" being
2111 * equal to "satisfied".
2113 * We only support the case where the original skip condition is universal,
2114 * i.e., where skipping is unconditional, and where satisfied == 1.
2115 * In this case, the skip condition is changed to skip only when
2116 * "test" is equal to one.
2118 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2119 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2125 if (!pet_scop_has_skip(scop
, type
))
2129 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2131 return pet_scop_free(scop
);
2132 if (satisfied
&& is_univ
) {
2133 isl_multi_pw_aff
*skip
;
2134 skip
= isl_multi_pw_aff_copy(test
);
2135 scop
= pet_scop_set_skip(scop
, type
, skip
);
2139 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2140 "skip expression cannot be filtered",
2141 return pet_scop_free(scop
));
2147 /* Make all statements in "scop" depend on the value of "test"
2148 * being equal to "satisfied" by adjusting their domains.
2150 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2151 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2155 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2156 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2161 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2162 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2163 isl_multi_pw_aff_copy(test
), satisfied
);
2164 if (!scop
->stmts
[i
])
2168 isl_multi_pw_aff_free(test
);
2171 isl_multi_pw_aff_free(test
);
2172 return pet_scop_free(scop
);
2175 /* Add all parameters in "expr" to "space" and return the result.
2177 static __isl_give isl_space
*expr_collect_params(struct pet_expr
*expr
,
2178 __isl_take isl_space
*space
)
2184 for (i
= 0; i
< expr
->n_arg
; ++i
)
2185 space
= expr_collect_params(expr
->args
[i
], space
);
2187 if (expr
->type
== pet_expr_access
)
2188 space
= isl_space_align_params(space
,
2189 isl_map_get_space(expr
->acc
.access
));
2193 pet_expr_free(expr
);
2194 return isl_space_free(space
);
2197 /* Add all parameters in "stmt" to "space" and return the result.
2199 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2200 __isl_take isl_space
*space
)
2205 return isl_space_free(space
);
2207 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2208 space
= isl_space_align_params(space
,
2209 isl_map_get_space(stmt
->schedule
));
2210 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2211 space
= expr_collect_params(stmt
->args
[i
], space
);
2212 space
= expr_collect_params(stmt
->body
, space
);
2217 /* Add all parameters in "array" to "space" and return the result.
2219 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2220 __isl_take isl_space
*space
)
2223 return isl_space_free(space
);
2225 space
= isl_space_align_params(space
,
2226 isl_set_get_space(array
->context
));
2227 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2232 /* Add all parameters in "scop" to "space" and return the result.
2234 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2235 __isl_take isl_space
*space
)
2240 return isl_space_free(space
);
2242 for (i
= 0; i
< scop
->n_array
; ++i
)
2243 space
= array_collect_params(scop
->arrays
[i
], space
);
2245 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2246 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2251 /* Add all parameters in "space" to the domain, schedule and
2252 * all access relations in "stmt".
2254 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2255 __isl_take isl_space
*space
)
2262 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2263 isl_space_copy(space
));
2264 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2265 isl_space_copy(space
));
2267 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2268 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2269 isl_space_copy(space
));
2273 stmt
->body
= pet_expr_align_params(stmt
->body
, isl_space_copy(space
));
2275 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2278 isl_space_free(space
);
2281 isl_space_free(space
);
2282 return pet_stmt_free(stmt
);
2285 /* Add all parameters in "space" to "array".
2287 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2288 __isl_take isl_space
*space
)
2293 array
->context
= isl_set_align_params(array
->context
,
2294 isl_space_copy(space
));
2295 array
->extent
= isl_set_align_params(array
->extent
,
2296 isl_space_copy(space
));
2297 if (array
->value_bounds
) {
2298 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2299 isl_space_copy(space
));
2300 if (!array
->value_bounds
)
2304 if (!array
->context
|| !array
->extent
)
2307 isl_space_free(space
);
2310 isl_space_free(space
);
2311 return pet_array_free(array
);
2314 /* Add all parameters in "space" to "scop".
2316 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2317 __isl_take isl_space
*space
)
2324 for (i
= 0; i
< scop
->n_array
; ++i
) {
2325 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2326 isl_space_copy(space
));
2327 if (!scop
->arrays
[i
])
2331 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2332 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2333 isl_space_copy(space
));
2334 if (!scop
->stmts
[i
])
2338 isl_space_free(space
);
2341 isl_space_free(space
);
2342 return pet_scop_free(scop
);
2345 /* Update all isl_sets and isl_maps in "scop" such that they all
2346 * have the same parameters.
2348 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2355 space
= isl_set_get_space(scop
->context
);
2356 space
= scop_collect_params(scop
, space
);
2358 scop
->context
= isl_set_align_params(scop
->context
,
2359 isl_space_copy(space
));
2360 scop
= scop_propagate_params(scop
, space
);
2362 if (scop
&& !scop
->context
)
2363 return pet_scop_free(scop
);
2368 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2369 * in "space" by a value equal to the corresponding parameter.
2371 static struct pet_stmt
*stmt_detect_parameter_accesses(struct pet_stmt
*stmt
,
2372 __isl_take isl_space
*space
)
2377 stmt
->body
= pet_expr_detect_parameter_accesses(stmt
->body
,
2378 isl_space_copy(space
));
2380 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2383 isl_space_free(space
);
2386 isl_space_free(space
);
2387 return pet_stmt_free(stmt
);
2390 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2391 * in "space" by a value equal to the corresponding parameter.
2393 static struct pet_scop
*scop_detect_parameter_accesses(struct pet_scop
*scop
,
2394 __isl_take isl_space
*space
)
2401 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2402 scop
->stmts
[i
] = stmt_detect_parameter_accesses(scop
->stmts
[i
],
2403 isl_space_copy(space
));
2404 if (!scop
->stmts
[i
])
2408 isl_space_free(space
);
2411 isl_space_free(space
);
2412 return pet_scop_free(scop
);
2415 /* Replace all accesses to (0D) arrays that correspond to any of
2416 * the parameters used in "scop" by a value equal
2417 * to the corresponding parameter.
2419 struct pet_scop
*pet_scop_detect_parameter_accesses(struct pet_scop
*scop
)
2426 space
= isl_set_get_space(scop
->context
);
2427 space
= scop_collect_params(scop
, space
);
2429 scop
= scop_detect_parameter_accesses(scop
, space
);
2434 /* Add the access relation of the access expression "expr" to "accesses" and
2435 * return the result.
2436 * The domain of the access relation is intersected with "domain".
2437 * If "tag" is set, then the access relation is tagged with
2438 * the corresponding reference identifier.
2440 static __isl_give isl_union_map
*expr_collect_access(struct pet_expr
*expr
,
2441 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2445 access
= pet_expr_access_get_may_access(expr
);
2446 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
2448 access
= pet_expr_tag_access(expr
, access
);
2449 return isl_union_map_add_map(accesses
, access
);
2452 /* Add all read access relations (if "read" is set) and/or all write
2453 * access relations (if "write" is set) to "accesses" and return the result.
2454 * The domains of the access relations are intersected with "domain".
2455 * If "tag" is set, then the access relations are tagged with
2456 * the corresponding reference identifiers.
2458 * If "must" is set, then we only add the accesses that are definitely
2459 * performed. Otherwise, we add all potential accesses.
2460 * In particular, if the access has any arguments, then if "must" is
2461 * set we currently skip the access completely. If "must" is not set,
2462 * we project out the values of the access arguments.
2464 static __isl_give isl_union_map
*expr_collect_accesses(struct pet_expr
*expr
,
2465 int read
, int write
, int must
, int tag
,
2466 __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2473 return isl_union_map_free(accesses
);
2475 for (i
= 0; i
< expr
->n_arg
; ++i
)
2476 accesses
= expr_collect_accesses(expr
->args
[i
],
2477 read
, write
, must
, tag
, accesses
, domain
);
2479 if (expr
->type
== pet_expr_access
&& !pet_expr_is_affine(expr
) &&
2480 ((read
&& expr
->acc
.read
) || (write
&& expr
->acc
.write
)) &&
2481 (!must
|| expr
->n_arg
== 0)) {
2482 accesses
= expr_collect_access(expr
, tag
, accesses
, domain
);
2488 /* Collect and return all read access relations (if "read" is set)
2489 * and/or all write access relations (if "write" is set) in "stmt".
2490 * If "tag" is set, then the access relations are tagged with
2491 * the corresponding reference identifiers.
2492 * If "kill" is set, then "stmt" is a kill statement and we simply
2493 * add the argument of the kill operation.
2495 * If "must" is set, then we only add the accesses that are definitely
2496 * performed. Otherwise, we add all potential accesses.
2497 * In particular, if the statement has any arguments, then if "must" is
2498 * set we currently skip the statement completely. If "must" is not set,
2499 * we project out the values of the statement arguments.
2501 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2502 int read
, int write
, int kill
, int must
, int tag
,
2503 __isl_take isl_space
*dim
)
2505 isl_union_map
*accesses
;
2511 accesses
= isl_union_map_empty(dim
);
2513 if (must
&& stmt
->n_arg
> 0)
2516 domain
= isl_set_copy(stmt
->domain
);
2517 if (isl_set_is_wrapping(domain
))
2518 domain
= isl_map_domain(isl_set_unwrap(domain
));
2521 accesses
= expr_collect_access(stmt
->body
->args
[0], tag
,
2524 accesses
= expr_collect_accesses(stmt
->body
, read
, write
,
2525 must
, tag
, accesses
, domain
);
2526 isl_set_free(domain
);
2531 /* Is "stmt" an assignment statement?
2533 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2537 if (stmt
->body
->type
!= pet_expr_op
)
2539 return stmt
->body
->op
== pet_op_assign
;
2542 /* Is "stmt" a kill statement?
2544 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2548 if (stmt
->body
->type
!= pet_expr_op
)
2550 return stmt
->body
->op
== pet_op_kill
;
2553 /* Is "stmt" an assume statement?
2555 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2557 if (stmt
->body
->type
!= pet_expr_op
)
2559 return stmt
->body
->op
== pet_op_assume
;
2562 /* Compute a mapping from all arrays (of structs) in scop
2563 * to their innermost arrays.
2565 * In particular, for each array of a primitive type, the result
2566 * contains the identity mapping on that array.
2567 * For each array involving member accesses, the result
2568 * contains a mapping from the elements of any intermediate array of structs
2569 * to all corresponding elements of the innermost nested arrays.
2571 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
2574 isl_union_map
*to_inner
;
2576 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2578 for (i
= 0; i
< scop
->n_array
; ++i
) {
2579 struct pet_array
*array
= scop
->arrays
[i
];
2581 isl_map
*map
, *gist
;
2583 if (array
->element_is_record
)
2586 map
= isl_set_identity(isl_set_copy(array
->extent
));
2588 set
= isl_map_domain(isl_map_copy(map
));
2589 gist
= isl_map_copy(map
);
2590 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2591 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2593 while (set
&& isl_set_is_wrapping(set
)) {
2597 id
= isl_set_get_tuple_id(set
);
2598 wrapped
= isl_set_unwrap(set
);
2599 wrapped
= isl_map_domain_map(wrapped
);
2600 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2601 map
= isl_map_apply_domain(map
, wrapped
);
2602 set
= isl_map_domain(isl_map_copy(map
));
2603 gist
= isl_map_copy(map
);
2604 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2605 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2615 /* Collect and return all read access relations (if "read" is set)
2616 * and/or all write access relations (if "write" is set) in "scop".
2617 * If "kill" is set, then we only add the arguments of kill operations.
2618 * If "must" is set, then we only add the accesses that are definitely
2619 * performed. Otherwise, we add all potential accesses.
2620 * If "tag" is set, then the access relations are tagged with
2621 * the corresponding reference identifiers.
2622 * For accesses to structures, the returned access relation accesses
2623 * all individual fields in the structures.
2625 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2626 int read
, int write
, int kill
, int must
, int tag
)
2629 isl_union_map
*accesses
;
2630 isl_union_set
*arrays
;
2631 isl_union_map
*to_inner
;
2636 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2638 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2639 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2640 isl_union_map
*accesses_i
;
2643 if (kill
&& !pet_stmt_is_kill(stmt
))
2646 space
= isl_set_get_space(scop
->context
);
2647 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
2649 accesses
= isl_union_map_union(accesses
, accesses_i
);
2652 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2653 for (i
= 0; i
< scop
->n_array
; ++i
) {
2654 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2655 arrays
= isl_union_set_add_set(arrays
, extent
);
2657 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2659 to_inner
= compute_to_inner(scop
);
2660 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2665 /* Collect all potential read access relations.
2667 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2669 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
2672 /* Collect all potential write access relations.
2674 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2676 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
2679 /* Collect all definite write access relations.
2681 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2683 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
2686 /* Collect all definite kill access relations.
2688 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2690 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
2693 /* Collect all tagged potential read access relations.
2695 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2696 struct pet_scop
*scop
)
2698 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
2701 /* Collect all tagged potential write access relations.
2703 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2704 struct pet_scop
*scop
)
2706 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
2709 /* Collect all tagged definite write access relations.
2711 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2712 struct pet_scop
*scop
)
2714 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
2717 /* Collect all tagged definite kill access relations.
2719 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2720 struct pet_scop
*scop
)
2722 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
2725 /* Collect and return the union of iteration domains in "scop".
2727 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2731 isl_union_set
*domain
;
2736 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2738 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2739 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2740 domain
= isl_union_set_add_set(domain
, domain_i
);
2746 /* Collect and return the schedules of the statements in "scop".
2747 * The range is normalized to the maximal number of scheduling
2750 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2753 isl_map
*schedule_i
;
2754 isl_union_map
*schedule
;
2755 int depth
, max_depth
= 0;
2760 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2762 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2763 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2764 if (depth
> max_depth
)
2768 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2769 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2770 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2771 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2773 for (j
= depth
; j
< max_depth
; ++j
)
2774 schedule_i
= isl_map_fix_si(schedule_i
,
2776 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2782 /* Does statement "stmt" write to "id"?
2784 static int stmt_writes(struct pet_stmt
*stmt
, __isl_keep isl_id
*id
)
2786 return pet_expr_writes(stmt
->body
, id
);
2789 /* Is there any write access in "scop" that accesses "id"?
2791 int pet_scop_writes(struct pet_scop
*scop
, __isl_keep isl_id
*id
)
2798 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2799 int writes
= stmt_writes(scop
->stmts
[i
], id
);
2800 if (writes
< 0 || writes
)
2807 /* Add a reference identifier to all access expressions in "stmt".
2808 * "n_ref" points to an integer that contains the sequence number
2809 * of the next reference.
2811 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2818 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2819 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2821 return pet_stmt_free(stmt
);
2824 stmt
->body
= pet_expr_add_ref_ids(stmt
->body
, n_ref
);
2826 return pet_stmt_free(stmt
);
2831 /* Add a reference identifier to all access expressions in "scop".
2833 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2842 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2843 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2844 if (!scop
->stmts
[i
])
2845 return pet_scop_free(scop
);
2851 /* Reset the user pointer on all parameter ids in "array".
2853 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2858 array
->context
= isl_set_reset_user(array
->context
);
2859 array
->extent
= isl_set_reset_user(array
->extent
);
2860 if (!array
->context
|| !array
->extent
)
2861 return pet_array_free(array
);
2866 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2868 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2877 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
2878 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
2879 if (!stmt
->domain
|| !stmt
->schedule
)
2880 return pet_stmt_free(stmt
);
2882 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2883 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
2885 return pet_stmt_free(stmt
);
2888 stmt
->body
= pet_expr_anonymize(stmt
->body
);
2890 return pet_stmt_free(stmt
);
2895 /* Reset the user pointer on the tuple ids and all parameter ids
2898 static struct pet_implication
*implication_anonymize(
2899 struct pet_implication
*implication
)
2904 implication
->extension
= isl_map_reset_user(implication
->extension
);
2905 if (!implication
->extension
)
2906 return pet_implication_free(implication
);
2911 /* Reset the user pointer on all parameter and tuple ids in "scop".
2913 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2920 scop
->context
= isl_set_reset_user(scop
->context
);
2921 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
2922 if (!scop
->context
|| !scop
->context_value
)
2923 return pet_scop_free(scop
);
2925 for (i
= 0; i
< scop
->n_array
; ++i
) {
2926 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2927 if (!scop
->arrays
[i
])
2928 return pet_scop_free(scop
);
2931 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2932 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2933 if (!scop
->stmts
[i
])
2934 return pet_scop_free(scop
);
2937 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2938 scop
->implications
[i
] =
2939 implication_anonymize(scop
->implications
[i
]);
2940 if (!scop
->implications
[i
])
2941 return pet_scop_free(scop
);
2947 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
2948 * then intersect the range of "map" with the valid set of values.
2950 static __isl_give isl_map
*access_apply_value_bounds(__isl_take isl_map
*map
,
2951 struct pet_expr
*arg
, __isl_keep isl_union_map
*value_bounds
)
2956 isl_ctx
*ctx
= isl_map_get_ctx(map
);
2958 id
= pet_expr_access_get_id(arg
);
2959 space
= isl_space_alloc(ctx
, 0, 0, 1);
2960 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
2961 vb
= isl_union_map_extract_map(value_bounds
, space
);
2962 if (!isl_map_plain_is_empty(vb
))
2963 map
= isl_map_intersect_range(map
, isl_map_range(vb
));
2970 /* Given a set "domain", return a wrapped relation with the given set
2971 * as domain and a range of dimension "n_arg", where each coordinate
2972 * is either unbounded or, if the corresponding element of args is of
2973 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2975 static __isl_give isl_set
*apply_value_bounds(__isl_take isl_set
*domain
,
2976 unsigned n_arg
, struct pet_expr
**args
,
2977 __isl_keep isl_union_map
*value_bounds
)
2983 map
= isl_map_from_domain(domain
);
2984 space
= isl_map_get_space(map
);
2985 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2987 for (i
= 0; i
< n_arg
; ++i
) {
2989 struct pet_expr
*arg
= args
[i
];
2991 map_i
= isl_map_universe(isl_space_copy(space
));
2992 if (arg
->type
== pet_expr_access
)
2993 map_i
= access_apply_value_bounds(map_i
, arg
,
2995 map
= isl_map_flat_range_product(map
, map_i
);
2997 isl_space_free(space
);
2999 return isl_map_wrap(map
);
3002 /* Data used in access_gist() callback.
3004 struct pet_access_gist_data
{
3006 isl_union_map
*value_bounds
;
3009 /* Given an expression "expr" of type pet_expr_access, compute
3010 * the gist of the associated access relation and index expression
3011 * with respect to data->domain and the bounds on the values of the arguments
3012 * of the expression.
3014 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
3016 struct pet_access_gist_data
*data
= user
;
3019 domain
= isl_set_copy(data
->domain
);
3020 if (expr
->n_arg
> 0)
3021 domain
= apply_value_bounds(domain
, expr
->n_arg
, expr
->args
,
3022 data
->value_bounds
);
3024 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
3025 isl_set_copy(domain
));
3026 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
3027 if (!expr
->acc
.access
|| !expr
->acc
.index
)
3028 return pet_expr_free(expr
);
3033 /* Compute the gist of the iteration domain and all access relations
3034 * of "stmt" based on the constraints on the parameters specified by "context"
3035 * and the constraints on the values of nested accesses specified
3036 * by "value_bounds".
3038 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3039 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3043 struct pet_access_gist_data data
;
3048 data
.domain
= isl_set_copy(stmt
->domain
);
3049 data
.value_bounds
= value_bounds
;
3050 if (stmt
->n_arg
> 0)
3051 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
3053 data
.domain
= isl_set_intersect_params(data
.domain
,
3054 isl_set_copy(context
));
3056 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3057 stmt
->args
[i
] = pet_expr_map_access(stmt
->args
[i
],
3058 &access_gist
, &data
);
3063 stmt
->body
= pet_expr_map_access(stmt
->body
, &access_gist
, &data
);
3067 isl_set_free(data
.domain
);
3069 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
3070 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3071 if (stmt
->n_arg
> 0)
3072 domain
= apply_value_bounds(domain
, stmt
->n_arg
, stmt
->args
,
3074 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3076 return pet_stmt_free(stmt
);
3080 isl_set_free(data
.domain
);
3081 return pet_stmt_free(stmt
);
3084 /* Compute the gist of the extent of the array
3085 * based on the constraints on the parameters specified by "context".
3087 static struct pet_array
*array_gist(struct pet_array
*array
,
3088 __isl_keep isl_set
*context
)
3093 array
->extent
= isl_set_gist_params(array
->extent
,
3094 isl_set_copy(context
));
3096 return pet_array_free(array
);
3101 /* Compute the gist of all sets and relations in "scop"
3102 * based on the constraints on the parameters specified by "scop->context"
3103 * and the constraints on the values of nested accesses specified
3104 * by "value_bounds".
3106 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3107 __isl_keep isl_union_map
*value_bounds
)
3114 scop
->context
= isl_set_coalesce(scop
->context
);
3116 return pet_scop_free(scop
);
3118 for (i
= 0; i
< scop
->n_array
; ++i
) {
3119 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3120 if (!scop
->arrays
[i
])
3121 return pet_scop_free(scop
);
3124 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3125 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3127 if (!scop
->stmts
[i
])
3128 return pet_scop_free(scop
);
3134 /* Intersect the context of "scop" with "context".
3135 * To ensure that we don't introduce any unnamed parameters in
3136 * the context of "scop", we first remove the unnamed parameters
3139 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3140 __isl_take isl_set
*context
)
3145 context
= set_project_out_unnamed_params(context
);
3146 scop
->context
= isl_set_intersect(scop
->context
, context
);
3148 return pet_scop_free(scop
);
3152 isl_set_free(context
);
3153 return pet_scop_free(scop
);
3156 /* Drop the current context of "scop". That is, replace the context
3157 * by a universal set.
3159 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3166 space
= isl_set_get_space(scop
->context
);
3167 isl_set_free(scop
->context
);
3168 scop
->context
= isl_set_universe(space
);
3170 return pet_scop_free(scop
);
3175 /* Append "array" to the arrays of "scop".
3177 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3178 struct pet_array
*array
)
3181 struct pet_array
**arrays
;
3183 if (!array
|| !scop
)
3186 ctx
= isl_set_get_ctx(scop
->context
);
3187 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3191 scop
->arrays
= arrays
;
3192 scop
->arrays
[scop
->n_array
] = array
;
3197 pet_array_free(array
);
3198 return pet_scop_free(scop
);
3201 /* Create and return an implication on filter values equal to "satisfied"
3202 * with extension "map".
3204 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3208 struct pet_implication
*implication
;
3212 ctx
= isl_map_get_ctx(map
);
3213 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3217 implication
->extension
= map
;
3218 implication
->satisfied
= satisfied
;
3226 /* Add an implication on filter values equal to "satisfied"
3227 * with extension "map" to "scop".
3229 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3230 __isl_take isl_map
*map
, int satisfied
)
3233 struct pet_implication
*implication
;
3234 struct pet_implication
**implications
;
3236 implication
= new_implication(map
, satisfied
);
3237 if (!scop
|| !implication
)
3240 ctx
= isl_set_get_ctx(scop
->context
);
3241 implications
= isl_realloc_array(ctx
, scop
->implications
,
3242 struct pet_implication
*,
3243 scop
->n_implication
+ 1);
3246 scop
->implications
= implications
;
3247 scop
->implications
[scop
->n_implication
] = implication
;
3248 scop
->n_implication
++;
3252 pet_implication_free(implication
);
3253 return pet_scop_free(scop
);
3256 /* Given an access expression, check if it is data dependent.
3257 * If so, set *found and abort the search.
3259 static int is_data_dependent(struct pet_expr
*expr
, void *user
)
3271 /* Does "scop" contain any data dependent accesses?
3273 * Check the body of each statement for such accesses.
3275 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3283 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3284 int r
= pet_expr_foreach_access_expr(scop
->stmts
[i
]->body
,
3285 &is_data_dependent
, &found
);
3286 if (r
< 0 && !found
)
3295 /* Does "scop" contain and data dependent conditions?
3297 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3304 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3305 if (scop
->stmts
[i
]->n_arg
> 0)
3311 /* Keep track of the "input" file inside the (extended) "scop".
3313 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3315 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3325 /* Print the original code corresponding to "scop" to printer "p".
3327 * pet_scop_print_original can only be called from
3328 * a pet_transform_C_source callback. This means that the input
3329 * file is stored in the extended scop and that the printer prints
3332 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3333 __isl_take isl_printer
*p
)
3335 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3339 return isl_printer_free(p
);
3342 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3343 "no input file stored in scop",
3344 return isl_printer_free(p
));
3346 output
= isl_printer_get_file(p
);
3348 return isl_printer_free(p
);
3350 if (copy(ext
->input
, output
, scop
->start
, scop
->end
) < 0)
3351 return isl_printer_free(p
);