1	/*
2	* Copyright 2012 Ecole Normale Superieure
3	* Copyright 2014 INRIA Rocquencourt
4	* Copyright 2019 Cerebras Systems
5	*
6	* Use of this software is governed by the MIT license
7	*
8	* Written by Sven Verdoolaege,
9	* Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
10	* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11	* B.P. 105 - 78153 Le Chesnay, France
12	* and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
13	*/
14
15	#include <isl/id.h>
16	#include <isl/space.h>
17	#include <isl/stream.h>
18	#include <isl_ast_private.h>
19	#include <isl_ast_build_expr.h>
20	#include <isl_ast_build_private.h>
21	#include <isl_ast_graft_private.h>
22	#include "isl_set_to_ast_graft_list.h"
23
24	static __isl_give isl_ast_graft *isl_ast_graft_copy(
25	__isl_keep isl_ast_graft *graft);
26	static __isl_give isl_ast_graft *isl_stream_read_ast_graft(
27	__isl_keep isl_stream *s);
28
29	#undef EL_BASE
30	#define EL_BASE ast_graft
31
32	#include <isl_list_templ.c>
33	#include <isl_list_read_templ.c>
34
35	#undef BASE
36	#define BASE ast_graft
37	#include <print_templ.c>
38
39	isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)
40	{
41	if (!graft)
42	return NULL;
43	return isl_basic_set_get_ctx(bset: graft->enforced);
44	}
45
46	__isl_give isl_ast_node *isl_ast_graft_get_node(
47	__isl_keep isl_ast_graft *graft)
48	{
49	return graft ? isl_ast_node_copy(node: graft->node) : NULL;
50	}
51
52	/* Create a graft for "node" with guards "guard" and
53	* enforced conditions "enforced".
54	*/
55	static isl_ast_graft *graft_alloc(__isl_take isl_ast_node *node,
56	__isl_take isl_set *guard, __isl_take isl_basic_set *enforced)
57	{
58	isl_ctx *ctx;
59	isl_ast_graft *graft;
60
61	if (!node || !guard || !enforced)
62	goto error;
63
64	ctx = isl_ast_node_get_ctx(node);
65	graft = isl_calloc_type(ctx, isl_ast_graft);
66	if (!graft)
67	goto error;
68
69	graft->ref = 1;
70	graft->node = node;
71	graft->guard = guard;
72	graft->enforced = enforced;
73
74	return graft;
75	error:
76	isl_ast_node_free(node);
77	isl_set_free(set: guard);
78	isl_basic_set_free(bset: enforced);
79	return NULL;
80	}
81
82	/* Create a graft for "node" with no guards and no enforced conditions.
83	*/
84	__isl_give isl_ast_graft *isl_ast_graft_alloc(
85	__isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)
86	{
87	isl_space *space;
88	isl_set *guard;
89	isl_basic_set *enforced;
90
91	if (!node)
92	return NULL;
93
94	space = isl_ast_build_get_space(build, internal: 1);
95
96	guard = isl_set_universe(space: isl_space_copy(space));
97	enforced = isl_basic_set_universe(space);
98
99	return graft_alloc(node, guard, enforced);
100	}
101
102	/* Create a graft with no guards and no enforced conditions
103	* encapsulating a call to the domain element specified by "executed".
104	* "executed" is assumed to be single-valued.
105	*/
106	__isl_give isl_ast_graft *isl_ast_graft_alloc_domain(
107	__isl_take isl_map *executed, __isl_keep isl_ast_build *build)
108	{
109	isl_ast_node *node;
110
111	node = isl_ast_build_call_from_executed(build, executed);
112
113	return isl_ast_graft_alloc(node, build);
114	}
115
116	static __isl_give isl_ast_graft *isl_ast_graft_copy(
117	__isl_keep isl_ast_graft *graft)
118	{
119	if (!graft)
120	return NULL;
121
122	graft->ref++;
123	return graft;
124	}
125
126	/* Do all the grafts in "list" have the same guard and is this guard
127	* independent of the current depth?
128	*/
129	static isl_bool equal_independent_guards(__isl_keep isl_ast_graft_list *list,
130	__isl_keep isl_ast_build *build)
131	{
132	int i;
133	isl_size n;
134	isl_size depth;
135	isl_size dim;
136	isl_ast_graft *graft_0;
137	isl_bool equal = isl_bool_true;
138	isl_bool skip;
139
140	n = isl_ast_graft_list_n_ast_graft(list);
141	depth = isl_ast_build_get_depth(build);
142	if (n < 0 || depth < 0)
143	return isl_bool_error;
144	graft_0 = isl_ast_graft_list_get_ast_graft(list, index: 0);
145	if (!graft_0)
146	return isl_bool_error;
147
148	dim = isl_set_dim(set: graft_0->guard, type: isl_dim_set);
149	if (dim < 0)
150	skip = isl_bool_error;
151	else if (dim <= depth)
152	skip = isl_bool_false;
153	else
154	skip = isl_set_involves_dims(set: graft_0->guard,
155	type: isl_dim_set, first: depth, n: 1);
156	if (skip < 0 || skip) {
157	isl_ast_graft_free(graft: graft_0);
158	return isl_bool_not(b: skip);
159	}
160
161	for (i = 1; i < n; ++i) {
162	isl_ast_graft *graft;
163	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
164	if (!graft)
165	equal = isl_bool_error;
166	else
167	equal = isl_set_is_equal(set1: graft_0->guard, set2: graft->guard);
168	isl_ast_graft_free(graft);
169	if (equal < 0 || !equal)
170	break;
171	}
172
173	isl_ast_graft_free(graft: graft_0);
174
175	return equal;
176	}
177
178	/* Hoist "guard" out of the current level (given by "build").
179	*
180	* In particular, eliminate the dimension corresponding to the current depth.
181	*/
182	static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,
183	__isl_keep isl_ast_build *build)
184	{
185	isl_size depth;
186	isl_size dim;
187
188	depth = isl_ast_build_get_depth(build);
189	dim = isl_set_dim(set: guard, type: isl_dim_set);
190	if (depth < 0 || dim < 0)
191	return isl_set_free(set: guard);
192	if (depth < dim) {
193	guard = isl_set_remove_divs_involving_dims(set: guard,
194	type: isl_dim_set, first: depth, n: 1);
195	guard = isl_set_eliminate(set: guard, type: isl_dim_set, first: depth, n: 1);
196	guard = isl_set_compute_divs(set: guard);
197	}
198
199	return guard;
200	}
201
202	/* Extract a common guard from the grafts in "list" that can be hoisted
203	* out of the current level. If no such guard can be found, then return
204	* a universal set.
205	*
206	* If all the grafts in the list have the same guard and if this guard
207	* is independent of the current level, then it can be hoisted out.
208	* If there is only one graft in the list and if its guard
209	* depends on the current level, then we eliminate this level and
210	* return the result.
211	*
212	* Otherwise, we return the unshifted simple hull of the guards.
213	* In order to be able to hoist as many constraints as possible,
214	* but at the same time avoid hoisting constraints that did not
215	* appear in the guards in the first place, we intersect the guards
216	* with all the information that is available (i.e., the domain
217	* from the build and the enforced constraints of the graft) and
218	* compute the unshifted hull of the result using only constraints
219	* from the original guards.
220	* In particular, intersecting the guards with other known information
221	* allows us to hoist guards that are only explicit is some of
222	* the grafts and implicit in the others.
223	*
224	* The special case for equal guards is needed in case those guards
225	* are non-convex. Taking the simple hull would remove information
226	* and would not allow for these guards to be hoisted completely.
227	*/
228	__isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(
229	__isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
230	{
231	int i;
232	isl_size n;
233	isl_bool equal;
234	isl_ctx *ctx;
235	isl_set *guard;
236	isl_set_list *set_list;
237	isl_basic_set *hull;
238
239	if (!list || !build)
240	return NULL;
241
242	n = isl_ast_graft_list_n_ast_graft(list);
243	if (n < 0)
244	return NULL;
245	if (n == 0)
246	return isl_set_universe(space: isl_ast_build_get_space(build, internal: 1));
247
248	equal = equal_independent_guards(list, build);
249	if (equal < 0)
250	return NULL;
251
252	if (equal || n == 1) {
253	isl_ast_graft *graft_0;
254
255	graft_0 = isl_ast_graft_list_get_ast_graft(list, index: 0);
256	if (!graft_0)
257	return NULL;
258	guard = isl_set_copy(set: graft_0->guard);
259	if (!equal)
260	guard = hoist_guard(guard, build);
261	isl_ast_graft_free(graft: graft_0);
262	return guard;
263	}
264
265	ctx = isl_ast_build_get_ctx(build);
266	set_list = isl_set_list_alloc(ctx, n);
267	guard = isl_set_empty(space: isl_ast_build_get_space(build, internal: 1));
268	for (i = 0; i < n; ++i) {
269	isl_ast_graft *graft;
270	isl_basic_set *enforced;
271	isl_set *guard_i;
272
273	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
274	enforced = isl_ast_graft_get_enforced(graft);
275	guard_i = isl_set_copy(set: graft->guard);
276	isl_ast_graft_free(graft);
277	set_list = isl_set_list_add(list: set_list, el: isl_set_copy(set: guard_i));
278	guard_i = isl_set_intersect(set1: guard_i,
279	set2: isl_set_from_basic_set(bset: enforced));
280	guard_i = isl_set_intersect(set1: guard_i,
281	set2: isl_ast_build_get_domain(build));
282	guard = isl_set_union(set1: guard, set2: guard_i);
283	}
284	hull = isl_set_unshifted_simple_hull_from_set_list(set: guard, list: set_list);
285	guard = isl_set_from_basic_set(bset: hull);
286	return hoist_guard(guard, build);
287	}
288
289	/* Internal data structure used inside insert_if.
290	*
291	* list is the list of guarded nodes created by each call to insert_if.
292	* node is the original node that is guarded by insert_if.
293	* build is the build in which the AST is constructed.
294	*/
295	struct isl_insert_if_data {
296	isl_ast_node_list *list;
297	isl_ast_node *node;
298	isl_ast_build *build;
299	};
300
301	static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user);
302
303	/* Insert an if node around "node" testing the condition encoded
304	* in guard "guard".
305	*
306	* If the user does not want any disjunctions in the if conditions
307	* and if "guard" does involve a disjunction, then we make the different
308	* disjuncts disjoint and insert an if node corresponding to each disjunct
309	* around a copy of "node". The result is then a block node containing
310	* this sequence of guarded copies of "node".
311	*/
312	static __isl_give isl_ast_node *ast_node_insert_if(
313	__isl_take isl_ast_node *node, __isl_take isl_set *guard,
314	__isl_keep isl_ast_build *build)
315	{
316	struct isl_insert_if_data data;
317	isl_ctx *ctx;
318	isl_size n;
319
320	n = isl_set_n_basic_set(set: guard);
321	if (n < 0)
322	goto error;
323	ctx = isl_ast_build_get_ctx(build);
324	if (isl_options_get_ast_build_allow_or(ctx) || n <= 1) {
325	isl_ast_node *if_node;
326	isl_ast_expr *expr;
327
328	expr = isl_ast_build_expr_from_set_internal(build, set: guard);
329
330	if_node = isl_ast_node_alloc_if(guard: expr);
331	return isl_ast_node_if_set_then(node: if_node, child: node);
332	}
333
334	guard = isl_set_make_disjoint(set: guard);
335
336	data.list = isl_ast_node_list_alloc(ctx, n: 0);
337	data.node = node;
338	data.build = build;
339	if (isl_set_foreach_basic_set(set: guard, fn: &insert_if, user: &data) < 0)
340	data.list = isl_ast_node_list_free(list: data.list);
341
342	isl_set_free(set: guard);
343	isl_ast_node_free(node: data.node);
344	return isl_ast_node_alloc_block(list: data.list);
345	error:
346	isl_set_free(set: guard);
347	isl_ast_node_free(node);
348	return NULL;
349	}
350
351	/* Insert an if node around a copy of "data->node" testing the condition
352	* encoded in guard "bset" and add the result to data->list.
353	*/
354	static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user)
355	{
356	struct isl_insert_if_data *data = user;
357	isl_ast_node *node;
358	isl_set *set;
359
360	set = isl_set_from_basic_set(bset);
361	node = isl_ast_node_copy(node: data->node);
362	node = ast_node_insert_if(node, guard: set, build: data->build);
363	data->list = isl_ast_node_list_add(list: data->list, el: node);
364
365	return isl_stat_ok;
366	}
367
368	/* Insert an if node around graft->node testing the condition encoded
369	* in guard "guard", assuming guard involves any conditions.
370	*/
371	static __isl_give isl_ast_graft *insert_if_node(
372	__isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
373	__isl_keep isl_ast_build *build)
374	{
375	int univ;
376
377	if (!graft)
378	goto error;
379
380	univ = isl_set_plain_is_universe(set: guard);
381	if (univ < 0)
382	goto error;
383	if (univ) {
384	isl_set_free(set: guard);
385	return graft;
386	}
387
388	graft->node = ast_node_insert_if(node: graft->node, guard, build);
389
390	if (!graft->node)
391	return isl_ast_graft_free(graft);
392
393	return graft;
394	error:
395	isl_set_free(set: guard);
396	return isl_ast_graft_free(graft);
397	}
398
399	/* Insert an if node around graft->node testing the condition encoded
400	* in graft->guard, assuming graft->guard involves any conditions.
401	*/
402	static __isl_give isl_ast_graft *insert_pending_guard_node(
403	__isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
404	{
405	if (!graft)
406	return NULL;
407
408	return insert_if_node(graft, guard: isl_set_copy(set: graft->guard), build);
409	}
410
411	/* Replace graft->enforced by "enforced".
412	*/
413	__isl_give isl_ast_graft *isl_ast_graft_set_enforced(
414	__isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
415	{
416	if (!graft || !enforced)
417	goto error;
418
419	isl_basic_set_free(bset: graft->enforced);
420	graft->enforced = enforced;
421
422	return graft;
423	error:
424	isl_basic_set_free(bset: enforced);
425	return isl_ast_graft_free(graft);
426	}
427
428	/* Update "enforced" such that it only involves constraints that are
429	* also enforced by "graft".
430	*/
431	static __isl_give isl_basic_set *update_enforced(
432	__isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
433	int depth)
434	{
435	isl_size dim;
436	isl_basic_set *enforced_g;
437
438	enforced_g = isl_ast_graft_get_enforced(graft);
439	dim = isl_basic_set_dim(bset: enforced_g, type: isl_dim_set);
440	if (dim < 0)
441	enforced_g = isl_basic_set_free(bset: enforced_g);
442	if (depth < dim)
443	enforced_g = isl_basic_set_eliminate(bset: enforced_g,
444	type: isl_dim_set, first: depth, n: 1);
445	enforced_g = isl_basic_set_remove_unknown_divs(bset: enforced_g);
446	enforced_g = isl_basic_set_align_params(bset: enforced_g,
447	model: isl_basic_set_get_space(bset: enforced));
448	enforced = isl_basic_set_align_params(bset: enforced,
449	model: isl_basic_set_get_space(bset: enforced_g));
450	enforced = isl_set_simple_hull(set: isl_basic_set_union(bset1: enforced,
451	bset2: enforced_g));
452
453	return enforced;
454	}
455
456	/* Extend the node at *body with node.
457	*
458	* If body points to the else branch, then *body may still be NULL.
459	* If so, we simply attach node to this else branch.
460	* Otherwise, we attach a list containing the statements already
461	* attached at *body followed by node.
462	*/
463	static void extend_body(__isl_keep isl_ast_node **body,
464	__isl_take isl_ast_node *node)
465	{
466	isl_ast_node_list *list;
467
468	if (!*body) {
469	*body = node;
470	return;
471	}
472
473	if ((*body)->type == isl_ast_node_block) {
474	list = isl_ast_node_block_get_children(node: *body);
475	isl_ast_node_free(node: *body);
476	} else
477	list = isl_ast_node_list_from_ast_node(el: *body);
478	list = isl_ast_node_list_add(list, el: node);
479	*body = isl_ast_node_alloc_block(list);
480	}
481
482	/* Merge "graft" into the last graft of "list".
483	* body points to the then or else branch of an if node in that last graft.
484	*
485	* We attach graft->node to this branch and update the enforced
486	* set of the last graft of "list" to take into account the enforced
487	* set of "graft".
488	*/
489	static __isl_give isl_ast_graft_list *graft_extend_body(
490	__isl_take isl_ast_graft_list *list,
491	__isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
492	__isl_keep isl_ast_build *build)
493	{
494	isl_size n;
495	isl_size depth;
496	isl_ast_graft *last;
497	isl_space *space;
498	isl_basic_set *enforced;
499
500	n = isl_ast_graft_list_n_ast_graft(list);
501	depth = isl_ast_build_get_depth(build);
502	if (n < 0 || depth < 0 || !graft)
503	goto error;
504	extend_body(body, node: isl_ast_node_copy(node: graft->node));
505	if (!*body)
506	goto error;
507
508	last = isl_ast_graft_list_get_ast_graft(list, index: n - 1);
509
510	space = isl_ast_build_get_space(build, internal: 1);
511	enforced = isl_basic_set_empty(space);
512	enforced = update_enforced(enforced, graft: last, depth);
513	enforced = update_enforced(enforced, graft, depth);
514	last = isl_ast_graft_set_enforced(graft: last, enforced);
515
516	list = isl_ast_graft_list_set_ast_graft(list, index: n - 1, el: last);
517	isl_ast_graft_free(graft);
518	return list;
519	error:
520	isl_ast_graft_free(graft);
521	return isl_ast_graft_list_free(list);
522	}
523
524	/* Merge "graft" into the last graft of "list", attaching graft->node
525	* to the then branch of "last_if".
526	*/
527	static __isl_give isl_ast_graft_list *extend_then(
528	__isl_take isl_ast_graft_list *list,
529	__isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
530	__isl_keep isl_ast_build *build)
531	{
532	return graft_extend_body(list, body: &last_if->u.i.then, graft, build);
533	}
534
535	/* Merge "graft" into the last graft of "list", attaching graft->node
536	* to the else branch of "last_if".
537	*/
538	static __isl_give isl_ast_graft_list *extend_else(
539	__isl_take isl_ast_graft_list *list,
540	__isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
541	__isl_keep isl_ast_build *build)
542	{
543	return graft_extend_body(list, body: &last_if->u.i.else_node, graft, build);
544	}
545
546	/* This data structure keeps track of an if node.
547	*
548	* "node" is the actual if-node
549	* "guard" is the original, non-simplified guard of the node
550	* "complement" is the complement of "guard" in the context of outer if nodes
551	*/
552	struct isl_if_node {
553	isl_ast_node *node;
554	isl_set *guard;
555	isl_set *complement;
556	};
557
558	/* Given a list of "n" if nodes, clear those starting at "first"
559	* and return "first" (i.e., the updated size of the array).
560	*/
561	static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
562	{
563	int i;
564
565	for (i = first; i < n; ++i) {
566	isl_set_free(set: if_node[i].guard);
567	isl_set_free(set: if_node[i].complement);
568	}
569
570	return first;
571	}
572
573	/* For each graft in "list",
574	* insert an if node around graft->node testing the condition encoded
575	* in graft->guard, assuming graft->guard involves any conditions.
576	*
577	* We keep track of a list of generated if nodes that can be extended
578	* without changing the order of the elements in "list".
579	* If the guard of a graft is a subset of either the guard or its complement
580	* of one of those if nodes, then the node
581	* of the new graft is inserted into the then or else branch of the last graft
582	* and the current graft is discarded.
583	* The guard of the node is then simplified based on the conditions
584	* enforced at that then or else branch.
585	* Otherwise, the current graft is appended to the list.
586	*
587	* We only construct else branches if allowed by the user.
588	*/
589	static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
590	__isl_take isl_ast_graft_list *list,
591	__isl_keep isl_ast_build *build)
592	{
593	int i, j, n_if;
594	isl_size n;
595	int allow_else;
596	isl_ctx *ctx;
597	isl_ast_graft_list *res;
598	struct isl_if_node *if_node = NULL;
599
600	n = isl_ast_graft_list_n_ast_graft(list);
601	if (!build || n < 0)
602	return isl_ast_graft_list_free(list);
603
604	ctx = isl_ast_build_get_ctx(build);
605
606	allow_else = isl_options_get_ast_build_allow_else(ctx);
607
608	n_if = 0;
609	if (n > 1) {
610	if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
611	if (!if_node)
612	return isl_ast_graft_list_free(list);
613	}
614
615	res = isl_ast_graft_list_alloc(ctx, n);
616
617	for (i = 0; i < n; ++i) {
618	isl_set *guard;
619	isl_ast_graft *graft;
620	int subset, found_then, found_else;
621	isl_ast_node *node;
622
623	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
624	if (!graft)
625	break;
626	subset = 0;
627	found_then = found_else = -1;
628	if (n_if > 0) {
629	isl_set *test;
630	test = isl_set_copy(set: graft->guard);
631	test = isl_set_intersect(set1: test,
632	set2: isl_set_copy(set: build->domain));
633	for (j = n_if - 1; j >= 0; --j) {
634	subset = isl_set_is_subset(set1: test,
635	set2: if_node[j].guard);
636	if (subset < 0 || subset) {
637	found_then = j;
638	break;
639	}
640	if (!allow_else)
641	continue;
642	subset = isl_set_is_subset(set1: test,
643	set2: if_node[j].complement);
644	if (subset < 0 || subset) {
645	found_else = j;
646	break;
647	}
648	}
649	n_if = clear_if_nodes(if_node, first: j + 1, n: n_if);
650	isl_set_free(set: test);
651	}
652	if (subset < 0) {
653	graft = isl_ast_graft_free(graft);
654	break;
655	}
656
657	guard = isl_set_copy(set: graft->guard);
658	if (found_then >= 0)
659	graft->guard = isl_set_gist(set: graft->guard,
660	context: isl_set_copy(set: if_node[found_then].guard));
661	else if (found_else >= 0)
662	graft->guard = isl_set_gist(set: graft->guard,
663	context: isl_set_copy(set: if_node[found_else].complement));
664
665	node = graft->node;
666	if (!graft->guard)
667	graft = isl_ast_graft_free(graft);
668	graft = insert_pending_guard_node(graft, build);
669	if (graft && graft->node != node && i != n - 1) {
670	isl_set *set;
671	if_node[n_if].node = graft->node;
672	if_node[n_if].guard = guard;
673	if (found_then >= 0)
674	set = if_node[found_then].guard;
675	else if (found_else >= 0)
676	set = if_node[found_else].complement;
677	else
678	set = build->domain;
679	set = isl_set_copy(set);
680	set = isl_set_subtract(set1: set, set2: isl_set_copy(set: guard));
681	if_node[n_if].complement = set;
682	n_if++;
683	} else
684	isl_set_free(set: guard);
685	if (!graft)
686	break;
687
688	if (found_then >= 0)
689	res = extend_then(list: res, last_if: if_node[found_then].node,
690	graft, build);
691	else if (found_else >= 0)
692	res = extend_else(list: res, last_if: if_node[found_else].node,
693	graft, build);
694	else
695	res = isl_ast_graft_list_add(list: res, el: graft);
696	}
697	if (i < n)
698	res = isl_ast_graft_list_free(list: res);
699
700	isl_ast_graft_list_free(list);
701	clear_if_nodes(if_node, first: 0, n: n_if);
702	free(ptr: if_node);
703	return res;
704	}
705
706	/* For each graft in "list",
707	* insert an if node around graft->node testing the condition encoded
708	* in graft->guard, assuming graft->guard involves any conditions.
709	* Subsequently remove the guards from the grafts.
710	*/
711	__isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes(
712	__isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
713	{
714	int i;
715	isl_size n;
716	isl_set *universe;
717
718	list = insert_pending_guard_nodes(list, build);
719	n = isl_ast_graft_list_n_ast_graft(list);
720	if (n < 0)
721	return isl_ast_graft_list_free(list);
722
723	universe = isl_set_universe(space: isl_ast_build_get_space(build, internal: 1));
724	for (i = 0; i < n; ++i) {
725	isl_ast_graft *graft;
726
727	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
728	if (!graft)
729	break;
730	isl_set_free(set: graft->guard);
731	graft->guard = isl_set_copy(set: universe);
732	if (!graft->guard)
733	graft = isl_ast_graft_free(graft);
734	list = isl_ast_graft_list_set_ast_graft(list, index: i, el: graft);
735	}
736	isl_set_free(set: universe);
737	if (i < n)
738	return isl_ast_graft_list_free(list);
739
740	return list;
741	}
742
743	/* Collect the nodes contained in the grafts in "list" in a node list.
744	*/
745	static __isl_give isl_ast_node_list *extract_node_list(
746	__isl_keep isl_ast_graft_list *list)
747	{
748	int i;
749	isl_size n;
750	isl_ctx *ctx;
751	isl_ast_node_list *node_list;
752
753	n = isl_ast_graft_list_n_ast_graft(list);
754	if (n < 0)
755	return NULL;
756	ctx = isl_ast_graft_list_get_ctx(list);
757	node_list = isl_ast_node_list_alloc(ctx, n);
758	for (i = 0; i < n; ++i) {
759	isl_ast_node *node;
760	isl_ast_graft *graft;
761
762	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
763	node = isl_ast_graft_get_node(graft);
764	node_list = isl_ast_node_list_add(list: node_list, el: node);
765	isl_ast_graft_free(graft);
766	}
767
768	return node_list;
769	}
770
771	/* Look for shared enforced constraints by all the elements in "list"
772	* on outer loops (with respect to the current depth) and return the result.
773	*
774	* If there are no elements in "list", then return the empty set.
775	*/
776	__isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(
777	__isl_keep isl_ast_graft_list *list,
778	__isl_keep isl_ast_build *build)
779	{
780	int i;
781	isl_size n;
782	isl_size depth;
783	isl_space *space;
784	isl_basic_set *enforced;
785
786	n = isl_ast_graft_list_n_ast_graft(list);
787	depth = isl_ast_build_get_depth(build);
788	if (n < 0 || depth < 0)
789	return NULL;
790
791	space = isl_ast_build_get_space(build, internal: 1);
792	enforced = isl_basic_set_empty(space);
793
794	for (i = 0; i < n; ++i) {
795	isl_ast_graft *graft;
796
797	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
798	enforced = update_enforced(enforced, graft, depth);
799	isl_ast_graft_free(graft);
800	}
801
802	return enforced;
803	}
804
805	/* Record "guard" in "graft" so that it will be enforced somewhere
806	* up the tree. If the graft already has a guard, then it may be partially
807	* redundant in combination with the new guard and in the context
808	* the generated constraints of "build". In fact, the new guard
809	* may in itself have some redundant constraints.
810	* We therefore (re)compute the gist of the intersection
811	* and coalesce the result.
812	*/
813	static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
814	__isl_take isl_set *guard, __isl_keep isl_ast_build *build)
815	{
816	int is_universe;
817
818	if (!graft)
819	goto error;
820
821	is_universe = isl_set_plain_is_universe(set: guard);
822	if (is_universe < 0)
823	goto error;
824	if (is_universe) {
825	isl_set_free(set: guard);
826	return graft;
827	}
828
829	graft->guard = isl_set_intersect(set1: graft->guard, set2: guard);
830	graft->guard = isl_set_gist(set: graft->guard,
831	context: isl_ast_build_get_generated(build));
832	graft->guard = isl_set_coalesce(set: graft->guard);
833	if (!graft->guard)
834	return isl_ast_graft_free(graft);
835
836	return graft;
837	error:
838	isl_set_free(set: guard);
839	return isl_ast_graft_free(graft);
840	}
841
842	/* For each graft in "list", replace its guard with the gist with
843	* respect to "context".
844	*/
845	static __isl_give isl_ast_graft_list *gist_guards(
846	__isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
847	{
848	int i;
849	isl_size n;
850
851	n = isl_ast_graft_list_n_ast_graft(list);
852	if (!list)
853	return isl_ast_graft_list_free(list);
854
855	for (i = 0; i < n; ++i) {
856	isl_ast_graft *graft;
857
858	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
859	if (!graft)
860	break;
861	graft->guard = isl_set_gist(set: graft->guard,
862	context: isl_set_copy(set: context));
863	if (!graft->guard)
864	graft = isl_ast_graft_free(graft);
865	list = isl_ast_graft_list_set_ast_graft(list, index: i, el: graft);
866	}
867	if (i < n)
868	return isl_ast_graft_list_free(list);
869
870	return list;
871	}
872
873	/* For each graft in "list", replace its guard with the gist with
874	* respect to "context".
875	*/
876	__isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(
877	__isl_take isl_ast_graft_list *list, __isl_take isl_set *context)
878	{
879	list = gist_guards(list, context);
880	isl_set_free(set: context);
881
882	return list;
883	}
884
885	/* Allocate a graft in "build" based on the list of grafts in "sub_build".
886	* "guard" and "enforced" are the guard and enforced constraints
887	* of the allocated graft. The guard is used to simplify the guards
888	* of the elements in "list".
889	*
890	* The node is initialized to either a block containing the nodes of "children"
891	* or, if there is only a single child, the node of that child.
892	* If the current level requires a for node, it should be inserted by
893	* a subsequent call to isl_ast_graft_insert_for.
894	*/
895	__isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(
896	__isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,
897	__isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,
898	__isl_keep isl_ast_build *sub_build)
899	{
900	isl_ast_build *guard_build;
901	isl_ast_node *node;
902	isl_ast_node_list *node_list;
903	isl_ast_graft *graft;
904
905	guard_build = isl_ast_build_copy(build: sub_build);
906	guard_build = isl_ast_build_replace_pending_by_guard(build: guard_build,
907	guard: isl_set_copy(set: guard));
908	list = gist_guards(list, context: guard);
909	list = insert_pending_guard_nodes(list, build: guard_build);
910	isl_ast_build_free(build: guard_build);
911
912	node_list = extract_node_list(list);
913	node = isl_ast_node_from_ast_node_list(list: node_list);
914	isl_ast_graft_list_free(list);
915
916	graft = isl_ast_graft_alloc(node, build);
917	graft = store_guard(graft, guard, build);
918	graft = isl_ast_graft_enforce(graft, enforced);
919
920	return graft;
921	}
922
923	/* Combine the grafts in the list into a single graft.
924	*
925	* The guard is initialized to the shared guard of the list elements (if any),
926	* provided it does not depend on the current dimension.
927	* The guards in the elements are then simplified with respect to the
928	* hoisted guard and materialized as if nodes around the contained AST nodes
929	* in the context of "sub_build".
930	*
931	* The enforced set is initialized to the simple hull of the enforced sets
932	* of the elements, provided the ast_build_exploit_nested_bounds option is set
933	* or the new graft will be used at the same level.
934	*
935	* The node is initialized to either a block containing the nodes of "list"
936	* or, if there is only a single element, the node of that element.
937	*/
938	static __isl_give isl_ast_graft *ast_graft_list_fuse(
939	__isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
940	{
941	isl_ast_graft *graft;
942	isl_basic_set *enforced;
943	isl_set *guard;
944
945	if (!list)
946	return NULL;
947
948	enforced = isl_ast_graft_list_extract_shared_enforced(list, build);
949	guard = isl_ast_graft_list_extract_hoistable_guard(list, build);
950	graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
951	build, sub_build: build);
952
953	return graft;
954	}
955
956	/* Combine the grafts in the list into a single graft.
957	* Return a list containing this single graft.
958	* If the original list is empty, then return an empty list.
959	*/
960	__isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
961	__isl_take isl_ast_graft_list *list,
962	__isl_keep isl_ast_build *build)
963	{
964	isl_size n;
965	isl_ast_graft *graft;
966
967	n = isl_ast_graft_list_n_ast_graft(list);
968	if (n < 0)
969	return isl_ast_graft_list_free(list);
970	if (n <= 1)
971	return list;
972	graft = ast_graft_list_fuse(list, build);
973	return isl_ast_graft_list_from_ast_graft(el: graft);
974	}
975
976	/* Combine the two grafts into a single graft.
977	* Return a list containing this single graft.
978	*/
979	static __isl_give isl_ast_graft *isl_ast_graft_fuse(
980	__isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
981	__isl_keep isl_ast_build *build)
982	{
983	isl_ctx *ctx;
984	isl_ast_graft_list *list;
985
986	ctx = isl_ast_build_get_ctx(build);
987
988	list = isl_ast_graft_list_alloc(ctx, n: 2);
989	list = isl_ast_graft_list_add(list, el: graft1);
990	list = isl_ast_graft_list_add(list, el: graft2);
991
992	return ast_graft_list_fuse(list, build);
993	}
994
995	/* Insert a for node enclosing the current graft->node.
996	*/
997	__isl_give isl_ast_graft *isl_ast_graft_insert_for(
998	__isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
999	{
1000	if (!graft)
1001	goto error;
1002
1003	graft->node = isl_ast_node_for_set_body(node, body: graft->node);
1004	if (!graft->node)
1005	return isl_ast_graft_free(graft);
1006
1007	return graft;
1008	error:
1009	isl_ast_node_free(node);
1010	isl_ast_graft_free(graft);
1011	return NULL;
1012	}
1013
1014	/* Insert a mark governing the current graft->node.
1015	*/
1016	__isl_give isl_ast_graft *isl_ast_graft_insert_mark(
1017	__isl_take isl_ast_graft *graft, __isl_take isl_id *mark)
1018	{
1019	if (!graft)
1020	goto error;
1021
1022	graft->node = isl_ast_node_alloc_mark(id: mark, node: graft->node);
1023	if (!graft->node)
1024	return isl_ast_graft_free(graft);
1025
1026	return graft;
1027	error:
1028	isl_id_free(id: mark);
1029	isl_ast_graft_free(graft);
1030	return NULL;
1031	}
1032
1033	/* Represent the graft list as an AST node.
1034	* This operation drops the information about guards in the grafts, so
1035	* if there are any pending guards, then they are materialized as if nodes.
1036	*/
1037	__isl_give isl_ast_node *isl_ast_node_from_graft_list(
1038	__isl_take isl_ast_graft_list *list,
1039	__isl_keep isl_ast_build *build)
1040	{
1041	isl_ast_node_list *node_list;
1042
1043	list = insert_pending_guard_nodes(list, build);
1044	node_list = extract_node_list(list);
1045	isl_ast_graft_list_free(list);
1046
1047	return isl_ast_node_from_ast_node_list(list: node_list);
1048	}
1049
1050	__isl_null isl_ast_graft *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
1051	{
1052	if (!graft)
1053	return NULL;
1054
1055	if (--graft->ref > 0)
1056	return NULL;
1057
1058	isl_ast_node_free(node: graft->node);
1059	isl_set_free(set: graft->guard);
1060	isl_basic_set_free(bset: graft->enforced);
1061	free(ptr: graft);
1062
1063	return NULL;
1064	}
1065
1066	/* Record that the grafted tree enforces
1067	* "enforced" by intersecting graft->enforced with "enforced".
1068	*/
1069	__isl_give isl_ast_graft *isl_ast_graft_enforce(
1070	__isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
1071	{
1072	if (!graft || !enforced)
1073	goto error;
1074
1075	enforced = isl_basic_set_align_params(bset: enforced,
1076	model: isl_basic_set_get_space(bset: graft->enforced));
1077	graft->enforced = isl_basic_set_align_params(bset: graft->enforced,
1078	model: isl_basic_set_get_space(bset: enforced));
1079	graft->enforced = isl_basic_set_intersect(bset1: graft->enforced, bset2: enforced);
1080	if (!graft->enforced)
1081	return isl_ast_graft_free(graft);
1082
1083	return graft;
1084	error:
1085	isl_basic_set_free(bset: enforced);
1086	return isl_ast_graft_free(graft);
1087	}
1088
1089	__isl_give isl_basic_set *isl_ast_graft_get_enforced(
1090	__isl_keep isl_ast_graft *graft)
1091	{
1092	return graft ? isl_basic_set_copy(bset: graft->enforced) : NULL;
1093	}
1094
1095	__isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
1096	{
1097	return graft ? isl_set_copy(set: graft->guard) : NULL;
1098	}
1099
1100	/* Record that "guard" needs to be inserted in "graft".
1101	*/
1102	__isl_give isl_ast_graft *isl_ast_graft_add_guard(
1103	__isl_take isl_ast_graft *graft,
1104	__isl_take isl_set *guard, __isl_keep isl_ast_build *build)
1105	{
1106	return store_guard(graft, guard, build);
1107	}
1108
1109	/* Reformulate the "graft", which was generated in the context
1110	* of an inner code generation, in terms of the outer code generation
1111	* AST build.
1112	*
1113	* If "product" is set, then the domain of the inner code generation build is
1114	*
1115	* [O -> S]
1116	*
1117	* with O the domain of the outer code generation build.
1118	* We essentially need to project out S.
1119	*
1120	* If "product" is not set, then we need to project the domains onto
1121	* their parameter spaces.
1122	*/
1123	__isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
1124	int product)
1125	{
1126	isl_basic_set *enforced;
1127
1128	if (!graft)
1129	return NULL;
1130
1131	if (product) {
1132	enforced = graft->enforced;
1133	enforced = isl_basic_map_domain(bmap: isl_basic_set_unwrap(bset: enforced));
1134	graft->enforced = enforced;
1135	graft->guard = isl_map_domain(bmap: isl_set_unwrap(set: graft->guard));
1136	} else {
1137	graft->enforced = isl_basic_set_params(bset: graft->enforced);
1138	graft->guard = isl_set_params(set: graft->guard);
1139	}
1140	graft->guard = isl_set_compute_divs(set: graft->guard);
1141
1142	if (!graft->enforced || !graft->guard)
1143	return isl_ast_graft_free(graft);
1144
1145	return graft;
1146	}
1147
1148	/* Reformulate the grafts in "list", which were generated in the context
1149	* of an inner code generation, in terms of the outer code generation
1150	* AST build.
1151	*/
1152	__isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1153	__isl_take isl_ast_graft_list *list, int product)
1154	{
1155	int i;
1156	isl_size n;
1157
1158	n = isl_ast_graft_list_n_ast_graft(list);
1159	if (n < 0)
1160	return isl_ast_graft_list_free(list);
1161	for (i = 0; i < n; ++i) {
1162	isl_ast_graft *graft;
1163
1164	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
1165	graft = isl_ast_graft_unembed(graft, product);
1166	list = isl_ast_graft_list_set_ast_graft(list, index: i, el: graft);
1167	}
1168
1169	return list;
1170	}
1171
1172	/* Compute the preimage of "graft" under the function represented by "ma".
1173	* In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1174	*/
1175	__isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1176	__isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1177	{
1178	isl_basic_set *enforced;
1179
1180	if (!graft)
1181	return NULL;
1182
1183	enforced = graft->enforced;
1184	graft->enforced = isl_basic_set_preimage_multi_aff(bset: enforced,
1185	ma: isl_multi_aff_copy(multi: ma));
1186	graft->guard = isl_set_preimage_multi_aff(set: graft->guard, ma);
1187
1188	if (!graft->enforced || !graft->guard)
1189	return isl_ast_graft_free(graft);
1190
1191	return graft;
1192	}
1193
1194	/* Compute the preimage of all the grafts in "list" under
1195	* the function represented by "ma".
1196	*/
1197	__isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1198	__isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1199	{
1200	int i;
1201	isl_size n;
1202
1203	n = isl_ast_graft_list_n_ast_graft(list);
1204	if (n < 0)
1205	list = isl_ast_graft_list_free(list);
1206	for (i = 0; i < n; ++i) {
1207	isl_ast_graft *graft;
1208
1209	graft = isl_ast_graft_list_get_ast_graft(list, index: i);
1210	graft = isl_ast_graft_preimage_multi_aff(graft,
1211	ma: isl_multi_aff_copy(multi: ma));
1212	list = isl_ast_graft_list_set_ast_graft(list, index: i, el: graft);
1213	}
1214
1215	isl_multi_aff_free(multi: ma);
1216	return list;
1217	}
1218
1219	/* Compare two grafts based on their guards.
1220	*/
1221	static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1222	void *user)
1223	{
1224	return isl_set_plain_cmp(set1: a->guard, set2: b->guard);
1225	}
1226
1227	/* Order the elements in "list" based on their guards.
1228	*/
1229	__isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1230	__isl_take isl_ast_graft_list *list)
1231	{
1232	return isl_ast_graft_list_sort(list, cmp: &cmp_graft, NULL);
1233	}
1234
1235	/* Merge the given two lists into a single list of grafts,
1236	* merging grafts with the same guard into a single graft.
1237	*
1238	* "list2" has been sorted using isl_ast_graft_list_sort.
1239	* "list1" may be the result of a previous call to isl_ast_graft_list_merge
1240	* and may therefore not be completely sorted.
1241	*
1242	* The elements in "list2" need to be executed after those in "list1",
1243	* but if the guard of a graft in "list2" is disjoint from the guards
1244	* of some final elements in "list1", then it can be moved up to before
1245	* those final elements.
1246	*
1247	* In particular, we look at each element g of "list2" in turn
1248	* and move it up beyond elements of "list1" that would be sorted
1249	* after g as long as each of these elements has a guard that is disjoint
1250	* from that of g.
1251	*
1252	* We do not allow the second or any later element of "list2" to be moved
1253	* before a previous elements of "list2" even if the reason that
1254	* that element didn't move up further was that its guard was not disjoint
1255	* from that of the previous element in "list1".
1256	*/
1257	__isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1258	__isl_take isl_ast_graft_list *list1,
1259	__isl_take isl_ast_graft_list *list2,
1260	__isl_keep isl_ast_build *build)
1261	{
1262	int i, j, first;
1263
1264	if (!list1 || !list2 || !build)
1265	goto error;
1266	if (list2->n == 0) {
1267	isl_ast_graft_list_free(list: list2);
1268	return list1;
1269	}
1270	if (list1->n == 0) {
1271	isl_ast_graft_list_free(list: list1);
1272	return list2;
1273	}
1274
1275	first = 0;
1276	for (i = 0; i < list2->n; ++i) {
1277	isl_ast_graft *graft;
1278	graft = isl_ast_graft_list_get_ast_graft(list: list2, index: i);
1279	if (!graft)
1280	break;
1281
1282	for (j = list1->n; j >= 0; --j) {
1283	int cmp, disjoint;
1284	isl_ast_graft *graft_j;
1285
1286	if (j == first)
1287	cmp = -1;
1288	else
1289	cmp = isl_set_plain_cmp(set1: list1->p[j - 1]->guard,
1290	set2: graft->guard);
1291	if (cmp > 0) {
1292	disjoint = isl_set_is_disjoint(set1: graft->guard,
1293	set2: list1->p[j - 1]->guard);
1294	if (disjoint < 0) {
1295	isl_ast_graft_free(graft);
1296	list1 = isl_ast_graft_list_free(list: list1);
1297	break;
1298	}
1299	if (!disjoint)
1300	cmp = -1;
1301	}
1302	if (cmp > 0)
1303	continue;
1304	if (cmp < 0) {
1305	list1 = isl_ast_graft_list_insert(list: list1, pos: j,
1306	el: graft);
1307	break;
1308	}
1309
1310	--j;
1311
1312	graft_j = isl_ast_graft_list_get_ast_graft(list: list1, index: j);
1313	graft_j = isl_ast_graft_fuse(graft1: graft_j, graft2: graft, build);
1314	list1 = isl_ast_graft_list_set_ast_graft(list: list1, index: j,
1315	el: graft_j);
1316	break;
1317	}
1318
1319	if (j < 0) {
1320	isl_ast_graft_free(graft);
1321	isl_die(isl_ast_build_get_ctx(build),
1322	isl_error_internal,
1323	"element failed to get inserted", break);
1324	}
1325
1326	first = j + 1;
1327	if (!list1)
1328	break;
1329	}
1330	if (i < list2->n)
1331	list1 = isl_ast_graft_list_free(list: list1);
1332	isl_ast_graft_list_free(list: list2);
1333
1334	return list1;
1335	error:
1336	isl_ast_graft_list_free(list: list1);
1337	isl_ast_graft_list_free(list: list2);
1338	return NULL;
1339	}
1340
1341	/* Internal data structure for split_on_guard.
1342	*
1343	* "guard2list" is the constructed associative array.
1344	* "any_match" gets set if any guard was seen more than once.
1345	*/
1346	struct isl_split_on_guard_data {
1347	isl_set_to_ast_graft_list *guard2list;
1348	int *any_match;
1349	};
1350
1351	/* Add "graft" to the list associated to its guard in data->guard2list.
1352	* If some other graft was already associated to this guard,
1353	* then set data->any_match.
1354	*/
1355	static isl_stat add_to_guard_list(__isl_take isl_ast_graft *graft, void *user)
1356	{
1357	struct isl_split_on_guard_data *data = user;
1358	isl_set *guard;
1359	isl_maybe_isl_ast_graft_list m;
1360
1361	if (!graft)
1362	return isl_stat_error;
1363	m = isl_set_to_ast_graft_list_try_get(hmap: data->guard2list, key: graft->guard);
1364	if (m.valid < 0)
1365	return isl_stat_non_null(obj: isl_ast_graft_free(graft));
1366
1367	if (m.valid) {
1368	*data->any_match = 1;
1369	m.value = isl_ast_graft_list_add(list: m.value, el: graft);
1370	} else {
1371	m.value = isl_ast_graft_list_from_ast_graft(el: graft);
1372	}
1373	guard = isl_set_copy(set: graft->guard);
1374	data->guard2list =
1375	isl_set_to_ast_graft_list_set(hmap: data->guard2list, key: guard, val: m.value);
1376
1377	return isl_stat_non_null(obj: data->guard2list);
1378	}
1379
1380	/* Construct an associative array that groups the elements
1381	* of "list" based on their guards.
1382	* If any guard appears more than once, then set "any_match".
1383	*/
1384	static __isl_give isl_set_to_ast_graft_list *split_on_guard(
1385	__isl_keep isl_ast_graft_list *list, int *any_match)
1386	{
1387	struct isl_split_on_guard_data data = { NULL, any_match };
1388	isl_size n;
1389	isl_ctx *ctx;
1390
1391	n = isl_ast_graft_list_size(list);
1392	if (n < 0)
1393	return NULL;
1394
1395	ctx = isl_ast_graft_list_get_ctx(list);
1396	data.guard2list = isl_set_to_ast_graft_list_alloc(ctx, min_size: n);
1397
1398	if (isl_ast_graft_list_foreach(list, fn: &add_to_guard_list, user: &data) < 0)
1399	return isl_set_to_ast_graft_list_free(hmap: data.guard2list);
1400
1401	return data.guard2list;
1402	}
1403
1404	/* Add the elements of "guard_list" to "list".
1405	*/
1406	static isl_stat add_same_guard(__isl_take isl_set *guard,
1407	__isl_take isl_ast_graft_list *guard_list, void *user)
1408	{
1409	isl_ast_graft_list **list = user;
1410
1411	isl_set_free(set: guard);
1412	*list = isl_ast_graft_list_concat(list1: *list, list2: guard_list);
1413
1414	return isl_stat_non_null(obj: *list);
1415	}
1416
1417	/* Given an associative array "guard2list" containing the elements
1418	* of "list" grouped on common guards, reconstruct "list"
1419	* by placing elements with the same guard consecutively.
1420	*/
1421	static __isl_give isl_ast_graft_list *reconstruct(
1422	__isl_take isl_ast_graft_list *list,
1423	__isl_keep isl_set_to_ast_graft_list *guard2list,
1424	__isl_keep isl_ast_build *build)
1425	{
1426	list = isl_ast_graft_list_clear(list);
1427	if (isl_set_to_ast_graft_list_foreach(hmap: guard2list,
1428	fn: &add_same_guard, user: &list) < 0)
1429	list = isl_ast_graft_list_free(list);
1430
1431	return list;
1432	}
1433
1434	/* Group the grafts in "list" based on identical guards.
1435	*
1436	* Note that there need to be a least three elements in the list
1437	* for the elements not to be grouped already.
1438	*
1439	* Group the elements in an associative array based on their guards.
1440	* If any guard was seen more than once, then reconstruct the list
1441	* from the associative array. Otherwise, simply return the original list.
1442	*/
1443	__isl_give isl_ast_graft_list *isl_ast_graft_list_group_on_guard(
1444	__isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
1445	{
1446	int any_match = 0;
1447	isl_size n;
1448	isl_set_to_ast_graft_list *guard2list;
1449
1450	n = isl_ast_graft_list_size(list);
1451	if (n < 0)
1452	return isl_ast_graft_list_free(list);
1453	if (n <= 2)
1454	return list;
1455
1456	guard2list = split_on_guard(list, any_match: &any_match);
1457	if (any_match)
1458	list = reconstruct(list, guard2list, build);
1459
1460	isl_set_to_ast_graft_list_free(hmap: guard2list);
1461
1462	return list;
1463	}
1464
1465	/* An enumeration of the keys that appear in the textual representation
1466	* of an isl_sat_graft object.
1467	*/
1468	enum isl_graft_key {
1469	isl_graft_key_error = -1,
1470	isl_graft_key_guard,
1471	isl_graft_key_enforced,
1472	isl_graft_key_node,
1473	isl_graft_key_end
1474	};
1475
1476	/* Textual representations of the keys for an isl_sat_graft object.
1477	*/
1478	static char *key_str[] = {
1479	[isl_graft_key_guard] = "guard",
1480	[isl_graft_key_enforced] = "enforced",
1481	[isl_graft_key_node] = "node",
1482	};
1483
1484	__isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1485	__isl_keep isl_ast_graft *graft)
1486	{
1487	if (!p)
1488	return NULL;
1489	if (!graft)
1490	return isl_printer_free(printer: p);
1491
1492	p = isl_printer_print_str(p, s: "(");
1493	p = isl_printer_print_str(p, s: key_str[isl_graft_key_guard]);
1494	p = isl_printer_print_str(p, s: ": ");
1495	p = isl_printer_print_set(printer: p, map: graft->guard);
1496	p = isl_printer_print_str(p, s: ", ");
1497	p = isl_printer_print_str(p, s: key_str[isl_graft_key_enforced]);
1498	p = isl_printer_print_str(p, s: ": ");
1499	p = isl_printer_print_basic_set(printer: p, bset: graft->enforced);
1500	p = isl_printer_print_str(p, s: ", ");
1501	p = isl_printer_print_str(p, s: key_str[isl_graft_key_node]);
1502	p = isl_printer_print_str(p, s: ": ");
1503	p = isl_printer_print_ast_node(p, node: graft->node);
1504	p = isl_printer_print_str(p, s: ")");
1505
1506	return p;
1507	}
1508
1509	#undef KEY
1510	#define KEY enum isl_graft_key
1511	#undef KEY_ERROR
1512	#define KEY_ERROR isl_graft_key_error
1513	#undef KEY_END
1514	#define KEY_END isl_graft_key_end
1515	#undef KEY_STR
1516	#define KEY_STR key_str
1517	#undef KEY_EXTRACT
1518	#define KEY_EXTRACT extract_key
1519	#undef KEY_GET
1520	#define KEY_GET get_key
1521	#include "extract_key.c"
1522
1523	/* Read the key "key" from "s", along with the subsequent colon.
1524	*/
1525	static isl_stat read_key(__isl_keep isl_stream *s, enum isl_graft_key key)
1526	{
1527	enum isl_graft_key extracted;
1528
1529	extracted = get_key(s);
1530	if (extracted < 0)
1531	return isl_stat_error;
1532	if (extracted != key)
1533	isl_die(isl_stream_get_ctx(s), isl_error_invalid,
1534	"expecting different field", return isl_stat_error);
1535	if (isl_stream_eat(s, type: ':') < 0)
1536	return isl_stat_error;
1537	return isl_stat_ok;
1538	}
1539
1540	/* Read an isl_ast_graft object from "s".
1541	*
1542	* Read the pieces in the way they are printed in isl_printer_print_ast_graft.
1543	*/
1544	static __isl_give isl_ast_graft *isl_stream_read_ast_graft(
1545	__isl_keep isl_stream *s)
1546	{
1547	isl_set *guard;
1548	isl_basic_set *enforced = NULL;
1549	isl_ast_node *node = NULL;
1550
1551	if (isl_stream_eat(s, type: '(') < 0)
1552	return NULL;
1553	if (read_key(s, key: isl_graft_key_guard) < 0)
1554	return NULL;
1555	guard = isl_stream_read_set(s);
1556	if (!guard)
1557	goto error;
1558	if (isl_stream_eat(s, type: ',') < 0)
1559	goto error;
1560	if (read_key(s, key: isl_graft_key_enforced) < 0)
1561	goto error;
1562	enforced = isl_stream_read_basic_set(s);
1563	if (!enforced)
1564	goto error;
1565	if (isl_stream_eat(s, type: ',') < 0)
1566	goto error;
1567	if (read_key(s, key: isl_graft_key_node) < 0)
1568	goto error;
1569	node = isl_stream_read_ast_node(s);
1570	if (!node)
1571	goto error;
1572	if (isl_stream_eat(s, type: ')') < 0)
1573	goto error;
1574	return graft_alloc(node, guard, enforced);
1575	error:
1576	isl_set_free(set: guard);
1577	isl_basic_set_free(bset: enforced);
1578	isl_ast_node_free(node);
1579	return NULL;
1580	}
1581