Coverage Report

Created: 2018-08-20 19:24

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_space.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 * Copyright 2013-2014 Ecole Normale Superieure
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
12
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13
 */
14
15
#include <stdlib.h>
16
#include <string.h>
17
#include <isl_space_private.h>
18
#include <isl_id_private.h>
19
#include <isl_reordering.h>
20
21
isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim)
22
1.69M
{
23
1.69M
  return dim ? dim->ctx : NULL;
24
1.69M
}
25
26
__isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
27
      unsigned nparam, unsigned n_in, unsigned n_out)
28
5.01M
{
29
5.01M
  isl_space *dim;
30
5.01M
31
5.01M
  dim = isl_alloc_type(ctx, struct isl_space);
32
5.01M
  if (!dim)
33
12
    return NULL;
34
5.01M
35
5.01M
  dim->ctx = ctx;
36
5.01M
  isl_ctx_ref(ctx);
37
5.01M
  dim->ref = 1;
38
5.01M
  dim->nparam = nparam;
39
5.01M
  dim->n_in = n_in;
40
5.01M
  dim->n_out = n_out;
41
5.01M
42
5.01M
  dim->tuple_id[0] = NULL;
43
5.01M
  dim->tuple_id[1] = NULL;
44
5.01M
45
5.01M
  dim->nested[0] = NULL;
46
5.01M
  dim->nested[1] = NULL;
47
5.01M
48
5.01M
  dim->n_id = 0;
49
5.01M
  dim->ids = NULL;
50
5.01M
51
5.01M
  return dim;
52
5.01M
}
53
54
/* Mark the space as being that of a set, by setting the domain tuple
55
 * to isl_id_none.
56
 */
57
static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)
58
1.59M
{
59
1.59M
  space = isl_space_cow(space);
60
1.59M
  if (!space)
61
2
    return NULL;
62
1.59M
  space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
63
1.59M
  return space;
64
1.59M
}
65
66
/* Is the space that of a set?
67
 */
68
isl_bool isl_space_is_set(__isl_keep isl_space *space)
69
1.77M
{
70
1.77M
  if (!space)
71
0
    return isl_bool_error;
72
1.77M
  if (space->n_in != 0 || 
space->nested[0]1.47M
)
73
307k
    return isl_bool_false;
74
1.46M
  if (space->tuple_id[0] != &isl_id_none)
75
16.6k
    return isl_bool_false;
76
1.44M
  return isl_bool_true;
77
1.44M
}
78
79
/* Is the given space that of a map?
80
 */
81
isl_bool isl_space_is_map(__isl_keep isl_space *space)
82
30.3k
{
83
30.3k
  if (!space)
84
0
    return isl_bool_error;
85
30.3k
  return space->tuple_id[0] != &isl_id_none &&
86
30.3k
    
space->tuple_id[1] != &isl_id_none805
;
87
30.3k
}
88
89
__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
90
      unsigned nparam, unsigned dim)
91
533k
{
92
533k
  isl_space *space;
93
533k
  space = isl_space_alloc(ctx, nparam, 0, dim);
94
533k
  space = mark_as_set(space);
95
533k
  return space;
96
533k
}
97
98
/* Mark the space as being that of a parameter domain, by setting
99
 * both tuples to isl_id_none.
100
 */
101
static __isl_give isl_space *mark_as_params(isl_space *space)
102
198k
{
103
198k
  if (!space)
104
0
    return NULL;
105
198k
  space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
106
198k
  space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
107
198k
  return space;
108
198k
}
109
110
/* Is the space that of a parameter domain?
111
 */
112
isl_bool isl_space_is_params(__isl_keep isl_space *space)
113
766k
{
114
766k
  if (!space)
115
27
    return isl_bool_error;
116
766k
  if (space->n_in != 0 || 
space->nested[0]620k
||
117
766k
      
space->n_out != 0620k
||
space->nested[1]467k
)
118
299k
    return isl_bool_false;
119
466k
  if (space->tuple_id[0] != &isl_id_none)
120
25.9k
    return isl_bool_false;
121
440k
  if (space->tuple_id[1] != &isl_id_none)
122
38.9k
    return isl_bool_false;
123
401k
  return isl_bool_true;
124
401k
}
125
126
/* Create a space for a parameter domain.
127
 */
128
__isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
129
28.6k
{
130
28.6k
  isl_space *space;
131
28.6k
  space = isl_space_alloc(ctx, nparam, 0, 0);
132
28.6k
  space = mark_as_params(space);
133
28.6k
  return space;
134
28.6k
}
135
136
static unsigned global_pos(__isl_keep isl_space *dim,
137
         enum isl_dim_type type, unsigned pos)
138
51.2M
{
139
51.2M
  struct isl_ctx *ctx = dim->ctx;
140
51.2M
141
51.2M
  switch (type) {
142
51.2M
  case isl_dim_param:
143
33.9M
    isl_assert(ctx, pos < dim->nparam,
144
33.9M
          return isl_space_dim(dim, isl_dim_all));
145
33.9M
    return pos;
146
33.9M
  case isl_dim_in:
147
6.70M
    isl_assert(ctx, pos < dim->n_in,
148
6.70M
          return isl_space_dim(dim, isl_dim_all));
149
6.70M
    return pos + dim->nparam;
150
10.6M
  case isl_dim_out:
151
10.6M
    isl_assert(ctx, pos < dim->n_out,
152
10.6M
          return isl_space_dim(dim, isl_dim_all));
153
10.6M
    return pos + dim->nparam + dim->n_in;
154
10.6M
  default:
155
0
    isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
156
51.2M
  }
157
51.2M
  
return isl_space_dim(dim, isl_dim_all)0
;
158
51.2M
}
159
160
/* Extend length of ids array to the total number of dimensions.
161
 */
162
static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)
163
2.19M
{
164
2.19M
  isl_id **ids;
165
2.19M
  int i;
166
2.19M
167
2.19M
  if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
168
523k
    return dim;
169
1.67M
170
1.67M
  if (!dim->ids) {
171
1.67M
    dim->ids = isl_calloc_array(dim->ctx,
172
1.67M
        isl_id *, isl_space_dim(dim, isl_dim_all));
173
1.67M
    if (!dim->ids)
174
0
      goto error;
175
669
  } else {
176
669
    ids = isl_realloc_array(dim->ctx, dim->ids,
177
669
        isl_id *, isl_space_dim(dim, isl_dim_all));
178
669
    if (!ids)
179
0
      goto error;
180
669
    dim->ids = ids;
181
3.69k
    for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); 
++i3.02k
)
182
3.02k
      dim->ids[i] = NULL;
183
669
  }
184
1.67M
185
1.67M
  dim->n_id = isl_space_dim(dim, isl_dim_all);
186
1.67M
187
1.67M
  return dim;
188
0
error:
189
0
  isl_space_free(dim);
190
0
  return NULL;
191
1.67M
}
192
193
static __isl_give isl_space *set_id(__isl_take isl_space *dim,
194
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
195
6.84M
{
196
6.84M
  dim = isl_space_cow(dim);
197
6.84M
198
6.84M
  if (!dim)
199
0
    goto error;
200
6.84M
201
6.84M
  pos = global_pos(dim, type, pos);
202
6.84M
  if (pos == isl_space_dim(dim, isl_dim_all))
203
0
    goto error;
204
6.84M
205
6.84M
  if (pos >= dim->n_id) {
206
1.67M
    if (!id)
207
0
      return dim;
208
1.67M
    dim = extend_ids(dim);
209
1.67M
    if (!dim)
210
0
      goto error;
211
6.84M
  }
212
6.84M
213
6.84M
  dim->ids[pos] = id;
214
6.84M
215
6.84M
  return dim;
216
0
error:
217
0
  isl_id_free(id);
218
0
  isl_space_free(dim);
219
0
  return NULL;
220
6.84M
}
221
222
static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
223
         enum isl_dim_type type, unsigned pos)
224
44.4M
{
225
44.4M
  if (!dim)
226
0
    return NULL;
227
44.4M
228
44.4M
  pos = global_pos(dim, type, pos);
229
44.4M
  if (pos == isl_space_dim(dim, isl_dim_all))
230
0
    return NULL;
231
44.4M
  if (pos >= dim->n_id)
232
3.12M
    return NULL;
233
41.3M
  return dim->ids[pos];
234
41.3M
}
235
236
static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
237
2.17M
{
238
2.17M
  switch (type) {
239
2.17M
  
case isl_dim_param: return 0713k
;
240
2.17M
  
case isl_dim_in: return dim->nparam506k
;
241
2.17M
  
case isl_dim_out: return dim->nparam + dim->n_in951k
;
242
2.17M
  
default: return 00
;
243
2.17M
  }
244
2.17M
}
245
246
static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
247
278M
{
248
278M
  switch (type) {
249
278M
  
case isl_dim_param: return dim->nparam54.0M
;
250
278M
  
case isl_dim_in: return dim->n_in34.9M
;
251
278M
  
case isl_dim_out: return dim->n_out40.2M
;
252
278M
  
case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out149M
;
253
278M
  
default: return 00
;
254
278M
  }
255
278M
}
256
257
unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
258
199M
{
259
199M
  if (!dim)
260
4
    return 0;
261
199M
  return n(dim, type);
262
199M
}
263
264
unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
265
1.96M
{
266
1.96M
  if (!dim)
267
0
    return 0;
268
1.96M
  return offset(dim, type);
269
1.96M
}
270
271
static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,
272
  enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,
273
  enum isl_dim_type src_type)
274
6.71M
{
275
6.71M
  int i;
276
6.71M
  isl_id *id;
277
6.71M
278
6.71M
  if (!dst)
279
0
    return NULL;
280
6.71M
281
18.4M
  
for (i = 0; 6.71M
i < n(src, src_type);
++i11.6M
) {
282
11.6M
    id = get_id(src, src_type, i);
283
11.6M
    if (!id)
284
7.01M
      continue;
285
4.66M
    dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
286
4.66M
    if (!dst)
287
0
      return NULL;
288
4.66M
  }
289
6.71M
  return dst;
290
6.71M
}
291
292
__isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
293
3.74M
{
294
3.74M
  isl_space *dup;
295
3.74M
  if (!dim)
296
0
    return NULL;
297
3.74M
  dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
298
3.74M
  if (!dup)
299
12
    return NULL;
300
3.74M
  if (dim->tuple_id[0] &&
301
3.74M
      
!(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0]))2.14M
)
302
0
    goto error;
303
3.74M
  if (dim->tuple_id[1] &&
304
3.74M
      
!(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1]))882k
)
305
0
    goto error;
306
3.74M
  if (dim->nested[0] && 
!(dup->nested[0] = isl_space_copy(dim->nested[0]))715k
)
307
0
    goto error;
308
3.74M
  if (dim->nested[1] && 
!(dup->nested[1] = isl_space_copy(dim->nested[1]))929k
)
309
0
    goto error;
310
3.74M
  if (!dim->ids)
311
2.28M
    return dup;
312
1.46M
  dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);
313
1.46M
  dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);
314
1.46M
  dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);
315
1.46M
  return dup;
316
0
error:
317
0
  isl_space_free(dup);
318
0
  return NULL;
319
1.46M
}
320
321
__isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)
322
18.6M
{
323
18.6M
  if (!dim)
324
11
    return NULL;
325
18.6M
326
18.6M
  if (dim->ref == 1)
327
14.9M
    return dim;
328
3.72M
  dim->ref--;
329
3.72M
  return isl_space_dup(dim);
330
3.72M
}
331
332
__isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
333
16.7M
{
334
16.7M
  if (!dim)
335
9.11k
    return NULL;
336
16.7M
337
16.7M
  dim->ref++;
338
16.7M
  return dim;
339
16.7M
}
340
341
__isl_null isl_space *isl_space_free(__isl_take isl_space *space)
342
29.4M
{
343
29.4M
  int i;
344
29.4M
345
29.4M
  if (!space)
346
11.4M
    return NULL;
347
18.0M
348
18.0M
  if (--space->ref > 0)
349
12.9M
    return NULL;
350
5.00M
351
5.00M
  isl_id_free(space->tuple_id[0]);
352
5.00M
  isl_id_free(space->tuple_id[1]);
353
5.00M
354
5.00M
  isl_space_free(space->nested[0]);
355
5.00M
  isl_space_free(space->nested[1]);
356
5.00M
357
11.8M
  for (i = 0; i < space->n_id; 
++i6.79M
)
358
6.79M
    isl_id_free(space->ids[i]);
359
5.00M
  free(space->ids);
360
5.00M
  isl_ctx_deref(space->ctx);
361
5.00M
  
362
5.00M
  free(space);
363
5.00M
364
5.00M
  return NULL;
365
5.00M
}
366
367
/* Check if "s" is a valid dimension or tuple name.
368
 * We currently only forbid names that look like a number.
369
 *
370
 * s is assumed to be non-NULL.
371
 */
