1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2014 Ecole Normale Superieure. All rights reserved.
4 * Copyright 2017 Sven Verdoolaege. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
25 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * The views and conclusions contained in the software and documentation
31 * are those of the authors and should not be interpreted as
32 * representing official policies, either expressed or implied, of
33 * Leiden University.
34 */
35
36 #include <string.h>
37
38 #include <isl/ctx.h>
39 #include <isl/id.h>
40 #include <isl/val.h>
41 #include <isl/space.h>
42 #include <isl/aff.h>
43
44 #include "expr.h"
45 #include "loc.h"
46 #include "tree.h"
47
48 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
49
50 static const char *type_str[] = {
51 [pet_tree_block] = "block",
52 [pet_tree_break] = "break",
53 [pet_tree_continue] = "continue",
54 [pet_tree_decl] = "declaration",
55 [pet_tree_decl_init] = "declaration-init",
56 [pet_tree_expr] = "expression",
57 [pet_tree_for] = "for",
58 [pet_tree_infinite_loop] = "infinite-loop",
59 [pet_tree_if] = "if",
60 [pet_tree_if_else] = "if-else",
61 [pet_tree_while] = "while",
62 [pet_tree_return] = "return",
63 };
64
65 /* Return a textual representation of the type "type".
66 */
pet_tree_type_str(enum pet_tree_type type)67 const char *pet_tree_type_str(enum pet_tree_type type)
68 {
69 if (type < 0)
70 return "error";
71 return type_str[type];
72 }
73
74 /* Extract a type from its textual representation "str".
75 */
pet_tree_str_type(const char * str)76 enum pet_tree_type pet_tree_str_type(const char *str)
77 {
78 int i;
79
80 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
81 if (!strcmp(type_str[i], str))
82 return i;
83
84 return pet_tree_error;
85 }
86
87 /* Return a new pet_tree of the given type.
88 *
89 * The location is initializaed to pet_loc_dummy.
90 */
pet_tree_alloc(isl_ctx * ctx,enum pet_tree_type type)91 __isl_give pet_tree *pet_tree_alloc(isl_ctx *ctx, enum pet_tree_type type)
92 {
93 pet_tree *tree;
94
95 tree = isl_calloc_type(ctx, struct pet_tree);
96 if (!tree)
97 return NULL;
98
99 tree->ctx = ctx;
100 isl_ctx_ref(ctx);
101 tree->ref = 1;
102 tree->type = type;
103 tree->loc = &pet_loc_dummy;
104
105 return tree;
106 }
107
108 /* Return a new pet_tree representing the declaration (without initialization)
109 * of the variable "var".
110 */
pet_tree_new_decl(__isl_take pet_expr * var)111 __isl_give pet_tree *pet_tree_new_decl(__isl_take pet_expr *var)
112 {
113 isl_ctx *ctx;
114 pet_tree *tree;
115
116 if (!var)
117 return NULL;
118 ctx = pet_expr_get_ctx(var);
119 tree = pet_tree_alloc(ctx, pet_tree_decl);
120 if (!tree)
121 goto error;
122
123 tree->u.d.var = var;
124
125 return tree;
126 error:
127 pet_expr_free(var);
128 return NULL;
129 }
130
131 /* Return a new pet_tree representing the declaration of the variable "var"
132 * with initial value "init".
133 */
pet_tree_new_decl_init(__isl_take pet_expr * var,__isl_take pet_expr * init)134 __isl_give pet_tree *pet_tree_new_decl_init(__isl_take pet_expr *var,
135 __isl_take pet_expr *init)
136 {
137 isl_ctx *ctx;
138 pet_tree *tree;
139
140 if (!var || !init)
141 goto error;
142 ctx = pet_expr_get_ctx(var);
143 tree = pet_tree_alloc(ctx, pet_tree_decl_init);
144 if (!tree)
145 goto error;
146
147 tree->u.d.var = var;
148 tree->u.d.init = init;
149
150 return tree;
151 error:
152 pet_expr_free(var);
153 pet_expr_free(init);
154 return NULL;
155 }
156
157 /* Return a new pet_tree representing the expression "expr".
158 */
pet_tree_new_expr(__isl_take pet_expr * expr)159 __isl_give pet_tree *pet_tree_new_expr(__isl_take pet_expr *expr)
160 {
161 isl_ctx *ctx;
162 pet_tree *tree;
163
164 if (!expr)
165 return NULL;
166 ctx = pet_expr_get_ctx(expr);
167 tree = pet_tree_alloc(ctx, pet_tree_expr);
168 if (!tree)
169 goto error;
170
171 tree->u.e.expr = expr;
172
173 return tree;
174 error:
175 pet_expr_free(expr);
176 return NULL;
177 }
178
179 /* Return a new pet_tree representing the return of expression "expr".
180 */
pet_tree_new_return(__isl_take pet_expr * expr)181 __isl_give pet_tree *pet_tree_new_return(__isl_take pet_expr *expr)
182 {
183 isl_ctx *ctx;
184 pet_tree *tree;
185
186 if (!expr)
187 return NULL;
188 ctx = pet_expr_get_ctx(expr);
189 tree = pet_tree_alloc(ctx, pet_tree_return);
190 if (!tree)
191 goto error;
192
193 tree->u.e.expr = expr;
194
195 return tree;
196 error:
197 pet_expr_free(expr);
198 return NULL;
199 }
200
201 /* Return a new pet_tree representing an initially empty sequence
202 * of trees with room for "n" trees.
203 * "block" indicates whether the sequence has its own scope.
204 */
pet_tree_new_block(isl_ctx * ctx,int block,int n)205 __isl_give pet_tree *pet_tree_new_block(isl_ctx *ctx, int block, int n)
206 {
207 pet_tree *tree;
208
209 tree = pet_tree_alloc(ctx, pet_tree_block);
210 if (!tree)
211 return NULL;
212 tree->u.b.block = block;
213 tree->u.b.n = 0;
214 tree->u.b.max = n;
215 tree->u.b.child = isl_calloc_array(ctx, pet_tree *, n);
216 if (n && !tree->u.b.child)
217 return pet_tree_free(tree);
218
219 return tree;
220 }
221
222 /* Return a new pet_tree representing a break statement.
223 */
pet_tree_new_break(isl_ctx * ctx)224 __isl_give pet_tree *pet_tree_new_break(isl_ctx *ctx)
225 {
226 return pet_tree_alloc(ctx, pet_tree_break);
227 }
228
229 /* Return a new pet_tree representing a continue statement.
230 */
pet_tree_new_continue(isl_ctx * ctx)231 __isl_give pet_tree *pet_tree_new_continue(isl_ctx *ctx)
232 {
233 return pet_tree_alloc(ctx, pet_tree_continue);
234 }
235
236 /* Return a new pet_tree representing a for loop
237 * with induction variable "iv", initial value for the induction
238 * variable "init", loop condition "cond", induction variable increment "inc"
239 * and loop body "body". "declared" indicates whether the induction variable
240 * is declared by the loop. "independent" is set if the for loop is marked
241 * independent.
242 *
243 * The location of the loop is initialized to that of the body.
244 */
pet_tree_new_for(int independent,int declared,__isl_take pet_expr * iv,__isl_take pet_expr * init,__isl_take pet_expr * cond,__isl_take pet_expr * inc,__isl_take pet_tree * body)245 __isl_give pet_tree *pet_tree_new_for(int independent, int declared,
246 __isl_take pet_expr *iv, __isl_take pet_expr *init,
247 __isl_take pet_expr *cond, __isl_take pet_expr *inc,
248 __isl_take pet_tree *body)
249 {
250 isl_ctx *ctx;
251 pet_tree *tree;
252
253 if (!iv || !init || !cond || !inc || !body)
254 goto error;
255 ctx = pet_tree_get_ctx(body);
256 tree = pet_tree_alloc(ctx, pet_tree_for);
257 if (!tree)
258 goto error;
259
260 tree->u.l.independent = independent;
261 tree->u.l.declared = declared;
262 tree->u.l.iv = iv;
263 tree->u.l.init = init;
264 tree->u.l.cond = cond;
265 tree->u.l.inc = inc;
266 tree->u.l.body = body;
267 tree->loc = pet_tree_get_loc(body);
268 if (!tree->loc)
269 return pet_tree_free(tree);
270
271 return tree;
272 error:
273 pet_expr_free(iv);
274 pet_expr_free(init);
275 pet_expr_free(cond);
276 pet_expr_free(inc);
277 pet_tree_free(body);
278 return NULL;
279 }
280
281 /* Return a new pet_tree representing a while loop
282 * with loop condition "cond" and loop body "body".
283 *
284 * The location of the loop is initialized to that of the body.
285 */
pet_tree_new_while(__isl_take pet_expr * cond,__isl_take pet_tree * body)286 __isl_give pet_tree *pet_tree_new_while(__isl_take pet_expr *cond,
287 __isl_take pet_tree *body)
288 {
289 isl_ctx *ctx;
290 pet_tree *tree;
291
292 if (!cond || !body)
293 goto error;
294 ctx = pet_tree_get_ctx(body);
295 tree = pet_tree_alloc(ctx, pet_tree_while);
296 if (!tree)
297 goto error;
298
299 tree->u.l.cond = cond;
300 tree->u.l.body = body;
301 tree->loc = pet_tree_get_loc(body);
302 if (!tree->loc)
303 return pet_tree_free(tree);
304
305 return tree;
306 error:
307 pet_expr_free(cond);
308 pet_tree_free(body);
309 return NULL;
310 }
311
312 /* Return a new pet_tree representing an infinite loop
313 * with loop body "body".
314 *
315 * The location of the loop is initialized to that of the body.
316 */
pet_tree_new_infinite_loop(__isl_take pet_tree * body)317 __isl_give pet_tree *pet_tree_new_infinite_loop(__isl_take pet_tree *body)
318 {
319 isl_ctx *ctx;
320 pet_tree *tree;
321
322 if (!body)
323 return NULL;
324 ctx = pet_tree_get_ctx(body);
325 tree = pet_tree_alloc(ctx, pet_tree_infinite_loop);
326 if (!tree)
327 return pet_tree_free(body);
328
329 tree->u.l.body = body;
330 tree->loc = pet_tree_get_loc(body);
331 if (!tree->loc)
332 return pet_tree_free(tree);
333
334 return tree;
335 }
336
337 /* Return a new pet_tree representing an if statement
338 * with condition "cond" and then branch "then_body".
339 *
340 * The location of the if statement is initialized to that of the body.
341 */
pet_tree_new_if(__isl_take pet_expr * cond,__isl_take pet_tree * then_body)342 __isl_give pet_tree *pet_tree_new_if(__isl_take pet_expr *cond,
343 __isl_take pet_tree *then_body)
344 {
345 isl_ctx *ctx;
346 pet_tree *tree;
347
348 if (!cond || !then_body)
349 goto error;
350 ctx = pet_tree_get_ctx(then_body);
351 tree = pet_tree_alloc(ctx, pet_tree_if);
352 if (!tree)
353 goto error;
354
355 tree->u.i.cond = cond;
356 tree->u.i.then_body = then_body;
357 tree->loc = pet_tree_get_loc(then_body);
358 if (!tree->loc)
359 return pet_tree_free(tree);
360
361 return tree;
362 error:
363 pet_expr_free(cond);
364 pet_tree_free(then_body);
365 return NULL;
366 }
367
368 /* Return a new pet_tree representing an if statement
369 * with condition "cond", then branch "then_body" and else branch "else_body".
370 *
371 * The location of the if statement is initialized to cover
372 * those of the bodies.
373 */
pet_tree_new_if_else(__isl_take pet_expr * cond,__isl_take pet_tree * then_body,__isl_take pet_tree * else_body)374 __isl_give pet_tree *pet_tree_new_if_else(__isl_take pet_expr *cond,
375 __isl_take pet_tree *then_body, __isl_take pet_tree *else_body)
376 {
377 isl_ctx *ctx;
378 pet_tree *tree;
379
380 if (!cond || !then_body || !else_body)
381 goto error;
382 ctx = pet_tree_get_ctx(then_body);
383 tree = pet_tree_alloc(ctx, pet_tree_if_else);
384 if (!tree)
385 goto error;
386
387 tree->u.i.cond = cond;
388 tree->u.i.then_body = then_body;
389 tree->u.i.else_body = else_body;
390 tree->loc = pet_tree_get_loc(then_body);
391 tree->loc = pet_loc_update_start_end_from_loc(tree->loc,
392 else_body->loc);
393 if (!tree->loc)
394 return pet_tree_free(tree);
395
396 return tree;
397 error:
398 pet_expr_free(cond);
399 pet_tree_free(then_body);
400 pet_tree_free(else_body);
401 return NULL;
402 }
403
404 /* Return an independent duplicate of "tree".
405 */
pet_tree_dup(__isl_keep pet_tree * tree)406 static __isl_give pet_tree *pet_tree_dup(__isl_keep pet_tree *tree)
407 {
408 int i;
409 pet_tree *dup;
410
411 if (!tree)
412 return NULL;
413
414 switch (tree->type) {
415 case pet_tree_error:
416 return NULL;
417 case pet_tree_block:
418 dup = pet_tree_new_block(tree->ctx, tree->u.b.block,
419 tree->u.b.n);
420 for (i = 0; i < tree->u.b.n; ++i)
421 dup = pet_tree_block_add_child(dup,
422 pet_tree_copy(tree->u.b.child[i]));
423 break;
424 case pet_tree_break:
425 dup = pet_tree_new_break(tree->ctx);
426 break;
427 case pet_tree_continue:
428 dup = pet_tree_new_continue(tree->ctx);
429 break;
430 case pet_tree_decl:
431 dup = pet_tree_new_decl(pet_expr_copy(tree->u.d.var));
432 break;
433 case pet_tree_decl_init:
434 dup = pet_tree_new_decl_init(pet_expr_copy(tree->u.d.var),
435 pet_expr_copy(tree->u.d.init));
436 break;
437 case pet_tree_expr:
438 dup = pet_tree_new_expr(pet_expr_copy(tree->u.e.expr));
439 break;
440 case pet_tree_return:
441 dup = pet_tree_new_return(pet_expr_copy(tree->u.e.expr));
442 break;
443 case pet_tree_for:
444 dup = pet_tree_new_for(tree->u.l.independent,
445 tree->u.l.declared,
446 pet_expr_copy(tree->u.l.iv), pet_expr_copy(tree->u.l.init),
447 pet_expr_copy(tree->u.l.cond), pet_expr_copy(tree->u.l.inc),
448 pet_tree_copy(tree->u.l.body));
449 break;
450 case pet_tree_while:
451 dup = pet_tree_new_while(pet_expr_copy(tree->u.l.cond),
452 pet_tree_copy(tree->u.l.body));
453 break;
454 case pet_tree_infinite_loop:
455 dup = pet_tree_new_infinite_loop(pet_tree_copy(tree->u.l.body));
456 break;
457 case pet_tree_if:
458 dup = pet_tree_new_if(pet_expr_copy(tree->u.i.cond),
459 pet_tree_copy(tree->u.i.then_body));
460 break;
461 case pet_tree_if_else:
462 dup = pet_tree_new_if_else(pet_expr_copy(tree->u.i.cond),
463 pet_tree_copy(tree->u.i.then_body),
464 pet_tree_copy(tree->u.i.else_body));
465 break;
466 }
467
468 if (!dup)
469 return NULL;
470 pet_loc_free(dup->loc);
471 dup->loc = pet_loc_copy(tree->loc);
472 if (!dup->loc)
473 return pet_tree_free(dup);
474 if (tree->label) {
475 dup->label = isl_id_copy(tree->label);
476 if (!dup->label)
477 return pet_tree_free(dup);
478 }
479
480 return dup;
481 }
482
483 /* Return a pet_tree that is equal to "tree" and that has only one reference.
484 */
pet_tree_cow(__isl_take pet_tree * tree)485 __isl_give pet_tree *pet_tree_cow(__isl_take pet_tree *tree)
486 {
487 if (!tree)
488 return NULL;
489
490 if (tree->ref == 1)
491 return tree;
492 tree->ref--;
493 return pet_tree_dup(tree);
494 }
495
496 /* Return an extra reference to "tree".
497 */
pet_tree_copy(__isl_keep pet_tree * tree)498 __isl_give pet_tree *pet_tree_copy(__isl_keep pet_tree *tree)
499 {
500 if (!tree)
501 return NULL;
502
503 tree->ref++;
504 return tree;
505 }
506
507 /* Free a reference to "tree".
508 */
pet_tree_free(__isl_take pet_tree * tree)509 __isl_null pet_tree *pet_tree_free(__isl_take pet_tree *tree)
510 {
511 int i;
512
513 if (!tree)
514 return NULL;
515 if (--tree->ref > 0)
516 return NULL;
517
518 pet_loc_free(tree->loc);
519 isl_id_free(tree->label);
520
521 switch (tree->type) {
522 case pet_tree_error:
523 break;
524 case pet_tree_block:
525 for (i = 0; i < tree->u.b.n; ++i)
526 pet_tree_free(tree->u.b.child[i]);
527 free(tree->u.b.child);
528 break;
529 case pet_tree_break:
530 case pet_tree_continue:
531 break;
532 case pet_tree_decl_init:
533 pet_expr_free(tree->u.d.init);
534 case pet_tree_decl:
535 pet_expr_free(tree->u.d.var);
536 break;
537 case pet_tree_expr:
538 case pet_tree_return:
539 pet_expr_free(tree->u.e.expr);
540 break;
541 case pet_tree_for:
542 pet_expr_free(tree->u.l.iv);
543 pet_expr_free(tree->u.l.init);
544 pet_expr_free(tree->u.l.inc);
545 case pet_tree_while:
546 pet_expr_free(tree->u.l.cond);
547 case pet_tree_infinite_loop:
548 pet_tree_free(tree->u.l.body);
549 break;
550 case pet_tree_if_else:
551 pet_tree_free(tree->u.i.else_body);
552 case pet_tree_if:
553 pet_expr_free(tree->u.i.cond);
554 pet_tree_free(tree->u.i.then_body);
555 break;
556 }
557
558 isl_ctx_deref(tree->ctx);
559 free(tree);
560 return NULL;
561 }
562
563 /* Return the isl_ctx in which "tree" was created.
564 */
pet_tree_get_ctx(__isl_keep pet_tree * tree)565 isl_ctx *pet_tree_get_ctx(__isl_keep pet_tree *tree)
566 {
567 return tree ? tree->ctx : NULL;
568 }
569
570 /* Return the location of "tree".
571 */
pet_tree_get_loc(__isl_keep pet_tree * tree)572 __isl_give pet_loc *pet_tree_get_loc(__isl_keep pet_tree *tree)
573 {
574 return tree ? pet_loc_copy(tree->loc) : NULL;
575 }
576
577 /* Return the type of "tree".
578 */
pet_tree_get_type(__isl_keep pet_tree * tree)579 enum pet_tree_type pet_tree_get_type(__isl_keep pet_tree *tree)
580 {
581 if (!tree)
582 return pet_tree_error;
583
584 return tree->type;
585 }
586
587 /* Replace the location of "tree" by "loc".
588 */
pet_tree_set_loc(__isl_take pet_tree * tree,__isl_take pet_loc * loc)589 __isl_give pet_tree *pet_tree_set_loc(__isl_take pet_tree *tree,
590 __isl_take pet_loc *loc)
591 {
592 tree = pet_tree_cow(tree);
593 if (!tree || !loc)
594 goto error;
595
596 pet_loc_free(tree->loc);
597 tree->loc = loc;
598
599 return tree;
600 error:
601 pet_loc_free(loc);
602 pet_tree_free(tree);
603 return NULL;
604 }
605
606 /* Replace the label of "tree" by "label".
607 */
pet_tree_set_label(__isl_take pet_tree * tree,__isl_take isl_id * label)608 __isl_give pet_tree *pet_tree_set_label(__isl_take pet_tree *tree,
609 __isl_take isl_id *label)
610 {
611 tree = pet_tree_cow(tree);
612 if (!tree || !label)
613 goto error;
614
615 isl_id_free(tree->label);
616 tree->label = label;
617
618 return tree;
619 error:
620 isl_id_free(label);
621 return pet_tree_free(tree);
622 }
623
624 /* Given an expression tree "tree", return the associated expression.
625 */
pet_tree_expr_get_expr(__isl_keep pet_tree * tree)626 __isl_give pet_expr *pet_tree_expr_get_expr(__isl_keep pet_tree *tree)
627 {
628 if (!tree)
629 return NULL;
630 if (pet_tree_get_type(tree) != pet_tree_expr)
631 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
632 "not an expression tree", return NULL);
633
634 return pet_expr_copy(tree->u.e.expr);
635 }
636
637 /* Given a return tree "tree", return the returned expression.
638 */
pet_tree_return_get_expr(__isl_keep pet_tree * tree)639 __isl_give pet_expr *pet_tree_return_get_expr(__isl_keep pet_tree *tree)
640 {
641 if (!tree)
642 return NULL;
643 if (pet_tree_get_type(tree) != pet_tree_return)
644 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
645 "not a return tree", return NULL);
646
647 return pet_expr_copy(tree->u.e.expr);
648 }
649
650 /* Given a block tree "tree", return the number of children in the sequence.
651 */
pet_tree_block_n_child(__isl_keep pet_tree * tree)652 int pet_tree_block_n_child(__isl_keep pet_tree *tree)
653 {
654 if (!tree)
655 return -1;
656 if (pet_tree_get_type(tree) != pet_tree_block)
657 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
658 "not a block tree", return -1);
659
660 return tree->u.b.n;
661 }
662
663 /* Add "child" to the sequence of trees represented by "block".
664 *
665 * Update the location of "block" to include that of "child".
666 */
pet_tree_block_add_child(__isl_take pet_tree * block,__isl_take pet_tree * child)667 __isl_give pet_tree *pet_tree_block_add_child(__isl_take pet_tree *block,
668 __isl_take pet_tree *child)
669 {
670 block = pet_tree_cow(block);
671 if (!block || !child)
672 goto error;
673 if (block->type != pet_tree_block)
674 isl_die(pet_tree_get_ctx(block), isl_error_invalid,
675 "not a block tree", goto error);
676 if (block->u.b.n >= block->u.b.max)
677 isl_die(pet_tree_get_ctx(block), isl_error_invalid,
678 "out of space in block", goto error);
679
680 block->loc = pet_loc_update_start_end_from_loc(block->loc, child->loc);
681 block->u.b.child[block->u.b.n++] = child;
682
683 if (!block->loc)
684 return pet_tree_free(block);
685
686 return block;
687 error:
688 pet_tree_free(block);
689 pet_tree_free(child);
690 return NULL;
691 }
692
693 /* Does the block tree "tree" have its own scope?
694 */
pet_tree_block_get_block(__isl_keep pet_tree * tree)695 int pet_tree_block_get_block(__isl_keep pet_tree *tree)
696 {
697 if (!tree)
698 return -1;
699 if (pet_tree_get_type(tree) != pet_tree_block)
700 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
701 "not a block tree", return -1);
702
703 return tree->u.b.block;
704 }
705
706 /* Set the block property (whether or not the block tree has its own scope)
707 * of "tree" to "is_block".
708 */
pet_tree_block_set_block(__isl_take pet_tree * tree,int is_block)709 __isl_give pet_tree *pet_tree_block_set_block(__isl_take pet_tree *tree,
710 int is_block)
711 {
712 if (!tree)
713 return NULL;
714 if (tree->type != pet_tree_block)
715 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
716 "not a block tree", return pet_tree_free(tree));
717 if (tree->u.b.block == is_block)
718 return tree;
719 tree = pet_tree_cow(tree);
720 if (!tree)
721 return NULL;
722 tree->u.b.block = is_block;
723 return tree;
724 }
725
726 /* Given a block tree "tree", return the child at position "pos".
727 */
pet_tree_block_get_child(__isl_keep pet_tree * tree,int pos)728 __isl_give pet_tree *pet_tree_block_get_child(__isl_keep pet_tree *tree,
729 int pos)
730 {
731 if (!tree)
732 return NULL;
733 if (pet_tree_get_type(tree) != pet_tree_block)
734 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
735 "not a block tree", return NULL);
736 if (pos < 0 || pos >= tree->u.b.n)
737 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
738 "position out of bounds", return NULL);
739
740 return pet_tree_copy(tree->u.b.child[pos]);
741 }
742
743 /* Does "tree" represent a declaration (with or without initialization)?
744 */
pet_tree_is_decl(__isl_keep pet_tree * tree)745 int pet_tree_is_decl(__isl_keep pet_tree *tree)
746 {
747 if (!tree)
748 return -1;
749
750 switch (pet_tree_get_type(tree)) {
751 case pet_tree_decl:
752 case pet_tree_decl_init:
753 return 1;
754 default:
755 return 0;
756 }
757 }
758
759 /* Given a declaration tree "tree", return the variable that is being
760 * declared.
761 */
pet_tree_decl_get_var(__isl_keep pet_tree * tree)762 __isl_give pet_expr *pet_tree_decl_get_var(__isl_keep pet_tree *tree)
763 {
764 if (!tree)
765 return NULL;
766 if (!pet_tree_is_decl(tree))
767 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
768 "not a decl tree", return NULL);
769
770 return pet_expr_copy(tree->u.d.var);
771 }
772
773 /* Given a declaration tree with initialization "tree",
774 * return the initial value of the declared variable.
775 */
pet_tree_decl_get_init(__isl_keep pet_tree * tree)776 __isl_give pet_expr *pet_tree_decl_get_init(__isl_keep pet_tree *tree)
777 {
778 if (!tree)
779 return NULL;
780 if (pet_tree_get_type(tree) != pet_tree_decl_init)
781 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
782 "not a decl_init tree", return NULL);
783
784 return pet_expr_copy(tree->u.d.init);
785 }
786
787 /* Given an if tree "tree", return the if condition.
788 */
pet_tree_if_get_cond(__isl_keep pet_tree * tree)789 __isl_give pet_expr *pet_tree_if_get_cond(__isl_keep pet_tree *tree)
790 {
791 enum pet_tree_type type;
792
793 if (!tree)
794 return NULL;
795 type = pet_tree_get_type(tree);
796 if (type != pet_tree_if && type != pet_tree_if_else)
797 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
798 "not an if tree", return NULL);
799
800 return pet_expr_copy(tree->u.i.cond);
801 }
802
803 /* Given an if tree "tree", return the body of the then branch.
804 */
pet_tree_if_get_then(__isl_keep pet_tree * tree)805 __isl_give pet_tree *pet_tree_if_get_then(__isl_keep pet_tree *tree)
806 {
807 enum pet_tree_type type;
808
809 if (!tree)
810 return NULL;
811 type = pet_tree_get_type(tree);
812 if (type != pet_tree_if && type != pet_tree_if_else)
813 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
814 "not an if tree", return NULL);
815
816 return pet_tree_copy(tree->u.i.then_body);
817 }
818
819 /* Given an if tree with an else branch "tree",
820 * return the body of that else branch.
821 */
pet_tree_if_get_else(__isl_keep pet_tree * tree)822 __isl_give pet_tree *pet_tree_if_get_else(__isl_keep pet_tree *tree)
823 {
824 if (!tree)
825 return NULL;
826 if (pet_tree_get_type(tree) != pet_tree_if_else)
827 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
828 "not an if tree with an else branch", return NULL);
829
830 return pet_tree_copy(tree->u.i.else_body);
831 }
832
833 /* Does "tree" represent some type of loop?
834 */
pet_tree_is_loop(__isl_keep pet_tree * tree)835 int pet_tree_is_loop(__isl_keep pet_tree *tree)
836 {
837 if (!tree)
838 return -1;
839
840 switch (pet_tree_get_type(tree)) {
841 case pet_tree_for:
842 case pet_tree_infinite_loop:
843 case pet_tree_while:
844 return 1;
845 default:
846 return 0;
847 }
848 }
849
850 /* Given a for loop "tree", return the induction variable.
851 */
pet_tree_loop_get_var(__isl_keep pet_tree * tree)852 __isl_give pet_expr *pet_tree_loop_get_var(__isl_keep pet_tree *tree)
853 {
854 if (!tree)
855 return NULL;
856 if (pet_tree_get_type(tree) != pet_tree_for)
857 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
858 "not a for tree", return NULL);
859
860 return pet_expr_copy(tree->u.l.iv);
861 }
862
863 /* Given a for loop "tree", return the initial value of the induction variable.
864 */
pet_tree_loop_get_init(__isl_keep pet_tree * tree)865 __isl_give pet_expr *pet_tree_loop_get_init(__isl_keep pet_tree *tree)
866 {
867 if (!tree)
868 return NULL;
869 if (pet_tree_get_type(tree) != pet_tree_for)
870 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
871 "not a for tree", return NULL);
872
873 return pet_expr_copy(tree->u.l.init);
874 }
875
876 /* Given a loop "tree", return the loop condition.
877 *
878 * For an infinite loop, the loop condition always holds,
879 * so we simply return "1".
880 */
pet_tree_loop_get_cond(__isl_keep pet_tree * tree)881 __isl_give pet_expr *pet_tree_loop_get_cond(__isl_keep pet_tree *tree)
882 {
883 enum pet_tree_type type;
884
885 if (!tree)
886 return NULL;
887 type = pet_tree_get_type(tree);
888 if (type == pet_tree_infinite_loop)
889 return pet_expr_new_int(isl_val_one(pet_tree_get_ctx(tree)));
890 if (type != pet_tree_for && type != pet_tree_while)
891 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
892 "not a for or while tree", return NULL);
893
894 return pet_expr_copy(tree->u.l.cond);
895 }
896
897 /* Given a for loop "tree", return the increment of the induction variable.
898 */
pet_tree_loop_get_inc(__isl_keep pet_tree * tree)899 __isl_give pet_expr *pet_tree_loop_get_inc(__isl_keep pet_tree *tree)
900 {
901 if (!tree)
902 return NULL;
903 if (pet_tree_get_type(tree) != pet_tree_for)
904 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
905 "not a for tree", return NULL);
906
907 return pet_expr_copy(tree->u.l.inc);
908 }
909
910 /* Given a loop tree "tree", return the body.
911 */
pet_tree_loop_get_body(__isl_keep pet_tree * tree)912 __isl_give pet_tree *pet_tree_loop_get_body(__isl_keep pet_tree *tree)
913 {
914 if (!tree)
915 return NULL;
916
917 if (!pet_tree_is_loop(tree))
918 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
919 "not a loop tree", return NULL);
920
921 return pet_tree_copy(tree->u.l.body);
922 }
923
924 /* Call "fn" on each node of "tree", including "tree" itself.
925 *
926 * Return 0 on success and -1 on error, where "fn" returning a negative
927 * value is treated as an error.
928 */
pet_tree_foreach_sub_tree(__isl_keep pet_tree * tree,int (* fn)(__isl_keep pet_tree * tree,void * user),void * user)929 int pet_tree_foreach_sub_tree(__isl_keep pet_tree *tree,
930 int (*fn)(__isl_keep pet_tree *tree, void *user), void *user)
931 {
932 int i;
933
934 if (!tree)
935 return -1;
936
937 if (fn(tree, user) < 0)
938 return -1;
939
940 switch (tree->type) {
941 case pet_tree_error:
942 return -1;
943 case pet_tree_block:
944 for (i = 0; i < tree->u.b.n; ++i)
945 if (pet_tree_foreach_sub_tree(tree->u.b.child[i],
946 fn, user) < 0)
947 return -1;
948 break;
949 case pet_tree_break:
950 case pet_tree_continue:
951 case pet_tree_decl:
952 case pet_tree_decl_init:
953 case pet_tree_expr:
954 case pet_tree_return:
955 break;
956 case pet_tree_if:
957 if (pet_tree_foreach_sub_tree(tree->u.i.then_body,
958 fn, user) < 0)
959 return -1;
960 break;
961 case pet_tree_if_else:
962 if (pet_tree_foreach_sub_tree(tree->u.i.then_body,
963 fn, user) < 0)
964 return -1;
965 if (pet_tree_foreach_sub_tree(tree->u.i.else_body,
966 fn, user) < 0)
967 return -1;
968 break;
969 case pet_tree_while:
970 case pet_tree_for:
971 case pet_tree_infinite_loop:
972 if (pet_tree_foreach_sub_tree(tree->u.l.body, fn, user) < 0)
973 return -1;
974 break;
975 }
976
977 return 0;
978 }
979
980 /* Intermediate data structure for foreach_expr.
981 *
982 * "fn" is the function that needs to be called on each expression.
983 * "user" is the user argument to be passed to "fn".
984 */
985 struct pet_tree_foreach_expr_data {
986 int (*fn)(__isl_keep pet_expr *expr, void *user);
987 void *user;
988 };
989
990 /* Call data->fn on each expression in the "tree" object.
991 * This function is used as a callback to pet_tree_foreach_sub_tree
992 * to implement pet_tree_foreach_expr.
993 *
994 * Return 0 on success and -1 on error, where data->fn returning a negative
995 * value is treated as an error.
996 */
foreach_expr(__isl_keep pet_tree * tree,void * user)997 static int foreach_expr(__isl_keep pet_tree *tree, void *user)
998 {
999 struct pet_tree_foreach_expr_data *data = user;
1000
1001 if (!tree)
1002 return -1;
1003
1004 switch (tree->type) {
1005 case pet_tree_error:
1006 return -1;
1007 case pet_tree_block:
1008 case pet_tree_break:
1009 case pet_tree_continue:
1010 case pet_tree_infinite_loop:
1011 break;
1012 case pet_tree_decl:
1013 if (data->fn(tree->u.d.var, data->user) < 0)
1014 return -1;
1015 break;
1016 case pet_tree_decl_init:
1017 if (data->fn(tree->u.d.var, data->user) < 0)
1018 return -1;
1019 if (data->fn(tree->u.d.init, data->user) < 0)
1020 return -1;
1021 break;
1022 case pet_tree_expr:
1023 case pet_tree_return:
1024 if (data->fn(tree->u.e.expr, data->user) < 0)
1025 return -1;
1026 break;
1027 case pet_tree_if:
1028 if (data->fn(tree->u.i.cond, data->user) < 0)
1029 return -1;
1030 break;
1031 case pet_tree_if_else:
1032 if (data->fn(tree->u.i.cond, data->user) < 0)
1033 return -1;
1034 break;
1035 case pet_tree_while:
1036 if (data->fn(tree->u.l.cond, data->user) < 0)
1037 return -1;
1038 break;
1039 case pet_tree_for:
1040 if (data->fn(tree->u.l.iv, data->user) < 0)
1041 return -1;
1042 if (data->fn(tree->u.l.init, data->user) < 0)
1043 return -1;
1044 if (data->fn(tree->u.l.cond, data->user) < 0)
1045 return -1;
1046 if (data->fn(tree->u.l.inc, data->user) < 0)
1047 return -1;
1048 break;
1049 }
1050
1051 return 0;
1052 }
1053
1054 /* Call "fn" on each top-level expression in the nodes of "tree"
1055 *
1056 * Return 0 on success and -1 on error, where "fn" returning a negative
1057 * value is treated as an error.
1058 *
1059 * We run over all nodes in "tree" and call "fn"
1060 * on each expression in those nodes.
1061 */
pet_tree_foreach_expr(__isl_keep pet_tree * tree,int (* fn)(__isl_keep pet_expr * expr,void * user),void * user)1062 int pet_tree_foreach_expr(__isl_keep pet_tree *tree,
1063 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1064 {
1065 struct pet_tree_foreach_expr_data data = { fn, user };
1066
1067 return pet_tree_foreach_sub_tree(tree, &foreach_expr, &data);
1068 }
1069
1070 /* Intermediate data structure for foreach_access_expr.
1071 *
1072 * "fn" is the function that needs to be called on each access subexpression.
1073 * "user" is the user argument to be passed to "fn".
1074 */
1075 struct pet_tree_foreach_access_expr_data {
1076 int (*fn)(__isl_keep pet_expr *expr, void *user);
1077 void *user;
1078 };
1079
1080 /* Call data->fn on each access subexpression of "expr".
1081 * This function is used as a callback to pet_tree_foreach_expr
1082 * to implement pet_tree_foreach_access_expr.
1083 *
1084 * Return 0 on success and -1 on error, where data->fn returning a negative
1085 * value is treated as an error.
1086 */
foreach_access_expr(__isl_keep pet_expr * expr,void * user)1087 static int foreach_access_expr(__isl_keep pet_expr *expr, void *user)
1088 {
1089 struct pet_tree_foreach_access_expr_data *data = user;
1090
1091 return pet_expr_foreach_access_expr(expr, data->fn, data->user);
1092 }
1093
1094 /* Call "fn" on each access subexpression in the nodes of "tree"
1095 *
1096 * Return 0 on success and -1 on error, where "fn" returning a negative
1097 * value is treated as an error.
1098 *
1099 * We run over all expressions in the nodes of "tree" and call "fn"
1100 * on each access subexpression of those expressions.
1101 */
pet_tree_foreach_access_expr(__isl_keep pet_tree * tree,int (* fn)(__isl_keep pet_expr * expr,void * user),void * user)1102 int pet_tree_foreach_access_expr(__isl_keep pet_tree *tree,
1103 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1104 {
1105 struct pet_tree_foreach_access_expr_data data = { fn, user };
1106
1107 return pet_tree_foreach_expr(tree, &foreach_access_expr, &data);
1108 }
1109
1110 /* Modify all subtrees of "tree", include "tree" itself,
1111 * by calling "fn" on them.
1112 * The subtrees are traversed in depth first preorder.
1113 */
pet_tree_map_top_down(__isl_take pet_tree * tree,__isl_give pet_tree * (* fn)(__isl_take pet_tree * tree,void * user),void * user)1114 __isl_give pet_tree *pet_tree_map_top_down(__isl_take pet_tree *tree,
1115 __isl_give pet_tree *(*fn)(__isl_take pet_tree *tree, void *user),
1116 void *user)
1117 {
1118 int i;
1119
1120 if (!tree)
1121 return NULL;
1122
1123 tree = fn(tree, user);
1124 tree = pet_tree_cow(tree);
1125 if (!tree)
1126 return NULL;
1127
1128 switch (tree->type) {
1129 case pet_tree_error:
1130 return pet_tree_free(tree);
1131 case pet_tree_block:
1132 for (i = 0; i < tree->u.b.n; ++i) {
1133 tree->u.b.child[i] =
1134 pet_tree_map_top_down(tree->u.b.child[i], fn, user);
1135 if (!tree->u.b.child[i])
1136 return pet_tree_free(tree);
1137 }
1138 break;
1139 case pet_tree_break:
1140 case pet_tree_continue:
1141 case pet_tree_decl:
1142 case pet_tree_decl_init:
1143 case pet_tree_expr:
1144 case pet_tree_return:
1145 break;
1146 case pet_tree_if:
1147 tree->u.i.then_body =
1148 pet_tree_map_top_down(tree->u.i.then_body, fn, user);
1149 if (!tree->u.i.then_body)
1150 return pet_tree_free(tree);
1151 break;
1152 case pet_tree_if_else:
1153 tree->u.i.then_body =
1154 pet_tree_map_top_down(tree->u.i.then_body, fn, user);
1155 tree->u.i.else_body =
1156 pet_tree_map_top_down(tree->u.i.else_body, fn, user);
1157 if (!tree->u.i.then_body || !tree->u.i.else_body)
1158 return pet_tree_free(tree);
1159 break;
1160 case pet_tree_while:
1161 case pet_tree_for:
1162 case pet_tree_infinite_loop:
1163 tree->u.l.body =
1164 pet_tree_map_top_down(tree->u.l.body, fn, user);
1165 if (!tree->u.l.body)
1166 return pet_tree_free(tree);
1167 break;
1168 }
1169
1170 return tree;
1171 }
1172
1173 /* Modify all top-level expressions in the nodes of "tree"
1174 * by calling "fn" on them.
1175 */
pet_tree_map_expr(__isl_take pet_tree * tree,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1176 __isl_give pet_tree *pet_tree_map_expr(__isl_take pet_tree *tree,
1177 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1178 void *user)
1179 {
1180 int i;
1181
1182 tree = pet_tree_cow(tree);
1183 if (!tree)
1184 return NULL;
1185
1186 switch (tree->type) {
1187 case pet_tree_error:
1188 return pet_tree_free(tree);
1189 case pet_tree_block:
1190 for (i = 0; i < tree->u.b.n; ++i) {
1191 tree->u.b.child[i] =
1192 pet_tree_map_expr(tree->u.b.child[i], fn, user);
1193 if (!tree->u.b.child[i])
1194 return pet_tree_free(tree);
1195 }
1196 break;
1197 case pet_tree_break:
1198 case pet_tree_continue:
1199 break;
1200 case pet_tree_decl:
1201 tree->u.d.var = fn(tree->u.d.var, user);
1202 if (!tree->u.d.var)
1203 return pet_tree_free(tree);
1204 break;
1205 case pet_tree_decl_init:
1206 tree->u.d.var = fn(tree->u.d.var, user);
1207 tree->u.d.init = fn(tree->u.d.init, user);
1208 if (!tree->u.d.var || !tree->u.d.init)
1209 return pet_tree_free(tree);
1210 break;
1211 case pet_tree_expr:
1212 case pet_tree_return:
1213 tree->u.e.expr = fn(tree->u.e.expr, user);
1214 if (!tree->u.e.expr)
1215 return pet_tree_free(tree);
1216 break;
1217 case pet_tree_if:
1218 tree->u.i.cond = fn(tree->u.i.cond, user);
1219 tree->u.i.then_body =
1220 pet_tree_map_expr(tree->u.i.then_body, fn, user);
1221 if (!tree->u.i.cond || !tree->u.i.then_body)
1222 return pet_tree_free(tree);
1223 break;
1224 case pet_tree_if_else:
1225 tree->u.i.cond = fn(tree->u.i.cond, user);
1226 tree->u.i.then_body =
1227 pet_tree_map_expr(tree->u.i.then_body, fn, user);
1228 tree->u.i.else_body =
1229 pet_tree_map_expr(tree->u.i.else_body, fn, user);
1230 if (!tree->u.i.cond ||
1231 !tree->u.i.then_body || !tree->u.i.else_body)
1232 return pet_tree_free(tree);
1233 break;
1234 case pet_tree_while:
1235 tree->u.l.cond = fn(tree->u.l.cond, user);
1236 tree->u.l.body = pet_tree_map_expr(tree->u.l.body, fn, user);
1237 if (!tree->u.l.cond || !tree->u.l.body)
1238 return pet_tree_free(tree);
1239 break;
1240 case pet_tree_for:
1241 tree->u.l.iv = fn(tree->u.l.iv, user);
1242 tree->u.l.init = fn(tree->u.l.init, user);
1243 tree->u.l.cond = fn(tree->u.l.cond, user);
1244 tree->u.l.inc = fn(tree->u.l.inc, user);
1245 tree->u.l.body = pet_tree_map_expr(tree->u.l.body, fn, user);
1246 if (!tree->u.l.iv || !tree->u.l.init || !tree->u.l.cond ||
1247 !tree->u.l.inc || !tree->u.l.body)
1248 return pet_tree_free(tree);
1249 break;
1250 case pet_tree_infinite_loop:
1251 tree->u.l.body = pet_tree_map_expr(tree->u.l.body, fn, user);
1252 if (!tree->u.l.body)
1253 return pet_tree_free(tree);
1254 break;
1255 }
1256
1257 return tree;
1258 }
1259
1260 /* Intermediate data structure for map_expr.
1261 *
1262 * "map" is a function that modifies subexpressions of a given type.
1263 * "fn" is the function that needs to be called on each of those subexpressions.
1264 * "user" is the user argument to be passed to "fn".
1265 */
1266 struct pet_tree_map_expr_data {
1267 __isl_give pet_expr *(*map)(__isl_take pet_expr *expr,
1268 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr,
1269 void *user), void *user);
1270 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user);
1271 void *user;
1272 };
1273
1274 /* This function is called on each top-level expressions in the nodes
1275 * of a tree. Call data->map to modify subexpressions of the top-level
1276 * expression by calling data->fn on them.
1277 *
1278 * This is a wrapper around data->map for use as a callback
1279 * to pet_tree_map_expr.
1280 */
map_expr(__isl_take pet_expr * expr,void * user)1281 static __isl_give pet_expr *map_expr(__isl_take pet_expr *expr,
1282 void *user)
1283 {
1284 struct pet_tree_map_expr_data *data = user;
1285
1286 return data->map(expr, data->fn, data->user);
1287 }
1288
1289 /* Modify all access subexpressions in the nodes of "tree"
1290 * by calling "fn" on them.
1291 *
1292 * We run over all expressions in the nodes of "tree" and call "fn"
1293 * on each access subexpression of those expressions.
1294 */
pet_tree_map_access_expr(__isl_take pet_tree * tree,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1295 __isl_give pet_tree *pet_tree_map_access_expr(__isl_take pet_tree *tree,
1296 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1297 void *user)
1298 {
1299 struct pet_tree_map_expr_data data = { &pet_expr_map_access, fn, user };
1300
1301 return pet_tree_map_expr(tree, &map_expr, &data);
1302 }
1303
1304 /* Modify all call subexpressions in the nodes of "tree"
1305 * by calling "fn" on them.
1306 *
1307 * We run over all expressions in the nodes of "tree" and call "fn"
1308 * on each call subexpression of those expressions.
1309 */
pet_tree_map_call_expr(__isl_take pet_tree * tree,__isl_give pet_expr * (* fn)(__isl_take pet_expr * expr,void * user),void * user)1310 __isl_give pet_tree *pet_tree_map_call_expr(__isl_take pet_tree *tree,
1311 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1312 void *user)
1313 {
1314 struct pet_tree_map_expr_data data = { &pet_expr_map_call, fn, user };
1315
1316 return pet_tree_map_expr(tree, &map_expr, &data);
1317 }
1318
1319 /* Wrapper around pet_expr_align_params
1320 * for use as a pet_tree_map_expr callback.
1321 */
align_params(__isl_take pet_expr * expr,void * user)1322 static __isl_give pet_expr *align_params(__isl_take pet_expr *expr,
1323 void *user)
1324 {
1325 isl_space *space = user;
1326
1327 return pet_expr_align_params(expr, isl_space_copy(space));
1328 }
1329
1330 /* Add all parameters in "space" to all access relations and index expressions
1331 * in "tree".
1332 */
pet_tree_align_params(__isl_take pet_tree * tree,__isl_take isl_space * space)1333 __isl_give pet_tree *pet_tree_align_params(__isl_take pet_tree *tree,
1334 __isl_take isl_space *space)
1335 {
1336 tree = pet_tree_map_expr(tree, &align_params, space);
1337 isl_space_free(space);
1338 return tree;
1339 }
1340
1341 /* Wrapper around pet_expr_add_ref_ids
1342 * for use as a pet_tree_map_expr callback.
1343 */
add_ref_ids(__isl_take pet_expr * expr,void * user)1344 static __isl_give pet_expr *add_ref_ids(__isl_take pet_expr *expr, void *user)
1345 {
1346 int *n_ref = user;
1347
1348 return pet_expr_add_ref_ids(expr, n_ref);
1349 }
1350
1351 /* Add reference identifiers to all access expressions in "tree".
1352 * "n_ref" points to an integer that contains the sequence number
1353 * of the next reference.
1354 */
pet_tree_add_ref_ids(__isl_take pet_tree * tree,int * n_ref)1355 __isl_give pet_tree *pet_tree_add_ref_ids(__isl_take pet_tree *tree,
1356 int *n_ref)
1357 {
1358 return pet_tree_map_expr(tree, &add_ref_ids, n_ref);
1359 }
1360
1361 /* Wrapper around pet_expr_anonymize
1362 * for use as a pet_tree_map_expr callback.
1363 */
anonymize(__isl_take pet_expr * expr,void * user)1364 static __isl_give pet_expr *anonymize(__isl_take pet_expr *expr, void *user)
1365 {
1366 return pet_expr_anonymize(expr);
1367 }
1368
1369 /* Reset the user pointer on all parameter and tuple ids in "tree".
1370 */
pet_tree_anonymize(__isl_take pet_tree * tree)1371 __isl_give pet_tree *pet_tree_anonymize(__isl_take pet_tree *tree)
1372 {
1373 return pet_tree_map_expr(tree, &anonymize, NULL);
1374 }
1375
1376 /* Arguments to be passed to pet_expr_gist from the gist wrapper.
1377 */
1378 struct pet_tree_gist_data {
1379 isl_set *domain;
1380 isl_union_map *value_bounds;
1381 };
1382
1383 /* Wrapper around pet_expr_gist for use as a pet_tree_map_expr callback.
1384 */
gist(__isl_take pet_expr * expr,void * user)1385 static __isl_give pet_expr *gist(__isl_take pet_expr *expr, void *user)
1386 {
1387 struct pet_tree_gist_data *data = user;
1388
1389 return pet_expr_gist(expr, data->domain, data->value_bounds);
1390 }
1391
1392 /* Compute the gist of all access relations and index expressions inside
1393 * "tree" based on the constraints on the parameters specified by "context"
1394 * and the constraints on the values of nested accesses specified
1395 * by "value_bounds".
1396 */
pet_tree_gist(__isl_take pet_tree * tree,__isl_keep isl_set * context,__isl_keep isl_union_map * value_bounds)1397 __isl_give pet_tree *pet_tree_gist(__isl_take pet_tree *tree,
1398 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
1399 {
1400 struct pet_tree_gist_data data = { context, value_bounds };
1401
1402 return pet_tree_map_expr(tree, &gist, &data);
1403 }
1404
1405 /* Return 1 if the two pet_tree objects are equivalent.
1406 *
1407 * We ignore the locations of the trees.
1408 */
pet_tree_is_equal(__isl_keep pet_tree * tree1,__isl_keep pet_tree * tree2)1409 int pet_tree_is_equal(__isl_keep pet_tree *tree1, __isl_keep pet_tree *tree2)
1410 {
1411 int i;
1412 int equal;
1413
1414 if (!tree1 || !tree2)
1415 return 0;
1416
1417 if (tree1 == tree2)
1418 return 1;
1419
1420 if (tree1->type != tree2->type)
1421 return 0;
1422 if (tree1->label != tree2->label)
1423 return 0;
1424
1425 switch (tree1->type) {
1426 case pet_tree_error:
1427 return -1;
1428 case pet_tree_block:
1429 if (tree1->u.b.block != tree2->u.b.block)
1430 return 0;
1431 if (tree1->u.b.n != tree2->u.b.n)
1432 return 0;
1433 for (i = 0; i < tree1->u.b.n; ++i) {
1434 equal = pet_tree_is_equal(tree1->u.b.child[i],
1435 tree2->u.b.child[i]);
1436 if (equal < 0 || !equal)
1437 return equal;
1438 }
1439 break;
1440 case pet_tree_break:
1441 case pet_tree_continue:
1442 break;
1443 case pet_tree_decl:
1444 return pet_expr_is_equal(tree1->u.d.var, tree2->u.d.var);
1445 case pet_tree_decl_init:
1446 equal = pet_expr_is_equal(tree1->u.d.var, tree2->u.d.var);
1447 if (equal < 0 || !equal)
1448 return equal;
1449 return pet_expr_is_equal(tree1->u.d.init, tree2->u.d.init);
1450 case pet_tree_expr:
1451 case pet_tree_return:
1452 return pet_expr_is_equal(tree1->u.e.expr, tree2->u.e.expr);
1453 case pet_tree_for:
1454 if (tree1->u.l.declared != tree2->u.l.declared)
1455 return 0;
1456 equal = pet_expr_is_equal(tree1->u.l.iv, tree2->u.l.iv);
1457 if (equal < 0 || !equal)
1458 return equal;
1459 equal = pet_expr_is_equal(tree1->u.l.init, tree2->u.l.init);
1460 if (equal < 0 || !equal)
1461 return equal;
1462 equal = pet_expr_is_equal(tree1->u.l.cond, tree2->u.l.cond);
1463 if (equal < 0 || !equal)
1464 return equal;
1465 equal = pet_expr_is_equal(tree1->u.l.inc, tree2->u.l.inc);
1466 if (equal < 0 || !equal)
1467 return equal;
1468 return pet_tree_is_equal(tree1->u.l.body, tree2->u.l.body);
1469 case pet_tree_while:
1470 equal = pet_expr_is_equal(tree1->u.l.cond, tree2->u.l.cond);
1471 if (equal < 0 || !equal)
1472 return equal;
1473 return pet_tree_is_equal(tree1->u.l.body, tree2->u.l.body);
1474 case pet_tree_infinite_loop:
1475 return pet_tree_is_equal(tree1->u.l.body, tree2->u.l.body);
1476 case pet_tree_if:
1477 equal = pet_expr_is_equal(tree1->u.i.cond, tree2->u.i.cond);
1478 if (equal < 0 || !equal)
1479 return equal;
1480 return pet_tree_is_equal(tree1->u.i.then_body,
1481 tree2->u.i.then_body);
1482 case pet_tree_if_else:
1483 equal = pet_expr_is_equal(tree1->u.i.cond, tree2->u.i.cond);
1484 if (equal < 0 || !equal)
1485 return equal;
1486 equal = pet_tree_is_equal(tree1->u.i.then_body,
1487 tree2->u.i.then_body);
1488 if (equal < 0 || !equal)
1489 return equal;
1490 return pet_tree_is_equal(tree1->u.i.else_body,
1491 tree2->u.i.else_body);
1492 }
1493
1494 return 1;
1495 }
1496
1497 /* Is "tree" an expression tree that performs the operation "type"?
1498 */
pet_tree_is_op_of_type(__isl_keep pet_tree * tree,enum pet_op_type type)1499 static int pet_tree_is_op_of_type(__isl_keep pet_tree *tree,
1500 enum pet_op_type type)
1501 {
1502 if (!tree)
1503 return 0;
1504 if (tree->type != pet_tree_expr)
1505 return 0;
1506 if (pet_expr_get_type(tree->u.e.expr) != pet_expr_op)
1507 return 0;
1508 return pet_expr_op_get_type(tree->u.e.expr) == type;
1509 }
1510
1511 /* Is "tree" an expression tree that performs a kill operation?
1512 */
pet_tree_is_kill(__isl_keep pet_tree * tree)1513 int pet_tree_is_kill(__isl_keep pet_tree *tree)
1514 {
1515 return pet_tree_is_op_of_type(tree, pet_op_kill);
1516 }
1517
1518 /* Is "tree" an expression tree that performs an assignment operation?
1519 */
pet_tree_is_assign(__isl_keep pet_tree * tree)1520 int pet_tree_is_assign(__isl_keep pet_tree *tree)
1521 {
1522 return pet_tree_is_op_of_type(tree, pet_op_assign);
1523 }
1524
1525 /* Is "tree" an expression tree that performs an assume operation?
1526 */
pet_tree_is_assume(__isl_keep pet_tree * tree)1527 int pet_tree_is_assume(__isl_keep pet_tree *tree)
1528 {
1529 return pet_tree_is_op_of_type(tree, pet_op_assume);
1530 }
1531
1532 /* Is "tree" an expression tree that performs an assume operation
1533 * such that the assumed expression is affine?
1534 */
pet_tree_is_affine_assume(__isl_keep pet_tree * tree)1535 isl_bool pet_tree_is_affine_assume(__isl_keep pet_tree *tree)
1536 {
1537 if (!pet_tree_is_assume(tree))
1538 return isl_bool_false;
1539 return pet_expr_is_affine(tree->u.e.expr->args[0]);
1540 }
1541
1542 /* Given a tree that represent an assume operation expression
1543 * with an access as argument (possibly an affine expression),
1544 * return the index expression of that access.
1545 */
pet_tree_assume_get_index(__isl_keep pet_tree * tree)1546 __isl_give isl_multi_pw_aff *pet_tree_assume_get_index(
1547 __isl_keep pet_tree *tree)
1548 {
1549 if (!tree)
1550 return NULL;
1551 if (!pet_tree_is_assume(tree))
1552 isl_die(pet_tree_get_ctx(tree), isl_error_invalid,
1553 "not an assume tree", return NULL);
1554 return pet_expr_access_get_index(tree->u.e.expr->args[0]);
1555 }
1556
1557 /* Internal data structure for pet_tree_writes.
1558 * "id" is the identifier that we are looking for.
1559 * "writes" is set if we have found the identifier being written to.
1560 */
1561 struct pet_tree_writes_data {
1562 isl_id *id;
1563 int writes;
1564 };
1565
1566 /* Check if expr writes to data->id.
1567 * If so, set data->writes and abort the search.
1568 */
check_write(__isl_keep pet_expr * expr,void * user)1569 static int check_write(__isl_keep pet_expr *expr, void *user)
1570 {
1571 struct pet_tree_writes_data *data = user;
1572
1573 data->writes = pet_expr_writes(expr, data->id);
1574 if (data->writes < 0 || data->writes)
1575 return -1;
1576
1577 return 0;
1578 }
1579
1580 /* Is there any write access in "tree" that accesses "id"?
1581 */
pet_tree_writes(__isl_keep pet_tree * tree,__isl_keep isl_id * id)1582 int pet_tree_writes(__isl_keep pet_tree *tree, __isl_keep isl_id *id)
1583 {
1584 struct pet_tree_writes_data data;
1585
1586 data.id = id;
1587 data.writes = 0;
1588 if (pet_tree_foreach_expr(tree, &check_write, &data) < 0 &&
1589 !data.writes)
1590 return -1;
1591
1592 return data.writes;
1593 }
1594
1595 /* Wrapper around pet_expr_update_domain
1596 * for use as a pet_tree_map_expr callback.
1597 */
update_domain(__isl_take pet_expr * expr,void * user)1598 static __isl_give pet_expr *update_domain(__isl_take pet_expr *expr, void *user)
1599 {
1600 isl_multi_pw_aff *update = user;
1601
1602 return pet_expr_update_domain(expr, isl_multi_pw_aff_copy(update));
1603 }
1604
1605 /* Modify all access relations in "tree" by precomposing them with
1606 * the given iteration space transformation.
1607 */
pet_tree_update_domain(__isl_take pet_tree * tree,__isl_take isl_multi_pw_aff * update)1608 __isl_give pet_tree *pet_tree_update_domain(__isl_take pet_tree *tree,
1609 __isl_take isl_multi_pw_aff *update)
1610 {
1611 tree = pet_tree_map_expr(tree, &update_domain, update);
1612 isl_multi_pw_aff_free(update);
1613 return tree;
1614 }
1615
1616 /* Does "tree" contain a continue or break node (not contained in any loop
1617 * subtree of "tree")?
1618 */
pet_tree_has_continue_or_break(__isl_keep pet_tree * tree)1619 int pet_tree_has_continue_or_break(__isl_keep pet_tree *tree)
1620 {
1621 int i;
1622 int found;
1623
1624 if (!tree)
1625 return -1;
1626
1627 switch (tree->type) {
1628 case pet_tree_error:
1629 return -1;
1630 case pet_tree_continue:
1631 case pet_tree_break:
1632 return 1;
1633 case pet_tree_decl:
1634 case pet_tree_decl_init:
1635 case pet_tree_expr:
1636 case pet_tree_return:
1637 case pet_tree_for:
1638 case pet_tree_while:
1639 case pet_tree_infinite_loop:
1640 return 0;
1641 case pet_tree_block:
1642 for (i = 0; i < tree->u.b.n; ++i) {
1643 found =
1644 pet_tree_has_continue_or_break(tree->u.b.child[i]);
1645 if (found < 0 || found)
1646 return found;
1647 }
1648 return 0;
1649 case pet_tree_if:
1650 return pet_tree_has_continue_or_break(tree->u.i.then_body);
1651 case pet_tree_if_else:
1652 found = pet_tree_has_continue_or_break(tree->u.i.then_body);
1653 if (found < 0 || found)
1654 return found;
1655 return pet_tree_has_continue_or_break(tree->u.i.else_body);
1656 }
1657 }
1658
print_indent(int indent)1659 static void print_indent(int indent)
1660 {
1661 fprintf(stderr, "%*s", indent, "");
1662 }
1663
pet_tree_dump_with_indent(__isl_keep pet_tree * tree,int indent)1664 void pet_tree_dump_with_indent(__isl_keep pet_tree *tree, int indent)
1665 {
1666 int i;
1667
1668 if (!tree)
1669 return;
1670
1671 print_indent(indent);
1672 fprintf(stderr, "%s\n", pet_tree_type_str(tree->type));
1673 print_indent(indent);
1674 fprintf(stderr, "line: %d\n", pet_loc_get_line(tree->loc));
1675 print_indent(indent);
1676 fprintf(stderr, "start: %d\n", pet_loc_get_start(tree->loc));
1677 print_indent(indent);
1678 fprintf(stderr, "end: %d\n", pet_loc_get_end(tree->loc));
1679 if (tree->label) {
1680 print_indent(indent);
1681 fprintf(stderr, "label: ");
1682 isl_id_dump(tree->label);
1683 }
1684 switch (tree->type) {
1685 case pet_tree_block:
1686 print_indent(indent);
1687 fprintf(stderr, "block: %d\n", tree->u.b.block);
1688 for (i = 0; i < tree->u.b.n; ++i)
1689 pet_tree_dump_with_indent(tree->u.b.child[i],
1690 indent + 2);
1691 break;
1692 case pet_tree_expr:
1693 pet_expr_dump_with_indent(tree->u.e.expr, indent);
1694 break;
1695 case pet_tree_return:
1696 print_indent(indent);
1697 fprintf(stderr, "return:\n");
1698 pet_expr_dump_with_indent(tree->u.e.expr, indent);
1699 break;
1700 case pet_tree_break:
1701 case pet_tree_continue:
1702 break;
1703 case pet_tree_decl:
1704 case pet_tree_decl_init:
1705 print_indent(indent);
1706 fprintf(stderr, "var:\n");
1707 pet_expr_dump_with_indent(tree->u.d.var, indent + 2);
1708 if (tree->type != pet_tree_decl_init)
1709 break;
1710 print_indent(indent);
1711 fprintf(stderr, "init:\n");
1712 pet_expr_dump_with_indent(tree->u.d.init, indent + 2);
1713 break;
1714 case pet_tree_if:
1715 case pet_tree_if_else:
1716 print_indent(indent);
1717 fprintf(stderr, "condition:\n");
1718 pet_expr_dump_with_indent(tree->u.i.cond, indent + 2);
1719 print_indent(indent);
1720 fprintf(stderr, "then:\n");
1721 pet_tree_dump_with_indent(tree->u.i.then_body, indent + 2);
1722 if (tree->type != pet_tree_if_else)
1723 break;
1724 print_indent(indent);
1725 fprintf(stderr, "else:\n");
1726 pet_tree_dump_with_indent(tree->u.i.else_body, indent + 2);
1727 break;
1728 case pet_tree_for:
1729 print_indent(indent);
1730 fprintf(stderr, "declared: %d\n", tree->u.l.declared);
1731 print_indent(indent);
1732 fprintf(stderr, "var:\n");
1733 pet_expr_dump_with_indent(tree->u.l.iv, indent + 2);
1734 print_indent(indent);
1735 fprintf(stderr, "init:\n");
1736 pet_expr_dump_with_indent(tree->u.l.init, indent + 2);
1737 print_indent(indent);
1738 fprintf(stderr, "inc:\n");
1739 pet_expr_dump_with_indent(tree->u.l.inc, indent + 2);
1740 case pet_tree_while:
1741 print_indent(indent);
1742 fprintf(stderr, "condition:\n");
1743 pet_expr_dump_with_indent(tree->u.l.cond, indent + 2);
1744 case pet_tree_infinite_loop:
1745 print_indent(indent);
1746 fprintf(stderr, "body:\n");
1747 pet_tree_dump_with_indent(tree->u.l.body, indent + 2);
1748 break;
1749 case pet_tree_error:
1750 print_indent(indent);
1751 fprintf(stderr, "ERROR\n");
1752 break;
1753 }
1754 }
1755
pet_tree_dump(__isl_keep pet_tree * tree)1756 void pet_tree_dump(__isl_keep pet_tree *tree)
1757 {
1758 pet_tree_dump_with_indent(tree, 0);
1759 }
1760