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