372
static int name_ok(isl_ctx *ctx, const char *s)
373
55.3k
{
374
55.3k
  char *p;
375
55.3k
  long dummy;
376
55.3k
377
55.3k
  dummy = strtol(s, &p, 0);
378
55.3k
  if (p != s)
379
55.3k
    
isl_die0
(ctx, isl_error_invalid, "name looks like a number",
380
55.3k
      return 0);
381
55.3k
382
55.3k
  return 1;
383
55.3k
}
384
385
/* Is it possible for the given dimension type to have a tuple id?
386
 */
387
static int space_can_have_id(__isl_keep isl_space *space,
388
  enum isl_dim_type type)
389
118k
{
390
118k
  if (!space)
391
0
    return 0;
392
118k
  if (isl_space_is_params(space))
393
118k
    
isl_die0
(space->ctx, isl_error_invalid,
394
118k
      "parameter spaces don't have tuple ids", return 0);
395
118k
  if (isl_space_is_set(space) && 
type != isl_dim_set30.9k
)
396
118k
    
isl_die0
(space->ctx, isl_error_invalid,
397
118k
      "set spaces can only have a set id", return 0);
398
118k
  if (type != isl_dim_in && 
type != isl_dim_out118k
)
399
118k
    
isl_die0
(space->ctx, isl_error_invalid,
400
118k
      "only input, output and set tuples can have ids",
401
118k
      return 0);
402
118k
403
118k
  return 1;
404
118k
}
405
406
/* Does the tuple have an id?
407
 */
408
isl_bool isl_space_has_tuple_id(__isl_keep isl_space *dim,
409
  enum isl_dim_type type)
410
117k
{
411
117k
  if (!space_can_have_id(dim, type))
412
0
    return isl_bool_error;
413
117k
  return dim->tuple_id[type - isl_dim_in] != NULL;
414
117k
}
415
416
__isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,
417
  enum isl_dim_type type)
418
38.2k
{
419
38.2k
  int has_id;
420
38.2k
421
38.2k
  if (!dim)
422
0
    return NULL;
423
38.2k
  has_id = isl_space_has_tuple_id(dim, type);
424
38.2k
  if (has_id < 0)
425
0
    return NULL;
426
38.2k
  if (!has_id)
427
38.2k
    
isl_die0
(dim->ctx, isl_error_invalid,
428
38.2k
      "tuple has no id", return NULL);
429
38.2k
  return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
430
38.2k
}
431
432
__isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,
433
  enum isl_dim_type type, __isl_take isl_id *id)
434
2.06M
{
435
2.06M
  dim = isl_space_cow(dim);
436
2.06M
  if (!dim || !id)
437
0
    goto error;
438
2.06M
  if (type != isl_dim_in && 
type != isl_dim_out262k
)
439
2.06M
    
isl_die0
(dim->ctx, isl_error_invalid,
440
2.06M
      "only input, output and set tuples can have names",
441
2.06M
      goto error);
442
2.06M
443
2.06M
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
444
2.06M
  dim->tuple_id[type - isl_dim_in] = id;
445
2.06M
446
2.06M
  return dim;
447
0
error:
448
0
  isl_id_free(id);
449
0
  isl_space_free(dim);
450
0
  return NULL;
451
2.06M
}
452
453
__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
454
  enum isl_dim_type type)
455
5.95k
{
456
5.95k
  dim = isl_space_cow(dim);
457
5.95k
  if (!dim)
458
0
    return NULL;
459
5.95k
  if (type != isl_dim_in && type != isl_dim_out)
460
5.95k
    
isl_die0
(dim->ctx, isl_error_invalid,
461
5.95k
      "only input, output and set tuples can have names",
462
5.95k
      goto error);
463
5.95k
464
5.95k
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
465
5.95k
  dim->tuple_id[type - isl_dim_in] = NULL;
466
5.95k
467
5.95k
  return dim;
468
0
error:
469
0
  isl_space_free(dim);
470
0
  return NULL;
471
5.95k
}
472
473
/* Set the id of the given dimension of "space" to "id".
474
 * If the dimension already has an id, then it is replaced.
475
 * If the dimension is a parameter, then we need to change it
476
 * in the nested spaces (if any) as well.
477
 */
478
__isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,
479
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
480
82.4k
{
481
82.4k
  space = isl_space_cow(space);
482
82.4k
  if (!space || !id)
483
0
    goto error;
484
82.4k
485
82.4k
  if (type == isl_dim_param) {
486
61.1k
    int i;
487
61.1k
488
183k
    for (i = 0; i < 2; 
++i122k
) {
489
122k
      if (!space->nested[i])
490
122k
        continue;
491
0
      space->nested[i] =
492
0
        isl_space_set_dim_id(space->nested[i],
493
0
            type, pos, isl_id_copy(id));
494
0
      if (!space->nested[i])
495
0
        goto error;
496
0
    }
497
61.1k
  }
498
82.4k
499
82.4k
  isl_id_free(get_id(space, type, pos));
500
82.4k
  return set_id(space, type, pos, id);
501
0
error:
502
0
  isl_id_free(id);
503
0
  isl_space_free(space);
504
0
  return NULL;
505
82.4k
}
506
507
/* Reset the id of the given dimension of "space".
508
 * If the dimension already has an id, then it is removed.
509
 * If the dimension is a parameter, then we need to reset it
510
 * in the nested spaces (if any) as well.
511
 */
512
__isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,
513
  enum isl_dim_type type, unsigned pos)
514
0
{
515
0
  space = isl_space_cow(space);
516
0
  if (!space)
517
0
    goto error;
518
0
519
0
  if (type == isl_dim_param) {
520
0
    int i;
521
0
522
0
    for (i = 0; i < 2; ++i) {
523
0
      if (!space->nested[i])
524
0
        continue;
525
0
      space->nested[i] =
526
0
        isl_space_reset_dim_id(space->nested[i],
527
0
              type, pos);
528
0
      if (!space->nested[i])
529
0
        goto error;
530
0
    }
531
0
  }
532
0
533
0
  isl_id_free(get_id(space, type, pos));
534
0
  return set_id(space, type, pos, NULL);
535
0
error:
536
0
  isl_space_free(space);
537
0
  return NULL;
538
0
}
539
540
isl_bool isl_space_has_dim_id(__isl_keep isl_space *dim,
541
  enum isl_dim_type type, unsigned pos)
542
1.11k
{
543
1.11k
  if (!dim)
544
0
    return isl_bool_error;
545
1.11k
  return get_id(dim, type, pos) != NULL;
546
1.11k
}
547
548
__isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,
549
  enum isl_dim_type type, unsigned pos)
550
778k
{
551
778k
  if (!dim)
552
0
    return NULL;
553
778k
  if (!get_id(dim, type, pos))
554
778k
    
isl_die0
(dim->ctx, isl_error_invalid,
555
778k
      "dim has no id", return NULL);
556
778k
  return isl_id_copy(get_id(dim, type, pos));
557
778k
}
558
559
__isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,
560
  enum isl_dim_type type, const char *s)
561
48.8k
{
562
48.8k
  isl_id *id;
563
48.8k
564
48.8k
  if (!dim)
565
0
    return NULL;
566
48.8k
567
48.8k
  if (!s)
568
0
    return isl_space_reset_tuple_id(dim, type);
569
48.8k
570
48.8k
  if (!name_ok(dim->ctx, s))
571
0
    goto error;
572
48.8k
573
48.8k
  id = isl_id_alloc(dim->ctx, s, NULL);
574
48.8k
  return isl_space_set_tuple_id(dim, type, id);
575
0
error:
576
0
  isl_space_free(dim);
577
0
  return NULL;
578
48.8k
}
579
580
/* Does the tuple have a name?
581
 */
582
isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,
583
  enum isl_dim_type type)
584
1.06k
{
585
1.06k
  isl_id *id;
586
1.06k
587
1.06k
  if (!space_can_have_id(space, type))
588
0
    return isl_bool_error;
589
1.06k
  id = space->tuple_id[type - isl_dim_in];
590
1.06k
  return id && 
id->name180
;
591
1.06k
}
592
593
__isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
594
   enum isl_dim_type type)
595
10.8k
{
596
10.8k
  isl_id *id;
597
10.8k
  if (!dim)
598
0
    return NULL;
599
10.8k
  if (type != isl_dim_in && 
type != isl_dim_out6.40k
)
600
0
    return NULL;
601
10.8k
  id = dim->tuple_id[type - isl_dim_in];
602
10.8k
  return id ? 
id->name9.35k
: NULL;
603
10.8k
}
604
605
__isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,
606
         enum isl_dim_type type, unsigned pos,
607
         const char *s)
608
6.50k
{
609
6.50k
  isl_id *id;
610
6.50k
611
6.50k
  if (!dim)
612
0
    return NULL;
613
6.50k
  if (!s)
614
0
    return isl_space_reset_dim_id(dim, type, pos);
615
6.50k
  if (!name_ok(dim->ctx, s))
616
0
    goto error;
617
6.50k
  id = isl_id_alloc(dim->ctx, s, NULL);
618
6.50k
  return isl_space_set_dim_id(dim, type, pos, id);
619
0
error:
620
0
  isl_space_free(dim);
621
0
  return NULL;
622
6.50k
}
623
624
/* Does the given dimension have a name?
625
 */
626
isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,
627
  enum isl_dim_type type, unsigned pos)
628
6.62k
{
629
6.62k
  isl_id *id;
630
6.62k
631
6.62k
  if (!space)
632
0
    return isl_bool_error;
633
6.62k
  id = get_id(space, type, pos);
634
6.62k
  return id && 
id->name1.01k
;
635
6.62k
}
636
637
__isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,
638
         enum isl_dim_type type, unsigned pos)
639
313k
{
640
313k
  isl_id *id = get_id(dim, type, pos);
641
313k
  return id ? 
id->name261k
: NULL;
642
313k
}
643
644
int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,
645
  __isl_keep isl_id *id)
646
394
{
647
394
  int i;
648
394
  int offset;
649
394
  int n;
650
394
651
394
  if (!dim || !id)
652
0
    return -1;
653
394
654
394
  offset = isl_space_offset(dim, type);
655
394
  n = isl_space_dim(dim, type);
656
518
  for (i = 0; i < n && 
offset + i < dim->n_id516
;
++i124
)
657
516
    if (dim->ids[offset + i] == id)
658
392
      return i;
659
394
660
394
  
return -12
;
661
394
}
662
663
int isl_space_find_dim_by_name(__isl_keep isl_space *space,
664
  enum isl_dim_type type, const char *name)
665
875
{
666
875
  int i;
667
875
  int offset;
668
875
  int n;
669
875
670
875
  if (!space || !name)
671
0
    return -1;
672
875
673
875
  offset = isl_space_offset(space, type);
674
875
  n = isl_space_dim(space, type);
675
1.39k
  for (i = 0; i < n && 
offset + i < space->n_id524
;
++i524
) {
676
524
    isl_id *id = get_id(space, type, i);
677
524
    if (id && id->name && !strcmp(id->name, name))
678
0
      return i;
679
524
  }
680
875
681
875
  return -1;
682
875
}
683
684
/* Reset the user pointer on all identifiers of parameters and tuples
685
 * of "space".
686
 */
687
__isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)
688
0
{
689
0
  int i;
690
0
  isl_ctx *ctx;
691
0
  isl_id *id;
692
0
  const char *name;
693
0
694
0
  if (!space)
695
0
    return NULL;
696
0
697
0
  ctx = isl_space_get_ctx(space);
698
0
699
0
  for (i = 0; i < space->nparam && i < space->n_id; ++i) {
700
0
    if (!isl_id_get_user(space->ids[i]))
701
0
      continue;
702
0
    space = isl_space_cow(space);
703
0
    if (!space)
704
0
      return NULL;
705
0
    name = isl_id_get_name(space->ids[i]);
706
0
    id = isl_id_alloc(ctx, name, NULL);
707
0
    isl_id_free(space->ids[i]);
708
0
    space->ids[i] = id;
709
0
    if (!id)
710
0
      return isl_space_free(space);
711
0
  }
712
0
713
0
  for (i = 0; i < 2; ++i) {
714
0
    if (!space->tuple_id[i])
715
0
      continue;
716
0
    if (!isl_id_get_user(space->tuple_id[i]))
717
0
      continue;
718
0
    space = isl_space_cow(space);
719
0
    if (!space)
720
0
      return NULL;
721
0
    name = isl_id_get_name(space->tuple_id[i]);
722
0
    id = isl_id_alloc(ctx, name, NULL);
723
0
    isl_id_free(space->tuple_id[i]);
724
0
    space->tuple_id[i] = id;
725
0
    if (!id)
726
0
      return isl_space_free(space);
727
0
  }
728
0
729
0
  for (i = 0; i < 2; ++i) {
730
0
    if (!space->nested[i])
731
0
      continue;
732
0
    space = isl_space_cow(space);
733
0
    if (!space)
734
0
      return NULL;
735
0
    space->nested[i] = isl_space_reset_user(space->nested[i]);
736
0
    if (!space->nested[i])
737
0
      return isl_space_free(space);
738
0
  }
739
0
740
0
  return space;
741
0
}
742
743
static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,
744
  enum isl_dim_type type)
