Coverage Report

Created: 2018-04-23 18:20

/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.39M
{
23
1.39M
  return dim ? dim->ctx : NULL;
24
1.39M
}
25
26
__isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
27
      unsigned nparam, unsigned n_in, unsigned n_out)
28
5.05M
{
29
5.05M
  isl_space *dim;
30
5.05M
31
5.05M
  dim = isl_alloc_type(ctx, struct isl_space);
32
5.05M
  if (!dim)
33
8
    return NULL;
34
5.05M
35
5.05M
  dim->ctx = ctx;
36
5.05M
  isl_ctx_ref(ctx);
37
5.05M
  dim->ref = 1;
38
5.05M
  dim->nparam = nparam;
39
5.05M
  dim->n_in = n_in;
40
5.05M
  dim->n_out = n_out;
41
5.05M
42
5.05M
  dim->tuple_id[0] = NULL;
43
5.05M
  dim->tuple_id[1] = NULL;
44
5.05M
45
5.05M
  dim->nested[0] = NULL;
46
5.05M
  dim->nested[1] = NULL;
47
5.05M
48
5.05M
  dim->n_id = 0;
49
5.05M
  dim->ids = NULL;
50
5.05M
51
5.05M
  return dim;
52
5.05M
}
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.60M
{
59
1.60M
  space = isl_space_cow(space);
60
1.60M
  if (!space)
61
0
    return NULL;
62
1.60M
  space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
63
1.60M
  return space;
64
1.60M
}
65
66
/* Is the space that of a set?
67
 */
68
isl_bool isl_space_is_set(__isl_keep isl_space *space)
69
1.76M
{
70
1.76M
  if (!space)
71
0
    return isl_bool_error;
72
1.76M
  if (space->n_in != 0 || 
space->nested[0]1.47M
)
73
304k
    return isl_bool_false;
74
1.46M
  if (space->tuple_id[0] != &isl_id_none)
75
16.9k
    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_none806
;
87
30.3k
}
88
89
__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
90
      unsigned nparam, unsigned dim)
91
548k
{
92
548k
  isl_space *space;
93
548k
  space = isl_space_alloc(ctx, nparam, 0, dim);
94
548k
  space = mark_as_set(space);
95
548k
  return space;
96
548k
}
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
141k
{
103
141k
  if (!space)
104
0
    return NULL;
105
141k
  space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);
106
141k
  space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);
107
141k
  return space;
108
141k
}
109
110
/* Is the space that of a parameter domain?
111
 */
112
isl_bool isl_space_is_params(__isl_keep isl_space *space)
113
687k
{
114
687k
  if (!space)
115
22
    return isl_bool_error;
116
687k
  if (space->n_in != 0 || 
space->nested[0]566k
||
117
687k
      
space->n_out != 0565k
||
space->nested[1]439k
)
118
248k
    return isl_bool_false;
119
438k
  if (space->tuple_id[0] != &isl_id_none)
120
23.8k
    return isl_bool_false;
121
415k
  if (space->tuple_id[1] != &isl_id_none)
122
34.3k
    return isl_bool_false;
123
380k
  return isl_bool_true;
124
380k
}
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
50.1M
{
139
50.1M
  struct isl_ctx *ctx = dim->ctx;
140
50.1M
141
50.1M
  switch (type) {
142
50.1M
  case isl_dim_param:
143
33.2M
    isl_assert(ctx, pos < dim->nparam,
144
33.2M
          return isl_space_dim(dim, isl_dim_all));
145
33.2M
    return pos;
146
33.2M
  case isl_dim_in:
147
6.48M
    isl_assert(ctx, pos < dim->n_in,
148
6.48M
          return isl_space_dim(dim, isl_dim_all));
149
6.48M
    return pos + dim->nparam;
150
10.4M
  case isl_dim_out:
151
10.4M
    isl_assert(ctx, pos < dim->n_out,
152
10.4M
          return isl_space_dim(dim, isl_dim_all));
153
10.4M
    return pos + dim->nparam + dim->n_in;
154
10.4M
  default:
155
0
    isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));
156
50.1M
  }
157
50.1M
  
return isl_space_dim(dim, isl_dim_all)0
;
158
50.1M
}
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.18M
{
164
2.18M
  isl_id **ids;
165
2.18M
  int i;
166
2.18M
167
2.18M
  if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)
168
517k
    return dim;
169
1.66M
170
1.66M
  if (!dim->ids) {
171
1.66M
    dim->ids = isl_calloc_array(dim->ctx,
172
1.66M
        isl_id *, isl_space_dim(dim, isl_dim_all));
173
1.66M
    if (!dim->ids)
174
0
      goto error;
175
585
  } else {
176
585
    ids = isl_realloc_array(dim->ctx, dim->ids,
177
585
        isl_id *, isl_space_dim(dim, isl_dim_all));
178
585
    if (!ids)
179
0
      goto error;
180
585
    dim->ids = ids;
181
3.03k
    for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); 
++i2.45k
)
182
2.45k
      dim->ids[i] = NULL;
183
585
  }
184
1.66M
185
1.66M
  dim->n_id = isl_space_dim(dim, isl_dim_all);
186
1.66M
187
1.66M
  return dim;
188
0
error:
189
0
  isl_space_free(dim);
190
0
  return NULL;
191
1.66M
}
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.80M
{
196
6.80M
  dim = isl_space_cow(dim);
197
6.80M
198
6.80M
  if (!dim)
199
0
    goto error;
200
6.80M
201
6.80M
  pos = global_pos(dim, type, pos);
202
6.80M
  if (pos == isl_space_dim(dim, isl_dim_all))
203
0
    goto error;
204
6.80M
205
6.80M
  if (pos >= dim->n_id) {
206
1.66M
    if (!id)
207
0
      return dim;
208
1.66M
    dim = extend_ids(dim);
209
1.66M
    if (!dim)
210
0
      goto error;
211
6.80M
  }
212
6.80M
213
6.80M
  dim->ids[pos] = id;
214
6.80M
215
6.80M
  return dim;
216
0
error:
217
0
  isl_id_free(id);
218
0
  isl_space_free(dim);
219
0
  return NULL;
220
6.80M
}
221
222
static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,
223
         enum isl_dim_type type, unsigned pos)
224
43.3M
{
225
43.3M
  if (!dim)
226
0
    return NULL;
227
43.3M
228
43.3M
  pos = global_pos(dim, type, pos);
229
43.3M
  if (pos == isl_space_dim(dim, isl_dim_all))
230
0
    return NULL;
231
43.3M
  if (pos >= dim->n_id)
232
3.14M
    return NULL;
233
40.2M
  return dim->ids[pos];
234
40.2M
}
235
236
static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)
237
2.14M
{
238
2.14M
  switch (type) {
239
2.14M
  
case isl_dim_param: return 0695k
;
240
2.14M
  
case isl_dim_in:  return dim->nparam491k
;
241
2.14M
  
case isl_dim_out: return dim->nparam + dim->n_in954k
;
242
2.14M
  
default:    return 00
;
243
0
  }
244
0
}
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->nparam53.4M
;
250
278M
  
case isl_dim_in:  return dim->n_in34.7M
;
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_out150M
;
253
278M
  
default:    return 00
;
254
0
  }
255
0
}
256
257
unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)
258
200M
{
259
200M
  if (!dim)
260
4
    return 0;
261
200M
  return n(dim, type);
262
200M
}
263
264
unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)
265
1.94M
{
266
1.94M
  if (!dim)
267
0
    return 0;
268
1.94M
  return offset(dim, type);
269
1.94M
}
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.2M
  
for (i = 0; 6.71M
i < n(src, src_type);
++i11.5M
) {
282
11.5M
    id = get_id(src, src_type, i);
283
11.5M
    if (!id)
284
6.82M
      continue;
285
4.68M
    dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));
286
4.68M
    if (!dst)
287
0
      return NULL;
288
4.68M
  }
289
6.71M
  return dst;
290
6.71M
}
291
292
__isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)
293
3.77M
{
294
3.77M
  isl_space *dup;
295
3.77M
  if (!dim)
296
0
    return NULL;
297
3.77M
  dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);
298
3.77M
  if (!dup)
299
8
    return NULL;
300
3.77M
  if (dim->tuple_id[0] &&
301
3.77M
      
!(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0]))2.15M
)
302
0
    goto error;
303
3.77M
  if (dim->tuple_id[1] &&
304
3.77M
      
!(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1]))891k
)
305
0
    goto error;
306
3.77M
  if (dim->nested[0] && 
!(dup->nested[0] = isl_space_copy(dim->nested[0]))712k
)
307
0
    goto error;
308
3.77M
  if (dim->nested[1] && 
!(dup->nested[1] = isl_space_copy(dim->nested[1]))931k
)
309
0
    goto error;
310
3.77M
  if (!dim->ids)
311
2.31M
    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.5M
{
323
18.5M
  if (!dim)
324
8
    return NULL;
325
18.5M
326
18.5M
  if (dim->ref == 1)
327
14.8M
    return dim;
328
3.75M
  dim->ref--;
329
3.75M
  return isl_space_dup(dim);
330
3.75M
}
331
332
__isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)
333
16.7M
{
334
16.7M
  if (!dim)
335
8.89k
    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.6M
{
343
29.6M
  int i;
344
29.6M
345
29.6M
  if (!space)
346
11.5M
    return NULL;
347
18.0M
348
18.0M
  if (--space->ref > 0)
349
12.9M
    return NULL;
350
5.05M
351
5.05M
  isl_id_free(space->tuple_id[0]);
352
5.05M
  isl_id_free(space->tuple_id[1]);
353
5.05M
354
5.05M
  isl_space_free(space->nested[0]);
355
5.05M
  isl_space_free(space->nested[1]);
356
5.05M
357
11.7M
  for (i = 0; i < space->n_id; 
++i6.65M
)
358
6.65M
    isl_id_free(space->ids[i]);
359
5.05M
  free(space->ids);
360
5.05M
  isl_ctx_deref(space->ctx);
361
5.05M
  
362
5.05M
  free(space);
363
5.05M
364
5.05M
  return NULL;
365
5.05M
}
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.8k
{
374
55.8k
  char *p;
375
55.8k
  long dummy;
376
55.8k
377
55.8k
  dummy = strtol(s, &p, 0);
378
55.8k
  if (p != s)
379
55.8k
    
isl_die0
(ctx, isl_error_invalid, "name looks like a number",
380
55.8k
      return 0);
381
55.8k
382
55.8k
  return 1;
383
55.8k
}
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_set31.0k
)
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.1k
{
419
38.1k
  int has_id;
420
38.1k
421
38.1k
  if (!dim)
422
0
    return NULL;
423
38.1k
  has_id = isl_space_has_tuple_id(dim, type);
424
38.1k
  if (has_id < 0)
425
0
    return NULL;
426
38.1k
  if (!has_id)
427
38.1k
    
isl_die0
(dim->ctx, isl_error_invalid,
428
38.1k
      "tuple has no id", return NULL);
429
38.1k
  return isl_id_copy(dim->tuple_id[type - isl_dim_in]);
430
38.1k
}
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
1.95M
{
435
1.95M
  dim = isl_space_cow(dim);
436
1.95M
  if (!dim || !id)
437
0
    goto error;
438
1.95M
  if (type != isl_dim_in && 
type != isl_dim_out205k
)
439
1.95M
    
isl_die0
(dim->ctx, isl_error_invalid,
440
1.95M
      "only input, output and set tuples can have names",
441
1.95M
      goto error);
442
1.95M
443
1.95M
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
444
1.95M
  dim->tuple_id[type - isl_dim_in] = id;
445
1.95M
446
1.95M
  return dim;
447
0
error:
448
0
  isl_id_free(id);
449
0
  isl_space_free(dim);
450
0
  return NULL;
451
1.95M
}
452
453
__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,
454
  enum isl_dim_type type)
