xref: /netbsd-src/external/mit/isl/dist/isl_ast.c (revision 5971e316fdea024efff6be8f03536623db06833e)
1 /*
2  * Copyright 2012-2013 Ecole Normale Superieure
3  * Copyright 2022      Cerebras Systems
4  *
5  * Use of this software is governed by the MIT license
6  *
7  * Written by Sven Verdoolaege,
8  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9  * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
10  */
11 
12 #include <string.h>
13 
14 #include <isl/id.h>
15 #include <isl/stream.h>
16 #include <isl/val.h>
17 #include <isl_ast_private.h>
18 
19 #undef EL_BASE
20 #define EL_BASE ast_expr
21 
22 #include <isl_list_templ.c>
23 
24 #undef EL_BASE
25 #define EL_BASE ast_node
26 
27 #include <isl_list_templ.c>
28 
isl_ast_print_options_get_ctx(__isl_keep isl_ast_print_options * options)29 isl_ctx *isl_ast_print_options_get_ctx(
30 	__isl_keep isl_ast_print_options *options)
31 {
32 	return options ? options->ctx : NULL;
33 }
34 
isl_ast_print_options_alloc(isl_ctx * ctx)35 __isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
36 {
37 	isl_ast_print_options *options;
38 
39 	options = isl_calloc_type(ctx, isl_ast_print_options);
40 	if (!options)
41 		return NULL;
42 
43 	options->ctx = ctx;
44 	isl_ctx_ref(ctx);
45 	options->ref = 1;
46 
47 	return options;
48 }
49 
isl_ast_print_options_dup(__isl_keep isl_ast_print_options * options)50 __isl_give isl_ast_print_options *isl_ast_print_options_dup(
51 	__isl_keep isl_ast_print_options *options)
52 {
53 	isl_ctx *ctx;
54 	isl_ast_print_options *dup;
55 
56 	if (!options)
57 		return NULL;
58 
59 	ctx = isl_ast_print_options_get_ctx(options);
60 	dup = isl_ast_print_options_alloc(ctx);
61 	if (!dup)
62 		return NULL;
63 
64 	dup->print_for = options->print_for;
65 	dup->print_for_user = options->print_for_user;
66 	dup->print_user = options->print_user;
67 	dup->print_user_user = options->print_user_user;
68 
69 	return dup;
70 }
71 
isl_ast_print_options_cow(__isl_take isl_ast_print_options * options)72 __isl_give isl_ast_print_options *isl_ast_print_options_cow(
73 	__isl_take isl_ast_print_options *options)
74 {
75 	if (!options)
76 		return NULL;
77 
78 	if (options->ref == 1)
79 		return options;
80 	options->ref--;
81 	return isl_ast_print_options_dup(options);
82 }
83 
isl_ast_print_options_copy(__isl_keep isl_ast_print_options * options)84 __isl_give isl_ast_print_options *isl_ast_print_options_copy(
85 	__isl_keep isl_ast_print_options *options)
86 {
87 	if (!options)
88 		return NULL;
89 
90 	options->ref++;
91 	return options;
92 }
93 
isl_ast_print_options_free(__isl_take isl_ast_print_options * options)94 __isl_null isl_ast_print_options *isl_ast_print_options_free(
95 	__isl_take isl_ast_print_options *options)
96 {
97 	if (!options)
98 		return NULL;
99 
100 	if (--options->ref > 0)
101 		return NULL;
102 
103 	isl_ctx_deref(options->ctx);
104 
105 	free(options);
106 	return NULL;
107 }
108 
109 /* Set the print_user callback of "options" to "print_user".
110  *
111  * If this callback is set, then it is used to print user nodes in the AST.
112  * Otherwise, the expression associated to the user node is printed.
113  */
isl_ast_print_options_set_print_user(__isl_take isl_ast_print_options * options,__isl_give isl_printer * (* print_user)(__isl_take isl_printer * p,__isl_take isl_ast_print_options * options,__isl_keep isl_ast_node * node,void * user),void * user)114 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_user(
115 	__isl_take isl_ast_print_options *options,
116 	__isl_give isl_printer *(*print_user)(__isl_take isl_printer *p,
117 		__isl_take isl_ast_print_options *options,
118 		__isl_keep isl_ast_node *node, void *user),
119 	void *user)
120 {
121 	options = isl_ast_print_options_cow(options);
122 	if (!options)
123 		return NULL;
124 
125 	options->print_user = print_user;
126 	options->print_user_user = user;
127 
128 	return options;
129 }
130 
131 /* Set the print_for callback of "options" to "print_for".
132  *
133  * If this callback is set, then it used to print for nodes in the AST.
134  */
isl_ast_print_options_set_print_for(__isl_take isl_ast_print_options * options,__isl_give isl_printer * (* print_for)(__isl_take isl_printer * p,__isl_take isl_ast_print_options * options,__isl_keep isl_ast_node * node,void * user),void * user)135 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_for(
136 	__isl_take isl_ast_print_options *options,
137 	__isl_give isl_printer *(*print_for)(__isl_take isl_printer *p,
138 		__isl_take isl_ast_print_options *options,
139 		__isl_keep isl_ast_node *node, void *user),
140 	void *user)
141 {
142 	options = isl_ast_print_options_cow(options);
143 	if (!options)
144 		return NULL;
145 
146 	options->print_for = print_for;
147 	options->print_for_user = user;
148 
149 	return options;
150 }
151 
152 /* Create a new operation expression of operation type "op",
153  * with arguments "args".
154  */
alloc_op(enum isl_ast_expr_op_type op,__isl_take isl_ast_expr_list * args)155 static __isl_give isl_ast_expr *alloc_op(enum isl_ast_expr_op_type op,
156 	__isl_take isl_ast_expr_list *args)
157 {
158 	isl_ctx *ctx;
159 	isl_ast_expr *expr;
160 
161 	if (!args)
162 		return NULL;
163 
164 	ctx = isl_ast_expr_list_get_ctx(args);
165 	expr = isl_calloc_type(ctx, isl_ast_expr);
166 	if (!expr)
167 		goto error;
168 
169 	expr->ctx = ctx;
170 	isl_ctx_ref(ctx);
171 	expr->ref = 1;
172 	expr->type = isl_ast_expr_op;
173 	expr->u.op.op = op;
174 	expr->u.op.args = args;
175 
176 	return expr;
177 error:
178 	isl_ast_expr_list_free(args);
179 	return NULL;
180 }
181 
182 /* Create a new operation expression of operation type "op",
183  * which will end up having "n_arg" arguments.
184  * The caller still needs to add those arguments.
185  */
isl_ast_expr_alloc_op(isl_ctx * ctx,enum isl_ast_expr_op_type op,int n_arg)186 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
187 	enum isl_ast_expr_op_type op, int n_arg)
188 {
189 	isl_ast_expr_list *args;
190 
191 	args = isl_ast_expr_list_alloc(ctx, n_arg);
192 	return alloc_op(op, args);
193 }
194 
isl_ast_expr_copy(__isl_keep isl_ast_expr * expr)195 __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
196 {
197 	if (!expr)
198 		return NULL;
199 
200 	expr->ref++;
201 	return expr;
202 }
203 
isl_ast_expr_dup(__isl_keep isl_ast_expr * expr)204 __isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
205 {
206 	isl_ast_expr *dup;
207 
208 	if (!expr)
209 		return NULL;
210 
211 	switch (expr->type) {
212 	case isl_ast_expr_int:
213 		dup = isl_ast_expr_from_val(isl_val_copy(expr->u.v));
214 		break;
215 	case isl_ast_expr_id:
216 		dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id));
217 		break;
218 	case isl_ast_expr_op:
219 		dup = alloc_op(expr->u.op.op,
220 				isl_ast_expr_list_copy(expr->u.op.args));
221 		break;
222 	case isl_ast_expr_error:
223 		dup = NULL;
224 	}
225 
226 	if (!dup)
227 		return NULL;
228 
229 	return dup;
230 }
231 
isl_ast_expr_cow(__isl_take isl_ast_expr * expr)232 __isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr)
233 {
234 	if (!expr)
235 		return NULL;
236 
237 	if (expr->ref == 1)
238 		return expr;
239 	expr->ref--;
240 	return isl_ast_expr_dup(expr);
241 }
242 
isl_ast_expr_free(__isl_take isl_ast_expr * expr)243 __isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr)
244 {
245 	if (!expr)
246 		return NULL;
247 
248 	if (--expr->ref > 0)
249 		return NULL;
250 
251 	isl_ctx_deref(expr->ctx);
252 
253 	switch (expr->type) {
254 	case isl_ast_expr_int:
255 		isl_val_free(expr->u.v);
256 		break;
257 	case isl_ast_expr_id:
258 		isl_id_free(expr->u.id);
259 		break;
260 	case isl_ast_expr_op:
261 		isl_ast_expr_list_free(expr->u.op.args);
262 		break;
263 	case isl_ast_expr_error:
264 		break;
265 	}
266 
267 	free(expr);
268 	return NULL;
269 }
270 
isl_ast_expr_get_ctx(__isl_keep isl_ast_expr * expr)271 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
272 {
273 	return expr ? expr->ctx : NULL;
274 }
275 
isl_ast_expr_get_type(__isl_keep isl_ast_expr * expr)276 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
277 {
278 	return expr ? expr->type : isl_ast_expr_error;
279 }
280 
281 /* Return the integer value represented by "expr".
282  */
isl_ast_expr_int_get_val(__isl_keep isl_ast_expr * expr)283 __isl_give isl_val *isl_ast_expr_int_get_val(__isl_keep isl_ast_expr *expr)
284 {
285 	if (!expr)
286 		return NULL;
287 	if (expr->type != isl_ast_expr_int)
288 		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
289 			"expression not an int", return NULL);
290 	return isl_val_copy(expr->u.v);
291 }
292 
293 /* This is an alternative name for the function above.
294  */
isl_ast_expr_get_val(__isl_keep isl_ast_expr * expr)295 __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
296 {
297 	return isl_ast_expr_int_get_val(expr);
298 }
299 
isl_ast_expr_id_get_id(__isl_keep isl_ast_expr * expr)300 __isl_give isl_id *isl_ast_expr_id_get_id(__isl_keep isl_ast_expr *expr)
301 {
302 	if (!expr)
303 		return NULL;
304 	if (expr->type != isl_ast_expr_id)
305 		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
306 			"expression not an identifier", return NULL);
307 
308 	return isl_id_copy(expr->u.id);
309 }
310 
311 /* This is an alternative name for the function above.
312  */
isl_ast_expr_get_id(__isl_keep isl_ast_expr * expr)313 __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
314 {
315 	return isl_ast_expr_id_get_id(expr);
316 }
317 
318 /* Check that "expr" is of type isl_ast_expr_op.
319  */
isl_ast_expr_check_op(__isl_keep isl_ast_expr * expr)320 static isl_stat isl_ast_expr_check_op(__isl_keep isl_ast_expr *expr)
321 {
322 	if (!expr)
323 		return isl_stat_error;
324 	if (expr->type != isl_ast_expr_op)
325 		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
326 			"expression not an operation", return isl_stat_error);
327 	return isl_stat_ok;
328 }
329 
330 /* Return the type of operation represented by "expr".
331  */
isl_ast_expr_op_get_type(__isl_keep isl_ast_expr * expr)332 enum isl_ast_expr_op_type isl_ast_expr_op_get_type(
333 	__isl_keep isl_ast_expr *expr)
334 {
335 	if (isl_ast_expr_check_op(expr) < 0)
336 		return isl_ast_expr_op_error;
337 	return expr->u.op.op;
338 }
339 
340 /* This is an alternative name for the function above.
341  */
isl_ast_expr_get_op_type(__isl_keep isl_ast_expr * expr)342 enum isl_ast_expr_op_type isl_ast_expr_get_op_type(
343 	__isl_keep isl_ast_expr *expr)
344 {
345 	return isl_ast_expr_op_get_type(expr);
346 }
347 
348 /* Return the number of arguments of the operation represented by "expr".
349  */
isl_ast_expr_op_get_n_arg(__isl_keep isl_ast_expr * expr)350 isl_size isl_ast_expr_op_get_n_arg(__isl_keep isl_ast_expr *expr)
351 {
352 	if (isl_ast_expr_check_op(expr) < 0)
353 		return isl_size_error;
354 	return isl_ast_expr_list_size(expr->u.op.args);
355 }
356 
357 /* This is an alternative name for the function above.
358  */
isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr * expr)359 isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
360 {
361 	return isl_ast_expr_op_get_n_arg(expr);
362 }
363 
364 /* Return the argument at position "pos" of the operation represented by "expr".
365  */
isl_ast_expr_op_get_arg(__isl_keep isl_ast_expr * expr,int pos)366 __isl_give isl_ast_expr *isl_ast_expr_op_get_arg(__isl_keep isl_ast_expr *expr,
367 	int pos)
368 {
369 	if (isl_ast_expr_check_op(expr) < 0)
370 		return NULL;
371 
372 	return isl_ast_expr_list_get_at(expr->u.op.args, pos);
373 }
374 
375 /* This is an alternative name for the function above.
376  */
isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr * expr,int pos)377 __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
378 	int pos)
379 {
380 	return isl_ast_expr_op_get_arg(expr, pos);
381 }
382 
383 /* Return a copy of the arguments of the operation represented by "expr".
384  */
isl_ast_expr_op_get_args(__isl_keep isl_ast_expr * expr)385 static __isl_give isl_ast_expr_list *isl_ast_expr_op_get_args(
386 	__isl_keep isl_ast_expr *expr)
387 {
388 	if (isl_ast_expr_check_op(expr) < 0)
389 		return NULL;
390 	return isl_ast_expr_list_copy(expr->u.op.args);
391 }
392 
393 /* Return the arguments of the operation expression "expr".
394  * This may be either a copy or the arguments themselves
395  * if there is only one reference to "expr".
396  * This allows the arguments to be modified inplace
397  * if both "expr" and its arguments have only a single reference.
398  * The caller is not allowed to modify "expr" between this call and
399  * the subsequent call to isl_ast_expr_op_restore_args.
400  * The only exception is that isl_ast_expr_free can be called instead.
401  */
isl_ast_expr_op_take_args(__isl_keep isl_ast_expr * expr)402 static __isl_give isl_ast_expr_list *isl_ast_expr_op_take_args(
403 	__isl_keep isl_ast_expr *expr)
404 {
405 	isl_ast_expr_list *args;
406 
407 	if (isl_ast_expr_check_op(expr) < 0)
408 		return NULL;
409 	if (expr->ref != 1)
410 		return isl_ast_expr_op_get_args(expr);
411 	args = expr->u.op.args;
412 	expr->u.op.args = NULL;
413 	return args;
414 }
415 
416 /* Set the arguments of the operation expression "expr" to "args",
417  * where the arguments of "args" may be missing
418  * due to a preceding call to isl_ast_expr_op_take_args.
419  * However, in this case, "expr" only has a single reference and
420  * then the call to isl_ast_expr_cow has no effect.
421  */
isl_ast_expr_op_restore_args(__isl_take isl_ast_expr * expr,__isl_take isl_ast_expr_list * args)422 static __isl_give isl_ast_expr *isl_ast_expr_op_restore_args(
423 	__isl_take isl_ast_expr *expr, __isl_take isl_ast_expr_list *args)
424 {
425 	if (isl_ast_expr_check_op(expr) < 0 || !args)
426 		goto error;
427 	if (expr->u.op.args == args) {
428 		isl_ast_expr_list_free(args);
429 		return expr;
430 	}
431 
432 	expr = isl_ast_expr_cow(expr);
433 	if (!expr)
434 		goto error;
435 
436 	isl_ast_expr_list_free(expr->u.op.args);
437 	expr->u.op.args = args;
438 
439 	return expr;
440 error:
441 	isl_ast_expr_free(expr);
442 	isl_ast_expr_list_free(args);
443 	return NULL;
444 }
445 
446 /* Add "arg" to the arguments of the operation expression "expr".
447  */
isl_ast_expr_op_add_arg(__isl_take isl_ast_expr * expr,__isl_take isl_ast_expr * arg)448 __isl_give isl_ast_expr *isl_ast_expr_op_add_arg(__isl_take isl_ast_expr *expr,
449 	__isl_take isl_ast_expr *arg)
450 {
451 	isl_ast_expr_list *args;
452 
453 	args = isl_ast_expr_op_take_args(expr);
454 	args = isl_ast_expr_list_add(args, arg);
455 	expr = isl_ast_expr_op_restore_args(expr, args);
456 
457 	return expr;
458 }
459 
460 /* Replace the argument at position "pos" of "expr" by "arg".
461  */
isl_ast_expr_set_op_arg(__isl_take isl_ast_expr * expr,int pos,__isl_take isl_ast_expr * arg)462 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
463 	int pos, __isl_take isl_ast_expr *arg)
464 {
465 	isl_ast_expr_list *args;
466 
467 	args = isl_ast_expr_op_take_args(expr);
468 	args = isl_ast_expr_list_set_at(args, pos, arg);
469 	expr = isl_ast_expr_op_restore_args(expr, args);
470 
471 	return expr;
472 }
473 
474 /* Are the lists of AST expressions "list1" and "list2" the same?
475  */
isl_ast_expr_list_is_equal(__isl_keep isl_ast_expr_list * list1,__isl_keep isl_ast_expr_list * list2)476 static isl_bool isl_ast_expr_list_is_equal(__isl_keep isl_ast_expr_list *list1,
477 	__isl_keep isl_ast_expr_list *list2)
478 {
479 	int i;
480 	isl_size n1, n2;
481 
482 	if (!list1 || !list2)
483 		return isl_bool_error;
484 	if (list1 == list2)
485 		return isl_bool_true;
486 
487 	n1 = isl_ast_expr_list_size(list1);
488 	n2 = isl_ast_expr_list_size(list2);
489 	if (n1 < 0 || n2 < 0)
490 		return isl_bool_error;
491 	if (n1 != n2)
492 		return isl_bool_false;
493 	for (i = 0; i < n1; ++i) {
494 		isl_ast_expr *expr1, *expr2;
495 		isl_bool equal;
496 
497 		expr1 = isl_ast_expr_list_get_at(list1, i);
498 		expr2 = isl_ast_expr_list_get_at(list2, i);
499 		equal = isl_ast_expr_is_equal(expr1, expr2);
500 		isl_ast_expr_free(expr1);
501 		isl_ast_expr_free(expr2);
502 		if (equal < 0 || !equal)
503 			return equal;
504 	}
505 
506 	return isl_bool_true;
507 }
508 
509 /* Is "expr1" equal to "expr2"?
510  */
isl_ast_expr_is_equal(__isl_keep isl_ast_expr * expr1,__isl_keep isl_ast_expr * expr2)511 isl_bool isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
512 	__isl_keep isl_ast_expr *expr2)
513 {
514 	if (!expr1 || !expr2)
515 		return isl_bool_error;
516 
517 	if (expr1 == expr2)
518 		return isl_bool_true;
519 	if (expr1->type != expr2->type)
520 		return isl_bool_false;
521 	switch (expr1->type) {
522 	case isl_ast_expr_int:
523 		return isl_val_eq(expr1->u.v, expr2->u.v);
524 	case isl_ast_expr_id:
525 		return isl_bool_ok(expr1->u.id == expr2->u.id);
526 	case isl_ast_expr_op:
527 		if (expr1->u.op.op != expr2->u.op.op)
528 			return isl_bool_false;
529 		return isl_ast_expr_list_is_equal(expr1->u.op.args,
530 						expr2->u.op.args);
531 	case isl_ast_expr_error:
532 		return isl_bool_error;
533 	}
534 
535 	isl_die(isl_ast_expr_get_ctx(expr1), isl_error_internal,
536 		"unhandled case", return isl_bool_error);
537 }
538 
539 /* Create a new id expression representing "id".
540  */
isl_ast_expr_from_id(__isl_take isl_id * id)541 __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
542 {
543 	isl_ctx *ctx;
544 	isl_ast_expr *expr;
545 
546 	if (!id)
547 		return NULL;
548 
549 	ctx = isl_id_get_ctx(id);
550 	expr = isl_calloc_type(ctx, isl_ast_expr);
551 	if (!expr)
552 		goto error;
553 
554 	expr->ctx = ctx;
555 	isl_ctx_ref(ctx);
556 	expr->ref = 1;
557 	expr->type = isl_ast_expr_id;
558 	expr->u.id = id;
559 
560 	return expr;
561 error:
562 	isl_id_free(id);
563 	return NULL;
564 }
565 
566 /* Create a new integer expression representing "i".
567  */
isl_ast_expr_alloc_int_si(isl_ctx * ctx,int i)568 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
569 {
570 	isl_ast_expr *expr;
571 
572 	expr = isl_calloc_type(ctx, isl_ast_expr);
573 	if (!expr)
574 		return NULL;
575 
576 	expr->ctx = ctx;
577 	isl_ctx_ref(ctx);
578 	expr->ref = 1;
579 	expr->type = isl_ast_expr_int;
580 	expr->u.v = isl_val_int_from_si(ctx, i);
581 	if (!expr->u.v)
582 		return isl_ast_expr_free(expr);
583 
584 	return expr;
585 }
586 
587 /* Create a new integer expression representing "v".
588  */
isl_ast_expr_from_val(__isl_take isl_val * v)589 __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
590 {
591 	isl_ctx *ctx;
592 	isl_ast_expr *expr;
593 
594 	if (!v)
595 		return NULL;
596 	if (!isl_val_is_int(v))
597 		isl_die(isl_val_get_ctx(v), isl_error_invalid,
598 			"expecting integer value", goto error);
599 
600 	ctx = isl_val_get_ctx(v);
601 	expr = isl_calloc_type(ctx, isl_ast_expr);
602 	if (!expr)
603 		goto error;
604 
605 	expr->ctx = ctx;
606 	isl_ctx_ref(ctx);
607 	expr->ref = 1;
608 	expr->type = isl_ast_expr_int;
609 	expr->u.v = v;
610 
611 	return expr;
612 error:
613 	isl_val_free(v);
614 	return NULL;
615 }
616 
617 /* Create an expression representing the unary operation "type" applied to
618  * "arg".
619  */
isl_ast_expr_alloc_unary(enum isl_ast_expr_op_type type,__isl_take isl_ast_expr * arg)620 __isl_give isl_ast_expr *isl_ast_expr_alloc_unary(
621 	enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg)
622 {
623 	isl_ctx *ctx;
624 	isl_ast_expr *expr = NULL;
625 	isl_ast_expr_list *args;
626 
627 	if (!arg)
628 		return NULL;
629 
630 	ctx = isl_ast_expr_get_ctx(arg);
631 	expr = isl_ast_expr_alloc_op(ctx, type, 1);
632 
633 	args = isl_ast_expr_op_take_args(expr);
634 	args = isl_ast_expr_list_add(args, arg);
635 	expr = isl_ast_expr_op_restore_args(expr, args);
636 
637 	return expr;
638 }
639 
640 /* Create an expression representing the negation of "arg".
641  */
isl_ast_expr_neg(__isl_take isl_ast_expr * arg)642 __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg)
643 {
644 	return isl_ast_expr_alloc_unary(isl_ast_expr_op_minus, arg);
645 }
646 
647 /* Create an expression representing the address of "expr".
648  */
isl_ast_expr_address_of(__isl_take isl_ast_expr * expr)649 __isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
650 {
651 	if (!expr)
652 		return NULL;
653 
654 	if (isl_ast_expr_get_type(expr) != isl_ast_expr_op ||
655 	    isl_ast_expr_get_op_type(expr) != isl_ast_expr_op_access)
656 		isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
657 			"can only take address of access expressions",
658 			return isl_ast_expr_free(expr));
659 
660 	return isl_ast_expr_alloc_unary(isl_ast_expr_op_address_of, expr);
661 }
662 
663 /* Create an expression representing the binary operation "type"
664  * applied to "expr1" and "expr2".
665  */
isl_ast_expr_alloc_binary(enum isl_ast_expr_op_type type,__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)666 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(
667 	enum isl_ast_expr_op_type type,
668 	__isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
669 {
670 	isl_ctx *ctx;
671 	isl_ast_expr *expr = NULL;
672 	isl_ast_expr_list *args;
673 
674 	if (!expr1 || !expr2)
675 		goto error;
676 
677 	ctx = isl_ast_expr_get_ctx(expr1);
678 	expr = isl_ast_expr_alloc_op(ctx, type, 2);
679 
680 	args = isl_ast_expr_op_take_args(expr);
681 	args = isl_ast_expr_list_add(args, expr1);
682 	args = isl_ast_expr_list_add(args, expr2);
683 	expr = isl_ast_expr_op_restore_args(expr, args);
684 
685 	return expr;
686 error:
687 	isl_ast_expr_free(expr1);
688 	isl_ast_expr_free(expr2);
689 	return NULL;
690 }
691 
692 /* Create an expression representing the sum of "expr1" and "expr2".
693  */
isl_ast_expr_add(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)694 __isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
695 	__isl_take isl_ast_expr *expr2)
696 {
697 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_add, expr1, expr2);
698 }
699 
700 /* Create an expression representing the difference of "expr1" and "expr2".
701  */
isl_ast_expr_sub(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)702 __isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
703 	__isl_take isl_ast_expr *expr2)
704 {
705 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_sub, expr1, expr2);
706 }
707 
708 /* Create an expression representing the product of "expr1" and "expr2".
709  */
isl_ast_expr_mul(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)710 __isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
711 	__isl_take isl_ast_expr *expr2)
712 {
713 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_mul, expr1, expr2);
714 }
715 
716 /* Create an expression representing the quotient of "expr1" and "expr2".
717  */
isl_ast_expr_div(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)718 __isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1,
719 	__isl_take isl_ast_expr *expr2)
720 {
721 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_div, expr1, expr2);
722 }
723 
724 /* Create an expression representing the quotient of the integer
725  * division of "expr1" by "expr2", where "expr1" is known to be
726  * non-negative.
727  */
isl_ast_expr_pdiv_q(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)728 __isl_give isl_ast_expr *isl_ast_expr_pdiv_q(__isl_take isl_ast_expr *expr1,
729 	__isl_take isl_ast_expr *expr2)
730 {
731 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_q, expr1, expr2);
732 }
733 
734 /* Create an expression representing the remainder of the integer
735  * division of "expr1" by "expr2", where "expr1" is known to be
736  * non-negative.
737  */
isl_ast_expr_pdiv_r(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)738 __isl_give isl_ast_expr *isl_ast_expr_pdiv_r(__isl_take isl_ast_expr *expr1,
739 	__isl_take isl_ast_expr *expr2)
740 {
741 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_r, expr1, expr2);
742 }
743 
744 /* Create an expression representing the conjunction of "expr1" and "expr2".
745  */
isl_ast_expr_and(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)746 __isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
747 	__isl_take isl_ast_expr *expr2)
748 {
749 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_and, expr1, expr2);
750 }
751 
752 /* Create an expression representing the conjunction of "expr1" and "expr2",
753  * where "expr2" is evaluated only if "expr1" is evaluated to true.
754  */
isl_ast_expr_and_then(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)755 __isl_give isl_ast_expr *isl_ast_expr_and_then(__isl_take isl_ast_expr *expr1,
756 	__isl_take isl_ast_expr *expr2)
757 {
758 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_and_then, expr1, expr2);
759 }
760 
761 /* Create an expression representing the disjunction of "expr1" and "expr2".
762  */
isl_ast_expr_or(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)763 __isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
764 	__isl_take isl_ast_expr *expr2)
765 {
766 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_or, expr1, expr2);
767 }
768 
769 /* Create an expression representing the disjunction of "expr1" and "expr2",
770  * where "expr2" is evaluated only if "expr1" is evaluated to false.
771  */
isl_ast_expr_or_else(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)772 __isl_give isl_ast_expr *isl_ast_expr_or_else(__isl_take isl_ast_expr *expr1,
773 	__isl_take isl_ast_expr *expr2)
774 {
775 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_or_else, expr1, expr2);
776 }
777 
778 /* Create an expression representing "expr1" less than or equal to "expr2".
779  */
isl_ast_expr_le(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)780 __isl_give isl_ast_expr *isl_ast_expr_le(__isl_take isl_ast_expr *expr1,
781 	__isl_take isl_ast_expr *expr2)
782 {
783 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_le, expr1, expr2);
784 }
785 
786 /* Create an expression representing "expr1" less than "expr2".
787  */
isl_ast_expr_lt(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)788 __isl_give isl_ast_expr *isl_ast_expr_lt(__isl_take isl_ast_expr *expr1,
789 	__isl_take isl_ast_expr *expr2)
790 {
791 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_lt, expr1, expr2);
792 }
793 
794 /* Create an expression representing "expr1" greater than or equal to "expr2".
795  */
isl_ast_expr_ge(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)796 __isl_give isl_ast_expr *isl_ast_expr_ge(__isl_take isl_ast_expr *expr1,
797 	__isl_take isl_ast_expr *expr2)
798 {
799 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_ge, expr1, expr2);
800 }
801 
802 /* Create an expression representing "expr1" greater than "expr2".
803  */
isl_ast_expr_gt(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)804 __isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1,
805 	__isl_take isl_ast_expr *expr2)
806 {
807 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_gt, expr1, expr2);
808 }
809 
810 /* Create an expression representing "expr1" equal to "expr2".
811  */
isl_ast_expr_eq(__isl_take isl_ast_expr * expr1,__isl_take isl_ast_expr * expr2)812 __isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1,
813 	__isl_take isl_ast_expr *expr2)
814 {
815 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_eq, expr1, expr2);
816 }
817 
818 /* Create an expression of type "type" with as arguments "arg0" followed
819  * by "arguments".
820  */
ast_expr_with_arguments(enum isl_ast_expr_op_type type,__isl_take isl_ast_expr * arg0,__isl_take isl_ast_expr_list * arguments)821 static __isl_give isl_ast_expr *ast_expr_with_arguments(
822 	enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg0,
823 	__isl_take isl_ast_expr_list *arguments)
824 {
825 	arguments = isl_ast_expr_list_insert(arguments, 0, arg0);
826 	return alloc_op(type, arguments);
827 }
828 
829 /* Create an expression representing an access to "array" with index
830  * expressions "indices".
831  */
isl_ast_expr_access(__isl_take isl_ast_expr * array,__isl_take isl_ast_expr_list * indices)832 __isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
833 	__isl_take isl_ast_expr_list *indices)
834 {
835 	return ast_expr_with_arguments(isl_ast_expr_op_access, array, indices);
836 }
837 
838 /* Create an expression representing a call to "function" with argument
839  * expressions "arguments".
840  */
isl_ast_expr_call(__isl_take isl_ast_expr * function,__isl_take isl_ast_expr_list * arguments)841 __isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function,
842 	__isl_take isl_ast_expr_list *arguments)
843 {
844 	return ast_expr_with_arguments(isl_ast_expr_op_call, function, arguments);
845 }
846 
847 /* Wrapper around isl_ast_expr_substitute_ids for use
848  * as an isl_ast_expr_list_map callback.
849  */
substitute_ids(__isl_take isl_ast_expr * expr,void * user)850 static __isl_give isl_ast_expr *substitute_ids(__isl_take isl_ast_expr *expr,
851 	void *user)
852 {
853 	isl_id_to_ast_expr *id2expr = user;
854 
855 	return isl_ast_expr_substitute_ids(expr,
856 					    isl_id_to_ast_expr_copy(id2expr));
857 }
858 
859 /* For each subexpression of "expr" of type isl_ast_expr_id,
860  * if it appears in "id2expr", then replace it by the corresponding
861  * expression.
862  */
isl_ast_expr_substitute_ids(__isl_take isl_ast_expr * expr,__isl_take isl_id_to_ast_expr * id2expr)863 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
864 	__isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
865 {
866 	isl_maybe_isl_ast_expr m;
867 	isl_ast_expr_list *args;
868 
869 	if (!expr || !id2expr)
870 		goto error;
871 
872 	switch (expr->type) {
873 	case isl_ast_expr_int:
874 		break;
875 	case isl_ast_expr_id:
876 		m = isl_id_to_ast_expr_try_get(id2expr, expr->u.id);
877 		if (m.valid < 0)
878 			goto error;
879 		if (!m.valid)
880 			break;
881 		isl_ast_expr_free(expr);
882 		expr = m.value;
883 		break;
884 	case isl_ast_expr_op:
885 		args = isl_ast_expr_op_take_args(expr);
886 		args = isl_ast_expr_list_map(args, &substitute_ids, id2expr);
887 		expr = isl_ast_expr_op_restore_args(expr, args);
888 		break;
889 	case isl_ast_expr_error:
890 		expr = isl_ast_expr_free(expr);
891 		break;
892 	}
893 
894 	isl_id_to_ast_expr_free(id2expr);
895 	return expr;
896 error:
897 	isl_ast_expr_free(expr);
898 	isl_id_to_ast_expr_free(id2expr);
899 	return NULL;
900 }
901 
isl_ast_node_get_ctx(__isl_keep isl_ast_node * node)902 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
903 {
904 	return node ? node->ctx : NULL;
905 }
906 
isl_ast_node_get_type(__isl_keep isl_ast_node * node)907 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
908 {
909 	return node ? node->type : isl_ast_node_error;
910 }
911 
isl_ast_node_alloc(isl_ctx * ctx,enum isl_ast_node_type type)912 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
913 	enum isl_ast_node_type type)
914 {
915 	isl_ast_node *node;
916 
917 	node = isl_calloc_type(ctx, isl_ast_node);
918 	if (!node)
919 		return NULL;
920 
921 	node->ctx = ctx;
922 	isl_ctx_ref(ctx);
923 	node->ref = 1;
924 	node->type = type;
925 
926 	return node;
927 }
928 
929 /* Create an if node with the given guard.
930  *
931  * The then body needs to be filled in later.
932  */
isl_ast_node_alloc_if(__isl_take isl_ast_expr * guard)933 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
934 {
935 	isl_ast_node *node;
936 
937 	if (!guard)
938 		return NULL;
939 
940 	node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
941 	if (!node)
942 		goto error;
943 	node->u.i.guard = guard;
944 
945 	return node;
946 error:
947 	isl_ast_expr_free(guard);
948 	return NULL;
949 }
950 
951 /* Create a for node with the given iterator.
952  *
953  * The remaining fields need to be filled in later.
954  */
isl_ast_node_alloc_for(__isl_take isl_id * id)955 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
956 {
957 	isl_ast_node *node;
958 	isl_ctx *ctx;
959 
960 	if (!id)
961 		return NULL;
962 
963 	ctx = isl_id_get_ctx(id);
964 	node = isl_ast_node_alloc(ctx, isl_ast_node_for);
965 	if (!node)
966 		goto error;
967 
968 	node->u.f.iterator = isl_ast_expr_from_id(id);
969 	if (!node->u.f.iterator)
970 		return isl_ast_node_free(node);
971 
972 	return node;
973 error:
974 	isl_id_free(id);
975 	return NULL;
976 }
977 
978 /* Create a mark node, marking "node" with "id".
979  */
isl_ast_node_alloc_mark(__isl_take isl_id * id,__isl_take isl_ast_node * node)980 __isl_give isl_ast_node *isl_ast_node_alloc_mark(__isl_take isl_id *id,
981 	__isl_take isl_ast_node *node)
982 {
983 	isl_ctx *ctx;
984 	isl_ast_node *mark;
985 
986 	if (!id || !node)
987 		goto error;
988 
989 	ctx = isl_id_get_ctx(id);
990 	mark = isl_ast_node_alloc(ctx, isl_ast_node_mark);
991 	if (!mark)
992 		goto error;
993 
994 	mark->u.m.mark = id;
995 	mark->u.m.node = node;
996 
997 	return mark;
998 error:
999 	isl_id_free(id);
1000 	isl_ast_node_free(node);
1001 	return NULL;
1002 }
1003 
1004 /* Create a user node evaluating "expr".
1005  */
isl_ast_node_user_from_expr(__isl_take isl_ast_expr * expr)1006 __isl_give isl_ast_node *isl_ast_node_user_from_expr(
1007 	__isl_take isl_ast_expr *expr)
1008 {
1009 	isl_ctx *ctx;
1010 	isl_ast_node *node;
1011 
1012 	if (!expr)
1013 		return NULL;
1014 
1015 	ctx = isl_ast_expr_get_ctx(expr);
1016 	node = isl_ast_node_alloc(ctx, isl_ast_node_user);
1017 	if (!node)
1018 		goto error;
1019 
1020 	node->u.e.expr = expr;
1021 
1022 	return node;
1023 error:
1024 	isl_ast_expr_free(expr);
1025 	return NULL;
1026 }
1027 
1028 /* This is an alternative name for the function above.
1029  */
isl_ast_node_alloc_user(__isl_take isl_ast_expr * expr)1030 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
1031 {
1032 	return isl_ast_node_user_from_expr(expr);
1033 }
1034 
1035 /* Create a block node with the given children.
1036  */
isl_ast_node_block_from_children(__isl_take isl_ast_node_list * list)1037 __isl_give isl_ast_node *isl_ast_node_block_from_children(
1038 	__isl_take isl_ast_node_list *list)
1039 {
1040 	isl_ast_node *node;
1041 	isl_ctx *ctx;
1042 
1043 	if (!list)
1044 		return NULL;
1045 
1046 	ctx = isl_ast_node_list_get_ctx(list);
1047 	node = isl_ast_node_alloc(ctx, isl_ast_node_block);
1048 	if (!node)
1049 		goto error;
1050 
1051 	node->u.b.children = list;
1052 
1053 	return node;
1054 error:
1055 	isl_ast_node_list_free(list);
1056 	return NULL;
1057 }
1058 
1059 /* This is an alternative name for the function above.
1060  */
isl_ast_node_alloc_block(__isl_take isl_ast_node_list * list)1061 __isl_give isl_ast_node *isl_ast_node_alloc_block(
1062 	__isl_take isl_ast_node_list *list)
1063 {
1064 	return isl_ast_node_block_from_children(list);
1065 }
1066 
1067 /* Represent the given list of nodes as a single node, either by
1068  * extract the node from a single element list or by creating
1069  * a block node with the list of nodes as children.
1070  */
isl_ast_node_from_ast_node_list(__isl_take isl_ast_node_list * list)1071 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
1072 	__isl_take isl_ast_node_list *list)
1073 {
1074 	isl_size n;
1075 	isl_ast_node *node;
1076 
1077 	n = isl_ast_node_list_n_ast_node(list);
1078 	if (n < 0)
1079 		goto error;
1080 	if (n != 1)
1081 		return isl_ast_node_alloc_block(list);
1082 
1083 	node = isl_ast_node_list_get_ast_node(list, 0);
1084 	isl_ast_node_list_free(list);
1085 
1086 	return node;
1087 error:
1088 	isl_ast_node_list_free(list);
1089 	return NULL;
1090 }
1091 
isl_ast_node_copy(__isl_keep isl_ast_node * node)1092 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
1093 {
1094 	if (!node)
1095 		return NULL;
1096 
1097 	node->ref++;
1098 	return node;
1099 }
1100 
1101 /* Return a fresh copy of "node".
1102  *
1103  * In the case of a degenerate for node, take into account
1104  * that "cond" and "inc" are NULL.
1105  */
isl_ast_node_dup(__isl_keep isl_ast_node * node)1106 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
1107 {
1108 	isl_ast_node *dup;
1109 
1110 	if (!node)
1111 		return NULL;
1112 
1113 	dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
1114 	if (!dup)
1115 		return NULL;
1116 
1117 	switch (node->type) {
1118 	case isl_ast_node_if:
1119 		dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
1120 		dup->u.i.then = isl_ast_node_copy(node->u.i.then);
1121 		dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
1122 		if (!dup->u.i.guard  || !dup->u.i.then ||
1123 		    (node->u.i.else_node && !dup->u.i.else_node))
1124 			return isl_ast_node_free(dup);
1125 		break;
1126 	case isl_ast_node_for:
1127 		dup->u.f.degenerate = node->u.f.degenerate;
1128 		dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
1129 		dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
1130 		dup->u.f.body = isl_ast_node_copy(node->u.f.body);
1131 		if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.body)
1132 			return isl_ast_node_free(dup);
1133 		if (node->u.f.degenerate)
1134 			break;
1135 		dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
1136 		dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
1137 		if (!dup->u.f.cond || !dup->u.f.inc)
1138 			return isl_ast_node_free(dup);
1139 		break;
1140 	case isl_ast_node_block:
1141 		dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
1142 		if (!dup->u.b.children)
1143 			return isl_ast_node_free(dup);
1144 		break;
1145 	case isl_ast_node_mark:
1146 		dup->u.m.mark = isl_id_copy(node->u.m.mark);
1147 		dup->u.m.node = isl_ast_node_copy(node->u.m.node);
1148 		if (!dup->u.m.mark || !dup->u.m.node)
1149 			return isl_ast_node_free(dup);
1150 		break;
1151 	case isl_ast_node_user:
1152 		dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
1153 		if (!dup->u.e.expr)
1154 			return isl_ast_node_free(dup);
1155 		break;
1156 	case isl_ast_node_error:
1157 		break;
1158 	}
1159 
1160 	if (!node->annotation)
1161 		return dup;
1162 	dup->annotation = isl_id_copy(node->annotation);
1163 	if (!dup->annotation)
1164 		return isl_ast_node_free(dup);
1165 
1166 	return dup;
1167 }
1168 
isl_ast_node_cow(__isl_take isl_ast_node * node)1169 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
1170 {
1171 	if (!node)
1172 		return NULL;
1173 
1174 	if (node->ref == 1)
1175 		return node;
1176 	node->ref--;
1177 	return isl_ast_node_dup(node);
1178 }
1179 
isl_ast_node_free(__isl_take isl_ast_node * node)1180 __isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node)
1181 {
1182 	if (!node)
1183 		return NULL;
1184 
1185 	if (--node->ref > 0)
1186 		return NULL;
1187 
1188 	switch (node->type) {
1189 	case isl_ast_node_if:
1190 		isl_ast_expr_free(node->u.i.guard);
1191 		isl_ast_node_free(node->u.i.then);
1192 		isl_ast_node_free(node->u.i.else_node);
1193 		break;
1194 	case isl_ast_node_for:
1195 		isl_ast_expr_free(node->u.f.iterator);
1196 		isl_ast_expr_free(node->u.f.init);
1197 		isl_ast_expr_free(node->u.f.cond);
1198 		isl_ast_expr_free(node->u.f.inc);
1199 		isl_ast_node_free(node->u.f.body);
1200 		break;
1201 	case isl_ast_node_block:
1202 		isl_ast_node_list_free(node->u.b.children);
1203 		break;
1204 	case isl_ast_node_mark:
1205 		isl_id_free(node->u.m.mark);
1206 		isl_ast_node_free(node->u.m.node);
1207 		break;
1208 	case isl_ast_node_user:
1209 		isl_ast_expr_free(node->u.e.expr);
1210 		break;
1211 	case isl_ast_node_error:
1212 		break;
1213 	}
1214 
1215 	isl_id_free(node->annotation);
1216 	isl_ctx_deref(node->ctx);
1217 	free(node);
1218 
1219 	return NULL;
1220 }
1221 
1222 /* Check that "node" is of type "type", printing "msg" if not.
1223  */
isl_ast_node_check_type(__isl_keep isl_ast_node * node,enum isl_ast_node_type type,const char * msg)1224 static isl_stat isl_ast_node_check_type(__isl_keep isl_ast_node *node,
1225 	enum isl_ast_node_type type, const char *msg)
1226 {
1227 	if (!node)
1228 		return isl_stat_error;
1229 	if (node->type != type)
1230 		isl_die(isl_ast_node_get_ctx(node), isl_error_invalid, msg,
1231 			return isl_stat_error);
1232 	return isl_stat_ok;
1233 }
1234 
1235 /* Check that "node" is of type isl_ast_node_block.
1236  */
isl_ast_node_check_block(__isl_keep isl_ast_node * node)1237 static isl_stat isl_ast_node_check_block(__isl_keep isl_ast_node *node)
1238 {
1239 	return isl_ast_node_check_type(node, isl_ast_node_block,
1240 					"not a block node");
1241 }
1242 
1243 /* Check that "node" is of type isl_ast_node_if.
1244  */
isl_ast_node_check_if(__isl_keep isl_ast_node * node)1245 static isl_stat isl_ast_node_check_if(__isl_keep isl_ast_node *node)
1246 {
1247 	return isl_ast_node_check_type(node, isl_ast_node_if, "not an if node");
1248 }
1249 
1250 /* Check that "node" is of type isl_ast_node_for.
1251  */
isl_ast_node_check_for(__isl_keep isl_ast_node * node)1252 static isl_stat isl_ast_node_check_for(__isl_keep isl_ast_node *node)
1253 {
1254 	return isl_ast_node_check_type(node, isl_ast_node_for,
1255 					"not a for node");
1256 }
1257 
1258 /* Check that "node" is of type isl_ast_node_mark.
1259  */
isl_ast_node_check_mark(__isl_keep isl_ast_node * node)1260 static isl_stat isl_ast_node_check_mark(__isl_keep isl_ast_node *node)
1261 {
1262 	return isl_ast_node_check_type(node, isl_ast_node_mark,
1263 					"not a mark node");
1264 }
1265 
1266 /* Check that "node" is of type isl_ast_node_user.
1267  */
isl_ast_node_check_user(__isl_keep isl_ast_node * node)1268 static isl_stat isl_ast_node_check_user(__isl_keep isl_ast_node *node)
1269 {
1270 	return isl_ast_node_check_type(node, isl_ast_node_user,
1271 					"not a user node");
1272 }
1273 
1274 #undef NODE_TYPE
1275 #define NODE_TYPE	for
1276 #undef FIELD_NAME
1277 #define FIELD_NAME	init
1278 #undef FIELD_TYPE
1279 #define FIELD_TYPE	isl_ast_expr
1280 #undef FIELD
1281 #define FIELD		u.f.init
1282 #include "isl_ast_node_set_field_templ.c"
1283 
1284 #undef NODE_TYPE
1285 #define NODE_TYPE	for
1286 #undef FIELD_NAME
1287 #define FIELD_NAME	cond
1288 #undef FIELD_TYPE
1289 #define FIELD_TYPE	isl_ast_expr
1290 #undef FIELD
1291 #define FIELD		u.f.cond
1292 #include "isl_ast_node_set_field_templ.c"
1293 
1294 #undef NODE_TYPE
1295 #define NODE_TYPE	for
1296 #undef FIELD_NAME
1297 #define FIELD_NAME	inc
1298 #undef FIELD_TYPE
1299 #define FIELD_TYPE	isl_ast_expr
1300 #undef FIELD
1301 #define FIELD		u.f.inc
1302 #include "isl_ast_node_set_field_templ.c"
1303 
1304 #undef NODE_TYPE
1305 #define NODE_TYPE	for
1306 #undef FIELD_NAME
1307 #define FIELD_NAME	body
1308 #undef FIELD_TYPE
1309 #define FIELD_TYPE	isl_ast_node
1310 #undef FIELD
1311 #define FIELD		u.f.body
1312 #include "isl_ast_node_set_field_templ.c"
1313 
1314 /* Return the body of the for-node "node",
1315  * This may be either a copy or the body itself
1316  * if there is only one reference to "node".
1317  * This allows the body to be modified inplace
1318  * if both "node" and its body have only a single reference.
1319  * The caller is not allowed to modify "node" between this call and
1320  * the subsequent call to isl_ast_node_for_restore_body.
1321  * The only exception is that isl_ast_node_free can be called instead.
1322  */
isl_ast_node_for_take_body(__isl_keep isl_ast_node * node)1323 static __isl_give isl_ast_node *isl_ast_node_for_take_body(
1324 	__isl_keep isl_ast_node *node)
1325 {
1326 	isl_ast_node *body;
1327 
1328 	if (isl_ast_node_check_for(node) < 0)
1329 		return NULL;
1330 	if (node->ref != 1)
1331 		return isl_ast_node_for_get_body(node);
1332 	body = node->u.f.body;
1333 	node->u.f.body = NULL;
1334 	return body;
1335 }
1336 
1337 /* Set the body of the for-node "node" to "body",
1338  * where the body of "node" may be missing
1339  * due to a preceding call to isl_ast_node_for_take_body.
1340  * However, in this case, "node" only has a single reference.
1341  */
isl_ast_node_for_restore_body(__isl_take isl_ast_node * node,__isl_take isl_ast_node * body)1342 static __isl_give isl_ast_node *isl_ast_node_for_restore_body(
1343 	__isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
1344 {
1345 	return isl_ast_node_for_set_body(node, body);
1346 }
1347 
isl_ast_node_for_get_body(__isl_keep isl_ast_node * node)1348 __isl_give isl_ast_node *isl_ast_node_for_get_body(
1349 	__isl_keep isl_ast_node *node)
1350 {
1351 	if (isl_ast_node_check_for(node) < 0)
1352 		return NULL;
1353 	return isl_ast_node_copy(node->u.f.body);
1354 }
1355 
1356 /* Mark the given for node as being degenerate.
1357  */
isl_ast_node_for_mark_degenerate(__isl_take isl_ast_node * node)1358 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
1359 	__isl_take isl_ast_node *node)
1360 {
1361 	node = isl_ast_node_cow(node);
1362 	if (!node)
1363 		return NULL;
1364 	node->u.f.degenerate = 1;
1365 	return node;
1366 }
1367 
isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node * node)1368 isl_bool isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
1369 {
1370 	if (isl_ast_node_check_for(node) < 0)
1371 		return isl_bool_error;
1372 	return isl_bool_ok(node->u.f.degenerate);
1373 }
1374 
isl_ast_node_for_get_iterator(__isl_keep isl_ast_node * node)1375 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
1376 	__isl_keep isl_ast_node *node)
1377 {
1378 	if (isl_ast_node_check_for(node) < 0)
1379 		return NULL;
1380 	return isl_ast_expr_copy(node->u.f.iterator);
1381 }
1382 
isl_ast_node_for_get_init(__isl_keep isl_ast_node * node)1383 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
1384 	__isl_keep isl_ast_node *node)
1385 {
1386 	if (isl_ast_node_check_for(node) < 0)
1387 		return NULL;
1388 	return isl_ast_expr_copy(node->u.f.init);
1389 }
1390 
1391 /* Return the condition expression of the given for node.
1392  *
1393  * If the for node is degenerate, then the condition is not explicitly
1394  * stored in the node.  Instead, it is constructed as
1395  *
1396  *	iterator <= init
1397  */
isl_ast_node_for_get_cond(__isl_keep isl_ast_node * node)1398 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
1399 	__isl_keep isl_ast_node *node)
1400 {
1401 	if (isl_ast_node_check_for(node) < 0)
1402 		return NULL;
1403 	if (!node->u.f.degenerate)
1404 		return isl_ast_expr_copy(node->u.f.cond);
1405 
1406 	return isl_ast_expr_alloc_binary(isl_ast_expr_op_le,
1407 				isl_ast_expr_copy(node->u.f.iterator),
1408 				isl_ast_expr_copy(node->u.f.init));
1409 }
1410 
1411 /* Return the increment of the given for node.
1412  *
1413  * If the for node is degenerate, then the increment is not explicitly
1414  * stored in the node.  We simply return "1".
1415  */
isl_ast_node_for_get_inc(__isl_keep isl_ast_node * node)1416 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1417 	__isl_keep isl_ast_node *node)
1418 {
1419 	if (isl_ast_node_check_for(node) < 0)
1420 		return NULL;
1421 	if (!node->u.f.degenerate)
1422 		return isl_ast_expr_copy(node->u.f.inc);
1423 	return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1424 }
1425 
1426 #undef NODE_TYPE
1427 #define NODE_TYPE	if
1428 #undef FIELD_NAME
1429 #define FIELD_NAME	then
1430 #undef FIELD_TYPE
1431 #define FIELD_TYPE	isl_ast_node
1432 #undef FIELD
1433 #define FIELD		u.i.then
1434 #include "isl_ast_node_set_field_templ.c"
1435 
1436 /* Return the then-branch of the if-node "node",
1437  * This may be either a copy or the branch itself
1438  * if there is only one reference to "node".
1439  * This allows the branch to be modified inplace
1440  * if both "node" and its then-branch have only a single reference.
1441  * The caller is not allowed to modify "node" between this call and
1442  * the subsequent call to isl_ast_node_if_restore_then_node.
1443  * The only exception is that isl_ast_node_free can be called instead.
1444  */
isl_ast_node_if_take_then_node(__isl_keep isl_ast_node * node)1445 static __isl_give isl_ast_node *isl_ast_node_if_take_then_node(
1446 	__isl_keep isl_ast_node *node)
1447 {
1448 	isl_ast_node *then_node;
1449 
1450 	if (isl_ast_node_check_if(node) < 0)
1451 		return NULL;
1452 	if (node->ref != 1)
1453 		return isl_ast_node_if_get_then_node(node);
1454 	then_node = node->u.i.then;
1455 	node->u.i.then = NULL;
1456 	return then_node;
1457 }
1458 
1459 /* Set the then-branch of the if-node "node" to "child",
1460  * where the then-branch of "node" may be missing
1461  * due to a preceding call to isl_ast_node_if_take_then_node.
1462  * However, in this case, "node" only has a single reference.
1463  */
isl_ast_node_if_restore_then_node(__isl_take isl_ast_node * node,__isl_take isl_ast_node * child)1464 static __isl_give isl_ast_node *isl_ast_node_if_restore_then_node(
1465 	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1466 {
1467 	return isl_ast_node_if_set_then(node, child);
1468 }
1469 
1470 /* Return the then-node of the given if-node.
1471  */
isl_ast_node_if_get_then_node(__isl_keep isl_ast_node * node)1472 __isl_give isl_ast_node *isl_ast_node_if_get_then_node(
1473 	__isl_keep isl_ast_node *node)
1474 {
1475 	if (isl_ast_node_check_if(node) < 0)
1476 		return NULL;
1477 	return isl_ast_node_copy(node->u.i.then);
1478 }
1479 
1480 /* This is an alternative name for the function above.
1481  */
isl_ast_node_if_get_then(__isl_keep isl_ast_node * node)1482 __isl_give isl_ast_node *isl_ast_node_if_get_then(
1483 	__isl_keep isl_ast_node *node)
1484 {
1485 	return isl_ast_node_if_get_then_node(node);
1486 }
1487 
1488 /* Does the given if-node have an else-node?
1489  */
isl_ast_node_if_has_else_node(__isl_keep isl_ast_node * node)1490 isl_bool isl_ast_node_if_has_else_node(__isl_keep isl_ast_node *node)
1491 {
1492 	if (isl_ast_node_check_if(node) < 0)
1493 		return isl_bool_error;
1494 	return isl_bool_ok(node->u.i.else_node != NULL);
1495 }
1496 
1497 /* This is an alternative name for the function above.
1498  */
isl_ast_node_if_has_else(__isl_keep isl_ast_node * node)1499 isl_bool isl_ast_node_if_has_else(__isl_keep isl_ast_node *node)
1500 {
1501 	return isl_ast_node_if_has_else_node(node);
1502 }
1503 
1504 /* Return the else-node of the given if-node,
1505  * assuming there is one.
1506  */
isl_ast_node_if_get_else_node(__isl_keep isl_ast_node * node)1507 __isl_give isl_ast_node *isl_ast_node_if_get_else_node(
1508 	__isl_keep isl_ast_node *node)
1509 {
1510 	if (isl_ast_node_check_if(node) < 0)
1511 		return NULL;
1512 	return isl_ast_node_copy(node->u.i.else_node);
1513 }
1514 
1515 /* This is an alternative name for the function above.
1516  */
isl_ast_node_if_get_else(__isl_keep isl_ast_node * node)1517 __isl_give isl_ast_node *isl_ast_node_if_get_else(
1518 	__isl_keep isl_ast_node *node)
1519 {
1520 	return isl_ast_node_if_get_else_node(node);
1521 }
1522 
1523 #undef NODE_TYPE
1524 #define NODE_TYPE	if
1525 #undef FIELD_NAME
1526 #define FIELD_NAME	else_node
1527 #undef FIELD_TYPE
1528 #define FIELD_TYPE	isl_ast_node
1529 #undef FIELD
1530 #define FIELD		u.i.else_node
1531 static
1532 #include "isl_ast_node_set_field_templ.c"
1533 
1534 /* Return the else-branch of the if-node "node",
1535  * This may be either a copy or the branch itself
1536  * if there is only one reference to "node".
1537  * This allows the branch to be modified inplace
1538  * if both "node" and its else-branch have only a single reference.
1539  * The caller is not allowed to modify "node" between this call and
1540  * the subsequent call to isl_ast_node_if_restore_else_node.
1541  * The only exception is that isl_ast_node_free can be called instead.
1542  */
isl_ast_node_if_take_else_node(__isl_keep isl_ast_node * node)1543 static __isl_give isl_ast_node *isl_ast_node_if_take_else_node(
1544 	__isl_keep isl_ast_node *node)
1545 {
1546 	isl_ast_node *else_node;
1547 
1548 	if (isl_ast_node_check_if(node) < 0)
1549 		return NULL;
1550 	if (node->ref != 1)
1551 		return isl_ast_node_if_get_else_node(node);
1552 	else_node = node->u.i.else_node;
1553 	node->u.i.else_node = NULL;
1554 	return else_node;
1555 }
1556 
1557 /* Set the else-branch of the if-node "node" to "child",
1558  * where the else-branch of "node" may be missing
1559  * due to a preceding call to isl_ast_node_if_take_else_node.
1560  * However, in this case, "node" only has a single reference.
1561  */
isl_ast_node_if_restore_else_node(__isl_take isl_ast_node * node,__isl_take isl_ast_node * child)1562 static __isl_give isl_ast_node *isl_ast_node_if_restore_else_node(
1563 	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1564 {
1565 	return isl_ast_node_if_set_else_node(node, child);
1566 }
1567 
isl_ast_node_if_get_cond(__isl_keep isl_ast_node * node)1568 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
1569 	__isl_keep isl_ast_node *node)
1570 {
1571 	if (isl_ast_node_check_if(node) < 0)
1572 		return NULL;
1573 	return isl_ast_expr_copy(node->u.i.guard);
1574 }
1575 
isl_ast_node_block_get_children(__isl_keep isl_ast_node * node)1576 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1577 	__isl_keep isl_ast_node *node)
1578 {
1579 	if (isl_ast_node_check_block(node) < 0)
1580 		return NULL;
1581 	return isl_ast_node_list_copy(node->u.b.children);
1582 }
1583 
1584 #undef NODE_TYPE
1585 #define NODE_TYPE	block
1586 #undef FIELD_NAME
1587 #define FIELD_NAME	children
1588 #undef FIELD_TYPE
1589 #define FIELD_TYPE	isl_ast_node_list
1590 #undef FIELD
1591 #define FIELD		u.b.children
1592 static
1593 #include "isl_ast_node_set_field_templ.c"
1594 
1595 /* Return the children of the block-node "node",
1596  * This may be either a copy or the children themselves
1597  * if there is only one reference to "node".
1598  * This allows the children to be modified inplace
1599  * if both "node" and its children have only a single reference.
1600  * The caller is not allowed to modify "node" between this call and
1601  * the subsequent call to isl_ast_node_block_restore_children.
1602  * The only exception is that isl_ast_node_free can be called instead.
1603  */
isl_ast_node_block_take_children(__isl_keep isl_ast_node * node)1604 static __isl_give isl_ast_node_list *isl_ast_node_block_take_children(
1605 	__isl_keep isl_ast_node *node)
1606 {
1607 	isl_ast_node_list *children;
1608 
1609 	if (isl_ast_node_check_block(node) < 0)
1610 		return NULL;
1611 	if (node->ref != 1)
1612 		return isl_ast_node_block_get_children(node);
1613 	children = node->u.b.children;
1614 	node->u.b.children = NULL;
1615 	return children;
1616 }
1617 
1618 /* Set the children of the block-node "node" to "children",
1619  * where the children of "node" may be missing
1620  * due to a preceding call to isl_ast_node_block_take_children.
1621  * However, in this case, "node" only has a single reference.
1622  */
isl_ast_node_block_restore_children(__isl_take isl_ast_node * node,__isl_take isl_ast_node_list * children)1623 static __isl_give isl_ast_node *isl_ast_node_block_restore_children(
1624 	__isl_take isl_ast_node *node, __isl_take isl_ast_node_list *children)
1625 {
1626 	return isl_ast_node_block_set_children(node, children);
1627 }
1628 
isl_ast_node_user_get_expr(__isl_keep isl_ast_node * node)1629 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1630 	__isl_keep isl_ast_node *node)
1631 {
1632 	if (isl_ast_node_check_user(node) < 0)
1633 		return NULL;
1634 
1635 	return isl_ast_expr_copy(node->u.e.expr);
1636 }
1637 
1638 /* Return the mark identifier of the mark node "node".
1639  */
isl_ast_node_mark_get_id(__isl_keep isl_ast_node * node)1640 __isl_give isl_id *isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node)
1641 {
1642 	if (isl_ast_node_check_mark(node) < 0)
1643 		return NULL;
1644 
1645 	return isl_id_copy(node->u.m.mark);
1646 }
1647 
1648 /* Return the node marked by mark node "node".
1649  */
isl_ast_node_mark_get_node(__isl_keep isl_ast_node * node)1650 __isl_give isl_ast_node *isl_ast_node_mark_get_node(
1651 	__isl_keep isl_ast_node *node)
1652 {
1653 	if (isl_ast_node_check_mark(node) < 0)
1654 		return NULL;
1655 
1656 	return isl_ast_node_copy(node->u.m.node);
1657 }
1658 
1659 #undef NODE_TYPE
1660 #define NODE_TYPE	mark
1661 #undef FIELD_NAME
1662 #define FIELD_NAME	node
1663 #undef FIELD_TYPE
1664 #define FIELD_TYPE	isl_ast_node
1665 #undef FIELD
1666 #define FIELD		u.m.node
1667 static
1668 #include "isl_ast_node_set_field_templ.c"
1669 
1670 /* Return the child of the mark-node "node",
1671  * This may be either a copy or the child itself
1672  * if there is only one reference to "node".
1673  * This allows the child to be modified inplace
1674  * if both "node" and its child have only a single reference.
1675  * The caller is not allowed to modify "node" between this call and
1676  * the subsequent call to isl_ast_node_mark_restore_node.
1677  * The only exception is that isl_ast_node_free can be called instead.
1678  */
isl_ast_node_mark_take_node(__isl_keep isl_ast_node * node)1679 static __isl_give isl_ast_node *isl_ast_node_mark_take_node(
1680 	__isl_keep isl_ast_node *node)
1681 {
1682 	isl_ast_node *child;
1683 
1684 	if (isl_ast_node_check_mark(node) < 0)
1685 		return NULL;
1686 	if (node->ref != 1)
1687 		return isl_ast_node_mark_get_node(node);
1688 	child = node->u.m.node;
1689 	node->u.m.node = NULL;
1690 	return child;
1691 }
1692 
1693 /* Set the child of the mark-node "node" to "child",
1694  * where the child of "node" may be missing
1695  * due to a preceding call to isl_ast_node_mark_take_node.
1696  * However, in this case, "node" only has a single reference.
1697  */
isl_ast_node_mark_restore_node(__isl_take isl_ast_node * node,__isl_take isl_ast_node * child)1698 static __isl_give isl_ast_node *isl_ast_node_mark_restore_node(
1699 	__isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1700 {
1701 	return isl_ast_node_mark_set_node(node, child);
1702 }
1703 
isl_ast_node_get_annotation(__isl_keep isl_ast_node * node)1704 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1705 {
1706 	return node ? isl_id_copy(node->annotation) : NULL;
1707 }
1708 
1709 /* Check that "node" is of any type.
1710  * That is, simply check that it is a valid node.
1711  */
isl_ast_node_check_any(__isl_keep isl_ast_node * node)1712 static isl_stat isl_ast_node_check_any(__isl_keep isl_ast_node *node)
1713 {
1714 	return isl_stat_non_null(node);
1715 }
1716 
1717 #undef NODE_TYPE
1718 #define NODE_TYPE	any
1719 #undef FIELD_NAME
1720 #define FIELD_NAME	annotation
1721 #undef FIELD_TYPE
1722 #define FIELD_TYPE	isl_id
1723 #undef FIELD
1724 #define FIELD		annotation
1725 static
1726 #include "isl_ast_node_set_field_templ.c"
1727 
1728 /* Replace node->annotation by "annotation".
1729  */
isl_ast_node_set_annotation(__isl_take isl_ast_node * node,__isl_take isl_id * annotation)1730 __isl_give isl_ast_node *isl_ast_node_set_annotation(
1731 	__isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1732 {
1733 	return isl_ast_node_any_set_annotation(node, annotation);
1734 }
1735 
1736 static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node,
1737 	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1738 		int *more, void *user),
1739 	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1740 		void *user),
1741 	void *user);
1742 
1743 /* Traverse the elements of "list" and all their descendants
1744  * in depth first preorder.  Call "enter" whenever a node is entered and "leave"
1745  * whenever a node is left.
1746  *
1747  * Return the updated node.
1748  */
traverse_list(__isl_take isl_ast_node_list * list,__isl_give isl_ast_node * (* enter)(__isl_take isl_ast_node * node,int * more,void * user),__isl_give isl_ast_node * (* leave)(__isl_take isl_ast_node * node,void * user),void * user)1749 static __isl_give isl_ast_node_list *traverse_list(
1750 	__isl_take isl_ast_node_list *list,
1751 	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1752 		int *more, void *user),
1753 	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1754 		void *user),
1755 	void *user)
1756 {
1757 	int i;
1758 	isl_size n;
1759 
1760 	n = isl_ast_node_list_size(list);
1761 	if (n < 0)
1762 		return isl_ast_node_list_free(list);
1763 
1764 	for (i = 0; i < n; ++i) {
1765 		isl_ast_node *node;
1766 
1767 		node = isl_ast_node_list_get_at(list, i);
1768 		node = traverse(node, enter, leave, user);
1769 		list = isl_ast_node_list_set_at(list, i, node);
1770 	}
1771 
1772 	return list;
1773 }
1774 
1775 /* Traverse the descendants of "node" (including the node itself)
1776  * in depth first preorder.  Call "enter" whenever a node is entered and "leave"
1777  * whenever a node is left.
1778  *
1779  * If "enter" sets the "more" argument to zero, then the subtree rooted
1780  * at the given node is skipped.
1781  *
1782  * Return the updated node.
1783  */
traverse(__isl_take isl_ast_node * node,__isl_give isl_ast_node * (* enter)(__isl_take isl_ast_node * node,int * more,void * user),__isl_give isl_ast_node * (* leave)(__isl_take isl_ast_node * node,void * user),void * user)1784 static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node,
1785 	__isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node,
1786 		int *more, void *user),
1787 	__isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node,
1788 		void *user),
1789 	void *user)
1790 {
1791 	int more;
1792 	isl_bool has_else;
1793 	isl_ast_node *child;
1794 	isl_ast_node_list *children;
1795 
1796 	node = enter(node, &more, user);
1797 	if (!node)
1798 		return NULL;
1799 	if (!more)
1800 		return node;
1801 
1802 	switch (node->type) {
1803 	case isl_ast_node_for:
1804 		child = isl_ast_node_for_take_body(node);
1805 		child = traverse(child, enter, leave, user);
1806 		node = isl_ast_node_for_restore_body(node, child);
1807 		return leave(node, user);
1808 	case isl_ast_node_if:
1809 		child = isl_ast_node_if_take_then_node(node);
1810 		child = traverse(child, enter, leave, user);
1811 		node = isl_ast_node_if_restore_then_node(node, child);
1812 		has_else = isl_ast_node_if_has_else_node(node);
1813 		if (has_else < 0)
1814 			return isl_ast_node_free(node);
1815 		if (!has_else)
1816 			return leave(node, user);
1817 		child = isl_ast_node_if_take_else_node(node);
1818 		child = traverse(child, enter, leave, user);
1819 		node = isl_ast_node_if_restore_else_node(node, child);
1820 		return leave(node, user);
1821 	case isl_ast_node_block:
1822 		children = isl_ast_node_block_take_children(node);
1823 		children = traverse_list(children, enter, leave, user);
1824 		node = isl_ast_node_block_restore_children(node, children);
1825 		return leave(node, user);
1826 	case isl_ast_node_mark:
1827 		child = isl_ast_node_mark_take_node(node);
1828 		child = traverse(child, enter, leave, user);
1829 		node = isl_ast_node_mark_restore_node(node, child);
1830 		return leave(node, user);
1831 	case isl_ast_node_user:
1832 		return leave(node, user);
1833 	case isl_ast_node_error:
1834 		return isl_ast_node_free(node);
1835 	}
1836 
1837 	return node;
1838 }
1839 
1840 /* Internal data structure storing the arguments of
1841  * isl_ast_node_foreach_descendant_top_down.
1842  */
1843 struct isl_ast_node_preorder_data {
1844 	isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user);
1845 	void *user;
1846 };
1847 
1848 /* Enter "node" and set *more to continue traversing its descendants.
1849  *
1850  * In the case of a depth first preorder traversal, call data->fn and
1851  * let it decide whether to continue.
1852  */
preorder_enter(__isl_take isl_ast_node * node,int * more,void * user)1853 static __isl_give isl_ast_node *preorder_enter(__isl_take isl_ast_node *node,
1854 	int *more, void *user)
1855 {
1856 	struct isl_ast_node_preorder_data *data = user;
1857 	isl_bool m;
1858 
1859 	if (!node)
1860 		return NULL;
1861 	m = data->fn(node, data->user);
1862 	if (m < 0)
1863 		return isl_ast_node_free(node);
1864 	*more = m;
1865 	return node;
1866 }
1867 
1868 /* Leave "node".
1869  *
1870  * In the case of a depth first preorder traversal, nothing needs to be done.
1871  */
preorder_leave(__isl_take isl_ast_node * node,void * user)1872 static __isl_give isl_ast_node *preorder_leave(__isl_take isl_ast_node *node,
1873 	void *user)
1874 {
1875 	return node;
1876 }
1877 
1878 /* Traverse the descendants of "node" (including the node itself)
1879  * in depth first preorder.
1880  *
1881  * If "fn" returns isl_bool_error on any of the nodes, then the traversal
1882  * is aborted.
1883  * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1884  * at that node is skipped.
1885  *
1886  * Return isl_stat_ok on success and isl_stat_error on failure.
1887  */
isl_ast_node_foreach_descendant_top_down(__isl_keep isl_ast_node * node,isl_bool (* fn)(__isl_keep isl_ast_node * node,void * user),void * user)1888 isl_stat isl_ast_node_foreach_descendant_top_down(
1889 	__isl_keep isl_ast_node *node,
1890 	isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user)
1891 {
1892 	struct isl_ast_node_preorder_data data = { fn, user };
1893 
1894 	node = isl_ast_node_copy(node);
1895 	node = traverse(node, &preorder_enter, &preorder_leave, &data);
1896 	isl_ast_node_free(node);
1897 
1898 	return isl_stat_non_null(node);
1899 }
1900 
1901 /* Internal data structure storing the arguments of
1902  * isl_ast_node_map_descendant_bottom_up.
1903  */
1904 struct isl_ast_node_postorder_data {
1905 	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
1906 		void *user);
1907 	void *user;
1908 };
1909 
1910 /* Enter "node" and set *more to continue traversing its descendants.
1911  *
1912  * In the case of a depth-first post-order traversal,
1913  * nothing needs to be done and traversal always continues.
1914  */
postorder_enter(__isl_take isl_ast_node * node,int * more,void * user)1915 static __isl_give isl_ast_node *postorder_enter(__isl_take isl_ast_node *node,
1916 	int *more, void *user)
1917 {
1918 	*more = 1;
1919 	return node;
1920 }
1921 
1922 /* Leave "node".
1923  *
1924  * In the case of a depth-first post-order traversal, call data->fn.
1925  */
postorder_leave(__isl_take isl_ast_node * node,void * user)1926 static __isl_give isl_ast_node *postorder_leave(__isl_take isl_ast_node *node,
1927 	void *user)
1928 {
1929 	struct isl_ast_node_postorder_data *data = user;
1930 
1931 	if (!node)
1932 		return NULL;
1933 
1934 	node = data->fn(node, data->user);
1935 	return node;
1936 }
1937 
1938 /* Traverse the descendants of "node" (including the node itself)
1939  * in depth-first post-order, where the user callback is allowed to modify the
1940  * visited node.
1941  *
1942  * Return the updated node.
1943  */
isl_ast_node_map_descendant_bottom_up(__isl_take isl_ast_node * node,__isl_give isl_ast_node * (* fn)(__isl_take isl_ast_node * node,void * user),void * user)1944 __isl_give isl_ast_node *isl_ast_node_map_descendant_bottom_up(
1945 	__isl_take isl_ast_node *node,
1946 	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
1947 		void *user), void *user)
1948 {
1949 	struct isl_ast_node_postorder_data data = { fn, user };
1950 
1951 	return traverse(node, &postorder_enter, &postorder_leave, &data);
1952 }
1953 
1954 /* Textual C representation of the various operators.
1955  */
1956 static char *op_str_c[] = {
1957 	[isl_ast_expr_op_and] = "&&",
1958 	[isl_ast_expr_op_and_then] = "&&",
1959 	[isl_ast_expr_op_or] = "||",
1960 	[isl_ast_expr_op_or_else] = "||",
1961 	[isl_ast_expr_op_max] = "max",
1962 	[isl_ast_expr_op_min] = "min",
1963 	[isl_ast_expr_op_minus] = "-",
1964 	[isl_ast_expr_op_add] = "+",
1965 	[isl_ast_expr_op_sub] = "-",
1966 	[isl_ast_expr_op_mul] = "*",
1967 	[isl_ast_expr_op_fdiv_q] = "floord",
1968 	[isl_ast_expr_op_pdiv_q] = "/",
1969 	[isl_ast_expr_op_pdiv_r] = "%",
1970 	[isl_ast_expr_op_zdiv_r] = "%",
1971 	[isl_ast_expr_op_div] = "/",
1972 	[isl_ast_expr_op_eq] = "==",
1973 	[isl_ast_expr_op_le] = "<=",
1974 	[isl_ast_expr_op_ge] = ">=",
1975 	[isl_ast_expr_op_lt] = "<",
1976 	[isl_ast_expr_op_gt] = ">",
1977 	[isl_ast_expr_op_member] = ".",
1978 	[isl_ast_expr_op_address_of] = "&"
1979 };
1980 
1981 /* Precedence in C of the various operators.
1982  * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1983  * Lowest value means highest precedence.
1984  */
1985 static int op_prec[] = {
1986 	[isl_ast_expr_op_and] = 13,
1987 	[isl_ast_expr_op_and_then] = 13,
1988 	[isl_ast_expr_op_or] = 14,
1989 	[isl_ast_expr_op_or_else] = 14,
1990 	[isl_ast_expr_op_max] = 2,
1991 	[isl_ast_expr_op_min] = 2,
1992 	[isl_ast_expr_op_minus] = 3,
1993 	[isl_ast_expr_op_add] = 6,
1994 	[isl_ast_expr_op_sub] = 6,
1995 	[isl_ast_expr_op_mul] = 5,
1996 	[isl_ast_expr_op_div] = 5,
1997 	[isl_ast_expr_op_fdiv_q] = 2,
1998 	[isl_ast_expr_op_pdiv_q] = 5,
1999 	[isl_ast_expr_op_pdiv_r] = 5,
2000 	[isl_ast_expr_op_zdiv_r] = 5,
2001 	[isl_ast_expr_op_cond] = 15,
2002 	[isl_ast_expr_op_select] = 15,
2003 	[isl_ast_expr_op_eq] = 9,
2004 	[isl_ast_expr_op_le] = 8,
2005 	[isl_ast_expr_op_ge] = 8,
2006 	[isl_ast_expr_op_lt] = 8,
2007 	[isl_ast_expr_op_gt] = 8,
2008 	[isl_ast_expr_op_call] = 2,
2009 	[isl_ast_expr_op_access] = 2,
2010 	[isl_ast_expr_op_member] = 2,
2011 	[isl_ast_expr_op_address_of] = 3
2012 };
2013 
2014 /* Is the operator left-to-right associative?
2015  */
2016 static int op_left[] = {
2017 	[isl_ast_expr_op_and] = 1,
2018 	[isl_ast_expr_op_and_then] = 1,
2019 	[isl_ast_expr_op_or] = 1,
2020 	[isl_ast_expr_op_or_else] = 1,
2021 	[isl_ast_expr_op_max] = 1,
2022 	[isl_ast_expr_op_min] = 1,
2023 	[isl_ast_expr_op_minus] = 0,
2024 	[isl_ast_expr_op_add] = 1,
2025 	[isl_ast_expr_op_sub] = 1,
2026 	[isl_ast_expr_op_mul] = 1,
2027 	[isl_ast_expr_op_div] = 1,
2028 	[isl_ast_expr_op_fdiv_q] = 1,
2029 	[isl_ast_expr_op_pdiv_q] = 1,
2030 	[isl_ast_expr_op_pdiv_r] = 1,
2031 	[isl_ast_expr_op_zdiv_r] = 1,
2032 	[isl_ast_expr_op_cond] = 0,
2033 	[isl_ast_expr_op_select] = 0,
2034 	[isl_ast_expr_op_eq] = 1,
2035 	[isl_ast_expr_op_le] = 1,
2036 	[isl_ast_expr_op_ge] = 1,
2037 	[isl_ast_expr_op_lt] = 1,
2038 	[isl_ast_expr_op_gt] = 1,
2039 	[isl_ast_expr_op_call] = 1,
2040 	[isl_ast_expr_op_access] = 1,
2041 	[isl_ast_expr_op_member] = 1,
2042 	[isl_ast_expr_op_address_of] = 0
2043 };
2044 
is_and(enum isl_ast_expr_op_type op)2045 static int is_and(enum isl_ast_expr_op_type op)
2046 {
2047 	return op == isl_ast_expr_op_and || op == isl_ast_expr_op_and_then;
2048 }
2049 
is_or(enum isl_ast_expr_op_type op)2050 static int is_or(enum isl_ast_expr_op_type op)
2051 {
2052 	return op == isl_ast_expr_op_or || op == isl_ast_expr_op_or_else;
2053 }
2054 
is_add_sub(enum isl_ast_expr_op_type op)2055 static int is_add_sub(enum isl_ast_expr_op_type op)
2056 {
2057 	return op == isl_ast_expr_op_add || op == isl_ast_expr_op_sub;
2058 }
2059 
is_div_mod(enum isl_ast_expr_op_type op)2060 static int is_div_mod(enum isl_ast_expr_op_type op)
2061 {
2062 	return op == isl_ast_expr_op_div ||
2063 	       op == isl_ast_expr_op_pdiv_r ||
2064 	       op == isl_ast_expr_op_zdiv_r;
2065 }
2066 
2067 static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p,
2068 	__isl_keep isl_ast_expr *expr);
2069 
2070 /* Do we need/want parentheses around "expr" as a subexpression of
2071  * an "op" operation?  If "left" is set, then "expr" is the left-most
2072  * operand.
2073  *
2074  * We only need parentheses if "expr" represents an operation.
2075  *
2076  * If op has a higher precedence than expr->u.op.op, then we need
2077  * parentheses.
2078  * If op and expr->u.op.op have the same precedence, but the operations
2079  * are performed in an order that is different from the associativity,
2080  * then we need parentheses.
2081  *
2082  * An and inside an or technically does not require parentheses,
2083  * but some compilers complain about that, so we add them anyway.
2084  *
2085  * Computations such as "a / b * c" and "a % b + c" can be somewhat
2086  * difficult to read, so we add parentheses for those as well.
2087  */
sub_expr_need_parens(enum isl_ast_expr_op_type op,__isl_keep isl_ast_expr * expr,int left)2088 static int sub_expr_need_parens(enum isl_ast_expr_op_type op,
2089 	__isl_keep isl_ast_expr *expr, int left)
2090 {
2091 	if (expr->type != isl_ast_expr_op)
2092 		return 0;
2093 
2094 	if (op_prec[expr->u.op.op] > op_prec[op])
2095 		return 1;
2096 	if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
2097 		return 1;
2098 
2099 	if (is_or(op) && is_and(expr->u.op.op))
2100 		return 1;
2101 	if (op == isl_ast_expr_op_mul && expr->u.op.op != isl_ast_expr_op_mul &&
2102 	    op_prec[expr->u.op.op] == op_prec[op])
2103 		return 1;
2104 	if (is_add_sub(op) && is_div_mod(expr->u.op.op))
2105 		return 1;
2106 
2107 	return 0;
2108 }
2109 
2110 /* Print the subexpression at position "pos" of operation expression "expr"
2111  * in C format.
2112  * If "left" is set, then "expr" is the left-most operand.
2113  */
print_sub_expr_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr,int pos,int left)2114 static __isl_give isl_printer *print_sub_expr_c(__isl_take isl_printer *p,
2115 	__isl_keep isl_ast_expr *expr, int pos, int left)
2116 {
2117 	int need_parens;
2118 	isl_ast_expr *arg;
2119 
2120 	if (!expr)
2121 		return isl_printer_free(p);
2122 
2123 	arg = isl_ast_expr_list_get_at(expr->u.op.args, pos);
2124 	need_parens = sub_expr_need_parens(expr->u.op.op, arg, left);
2125 
2126 	if (need_parens)
2127 		p = isl_printer_print_str(p, "(");
2128 	p = print_ast_expr_c(p, arg);
2129 	if (need_parens)
2130 		p = isl_printer_print_str(p, ")");
2131 
2132 	isl_ast_expr_free(arg);
2133 
2134 	return p;
2135 }
2136 
2137 #define isl_ast_expr_op_last	isl_ast_expr_op_address_of
2138 
2139 /* Data structure that holds the user-specified textual
2140  * representations for the operators in C format.
2141  * The entries are either NULL or copies of strings.
2142  * A NULL entry means that the default name should be used.
2143  */
2144 struct isl_ast_expr_op_names {
2145 	char *op_str[isl_ast_expr_op_last + 1];
2146 };
2147 
2148 /* Create an empty struct isl_ast_expr_op_names.
2149  */
create_names(isl_ctx * ctx)2150 static void *create_names(isl_ctx *ctx)
2151 {
2152 	return isl_calloc_type(ctx, struct isl_ast_expr_op_names);
2153 }
2154 
2155 /* Free a struct isl_ast_expr_op_names along with all memory
2156  * owned by the struct.
2157  */
free_names(void * user)2158 static void free_names(void *user)
2159 {
2160 	int i;
2161 	struct isl_ast_expr_op_names *names = user;
2162 
2163 	if (!user)
2164 		return;
2165 
2166 	for (i = 0; i <= isl_ast_expr_op_last; ++i)
2167 		free(names->op_str[i]);
2168 	free(user);
2169 }
2170 
2171 /* Create an identifier that is used to store
2172  * an isl_ast_expr_op_names note.
2173  */
names_id(isl_ctx * ctx)2174 static __isl_give isl_id *names_id(isl_ctx *ctx)
2175 {
2176 	return isl_id_alloc(ctx, "isl_ast_expr_op_type_names", NULL);
2177 }
2178 
2179 /* Ensure that "p" has a note identified by "id".
2180  * If there is no such note yet, then it is created by "note_create" and
2181  * scheduled do be freed by "note_free".
2182  */
alloc_note(__isl_take isl_printer * p,__isl_keep isl_id * id,void * (* note_create)(isl_ctx *),void (* note_free)(void *))2183 static __isl_give isl_printer *alloc_note(__isl_take isl_printer *p,
2184 	__isl_keep isl_id *id, void *(*note_create)(isl_ctx *),
2185 	void (*note_free)(void *))
2186 {
2187 	isl_ctx *ctx;
2188 	isl_id *note_id;
2189 	isl_bool has_note;
2190 	void *note;
2191 
2192 	has_note = isl_printer_has_note(p, id);
2193 	if (has_note < 0)
2194 		return isl_printer_free(p);
2195 	if (has_note)
2196 		return p;
2197 
2198 	ctx = isl_printer_get_ctx(p);
2199 	note = note_create(ctx);
2200 	if (!note)
2201 		return isl_printer_free(p);
2202 	note_id = isl_id_alloc(ctx, NULL, note);
2203 	if (!note_id)
2204 		note_free(note);
2205 	else
2206 		note_id = isl_id_set_free_user(note_id, note_free);
2207 
2208 	p = isl_printer_set_note(p, isl_id_copy(id), note_id);
2209 
2210 	return p;
2211 }
2212 
2213 /* Ensure that "p" has an isl_ast_expr_op_names note identified by "id".
2214  */
alloc_names(__isl_take isl_printer * p,__isl_keep isl_id * id)2215 static __isl_give isl_printer *alloc_names(__isl_take isl_printer *p,
2216 	__isl_keep isl_id *id)
2217 {
2218 	return alloc_note(p, id, &create_names, &free_names);
2219 }
2220 
2221 /* Retrieve the note identified by "id" from "p".
2222  * The note is assumed to exist.
2223  */
get_note(__isl_keep isl_printer * p,__isl_keep isl_id * id)2224 static void *get_note(__isl_keep isl_printer *p, __isl_keep isl_id *id)
2225 {
2226 	void *note;
2227 
2228 	id = isl_printer_get_note(p, isl_id_copy(id));
2229 	note = isl_id_get_user(id);
2230 	isl_id_free(id);
2231 
2232 	return note;
2233 }
2234 
2235 /* Use "name" to print operations of type "type" to "p".
2236  *
2237  * Store the name in an isl_ast_expr_op_names note attached to "p", such that
2238  * it can be retrieved by get_op_str.
2239  */
isl_ast_expr_op_type_set_print_name(__isl_take isl_printer * p,enum isl_ast_expr_op_type type,__isl_keep const char * name)2240 __isl_give isl_printer *isl_ast_expr_op_type_set_print_name(
2241 	__isl_take isl_printer *p, enum isl_ast_expr_op_type type,
2242 	__isl_keep const char *name)
2243 {
2244 	isl_id *id;
2245 	struct isl_ast_expr_op_names *names;
2246 
2247 	if (!p)
2248 		return NULL;
2249 	if (type > isl_ast_expr_op_last)
2250 		isl_die(isl_printer_get_ctx(p), isl_error_invalid,
2251 			"invalid type", return isl_printer_free(p));
2252 
2253 	id = names_id(isl_printer_get_ctx(p));
2254 	p = alloc_names(p, id);
2255 	names = get_note(p, id);
2256 	isl_id_free(id);
2257 	if (!names)
2258 		return isl_printer_free(p);
2259 	free(names->op_str[type]);
2260 	names->op_str[type] = strdup(name);
2261 
2262 	return p;
2263 }
2264 
2265 /* This is an alternative name for the function above.
2266  */
isl_ast_op_type_set_print_name(__isl_take isl_printer * p,enum isl_ast_expr_op_type type,__isl_keep const char * name)2267 __isl_give isl_printer *isl_ast_op_type_set_print_name(
2268 	__isl_take isl_printer *p, enum isl_ast_expr_op_type type,
2269 	__isl_keep const char *name)
2270 {
2271 	return isl_ast_expr_op_type_set_print_name(p, type, name);
2272 }
2273 
2274 /* Return the textual representation of "type" in C format.
2275  *
2276  * If there is a user-specified name in an isl_ast_expr_op_names note
2277  * associated to "p", then return that.
2278  * Otherwise, return the default name in op_str_c.
2279  */
get_op_str_c(__isl_keep isl_printer * p,enum isl_ast_expr_op_type type)2280 static const char *get_op_str_c(__isl_keep isl_printer *p,
2281 	enum isl_ast_expr_op_type type)
2282 {
2283 	isl_id *id;
2284 	isl_bool has_names;
2285 	struct isl_ast_expr_op_names *names = NULL;
2286 
2287 	id = names_id(isl_printer_get_ctx(p));
2288 	has_names = isl_printer_has_note(p, id);
2289 	if (has_names >= 0 && has_names)
2290 		names = get_note(p, id);
2291 	isl_id_free(id);
2292 	if (names && names->op_str[type])
2293 		return names->op_str[type];
2294 	return op_str_c[type];
2295 }
2296 
2297 /* Print the expression at position "pos" in "list" in C format.
2298  */
print_at_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr_list * list,int pos)2299 static __isl_give isl_printer *print_at_c(__isl_take isl_printer *p,
2300 	__isl_keep isl_ast_expr_list *list, int pos)
2301 {
2302 	isl_ast_expr *expr;
2303 
2304 	expr = isl_ast_expr_list_get_at(list, pos);
2305 	p = print_ast_expr_c(p, expr);
2306 	isl_ast_expr_free(expr);
2307 
2308 	return p;
2309 }
2310 
2311 /* Print a min or max reduction "expr" in C format.
2312  */
print_min_max_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2313 static __isl_give isl_printer *print_min_max_c(__isl_take isl_printer *p,
2314 	__isl_keep isl_ast_expr *expr)
2315 {
2316 	int i = 0;
2317 	isl_size n;
2318 
2319 	n = isl_ast_expr_list_size(expr->u.op.args);
2320 	if (n < 0)
2321 		return isl_printer_free(p);
2322 
2323 	for (i = 1; i < n; ++i) {
2324 		p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op));
2325 		p = isl_printer_print_str(p, "(");
2326 	}
2327 	p = print_at_c(p, expr->u.op.args, 0);
2328 	for (i = 1; i < n; ++i) {
2329 		p = isl_printer_print_str(p, ", ");
2330 		p = print_at_c(p, expr->u.op.args, i);
2331 		p = isl_printer_print_str(p, ")");
2332 	}
2333 
2334 	return p;
2335 }
2336 
2337 /* Print a function call "expr" in C format.
2338  *
2339  * The first argument represents the function to be called.
2340  */
print_call_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2341 static __isl_give isl_printer *print_call_c(__isl_take isl_printer *p,
2342 	__isl_keep isl_ast_expr *expr)
2343 {
2344 	int i = 0;
2345 	isl_size n;
2346 
2347 	n = isl_ast_expr_list_size(expr->u.op.args);
2348 	if (n < 0)
2349 		return isl_printer_free(p);
2350 
2351 	p = print_at_c(p, expr->u.op.args, 0);
2352 	p = isl_printer_print_str(p, "(");
2353 	for (i = 1; i < n; ++i) {
2354 		if (i != 1)
2355 			p = isl_printer_print_str(p, ", ");
2356 		p = print_at_c(p, expr->u.op.args, i);
2357 	}
2358 	p = isl_printer_print_str(p, ")");
2359 
2360 	return p;
2361 }
2362 
2363 /* Print an array access "expr" in C format.
2364  *
2365  * The first argument represents the array being accessed.
2366  */
print_access_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2367 static __isl_give isl_printer *print_access_c(__isl_take isl_printer *p,
2368 	__isl_keep isl_ast_expr *expr)
2369 {
2370 	int i = 0;
2371 	isl_size n;
2372 
2373 	n = isl_ast_expr_list_size(expr->u.op.args);
2374 	if (n < 0)
2375 		return isl_printer_free(p);
2376 
2377 	p = print_at_c(p, expr->u.op.args, 0);
2378 	for (i = 1; i < n; ++i) {
2379 		p = isl_printer_print_str(p, "[");
2380 		p = print_at_c(p, expr->u.op.args, i);
2381 		p = isl_printer_print_str(p, "]");
2382 	}
2383 
2384 	return p;
2385 }
2386 
2387 /* Print "expr" to "p" in C format.
2388  */
print_ast_expr_c(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2389 static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p,
2390 	__isl_keep isl_ast_expr *expr)
2391 {
2392 	isl_size n;
2393 
2394 	if (!p)
2395 		return NULL;
2396 	if (!expr)
2397 		return isl_printer_free(p);
2398 
2399 	switch (expr->type) {
2400 	case isl_ast_expr_op:
2401 		if (expr->u.op.op == isl_ast_expr_op_call) {
2402 			p = print_call_c(p, expr);
2403 			break;
2404 		}
2405 		if (expr->u.op.op == isl_ast_expr_op_access) {
2406 			p = print_access_c(p, expr);
2407 			break;
2408 		}
2409 		n = isl_ast_expr_list_size(expr->u.op.args);
2410 		if (n < 0)
2411 			return isl_printer_free(p);
2412 		if (n == 1) {
2413 			p = isl_printer_print_str(p,
2414 						get_op_str_c(p, expr->u.op.op));
2415 			p = print_sub_expr_c(p, expr, 0, 0);
2416 			break;
2417 		}
2418 		if (expr->u.op.op == isl_ast_expr_op_fdiv_q) {
2419 			const char *name;
2420 
2421 			name = get_op_str_c(p, isl_ast_expr_op_fdiv_q);
2422 			p = isl_printer_print_str(p, name);
2423 			p = isl_printer_print_str(p, "(");
2424 			p = print_at_c(p, expr->u.op.args, 0);
2425 			p = isl_printer_print_str(p, ", ");
2426 			p = print_at_c(p, expr->u.op.args, 1);
2427 			p = isl_printer_print_str(p, ")");
2428 			break;
2429 		}
2430 		if (expr->u.op.op == isl_ast_expr_op_max ||
2431 		    expr->u.op.op == isl_ast_expr_op_min) {
2432 			p = print_min_max_c(p, expr);
2433 			break;
2434 		}
2435 		if (expr->u.op.op == isl_ast_expr_op_cond ||
2436 		    expr->u.op.op == isl_ast_expr_op_select) {
2437 			p = print_at_c(p, expr->u.op.args, 0);
2438 			p = isl_printer_print_str(p, " ? ");
2439 			p = print_at_c(p, expr->u.op.args, 1);
2440 			p = isl_printer_print_str(p, " : ");
2441 			p = print_at_c(p, expr->u.op.args, 2);
2442 			break;
2443 		}
2444 		if (n != 2)
2445 			isl_die(isl_printer_get_ctx(p), isl_error_internal,
2446 				"operation should have two arguments",
2447 				return isl_printer_free(p));
2448 		p = print_sub_expr_c(p, expr, 0, 1);
2449 		if (expr->u.op.op != isl_ast_expr_op_member)
2450 			p = isl_printer_print_str(p, " ");
2451 		p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op));
2452 		if (expr->u.op.op != isl_ast_expr_op_member)
2453 			p = isl_printer_print_str(p, " ");
2454 		p = print_sub_expr_c(p, expr, 1, 0);
2455 		break;
2456 	case isl_ast_expr_id:
2457 		p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
2458 		break;
2459 	case isl_ast_expr_int:
2460 		p = isl_printer_print_val(p, expr->u.v);
2461 		break;
2462 	case isl_ast_expr_error:
2463 		break;
2464 	}
2465 
2466 	return p;
2467 }
2468 
2469 /* Textual representation of the isl_ast_expr_op_type elements
2470  * for use in a YAML representation of an isl_ast_expr.
2471  */
2472 static char *op_str[] = {
2473 	[isl_ast_expr_op_and] = "and",
2474 	[isl_ast_expr_op_and_then] = "and_then",
2475 	[isl_ast_expr_op_or] = "or",
2476 	[isl_ast_expr_op_or_else] = "or_else",
2477 	[isl_ast_expr_op_max] = "max",
2478 	[isl_ast_expr_op_min] = "min",
2479 	[isl_ast_expr_op_minus] = "minus",
2480 	[isl_ast_expr_op_add] = "add",
2481 	[isl_ast_expr_op_sub] = "sub",
2482 	[isl_ast_expr_op_mul] = "mul",
2483 	[isl_ast_expr_op_div] = "div",
2484 	[isl_ast_expr_op_fdiv_q] = "fdiv_q",
2485 	[isl_ast_expr_op_pdiv_q] = "pdiv_q",
2486 	[isl_ast_expr_op_pdiv_r] = "pdiv_r",
2487 	[isl_ast_expr_op_zdiv_r] = "zdiv_r",
2488 	[isl_ast_expr_op_cond] = "cond",
2489 	[isl_ast_expr_op_select] = "select",
2490 	[isl_ast_expr_op_eq] = "eq",
2491 	[isl_ast_expr_op_le] = "le",
2492 	[isl_ast_expr_op_lt] = "lt",
2493 	[isl_ast_expr_op_ge] = "ge",
2494 	[isl_ast_expr_op_gt] = "gt",
2495 	[isl_ast_expr_op_call] = "call",
2496 	[isl_ast_expr_op_access] = "access",
2497 	[isl_ast_expr_op_member] = "member",
2498 	[isl_ast_expr_op_address_of] = "address_of"
2499 };
2500 
2501 static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p,
2502 	__isl_keep isl_ast_expr *expr);
2503 
2504 /* Print the arguments of "expr" to "p" in isl format.
2505  *
2506  * If there are no arguments, then nothing needs to be printed.
2507  * Otherwise add an "args" key to the current mapping with as value
2508  * the list of arguments of "expr".
2509  */
print_arguments(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2510 static __isl_give isl_printer *print_arguments(__isl_take isl_printer *p,
2511 	__isl_keep isl_ast_expr *expr)
2512 {
2513 	int i;
2514 	isl_size n;
2515 
2516 	n = isl_ast_expr_get_op_n_arg(expr);
2517 	if (n < 0)
2518 		return isl_printer_free(p);
2519 	if (n == 0)
2520 		return p;
2521 
2522 	p = isl_printer_print_str(p, "args");
2523 	p = isl_printer_yaml_next(p);
2524 	p = isl_printer_yaml_start_sequence(p);
2525 	for (i = 0; i < n; ++i) {
2526 		isl_ast_expr *arg;
2527 
2528 		arg = isl_ast_expr_get_op_arg(expr, i);
2529 		p = print_ast_expr_isl(p, arg);
2530 		isl_ast_expr_free(arg);
2531 		p = isl_printer_yaml_next(p);
2532 	}
2533 	p = isl_printer_yaml_end_sequence(p);
2534 
2535 	return p;
2536 }
2537 
2538 /* Textual representations of the YAML keys for an isl_ast_expr object.
2539  */
2540 static char *expr_str[] = {
2541 	[isl_ast_expr_op] = "op",
2542 	[isl_ast_expr_id] = "id",
2543 	[isl_ast_expr_int] = "val",
2544 };
2545 
2546 /* Print "expr" to "p" in isl format.
2547  *
2548  * In particular, print the isl_ast_expr as a YAML document.
2549  */
print_ast_expr_isl(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2550 static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p,
2551 	__isl_keep isl_ast_expr *expr)
2552 {
2553 	enum isl_ast_expr_type type;
2554 	enum isl_ast_expr_op_type op;
2555 	isl_id *id;
2556 	isl_val *v;
2557 
2558 	if (!expr)
2559 		return isl_printer_free(p);
2560 
2561 	p = isl_printer_yaml_start_mapping(p);
2562 	type = isl_ast_expr_get_type(expr);
2563 	switch (type) {
2564 	case isl_ast_expr_error:
2565 		return isl_printer_free(p);
2566 	case isl_ast_expr_op:
2567 		op = isl_ast_expr_get_op_type(expr);
2568 		if (op == isl_ast_expr_op_error)
2569 			return isl_printer_free(p);
2570 		p = isl_printer_print_str(p, expr_str[type]);
2571 		p = isl_printer_yaml_next(p);
2572 		p = isl_printer_print_str(p, op_str[op]);
2573 		p = isl_printer_yaml_next(p);
2574 		p = print_arguments(p, expr);
2575 		break;
2576 	case isl_ast_expr_id:
2577 		p = isl_printer_print_str(p, expr_str[type]);
2578 		p = isl_printer_yaml_next(p);
2579 		id = isl_ast_expr_get_id(expr);
2580 		p = isl_printer_print_id(p, id);
2581 		isl_id_free(id);
2582 		break;
2583 	case isl_ast_expr_int:
2584 		p = isl_printer_print_str(p, expr_str[type]);
2585 		p = isl_printer_yaml_next(p);
2586 		v = isl_ast_expr_get_val(expr);
2587 		p = isl_printer_print_val(p, v);
2588 		isl_val_free(v);
2589 		break;
2590 	}
2591 	p = isl_printer_yaml_end_mapping(p);
2592 
2593 	return p;
2594 }
2595 
2596 /* Print "expr" to "p".
2597  *
2598  * Only an isl and a C format are supported.
2599  */
isl_printer_print_ast_expr(__isl_take isl_printer * p,__isl_keep isl_ast_expr * expr)2600 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
2601 	__isl_keep isl_ast_expr *expr)
2602 {
2603 	int format;
2604 
2605 	if (!p)
2606 		return NULL;
2607 
2608 	format = isl_printer_get_output_format(p);
2609 	switch (format) {
2610 	case ISL_FORMAT_ISL:
2611 		p = print_ast_expr_isl(p, expr);
2612 		break;
2613 	case ISL_FORMAT_C:
2614 		p = print_ast_expr_c(p, expr);
2615 		break;
2616 	default:
2617 		isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
2618 			"output format not supported for ast_expr",
2619 			return isl_printer_free(p));
2620 	}
2621 
2622 	return p;
2623 }
2624 
2625 #undef KEY
2626 #define KEY		enum isl_ast_expr_op_type
2627 #undef KEY_ERROR
2628 #define KEY_ERROR	isl_ast_expr_op_error
2629 #undef KEY_END
2630 #define KEY_END		(isl_ast_expr_op_address_of + 1)
2631 #undef KEY_STR
2632 #define KEY_STR		op_str
2633 #undef KEY_EXTRACT
2634 #define KEY_EXTRACT	extract_op_type
2635 #undef KEY_GET
2636 #define KEY_GET		get_op_type
2637 #include "extract_key.c"
2638 
2639 /* Return the next token, which is assumed to be a key in a YAML mapping,
2640  * from "s" as a string.
2641  */
next_key(__isl_keep isl_stream * s)2642 static __isl_give char *next_key(__isl_keep isl_stream *s)
2643 {
2644 	struct isl_token *tok;
2645 	char *str;
2646 	isl_ctx *ctx;
2647 
2648 	if (!s)
2649 		return NULL;
2650 	tok = isl_stream_next_token(s);
2651 	if (!tok) {
2652 		isl_stream_error(s, NULL, "unexpected EOF");
2653 		return NULL;
2654 	}
2655 	ctx = isl_stream_get_ctx(s);
2656 	str = isl_token_get_str(ctx, tok);
2657 	isl_token_free(tok);
2658 	return str;
2659 }
2660 
2661 /* Remove the next token, which is assumed to be the key "expected"
2662  * in a YAML mapping, from "s" and move to the corresponding value.
2663  */
eat_key(__isl_keep isl_stream * s,const char * expected)2664 static isl_stat eat_key(__isl_keep isl_stream *s, const char *expected)
2665 {
2666 	char *str;
2667 	int ok;
2668 
2669 	str = next_key(s);
2670 	if (!str)
2671 		return isl_stat_error;
2672 	ok = !strcmp(str, expected);
2673 	free(str);
2674 
2675 	if (!ok) {
2676 		isl_stream_error(s, NULL, "expecting different key");
2677 		return isl_stat_error;
2678 	}
2679 
2680 	if (isl_stream_yaml_next(s) < 0)
2681 		return isl_stat_error;
2682 
2683 	return isl_stat_ok;
2684 }
2685 
2686 #undef EL_BASE
2687 #define EL_BASE ast_expr
2688 
2689 #include <isl_list_read_yaml_templ.c>
2690 
2691 /* Read an isl_ast_expr object of type isl_ast_expr_op from "s",
2692  * where the "op" key has already been read by the caller.
2693  *
2694  * Read the operation type and the arguments and
2695  * return the corresponding isl_ast_expr object.
2696  */
read_op(__isl_keep isl_stream * s)2697 static __isl_give isl_ast_expr *read_op(__isl_keep isl_stream *s)
2698 {
2699 	enum isl_ast_expr_op_type op;
2700 	isl_ast_expr_list *list;
2701 
2702 	op = get_op_type(s);
2703 	if (op < 0)
2704 		return NULL;
2705 	if (isl_stream_yaml_next(s) < 0)
2706 		return NULL;
2707 	if (eat_key(s, "args") < 0)
2708 		return NULL;
2709 
2710 	list = isl_stream_yaml_read_ast_expr_list(s);
2711 
2712 	return alloc_op(op, list);
2713 }
2714 
2715 /* Read an isl_ast_expr object of type isl_ast_expr_id from "s",
2716  * where the "id" key has already been read by the caller.
2717  */
read_id(__isl_keep isl_stream * s)2718 static __isl_give isl_ast_expr *read_id(__isl_keep isl_stream *s)
2719 {
2720 	return isl_ast_expr_from_id(isl_stream_read_id(s));
2721 }
2722 
2723 /* Read an isl_ast_expr object of type isl_ast_expr_int from "s",
2724  * where the "val" key has already been read by the caller.
2725  */
read_int(__isl_keep isl_stream * s)2726 static __isl_give isl_ast_expr *read_int(__isl_keep isl_stream *s)
2727 {
2728 	return isl_ast_expr_from_val(isl_stream_read_val(s));
2729 }
2730 
2731 #undef KEY
2732 #define KEY		enum isl_ast_expr_type
2733 #undef KEY_ERROR
2734 #define KEY_ERROR	isl_ast_expr_error
2735 #undef KEY_END
2736 #define KEY_END		(isl_ast_expr_int + 1)
2737 #undef KEY_STR
2738 #define KEY_STR		expr_str
2739 #undef KEY_EXTRACT
2740 #define KEY_EXTRACT	extract_expr_type
2741 #undef KEY_GET
2742 #define KEY_GET		get_expr_type
2743 #include "extract_key.c"
2744 
2745 /* Read an isl_ast_expr object from "s".
2746  *
2747  * The keys in the YAML mapping are assumed to appear
2748  * in the same order as the one in which they are printed
2749  * by print_ast_expr_isl.
2750  * In particular, the isl_ast_expr_op type, which is the only one
2751  * with more than one element, is identified by the "op" key and
2752  * not by the "args" key.
2753  */
isl_stream_read_ast_expr(__isl_keep isl_stream * s)2754 __isl_give isl_ast_expr *isl_stream_read_ast_expr(__isl_keep isl_stream *s)
2755 {
2756 	enum isl_ast_expr_type type;
2757 	isl_bool more;
2758 	isl_ast_expr *expr;
2759 
2760 	if (isl_stream_yaml_read_start_mapping(s))
2761 		return NULL;
2762 	more = isl_stream_yaml_next(s);
2763 	if (more < 0)
2764 		return NULL;
2765 	if (!more) {
2766 		isl_stream_error(s, NULL, "missing key");
2767 		return NULL;
2768 	}
2769 
2770 	type = get_expr_type(s);
2771 	if (type < 0)
2772 		return NULL;
2773 	if (isl_stream_yaml_next(s) < 0)
2774 		return NULL;
2775 	switch (type) {
2776 	case isl_ast_expr_op:
2777 		expr = read_op(s);
2778 		break;
2779 	case isl_ast_expr_id:
2780 		expr = read_id(s);
2781 		break;
2782 	case isl_ast_expr_int:
2783 		expr = read_int(s);
2784 		break;
2785 	case isl_ast_expr_error:
2786 		return NULL;
2787 	}
2788 
2789 	if (isl_stream_yaml_read_end_mapping(s) < 0)
2790 		return isl_ast_expr_free(expr);
2791 
2792 	return expr;
2793 }
2794 
2795 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
2796 	__isl_keep isl_ast_node *node);
2797 
2798 /* Print a YAML sequence containing the entries in "list" to "p".
2799  */
print_ast_node_list(__isl_take isl_printer * p,__isl_keep isl_ast_node_list * list)2800 static __isl_give isl_printer *print_ast_node_list(__isl_take isl_printer *p,
2801 	__isl_keep isl_ast_node_list *list)
2802 {
2803 	int i;
2804 	isl_size n;
2805 
2806 	n = isl_ast_node_list_n_ast_node(list);
2807 	if (n < 0)
2808 		return isl_printer_free(p);
2809 
2810 	p = isl_printer_yaml_start_sequence(p);
2811 	for (i = 0; i < n; ++i) {
2812 		isl_ast_node *node;
2813 
2814 		node = isl_ast_node_list_get_ast_node(list, i);
2815 		p = print_ast_node_isl(p, node);
2816 		isl_ast_node_free(node);
2817 		p = isl_printer_yaml_next(p);
2818 	}
2819 	p = isl_printer_yaml_end_sequence(p);
2820 
2821 	return p;
2822 }
2823 
2824 /* Print "node" to "p" in "isl format".
2825  *
2826  * In particular, print the isl_ast_node as a YAML document.
2827  */
print_ast_node_isl(__isl_take isl_printer * p,__isl_keep isl_ast_node * node)2828 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
2829 	__isl_keep isl_ast_node *node)
2830 {
2831 	switch (node->type) {
2832 	case isl_ast_node_for:
2833 		p = isl_printer_yaml_start_mapping(p);
2834 		p = isl_printer_print_str(p, "iterator");
2835 		p = isl_printer_yaml_next(p);
2836 		p = isl_printer_print_ast_expr(p, node->u.f.iterator);
2837 		p = isl_printer_yaml_next(p);
2838 		if (node->u.f.degenerate) {
2839 			p = isl_printer_print_str(p, "value");
2840 			p = isl_printer_yaml_next(p);
2841 			p = isl_printer_print_ast_expr(p, node->u.f.init);
2842 			p = isl_printer_yaml_next(p);
2843 		} else {
2844 			p = isl_printer_print_str(p, "init");
2845 			p = isl_printer_yaml_next(p);
2846 			p = isl_printer_print_ast_expr(p, node->u.f.init);
2847 			p = isl_printer_yaml_next(p);
2848 			p = isl_printer_print_str(p, "cond");
2849 			p = isl_printer_yaml_next(p);
2850 			p = isl_printer_print_ast_expr(p, node->u.f.cond);
2851 			p = isl_printer_yaml_next(p);
2852 			p = isl_printer_print_str(p, "inc");
2853 			p = isl_printer_yaml_next(p);
2854 			p = isl_printer_print_ast_expr(p, node->u.f.inc);
2855 			p = isl_printer_yaml_next(p);
2856 		}
2857 		if (node->u.f.body) {
2858 			p = isl_printer_print_str(p, "body");
2859 			p = isl_printer_yaml_next(p);
2860 			p = isl_printer_print_ast_node(p, node->u.f.body);
2861 			p = isl_printer_yaml_next(p);
2862 		}
2863 		p = isl_printer_yaml_end_mapping(p);
2864 		break;
2865 	case isl_ast_node_mark:
2866 		p = isl_printer_yaml_start_mapping(p);
2867 		p = isl_printer_print_str(p, "mark");
2868 		p = isl_printer_yaml_next(p);
2869 		p = isl_printer_print_id(p, node->u.m.mark);
2870 		p = isl_printer_yaml_next(p);
2871 		p = isl_printer_print_str(p, "node");
2872 		p = isl_printer_yaml_next(p);
2873 		p = isl_printer_print_ast_node(p, node->u.m.node);
2874 		p = isl_printer_yaml_end_mapping(p);
2875 		break;
2876 	case isl_ast_node_user:
2877 		p = isl_printer_yaml_start_mapping(p);
2878 		p = isl_printer_print_str(p, "user");
2879 		p = isl_printer_yaml_next(p);
2880 		p = isl_printer_print_ast_expr(p, node->u.e.expr);
2881 		p = isl_printer_yaml_end_mapping(p);
2882 		break;
2883 	case isl_ast_node_if:
2884 		p = isl_printer_yaml_start_mapping(p);
2885 		p = isl_printer_print_str(p, "guard");
2886 		p = isl_printer_yaml_next(p);
2887 		p = isl_printer_print_ast_expr(p, node->u.i.guard);
2888 		p = isl_printer_yaml_next(p);
2889 		if (node->u.i.then) {
2890 			p = isl_printer_print_str(p, "then");
2891 			p = isl_printer_yaml_next(p);
2892 			p = isl_printer_print_ast_node(p, node->u.i.then);
2893 			p = isl_printer_yaml_next(p);
2894 		}
2895 		if (node->u.i.else_node) {
2896 			p = isl_printer_print_str(p, "else");
2897 			p = isl_printer_yaml_next(p);
2898 			p = isl_printer_print_ast_node(p, node->u.i.else_node);
2899 		}
2900 		p = isl_printer_yaml_end_mapping(p);
2901 		break;
2902 	case isl_ast_node_block:
2903 		p = print_ast_node_list(p, node->u.b.children);
2904 		break;
2905 	case isl_ast_node_error:
2906 		break;
2907 	}
2908 	return p;
2909 }
2910 
2911 /* Do we need to print a block around the body "node" of a for or if node?
2912  *
2913  * If the node is a block, then we need to print a block.
2914  * Also if the node is a degenerate for then we will print it as
2915  * an assignment followed by the body of the for loop, so we need a block
2916  * as well.
2917  * If the node is an if node with an else, then we print a block
2918  * to avoid spurious dangling else warnings emitted by some compilers.
2919  * If the node is a mark, then in principle, we would have to check
2920  * the child of the mark node.  However, even if the child would not
2921  * require us to print a block, for readability it is probably best
2922  * to print a block anyway.
2923  * If the ast_always_print_block option has been set, then we print a block.
2924  */
need_block(__isl_keep isl_ast_node * node)2925 static int need_block(__isl_keep isl_ast_node *node)
2926 {
2927 	isl_ctx *ctx;
2928 
2929 	if (node->type == isl_ast_node_block)
2930 		return 1;
2931 	if (node->type == isl_ast_node_for && node->u.f.degenerate)
2932 		return 1;
2933 	if (node->type == isl_ast_node_if && node->u.i.else_node)
2934 		return 1;
2935 	if (node->type == isl_ast_node_mark)
2936 		return 1;
2937 
2938 	ctx = isl_ast_node_get_ctx(node);
2939 	return isl_options_get_ast_always_print_block(ctx);
2940 }
2941 
2942 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
2943 	__isl_keep isl_ast_node *node,
2944 	__isl_keep isl_ast_print_options *options, int in_block, int in_list);
2945 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
2946 	__isl_keep isl_ast_node *node,
2947 	__isl_keep isl_ast_print_options *options, int new_line,
2948 	int force_block);
2949 
2950 /* Print the body "node" of a for or if node.
2951  * If "else_node" is set, then it is printed as well.
2952  * If "force_block" is set, then print out the body as a block.
2953  *
2954  * We first check if we need to print out a block.
2955  * We always print out a block if there is an else node to make
2956  * sure that the else node is matched to the correct if node.
2957  * For consistency, the corresponding else node is also printed as a block.
2958  *
2959  * If the else node is itself an if, then we print it as
2960  *
2961  *	} else if (..) {
2962  *	}
2963  *
2964  * Otherwise the else node is printed as
2965  *
2966  *	} else {
2967  *	  node
2968  *	}
2969  */
print_body_c(__isl_take isl_printer * p,__isl_keep isl_ast_node * node,__isl_keep isl_ast_node * else_node,__isl_keep isl_ast_print_options * options,int force_block)2970 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
2971 	__isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
2972 	__isl_keep isl_ast_print_options *options, int force_block)
2973 {
2974 	if (!node)
2975 		return isl_printer_free(p);
2976 
2977 	if (!force_block && !else_node && !need_block(node)) {
2978 		p = isl_printer_end_line(p);
2979 		p = isl_printer_indent(p, 2);
2980 		p = isl_ast_node_print(node, p,
2981 					isl_ast_print_options_copy(options));
2982 		p = isl_printer_indent(p, -2);
2983 		return p;
2984 	}
2985 
2986 	p = isl_printer_print_str(p, " {");
2987 	p = isl_printer_end_line(p);
2988 	p = isl_printer_indent(p, 2);
2989 	p = print_ast_node_c(p, node, options, 1, 0);
2990 	p = isl_printer_indent(p, -2);
2991 	p = isl_printer_start_line(p);
2992 	p = isl_printer_print_str(p, "}");
2993 	if (else_node) {
2994 		if (else_node->type == isl_ast_node_if) {
2995 			p = isl_printer_print_str(p, " else ");
2996 			p = print_if_c(p, else_node, options, 0, 1);
2997 		} else {
2998 			p = isl_printer_print_str(p, " else");
2999 			p = print_body_c(p, else_node, NULL, options, 1);
3000 		}
3001 	} else
3002 		p = isl_printer_end_line(p);
3003 
3004 	return p;
3005 }
3006 
3007 /* Print the start of a compound statement.
3008  */
start_block(__isl_take isl_printer * p)3009 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
3010 {
3011 	p = isl_printer_start_line(p);
3012 	p = isl_printer_print_str(p, "{");
3013 	p = isl_printer_end_line(p);
3014 	p = isl_printer_indent(p, 2);
3015 
3016 	return p;
3017 }
3018 
3019 /* Print the end of a compound statement.
3020  */
end_block(__isl_take isl_printer * p)3021 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
3022 {
3023 	p = isl_printer_indent(p, -2);
3024 	p = isl_printer_start_line(p);
3025 	p = isl_printer_print_str(p, "}");
3026 	p = isl_printer_end_line(p);
3027 
3028 	return p;
3029 }
3030 
3031 /* Print the for node "node".
3032  *
3033  * If the for node is degenerate, it is printed as
3034  *
3035  *	type iterator = init;
3036  *	body
3037  *
3038  * Otherwise, it is printed as
3039  *
3040  *	for (type iterator = init; cond; iterator += inc)
3041  *		body
3042  *
3043  * "in_block" is set if we are currently inside a block.
3044  * "in_list" is set if the current node is not alone in the block.
3045  * If we are not in a block or if the current not is not alone in the block
3046  * then we print a block around a degenerate for loop such that the variable
3047  * declaration will not conflict with any potential other declaration
3048  * of the same variable.
3049  */
print_for_c(__isl_take isl_printer * p,__isl_keep isl_ast_node * node,__isl_keep isl_ast_print_options * options,int in_block,int in_list)3050 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
3051 	__isl_keep isl_ast_node *node,
3052 	__isl_keep isl_ast_print_options *options, int in_block, int in_list)
3053 {
3054 	isl_id *id;
3055 	const char *name;
3056 	const char *type;
3057 
3058 	type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
3059 	if (!node->u.f.degenerate) {
3060 		id = isl_ast_expr_get_id(node->u.f.iterator);
3061 		name = isl_id_get_name(id);
3062 		isl_id_free(id);
3063 		p = isl_printer_start_line(p);
3064 		p = isl_printer_print_str(p, "for (");
3065 		p = isl_printer_print_str(p, type);
3066 		p = isl_printer_print_str(p, " ");
3067 		p = isl_printer_print_str(p, name);
3068 		p = isl_printer_print_str(p, " = ");
3069 		p = isl_printer_print_ast_expr(p, node->u.f.init);
3070 		p = isl_printer_print_str(p, "; ");
3071 		p = isl_printer_print_ast_expr(p, node->u.f.cond);
3072 		p = isl_printer_print_str(p, "; ");
3073 		p = isl_printer_print_str(p, name);
3074 		p = isl_printer_print_str(p, " += ");
3075 		p = isl_printer_print_ast_expr(p, node->u.f.inc);
3076 		p = isl_printer_print_str(p, ")");
3077 		p = print_body_c(p, node->u.f.body, NULL, options, 0);
3078 	} else {
3079 		id = isl_ast_expr_get_id(node->u.f.iterator);
3080 		name = isl_id_get_name(id);
3081 		isl_id_free(id);
3082 		if (!in_block || in_list)
3083 			p = start_block(p);
3084 		p = isl_printer_start_line(p);
3085 		p = isl_printer_print_str(p, type);
3086 		p = isl_printer_print_str(p, " ");
3087 		p = isl_printer_print_str(p, name);
3088 		p = isl_printer_print_str(p, " = ");
3089 		p = isl_printer_print_ast_expr(p, node->u.f.init);
3090 		p = isl_printer_print_str(p, ";");
3091 		p = isl_printer_end_line(p);
3092 		p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
3093 		if (!in_block || in_list)
3094 			p = end_block(p);
3095 	}
3096 
3097 	return p;
3098 }
3099 
3100 /* Print the if node "node".
3101  * If "new_line" is set then the if node should be printed on a new line.
3102  * If "force_block" is set, then print out the body as a block.
3103  */
print_if_c(__isl_take isl_printer * p,__isl_keep isl_ast_node * node,__isl_keep isl_ast_print_options * options,int new_line,int force_block)3104 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
3105 	__isl_keep isl_ast_node *node,
3106 	__isl_keep isl_ast_print_options *options, int new_line,
3107 	int force_block)
3108 {
3109 	if (new_line)
3110 		p = isl_printer_start_line(p);
3111 	p = isl_printer_print_str(p, "if (");
3112 	p = isl_printer_print_ast_expr(p, node->u.i.guard);
3113 	p = isl_printer_print_str(p, ")");
3114 	p = print_body_c(p, node->u.i.then, node->u.i.else_node, options,
3115 			force_block);
3116 
3117 	return p;
3118 }
3119 
3120 /* Print the "node" to "p".
3121  *
3122  * "in_block" is set if we are currently inside a block.
3123  * If so, we do not print a block around the children of a block node.
3124  * We do this to avoid an extra block around the body of a degenerate
3125  * for node.
3126  *
3127  * "in_list" is set if the current node is not alone in the block.
3128  */
print_ast_node_c(__isl_take isl_printer * p,__isl_keep isl_ast_node * node,__isl_keep isl_ast_print_options * options,int in_block,int in_list)3129 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
3130 	__isl_keep isl_ast_node *node,
3131 	__isl_keep isl_ast_print_options *options, int in_block, int in_list)
3132 {
3133 	switch (node->type) {
3134 	case isl_ast_node_for:
3135 		if (options->print_for)
3136 			return options->print_for(p,
3137 					isl_ast_print_options_copy(options),
3138 					node, options->print_for_user);
3139 		p = print_for_c(p, node, options, in_block, in_list);
3140 		break;
3141 	case isl_ast_node_if:
3142 		p = print_if_c(p, node, options, 1, 0);
3143 		break;
3144 	case isl_ast_node_block:
3145 		if (!in_block)
3146 			p = start_block(p);
3147 		p = isl_ast_node_list_print(node->u.b.children, p, options);
3148 		if (!in_block)
3149 			p = end_block(p);
3150 		break;
3151 	case isl_ast_node_mark:
3152 		p = isl_printer_start_line(p);
3153 		p = isl_printer_print_str(p, "// ");
3154 		p = isl_printer_print_str(p, isl_id_get_name(node->u.m.mark));
3155 		p = isl_printer_end_line(p);
3156 		p = print_ast_node_c(p, node->u.m.node, options, 0, in_list);
3157 		break;
3158 	case isl_ast_node_user:
3159 		if (options->print_user)
3160 			return options->print_user(p,
3161 					isl_ast_print_options_copy(options),
3162 					node, options->print_user_user);
3163 		p = isl_printer_start_line(p);
3164 		p = isl_printer_print_ast_expr(p, node->u.e.expr);
3165 		p = isl_printer_print_str(p, ";");
3166 		p = isl_printer_end_line(p);
3167 		break;
3168 	case isl_ast_node_error:
3169 		break;
3170 	}
3171 	return p;
3172 }
3173 
3174 /* Print the for node "node" to "p".
3175  */
isl_ast_node_for_print(__isl_keep isl_ast_node * node,__isl_take isl_printer * p,__isl_take isl_ast_print_options * options)3176 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
3177 	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3178 {
3179 	if (isl_ast_node_check_for(node) < 0 || !options)
3180 		goto error;
3181 	p = print_for_c(p, node, options, 0, 0);
3182 	isl_ast_print_options_free(options);
3183 	return p;
3184 error:
3185 	isl_ast_print_options_free(options);
3186 	isl_printer_free(p);
3187 	return NULL;
3188 }
3189 
3190 /* Print the if node "node" to "p".
3191  */
isl_ast_node_if_print(__isl_keep isl_ast_node * node,__isl_take isl_printer * p,__isl_take isl_ast_print_options * options)3192 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
3193 	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3194 {
3195 	if (isl_ast_node_check_if(node) < 0 || !options)
3196 		goto error;
3197 	p = print_if_c(p, node, options, 1, 0);
3198 	isl_ast_print_options_free(options);
3199 	return p;
3200 error:
3201 	isl_ast_print_options_free(options);
3202 	isl_printer_free(p);
3203 	return NULL;
3204 }
3205 
3206 /* Print "node" to "p".
3207  *
3208  * "node" is assumed to be either the outermost node in an AST or
3209  * a node that is known not to be a block.
3210  * If "node" is a block (and is therefore outermost) and
3211  * if the ast_print_outermost_block options is not set,
3212  * then act as if the printing occurs inside a block, such
3213  * that no "extra" block will get printed.
3214  */
isl_ast_node_print(__isl_keep isl_ast_node * node,__isl_take isl_printer * p,__isl_take isl_ast_print_options * options)3215 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
3216 	__isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
3217 {
3218 	int in_block = 0;
3219 
3220 	if (!options || !node)
3221 		goto error;
3222 	if (node->type == isl_ast_node_block) {
3223 		isl_ctx *ctx;
3224 
3225 		ctx = isl_ast_node_get_ctx(node);
3226 		in_block = !isl_options_get_ast_print_outermost_block(ctx);
3227 	}
3228 	p = print_ast_node_c(p, node, options, in_block, 0);
3229 	isl_ast_print_options_free(options);
3230 	return p;
3231 error:
3232 	isl_ast_print_options_free(options);
3233 	isl_printer_free(p);
3234 	return NULL;
3235 }
3236 
3237 /* Print "node" to "p".
3238  */
isl_printer_print_ast_node(__isl_take isl_printer * p,__isl_keep isl_ast_node * node)3239 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
3240 	__isl_keep isl_ast_node *node)
3241 {
3242 	int format;
3243 	isl_ast_print_options *options;
3244 
3245 	if (!p)
3246 		return NULL;
3247 
3248 	format = isl_printer_get_output_format(p);
3249 	switch (format) {
3250 	case ISL_FORMAT_ISL:
3251 		p = print_ast_node_isl(p, node);
3252 		break;
3253 	case ISL_FORMAT_C:
3254 		options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
3255 		p = isl_ast_node_print(node, p, options);
3256 		break;
3257 	default:
3258 		isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
3259 			"output format not supported for ast_node",
3260 			return isl_printer_free(p));
3261 	}
3262 
3263 	return p;
3264 }
3265 
3266 /* Print the list of nodes "list" to "p".
3267  */
isl_ast_node_list_print(__isl_keep isl_ast_node_list * list,__isl_take isl_printer * p,__isl_keep isl_ast_print_options * options)3268 __isl_give isl_printer *isl_ast_node_list_print(
3269 	__isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
3270 	__isl_keep isl_ast_print_options *options)
3271 {
3272 	int i;
3273 
3274 	if (!p || !list || !options)
3275 		return isl_printer_free(p);
3276 
3277 	for (i = 0; i < list->n; ++i)
3278 		p = print_ast_node_c(p, list->p[i], options, 1, 1);
3279 
3280 	return p;
3281 }
3282 
3283 /* Is the next token on "s" the start of a YAML sequence
3284  * (rather than a YAML mapping)?
3285  *
3286  * A YAML sequence starts with either a '[' or a '-', depending on the format.
3287  */
next_is_sequence(__isl_keep isl_stream * s)3288 static isl_bool next_is_sequence(__isl_keep isl_stream *s)
3289 {
3290 	struct isl_token *tok;
3291 	int type;
3292 	int seq;
3293 
3294 	tok = isl_stream_next_token(s);
3295 	if (!tok)
3296 		return isl_bool_error;
3297 	type = isl_token_get_type(tok);
3298 	seq = type == '[' || type == '-';
3299 	isl_stream_push_token(s, tok);
3300 
3301 	return isl_bool_ok(seq);
3302 }
3303 
3304 #undef EL_BASE
3305 #define EL_BASE ast_node
3306 
3307 #include <isl_list_read_yaml_templ.c>
3308 
3309 /* Read an isl_ast_node object of type isl_ast_node_block from "s".
3310  */
read_block(__isl_keep isl_stream * s)3311 static __isl_give isl_ast_node *read_block(__isl_keep isl_stream *s)
3312 {
3313 	isl_ast_node_list *children;
3314 
3315 	children = isl_stream_yaml_read_ast_node_list(s);
3316 	return isl_ast_node_block_from_children(children);
3317 }
3318 
3319 /* Textual representation of the first YAML key used
3320  * while printing an isl_ast_node of a given type.
3321  *
3322  * An isl_ast_node of type isl_ast_node_block is not printed
3323  * as a YAML mapping and is therefore assigned a dummy key.
3324  */
3325 static char *node_first_str[] = {
3326 	[isl_ast_node_for] = "iterator",
3327 	[isl_ast_node_mark] = "mark",
3328 	[isl_ast_node_user] = "user",
3329 	[isl_ast_node_if] = "guard",
3330 	[isl_ast_node_block] = "",
3331 };
3332 
3333 #undef KEY
3334 #define KEY		enum isl_ast_node_type
3335 #undef KEY_ERROR
3336 #define KEY_ERROR	isl_ast_node_error
3337 #undef KEY_END
3338 #define KEY_END		(isl_ast_node_user + 1)
3339 #undef KEY_STR
3340 #define KEY_STR		node_first_str
3341 #undef KEY_EXTRACT
3342 #define KEY_EXTRACT	extract_node_type
3343 #undef KEY_GET
3344 #define KEY_GET		get_node_type
3345 #include "extract_key.c"
3346 
read_body(__isl_keep isl_stream * s,__isl_take isl_ast_node * node)3347 static __isl_give isl_ast_node *read_body(__isl_keep isl_stream *s,
3348 	__isl_take isl_ast_node *node)
3349 {
3350 	if (eat_key(s, "body") < 0)
3351 		return isl_ast_node_free(node);
3352 	node = isl_ast_node_for_set_body(node, isl_stream_read_ast_node(s));
3353 	if (isl_stream_yaml_next(s) < 0)
3354 		return isl_ast_node_free(node);
3355 	return node;
3356 }
3357 
3358 /* Read an isl_ast_node object of type isl_ast_node_for from "s",
3359  * where the initial "iterator" key has already been read by the caller.
3360  *
3361  * If the initial value is printed as the value of the key "value",
3362  * then the for-loop is degenerate and can at most have
3363  * a further "body" element.
3364  * Otherwise, the for-loop also has "cond" and "inc" elements.
3365  */
read_for(__isl_keep isl_stream * s)3366 static __isl_give isl_ast_node *read_for(__isl_keep isl_stream *s)
3367 {
3368 	isl_id *id;
3369 	isl_ast_expr *expr;
3370 	isl_ast_node *node;
3371 	char *key;
3372 	isl_bool more;
3373 	int is_value, is_init;
3374 
3375 	expr = isl_stream_read_ast_expr(s);
3376 	id = isl_ast_expr_id_get_id(expr);
3377 	isl_ast_expr_free(expr);
3378 	if (!id)
3379 		return NULL;
3380 	if (isl_stream_yaml_next(s) < 0)
3381 		id = isl_id_free(id);
3382 
3383 	node = isl_ast_node_alloc_for(id);
3384 
3385 	key = next_key(s);
3386 	if (!key)
3387 		return isl_ast_node_free(node);
3388 	is_value = !strcmp(key, "value");
3389 	is_init = !strcmp(key, "init");
3390 	free(key);
3391 	if (!is_value && !is_init)
3392 		isl_die(isl_stream_get_ctx(s), isl_error_invalid,
3393 			"unexpected key", return isl_ast_node_free(node));
3394 	if (isl_stream_yaml_next(s) < 0)
3395 		return isl_ast_node_free(node);
3396 	node = isl_ast_node_for_set_init(node, isl_stream_read_ast_expr(s));
3397 	if ((more = isl_stream_yaml_next(s)) < 0)
3398 		return isl_ast_node_free(node);
3399 	if (is_value) {
3400 		node = isl_ast_node_for_mark_degenerate(node);
3401 		if (more)
3402 			node = read_body(s, node);
3403 		return node;
3404 	}
3405 
3406 	if (eat_key(s, "cond") < 0)
3407 		return isl_ast_node_free(node);
3408 	node = isl_ast_node_for_set_cond(node, isl_stream_read_ast_expr(s));
3409 	if (isl_stream_yaml_next(s) < 0)
3410 		return isl_ast_node_free(node);
3411 	if (eat_key(s, "inc") < 0)
3412 		return isl_ast_node_free(node);
3413 	node = isl_ast_node_for_set_inc(node, isl_stream_read_ast_expr(s));
3414 	if ((more = isl_stream_yaml_next(s)) < 0)
3415 		return isl_ast_node_free(node);
3416 
3417 	if (more)
3418 		node = read_body(s, node);
3419 
3420 	return node;
3421 }
3422 
3423 /* Read an isl_ast_node object of type isl_ast_node_mark from "s",
3424  * where the initial "mark" key has already been read by the caller.
3425  */
read_mark(__isl_keep isl_stream * s)3426 static __isl_give isl_ast_node *read_mark(__isl_keep isl_stream *s)
3427 {
3428 	isl_id *id;
3429 	isl_ast_node *node;
3430 
3431 	id = isl_stream_read_id(s);
3432 	if (!id)
3433 		return NULL;
3434 	if (isl_stream_yaml_next(s) < 0)
3435 		goto error;
3436 	if (eat_key(s, "node") < 0)
3437 		goto error;
3438 	node = isl_stream_read_ast_node(s);
3439 	node = isl_ast_node_alloc_mark(id, node);
3440 	if (isl_stream_yaml_next(s) < 0)
3441 		return isl_ast_node_free(node);
3442 	return node;
3443 error:
3444 	isl_id_free(id);
3445 	return NULL;
3446 }
3447 
3448 /* Read an isl_ast_node object of type isl_ast_node_user from "s",
3449  * where the "user" key has already been read by the caller.
3450  */
read_user(__isl_keep isl_stream * s)3451 static __isl_give isl_ast_node *read_user(__isl_keep isl_stream *s)
3452 {
3453 	isl_ast_node *node;
3454 
3455 	node = isl_ast_node_alloc_user(isl_stream_read_ast_expr(s));
3456 	if (isl_stream_yaml_next(s) < 0)
3457 		return isl_ast_node_free(node);
3458 	return node;
3459 }
3460 
3461 /* Read an isl_ast_node object of type isl_ast_node_if from "s",
3462  * where the initial "guard" key has already been read by the caller.
3463  */
read_if(__isl_keep isl_stream * s)3464 static __isl_give isl_ast_node *read_if(__isl_keep isl_stream *s)
3465 {
3466 	isl_bool more;
3467 	isl_ast_node *node;
3468 
3469 	node = isl_ast_node_alloc_if(isl_stream_read_ast_expr(s));
3470 	if ((more = isl_stream_yaml_next(s)) < 0)
3471 		return isl_ast_node_free(node);
3472 	if (!more)
3473 		return node;
3474 
3475 	if (eat_key(s, "then") < 0)
3476 		return isl_ast_node_free(node);
3477 	node = isl_ast_node_if_set_then(node, isl_stream_read_ast_node(s));
3478 	if ((more = isl_stream_yaml_next(s)) < 0)
3479 		return isl_ast_node_free(node);
3480 	if (!more)
3481 		return node;
3482 
3483 	if (eat_key(s, "else") < 0)
3484 		return isl_ast_node_free(node);
3485 	node = isl_ast_node_if_set_else_node(node, isl_stream_read_ast_node(s));
3486 	if (isl_stream_yaml_next(s) < 0)
3487 		return isl_ast_node_free(node);
3488 
3489 	return node;
3490 }
3491 
3492 /* Read an isl_ast_node object from "s".
3493  *
3494  * A block node is printed as a YAML sequence by print_ast_node_isl.
3495  * Every other node type is printed as a YAML mapping.
3496  *
3497  * First check if the next element is a sequence and if so,
3498  * read a block node.
3499  * Otherwise, read a node based on the first mapping key
3500  * that is used to print a node type.
3501  * Note that the keys in the YAML mapping are assumed to appear
3502  * in the same order as the one in which they are printed
3503  * by print_ast_node_isl.
3504  */
isl_stream_read_ast_node(__isl_keep isl_stream * s)3505 __isl_give isl_ast_node *isl_stream_read_ast_node(__isl_keep isl_stream *s)
3506 {
3507 	enum isl_ast_node_type type;
3508 	isl_bool more;
3509 	isl_bool seq;
3510 	isl_ast_node *node;
3511 
3512 	seq = next_is_sequence(s);
3513 	if (seq < 0)
3514 		return NULL;
3515 	if (seq)
3516 		return read_block(s);
3517 
3518 	if (isl_stream_yaml_read_start_mapping(s))
3519 		return NULL;
3520 	more = isl_stream_yaml_next(s);
3521 	if (more < 0)
3522 		return NULL;
3523 	if (!more) {
3524 		isl_stream_error(s, NULL, "missing key");
3525 		return NULL;
3526 	}
3527 
3528 	type = get_node_type(s);
3529 	if (type < 0)
3530 		return NULL;
3531 	if (isl_stream_yaml_next(s) < 0)
3532 		return NULL;
3533 
3534 	switch (type) {
3535 	case isl_ast_node_block:
3536 		isl_die(isl_stream_get_ctx(s), isl_error_internal,
3537 			"block cannot be detected as mapping",
3538 			return NULL);
3539 	case isl_ast_node_for:
3540 		node = read_for(s);
3541 		break;
3542 	case isl_ast_node_mark:
3543 		node = read_mark(s);
3544 		break;
3545 	case isl_ast_node_user:
3546 		node = read_user(s);
3547 		break;
3548 	case isl_ast_node_if:
3549 		node = read_if(s);
3550 		break;
3551 	case isl_ast_node_error:
3552 		return NULL;
3553 	}
3554 
3555 	if (isl_stream_yaml_read_end_mapping(s) < 0)
3556 		return isl_ast_node_free(node);
3557 
3558 	return node;
3559 }
3560 
3561 #define ISL_AST_MACRO_FDIV_Q	(1 << 0)
3562 #define ISL_AST_MACRO_MIN	(1 << 1)
3563 #define ISL_AST_MACRO_MAX	(1 << 2)
3564 #define ISL_AST_MACRO_ALL	(ISL_AST_MACRO_FDIV_Q | \
3565 				 ISL_AST_MACRO_MIN | \
3566 				 ISL_AST_MACRO_MAX)
3567 
3568 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros);
3569 
3570 /* Wrapper around ast_expr_required_macros for use
3571  * as an isl_ast_expr_list_foreach callback.
3572  */
entry_required_macros(__isl_take isl_ast_expr * expr,void * user)3573 static isl_stat entry_required_macros(__isl_take isl_ast_expr *expr, void *user)
3574 {
3575 	int *macros = user;
3576 
3577 	*macros = ast_expr_required_macros(expr, *macros);
3578 	isl_ast_expr_free(expr);
3579 
3580 	return isl_stat_ok;
3581 }
3582 
3583 /* If "expr" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3584  * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3585  */
ast_expr_required_macros(__isl_keep isl_ast_expr * expr,int macros)3586 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
3587 {
3588 	if (macros == ISL_AST_MACRO_ALL)
3589 		return macros;
3590 
3591 	if (expr->type != isl_ast_expr_op)
3592 		return macros;
3593 
3594 	if (expr->u.op.op == isl_ast_expr_op_min)
3595 		macros |= ISL_AST_MACRO_MIN;
3596 	if (expr->u.op.op == isl_ast_expr_op_max)
3597 		macros |= ISL_AST_MACRO_MAX;
3598 	if (expr->u.op.op == isl_ast_expr_op_fdiv_q)
3599 		macros |= ISL_AST_MACRO_FDIV_Q;
3600 
3601 	isl_ast_expr_list_foreach(expr->u.op.args,
3602 				&entry_required_macros, &macros);
3603 
3604 	return macros;
3605 }
3606 
3607 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
3608 	int macros);
3609 
3610 /* If "node" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3611  * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3612  */
ast_node_required_macros(__isl_keep isl_ast_node * node,int macros)3613 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
3614 {
3615 	if (macros == ISL_AST_MACRO_ALL)
3616 		return macros;
3617 
3618 	switch (node->type) {
3619 	case isl_ast_node_for:
3620 		macros = ast_expr_required_macros(node->u.f.init, macros);
3621 		if (!node->u.f.degenerate) {
3622 			macros = ast_expr_required_macros(node->u.f.cond,
3623 								macros);
3624 			macros = ast_expr_required_macros(node->u.f.inc,
3625 								macros);
3626 		}
3627 		macros = ast_node_required_macros(node->u.f.body, macros);
3628 		break;
3629 	case isl_ast_node_if:
3630 		macros = ast_expr_required_macros(node->u.i.guard, macros);
3631 		macros = ast_node_required_macros(node->u.i.then, macros);
3632 		if (node->u.i.else_node)
3633 			macros = ast_node_required_macros(node->u.i.else_node,
3634 								macros);
3635 		break;
3636 	case isl_ast_node_block:
3637 		macros = ast_node_list_required_macros(node->u.b.children,
3638 							macros);
3639 		break;
3640 	case isl_ast_node_mark:
3641 		macros = ast_node_required_macros(node->u.m.node, macros);
3642 		break;
3643 	case isl_ast_node_user:
3644 		macros = ast_expr_required_macros(node->u.e.expr, macros);
3645 		break;
3646 	case isl_ast_node_error:
3647 		break;
3648 	}
3649 
3650 	return macros;
3651 }
3652 
3653 /* If "list" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or
3654  * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".
3655  */
ast_node_list_required_macros(__isl_keep isl_ast_node_list * list,int macros)3656 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
3657 	int macros)
3658 {
3659 	int i;
3660 
3661 	for (i = 0; i < list->n; ++i)
3662 		macros = ast_node_required_macros(list->p[i], macros);
3663 
3664 	return macros;
3665 }
3666 
3667 /* Data structure for keeping track of whether a macro definition
3668  * for a given type has already been printed.
3669  * The value is zero if no definition has been printed and non-zero otherwise.
3670  */
3671 struct isl_ast_expr_op_printed {
3672 	char printed[isl_ast_expr_op_last + 1];
3673 };
3674 
3675 /* Create an empty struct isl_ast_expr_op_printed.
3676  */
create_printed(isl_ctx * ctx)3677 static void *create_printed(isl_ctx *ctx)
3678 {
3679 	return isl_calloc_type(ctx, struct isl_ast_expr_op_printed);
3680 }
3681 
3682 /* Free a struct isl_ast_expr_op_printed.
3683  */
free_printed(void * user)3684 static void free_printed(void *user)
3685 {
3686 	free(user);
3687 }
3688 
3689 /* Ensure that "p" has an isl_ast_expr_op_printed note identified by "id".
3690  */
alloc_printed(__isl_take isl_printer * p,__isl_keep isl_id * id)3691 static __isl_give isl_printer *alloc_printed(__isl_take isl_printer *p,
3692 	__isl_keep isl_id *id)
3693 {
3694 	return alloc_note(p, id, &create_printed, &free_printed);
3695 }
3696 
3697 /* Create an identifier that is used to store
3698  * an isl_ast_expr_op_printed note.
3699  */
printed_id(isl_ctx * ctx)3700 static __isl_give isl_id *printed_id(isl_ctx *ctx)
3701 {
3702 	return isl_id_alloc(ctx, "isl_ast_expr_op_type_printed", NULL);
3703 }
3704 
3705 /* Did the user specify that a macro definition should only be
3706  * printed once and has a macro definition for "type" already
3707  * been printed to "p"?
3708  * If definitions should only be printed once, but a definition
3709  * for "p" has not yet been printed, then mark it as having been
3710  * printed so that it will not printed again.
3711  * The actual printing is taken care of by the caller.
3712  */
already_printed_once(__isl_keep isl_printer * p,enum isl_ast_expr_op_type type)3713 static isl_bool already_printed_once(__isl_keep isl_printer *p,
3714 	enum isl_ast_expr_op_type type)
3715 {
3716 	isl_ctx *ctx;
3717 	isl_id *id;
3718 	struct isl_ast_expr_op_printed *printed;
3719 
3720 	if (!p)
3721 		return isl_bool_error;
3722 
3723 	ctx = isl_printer_get_ctx(p);
3724 	if (!isl_options_get_ast_print_macro_once(ctx))
3725 		return isl_bool_false;
3726 
3727 	if (type > isl_ast_expr_op_last)
3728 		isl_die(isl_printer_get_ctx(p), isl_error_invalid,
3729 			"invalid type", return isl_bool_error);
3730 
3731 	id = printed_id(isl_printer_get_ctx(p));
3732 	p = alloc_printed(p, id);
3733 	printed = get_note(p, id);
3734 	isl_id_free(id);
3735 	if (!printed)
3736 		return isl_bool_error;
3737 
3738 	if (printed->printed[type])
3739 		return isl_bool_true;
3740 
3741 	printed->printed[type] = 1;
3742 	return isl_bool_false;
3743 }
3744 
3745 /* Print a macro definition for the operator "type".
3746  *
3747  * If the user has specified that a macro definition should
3748  * only be printed once to any given printer and if the macro definition
3749  * has already been printed to "p", then do not print the definition.
3750  */
isl_ast_expr_op_type_print_macro(enum isl_ast_expr_op_type type,__isl_take isl_printer * p)3751 __isl_give isl_printer *isl_ast_expr_op_type_print_macro(
3752 	enum isl_ast_expr_op_type type, __isl_take isl_printer *p)
3753 {
3754 	isl_bool skip;
3755 
3756 	skip = already_printed_once(p, type);
3757 	if (skip < 0)
3758 		return isl_printer_free(p);
3759 	if (skip)
3760 		return p;
3761 
3762 	switch (type) {
3763 	case isl_ast_expr_op_min:
3764 		p = isl_printer_start_line(p);
3765 		p = isl_printer_print_str(p, "#define ");
3766 		p = isl_printer_print_str(p, get_op_str_c(p, type));
3767 		p = isl_printer_print_str(p,
3768 			"(x,y)    ((x) < (y) ? (x) : (y))");
3769 		p = isl_printer_end_line(p);
3770 		break;
3771 	case isl_ast_expr_op_max:
3772 		p = isl_printer_start_line(p);
3773 		p = isl_printer_print_str(p, "#define ");
3774 		p = isl_printer_print_str(p, get_op_str_c(p, type));
3775 		p = isl_printer_print_str(p,
3776 			"(x,y)    ((x) > (y) ? (x) : (y))");
3777 		p = isl_printer_end_line(p);
3778 		break;
3779 	case isl_ast_expr_op_fdiv_q:
3780 		p = isl_printer_start_line(p);
3781 		p = isl_printer_print_str(p, "#define ");
3782 		p = isl_printer_print_str(p, get_op_str_c(p, type));
3783 		p = isl_printer_print_str(p,
3784 			"(n,d) "
3785 			"(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
3786 		p = isl_printer_end_line(p);
3787 		break;
3788 	default:
3789 		break;
3790 	}
3791 
3792 	return p;
3793 }
3794 
3795 /* This is an alternative name for the function above.
3796  */
isl_ast_op_type_print_macro(enum isl_ast_expr_op_type type,__isl_take isl_printer * p)3797 __isl_give isl_printer *isl_ast_op_type_print_macro(
3798 	enum isl_ast_expr_op_type type, __isl_take isl_printer *p)
3799 {
3800 	return isl_ast_expr_op_type_print_macro(type, p);
3801 }
3802 
3803 /* Call "fn" for each type of operation represented in the "macros"
3804  * bit vector.
3805  */
foreach_ast_expr_op_type(int macros,isl_stat (* fn)(enum isl_ast_expr_op_type type,void * user),void * user)3806 static isl_stat foreach_ast_expr_op_type(int macros,
3807 	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3808 {
3809 	if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_expr_op_min, user) < 0)
3810 		return isl_stat_error;
3811 	if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_expr_op_max, user) < 0)
3812 		return isl_stat_error;
3813 	if (macros & ISL_AST_MACRO_FDIV_Q &&
3814 	    fn(isl_ast_expr_op_fdiv_q, user) < 0)
3815 		return isl_stat_error;
3816 
3817 	return isl_stat_ok;
3818 }
3819 
3820 /* Call "fn" for each type of operation that appears in "expr"
3821  * and that requires a macro definition.
3822  */
isl_ast_expr_foreach_ast_expr_op_type(__isl_keep isl_ast_expr * expr,isl_stat (* fn)(enum isl_ast_expr_op_type type,void * user),void * user)3823 isl_stat isl_ast_expr_foreach_ast_expr_op_type(__isl_keep isl_ast_expr *expr,
3824 	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3825 {
3826 	int macros;
3827 
3828 	if (!expr)
3829 		return isl_stat_error;
3830 
3831 	macros = ast_expr_required_macros(expr, 0);
3832 	return foreach_ast_expr_op_type(macros, fn, user);
3833 }
3834 
3835 /* This is an alternative name for the function above.
3836  */
isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr * expr,isl_stat (* fn)(enum isl_ast_expr_op_type type,void * user),void * user)3837 isl_stat isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr *expr,
3838 	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3839 {
3840 	return isl_ast_expr_foreach_ast_expr_op_type(expr, fn, user);
3841 }
3842 
3843 /* Call "fn" for each type of operation that appears in "node"
3844  * and that requires a macro definition.
3845  */
isl_ast_node_foreach_ast_expr_op_type(__isl_keep isl_ast_node * node,isl_stat (* fn)(enum isl_ast_expr_op_type type,void * user),void * user)3846 isl_stat isl_ast_node_foreach_ast_expr_op_type(__isl_keep isl_ast_node *node,
3847 	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3848 {
3849 	int macros;
3850 
3851 	if (!node)
3852 		return isl_stat_error;
3853 
3854 	macros = ast_node_required_macros(node, 0);
3855 	return foreach_ast_expr_op_type(macros, fn, user);
3856 }
3857 
3858 /* This is an alternative name for the function above.
3859  */
isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node * node,isl_stat (* fn)(enum isl_ast_expr_op_type type,void * user),void * user)3860 isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
3861 	isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user)
3862 {
3863 	return isl_ast_node_foreach_ast_expr_op_type(node, fn, user);
3864 }
3865 
ast_op_type_print_macro(enum isl_ast_expr_op_type type,void * user)3866 static isl_stat ast_op_type_print_macro(enum isl_ast_expr_op_type type,
3867 	void *user)
3868 {
3869 	isl_printer **p = user;
3870 
3871 	*p = isl_ast_expr_op_type_print_macro(type, *p);
3872 
3873 	return isl_stat_ok;
3874 }
3875 
3876 /* Print macro definitions for all the macros used in the result
3877  * of printing "expr".
3878  */
isl_ast_expr_print_macros(__isl_keep isl_ast_expr * expr,__isl_take isl_printer * p)3879 __isl_give isl_printer *isl_ast_expr_print_macros(
3880 	__isl_keep isl_ast_expr *expr, __isl_take isl_printer *p)
3881 {
3882 	if (isl_ast_expr_foreach_ast_expr_op_type(expr,
3883 					    &ast_op_type_print_macro, &p) < 0)
3884 		return isl_printer_free(p);
3885 	return p;
3886 }
3887 
3888 /* Print macro definitions for all the macros used in the result
3889  * of printing "node".
3890  */
isl_ast_node_print_macros(__isl_keep isl_ast_node * node,__isl_take isl_printer * p)3891 __isl_give isl_printer *isl_ast_node_print_macros(
3892 	__isl_keep isl_ast_node *node, __isl_take isl_printer *p)
3893 {
3894 	if (isl_ast_node_foreach_ast_expr_op_type(node,
3895 					    &ast_op_type_print_macro, &p) < 0)
3896 		return isl_printer_free(p);
3897 	return p;
3898 }
3899 
3900 /* Return a string containing C code representing this isl_ast_expr.
3901  */
isl_ast_expr_to_C_str(__isl_keep isl_ast_expr * expr)3902 __isl_give char *isl_ast_expr_to_C_str(__isl_keep isl_ast_expr *expr)
3903 {
3904 	isl_printer *p;
3905 	char *str;
3906 
3907 	if (!expr)
3908 		return NULL;
3909 
3910 	p = isl_printer_to_str(isl_ast_expr_get_ctx(expr));
3911 	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
3912 	p = isl_printer_print_ast_expr(p, expr);
3913 
3914 	str = isl_printer_get_str(p);
3915 
3916 	isl_printer_free(p);
3917 
3918 	return str;
3919 }
3920 
3921 /* Return a string containing C code representing this isl_ast_node.
3922  */
isl_ast_node_to_C_str(__isl_keep isl_ast_node * node)3923 __isl_give char *isl_ast_node_to_C_str(__isl_keep isl_ast_node *node)
3924 {
3925 	isl_printer *p;
3926 	char *str;
3927 
3928 	if (!node)
3929 		return NULL;
3930 
3931 	p = isl_printer_to_str(isl_ast_node_get_ctx(node));
3932 	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
3933 	p = isl_printer_print_ast_node(p, node);
3934 
3935 	str = isl_printer_get_str(p);
3936 
3937 	isl_printer_free(p);
3938 
3939 	return str;
3940 }
3941