1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
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.
16 *
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.
28 *
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.
33 */
34
35 #include <string.h>
36
37 #include <isl/ctx.h>
38 #include <isl/hash.h>
39 #include <isl/id.h>
40 #include <isl/val.h>
41 #include <isl/space.h>
42 #include <isl/local_space.h>
43 #include <isl/aff.h>
44 #include <isl/map.h>
45 #include <isl/union_set.h>
46 #include <isl/union_map.h>
47 #include <isl/printer.h>
48
49 #include "aff.h"
50 #include "array.h"
51 #include "expr.h"
52 #include "expr_arg.h"
53 #include "filter.h"
54 #include "nest.h"
55 #include "options.h"
56 #include "value_bounds.h"
57 #include "patch.h"
58
59 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
60
61 static char *type_str[] = {
62 [pet_expr_access] = "access",
63 [pet_expr_call] = "call",
64 [pet_expr_cast] = "cast",
65 [pet_expr_double] = "double",
66 [pet_expr_int] = "int",
67 [pet_expr_op] = "op",
68 };
69
70 static char *op_str[] = {
71 [pet_op_add_assign] = "+=",
72 [pet_op_sub_assign] = "-=",
73 [pet_op_mul_assign] = "*=",
74 [pet_op_div_assign] = "/=",
75 [pet_op_and_assign] = "&=",
76 [pet_op_xor_assign] = "^=",
77 [pet_op_or_assign] = "|=",
78 [pet_op_assign] = "=",
79 [pet_op_add] = "+",
80 [pet_op_sub] = "-",
81 [pet_op_mul] = "*",
82 [pet_op_div] = "/",
83 [pet_op_mod] = "%",
84 [pet_op_shl] = "<<",
85 [pet_op_shr] = ">>",
86 [pet_op_eq] = "==",
87 [pet_op_ne] = "!=",
88 [pet_op_le] = "<=",
89 [pet_op_ge] = ">=",
90 [pet_op_lt] = "<",
91 [pet_op_gt] = ">",
92 [pet_op_minus] = "-",
93 [pet_op_post_inc] = "++",
94 [pet_op_post_dec] = "--",
95 [pet_op_pre_inc] = "++",
96 [pet_op_pre_dec] = "--",
97 [pet_op_address_of] = "&",
98 [pet_op_and] = "&",
99 [pet_op_xor] = "^",
100 [pet_op_or] = "|",
101 [pet_op_not] = "~",
102 [pet_op_land] = "&&",
103 [pet_op_lor] = "||",
104 [pet_op_lnot] = "!",
105 [pet_op_cond] = "?:",
106 [pet_op_assume] = "assume",
107 [pet_op_kill] = "kill"
108 };
109
pet_op_str(enum pet_op_type op)110 const char *pet_op_str(enum pet_op_type op)
111 {
112 return op_str[op];
113 }
114
pet_op_is_inc_dec(enum pet_op_type op)115 int pet_op_is_inc_dec(enum pet_op_type op)
116 {
117 return op == pet_op_post_inc || op == pet_op_post_dec ||
118 op == pet_op_pre_inc || op == pet_op_pre_dec;
119 }
120
pet_type_str(enum pet_expr_type type)121 const char *pet_type_str(enum pet_expr_type type)
122 {
123 return type_str[type];
124 }
125
pet_str_op(const char * str)126 enum pet_op_type pet_str_op(const char *str)
127 {
128 int i;
129
130 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
131 if (!strcmp(op_str[i], str))
132 return i;
133
134 return -1;
135 }
136
pet_str_type(const char * str)137 enum pet_expr_type pet_str_type(const char *str)
138 {
139 int i;
140
141 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
142 if (!strcmp(type_str[i], str))
143 return i;
144
145 return -1;
146 }
147
148 /* Construct a pet_expr of the given type.
149 */
pet_expr_alloc(isl_ctx * ctx,enum pet_expr_type type)150 __isl_give pet_expr *pet_expr_alloc(isl_ctx *ctx, enum pet_expr_type type)
151 {
152 pet_expr *expr;
153
154 expr = isl_calloc_type(ctx, struct pet_expr);
155 if (!expr)
156 return NULL;
157
158 expr->ctx = ctx;
159 isl_ctx_ref(ctx);
160 expr->type = type;
161 expr->ref = 1;
162
163 return expr;
164 }
165
166 /* Construct an access pet_expr from an index expression.
167 * By default, the access is considered to be a read access.
168 * The initial depth is set from the index expression and
169 * may still be updated by the caller before the access relation
170 * is created.
171 */
pet_expr_from_index(__isl_take isl_multi_pw_aff * index)172 __isl_give pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
173 {
174 isl_ctx *ctx;
175 pet_expr *expr;
176
177 if (!index)
178 return NULL;
179 ctx = isl_multi_pw_aff_get_ctx(index);
180 expr = pet_expr_alloc(ctx, pet_expr_access);
181 if (!expr)
182 goto error;
183
184 expr->acc.read = 1;
185 expr->acc.write = 0;
186
187 expr = pet_expr_access_set_index(expr, index);
188
189 return expr;
190 error:
191 isl_multi_pw_aff_free(index);
192 return NULL;
193 }
194
195 /* Extend the range of "access" with "n" dimensions, retaining
196 * the tuple identifier on this range.
197 *
198 * If "access" represents a member access, then extend the range
199 * of the member.
200 */
extend_range(__isl_take isl_map * access,int n)201 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
202 {
203 isl_id *id;
204
205 id = isl_map_get_tuple_id(access, isl_dim_out);
206
207 if (!isl_map_range_is_wrapping(access)) {
208 access = isl_map_add_dims(access, isl_dim_out, n);
209 } else {
210 isl_map *domain;
211
212 domain = isl_map_copy(access);
213 domain = isl_map_range_factor_domain(domain);
214 access = isl_map_range_factor_range(access);
215 access = extend_range(access, n);
216 access = isl_map_range_product(domain, access);
217 }
218
219 access = isl_map_set_tuple_id(access, isl_dim_out, id);
220
221 return access;
222 }
223
224 /* Does the access expression "expr" have any explicit access relation?
225 */
pet_expr_access_has_any_access_relation(__isl_keep pet_expr * expr)226 isl_bool pet_expr_access_has_any_access_relation(__isl_keep pet_expr *expr)
227 {
228 enum pet_expr_access_type type;
229
230 if (!expr)
231 return isl_bool_error;
232
233 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type)
234 if (expr->acc.access[type])
235 return isl_bool_true;
236
237 return isl_bool_false;
238 }
239
240 /* Are all relevant access relations explicitly available in "expr"?
241 */
has_relevant_access_relations(__isl_keep pet_expr * expr)242 static int has_relevant_access_relations(__isl_keep pet_expr *expr)
243 {
244 if (!expr)
245 return -1;
246
247 if (expr->acc.kill && !expr->acc.access[pet_expr_access_fake_killed])
248 return 0;
249 if (expr->acc.read && !expr->acc.access[pet_expr_access_may_read])
250 return 0;
251 if (expr->acc.write &&
252 (!expr->acc.access[pet_expr_access_may_write] ||
253 !expr->acc.access[pet_expr_access_must_write]))
254 return 0;
255
256 return 1;
257 }
258
259 /* Replace the depth of the access expr "expr" by "depth".
260 *
261 * To avoid inconsistencies between the depth and the access relation,
262 * we currently do not allow the depth to change once the access relation
263 * has been set or computed.
264 */
pet_expr_access_set_depth(__isl_take pet_expr * expr,int depth)265 __isl_give pet_expr *pet_expr_access_set_depth(__isl_take pet_expr *expr,
266 int depth)
267 {
268 if (!expr)
269 return NULL;
270 if (expr->acc.depth == depth)
271 return expr;
272 if (pet_expr_access_has_any_access_relation(expr))
273 isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
274 "depth cannot be changed after access relation "
275 "has been set or computed", return pet_expr_free(expr));
276
277 expr = pet_expr_cow(expr);
278 if (!expr)
279 return NULL;
280 expr->acc.depth = depth;
281
282 return expr;
283 }
284
285 /* Construct a pet_expr that kills the elements specified by
286 * the index expression "index" and the access relation "access".
287 */
pet_expr_kill_from_access_and_index(__isl_take isl_map * access,__isl_take isl_multi_pw_aff * index)288 __isl_give pet_expr *pet_expr_kill_from_access_and_index(
289 __isl_take isl_map *access, __isl_take isl_multi_pw_aff *index)
290 {
291 int depth;
292 pet_expr *expr;
293
294 if (!access || !index)
295 goto error;
296
297 expr = pet_expr_from_index(index);
298 expr = pet_expr_access_set_read(expr, 0);
299 expr = pet_expr_access_set_kill(expr, 1);
300 depth = isl_map_dim(access, isl_dim_out);
301 expr = pet_expr_access_set_depth(expr, depth);
302 expr = pet_expr_access_set_access(expr, pet_expr_access_killed,
303 isl_union_map_from_map(access));
304 return pet_expr_new_unary(0, pet_op_kill, expr);
305 error:
306 isl_map_free(access);
307 isl_multi_pw_aff_free(index);
308 return NULL;
309 }
310
311 /* Construct a unary pet_expr that performs "op" on "arg",
312 * where the result is represented using a type of "type_size" bits
313 * (may be zero if unknown or if the type is not an integer).
314 */
pet_expr_new_unary(int type_size,enum pet_op_type op,__isl_take pet_expr * arg)315 __isl_give pet_expr *pet_expr_new_unary(int type_size, enum pet_op_type op,
316 __isl_take pet_expr *arg)
317 {
318 isl_ctx *ctx;
319 pet_expr *expr;
320
321 if (!arg)
322 return NULL;
323 ctx = pet_expr_get_ctx(arg);
324 expr = pet_expr_alloc(ctx, pet_expr_op);
325 expr = pet_expr_set_n_arg(expr, 1);
326 if (!expr)
327 goto error;
328
329 expr->op = op;
330 expr->type_size = type_size;
331 expr->args[pet_un_arg] = arg;
332
333 return expr;
334 error:
335 pet_expr_free(arg);
336 return NULL;
337 }
338
339 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
340 * where the result is represented using a type of "type_size" bits
341 * (may be zero if unknown or if the type is not an integer).
342 */
pet_expr_new_binary(int type_size,enum pet_op_type op,__isl_take pet_expr * lhs,__isl_take pet_expr * rhs)343 __isl_give pet_expr *pet_expr_new_binary(int type_size, enum pet_op_type op,
344 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
345 {
346 isl_ctx *ctx;
347 pet_expr *expr;
348
349 if (!lhs || !rhs)
350 goto error;
351 ctx = pet_expr_get_ctx(lhs);
352 expr = pet_expr_alloc(ctx, pet_expr_op);
353 expr = pet_expr_set_n_arg(expr, 2);
354 if (!expr)
355 goto error;
356
357 expr->op = op;
358 expr->type_size = type_size;
359 expr->args[pet_bin_lhs] = lhs;
360 expr->args[pet_bin_rhs] = rhs;
361
362 return expr;
363 error:
364 pet_expr_free(lhs);
365 pet_expr_free(rhs);
366 return NULL;
367 }
368
369 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
370 */
pet_expr_new_ternary(__isl_take pet_expr * cond,__isl_take pet_expr * lhs,__isl_take pet_expr * rhs)371 __isl_give pet_expr *pet_expr_new_ternary(__isl_take pet_expr *cond,
372 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
373 {
374 isl_ctx *ctx;
375 pet_expr *expr;
376
377 if (!cond || !lhs || !rhs)
378 goto error;
379 ctx = pet_expr_get_ctx(cond);
380 expr = pet_expr_alloc(ctx, pet_expr_op);
381 expr = pet_expr_set_n_arg(expr, 3);
382 if (!expr)
383 goto error;
384
385 expr->op = pet_op_cond;
386 expr->args[pet_ter_cond] = cond;
387 expr->args[pet_ter_true] = lhs;
388 expr->args[pet_ter_false] = rhs;
389
390 return expr;
391 error:
392 pet_expr_free(cond);
393 pet_expr_free(lhs);
394 pet_expr_free(rhs);
395 return NULL;
396 }
397
398 /* Construct a call pet_expr that calls function "name" with "n_arg"
399 * arguments. The caller is responsible for filling in the arguments.
400 */
pet_expr_new_call(isl_ctx * ctx,const char * name,unsigned n_arg)401 __isl_give pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
402 unsigned n_arg)
403 {
404 pet_expr *expr;
405
406 expr = pet_expr_alloc(ctx, pet_expr_call);
407 expr = pet_expr_set_n_arg(expr, n_arg);
408 if (!expr)
409 return NULL;
410
411 expr->c.name = strdup(name);
412 if (!expr->c.name)
413 return pet_expr_free(expr);
414
415 return expr;
416 }
417
418 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
419 */
pet_expr_new_cast(const char * type_name,__isl_take pet_expr * arg)420 __isl_give pet_expr *pet_expr_new_cast(const char *type_name,
421 __isl_take pet_expr *arg)
422 {
423 isl_ctx *ctx;
424 pet_expr *expr;
425
426 if (!arg)
427 return NULL;
428
429 ctx = pet_expr_get_ctx(arg);
430 expr = pet_expr_alloc(ctx, pet_expr_cast);
431 expr = pet_expr_set_n_arg(expr, 1);
432 if (!expr)
433 goto error;
434
435 expr->type_name = strdup(type_name);
436 if (!expr->type_name)
437 goto error;
438
439 expr->args[0] = arg;
440
441 return expr;
442 error:
443 pet_expr_free(arg);
444 pet_expr_free(expr);
445 return NULL;
446 }
447
448 /* Construct a pet_expr that represents the double "d".
449 */
pet_expr_new_double(isl_ctx * ctx,double val,const char * s)450 __isl_give pet_expr *pet_expr_new_double(isl_ctx *ctx,
451 double val, const char *s)
452 {
453 pet_expr *expr;
454
455 expr = pet_expr_alloc(ctx, pet_expr_double);
456 if (!expr)
457 return NULL;
458
459 expr->d.val = val;
460 expr->d.s = strdup(s);
461 if (!expr->d.s)
462 return pet_expr_free(expr);
463
464 return expr;
465 }
466
467 /* Construct a pet_expr that represents the integer value "v".
468 */
pet_expr_new_int(__isl_take isl_val * v)469 __isl_give pet_expr *pet_expr_new_int(__isl_take isl_val *v)
470 {
471 isl_ctx *ctx;
472 pet_expr *expr;
473
474 if (!v)
475 return NULL;
476
477 ctx = isl_val_get_ctx(v);
478 expr = pet_expr_alloc(ctx, pet_expr_int);
479 if (!expr)
480 goto error;
481
482 expr->i = v;
483
484 return expr;
485 error:
486 isl_val_free(v);
487 return NULL;
488 }
489
490 /* Return an independent duplicate of "expr".
491 *
492 * In case of an access expression, make sure the depth of the duplicate is set
493 * before the access relation (if any) is set and after the index expression
494 * is set.
495 */
pet_expr_dup(__isl_keep pet_expr * expr)496 static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr)
497 {
498 int i;
499 pet_expr *dup;
500 enum pet_expr_access_type type;
501
502 if (!expr)
503 return NULL;
504
505 dup = pet_expr_alloc(expr->ctx, expr->type);
506 dup = pet_expr_set_type_size(dup, expr->type_size);
507 dup = pet_expr_set_n_arg(dup, expr->n_arg);
508 for (i = 0; i < expr->n_arg; ++i)
509 dup = pet_expr_set_arg(dup, i, pet_expr_copy(expr->args[i]));
510
511 switch (expr->type) {
512 case pet_expr_access:
513 if (expr->acc.ref_id)
514 dup = pet_expr_access_set_ref_id(dup,
515 isl_id_copy(expr->acc.ref_id));
516 dup = pet_expr_access_set_index(dup,
517 isl_multi_pw_aff_copy(expr->acc.index));
518 dup = pet_expr_access_set_depth(dup, expr->acc.depth);
519 for (type = pet_expr_access_begin;
520 type < pet_expr_access_end; ++type) {
521 if (!expr->acc.access[type])
522 continue;
523 dup = pet_expr_access_set_access(dup, type,
524 isl_union_map_copy(expr->acc.access[type]));
525 }
526 dup = pet_expr_access_set_read(dup, expr->acc.read);
527 dup = pet_expr_access_set_write(dup, expr->acc.write);
528 dup = pet_expr_access_set_kill(dup, expr->acc.kill);
529 break;
530 case pet_expr_call:
531 dup = pet_expr_call_set_name(dup, expr->c.name);
532 if (expr->c.summary)
533 dup = pet_expr_call_set_summary(dup,
534 pet_function_summary_copy(expr->c.summary));
535 break;
536 case pet_expr_cast:
537 dup = pet_expr_cast_set_type_name(dup, expr->type_name);
538 break;
539 case pet_expr_double:
540 dup = pet_expr_double_set(dup, expr->d.val, expr->d.s);
541 break;
542 case pet_expr_int:
543 dup = pet_expr_int_set_val(dup, isl_val_copy(expr->i));
544 break;
545 case pet_expr_op:
546 dup = pet_expr_op_set_type(dup, expr->op);
547 break;
548 case pet_expr_error:
549 dup = pet_expr_free(dup);
550 break;
551 }
552
553 return dup;
554 }
555
556 /* Return a pet_expr that is equal to "expr" and that has only
557 * a single reference.
558 *
559 * If "expr" itself only has one reference, then clear its hash value
560 * since the returned pet_expr will be modified.
561 */
pet_expr_cow(__isl_take pet_expr * expr)562 __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr)
563 {
564 if (!expr)
565 return NULL;
566
567 if (expr->ref == 1) {
568 expr->hash = 0;
569 return expr;
570 }
571 expr->ref--;
572 return pet_expr_dup(expr);
573 }
574
pet_expr_free(__isl_take pet_expr * expr)575 __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr)
576 {
577 enum pet_expr_access_type type;
578 int i;
579
580 if (!expr)
581 return NULL;
582 if (--expr->ref > 0)
583 return NULL;
584
585 for (i = 0; i < expr->n_arg; ++i)
586 pet_expr_free(expr->args[i]);
587 free(expr->args);
588
589 switch (expr->type) {
590 case pet_expr_access:
591 isl_id_free(expr->acc.ref_id);
592 for (type = pet_expr_access_begin;
593 type < pet_expr_access_end; ++type)
594 isl_union_map_free(expr->acc.access[type]);
595 isl_multi_pw_aff_free(expr->acc.index);
596 break;
597 case pet_expr_call:
598 free(expr->c.name);
599 pet_function_summary_free(expr->c.summary);
600 break;
601 case pet_expr_cast:
602 free(expr->type_name);
603 break;
604 case pet_expr_double:
605 free(expr->d.s);
606 break;
607 case pet_expr_int:
608 isl_val_free(expr->i);
609 break;
610 case pet_expr_op:
611 case pet_expr_error:
612 break;
613 }
614
615 isl_ctx_deref(expr->ctx);
616 free(expr);
617 return NULL;
618 }
619
620 /* Return an additional reference to "expr".
621 */
pet_expr_copy(__isl_keep pet_expr * expr)622 __isl_give pet_expr *pet_expr_copy(__isl_keep pet_expr *expr)
623 {
624 if (!expr)
625 return NULL;
626
627 expr->ref++;
628 return expr;
629 }
630
631 /* Return the isl_ctx in which "expr" was created.
632 */
pet_expr_get_ctx(__isl_keep pet_expr * expr)633 isl_ctx *pet_expr_get_ctx(__isl_keep pet_expr *expr)
634 {
635 return expr ? expr->ctx : NULL;
636 }
637
638 /* Return the type of "expr".
639 */
pet_expr_get_type(__isl_keep pet_expr * expr)640 enum pet_expr_type pet_expr_get_type(__isl_keep pet_expr *expr)
641 {
642 if (!expr)
643 return pet_expr_error;
644 return expr->type;
645 }
646
647 /* Return the number of arguments of "expr".
648 */
pet_expr_get_n_arg(__isl_keep pet_expr * expr)649 int pet_expr_get_n_arg(__isl_keep pet_expr *expr)
650 {
651 if (!expr)
652 return -1;
653
654 return expr->n_arg;
655 }
656
657 /* Set the number of arguments of "expr" to "n".
658 *
659 * If "expr" originally had more arguments, then remove the extra arguments.
660 * If "expr" originally had fewer arguments, then create space for
661 * the extra arguments ans initialize them to NULL.
662 */
pet_expr_set_n_arg(__isl_take pet_expr * expr,int n)663 __isl_give pet_expr *pet_expr_set_n_arg(__isl_take pet_expr *expr, int n)
664 {
665 int i;
666 pet_expr **args;
667
668 if (!expr)
669 return NULL;
670 if (expr->n_arg == n)
671 return expr;
672 expr = pet_expr_cow(expr);
673 if (!expr)
674 return NULL;
675
676 if (n < expr->n_arg) {
677 for (i = n; i < expr->n_arg; ++i)
678 pet_expr_free(expr->args[i]);
679 expr->n_arg = n;
680 return expr;
681 }
682
683 args = isl_realloc_array(expr->ctx, expr->args, pet_expr *, n);
684 if (!args)
685 return pet_expr_free(expr);
686 expr->args = args;
687 for (i = expr->n_arg; i < n; ++i)
688 expr->args[i] = NULL;
689 expr->n_arg = n;
690
691 return expr;
692 }
693
694 /* Return the argument of "expr" at position "pos".
695 */
pet_expr_get_arg(__isl_keep pet_expr * expr,int pos)696 __isl_give pet_expr *pet_expr_get_arg(__isl_keep pet_expr *expr, int pos)
697 {
698 if (!expr)
699 return NULL;
700 if (pos < 0 || pos >= expr->n_arg)
701 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
702 "position out of bounds", return NULL);
703
704 return pet_expr_copy(expr->args[pos]);
705 }
706
707 /* Replace "expr" by its argument at position "pos".
708 */
pet_expr_arg(__isl_take pet_expr * expr,int pos)709 __isl_give pet_expr *pet_expr_arg(__isl_take pet_expr *expr, int pos)
710 {
711 pet_expr *arg;
712
713 arg = pet_expr_get_arg(expr, pos);
714 pet_expr_free(expr);
715
716 return arg;
717 }
718
719 /* Replace the argument of "expr" at position "pos" by "arg".
720 */
pet_expr_set_arg(__isl_take pet_expr * expr,int pos,__isl_take pet_expr * arg)721 __isl_give pet_expr *pet_expr_set_arg(__isl_take pet_expr *expr, int pos,
722 __isl_take pet_expr *arg)
723 {
724 if (!expr || !arg)
725 goto error;
726 if (pos < 0 || pos >= expr->n_arg)
727 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
728 "position out of bounds", goto error);
729 if (expr->args[pos] == arg) {
730 pet_expr_free(arg);
731 return expr;
732 }
733
734 expr = pet_expr_cow(expr);
735 if (!expr)
736 goto error;
737
738 pet_expr_free(expr->args[pos]);
739 expr->args[pos] = arg;
740
741 return expr;
742 error:
743 pet_expr_free(expr);
744 pet_expr_free(arg);
745 return NULL;
746 }
747
748 /* Does "expr" perform a comparison operation?
749 */
pet_expr_is_comparison(__isl_keep pet_expr * expr)750 int pet_expr_is_comparison(__isl_keep pet_expr *expr)
751 {
752 if (!expr)
753 return -1;
754 if (expr->type != pet_expr_op)
755 return 0;
756 switch (expr->op) {
757 case pet_op_eq:
758 case pet_op_ne:
759 case pet_op_le:
760 case pet_op_ge:
761 case pet_op_lt:
762 case pet_op_gt:
763 return 1;
764 default:
765 return 0;
766 }
767 }
768
769 /* Does "expr" perform a boolean operation?
770 */
pet_expr_is_boolean(__isl_keep pet_expr * expr)771 int pet_expr_is_boolean(__isl_keep pet_expr *expr)
772 {
773 if (!expr)
774 return -1;
775 if (expr->type != pet_expr_op)
776 return 0;
777 switch (expr->op) {
778 case pet_op_land:
779 case pet_op_lor:
780 case pet_op_lnot:
781 return 1;
782 default:
783 return 0;
784 }
785 }
786
787 /* Is "expr" an address-of operation?
788 */
pet_expr_is_address_of(__isl_keep pet_expr * expr)789 int pet_expr_is_address_of(__isl_keep pet_expr *expr)
790 {
791 if (!expr)
792 return -1;
793 if (expr->type != pet_expr_op)
794 return 0;
795 return expr->op == pet_op_address_of;
796 }
797
798 /* Is "expr" an assume statement?
799 */
pet_expr_is_assume(__isl_keep pet_expr * expr)800 int pet_expr_is_assume(__isl_keep pet_expr *expr)
801 {
802 if (!expr)
803 return -1;
804 if (expr->type != pet_expr_op)
805 return 0;
806 return expr->op == pet_op_assume;
807 }
808
809 /* Does "expr" perform a min operation?
810 */
pet_expr_is_min(__isl_keep pet_expr * expr)811 int pet_expr_is_min(__isl_keep pet_expr *expr)
812 {
813 if (!expr)
814 return -1;
815 if (expr->type != pet_expr_call)
816 return 0;
817 if (expr->n_arg != 2)
818 return 0;
819 if (strcmp(expr->c.name, "min") != 0)
820 return 0;
821 return 1;
822 }
823
824 /* Does "expr" perform a max operation?
825 */
pet_expr_is_max(__isl_keep pet_expr * expr)826 int pet_expr_is_max(__isl_keep pet_expr *expr)
827 {
828 if (!expr)
829 return -1;
830 if (expr->type != pet_expr_call)
831 return 0;
832 if (expr->n_arg != 2)
833 return 0;
834 if (strcmp(expr->c.name, "max") != 0)
835 return 0;
836 return 1;
837 }
838
839 /* Does "expr" represent an access to an unnamed space, i.e.,
840 * does it represent an affine expression?
841 */
pet_expr_is_affine(__isl_keep pet_expr * expr)842 isl_bool pet_expr_is_affine(__isl_keep pet_expr *expr)
843 {
844 int has_id;
845
846 if (!expr)
847 return isl_bool_error;
848 if (expr->type != pet_expr_access)
849 return isl_bool_false;
850
851 has_id = isl_multi_pw_aff_has_tuple_id(expr->acc.index, isl_dim_out);
852 if (has_id < 0)
853 return isl_bool_error;
854
855 return !has_id;
856 }
857
858 /* Given that "expr" represents an affine expression, i.e., that
859 * it is an access to an unnamed (1D) space, return this affine expression.
860 */
pet_expr_get_affine(__isl_keep pet_expr * expr)861 __isl_give isl_pw_aff *pet_expr_get_affine(__isl_keep pet_expr *expr)
862 {
863 isl_bool is_affine;
864 isl_pw_aff *pa;
865 isl_multi_pw_aff *mpa;
866
867 is_affine = pet_expr_is_affine(expr);
868 if (is_affine < 0)
869 return NULL;
870 if (!is_affine)
871 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
872 "not an affine expression", return NULL);
873
874 mpa = pet_expr_access_get_index(expr);
875 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
876 isl_multi_pw_aff_free(mpa);
877 return pa;
878 }
879
880 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
881 * not part of any struct?
882 */
pet_expr_is_scalar_access(__isl_keep pet_expr * expr)883 int pet_expr_is_scalar_access(__isl_keep pet_expr *expr)
884 {
885 if (!expr)
886 return -1;
887 if (expr->type != pet_expr_access)
888 return 0;
889 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index))
890 return 0;
891
892 return expr->acc.depth == 0;
893 }
894
895 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
896 * of parameters.
897 */
multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff * mpa1,__isl_keep isl_multi_pw_aff * mpa2)898 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1,
899 __isl_keep isl_multi_pw_aff *mpa2)
900 {
901 int equal;
902
903 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
904 if (equal < 0 || equal)
905 return equal;
906 mpa2 = isl_multi_pw_aff_copy(mpa2);
907 mpa2 = isl_multi_pw_aff_align_params(mpa2,
908 isl_multi_pw_aff_get_space(mpa1));
909 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
910 isl_multi_pw_aff_free(mpa2);
911
912 return equal;
913 }
914
915 /* Construct an access relation from the index expression and
916 * the array depth of the access expression "expr".
917 *
918 * If the number of indices is smaller than the depth of the array,
919 * then we assume that all elements of the remaining dimensions
920 * are accessed.
921 */
construct_access_relation(__isl_keep pet_expr * expr)922 static __isl_give isl_union_map *construct_access_relation(
923 __isl_keep pet_expr *expr)
924 {
925 isl_map *access;
926 int dim;
927
928 if (!expr)
929 return NULL;
930
931 access = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
932 if (!access)
933 return NULL;
934
935 dim = isl_map_dim(access, isl_dim_out);
936 if (dim > expr->acc.depth)
937 isl_die(isl_map_get_ctx(access), isl_error_internal,
938 "number of indices greater than depth",
939 access = isl_map_free(access));
940
941 if (dim != expr->acc.depth)
942 access = extend_range(access, expr->acc.depth - dim);
943
944 return isl_union_map_from_map(access);
945 }
946
947 /* Ensure that all relevant access relations are explicitly
948 * available in "expr".
949 *
950 * If "expr" does not already have the relevant access relations, then create
951 * them based on the index expression and the array depth.
952 *
953 * We do not cow since adding an explicit access relation
954 * does not change the meaning of the expression.
955 * However, the explicit access relations may modify the hash value,
956 * so the cached value is reset.
957 */
introduce_access_relations(__isl_take pet_expr * expr)958 static __isl_give pet_expr *introduce_access_relations(
959 __isl_take pet_expr *expr)
960 {
961 isl_union_map *access;
962 int kill, read, write;
963
964 if (!expr)
965 return NULL;
966 if (has_relevant_access_relations(expr))
967 return expr;
968
969 access = construct_access_relation(expr);
970 if (!access)
971 return pet_expr_free(expr);
972
973 expr->hash = 0;
974 kill = expr->acc.kill;
975 read = expr->acc.read;
976 write = expr->acc.write;
977 if (kill && !expr->acc.access[pet_expr_access_fake_killed])
978 expr->acc.access[pet_expr_access_fake_killed] =
979 isl_union_map_copy(access);
980 if (read && !expr->acc.access[pet_expr_access_may_read])
981 expr->acc.access[pet_expr_access_may_read] =
982 isl_union_map_copy(access);
983 if (write && !expr->acc.access[pet_expr_access_may_write])
984 expr->acc.access[pet_expr_access_may_write] =
985 isl_union_map_copy(access);
986 if (write && !expr->acc.access[pet_expr_access_must_write])
987 expr->acc.access[pet_expr_access_must_write] =
988 isl_union_map_copy(access);
989
990 isl_union_map_free(access);
991
992 if (!has_relevant_access_relations(expr))
993 return pet_expr_free(expr);
994
995 return expr;
996 }
997
998 /* Return a hash value that digests "expr".
999 * If a hash value was computed already, then return that value.
1000 * Otherwise, compute the hash value and store a copy in expr->hash.
1001 */
pet_expr_get_hash(__isl_keep pet_expr * expr)1002 uint32_t pet_expr_get_hash(__isl_keep pet_expr *expr)
1003 {
1004 int i;
1005 enum pet_expr_access_type type;
1006 uint32_t hash, hash_f;
1007
1008 if (!expr)
1009 return 0;
1010 if (expr->hash)
1011 return expr->hash;
1012
1013 hash = isl_hash_init();
1014 isl_hash_byte(hash, expr->type & 0xFF);
1015 isl_hash_byte(hash, expr->n_arg & 0xFF);
1016 for (i = 0; i < expr->n_arg; ++i) {
1017 uint32_t hash_i;
1018 hash_i = pet_expr_get_hash(expr->args[i]);
1019 isl_hash_hash(hash, hash_i);
1020 }
1021 switch (expr->type) {
1022 case pet_expr_error:
1023 return 0;
1024 case pet_expr_double:
1025 hash = isl_hash_string(hash, expr->d.s);
1026 break;
1027 case pet_expr_int:
1028 hash_f = isl_val_get_hash(expr->i);
1029 isl_hash_hash(hash, hash_f);
1030 break;
1031 case pet_expr_access:
1032 isl_hash_byte(hash, expr->acc.read & 0xFF);
1033 isl_hash_byte(hash, expr->acc.write & 0xFF);
1034 isl_hash_byte(hash, expr->acc.kill & 0xFF);
1035 hash_f = isl_id_get_hash(expr->acc.ref_id);
1036 isl_hash_hash(hash, hash_f);
1037 hash_f = isl_multi_pw_aff_get_hash(expr->acc.index);
1038 isl_hash_hash(hash, hash_f);
1039 isl_hash_byte(hash, expr->acc.depth & 0xFF);
1040 for (type = pet_expr_access_begin;
1041 type < pet_expr_access_end; ++type) {
1042 hash_f = isl_union_map_get_hash(expr->acc.access[type]);
1043 isl_hash_hash(hash, hash_f);
1044 }
1045 break;
1046 case pet_expr_op:
1047 isl_hash_byte(hash, expr->op & 0xFF);
1048 break;
1049 case pet_expr_call:
1050 hash = isl_hash_string(hash, expr->c.name);
1051 break;
1052 case pet_expr_cast:
1053 hash = isl_hash_string(hash, expr->type_name);
1054 break;
1055 }
1056 expr->hash = hash;
1057 return hash;
1058 }
1059
1060 /* Return 1 if the two pet_exprs are equivalent.
1061 */
pet_expr_is_equal(__isl_keep pet_expr * expr1,__isl_keep pet_expr * expr2)1062 int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2)
1063 {
1064 int i;
1065 enum pet_expr_access_type type;
1066
1067 if (!expr1 || !expr2)
1068 return 0;
1069
1070 if (expr1->type != expr2->type)
1071 return 0;
1072 if (expr1->n_arg != expr2->n_arg)
1073 return 0;
1074 for (i = 0; i < expr1->n_arg; ++i)
1075 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
1076 return 0;
1077 switch (expr1->type) {
1078 case pet_expr_error:
1079 return -1;
1080 case pet_expr_double:
1081 if (strcmp(expr1->d.s, expr2->d.s))
1082 return 0;
1083 if (expr1->d.val != expr2->d.val)
1084 return 0;
1085 break;
1086 case pet_expr_int:
1087 if (!isl_val_eq(expr1->i, expr2->i))
1088 return 0;
1089 break;
1090 case pet_expr_access:
1091 if (expr1->acc.read != expr2->acc.read)
1092 return 0;
1093 if (expr1->acc.write != expr2->acc.write)
1094 return 0;
1095 if (expr1->acc.kill != expr2->acc.kill)
1096 return 0;
1097 if (expr1->acc.ref_id != expr2->acc.ref_id)
1098 return 0;
1099 if (!expr1->acc.index || !expr2->acc.index)
1100 return 0;
1101 if (!multi_pw_aff_is_equal(expr1->acc.index, expr2->acc.index))
1102 return 0;
1103 if (expr1->acc.depth != expr2->acc.depth)
1104 return 0;
1105 if (has_relevant_access_relations(expr1) !=
1106 has_relevant_access_relations(expr2)) {
1107 int equal;
1108 expr1 = pet_expr_copy(expr1);
1109 expr2 = pet_expr_copy(expr2);
1110 expr1 = introduce_access_relations(expr1);
1111 expr2 = introduce_access_relations(expr2);
1112 equal = pet_expr_is_equal(expr1, expr2);
1113 pet_expr_free(expr1);
1114 pet_expr_free(expr2);
1115 return equal;
1116 }
1117 for (type = pet_expr_access_begin;
1118 type < pet_expr_access_end; ++type) {
1119 if (!expr1->acc.access[type] !=
1120 !expr2->acc.access[type])
1121 return 0;
1122 if (!expr1->acc.access[type])
1123 continue;
1124 if (!isl_union_map_is_equal(expr1->acc.access[type],
1125 expr2->acc.access[type]))
1126 return 0;
1127 }
1128 break;
1129 case pet_expr_op:
1130 if (expr1->op != expr2->op)
1131 return 0;
1132 break;
1133 case pet_expr_call:
1134 if (strcmp(expr1->c.name, expr2->c.name))
1135 return 0;
1136 break;
1137 case pet_expr_cast:
1138 if (strcmp(expr1->type_name, expr2->type_name))
1139 return 0;
1140 break;
1141 }
1142
1143 return 1;
1144 }
1145
1146 /* Do "expr1" and "expr2" represent two accesses to the same array
1147 * that are also of the same type? That is, can these two accesses
1148 * be replaced by a single access?
1149 */
pet_expr_is_same_access(__isl_keep pet_expr * expr1,__isl_keep pet_expr * expr2)1150 isl_bool pet_expr_is_same_access(__isl_keep pet_expr *expr1,
1151 __isl_keep pet_expr *expr2)
1152 {
1153 isl_space *space1, *space2;
1154 isl_bool same;
1155
1156 if (!expr1 || !expr2)
1157 return isl_bool_error;
1158 if (pet_expr_get_type(expr1) != pet_expr_access)
1159 return isl_bool_false;
1160 if (pet_expr_get_type(expr2) != pet_expr_access)
1161 return isl_bool_false;
1162 if (expr1->acc.read != expr2->acc.read)
1163 return isl_bool_false;
1164 if (expr1->acc.write != expr2->acc.write)
1165 return isl_bool_false;
1166 if (expr1->acc.kill != expr2->acc.kill)
1167 return isl_bool_false;
1168 if (expr1->acc.depth != expr2->acc.depth)
1169 return isl_bool_false;
1170
1171 space1 = isl_multi_pw_aff_get_space(expr1->acc.index);
1172 space2 = isl_multi_pw_aff_get_space(expr2->acc.index);
1173 same = isl_space_tuple_is_equal(space1, isl_dim_out,
1174 space2, isl_dim_out);
1175 if (same >= 0 && same)
1176 same = isl_space_tuple_is_equal(space1, isl_dim_in,
1177 space2, isl_dim_in);
1178 isl_space_free(space1);
1179 isl_space_free(space2);
1180
1181 return same;
1182 }
1183
1184 /* Does the access expression "expr" read the accessed elements?
1185 */
pet_expr_access_is_read(__isl_keep pet_expr * expr)1186 isl_bool pet_expr_access_is_read(__isl_keep pet_expr *expr)
1187 {
1188 if (!expr)
1189 return isl_bool_error;
1190 if (expr->type != pet_expr_access)
1191 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1192 "not an access expression", return isl_bool_error);
1193
1194 return expr->acc.read;
1195 }
1196
1197 /* Does the access expression "expr" write to the accessed elements?
1198 */
pet_expr_access_is_write(__isl_keep pet_expr * expr)1199 isl_bool pet_expr_access_is_write(__isl_keep pet_expr *expr)
1200 {
1201 if (!expr)
1202 return isl_bool_error;
1203 if (expr->type != pet_expr_access)
1204 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1205 "not an access expression", return isl_bool_error);
1206
1207 return expr->acc.write;
1208 }
1209
1210 /* Does the access expression "expr" kill the accessed elements?
1211 */
pet_expr_access_is_kill(__isl_keep pet_expr * expr)1212 isl_bool pet_expr_access_is_kill(__isl_keep pet_expr *expr)
1213 {
1214 if (!expr)
1215 return isl_bool_error;
1216 if (expr->type != pet_expr_access)
1217 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1218 "not an access expression", return isl_bool_error);
1219
1220 return expr->acc.kill;
1221 }
1222
1223 /* Return the identifier of the array accessed by "expr".
1224 *
1225 * If "expr" represents a member access, then return the identifier
1226 * of the outer structure array.
1227 */
pet_expr_access_get_id(__isl_keep pet_expr * expr)1228 __isl_give isl_id *pet_expr_access_get_id(__isl_keep pet_expr *expr)
1229 {
1230 if (!expr)
1231 return NULL;
1232 if (expr->type != pet_expr_access)
1233 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1234 "not an access expression", return NULL);
1235
1236 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index)) {
1237 isl_space *space;
1238 isl_id *id;
1239
1240 space = isl_multi_pw_aff_get_space(expr->acc.index);
1241 space = isl_space_range(space);
1242 while (space && isl_space_is_wrapping(space))
1243 space = isl_space_domain(isl_space_unwrap(space));
1244 id = isl_space_get_tuple_id(space, isl_dim_set);
1245 isl_space_free(space);
1246
1247 return id;
1248 }
1249
1250 return isl_multi_pw_aff_get_tuple_id(expr->acc.index, isl_dim_out);
1251 }
1252
1253 /* Return the parameter space of "expr".
1254 */
pet_expr_access_get_parameter_space(__isl_keep pet_expr * expr)1255 __isl_give isl_space *pet_expr_access_get_parameter_space(
1256 __isl_keep pet_expr *expr)
1257 {
1258 isl_space *space;
1259
1260 if (!expr)
1261 return NULL;
1262 if (expr->type != pet_expr_access)
1263 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1264 "not an access expression", return NULL);
1265
1266 space = isl_multi_pw_aff_get_space(expr->acc.index);
1267 space = isl_space_params(space);
1268
1269 return space;
1270 }
1271
1272 /* Return the domain space of "expr", including the arguments (if any).
1273 */
pet_expr_access_get_augmented_domain_space(__isl_keep pet_expr * expr)1274 __isl_give isl_space *pet_expr_access_get_augmented_domain_space(
1275 __isl_keep pet_expr *expr)
1276 {
1277 isl_space *space;
1278
1279 if (!expr)
1280 return NULL;
1281 if (expr->type != pet_expr_access)
1282 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1283 "not an access expression", return NULL);
1284
1285 space = isl_multi_pw_aff_get_space(expr->acc.index);
1286 space = isl_space_domain(space);
1287
1288 return space;
1289 }
1290
1291 /* Return the domain space of "expr", without the arguments (if any).
1292 */
pet_expr_access_get_domain_space(__isl_keep pet_expr * expr)1293 __isl_give isl_space *pet_expr_access_get_domain_space(
1294 __isl_keep pet_expr *expr)
1295 {
1296 isl_space *space;
1297
1298 space = pet_expr_access_get_augmented_domain_space(expr);
1299 if (isl_space_is_wrapping(space))
1300 space = isl_space_domain(isl_space_unwrap(space));
1301
1302 return space;
1303 }
1304
1305 /* Internal data structure for pet_expr_access_foreach_data_space.
1306 */
1307 struct pet_foreach_data_space_data {
1308 isl_stat (*fn)(__isl_take isl_space *space, void *user);
1309 void *user;
1310 };
1311
1312 /* Given a piece of an access relation, call data->fn on the data
1313 * (i.e., range) space.
1314 */
foreach_data_space(__isl_take isl_map * map,void * user)1315 static isl_stat foreach_data_space(__isl_take isl_map *map, void *user)
1316 {
1317 struct pet_foreach_data_space_data *data = user;
1318 isl_space *space;
1319
1320 space = isl_map_get_space(map);
1321 space = isl_space_range(space);
1322 isl_map_free(map);
1323
1324 return data->fn(space, data->user);
1325 }
1326
1327 /* Call "fn" on the data spaces accessed by "expr".
1328 * In particular, call "fn" on the range space of the index expression,
1329 * but if "expr" keeps track of any explicit access relations,
1330 * then also call "fn" on the corresponding range spaces.
1331 */
pet_expr_access_foreach_data_space(__isl_keep pet_expr * expr,isl_stat (* fn)(__isl_take isl_space * space,void * user),void * user)1332 isl_stat pet_expr_access_foreach_data_space(__isl_keep pet_expr *expr,
1333 isl_stat (*fn)(__isl_take isl_space *space, void *user), void *user)
1334 {
1335 struct pet_foreach_data_space_data data = { fn, user };
1336 enum pet_expr_access_type type;
1337 isl_space *space;
1338
1339 if (!expr)
1340 return isl_stat_error;
1341 if (expr->type != pet_expr_access)
1342 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1343 "not an access expression", return isl_stat_error);
1344
1345 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1346 if (!expr->acc.access[type])
1347 continue;
1348 if (isl_union_map_foreach_map(expr->acc.access[type],
1349 &foreach_data_space, &data) < 0)
1350 return isl_stat_error;
1351 }
1352
1353 space = isl_multi_pw_aff_get_space(expr->acc.index);
1354 space = isl_space_range(space);
1355 return fn(space, user);
1356 }
1357
1358 /* Modify all subexpressions of "expr" by calling "fn" on them.
1359 * The subexpressions are traversed in depth first preorder.
1360 */
pet_expr_map_top_down(__isl_take pet_expr * expr,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1361 __isl_give pet_expr *pet_expr_map_top_down(__isl_take pet_expr *expr,
1362 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1363 void *user)
1364 {
1365 int i, n;
1366
1367 if (!expr)
1368 return NULL;
1369
1370 expr = fn(expr, user);
1371
1372 n = pet_expr_get_n_arg(expr);
1373 for (i = 0; i < n; ++i) {
1374 pet_expr *arg = pet_expr_get_arg(expr, i);
1375 arg = pet_expr_map_top_down(arg, fn, user);
1376 expr = pet_expr_set_arg(expr, i, arg);
1377 }
1378
1379 return expr;
1380 }
1381
1382 /* Modify all expressions of type "type" in "expr" by calling "fn" on them.
1383 */
pet_expr_map_expr_of_type(__isl_take pet_expr * expr,enum pet_expr_type type,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1384 static __isl_give pet_expr *pet_expr_map_expr_of_type(__isl_take pet_expr *expr,
1385 enum pet_expr_type type,
1386 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1387 void *user)
1388 {
1389 int i, n;
1390
1391 n = pet_expr_get_n_arg(expr);
1392 for (i = 0; i < n; ++i) {
1393 pet_expr *arg = pet_expr_get_arg(expr, i);
1394 arg = pet_expr_map_expr_of_type(arg, type, fn, user);
1395 expr = pet_expr_set_arg(expr, i, arg);
1396 }
1397
1398 if (!expr)
1399 return NULL;
1400
1401 if (expr->type == type)
1402 expr = fn(expr, user);
1403
1404 return expr;
1405 }
1406
1407 /* Modify all expressions of type pet_expr_access in "expr"
1408 * by calling "fn" on them.
1409 */
pet_expr_map_access(__isl_take pet_expr * expr,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1410 __isl_give pet_expr *pet_expr_map_access(__isl_take pet_expr *expr,
1411 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1412 void *user)
1413 {
1414 return pet_expr_map_expr_of_type(expr, pet_expr_access, fn, user);
1415 }
1416
1417 /* Modify all expressions of type pet_expr_call in "expr"
1418 * by calling "fn" on them.
1419 */
pet_expr_map_call(__isl_take pet_expr * expr,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1420 __isl_give pet_expr *pet_expr_map_call(__isl_take pet_expr *expr,
1421 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1422 void *user)
1423 {
1424 return pet_expr_map_expr_of_type(expr, pet_expr_call, fn, user);
1425 }
1426
1427 /* Modify all expressions of type pet_expr_op in "expr"
1428 * by calling "fn" on them.
1429 */
pet_expr_map_op(__isl_take pet_expr * expr,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1430 __isl_give pet_expr *pet_expr_map_op(__isl_take pet_expr *expr,
1431 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1432 void *user)
1433 {
1434 return pet_expr_map_expr_of_type(expr, pet_expr_op, fn, user);
1435 }
1436
1437 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1438 *
1439 * Return -1 on error (where fn returning a negative value is treated as
1440 * an error).
1441 * Otherwise return 0.
1442 */
pet_expr_foreach_expr_of_type(__isl_keep pet_expr * expr,enum pet_expr_type type,int (* fn)(__isl_keep pet_expr * expr,void * user),void * user)1443 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr *expr,
1444 enum pet_expr_type type,
1445 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1446 {
1447 int i;
1448
1449 if (!expr)
1450 return -1;
1451
1452 for (i = 0; i < expr->n_arg; ++i)
1453 if (pet_expr_foreach_expr_of_type(expr->args[i],
1454 type, fn, user) < 0)
1455 return -1;
1456
1457 if (expr->type == type)
1458 return fn(expr, user);
1459
1460 return 0;
1461 }
1462
1463 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1464 *
1465 * Return -1 on error (where fn returning a negative value is treated as
1466 * an error).
1467 * Otherwise return 0.
1468 */
pet_expr_foreach_access_expr(__isl_keep pet_expr * expr,int (* fn)(__isl_keep pet_expr * expr,void * user),void * user)1469 int pet_expr_foreach_access_expr(__isl_keep pet_expr *expr,
1470 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1471 {
1472 return pet_expr_foreach_expr_of_type(expr, pet_expr_access, fn, user);
1473 }
1474
1475 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1476 *
1477 * Return -1 on error (where fn returning a negative value is treated as
1478 * an error).
1479 * Otherwise return 0.
1480 */
pet_expr_foreach_call_expr(__isl_keep pet_expr * expr,int (* fn)(__isl_keep pet_expr * expr,void * user),void * user)1481 int pet_expr_foreach_call_expr(__isl_keep pet_expr *expr,
1482 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1483 {
1484 return pet_expr_foreach_expr_of_type(expr, pet_expr_call, fn, user);
1485 }
1486
1487 /* Internal data structure for pet_expr_writes.
1488 * "id" is the identifier that we are looking for.
1489 * "found" is set if we have found the identifier being written to.
1490 */
1491 struct pet_expr_writes_data {
1492 isl_id *id;
1493 int found;
1494 };
1495
1496 /* Given an access expression, check if it writes to data->id.
1497 * If so, set data->found and abort the search.
1498 */
writes(__isl_keep pet_expr * expr,void * user)1499 static int writes(__isl_keep pet_expr *expr, void *user)
1500 {
1501 struct pet_expr_writes_data *data = user;
1502 isl_id *write_id;
1503
1504 if (!expr->acc.write)
1505 return 0;
1506 if (pet_expr_is_affine(expr))
1507 return 0;
1508
1509 write_id = pet_expr_access_get_id(expr);
1510 isl_id_free(write_id);
1511
1512 if (!write_id)
1513 return -1;
1514
1515 if (write_id != data->id)
1516 return 0;
1517
1518 data->found = 1;
1519 return -1;
1520 }
1521
1522 /* Does expression "expr" write to "id"?
1523 */
pet_expr_writes(__isl_keep pet_expr * expr,__isl_keep isl_id * id)1524 int pet_expr_writes(__isl_keep pet_expr *expr, __isl_keep isl_id *id)
1525 {
1526 struct pet_expr_writes_data data;
1527
1528 data.id = id;
1529 data.found = 0;
1530 if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
1531 !data.found)
1532 return -1;
1533
1534 return data.found;
1535 }
1536
1537 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1538 * index expression and access relations of "expr" (if any)
1539 * to dimensions of "dst_type" at "dst_pos".
1540 */
pet_expr_access_move_dims(__isl_take pet_expr * expr,enum isl_dim_type dst_type,unsigned dst_pos,enum isl_dim_type src_type,unsigned src_pos,unsigned n)1541 __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr,
1542 enum isl_dim_type dst_type, unsigned dst_pos,
1543 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1544 {
1545 enum pet_expr_access_type type;
1546
1547 expr = pet_expr_cow(expr);
1548 if (!expr)
1549 return NULL;
1550 if (expr->type != pet_expr_access)
1551 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1552 "not an access pet_expr", return pet_expr_free(expr));
1553
1554 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1555 if (!expr->acc.access[type])
1556 continue;
1557 expr->acc.access[type] =
1558 pet_union_map_move_dims(expr->acc.access[type],
1559 dst_type, dst_pos, src_type, src_pos, n);
1560 if (!expr->acc.access[type])
1561 break;
1562 }
1563 expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index,
1564 dst_type, dst_pos, src_type, src_pos, n);
1565 if (!expr->acc.index || type < pet_expr_access_end)
1566 return pet_expr_free(expr);
1567
1568 return expr;
1569 }
1570
1571 /* Replace the index expression and access relations (if any) of "expr"
1572 * by their preimages under the function represented by "ma".
1573 */
pet_expr_access_pullback_multi_aff(__isl_take pet_expr * expr,__isl_take isl_multi_aff * ma)1574 __isl_give pet_expr *pet_expr_access_pullback_multi_aff(
1575 __isl_take pet_expr *expr, __isl_take isl_multi_aff *ma)
1576 {
1577 enum pet_expr_access_type type;
1578
1579 expr = pet_expr_cow(expr);
1580 if (!expr || !ma)
1581 goto error;
1582 if (expr->type != pet_expr_access)
1583 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1584 "not an access pet_expr", goto error);
1585
1586 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1587 if (!expr->acc.access[type])
1588 continue;
1589 expr->acc.access[type] =
1590 isl_union_map_preimage_domain_multi_aff(
1591 expr->acc.access[type], isl_multi_aff_copy(ma));
1592 if (!expr->acc.access[type])
1593 break;
1594 }
1595 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
1596 ma);
1597 if (!expr->acc.index || type < pet_expr_access_end)
1598 return pet_expr_free(expr);
1599
1600 return expr;
1601 error:
1602 isl_multi_aff_free(ma);
1603 pet_expr_free(expr);
1604 return NULL;
1605 }
1606
1607 /* Replace the index expression and access relations (if any) of "expr"
1608 * by their preimages under the function represented by "mpa".
1609 */
pet_expr_access_pullback_multi_pw_aff(__isl_take pet_expr * expr,__isl_take isl_multi_pw_aff * mpa)1610 __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff(
1611 __isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *mpa)
1612 {
1613 enum pet_expr_access_type type;
1614
1615 expr = pet_expr_cow(expr);
1616 if (!expr || !mpa)
1617 goto error;
1618 if (expr->type != pet_expr_access)
1619 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1620 "not an access pet_expr", goto error);
1621
1622 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1623 if (!expr->acc.access[type])
1624 continue;
1625 expr->acc.access[type] =
1626 isl_union_map_preimage_domain_multi_pw_aff(
1627 expr->acc.access[type], isl_multi_pw_aff_copy(mpa));
1628 if (!expr->acc.access[type])
1629 break;
1630 }
1631 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1632 expr->acc.index, mpa);
1633 if (!expr->acc.index || type < pet_expr_access_end)
1634 return pet_expr_free(expr);
1635
1636 return expr;
1637 error:
1638 isl_multi_pw_aff_free(mpa);
1639 pet_expr_free(expr);
1640 return NULL;
1641 }
1642
1643 /* Return the index expression of access expression "expr".
1644 */
pet_expr_access_get_index(__isl_keep pet_expr * expr)1645 __isl_give isl_multi_pw_aff *pet_expr_access_get_index(
1646 __isl_keep pet_expr *expr)
1647 {
1648 if (!expr)
1649 return NULL;
1650 if (expr->type != pet_expr_access)
1651 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1652 "not an access expression", return NULL);
1653
1654 return isl_multi_pw_aff_copy(expr->acc.index);
1655 }
1656
1657 /* Align the parameters of expr->acc.index and expr->acc.access[*] (if set).
1658 */
pet_expr_access_align_params(__isl_take pet_expr * expr)1659 __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr)
1660 {
1661 isl_space *space;
1662 enum pet_expr_access_type type;
1663
1664 expr = pet_expr_cow(expr);
1665 if (!expr)
1666 return NULL;
1667 if (expr->type != pet_expr_access)
1668 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1669 "not an access expression", return pet_expr_free(expr));
1670
1671 if (!pet_expr_access_has_any_access_relation(expr))
1672 return expr;
1673
1674 space = isl_multi_pw_aff_get_space(expr->acc.index);
1675 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1676 if (!expr->acc.access[type])
1677 continue;
1678 space = isl_space_align_params(space,
1679 isl_union_map_get_space(expr->acc.access[type]));
1680 }
1681 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1682 isl_space_copy(space));
1683 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1684 if (!expr->acc.access[type])
1685 continue;
1686 expr->acc.access[type] =
1687 isl_union_map_align_params(expr->acc.access[type],
1688 isl_space_copy(space));
1689 if (!expr->acc.access[type])
1690 break;
1691 }
1692 isl_space_free(space);
1693 if (!expr->acc.index || type < pet_expr_access_end)
1694 return pet_expr_free(expr);
1695
1696 return expr;
1697 }
1698
1699 /* Are "expr1" and "expr2" both array accesses such that
1700 * the access relation of "expr1" is a subset of that of "expr2"?
1701 * Only take into account the first "n_arg" arguments.
1702 *
1703 * This function is tailored for use by mark_self_dependences in nest.c.
1704 * In particular, the input expressions may have more than "n_arg"
1705 * elements in their arguments arrays, while only the first "n_arg"
1706 * elements are referenced from the access relations.
1707 */
pet_expr_is_sub_access(__isl_keep pet_expr * expr1,__isl_keep pet_expr * expr2,int n_arg)1708 int pet_expr_is_sub_access(__isl_keep pet_expr *expr1,
1709 __isl_keep pet_expr *expr2, int n_arg)
1710 {
1711 isl_id *id1, *id2;
1712 int i, n1, n2;
1713 int is_subset;
1714
1715 if (!expr1 || !expr2)
1716 return 0;
1717 if (pet_expr_get_type(expr1) != pet_expr_access)
1718 return 0;
1719 if (pet_expr_get_type(expr2) != pet_expr_access)
1720 return 0;
1721 if (pet_expr_is_affine(expr1))
1722 return 0;
1723 if (pet_expr_is_affine(expr2))
1724 return 0;
1725 n1 = pet_expr_get_n_arg(expr1);
1726 if (n1 > n_arg)
1727 n1 = n_arg;
1728 n2 = pet_expr_get_n_arg(expr2);
1729 if (n2 > n_arg)
1730 n2 = n_arg;
1731 if (n1 != n2)
1732 return 0;
1733 for (i = 0; i < n1; ++i) {
1734 int equal;
1735 equal = pet_expr_is_equal(expr1->args[i], expr2->args[i]);
1736 if (equal < 0 || !equal)
1737 return equal;
1738 }
1739 id1 = pet_expr_access_get_id(expr1);
1740 id2 = pet_expr_access_get_id(expr2);
1741 isl_id_free(id1);
1742 isl_id_free(id2);
1743 if (!id1 || !id2)
1744 return 0;
1745 if (id1 != id2)
1746 return 0;
1747
1748 expr1 = pet_expr_copy(expr1);
1749 expr2 = pet_expr_copy(expr2);
1750 expr1 = introduce_access_relations(expr1);
1751 expr2 = introduce_access_relations(expr2);
1752 if (!expr1 || !expr2)
1753 goto error;
1754
1755 is_subset = isl_union_map_is_subset(
1756 expr1->acc.access[pet_expr_access_may_read],
1757 expr2->acc.access[pet_expr_access_may_read]);
1758
1759 pet_expr_free(expr1);
1760 pet_expr_free(expr2);
1761
1762 return is_subset;
1763 error:
1764 pet_expr_free(expr1);
1765 pet_expr_free(expr2);
1766 return -1;
1767 }
1768
1769 /* Given a set in the iteration space "domain", extend it to live in the space
1770 * of the domain of access relations.
1771 *
1772 * That, is the number of arguments "n" is 0, then simply return domain.
1773 * Otherwise, return [domain -> [a_1,...,a_n]].
1774 */
add_arguments(__isl_take isl_set * domain,int n)1775 static __isl_give isl_set *add_arguments(__isl_take isl_set *domain, int n)
1776 {
1777 isl_map *map;
1778
1779 if (n == 0)
1780 return domain;
1781
1782 map = isl_map_from_domain(domain);
1783 map = isl_map_add_dims(map, isl_dim_out, n);
1784 return isl_map_wrap(map);
1785 }
1786
1787 /* Add extra conditions to the domains of all access relations in "expr",
1788 * introducing access relations if they are not already present.
1789 *
1790 * The conditions are not added to the index expression. Instead, they
1791 * are used to try and simplify the index expression.
1792 */
pet_expr_restrict(__isl_take pet_expr * expr,__isl_take isl_set * cond)1793 __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr,
1794 __isl_take isl_set *cond)
1795 {
1796 int i;
1797 isl_union_set *uset;
1798 enum pet_expr_access_type type;
1799
1800 expr = pet_expr_cow(expr);
1801 if (!expr)
1802 goto error;
1803
1804 for (i = 0; i < expr->n_arg; ++i) {
1805 expr->args[i] = pet_expr_restrict(expr->args[i],
1806 isl_set_copy(cond));
1807 if (!expr->args[i])
1808 goto error;
1809 }
1810
1811 if (expr->type != pet_expr_access) {
1812 isl_set_free(cond);
1813 return expr;
1814 }
1815
1816 expr = introduce_access_relations(expr);
1817 if (!expr)
1818 goto error;
1819
1820 cond = add_arguments(cond, expr->n_arg);
1821 uset = isl_union_set_from_set(isl_set_copy(cond));
1822 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1823 if (!expr->acc.access[type])
1824 continue;
1825 expr->acc.access[type] =
1826 isl_union_map_intersect_domain(expr->acc.access[type],
1827 isl_union_set_copy(uset));
1828 if (!expr->acc.access[type])
1829 break;
1830 }
1831 isl_union_set_free(uset);
1832 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, cond);
1833 if (type < pet_expr_access_end || !expr->acc.index)
1834 return pet_expr_free(expr);
1835
1836 return expr;
1837 error:
1838 isl_set_free(cond);
1839 return pet_expr_free(expr);
1840 }
1841
1842 /* Modify the access relations (if any) and index expression
1843 * of the given access expression
1844 * based on the given iteration space transformation.
1845 * In particular, precompose the access relation and index expression
1846 * with the update function.
1847 *
1848 * If the access has any arguments then the domain of the access relation
1849 * is a wrapped mapping from the iteration space to the space of
1850 * argument values. We only need to change the domain of this wrapped
1851 * mapping, so we extend the input transformation with an identity mapping
1852 * on the space of argument values.
1853 */
pet_expr_access_update_domain(__isl_take pet_expr * expr,__isl_keep isl_multi_pw_aff * update)1854 __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr,
1855 __isl_keep isl_multi_pw_aff *update)
1856 {
1857 enum pet_expr_access_type type;
1858
1859 expr = pet_expr_cow(expr);
1860 if (!expr)
1861 return NULL;
1862 if (expr->type != pet_expr_access)
1863 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1864 "not an access expression", return pet_expr_free(expr));
1865
1866 update = isl_multi_pw_aff_copy(update);
1867
1868 if (expr->n_arg > 0) {
1869 isl_space *space;
1870 isl_multi_pw_aff *id;
1871
1872 space = isl_multi_pw_aff_get_space(expr->acc.index);
1873 space = isl_space_domain(space);
1874 space = isl_space_unwrap(space);
1875 space = isl_space_range(space);
1876 space = isl_space_map_from_set(space);
1877 id = isl_multi_pw_aff_identity(space);
1878 update = isl_multi_pw_aff_product(update, id);
1879 }
1880
1881 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1882 if (!expr->acc.access[type])
1883 continue;
1884 expr->acc.access[type] =
1885 isl_union_map_preimage_domain_multi_pw_aff(
1886 expr->acc.access[type],
1887 isl_multi_pw_aff_copy(update));
1888 if (!expr->acc.access[type])
1889 break;
1890 }
1891 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1892 expr->acc.index, update);
1893 if (type < pet_expr_access_end || !expr->acc.index)
1894 return pet_expr_free(expr);
1895
1896 return expr;
1897 }
1898
update_domain(__isl_take pet_expr * expr,void * user)1899 static __isl_give pet_expr *update_domain(__isl_take pet_expr *expr, void *user)
1900 {
1901 isl_multi_pw_aff *update = user;
1902
1903 return pet_expr_access_update_domain(expr, update);
1904 }
1905
1906 /* Modify all access relations in "expr" by precomposing them with
1907 * the given iteration space transformation.
1908 */
pet_expr_update_domain(__isl_take pet_expr * expr,__isl_take isl_multi_pw_aff * update)1909 __isl_give pet_expr *pet_expr_update_domain(__isl_take pet_expr *expr,
1910 __isl_take isl_multi_pw_aff *update)
1911 {
1912 expr = pet_expr_map_access(expr, &update_domain, update);
1913 isl_multi_pw_aff_free(update);
1914 return expr;
1915 }
1916
1917 /* Given an expression with accesses that have a 0D anonymous domain,
1918 * replace those domains by "space".
1919 */
pet_expr_insert_domain(__isl_take pet_expr * expr,__isl_take isl_space * space)1920 __isl_give pet_expr *pet_expr_insert_domain(__isl_take pet_expr *expr,
1921 __isl_take isl_space *space)
1922 {
1923 isl_multi_pw_aff *mpa;
1924
1925 space = isl_space_from_domain(space);
1926 mpa = isl_multi_pw_aff_zero(space);
1927 return pet_expr_update_domain(expr, mpa);
1928 }
1929
1930 /* Add all parameters in "space" to the access relations (if any)
1931 * and index expression of "expr".
1932 */
align_params(__isl_take pet_expr * expr,void * user)1933 static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user)
1934 {
1935 isl_space *space = user;
1936 enum pet_expr_access_type type;
1937
1938 expr = pet_expr_cow(expr);
1939 if (!expr)
1940 return NULL;
1941 if (expr->type != pet_expr_access)
1942 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1943 "not an access expression", return pet_expr_free(expr));
1944
1945 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1946 if (!expr->acc.access[type])
1947 continue;
1948 expr->acc.access[type] =
1949 isl_union_map_align_params(expr->acc.access[type],
1950 isl_space_copy(space));
1951 if (!expr->acc.access[type])
1952 break;
1953 }
1954 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1955 isl_space_copy(space));
1956 if (type < pet_expr_access_end || !expr->acc.index)
1957 return pet_expr_free(expr);
1958
1959 return expr;
1960 }
1961
1962 /* Add all parameters in "space" to all access relations and index expressions
1963 * in "expr".
1964 */
pet_expr_align_params(__isl_take pet_expr * expr,__isl_take isl_space * space)1965 __isl_give pet_expr *pet_expr_align_params(__isl_take pet_expr *expr,
1966 __isl_take isl_space *space)
1967 {
1968 expr = pet_expr_map_access(expr, &align_params, space);
1969 isl_space_free(space);
1970 return expr;
1971 }
1972
1973 /* Insert an argument expression corresponding to "test" in front
1974 * of the list of arguments described by *n_arg and *args.
1975 */
insert_access_arg(__isl_take pet_expr * expr,__isl_keep isl_multi_pw_aff * test)1976 static __isl_give pet_expr *insert_access_arg(__isl_take pet_expr *expr,
1977 __isl_keep isl_multi_pw_aff *test)
1978 {
1979 int i;
1980 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1981
1982 if (!test)
1983 return pet_expr_free(expr);
1984 expr = pet_expr_cow(expr);
1985 if (!expr)
1986 return NULL;
1987
1988 if (!expr->args) {
1989 expr->args = isl_calloc_array(ctx, pet_expr *, 1);
1990 if (!expr->args)
1991 return pet_expr_free(expr);
1992 } else {
1993 pet_expr **ext;
1994 ext = isl_calloc_array(ctx, pet_expr *, 1 + expr->n_arg);
1995 if (!ext)
1996 return pet_expr_free(expr);
1997 for (i = 0; i < expr->n_arg; ++i)
1998 ext[1 + i] = expr->args[i];
1999 free(expr->args);
2000 expr->args = ext;
2001 }
2002 expr->n_arg++;
2003 expr->args[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
2004 if (!expr->args[0])
2005 return pet_expr_free(expr);
2006
2007 return expr;
2008 }
2009
2010 /* Make the expression "expr" depend on the value of "test"
2011 * being equal to "satisfied".
2012 *
2013 * If "test" is an affine expression, we simply add the conditions
2014 * on the expression having the value "satisfied" to all access relations
2015 * (introducing access relations if they are missing) and index expressions.
2016 *
2017 * Otherwise, we add a filter to "expr" (which is then assumed to be
2018 * an access expression) corresponding to "test" being equal to "satisfied".
2019 */
pet_expr_filter(__isl_take pet_expr * expr,__isl_take isl_multi_pw_aff * test,int satisfied)2020 __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr,
2021 __isl_take isl_multi_pw_aff *test, int satisfied)
2022 {
2023 isl_id *id;
2024 isl_ctx *ctx;
2025 isl_space *space;
2026 isl_pw_multi_aff *pma;
2027 enum pet_expr_access_type type;
2028
2029 expr = pet_expr_cow(expr);
2030 if (!expr || !test)
2031 goto error;
2032
2033 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
2034 isl_pw_aff *pa;
2035 isl_set *cond;
2036
2037 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
2038 isl_multi_pw_aff_free(test);
2039 if (satisfied)
2040 cond = isl_pw_aff_non_zero_set(pa);
2041 else
2042 cond = isl_pw_aff_zero_set(pa);
2043 return pet_expr_restrict(expr, cond);
2044 }
2045
2046 ctx = isl_multi_pw_aff_get_ctx(test);
2047 if (expr->type != pet_expr_access)
2048 isl_die(ctx, isl_error_invalid,
2049 "can only filter access expressions", goto error);
2050
2051 expr = introduce_access_relations(expr);
2052 if (!expr)
2053 goto error;
2054
2055 space = isl_space_domain(isl_multi_pw_aff_get_space(expr->acc.index));
2056 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2057 pma = pet_filter_insert_pma(space, id, satisfied);
2058
2059 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
2060 if (!expr->acc.access[type])
2061 continue;
2062 expr->acc.access[type] =
2063 isl_union_map_preimage_domain_pw_multi_aff(
2064 expr->acc.access[type],
2065 isl_pw_multi_aff_copy(pma));
2066 if (!expr->acc.access[type])
2067 break;
2068 }
2069 pma = isl_pw_multi_aff_gist(pma,
2070 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma)));
2071 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
2072 expr->acc.index, pma);
2073 if (type < pet_expr_access_end || !expr->acc.index)
2074 goto error;
2075
2076 expr = insert_access_arg(expr, test);
2077
2078 isl_multi_pw_aff_free(test);
2079 return expr;
2080 error:
2081 isl_multi_pw_aff_free(test);
2082 return pet_expr_free(expr);
2083 }
2084
2085 /* Add a reference identifier to access expression "expr".
2086 * "user" points to an integer that contains the sequence number
2087 * of the next reference.
2088 */
access_add_ref_id(__isl_take pet_expr * expr,void * user)2089 static __isl_give pet_expr *access_add_ref_id(__isl_take pet_expr *expr,
2090 void *user)
2091 {
2092 isl_ctx *ctx;
2093 char name[50];
2094 int *n_ref = user;
2095
2096 expr = pet_expr_cow(expr);
2097 if (!expr)
2098 return expr;
2099 if (expr->type != pet_expr_access)
2100 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2101 "not an access expression", return pet_expr_free(expr));
2102
2103 ctx = pet_expr_get_ctx(expr);
2104 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
2105 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
2106 if (!expr->acc.ref_id)
2107 return pet_expr_free(expr);
2108
2109 return expr;
2110 }
2111
pet_expr_add_ref_ids(__isl_take pet_expr * expr,int * n_ref)2112 __isl_give pet_expr *pet_expr_add_ref_ids(__isl_take pet_expr *expr, int *n_ref)
2113 {
2114 return pet_expr_map_access(expr, &access_add_ref_id, n_ref);
2115 }
2116
2117 /* Reset the user pointer on all parameter and tuple ids in
2118 * the access relations (if any) and the index expression
2119 * of the access expression "expr".
2120 */
access_anonymize(__isl_take pet_expr * expr,void * user)2121 static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr,
2122 void *user)
2123 {
2124 enum pet_expr_access_type type;
2125
2126 expr = pet_expr_cow(expr);
2127 if (!expr)
2128 return expr;
2129 if (expr->type != pet_expr_access)
2130 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2131 "not an access expression", return pet_expr_free(expr));
2132
2133 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
2134 if (!expr->acc.access[type])
2135 continue;
2136 expr->acc.access[type] =
2137 isl_union_map_reset_user(expr->acc.access[type]);
2138 if (!expr->acc.access[type])
2139 break;
2140 }
2141 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
2142 if (type < pet_expr_access_end || !expr->acc.index)
2143 return pet_expr_free(expr);
2144
2145 return expr;
2146 }
2147
pet_expr_anonymize(__isl_take pet_expr * expr)2148 __isl_give pet_expr *pet_expr_anonymize(__isl_take pet_expr *expr)
2149 {
2150 return pet_expr_map_access(expr, &access_anonymize, NULL);
2151 }
2152
2153 /* Data used in access_gist() callback.
2154 */
2155 struct pet_access_gist_data {
2156 isl_set *domain;
2157 isl_union_map *value_bounds;
2158 };
2159
2160 /* Given an expression "expr" of type pet_expr_access, compute
2161 * the gist of the associated access relations (if any) and index expression
2162 * with respect to data->domain and the bounds on the values of the arguments
2163 * of the expression.
2164 *
2165 * The arguments of "expr" have been gisted right before "expr" itself
2166 * is gisted. The gisted arguments may have become equal where before
2167 * they may not have been (obviously) equal. We therefore take
2168 * the opportunity to remove duplicate arguments here.
2169 */
access_gist(__isl_take pet_expr * expr,void * user)2170 static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user)
2171 {
2172 struct pet_access_gist_data *data = user;
2173 isl_set *domain;
2174 isl_union_set *uset;
2175 enum pet_expr_access_type type;
2176
2177 expr = pet_expr_remove_duplicate_args(expr);
2178 expr = pet_expr_cow(expr);
2179 if (!expr)
2180 return expr;
2181 if (expr->type != pet_expr_access)
2182 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2183 "not an access expression", return pet_expr_free(expr));
2184
2185 domain = isl_set_copy(data->domain);
2186 if (expr->n_arg > 0)
2187 domain = pet_value_bounds_apply(domain, expr->n_arg, expr->args,
2188 data->value_bounds);
2189
2190 uset = isl_union_set_from_set(isl_set_copy(domain));
2191 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
2192 if (!expr->acc.access[type])
2193 continue;
2194 expr->acc.access[type] =
2195 isl_union_map_gist_domain(expr->acc.access[type],
2196 isl_union_set_copy(uset));
2197 if (!expr->acc.access[type])
2198 break;
2199 }
2200 isl_union_set_free(uset);
2201 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
2202 if (type < pet_expr_access_end || !expr->acc.index)
2203 return pet_expr_free(expr);
2204
2205 return expr;
2206 }
2207
pet_expr_gist(__isl_take pet_expr * expr,__isl_keep isl_set * context,__isl_keep isl_union_map * value_bounds)2208 __isl_give pet_expr *pet_expr_gist(__isl_take pet_expr *expr,
2209 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2210 {
2211 struct pet_access_gist_data data = { context, value_bounds };
2212
2213 return pet_expr_map_access(expr, &access_gist, &data);
2214 }
2215
2216 /* Mark "expr" as a read dependening on "read".
2217 */
pet_expr_access_set_read(__isl_take pet_expr * expr,int read)2218 __isl_give pet_expr *pet_expr_access_set_read(__isl_take pet_expr *expr,
2219 int read)
2220 {
2221 if (!expr)
2222 return pet_expr_free(expr);
2223 if (expr->type != pet_expr_access)
2224 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2225 "not an access expression", return pet_expr_free(expr));
2226 if (expr->acc.read == read)
2227 return expr;
2228 expr = pet_expr_cow(expr);
2229 if (!expr)
2230 return NULL;
2231 expr->acc.read = read;
2232
2233 return expr;
2234 }
2235
2236 /* Mark "expr" as a write dependening on "write".
2237 */
pet_expr_access_set_write(__isl_take pet_expr * expr,int write)2238 __isl_give pet_expr *pet_expr_access_set_write(__isl_take pet_expr *expr,
2239 int write)
2240 {
2241 if (!expr)
2242 return pet_expr_free(expr);
2243 if (expr->type != pet_expr_access)
2244 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2245 "not an access expression", return pet_expr_free(expr));
2246 if (expr->acc.write == write)
2247 return expr;
2248 expr = pet_expr_cow(expr);
2249 if (!expr)
2250 return NULL;
2251 expr->acc.write = write;
2252
2253 return expr;
2254 }
2255
2256 /* Mark "expr" as a kill dependening on "kill".
2257 */
pet_expr_access_set_kill(__isl_take pet_expr * expr,int kill)2258 __isl_give pet_expr *pet_expr_access_set_kill(__isl_take pet_expr *expr,
2259 int kill)
2260 {
2261 if (!expr)
2262 return pet_expr_free(expr);
2263 if (expr->type != pet_expr_access)
2264 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2265 "not an access expression", return pet_expr_free(expr));
2266 if (expr->acc.kill == kill)
2267 return expr;
2268 expr = pet_expr_cow(expr);
2269 if (!expr)
2270 return NULL;
2271 expr->acc.kill = kill;
2272
2273 return expr;
2274 }
2275
2276 /* Map the access type "type" to the corresponding location
2277 * in the access array.
2278 * In particular, the access relation of type pet_expr_access_killed is
2279 * stored in the element at position pet_expr_access_fake_killed.
2280 */
internalize_type(enum pet_expr_access_type type)2281 static enum pet_expr_access_type internalize_type(
2282 enum pet_expr_access_type type)
2283 {
2284 if (type == pet_expr_access_killed)
2285 return pet_expr_access_fake_killed;
2286 return type;
2287 }
2288
2289 /* Replace the access relation of the given "type" of "expr" by "access".
2290 * If the access relation is non-empty and the type is a read or a write,
2291 * then also mark the access expression itself as a read or a write.
2292 */
pet_expr_access_set_access(__isl_take pet_expr * expr,enum pet_expr_access_type type,__isl_take isl_union_map * access)2293 __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr,
2294 enum pet_expr_access_type type, __isl_take isl_union_map *access)
2295 {
2296 int empty;
2297
2298 expr = pet_expr_cow(expr);
2299 if (!expr || !access)
2300 goto error;
2301 if (expr->type != pet_expr_access)
2302 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2303 "not an access expression", goto error);
2304 type = internalize_type(type);
2305 isl_union_map_free(expr->acc.access[type]);
2306 expr->acc.access[type] = access;
2307
2308 if (expr->acc.kill)
2309 return expr;
2310
2311 empty = isl_union_map_is_empty(access);
2312 if (empty < 0)
2313 return pet_expr_free(expr);
2314 if (empty)
2315 return expr;
2316
2317 if (type == pet_expr_access_may_read)
2318 expr = pet_expr_access_set_read(expr, 1);
2319 else
2320 expr = pet_expr_access_set_write(expr, 1);
2321
2322 return expr;
2323 error:
2324 isl_union_map_free(access);
2325 pet_expr_free(expr);
2326 return NULL;
2327 }
2328
2329 /* Replace the index expression of "expr" by "index" and
2330 * set the array depth accordingly.
2331 */
pet_expr_access_set_index(__isl_take pet_expr * expr,__isl_take isl_multi_pw_aff * index)2332 __isl_give pet_expr *pet_expr_access_set_index(__isl_take pet_expr *expr,
2333 __isl_take isl_multi_pw_aff *index)
2334 {
2335 expr = pet_expr_cow(expr);
2336 if (!expr || !index)
2337 goto error;
2338 if (expr->type != pet_expr_access)
2339 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2340 "not an access expression", goto error);
2341 isl_multi_pw_aff_free(expr->acc.index);
2342 expr->acc.index = index;
2343 expr->acc.depth = isl_multi_pw_aff_dim(index, isl_dim_out);
2344
2345 return expr;
2346 error:
2347 isl_multi_pw_aff_free(index);
2348 pet_expr_free(expr);
2349 return NULL;
2350 }
2351
2352 /* Return the reference identifier of access expression "expr".
2353 */
pet_expr_access_get_ref_id(__isl_keep pet_expr * expr)2354 __isl_give isl_id *pet_expr_access_get_ref_id(__isl_keep pet_expr *expr)
2355 {
2356 if (!expr)
2357 return NULL;
2358 if (expr->type != pet_expr_access)
2359 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2360 "not an access expression", return NULL);
2361
2362 return isl_id_copy(expr->acc.ref_id);
2363 }
2364
2365 /* Replace the reference identifier of access expression "expr" by "ref_id".
2366 */
pet_expr_access_set_ref_id(__isl_take pet_expr * expr,__isl_take isl_id * ref_id)2367 __isl_give pet_expr *pet_expr_access_set_ref_id(__isl_take pet_expr *expr,
2368 __isl_take isl_id *ref_id)
2369 {
2370 expr = pet_expr_cow(expr);
2371 if (!expr || !ref_id)
2372 goto error;
2373 if (expr->type != pet_expr_access)
2374 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2375 "not an access expression", goto error);
2376 isl_id_free(expr->acc.ref_id);
2377 expr->acc.ref_id = ref_id;
2378
2379 return expr;
2380 error:
2381 isl_id_free(ref_id);
2382 pet_expr_free(expr);
2383 return NULL;
2384 }
2385
2386 /* Tag the access relation "access" with "id".
2387 * That is, insert the id as the range of a wrapped relation
2388 * in the domain of "access".
2389 *
2390 * If "access" is of the form
2391 *
2392 * D[i] -> A[a]
2393 *
2394 * then the result is of the form
2395 *
2396 * [D[i] -> id[]] -> A[a]
2397 */
pet_expr_tag_access(__isl_keep pet_expr * expr,__isl_take isl_union_map * access)2398 __isl_give isl_union_map *pet_expr_tag_access(__isl_keep pet_expr *expr,
2399 __isl_take isl_union_map *access)
2400 {
2401 isl_space *space;
2402 isl_multi_aff *add_tag;
2403 isl_id *id;
2404
2405 if (expr->type != pet_expr_access)
2406 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2407 "not an access expression",
2408 return isl_union_map_free(access));
2409
2410 id = isl_id_copy(expr->acc.ref_id);
2411 space = pet_expr_access_get_domain_space(expr);
2412 space = isl_space_from_domain(space);
2413 space = isl_space_set_tuple_id(space, isl_dim_out, id);
2414 add_tag = isl_multi_aff_domain_map(space);
2415 access = isl_union_map_preimage_domain_multi_aff(access, add_tag);
2416
2417 return access;
2418 }
2419
2420 /* Return the access relation of the given "type" associated to "expr"
2421 * that maps pairs of domain iterations and argument values
2422 * to the corresponding accessed data elements.
2423 *
2424 * If the requested access relation is explicitly available,
2425 * then return a copy. Otherwise, check if it is irrelevant for
2426 * the access expression and return an empty relation if this is the case.
2427 * Otherwise, introduce the requested access relation in "expr" and
2428 * return a copy.
2429 */
pet_expr_access_get_dependent_access(__isl_keep pet_expr * expr,enum pet_expr_access_type type)2430 __isl_give isl_union_map *pet_expr_access_get_dependent_access(
2431 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2432 {
2433 isl_union_map *access;
2434 int empty;
2435
2436 if (!expr)
2437 return NULL;
2438 if (expr->type != pet_expr_access)
2439 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2440 "not an access expression", return NULL);
2441
2442 type = internalize_type(type);
2443 if (expr->acc.access[type])
2444 return isl_union_map_copy(expr->acc.access[type]);
2445
2446 if (type == pet_expr_access_may_read)
2447 empty = !expr->acc.read;
2448 else
2449 empty = !expr->acc.write;
2450
2451 if (!empty) {
2452 expr = pet_expr_copy(expr);
2453 expr = introduce_access_relations(expr);
2454 if (!expr)
2455 return NULL;
2456 access = isl_union_map_copy(expr->acc.access[type]);
2457 pet_expr_free(expr);
2458
2459 return access;
2460 }
2461
2462 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr));
2463 }
2464
2465 /* Return the may read access relation associated to "expr"
2466 * that maps pairs of domain iterations and argument values
2467 * to the corresponding accessed data elements.
2468 */
pet_expr_access_get_dependent_may_read(__isl_keep pet_expr * expr)2469 __isl_give isl_union_map *pet_expr_access_get_dependent_may_read(
2470 __isl_keep pet_expr *expr)
2471 {
2472 return pet_expr_access_get_dependent_access(expr,
2473 pet_expr_access_may_read);
2474 }
2475
2476 /* Return the may write access relation associated to "expr"
2477 * that maps pairs of domain iterations and argument values
2478 * to the corresponding accessed data elements.
2479 */
pet_expr_access_get_dependent_may_write(__isl_keep pet_expr * expr)2480 __isl_give isl_union_map *pet_expr_access_get_dependent_may_write(
2481 __isl_keep pet_expr *expr)
2482 {
2483 return pet_expr_access_get_dependent_access(expr,
2484 pet_expr_access_may_write);
2485 }
2486
2487 /* Return the must write access relation associated to "expr"
2488 * that maps pairs of domain iterations and argument values
2489 * to the corresponding accessed data elements.
2490 */
pet_expr_access_get_dependent_must_write(__isl_keep pet_expr * expr)2491 __isl_give isl_union_map *pet_expr_access_get_dependent_must_write(
2492 __isl_keep pet_expr *expr)
2493 {
2494 return pet_expr_access_get_dependent_access(expr,
2495 pet_expr_access_must_write);
2496 }
2497
2498 /* Return the relation of the given "type" mapping domain iterations
2499 * to the accessed data elements.
2500 * In particular, take the access relation and, in case of may_read
2501 * or may_write, project out the values of the arguments, if any.
2502 * In case of must_write, return the empty relation if there are
2503 * any arguments.
2504 */
pet_expr_access_get_access(__isl_keep pet_expr * expr,enum pet_expr_access_type type)2505 __isl_give isl_union_map *pet_expr_access_get_access(__isl_keep pet_expr *expr,
2506 enum pet_expr_access_type type)
2507 {
2508 isl_union_map *access;
2509 isl_space *space;
2510 isl_map *map;
2511
2512 if (!expr)
2513 return NULL;
2514 if (expr->type != pet_expr_access)
2515 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2516 "not an access expression", return NULL);
2517
2518 if (expr->n_arg != 0 && type == pet_expr_access_must_write) {
2519 space = pet_expr_access_get_parameter_space(expr);
2520 return isl_union_map_empty(space);
2521 }
2522
2523 access = pet_expr_access_get_dependent_access(expr, type);
2524 if (expr->n_arg == 0)
2525 return access;
2526
2527 space = isl_multi_pw_aff_get_space(expr->acc.index);
2528 space = isl_space_domain(space);
2529 map = isl_map_universe(isl_space_unwrap(space));
2530 map = isl_map_domain_map(map);
2531 access = isl_union_map_apply_domain(access,
2532 isl_union_map_from_map(map));
2533
2534 return access;
2535 }
2536
2537 /* Return the relation mapping domain iterations to all possibly
2538 * read data elements.
2539 */
pet_expr_access_get_may_read(__isl_keep pet_expr * expr)2540 __isl_give isl_union_map *pet_expr_access_get_may_read(
2541 __isl_keep pet_expr *expr)
2542 {
2543 return pet_expr_access_get_access(expr, pet_expr_access_may_read);
2544 }
2545
2546 /* Return the relation mapping domain iterations to all possibly
2547 * written data elements.
2548 */
pet_expr_access_get_may_write(__isl_keep pet_expr * expr)2549 __isl_give isl_union_map *pet_expr_access_get_may_write(
2550 __isl_keep pet_expr *expr)
2551 {
2552 return pet_expr_access_get_access(expr, pet_expr_access_may_write);
2553 }
2554
2555 /* Return a relation mapping domain iterations to definitely
2556 * written data elements, assuming the statement containing
2557 * the expression is executed.
2558 */
pet_expr_access_get_must_write(__isl_keep pet_expr * expr)2559 __isl_give isl_union_map *pet_expr_access_get_must_write(
2560 __isl_keep pet_expr *expr)
2561 {
2562 return pet_expr_access_get_access(expr, pet_expr_access_must_write);
2563 }
2564
2565 /* Return the relation of the given "type" mapping domain iterations to
2566 * accessed data elements, with its domain tagged with the reference
2567 * identifier.
2568 */
pet_expr_access_get_tagged_access(__isl_keep pet_expr * expr,enum pet_expr_access_type type)2569 static __isl_give isl_union_map *pet_expr_access_get_tagged_access(
2570 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2571 {
2572 isl_union_map *access;
2573
2574 if (!expr)
2575 return NULL;
2576
2577 access = pet_expr_access_get_access(expr, type);
2578 access = pet_expr_tag_access(expr, access);
2579
2580 return access;
2581 }
2582
2583 /* Return the relation mapping domain iterations to all possibly
2584 * read data elements, with its domain tagged with the reference
2585 * identifier.
2586 */
pet_expr_access_get_tagged_may_read(__isl_keep pet_expr * expr)2587 __isl_give isl_union_map *pet_expr_access_get_tagged_may_read(
2588 __isl_keep pet_expr *expr)
2589 {
2590 return pet_expr_access_get_tagged_access(expr,
2591 pet_expr_access_may_read);
2592 }
2593
2594 /* Return the relation mapping domain iterations to all possibly
2595 * written data elements, with its domain tagged with the reference
2596 * identifier.
2597 */
pet_expr_access_get_tagged_may_write(__isl_keep pet_expr * expr)2598 __isl_give isl_union_map *pet_expr_access_get_tagged_may_write(
2599 __isl_keep pet_expr *expr)
2600 {
2601 return pet_expr_access_get_tagged_access(expr,
2602 pet_expr_access_may_write);
2603 }
2604
2605 /* Return the operation type of operation expression "expr".
2606 */
pet_expr_op_get_type(__isl_keep pet_expr * expr)2607 enum pet_op_type pet_expr_op_get_type(__isl_keep pet_expr *expr)
2608 {
2609 if (!expr)
2610 return pet_op_last;
2611 if (expr->type != pet_expr_op)
2612 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2613 "not an operation expression", return pet_op_last);
2614
2615 return expr->op;
2616 }
2617
2618 /* Replace the operation type of operation expression "expr" by "type".
2619 */
pet_expr_op_set_type(__isl_take pet_expr * expr,enum pet_op_type type)2620 __isl_give pet_expr *pet_expr_op_set_type(__isl_take pet_expr *expr,
2621 enum pet_op_type type)
2622 {
2623 if (!expr)
2624 return pet_expr_free(expr);
2625 if (expr->type != pet_expr_op)
2626 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2627 "not an operation expression",
2628 return pet_expr_free(expr));
2629 if (expr->op == type)
2630 return expr;
2631 expr = pet_expr_cow(expr);
2632 if (!expr)
2633 return NULL;
2634 expr->op = type;
2635
2636 return expr;
2637 }
2638
2639 /* Return the name of the function called by "expr".
2640 */
pet_expr_call_get_name(__isl_keep pet_expr * expr)2641 __isl_keep const char *pet_expr_call_get_name(__isl_keep pet_expr *expr)
2642 {
2643 if (!expr)
2644 return NULL;
2645 if (expr->type != pet_expr_call)
2646 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2647 "not a call expression", return NULL);
2648 return expr->c.name;
2649 }
2650
2651 /* Replace the name of the function called by "expr" by "name".
2652 */
pet_expr_call_set_name(__isl_take pet_expr * expr,__isl_keep const char * name)2653 __isl_give pet_expr *pet_expr_call_set_name(__isl_take pet_expr *expr,
2654 __isl_keep const char *name)
2655 {
2656 expr = pet_expr_cow(expr);
2657 if (!expr || !name)
2658 return pet_expr_free(expr);
2659 if (expr->type != pet_expr_call)
2660 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2661 "not a call expression", return pet_expr_free(expr));
2662 free(expr->c.name);
2663 expr->c.name = strdup(name);
2664 if (!expr->c.name)
2665 return pet_expr_free(expr);
2666 return expr;
2667 }
2668
2669 /* Does the call expression "expr" have an associated function summary?
2670 */
pet_expr_call_has_summary(__isl_keep pet_expr * expr)2671 int pet_expr_call_has_summary(__isl_keep pet_expr *expr)
2672 {
2673 if (!expr)
2674 return -1;
2675 if (expr->type != pet_expr_call)
2676 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2677 "not a call expression", return -1);
2678
2679 return expr->c.summary != NULL;
2680 }
2681
2682 /* Return a copy of the function summary associated to
2683 * the call expression "expr".
2684 */
pet_expr_call_get_summary(__isl_keep pet_expr * expr)2685 __isl_give pet_function_summary *pet_expr_call_get_summary(
2686 __isl_keep pet_expr *expr)
2687 {
2688 if (!expr)
2689 return NULL;
2690 if (expr->type != pet_expr_call)
2691 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2692 "not a call expression", return NULL);
2693
2694 return pet_function_summary_copy(expr->c.summary);
2695 }
2696
2697 /* Replace the function summary associated to the call expression "expr"
2698 * by "summary".
2699 */
pet_expr_call_set_summary(__isl_take pet_expr * expr,__isl_take pet_function_summary * summary)2700 __isl_give pet_expr *pet_expr_call_set_summary(__isl_take pet_expr *expr,
2701 __isl_take pet_function_summary *summary)
2702 {
2703 expr = pet_expr_cow(expr);
2704 if (!expr || !summary)
2705 goto error;
2706 if (expr->type != pet_expr_call)
2707 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2708 "not a call expression", goto error);
2709 pet_function_summary_free(expr->c.summary);
2710 expr->c.summary = summary;
2711 return expr;
2712 error:
2713 pet_function_summary_free(summary);
2714 return pet_expr_free(expr);
2715 }
2716
2717 /* Replace the type of the cast performed by "expr" by "name".
2718 */
pet_expr_cast_set_type_name(__isl_take pet_expr * expr,__isl_keep const char * name)2719 __isl_give pet_expr *pet_expr_cast_set_type_name(__isl_take pet_expr *expr,
2720 __isl_keep const char *name)
2721 {
2722 expr = pet_expr_cow(expr);
2723 if (!expr || !name)
2724 return pet_expr_free(expr);
2725 if (expr->type != pet_expr_cast)
2726 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2727 "not a cast expression", return pet_expr_free(expr));
2728 free(expr->type_name);
2729 expr->type_name = strdup(name);
2730 if (!expr->type_name)
2731 return pet_expr_free(expr);
2732 return expr;
2733 }
2734
2735 /* Return the value of the integer represented by "expr".
2736 */
pet_expr_int_get_val(__isl_keep pet_expr * expr)2737 __isl_give isl_val *pet_expr_int_get_val(__isl_keep pet_expr *expr)
2738 {
2739 if (!expr)
2740 return NULL;
2741 if (expr->type != pet_expr_int)
2742 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2743 "not an int expression", return NULL);
2744
2745 return isl_val_copy(expr->i);
2746 }
2747
2748 /* Replace the value of the integer represented by "expr" by "v".
2749 */
pet_expr_int_set_val(__isl_take pet_expr * expr,__isl_take isl_val * v)2750 __isl_give pet_expr *pet_expr_int_set_val(__isl_take pet_expr *expr,
2751 __isl_take isl_val *v)
2752 {
2753 expr = pet_expr_cow(expr);
2754 if (!expr || !v)
2755 goto error;
2756 if (expr->type != pet_expr_int)
2757 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2758 "not an int expression", goto error);
2759 isl_val_free(expr->i);
2760 expr->i = v;
2761
2762 return expr;
2763 error:
2764 isl_val_free(v);
2765 pet_expr_free(expr);
2766 return NULL;
2767 }
2768
2769 /* Replace the value and string representation of the double
2770 * represented by "expr" by "d" and "s".
2771 */
pet_expr_double_set(__isl_take pet_expr * expr,double d,__isl_keep const char * s)2772 __isl_give pet_expr *pet_expr_double_set(__isl_take pet_expr *expr,
2773 double d, __isl_keep const char *s)
2774 {
2775 expr = pet_expr_cow(expr);
2776 if (!expr || !s)
2777 return pet_expr_free(expr);
2778 if (expr->type != pet_expr_double)
2779 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2780 "not a double expression", return pet_expr_free(expr));
2781 expr->d.val = d;
2782 free(expr->d.s);
2783 expr->d.s = strdup(s);
2784 if (!expr->d.s)
2785 return pet_expr_free(expr);
2786 return expr;
2787 }
2788
2789 /* Return a string representation of the double expression "expr".
2790 */
pet_expr_double_get_str(__isl_keep pet_expr * expr)2791 __isl_give char *pet_expr_double_get_str(__isl_keep pet_expr *expr)
2792 {
2793 if (!expr)
2794 return NULL;
2795 if (expr->type != pet_expr_double)
2796 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2797 "not a double expression", return NULL);
2798 return strdup(expr->d.s);
2799 }
2800
2801 /* Return a piecewise affine expression defined on the specified domain
2802 * that represents NaN.
2803 */
non_affine(__isl_take isl_space * space)2804 static __isl_give isl_pw_aff *non_affine(__isl_take isl_space *space)
2805 {
2806 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space));
2807 }
2808
2809 /* This function is called when we come across an access that is
2810 * nested in what is supposed to be an affine expression.
2811 * "pc" is the context in which the affine expression is created.
2812 * If nesting is allowed in "pc", we return an affine expression that is
2813 * equal to a new parameter corresponding to this nested access.
2814 * Otherwise, we return NaN.
2815 *
2816 * Note that we currently don't allow nested accesses themselves
2817 * to contain any nested accesses, so we check if "expr" itself
2818 * involves any nested accesses (either explicitly as arguments
2819 * or implicitly through parameters) and return NaN if it does.
2820 *
2821 * The new parameter is resolved in resolve_nested.
2822 */
nested_access(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)2823 static __isl_give isl_pw_aff *nested_access(__isl_keep pet_expr *expr,
2824 __isl_keep pet_context *pc)
2825 {
2826 isl_ctx *ctx;
2827 isl_id *id;
2828 isl_space *space;
2829 isl_local_space *ls;
2830 isl_aff *aff;
2831 int nested;
2832
2833 if (!expr || !pc)
2834 return NULL;
2835 if (!pet_context_allow_nesting(pc))
2836 return non_affine(pet_context_get_space(pc));
2837
2838 if (pet_expr_get_type(expr) != pet_expr_access)
2839 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2840 "not an access expression", return NULL);
2841
2842 if (expr->n_arg > 0)
2843 return non_affine(pet_context_get_space(pc));
2844
2845 space = pet_expr_access_get_parameter_space(expr);
2846 nested = pet_nested_any_in_space(space);
2847 isl_space_free(space);
2848 if (nested)
2849 return non_affine(pet_context_get_space(pc));
2850
2851 ctx = pet_expr_get_ctx(expr);
2852 id = pet_nested_pet_expr(pet_expr_copy(expr));
2853 space = pet_context_get_space(pc);
2854 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2855
2856 space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
2857 ls = isl_local_space_from_space(space);
2858 aff = isl_aff_var_on_domain(ls, isl_dim_param, 0);
2859
2860 return isl_pw_aff_from_aff(aff);
2861 }
2862
2863 /* Extract an affine expression from the access pet_expr "expr".
2864 * "pc" is the context in which the affine expression is created.
2865 *
2866 * If "expr" is actually an affine expression rather than
2867 * a real access, then we return that expression.
2868 * Otherwise, we require that "expr" is of an integral type.
2869 * If not, we return NaN.
2870 *
2871 * If the variable has been assigned a known affine expression,
2872 * then we return that expression.
2873 *
2874 * Otherwise, we return an expression that is equal to a parameter
2875 * representing "expr" (if "allow_nested" is set).
2876 */
extract_affine_from_access(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)2877 static __isl_give isl_pw_aff *extract_affine_from_access(
2878 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2879 {
2880 isl_id *id;
2881
2882 if (pet_expr_is_affine(expr))
2883 return pet_expr_get_affine(expr);
2884
2885 if (pet_expr_get_type_size(expr) == 0)
2886 return non_affine(pet_context_get_space(pc));
2887
2888 if (!pet_expr_is_scalar_access(expr))
2889 return nested_access(expr, pc);
2890
2891 id = pet_expr_access_get_id(expr);
2892 if (pet_context_is_assigned(pc, id))
2893 return pet_context_get_value(pc, id);
2894
2895 isl_id_free(id);
2896 return nested_access(expr, pc);
2897 }
2898
2899 /* Construct an affine expression from the integer constant "expr".
2900 * "pc" is the context in which the affine expression is created.
2901 */
extract_affine_from_int(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)2902 static __isl_give isl_pw_aff *extract_affine_from_int(__isl_keep pet_expr *expr,
2903 __isl_keep pet_context *pc)
2904 {
2905 isl_local_space *ls;
2906 isl_aff *aff;
2907
2908 if (!expr)
2909 return NULL;
2910
2911 ls = isl_local_space_from_space(pet_context_get_space(pc));
2912 aff = isl_aff_val_on_domain(ls, pet_expr_int_get_val(expr));
2913
2914 return isl_pw_aff_from_aff(aff);
2915 }
2916
2917 /* Extract an affine expression from an addition or subtraction operation.
2918 * Return NaN if we are unable to extract an affine expression.
2919 *
2920 * "pc" is the context in which the affine expression is created.
2921 */
extract_affine_add_sub(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)2922 static __isl_give isl_pw_aff *extract_affine_add_sub(__isl_keep pet_expr *expr,
2923 __isl_keep pet_context *pc)
2924 {
2925 isl_pw_aff *lhs;
2926 isl_pw_aff *rhs;
2927
2928 if (!expr)
2929 return NULL;
2930 if (expr->n_arg != 2)
2931 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2932 "expecting two arguments", return NULL);
2933
2934 lhs = pet_expr_extract_affine(expr->args[0], pc);
2935 rhs = pet_expr_extract_affine(expr->args[1], pc);
2936
2937 switch (pet_expr_op_get_type(expr)) {
2938 case pet_op_add:
2939 return isl_pw_aff_add(lhs, rhs);
2940 case pet_op_sub:
2941 return isl_pw_aff_sub(lhs, rhs);
2942 default:
2943 isl_pw_aff_free(lhs);
2944 isl_pw_aff_free(rhs);
2945 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2946 "not an addition or subtraction operation",
2947 return NULL);
2948 }
2949
2950 }
2951
2952 /* Extract an affine expression from an integer division or a modulo operation.
2953 * Return NaN if we are unable to extract an affine expression.
2954 *
2955 * "pc" is the context in which the affine expression is created.
2956 *
2957 * In particular, if "expr" is lhs/rhs, then return
2958 *
2959 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2960 *
2961 * If "expr" is lhs%rhs, then return
2962 *
2963 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2964 *
2965 * If the second argument (rhs) is not a (positive) integer constant,
2966 * then we fail to extract an affine expression.
2967 *
2968 * We simplify the result in the context of the domain of "pc" in case
2969 * this domain implies that lhs >= 0 (or < 0).
2970 */
extract_affine_div_mod(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)2971 static __isl_give isl_pw_aff *extract_affine_div_mod(__isl_keep pet_expr *expr,
2972 __isl_keep pet_context *pc)
2973 {
2974 int is_cst;
2975 isl_pw_aff *lhs;
2976 isl_pw_aff *rhs;
2977 isl_pw_aff *res;
2978
2979 if (!expr)
2980 return NULL;
2981 if (expr->n_arg != 2)
2982 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2983 "expecting two arguments", return NULL);
2984
2985 rhs = pet_expr_extract_affine(expr->args[1], pc);
2986
2987 is_cst = isl_pw_aff_is_cst(rhs);
2988 if (is_cst < 0 || !is_cst) {
2989 isl_pw_aff_free(rhs);
2990 return non_affine(pet_context_get_space(pc));
2991 }
2992
2993 lhs = pet_expr_extract_affine(expr->args[0], pc);
2994
2995 switch (pet_expr_op_get_type(expr)) {
2996 case pet_op_div:
2997 res = isl_pw_aff_tdiv_q(lhs, rhs);
2998 break;
2999 case pet_op_mod:
3000 res = isl_pw_aff_tdiv_r(lhs, rhs);
3001 break;
3002 default:
3003 isl_pw_aff_free(lhs);
3004 isl_pw_aff_free(rhs);
3005 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
3006 "not a div or mod operator", return NULL);
3007 }
3008
3009 return isl_pw_aff_gist(res, pet_context_get_gist_domain(pc));
3010 }
3011
3012 /* Extract an affine expression from a multiplication operation.
3013 * Return NaN if we are unable to extract an affine expression.
3014 * In particular, if neither of the arguments is a (piecewise) constant
3015 * then we return NaN.
3016 *
3017 * "pc" is the context in which the affine expression is created.
3018 */
extract_affine_mul(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3019 static __isl_give isl_pw_aff *extract_affine_mul(__isl_keep pet_expr *expr,
3020 __isl_keep pet_context *pc)
3021 {
3022 int lhs_cst, rhs_cst;
3023 isl_pw_aff *lhs;
3024 isl_pw_aff *rhs;
3025
3026 if (!expr)
3027 return NULL;
3028 if (expr->n_arg != 2)
3029 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3030 "expecting two arguments", return NULL);
3031
3032 lhs = pet_expr_extract_affine(expr->args[0], pc);
3033 rhs = pet_expr_extract_affine(expr->args[1], pc);
3034
3035 lhs_cst = isl_pw_aff_is_cst(lhs);
3036 rhs_cst = isl_pw_aff_is_cst(rhs);
3037 if (lhs_cst >= 0 && rhs_cst >= 0 && (lhs_cst || rhs_cst))
3038 return isl_pw_aff_mul(lhs, rhs);
3039
3040 isl_pw_aff_free(lhs);
3041 isl_pw_aff_free(rhs);
3042
3043 if (lhs_cst < 0 || rhs_cst < 0)
3044 return NULL;
3045
3046 return non_affine(pet_context_get_space(pc));
3047 }
3048
3049 /* Extract an affine expression from a negation operation.
3050 * Return NaN if we are unable to extract an affine expression.
3051 *
3052 * "pc" is the context in which the affine expression is created.
3053 */
extract_affine_neg(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3054 static __isl_give isl_pw_aff *extract_affine_neg(__isl_keep pet_expr *expr,
3055 __isl_keep pet_context *pc)
3056 {
3057 isl_pw_aff *res;
3058
3059 if (!expr)
3060 return NULL;
3061 if (expr->n_arg != 1)
3062 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3063 "expecting one argument", return NULL);
3064
3065 res = pet_expr_extract_affine(expr->args[0], pc);
3066 return isl_pw_aff_neg(res);
3067 }
3068
3069 /* Extract an affine expression from a conditional operation.
3070 * Return NaN if we are unable to extract an affine expression.
3071 *
3072 * "pc" is the context in which the affine expression is created.
3073 */
extract_affine_cond(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3074 static __isl_give isl_pw_aff *extract_affine_cond(__isl_keep pet_expr *expr,
3075 __isl_keep pet_context *pc)
3076 {
3077 isl_pw_aff *cond, *lhs, *rhs;
3078
3079 if (!expr)
3080 return NULL;
3081 if (expr->n_arg != 3)
3082 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3083 "expecting three arguments", return NULL);
3084
3085 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
3086 lhs = pet_expr_extract_affine(expr->args[1], pc);
3087 rhs = pet_expr_extract_affine(expr->args[2], pc);
3088
3089 return isl_pw_aff_cond(cond, lhs, rhs);
3090 }
3091
3092 /* Limit the domain of "pwaff" to those elements where the function
3093 * value satisfies
3094 *
3095 * 2^{width-1} <= pwaff < 2^{width-1}
3096 */
avoid_overflow(__isl_take isl_pw_aff * pwaff,unsigned width)3097 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
3098 unsigned width)
3099 {
3100 isl_ctx *ctx;
3101 isl_val *v;
3102 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
3103 isl_local_space *ls = isl_local_space_from_space(space);
3104 isl_aff *bound;
3105 isl_set *dom;
3106 isl_pw_aff *b;
3107
3108 ctx = isl_pw_aff_get_ctx(pwaff);
3109 v = isl_val_int_from_ui(ctx, width - 1);
3110 v = isl_val_2exp(v);
3111
3112 bound = isl_aff_zero_on_domain(ls);
3113 bound = isl_aff_add_constant_val(bound, v);
3114 b = isl_pw_aff_from_aff(bound);
3115
3116 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
3117 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
3118
3119 b = isl_pw_aff_neg(b);
3120 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
3121 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
3122
3123 return pwaff;
3124 }
3125
3126 /* Handle potential overflows on signed computations.
3127 *
3128 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
3129 * then we adjust the domain of "pa" to avoid overflows.
3130 */
signed_overflow(__isl_take isl_pw_aff * pa,unsigned width)3131 static __isl_give isl_pw_aff *signed_overflow(__isl_take isl_pw_aff *pa,
3132 unsigned width)
3133 {
3134 isl_ctx *ctx;
3135 struct pet_options *options;
3136
3137 if (!pa)
3138 return NULL;
3139
3140 ctx = isl_pw_aff_get_ctx(pa);
3141 options = isl_ctx_peek_pet_options(ctx);
3142 if (!options || options->signed_overflow == PET_OVERFLOW_AVOID)
3143 pa = avoid_overflow(pa, width);
3144
3145 return pa;
3146 }
3147
3148 /* Extract an affine expression from some an operation.
3149 * Return NaN if we are unable to extract an affine expression.
3150 * If the result of a binary (non boolean) operation is unsigned,
3151 * then we wrap it based on the size of the type. If the result is signed,
3152 * then we ensure that no overflow occurs.
3153 *
3154 * "pc" is the context in which the affine expression is created.
3155 */
extract_affine_from_op(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3156 static __isl_give isl_pw_aff *extract_affine_from_op(__isl_keep pet_expr *expr,
3157 __isl_keep pet_context *pc)
3158 {
3159 isl_pw_aff *res;
3160 int type_size;
3161
3162 switch (pet_expr_op_get_type(expr)) {
3163 case pet_op_add:
3164 case pet_op_sub:
3165 res = extract_affine_add_sub(expr, pc);
3166 break;
3167 case pet_op_div:
3168 case pet_op_mod:
3169 res = extract_affine_div_mod(expr, pc);
3170 break;
3171 case pet_op_mul:
3172 res = extract_affine_mul(expr, pc);
3173 break;
3174 case pet_op_minus:
3175 return extract_affine_neg(expr, pc);
3176 case pet_op_cond:
3177 return extract_affine_cond(expr, pc);
3178 case pet_op_eq:
3179 case pet_op_ne:
3180 case pet_op_le:
3181 case pet_op_ge:
3182 case pet_op_lt:
3183 case pet_op_gt:
3184 case pet_op_land:
3185 case pet_op_lor:
3186 case pet_op_lnot:
3187 return pet_expr_extract_affine_condition(expr, pc);
3188 default:
3189 return non_affine(pet_context_get_space(pc));
3190 }
3191
3192 if (!res)
3193 return NULL;
3194 if (isl_pw_aff_involves_nan(res)) {
3195 isl_space *space = isl_pw_aff_get_domain_space(res);
3196 isl_pw_aff_free(res);
3197 return non_affine(space);
3198 }
3199
3200 type_size = pet_expr_get_type_size(expr);
3201 if (type_size > 0)
3202 res = pet_wrap_pw_aff(res, type_size);
3203 else
3204 res = signed_overflow(res, -type_size);
3205
3206 return res;
3207 }
3208
3209 /* Internal data structure for affine builtin function declarations.
3210 *
3211 * "pencil" is set if the builtin is pencil specific.
3212 * "n_args" is the number of arguments the function takes.
3213 * "name" is the function name.
3214 */
3215 struct affine_builtin_decl {
3216 int pencil;
3217 int n_args;
3218 const char *name;
3219 };
3220
3221 static struct affine_builtin_decl affine_builtins[] = {
3222 { 0, 2, "min" },
3223 { 1, 2, "imin" },
3224 { 1, 2, "umin" },
3225 { 0, 2, "max" },
3226 { 1, 2, "imax" },
3227 { 1, 2, "umax" },
3228 { 0, 2, "intMod" },
3229 { 0, 2, "intFloor" },
3230 { 0, 2, "intCeil" },
3231 { 0, 2, "floord" },
3232 { 0, 2, "ceild" }
3233 };
3234
3235 /* List of min and max builtin functions.
3236 */
3237 static const char *min_max_builtins[] = {
3238 "min", "imin", "umin",
3239 "max", "imax", "umax"
3240 };
3241
3242 /* Is a function call to "name" with "n_args" arguments a call to a
3243 * builtin function for which we can construct an affine expression?
3244 * pencil specific builtins are only recognized if "pencil" is set.
3245 */
is_affine_builtin(int pencil,int n_args,const char * name)3246 static int is_affine_builtin(int pencil, int n_args, const char *name)
3247 {
3248 int i;
3249
3250 for (i = 0; i < ARRAY_SIZE(affine_builtins); ++i) {
3251 struct affine_builtin_decl *decl = &affine_builtins[i];
3252
3253 if (decl->pencil && !pencil)
3254 continue;
3255 if (decl->n_args == n_args && !strcmp(decl->name, name))
3256 return 1;
3257 }
3258
3259 return 0;
3260 }
3261
3262 /* Is function "name" a known min or max builtin function?
3263 */
is_min_or_max_builtin(const char * name)3264 static int is_min_or_max_builtin(const char *name)
3265 {
3266 int i;
3267
3268 for (i = 0; i < ARRAY_SIZE(min_max_builtins); ++i)
3269 if (!strcmp(min_max_builtins[i], name))
3270 return 1;
3271
3272 return 0;
3273 }
3274
3275 /* Extract an affine expression from some special function calls.
3276 * Return NaN if we are unable to extract an affine expression.
3277 * In particular, we handle "min", "max", "ceild", "floord",
3278 * "intMod", "intFloor" and "intCeil".
3279 * In case of the latter five, the second argument needs to be
3280 * a (positive) integer constant.
3281 * If the pencil option is set, then we also handle "{i,u}min" and
3282 * "{i,u}max".
3283 *
3284 * "pc" is the context in which the affine expression is created.
3285 */
extract_affine_from_call(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3286 static __isl_give isl_pw_aff *extract_affine_from_call(
3287 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3288 {
3289 isl_ctx *ctx;
3290 isl_pw_aff *aff1, *aff2;
3291 int n;
3292 const char *name;
3293 struct pet_options *options;
3294
3295 if (!expr)
3296 return NULL;
3297 ctx = pet_expr_get_ctx(expr);
3298 options = isl_ctx_peek_pet_options(ctx);
3299
3300 n = pet_expr_get_n_arg(expr);
3301 name = pet_expr_call_get_name(expr);
3302 if (!is_affine_builtin(options->pencil, n, name))
3303 return non_affine(pet_context_get_space(pc));
3304
3305 if (is_min_or_max_builtin(name)) {
3306 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3307 aff2 = pet_expr_extract_affine(expr->args[1], pc);
3308
3309 if (strstr(name, "min"))
3310 aff1 = isl_pw_aff_min(aff1, aff2);
3311 else
3312 aff1 = isl_pw_aff_max(aff1, aff2);
3313 } else if (!strcmp(name, "intMod")) {
3314 isl_val *v;
3315
3316 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3317 return non_affine(pet_context_get_space(pc));
3318 v = pet_expr_int_get_val(expr->args[1]);
3319 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3320 aff1 = isl_pw_aff_mod_val(aff1, v);
3321 } else {
3322 isl_val *v;
3323
3324 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3325 return non_affine(pet_context_get_space(pc));
3326 v = pet_expr_int_get_val(expr->args[1]);
3327 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3328 aff1 = isl_pw_aff_scale_down_val(aff1, v);
3329 if (!strcmp(name, "floord") || !strcmp(name, "intFloor"))
3330 aff1 = isl_pw_aff_floor(aff1);
3331 else
3332 aff1 = isl_pw_aff_ceil(aff1);
3333 }
3334
3335 return aff1;
3336 }
3337
3338 /* Extract an affine expression from "expr", if possible.
3339 * Otherwise return NaN.
3340 *
3341 * "pc" is the context in which the affine expression is created.
3342 *
3343 * Store the result in "pc" such that it can be reused in case
3344 * pet_expr_extract_affine is called again on the same pair of
3345 * "expr" and "pc".
3346 */
pet_expr_extract_affine(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3347 __isl_give isl_pw_aff *pet_expr_extract_affine(__isl_keep pet_expr *expr,
3348 __isl_keep pet_context *pc)
3349 {
3350 isl_maybe_isl_pw_aff m;
3351 isl_pw_aff *pa;
3352
3353 if (!expr)
3354 return NULL;
3355
3356 m = pet_context_get_extracted_affine(pc, expr);
3357 if (m.valid < 0 || m.valid)
3358 return m.value;
3359
3360 switch (pet_expr_get_type(expr)) {
3361 case pet_expr_access:
3362 pa = extract_affine_from_access(expr, pc);
3363 break;
3364 case pet_expr_int:
3365 pa = extract_affine_from_int(expr, pc);
3366 break;
3367 case pet_expr_op:
3368 pa = extract_affine_from_op(expr, pc);
3369 break;
3370 case pet_expr_call:
3371 pa = extract_affine_from_call(expr, pc);
3372 break;
3373 case pet_expr_cast:
3374 case pet_expr_double:
3375 case pet_expr_error:
3376 pa = non_affine(pet_context_get_space(pc));
3377 break;
3378 }
3379
3380 if (pet_context_set_extracted_affine(pc, expr, pa) < 0)
3381 return isl_pw_aff_free(pa);
3382
3383 return pa;
3384 }
3385
3386 /* Extract an affine expressions representing the comparison "LHS op RHS"
3387 * Return NaN if we are unable to extract such an affine expression.
3388 *
3389 * "pc" is the context in which the affine expression is created.
3390 *
3391 * If the comparison is of the form
3392 *
3393 * a <= min(b,c)
3394 *
3395 * then the expression is constructed as the conjunction of
3396 * the comparisons
3397 *
3398 * a <= b and a <= c
3399 *
3400 * A similar optimization is performed for max(a,b) <= c.
3401 * We do this because that will lead to simpler representations
3402 * of the expression.
3403 * If isl is ever enhanced to explicitly deal with min and max expressions,
3404 * this optimization can be removed.
3405 */
pet_expr_extract_comparison(enum pet_op_type op,__isl_keep pet_expr * lhs,__isl_keep pet_expr * rhs,__isl_keep pet_context * pc)3406 __isl_give isl_pw_aff *pet_expr_extract_comparison(enum pet_op_type op,
3407 __isl_keep pet_expr *lhs, __isl_keep pet_expr *rhs,
3408 __isl_keep pet_context *pc)
3409 {
3410 isl_pw_aff *lhs_pa, *rhs_pa;
3411
3412 if (op == pet_op_gt)
3413 return pet_expr_extract_comparison(pet_op_lt, rhs, lhs, pc);
3414 if (op == pet_op_ge)
3415 return pet_expr_extract_comparison(pet_op_le, rhs, lhs, pc);
3416
3417 if (op == pet_op_lt || op == pet_op_le) {
3418 if (pet_expr_is_min(rhs)) {
3419 lhs_pa = pet_expr_extract_comparison(op, lhs,
3420 rhs->args[0], pc);
3421 rhs_pa = pet_expr_extract_comparison(op, lhs,
3422 rhs->args[1], pc);
3423 return pet_and(lhs_pa, rhs_pa);
3424 }
3425 if (pet_expr_is_max(lhs)) {
3426 lhs_pa = pet_expr_extract_comparison(op, lhs->args[0],
3427 rhs, pc);
3428 rhs_pa = pet_expr_extract_comparison(op, lhs->args[1],
3429 rhs, pc);
3430 return pet_and(lhs_pa, rhs_pa);
3431 }
3432 }
3433
3434 lhs_pa = pet_expr_extract_affine(lhs, pc);
3435 rhs_pa = pet_expr_extract_affine(rhs, pc);
3436
3437 return pet_comparison(op, lhs_pa, rhs_pa);
3438 }
3439
3440 /* Extract an affine expressions from the comparison "expr".
3441 * Return NaN if we are unable to extract such an affine expression.
3442 *
3443 * "pc" is the context in which the affine expression is created.
3444 */
extract_comparison(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3445 static __isl_give isl_pw_aff *extract_comparison(__isl_keep pet_expr *expr,
3446 __isl_keep pet_context *pc)
3447 {
3448 enum pet_op_type type;
3449
3450 if (!expr)
3451 return NULL;
3452 if (expr->n_arg != 2)
3453 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3454 "expecting two arguments", return NULL);
3455
3456 type = pet_expr_op_get_type(expr);
3457 return pet_expr_extract_comparison(type, expr->args[0], expr->args[1],
3458 pc);
3459 }
3460
3461 /* Extract an affine expression representing the boolean operation
3462 * expressed by "expr".
3463 * Return NaN if we are unable to extract an affine expression.
3464 *
3465 * "pc" is the context in which the affine expression is created.
3466 */
extract_boolean(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3467 static __isl_give isl_pw_aff *extract_boolean(__isl_keep pet_expr *expr,
3468 __isl_keep pet_context *pc)
3469 {
3470 isl_pw_aff *lhs, *rhs;
3471 int n;
3472
3473 if (!expr)
3474 return NULL;
3475
3476 n = pet_expr_get_n_arg(expr);
3477 lhs = pet_expr_extract_affine_condition(expr->args[0], pc);
3478 if (n == 1)
3479 return pet_not(lhs);
3480
3481 rhs = pet_expr_extract_affine_condition(expr->args[1], pc);
3482 return pet_boolean(pet_expr_op_get_type(expr), lhs, rhs);
3483 }
3484
3485 /* Extract the affine expression "expr != 0 ? 1 : 0".
3486 * Return NaN if we are unable to extract an affine expression.
3487 *
3488 * "pc" is the context in which the affine expression is created.
3489 */
extract_implicit_condition(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3490 static __isl_give isl_pw_aff *extract_implicit_condition(
3491 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3492 {
3493 isl_pw_aff *res;
3494
3495 res = pet_expr_extract_affine(expr, pc);
3496 return pet_to_bool(res);
3497 }
3498
3499 /* Extract a boolean affine expression from "expr".
3500 * Return NaN if we are unable to extract an affine expression.
3501 *
3502 * "pc" is the context in which the affine expression is created.
3503 *
3504 * If "expr" is neither a comparison nor a boolean operation,
3505 * then we assume it is an affine expression and return the
3506 * boolean expression "expr != 0 ? 1 : 0".
3507 */
pet_expr_extract_affine_condition(__isl_keep pet_expr * expr,__isl_keep pet_context * pc)3508 __isl_give isl_pw_aff *pet_expr_extract_affine_condition(
3509 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3510 {
3511 if (!expr)
3512 return NULL;
3513
3514 if (pet_expr_is_comparison(expr))
3515 return extract_comparison(expr, pc);
3516 if (pet_expr_is_boolean(expr))
3517 return extract_boolean(expr, pc);
3518
3519 return extract_implicit_condition(expr, pc);
3520 }
3521
3522 /* Check if "expr" is an assume expression and if its single argument
3523 * can be converted to an affine expression in the context of "pc".
3524 * If so, replace the argument by the affine expression.
3525 */
pet_expr_resolve_assume(__isl_take pet_expr * expr,__isl_keep pet_context * pc)3526 __isl_give pet_expr *pet_expr_resolve_assume(__isl_take pet_expr *expr,
3527 __isl_keep pet_context *pc)
3528 {
3529 isl_pw_aff *cond;
3530 isl_multi_pw_aff *index;
3531
3532 if (!expr)
3533 return NULL;
3534 if (!pet_expr_is_assume(expr))
3535 return expr;
3536 if (expr->n_arg != 1)
3537 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3538 "expecting one argument", return pet_expr_free(expr));
3539
3540 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
3541 if (!cond)
3542 return pet_expr_free(expr);
3543 if (isl_pw_aff_involves_nan(cond)) {
3544 isl_pw_aff_free(cond);
3545 return expr;
3546 }
3547
3548 index = isl_multi_pw_aff_from_pw_aff(cond);
3549 expr = pet_expr_set_arg(expr, 0, pet_expr_from_index(index));
3550
3551 return expr;
3552 }
3553
3554 /* Return the number of bits needed to represent the type of "expr".
3555 * See the description of the type_size field of pet_expr.
3556 */
pet_expr_get_type_size(__isl_keep pet_expr * expr)3557 int pet_expr_get_type_size(__isl_keep pet_expr *expr)
3558 {
3559 return expr ? expr->type_size : 0;
3560 }
3561
3562 /* Replace the number of bits needed to represent the type of "expr"
3563 * by "type_size".
3564 * See the description of the type_size field of pet_expr.
3565 */
pet_expr_set_type_size(__isl_take pet_expr * expr,int type_size)3566 __isl_give pet_expr *pet_expr_set_type_size(__isl_take pet_expr *expr,
3567 int type_size)
3568 {
3569 expr = pet_expr_cow(expr);
3570 if (!expr)
3571 return NULL;
3572
3573 expr->type_size = type_size;
3574
3575 return expr;
3576 }
3577
3578 /* Extend an access expression "expr" with an additional index "index".
3579 * In particular, add "index" as an extra argument to "expr" and
3580 * adjust the index expression of "expr" to refer to this extra argument.
3581 * The caller is responsible for calling pet_expr_access_set_depth
3582 * to update the corresponding access relation.
3583 *
3584 * Note that we only collect the individual index expressions as
3585 * arguments of "expr" here.
3586 * An attempt to integrate them into the index expression of "expr"
3587 * is performed in pet_expr_access_plug_in_args.
3588 */
pet_expr_access_subscript(__isl_take pet_expr * expr,__isl_take pet_expr * index)3589 __isl_give pet_expr *pet_expr_access_subscript(__isl_take pet_expr *expr,
3590 __isl_take pet_expr *index)
3591 {
3592 int n;
3593 isl_space *space;
3594 isl_local_space *ls;
3595 isl_pw_aff *pa;
3596
3597 expr = pet_expr_cow(expr);
3598 if (!expr || !index)
3599 goto error;
3600 if (expr->type != pet_expr_access)
3601 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3602 "not an access pet_expr", goto error);
3603
3604 n = pet_expr_get_n_arg(expr);
3605 expr = pet_expr_insert_arg(expr, n, index);
3606 if (!expr)
3607 return NULL;
3608
3609 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3610 ls = isl_local_space_from_space(space);
3611 pa = isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, isl_dim_set, n));
3612 expr->acc.index = pet_array_subscript(expr->acc.index, pa);
3613 if (!expr->acc.index)
3614 return pet_expr_free(expr);
3615
3616 return expr;
3617 error:
3618 pet_expr_free(expr);
3619 pet_expr_free(index);
3620 return NULL;
3621 }
3622
3623 /* Extend an access expression "expr" with an additional member acces to "id".
3624 * In particular, extend the index expression of "expr" to include
3625 * the additional member access.
3626 * The caller is responsible for calling pet_expr_access_set_depth
3627 * to update the corresponding access relation.
3628 */
pet_expr_access_member(__isl_take pet_expr * expr,__isl_take isl_id * id)3629 __isl_give pet_expr *pet_expr_access_member(__isl_take pet_expr *expr,
3630 __isl_take isl_id *id)
3631 {
3632 isl_space *space;
3633 isl_multi_pw_aff *field_access;
3634
3635 expr = pet_expr_cow(expr);
3636 if (!expr || !id)
3637 goto error;
3638 if (expr->type != pet_expr_access)
3639 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3640 "not an access pet_expr", goto error);
3641
3642 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3643 space = isl_space_from_domain(space);
3644 space = isl_space_set_tuple_id(space, isl_dim_out, id);
3645 field_access = isl_multi_pw_aff_zero(space);
3646 expr->acc.index = pet_array_member(expr->acc.index, field_access);
3647 if (!expr->acc.index)
3648 return pet_expr_free(expr);
3649
3650 return expr;
3651 error:
3652 pet_expr_free(expr);
3653 isl_id_free(id);
3654 return NULL;
3655 }
3656
3657 /* Prefix the access expression "expr" with "prefix".
3658 * If "add" is set, then it is not the index expression "prefix" itself
3659 * that was passed to the function, but its address.
3660 */
pet_expr_access_patch(__isl_take pet_expr * expr,__isl_take isl_multi_pw_aff * prefix,int add)3661 __isl_give pet_expr *pet_expr_access_patch(__isl_take pet_expr *expr,
3662 __isl_take isl_multi_pw_aff *prefix, int add)
3663 {
3664 enum pet_expr_access_type type;
3665
3666 expr = pet_expr_cow(expr);
3667 if (!expr || !prefix)
3668 goto error;
3669 if (expr->type != pet_expr_access)
3670 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3671 "not an access pet_expr", goto error);
3672
3673 expr->acc.depth += isl_multi_pw_aff_dim(prefix, isl_dim_out) - add;
3674 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
3675 if (!expr->acc.access[type])
3676 continue;
3677 expr->acc.access[type] = pet_patch_union_map(
3678 isl_multi_pw_aff_copy(prefix), expr->acc.access[type],
3679 add, 0);
3680 if (!expr->acc.access[type])
3681 break;
3682 }
3683 expr->acc.index = pet_patch_multi_pw_aff(prefix, expr->acc.index, add);
3684 if (!expr->acc.index || type < pet_expr_access_end)
3685 return pet_expr_free(expr);
3686
3687 return expr;
3688 error:
3689 pet_expr_free(expr);
3690 isl_multi_pw_aff_free(prefix);
3691 return NULL;
3692 }
3693
3694 /* Dump the arguments of "expr" to "p" as a YAML sequence keyed
3695 * by "args", if there are any such arguments.
3696 */
dump_arguments(__isl_keep pet_expr * expr,__isl_take isl_printer * p)3697 static __isl_give isl_printer *dump_arguments(__isl_keep pet_expr *expr,
3698 __isl_take isl_printer *p)
3699 {
3700 int i;
3701
3702 if (expr->n_arg == 0)
3703 return p;
3704
3705 p = isl_printer_print_str(p, "args");
3706 p = isl_printer_yaml_next(p);
3707 p = isl_printer_yaml_start_sequence(p);
3708 for (i = 0; i < expr->n_arg; ++i) {
3709 p = pet_expr_print(expr->args[i], p);
3710 p = isl_printer_yaml_next(p);
3711 }
3712 p = isl_printer_yaml_end_sequence(p);
3713
3714 return p;
3715 }
3716
3717 /* Print "expr" to "p" in YAML format.
3718 */
pet_expr_print(__isl_keep pet_expr * expr,__isl_take isl_printer * p)3719 __isl_give isl_printer *pet_expr_print(__isl_keep pet_expr *expr,
3720 __isl_take isl_printer *p)
3721 {
3722 if (!expr || !p)
3723 return isl_printer_free(p);
3724
3725 switch (expr->type) {
3726 case pet_expr_double:
3727 p = isl_printer_print_str(p, expr->d.s);
3728 break;
3729 case pet_expr_int:
3730 p = isl_printer_print_val(p, expr->i);
3731 break;
3732 case pet_expr_access:
3733 p = isl_printer_yaml_start_mapping(p);
3734 if (expr->acc.ref_id) {
3735 p = isl_printer_print_str(p, "ref_id");
3736 p = isl_printer_yaml_next(p);
3737 p = isl_printer_print_id(p, expr->acc.ref_id);
3738 p = isl_printer_yaml_next(p);
3739 }
3740 p = isl_printer_print_str(p, "index");
3741 p = isl_printer_yaml_next(p);
3742 p = isl_printer_print_multi_pw_aff(p, expr->acc.index);
3743 p = isl_printer_yaml_next(p);
3744 p = isl_printer_print_str(p, "depth");
3745 p = isl_printer_yaml_next(p);
3746 p = isl_printer_print_int(p, expr->acc.depth);
3747 p = isl_printer_yaml_next(p);
3748 if (expr->acc.kill) {
3749 p = isl_printer_print_str(p, "kill");
3750 p = isl_printer_yaml_next(p);
3751 p = isl_printer_print_int(p, 1);
3752 p = isl_printer_yaml_next(p);
3753 } else {
3754 p = isl_printer_print_str(p, "read");
3755 p = isl_printer_yaml_next(p);
3756 p = isl_printer_print_int(p, expr->acc.read);
3757 p = isl_printer_yaml_next(p);
3758 p = isl_printer_print_str(p, "write");
3759 p = isl_printer_yaml_next(p);
3760 p = isl_printer_print_int(p, expr->acc.write);
3761 p = isl_printer_yaml_next(p);
3762 }
3763 if (expr->acc.access[pet_expr_access_may_read]) {
3764 p = isl_printer_print_str(p, "may_read");
3765 p = isl_printer_yaml_next(p);
3766 p = isl_printer_print_union_map(p,
3767 expr->acc.access[pet_expr_access_may_read]);
3768 p = isl_printer_yaml_next(p);
3769 }
3770 if (expr->acc.access[pet_expr_access_may_write]) {
3771 p = isl_printer_print_str(p, "may_write");
3772 p = isl_printer_yaml_next(p);
3773 p = isl_printer_print_union_map(p,
3774 expr->acc.access[pet_expr_access_may_write]);
3775 p = isl_printer_yaml_next(p);
3776 }
3777 if (expr->acc.access[pet_expr_access_must_write]) {
3778 p = isl_printer_print_str(p, "must_write");
3779 p = isl_printer_yaml_next(p);
3780 p = isl_printer_print_union_map(p,
3781 expr->acc.access[pet_expr_access_must_write]);
3782 p = isl_printer_yaml_next(p);
3783 }
3784 p = dump_arguments(expr, p);
3785 p = isl_printer_yaml_end_mapping(p);
3786 break;
3787 case pet_expr_op:
3788 p = isl_printer_yaml_start_mapping(p);
3789 p = isl_printer_print_str(p, "op");
3790 p = isl_printer_yaml_next(p);
3791 p = isl_printer_print_str(p, op_str[expr->op]);
3792 p = isl_printer_yaml_next(p);
3793 p = dump_arguments(expr, p);
3794 p = isl_printer_yaml_end_mapping(p);
3795 break;
3796 case pet_expr_call:
3797 p = isl_printer_yaml_start_mapping(p);
3798 p = isl_printer_print_str(p, "call");
3799 p = isl_printer_yaml_next(p);
3800 p = isl_printer_print_str(p, expr->c.name);
3801 p = isl_printer_print_str(p, "/");
3802 p = isl_printer_print_int(p, expr->n_arg);
3803 p = isl_printer_yaml_next(p);
3804 p = dump_arguments(expr, p);
3805 if (expr->c.summary) {
3806 p = isl_printer_print_str(p, "summary");
3807 p = isl_printer_yaml_next(p);
3808 p = pet_function_summary_print(expr->c.summary, p);
3809 }
3810 p = isl_printer_yaml_end_mapping(p);
3811 break;
3812 case pet_expr_cast:
3813 p = isl_printer_yaml_start_mapping(p);
3814 p = isl_printer_print_str(p, "cast");
3815 p = isl_printer_yaml_next(p);
3816 p = isl_printer_print_str(p, expr->type_name);
3817 p = isl_printer_yaml_next(p);
3818 p = dump_arguments(expr, p);
3819 p = isl_printer_yaml_end_mapping(p);
3820 break;
3821 case pet_expr_error:
3822 p = isl_printer_print_str(p, "ERROR");
3823 break;
3824 }
3825
3826 return p;
3827 }
3828
3829 /* Dump "expr" to stderr with indentation "indent".
3830 */
pet_expr_dump_with_indent(__isl_keep pet_expr * expr,int indent)3831 void pet_expr_dump_with_indent(__isl_keep pet_expr *expr, int indent)
3832 {
3833 isl_printer *p;
3834
3835 if (!expr)
3836 return;
3837
3838 p = isl_printer_to_file(pet_expr_get_ctx(expr), stderr);
3839 p = isl_printer_set_indent(p, indent);
3840 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);
3841 p = isl_printer_start_line(p);
3842 p = pet_expr_print(expr, p);
3843
3844 isl_printer_free(p);
3845 }
3846
pet_expr_dump(__isl_keep pet_expr * expr)3847 void pet_expr_dump(__isl_keep pet_expr *expr)
3848 {
3849 pet_expr_dump_with_indent(expr, 0);
3850 }
3851