Coverage Report

Created: 2017-11-21 16:49

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_union_map.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2010-2011 INRIA Saclay
3
 * Copyright 2013-2014 Ecole Normale Superieure
4
 * Copyright 2014      INRIA Rocquencourt
5
 * Copyright 2016-2017 Sven Verdoolaege
6
 *
7
 * Use of this software is governed by the MIT license
8
 *
9
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11
 * 91893 Orsay, France 
12
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
13
 * B.P. 105 - 78153 Le Chesnay, France
14
 */
15
16
#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
290
{
39
290
  if (!umap)
40
0
    return 0;
41
290
42
290
  if (type != isl_dim_param)
43
290
    
isl_die0
(isl_union_map_get_ctx(umap), isl_error_invalid,
44
290
      "can only reference parameters", return 0);
45
290
46
290
  return isl_space_dim(umap->dim, type);
47
290
}
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
0
{
55
0
  return isl_union_map_dim(uset, type);
56
0
}
57
58
/* Return the id of the specified dimension.
59
 */
60
__isl_give isl_id *isl_union_map_get_dim_id(__isl_keep isl_union_map *umap,
61
  enum isl_dim_type type, unsigned pos)
62
0
{
63
0
  if (!umap)
64
0
    return NULL;
65
0
66
0
  if (type != isl_dim_param)
67
0
    isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
68
0
      "can only reference parameters", return NULL);
69
0
70
0
  return isl_space_get_dim_id(umap->dim, type, pos);
71
0
}
72
73
/* Is this union set a parameter domain?
74
 */
75
isl_bool isl_union_set_is_params(__isl_keep isl_union_set *uset)
76
17.7k
{
77
17.7k
  isl_set *set;
78
17.7k
  isl_bool params;
79
17.7k
80
17.7k
  if (!uset)
81
0
    return isl_bool_error;
82
17.7k
  if (uset->table.n != 1)
83
4.67k
    return isl_bool_false;
84
13.0k
85
13.0k
  set = isl_set_from_union_set(isl_union_set_copy(uset));
86
13.0k
  params = isl_set_is_params(set);
87
13.0k
  isl_set_free(set);
88
13.0k
  return params;
89
13.0k
}
90
91
static __isl_give isl_union_map *isl_union_map_alloc(
92
  __isl_take isl_space *space, int size)
93
107k
{
94
107k
  isl_union_map *umap;
95
107k
96
107k
  space = isl_space_params(space);
97
107k
  if (!space)
98
0
    return NULL;
99
107k
100
107k
  umap = isl_calloc_type(space->ctx, isl_union_map);
101
107k
  if (!umap) {
102
0
    isl_space_free(space);
103
0
    return NULL;
104
0
  }
105
107k
106
107k
  umap->ref = 1;
107
107k
  umap->dim = space;
108
107k
  if (isl_hash_table_init(space->ctx, &umap->table, size) < 0)
109
0
    return isl_union_map_free(umap);
110
107k
111
107k
  return umap;
112
107k
}
113
114
__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
115
45.1k
{
116
45.1k
  return isl_union_map_alloc(dim, 16);
117
45.1k
}
118
119
__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
120
8.22k
{
121
8.22k
  return isl_union_map_empty(dim);
122
8.22k
}
123
124
isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
125
77.8k
{
126
77.8k
  return umap ? umap->dim->ctx : NULL;
127
77.8k
}
128
129
isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
130
4.12k
{
131
4.12k
  return uset ? uset->dim->ctx : NULL;
132
4.12k
}
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
135k
{
138
135k
  return umap ? 
umap->dim135k
: NULL;
139
135k
}
140
141
__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
142
135k
{
143
135k
  return isl_space_copy(isl_union_map_peek_space(umap));
144
135k
}
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
6.39k
{
160
6.39k
  return isl_union_map_get_space(uset);
161
6.39k
}
162
163
static isl_stat free_umap_entry(void **entry, void *user)
164
116k
{
165
116k
  isl_map *map = *entry;
166
116k
  isl_map_free(map);
167
116k
  return isl_stat_ok;
168
116k
}
169
170
static isl_stat add_map(__isl_take isl_map *map, void *user)
171
13.0k
{
172
13.0k
  isl_union_map **umap = (isl_union_map **)user;
173
13.0k
174
13.0k
  *umap = isl_union_map_add_map(*umap, map);
175
13.0k
176
13.0k
  return isl_stat_ok;
177
13.0k
}
178
179
__isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
180
7.68k
{
181
7.68k
  isl_union_map *dup;
182
7.68k
183
7.68k
  if (!umap)
184
0
    return NULL;
185
7.68k
186
7.68k
  dup = isl_union_map_empty(isl_space_copy(umap->dim));
187
7.68k
  if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
188
0
    goto error;
189
7.68k
  return dup;
190
0
error:
191
0
  isl_union_map_free(dup);
192
0
  return NULL;
193
7.68k
}
194
195
__isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
196
132k
{
197
132k
  if (!umap)
198
0
    return NULL;
199
132k
200
132k
  if (umap->ref == 1)
201
124k
    return umap;
202
7.68k
  umap->ref--;
203
7.68k
  return isl_union_map_dup(umap);
204
7.68k
}
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
3.36k
{
213
3.36k
  isl_map *map = *entry;
214
3.36k
  isl_reordering *exp;
215
3.36k
  struct isl_union_align *data = user;
216
3.36k
217
3.36k
  exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
218
3.36k
            isl_map_get_space(map));
219
3.36k
220
3.36k
  data->res = isl_union_map_add_map(data->res,
221
3.36k
          isl_map_realign(isl_map_copy(map), exp));
222
3.36k
223
3.36k
  return isl_stat_ok;
224
3.36k
}
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
89.6k
{
234
89.6k
  struct isl_union_align data = { NULL, NULL };
235
89.6k
  isl_bool equal_params;
236
89.6k
237
89.6k
  if (!umap || 
!model89.6k
)
238
76
    goto error;
239
89.5k
240
89.5k
  equal_params = isl_space_has_equal_params(umap->dim, model);
241
89.5k
  if (equal_params < 0)
242
0
    goto error;
243
89.5k
  if (equal_params) {
244
85.1k
    isl_space_free(model);
245
85.1k
    return umap;
246
85.1k
  }
247
4.45k
248
4.45k
  model = isl_space_params(model);
249
4.45k
  data.exp = isl_parameter_alignment_reordering(umap->dim, model);
250
4.45k
  if (!data.exp)
251
0
    goto error;
252
4.45k
253
4.45k
  data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
254
4.45k
          umap->table.n);
255
4.45k
  if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
256
4.45k
          &align_entry, &data) < 0)
257
0
    goto error;
258
4.45k
259
4.45k
  isl_reordering_free(data.exp);
260
4.45k
  isl_union_map_free(umap);
261
4.45k
  isl_space_free(model);
262
4.45k
  return data.res;
263
76
error:
264
76
  isl_reordering_free(data.exp);
265
76
  isl_union_map_free(umap);
266
76
  isl_union_map_free(data.res);
267
76
  isl_space_free(model);
268
76
  return NULL;
269
89.6k
}
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
226
{
274
226
  return isl_union_map_align_params(uset, model);
275
226
}
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
11.8k
{
280
11.8k
  umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
281
11.8k
  umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
282
11.8k
283
11.8k
  umap1 = isl_union_map_cow(umap1);
284
11.8k
285
11.8k
  if (!umap1 || !umap2)
286
0
    goto error;
287
11.8k
288
11.8k
  if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
289
0
    goto error;
290
11.8k
291
11.8k
  isl_union_map_free(umap2);
292
11.8k
293
11.8k
  return umap1;
294
0
error:
295
0
  isl_union_map_free(umap1);
296
0
  isl_union_map_free(umap2);
297
0
  return NULL;
298
11.8k
}
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
1.06k
{
303
1.06k
  return isl_union_map_union(uset1, uset2);
304
1.06k
}
305
306
__isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
307
148k
{
308
148k
  if (!umap)
309
1.73k
    return NULL;
310
146k
311
146k
  umap->ref++;
312
146k
  return umap;
313
146k
}
314
315
__isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
316
42.0k
{
317
42.0k
  return isl_union_map_copy(uset);
318
42.0k
}
319
320
__isl_null isl_union_map *isl_union_map_free(__isl_take isl_union_map *umap)
321
249k
{
322
249k
  if (!umap)
323
2.92k
    return NULL;
324
246k
325
246k
  if (--umap->ref > 0)
326
139k
    return NULL;
327
107k
328
107k
  isl_hash_table_foreach(umap->dim->ctx, &umap->table,
329
107k
             &free_umap_entry, NULL);
330
107k
  isl_hash_table_clear(&umap->table);
331
107k
  isl_space_free(umap->dim);
332
107k
  free(umap);
333
107k
  return NULL;
334
107k
}
335
336
__isl_null isl_union_set *isl_union_set_free(__isl_take isl_union_set *uset)
337
26.4k
{
338
26.4k
  return isl_union_map_free(uset);
339
26.4k
}
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
63
{
346
63
  isl_space *umap_space;
347
63
348
63
  umap_space = isl_union_map_peek_space(umap);
349
63
  return isl_space_has_equal_params(umap_space, space);
350
63
}
351
352
static int has_space(const void *entry, const void *val)
353
24.1k
{
354
24.1k
  isl_map *map = (isl_map *)entry;
355
24.1k
  isl_space *space = (isl_space *) val;
356
24.1k
357
24.1k
  return isl_space_is_equal(map->dim, space);
358
24.1k
}
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
124k
{
363
124k
  uint32_t hash;
364
124k
  struct isl_hash_table_entry *entry;
365
124k
  isl_bool aligned;
366
124k
367
124k
  if (!map || !umap)
368
0
    goto error;
369
124k
370
124k
  if (isl_map_plain_is_empty(map)) {
371
4.18k
    isl_map_free(map);
372
4.18k
    return umap;
373
4.18k
  }
374
120k
375
120k
  aligned = isl_map_space_has_equal_params(map, umap->dim);
376
120k
  if (aligned < 0)
377
0
    goto error;
378
120k
  if (!aligned) {
379
2.42k
    umap = isl_union_map_align_params(umap, isl_map_get_space(map));
380
2.42k
    map = isl_map_align_params(map, isl_union_map_get_space(umap));
381
2.42k
  }
382
120k
383
120k
  umap = isl_union_map_cow(umap);
384
120k
385
120k
  if (!map || !umap)
386
0
    goto error;
387
120k
388
120k
  hash = isl_space_get_hash(map->dim);
389
120k
  entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
390
120k
            &has_space, map->dim, 1);
