1	/*
2	* Copyright 2012-2013 Ecole Normale Superieure
3	* Copyright 2014 INRIA Rocquencourt
4	*
5	* Use of this software is governed by the MIT license
6	*
7	* Written by Sven Verdoolaege,
8	* Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9	* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10	* B.P. 105 - 78153 Le Chesnay, France
11	*/
12
13	#include <isl/id.h>
14	#include <isl/val.h>
15	#include <isl/space.h>
16	#include <isl/map.h>
17	#include <isl/aff.h>
18	#include <isl/constraint.h>
19	#include <isl/map.h>
20	#include <isl/union_set.h>
21	#include <isl/union_map.h>
22	#include <isl_ast_build_private.h>
23	#include <isl_ast_private.h>
24	#include <isl_config.h>
25
26	/* Construct a map that isolates the current dimension.
27	*
28	* Essentially, the current dimension of "set" is moved to the single output
29	* dimension in the result, with the current dimension in the domain replaced
30	* by an unconstrained variable.
31	*/
32	__isl_give isl_map *isl_ast_build_map_to_iterator(
33	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
34	{
35	isl_map *map;
36
37	map = isl_map_from_domain(set);
38	map = isl_map_add_dims(map, type: isl_dim_out, n: 1);
39
40	if (!build)
41	return isl_map_free(map);
42
43	map = isl_map_equate(map, type1: isl_dim_in, pos1: build->depth, type2: isl_dim_out, pos2: 0);
44	map = isl_map_eliminate(map, type: isl_dim_in, first: build->depth, n: 1);
45
46	return map;
47	}
48
49	/* Initialize the information derived during the AST generation to default
50	* values for a schedule domain in "space".
51	*
52	* We also check that the remaining fields are not NULL so that
53	* the calling functions don't have to perform this test.
54	*/
55	static __isl_give isl_ast_build *isl_ast_build_init_derived(
56	__isl_take isl_ast_build *build, __isl_take isl_space *space)
57	{
58	isl_ctx *ctx;
59	isl_vec *strides;
60	isl_size dim;
61
62	build = isl_ast_build_cow(build);
63	if (!build || !build->domain)
64	goto error;
65
66	ctx = isl_ast_build_get_ctx(build);
67	dim = isl_space_dim(space, type: isl_dim_set);
68	if (dim < 0)
69	goto error;
70	strides = isl_vec_alloc(ctx, size: dim);
71	strides = isl_vec_set_si(vec: strides, v: 1);
72
73	isl_vec_free(vec: build->strides);
74	build->strides = strides;
75
76	space = isl_space_map_from_set(space);
77	isl_multi_aff_free(multi: build->offsets);
78	build->offsets = isl_multi_aff_zero(space: isl_space_copy(space));
79	isl_multi_aff_free(multi: build->values);
80	build->values = isl_multi_aff_identity(space: isl_space_copy(space));
81	isl_multi_aff_free(multi: build->internal2input);
82	build->internal2input = isl_multi_aff_identity(space);
83
84	if (!build->iterators || !build->domain || !build->generated ||
85	!build->pending || !build->values || !build->internal2input ||
86	!build->strides || !build->offsets || !build->options)
87	return isl_ast_build_free(build);
88
89	return build;
90	error:
91	isl_space_free(space);
92	return isl_ast_build_free(build);
93	}
94
95	/* Return an isl_id called "c%d", with "%d" set to "i".
96	* If an isl_id with such a name already appears among the parameters
97	* in build->domain, then adjust the name to "c%d_%d".
98	*/
99	static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
100	__isl_keep isl_ast_build *build)
101	{
102	int j;
103	char name[23];
104	isl_set *dom = build->domain;
105
106	snprintf(s: name, maxlen: sizeof(name), format: "c%d", i);
107	j = 0;
108	while (isl_set_find_dim_by_name(set: dom, type: isl_dim_param, name) >= 0)
109	snprintf(s: name, maxlen: sizeof(name), format: "c%d_%d", i, j++);
110	return isl_id_alloc(ctx, name, NULL);
111	}
112
113	/* Create an isl_ast_build with "set" as domain.
114	*
115	* The input set is usually a parameter domain, but we currently allow it to
116	* be any kind of set. We set the domain of the returned isl_ast_build
117	* to "set" and initialize all the other fields to default values.
118	*/
119	__isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
120	{
121	int i;
122	isl_size n;
123	isl_ctx *ctx;
124	isl_space *space;
125	isl_ast_build *build;
126
127	set = isl_set_compute_divs(set);
128	n = isl_set_dim(set, type: isl_dim_set);
129	if (n < 0)
130	goto error;
131
132	ctx = isl_set_get_ctx(set);
133
134	build = isl_calloc_type(ctx, isl_ast_build);
135	if (!build)
136	goto error;
137
138	build->ref = 1;
139	build->domain = set;
140	build->generated = isl_set_copy(set: build->domain);
141	build->pending = isl_set_universe(space: isl_set_get_space(set: build->domain));
142	build->options = isl_union_map_empty(space: isl_space_params_alloc(ctx, nparam: 0));
143	build->depth = n;
144	build->iterators = isl_id_list_alloc(ctx, n);
145	for (i = 0; i < n; ++i) {
146	isl_id *id;
147	if (isl_set_has_dim_id(set, type: isl_dim_set, pos: i))
148	id = isl_set_get_dim_id(set, type: isl_dim_set, pos: i);
149	else
150	id = generate_name(ctx, i, build);
151	build->iterators = isl_id_list_add(list: build->iterators, el: id);
152	}
153	space = isl_set_get_space(set);
154	if (isl_space_is_params(space))
155	space = isl_space_set_from_params(space);
156
157	return isl_ast_build_init_derived(build, space);
158	error:
159	isl_set_free(set);
160	return NULL;
161	}
162
163	/* Create an isl_ast_build with a universe (parametric) context.
164	*/
165	__isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
166	{
167	isl_space *space;
168	isl_set *context;
169
170	space = isl_space_params_alloc(ctx, nparam: 0);
171	context = isl_set_universe(space);
172
173	return isl_ast_build_from_context(set: context);
174	}
175
176	__isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
177	{
178	if (!build)
179	return NULL;
180
181	build->ref++;
182	return build;
183	}
184
185	__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
186	{
187	isl_ctx *ctx;
188	isl_ast_build *dup;
189
190	if (!build)
191	return NULL;
192
193	ctx = isl_ast_build_get_ctx(build);
194	dup = isl_calloc_type(ctx, isl_ast_build);
195	if (!dup)
196	return NULL;
197
198	dup->ref = 1;
199	dup->outer_pos = build->outer_pos;
200	dup->depth = build->depth;
201	dup->iterators = isl_id_list_copy(list: build->iterators);
202	dup->domain = isl_set_copy(set: build->domain);
203	dup->generated = isl_set_copy(set: build->generated);
204	dup->pending = isl_set_copy(set: build->pending);
205	dup->values = isl_multi_aff_copy(multi: build->values);
206	dup->internal2input = isl_multi_aff_copy(multi: build->internal2input);
207	dup->value = isl_pw_aff_copy(pwaff: build->value);
208	dup->strides = isl_vec_copy(vec: build->strides);
209	dup->offsets = isl_multi_aff_copy(multi: build->offsets);
210	dup->executed = isl_union_map_copy(umap: build->executed);
211	dup->single_valued = build->single_valued;
212	dup->options = isl_union_map_copy(umap: build->options);
213	dup->at_each_domain = build->at_each_domain;
214	dup->at_each_domain_user = build->at_each_domain_user;
215	dup->before_each_for = build->before_each_for;
216	dup->before_each_for_user = build->before_each_for_user;
217	dup->after_each_for = build->after_each_for;
218	dup->after_each_for_user = build->after_each_for_user;
219	dup->before_each_mark = build->before_each_mark;
220	dup->before_each_mark_user = build->before_each_mark_user;
221	dup->after_each_mark = build->after_each_mark;
222	dup->after_each_mark_user = build->after_each_mark_user;
223	dup->create_leaf = build->create_leaf;
224	dup->create_leaf_user = build->create_leaf_user;
225	dup->node = isl_schedule_node_copy(node: build->node);
226	if (build->loop_type) {
227	int i;
228
229	dup->n = build->n;
230	dup->loop_type = isl_alloc_array(ctx,
231	enum isl_ast_loop_type, dup->n);
232	if (dup->n && !dup->loop_type)
233	return isl_ast_build_free(build: dup);
234	for (i = 0; i < dup->n; ++i)
235	dup->loop_type[i] = build->loop_type[i];
236	}
237
238	if (!dup->iterators || !dup->domain || !dup->generated ||
239	!dup->pending || !dup->values ||
240	!dup->strides || !dup->offsets || !dup->options ||
241	(build->internal2input && !dup->internal2input) ||
242	(build->executed && !dup->executed) ||
243	(build->value && !dup->value) ||
244	(build->node && !dup->node))
245	return isl_ast_build_free(build: dup);
246
247	return dup;
248	}
249
250	/* Align the parameters of "build" to those of "model", introducing
251	* additional parameters if needed.
252	*/
253	__isl_give isl_ast_build *isl_ast_build_align_params(
254	__isl_take isl_ast_build *build, __isl_take isl_space *model)
255	{
256	build = isl_ast_build_cow(build);
257	if (!build)
258	goto error;
259
260	build->domain = isl_set_align_params(set: build->domain,
261	model: isl_space_copy(space: model));
262	build->generated = isl_set_align_params(set: build->generated,
263	model: isl_space_copy(space: model));
264	build->pending = isl_set_align_params(set: build->pending,
265	model: isl_space_copy(space: model));
266	build->values = isl_multi_aff_align_params(multi: build->values,
267	model: isl_space_copy(space: model));
268	build->offsets = isl_multi_aff_align_params(multi: build->offsets,
269	model: isl_space_copy(space: model));
270	build->options = isl_union_map_align_params(umap: build->options,
271	model: isl_space_copy(space: model));
272	if (build->internal2input) {
273	build->internal2input =
274	isl_multi_aff_align_params(multi: build->internal2input,
275	model);
276	if (!build->internal2input)
277	return isl_ast_build_free(build);
278	} else {
279	isl_space_free(space: model);
280	}
281
282	if (!build->domain || !build->values || !build->offsets ||
283	!build->options)
284	return isl_ast_build_free(build);
285
286	return build;
287	error:
288	isl_space_free(space: model);
289	return NULL;
290	}
291
292	__isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
293	{
294	if (!build)
295	return NULL;
296
297	if (build->ref == 1)
298	return build;
299	build->ref--;
300	return isl_ast_build_dup(build);
301	}
302
303	__isl_null isl_ast_build *isl_ast_build_free(
304	__isl_take isl_ast_build *build)
305	{
306	if (!build)
307	return NULL;
308
309	if (--build->ref > 0)
310	return NULL;
311
312	isl_id_list_free(list: build->iterators);
313	isl_set_free(set: build->domain);
314	isl_set_free(set: build->generated);
315	isl_set_free(set: build->pending);
316	isl_multi_aff_free(multi: build->values);
317	isl_multi_aff_free(multi: build->internal2input);
318	isl_pw_aff_free(pwaff: build->value);
319	isl_vec_free(vec: build->strides);
320	isl_multi_aff_free(multi: build->offsets);
321	isl_multi_aff_free(multi: build->schedule_map);
322	isl_union_map_free(umap: build->executed);
323	isl_union_map_free(umap: build->options);
324	isl_schedule_node_free(node: build->node);
325	free(ptr: build->loop_type);
326	isl_set_free(set: build->isolated);
327
328	free(ptr: build);
329
330	return NULL;
331	}
332
333	isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
334	{
335	return build ? isl_set_get_ctx(set: build->domain) : NULL;
336	}
337
338	/* Replace build->options by "options".
339	*/
340	__isl_give isl_ast_build *isl_ast_build_set_options(
341	__isl_take isl_ast_build *build, __isl_take isl_union_map *options)
342	{
343	build = isl_ast_build_cow(build);
344
345	if (!build || !options)
346	goto error;
347
348	isl_union_map_free(umap: build->options);
349	build->options = options;
350
351	return build;
352	error:
353	isl_union_map_free(umap: options);
354	return isl_ast_build_free(build);
355	}
356
357	/* Set the iterators for the next code generation.
358	*
359	* If we still have some iterators left from the previous code generation
360	* (if any) or if iterators have already been set by a previous
361	* call to this function, then we remove them first.
362	*/
363	__isl_give isl_ast_build *isl_ast_build_set_iterators(
364	__isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
365	{
366	isl_size dim, n_it;
367
368	build = isl_ast_build_cow(build);
369	if (!build)
370	goto error;
371
372	dim = isl_ast_build_dim(build, type: isl_dim_set);
373	n_it = isl_id_list_n_id(list: build->iterators);
374	if (dim < 0 || n_it < 0)
375	goto error;
376	if (n_it < dim)
377	isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
378	"isl_ast_build in inconsistent state", goto error);
379	if (n_it > dim)
380	build->iterators = isl_id_list_drop(list: build->iterators,
381	first: dim, n: n_it - dim);
382	build->iterators = isl_id_list_concat(list1: build->iterators, list2: iterators);
383	if (!build->iterators)
384	return isl_ast_build_free(build);
385
386	return build;
387	error:
388	isl_id_list_free(list: iterators);
389	return isl_ast_build_free(build);
390	}
391
392	/* Set the "at_each_domain" callback of "build" to "fn".
393	*/
394	__isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
395	__isl_take isl_ast_build *build,
396	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
397	__isl_keep isl_ast_build *build, void *user), void *user)
398	{
399	build = isl_ast_build_cow(build);
400
401	if (!build)
402	return NULL;
403
404	build->at_each_domain = fn;
405	build->at_each_domain_user = user;
406
407	return build;
408	}
409
410	/* Set the "before_each_for" callback of "build" to "fn".
411	*/
412	__isl_give isl_ast_build *isl_ast_build_set_before_each_for(
413	__isl_take isl_ast_build *build,
414	__isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
415	void *user), void *user)
416	{
417	build = isl_ast_build_cow(build);
418
419	if (!build)
420	return NULL;
421
422	build->before_each_for = fn;
423	build->before_each_for_user = user;
424
425	return build;
426	}
427
428	/* Set the "after_each_for" callback of "build" to "fn".
429	*/
430	__isl_give isl_ast_build *isl_ast_build_set_after_each_for(
431	__isl_take isl_ast_build *build,
432	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
433	__isl_keep isl_ast_build *build, void *user), void *user)
434	{
435	build = isl_ast_build_cow(build);
436
437	if (!build)
438	return NULL;
439
440	build->after_each_for = fn;
441	build->after_each_for_user = user;
442
443	return build;
444	}
445
446	/* Set the "before_each_mark" callback of "build" to "fn".
447	*/
448	__isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
449	__isl_take isl_ast_build *build,
450	isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
451	void *user), void *user)
452	{
453	build = isl_ast_build_cow(build);
454
455	if (!build)
456	return NULL;
457
458	build->before_each_mark = fn;
459	build->before_each_mark_user = user;
460
461	return build;
462	}
463
464	/* Set the "after_each_mark" callback of "build" to "fn".
465	*/
466	__isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
467	__isl_take isl_ast_build *build,
468	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
469	__isl_keep isl_ast_build *build, void *user), void *user)
470	{
471	build = isl_ast_build_cow(build);
472
473	if (!build)
474	return NULL;
475
476	build->after_each_mark = fn;
477	build->after_each_mark_user = user;
478
479	return build;
480	}
481
482	/* Set the "create_leaf" callback of "build" to "fn".
483	*/
484	__isl_give isl_ast_build *isl_ast_build_set_create_leaf(
485	__isl_take isl_ast_build *build,
486	__isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
487	void *user), void *user)
488	{
489	build = isl_ast_build_cow(build);
490
491	if (!build)
492	return NULL;
493
494	build->create_leaf = fn;
495	build->create_leaf_user = user;
496
497	return build;
498	}
499
500	/* Clear all information that is specific to this code generation
501	* and that is (probably) not meaningful to any nested code generation.
502	*/
503	__isl_give isl_ast_build *isl_ast_build_clear_local_info(
504	__isl_take isl_ast_build *build)
505	{
506	isl_space *space;
507
508	build = isl_ast_build_cow(build);
509	if (!build)
510	return NULL;
511
512	space = isl_union_map_get_space(umap: build->options);
513	isl_union_map_free(umap: build->options);
514	build->options = isl_union_map_empty(space);
515
516	build->at_each_domain = NULL;
517	build->at_each_domain_user = NULL;
518	build->before_each_for = NULL;
519	build->before_each_for_user = NULL;
520	build->after_each_for = NULL;
521	build->after_each_for_user = NULL;
522	build->before_each_mark = NULL;
523	build->before_each_mark_user = NULL;
524	build->after_each_mark = NULL;
525	build->after_each_mark_user = NULL;
526	build->create_leaf = NULL;
527	build->create_leaf_user = NULL;
528
529	if (!build->options)
530	return isl_ast_build_free(build);
531
532	return build;
533	}
534
535	/* Have any loops been eliminated?
536	* That is, do any of the original schedule dimensions have a fixed
537	* value that has been substituted?
538	*/
539	static int any_eliminated(isl_ast_build *build)
540	{
541	int i;
542
543	for (i = 0; i < build->depth; ++i)
544	if (isl_ast_build_has_affine_value(build, pos: i))
545	return 1;
546
547	return 0;
548	}
549
550	/* Clear build->schedule_map.
551	* This function should be called whenever anything that might affect
552	* the result of isl_ast_build_get_schedule_map_multi_aff changes.
553	* In particular, it should be called when the depth is changed or
554	* when an iterator is determined to have a fixed value.
555	*/
556	static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
557	{
558	if (!build)
559	return;
560	isl_multi_aff_free(multi: build->schedule_map);
561	build->schedule_map = NULL;
562	}
563
564	/* Do we need a (non-trivial) schedule map?
565	* That is, is the internal schedule space different from
566	* the external schedule space?
567	*
568	* The internal and external schedule spaces are only the same
569	* if code has been generated for the entire schedule and if none
570	* of the loops have been eliminated.
571	*/
572	isl_bool isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
573	{
574	isl_size dim;
575
576	dim = isl_ast_build_dim(build, type: isl_dim_set);
577	if (dim < 0)
578	return isl_bool_error;
579	return isl_bool_ok(b: build->depth != dim || any_eliminated(build));
580	}
581
582	/* Return a mapping from the internal schedule space to the external
583	* schedule space in the form of an isl_multi_aff.
584	* The internal schedule space originally corresponds to that of the
585	* input schedule. This may change during the code generation if
586	* if isl_ast_build_insert_dim is ever called.
587	* The external schedule space corresponds to the
588	* loops that have been generated.
589	*
590	* Currently, the only difference between the internal schedule domain
591	* and the external schedule domain is that some dimensions are projected
592	* out in the external schedule domain. In particular, the dimensions
593	* for which no code has been generated yet and the dimensions that correspond
594	* to eliminated loops.
595	*
596	* We cache a copy of the schedule_map in build->schedule_map.
597	* The cache is cleared through isl_ast_build_reset_schedule_map
598	* whenever anything changes that might affect the result of this function.
599	*/
600	__isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
601	__isl_keep isl_ast_build *build)
602	{
603	isl_bool needs_map;
604	isl_space *space;
605	isl_multi_aff *ma;
606
607	if (!build)
608	return NULL;
609	if (build->schedule_map)
610	return isl_multi_aff_copy(multi: build->schedule_map);
611	needs_map = isl_ast_build_need_schedule_map(build);
612	if (needs_map < 0)
613	return NULL;
614
615	space = isl_ast_build_get_space(build, internal: 1);
616	space = isl_space_map_from_set(space);
617	ma = isl_multi_aff_identity(space);
618	if (needs_map) {
619	int i;
620	isl_size dim = isl_ast_build_dim(build, type: isl_dim_set);
621
622	if (dim < 0)
623	ma = isl_multi_aff_free(multi: ma);
624	ma = isl_multi_aff_drop_dims(multi: ma, type: isl_dim_out,
625	first: build->depth, n: dim - build->depth);
626	for (i = build->depth - 1; i >= 0; --i)
627	if (isl_ast_build_has_affine_value(build, pos: i))
628	ma = isl_multi_aff_drop_dims(multi: ma,
629	type: isl_dim_out, first: i, n: 1);
630	}
631
632	build->schedule_map = ma;
633	return isl_multi_aff_copy(multi: build->schedule_map);
634	}
635
636	/* Return a mapping from the internal schedule space to the external
637	* schedule space in the form of an isl_map.
638	*/
639	__isl_give isl_map *isl_ast_build_get_schedule_map(
640	__isl_keep isl_ast_build *build)
641	{
642	isl_multi_aff *ma;
643
644	ma = isl_ast_build_get_schedule_map_multi_aff(build);
645	return isl_map_from_multi_aff(maff: ma);
646	}
647
648	/* Return the position of the dimension in build->domain for which
649	* an AST node is currently being generated.
650	*/
651	isl_size isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
652	{
653	return build ? build->depth : isl_size_error;
654	}
655
656	/* Prepare for generating code for the next level.
657	* In particular, increase the depth and reset any information
658	* that is local to the current depth.
659	*/
660	__isl_give isl_ast_build *isl_ast_build_increase_depth(
661	__isl_take isl_ast_build *build)
662	{
663	build = isl_ast_build_cow(build);
664	if (!build)
665	return NULL;
666	build->depth++;
667	isl_ast_build_reset_schedule_map(build);
668	build->value = isl_pw_aff_free(pwaff: build->value);
669	return build;
670	}
671
672	void isl_ast_build_dump(__isl_keep isl_ast_build *build)
673	{
674	if (!build)
675	return;
676
677	fprintf(stderr, format: "domain: ");
678	isl_set_dump(set: build->domain);
679	fprintf(stderr, format: "generated: ");
680	isl_set_dump(set: build->generated);
681	fprintf(stderr, format: "pending: ");
682	isl_set_dump(set: build->pending);
683	fprintf(stderr, format: "iterators: ");
684	isl_id_list_dump(list: build->iterators);
685	fprintf(stderr, format: "values: ");
686	isl_multi_aff_dump(maff: build->values);
687	if (build->value) {
688	fprintf(stderr, format: "value: ");
689	isl_pw_aff_dump(pwaff: build->value);
690	}
691	fprintf(stderr, format: "strides: ");
692	isl_vec_dump(vec: build->strides);
693	fprintf(stderr, format: "offsets: ");
694	isl_multi_aff_dump(maff: build->offsets);
695	fprintf(stderr, format: "internal2input: ");
696	isl_multi_aff_dump(maff: build->internal2input);
697	}
698
699	/* Initialize "build" for AST construction in schedule space "space"
700	* in the case that build->domain is a parameter set.
701	*
702	* build->iterators is assumed to have been updated already.
703	*/
704	static __isl_give isl_ast_build *isl_ast_build_init(
705	__isl_take isl_ast_build *build, __isl_take isl_space *space)
706	{
707	isl_set *set;
708
709	build = isl_ast_build_cow(build);
710	if (!build)
711	goto error;
712
713	set = isl_set_universe(space: isl_space_copy(space));
714	build->domain = isl_set_intersect_params(set: isl_set_copy(set),
715	params: build->domain);
716	build->pending = isl_set_intersect_params(set: isl_set_copy(set),
717	params: build->pending);
718	build->generated = isl_set_intersect_params(set, params: build->generated);
719
720	return isl_ast_build_init_derived(build, space);
721	error:
722	isl_ast_build_free(build);
723	isl_space_free(space);
724	return NULL;
725	}
726
727	/* Assign "aff" to *user and return -1, effectively extracting
728	* the first (and presumably only) affine expression in the isl_pw_aff
729	* on which this function is used.
730	*/
731	static isl_stat extract_single_piece(__isl_take isl_set *set,
732	__isl_take isl_aff *aff, void *user)
733	{
734	isl_aff **p = user;
735
736	*p = aff;
737	isl_set_free(set);
738
739	return isl_stat_error;
740	}
741
742	/* Intersect "set" with the stride constraint of "build", if any.
743	*/
744	static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
745	__isl_keep isl_ast_build *build)
746	{
747	isl_set *stride;
748
749	if (!build)
750	return isl_set_free(set);
751	if (!isl_ast_build_has_stride(build, pos: build->depth))
752	return set;
753
754	stride = isl_ast_build_get_stride_constraint(build);
755	return isl_set_intersect(set1: set, set2: stride);
756	}
757
758	/* Check if the given bounds on the current dimension (together with
759	* the stride constraint, if any) imply that
760	* this current dimension attains only a single value (in terms of
761	* parameters and outer dimensions).
762	* If so, we record it in build->value.
763	* If, moreover, this value can be represented as a single affine expression,
764	* then we also update build->values, effectively marking the current
765	* dimension as "eliminated".
766	*
767	* When computing the gist of the fixed value that can be represented
768	* as a single affine expression, it is important to only take into
769	* account the domain constraints in the original AST build and
770	* not the domain of the affine expression itself.
771	* Otherwise, a [i/3] is changed into a i/3 because we know that i
772	* is a multiple of 3, but then we end up not expressing anywhere
773	* in the context that i is a multiple of 3.
774	*/
775	static __isl_give isl_ast_build *update_values(
776	__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
777	{
778	isl_bool sv;
779	isl_size n;
780	isl_pw_multi_aff *pma;
781	isl_aff *aff = NULL;
782	isl_map *it_map;
783	isl_set *set;
784
785	set = isl_set_from_basic_set(bset: bounds);
786	set = isl_set_intersect(set1: set, set2: isl_set_copy(set: build->domain));
787	set = intersect_stride_constraint(set, build);
788	it_map = isl_ast_build_map_to_iterator(build, set);
789
790	sv = isl_map_is_single_valued(map: it_map);
791	if (sv < 0)
792	build = isl_ast_build_free(build);
793	if (!build || !sv) {
794	isl_map_free(map: it_map);
795	return build;
796	}
797
798	pma = isl_pw_multi_aff_from_map(map: it_map);
799	build->value = isl_pw_multi_aff_get_pw_aff(pma, pos: 0);
800	build->value = isl_ast_build_compute_gist_pw_aff(build, pa: build->value);
801	build->value = isl_pw_aff_coalesce(pa: build->value);
802	isl_pw_multi_aff_free(pma);
803
804	n = isl_pw_aff_n_piece(pwaff: build->value);
805	if (n < 0)
806	return isl_ast_build_free(build);
807	if (n != 1)
808	return build;
809
810	isl_pw_aff_foreach_piece(pwaff: build->value, fn: &extract_single_piece, user: &aff);
811
812	build->values = isl_multi_aff_set_aff(multi: build->values, pos: build->depth, el: aff);
813	if (!build->values)
814	return isl_ast_build_free(build);
815	isl_ast_build_reset_schedule_map(build);
816	return build;
817	}
818
819	/* Update the AST build based on the given loop bounds for
820	* the current dimension and the stride information available in the build.
821	*
822	* We first make sure that the bounds do not refer to any iterators
823	* that have already been eliminated.
824	* Then, we check if the bounds imply that the current iterator
825	* has a fixed value.
826	* If they do and if this fixed value can be expressed as a single
827	* affine expression, we eliminate the iterators from the bounds.
828	* Note that we cannot simply plug in this single value using
829	* isl_basic_set_preimage_multi_aff as the single value may only
830	* be defined on a subset of the domain. Plugging in the value
831	* would restrict the build domain to this subset, while this
832	* restriction may not be reflected in the generated code.
833	* Finally, we intersect build->domain with the updated bounds.
834	* We also add the stride constraint unless we have been able
835	* to find a fixed value expressed as a single affine expression.
836	*
837	* Note that the check for a fixed value in update_values requires
838	* us to intersect the bounds with the current build domain.
839	* When we intersect build->domain with the updated bounds in
840	* the final step, we make sure that these updated bounds have
841	* not been intersected with the old build->domain.
842	* Otherwise, we would indirectly intersect the build domain with itself,
843	* which can lead to inefficiencies, in particular if the build domain
844	* contains any unknown divs.
845	*
846	* The pending and generated sets are not updated by this function to
847	* match the updated domain.
848	* The caller still needs to call isl_ast_build_set_pending_generated.
849	*/
850	__isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
851	__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
852	{
853	isl_set *set;
854
855	build = isl_ast_build_cow(build);
856	if (!build)
857	goto error;
858
859	build = update_values(build, bounds: isl_basic_set_copy(bset: bounds));
860	if (!build)
861	goto error;
862	set = isl_set_from_basic_set(bset: isl_basic_set_copy(bset: bounds));
863	if (isl_ast_build_has_affine_value(build, pos: build->depth)) {
864	set = isl_set_eliminate(set, type: isl_dim_set, first: build->depth, n: 1);
865	set = isl_set_compute_divs(set);
866	build->pending = isl_set_intersect(set1: build->pending,
867	set2: isl_set_copy(set));
868	build->domain = isl_set_intersect(set1: build->domain, set2: set);
869	} else {
870	build->domain = isl_set_intersect(set1: build->domain, set2: set);
871	build = isl_ast_build_include_stride(build);
872	if (!build)
873	goto error;
874	}
875	isl_basic_set_free(bset: bounds);
876
877	if (!build->domain || !build->pending || !build->generated)
878	return isl_ast_build_free(build);
879
880	return build;
881	error:
882	isl_ast_build_free(build);
883	isl_basic_set_free(bset: bounds);
884	return NULL;
885	}
886
887	/* Update the pending and generated sets of "build" according to "bounds".
888	* If the build has an affine value at the current depth,
889	* then isl_ast_build_set_loop_bounds has already set the pending set.
890	* Otherwise, do it here.
891	*/
892	__isl_give isl_ast_build *isl_ast_build_set_pending_generated(
893	__isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
894	{
895	isl_basic_set *generated, *pending;
896
897	if (!build)
898	goto error;
899
900	if (isl_ast_build_has_affine_value(build, pos: build->depth)) {
901	isl_basic_set_free(bset: bounds);
902	return build;
903	}
904
905	build = isl_ast_build_cow(build);
906	if (!build)
907	goto error;
908
909	pending = isl_basic_set_copy(bset: bounds);
910	pending = isl_basic_set_drop_constraints_involving_dims(bset: pending,
911	type: isl_dim_set, first: build->depth, n: 1);
912	build->pending = isl_set_intersect(set1: build->pending,
913	set2: isl_set_from_basic_set(bset: pending));
914	generated = bounds;
915	generated = isl_basic_set_drop_constraints_not_involving_dims(
916	bset: generated, type: isl_dim_set, first: build->depth, n: 1);
917	build->generated = isl_set_intersect(set1: build->generated,
918	set2: isl_set_from_basic_set(bset: generated));
919
920	if (!build->pending || !build->generated)
921	return isl_ast_build_free(build);
922
923	return build;
924	error:
925	isl_ast_build_free(build);
926	isl_basic_set_free(bset: bounds);
927	return NULL;
928	}
929
930	/* Intersect build->domain with "set", where "set" is specified
931	* in terms of the internal schedule domain.
932	*/
933	static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
934	__isl_take isl_ast_build *build, __isl_take isl_set *set)
935	{
936	build = isl_ast_build_cow(build);
937	if (!build)
938	goto error;
939
940	set = isl_set_compute_divs(set);
941	build->domain = isl_set_intersect(set1: build->domain, set2: set);
942	build->domain = isl_set_coalesce(set: build->domain);
943
944	if (!build->domain)
945	return isl_ast_build_free(build);
946
947	return build;
948	error:
949	isl_ast_build_free(build);
950	isl_set_free(set);
951	return NULL;
952	}
953
954	/* Intersect build->generated and build->domain with "set",
955	* where "set" is specified in terms of the internal schedule domain.
956	*/
957	__isl_give isl_ast_build *isl_ast_build_restrict_generated(
958	__isl_take isl_ast_build *build, __isl_take isl_set *set)
959	{
960	set = isl_set_compute_divs(set);
961	build = isl_ast_build_restrict_internal(build, set: isl_set_copy(set));
962	build = isl_ast_build_cow(build);
963	if (!build)
964	goto error;
965
966	build->generated = isl_set_intersect(set1: build->generated, set2: set);
967	build->generated = isl_set_coalesce(set: build->generated);
968
969	if (!build->generated)
970	return isl_ast_build_free(build);
971
972	return build;
973	error:
974	isl_ast_build_free(build);
975	isl_set_free(set);
976	return NULL;
977	}
978
979	/* Replace the set of pending constraints by "guard", which is then
980	* no longer considered as pending.
981	* That is, add "guard" to the generated constraints and clear all pending
982	* constraints, making the domain equal to the generated constraints.
983	*/
984	__isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
985	__isl_take isl_ast_build *build, __isl_take isl_set *guard)
986	{
987	build = isl_ast_build_restrict_generated(build, set: guard);
988	build = isl_ast_build_cow(build);
989	if (!build)
990	return NULL;
991
992	isl_set_free(set: build->domain);
993	build->domain = isl_set_copy(set: build->generated);
994	isl_set_free(set: build->pending);
995	build->pending = isl_set_universe(space: isl_set_get_space(set: build->domain));
996
997	if (!build->pending)
998	return isl_ast_build_free(build);
999
1000	return build;
1001	}
1002
1003	/* Intersect build->domain with "set", where "set" is specified
1004	* in terms of the external schedule domain.
1005	*/
1006	__isl_give isl_ast_build *isl_ast_build_restrict(
1007	__isl_take isl_ast_build *build, __isl_take isl_set *set)
1008	{
1009	isl_bool needs_map;
1010
1011	if (isl_set_is_params(set))
1012	return isl_ast_build_restrict_generated(build, set);
1013
1014	needs_map = isl_ast_build_need_schedule_map(build);
1015	if (needs_map < 0)
1016	goto error;
1017	if (needs_map) {
1018	isl_multi_aff *ma;
1019	ma = isl_ast_build_get_schedule_map_multi_aff(build);
1020	set = isl_set_preimage_multi_aff(set, ma);
1021	}
1022	return isl_ast_build_restrict_generated(build, set);
1023	error:
1024	isl_ast_build_free(build);
1025	isl_set_free(set);
1026	return NULL;
1027	}
1028
1029	/* Replace build->executed by "executed".
1030	*/
1031	__isl_give isl_ast_build *isl_ast_build_set_executed(
1032	__isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
1033	{
1034	build = isl_ast_build_cow(build);
1035	if (!build)
1036	goto error;
1037
1038	isl_union_map_free(umap: build->executed);
1039	build->executed = executed;
1040
1041	return build;
1042	error:
1043	isl_ast_build_free(build);
1044	isl_union_map_free(umap: executed);
1045	return NULL;
1046	}
1047
1048	/* Does "build" point to a band node?
1049	* That is, are we currently handling a band node inside a schedule tree?
1050	*/
1051	int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1052	{
1053	if (!build)
1054	return -1;
1055	return build->node != NULL;
1056	}
1057
1058	/* Return a copy of the band node that "build" refers to.
1059	*/
1060	__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1061	__isl_keep isl_ast_build *build)
1062	{
1063	if (!build)
1064	return NULL;
1065	return isl_schedule_node_copy(node: build->node);
1066	}
1067
1068	/* Extract the loop AST generation types for the members of build->node
1069	* and store them in build->loop_type.
1070	*/
1071	static __isl_give isl_ast_build *extract_loop_types(
1072	__isl_take isl_ast_build *build)
1073	{
1074	int i;
1075	isl_size n;
1076	isl_ctx *ctx;
1077	isl_schedule_node *node;
1078
1079	if (!build)
1080	return NULL;
1081	n = isl_schedule_node_band_n_member(node: build->node);
1082	if (n < 0)
1083	return isl_ast_build_free(build);
1084	ctx = isl_ast_build_get_ctx(build);
1085	if (!build->node)
1086	isl_die(ctx, isl_error_internal, "missing AST node",
1087	return isl_ast_build_free(build));
1088
1089	free(ptr: build->loop_type);
1090	build->n = n;
1091	build->loop_type = isl_alloc_array(ctx,
1092	enum isl_ast_loop_type, build->n);
1093	if (build->n && !build->loop_type)
1094	return isl_ast_build_free(build);
1095	node = build->node;
1096	for (i = 0; i < build->n; ++i)
1097	build->loop_type[i] =
1098	isl_schedule_node_band_member_get_ast_loop_type(node, pos: i);
1099
1100	return build;
1101	}
1102
1103	/* Replace the band node that "build" refers to by "node" and
1104	* extract the corresponding loop AST generation types.
1105	*/
1106	__isl_give isl_ast_build *isl_ast_build_set_schedule_node(
1107	__isl_take isl_ast_build *build,
1108	__isl_take isl_schedule_node *node)
1109	{
1110	build = isl_ast_build_cow(build);
1111	if (!build || !node)
1112	goto error;
1113
1114	isl_schedule_node_free(node: build->node);
1115	build->node = node;
1116
1117	build = extract_loop_types(build);
1118
1119	return build;
1120	error:
1121	isl_ast_build_free(build);
1122	isl_schedule_node_free(node);
1123	return NULL;
1124	}
1125
1126	/* Remove any reference to a band node from "build".
1127	*/
1128	__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1129	__isl_take isl_ast_build *build)
1130	{
1131	build = isl_ast_build_cow(build);
1132	if (!build)
1133	return NULL;
1134
1135	isl_schedule_node_free(node: build->node);
1136	build->node = NULL;
1137
1138	return build;
1139	}
1140
1141	/* Return a copy of the current schedule domain.
1142	*/
1143	__isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1144	{
1145	return build ? isl_set_copy(set: build->domain) : NULL;
1146	}
1147
1148	/* Return a copy of the set of pending constraints.
1149	*/
1150	__isl_give isl_set *isl_ast_build_get_pending(
1151	__isl_keep isl_ast_build *build)
1152	{
1153	return build ? isl_set_copy(set: build->pending) : NULL;
1154	}
1155
1156	/* Return a copy of the set of generated constraints.
1157	*/
1158	__isl_give isl_set *isl_ast_build_get_generated(
1159	__isl_keep isl_ast_build *build)
1160	{
1161	return build ? isl_set_copy(set: build->generated) : NULL;
1162	}
1163
1164	/* Return a copy of the map from the internal schedule domain
1165	* to the original input schedule domain.
1166	*/
1167	__isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1168	__isl_keep isl_ast_build *build)
1169	{
1170	return build ? isl_multi_aff_copy(multi: build->internal2input) : NULL;
1171	}
1172
1173	/* Return the number of variables of the given type
1174	* in the (internal) schedule space.
1175	*/
1176	isl_size isl_ast_build_dim(__isl_keep isl_ast_build *build,
1177	enum isl_dim_type type)
1178	{
1179	if (!build)
1180	return isl_size_error;
1181	return isl_set_dim(set: build->domain, type);
1182	}
1183
1184	/* Return the (schedule) space of "build".
1185	*
1186	* If "internal" is set, then this space is the space of the internal
1187	* representation of the entire schedule, including those parts for
1188	* which no code has been generated yet.
1189	*
1190	* If "internal" is not set, then this space is the external representation
1191	* of the loops generated so far.
1192	*/
1193	__isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1194	int internal)
1195	{
1196	int i;
1197	isl_size dim;
1198	isl_bool needs_map;
1199	isl_space *space;
1200
1201	if (!build)
1202	return NULL;
1203
1204	space = isl_set_get_space(set: build->domain);
1205	if (internal)
1206	return space;
1207
1208	needs_map = isl_ast_build_need_schedule_map(build);
1209	if (needs_map < 0)
1210	return isl_space_free(space);
1211	if (!needs_map)
1212	return space;
1213
1214	dim = isl_ast_build_dim(build, type: isl_dim_set);
1215	if (dim < 0)
1216	return isl_space_free(space);
1217	space = isl_space_drop_dims(space, type: isl_dim_set,
1218	first: build->depth, num: dim - build->depth);
1219	for (i = build->depth - 1; i >= 0; --i) {
1220	isl_bool affine = isl_ast_build_has_affine_value(build, pos: i);
1221
1222	if (affine < 0)
1223	return isl_space_free(space);
1224	if (affine)
1225	space = isl_space_drop_dims(space, type: isl_dim_set, first: i, num: 1);
1226	}
1227
1228	return space;
1229	}
1230
1231	/* Return the external representation of the schedule space of "build",
1232	* i.e., a space with a dimension for each loop generated so far,
1233	* with the names of the dimensions set to the loop iterators.
1234	*/
1235	__isl_give isl_space *isl_ast_build_get_schedule_space(
1236	__isl_keep isl_ast_build *build)
1237	{
1238	isl_space *space;
1239	int i, skip;
1240
1241	if (!build)
1242	return NULL;
1243
1244	space = isl_ast_build_get_space(build, internal: 0);
1245
1246	skip = 0;
1247	for (i = 0; i < build->depth; ++i) {
1248	isl_id *id;
1249
1250	if (isl_ast_build_has_affine_value(build, pos: i)) {
1251	skip++;
1252	continue;
1253	}
1254
1255	id = isl_ast_build_get_iterator_id(build, pos: i);
1256	space = isl_space_set_dim_id(space, type: isl_dim_set, pos: i - skip, id);
1257	}
1258
1259	return space;
1260	}
1261
1262	/* Return the current schedule, as stored in build->executed, in terms
1263	* of the external schedule domain.
1264	*/
1265	__isl_give isl_union_map *isl_ast_build_get_schedule(
1266	__isl_keep isl_ast_build *build)
1267	{
1268	isl_bool needs_map;
1269	isl_union_map *executed;
1270	isl_union_map *schedule;
1271
1272	needs_map = isl_ast_build_need_schedule_map(build);
1273	if (needs_map < 0)
1274	return NULL;
1275
1276	executed = isl_union_map_copy(umap: build->executed);
1277	if (needs_map) {
1278	isl_map *proj = isl_ast_build_get_schedule_map(build);
1279	executed = isl_union_map_apply_domain(umap1: executed,
1280	umap2: isl_union_map_from_map(map: proj));
1281	}
1282	schedule = isl_union_map_reverse(umap: executed);
1283
1284	return schedule;
1285	}
1286
1287	/* Return the iterator attached to the internal schedule dimension "pos".
1288	*/
1289	__isl_give isl_id *isl_ast_build_get_iterator_id(
1290	__isl_keep isl_ast_build *build, int pos)
1291	{
1292	if (!build)
1293	return NULL;
1294
1295	return isl_id_list_get_id(list: build->iterators, index: pos);
1296	}
1297
1298	/* Set the stride and offset of the current dimension to the given
1299	* value and expression.
1300	*/
1301	static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1302	__isl_take isl_val *stride, __isl_take isl_aff *offset)
1303	{
1304	int pos;
1305
1306	build = isl_ast_build_cow(build);
1307	if (!build || !stride || !offset)
1308	goto error;
1309
1310	pos = build->depth;
1311
1312	build->strides = isl_vec_set_element_val(vec: build->strides, pos, v: stride);
1313	build->offsets = isl_multi_aff_set_aff(multi: build->offsets, pos, el: offset);
1314	if (!build->strides || !build->offsets)
1315	return isl_ast_build_free(build);
1316
1317	return build;
1318	error:
1319	isl_val_free(v: stride);
1320	isl_aff_free(aff: offset);
1321	return isl_ast_build_free(build);
1322	}
1323
1324	/* Return a set expressing the stride constraint at the current depth.
1325	*
1326	* In particular, if the current iterator (i) is known to attain values
1327	*
1328	* f + s a
1329	*
1330	* where f is the offset and s is the stride, then the returned set
1331	* expresses the constraint
1332	*
1333	* (f - i) mod s = 0
1334	*/
1335	__isl_give isl_set *isl_ast_build_get_stride_constraint(
1336	__isl_keep isl_ast_build *build)
1337	{
1338	isl_aff *aff;
1339	isl_set *set;
1340	isl_val *stride;
1341	int pos;
1342
1343	if (!build)
1344	return NULL;
1345
1346	pos = build->depth;
1347
1348	if (!isl_ast_build_has_stride(build, pos))
1349	return isl_set_universe(space: isl_ast_build_get_space(build, internal: 1));
1350
1351	stride = isl_ast_build_get_stride(build, pos);
1352	aff = isl_ast_build_get_offset(build, pos);
1353	aff = isl_aff_add_coefficient_si(aff, type: isl_dim_in, pos, v: -1);
1354	aff = isl_aff_mod_val(aff, mod: stride);
1355	set = isl_set_from_basic_set(bset: isl_aff_zero_basic_set(aff));
1356
1357	return set;
1358	}
1359
1360	/* Return the expansion implied by the stride and offset at the current
1361	* depth.
1362	*
1363	* That is, return the mapping
1364	*
1365	* [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1366	* -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1367	*
1368	* where s is the stride at the current depth d and offset(i) is
1369	* the corresponding offset.
1370	*/
1371	__isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1372	__isl_keep isl_ast_build *build)
1373	{
1374	isl_space *space;
1375	isl_multi_aff *ma;
1376	isl_size pos;
1377	isl_aff *aff, *offset;
1378	isl_val *stride;
1379
1380	pos = isl_ast_build_get_depth(build);
1381	if (pos < 0)
1382	return NULL;
1383
1384	space = isl_ast_build_get_space(build, internal: 1);
1385	space = isl_space_map_from_set(space);
1386	ma = isl_multi_aff_identity(space);
1387
1388	if (!isl_ast_build_has_stride(build, pos))
1389	return ma;
1390
1391	offset = isl_ast_build_get_offset(build, pos);
1392	stride = isl_ast_build_get_stride(build, pos);
1393	aff = isl_multi_aff_get_aff(multi: ma, pos);
1394	aff = isl_aff_scale_val(aff, v: stride);
1395	aff = isl_aff_add(aff1: aff, aff2: offset);
1396	ma = isl_multi_aff_set_aff(multi: ma, pos, el: aff);
1397
1398	return ma;
1399	}
1400
1401	/* Add constraints corresponding to any previously detected
1402	* stride on the current dimension to build->domain.
1403	*/
1404	__isl_give isl_ast_build *isl_ast_build_include_stride(
1405	__isl_take isl_ast_build *build)
1406	{
1407	isl_set *set;
1408
1409	if (!build)
1410	return NULL;
1411	if (!isl_ast_build_has_stride(build, pos: build->depth))
1412	return build;
1413	build = isl_ast_build_cow(build);
1414	if (!build)
1415	return NULL;
1416
1417	set = isl_ast_build_get_stride_constraint(build);
1418
1419	build->domain = isl_set_intersect(set1: build->domain, set2: isl_set_copy(set));
1420	build->generated = isl_set_intersect(set1: build->generated, set2: set);
1421	if (!build->domain || !build->generated)
1422	return isl_ast_build_free(build);
1423
1424	return build;
1425	}
1426
1427	/* Check if the constraints in "set" imply any stride on the current
1428	* dimension and, if so, record the stride information in "build"
1429	* and return the updated "build".
1430	*
1431	* We assume that inner dimensions have been eliminated from "set"
1432	* by the caller. This is needed because the common stride
1433	* may be imposed by different inner dimensions on different parts of
1434	* the domain.
1435	* The assumption ensures that the lower bound does not depend
1436	* on inner dimensions.
1437	*/
1438	__isl_give isl_ast_build *isl_ast_build_detect_strides(
1439	__isl_take isl_ast_build *build, __isl_take isl_set *set)
1440	{
1441	isl_size pos;
1442	isl_bool no_stride;
1443	isl_val *stride;
1444	isl_aff *offset;
1445	isl_stride_info *si;
1446
1447	pos = isl_ast_build_get_depth(build);
1448	if (pos < 0)
1449	goto error;
1450
1451	si = isl_set_get_stride_info(set, pos);
1452	stride = isl_stride_info_get_stride(si);
1453	offset = isl_stride_info_get_offset(si);
1454	isl_stride_info_free(si);
1455	isl_set_free(set);
1456
1457	no_stride = isl_val_is_one(v: stride);
1458	if (no_stride >= 0 && !no_stride)
1459	return set_stride(build, stride, offset);
1460	isl_val_free(v: stride);
1461	isl_aff_free(aff: offset);
1462	if (no_stride < 0)
1463	return isl_ast_build_free(build);
1464	return build;
1465	error:
1466	isl_set_free(set);
1467	return NULL;
1468	}
1469
1470	/* Does "map" not involve the input dimension data->depth?
1471	*/
1472	static isl_bool free_of_depth(__isl_keep isl_map *map, void *user)
1473	{
1474	int *depth = user;
1475
1476	return isl_bool_not(b: isl_map_involves_dims(map, type: isl_dim_in, first: *depth, n: 1));
1477	}
1478
1479	/* Do any options depend on the value of the dimension at the current depth?
1480	*/
1481	int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1482	{
1483	isl_bool free;
1484
1485	if (!build)
1486	return -1;
1487
1488	free = isl_union_map_every_map(umap: build->options, test: &free_of_depth,
1489	user: &build->depth);
1490	return isl_bool_not(b: free);
1491	}
1492
1493	/* Construct the map
1494	*
1495	* { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1496	*
1497	* with "space" the parameter space of the constructed map.
1498	*/
1499	static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1500	int pos)
1501	{
1502	isl_constraint *c;
1503	isl_basic_map *bmap1, *bmap2;
1504
1505	space = isl_space_set_from_params(space);
1506	space = isl_space_add_dims(space, type: isl_dim_set, n: 1);
1507	space = isl_space_map_from_set(space);
1508	c = isl_constraint_alloc_equality(ls: isl_local_space_from_space(space));
1509	c = isl_constraint_set_coefficient_si(constraint: c, type: isl_dim_in, pos: 0, v: 1);
1510	c = isl_constraint_set_coefficient_si(constraint: c, type: isl_dim_out, pos: 0, v: -1);
1511	bmap1 = isl_basic_map_from_constraint(constraint: isl_constraint_copy(c));
1512	c = isl_constraint_set_constant_si(constraint: c, v: 1);
1513	bmap2 = isl_basic_map_from_constraint(constraint: c);
1514
1515	bmap1 = isl_basic_map_upper_bound_si(bmap: bmap1, type: isl_dim_in, pos: 0, value: pos - 1);
1516	bmap2 = isl_basic_map_lower_bound_si(bmap: bmap2, type: isl_dim_in, pos: 0, value: pos);
1517
1518	return isl_basic_map_union(bmap1, bmap2);
1519	}
1520
1521	static const char *option_str[] = {
1522	[isl_ast_loop_atomic] = "atomic",
1523	[isl_ast_loop_unroll] = "unroll",
1524	[isl_ast_loop_separate] = "separate"
1525	};
1526
1527	/* Update the "options" to reflect the insertion of a dimension
1528	* at position "pos" in the schedule domain space.
1529	* "space" is the original domain space before the insertion and
1530	* may be named and/or structured.
1531	*
1532	* The (relevant) input options all have "space" as domain, which
1533	* has to be mapped to the extended space.
1534	* The values of the ranges also refer to the schedule domain positions
1535	* and they therefore also need to be adjusted. In particular, values
1536	* smaller than pos do not need to change, while values greater than or
1537	* equal to pos need to be incremented.
1538	* That is, we need to apply the following map.
1539	*
1540	* { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1541	* unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1542	* separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1543	* separation_class[[i] -> [c]]
1544	* -> separation_class[[i] -> [c]] : i < pos;
1545	* separation_class[[i] -> [c]]
1546	* -> separation_class[[i + 1] -> [c]] : i >= pos }
1547	*/
1548	static __isl_give isl_union_map *options_insert_dim(
1549	__isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1550	{
1551	isl_map *map;
1552	isl_union_map *insertion;
1553	enum isl_ast_loop_type type;
1554	const char *name = "separation_class";
1555
1556	space = isl_space_map_from_set(space);
1557	map = isl_map_identity(space);
1558	map = isl_map_insert_dims(map, type: isl_dim_out, pos, n: 1);
1559	options = isl_union_map_apply_domain(umap1: options,
1560	umap2: isl_union_map_from_map(map));
1561
1562	if (!options)
1563	return NULL;
1564
1565	map = construct_insertion_map(space: isl_union_map_get_space(umap: options), pos);
1566
1567	insertion = isl_union_map_empty(space: isl_union_map_get_space(umap: options));
1568
1569	for (type = isl_ast_loop_atomic;
1570	type <= isl_ast_loop_separate; ++type) {
1571	isl_map *map_type = isl_map_copy(map);
1572	const char *name = option_str[type];
1573	map_type = isl_map_set_tuple_name(map: map_type, type: isl_dim_in, s: name);
1574	map_type = isl_map_set_tuple_name(map: map_type, type: isl_dim_out, s: name);
1575	insertion = isl_union_map_add_map(umap: insertion, map: map_type);
1576	}
1577
1578	map = isl_map_product(map1: map, map2: isl_map_identity(space: isl_map_get_space(map)));
1579	map = isl_map_set_tuple_name(map, type: isl_dim_in, s: name);
1580	map = isl_map_set_tuple_name(map, type: isl_dim_out, s: name);
1581	insertion = isl_union_map_add_map(umap: insertion, map);
1582
1583	options = isl_union_map_apply_range(umap1: options, umap2: insertion);
1584
1585	return options;
1586	}
1587
1588	/* If we are generating an AST from a schedule tree (build->node is set),
1589	* then update the loop AST generation types
1590	* to reflect the insertion of a dimension at (global) position "pos"
1591	* in the schedule domain space.
1592	* We do not need to adjust any isolate option since we would not be inserting
1593	* any dimensions if there were any isolate option.
1594	*/
1595	static __isl_give isl_ast_build *node_insert_dim(
1596	__isl_take isl_ast_build *build, int pos)
1597	{
1598	int i;
1599	int local_pos;
1600	enum isl_ast_loop_type *loop_type;
1601	isl_ctx *ctx;
1602
1603	build = isl_ast_build_cow(build);
1604	if (!build)
1605	return NULL;
1606	if (!build->node)
1607	return build;
1608
1609	ctx = isl_ast_build_get_ctx(build);
1610	local_pos = pos - build->outer_pos;
1611	loop_type = isl_realloc_array(ctx, build->loop_type,
1612	enum isl_ast_loop_type, build->n + 1);
1613	if (!loop_type)
1614	return isl_ast_build_free(build);
1615	build->loop_type = loop_type;
1616	for (i = build->n - 1; i >= local_pos; --i)
1617	loop_type[i + 1] = loop_type[i];
1618	loop_type[local_pos] = isl_ast_loop_default;
1619	build->n++;
1620
1621	return build;
1622	}
1623
1624	/* Insert a single dimension in the schedule domain at position "pos".
1625	* The new dimension is given an isl_id with the empty string as name.
1626	*
1627	* The main difficulty is updating build->options to reflect the
1628	* extra dimension. This is handled in options_insert_dim.
1629	*
1630	* Note that because of the dimension manipulations, the resulting
1631	* schedule domain space will always be unnamed and unstructured.
1632	* However, the original schedule domain space may be named and/or
1633	* structured, so we have to take this possibility into account
1634	* while performing the transformations.
1635	*
1636	* Since the inserted schedule dimension is used by the caller
1637	* to differentiate between different domain spaces, there is
1638	* no longer a uniform mapping from the internal schedule space
1639	* to the input schedule space. The internal2input mapping is
1640	* therefore removed.
1641	*/
1642	__isl_give isl_ast_build *isl_ast_build_insert_dim(
1643	__isl_take isl_ast_build *build, int pos)
1644	{
1645	isl_ctx *ctx;
1646	isl_space *space, *ma_space;
1647	isl_id *id;
1648	isl_multi_aff *ma;
1649
1650	build = isl_ast_build_cow(build);
1651	if (!build)
1652	return NULL;
1653
1654	ctx = isl_ast_build_get_ctx(build);
1655	id = isl_id_alloc(ctx, name: "", NULL);
1656	if (!build->node)
1657	space = isl_ast_build_get_space(build, internal: 1);
1658	build->iterators = isl_id_list_insert(list: build->iterators, pos, el: id);
1659	build->domain = isl_set_insert_dims(set: build->domain,
1660	type: isl_dim_set, pos, n: 1);
1661	build->generated = isl_set_insert_dims(set: build->generated,
1662	type: isl_dim_set, pos, n: 1);
1663	build->pending = isl_set_insert_dims(set: build->pending,
1664	type: isl_dim_set, pos, n: 1);
1665	build->strides = isl_vec_insert_els(vec: build->strides, pos, n: 1);
1666	build->strides = isl_vec_set_element_si(vec: build->strides, pos, v: 1);
1667	ma_space = isl_space_params(space: isl_multi_aff_get_space(multi: build->offsets));
1668	ma_space = isl_space_set_from_params(space: ma_space);
1669	ma_space = isl_space_add_dims(space: ma_space, type: isl_dim_set, n: 1);
1670	ma_space = isl_space_map_from_set(space: ma_space);
1671	ma = isl_multi_aff_zero(space: isl_space_copy(space: ma_space));
1672	build->offsets = isl_multi_aff_splice(multi1: build->offsets, in_pos: pos, out_pos: pos, multi2: ma);
1673	ma = isl_multi_aff_identity(space: ma_space);
1674	build->values = isl_multi_aff_splice(multi1: build->values, in_pos: pos, out_pos: pos, multi2: ma);
1675	if (!build->node)
1676	build->options = options_insert_dim(options: build->options, space, pos);
1677	build->internal2input = isl_multi_aff_free(multi: build->internal2input);
1678
1679	if (!build->iterators || !build->domain || !build->generated ||
1680	!build->pending || !build->values ||
1681	!build->strides || !build->offsets || !build->options)
1682	return isl_ast_build_free(build);
1683
1684	build = node_insert_dim(build, pos);
1685
1686	return build;
1687	}
1688
1689	/* Scale down the current dimension by a factor of "m".
1690	* "umap" is an isl_union_map that implements the scaling down.
1691	* That is, it is of the form
1692	*
1693	* { [.... i ....] -> [.... i' ....] : i = m i' }
1694	*
1695	* This function is called right after the strides have been
1696	* detected, but before any constraints on the current dimension
1697	* have been included in build->domain.
1698	* We therefore only need to update stride, offset, the options and
1699	* the mapping from internal schedule space to the original schedule
1700	* space, if we are still keeping track of such a mapping.
1701	* The latter mapping is updated by plugging in
1702	* { [... i ...] -> [... m i ... ] }.
1703	*/
1704	__isl_give isl_ast_build *isl_ast_build_scale_down(
1705	__isl_take isl_ast_build *build, __isl_take isl_val *m,
1706	__isl_take isl_union_map *umap)
1707	{
1708	isl_aff *aff;
1709	isl_val *v;
1710	int depth;
1711
1712	build = isl_ast_build_cow(build);
1713	if (!build || !umap || !m)
1714	goto error;
1715
1716	depth = build->depth;
1717
1718	if (build->internal2input) {
1719	isl_space *space;
1720	isl_multi_aff *ma;
1721	isl_aff *aff;
1722
1723	space = isl_multi_aff_get_space(multi: build->internal2input);
1724	space = isl_space_map_from_set(space: isl_space_domain(space));
1725	ma = isl_multi_aff_identity(space);
1726	aff = isl_multi_aff_get_aff(multi: ma, pos: depth);
1727	aff = isl_aff_scale_val(aff, v: isl_val_copy(v: m));
1728	ma = isl_multi_aff_set_aff(multi: ma, pos: depth, el: aff);
1729	build->internal2input =
1730	isl_multi_aff_pullback_multi_aff(ma1: build->internal2input, ma2: ma);
1731	if (!build->internal2input)
1732	goto error;
1733	}
1734
1735	v = isl_vec_get_element_val(vec: build->strides, pos: depth);
1736	v = isl_val_div(v1: v, v2: isl_val_copy(v: m));
1737	build->strides = isl_vec_set_element_val(vec: build->strides, pos: depth, v);
1738
1739	aff = isl_multi_aff_get_aff(multi: build->offsets, pos: depth);
1740	aff = isl_aff_scale_down_val(aff, v: m);
1741	build->offsets = isl_multi_aff_set_aff(multi: build->offsets, pos: depth, el: aff);
1742	build->options = isl_union_map_apply_domain(umap1: build->options, umap2: umap);
1743	if (!build->strides || !build->offsets || !build->options)
1744	return isl_ast_build_free(build);
1745
1746	return build;
1747	error:
1748	isl_val_free(v: m);
1749	isl_union_map_free(umap);
1750	return isl_ast_build_free(build);
1751	}
1752
1753	/* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1754	* If an isl_id with such a name already appears among the parameters
1755	* in build->domain, then adjust the name to "c%d_%d".
1756	*/
1757	static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1758	__isl_keep isl_ast_build *build)
1759	{
1760	int i;
1761	isl_id_list *names;
1762
1763	names = isl_id_list_alloc(ctx, n);
1764	for (i = 0; i < n; ++i) {
1765	isl_id *id;
1766
1767	id = generate_name(ctx, i: first + i, build);
1768	names = isl_id_list_add(list: names, el: id);
1769	}
1770
1771	return names;
1772	}
1773
1774	/* Embed "options" into the given isl_ast_build space.
1775	*
1776	* This function is called from within a nested call to
1777	* isl_ast_build_node_from_schedule_map.
1778	* "options" refers to the additional schedule,
1779	* while space refers to both the space of the outer isl_ast_build and
1780	* that of the additional schedule.
1781	* Specifically, space is of the form
1782	*
1783	* [I -> S]
1784	*
1785	* while options lives in the space(s)
1786	*
1787	* S -> *
1788	*
1789	* We compute
1790	*
1791	* [I -> S] -> S
1792	*
1793	* and compose this with options, to obtain the new options
1794	* living in the space(s)
1795	*
1796	* [I -> S] -> *
1797	*/
1798	static __isl_give isl_union_map *embed_options(
1799	__isl_take isl_union_map *options, __isl_take isl_space *space)
1800	{
1801	isl_map *map;
1802
1803	map = isl_map_universe(space: isl_space_unwrap(space));
1804	map = isl_map_range_map(map);
1805
1806	options = isl_union_map_apply_range(
1807	umap1: isl_union_map_from_map(map), umap2: options);
1808
1809	return options;
1810	}
1811
1812	/* Update "build" for use in a (possibly nested) code generation. That is,
1813	* extend "build" from an AST build on some domain O to an AST build
1814	* on domain [O -> S], with S corresponding to "space".
1815	* If the original domain is a parameter domain, then the new domain is
1816	* simply S.
1817	* "iterators" is a list of iterators for S, but the number of elements
1818	* may be smaller or greater than the number of set dimensions of S.
1819	* If "keep_iterators" is set, then any extra ids in build->iterators
1820	* are reused for S. Otherwise, these extra ids are dropped.
1821	*
1822	* We first update build->outer_pos to the current depth.
1823	* This depth is zero in case this is the outermost code generation.
1824	*
1825	* We then add additional ids such that the number of iterators is at least
1826	* equal to the dimension of the new build domain.
1827	*
1828	* If the original domain is parametric, then we are constructing
1829	* an isl_ast_build for the outer code generation and we pass control
1830	* to isl_ast_build_init.
1831	*
1832	* Otherwise, we adjust the fields of "build" to include "space".
1833	*/
1834	__isl_give isl_ast_build *isl_ast_build_product(
1835	__isl_take isl_ast_build *build, __isl_take isl_space *space)
1836	{
1837	isl_ctx *ctx;
1838	isl_vec *strides;
1839	isl_set *set;
1840	isl_multi_aff *embedding;
1841	isl_size dim, space_dim, n_it;
1842
1843	build = isl_ast_build_cow(build);
1844	if (!build)
1845	goto error;
1846
1847	build->outer_pos = build->depth;
1848
1849	ctx = isl_ast_build_get_ctx(build);
1850	dim = isl_ast_build_dim(build, type: isl_dim_set);
1851	space_dim = isl_space_dim(space, type: isl_dim_set);
1852	n_it = isl_id_list_n_id(list: build->iterators);
1853	if (dim < 0 || space_dim < 0 || n_it < 0)
1854	goto error;
1855	dim += space_dim;
1856	if (n_it < dim) {
1857	isl_id_list *l;
1858	l = generate_names(ctx, n: dim - n_it, first: n_it, build);
1859	build->iterators = isl_id_list_concat(list1: build->iterators, list2: l);
1860	}
1861
1862	if (isl_set_is_params(set: build->domain))
1863	return isl_ast_build_init(build, space);
1864
1865	set = isl_set_universe(space: isl_space_copy(space));
1866	build->domain = isl_set_product(set1: build->domain, set2: isl_set_copy(set));
1867	build->pending = isl_set_product(set1: build->pending, set2: isl_set_copy(set));
1868	build->generated = isl_set_product(set1: build->generated, set2: set);
1869
1870	strides = isl_vec_alloc(ctx, size: space_dim);
1871	strides = isl_vec_set_si(vec: strides, v: 1);
1872	build->strides = isl_vec_concat(vec1: build->strides, vec2: strides);
1873
1874	space = isl_space_map_from_set(space);
1875	build->offsets = isl_multi_aff_align_params(multi: build->offsets,
1876	model: isl_space_copy(space));
1877	build->offsets = isl_multi_aff_product(multi1: build->offsets,
1878	multi2: isl_multi_aff_zero(space: isl_space_copy(space)));
1879	build->values = isl_multi_aff_align_params(multi: build->values,
1880	model: isl_space_copy(space));
1881	embedding = isl_multi_aff_identity(space);
1882	build->values = isl_multi_aff_product(multi1: build->values,
1883	multi2: isl_multi_aff_copy(multi: embedding));
1884	if (build->internal2input) {
1885	build->internal2input =
1886	isl_multi_aff_product(multi1: build->internal2input, multi2: embedding);
1887	build->internal2input =
1888	isl_multi_aff_flatten_range(multi: build->internal2input);
1889	if (!build->internal2input)
1890	return isl_ast_build_free(build);
1891	} else {
1892	isl_multi_aff_free(multi: embedding);
1893	}
1894
1895	space = isl_ast_build_get_space(build, internal: 1);
1896	build->options = embed_options(options: build->options, space);
1897
1898	if (!build->iterators || !build->domain || !build->generated ||
1899	!build->pending || !build->values ||
1900	!build->strides || !build->offsets || !build->options)
1901	return isl_ast_build_free(build);
1902
1903	return build;
1904	error:
1905	isl_ast_build_free(build);
1906	isl_space_free(space);
1907	return NULL;
1908	}
1909
1910	/* Does "aff" only attain non-negative values over build->domain?
1911	* That is, does it not attain any negative values?
1912	*/
1913	isl_bool isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1914	__isl_keep isl_aff *aff)
1915	{
1916	isl_set *test;
1917	isl_bool empty;
1918
1919	if (!build)
1920	return isl_bool_error;
1921
1922	aff = isl_aff_copy(aff);
1923	test = isl_set_from_basic_set(bset: isl_aff_neg_basic_set(aff));
1924	test = isl_set_intersect(set1: test, set2: isl_set_copy(set: build->domain));
1925	empty = isl_set_is_empty(set: test);
1926	isl_set_free(set: test);
1927
1928	return empty;
1929	}
1930
1931	/* Does the dimension at (internal) position "pos" have a non-trivial stride?
1932	*/
1933	isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1934	{
1935	isl_val *v;
1936	isl_bool has_stride;
1937
1938	if (!build)
1939	return isl_bool_error;
1940
1941	v = isl_vec_get_element_val(vec: build->strides, pos);
1942	has_stride = isl_bool_not(b: isl_val_is_one(v));
1943	isl_val_free(v);
1944
1945	return has_stride;
1946	}
1947
1948	/* Given that the dimension at position "pos" takes on values
1949	*
1950	* f + s a
1951	*
1952	* with a an integer, return s.
1953	*/
1954	__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
1955	int pos)
1956	{
1957	if (!build)
1958	return NULL;
1959
1960	return isl_vec_get_element_val(vec: build->strides, pos);
1961	}
1962
1963	/* Given that the dimension at position "pos" takes on values
1964	*
1965	* f + s a
1966	*
1967	* with a an integer, return f.
1968	*/
1969	__isl_give isl_aff *isl_ast_build_get_offset(
1970	__isl_keep isl_ast_build *build, int pos)
1971	{
1972	if (!build)
1973	return NULL;
1974
1975	return isl_multi_aff_get_aff(multi: build->offsets, pos);
1976	}
1977
1978	/* Is the dimension at position "pos" known to attain only a single
1979	* value that, moreover, can be described by a single affine expression
1980	* in terms of the outer dimensions and parameters?
1981	*
1982	* If not, then the corresponding affine expression in build->values
1983	* is set to be equal to the same input dimension.
1984	* Otherwise, it is set to the requested expression in terms of
1985	* outer dimensions and parameters.
1986	*/
1987	isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1988	int pos)
1989	{
1990	isl_aff *aff;
1991	isl_bool involves;
1992
1993	if (!build)
1994	return isl_bool_error;
1995
1996	aff = isl_multi_aff_get_aff(multi: build->values, pos);
1997	involves = isl_aff_involves_dims(aff, type: isl_dim_in, first: pos, n: 1);
1998	isl_aff_free(aff);
1999
2000	return isl_bool_not(b: involves);
2001	}
2002
2003	/* Plug in the known values (fixed affine expressions in terms of
2004	* parameters and outer loop iterators) of all loop iterators
2005	* in the domain of "umap".
2006	*
2007	* We simply precompose "umap" with build->values.
2008	*/
2009	__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
2010	__isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
2011	{
2012	isl_multi_aff *values;
2013
2014	if (!build)
2015	return isl_union_map_free(umap);
2016
2017	values = isl_multi_aff_copy(multi: build->values);
2018	umap = isl_union_map_preimage_domain_multi_aff(umap, ma: values);
2019
2020	return umap;
2021	}
2022
2023	/* Is the current dimension known to attain only a single value?
2024	*/
2025	int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2026	{
2027	if (!build)
2028	return -1;
2029
2030	return build->value != NULL;
2031	}
2032
2033	/* Simplify the basic set "bset" based on what we know about
2034	* the iterators of already generated loops.
2035	*
2036	* "bset" is assumed to live in the (internal) schedule domain.
2037	*/
2038	__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
2039	__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2040	{
2041	if (!build)
2042	goto error;
2043
2044	bset = isl_basic_set_preimage_multi_aff(bset,
2045	ma: isl_multi_aff_copy(multi: build->values));
2046	bset = isl_basic_set_gist(bset,
2047	context: isl_set_simple_hull(set: isl_set_copy(set: build->domain)));
2048
2049	return bset;
2050	error:
2051	isl_basic_set_free(bset);
2052	return NULL;
2053	}
2054
2055	/* Simplify the set "set" based on what we know about
2056	* the iterators of already generated loops.
2057	*
2058	* "set" is assumed to live in the (internal) schedule domain.
2059	*/
2060	__isl_give isl_set *isl_ast_build_compute_gist(
2061	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
2062	{
2063	if (!build)
2064	goto error;
2065
2066	if (!isl_set_is_params(set))
2067	set = isl_set_preimage_multi_aff(set,
2068	ma: isl_multi_aff_copy(multi: build->values));
2069	set = isl_set_gist(set, context: isl_set_copy(set: build->domain));
2070
2071	return set;
2072	error:
2073	isl_set_free(set);
2074	return NULL;
2075	}
2076
2077	/* Include information about what we know about the iterators of
2078	* already generated loops to "set".
2079	*
2080	* We currently only plug in the known affine values of outer loop
2081	* iterators.
2082	* In principle we could also introduce equalities or even other
2083	* constraints implied by the intersection of "set" and build->domain.
2084	*/
2085	__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2086	__isl_take isl_set *set)
2087	{
2088	if (!build)
2089	return isl_set_free(set);
2090
2091	return isl_set_preimage_multi_aff(set,
2092	ma: isl_multi_aff_copy(multi: build->values));
2093	}
2094
2095	/* Plug in the known affine values of outer loop iterators in "bset".
2096	*/
2097	__isl_give isl_basic_set *isl_ast_build_specialize_basic_set(
2098	__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2099	{
2100	if (!build)
2101	return isl_basic_set_free(bset);
2102
2103	return isl_basic_set_preimage_multi_aff(bset,
2104	ma: isl_multi_aff_copy(multi: build->values));
2105	}
2106
2107	/* Simplify the map "map" based on what we know about
2108	* the iterators of already generated loops.
2109	*
2110	* The domain of "map" is assumed to live in the (internal) schedule domain.
2111	*/
2112	__isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2113	__isl_keep isl_ast_build *build, __isl_take isl_map *map)
2114	{
2115	if (!build)
2116	goto error;
2117
2118	map = isl_map_gist_domain(map, context: isl_set_copy(set: build->domain));
2119
2120	return map;
2121	error:
2122	isl_map_free(map);
2123	return NULL;
2124	}
2125
2126	/* Simplify the affine expression "aff" based on what we know about
2127	* the iterators of already generated loops.
2128	*
2129	* The domain of "aff" is assumed to live in the (internal) schedule domain.
2130	*/
2131	__isl_give isl_aff *isl_ast_build_compute_gist_aff(
2132	__isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2133	{
2134	if (!build)
2135	goto error;
2136
2137	aff = isl_aff_gist(aff, context: isl_set_copy(set: build->domain));
2138
2139	return aff;
2140	error:
2141	isl_aff_free(aff);
2142	return NULL;
2143	}
2144
2145	/* Simplify the piecewise affine expression "aff" based on what we know about
2146	* the iterators of already generated loops.
2147	*
2148	* The domain of "pa" is assumed to live in the (internal) schedule domain.
2149	*/
2150	__isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
2151	__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2152	{
2153	if (!build)
2154	goto error;
2155
2156	if (!isl_set_is_params(set: build->domain))
2157	pa = isl_pw_aff_pullback_multi_aff(pa,
2158	ma: isl_multi_aff_copy(multi: build->values));
2159	pa = isl_pw_aff_gist(pwaff: pa, context: isl_set_copy(set: build->domain));
2160
2161	return pa;
2162	error:
2163	isl_pw_aff_free(pwaff: pa);
2164	return NULL;
2165	}
2166
2167	/* Simplify the piecewise multi-affine expression "aff" based on what
2168	* we know about the iterators of already generated loops.
2169	*
2170	* The domain of "pma" is assumed to live in the (internal) schedule domain.
2171	*/
2172	__isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
2173	__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2174	{
2175	if (!build)
2176	goto error;
2177
2178	pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2179	ma: isl_multi_aff_copy(multi: build->values));
2180	pma = isl_pw_multi_aff_gist(pma, set: isl_set_copy(set: build->domain));
2181
2182	return pma;
2183	error:
2184	isl_pw_multi_aff_free(pma);
2185	return NULL;
2186	}
2187
2188	/* Extract the schedule domain of the given type from build->options
2189	* at the current depth.
2190	*
2191	* In particular, find the subset of build->options that is of
2192	* the following form
2193	*
2194	* schedule_domain -> type[depth]
2195	*
2196	* and return the corresponding domain, after eliminating inner dimensions
2197	* and divs that depend on the current dimension.
2198	*
2199	* Note that the domain of build->options has been reformulated
2200	* in terms of the internal build space in embed_options,
2201	* but the position is still that within the current code generation.
2202	*/
2203	__isl_give isl_set *isl_ast_build_get_option_domain(
2204	__isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2205	{
2206	const char *name;
2207	isl_space *space;
2208	isl_map *option;
2209	isl_set *domain;
2210	int local_pos;
2211
2212	if (!build)
2213	return NULL;
2214
2215	name = option_str[type];
2216	local_pos = build->depth - build->outer_pos;
2217
2218	space = isl_ast_build_get_space(build, internal: 1);
2219	space = isl_space_from_domain(space);
2220	space = isl_space_add_dims(space, type: isl_dim_out, n: 1);
2221	space = isl_space_set_tuple_name(space, type: isl_dim_out, s: name);
2222
2223	option = isl_union_map_extract_map(umap: build->options, space);
2224	option = isl_map_fix_si(map: option, type: isl_dim_out, pos: 0, value: local_pos);
2225
2226	domain = isl_map_domain(bmap: option);
2227	domain = isl_ast_build_eliminate(build, domain);
2228
2229	return domain;
2230	}
2231
2232	/* How does the user want the current schedule dimension to be generated?
2233	* These choices have been extracted from the schedule node
2234	* in extract_loop_types and stored in build->loop_type.
2235	* They have been updated to reflect any dimension insertion in
2236	* node_insert_dim.
2237	* Return isl_ast_domain_error on error.
2238	*
2239	* If "isolated" is set, then we get the loop AST generation type
2240	* directly from the band node since node_insert_dim cannot have been
2241	* called on a band with the isolate option.
2242	*/
2243	enum isl_ast_loop_type isl_ast_build_get_loop_type(
2244	__isl_keep isl_ast_build *build, int isolated)
2245	{
2246	int local_pos;
2247	isl_ctx *ctx;
2248
2249	if (!build)
2250	return isl_ast_loop_error;
2251	ctx = isl_ast_build_get_ctx(build);
2252	if (!build->node)
2253	isl_die(ctx, isl_error_internal,
2254	"only works for schedule tree based AST generation",
2255	return isl_ast_loop_error);
2256
2257	local_pos = build->depth - build->outer_pos;
2258	if (!isolated)
2259	return build->loop_type[local_pos];
2260	return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2261	node: build->node, pos: local_pos);
2262	}
2263
2264	/* Extract the isolated set from the isolate option, if any,
2265	* and store in the build.
2266	* If there is no isolate option, then the isolated set is
2267	* set to the empty set.
2268	*
2269	* The isolate option is of the form
2270	*
2271	* isolate[[outer bands] -> current_band]
2272	*
2273	* We flatten this set and then map it back to the internal
2274	* schedule space.
2275	*
2276	* If we have already extracted the isolated set
2277	* or if internal2input is no longer set, then we do not
2278	* need to do anything. In the latter case, we know
2279	* that the current band cannot have any isolate option.
2280	*/
2281	__isl_give isl_ast_build *isl_ast_build_extract_isolated(
2282	__isl_take isl_ast_build *build)
2283	{
2284	isl_set *isolated;
2285
2286	if (!build)
2287	return NULL;
2288	if (!build->internal2input)
2289	return build;
2290	if (build->isolated)
2291	return build;
2292
2293	build = isl_ast_build_cow(build);
2294	if (!build)
2295	return NULL;
2296
2297	isolated = isl_schedule_node_band_get_ast_isolate_option(node: build->node);
2298	isolated = isl_set_flatten(set: isolated);
2299	isolated = isl_set_preimage_multi_aff(set: isolated,
2300	ma: isl_multi_aff_copy(multi: build->internal2input));
2301
2302	build->isolated = isolated;
2303	if (!build->isolated)
2304	return isl_ast_build_free(build);
2305
2306	return build;
2307	}
2308
2309	/* Does "build" have a non-empty isolated set?
2310	*
2311	* The caller is assumed to have called isl_ast_build_extract_isolated first.
2312	*/
2313	int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2314	{
2315	int empty;
2316
2317	if (!build)
2318	return -1;
2319	if (!build->internal2input)
2320	return 0;
2321	if (!build->isolated)
2322	isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2323	"isolated set not extracted yet", return -1);
2324
2325	empty = isl_set_plain_is_empty(set: build->isolated);
2326	return empty < 0 ? -1 : !empty;
2327	}
2328
2329	/* Return a copy of the isolated set of "build".
2330	*
2331	* The caller is assume to have called isl_ast_build_has_isolated first,
2332	* with this function returning true.
2333	* In particular, this function should not be called if we are no
2334	* longer keeping track of internal2input (and there therefore could
2335	* not possibly be any isolated set).
2336	*/
2337	__isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2338	{
2339	if (!build)
2340	return NULL;
2341	if (!build->internal2input)
2342	isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2343	"build cannot have isolated set", return NULL);
2344
2345	return isl_set_copy(set: build->isolated);
2346	}
2347
2348	/* Extract the separation class mapping at the current depth.
2349	*
2350	* In particular, find and return the subset of build->options that is of
2351	* the following form
2352	*
2353	* schedule_domain -> separation_class[[depth] -> [class]]
2354	*
2355	* The caller is expected to eliminate inner dimensions from the domain.
2356	*
2357	* Note that the domain of build->options has been reformulated
2358	* in terms of the internal build space in embed_options,
2359	* but the position is still that within the current code generation.
2360	*/
2361	__isl_give isl_map *isl_ast_build_get_separation_class(
2362	__isl_keep isl_ast_build *build)
2363	{
2364	isl_ctx *ctx;
2365	isl_space *space_sep, *space;
2366	isl_map *res;
2367	int local_pos;
2368
2369	if (!build)
2370	return NULL;
2371
2372	local_pos = build->depth - build->outer_pos;
2373	ctx = isl_ast_build_get_ctx(build);
2374	space_sep = isl_space_alloc(ctx, nparam: 0, n_in: 1, n_out: 1);
2375	space_sep = isl_space_wrap(space: space_sep);
2376	space_sep = isl_space_set_tuple_name(space: space_sep, type: isl_dim_set,
2377	s: "separation_class");
2378	space = isl_ast_build_get_space(build, internal: 1);
2379	space_sep = isl_space_align_params(space1: space_sep, space2: isl_space_copy(space));
2380	space = isl_space_map_from_domain_and_range(domain: space, range: space_sep);
2381
2382	res = isl_union_map_extract_map(umap: build->options, space);
2383	res = isl_map_fix_si(map: res, type: isl_dim_out, pos: 0, value: local_pos);
2384	res = isl_map_coalesce(map: res);
2385
2386	return res;
2387	}
2388
2389	/* Eliminate dimensions inner to the current dimension.
2390	*/
2391	__isl_give isl_set *isl_ast_build_eliminate_inner(
2392	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
2393	{
2394	int dim;
2395	int depth;
2396
2397	if (!build)
2398	return isl_set_free(set);
2399
2400	dim = isl_set_dim(set, type: isl_dim_set);
2401	depth = build->depth;
2402	set = isl_set_detect_equalities(set);
2403	set = isl_set_eliminate(set, type: isl_dim_set, first: depth + 1, n: dim - (depth + 1));
2404
2405	return set;
2406	}
2407
2408	/* Eliminate unknown divs and divs that depend on the current dimension.
2409	*
2410	* Note that during the elimination of unknown divs, we may discover
2411	* an explicit representation of some other unknown divs, which may
2412	* depend on the current dimension. We therefore need to eliminate
2413	* unknown divs first.
2414	*/
2415	__isl_give isl_set *isl_ast_build_eliminate_divs(
2416	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
2417	{
2418	int depth;
2419
2420	if (!build)
2421	return isl_set_free(set);
2422
2423	set = isl_set_remove_unknown_divs(set);
2424	depth = build->depth;
2425	set = isl_set_remove_divs_involving_dims(set, type: isl_dim_set, first: depth, n: 1);
2426
2427	return set;
2428	}
2429
2430	/* Eliminate dimensions inner to the current dimension as well as
2431	* unknown divs and divs that depend on the current dimension.
2432	* The result then consists only of constraints that are independent
2433	* of the current dimension and upper and lower bounds on the current
2434	* dimension.
2435	*/
2436	__isl_give isl_set *isl_ast_build_eliminate(
2437	__isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2438	{
2439	domain = isl_ast_build_eliminate_inner(build, set: domain);
2440	domain = isl_ast_build_eliminate_divs(build, set: domain);
2441	return domain;
2442	}
2443
2444	/* Replace build->single_valued by "sv".
2445	*/
2446	__isl_give isl_ast_build *isl_ast_build_set_single_valued(
2447	__isl_take isl_ast_build *build, int sv)
2448	{
2449	if (!build)
2450	return build;
2451	if (build->single_valued == sv)
2452	return build;
2453	build = isl_ast_build_cow(build);
2454	if (!build)
2455	return build;
2456	build->single_valued = sv;
2457
2458	return build;
2459	}
2460