1 #include <isl_ast_private.h>
2 #include <isl_list_private.h>
7 #include <isl_list_templ.c>
12 #include <isl_list_templ.c>
14 __isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
16 return isl_calloc_type(ctx, isl_ast_print_options);
19 void *isl_ast_print_options_free(__isl_take isl_ast_print_options *options)
25 /* Set the print_user callback of "options" to "print_user".
27 * If this callback is set, then it used to print user nodes in the AST.
28 * Otherwise, the expression associated to the user node is printed.
30 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_user(
31 __isl_take isl_ast_print_options *options,
32 __isl_give isl_printer *(*print_user)(__isl_take isl_printer *p,
33 __isl_keep isl_ast_node *node, void *user),
39 options->print_user = print_user;
40 options->print_user_user = user;
45 /* Set the print_for callback of "options" to "print_for".
47 * If this callback is set, then it used to print for nodes in the AST.
49 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_for(
50 __isl_take isl_ast_print_options *options,
51 __isl_give isl_printer *(*print_for)(__isl_take isl_printer *p,
52 __isl_keep isl_ast_node *node, void *user),
58 options->print_for = print_for;
59 options->print_for_user = user;
64 __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
73 __isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
82 ctx = isl_ast_expr_get_ctx(expr);
84 case isl_ast_expr_int:
85 dup = isl_ast_expr_alloc_int(ctx, expr->u.i);
88 dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id));
91 dup = isl_ast_expr_alloc_op(ctx,
92 expr->u.op.op, expr->u.op.n_arg);
95 for (i = 0; i < expr->u.op.n_arg; ++i)
97 isl_ast_expr_copy(expr->u.op.args[i]);
99 case isl_ast_expr_error:
109 __isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr)
117 return isl_ast_expr_dup(expr);
120 void *isl_ast_expr_free(__isl_take isl_ast_expr *expr)
130 isl_ctx_deref(expr->ctx);
132 switch (expr->type) {
133 case isl_ast_expr_int:
134 isl_int_clear(expr->u.i);
136 case isl_ast_expr_id:
137 isl_id_free(expr->u.id);
139 case isl_ast_expr_op:
140 for (i = 0; i < expr->u.op.n_arg; ++i)
141 isl_ast_expr_free(expr->u.op.args[i]);
142 free(expr->u.op.args);
144 case isl_ast_expr_error:
152 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
154 return expr ? expr->ctx : NULL;
157 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
159 return expr ? expr->type : isl_ast_expr_error;
162 int isl_ast_expr_get_int(__isl_keep isl_ast_expr *expr, isl_int *v)
166 if (expr->type != isl_ast_expr_int)
167 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
168 "expression not an int", return -1);
169 isl_int_set(*v, expr->u.i);
173 __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
177 if (expr->type != isl_ast_expr_id)
178 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
179 "expression not an identifier", return NULL);
181 return isl_id_copy(expr->u.id);
184 enum isl_ast_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
187 return isl_ast_op_error;
188 if (expr->type != isl_ast_expr_op)
189 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
190 "expression not an operation", return isl_ast_op_error);
191 return expr->u.op.op;
194 int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
198 if (expr->type != isl_ast_expr_op)
199 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
200 "expression not an operation", return -1);
201 return expr->u.op.n_arg;
204 __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
209 if (expr->type != isl_ast_expr_op)
210 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
211 "expression not an operation", return NULL);
212 if (pos < 0 || pos >= expr->u.op.n_arg)
213 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
214 "index out of bounds", return NULL);
216 return isl_ast_expr_copy(expr->u.op.args[pos]);
219 /* Replace the argument at position "pos" of "expr" by "arg".
221 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
222 int pos, __isl_take isl_ast_expr *arg)
224 expr = isl_ast_expr_cow(expr);
227 if (expr->type != isl_ast_expr_op)
228 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
229 "expression not an operation", goto error);
230 if (pos < 0 || pos >= expr->u.op.n_arg)
231 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
232 "index out of bounds", goto error);
234 isl_ast_expr_free(expr->u.op.args[pos]);
235 expr->u.op.args[pos] = arg;
239 isl_ast_expr_free(arg);
240 return isl_ast_expr_free(expr);
243 /* Create a new operation expression of operation type "op",
244 * with "n_arg" as yet unspecified arguments.
246 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
247 enum isl_ast_op_type op, int n_arg)
251 expr = isl_calloc_type(ctx, isl_ast_expr);
258 expr->type = isl_ast_expr_op;
260 expr->u.op.n_arg = n_arg;
261 expr->u.op.args = isl_calloc_array(ctx, isl_ast_expr *, n_arg);
263 if (!expr->u.op.args)
264 return isl_ast_expr_free(expr);
269 /* Create a new id expression representing "id".
271 __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
279 ctx = isl_id_get_ctx(id);
280 expr = isl_calloc_type(ctx, isl_ast_expr);
282 return isl_id_free(id);
287 expr->type = isl_ast_expr_id;
293 /* Create a new integer expression representing "i".
295 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
299 expr = isl_calloc_type(ctx, isl_ast_expr);
306 expr->type = isl_ast_expr_int;
308 isl_int_init(expr->u.i);
309 isl_int_set_si(expr->u.i, i);
314 /* Create a new integer expression representing "i".
316 __isl_give isl_ast_expr *isl_ast_expr_alloc_int(isl_ctx *ctx, isl_int i)
320 expr = isl_calloc_type(ctx, isl_ast_expr);
327 expr->type = isl_ast_expr_int;
329 isl_int_init(expr->u.i);
330 isl_int_set(expr->u.i, i);
335 /* Create an expression representing the negation of "arg".
337 __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg)
340 isl_ast_expr *expr = NULL;
345 ctx = isl_ast_expr_get_ctx(arg);
346 expr = isl_ast_expr_alloc_op(ctx, isl_ast_op_minus, 1);
350 expr->u.op.args[0] = arg;
354 isl_ast_expr_free(arg);
358 /* Create an expression representing the binary operation "type"
359 * applied to "expr1" and "expr2".
361 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(enum isl_ast_op_type type,
362 __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
365 isl_ast_expr *expr = NULL;
367 if (!expr1 || !expr2)
370 ctx = isl_ast_expr_get_ctx(expr1);
371 expr = isl_ast_expr_alloc_op(ctx, type, 2);
375 expr->u.op.args[0] = expr1;
376 expr->u.op.args[1] = expr2;
380 isl_ast_expr_free(expr1);
381 isl_ast_expr_free(expr2);
385 /* Create an expression representing the sum of "expr1" and "expr2".
387 __isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
388 __isl_take isl_ast_expr *expr2)
390 return isl_ast_expr_alloc_binary(isl_ast_op_add, expr1, expr2);
393 /* Create an expression representing the difference of "expr1" and "expr2".
395 __isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
396 __isl_take isl_ast_expr *expr2)
398 return isl_ast_expr_alloc_binary(isl_ast_op_sub, expr1, expr2);
401 /* Create an expression representing the product of "expr1" and "expr2".
403 __isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
404 __isl_take isl_ast_expr *expr2)
406 return isl_ast_expr_alloc_binary(isl_ast_op_mul, expr1, expr2);
409 /* Create an expression representing the quotient of "expr1" and "expr2".
411 __isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1,
412 __isl_take isl_ast_expr *expr2)
414 return isl_ast_expr_alloc_binary(isl_ast_op_div, expr1, expr2);
417 /* Create an expression representing the conjunction of "expr1" and "expr2".
419 __isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
420 __isl_take isl_ast_expr *expr2)
422 return isl_ast_expr_alloc_binary(isl_ast_op_and, expr1, expr2);
425 /* Create an expression representing the disjunction of "expr1" and "expr2".
427 __isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
428 __isl_take isl_ast_expr *expr2)
430 return isl_ast_expr_alloc_binary(isl_ast_op_or, expr1, expr2);
433 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
435 return node ? node->ctx : NULL;
438 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
440 return node ? node->type : isl_ast_node_error;
443 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
444 enum isl_ast_node_type type)
448 node = isl_calloc_type(ctx, isl_ast_node);
460 /* Create an if node with the given guard.
462 * The then body needs to be filled in later.
464 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
471 node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
474 node->u.i.guard = guard;
478 isl_ast_expr_free(guard);
482 /* Create a for node with the given iterator.
484 * The remaining fields need to be filled in later.
486 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
494 ctx = isl_id_get_ctx(id);
495 node = isl_ast_node_alloc(ctx, isl_ast_node_for);
499 node->u.f.iterator = isl_ast_expr_from_id(id);
500 if (!node->u.f.iterator)
501 return isl_ast_node_free(node);
506 /* Create a user node evaluating "expr".
508 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
516 ctx = isl_ast_expr_get_ctx(expr);
517 node = isl_ast_node_alloc(ctx, isl_ast_node_user);
521 node->u.e.expr = expr;
525 isl_ast_expr_free(expr);
529 /* Create a block node with the given children.
531 __isl_give isl_ast_node *isl_ast_node_alloc_block(
532 __isl_take isl_ast_node_list *list)
540 ctx = isl_ast_node_list_get_ctx(list);
541 node = isl_ast_node_alloc(ctx, isl_ast_node_block);
545 node->u.b.children = list;
549 isl_ast_node_list_free(list);
553 /* Represent the given list of nodes as a single node, either by
554 * extract the node from a single element list or by creating
555 * a block node with the list of nodes as children.
557 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
558 __isl_take isl_ast_node_list *list)
562 if (isl_ast_node_list_n_ast_node(list) != 1)
563 return isl_ast_node_alloc_block(list);
565 node = isl_ast_node_list_get_ast_node(list, 0);
566 isl_ast_node_list_free(list);
571 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
580 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
587 dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
591 switch (node->type) {
592 case isl_ast_node_if:
593 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
594 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
595 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
596 if (!dup->u.i.guard || !dup->u.i.then ||
597 (node->u.i.else_node && !dup->u.i.else_node))
598 return isl_ast_node_free(dup);
600 case isl_ast_node_for:
601 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
602 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
603 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
604 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
605 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
606 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
607 !dup->u.f.inc || !dup->u.f.body)
608 return isl_ast_node_free(dup);
610 case isl_ast_node_block:
611 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
612 if (!dup->u.b.children)
613 return isl_ast_node_free(dup);
615 case isl_ast_node_user:
616 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
618 return isl_ast_node_free(dup);
620 case isl_ast_node_error:
627 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
635 return isl_ast_node_dup(node);
638 void *isl_ast_node_free(__isl_take isl_ast_node *node)
646 switch (node->type) {
647 case isl_ast_node_if:
648 isl_ast_expr_free(node->u.i.guard);
649 isl_ast_node_free(node->u.i.then);
650 isl_ast_node_free(node->u.i.else_node);
652 case isl_ast_node_for:
653 isl_ast_expr_free(node->u.f.iterator);
654 isl_ast_expr_free(node->u.f.init);
655 isl_ast_expr_free(node->u.f.cond);
656 isl_ast_expr_free(node->u.f.inc);
657 isl_ast_node_free(node->u.f.body);
659 case isl_ast_node_block:
660 isl_ast_node_list_free(node->u.b.children);
662 case isl_ast_node_user:
663 isl_ast_expr_free(node->u.e.expr);
665 case isl_ast_node_error:
669 isl_id_free(node->annotation);
670 isl_ctx_deref(node->ctx);
676 /* Replace the body of the for node "node" by "body".
678 __isl_give isl_ast_node *isl_ast_node_for_set_body(
679 __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
681 node = isl_ast_node_cow(node);
684 if (node->type != isl_ast_node_for)
685 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
686 "not a for node", goto error);
688 isl_ast_node_free(node->u.f.body);
689 node->u.f.body = body;
693 isl_ast_node_free(node);
694 isl_ast_node_free(body);
698 __isl_give isl_ast_node *isl_ast_node_for_get_body(
699 __isl_keep isl_ast_node *node)
703 if (node->type != isl_ast_node_for)
704 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
705 "not a for node", return NULL);
706 return isl_ast_node_copy(node->u.f.body);
709 /* Mark the given for node as being degenerate.
711 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
712 __isl_take isl_ast_node *node)
714 node = isl_ast_node_cow(node);
717 node->u.f.degenerate = 1;
721 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
725 if (node->type != isl_ast_node_for)
726 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
727 "not a for node", return -1);
728 return node->u.f.degenerate;
731 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
732 __isl_keep isl_ast_node *node)
736 if (node->type != isl_ast_node_for)
737 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
738 "not a for node", return NULL);
739 return isl_ast_expr_copy(node->u.f.iterator);
742 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
743 __isl_keep isl_ast_node *node)
747 if (node->type != isl_ast_node_for)
748 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
749 "not a for node", return NULL);
750 return isl_ast_expr_copy(node->u.f.init);
753 /* Return the condition expression of the given for node.
755 * If the for node is degenerate, then the condition is not explicitly
756 * stored in the node. Instead, it is constructed as
760 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
761 __isl_keep isl_ast_node *node)
765 if (node->type != isl_ast_node_for)
766 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
767 "not a for node", return NULL);
768 if (!node->u.f.degenerate)
769 return isl_ast_expr_copy(node->u.f.cond);
771 return isl_ast_expr_alloc_binary(isl_ast_op_le,
772 isl_ast_expr_copy(node->u.f.iterator),
773 isl_ast_expr_copy(node->u.f.init));
776 /* Return the increment of the given for node.
778 * If the for node is degenerate, then the increment is not explicitly
779 * stored in the node. We simply return "1".
781 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
782 __isl_keep isl_ast_node *node)
786 if (node->type != isl_ast_node_for)
787 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
788 "not a for node", return NULL);
789 if (!node->u.f.degenerate)
790 return isl_ast_expr_copy(node->u.f.inc);
791 return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
794 /* Replace the then branch of the if node "node" by "child".
796 __isl_give isl_ast_node *isl_ast_node_if_set_then(
797 __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
799 node = isl_ast_node_cow(node);
802 if (node->type != isl_ast_node_if)
803 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
804 "not an if node", goto error);
806 isl_ast_node_free(node->u.i.then);
807 node->u.i.then = child;
811 isl_ast_node_free(node);
812 isl_ast_node_free(child);
816 __isl_give isl_ast_node *isl_ast_node_if_get_then(
817 __isl_keep isl_ast_node *node)
821 if (node->type != isl_ast_node_if)
822 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
823 "not an if node", return NULL);
824 return isl_ast_node_copy(node->u.i.then);
827 int isl_ast_node_if_has_else(
828 __isl_keep isl_ast_node *node)
832 if (node->type != isl_ast_node_if)
833 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
834 "not an if node", return -1);
835 return node->u.i.else_node != NULL;
838 __isl_give isl_ast_node *isl_ast_node_if_get_else(
839 __isl_keep isl_ast_node *node)
843 if (node->type != isl_ast_node_if)
844 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
845 "not an if node", return NULL);
846 return isl_ast_node_copy(node->u.i.else_node);
849 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
850 __isl_keep isl_ast_node *node)
854 if (node->type != isl_ast_node_if)
855 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
856 "not a guard node", return NULL);
857 return isl_ast_expr_copy(node->u.i.guard);
860 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
861 __isl_keep isl_ast_node *node)
865 if (node->type != isl_ast_node_block)
866 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
867 "not a block node", return NULL);
868 return isl_ast_node_list_copy(node->u.b.children);
871 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
872 __isl_keep isl_ast_node *node)
877 return isl_ast_expr_copy(node->u.e.expr);
880 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
882 return node ? isl_id_copy(node->annotation) : NULL;
885 /* Replace node->annotation by "annotation".
887 __isl_give isl_ast_node *isl_ast_node_set_annotation(
888 __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
890 node = isl_ast_node_cow(node);
891 if (!node || !annotation)
894 isl_id_free(node->annotation);
895 node->annotation = annotation;
899 isl_id_free(annotation);
900 return isl_ast_node_free(node);
903 /* Textual C representation of the various operators.
905 static char *op_str[] = {
906 [isl_ast_op_and] = "&&",
907 [isl_ast_op_and_then] = "&&",
908 [isl_ast_op_or] = "||",
909 [isl_ast_op_or_else] = "||",
910 [isl_ast_op_max] = "max",
911 [isl_ast_op_min] = "min",
912 [isl_ast_op_minus] = "-",
913 [isl_ast_op_add] = "+",
914 [isl_ast_op_sub] = "-",
915 [isl_ast_op_mul] = "*",
916 [isl_ast_op_pdiv_q] = "/",
917 [isl_ast_op_pdiv_r] = "%",
918 [isl_ast_op_div] = "/",
919 [isl_ast_op_eq] = "==",
920 [isl_ast_op_le] = "<=",
921 [isl_ast_op_ge] = ">=",
922 [isl_ast_op_lt] = "<",
923 [isl_ast_op_gt] = ">"
926 /* Precedence in C of the various operators.
927 * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
928 * Lowest value means highest precedence.
930 static int op_prec[] = {
931 [isl_ast_op_and] = 13,
932 [isl_ast_op_and_then] = 13,
933 [isl_ast_op_or] = 14,
934 [isl_ast_op_or_else] = 14,
935 [isl_ast_op_max] = 2,
936 [isl_ast_op_min] = 2,
937 [isl_ast_op_minus] = 3,
938 [isl_ast_op_add] = 6,
939 [isl_ast_op_sub] = 6,
940 [isl_ast_op_mul] = 5,
941 [isl_ast_op_div] = 5,
942 [isl_ast_op_fdiv_q] = 2,
943 [isl_ast_op_pdiv_q] = 5,
944 [isl_ast_op_pdiv_r] = 5,
945 [isl_ast_op_cond] = 15,
946 [isl_ast_op_select] = 15,
952 [isl_ast_op_call] = 2
955 /* Is the operator left-to-right associative?
957 static int op_left[] = {
958 [isl_ast_op_and] = 1,
959 [isl_ast_op_and_then] = 1,
961 [isl_ast_op_or_else] = 1,
962 [isl_ast_op_max] = 1,
963 [isl_ast_op_min] = 1,
964 [isl_ast_op_minus] = 0,
965 [isl_ast_op_add] = 1,
966 [isl_ast_op_sub] = 1,
967 [isl_ast_op_mul] = 1,
968 [isl_ast_op_div] = 1,
969 [isl_ast_op_fdiv_q] = 1,
970 [isl_ast_op_pdiv_q] = 1,
971 [isl_ast_op_pdiv_r] = 1,
972 [isl_ast_op_cond] = 0,
973 [isl_ast_op_select] = 0,
979 [isl_ast_op_call] = 1
982 static int is_and(enum isl_ast_op_type op)
984 return op == isl_ast_op_and || op == isl_ast_op_and_then;
987 static int is_or(enum isl_ast_op_type op)
989 return op == isl_ast_op_or || op == isl_ast_op_or_else;
992 static int is_add_sub(enum isl_ast_op_type op)
994 return op == isl_ast_op_add || op == isl_ast_op_sub;
997 static int is_div_mod(enum isl_ast_op_type op)
999 return op == isl_ast_op_div || op == isl_ast_op_pdiv_r;
1002 /* Do we need/want parentheses around "expr" as a subexpression of
1003 * an "op" operation? If "left" is set, then "expr" is the left-most
1006 * We only need parentheses if "expr" represents an operation.
1008 * If op has a higher precedence than expr->u.op.op, then we need
1010 * If op and expr->u.op.op have the same precedence, but the operations
1011 * are performed in an order that is different from the associativity,
1012 * then we need parentheses.
1014 * An and inside an or technically does not require parentheses,
1015 * but some compilers complain about that, so we add them anyway.
1017 * Computations such as "a / b * c" and "a % b + c" can be somewhat
1018 * difficult to read, so we add parentheses for those as well.
1020 static int sub_expr_need_parens(enum isl_ast_op_type op,
1021 __isl_keep isl_ast_expr *expr, int left)
1023 if (expr->type != isl_ast_expr_op)
1026 if (op_prec[expr->u.op.op] > op_prec[op])
1028 if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1031 if (is_or(op) && is_and(expr->u.op.op))
1033 if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1034 op_prec[expr->u.op.op] == op_prec[op])
1036 if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1042 /* Print "expr" as a subexpression of an "op" operation.
1043 * If "left" is set, then "expr" is the left-most operand.
1045 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1046 enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1050 need_parens = sub_expr_need_parens(op, expr, left);
1053 p = isl_printer_print_str(p, "(");
1054 p = isl_printer_print_ast_expr(p, expr);
1056 p = isl_printer_print_str(p, ")");
1060 /* Print a min or max reduction "expr".
1062 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1063 __isl_keep isl_ast_expr *expr)
1067 for (i = 1; i < expr->u.op.n_arg; ++i) {
1068 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1069 p = isl_printer_print_str(p, "(");
1071 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1072 for (i = 1; i < expr->u.op.n_arg; ++i) {
1073 p = isl_printer_print_str(p, ", ");
1074 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1075 p = isl_printer_print_str(p, ")");
1081 /* Print a function call "expr".
1083 * The first argument represents the function to be called.
1085 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1086 __isl_keep isl_ast_expr *expr)
1090 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1091 p = isl_printer_print_str(p, "(");
1092 for (i = 1; i < expr->u.op.n_arg; ++i) {
1094 p = isl_printer_print_str(p, ", ");
1095 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1097 p = isl_printer_print_str(p, ")");
1102 /* Print "expr" to "p".
1104 * If we are printing in isl format, then we also print an indication
1105 * of the size of the expression (if it was computed).
1107 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1108 __isl_keep isl_ast_expr *expr)
1113 return isl_printer_free(p);
1115 switch (expr->type) {
1116 case isl_ast_expr_op:
1117 if (expr->u.op.op == isl_ast_op_call) {
1118 p = print_call(p, expr);
1121 if (expr->u.op.n_arg == 1) {
1122 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1123 p = print_sub_expr(p, expr->u.op.op,
1124 expr->u.op.args[0], 0);
1127 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1128 p = isl_printer_print_str(p, "floord(");
1129 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1130 p = isl_printer_print_str(p, ", ");
1131 p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1132 p = isl_printer_print_str(p, ")");
1135 if (expr->u.op.op == isl_ast_op_max ||
1136 expr->u.op.op == isl_ast_op_min) {
1137 p = print_min_max(p, expr);
1140 if (expr->u.op.op == isl_ast_op_cond ||
1141 expr->u.op.op == isl_ast_op_select) {
1142 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1143 p = isl_printer_print_str(p, " ? ");
1144 p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1145 p = isl_printer_print_str(p, " : ");
1146 p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1149 if (expr->u.op.n_arg != 2)
1150 isl_die(isl_printer_get_ctx(p), isl_error_internal,
1151 "operation should have two arguments",
1153 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1154 p = isl_printer_print_str(p, " ");
1155 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1156 p = isl_printer_print_str(p, " ");
1157 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1159 case isl_ast_expr_id:
1160 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1162 case isl_ast_expr_int:
1163 p = isl_printer_print_isl_int(p, expr->u.i);
1165 case isl_ast_expr_error:
1171 isl_printer_free(p);
1175 /* Print "node" to "p" in "isl format".
1177 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1178 __isl_keep isl_ast_node *node)
1180 p = isl_printer_print_str(p, "(");
1181 switch (node->type) {
1182 case isl_ast_node_for:
1183 if (node->u.f.degenerate) {
1184 p = isl_printer_print_ast_expr(p, node->u.f.init);
1186 p = isl_printer_print_str(p, "init: ");
1187 p = isl_printer_print_ast_expr(p, node->u.f.init);
1188 p = isl_printer_print_str(p, ", ");
1189 p = isl_printer_print_str(p, "cond: ");
1190 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1191 p = isl_printer_print_str(p, ", ");
1192 p = isl_printer_print_str(p, "inc: ");
1193 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1195 if (node->u.f.body) {
1196 p = isl_printer_print_str(p, ", ");
1197 p = isl_printer_print_str(p, "body: ");
1198 p = isl_printer_print_ast_node(p, node->u.f.body);
1201 case isl_ast_node_user:
1202 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1204 case isl_ast_node_if:
1205 p = isl_printer_print_str(p, "guard: ");
1206 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1207 if (node->u.i.then) {
1208 p = isl_printer_print_str(p, ", ");
1209 p = isl_printer_print_str(p, "then: ");
1210 p = isl_printer_print_ast_node(p, node->u.i.then);
1212 if (node->u.i.else_node) {
1213 p = isl_printer_print_str(p, ", ");
1214 p = isl_printer_print_str(p, "else: ");
1215 p = isl_printer_print_ast_node(p, node->u.i.else_node);
1218 case isl_ast_node_block:
1219 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1224 p = isl_printer_print_str(p, ")");
1228 /* Do we need to print a block around the body "node" of a for or if node?
1230 * If the node is a block, then we need to print a block.
1231 * Also if the node is a degenerate for then we will print it as
1232 * an assignment followed by the body of the for loop, so we need a block
1235 static int need_block(__isl_keep isl_ast_node *node)
1237 if (node->type == isl_ast_node_block)
1239 if (node->type == isl_ast_node_for && node->u.f.degenerate)
1244 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1245 __isl_keep isl_ast_node *node,
1246 __isl_keep isl_ast_print_options *options, int in_block);
1247 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1248 __isl_keep isl_ast_node *node,
1249 __isl_keep isl_ast_print_options *options, int new_line);
1251 /* Print the body "node" of a for or if node.
1252 * If "else_node" is set, then it is printed as well.
1254 * We first check if we need to print out a block.
1255 * We always print out a block if there is an else node to make
1256 * sure that the else node is matched to the correct if node.
1258 * If the else node is itself an if, then we print it as
1262 * Otherwise the else node is printed as
1267 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1268 __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1269 __isl_keep isl_ast_print_options *options)
1272 return isl_printer_free(p);
1274 if (!else_node && !need_block(node)) {
1275 p = isl_printer_end_line(p);
1276 p = isl_printer_indent(p, 2);
1277 p = isl_ast_node_print(node, p, options);
1278 p = isl_printer_indent(p, -2);
1282 p = isl_printer_print_str(p, " {");
1283 p = isl_printer_end_line(p);
1284 p = isl_printer_indent(p, 2);
1285 p = print_ast_node_c(p, node, options, 1);
1286 p = isl_printer_indent(p, -2);
1287 p = isl_printer_start_line(p);
1288 p = isl_printer_print_str(p, "}");
1290 if (else_node->type == isl_ast_node_if) {
1291 p = isl_printer_print_str(p, " else ");
1292 p = print_if_c(p, else_node, options, 0);
1294 p = isl_printer_print_str(p, " else");
1295 p = print_body_c(p, else_node, NULL, options);
1298 p = isl_printer_end_line(p);
1303 /* Print the for node "node".
1305 * If the for node is degenerate, it is printed as
1307 * type iterator = init;
1310 * Otherwise, it is printed as
1312 * for (type iterator = init; cond; iterator += inc)
1315 * "in_block" is set if we are currently inside a block.
1316 * We simply pass it along to print_ast_node_c in case of a degenerate
1319 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1320 __isl_keep isl_ast_node *node,
1321 __isl_keep isl_ast_print_options *options, int in_block)
1327 type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1328 if (!node->u.f.degenerate) {
1329 id = isl_ast_expr_get_id(node->u.f.iterator);
1330 name = isl_id_get_name(id);
1332 p = isl_printer_start_line(p);
1333 p = isl_printer_print_str(p, "for (");
1334 p = isl_printer_print_str(p, type);
1335 p = isl_printer_print_str(p, " ");
1336 p = isl_printer_print_str(p, name);
1337 p = isl_printer_print_str(p, " = ");
1338 p = isl_printer_print_ast_expr(p, node->u.f.init);
1339 p = isl_printer_print_str(p, "; ");
1340 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1341 p = isl_printer_print_str(p, "; ");
1342 p = isl_printer_print_str(p, name);
1343 p = isl_printer_print_str(p, " += ");
1344 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1345 p = isl_printer_print_str(p, ")");
1346 p = print_body_c(p, node->u.f.body, NULL, options);
1348 id = isl_ast_expr_get_id(node->u.f.iterator);
1349 name = isl_id_get_name(id);
1351 p = isl_printer_start_line(p);
1352 p = isl_printer_print_str(p, type);
1353 p = isl_printer_print_str(p, " ");
1354 p = isl_printer_print_str(p, name);
1355 p = isl_printer_print_str(p, " = ");
1356 p = isl_printer_print_ast_expr(p, node->u.f.init);
1357 p = isl_printer_print_str(p, ";");
1358 p = isl_printer_end_line(p);
1359 p = print_ast_node_c(p, node->u.f.body, options, in_block);
1365 /* Print the if node "node".
1366 * If "new_line" is set then the if node should be printed on a new line.
1368 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1369 __isl_keep isl_ast_node *node,
1370 __isl_keep isl_ast_print_options *options, int new_line)
1373 p = isl_printer_start_line(p);
1374 p = isl_printer_print_str(p, "if (");
1375 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1376 p = isl_printer_print_str(p, ")");
1377 p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1382 /* Print the "node" to "p".
1384 * "in_block" is set if we are currently inside a block.
1385 * If so, we do not print a block around the children of a block node.
1386 * We do this to avoid an extra block around the body of a degenerate
1389 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1390 __isl_keep isl_ast_node *node,
1391 __isl_keep isl_ast_print_options *options, int in_block)
1393 switch (node->type) {
1394 case isl_ast_node_for:
1395 if (options->print_for)
1396 return options->print_for(p, node,
1397 options->print_for_user);
1398 p = print_for_c(p, node, options, in_block);
1400 case isl_ast_node_if:
1401 p = print_if_c(p, node, options, 1);
1403 case isl_ast_node_block:
1405 p = isl_printer_start_line(p);
1406 p = isl_printer_print_str(p, "{");
1407 p = isl_printer_end_line(p);
1408 p = isl_printer_indent(p, 2);
1410 p = isl_ast_node_list_print(node->u.b.children, p, options);
1412 p = isl_printer_indent(p, -2);
1413 p = isl_printer_start_line(p);
1414 p = isl_printer_print_str(p, "}");
1415 p = isl_printer_end_line(p);
1418 case isl_ast_node_user:
1419 if (options->print_user)
1420 return options->print_user(p, node,
1421 options->print_user_user);
1422 p = isl_printer_start_line(p);
1423 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1424 p = isl_printer_print_str(p, ";");
1425 p = isl_printer_end_line(p);
1427 case isl_ast_node_error:
1433 /* Print the for node "node" to "p".
1435 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1436 __isl_take isl_printer *p, __isl_keep isl_ast_print_options *options)
1438 if (!node || !options)
1440 if (node->type != isl_ast_node_for)
1441 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1442 "not a for node", goto error);
1443 return print_for_c(p, node, options, 0);
1445 isl_printer_free(p);
1449 /* Print the if node "node" to "p".
1451 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1452 __isl_take isl_printer *p, __isl_keep isl_ast_print_options *options)
1454 if (!node || !options)
1456 if (node->type != isl_ast_node_if)
1457 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1458 "not an if node", goto error);
1459 return print_if_c(p, node, options, 1);
1461 isl_printer_free(p);
1465 /* Print "node" to "p".
1467 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1468 __isl_take isl_printer *p, __isl_keep isl_ast_print_options *options)
1470 if (!options || !node)
1472 return print_ast_node_c(p, node, options, 0);
1474 isl_printer_free(p);
1478 /* Print "node" to "p".
1480 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1481 __isl_keep isl_ast_node *node)
1484 isl_ast_print_options *options;
1489 format = isl_printer_get_output_format(p);
1491 case ISL_FORMAT_ISL:
1492 p = print_ast_node_isl(p, node);
1495 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
1496 p = isl_ast_node_print(node, p, options);
1497 isl_ast_print_options_free(options);
1500 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
1501 "output format not supported for ast_node",
1502 return isl_printer_free(p));
1508 /* Print the list of nodes "list" to "p".
1510 __isl_give isl_printer *isl_ast_node_list_print(
1511 __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
1512 __isl_keep isl_ast_print_options *options)
1516 if (!p || !list || !options)
1517 return isl_printer_free(p);
1519 for (i = 0; i < list->n; ++i)
1520 p = print_ast_node_c(p, list->p[i], options, 1);
1525 #define ISL_AST_MACRO_FLOORD (1 << 0)
1526 #define ISL_AST_MACRO_MIN (1 << 1)
1527 #define ISL_AST_MACRO_MAX (1 << 2)
1528 #define ISL_AST_MACRO_ALL (ISL_AST_MACRO_FLOORD | \
1529 ISL_AST_MACRO_MIN | \
1532 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1533 * then set the corresponding bit in "macros".
1535 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
1539 if (macros == ISL_AST_MACRO_ALL)
1542 if (expr->type != isl_ast_expr_op)
1545 if (expr->u.op.op == isl_ast_op_min)
1546 macros |= ISL_AST_MACRO_MIN;
1547 if (expr->u.op.op == isl_ast_op_max)
1548 macros |= ISL_AST_MACRO_MAX;
1549 if (expr->u.op.op == isl_ast_op_fdiv_q)
1550 macros |= ISL_AST_MACRO_FLOORD;
1552 for (i = 0; i < expr->u.op.n_arg; ++i)
1553 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
1558 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1561 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1562 * then set the corresponding bit in "macros".
1564 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
1566 if (macros == ISL_AST_MACRO_ALL)
1569 switch (node->type) {
1570 case isl_ast_node_for:
1571 macros = ast_expr_required_macros(node->u.f.init, macros);
1572 if (!node->u.f.degenerate) {
1573 macros = ast_expr_required_macros(node->u.f.cond,
1575 macros = ast_expr_required_macros(node->u.f.inc,
1578 macros = ast_node_required_macros(node->u.f.body, macros);
1580 case isl_ast_node_if:
1581 macros = ast_expr_required_macros(node->u.i.guard, macros);
1582 macros = ast_node_required_macros(node->u.i.then, macros);
1583 if (node->u.i.else_node)
1584 macros = ast_node_required_macros(node->u.i.else_node,
1587 case isl_ast_node_block:
1588 macros = ast_node_list_required_macros(node->u.b.children,
1591 case isl_ast_node_user:
1592 macros = ast_expr_required_macros(node->u.e.expr, macros);
1594 case isl_ast_node_error:
1601 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1602 * then set the corresponding bit in "macros".
1604 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1609 for (i = 0; i < list->n; ++i)
1610 macros = ast_node_required_macros(list->p[i], macros);
1615 /* Print a macro definition for the operator "type".
1617 __isl_give isl_printer *isl_ast_op_type_print_macro(
1618 enum isl_ast_op_type type, __isl_take isl_printer *p)
1621 case isl_ast_op_min:
1622 p = isl_printer_start_line(p);
1623 p = isl_printer_print_str(p,
1624 "#define min(x,y) ((x) < (y) ? (x) : (y))");
1625 p = isl_printer_end_line(p);
1627 case isl_ast_op_max:
1628 p = isl_printer_start_line(p);
1629 p = isl_printer_print_str(p,
1630 "#define max(x,y) ((x) > (y) ? (x) : (y))");
1631 p = isl_printer_end_line(p);
1633 case isl_ast_op_fdiv_q:
1634 p = isl_printer_start_line(p);
1635 p = isl_printer_print_str(p,
1636 "#define floord(n,d) "
1637 "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
1638 p = isl_printer_end_line(p);
1647 /* Call "fn" for each type of operation that appears in "node"
1648 * and that requires a macro definition.
1650 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
1651 int (*fn)(enum isl_ast_op_type type, void *user), void *user)
1658 macros = ast_node_required_macros(node, 0);
1660 if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
1662 if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
1664 if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
1670 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
1672 isl_printer **p = user;
1674 *p = isl_ast_op_type_print_macro(type, *p);
1679 /* Print macro definitions for all the macros used in the result
1680 * of printing "node.
1682 __isl_give isl_printer *isl_ast_node_print_macros(
1683 __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
1685 if (isl_ast_node_foreach_ast_op_type(node,
1686 &ast_op_type_print_macro, &p) < 0)
1687 return isl_printer_free(p);