391
120k
  if (!entry)
392
0
    goto error;
393
120k
394
120k
  if (!entry->data)
395
116k
    entry->data = map;
396
4.00k
  else {
397
4.00k
    entry->data = isl_map_union(entry->data, isl_map_copy(map));
398
4.00k
    if (!entry->data)
399
0
      goto error;
400
4.00k
    isl_map_free(map);
401
4.00k
  }
402
120k
403
120k
  return umap;
404
0
error:
405
0
  isl_map_free(map);
406
0
  isl_union_map_free(umap);
407
0
  return NULL;
408
124k
}
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
11.7k
{
413
11.7k
  return isl_union_map_add_map(uset, set_to_map(set));
414
11.7k
}
415
416
__isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
417
15.4k
{
418
15.4k
  isl_space *dim;
419
15.4k
  isl_union_map *umap;
420
15.4k
421
15.4k
  if (!map)
422
0
    return NULL;
423
15.4k
424
15.4k
  dim = isl_map_get_space(map);
425
15.4k
  dim = isl_space_params(dim);
426
15.4k
  umap = isl_union_map_empty(dim);
427
15.4k
  umap = isl_union_map_add_map(umap, map);
428
15.4k
429
15.4k
  return umap;
430
15.4k
}
431
432
__isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
433
4.04k
{
434
4.04k
  return isl_union_map_from_map(set_to_map(set));
435
4.04k
}
436
437
__isl_give isl_union_map *isl_union_map_from_basic_map(
438
  __isl_take isl_basic_map *bmap)
439
2.94k
{
440
2.94k
  return isl_union_map_from_map(isl_map_from_basic_map(bmap));
441
2.94k
}
442
443
__isl_give isl_union_set *isl_union_set_from_basic_set(
444
  __isl_take isl_basic_set *bset)
445
2.94k
{
446
2.94k
  return isl_union_map_from_basic_map(bset);
447
2.94k
}
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
30.7k
{
457
30.7k
  isl_map *map = *entry;
458
30.7k
  struct isl_union_map_foreach_data *data;
459
30.7k
  data = (struct isl_union_map_foreach_data *)user;
460
30.7k
461
30.7k
  return data->fn(isl_map_copy(map), data->user);
462
30.7k
}
463
464
int isl_union_map_n_map(__isl_keep isl_union_map *umap)
465
6.50k
{
466
6.50k
  return umap ? umap->table.n : 
00
;
467
6.50k
}
468
469
int isl_union_set_n_set(__isl_keep isl_union_set *uset)
470
90
{
471
90
  return uset ? uset->table.n : 
00
;
472
90
}
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
34.0k
{
477
34.0k
  struct isl_union_map_foreach_data data = { fn, user };
478
34.0k
479
34.0k
  if (!umap)
480
0
    return isl_stat_error;
481
34.0k
482
34.0k
  return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
483
34.0k
              &call_on_copy, &data);
484
34.0k
}
485
486
static isl_stat copy_map(void **entry, void *user)
487
22.3k
{
488
22.3k
  isl_map *map = *entry;
489
22.3k
  isl_map **map_p = user;
490
22.3k
491
22.3k
  *map_p = isl_map_copy(map);
492
22.3k
493
22.3k
  return isl_stat_error;
494
22.3k
}
495
496
__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
497
22.3k
{
498
22.3k
  isl_ctx *ctx;
499
22.3k
  isl_map *map = NULL;
500
22.3k
501
22.3k
  if (!umap)
502
0
    return NULL;
503
22.3k
  ctx = isl_union_map_get_ctx(umap);
504
22.3k
  if (umap->table.n != 1)
505
22.3k
    
isl_die0
(ctx, isl_error_invalid,
506
22.3k
      "union map needs to contain elements in exactly "
507
22.3k
      "one space", goto error);
508
22.3k
509
22.3k
  isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
510
22.3k
511
22.3k
  isl_union_map_free(umap);
512
22.3k
513
22.3k
  return map;
514
0
error:
515
0
  isl_union_map_free(umap);
516
0
  return NULL;
517
22.3k
}
518
519
__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
520
21.4k
{
521
21.4k
  return isl_map_from_union_map(uset);
522
21.4k
}
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
1.96k
{
530
1.96k
  uint32_t hash;
531
1.96k
  struct isl_hash_table_entry *entry;
532
1.96k
533
1.96k
  space = isl_space_drop_dims(space, isl_dim_param,
534
1.96k
          0, isl_space_dim(space, isl_dim_param));
535
1.96k
  space = isl_space_align_params(space, isl_union_map_get_space(umap));
536
1.96k
  if (!umap || !space)
537
0
    goto error;
538
1.96k
539
1.96k
  hash = isl_space_get_hash(space);
540
1.96k
  entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
541
1.96k
            &has_space, space, 0);
542
1.96k
  if (!entry)
543
727
    return isl_map_empty(space);
544
1.24k
  isl_space_free(space);
545
1.24k
  return isl_map_copy(entry->data);
546
0
error:
547
0
  isl_space_free(space);
548
0
  return NULL;
549
1.96k
}
550
551
__isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
552
  __isl_take isl_space *dim)
553
1.66k
{
554
1.66k
  return set_from_map(isl_union_map_extract_map(uset, dim));
555
1.66k
}
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
87
{
562
87
  uint32_t hash;
563
87
  struct isl_hash_table_entry *entry;
564
87
565
87
  if (!umap || !space)
566
0
    return isl_bool_error;
567
87
568
87
  hash = isl_space_get_hash(space);
569
87
  entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
570
87
            &has_space, space, 0);
571
87
  return !!entry;
572
87
}
573
574
isl_bool isl_union_set_contains(__isl_keep isl_union_set *uset,
575
  __isl_keep isl_space *space)
576
87
{
577
87
  return isl_union_map_contains(uset, space);
578
87
}
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
3.30k
{
583
3.30k
  return isl_union_map_foreach_map(uset,
584
3.30k
    (isl_stat(*)(__isl_take isl_map *, void*))fn, user);
585
3.30k
}
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
678
{
651
678
  return isl_union_map_add_map(res, isl_map_copy(map));
652
678
}
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
11.2k
{
661
11.2k
  isl_bool empty;
662
11.2k
  isl_map *map;
663
11.2k
664
11.2k
  map = data->control->fn_map(isl_map_copy(map1), isl_map_copy(map2));
665
11.2k
  empty = isl_map_is_empty(map);
666
11.2k
  if (empty < 0 || empty) {
667
1.43k
    isl_map_free(map);
668
1.43k
    if (empty < 0)
669
0
      return isl_union_map_free(res);
670
1.43k
    return res;
671
1.43k
  }
672
9.83k
  return isl_union_map_add_map(res, map);
673
9.83k
}
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
18.2k
{
695
18.2k
  uint32_t hash;
696
18.2k
  struct isl_hash_table_entry *entry2;
697
18.2k
  isl_space *space;
698
18.2k
  isl_maybe_isl_map res = { isl_bool_error, NULL };
699
18.2k
700
18.2k
  if (data->control->filter) {
701
0
    res.valid = data->control->filter(map);
702
0
    if (res.valid < 0 || !res.valid)
703
0
      return res;
704
0
    res.valid = isl_bool_error;
705
0
  }
706
18.2k
707
18.2k
  space = isl_map_get_space(map);
708
18.2k
  if (data->control->match_space != &identity)
709
17.1k
    space = data->control->match_space(space);
710
18.2k
  if (!space)
711
0
    return res;
712
18.2k
  hash = isl_space_get_hash(space);
713
18.2k
  entry2 = isl_hash_table_find(isl_union_map_get_ctx(data->umap2),
714
18.2k
             &data->umap2->table, hash,
715
18.2k
             &has_space, space, 0);
716
18.2k
  isl_space_free(space);
717
18.2k
  res.valid = entry2 != NULL;
718
18.2k
  if (entry2)
719
11.2k
    res.value = entry2->data;
720
18.2k
721
18.2k
  return res;
722
18.2k
}
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
18.2k
{
735
18.2k
  struct isl_union_map_gen_bin_data *data = user;
736
18.2k
  isl_map *map = *entry;
737
18.2k
  isl_maybe_isl_map m;
738
18.2k
739
18.2k
  m = bin_try_get_match(data, map);
740
18.2k
  if (m.valid < 0)
741
0
    return isl_stat_error;
742
18.2k
  if (!m.valid && 
!data->control->subtract6.94k
)
743
6.27k
    return isl_stat_ok;
744
11.9k
745
11.9k
  if (!m.valid)
746
678
    data->res = bin_add_map(data->res, map);
747
11.2k
  else
748
11.2k
    data->res = bin_add_pair(data->res, map, m.value, data);
749
11.9k
  if (!data->res)
750
0
    return isl_stat_error;
751
11.9k
752
11.9k
  return isl_stat_ok;
753
11.9k
}
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
12.9k
{
762
12.9k
  struct isl_union_map_gen_bin_data data = { control, NULL, NULL };
763
12.9k
764
12.9k
  umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
765
12.9k
  umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
766
12.9k
767
12.9k
  if (!umap1 || 
!umap212.8k
)
768
38
    goto error;
769
12.8k
770
12.8k
  data.umap2 = umap2;
771
12.8k
  data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
772
12.8k
               umap1->table.n);
