brintos / llvm-project-archived public Read only

1/*2 * Copyright 2012-2013 Ecole Normale Superieure3 * Copyright 2022      Cerebras Systems4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege,8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France9 * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA10 */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_BASE20#define EL_BASE ast_expr21 22#include <isl_list_templ.c>23 24#undef EL_BASE25#define EL_BASE ast_node26 27#include <isl_list_templ.c>28 29isl_ctx *isl_ast_print_options_get_ctx(30	__isl_keep isl_ast_print_options *options)31{32	return options ? options->ctx : NULL;33}34 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 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 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 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 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 */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 */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 */155static __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;177error: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 */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 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 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 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 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 271isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)272{273	return expr ? expr->ctx : NULL;274}275 276enum 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 */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 */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 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 */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 */320static 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 */332enum 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 */342enum 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 */350isl_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 */359isl_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 */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 */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 */385static __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 themselves395 * if there is only one reference to "expr".396 * This allows the arguments to be modified inplace397 * if both "expr" and its arguments have only a single reference.398 * The caller is not allowed to modify "expr" between this call and399 * 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 */402static __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 missing418 * due to a preceding call to isl_ast_expr_op_take_args.419 * However, in this case, "expr" only has a single reference and420 * then the call to isl_ast_expr_cow has no effect.421 */422static __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;440error: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 */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 */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 */476static 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 */511isl_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 */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;561error:562	isl_id_free(id);563	return NULL;564}565 566/* Create a new integer expression representing "i".567 */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 */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;612error:613	isl_val_free(v);614	return NULL;615}616 617/* Create an expression representing the unary operation "type" applied to618 * "arg".619 */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 */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 */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 */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;686error: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 */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 */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 */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 */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 integer725 * division of "expr1" by "expr2", where "expr1" is known to be726 * non-negative.727 */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 integer735 * division of "expr1" by "expr2", where "expr1" is known to be736 * non-negative.737 */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 */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 */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 */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 */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 */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 */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 */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 */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 */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" followed819 * by "arguments".820 */821static __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 index830 * expressions "indices".831 */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 argument839 * expressions "arguments".840 */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 use848 * as an isl_ast_expr_list_map callback.849 */850static __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 corresponding861 * expression.862 */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;896error:897	isl_ast_expr_free(expr);898	isl_id_to_ast_expr_free(id2expr);899	return NULL;900}901 902isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)903{904	return node ? node->ctx : NULL;905}906 907enum 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 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 */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;946error: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 */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;973error:974	isl_id_free(id);975	return NULL;976}977 978/* Create a mark node, marking "node" with "id".979 */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;998error:999	isl_id_free(id);1000	isl_ast_node_free(node);1001	return NULL;1002}1003 1004/* Create a user node evaluating "expr".1005 */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;1023error:1024	isl_ast_expr_free(expr);1025	return NULL;1026}1027 1028/* This is an alternative name for the function above.1029 */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 */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;1054error:1055	isl_ast_node_list_free(list);1056	return NULL;1057}1058 1059/* This is an alternative name for the function above.1060 */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 by1068 * extract the node from a single element list or by creating1069 * a block node with the list of nodes as children.1070 */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;1087error:1088	isl_ast_node_list_free(list);1089	return NULL;1090}1091 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 account1104 * that "cond" and "inc" are NULL.1105 */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 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 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 */1224static 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 */1237static 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 */1245static 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 */1252static 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 */1260static 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 */1268static 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_TYPE1275#define NODE_TYPE	for1276#undef FIELD_NAME1277#define FIELD_NAME	init1278#undef FIELD_TYPE1279#define FIELD_TYPE	isl_ast_expr1280#undef FIELD1281#define FIELD		u.f.init1282#include "isl_ast_node_set_field_templ.c"1283 1284#undef NODE_TYPE1285#define NODE_TYPE	for1286#undef FIELD_NAME1287#define FIELD_NAME	cond1288#undef FIELD_TYPE1289#define FIELD_TYPE	isl_ast_expr1290#undef FIELD1291#define FIELD		u.f.cond1292#include "isl_ast_node_set_field_templ.c"1293 1294#undef NODE_TYPE1295#define NODE_TYPE	for1296#undef FIELD_NAME1297#define FIELD_NAME	inc1298#undef FIELD_TYPE1299#define FIELD_TYPE	isl_ast_expr1300#undef FIELD1301#define FIELD		u.f.inc1302#include "isl_ast_node_set_field_templ.c"1303 1304#undef NODE_TYPE1305#define NODE_TYPE	for1306#undef FIELD_NAME1307#define FIELD_NAME	body1308#undef FIELD_TYPE1309#define FIELD_TYPE	isl_ast_node1310#undef FIELD1311#define FIELD		u.f.body1312#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 itself1316 * if there is only one reference to "node".1317 * This allows the body to be modified inplace1318 * if both "node" and its body have only a single reference.1319 * The caller is not allowed to modify "node" between this call and1320 * 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 */1323static __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 missing1339 * due to a preceding call to isl_ast_node_for_take_body.1340 * However, in this case, "node" only has a single reference.1341 */1342static __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 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 */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 1368isl_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 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 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 explicitly1394 * stored in the node.  Instead, it is constructed as1395 *1396 *	iterator <= init1397 */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 explicitly1414 * stored in the node.  We simply return "1".1415 */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_TYPE1427#define NODE_TYPE	if1428#undef FIELD_NAME1429#define FIELD_NAME	then1430#undef FIELD_TYPE1431#define FIELD_TYPE	isl_ast_node1432#undef FIELD1433#define FIELD		u.i.then1434#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 itself1438 * if there is only one reference to "node".1439 * This allows the branch to be modified inplace1440 * if both "node" and its then-branch have only a single reference.1441 * The caller is not allowed to modify "node" between this call and1442 * 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 */1445static __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 missing1461 * 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 */1464static __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 */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 */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 */1490isl_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 */1499isl_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 */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 */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_TYPE1524#define NODE_TYPE	if1525#undef FIELD_NAME1526#define FIELD_NAME	else_node1527#undef FIELD_TYPE1528#define FIELD_TYPE	isl_ast_node1529#undef FIELD1530#define FIELD		u.i.else_node1531static1532#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 itself1536 * if there is only one reference to "node".1537 * This allows the branch to be modified inplace1538 * if both "node" and its else-branch have only a single reference.1539 * The caller is not allowed to modify "node" between this call and1540 * 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 */1543static __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 missing1559 * 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 */1562static __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 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 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_TYPE1585#define NODE_TYPE	block1586#undef FIELD_NAME1587#define FIELD_NAME	children1588#undef FIELD_TYPE1589#define FIELD_TYPE	isl_ast_node_list1590#undef FIELD1591#define FIELD		u.b.children1592static1593#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 themselves1597 * if there is only one reference to "node".1598 * This allows the children to be modified inplace1599 * if both "node" and its children have only a single reference.1600 * The caller is not allowed to modify "node" between this call and1601 * 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 */1604static __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 missing1620 * due to a preceding call to isl_ast_node_block_take_children.1621 * However, in this case, "node" only has a single reference.1622 */1623static __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 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 */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 */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_TYPE1660#define NODE_TYPE	mark1661#undef FIELD_NAME1662#define FIELD_NAME	node1663#undef FIELD_TYPE1664#define FIELD_TYPE	isl_ast_node1665#undef FIELD1666#define FIELD		u.m.node1667static1668#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 itself1672 * if there is only one reference to "node".1673 * This allows the child to be modified inplace1674 * if both "node" and its child have only a single reference.1675 * The caller is not allowed to modify "node" between this call and1676 * 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 */1679static __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 missing1695 * due to a preceding call to isl_ast_node_mark_take_node.1696 * However, in this case, "node" only has a single reference.1697 */1698static __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 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 */1712static 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_TYPE1718#define NODE_TYPE	any1719#undef FIELD_NAME1720#define FIELD_NAME	annotation1721#undef FIELD_TYPE1722#define FIELD_TYPE	isl_id1723#undef FIELD1724#define FIELD		annotation1725static1726#include "isl_ast_node_set_field_templ.c"1727 1728/* Replace node->annotation by "annotation".1729 */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 1736static __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 descendants1744 * 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 */1749static __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 rooted1780 * at the given node is skipped.1781 *1782 * Return the updated node.1783 */1784static __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 of1841 * isl_ast_node_foreach_descendant_top_down.1842 */1843struct 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 and1851 * let it decide whether to continue.1852 */1853static __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 */1872static __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 traversal1882 * is aborted.1883 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted1884 * at that node is skipped.1885 *1886 * Return isl_stat_ok on success and isl_stat_error on failure.1887 */1888isl_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 of1902 * isl_ast_node_map_descendant_bottom_up.1903 */1904struct 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 */1915static __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 */1926static __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 the1940 * visited node.1941 *1942 * Return the updated node.1943 */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 */1956static 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 */1985static 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] = 32012};2013 2014/* Is the operator left-to-right associative?2015 */2016static 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] = 02043};2044 2045static 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 2050static 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 2055static 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 2060static 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 2067static __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 of2071 * an "op" operation?  If "left" is set, then "expr" is the left-most2072 * 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 need2077 * parentheses.2078 * If op and expr->u.op.op have the same precedence, but the operations2079 * 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 somewhat2086 * difficult to read, so we add parentheses for those as well.2087 */2088static 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 */2114static __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_of2138 2139/* Data structure that holds the user-specified textual2140 * 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 */2144struct 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 */2150static 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 memory2156 * owned by the struct.2157 */2158static 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 store2172 * an isl_ast_expr_op_names note.2173 */2174static __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" and2181 * scheduled do be freed by "note_free".2182 */2183static __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	else2206		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 */2215static __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 */2224static 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 that2238 * it can be retrieved by get_op_str.2239 */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 */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 note2277 * associated to "p", then return that.2278 * Otherwise, return the default name in op_str_c.2279 */2280static 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 */2299static __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 */2313static __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 */2341static __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 */2367static __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 */2389static __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 elements2470 * for use in a YAML representation of an isl_ast_expr.2471 */2472static 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 2501static __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 value2508 * the list of arguments of "expr".2509 */2510static __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 */2540static 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 */2550static __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 */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 KEY2626#define KEY		enum isl_ast_expr_op_type2627#undef KEY_ERROR2628#define KEY_ERROR	isl_ast_expr_op_error2629#undef KEY_END2630#define KEY_END		(isl_ast_expr_op_address_of + 1)2631#undef KEY_STR2632#define KEY_STR		op_str2633#undef KEY_EXTRACT2634#define KEY_EXTRACT	extract_op_type2635#undef KEY_GET2636#define KEY_GET		get_op_type2637#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 */2642static __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 */2664static 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_BASE2687#define EL_BASE ast_expr2688 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 and2695 * return the corresponding isl_ast_expr object.2696 */2697static __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 */2718static __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 */2726static __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 KEY2732#define KEY		enum isl_ast_expr_type2733#undef KEY_ERROR2734#define KEY_ERROR	isl_ast_expr_error2735#undef KEY_END2736#define KEY_END		(isl_ast_expr_int + 1)2737#undef KEY_STR2738#define KEY_STR		expr_str2739#undef KEY_EXTRACT2740#define KEY_EXTRACT	extract_expr_type2741#undef KEY_GET2742#define KEY_GET		get_expr_type2743#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 appear2748 * in the same order as the one in which they are printed2749 * by print_ast_expr_isl.2750 * In particular, the isl_ast_expr_op type, which is the only one2751 * with more than one element, is identified by the "op" key and2752 * not by the "args" key.2753 */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 2795static __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 */2800static __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 */2828static __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 as2915 * an assignment followed by the body of the for loop, so we need a block2916 * as well.2917 * If the node is an if node with an else, then we print a block2918 * to avoid spurious dangling else warnings emitted by some compilers.2919 * If the node is a mark, then in principle, we would have to check2920 * the child of the mark node.  However, even if the child would not2921 * require us to print a block, for readability it is probably best2922 * to print a block anyway.2923 * If the ast_always_print_block option has been set, then we print a block.2924 */2925static 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 2942static __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);2945static __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 make2956 * 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 as2960 *2961 *	} else if (..) {2962 *	}2963 *2964 * Otherwise the else node is printed as2965 *2966 *	} else {2967 *	  node2968 *	}2969 */2970static __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	} else3002		p = isl_printer_end_line(p);3003 3004	return p;3005}3006 3007/* Print the start of a compound statement.3008 */3009static __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 */3021static __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 as3034 *3035 *	type iterator = init;3036 *	body3037 *3038 * Otherwise, it is printed as3039 *3040 *	for (type iterator = init; cond; iterator += inc)3041 *		body3042 *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 block3046 * then we print a block around a degenerate for loop such that the variable3047 * declaration will not conflict with any potential other declaration3048 * of the same variable.3049 */3050static __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 */3104static __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 degenerate3125 * for node.3126 *3127 * "in_list" is set if the current node is not alone in the block.3128 */3129static __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 */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;3184error: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 */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;3200error: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 or3209 * a node that is known not to be a block.3210 * If "node" is a block (and is therefore outermost) and3211 * if the ast_print_outermost_block options is not set,3212 * then act as if the printing occurs inside a block, such3213 * that no "extra" block will get printed.3214 */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;3231error:3232	isl_ast_print_options_free(options);3233	isl_printer_free(p);3234	return NULL;3235}3236 3237/* Print "node" to "p".3238 */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 */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 sequence3284 * (rather than a YAML mapping)?3285 *3286 * A YAML sequence starts with either a '[' or a '-', depending on the format.3287 */3288static 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_BASE3305#define EL_BASE ast_node3306 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 */3311static __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 used3320 * while printing an isl_ast_node of a given type.3321 *3322 * An isl_ast_node of type isl_ast_node_block is not printed3323 * as a YAML mapping and is therefore assigned a dummy key.3324 */3325static 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 KEY3334#define KEY		enum isl_ast_node_type3335#undef KEY_ERROR3336#define KEY_ERROR	isl_ast_node_error3337#undef KEY_END3338#define KEY_END		(isl_ast_node_user + 1)3339#undef KEY_STR3340#define KEY_STR		node_first_str3341#undef KEY_EXTRACT3342#define KEY_EXTRACT	extract_node_type3343#undef KEY_GET3344#define KEY_GET		get_node_type3345#include "extract_key.c"3346 3347static __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 have3363 * a further "body" element.3364 * Otherwise, the for-loop also has "cond" and "inc" elements.3365 */3366static __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 */3426static __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;3443error: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 */3451static __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 */3464static __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 key3500 * that is used to print a node type.3501 * Note that the keys in the YAML mapping are assumed to appear3502 * in the same order as the one in which they are printed3503 * by print_ast_node_isl.3504 */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 3568static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros);3569 3570/* Wrapper around ast_expr_required_macros for use3571 * as an isl_ast_expr_list_foreach callback.3572 */3573static 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 or3584 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".3585 */3586static 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 3607static 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 or3611 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".3612 */3613static 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 or3654 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros".3655 */3656static 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 definition3668 * for a given type has already been printed.3669 * The value is zero if no definition has been printed and non-zero otherwise.3670 */3671struct 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 */3677static 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 */3684static 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 */3691static __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 store3698 * an isl_ast_expr_op_printed note.3699 */3700static __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 be3706 * printed once and has a macro definition for "type" already3707 * been printed to "p"?3708 * If definitions should only be printed once, but a definition3709 * for "p" has not yet been printed, then mark it as having been3710 * printed so that it will not printed again.3711 * The actual printing is taken care of by the caller.3712 */3713static 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 should3748 * only be printed once to any given printer and if the macro definition3749 * has already been printed to "p", then do not print the definition.3750 */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 */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 */3806static 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 */3823isl_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 */3837isl_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 */3846isl_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 */3860isl_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 3866static 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 result3877 * of printing "expr".3878 */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 result3889 * of printing "node".3890 */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 */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 */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