745
44.4M
{
746
44.4M
  if (!dim)
747
0
    return NULL;
748
44.4M
  if (type == isl_dim_in)
749
13.8M
    return dim->tuple_id[0];
750
30.6M
  if (type == isl_dim_out)
751
12.5M
    return dim->tuple_id[1];
752
18.0M
  return NULL;
753
18.0M
}
754
755
static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
756
  enum isl_dim_type type)
757
41.3M
{
758
41.3M
  if (!dim)
759
0
    return NULL;
760
41.3M
  if (type == isl_dim_in)
761
11.8M
    return dim->nested[0];
762
29.4M
  if (type == isl_dim_out)
763
11.4M
    return dim->nested[1];
764
18.0M
  return NULL;
765
18.0M
}
766
767
/* Are the two spaces the same, apart from positions and names of parameters?
768
 */
769
isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,
770
  __isl_keep isl_space *space2)
771
6.90M
{
772
6.90M
  if (!space1 || !space2)
773
0
    return isl_bool_error;
774
6.90M
  if (space1 == space2)
775
2.24M
    return isl_bool_true;
776
4.66M
  return isl_space_tuple_is_equal(space1, isl_dim_in,
777
4.66M
          space2, isl_dim_in) &&
778
4.66M
         isl_space_tuple_is_equal(space1, isl_dim_out,
779
4.01M
          space2, isl_dim_out);
780
4.66M
}
781
782
/* Check if the tuple of type "type1" of "space1" is the same as
783
 * the tuple of type "type2" of "space2".
784
 *
785
 * That is, check if the tuples have the same identifier, the same dimension
786
 * and the same internal structure.
787
 * The identifiers of the dimensions inside the tuples do not affect the result.
788
 *
789
 * Note that this function only checks the tuples themselves.
790
 * If nested tuples are involved, then we need to be careful not
791
 * to have result affected by possibly differing parameters
792
 * in those nested tuples.
793
 */
794
isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,
795
  enum isl_dim_type type1, __isl_keep isl_space *space2,
796
  enum isl_dim_type type2)
797
21.7M
{
798
21.7M
  isl_id *id1, *id2;
799
21.7M
  isl_space *nested1, *nested2;
800
21.7M
801
21.7M
  if (!space1 || !space2)
802
0
    return isl_bool_error;
803
21.7M
804
21.7M
  if (space1 == space2 && 
type1 == type21.95M
)
805
6.35k
    return isl_bool_true;
806
21.7M
807
21.7M
  if (n(space1, type1) != n(space2, type2))
808
2.21M
    return isl_bool_false;
809
19.5M
  id1 = tuple_id(space1, type1);
810
19.5M
  id2 = tuple_id(space2, type2);
811
19.5M
  if (!id1 ^ !id2)
812
625k
    return isl_bool_false;
813
18.9M
  if (id1 && 
id1 != id23.95M
)
814
149k
    return isl_bool_false;
815
18.7M
  nested1 = nested(space1, type1);
816
18.7M
  nested2 = nested(space2, type2);
817
18.7M
  if (!nested1 ^ !nested2)
818
64.0k
    return isl_bool_false;
819
18.7M
  if (nested1 && 
!isl_space_has_equal_tuples(nested1, nested2)3.55M
)
820
26.1k
    return isl_bool_false;
821
18.6M
  return isl_bool_true;
822
18.6M
}
823
824
static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,
825
  __isl_keep isl_space *space2, enum isl_dim_type type2)
826
11.6M
{
827
11.6M
  int i;
828
11.6M
829
11.6M
  if (space1 == space2 && 
type1 == type22.84M
)
830
904k
    return isl_bool_true;
831
10.7M
832
10.7M
  if (!isl_space_tuple_is_equal(space1, type1, space2, type2))
833
2.07M
    return isl_bool_false;
834
8.68M
835
8.68M
  if (!space1->ids && 
!space2->ids5.67M
)
836
5.63M
    return isl_bool_true;
837
3.04M
838
11.3M
  
for (i = 0; 3.04M
i < n(space1, type1);
++i8.26M
) {
839
8.32M
    if (get_id(space1, type1, i) != get_id(space2, type2, i))
840
62.0k
      return isl_bool_false;
841
8.32M
  }
842
3.04M
  
return isl_bool_true2.98M
;
843
3.04M
}
844
845
/* Do "space1" and "space2" have the same parameters?
846
 */
847
isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,
848
  __isl_keep isl_space *space2)
849
9.31M
{
850
9.31M
  if (!space1 || 
!space29.31M
)
851
2
    return isl_bool_error;
852
9.31M
853
9.31M
  return match(space1, isl_dim_param, space2, isl_dim_param);
854
9.31M
}
855
856
/* Do "space1" and "space2" have the same identifiers for all
857
 * the tuple variables?
858
 */
859
isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,
860
  __isl_keep isl_space *space2)
861
204k
{
862
204k
  isl_bool equal;
863
204k
864
204k
  if (!space1 || !space2)
865
0
    return isl_bool_error;
866
204k
867
204k
  equal = match(space1, isl_dim_in, space2, isl_dim_in);
868
204k
  if (equal < 0 || !equal)
869
132
    return equal;
870
204k
  return match(space1, isl_dim_out, space2, isl_dim_out);
871
204k
}
872
873
isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,
874
  __isl_keep isl_space *space2, enum isl_dim_type type2)
875
0
{
876
0
  if (!space1 || !space2)
877
0
    return isl_bool_error;
878
0
879
0
  return match(space1, type1, space2, type2);
880
0
}
881
882
static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
883
  unsigned first, unsigned n, __isl_keep isl_id **ids)
884
2.77M
{
885
2.77M
  int i;
886
2.77M
887
7.00M
  for (i = 0; i < n ; 
++i4.23M
)
888
4.23M
    ids[i] = get_id(dim, type, first + i);
889
2.77M
}
890
891
static __isl_give isl_space *space_extend(__isl_take isl_space *space,
892
      unsigned nparam, unsigned n_in, unsigned n_out)
893
702k
{
894
702k
  isl_id **ids = NULL;
895
702k
896
702k
  if (!space)
897
0
    return NULL;
898
702k
  if (space->nparam == nparam &&
899
702k
      
space->n_in == n_in579k
&&
space->n_out == n_out571k
)
900
1.44k
    return space;
901
700k
902
700k
  isl_assert(space->ctx, space->nparam <= nparam, goto error);
903
700k
  isl_assert(space->ctx, space->n_in <= n_in, goto error);
904
700k
  isl_assert(space->ctx, space->n_out <= n_out, goto error);
905
700k
906
700k
  space = isl_space_cow(space);
907
700k
  if (!space)
908
0
    goto error;
909
700k
910
700k
  if (space->ids) {
911
307k
    unsigned n;
912
307k
    n = nparam + n_in + n_out;
913
307k
    if (n < nparam || n < n_in || n < n_out)
914
307k
      
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
915
307k
        "overflow in total number of dimensions",
916
307k
        goto error);
917
307k
    ids = isl_calloc_array(space->ctx, isl_id *, n);
918
307k
    if (!ids)
919
0
      goto error;
920
307k
    get_ids(space, isl_dim_param, 0, space->nparam, ids);
921
307k
    get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);
922
307k
    get_ids(space, isl_dim_out, 0, space->n_out,
923
307k
      ids + nparam + n_in);
924
307k
    free(space->ids);
925
307k
    space->ids = ids;
926
307k
    space->n_id = nparam + n_in + n_out;
927
307k
  }
928
700k
  space->nparam = nparam;
929
700k
  space->n_in = n_in;
930
700k
  space->n_out = n_out;
931
700k
932
700k
  return space;
933
0
error:
934
0
  free(ids);
935
0
  isl_space_free(space);
936
0
  return NULL;
937
700k
}
938
939
__isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
940
  unsigned nparam, unsigned n_in, unsigned n_out)
941
0
{
942
0
  return space_extend(space, nparam, n_in, n_out);
943
0
}
944
945
__isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
946
  enum isl_dim_type type, unsigned n)
947
702k
{
948
702k
  space = isl_space_reset(space, type);
949
702k
  if (!space)
950
9
    return NULL;
951
702k
  switch (type) {
952
702k
  case isl_dim_param:
953
122k
    space = space_extend(space,
954
122k
        space->nparam + n, space->n_in, space->n_out);
955
122k
    if (space && space->nested[0] &&
956
122k
        !(space->nested[0] = isl_space_add_dims(space->nested[0],
957
125
                isl_dim_param, n)))
958
0
      goto error;
959
122k
    if (space && space->nested[1] &&
960
122k
        !(space->nested[1] = isl_space_add_dims(space->nested[1],
961
389
                isl_dim_param, n)))
962
0
      goto error;
963
122k
    return space;
964
122k
  case isl_dim_in:
965
8.83k
    return space_extend(space,
966
8.83k
        space->nparam, space->n_in + n, space->n_out);
967
570k
  case isl_dim_out:
968
570k
    return space_extend(space,
969
570k
        space->nparam, space->n_in, space->n_out + n);
970
122k
  default:
971
0
    isl_die(space->ctx, isl_error_invalid,
972
702k
      "cannot add dimensions of specified type", goto error);
973
702k
  }
974
702k
error:
975
0
  isl_space_free(space);
976
0
  return NULL;
977
702k
}
978
979
/* Add a parameter with identifier "id" to "space", provided
980
 * it does not already appear in "space".
981
 */
982
__isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,
983
  __isl_take isl_id *id)
984
1
{
985
1
  int pos;
986
1
987
1
  if (!space || !id)
988
0
    goto error;
989
1
990
1
  if (isl_space_find_dim_by_id(space, isl_dim_param, id) >= 0) {
991
0
    isl_id_free(id);
992
0
    return space;
993
0
  }
994
1
995
1
  pos = isl_space_dim(space, isl_dim_param);
996
1
  space = isl_space_add_dims(space, isl_dim_param, 1);
997
1
  space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
998
1
999
1
  return space;
1000
0
error:
1001
0
  isl_space_free(space);
1002
0
  isl_id_free(id);
1003
0
  return NULL;
1004
1
}
1005
1006
static int valid_dim_type(enum isl_dim_type type)
1007
2.03M
{
1008
2.03M
  switch (type) {
1009
2.03M
  case isl_dim_param:
1010
2.03M
  case isl_dim_in:
1011
2.03M
  case isl_dim_out:
1012
2.03M
    return 1;
1013
2.03M
  default:
1014
0
    return 0;
1015
2.03M
  }
1016
2.03M
}
1017
1018
/* Insert "n" dimensions of type "type" at position "pos".
1019
 * If we are inserting parameters, then they are also inserted in
1020
 * any nested spaces.
1021
 */
1022
__isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
1023
  enum isl_dim_type type, unsigned pos, unsigned n)
