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