455
5.93k
{
456
5.93k
  dim = isl_space_cow(dim);
457
5.93k
  if (!dim)
458
0
    return NULL;
459
5.93k
  if (type != isl_dim_in && type != isl_dim_out)
460
5.93k
    
isl_die0
(dim->ctx, isl_error_invalid,
461
5.93k
      "only input, output and set tuples can have names",
462
5.93k
      goto error);
463
5.93k
464
5.93k
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
465
5.93k
  dim->tuple_id[type - isl_dim_in] = NULL;
466
5.93k
467
5.93k
  return dim;
468
0
error:
469
0
  isl_space_free(dim);
470
0
  return NULL;
471
5.93k
}
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.5k
{
481
82.5k
  space = isl_space_cow(space);
482
82.5k
  if (!space || !id)
483
0
    goto error;
484
82.5k
485
82.5k
  if (type == isl_dim_param) {
486
61.2k
    int i;
487
61.2k
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.2k
  }
498
82.5k
499
82.5k
  isl_id_free(get_id(space, type, pos));
500
82.5k
  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.5k
}
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.12k
{
543
1.12k
  if (!dim)
544
0
    return isl_bool_error;
545
1.12k
  return get_id(dim, type, pos) != NULL;
546
1.12k
}
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
780k
{
551
780k
  if (!dim)
552
0
    return NULL;
553
780k
  if (!get_id(dim, type, pos))
554
780k
    
isl_die0
(dim->ctx, isl_error_invalid,
555
780k
      "dim has no id", return NULL);
556
780k
  return isl_id_copy(get_id(dim, type, pos));
557
780k
}
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
49.3k
{
562
49.3k
  isl_id *id;
563
49.3k
564
49.3k
  if (!dim)
565
0
    return NULL;
566
49.3k
567
49.3k
  if (!s)
568
0
    return isl_space_reset_tuple_id(dim, type);
569
49.3k
570
49.3k
  if (!name_ok(dim->ctx, s))
571
0
    goto error;
572
49.3k
573
49.3k
  id = isl_id_alloc(dim->ctx, s, NULL);
574
49.3k
  return isl_space_set_tuple_id(dim, type, id);
575
0
error:
576
0
  isl_space_free(dim);
577
0
  return NULL;
578
49.3k
}
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.05k
{
585
1.05k
  isl_id *id;
586
1.05k
587
1.05k
  if (!space_can_have_id(space, type))
588
0
    return isl_bool_error;
589
1.05k
  id = space->tuple_id[type - isl_dim_in];
590
1.05k
  return id && 
id->name180
;
591
1.05k
}
592
593
__isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,
594
   enum isl_dim_type type)
595
10.9k
{
596
10.9k
  isl_id *id;
597
10.9k
  if (!dim)
598
0
    return NULL;
599
10.9k
  if (type != isl_dim_in && 
type != isl_dim_out6.44k
)
600
0
    return NULL;
601
10.9k
  id = dim->tuple_id[type - isl_dim_in];
602
10.9k
  return id ? 
id->name9.42k
: NULL;
603
10.9k
}
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.51k
{
609
6.51k
  isl_id *id;
610
6.51k
611
6.51k
  if (!dim)
612
0
    return NULL;
613
6.51k
  if (!s)
614
0
    return isl_space_reset_dim_id(dim, type, pos);
615
6.51k
  if (!name_ok(dim->ctx, s))
616
0
    goto error;
617
6.51k
  id = isl_id_alloc(dim->ctx, s, NULL);
618
6.51k
  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.51k
}
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.67k
{
629
6.67k
  isl_id *id;
630
6.67k
631
6.67k
  if (!space)
632
0
    return isl_bool_error;
633
6.67k
  id = get_id(space, type, pos);
634
6.67k
  return id && 
id->name1.00k
;
635
6.67k
}
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
388
{
647
388
  int i;
648
388
  int offset;
649
388
  int n;
650
388
651
388
  if (!dim || !id)
652
0
    return -1;
653
388
654
388
  offset = isl_space_offset(dim, type);
655
388
  n = isl_space_dim(dim, type);
656
512
  for (i = 0; i < n && 
offset + i < dim->n_id510
;
++i124
)
657
510
    if (dim->ids[offset + i] == id)
658
386
      return i;
659
388
660
388
  
return -12
;
661
388
}
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
43.1M
{
746
43.1M
  if (!dim)
747
0
    return NULL;
748
43.1M
  if (type == isl_dim_in)
749
13.4M
    return dim->tuple_id[0];
750
29.7M
  if (type == isl_dim_out)
751
12.2M
    return dim->tuple_id[1];
752
17.5M
  return NULL;
753
17.5M
}
754
755
static __isl_keep isl_space *nested(__isl_keep isl_space *dim,
756
  enum isl_dim_type type)
757
40.0M
{
758
40.0M
  if (!dim)
759
0
    return NULL;
760
40.0M
  if (type == isl_dim_in)
761
11.4M
    return dim->nested[0];
762
28.5M
  if (type == isl_dim_out)
763
11.0M
    return dim->nested[1];
764
17.5M
  return NULL;
765
17.5M
}
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.82M
{
772
6.82M
  if (!space1 || !space2)
773
0
    return isl_bool_error;
774
6.82M
  if (space1 == space2)
775
2.21M
    return isl_bool_true;
776
4.60M
  return isl_space_tuple_is_equal(space1, isl_dim_in,
777
4.60M
          space2, isl_dim_in) &&
778
4.60M
         isl_space_tuple_is_equal(space1, isl_dim_out,
779
3.96M
          space2, isl_dim_out);
780
4.60M
}
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.5M
{
798
21.5M
  isl_id *id1, *id2;
799
21.5M
  isl_space *nested1, *nested2;
800
21.5M
801
21.5M
  if (!space1 || !space2)
802
0
    return isl_bool_error;
803
21.5M
804
21.5M
  if (space1 == space2 && 
type1 == type21.95M
)
805
6.52k
    return isl_bool_true;
806
21.5M
807
21.5M
  if (n(space1, type1) != n(space2, type2))
808
2.18M
    return isl_bool_false;
809
19.3M
  id1 = tuple_id(space1, type1);
810
19.3M
  id2 = tuple_id(space2, type2);
811
19.3M
  if (!id1 ^ !id2)
812
622k
    return isl_bool_false;
813
18.7M
  if (id1 && 
id1 != id23.88M
)
814
147k
    return isl_bool_false;
815
18.5M
  nested1 = nested(space1, type1);
816
18.5M
  nested2 = nested(space2, type2);
817
18.5M
  if (!nested1 ^ !nested2)
818
64.4k
    return isl_bool_false;
819
18.5M
  if (nested1 && 
!isl_space_has_equal_tuples(nested1, nested2)3.54M
)
820
26.1k
    return isl_bool_false;
821
18.4M
  return isl_bool_true;
822
18.4M
}
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.5M
{
827
11.5M
  int i;
828
11.5M
829
11.5M
  if (space1 == space2 && 
type1 == type22.85M
)
830
916k
    return isl_bool_true;
831
10.6M
832
10.6M
  if (!isl_space_tuple_is_equal(space1, type1, space2, type2))
833
2.06M
    return isl_bool_false;
834
8.57M
835
8.57M
  if (!space1->ids && 
!space2->ids5.66M
)
836
5.63M
    return isl_bool_true;
837
2.94M
838
10.9M
  
for (i = 0; 2.94M
i < n(space1, type1);
++i8.02M
) {
839
8.08M
    if (get_id(space1, type1, i) != get_id(space2, type2, i))
840
62.0k
      return isl_bool_false;
841
8.08M
  }
842
2.94M
  
return isl_bool_true2.87M
;
843
2.94M
}
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.21M
{
850
9.21M
  if (!space1 || !space2)
851
0
    return isl_bool_error;
852
9.21M
853
9.21M
  return match(space1, isl_dim_param, space2, isl_dim_param);
854
9.21M
}
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
203k
{
862
203k
  isl_bool equal;
863
203k
864
203k
  if (!space1 || !space2)
865
0
    return isl_bool_error;
866
203k
867
203k
  equal = match(space1, isl_dim_in, space2, isl_dim_in);
868
203k
  if (equal < 0 || !equal)
869
132
    return equal;
870
202k
  return match(space1, isl_dim_out, space2, isl_dim_out);
871
202k
}
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.74M
{
885
2.74M
  int i;
886
2.74M
887
6.88M
  for (i = 0; i < n ; 
++i4.13M
)
888
4.13M
    ids[i] = get_id(dim, type, first + i);
889
2.74M
}
890
891
static __isl_give isl_space *space_extend(__isl_take isl_space *space,
892
      unsigned nparam, unsigned n_in, unsigned n_out)
893
703k
{
894
703k
  isl_id **ids = NULL;
895
703k
896
703k
  if (!space)
897
0
    return NULL;
898
703k
  if (space->nparam == nparam &&
899
703k
      
space->n_in == n_in581k
&&
space->n_out == n_out573k
)
900
1.44k
    return space;
901
702k
902
702k
  isl_assert(space->ctx, space->nparam <= nparam, goto error);
903
702k
  isl_assert(space->ctx, space->n_in <= n_in, goto error);
904
702k
  isl_assert(space->ctx, space->n_out <= n_out, goto error);
905
702k
906
702k
  space = isl_space_cow(space);
907
702k
  if (!space)
908
0
    goto error;
909
702k
910
702k
  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
702k
  space->nparam = nparam;
929
702k
  space->n_in = n_in;
930
702k
  space->n_out = n_out;
931
702k
932
702k
  return space;
933
0
error:
934
0
  free(ids);
935
0
  isl_space_free(space);
936
0
  return NULL;
937
702k
}
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
703k
{
948
703k
  space = isl_space_reset(space, type);
949
703k
  if (!space)
950
8
    return NULL;
951
703k
  switch (type) {
952
703k
  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.79k
    return space_extend(space,
966
8.79k
        space->nparam, space->n_in + n, space->n_out);
967
572k
  case isl_dim_out:
968
572k
    return space_extend(space,
969
572k
        space->nparam, space->n_in, space->n_out + n);
970
122k
  default:
971
0
    isl_die(space->ctx, isl_error_invalid,
972
703k
      "cannot add dimensions of specified type", goto error);
973
703k
  }
974
703k
error:
975
0
  isl_space_free(space);
976
0
  return NULL;
977
703k
}
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.02M
{
1008
2.02M
  switch (type) {
1009
2.02M
  case isl_dim_param:
1010
2.02M
  case isl_dim_in:
1011
2.02M
  case isl_dim_out:
1012
2.02M
    return 1;
1013
2.02M
  default:
1014
0
    return 0;
1015
0
  }
1016
0
}
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 *dim,
1023
  enum isl_dim_type type, unsigned pos, unsigned n)
