Coverage Report

Created: 2018-04-23 18:20

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