1024
178k
{
1025
178k
  isl_ctx *ctx;
1026
178k
  isl_id **ids = NULL;
1027
178k
  unsigned total;
1028
178k
1029
178k
  if (!space)
1030
0
    return NULL;
1031
178k
  if (n == 0)
1032
6
    return isl_space_reset(space, type);
1033
178k
1034
178k
  ctx = isl_space_get_ctx(space);
1035
178k
  if (!valid_dim_type(type))
1036
178k
    
isl_die0
(ctx, isl_error_invalid,
1037
178k
      "cannot insert dimensions of specified type",
1038
178k
      goto error);
1039
178k
1040
178k
  total = isl_space_dim(space, isl_dim_all);
1041
178k
  if (total + n < total)
1042
178k
    
isl_die0
(ctx, isl_error_invalid,
1043
178k
      "overflow in total number of dimensions",
1044
178k
      return isl_space_free(space));
1045
178k
  isl_assert(ctx, pos <= isl_space_dim(space, type), goto error);
1046
178k
1047
178k
  space = isl_space_cow(space);
1048
178k
  if (!space)
1049
0
    return NULL;
1050
178k
1051
178k
  if (space->ids) {
1052
52.7k
    enum isl_dim_type t, o = isl_dim_param;
1053
52.7k
    int off;
1054
52.7k
    int s[3];
1055
52.7k
    ids = isl_calloc_array(ctx, isl_id *,
1056
52.7k
           space->nparam + space->n_in + space->n_out + n);
1057
52.7k
    if (!ids)
1058
0
      goto error;
1059
52.7k
    off = 0;
1060
52.7k
    s[isl_dim_param - o] = space->nparam;
1061
52.7k
    s[isl_dim_in - o] = space->n_in;
1062
52.7k
    s[isl_dim_out - o] = space->n_out;
1063
211k
    for (t = isl_dim_param; t <= isl_dim_out; 
++t158k
) {
1064
158k
      if (t != type) {
1065
105k
        get_ids(space, t, 0, s[t - o], ids + off);
1066
105k
        off += s[t - o];
1067
105k
      } else {
1068
52.7k
        get_ids(space, t, 0, pos, ids + off);
1069
52.7k
        off += pos + n;
1070
52.7k
        get_ids(space, t, pos, s[t - o] - pos,
1071
52.7k
          ids + off);
1072
52.7k
        off += s[t - o] - pos;
1073
52.7k
      }
1074
158k
    }
1075
52.7k
    free(space->ids);
1076
52.7k
    space->ids = ids;
1077
52.7k
    space->n_id = space->nparam + space->n_in + space->n_out + n;
1078
52.7k
  }
1079
178k
  switch (type) {
1080
178k
  
case isl_dim_param: space->nparam += n; break2.79k
;
1081
178k
  
case isl_dim_in: space->n_in += n; break10.2k
;
1082
178k
  
case isl_dim_out: space->n_out += n; break165k
;
1083
178k
  
default: ;0
1084
178k
  }
1085
178k
  space = isl_space_reset(space, type);
1086
178k
1087
178k
  if (type == isl_dim_param) {
1088
2.79k
    if (space && space->nested[0] &&
1089
2.79k
        !(space->nested[0] = isl_space_insert_dims(space->nested[0],
1090
0
                isl_dim_param, pos, n)))
1091
0
      goto error;
1092
2.79k
    if (space && space->nested[1] &&
1093
2.79k
        !(space->nested[1] = isl_space_insert_dims(space->nested[1],
1094
1
                isl_dim_param, pos, n)))
1095
0
      goto error;
1096
178k
  }
1097
178k
1098
178k
  return space;
1099
0
error:
1100
0
  isl_space_free(space);
1101
0
  return NULL;
1102
178k
}
1103
1104
__isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1105
  enum isl_dim_type dst_type, unsigned dst_pos,
1106
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1107
1.14k
{
1108
1.14k
  int i;
1109
1.14k
1110
1.14k
  space = isl_space_reset(space, src_type);
1111
1.14k
  space = isl_space_reset(space, dst_type);
1112
1.14k
  if (!space)
1113
0
    return NULL;
1114
1.14k
  if (n == 0)
1115
290
    return space;
1116
852
1117
852
  isl_assert(space->ctx, src_pos + n <= isl_space_dim(space, src_type),
1118
852
    goto error);
1119
852
1120
852
  if (dst_type == src_type && 
dst_pos == src_pos0
)
1121
0
    return space;
1122
852
1123
852
  isl_assert(space->ctx, dst_type != src_type, goto error);
1124
852
1125
852
  space = isl_space_cow(space);
1126
852
  if (!space)
1127
0
    return NULL;
1128
852
1129
852
  if (space->ids) {
1130
306
    isl_id **ids;
1131
306
    enum isl_dim_type t, o = isl_dim_param;
1132
306
    int off;
1133
306
    int s[3];
1134
306
    ids = isl_calloc_array(space->ctx, isl_id *,
1135
306
         space->nparam + space->n_in + space->n_out);
1136
306
    if (!ids)
1137
0
      goto error;
1138
306
    off = 0;
1139
306
    s[isl_dim_param - o] = space->nparam;
1140
306
    s[isl_dim_in - o] = space->n_in;
1141
306
    s[isl_dim_out - o] = space->n_out;
1142
1.22k
    for (t = isl_dim_param; t <= isl_dim_out; 
++t918
) {
1143
918
      if (t == dst_type) {
1144
306
        get_ids(space, t, 0, dst_pos, ids + off);
1145
306
        off += dst_pos;
1146
306
        get_ids(space, src_type, src_pos, n, ids + off);
1147
306
        off += n;
1148
306
        get_ids(space, t, dst_pos, s[t - o] - dst_pos,
1149
306
            ids + off);
1150
306
        off += s[t - o] - dst_pos;
1151
612
      } else if (t == src_type) {
1152
306
        get_ids(space, t, 0, src_pos, ids + off);
1153
306
        off += src_pos;
1154
306
        get_ids(space, t, src_pos + n,
1155
306
              s[t - o] - src_pos - n, ids + off);
1156
306
        off += s[t - o] - src_pos - n;
1157
306
      } else {
1158
306
        get_ids(space, t, 0, s[t - o], ids + off);
1159
306
        off += s[t - o];
1160
306
      }
1161
918
    }
1162
306
    free(space->ids);
1163
306
    space->ids = ids;
1164
306
    space->n_id = space->nparam + space->n_in + space->n_out;
1165
306
  }
1166
852
1167
852
  switch (dst_type) {
1168
852
  
case isl_dim_param: space->nparam += n; break82
;
1169
852
  
case isl_dim_in: space->n_in += n; break361
;
1170
852
  
case isl_dim_out: space->n_out += n; break409
;
1171
852
  
default: ;0
1172
852
  }
1173
852
1174
852
  switch (src_type) {
1175
852
  
case isl_dim_param: space->nparam -= n; break234
;
1176
852
  
case isl_dim_in: space->n_in -= n; break193
;
1177
852
  
case isl_dim_out: space->n_out -= n; break425
;
1178
852
  
default: ;0
1179
852
  }
1180
852
1181
852
  if (dst_type != isl_dim_param && 
src_type != isl_dim_param770
)
1182
536
    return space;
1183
316
1184
948
  
for (i = 0; 316
i < 2;
++i632
) {
1185
632
    if (!space->nested[i])
1186
615
      continue;
1187
17
    space->nested[i] = isl_space_replace_params(space->nested[i],
1188
17
                   space);
1189
17
    if (!space->nested[i])
1190
0
      goto error;
1191
17
  }
1192
316
1193
316
  return space;
1194
0
error:
1195
0
  isl_space_free(space);
1196
0
  return NULL;
1197
316
}
1198
1199
/* Check that "space1" and "space2" have the same parameters,
1200
 * reporting an error if they do not.
1201
 */
1202
isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1203
  __isl_keep isl_space *space2)
1204
658k
{
1205
658k
  isl_bool equal;
1206
658k
1207
658k
  equal = isl_space_has_equal_params(space1, space2);
1208
658k
  if (equal < 0)
1209
2
    return isl_stat_error;
1210
658k
  if (!equal)
1211
658k
    
isl_die0
(isl_space_get_ctx(space1), isl_error_invalid,
1212
658k
      "parameters need to match", return isl_stat_error);
1213
658k
  return isl_stat_ok;
1214
658k
}
1215
1216
__isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1217
  __isl_take isl_space *right)
1218
548k
{
1219
548k
  isl_space *dim;
1220
548k
1221
548k
  if (isl_space_check_equal_params(left, right) < 0)
1222
2
    goto error;
1223
548k
1224
548k
  isl_assert(left->ctx,
1225
548k
    isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1226
548k
    goto error);
1227
548k
1228
548k
  dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
1229
548k
  if (!dim)
1230
0
    goto error;
1231
548k
1232
548k
  dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
1233
548k
  dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
1234
548k
  dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
1235
548k
1236
548k
  if (dim && left->tuple_id[0] &&
1237
548k
      
!(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0]))184k
)
1238
0
    goto error;
1239
548k
  if (dim && right->tuple_id[1] &&
1240
548k
      
!(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1]))149k
)
1241
0
    goto error;
1242
548k
  if (dim && left->nested[0] &&
1243
548k
      
!(dim->nested[0] = isl_space_copy(left->nested[0]))207k
)
1244
0
    goto error;
1245
548k
  if (dim && right->nested[1] &&
1246
548k
      
!(dim->nested[1] = isl_space_copy(right->nested[1]))253k
)
1247
0
    goto error;
1248
548k
1249
548k
  isl_space_free(left);
1250
548k
  isl_space_free(right);
1251
548k
1252
548k
  return dim;
1253
2
error:
1254
2
  isl_space_free(left);
1255
2
  isl_space_free(right);
1256
2
  return NULL;
1257
548k
}
1258
1259
/* Given two map spaces { A -> C } and { B -> D }, construct the space
1260
 * { [A -> B] -> [C -> D] }.
1261
 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1262
 */
1263
__isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1264
  __isl_take isl_space *right)
1265
2.76k
{
1266
2.76k
  isl_space *dom1, *dom2, *nest1, *nest2;
1267
2.76k
  int is_set;
1268
2.76k
1269
2.76k
  if (!left || !right)
1270
0
    goto error;
1271
2.76k
1272
2.76k
  is_set = isl_space_is_set(left);
1273
2.76k
  if (is_set != isl_space_is_set(right))
1274
2.76k
    
isl_die0
(isl_space_get_ctx(left), isl_error_invalid,
1275
2.76k
      "expecting either two set spaces or two map spaces",
1276
2.76k
      goto error);
1277
2.76k
  if (is_set)
1278
274
    return isl_space_range_product(left, right);
1279
2.49k
1280
2.49k
  if (isl_space_check_equal_params(left, right) < 0)
1281
0
    goto error;
1282
2.49k
1283
2.49k
  dom1 = isl_space_domain(isl_space_copy(left));
1284
2.49k
  dom2 = isl_space_domain(isl_space_copy(right));
1285
2.49k
  nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1286
2.49k
1287
2.49k
  dom1 = isl_space_range(left);
1288
2.49k
  dom2 = isl_space_range(right);
1289
2.49k
  nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1290
2.49k
1291
2.49k
  return isl_space_join(isl_space_reverse(nest1), nest2);
1292
0
error:
1293
0
  isl_space_free(left);
1294
0
  isl_space_free(right);
1295
0
  return NULL;
1296
2.49k
}
1297
1298
/* Given two spaces { A -> C } and { B -> C }, construct the space
1299
 * { [A -> B] -> C }
1300
 */
1301
__isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1302
  __isl_take isl_space *right)
1303
1.88k
{
1304
1.88k
  isl_space *ran, *dom1, *dom2, *nest;
1305
1.88k
1306
1.88k
  if (isl_space_check_equal_params(left, right) < 0)
1307
0
    goto error;
1308
1.88k
1309
1.88k
  if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))
1310
1.88k
    
isl_die0
(left->ctx, isl_error_invalid,
1311
1.88k
      "ranges need to match", goto error);
1312
1.88k
1313
1.88k
  ran = isl_space_range(isl_space_copy(left));
1314
1.88k
1315
1.88k
  dom1 = isl_space_domain(left);
1316
1.88k
  dom2 = isl_space_domain(right);
1317
1.88k
  nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1318
1.88k
1319
1.88k
  return isl_space_join(isl_space_reverse(nest), ran);
1320
0
error:
1321
0
  isl_space_free(left);
1322
0
  isl_space_free(right);
1323
0
  return NULL;
1324
1.88k
}
1325
1326
__isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1327
  __isl_take isl_space *right)
1328
105k
{
1329
105k
  isl_space *dom, *ran1, *ran2, *nest;
1330
105k
1331
105k
  if (isl_space_check_equal_params(left, right) < 0)
1332
0
    goto error;
1333
105k
1334
105k
  if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))
1335
105k
    
isl_die0
(left->ctx, isl_error_invalid,
1336
105k
      "domains need to match", goto error);
1337
105k
1338
105k
  dom = isl_space_domain(isl_space_copy(left));
1339
105k
1340
105k
  ran1 = isl_space_range(left);
1341
105k
  ran2 = isl_space_range(right);
1342
105k
  nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1343
105k
1344
105k
  return isl_space_join(isl_space_reverse(dom), nest);
1345
0
error:
1346
0
  isl_space_free(left);
1347
0
  isl_space_free(right);
1348
0
  return NULL;
1349
105k
}
1350
1351
/* Given a space of the form [A -> B] -> C, return the space A -> C.
1352
 */
1353
__isl_give isl_space *isl_space_domain_factor_domain(
1354
  __isl_take isl_space *space)
1355
857
{
1356
857
  isl_space *nested;
1357
857
  isl_space *domain;
1358
857
1359
857
  if (!space)
1360
0
    return NULL;
1361
857
  if (!isl_space_domain_is_wrapping(space))
1362
857
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1363
857
      "domain not a product", return isl_space_free(space));
1364
857
1365
857
  nested = space->nested[0];
1366
857
  domain = isl_space_copy(space);
