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