773
12.8k
  if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
774
12.8k
           &gen_bin_entry, &data) < 0)
775
0
    goto error;
776
12.8k
777
12.8k
  isl_union_map_free(umap1);
778
12.8k
  isl_union_map_free(umap2);
779
12.8k
  return data.res;
780
38
error:
781
38
  isl_union_map_free(umap1);
782
38
  isl_union_map_free(umap2);
783
38
  isl_union_map_free(data.res);
784
38
  return NULL;
785
12.9k
}
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
1.15k
{
790
1.15k
  struct isl_bin_op_control control = {
791
1.15k
    .subtract = 1,
792
1.15k
    .match_space = &identity,
793
1.15k
    .fn_map = &isl_map_subtract,
794
1.15k
  };
795
1.15k
796
1.15k
  return gen_bin_op(umap1, umap2, &control);
797
1.15k
}
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
236
{
802
236
  return isl_union_map_subtract(uset1, uset2);
803
236
}
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
0
{
812
0
  struct isl_union_map_gen_bin_set_data *data = user;
813
0
  isl_map *map = *entry;
814
0
  int empty;
815
0
816
0
  map = isl_map_copy(map);
817
0
  map = isl_map_intersect_params(map, isl_set_copy(data->set));
818
0
819
0
  empty = isl_map_is_empty(map);
820
0
  if (empty < 0) {
821
0
    isl_map_free(map);
822
0
    return isl_stat_error;
823
0
  }
824
0
825
0
  data->res = isl_union_map_add_map(data->res, map);
826
0
827
0
  return isl_stat_ok;
828
0
}
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
367
{
833
367
  struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
834
367
835
367
  umap = isl_union_map_align_params(umap, isl_set_get_space(set));
836
367
  set = isl_set_align_params(set, isl_union_map_get_space(umap));
837
367
838
367
  if (!umap || !set)
839
0
    goto error;
840
367
841
367
  data.set = set;
842
367
  data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
843
367
               umap->table.n);
844
367
  if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
845
367
           fn, &data) < 0)
846
0
    goto error;
847
367
848
367
  isl_union_map_free(umap);
849
367
  isl_set_free(set);
850
367
  return data.res;
851
0
error:
852
0
  isl_union_map_free(umap);
853
0
  isl_set_free(set);
854
0
  isl_union_map_free(data.res);
855
0
  return NULL;
856
367
}
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
204
{
865
204
  int is_universe;
866
204
867
204
  is_universe = isl_set_plain_is_universe(set);
868
204
  if (is_universe < 0)
869
0
    goto error;
870
204
  if (is_universe) {
871
197
    isl_set_free(set);
872
197
    return umap;
873
197
  }
874
7
875
7
  return gen_bin_set_op(umap, set, &intersect_params_entry);
876
0
error:
877
0
  isl_union_map_free(umap);
878
0
  isl_set_free(set);
879
0
  return NULL;
880
204
}
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
12
{
885
12
  return isl_union_map_intersect_params(uset, set);
886
12
}
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
0
{
891
0
  return isl_union_map_intersect_params(umap,
892
0
            isl_set_from_union_set(uset));
893
0
}
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
5.60k
{
909
5.60k
  struct isl_union_map_match_bin_data *data = user;
910
5.60k
  uint32_t hash;
911
5.60k
  struct isl_hash_table_entry *entry2;
912
5.60k
  isl_map *map = *entry;
913
5.60k
  int empty;
914
5.60k
915
5.60k
  hash = isl_space_get_hash(map->dim);
916
5.60k
  entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
917
5.60k
             hash, &has_space, map->dim, 0);
918
5.60k
  if (!entry2)
919
823
    return isl_stat_ok;
920
4.78k
921
4.78k
  map = isl_map_copy(map);
922
4.78k
  map = data->fn(map, isl_map_copy(entry2->data));
923
4.78k
924
4.78k
  empty = isl_map_is_empty(map);
925
4.78k
  if (empty < 0) {
926
0
    isl_map_free(map);
927
0
    return isl_stat_error;
928
0
  }
929
4.78k
  if (empty) {
930
150
    isl_map_free(map);
931
150
    return isl_stat_ok;
932
150
  }
933
4.63k
934
4.63k
  data->res = isl_union_map_add_map(data->res, map);
935
4.63k
936
4.63k
  return isl_stat_ok;
937
4.63k
}
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
4.62k
{
943
4.62k
  struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
944
4.62k
945
4.62k
  umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
946
4.62k
  umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
947
4.62k
948
4.62k
  if (!umap1 || !umap2)
949
0
    goto error;
950
4.62k
951
4.62k
  data.umap2 = umap2;
952
4.62k
  data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
953
4.62k
               umap1->table.n);
954
4.62k
  if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
955
4.62k
           &match_bin_entry, &data) < 0)
956
0
    goto error;
957
4.62k
958
4.62k
  isl_union_map_free(umap1);
959
4.62k
  isl_union_map_free(umap2);
960
4.62k
  return data.res;
961
0
error:
962
0
  isl_union_map_free(umap1);
963
0
  isl_union_map_free(umap2);
964
0
  isl_union_map_free(data.res);
965
0
  return NULL;
966
4.62k
}
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
3.80k
{
971
3.80k
  return match_bin_op(umap1, umap2, &isl_map_intersect);
972
3.80k
}
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
2.77k
{
982
2.77k
  int p1, p2;
983
2.77k
984
2.77k
  p1 = isl_union_set_is_params(uset1);
985
2.77k
  p2 = isl_union_set_is_params(uset2);
986
2.77k
  if (p1 < 0 || p2 < 0)
987
0
    goto error;
988
2.77k
  if (!p1 && p2)
989
0
    return union_map_intersect_params(uset1, uset2);
990
2.77k
  if (p1 && 
!p20
)
991
0
    return union_map_intersect_params(uset2, uset1);
992
2.77k
  return isl_union_map_intersect(uset1, uset2);
993
0
error:
994
0
  isl_union_set_free(uset1);
995
0
  isl_union_set_free(uset2);
996
0
  return NULL;
997
2.77k
}
998
999
static isl_stat gist_params_entry(void **entry, void *user)
1000
684
{
1001
684
  struct isl_union_map_gen_bin_set_data *data = user;
1002
684
  isl_map *map = *entry;
1003
684
  int empty;
1004
684
1005
684
  map = isl_map_copy(map);
1006
684
  map = isl_map_gist_params(map, isl_set_copy(data->set));
1007
684
1008
684
  empty = isl_map_is_empty(map);
1009
684
  if (empty < 0) {
1010
0
    isl_map_free(map);
1011
0
    return isl_stat_error;
1012
0
  }
1013
684
1014
684
  data->res = isl_union_map_add_map(data->res, map);
1015
684
1016
684
  return isl_stat_ok;
1017
684
}
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
360
{
1022
360
  return gen_bin_set_op(umap, set, &gist_params_entry);
1023
360
}
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
360
{
1028
360
  return isl_union_map_gist_params(uset, set);
1029
360
}
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
792
{
1034
792
  return match_bin_op(umap, context, &isl_map_gist);
1035
792
}
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
792
{
1040
792
  if (isl_union_set_is_params(context))
1041
0
    return union_map_gist_params(uset, context);
1042
792
  return isl_union_map_gist(uset, context);
1043
792
}
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
0
{
1053
0
  return match_bin_op(umap, context, &isl_map_plain_gist);
1054
0
}
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
0
{
1064
0
  return isl_union_map_plain_gist(uset, context);
1065
0
}
1066
1067
static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
1068
  __isl_take isl_map *set2)
1069
23
{
1070
23
  return isl_set_lex_le_set(set_from_map(set1), set_from_map(set2));
1071
23
}
1072
1073
static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
1074
  __isl_take isl_map *set2)
