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

source code of polly/lib/External/isl/isl_union_map.c