1367
857
  domain = isl_space_drop_dims(domain, isl_dim_in,
1368
857
          nested->n_in, nested->n_out);
1369
857
  if (!domain)
1370
0
    return isl_space_free(space);
1371
857
  if (nested->tuple_id[0]) {
1372
538
    domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);
1373
538
    if (!domain->tuple_id[0])
1374
0
      goto error;
1375
857
  }
1376
857
  if (nested->nested[0]) {
1377
319
    domain->nested[0] = isl_space_copy(nested->nested[0]);
1378
319
    if (!domain->nested[0])
1379
0
      goto error;
1380
857
  }
1381
857
1382
857
  isl_space_free(space);
1383
857
  return domain;
1384
0
error:
1385
0
  isl_space_free(space);
1386
0
  isl_space_free(domain);
1387
0
  return NULL;
1388
857
}
1389
1390
/* Given a space of the form [A -> B] -> C, return the space B -> C.
1391
 */
1392
__isl_give isl_space *isl_space_domain_factor_range(
1393
  __isl_take isl_space *space)
1394
20.5k
{
1395
20.5k
  isl_space *nested;
1396
20.5k
  isl_space *range;
1397
20.5k
1398
20.5k
  if (!space)
1399
0
    return NULL;
1400
20.5k
  if (!isl_space_domain_is_wrapping(space))
1401
20.5k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1402
20.5k
      "domain not a product", return isl_space_free(space));
1403
20.5k
1404
20.5k
  nested = space->nested[0];
1405
20.5k
  range = isl_space_copy(space);
1406
20.5k
  range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);
1407
20.5k
  if (!range)
1408
0
    return isl_space_free(space);
1409
20.5k
  if (nested->tuple_id[1]) {
1410
12.2k
    range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);
1411
12.2k
    if (!range->tuple_id[0])
1412
0
      goto error;
1413
20.5k
  }
1414
20.5k
  if (nested->nested[1]) {
1415
8.21k
    range->nested[0] = isl_space_copy(nested->nested[1]);
1416
8.21k
    if (!range->nested[0])
1417
0
      goto error;
1418
20.5k
  }
1419
20.5k
1420
20.5k
  isl_space_free(space);
1421
20.5k
  return range;
1422
0
error:
1423
0
  isl_space_free(space);
1424
0
  isl_space_free(range);
1425
0
  return NULL;
1426
20.5k
}
1427
1428
/* Internal function that selects the domain of the map that is
1429
 * embedded in either a set space or the range of a map space.
1430
 * In particular, given a space of the form [A -> B], return the space A.
1431
 * Given a space of the form A -> [B -> C], return the space A -> B.
1432
 */
1433
static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1434
2.21k
{
1435
2.21k
  isl_space *nested;
1436
2.21k
  isl_space *domain;
1437
2.21k
1438
2.21k
  if (!space)
1439
0
    return NULL;
1440
2.21k
1441
2.21k
  nested = space->nested[1];
1442
2.21k
  domain = isl_space_copy(space);
1443
2.21k
  domain = isl_space_drop_dims(domain, isl_dim_out,
1444
2.21k
          nested->n_in, nested->n_out);
1445
2.21k
  if (!domain)
1446
0
    return isl_space_free(space);
1447
2.21k
  if (nested->tuple_id[0]) {
1448
1.26k
    domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);
1449
1.26k
    if (!domain->tuple_id[1])
1450
0
      goto error;
1451
2.21k
  }
1452
2.21k
  if (nested->nested[0]) {
1453
940
    domain->nested[1] = isl_space_copy(nested->nested[0]);
1454
940
    if (!domain->nested[1])
1455
0
      goto error;
1456
2.21k
  }
1457
2.21k
1458
2.21k
  isl_space_free(space);
1459
2.21k
  return domain;
1460
0
error:
1461
0
  isl_space_free(space);
1462
0
  isl_space_free(domain);
1463
0
  return NULL;
1464
2.21k
}
1465
1466
/* Given a space of the form A -> [B -> C], return the space A -> B.
1467
 */
1468
__isl_give isl_space *isl_space_range_factor_domain(
1469
  __isl_take isl_space *space)
1470
2.21k
{
1471
2.21k
  if (!space)
1472
0
    return NULL;
1473
2.21k
  if (!isl_space_range_is_wrapping(space))
1474
2.21k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1475
2.21k
      "range not a product", return isl_space_free(space));
1476
2.21k
1477
2.21k
  return range_factor_domain(space);
1478
2.21k
}
1479
1480
/* Given a space of the form [A -> B], return the space A.
1481
 */
1482
static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1483
0
{
1484
0
  if (!space)
1485
0
    return NULL;
1486
0
  if (!isl_space_is_wrapping(space))
1487
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
1488
0
      "not a product", return isl_space_free(space));
1489
0
1490
0
  return range_factor_domain(space);
1491
0
}
1492
1493
/* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1494
 * Given a space of the form [A -> B], return the space A.
1495
 */
1496
__isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1497
132
{
1498
132
  if (!space)
1499
0
    return NULL;
1500
132
  if (isl_space_is_set(space))
1501
0
    return set_factor_domain(space);
1502
132
  space = isl_space_domain_factor_domain(space);
1503
132
  space = isl_space_range_factor_domain(space);
1504
132
  return space;
1505
132
}
1506
1507
/* Internal function that selects the range of the map that is
1508
 * embedded in either a set space or the range of a map space.
1509
 * In particular, given a space of the form [A -> B], return the space B.
1510
 * Given a space of the form A -> [B -> C], return the space A -> C.
1511
 */
1512
static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1513
13.3k
{
1514
13.3k
  isl_space *nested;
1515
13.3k
  isl_space *range;
1516
13.3k
1517
13.3k
  if (!space)
1518
0
    return NULL;
1519
13.3k
1520
13.3k
  nested = space->nested[1];
1521
13.3k
  range = isl_space_copy(space);
1522
13.3k
  range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);
1523
13.3k
  if (!range)
1524
0
    return isl_space_free(space);
1525
13.3k
  if (nested->tuple_id[1]) {
1526
742
    range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);
1527
742
    if (!range->tuple_id[1])
1528
0
      goto error;
1529
13.3k
  }
1530
13.3k
  if (nested->nested[1]) {
1531
12.6k
    range->nested[1] = isl_space_copy(nested->nested[1]);
1532
12.6k
    if (!range->nested[1])
1533
0
      goto error;
1534
13.3k
  }
1535
13.3k
1536
13.3k
  isl_space_free(space);
1537
13.3k
  return range;
1538
0
error:
1539
0
  isl_space_free(space);
1540
0
  isl_space_free(range);
1541
0
  return NULL;
1542
13.3k
}
1543
1544
/* Given a space of the form A -> [B -> C], return the space A -> C.
1545
 */
1546
__isl_give isl_space *isl_space_range_factor_range(
1547
  __isl_take isl_space *space)
1548
13.3k
{
1549
13.3k
  if (!space)
1550
0
    return NULL;
1551
13.3k
  if (!isl_space_range_is_wrapping(space))
1552
13.3k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1553
13.3k
      "range not a product", return isl_space_free(space));
1554
13.3k
1555
13.3k
  return range_factor_range(space);
1556
13.3k
}
1557
1558
/* Given a space of the form [A -> B], return the space B.
1559
 */
1560
static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1561
9
{
1562
9
  if (!space)
1563
0
    return NULL;
1564
9
  if (!isl_space_is_wrapping(space))
1565
9
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1566
9
      "not a product", return isl_space_free(space));
1567
9
1568
9
  return range_factor_range(space);
1569
9
}
1570
1571
/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1572
 * Given a space of the form [A -> B], return the space B.
1573
 */
1574
__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1575
12.6k
{
1576
12.6k
  if (!space)
1577
0
    return NULL;
1578
12.6k
  if (isl_space_is_set(space))
1579
9
    return set_factor_range(space);
1580
12.6k
  space = isl_space_domain_factor_range(space);
1581
12.6k
  space = isl_space_range_factor_range(space);
1582
12.6k
  return space;
1583
12.6k
}
1584
1585
__isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1586
12.5k
{
1587
12.5k
  isl_ctx *ctx;
1588
12.5k
  isl_id **ids = NULL;
1589
12.5k
  int n_id;
1590
12.5k
1591
12.5k
  if (!space)
1592
7
    return NULL;
1593
12.5k
  ctx = isl_space_get_ctx(space);
1594
12.5k
  if (!isl_space_is_set(space))
1595
12.5k
    
isl_die0
(ctx, isl_error_invalid, "not a set space", goto error);
1596
12.5k
  space = isl_space_cow(space);
1597
12.5k
  if (!space)
1598
0
    return NULL;
1599
12.5k
  n_id = space->nparam + space->n_out + space->n_out;
1600
12.5k
  if (n_id > 0 && 
space->ids11.9k
) {
1601
3.43k
    ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1602
3.43k
    if (!ids)
1603
0
      goto error;
1604
3.43k
    get_ids(space, isl_dim_param, 0, space->nparam, ids);
1605
3.43k
    get_ids(space, isl_dim_out, 0, space->n_out,
1606
3.43k
      ids + space->nparam);
1607
3.43k
  }
1608
12.5k
  space->n_in = space->n_out;
1609
12.5k
  if (ids) {
1610
3.43k
    free(space->ids);
1611
3.43k
    space->ids = ids;
1612
3.43k
    space->n_id = n_id;
1613
3.43k
    space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);
1614
3.43k
  }
1615
12.5k
  isl_id_free(space->tuple_id[0]);
1616
12.5k
  space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);
1617
12.5k
  isl_space_free(space->nested[0]);
1618
12.5k
  space->nested[0] = isl_space_copy(space->nested[1]);
1619
12.5k
  return space;
1620
0
error:
1621
0
  isl_space_free(space);
1622
0
  return NULL;
1623
12.5k
}
1624
1625
__isl_give isl_space *isl_space_map_from_domain_and_range(
1626
  __isl_take isl_space *domain, __isl_take isl_space *range)
1627
83.7k
{
1628
83.7k
  if (!domain || !range)
1629
0
    goto error;
1630
83.7k
  if (!isl_space_is_set(domain))
1631
83.7k
    
isl_die0
(isl_space_get_ctx(domain), isl_error_invalid,
1632
83.7k
      "domain is not a set space", goto error);
1633
83.7k
  if (!isl_space_is_set(range))
1634
83.7k
    
isl_die0
(isl_space_get_ctx(range), isl_error_invalid,
1635
83.7k
      "range is not a set space", goto error);
1636
83.7k
  return isl_space_join(isl_space_reverse(domain), range);
1637
0
error:
1638
0
  isl_space_free(domain);
1639
0
  isl_space_free(range);
1640
0
  return NULL;
1641
83.7k
}
1642
1643
static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1644
  enum isl_dim_type type,
1645
  unsigned first, unsigned n, __isl_take isl_id **ids)
1646
1.42M
{
1647
1.42M
  int i;
1648
1.42M
1649
3.46M
  for (i = 0; i < n ; 
++i2.03M
)
1650
2.03M
    dim = set_id(dim, type, first + i, ids[i]);
1651
1.42M
1652
1.42M
  return dim;
1653
1.42M
}
1654
1655
__isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
1656
1.94M
{
1657
1.94M
  unsigned t;
1658
1.94M
  isl_space *nested;
1659
1.94M
  isl_id **ids = NULL;
1660
1.94M
  isl_id *id;
1661
1.94M
1662
1.94M
  if (!dim)
1663
1
    return NULL;
1664
1.94M
  if (match(dim, isl_dim_in, dim, isl_dim_out))
1665
115k
    return dim;
1666
1.82M
1667
1.82M
  dim = isl_space_cow(dim);
1668
1.82M
  if (!dim)
1669
0
    return NULL;
1670
1.82M
1671
1.82M
  id = dim->tuple_id[0];
1672
1.82M
  dim->tuple_id[0] = dim->tuple_id[1];
1673
1.82M
  dim->tuple_id[1] = id;
1674
1.82M
1675
1.82M
  nested = dim->nested[0];
1676
1.82M
  dim->nested[0] = dim->nested[1];
1677
1.82M
  dim->nested[1] = nested;
1678
1.82M
1679
1.82M
  if (dim->ids) {
1680
713k
    int n_id = dim->n_in + dim->n_out;
1681
713k
    ids = isl_alloc_array(dim->ctx, isl_id *, n_id);
1682
713k
    if (n_id && 
!ids600k
)
1683
0
      goto error;
1684
713k
    get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1685
713k
    get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1686
713k
  }
1687
1.82M
1688
1.82M
  t = dim->n_in;
1689
1.82M
  dim->n_in = dim->n_out;
1690
1.82M
  dim->n_out = t;
1691
1.82M
1692
1.82M
  if (dim->ids) {
1693
713k
    dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1694
713k
    dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1695
713k
    free(ids);
1696
713k
  }
1697
1.82M
1698
1.82M
  return dim;
1699
0
error:
1700
0
  free(ids);
1701
0
  isl_space_free(dim);
1702
0
  return NULL;
1703
1.82M
}
1704
1705
__isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1706
  enum isl_dim_type type, unsigned first, unsigned num)