1075
0
{
1076
0
  return isl_set_lex_lt_set(set_from_map(set1), set_from_map(set2));
1077
0
}
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
0
{
1082
0
  return match_bin_op(uset1, uset2, &lex_lt_set);
1083
0
}
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
23
{
1088
23
  return match_bin_op(uset1, uset2, &lex_le_set);
1089
23
}
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
0
{
1094
0
  return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
1095
0
}
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
11.2k
{
1120
11.2k
  struct isl_bin_op_control control = {
1121
11.2k
    .match_space = &isl_space_domain,
1122
11.2k
    .fn_map = &isl_map_intersect_domain,
1123
11.2k
  };
1124
11.2k
1125
11.2k
  return gen_bin_op(umap, uset, &control);
1126
11.2k
}
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
11.2k
{
1135
11.2k
  if (isl_union_set_is_params(uset))
1136
0
    return union_map_intersect_params(umap, uset);
1137
11.2k
  else
1138
11.2k
    return union_map_intersect_domain(umap, uset);
1139
11.2k
}
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
116
{
1146
116
  struct isl_bin_op_control control = {
1147
116
    .subtract = 1,
1148
116
    .match_space = &isl_space_domain,
1149
116
    .fn_map = &isl_map_subtract_domain,
1150
116
  };
1151
116
1152
116
  return gen_bin_op(umap, dom, &control);
1153
116
}
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
0
{
1160
0
  struct isl_bin_op_control control = {
1161
0
    .subtract = 1,
1162
0
    .match_space = &isl_space_range,
1163
0
    .fn_map = &isl_map_subtract_range,
1164
0
  };
1165
0
1166
0
  return gen_bin_op(umap, dom, &control);
1167
0
}
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
37
{
1174
37
  struct isl_bin_op_control control = {
1175
37
    .match_space = &isl_space_domain,
1176
37
    .fn_map = &isl_map_gist_domain,
1177
37
  };
1178
37
1179
37
  return gen_bin_op(umap, uset, &control);
1180
37
}
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
37
{
1189
37
  if (isl_union_set_is_params(uset))
1190
0
    return union_map_gist_params(umap, uset);
1191
37
  else
1192
37
    return union_map_gist_domain(umap, uset);
1193
37
}
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
24
{
1200
24
  struct isl_bin_op_control control = {
1201
24
    .match_space = &isl_space_range,
1202
24
    .fn_map = &isl_map_gist_range,
1203
24
  };
1204
24
1205
24
  return gen_bin_op(umap, uset, &control);
1206
24
}
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
309
{
1211
309
  struct isl_bin_op_control control = {
1212
309
    .match_space = &isl_space_range,
1213
309
    .fn_map = &isl_map_intersect_range,
1214
309
  };
1215
309
1216
309
  return gen_bin_op(umap, uset, &control);
1217
309
}
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
12.7k
{
1244
12.7k
  struct isl_union_map_bin_data *data = user;
1245
12.7k
  isl_map *map2 = *entry;
1246
12.7k
  isl_bool empty;
1247
12.7k
1248
12.7k
  if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1249
12.7k
         map2->dim, isl_dim_in))
1250
7.45k
    return isl_stat_ok;
1251
5.28k
1252
5.28k
  map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1253
5.28k
1254
5.28k
  empty = isl_map_is_empty(map2);
1255
5.28k
  if (empty < 0) {
1256
0
    isl_map_free(map2);
1257
0
    return isl_stat_error;
1258
0
  }
1259
5.28k
  if (empty) {
1260
489
    isl_map_free(map2);
1261
489
    return isl_stat_ok;
1262
489
  }
1263
4.79k
1264
4.79k
  data->res = isl_union_map_add_map(data->res, map2);
1265
4.79k
1266
4.79k
  return isl_stat_ok;
1267
4.79k
}
1268
1269
static isl_stat bin_entry(void **entry, void *user)
1270
17.8k
{
1271
17.8k
  struct isl_union_map_bin_data *data = user;
1272
17.8k
  isl_map *map = *entry;
1273
17.8k
1274
17.8k
  data->map = map;
1275
17.8k
  if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1276
17.8k
           data->fn, data) < 0)
1277
0
    return isl_stat_error;
1278
17.8k
1279
17.8k
  return isl_stat_ok;
1280
17.8k
}
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
9.60k
{
1286
9.60k
  struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1287
9.60k
1288
9.60k
  umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1289
9.60k
  umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1290
9.60k
1291
9.60k
  if (!umap1 || !umap2)
1292
0
    goto error;
1293
9.60k
1294
9.60k
  data.umap2 = umap2;
1295
9.60k
  data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1296
9.60k
               umap1->table.n);
1297
9.60k
  if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1298
9.60k
           &bin_entry, &data) < 0)
1299
0
    goto error;
1300
9.60k
1301
9.60k
  isl_union_map_free(umap1);
1302
9.60k
  isl_union_map_free(umap2);
1303
9.60k
  return data.res;
1304
0
error:
1305
0
  isl_union_map_free(umap1);
1306
0
  isl_union_map_free(umap2);
1307
0
  isl_union_map_free(data.res);
1308
0
  return NULL;
1309
9.60k
}
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
5.76k
{
1314
5.76k
  return bin_op(umap1, umap2, &apply_range_entry);
1315
5.76k
}
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.05k
{
1320
1.05k
  umap1 = isl_union_map_reverse(umap1);
1321
1.05k
  umap1 = isl_union_map_apply_range(umap1, umap2);
1322
1.05k
  return isl_union_map_reverse(umap1);
1323
1.05k
}
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
2
{
1328
2
  return isl_union_map_apply_range(uset, umap);
1329
2
}
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
90
{
1377
90
  struct isl_union_map_bin_data *data = user;
1378
90
  isl_map *map2 = *entry;
1379
90
1380
90
  map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1381
90
1382
90
  data->res = isl_union_map_add_map(data->res, map2);
1383
90
1384
90
  return isl_stat_ok;
1385
90
}
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
18
{
1390
18
  return bin_op(umap1, umap2, &product_entry);
1391
18
}
1392
1393
static isl_stat set_product_entry(void **entry, void *user)
1394
0
{
1395
0
  struct isl_union_map_bin_data *data = user;
1396
0
  isl_set *set2 = *entry;
1397
0
1398
0
  set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1399
0
1400
0
  data->res = isl_union_set_add_set(data->res, set2);
1401
0
1402
0
  return isl_stat_ok;
1403
0
}
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
0
{
1408
0
  return bin_op(uset1, uset2, &set_product_entry);
1409
0
}
1410
1411
static isl_stat domain_product_entry(void **entry, void *user)
1412
319
{
1413
319
  struct isl_union_map_bin_data *data = user;
1414
319
  isl_map *map2 = *entry;
1415
319
1416
319
  if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1417
319
         map2->dim, isl_dim_out))
1418
100
    return isl_stat_ok;
1419
219
1420
219
  map2 = isl_map_domain_product(isl_map_copy(data->map),
1421
219
             isl_map_copy(map2));
1422
219
1423
219
  data->res = isl_union_map_add_map(data->res, map2);
1424
219
1425
219
  return isl_stat_ok;
1426
219
}
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
184
{
1433
184
  return bin_op(umap1, umap2, &domain_product_entry);
1434
184
}
1435
1436
static isl_stat range_product_entry(void **entry, void *user)
1437
271
{
1438
271
  struct isl_union_map_bin_data *data = user;
1439
271
  isl_map *map2 = *entry;
1440
271
1441
271
  if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in,
1442
271
         map2->dim, isl_dim_in))
1443
180
    return isl_stat_ok;
1444
91
1445
91
  map2 = isl_map_range_product(isl_map_copy(data->map),
1446
91
             isl_map_copy(map2));
1447
91
1448
91
  data->res = isl_union_map_add_map(data->res, map2);
1449
91
1450
91
  return isl_stat_ok;
1451
91
}
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
63
{
1456
63
  return bin_op(umap1, umap2, &range_product_entry);
1457
63
}
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
23.3k
{
1489
23.3k
  struct isl_union_map_bin_data *data = user;
1490
23.3k
  isl_map *map2 = *entry;
1491
23.3k
1492
23.3k
  if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in,
1493
23.3k
         map2->dim, isl_dim_in))
1494
18.1k
    return isl_stat_ok;
1495
5.26k
1496
5.26k
  map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1497
5.26k
            isl_map_copy(map2));
1498
5.26k
1499
5.26k
  data->res = isl_union_map_add_map(data->res, map2);
1500
5.26k
1501
5.26k
  return isl_stat_ok;
1502
5.26k
}
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
3.57k
{
1507
3.57k
  return bin_op(umap1, umap2, &flat_range_product_entry);
1508
3.57k
}
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
39.3k
{
1552
39.3k
  struct isl_union_map_un_data *data = user;
1553
39.3k
  isl_map *map = *entry;
1554
39.3k
1555
39.3k
  if (data->control->filter) {
1556
1.86k
    isl_bool ok;
1557
1.86k
1558
1.86k
    ok = data->control->filter(map);
1559
1.86k
    if (ok < 0)
1560
0
      return isl_stat_error;
1561
1.86k
    if (!ok)
1562
14
      return isl_stat_ok;
1563
39.3k
  }
1564
39.3k
1565
39.3k
  map = data->control->fn_map(isl_map_copy(map));
1566
39.3k
  if (!map)
1567
0
    return isl_stat_error;
1568
39.3k
  if (data->control->inplace) {
1569
4.47k
    isl_map_free(*entry);
1570
4.47k
    *entry = map;
1571
34.8k
  } else {
1572
34.8k
    data->res = isl_union_map_add_map(data->res, map);
1573
34.8k
    if (!data->res)
1574
0
      return isl_stat_error;
1575
39.3k
  }
1576
39.3k
1577
39.3k
  return isl_stat_ok;
1578
39.3k
}
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
31.9k
{
1590
31.9k
  struct isl_union_map_un_data data = { control };
1591
31.9k
1592
31.9k
  if (!umap)
1593
88
    return NULL;
1594
31.8k
  if ((control->inplace || 
control->total28.1k
) &&
control->filter3.87k
)
1595
31.8k
    
isl_die0
(isl_union_map_get_ctx(umap), isl_error_invalid,
1596
31.8k
      "inplace/total modification cannot be filtered",
1597
31.8k
      return isl_union_map_free(umap));
1598
31.8k
1599
31.8k
  if (control->total && 
umap->ref == 1226
)
1600
0
    control->inplace = 1;
1601
31.8k
  if (control->inplace) {
1602
3.64k
    data.res = umap;
1603
28.1k
  } else {
1604
28.1k
    isl_space *space;
1605
28.1k
1606
28.1k
    space = isl_union_map_get_space(umap);
1607
28.1k
    data.res = isl_union_map_alloc(space, umap->table.n);
1608
28.1k
  }
1609
31.8k
  if (isl_hash_table_foreach(isl_union_map_get_ctx(umap),
1610
31.8k
            &umap->table, &un_entry, &data) < 0)
1611
0
    data.res = isl_union_map_free(data.res);
1612
31.8k
1613
31.8k
  if (control->inplace)
1614
3.64k
    return data.res;
1615
28.1k
  isl_union_map_free(umap);
1616
28.1k
  return data.res;
1617
28.1k
}
1618
1619
__isl_give isl_union_map *isl_union_map_from_range(
1620
  __isl_take isl_union_set *uset)
