pet_expr_access_set_access: set read/write on non-empty access relation
[pet.git] / context.c
blob515c7a54722abddd14bca7350aaba5bf37750cfb
1 /*
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
7 * are met:
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
32 * Leiden University.
35 #include <isl/aff.h>
37 #include "aff.h"
38 #include "context.h"
39 #include "expr.h"
40 #include "expr_arg.h"
41 #include "nest.h"
42 #include "tree.h"
44 /* A pet_context represents the context in which a pet_expr
45 * in converted to an affine expression.
47 * "domain" prescribes the domain of the affine expressions.
49 * "assignments" maps variable names to their currently known values.
50 * Internally, the domains of the values may be equal to some prefix
51 * of the space of "domain", but the domains are updated to be
52 * equal to the space of "domain" before passing them to the user.
54 * If "allow_nested" is set, then the affine expression created
55 * in this context may involve new parameters that encode a pet_expr.
57 struct pet_context {
58 int ref;
60 isl_set *domain;
61 isl_id_to_pw_aff *assignments;
62 int allow_nested;
65 /* Create a pet_context with the given domain, assignments,
66 * and value for allow_nested.
68 static __isl_give pet_context *context_alloc(__isl_take isl_set *domain,
69 __isl_take isl_id_to_pw_aff *assignments, int allow_nested)
71 pet_context *pc;
73 if (!domain || !assignments)
74 goto error;
76 pc = isl_calloc_type(isl_set_get_ctx(domain), struct pet_context);
77 if (!pc)
78 goto error;
80 pc->ref = 1;
81 pc->domain = domain;
82 pc->assignments = assignments;
83 pc->allow_nested = allow_nested;
85 return pc;
86 error:
87 isl_set_free(domain);
88 isl_id_to_pw_aff_free(assignments);
89 return NULL;
92 /* Create a pet_context with the given domain.
94 * Initially, there are no assigned values and parameters that
95 * encode a pet_expr are not allowed.
97 __isl_give pet_context *pet_context_alloc(__isl_take isl_set *domain)
99 isl_id_to_pw_aff *assignments;
101 if (!domain)
102 return NULL;
104 assignments = isl_id_to_pw_aff_alloc(isl_set_get_ctx(domain), 0);;
105 return context_alloc(domain, assignments, 0);
108 /* Return an independent duplicate of "pc".
110 static __isl_give pet_context *pet_context_dup(__isl_keep pet_context *pc)
112 pet_context *dup;
114 if (!pc)
115 return NULL;
117 dup = context_alloc(isl_set_copy(pc->domain),
118 isl_id_to_pw_aff_copy(pc->assignments),
119 pc->allow_nested);
121 return dup;
124 /* Return a pet_context that is equal to "pc" and that has only one reference.
126 static __isl_give pet_context *pet_context_cow(__isl_take pet_context *pc)
128 if (!pc)
129 return NULL;
131 if (pc->ref == 1)
132 return pc;
133 pc->ref--;
134 return pet_context_dup(pc);
137 /* Return an extra reference to "pc".
139 __isl_give pet_context *pet_context_copy(__isl_keep pet_context *pc)
141 if (!pc)
142 return NULL;
144 pc->ref++;
145 return pc;
148 /* Free a reference to "pc" and return NULL.
150 __isl_null pet_context *pet_context_free(__isl_take pet_context *pc)
152 if (!pc)
153 return NULL;
154 if (--pc->ref > 0)
155 return NULL;
157 isl_set_free(pc->domain);
158 isl_id_to_pw_aff_free(pc->assignments);
159 free(pc);
160 return NULL;
163 /* Return the isl_ctx in which "pc" was created.
165 isl_ctx *pet_context_get_ctx(__isl_keep pet_context *pc)
167 return pc ? isl_set_get_ctx(pc->domain) : NULL;
170 /* Return the domain of "pc".
172 __isl_give isl_set *pet_context_get_domain(__isl_keep pet_context *pc)
174 if (!pc)
175 return NULL;
176 return isl_set_copy(pc->domain);
179 /* Return the domain of "pc" in a form that is suitable
180 * for use as a gist context.
181 * In particular, remove all references to nested expression parameters
182 * so that they do not get introduced in the gisted expression.
184 __isl_give isl_set *pet_context_get_gist_domain(__isl_keep pet_context *pc)
186 isl_set *domain;
188 domain = pet_context_get_domain(pc);
189 domain = pet_nested_remove_from_set(domain);
190 return domain;
193 /* Return the domain space of "pc".
195 * The domain of "pc" may have constraints involving parameters
196 * that encode a pet_expr. These parameters are not relevant
197 * outside this domain. Furthermore, they need to be resolved
198 * from the final result, so we do not want to propagate them needlessly.
200 __isl_give isl_space *pet_context_get_space(__isl_keep pet_context *pc)
202 isl_space *space;
204 if (!pc)
205 return NULL;
207 space = isl_set_get_space(pc->domain);
208 space = pet_nested_remove_from_space(space);
209 return space;
212 /* Return the dimension of the domain space of "pc".
214 unsigned pet_context_dim(__isl_keep pet_context *pc)
216 if (!pc)
217 return 0;
218 return isl_set_dim(pc->domain, isl_dim_set);
221 /* Return the assignments of "pc".
223 __isl_give isl_id_to_pw_aff *pet_context_get_assignments(
224 __isl_keep pet_context *pc)
226 if (!pc)
227 return NULL;
228 return isl_id_to_pw_aff_copy(pc->assignments);
231 /* Is "id" assigned any value in "pc"?
233 int pet_context_is_assigned(__isl_keep pet_context *pc, __isl_keep isl_id *id)
235 if (!pc || !id)
236 return -1;
237 return isl_id_to_pw_aff_has(pc->assignments, id);
240 /* Return the value assigned to "id" in "pc".
242 * Some dimensions may have been added to pc->domain after the value
243 * associated to "id" was added. We therefore need to adjust the domain
244 * of the stored value to match pc->domain by adding the missing
245 * dimensions.
247 __isl_give isl_pw_aff *pet_context_get_value(__isl_keep pet_context *pc,
248 __isl_take isl_id *id)
250 int dim;
251 isl_pw_aff *pa;
252 isl_multi_aff *ma;
254 if (!pc || !id)
255 goto error;
257 pa = isl_id_to_pw_aff_get(pc->assignments, id);
258 dim = isl_pw_aff_dim(pa, isl_dim_in);
259 if (dim == isl_set_dim(pc->domain, isl_dim_set))
260 return pa;
262 ma = pet_prefix_projection(pet_context_get_space(pc), dim);
263 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
265 return pa;
266 error:
267 isl_id_free(id);
268 return NULL;
271 /* Assign the value "value" to "id" in "pc", replacing the previously
272 * assigned value, if any.
274 __isl_give pet_context *pet_context_set_value(__isl_take pet_context *pc,
275 __isl_take isl_id *id, isl_pw_aff *value)
277 pc = pet_context_cow(pc);
278 if (!pc)
279 goto error;
280 pc->assignments = isl_id_to_pw_aff_set(pc->assignments, id, value);
281 if (!pc->assignments)
282 return pet_context_free(pc);
283 return pc;
284 error:
285 isl_id_free(id);
286 isl_pw_aff_free(value);
287 return NULL;
290 /* Remove any assignment to "id" in "pc".
292 __isl_give pet_context *pet_context_clear_value(__isl_keep pet_context *pc,
293 __isl_take isl_id *id)
295 pc = pet_context_cow(pc);
296 if (!pc)
297 goto error;
298 pc->assignments = isl_id_to_pw_aff_drop(pc->assignments, id);
299 if (!pc->assignments)
300 return pet_context_free(pc);
301 return pc;
302 error:
303 isl_id_free(id);
304 return NULL;
307 /* Are affine expressions created in this context allowed to involve
308 * parameters that encode a pet_expr?
310 int pet_context_allow_nesting(__isl_keep pet_context *pc)
312 if (!pc)
313 return -1;
314 return pc->allow_nested;
317 /* Allow affine expressions created in this context to involve
318 * parameters that encode a pet_expr based on the value of "allow_nested".
320 __isl_give pet_context *pet_context_set_allow_nested(__isl_take pet_context *pc,
321 int allow_nested)
323 if (!pc)
324 return NULL;
325 if (pc->allow_nested == allow_nested)
326 return pc;
327 pc = pet_context_cow(pc);
328 if (!pc)
329 return NULL;
330 pc->allow_nested = allow_nested;
331 return pc;
334 /* If the access expression "expr" writes to a (non-virtual) scalar,
335 * then remove any assignment to the scalar in "pc".
337 static int clear_write(__isl_keep pet_expr *expr, void *user)
339 isl_id *id;
340 pet_context **pc = (pet_context **) user;
342 if (!pet_expr_access_is_write(expr))
343 return 0;
344 if (!pet_expr_is_scalar_access(expr))
345 return 0;
347 id = pet_expr_access_get_id(expr);
348 if (isl_id_get_user(id))
349 *pc = pet_context_clear_value(*pc, id);
350 else
351 isl_id_free(id);
353 return 0;
356 /* Look for any writes to scalar variables in "expr" and
357 * remove any assignment to them in "pc".
359 __isl_give pet_context *pet_context_clear_writes_in_expr(
360 __isl_take pet_context *pc, __isl_keep pet_expr *expr)
362 if (pet_expr_foreach_access_expr(expr, &clear_write, &pc) < 0)
363 pc = pet_context_free(pc);
365 return pc;
368 /* Look for any writes to scalar variables in "tree" and
369 * remove any assignment to them in "pc".
371 __isl_give pet_context *pet_context_clear_writes_in_tree(
372 __isl_take pet_context *pc, __isl_keep pet_tree *tree)
374 if (pet_tree_foreach_access_expr(tree, &clear_write, &pc) < 0)
375 pc = pet_context_free(pc);
377 return pc;
380 /* Internal data structure for pet_context_add_parameters.
382 * "pc" is the context that is being updated.
383 * "get_array_size" is a callback function that can be used to determine
384 * the size of the array that is accessed by a given access expression.
385 * "user" is the user data for this callback.
387 struct pet_context_add_parameter_data {
388 pet_context *pc;
389 __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access,
390 void *user);
391 void *user;
394 /* Given an access expression "expr", add a parameter assignment to data->pc
395 * to the variable being accessed, provided it is a read from an integer
396 * scalar variable.
397 * If an array is being accesed, then recursively call the function
398 * on each of the access expressions in the size expression of the array.
400 static int add_parameter(__isl_keep pet_expr *expr, void *user)
402 struct pet_context_add_parameter_data *data = user;
403 int pos;
404 isl_id *id;
405 isl_space *space;
406 isl_local_space *ls;
407 isl_aff *aff;
408 isl_pw_aff *pa;
410 if (!pet_expr_is_scalar_access(expr)) {
411 pet_expr *size = data->get_array_size(expr, data->user);
412 if (pet_expr_foreach_access_expr(size,
413 &add_parameter, data) < 0)
414 data->pc = pet_context_free(data->pc);
415 pet_expr_free(size);
416 return 0;
418 if (!pet_expr_access_is_read(expr))
419 return 0;
420 if (pet_expr_get_type_size(expr) == 0)
421 return 0;
423 id = pet_expr_access_get_id(expr);
424 if (pet_context_is_assigned(data->pc, id)) {
425 isl_id_free(id);
426 return 0;
429 space = pet_context_get_space(data->pc);
430 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
431 if (pos < 0) {
432 pos = isl_space_dim(space, isl_dim_param);
433 space = isl_space_add_dims(space, isl_dim_param, 1);
434 space = isl_space_set_dim_id(space, isl_dim_param, pos,
435 isl_id_copy(id));
438 ls = isl_local_space_from_space(space);
439 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
440 pa = isl_pw_aff_from_aff(aff);
441 data->pc = pet_context_set_value(data->pc, id, pa);
443 return 0;
446 /* Add an assignment to "pc" for each parameter in "tree".
447 * "get_array_size" is a callback function that can be used to determine
448 * the size of the array that is accessed by a given access expression.
450 * We initially treat as parameters any integer variable that is read
451 * anywhere in "tree" or in any of the size expressions for any of
452 * the arrays accessed in "tree".
453 * Then we remove from those variables that are written anywhere
454 * inside "tree".
456 __isl_give pet_context *pet_context_add_parameters(__isl_take pet_context *pc,
457 __isl_keep pet_tree *tree,
458 __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access,
459 void *user), void *user)
461 struct pet_context_add_parameter_data data;
463 data.pc = pc;
464 data.get_array_size = get_array_size;
465 data.user = user;
466 if (pet_tree_foreach_access_expr(tree, &add_parameter, &data) < 0)
467 data.pc = pet_context_free(data.pc);
469 data.pc = pet_context_clear_writes_in_tree(data.pc, tree);
471 return data.pc;
474 /* Given an access expression, check if it reads a scalar variable
475 * that has a known value in "pc".
476 * If so, then replace the access by an access to that value.
478 static __isl_give pet_expr *access_plug_in_affine_read(
479 __isl_take pet_expr *expr, void *user)
481 pet_context *pc = user;
482 isl_pw_aff *pa;
484 if (pet_expr_access_is_write(expr))
485 return expr;
486 if (!pet_expr_is_scalar_access(expr))
487 return expr;
489 pa = pet_expr_extract_affine(expr, pc);
490 if (!pa)
491 return pet_expr_free(expr);
492 if (isl_pw_aff_involves_nan(pa)) {
493 isl_pw_aff_free(pa);
494 return expr;
497 pet_expr_free(expr);
498 expr = pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa));
500 return expr;
503 /* Replace every read access in "expr" to a scalar variable
504 * that has a known value in "pc" by that known value.
506 static __isl_give pet_expr *plug_in_affine_read(__isl_take pet_expr *expr,
507 __isl_keep pet_context *pc)
509 return pet_expr_map_access(expr, &access_plug_in_affine_read, pc);
512 /* Evaluate "expr" in the context of "pc".
514 * In particular, we first make sure that all the access expressions
515 * inside "expr" have the same domain as "pc".
516 * Then, we plug in affine expressions for scalar reads and
517 * plug in the arguments of all access expressions in "expr".
519 __isl_give pet_expr *pet_context_evaluate_expr(__isl_keep pet_context *pc,
520 __isl_take pet_expr *expr)
522 expr = pet_expr_insert_domain(expr, pet_context_get_space(pc));
523 expr = plug_in_affine_read(expr, pc);
524 return pet_expr_plug_in_args(expr, pc);
527 /* Wrapper around pet_context_evaluate_expr
528 * for use as a callback to pet_tree_map_expr.
530 static __isl_give pet_expr *evaluate_expr(__isl_take pet_expr *expr,
531 void *user)
533 pet_context *pc = user;
535 return pet_context_evaluate_expr(pc, expr);
538 /* Evaluate "tree" in the context of "pc".
539 * That is, evaluate all the expressions of "tree" in the context of "pc".
541 __isl_give pet_tree *pet_context_evaluate_tree(__isl_keep pet_context *pc,
542 __isl_take pet_tree *tree)
544 return pet_tree_map_expr(tree, &evaluate_expr, pc);
547 /* Add an unbounded inner dimension "id" to pc->domain.
549 * The assignments are not adjusted here and therefore keep
550 * their original domain. These domains need to be adjusted before
551 * these assigned values can be used. This is taken care of by
552 * pet_context_get_value.
554 static __isl_give pet_context *extend_domain(__isl_take pet_context *pc,
555 __isl_take isl_id *id)
557 int pos;
559 pc = pet_context_cow(pc);
560 if (!pc || !id)
561 goto error;
563 pos = pet_context_dim(pc);
564 pc->domain = isl_set_add_dims(pc->domain, isl_dim_set, 1);
565 pc->domain = isl_set_set_dim_id(pc->domain, isl_dim_set, pos, id);
566 if (!pc->domain)
567 return pet_context_free(pc);
569 return pc;
570 error:
571 pet_context_free(pc);
572 isl_id_free(id);
573 return NULL;
576 /* Add an unbounded inner iterator "id" to pc->domain.
577 * Additionally, mark the variable "id" as having the value of this
578 * new inner iterator.
580 __isl_give pet_context *pet_context_add_inner_iterator(
581 __isl_take pet_context *pc, __isl_take isl_id *id)
583 int pos;
584 isl_space *space;
585 isl_local_space *ls;
586 isl_aff *aff;
587 isl_pw_aff *pa;
589 if (!pc || !id)
590 goto error;
592 pos = pet_context_dim(pc);
593 pc = extend_domain(pc, isl_id_copy(id));
594 if (!pc)
595 goto error;
597 space = pet_context_get_space(pc);
598 ls = isl_local_space_from_space(space);
599 aff = isl_aff_var_on_domain(ls, isl_dim_set, pos);
600 pa = isl_pw_aff_from_aff(aff);
602 pc = pet_context_set_value(pc, id, pa);
604 return pc;
605 error:
606 pet_context_free(pc);
607 isl_id_free(id);
608 return NULL;
611 /* Add an inner iterator to pc->domain.
612 * In particular, extend the domain with an inner loop { [t] : t >= 0 }.
614 __isl_give pet_context *pet_context_add_infinite_loop(
615 __isl_take pet_context *pc)
617 int dim;
618 isl_ctx *ctx;
619 isl_id *id;
621 if (!pc)
622 return NULL;
624 dim = pet_context_dim(pc);
625 ctx = pet_context_get_ctx(pc);
626 id = isl_id_alloc(ctx, "t", NULL);
627 pc = extend_domain(pc, id);
628 pc = pet_context_cow(pc);
629 if (!pc)
630 return NULL;
631 pc->domain = isl_set_lower_bound_si(pc->domain, isl_dim_set, dim, 0);
632 if (!pc->domain)
633 return pet_context_free(pc);
635 return pc;
638 /* Internal data structure for preimage_domain.
640 * "ma" is the function under which the preimage should be computed.
641 * "assignments" collects the results.
643 struct pet_preimage_domain_data {
644 isl_multi_aff *ma;
645 isl_id_to_pw_aff *assignments;
648 /* Add the assignment to "key" of the preimage of "val" under data->ma
649 * to data->assignments.
651 * Some dimensions may have been added to the domain of the enclosing
652 * pet_context after the value "val" was added. We therefore need to
653 * adjust the domain of "val" to match the range of data->ma (which
654 * in turn matches the domain of the pet_context), by adding the missing
655 * dimensions.
657 static int preimage_domain_pair(__isl_take isl_id *key,
658 __isl_take isl_pw_aff *val, void *user)
660 struct pet_preimage_domain_data *data = user;
661 int dim;
662 isl_multi_aff *ma;
664 ma = isl_multi_aff_copy(data->ma);
666 dim = isl_pw_aff_dim(val, isl_dim_in);
667 if (dim != isl_multi_aff_dim(data->ma, isl_dim_out)) {
668 isl_space *space;
669 isl_multi_aff *proj;
670 space = isl_multi_aff_get_space(data->ma);
671 space = isl_space_range(space);
672 proj = pet_prefix_projection(space, dim);
673 ma = isl_multi_aff_pullback_multi_aff(proj, ma);
676 val = isl_pw_aff_pullback_multi_aff(val, ma);
677 data->assignments = isl_id_to_pw_aff_set(data->assignments, key, val);
679 return 0;
682 /* Compute the preimage of "assignments" under the function represented by "ma".
683 * In other words, plug in "ma" in the domains of the assigned values.
685 static __isl_give isl_id_to_pw_aff *preimage_domain(
686 __isl_take isl_id_to_pw_aff *assignments, __isl_keep isl_multi_aff *ma)
688 struct pet_preimage_domain_data data = { ma };
689 isl_ctx *ctx;
691 ctx = isl_id_to_pw_aff_get_ctx(assignments);
692 data.assignments = isl_id_to_pw_aff_alloc(ctx, 0);
693 if (isl_id_to_pw_aff_foreach(assignments, &preimage_domain_pair,
694 &data) < 0)
695 data.assignments = isl_id_to_pw_aff_free(data.assignments);
696 isl_id_to_pw_aff_free(assignments);
698 return data.assignments;
701 /* Compute the preimage of "pc" under the function represented by "ma".
702 * In other words, plug in "ma" in the domain of "pc".
704 __isl_give pet_context *pet_context_preimage_domain(__isl_take pet_context *pc,
705 __isl_keep isl_multi_aff *ma)
707 pc = pet_context_cow(pc);
708 if (!pc)
709 return NULL;
710 pc->domain = isl_set_preimage_multi_aff(pc->domain,
711 isl_multi_aff_copy(ma));
712 pc->assignments = preimage_domain(pc->assignments, ma);
713 if (!pc->domain || !pc->assignments)
714 return pet_context_free(pc);
715 return pc;
718 /* Add the constraints of "set" to the domain of "pc".
720 __isl_give pet_context *pet_context_intersect_domain(__isl_take pet_context *pc,
721 __isl_take isl_set *set)
723 pc = pet_context_cow(pc);
724 if (!pc)
725 goto error;
726 pc->domain = isl_set_intersect(pc->domain, set);
727 if (!pc->domain)
728 return pet_context_free(pc);
729 return pc;
730 error:
731 pet_context_free(pc);
732 isl_set_free(set);
733 return NULL;
736 void pet_context_dump(__isl_keep pet_context *pc)
738 if (!pc)
739 return;
740 fprintf(stderr, "domain: ");
741 isl_set_dump(pc->domain);
742 fprintf(stderr, "assignments: ");
743 isl_id_to_pw_aff_dump(pc->assignments);
744 fprintf(stderr, "nesting allowed: %d\n", pc->allow_nested);