1024
177k
{
1025
177k
  isl_id **ids = NULL;
1026
177k
1027
177k
  if (!dim)
1028
0
    return NULL;
1029
177k
  if (n == 0)
1030
6
    return isl_space_reset(dim, type);
1031
177k
1032
177k
  if (!valid_dim_type(type))
1033
177k
    
isl_die0
(dim->ctx, isl_error_invalid,
1034
177k
      "cannot insert dimensions of specified type",
1035
177k
      goto error);
1036
177k
1037
177k
  isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error);
1038
177k
1039
177k
  dim = isl_space_cow(dim);
1040
177k
  if (!dim)
1041
0
    return NULL;
1042
177k
1043
177k
  if (dim->ids) {
1044
50.4k
    enum isl_dim_type t, o = isl_dim_param;
1045
50.4k
    int off;
1046
50.4k
    int s[3];
1047
50.4k
    ids = isl_calloc_array(dim->ctx, isl_id *,
1048
50.4k
             dim->nparam + dim->n_in + dim->n_out + n);
1049
50.4k
    if (!ids)
1050
0
      goto error;
1051
50.4k
    off = 0;
1052
50.4k
    s[isl_dim_param - o] = dim->nparam;
1053
50.4k
    s[isl_dim_in - o] = dim->n_in;
1054
50.4k
    s[isl_dim_out - o] = dim->n_out;
1055
201k
    for (t = isl_dim_param; t <= isl_dim_out; 
++t151k
) {
1056
151k
      if (t != type) {
1057
100k
        get_ids(dim, t, 0, s[t - o], ids + off);
1058
100k
        off += s[t - o];
1059
100k
      } else {
1060
50.4k
        get_ids(dim, t, 0, pos, ids + off);
1061
50.4k
        off += pos + n;
1062
50.4k
        get_ids(dim, t, pos, s[t - o] - pos, ids + off);
1063
50.4k
        off += s[t - o] - pos;
1064
50.4k
      }
1065
151k
    }
1066
50.4k
    free(dim->ids);
1067
50.4k
    dim->ids = ids;
1068
50.4k
    dim->n_id = dim->nparam + dim->n_in + dim->n_out + n;
1069
50.4k
  }
1070
177k
  switch (type) {
1071
177k
  
case isl_dim_param: dim->nparam += n; break2.77k
;
1072
177k
  
case isl_dim_in:  dim->n_in += n; break10.2k
;
1073
177k
  
case isl_dim_out: dim->n_out += n; break164k
;
1074
177k
  
default:    ;0
1075
177k
  }
1076
177k
  dim = isl_space_reset(dim, type);
1077
177k
1078
177k
  if (type == isl_dim_param) {
1079
2.77k
    if (dim && dim->nested[0] &&
1080
2.77k
        !(dim->nested[0] = isl_space_insert_dims(dim->nested[0],
1081
0
                isl_dim_param, pos, n)))
1082
0
      goto error;
1083
2.77k
    if (dim && dim->nested[1] &&
1084
2.77k
        !(dim->nested[1] = isl_space_insert_dims(dim->nested[1],
1085
1
                isl_dim_param, pos, n)))
1086
0
      goto error;
1087
177k
  }
1088
177k
1089
177k
  return dim;
1090
0
error:
1091
0
  isl_space_free(dim);
1092
0
  return NULL;
1093
177k
}
1094
1095
__isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
1096
  enum isl_dim_type dst_type, unsigned dst_pos,
1097
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1098
1.16k
{
1099
1.16k
  int i;
1100
1.16k
1101
1.16k
  space = isl_space_reset(space, src_type);
1102
1.16k
  space = isl_space_reset(space, dst_type);
1103
1.16k
  if (!space)
1104
0
    return NULL;
1105
1.16k
  if (n == 0)
1106
304
    return space;
1107
860
1108
860
  isl_assert(space->ctx, src_pos + n <= isl_space_dim(space, src_type),
1109
860
    goto error);
1110
860
1111
860
  if (dst_type == src_type && 
dst_pos == src_pos0
)
1112
0
    return space;
1113
860
1114
860
  isl_assert(space->ctx, dst_type != src_type, goto error);
1115
860
1116
860
  space = isl_space_cow(space);
1117
860
  if (!space)
1118
0
    return NULL;
1119
860
1120
860
  if (space->ids) {
1121
306
    isl_id **ids;
1122
306
    enum isl_dim_type t, o = isl_dim_param;
1123
306
    int off;
1124
306
    int s[3];
1125
306
    ids = isl_calloc_array(space->ctx, isl_id *,
1126
306
         space->nparam + space->n_in + space->n_out);
1127
306
    if (!ids)
1128
0
      goto error;
1129
306
    off = 0;
1130
306
    s[isl_dim_param - o] = space->nparam;
1131
306
    s[isl_dim_in - o] = space->n_in;
1132
306
    s[isl_dim_out - o] = space->n_out;
1133
1.22k
    for (t = isl_dim_param; t <= isl_dim_out; 
++t918
) {
1134
918
      if (t == dst_type) {
1135
306
        get_ids(space, t, 0, dst_pos, ids + off);
1136
306
        off += dst_pos;
1137
306
        get_ids(space, src_type, src_pos, n, ids + off);
1138
306
        off += n;
1139
306
        get_ids(space, t, dst_pos, s[t - o] - dst_pos,
1140
306
            ids + off);
1141
306
        off += s[t - o] - dst_pos;
1142
612
      } else if (t == src_type) {
1143
306
        get_ids(space, t, 0, src_pos, ids + off);
1144
306
        off += src_pos;
1145
306
        get_ids(space, t, src_pos + n,
1146
306
              s[t - o] - src_pos - n, ids + off);
1147
306
        off += s[t - o] - src_pos - n;
1148
306
      } else {
1149
306
        get_ids(space, t, 0, s[t - o], ids + off);
1150
306
        off += s[t - o];
1151
306
      }
1152
918
    }
1153
306
    free(space->ids);
1154
306
    space->ids = ids;
1155
306
    space->n_id = space->nparam + space->n_in + space->n_out;
1156
306
  }
1157
860
1158
860
  switch (dst_type) {
1159
860
  
case isl_dim_param: space->nparam += n; break86
;
1160
860
  
case isl_dim_in:  space->n_in += n; break361
;
1161
860
  
case isl_dim_out: space->n_out += n; break413
;
1162
860
  
default:    ;0
1163
860
  }
1164
860
1165
860
  switch (src_type) {
1166
860
  
case isl_dim_param: space->nparam -= n; break238
;
1167
860
  
case isl_dim_in:  space->n_in -= n; break193
;
1168
860
  
case isl_dim_out: space->n_out -= n; break429
;
1169
860
  
default:    ;0
1170
860
  }
1171
860
1172
860
  if (dst_type != isl_dim_param && 
src_type != isl_dim_param774
)
1173
536
    return space;
1174
324
1175
972
  
for (i = 0; 324
i < 2;
++i648
) {
1176
648
    if (!space->nested[i])
1177
631
      continue;
1178
17
    space->nested[i] = isl_space_replace_params(space->nested[i],
1179
17
                   space);
1180
17
    if (!space->nested[i])
1181
0
      goto error;
1182
17
  }
1183
324
1184
324
  return space;
1185
0
error:
1186
0
  isl_space_free(space);
1187
0
  return NULL;
1188
324
}
1189
1190
/* Check that "space1" and "space2" have the same parameters,
1191
 * reporting an error if they do not.
1192
 */
1193
isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,
1194
  __isl_keep isl_space *space2)
1195
649k
{
1196
649k
  isl_bool equal;
1197
649k
1198
649k
  equal = isl_space_has_equal_params(space1, space2);
1199
649k
  if (equal < 0)
1200
0
    return isl_stat_error;
1201
649k
  if (!equal)
1202
649k
    
isl_die0
(isl_space_get_ctx(space1), isl_error_invalid,
1203
649k
      "parameters need to match", return isl_stat_error);
1204
649k
  return isl_stat_ok;
1205
649k
}
1206
1207
__isl_give isl_space *isl_space_join(__isl_take isl_space *left,
1208
  __isl_take isl_space *right)
1209
541k
{
1210
541k
  isl_space *dim;
1211
541k
1212
541k
  if (isl_space_check_equal_params(left, right) < 0)
1213
0
    goto error;
1214
541k
1215
541k
  isl_assert(left->ctx,
1216
541k
    isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),
1217
541k
    goto error);
1218
541k
1219
541k
  dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out);
1220
541k
  if (!dim)
1221
0
    goto error;
1222
541k
1223
541k
  dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param);
1224
541k
  dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in);
1225
541k
  dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out);
1226
541k
1227
541k
  if (dim && left->tuple_id[0] &&
1228
541k
      
!(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0]))184k
)
1229
0
    goto error;
1230
541k
  if (dim && right->tuple_id[1] &&
1231
541k
      
!(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1]))144k
)
1232
0
    goto error;
1233
541k
  if (dim && left->nested[0] &&
1234
541k
      
!(dim->nested[0] = isl_space_copy(left->nested[0]))200k
)
1235
0
    goto error;
1236
541k
  if (dim && right->nested[1] &&
1237
541k
      
!(dim->nested[1] = isl_space_copy(right->nested[1]))252k
)
1238
0
    goto error;
1239
541k
1240
541k
  isl_space_free(left);
1241
541k
  isl_space_free(right);
1242
541k
1243
541k
  return dim;
1244
0
error:
1245
0
  isl_space_free(left);
1246
0
  isl_space_free(right);
1247
0
  return NULL;
1248
541k
}
1249
1250
/* Given two map spaces { A -> C } and { B -> D }, construct the space
1251
 * { [A -> B] -> [C -> D] }.
1252
 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1253
 */
1254
__isl_give isl_space *isl_space_product(__isl_take isl_space *left,
1255
  __isl_take isl_space *right)
1256
2.76k
{
1257
2.76k
  isl_space *dom1, *dom2, *nest1, *nest2;
1258
2.76k
  int is_set;
1259
2.76k
1260
2.76k
  if (!left || !right)
1261
0
    goto error;
1262
2.76k
1263
2.76k
  is_set = isl_space_is_set(left);
1264
2.76k
  if (is_set != isl_space_is_set(right))
1265
2.76k
    
isl_die0
(isl_space_get_ctx(left), isl_error_invalid,
1266
2.76k
      "expecting either two set spaces or two map spaces",
1267
2.76k
      goto error);
1268
2.76k
  if (is_set)
1269
272
    return isl_space_range_product(left, right);
1270
2.49k
1271
2.49k
  if (isl_space_check_equal_params(left, right) < 0)
1272
0
    goto error;
1273
2.49k
1274
2.49k
  dom1 = isl_space_domain(isl_space_copy(left));
1275
2.49k
  dom2 = isl_space_domain(isl_space_copy(right));
1276
2.49k
  nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1277
2.49k
1278
2.49k
  dom1 = isl_space_range(left);
1279
2.49k
  dom2 = isl_space_range(right);
1280
2.49k
  nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1281
2.49k
1282
2.49k
  return isl_space_join(isl_space_reverse(nest1), nest2);
1283
0
error:
1284
0
  isl_space_free(left);
1285
0
  isl_space_free(right);
1286
0
  return NULL;
1287
2.49k
}
1288
1289
/* Given two spaces { A -> C } and { B -> C }, construct the space
1290
 * { [A -> B] -> C }
1291
 */
