Bug Summary

File:tools/polly/lib/External/isl/isl_union_map.c
Warning:line 1052, column 9
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

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