Coverage Report

Created: 2017-04-27 19:33

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