1292
__isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,
1293
  __isl_take isl_space *right)
1294
1.88k
{
1295
1.88k
  isl_space *ran, *dom1, *dom2, *nest;
1296
1.88k
1297
1.88k
  if (isl_space_check_equal_params(left, right) < 0)
1298
0
    goto error;
1299
1.88k
1300
1.88k
  if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))
1301
1.88k
    
isl_die0
(left->ctx, isl_error_invalid,
1302
1.88k
      "ranges need to match", goto error);
1303
1.88k
1304
1.88k
  ran = isl_space_range(isl_space_copy(left));
1305
1.88k
1306
1.88k
  dom1 = isl_space_domain(left);
1307
1.88k
  dom2 = isl_space_domain(right);
1308
1.88k
  nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));
1309
1.88k
1310
1.88k
  return isl_space_join(isl_space_reverse(nest), ran);
1311
0
error:
1312
0
  isl_space_free(left);
1313
0
  isl_space_free(right);
1314
0
  return NULL;
1315
1.88k
}
1316
1317
__isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,
1318
  __isl_take isl_space *right)
1319
103k
{
1320
103k
  isl_space *dom, *ran1, *ran2, *nest;
1321
103k
1322
103k
  if (isl_space_check_equal_params(left, right) < 0)
1323
0
    goto error;
1324
103k
1325
103k
  if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))
1326
103k
    
isl_die0
(left->ctx, isl_error_invalid,
1327
103k
      "domains need to match", goto error);
1328
103k
1329
103k
  dom = isl_space_domain(isl_space_copy(left));
1330
103k
1331
103k
  ran1 = isl_space_range(left);
1332
103k
  ran2 = isl_space_range(right);
1333
103k
  nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));
1334
103k
1335
103k
  return isl_space_join(isl_space_reverse(dom), nest);
1336
0
error:
1337
0
  isl_space_free(left);
1338
0
  isl_space_free(right);
1339
0
  return NULL;
1340
103k
}
1341
1342
/* Given a space of the form [A -> B] -> C, return the space A -> C.
1343
 */
1344
__isl_give isl_space *isl_space_domain_factor_domain(
1345
  __isl_take isl_space *space)
1346
857
{
1347
857
  isl_space *nested;
1348
857
  isl_space *domain;
1349
857
1350
857
  if (!space)
1351
0
    return NULL;
1352
857
  if (!isl_space_domain_is_wrapping(space))
1353
857
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1354
857
      "domain not a product", return isl_space_free(space));
1355
857
1356
857
  nested = space->nested[0];
1357
857
  domain = isl_space_copy(space);
1358
857
  domain = isl_space_drop_dims(domain, isl_dim_in,
1359
857
          nested->n_in, nested->n_out);
1360
857
  if (!domain)
1361
0
    return isl_space_free(space);
1362
857
  if (nested->tuple_id[0]) {
1363
538
    domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);
1364
538
    if (!domain->tuple_id[0])
1365
0
      goto error;
1366
857
  }
1367
857
  if (nested->nested[0]) {
1368
319
    domain->nested[0] = isl_space_copy(nested->nested[0]);
1369
319
    if (!domain->nested[0])
1370
0
      goto error;
1371
857
  }
1372
857
1373
857
  isl_space_free(space);
1374
857
  return domain;
1375
0
error:
1376
0
  isl_space_free(space);
1377
0
  isl_space_free(domain);
1378
0
  return NULL;
1379
857
}
1380
1381
/* Given a space of the form [A -> B] -> C, return the space B -> C.
1382
 */
1383
__isl_give isl_space *isl_space_domain_factor_range(
1384
  __isl_take isl_space *space)
1385
20.6k
{
1386
20.6k
  isl_space *nested;
1387
20.6k
  isl_space *range;
1388
20.6k
1389
20.6k
  if (!space)
1390
0
    return NULL;
1391
20.6k
  if (!isl_space_domain_is_wrapping(space))
1392
20.6k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1393
20.6k
      "domain not a product", return isl_space_free(space));
1394
20.6k
1395
20.6k
  nested = space->nested[0];
1396
20.6k
  range = isl_space_copy(space);
1397
20.6k
  range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);
1398
20.6k
  if (!range)
1399
0
    return isl_space_free(space);
1400
20.6k
  if (nested->tuple_id[1]) {
1401
12.3k
    range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);
1402
12.3k
    if (!range->tuple_id[0])
1403
0
      goto error;
1404
20.6k
  }
1405
20.6k
  if (nested->nested[1]) {
1406
8.23k
    range->nested[0] = isl_space_copy(nested->nested[1]);
1407
8.23k
    if (!range->nested[0])
1408
0
      goto error;
1409
20.6k
  }
1410
20.6k
1411
20.6k
  isl_space_free(space);
1412
20.6k
  return range;
1413
0
error:
1414
0
  isl_space_free(space);
1415
0
  isl_space_free(range);
1416
0
  return NULL;
1417
20.6k
}
1418
1419
/* Internal function that selects the domain of the map that is
1420
 * embedded in either a set space or the range of a map space.
1421
 * In particular, given a space of the form [A -> B], return the space A.
1422
 * Given a space of the form A -> [B -> C], return the space A -> B.
1423
 */
1424
static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)
1425
2.22k
{
1426
2.22k
  isl_space *nested;
1427
2.22k
  isl_space *domain;
1428
2.22k
1429
2.22k
  if (!space)
1430
0
    return NULL;
1431
2.22k
1432
2.22k
  nested = space->nested[1];
1433
2.22k
  domain = isl_space_copy(space);
1434
2.22k
  domain = isl_space_drop_dims(domain, isl_dim_out,
1435
2.22k
          nested->n_in, nested->n_out);
1436
2.22k
  if (!domain)
1437
0
    return isl_space_free(space);
1438
2.22k
  if (nested->tuple_id[0]) {
1439
1.26k
    domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);
1440
1.26k
    if (!domain->tuple_id[1])
1441
0
      goto error;
1442
2.22k
  }
1443
2.22k
  if (nested->nested[0]) {
1444
940
    domain->nested[1] = isl_space_copy(nested->nested[0]);
1445
940
    if (!domain->nested[1])
1446
0
      goto error;
1447
2.22k
  }
1448
2.22k
1449
2.22k
  isl_space_free(space);
1450
2.22k
  return domain;
1451
0
error:
1452
0
  isl_space_free(space);
1453
0
  isl_space_free(domain);
1454
0
  return NULL;
1455
2.22k
}
1456
1457
/* Given a space of the form A -> [B -> C], return the space A -> B.
1458
 */
1459
__isl_give isl_space *isl_space_range_factor_domain(
1460
  __isl_take isl_space *space)
1461
2.22k
{
1462
2.22k
  if (!space)
1463
0
    return NULL;
1464
2.22k
  if (!isl_space_range_is_wrapping(space))
1465
2.22k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1466
2.22k
      "range not a product", return isl_space_free(space));
1467
2.22k
1468
2.22k
  return range_factor_domain(space);
1469
2.22k
}
1470
1471
/* Given a space of the form [A -> B], return the space A.
1472
 */
1473
static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)
1474
0
{
1475
0
  if (!space)
1476
0
    return NULL;
1477
0
  if (!isl_space_is_wrapping(space))
1478
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
1479
0
      "not a product", return isl_space_free(space));
1480
0
1481
0
  return range_factor_domain(space);
1482
0
}
1483
1484
/* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1485
 * Given a space of the form [A -> B], return the space A.
1486
 */
1487
__isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
1488
132
{
1489
132
  if (!space)
1490
0
    return NULL;
1491
132
  if (isl_space_is_set(space))
1492
0
    return set_factor_domain(space);
1493
132
  space = isl_space_domain_factor_domain(space);
1494
132
  space = isl_space_range_factor_domain(space);
1495
132
  return space;
1496
132
}
1497
1498
/* Internal function that selects the range of the map that is
1499
 * embedded in either a set space or the range of a map space.
1500
 * In particular, given a space of the form [A -> B], return the space B.
1501
 * Given a space of the form A -> [B -> C], return the space A -> C.
1502
 */
1503
static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
1504
13.4k
{
1505
13.4k
  isl_space *nested;
1506
13.4k
  isl_space *range;
1507
13.4k
1508
13.4k
  if (!space)
1509
0
    return NULL;
1510
13.4k
1511
13.4k
  nested = space->nested[1];
1512
13.4k
  range = isl_space_copy(space);
1513
13.4k
  range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);
1514
13.4k
  if (!range)
1515
0
    return isl_space_free(space);
1516
13.4k
  if (nested->tuple_id[1]) {
1517
744
    range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);
1518
744
    if (!range->tuple_id[1])
1519
0
      goto error;
1520
13.4k
  }
1521
13.4k
  if (nested->nested[1]) {
1522
12.7k
    range->nested[1] = isl_space_copy(nested->nested[1]);
1523
12.7k
    if (!range->nested[1])
1524
0
      goto error;
1525
13.4k
  }
1526
13.4k
1527
13.4k
  isl_space_free(space);
1528
13.4k
  return range;
1529
0
error:
1530
0
  isl_space_free(space);
1531
0
  isl_space_free(range);
1532
0
  return NULL;
1533
13.4k
}
1534
1535
/* Given a space of the form A -> [B -> C], return the space A -> C.
1536
 */
1537
__isl_give isl_space *isl_space_range_factor_range(
1538
  __isl_take isl_space *space)
1539
13.4k
{
1540
13.4k
  if (!space)
1541
0
    return NULL;
1542
13.4k
  if (!isl_space_range_is_wrapping(space))
1543
13.4k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1544
13.4k
      "range not a product", return isl_space_free(space));
1545
13.4k
1546
13.4k
  return range_factor_range(space);
1547
13.4k
}
1548
1549
/* Given a space of the form [A -> B], return the space B.
1550
 */
1551
static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
1552
9
{
1553
9
  if (!space)
1554
0
    return NULL;
1555
9
  if (!isl_space_is_wrapping(space))
1556
9
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1557
9
      "not a product", return isl_space_free(space));
1558
9
1559
9
  return range_factor_range(space);
1560
9
}
1561
1562
/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1563
 * Given a space of the form [A -> B], return the space B.
1564
 */
