2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
41 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
43 static const char *type_str
[] = {
44 [pet_tree_block
] = "block",
45 [pet_tree_break
] = "break",
46 [pet_tree_continue
] = "continue",
47 [pet_tree_decl
] = "declaration",
48 [pet_tree_decl_init
] = "declaration-init",
49 [pet_tree_expr
] = "expression",
50 [pet_tree_for
] = "for",
51 [pet_tree_infinite_loop
] = "infinite-loop",
53 [pet_tree_if_else
] = "if-else",
54 [pet_tree_while
] = "while",
57 /* Return a textual representation of the type "type".
59 const char *pet_tree_type_str(enum pet_tree_type type
)
63 return type_str
[type
];
66 /* Extract a type from its textual representation "str".
68 enum pet_tree_type
pet_tree_str_type(const char *str
)
72 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
73 if (!strcmp(type_str
[i
], str
))
76 return pet_tree_error
;
79 /* Return a new pet_tree of the given type.
81 * The location is initializaed to pet_loc_dummy.
83 __isl_give pet_tree
*pet_tree_alloc(isl_ctx
*ctx
, enum pet_tree_type type
)
87 tree
= isl_calloc_type(ctx
, struct pet_tree
);
95 tree
->loc
= &pet_loc_dummy
;
100 /* Return a new pet_tree representing the declaration (without initialization)
101 * of the variable "var".
103 __isl_give pet_tree
*pet_tree_new_decl(__isl_take pet_expr
*var
)
110 ctx
= pet_expr_get_ctx(var
);
111 tree
= pet_tree_alloc(ctx
, pet_tree_decl
);
123 /* Return a new pet_tree representing the declaration of the variable "var"
124 * with initial value "init".
126 __isl_give pet_tree
*pet_tree_new_decl_init(__isl_take pet_expr
*var
,
127 __isl_take pet_expr
*init
)
134 ctx
= pet_expr_get_ctx(var
);
135 tree
= pet_tree_alloc(ctx
, pet_tree_decl_init
);
140 tree
->u
.d
.init
= init
;
149 /* Return a new pet_tree representing the expression "expr".
151 __isl_give pet_tree
*pet_tree_new_expr(__isl_take pet_expr
*expr
)
158 ctx
= pet_expr_get_ctx(expr
);
159 tree
= pet_tree_alloc(ctx
, pet_tree_expr
);
163 tree
->u
.e
.expr
= expr
;
171 /* Return a new pet_tree representing an intially empty sequence
172 * of trees with room for "n" trees.
173 * "block" indicates whether the sequence has its own scope.
175 __isl_give pet_tree
*pet_tree_new_block(isl_ctx
*ctx
, int block
, int n
)
179 tree
= pet_tree_alloc(ctx
, pet_tree_block
);
182 tree
->u
.b
.block
= block
;
185 tree
->u
.b
.child
= isl_calloc_array(ctx
, pet_tree
*, n
);
186 if (n
&& !tree
->u
.b
.child
)
187 return pet_tree_free(tree
);
192 /* Return a new pet_tree representing a break statement.
194 __isl_give pet_tree
*pet_tree_new_break(isl_ctx
*ctx
)
196 return pet_tree_alloc(ctx
, pet_tree_break
);
199 /* Return a new pet_tree representing a continue statement.
201 __isl_give pet_tree
*pet_tree_new_continue(isl_ctx
*ctx
)
203 return pet_tree_alloc(ctx
, pet_tree_continue
);
206 /* Return a new pet_tree representing a for loop
207 * with induction variable "iv", initial value for the induction
208 * variable "init", loop condition "cond", induction variable increment "inc"
209 * and loop body "body". "declared" indicates whether the induction variable
210 * is declared by the loop.
212 * The location of the loop is initialized to that of the body.
214 __isl_give pet_tree
*pet_tree_new_for(int declared
,
215 __isl_take pet_expr
*iv
, __isl_take pet_expr
*init
,
216 __isl_take pet_expr
*cond
, __isl_take pet_expr
*inc
,
217 __isl_take pet_tree
*body
)
222 if (!iv
|| !init
|| !cond
|| !inc
|| !body
)
224 ctx
= pet_tree_get_ctx(body
);
225 tree
= pet_tree_alloc(ctx
, pet_tree_for
);
229 tree
->u
.l
.declared
= declared
;
231 tree
->u
.l
.init
= init
;
232 tree
->u
.l
.cond
= cond
;
234 tree
->u
.l
.body
= body
;
235 tree
->loc
= pet_tree_get_loc(body
);
237 return pet_tree_free(tree
);
249 /* Return a new pet_tree representing a while loop
250 * with loop condition "cond" and loop body "body".
252 * The location of the loop is initialized to that of the body.
254 __isl_give pet_tree
*pet_tree_new_while(__isl_take pet_expr
*cond
,
255 __isl_take pet_tree
*body
)
262 ctx
= pet_tree_get_ctx(body
);
263 tree
= pet_tree_alloc(ctx
, pet_tree_while
);
267 tree
->u
.l
.cond
= cond
;
268 tree
->u
.l
.body
= body
;
269 tree
->loc
= pet_tree_get_loc(body
);
271 return pet_tree_free(tree
);
280 /* Return a new pet_tree representing an infinite loop
281 * with loop body "body".
283 * The location of the loop is initialized to that of the body.
285 __isl_give pet_tree
*pet_tree_new_infinite_loop(__isl_take pet_tree
*body
)
292 ctx
= pet_tree_get_ctx(body
);
293 tree
= pet_tree_alloc(ctx
, pet_tree_infinite_loop
);
295 return pet_tree_free(body
);
297 tree
->u
.l
.body
= body
;
298 tree
->loc
= pet_tree_get_loc(body
);
300 return pet_tree_free(tree
);
305 /* Return a new pet_tree representing an if statement
306 * with condition "cond" and then branch "then_body".
308 * The location of the if statement is initialized to that of the body.
310 __isl_give pet_tree
*pet_tree_new_if(__isl_take pet_expr
*cond
,
311 __isl_take pet_tree
*then_body
)
316 if (!cond
|| !then_body
)
318 ctx
= pet_tree_get_ctx(then_body
);
319 tree
= pet_tree_alloc(ctx
, pet_tree_if
);
323 tree
->u
.i
.cond
= cond
;
324 tree
->u
.i
.then_body
= then_body
;
325 tree
->loc
= pet_tree_get_loc(then_body
);
327 return pet_tree_free(tree
);
332 pet_tree_free(then_body
);
336 /* Return a new pet_tree representing an if statement
337 * with condition "cond", then branch "then_body" and else branch "else_body".
339 * The location of the if statement is initialized to cover
340 * those of the bodies.
342 __isl_give pet_tree
*pet_tree_new_if_else(__isl_take pet_expr
*cond
,
343 __isl_take pet_tree
*then_body
, __isl_take pet_tree
*else_body
)
348 if (!cond
|| !then_body
|| !else_body
)
350 ctx
= pet_tree_get_ctx(then_body
);
351 tree
= pet_tree_alloc(ctx
, pet_tree_if_else
);
355 tree
->u
.i
.cond
= cond
;
356 tree
->u
.i
.then_body
= then_body
;
357 tree
->u
.i
.else_body
= else_body
;
358 tree
->loc
= pet_tree_get_loc(then_body
);
359 tree
->loc
= pet_loc_update_start_end_from_loc(tree
->loc
,
362 return pet_tree_free(tree
);
367 pet_tree_free(then_body
);
368 pet_tree_free(else_body
);
372 /* Return an independent duplicate of "tree".
374 static __isl_give pet_tree
*pet_tree_dup(__isl_keep pet_tree
*tree
)
382 switch (tree
->type
) {
386 dup
= pet_tree_new_block(tree
->ctx
, tree
->u
.b
.block
,
388 for (i
= 0; i
< tree
->u
.b
.n
; ++i
)
389 dup
= pet_tree_block_add_child(dup
,
390 pet_tree_copy(tree
->u
.b
.child
[i
]));
393 dup
= pet_tree_new_break(tree
->ctx
);
395 case pet_tree_continue
:
396 dup
= pet_tree_new_continue(tree
->ctx
);
399 dup
= pet_tree_new_decl(pet_expr_copy(tree
->u
.d
.var
));
401 case pet_tree_decl_init
:
402 dup
= pet_tree_new_decl_init(pet_expr_copy(tree
->u
.d
.var
),
403 pet_expr_copy(tree
->u
.d
.init
));
406 dup
= pet_tree_new_expr(pet_expr_copy(tree
->u
.e
.expr
));
409 dup
= pet_tree_new_for(tree
->u
.l
.declared
,
410 pet_expr_copy(tree
->u
.l
.iv
), pet_expr_copy(tree
->u
.l
.init
),
411 pet_expr_copy(tree
->u
.l
.cond
), pet_expr_copy(tree
->u
.l
.inc
),
412 pet_tree_copy(tree
->u
.l
.body
));
415 dup
= pet_tree_new_while(pet_expr_copy(tree
->u
.l
.cond
),
416 pet_tree_copy(tree
->u
.l
.body
));
418 case pet_tree_infinite_loop
:
419 dup
= pet_tree_new_infinite_loop(pet_tree_copy(tree
->u
.l
.body
));
422 dup
= pet_tree_new_if(pet_expr_copy(tree
->u
.i
.cond
),
423 pet_tree_copy(tree
->u
.i
.then_body
));
425 case pet_tree_if_else
:
426 dup
= pet_tree_new_if_else(pet_expr_copy(tree
->u
.i
.cond
),
427 pet_tree_copy(tree
->u
.i
.then_body
),
428 pet_tree_copy(tree
->u
.i
.else_body
));
434 pet_loc_free(dup
->loc
);
435 dup
->loc
= pet_loc_copy(tree
->loc
);
437 return pet_tree_free(dup
);
439 dup
->label
= isl_id_copy(tree
->label
);
441 return pet_tree_free(dup
);
447 /* Return a pet_tree that is equal to "tree" and that has only one reference.
449 __isl_give pet_tree
*pet_tree_cow(__isl_take pet_tree
*tree
)
457 return pet_tree_dup(tree
);
460 /* Return an extra reference to "tree".
462 __isl_give pet_tree
*pet_tree_copy(__isl_keep pet_tree
*tree
)
471 /* Free a reference to "tree".
473 __isl_null pet_tree
*pet_tree_free(__isl_take pet_tree
*tree
)
482 pet_loc_free(tree
->loc
);
483 isl_id_free(tree
->label
);
485 switch (tree
->type
) {
489 for (i
= 0; i
< tree
->u
.b
.n
; ++i
)
490 pet_tree_free(tree
->u
.b
.child
[i
]);
491 free(tree
->u
.b
.child
);
494 case pet_tree_continue
:
496 case pet_tree_decl_init
:
497 pet_expr_free(tree
->u
.d
.init
);
499 pet_expr_free(tree
->u
.d
.var
);
502 pet_expr_free(tree
->u
.e
.expr
);
505 pet_expr_free(tree
->u
.l
.iv
);
506 pet_expr_free(tree
->u
.l
.init
);
507 pet_expr_free(tree
->u
.l
.inc
);
509 pet_expr_free(tree
->u
.l
.cond
);
510 case pet_tree_infinite_loop
:
511 pet_tree_free(tree
->u
.l
.body
);
513 case pet_tree_if_else
:
514 pet_tree_free(tree
->u
.i
.else_body
);
516 pet_expr_free(tree
->u
.i
.cond
);
517 pet_tree_free(tree
->u
.i
.then_body
);
521 isl_ctx_deref(tree
->ctx
);
526 /* Return the isl_ctx in which "tree" was created.
528 isl_ctx
*pet_tree_get_ctx(__isl_keep pet_tree
*tree
)
530 return tree
? tree
->ctx
: NULL
;
533 /* Return the location of "tree".
535 __isl_give pet_loc
*pet_tree_get_loc(__isl_keep pet_tree
*tree
)
537 return tree
? pet_loc_copy(tree
->loc
) : NULL
;
540 /* Return the type of "tree".
542 enum pet_tree_type
pet_tree_get_type(__isl_keep pet_tree
*tree
)
545 return pet_tree_error
;
550 /* Replace the location of "tree" by "loc".
552 __isl_give pet_tree
*pet_tree_set_loc(__isl_take pet_tree
*tree
,
553 __isl_take pet_loc
*loc
)
555 tree
= pet_tree_cow(tree
);
559 pet_loc_free(tree
->loc
);
569 /* Replace the label of "tree" by "label".
571 __isl_give pet_tree
*pet_tree_set_label(__isl_take pet_tree
*tree
,
572 __isl_take isl_id
*label
)
574 tree
= pet_tree_cow(tree
);
578 isl_id_free(tree
->label
);
584 return pet_tree_free(tree
);
587 /* Given an expression tree "tree", return the associated expression.
589 __isl_give pet_expr
*pet_tree_expr_get_expr(__isl_keep pet_tree
*tree
)
593 if (pet_tree_get_type(tree
) != pet_tree_expr
)
594 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
595 "not an expression tree", return NULL
);
597 return pet_expr_copy(tree
->u
.e
.expr
);
600 /* Given a block tree "tree", return the number of children in the sequence.
602 int pet_tree_block_n_child(__isl_keep pet_tree
*tree
)
606 if (pet_tree_get_type(tree
) != pet_tree_block
)
607 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
608 "not a block tree", return -1);
613 /* Add "child" to the sequence of trees represented by "block".
615 * Update the location of "block" to include that of "child".
617 __isl_give pet_tree
*pet_tree_block_add_child(__isl_take pet_tree
*block
,
618 __isl_take pet_tree
*child
)
620 block
= pet_tree_cow(block
);
621 if (!block
|| !child
)
623 if (block
->type
!= pet_tree_block
)
624 isl_die(pet_tree_get_ctx(block
), isl_error_invalid
,
625 "not a block tree", goto error
);
626 if (block
->u
.b
.n
>= block
->u
.b
.max
)
627 isl_die(pet_tree_get_ctx(block
), isl_error_invalid
,
628 "out of space in block", goto error
);
630 block
->loc
= pet_loc_update_start_end_from_loc(block
->loc
, child
->loc
);
631 block
->u
.b
.child
[block
->u
.b
.n
++] = child
;
634 return pet_tree_free(block
);
638 pet_tree_free(block
);
639 pet_tree_free(child
);
643 /* Given a block tree "tree", return the child at position "pos".
645 __isl_give pet_tree
*pet_tree_block_get_child(__isl_keep pet_tree
*tree
,
650 if (pet_tree_get_type(tree
) != pet_tree_block
)
651 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
652 "not a block tree", return NULL
);
653 if (pos
< 0 || pos
>= tree
->u
.b
.n
)
654 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
655 "position out of bounds", return NULL
);
657 return pet_tree_copy(tree
->u
.b
.child
[pos
]);
660 /* Does "tree" represent a declaration (with or without initialization?
662 int pet_tree_is_decl(__isl_keep pet_tree
*tree
)
667 switch (pet_tree_get_type(tree
)) {
669 case pet_tree_decl_init
:
676 /* Given a declaration tree "tree", return the variable that is being
679 __isl_give pet_expr
*pet_tree_decl_get_var(__isl_keep pet_tree
*tree
)
683 if (!pet_tree_is_decl(tree
))
684 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
685 "not a decl tree", return NULL
);
687 return pet_expr_copy(tree
->u
.d
.var
);
690 /* Given a declaration tree with initialization "tree",
691 * return the initial value of the declared variable.
693 __isl_give pet_expr
*pet_tree_decl_get_init(__isl_keep pet_tree
*tree
)
697 if (pet_tree_get_type(tree
) != pet_tree_decl_init
)
698 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
699 "not a decl_init tree", return NULL
);
701 return pet_expr_copy(tree
->u
.d
.init
);
704 /* Given an if tree "tree", return the if condition.
706 __isl_give pet_expr
*pet_tree_if_get_cond(__isl_keep pet_tree
*tree
)
708 enum pet_tree_type type
;
712 type
= pet_tree_get_type(tree
);
713 if (type
!= pet_tree_if
&& type
!= pet_tree_if_else
)
714 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
715 "not an if tree", return NULL
);
717 return pet_expr_copy(tree
->u
.i
.cond
);
720 /* Given an if tree "tree", return the body of the then branch.
722 __isl_give pet_tree
*pet_tree_if_get_then(__isl_keep pet_tree
*tree
)
724 enum pet_tree_type type
;
728 type
= pet_tree_get_type(tree
);
729 if (type
!= pet_tree_if
&& type
!= pet_tree_if_else
)
730 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
731 "not an if tree", return NULL
);
733 return pet_tree_copy(tree
->u
.i
.then_body
);
736 /* Given an if tree with an else branch "tree",
737 * return the body of that else branch.
739 __isl_give pet_tree
*pet_tree_if_get_else(__isl_keep pet_tree
*tree
)
743 if (pet_tree_get_type(tree
) != pet_tree_if_else
)
744 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
745 "not an if tree with an else branch", return NULL
);
747 return pet_tree_copy(tree
->u
.i
.else_body
);
750 /* Does "tree" represent some type of loop?
752 int pet_tree_is_loop(__isl_keep pet_tree
*tree
)
757 switch (pet_tree_get_type(tree
)) {
759 case pet_tree_infinite_loop
:
767 /* Given a for loop "tree", return the induction variable.
769 __isl_give pet_expr
*pet_tree_loop_get_var(__isl_keep pet_tree
*tree
)
773 if (pet_tree_get_type(tree
) != pet_tree_for
)
774 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
775 "not a for tree", return NULL
);
777 return pet_expr_copy(tree
->u
.l
.iv
);
780 /* Given a for loop "tree", return the initial value of the induction variable.
782 __isl_give pet_expr
*pet_tree_loop_get_init(__isl_keep pet_tree
*tree
)
786 if (pet_tree_get_type(tree
) != pet_tree_for
)
787 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
788 "not a for tree", return NULL
);
790 return pet_expr_copy(tree
->u
.l
.init
);
793 /* Given a loop "tree", return the loop condition.
795 * For an infinite loop, the loop condition always holds,
796 * so we simply return "1".
798 __isl_give pet_expr
*pet_tree_loop_get_cond(__isl_keep pet_tree
*tree
)
800 enum pet_tree_type type
;
804 type
= pet_tree_get_type(tree
);
805 if (type
== pet_tree_infinite_loop
)
806 return pet_expr_new_int(isl_val_one(pet_tree_get_ctx(tree
)));
807 if (type
!= pet_tree_for
&& type
!= pet_tree_while
)
808 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
809 "not a for or while tree", return NULL
);
811 return pet_expr_copy(tree
->u
.l
.cond
);
814 /* Given a for loop "tree", return the increment of the induction variable.
816 __isl_give pet_expr
*pet_tree_loop_get_inc(__isl_keep pet_tree
*tree
)
820 if (pet_tree_get_type(tree
) != pet_tree_for
)
821 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
822 "not a for tree", return NULL
);
824 return pet_expr_copy(tree
->u
.l
.inc
);
827 /* Given a loop tree "tree", return the body.
829 __isl_give pet_tree
*pet_tree_loop_get_body(__isl_keep pet_tree
*tree
)
834 if (!pet_tree_is_loop(tree
))
835 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
836 "not a loop tree", return NULL
);
838 return pet_tree_copy(tree
->u
.l
.body
);
841 /* Call "fn" on each node of "tree", including "tree" itself.
843 * Return 0 on success and -1 on error, where "fn" returning a negative
844 * value is treated as an error.
846 int pet_tree_foreach_sub_tree(__isl_keep pet_tree
*tree
,
847 int (*fn
)(__isl_keep pet_tree
*tree
, void *user
), void *user
)
854 if (fn(tree
, user
) < 0)
857 switch (tree
->type
) {
861 for (i
= 0; i
< tree
->u
.b
.n
; ++i
)
862 if (pet_tree_foreach_sub_tree(tree
->u
.b
.child
[i
],
867 case pet_tree_continue
:
869 case pet_tree_decl_init
:
873 if (pet_tree_foreach_sub_tree(tree
->u
.i
.then_body
,
877 case pet_tree_if_else
:
878 if (pet_tree_foreach_sub_tree(tree
->u
.i
.then_body
,
881 if (pet_tree_foreach_sub_tree(tree
->u
.i
.else_body
,
887 case pet_tree_infinite_loop
:
888 if (pet_tree_foreach_sub_tree(tree
->u
.l
.body
, fn
, user
) < 0)
896 /* Intermediate data structure for foreach_expr.
898 * "fn" is the function that needs to be called on each expression.
899 * "user" is the user argument to be passed to "fn".
901 struct pet_tree_foreach_expr_data
{
902 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
);
906 /* Call data->fn on each expression in the "tree" object.
907 * This function is used as a callback to pet_tree_foreach_sub_tree
908 * to implement pet_tree_foreach_expr.
910 * Return 0 on success and -1 on error, where data->fn returning a negative
911 * value is treated as an error.
913 static int foreach_expr(__isl_keep pet_tree
*tree
, void *user
)
915 struct pet_tree_foreach_expr_data
*data
= user
;
920 switch (tree
->type
) {
925 case pet_tree_continue
:
926 case pet_tree_infinite_loop
:
929 if (data
->fn(tree
->u
.d
.var
, data
->user
) < 0)
932 case pet_tree_decl_init
:
933 if (data
->fn(tree
->u
.d
.var
, data
->user
) < 0)
935 if (data
->fn(tree
->u
.d
.init
, data
->user
) < 0)
939 if (data
->fn(tree
->u
.e
.expr
, data
->user
) < 0)
943 if (data
->fn(tree
->u
.i
.cond
, data
->user
) < 0)
946 case pet_tree_if_else
:
947 if (data
->fn(tree
->u
.i
.cond
, data
->user
) < 0)
951 if (data
->fn(tree
->u
.l
.cond
, data
->user
) < 0)
955 if (data
->fn(tree
->u
.l
.iv
, data
->user
) < 0)
957 if (data
->fn(tree
->u
.l
.init
, data
->user
) < 0)
959 if (data
->fn(tree
->u
.l
.cond
, data
->user
) < 0)
961 if (data
->fn(tree
->u
.l
.inc
, data
->user
) < 0)
969 /* Call "fn" on each top-level expression in the nodes of "tree"
971 * Return 0 on success and -1 on error, where "fn" returning a negative
972 * value is treated as an error.
974 * We run over all nodes in "tree" and call "fn"
975 * on each expression in those nodes.
977 int pet_tree_foreach_expr(__isl_keep pet_tree
*tree
,
978 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
980 struct pet_tree_foreach_expr_data data
= { fn
, user
};
982 return pet_tree_foreach_sub_tree(tree
, &foreach_expr
, &data
);
985 /* Intermediate data structure for foreach_access_expr.
987 * "fn" is the function that needs to be called on each access subexpression.
988 * "user" is the user argument to be passed to "fn".
990 struct pet_tree_foreach_access_expr_data
{
991 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
);
995 /* Call data->fn on each access subexpression of "expr".
996 * This function is used as a callback to pet_tree_foreach_expr
997 * to implement pet_tree_foreach_access_expr.
999 * Return 0 on success and -1 on error, where data->fn returning a negative
1000 * value is treated as an error.
1002 static int foreach_access_expr(__isl_keep pet_expr
*expr
, void *user
)
1004 struct pet_tree_foreach_access_expr_data
*data
= user
;
1006 return pet_expr_foreach_access_expr(expr
, data
->fn
, data
->user
);
1009 /* Call "fn" on each access subexpression in the nodes of "tree"
1011 * Return 0 on success and -1 on error, where "fn" returning a negative
1012 * value is treated as an error.
1014 * We run over all expressions in the nodes of "tree" and call "fn"
1015 * on each access subexpression of those expressions.
1017 int pet_tree_foreach_access_expr(__isl_keep pet_tree
*tree
,
1018 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1020 struct pet_tree_foreach_access_expr_data data
= { fn
, user
};
1022 return pet_tree_foreach_expr(tree
, &foreach_access_expr
, &data
);
1025 /* Modify all top-level expressions in the nodes of "tree"
1026 * by calling "fn" on them.
1028 __isl_give pet_tree
*pet_tree_map_expr(__isl_take pet_tree
*tree
,
1029 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1034 tree
= pet_tree_cow(tree
);
1038 switch (tree
->type
) {
1039 case pet_tree_error
:
1040 return pet_tree_free(tree
);
1041 case pet_tree_block
:
1042 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
1043 tree
->u
.b
.child
[i
] =
1044 pet_tree_map_expr(tree
->u
.b
.child
[i
], fn
, user
);
1045 if (!tree
->u
.b
.child
[i
])
1046 return pet_tree_free(tree
);
1049 case pet_tree_break
:
1050 case pet_tree_continue
:
1053 tree
->u
.d
.var
= fn(tree
->u
.d
.var
, user
);
1055 return pet_tree_free(tree
);
1057 case pet_tree_decl_init
:
1058 tree
->u
.d
.var
= fn(tree
->u
.d
.var
, user
);
1059 tree
->u
.d
.init
= fn(tree
->u
.d
.init
, user
);
1060 if (!tree
->u
.d
.var
|| !tree
->u
.d
.init
)
1061 return pet_tree_free(tree
);
1064 tree
->u
.e
.expr
= fn(tree
->u
.e
.expr
, user
);
1065 if (!tree
->u
.e
.expr
)
1066 return pet_tree_free(tree
);
1069 tree
->u
.i
.cond
= fn(tree
->u
.i
.cond
, user
);
1070 tree
->u
.i
.then_body
=
1071 pet_tree_map_expr(tree
->u
.i
.then_body
, fn
, user
);
1072 if (!tree
->u
.i
.cond
|| !tree
->u
.i
.then_body
)
1073 return pet_tree_free(tree
);
1075 case pet_tree_if_else
:
1076 tree
->u
.i
.cond
= fn(tree
->u
.i
.cond
, user
);
1077 tree
->u
.i
.then_body
=
1078 pet_tree_map_expr(tree
->u
.i
.then_body
, fn
, user
);
1079 tree
->u
.i
.else_body
=
1080 pet_tree_map_expr(tree
->u
.i
.else_body
, fn
, user
);
1081 if (!tree
->u
.i
.cond
||
1082 !tree
->u
.i
.then_body
|| !tree
->u
.i
.else_body
)
1083 return pet_tree_free(tree
);
1085 case pet_tree_while
:
1086 tree
->u
.l
.cond
= fn(tree
->u
.l
.cond
, user
);
1087 tree
->u
.l
.body
= pet_tree_map_expr(tree
->u
.l
.body
, fn
, user
);
1088 if (!tree
->u
.l
.cond
|| !tree
->u
.l
.body
)
1089 return pet_tree_free(tree
);
1092 tree
->u
.l
.iv
= fn(tree
->u
.l
.iv
, user
);
1093 tree
->u
.l
.init
= fn(tree
->u
.l
.init
, user
);
1094 tree
->u
.l
.cond
= fn(tree
->u
.l
.cond
, user
);
1095 tree
->u
.l
.inc
= fn(tree
->u
.l
.inc
, user
);
1096 tree
->u
.l
.body
= pet_tree_map_expr(tree
->u
.l
.body
, fn
, user
);
1097 if (!tree
->u
.l
.iv
|| !tree
->u
.l
.init
|| !tree
->u
.l
.cond
||
1098 !tree
->u
.l
.inc
|| !tree
->u
.l
.body
)
1099 return pet_tree_free(tree
);
1101 case pet_tree_infinite_loop
:
1102 tree
->u
.l
.body
= pet_tree_map_expr(tree
->u
.l
.body
, fn
, user
);
1103 if (!tree
->u
.l
.body
)
1104 return pet_tree_free(tree
);
1111 /* Intermediate data structure for map_access_expr.
1113 * "fn" is the function that needs to be called on each access subexpression.
1114 * "user" is the user argument to be passed to "fn".
1116 struct pet_tree_map_access_expr_data
{
1117 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
);
1121 /* Modify all top-level expressions in the nodes of "tree"
1122 * by calling "fn" on them.
1124 * This is a wrapper around pet_expr_map_access for use as a callback
1125 * to pet_tree_map_expr.
1127 static __isl_give pet_expr
*map_access_expr(__isl_take pet_expr
*expr
,
1130 struct pet_tree_map_access_expr_data
*data
= user
;
1132 return pet_expr_map_access(expr
, data
->fn
, data
->user
);
1135 /* Modify all access subexpressions in the nodes of "tree"
1136 * by calling "fn" on them.
1138 * We run over all expressions in the nodes of "tree" and call "fn"
1139 * on each access subexpression of those expressions.
1141 __isl_give pet_tree
*pet_tree_map_access_expr(__isl_take pet_tree
*tree
,
1142 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1145 struct pet_tree_map_access_expr_data data
= { fn
, user
};
1147 return pet_tree_map_expr(tree
, &map_access_expr
, &data
);
1150 /* Return 1 if the two pet_tree objects are equivalent.
1152 * We ignore the locations of the trees.
1154 int pet_tree_is_equal(__isl_keep pet_tree
*tree1
, __isl_keep pet_tree
*tree2
)
1159 if (!tree1
|| !tree2
)
1165 if (tree1
->type
!= tree2
->type
)
1167 if (tree1
->label
!= tree2
->label
)
1170 switch (tree1
->type
) {
1171 case pet_tree_error
:
1173 case pet_tree_block
:
1174 if (tree1
->u
.b
.block
!= tree2
->u
.b
.block
)
1176 if (tree1
->u
.b
.n
!= tree2
->u
.b
.n
)
1178 for (i
= 0; i
< tree1
->u
.b
.n
; ++i
) {
1179 equal
= pet_tree_is_equal(tree1
->u
.b
.child
[i
],
1180 tree2
->u
.b
.child
[i
]);
1181 if (equal
< 0 || !equal
)
1185 case pet_tree_break
:
1186 case pet_tree_continue
:
1189 return pet_expr_is_equal(tree1
->u
.d
.var
, tree2
->u
.d
.var
);
1190 case pet_tree_decl_init
:
1191 equal
= pet_expr_is_equal(tree1
->u
.d
.var
, tree2
->u
.d
.var
);
1192 if (equal
< 0 || !equal
)
1194 return pet_expr_is_equal(tree1
->u
.d
.init
, tree2
->u
.d
.init
);
1196 return pet_expr_is_equal(tree1
->u
.e
.expr
, tree2
->u
.e
.expr
);
1198 if (tree1
->u
.l
.declared
!= tree2
->u
.l
.declared
)
1200 equal
= pet_expr_is_equal(tree1
->u
.l
.iv
, tree2
->u
.l
.iv
);
1201 if (equal
< 0 || !equal
)
1203 equal
= pet_expr_is_equal(tree1
->u
.l
.init
, tree2
->u
.l
.init
);
1204 if (equal
< 0 || !equal
)
1206 equal
= pet_expr_is_equal(tree1
->u
.l
.cond
, tree2
->u
.l
.cond
);
1207 if (equal
< 0 || !equal
)
1209 equal
= pet_expr_is_equal(tree1
->u
.l
.inc
, tree2
->u
.l
.inc
);
1210 if (equal
< 0 || !equal
)
1212 return pet_tree_is_equal(tree1
->u
.l
.body
, tree2
->u
.l
.body
);
1213 case pet_tree_while
:
1214 equal
= pet_expr_is_equal(tree1
->u
.l
.cond
, tree2
->u
.l
.cond
);
1215 if (equal
< 0 || !equal
)
1217 return pet_tree_is_equal(tree1
->u
.l
.body
, tree2
->u
.l
.body
);
1218 case pet_tree_infinite_loop
:
1219 return pet_tree_is_equal(tree1
->u
.l
.body
, tree2
->u
.l
.body
);
1221 equal
= pet_expr_is_equal(tree1
->u
.i
.cond
, tree2
->u
.i
.cond
);
1222 if (equal
< 0 || !equal
)
1224 return pet_tree_is_equal(tree1
->u
.i
.then_body
,
1225 tree2
->u
.i
.then_body
);
1226 case pet_tree_if_else
:
1227 equal
= pet_expr_is_equal(tree1
->u
.i
.cond
, tree2
->u
.i
.cond
);
1228 if (equal
< 0 || !equal
)
1230 equal
= pet_tree_is_equal(tree1
->u
.i
.then_body
,
1231 tree2
->u
.i
.then_body
);
1232 if (equal
< 0 || !equal
)
1234 return pet_tree_is_equal(tree1
->u
.i
.else_body
,
1235 tree2
->u
.i
.else_body
);
1241 /* Is "tree" an expression tree that performs the operation "type"?
1243 static int pet_tree_is_op_of_type(__isl_keep pet_tree
*tree
,
1244 enum pet_op_type type
)
1248 if (tree
->type
!= pet_tree_expr
)
1250 if (pet_expr_get_type(tree
->u
.e
.expr
) != pet_expr_op
)
1252 return pet_expr_op_get_type(tree
->u
.e
.expr
) == type
;
1255 /* Is "tree" an expression tree that performs a kill operation?
1257 int pet_tree_is_kill(__isl_keep pet_tree
*tree
)
1259 return pet_tree_is_op_of_type(tree
, pet_op_kill
);
1262 /* Is "tree" an expression tree that performs an assignment operation?
1264 int pet_tree_is_assign(__isl_keep pet_tree
*tree
)
1266 return pet_tree_is_op_of_type(tree
, pet_op_assign
);
1269 /* Is "tree" an expression tree that performs an assume operation?
1271 int pet_tree_is_assume(__isl_keep pet_tree
*tree
)
1273 return pet_tree_is_op_of_type(tree
, pet_op_assume
);
1276 /* Is "tree" an expression tree that performs an assume operation
1277 * such that the assumed expression is affine?
1279 int pet_tree_is_affine_assume(__isl_keep pet_tree
*tree
)
1281 if (!pet_tree_is_assume(tree
))
1283 return pet_expr_is_affine(tree
->u
.e
.expr
->args
[0]);
1286 /* Given a tree that represent an assume operation expression
1287 * with an access as argument (possibly an affine expression),
1288 * return the index expression of that access.
1290 __isl_give isl_multi_pw_aff
*pet_tree_assume_get_index(
1291 __isl_keep pet_tree
*tree
)
1295 if (!pet_tree_is_assume(tree
))
1296 isl_die(pet_tree_get_ctx(tree
), isl_error_invalid
,
1297 "not an assume tree", return NULL
);
1298 return pet_expr_access_get_index(tree
->u
.e
.expr
->args
[0]);
1301 /* Internal data structure for pet_tree_writes.
1302 * "id" is the identifier that we are looking for.
1303 * "writes" is set if we have found the identifier being written to.
1305 struct pet_tree_writes_data
{
1310 /* Check if expr writes to data->id.
1311 * If so, set data->writes and abort the search.
1313 static int check_write(__isl_keep pet_expr
*expr
, void *user
)
1315 struct pet_tree_writes_data
*data
= user
;
1317 data
->writes
= pet_expr_writes(expr
, data
->id
);
1318 if (data
->writes
< 0 || data
->writes
)
1324 /* Is there any write access in "tree" that accesses "id"?
1326 int pet_tree_writes(__isl_keep pet_tree
*tree
, __isl_keep isl_id
*id
)
1328 struct pet_tree_writes_data data
;
1332 if (pet_tree_foreach_expr(tree
, &check_write
, &data
) < 0 &&
1339 /* Does "tree" contain a continue node (not contained in any loop
1340 * subtree of "tree"?
1342 int pet_tree_has_continue(__isl_keep pet_tree
*tree
)
1350 switch (tree
->type
) {
1351 case pet_tree_error
:
1353 case pet_tree_continue
:
1355 case pet_tree_break
:
1357 case pet_tree_decl_init
:
1360 case pet_tree_while
:
1361 case pet_tree_infinite_loop
:
1363 case pet_tree_block
:
1364 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
1365 found
= pet_tree_has_continue(tree
->u
.b
.child
[i
]);
1366 if (found
< 0 || found
)
1371 return pet_tree_has_continue(tree
->u
.i
.then_body
);
1372 case pet_tree_if_else
:
1373 found
= pet_tree_has_continue(tree
->u
.i
.then_body
);
1374 if (found
< 0 || found
)
1376 return pet_tree_has_continue(tree
->u
.i
.else_body
);
1380 static void print_indent(int indent
)
1382 fprintf(stderr
, "%*s", indent
, "");
1385 void pet_tree_dump_with_indent(__isl_keep pet_tree
*tree
, int indent
)
1392 print_indent(indent
);
1393 fprintf(stderr
, "%s\n", pet_tree_type_str(tree
->type
));
1394 print_indent(indent
);
1395 fprintf(stderr
, "line: %d\n", pet_loc_get_line(tree
->loc
));
1396 print_indent(indent
);
1397 fprintf(stderr
, "start: %d\n", pet_loc_get_start(tree
->loc
));
1398 print_indent(indent
);
1399 fprintf(stderr
, "end: %d\n", pet_loc_get_end(tree
->loc
));
1401 print_indent(indent
);
1402 fprintf(stderr
, "end: ");
1403 isl_id_dump(tree
->label
);
1405 switch (tree
->type
) {
1406 case pet_tree_block
:
1407 print_indent(indent
);
1408 fprintf(stderr
, "block: %d\n", tree
->u
.b
.block
);
1409 for (i
= 0; i
< tree
->u
.b
.n
; ++i
)
1410 pet_tree_dump_with_indent(tree
->u
.b
.child
[i
],
1414 pet_expr_dump_with_indent(tree
->u
.e
.expr
, indent
);
1416 case pet_tree_break
:
1417 case pet_tree_continue
:
1420 case pet_tree_decl_init
:
1421 print_indent(indent
);
1422 fprintf(stderr
, "var:\n");
1423 pet_expr_dump_with_indent(tree
->u
.d
.var
, indent
+ 2);
1424 if (tree
->type
!= pet_tree_decl_init
)
1426 print_indent(indent
);
1427 fprintf(stderr
, "init:\n");
1428 pet_expr_dump_with_indent(tree
->u
.d
.init
, indent
+ 2);
1431 case pet_tree_if_else
:
1432 print_indent(indent
);
1433 fprintf(stderr
, "condition:\n");
1434 pet_expr_dump_with_indent(tree
->u
.i
.cond
, indent
+ 2);
1435 print_indent(indent
);
1436 fprintf(stderr
, "then:\n");
1437 pet_tree_dump_with_indent(tree
->u
.i
.then_body
, indent
+ 2);
1438 if (tree
->type
!= pet_tree_if_else
)
1440 print_indent(indent
);
1441 fprintf(stderr
, "else:\n");
1442 pet_tree_dump_with_indent(tree
->u
.i
.else_body
, indent
+ 2);
1445 print_indent(indent
);
1446 fprintf(stderr
, "declared: %d\n", tree
->u
.l
.declared
);
1447 print_indent(indent
);
1448 fprintf(stderr
, "var:\n");
1449 pet_expr_dump_with_indent(tree
->u
.l
.iv
, indent
+ 2);
1450 print_indent(indent
);
1451 fprintf(stderr
, "init:\n");
1452 pet_expr_dump_with_indent(tree
->u
.l
.init
, indent
+ 2);
1453 print_indent(indent
);
1454 fprintf(stderr
, "inc:\n");
1455 pet_expr_dump_with_indent(tree
->u
.l
.inc
, indent
+ 2);
1456 case pet_tree_while
:
1457 print_indent(indent
);
1458 fprintf(stderr
, "condition:\n");
1459 pet_expr_dump_with_indent(tree
->u
.l
.cond
, indent
+ 2);
1460 case pet_tree_infinite_loop
:
1461 print_indent(indent
);
1462 fprintf(stderr
, "body:\n");
1463 pet_tree_dump_with_indent(tree
->u
.l
.body
, indent
+ 2);
1465 case pet_tree_error
:
1466 print_indent(indent
);
1467 fprintf(stderr
, "ERROR\n");
1472 void pet_tree_dump(__isl_keep pet_tree
*tree
)
1474 pet_tree_dump_with_indent(tree
, 0);