Coverage Report

Created: 2017-06-28 17:40

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