1565
__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
1566
12.7k
{
1567
12.7k
  if (!space)
1568
0
    return NULL;
1569
12.7k
  if (isl_space_is_set(space))
1570
9
    return set_factor_range(space);
1571
12.7k
  space = isl_space_domain_factor_range(space);
1572
12.7k
  space = isl_space_range_factor_range(space);
1573
12.7k
  return space;
1574
12.7k
}
1575
1576
__isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)
1577
12.4k
{
1578
12.4k
  isl_ctx *ctx;
1579
12.4k
  isl_id **ids = NULL;
1580
12.4k
  int n_id;
1581
12.4k
1582
12.4k
  if (!space)
1583
6
    return NULL;
1584
12.4k
  ctx = isl_space_get_ctx(space);
1585
12.4k
  if (!isl_space_is_set(space))
1586
12.4k
    
isl_die0
(ctx, isl_error_invalid, "not a set space", goto error);
1587
12.4k
  space = isl_space_cow(space);
1588
12.4k
  if (!space)
1589
0
    return NULL;
1590
12.4k
  n_id = space->nparam + space->n_out + space->n_out;
1591
12.4k
  if (n_id > 0 && 
space->ids11.8k
) {
1592
3.31k
    ids = isl_calloc_array(space->ctx, isl_id *, n_id);
1593
3.31k
    if (!ids)
1594
0
      goto error;
1595
3.31k
    get_ids(space, isl_dim_param, 0, space->nparam, ids);
1596
3.31k
    get_ids(space, isl_dim_out, 0, space->n_out,
1597
3.31k
      ids + space->nparam);
1598
3.31k
  }
1599
12.4k
  space->n_in = space->n_out;
1600
12.4k
  if (ids) {
1601
3.31k
    free(space->ids);
1602
3.31k
    space->ids = ids;
1603
3.31k
    space->n_id = n_id;
1604
3.31k
    space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);
1605
3.31k
  }
1606
12.4k
  isl_id_free(space->tuple_id[0]);
1607
12.4k
  space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);
1608
12.4k
  isl_space_free(space->nested[0]);
1609
12.4k
  space->nested[0] = isl_space_copy(space->nested[1]);
1610
12.4k
  return space;
1611
0
error:
1612
0
  isl_space_free(space);
1613
0
  return NULL;
1614
12.4k
}
1615
1616
__isl_give isl_space *isl_space_map_from_domain_and_range(
1617
  __isl_take isl_space *domain, __isl_take isl_space *range)
1618
83.9k
{
1619
83.9k
  if (!domain || !range)
1620
0
    goto error;
1621
83.9k
  if (!isl_space_is_set(domain))
1622
83.9k
    
isl_die0
(isl_space_get_ctx(domain), isl_error_invalid,
1623
83.9k
      "domain is not a set space", goto error);
1624
83.9k
  if (!isl_space_is_set(range))
1625
83.9k
    
isl_die0
(isl_space_get_ctx(range), isl_error_invalid,
1626
83.9k
      "range is not a set space", goto error);
1627
83.9k
  return isl_space_join(isl_space_reverse(domain), range);
1628
0
error:
1629
0
  isl_space_free(domain);
1630
0
  isl_space_free(range);
1631
0
  return NULL;
1632
83.9k
}
1633
1634
static __isl_give isl_space *set_ids(__isl_take isl_space *dim,
1635
  enum isl_dim_type type,
1636
  unsigned first, unsigned n, __isl_take isl_id **ids)
1637
1.41M
{
1638
1.41M
  int i;
1639
1.41M
1640
3.38M
  for (i = 0; i < n ; 
++i1.97M
)
1641
1.97M
    dim = set_id(dim, type, first + i, ids[i]);
1642
1.41M
1643
1.41M
  return dim;
1644
1.41M
}
1645
1646
__isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim)
1647
1.93M
{
1648
1.93M
  unsigned t;
1649
1.93M
  isl_space *nested;
1650
1.93M
  isl_id **ids = NULL;
1651
1.93M
  isl_id *id;
1652
1.93M
1653
1.93M
  if (!dim)
1654
0
    return NULL;
1655
1.93M
  if (match(dim, isl_dim_in, dim, isl_dim_out))
1656
115k
    return dim;
1657
1.82M
1658
1.82M
  dim = isl_space_cow(dim);
1659
1.82M
  if (!dim)
1660
0
    return NULL;
1661
1.82M
1662
1.82M
  id = dim->tuple_id[0];
1663
1.82M
  dim->tuple_id[0] = dim->tuple_id[1];
1664
1.82M
  dim->tuple_id[1] = id;
1665
1.82M
1666
1.82M
  nested = dim->nested[0];
1667
1.82M
  dim->nested[0] = dim->nested[1];
1668
1.82M
  dim->nested[1] = nested;
1669
1.82M
1670
1.82M
  if (dim->ids) {
1671
705k
    int n_id = dim->n_in + dim->n_out;
1672
705k
    ids = isl_alloc_array(dim->ctx, isl_id *, n_id);
1673
705k
    if (n_id && 
!ids591k
)
1674
0
      goto error;
1675
705k
    get_ids(dim, isl_dim_in, 0, dim->n_in, ids);
1676
705k
    get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in);
1677
705k
  }
1678
1.82M
1679
1.82M
  t = dim->n_in;
1680
1.82M
  dim->n_in = dim->n_out;
1681
1.82M
  dim->n_out = t;
1682
1.82M
1683
1.82M
  if (dim->ids) {
1684
705k
    dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids);
1685
705k
    dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out);
1686
705k
    free(ids);
1687
705k
  }
1688
1.82M
1689
1.82M
  return dim;
1690
0
error:
1691
0
  free(ids);
1692
0
  isl_space_free(dim);
1693
0
  return NULL;
1694
1.82M
}
1695
1696
__isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim,
1697
  enum isl_dim_type type, unsigned first, unsigned num)
1698
2.25M
{
1699
2.25M
  int i;
1700
2.25M
1701
2.25M
  if (!dim)
1702
2
    return NULL;
1703
2.25M
1704
2.25M
  if (num == 0)
1705
413k
    return isl_space_reset(dim, type);
1706
1.84M
1707
1.84M
  if (!valid_dim_type(type))
1708
1.84M
    
isl_die0
(dim->ctx, isl_error_invalid,
1709
1.84M
      "cannot drop dimensions of specified type", goto error);
1710
1.84M
1711
1.84M
  if (first + num > n(dim, type) || first + num < first)
1712
1.84M
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1713
1.84M
      "index out of bounds", return isl_space_free(dim));
1714
1.84M
  dim = isl_space_cow(dim);
1715
1.84M
  if (!dim)
1716
0
    goto error;
1717
1.84M
  if (dim->ids) {
1718
517k
    dim = extend_ids(dim);
1719
517k
    if (!dim)
1720
0
      goto error;
1721
1.64M
    
for (i = 0; 517k
i < num;
++i1.12M
)
1722
1.12M
      isl_id_free(get_id(dim, type, first + i));
1723
574k
    for (i = first+num; i < n(dim, type); 
++i57.3k
)
1724
57.3k
      set_id(dim, type, i - num, get_id(dim, type, i));
1725
517k
    switch (type) {
1726
517k
    case isl_dim_param:
1727
29.6k
      get_ids(dim, isl_dim_in, 0, dim->n_in,
1728
29.6k
        dim->ids + offset(dim, isl_dim_in) - num);
1729
171k
    case isl_dim_in:
1730
171k
      get_ids(dim, isl_dim_out, 0, dim->n_out,
1731
171k
        dim->ids + offset(dim, isl_dim_out) - num);
1732
517k
    default:
1733
517k
      ;
1734
517k
    }
1735
517k
    dim->n_id -= num;
1736
517k
  }
1737
1.84M
  switch (type) {
1738
1.84M
  
case isl_dim_param: dim->nparam -= num; break30.3k
;
1739
1.84M
  
case isl_dim_in:  dim->n_in -= num; break399k
;
1740
1.84M
  
case isl_dim_out: dim->n_out -= num; break1.41M
;
1741
1.84M
  
default:    ;0
1742
1.84M
  }
1743
1.84M
  dim = isl_space_reset(dim, type);
1744
1.84M
  if (type == isl_dim_param) {
1745
30.3k
    if (dim && dim->nested[0] &&
1746
30.3k
        !(dim->nested[0] = isl_space_drop_dims(dim->nested[0],
1747
122
                isl_dim_param, first, num)))
1748
0
      goto error;
1749
30.3k
    if (dim && dim->nested[1] &&
1750
30.3k
        !(dim->nested[1] = isl_space_drop_dims(dim->nested[1],
1751
548
                isl_dim_param, first, num)))
1752
0
      goto error;
1753
1.84M
  }
1754
1.84M
  return dim;
1755
0
error:
1756
0
  isl_space_free(dim);
1757
0
  return NULL;
1758
1.84M
}
1759
1760
__isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim,
1761
    unsigned first, unsigned n)
1762
0
{
1763
0
  if (!dim)
1764
0
    return NULL;
1765
0
  return isl_space_drop_dims(dim, isl_dim_in, first, n);
1766
0
}
1767
1768
__isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim,
1769
    unsigned first, unsigned n)
1770
0
{
1771
0
  if (!dim)
1772
0
    return NULL;
1773
0
  return isl_space_drop_dims(dim, isl_dim_out, first, n);
1774
0
}
1775
1776
__isl_give isl_space *isl_space_domain(__isl_take isl_space *space)
1777
706k
{
1778
706k
  if (!space)
1779
0
    return NULL;
1780
706k
  space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);
1781
706k
  space = isl_space_reverse(space);
1782
706k
  space = mark_as_set(space);
1783
706k
  return space;
1784
706k
}
1785
1786
__isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim)
1787
656k
{
1788
656k
  if (!dim)
1789
0
    return NULL;
1790
656k
  if (!isl_space_is_set(dim))
1791
656k
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1792
656k
      "not a set space", goto error);
1793
656k
  dim = isl_space_reverse(dim);
1794
656k
  dim = isl_space_reset(dim, isl_dim_out);
1795
656k
  return dim;
1796
0
error:
1797
0
  isl_space_free(dim);
1798
0
  return NULL;
1799
656k
}
1800
1801
__isl_give isl_space *isl_space_range(__isl_take isl_space *space)
1802
351k
{
1803
351k
  if (!space)
1804
2
    return NULL;
1805
351k
  space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);
1806
351k
  space = mark_as_set(space);
1807
351k
  return space;
1808
351k
}
1809
1810
__isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim)
1811
199k
{
1812
199k
  if (!dim)
1813
3
    return NULL;
1814
199k
  if (!isl_space_is_set(dim))
1815
199k
    
isl_die0
(isl_space_get_ctx(dim), isl_error_invalid,
1816
199k
      "not a set space", goto error);
1817
199k
  return isl_space_reset(dim, isl_dim_in);
1818
0
error:
1819
0
  isl_space_free(dim);
1820
0
  return NULL;
1821
199k
}
1822
1823
/* Given a map space A -> B, return the map space [A -> B] -> A.
1824
 */
1825
__isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)
1826
1.86k
{
1827
1.86k
  isl_space *domain;
1828
1.86k
1829
1.86k
  domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));
1830
1.86k
  space = isl_space_from_domain(isl_space_wrap(space));
1831
1.86k
  space = isl_space_join(space, domain);
1832
1.86k
1833
1.86k
  return space;
1834
1.86k
}
1835
1836
/* Given a map space A -> B, return the map space [A -> B] -> B.
1837
 */