1621
1.56k
{
1622
1.56k
  struct isl_un_op_control control = {
1623
1.56k
    .fn_map = &isl_map_from_range,
1624
1.56k
  };
1625
1.56k
  return un_op(uset, &control);
1626
1.56k
}
1627
1628
__isl_give isl_union_map *isl_union_map_from_domain(
1629
  __isl_take isl_union_set *uset)
1630
1.41k
{
1631
1.41k
  return isl_union_map_reverse(isl_union_map_from_range(uset));
1632
1.41k
}
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
142
{
1637
142
  return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1638
142
                 isl_union_map_from_range(range));
1639
142
}
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
226
{
1647
226
  struct isl_un_op_control control = {
1648
226
    .total = 1,
1649
226
    .fn_map = fn,
1650
226
  };
1651
226
1652
226
  return un_op(umap, &control);
1653
226
}
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
3
{
1659
3
  return isl_map_from_basic_map(isl_map_affine_hull(map));
1660
3
}
1661
1662
__isl_give isl_union_map *isl_union_map_affine_hull(
1663
  __isl_take isl_union_map *umap)
1664
2
{
1665
2
  return total(umap, &isl_map_affine_hull_map);
1666
2
}
1667
1668
__isl_give isl_union_set *isl_union_set_affine_hull(
1669
  __isl_take isl_union_set *uset)
1670
2
{
1671
2
  return isl_union_map_affine_hull(uset);
1672
2
}
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
0
{
1680
0
  return isl_set_from_basic_set(isl_set_combined_lineality_space(set));
1681
0
}
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
0
{
1690
0
  struct isl_un_op_control control = {
1691
0
    .fn_map = &combined_lineality_space,
1692
0
  };
1693
0
  return un_op(uset, &control);
1694
0
}
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
3.66k
{
1739
3.66k
  struct isl_un_op_control control = {
1740
3.66k
    .inplace = 1,
1741
3.66k
    .fn_map = fn,
1742
3.66k
  };
1743
3.66k
1744
3.66k
  return un_op(umap, &control);
1745
3.66k
}
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
0
{
1754
0
  return inplace(umap, &isl_map_remove_redundancies);
1755
0
}
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
2.70k
{
1768
2.70k
  return inplace(umap, &isl_map_coalesce);
1769
2.70k
}
1770
1771
__isl_give isl_union_set *isl_union_set_coalesce(
1772
  __isl_take isl_union_set *uset)
1773
312
{
1774
312
  return isl_union_map_coalesce(uset);
1775
312
}
1776
1777
__isl_give isl_union_map *isl_union_map_detect_equalities(
1778
  __isl_take isl_union_map *umap)
1779
713
{
1780
713
  return inplace(umap, &isl_map_detect_equalities);
1781
713
}
1782
1783
__isl_give isl_union_set *isl_union_set_detect_equalities(
1784
  __isl_take isl_union_set *uset)
1785
172
{
1786
172
  return isl_union_map_detect_equalities(uset);
1787
172
}
1788
1789
__isl_give isl_union_map *isl_union_map_compute_divs(
1790
  __isl_take isl_union_map *umap)
1791
245
{
1792
245
  return inplace(umap, &isl_map_compute_divs);
1793
245
}
1794
1795
__isl_give isl_union_set *isl_union_set_compute_divs(
1796
  __isl_take isl_union_set *uset)
1797
34
{
1798
34
  return isl_union_map_compute_divs(uset);
1799
34
}
1800
1801
__isl_give isl_union_map *isl_union_map_lexmin(
1802
  __isl_take isl_union_map *umap)
1803
114
{
1804
114
  return total(umap, &isl_map_lexmin);
1805
114
}
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
110
{
1816
110
  return total(umap, &isl_map_lexmax);
1817
110
}
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
5.01k
{
1829
5.01k
  isl_space *space;
1830
5.01k
1831
5.01k
  space = isl_map_get_space(map);
1832
5.01k
  isl_map_free(map);
1833
5.01k
  return isl_map_universe(space);
1834
5.01k
}
1835
1836
__isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1837
3.78k
{
1838
3.78k
  struct isl_un_op_control control = {
1839
3.78k
    .fn_map = &universe,
1840
3.78k
  };
1841
3.78k
  return un_op(umap, &control);
1842
3.78k
}
1843
1844
__isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1845
3.03k
{
1846
3.03k
  return isl_union_map_universe(uset);
1847
3.03k
}
1848
1849
__isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1850
5.99k
{
1851
5.99k
  struct isl_un_op_control control = {
1852
5.99k
    .fn_map = &isl_map_reverse,
1853
5.99k
  };
1854
5.99k
  return un_op(umap, &control);
1855
5.99k
}
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
2.83k
{
1861
2.83k
  struct isl_un_op_control control = {
1862
2.83k
    .fn_map = &isl_map_params,
1863
2.83k
  };
1864
2.83k
  int empty;
1865
2.83k
1866
2.83k
  empty = isl_union_map_is_empty(umap);
1867
2.83k
  if (empty < 0)
1868
0
    goto error;
1869
2.83k
  if (empty) {
1870
103
    isl_space *space;
1871
103
    space = isl_union_map_get_space(umap);
1872
103
    isl_union_map_free(umap);
1873
103
    return isl_set_empty(space);
1874
103
  }
1875
2.72k
  return isl_set_from_union_set(un_op(umap, &control));
1876
0
error:
1877
0
  isl_union_map_free(umap);
1878
0
  return NULL;
1879
2.83k
}
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
2.73k
{
1885
2.73k
  return isl_union_map_params(uset);
1886
2.73k
}
1887
1888
__isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1889
9.04k
{
1890
9.04k
  struct isl_un_op_control control = {
1891
9.04k
    .fn_map = &isl_map_domain,
1892
9.04k
  };
1893
9.04k
  return un_op(umap, &control);
1894
9.04k
}
1895
1896
__isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1897
727
{
1898
727
  struct isl_un_op_control control = {
1899
727
    .fn_map = &isl_map_range,
1900
727
  };
1901
727
  return un_op(umap, &control);
1902
727
}
1903
1904
__isl_give isl_union_map *isl_union_map_domain_map(
1905
  __isl_take isl_union_map *umap)
1906
205
{
1907
205
  struct isl_un_op_control control = {
1908
205
    .fn_map = &isl_map_domain_map,
1909
205
  };
1910
205
  return un_op(umap, &control);
1911
205
}
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
97
{
1918
97
  isl_union_pw_multi_aff **res = user;
1919
97
  isl_multi_aff *ma;
1920
97
  isl_pw_multi_aff *pma;
1921
97
1922
97
  ma = isl_multi_aff_domain_map(isl_map_get_space(map));
1923
97
  pma = isl_pw_multi_aff_alloc(isl_map_wrap(map), ma);
1924
97
  *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
1925
97
1926
97
  return *res ? isl_stat_ok : 
isl_stat_error0
;
1927
97
1928
97
}
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
42
{
1936
42
  isl_union_pw_multi_aff *res;
1937
42
1938
42
  res = isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap));
1939
42
  if (isl_union_map_foreach_map(umap, &domain_map_upma, &res) < 0)
1940
0
    res = isl_union_pw_multi_aff_free(res);
1941
42
1942
42
  isl_union_map_free(umap);
1943
42
  return res;
1944
42
}
1945
1946
__isl_give isl_union_map *isl_union_map_range_map(
1947
  __isl_take isl_union_map *umap)
1948
1.46k
{
1949
1.46k
  struct isl_un_op_control control = {
1950
1.46k
    .fn_map = &isl_map_range_map,
1951
1.46k
  };
1952
1.46k
  return un_op(umap, &control);
1953
1.46k
}
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
46
{
1972
46
  return isl_space_tuple_is_equal(map->dim, isl_dim_in,
1973
46
          map->dim, isl_dim_out);
1974
46
}
1975
1976
__isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1977
59
{
1978
59
  struct isl_un_op_control control = {
1979
59
    .filter = &equal_tuples,
1980
59
    .fn_map = &isl_map_deltas,
1981
59
  };
1982
59
  return un_op(umap, &control);
1983
59
}
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
33
{
1997
33
  struct isl_un_op_control control = {
1998
33
    .fn_map = &isl_set_identity,
1999
33
  };
2000
33
  return un_op(uset, &control);
2001
33
}
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
9
{
2007
9
  isl_union_pw_multi_aff **res = user;
2008
9
  isl_space *space;
2009
9
  isl_pw_multi_aff *pma;
2010
9
2011
9
  space = isl_space_map_from_set(isl_set_get_space(set));
2012
9
  pma = isl_pw_multi_aff_identity(space);
2013
9
  pma = isl_pw_multi_aff_intersect_domain(pma, set);
2014
9
  *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
2015
9
2016
9
  return *res ? isl_stat_ok : 
isl_stat_error0
;
2017
9
}
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
9
{
2025
9
  isl_union_pw_multi_aff *res;
2026
9
2027
9
  res = isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset));
