2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 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
43 /* A pet_context represents the context in which a pet_expr
44 * in converted to an affine expression.
46 * "domain" prescribes the domain of the affine expressions.
48 * "assignments" maps variable names to their currently known values.
49 * Internally, the domains of the values may be equal to some prefix
50 * of the space of "domain", but the domains are updated to be
51 * equal to the space of "domain" before passing them to the user.
53 * If "allow_nested" is set, then the affine expression created
54 * in this context may involve new parameters that encode a pet_expr.
60 isl_id_to_pw_aff
*assignments
;
64 /* Create a pet_context with the given domain, assignments,
65 * and value for allow_nested.
67 static __isl_give pet_context
*context_alloc(__isl_take isl_set
*domain
,
68 __isl_take isl_id_to_pw_aff
*assignments
, int allow_nested
)
72 if (!domain
|| !assignments
)
75 pc
= isl_calloc_type(isl_set_get_ctx(domain
), struct pet_context
);
81 pc
->assignments
= assignments
;
82 pc
->allow_nested
= allow_nested
;
87 isl_id_to_pw_aff_free(assignments
);
91 /* Create a pet_context with the given domain.
93 * Initially, there are no assigned values and parameters that
94 * encode a pet_expr are not allowed.
96 __isl_give pet_context
*pet_context_alloc(__isl_take isl_set
*domain
)
98 isl_id_to_pw_aff
*assignments
;
103 assignments
= isl_id_to_pw_aff_alloc(isl_set_get_ctx(domain
), 0);;
104 return context_alloc(domain
, assignments
, 0);
107 /* Return an independent duplicate of "pc".
109 static __isl_give pet_context
*pet_context_dup(__isl_keep pet_context
*pc
)
116 dup
= context_alloc(isl_set_copy(pc
->domain
),
117 isl_id_to_pw_aff_copy(pc
->assignments
),
123 /* Return a pet_context that is equal to "pc" and that has only one reference.
125 static __isl_give pet_context
*pet_context_cow(__isl_take pet_context
*pc
)
133 return pet_context_dup(pc
);
136 /* Return an extra reference to "pc".
138 __isl_give pet_context
*pet_context_copy(__isl_keep pet_context
*pc
)
147 /* Free a reference to "pc" and return NULL.
149 __isl_null pet_context
*pet_context_free(__isl_take pet_context
*pc
)
156 isl_set_free(pc
->domain
);
157 isl_id_to_pw_aff_free(pc
->assignments
);
162 /* Return the isl_ctx in which "pc" was created.
164 isl_ctx
*pet_context_get_ctx(__isl_keep pet_context
*pc
)
166 return pc
? isl_set_get_ctx(pc
->domain
) : NULL
;
169 /* Return the domain of "pc".
171 __isl_give isl_set
*pet_context_get_domain(__isl_keep pet_context
*pc
)
175 return isl_set_copy(pc
->domain
);
178 /* Return the domain of "pc" in a form that is suitable
179 * for use as a gist context.
180 * In particular, remove all references to nested expression parameters
181 * so that they do not get introduced in the gisted expression.
183 __isl_give isl_set
*pet_context_get_gist_domain(__isl_keep pet_context
*pc
)
187 domain
= pet_context_get_domain(pc
);
188 domain
= pet_nested_remove_from_set(domain
);
192 /* Return the domain space of "pc".
194 * The domain of "pc" may have constraints involving parameters
195 * that encode a pet_expr. These parameters are not relevant
196 * outside this domain. Furthermore, they need to be resolved
197 * from the final result, so we do not want to propagate them needlessly.
199 __isl_give isl_space
*pet_context_get_space(__isl_keep pet_context
*pc
)
206 space
= isl_set_get_space(pc
->domain
);
207 space
= pet_nested_remove_from_space(space
);
211 /* Return the dimension of the domain space of "pc".
213 unsigned pet_context_dim(__isl_keep pet_context
*pc
)
217 return isl_set_dim(pc
->domain
, isl_dim_set
);
220 /* Return the assignments of "pc".
222 __isl_give isl_id_to_pw_aff
*pet_context_get_assignments(
223 __isl_keep pet_context
*pc
)
227 return isl_id_to_pw_aff_copy(pc
->assignments
);
230 /* Is "id" assigned any value in "pc"?
232 int pet_context_is_assigned(__isl_keep pet_context
*pc
, __isl_keep isl_id
*id
)
236 return isl_id_to_pw_aff_has(pc
->assignments
, id
);
239 /* Return the value assigned to "id" in "pc".
241 * Some dimensions may have been added to pc->domain after the value
242 * associated to "id" was added. We therefore need to adjust the domain
243 * of the stored value to match pc->domain by adding the missing
246 __isl_give isl_pw_aff
*pet_context_get_value(__isl_keep pet_context
*pc
,
247 __isl_take isl_id
*id
)
256 pa
= isl_id_to_pw_aff_get(pc
->assignments
, id
);
257 dim
= isl_pw_aff_dim(pa
, isl_dim_in
);
258 if (dim
== isl_set_dim(pc
->domain
, isl_dim_set
))
261 ma
= pet_prefix_projection(pet_context_get_space(pc
), dim
);
262 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
270 /* Assign the value "value" to "id" in "pc", replacing the previously
271 * assigned value, if any.
273 __isl_give pet_context
*pet_context_set_value(__isl_take pet_context
*pc
,
274 __isl_take isl_id
*id
, isl_pw_aff
*value
)
276 pc
= pet_context_cow(pc
);
279 pc
->assignments
= isl_id_to_pw_aff_set(pc
->assignments
, id
, value
);
280 if (!pc
->assignments
)
281 return pet_context_free(pc
);
285 isl_pw_aff_free(value
);
289 /* Remove any assignment to "id" in "pc".
291 __isl_give pet_context
*pet_context_clear_value(__isl_keep pet_context
*pc
,
292 __isl_take isl_id
*id
)
294 pc
= pet_context_cow(pc
);
297 pc
->assignments
= isl_id_to_pw_aff_drop(pc
->assignments
, id
);
298 if (!pc
->assignments
)
299 return pet_context_free(pc
);
306 /* Are affine expressions created in this context allowed to involve
307 * parameters that encode a pet_expr?
309 int pet_context_allow_nesting(__isl_keep pet_context
*pc
)
313 return pc
->allow_nested
;
316 /* Allow affine expressions created in this context to involve
317 * parameters that encode a pet_expr based on the value of "allow_nested".
319 __isl_give pet_context
*pet_context_set_allow_nested(__isl_take pet_context
*pc
,
324 if (pc
->allow_nested
== allow_nested
)
326 pc
= pet_context_cow(pc
);
329 pc
->allow_nested
= allow_nested
;
333 /* If the access expression "expr" writes to a (non-virtual) scalar,
334 * then remove any assignment to the scalar in "pc".
336 static int clear_write(__isl_keep pet_expr
*expr
, void *user
)
339 pet_context
**pc
= (pet_context
**) user
;
341 if (!pet_expr_access_is_write(expr
))
343 if (!pet_expr_is_scalar_access(expr
))
346 id
= pet_expr_access_get_id(expr
);
347 if (isl_id_get_user(id
))
348 *pc
= pet_context_clear_value(*pc
, id
);
355 /* Look for any writes to scalar variables in "expr" and
356 * remove any assignment to them in "pc".
358 __isl_give pet_context
*pet_context_clear_writes_in_expr(
359 __isl_take pet_context
*pc
, __isl_keep pet_expr
*expr
)
361 if (pet_expr_foreach_access_expr(expr
, &clear_write
, &pc
) < 0)
362 pc
= pet_context_free(pc
);
367 /* Look for any writes to scalar variables in "tree" and
368 * remove any assignment to them in "pc".
370 __isl_give pet_context
*pet_context_clear_writes_in_tree(
371 __isl_take pet_context
*pc
, __isl_keep pet_tree
*tree
)
373 if (pet_tree_foreach_access_expr(tree
, &clear_write
, &pc
) < 0)
374 pc
= pet_context_free(pc
);
379 /* Internal data structure for pet_context_add_parameters.
381 * "pc" is the context that is being updated.
382 * "get_array_size" is a callback function that can be used to determine
383 * the size of the array that is accessed by a given access expression.
384 * "user" is the user data for this callback.
386 struct pet_context_add_parameter_data
{
388 __isl_give pet_expr
*(*get_array_size
)(__isl_keep pet_expr
*access
,
393 /* Given an access expression "expr", add a parameter assignment to data->pc
394 * to the variable being accessed, provided it is a read from an integer
396 * If an array is being accesed, then recursively call the function
397 * on each of the access expressions in the size expression of the array.
399 static int add_parameter(__isl_keep pet_expr
*expr
, void *user
)
401 struct pet_context_add_parameter_data
*data
= user
;
409 if (!pet_expr_is_scalar_access(expr
)) {
410 pet_expr
*size
= data
->get_array_size(expr
, data
->user
);
411 if (pet_expr_foreach_access_expr(size
,
412 &add_parameter
, data
) < 0)
413 data
->pc
= pet_context_free(data
->pc
);
417 if (!pet_expr_access_is_read(expr
))
419 if (pet_expr_get_type_size(expr
) == 0)
422 id
= pet_expr_access_get_id(expr
);
423 if (pet_context_is_assigned(data
->pc
, id
)) {
428 space
= pet_context_get_space(data
->pc
);
429 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
431 pos
= isl_space_dim(space
, isl_dim_param
);
432 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
433 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
,
437 ls
= isl_local_space_from_space(space
);
438 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
439 pa
= isl_pw_aff_from_aff(aff
);
440 data
->pc
= pet_context_set_value(data
->pc
, id
, pa
);
445 /* Add an assignment to "pc" for each parameter in "tree".
446 * "get_array_size" is a callback function that can be used to determine
447 * the size of the array that is accessed by a given access expression.
449 * We initially treat as parameters any integer variable that is read
450 * anywhere in "tree" or in any of the size expressions for any of
451 * the arrays accessed in "tree".
452 * Then we remove from those variables that are written anywhere
455 __isl_give pet_context
*pet_context_add_parameters(__isl_take pet_context
*pc
,
456 __isl_keep pet_tree
*tree
,
457 __isl_give pet_expr
*(*get_array_size
)(__isl_keep pet_expr
*access
,
458 void *user
), void *user
)
460 struct pet_context_add_parameter_data data
;
463 data
.get_array_size
= get_array_size
;
465 if (pet_tree_foreach_access_expr(tree
, &add_parameter
, &data
) < 0)
466 data
.pc
= pet_context_free(data
.pc
);
468 data
.pc
= pet_context_clear_writes_in_tree(data
.pc
, tree
);
473 /* Given an access expression, check if it reads a scalar variable
474 * that has a known value in "pc".
475 * If so, then replace the access by an access to that value.
477 static __isl_give pet_expr
*access_plug_in_affine_read(
478 __isl_take pet_expr
*expr
, void *user
)
480 pet_context
*pc
= user
;
483 if (pet_expr_access_is_write(expr
))
485 if (!pet_expr_is_scalar_access(expr
))
488 pa
= pet_expr_extract_affine(expr
, pc
);
490 return pet_expr_free(expr
);
491 if (isl_pw_aff_involves_nan(pa
)) {
497 expr
= pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa
));
502 /* Replace every read access in "expr" to a scalar variable
503 * that has a known value in "pc" by that known value.
505 static __isl_give pet_expr
*plug_in_affine_read(__isl_take pet_expr
*expr
,
506 __isl_keep pet_context
*pc
)
508 return pet_expr_map_access(expr
, &access_plug_in_affine_read
, pc
);
511 /* Evaluate "expr" in the context of "pc".
513 * In particular, we first make sure that all the access expressions
514 * inside "expr" have the same domain as "pc".
515 * Then, we plug in affine expressions for scalar reads and
516 * plug in the arguments of all access expressions in "expr".
518 __isl_give pet_expr
*pet_context_evaluate_expr(__isl_keep pet_context
*pc
,
519 __isl_take pet_expr
*expr
)
521 expr
= pet_expr_insert_domain(expr
, pet_context_get_space(pc
));
522 expr
= plug_in_affine_read(expr
, pc
);
523 return pet_expr_plug_in_args(expr
, pc
);
526 /* Add an unbounded inner dimension "id" to pc->domain.
528 * The assignments are not adjusted here and therefore keep
529 * their original domain. These domains need to be adjusted before
530 * these assigned values can be used. This is taken care of by
531 * pet_context_get_value.
533 static __isl_give pet_context
*extend_domain(__isl_take pet_context
*pc
,
534 __isl_take isl_id
*id
)
538 pc
= pet_context_cow(pc
);
542 pos
= pet_context_dim(pc
);
543 pc
->domain
= isl_set_add_dims(pc
->domain
, isl_dim_set
, 1);
544 pc
->domain
= isl_set_set_dim_id(pc
->domain
, isl_dim_set
, pos
, id
);
546 return pet_context_free(pc
);
550 pet_context_free(pc
);
555 /* Add an unbounded inner iterator "id" to pc->domain.
556 * Additionally, mark the variable "id" as having the value of this
557 * new inner iterator.
559 __isl_give pet_context
*pet_context_add_inner_iterator(
560 __isl_take pet_context
*pc
, __isl_take isl_id
*id
)
571 pos
= pet_context_dim(pc
);
572 pc
= extend_domain(pc
, isl_id_copy(id
));
576 space
= pet_context_get_space(pc
);
577 ls
= isl_local_space_from_space(space
);
578 aff
= isl_aff_var_on_domain(ls
, isl_dim_set
, pos
);
579 pa
= isl_pw_aff_from_aff(aff
);
581 pc
= pet_context_set_value(pc
, id
, pa
);
585 pet_context_free(pc
);
590 /* Add an inner iterator to pc->domain.
591 * In particular, extend the domain with an inner loop { [t] : t >= 0 }.
593 __isl_give pet_context
*pet_context_add_infinite_loop(
594 __isl_take pet_context
*pc
)
603 dim
= pet_context_dim(pc
);
604 ctx
= pet_context_get_ctx(pc
);
605 id
= isl_id_alloc(ctx
, "t", NULL
);
606 pc
= extend_domain(pc
, id
);
607 pc
= pet_context_cow(pc
);
610 pc
->domain
= isl_set_lower_bound_si(pc
->domain
, isl_dim_set
, dim
, 0);
612 return pet_context_free(pc
);
617 /* Internal data structure for preimage_domain.
619 * "ma" is the function under which the preimage should be computed.
620 * "assignments" collects the results.
622 struct pet_preimage_domain_data
{
624 isl_id_to_pw_aff
*assignments
;
627 /* Add the assignment to "key" of the preimage of "val" under data->ma
628 * to data->assignments.
630 * Some dimensions may have been added to the domain of the enclosing
631 * pet_context after the value "val" was added. We therefore need to
632 * adjust the domain of "val" to match the range of data->ma (which
633 * in turn matches the domain of the pet_context), by adding the missing
636 static int preimage_domain_pair(__isl_take isl_id
*key
,
637 __isl_take isl_pw_aff
*val
, void *user
)
639 struct pet_preimage_domain_data
*data
= user
;
643 ma
= isl_multi_aff_copy(data
->ma
);
645 dim
= isl_pw_aff_dim(val
, isl_dim_in
);
646 if (dim
!= isl_multi_aff_dim(data
->ma
, isl_dim_out
)) {
649 space
= isl_multi_aff_get_space(data
->ma
);
650 space
= isl_space_range(space
);
651 proj
= pet_prefix_projection(space
, dim
);
652 ma
= isl_multi_aff_pullback_multi_aff(proj
, ma
);
655 val
= isl_pw_aff_pullback_multi_aff(val
, ma
);
656 data
->assignments
= isl_id_to_pw_aff_set(data
->assignments
, key
, val
);
661 /* Compute the preimage of "assignments" under the function represented by "ma".
662 * In other words, plug in "ma" in the domains of the assigned values.
664 static __isl_give isl_id_to_pw_aff
*preimage_domain(
665 __isl_take isl_id_to_pw_aff
*assignments
, __isl_keep isl_multi_aff
*ma
)
667 struct pet_preimage_domain_data data
= { ma
};
670 ctx
= isl_id_to_pw_aff_get_ctx(assignments
);
671 data
.assignments
= isl_id_to_pw_aff_alloc(ctx
, 0);
672 if (isl_id_to_pw_aff_foreach(assignments
, &preimage_domain_pair
,
674 data
.assignments
= isl_id_to_pw_aff_free(data
.assignments
);
675 isl_id_to_pw_aff_free(assignments
);
677 return data
.assignments
;
680 /* Compute the preimage of "pc" under the function represented by "ma".
681 * In other words, plug in "ma" in the domain of "pc".
683 __isl_give pet_context
*pet_context_preimage_domain(__isl_take pet_context
*pc
,
684 __isl_keep isl_multi_aff
*ma
)
686 pc
= pet_context_cow(pc
);
689 pc
->domain
= isl_set_preimage_multi_aff(pc
->domain
,
690 isl_multi_aff_copy(ma
));
691 pc
->assignments
= preimage_domain(pc
->assignments
, ma
);
692 if (!pc
->domain
|| !pc
->assignments
)
693 return pet_context_free(pc
);
697 /* Add the constraints of "set" to the domain of "pc".
699 __isl_give pet_context
*pet_context_intersect_domain(__isl_take pet_context
*pc
,
700 __isl_take isl_set
*set
)
702 pc
= pet_context_cow(pc
);
705 pc
->domain
= isl_set_intersect(pc
->domain
, set
);
707 return pet_context_free(pc
);
710 pet_context_free(pc
);
715 void pet_context_dump(__isl_keep pet_context
*pc
)
719 fprintf(stderr
, "domain: ");
720 isl_set_dump(pc
->domain
);
721 fprintf(stderr
, "assignments: ");
722 isl_id_to_pw_aff_dump(pc
->assignments
);
723 fprintf(stderr
, "nesting allowed: %d\n", pc
->allow_nested
);