1838
__isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)
1839
16
{
1840
16
  isl_space *range;
1841
16
1842
16
  range = isl_space_from_range(isl_space_range(isl_space_copy(space)));
1843
16
  space = isl_space_from_domain(isl_space_wrap(space));
1844
16
  space = isl_space_join(space, range);
1845
16
1846
16
  return space;
1847
16
}
1848
1849
__isl_give isl_space *isl_space_params(__isl_take isl_space *space)
1850
468k
{
1851
468k
  if (isl_space_is_params(space))
1852
355k
    return space;
1853
112k
  space = isl_space_drop_dims(space,
1854
112k
          isl_dim_in, 0, isl_space_dim(space, isl_dim_in));
1855
112k
  space = isl_space_drop_dims(space,
1856
112k
          isl_dim_out, 0, isl_space_dim(space, isl_dim_out));
1857
112k
  space = mark_as_params(space);
1858
112k
  return space;
1859
112k
}
1860
1861
__isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)
1862
17.0k
{
1863
17.0k
  if (!space)
1864
0
    return NULL;
1865
17.0k
  if (!isl_space_is_params(space))
1866
17.0k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
1867
17.0k
      "not a parameter space", goto error);
1868
17.0k
  return isl_space_reset(space, isl_dim_set);
1869
0
error:
1870
0
  isl_space_free(space);
1871
0
  return NULL;
1872
17.0k
}
1873
1874
__isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim,
1875
  unsigned n_div)
1876
444k
{
1877
444k
  int i;
1878
444k
1879
444k
  if (!dim)
1880
0
    return NULL;
1881
444k
  if (n_div == 0 &&
1882
444k
      
dim->nparam == 0427k
&&
dim->n_in == 0243k
&&
dim->n_id == 0194k
)
1883
177k
    return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out);
1884
266k
  dim = isl_space_cow(dim);
1885
266k
  if (!dim)
1886
0
    return NULL;
1887
266k
  dim->n_out += dim->nparam + dim->n_in + n_div;
1888
266k
  dim->nparam = 0;
1889
266k
  dim->n_in = 0;
1890
266k
1891
1.35M
  for (i = 0; i < dim->n_id; 
++i1.08M
)
1892
1.08M
    isl_id_free(get_id(dim, isl_dim_out, i));
1893
266k
  dim->n_id = 0;
1894
266k
  dim = isl_space_reset(dim, isl_dim_in);
1895
266k
  dim = isl_space_reset(dim, isl_dim_out);
1896
266k
1897
266k
  return dim;
1898
266k
}
1899
1900
/* Are the two spaces the same, including positions and names of parameters?
1901
 */
1902
isl_bool isl_space_is_equal(__isl_keep isl_space *space1,
1903
  __isl_keep isl_space *space2)
1904
7.67M
{
1905
7.67M
  isl_bool equal;
1906
7.67M
1907
7.67M
  if (!space1 || !space2)
1908
0
    return isl_bool_error;
1909
7.67M
  if (space1 == space2)
1910
4.32M
    return isl_bool_true;
1911
3.34M
  equal = isl_space_has_equal_params(space1, space2);
1912
3.34M
  if (equal < 0 || !equal)
1913
67.7k
    return equal;
1914
3.27M
  return isl_space_has_equal_tuples(space1, space2);
1915
3.27M
}
1916
1917
/* Do the tuples of "space1" correspond to those of the domain of "space2"?
1918
 * That is, is "space1" eqaul to the domain of "space2", ignoring parameters.
1919
 *
1920
 * "space2" is allowed to be a set space, in which case "space1"
1921
 * should be a parameter space.
1922
 */
1923
isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,
1924
  __isl_keep isl_space *space2)
1925
106k
{
1926
106k
  isl_bool is_set;
1927
106k
1928
106k
  is_set = isl_space_is_set(space1);
1929
106k
  if (is_set < 0 || !is_set)
1930
0
    return is_set;
1931
106k
  return isl_space_tuple_is_equal(space1, isl_dim_set,
1932
106k
          space2, isl_dim_in);
1933
106k
}
1934
1935
/* Is space1 equal to the domain of space2?
1936
 *
1937
 * In the internal version we also allow space2 to be the space of a set,
1938
 * provided space1 is a parameter space.
1939
 */
1940
isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,
1941
  __isl_keep isl_space *space2)
1942
106k
{
1943
106k
  isl_bool equal_params;
1944
106k
1945
106k
  if (!space1 || !space2)
1946
0
    return isl_bool_error;
1947
106k
  equal_params = isl_space_has_equal_params(space1, space2);
1948
106k
  if (equal_params < 0 || !equal_params)
1949
0
    return equal_params;
1950
106k
  return isl_space_has_domain_tuples(space1, space2);
1951
106k
}
1952
1953
/* Is space1 equal to the domain of space2?
1954
 */
1955
isl_bool isl_space_is_domain(__isl_keep isl_space *space1,
1956
  __isl_keep isl_space *space2)
1957
25
{
1958
25
  if (!space2)
1959
0
    return isl_bool_error;
1960
25
  if (!isl_space_is_map(space2))
1961
0
    return isl_bool_false;
1962
25
  return isl_space_is_domain_internal(space1, space2);
1963
25
}
1964
1965
/* Is space1 equal to the range of space2?
1966
 *
1967
 * In the internal version, space2 is allowed to be the space of a set,
1968
 * in which case it should be equal to space1.
1969
 */
1970
isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,
1971
  __isl_keep isl_space *space2)
1972
17.3k
{
1973
17.3k
  isl_bool equal_params;
1974
17.3k
1975
17.3k
  if (!space1 || !space2)
1976
0
    return isl_bool_error;
1977
17.3k
  if (!isl_space_is_set(space1))
1978
0
    return isl_bool_false;
1979
17.3k
  equal_params = isl_space_has_equal_params(space1, space2);
1980
17.3k
  if (equal_params < 0 || !equal_params)
1981
0
    return equal_params;
1982
17.3k
  return isl_space_tuple_is_equal(space1, isl_dim_set,
1983
17.3k
          space2, isl_dim_out);
1984
17.3k
}
1985
1986
/* Is space1 equal to the range of space2?
1987
 */
1988
isl_bool isl_space_is_range(__isl_keep isl_space *space1,
1989
  __isl_keep isl_space *space2)
1990
0
{
1991
0
  if (!space2)
1992
0
    return isl_bool_error;
1993
0
  if (!isl_space_is_map(space2))
1994
0
    return isl_bool_false;
1995
0
  return isl_space_is_range_internal(space1, space2);
1996
0
}
1997
1998
/* Update "hash" by hashing in the parameters of "space".
1999
 */
2000
static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)
2001
543k
{
2002
543k
  int i;
2003
543k
  isl_id *id;
2004
543k
2005
543k
  if (!space)
2006
0
    return hash;
2007
543k
2008
543k
  isl_hash_byte(hash, space->nparam % 256);
2009
543k
2010
1.27M
  for (i = 0; i < space->nparam; 
++i731k
) {
2011
731k
    id = get_id(space, isl_dim_param, i);
2012
731k
    hash = isl_hash_id(hash, id);
2013
731k
  }
2014
543k
2015
543k
  return hash;
2016
543k
}
2017
2018
/* Update "hash" by hashing in the tuples of "space".
2019
 * Changes in this function should be reflected in isl_hash_tuples_domain.
2020
 */
2021
static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)
2022
2.10M
{
2023
2.10M
  isl_id *id;
2024
2.10M
2025
2.10M
  if (!space)
2026
1.32M
    return hash;
2027
781k
2028
781k
  isl_hash_byte(hash, space->n_in % 256);
2029
781k
  isl_hash_byte(hash, space->n_out % 256);
2030
781k
2031
781k
  id = tuple_id(space, isl_dim_in);
2032
781k
  hash = isl_hash_id(hash, id);
2033
781k
  id = tuple_id(space, isl_dim_out);
2034
781k
  hash = isl_hash_id(hash, id);
2035
781k
2036
781k
  hash = isl_hash_tuples(hash, space->nested[0]);
2037
781k
  hash = isl_hash_tuples(hash, space->nested[1]);
2038
781k
2039
781k
  return hash;
2040
781k
}
2041
2042
/* Update "hash" by hashing in the domain tuple of "space".
2043
 * The result of this function is equal to the result of applying
2044
 * isl_hash_tuples to the domain of "space".
2045
 */
2046
static uint32_t isl_hash_tuples_domain(uint32_t hash,
2047
  __isl_keep isl_space *space)
2048
45.1k
{
2049
45.1k
  isl_id *id;
2050
45.1k
2051
45.1k
  if (!space)
2052
0
    return hash;
2053
45.1k
2054
45.1k
  isl_hash_byte(hash, 0);
2055
45.1k
  isl_hash_byte(hash, space->n_in % 256);
2056
45.1k
2057
45.1k
  hash = isl_hash_id(hash, &isl_id_none);
2058
45.1k
  id = tuple_id(space, isl_dim_in);
2059
45.1k
  hash = isl_hash_id(hash, id);
2060
45.1k
2061
45.1k
  hash = isl_hash_tuples(hash, space->nested[0]);
2062
45.1k
2063
45.1k
  return hash;
2064
45.1k
}
2065
2066
/* Return a hash value that digests the tuples of "space",
2067
 * i.e., that ignores the parameters.
2068
 */
2069
uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)
2070
2.26k
{
2071
2.26k
  uint32_t hash;
2072
2.26k
2073
2.26k
  if (!space)
2074
0
    return 0;
2075
2.26k
2076
2.26k
  hash = isl_hash_init();
2077
2.26k
  hash = isl_hash_tuples(hash, space);
2078
2.26k
2079
2.26k
  return hash;
2080
2.26k
}
2081
2082
uint32_t isl_space_get_hash(__isl_keep isl_space *space)
2083
497k
{
2084
497k
  uint32_t hash;
2085
497k
2086
497k
  if (!space)
2087
0
    return 0;
2088
497k
2089
497k
  hash = isl_hash_init();
2090
497k
  hash = isl_hash_params(hash, space);
2091
497k
  hash = isl_hash_tuples(hash, space);
2092
497k
2093
497k
  return hash;
2094
497k
}
2095
2096
/* Return the hash value of the domain of "space".
2097
 * That is, isl_space_get_domain_hash(space) is equal to
2098
 * isl_space_get_hash(isl_space_domain(space)).
2099
 */
2100
uint32_t isl_space_get_domain_hash(__isl_keep isl_space *space)
2101
45.1k
{
2102
45.1k
  uint32_t hash;
2103
45.1k
2104
45.1k
  if (!space)
2105
0
    return 0;
2106
45.1k
2107
45.1k
  hash = isl_hash_init();
2108
45.1k
  hash = isl_hash_params(hash, space);
2109
45.1k
  hash = isl_hash_tuples_domain(hash, space);
2110
45.1k
2111
45.1k
  return hash;
2112
45.1k
}
2113
2114
isl_bool isl_space_is_wrapping(__isl_keep isl_space *dim)
2115
57.6k
{
2116
57.6k
  if (!dim)
2117
0
    return isl_bool_error;
2118
57.6k
2119
57.6k
  if (!isl_space_is_set(dim))
2120
0
    return isl_bool_false;
2121
57.6k
2122
57.6k
  return dim->nested[1] != NULL;
2123
57.6k
}
2124
2125
/* Is "space" the space of a map where the domain is a wrapped map space?
2126
 */