1707
2.24M
{
1708
2.24M
  int i;
1709
2.24M
1710
2.24M
  if (!dim)
1711
2
    return NULL;
1712
2.24M
1713
2.24M
  if (num == 0)
1714
381k
    return isl_space_reset(dim, type);
1715
1.86M
1716
1.86M
  if (!valid_dim_type(type))
1717
1.86M
    
isl_die0
(dim->ctx, isl_error_invalid,
1718
1.86M
      "cannot drop dimensions of specified type", goto error);
1719
1.86M
1720
1.86M
  if (first + num > n(dim, type) || first + num < first)
1721
1.86M
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1722
1.86M
      "index out of bounds", return isl_space_free(dim));
1723
1.86M
  dim = isl_space_cow(dim);
1724
1.86M
  if (!dim)
1725
2
    goto error;
1726
1.86M
  if (dim->ids) {
1727
524k
    dim = extend_ids(dim);
1728
524k
    if (!dim)
1729
0
      goto error;
1730
1.68M
    
for (i = 0; 524k
i < num;
++i1.16M
)
1731
1.16M
      isl_id_free(get_id(dim, type, first + i));
1732
582k
    for (i = first+num; i < n(dim, type); 
++i57.7k
)
1733
57.7k
      set_id(dim, type, i - num, get_id(dim, type, i));
1734
524k
    switch (type) {
1735
524k
    case isl_dim_param:
1736
29.9k
      get_ids(dim, isl_dim_in, 0, dim->n_in,
1737
29.9k
        dim->ids + offset(dim, isl_dim_in) - num);
1738
175k
    case isl_dim_in:
1739
175k
      get_ids(dim, isl_dim_out, 0, dim->n_out,
1740
175k
        dim->ids + offset(dim, isl_dim_out) - num);
1741
524k
    default:
1742
524k
      ;
1743
524k
    }
1744
524k
    dim->n_id -= num;
1745
524k
  }
1746
1.86M
  switch (type) {
1747
1.86M
  
case isl_dim_param: dim->nparam -= num; break30.6k
;
1748
1.86M
  
case isl_dim_in: dim->n_in -= num; break411k
;
1749
1.86M
  
case isl_dim_out: dim->n_out -= num; break1.41M
;
1750
1.86M
  
default: ;0
1751
1.86M
  }
1752
1.86M
  dim = isl_space_reset(dim, type);
1753
1.86M
  if (type == isl_dim_param) {
1754
30.6k
    if (dim && dim->nested[0] &&
1755
30.6k
        !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1756
122
                isl_dim_param, first, num)))
1757
0
      goto error;
1758
30.6k
    if (dim && dim->nested[1] &&
1759
30.6k
        !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1760
548
                isl_dim_param, first, num)))
1761
0
      goto error;
1762
1.86M
  }
1763
1.86M
  return dim;
1764
2
error:
1765
2
  isl_space_free(dim);
1766
2
  return NULL;
1767
1.86M
}
1768
1769
__isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1770
    unsigned first, unsigned n)
1771
0
{
1772
0
  if (!dim)
1773
0
    return NULL;
1774
0
  return isl_space_drop_dims(dim, isl_dim_in, first, n);
1775
0
}
1776
1777
__isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1778
    unsigned first, unsigned n)
1779
0
{
1780
0
  if (!dim)
1781
0
    return NULL;
1782
0
  return isl_space_drop_dims(dim, isl_dim_out, first, n);
1783
0
}
1784
1785
__isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
1786
708k
{
1787
708k
  if (!space)
1788
1
    return NULL;
1789
708k
  space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);
1790
708k
  space = isl_space_reverse(space);
1791
708k
  space = mark_as_set(space);
1792
708k
  return space;
1793
708k
}
1794
1795
__isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1796
657k
{
1797
657k
  if (!dim)
1798
2
    return NULL;
1799
657k
  if (!isl_space_is_set(dim))
1800
657k
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1801
657k
      "not a set space", goto error);
1802
657k
  dim = isl_space_reverse(dim);
1803
657k
  dim = isl_space_reset(dim, isl_dim_out);
1804
657k
  return dim;
1805
0
error:
1806
0
  isl_space_free(dim);
1807
0
  return NULL;
1808
657k
}
1809
1810
__isl_give isl_space *isl_space_range(__isl_take isl_space *space)
1811
354k
{
1812
354k
  if (!space)
1813
3
    return NULL;
1814
354k
  space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);
1815
354k
  space = mark_as_set(space);
1816
354k
  return space;
1817
354k
}
1818
1819
__isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1820
199k
{
1821
199k
  if (!dim)
1822
5
    return NULL;
1823
199k
  if (!isl_space_is_set(dim))
1824
199k
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1825
199k
      "not a set space", goto error);
1826
199k
  return isl_space_reset(dim, isl_dim_in);
1827
0
error:
1828
0
  isl_space_free(dim);
1829
0
  return NULL;
1830
199k
}
1831
1832
/* Given a map space A -> B, return the map space [A -> B] -> A.
1833
 */
1834
__isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
1835
1.90k
{
1836
1.90k
  isl_space *domain;
1837
1.90k
1838
1.90k
  domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));
1839
1.90k
  space = isl_space_from_domain(isl_space_wrap(space));
1840
1.90k
  space = isl_space_join(space, domain);
1841
1.90k
1842
1.90k
  return space;
1843
1.90k
}
1844
1845
/* Given a map space A -> B, return the map space [A -> B] -> B.
1846
 */
1847
__isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
1848
16
{
1849
16
  isl_space *range;
1850
16
1851
16
  range = isl_space_from_range(isl_space_range(isl_space_copy(space)));
1852
16
  space = isl_space_from_domain(isl_space_wrap(space));
1853
16
  space = isl_space_join(space, range);
1854
16
1855
16
  return space;
1856
16
}
1857
1858
__isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1859
546k
{
1860
546k
  if (isl_space_is_params(space))
1861
376k
    return space;
1862
170k
  space = isl_space_drop_dims(space,
1863
170k
          isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1864
170k
  space = isl_space_drop_dims(space,
1865
170k
          isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1866
170k
  space = mark_as_params(space);
1867
170k
  return space;
1868
170k
}
1869
1870
__isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1871
17.0k
{
1872
17.0k
  if (!space)
1873
0
    return NULL;
1874
17.0k
  if (!isl_space_is_params(space))
1875
17.0k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1876
17.0k
      "not a parameter space", goto error);
1877
17.0k
  return isl_space_reset(space, isl_dim_set);
1878
0
error:
1879
0
  isl_space_free(space);
1880
0
  return NULL;
1881
17.0k
}
1882
1883
__isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1884
  unsigned n_div)
1885
435k
{
1886
435k
  int i;
1887
435k
1888
435k
  if (!dim)
1889
0
    return NULL;
1890
435k
  if (n_div == 0 &&
1891
435k
      
dim->nparam == 0417k
&&
dim->n_in == 0238k
&&
dim->n_id == 0190k
)
1892
173k
    return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1893
262k
  dim = isl_space_cow(dim);
1894
262k
  if (!dim)
1895
0
    return NULL;
1896
262k
  dim->n_out += dim->nparam + dim->n_in + n_div;
1897
262k
  dim->nparam = 0;
1898
262k
  dim->n_in = 0;
1899
262k
1900
1.34M
  for (i = 0; i < dim->n_id; 
++i1.08M
)
1901
1.08M
    isl_id_free(get_id(dim, isl_dim_out, i));
1902
262k
  dim->n_id = 0;
1903
262k
  dim = isl_space_reset(dim, isl_dim_in);
1904
262k
  dim = isl_space_reset(dim, isl_dim_out);
1905
262k
1906
262k
  return dim;
1907
262k
}
1908
1909
/* Are the two spaces the same, including positions and names of parameters?
1910
 */
1911
isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
1912
  __isl_keep isl_space *space2)
1913
7.76M
{
1914
7.76M
  isl_bool equal;
1915
7.76M
1916
7.76M
  if (!space1 || !space2)
1917
1
    return isl_bool_error;
1918
7.76M
  if (space1 == space2)
1919
4.34M
    return isl_bool_true;
1920
3.41M
  equal = isl_space_has_equal_params(space1, space2);
1921
3.41M
  if (equal < 0 || !equal)
1922
67.2k
    return equal;
1923
3.35M
  return isl_space_has_equal_tuples(space1, space2);
1924
3.35M
}
1925
1926
/* Do the tuples of "space1" correspond to those of the domain of "space2"?
1927
 * That is, is "space1" eqaul to the domain of "space2", ignoring parameters.
1928
 *
1929
 * "space2" is allowed to be a set space, in which case "space1"
1930
 * should be a parameter space.
1931
 */
1932
isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
1933
  __isl_keep isl_space *space2)
1934
106k
{
1935
106k
  isl_bool is_set;
1936
106k
1937
106k
  is_set = isl_space_is_set(space1);
1938
106k
  if (is_set < 0 || !is_set)
1939
0
    return is_set;
1940
106k
  return isl_space_tuple_is_equal(space1, isl_dim_set,
1941
106k
          space2, isl_dim_in);
1942
106k
}
1943
1944
/* Is space1 equal to the domain of space2?
1945
 *
1946
 * In the internal version we also allow space2 to be the space of a set,
1947
 * provided space1 is a parameter space.
1948
 */
1949
isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
1950
  __isl_keep isl_space *space2)
1951
106k
{
1952
106k
  isl_bool equal_params;
1953
106k
1954
106k
  if (!space1 || !space2)
1955
0
    return isl_bool_error;
1956
106k
  equal_params = isl_space_has_equal_params(space1, space2);
1957
106k
  if (equal_params < 0 || !equal_params)
1958
0
    return equal_params;
1959
106k
  return isl_space_has_domain_tuples(space1, space2);
1960
106k
}
1961
1962
/* Is space1 equal to the domain of space2?
1963
 */
1964
isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
1965
  __isl_keep isl_space *space2)
1966
25
{
1967
25
  if (!space2)
1968
0
    return isl_bool_error;
1969
25
  if (!isl_space_is_map(space2))
1970
0
    return isl_bool_false;
1971
25
  return isl_space_is_domain_internal(space1, space2);
1972
25
}
1973
1974
/* Is space1 equal to the range of space2?
1975
 *
1976
 * In the internal version, space2 is allowed to be the space of a set,
1977
 * in which case it should be equal to space1.
1978
 */
1979
isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
1980
  __isl_keep isl_space *space2)
1981
17.3k
{
1982
17.3k
  isl_bool equal_params;
1983
17.3k
1984
17.3k
  if (!space1 || !space2)
1985
0
    return isl_bool_error;
1986
17.3k
  if (!isl_space_is_set(space1))
1987
0
    return isl_bool_false;
1988
17.3k
  equal_params = isl_space_has_equal_params(space1, space2);
1989
17.3k
  if (equal_params < 0 || !equal_params)
1990
0
    return equal_params;
1991
17.3k
  return isl_space_tuple_is_equal(space1, isl_dim_set,
1992
17.3k
          space2, isl_dim_out);
1993
17.3k
}
1994
1995
/* Is space1 equal to the range of space2?
1996
 */
1997
isl_bool isl_space_is_range(__isl_keep isl_space *space1,
1998
  __isl_keep isl_space *space2)
1999
0
{
2000
0
  if (!space2)
2001
0
    return isl_bool_error;
2002
0
  if (!isl_space_is_map(space2))
2003
0
    return isl_bool_false;
2004
0
  return isl_space_is_range_internal(space1, space2);
2005
0
}
2006
2007
/* Update "hash" by hashing in the parameters of "space".
2008
 */
2009
static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2010
547k
{
2011
547k
  int i;
2012
547k
  isl_id *id;
2013
547k
2014
547k
  if (!space)
2015
0
    return hash;
2016
547k
2017
547k
  isl_hash_byte(hash, space->nparam % 256);
2018
547k
2019
1.28M
  for (i = 0; i < space->nparam; 
++i733k
) {
2020
733k
    id = get_id(space, isl_dim_param, i);
2021
733k
    hash = isl_hash_id(hash, id);
2022
733k
  }
2023
547k
2024
547k
  return hash;
2025
547k
}
2026
2027
/* Update "hash" by hashing in the tuples of "space".
2028
 * Changes in this function should be reflected in isl_hash_tuples_domain.
2029
 */
