Bug Summary

File:polly/lib/External/isl/isl_union_map.c
Warning:line 380, column 25
Access to field 'ctx' results in a dereference of a null pointer (loaded from field 'dim')

Annotated Source Code

Press '?' to see keyboard shortcuts

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