2127
isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)
2128
49.9k
{
2129
49.9k
  if (!space)
2130
0
    return isl_bool_error;
2131
49.9k
2132
49.9k
  if (isl_space_is_set(space))
2133
0
    return isl_bool_false;
2134
49.9k
2135
49.9k
  return space->nested[0] != NULL;
2136
49.9k
}
2137
2138
/* Is "space" the space of a map where the range is a wrapped map space?
2139
 */
2140
isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)
2141
66.8k
{
2142
66.8k
  if (!space)
2143
0
    return isl_bool_error;
2144
66.8k
2145
66.8k
  if (isl_space_is_set(space))
2146
781
    return isl_bool_false;
2147
66.0k
2148
66.0k
  return space->nested[1] != NULL;
2149
66.0k
}
2150
2151
/* Is "space" a product of two spaces?
2152
 * That is, is it a wrapping set space or a map space
2153
 * with wrapping domain and range?
2154
 */
2155
isl_bool isl_space_is_product(__isl_keep isl_space *space)
2156
6.23k
{
2157
6.23k
  isl_bool is_set;
2158
6.23k
  isl_bool is_product;
2159
6.23k
2160
6.23k
  is_set = isl_space_is_set(space);
2161
6.23k
  if (is_set < 0)
2162
0
    return isl_bool_error;
2163
6.23k
  if (is_set)
2164
0
    return isl_space_is_wrapping(space);
2165
6.23k
  is_product = isl_space_domain_is_wrapping(space);
2166
6.23k
  if (is_product < 0 || !is_product)
2167
35
    return is_product;
2168
6.20k
  return isl_space_range_is_wrapping(space);
2169
6.20k
}
2170
2171
__isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim)
2172
205k
{
2173
205k
  isl_space *wrap;
2174
205k
2175
205k
  if (!dim)
2176
0
    return NULL;
2177
205k
2178
205k
  wrap = isl_space_set_alloc(dim->ctx,
2179
205k
            dim->nparam, dim->n_in + dim->n_out);
2180
205k
2181
205k
  wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param);
2182
205k
  wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in);
2183
205k
  wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out);
2184
205k
2185
205k
  if (!wrap)
2186
0
    goto error;
2187
205k
2188
205k
  wrap->nested[1] = dim;
2189
205k
2190
205k
  return wrap;
2191
0
error:
2192
0
  isl_space_free(dim);
2193
0
  return NULL;
2194
205k
}
2195
2196
__isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim)
2197
39.8k
{
2198
39.8k
  isl_space *unwrap;
2199
39.8k
2200
39.8k
  if (!dim)
2201
0
    return NULL;
2202
39.8k
2203
39.8k
  if (!isl_space_is_wrapping(dim))
2204
39.8k
    
isl_die0
(dim->ctx, isl_error_invalid, "not a wrapping space",
2205
39.8k
      goto error);
2206
39.8k
2207
39.8k
  unwrap = isl_space_copy(dim->nested[1]);
2208
39.8k
  isl_space_free(dim);
2209
39.8k
2210
39.8k
  return unwrap;
2211
0
error:
2212
0
  isl_space_free(dim);
2213
0
  return NULL;
2214
39.8k
}
2215
2216
isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,
2217
  enum isl_dim_type type)
2218
5.52M
{
2219
5.52M
  if (type != isl_dim_in && 
type != isl_dim_out3.98M
)
2220
206k
    return isl_bool_false;
2221
5.32M
  if (!space)
2222
8
    return isl_bool_error;
2223
5.32M
  if (space->tuple_id[type - isl_dim_in])
2224
2.25M
    return isl_bool_true;
2225
3.06M
  if (space->nested[type - isl_dim_in])
2226
778k
    return isl_bool_true;
2227
2.28M
  return isl_bool_false;
2228
2.28M
}
2229
2230
isl_bool isl_space_may_be_set(__isl_keep isl_space *space)
2231
272
{
2232
272
  isl_bool nested;
2233
272
2234
272
  if (!space)
2235
0
    return isl_bool_error;
2236
272
  if (isl_space_is_set(space))
2237
167
    return isl_bool_true;
2238
105
  if (isl_space_dim(space, isl_dim_in) != 0)
2239
0
    return isl_bool_false;
2240
105
  nested = isl_space_is_named_or_nested(space, isl_dim_in);
2241
105
  if (nested < 0 || nested)
2242
0
    return isl_bool_not(nested);
2243
105
  return isl_bool_true;
2244
105
}
2245
2246
__isl_give isl_space *isl_space_reset(__isl_take isl_space *dim,
2247
  enum isl_dim_type type)
2248
5.03M
{
2249
5.03M
  if (!isl_space_is_named_or_nested(dim, type))
2250
2.23M
    return dim;
2251
2.80M
2252
2.80M
  dim = isl_space_cow(dim);
2253
2.80M
  if (!dim)
2254
16
    return NULL;
2255
2.80M
2256
2.80M
  isl_id_free(dim->tuple_id[type - isl_dim_in]);
2257
2.80M
  dim->tuple_id[type - isl_dim_in] = NULL;
2258
2.80M
  isl_space_free(dim->nested[type - isl_dim_in]);
2259
2.80M
  dim->nested[type - isl_dim_in] = NULL;
2260
2.80M
2261
2.80M
  return dim;
2262
2.80M
}
2263
2264
__isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim)
2265
23.0k
{
2266
23.0k
  if (!dim)
2267
0
    return NULL;
2268
23.0k
  if (!dim->nested[0] && !dim->nested[1])
2269
0
    return dim;
2270
23.0k
2271
23.0k
  if (dim->nested[0])
2272
0
    dim = isl_space_reset(dim, isl_dim_in);
2273
23.0k
  if (dim && dim->nested[1])
2274
23.0k
    dim = isl_space_reset(dim, isl_dim_out);
2275
23.0k
2276
23.0k
  return dim;
2277
23.0k
}
2278
2279
__isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)
2280
34
{
2281
34
  if (!space)
2282
0
    return NULL;
2283
34
  if (!space->nested[0])
2284
0
    return space;
2285
34
2286
34
  return isl_space_reset(space, isl_dim_in);
2287
34
}
2288
2289
__isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)
2290
74.1k
{
2291
74.1k
  if (!space)
2292
0
    return NULL;
2293
74.1k
  if (!space->nested[1])
2294
0
    return space;
2295
74.1k
2296
74.1k
  return isl_space_reset(space, isl_dim_out);
2297
74.1k
}
2298
2299
/* Replace the parameters of dst by those of src.
2300
 */
2301
__isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,
2302
  __isl_keep isl_space *src)
2303
114k
{
2304
114k
  isl_bool equal_params;
2305
114k
  enum isl_dim_type type = isl_dim_param;
2306
114k
2307
114k
  equal_params = isl_space_has_equal_params(dst, src);
2308
114k
  if (equal_params < 0)
2309
0
    return isl_space_free(dst);
2310
114k
  if (equal_params)
2311
49.1k
    return dst;
2312
65.3k
2313
65.3k
  dst = isl_space_cow(dst);
2314
65.3k
2315
65.3k
  if (!dst || !src)
2316
0
    goto error;
2317
65.3k
2318
65.3k
  dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type));
2319
65.3k
  dst = isl_space_add_dims(dst, type, isl_space_dim(src, type));
2320
65.3k
  dst = copy_ids(dst, type, 0, src, type);
2321
65.3k
2322
65.3k
  if (dst) {
2323
65.3k
    int i;
2324
195k
    for (i = 0; i <= 1; 
++i130k
) {
2325
130k
      if (!dst->nested[i])
2326
130k
        continue;
2327
463
      dst->nested[i] = isl_space_replace_params(
2328
463
              dst->nested[i], src);
2329
463
      if (!dst->nested[i])
2330
0
        goto error;
2331
463
    }
2332
65.3k
  }
2333
65.3k
2334
65.3k
  return dst;
2335
0
error:
2336
0
  isl_space_free(dst);
2337
0
  return NULL;
2338
65.3k
}
2339
2340
/* Given a dimension specification "dim" of a set, create a dimension
2341
 * specification for the lift of the set.  In particular, the result
2342
 * is of the form [dim -> local[..]], with n_local variables in the
2343
 * range of the wrapped map.
2344
 */
2345
__isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local)
2346
20.7k
{
2347
20.7k
  isl_space *local_dim;
2348
20.7k
2349
20.7k
  if (!dim)
2350
0
    return NULL;
2351
20.7k
2352
20.7k
  local_dim = isl_space_dup(dim);
2353
20.7k
  local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out);
2354
20.7k
  local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local);
2355
20.7k
  local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local");
2356
20.7k
  dim = isl_space_join(isl_space_from_domain(dim),
2357
20.7k
          isl_space_from_range(local_dim));
2358
20.7k
  dim = isl_space_wrap(dim);
2359
20.7k
  dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted");
2360
20.7k
2361
20.7k
  return dim;
2362
20.7k
}
2363
2364
isl_bool isl_space_can_zip(__isl_keep isl_space *space)
2365
6.14k
{
2366
6.14k
  isl_bool is_set;
2367
6.14k
2368
6.14k
  is_set = isl_space_is_set(space);
2369
6.14k
  if (is_set < 0)
2370
0
    return isl_bool_error;
2371
6.14k
  if (is_set)
2372
0
    return isl_bool_false;
2373
6.14k
  return isl_space_is_product(space);
2374
6.14k
}
2375
2376
__isl_give isl_space *isl_space_zip(__isl_take isl_space *dim)
2377
2.63k
{
2378
2.63k
  isl_space *dom, *ran;
2379
2.63k
  isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;
2380
2.63k
2381
2.63k
  if (!isl_space_can_zip(dim))
2382
2.63k
    
isl_die0
(dim->ctx, isl_error_invalid, "dim cannot be zipped",
2383
2.63k
      goto error);
2384
2.63k
2385
2.63k
  if (!dim)
2386
0
    return NULL;
2387
2.63k
  dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim)));
2388
2.63k
  ran = isl_space_unwrap(isl_space_range(dim));
2389
2.63k
  dom_dom = isl_space_domain(isl_space_copy(dom));
2390
2.63k
  dom_ran = isl_space_range(dom);
2391
2.63k
  ran_dom = isl_space_domain(isl_space_copy(ran));
2392
2.63k
  ran_ran = isl_space_range(ran);
2393
2.63k
  dom = isl_space_join(isl_space_from_domain(dom_dom),
2394
2.63k
         isl_space_from_range(ran_dom));
2395
2.63k
  ran = isl_space_join(isl_space_from_domain(dom_ran),
2396
2.63k
         isl_space_from_range(ran_ran));
2397
2.63k
  return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2398
2.63k
          isl_space_from_range(isl_space_wrap(ran)));
2399
0
error:
2400
0
  isl_space_free(dim);
2401
0
  return NULL;
2402
2.63k
}
2403
2404
/* Can we apply isl_space_curry to "space"?
2405
 * That is, does it have a nested relation in its domain?
2406
 */