2030
static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2031
2.12M
{
2032
2.12M
  isl_id *id;
2033
2.12M
2034
2.12M
  if (!space)
2035
1.33M
    return hash;
2036
786k
2037
786k
  isl_hash_byte(hash, space->n_in % 256);
2038
786k
  isl_hash_byte(hash, space->n_out % 256);
2039
786k
2040
786k
  id = tuple_id(space, isl_dim_in);
2041
786k
  hash = isl_hash_id(hash, id);
2042
786k
  id = tuple_id(space, isl_dim_out);
2043
786k
  hash = isl_hash_id(hash, id);
2044
786k
2045
786k
  hash = isl_hash_tuples(hash, space->nested[0]);
2046
786k
  hash = isl_hash_tuples(hash, space->nested[1]);
2047
786k
2048
786k
  return hash;
2049
786k
}
2050
2051
/* Update "hash" by hashing in the domain tuple of "space".
2052
 * The result of this function is equal to the result of applying
2053
 * isl_hash_tuples to the domain of "space".
2054
 */
2055
static uint32_t isl_hash_tuples_domain(uint32_t hash,
2056
  __isl_keep isl_space *space)
2057
45.9k
{
2058
45.9k
  isl_id *id;
2059
45.9k
2060
45.9k
  if (!space)
2061
0
    return hash;
2062
45.9k
2063
45.9k
  isl_hash_byte(hash, 0);
2064
45.9k
  isl_hash_byte(hash, space->n_in % 256);
2065
45.9k
2066
45.9k
  hash = isl_hash_id(hash, &isl_id_none);
2067
45.9k
  id = tuple_id(space, isl_dim_in);
2068
45.9k
  hash = isl_hash_id(hash, id);
2069
45.9k
2070
45.9k
  hash = isl_hash_tuples(hash, space->nested[0]);
2071
45.9k
2072
45.9k
  return hash;
2073
45.9k
}
2074
2075
/* Return a hash value that digests the tuples of "space",
2076
 * i.e., that ignores the parameters.
2077
 */
2078
uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2079
2.23k
{
2080
2.23k
  uint32_t hash;
2081
2.23k
2082
2.23k
  if (!space)
2083
0
    return 0;
2084
2.23k
2085
2.23k
  hash = isl_hash_init();
2086
2.23k
  hash = isl_hash_tuples(hash, space);
2087
2.23k
2088
2.23k
  return hash;
2089
2.23k
}
2090
2091
uint32_t isl_space_get_hash(__isl_keep isl_space *space)
2092
501k
{
2093
501k
  uint32_t hash;
2094
501k
2095
501k
  if (!space)
2096
0
    return 0;
2097
501k
2098
501k
  hash = isl_hash_init();
2099
501k
  hash = isl_hash_params(hash, space);
2100
501k
  hash = isl_hash_tuples(hash, space);
2101
501k
2102
501k
  return hash;
2103
501k
}
2104
2105
/* Return the hash value of the domain of "space".
2106
 * That is, isl_space_get_domain_hash(space) is equal to
2107
 * isl_space_get_hash(isl_space_domain(space)).
2108
 */
2109
uint32_t isl_space_get_domain_hash(__isl_keep isl_space *space)
2110
45.9k
{
2111
45.9k
  uint32_t hash;
2112
45.9k
2113
45.9k
  if (!space)
2114
0
    return 0;
2115
45.9k
2116
45.9k
  hash = isl_hash_init();
2117
45.9k
  hash = isl_hash_params(hash, space);
2118
45.9k
  hash = isl_hash_tuples_domain(hash, space);
2119
45.9k
2120
45.9k
  return hash;
2121
45.9k
}
2122
2123
isl_bool isl_space_is_wrapping(__isl_keep isl_space *dim)
2124
57.4k
{
2125
57.4k
  if (!dim)
2126
0
    return isl_bool_error;
2127
57.4k
2128
57.4k
  if (!isl_space_is_set(dim))
2129
0
    return isl_bool_false;
2130
57.4k
2131
57.4k
  return dim->nested[1] != NULL;
2132
57.4k
}
2133
2134
/* Is "space" the space of a map where the domain is a wrapped map space?
2135
 */
2136
isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2137
49.7k
{
2138
49.7k
  if (!space)
2139
0
    return isl_bool_error;
2140
49.7k
2141
49.7k
  if (isl_space_is_set(space))
2142
0
    return isl_bool_false;
2143
49.7k
2144
49.7k
  return space->nested[0] != NULL;
2145
49.7k
}
2146
2147
/* Is "space" the space of a map where the range is a wrapped map space?
2148
 */
2149
isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2150
66.4k
{
2151
66.4k
  if (!space)
2152
0
    return isl_bool_error;
2153
66.4k
2154
66.4k
  if (isl_space_is_set(space))
2155
781
    return isl_bool_false;
2156
65.6k
2157
65.6k
  return space->nested[1] != NULL;
2158
65.6k
}
2159
2160
/* Is "space" a product of two spaces?
2161
 * That is, is it a wrapping set space or a map space
2162
 * with wrapping domain and range?
2163
 */
2164
isl_bool isl_space_is_product(__isl_keep isl_space *space)
2165
6.23k
{
2166
6.23k
  isl_bool is_set;
2167
6.23k
  isl_bool is_product;
2168
6.23k
2169
6.23k
  is_set = isl_space_is_set(space);
2170
6.23k
  if (is_set < 0)
2171
0
    return isl_bool_error;
2172
6.23k
  if (is_set)
2173
0
    return isl_space_is_wrapping(space);
2174
6.23k
  is_product = isl_space_domain_is_wrapping(space);
2175
6.23k
  if (is_product < 0 || !is_product)
2176
35
    return is_product;
2177
6.20k
  return isl_space_range_is_wrapping(space);
2178
6.20k
}
2179
2180
__isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
2181
207k
{
2182
207k
  isl_space *wrap;
2183
207k
2184
207k
  if (!dim)
2185
1
    return NULL;
2186
207k
2187
207k
  wrap = isl_space_set_alloc(dim->ctx,
2188
207k
            dim->nparam, dim->n_in + dim->n_out);
2189
207k
2190
207k
  wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
2191
207k
  wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
2192
207k
  wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
2193
207k
2194
207k
  if (!wrap)
2195
0
    goto error;
2196
207k
2197
207k
  wrap->nested[1] = dim;
2198
207k
2199
207k
  return wrap;
2200
0
error:
2201
0
  isl_space_free(dim);
2202
0
  return NULL;
2203
207k
}
2204
2205
__isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
2206
39.7k
{
2207
39.7k
  isl_space *unwrap;
2208
39.7k
2209
39.7k
  if (!dim)
2210
1
    return NULL;
2211
39.7k
2212
39.7k
  if (!isl_space_is_wrapping(dim))
2213
39.7k
    
isl_die0
(dim->ctx, isl_error_invalid, "not a wrapping space",
2214
39.7k
      goto error);
2215
39.7k
2216
39.7k
  unwrap = isl_space_copy(dim->nested[1]);
2217
39.7k
  isl_space_free(dim);
2218
39.7k
2219
39.7k
  return unwrap;
2220
0
error:
2221
0
  isl_space_free(dim);
2222
0
  return NULL;
2223
39.7k
}
2224
2225
isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2226
  enum isl_dim_type type)
2227
5.49M
{
2228
5.49M
  if (type != isl_dim_in && 
type != isl_dim_out3.96M
)
2229
207k
    return isl_bool_false;
2230
5.28M
  if (!space)
2231
9
    return isl_bool_error;
2232
5.28M
  if (space->tuple_id[type - isl_dim_in])
2233
2.21M
    return isl_bool_true;
2234
3.06M
  if (space->nested[type - isl_dim_in])
2235
774k
    return isl_bool_true;
2236
2.29M
  return isl_bool_false;
2237
2.29M
}
2238
2239
isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2240
278
{
2241
278
  isl_bool nested;
2242
278
2243
278
  if (!space)
2244
0
    return isl_bool_error;
2245
278
  if (isl_space_is_set(space))
2246
173
    return isl_bool_true;
2247
105
  if (isl_space_dim(space, isl_dim_in) != 0)
2248
0
    return isl_bool_false;
2249
105
  nested = isl_space_is_named_or_nested(space, isl_dim_in);
2250
105
  if (nested < 0 || nested)
2251
0
    return isl_bool_not(nested);
2252
105
  return isl_bool_true;
2253
105
}
2254
2255
__isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
2256
  enum isl_dim_type type)
2257
5.00M
{
2258
5.00M
  if (!isl_space_is_named_or_nested(dim, type))
2259
2.24M
    return dim;
2260
2.76M
2261
2.76M
  dim = isl_space_cow(dim);
2262
2.76M
  if (!dim)
2263
19
    return NULL;
2264
2.76M
2265
2.76M
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
2266
2.76M
  dim->tuple_id[type - isl_dim_in] = NULL;
2267
2.76M
  isl_space_free(dim->nested[type - isl_dim_in]);
2268
2.76M
  dim->nested[type - isl_dim_in] = NULL;
2269
2.76M
2270
2.76M
  return dim;
2271
2.76M
}
2272
2273
__isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
2274
22.8k
{
2275
22.8k
  if (!dim)
2276
0
    return NULL;
2277
22.8k
  if (!dim->nested[0] && !dim->nested[1])
2278
0
    return dim;
2279
22.8k
2280
22.8k
  if (dim->nested[0])
2281
0
    dim = isl_space_reset(dim, isl_dim_in);
2282
22.8k
  if (dim && dim->nested[1])
2283
22.8k
    dim = isl_space_reset(dim, isl_dim_out);
2284
22.8k
2285
22.8k
  return dim;
2286
22.8k
}
2287
2288
__isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2289
34
{
2290
34
  if (!space)
2291
0
    return NULL;
2292
34
  if (!space->nested[0])
2293
0
    return space;
2294
34
2295
34
  return isl_space_reset(space, isl_dim_in);
2296
34
}
2297
2298
__isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2299
75.6k
{
2300
75.6k
  if (!space)
2301
0
    return NULL;
2302
75.6k
  if (!space->nested[1])
2303
0
    return space;
2304
75.6k
2305
75.6k
  return isl_space_reset(space, isl_dim_out);
2306
75.6k
}
2307
2308
/* Replace the parameters of dst by those of src.
2309
 */
2310
__isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2311
  __isl_keep isl_space *src)
2312
123k
{
2313
123k
  isl_bool equal_params;
2314
123k
  enum isl_dim_type type = isl_dim_param;
2315
123k
2316
123k
  equal_params = isl_space_has_equal_params(dst, src);
2317
123k
  if (equal_params < 0)
2318
0
    return isl_space_free(dst);
2319
123k
  if (equal_params)
2320
57.8k
    return dst;
2321
65.7k
2322
65.7k
  dst = isl_space_cow(dst);
2323
65.7k
2324
65.7k
  if (!dst || !src)
2325
0
    goto error;
2326
65.7k
2327
65.7k
  dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
2328
65.7k
  dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
2329
65.7k
  dst = copy_ids(dst, type, 0, src, type);
2330
65.7k
2331
65.7k
  if (dst) {
2332
65.7k
    int i;
2333
197k
    for (i = 0; i <= 1; 
++i131k
) {
2334
131k
      if (!dst->nested[i])
2335
131k
        continue;
2336
463
      dst->nested[i] = isl_space_replace_params(
2337
463
              dst->nested[i], src);
2338
463
      if (!dst->nested[i])
2339
0
        goto error;
2340
463
    }
2341
65.7k
  }
2342
65.7k
2343
65.7k
  return dst;
2344
0
error:
2345
0
  isl_space_free(dst);
2346
0
  return NULL;
2347
65.7k
}
2348
2349
/* Given a dimension specification "dim" of a set, create a dimension
2350
 * specification for the lift of the set.  In particular, the result
2351
 * is of the form [dim -> local[..]], with n_local variables in the
2352
 * range of the wrapped map.
2353
 */
