Bug Summary

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

Annotated Source Code

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