pet 0.11.8
[pet.git] / context.c
blobfc338d369df3ad27025f10a6e4e5dc6c83903a0f
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2014 Ecole Normale Superieure. All rights reserved.
4 * Copyright 2016 Sven Verdoolaege. All rights reserved.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
25 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * The views and conclusions contained in the software and documentation
31 * are those of the authors and should not be interpreted as
32 * representing official policies, either expressed or implied, of
33 * Leiden University.
36 #include <isl/aff.h>
38 #include "aff.h"
39 #include "array.h"
40 #include "context.h"
41 #include "expr.h"
42 #include "expr_arg.h"
43 #include "nest.h"
44 #include "patch.h"
45 #include "tree.h"
46 #include "pet_expr_to_isl_pw_aff.h"
48 /* A pet_context represents the context in which a pet_expr
49 * in converted to an affine expression.
51 * "domain" prescribes the domain of the affine expressions.
53 * "assignments" maps variable names to their currently known values.
54 * Internally, the domains of the values may be equal to some prefix
55 * of the space of "domain", but the domains are updated to be
56 * equal to the space of "domain" before passing them to the user.
58 * If "allow_nested" is set, then the affine expression created
59 * in this context may involve new parameters that encode a pet_expr.
61 * "extracted_affine" caches the results of pet_expr_extract_affine.
62 * It may be NULL if no results have been cached so far and
63 * it is cleared (in pet_context_cow) whenever the context is changed.
65 struct pet_context {
66 int ref;
68 isl_set *domain;
69 isl_id_to_pw_aff *assignments;
70 int allow_nested;
72 pet_expr_to_isl_pw_aff *extracted_affine;
75 /* Create a pet_context with the given domain, assignments,
76 * and value for allow_nested.
78 static __isl_give pet_context *context_alloc(__isl_take isl_set *domain,
79 __isl_take isl_id_to_pw_aff *assignments, int allow_nested)
81 pet_context *pc;
83 if (!domain || !assignments)
84 goto error;
86 pc = isl_calloc_type(isl_set_get_ctx(domain), struct pet_context);
87 if (!pc)
88 goto error;
90 pc->ref = 1;
91 pc->domain = domain;
92 pc->assignments = assignments;
93 pc->allow_nested = allow_nested;
95 return pc;
96 error:
97 isl_set_free(domain);
98 isl_id_to_pw_aff_free(assignments);
99 return NULL;
102 /* Create a pet_context with the given domain.
104 * Initially, there are no assigned values and parameters that
105 * encode a pet_expr are not allowed.
107 __isl_give pet_context *pet_context_alloc(__isl_take isl_set *domain)
109 isl_id_to_pw_aff *assignments;
111 if (!domain)
112 return NULL;
114 assignments = isl_id_to_pw_aff_alloc(isl_set_get_ctx(domain), 0);
115 return context_alloc(domain, assignments, 0);
118 /* Return an independent duplicate of "pc".
120 static __isl_give pet_context *pet_context_dup(__isl_keep pet_context *pc)
122 pet_context *dup;
124 if (!pc)
125 return NULL;
127 dup = context_alloc(isl_set_copy(pc->domain),
128 isl_id_to_pw_aff_copy(pc->assignments),
129 pc->allow_nested);
131 return dup;
134 /* Return a pet_context that is equal to "pc" and that has only one reference.
136 * If "pc" itself only has one reference, then clear the cache of
137 * pet_expr_extract_affine results since the returned pet_context
138 * will be modified and the cached results may no longer be valid
139 * after these modifications.
141 static __isl_give pet_context *pet_context_cow(__isl_take pet_context *pc)
143 if (!pc)
144 return NULL;
146 if (pc->ref == 1) {
147 pet_expr_to_isl_pw_aff_free(pc->extracted_affine);
148 pc->extracted_affine = NULL;
149 return pc;
151 pc->ref--;
152 return pet_context_dup(pc);
155 /* Return an extra reference to "pc".
157 __isl_give pet_context *pet_context_copy(__isl_keep pet_context *pc)
159 if (!pc)
160 return NULL;
162 pc->ref++;
163 return pc;
166 /* Free a reference to "pc" and return NULL.
168 __isl_null pet_context *pet_context_free(__isl_take pet_context *pc)
170 if (!pc)
171 return NULL;
172 if (--pc->ref > 0)
173 return NULL;
175 isl_set_free(pc->domain);
176 isl_id_to_pw_aff_free(pc->assignments);
177 pet_expr_to_isl_pw_aff_free(pc->extracted_affine);
178 free(pc);
179 return NULL;
182 /* If an isl_pw_aff corresponding to "expr" has been cached in "pc",
183 * then return a copy of that isl_pw_aff.
184 * Otherwise, return (isl_bool_false, NULL).
186 __isl_give isl_maybe_isl_pw_aff pet_context_get_extracted_affine(
187 __isl_keep pet_context *pc, __isl_keep pet_expr *expr)
189 isl_maybe_isl_pw_aff m = { isl_bool_false, NULL };
191 if (!pc)
192 goto error;
193 if (!pc->extracted_affine)
194 return m;
195 return pet_expr_to_isl_pw_aff_try_get(pc->extracted_affine, expr);
196 error:
197 m.valid = isl_bool_error;
198 return m;
201 /* Keep track of the fact that "expr" maps to "pa" in "pc".
203 isl_stat pet_context_set_extracted_affine(__isl_keep pet_context *pc,
204 __isl_keep pet_expr *expr, __isl_keep isl_pw_aff *pa)
206 if (!pc || !expr)
207 return isl_stat_error;
209 if (!pc->extracted_affine) {
210 isl_ctx *ctx;
212 ctx = pet_context_get_ctx(pc);
213 pc->extracted_affine = pet_expr_to_isl_pw_aff_alloc(ctx, 1);
216 pc->extracted_affine = pet_expr_to_isl_pw_aff_set(pc->extracted_affine,
217 pet_expr_copy(expr), isl_pw_aff_copy(pa));
218 if (!pc->extracted_affine)
219 return isl_stat_error;
221 return isl_stat_ok;
224 /* Return the isl_ctx in which "pc" was created.
226 isl_ctx *pet_context_get_ctx(__isl_keep pet_context *pc)
228 return pc ? isl_set_get_ctx(pc->domain) : NULL;
231 /* Return the domain of "pc".
233 __isl_give isl_set *pet_context_get_domain(__isl_keep pet_context *pc)
235 if (!pc)
236 return NULL;
237 return isl_set_copy(pc->domain);
240 /* Return the domain of "pc" in a form that is suitable
241 * for use as a gist context.
242 * In particular, remove all references to nested expression parameters
243 * so that they do not get introduced in the gisted expression.
245 __isl_give isl_set *pet_context_get_gist_domain(__isl_keep pet_context *pc)
247 isl_set *domain;
249 domain = pet_context_get_domain(pc);
250 domain = pet_nested_remove_from_set(domain);
251 return domain;
254 /* Return the domain space of "pc".
256 * The domain of "pc" may have constraints involving parameters
257 * that encode a pet_expr. These parameters are not relevant
258 * outside this domain. Furthermore, they need to be resolved
259 * from the final result, so we do not want to propagate them needlessly.
261 __isl_give isl_space *pet_context_get_space(__isl_keep pet_context *pc)
263 isl_space *space;
265 if (!pc)
266 return NULL;
268 space = isl_set_get_space(pc->domain);
269 space = pet_nested_remove_from_space(space);
270 return space;
273 /* Return the dimension of the domain space of "pc".
275 unsigned pet_context_dim(__isl_keep pet_context *pc)
277 if (!pc)
278 return 0;
279 return isl_set_dim(pc->domain, isl_dim_set);
282 /* Return the assignments of "pc".
284 __isl_give isl_id_to_pw_aff *pet_context_get_assignments(
285 __isl_keep pet_context *pc)
287 if (!pc)
288 return NULL;
289 return isl_id_to_pw_aff_copy(pc->assignments);
292 /* Is "id" assigned any value in "pc"?
294 int pet_context_is_assigned(__isl_keep pet_context *pc, __isl_keep isl_id *id)
296 if (!pc || !id)
297 return -1;
298 return isl_id_to_pw_aff_has(pc->assignments, id);
301 /* Return the value assigned to "id" in "pc".
303 * Some dimensions may have been added to pc->domain after the value
304 * associated to "id" was added. We therefore need to adjust the domain
305 * of the stored value to match pc->domain by adding the missing
306 * dimensions.
308 __isl_give isl_pw_aff *pet_context_get_value(__isl_keep pet_context *pc,
309 __isl_take isl_id *id)
311 int dim;
312 isl_pw_aff *pa;
313 isl_multi_aff *ma;
315 if (!pc || !id)
316 goto error;
318 pa = isl_id_to_pw_aff_get(pc->assignments, id);
319 dim = isl_pw_aff_dim(pa, isl_dim_in);
320 if (dim == isl_set_dim(pc->domain, isl_dim_set))
321 return pa;
323 ma = pet_prefix_projection(pet_context_get_space(pc), dim);
324 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
326 return pa;
327 error:
328 isl_id_free(id);
329 return NULL;
332 /* Assign the value "value" to "id" in "pc", replacing the previously
333 * assigned value, if any.
335 __isl_give pet_context *pet_context_set_value(__isl_take pet_context *pc,
336 __isl_take isl_id *id, isl_pw_aff *value)
338 pc = pet_context_cow(pc);
339 if (!pc)
340 goto error;
341 pc->assignments = isl_id_to_pw_aff_set(pc->assignments, id, value);
342 if (!pc->assignments)
343 return pet_context_free(pc);
344 return pc;
345 error:
346 isl_id_free(id);
347 isl_pw_aff_free(value);
348 return NULL;
351 /* Remove any assignment to "id" in "pc".
353 __isl_give pet_context *pet_context_clear_value(__isl_keep pet_context *pc,
354 __isl_take isl_id *id)
356 pc = pet_context_cow(pc);
357 if (!pc)
358 goto error;
359 pc->assignments = isl_id_to_pw_aff_drop(pc->assignments, id);
360 if (!pc->assignments)
361 return pet_context_free(pc);
362 return pc;
363 error:
364 isl_id_free(id);
365 return NULL;
368 /* Are affine expressions created in this context allowed to involve
369 * parameters that encode a pet_expr?
371 int pet_context_allow_nesting(__isl_keep pet_context *pc)
373 if (!pc)
374 return -1;
375 return pc->allow_nested;
378 /* Allow affine expressions created in this context to involve
379 * parameters that encode a pet_expr based on the value of "allow_nested".
381 __isl_give pet_context *pet_context_set_allow_nested(__isl_take pet_context *pc,
382 int allow_nested)
384 if (!pc)
385 return NULL;
386 if (pc->allow_nested == allow_nested)
387 return pc;
388 pc = pet_context_cow(pc);
389 if (!pc)
390 return NULL;
391 pc->allow_nested = allow_nested;
392 return pc;
395 /* If the access expression "expr" writes to a (non-virtual) scalar,
396 * then remove any assignment to the scalar in "pc".
398 static int clear_write(__isl_keep pet_expr *expr, void *user)
400 isl_id *id;
401 pet_context **pc = (pet_context **) user;
403 if (!pet_expr_access_is_write(expr))
404 return 0;
405 if (!pet_expr_is_scalar_access(expr))
406 return 0;
408 id = pet_expr_access_get_id(expr);
409 if (isl_id_get_user(id))
410 *pc = pet_context_clear_value(*pc, id);
411 else
412 isl_id_free(id);
414 return 0;
417 /* Look for any writes to scalar variables in "expr" and
418 * remove any assignment to them in "pc".
420 __isl_give pet_context *pet_context_clear_writes_in_expr(
421 __isl_take pet_context *pc, __isl_keep pet_expr *expr)
423 if (pet_expr_foreach_access_expr(expr, &clear_write, &pc) < 0)
424 pc = pet_context_free(pc);
426 return pc;
429 /* Look for any writes to scalar variables in "tree" and
430 * remove any assignment to them in "pc".
432 __isl_give pet_context *pet_context_clear_writes_in_tree(
433 __isl_take pet_context *pc, __isl_keep pet_tree *tree)
435 if (pet_tree_foreach_access_expr(tree, &clear_write, &pc) < 0)
436 pc = pet_context_free(pc);
438 return pc;
441 /* Internal data structure for pet_context_add_parameters.
443 * "pc" is the context that is being updated.
444 * "get_array_size" is a callback function that can be used to determine
445 * the size of the array that is accessed by a given access expression.
446 * "user" is the user data for this callback.
448 struct pet_context_add_parameter_data {
449 pet_context *pc;
450 __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access,
451 void *user);
452 void *user;
455 /* Given an access expression "expr", add a parameter assignment to data->pc
456 * to the variable being accessed, provided it is a read from an integer
457 * scalar variable.
458 * If an array is being accesed, then recursively call the function
459 * on each of the access expressions in the size expression of the array.
461 static int add_parameter(__isl_keep pet_expr *expr, void *user)
463 struct pet_context_add_parameter_data *data = user;
464 int pos;
465 isl_id *id;
466 isl_space *space;
467 isl_local_space *ls;
468 isl_aff *aff;
469 isl_pw_aff *pa;
471 if (!pet_expr_is_scalar_access(expr)) {
472 pet_expr *size = data->get_array_size(expr, data->user);
473 if (pet_expr_foreach_access_expr(size,
474 &add_parameter, data) < 0)
475 data->pc = pet_context_free(data->pc);
476 pet_expr_free(size);
477 return 0;
479 if (!pet_expr_access_is_read(expr))
480 return 0;
481 if (pet_expr_get_type_size(expr) == 0)
482 return 0;
484 id = pet_expr_access_get_id(expr);
485 if (pet_context_is_assigned(data->pc, id)) {
486 isl_id_free(id);
487 return 0;
490 space = pet_context_get_space(data->pc);
491 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
492 if (pos < 0) {
493 pos = isl_space_dim(space, isl_dim_param);
494 space = isl_space_add_dims(space, isl_dim_param, 1);
495 space = isl_space_set_dim_id(space, isl_dim_param, pos,
496 isl_id_copy(id));
499 ls = isl_local_space_from_space(space);
500 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
501 pa = isl_pw_aff_from_aff(aff);
502 data->pc = pet_context_set_value(data->pc, id, pa);
504 return 0;
507 /* Add an assignment to "pc" for each parameter in "tree".
508 * "get_array_size" is a callback function that can be used to determine
509 * the size of the array that is accessed by a given access expression.
511 * We initially treat as parameters any integer variable that is read
512 * anywhere in "tree" or in any of the size expressions for any of
513 * the arrays accessed in "tree".
514 * Then we remove from those variables that are written anywhere
515 * inside "tree".
517 __isl_give pet_context *pet_context_add_parameters(__isl_take pet_context *pc,
518 __isl_keep pet_tree *tree,
519 __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access,
520 void *user), void *user)
522 struct pet_context_add_parameter_data data;
524 data.pc = pc;
525 data.get_array_size = get_array_size;
526 data.user = user;
527 if (pet_tree_foreach_access_expr(tree, &add_parameter, &data) < 0)
528 data.pc = pet_context_free(data.pc);
530 data.pc = pet_context_clear_writes_in_tree(data.pc, tree);
532 return data.pc;
535 /* Given an access expression, check if it reads a scalar variable
536 * that has a known value in "pc".
537 * If so, then replace the access by an access to that value.
539 static __isl_give pet_expr *access_plug_in_affine_read(
540 __isl_take pet_expr *expr, void *user)
542 pet_context *pc = user;
543 isl_pw_aff *pa;
545 if (pet_expr_access_is_write(expr))
546 return expr;
547 if (!pet_expr_is_scalar_access(expr))
548 return expr;
550 pa = pet_expr_extract_affine(expr, pc);
551 if (!pa)
552 return pet_expr_free(expr);
553 if (isl_pw_aff_involves_nan(pa)) {
554 isl_pw_aff_free(pa);
555 return expr;
558 pet_expr_free(expr);
559 expr = pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa));
561 return expr;
564 /* Replace every read access in "expr" to a scalar variable
565 * that has a known value in "pc" by that known value.
567 static __isl_give pet_expr *plug_in_affine_read(__isl_take pet_expr *expr,
568 __isl_keep pet_context *pc)
570 return pet_expr_map_access(expr, &access_plug_in_affine_read, pc);
573 /* Add an extra affine expression to "mpa" that is equal to
574 * an extra dimension in the range of the wrapped relation in the domain
575 * of "mpa". "n_arg" is the original number of dimensions in this range.
577 * That is, if "n_arg" is 0, then the input has the form
579 * D(i) -> [f(i)]
581 * and the output has the form
583 * [D(i) -> [y]] -> [f(i), y]
585 * If "n_arg" is different from 0, then the input has the form
587 * [D(i) -> [x]] -> [f(i,x)]
589 * with x consisting of "n_arg" dimensions, and the output has the form
591 * [D(i) -> [x,y]] -> [f(i,x), y]
594 * We first adjust the domain of "mpa" and then add the extra
595 * affine expression (y).
597 static __isl_give isl_multi_pw_aff *add_arg(__isl_take isl_multi_pw_aff *mpa,
598 int n_arg)
600 int dim;
601 isl_space *space;
602 isl_multi_aff *ma;
603 isl_multi_pw_aff *mpa2;
605 if (n_arg == 0) {
606 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
607 dim = isl_space_dim(space, isl_dim_set);
608 space = isl_space_from_domain(space);
609 space = isl_space_add_dims(space, isl_dim_set, 1);
610 ma = isl_multi_aff_domain_map(space);
611 } else {
612 isl_multi_aff *ma2;
613 isl_space *dom, *ran;
615 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
616 space = isl_space_unwrap(space);
617 dom = isl_space_domain(isl_space_copy(space));
618 dim = isl_space_dim(dom, isl_dim_set);
619 ran = isl_space_range(space);
620 ran = isl_space_add_dims(ran, isl_dim_set, 1);
621 space = isl_space_map_from_set(dom);
622 ma = isl_multi_aff_identity(space);
623 ma2 = isl_multi_aff_project_out_map(ran, isl_dim_set, n_arg, 1);
624 ma = isl_multi_aff_product(ma, ma2);
627 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
628 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
629 ma = isl_multi_aff_project_out_map(space, isl_dim_set, 0, dim + n_arg);
630 mpa2 = isl_multi_pw_aff_from_multi_aff(ma);
631 mpa = isl_multi_pw_aff_flat_range_product(mpa, mpa2);
633 return mpa;
636 /* Add the integer value from "arg" to "mpa".
638 static __isl_give isl_multi_pw_aff *add_int(__isl_take isl_multi_pw_aff *mpa,
639 __isl_take pet_expr *arg)
641 isl_space *space;
642 isl_val *v;
643 isl_aff *aff;
644 isl_multi_pw_aff *mpa_arg;
646 v = pet_expr_int_get_val(arg);
647 pet_expr_free(arg);
649 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
650 aff = isl_aff_val_on_domain(isl_local_space_from_space(space), v);
651 mpa_arg = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
653 mpa = isl_multi_pw_aff_flat_range_product(mpa, mpa_arg);
655 return mpa;
658 /* Add the affine expression from "arg" to "mpa".
659 * "n_arg" is the number of dimensions in the range of the wrapped
660 * relation in the domain of "mpa".
662 static __isl_give isl_multi_pw_aff *add_aff(__isl_take isl_multi_pw_aff *mpa,
663 int n_arg, __isl_take pet_expr *arg)
665 isl_multi_pw_aff *mpa_arg;
667 mpa_arg = pet_expr_access_get_index(arg);
668 pet_expr_free(arg);
670 if (n_arg > 0) {
671 isl_space *space;
672 isl_multi_aff *ma;
674 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
675 space = isl_space_unwrap(space);
676 ma = isl_multi_aff_domain_map(space);
677 mpa_arg = isl_multi_pw_aff_pullback_multi_aff(mpa_arg, ma);
680 mpa = isl_multi_pw_aff_flat_range_product(mpa, mpa_arg);
682 return mpa;
685 /* Combine the index expression of "expr" with the subaccess relation "access".
686 * If "add" is set, then it is not the index expression of "expr" itself
687 * that is passed to the function, but its address.
689 * We call patch_map on each map in "access" and return the combined results.
691 static __isl_give isl_union_map *patch(__isl_take isl_union_map *access,
692 __isl_keep pet_expr *expr, int add)
694 isl_multi_pw_aff *prefix;
696 prefix = pet_expr_access_get_index(expr);
697 return pet_patch_union_map(prefix, access, add, 1);
700 /* Set the access relations of "expr", which appears in the argument
701 * at position "pos" in a call expression by composing the access
702 * relations in "summary" with the expression "int_arg" of the integer
703 * arguments in terms of the domain and expression arguments of "expr" and
704 * combining the result with the index expression passed to the function.
705 * If "add" is set, then it is not "expr" itself that is passed
706 * to the function, but the address of "expr".
708 * We reset the read an write flag of "expr" and rely on
709 * pet_expr_access_set_access setting the flags based on
710 * the access relations.
712 * After relating each access relation of the called function
713 * to the domain and expression arguments at the call site,
714 * the result is combined with the index expression by the function patch
715 * and then stored in the access expression.
717 static __isl_give pet_expr *set_access_relations(__isl_take pet_expr *expr,
718 __isl_keep pet_function_summary *summary, int pos,
719 __isl_take isl_multi_pw_aff *int_arg, int add)
721 enum pet_expr_access_type type;
723 expr = pet_expr_access_set_read(expr, 0);
724 expr = pet_expr_access_set_write(expr, 0);
725 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
726 isl_union_map *access;
728 access = pet_function_summary_arg_get_access(summary,
729 pos, type);
730 access = isl_union_map_preimage_domain_multi_pw_aff(access,
731 isl_multi_pw_aff_copy(int_arg));
732 access = patch(access, expr, add);
733 expr = pet_expr_access_set_access(expr, type, access);
735 isl_multi_pw_aff_free(int_arg);
737 return expr;
740 /* Set the access relations of "arg", which appears in the argument
741 * at position "pos" in the call expression "call" based on the
742 * information in "summary".
743 * If "add" is set, then it is not "arg" itself that is passed
744 * to the function, but the address of "arg".
746 * We create an affine function "int_arg" that expresses
747 * the integer function call arguments in terms of the domain of "arg"
748 * (i.e., the outer loop iterators) and the expression arguments.
749 * If the actual argument is not an affine expression or if it itself
750 * has expression arguments, then it is added as an argument to "arg" and
751 * "int_arg" is made to reference this additional expression argument.
753 * Finally, we call set_access_relations to plug in the actual arguments
754 * (expressed in "int_arg") into the access relations in "summary" and
755 * to add the resulting access relations to "arg".
757 static __isl_give pet_expr *access_plug_in_summary(__isl_take pet_expr *arg,
758 __isl_keep pet_expr *call, __isl_keep pet_function_summary *summary,
759 int pos, int add)
761 int j, n;
762 isl_space *space;
763 isl_multi_pw_aff *int_arg;
764 int arg_n_arg;
766 space = pet_expr_access_get_augmented_domain_space(arg);
767 space = isl_space_from_domain(space);
768 arg_n_arg = pet_expr_get_n_arg(arg);
769 int_arg = isl_multi_pw_aff_zero(space);
770 n = pet_function_summary_get_n_arg(summary);
771 for (j = 0; j < n; ++j) {
772 pet_expr *arg_j;
773 int arg_j_n_arg;
775 if (!pet_function_summary_arg_is_int(summary, j))
776 continue;
778 arg_j = pet_expr_get_arg(call, j);
779 arg_j_n_arg = pet_expr_get_n_arg(arg_j);
780 if (pet_expr_get_type(arg_j) == pet_expr_int) {
781 int_arg = add_int(int_arg, arg_j);
782 } else if (arg_j_n_arg != 0 || !pet_expr_is_affine(arg_j)) {
783 arg = pet_expr_insert_arg(arg, arg_n_arg,
784 arg_j);
785 int_arg = add_arg(int_arg, arg_n_arg);
786 arg_n_arg++;
787 } else {
788 int_arg = add_aff(int_arg, arg_n_arg, arg_j);
791 arg = set_access_relations(arg, summary, pos, int_arg, add);
793 return arg;
796 /* Given the argument "arg" at position "pos" of "call",
797 * check if it is either an access expression or the address
798 * of an access expression. If so, use the information in "summary"
799 * to set the access relations of the access expression.
801 static __isl_give pet_expr *arg_plug_in_summary(__isl_take pet_expr *arg,
802 __isl_keep pet_expr *call, __isl_keep pet_function_summary *summary,
803 int pos)
805 enum pet_expr_type type;
806 pet_expr *arg2;
808 type = pet_expr_get_type(arg);
809 if (type == pet_expr_access)
810 return access_plug_in_summary(arg, call, summary, pos, 0);
811 if (!pet_expr_is_address_of(arg))
812 return arg;
814 arg2 = pet_expr_get_arg(arg, 0);
815 if (pet_expr_get_type(arg2) == pet_expr_access)
816 arg2 = access_plug_in_summary(arg2, call, summary, pos, 1);
817 arg = pet_expr_set_arg(arg, 0, arg2);
819 return arg;
822 /* Given a call expression, check if the integer arguments can
823 * be represented by affine expressions in the context "pc"
824 * (assuming they are not already affine expressions).
825 * If so, replace these arguments by the corresponding affine expressions.
827 static __isl_give pet_expr *call_plug_in_affine_args(__isl_take pet_expr *call,
828 __isl_keep pet_context *pc)
830 int i, n;
832 n = pet_expr_get_n_arg(call);
833 for (i = 0; i < n; ++i) {
834 pet_expr *arg;
835 isl_pw_aff *pa;
837 arg = pet_expr_get_arg(call, i);
838 if (!arg)
839 return pet_expr_free(call);
840 if (pet_expr_get_type_size(arg) == 0 ||
841 pet_expr_is_affine(arg)) {
842 pet_expr_free(arg);
843 continue;
846 pa = pet_expr_extract_affine(arg, pc);
847 pet_expr_free(arg);
848 if (!pa)
849 return pet_expr_free(call);
850 if (isl_pw_aff_involves_nan(pa)) {
851 isl_pw_aff_free(pa);
852 continue;
855 arg = pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa));
856 call = pet_expr_set_arg(call, i, arg);
859 return call;
862 /* If "call" has an associated function summary, then use it
863 * to set the access relations of the array arguments of the function call.
865 * We first plug in affine expressions for the integer arguments
866 * whenever possible as these arguments will be plugged in
867 * in the access relations of the array arguments.
869 static __isl_give pet_expr *call_plug_in_summary(__isl_take pet_expr *call,
870 void *user)
872 pet_context *pc = user;
873 pet_function_summary *summary;
874 int i, n;
876 if (!pet_expr_call_has_summary(call))
877 return call;
879 call = call_plug_in_affine_args(call, pc);
881 summary = pet_expr_call_get_summary(call);
882 if (!summary)
883 return pet_expr_free(call);
885 n = pet_expr_get_n_arg(call);
886 for (i = 0; i < n; ++i) {
887 pet_expr *arg_i;
889 if (!pet_function_summary_arg_is_array(summary, i))
890 continue;
892 arg_i = pet_expr_get_arg(call, i);
893 arg_i = arg_plug_in_summary(arg_i, call, summary, i);
894 call = pet_expr_set_arg(call, i, arg_i);
897 pet_function_summary_free(summary);
898 return call;
901 /* For each call subexpression of "expr", plug in the access relations
902 * from the associated function summary (if any).
904 static __isl_give pet_expr *plug_in_summaries(__isl_take pet_expr *expr,
905 __isl_keep pet_context *pc)
907 return pet_expr_map_call(expr, &call_plug_in_summary, pc);
910 /* Given an access expression "expr", check that it is an affine
911 * access expression and set *only_affine to 1.
912 * If "expr" is not an affine access expression, then set *only_affine to 0
913 * and abort.
915 static int check_only_affine(__isl_keep pet_expr *expr, void *user)
917 int *only_affine = user;
918 int is_affine;
920 is_affine = pet_expr_is_affine(expr);
921 if (is_affine < 0)
922 return -1;
923 if (!is_affine) {
924 *only_affine = 0;
925 return -1;
927 *only_affine = 1;
929 return 0;
932 /* Does "expr" have any affine access subexpression and no other
933 * access subexpressions?
935 * only_affine is initialized to -1 and set to 1 as soon as one affine
936 * access subexpression has been found and to 0 if some other access
937 * subexpression has been found. In this latter case, the search is
938 * aborted.
940 static isl_bool has_only_affine_access_sub_expr(__isl_keep pet_expr *expr)
942 int only_affine = -1;
944 if (pet_expr_foreach_access_expr(expr, &check_only_affine,
945 &only_affine) < 0 &&
946 only_affine != 0)
947 return isl_bool_error;
949 return only_affine > 0;
952 /* Try and replace "expr" by an affine access expression by essentially
953 * evaluating operations and/or special calls on affine access expressions.
954 * It therefore only makes sense to do this if "expr" is a call or an operation
955 * and if it has at least one affine access subexpression and no other
956 * access subexpressions.
958 static __isl_give pet_expr *expr_plug_in_affine(__isl_take pet_expr *expr,
959 void *user)
961 enum pet_expr_type type;
962 pet_context *pc = user;
963 isl_pw_aff *pa;
964 isl_bool contains_access;
966 type = pet_expr_get_type(expr);
967 if (type != pet_expr_call && type != pet_expr_op)
968 return expr;
969 contains_access = has_only_affine_access_sub_expr(expr);
970 if (contains_access < 0)
971 return pet_expr_free(expr);
972 if (!contains_access)
973 return expr;
975 pa = pet_expr_extract_affine(expr, pc);
976 if (!pa)
977 return pet_expr_free(expr);
978 if (isl_pw_aff_involves_nan(pa)) {
979 isl_pw_aff_free(pa);
980 return expr;
983 pet_expr_free(expr);
984 expr = pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa));
986 return expr;
989 /* Detect affine subexpressions in "expr".
991 * The detection is performed top-down in order to be able
992 * to exploit the min/max optimization in comparisons.
993 * That is, if some subexpression is of the form max(a,b) <= min(c,d)
994 * and if the affine expressions were being detected bottom-up, then
995 * affine expressions for max(a,b) and min(c,d) would be constructed
996 * first and it would no longer be possible to optimize the extraction
997 * of the comparison as a <= c && a <= d && b <= c && b <= d.
999 static __isl_give pet_expr *plug_in_affine(__isl_take pet_expr *expr,
1000 __isl_keep pet_context *pc)
1002 return pet_expr_map_top_down(expr, &expr_plug_in_affine, pc);
1005 /* Given an affine condition "cond" and two access expressions "lhs" and
1006 * "rhs" to the same array, construct an access expression to the array that
1007 * performs the "lhs" access if "cond" is satisfied and the "rhs" access
1008 * otherwise.
1010 * That is, replace
1012 * c ? A[f] : A[g]
1014 * by
1016 * A[c ? f : g].
1018 static __isl_give pet_expr *merged_access(__isl_take pet_expr *cond,
1019 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
1021 isl_multi_pw_aff *index1, *index2;
1022 isl_pw_aff *c;
1023 int i, n;
1025 c = pet_expr_get_affine(cond);
1026 index1 = pet_expr_access_get_index(lhs);
1027 index2 = pet_expr_access_get_index(rhs);
1028 n = isl_multi_pw_aff_dim(index1, isl_dim_out);
1029 for (i = 0; i < n; ++i) {
1030 isl_pw_aff *pa1, *pa2;
1032 pa1 = isl_multi_pw_aff_get_pw_aff(index1, i);
1033 pa2 = isl_multi_pw_aff_get_pw_aff(index2, i);
1034 pa1 = isl_pw_aff_cond(isl_pw_aff_copy(c), pa1, pa2);
1035 index1 = isl_multi_pw_aff_set_pw_aff(index1, i, pa1);
1037 isl_pw_aff_free(c);
1038 isl_multi_pw_aff_free(index2);
1040 lhs = pet_expr_access_set_index(lhs, index1);
1042 pet_expr_free(cond);
1043 pet_expr_free(rhs);
1045 return lhs;
1048 /* If "expr" is a conditional access to an array expressed as a conditional
1049 * operator with two accesses to the same array and an affine condition,
1050 * then replace the conditional operator by a single access to the array.
1052 * If either of the two accesses has any arguments or access relations,
1053 * then the original expression is kept since replacing it may lose
1054 * information.
1056 static __isl_give pet_expr *merge_conditional_access(__isl_take pet_expr *expr,
1057 void *user)
1059 pet_expr *cond, *lhs, *rhs;
1060 isl_bool ok;
1062 if (pet_expr_op_get_type(expr) != pet_op_cond)
1063 return expr;
1065 cond = pet_expr_get_arg(expr, 0);
1066 lhs = pet_expr_get_arg(expr, 1);
1067 rhs = pet_expr_get_arg(expr, 2);
1068 ok = pet_expr_get_n_arg(lhs) == 0 && pet_expr_get_n_arg(rhs) == 0;
1069 if (ok > 0)
1070 ok = pet_expr_is_affine(cond);
1071 if (ok > 0)
1072 ok = pet_expr_is_same_access(lhs, rhs);
1073 if (ok > 0)
1074 ok = isl_bool_not(pet_expr_access_has_any_access_relation(lhs));
1075 if (ok > 0)
1076 ok = isl_bool_not(pet_expr_access_has_any_access_relation(rhs));
1077 if (ok > 0) {
1078 pet_expr_free(expr);
1079 return merged_access(cond, lhs, rhs);
1081 pet_expr_free(cond);
1082 pet_expr_free(lhs);
1083 pet_expr_free(rhs);
1084 if (ok < 0)
1085 return pet_expr_free(expr);
1086 return expr;
1089 /* Look for any conditional access to an array expressed as a conditional
1090 * operator with two accesses to the same array and replace it
1091 * by a single access to the array.
1093 static __isl_give pet_expr *merge_conditional_accesses(
1094 __isl_take pet_expr *expr)
1096 return pet_expr_map_op(expr, &merge_conditional_access, NULL);
1099 /* Evaluate "expr" in the context of "pc".
1101 * In particular, we first make sure that all the access expressions
1102 * inside "expr" have the same domain as "pc".
1103 * Then, we plug in affine expressions for scalar reads,
1104 * plug in the arguments of all access expressions in "expr" as well
1105 * as any other affine expressions that may appear inside "expr",
1106 * merge conditional accesses to the same array and
1107 * plug in the access relations from the summary functions associated
1108 * to call expressions.
1110 * The merging of conditional accesses needs to be performed after
1111 * the detection of affine expressions such that it can simply
1112 * check if the condition is an affine expression.
1113 * It needs to be performed before access relations are plugged in
1114 * such that these access relations only need to be plugged into
1115 * the fused access.
1117 __isl_give pet_expr *pet_context_evaluate_expr(__isl_keep pet_context *pc,
1118 __isl_take pet_expr *expr)
1120 expr = pet_expr_insert_domain(expr, pet_context_get_space(pc));
1121 expr = plug_in_affine_read(expr, pc);
1122 expr = pet_expr_plug_in_args(expr, pc);
1123 expr = plug_in_affine(expr, pc);
1124 expr = merge_conditional_accesses(expr);
1125 expr = plug_in_summaries(expr, pc);
1126 return expr;
1129 /* Wrapper around pet_context_evaluate_expr
1130 * for use as a callback to pet_tree_map_expr.
1132 static __isl_give pet_expr *evaluate_expr(__isl_take pet_expr *expr,
1133 void *user)
1135 pet_context *pc = user;
1137 return pet_context_evaluate_expr(pc, expr);
1140 /* Evaluate "tree" in the context of "pc".
1141 * That is, evaluate all the expressions of "tree" in the context of "pc".
1143 __isl_give pet_tree *pet_context_evaluate_tree(__isl_keep pet_context *pc,
1144 __isl_take pet_tree *tree)
1146 return pet_tree_map_expr(tree, &evaluate_expr, pc);
1149 /* Add an unbounded inner dimension "id" to pc->domain.
1151 * The assignments are not adjusted here and therefore keep
1152 * their original domain. These domains need to be adjusted before
1153 * these assigned values can be used. This is taken care of by
1154 * pet_context_get_value.
1156 static __isl_give pet_context *extend_domain(__isl_take pet_context *pc,
1157 __isl_take isl_id *id)
1159 int pos;
1161 pc = pet_context_cow(pc);
1162 if (!pc || !id)
1163 goto error;
1165 pos = pet_context_dim(pc);
1166 pc->domain = isl_set_add_dims(pc->domain, isl_dim_set, 1);
1167 pc->domain = isl_set_set_dim_id(pc->domain, isl_dim_set, pos, id);
1168 if (!pc->domain)
1169 return pet_context_free(pc);
1171 return pc;
1172 error:
1173 pet_context_free(pc);
1174 isl_id_free(id);
1175 return NULL;
1178 /* Add an unbounded inner iterator "id" to pc->domain.
1179 * Additionally, mark the variable "id" as having the value of this
1180 * new inner iterator.
1182 __isl_give pet_context *pet_context_add_inner_iterator(
1183 __isl_take pet_context *pc, __isl_take isl_id *id)
1185 int pos;
1186 isl_space *space;
1187 isl_local_space *ls;
1188 isl_aff *aff;
1189 isl_pw_aff *pa;
1191 if (!pc || !id)
1192 goto error;
1194 pos = pet_context_dim(pc);
1195 pc = extend_domain(pc, isl_id_copy(id));
1196 if (!pc)
1197 goto error;
1199 space = pet_context_get_space(pc);
1200 ls = isl_local_space_from_space(space);
1201 aff = isl_aff_var_on_domain(ls, isl_dim_set, pos);
1202 pa = isl_pw_aff_from_aff(aff);
1204 pc = pet_context_set_value(pc, id, pa);
1206 return pc;
1207 error:
1208 pet_context_free(pc);
1209 isl_id_free(id);
1210 return NULL;
1213 /* Add an inner iterator to pc->domain.
1214 * In particular, extend the domain with an inner loop { [t] : t >= 0 }.
1216 __isl_give pet_context *pet_context_add_infinite_loop(
1217 __isl_take pet_context *pc)
1219 int dim;
1220 isl_ctx *ctx;
1221 isl_id *id;
1223 if (!pc)
1224 return NULL;
1226 dim = pet_context_dim(pc);
1227 ctx = pet_context_get_ctx(pc);
1228 id = isl_id_alloc(ctx, "t", NULL);
1229 pc = extend_domain(pc, id);
1230 pc = pet_context_cow(pc);
1231 if (!pc)
1232 return NULL;
1233 pc->domain = isl_set_lower_bound_si(pc->domain, isl_dim_set, dim, 0);
1234 if (!pc->domain)
1235 return pet_context_free(pc);
1237 return pc;
1240 /* Internal data structure for preimage_domain.
1242 * "ma" is the function under which the preimage should be computed.
1243 * "assignments" collects the results.
1245 struct pet_preimage_domain_data {
1246 isl_multi_aff *ma;
1247 isl_id_to_pw_aff *assignments;
1250 /* Add the assignment to "key" of the preimage of "val" under data->ma
1251 * to data->assignments.
1253 * Some dimensions may have been added to the domain of the enclosing
1254 * pet_context after the value "val" was added. We therefore need to
1255 * adjust the domain of "val" to match the range of data->ma (which
1256 * in turn matches the domain of the pet_context), by adding the missing
1257 * dimensions.
1259 static isl_stat preimage_domain_pair(__isl_take isl_id *key,
1260 __isl_take isl_pw_aff *val, void *user)
1262 struct pet_preimage_domain_data *data = user;
1263 int dim;
1264 isl_multi_aff *ma;
1266 ma = isl_multi_aff_copy(data->ma);
1268 dim = isl_pw_aff_dim(val, isl_dim_in);
1269 if (dim != isl_multi_aff_dim(data->ma, isl_dim_out)) {
1270 isl_space *space;
1271 isl_multi_aff *proj;
1272 space = isl_multi_aff_get_space(data->ma);
1273 space = isl_space_range(space);
1274 proj = pet_prefix_projection(space, dim);
1275 ma = isl_multi_aff_pullback_multi_aff(proj, ma);
1278 val = isl_pw_aff_pullback_multi_aff(val, ma);
1279 data->assignments = isl_id_to_pw_aff_set(data->assignments, key, val);
1281 return isl_stat_ok;
1284 /* Compute the preimage of "assignments" under the function represented by "ma".
1285 * In other words, plug in "ma" in the domains of the assigned values.
1287 static __isl_give isl_id_to_pw_aff *preimage_domain(
1288 __isl_take isl_id_to_pw_aff *assignments, __isl_keep isl_multi_aff *ma)
1290 struct pet_preimage_domain_data data = { ma };
1291 isl_ctx *ctx;
1293 ctx = isl_id_to_pw_aff_get_ctx(assignments);
1294 data.assignments = isl_id_to_pw_aff_alloc(ctx, 0);
1295 if (isl_id_to_pw_aff_foreach(assignments, &preimage_domain_pair,
1296 &data) < 0)
1297 data.assignments = isl_id_to_pw_aff_free(data.assignments);
1298 isl_id_to_pw_aff_free(assignments);
1300 return data.assignments;
1303 /* Compute the preimage of "pc" under the function represented by "ma".
1304 * In other words, plug in "ma" in the domain of "pc".
1306 __isl_give pet_context *pet_context_preimage_domain(__isl_take pet_context *pc,
1307 __isl_keep isl_multi_aff *ma)
1309 pc = pet_context_cow(pc);
1310 if (!pc)
1311 return NULL;
1312 pc->domain = isl_set_preimage_multi_aff(pc->domain,
1313 isl_multi_aff_copy(ma));
1314 pc->assignments = preimage_domain(pc->assignments, ma);
1315 if (!pc->domain || !pc->assignments)
1316 return pet_context_free(pc);
1317 return pc;
1320 /* Add the constraints of "set" to the domain of "pc".
1322 __isl_give pet_context *pet_context_intersect_domain(__isl_take pet_context *pc,
1323 __isl_take isl_set *set)
1325 pc = pet_context_cow(pc);
1326 if (!pc)
1327 goto error;
1328 pc->domain = isl_set_intersect(pc->domain, set);
1329 if (!pc->domain)
1330 return pet_context_free(pc);
1331 return pc;
1332 error:
1333 pet_context_free(pc);
1334 isl_set_free(set);
1335 return NULL;
1338 void pet_context_dump(__isl_keep pet_context *pc)
1340 if (!pc)
1341 return;
1342 fprintf(stderr, "domain: ");
1343 isl_set_dump(pc->domain);
1344 fprintf(stderr, "assignments: ");
1345 isl_id_to_pw_aff_dump(pc->assignments);
1346 fprintf(stderr, "nesting allowed: %d\n", pc->allow_nested);