1	/*
2	* Copyright 2005-2007 Universiteit Leiden
3	* Copyright 2008-2009 Katholieke Universiteit Leuven
4	* Copyright 2010 INRIA Saclay
5	* Copyright 2012 Universiteit Leiden
6	* Copyright 2014 Ecole Normale Superieure
7	*
8	* Use of this software is governed by the MIT license
9	*
10	* Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
11	* Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
12	* and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
13	* B-3001 Leuven, Belgium
14	* and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
15	* ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
16	* and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
17	*/
18
19	#include <isl/val.h>
20	#include <isl/space.h>
21	#include <isl/set.h>
22	#include <isl/map.h>
23	#include <isl/union_set.h>
24	#include <isl/union_map.h>
25	#include <isl/flow.h>
26	#include <isl/schedule_node.h>
27	#include <isl_sort.h>
28	#include <isl/stream.h>
29
30	enum isl_restriction_type {
31	isl_restriction_type_empty,
32	isl_restriction_type_none,
33	isl_restriction_type_input,
34	isl_restriction_type_output
35	};
36
37	struct isl_restriction {
38	enum isl_restriction_type type;
39
40	isl_set *source;
41	isl_set *sink;
42	};
43
44	/* Create a restriction of the given type.
45	*/
46	static __isl_give isl_restriction *isl_restriction_alloc(
47	__isl_take isl_map *source_map, enum isl_restriction_type type)
48	{
49	isl_ctx *ctx;
50	isl_restriction *restr;
51
52	if (!source_map)
53	return NULL;
54
55	ctx = isl_map_get_ctx(map: source_map);
56	restr = isl_calloc_type(ctx, struct isl_restriction);
57	if (!restr)
58	goto error;
59
60	restr->type = type;
61
62	isl_map_free(map: source_map);
63	return restr;
64	error:
65	isl_map_free(map: source_map);
66	return NULL;
67	}
68
69	/* Create a restriction that doesn't restrict anything.
70	*/
71	__isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map)
72	{
73	return isl_restriction_alloc(source_map, type: isl_restriction_type_none);
74	}
75
76	/* Create a restriction that removes everything.
77	*/
78	__isl_give isl_restriction *isl_restriction_empty(
79	__isl_take isl_map *source_map)
80	{
81	return isl_restriction_alloc(source_map, type: isl_restriction_type_empty);
82	}
83
84	/* Create a restriction on the input of the maximization problem
85	* based on the given source and sink restrictions.
86	*/
87	__isl_give isl_restriction *isl_restriction_input(
88	__isl_take isl_set *source_restr, __isl_take isl_set *sink_restr)
89	{
90	isl_ctx *ctx;
91	isl_restriction *restr;
92
93	if (!source_restr || !sink_restr)
94	goto error;
95
96	ctx = isl_set_get_ctx(set: source_restr);
97	restr = isl_calloc_type(ctx, struct isl_restriction);
98	if (!restr)
99	goto error;
100
101	restr->type = isl_restriction_type_input;
102	restr->source = source_restr;
103	restr->sink = sink_restr;
104
105	return restr;
106	error:
107	isl_set_free(set: source_restr);
108	isl_set_free(set: sink_restr);
109	return NULL;
110	}
111
112	/* Create a restriction on the output of the maximization problem
113	* based on the given source restriction.
114	*/
115	__isl_give isl_restriction *isl_restriction_output(
116	__isl_take isl_set *source_restr)
117	{
118	isl_ctx *ctx;
119	isl_restriction *restr;
120
121	if (!source_restr)
122	return NULL;
123
124	ctx = isl_set_get_ctx(set: source_restr);
125	restr = isl_calloc_type(ctx, struct isl_restriction);
126	if (!restr)
127	goto error;
128
129	restr->type = isl_restriction_type_output;
130	restr->source = source_restr;
131
132	return restr;
133	error:
134	isl_set_free(set: source_restr);
135	return NULL;
136	}
137
138	__isl_null isl_restriction *isl_restriction_free(
139	__isl_take isl_restriction *restr)
140	{
141	if (!restr)
142	return NULL;
143
144	isl_set_free(set: restr->source);
145	isl_set_free(set: restr->sink);
146	free(ptr: restr);
147	return NULL;
148	}
149
150	isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr)
151	{
152	return restr ? isl_set_get_ctx(set: restr->source) : NULL;
153	}
154
155	/* A private structure to keep track of a mapping together with
156	* a user-specified identifier and a boolean indicating whether
157	* the map represents a must or may access/dependence.
158	*/
159	struct isl_labeled_map {
160	struct isl_map *map;
161	void *data;
162	int must;
163	};
164
165	typedef isl_bool (*isl_access_coscheduled)(void *first, void *second);
166
167	/* A structure containing the input for dependence analysis:
168	* - a sink
169	* - n_must + n_may (<= max_source) sources
170	* - a function for determining the relative order of sources and sink
171	* - an optional function "coscheduled" for determining whether sources
172	* may be coscheduled. If "coscheduled" is NULL, then the sources
173	* are assumed not to be coscheduled.
174	* The must sources are placed before the may sources.
175	*
176	* domain_map is an auxiliary map that maps the sink access relation
177	* to the domain of this access relation.
178	* This field is only needed when restrict_fn is set and
179	* the field itself is set by isl_access_info_compute_flow.
180	*
181	* restrict_fn is a callback that (if not NULL) will be called
182	* right before any lexicographical maximization.
183	*/
184	struct isl_access_info {
185	isl_map *domain_map;
186	struct isl_labeled_map sink;
187	isl_access_level_before level_before;
188	isl_access_coscheduled coscheduled;
189
190	isl_access_restrict restrict_fn;
191	void *restrict_user;
192
193	int max_source;
194	int n_must;
195	int n_may;
196	struct isl_labeled_map source[1];
197	};
198
199	/* A structure containing the output of dependence analysis:
200	* - n_source dependences
201	* - a wrapped subset of the sink for which definitely no source could be found
202	* - a wrapped subset of the sink for which possibly no source could be found
203	*/
204	struct isl_flow {
205	isl_set *must_no_source;
206	isl_set *may_no_source;
207	int n_source;
208	struct isl_labeled_map *dep;
209	};
210
211	/* Construct an isl_access_info structure and fill it up with
212	* the given data. The number of sources is set to 0.
213	*/
214	__isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink,
215	void *sink_user, isl_access_level_before fn, int max_source)
216	{
217	isl_ctx *ctx;
218	struct isl_access_info *acc;
219
220	if (!sink)
221	return NULL;
222
223	ctx = isl_map_get_ctx(map: sink);
224	isl_assert(ctx, max_source >= 0, goto error);
225
226	acc = isl_calloc(ctx, struct isl_access_info,
227	sizeof(struct isl_access_info) +
228	(max_source - 1) * sizeof(struct isl_labeled_map));
229	if (!acc)
230	goto error;
231
232	acc->sink.map = sink;
233	acc->sink.data = sink_user;
234	acc->level_before = fn;
235	acc->max_source = max_source;
236	acc->n_must = 0;
237	acc->n_may = 0;
238
239	return acc;
240	error:
241	isl_map_free(map: sink);
242	return NULL;
243	}
244
245	/* Free the given isl_access_info structure.
246	*/
247	__isl_null isl_access_info *isl_access_info_free(
248	__isl_take isl_access_info *acc)
249	{
250	int i;
251
252	if (!acc)
253	return NULL;
254	isl_map_free(map: acc->domain_map);
255	isl_map_free(map: acc->sink.map);
256	for (i = 0; i < acc->n_must + acc->n_may; ++i)
257	isl_map_free(map: acc->source[i].map);
258	free(ptr: acc);
259	return NULL;
260	}
261
262	isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)
263	{
264	return acc ? isl_map_get_ctx(map: acc->sink.map) : NULL;
265	}
266
267	__isl_give isl_access_info *isl_access_info_set_restrict(
268	__isl_take isl_access_info *acc, isl_access_restrict fn, void *user)
269	{
270	if (!acc)
271	return NULL;
272	acc->restrict_fn = fn;
273	acc->restrict_user = user;
274	return acc;
275	}
276
277	/* Add another source to an isl_access_info structure, making
278	* sure the "must" sources are placed before the "may" sources.
279	* This function may be called at most max_source times on a
280	* given isl_access_info structure, with max_source as specified
281	* in the call to isl_access_info_alloc that constructed the structure.
282	*/
283	__isl_give isl_access_info *isl_access_info_add_source(
284	__isl_take isl_access_info *acc, __isl_take isl_map *source,
285	int must, void *source_user)
286	{
287	isl_ctx *ctx;
288
289	if (!acc)
290	goto error;
291	ctx = isl_map_get_ctx(map: acc->sink.map);
292	isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
293
294	if (must) {
295	if (acc->n_may)
296	acc->source[acc->n_must + acc->n_may] =
297	acc->source[acc->n_must];
298	acc->source[acc->n_must].map = source;
299	acc->source[acc->n_must].data = source_user;
300	acc->source[acc->n_must].must = 1;
301	acc->n_must++;
302	} else {
303	acc->source[acc->n_must + acc->n_may].map = source;
304	acc->source[acc->n_must + acc->n_may].data = source_user;
305	acc->source[acc->n_must + acc->n_may].must = 0;
306	acc->n_may++;
307	}
308
309	return acc;
310	error:
311	isl_map_free(map: source);
312	isl_access_info_free(acc);
313	return NULL;
314	}
315
316	/* A helper struct carrying the isl_access_info and an error condition.
317	*/
318	struct access_sort_info {
319	isl_access_info *access_info;
320	int error;
321	};
322
323	/* Return -n, 0 or n (with n a positive value), depending on whether
324	* the source access identified by p1 should be sorted before, together
325	* or after that identified by p2.
326	*
327	* If p1 appears before p2, then it should be sorted first.
328	* For more generic initial schedules, it is possible that neither
329	* p1 nor p2 appears before the other, or at least not in any obvious way.
330	* We therefore also check if p2 appears before p1, in which case p2
331	* should be sorted first.
332	* If not, we try to order the two statements based on the description
333	* of the iteration domains. This results in an arbitrary, but fairly
334	* stable ordering.
335	*
336	* In case of an error, sort_info.error is set to true and all elements are
337	* reported to be equal.
338	*/
339	static int access_sort_cmp(const void *p1, const void *p2, void *user)
340	{
341	struct access_sort_info *sort_info = user;
342	isl_access_info *acc = sort_info->access_info;
343
344	if (sort_info->error)
345	return 0;
346
347	const struct isl_labeled_map *i1, *i2;
348	int level1, level2;
349	uint32_t h1, h2;
350	i1 = (const struct isl_labeled_map *) p1;
351	i2 = (const struct isl_labeled_map *) p2;
352
353	level1 = acc->level_before(i1->data, i2->data);
354	if (level1 < 0)
355	goto error;
356	if (level1 % 2)
357	return -1;
358
359	level2 = acc->level_before(i2->data, i1->data);
360	if (level2 < 0)
361	goto error;
362	if (level2 % 2)
363	return 1;
364
365	h1 = isl_map_get_hash(map: i1->map);
366	h2 = isl_map_get_hash(map: i2->map);
367	return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
368	error:
369	sort_info->error = 1;
370	return 0;
371	}
372
373	/* Sort the must source accesses in their textual order.
374	*/
375	static __isl_give isl_access_info *isl_access_info_sort_sources(
376	__isl_take isl_access_info *acc)
377	{
378	struct access_sort_info sort_info;
379
380	sort_info.access_info = acc;
381	sort_info.error = 0;
382
383	if (!acc)
384	return NULL;
385	if (acc->n_must <= 1)
386	return acc;
387
388	if (isl_sort(pbase: acc->source, total_elems: acc->n_must, size: sizeof(struct isl_labeled_map),
389	cmp: access_sort_cmp, arg: &sort_info) < 0)
390	return isl_access_info_free(acc);
391	if (sort_info.error)
392	return isl_access_info_free(acc);
393
394	return acc;
395	}
396
397	/* Align the parameters of the two spaces if needed and then call
398	* isl_space_join.
399	*/
400	static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left,
401	__isl_take isl_space *right)
402	{
403	isl_bool equal_params;
404
405	equal_params = isl_space_has_equal_params(space1: left, space2: right);
406	if (equal_params < 0)
407	goto error;
408	if (equal_params)
409	return isl_space_join(left, right);
410
411	left = isl_space_align_params(space1: left, space2: isl_space_copy(space: right));
412	right = isl_space_align_params(space1: right, space2: isl_space_copy(space: left));
413	return isl_space_join(left, right);
414	error:
415	isl_space_free(space: left);
416	isl_space_free(space: right);
417	return NULL;
418	}
419
420	/* Initialize an empty isl_flow structure corresponding to a given
421	* isl_access_info structure.
422	* For each must access, two dependences are created (initialized
423	* to the empty relation), one for the resulting must dependences
424	* and one for the resulting may dependences. May accesses can
425	* only lead to may dependences, so only one dependence is created
426	* for each of them.
427	* This function is private as isl_flow structures are only supposed
428	* to be created by isl_access_info_compute_flow.
429	*/
430	static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)
431	{
432	int i, n;
433	struct isl_ctx *ctx;
434	struct isl_flow *dep;
435
436	if (!acc)
437	return NULL;
438
439	ctx = isl_map_get_ctx(map: acc->sink.map);
440	dep = isl_calloc_type(ctx, struct isl_flow);
441	if (!dep)
442	return NULL;
443
444	n = 2 * acc->n_must + acc->n_may;
445	dep->dep = isl_calloc_array(ctx, struct isl_labeled_map, n);
446	if (n && !dep->dep)
447	goto error;
448
449	dep->n_source = n;
450	for (i = 0; i < acc->n_must; ++i) {
451	isl_space *space;
452	space = space_align_and_join(
453	left: isl_map_get_space(map: acc->source[i].map),
454	right: isl_space_reverse(space: isl_map_get_space(map: acc->sink.map)));
455	dep->dep[2 * i].map = isl_map_empty(space);
456	dep->dep[2 * i + 1].map = isl_map_copy(map: dep->dep[2 * i].map);
457	dep->dep[2 * i].data = acc->source[i].data;
458	dep->dep[2 * i + 1].data = acc->source[i].data;
459	dep->dep[2 * i].must = 1;
460	dep->dep[2 * i + 1].must = 0;
461	if (!dep->dep[2 * i].map || !dep->dep[2 * i + 1].map)
462	goto error;
463	}
464	for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {
465	isl_space *space;
466	space = space_align_and_join(
467	left: isl_map_get_space(map: acc->source[i].map),
468	right: isl_space_reverse(space: isl_map_get_space(map: acc->sink.map)));
469	dep->dep[acc->n_must + i].map = isl_map_empty(space);
470	dep->dep[acc->n_must + i].data = acc->source[i].data;
471	dep->dep[acc->n_must + i].must = 0;
472	if (!dep->dep[acc->n_must + i].map)
473	goto error;
474	}
475
476	return dep;
477	error:
478	isl_flow_free(deps: dep);
479	return NULL;
480	}
481
482	/* Iterate over all sources and for each resulting flow dependence
483	* that is not empty, call the user specfied function.
484	* The second argument in this function call identifies the source,
485	* while the third argument correspond to the final argument of
486	* the isl_flow_foreach call.
487	*/
488	isl_stat isl_flow_foreach(__isl_keep isl_flow *deps,
489	isl_stat (*fn)(__isl_take isl_map *dep, int must, void *dep_user,
490	void *user),
491	void *user)
492	{
493	int i;
494
495	if (!deps)
496	return isl_stat_error;
497
498	for (i = 0; i < deps->n_source; ++i) {
499	if (isl_map_plain_is_empty(map: deps->dep[i].map))
500	continue;
501	if (fn(isl_map_copy(map: deps->dep[i].map), deps->dep[i].must,
502	deps->dep[i].data, user) < 0)
503	return isl_stat_error;
504	}
505
506	return isl_stat_ok;
507	}
508
509	/* Return a copy of the subset of the sink for which no source could be found.
510	*/
511	__isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
512	{
513	if (!deps)
514	return NULL;
515
516	if (must)
517	return isl_set_unwrap(set: isl_set_copy(set: deps->must_no_source));
518	else
519	return isl_set_unwrap(set: isl_set_copy(set: deps->may_no_source));
520	}
521
522	__isl_null isl_flow *isl_flow_free(__isl_take isl_flow *deps)
523	{
524	int i;
525
526	if (!deps)
527	return NULL;
528	isl_set_free(set: deps->must_no_source);
529	isl_set_free(set: deps->may_no_source);
530	if (deps->dep) {
531	for (i = 0; i < deps->n_source; ++i)
532	isl_map_free(map: deps->dep[i].map);
533	free(ptr: deps->dep);
534	}
535	free(ptr: deps);
536
537	return NULL;
538	}
539
540	isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
541	{
542	return deps ? isl_set_get_ctx(set: deps->must_no_source) : NULL;
543	}
544
545	/* Return a map that enforces that the domain iteration occurs after
546	* the range iteration at the given level.
547	* If level is odd, then the domain iteration should occur after
548	* the target iteration in their shared level/2 outermost loops.
549	* In this case we simply need to enforce that these outermost
550	* loop iterations are the same.
551	* If level is even, then the loop iterator of the domain should
552	* be greater than the loop iterator of the range at the last
553	* of the level/2 shared loops, i.e., loop level/2 - 1.
554	*/
555	static __isl_give isl_map *after_at_level(__isl_take isl_space *space,
556	int level)
557	{
558	struct isl_basic_map *bmap;
559
560	if (level % 2)
561	bmap = isl_basic_map_equal(space, n_equal: level/2);
562	else
563	bmap = isl_basic_map_more_at(space, pos: level/2 - 1);
564
565	return isl_map_from_basic_map(bmap);
566	}
567
568	/* Compute the partial lexicographic maximum of "dep" on domain "sink",
569	* but first check if the user has set acc->restrict_fn and if so
570	* update either the input or the output of the maximization problem
571	* with respect to the resulting restriction.
572	*
573	* Since the user expects a mapping from sink iterations to source iterations,
574	* whereas the domain of "dep" is a wrapped map, mapping sink iterations
575	* to accessed array elements, we first need to project out the accessed
576	* sink array elements by applying acc->domain_map.
577	* Similarly, the sink restriction specified by the user needs to be
578	* converted back to the wrapped map.
579	*/
580	static __isl_give isl_map *restricted_partial_lexmax(
581	__isl_keep isl_access_info *acc, __isl_take isl_map *dep,
582	int source, __isl_take isl_set *sink, __isl_give isl_set **empty)
583	{
584	isl_map *source_map;
585	isl_restriction *restr;
586	isl_set *sink_domain;
587	isl_set *sink_restr;
588	isl_map *res;
589
590	if (!acc->restrict_fn)
591	return isl_map_partial_lexmax(map: dep, dom: sink, empty);
592
593	source_map = isl_map_copy(map: dep);
594	source_map = isl_map_apply_domain(map1: source_map,
595	map2: isl_map_copy(map: acc->domain_map));
596	sink_domain = isl_set_copy(set: sink);
597	sink_domain = isl_set_apply(set: sink_domain, map: isl_map_copy(map: acc->domain_map));
598	restr = acc->restrict_fn(source_map, sink_domain,
599	acc->source[source].data, acc->restrict_user);
600	isl_set_free(set: sink_domain);
601	isl_map_free(map: source_map);
602
603	if (!restr)
604	goto error;
605	if (restr->type == isl_restriction_type_input) {
606	dep = isl_map_intersect_range(map: dep, set: isl_set_copy(set: restr->source));
607	sink_restr = isl_set_copy(set: restr->sink);
608	sink_restr = isl_set_apply(set: sink_restr,
609	map: isl_map_reverse(map: isl_map_copy(map: acc->domain_map)));
610	sink = isl_set_intersect(set1: sink, set2: sink_restr);
611	} else if (restr->type == isl_restriction_type_empty) {
612	isl_space *space = isl_map_get_space(map: dep);
613	isl_map_free(map: dep);
614	dep = isl_map_empty(space);
615	}
616
617	res = isl_map_partial_lexmax(map: dep, dom: sink, empty);
618
619	if (restr->type == isl_restriction_type_output)
620	res = isl_map_intersect_range(map: res, set: isl_set_copy(set: restr->source));
621
622	isl_restriction_free(restr);
623	return res;
624	error:
625	isl_map_free(map: dep);
626	isl_set_free(set: sink);
627	*empty = NULL;
628	return NULL;
629	}
630
631	/* Compute the last iteration of must source j that precedes the sink
632	* at the given level for sink iterations in set_C.
633	* The subset of set_C for which no such iteration can be found is returned
634	* in *empty.
635	*/
636	static struct isl_map *last_source(struct isl_access_info *acc,
637	struct isl_set *set_C,
638	int j, int level, struct isl_set **empty)
639	{
640	struct isl_map *read_map;
641	struct isl_map *write_map;
642	struct isl_map *dep_map;
643	struct isl_map *after;
644	struct isl_map *result;
645
646	read_map = isl_map_copy(map: acc->sink.map);
647	write_map = isl_map_copy(map: acc->source[j].map);
648	write_map = isl_map_reverse(map: write_map);
649	dep_map = isl_map_apply_range(map1: read_map, map2: write_map);
650	after = after_at_level(space: isl_map_get_space(map: dep_map), level);
651	dep_map = isl_map_intersect(map1: dep_map, map2: after);
652	result = restricted_partial_lexmax(acc, dep: dep_map, source: j, sink: set_C, empty);
653	result = isl_map_reverse(map: result);
654
655	return result;
656	}
657
658	/* For a given mapping between iterations of must source j and iterations
659	* of the sink, compute the last iteration of must source k preceding
660	* the sink at level before_level for any of the sink iterations,
661	* but following the corresponding iteration of must source j at level
662	* after_level.
663	*/
664	static struct isl_map *last_later_source(struct isl_access_info *acc,
665	struct isl_map *old_map,
666	int j, int before_level,
667	int k, int after_level,
668	struct isl_set **empty)
669	{
670	isl_space *space;
671	struct isl_set *set_C;
672	struct isl_map *read_map;
673	struct isl_map *write_map;
674	struct isl_map *dep_map;
675	struct isl_map *after_write;
676	struct isl_map *before_read;
677	struct isl_map *result;
678
679	set_C = isl_map_range(map: isl_map_copy(map: old_map));
680	read_map = isl_map_copy(map: acc->sink.map);
681	write_map = isl_map_copy(map: acc->source[k].map);
682
683	write_map = isl_map_reverse(map: write_map);
684	dep_map = isl_map_apply_range(map1: read_map, map2: write_map);
685	space = space_align_and_join(left: isl_map_get_space(map: acc->source[k].map),
686	right: isl_space_reverse(space: isl_map_get_space(map: acc->source[j].map)));
687	after_write = after_at_level(space, level: after_level);
688	after_write = isl_map_apply_range(map1: after_write, map2: old_map);
689	after_write = isl_map_reverse(map: after_write);
690	dep_map = isl_map_intersect(map1: dep_map, map2: after_write);
691	before_read = after_at_level(space: isl_map_get_space(map: dep_map), level: before_level);
692	dep_map = isl_map_intersect(map1: dep_map, map2: before_read);
693	result = restricted_partial_lexmax(acc, dep: dep_map, source: k, sink: set_C, empty);
694	result = isl_map_reverse(map: result);
695
696	return result;
697	}
698
699	/* Given a shared_level between two accesses, return 1 if the
700	* the first can precede the second at the requested target_level.
701	* If the target level is odd, i.e., refers to a statement level
702	* dimension, then first needs to precede second at the requested
703	* level, i.e., shared_level must be equal to target_level.
704	* If the target level is odd, then the two loops should share
705	* at least the requested number of outer loops.
706	*/
707	static int can_precede_at_level(int shared_level, int target_level)
708	{
709	if (shared_level < target_level)
710	return 0;
711	if ((target_level % 2) && shared_level > target_level)
712	return 0;
713	return 1;
714	}
715
716	/* Given a possible flow dependence temp_rel[j] between source j and the sink
717	* at level sink_level, remove those elements for which
718	* there is an iteration of another source k < j that is closer to the sink.
719	* The flow dependences temp_rel[k] are updated with the improved sources.
720	* Any improved source needs to precede the sink at the same level
721	* and needs to follow source j at the same or a deeper level.
722	* The lower this level, the later the execution date of source k.
723	* We therefore consider lower levels first.
724	*
725	* If temp_rel[j] is empty, then there can be no improvement and
726	* we return immediately.
727	*
728	* This function returns isl_stat_ok in case it was executed successfully and
729	* isl_stat_error in case of errors during the execution of this function.
730	*/
731	static isl_stat intermediate_sources(__isl_keep isl_access_info *acc,
732	struct isl_map **temp_rel, int j, int sink_level)
733	{
734	int k, level;
735	isl_size n_in = isl_map_dim(map: acc->source[j].map, type: isl_dim_in);
736	int depth = 2 * n_in + 1;
737
738	if (n_in < 0)
739	return isl_stat_error;
740	if (isl_map_plain_is_empty(map: temp_rel[j]))
741	return isl_stat_ok;
742
743	for (k = j - 1; k >= 0; --k) {
744	int plevel, plevel2;
745	plevel = acc->level_before(acc->source[k].data, acc->sink.data);
746	if (plevel < 0)
747	return isl_stat_error;
748	if (!can_precede_at_level(shared_level: plevel, target_level: sink_level))
749	continue;
750
751	plevel2 = acc->level_before(acc->source[j].data,
752	acc->source[k].data);
753	if (plevel2 < 0)
754	return isl_stat_error;
755
756	for (level = sink_level; level <= depth; ++level) {
757	struct isl_map *T;
758	struct isl_set *trest;
759	struct isl_map *copy;
760
761	if (!can_precede_at_level(shared_level: plevel2, target_level: level))
762	continue;
763
764	copy = isl_map_copy(map: temp_rel[j]);
765	T = last_later_source(acc, old_map: copy, j, before_level: sink_level, k,
766	after_level: level, empty: &trest);
767	if (isl_map_plain_is_empty(map: T)) {
768	isl_set_free(set: trest);
769	isl_map_free(map: T);
770	continue;
771	}
772	temp_rel[j] = isl_map_intersect_range(map: temp_rel[j], set: trest);
773	temp_rel[k] = isl_map_union_disjoint(map1: temp_rel[k], map2: T);
774	}
775	}
776
777	return isl_stat_ok;
778	}
779
780	/* Compute all iterations of may source j that precedes the sink at the given
781	* level for sink iterations in set_C.
782	*/
783	static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc,
784	__isl_take isl_set *set_C, int j, int level)
785	{
786	isl_map *read_map;
787	isl_map *write_map;
788	isl_map *dep_map;
789	isl_map *after;
790
791	read_map = isl_map_copy(map: acc->sink.map);
792	read_map = isl_map_intersect_domain(map: read_map, set: set_C);
793	write_map = isl_map_copy(map: acc->source[acc->n_must + j].map);
794	write_map = isl_map_reverse(map: write_map);
795	dep_map = isl_map_apply_range(map1: read_map, map2: write_map);
796	after = after_at_level(space: isl_map_get_space(map: dep_map), level);
797	dep_map = isl_map_intersect(map1: dep_map, map2: after);
798
799	return isl_map_reverse(map: dep_map);
800	}
801
802	/* For a given mapping between iterations of must source k and iterations
803	* of the sink, compute all iterations of may source j preceding
804	* the sink at level before_level for any of the sink iterations,
805	* but following the corresponding iteration of must source k at level
806	* after_level.
807	*/
808	static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc,
809	__isl_take isl_map *old_map,
810	int j, int before_level, int k, int after_level)
811	{
812	isl_space *space;
813	isl_set *set_C;
814	isl_map *read_map;
815	isl_map *write_map;
816	isl_map *dep_map;
817	isl_map *after_write;
818	isl_map *before_read;
819
820	set_C = isl_map_range(map: isl_map_copy(map: old_map));
821	read_map = isl_map_copy(map: acc->sink.map);
822	read_map = isl_map_intersect_domain(map: read_map, set: set_C);
823	write_map = isl_map_copy(map: acc->source[acc->n_must + j].map);
824
825	write_map = isl_map_reverse(map: write_map);
826	dep_map = isl_map_apply_range(map1: read_map, map2: write_map);
827	space = isl_space_join(left: isl_map_get_space(
828	map: acc->source[acc->n_must + j].map),
829	right: isl_space_reverse(space: isl_map_get_space(map: acc->source[k].map)));
830	after_write = after_at_level(space, level: after_level);
831	after_write = isl_map_apply_range(map1: after_write, map2: old_map);
832	after_write = isl_map_reverse(map: after_write);
833	dep_map = isl_map_intersect(map1: dep_map, map2: after_write);
834	before_read = after_at_level(space: isl_map_get_space(map: dep_map), level: before_level);
835	dep_map = isl_map_intersect(map1: dep_map, map2: before_read);
836	return isl_map_reverse(map: dep_map);
837	}
838
839	/* Given the must and may dependence relations for the must accesses
840	* for level sink_level, check if there are any accesses of may access j
841	* that occur in between and return their union.
842	* If some of these accesses are intermediate with respect to
843	* (previously thought to be) must dependences, then these
844	* must dependences are turned into may dependences.
845	*/
846	static __isl_give isl_map *all_intermediate_sources(
847	__isl_keep isl_access_info *acc, __isl_take isl_map *map,
848	struct isl_map **must_rel, struct isl_map **may_rel,
849	int j, int sink_level)
850	{
851	int k, level;
852	isl_size n_in = isl_map_dim(map: acc->source[acc->n_must + j].map,
853	type: isl_dim_in);
854	int depth = 2 * n_in + 1;
855
856	if (n_in < 0)
857	return isl_map_free(map);
858	for (k = 0; k < acc->n_must; ++k) {
859	int plevel;
860
861	if (isl_map_plain_is_empty(map: may_rel[k]) &&
862	isl_map_plain_is_empty(map: must_rel[k]))
863	continue;
864
865	plevel = acc->level_before(acc->source[k].data,
866	acc->source[acc->n_must + j].data);
867	if (plevel < 0)
868	return isl_map_free(map);
869
870	for (level = sink_level; level <= depth; ++level) {
871	isl_map *T;
872	isl_map *copy;
873	isl_set *ran;
874
875	if (!can_precede_at_level(shared_level: plevel, target_level: level))
876	continue;
877
878	copy = isl_map_copy(map: may_rel[k]);
879	T = all_later_sources(acc, old_map: copy, j, before_level: sink_level, k, after_level: level);
880	map = isl_map_union(map1: map, map2: T);
881
882	copy = isl_map_copy(map: must_rel[k]);
883	T = all_later_sources(acc, old_map: copy, j, before_level: sink_level, k, after_level: level);
884	ran = isl_map_range(map: isl_map_copy(map: T));
885	map = isl_map_union(map1: map, map2: T);
886	may_rel[k] = isl_map_union_disjoint(map1: may_rel[k],
887	map2: isl_map_intersect_range(map: isl_map_copy(map: must_rel[k]),
888	set: isl_set_copy(set: ran)));
889	T = isl_map_from_domain_and_range(
890	domain: isl_set_universe(
891	space: isl_space_domain(space: isl_map_get_space(map: must_rel[k]))),
892	range: ran);
893	must_rel[k] = isl_map_subtract(map1: must_rel[k], map2: T);
894	}
895	}
896
897	return map;
898	}
899
900	/* Given a dependence relation "old_map" between a must-source and the sink,
901	* return a subset of the dependences, augmented with instances
902	* of the source at position "pos" in "acc" that are coscheduled
903	* with the must-source and that access the same element.
904	* That is, if the input lives in a space T -> K, then the output
905	* lives in the space [T -> S] -> K, with S the space of source "pos", and
906	* the domain factor of the domain product is a subset of the input.
907	* The sources are considered to be coscheduled if they have the same values
908	* for the initial "depth" coordinates.
909	*
910	* First construct a dependence relation S -> K and a mapping
911	* between coscheduled sources T -> S.
912	* The second is combined with the original dependence relation T -> K
913	* to form a relation in T -> [S -> K], which is subsequently
914	* uncurried to [T -> S] -> K.
915	* This result is then intersected with the dependence relation S -> K
916	* to form the output.
917	*
918	* In case a negative depth is given, NULL is returned to indicate an error.
919	*/
920	static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
921	__isl_keep isl_map *old_map, int pos, int depth)
922	{
923	isl_space *space;
924	isl_set *set_C;
925	isl_map *read_map;
926	isl_map *write_map;
927	isl_map *dep_map;
928	isl_map *equal;
929	isl_map *map;
930
931	if (depth < 0)
932	return NULL;
933
934	set_C = isl_map_range(map: isl_map_copy(map: old_map));
935	read_map = isl_map_copy(map: acc->sink.map);
936	read_map = isl_map_intersect_domain(map: read_map, set: set_C);
937	write_map = isl_map_copy(map: acc->source[pos].map);
938	dep_map = isl_map_domain_product(map1: write_map, map2: read_map);
939	dep_map = isl_set_unwrap(set: isl_map_domain(bmap: dep_map));
940	space = isl_space_join(left: isl_map_get_space(map: old_map),
941	right: isl_space_reverse(space: isl_map_get_space(map: dep_map)));
942	equal = isl_map_from_basic_map(bmap: isl_basic_map_equal(space, n_equal: depth));
943	map = isl_map_range_product(map1: equal, map2: isl_map_copy(map: old_map));
944	map = isl_map_uncurry(map);
945	map = isl_map_intersect_domain_factor_range(map, factor: dep_map);
946
947	return map;
948	}
949
950	/* After the dependences derived from a must-source have been computed
951	* at a certain level, check if any of the sources of the must-dependences
952	* may be coscheduled with other sources.
953	* If they are any such sources, then there is no way of determining
954	* which of the sources actually comes last and the must-dependences
955	* need to be turned into may-dependences, while dependences from
956	* the other sources need to be added to the may-dependences as well.
957	* "acc" describes the sources and a callback for checking whether
958	* two sources may be coscheduled. If acc->coscheduled is NULL then
959	* the sources are assumed not to be coscheduled.
960	* "must_rel" and "may_rel" describe the must and may-dependence relations
961	* computed at the current level for the must-sources. Some of the dependences
962	* may be moved from "must_rel" to "may_rel".
963	* "flow" contains all dependences computed so far (apart from those
964	* in "must_rel" and "may_rel") and may be updated with additional
965	* dependences derived from may-sources.
966	*
967	* In particular, consider all the must-sources with a non-empty
968	* dependence relation in "must_rel". They are considered in reverse
969	* order because that is the order in which they are considered in the caller.
970	* If any of the must-sources are coscheduled, then the last one
971	* is the one that will have a corresponding dependence relation.
972	* For each must-source i, consider both all the previous must-sources
973	* and all the may-sources. If any of those may be coscheduled with
974	* must-source i, then compute the coscheduled instances that access
975	* the same memory elements. The result is a relation [T -> S] -> K.
976	* The projection onto T -> K is a subset of the must-dependence relation
977	* that needs to be turned into may-dependences.
978	* The projection onto S -> K needs to be added to the may-dependences
979	* of source S.
980	* Since a given must-source instance may be coscheduled with several
981	* other source instances, the dependences that need to be turned
982	* into may-dependences are first collected and only actually removed
983	* from the must-dependences after all other sources have been considered.
984	*/
985	static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc,
986	__isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel,
987	__isl_take isl_flow *flow)
988	{
989	int i, j;
990
991	if (!acc->coscheduled)
992	return flow;
993	for (i = acc->n_must - 1; i >= 0; --i) {
994	isl_map *move;
995
996	if (isl_map_plain_is_empty(map: must_rel[i]))
997	continue;
998	move = isl_map_empty(space: isl_map_get_space(map: must_rel[i]));
999	for (j = i - 1; j >= 0; --j) {
1000	int depth;
1001	isl_bool coscheduled;
1002	isl_map *map, *factor;
1003
1004	coscheduled = acc->coscheduled(acc->source[i].data,
1005	acc->source[j].data);
1006	if (coscheduled < 0) {
1007	isl_map_free(map: move);
1008	return isl_flow_free(deps: flow);
1009	}
1010	if (!coscheduled)
1011	continue;
1012	depth = acc->level_before(acc->source[i].data,
1013	acc->source[j].data) / 2;
1014	map = coscheduled_source(acc, old_map: must_rel[i], pos: j, depth);
1015	factor = isl_map_domain_factor_range(map: isl_map_copy(map));
1016	may_rel[j] = isl_map_union(map1: may_rel[j], map2: factor);
1017	map = isl_map_domain_factor_domain(map);
1018	move = isl_map_union(map1: move, map2: map);
1019	}
1020	for (j = 0; j < acc->n_may; ++j) {
1021	int depth, pos;
1022	isl_bool coscheduled;
1023	isl_map *map, *factor;
1024
1025	pos = acc->n_must + j;
1026	coscheduled = acc->coscheduled(acc->source[i].data,
1027	acc->source[pos].data);
1028	if (coscheduled < 0) {
1029	isl_map_free(map: move);
1030	return isl_flow_free(deps: flow);
1031	}
1032	if (!coscheduled)
1033	continue;
1034	depth = acc->level_before(acc->source[i].data,
1035	acc->source[pos].data) / 2;
1036	map = coscheduled_source(acc, old_map: must_rel[i], pos, depth);
1037	factor = isl_map_domain_factor_range(map: isl_map_copy(map));
1038	pos = 2 * acc->n_must + j;
1039	flow->dep[pos].map = isl_map_union(map1: flow->dep[pos].map,
1040	map2: factor);
1041	map = isl_map_domain_factor_domain(map);
1042	move = isl_map_union(map1: move, map2: map);
1043	}
1044	must_rel[i] = isl_map_subtract(map1: must_rel[i], map2: isl_map_copy(map: move));
1045	may_rel[i] = isl_map_union(map1: may_rel[i], map2: move);
1046	}
1047
1048	return flow;
1049	}
1050
1051	/* Compute dependences for the case where all accesses are "may"
1052	* accesses, which boils down to computing memory based dependences.
1053	* The generic algorithm would also work in this case, but it would
1054	* be overkill to use it.
1055	*/
1056	static __isl_give isl_flow *compute_mem_based_dependences(
1057	__isl_keep isl_access_info *acc)
1058	{
1059	int i;
1060	isl_set *mustdo;
1061	isl_set *maydo;
1062	isl_flow *res;
1063
1064	res = isl_flow_alloc(acc);
1065	if (!res)
1066	return NULL;
1067
1068	mustdo = isl_map_domain(bmap: isl_map_copy(map: acc->sink.map));
1069	maydo = isl_set_copy(set: mustdo);
1070
1071	for (i = 0; i < acc->n_may; ++i) {
1072	int plevel;
1073	int is_before;
1074	isl_space *space;
1075	isl_map *before;
1076	isl_map *dep;
1077
1078	plevel = acc->level_before(acc->source[i].data, acc->sink.data);
1079	if (plevel < 0)
1080	goto error;
1081
1082	is_before = plevel & 1;
1083	plevel >>= 1;
1084
1085	space = isl_map_get_space(map: res->dep[i].map);
1086	if (is_before)
1087	before = isl_map_lex_le_first(space, n: plevel);
1088	else
1089	before = isl_map_lex_lt_first(space, n: plevel);
1090	dep = isl_map_apply_range(map1: isl_map_copy(map: acc->source[i].map),
1091	map2: isl_map_reverse(map: isl_map_copy(map: acc->sink.map)));
1092	dep = isl_map_intersect(map1: dep, map2: before);
1093	mustdo = isl_set_subtract(set1: mustdo,
1094	set2: isl_map_range(map: isl_map_copy(map: dep)));
1095	res->dep[i].map = isl_map_union(map1: res->dep[i].map, map2: dep);
1096	}
1097
1098	res->may_no_source = isl_set_subtract(set1: maydo, set2: isl_set_copy(set: mustdo));
1099	res->must_no_source = mustdo;
1100
1101	return res;
1102	error:
1103	isl_set_free(set: mustdo);
1104	isl_set_free(set: maydo);
1105	isl_flow_free(deps: res);
1106	return NULL;
1107	}
1108
1109	/* Compute dependences for the case where there is at least one
1110	* "must" access.
1111	*
1112	* The core algorithm considers all levels in which a source may precede
1113	* the sink, where a level may either be a statement level or a loop level.
1114	* The outermost statement level is 1, the first loop level is 2, etc...
1115	* The algorithm basically does the following:
1116	* for all levels l of the read access from innermost to outermost
1117	* for all sources w that may precede the sink access at that level
1118	* compute the last iteration of the source that precedes the sink access
1119	* at that level
1120	* add result to possible last accesses at level l of source w
1121	* for all sources w2 that we haven't considered yet at this level that may
1122	* also precede the sink access
1123	* for all levels l2 of w from l to innermost
1124	* for all possible last accesses dep of w at l
1125	* compute last iteration of w2 between the source and sink
1126	* of dep
1127	* add result to possible last accesses at level l of write w2
1128	* and replace possible last accesses dep by the remainder
1129	*
1130	*
1131	* The above algorithm is applied to the must access. During the course
1132	* of the algorithm, we keep track of sink iterations that still
1133	* need to be considered. These iterations are split into those that
1134	* haven't been matched to any source access (mustdo) and those that have only
1135	* been matched to may accesses (maydo).
1136	* At the end of each level, must-sources and may-sources that are coscheduled
1137	* with the sources of the must-dependences at that level are considered.
1138	* If any coscheduled instances are found, then corresponding may-dependences
1139	* are added and the original must-dependences are turned into may-dependences.
1140	* Afterwards, the may accesses that occur after must-dependence sources
1141	* are considered.
1142	* In particular, we consider may accesses that precede the remaining
1143	* sink iterations, moving elements from mustdo to maydo when appropriate,
1144	* and may accesses that occur between a must source and a sink of any
1145	* dependences found at the current level, turning must dependences into
1146	* may dependences when appropriate.
1147	*
1148	*/
1149	static __isl_give isl_flow *compute_val_based_dependences(
1150	__isl_keep isl_access_info *acc)
1151	{
1152	isl_ctx *ctx;
1153	isl_flow *res;
1154	isl_set *mustdo = NULL;
1155	isl_set *maydo = NULL;
1156	int level, j;
1157	isl_size n_in;
1158	int depth;
1159	isl_map **must_rel = NULL;
1160	isl_map **may_rel = NULL;
1161
1162	if (!acc)
1163	return NULL;
1164
1165	res = isl_flow_alloc(acc);
1166	if (!res)
1167	goto error;
1168	ctx = isl_map_get_ctx(map: acc->sink.map);
1169
1170	n_in = isl_map_dim(map: acc->sink.map, type: isl_dim_in);
1171	if (n_in < 0)
1172	goto error;
1173	depth = 2 * n_in + 1;
1174	mustdo = isl_map_domain(bmap: isl_map_copy(map: acc->sink.map));
1175	maydo = isl_set_empty(space: isl_set_get_space(set: mustdo));
1176	if (!mustdo || !maydo)
1177	goto error;
1178	if (isl_set_plain_is_empty(set: mustdo))
1179	goto done;
1180
1181	must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1182	may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1183	if (!must_rel || !may_rel)
1184	goto error;
1185
1186	for (level = depth; level >= 1; --level) {
1187	for (j = acc->n_must-1; j >=0; --j) {
1188	isl_space *space;
1189	space = isl_map_get_space(map: res->dep[2 * j].map);
1190	must_rel[j] = isl_map_empty(space);
1191	may_rel[j] = isl_map_copy(map: must_rel[j]);
1192	}
1193
1194	for (j = acc->n_must - 1; j >= 0; --j) {
1195	struct isl_map *T;
1196	struct isl_set *rest;
1197	int plevel;
1198
1199	plevel = acc->level_before(acc->source[j].data,
1200	acc->sink.data);
1201	if (plevel < 0)
1202	goto error;
1203	if (!can_precede_at_level(shared_level: plevel, target_level: level))
1204	continue;
1205
1206	T = last_source(acc, set_C: mustdo, j, level, empty: &rest);
1207	must_rel[j] = isl_map_union_disjoint(map1: must_rel[j], map2: T);
1208	mustdo = rest;
1209
1210	if (intermediate_sources(acc, temp_rel: must_rel, j, sink_level: level) < 0)
1211	goto error;
1212
1213	T = last_source(acc, set_C: maydo, j, level, empty: &rest);
1214	may_rel[j] = isl_map_union_disjoint(map1: may_rel[j], map2: T);
1215	maydo = rest;
1216
1217	if (intermediate_sources(acc, temp_rel: may_rel, j, sink_level: level) < 0)
1218	goto error;
1219
1220	if (isl_set_plain_is_empty(set: mustdo) &&
1221	isl_set_plain_is_empty(set: maydo))
1222	break;
1223	}
1224	for (j = j - 1; j >= 0; --j) {
1225	int plevel;
1226
1227	plevel = acc->level_before(acc->source[j].data,
1228	acc->sink.data);
1229	if (plevel < 0)
1230	goto error;
1231	if (!can_precede_at_level(shared_level: plevel, target_level: level))
1232	continue;
1233
1234	if (intermediate_sources(acc, temp_rel: must_rel, j, sink_level: level) < 0)
1235	goto error;
1236	if (intermediate_sources(acc, temp_rel: may_rel, j, sink_level: level) < 0)
1237	goto error;
1238	}
1239
1240	res = handle_coscheduled(acc, must_rel, may_rel, flow: res);
1241	if (!res)
1242	goto error;
1243
1244	for (j = 0; j < acc->n_may; ++j) {
1245	int plevel;
1246	isl_map *T;
1247	isl_set *ran;
1248
1249	plevel = acc->level_before(acc->source[acc->n_must + j].data,
1250	acc->sink.data);
1251	if (plevel < 0)
1252	goto error;
1253	if (!can_precede_at_level(shared_level: plevel, target_level: level))
1254	continue;
1255
1256	T = all_sources(acc, set_C: isl_set_copy(set: maydo), j, level);
1257	res->dep[2 * acc->n_must + j].map =
1258	isl_map_union(map1: res->dep[2 * acc->n_must + j].map, map2: T);
1259	T = all_sources(acc, set_C: isl_set_copy(set: mustdo), j, level);
1260	ran = isl_map_range(map: isl_map_copy(map: T));
1261	res->dep[2 * acc->n_must + j].map =
1262	isl_map_union(map1: res->dep[2 * acc->n_must + j].map, map2: T);
1263	mustdo = isl_set_subtract(set1: mustdo, set2: isl_set_copy(set: ran));
1264	maydo = isl_set_union_disjoint(set1: maydo, set2: ran);
1265
1266	T = res->dep[2 * acc->n_must + j].map;
1267	T = all_intermediate_sources(acc, map: T, must_rel, may_rel,
1268	j, sink_level: level);
1269	res->dep[2 * acc->n_must + j].map = T;
1270	}
1271
1272	for (j = acc->n_must - 1; j >= 0; --j) {
1273	res->dep[2 * j].map =
1274	isl_map_union_disjoint(map1: res->dep[2 * j].map,
1275	map2: must_rel[j]);
1276	res->dep[2 * j + 1].map =
1277	isl_map_union_disjoint(map1: res->dep[2 * j + 1].map,
1278	map2: may_rel[j]);
1279	}
1280
1281	if (isl_set_plain_is_empty(set: mustdo) &&
1282	isl_set_plain_is_empty(set: maydo))
1283	break;
1284	}
1285
1286	free(ptr: must_rel);
1287	free(ptr: may_rel);
1288	done:
1289	res->must_no_source = mustdo;
1290	res->may_no_source = maydo;
1291	return res;
1292	error:
1293	if (must_rel)
1294	for (j = 0; j < acc->n_must; ++j)
1295	isl_map_free(map: must_rel[j]);
1296	if (may_rel)
1297	for (j = 0; j < acc->n_must; ++j)
1298	isl_map_free(map: may_rel[j]);
1299	isl_flow_free(deps: res);
1300	isl_set_free(set: mustdo);
1301	isl_set_free(set: maydo);
1302	free(ptr: must_rel);
1303	free(ptr: may_rel);
1304	return NULL;
1305	}
1306
1307	/* Given a "sink" access, a list of n "source" accesses,
1308	* compute for each iteration of the sink access
1309	* and for each element accessed by that iteration,
1310	* the source access in the list that last accessed the
1311	* element accessed by the sink access before this sink access.
1312	* Each access is given as a map from the loop iterators
1313	* to the array indices.
1314	* The result is a list of n relations between source and sink
1315	* iterations and a subset of the domain of the sink access,
1316	* corresponding to those iterations that access an element
1317	* not previously accessed.
1318	*
1319	* To deal with multi-valued sink access relations, the sink iteration
1320	* domain is first extended with dimensions that correspond to the data
1321	* space. However, these extra dimensions are not projected out again.
1322	* It is up to the caller to decide whether these dimensions should be kept.
1323	*/
1324	static __isl_give isl_flow *access_info_compute_flow_core(
1325	__isl_take isl_access_info *acc)
1326	{
1327	struct isl_flow *res = NULL;
1328
1329	if (!acc)
1330	return NULL;
1331
1332	acc->sink.map = isl_map_range_map(map: acc->sink.map);
1333	if (!acc->sink.map)
1334	goto error;
1335
1336	if (acc->n_must == 0)
1337	res = compute_mem_based_dependences(acc);
1338	else {
1339	acc = isl_access_info_sort_sources(acc);
1340	res = compute_val_based_dependences(acc);
1341	}
1342	acc = isl_access_info_free(acc);
1343	if (!res)
1344	return NULL;
1345	if (!res->must_no_source || !res->may_no_source)
1346	goto error;
1347	return res;
1348	error:
1349	isl_access_info_free(acc);
1350	isl_flow_free(deps: res);
1351	return NULL;
1352	}
1353
1354	/* Given a "sink" access, a list of n "source" accesses,
1355	* compute for each iteration of the sink access
1356	* and for each element accessed by that iteration,
1357	* the source access in the list that last accessed the
1358	* element accessed by the sink access before this sink access.
1359	* Each access is given as a map from the loop iterators
1360	* to the array indices.
1361	* The result is a list of n relations between source and sink
1362	* iterations and a subset of the domain of the sink access,
1363	* corresponding to those iterations that access an element
1364	* not previously accessed.
1365	*
1366	* To deal with multi-valued sink access relations,
1367	* access_info_compute_flow_core extends the sink iteration domain
1368	* with dimensions that correspond to the data space. These extra dimensions
1369	* are projected out from the result of access_info_compute_flow_core.
1370	*/
1371	__isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)
1372	{
1373	int j;
1374	struct isl_flow *res;
1375
1376	if (!acc)
1377	return NULL;
1378
1379	acc->domain_map = isl_map_domain_map(map: isl_map_copy(map: acc->sink.map));
1380	res = access_info_compute_flow_core(acc);
1381	if (!res)
1382	return NULL;
1383
1384	for (j = 0; j < res->n_source; ++j) {
1385	res->dep[j].map = isl_map_range_factor_domain(map: res->dep[j].map);
1386	if (!res->dep[j].map)
1387	goto error;
1388	}
1389
1390	return res;
1391	error:
1392	isl_flow_free(deps: res);
1393	return NULL;
1394	}
1395
1396
1397	/* Keep track of some information about a schedule for a given
1398	* access. In particular, keep track of which dimensions
1399	* have a constant value and of the actual constant values.
1400	*/
1401	struct isl_sched_info {
1402	int *is_cst;
1403	isl_vec *cst;
1404	};
1405
1406	static void sched_info_free(__isl_take struct isl_sched_info *info)
1407	{
1408	if (!info)
1409	return;
1410	isl_vec_free(vec: info->cst);
1411	free(ptr: info->is_cst);
1412	free(ptr: info);
1413	}
1414
1415	/* Extract information on the constant dimensions of the schedule
1416	* for a given access. The "map" is of the form
1417	*
1418	* [S -> D] -> A
1419	*
1420	* with S the schedule domain, D the iteration domain and A the data domain.
1421	*/
1422	static __isl_give struct isl_sched_info *sched_info_alloc(
1423	__isl_keep isl_map *map)
1424	{
1425	isl_ctx *ctx;
1426	isl_space *space;
1427	struct isl_sched_info *info;
1428	int i;
1429	isl_size n;
1430
1431	if (!map)
1432	return NULL;
1433
1434	space = isl_space_unwrap(space: isl_space_domain(space: isl_map_get_space(map)));
1435	if (!space)
1436	return NULL;
1437	n = isl_space_dim(space, type: isl_dim_in);
1438	isl_space_free(space);
1439	if (n < 0)
1440	return NULL;
1441
1442	ctx = isl_map_get_ctx(map);
1443	info = isl_alloc_type(ctx, struct isl_sched_info);
1444	if (!info)
1445	return NULL;
1446	info->is_cst = isl_alloc_array(ctx, int, n);
1447	info->cst = isl_vec_alloc(ctx, size: n);
1448	if (n && (!info->is_cst || !info->cst))
1449	goto error;
1450
1451	for (i = 0; i < n; ++i) {
1452	isl_val *v;
1453
1454	v = isl_map_plain_get_val_if_fixed(map, type: isl_dim_in, pos: i);
1455	if (!v)
1456	goto error;
1457	info->is_cst[i] = !isl_val_is_nan(v);
1458	if (info->is_cst[i])
1459	info->cst = isl_vec_set_element_val(vec: info->cst, pos: i, v);
1460	else
1461	isl_val_free(v);
1462	}
1463
1464	return info;
1465	error:
1466	sched_info_free(info);
1467	return NULL;
1468	}
1469
1470	/* The different types of access relations that isl_union_access_info
1471	* keeps track of.
1472
1473	* "isl_access_sink" represents the sink accesses.
1474	* "isl_access_must_source" represents the definite source accesses.
1475	* "isl_access_may_source" represents the possible source accesses.
1476	* "isl_access_kill" represents the kills.
1477	*
1478	* isl_access_sink is sometimes treated differently and
1479	* should therefore appear first.
1480	*/
1481	enum isl_access_type {
1482	isl_access_sink,
1483	isl_access_must_source,
1484	isl_access_may_source,
1485	isl_access_kill,
1486	isl_access_end
1487	};
1488
1489	/* This structure represents the input for a dependence analysis computation.
1490	*
1491	* "access" contains the access relations.
1492	*
1493	* "schedule" or "schedule_map" represents the execution order.
1494	* Exactly one of these fields should be NULL. The other field
1495	* determines the execution order.
1496	*
1497	* The domains of these four maps refer to the same iteration spaces(s).
1498	* The ranges of the first three maps also refer to the same data space(s).
1499	*
1500	* After a call to isl_union_access_info_introduce_schedule,
1501	* the "schedule_map" field no longer contains useful information.
1502	*/
1503	struct isl_union_access_info {
1504	isl_union_map *access[isl_access_end];
1505
1506	isl_schedule *schedule;
1507	isl_union_map *schedule_map;
1508	};
1509
1510	/* Free "access" and return NULL.
1511	*/
1512	__isl_null isl_union_access_info *isl_union_access_info_free(
1513	__isl_take isl_union_access_info *access)
1514	{
1515	enum isl_access_type i;
1516
1517	if (!access)
1518	return NULL;
1519
1520	for (i = isl_access_sink; i < isl_access_end; ++i)
1521	isl_union_map_free(umap: access->access[i]);
1522	isl_schedule_free(sched: access->schedule);
1523	isl_union_map_free(umap: access->schedule_map);
1524	free(ptr: access);
1525
1526	return NULL;
1527	}
1528
1529	/* Return the isl_ctx to which "access" belongs.
1530	*/
1531	isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access)
1532	{
1533	if (!access)
1534	return NULL;
1535	return isl_union_map_get_ctx(umap: access->access[isl_access_sink]);
1536	}
1537
1538	/* Construct an empty (invalid) isl_union_access_info object.
1539	* The caller is responsible for setting the sink access relation and
1540	* initializing all the other fields, e.g., by calling
1541	* isl_union_access_info_init.
1542	*/
1543	static __isl_give isl_union_access_info *isl_union_access_info_alloc(
1544	isl_ctx *ctx)
1545	{
1546	return isl_calloc_type(ctx, isl_union_access_info);
1547	}
1548
1549	/* Initialize all the fields of "info", except the sink access relation,
1550	* which is assumed to have been set by the caller.
1551	*
1552	* By default, we use the schedule field of the isl_union_access_info,
1553	* but this may be overridden by a call
1554	* to isl_union_access_info_set_schedule_map.
1555	*/
1556	static __isl_give isl_union_access_info *isl_union_access_info_init(
1557	__isl_take isl_union_access_info *info)
1558	{
1559	isl_space *space;
1560	isl_union_map *empty;
1561	enum isl_access_type i;
1562
1563	if (!info)
1564	return NULL;
1565	if (!info->access[isl_access_sink])
1566	return isl_union_access_info_free(access: info);
1567
1568	space = isl_union_map_get_space(umap: info->access[isl_access_sink]);
1569	empty = isl_union_map_empty(space: isl_space_copy(space));
1570	for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1571	if (!info->access[i])
1572	info->access[i] = isl_union_map_copy(umap: empty);
1573	isl_union_map_free(umap: empty);
1574	if (!info->schedule && !info->schedule_map)
1575	info->schedule = isl_schedule_empty(space: isl_space_copy(space));
1576	isl_space_free(space);
1577
1578	for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1579	if (!info->access[i])
1580	return isl_union_access_info_free(access: info);
1581	if (!info->schedule && !info->schedule_map)
1582	return isl_union_access_info_free(access: info);
1583
1584	return info;
1585	}
1586
1587	/* Create a new isl_union_access_info with the given sink accesses and
1588	* and no other accesses or schedule information.
1589	*/
1590	__isl_give isl_union_access_info *isl_union_access_info_from_sink(
1591	__isl_take isl_union_map *sink)
1592	{
1593	isl_ctx *ctx;
1594	isl_union_access_info *access;
1595
1596	if (!sink)
1597	return NULL;
1598	ctx = isl_union_map_get_ctx(umap: sink);
1599	access = isl_union_access_info_alloc(ctx);
1600	if (!access)
1601	goto error;
1602	access->access[isl_access_sink] = sink;
1603	return isl_union_access_info_init(info: access);
1604	error:
1605	isl_union_map_free(umap: sink);
1606	return NULL;
1607	}
1608
1609	/* Replace the access relation of type "type" of "info" by "access".
1610	*/
1611	static __isl_give isl_union_access_info *isl_union_access_info_set(
1612	__isl_take isl_union_access_info *info,
1613	enum isl_access_type type, __isl_take isl_union_map *access)
1614	{
1615	if (!info || !access)
1616	goto error;
1617
1618	isl_union_map_free(umap: info->access[type]);
1619	info->access[type] = access;
1620
1621	return info;
1622	error:
1623	isl_union_access_info_free(access: info);
1624	isl_union_map_free(umap: access);
1625	return NULL;
1626	}
1627
1628	/* Replace the definite source accesses of "access" by "must_source".
1629	*/
1630	__isl_give isl_union_access_info *isl_union_access_info_set_must_source(
1631	__isl_take isl_union_access_info *access,
1632	__isl_take isl_union_map *must_source)
1633	{
1634	return isl_union_access_info_set(info: access, type: isl_access_must_source,
1635	access: must_source);
1636	}
1637
1638	/* Replace the possible source accesses of "access" by "may_source".
1639	*/
1640	__isl_give isl_union_access_info *isl_union_access_info_set_may_source(
1641	__isl_take isl_union_access_info *access,
1642	__isl_take isl_union_map *may_source)
1643	{
1644	return isl_union_access_info_set(info: access, type: isl_access_may_source,
1645	access: may_source);
1646	}
1647
1648	/* Replace the kills of "info" by "kill".
1649	*/
1650	__isl_give isl_union_access_info *isl_union_access_info_set_kill(
1651	__isl_take isl_union_access_info *info, __isl_take isl_union_map *kill)
1652	{
1653	return isl_union_access_info_set(info, type: isl_access_kill, access: kill);
1654	}
1655
1656	/* Return the access relation of type "type" of "info".
1657	*/
1658	static __isl_give isl_union_map *isl_union_access_info_get(
1659	__isl_keep isl_union_access_info *info, enum isl_access_type type)
1660	{
1661	if (!info)
1662	return NULL;
1663	return isl_union_map_copy(umap: info->access[type]);
1664	}
1665
1666	/* Return the definite source accesses of "info".
1667	*/
1668	__isl_give isl_union_map *isl_union_access_info_get_must_source(
1669	__isl_keep isl_union_access_info *info)
1670	{
1671	return isl_union_access_info_get(info, type: isl_access_must_source);
1672	}
1673
1674	/* Return the possible source accesses of "info".
1675	*/
1676	__isl_give isl_union_map *isl_union_access_info_get_may_source(
1677	__isl_keep isl_union_access_info *info)
1678	{
1679	return isl_union_access_info_get(info, type: isl_access_may_source);
1680	}
1681
1682	/* Return the kills of "info".
1683	*/
1684	__isl_give isl_union_map *isl_union_access_info_get_kill(
1685	__isl_keep isl_union_access_info *info)
1686	{
1687	return isl_union_access_info_get(info, type: isl_access_kill);
1688	}
1689
1690	/* Does "info" specify any kills?
1691	*/
1692	static isl_bool isl_union_access_has_kill(
1693	__isl_keep isl_union_access_info *info)
1694	{
1695	isl_bool empty;
1696
1697	if (!info)
1698	return isl_bool_error;
1699	empty = isl_union_map_is_empty(umap: info->access[isl_access_kill]);
1700	return isl_bool_not(b: empty);
1701	}
1702
1703	/* Replace the schedule of "access" by "schedule".
1704	* Also free the schedule_map in case it was set last.
1705	*/
1706	__isl_give isl_union_access_info *isl_union_access_info_set_schedule(
1707	__isl_take isl_union_access_info *access,
1708	__isl_take isl_schedule *schedule)
1709	{
1710	if (!access || !schedule)
1711	goto error;
1712
1713	access->schedule_map = isl_union_map_free(umap: access->schedule_map);
1714	isl_schedule_free(sched: access->schedule);
1715	access->schedule = schedule;
1716
1717	return access;
1718	error:
1719	isl_union_access_info_free(access);
1720	isl_schedule_free(sched: schedule);
1721	return NULL;
1722	}
1723
1724	/* Replace the schedule map of "access" by "schedule_map".
1725	* Also free the schedule in case it was set last.
1726	*/
1727	__isl_give isl_union_access_info *isl_union_access_info_set_schedule_map(
1728	__isl_take isl_union_access_info *access,
1729	__isl_take isl_union_map *schedule_map)
1730	{
1731	if (!access || !schedule_map)
1732	goto error;
1733
1734	isl_union_map_free(umap: access->schedule_map);
1735	access->schedule = isl_schedule_free(sched: access->schedule);
1736	access->schedule_map = schedule_map;
1737
1738	return access;
1739	error:
1740	isl_union_access_info_free(access);
1741	isl_union_map_free(umap: schedule_map);
1742	return NULL;
1743	}
1744
1745	__isl_give isl_union_access_info *isl_union_access_info_copy(
1746	__isl_keep isl_union_access_info *access)
1747	{
1748	isl_union_access_info *copy;
1749	enum isl_access_type i;
1750
1751	if (!access)
1752	return NULL;
1753	copy = isl_union_access_info_from_sink(
1754	sink: isl_union_map_copy(umap: access->access[isl_access_sink]));
1755	for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1756	copy = isl_union_access_info_set(info: copy, type: i,
1757	access: isl_union_map_copy(umap: access->access[i]));
1758	if (access->schedule)
1759	copy = isl_union_access_info_set_schedule(access: copy,
1760	schedule: isl_schedule_copy(sched: access->schedule));
1761	else
1762	copy = isl_union_access_info_set_schedule_map(access: copy,
1763	schedule_map: isl_union_map_copy(umap: access->schedule_map));
1764
1765	return copy;
1766	}
1767
1768	#undef BASE
1769	#define BASE union_map
1770	#include "print_yaml_field_templ.c"
1771
1772	/* An enumeration of the various keys that may appear in a YAML mapping
1773	* of an isl_union_access_info object.
1774	* The keys for the access relation types are assumed to have the same values
1775	* as the access relation types in isl_access_type.
1776	*/
1777	enum isl_ai_key {
1778	isl_ai_key_error = -1,
1779	isl_ai_key_sink = isl_access_sink,
1780	isl_ai_key_must_source = isl_access_must_source,
1781	isl_ai_key_may_source = isl_access_may_source,
1782	isl_ai_key_kill = isl_access_kill,
1783	isl_ai_key_schedule_map,
1784	isl_ai_key_schedule,
1785	isl_ai_key_end
1786	};
1787
1788	/* Textual representations of the YAML keys for an isl_union_access_info
1789	* object.
1790	*/
1791	static char *key_str[] = {
1792	[isl_ai_key_sink] = "sink",
1793	[isl_ai_key_must_source] = "must_source",
1794	[isl_ai_key_may_source] = "may_source",
1795	[isl_ai_key_kill] = "kill",
1796	[isl_ai_key_schedule_map] = "schedule_map",
1797	[isl_ai_key_schedule] = "schedule",
1798	};
1799
1800	/* Print a key-value pair corresponding to the access relation of type "type"
1801	* of a YAML mapping of "info" to "p".
1802	*
1803	* The sink access relation is always printed, but any other access relation
1804	* is only printed if it is non-empty.
1805	*/
1806	static __isl_give isl_printer *print_access_field(__isl_take isl_printer *p,
1807	__isl_keep isl_union_access_info *info, enum isl_access_type type)
1808	{
1809	if (type != isl_access_sink) {
1810	isl_bool empty;
1811
1812	empty = isl_union_map_is_empty(umap: info->access[type]);
1813	if (empty < 0)
1814	return isl_printer_free(printer: p);
1815	if (empty)
1816	return p;
1817	}
1818	return print_yaml_field_union_map(p, name: key_str[type], val: info->access[type]);
1819	}
1820
1821	/* Print the information contained in "access" to "p".
1822	* The information is printed as a YAML document.
1823	*/
1824	__isl_give isl_printer *isl_printer_print_union_access_info(
1825	__isl_take isl_printer *p, __isl_keep isl_union_access_info *access)
1826	{
1827	enum isl_access_type i;
1828
1829	if (!access)
1830	return isl_printer_free(printer: p);
1831
1832	p = isl_printer_yaml_start_mapping(p);
1833	for (i = isl_access_sink; i < isl_access_end; ++i)
1834	p = print_access_field(p, info: access, type: i);
1835	if (access->schedule) {
1836	p = isl_printer_print_str(p, s: key_str[isl_ai_key_schedule]);
1837	p = isl_printer_yaml_next(p);
1838	p = isl_printer_print_schedule(p, schedule: access->schedule);
1839	p = isl_printer_yaml_next(p);
1840	} else {
1841	p = print_yaml_field_union_map(p,
1842	name: key_str[isl_ai_key_schedule_map], val: access->schedule_map);
1843	}
1844	p = isl_printer_yaml_end_mapping(p);
1845
1846	return p;
1847	}
1848
1849	/* Return a string representation of the information in "access".
1850	* The information is printed in flow format.
1851	*/
1852	__isl_give char *isl_union_access_info_to_str(
1853	__isl_keep isl_union_access_info *access)
1854	{
1855	isl_printer *p;
1856	char *s;
1857
1858	if (!access)
1859	return NULL;
1860
1861	p = isl_printer_to_str(ctx: isl_union_access_info_get_ctx(access));
1862	p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
1863	p = isl_printer_print_union_access_info(p, access);
1864	s = isl_printer_get_str(printer: p);
1865	isl_printer_free(printer: p);
1866
1867	return s;
1868	}
1869
1870	#undef KEY
1871	#define KEY enum isl_ai_key
1872	#undef KEY_ERROR
1873	#define KEY_ERROR isl_ai_key_error
1874	#undef KEY_END
1875	#define KEY_END isl_ai_key_end
1876	#undef KEY_STR
1877	#define KEY_STR key_str
1878	#undef KEY_EXTRACT
1879	#define KEY_EXTRACT extract_key
1880	#undef KEY_GET
1881	#define KEY_GET get_key
1882	#include "extract_key.c"
1883
1884	#undef BASE
1885	#define BASE union_map
1886	#include "read_in_string_templ.c"
1887
1888	/* Read an isl_union_access_info object from "s".
1889	*
1890	* Start off with an empty (invalid) isl_union_access_info object and
1891	* then fill up the fields based on the input.
1892	* The input needs to contain at least a description of the sink
1893	* access relation as well as some form of schedule.
1894	* The other access relations are set to empty relations
1895	* by isl_union_access_info_init if they are not specified in the input.
1896	*/
1897	__isl_give isl_union_access_info *isl_stream_read_union_access_info(
1898	isl_stream *s)
1899	{
1900	isl_ctx *ctx;
1901	isl_union_access_info *info;
1902	isl_bool more;
1903	int sink_set = 0;
1904	int schedule_set = 0;
1905
1906	if (isl_stream_yaml_read_start_mapping(s) < 0)
1907	return NULL;
1908
1909	ctx = isl_stream_get_ctx(s);
1910	info = isl_union_access_info_alloc(ctx);
1911	while ((more = isl_stream_yaml_next(s)) == isl_bool_true) {
1912	enum isl_ai_key key;
1913	enum isl_access_type type;
1914	isl_union_map *access, *schedule_map;
1915	isl_schedule *schedule;
1916
1917	key = get_key(s);
1918	if (isl_stream_yaml_next(s) < 0)
1919	return isl_union_access_info_free(access: info);
1920	switch (key) {
1921	case isl_ai_key_end:
1922	case isl_ai_key_error:
1923	return isl_union_access_info_free(access: info);
1924	case isl_ai_key_sink:
1925	sink_set = 1;
1926	case isl_ai_key_must_source:
1927	case isl_ai_key_may_source:
1928	case isl_ai_key_kill:
1929	type = (enum isl_access_type) key;
1930	access = read_union_map(s);
1931	info = isl_union_access_info_set(info, type, access);
1932	if (!info)
1933	return NULL;
1934	break;
1935	case isl_ai_key_schedule_map:
1936	schedule_set = 1;
1937	schedule_map = read_union_map(s);
1938	info = isl_union_access_info_set_schedule_map(access: info,
1939	schedule_map);
1940	if (!info)
1941	return NULL;
1942	break;
1943	case isl_ai_key_schedule:
1944	schedule_set = 1;
1945	schedule = isl_stream_read_schedule(s);
1946	info = isl_union_access_info_set_schedule(access: info,
1947	schedule);
1948	if (!info)
1949	return NULL;
1950	break;
1951	}
1952	}
1953	if (more < 0)
1954	return isl_union_access_info_free(access: info);
1955
1956	if (isl_stream_yaml_read_end_mapping(s) < 0)
1957	return isl_union_access_info_free(access: info);
1958
1959	if (!sink_set) {
1960	isl_stream_error(s, NULL, msg: "no sink specified");
1961	return isl_union_access_info_free(access: info);
1962	}
1963
1964	if (!schedule_set) {
1965	isl_stream_error(s, NULL, msg: "no schedule specified");
1966	return isl_union_access_info_free(access: info);
1967	}
1968
1969	return isl_union_access_info_init(info);
1970	}
1971
1972	/* Read an isl_union_access_info object from the file "input".
1973	*/
1974	__isl_give isl_union_access_info *isl_union_access_info_read_from_file(
1975	isl_ctx *ctx, FILE *input)
1976	{
1977	isl_stream *s;
1978	isl_union_access_info *access;
1979
1980	s = isl_stream_new_file(ctx, file: input);
1981	if (!s)
1982	return NULL;
1983	access = isl_stream_read_union_access_info(s);
1984	isl_stream_free(s);
1985
1986	return access;
1987	}
1988
1989	/* Update the fields of "access" such that they all have the same parameters,
1990	* keeping in mind that the schedule_map field may be NULL and ignoring
1991	* the schedule field.
1992	*/
1993	static __isl_give isl_union_access_info *isl_union_access_info_align_params(
1994	__isl_take isl_union_access_info *access)
1995	{
1996	isl_space *space;
1997	enum isl_access_type i;
1998
1999	if (!access)
2000	return NULL;
2001
2002	space = isl_union_map_get_space(umap: access->access[isl_access_sink]);
2003	for (i = isl_access_sink + 1; i < isl_access_end; ++i)
2004	space = isl_space_align_params(space1: space,
2005	space2: isl_union_map_get_space(umap: access->access[i]));
2006	if (access->schedule_map)
2007	space = isl_space_align_params(space1: space,
2008	space2: isl_union_map_get_space(umap: access->schedule_map));
2009	for (i = isl_access_sink; i < isl_access_end; ++i)
2010	access->access[i] =
2011	isl_union_map_align_params(umap: access->access[i],
2012	model: isl_space_copy(space));
2013	if (!access->schedule_map) {
2014	isl_space_free(space);
2015	} else {
2016	access->schedule_map =
2017	isl_union_map_align_params(umap: access->schedule_map, model: space);
2018	if (!access->schedule_map)
2019	return isl_union_access_info_free(access);
2020	}
2021
2022	for (i = isl_access_sink; i < isl_access_end; ++i)
2023	if (!access->access[i])
2024	return isl_union_access_info_free(access);
2025
2026	return access;
2027	}
2028
2029	/* Prepend the schedule dimensions to the iteration domains.
2030	*
2031	* That is, if the schedule is of the form
2032	*
2033	* D -> S
2034	*
2035	* while the access relations are of the form
2036	*
2037	* D -> A
2038	*
2039	* then the updated access relations are of the form
2040	*
2041	* [S -> D] -> A
2042	*
2043	* The schedule map is also replaced by the map
2044	*
2045	* [S -> D] -> D
2046	*
2047	* that is used during the internal computation.
2048	* Neither the original schedule map nor this updated schedule map
2049	* are used after the call to this function.
2050	*/
2051	static __isl_give isl_union_access_info *
2052	isl_union_access_info_introduce_schedule(
2053	__isl_take isl_union_access_info *access)
2054	{
2055	isl_union_map *sm;
2056	enum isl_access_type i;
2057
2058	if (!access)
2059	return NULL;
2060
2061	sm = isl_union_map_reverse(umap: access->schedule_map);
2062	sm = isl_union_map_range_map(umap: sm);
2063	for (i = isl_access_sink; i < isl_access_end; ++i)
2064	access->access[i] =
2065	isl_union_map_apply_range(umap1: isl_union_map_copy(umap: sm),
2066	umap2: access->access[i]);
2067	access->schedule_map = sm;
2068
2069	for (i = isl_access_sink; i < isl_access_end; ++i)
2070	if (!access->access[i])
2071	return isl_union_access_info_free(access);
2072	if (!access->schedule_map)
2073	return isl_union_access_info_free(access);
2074
2075	return access;
2076	}
2077
2078	/* This structure represents the result of a dependence analysis computation.
2079	*
2080	* "must_dep" represents the full definite dependences
2081	* "may_dep" represents the full non-definite dependences.
2082	* Both are of the form
2083	*
2084	* [Source] -> [[Sink -> Data]]
2085	*
2086	* (after the schedule dimensions have been projected out).
2087	* "must_no_source" represents the subset of the sink accesses for which
2088	* definitely no source was found.
2089	* "may_no_source" represents the subset of the sink accesses for which
2090	* possibly, but not definitely, no source was found.
2091	*/
2092	struct isl_union_flow {
2093	isl_union_map *must_dep;
2094	isl_union_map *may_dep;
2095	isl_union_map *must_no_source;
2096	isl_union_map *may_no_source;
2097	};
2098
2099	/* Return the isl_ctx to which "flow" belongs.
2100	*/
2101	isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow)
2102	{
2103	return flow ? isl_union_map_get_ctx(umap: flow->must_dep) : NULL;
2104	}
2105
2106	/* Free "flow" and return NULL.
2107	*/
2108	__isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow)
2109	{
2110	if (!flow)
2111	return NULL;
2112	isl_union_map_free(umap: flow->must_dep);
2113	isl_union_map_free(umap: flow->may_dep);
2114	isl_union_map_free(umap: flow->must_no_source);
2115	isl_union_map_free(umap: flow->may_no_source);
2116	free(ptr: flow);
2117	return NULL;
2118	}
2119
2120	void isl_union_flow_dump(__isl_keep isl_union_flow *flow)
2121	{
2122	if (!flow)
2123	return;
2124
2125	fprintf(stderr, format: "must dependences: ");
2126	isl_union_map_dump(umap: flow->must_dep);
2127	fprintf(stderr, format: "may dependences: ");
2128	isl_union_map_dump(umap: flow->may_dep);
2129	fprintf(stderr, format: "must no source: ");
2130	isl_union_map_dump(umap: flow->must_no_source);
2131	fprintf(stderr, format: "may no source: ");
2132	isl_union_map_dump(umap: flow->may_no_source);
2133	}
2134
2135	/* Return the full definite dependences in "flow", with accessed elements.
2136	*/
2137	__isl_give isl_union_map *isl_union_flow_get_full_must_dependence(
2138	__isl_keep isl_union_flow *flow)
2139	{
2140	if (!flow)
2141	return NULL;
2142	return isl_union_map_copy(umap: flow->must_dep);
2143	}
2144
2145	/* Return the full possible dependences in "flow", including the definite
2146	* dependences, with accessed elements.
2147	*/
2148	__isl_give isl_union_map *isl_union_flow_get_full_may_dependence(
2149	__isl_keep isl_union_flow *flow)
2150	{
2151	if (!flow)
2152	return NULL;
2153	return isl_union_map_union(umap1: isl_union_map_copy(umap: flow->must_dep),
2154	umap2: isl_union_map_copy(umap: flow->may_dep));
2155	}
2156
2157	/* Return the definite dependences in "flow", without the accessed elements.
2158	*/
2159	__isl_give isl_union_map *isl_union_flow_get_must_dependence(
2160	__isl_keep isl_union_flow *flow)
2161	{
2162	isl_union_map *dep;
2163
2164	if (!flow)
2165	return NULL;
2166	dep = isl_union_map_copy(umap: flow->must_dep);
2167	return isl_union_map_range_factor_domain(umap: dep);
2168	}
2169
2170	/* Return the possible dependences in "flow", including the definite
2171	* dependences, without the accessed elements.
2172	*/
2173	__isl_give isl_union_map *isl_union_flow_get_may_dependence(
2174	__isl_keep isl_union_flow *flow)
2175	{
2176	isl_union_map *dep;
2177
2178	if (!flow)
2179	return NULL;
2180	dep = isl_union_map_union(umap1: isl_union_map_copy(umap: flow->must_dep),
2181	umap2: isl_union_map_copy(umap: flow->may_dep));
2182	return isl_union_map_range_factor_domain(umap: dep);
2183	}
2184
2185	/* Return the non-definite dependences in "flow".
2186	*/
2187	static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence(
2188	__isl_keep isl_union_flow *flow)
2189	{
2190	if (!flow)
2191	return NULL;
2192	return isl_union_map_copy(umap: flow->may_dep);
2193	}
2194
2195	/* Return the subset of the sink accesses for which definitely
2196	* no source was found.
2197	*/
2198	__isl_give isl_union_map *isl_union_flow_get_must_no_source(
2199	__isl_keep isl_union_flow *flow)
2200	{
2201	if (!flow)
2202	return NULL;
2203	return isl_union_map_copy(umap: flow->must_no_source);
2204	}
2205
2206	/* Return the subset of the sink accesses for which possibly
2207	* no source was found, including those for which definitely
2208	* no source was found.
2209	*/
2210	__isl_give isl_union_map *isl_union_flow_get_may_no_source(
2211	__isl_keep isl_union_flow *flow)
2212	{
2213	if (!flow)
2214	return NULL;
2215	return isl_union_map_union(umap1: isl_union_map_copy(umap: flow->must_no_source),
2216	umap2: isl_union_map_copy(umap: flow->may_no_source));
2217	}
2218
2219	/* Return the subset of the sink accesses for which possibly, but not
2220	* definitely, no source was found.
2221	*/
2222	static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source(
2223	__isl_keep isl_union_flow *flow)
2224	{
2225	if (!flow)
2226	return NULL;
2227	return isl_union_map_copy(umap: flow->may_no_source);
2228	}
2229
2230	/* Create a new isl_union_flow object, initialized with empty
2231	* dependence relations and sink subsets.
2232	*/
2233	static __isl_give isl_union_flow *isl_union_flow_alloc(
2234	__isl_take isl_space *space)
2235	{
2236	isl_ctx *ctx;
2237	isl_union_map *empty;
2238	isl_union_flow *flow;
2239
2240	if (!space)
2241	return NULL;
2242	ctx = isl_space_get_ctx(space);
2243	flow = isl_alloc_type(ctx, isl_union_flow);
2244	if (!flow)
2245	goto error;
2246
2247	empty = isl_union_map_empty(space);
2248	flow->must_dep = isl_union_map_copy(umap: empty);
2249	flow->may_dep = isl_union_map_copy(umap: empty);
2250	flow->must_no_source = isl_union_map_copy(umap: empty);
2251	flow->may_no_source = empty;
2252
2253	if (!flow->must_dep || !flow->may_dep ||
2254	!flow->must_no_source || !flow->may_no_source)
2255	return isl_union_flow_free(flow);
2256
2257	return flow;
2258	error:
2259	isl_space_free(space);
2260	return NULL;
2261	}
2262
2263	/* Copy this isl_union_flow object.
2264	*/
2265	__isl_give isl_union_flow *isl_union_flow_copy(__isl_keep isl_union_flow *flow)
2266	{
2267	isl_union_flow *copy;
2268
2269	if (!flow)
2270	return NULL;
2271
2272	copy = isl_union_flow_alloc(space: isl_union_map_get_space(umap: flow->must_dep));
2273
2274	if (!copy)
2275	return NULL;
2276
2277	copy->must_dep = isl_union_map_union(umap1: copy->must_dep,
2278	umap2: isl_union_map_copy(umap: flow->must_dep));
2279	copy->may_dep = isl_union_map_union(umap1: copy->may_dep,
2280	umap2: isl_union_map_copy(umap: flow->may_dep));
2281	copy->must_no_source = isl_union_map_union(umap1: copy->must_no_source,
2282	umap2: isl_union_map_copy(umap: flow->must_no_source));
2283	copy->may_no_source = isl_union_map_union(umap1: copy->may_no_source,
2284	umap2: isl_union_map_copy(umap: flow->may_no_source));
2285
2286	if (!copy->must_dep || !copy->may_dep ||
2287	!copy->must_no_source || !copy->may_no_source)
2288	return isl_union_flow_free(flow: copy);
2289
2290	return copy;
2291	}
2292
2293	/* Drop the schedule dimensions from the iteration domains in "flow".
2294	* In particular, the schedule dimensions have been prepended
2295	* to the iteration domains prior to the dependence analysis by
2296	* replacing the iteration domain D, by the wrapped map [S -> D].
2297	* Replace these wrapped maps by the original D.
2298	*
2299	* In particular, the dependences computed by access_info_compute_flow_core
2300	* are of the form
2301	*
2302	* [S -> D] -> [[S' -> D'] -> A]
2303	*
2304	* The schedule dimensions are projected out by first currying the range,
2305	* resulting in
2306	*
2307	* [S -> D] -> [S' -> [D' -> A]]
2308	*
2309	* and then computing the factor range
2310	*
2311	* D -> [D' -> A]
2312	*/
2313	static __isl_give isl_union_flow *isl_union_flow_drop_schedule(
2314	__isl_take isl_union_flow *flow)
2315	{
2316	if (!flow)
2317	return NULL;
2318
2319	flow->must_dep = isl_union_map_range_curry(umap: flow->must_dep);
2320	flow->must_dep = isl_union_map_factor_range(umap: flow->must_dep);
2321	flow->may_dep = isl_union_map_range_curry(umap: flow->may_dep);
2322	flow->may_dep = isl_union_map_factor_range(umap: flow->may_dep);
2323	flow->must_no_source =
2324	isl_union_map_domain_factor_range(umap: flow->must_no_source);
2325	flow->may_no_source =
2326	isl_union_map_domain_factor_range(umap: flow->may_no_source);
2327
2328	if (!flow->must_dep || !flow->may_dep ||
2329	!flow->must_no_source || !flow->may_no_source)
2330	return isl_union_flow_free(flow);
2331
2332	return flow;
2333	}
2334
2335	struct isl_compute_flow_data {
2336	isl_union_map *must_source;
2337	isl_union_map *may_source;
2338	isl_union_flow *flow;
2339
2340	int count;
2341	int must;
2342	isl_space *dim;
2343	struct isl_sched_info *sink_info;
2344	struct isl_sched_info **source_info;
2345	isl_access_info *accesses;
2346	};
2347
2348	static isl_stat count_matching_array(__isl_take isl_map *map, void *user)
2349	{
2350	int eq;
2351	isl_space *space;
2352	struct isl_compute_flow_data *data;
2353
2354	data = (struct isl_compute_flow_data *)user;
2355
2356	space = isl_space_range(space: isl_map_get_space(map));
2357
2358	eq = isl_space_is_equal(space1: space, space2: data->dim);
2359
2360	isl_space_free(space);
2361	isl_map_free(map);
2362
2363	if (eq < 0)
2364	return isl_stat_error;
2365	if (eq)
2366	data->count++;
2367
2368	return isl_stat_ok;
2369	}
2370
2371	static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
2372	{
2373	int eq;
2374	isl_space *space;
2375	struct isl_sched_info *info;
2376	struct isl_compute_flow_data *data;
2377
2378	data = (struct isl_compute_flow_data *)user;
2379
2380	space = isl_space_range(space: isl_map_get_space(map));
2381
2382	eq = isl_space_is_equal(space1: space, space2: data->dim);
2383
2384	isl_space_free(space);
2385
2386	if (eq < 0)
2387	goto error;
2388	if (!eq) {
2389	isl_map_free(map);
2390	return isl_stat_ok;
2391	}
2392
2393	info = sched_info_alloc(map);
2394	data->source_info[data->count] = info;
2395
2396	data->accesses = isl_access_info_add_source(acc: data->accesses,
2397	source: map, must: data->must, source_user: info);
2398
2399	data->count++;
2400
2401	return isl_stat_ok;
2402	error:
2403	isl_map_free(map);
2404	return isl_stat_error;
2405	}
2406
2407	/* Determine the shared nesting level and the "textual order" of
2408	* the given accesses.
2409	*
2410	* We first determine the minimal schedule dimension for both accesses.
2411	*
2412	* If among those dimensions, we can find one where both have a fixed
2413	* value and if moreover those values are different, then the previous
2414	* dimension is the last shared nesting level and the textual order
2415	* is determined based on the order of the fixed values.
2416	* If no such fixed values can be found, then we set the shared
2417	* nesting level to the minimal schedule dimension, with no textual ordering.
2418	*/
2419	static int before(void *first, void *second)
2420	{
2421	struct isl_sched_info *info1 = first;
2422	struct isl_sched_info *info2 = second;
2423	isl_size n1, n2;
2424	int i;
2425
2426	n1 = isl_vec_size(vec: info1->cst);
2427	n2 = isl_vec_size(vec: info2->cst);
2428	if (n1 < 0 || n2 < 0)
2429	return -1;
2430
2431	if (n2 < n1)
2432	n1 = n2;
2433
2434	for (i = 0; i < n1; ++i) {
2435	int r;
2436	int cmp;
2437
2438	if (!info1->is_cst[i])
2439	continue;
2440	if (!info2->is_cst[i])
2441	continue;
2442	cmp = isl_vec_cmp_element(vec1: info1->cst, vec2: info2->cst, pos: i);
2443	if (cmp == 0)
2444	continue;
2445
2446	r = 2 * i + (cmp < 0);
2447
2448	return r;
2449	}
2450
2451	return 2 * n1;
2452	}
2453
2454	/* Check if the given two accesses may be coscheduled.
2455	* If so, return isl_bool_true. Otherwise return isl_bool_false.
2456	*
2457	* Two accesses may only be coscheduled if the fixed schedule
2458	* coordinates have the same values.
2459	*/
2460	static isl_bool coscheduled(void *first, void *second)
2461	{
2462	struct isl_sched_info *info1 = first;
2463	struct isl_sched_info *info2 = second;
2464	isl_size n1, n2;
2465	int i;
2466
2467	n1 = isl_vec_size(vec: info1->cst);
2468	n2 = isl_vec_size(vec: info2->cst);
2469	if (n1 < 0 || n2 < 0)
2470	return isl_bool_error;
2471
2472	if (n2 < n1)
2473	n1 = n2;
2474
2475	for (i = 0; i < n1; ++i) {
2476	int cmp;
2477
2478	if (!info1->is_cst[i])
2479	continue;
2480	if (!info2->is_cst[i])
2481	continue;
2482	cmp = isl_vec_cmp_element(vec1: info1->cst, vec2: info2->cst, pos: i);
2483	if (cmp != 0)
2484	return isl_bool_false;
2485	}
2486
2487	return isl_bool_true;
2488	}
2489
2490	/* Given a sink access, look for all the source accesses that access
2491	* the same array and perform dataflow analysis on them using
2492	* isl_access_info_compute_flow_core.
2493	*/
2494	static isl_stat compute_flow(__isl_take isl_map *map, void *user)
2495	{
2496	int i;
2497	isl_ctx *ctx;
2498	struct isl_compute_flow_data *data;
2499	isl_flow *flow;
2500	isl_union_flow *df;
2501
2502	data = (struct isl_compute_flow_data *)user;
2503	df = data->flow;
2504
2505	ctx = isl_map_get_ctx(map);
2506
2507	data->accesses = NULL;
2508	data->sink_info = NULL;
2509	data->source_info = NULL;
2510	data->count = 0;
2511	data->dim = isl_space_range(space: isl_map_get_space(map));
2512
2513	if (isl_union_map_foreach_map(umap: data->must_source,
2514	fn: &count_matching_array, user: data) < 0)
2515	goto error;
2516	if (isl_union_map_foreach_map(umap: data->may_source,
2517	fn: &count_matching_array, user: data) < 0)
2518	goto error;
2519
2520	data->sink_info = sched_info_alloc(map);
2521	data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
2522	data->count);
2523
2524	data->accesses = isl_access_info_alloc(sink: isl_map_copy(map),
2525	sink_user: data->sink_info, fn: &before, max_source: data->count);
2526	if (!data->sink_info || (data->count && !data->source_info) ||
2527	!data->accesses)
2528	goto error;
2529	data->accesses->coscheduled = &coscheduled;
2530	data->count = 0;
2531	data->must = 1;
2532	if (isl_union_map_foreach_map(umap: data->must_source,
2533	fn: &collect_matching_array, user: data) < 0)
2534	goto error;
2535	data->must = 0;
2536	if (isl_union_map_foreach_map(umap: data->may_source,
2537	fn: &collect_matching_array, user: data) < 0)
2538	goto error;
2539
2540	flow = access_info_compute_flow_core(acc: data->accesses);
2541	data->accesses = NULL;
2542
2543	if (!flow)
2544	goto error;
2545
2546	df->must_no_source = isl_union_map_union(umap1: df->must_no_source,
2547	umap2: isl_union_map_from_map(map: isl_flow_get_no_source(deps: flow, must: 1)));
2548	df->may_no_source = isl_union_map_union(umap1: df->may_no_source,
2549	umap2: isl_union_map_from_map(map: isl_flow_get_no_source(deps: flow, must: 0)));
2550
2551	for (i = 0; i < flow->n_source; ++i) {
2552	isl_union_map *dep;
2553	dep = isl_union_map_from_map(map: isl_map_copy(map: flow->dep[i].map));
2554	if (flow->dep[i].must)
2555	df->must_dep = isl_union_map_union(umap1: df->must_dep, umap2: dep);
2556	else
2557	df->may_dep = isl_union_map_union(umap1: df->may_dep, umap2: dep);
2558	}
2559
2560	isl_flow_free(deps: flow);
2561
2562	sched_info_free(info: data->sink_info);
2563	if (data->source_info) {
2564	for (i = 0; i < data->count; ++i)
2565	sched_info_free(info: data->source_info[i]);
2566	free(ptr: data->source_info);
2567	}
2568	isl_space_free(space: data->dim);
2569	isl_map_free(map);
2570
2571	return isl_stat_ok;
2572	error:
2573	isl_access_info_free(acc: data->accesses);
2574	sched_info_free(info: data->sink_info);
2575	if (data->source_info) {
2576	for (i = 0; i < data->count; ++i)
2577	sched_info_free(info: data->source_info[i]);
2578	free(ptr: data->source_info);
2579	}
2580	isl_space_free(space: data->dim);
2581	isl_map_free(map);
2582
2583	return isl_stat_error;
2584	}
2585
2586	/* Add the kills of "info" to the must-sources.
2587	*/
2588	static __isl_give isl_union_access_info *
2589	isl_union_access_info_add_kill_to_must_source(
2590	__isl_take isl_union_access_info *info)
2591	{
2592	isl_union_map *must, *kill;
2593
2594	must = isl_union_access_info_get_must_source(info);
2595	kill = isl_union_access_info_get_kill(info);
2596	must = isl_union_map_union(umap1: must, umap2: kill);
2597	return isl_union_access_info_set_must_source(access: info, must_source: must);
2598	}
2599
2600	/* Drop dependences from "flow" that purely originate from kills.
2601	* That is, only keep those dependences that originate from
2602	* the original must-sources "must" and/or the original may-sources "may".
2603	* In particular, "must" contains the must-sources from before
2604	* the kills were added and "may" contains the may-source from before
2605	* the kills were removed.
2606	*
2607	* The dependences are of the form
2608	*
2609	* Source -> [Sink -> Data]
2610	*
2611	* Only those dependences are kept where the Source -> Data part
2612	* is a subset of the original may-sources or must-sources.
2613	* Of those, only the must-dependences that intersect with the must-sources
2614	* remain must-dependences.
2615	* If there is some overlap between the may-sources and the must-sources,
2616	* then the may-dependences and must-dependences may also overlap.
2617	* This should be fine since the may-dependences are only kept
2618	* disjoint from the must-dependences for the isl_union_map_compute_flow
2619	* interface. This interface does not support kills, so it will
2620	* not end up calling this function.
2621	*/
2622	static __isl_give isl_union_flow *isl_union_flow_drop_kill_source(
2623	__isl_take isl_union_flow *flow, __isl_take isl_union_map *must,
2624	__isl_take isl_union_map *may)
2625	{
2626	isl_union_map *move;
2627
2628	if (!flow)
2629	goto error;
2630	move = isl_union_map_copy(umap: flow->must_dep);
2631	move = isl_union_map_intersect_range_factor_range(umap: move,
2632	factor: isl_union_map_copy(umap: may));
2633	may = isl_union_map_union(umap1: may, umap2: isl_union_map_copy(umap: must));
2634	flow->may_dep = isl_union_map_intersect_range_factor_range(
2635	umap: flow->may_dep, factor: may);
2636	flow->must_dep = isl_union_map_intersect_range_factor_range(
2637	umap: flow->must_dep, factor: must);
2638	flow->may_dep = isl_union_map_union(umap1: flow->may_dep, umap2: move);
2639	if (!flow->must_dep || !flow->may_dep)
2640	return isl_union_flow_free(flow);
2641
2642	return flow;
2643	error:
2644	isl_union_map_free(umap: must);
2645	isl_union_map_free(umap: may);
2646	return NULL;
2647	}
2648
2649	/* Remove the must accesses from the may accesses.
2650	*
2651	* A must access always trumps a may access, so there is no need
2652	* for a must access to also be considered as a may access. Doing so
2653	* would only cost extra computations only to find out that
2654	* the duplicated may access does not make any difference.
2655	*/
2656	static __isl_give isl_union_access_info *isl_union_access_info_normalize(
2657	__isl_take isl_union_access_info *access)
2658	{
2659	if (!access)
2660	return NULL;
2661	access->access[isl_access_may_source] =
2662	isl_union_map_subtract(umap1: access->access[isl_access_may_source],
2663	umap2: isl_union_map_copy(umap: access->access[isl_access_must_source]));
2664	if (!access->access[isl_access_may_source])
2665	return isl_union_access_info_free(access);
2666
2667	return access;
2668	}
2669
2670	/* Given a description of the "sink" accesses, the "source" accesses and
2671	* a schedule, compute for each instance of a sink access
2672	* and for each element accessed by that instance,
2673	* the possible or definite source accesses that last accessed the
2674	* element accessed by the sink access before this sink access
2675	* in the sense that there is no intermediate definite source access.
2676	*
2677	* The must_no_source and may_no_source elements of the result
2678	* are subsets of access->sink. The elements must_dep and may_dep
2679	* map domain elements of access->{may,must)_source to
2680	* domain elements of access->sink.
2681	*
2682	* This function is used when only the schedule map representation
2683	* is available.
2684	*
2685	* We first prepend the schedule dimensions to the domain
2686	* of the accesses so that we can easily compare their relative order.
2687	* Then we consider each sink access individually in compute_flow.
2688	*/
2689	static __isl_give isl_union_flow *compute_flow_union_map(
2690	__isl_take isl_union_access_info *access)
2691	{
2692	struct isl_compute_flow_data data;
2693	isl_union_map *sink;
2694
2695	access = isl_union_access_info_align_params(access);
2696	access = isl_union_access_info_introduce_schedule(access);
2697	if (!access)
2698	return NULL;
2699
2700	data.must_source = access->access[isl_access_must_source];
2701	data.may_source = access->access[isl_access_may_source];
2702
2703	sink = access->access[isl_access_sink];
2704	data.flow = isl_union_flow_alloc(space: isl_union_map_get_space(umap: sink));
2705
2706	if (isl_union_map_foreach_map(umap: sink, fn: &compute_flow, user: &data) < 0)
2707	goto error;
2708
2709	data.flow = isl_union_flow_drop_schedule(flow: data.flow);
2710
2711	isl_union_access_info_free(access);
2712	return data.flow;
2713	error:
2714	isl_union_access_info_free(access);
2715	isl_union_flow_free(flow: data.flow);
2716	return NULL;
2717	}
2718
2719	/* A schedule access relation.
2720	*
2721	* The access relation "access" is of the form [S -> D] -> A,
2722	* where S corresponds to the prefix schedule at "node".
2723	* "must" is only relevant for source accesses and indicates
2724	* whether the access is a must source or a may source.
2725	*/
2726	struct isl_scheduled_access {
2727	isl_map *access;
2728	int must;
2729	isl_schedule_node *node;
2730	};
2731
2732	/* Data structure for keeping track of individual scheduled sink and source
2733	* accesses when computing dependence analysis based on a schedule tree.
2734	*
2735	* "n_sink" is the number of used entries in "sink"
2736	* "n_source" is the number of used entries in "source"
2737	*
2738	* "set_sink", "must" and "node" are only used inside collect_sink_source,
2739	* to keep track of the current node and
2740	* of what extract_sink_source needs to do.
2741	*/
2742	struct isl_compute_flow_schedule_data {
2743	isl_union_access_info *access;
2744
2745	int n_sink;
2746	int n_source;
2747
2748	struct isl_scheduled_access *sink;
2749	struct isl_scheduled_access *source;
2750
2751	int set_sink;
2752	int must;
2753	isl_schedule_node *node;
2754	};
2755
2756	/* Align the parameters of all sinks with all sources.
2757	*
2758	* If there are no sinks or no sources, then no alignment is needed.
2759	*/
2760	static void isl_compute_flow_schedule_data_align_params(
2761	struct isl_compute_flow_schedule_data *data)
2762	{
2763	int i;
2764	isl_space *space;
2765
2766	if (data->n_sink == 0 || data->n_source == 0)
2767	return;
2768
2769	space = isl_map_get_space(map: data->sink[0].access);
2770
2771	for (i = 1; i < data->n_sink; ++i)
2772	space = isl_space_align_params(space1: space,
2773	space2: isl_map_get_space(map: data->sink[i].access));
2774	for (i = 0; i < data->n_source; ++i)
2775	space = isl_space_align_params(space1: space,
2776	space2: isl_map_get_space(map: data->source[i].access));
2777
2778	for (i = 0; i < data->n_sink; ++i)
2779	data->sink[i].access =
2780	isl_map_align_params(map: data->sink[i].access,
2781	model: isl_space_copy(space));
2782	for (i = 0; i < data->n_source; ++i)
2783	data->source[i].access =
2784	isl_map_align_params(map: data->source[i].access,
2785	model: isl_space_copy(space));
2786
2787	isl_space_free(space);
2788	}
2789
2790	/* Free all the memory referenced from "data".
2791	* Do not free "data" itself as it may be allocated on the stack.
2792	*/
2793	static void isl_compute_flow_schedule_data_clear(
2794	struct isl_compute_flow_schedule_data *data)
2795	{
2796	int i;
2797
2798	if (!data->sink)
2799	return;
2800
2801	for (i = 0; i < data->n_sink; ++i) {
2802	isl_map_free(map: data->sink[i].access);
2803	isl_schedule_node_free(node: data->sink[i].node);
2804	}
2805
2806	for (i = 0; i < data->n_source; ++i) {
2807	isl_map_free(map: data->source[i].access);
2808	isl_schedule_node_free(node: data->source[i].node);
2809	}
2810
2811	free(ptr: data->sink);
2812	}
2813
2814	/* isl_schedule_foreach_schedule_node_top_down callback for counting
2815	* (an upper bound on) the number of sinks and sources.
2816	*
2817	* Sinks and sources are only extracted at leaves of the tree,
2818	* so we skip the node if it is not a leaf.
2819	* Otherwise we increment data->n_sink and data->n_source with
2820	* the number of spaces in the sink and source access domains
2821	* that reach this node.
2822	*/
2823	static isl_bool count_sink_source(__isl_keep isl_schedule_node *node,
2824	void *user)
2825	{
2826	struct isl_compute_flow_schedule_data *data = user;
2827	isl_union_set *domain;
2828	isl_union_map *umap;
2829	isl_bool r = isl_bool_false;
2830	isl_size n;
2831
2832	if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2833	return isl_bool_true;
2834
2835	domain = isl_schedule_node_get_universe_domain(node);
2836
2837	umap = isl_union_map_copy(umap: data->access->access[isl_access_sink]);
2838	umap = isl_union_map_intersect_domain(umap, uset: isl_union_set_copy(uset: domain));
2839	data->n_sink += n = isl_union_map_n_map(umap);
2840	isl_union_map_free(umap);
2841	if (n < 0)
2842	r = isl_bool_error;
2843
2844	umap = isl_union_map_copy(umap: data->access->access[isl_access_must_source]);
2845	umap = isl_union_map_intersect_domain(umap, uset: isl_union_set_copy(uset: domain));
2846	data->n_source += n = isl_union_map_n_map(umap);
2847	isl_union_map_free(umap);
2848	if (n < 0)
2849	r = isl_bool_error;
2850
2851	umap = isl_union_map_copy(umap: data->access->access[isl_access_may_source]);
2852	umap = isl_union_map_intersect_domain(umap, uset: isl_union_set_copy(uset: domain));
2853	data->n_source += n = isl_union_map_n_map(umap);
2854	isl_union_map_free(umap);
2855	if (n < 0)
2856	r = isl_bool_error;
2857
2858	isl_union_set_free(uset: domain);
2859
2860	return r;
2861	}
2862
2863	/* Add a single scheduled sink or source (depending on data->set_sink)
2864	* with scheduled access relation "map", must property data->must and
2865	* schedule node data->node to the list of sinks or sources.
2866	*/
2867	static isl_stat extract_sink_source(__isl_take isl_map *map, void *user)
2868	{
2869	struct isl_compute_flow_schedule_data *data = user;
2870	struct isl_scheduled_access *access;
2871
2872	if (data->set_sink)
2873	access = data->sink + data->n_sink++;
2874	else
2875	access = data->source + data->n_source++;
2876
2877	access->access = map;
2878	access->must = data->must;
2879	access->node = isl_schedule_node_copy(node: data->node);
2880
2881	return isl_stat_ok;
2882	}
2883
2884	/* isl_schedule_foreach_schedule_node_top_down callback for collecting
2885	* individual scheduled source and sink accesses (taking into account
2886	* the domain of the schedule).
2887	*
2888	* We only collect accesses at the leaves of the schedule tree.
2889	* We prepend the schedule dimensions at the leaf to the iteration
2890	* domains of the source and sink accesses and then extract
2891	* the individual accesses (per space).
2892	*
2893	* In particular, if the prefix schedule at the node is of the form
2894	*
2895	* D -> S
2896	*
2897	* while the access relations are of the form
2898	*
2899	* D -> A
2900	*
2901	* then the updated access relations are of the form
2902	*
2903	* [S -> D] -> A
2904	*
2905	* Note that S consists of a single space such that introducing S
2906	* in the access relations does not increase the number of spaces.
2907	*/
2908	static isl_bool collect_sink_source(__isl_keep isl_schedule_node *node,
2909	void *user)
2910	{
2911	struct isl_compute_flow_schedule_data *data = user;
2912	isl_union_map *prefix;
2913	isl_union_map *umap;
2914	isl_bool r = isl_bool_false;
2915
2916	if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2917	return isl_bool_true;
2918
2919	data->node = node;
2920
2921	prefix = isl_schedule_node_get_prefix_schedule_relation(node);
2922	prefix = isl_union_map_reverse(umap: prefix);
2923	prefix = isl_union_map_range_map(umap: prefix);
2924
2925	data->set_sink = 1;
2926	umap = isl_union_map_copy(umap: data->access->access[isl_access_sink]);
2927	umap = isl_union_map_apply_range(umap1: isl_union_map_copy(umap: prefix), umap2: umap);
2928	if (isl_union_map_foreach_map(umap, fn: &extract_sink_source, user: data) < 0)
2929	r = isl_bool_error;
2930	isl_union_map_free(umap);
2931
2932	data->set_sink = 0;
2933	data->must = 1;
2934	umap = isl_union_map_copy(umap: data->access->access[isl_access_must_source]);
2935	umap = isl_union_map_apply_range(umap1: isl_union_map_copy(umap: prefix), umap2: umap);
2936	if (isl_union_map_foreach_map(umap, fn: &extract_sink_source, user: data) < 0)
2937	r = isl_bool_error;
2938	isl_union_map_free(umap);
2939
2940	data->set_sink = 0;
2941	data->must = 0;
2942	umap = isl_union_map_copy(umap: data->access->access[isl_access_may_source]);
2943	umap = isl_union_map_apply_range(umap1: isl_union_map_copy(umap: prefix), umap2: umap);
2944	if (isl_union_map_foreach_map(umap, fn: &extract_sink_source, user: data) < 0)
2945	r = isl_bool_error;
2946	isl_union_map_free(umap);
2947
2948	isl_union_map_free(umap: prefix);
2949
2950	return r;
2951	}
2952
2953	/* isl_access_info_compute_flow callback for determining whether
2954	* the shared nesting level and the ordering within that level
2955	* for two scheduled accesses for use in compute_single_flow.
2956	*
2957	* The tokens passed to this function refer to the leaves
2958	* in the schedule tree where the accesses take place.
2959	*
2960	* If n is the shared number of loops, then we need to return
2961	* "2 * n + 1" if "first" precedes "second" inside the innermost
2962	* shared loop and "2 * n" otherwise.
2963	*
2964	* The innermost shared ancestor may be the leaves themselves
2965	* if the accesses take place in the same leaf. Otherwise,
2966	* it is either a set node or a sequence node. Only in the case
2967	* of a sequence node do we consider one access to precede the other.
2968	*/
2969	static int before_node(void *first, void *second)
2970	{
2971	isl_schedule_node *node1 = first;
2972	isl_schedule_node *node2 = second;
2973	isl_schedule_node *shared;
2974	isl_size depth;
2975	int before = 0;
2976
2977	shared = isl_schedule_node_get_shared_ancestor(node1, node2);
2978	depth = isl_schedule_node_get_schedule_depth(node: shared);
2979	if (depth < 0) {
2980	isl_schedule_node_free(node: shared);
2981	return -1;
2982	}
2983
2984	if (isl_schedule_node_get_type(node: shared) == isl_schedule_node_sequence) {
2985	isl_size pos1, pos2;
2986
2987	pos1 = isl_schedule_node_get_ancestor_child_position(node: node1,
2988	ancestor: shared);
2989	pos2 = isl_schedule_node_get_ancestor_child_position(node: node2,
2990	ancestor: shared);
2991	if (pos1 < 0 || pos2 < 0) {
2992	isl_schedule_node_free(node: shared);
2993	return -1;
2994	}
2995	before = pos1 < pos2;
2996	}
2997
2998	isl_schedule_node_free(node: shared);
2999
3000	return 2 * depth + before;
3001	}
3002
3003	/* Check if the given two accesses may be coscheduled.
3004	* If so, return isl_bool_true. Otherwise return isl_bool_false.
3005	*
3006	* Two accesses may only be coscheduled if they appear in the same leaf.
3007	*/
3008	static isl_bool coscheduled_node(void *first, void *second)
3009	{
3010	isl_schedule_node *node1 = first;
3011	isl_schedule_node *node2 = second;
3012
3013	return isl_bool_ok(b: node1 == node2);
3014	}
3015
3016	/* Add the scheduled sources from "data" that access
3017	* the same data space as "sink" to "access".
3018	*/
3019	static __isl_give isl_access_info *add_matching_sources(
3020	__isl_take isl_access_info *access, struct isl_scheduled_access *sink,
3021	struct isl_compute_flow_schedule_data *data)
3022	{
3023	int i;
3024	isl_space *space;
3025
3026	space = isl_space_range(space: isl_map_get_space(map: sink->access));
3027	for (i = 0; i < data->n_source; ++i) {
3028	struct isl_scheduled_access *source;
3029	isl_space *source_space;
3030	int eq;
3031
3032	source = &data->source[i];
3033	source_space = isl_map_get_space(map: source->access);
3034	source_space = isl_space_range(space: source_space);
3035	eq = isl_space_is_equal(space1: space, space2: source_space);
3036	isl_space_free(space: source_space);
3037
3038	if (!eq)
3039	continue;
3040	if (eq < 0)
3041	goto error;
3042
3043	access = isl_access_info_add_source(acc: access,
3044	source: isl_map_copy(map: source->access), must: source->must, source_user: source->node);
3045	}
3046
3047	isl_space_free(space);
3048	return access;
3049	error:
3050	isl_space_free(space);
3051	isl_access_info_free(acc: access);
3052	return NULL;
3053	}
3054
3055	/* Given a scheduled sink access relation "sink", compute the corresponding
3056	* dependences on the sources in "data" and add the computed dependences
3057	* to "uf".
3058	*
3059	* The dependences computed by access_info_compute_flow_core are of the form
3060	*
3061	* [S -> I] -> [[S' -> I'] -> A]
3062	*
3063	* The schedule dimensions are projected out by first currying the range,
3064	* resulting in
3065	*
3066	* [S -> I] -> [S' -> [I' -> A]]
3067	*
3068	* and then computing the factor range
3069	*
3070	* I -> [I' -> A]
3071	*/
3072	static __isl_give isl_union_flow *compute_single_flow(
3073	__isl_take isl_union_flow *uf, struct isl_scheduled_access *sink,
3074	struct isl_compute_flow_schedule_data *data)
3075	{
3076	int i;
3077	isl_access_info *access;
3078	isl_flow *flow;
3079	isl_map *map;
3080
3081	if (!uf)
3082	return NULL;
3083
3084	access = isl_access_info_alloc(sink: isl_map_copy(map: sink->access), sink_user: sink->node,
3085	fn: &before_node, max_source: data->n_source);
3086	if (access)
3087	access->coscheduled = &coscheduled_node;
3088	access = add_matching_sources(access, sink, data);
3089
3090	flow = access_info_compute_flow_core(acc: access);
3091	if (!flow)
3092	return isl_union_flow_free(flow: uf);
3093
3094	map = isl_map_domain_factor_range(map: isl_flow_get_no_source(deps: flow, must: 1));
3095	uf->must_no_source = isl_union_map_union(umap1: uf->must_no_source,
3096	umap2: isl_union_map_from_map(map));
3097	map = isl_map_domain_factor_range(map: isl_flow_get_no_source(deps: flow, must: 0));
3098	uf->may_no_source = isl_union_map_union(umap1: uf->may_no_source,
3099	umap2: isl_union_map_from_map(map));
3100
3101	for (i = 0; i < flow->n_source; ++i) {
3102	isl_union_map *dep;
3103
3104	map = isl_map_range_curry(map: isl_map_copy(map: flow->dep[i].map));
3105	map = isl_map_factor_range(map);
3106	dep = isl_union_map_from_map(map);
3107	if (flow->dep[i].must)
3108	uf->must_dep = isl_union_map_union(umap1: uf->must_dep, umap2: dep);
3109	else
3110	uf->may_dep = isl_union_map_union(umap1: uf->may_dep, umap2: dep);
3111	}
3112
3113	isl_flow_free(deps: flow);
3114
3115	return uf;
3116	}
3117
3118	/* Given a description of the "sink" accesses, the "source" accesses and
3119	* a schedule, compute for each instance of a sink access
3120	* and for each element accessed by that instance,
3121	* the possible or definite source accesses that last accessed the
3122	* element accessed by the sink access before this sink access
3123	* in the sense that there is no intermediate definite source access.
3124	* Only consider dependences between statement instances that belong
3125	* to the domain of the schedule.
3126	*
3127	* The must_no_source and may_no_source elements of the result
3128	* are subsets of access->sink. The elements must_dep and may_dep
3129	* map domain elements of access->{may,must)_source to
3130	* domain elements of access->sink.
3131	*
3132	* This function is used when a schedule tree representation
3133	* is available.
3134	*
3135	* We extract the individual scheduled source and sink access relations
3136	* (taking into account the domain of the schedule) and
3137	* then compute dependences for each scheduled sink individually.
3138	*/
3139	static __isl_give isl_union_flow *compute_flow_schedule(
3140	__isl_take isl_union_access_info *access)
3141	{
3142	struct isl_compute_flow_schedule_data data = { access };
3143	int i, n;
3144	isl_ctx *ctx;
3145	isl_space *space;
3146	isl_union_flow *flow;
3147
3148	ctx = isl_union_access_info_get_ctx(access);
3149
3150	data.n_sink = 0;
3151	data.n_source = 0;
3152	if (isl_schedule_foreach_schedule_node_top_down(sched: access->schedule,
3153	fn: &count_sink_source, user: &data) < 0)
3154	goto error;
3155
3156	n = data.n_sink + data.n_source;
3157	data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n);
3158	if (n && !data.sink)
3159	goto error;
3160	data.source = data.sink + data.n_sink;
3161
3162	data.n_sink = 0;
3163	data.n_source = 0;
3164	if (isl_schedule_foreach_schedule_node_top_down(sched: access->schedule,
3165	fn: &collect_sink_source, user: &data) < 0)
3166	goto error;
3167
3168	space = isl_union_map_get_space(umap: access->access[isl_access_sink]);
3169	flow = isl_union_flow_alloc(space);
3170
3171	isl_compute_flow_schedule_data_align_params(data: &data);
3172
3173	for (i = 0; i < data.n_sink; ++i)
3174	flow = compute_single_flow(uf: flow, sink: &data.sink[i], data: &data);
3175
3176	isl_compute_flow_schedule_data_clear(data: &data);
3177
3178	isl_union_access_info_free(access);
3179	return flow;
3180	error:
3181	isl_union_access_info_free(access);
3182	isl_compute_flow_schedule_data_clear(data: &data);
3183	return NULL;
3184	}
3185
3186	/* Given a description of the "sink" accesses, the "source" accesses and
3187	* a schedule, compute for each instance of a sink access
3188	* and for each element accessed by that instance,
3189	* the possible or definite source accesses that last accessed the
3190	* element accessed by the sink access before this sink access
3191	* in the sense that there is no intermediate definite source access.
3192	*
3193	* The must_no_source and may_no_source elements of the result
3194	* are subsets of access->sink. The elements must_dep and may_dep
3195	* map domain elements of access->{may,must)_source to
3196	* domain elements of access->sink.
3197	*
3198	* If any kills have been specified, then they are treated as
3199	* must-sources internally. Any dependence that purely derives
3200	* from an original kill is removed from the output.
3201	*
3202	* We check whether the schedule is available as a schedule tree
3203	* or a schedule map and call the corresponding function to perform
3204	* the analysis.
3205	*/
3206	__isl_give isl_union_flow *isl_union_access_info_compute_flow(
3207	__isl_take isl_union_access_info *access)
3208	{
3209	isl_bool has_kill;
3210	isl_union_map *must = NULL, *may = NULL;
3211	isl_union_flow *flow;
3212
3213	has_kill = isl_union_access_has_kill(info: access);
3214	if (has_kill < 0)
3215	goto error;
3216	if (has_kill) {
3217	must = isl_union_access_info_get_must_source(info: access);
3218	may = isl_union_access_info_get_may_source(info: access);
3219	}
3220	access = isl_union_access_info_add_kill_to_must_source(info: access);
3221	access = isl_union_access_info_normalize(access);
3222	if (!access)
3223	goto error;
3224	if (access->schedule)
3225	flow = compute_flow_schedule(access);
3226	else
3227	flow = compute_flow_union_map(access);
3228	if (has_kill)
3229	flow = isl_union_flow_drop_kill_source(flow, must, may);
3230	return flow;
3231	error:
3232	isl_union_access_info_free(access);
3233	isl_union_map_free(umap: must);
3234	isl_union_map_free(umap: may);
3235	return NULL;
3236	}
3237
3238	/* Print the information contained in "flow" to "p".
3239	* The information is printed as a YAML document.
3240	*/
3241	__isl_give isl_printer *isl_printer_print_union_flow(
3242	__isl_take isl_printer *p, __isl_keep isl_union_flow *flow)
3243	{
3244	isl_union_map *umap;
3245
3246	if (!flow)
3247	return isl_printer_free(printer: p);
3248
3249	p = isl_printer_yaml_start_mapping(p);
3250	umap = isl_union_flow_get_full_must_dependence(flow);
3251	p = print_yaml_field_union_map(p, name: "must_dependence", val: umap);
3252	isl_union_map_free(umap);
3253	umap = isl_union_flow_get_full_may_dependence(flow);
3254	p = print_yaml_field_union_map(p, name: "may_dependence", val: umap);
3255	isl_union_map_free(umap);
3256	p = print_yaml_field_union_map(p, name: "must_no_source",
3257	val: flow->must_no_source);
3258	umap = isl_union_flow_get_may_no_source(flow);
3259	p = print_yaml_field_union_map(p, name: "may_no_source", val: umap);
3260	isl_union_map_free(umap);
3261	p = isl_printer_yaml_end_mapping(p);
3262
3263	return p;
3264	}
3265
3266	/* Return a string representation of the information in "flow".
3267	* The information is printed in flow format.
3268	*/
3269	__isl_give char *isl_union_flow_to_str(__isl_keep isl_union_flow *flow)
3270	{
3271	isl_printer *p;
3272	char *s;
3273
3274	if (!flow)
3275	return NULL;
3276
3277	p = isl_printer_to_str(ctx: isl_union_flow_get_ctx(flow));
3278	p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
3279	p = isl_printer_print_union_flow(p, flow);
3280	s = isl_printer_get_str(printer: p);
3281	isl_printer_free(printer: p);
3282
3283	return s;
3284	}
3285
3286	/* Given a collection of "sink" and "source" accesses,
3287	* compute for each iteration of a sink access
3288	* and for each element accessed by that iteration,
3289	* the source access in the list that last accessed the
3290	* element accessed by the sink access before this sink access.
3291	* Each access is given as a map from the loop iterators
3292	* to the array indices.
3293	* The result is a relations between source and sink
3294	* iterations and a subset of the domain of the sink accesses,
3295	* corresponding to those iterations that access an element
3296	* not previously accessed.
3297	*
3298	* We collect the inputs in an isl_union_access_info object,
3299	* call isl_union_access_info_compute_flow and extract
3300	* the outputs from the result.
3301	*/
3302	int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
3303	__isl_take isl_union_map *must_source,
3304	__isl_take isl_union_map *may_source,
3305	__isl_take isl_union_map *schedule,
3306	__isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
3307	__isl_give isl_union_map **must_no_source,
3308	__isl_give isl_union_map **may_no_source)
3309	{
3310	isl_union_access_info *access;
3311	isl_union_flow *flow;
3312
3313	access = isl_union_access_info_from_sink(sink);
3314	access = isl_union_access_info_set_must_source(access, must_source);
3315	access = isl_union_access_info_set_may_source(access, may_source);
3316	access = isl_union_access_info_set_schedule_map(access, schedule_map: schedule);
3317	flow = isl_union_access_info_compute_flow(access);
3318
3319	if (must_dep)
3320	*must_dep = isl_union_flow_get_must_dependence(flow);
3321	if (may_dep)
3322	*may_dep = isl_union_flow_get_non_must_dependence(flow);
3323	if (must_no_source)
3324	*must_no_source = isl_union_flow_get_must_no_source(flow);
3325	if (may_no_source)
3326	*may_no_source = isl_union_flow_get_non_must_no_source(flow);
3327
3328	isl_union_flow_free(flow);
3329
3330	if ((must_dep && !*must_dep) || (may_dep && !*may_dep) ||
3331	(must_no_source && !*must_no_source) ||
3332	(may_no_source && !*may_no_source))
3333	goto error;
3334
3335	return 0;
3336	error:
3337	if (must_dep)
3338	*must_dep = isl_union_map_free(umap: *must_dep);
3339	if (may_dep)
3340	*may_dep = isl_union_map_free(umap: *may_dep);
3341	if (must_no_source)
3342	*must_no_source = isl_union_map_free(umap: *must_no_source);
3343	if (may_no_source)
3344	*may_no_source = isl_union_map_free(umap: *may_no_source);
3345	return -1;
3346	}
3347