• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2010-2011 INRIA Saclay
3  * Copyright 2013-2014 Ecole Normale Superieure
4  * Copyright 2014      INRIA Rocquencourt
5  * Copyright 2016-2017 Sven Verdoolaege
6  *
7  * Use of this software is governed by the MIT license
8  *
9  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11  * 91893 Orsay, France
12  * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
13  * B.P. 105 - 78153 Le Chesnay, France
14  */
15 
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl/ctx.h>
19 #include <isl/hash.h>
20 #include <isl_aff_private.h>
21 #include <isl/map.h>
22 #include <isl/set.h>
23 #include <isl_space_private.h>
24 #include <isl/union_set.h>
25 #include <isl_maybe_map.h>
26 #include <isl_id_private.h>
27 
28 #include <bset_from_bmap.c>
29 #include <set_to_map.c>
30 #include <set_from_map.c>
31 #include <uset_to_umap.c>
32 #include <uset_from_umap.c>
33 #include <set_list_from_map_list_inl.c>
34 
35 /* Return the number of parameters of "umap", where "type"
36  * is required to be set to isl_dim_param.
37  */
isl_union_map_dim(__isl_keep isl_union_map * umap,enum isl_dim_type type)38 isl_size isl_union_map_dim(__isl_keep isl_union_map *umap,
39 	enum isl_dim_type type)
40 {
41 	if (!umap)
42 		return isl_size_error;
43 
44 	if (type != isl_dim_param)
45 		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
46 			"can only reference parameters", return isl_size_error);
47 
48 	return isl_space_dim(umap->dim, type);
49 }
50 
51 /* Return the number of parameters of "uset", where "type"
52  * is required to be set to isl_dim_param.
53  */
isl_union_set_dim(__isl_keep isl_union_set * uset,enum isl_dim_type type)54 isl_size isl_union_set_dim(__isl_keep isl_union_set *uset,
55 	enum isl_dim_type type)
56 {
57 	return isl_union_map_dim(uset, type);
58 }
59 
60 /* Return the id of the specified dimension.
61  */
isl_union_map_get_dim_id(__isl_keep isl_union_map * umap,enum isl_dim_type type,unsigned pos)62 __isl_give isl_id *isl_union_map_get_dim_id(__isl_keep isl_union_map *umap,
63 	enum isl_dim_type type, unsigned pos)
64 {
65 	if (!umap)
66 		return NULL;
67 
68 	if (type != isl_dim_param)
69 		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
70 			"can only reference parameters", return NULL);
71 
72 	return isl_space_get_dim_id(umap->dim, type, pos);
73 }
74 
75 /* Is this union set a parameter domain?
76  */
isl_union_set_is_params(__isl_keep isl_union_set * uset)77 isl_bool isl_union_set_is_params(__isl_keep isl_union_set *uset)
78 {
79 	isl_set *set;
80 	isl_bool params;
81 
82 	if (!uset)
83 		return isl_bool_error;
84 	if (uset->table.n != 1)
85 		return isl_bool_false;
86 
87 	set = isl_set_from_union_set(isl_union_set_copy(uset));
88 	params = isl_set_is_params(set);
89 	isl_set_free(set);
90 	return params;
91 }
92 
93 /* Is this union map actually a parameter domain?
94  * Users should never call this function.  Outside of isl,
95  * a union map can never be a parameter domain.
96  */
isl_union_map_is_params(__isl_keep isl_union_map * umap)97 isl_bool isl_union_map_is_params(__isl_keep isl_union_map *umap)
98 {
99 	return isl_union_set_is_params(uset_from_umap(umap));
100 }
101 
isl_union_map_alloc(__isl_take isl_space * space,int size)102 static __isl_give isl_union_map *isl_union_map_alloc(
103 	__isl_take isl_space *space, int size)
104 {
105 	isl_union_map *umap;
106 
107 	space = isl_space_params(space);
108 	if (!space)
109 		return NULL;
110 
111 	umap = isl_calloc_type(space->ctx, isl_union_map);
112 	if (!umap) {
113 		isl_space_free(space);
114 		return NULL;
115 	}
116 
117 	umap->ref = 1;
118 	umap->dim = space;
119 	if (isl_hash_table_init(space->ctx, &umap->table, size) < 0)
120 		return isl_union_map_free(umap);
121 
122 	return umap;
123 }
124 
125 /* Create an empty union map without specifying any parameters.
126  */
isl_union_map_empty_ctx(isl_ctx * ctx)127 __isl_give isl_union_map *isl_union_map_empty_ctx(isl_ctx *ctx)
128 {
129 	return isl_union_map_empty_space(isl_space_unit(ctx));
130 }
131 
isl_union_map_empty_space(__isl_take isl_space * space)132 __isl_give isl_union_map *isl_union_map_empty_space(__isl_take isl_space *space)
133 {
134 	return isl_union_map_alloc(space, 16);
135 }
136 
137 /* This is an alternative name for the function above.
138  */
isl_union_map_empty(__isl_take isl_space * space)139 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *space)
140 {
141 	return isl_union_map_empty_space(space);
142 }
143 
144 /* Create an empty union set without specifying any parameters.
145  */
isl_union_set_empty_ctx(isl_ctx * ctx)146 __isl_give isl_union_set *isl_union_set_empty_ctx(isl_ctx *ctx)
147 {
148 	return uset_from_umap(isl_union_map_empty_ctx(ctx));
149 }
150 
isl_union_set_empty_space(__isl_take isl_space * space)151 __isl_give isl_union_set *isl_union_set_empty_space(__isl_take isl_space *space)
152 {
153 	return uset_from_umap(isl_union_map_empty_space(space));
154 }
155 
156 /* This is an alternative name for the function above.
157  */
isl_union_set_empty(__isl_take isl_space * space)158 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *space)
159 {
160 	return isl_union_set_empty_space(space);
161 }
162 
isl_union_map_get_ctx(__isl_keep isl_union_map * umap)163 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
164 {
165 	return umap ? umap->dim->ctx : NULL;
166 }
167 
isl_union_set_get_ctx(__isl_keep isl_union_set * uset)168 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
169 {
170 	return uset ? uset->dim->ctx : NULL;
171 }
172 
173 /* Return the space of "umap".
174  */
isl_union_map_peek_space(__isl_keep isl_union_map * umap)175 __isl_keep isl_space *isl_union_map_peek_space(__isl_keep isl_union_map *umap)
176 {
177 	return umap ? umap->dim : NULL;
178 }
179 
180 /* Return the space of "uset".
181  */
isl_union_set_peek_space(__isl_keep isl_union_set * uset)182 __isl_keep isl_space *isl_union_set_peek_space(__isl_keep isl_union_set *uset)
183 {
184 	return isl_union_map_peek_space(uset_to_umap(uset));
185 }
186 
isl_union_map_get_space(__isl_keep isl_union_map * umap)187 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
188 {
189 	return isl_space_copy(isl_union_map_peek_space(umap));
190 }
191 
192 /* Return the position of the parameter with the given name
193  * in "umap".
194  * Return -1 if no such dimension can be found.
195  */
isl_union_map_find_dim_by_name(__isl_keep isl_union_map * umap,enum isl_dim_type type,const char * name)196 int isl_union_map_find_dim_by_name(__isl_keep isl_union_map *umap,
197 	enum isl_dim_type type, const char *name)
198 {
199 	if (!umap)
200 		return -1;
201 	return isl_space_find_dim_by_name(umap->dim, type, name);
202 }
203 
isl_union_set_get_space(__isl_keep isl_union_set * uset)204 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
205 {
206 	return isl_union_map_get_space(uset);
207 }
208 
free_umap_entry(void ** entry,void * user)209 static isl_stat free_umap_entry(void **entry, void *user)
210 {
211 	isl_map *map = *entry;
212 	isl_map_free(map);
213 	return isl_stat_ok;
214 }
215 
add_map(__isl_take isl_map * map,void * user)216 static isl_stat add_map(__isl_take isl_map *map, void *user)
217 {
218 	isl_union_map **umap = (isl_union_map **)user;
219 
220 	*umap = isl_union_map_add_map(*umap, map);
221 
222 	return isl_stat_ok;
223 }
224 
isl_union_map_dup(__isl_keep isl_union_map * umap)225 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
226 {
227 	isl_union_map *dup;
228 
229 	if (!umap)
230 		return NULL;
231 
232 	dup = isl_union_map_empty(isl_space_copy(umap->dim));
233 	if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
234 		goto error;
235 	return dup;
236 error:
237 	isl_union_map_free(dup);
238 	return NULL;
239 }
240 
isl_union_map_cow(__isl_take isl_union_map * umap)241 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
242 {
243 	if (!umap)
244 		return NULL;
245 
246 	if (umap->ref == 1)
247 		return umap;
248 	umap->ref--;
249 	return isl_union_map_dup(umap);
250 }
251 
252 struct isl_union_align {
253 	isl_reordering *exp;
254 	isl_union_map *res;
255 };
256 
align_entry(void ** entry,void * user)257 static isl_stat align_entry(void **entry, void *user)
258 {
259 	isl_map *map = *entry;
260 	isl_reordering *exp;
261 	struct isl_union_align *data = user;
262 
263 	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
264 				    isl_map_get_space(map));
265 
266 	data->res = isl_union_map_add_map(data->res,
267 					isl_map_realign(isl_map_copy(map), exp));
268 
269 	return isl_stat_ok;
270 }
271 
272 /* Align the parameters of umap along those of model.
273  * The result has the parameters of model first, in the same order
274  * as they appear in model, followed by any remaining parameters of
275  * umap that do not appear in model.
276  */
isl_union_map_align_params(__isl_take isl_union_map * umap,__isl_take isl_space * model)277 __isl_give isl_union_map *isl_union_map_align_params(
278 	__isl_take isl_union_map *umap, __isl_take isl_space *model)
279 {
280 	struct isl_union_align data = { NULL, NULL };
281 	isl_bool equal_params;
282 
283 	if (!umap || !model)
284 		goto error;
285 
286 	equal_params = isl_space_has_equal_params(umap->dim, model);
287 	if (equal_params < 0)
288 		goto error;
289 	if (equal_params) {
290 		isl_space_free(model);
291 		return umap;
292 	}
293 
294 	data.exp = isl_parameter_alignment_reordering(umap->dim, model);
295 	if (!data.exp)
296 		goto error;
297 
298 	data.res = isl_union_map_alloc(isl_reordering_get_space(data.exp),
299 					umap->table.n);
300 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
301 					&align_entry, &data) < 0)
302 		goto error;
303 
304 	isl_reordering_free(data.exp);
305 	isl_union_map_free(umap);
306 	isl_space_free(model);
307 	return data.res;
308 error:
309 	isl_reordering_free(data.exp);
310 	isl_union_map_free(umap);
311 	isl_union_map_free(data.res);
312 	isl_space_free(model);
313 	return NULL;
314 }
315 
isl_union_set_align_params(__isl_take isl_union_set * uset,__isl_take isl_space * model)316 __isl_give isl_union_set *isl_union_set_align_params(
317 	__isl_take isl_union_set *uset, __isl_take isl_space *model)
318 {
319 	return isl_union_map_align_params(uset, model);
320 }
321 
isl_union_map_union(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)322 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
323 	__isl_take isl_union_map *umap2)
324 {
325 	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
326 	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
327 
328 	umap1 = isl_union_map_cow(umap1);
329 
330 	if (!umap1 || !umap2)
331 		goto error;
332 
333 	if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
334 		goto error;
335 
336 	isl_union_map_free(umap2);
337 
338 	return umap1;
339 error:
340 	isl_union_map_free(umap1);
341 	isl_union_map_free(umap2);
342 	return NULL;
343 }
344 
isl_union_set_union(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)345 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
346 	__isl_take isl_union_set *uset2)
347 {
348 	return isl_union_map_union(uset1, uset2);
349 }
350 
isl_union_map_copy(__isl_keep isl_union_map * umap)351 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
352 {
353 	if (!umap)
354 		return NULL;
355 
356 	umap->ref++;
357 	return umap;
358 }
359 
isl_union_set_copy(__isl_keep isl_union_set * uset)360 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
361 {
362 	return isl_union_map_copy(uset);
363 }
364 
isl_union_map_free(__isl_take isl_union_map * umap)365 __isl_null isl_union_map *isl_union_map_free(__isl_take isl_union_map *umap)
366 {
367 	if (!umap)
368 		return NULL;
369 
370 	if (--umap->ref > 0)
371 		return NULL;
372 
373 	isl_hash_table_foreach(umap->dim->ctx, &umap->table,
374 			       &free_umap_entry, NULL);
375 	isl_hash_table_clear(&umap->table);
376 	isl_space_free(umap->dim);
377 	free(umap);
378 	return NULL;
379 }
380 
isl_union_set_free(__isl_take isl_union_set * uset)381 __isl_null isl_union_set *isl_union_set_free(__isl_take isl_union_set *uset)
382 {
383 	return isl_union_map_free(uset);
384 }
385 
386 /* Do "umap" and "space" have the same parameters?
387  */
isl_union_map_space_has_equal_params(__isl_keep isl_union_map * umap,__isl_keep isl_space * space)388 isl_bool isl_union_map_space_has_equal_params(__isl_keep isl_union_map *umap,
389 	__isl_keep isl_space *space)
390 {
391 	isl_space *umap_space;
392 
393 	umap_space = isl_union_map_peek_space(umap);
394 	return isl_space_has_equal_params(umap_space, space);
395 }
396 
397 /* Do "uset" and "space" have the same parameters?
398  */
isl_union_set_space_has_equal_params(__isl_keep isl_union_set * uset,__isl_keep isl_space * space)399 isl_bool isl_union_set_space_has_equal_params(__isl_keep isl_union_set *uset,
400 	__isl_keep isl_space *space)
401 {
402 	return isl_union_map_space_has_equal_params(uset_to_umap(uset), space);
403 }
404 
has_space(const void * entry,const void * val)405 static isl_bool has_space(const void *entry, const void *val)
406 {
407 	isl_map *map = (isl_map *)entry;
408 	isl_space *space = (isl_space *) val;
409 
410 	return isl_space_is_equal(map->dim, space);
411 }
412 
isl_union_map_add_map(__isl_take isl_union_map * umap,__isl_take isl_map * map)413 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
414 	__isl_take isl_map *map)
415 {
416 	uint32_t hash;
417 	struct isl_hash_table_entry *entry;
418 	isl_bool aligned;
419 
420 	if (!map || !umap)
421 		goto error;
422 
423 	if (isl_map_plain_is_empty(map)) {
424 		isl_map_free(map);
425 		return umap;
426 	}
427 
428 	aligned = isl_map_space_has_equal_params(map, umap->dim);
429 	if (aligned < 0)
430 		goto error;
431 	if (!aligned) {
432 		umap = isl_union_map_align_params(umap, isl_map_get_space(map));
433 		map = isl_map_align_params(map, isl_union_map_get_space(umap));
434 	}
435 
436 	umap = isl_union_map_cow(umap);
437 
438 	if (!map || !umap)
439 		goto error;
440 
441 	hash = isl_space_get_hash(map->dim);
442 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
443 				    &has_space, map->dim, 1);
444 	if (!entry)
445 		goto error;
446 
447 	if (!entry->data)
448 		entry->data = map;
449 	else {
450 		entry->data = isl_map_union(entry->data, isl_map_copy(map));
451 		if (!entry->data)
452 			goto error;
453 		isl_map_free(map);
454 	}
455 
456 	return umap;
457 error:
458 	isl_map_free(map);
459 	isl_union_map_free(umap);
460 	return NULL;
461 }
462 
isl_union_set_add_set(__isl_take isl_union_set * uset,__isl_take isl_set * set)463 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
464 	__isl_take isl_set *set)
465 {
466 	return isl_union_map_add_map(uset, set_to_map(set));
467 }
468 
isl_union_map_from_map(__isl_take isl_map * map)469 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
470 {
471 	isl_space *space;
472 	isl_union_map *umap;
473 
474 	if (!map)
475 		return NULL;
476 
477 	space = isl_map_get_space(map);
478 	space = isl_space_params(space);
479 	umap = isl_union_map_empty(space);
480 	umap = isl_union_map_add_map(umap, map);
481 
482 	return umap;
483 }
484 
isl_union_set_from_set(__isl_take isl_set * set)485 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
486 {
487 	return isl_union_map_from_map(set_to_map(set));
488 }
489 
isl_union_map_from_basic_map(__isl_take isl_basic_map * bmap)490 __isl_give isl_union_map *isl_union_map_from_basic_map(
491 	__isl_take isl_basic_map *bmap)
492 {
493 	return isl_union_map_from_map(isl_map_from_basic_map(bmap));
494 }
495 
isl_union_set_from_basic_set(__isl_take isl_basic_set * bset)496 __isl_give isl_union_set *isl_union_set_from_basic_set(
497 	__isl_take isl_basic_set *bset)
498 {
499 	return isl_union_map_from_basic_map(bset);
500 }
501 
502 struct isl_union_map_foreach_data
503 {
504 	isl_stat (*fn)(__isl_take isl_map *map, void *user);
505 	void *user;
506 };
507 
call_on_copy(void ** entry,void * user)508 static isl_stat call_on_copy(void **entry, void *user)
509 {
510 	isl_map *map = *entry;
511 	struct isl_union_map_foreach_data *data;
512 	data = (struct isl_union_map_foreach_data *)user;
513 
514 	return data->fn(isl_map_copy(map), data->user);
515 }
516 
isl_union_map_n_map(__isl_keep isl_union_map * umap)517 isl_size isl_union_map_n_map(__isl_keep isl_union_map *umap)
518 {
519 	return umap ? umap->table.n : isl_size_error;
520 }
521 
isl_union_set_n_set(__isl_keep isl_union_set * uset)522 isl_size isl_union_set_n_set(__isl_keep isl_union_set *uset)
523 {
524 	return uset ? uset->table.n : isl_size_error;
525 }
526 
isl_union_map_foreach_map(__isl_keep isl_union_map * umap,isl_stat (* fn)(__isl_take isl_map * map,void * user),void * user)527 isl_stat isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
528 	isl_stat (*fn)(__isl_take isl_map *map, void *user), void *user)
529 {
530 	struct isl_union_map_foreach_data data = { fn, user };
531 
532 	if (!umap)
533 		return isl_stat_error;
534 
535 	return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
536 				      &call_on_copy, &data);
537 }
538 
539 /* Internal data structure for isl_union_map_every_map.
540  *
541  * "test" is the user-specified callback function.
542  * "user" is the user-specified callback function argument.
543  *
544  * "failed" is initialized to 0 and set to 1 if "test" fails
545  * on any map.
546  */
547 struct isl_union_map_every_data {
548 	isl_bool (*test)(__isl_keep isl_map *map, void *user);
549 	void *user;
550 	int failed;
551 };
552 
553 /* Call data->test on "map".
554  * If this fails, then set data->failed and abort.
555  */
call_every(void ** entry,void * user)556 static isl_stat call_every(void **entry, void *user)
557 {
558 	isl_map *map = *entry;
559 	struct isl_union_map_every_data *data = user;
560 	isl_bool r;
561 
562 	r = data->test(map, data->user);
563 	if (r < 0)
564 		return isl_stat_error;
565 	if (r)
566 		return isl_stat_ok;
567 	data->failed = 1;
568 	return isl_stat_error;
569 }
570 
571 /* Does "test" succeed on every map in "umap"?
572  */
isl_union_map_every_map(__isl_keep isl_union_map * umap,isl_bool (* test)(__isl_keep isl_map * map,void * user),void * user)573 isl_bool isl_union_map_every_map(__isl_keep isl_union_map *umap,
574 	isl_bool (*test)(__isl_keep isl_map *map, void *user), void *user)
575 {
576 	struct isl_union_map_every_data data = { test, user, 0 };
577 	isl_stat r;
578 
579 	if (!umap)
580 		return isl_bool_error;
581 
582 	r = isl_hash_table_foreach(isl_union_map_get_ctx(umap), &umap->table,
583 				      &call_every, &data);
584 	if (r >= 0)
585 		return isl_bool_true;
586 	if (data.failed)
587 		return isl_bool_false;
588 	return isl_bool_error;
589 }
590 
591 /* Add "map" to "list".
592  */
add_list_map(__isl_take isl_map * map,void * user)593 static isl_stat add_list_map(__isl_take isl_map *map, void *user)
594 {
595 	isl_map_list **list = user;
596 
597 	*list = isl_map_list_add(*list, map);
598 
599 	if (!*list)
600 		return isl_stat_error;
601 	return isl_stat_ok;
602 }
603 
604 /* Return the maps in "umap" as a list.
605  *
606  * First construct a list of the appropriate size and then add all the
607  * elements.
608  */
isl_union_map_get_map_list(__isl_keep isl_union_map * umap)609 __isl_give isl_map_list *isl_union_map_get_map_list(
610 	__isl_keep isl_union_map *umap)
611 {
612 	isl_size n_maps;
613 	isl_ctx *ctx;
614 	isl_map_list *list;
615 
616 	n_maps = isl_union_map_n_map(umap);
617 	if (n_maps < 0)
618 		return NULL;
619 	ctx = isl_union_map_get_ctx(umap);
620 	list = isl_map_list_alloc(ctx, n_maps);
621 
622 	if (isl_union_map_foreach_map(umap, &add_list_map, &list) < 0)
623 		list = isl_map_list_free(list);
624 
625 	return list;
626 }
627 
628 /* Return the sets in "uset" as a list.
629  */
isl_union_set_get_set_list(__isl_keep isl_union_set * uset)630 __isl_give isl_set_list *isl_union_set_get_set_list(
631 	__isl_keep isl_union_set *uset)
632 {
633 	return set_list_from_map_list(
634 		isl_union_map_get_map_list(uset_to_umap(uset)));
635 }
636 
637 /* Can "umap" be converted to an isl_map?
638  * That is, does it contain elements in exactly one space?
639  */
isl_union_map_isa_map(__isl_keep isl_union_map * umap)640 isl_bool isl_union_map_isa_map(__isl_keep isl_union_map *umap)
641 {
642 	isl_size n;
643 
644 	n = isl_union_map_n_map(umap);
645 	if (n < 0)
646 		return isl_bool_error;
647 	return isl_bool_ok(n == 1);
648 }
649 
650 /* Can "uset" be converted to an isl_set?
651  * That is, does it contain elements in exactly one space?
652  */
isl_union_set_isa_set(__isl_keep isl_union_set * uset)653 isl_bool isl_union_set_isa_set(__isl_keep isl_union_set *uset)
654 {
655 	return isl_union_map_isa_map(uset_to_umap(uset));
656 }
657 
copy_map(void ** entry,void * user)658 static isl_stat copy_map(void **entry, void *user)
659 {
660 	isl_map *map = *entry;
661 	isl_map **map_p = user;
662 
663 	*map_p = isl_map_copy(map);
664 
665 	return isl_stat_error;
666 }
667 
isl_map_from_union_map(__isl_take isl_union_map * umap)668 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
669 {
670 	isl_bool is_map;
671 	isl_ctx *ctx;
672 	isl_map *map = NULL;
673 
674 	is_map = isl_union_map_isa_map(umap);
675 	if (is_map < 0)
676 		goto error;
677 	ctx = isl_union_map_get_ctx(umap);
678 	if (!is_map)
679 		isl_die(ctx, isl_error_invalid,
680 			"union map needs to contain elements in exactly "
681 			"one space", goto error);
682 
683 	isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
684 
685 	isl_union_map_free(umap);
686 
687 	return map;
688 error:
689 	isl_union_map_free(umap);
690 	return NULL;
691 }
692 
isl_set_from_union_set(__isl_take isl_union_set * uset)693 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
694 {
695 	return isl_map_from_union_map(uset);
696 }
697 
698 /* Extract the map in "umap" that lives in the given space (ignoring
699  * parameters).
700  */
isl_union_map_extract_map(__isl_keep isl_union_map * umap,__isl_take isl_space * space)701 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
702 	__isl_take isl_space *space)
703 {
704 	uint32_t hash;
705 	struct isl_hash_table_entry *entry;
706 
707 	space = isl_space_drop_all_params(space);
708 	space = isl_space_align_params(space, isl_union_map_get_space(umap));
709 	if (!umap || !space)
710 		goto error;
711 
712 	hash = isl_space_get_hash(space);
713 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
714 				    &has_space, space, 0);
715 	if (!entry)
716 		goto error;
717 	if (entry == isl_hash_table_entry_none)
718 		return isl_map_empty(space);
719 	isl_space_free(space);
720 	return isl_map_copy(entry->data);
721 error:
722 	isl_space_free(space);
723 	return NULL;
724 }
725 
isl_union_set_extract_set(__isl_keep isl_union_set * uset,__isl_take isl_space * space)726 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
727 	__isl_take isl_space *space)
728 {
729 	return set_from_map(isl_union_map_extract_map(uset, space));
730 }
731 
732 /* Check if umap contains a map in the given space (ignoring parameters).
733  */
isl_union_map_contains(__isl_keep isl_union_map * umap,__isl_keep isl_space * space)734 isl_bool isl_union_map_contains(__isl_keep isl_union_map *umap,
735 	__isl_keep isl_space *space)
736 {
737 	uint32_t hash;
738 	struct isl_hash_table_entry *entry;
739 
740 	space = isl_space_drop_all_params(isl_space_copy(space));
741 	space = isl_space_align_params(space, isl_union_map_get_space(umap));
742 	if (!space)
743 		return isl_bool_error;
744 
745 	hash = isl_space_get_hash(space);
746 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
747 				    &has_space, space, 0);
748 	isl_space_free(space);
749 	if (!entry)
750 		return isl_bool_error;
751 	return isl_bool_ok(entry != isl_hash_table_entry_none);
752 }
753 
isl_union_set_contains(__isl_keep isl_union_set * uset,__isl_keep isl_space * space)754 isl_bool isl_union_set_contains(__isl_keep isl_union_set *uset,
755 	__isl_keep isl_space *space)
756 {
757 	return isl_union_map_contains(uset, space);
758 }
759 
isl_union_set_foreach_set(__isl_keep isl_union_set * uset,isl_stat (* fn)(__isl_take isl_set * set,void * user),void * user)760 isl_stat isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
761 	isl_stat (*fn)(__isl_take isl_set *set, void *user), void *user)
762 {
763 	return isl_union_map_foreach_map(uset,
764 		(isl_stat(*)(__isl_take isl_map *, void*))fn, user);
765 }
766 
767 /* Internal data structure for isl_union_set_every_set.
768  *
769  * "test" is the user-specified callback function.
770  * "user" is the user-specified callback function argument.
771  */
772 struct isl_test_set_from_map_data {
773 	isl_bool (*test)(__isl_keep isl_set *set, void *user);
774 	void *user;
775 };
776 
777 /* Call data->test on "map", which is part of an isl_union_set and
778  * therefore known to be an isl_set.
779  */
test_set_from_map(__isl_keep isl_map * map,void * user)780 static isl_bool test_set_from_map(__isl_keep isl_map *map, void *user)
781 {
782 	struct isl_test_set_from_map_data *data = user;
783 
784 	return data->test(set_from_map(map), data->user);
785 }
786 
787 /* Does "test" succeed on every set in "uset"?
788  */
isl_union_set_every_set(__isl_keep isl_union_set * uset,isl_bool (* test)(__isl_keep isl_set * set,void * user),void * user)789 isl_bool isl_union_set_every_set(__isl_keep isl_union_set *uset,
790 	isl_bool (*test)(__isl_keep isl_set *set, void *user), void *user)
791 {
792 	struct isl_test_set_from_map_data data = { test, user };
793 
794 	return isl_union_map_every_map(uset_to_umap(uset),
795 					&test_set_from_map, &data);
796 }
797 
798 struct isl_union_set_foreach_point_data {
799 	isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
800 	void *user;
801 };
802 
foreach_point(__isl_take isl_set * set,void * user)803 static isl_stat foreach_point(__isl_take isl_set *set, void *user)
804 {
805 	struct isl_union_set_foreach_point_data *data = user;
806 	isl_stat r;
807 
808 	r = isl_set_foreach_point(set, data->fn, data->user);
809 	isl_set_free(set);
810 
811 	return r;
812 }
813 
isl_union_set_foreach_point(__isl_keep isl_union_set * uset,isl_stat (* fn)(__isl_take isl_point * pnt,void * user),void * user)814 isl_stat isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
815 	isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
816 {
817 	struct isl_union_set_foreach_point_data data = { fn, user };
818 	return isl_union_set_foreach_set(uset, &foreach_point, &data);
819 }
820 
821 /* Data structure that specifies how gen_bin_op should
822  * construct results from the inputs.
823  *
824  * If "subtract" is set, then a map in the first input is copied to the result
825  * if there is no corresponding map in the second input.
826  * Otherwise, a map in the first input with no corresponding map
827  * in the second input is ignored.
828  * If "filter" is not NULL, then it specifies which maps in the first
829  * input may have a matching map in the second input.
830  * In particular, it makes sure that "match_space" can be called
831  * on the space of the map.
832  * "match_space" specifies how to transform the space of a map
833  * in the first input to the space of the corresponding map
834  * in the second input.
835  * "fn_map" specifies how the matching maps, one from each input,
836  * should be combined to form a map in the result.
837  */
838 struct isl_bin_op_control {
839 	int subtract;
840 	isl_bool (*filter)(__isl_keep isl_map *map);
841 	__isl_give isl_space *(*match_space)(__isl_take isl_space *space);
842 	__isl_give isl_map *(*fn_map)(__isl_take isl_map *map1,
843 		__isl_take isl_map *map2);
844 };
845 
846 /* Internal data structure for gen_bin_op.
847  * "control" specifies how the maps in the result should be constructed.
848  * "umap2" is a pointer to the second argument.
849  * "res" collects the results.
850  */
851 struct isl_union_map_gen_bin_data {
852 	struct isl_bin_op_control *control;
853 	isl_union_map *umap2;
854 	isl_union_map *res;
855 };
856 
857 /* Add a copy of "map" to "res" and return the result.
858  */
bin_add_map(__isl_take isl_union_map * res,__isl_keep isl_map * map)859 static __isl_give isl_union_map *bin_add_map(__isl_take isl_union_map *res,
860 	__isl_keep isl_map *map)
861 {
862 	return isl_union_map_add_map(res, isl_map_copy(map));
863 }
864 
865 /* Combine "map1" and "map2", add the result to "res" and return the result.
866  * Check whether the result is empty before adding it to "res".
867  */
bin_add_pair(__isl_take isl_union_map * res,__isl_keep isl_map * map1,__isl_keep isl_map * map2,struct isl_union_map_gen_bin_data * data)868 static __isl_give isl_union_map *bin_add_pair(__isl_take isl_union_map *res,
869 	__isl_keep isl_map *map1, __isl_keep isl_map *map2,
870 	struct isl_union_map_gen_bin_data *data)
871 {
872 	isl_bool empty;
873 	isl_map *map;
874 
875 	map = data->control->fn_map(isl_map_copy(map1), isl_map_copy(map2));
876 	empty = isl_map_is_empty(map);
877 	if (empty < 0 || empty) {
878 		isl_map_free(map);
879 		if (empty < 0)
880 			return isl_union_map_free(res);
881 		return res;
882 	}
883 	return isl_union_map_add_map(res, map);
884 }
885 
886 /* Dummy match_space function that simply returns the input space.
887  */
identity(__isl_take isl_space * space)888 static __isl_give isl_space *identity(__isl_take isl_space *space)
889 {
890 	return space;
891 }
892 
893 /* Look for the map in data->umap2 that corresponds to "map", if any.
894  * Return (isl_bool_true, matching map) if there is one,
895  * (isl_bool_false, NULL) if there is no matching map and
896  * (isl_bool_error, NULL) on error.
897  *
898  * If not NULL, then data->control->filter specifies whether "map"
899  * can have any matching map.  If so,
900  * data->control->match_space specifies which map in data->umap2
901  * corresponds to "map".
902  */
bin_try_get_match(struct isl_union_map_gen_bin_data * data,__isl_keep isl_map * map)903 static __isl_keep isl_maybe_isl_map bin_try_get_match(
904 	struct isl_union_map_gen_bin_data *data, __isl_keep isl_map *map)
905 {
906 	uint32_t hash;
907 	struct isl_hash_table_entry *entry2;
908 	isl_space *space;
909 	isl_maybe_isl_map res = { isl_bool_error, NULL };
910 
911 	if (data->control->filter) {
912 		res.valid = data->control->filter(map);
913 		if (res.valid < 0 || !res.valid)
914 			return res;
915 		res.valid = isl_bool_error;
916 	}
917 
918 	space = isl_map_get_space(map);
919 	if (data->control->match_space != &identity)
920 		space = data->control->match_space(space);
921 	if (!space)
922 		return res;
923 	hash = isl_space_get_hash(space);
924 	entry2 = isl_hash_table_find(isl_union_map_get_ctx(data->umap2),
925 				     &data->umap2->table, hash,
926 				     &has_space, space, 0);
927 	isl_space_free(space);
928 	if (entry2)
929 		res.valid = isl_bool_ok(entry2 != isl_hash_table_entry_none);
930 	if (res.valid >= 0 && res.valid)
931 		res.value = entry2->data;
932 
933 	return res;
934 }
935 
936 /* isl_hash_table_foreach callback for gen_bin_op.
937  * Look for the map in data->umap2 that corresponds
938  * to the map that "entry" points to, apply the binary operation and
939  * add the result to data->res.
940  *
941  * If no corresponding map can be found, then the effect depends
942  * on data->control->subtract.  If it is set, then the current map
943  * is added directly to the result.  Otherwise, it is ignored.
944  */
gen_bin_entry(void ** entry,void * user)945 static isl_stat gen_bin_entry(void **entry, void *user)
946 {
947 	struct isl_union_map_gen_bin_data *data = user;
948 	isl_map *map = *entry;
949 	isl_maybe_isl_map m;
950 
951 	m = bin_try_get_match(data, map);
952 	if (m.valid < 0)
953 		return isl_stat_error;
954 	if (!m.valid && !data->control->subtract)
955 		return isl_stat_ok;
956 
957 	if (!m.valid)
958 		data->res = bin_add_map(data->res, map);
959 	else
960 		data->res = bin_add_pair(data->res, map, m.value, data);
961 	if (!data->res)
962 		return isl_stat_error;
963 
964 	return isl_stat_ok;
965 }
966 
967 /* Apply a binary operation to "umap1" and "umap2" based on "control".
968  * Run over all maps in "umap1" and look for the corresponding map in "umap2"
969  * in gen_bin_entry.
970  */
gen_bin_op(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2,struct isl_bin_op_control * control)971 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
972 	__isl_take isl_union_map *umap2, struct isl_bin_op_control *control)
973 {
974 	struct isl_union_map_gen_bin_data data = { control, NULL, NULL };
975 
976 	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
977 	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
978 
979 	if (!umap1 || !umap2)
980 		goto error;
981 
982 	data.umap2 = umap2;
983 	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
984 				       umap1->table.n);
985 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
986 				   &gen_bin_entry, &data) < 0)
987 		goto error;
988 
989 	isl_union_map_free(umap1);
990 	isl_union_map_free(umap2);
991 	return data.res;
992 error:
993 	isl_union_map_free(umap1);
994 	isl_union_map_free(umap2);
995 	isl_union_map_free(data.res);
996 	return NULL;
997 }
998 
isl_union_map_subtract(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)999 __isl_give isl_union_map *isl_union_map_subtract(
1000 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1001 {
1002 	struct isl_bin_op_control control = {
1003 		.subtract = 1,
1004 		.match_space = &identity,
1005 		.fn_map = &isl_map_subtract,
1006 	};
1007 
1008 	return gen_bin_op(umap1, umap2, &control);
1009 }
1010 
isl_union_set_subtract(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1011 __isl_give isl_union_set *isl_union_set_subtract(
1012 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1013 {
1014 	return isl_union_map_subtract(uset1, uset2);
1015 }
1016 
1017 struct isl_union_map_gen_bin_set_data {
1018 	isl_set *set;
1019 	isl_union_map *res;
1020 };
1021 
intersect_params_entry(void ** entry,void * user)1022 static isl_stat intersect_params_entry(void **entry, void *user)
1023 {
1024 	struct isl_union_map_gen_bin_set_data *data = user;
1025 	isl_map *map = *entry;
1026 	int empty;
1027 
1028 	map = isl_map_copy(map);
1029 	map = isl_map_intersect_params(map, isl_set_copy(data->set));
1030 
1031 	empty = isl_map_is_empty(map);
1032 	if (empty < 0) {
1033 		isl_map_free(map);
1034 		return isl_stat_error;
1035 	}
1036 
1037 	data->res = isl_union_map_add_map(data->res, map);
1038 
1039 	return isl_stat_ok;
1040 }
1041 
gen_bin_set_op(__isl_take isl_union_map * umap,__isl_take isl_set * set,isl_stat (* fn)(void **,void *))1042 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
1043 	__isl_take isl_set *set, isl_stat (*fn)(void **, void *))
1044 {
1045 	struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
1046 
1047 	umap = isl_union_map_align_params(umap, isl_set_get_space(set));
1048 	set = isl_set_align_params(set, isl_union_map_get_space(umap));
1049 
1050 	if (!umap || !set)
1051 		goto error;
1052 
1053 	data.set = set;
1054 	data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
1055 				       umap->table.n);
1056 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1057 				   fn, &data) < 0)
1058 		goto error;
1059 
1060 	isl_union_map_free(umap);
1061 	isl_set_free(set);
1062 	return data.res;
1063 error:
1064 	isl_union_map_free(umap);
1065 	isl_set_free(set);
1066 	isl_union_map_free(data.res);
1067 	return NULL;
1068 }
1069 
1070 /* Intersect "umap" with the parameter domain "set".
1071  *
1072  * If "set" does not have any constraints, then we can return immediately.
1073  */
isl_union_map_intersect_params(__isl_take isl_union_map * umap,__isl_take isl_set * set)1074 __isl_give isl_union_map *isl_union_map_intersect_params(
1075 	__isl_take isl_union_map *umap, __isl_take isl_set *set)
1076 {
1077 	int is_universe;
1078 
1079 	is_universe = isl_set_plain_is_universe(set);
1080 	if (is_universe < 0)
1081 		goto error;
1082 	if (is_universe) {
1083 		isl_set_free(set);
1084 		return umap;
1085 	}
1086 
1087 	return gen_bin_set_op(umap, set, &intersect_params_entry);
1088 error:
1089 	isl_union_map_free(umap);
1090 	isl_set_free(set);
1091 	return NULL;
1092 }
1093 
isl_union_set_intersect_params(__isl_take isl_union_set * uset,__isl_take isl_set * set)1094 __isl_give isl_union_set *isl_union_set_intersect_params(
1095 	__isl_take isl_union_set *uset, __isl_take isl_set *set)
1096 {
1097 	return isl_union_map_intersect_params(uset, set);
1098 }
1099 
union_map_intersect_params(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1100 static __isl_give isl_union_map *union_map_intersect_params(
1101 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1102 {
1103 	return isl_union_map_intersect_params(umap,
1104 						isl_set_from_union_set(uset));
1105 }
1106 
union_map_gist_params(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1107 static __isl_give isl_union_map *union_map_gist_params(
1108 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1109 {
1110 	return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
1111 }
1112 
1113 struct isl_union_map_match_bin_data {
1114 	isl_union_map *umap2;
1115 	isl_union_map *res;
1116 	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
1117 };
1118 
match_bin_entry(void ** entry,void * user)1119 static isl_stat match_bin_entry(void **entry, void *user)
1120 {
1121 	struct isl_union_map_match_bin_data *data = user;
1122 	uint32_t hash;
1123 	struct isl_hash_table_entry *entry2;
1124 	isl_map *map = *entry;
1125 	int empty;
1126 
1127 	hash = isl_space_get_hash(map->dim);
1128 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1129 				     hash, &has_space, map->dim, 0);
1130 	if (!entry2)
1131 		return isl_stat_error;
1132 	if (entry2 == isl_hash_table_entry_none)
1133 		return isl_stat_ok;
1134 
1135 	map = isl_map_copy(map);
1136 	map = data->fn(map, isl_map_copy(entry2->data));
1137 
1138 	empty = isl_map_is_empty(map);
1139 	if (empty < 0) {
1140 		isl_map_free(map);
1141 		return isl_stat_error;
1142 	}
1143 	if (empty) {
1144 		isl_map_free(map);
1145 		return isl_stat_ok;
1146 	}
1147 
1148 	data->res = isl_union_map_add_map(data->res, map);
1149 
1150 	return isl_stat_ok;
1151 }
1152 
match_bin_op(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2,__isl_give isl_map * (* fn)(__isl_take isl_map *,__isl_take isl_map *))1153 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
1154 	__isl_take isl_union_map *umap2,
1155 	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
1156 {
1157 	struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
1158 
1159 	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1160 	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1161 
1162 	if (!umap1 || !umap2)
1163 		goto error;
1164 
1165 	data.umap2 = umap2;
1166 	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1167 				       umap1->table.n);
1168 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1169 				   &match_bin_entry, &data) < 0)
1170 		goto error;
1171 
1172 	isl_union_map_free(umap1);
1173 	isl_union_map_free(umap2);
1174 	return data.res;
1175 error:
1176 	isl_union_map_free(umap1);
1177 	isl_union_map_free(umap2);
1178 	isl_union_map_free(data.res);
1179 	return NULL;
1180 }
1181 
isl_union_map_intersect(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1182 __isl_give isl_union_map *isl_union_map_intersect(
1183 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1184 {
1185 	return match_bin_op(umap1, umap2, &isl_map_intersect);
1186 }
1187 
1188 /* Compute the intersection of the two union_sets.
1189  * As a special case, if exactly one of the two union_sets
1190  * is a parameter domain, then intersect the parameter domain
1191  * of the other one with this set.
1192  */
isl_union_set_intersect(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1193 __isl_give isl_union_set *isl_union_set_intersect(
1194 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1195 {
1196 	int p1, p2;
1197 
1198 	p1 = isl_union_set_is_params(uset1);
1199 	p2 = isl_union_set_is_params(uset2);
1200 	if (p1 < 0 || p2 < 0)
1201 		goto error;
1202 	if (!p1 && p2)
1203 		return union_map_intersect_params(uset1, uset2);
1204 	if (p1 && !p2)
1205 		return union_map_intersect_params(uset2, uset1);
1206 	return isl_union_map_intersect(uset1, uset2);
1207 error:
1208 	isl_union_set_free(uset1);
1209 	isl_union_set_free(uset2);
1210 	return NULL;
1211 }
1212 
gist_params_entry(void ** entry,void * user)1213 static isl_stat gist_params_entry(void **entry, void *user)
1214 {
1215 	struct isl_union_map_gen_bin_set_data *data = user;
1216 	isl_map *map = *entry;
1217 	int empty;
1218 
1219 	map = isl_map_copy(map);
1220 	map = isl_map_gist_params(map, isl_set_copy(data->set));
1221 
1222 	empty = isl_map_is_empty(map);
1223 	if (empty < 0) {
1224 		isl_map_free(map);
1225 		return isl_stat_error;
1226 	}
1227 
1228 	data->res = isl_union_map_add_map(data->res, map);
1229 
1230 	return isl_stat_ok;
1231 }
1232 
isl_union_map_gist_params(__isl_take isl_union_map * umap,__isl_take isl_set * set)1233 __isl_give isl_union_map *isl_union_map_gist_params(
1234 	__isl_take isl_union_map *umap, __isl_take isl_set *set)
1235 {
1236 	return gen_bin_set_op(umap, set, &gist_params_entry);
1237 }
1238 
isl_union_set_gist_params(__isl_take isl_union_set * uset,__isl_take isl_set * set)1239 __isl_give isl_union_set *isl_union_set_gist_params(
1240 	__isl_take isl_union_set *uset, __isl_take isl_set *set)
1241 {
1242 	return isl_union_map_gist_params(uset, set);
1243 }
1244 
isl_union_map_gist(__isl_take isl_union_map * umap,__isl_take isl_union_map * context)1245 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
1246 	__isl_take isl_union_map *context)
1247 {
1248 	return match_bin_op(umap, context, &isl_map_gist);
1249 }
1250 
isl_union_set_gist(__isl_take isl_union_set * uset,__isl_take isl_union_set * context)1251 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
1252 	__isl_take isl_union_set *context)
1253 {
1254 	if (isl_union_set_is_params(context))
1255 		return union_map_gist_params(uset, context);
1256 	return isl_union_map_gist(uset, context);
1257 }
1258 
1259 /* For each map in "umap", remove the constraints in the corresponding map
1260  * of "context".
1261  * Each map in "context" is assumed to consist of a single disjunct and
1262  * to have explicit representations for all local variables.
1263  */
isl_union_map_plain_gist(__isl_take isl_union_map * umap,__isl_take isl_union_map * context)1264 __isl_give isl_union_map *isl_union_map_plain_gist(
1265 	__isl_take isl_union_map *umap, __isl_take isl_union_map *context)
1266 {
1267 	return match_bin_op(umap, context, &isl_map_plain_gist);
1268 }
1269 
1270 /* For each set in "uset", remove the constraints in the corresponding set
1271  * of "context".
1272  * Each set in "context" is assumed to consist of a single disjunct and
1273  * to have explicit representations for all local variables.
1274  */
isl_union_set_plain_gist(__isl_take isl_union_set * uset,__isl_take isl_union_set * context)1275 __isl_give isl_union_set *isl_union_set_plain_gist(
1276 	__isl_take isl_union_set *uset, __isl_take isl_union_set *context)
1277 {
1278 	return isl_union_map_plain_gist(uset, context);
1279 }
1280 
lex_le_set(__isl_take isl_map * set1,__isl_take isl_map * set2)1281 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
1282 	__isl_take isl_map *set2)
1283 {
1284 	return isl_set_lex_le_set(set_from_map(set1), set_from_map(set2));
1285 }
1286 
lex_lt_set(__isl_take isl_map * set1,__isl_take isl_map * set2)1287 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
1288 	__isl_take isl_map *set2)
1289 {
1290 	return isl_set_lex_lt_set(set_from_map(set1), set_from_map(set2));
1291 }
1292 
isl_union_set_lex_lt_union_set(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1293 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
1294 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1295 {
1296 	return match_bin_op(uset1, uset2, &lex_lt_set);
1297 }
1298 
isl_union_set_lex_le_union_set(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1299 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
1300 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1301 {
1302 	return match_bin_op(uset1, uset2, &lex_le_set);
1303 }
1304 
isl_union_set_lex_gt_union_set(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1305 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
1306 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1307 {
1308 	return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
1309 }
1310 
isl_union_set_lex_ge_union_set(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1311 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
1312 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
1313 {
1314 	return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
1315 }
1316 
isl_union_map_lex_gt_union_map(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1317 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
1318 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1319 {
1320 	return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
1321 }
1322 
isl_union_map_lex_ge_union_map(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1323 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
1324 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1325 {
1326 	return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
1327 }
1328 
1329 /* Intersect the domain of "umap" with "uset".
1330  */
union_map_intersect_domain(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1331 static __isl_give isl_union_map *union_map_intersect_domain(
1332 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1333 {
1334 	struct isl_bin_op_control control = {
1335 		.match_space = &isl_space_domain,
1336 		.fn_map = &isl_map_intersect_domain,
1337 	};
1338 
1339 	return gen_bin_op(umap, uset, &control);
1340 }
1341 
1342 /* Intersect the domain of "umap" with "uset".
1343  * If "uset" is a parameters domain, then intersect the parameter
1344  * domain of "umap" with this set.
1345  */
isl_union_map_intersect_domain_union_set(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1346 __isl_give isl_union_map *isl_union_map_intersect_domain_union_set(
1347 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1348 {
1349 	if (isl_union_set_is_params(uset))
1350 		return union_map_intersect_params(umap, uset);
1351 	else
1352 		return union_map_intersect_domain(umap, uset);
1353 }
1354 
1355 /* This is an alternative name for the function above.
1356  */
isl_union_map_intersect_domain(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1357 __isl_give isl_union_map *isl_union_map_intersect_domain(
1358 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1359 {
1360 	return isl_union_map_intersect_domain_union_set(umap, uset);
1361 }
1362 
1363 /* Remove the elements of "uset" from the domain of "umap".
1364  */
isl_union_map_subtract_domain(__isl_take isl_union_map * umap,__isl_take isl_union_set * dom)1365 __isl_give isl_union_map *isl_union_map_subtract_domain(
1366 	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1367 {
1368 	struct isl_bin_op_control control = {
1369 		.subtract = 1,
1370 		.match_space = &isl_space_domain,
1371 		.fn_map = &isl_map_subtract_domain,
1372 	};
1373 
1374 	return gen_bin_op(umap, dom, &control);
1375 }
1376 
1377 /* Remove the elements of "uset" from the range of "umap".
1378  */
isl_union_map_subtract_range(__isl_take isl_union_map * umap,__isl_take isl_union_set * dom)1379 __isl_give isl_union_map *isl_union_map_subtract_range(
1380 	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1381 {
1382 	struct isl_bin_op_control control = {
1383 		.subtract = 1,
1384 		.match_space = &isl_space_range,
1385 		.fn_map = &isl_map_subtract_range,
1386 	};
1387 
1388 	return gen_bin_op(umap, dom, &control);
1389 }
1390 
1391 /* Compute the gist of "umap" with respect to the domain "uset".
1392  */
union_map_gist_domain(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1393 static __isl_give isl_union_map *union_map_gist_domain(
1394 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1395 {
1396 	struct isl_bin_op_control control = {
1397 		.match_space = &isl_space_domain,
1398 		.fn_map = &isl_map_gist_domain,
1399 	};
1400 
1401 	return gen_bin_op(umap, uset, &control);
1402 }
1403 
1404 /* Compute the gist of "umap" with respect to the domain "uset".
1405  * If "uset" is a parameters domain, then compute the gist
1406  * with respect to this parameter domain.
1407  */
isl_union_map_gist_domain(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1408 __isl_give isl_union_map *isl_union_map_gist_domain(
1409 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1410 {
1411 	if (isl_union_set_is_params(uset))
1412 		return union_map_gist_params(umap, uset);
1413 	else
1414 		return union_map_gist_domain(umap, uset);
1415 }
1416 
1417 /* Compute the gist of "umap" with respect to the range "uset".
1418  */
isl_union_map_gist_range(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1419 __isl_give isl_union_map *isl_union_map_gist_range(
1420 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1421 {
1422 	struct isl_bin_op_control control = {
1423 		.match_space = &isl_space_range,
1424 		.fn_map = &isl_map_gist_range,
1425 	};
1426 
1427 	return gen_bin_op(umap, uset, &control);
1428 }
1429 
isl_union_map_intersect_range_union_set(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1430 __isl_give isl_union_map *isl_union_map_intersect_range_union_set(
1431 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1432 {
1433 	struct isl_bin_op_control control = {
1434 		.match_space = &isl_space_range,
1435 		.fn_map = &isl_map_intersect_range,
1436 	};
1437 
1438 	return gen_bin_op(umap, uset, &control);
1439 }
1440 
1441 /* This is an alternative name for the function above.
1442  */
isl_union_map_intersect_range(__isl_take isl_union_map * umap,__isl_take isl_union_set * uset)1443 __isl_give isl_union_map *isl_union_map_intersect_range(
1444 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1445 {
1446 	return isl_union_map_intersect_range_union_set(umap, uset);
1447 }
1448 
1449 /* Intersect each map in "umap" in a space [A -> B] -> C
1450  * with the corresponding map in "factor" in the space B -> C and
1451  * collect the results.
1452  */
isl_union_map_intersect_domain_factor_range(__isl_take isl_union_map * umap,__isl_take isl_union_map * factor)1453 __isl_give isl_union_map *isl_union_map_intersect_domain_factor_range(
1454 	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)
1455 {
1456 	struct isl_bin_op_control control = {
1457 		.filter = &isl_map_domain_is_wrapping,
1458 		.match_space = &isl_space_domain_factor_range,
1459 		.fn_map = &isl_map_intersect_domain_factor_range,
1460 	};
1461 
1462 	return gen_bin_op(umap, factor, &control);
1463 }
1464 
1465 /* Intersect each map in "umap" in a space A -> [B -> C]
1466  * with the corresponding map in "factor" in the space A -> B and
1467  * collect the results.
1468  */
isl_union_map_intersect_range_factor_domain(__isl_take isl_union_map * umap,__isl_take isl_union_map * factor)1469 __isl_give isl_union_map *isl_union_map_intersect_range_factor_domain(
1470 	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)
1471 {
1472 	struct isl_bin_op_control control = {
1473 		.filter = &isl_map_range_is_wrapping,
1474 		.match_space = &isl_space_range_factor_domain,
1475 		.fn_map = &isl_map_intersect_range_factor_domain,
1476 	};
1477 
1478 	return gen_bin_op(umap, factor, &control);
1479 }
1480 
1481 /* Intersect each map in "umap" in a space A -> [B -> C]
1482  * with the corresponding map in "factor" in the space A -> C and
1483  * collect the results.
1484  */
isl_union_map_intersect_range_factor_range(__isl_take isl_union_map * umap,__isl_take isl_union_map * factor)1485 __isl_give isl_union_map *isl_union_map_intersect_range_factor_range(
1486 	__isl_take isl_union_map *umap, __isl_take isl_union_map *factor)
1487 {
1488 	struct isl_bin_op_control control = {
1489 		.filter = &isl_map_range_is_wrapping,
1490 		.match_space = &isl_space_range_factor_range,
1491 		.fn_map = &isl_map_intersect_range_factor_range,
1492 	};
1493 
1494 	return gen_bin_op(umap, factor, &control);
1495 }
1496 
1497 struct isl_union_map_bin_data {
1498 	isl_union_map *umap2;
1499 	isl_union_map *res;
1500 	isl_map *map;
1501 	isl_stat (*fn)(void **entry, void *user);
1502 };
1503 
apply_range_entry(void ** entry,void * user)1504 static isl_stat apply_range_entry(void **entry, void *user)
1505 {
1506 	struct isl_union_map_bin_data *data = user;
1507 	isl_map *map2 = *entry;
1508 	isl_bool empty, match;
1509 
1510 	match = isl_map_tuple_is_equal(data->map, isl_dim_out,
1511 				map2, isl_dim_in);
1512 	if (match < 0)
1513 		return isl_stat_error;
1514 	if (!match)
1515 		return isl_stat_ok;
1516 
1517 	map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1518 
1519 	empty = isl_map_is_empty(map2);
1520 	if (empty < 0) {
1521 		isl_map_free(map2);
1522 		return isl_stat_error;
1523 	}
1524 	if (empty) {
1525 		isl_map_free(map2);
1526 		return isl_stat_ok;
1527 	}
1528 
1529 	data->res = isl_union_map_add_map(data->res, map2);
1530 
1531 	return isl_stat_ok;
1532 }
1533 
bin_entry(void ** entry,void * user)1534 static isl_stat bin_entry(void **entry, void *user)
1535 {
1536 	struct isl_union_map_bin_data *data = user;
1537 	isl_map *map = *entry;
1538 
1539 	data->map = map;
1540 	if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1541 				   data->fn, data) < 0)
1542 		return isl_stat_error;
1543 
1544 	return isl_stat_ok;
1545 }
1546 
bin_op(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2,isl_stat (* fn)(void ** entry,void * user))1547 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1548 	__isl_take isl_union_map *umap2,
1549 	isl_stat (*fn)(void **entry, void *user))
1550 {
1551 	struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1552 
1553 	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1554 	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1555 
1556 	if (!umap1 || !umap2)
1557 		goto error;
1558 
1559 	data.umap2 = umap2;
1560 	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1561 				       umap1->table.n);
1562 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1563 				   &bin_entry, &data) < 0)
1564 		goto error;
1565 
1566 	isl_union_map_free(umap1);
1567 	isl_union_map_free(umap2);
1568 	return data.res;
1569 error:
1570 	isl_union_map_free(umap1);
1571 	isl_union_map_free(umap2);
1572 	isl_union_map_free(data.res);
1573 	return NULL;
1574 }
1575 
isl_union_map_apply_range(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1576 __isl_give isl_union_map *isl_union_map_apply_range(
1577 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1578 {
1579 	return bin_op(umap1, umap2, &apply_range_entry);
1580 }
1581 
isl_union_map_apply_domain(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1582 __isl_give isl_union_map *isl_union_map_apply_domain(
1583 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1584 {
1585 	umap1 = isl_union_map_reverse(umap1);
1586 	umap1 = isl_union_map_apply_range(umap1, umap2);
1587 	return isl_union_map_reverse(umap1);
1588 }
1589 
isl_union_set_apply(__isl_take isl_union_set * uset,__isl_take isl_union_map * umap)1590 __isl_give isl_union_set *isl_union_set_apply(
1591 	__isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1592 {
1593 	return isl_union_map_apply_range(uset, umap);
1594 }
1595 
map_lex_lt_entry(void ** entry,void * user)1596 static isl_stat map_lex_lt_entry(void **entry, void *user)
1597 {
1598 	struct isl_union_map_bin_data *data = user;
1599 	isl_map *map2 = *entry;
1600 	isl_bool match;
1601 
1602 	match = isl_map_tuple_is_equal(data->map, isl_dim_out,
1603 				 map2, isl_dim_out);
1604 	if (match < 0)
1605 		return isl_stat_error;
1606 	if (!match)
1607 		return isl_stat_ok;
1608 
1609 	map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1610 
1611 	data->res = isl_union_map_add_map(data->res, map2);
1612 
1613 	return isl_stat_ok;
1614 }
1615 
isl_union_map_lex_lt_union_map(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1616 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1617 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1618 {
1619 	return bin_op(umap1, umap2, &map_lex_lt_entry);
1620 }
1621 
map_lex_le_entry(void ** entry,void * user)1622 static isl_stat map_lex_le_entry(void **entry, void *user)
1623 {
1624 	struct isl_union_map_bin_data *data = user;
1625 	isl_map *map2 = *entry;
1626 	isl_bool match;
1627 
1628 	match = isl_map_tuple_is_equal(data->map, isl_dim_out,
1629 				 map2, isl_dim_out);
1630 	if (match < 0)
1631 		return isl_stat_error;
1632 	if (!match)
1633 		return isl_stat_ok;
1634 
1635 	map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1636 
1637 	data->res = isl_union_map_add_map(data->res, map2);
1638 
1639 	return isl_stat_ok;
1640 }
1641 
isl_union_map_lex_le_union_map(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1642 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1643 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1644 {
1645 	return bin_op(umap1, umap2, &map_lex_le_entry);
1646 }
1647 
product_entry(void ** entry,void * user)1648 static isl_stat product_entry(void **entry, void *user)
1649 {
1650 	struct isl_union_map_bin_data *data = user;
1651 	isl_map *map2 = *entry;
1652 
1653 	map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1654 
1655 	data->res = isl_union_map_add_map(data->res, map2);
1656 
1657 	return isl_stat_ok;
1658 }
1659 
isl_union_map_product(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1660 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1661 	__isl_take isl_union_map *umap2)
1662 {
1663 	return bin_op(umap1, umap2, &product_entry);
1664 }
1665 
set_product_entry(void ** entry,void * user)1666 static isl_stat set_product_entry(void **entry, void *user)
1667 {
1668 	struct isl_union_map_bin_data *data = user;
1669 	isl_set *set2 = *entry;
1670 
1671 	set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1672 
1673 	data->res = isl_union_set_add_set(data->res, set2);
1674 
1675 	return isl_stat_ok;
1676 }
1677 
isl_union_set_product(__isl_take isl_union_set * uset1,__isl_take isl_union_set * uset2)1678 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1679 	__isl_take isl_union_set *uset2)
1680 {
1681 	return bin_op(uset1, uset2, &set_product_entry);
1682 }
1683 
domain_product_entry(void ** entry,void * user)1684 static isl_stat domain_product_entry(void **entry, void *user)
1685 {
1686 	struct isl_union_map_bin_data *data = user;
1687 	isl_map *map2 = *entry;
1688 	isl_bool match;
1689 
1690 	match = isl_map_tuple_is_equal(data->map, isl_dim_out,
1691 				 map2, isl_dim_out);
1692 	if (match < 0)
1693 		return isl_stat_error;
1694 	if (!match)
1695 		return isl_stat_ok;
1696 
1697 	map2 = isl_map_domain_product(isl_map_copy(data->map),
1698 				     isl_map_copy(map2));
1699 
1700 	data->res = isl_union_map_add_map(data->res, map2);
1701 
1702 	return isl_stat_ok;
1703 }
1704 
1705 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1706  */
isl_union_map_domain_product(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1707 __isl_give isl_union_map *isl_union_map_domain_product(
1708 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1709 {
1710 	return bin_op(umap1, umap2, &domain_product_entry);
1711 }
1712 
range_product_entry(void ** entry,void * user)1713 static isl_stat range_product_entry(void **entry, void *user)
1714 {
1715 	struct isl_union_map_bin_data *data = user;
1716 	isl_map *map2 = *entry;
1717 	isl_bool match;
1718 
1719 	match = isl_map_tuple_is_equal(data->map, isl_dim_in, map2, isl_dim_in);
1720 	if (match < 0)
1721 		return isl_stat_error;
1722 	if (!match)
1723 		return isl_stat_ok;
1724 
1725 	map2 = isl_map_range_product(isl_map_copy(data->map),
1726 				     isl_map_copy(map2));
1727 
1728 	data->res = isl_union_map_add_map(data->res, map2);
1729 
1730 	return isl_stat_ok;
1731 }
1732 
isl_union_map_range_product(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1733 __isl_give isl_union_map *isl_union_map_range_product(
1734 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1735 {
1736 	return bin_op(umap1, umap2, &range_product_entry);
1737 }
1738 
1739 /* If data->map A -> B and "map2" C -> D have the same range space,
1740  * then add (A, C) -> (B * D) to data->res.
1741  */
flat_domain_product_entry(void ** entry,void * user)1742 static isl_stat flat_domain_product_entry(void **entry, void *user)
1743 {
1744 	struct isl_union_map_bin_data *data = user;
1745 	isl_map *map2 = *entry;
1746 	isl_bool match;
1747 
1748 	match = isl_map_tuple_is_equal(data->map, isl_dim_out,
1749 				 map2, isl_dim_out);
1750 	if (match < 0)
1751 		return isl_stat_error;
1752 	if (!match)
1753 		return isl_stat_ok;
1754 
1755 	map2 = isl_map_flat_domain_product(isl_map_copy(data->map),
1756 					  isl_map_copy(map2));
1757 
1758 	data->res = isl_union_map_add_map(data->res, map2);
1759 
1760 	return isl_stat_ok;
1761 }
1762 
1763 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D).
1764  */
isl_union_map_flat_domain_product(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1765 __isl_give isl_union_map *isl_union_map_flat_domain_product(
1766 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1767 {
1768 	return bin_op(umap1, umap2, &flat_domain_product_entry);
1769 }
1770 
flat_range_product_entry(void ** entry,void * user)1771 static isl_stat flat_range_product_entry(void **entry, void *user)
1772 {
1773 	struct isl_union_map_bin_data *data = user;
1774 	isl_map *map2 = *entry;
1775 	isl_bool match;
1776 
1777 	match = isl_map_tuple_is_equal(data->map, isl_dim_in, map2, isl_dim_in);
1778 	if (match < 0)
1779 		return isl_stat_error;
1780 	if (!match)
1781 		return isl_stat_ok;
1782 
1783 	map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1784 					  isl_map_copy(map2));
1785 
1786 	data->res = isl_union_map_add_map(data->res, map2);
1787 
1788 	return isl_stat_ok;
1789 }
1790 
isl_union_map_flat_range_product(__isl_take isl_union_map * umap1,__isl_take isl_union_map * umap2)1791 __isl_give isl_union_map *isl_union_map_flat_range_product(
1792 	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1793 {
1794 	return bin_op(umap1, umap2, &flat_range_product_entry);
1795 }
1796 
1797 /* Data structure that specifies how un_op should modify
1798  * the maps in the union map.
1799  *
1800  * If "inplace" is set, then the maps in the input union map
1801  * are modified in place.  This means that "fn_map" should not
1802  * change the meaning of the map or that the union map only
1803  * has a single reference.
1804  * If "total" is set, then all maps need to be modified and
1805  * the results need to live in the same space.
1806  * Otherwise, a new union map is constructed to store the results.
1807  * If "filter" is not NULL, then only the input maps that satisfy "filter"
1808  * are taken into account.  "filter_user" is passed as the second argument
1809  * to "filter".  No filter can be set if "inplace" or
1810  * "total" is set.
1811  * At most one of "fn_map" or "fn_map2" can be set, specifying
1812  * how the maps (selected by "filter") should be transformed.
1813  * If "fn_map2" is set, then "fn_map2_user" is passed as the second argument.
1814  */
1815 struct isl_un_op_control {
1816 	int inplace;
1817 	int total;
1818 	isl_bool (*filter)(__isl_keep isl_map *map, void *user);
1819 	void *filter_user;
1820 	__isl_give isl_map *(*fn_map)(__isl_take isl_map *map);
1821 	__isl_give isl_map *(*fn_map2)(__isl_take isl_map *map, void *user);
1822 	void *fn_map2_user;
1823 };
1824 
1825 /* Data structure for wrapping the data for un_op_filter_drop_user.
1826  * "filter" is the function that is being wrapped.
1827  */
1828 struct isl_un_op_drop_user_data {
1829 	isl_bool (*filter)(__isl_keep isl_map *map);
1830 };
1831 
1832 /* Wrapper for isl_un_op_control filters that do not require
1833  * a second argument.
1834  * Simply call data->filter without the second argument.
1835  */
un_op_filter_drop_user(__isl_keep isl_map * map,void * user)1836 static isl_bool un_op_filter_drop_user(__isl_keep isl_map *map, void *user)
1837 {
1838 	struct isl_un_op_drop_user_data *data = user;
1839 	return data->filter(map);
1840 }
1841 
1842 /* Internal data structure for "un_op".
1843  * "control" specifies how the maps in the union map should be modified.
1844  * "res" collects the results.
1845  */
1846 struct isl_union_map_un_data {
1847 	struct isl_un_op_control *control;
1848 	isl_union_map *res;
1849 };
1850 
1851 /* isl_hash_table_foreach callback for un_op.
1852  * Handle the map that "entry" points to.
1853  *
1854  * If control->filter is set, then check if this map satisfies the filter.
1855  * If so (or if control->filter is not set), modify the map
1856  * by calling control->fn_map or control->fn_map2 (if set) and
1857  * either add the result to data->res or
1858  * replace the original entry by the result (if control->inplace is set).
1859  */
un_entry(void ** entry,void * user)1860 static isl_stat un_entry(void **entry, void *user)
1861 {
1862 	struct isl_union_map_un_data *data = user;
1863 	struct isl_un_op_control *control = data->control;
1864 	isl_map *map = *entry;
1865 
1866 	if (control->filter) {
1867 		isl_bool ok;
1868 
1869 		ok = control->filter(map, control->filter_user);
1870 		if (ok < 0)
1871 			return isl_stat_error;
1872 		if (!ok)
1873 			return isl_stat_ok;
1874 	}
1875 
1876 	map = isl_map_copy(map);
1877 	if (control->fn_map2 != NULL)
1878 		map = control->fn_map2(map, control->fn_map2_user);
1879 	else if (control->fn_map != NULL)
1880 		map = control->fn_map(map);
1881 	if (!map)
1882 		return isl_stat_error;
1883 	if (control->inplace) {
1884 		isl_map_free(*entry);
1885 		*entry = map;
1886 	} else {
1887 		data->res = isl_union_map_add_map(data->res, map);
1888 		if (!data->res)
1889 			return isl_stat_error;
1890 	}
1891 
1892 	return isl_stat_ok;
1893 }
1894 
1895 /* Modify the maps in "umap" based on "control".
1896  * If control->inplace is set, then modify the maps in "umap" in-place.
1897  * Otherwise, create a new union map to hold the results.
1898  * If control->total is set, then perform an inplace computation
1899  * if "umap" is only referenced once.  Otherwise, create a new union map
1900  * to store the results.
1901  */
un_op(__isl_take isl_union_map * umap,struct isl_un_op_control * control)1902 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1903 	struct isl_un_op_control *control)
1904 {
1905 	struct isl_union_map_un_data data = { control };
1906 
1907 	if (!umap)
1908 		return NULL;
1909 	if (!!control->fn_map && !!control->fn_map2)
1910 		isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1911 			"at most one mapping function can be specified",
1912 			return isl_union_map_free(umap));
1913 	if ((control->inplace || control->total) && control->filter)
1914 		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
1915 			"inplace/total modification cannot be filtered",
1916 			return isl_union_map_free(umap));
1917 
1918 	if (control->total && umap->ref == 1)
1919 		control->inplace = 1;
1920 	if (control->inplace) {
1921 		data.res = umap;
1922 	} else {
1923 		isl_space *space;
1924 
1925 		space = isl_union_map_get_space(umap);
1926 		data.res = isl_union_map_alloc(space, umap->table.n);
1927 	}
1928 	if (isl_hash_table_foreach(isl_union_map_get_ctx(umap),
1929 				    &umap->table, &un_entry, &data) < 0)
1930 		data.res = isl_union_map_free(data.res);
1931 
1932 	if (control->inplace)
1933 		return data.res;
1934 	isl_union_map_free(umap);
1935 	return data.res;
1936 }
1937 
isl_union_map_from_range(__isl_take isl_union_set * uset)1938 __isl_give isl_union_map *isl_union_map_from_range(
1939 	__isl_take isl_union_set *uset)
1940 {
1941 	struct isl_un_op_control control = {
1942 		.fn_map = &isl_map_from_range,
1943 	};
1944 	return un_op(uset, &control);
1945 }
1946 
isl_union_map_from_domain(__isl_take isl_union_set * uset)1947 __isl_give isl_union_map *isl_union_map_from_domain(
1948 	__isl_take isl_union_set *uset)
1949 {
1950 	return isl_union_map_reverse(isl_union_map_from_range(uset));
1951 }
1952 
isl_union_map_from_domain_and_range(__isl_take isl_union_set * domain,__isl_take isl_union_set * range)1953 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1954 	__isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1955 {
1956 	return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1957 				         isl_union_map_from_range(range));
1958 }
1959 
1960 /* Modify the maps in "umap" by applying "fn" on them.
1961  * "fn" should apply to all maps in "umap" and should not modify the space.
1962  */
total(__isl_take isl_union_map * umap,__isl_give isl_map * (* fn)(__isl_take isl_map *))1963 static __isl_give isl_union_map *total(__isl_take isl_union_map *umap,
1964 	__isl_give isl_map *(*fn)(__isl_take isl_map *))
1965 {
1966 	struct isl_un_op_control control = {
1967 		.total = 1,
1968 		.fn_map = fn,
1969 	};
1970 
1971 	return un_op(umap, &control);
1972 }
1973 
1974 /* Compute the affine hull of "map" and return the result as an isl_map.
1975  */
isl_map_affine_hull_map(__isl_take isl_map * map)1976 static __isl_give isl_map *isl_map_affine_hull_map(__isl_take isl_map *map)
1977 {
1978 	return isl_map_from_basic_map(isl_map_affine_hull(map));
1979 }
1980 
isl_union_map_affine_hull(__isl_take isl_union_map * umap)1981 __isl_give isl_union_map *isl_union_map_affine_hull(
1982 	__isl_take isl_union_map *umap)
1983 {
1984 	return total(umap, &isl_map_affine_hull_map);
1985 }
1986 
isl_union_set_affine_hull(__isl_take isl_union_set * uset)1987 __isl_give isl_union_set *isl_union_set_affine_hull(
1988 	__isl_take isl_union_set *uset)
1989 {
1990 	return isl_union_map_affine_hull(uset);
1991 }
1992 
1993 /* Wrapper around isl_set_combined_lineality_space
1994  * that returns the combined lineality space in the form of an isl_set
1995  * instead of an isl_basic_set.
1996  */
combined_lineality_space(__isl_take isl_set * set)1997 static __isl_give isl_set *combined_lineality_space(__isl_take isl_set *set)
1998 {
1999 	return isl_set_from_basic_set(isl_set_combined_lineality_space(set));
2000 }
2001 
2002 /* For each set in "uset", compute the (linear) hull
2003  * of the lineality spaces of its basic sets and
2004  * collect and return the results.
2005  */
isl_union_set_combined_lineality_space(__isl_take isl_union_set * uset)2006 __isl_give isl_union_set *isl_union_set_combined_lineality_space(
2007 	__isl_take isl_union_set *uset)
2008 {
2009 	struct isl_un_op_control control = {
2010 		.fn_map = &combined_lineality_space,
2011 	};
2012 	return un_op(uset, &control);
2013 }
2014 
2015 /* Compute the polyhedral hull of "map" and return the result as an isl_map.
2016  */
isl_map_polyhedral_hull_map(__isl_take isl_map * map)2017 static __isl_give isl_map *isl_map_polyhedral_hull_map(__isl_take isl_map *map)
2018 {
2019 	return isl_map_from_basic_map(isl_map_polyhedral_hull(map));
2020 }
2021 
isl_union_map_polyhedral_hull(__isl_take isl_union_map * umap)2022 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
2023 	__isl_take isl_union_map *umap)
2024 {
2025 	return total(umap, &isl_map_polyhedral_hull_map);
2026 }
2027 
isl_union_set_polyhedral_hull(__isl_take isl_union_set * uset)2028 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
2029 	__isl_take isl_union_set *uset)
2030 {
2031 	return isl_union_map_polyhedral_hull(uset);
2032 }
2033 
2034 /* Compute a superset of the convex hull of "map" that is described
2035  * by only translates of the constraints in the constituents of "map" and
2036  * return the result as an isl_map.
2037  */
isl_map_simple_hull_map(__isl_take isl_map * map)2038 static __isl_give isl_map *isl_map_simple_hull_map(__isl_take isl_map *map)
2039 {
2040 	return isl_map_from_basic_map(isl_map_simple_hull(map));
2041 }
2042 
isl_union_map_simple_hull(__isl_take isl_union_map * umap)2043 __isl_give isl_union_map *isl_union_map_simple_hull(
2044 	__isl_take isl_union_map *umap)
2045 {
2046 	return total(umap, &isl_map_simple_hull_map);
2047 }
2048 
isl_union_set_simple_hull(__isl_take isl_union_set * uset)2049 __isl_give isl_union_set *isl_union_set_simple_hull(
2050 	__isl_take isl_union_set *uset)
2051 {
2052 	return isl_union_map_simple_hull(uset);
2053 }
2054 
inplace(__isl_take isl_union_map * umap,__isl_give isl_map * (* fn)(__isl_take isl_map *))2055 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
2056 	__isl_give isl_map *(*fn)(__isl_take isl_map *))
2057 {
2058 	struct isl_un_op_control control = {
2059 		.inplace = 1,
2060 		.fn_map = fn,
2061 	};
2062 
2063 	return un_op(umap, &control);
2064 }
2065 
2066 /* Remove redundant constraints in each of the basic maps of "umap".
2067  * Since removing redundant constraints does not change the meaning
2068  * or the space, the operation can be performed in-place.
2069  */
isl_union_map_remove_redundancies(__isl_take isl_union_map * umap)2070 __isl_give isl_union_map *isl_union_map_remove_redundancies(
2071 	__isl_take isl_union_map *umap)
2072 {
2073 	return inplace(umap, &isl_map_remove_redundancies);
2074 }
2075 
2076 /* Remove redundant constraints in each of the basic sets of "uset".
2077  */
isl_union_set_remove_redundancies(__isl_take isl_union_set * uset)2078 __isl_give isl_union_set *isl_union_set_remove_redundancies(
2079 	__isl_take isl_union_set *uset)
2080 {
2081 	return isl_union_map_remove_redundancies(uset);
2082 }
2083 
isl_union_map_coalesce(__isl_take isl_union_map * umap)2084 __isl_give isl_union_map *isl_union_map_coalesce(
2085 	__isl_take isl_union_map *umap)
2086 {
2087 	return inplace(umap, &isl_map_coalesce);
2088 }
2089 
isl_union_set_coalesce(__isl_take isl_union_set * uset)2090 __isl_give isl_union_set *isl_union_set_coalesce(
2091 	__isl_take isl_union_set *uset)
2092 {
2093 	return isl_union_map_coalesce(uset);
2094 }
2095 
isl_union_map_detect_equalities(__isl_take isl_union_map * umap)2096 __isl_give isl_union_map *isl_union_map_detect_equalities(
2097 	__isl_take isl_union_map *umap)
2098 {
2099 	return inplace(umap, &isl_map_detect_equalities);
2100 }
2101 
isl_union_set_detect_equalities(__isl_take isl_union_set * uset)2102 __isl_give isl_union_set *isl_union_set_detect_equalities(
2103 	__isl_take isl_union_set *uset)
2104 {
2105 	return isl_union_map_detect_equalities(uset);
2106 }
2107 
isl_union_map_compute_divs(__isl_take isl_union_map * umap)2108 __isl_give isl_union_map *isl_union_map_compute_divs(
2109 	__isl_take isl_union_map *umap)
2110 {
2111 	return inplace(umap, &isl_map_compute_divs);
2112 }
2113 
isl_union_set_compute_divs(__isl_take isl_union_set * uset)2114 __isl_give isl_union_set *isl_union_set_compute_divs(
2115 	__isl_take isl_union_set *uset)
2116 {
2117 	return isl_union_map_compute_divs(uset);
2118 }
2119 
isl_union_map_lexmin(__isl_take isl_union_map * umap)2120 __isl_give isl_union_map *isl_union_map_lexmin(
2121 	__isl_take isl_union_map *umap)
2122 {
2123 	return total(umap, &isl_map_lexmin);
2124 }
2125 
isl_union_set_lexmin(__isl_take isl_union_set * uset)2126 __isl_give isl_union_set *isl_union_set_lexmin(
2127 	__isl_take isl_union_set *uset)
2128 {
2129 	return isl_union_map_lexmin(uset);
2130 }
2131 
isl_union_map_lexmax(__isl_take isl_union_map * umap)2132 __isl_give isl_union_map *isl_union_map_lexmax(
2133 	__isl_take isl_union_map *umap)
2134 {
2135 	return total(umap, &isl_map_lexmax);
2136 }
2137 
isl_union_set_lexmax(__isl_take isl_union_set * uset)2138 __isl_give isl_union_set *isl_union_set_lexmax(
2139 	__isl_take isl_union_set *uset)
2140 {
2141 	return isl_union_map_lexmax(uset);
2142 }
2143 
2144 /* Return the universe in the space of "map".
2145  */
universe(__isl_take isl_map * map)2146 static __isl_give isl_map *universe(__isl_take isl_map *map)
2147 {
2148 	isl_space *space;
2149 
2150 	space = isl_map_get_space(map);
2151 	isl_map_free(map);
2152 	return isl_map_universe(space);
2153 }
2154 
isl_union_map_universe(__isl_take isl_union_map * umap)2155 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
2156 {
2157 	struct isl_un_op_control control = {
2158 		.fn_map = &universe,
2159 	};
2160 	return un_op(umap, &control);
2161 }
2162 
isl_union_set_universe(__isl_take isl_union_set * uset)2163 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
2164 {
2165 	return isl_union_map_universe(uset);
2166 }
2167 
isl_union_map_reverse(__isl_take isl_union_map * umap)2168 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
2169 {
2170 	struct isl_un_op_control control = {
2171 		.fn_map = &isl_map_reverse,
2172 	};
2173 	return un_op(umap, &control);
2174 }
2175 
2176 /* Given a union map, take the maps of the form A -> (B -> C) and
2177  * return the union of the corresponding maps A -> (C -> B).
2178  */
isl_union_map_range_reverse(__isl_take isl_union_map * umap)2179 __isl_give isl_union_map *isl_union_map_range_reverse(
2180 	__isl_take isl_union_map *umap)
2181 {
2182 	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };
2183 	struct isl_un_op_control control = {
2184 		.filter = &un_op_filter_drop_user,
2185 		.filter_user = &data,
2186 		.fn_map = &isl_map_range_reverse,
2187 	};
2188 	return un_op(umap, &control);
2189 }
2190 
2191 /* Compute the parameter domain of the given union map.
2192  */
isl_union_map_params(__isl_take isl_union_map * umap)2193 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
2194 {
2195 	struct isl_un_op_control control = {
2196 		.fn_map = &isl_map_params,
2197 	};
2198 	int empty;
2199 
2200 	empty = isl_union_map_is_empty(umap);
2201 	if (empty < 0)
2202 		goto error;
2203 	if (empty) {
2204 		isl_space *space;
2205 		space = isl_union_map_get_space(umap);
2206 		isl_union_map_free(umap);
2207 		return isl_set_empty(space);
2208 	}
2209 	return isl_set_from_union_set(un_op(umap, &control));
2210 error:
2211 	isl_union_map_free(umap);
2212 	return NULL;
2213 }
2214 
2215 /* Compute the parameter domain of the given union set.
2216  */
isl_union_set_params(__isl_take isl_union_set * uset)2217 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
2218 {
2219 	return isl_union_map_params(uset);
2220 }
2221 
isl_union_map_domain(__isl_take isl_union_map * umap)2222 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
2223 {
2224 	struct isl_un_op_control control = {
2225 		.fn_map = &isl_map_domain,
2226 	};
2227 	return un_op(umap, &control);
2228 }
2229 
isl_union_map_range(__isl_take isl_union_map * umap)2230 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
2231 {
2232 	struct isl_un_op_control control = {
2233 		.fn_map = &isl_map_range,
2234 	};
2235 	return un_op(umap, &control);
2236 }
2237 
isl_union_map_domain_map(__isl_take isl_union_map * umap)2238 __isl_give isl_union_map *isl_union_map_domain_map(
2239 	__isl_take isl_union_map *umap)
2240 {
2241 	struct isl_un_op_control control = {
2242 		.fn_map = &isl_map_domain_map,
2243 	};
2244 	return un_op(umap, &control);
2245 }
2246 
2247 /* Construct an isl_pw_multi_aff that maps "map" to its domain and
2248  * add the result to "res".
2249  */
domain_map_upma(__isl_take isl_map * map,void * user)2250 static isl_stat domain_map_upma(__isl_take isl_map *map, void *user)
2251 {
2252 	isl_union_pw_multi_aff **res = user;
2253 	isl_multi_aff *ma;
2254 	isl_pw_multi_aff *pma;
2255 
2256 	ma = isl_multi_aff_domain_map(isl_map_get_space(map));
2257 	pma = isl_pw_multi_aff_alloc(isl_map_wrap(map), ma);
2258 	*res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
2259 
2260 	return *res ? isl_stat_ok : isl_stat_error;
2261 
2262 }
2263 
2264 /* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap"
2265  * to its domain.
2266  */
isl_union_map_domain_map_union_pw_multi_aff(__isl_take isl_union_map * umap)2267 __isl_give isl_union_pw_multi_aff *isl_union_map_domain_map_union_pw_multi_aff(
2268 	__isl_take isl_union_map *umap)
2269 {
2270 	isl_union_pw_multi_aff *res;
2271 
2272 	res = isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap));
2273 	if (isl_union_map_foreach_map(umap, &domain_map_upma, &res) < 0)
2274 		res = isl_union_pw_multi_aff_free(res);
2275 
2276 	isl_union_map_free(umap);
2277 	return res;
2278 }
2279 
isl_union_map_range_map(__isl_take isl_union_map * umap)2280 __isl_give isl_union_map *isl_union_map_range_map(
2281 	__isl_take isl_union_map *umap)
2282 {
2283 	struct isl_un_op_control control = {
2284 		.fn_map = &isl_map_range_map,
2285 	};
2286 	return un_op(umap, &control);
2287 }
2288 
2289 /* Given a collection of wrapped maps of the form A[B -> C],
2290  * return the collection of maps A[B -> C] -> B.
2291  */
isl_union_set_wrapped_domain_map(__isl_take isl_union_set * uset)2292 __isl_give isl_union_map *isl_union_set_wrapped_domain_map(
2293 	__isl_take isl_union_set *uset)
2294 {
2295 	struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping };
2296 	struct isl_un_op_control control = {
2297 		.filter = &un_op_filter_drop_user,
2298 		.filter_user = &data,
2299 		.fn_map = &isl_set_wrapped_domain_map,
2300 	};
2301 	return un_op(uset, &control);
2302 }
2303 
2304 /* Does "map" relate elements from the same space?
2305  */
equal_tuples(__isl_keep isl_map * map,void * user)2306 static isl_bool equal_tuples(__isl_keep isl_map *map, void *user)
2307 {
2308 	return isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);
2309 }
2310 
isl_union_map_deltas(__isl_take isl_union_map * umap)2311 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
2312 {
2313 	struct isl_un_op_control control = {
2314 		.filter = &equal_tuples,
2315 		.fn_map = &isl_map_deltas,
2316 	};
2317 	return un_op(umap, &control);
2318 }
2319 
isl_union_map_deltas_map(__isl_take isl_union_map * umap)2320 __isl_give isl_union_map *isl_union_map_deltas_map(
2321 	__isl_take isl_union_map *umap)
2322 {
2323 	struct isl_un_op_control control = {
2324 		.filter = &equal_tuples,
2325 		.fn_map = &isl_map_deltas_map,
2326 	};
2327 	return un_op(umap, &control);
2328 }
2329 
isl_union_set_identity(__isl_take isl_union_set * uset)2330 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
2331 {
2332 	struct isl_un_op_control control = {
2333 		.fn_map = &isl_set_identity,
2334 	};
2335 	return un_op(uset, &control);
2336 }
2337 
2338 /* Construct an identity isl_pw_multi_aff on "set" and add it to *res.
2339  */
identity_upma(__isl_take isl_set * set,void * user)2340 static isl_stat identity_upma(__isl_take isl_set *set, void *user)
2341 {
2342 	isl_union_pw_multi_aff **res = user;
2343 	isl_space *space;
2344 	isl_pw_multi_aff *pma;
2345 
2346 	space = isl_space_map_from_set(isl_set_get_space(set));
2347 	pma = isl_pw_multi_aff_identity(space);
2348 	pma = isl_pw_multi_aff_intersect_domain(pma, set);
2349 	*res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
2350 
2351 	return *res ? isl_stat_ok : isl_stat_error;
2352 }
2353 
2354 /* Return an identity function on "uset" in the form
2355  * of an isl_union_pw_multi_aff.
2356  */
isl_union_set_identity_union_pw_multi_aff(__isl_take isl_union_set * uset)2357 __isl_give isl_union_pw_multi_aff *isl_union_set_identity_union_pw_multi_aff(
2358 	__isl_take isl_union_set *uset)
2359 {
2360 	isl_union_pw_multi_aff *res;
2361 
2362 	res = isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset));
2363 	if (isl_union_set_foreach_set(uset, &identity_upma, &res) < 0)
2364 		res = isl_union_pw_multi_aff_free(res);
2365 
2366 	isl_union_set_free(uset);
2367 	return res;
2368 }
2369 
2370 /* For each map in "umap" of the form [A -> B] -> C,
2371  * construct the map A -> C and collect the results.
2372  */
isl_union_map_domain_factor_domain(__isl_take isl_union_map * umap)2373 __isl_give isl_union_map *isl_union_map_domain_factor_domain(
2374 	__isl_take isl_union_map *umap)
2375 {
2376 	struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping };
2377 	struct isl_un_op_control control = {
2378 		.filter = &un_op_filter_drop_user,
2379 		.filter_user = &data,
2380 		.fn_map = &isl_map_domain_factor_domain,
2381 	};
2382 	return un_op(umap, &control);
2383 }
2384 
2385 /* For each map in "umap" of the form [A -> B] -> C,
2386  * construct the map B -> C and collect the results.
2387  */
isl_union_map_domain_factor_range(__isl_take isl_union_map * umap)2388 __isl_give isl_union_map *isl_union_map_domain_factor_range(
2389 	__isl_take isl_union_map *umap)
2390 {
2391 	struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping };
2392 	struct isl_un_op_control control = {
2393 		.filter = &un_op_filter_drop_user,
2394 		.filter_user = &data,
2395 		.fn_map = &isl_map_domain_factor_range,
2396 	};
2397 	return un_op(umap, &control);
2398 }
2399 
2400 /* For each map in "umap" of the form A -> [B -> C],
2401  * construct the map A -> B and collect the results.
2402  */
isl_union_map_range_factor_domain(__isl_take isl_union_map * umap)2403 __isl_give isl_union_map *isl_union_map_range_factor_domain(
2404 	__isl_take isl_union_map *umap)
2405 {
2406 	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };
2407 	struct isl_un_op_control control = {
2408 		.filter = &un_op_filter_drop_user,
2409 		.filter_user = &data,
2410 		.fn_map = &isl_map_range_factor_domain,
2411 	};
2412 	return un_op(umap, &control);
2413 }
2414 
2415 /* For each map in "umap" of the form A -> [B -> C],
2416  * construct the map A -> C and collect the results.
2417  */
isl_union_map_range_factor_range(__isl_take isl_union_map * umap)2418 __isl_give isl_union_map *isl_union_map_range_factor_range(
2419 	__isl_take isl_union_map *umap)
2420 {
2421 	struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping };
2422 	struct isl_un_op_control control = {
2423 		.filter = &un_op_filter_drop_user,
2424 		.filter_user = &data,
2425 		.fn_map = &isl_map_range_factor_range,
2426 	};
2427 	return un_op(umap, &control);
2428 }
2429 
2430 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2431  * construct the map A -> C and collect the results.
2432  */
isl_union_map_factor_domain(__isl_take isl_union_map * umap)2433 __isl_give isl_union_map *isl_union_map_factor_domain(
2434 	__isl_take isl_union_map *umap)
2435 {
2436 	struct isl_un_op_drop_user_data data = { &isl_map_is_product };
2437 	struct isl_un_op_control control = {
2438 		.filter = &un_op_filter_drop_user,
2439 		.filter_user = &data,
2440 		.fn_map = &isl_map_factor_domain,
2441 	};
2442 	return un_op(umap, &control);
2443 }
2444 
2445 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2446  * construct the map B -> D and collect the results.
2447  */
isl_union_map_factor_range(__isl_take isl_union_map * umap)2448 __isl_give isl_union_map *isl_union_map_factor_range(
2449 	__isl_take isl_union_map *umap)
2450 {
2451 	struct isl_un_op_drop_user_data data = { &isl_map_is_product };
2452 	struct isl_un_op_control control = {
2453 		.filter = &un_op_filter_drop_user,
2454 		.filter_user = &data,
2455 		.fn_map = &isl_map_factor_range,
2456 	};
2457 	return un_op(umap, &control);
2458 }
2459 
isl_union_set_unwrap(__isl_take isl_union_set * uset)2460 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
2461 {
2462 	struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping };
2463 	struct isl_un_op_control control = {
2464 		.filter = &un_op_filter_drop_user,
2465 		.filter_user = &data,
2466 		.fn_map = &isl_set_unwrap,
2467 	};
2468 	return un_op(uset, &control);
2469 }
2470 
isl_union_map_wrap(__isl_take isl_union_map * umap)2471 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
2472 {
2473 	struct isl_un_op_control control = {
2474 		.fn_map = &isl_map_wrap,
2475 	};
2476 	return un_op(umap, &control);
2477 }
2478 
2479 struct isl_union_map_is_subset_data {
2480 	isl_union_map *umap2;
2481 	isl_bool is_subset;
2482 };
2483 
is_subset_entry(void ** entry,void * user)2484 static isl_stat is_subset_entry(void **entry, void *user)
2485 {
2486 	struct isl_union_map_is_subset_data *data = user;
2487 	uint32_t hash;
2488 	struct isl_hash_table_entry *entry2;
2489 	isl_map *map = *entry;
2490 
2491 	hash = isl_space_get_hash(map->dim);
2492 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2493 				     hash, &has_space, map->dim, 0);
2494 	if (!entry2)
2495 		return isl_stat_error;
2496 	if (entry2 == isl_hash_table_entry_none) {
2497 		int empty = isl_map_is_empty(map);
2498 		if (empty < 0)
2499 			return isl_stat_error;
2500 		if (empty)
2501 			return isl_stat_ok;
2502 		data->is_subset = isl_bool_false;
2503 		return isl_stat_error;
2504 	}
2505 
2506 	data->is_subset = isl_map_is_subset(map, entry2->data);
2507 	if (data->is_subset < 0 || !data->is_subset)
2508 		return isl_stat_error;
2509 
2510 	return isl_stat_ok;
2511 }
2512 
isl_union_map_is_subset(__isl_keep isl_union_map * umap1,__isl_keep isl_union_map * umap2)2513 isl_bool isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
2514 	__isl_keep isl_union_map *umap2)
2515 {
2516 	struct isl_union_map_is_subset_data data = { NULL, isl_bool_true };
2517 
2518 	umap1 = isl_union_map_copy(umap1);
2519 	umap2 = isl_union_map_copy(umap2);
2520 	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
2521 	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
2522 
2523 	if (!umap1 || !umap2)
2524 		goto error;
2525 
2526 	data.umap2 = umap2;
2527 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2528 				   &is_subset_entry, &data) < 0 &&
2529 	    data.is_subset)
2530 		goto error;
2531 
2532 	isl_union_map_free(umap1);
2533 	isl_union_map_free(umap2);
2534 
2535 	return data.is_subset;
2536 error:
2537 	isl_union_map_free(umap1);
2538 	isl_union_map_free(umap2);
2539 	return isl_bool_error;
2540 }
2541 
isl_union_set_is_subset(__isl_keep isl_union_set * uset1,__isl_keep isl_union_set * uset2)2542 isl_bool isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
2543 	__isl_keep isl_union_set *uset2)
2544 {
2545 	return isl_union_map_is_subset(uset1, uset2);
2546 }
2547 
isl_union_map_is_equal(__isl_keep isl_union_map * umap1,__isl_keep isl_union_map * umap2)2548 isl_bool isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
2549 	__isl_keep isl_union_map *umap2)
2550 {
2551 	isl_bool is_subset;
2552 
2553 	if (!umap1 || !umap2)
2554 		return isl_bool_error;
2555 	is_subset = isl_union_map_is_subset(umap1, umap2);
2556 	if (is_subset != isl_bool_true)
2557 		return is_subset;
2558 	is_subset = isl_union_map_is_subset(umap2, umap1);
2559 	return is_subset;
2560 }
2561 
isl_union_set_is_equal(__isl_keep isl_union_set * uset1,__isl_keep isl_union_set * uset2)2562 isl_bool isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
2563 	__isl_keep isl_union_set *uset2)
2564 {
2565 	return isl_union_map_is_equal(uset1, uset2);
2566 }
2567 
isl_union_map_is_strict_subset(__isl_keep isl_union_map * umap1,__isl_keep isl_union_map * umap2)2568 isl_bool isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
2569 	__isl_keep isl_union_map *umap2)
2570 {
2571 	isl_bool is_subset;
2572 
2573 	if (!umap1 || !umap2)
2574 		return isl_bool_error;
2575 	is_subset = isl_union_map_is_subset(umap1, umap2);
2576 	if (is_subset != isl_bool_true)
2577 		return is_subset;
2578 	is_subset = isl_union_map_is_subset(umap2, umap1);
2579 	return isl_bool_not(is_subset);
2580 }
2581 
isl_union_set_is_strict_subset(__isl_keep isl_union_set * uset1,__isl_keep isl_union_set * uset2)2582 isl_bool isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
2583 	__isl_keep isl_union_set *uset2)
2584 {
2585 	return isl_union_map_is_strict_subset(uset1, uset2);
2586 }
2587 
2588 /* Internal data structure for isl_union_map_is_disjoint.
2589  * umap2 is the union map with which we are comparing.
2590  * is_disjoint is initialized to 1 and is set to 0 as soon
2591  * as the union maps turn out not to be disjoint.
2592  */
2593 struct isl_union_map_is_disjoint_data {
2594 	isl_union_map *umap2;
2595 	isl_bool is_disjoint;
2596 };
2597 
2598 /* Check if "map" is disjoint from data->umap2 and abort
2599  * the search if it is not.
2600  */
is_disjoint_entry(void ** entry,void * user)2601 static isl_stat is_disjoint_entry(void **entry, void *user)
2602 {
2603 	struct isl_union_map_is_disjoint_data *data = user;
2604 	uint32_t hash;
2605 	struct isl_hash_table_entry *entry2;
2606 	isl_map *map = *entry;
2607 
2608 	hash = isl_space_get_hash(map->dim);
2609 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2610 				     hash, &has_space, map->dim, 0);
2611 	if (!entry2)
2612 		return isl_stat_error;
2613 	if (entry2 == isl_hash_table_entry_none)
2614 		return isl_stat_ok;
2615 
2616 	data->is_disjoint = isl_map_is_disjoint(map, entry2->data);
2617 	if (data->is_disjoint < 0 || !data->is_disjoint)
2618 		return isl_stat_error;
2619 
2620 	return isl_stat_ok;
2621 }
2622 
2623 /* Are "umap1" and "umap2" disjoint?
2624  */
isl_union_map_is_disjoint(__isl_keep isl_union_map * umap1,__isl_keep isl_union_map * umap2)2625 isl_bool isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1,
2626 	__isl_keep isl_union_map *umap2)
2627 {
2628 	struct isl_union_map_is_disjoint_data data = { NULL, isl_bool_true };
2629 
2630 	umap1 = isl_union_map_copy(umap1);
2631 	umap2 = isl_union_map_copy(umap2);
2632 	umap1 = isl_union_map_align_params(umap1,
2633 						isl_union_map_get_space(umap2));
2634 	umap2 = isl_union_map_align_params(umap2,
2635 						isl_union_map_get_space(umap1));
2636 
2637 	if (!umap1 || !umap2)
2638 		goto error;
2639 
2640 	data.umap2 = umap2;
2641 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2642 				   &is_disjoint_entry, &data) < 0 &&
2643 	    data.is_disjoint)
2644 		goto error;
2645 
2646 	isl_union_map_free(umap1);
2647 	isl_union_map_free(umap2);
2648 
2649 	return data.is_disjoint;
2650 error:
2651 	isl_union_map_free(umap1);
2652 	isl_union_map_free(umap2);
2653 	return isl_bool_error;
2654 }
2655 
2656 /* Are "uset1" and "uset2" disjoint?
2657  */
isl_union_set_is_disjoint(__isl_keep isl_union_set * uset1,__isl_keep isl_union_set * uset2)2658 isl_bool isl_union_set_is_disjoint(__isl_keep isl_union_set *uset1,
2659 	__isl_keep isl_union_set *uset2)
2660 {
2661 	return isl_union_map_is_disjoint(uset1, uset2);
2662 }
2663 
sample_entry(void ** entry,void * user)2664 static isl_stat sample_entry(void **entry, void *user)
2665 {
2666 	isl_basic_map **sample = (isl_basic_map **)user;
2667 	isl_map *map = *entry;
2668 
2669 	*sample = isl_map_sample(isl_map_copy(map));
2670 	if (!*sample)
2671 		return isl_stat_error;
2672 	if (!isl_basic_map_plain_is_empty(*sample))
2673 		return isl_stat_error;
2674 	return isl_stat_ok;
2675 }
2676 
isl_union_map_sample(__isl_take isl_union_map * umap)2677 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
2678 {
2679 	isl_basic_map *sample = NULL;
2680 
2681 	if (!umap)
2682 		return NULL;
2683 
2684 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2685 				   &sample_entry, &sample) < 0 &&
2686 	    !sample)
2687 		goto error;
2688 
2689 	if (!sample)
2690 		sample = isl_basic_map_empty(isl_union_map_get_space(umap));
2691 
2692 	isl_union_map_free(umap);
2693 
2694 	return sample;
2695 error:
2696 	isl_union_map_free(umap);
2697 	return NULL;
2698 }
2699 
isl_union_set_sample(__isl_take isl_union_set * uset)2700 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
2701 {
2702 	return bset_from_bmap(isl_union_map_sample(uset));
2703 }
2704 
2705 /* Return an element in "uset" in the form of an isl_point.
2706  * Return a void isl_point if "uset" is empty.
2707  */
isl_union_set_sample_point(__isl_take isl_union_set * uset)2708 __isl_give isl_point *isl_union_set_sample_point(__isl_take isl_union_set *uset)
2709 {
2710 	return isl_basic_set_sample_point(isl_union_set_sample(uset));
2711 }
2712 
2713 struct isl_forall_data {
2714 	isl_bool res;
2715 	isl_bool (*fn)(__isl_keep isl_map *map);
2716 };
2717 
forall_entry(void ** entry,void * user)2718 static isl_stat forall_entry(void **entry, void *user)
2719 {
2720 	struct isl_forall_data *data = user;
2721 	isl_map *map = *entry;
2722 
2723 	data->res = data->fn(map);
2724 	if (data->res < 0)
2725 		return isl_stat_error;
2726 
2727 	if (!data->res)
2728 		return isl_stat_error;
2729 
2730 	return isl_stat_ok;
2731 }
2732 
union_map_forall(__isl_keep isl_union_map * umap,isl_bool (* fn)(__isl_keep isl_map * map))2733 static isl_bool union_map_forall(__isl_keep isl_union_map *umap,
2734 	isl_bool (*fn)(__isl_keep isl_map *map))
2735 {
2736 	struct isl_forall_data data = { isl_bool_true, fn };
2737 
2738 	if (!umap)
2739 		return isl_bool_error;
2740 
2741 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2742 				   &forall_entry, &data) < 0 && data.res)
2743 		return isl_bool_error;
2744 
2745 	return data.res;
2746 }
2747 
2748 struct isl_forall_user_data {
2749 	isl_bool res;
2750 	isl_bool (*fn)(__isl_keep isl_map *map, void *user);
2751 	void *user;
2752 };
2753 
forall_user_entry(void ** entry,void * user)2754 static isl_stat forall_user_entry(void **entry, void *user)
2755 {
2756 	struct isl_forall_user_data *data = user;
2757 	isl_map *map = *entry;
2758 
2759 	data->res = data->fn(map, data->user);
2760 	if (data->res < 0)
2761 		return isl_stat_error;
2762 
2763 	if (!data->res)
2764 		return isl_stat_error;
2765 
2766 	return isl_stat_ok;
2767 }
2768 
2769 /* Check if fn(map, user) returns true for all maps "map" in umap.
2770  */
union_map_forall_user(__isl_keep isl_union_map * umap,isl_bool (* fn)(__isl_keep isl_map * map,void * user),void * user)2771 static isl_bool union_map_forall_user(__isl_keep isl_union_map *umap,
2772 	isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user)
2773 {
2774 	struct isl_forall_user_data data = { isl_bool_true, fn, user };
2775 
2776 	if (!umap)
2777 		return isl_bool_error;
2778 
2779 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2780 				   &forall_user_entry, &data) < 0 && data.res)
2781 		return isl_bool_error;
2782 
2783 	return data.res;
2784 }
2785 
2786 /* Is "umap" obviously empty?
2787  */
isl_union_map_plain_is_empty(__isl_keep isl_union_map * umap)2788 isl_bool isl_union_map_plain_is_empty(__isl_keep isl_union_map *umap)
2789 {
2790 	isl_size n;
2791 
2792 	n = isl_union_map_n_map(umap);
2793 	if (n < 0)
2794 		return isl_bool_error;
2795 	return n == 0;
2796 }
2797 
isl_union_map_is_empty(__isl_keep isl_union_map * umap)2798 isl_bool isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2799 {
2800 	return union_map_forall(umap, &isl_map_is_empty);
2801 }
2802 
isl_union_set_is_empty(__isl_keep isl_union_set * uset)2803 isl_bool isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2804 {
2805 	return isl_union_map_is_empty(uset);
2806 }
2807 
is_subset_of_identity(__isl_keep isl_map * map)2808 static isl_bool is_subset_of_identity(__isl_keep isl_map *map)
2809 {
2810 	isl_bool is_subset;
2811 	isl_space *space;
2812 	isl_map *id;
2813 	isl_bool match;
2814 
2815 	match = isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);
2816 	if (match < 0)
2817 		return isl_bool_error;
2818 	if (!match)
2819 		return isl_bool_false;
2820 
2821 	space = isl_map_get_space(map);
2822 	id = isl_map_identity(space);
2823 
2824 	is_subset = isl_map_is_subset(map, id);
2825 
2826 	isl_map_free(id);
2827 
2828 	return is_subset;
2829 }
2830 
2831 /* Given an isl_union_map that consists of a single map, check
2832  * if it is single-valued.
2833  */
single_map_is_single_valued(__isl_keep isl_union_map * umap)2834 static isl_bool single_map_is_single_valued(__isl_keep isl_union_map *umap)
2835 {
2836 	isl_map *map;
2837 	isl_bool sv;
2838 
2839 	umap = isl_union_map_copy(umap);
2840 	map = isl_map_from_union_map(umap);
2841 	sv = isl_map_is_single_valued(map);
2842 	isl_map_free(map);
2843 
2844 	return sv;
2845 }
2846 
2847 /* Internal data structure for single_valued_on_domain.
2848  *
2849  * "umap" is the union map to be tested.
2850  * "sv" is set to 1 as long as "umap" may still be single-valued.
2851  */
2852 struct isl_union_map_is_sv_data {
2853 	isl_union_map *umap;
2854 	isl_bool sv;
2855 };
2856 
2857 /* Check if the data->umap is single-valued on "set".
2858  *
2859  * If data->umap consists of a single map on "set", then test it
2860  * as an isl_map.
2861  *
2862  * Otherwise, compute
2863  *
2864  *	M \circ M^-1
2865  *
2866  * check if the result is a subset of the identity mapping and
2867  * store the result in data->sv.
2868  *
2869  * Terminate as soon as data->umap has been determined not to
2870  * be single-valued.
2871  */
single_valued_on_domain(__isl_take isl_set * set,void * user)2872 static isl_stat single_valued_on_domain(__isl_take isl_set *set, void *user)
2873 {
2874 	struct isl_union_map_is_sv_data *data = user;
2875 	isl_union_map *umap, *test;
2876 	isl_size n;
2877 
2878 	umap = isl_union_map_copy(data->umap);
2879 	umap = isl_union_map_intersect_domain(umap,
2880 						isl_union_set_from_set(set));
2881 
2882 	n = isl_union_map_n_map(umap);
2883 	if (n < 0) {
2884 		data->sv = isl_bool_error;
2885 	} else if (n == 1) {
2886 		data->sv = single_map_is_single_valued(umap);
2887 		isl_union_map_free(umap);
2888 	} else {
2889 		test = isl_union_map_reverse(isl_union_map_copy(umap));
2890 		test = isl_union_map_apply_range(test, umap);
2891 
2892 		data->sv = union_map_forall(test, &is_subset_of_identity);
2893 
2894 		isl_union_map_free(test);
2895 	}
2896 
2897 	if (data->sv < 0 || !data->sv)
2898 		return isl_stat_error;
2899 	return isl_stat_ok;
2900 }
2901 
2902 /* Check if the given map is single-valued.
2903  *
2904  * If the union map consists of a single map, then test it as an isl_map.
2905  * Otherwise, check if the union map is single-valued on each of its
2906  * domain spaces.
2907  */
isl_union_map_is_single_valued(__isl_keep isl_union_map * umap)2908 isl_bool isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2909 {
2910 	isl_union_map *universe;
2911 	isl_union_set *domain;
2912 	struct isl_union_map_is_sv_data data;
2913 	isl_size n;
2914 
2915 	n = isl_union_map_n_map(umap);
2916 	if (n < 0)
2917 		return isl_bool_error;
2918 	if (n == 1)
2919 		return single_map_is_single_valued(umap);
2920 
2921 	universe = isl_union_map_universe(isl_union_map_copy(umap));
2922 	domain = isl_union_map_domain(universe);
2923 
2924 	data.sv = isl_bool_true;
2925 	data.umap = umap;
2926 	if (isl_union_set_foreach_set(domain,
2927 			    &single_valued_on_domain, &data) < 0 && data.sv)
2928 		data.sv = isl_bool_error;
2929 	isl_union_set_free(domain);
2930 
2931 	return data.sv;
2932 }
2933 
isl_union_map_is_injective(__isl_keep isl_union_map * umap)2934 isl_bool isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2935 {
2936 	isl_bool in;
2937 
2938 	umap = isl_union_map_copy(umap);
2939 	umap = isl_union_map_reverse(umap);
2940 	in = isl_union_map_is_single_valued(umap);
2941 	isl_union_map_free(umap);
2942 
2943 	return in;
2944 }
2945 
2946 /* Is "map" obviously not an identity relation because
2947  * it maps elements from one space to another space?
2948  * Update *non_identity accordingly.
2949  *
2950  * In particular, if the domain and range spaces are the same,
2951  * then the map is not considered to obviously not be an identity relation.
2952  * Otherwise, the map is considered to obviously not be an identity relation
2953  * if it is is non-empty.
2954  *
2955  * If "map" is determined to obviously not be an identity relation,
2956  * then the search is aborted.
2957  */
map_plain_is_not_identity(__isl_take isl_map * map,void * user)2958 static isl_stat map_plain_is_not_identity(__isl_take isl_map *map, void *user)
2959 {
2960 	isl_bool *non_identity = user;
2961 	isl_bool equal;
2962 
2963 	equal = isl_map_tuple_is_equal(map, isl_dim_in, map, isl_dim_out);
2964 	if (equal >= 0 && !equal)
2965 		*non_identity = isl_bool_not(isl_map_is_empty(map));
2966 	else
2967 		*non_identity = isl_bool_not(equal);
2968 	isl_map_free(map);
2969 
2970 	if (*non_identity < 0 || *non_identity)
2971 		return isl_stat_error;
2972 
2973 	return isl_stat_ok;
2974 }
2975 
2976 /* Is "umap" obviously not an identity relation because
2977  * it maps elements from one space to another space?
2978  *
2979  * As soon as a map has been found that maps elements to a different space,
2980  * non_identity is changed and the search is aborted.
2981  */
isl_union_map_plain_is_not_identity(__isl_keep isl_union_map * umap)2982 static isl_bool isl_union_map_plain_is_not_identity(
2983 	__isl_keep isl_union_map *umap)
2984 {
2985 	isl_bool non_identity;
2986 
2987 	non_identity = isl_bool_false;
2988 	if (isl_union_map_foreach_map(umap, &map_plain_is_not_identity,
2989 					&non_identity) < 0 &&
2990 	    non_identity == isl_bool_false)
2991 		return isl_bool_error;
2992 
2993 	return non_identity;
2994 }
2995 
2996 /* Does "map" only map elements to themselves?
2997  * Update *identity accordingly.
2998  *
2999  * If "map" is determined not to be an identity relation,
3000  * then the search is aborted.
3001  */
map_is_identity(__isl_take isl_map * map,void * user)3002 static isl_stat map_is_identity(__isl_take isl_map *map, void *user)
3003 {
3004 	isl_bool *identity = user;
3005 
3006 	*identity = isl_map_is_identity(map);
3007 	isl_map_free(map);
3008 
3009 	if (*identity < 0 || !*identity)
3010 		return isl_stat_error;
3011 
3012 	return isl_stat_ok;
3013 }
3014 
3015 /* Does "umap" only map elements to themselves?
3016  *
3017  * First check if there are any maps that map elements to different spaces.
3018  * If not, then check that all the maps (between identical spaces)
3019  * are identity relations.
3020  */
isl_union_map_is_identity(__isl_keep isl_union_map * umap)3021 isl_bool isl_union_map_is_identity(__isl_keep isl_union_map *umap)
3022 {
3023 	isl_bool non_identity;
3024 	isl_bool identity;
3025 
3026 	non_identity = isl_union_map_plain_is_not_identity(umap);
3027 	if (non_identity < 0 || non_identity)
3028 		return isl_bool_not(non_identity);
3029 
3030 	identity = isl_bool_true;
3031 	if (isl_union_map_foreach_map(umap, &map_is_identity, &identity) < 0 &&
3032 	    identity == isl_bool_true)
3033 		return isl_bool_error;
3034 
3035 	return identity;
3036 }
3037 
3038 /* Represents a map that has a fixed value (v) for one of its
3039  * range dimensions.
3040  * The map in this structure is not reference counted, so it
3041  * is only valid while the isl_union_map from which it was
3042  * obtained is still alive.
3043  */
3044 struct isl_fixed_map {
3045 	isl_int v;
3046 	isl_map *map;
3047 };
3048 
alloc_isl_fixed_map_array(isl_ctx * ctx,int n)3049 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
3050 	int n)
3051 {
3052 	int i;
3053 	struct isl_fixed_map *v;
3054 
3055 	v = isl_calloc_array(ctx, struct isl_fixed_map, n);
3056 	if (!v)
3057 		return NULL;
3058 	for (i = 0; i < n; ++i)
3059 		isl_int_init(v[i].v);
3060 	return v;
3061 }
3062 
free_isl_fixed_map_array(struct isl_fixed_map * v,int n)3063 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
3064 {
3065 	int i;
3066 
3067 	if (!v)
3068 		return;
3069 	for (i = 0; i < n; ++i)
3070 		isl_int_clear(v[i].v);
3071 	free(v);
3072 }
3073 
3074 /* Compare the "v" field of two isl_fixed_map structs.
3075  */
qsort_fixed_map_cmp(const void * p1,const void * p2)3076 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
3077 {
3078 	const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
3079 	const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
3080 
3081 	return isl_int_cmp(e1->v, e2->v);
3082 }
3083 
3084 /* Internal data structure used while checking whether all maps
3085  * in a union_map have a fixed value for a given output dimension.
3086  * v is the list of maps, with the fixed value for the dimension
3087  * n is the number of maps considered so far
3088  * pos is the output dimension under investigation
3089  */
3090 struct isl_fixed_dim_data {
3091 	struct isl_fixed_map *v;
3092 	int n;
3093 	int pos;
3094 };
3095 
fixed_at_pos(__isl_keep isl_map * map,void * user)3096 static isl_bool fixed_at_pos(__isl_keep isl_map *map, void *user)
3097 {
3098 	struct isl_fixed_dim_data *data = user;
3099 
3100 	data->v[data->n].map = map;
3101 	return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
3102 				      &data->v[data->n++].v);
3103 }
3104 
3105 static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap,
3106 	int first, int n_range);
3107 
3108 /* Given a list of the maps, with their fixed values at output dimension "pos",
3109  * check whether the ranges of the maps form an obvious partition.
3110  *
3111  * We first sort the maps according to their fixed values.
3112  * If all maps have a different value, then we know the ranges form
3113  * a partition.
3114  * Otherwise, we collect the maps with the same fixed value and
3115  * check whether each such collection is obviously injective
3116  * based on later dimensions.
3117  */
separates(struct isl_fixed_map * v,int n,__isl_take isl_space * space,int pos,int n_range)3118 static int separates(struct isl_fixed_map *v, int n,
3119 	__isl_take isl_space *space, int pos, int n_range)
3120 {
3121 	int i;
3122 
3123 	if (!v)
3124 		goto error;
3125 
3126 	qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
3127 
3128 	for (i = 0; i + 1 < n; ++i) {
3129 		int j, k;
3130 		isl_union_map *part;
3131 		int injective;
3132 
3133 		for (j = i + 1; j < n; ++j)
3134 			if (isl_int_ne(v[i].v, v[j].v))
3135 				break;
3136 
3137 		if (j == i + 1)
3138 			continue;
3139 
3140 		part = isl_union_map_alloc(isl_space_copy(space), j - i);
3141 		for (k = i; k < j; ++k)
3142 			part = isl_union_map_add_map(part,
3143 						     isl_map_copy(v[k].map));
3144 
3145 		injective = plain_injective_on_range(part, pos + 1, n_range);
3146 		if (injective < 0)
3147 			goto error;
3148 		if (!injective)
3149 			break;
3150 
3151 		i = j - 1;
3152 	}
3153 
3154 	isl_space_free(space);
3155 	free_isl_fixed_map_array(v, n);
3156 	return i + 1 >= n;
3157 error:
3158 	isl_space_free(space);
3159 	free_isl_fixed_map_array(v, n);
3160 	return -1;
3161 }
3162 
3163 /* Check whether the maps in umap have obviously distinct ranges.
3164  * In particular, check for an output dimension in the range
3165  * [first,n_range) for which all maps have a fixed value
3166  * and then check if these values, possibly along with fixed values
3167  * at later dimensions, entail distinct ranges.
3168  */
plain_injective_on_range(__isl_take isl_union_map * umap,int first,int n_range)3169 static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap,
3170 	int first, int n_range)
3171 {
3172 	isl_ctx *ctx;
3173 	isl_size n;
3174 	struct isl_fixed_dim_data data = { NULL };
3175 
3176 	ctx = isl_union_map_get_ctx(umap);
3177 
3178 	n = isl_union_map_n_map(umap);
3179 	if (n < 0)
3180 		goto error;
3181 
3182 	if (n <= 1) {
3183 		isl_union_map_free(umap);
3184 		return isl_bool_true;
3185 	}
3186 
3187 	if (first >= n_range) {
3188 		isl_union_map_free(umap);
3189 		return isl_bool_false;
3190 	}
3191 
3192 	data.v = alloc_isl_fixed_map_array(ctx, n);
3193 	if (!data.v)
3194 		goto error;
3195 
3196 	for (data.pos = first; data.pos < n_range; ++data.pos) {
3197 		isl_bool fixed;
3198 		int injective;
3199 		isl_space *space;
3200 
3201 		data.n = 0;
3202 		fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
3203 		if (fixed < 0)
3204 			goto error;
3205 		if (!fixed)
3206 			continue;
3207 		space = isl_union_map_get_space(umap);
3208 		injective = separates(data.v, n, space, data.pos, n_range);
3209 		isl_union_map_free(umap);
3210 		return injective;
3211 	}
3212 
3213 	free_isl_fixed_map_array(data.v, n);
3214 	isl_union_map_free(umap);
3215 
3216 	return isl_bool_false;
3217 error:
3218 	free_isl_fixed_map_array(data.v, n);
3219 	isl_union_map_free(umap);
3220 	return isl_bool_error;
3221 }
3222 
3223 /* Check whether the maps in umap that map to subsets of "ran"
3224  * have obviously distinct ranges.
3225  */
plain_injective_on_range_wrap(__isl_keep isl_set * ran,void * user)3226 static isl_bool plain_injective_on_range_wrap(__isl_keep isl_set *ran,
3227 	void *user)
3228 {
3229 	isl_size dim;
3230 	isl_union_map *umap = user;
3231 
3232 	dim = isl_set_dim(ran, isl_dim_set);
3233 	if (dim < 0)
3234 		return isl_bool_error;
3235 
3236 	umap = isl_union_map_copy(umap);
3237 	umap = isl_union_map_intersect_range(umap,
3238 			isl_union_set_from_set(isl_set_copy(ran)));
3239 	return plain_injective_on_range(umap, 0, dim);
3240 }
3241 
3242 /* Check if the given union_map is obviously injective.
3243  *
3244  * In particular, we first check if all individual maps are obviously
3245  * injective and then check if all the ranges of these maps are
3246  * obviously disjoint.
3247  */
isl_union_map_plain_is_injective(__isl_keep isl_union_map * umap)3248 isl_bool isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
3249 {
3250 	isl_bool in;
3251 	isl_union_map *univ;
3252 	isl_union_set *ran;
3253 
3254 	in = union_map_forall(umap, &isl_map_plain_is_injective);
3255 	if (in < 0)
3256 		return isl_bool_error;
3257 	if (!in)
3258 		return isl_bool_false;
3259 
3260 	univ = isl_union_map_universe(isl_union_map_copy(umap));
3261 	ran = isl_union_map_range(univ);
3262 
3263 	in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
3264 
3265 	isl_union_set_free(ran);
3266 
3267 	return in;
3268 }
3269 
isl_union_map_is_bijective(__isl_keep isl_union_map * umap)3270 isl_bool isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
3271 {
3272 	isl_bool sv;
3273 
3274 	sv = isl_union_map_is_single_valued(umap);
3275 	if (sv < 0 || !sv)
3276 		return sv;
3277 
3278 	return isl_union_map_is_injective(umap);
3279 }
3280 
isl_union_map_zip(__isl_take isl_union_map * umap)3281 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
3282 {
3283 	struct isl_un_op_drop_user_data data = { &isl_map_can_zip };
3284 	struct isl_un_op_control control = {
3285 		.filter = &un_op_filter_drop_user,
3286 		.filter_user = &data,
3287 		.fn_map = &isl_map_zip,
3288 	};
3289 	return un_op(umap, &control);
3290 }
3291 
3292 /* Given a union map, take the maps of the form A -> (B -> C) and
3293  * return the union of the corresponding maps (A -> B) -> C.
3294  */
isl_union_map_uncurry(__isl_take isl_union_map * umap)3295 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
3296 {
3297 	struct isl_un_op_drop_user_data data = { &isl_map_can_uncurry };
3298 	struct isl_un_op_control control = {
3299 		.filter = &un_op_filter_drop_user,
3300 		.filter_user = &data,
3301 		.fn_map = &isl_map_uncurry,
3302 	};
3303 	return un_op(umap, &control);
3304 }
3305 
3306 /* Given a union map, take the maps of the form (A -> B) -> C and
3307  * return the union of the corresponding maps A -> (B -> C).
3308  */
isl_union_map_curry(__isl_take isl_union_map * umap)3309 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
3310 {
3311 	struct isl_un_op_drop_user_data data = { &isl_map_can_curry };
3312 	struct isl_un_op_control control = {
3313 		.filter = &un_op_filter_drop_user,
3314 		.filter_user = &data,
3315 		.fn_map = &isl_map_curry,
3316 	};
3317 	return un_op(umap, &control);
3318 }
3319 
3320 /* Given a union map, take the maps of the form A -> ((B -> C) -> D) and
3321  * return the union of the corresponding maps A -> (B -> (C -> D)).
3322  */
isl_union_map_range_curry(__isl_take isl_union_map * umap)3323 __isl_give isl_union_map *isl_union_map_range_curry(
3324 	__isl_take isl_union_map *umap)
3325 {
3326 	struct isl_un_op_drop_user_data data = { &isl_map_can_range_curry };
3327 	struct isl_un_op_control control = {
3328 		.filter = &un_op_filter_drop_user,
3329 		.filter_user = &data,
3330 		.fn_map = &isl_map_range_curry,
3331 	};
3332 	return un_op(umap, &control);
3333 }
3334 
isl_union_set_lift(__isl_take isl_union_set * uset)3335 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
3336 {
3337 	struct isl_un_op_control control = {
3338 		.fn_map = &isl_set_lift,
3339 	};
3340 	return un_op(uset, &control);
3341 }
3342 
coefficients_entry(void ** entry,void * user)3343 static isl_stat coefficients_entry(void **entry, void *user)
3344 {
3345 	isl_set *set = *entry;
3346 	isl_union_set **res = user;
3347 
3348 	set = isl_set_copy(set);
3349 	set = isl_set_from_basic_set(isl_set_coefficients(set));
3350 	*res = isl_union_set_add_set(*res, set);
3351 
3352 	return isl_stat_ok;
3353 }
3354 
isl_union_set_coefficients(__isl_take isl_union_set * uset)3355 __isl_give isl_union_set *isl_union_set_coefficients(
3356 	__isl_take isl_union_set *uset)
3357 {
3358 	isl_ctx *ctx;
3359 	isl_space *space;
3360 	isl_union_set *res;
3361 
3362 	if (!uset)
3363 		return NULL;
3364 
3365 	ctx = isl_union_set_get_ctx(uset);
3366 	space = isl_space_set_alloc(ctx, 0, 0);
3367 	res = isl_union_map_alloc(space, uset->table.n);
3368 	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
3369 				   &coefficients_entry, &res) < 0)
3370 		goto error;
3371 
3372 	isl_union_set_free(uset);
3373 	return res;
3374 error:
3375 	isl_union_set_free(uset);
3376 	isl_union_set_free(res);
3377 	return NULL;
3378 }
3379 
solutions_entry(void ** entry,void * user)3380 static isl_stat solutions_entry(void **entry, void *user)
3381 {
3382 	isl_set *set = *entry;
3383 	isl_union_set **res = user;
3384 
3385 	set = isl_set_copy(set);
3386 	set = isl_set_from_basic_set(isl_set_solutions(set));
3387 	if (!*res)
3388 		*res = isl_union_set_from_set(set);
3389 	else
3390 		*res = isl_union_set_add_set(*res, set);
3391 
3392 	if (!*res)
3393 		return isl_stat_error;
3394 
3395 	return isl_stat_ok;
3396 }
3397 
isl_union_set_solutions(__isl_take isl_union_set * uset)3398 __isl_give isl_union_set *isl_union_set_solutions(
3399 	__isl_take isl_union_set *uset)
3400 {
3401 	isl_union_set *res = NULL;
3402 
3403 	if (!uset)
3404 		return NULL;
3405 
3406 	if (uset->table.n == 0) {
3407 		res = isl_union_set_empty(isl_union_set_get_space(uset));
3408 		isl_union_set_free(uset);
3409 		return res;
3410 	}
3411 
3412 	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
3413 				   &solutions_entry, &res) < 0)
3414 		goto error;
3415 
3416 	isl_union_set_free(uset);
3417 	return res;
3418 error:
3419 	isl_union_set_free(uset);
3420 	isl_union_set_free(res);
3421 	return NULL;
3422 }
3423 
3424 /* Is the domain space of "map" equal to "space"?
3425  */
domain_match(__isl_keep isl_map * map,__isl_keep isl_space * space)3426 static int domain_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3427 {
3428 	return isl_map_space_tuple_is_equal(map, isl_dim_in,
3429 					space, isl_dim_out);
3430 }
3431 
3432 /* Is the range space of "map" equal to "space"?
3433  */
range_match(__isl_keep isl_map * map,__isl_keep isl_space * space)3434 static int range_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3435 {
3436 	return isl_map_space_tuple_is_equal(map, isl_dim_out,
3437 					space, isl_dim_out);
3438 }
3439 
3440 /* Is the set space of "map" equal to "space"?
3441  */
set_match(__isl_keep isl_map * map,__isl_keep isl_space * space)3442 static int set_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3443 {
3444 	return isl_map_space_tuple_is_equal(map, isl_dim_set,
3445 					space, isl_dim_out);
3446 }
3447 
3448 /* Internal data structure for preimage_pw_multi_aff.
3449  *
3450  * "pma" is the function under which the preimage should be taken.
3451  * "space" is the space of "pma".
3452  * "res" collects the results.
3453  * "fn" computes the preimage for a given map.
3454  * "match" returns true if "fn" can be called.
3455  */
3456 struct isl_union_map_preimage_data {
3457 	isl_space *space;
3458 	isl_pw_multi_aff *pma;
3459 	isl_union_map *res;
3460 	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);
3461 	__isl_give isl_map *(*fn)(__isl_take isl_map *map,
3462 		__isl_take isl_pw_multi_aff *pma);
3463 };
3464 
3465 /* Call data->fn to compute the preimage of the domain or range of *entry
3466  * under the function represented by data->pma, provided the domain/range
3467  * space of *entry matches the target space of data->pma
3468  * (as given by data->match), and add the result to data->res.
3469  */
preimage_entry(void ** entry,void * user)3470 static isl_stat preimage_entry(void **entry, void *user)
3471 {
3472 	int m;
3473 	isl_map *map = *entry;
3474 	struct isl_union_map_preimage_data *data = user;
3475 	isl_bool empty;
3476 
3477 	m = data->match(map, data->space);
3478 	if (m < 0)
3479 		return isl_stat_error;
3480 	if (!m)
3481 		return isl_stat_ok;
3482 
3483 	map = isl_map_copy(map);
3484 	map = data->fn(map, isl_pw_multi_aff_copy(data->pma));
3485 
3486 	empty = isl_map_is_empty(map);
3487 	if (empty < 0 || empty) {
3488 		isl_map_free(map);
3489 		return empty < 0 ? isl_stat_error : isl_stat_ok;
3490 	}
3491 
3492 	data->res = isl_union_map_add_map(data->res, map);
3493 
3494 	return isl_stat_ok;
3495 }
3496 
3497 /* Compute the preimage of the domain or range of "umap" under the function
3498  * represented by "pma".
3499  * In other words, plug in "pma" in the domain or range of "umap".
3500  * The function "fn" performs the actual preimage computation on a map,
3501  * while "match" determines to which maps the function should be applied.
3502  */
preimage_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_pw_multi_aff * pma,int (* match)(__isl_keep isl_map * map,__isl_keep isl_space * space),__isl_give isl_map * (* fn)(__isl_take isl_map * map,__isl_take isl_pw_multi_aff * pma))3503 static __isl_give isl_union_map *preimage_pw_multi_aff(
3504 	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma,
3505 	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),
3506 	__isl_give isl_map *(*fn)(__isl_take isl_map *map,
3507 		__isl_take isl_pw_multi_aff *pma))
3508 {
3509 	isl_ctx *ctx;
3510 	isl_space *space;
3511 	struct isl_union_map_preimage_data data;
3512 
3513 	umap = isl_union_map_align_params(umap,
3514 					    isl_pw_multi_aff_get_space(pma));
3515 	pma = isl_pw_multi_aff_align_params(pma, isl_union_map_get_space(umap));
3516 
3517 	if (!umap || !pma)
3518 		goto error;
3519 
3520 	ctx = isl_union_map_get_ctx(umap);
3521 	space = isl_union_map_get_space(umap);
3522 	data.space = isl_pw_multi_aff_get_space(pma);
3523 	data.pma = pma;
3524 	data.res = isl_union_map_alloc(space, umap->table.n);
3525 	data.match = match;
3526 	data.fn = fn;
3527 	if (isl_hash_table_foreach(ctx, &umap->table, &preimage_entry,
3528 					&data) < 0)
3529 		data.res = isl_union_map_free(data.res);
3530 
3531 	isl_space_free(data.space);
3532 	isl_union_map_free(umap);
3533 	isl_pw_multi_aff_free(pma);
3534 	return data.res;
3535 error:
3536 	isl_union_map_free(umap);
3537 	isl_pw_multi_aff_free(pma);
3538 	return NULL;
3539 }
3540 
3541 /* Compute the preimage of the domain of "umap" under the function
3542  * represented by "pma".
3543  * In other words, plug in "pma" in the domain of "umap".
3544  * The result contains maps that live in the same spaces as the maps of "umap"
3545  * with domain space equal to the target space of "pma",
3546  * except that the domain has been replaced by the domain space of "pma".
3547  */
isl_union_map_preimage_domain_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_pw_multi_aff * pma)3548 __isl_give isl_union_map *isl_union_map_preimage_domain_pw_multi_aff(
3549 	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)
3550 {
3551 	return preimage_pw_multi_aff(umap, pma, &domain_match,
3552 					&isl_map_preimage_domain_pw_multi_aff);
3553 }
3554 
3555 /* Compute the preimage of the range of "umap" under the function
3556  * represented by "pma".
3557  * In other words, plug in "pma" in the range of "umap".
3558  * The result contains maps that live in the same spaces as the maps of "umap"
3559  * with range space equal to the target space of "pma",
3560  * except that the range has been replaced by the domain space of "pma".
3561  */
isl_union_map_preimage_range_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_pw_multi_aff * pma)3562 __isl_give isl_union_map *isl_union_map_preimage_range_pw_multi_aff(
3563 	__isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)
3564 {
3565 	return preimage_pw_multi_aff(umap, pma, &range_match,
3566 					&isl_map_preimage_range_pw_multi_aff);
3567 }
3568 
3569 /* Compute the preimage of "uset" under the function represented by "pma".
3570  * In other words, plug in "pma" in "uset".
3571  * The result contains sets that live in the same spaces as the sets of "uset"
3572  * with space equal to the target space of "pma",
3573  * except that the space has been replaced by the domain space of "pma".
3574  */
isl_union_set_preimage_pw_multi_aff(__isl_take isl_union_set * uset,__isl_take isl_pw_multi_aff * pma)3575 __isl_give isl_union_set *isl_union_set_preimage_pw_multi_aff(
3576 	__isl_take isl_union_set *uset, __isl_take isl_pw_multi_aff *pma)
3577 {
3578 	return preimage_pw_multi_aff(uset, pma, &set_match,
3579 					&isl_set_preimage_pw_multi_aff);
3580 }
3581 
3582 /* Compute the preimage of the domain of "umap" under the function
3583  * represented by "ma".
3584  * In other words, plug in "ma" in the domain of "umap".
3585  * The result contains maps that live in the same spaces as the maps of "umap"
3586  * with domain space equal to the target space of "ma",
3587  * except that the domain has been replaced by the domain space of "ma".
3588  */
isl_union_map_preimage_domain_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_aff * ma)3589 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(
3590 	__isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
3591 {
3592 	return isl_union_map_preimage_domain_pw_multi_aff(umap,
3593 					isl_pw_multi_aff_from_multi_aff(ma));
3594 }
3595 
3596 /* Compute the preimage of the range of "umap" under the function
3597  * represented by "ma".
3598  * In other words, plug in "ma" in the range of "umap".
3599  * The result contains maps that live in the same spaces as the maps of "umap"
3600  * with range space equal to the target space of "ma",
3601  * except that the range has been replaced by the domain space of "ma".
3602  */
isl_union_map_preimage_range_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_aff * ma)3603 __isl_give isl_union_map *isl_union_map_preimage_range_multi_aff(
3604 	__isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
3605 {
3606 	return isl_union_map_preimage_range_pw_multi_aff(umap,
3607 					isl_pw_multi_aff_from_multi_aff(ma));
3608 }
3609 
3610 /* Compute the preimage of "uset" under the function represented by "ma".
3611  * In other words, plug in "ma" in "uset".
3612  * The result contains sets that live in the same spaces as the sets of "uset"
3613  * with space equal to the target space of "ma",
3614  * except that the space has been replaced by the domain space of "ma".
3615  */
isl_union_set_preimage_multi_aff(__isl_take isl_union_set * uset,__isl_take isl_multi_aff * ma)3616 __isl_give isl_union_map *isl_union_set_preimage_multi_aff(
3617 	__isl_take isl_union_set *uset, __isl_take isl_multi_aff *ma)
3618 {
3619 	return isl_union_set_preimage_pw_multi_aff(uset,
3620 					isl_pw_multi_aff_from_multi_aff(ma));
3621 }
3622 
3623 /* Internal data structure for preimage_multi_pw_aff.
3624  *
3625  * "mpa" is the function under which the preimage should be taken.
3626  * "space" is the space of "mpa".
3627  * "res" collects the results.
3628  * "fn" computes the preimage for a given map.
3629  * "match" returns true if "fn" can be called.
3630  */
3631 struct isl_union_map_preimage_mpa_data {
3632 	isl_space *space;
3633 	isl_multi_pw_aff *mpa;
3634 	isl_union_map *res;
3635 	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);
3636 	__isl_give isl_map *(*fn)(__isl_take isl_map *map,
3637 		__isl_take isl_multi_pw_aff *mpa);
3638 };
3639 
3640 /* Call data->fn to compute the preimage of the domain or range of *entry
3641  * under the function represented by data->mpa, provided the domain/range
3642  * space of *entry matches the target space of data->mpa
3643  * (as given by data->match), and add the result to data->res.
3644  */
preimage_mpa_entry(void ** entry,void * user)3645 static isl_stat preimage_mpa_entry(void **entry, void *user)
3646 {
3647 	int m;
3648 	isl_map *map = *entry;
3649 	struct isl_union_map_preimage_mpa_data *data = user;
3650 	isl_bool empty;
3651 
3652 	m = data->match(map, data->space);
3653 	if (m < 0)
3654 		return isl_stat_error;
3655 	if (!m)
3656 		return isl_stat_ok;
3657 
3658 	map = isl_map_copy(map);
3659 	map = data->fn(map, isl_multi_pw_aff_copy(data->mpa));
3660 
3661 	empty = isl_map_is_empty(map);
3662 	if (empty < 0 || empty) {
3663 		isl_map_free(map);
3664 		return empty < 0 ? isl_stat_error : isl_stat_ok;
3665 	}
3666 
3667 	data->res = isl_union_map_add_map(data->res, map);
3668 
3669 	return isl_stat_ok;
3670 }
3671 
3672 /* Compute the preimage of the domain or range of "umap" under the function
3673  * represented by "mpa".
3674  * In other words, plug in "mpa" in the domain or range of "umap".
3675  * The function "fn" performs the actual preimage computation on a map,
3676  * while "match" determines to which maps the function should be applied.
3677  */
preimage_multi_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_pw_aff * mpa,int (* match)(__isl_keep isl_map * map,__isl_keep isl_space * space),__isl_give isl_map * (* fn)(__isl_take isl_map * map,__isl_take isl_multi_pw_aff * mpa))3678 static __isl_give isl_union_map *preimage_multi_pw_aff(
3679 	__isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa,
3680 	int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),
3681 	__isl_give isl_map *(*fn)(__isl_take isl_map *map,
3682 		__isl_take isl_multi_pw_aff *mpa))
3683 {
3684 	isl_ctx *ctx;
3685 	isl_space *space;
3686 	struct isl_union_map_preimage_mpa_data data;
3687 
3688 	umap = isl_union_map_align_params(umap,
3689 					    isl_multi_pw_aff_get_space(mpa));
3690 	mpa = isl_multi_pw_aff_align_params(mpa, isl_union_map_get_space(umap));
3691 
3692 	if (!umap || !mpa)
3693 		goto error;
3694 
3695 	ctx = isl_union_map_get_ctx(umap);
3696 	space = isl_union_map_get_space(umap);
3697 	data.space = isl_multi_pw_aff_get_space(mpa);
3698 	data.mpa = mpa;
3699 	data.res = isl_union_map_alloc(space, umap->table.n);
3700 	data.match = match;
3701 	data.fn = fn;
3702 	if (isl_hash_table_foreach(ctx, &umap->table, &preimage_mpa_entry,
3703 					&data) < 0)
3704 		data.res = isl_union_map_free(data.res);
3705 
3706 	isl_space_free(data.space);
3707 	isl_union_map_free(umap);
3708 	isl_multi_pw_aff_free(mpa);
3709 	return data.res;
3710 error:
3711 	isl_union_map_free(umap);
3712 	isl_multi_pw_aff_free(mpa);
3713 	return NULL;
3714 }
3715 
3716 /* Compute the preimage of the domain of "umap" under the function
3717  * represented by "mpa".
3718  * In other words, plug in "mpa" in the domain of "umap".
3719  * The result contains maps that live in the same spaces as the maps of "umap"
3720  * with domain space equal to the target space of "mpa",
3721  * except that the domain has been replaced by the domain space of "mpa".
3722  */
isl_union_map_preimage_domain_multi_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_pw_aff * mpa)3723 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_pw_aff(
3724 	__isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa)
3725 {
3726 	return preimage_multi_pw_aff(umap, mpa, &domain_match,
3727 					&isl_map_preimage_domain_multi_pw_aff);
3728 }
3729 
3730 /* Internal data structure for preimage_upma.
3731  *
3732  * "umap" is the map of which the preimage should be computed.
3733  * "res" collects the results.
3734  * "fn" computes the preimage for a given piecewise multi-affine function.
3735  */
3736 struct isl_union_map_preimage_upma_data {
3737 	isl_union_map *umap;
3738 	isl_union_map *res;
3739 	__isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,
3740 		__isl_take isl_pw_multi_aff *pma);
3741 };
3742 
3743 /* Call data->fn to compute the preimage of the domain or range of data->umap
3744  * under the function represented by pma and add the result to data->res.
3745  */
preimage_upma(__isl_take isl_pw_multi_aff * pma,void * user)3746 static isl_stat preimage_upma(__isl_take isl_pw_multi_aff *pma, void *user)
3747 {
3748 	struct isl_union_map_preimage_upma_data *data = user;
3749 	isl_union_map *umap;
3750 
3751 	umap = isl_union_map_copy(data->umap);
3752 	umap = data->fn(umap, pma);
3753 	data->res = isl_union_map_union(data->res, umap);
3754 
3755 	return data->res ? isl_stat_ok : isl_stat_error;
3756 }
3757 
3758 /* Compute the preimage of the domain or range of "umap" under the function
3759  * represented by "upma".
3760  * In other words, plug in "upma" in the domain or range of "umap".
3761  * The function "fn" performs the actual preimage computation
3762  * on a piecewise multi-affine function.
3763  */
preimage_union_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_union_pw_multi_aff * upma,__isl_give isl_union_map * (* fn)(__isl_take isl_union_map * umap,__isl_take isl_pw_multi_aff * pma))3764 static __isl_give isl_union_map *preimage_union_pw_multi_aff(
3765 	__isl_take isl_union_map *umap,
3766 	__isl_take isl_union_pw_multi_aff *upma,
3767 	__isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,
3768 		__isl_take isl_pw_multi_aff *pma))
3769 {
3770 	struct isl_union_map_preimage_upma_data data;
3771 
3772 	data.umap = umap;
3773 	data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3774 	data.fn = fn;
3775 	if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3776 						    &preimage_upma, &data) < 0)
3777 		data.res = isl_union_map_free(data.res);
3778 
3779 	isl_union_map_free(umap);
3780 	isl_union_pw_multi_aff_free(upma);
3781 
3782 	return data.res;
3783 }
3784 
3785 /* Compute the preimage of the domain of "umap" under the function
3786  * represented by "upma".
3787  * In other words, plug in "upma" in the domain of "umap".
3788  * The result contains maps that live in the same spaces as the maps of "umap"
3789  * with domain space equal to one of the target spaces of "upma",
3790  * except that the domain has been replaced by one of the domain spaces that
3791  * correspond to that target space of "upma".
3792  */
isl_union_map_preimage_domain_union_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_union_pw_multi_aff * upma)3793 __isl_give isl_union_map *isl_union_map_preimage_domain_union_pw_multi_aff(
3794 	__isl_take isl_union_map *umap,
3795 	__isl_take isl_union_pw_multi_aff *upma)
3796 {
3797 	return preimage_union_pw_multi_aff(umap, upma,
3798 				&isl_union_map_preimage_domain_pw_multi_aff);
3799 }
3800 
3801 /* Compute the preimage of the range of "umap" under the function
3802  * represented by "upma".
3803  * In other words, plug in "upma" in the range of "umap".
3804  * The result contains maps that live in the same spaces as the maps of "umap"
3805  * with range space equal to one of the target spaces of "upma",
3806  * except that the range has been replaced by one of the domain spaces that
3807  * correspond to that target space of "upma".
3808  */
isl_union_map_preimage_range_union_pw_multi_aff(__isl_take isl_union_map * umap,__isl_take isl_union_pw_multi_aff * upma)3809 __isl_give isl_union_map *isl_union_map_preimage_range_union_pw_multi_aff(
3810 	__isl_take isl_union_map *umap,
3811 	__isl_take isl_union_pw_multi_aff *upma)
3812 {
3813 	return preimage_union_pw_multi_aff(umap, upma,
3814 				&isl_union_map_preimage_range_pw_multi_aff);
3815 }
3816 
3817 /* Compute the preimage of "uset" under the function represented by "upma".
3818  * In other words, plug in "upma" in the range of "uset".
3819  * The result contains sets that live in the same spaces as the sets of "uset"
3820  * with space equal to one of the target spaces of "upma",
3821  * except that the space has been replaced by one of the domain spaces that
3822  * correspond to that target space of "upma".
3823  */
isl_union_set_preimage_union_pw_multi_aff(__isl_take isl_union_set * uset,__isl_take isl_union_pw_multi_aff * upma)3824 __isl_give isl_union_set *isl_union_set_preimage_union_pw_multi_aff(
3825 	__isl_take isl_union_set *uset,
3826 	__isl_take isl_union_pw_multi_aff *upma)
3827 {
3828 	return preimage_union_pw_multi_aff(uset, upma,
3829 					&isl_union_set_preimage_pw_multi_aff);
3830 }
3831 
3832 /* Reset the user pointer on all identifiers of parameters and tuples
3833  * of the spaces of "umap".
3834  */
isl_union_map_reset_user(__isl_take isl_union_map * umap)3835 __isl_give isl_union_map *isl_union_map_reset_user(
3836 	__isl_take isl_union_map *umap)
3837 {
3838 	umap = isl_union_map_cow(umap);
3839 	if (!umap)
3840 		return NULL;
3841 	umap->dim = isl_space_reset_user(umap->dim);
3842 	if (!umap->dim)
3843 		return isl_union_map_free(umap);
3844 	return total(umap, &isl_map_reset_user);
3845 }
3846 
3847 /* Reset the user pointer on all identifiers of parameters and tuples
3848  * of the spaces of "uset".
3849  */
isl_union_set_reset_user(__isl_take isl_union_set * uset)3850 __isl_give isl_union_set *isl_union_set_reset_user(
3851 	__isl_take isl_union_set *uset)
3852 {
3853 	return isl_union_map_reset_user(uset);
3854 }
3855 
3856 /* Remove all existentially quantified variables and integer divisions
3857  * from "umap" using Fourier-Motzkin elimination.
3858  */
isl_union_map_remove_divs(__isl_take isl_union_map * umap)3859 __isl_give isl_union_map *isl_union_map_remove_divs(
3860 	__isl_take isl_union_map *umap)
3861 {
3862 	return total(umap, &isl_map_remove_divs);
3863 }
3864 
3865 /* Remove all existentially quantified variables and integer divisions
3866  * from "uset" using Fourier-Motzkin elimination.
3867  */
isl_union_set_remove_divs(__isl_take isl_union_set * uset)3868 __isl_give isl_union_set *isl_union_set_remove_divs(
3869 	__isl_take isl_union_set *uset)
3870 {
3871 	return isl_union_map_remove_divs(uset);
3872 }
3873 
3874 /* Internal data structure for isl_union_map_project_out.
3875  * "type", "first" and "n" are the arguments for the isl_map_project_out
3876  * call.
3877  * "res" collects the results.
3878  */
3879 struct isl_union_map_project_out_data {
3880 	enum isl_dim_type type;
3881 	unsigned first;
3882 	unsigned n;
3883 
3884 	isl_union_map *res;
3885 };
3886 
3887 /* Turn the data->n dimensions of type data->type, starting at data->first
3888  * into existentially quantified variables and add the result to data->res.
3889  */
project_out(__isl_take isl_map * map,void * user)3890 static isl_stat project_out(__isl_take isl_map *map, void *user)
3891 {
3892 	struct isl_union_map_project_out_data *data = user;
3893 
3894 	map = isl_map_project_out(map, data->type, data->first, data->n);
3895 	data->res = isl_union_map_add_map(data->res, map);
3896 
3897 	return isl_stat_ok;
3898 }
3899 
3900 /* Turn the "n" dimensions of type "type", starting at "first"
3901  * into existentially quantified variables.
3902  * Since the space of an isl_union_map only contains parameters,
3903  * type is required to be equal to isl_dim_param.
3904  */
isl_union_map_project_out(__isl_take isl_union_map * umap,enum isl_dim_type type,unsigned first,unsigned n)3905 __isl_give isl_union_map *isl_union_map_project_out(
3906 	__isl_take isl_union_map *umap,
3907 	enum isl_dim_type type, unsigned first, unsigned n)
3908 {
3909 	isl_space *space;
3910 	struct isl_union_map_project_out_data data = { type, first, n };
3911 
3912 	if (!umap)
3913 		return NULL;
3914 
3915 	if (type != isl_dim_param)
3916 		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
3917 			"can only project out parameters",
3918 			return isl_union_map_free(umap));
3919 
3920 	space = isl_union_map_get_space(umap);
3921 	space = isl_space_drop_dims(space, type, first, n);
3922 	data.res = isl_union_map_empty(space);
3923 	if (isl_union_map_foreach_map(umap, &project_out, &data) < 0)
3924 		data.res = isl_union_map_free(data.res);
3925 
3926 	isl_union_map_free(umap);
3927 
3928 	return data.res;
3929 }
3930 
3931 #undef TYPE
3932 #define TYPE	isl_union_map
3933 #include "isl_project_out_all_params_templ.c"
3934 
3935 /* Turn the "n" dimensions of type "type", starting at "first"
3936  * into existentially quantified variables.
3937  * Since the space of an isl_union_set only contains parameters,
3938  * "type" is required to be equal to isl_dim_param.
3939  */
isl_union_set_project_out(__isl_take isl_union_set * uset,enum isl_dim_type type,unsigned first,unsigned n)3940 __isl_give isl_union_set *isl_union_set_project_out(
3941 	__isl_take isl_union_set *uset,
3942 	enum isl_dim_type type, unsigned first, unsigned n)
3943 {
3944 	return isl_union_map_project_out(uset, type, first, n);
3945 }
3946 
3947 /* Project out all parameters from "uset" by existentially quantifying
3948  * over them.
3949  */
isl_union_set_project_out_all_params(__isl_take isl_union_set * uset)3950 __isl_give isl_union_set *isl_union_set_project_out_all_params(
3951 	__isl_take isl_union_set *uset)
3952 {
3953 	return uset_from_umap(
3954 		    isl_union_map_project_out_all_params(uset_to_umap(uset)));
3955 }
3956 
3957 /* Internal data structure for isl_union_map_involves_dims.
3958  * "first" and "n" are the arguments for the isl_map_involves_dims calls.
3959  */
3960 struct isl_union_map_involves_dims_data {
3961 	unsigned first;
3962 	unsigned n;
3963 };
3964 
3965 /* Does "map" _not_ involve the data->n parameters starting at data->first?
3966  */
map_excludes(__isl_keep isl_map * map,void * user)3967 static isl_bool map_excludes(__isl_keep isl_map *map, void *user)
3968 {
3969 	struct isl_union_map_involves_dims_data *data = user;
3970 	isl_bool involves;
3971 
3972 	involves = isl_map_involves_dims(map,
3973 					isl_dim_param, data->first, data->n);
3974 	return isl_bool_not(involves);
3975 }
3976 
3977 /* Does "umap" involve any of the n parameters starting at first?
3978  * "type" is required to be set to isl_dim_param.
3979  *
3980  * "umap" involves any of those parameters if any of its maps
3981  * involve the parameters.  In other words, "umap" does not
3982  * involve any of the parameters if all its maps to not
3983  * involve the parameters.
3984  */
isl_union_map_involves_dims(__isl_keep isl_union_map * umap,enum isl_dim_type type,unsigned first,unsigned n)3985 isl_bool isl_union_map_involves_dims(__isl_keep isl_union_map *umap,
3986 	enum isl_dim_type type, unsigned first, unsigned n)
3987 {
3988 	struct isl_union_map_involves_dims_data data = { first, n };
3989 	isl_bool excludes;
3990 
3991 	if (type != isl_dim_param)
3992 		isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
3993 			"can only reference parameters", return isl_bool_error);
3994 
3995 	excludes = union_map_forall_user(umap, &map_excludes, &data);
3996 
3997 	return isl_bool_not(excludes);
3998 }
3999 
4000 /* Internal data structure for isl_union_map_reset_range_space.
4001  * "range" is the space from which to set the range space.
4002  * "res" collects the results.
4003  */
4004 struct isl_union_map_reset_range_space_data {
4005 	isl_space *range;
4006 	isl_union_map *res;
4007 };
4008 
4009 /* Replace the range space of "map" by the range space of data->range and
4010  * add the result to data->res.
4011  */
reset_range_space(__isl_take isl_map * map,void * user)4012 static isl_stat reset_range_space(__isl_take isl_map *map, void *user)
4013 {
4014 	struct isl_union_map_reset_range_space_data *data = user;
4015 	isl_space *space;
4016 
4017 	space = isl_map_get_space(map);
4018 	space = isl_space_domain(space);
4019 	space = isl_space_extend_domain_with_range(space,
4020 						isl_space_copy(data->range));
4021 	map = isl_map_reset_space(map, space);
4022 	data->res = isl_union_map_add_map(data->res, map);
4023 
4024 	return data->res ? isl_stat_ok : isl_stat_error;
4025 }
4026 
4027 /* Replace the range space of all the maps in "umap" by
4028  * the range space of "space".
4029  *
4030  * This assumes that all maps have the same output dimension.
4031  * This function should therefore not be made publicly available.
4032  *
4033  * Since the spaces of the maps change, so do their hash value.
4034  * We therefore need to create a new isl_union_map.
4035  */
isl_union_map_reset_range_space(__isl_take isl_union_map * umap,__isl_take isl_space * space)4036 __isl_give isl_union_map *isl_union_map_reset_range_space(
4037 	__isl_take isl_union_map *umap, __isl_take isl_space *space)
4038 {
4039 	struct isl_union_map_reset_range_space_data data = { space };
4040 
4041 	data.res = isl_union_map_empty(isl_union_map_get_space(umap));
4042 	if (isl_union_map_foreach_map(umap, &reset_range_space, &data) < 0)
4043 		data.res = isl_union_map_free(data.res);
4044 
4045 	isl_space_free(space);
4046 	isl_union_map_free(umap);
4047 	return data.res;
4048 }
4049 
4050 /* Check that "umap" and "space" have the same number of parameters.
4051  */
check_union_map_space_equal_dim(__isl_keep isl_union_map * umap,__isl_keep isl_space * space)4052 static isl_stat check_union_map_space_equal_dim(__isl_keep isl_union_map *umap,
4053 	__isl_keep isl_space *space)
4054 {
4055 	isl_size dim1, dim2;
4056 
4057 	dim1 = isl_union_map_dim(umap, isl_dim_param);
4058 	dim2 = isl_space_dim(space, isl_dim_param);
4059 	if (dim1 < 0 || dim2 < 0)
4060 		return isl_stat_error;
4061 	if (dim1 == dim2)
4062 		return isl_stat_ok;
4063 	isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
4064 		"number of parameters does not match", return isl_stat_error);
4065 }
4066 
4067 /* Internal data structure for isl_union_map_reset_equal_dim_space.
4068  * "space" is the target space.
4069  * "res" collects the results.
4070  */
4071 struct isl_union_map_reset_params_data {
4072 	isl_space *space;
4073 	isl_union_map *res;
4074 };
4075 
4076 /* Replace the parameters of "map" by those of data->space and
4077  * add the result to data->res.
4078  */
reset_params(__isl_take isl_map * map,void * user)4079 static isl_stat reset_params(__isl_take isl_map *map, void *user)
4080 {
4081 	struct isl_union_map_reset_params_data *data = user;
4082 	isl_space *space;
4083 
4084 	space = isl_map_get_space(map);
4085 	space = isl_space_replace_params(space, data->space);
4086 	map = isl_map_reset_equal_dim_space(map, space);
4087 	data->res = isl_union_map_add_map(data->res, map);
4088 
4089 	return data->res ? isl_stat_ok : isl_stat_error;
4090 }
4091 
4092 /* Replace the space of "umap" by "space", without modifying
4093  * the dimension of "umap", i.e., the number of parameters of "umap".
4094  *
4095  * Since the hash values of the maps in the union map depend
4096  * on the parameters, a new union map needs to be constructed.
4097  */
isl_union_map_reset_equal_dim_space(__isl_take isl_union_map * umap,__isl_take isl_space * space)4098 __isl_give isl_union_map *isl_union_map_reset_equal_dim_space(
4099 	__isl_take isl_union_map *umap, __isl_take isl_space *space)
4100 {
4101 	struct isl_union_map_reset_params_data data = { space };
4102 	isl_bool equal;
4103 	isl_space *umap_space;
4104 
4105 	umap_space = isl_union_map_peek_space(umap);
4106 	equal = isl_space_is_equal(umap_space, space);
4107 	if (equal < 0)
4108 		goto error;
4109 	if (equal) {
4110 		isl_space_free(space);
4111 		return umap;
4112 	}
4113 	if (check_union_map_space_equal_dim(umap, space) < 0)
4114 		goto error;
4115 
4116 	data.res = isl_union_map_empty(isl_space_copy(space));
4117 	if (isl_union_map_foreach_map(umap, &reset_params, &data) < 0)
4118 		data.res = isl_union_map_free(data.res);
4119 
4120 	isl_space_free(space);
4121 	isl_union_map_free(umap);
4122 	return data.res;
4123 error:
4124 	isl_union_map_free(umap);
4125 	isl_space_free(space);
4126 	return NULL;
4127 }
4128 
4129 /* Internal data structure for isl_union_map_order_at_multi_union_pw_aff.
4130  * "mupa" is the function from which the isl_multi_pw_affs are extracted.
4131  * "order" is applied to the extracted isl_multi_pw_affs that correspond
4132  * to the domain and the range of each map.
4133  * "res" collects the results.
4134  */
4135 struct isl_union_order_at_data {
4136 	isl_multi_union_pw_aff *mupa;
4137 	__isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,
4138 		__isl_take isl_multi_pw_aff *mpa2);
4139 	isl_union_map *res;
4140 };
4141 
4142 /* Intersect "map" with the result of applying data->order to
4143  * the functions in data->mupa that apply to the domain and the range
4144  * of "map" and add the result to data->res.
4145  */
order_at(__isl_take isl_map * map,void * user)4146 static isl_stat order_at(__isl_take isl_map *map, void *user)
4147 {
4148 	struct isl_union_order_at_data *data = user;
4149 	isl_space *space;
4150 	isl_multi_pw_aff *mpa1, *mpa2;
4151 	isl_map *order;
4152 
4153 	space = isl_space_domain(isl_map_get_space(map));
4154 	mpa1 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);
4155 	space = isl_space_range(isl_map_get_space(map));
4156 	mpa2 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);
4157 	order = data->order(mpa1, mpa2);
4158 	map = isl_map_intersect(map, order);
4159 	data->res = isl_union_map_add_map(data->res, map);
4160 
4161 	return data->res ? isl_stat_ok : isl_stat_error;
4162 }
4163 
4164 /* If "mupa" has a non-trivial explicit domain, then intersect
4165  * domain and range of "umap" with this explicit domain.
4166  * If the explicit domain only describes constraints on the parameters,
4167  * then the intersection only needs to be performed once.
4168  */
intersect_explicit_domain(__isl_take isl_union_map * umap,__isl_keep isl_multi_union_pw_aff * mupa)4169 static __isl_give isl_union_map *intersect_explicit_domain(
4170 	__isl_take isl_union_map *umap, __isl_keep isl_multi_union_pw_aff *mupa)
4171 {
4172 	isl_bool non_trivial, is_params;
4173 	isl_union_set *dom;
4174 
4175 	non_trivial = isl_multi_union_pw_aff_has_non_trivial_domain(mupa);
4176 	if (non_trivial < 0)
4177 		return isl_union_map_free(umap);
4178 	if (!non_trivial)
4179 		return umap;
4180 	mupa = isl_multi_union_pw_aff_copy(mupa);
4181 	dom = isl_multi_union_pw_aff_domain(mupa);
4182 	is_params = isl_union_set_is_params(dom);
4183 	if (is_params < 0) {
4184 		isl_union_set_free(dom);
4185 		return isl_union_map_free(umap);
4186 	}
4187 	if (is_params) {
4188 		isl_set *set;
4189 
4190 		set = isl_union_set_params(dom);
4191 		umap = isl_union_map_intersect_params(umap, set);
4192 		return umap;
4193 	}
4194 	umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(dom));
4195 	umap = isl_union_map_intersect_range(umap, dom);
4196 	return umap;
4197 }
4198 
4199 /* Intersect each map in "umap" with the result of calling "order"
4200  * on the functions is "mupa" that apply to the domain and the range
4201  * of the map.
4202  */
isl_union_map_order_at_multi_union_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_union_pw_aff * mupa,__isl_give isl_map * (* order)(__isl_take isl_multi_pw_aff * mpa1,__isl_take isl_multi_pw_aff * mpa2))4203 static __isl_give isl_union_map *isl_union_map_order_at_multi_union_pw_aff(
4204 	__isl_take isl_union_map *umap, __isl_take isl_multi_union_pw_aff *mupa,
4205 	__isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,
4206 		__isl_take isl_multi_pw_aff *mpa2))
4207 {
4208 	struct isl_union_order_at_data data;
4209 
4210 	umap = isl_union_map_align_params(umap,
4211 				isl_multi_union_pw_aff_get_space(mupa));
4212 	mupa = isl_multi_union_pw_aff_align_params(mupa,
4213 				isl_union_map_get_space(umap));
4214 	umap = intersect_explicit_domain(umap, mupa);
4215 	data.mupa = mupa;
4216 	data.order = order;
4217 	data.res = isl_union_map_empty(isl_union_map_get_space(umap));
4218 	if (isl_union_map_foreach_map(umap, &order_at, &data) < 0)
4219 		data.res = isl_union_map_free(data.res);
4220 
4221 	isl_multi_union_pw_aff_free(mupa);
4222 	isl_union_map_free(umap);
4223 	return data.res;
4224 }
4225 
4226 /* Return the subset of "umap" where the domain and the range
4227  * have equal "mupa" values.
4228  */
isl_union_map_eq_at_multi_union_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_union_pw_aff * mupa)4229 __isl_give isl_union_map *isl_union_map_eq_at_multi_union_pw_aff(
4230 	__isl_take isl_union_map *umap,
4231 	__isl_take isl_multi_union_pw_aff *mupa)
4232 {
4233 	return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
4234 						&isl_multi_pw_aff_eq_map);
4235 }
4236 
4237 /* Return the subset of "umap" where the domain has a lexicographically
4238  * smaller "mupa" value than the range.
4239  */
isl_union_map_lex_lt_at_multi_union_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_union_pw_aff * mupa)4240 __isl_give isl_union_map *isl_union_map_lex_lt_at_multi_union_pw_aff(
4241 	__isl_take isl_union_map *umap,
4242 	__isl_take isl_multi_union_pw_aff *mupa)
4243 {
4244 	return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
4245 						&isl_multi_pw_aff_lex_lt_map);
4246 }
4247 
4248 /* Return the subset of "umap" where the domain has a lexicographically
4249  * greater "mupa" value than the range.
4250  */
isl_union_map_lex_gt_at_multi_union_pw_aff(__isl_take isl_union_map * umap,__isl_take isl_multi_union_pw_aff * mupa)4251 __isl_give isl_union_map *isl_union_map_lex_gt_at_multi_union_pw_aff(
4252 	__isl_take isl_union_map *umap,
4253 	__isl_take isl_multi_union_pw_aff *mupa)
4254 {
4255 	return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
4256 						&isl_multi_pw_aff_lex_gt_map);
4257 }
4258 
4259 /* Return the union of the elements in the list "list".
4260  */
isl_union_set_list_union(__isl_take isl_union_set_list * list)4261 __isl_give isl_union_set *isl_union_set_list_union(
4262 	__isl_take isl_union_set_list *list)
4263 {
4264 	int i;
4265 	isl_size n;
4266 	isl_ctx *ctx;
4267 	isl_space *space;
4268 	isl_union_set *res;
4269 
4270 	n = isl_union_set_list_n_union_set(list);
4271 	if (n < 0)
4272 		goto error;
4273 
4274 	ctx = isl_union_set_list_get_ctx(list);
4275 	space = isl_space_params_alloc(ctx, 0);
4276 	res = isl_union_set_empty(space);
4277 
4278 	for (i = 0; i < n; ++i) {
4279 		isl_union_set *uset_i;
4280 
4281 		uset_i = isl_union_set_list_get_union_set(list, i);
4282 		res = isl_union_set_union(res, uset_i);
4283 	}
4284 
4285 	isl_union_set_list_free(list);
4286 	return res;
4287 error:
4288 	isl_union_set_list_free(list);
4289 	return NULL;
4290 }
4291 
4292 /* Update *hash with the hash value of "map".
4293  */
add_hash(__isl_take isl_map * map,void * user)4294 static isl_stat add_hash(__isl_take isl_map *map, void *user)
4295 {
4296 	uint32_t *hash = user;
4297 	uint32_t map_hash;
4298 
4299 	map_hash = isl_map_get_hash(map);
4300 	isl_hash_hash(*hash, map_hash);
4301 
4302 	isl_map_free(map);
4303 	return isl_stat_ok;
4304 }
4305 
4306 /* Return a hash value that digests "umap".
4307  */
isl_union_map_get_hash(__isl_keep isl_union_map * umap)4308 uint32_t isl_union_map_get_hash(__isl_keep isl_union_map *umap)
4309 {
4310 	uint32_t hash;
4311 
4312 	if (!umap)
4313 		return 0;
4314 
4315 	hash = isl_hash_init();
4316 	if (isl_union_map_foreach_map(umap, &add_hash, &hash) < 0)
4317 		return 0;
4318 
4319 	return hash;
4320 }
4321 
4322 /* Return a hash value that digests "uset".
4323  */
isl_union_set_get_hash(__isl_keep isl_union_set * uset)4324 uint32_t isl_union_set_get_hash(__isl_keep isl_union_set *uset)
4325 {
4326 	return isl_union_map_get_hash(uset);
4327 }
4328 
4329 /* Add the number of basic sets in "set" to "n".
4330  */
add_n(__isl_take isl_set * set,void * user)4331 static isl_stat add_n(__isl_take isl_set *set, void *user)
4332 {
4333 	int *n = user;
4334 	isl_size set_n;
4335 
4336 	set_n = isl_set_n_basic_set(set);
4337 	*n += set_n;
4338 	isl_set_free(set);
4339 
4340 	return set_n < 0 ? isl_stat_error : isl_stat_ok;
4341 }
4342 
4343 /* Return the total number of basic sets in "uset".
4344  */
isl_union_set_n_basic_set(__isl_keep isl_union_set * uset)4345 int isl_union_set_n_basic_set(__isl_keep isl_union_set *uset)
4346 {
4347 	int n = 0;
4348 
4349 	if (isl_union_set_foreach_set(uset, &add_n, &n) < 0)
4350 		return -1;
4351 
4352 	return n;
4353 }
4354 
4355 /* Add the basic sets in "set" to "list".
4356  */
add_list(__isl_take isl_set * set,void * user)4357 static isl_stat add_list(__isl_take isl_set *set, void *user)
4358 {
4359 	isl_basic_set_list **list = user;
4360 	isl_basic_set_list *list_i;
4361 
4362 	list_i = isl_set_get_basic_set_list(set);
4363 	*list = isl_basic_set_list_concat(*list, list_i);
4364 	isl_set_free(set);
4365 
4366 	if (!*list)
4367 		return isl_stat_error;
4368 	return isl_stat_ok;
4369 }
4370 
4371 /* Return a list containing all the basic sets in "uset".
4372  *
4373  * First construct a list of the appropriate size and
4374  * then add all the elements.
4375  */
isl_union_set_get_basic_set_list(__isl_keep isl_union_set * uset)4376 __isl_give isl_basic_set_list *isl_union_set_get_basic_set_list(
4377 	__isl_keep isl_union_set *uset)
4378 {
4379 	int n;
4380 	isl_ctx *ctx;
4381 	isl_basic_set_list *list;
4382 
4383 	if (!uset)
4384 		return NULL;
4385 	ctx = isl_union_set_get_ctx(uset);
4386 	n = isl_union_set_n_basic_set(uset);
4387 	if (n < 0)
4388 		return NULL;
4389 	list = isl_basic_set_list_alloc(ctx, n);
4390 	if (isl_union_set_foreach_set(uset, &add_list, &list) < 0)
4391 		list = isl_basic_set_list_free(list);
4392 
4393 	return list;
4394 }
4395 
4396 /* Internal data structure for isl_union_map_remove_map_if.
4397  * "fn" and "user" are the arguments to isl_union_map_remove_map_if.
4398  */
4399 struct isl_union_map_remove_map_if_data {
4400 	isl_bool (*fn)(__isl_keep isl_map *map, void *user);
4401 	void *user;
4402 };
4403 
4404 /* isl_un_op_control filter that negates the result of data->fn
4405  * called on "map".
4406  */
not(__isl_keep isl_map * map,void * user)4407 static isl_bool not(__isl_keep isl_map *map, void *user)
4408 {
4409 	struct isl_union_map_remove_map_if_data *data = user;
4410 
4411 	return isl_bool_not(data->fn(map, data->user));
4412 }
4413 
4414 /* Dummy isl_un_op_control transformation callback that
4415  * simply returns the input.
4416  */
map_id(__isl_take isl_map * map)4417 static __isl_give isl_map *map_id(__isl_take isl_map *map)
4418 {
4419 	return map;
4420 }
4421 
4422 /* Call "fn" on every map in "umap" and remove those maps
4423  * for which the callback returns true.
4424  *
4425  * Use un_op to keep only those maps that are not filtered out,
4426  * applying an identity transformation on them.
4427  */
isl_union_map_remove_map_if(__isl_take isl_union_map * umap,isl_bool (* fn)(__isl_keep isl_map * map,void * user),void * user)4428 __isl_give isl_union_map *isl_union_map_remove_map_if(
4429 	__isl_take isl_union_map *umap,
4430 	isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user)
4431 {
4432 	struct isl_union_map_remove_map_if_data data = { fn, user };
4433 	struct isl_un_op_control control = {
4434 		.filter = &not,
4435 		.filter_user = &data,
4436 		.fn_map = &map_id,
4437 	};
4438 	return un_op(umap, &control);
4439 }
4440 
4441 /* Does "map" have "space" as domain (ignoring parameters)?
4442  */
has_domain_space_tuples(__isl_keep isl_map * map,void * user)4443 static isl_bool has_domain_space_tuples(__isl_keep isl_map *map, void *user)
4444 {
4445 	isl_space *space = user;
4446 
4447 	return isl_space_has_domain_tuples(space, isl_map_peek_space(map));
4448 }
4449 
4450 /* Does "map" have "space" as range (ignoring parameters)?
4451  */
has_range_space_tuples(__isl_keep isl_map * map,void * user)4452 static isl_bool has_range_space_tuples(__isl_keep isl_map *map, void *user)
4453 {
4454 	isl_space *space = user;
4455 
4456 	return isl_space_has_range_tuples(space, isl_map_peek_space(map));
4457 }
4458 
4459 /* Wrapper around isl_map_bind_range for use as a un_op callback.
4460  */
bind_range(__isl_take isl_map * map,void * user)4461 static __isl_give isl_map *bind_range(__isl_take isl_map *map, void *user)
4462 {
4463 	isl_multi_id *tuple = user;
4464 
4465 	return isl_map_bind_range(map, isl_multi_id_copy(tuple));
4466 }
4467 
4468 /* Bind the output dimensions of "umap" to parameters with identifiers
4469  * specified by "tuple", living in the range space of "umap",
4470  * for those maps that have a matching range space.
4471  */
isl_union_map_bind_range(__isl_take isl_union_map * umap,__isl_take isl_multi_id * tuple)4472 __isl_give isl_union_set *isl_union_map_bind_range(
4473 	__isl_take isl_union_map *umap, __isl_take isl_multi_id *tuple)
4474 {
4475 	struct isl_un_op_control control = {
4476 		.filter = &has_range_space_tuples,
4477 		.filter_user = isl_multi_id_peek_space(tuple),
4478 		.fn_map2 = &bind_range,
4479 		.fn_map2_user = tuple,
4480 	};
4481 	isl_union_set *bound;
4482 
4483 	bound = uset_from_umap(un_op(umap, &control));
4484 	isl_multi_id_free(tuple);
4485 	return bound;
4486 }
4487 
4488 /* Only keep those elements in "umap" that have a domain in "space".
4489  */
isl_union_map_intersect_domain_space(__isl_take isl_union_map * umap,__isl_take isl_space * space)4490 __isl_give isl_union_map *isl_union_map_intersect_domain_space(
4491 	__isl_take isl_union_map *umap, __isl_take isl_space *space)
4492 {
4493 	struct isl_un_op_control control = {
4494 		.filter = &has_domain_space_tuples,
4495 		.filter_user = space,
4496 	};
4497 
4498 	umap = un_op(umap, &control);
4499 	isl_space_free(space);
4500 	return umap;
4501 }
4502 
4503 /* Only keep those elements in "umap" that have a range in "space".
4504  */
isl_union_map_intersect_range_space(__isl_take isl_union_map * umap,__isl_take isl_space * space)4505 __isl_give isl_union_map *isl_union_map_intersect_range_space(
4506 	__isl_take isl_union_map *umap, __isl_take isl_space *space)
4507 {
4508 	struct isl_un_op_control control = {
4509 		.filter = &has_range_space_tuples,
4510 		.filter_user = space,
4511 	};
4512 
4513 	umap = un_op(umap, &control);
4514 	isl_space_free(space);
4515 	return umap;
4516 }
4517