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