2407
isl_bool isl_space_can_curry(__isl_keep isl_space *space)
2408
41.4k
{
2409
41.4k
  if (!space)
2410
0
    return isl_bool_error;
2411
41.4k
2412
41.4k
  return !!space->nested[0];
2413
41.4k
}
2414
2415
/* Given a space (A -> B) -> C, return the corresponding space
2416
 * A -> (B -> C).
2417
 */
2418
__isl_give isl_space *isl_space_curry(__isl_take isl_space *space)
2419
13.4k
{
2420
13.4k
  isl_space *dom, *ran;
2421
13.4k
  isl_space *dom_dom, *dom_ran;
2422
13.4k
2423
13.4k
  if (!space)
2424
0
    return NULL;
2425
13.4k
2426
13.4k
  if (!isl_space_can_curry(space))
2427
13.4k
    
isl_die0
(space->ctx, isl_error_invalid,
2428
13.4k
      "space cannot be curried", goto error);
2429
13.4k
2430
13.4k
  dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));
2431
13.4k
  ran = isl_space_range(space);
2432
13.4k
  dom_dom = isl_space_domain(isl_space_copy(dom));
2433
13.4k
  dom_ran = isl_space_range(dom);
2434
13.4k
  ran = isl_space_join(isl_space_from_domain(dom_ran),
2435
13.4k
         isl_space_from_range(ran));
2436
13.4k
  return isl_space_join(isl_space_from_domain(dom_dom),
2437
13.4k
          isl_space_from_range(isl_space_wrap(ran)));
2438
0
error:
2439
0
  isl_space_free(space);
2440
0
  return NULL;
2441
13.4k
}
2442
2443
/* Can isl_space_range_curry be applied to "space"?
2444
 * That is, does it have a nested relation in its range,
2445
 * the domain of which is itself a nested relation?
2446
 */
2447
isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)
2448
25.5k
{
2449
25.5k
  isl_bool can;
2450
25.5k
2451
25.5k
  if (!space)
2452
0
    return isl_bool_error;
2453
25.5k
  can = isl_space_range_is_wrapping(space);
2454
25.5k
  if (can < 0 || !can)
2455
0
    return can;
2456
25.5k
  return isl_space_can_curry(space->nested[1]);
2457
25.5k
}
2458
2459
/* Given a space A -> ((B -> C) -> D), return the corresponding space
2460
 * A -> (B -> (C -> D)).
2461
 */
2462
__isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)
2463
12.7k
{
2464
12.7k
  if (!space)
2465
0
    return NULL;
2466
12.7k
2467
12.7k
  if (!isl_space_can_range_curry(space))
2468
12.7k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
2469
12.7k
      "space range cannot be curried",
2470
12.7k
      return isl_space_free(space));
2471
12.7k
2472
12.7k
  space = isl_space_cow(space);
2473
12.7k
  if (!space)
2474
0
    return NULL;
2475
12.7k
  space->nested[1] = isl_space_curry(space->nested[1]);
2476
12.7k
  if (!space->nested[1])
2477
0
    return isl_space_free(space);
2478
12.7k
2479
12.7k
  return space;
2480
12.7k
}
2481
2482
/* Can we apply isl_space_uncurry to "space"?
2483
 * That is, does it have a nested relation in its range?
2484
 */
2485
isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)
2486
1.68k
{
2487
1.68k
  if (!space)
2488
0
    return isl_bool_error;
2489
1.68k
2490
1.68k
  return !!space->nested[1];
2491
1.68k
}
2492
2493
/* Given a space A -> (B -> C), return the corresponding space
2494
 * (A -> B) -> C.
2495
 */
2496
__isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)
2497
591
{
2498
591
  isl_space *dom, *ran;
2499
591
  isl_space *ran_dom, *ran_ran;
2500
591
2501
591
  if (!space)
2502
0
    return NULL;
2503
591
2504
591
  if (!isl_space_can_uncurry(space))
2505
591
    
isl_die0
(space->ctx, isl_error_invalid,
2506
591
      "space cannot be uncurried",
2507
591
      return isl_space_free(space));
2508
591
2509
591
  dom = isl_space_domain(isl_space_copy(space));
2510
591
  ran = isl_space_unwrap(isl_space_range(space));
2511
591
  ran_dom = isl_space_domain(isl_space_copy(ran));
2512
591
  ran_ran = isl_space_range(ran);
2513
591
  dom = isl_space_join(isl_space_from_domain(dom),
2514
591
         isl_space_from_range(ran_dom));
2515
591
  return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),
2516
591
          isl_space_from_range(ran_ran));
2517
591
}
2518
2519
isl_bool isl_space_has_named_params(__isl_keep isl_space *space)
2520
485k
{
2521
485k
  int i;
2522
485k
  unsigned off;
2523
485k
2524
485k
  if (!space)
2525
2
    return isl_bool_error;
2526
485k
  if (space->nparam == 0)
2527
218k
    return isl_bool_true;
2528
267k
  off = isl_space_offset(space, isl_dim_param);
2529
267k
  if (off + space->nparam > space->n_id)
2530
0
    return isl_bool_false;
2531
1.08M
  
for (i = 0; 267k
i < space->nparam;
++i819k
)
2532
819k
    if (!space->ids[off + i])
2533
0
      return isl_bool_false;
2534
267k
  return isl_bool_true;
2535
267k
}
2536
2537
/* Check that "space" has only named parameters, reporting an error
2538
 * if it does not.
2539
 */
2540
isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
2541
177k
{
2542
177k
  isl_bool named;
2543
177k
2544
177k
  named = isl_space_has_named_params(space);
2545
177k
  if (named < 0)
2546
0
    return isl_stat_error;
2547
177k
  if (!named)
2548
177k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
2549
177k
      "unaligned unnamed parameters", return isl_stat_error);
2550
177k
2551
177k
  return isl_stat_ok;
2552
177k
}
2553
2554
/* Align the initial parameters of dim1 to match the order in dim2.
2555
 */
2556
__isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
2557
  __isl_take isl_space *dim2)
2558
26.7k
{
2559
26.7k
  isl_reordering *exp;
2560
26.7k
2561
26.7k
  if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
2562
26.7k
    
isl_die0
(isl_space_get_ctx(dim1), isl_error_invalid,
2563
26.7k
      "parameter alignment requires named parameters",
2564
26.7k
      goto error);
2565
26.7k
2566
26.7k
  dim2 = isl_space_params(dim2);
2567
26.7k
  exp = isl_parameter_alignment_reordering(dim1, dim2);
2568
26.7k
  exp = isl_reordering_extend_space(exp, dim1);
2569
26.7k
  isl_space_free(dim2);
2570
26.7k
  if (!exp)
2571
2
    return NULL;
2572
26.7k
  dim1 = isl_space_copy(exp->dim);
2573
26.7k
  isl_reordering_free(exp);
2574
26.7k
  return dim1;
2575
0
error:
2576
0
  isl_space_free(dim1);
2577
0
  isl_space_free(dim2);
2578
0
  return NULL;
2579
26.7k
}
2580
2581
/* Given the space of set (domain), construct a space for a map
2582
 * with as domain the given space and as range the range of "model".
2583
 */
2584
__isl_give isl_space *isl_space_extend_domain_with_range(
2585
  __isl_take isl_space *space, __isl_take isl_space *model)
2586
73.2k
{
2587
73.2k
  if (!model)
2588
0
    goto error;
2589
73.2k
2590
73.2k
  space = isl_space_from_domain(space);
2591
73.2k
  space = isl_space_add_dims(space, isl_dim_out,
2592
73.2k
            isl_space_dim(model, isl_dim_out));
2593
73.2k
  if (isl_space_has_tuple_id(model, isl_dim_out))
2594
125
    space = isl_space_set_tuple_id(space, isl_dim_out,
2595
125
        isl_space_get_tuple_id(model, isl_dim_out));
2596
73.2k
  if (!space)
2597
0
    goto error;
2598
73.2k
  if (model->nested[1]) {
2599
1
    isl_space *nested = isl_space_copy(model->nested[1]);
2600
1
    int n_nested, n_space;
2601
1
    nested = isl_space_align_params(nested, isl_space_copy(space));
2602
1
    n_nested = isl_space_dim(nested, isl_dim_param);
2603
1
    n_space = isl_space_dim(space, isl_dim_param);
2604
1
    if (n_nested > n_space)
2605
0
      nested = isl_space_drop_dims(nested, isl_dim_param,
2606
0
            n_space, n_nested - n_space);
2607
1
    if (!nested)
2608
0
      goto error;
2609
1
    space->nested[1] = nested;
2610
1
  }
2611
73.2k
  isl_space_free(model);
2612
73.2k
  return space;
2613
0
error:
2614
0
  isl_space_free(model);
2615
0
  isl_space_free(space);
2616
0
  return NULL;
2617
73.2k
}
2618
2619
/* Compare the "type" dimensions of two isl_spaces.
2620
 *
2621
 * The order is fairly arbitrary.
2622
 */
2623
static int isl_space_cmp_type(__isl_keep isl_space *space1,
2624
  __isl_keep isl_space *space2, enum isl_dim_type type)
2625
1.45M
{
2626
1.45M
  int cmp;
2627
1.45M
  isl_space *nested1, *nested2;
2628
1.45M
2629
1.45M
  if (isl_space_dim(space1, type) != isl_space_dim(space2, type))
2630
0
    return isl_space_dim(space1, type) -
2631
0
      isl_space_dim(space2, type);
2632
1.45M
2633
1.45M
  cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));
2634
1.45M
  if (cmp != 0)
2635
0
    return cmp;
2636
1.45M
2637
1.45M
  nested1 = nested(space1, type);
2638
1.45M
  nested2 = nested(space2, type);
2639
1.45M
  if (!nested1 != !nested2)
2640
0
    return !nested1 - !nested2;
2641
1.45M
2642
1.45M
  if (nested1)
2643
113k
    return isl_space_cmp(nested1, nested2);
2644
1.34M
2645
1.34M
  return 0;
2646
1.34M
}
2647
2648
/* Compare two isl_spaces.
2649
 *
2650
 * The order is fairly arbitrary.
2651
 */
2652
int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)
2653
1.59M
{
2654
1.59M
  int i;
2655
1.59M
  int cmp;
2656
1.59M
2657
1.59M
  if (space1 == space2)
2658
1.10M
    return 0;
2659
486k
  if (!space1)
2660
0
    return -1;
2661
486k
  if (!space2)
2662
0
    return 1;
2663
486k
2664
486k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_param);
2665
486k
  if (cmp != 0)
2666
0
    return cmp;
2667
486k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_in);
2668
486k
  if (cmp != 0)
2669
0
    return cmp;
2670
486k
  cmp = isl_space_cmp_type(space1, space2, isl_dim_out);
2671
486k
  if (cmp != 0)
2672
0
    return cmp;
2673
486k
2674
486k
  if (!space1->ids && 
!space2->ids128k
)
2675
128k
    return 0;
2676
357k
2677
3.65M
  
for (i = 0; 357k
i < n(space1, isl_dim_param);
++i3.29M
) {
2678
3.29M
    cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),
2679
3.29M
         get_id(space2, isl_dim_param, i));
2680
3.29M
    if (cmp != 0)
2681
0
      return cmp;
2682
3.29M
  }
2683
357k
2684
357k
  return 0;
2685
357k
}