?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_gmp.c: remove spurious include
[isl.git] / isl_ast.c
blob1ac5322ecbbbc19da13738e744028760ec60dbcf
1 /*
2 * Copyright 2012-2013 Ecole Normale Superieure
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
8 */
9
10 #include <isl_ast_private.h>
11
12 #undef BASE
13 #define BASE ast_expr
14
15 #include <isl_list_templ.c>
16
17 #undef BASE
18 #define BASE ast_node
19
20 #include <isl_list_templ.c>
21
22 isl_ctx *isl_ast_print_options_get_ctx(
23 __isl_keep isl_ast_print_options *options)
24 {
25 return options ? options->ctx : NULL;
26 }
27
28 __isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
29 {
30 isl_ast_print_options *options;
31
32 options = isl_calloc_type(ctx, isl_ast_print_options);
33 if (!options)
34 return NULL;
35
36 options->ctx = ctx;
37 isl_ctx_ref(ctx);
38 options->ref = 1;
39
40 return options;
41 }
42
43 __isl_give isl_ast_print_options *isl_ast_print_options_dup(
44 __isl_keep isl_ast_print_options *options)
45 {
46 isl_ctx *ctx;
47 isl_ast_print_options *dup;
48
49 if (!options)
50 return NULL;
51
52 ctx = isl_ast_print_options_get_ctx(options);
53 dup = isl_ast_print_options_alloc(ctx);
54 if (!dup)
55 return NULL;
56
57 dup->print_for = options->print_for;
58 dup->print_for_user = options->print_for_user;
59 dup->print_user = options->print_user;
60 dup->print_user_user = options->print_user_user;
61
62 return dup;
63 }
64
65 __isl_give isl_ast_print_options *isl_ast_print_options_cow(
66 __isl_take isl_ast_print_options *options)
67 {
68 if (!options)
69 return NULL;
70
71 if (options->ref == 1)
72 return options;
73 options->ref--;
74 return isl_ast_print_options_dup(options);
75 }
76
77 __isl_give isl_ast_print_options *isl_ast_print_options_copy(
78 __isl_keep isl_ast_print_options *options)
79 {
80 if (!options)
81 return NULL;
82
83 options->ref++;
84 return options;
85 }
86
87 __isl_null isl_ast_print_options *isl_ast_print_options_free(
88 __isl_take isl_ast_print_options *options)
89 {
90 if (!options)
91 return NULL;
92
93 if (--options->ref > 0)
94 return NULL;
95
96 isl_ctx_deref(options->ctx);
97
98 free(options);
99 return NULL;
100 }
101
102 /* Set the print_user callback of "options" to "print_user".
103 *
104 * If this callback is set, then it used to print user nodes in the AST.
105 * Otherwise, the expression associated to the user node is printed.
106 */
107 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_user(
108 __isl_take isl_ast_print_options *options,
109 __isl_give isl_printer *(*print_user)(__isl_take isl_printer *p,
110 __isl_take isl_ast_print_options *options,
111 __isl_keep isl_ast_node *node, void *user),
112 void *user)
113 {
114 options = isl_ast_print_options_cow(options);
115 if (!options)
116 return NULL;
117
118 options->print_user = print_user;
119 options->print_user_user = user;
120
121 return options;
122 }
123
124 /* Set the print_for callback of "options" to "print_for".
125 *
126 * If this callback is set, then it used to print for nodes in the AST.
127 */
128 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_for(
129 __isl_take isl_ast_print_options *options,
130 __isl_give isl_printer *(*print_for)(__isl_take isl_printer *p,
131 __isl_take isl_ast_print_options *options,
132 __isl_keep isl_ast_node *node, void *user),
133 void *user)
134 {
135 options = isl_ast_print_options_cow(options);
136 if (!options)
137 return NULL;
138
139 options->print_for = print_for;
140 options->print_for_user = user;
141
142 return options;
143 }
144
145 __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
146 {
147 if (!expr)
148 return NULL;
149
150 expr->ref++;
151 return expr;
152 }
153
154 __isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
155 {
156 int i;
157 isl_ctx *ctx;
158 isl_ast_expr *dup;
159
160 if (!expr)
161 return NULL;
162
163 ctx = isl_ast_expr_get_ctx(expr);
164 switch (expr->type) {
165 case isl_ast_expr_int:
166 dup = isl_ast_expr_from_val(isl_val_copy(expr->u.v));
167 break;
168 case isl_ast_expr_id:
169 dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id));
170 break;
171 case isl_ast_expr_op:
172 dup = isl_ast_expr_alloc_op(ctx,
173 expr->u.op.op, expr->u.op.n_arg);
174 if (!dup)
175 return NULL;
176 for (i = 0; i < expr->u.op.n_arg; ++i)
177 dup->u.op.args[i] =
178 isl_ast_expr_copy(expr->u.op.args[i]);
179 break;
180 case isl_ast_expr_error:
181 dup = NULL;
182 }
183
184 if (!dup)
185 return NULL;
186
187 return dup;
188 }
189
190 __isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr)
191 {
192 if (!expr)
193 return NULL;
194
195 if (expr->ref == 1)
196 return expr;
197 expr->ref--;
198 return isl_ast_expr_dup(expr);
199 }
200
201 __isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr)
202 {
203 int i;
204
205 if (!expr)
206 return NULL;
207
208 if (--expr->ref > 0)
209 return NULL;
210
211 isl_ctx_deref(expr->ctx);
212
213 switch (expr->type) {
214 case isl_ast_expr_int:
215 isl_val_free(expr->u.v);
216 break;
217 case isl_ast_expr_id:
218 isl_id_free(expr->u.id);
219 break;
220 case isl_ast_expr_op:
221 if (expr->u.op.args)
222 for (i = 0; i < expr->u.op.n_arg; ++i)
223 isl_ast_expr_free(expr->u.op.args[i]);
224 free(expr->u.op.args);
225 break;
226 case isl_ast_expr_error:
227 break;
228 }
229
230 free(expr);
231 return NULL;
232 }
233
234 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
235 {
236 return expr ? expr->ctx : NULL;
237 }
238
239 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
240 {
241 return expr ? expr->type : isl_ast_expr_error;
242 }
243
244 /* Return the integer value represented by "expr".
245 */
246 __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
247 {
248 if (!expr)
249 return NULL;
250 if (expr->type != isl_ast_expr_int)
251 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
252 "expression not an int", return NULL);
253 return isl_val_copy(expr->u.v);
254 }
255
256 __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
257 {
258 if (!expr)
259 return NULL;
260 if (expr->type != isl_ast_expr_id)
261 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
262 "expression not an identifier", return NULL);
263
264 return isl_id_copy(expr->u.id);
265 }
266
267 enum isl_ast_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
268 {
269 if (!expr)
270 return isl_ast_op_error;
271 if (expr->type != isl_ast_expr_op)
272 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
273 "expression not an operation", return isl_ast_op_error);
274 return expr->u.op.op;
275 }
276
277 int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
278 {
279 if (!expr)
280 return -1;
281 if (expr->type != isl_ast_expr_op)
282 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
283 "expression not an operation", return -1);
284 return expr->u.op.n_arg;
285 }
286
287 __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
288 int pos)
289 {
290 if (!expr)
291 return NULL;
292 if (expr->type != isl_ast_expr_op)
293 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
294 "expression not an operation", return NULL);
295 if (pos < 0 || pos >= expr->u.op.n_arg)
296 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
297 "index out of bounds", return NULL);
298
299 return isl_ast_expr_copy(expr->u.op.args[pos]);
300 }
301
302 /* Replace the argument at position "pos" of "expr" by "arg".
303 */
304 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
305 int pos, __isl_take isl_ast_expr *arg)
306 {
307 expr = isl_ast_expr_cow(expr);
308 if (!expr || !arg)
309 goto error;
310 if (expr->type != isl_ast_expr_op)
311 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
312 "expression not an operation", goto error);
313 if (pos < 0 || pos >= expr->u.op.n_arg)
314 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
315 "index out of bounds", goto error);
316
317 isl_ast_expr_free(expr->u.op.args[pos]);
318 expr->u.op.args[pos] = arg;
319
320 return expr;
321 error:
322 isl_ast_expr_free(arg);
323 return isl_ast_expr_free(expr);
324 }
325
326 /* Is "expr1" equal to "expr2"?
327 */
328 int isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
329 __isl_keep isl_ast_expr *expr2)
330 {
331 int i;
332
333 if (!expr1 || !expr2)
334 return -1;
335
336 if (expr1 == expr2)
337 return 1;
338 if (expr1->type != expr2->type)
339 return 0;
340 switch (expr1->type) {
341 case isl_ast_expr_int:
342 return isl_val_eq(expr1->u.v, expr2->u.v);
343 case isl_ast_expr_id:
344 return expr1->u.id == expr2->u.id;
345 case isl_ast_expr_op:
346 if (expr1->u.op.op != expr2->u.op.op)
347 return 0;
348 if (expr1->u.op.n_arg != expr2->u.op.n_arg)
349 return 0;
350 for (i = 0; i < expr1->u.op.n_arg; ++i) {
351 int equal;
352 equal = isl_ast_expr_is_equal(expr1->u.op.args[i],
353 expr2->u.op.args[i]);
354 return 0;
355 if (equal < 0 || !equal)
356 return equal;
357 }
358 return 1;
359 case isl_ast_expr_error:
360 return -1;
361 }
362 }
363
364 /* Create a new operation expression of operation type "op",
365 * with "n_arg" as yet unspecified arguments.
366 */
367 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
368 enum isl_ast_op_type op, int n_arg)
369 {
370 isl_ast_expr *expr;
371
372 expr = isl_calloc_type(ctx, isl_ast_expr);
373 if (!expr)
374 return NULL;
375
376 expr->ctx = ctx;
377 isl_ctx_ref(ctx);
378 expr->ref = 1;
379 expr->type = isl_ast_expr_op;
380 expr->u.op.op = op;
381 expr->u.op.n_arg = n_arg;
382 expr->u.op.args = isl_calloc_array(ctx, isl_ast_expr *, n_arg);
383
384 if (n_arg && !expr->u.op.args)
385 return isl_ast_expr_free(expr);
386
387 return expr;
388 }
389
390 /* Create a new id expression representing "id".
391 */
392 __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
393 {
394 isl_ctx *ctx;
395 isl_ast_expr *expr;
396
397 if (!id)
398 return NULL;
399
400 ctx = isl_id_get_ctx(id);
401 expr = isl_calloc_type(ctx, isl_ast_expr);
402 if (!expr)
403 goto error;
404
405 expr->ctx = ctx;
406 isl_ctx_ref(ctx);
407 expr->ref = 1;
408 expr->type = isl_ast_expr_id;
409 expr->u.id = id;
410
411 return expr;
412 error:
413 isl_id_free(id);
414 return NULL;
415 }
416
417 /* Create a new integer expression representing "i".
418 */
419 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
420 {
421 isl_ast_expr *expr;
422
423 expr = isl_calloc_type(ctx, isl_ast_expr);
424 if (!expr)
425 return NULL;
426
427 expr->ctx = ctx;
428 isl_ctx_ref(ctx);
429 expr->ref = 1;
430 expr->type = isl_ast_expr_int;
431 expr->u.v = isl_val_int_from_si(ctx, i);
432 if (!expr->u.v)
433 return isl_ast_expr_free(expr);
434
435 return expr;
436 }
437
438 /* Create a new integer expression representing "v".
439 */
440 __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
441 {
442 isl_ctx *ctx;
443 isl_ast_expr *expr;
444
445 if (!v)
446 return NULL;
447 if (!isl_val_is_int(v))
448 isl_die(isl_val_get_ctx(v), isl_error_invalid,
449 "expecting integer value", goto error);
450
451 ctx = isl_val_get_ctx(v);
452 expr = isl_calloc_type(ctx, isl_ast_expr);
453 if (!expr)
454 goto error;
455
456 expr->ctx = ctx;
457 isl_ctx_ref(ctx);
458 expr->ref = 1;
459 expr->type = isl_ast_expr_int;
460 expr->u.v = v;
461
462 return expr;
463 error:
464 isl_val_free(v);
465 return NULL;
466 }
467
468 /* Create an expression representing the negation of "arg".
469 */
470 __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg)
471 {
472 isl_ctx *ctx;
473 isl_ast_expr *expr = NULL;
474
475 if (!arg)
476 return NULL;
477
478 ctx = isl_ast_expr_get_ctx(arg);
479 expr = isl_ast_expr_alloc_op(ctx, isl_ast_op_minus, 1);
480 if (!expr)
481 goto error;
482
483 expr->u.op.args[0] = arg;
484
485 return expr;
486 error:
487 isl_ast_expr_free(arg);
488 return NULL;
489 }
490
491 /* Create an expression representing the binary operation "type"
492 * applied to "expr1" and "expr2".
493 */
494 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(enum isl_ast_op_type type,
495 __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
496 {
497 isl_ctx *ctx;
498 isl_ast_expr *expr = NULL;
499
500 if (!expr1 || !expr2)
501 goto error;
502
503 ctx = isl_ast_expr_get_ctx(expr1);
504 expr = isl_ast_expr_alloc_op(ctx, type, 2);
505 if (!expr)
506 goto error;
507
508 expr->u.op.args[0] = expr1;
509 expr->u.op.args[1] = expr2;
510
511 return expr;
512 error:
513 isl_ast_expr_free(expr1);
514 isl_ast_expr_free(expr2);
515 return NULL;
516 }
517
518 /* Create an expression representing the sum of "expr1" and "expr2".
519 */
520 __isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
521 __isl_take isl_ast_expr *expr2)
522 {
523 return isl_ast_expr_alloc_binary(isl_ast_op_add, expr1, expr2);
524 }
525
526 /* Create an expression representing the difference of "expr1" and "expr2".
527 */
528 __isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
529 __isl_take isl_ast_expr *expr2)
530 {
531 return isl_ast_expr_alloc_binary(isl_ast_op_sub, expr1, expr2);
532 }
533
534 /* Create an expression representing the product of "expr1" and "expr2".
535 */
536 __isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
537 __isl_take isl_ast_expr *expr2)
538 {
539 return isl_ast_expr_alloc_binary(isl_ast_op_mul, expr1, expr2);
540 }
541
542 /* Create an expression representing the quotient of "expr1" and "expr2".
543 */
544 __isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1,
545 __isl_take isl_ast_expr *expr2)
546 {
547 return isl_ast_expr_alloc_binary(isl_ast_op_div, expr1, expr2);
548 }
549
550 /* Create an expression representing the conjunction of "expr1" and "expr2".
551 */
552 __isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
553 __isl_take isl_ast_expr *expr2)
554 {
555 return isl_ast_expr_alloc_binary(isl_ast_op_and, expr1, expr2);
556 }
557
558 /* Create an expression representing the disjunction of "expr1" and "expr2".
559 */
560 __isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
561 __isl_take isl_ast_expr *expr2)
562 {
563 return isl_ast_expr_alloc_binary(isl_ast_op_or, expr1, expr2);
564 }
565
566 /* Create an expression representing an access to "array" with index
567 * expressions "indices".
568 */
569 __isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
570 __isl_take isl_ast_expr_list *indices)
571 {
572 int i, n;
573 isl_ctx *ctx;
574 isl_ast_expr *access = NULL;
575
576 if (!array || !indices)
577 goto error;
578
579 ctx = isl_ast_expr_get_ctx(array);
580 n = isl_ast_expr_list_n_ast_expr(indices);
581 access = isl_ast_expr_alloc_op(ctx, isl_ast_op_access, 1 + n);
582 if (!access)
583 goto error;
584 for (i = 0; i < n; ++i) {
585 isl_ast_expr *index;
586 index = isl_ast_expr_list_get_ast_expr(indices, i);
587 access->u.op.args[1 + i] = index;
588 if (!index)
589 goto error;
590 }
591 access->u.op.args[0] = array;
592
593 isl_ast_expr_list_free(indices);
594 return access;
595 error:
596 isl_ast_expr_free(array);
597 isl_ast_expr_list_free(indices);
598 isl_ast_expr_free(access);
599 return NULL;
600 }
601
602 /* For each subexpression of "expr" of type isl_ast_expr_id,
603 * if it appears in "id2expr", then replace it by the corresponding
604 * expression.
605 */
606 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
607 __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
608 {
609 int i;
610 isl_id *id;
611
612 if (!expr || !id2expr)
613 goto error;
614
615 switch (expr->type) {
616 case isl_ast_expr_int:
617 break;
618 case isl_ast_expr_id:
619 if (!isl_id_to_ast_expr_has(id2expr, expr->u.id))
620 break;
621 id = isl_id_copy(expr->u.id);
622 isl_ast_expr_free(expr);
623 expr = isl_id_to_ast_expr_get(id2expr, id);
624 break;
625 case isl_ast_expr_op:
626 for (i = 0; i < expr->u.op.n_arg; ++i) {
627 isl_ast_expr *arg;
628 arg = isl_ast_expr_copy(expr->u.op.args[i]);
629 arg = isl_ast_expr_substitute_ids(arg,
630 isl_id_to_ast_expr_copy(id2expr));
631 if (arg == expr->u.op.args[i]) {
632 isl_ast_expr_free(arg);
633 continue;
634 }
635 if (!arg)
636 expr = isl_ast_expr_free(expr);
637 expr = isl_ast_expr_cow(expr);
638 if (!expr) {
639 isl_ast_expr_free(arg);
640 break;
641 }
642 isl_ast_expr_free(expr->u.op.args[i]);
643 expr->u.op.args[i] = arg;
644 }
645 break;
646 case isl_ast_expr_error:
647 expr = isl_ast_expr_free(expr);
648 break;
649 }
650
651 isl_id_to_ast_expr_free(id2expr);
652 return expr;
653 error:
654 isl_ast_expr_free(expr);
655 isl_id_to_ast_expr_free(id2expr);
656 return NULL;
657 }
658
659 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
660 {
661 return node ? node->ctx : NULL;
662 }
663
664 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
665 {
666 return node ? node->type : isl_ast_node_error;
667 }
668
669 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
670 enum isl_ast_node_type type)
671 {
672 isl_ast_node *node;
673
674 node = isl_calloc_type(ctx, isl_ast_node);
675 if (!node)
676 return NULL;
677
678 node->ctx = ctx;
679 isl_ctx_ref(ctx);
680 node->ref = 1;
681 node->type = type;
682
683 return node;
684 }
685
686 /* Create an if node with the given guard.
687 *
688 * The then body needs to be filled in later.
689 */
690 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
691 {
692 isl_ast_node *node;
693
694 if (!guard)
695 return NULL;
696
697 node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
698 if (!node)
699 goto error;
700 node->u.i.guard = guard;
701
702 return node;
703 error:
704 isl_ast_expr_free(guard);
705 return NULL;
706 }
707
708 /* Create a for node with the given iterator.
709 *
710 * The remaining fields need to be filled in later.
711 */
712 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
713 {
714 isl_ast_node *node;
715 isl_ctx *ctx;
716
717 if (!id)
718 return NULL;
719
720 ctx = isl_id_get_ctx(id);
721 node = isl_ast_node_alloc(ctx, isl_ast_node_for);
722 if (!node)
723 goto error;
724
725 node->u.f.iterator = isl_ast_expr_from_id(id);
726 if (!node->u.f.iterator)
727 return isl_ast_node_free(node);
728
729 return node;
730 error:
731 isl_id_free(id);
732 return NULL;
733 }
734
735 /* Create a user node evaluating "expr".
736 */
737 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
738 {
739 isl_ctx *ctx;
740 isl_ast_node *node;
741
742 if (!expr)
743 return NULL;
744
745 ctx = isl_ast_expr_get_ctx(expr);
746 node = isl_ast_node_alloc(ctx, isl_ast_node_user);
747 if (!node)
748 goto error;
749
750 node->u.e.expr = expr;
751
752 return node;
753 error:
754 isl_ast_expr_free(expr);
755 return NULL;
756 }
757
758 /* Create a block node with the given children.
759 */
760 __isl_give isl_ast_node *isl_ast_node_alloc_block(
761 __isl_take isl_ast_node_list *list)
762 {
763 isl_ast_node *node;
764 isl_ctx *ctx;
765
766 if (!list)
767 return NULL;
768
769 ctx = isl_ast_node_list_get_ctx(list);
770 node = isl_ast_node_alloc(ctx, isl_ast_node_block);
771 if (!node)
772 goto error;
773
774 node->u.b.children = list;
775
776 return node;
777 error:
778 isl_ast_node_list_free(list);
779 return NULL;
780 }
781
782 /* Represent the given list of nodes as a single node, either by
783 * extract the node from a single element list or by creating
784 * a block node with the list of nodes as children.
785 */
786 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
787 __isl_take isl_ast_node_list *list)
788 {
789 isl_ast_node *node;
790
791 if (isl_ast_node_list_n_ast_node(list) != 1)
792 return isl_ast_node_alloc_block(list);
793
794 node = isl_ast_node_list_get_ast_node(list, 0);
795 isl_ast_node_list_free(list);
796
797 return node;
798 }
799
800 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
801 {
802 if (!node)
803 return NULL;
804
805 node->ref++;
806 return node;
807 }
808
809 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
810 {
811 isl_ast_node *dup;
812
813 if (!node)
814 return NULL;
815
816 dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
817 if (!dup)
818 return NULL;
819
820 switch (node->type) {
821 case isl_ast_node_if:
822 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
823 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
824 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
825 if (!dup->u.i.guard || !dup->u.i.then ||
826 (node->u.i.else_node && !dup->u.i.else_node))
827 return isl_ast_node_free(dup);
828 break;
829 case isl_ast_node_for:
830 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
831 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
832 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
833 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
834 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
835 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
836 !dup->u.f.inc || !dup->u.f.body)
837 return isl_ast_node_free(dup);
838 break;
839 case isl_ast_node_block:
840 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
841 if (!dup->u.b.children)
842 return isl_ast_node_free(dup);
843 break;
844 case isl_ast_node_user:
845 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
846 if (!dup->u.e.expr)
847 return isl_ast_node_free(dup);
848 break;
849 case isl_ast_node_error:
850 break;
851 }
852
853 return dup;
854 }
855
856 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
857 {
858 if (!node)
859 return NULL;
860
861 if (node->ref == 1)
862 return node;
863 node->ref--;
864 return isl_ast_node_dup(node);
865 }
866
867 __isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node)
868 {
869 if (!node)
870 return NULL;
871
872 if (--node->ref > 0)
873 return NULL;
874
875 switch (node->type) {
876 case isl_ast_node_if:
877 isl_ast_expr_free(node->u.i.guard);
878 isl_ast_node_free(node->u.i.then);
879 isl_ast_node_free(node->u.i.else_node);
880 break;
881 case isl_ast_node_for:
882 isl_ast_expr_free(node->u.f.iterator);
883 isl_ast_expr_free(node->u.f.init);
884 isl_ast_expr_free(node->u.f.cond);
885 isl_ast_expr_free(node->u.f.inc);
886 isl_ast_node_free(node->u.f.body);
887 break;
888 case isl_ast_node_block:
889 isl_ast_node_list_free(node->u.b.children);
890 break;
891 case isl_ast_node_user:
892 isl_ast_expr_free(node->u.e.expr);
893 break;
894 case isl_ast_node_error:
895 break;
896 }
897
898 isl_id_free(node->annotation);
899 isl_ctx_deref(node->ctx);
900 free(node);
901
902 return NULL;
903 }
904
905 /* Replace the body of the for node "node" by "body".
906 */
907 __isl_give isl_ast_node *isl_ast_node_for_set_body(
908 __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
909 {
910 node = isl_ast_node_cow(node);
911 if (!node || !body)
912 goto error;
913 if (node->type != isl_ast_node_for)
914 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
915 "not a for node", goto error);
916
917 isl_ast_node_free(node->u.f.body);
918 node->u.f.body = body;
919
920 return node;
921 error:
922 isl_ast_node_free(node);
923 isl_ast_node_free(body);
924 return NULL;
925 }
926
927 __isl_give isl_ast_node *isl_ast_node_for_get_body(
928 __isl_keep isl_ast_node *node)
929 {
930 if (!node)
931 return NULL;
932 if (node->type != isl_ast_node_for)
933 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
934 "not a for node", return NULL);
935 return isl_ast_node_copy(node->u.f.body);
936 }
937
938 /* Mark the given for node as being degenerate.
939 */
940 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
941 __isl_take isl_ast_node *node)
942 {
943 node = isl_ast_node_cow(node);
944 if (!node)
945 return NULL;
946 node->u.f.degenerate = 1;
947 return node;
948 }
949
950 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
951 {
952 if (!node)
953 return -1;
954 if (node->type != isl_ast_node_for)
955 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
956 "not a for node", return -1);
957 return node->u.f.degenerate;
958 }
959
960 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
961 __isl_keep isl_ast_node *node)
962 {
963 if (!node)
964 return NULL;
965 if (node->type != isl_ast_node_for)
966 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
967 "not a for node", return NULL);
968 return isl_ast_expr_copy(node->u.f.iterator);
969 }
970
971 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
972 __isl_keep isl_ast_node *node)
973 {
974 if (!node)
975 return NULL;
976 if (node->type != isl_ast_node_for)
977 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
978 "not a for node", return NULL);
979 return isl_ast_expr_copy(node->u.f.init);
980 }
981
982 /* Return the condition expression of the given for node.
983 *
984 * If the for node is degenerate, then the condition is not explicitly
985 * stored in the node. Instead, it is constructed as
986 *
987 * iterator <= init
988 */
989 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
990 __isl_keep isl_ast_node *node)
991 {
992 if (!node)
993 return NULL;
994 if (node->type != isl_ast_node_for)
995 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
996 "not a for node", return NULL);
997 if (!node->u.f.degenerate)
998 return isl_ast_expr_copy(node->u.f.cond);
999
1000 return isl_ast_expr_alloc_binary(isl_ast_op_le,
1001 isl_ast_expr_copy(node->u.f.iterator),
1002 isl_ast_expr_copy(node->u.f.init));
1003 }
1004
1005 /* Return the increment of the given for node.
1006 *
1007 * If the for node is degenerate, then the increment is not explicitly
1008 * stored in the node. We simply return "1".
1009 */
1010 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1011 __isl_keep isl_ast_node *node)
1012 {
1013 if (!node)
1014 return NULL;
1015 if (node->type != isl_ast_node_for)
1016 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1017 "not a for node", return NULL);
1018 if (!node->u.f.degenerate)
1019 return isl_ast_expr_copy(node->u.f.inc);
1020 return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1021 }
1022
1023 /* Replace the then branch of the if node "node" by "child".
1024 */
1025 __isl_give isl_ast_node *isl_ast_node_if_set_then(
1026 __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1027 {
1028 node = isl_ast_node_cow(node);
1029 if (!node || !child)
1030 goto error;
1031 if (node->type != isl_ast_node_if)
1032 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1033 "not an if node", goto error);
1034
1035 isl_ast_node_free(node->u.i.then);
1036 node->u.i.then = child;
1037
1038 return node;
1039 error:
1040 isl_ast_node_free(node);
1041 isl_ast_node_free(child);
1042 return NULL;
1043 }
1044
1045 __isl_give isl_ast_node *isl_ast_node_if_get_then(
1046 __isl_keep isl_ast_node *node)
1047 {
1048 if (!node)
1049 return NULL;
1050 if (node->type != isl_ast_node_if)
1051 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1052 "not an if node", return NULL);
1053 return isl_ast_node_copy(node->u.i.then);
1054 }
1055
1056 int isl_ast_node_if_has_else(
1057 __isl_keep isl_ast_node *node)
1058 {
1059 if (!node)
1060 return -1;
1061 if (node->type != isl_ast_node_if)
1062 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1063 "not an if node", return -1);
1064 return node->u.i.else_node != NULL;
1065 }
1066
1067 __isl_give isl_ast_node *isl_ast_node_if_get_else(
1068 __isl_keep isl_ast_node *node)
1069 {
1070 if (!node)
1071 return NULL;
1072 if (node->type != isl_ast_node_if)
1073 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1074 "not an if node", return NULL);
1075 return isl_ast_node_copy(node->u.i.else_node);
1076 }
1077
1078 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
1079 __isl_keep isl_ast_node *node)
1080 {
1081 if (!node)
1082 return NULL;
1083 if (node->type != isl_ast_node_if)
1084 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1085 "not a guard node", return NULL);
1086 return isl_ast_expr_copy(node->u.i.guard);
1087 }
1088
1089 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1090 __isl_keep isl_ast_node *node)
1091 {
1092 if (!node)
1093 return NULL;
1094 if (node->type != isl_ast_node_block)
1095 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1096 "not a block node", return NULL);
1097 return isl_ast_node_list_copy(node->u.b.children);
1098 }
1099
1100 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1101 __isl_keep isl_ast_node *node)
1102 {
1103 if (!node)
1104 return NULL;
1105
1106 return isl_ast_expr_copy(node->u.e.expr);
1107 }
1108
1109 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1110 {
1111 return node ? isl_id_copy(node->annotation) : NULL;
1112 }
1113
1114 /* Replace node->annotation by "annotation".
1115 */
1116 __isl_give isl_ast_node *isl_ast_node_set_annotation(
1117 __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1118 {
1119 node = isl_ast_node_cow(node);
1120 if (!node || !annotation)
1121 goto error;
1122
1123 isl_id_free(node->annotation);
1124 node->annotation = annotation;
1125
1126 return node;
1127 error:
1128 isl_id_free(annotation);
1129 return isl_ast_node_free(node);
1130 }
1131
1132 /* Textual C representation of the various operators.
1133 */
1134 static char *op_str[] = {
1135 [isl_ast_op_and] = "&&",
1136 [isl_ast_op_and_then] = "&&",
1137 [isl_ast_op_or] = "||",
1138 [isl_ast_op_or_else] = "||",
1139 [isl_ast_op_max] = "max",
1140 [isl_ast_op_min] = "min",
1141 [isl_ast_op_minus] = "-",
1142 [isl_ast_op_add] = "+",
1143 [isl_ast_op_sub] = "-",
1144 [isl_ast_op_mul] = "*",
1145 [isl_ast_op_pdiv_q] = "/",
1146 [isl_ast_op_pdiv_r] = "%",
1147 [isl_ast_op_div] = "/",
1148 [isl_ast_op_eq] = "==",
1149 [isl_ast_op_le] = "<=",
1150 [isl_ast_op_ge] = ">=",
1151 [isl_ast_op_lt] = "<",
1152 [isl_ast_op_gt] = ">",
1153 [isl_ast_op_member] = "."
1154 };
1155
1156 /* Precedence in C of the various operators.
1157 * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1158 * Lowest value means highest precedence.
1159 */
1160 static int op_prec[] = {
1161 [isl_ast_op_and] = 13,
1162 [isl_ast_op_and_then] = 13,
1163 [isl_ast_op_or] = 14,
1164 [isl_ast_op_or_else] = 14,
1165 [isl_ast_op_max] = 2,
1166 [isl_ast_op_min] = 2,
1167 [isl_ast_op_minus] = 3,
1168 [isl_ast_op_add] = 6,
1169 [isl_ast_op_sub] = 6,
1170 [isl_ast_op_mul] = 5,
1171 [isl_ast_op_div] = 5,
1172 [isl_ast_op_fdiv_q] = 2,
1173 [isl_ast_op_pdiv_q] = 5,
1174 [isl_ast_op_pdiv_r] = 5,
1175 [isl_ast_op_cond] = 15,
1176 [isl_ast_op_select] = 15,
1177 [isl_ast_op_eq] = 9,
1178 [isl_ast_op_le] = 8,
1179 [isl_ast_op_ge] = 8,
1180 [isl_ast_op_lt] = 8,
1181 [isl_ast_op_gt] = 8,
1182 [isl_ast_op_call] = 2,
1183 [isl_ast_op_access] = 2,
1184 [isl_ast_op_member] = 2
1185 };
1186
1187 /* Is the operator left-to-right associative?
1188 */
1189 static int op_left[] = {
1190 [isl_ast_op_and] = 1,
1191 [isl_ast_op_and_then] = 1,
1192 [isl_ast_op_or] = 1,
1193 [isl_ast_op_or_else] = 1,
1194 [isl_ast_op_max] = 1,
1195 [isl_ast_op_min] = 1,
1196 [isl_ast_op_minus] = 0,
1197 [isl_ast_op_add] = 1,
1198 [isl_ast_op_sub] = 1,
1199 [isl_ast_op_mul] = 1,
1200 [isl_ast_op_div] = 1,
1201 [isl_ast_op_fdiv_q] = 1,
1202 [isl_ast_op_pdiv_q] = 1,
1203 [isl_ast_op_pdiv_r] = 1,
1204 [isl_ast_op_cond] = 0,
1205 [isl_ast_op_select] = 0,
1206 [isl_ast_op_eq] = 1,
1207 [isl_ast_op_le] = 1,
1208 [isl_ast_op_ge] = 1,
1209 [isl_ast_op_lt] = 1,
1210 [isl_ast_op_gt] = 1,
1211 [isl_ast_op_call] = 1,
1212 [isl_ast_op_access] = 1,
1213 [isl_ast_op_member] = 1
1214 };
1215
1216 static int is_and(enum isl_ast_op_type op)
1217 {
1218 return op == isl_ast_op_and || op == isl_ast_op_and_then;
1219 }
1220
1221 static int is_or(enum isl_ast_op_type op)
1222 {
1223 return op == isl_ast_op_or || op == isl_ast_op_or_else;
1224 }
1225
1226 static int is_add_sub(enum isl_ast_op_type op)
1227 {
1228 return op == isl_ast_op_add || op == isl_ast_op_sub;
1229 }
1230
1231 static int is_div_mod(enum isl_ast_op_type op)
1232 {
1233 return op == isl_ast_op_div || op == isl_ast_op_pdiv_r;
1234 }
1235
1236 /* Do we need/want parentheses around "expr" as a subexpression of
1237 * an "op" operation? If "left" is set, then "expr" is the left-most
1238 * operand.
1239 *
1240 * We only need parentheses if "expr" represents an operation.
1241 *
1242 * If op has a higher precedence than expr->u.op.op, then we need
1243 * parentheses.
1244 * If op and expr->u.op.op have the same precedence, but the operations
1245 * are performed in an order that is different from the associativity,
1246 * then we need parentheses.
1247 *
1248 * An and inside an or technically does not require parentheses,
1249 * but some compilers complain about that, so we add them anyway.
1250 *
1251 * Computations such as "a / b * c" and "a % b + c" can be somewhat
1252 * difficult to read, so we add parentheses for those as well.
1253 */
1254 static int sub_expr_need_parens(enum isl_ast_op_type op,
1255 __isl_keep isl_ast_expr *expr, int left)
1256 {
1257 if (expr->type != isl_ast_expr_op)
1258 return 0;
1259
1260 if (op_prec[expr->u.op.op] > op_prec[op])
1261 return 1;
1262 if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1263 return 1;
1264
1265 if (is_or(op) && is_and(expr->u.op.op))
1266 return 1;
1267 if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1268 op_prec[expr->u.op.op] == op_prec[op])
1269 return 1;
1270 if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1271 return 1;
1272
1273 return 0;
1274 }
1275
1276 /* Print "expr" as a subexpression of an "op" operation.
1277 * If "left" is set, then "expr" is the left-most operand.
1278 */
1279 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1280 enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1281 {
1282 int need_parens;
1283
1284 need_parens = sub_expr_need_parens(op, expr, left);
1285
1286 if (need_parens)
1287 p = isl_printer_print_str(p, "(");
1288 p = isl_printer_print_ast_expr(p, expr);
1289 if (need_parens)
1290 p = isl_printer_print_str(p, ")");
1291 return p;
1292 }
1293
1294 /* Print a min or max reduction "expr".
1295 */
1296 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1297 __isl_keep isl_ast_expr *expr)
1298 {
1299 int i = 0;
1300
1301 for (i = 1; i < expr->u.op.n_arg; ++i) {
1302 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1303 p = isl_printer_print_str(p, "(");
1304 }
1305 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1306 for (i = 1; i < expr->u.op.n_arg; ++i) {
1307 p = isl_printer_print_str(p, ", ");
1308 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1309 p = isl_printer_print_str(p, ")");
1310 }
1311
1312 return p;
1313 }
1314
1315 /* Print a function call "expr".
1316 *
1317 * The first argument represents the function to be called.
1318 */
1319 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1320 __isl_keep isl_ast_expr *expr)
1321 {
1322 int i = 0;
1323
1324 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1325 p = isl_printer_print_str(p, "(");
1326 for (i = 1; i < expr->u.op.n_arg; ++i) {
1327 if (i != 1)
1328 p = isl_printer_print_str(p, ", ");
1329 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1330 }
1331 p = isl_printer_print_str(p, ")");
1332
1333 return p;
1334 }
1335
1336 /* Print an array access "expr".
1337 *
1338 * The first argument represents the array being accessed.
1339 */
1340 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
1341 __isl_keep isl_ast_expr *expr)
1342 {
1343 int i = 0;
1344
1345 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1346 for (i = 1; i < expr->u.op.n_arg; ++i) {
1347 p = isl_printer_print_str(p, "[");
1348 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1349 p = isl_printer_print_str(p, "]");
1350 }
1351
1352 return p;
1353 }
1354
1355 /* Print "expr" to "p".
1356 *
1357 * If we are printing in isl format, then we also print an indication
1358 * of the size of the expression (if it was computed).
1359 */
1360 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1361 __isl_keep isl_ast_expr *expr)
1362 {
1363 if (!p)
1364 return NULL;
1365 if (!expr)
1366 return isl_printer_free(p);
1367
1368 switch (expr->type) {
1369 case isl_ast_expr_op:
1370 if (expr->u.op.op == isl_ast_op_call) {
1371 p = print_call(p, expr);
1372 break;
1373 }
1374 if (expr->u.op.op == isl_ast_op_access) {
1375 p = print_access(p, expr);
1376 break;
1377 }
1378 if (expr->u.op.n_arg == 1) {
1379 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1380 p = print_sub_expr(p, expr->u.op.op,
1381 expr->u.op.args[0], 0);
1382 break;
1383 }
1384 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1385 p = isl_printer_print_str(p, "floord(");
1386 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1387 p = isl_printer_print_str(p, ", ");
1388 p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1389 p = isl_printer_print_str(p, ")");
1390 break;
1391 }
1392 if (expr->u.op.op == isl_ast_op_max ||
1393 expr->u.op.op == isl_ast_op_min) {
1394 p = print_min_max(p, expr);
1395 break;
1396 }
1397 if (expr->u.op.op == isl_ast_op_cond ||
1398 expr->u.op.op == isl_ast_op_select) {
1399 p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1400 p = isl_printer_print_str(p, " ? ");
1401 p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1402 p = isl_printer_print_str(p, " : ");
1403 p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1404 break;
1405 }
1406 if (expr->u.op.n_arg != 2)
1407 isl_die(isl_printer_get_ctx(p), isl_error_internal,
1408 "operation should have two arguments",
1409 goto error);
1410 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1411 if (expr->u.op.op != isl_ast_op_member)
1412 p = isl_printer_print_str(p, " ");
1413 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1414 if (expr->u.op.op != isl_ast_op_member)
1415 p = isl_printer_print_str(p, " ");
1416 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1417 break;
1418 case isl_ast_expr_id:
1419 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1420 break;
1421 case isl_ast_expr_int:
1422 p = isl_printer_print_val(p, expr->u.v);
1423 break;
1424 case isl_ast_expr_error:
1425 break;
1426 }
1427
1428 return p;
1429 error:
1430 isl_printer_free(p);
1431 return NULL;
1432 }
1433
1434 /* Print "node" to "p" in "isl format".
1435 */
1436 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1437 __isl_keep isl_ast_node *node)
1438 {
1439 p = isl_printer_print_str(p, "(");
1440 switch (node->type) {
1441 case isl_ast_node_for:
1442 if (node->u.f.degenerate) {
1443 p = isl_printer_print_ast_expr(p, node->u.f.init);
1444 } else {
1445 p = isl_printer_print_str(p, "init: ");
1446 p = isl_printer_print_ast_expr(p, node->u.f.init);
1447 p = isl_printer_print_str(p, ", ");
1448 p = isl_printer_print_str(p, "cond: ");
1449 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1450 p = isl_printer_print_str(p, ", ");
1451 p = isl_printer_print_str(p, "inc: ");
1452 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1453 }
1454 if (node->u.f.body) {
1455 p = isl_printer_print_str(p, ", ");
1456 p = isl_printer_print_str(p, "body: ");
1457 p = isl_printer_print_ast_node(p, node->u.f.body);
1458 }
1459 break;
1460 case isl_ast_node_user:
1461 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1462 break;
1463 case isl_ast_node_if:
1464 p = isl_printer_print_str(p, "guard: ");
1465 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1466 if (node->u.i.then) {
1467 p = isl_printer_print_str(p, ", ");
1468 p = isl_printer_print_str(p, "then: ");
1469 p = isl_printer_print_ast_node(p, node->u.i.then);
1470 }
1471 if (node->u.i.else_node) {
1472 p = isl_printer_print_str(p, ", ");
1473 p = isl_printer_print_str(p, "else: ");
1474 p = isl_printer_print_ast_node(p, node->u.i.else_node);
1475 }
1476 break;
1477 case isl_ast_node_block:
1478 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1479 break;
1480 default:
1481 break;
1482 }
1483 p = isl_printer_print_str(p, ")");
1484 return p;
1485 }
1486
1487 /* Do we need to print a block around the body "node" of a for or if node?
1488 *
1489 * If the node is a block, then we need to print a block.
1490 * Also if the node is a degenerate for then we will print it as
1491 * an assignment followed by the body of the for loop, so we need a block
1492 * as well.
1493 * If the node is an if node with an else, then we print a block
1494 * to avoid spurious dangling else warnings emitted by some compilers.
1495 */
1496 static int need_block(__isl_keep isl_ast_node *node)
1497 {
1498 if (node->type == isl_ast_node_block)
1499 return 1;
1500 if (node->type == isl_ast_node_for && node->u.f.degenerate)
1501 return 1;
1502 if (node->type == isl_ast_node_if && node->u.i.else_node)
1503 return 1;
1504 return 0;
1505 }
1506
1507 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1508 __isl_keep isl_ast_node *node,
1509 __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1510 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1511 __isl_keep isl_ast_node *node,
1512 __isl_keep isl_ast_print_options *options, int new_line);
1513
1514 /* Print the body "node" of a for or if node.
1515 * If "else_node" is set, then it is printed as well.
1516 *
1517 * We first check if we need to print out a block.
1518 * We always print out a block if there is an else node to make
1519 * sure that the else node is matched to the correct if node.
1520 *
1521 * If the else node is itself an if, then we print it as
1522 *
1523 * } else if (..)
1524 *
1525 * Otherwise the else node is printed as
1526 *
1527 * } else
1528 * node
1529 */
1530 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1531 __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1532 __isl_keep isl_ast_print_options *options)
1533 {
1534 if (!node)
1535 return isl_printer_free(p);
1536
1537 if (!else_node && !need_block(node)) {
1538 p = isl_printer_end_line(p);
1539 p = isl_printer_indent(p, 2);
1540 p = isl_ast_node_print(node, p,
1541 isl_ast_print_options_copy(options));
1542 p = isl_printer_indent(p, -2);
1543 return p;
1544 }
1545
1546 p = isl_printer_print_str(p, " {");
1547 p = isl_printer_end_line(p);
1548 p = isl_printer_indent(p, 2);
1549 p = print_ast_node_c(p, node, options, 1, 0);
1550 p = isl_printer_indent(p, -2);
1551 p = isl_printer_start_line(p);
1552 p = isl_printer_print_str(p, "}");
1553 if (else_node) {
1554 if (else_node->type == isl_ast_node_if) {
1555 p = isl_printer_print_str(p, " else ");
1556 p = print_if_c(p, else_node, options, 0);
1557 } else {
1558 p = isl_printer_print_str(p, " else");
1559 p = print_body_c(p, else_node, NULL, options);
1560 }
1561 } else
1562 p = isl_printer_end_line(p);
1563
1564 return p;
1565 }
1566
1567 /* Print the start of a compound statement.
1568 */
1569 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1570 {
1571 p = isl_printer_start_line(p);
1572 p = isl_printer_print_str(p, "{");
1573 p = isl_printer_end_line(p);
1574 p = isl_printer_indent(p, 2);
1575
1576 return p;
1577 }
1578
1579 /* Print the end of a compound statement.
1580 */
1581 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1582 {
1583 p = isl_printer_indent(p, -2);
1584 p = isl_printer_start_line(p);
1585 p = isl_printer_print_str(p, "}");
1586 p = isl_printer_end_line(p);
1587
1588 return p;
1589 }
1590
1591 /* Print the for node "node".
1592 *
1593 * If the for node is degenerate, it is printed as
1594 *
1595 * type iterator = init;
1596 * body
1597 *
1598 * Otherwise, it is printed as
1599 *
1600 * for (type iterator = init; cond; iterator += inc)
1601 * body
1602 *
1603 * "in_block" is set if we are currently inside a block.
1604 * "in_list" is set if the current node is not alone in the block.
1605 * If we are not in a block or if the current not is not alone in the block
1606 * then we print a block around a degenerate for loop such that the variable
1607 * declaration will not conflict with any potential other declaration
1608 * of the same variable.
1609 */
1610 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1611 __isl_keep isl_ast_node *node,
1612 __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1613 {
1614 isl_id *id;
1615 const char *name;
1616 const char *type;
1617
1618 type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1619 if (!node->u.f.degenerate) {
1620 id = isl_ast_expr_get_id(node->u.f.iterator);
1621 name = isl_id_get_name(id);
1622 isl_id_free(id);
1623 p = isl_printer_start_line(p);
1624 p = isl_printer_print_str(p, "for (");
1625 p = isl_printer_print_str(p, type);
1626 p = isl_printer_print_str(p, " ");
1627 p = isl_printer_print_str(p, name);
1628 p = isl_printer_print_str(p, " = ");
1629 p = isl_printer_print_ast_expr(p, node->u.f.init);
1630 p = isl_printer_print_str(p, "; ");
1631 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1632 p = isl_printer_print_str(p, "; ");
1633 p = isl_printer_print_str(p, name);
1634 p = isl_printer_print_str(p, " += ");
1635 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1636 p = isl_printer_print_str(p, ")");
1637 p = print_body_c(p, node->u.f.body, NULL, options);
1638 } else {
1639 id = isl_ast_expr_get_id(node->u.f.iterator);
1640 name = isl_id_get_name(id);
1641 isl_id_free(id);
1642 if (!in_block || in_list)
1643 p = start_block(p);
1644 p = isl_printer_start_line(p);
1645 p = isl_printer_print_str(p, type);
1646 p = isl_printer_print_str(p, " ");
1647 p = isl_printer_print_str(p, name);
1648 p = isl_printer_print_str(p, " = ");
1649 p = isl_printer_print_ast_expr(p, node->u.f.init);
1650 p = isl_printer_print_str(p, ";");
1651 p = isl_printer_end_line(p);
1652 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1653 if (!in_block || in_list)
1654 p = end_block(p);
1655 }
1656
1657 return p;
1658 }
1659
1660 /* Print the if node "node".
1661 * If "new_line" is set then the if node should be printed on a new line.
1662 */
1663 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1664 __isl_keep isl_ast_node *node,
1665 __isl_keep isl_ast_print_options *options, int new_line)
1666 {
1667 if (new_line)
1668 p = isl_printer_start_line(p);
1669 p = isl_printer_print_str(p, "if (");
1670 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1671 p = isl_printer_print_str(p, ")");
1672 p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1673
1674 return p;
1675 }
1676
1677 /* Print the "node" to "p".
1678 *
1679 * "in_block" is set if we are currently inside a block.
1680 * If so, we do not print a block around the children of a block node.
1681 * We do this to avoid an extra block around the body of a degenerate
1682 * for node.
1683 *
1684 * "in_list" is set if the current node is not alone in the block.
1685 */
1686 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1687 __isl_keep isl_ast_node *node,
1688 __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1689 {
1690 switch (node->type) {
1691 case isl_ast_node_for:
1692 if (options->print_for)
1693 return options->print_for(p,
1694 isl_ast_print_options_copy(options),
1695 node, options->print_for_user);
1696 p = print_for_c(p, node, options, in_block, in_list);
1697 break;
1698 case isl_ast_node_if:
1699 p = print_if_c(p, node, options, 1);
1700 break;
1701 case isl_ast_node_block:
1702 if (!in_block)
1703 p = start_block(p);
1704 p = isl_ast_node_list_print(node->u.b.children, p, options);
1705 if (!in_block)
1706 p = end_block(p);
1707 break;
1708 case isl_ast_node_user:
1709 if (options->print_user)
1710 return options->print_user(p,
1711 isl_ast_print_options_copy(options),
1712 node, options->print_user_user);
1713 p = isl_printer_start_line(p);
1714 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1715 p = isl_printer_print_str(p, ";");
1716 p = isl_printer_end_line(p);
1717 break;
1718 case isl_ast_node_error:
1719 break;
1720 }
1721 return p;
1722 }
1723
1724 /* Print the for node "node" to "p".
1725 */
1726 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1727 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1728 {
1729 if (!node || !options)
1730 goto error;
1731 if (node->type != isl_ast_node_for)
1732 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1733 "not a for node", goto error);
1734 p = print_for_c(p, node, options, 0, 0);
1735 isl_ast_print_options_free(options);
1736 return p;
1737 error:
1738 isl_ast_print_options_free(options);
1739 isl_printer_free(p);
1740 return NULL;
1741 }
1742
1743 /* Print the if node "node" to "p".
1744 */
1745 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1746 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1747 {
1748 if (!node || !options)
1749 goto error;
1750 if (node->type != isl_ast_node_if)
1751 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1752 "not an if node", goto error);
1753 p = print_if_c(p, node, options, 1);
1754 isl_ast_print_options_free(options);
1755 return p;
1756 error:
1757 isl_ast_print_options_free(options);
1758 isl_printer_free(p);
1759 return NULL;
1760 }
1761
1762 /* Print "node" to "p".
1763 */
1764 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1765 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1766 {
1767 if (!options || !node)
1768 goto error;
1769 p = print_ast_node_c(p, node, options, 0, 0);
1770 isl_ast_print_options_free(options);
1771 return p;
1772 error:
1773 isl_ast_print_options_free(options);
1774 isl_printer_free(p);
1775 return NULL;
1776 }
1777
1778 /* Print "node" to "p".
1779 */
1780 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1781 __isl_keep isl_ast_node *node)
1782 {
1783 int format;
1784 isl_ast_print_options *options;
1785
1786 if (!p)
1787 return NULL;
1788
1789 format = isl_printer_get_output_format(p);
1790 switch (format) {
1791 case ISL_FORMAT_ISL:
1792 p = print_ast_node_isl(p, node);
1793 break;
1794 case ISL_FORMAT_C:
1795 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
1796 p = isl_ast_node_print(node, p, options);
1797 break;
1798 default:
1799 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
1800 "output format not supported for ast_node",
1801 return isl_printer_free(p));
1802 }
1803
1804 return p;
1805 }
1806
1807 /* Print the list of nodes "list" to "p".
1808 */
1809 __isl_give isl_printer *isl_ast_node_list_print(
1810 __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
1811 __isl_keep isl_ast_print_options *options)
1812 {
1813 int i;
1814
1815 if (!p || !list || !options)
1816 return isl_printer_free(p);
1817
1818 for (i = 0; i < list->n; ++i)
1819 p = print_ast_node_c(p, list->p[i], options, 1, 1);
1820
1821 return p;
1822 }
1823
1824 #define ISL_AST_MACRO_FLOORD (1 << 0)
1825 #define ISL_AST_MACRO_MIN (1 << 1)
1826 #define ISL_AST_MACRO_MAX (1 << 2)
1827 #define ISL_AST_MACRO_ALL (ISL_AST_MACRO_FLOORD | \
1828 ISL_AST_MACRO_MIN | \
1829 ISL_AST_MACRO_MAX)
1830
1831 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1832 * then set the corresponding bit in "macros".
1833 */
1834 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
1835 {
1836 int i;
1837
1838 if (macros == ISL_AST_MACRO_ALL)
1839 return macros;
1840
1841 if (expr->type != isl_ast_expr_op)
1842 return macros;
1843
1844 if (expr->u.op.op == isl_ast_op_min)
1845 macros |= ISL_AST_MACRO_MIN;
1846 if (expr->u.op.op == isl_ast_op_max)
1847 macros |= ISL_AST_MACRO_MAX;
1848 if (expr->u.op.op == isl_ast_op_fdiv_q)
1849 macros |= ISL_AST_MACRO_FLOORD;
1850
1851 for (i = 0; i < expr->u.op.n_arg; ++i)
1852 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
1853
1854 return macros;
1855 }
1856
1857 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1858 int macros);
1859
1860 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1861 * then set the corresponding bit in "macros".
1862 */
1863 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
1864 {
1865 if (macros == ISL_AST_MACRO_ALL)
1866 return macros;
1867
1868 switch (node->type) {
1869 case isl_ast_node_for:
1870 macros = ast_expr_required_macros(node->u.f.init, macros);
1871 if (!node->u.f.degenerate) {
1872 macros = ast_expr_required_macros(node->u.f.cond,
1873 macros);
1874 macros = ast_expr_required_macros(node->u.f.inc,
1875 macros);
1876 }
1877 macros = ast_node_required_macros(node->u.f.body, macros);
1878 break;
1879 case isl_ast_node_if:
1880 macros = ast_expr_required_macros(node->u.i.guard, macros);
1881 macros = ast_node_required_macros(node->u.i.then, macros);
1882 if (node->u.i.else_node)
1883 macros = ast_node_required_macros(node->u.i.else_node,
1884 macros);
1885 break;
1886 case isl_ast_node_block:
1887 macros = ast_node_list_required_macros(node->u.b.children,
1888 macros);
1889 break;
1890 case isl_ast_node_user:
1891 macros = ast_expr_required_macros(node->u.e.expr, macros);
1892 break;
1893 case isl_ast_node_error:
1894 break;
1895 }
1896
1897 return macros;
1898 }
1899
1900 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1901 * then set the corresponding bit in "macros".
1902 */
1903 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1904 int macros)
1905 {
1906 int i;
1907
1908 for (i = 0; i < list->n; ++i)
1909 macros = ast_node_required_macros(list->p[i], macros);
1910
1911 return macros;
1912 }
1913
1914 /* Print a macro definition for the operator "type".
1915 */
1916 __isl_give isl_printer *isl_ast_op_type_print_macro(
1917 enum isl_ast_op_type type, __isl_take isl_printer *p)
1918 {
1919 switch (type) {
1920 case isl_ast_op_min:
1921 p = isl_printer_start_line(p);
1922 p = isl_printer_print_str(p,
1923 "#define min(x,y) ((x) < (y) ? (x) : (y))");
1924 p = isl_printer_end_line(p);
1925 break;
1926 case isl_ast_op_max:
1927 p = isl_printer_start_line(p);
1928 p = isl_printer_print_str(p,
1929 "#define max(x,y) ((x) > (y) ? (x) : (y))");
1930 p = isl_printer_end_line(p);
1931 break;
1932 case isl_ast_op_fdiv_q:
1933 p = isl_printer_start_line(p);
1934 p = isl_printer_print_str(p,
1935 "#define floord(n,d) "
1936 "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
1937 p = isl_printer_end_line(p);
1938 break;
1939 default:
1940 break;
1941 }
1942
1943 return p;
1944 }
1945
1946 /* Call "fn" for each type of operation that appears in "node"
1947 * and that requires a macro definition.
1948 */
1949 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
1950 int (*fn)(enum isl_ast_op_type type, void *user), void *user)
1951 {
1952 int macros;
1953
1954 if (!node)
1955 return -1;
1956
1957 macros = ast_node_required_macros(node, 0);
1958
1959 if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
1960 return -1;
1961 if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
1962 return -1;
1963 if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
1964 return -1;
1965
1966 return 0;
1967 }
1968
1969 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
1970 {
1971 isl_printer **p = user;
1972
1973 *p = isl_ast_op_type_print_macro(type, *p);
1974
1975 return 0;
1976 }
1977
1978 /* Print macro definitions for all the macros used in the result
1979 * of printing "node.
1980 */
1981 __isl_give isl_printer *isl_ast_node_print_macros(
1982 __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
1983 {
1984 if (isl_ast_node_foreach_ast_op_type(node,
1985 &ast_op_type_print_macro, &p) < 0)
1986 return isl_printer_free(p);
1987 return p;
1988 }
Integer set library