2028
9
  if (isl_union_set_foreach_set(uset, &identity_upma, &res) < 0)
2029
0
    res = isl_union_pw_multi_aff_free(res);
2030
9
2031
9
  isl_union_set_free(uset);
2032
9
  return res;
2033
9
}
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
262
{
2041
262
  struct isl_un_op_control control = {
2042
262
    .filter = &isl_map_domain_is_wrapping,
2043
262
    .fn_map = &isl_map_domain_factor_domain,
2044
262
  };
2045
262
  return un_op(umap, &control);
2046
262
}
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
16
{
2054
16
  struct isl_un_op_control control = {
2055
16
    .filter = &isl_map_domain_is_wrapping,
2056
16
    .fn_map = &isl_map_domain_factor_range,
2057
16
  };
2058
16
  return un_op(umap, &control);
2059
16
}
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
768
{
2067
768
  struct isl_un_op_control control = {
2068
768
    .filter = &isl_map_range_is_wrapping,
2069
768
    .fn_map = &isl_map_range_factor_domain,
2070
768
  };
2071
768
  return un_op(umap, &control);
2072
768
}
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
188
{
2080
188
  struct isl_un_op_control control = {
2081
188
    .filter = &isl_map_range_is_wrapping,
2082
188
    .fn_map = &isl_map_range_factor_range,
2083
188
  };
2084
188
  return un_op(umap, &control);
2085
188
}
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
0
{
2106
0
  struct isl_un_op_control control = {
2107
0
    .filter = &isl_map_is_product,
2108
0
    .fn_map = &isl_map_factor_range,
2109
0
  };
2110
0
  return un_op(umap, &control);
2111
0
}
2112
2113
__isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
2114
306
{
2115
306
  struct isl_un_op_control control = {
2116
306
    .filter = &isl_set_is_wrapping,
2117
306
    .fn_map = &isl_set_unwrap,
2118
306
  };
2119
306
  return un_op(uset, &control);
2120
306
}
2121
2122
__isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
2123
262
{
2124
262
  struct isl_un_op_control control = {
2125
262
    .fn_map = &isl_map_wrap,
2126
262
  };
2127
262
  return un_op(umap, &control);
2128
262
}
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
3.25k
{
2137
3.25k
  struct isl_union_map_is_subset_data *data = user;
2138
3.25k
  uint32_t hash;
2139
3.25k
  struct isl_hash_table_entry *entry2;
2140
3.25k
  isl_map *map = *entry;
2141
3.25k
2142
3.25k
  hash = isl_space_get_hash(map->dim);
2143
3.25k
  entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2144
3.25k
             hash, &has_space, map->dim, 0);
2145
3.25k
  if (!entry2) {
2146
449
    int empty = isl_map_is_empty(map);
2147
449
    if (empty < 0)
2148
0
      return isl_stat_error;
2149
449
    if (empty)
2150
0
      return isl_stat_ok;
2151
449
    data->is_subset = 0;
2152
449
    return isl_stat_error;
2153
449
  }
2154
2.80k
2155
2.80k
  data->is_subset = isl_map_is_subset(map, entry2->data);
2156
2.80k
  if (data->is_subset < 0 || !data->is_subset)
2157
143
    return isl_stat_error;
2158
2.66k
2159
2.66k
  return isl_stat_ok;
2160
2.66k
}
2161
2162
isl_bool isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
2163
  __isl_keep isl_union_map *umap2)
2164
2.50k
{
2165
2.50k
  struct isl_union_map_is_subset_data data = { NULL, isl_bool_true };
2166
2.50k
2167
2.50k
  umap1 = isl_union_map_copy(umap1);
2168
2.50k
  umap2 = isl_union_map_copy(umap2);
2169
2.50k
  umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
2170
2.50k
  umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
2171
2.50k
2172
2.50k
  if (!umap1 || !umap2)
2173
0
    goto error;
2174
2.50k
2175
2.50k
  data.umap2 = umap2;
2176
2.50k
  if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2177
2.50k
           &is_subset_entry, &data) < 0 &&
2178
2.50k
      
data.is_subset592
)
2179
0
    goto error;
2180
2.50k
2181
2.50k
  isl_union_map_free(umap1);
2182
2.50k
  isl_union_map_free(umap2);
2183
2.50k
2184
2.50k
  return data.is_subset;
2185
0
error:
2186
0
  isl_union_map_free(umap1);
2187
0
  isl_union_map_free(umap2);
2188
0
  return isl_bool_error;
2189
2.50k
}
2190
2191
isl_bool isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
2192
  __isl_keep isl_union_set *uset2)
2193
2.01k
{
2194
2.01k
  return isl_union_map_is_subset(uset1, uset2);
2195
2.01k
}
2196
2197
isl_bool isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
2198
  __isl_keep isl_union_map *umap2)
2199
96
{
2200
96
  isl_bool is_subset;
2201
96
2202
96
  if (!umap1 || !umap2)
2203
0
    return isl_bool_error;
2204
96
  is_subset = isl_union_map_is_subset(umap1, umap2);
2205
96
  if (is_subset != isl_bool_true)
2206
7
    return is_subset;
2207
89
  is_subset = isl_union_map_is_subset(umap2, umap1);
2208
89
  return is_subset;
2209
89
}
2210
2211
isl_bool isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
2212
  __isl_keep isl_union_set *uset2)
2213
33
{
2214
33
  return isl_union_map_is_equal(uset1, uset2);
2215
33
}
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 || !umap2)
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
628
{
2254
628
  struct isl_union_map_is_disjoint_data *data = user;
2255
628
  uint32_t hash;
2256
628
  struct isl_hash_table_entry *entry2;
2257
628
  isl_map *map = *entry;
2258
628
2259
628
  hash = isl_space_get_hash(map->dim);
2260
628
  entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2261
628
             hash, &has_space, map->dim, 0);
2262
628
  if (!entry2)
2263
626
    return isl_stat_ok;
2264
2
2265
2
  data->is_disjoint = isl_map_is_disjoint(map, entry2->data);
2266
2
  if (data->is_disjoint < 0 || !data->is_disjoint)
2267
2
    return isl_stat_error;
2268
0
2269
0
  return isl_stat_ok;
2270
0
}
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
416
{
2277
416
  struct isl_union_map_is_disjoint_data data = { NULL, isl_bool_true };
2278
416
2279
416
  umap1 = isl_union_map_copy(umap1);
2280
416
  umap2 = isl_union_map_copy(umap2);
2281
416
  umap1 = isl_union_map_align_params(umap1,
2282
416
            isl_union_map_get_space(umap2));
2283
416
  umap2 = isl_union_map_align_params(umap2,
2284
416
            isl_union_map_get_space(umap1));
2285
416
2286
416
  if (!umap1 || !umap2)
2287
0
    goto error;
2288
416
2289
416
  data.umap2 = umap2;
2290
416
  if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2291
416
           &is_disjoint_entry, &data) < 0 &&
2292
416
      
data.is_disjoint2
)
2293
0
    goto error;
2294
416
2295
416
  isl_union_map_free(umap1);
2296
416
  isl_union_map_free(umap2);
2297
416
2298
416
  return data.is_disjoint;
2299
0
error:
2300
0
  isl_union_map_free(umap1);
2301
0
  isl_union_map_free(umap2);
2302
0
  return isl_bool_error;
2303
416
}
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
372
{
2310
372
  return isl_union_map_is_disjoint(uset1, uset2);
2311
372
}
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 (!isl_basic_map_plain_is_empty(*sample))
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 (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2334
0
           &sample_entry, &sample) < 0 &&
2335
0
      !sample)
2336
0
    goto error;
2337
0
2338
0
  if (!sample)
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
10.9k
{
2369
10.9k
  struct isl_forall_data *data = user;
2370
10.9k
  isl_map *map = *entry;
2371
10.9k
2372
10.9k
  data->res = data->fn(map);
2373
10.9k
  if (data->res < 0)
2374
0
    return isl_stat_error;
2375
10.9k
2376
10.9k
  if (!data->res)
2377
10.9k
    return isl_stat_error;
2378
0
2379
0
  return isl_stat_ok;
2380
0
}
2381
2382
static isl_bool union_map_forall(__isl_keep isl_union_map *umap,
2383
  isl_bool (*fn)(__isl_keep isl_map *map))
2384
13.3k
{
2385
13.3k
  struct isl_forall_data data = { isl_bool_true, fn };
2386
13.3k
2387
13.3k
  if (!umap)
2388
38
    return isl_bool_error;
2389
13.2k
2390
13.2k
  if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2391
13.2k
           &forall_entry, &data) < 0 && 
data.res10.9k
)
2392
0
    return isl_bool_error;
2393
13.2k
2394
13.2k
  return data.res;
2395
13.2k
}
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
0
{
2405
0
  struct isl_forall_user_data *data = user;
2406
0
  isl_map *map = *entry;
2407
0
2408
0
  data->res = data->fn(map, data->user);
2409
0
  if (data->res < 0)
2410
0
    return isl_stat_error;
2411
0
2412
0
  if (!data->res)
2413
0
    return isl_stat_error;
2414
0
2415
0
  return isl_stat_ok;
2416
0
}
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
0
{
2423
0
  struct isl_forall_user_data data = { isl_bool_true, fn, user };
2424
0
2425
0
  if (!umap)
2426
0
    return isl_bool_error;
2427
0
2428
0
  if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2429
0
           &forall_user_entry, &data) < 0 && data.res)
