Coverage Report

Created: 2017-08-18 19:41

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