2354
__isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
2355
20.5k
{
2356
20.5k
  isl_space *local_dim;
2357
20.5k
2358
20.5k
  if (!dim)
2359
0
    return NULL;
2360
20.5k
2361
20.5k
  local_dim = isl_space_dup(dim);
2362
20.5k
  local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
2363
20.5k
  local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
2364
20.5k
  local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
2365
20.5k
  dim = isl_space_join(isl_space_from_domain(dim),
2366
20.5k
          isl_space_from_range(local_dim));
2367
20.5k
  dim = isl_space_wrap(dim);
2368
20.5k
  dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
2369
20.5k
2370
20.5k
  return dim;
2371
20.5k
}
2372
2373
isl_bool isl_space_can_zip(__isl_keep isl_space *space)
2374
6.14k
{
2375
6.14k
  isl_bool is_set;
2376
6.14k
2377
6.14k
  is_set = isl_space_is_set(space);
2378
6.14k
  if (is_set < 0)
2379
0
    return isl_bool_error;
2380
6.14k
  if (is_set)
2381
0
    return isl_bool_false;
2382
6.14k
  return isl_space_is_product(space);
2383
6.14k
}
2384
2385
__isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
2386
2.63k
{
2387
2.63k
  isl_space *dom, *ran;
2388
2.63k
  isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
2389
2.63k
2390
2.63k
  if (!isl_space_can_zip(dim))
2391
2.63k
    
isl_die0
(dim->ctx, isl_error_invalid, "dim cannot be zipped",
2392
2.63k
      goto error);
2393
2.63k
2394
2.63k
  if (!dim)
2395
0
    return NULL;
2396
2.63k
  dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
2397
2.63k
  ran = isl_space_unwrap(isl_space_range(dim));
2398
2.63k
  dom_dom = isl_space_domain(isl_space_copy(dom));
2399
2.63k
  dom_ran = isl_space_range(dom);
2400
2.63k
  ran_dom = isl_space_domain(isl_space_copy(ran));
2401
2.63k
  ran_ran = isl_space_range(ran);
2402
2.63k
  dom = isl_space_join(isl_space_from_domain(dom_dom),
2403
2.63k
         isl_space_from_range(ran_dom));
2404
2.63k
  ran = isl_space_join(isl_space_from_domain(dom_ran),
2405
2.63k
         isl_space_from_range(ran_ran));
2406
2.63k
  return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2407
2.63k
          isl_space_from_range(isl_space_wrap(ran)));
2408
0
error:
2409
0
  isl_space_free(dim);
2410
0
  return NULL;
2411
2.63k
}
2412
2413
/* Can we apply isl_space_curry to "space"?
2414
 * That is, does it have a nested relation in its domain?
2415
 */
2416
isl_bool isl_space_can_curry(__isl_keep isl_space *space)
2417
41.0k
{
2418
41.0k
  if (!space)
2419
0
    return isl_bool_error;
2420
41.0k
2421
41.0k
  return !!space->nested[0];
2422
41.0k
}
2423
2424
/* Given a space (A -> B) -> C, return the corresponding space
2425
 * A -> (B -> C).
2426
 */
2427
__isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
2428
13.3k
{
2429
13.3k
  isl_space *dom, *ran;
2430
13.3k
  isl_space *dom_dom, *dom_ran;
2431
13.3k
2432
13.3k
  if (!space)
2433
0
    return NULL;
2434
13.3k
2435
13.3k
  if (!isl_space_can_curry(space))
2436
13.3k
    
isl_die0
(space->ctx, isl_error_invalid,
2437
13.3k
      "space cannot be curried", goto error);
2438
13.3k
2439
13.3k
  dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
2440
13.3k
  ran = isl_space_range(space);
2441
13.3k
  dom_dom = isl_space_domain(isl_space_copy(dom));
2442
13.3k
  dom_ran = isl_space_range(dom);
2443
13.3k
  ran = isl_space_join(isl_space_from_domain(dom_ran),
2444
13.3k
         isl_space_from_range(ran));
2445
13.3k
  return isl_space_join(isl_space_from_domain(dom_dom),
2446
13.3k
          isl_space_from_range(isl_space_wrap(ran)));
2447
0
error:
2448
0
  isl_space_free(space);
2449
0
  return NULL;
2450
13.3k
}
2451
2452
/* Can isl_space_range_curry be applied to "space"?
2453
 * That is, does it have a nested relation in its range,
2454
 * the domain of which is itself a nested relation?
2455
 */
2456
isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
2457
25.3k
{
2458
25.3k
  isl_bool can;
2459
25.3k
2460
25.3k
  if (!space)
2461
0
    return isl_bool_error;
2462
25.3k
  can = isl_space_range_is_wrapping(space);
2463
25.3k
  if (can < 0 || !can)
2464
0
    return can;
2465
25.3k
  return isl_space_can_curry(space->nested[1]);
2466
25.3k
}
2467
2468
/* Given a space A -> ((B -> C) -> D), return the corresponding space
2469
 * A -> (B -> (C -> D)).
2470
 */
2471
__isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
2472
12.6k
{
2473
12.6k
  if (!space)
2474
0
    return NULL;
2475
12.6k
2476
12.6k
  if (!isl_space_can_range_curry(space))
2477
12.6k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
2478
12.6k
      "space range cannot be curried",
2479
12.6k
      return isl_space_free(space));
2480
12.6k
2481
12.6k
  space = isl_space_cow(space);
2482
12.6k
  if (!space)
2483
0
    return NULL;
2484
12.6k
  space->nested[1] = isl_space_curry(space->nested[1]);
2485
12.6k
  if (!space->nested[1])
2486
0
    return isl_space_free(space);
2487
12.6k
2488
12.6k
  return space;
2489
12.6k
}
2490
2491
/* Can we apply isl_space_uncurry to "space"?
2492
 * That is, does it have a nested relation in its range?
2493
 */
2494
isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
2495
1.60k
{
2496
1.60k
  if (!space)
2497
0
    return isl_bool_error;
2498
1.60k
2499
1.60k
  return !!space->nested[1];
2500
1.60k
}
2501
2502
/* Given a space A -> (B -> C), return the corresponding space
2503
 * (A -> B) -> C.
2504
 */
2505
__isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
2506
562
{
2507
562
  isl_space *dom, *ran;
2508
562
  isl_space *ran_dom, *ran_ran;
2509
562
2510
562
  if (!space)
2511
0
    return NULL;
2512
562
2513
562
  if (!isl_space_can_uncurry(space))
2514
562
    
isl_die0
(space->ctx, isl_error_invalid,
2515
562
      "space cannot be uncurried",
2516
562
      return isl_space_free(space));
2517
562
2518
562
  dom = isl_space_domain(isl_space_copy(space));
2519
562
  ran = isl_space_unwrap(isl_space_range(space));
2520
562
  ran_dom = isl_space_domain(isl_space_copy(ran));
2521
562
  ran_ran = isl_space_range(ran);
2522
562
  dom = isl_space_join(isl_space_from_domain(dom),
2523
562
         isl_space_from_range(ran_dom));
2524
562
  return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2525
562
          isl_space_from_range(ran_ran));
2526
562
}
2527
2528
isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
2529
523k
{
2530
523k
  int i;
2531
523k
  unsigned off;
2532
523k
2533
523k
  if (!space)
2534
2
    return isl_bool_error;
2535
523k
  if (space->nparam == 0)
2536
253k
    return isl_bool_true;
2537
270k
  off = isl_space_offset(space, isl_dim_param);
2538
270k
  if (off + space->nparam > space->n_id)
2539
0
    return isl_bool_false;
2540
1.09M
  
for (i = 0; 270k
i < space->nparam;
++i820k
)
2541
820k
    if (!space->ids[off + i])
2542
0
      return isl_bool_false;
2543
270k
  return isl_bool_true;
2544
270k
}
2545
2546
/* Check that "space" has only named parameters, reporting an error
2547
 * if it does not.
2548
 */
2549
isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
2550
336k
{
2551
336k
  isl_bool named;
2552
336k
2553
336k
  named = isl_space_has_named_params(space);
2554
336k
  if (named < 0)
2555
2
    return isl_stat_error;
2556
336k
  if (!named)
2557
336k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
2558
336k
      "unexpected unnamed parameters", return isl_stat_error);
2559
336k
2560
336k
  return isl_stat_ok;
2561
336k
}
2562
2563
/* Align the initial parameters of space1 to match the order in space2.
2564
 */
2565
__isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
2566
  __isl_take isl_space *space2)
2567
35.3k
{
2568
35.3k
  isl_reordering *exp;
2569
35.3k
2570
35.3k
  if (isl_space_check_named_params(space1) < 0 ||
2571
35.3k
      
isl_space_check_named_params(space2) < 035.3k
)
2572
2
    goto error;
2573
35.3k
2574
35.3k
  exp = isl_parameter_alignment_reordering(space1, space2);
2575
35.3k
  exp = isl_reordering_extend_space(exp, space1);
2576
35.3k
  isl_space_free(space2);
2577
35.3k
  space1 = isl_reordering_get_space(exp);
2578
35.3k
  isl_reordering_free(exp);
2579
35.3k
  return space1;
2580
2
error:
2581
2
  isl_space_free(space1);
2582
2
  isl_space_free(space2);
2583
2
  return NULL;
2584
35.3k
}
2585
2586
/* Given the space of set (domain), construct a space for a map
2587
 * with as domain the given space and as range the range of "model".
2588
 */
2589
__isl_give isl_space *isl_space_extend_domain_with_range(
2590
  __isl_take isl_space *space, __isl_take isl_space *model)
2591
73.3k
{
2592
73.3k
  if (!model)
2593
0
    goto error;
2594
73.3k
2595
73.3k
  space = isl_space_from_domain(space);
2596
73.3k
  space = isl_space_add_dims(space, isl_dim_out,
2597
73.3k
            isl_space_dim(model, isl_dim_out));
2598
73.3k
  if (isl_space_has_tuple_id(model, isl_dim_out))
2599
125
    space = isl_space_set_tuple_id(space, isl_dim_out,
2600
125
        isl_space_get_tuple_id(model, isl_dim_out));
2601
73.3k
  if (!space)
2602
0
    goto error;
2603
73.3k
  if (model->nested[1]) {
2604
1
    isl_space *nested = isl_space_copy(model->nested[1]);
2605
1
    int n_nested, n_space;
2606
1
    nested = isl_space_align_params(nested, isl_space_copy(space));
2607
1
    n_nested = isl_space_dim(nested, isl_dim_param);
2608
1
    n_space = isl_space_dim(space, isl_dim_param);
2609
1
    if (n_nested > n_space)
2610
0
      nested = isl_space_drop_dims(nested, isl_dim_param,
2611
0
            n_space, n_nested - n_space);
2612
1
    if (!nested)
2613
0
      goto error;
2614
1
    space->nested[1] = nested;
2615
1
  }
2616
73.3k
  isl_space_free(model);
2617
73.3k
  return space;
2618
0
error:
2619
0
  isl_space_free(model);
2620
0
  isl_space_free(space);
2621
0
  return NULL;
2622
73.3k
}
2623
2624
/* Compare the "type" dimensions of two isl_spaces.
2625
 *
2626
 * The order is fairly arbitrary.
2627
 */
2628
static int isl_space_cmp_type(__isl_keep isl_space *space1,
2629
  __isl_keep isl_space *space2, enum isl_dim_type type)
2630
1.87M
{
2631
1.87M
  int cmp;
2632
1.87M
  isl_space *nested1, *nested2;
2633
1.87M
2634
1.87M
  if (isl_space_dim(space1, type) != isl_space_dim(space2, type))
2635
0
    return isl_space_dim(space1, type) -
2636
0
      isl_space_dim(space2, type);
2637
1.87M
2638
1.87M
  cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));
2639
1.87M
  if (cmp != 0)
2640
0
    return cmp;
2641
1.87M
2642
1.87M
  nested1 = nested(space1, type);
2643
1.87M
  nested2 = nested(space2, type);
2644
1.87M
  if (!nested1 != !nested2)
2645
0
    return !nested1 - !nested2;
2646
1.87M
2647
1.87M
  if (nested1)
2648
237k
    return isl_space_cmp(nested1, nested2);
2649
1.64M
2650
1.64M
  return 0;
2651
1.64M
}
2652
2653
/* Compare two isl_spaces.
2654
 *
2655
 * The order is fairly arbitrary.
2656
 */
2657
int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
2658
1.82M
{
2659
1.82M
  int i;
2660
1.82M
  int cmp;
2661
1.82M
2662
1.82M
  if (space1 == space2)
2663
1.20M
    return 0;
2664
626k
  if (!space1)
2665
0
    return -1;
2666
626k
  if (!space2)
2667
0
    return 1;
2668
626k
2669
626k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_param);
2670
626k
  if (cmp != 0)
2671
0
    return cmp;
2672
626k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_in);
2673
626k
  if (cmp != 0)
2674
0
    return cmp;
2675
626k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_out);
2676
626k
  if (cmp != 0)
2677
0
    return cmp;
2678
626k
2679
626k
  if (!space1->ids && 
!space2->ids198k
)
2680
198k
    return 0;
2681
427k
2682
3.87M
  
for (i = 0; 427k
i < n(space1, isl_dim_param);
++i3.44M
) {
2683
3.44M
    cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),
2684
3.44M
         get_id(space2, isl_dim_param, i));
2685
3.44M
    if (cmp != 0)
2686
0
      return cmp;
2687
3.44M
  }
2688
427k
2689
427k
  return 0;
2690
427k
}