2430
0
    return isl_bool_error;
2431
0
2432
0
  return data.res;
2433
0
}
2434
2435
isl_bool isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2436
13.3k
{
2437
13.3k
  return union_map_forall(umap, &isl_map_is_empty);
2438
13.3k
}
2439
2440
isl_bool isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2441
376
{
2442
376
  return isl_union_map_is_empty(uset);
2443
376
}
2444
2445
static isl_bool is_subset_of_identity(__isl_keep isl_map *map)
2446
0
{
2447
0
  isl_bool is_subset;
2448
0
  isl_space *dim;
2449
0
  isl_map *id;
2450
0
2451
0
  if (!map)
2452
0
    return isl_bool_error;
2453
0
2454
0
  if (!isl_space_tuple_is_equal(map->dim, isl_dim_in,
2455
0
          map->dim, isl_dim_out))
2456
0
    return isl_bool_false;
2457
0
2458
0
  dim = isl_map_get_space(map);
2459
0
  id = isl_map_identity(dim);
2460
0
2461
0
  is_subset = isl_map_is_subset(map, id);
2462
0
2463
0
  isl_map_free(id);
2464
0
2465
0
  return is_subset;
2466
0
}
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
16
{
2473
16
  isl_map *map;
2474
16
  isl_bool sv;
2475
16
2476
16
  umap = isl_union_map_copy(umap);
2477
16
  map = isl_map_from_union_map(umap);
2478
16
  sv = isl_map_is_single_valued(map);
2479
16
  isl_map_free(map);
2480
16
2481
16
  return sv;
2482
16
}
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
0
{
2511
0
  struct isl_union_map_is_sv_data *data = user;
2512
0
  isl_union_map *umap, *test;
2513
0
2514
0
  umap = isl_union_map_copy(data->umap);
2515
0
  umap = isl_union_map_intersect_domain(umap,
2516
0
            isl_union_set_from_set(set));
2517
0
2518
0
  if (isl_union_map_n_map(umap) == 1) {
2519
0
    data->sv = single_map_is_single_valued(umap);
2520
0
    isl_union_map_free(umap);
2521
0
  } else {
2522
0
    test = isl_union_map_reverse(isl_union_map_copy(umap));
2523
0
    test = isl_union_map_apply_range(test, umap);
2524
0
2525
0
    data->sv = union_map_forall(test, &is_subset_of_identity);
2526
0
2527
0
    isl_union_map_free(test);
2528
0
  }
2529
0
2530
0
  if (data->sv < 0 || !data->sv)
2531
0
    return isl_stat_error;
2532
0
  return isl_stat_ok;
2533
0
}
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
16
{
2543
16
  isl_union_map *universe;
2544
16
  isl_union_set *domain;
2545
16
  struct isl_union_map_is_sv_data data;
2546
16
2547
16
  if (isl_union_map_n_map(umap) == 1)
2548
16
    return single_map_is_single_valued(umap);
2549
0
2550
0
  universe = isl_union_map_universe(isl_union_map_copy(umap));
2551
0
  domain = isl_union_map_domain(universe);
2552
0
2553
0
  data.sv = isl_bool_true;
2554
0
  data.umap = umap;
2555
0
  if (isl_union_set_foreach_set(domain,
2556
0
          &single_valued_on_domain, &data) < 0 && data.sv)
2557
0
    data.sv = isl_bool_error;
2558
16
  isl_union_set_free(domain);
2559
16
2560
16
  return data.sv;
2561
16
}
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 && !equal)
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 || *non_identity)
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 || !*identity)
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 || non_identity)
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
0
{
2684
0
  int i;
2685
0
  struct isl_fixed_map *v;
2686
0
2687
0
  v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2688
0
  if (!v)
2689
0
    return NULL;
2690
0
  for (i = 0; i < n; ++i)
2691
0
    isl_int_init(v[i].v);
2692
0
  return v;
2693
0
}
2694
2695
static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2696
0
{
2697
0
  int i;
2698
0
2699
0
  if (!v)
2700
0
    return;
2701
0
  for (i = 0; i < n; ++i)
2702
0
    isl_int_clear(v[i].v);
2703
0
  free(v);
2704
0
}
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
0
{
2710
0
  const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2711
0
  const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2712
0
2713
0
  return isl_int_cmp(e1->v, e2->v);
2714
0
}
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
0
{
2730
0
  struct isl_fixed_dim_data *data = user;
2731
0
2732
0
  data->v[data->n].map = map;
2733
0
  return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2734
0
              &data->v[data->n++].v);
2735
0
}
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
0
{
2753
0
  int i;
2754
0
2755
0
  if (!v)
2756
0
    goto error;
2757
0
2758
0
  qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2759
0
2760
0
  for (i = 0; i + 1 < n; ++i) {
2761
0
    int j, k;
2762
0
    isl_union_map *part;
2763
0
    int injective;
2764
0
2765
0
    for (j = i + 1; j < n; ++j)
2766
0
      if (isl_int_ne(v[i].v, v[j].v))
2767
0
        break;
2768
0
2769
0
    if (j == i + 1)
2770
0
      continue;
2771
0
2772
0
    part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2773
0
    for (k = i; k < j; ++k)
2774
0
      part = isl_union_map_add_map(part,
2775
0
                 isl_map_copy(v[k].map));
2776
0
2777
0
    injective = plain_injective_on_range(part, pos + 1, n_range);
2778
0
    if (injective < 0)
2779
0
      goto error;
2780
0
    if (!injective)
2781
0
      break;
2782
0
2783
0
    i = j - 1;
2784
0
  }
2785
0
2786
0
  isl_space_free(dim);
2787
0
  free_isl_fixed_map_array(v, n);
2788
0
  return i + 1 >= n;
2789
0
error:
2790
0
  isl_space_free(dim);
2791
0
  free_isl_fixed_map_array(v, n);
2792
0
  return -1;
2793
0
}
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
0
{
2804
0
  isl_ctx *ctx;
2805
0
  int n;
2806
0
  struct isl_fixed_dim_data data = { NULL };
2807
0
2808
0
  ctx = isl_union_map_get_ctx(umap);
2809
0
2810
0
  n = isl_union_map_n_map(umap);
2811
0
  if (!umap)
2812
0
    goto error;
2813
0
2814
0
  if (n <= 1) {
2815
0
    isl_union_map_free(umap);
2816
0
    return isl_bool_true;
2817
0
  }
2818
0
2819
0
  if (first >= n_range) {
2820
0
    isl_union_map_free(umap);
2821
0
    return isl_bool_false;
2822
0
  }
2823
0
2824
0
  data.v = alloc_isl_fixed_map_array(ctx, n);
2825
0
  if (!data.v)
2826
0
    goto error;
2827
0
2828
0
  for (data.pos = first; data.pos < n_range; ++data.pos) {
2829
0
    isl_bool fixed;
2830
0
    int injective;
2831
0
    isl_space *dim;
2832
0
2833
0
    data.n = 0;
2834
0
    fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2835
0
    if (fixed < 0)
2836
0
      goto error;
2837
0
    if (!fixed)
2838
0
      continue;
2839
0
    dim = isl_union_map_get_space(umap);
2840
0
    injective = separates(data.v, n, dim, data.pos, n_range);
2841
0
    isl_union_map_free(umap);
2842
0
    return injective;
2843
0
  }
2844
0
2845
0
  free_isl_fixed_map_array(data.v, n);
2846
0
  isl_union_map_free(umap);
2847
0
2848
0
  return isl_bool_false;
2849
0
error:
2850
0
  free_isl_fixed_map_array(data.v, n);
2851
0
  isl_union_map_free(umap);
2852
0
  return isl_bool_error;
2853
0
}
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
0
{
2861
0
  isl_union_map *umap = user;
2862
0
2863
0
  umap = isl_union_map_copy(umap);
2864
0
  umap = isl_union_map_intersect_range(umap,
2865
0
      isl_union_set_from_set(isl_set_copy(ran)));
2866
0
  return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2867
0
}
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
0
{
2877
0
  isl_bool in;
2878
0
  isl_union_map *univ;
2879
0
  isl_union_set *ran;
2880
0
2881
0
  in = union_map_forall(umap, &isl_map_plain_is_injective);
2882
0
  if (in < 0)
2883
0
    return isl_bool_error;
2884
0
  if (!in)
2885
0
    return isl_bool_false;
2886
0
2887
0
  univ = isl_union_map_universe(isl_union_map_copy(umap));
2888
0
  ran = isl_union_map_range(univ);
2889
0
2890
0
  in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2891
0
2892
0
  isl_union_set_free(ran);
2893
0
2894
0
  return in;
2895
0
}
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 || !sv)
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
210
{
2910
210
  struct isl_un_op_control control = {
2911
210
    .filter = &isl_map_can_zip,
2912
210
    .fn_map = &isl_map_zip,
2913
210
  };
2914
210
  return un_op(umap, &control);
2915
210
}
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
251
{
2922
251
  struct isl_un_op_control control = {
2923
251
    .filter = &isl_map_can_uncurry,
2924
251
    .fn_map = &isl_map_uncurry,
2925
251
  };
2926
251
  return un_op(umap, &control);
2927
251
}
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
174
{
2934
174
  struct isl_un_op_control control = {
2935
174
    .filter = &isl_map_can_curry,
2936
174
    .fn_map = &isl_map_curry,
2937
174
  };
2938
174
  return un_op(umap, &control);
2939
174
}
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
0
{
2947
0
  struct isl_un_op_control control = {
2948
0
    .filter = &isl_map_can_range_curry,
2949
0
    .fn_map = &isl_map_range_curry,
2950
0
  };
2951
0
  return un_op(umap, &control);
2952
0
}
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 (uset->table.n == 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 (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
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.03k
{
3047
2.03k
  return isl_space_tuple_is_equal(map->dim, isl_dim_in,
3048
2.03k
          space, isl_dim_out);
3049
2.03k
}
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
836
{
3063
836
  return isl_space_tuple_is_equal(map->dim, isl_dim_set,
3064
836
          space, isl_dim_out);
3065
836
}
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
2.87k
{
3091
2.87k
  int m;
3092
2.87k
  isl_map *map = *entry;
3093
2.87k
  struct isl_union_map_preimage_data *data = user;
3094
2.87k
  isl_bool empty;
3095
2.87k
3096
2.87k
  m = data->match(map, data->space);
3097
2.87k
  if (m < 0)
3098
0
    return isl_stat_error;
3099
2.87k
  if (!m)
3100
558
    return isl_stat_ok;
3101
2.31k
3102
2.31k
  map = isl_map_copy(map);
3103
2.31k
  map = data->fn(map, isl_pw_multi_aff_copy(data->pma));
3104
2.31k
3105
2.31k
  empty = isl_map_is_empty(map);
3106
2.31k
  if (empty < 0 || empty) {
3107
0
    isl_map_free(map);
3108
0
    return empty < 0 ? isl_stat_error : isl_stat_ok;
3109
0
  }
3110
2.31k
3111
2.31k
  data->res = isl_union_map_add_map(data->res, map);
3112
2.31k
3113
2.31k
  return isl_stat_ok;
3114
2.31k
}
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
2.57k
{
3128
2.57k
  isl_ctx *ctx;
3129
2.57k
  isl_space *space;
3130
2.57k
  struct isl_union_map_preimage_data data;
3131
2.57k
3132
2.57k
  umap = isl_union_map_align_params(umap,
3133
2.57k
              isl_pw_multi_aff_get_space(pma));
3134
2.57k
  pma = isl_pw_multi_aff_align_params(pma, isl_union_map_get_space(umap));
3135
2.57k
3136
2.57k
  if (!umap || !pma)
3137
0
    goto error;
3138
2.57k
3139
2.57k
  ctx = isl_union_map_get_ctx(umap);
3140
2.57k
  space = isl_union_map_get_space(umap);
3141
2.57k
  data.space = isl_pw_multi_aff_get_space(pma);
3142
2.57k
  data.pma = pma;
3143
2.57k
  data.res = isl_union_map_alloc(space, umap->table.n);
3144
2.57k
  data.match = match;
3145
2.57k
  data.fn = fn;
3146
2.57k
  if (isl_hash_table_foreach(ctx, &umap->table, &preimage_entry,
3147
2.57k
          &data) < 0)
3148
0
    data.res = isl_union_map_free(data.res);
3149
2.57k
3150
2.57k
  isl_space_free(data.space);
3151
2.57k
  isl_union_map_free(umap);
3152
2.57k
  isl_pw_multi_aff_free(pma);
3153
2.57k
  return data.res;
3154
0
error:
3155
0
  isl_union_map_free(umap);
3156
0
  isl_pw_multi_aff_free(pma);
3157
0
  return NULL;
3158
2.57k
}
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.03k
{
3170
2.03k
  return preimage_pw_multi_aff(umap, pma, &domain_match,
3171
2.03k
          &isl_map_preimage_domain_pw_multi_aff);
3172
2.03k
}
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
544
{
3197
544
  return preimage_pw_multi_aff(uset, pma, &set_match,
3198
544
          &isl_set_preimage_pw_multi_aff);
3199
544
}
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.03k
{
3211
2.03k
  return isl_union_map_preimage_domain_pw_multi_aff(umap,
3212
2.03k
          isl_pw_multi_aff_from_multi_aff(ma));
3213
2.03k
}
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 (!m)
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 || empty) {
3282
0
    isl_map_free(map);
3283
0
    return empty < 0 ? isl_stat_error : isl_stat_ok;
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 || !mpa)
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
544
{
3367
544
  struct isl_union_map_preimage_upma_data *data = user;
3368
544
  isl_union_map *umap;
3369
544
3370
544
  umap = isl_union_map_copy(data->umap);
3371
544
  umap = data->fn(umap, pma);
3372
544
  data->res = isl_union_map_union(data->res, umap);
3373
544
3374
544
  return data->res ? isl_stat_ok : 
isl_stat_error0
;
3375
544
}
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
104
{
3389
104
  struct isl_union_map_preimage_upma_data data;
3390
104
3391
104
  data.umap = umap;
3392
104
  data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3393
104
  data.fn = fn;
3394
104
  if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3395
104
                &preimage_upma, &data) < 0)
3396
0
    data.res = isl_union_map_free(data.res);
3397
104
3398
104
  isl_union_map_free(umap);
3399
104
  isl_union_pw_multi_aff_free(upma);
3400
104
3401
104
  return data.res;
3402
104
}
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
104
{
3447
104
  return preimage_union_pw_multi_aff(uset, upma,
3448
104
          &isl_union_set_preimage_pw_multi_aff);
3449
104
}
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
0
{
3481
0
  return total(umap, &isl_map_remove_divs);
3482
0
}
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
0
{
3490
0
  return isl_union_map_remove_divs(uset);
3491
0
}
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
0
{
3511
0
  struct isl_union_map_project_out_data *data = user;
3512
0
3513
0
  map = isl_map_project_out(map, data->type, data->first, data->n);
3514
0
  data->res = isl_union_map_add_map(data->res, map);
3515
0
3516
0
  return isl_stat_ok;
3517
0
}
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
0
{
3528
0
  isl_space *space;
3529
0
  struct isl_union_map_project_out_data data = { type, first, n };
3530
0
3531
0
  if (!umap)
3532
0
    return NULL;
3533
0
3534
0
  if (type != isl_dim_param)
3535
0
    isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
3536
0
      "can only project out parameters",
3537
0
      return isl_union_map_free(umap));
3538
0
3539
0
  space = isl_union_map_get_space(umap);
3540
0
  space = isl_space_drop_dims(space, type, first, n);
3541
0
  data.res = isl_union_map_empty(space);
3542
0
  if (isl_union_map_foreach_map(umap, &project_out, &data) < 0)
3543
0
    data.res = isl_union_map_free(data.res);
3544
0
3545
0
  isl_union_map_free(umap);
3546
0
3547
0
  return data.res;
3548
0
}
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
0
{
3559
0
  return isl_union_map_project_out(uset, type, first, n);
3560
0
}
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
4.71k
{
3624
4.71k
  struct isl_union_map_reset_range_space_data *data = user;
3625
4.71k
  isl_space *space;
3626
4.71k
3627
4.71k
  space = isl_map_get_space(map);
3628
4.71k
  space = isl_space_domain(space);
3629
4.71k
  space = isl_space_extend_domain_with_range(space,
3630
4.71k
            isl_space_copy(data->range));
3631
4.71k
  map = isl_map_reset_space(map, space);
3632
4.71k
  data->res = isl_union_map_add_map(data->res, map);
3633
4.71k
3634
4.71k
  return data->res ? isl_stat_ok : 
isl_stat_error0
;
3635
4.71k
}
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
2.34k
{
3649
2.34k
  struct isl_union_map_reset_range_space_data data = { space };
3650
2.34k
3651
2.34k
  data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3652
2.34k
  if (isl_union_map_foreach_map(umap, &reset_range_space, &data) < 0)
3653
0
    data.res = isl_union_map_free(data.res);
3654
2.34k
3655
2.34k
  isl_space_free(space);
3656
2.34k
  isl_union_map_free(umap);
3657
2.34k
  return data.res;
3658
2.34k
}
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_ok : isl_stat_error;
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 < n; ++i) {
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 = isl_hash_init();
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
0
{
3824
0
  int *n = user;
3825
0
3826
0
  *n += isl_set_n_basic_set(set);
3827
0
  isl_set_free(set);
3828
0
3829
0
  return isl_stat_ok;
3830
0
}
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
0
{
3836
0
  int n = 0;
3837
0
3838
0
  if (isl_union_set_foreach_set(uset, &add_n, &n) < 0)
3839
0
    return -1;
3840
0
3841
0
  return n;
3842
0
}
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
0
{
3848
0
  isl_basic_set_list **list = user;
3849
0
  isl_basic_set_list *list_i;
3850
0
3851
0
  list_i = isl_set_get_basic_set_list(set);
3852
0
  *list = isl_basic_set_list_concat(*list, list_i);
3853
0
  isl_set_free(set);
3854
0
3855
0
  if (!*list)
3856
0
    return isl_stat_error;
3857
0
  return isl_stat_ok;
3858
0
}
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
0
{
3868
0
  int n;
3869
0
  isl_ctx *ctx;
3870
0
  isl_basic_set_list *list;
3871
0
3872
0
  if (!uset)
3873
0
    return NULL;
3874
0
  ctx = isl_union_set_get_ctx(uset);
3875
0
  n = isl_union_set_n_basic_set(uset);
3876
0
  if (n < 0)
3877
0
    return NULL;
3878
0
  list = isl_basic_set_list_alloc(ctx, n);
3879
0
  if (isl_union_set_foreach_set(uset, &add_list, &list) < 0)
3880
0
    list = isl_basic_set_list_free(list);
3881
0
3882
0
  return list;
3883
0
}