Coverage Report

Created: 2018-02-20 23:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_map.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 * Copyright 2012-2014 Ecole Normale Superieure
5
 * Copyright 2014      INRIA Rocquencourt
6
 * Copyright 2016      INRIA Paris
7
 * Copyright 2016      Sven Verdoolaege
8
 *
9
 * Use of this software is governed by the MIT license
10
 *
11
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
12
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
13
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
14
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
15
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
16
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
17
 * B.P. 105 - 78153 Le Chesnay, France
18
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
19
 * CS 42112, 75589 Paris Cedex 12, France
20
 */
21
22
#include <string.h>
23
#include <isl_ctx_private.h>
24
#include <isl_map_private.h>
25
#include <isl_blk.h>
26
#include <isl/constraint.h>
27
#include "isl_space_private.h"
28
#include "isl_equalities.h"
29
#include <isl_lp_private.h>
30
#include <isl_seq.h>
31
#include <isl/set.h>
32
#include <isl/map.h>
33
#include <isl_reordering.h>
34
#include "isl_sample.h"
35
#include <isl_sort.h>
36
#include "isl_tab.h"
37
#include <isl/vec.h>
38
#include <isl_mat_private.h>
39
#include <isl_vec_private.h>
40
#include <isl_dim_map.h>
41
#include <isl_local_space_private.h>
42
#include <isl_aff_private.h>
43
#include <isl_options_private.h>
44
#include <isl_morph.h>
45
#include <isl_val_private.h>
46
47
#include <bset_to_bmap.c>
48
#include <bset_from_bmap.c>
49
#include <set_to_map.c>
50
#include <set_from_map.c>
51
52
static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
53
357k
{
54
357k
  switch (type) {
55
357k
  
case isl_dim_param: return dim->nparam8.18k
;
56
357k
  
case isl_dim_in:  return dim->n_in68.1k
;
57
357k
  
case isl_dim_out: return dim->n_out280k
;
58
357k
  
case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out115
;
59
357k
  
default:    return 00
;
60
0
  }
61
0
}
62
63
static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
64
121k
{
65
121k
  switch (type) {
66
121k
  
case isl_dim_param: return 1380
;
67
121k
  
case isl_dim_in:  return 1 + dim->nparam13.6k
;
68
121k
  
case isl_dim_out: return 1 + dim->nparam + dim->n_in107k
;
69
121k
  
default:    return 00
;
70
0
  }
71
0
}
72
73
unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
74
        enum isl_dim_type type)
75
44.4M
{
76
44.4M
  if (!bmap)
77
0
    return 0;
78
44.4M
  switch (type) {
79
44.4M
  
case isl_dim_cst: return 10
;
80
44.4M
  case isl_dim_param:
81
42.1M
  case isl_dim_in:
82
42.1M
  case isl_dim_out: return isl_space_dim(bmap->dim, type);
83
42.1M
  
case isl_dim_div: return bmap->n_div2.06M
;
84
42.1M
  
case isl_dim_all: return isl_basic_map_total_dim(bmap)285k
;
85
42.1M
  
default:    return 00
;
86
0
  }
87
0
}
88
89
/* Return the space of "map".
90
 */
91
__isl_keep isl_space *isl_map_peek_space(__isl_keep const isl_map *map)
92
3.91M
{
93
3.91M
  return map ? 
map->dim3.91M
: NULL;
94
3.91M
}
95
96
unsigned isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
97
197k
{
98
197k
  return map ? n(map->dim, type) : 
00
;
99
197k
}
100
101
unsigned isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
102
159k
{
103
159k
  return set ? n(set->dim, type) : 
00
;
104
159k
}
105
106
unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
107
          enum isl_dim_type type)
108
1.18M
{
109
1.18M
  isl_space *space;
110
1.18M
111
1.18M
  if (!bmap)
112
0
    return 0;
113
1.18M
114
1.18M
  space = bmap->dim;
115
1.18M
  switch (type) {
116
1.18M
  
case isl_dim_cst: return 00
;
117
1.18M
  
case isl_dim_param: return 14.23k
;
118
1.18M
  
case isl_dim_in:  return 1 + space->nparam229k
;
119
1.18M
  
case isl_dim_out: return 1 + space->nparam + space->n_in729k
;
120
1.18M
  case isl_dim_div: return 1 + space->nparam + space->n_in +
121
217k
                space->n_out;
122
1.18M
  
default:    return 00
;
123
0
  }
124
0
}
125
126
unsigned isl_basic_set_offset(__isl_keep isl_basic_set *bset,
127
          enum isl_dim_type type)
128
350
{
129
350
  return isl_basic_map_offset(bset, type);
130
350
}
131
132
static unsigned map_offset(__isl_keep isl_map *map, enum isl_dim_type type)
133
1.74k
{
134
1.74k
  return pos(map->dim, type);
135
1.74k
}
136
137
unsigned isl_basic_set_dim(__isl_keep isl_basic_set *bset,
138
        enum isl_dim_type type)
139
2.76M
{
140
2.76M
  return isl_basic_map_dim(bset, type);
141
2.76M
}
142
143
unsigned isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
144
1.48M
{
145
1.48M
  return isl_basic_set_dim(bset, isl_dim_set);
146
1.48M
}
147
148
unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
149
725k
{
150
725k
  return isl_basic_set_dim(bset, isl_dim_param);
151
725k
}
152
153
unsigned isl_basic_set_total_dim(__isl_keep const isl_basic_set *bset)
154
3.05M
{
155
3.05M
  if (!bset)
156
0
    return 0;
157
3.05M
  return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
158
3.05M
}
159
160
unsigned isl_set_n_dim(__isl_keep isl_set *set)
161
108k
{
162
108k
  return isl_set_dim(set, isl_dim_set);
163
108k
}
164
165
unsigned isl_set_n_param(__isl_keep isl_set *set)
166
553
{
167
553
  return isl_set_dim(set, isl_dim_param);
168
553
}
169
170
unsigned isl_basic_map_n_in(__isl_keep const isl_basic_map *bmap)
171
0
{
172
0
  return bmap ? bmap->dim->n_in : 0;
173
0
}
174
175
unsigned isl_basic_map_n_out(__isl_keep const isl_basic_map *bmap)
176
0
{
177
0
  return bmap ? bmap->dim->n_out : 0;
178
0
}
179
180
unsigned isl_basic_map_n_param(__isl_keep const isl_basic_map *bmap)
181
0
{
182
0
  return bmap ? bmap->dim->nparam : 0;
183
0
}
184
185
unsigned isl_basic_map_n_div(__isl_keep const isl_basic_map *bmap)
186
0
{
187
0
  return bmap ? bmap->n_div : 0;
188
0
}
189
190
unsigned isl_basic_map_total_dim(__isl_keep const isl_basic_map *bmap)
191
53.1M
{
192
53.1M
  return bmap ? isl_space_dim(bmap->dim, isl_dim_all) + bmap->n_div : 
00
;
193
53.1M
}
194
195
unsigned isl_map_n_in(__isl_keep const isl_map *map)
196
0
{
197
0
  return map ? map->dim->n_in : 0;
198
0
}
199
200
unsigned isl_map_n_out(__isl_keep const isl_map *map)
201
0
{
202
0
  return map ? map->dim->n_out : 0;
203
0
}
204
205
unsigned isl_map_n_param(__isl_keep const isl_map *map)
206
0
{
207
0
  return map ? map->dim->nparam : 0;
208
0
}
209
210
/* Return the number of equality constraints in the description of "bmap".
211
 * Return -1 on error.
212
 */
213
int isl_basic_map_n_equality(__isl_keep isl_basic_map *bmap)
214
343k
{
215
343k
  if (!bmap)
216
0
    return -1;
217
343k
  return bmap->n_eq;
218
343k
}
219
220
/* Return the number of equality constraints in the description of "bset".
221
 * Return -1 on error.
222
 */
223
int isl_basic_set_n_equality(__isl_keep isl_basic_set *bset)
224
1.77k
{
225
1.77k
  return isl_basic_map_n_equality(bset_to_bmap(bset));
226
1.77k
}
227
228
/* Return the number of inequality constraints in the description of "bmap".
229
 * Return -1 on error.
230
 */
231
int isl_basic_map_n_inequality(__isl_keep isl_basic_map *bmap)
232
368k
{
233
368k
  if (!bmap)
234
0
    return -1;
235
368k
  return bmap->n_ineq;
236
368k
}
237
238
/* Return the number of inequality constraints in the description of "bset".
239
 * Return -1 on error.
240
 */
241
int isl_basic_set_n_inequality(__isl_keep isl_basic_set *bset)
242
1.74k
{
243
1.74k
  return isl_basic_map_n_inequality(bset_to_bmap(bset));
244
1.74k
}
245
246
/* Do "bmap1" and "bmap2" have the same parameters?
247
 */
248
static isl_bool isl_basic_map_has_equal_params(__isl_keep isl_basic_map *bmap1,
249
  __isl_keep isl_basic_map *bmap2)
250
626k
{
251
626k
  isl_space *space1, *space2;
252
626k
253
626k
  space1 = isl_basic_map_peek_space(bmap1);
254
626k
  space2 = isl_basic_map_peek_space(bmap2);
255
626k
  return isl_space_has_equal_params(space1, space2);
256
626k
}
257
258
/* Do "map1" and "map2" have the same parameters?
259
 */
260
isl_bool isl_map_has_equal_params(__isl_keep isl_map *map1,
261
  __isl_keep isl_map *map2)
262
1.22M
{
263
1.22M
  isl_space *space1, *space2;
264
1.22M
265
1.22M
  space1 = isl_map_peek_space(map1);
266
1.22M
  space2 = isl_map_peek_space(map2);
267
1.22M
  return isl_space_has_equal_params(space1, space2);
268
1.22M
}
269
270
/* Do "map" and "set" have the same parameters?
271
 */
272
static isl_bool isl_map_set_has_equal_params(__isl_keep isl_map *map,
273
  __isl_keep isl_set *set)
274
11.9k
{
275
11.9k
  return isl_map_has_equal_params(map, set_to_map(set));
276
11.9k
}
277
278
isl_bool isl_map_compatible_domain(__isl_keep isl_map *map,
279
  __isl_keep isl_set *set)
280
105k
{
281
105k
  isl_bool m;
282
105k
  if (!map || !set)
283
0
    return isl_bool_error;
284
105k
  m = isl_map_has_equal_params(map, set_to_map(set));
285
105k
  if (m < 0 || !m)
286
0
    return m;
287
105k
  return isl_space_tuple_is_equal(map->dim, isl_dim_in,
288
105k
          set->dim, isl_dim_set);
289
105k
}
290
291
isl_bool isl_basic_map_compatible_domain(__isl_keep isl_basic_map *bmap,
292
  __isl_keep isl_basic_set *bset)
293
76.6k
{
294
76.6k
  isl_bool m;
295
76.6k
  if (!bmap || !bset)
296
0
    return isl_bool_error;
297
76.6k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
298
76.6k
  if (m < 0 || !m)
299
0
    return m;
300
76.6k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_in,
301
76.6k
          bset->dim, isl_dim_set);
302
76.6k
}
303
304
isl_bool isl_map_compatible_range(__isl_keep isl_map *map,
305
  __isl_keep isl_set *set)
306
5.05k
{
307
5.05k
  isl_bool m;
308
5.05k
  if (!map || !set)
309
0
    return isl_bool_error;
310
5.05k
  m = isl_map_has_equal_params(map, set_to_map(set));
311
5.05k
  if (m < 0 || !m)
312
0
    return m;
313
5.05k
  return isl_space_tuple_is_equal(map->dim, isl_dim_out,
314
5.05k
          set->dim, isl_dim_set);
315
5.05k
}
316
317
isl_bool isl_basic_map_compatible_range(__isl_keep isl_basic_map *bmap,
318
  __isl_keep isl_basic_set *bset)
319
6.52k
{
320
6.52k
  isl_bool m;
321
6.52k
  if (!bmap || !bset)
322
0
    return isl_bool_error;
323
6.52k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
324
6.52k
  if (m < 0 || !m)
325
0
    return m;
326
6.52k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_out,
327
6.52k
          bset->dim, isl_dim_set);
328
6.52k
}
329
330
isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
331
4.90M
{
332
4.90M
  return bmap ? bmap->ctx : NULL;
333
4.90M
}
334
335
isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
336
238k
{
337
238k
  return bset ? bset->ctx : NULL;
338
238k
}
339
340
isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
341
61.1k
{
342
61.1k
  return map ? map->ctx : NULL;
343
61.1k
}
344
345
isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
346
398k
{
347
398k
  return set ? set->ctx : NULL;
348
398k
}
349
350
/* Return the space of "bmap".
351
 */
352
__isl_keep isl_space *isl_basic_map_peek_space(
353
  __isl_keep const isl_basic_map *bmap)
354
5.76M
{
355
5.76M
  return bmap ? bmap->dim : NULL;
356
5.76M
}
357
358
/* Return the space of "bset".
359
 */
360
__isl_keep isl_space *isl_basic_set_peek_space(__isl_keep isl_basic_set *bset)
361
0
{
362
0
  return isl_basic_map_peek_space(bset_to_bmap(bset));
363
0
}
364
365
__isl_give isl_space *isl_basic_map_get_space(__isl_keep isl_basic_map *bmap)
366
662k
{
367
662k
  return isl_space_copy(isl_basic_map_peek_space(bmap));
368
662k
}
369
370
__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
371
199k
{
372
199k
  return isl_basic_map_get_space(bset_to_bmap(bset));
373
199k
}
374
375
/* Extract the divs in "bmap" as a matrix.
376
 */
377
__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap)
378
77.9k
{
379
77.9k
  int i;
380
77.9k
  isl_ctx *ctx;
381
77.9k
  isl_mat *div;
382
77.9k
  unsigned total;
383
77.9k
  unsigned cols;
384
77.9k
385
77.9k
  if (!bmap)
386
0
    return NULL;
387
77.9k
388
77.9k
  ctx = isl_basic_map_get_ctx(bmap);
389
77.9k
  total = isl_space_dim(bmap->dim, isl_dim_all);
390
77.9k
  cols = 1 + 1 + total + bmap->n_div;
391
77.9k
  div = isl_mat_alloc(ctx, bmap->n_div, cols);
392
77.9k
  if (!div)
393
0
    return NULL;
394
77.9k
395
90.6k
  
for (i = 0; 77.9k
i < bmap->n_div;
++i12.6k
)
396
12.6k
    isl_seq_cpy(div->row[i], bmap->div[i], cols);
397
77.9k
398
77.9k
  return div;
399
77.9k
}
400
401
/* Extract the divs in "bset" as a matrix.
402
 */
403
__isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset)
404
0
{
405
0
  return isl_basic_map_get_divs(bset);
406
0
}
407
408
__isl_give isl_local_space *isl_basic_map_get_local_space(
409
  __isl_keep isl_basic_map *bmap)
410
59.1k
{
411
59.1k
  isl_mat *div;
412
59.1k
413
59.1k
  if (!bmap)
414
0
    return NULL;
415
59.1k
416
59.1k
  div = isl_basic_map_get_divs(bmap);
417
59.1k
  return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div);
418
59.1k
}
419
420
__isl_give isl_local_space *isl_basic_set_get_local_space(
421
  __isl_keep isl_basic_set *bset)
422
7.22k
{
423
7.22k
  return isl_basic_map_get_local_space(bset);
424
7.22k
}
425
426
/* For each known div d = floor(f/m), add the constraints
427
 *
428
 *    f - m d >= 0
429
 *    -(f-(m-1)) + m d >= 0
430
 *
431
 * Do not finalize the result.
432
 */
433
static __isl_give isl_basic_map *add_known_div_constraints(
434
  __isl_take isl_basic_map *bmap)
435
135k
{
436
135k
  int i;
437
135k
  unsigned n_div;
438
135k
439
135k
  if (!bmap)
440
0
    return NULL;
441
135k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
442
135k
  if (n_div == 0)
443
103k
    return bmap;
444
32.3k
  bmap = isl_basic_map_cow(bmap);
445
32.3k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div);
446
32.3k
  if (!bmap)
447
0
    return NULL;
448
67.5k
  
for (i = 0; 32.3k
i < n_div;
++i35.1k
) {
449
35.1k
    if (isl_int_is_zero(bmap->div[i][0]))
450
35.1k
      
continue348
;
451
34.8k
    if (isl_basic_map_add_div_constraints(bmap, i) < 0)
452
0
      return isl_basic_map_free(bmap);
453
34.8k
  }
454
32.3k
455
32.3k
  return bmap;
456
32.3k
}
457
458
__isl_give isl_basic_map *isl_basic_map_from_local_space(
459
  __isl_take isl_local_space *ls)
460
132k
{
461
132k
  int i;
462
132k
  int n_div;
463
132k
  isl_basic_map *bmap;
464
132k
465
132k
  if (!ls)
466
0
    return NULL;
467
132k
468
132k
  n_div = isl_local_space_dim(ls, isl_dim_div);
469
132k
  bmap = isl_basic_map_alloc_space(isl_local_space_get_space(ls),
470
132k
          n_div, 0, 2 * n_div);
471
132k
472
164k
  for (i = 0; i < n_div; 
++i31.6k
)
473
31.6k
    if (isl_basic_map_alloc_div(bmap) < 0)
474
0
      goto error;
475
132k
476
164k
  
for (i = 0; 132k
i < n_div;
++i31.6k
)
477
31.6k
    isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col);
478
132k
  bmap = add_known_div_constraints(bmap);
479
132k
          
480
132k
  isl_local_space_free(ls);
481
132k
  return bmap;
482
0
error:
483
0
  isl_local_space_free(ls);
484
0
  isl_basic_map_free(bmap);
485
0
  return NULL;
486
132k
}
487
488
__isl_give isl_basic_set *isl_basic_set_from_local_space(
489
  __isl_take isl_local_space *ls)
490
20.5k
{
491
20.5k
  return isl_basic_map_from_local_space(ls);
492
20.5k
}
493
494
__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
495
704k
{
496
704k
  return isl_space_copy(isl_map_peek_space(map));
497
704k
}
498
499
__isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set)
500
157k
{
501
157k
  if (!set)
502
2
    return NULL;
503
157k
  return isl_space_copy(set->dim);
504
157k
}
505
506
__isl_give isl_basic_map *isl_basic_map_set_tuple_name(
507
  __isl_take isl_basic_map *bmap, enum isl_dim_type type, const char *s)
508
0
{
509
0
  bmap = isl_basic_map_cow(bmap);
510
0
  if (!bmap)
511
0
    return NULL;
512
0
  bmap->dim = isl_space_set_tuple_name(bmap->dim, type, s);
513
0
  if (!bmap->dim)
514
0
    goto error;
515
0
  bmap = isl_basic_map_finalize(bmap);
516
0
  return bmap;
517
0
error:
518
0
  isl_basic_map_free(bmap);
519
0
  return NULL;
520
0
}
521
522
__isl_give isl_basic_set *isl_basic_set_set_tuple_name(
523
  __isl_take isl_basic_set *bset, const char *s)
524
0
{
525
0
  return isl_basic_map_set_tuple_name(bset, isl_dim_set, s);
526
0
}
527
528
const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap,
529
  enum isl_dim_type type)
530
0
{
531
0
  return bmap ? isl_space_get_tuple_name(bmap->dim, type) : NULL;
532
0
}
533
534
__isl_give isl_map *isl_map_set_tuple_name(__isl_take isl_map *map,
535
  enum isl_dim_type type, const char *s)
536
0
{
537
0
  int i;
538
0
539
0
  map = isl_map_cow(map);
540
0
  if (!map)
541
0
    return NULL;
542
0
543
0
  map->dim = isl_space_set_tuple_name(map->dim, type, s);
544
0
  if (!map->dim)
545
0
    goto error;
546
0
547
0
  for (i = 0; i < map->n; ++i) {
548
0
    map->p[i] = isl_basic_map_set_tuple_name(map->p[i], type, s);
549
0
    if (!map->p[i])
550
0
      goto error;
551
0
  }
552
0
553
0
  return map;
554
0
error:
555
0
  isl_map_free(map);
556
0
  return NULL;
557
0
}
558
559
/* Replace the identifier of the tuple of type "type" by "id".
560
 */
561
__isl_give isl_basic_map *isl_basic_map_set_tuple_id(
562
  __isl_take isl_basic_map *bmap,
563
  enum isl_dim_type type, __isl_take isl_id *id)
564
0
{
565
0
  bmap = isl_basic_map_cow(bmap);
566
0
  if (!bmap)
567
0
    goto error;
568
0
  bmap->dim = isl_space_set_tuple_id(bmap->dim, type, id);
569
0
  if (!bmap->dim)
570
0
    return isl_basic_map_free(bmap);
571
0
  bmap = isl_basic_map_finalize(bmap);
572
0
  return bmap;
573
0
error:
574
0
  isl_id_free(id);
575
0
  return NULL;
576
0
}
577
578
/* Replace the identifier of the tuple by "id".
579
 */
580
__isl_give isl_basic_set *isl_basic_set_set_tuple_id(
581
  __isl_take isl_basic_set *bset, __isl_take isl_id *id)
582
0
{
583
0
  return isl_basic_map_set_tuple_id(bset, isl_dim_set, id);
584
0
}
585
586
/* Does the input or output tuple have a name?
587
 */
588
isl_bool isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type)
589
111
{
590
111
  return map ? isl_space_has_tuple_name(map->dim, type) : 
isl_bool_error0
;
591
111
}
592
593
const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
594
  enum isl_dim_type type)
595
24
{
596
24
  return map ? isl_space_get_tuple_name(map->dim, type) : NULL;
597
24
}
598
599
__isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set,
600
  const char *s)
601
0
{
602
0
  return set_from_map(isl_map_set_tuple_name(set_to_map(set),
603
0
            isl_dim_set, s));
604
0
}
605
606
__isl_give isl_map *isl_map_set_tuple_id(__isl_take isl_map *map,
607
  enum isl_dim_type type, __isl_take isl_id *id)
608
13.1k
{
609
13.1k
  map = isl_map_cow(map);
610
13.1k
  if (!map)
611
0
    goto error;
612
13.1k
613
13.1k
  map->dim = isl_space_set_tuple_id(map->dim, type, id);
614
13.1k
615
13.1k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
616
0
error:
617
0
  isl_id_free(id);
618
0
  return NULL;
619
13.1k
}
620
621
__isl_give isl_set *isl_set_set_tuple_id(__isl_take isl_set *set,
622
  __isl_take isl_id *id)
623
2.45k
{
624
2.45k
  return isl_map_set_tuple_id(set, isl_dim_set, id);
625
2.45k
}
626
627
__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
628
  enum isl_dim_type type)
629
5.89k
{
630
5.89k
  map = isl_map_cow(map);
631
5.89k
  if (!map)
632
0
    return NULL;
633
5.89k
634
5.89k
  map->dim = isl_space_reset_tuple_id(map->dim, type);
635
5.89k
636
5.89k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
637
5.89k
}
638
639
__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
640
5.89k
{
641
5.89k
  return isl_map_reset_tuple_id(set, isl_dim_set);
642
5.89k
}
643
644
isl_bool isl_map_has_tuple_id(__isl_keep isl_map *map, enum isl_dim_type type)
645
56
{
646
56
  return map ? isl_space_has_tuple_id(map->dim, type) : 
isl_bool_error0
;
647
56
}
648
649
__isl_give isl_id *isl_map_get_tuple_id(__isl_keep isl_map *map,
650
  enum isl_dim_type type)
651
27.8k
{
652
27.8k
  return map ? 
isl_space_get_tuple_id(map->dim, type)27.8k
: NULL;
653
27.8k
}
654
655
isl_bool isl_set_has_tuple_id(__isl_keep isl_set *set)
656
0
{
657
0
  return isl_map_has_tuple_id(set, isl_dim_set);
658
0
}
659
660
__isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
661
542
{
662
542
  return isl_map_get_tuple_id(set, isl_dim_set);
663
542
}
664
665
/* Does the set tuple have a name?
666
 */
667
isl_bool isl_set_has_tuple_name(__isl_keep isl_set *set)
668
144
{
669
144
  if (!set)
670
0
    return isl_bool_error;
671
144
  return isl_space_has_tuple_name(set->dim, isl_dim_set);
672
144
}
673
674
675
const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
676
0
{
677
0
  return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL;
678
0
}
679
680
const char *isl_set_get_tuple_name(__isl_keep isl_set *set)
681
171
{
682
171
  return set ? isl_space_get_tuple_name(set->dim, isl_dim_set) : NULL;
683
171
}
684
685
const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap,
686
  enum isl_dim_type type, unsigned pos)
687
0
{
688
0
  return bmap ? isl_space_get_dim_name(bmap->dim, type, pos) : NULL;
689
0
}
690
691
const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset,
692
  enum isl_dim_type type, unsigned pos)
693
0
{
694
0
  return bset ? isl_space_get_dim_name(bset->dim, type, pos) : NULL;
695
0
}
696
697
/* Does the given dimension have a name?
698
 */
699
isl_bool isl_map_has_dim_name(__isl_keep isl_map *map,
700
  enum isl_dim_type type, unsigned pos)
701
0
{
702
0
  if (!map)
703
0
    return isl_bool_error;
704
0
  return isl_space_has_dim_name(map->dim, type, pos);
705
0
}
706
707
const char *isl_map_get_dim_name(__isl_keep isl_map *map,
708
  enum isl_dim_type type, unsigned pos)
709
0
{
710
0
  return map ? isl_space_get_dim_name(map->dim, type, pos) : NULL;
711
0
}
712
713
const char *isl_set_get_dim_name(__isl_keep isl_set *set,
714
  enum isl_dim_type type, unsigned pos)
715
2
{
716
2
  return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL;
717
2
}
718
719
/* Does the given dimension have a name?
720
 */
721
isl_bool isl_set_has_dim_name(__isl_keep isl_set *set,
722
  enum isl_dim_type type, unsigned pos)
723
0
{
724
0
  if (!set)
725
0
    return isl_bool_error;
726
0
  return isl_space_has_dim_name(set->dim, type, pos);
727
0
}
728
729
__isl_give isl_basic_map *isl_basic_map_set_dim_name(
730
  __isl_take isl_basic_map *bmap,
731
  enum isl_dim_type type, unsigned pos, const char *s)
732
0
{
733
0
  bmap = isl_basic_map_cow(bmap);
734
0
  if (!bmap)
735
0
    return NULL;
736
0
  bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s);
737
0
  if (!bmap->dim)
738
0
    goto error;
739
0
  return isl_basic_map_finalize(bmap);
740
0
error:
741
0
  isl_basic_map_free(bmap);
742
0
  return NULL;
743
0
}
744
745
__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
746
  enum isl_dim_type type, unsigned pos, const char *s)
747
0
{
748
0
  int i;
749
0
750
0
  map = isl_map_cow(map);
751
0
  if (!map)
752
0
    return NULL;
753
0
754
0
  map->dim = isl_space_set_dim_name(map->dim, type, pos, s);
755
0
  if (!map->dim)
756
0
    goto error;
757
0
758
0
  for (i = 0; i < map->n; ++i) {
759
0
    map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s);
760
0
    if (!map->p[i])
761
0
      goto error;
762
0
  }
763
0
764
0
  return map;
765
0
error:
766
0
  isl_map_free(map);
767
0
  return NULL;
768
0
}
769
770
__isl_give isl_basic_set *isl_basic_set_set_dim_name(
771
  __isl_take isl_basic_set *bset,
772
  enum isl_dim_type type, unsigned pos, const char *s)
773
0
{
774
0
  return bset_from_bmap(isl_basic_map_set_dim_name(bset_to_bmap(bset),
775
0
              type, pos, s));
776
0
}
777
778
__isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set,
779
  enum isl_dim_type type, unsigned pos, const char *s)
780
0
{
781
0
  return set_from_map(isl_map_set_dim_name(set_to_map(set),
782
0
              type, pos, s));
783
0
}
784
785
isl_bool isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
786
  enum isl_dim_type type, unsigned pos)
787
0
{
788
0
  if (!bmap)
789
0
    return isl_bool_error;
790
0
  return isl_space_has_dim_id(bmap->dim, type, pos);
791
0
}
792
793
__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset,
794
  enum isl_dim_type type, unsigned pos)
795
0
{
796
0
  return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL;
797
0
}
798
799
isl_bool isl_map_has_dim_id(__isl_keep isl_map *map,
800
  enum isl_dim_type type, unsigned pos)
801
0
{
802
0
  return map ? isl_space_has_dim_id(map->dim, type, pos) : isl_bool_error;
803
0
}
804
805
__isl_give isl_id *isl_map_get_dim_id(__isl_keep isl_map *map,
806
  enum isl_dim_type type, unsigned pos)
807
6.20k
{
808
6.20k
  return map ? isl_space_get_dim_id(map->dim, type, pos) : NULL;
809
6.20k
}
810
811
isl_bool isl_set_has_dim_id(__isl_keep isl_set *set,
812
  enum isl_dim_type type, unsigned pos)
813
0
{
814
0
  return isl_map_has_dim_id(set, type, pos);
815
0
}
816
817
__isl_give isl_id *isl_set_get_dim_id(__isl_keep isl_set *set,
818
  enum isl_dim_type type, unsigned pos)
819
6.03k
{
820
6.03k
  return isl_map_get_dim_id(set, type, pos);
821
6.03k
}
822
823
__isl_give isl_map *isl_map_set_dim_id(__isl_take isl_map *map,
824
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
825
6.91k
{
826
6.91k
  map = isl_map_cow(map);
827
6.91k
  if (!map)
828
0
    goto error;
829
6.91k
830
6.91k
  map->dim = isl_space_set_dim_id(map->dim, type, pos, id);
831
6.91k
832
6.91k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
833
0
error:
834
0
  isl_id_free(id);
835
0
  return NULL;
836
6.91k
}
837
838
__isl_give isl_set *isl_set_set_dim_id(__isl_take isl_set *set,
839
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
840
5.85k
{
841
5.85k
  return isl_map_set_dim_id(set, type, pos, id);
842
5.85k
}
843
844
int isl_map_find_dim_by_id(__isl_keep isl_map *map, enum isl_dim_type type,
845
  __isl_keep isl_id *id)
846
118
{
847
118
  if (!map)
848
0
    return -1;
849
118
  return isl_space_find_dim_by_id(map->dim, type, id);
850
118
}
851
852
int isl_set_find_dim_by_id(__isl_keep isl_set *set, enum isl_dim_type type,
853
  __isl_keep isl_id *id)
854
118
{
855
118
  return isl_map_find_dim_by_id(set, type, id);
856
118
}
857
858
/* Return the position of the dimension of the given type and name
859
 * in "bmap".
860
 * Return -1 if no such dimension can be found.
861
 */
862
int isl_basic_map_find_dim_by_name(__isl_keep isl_basic_map *bmap,
863
  enum isl_dim_type type, const char *name)
864
0
{
865
0
  if (!bmap)
866
0
    return -1;
867
0
  return isl_space_find_dim_by_name(bmap->dim, type, name);
868
0
}
869
870
int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type,
871
  const char *name)
872
871
{
873
871
  if (!map)
874
0
    return -1;
875
871
  return isl_space_find_dim_by_name(map->dim, type, name);
876
871
}
877
878
int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
879
  const char *name)
880
871
{
881
871
  return isl_map_find_dim_by_name(set, type, name);
882
871
}
883
884
/* Check whether equality i of bset is a pure stride constraint
885
 * on a single dimension, i.e., of the form
886
 *
887
 *  v = k e
888
 *
889
 * with k a constant and e an existentially quantified variable.
890
 */
891
isl_bool isl_basic_set_eq_is_stride(__isl_keep isl_basic_set *bset, int i)
892
0
{
893
0
  unsigned nparam;
894
0
  unsigned d;
895
0
  unsigned n_div;
896
0
  int pos1;
897
0
  int pos2;
898
0
899
0
  if (!bset)
900
0
    return isl_bool_error;
901
0
902
0
  if (!isl_int_is_zero(bset->eq[i][0]))
903
0
    return isl_bool_false;
904
0
905
0
  nparam = isl_basic_set_dim(bset, isl_dim_param);
906
0
  d = isl_basic_set_dim(bset, isl_dim_set);
907
0
  n_div = isl_basic_set_dim(bset, isl_dim_div);
908
0
909
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1, nparam) != -1)
910
0
    return isl_bool_false;
911
0
  pos1 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam, d);
912
0
  if (pos1 == -1)
913
0
    return isl_bool_false;
914
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + pos1 + 1,
915
0
          d - pos1 - 1) != -1)
916
0
    return isl_bool_false;
917
0
918
0
  pos2 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d, n_div);
919
0
  if (pos2 == -1)
920
0
    return isl_bool_false;
921
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d  + pos2 + 1,
922
0
           n_div - pos2 - 1) != -1)
923
0
    return isl_bool_false;
924
0
  if (!isl_int_is_one(bset->eq[i][1 + nparam + pos1]) &&
925
0
      !isl_int_is_negone(bset->eq[i][1 + nparam + pos1]))
926
0
    return isl_bool_false;
927
0
928
0
  return isl_bool_true;
929
0
}
930
931
/* Reset the user pointer on all identifiers of parameters and tuples
932
 * of the space of "map".
933
 */
934
__isl_give isl_map *isl_map_reset_user(__isl_take isl_map *map)
935
0
{
936
0
  isl_space *space;
937
0
938
0
  space = isl_map_get_space(map);
939
0
  space = isl_space_reset_user(space);
940
0
  map = isl_map_reset_space(map, space);
941
0
942
0
  return map;
943
0
}
944
945
/* Reset the user pointer on all identifiers of parameters and tuples
946
 * of the space of "set".
947
 */
948
__isl_give isl_set *isl_set_reset_user(__isl_take isl_set *set)
949
0
{
950
0
  return isl_map_reset_user(set);
951
0
}
952
953
isl_bool isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
954
376k
{
955
376k
  if (!bmap)
956
0
    return isl_bool_error;
957
376k
  return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
958
376k
}
959
960
/* Has "map" been marked as a rational map?
961
 * In particular, have all basic maps in "map" been marked this way?
962
 * An empty map is not considered to be rational.
963
 * Maps where only some of the basic maps are marked rational
964
 * are not allowed.
965
 */
966
isl_bool isl_map_is_rational(__isl_keep isl_map *map)
967
8.51k
{
968
8.51k
  int i;
969
8.51k
  isl_bool rational;
970
8.51k
971
8.51k
  if (!map)
972
0
    return isl_bool_error;
973
8.51k
  if (map->n == 0)
974
0
    return isl_bool_false;
975
8.51k
  rational = isl_basic_map_is_rational(map->p[0]);
976
8.51k
  if (rational < 0)
977
0
    return rational;
978
9.14k
  
for (i = 1; 8.51k
i < map->n;
++i638
) {
979
638
    isl_bool rational_i;
980
638
981
638
    rational_i = isl_basic_map_is_rational(map->p[i]);
982
638
    if (rational_i < 0)
983
0
      return rational_i;
984
638
    if (rational != rational_i)
985
638
      
isl_die0
(isl_map_get_ctx(map), isl_error_unsupported,
986
638
        "mixed rational and integer basic maps "
987
638
        "not supported", return isl_bool_error);
988
638
  }
989
8.51k
990
8.51k
  return rational;
991
8.51k
}
992
993
/* Has "set" been marked as a rational set?
994
 * In particular, have all basic set in "set" been marked this way?
995
 * An empty set is not considered to be rational.
996
 * Sets where only some of the basic sets are marked rational
997
 * are not allowed.
998
 */
999
isl_bool isl_set_is_rational(__isl_keep isl_set *set)
1000
8.51k
{
1001
8.51k
  return isl_map_is_rational(set);
1002
8.51k
}
1003
1004
int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
1005
45.3k
{
1006
45.3k
  return isl_basic_map_is_rational(bset);
1007
45.3k
}
1008
1009
/* Does "bmap" contain any rational points?
1010
 *
1011
 * If "bmap" has an equality for each dimension, equating the dimension
1012
 * to an integer constant, then it has no rational points, even if it
1013
 * is marked as rational.
1014
 */
1015
isl_bool isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
1016
88.4k
{
1017
88.4k
  isl_bool has_rational = isl_bool_true;
1018
88.4k
  unsigned total;
1019
88.4k
1020
88.4k
  if (!bmap)
1021
0
    return isl_bool_error;
1022
88.4k
  if (isl_basic_map_plain_is_empty(bmap))
1023
2
    return isl_bool_false;
1024
88.4k
  if (!isl_basic_map_is_rational(bmap))
1025
88.3k
    return isl_bool_false;
1026
146
  bmap = isl_basic_map_copy(bmap);
1027
146
  bmap = isl_basic_map_implicit_equalities(bmap);
1028
146
  if (!bmap)
1029
0
    return isl_bool_error;
1030
146
  total = isl_basic_map_total_dim(bmap);
1031
146
  if (bmap->n_eq == total) {
1032
2
    int i, j;
1033
3
    for (i = 0; i < bmap->n_eq; 
++i1
) {
1034
2
      j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);
1035
2
      if (j < 0)
1036
0
        break;
1037
2
      if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
1038
2
          
!1
isl_int_is_negone1
(bmap->eq[i][1 + j]))
1039
2
        
break1
;
1040
1
      j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1,
1041
1
                total - j - 1);
1042
1
      if (j >= 0)
1043
0
        break;
1044
1
    }
1045
2
    if (i == bmap->n_eq)
1046
1
      has_rational = isl_bool_false;
1047
2
  }
1048
146
  isl_basic_map_free(bmap);
1049
146
1050
146
  return has_rational;
1051
146
}
1052
1053
/* Does "map" contain any rational points?
1054
 */
1055
isl_bool isl_map_has_rational(__isl_keep isl_map *map)
1056
75.5k
{
1057
75.5k
  int i;
1058
75.5k
  isl_bool has_rational;
1059
75.5k
1060
75.5k
  if (!map)
1061
0
    return isl_bool_error;
1062
163k
  
for (i = 0; 75.5k
i < map->n;
++i88.3k
) {
1063
88.4k
    has_rational = isl_basic_map_has_rational(map->p[i]);
1064
88.4k
    if (has_rational < 0 || has_rational)
1065
145
      return has_rational;
1066
88.4k
  }
1067
75.5k
  
return isl_bool_false75.4k
;
1068
75.5k
}
1069
1070
/* Does "set" contain any rational points?
1071
 */
1072
isl_bool isl_set_has_rational(__isl_keep isl_set *set)
1073
24.4k
{
1074
24.4k
  return isl_map_has_rational(set);
1075
24.4k
}
1076
1077
/* Is this basic set a parameter domain?
1078
 */
1079
isl_bool isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
1080
62
{
1081
62
  if (!bset)
1082
0
    return isl_bool_error;
1083
62
  return isl_space_is_params(bset->dim);
1084
62
}
1085
1086
/* Is this set a parameter domain?
1087
 */
1088
isl_bool isl_set_is_params(__isl_keep isl_set *set)
1089
62.1k
{
1090
62.1k
  if (!set)
1091
0
    return isl_bool_error;
1092
62.1k
  return isl_space_is_params(set->dim);
1093
62.1k
}
1094
1095
/* Is this map actually a parameter domain?
1096
 * Users should never call this function.  Outside of isl,
1097
 * a map can never be a parameter domain.
1098
 */
1099
isl_bool isl_map_is_params(__isl_keep isl_map *map)
1100
0
{
1101
0
  if (!map)
1102
0
    return isl_bool_error;
1103
0
  return isl_space_is_params(map->dim);
1104
0
}
1105
1106
static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
1107
    struct isl_basic_map *bmap, unsigned extra,
1108
    unsigned n_eq, unsigned n_ineq)
1109
4.62M
{
1110
4.62M
  int i;
1111
4.62M
  size_t row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + extra;
1112
4.62M
1113
4.62M
  bmap->ctx = ctx;
1114
4.62M
  isl_ctx_ref(ctx);
1115
4.62M
1116
4.62M
  bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
1117
4.62M
  if (isl_blk_is_error(bmap->block))
1118
0
    goto error;
1119
4.62M
1120
4.62M
  bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
1121
4.62M
  if ((n_ineq + n_eq) && 
!bmap->ineq3.41M
)
1122
0
    goto error;
1123
4.62M
1124
4.62M
  if (extra == 0) {
1125
4.36M
    bmap->block2 = isl_blk_empty();
1126
4.36M
    bmap->div = NULL;
1127
4.36M
  } else {
1128
263k
    bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
1129
263k
    if (isl_blk_is_error(bmap->block2))
1130
0
      goto error;
1131
263k
1132
263k
    bmap->div = isl_alloc_array(ctx, isl_int *, extra);
1133
263k
    if (!bmap->div)
1134
0
      goto error;
1135
4.62M
  }
1136
4.62M
1137
31.8M
  
for (i = 0; 4.62M
i < n_ineq + n_eq;
++i27.1M
)
1138
27.1M
    bmap->ineq[i] = bmap->block.data + i * row_size;
1139
4.62M
1140
5.08M
  for (i = 0; i < extra; 
++i453k
)
1141
453k
    bmap->div[i] = bmap->block2.data + i * (1 + row_size);
1142
4.62M
1143
4.62M
  bmap->ref = 1;
1144
4.62M
  bmap->flags = 0;
1145
4.62M
  bmap->c_size = n_eq + n_ineq;
1146
4.62M
  bmap->eq = bmap->ineq + n_ineq;
1147
4.62M
  bmap->extra = extra;
1148
4.62M
  bmap->n_eq = 0;
1149
4.62M
  bmap->n_ineq = 0;
1150
4.62M
  bmap->n_div = 0;
1151
4.62M
  bmap->sample = NULL;
1152
4.62M
1153
4.62M
  return bmap;
1154
0
error:
1155
0
  isl_basic_map_free(bmap);
1156
0
  return NULL;
1157
4.62M
}
1158
1159
struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
1160
    unsigned nparam, unsigned dim, unsigned extra,
1161
    unsigned n_eq, unsigned n_ineq)
1162
287k
{
1163
287k
  struct isl_basic_map *bmap;
1164
287k
  isl_space *space;
1165
287k
1166
287k
  space = isl_space_set_alloc(ctx, nparam, dim);
1167
287k
  if (!space)
1168
0
    return NULL;
1169
287k
1170
287k
  bmap = isl_basic_map_alloc_space(space, extra, n_eq, n_ineq);
1171
287k
  return bset_from_bmap(bmap);
1172
287k
}
1173
1174
__isl_give isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *dim,
1175
    unsigned extra, unsigned n_eq, unsigned n_ineq)
1176
371k
{
1177
371k
  struct isl_basic_map *bmap;
1178
371k
  if (!dim)
1179
0
    return NULL;
1180
371k
  isl_assert(dim->ctx, dim->n_in == 0, goto error);
1181
371k
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1182
371k
  return bset_from_bmap(bmap);
1183
0
error:
1184
0
  isl_space_free(dim);
1185
0
  return NULL;
1186
371k
}
1187
1188
struct isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *dim,
1189
    unsigned extra, unsigned n_eq, unsigned n_ineq)
1190
4.62M
{
1191
4.62M
  struct isl_basic_map *bmap;
1192
4.62M
1193
4.62M
  if (!dim)
1194
0
    return NULL;
1195
4.62M
  bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
1196
4.62M
  if (!bmap)
1197
0
    goto error;
1198
4.62M
  bmap->dim = dim;
1199
4.62M
1200
4.62M
  return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
1201
0
error:
1202
0
  isl_space_free(dim);
1203
0
  return NULL;
1204
4.62M
}
1205
1206
struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
1207
    unsigned nparam, unsigned in, unsigned out, unsigned extra,
1208
    unsigned n_eq, unsigned n_ineq)
1209
105
{
1210
105
  struct isl_basic_map *bmap;
1211
105
  isl_space *dim;
1212
105
1213
105
  dim = isl_space_alloc(ctx, nparam, in, out);
1214
105
  if (!dim)
1215
0
    return NULL;
1216
105
1217
105
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1218
105
  return bmap;
1219
105
}
1220
1221
static void dup_constraints(
1222
    struct isl_basic_map *dst, struct isl_basic_map *src)
1223
2.46M
{
1224
2.46M
  int i;
1225
2.46M
  unsigned total = isl_basic_map_total_dim(src);
1226
2.46M
1227
3.84M
  for (i = 0; i < src->n_eq; 
++i1.37M
) {
1228
1.37M
    int j = isl_basic_map_alloc_equality(dst);
1229
1.37M
    isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
1230
1.37M
  }
1231
2.46M
1232
17.6M
  for (i = 0; i < src->n_ineq; 
++i15.1M
) {
1233
15.1M
    int j = isl_basic_map_alloc_inequality(dst);
1234
15.1M
    isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
1235
15.1M
  }
1236
2.46M
1237
2.55M
  for (i = 0; i < src->n_div; 
++i92.4k
) {
1238
92.4k
    int j = isl_basic_map_alloc_div(dst);
1239
92.4k
    isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
1240
92.4k
  }
1241
2.46M
  ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
1242
2.46M
}
1243
1244
__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap)
1245
2.46M
{
1246
2.46M
  struct isl_basic_map *dup;
1247
2.46M
1248
2.46M
  if (!bmap)
1249
0
    return NULL;
1250
2.46M
  dup = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
1251
2.46M
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
1252
2.46M
  if (!dup)
1253
0
    return NULL;
1254
2.46M
  dup_constraints(dup, bmap);
1255
2.46M
  dup->flags = bmap->flags;
1256
2.46M
  dup->sample = isl_vec_copy(bmap->sample);
1257
2.46M
  return dup;
1258
2.46M
}
1259
1260
struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
1261
51.0k
{
1262
51.0k
  struct isl_basic_map *dup;
1263
51.0k
1264
51.0k
  dup = isl_basic_map_dup(bset_to_bmap(bset));
1265
51.0k
  return bset_from_bmap(dup);
1266
51.0k
}
1267
1268
__isl_give isl_basic_set *isl_basic_set_copy(__isl_keep isl_basic_set *bset)
1269
1.00M
{
1270
1.00M
  if (!bset)
1271
206
    return NULL;
1272
1.00M
1273
1.00M
  if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
1274
982k
    bset->ref++;
1275
982k
    return bset;
1276
982k
  }
1277
19.4k
  return isl_basic_set_dup(bset);
1278
19.4k
}
1279
1280
__isl_give isl_set *isl_set_copy(__isl_keep isl_set *set)
1281
1.61M
{
1282
1.61M
  if (!set)
1283
16.0k
    return NULL;
1284
1.60M
1285
1.60M
  set->ref++;
1286
1.60M
  return set;
1287
1.60M
}
1288
1289
__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)
1290
3.76M
{
1291
3.76M
  if (!bmap)
1292
0
    return NULL;
1293
3.76M
1294
3.76M
  if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
1295
3.63M
    bmap->ref++;
1296
3.63M
    return bmap;
1297
3.63M
  }
1298
124k
  bmap = isl_basic_map_dup(bmap);
1299
124k
  if (bmap)
1300
124k
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
1301
124k
  return bmap;
1302
124k
}
1303
1304
__isl_give isl_map *isl_map_copy(__isl_keep isl_map *map)
1305
1.20M
{
1306
1.20M
  if (!map)
1307
150
    return NULL;
1308
1.20M
1309
1.20M
  map->ref++;
1310
1.20M
  return map;
1311
1.20M
}
1312
1313
__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap)
1314
13.2M
{
1315
13.2M
  if (!bmap)
1316
6.31M
    return NULL;
1317
6.95M
1318
6.95M
  if (--bmap->ref > 0)
1319
2.33M
    return NULL;
1320
4.62M
1321
4.62M
  isl_ctx_deref(bmap->ctx);
1322
4.62M
  free(bmap->div);
1323
4.62M
  isl_blk_free(bmap->ctx, bmap->block2);
1324
4.62M
  free(bmap->ineq);
1325
4.62M
  isl_blk_free(bmap->ctx, bmap->block);
1326
4.62M
  isl_vec_free(bmap->sample);
1327
4.62M
  isl_space_free(bmap->dim);
1328
4.62M
  free(bmap);
1329
4.62M
1330
4.62M
  return NULL;
1331
4.62M
}
1332
1333
__isl_null isl_basic_set *isl_basic_set_free(__isl_take isl_basic_set *bset)
1334
1.69M
{
1335
1.69M
  return isl_basic_map_free(bset_to_bmap(bset));
1336
1.69M
}
1337
1338
static int room_for_con(struct isl_basic_map *bmap, unsigned n)
1339
5.48M
{
1340
5.48M
  return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
1341
5.48M
}
1342
1343
/* Check that "map" has only named parameters, reporting an error
1344
 * if it does not.
1345
 */
1346
isl_stat isl_map_check_named_params(__isl_keep isl_map *map)
1347
175k
{
1348
175k
  return isl_space_check_named_params(isl_map_peek_space(map));
1349
175k
}
1350
1351
/* Check that "bmap1" and "bmap2" have the same parameters,
1352
 * reporting an error if they do not.
1353
 */
1354
static isl_stat isl_basic_map_check_equal_params(
1355
  __isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2)
1356
543k
{
1357
543k
  isl_bool match;
1358
543k
1359
543k
  match = isl_basic_map_has_equal_params(bmap1, bmap2);
1360
543k
  if (match < 0)
1361
0
    return isl_stat_error;
1362
543k
  if (!match)
1363
543k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
1364
543k
      "parameters don't match", return isl_stat_error);
1365
543k
  return isl_stat_ok;
1366
543k
}
1367
1368
__isl_give isl_map *isl_map_align_params_map_map_and(
1369
  __isl_take isl_map *map1, __isl_take isl_map *map2,
1370
  __isl_give isl_map *(*fn)(__isl_take isl_map *map1,
1371
            __isl_take isl_map *map2))
1372
1.01M
{
1373
1.01M
  if (!map1 || 
!map21.01M
)
1374
10
    goto error;
1375
1.01M
  if (isl_map_has_equal_params(map1, map2))
1376
979k
    return fn(map1, map2);
1377
34.5k
  if (isl_map_check_named_params(map1) < 0)
1378
0
    goto error;
1379
34.5k
  if (isl_map_check_named_params(map2) < 0)
1380
0
    goto error;
1381
34.5k
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
1382
34.5k
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
1383
34.5k
  return fn(map1, map2);
1384
10
error:
1385
10
  isl_map_free(map1);
1386
10
  isl_map_free(map2);
1387
10
  return NULL;
1388
34.5k
}
1389
1390
isl_bool isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1,
1391
  __isl_keep isl_map *map2,
1392
  isl_bool (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2))
1393
63.7k
{
1394
63.7k
  isl_bool r;
1395
63.7k
1396
63.7k
  if (!map1 || !map2)
1397
0
    return isl_bool_error;
1398
63.7k
  if (isl_map_has_equal_params(map1, map2))
1399
61.1k
    return fn(map1, map2);
1400
2.54k
  if (isl_map_check_named_params(map1) < 0)
1401
0
    return isl_bool_error;
1402
2.54k
  if (isl_map_check_named_params(map2) < 0)
1403
0
    return isl_bool_error;
1404
2.54k
  map1 = isl_map_copy(map1);
1405
2.54k
  map2 = isl_map_copy(map2);
1406
2.54k
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
1407
2.54k
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
1408
2.54k
  r = fn(map1, map2);
1409
2.54k
  isl_map_free(map1);
1410
2.54k
  isl_map_free(map2);
1411
2.54k
  return r;
1412
2.54k
}
1413
1414
int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
1415
4.26M
{
1416
4.26M
  struct isl_ctx *ctx;
1417
4.26M
  if (!bmap)
1418
0
    return -1;
1419
4.26M
  ctx = bmap->ctx;
1420
4.26M
  isl_assert(ctx, room_for_con(bmap, 1), return -1);
1421
4.26M
  isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
1422
4.26M
      return -1);
1423
4.26M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1424
4.26M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1425
4.26M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1426
4.26M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1427
4.26M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1428
4.26M
  if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
1429
107k
    isl_int *t;
1430
107k
    int j = isl_basic_map_alloc_inequality(bmap);
1431
107k
    if (j < 0)
1432
0
      return -1;
1433
107k
    t = bmap->ineq[j];
1434
107k
    bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
1435
107k
    bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1436
107k
    bmap->eq[-1] = t;
1437
107k
    bmap->n_eq++;
1438
107k
    bmap->n_ineq--;
1439
107k
    bmap->eq--;
1440
107k
    return 0;
1441
107k
  }
1442
4.15M
  isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
1443
4.15M
          bmap->extra - bmap->n_div);
1444
4.15M
  return bmap->n_eq++;
1445
4.15M
}
1446
1447
int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
1448
1.08M
{
1449
1.08M
  return isl_basic_map_alloc_equality(bset_to_bmap(bset));
1450
1.08M
}
1451
1452
int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
1453
310k
{
1454
310k
  if (!bmap)
1455
0
    return -1;
1456
310k
  isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
1457
310k
  bmap->n_eq -= n;
1458
310k
  return 0;
1459
310k
}
1460
1461
int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
1462
501
{
1463
501
  return isl_basic_map_free_equality(bset_to_bmap(bset), n);
1464
501
}
1465
1466
int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
1467
608k
{
1468
608k
  isl_int *t;
1469
608k
  if (!bmap)
1470
0
    return -1;
1471
608k
  isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
1472
608k
1473
608k
  if (pos != bmap->n_eq - 1) {
1474
217k
    t = bmap->eq[pos];
1475
217k
    bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
1476
217k
    bmap->eq[bmap->n_eq - 1] = t;
1477
217k
  }
1478
608k
  bmap->n_eq--;
1479
608k
  return 0;
1480
608k
}
1481
1482
/* Turn inequality "pos" of "bmap" into an equality.
1483
 *
1484
 * In particular, we move the inequality in front of the equalities
1485
 * and move the last inequality in the position of the moved inequality.
1486
 * Note that isl_tab_make_equalities_explicit depends on this particular
1487
 * change in the ordering of the constraints.
1488
 */
1489
void isl_basic_map_inequality_to_equality(
1490
    struct isl_basic_map *bmap, unsigned pos)
1491
1.06M
{
1492
1.06M
  isl_int *t;
1493
1.06M
1494
1.06M
  t = bmap->ineq[pos];
1495
1.06M
  bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1496
1.06M
  bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1497
1.06M
  bmap->eq[-1] = t;
1498
1.06M
  bmap->n_eq++;
1499
1.06M
  bmap->n_ineq--;
1500
1.06M
  bmap->eq--;
1501
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1502
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1503
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1504
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1505
1.06M
}
1506
1507
static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
1508
23.7M
{
1509
23.7M
  return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
1510
23.7M
}
1511
1512
int isl_basic_map_alloc_inequality(__isl_keep isl_basic_map *bmap)
1513
23.1M
{
1514
23.1M
  struct isl_ctx *ctx;
1515
23.1M
  if (!bmap)
1516
0
    return -1;
1517
23.1M
  ctx = bmap->ctx;
1518
23.1M
  isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
1519
23.1M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1520
23.1M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1521
23.1M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1522
23.1M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1523
23.1M
  isl_seq_clr(bmap->ineq[bmap->n_ineq] +
1524
23.1M
          1 + isl_basic_map_total_dim(bmap),
1525
23.1M
          bmap->extra - bmap->n_div);
1526
23.1M
  return bmap->n_ineq++;
1527
23.1M
}
1528
1529
int isl_basic_set_alloc_inequality(__isl_keep isl_basic_set *bset)
1530
771k
{
1531
771k
  return isl_basic_map_alloc_inequality(bset_to_bmap(bset));
1532
771k
}
1533
1534
int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
1535
926k
{
1536
926k
  if (!bmap)
1537
0
    return -1;
1538
926k
  isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
1539
926k
  bmap->n_ineq -= n;
1540
926k
  return 0;
1541
926k
}
1542
1543
int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
1544
5.38k
{
1545
5.38k
  return isl_basic_map_free_inequality(bset_to_bmap(bset), n);
1546
5.38k
}
1547
1548
int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
1549
7.83M
{
1550
7.83M
  isl_int *t;
1551
7.83M
  if (!bmap)
1552
0
    return -1;
1553
7.83M
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1554
7.83M
1555
7.83M
  if (pos != bmap->n_ineq - 1) {
1556
4.39M
    t = bmap->ineq[pos];
1557
4.39M
    bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1558
4.39M
    bmap->ineq[bmap->n_ineq - 1] = t;
1559
4.39M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1560
4.39M
  }
1561
7.83M
  bmap->n_ineq--;
1562
7.83M
  return 0;
1563
7.83M
}
1564
1565
int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
1566
17.8k
{
1567
17.8k
  return isl_basic_map_drop_inequality(bset_to_bmap(bset), pos);
1568
17.8k
}
1569
1570
__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
1571
  isl_int *eq)
1572
19.7k
{
1573
19.7k
  int k;
1574
19.7k
1575
19.7k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
1576
19.7k
  if (!bmap)
1577
0
    return NULL;
1578
19.7k
  k = isl_basic_map_alloc_equality(bmap);
1579
19.7k
  if (k < 0)
1580
0
    goto error;
1581
19.7k
  isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
1582
19.7k
  return bmap;
1583
0
error:
1584
0
  isl_basic_map_free(bmap);
1585
0
  return NULL;
1586
19.7k
}
1587
1588
__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
1589
  isl_int *eq)
1590
0
{
1591
0
  return bset_from_bmap(isl_basic_map_add_eq(bset_to_bmap(bset), eq));
1592
0
}
1593
1594
__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
1595
  isl_int *ineq)
1596
384k
{
1597
384k
  int k;
1598
384k
1599
384k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
1600
384k
  if (!bmap)
1601
0
    return NULL;
1602
384k
  k = isl_basic_map_alloc_inequality(bmap);
1603
384k
  if (k < 0)
1604
0
    goto error;
1605
384k
  isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
1606
384k
  return bmap;
1607
0
error:
1608
0
  isl_basic_map_free(bmap);
1609
0
  return NULL;
1610
384k
}
1611
1612
__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
1613
  isl_int *ineq)
1614
20.9k
{
1615
20.9k
  return bset_from_bmap(isl_basic_map_add_ineq(bset_to_bmap(bset), ineq));
1616
20.9k
}
1617
1618
int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
1619
426k
{
1620
426k
  if (!bmap)
1621
0
    return -1;
1622
426k
  isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
1623
426k
  isl_seq_clr(bmap->div[bmap->n_div] +
1624
426k
          1 + 1 + isl_basic_map_total_dim(bmap),
1625
426k
          bmap->extra - bmap->n_div);
1626
426k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1627
426k
  return bmap->n_div++;
1628
426k
}
1629
1630
int isl_basic_set_alloc_div(struct isl_basic_set *bset)
1631
1.13k
{
1632
1.13k
  return isl_basic_map_alloc_div(bset_to_bmap(bset));
1633
1.13k
}
1634
1635
/* Check that there are "n" dimensions of type "type" starting at "first"
1636
 * in "bmap".
1637
 */
1638
static isl_stat isl_basic_map_check_range(__isl_keep isl_basic_map *bmap,
1639
  enum isl_dim_type type, unsigned first, unsigned n)
1640
320k
{
1641
320k
  unsigned dim;
1642
320k
1643
320k
  if (!bmap)
1644
0
    return isl_stat_error;
1645
320k
  dim = isl_basic_map_dim(bmap, type);
1646
320k
  if (first + n > dim || first + n < first)
1647
320k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1648
320k
      "position or range out of bounds",
1649
320k
      return isl_stat_error);
1650
320k
  return isl_stat_ok;
1651
320k
}
1652
1653
/* Insert an extra integer division, prescribed by "div", to "bmap"
1654
 * at (integer division) position "pos".
1655
 *
1656
 * The integer division is first added at the end and then moved
1657
 * into the right position.
1658
 */
1659
__isl_give isl_basic_map *isl_basic_map_insert_div(
1660
  __isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div)
1661
2.28k
{
1662
2.28k
  int i, k;
1663
2.28k
1664
2.28k
  bmap = isl_basic_map_cow(bmap);
1665
2.28k
  if (!bmap || !div)
1666
0
    return isl_basic_map_free(bmap);
1667
2.28k
1668
2.28k
  if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all))
1669
2.28k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1670
2.28k
      "unexpected size", return isl_basic_map_free(bmap));
1671
2.28k
  if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0)
1672
0
    return isl_basic_map_free(bmap);
1673
2.28k
1674
2.28k
  bmap = isl_basic_map_extend_space(bmap,
1675
2.28k
          isl_basic_map_get_space(bmap), 1, 0, 2);
1676
2.28k
  k = isl_basic_map_alloc_div(bmap);
1677
2.28k
  if (k < 0)
1678
0
    return isl_basic_map_free(bmap);
1679
2.28k
  isl_seq_cpy(bmap->div[k], div->el, div->size);
1680
2.28k
  isl_int_set_si(bmap->div[k][div->size], 0);
1681
2.28k
1682
2.78k
  for (i = k; i > pos; 
--i494
)
1683
494
    isl_basic_map_swap_div(bmap, i, i - 1);
1684
2.28k
1685
2.28k
  return bmap;
1686
2.28k
}
1687
1688
isl_stat isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
1689
621k
{
1690
621k
  if (!bmap)
1691
0
    return isl_stat_error;
1692
621k
  isl_assert(bmap->ctx, n <= bmap->n_div, return isl_stat_error);
1693
621k
  bmap->n_div -= n;
1694
621k
  return isl_stat_ok;
1695
621k
}
1696
1697
/* Copy constraint from src to dst, putting the vars of src at offset
1698
 * dim_off in dst and the divs of src at offset div_off in dst.
1699
 * If both sets are actually map, then dim_off applies to the input
1700
 * variables.
1701
 */
1702
static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
1703
          struct isl_basic_map *src_map, isl_int *src,
1704
          unsigned in_off, unsigned out_off, unsigned div_off)
1705
6.21M
{
1706
6.21M
  unsigned src_nparam = isl_basic_map_dim(src_map, isl_dim_param);
1707
6.21M
  unsigned dst_nparam = isl_basic_map_dim(dst_map, isl_dim_param);
1708
6.21M
  unsigned src_in = isl_basic_map_dim(src_map, isl_dim_in);
1709
6.21M
  unsigned dst_in = isl_basic_map_dim(dst_map, isl_dim_in);
1710
6.21M
  unsigned src_out = isl_basic_map_dim(src_map, isl_dim_out);
1711
6.21M
  unsigned dst_out = isl_basic_map_dim(dst_map, isl_dim_out);
1712
6.21M
  isl_int_set(dst[0], src[0]);
1713
6.21M
  isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
1714
6.21M
  if (dst_nparam > src_nparam)
1715
0
    isl_seq_clr(dst+1+src_nparam,
1716
0
        dst_nparam - src_nparam);
1717
6.21M
  isl_seq_clr(dst+1+dst_nparam, in_off);
1718
6.21M
  isl_seq_cpy(dst+1+dst_nparam+in_off,
1719
6.21M
        src+1+src_nparam,
1720
6.21M
        isl_min(dst_in-in_off, src_in));
1721
6.21M
  if (dst_in-in_off > src_in)
1722
48.5k
    isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
1723
48.5k
        dst_in - in_off - src_in);
1724
6.21M
  isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
1725
6.21M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
1726
6.21M
        src+1+src_nparam+src_in,
1727
6.21M
        isl_min(dst_out-out_off, src_out));
1728
6.21M
  if (dst_out-out_off > src_out)
1729
505k
    isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
1730
505k
        dst_out - out_off - src_out);
1731
6.21M
  isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
1732
6.21M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
1733
6.21M
        src+1+src_nparam+src_in+src_out,
1734
6.21M
        isl_min(dst_map->extra-div_off, src_map->n_div));
1735
6.21M
  if (dst_map->n_div-div_off > src_map->n_div)
1736
0
    isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
1737
0
        div_off+src_map->n_div,
1738
0
        dst_map->n_div - div_off - src_map->n_div);
1739
6.21M
}
1740
1741
static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
1742
         struct isl_basic_map *src_map, isl_int *src,
1743
         unsigned in_off, unsigned out_off, unsigned div_off)
1744
108k
{
1745
108k
  isl_int_set(dst[0], src[0]);
1746
108k
  copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
1747
108k
}
1748
1749
static __isl_give isl_basic_map *add_constraints(
1750
  __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2,
1751
  unsigned i_pos, unsigned o_pos)
1752
1.18M
{
1753
1.18M
  int i;
1754
1.18M
  unsigned div_off;
1755
1.18M
1756
1.18M
  if (!bmap1 || !bmap2)
1757
0
    goto error;
1758
1.18M
1759
1.18M
  div_off = bmap1->n_div;
1760
1.18M
1761
1.90M
  for (i = 0; i < bmap2->n_eq; 
++i715k
) {
1762
715k
    int i1 = isl_basic_map_alloc_equality(bmap1);
1763
715k
    if (i1 < 0)
1764
0
      goto error;
1765
715k
    copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
1766
715k
        i_pos, o_pos, div_off);
1767
715k
  }
1768
1.18M
1769
6.57M
  
for (i = 0; 1.18M
i < bmap2->n_ineq;
++i5.38M
) {
1770
5.38M
    int i1 = isl_basic_map_alloc_inequality(bmap1);
1771
5.38M
    if (i1 < 0)
1772
0
      goto error;
1773
5.38M
    copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
1774
5.38M
        i_pos, o_pos, div_off);
1775
5.38M
  }
1776
1.18M
1777
1.29M
  
for (i = 0; 1.18M
i < bmap2->n_div;
++i108k
) {
1778
108k
    int i1 = isl_basic_map_alloc_div(bmap1);
1779
108k
    if (i1 < 0)
1780
0
      goto error;
1781
108k
    copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
1782
108k
       i_pos, o_pos, div_off);
1783
108k
  }
1784
1.18M
1785
1.18M
  isl_basic_map_free(bmap2);
1786
1.18M
1787
1.18M
  return bmap1;
1788
0
1789
0
error:
1790
0
  isl_basic_map_free(bmap1);
1791
0
  isl_basic_map_free(bmap2);
1792
0
  return NULL;
1793
1.18M
}
1794
1795
struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
1796
    struct isl_basic_set *bset2, unsigned pos)
1797
0
{
1798
0
  return bset_from_bmap(add_constraints(bset_to_bmap(bset1),
1799
0
            bset_to_bmap(bset2), 0, pos));
1800
0
}
1801
1802
__isl_give isl_basic_map *isl_basic_map_extend_space(
1803
  __isl_take isl_basic_map *base, __isl_take isl_space *dim,
1804
  unsigned extra, unsigned n_eq, unsigned n_ineq)
1805
1.34M
{
1806
1.34M
  struct isl_basic_map *ext;
1807
1.34M
  unsigned flags;
1808
1.34M
  int dims_ok;
1809
1.34M
1810
1.34M
  if (!dim)
1811
0
    goto error;
1812
1.34M
1813
1.34M
  if (!base)
1814
0
    goto error;
1815
1.34M
1816
1.34M
  dims_ok = isl_space_is_equal(base->dim, dim) &&
1817
1.34M
      
base->extra >= base->n_div + extra1.24M
;
1818
1.34M
1819
1.34M
  if (dims_ok && 
room_for_con(base, n_eq + n_ineq)1.22M
&&
1820
1.34M
           
room_for_ineq(base, n_ineq)554k
) {
1821
540k
    isl_space_free(dim);
1822
540k
    return base;
1823
540k
  }
1824
809k
1825
809k
  isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
1826
809k
  isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
1827
809k
  isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
1828
809k
  extra += base->extra;
1829
809k
  n_eq += base->n_eq;
1830
809k
  n_ineq += base->n_ineq;
1831
809k
1832
809k
  ext = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1833
809k
  dim = NULL;
1834
809k
  if (!ext)
1835
0
    goto error;
1836
809k
1837
809k
  if (dims_ok)
1838
683k
    ext->sample = isl_vec_copy(base->sample);
1839
809k
  flags = base->flags;
1840
809k
  ext = add_constraints(ext, base, 0, 0);
1841
809k
  if (ext) {
1842
809k
    ext->flags = flags;
1843
809k
    ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
1844
809k
  }
1845
809k
1846
809k
  return ext;
1847
0
1848
0
error:
1849
0
  isl_space_free(dim);
1850
0
  isl_basic_map_free(base);
1851
0
  return NULL;
1852
809k
}
1853
1854
__isl_give isl_basic_set *isl_basic_set_extend_space(
1855
  __isl_take isl_basic_set *base,
1856
    __isl_take isl_space *dim, unsigned extra,
1857
    unsigned n_eq, unsigned n_ineq)
1858
13.6k
{
1859
13.6k
  return bset_from_bmap(isl_basic_map_extend_space(bset_to_bmap(base),
1860
13.6k
                dim, extra, n_eq, n_ineq));
1861
13.6k
}
1862
1863
struct isl_basic_map *isl_basic_map_extend_constraints(
1864
    struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
1865
708k
{
1866
708k
  if (!base)
1867
0
    return NULL;
1868
708k
  return isl_basic_map_extend_space(base, isl_space_copy(base->dim),
1869
708k
          0, n_eq, n_ineq);
1870
708k
}
1871
1872
struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
1873
    unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
1874
    unsigned n_eq, unsigned n_ineq)
1875
146k
{
1876
146k
  struct isl_basic_map *bmap;
1877
146k
  isl_space *dim;
1878
146k
1879
146k
  if (!base)
1880
0
    return NULL;
1881
146k
  dim = isl_space_alloc(base->ctx, nparam, n_in, n_out);
1882
146k
  if (!dim)
1883
0
    goto error;
1884
146k
1885
146k
  bmap = isl_basic_map_extend_space(base, dim, extra, n_eq, n_ineq);
1886
146k
  return bmap;
1887
0
error:
1888
0
  isl_basic_map_free(base);
1889
0
  return NULL;
1890
146k
}
1891
1892
struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
1893
    unsigned nparam, unsigned dim, unsigned extra,
1894
    unsigned n_eq, unsigned n_ineq)
1895
146k
{
1896
146k
  return bset_from_bmap(isl_basic_map_extend(bset_to_bmap(base),
1897
146k
          nparam, 0, dim, extra, n_eq, n_ineq));
1898
146k
}
1899
1900
struct isl_basic_set *isl_basic_set_extend_constraints(
1901
    struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
1902
11.9k
{
1903
11.9k
  isl_basic_map *bmap = bset_to_bmap(base);
1904
11.9k
  bmap = isl_basic_map_extend_constraints(bmap, n_eq, n_ineq);
1905
11.9k
  return bset_from_bmap(bmap);
1906
11.9k
}
1907
1908
__isl_give isl_basic_set *isl_basic_set_cow(__isl_take isl_basic_set *bset)
1909
894k
{
1910
894k
  return bset_from_bmap(isl_basic_map_cow(bset_to_bmap(bset)));
1911
894k
}
1912
1913
__isl_give isl_basic_map *isl_basic_map_cow(__isl_take isl_basic_map *bmap)
1914
5.10M
{
1915
5.10M
  if (!bmap)
1916
0
    return NULL;
1917
5.10M
1918
5.10M
  if (bmap->ref > 1) {
1919
2.28M
    bmap->ref--;
1920
2.28M
    bmap = isl_basic_map_dup(bmap);
1921
2.28M
  }
1922
5.10M
  if (bmap) {
1923
5.10M
    ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
1924
5.10M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
1925
5.10M
  }
1926
5.10M
  return bmap;
1927
5.10M
}
1928
1929
/* Clear all cached information in "map", either because it is about
1930
 * to be modified or because it is being freed.
1931
 * Always return the same pointer that is passed in.
1932
 * This is needed for the use in isl_map_free.
1933
 */
1934
static __isl_give isl_map *clear_caches(__isl_take isl_map *map)
1935
2.85M
{
1936
2.85M
  isl_basic_map_free(map->cached_simple_hull[0]);
1937
2.85M
  isl_basic_map_free(map->cached_simple_hull[1]);
1938
2.85M
  map->cached_simple_hull[0] = NULL;
1939
2.85M
  map->cached_simple_hull[1] = NULL;
1940
2.85M
  return map;
1941
2.85M
}
1942
1943
__isl_give isl_set *isl_set_cow(__isl_take isl_set *set)
1944
192k
{
1945
192k
  return isl_map_cow(set);
1946
192k
}
1947
1948
/* Return an isl_map that is equal to "map" and that has only
1949
 * a single reference.
1950
 *
1951
 * If the original input already has only one reference, then
1952
 * simply return it, but clear all cached information, since
1953
 * it may be rendered invalid by the operations that will be
1954
 * performed on the result.
1955
 *
1956
 * Otherwise, create a duplicate (without any cached information).
1957
 */
1958
__isl_give isl_map *isl_map_cow(__isl_take isl_map *map)
1959
1.93M
{
1960
1.93M
  if (!map)
1961
18
    return NULL;
1962
1.93M
1963
1.93M
  if (map->ref == 1)
1964
1.35M
    return clear_caches(map);
1965
581k
  map->ref--;
1966
581k
  return isl_map_dup(map);
1967
581k
}
1968
1969
static void swap_vars(struct isl_blk blk, isl_int *a,
1970
      unsigned a_len, unsigned b_len)
1971
401k
{
1972
401k
  isl_seq_cpy(blk.data, a+a_len, b_len);
1973
401k
  isl_seq_cpy(blk.data+b_len, a, a_len);
1974
401k
  isl_seq_cpy(a, blk.data, b_len+a_len);
1975
401k
}
1976
1977
static __isl_give isl_basic_map *isl_basic_map_swap_vars(
1978
  __isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2)
1979
182k
{
1980
182k
  int i;
1981
182k
  struct isl_blk blk;
1982
182k
1983
182k
  if (!bmap)
1984
0
    goto error;
1985
182k
1986
182k
  isl_assert(bmap->ctx,
1987
182k
    pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);
1988
182k
1989
182k
  if (n1 == 0 || 
n2 == 071.9k
)
1990
117k
    return bmap;
1991
64.7k
1992
64.7k
  bmap = isl_basic_map_cow(bmap);
1993
64.7k
  if (!bmap)
1994
0
    return NULL;
1995
64.7k
1996
64.7k
  blk = isl_blk_alloc(bmap->ctx, n1 + n2);
1997
64.7k
  if (isl_blk_is_error(blk))
1998
0
    goto error;
1999
64.7k
2000
258k
  
for (i = 0; 64.7k
i < bmap->n_eq;
++i193k
)
2001
193k
    swap_vars(blk,
2002
193k
        bmap->eq[i] + pos, n1, n2);
2003
64.7k
2004
268k
  for (i = 0; i < bmap->n_ineq; 
++i204k
)
2005
204k
    swap_vars(blk,
2006
204k
        bmap->ineq[i] + pos, n1, n2);
2007
64.7k
2008
68.3k
  for (i = 0; i < bmap->n_div; 
++i3.55k
)
2009
3.55k
    swap_vars(blk,
2010
3.55k
        bmap->div[i]+1 + pos, n1, n2);
2011
64.7k
2012
64.7k
  isl_blk_free(bmap->ctx, blk);
2013
64.7k
2014
64.7k
  ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
2015
64.7k
  bmap = isl_basic_map_gauss(bmap, NULL);
2016
64.7k
  return isl_basic_map_finalize(bmap);
2017
0
error:
2018
0
  isl_basic_map_free(bmap);
2019
0
  return NULL;
2020
64.7k
}
2021
2022
__isl_give isl_basic_map *isl_basic_map_set_to_empty(
2023
  __isl_take isl_basic_map *bmap)
2024
201k
{
2025
201k
  int i = 0;
2026
201k
  unsigned total;
2027
201k
  if (!bmap)
2028
0
    goto error;
2029
201k
  total = isl_basic_map_total_dim(bmap);
2030
201k
  if (isl_basic_map_free_div(bmap, bmap->n_div) < 0)
2031
0
    return isl_basic_map_free(bmap);
2032
201k
  isl_basic_map_free_inequality(bmap, bmap->n_ineq);
2033
201k
  if (bmap->n_eq > 0)
2034
94.7k
    isl_basic_map_free_equality(bmap, bmap->n_eq-1);
2035
107k
  else {
2036
107k
    i = isl_basic_map_alloc_equality(bmap);
2037
107k
    if (i < 0)
2038
0
      goto error;
2039
201k
  }
2040
201k
  isl_int_set_si(bmap->eq[i][0], 1);
2041
201k
  isl_seq_clr(bmap->eq[i]+1, total);
2042
201k
  ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
2043
201k
  isl_vec_free(bmap->sample);
2044
201k
  bmap->sample = NULL;
2045
201k
  return isl_basic_map_finalize(bmap);
2046
0
error:
2047
0
  isl_basic_map_free(bmap);
2048
0
  return NULL;
2049
201k
}
2050
2051
__isl_give isl_basic_set *isl_basic_set_set_to_empty(
2052
  __isl_take isl_basic_set *bset)
2053
6.69k
{
2054
6.69k
  return bset_from_bmap(isl_basic_map_set_to_empty(bset_to_bmap(bset)));
2055
6.69k
}
2056
2057
__isl_give isl_basic_map *isl_basic_map_set_rational(
2058
  __isl_take isl_basic_map *bmap)
2059
86.3k
{
2060
86.3k
  if (!bmap)
2061
0
    return NULL;
2062
86.3k
2063
86.3k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2064
86.3k
    
return bmap53.9k
;
2065
32.3k
2066
32.3k
  bmap = isl_basic_map_cow(bmap);
2067
32.3k
  if (!bmap)
2068
0
    return NULL;
2069
32.3k
2070
32.3k
  ISL_F_SET(bmap, ISL_BASIC_MAP_RATIONAL);
2071
32.3k
2072
32.3k
  return isl_basic_map_finalize(bmap);
2073
32.3k
}
2074
2075
__isl_give isl_basic_set *isl_basic_set_set_rational(
2076
  __isl_take isl_basic_set *bset)
2077
27.0k
{
2078
27.0k
  return isl_basic_map_set_rational(bset);
2079
27.0k
}
2080
2081
__isl_give isl_basic_set *isl_basic_set_set_integral(
2082
  __isl_take isl_basic_set *bset)
2083
15
{
2084
15
  if (!bset)
2085
0
    return NULL;
2086
15
2087
15
  if (!ISL_F_ISSET(bset, ISL_BASIC_MAP_RATIONAL))
2088
15
    
return bset0
;
2089
15
2090
15
  bset = isl_basic_set_cow(bset);
2091
15
  if (!bset)
2092
0
    return NULL;
2093
15
2094
15
  ISL_F_CLR(bset, ISL_BASIC_MAP_RATIONAL);
2095
15
2096
15
  return isl_basic_set_finalize(bset);
2097
15
}
2098
2099
__isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map)
2100
32.2k
{
2101
32.2k
  int i;
2102
32.2k
2103
32.2k
  map = isl_map_cow(map);
2104
32.2k
  if (!map)
2105
0
    return NULL;
2106
91.5k
  
for (i = 0; 32.2k
i < map->n;
++i59.2k
) {
2107
59.2k
    map->p[i] = isl_basic_map_set_rational(map->p[i]);
2108
59.2k
    if (!map->p[i])
2109
0
      goto error;
2110
59.2k
  }
2111
32.2k
  return map;
2112
0
error:
2113
0
  isl_map_free(map);
2114
0
  return NULL;
2115
32.2k
}
2116
2117
__isl_give isl_set *isl_set_set_rational(__isl_take isl_set *set)
2118
32.2k
{
2119
32.2k
  return isl_map_set_rational(set);
2120
32.2k
}
2121
2122
/* Swap divs "a" and "b" in "bmap" (without modifying any of the constraints
2123
 * of "bmap").
2124
 */
2125
static void swap_div(__isl_keep isl_basic_map *bmap, int a, int b)
2126
6.22k
{
2127
6.22k
  isl_int *t = bmap->div[a];
2128
6.22k
  bmap->div[a] = bmap->div[b];
2129
6.22k
  bmap->div[b] = t;
2130
6.22k
}
2131
2132
/* Swap divs "a" and "b" in "bmap" and adjust the constraints and
2133
 * div definitions accordingly.
2134
 */
2135
void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
2136
6.00k
{
2137
6.00k
  int i;
2138
6.00k
  unsigned off = isl_space_dim(bmap->dim, isl_dim_all);
2139
6.00k
2140
6.00k
  swap_div(bmap, a, b);
2141
6.00k
2142
24.9k
  for (i = 0; i < bmap->n_eq; 
++i18.9k
)
2143
18.9k
    isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
2144
6.00k
2145
78.5k
  for (i = 0; i < bmap->n_ineq; 
++i72.5k
)
2146
72.5k
    isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
2147
6.00k
2148
31.7k
  for (i = 0; i < bmap->n_div; 
++i25.7k
)
2149
25.7k
    isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
2150
6.00k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2151
6.00k
}
2152
2153
/* Swap divs "a" and "b" in "bset" and adjust the constraints and
2154
 * div definitions accordingly.
2155
 */
2156
void isl_basic_set_swap_div(__isl_keep isl_basic_set *bset, int a, int b)
2157
0
{
2158
0
  isl_basic_map_swap_div(bset, a, b);
2159
0
}
2160
2161
static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
2162
6.66M
{
2163
6.66M
  isl_seq_cpy(c, c + n, rem);
2164
6.66M
  isl_seq_clr(c + rem, n);
2165
6.66M
}
2166
2167
/* Drop n dimensions starting at first.
2168
 *
2169
 * In principle, this frees up some extra variables as the number
2170
 * of columns remains constant, but we would have to extend
2171
 * the div array too as the number of rows in this array is assumed
2172
 * to be equal to extra.
2173
 */
2174
__isl_give isl_basic_set *isl_basic_set_drop_dims(
2175
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
2176
169k
{
2177
169k
  return isl_basic_map_drop(bset_to_bmap(bset), isl_dim_set, first, n);
2178
169k
}
2179
2180
/* Move "n" divs starting at "first" to the end of the list of divs.
2181
 */
2182
static struct isl_basic_map *move_divs_last(struct isl_basic_map *bmap,
2183
  unsigned first, unsigned n)
2184
769
{
2185
769
  isl_int **div;
2186
769
  int i;
2187
769
2188
769
  if (first + n == bmap->n_div)
2189
684
    return bmap;
2190
85
2191
85
  div = isl_alloc_array(bmap->ctx, isl_int *, n);
2192
85
  if (!div)
2193
0
    goto error;
2194
170
  
for (i = 0; 85
i < n;
++i85
)
2195
85
    div[i] = bmap->div[first + i];
2196
222
  for (i = 0; i < bmap->n_div - first - n; 
++i137
)
2197
137
    bmap->div[first + i] = bmap->div[first + n + i];
2198
170
  for (i = 0; i < n; 
++i85
)
2199
85
    bmap->div[bmap->n_div - n + i] = div[i];
2200
85
  free(div);
2201
85
  return bmap;
2202
0
error:
2203
0
  isl_basic_map_free(bmap);
2204
0
  return NULL;
2205
85
}
2206
2207
/* Drop "n" dimensions of type "type" starting at "first".
2208
 *
2209
 * In principle, this frees up some extra variables as the number
2210
 * of columns remains constant, but we would have to extend
2211
 * the div array too as the number of rows in this array is assumed
2212
 * to be equal to extra.
2213
 */
2214
__isl_give isl_basic_map *isl_basic_map_drop(__isl_take isl_basic_map *bmap,
2215
  enum isl_dim_type type, unsigned first, unsigned n)
2216
531k
{
2217
531k
  int i;
2218
531k
  unsigned dim;
2219
531k
  unsigned offset;
2220
531k
  unsigned left;
2221
531k
2222
531k
  if (!bmap)
2223
0
    goto error;
2224
531k
2225
531k
  dim = isl_basic_map_dim(bmap, type);
2226
531k
  isl_assert(bmap->ctx, first + n <= dim, goto error);
2227
531k
2228
531k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)90.4k
)
2229
90.4k
    return bmap;
2230
441k
2231
441k
  bmap = isl_basic_map_cow(bmap);
2232
441k
  if (!bmap)
2233
0
    return NULL;
2234
441k
2235
441k
  offset = isl_basic_map_offset(bmap, type) + first;
2236
441k
  left = isl_basic_map_total_dim(bmap) - (offset - 1) - n;
2237
445k
  for (i = 0; i < bmap->n_eq; 
++i3.87k
)
2238
3.87k
    constraint_drop_vars(bmap->eq[i]+offset, n, left);
2239
441k
2240
2.17M
  for (i = 0; i < bmap->n_ineq; 
++i1.73M
)
2241
1.73M
    constraint_drop_vars(bmap->ineq[i]+offset, n, left);
2242
441k
2243
443k
  for (i = 0; i < bmap->n_div; 
++i2.15k
)
2244
2.15k
    constraint_drop_vars(bmap->div[i]+1+offset, n, left);
2245
441k
2246
441k
  if (type == isl_dim_div) {
2247
769
    bmap = move_divs_last(bmap, first, n);
2248
769
    if (!bmap)
2249
0
      goto error;
2250
769
    if (isl_basic_map_free_div(bmap, n) < 0)
2251
0
      return isl_basic_map_free(bmap);
2252
440k
  } else
2253
440k
    bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
2254
441k
  if (!bmap->dim)
2255
0
    goto error;
2256
441k
2257
441k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2258
441k
  bmap = isl_basic_map_simplify(bmap);
2259
441k
  return isl_basic_map_finalize(bmap);
2260
0
error:
2261
0
  isl_basic_map_free(bmap);
2262
0
  return NULL;
2263
441k
}
2264
2265
__isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset,
2266
  enum isl_dim_type type, unsigned first, unsigned n)
2267
359k
{
2268
359k
  return bset_from_bmap(isl_basic_map_drop(bset_to_bmap(bset),
2269
359k
              type, first, n));
2270
359k
}
2271
2272
__isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
2273
  enum isl_dim_type type, unsigned first, unsigned n)
2274
663
{
2275
663
  int i;
2276
663
2277
663
  if (!map)
2278
0
    goto error;
2279
663
2280
663
  isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
2281
663
2282
663
  if (n == 0 && 
!isl_space_is_named_or_nested(map->dim, type)0
)
2283
0
    return map;
2284
663
  map = isl_map_cow(map);
2285
663
  if (!map)
2286
0
    goto error;
2287
663
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
2288
663
  if (!map->dim)
2289
0
    goto error;
2290
663
2291
1.47k
  
for (i = 0; 663
i < map->n;
++i811
) {
2292
811
    map->p[i] = isl_basic_map_drop(map->p[i], type, first, n);
2293
811
    if (!map->p[i])
2294
0
      goto error;
2295
811
  }
2296
663
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2297
663
2298
663
  return map;
2299
0
error:
2300
0
  isl_map_free(map);
2301
0
  return NULL;
2302
663
}
2303
2304
__isl_give isl_set *isl_set_drop(__isl_take isl_set *set,
2305
  enum isl_dim_type type, unsigned first, unsigned n)
2306
91
{
2307
91
  return set_from_map(isl_map_drop(set_to_map(set), type, first, n));
2308
91
}
2309
2310
/*
2311
 * We don't cow, as the div is assumed to be redundant.
2312
 */
2313
__isl_give isl_basic_map *isl_basic_map_drop_div(
2314
  __isl_take isl_basic_map *bmap, unsigned div)
2315
418k
{
2316
418k
  int i;
2317
418k
  unsigned pos;
2318
418k
2319
418k
  if (!bmap)
2320
0
    goto error;
2321
418k
2322
418k
  pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;
2323
418k
2324
418k
  isl_assert(bmap->ctx, div < bmap->n_div, goto error);
2325
418k
2326
1.86M
  
for (i = 0; 418k
i < bmap->n_eq;
++i1.44M
)
2327
1.44M
    constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);
2328
418k
2329
3.01M
  for (i = 0; i < bmap->n_ineq; 
++i2.59M
) {
2330
2.59M
    if (!isl_int_is_zero(bmap->ineq[i][pos])) {
2331
20.2k
      isl_basic_map_drop_inequality(bmap, i);
2332
20.2k
      --i;
2333
20.2k
      continue;
2334
20.2k
    }
2335
2.57M
    constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
2336
2.57M
  }
2337
418k
2338
1.32M
  for (i = 0; i < bmap->n_div; 
++i906k
)
2339
906k
    constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);
2340
418k
2341
418k
  if (div != bmap->n_div - 1) {
2342
24.5k
    int j;
2343
24.5k
    isl_int *t = bmap->div[div];
2344
24.5k
2345
60.6k
    for (j = div; j < bmap->n_div - 1; 
++j36.1k
)
2346
36.1k
      bmap->div[j] = bmap->div[j+1];
2347
24.5k
2348
24.5k
    bmap->div[bmap->n_div - 1] = t;
2349
24.5k
  }
2350
418k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2351
418k
  if (isl_basic_map_free_div(bmap, 1) < 0)
2352
0
    return isl_basic_map_free(bmap);
2353
418k
2354
418k
  return bmap;
2355
0
error:
2356
0
  isl_basic_map_free(bmap);
2357
0
  return NULL;
2358
418k
}
2359
2360
/* Eliminate the specified n dimensions starting at first from the
2361
 * constraints, without removing the dimensions from the space.
2362
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2363
 */
2364
__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
2365
  enum isl_dim_type type, unsigned first, unsigned n)
2366
17.9k
{
2367
17.9k
  int i;
2368
17.9k
2369
17.9k
  if (!map)
2370
0
    return NULL;
2371
17.9k
  if (n == 0)
2372
6.76k
    return map;
2373
11.1k
2374
11.1k
  if (first + n > isl_map_dim(map, type) || first + n < first)
2375
11.1k
    
isl_die0
(map->ctx, isl_error_invalid,
2376
11.1k
      "index out of bounds", goto error);
2377
11.1k
2378
11.1k
  map = isl_map_cow(map);
2379
11.1k
  if (!map)
2380
0
    return NULL;
2381
11.1k
2382
22.4k
  
for (i = 0; 11.1k
i < map->n;
++i11.2k
) {
2383
11.2k
    map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n);
2384
11.2k
    if (!map->p[i])
2385
0
      goto error;
2386
11.2k
  }
2387
11.1k
  return map;
2388
0
error:
2389
0
  isl_map_free(map);
2390
0
  return NULL;
2391
11.1k
}
2392
2393
/* Eliminate the specified n dimensions starting at first from the
2394
 * constraints, without removing the dimensions from the space.
2395
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2396
 */
2397
__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
2398
  enum isl_dim_type type, unsigned first, unsigned n)
2399
14.0k
{
2400
14.0k
  return set_from_map(isl_map_eliminate(set_to_map(set), type, first, n));
2401
14.0k
}
2402
2403
/* Eliminate the specified n dimensions starting at first from the
2404
 * constraints, without removing the dimensions from the space.
2405
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2406
 */
2407
__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
2408
  unsigned first, unsigned n)
2409
0
{
2410
0
  return isl_set_eliminate(set, isl_dim_set, first, n);
2411
0
}
2412
2413
__isl_give isl_basic_map *isl_basic_map_remove_divs(
2414
  __isl_take isl_basic_map *bmap)
2415
2.67k
{
2416
2.67k
  if (!bmap)
2417
0
    return NULL;
2418
2.67k
  bmap = isl_basic_map_eliminate_vars(bmap,
2419
2.67k
          isl_space_dim(bmap->dim, isl_dim_all), bmap->n_div);
2420
2.67k
  if (!bmap)
2421
0
    return NULL;
2422
2.67k
  bmap->n_div = 0;
2423
2.67k
  return isl_basic_map_finalize(bmap);
2424
2.67k
}
2425
2426
__isl_give isl_basic_set *isl_basic_set_remove_divs(
2427
  __isl_take isl_basic_set *bset)
2428
801
{
2429
801
  return bset_from_bmap(isl_basic_map_remove_divs(bset_to_bmap(bset)));
2430
801
}
2431
2432
__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
2433
5.60k
{
2434
5.60k
  int i;
2435
5.60k
2436
5.60k
  if (!map)
2437
0
    return NULL;
2438
5.60k
  if (map->n == 0)
2439
4.39k
    return map;
2440
1.21k
2441
1.21k
  map = isl_map_cow(map);
2442
1.21k
  if (!map)
2443
0
    return NULL;
2444
1.21k
  
2445
3.04k
  
for (i = 0; 1.21k
i < map->n;
++i1.83k
) {
2446
1.83k
    map->p[i] = isl_basic_map_remove_divs(map->p[i]);
2447
1.83k
    if (!map->p[i])
2448
0
      goto error;
2449
1.83k
  }
2450
1.21k
  return map;
2451
0
error:
2452
0
  isl_map_free(map);
2453
0
  return NULL;
2454
1.21k
}
2455
2456
__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
2457
5.47k
{
2458
5.47k
  return isl_map_remove_divs(set);
2459
5.47k
}
2460
2461
__isl_give isl_basic_map *isl_basic_map_remove_dims(
2462
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
2463
  unsigned first, unsigned n)
2464
3.82k
{
2465
3.82k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2466
0
    return isl_basic_map_free(bmap);
2467
3.82k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)2.38k
)
2468
2.38k
    return bmap;
2469
1.44k
  bmap = isl_basic_map_eliminate_vars(bmap,
2470
1.44k
      isl_basic_map_offset(bmap, type) - 1 + first, n);
2471
1.44k
  if (!bmap)
2472
0
    return bmap;
2473
1.44k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && 
type == isl_dim_div25
)
2474
25
    return bmap;
2475
1.41k
  bmap = isl_basic_map_drop(bmap, type, first, n);
2476
1.41k
  return bmap;
2477
1.41k
}
2478
2479
/* Return true if the definition of the given div (recursively) involves
2480
 * any of the given variables.
2481
 */
2482
static isl_bool div_involves_vars(__isl_keep isl_basic_map *bmap, int div,
2483
  unsigned first, unsigned n)
2484
1.12k
{
2485
1.12k
  int i;
2486
1.12k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
2487
1.12k
2488
1.12k
  if (isl_int_is_zero(bmap->div[div][0]))
2489
1.12k
    
return isl_bool_false348
;
2490
781
  if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0)
2491
88
    return isl_bool_true;
2492
693
2493
1.49k
  
for (i = bmap->n_div - 1; 693
i >= 0;
--i802
) {
2494
802
    isl_bool involves;
2495
802
2496
802
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
2497
802
      continue;
2498
0
    involves = div_involves_vars(bmap, i, first, n);
2499
0
    if (involves < 0 || involves)
2500
0
      return involves;
2501
0
  }
2502
693
2503
693
  return isl_bool_false;
2504
693
}
2505
2506
/* Try and add a lower and/or upper bound on "div" to "bmap"
2507
 * based on inequality "i".
2508
 * "total" is the total number of variables (excluding the divs).
2509
 * "v" is a temporary object that can be used during the calculations.
2510
 * If "lb" is set, then a lower bound should be constructed.
2511
 * If "ub" is set, then an upper bound should be constructed.
2512
 *
2513
 * The calling function has already checked that the inequality does not
2514
 * reference "div", but we still need to check that the inequality is
2515
 * of the right form.  We'll consider the case where we want to construct
2516
 * a lower bound.  The construction of upper bounds is similar.
2517
 *
2518
 * Let "div" be of the form
2519
 *
2520
 *  q = floor((a + f(x))/d)
2521
 *
2522
 * We essentially check if constraint "i" is of the form
2523
 *
2524
 *  b + f(x) >= 0
2525
 *
2526
 * so that we can use it to derive a lower bound on "div".
2527
 * However, we allow a slightly more general form
2528
 *
2529
 *  b + g(x) >= 0
2530
 *
2531
 * with the condition that the coefficients of g(x) - f(x) are all
2532
 * divisible by d.
2533
 * Rewriting this constraint as
2534
 *
2535
 *  0 >= -b - g(x)
2536
 *
2537
 * adding a + f(x) to both sides and dividing by d, we obtain
2538
 *
2539
 *  (a + f(x))/d >= (a-b)/d + (f(x)-g(x))/d
2540
 *
2541
 * Taking the floor on both sides, we obtain
2542
 *
2543
 *  q >= floor((a-b)/d) + (f(x)-g(x))/d
2544
 *
2545
 * or
2546
 *
2547
 *  (g(x)-f(x))/d + ceil((b-a)/d) + q >= 0
2548
 *
2549
 * In the case of an upper bound, we construct the constraint
2550
 *
2551
 *  (g(x)+f(x))/d + floor((b+a)/d) - q >= 0
2552
 *
2553
 */
2554
static __isl_give isl_basic_map *insert_bounds_on_div_from_ineq(
2555
  __isl_take isl_basic_map *bmap, int div, int i,
2556
  unsigned total, isl_int v, int lb, int ub)
2557
68
{
2558
68
  int j;
2559
68
2560
257
  for (j = 0; (lb || 
ub68
) &&
j < total + bmap->n_div222
;
++j189
) {
2561
189
    if (lb) {
2562
168
      isl_int_sub(v, bmap->ineq[i][1 + j],
2563
168
          bmap->div[div][1 + 1 + j]);
2564
168
      lb = isl_int_is_divisible_by(v, bmap->div[div][0]);
2565
168
    }
2566
189
    if (ub) {
2567
163
      isl_int_add(v, bmap->ineq[i][1 + j],
2568
163
          bmap->div[div][1 + 1 + j]);
2569
163
      ub = isl_int_is_divisible_by(v, bmap->div[div][0]);
2570
163
    }
2571
189
  }
2572
68
  if (!lb && 
!ub47
)
2573
35
    return bmap;
2574
33
2575
33
  bmap = isl_basic_map_cow(bmap);
2576
33
  bmap = isl_basic_map_extend_constraints(bmap, 0, lb + ub);
2577
33
  if (lb) {
2578
21
    int k = isl_basic_map_alloc_inequality(bmap);
2579
21
    if (k < 0)
2580
0
      goto error;
2581
115
    
for (j = 0; 21
j < 1 + total + bmap->n_div;
++j94
) {
2582
94
      isl_int_sub(bmap->ineq[k][j], bmap->ineq[i][j],
2583
94
          bmap->div[div][1 + j]);
2584
94
      isl_int_cdiv_q(bmap->ineq[k][j],
2585
94
          bmap->ineq[k][j], bmap->div[div][0]);
2586
94
    }
2587
21
    isl_int_set_si(bmap->ineq[k][1 + total + div], 1);
2588
21
  }
2589
33
  if (ub) {
2590
18
    int k = isl_basic_map_alloc_inequality(bmap);
2591
18
    if (k < 0)
2592
0
      goto error;
2593
99
    
for (j = 0; 18
j < 1 + total + bmap->n_div;
++j81
) {
2594
81
      isl_int_add(bmap->ineq[k][j], bmap->ineq[i][j],
2595
81
          bmap->div[div][1 + j]);
2596
81
      isl_int_fdiv_q(bmap->ineq[k][j],
2597
81
          bmap->ineq[k][j], bmap->div[div][0]);
2598
81
    }
2599
18
    isl_int_set_si(bmap->ineq[k][1 + total + div], -1);
2600
18
  }
2601
33
2602
33
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2603
33
  return bmap;
2604
0
error:
2605
0
  isl_basic_map_free(bmap);
2606
0
  return NULL;
2607
33
}
2608
2609
/* This function is called right before "div" is eliminated from "bmap"
2610
 * using Fourier-Motzkin.
2611
 * Look through the constraints of "bmap" for constraints on the argument
2612
 * of the integer division and use them to construct constraints on the
2613
 * integer division itself.  These constraints can then be combined
2614
 * during the Fourier-Motzkin elimination.
2615
 * Note that it is only useful to introduce lower bounds on "div"
2616
 * if "bmap" already contains upper bounds on "div" as the newly
2617
 * introduce lower bounds can then be combined with the pre-existing
2618
 * upper bounds.  Similarly for upper bounds.
2619
 * We therefore first check if "bmap" contains any lower and/or upper bounds
2620
 * on "div".
2621
 *
2622
 * It is interesting to note that the introduction of these constraints
2623
 * can indeed lead to more accurate results, even when compared to
2624
 * deriving constraints on the argument of "div" from constraints on "div".
2625
 * Consider, for example, the set
2626
 *
2627
 *  { [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }
2628
 *
2629
 * The second constraint can be rewritten as
2630
 *
2631
 *  2 * [(-i-2j+3)/4] + k >= 0
2632
 *
2633
 * from which we can derive
2634
 *
2635
 *  -i - 2j + 3 >= -2k
2636
 *
2637
 * or
2638
 *
2639
 *  i + 2j <= 3 + 2k
2640
 *
2641
 * Combined with the first constraint, we obtain
2642
 *
2643
 *  -3 <= 3 + 2k  or  k >= -3
2644
 *
2645
 * If, on the other hand we derive a constraint on [(i+2j)/4] from
2646
 * the first constraint, we obtain
2647
 *
2648
 *  [(i + 2j)/4] >= [-3/4] = -1
2649
 *
2650
 * Combining this constraint with the second constraint, we obtain
2651
 *
2652
 *  k >= -2
2653
 */
2654
static __isl_give isl_basic_map *insert_bounds_on_div(
2655
  __isl_take isl_basic_map *bmap, int div)
2656
88
{
2657
88
  int i;
2658
88
  int check_lb, check_ub;
2659
88
  isl_int v;
2660
88
  unsigned total;
2661
88
2662
88
  if (!bmap)
2663
0
    return NULL;
2664
88
2665
88
  if (isl_int_is_zero(bmap->div[div][0]))
2666
88
    
return bmap0
;
2667
88
2668
88
  total = isl_space_dim(bmap->dim, isl_dim_all);
2669
88
2670
88
  check_lb = 0;
2671
88
  check_ub = 0;
2672
397
  for (i = 0; (!check_lb || 
!check_ub27
) &&
i < bmap->n_ineq378
;
++i309
) {
2673
309
    int s = isl_int_sgn(bmap->ineq[i][1 + total + div]);
2674
309
    if (s > 0)
2675
19
      check_ub = 1;
2676
309
    if (s < 0)
2677
20
      check_lb = 1;
2678
309
  }
2679
88
2680
88
  if (!check_lb && 
!check_ub69
)
2681
69
    return bmap;
2682
19
2683
19
  isl_int_init(v);
2684
19
2685
177
  for (i = 0; bmap && i < bmap->n_ineq; 
++i158
) {
2686
158
    if (!isl_int_is_zero(bmap->ineq[i][1 + total + div]))
2687
158
      
continue90
;
2688
68
2689
68
    bmap = insert_bounds_on_div_from_ineq(bmap, div, i, total, v,
2690
68
              check_lb, check_ub);
2691
68
  }
2692
19
2693
19
  isl_int_clear(v);
2694
19
2695
19
  return bmap;
2696
19
}
2697
2698
/* Remove all divs (recursively) involving any of the given dimensions
2699
 * in their definitions.
2700
 */
2701
__isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
2702
  __isl_take isl_basic_map *bmap,
2703
  enum isl_dim_type type, unsigned first, unsigned n)
2704
10.4k
{
2705
10.4k
  int i;
2706
10.4k
2707
10.4k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2708
0
    return isl_basic_map_free(bmap);
2709
10.4k
  first += isl_basic_map_offset(bmap, type);
2710
10.4k
2711
11.5k
  for (i = bmap->n_div - 1; i >= 0; 
--i1.12k
) {
2712
1.12k
    isl_bool involves;
2713
1.12k
2714
1.12k
    involves = div_involves_vars(bmap, i, first, n);
2715
1.12k
    if (involves < 0)
2716
0
      return isl_basic_map_free(bmap);
2717
1.12k
    if (!involves)
2718
1.04k
      continue;
2719
88
    bmap = insert_bounds_on_div(bmap, i);
2720
88
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
2721
88
    if (!bmap)
2722
0
      return NULL;
2723
88
    i = bmap->n_div;
2724
88
  }
2725
10.4k
2726
10.4k
  return bmap;
2727
10.4k
}
2728
2729
__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
2730
  __isl_take isl_basic_set *bset,
2731
  enum isl_dim_type type, unsigned first, unsigned n)
2732
0
{
2733
0
  return isl_basic_map_remove_divs_involving_dims(bset, type, first, n);
2734
0
}
2735
2736
__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
2737
  enum isl_dim_type type, unsigned first, unsigned n)
2738
8.29k
{
2739
8.29k
  int i;
2740
8.29k
2741
8.29k
  if (!map)
2742
0
    return NULL;
2743
8.29k
  if (map->n == 0)
2744
250
    return map;
2745
8.04k
2746
8.04k
  map = isl_map_cow(map);
2747
8.04k
  if (!map)
2748
0
    return NULL;
2749
8.04k
2750
17.1k
  
for (i = 0; 8.04k
i < map->n;
++i9.10k
) {
2751
9.10k
    map->p[i] = isl_basic_map_remove_divs_involving_dims(map->p[i],
2752
9.10k
                type, first, n);
2753
9.10k
    if (!map->p[i])
2754
0
      goto error;
2755
9.10k
  }
2756
8.04k
  return map;
2757
0
error:
2758
0
  isl_map_free(map);
2759
0
  return NULL;
2760
8.04k
}
2761
2762
__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set,
2763
  enum isl_dim_type type, unsigned first, unsigned n)
2764
8.29k
{
2765
8.29k
  return set_from_map(isl_map_remove_divs_involving_dims(set_to_map(set),
2766
8.29k
                    type, first, n));
2767
8.29k
}
2768
2769
/* Does the description of "bmap" depend on the specified dimensions?
2770
 * We also check whether the dimensions appear in any of the div definitions.
2771
 * In principle there is no need for this check.  If the dimensions appear
2772
 * in a div definition, they also appear in the defining constraints of that
2773
 * div.
2774
 */
2775
isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
2776
  enum isl_dim_type type, unsigned first, unsigned n)
2777
59.8k
{
2778
59.8k
  int i;
2779
59.8k
2780
59.8k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2781
0
    return isl_bool_error;
2782
59.8k
2783
59.8k
  first += isl_basic_map_offset(bmap, type);
2784
124k
  for (i = 0; i < bmap->n_eq; 
++i65.0k
)
2785
89.4k
    if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
2786
24.3k
      return isl_bool_true;
2787
82.6k
  
for (i = 0; 35.5k
i < bmap->n_ineq;
++i47.1k
)
2788
52.0k
    if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0)
2789
4.90k
      return isl_bool_true;
2790
35.5k
  
for (i = 0; 30.6k
i < bmap->n_div30.6k
;
++i85
) {
2791
85
    if (isl_int_is_zero(bmap->div[i][0]))
2792
85
      
continue0
;
2793
85
    if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0)
2794
0
      return isl_bool_true;
2795
85
  }
2796
30.6k
2797
30.6k
  return isl_bool_false;
2798
30.6k
}
2799
2800
isl_bool isl_map_involves_dims(__isl_keep isl_map *map,
2801
  enum isl_dim_type type, unsigned first, unsigned n)
2802
4.74k
{
2803
4.74k
  int i;
2804
4.74k
2805
4.74k
  if (!map)
2806
0
    return isl_bool_error;
2807
4.74k
2808
4.74k
  if (first + n > isl_map_dim(map, type))
2809
4.74k
    
isl_die0
(map->ctx, isl_error_invalid,
2810
4.74k
      "index out of bounds", return isl_bool_error);
2811
4.74k
2812
9.52k
  
for (i = 0; 4.74k
i < map->n;
++i4.77k
) {
2813
4.96k
    isl_bool involves = isl_basic_map_involves_dims(map->p[i],
2814
4.96k
                  type, first, n);
2815
4.96k
    if (involves < 0 || involves)
2816
187
      return involves;
2817
4.96k
  }
2818
4.74k
2819
4.74k
  
return isl_bool_false4.56k
;
2820
4.74k
}
2821
2822
isl_bool isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset,
2823
  enum isl_dim_type type, unsigned first, unsigned n)
2824
54.9k
{
2825
54.9k
  return isl_basic_map_involves_dims(bset, type, first, n);
2826
54.9k
}
2827
2828
isl_bool isl_set_involves_dims(__isl_keep isl_set *set,
2829
  enum isl_dim_type type, unsigned first, unsigned n)
2830
4.26k
{
2831
4.26k
  return isl_map_involves_dims(set, type, first, n);
2832
4.26k
}
2833
2834
/* Drop all constraints in bmap that involve any of the dimensions
2835
 * first to first+n-1.
2836
 */
2837
static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
2838
  __isl_take isl_basic_map *bmap, unsigned first, unsigned n)
2839
530k
{
2840
530k
  int i;
2841
530k
2842
530k
  if (n == 0)
2843
90.4k
    return bmap;
2844
440k
2845
440k
  bmap = isl_basic_map_cow(bmap);
2846
440k
2847
440k
  if (!bmap)
2848
0
    return NULL;
2849
440k
2850
443k
  
for (i = bmap->n_eq - 1; 440k
i >= 0;
--i3.52k
) {
2851
3.52k
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
2852
3.09k
      continue;
2853
427
    isl_basic_map_drop_equality(bmap, i);
2854
427
  }
2855
440k
2856
10.7M
  for (i = bmap->n_ineq - 1; i >= 0; 
--i10.3M
) {
2857
10.3M
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
2858
4.29M
      continue;
2859
6.06M
    isl_basic_map_drop_inequality(bmap, i);
2860
6.06M
  }
2861
440k
2862
440k
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2863
440k
  return bmap;
2864
440k
}
2865
2866
/* Drop all constraints in bset that involve any of the dimensions
2867
 * first to first+n-1.
2868
 */
2869
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
2870
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
2871
529k
{
2872
529k
  return isl_basic_map_drop_constraints_involving(bset, first, n);
2873
529k
}
2874
2875
/* Drop all constraints in bmap that do not involve any of the dimensions
2876
 * first to first + n - 1 of the given type.
2877
 */
2878
__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
2879
  __isl_take isl_basic_map *bmap,
2880
  enum isl_dim_type type, unsigned first, unsigned n)
2881
864
{
2882
864
  int i;
2883
864
2884
864
  if (n == 0) {
2885
38
    isl_space *space = isl_basic_map_get_space(bmap);
2886
38
    isl_basic_map_free(bmap);
2887
38
    return isl_basic_map_universe(space);
2888
38
  }
2889
826
  bmap = isl_basic_map_cow(bmap);
2890
826
  if (!bmap)
2891
0
    return NULL;
2892
826
2893
826
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2894
0
    return isl_basic_map_free(bmap);
2895
826
2896
826
  first += isl_basic_map_offset(bmap, type) - 1;
2897
826
2898
944
  for (i = bmap->n_eq - 1; i >= 0; 
--i118
) {
2899
118
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
2900
68
      continue;
2901
50
    isl_basic_map_drop_equality(bmap, i);
2902
50
  }
2903
826
2904
2.73k
  for (i = bmap->n_ineq - 1; i >= 0; 
--i1.90k
) {
2905
1.90k
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
2906
1.59k
      continue;
2907
312
    isl_basic_map_drop_inequality(bmap, i);
2908
312
  }
2909
826
2910
826
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2911
826
  return bmap;
2912
826
}
2913
2914
/* Drop all constraints in bset that do not involve any of the dimensions
2915
 * first to first + n - 1 of the given type.
2916
 */
2917
__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
2918
  __isl_take isl_basic_set *bset,
2919
  enum isl_dim_type type, unsigned first, unsigned n)
2920
699
{
2921
699
  return isl_basic_map_drop_constraints_not_involving_dims(bset,
2922
699
                  type, first, n);
2923
699
}
2924
2925
/* Drop all constraints in bmap that involve any of the dimensions
2926
 * first to first + n - 1 of the given type.
2927
 */
2928
__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
2929
  __isl_take isl_basic_map *bmap,
2930
  enum isl_dim_type type, unsigned first, unsigned n)
2931
59.0k
{
2932
59.0k
  if (!bmap)
2933
0
    return NULL;
2934
59.0k
  if (n == 0)
2935
57.6k
    return bmap;
2936
1.33k
2937
1.33k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2938
0
    return isl_basic_map_free(bmap);
2939
1.33k
2940
1.33k
  bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
2941
1.33k
  first += isl_basic_map_offset(bmap, type) - 1;
2942
1.33k
  return isl_basic_map_drop_constraints_involving(bmap, first, n);
2943
1.33k
}
2944
2945
/* Drop all constraints in bset that involve any of the dimensions
2946
 * first to first + n - 1 of the given type.
2947
 */
2948
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
2949
  __isl_take isl_basic_set *bset,
2950
  enum isl_dim_type type, unsigned first, unsigned n)
2951
699
{
2952
699
  return isl_basic_map_drop_constraints_involving_dims(bset,
2953
699
                  type, first, n);
2954
699
}
2955
2956
/* Drop constraints from "map" by applying "drop" to each basic map.
2957
 */
2958
static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
2959
  enum isl_dim_type type, unsigned first, unsigned n,
2960
  __isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
2961
    enum isl_dim_type type, unsigned first, unsigned n))
2962
128
{
2963
128
  int i;
2964
128
  unsigned dim;
2965
128
2966
128
  if (!map)
2967
0
    return NULL;
2968
128
2969
128
  dim = isl_map_dim(map, type);
2970
128
  if (first + n > dim || first + n < first)
2971
128
    
isl_die0
(isl_map_get_ctx(map), isl_error_invalid,
2972
128
      "index out of bounds", return isl_map_free(map));
2973
128
2974
128
  map = isl_map_cow(map);
2975
128
  if (!map)
2976
0
    return NULL;
2977
128
2978
325
  
for (i = 0; 128
i < map->n;
++i197
) {
2979
197
    map->p[i] = drop(map->p[i], type, first, n);
2980
197
    if (!map->p[i])
2981
0
      return isl_map_free(map);
2982
197
  }
2983
128
2984
128
  if (map->n > 1)
2985
128
    ISL_F_CLR(map, ISL_MAP_DISJOINT);
2986
128
2987
128
  return map;
2988
128
}
2989
2990
/* Drop all constraints in map that involve any of the dimensions
2991
 * first to first + n - 1 of the given type.
2992
 */
2993
__isl_give isl_map *isl_map_drop_constraints_involving_dims(
2994
  __isl_take isl_map *map,
2995
  enum isl_dim_type type, unsigned first, unsigned n)
2996
91
{
2997
91
  if (n == 0)
2998
7
    return map;
2999
84
  return drop_constraints(map, type, first, n,
3000
84
        &isl_basic_map_drop_constraints_involving_dims);
3001
84
}
3002
3003
/* Drop all constraints in "map" that do not involve any of the dimensions
3004
 * first to first + n - 1 of the given type.
3005
 */
3006
__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
3007
  __isl_take isl_map *map,
3008
  enum isl_dim_type type, unsigned first, unsigned n)
3009
44
{
3010
44
  if (n == 0) {
3011
0
    isl_space *space = isl_map_get_space(map);
3012
0
    isl_map_free(map);
3013
0
    return isl_map_universe(space);
3014
0
  }
3015
44
  return drop_constraints(map, type, first, n,
3016
44
          &isl_basic_map_drop_constraints_not_involving_dims);
3017
44
}
3018
3019
/* Drop all constraints in set that involve any of the dimensions
3020
 * first to first + n - 1 of the given type.
3021
 */
3022
__isl_give isl_set *isl_set_drop_constraints_involving_dims(
3023
  __isl_take isl_set *set,
3024
  enum isl_dim_type type, unsigned first, unsigned n)
3025
67
{
3026
67
  return isl_map_drop_constraints_involving_dims(set, type, first, n);
3027
67
}
3028
3029
/* Drop all constraints in "set" that do not involve any of the dimensions
3030
 * first to first + n - 1 of the given type.
3031
 */
3032
__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
3033
  __isl_take isl_set *set,
3034
  enum isl_dim_type type, unsigned first, unsigned n)
3035
44
{
3036
44
  return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
3037
44
}
3038
3039
/* Does local variable "div" of "bmap" have a complete explicit representation?
3040
 * Having a complete explicit representation requires not only
3041
 * an explicit representation, but also that all local variables
3042
 * that appear in this explicit representation in turn have
3043
 * a complete explicit representation.
3044
 */
3045
isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div)
3046
70.1k
{
3047
70.1k
  int i;
3048
70.1k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
3049
70.1k
  isl_bool marked;
3050
70.1k
3051
70.1k
  marked = isl_basic_map_div_is_marked_unknown(bmap, div);
3052
70.1k
  if (marked < 0 || marked)
3053
13.0k
    return isl_bool_not(marked);
3054
57.0k
3055
153k
  
for (i = bmap->n_div - 1; 57.0k
i >= 0;
--i96.7k
) {
3056
96.7k
    isl_bool known;
3057
96.7k
3058
96.7k
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
3059
96.7k
      
continue95.0k
;
3060
1.69k
    known = isl_basic_map_div_is_known(bmap, i);
3061
1.69k
    if (known < 0 || !known)
3062
1
      return known;
3063
1.69k
  }
3064
57.0k
3065
57.0k
  
return isl_bool_true57.0k
;
3066
57.0k
}
3067
3068
/* Remove all divs that are unknown or defined in terms of unknown divs.
3069
 */
3070
__isl_give isl_basic_map *isl_basic_map_remove_unknown_divs(
3071
  __isl_take isl_basic_map *bmap)
3072
182k
{
3073
182k
  int i;
3074
182k
3075
182k
  if (!bmap)
3076
0
    return NULL;
3077
182k
3078
183k
  
for (i = bmap->n_div - 1; 182k
i >= 0;
--i957
) {
3079
957
    if (isl_basic_map_div_is_known(bmap, i))
3080
954
      continue;
3081
3
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
3082
3
    if (!bmap)
3083
0
      return NULL;
3084
3
    i = bmap->n_div;
3085
3
  }
3086
182k
3087
182k
  return bmap;
3088
182k
}
3089
3090
/* Remove all divs that are unknown or defined in terms of unknown divs.
3091
 */
3092
__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
3093
  __isl_take isl_basic_set *bset)
3094
5.83k
{
3095
5.83k
  return isl_basic_map_remove_unknown_divs(bset);
3096
5.83k
}
3097
3098
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
3099
161k
{
3100
161k
  int i;
3101
161k
3102
161k
  if (!map)
3103
0
    return NULL;
3104
161k
  if (map->n == 0)
3105
250
    return map;
3106
161k
3107
161k
  map = isl_map_cow(map);
3108
161k
  if (!map)
3109
0
    return NULL;
3110
161k
3111
338k
  
for (i = 0; 161k
i < map->n;
++i177k
) {
3112
177k
    map->p[i] = isl_basic_map_remove_unknown_divs(map->p[i]);
3113
177k
    if (!map->p[i])
3114
0
      goto error;
3115
177k
  }
3116
161k
  return map;
3117
0
error:
3118
0
  isl_map_free(map);
3119
0
  return NULL;
3120
161k
}
3121
3122
__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
3123
9.03k
{
3124
9.03k
  return set_from_map(isl_map_remove_unknown_divs(set_to_map(set)));
3125
9.03k
}
3126
3127
__isl_give isl_basic_set *isl_basic_set_remove_dims(
3128
  __isl_take isl_basic_set *bset,
3129
  enum isl_dim_type type, unsigned first, unsigned n)
3130
2.98k
{
3131
2.98k
  isl_basic_map *bmap = bset_to_bmap(bset);
3132
2.98k
  bmap = isl_basic_map_remove_dims(bmap, type, first, n);
3133
2.98k
  return bset_from_bmap(bmap);
3134
2.98k
}
3135
3136
__isl_give isl_map *isl_map_remove_dims(__isl_take isl_map *map,
3137
  enum isl_dim_type type, unsigned first, unsigned n)
3138
1.79k
{
3139
1.79k
  int i;
3140
1.79k
3141
1.79k
  if (n == 0)
3142
1.22k
    return map;
3143
572
3144
572
  map = isl_map_cow(map);
3145
572
  if (!map)
3146
0
    return NULL;
3147
572
  isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
3148
572
  
3149
1.29k
  
for (i = 0; 572
i < map->n;
++i720
) {
3150
720
    map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
3151
720
      isl_basic_map_offset(map->p[i], type) - 1 + first, n);
3152
720
    if (!map->p[i])
3153
0
      goto error;
3154
720
  }
3155
572
  map = isl_map_drop(map, type, first, n);
3156
572
  return map;
3157
0
error:
3158
0
  isl_map_free(map);
3159
0
  return NULL;
3160
572
}
3161
3162
__isl_give isl_set *isl_set_remove_dims(__isl_take isl_set *bset,
3163
  enum isl_dim_type type, unsigned first, unsigned n)
3164
1.69k
{
3165
1.69k
  return set_from_map(isl_map_remove_dims(set_to_map(bset),
3166
1.69k
            type, first, n));
3167
1.69k
}
3168
3169
/* Project out n inputs starting at first using Fourier-Motzkin */
3170
struct isl_map *isl_map_remove_inputs(struct isl_map *map,
3171
  unsigned first, unsigned n)
3172
0
{
3173
0
  return isl_map_remove_dims(map, isl_dim_in, first, n);
3174
0
}
3175
3176
static void dump_term(struct isl_basic_map *bmap,
3177
      isl_int c, int pos, FILE *out)
3178
0
{
3179
0
  const char *name;
3180
0
  unsigned in = isl_basic_map_dim(bmap, isl_dim_in);
3181
0
  unsigned dim = in + isl_basic_map_dim(bmap, isl_dim_out);
3182
0
  unsigned nparam = isl_basic_map_dim(bmap, isl_dim_param);
3183
0
  if (!pos)
3184
0
    isl_int_print(out, c, 0);
3185
0
  else {
3186
0
    if (!isl_int_is_one(c))
3187
0
      isl_int_print(out, c, 0);
3188
0
    if (pos < 1 + nparam) {
3189
0
      name = isl_space_get_dim_name(bmap->dim,
3190
0
            isl_dim_param, pos - 1);
3191
0
      if (name)
3192
0
        fprintf(out, "%s", name);
3193
0
      else
3194
0
        fprintf(out, "p%d", pos - 1);
3195
0
    } else if (pos < 1 + nparam + in)
3196
0
      fprintf(out, "i%d", pos - 1 - nparam);
3197
0
    else if (pos < 1 + nparam + dim)
3198
0
      fprintf(out, "o%d", pos - 1 - nparam - in);
3199
0
    else
3200
0
      fprintf(out, "e%d", pos - 1 - nparam - dim);
3201
0
  }
3202
0
}
3203
3204
static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
3205
        int sign, FILE *out)
3206
0
{
3207
0
  int i;
3208
0
  int first;
3209
0
  unsigned len = 1 + isl_basic_map_total_dim(bmap);
3210
0
  isl_int v;
3211
0
3212
0
  isl_int_init(v);
3213
0
  for (i = 0, first = 1; i < len; ++i) {
3214
0
    if (isl_int_sgn(c[i]) * sign <= 0)
3215
0
      continue;
3216
0
    if (!first)
3217
0
      fprintf(out, " + ");
3218
0
    first = 0;
3219
0
    isl_int_abs(v, c[i]);
3220
0
    dump_term(bmap, v, i, out);
3221
0
  }
3222
0
  isl_int_clear(v);
3223
0
  if (first)
3224
0
    fprintf(out, "0");
3225
0
}
3226
3227
static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
3228
        const char *op, FILE *out, int indent)
3229
0
{
3230
0
  int i;
3231
0
3232
0
  fprintf(out, "%*s", indent, "");
3233
0
3234
0
  dump_constraint_sign(bmap, c, 1, out);
3235
0
  fprintf(out, " %s ", op);
3236
0
  dump_constraint_sign(bmap, c, -1, out);
3237
0
3238
0
  fprintf(out, "\n");
3239
0
3240
0
  for (i = bmap->n_div; i < bmap->extra; ++i) {
3241
0
    if (isl_int_is_zero(c[1+isl_space_dim(bmap->dim, isl_dim_all)+i]))
3242
0
      continue;
3243
0
    fprintf(out, "%*s", indent, "");
3244
0
    fprintf(out, "ERROR: unused div coefficient not zero\n");
3245
0
    abort();
3246
0
  }
3247
0
}
3248
3249
static void dump_constraints(struct isl_basic_map *bmap,
3250
        isl_int **c, unsigned n,
3251
        const char *op, FILE *out, int indent)
3252
0
{
3253
0
  int i;
3254
0
3255
0
  for (i = 0; i < n; ++i)
3256
0
    dump_constraint(bmap, c[i], op, out, indent);
3257
0
}
3258
3259
static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
3260
0
{
3261
0
  int j;
3262
0
  int first = 1;
3263
0
  unsigned total = isl_basic_map_total_dim(bmap);
3264
0
3265
0
  for (j = 0; j < 1 + total; ++j) {
3266
0
    if (isl_int_is_zero(exp[j]))
3267
0
      continue;
3268
0
    if (!first && isl_int_is_pos(exp[j]))
3269
0
      fprintf(out, "+");
3270
0
    dump_term(bmap, exp[j], j, out);
3271
0
    first = 0;
3272
0
  }
3273
0
}
3274
3275
static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
3276
0
{
3277
0
  int i;
3278
0
3279
0
  dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
3280
0
  dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
3281
0
3282
0
  for (i = 0; i < bmap->n_div; ++i) {
3283
0
    fprintf(out, "%*s", indent, "");
3284
0
    fprintf(out, "e%d = [(", i);
3285
0
    dump_affine(bmap, bmap->div[i]+1, out);
3286
0
    fprintf(out, ")/");
3287
0
    isl_int_print(out, bmap->div[i][0], 0);
3288
0
    fprintf(out, "]\n");
3289
0
  }
3290
0
}
3291
3292
void isl_basic_set_print_internal(struct isl_basic_set *bset,
3293
  FILE *out, int indent)
3294
0
{
3295
0
  if (!bset) {
3296
0
    fprintf(out, "null basic set\n");
3297
0
    return;
3298
0
  }
3299
0
3300
0
  fprintf(out, "%*s", indent, "");
3301
0
  fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
3302
0
      bset->ref, bset->dim->nparam, bset->dim->n_out,
3303
0
      bset->extra, bset->flags);
3304
0
  dump(bset_to_bmap(bset), out, indent);
3305
0
}
3306
3307
void isl_basic_map_print_internal(struct isl_basic_map *bmap,
3308
  FILE *out, int indent)
3309
0
{
3310
0
  if (!bmap) {
3311
0
    fprintf(out, "null basic map\n");
3312
0
    return;
3313
0
  }
3314
0
3315
0
  fprintf(out, "%*s", indent, "");
3316
0
  fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
3317
0
      "flags: %x, n_name: %d\n",
3318
0
    bmap->ref,
3319
0
    bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
3320
0
    bmap->extra, bmap->flags, bmap->dim->n_id);
3321
0
  dump(bmap, out, indent);
3322
0
}
3323
3324
int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
3325
20.3k
{
3326
20.3k
  unsigned total;
3327
20.3k
  if (!bmap)
3328
0
    return -1;
3329
20.3k
  total = isl_basic_map_total_dim(bmap);
3330
20.3k
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
3331
20.3k
  isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
3332
20.3k
  isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
3333
20.3k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
3334
20.3k
  return 0;
3335
20.3k
}
3336
3337
__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *space, int n,
3338
  unsigned flags)
3339
251k
{
3340
251k
  if (!space)
3341
0
    return NULL;
3342
251k
  if (isl_space_dim(space, isl_dim_in) != 0)
3343
251k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
3344
251k
      "set cannot have input dimensions", goto error);
3345
251k
  return isl_map_alloc_space(space, n, flags);
3346
0
error:
3347
0
  isl_space_free(space);
3348
0
  return NULL;
3349
251k
}
3350
3351
/* Make sure "map" has room for at least "n" more basic maps.
3352
 */
3353
__isl_give isl_map *isl_map_grow(__isl_take isl_map *map, int n)
3354
6.61k
{
3355
6.61k
  int i;
3356
6.61k
  struct isl_map *grown = NULL;
3357
6.61k
3358
6.61k
  if (!map)
3359
0
    return NULL;
3360
6.61k
  isl_assert(map->ctx, n >= 0, goto error);
3361
6.61k
  if (map->n + n <= map->size)
3362
6.17k
    return map;
3363
438
  grown = isl_map_alloc_space(isl_map_get_space(map), map->n + n, map->flags);
3364
438
  if (!grown)
3365
0
    goto error;
3366
1.00k
  
for (i = 0; 438
i < map->n;
++i562
) {
3367
562
    grown->p[i] = isl_basic_map_copy(map->p[i]);
3368
562
    if (!grown->p[i])
3369
0
      goto error;
3370
562
    grown->n++;
3371
562
  }
3372
438
  isl_map_free(map);
3373
438
  return grown;
3374
0
error:
3375
0
  isl_map_free(grown);
3376
0
  isl_map_free(map);
3377
0
  return NULL;
3378
438
}
3379
3380
/* Make sure "set" has room for at least "n" more basic sets.
3381
 */
3382
struct isl_set *isl_set_grow(struct isl_set *set, int n)
3383
3.23k
{
3384
3.23k
  return set_from_map(isl_map_grow(set_to_map(set), n));
3385
3.23k
}
3386
3387
__isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset)
3388
79.4k
{
3389
79.4k
  return isl_map_from_basic_map(bset);
3390
79.4k
}
3391
3392
__isl_give isl_map *isl_map_from_basic_map(__isl_take isl_basic_map *bmap)
3393
200k
{
3394
200k
  struct isl_map *map;
3395
200k
3396
200k
  if (!bmap)
3397
0
    return NULL;
3398
200k
3399
200k
  map = isl_map_alloc_space(isl_space_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
3400
200k
  return isl_map_add_basic_map(map, bmap);
3401
200k
}
3402
3403
__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
3404
            __isl_take isl_basic_set *bset)
3405
126k
{
3406
126k
  return set_from_map(isl_map_add_basic_map(set_to_map(set),
3407
126k
            bset_to_bmap(bset)));
3408
126k
}
3409
3410
__isl_null isl_set *isl_set_free(__isl_take isl_set *set)
3411
1.53M
{
3412
1.53M
  return isl_map_free(set);
3413
1.53M
}
3414
3415
void isl_set_print_internal(struct isl_set *set, FILE *out, int indent)
3416
0
{
3417
0
  int i;
3418
0
3419
0
  if (!set) {
3420
0
    fprintf(out, "null set\n");
3421
0
    return;
3422
0
  }
3423
0
3424
0
  fprintf(out, "%*s", indent, "");
3425
0
  fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
3426
0
      set->ref, set->n, set->dim->nparam, set->dim->n_out,
3427
0
      set->flags);
3428
0
  for (i = 0; i < set->n; ++i) {
3429
0
    fprintf(out, "%*s", indent, "");
3430
0
    fprintf(out, "basic set %d:\n", i);
3431
0
    isl_basic_set_print_internal(set->p[i], out, indent+4);
3432
0
  }
3433
0
}
3434
3435
void isl_map_print_internal(struct isl_map *map, FILE *out, int indent)
3436
0
{
3437
0
  int i;
3438
0
3439
0
  if (!map) {
3440
0
    fprintf(out, "null map\n");
3441
0
    return;
3442
0
  }
3443
0
3444
0
  fprintf(out, "%*s", indent, "");
3445
0
  fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
3446
0
         "flags: %x, n_name: %d\n",
3447
0
      map->ref, map->n, map->dim->nparam, map->dim->n_in,
3448
0
      map->dim->n_out, map->flags, map->dim->n_id);
3449
0
  for (i = 0; i < map->n; ++i) {
3450
0
    fprintf(out, "%*s", indent, "");
3451
0
    fprintf(out, "basic map %d:\n", i);
3452
0
    isl_basic_map_print_internal(map->p[i], out, indent+4);
3453
0
  }
3454
0
}
3455
3456
__isl_give isl_basic_map *isl_basic_map_intersect_domain(
3457
  __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
3458
66.0k
{
3459
66.0k
  struct isl_basic_map *bmap_domain;
3460
66.0k
3461
66.0k
  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
3462
0
    goto error;
3463
66.0k
3464
66.0k
  if (isl_space_dim(bset->dim, isl_dim_set) != 0)
3465
66.0k
    isl_assert(bset->ctx,
3466
66.0k
        isl_basic_map_compatible_domain(bmap, bset), goto error);
3467
66.0k
3468
66.0k
  bmap = isl_basic_map_cow(bmap);
3469
66.0k
  if (!bmap)
3470
0
    goto error;
3471
66.0k
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
3472
66.0k
      bset->n_div, bset->n_eq, bset->n_ineq);
3473
66.0k
  bmap_domain = isl_basic_map_from_domain(bset);
3474
66.0k
  bmap = add_constraints(bmap, bmap_domain, 0, 0);
3475
66.0k
3476
66.0k
  bmap = isl_basic_map_simplify(bmap);
3477
66.0k
  return isl_basic_map_finalize(bmap);
3478
0
error:
3479
0
  isl_basic_map_free(bmap);
3480
0
  isl_basic_set_free(bset);
3481
0
  return NULL;
3482
66.0k
}
3483
3484
/* Check that the space of "bset" is the same as that of the range of "bmap".
3485
 */
3486
static isl_stat isl_basic_map_check_compatible_range(
3487
  __isl_keep isl_basic_map *bmap, __isl_keep isl_basic_set *bset)
3488
6.52k
{
3489
6.52k
  isl_bool ok;
3490
6.52k
3491
6.52k
  ok = isl_basic_map_compatible_range(bmap, bset);
3492
6.52k
  if (ok < 0)
3493
0
    return isl_stat_error;
3494
6.52k
  if (!ok)
3495
6.52k
    
isl_die0
(isl_basic_set_get_ctx(bset), isl_error_invalid,
3496
6.52k
      "incompatible spaces", return isl_stat_error);
3497
6.52k
3498
6.52k
  return isl_stat_ok;
3499
6.52k
}
3500
3501
__isl_give isl_basic_map *isl_basic_map_intersect_range(
3502
  __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
3503
6.53k
{
3504
6.53k
  struct isl_basic_map *bmap_range;
3505
6.53k
3506
6.53k
  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
3507
0
    goto error;
3508
6.53k
3509
6.53k
  if (isl_space_dim(bset->dim, isl_dim_set) != 0 &&
3510
6.53k
      
isl_basic_map_check_compatible_range(bmap, bset) < 06.52k
)
3511
0
    goto error;
3512
6.53k
3513
6.53k
  if (isl_basic_set_plain_is_universe(bset)) {
3514
0
    isl_basic_set_free(bset);
3515
0
    return bmap;
3516
0
  }
3517
6.53k
3518
6.53k
  bmap = isl_basic_map_cow(bmap);
3519
6.53k
  if (!bmap)
3520
0
    goto error;
3521
6.53k
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
3522
6.53k
      bset->n_div, bset->n_eq, bset->n_ineq);
3523
6.53k
  bmap_range = bset_to_bmap(bset);
3524
6.53k
  bmap = add_constraints(bmap, bmap_range, 0, 0);
3525
6.53k
3526
6.53k
  bmap = isl_basic_map_simplify(bmap);
3527
6.53k
  return isl_basic_map_finalize(bmap);
3528
0
error:
3529
0
  isl_basic_map_free(bmap);
3530
0
  isl_basic_set_free(bset);
3531
0
  return NULL;
3532
6.53k
}
3533
3534
isl_bool isl_basic_map_contains(__isl_keep isl_basic_map *bmap,
3535
  __isl_keep isl_vec *vec)
3536
1.56M
{
3537
1.56M
  int i;
3538
1.56M
  unsigned total;
3539
1.56M
  isl_int s;
3540
1.56M
3541
1.56M
  if (!bmap || !vec)
3542
0
    return isl_bool_error;
3543
1.56M
3544
1.56M
  total = 1 + isl_basic_map_total_dim(bmap);
3545
1.56M
  if (total != vec->size)
3546
16.3k
    return isl_bool_false;
3547
1.54M
3548
1.54M
  isl_int_init(s);
3549
1.54M
3550
2.54M
  for (i = 0; i < bmap->n_eq; 
++i997k
) {
3551
1.39M
    isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
3552
1.39M
    if (!isl_int_is_zero(s)) {
3553
401k
      isl_int_clear(s);
3554
401k
      return isl_bool_false;
3555
401k
    }
3556
1.39M
  }
3557
1.54M
3558
6.64M
  
for (i = 0; 1.14M
i < bmap->n_ineq;
++i5.49M
) {
3559
5.87M
    isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
3560
5.87M
    if (isl_int_is_neg(s)) {
3561
375k
      isl_int_clear(s);
3562
375k
      return isl_bool_false;
3563
375k
    }
3564
5.87M
  }
3565
1.14M
3566
1.14M
  
isl_int_clear769k
(s);
3567
769k
3568
769k
  return isl_bool_true;
3569
1.14M
}
3570
3571
isl_bool isl_basic_set_contains(__isl_keep isl_basic_set *bset,
3572
  __isl_keep isl_vec *vec)
3573
841k
{
3574
841k
  return isl_basic_map_contains(bset_to_bmap(bset), vec);
3575
841k
}
3576
3577
__isl_give isl_basic_map *isl_basic_map_intersect(
3578
  __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
3579
303k
{
3580
303k
  struct isl_vec *sample = NULL;
3581
303k
3582
303k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
3583
0
    goto error;
3584
303k
  if (isl_space_dim(bmap1->dim, isl_dim_all) ==
3585
303k
        isl_space_dim(bmap1->dim, isl_dim_param) &&
3586
303k
      isl_space_dim(bmap2->dim, isl_dim_all) !=
3587
86.2k
        isl_space_dim(bmap2->dim, isl_dim_param))
3588
0
    return isl_basic_map_intersect(bmap2, bmap1);
3589
303k
3590
303k
  if (isl_space_dim(bmap2->dim, isl_dim_all) !=
3591
303k
          isl_space_dim(bmap2->dim, isl_dim_param))
3592
303k
    isl_assert(bmap1->ctx,
3593
303k
          isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);
3594
303k
3595
303k
  if (isl_basic_map_plain_is_empty(bmap1)) {
3596
29
    isl_basic_map_free(bmap2);
3597
29
    return bmap1;
3598
29
  }
3599
303k
  if (isl_basic_map_plain_is_empty(bmap2)) {
3600
0
    isl_basic_map_free(bmap1);
3601
0
    return bmap2;
3602
0
  }
3603
303k
3604
303k
  if (bmap1->sample &&
3605
303k
      
isl_basic_map_contains(bmap1, bmap1->sample) > 0116k
&&
3606
303k
      
isl_basic_map_contains(bmap2, bmap1->sample) > 0105k
)
3607
40.4k
    sample = isl_vec_copy(bmap1->sample);
3608
262k
  else if (bmap2->sample &&
3609
262k
      
isl_basic_map_contains(bmap1, bmap2->sample) > 0100k
&&
3610
262k
      
isl_basic_map_contains(bmap2, bmap2->sample) > 024.1k
)
3611
23.9k
    sample = isl_vec_copy(bmap2->sample);
3612
303k
3613
303k
  bmap1 = isl_basic_map_cow(bmap1);
3614
303k
  if (!bmap1)
3615
0
    goto error;
3616
303k
  bmap1 = isl_basic_map_extend_space(bmap1, isl_space_copy(bmap1->dim),
3617
303k
      bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
3618
303k
  bmap1 = add_constraints(bmap1, bmap2, 0, 0);
3619
303k
3620
303k
  if (!bmap1)
3621
0
    isl_vec_free(sample);
3622
303k
  else if (sample) {
3623
64.3k
    isl_vec_free(bmap1->sample);
3624
64.3k
    bmap1->sample = sample;
3625
64.3k
  }
3626
303k
3627
303k
  bmap1 = isl_basic_map_simplify(bmap1);
3628
303k
  return isl_basic_map_finalize(bmap1);
3629
0
error:
3630
0
  if (sample)
3631
0
    isl_vec_free(sample);
3632
0
  isl_basic_map_free(bmap1);
3633
0
  isl_basic_map_free(bmap2);
3634
0
  return NULL;
3635
303k
}
3636
3637
struct isl_basic_set *isl_basic_set_intersect(
3638
    struct isl_basic_set *bset1, struct isl_basic_set *bset2)
3639
73.2k
{
3640
73.2k
  return bset_from_bmap(isl_basic_map_intersect(bset_to_bmap(bset1),
3641
73.2k
              bset_to_bmap(bset2)));
3642
73.2k
}
3643
3644
__isl_give isl_basic_set *isl_basic_set_intersect_params(
3645
  __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
3646
0
{
3647
0
  return isl_basic_set_intersect(bset1, bset2);
3648
0
}
3649
3650
/* Special case of isl_map_intersect, where both map1 and map2
3651
 * are convex, without any divs and such that either map1 or map2
3652
 * contains a single constraint.  This constraint is then simply
3653
 * added to the other map.
3654
 */
3655
static __isl_give isl_map *map_intersect_add_constraint(
3656
  __isl_take isl_map *map1, __isl_take isl_map *map2)
3657
41.0k
{
3658
41.0k
  isl_assert(map1->ctx, map1->n == 1, goto error);
3659
41.0k
  isl_assert(map2->ctx, map1->n == 1, goto error);
3660
41.0k
  isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
3661
41.0k
  isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
3662
41.0k
3663
41.0k
  if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
3664
2.41k
    return isl_map_intersect(map2, map1);
3665
38.6k
3666
38.6k
  map1 = isl_map_cow(map1);
3667
38.6k
  if (!map1)
3668
0
    goto error;
3669
38.6k
  if (isl_map_plain_is_empty(map1)) {
3670
0
    isl_map_free(map2);
3671
0
    return map1;
3672
0
  }
3673
38.6k
  map1->p[0] = isl_basic_map_cow(map1->p[0]);
3674
38.6k
  if (map2->p[0]->n_eq == 1)
3675
19.7k
    map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
3676
18.9k
  else
3677
18.9k
    map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
3678
18.9k
              map2->p[0]->ineq[0]);
3679
38.6k
3680
38.6k
  map1->p[0] = isl_basic_map_simplify(map1->p[0]);
3681
38.6k
  map1->p[0] = isl_basic_map_finalize(map1->p[0]);
3682
38.6k
  if (!map1->p[0])
3683
0
    goto error;
3684
38.6k
3685
38.6k
  if (isl_basic_map_plain_is_empty(map1->p[0])) {
3686
4.92k
    isl_basic_map_free(map1->p[0]);
3687
4.92k
    map1->n = 0;
3688
4.92k
  }
3689
38.6k
3690
38.6k
  isl_map_free(map2);
3691
38.6k
3692
38.6k
  return map1;
3693
0
error:
3694
0
  isl_map_free(map1);
3695
0
  isl_map_free(map2);
3696
0
  return NULL;
3697
38.6k
}
3698
3699
/* map2 may be either a parameter domain or a map living in the same
3700
 * space as map1.
3701
 */
3702
static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1,
3703
  __isl_take isl_map *map2)
3704
393k
{
3705
393k
  unsigned flags = 0;
3706
393k
  isl_map *result;
3707
393k
  int i, j;
3708
393k
3709
393k
  if (!map1 || !map2)
3710
0
    goto error;
3711
393k
3712
393k
  if ((isl_map_plain_is_empty(map1) ||
3713
393k
       
isl_map_plain_is_universe(map2)380k
) &&
3714
393k
      
isl_space_is_equal(map1->dim, map2->dim)208k
) {
3715
196k
    isl_map_free(map2);
3716
196k
    return map1;
3717
196k
  }
3718
197k
  if ((isl_map_plain_is_empty(map2) ||
3719
197k
       
isl_map_plain_is_universe(map1)192k
) &&
3720
197k
      
isl_space_is_equal(map1->dim, map2->dim)103k
) {
3721
82.8k
    isl_map_free(map1);
3722
82.8k
    return map2;
3723
82.8k
  }
3724
114k
3725
114k
  if (map1->n == 1 && 
map2->n == 1100k
&&
3726
114k
      
map1->p[0]->n_div == 094.9k
&&
map2->p[0]->n_div == 091.4k
&&
3727
114k
      
isl_space_is_equal(map1->dim, map2->dim)90.5k
&&
3728
114k
      
(68.7k
map1->p[0]->n_eq + map1->p[0]->n_ineq == 168.7k
||
3729
68.7k
       
map2->p[0]->n_eq + map2->p[0]->n_ineq == 158.5k
))
3730
41.0k
    return map_intersect_add_constraint(map1, map2);
3731
73.5k
3732
73.5k
  if (isl_space_dim(map2->dim, isl_dim_all) !=
3733
73.5k
        isl_space_dim(map2->dim, isl_dim_param))
3734
73.5k
    isl_assert(map1->ctx,
3735
73.5k
          isl_space_is_equal(map1->dim, map2->dim), goto error);
3736
73.5k
3737
73.5k
  if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
3738
73.5k
      
ISL_F_ISSET58.5k
(map2, ISL_MAP_DISJOINT))
3739
73.5k
    
ISL_FL_SET54.3k
(flags, ISL_MAP_DISJOINT);
3740
73.5k
3741
73.5k
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
3742
73.5k
        map1->n * map2->n, flags);
3743
73.5k
  if (!result)
3744
0
    goto error;
3745
173k
  
for (i = 0; 73.5k
i < map1->n;
++i100k
)
3746
282k
    
for (j = 0; 100k
j < map2->n;
++j181k
) {
3747
181k
      struct isl_basic_map *part;
3748
181k
      part = isl_basic_map_intersect(
3749
181k
            isl_basic_map_copy(map1->p[i]),
3750
181k
            isl_basic_map_copy(map2->p[j]));
3751
181k
      if (isl_basic_map_is_empty(part) < 0)
3752
0
        part = isl_basic_map_free(part);
3753
181k
      result = isl_map_add_basic_map(result, part);
3754
181k
      if (!result)
3755
0
        goto error;
3756
181k
    }
3757
73.5k
  isl_map_free(map1);
3758
73.5k
  isl_map_free(map2);
3759
73.5k
  return result;
3760
0
error:
3761
0
  isl_map_free(map1);
3762
0
  isl_map_free(map2);
3763
0
  return NULL;
3764
73.5k
}
3765
3766
static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
3767
  __isl_take isl_map *map2)
3768
352k
{
3769
352k
  if (!map1 || !map2)
3770
0
    goto error;
3771
352k
  if (!isl_space_is_equal(map1->dim, map2->dim))
3772
352k
    
isl_die0
(isl_map_get_ctx(map1), isl_error_invalid,
3773
352k
      "spaces don't match", goto error);
3774
352k
  return map_intersect_internal(map1, map2);
3775
0
error:
3776
0
  isl_map_free(map1);
3777
0
  isl_map_free(map2);
3778
0
  return NULL;
3779
352k
}
3780
3781
__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
3782
  __isl_take isl_map *map2)
3783
351k
{
3784
351k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect);
3785
351k
}
3786
3787
struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
3788
281k
{
3789
281k
  return set_from_map(isl_map_intersect(set_to_map(set1),
3790
281k
                set_to_map(set2)));
3791
281k
}
3792
3793
/* map_intersect_internal accepts intersections
3794
 * with parameter domains, so we can just call that function.
3795
 */
3796
static __isl_give isl_map *map_intersect_params(__isl_take isl_map *map,
3797
    __isl_take isl_set *params)
3798
41.6k
{
3799
41.6k
  return map_intersect_internal(map, params);
3800
41.6k
}
3801
3802
__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1,
3803
  __isl_take isl_map *map2)
3804
41.6k
{
3805
41.6k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect_params);
3806
41.6k
}
3807
3808
__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
3809
    __isl_take isl_set *params)
3810
10.1k
{
3811
10.1k
  return isl_map_intersect_params(set, params);
3812
10.1k
}
3813
3814
__isl_give isl_basic_map *isl_basic_map_reverse(__isl_take isl_basic_map *bmap)
3815
180k
{
3816
180k
  isl_space *space;
3817
180k
  unsigned pos, n1, n2;
3818
180k
3819
180k
  if (!bmap)
3820
0
    return NULL;
3821
180k
  bmap = isl_basic_map_cow(bmap);
3822
180k
  if (!bmap)
3823
0
    return NULL;
3824
180k
  space = isl_space_reverse(isl_space_copy(bmap->dim));
3825
180k
  pos = isl_basic_map_offset(bmap, isl_dim_in);
3826
180k
  n1 = isl_basic_map_dim(bmap, isl_dim_in);
3827
180k
  n2 = isl_basic_map_dim(bmap, isl_dim_out);
3828
180k
  bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
3829
180k
  return isl_basic_map_reset_space(bmap, space);
3830
180k
}
3831
3832
static __isl_give isl_basic_map *basic_map_space_reset(
3833
  __isl_take isl_basic_map *bmap, enum isl_dim_type type)
3834
46.4k
{
3835
46.4k
  isl_space *space;
3836
46.4k
3837
46.4k
  if (!bmap)
3838
0
    return NULL;
3839
46.4k
  if (!isl_space_is_named_or_nested(bmap->dim, type))
3840
42.5k
    return bmap;
3841
3.86k
3842
3.86k
  space = isl_basic_map_get_space(bmap);
3843
3.86k
  space = isl_space_reset(space, type);
3844
3.86k
  bmap = isl_basic_map_reset_space(bmap, space);
3845
3.86k
  return bmap;
3846
3.86k
}
3847
3848
__isl_give isl_basic_map *isl_basic_map_insert_dims(
3849
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
3850
  unsigned pos, unsigned n)
3851
78.3k
{
3852
78.3k
  isl_bool rational;
3853
78.3k
  isl_space *res_dim;
3854
78.3k
  struct isl_basic_map *res;
3855
78.3k
  struct isl_dim_map *dim_map;
3856
78.3k
  unsigned total, off;
3857
78.3k
  enum isl_dim_type t;
3858
78.3k
3859
78.3k
  if (n == 0)
3860
19.1k
    return basic_map_space_reset(bmap, type);
3861
59.2k
3862
59.2k
  if (!bmap)
3863
0
    return NULL;
3864
59.2k
3865
59.2k
  res_dim = isl_space_insert_dims(isl_basic_map_get_space(bmap), type, pos, n);
3866
59.2k
3867
59.2k
  total = isl_basic_map_total_dim(bmap) + n;
3868
59.2k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
3869
59.2k
  off = 0;
3870
236k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t177k
) {
3871
177k
    if (t != type) {
3872
118k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
3873
118k
    } else {
3874
59.2k
      unsigned size = isl_basic_map_dim(bmap, t);
3875
59.2k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3876
59.2k
            0, pos, off);
3877
59.2k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3878
59.2k
            pos, size - pos, off + pos + n);
3879
59.2k
    }
3880
177k
    off += isl_space_dim(res_dim, t);
3881
177k
  }
3882
59.2k
  isl_dim_map_div(dim_map, bmap, off);
3883
59.2k
3884
59.2k
  res = isl_basic_map_alloc_space(res_dim,
3885
59.2k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
3886
59.2k
  rational = isl_basic_map_is_rational(bmap);
3887
59.2k
  if (rational < 0)
3888
0
    res = isl_basic_map_free(res);
3889
59.2k
  if (rational)
3890
0
    res = isl_basic_map_set_rational(res);
3891
59.2k
  if (isl_basic_map_plain_is_empty(bmap)) {
3892
1.58k
    isl_basic_map_free(bmap);
3893
1.58k
    free(dim_map);
3894
1.58k
    return isl_basic_map_set_to_empty(res);
3895
1.58k
  }
3896
57.6k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
3897
57.6k
  return isl_basic_map_finalize(res);
3898
57.6k
}
3899
3900
__isl_give isl_basic_set *isl_basic_set_insert_dims(
3901
  __isl_take isl_basic_set *bset,
3902
  enum isl_dim_type type, unsigned pos, unsigned n)
3903
0
{
3904
0
  return isl_basic_map_insert_dims(bset, type, pos, n);
3905
0
}
3906
3907
__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap,
3908
    enum isl_dim_type type, unsigned n)
3909
28.6k
{
3910
28.6k
  if (!bmap)
3911
0
    return NULL;
3912
28.6k
  return isl_basic_map_insert_dims(bmap, type,
3913
28.6k
          isl_basic_map_dim(bmap, type), n);
3914
28.6k
}
3915
3916
__isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset,
3917
    enum isl_dim_type type, unsigned n)
3918
26.4k
{
3919
26.4k
  if (!bset)
3920
0
    return NULL;
3921
26.4k
  isl_assert(bset->ctx, type != isl_dim_in, goto error);
3922
26.4k
  return isl_basic_map_add_dims(bset, type, n);
3923
0
error:
3924
0
  isl_basic_set_free(bset);
3925
0
  return NULL;
3926
26.4k
}
3927
3928
static __isl_give isl_map *map_space_reset(__isl_take isl_map *map,
3929
  enum isl_dim_type type)
3930
40.0k
{
3931
40.0k
  isl_space *space;
3932
40.0k
3933
40.0k
  if (!map || !isl_space_is_named_or_nested(map->dim, type))
3934
9.09k
    return map;
3935
30.9k
3936
30.9k
  space = isl_map_get_space(map);
3937
30.9k
  space = isl_space_reset(space, type);
3938
30.9k
  map = isl_map_reset_space(map, space);
3939
30.9k
  return map;
3940
30.9k
}
3941
3942
__isl_give isl_map *isl_map_insert_dims(__isl_take isl_map *map,
3943
    enum isl_dim_type type, unsigned pos, unsigned n)
3944
34.3k
{
3945
34.3k
  int i;
3946
34.3k
3947
34.3k
  if (n == 0)
3948
2.89k
    return map_space_reset(map, type);
3949
31.4k
3950
31.4k
  map = isl_map_cow(map);
3951
31.4k
  if (!map)
3952
0
    return NULL;
3953
31.4k
3954
31.4k
  map->dim = isl_space_insert_dims(map->dim, type, pos, n);
3955
31.4k
  if (!map->dim)
3956
0
    goto error;
3957
31.4k
3958
64.1k
  
for (i = 0; 31.4k
i < map->n;
++i32.7k
) {
3959
32.7k
    map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n);
3960
32.7k
    if (!map->p[i])
3961
0
      goto error;
3962
32.7k
  }
3963
31.4k
3964
31.4k
  return map;
3965
0
error:
3966
0
  isl_map_free(map);
3967
0
  return NULL;
3968
31.4k
}
3969
3970
__isl_give isl_set *isl_set_insert_dims(__isl_take isl_set *set,
3971
    enum isl_dim_type type, unsigned pos, unsigned n)
3972
6.75k
{
3973
6.75k
  return isl_map_insert_dims(set, type, pos, n);
3974
6.75k
}
3975
3976
__isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map,
3977
    enum isl_dim_type type, unsigned n)
3978
27.5k
{
3979
27.5k
  if (!map)
3980
0
    return NULL;
3981
27.5k
  return isl_map_insert_dims(map, type, isl_map_dim(map, type), n);
3982
27.5k
}
3983
3984
__isl_give isl_set *isl_set_add_dims(__isl_take isl_set *set,
3985
    enum isl_dim_type type, unsigned n)
3986
22.2k
{
3987
22.2k
  if (!set)
3988
0
    return NULL;
3989
22.2k
  isl_assert(set->ctx, type != isl_dim_in, goto error);
3990
22.2k
  return set_from_map(isl_map_add_dims(set_to_map(set), type, n));
3991
0
error:
3992
0
  isl_set_free(set);
3993
0
  return NULL;
3994
22.2k
}
3995
3996
__isl_give isl_basic_map *isl_basic_map_move_dims(
3997
  __isl_take isl_basic_map *bmap,
3998
  enum isl_dim_type dst_type, unsigned dst_pos,
3999
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4000
1.01k
{
4001
1.01k
  struct isl_dim_map *dim_map;
4002
1.01k
  struct isl_basic_map *res;
4003
1.01k
  enum isl_dim_type t;
4004
1.01k
  unsigned total, off;
4005
1.01k
4006
1.01k
  if (!bmap)
4007
0
    return NULL;
4008
1.01k
  if (n == 0) {
4009
631
    bmap = isl_basic_map_reset(bmap, src_type);
4010
631
    bmap = isl_basic_map_reset(bmap, dst_type);
4011
631
    return bmap;
4012
631
  }
4013
385
4014
385
  if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0)
4015
0
    return isl_basic_map_free(bmap);
4016
385
4017
385
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4018
0
    return bmap;
4019
385
4020
385
  isl_assert(bmap->ctx, dst_type != src_type, goto error);
4021
385
4022
385
  if (pos(bmap->dim, dst_type) + dst_pos ==
4023
385
      pos(bmap->dim, src_type) + src_pos +
4024
385
              ((src_type < dst_type) ? 
n111
:
0274
)) {
4025
271
    bmap = isl_basic_map_cow(bmap);
4026
271
    if (!bmap)
4027
0
      return NULL;
4028
271
4029
271
    bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4030
271
            src_type, src_pos, n);
4031
271
    if (!bmap->dim)
4032
0
      goto error;
4033
271
4034
271
    bmap = isl_basic_map_finalize(bmap);
4035
271
4036
271
    return bmap;
4037
271
  }
4038
114
4039
114
  total = isl_basic_map_total_dim(bmap);
4040
114
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4041
114
4042
114
  off = 0;
4043
456
  for (t = isl_dim_param; t <= isl_dim_out; 
++t342
) {
4044
342
    unsigned size = isl_space_dim(bmap->dim, t);
4045
342
    if (t == dst_type) {
4046
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4047
114
              0, dst_pos, off);
4048
114
      off += dst_pos;
4049
114
      isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
4050
114
              src_pos, n, off);
4051
114
      off += n;
4052
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4053
114
              dst_pos, size - dst_pos, off);
4054
114
      off += size - dst_pos;
4055
228
    } else if (t == src_type) {
4056
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4057
114
              0, src_pos, off);
4058
114
      off += src_pos;
4059
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4060
114
          src_pos + n, size - src_pos - n, off);
4061
114
      off += size - src_pos - n;
4062
114
    } else {
4063
114
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4064
114
      off += size;
4065
114
    }
4066
342
  }
4067
114
  isl_dim_map_div(dim_map, bmap, off);
4068
114
4069
114
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4070
114
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4071
114
  bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4072
114
  if (!bmap)
4073
0
    goto error;
4074
114
4075
114
  bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4076
114
          src_type, src_pos, n);
4077
114
  if (!bmap->dim)
4078
0
    goto error;
4079
114
4080
114
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
4081
114
  bmap = isl_basic_map_gauss(bmap, NULL);
4082
114
  bmap = isl_basic_map_finalize(bmap);
4083
114
4084
114
  return bmap;
4085
0
error:
4086
0
  isl_basic_map_free(bmap);
4087
0
  return NULL;
4088
114
}
4089
4090
__isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
4091
  enum isl_dim_type dst_type, unsigned dst_pos,
4092
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4093
8
{
4094
8
  isl_basic_map *bmap = bset_to_bmap(bset);
4095
8
  bmap = isl_basic_map_move_dims(bmap, dst_type, dst_pos,
4096
8
          src_type, src_pos, n);
4097
8
  return bset_from_bmap(bmap);
4098
8
}
4099
4100
__isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
4101
  enum isl_dim_type dst_type, unsigned dst_pos,
4102
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4103
1
{
4104
1
  if (!set)
4105
0
    return NULL;
4106
1
  isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
4107
1
  return set_from_map(isl_map_move_dims(set_to_map(set),
4108
1
            dst_type, dst_pos, src_type, src_pos, n));
4109
0
error:
4110
0
  isl_set_free(set);
4111
0
  return NULL;
4112
1
}
4113
4114
__isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
4115
  enum isl_dim_type dst_type, unsigned dst_pos,
4116
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4117
157
{
4118
157
  int i;
4119
157
4120
157
  if (!map)
4121
0
    return NULL;
4122
157
  if (n == 0) {
4123
0
    map = isl_map_reset(map, src_type);
4124
0
    map = isl_map_reset(map, dst_type);
4125
0
    return map;
4126
0
  }
4127
157
4128
157
  isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
4129
157
    goto error);
4130
157
4131
157
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4132
0
    return map;
4133
157
4134
157
  isl_assert(map->ctx, dst_type != src_type, goto error);
4135
157
4136
157
  map = isl_map_cow(map);
4137
157
  if (!map)
4138
0
    return NULL;
4139
157
4140
157
  map->dim = isl_space_move_dims(map->dim, dst_type, dst_pos, src_type, src_pos, n);
4141
157
  if (!map->dim)
4142
0
    goto error;
4143
157
4144
325
  
for (i = 0; 157
i < map->n;
++i168
) {
4145
168
    map->p[i] = isl_basic_map_move_dims(map->p[i],
4146
168
            dst_type, dst_pos,
4147
168
            src_type, src_pos, n);
4148
168
    if (!map->p[i])
4149
0
      goto error;
4150
168
  }
4151
157
4152
157
  return map;
4153
0
error:
4154
0
  isl_map_free(map);
4155
0
  return NULL;
4156
157
}
4157
4158
/* Move the specified dimensions to the last columns right before
4159
 * the divs.  Don't change the dimension specification of bmap.
4160
 * That's the responsibility of the caller.
4161
 */
4162
static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
4163
  enum isl_dim_type type, unsigned first, unsigned n)
4164
119k
{
4165
119k
  struct isl_dim_map *dim_map;
4166
119k
  struct isl_basic_map *res;
4167
119k
  enum isl_dim_type t;
4168
119k
  unsigned total, off;
4169
119k
4170
119k
  if (!bmap)
4171
0
    return NULL;
4172
119k
  if (pos(bmap->dim, type) + first + n ==
4173
119k
        1 + isl_space_dim(bmap->dim, isl_dim_all))
4174
97.6k
    return bmap;
4175
21.6k
4176
21.6k
  total = isl_basic_map_total_dim(bmap);
4177
21.6k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4178
21.6k
4179
21.6k
  off = 0;
4180
86.7k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t65.0k
) {
4181
65.0k
    unsigned size = isl_space_dim(bmap->dim, t);
4182
65.0k
    if (t == type) {
4183
21.6k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4184
21.6k
              0, first, off);
4185
21.6k
      off += first;
4186
21.6k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4187
21.6k
              first, n, total - bmap->n_div - n);
4188
21.6k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4189
21.6k
              first + n, size - (first + n), off);
4190
21.6k
      off += size - (first + n);
4191
43.3k
    } else {
4192
43.3k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4193
43.3k
      off += size;
4194
43.3k
    }
4195
65.0k
  }
4196
21.6k
  isl_dim_map_div(dim_map, bmap, off + n);
4197
21.6k
4198
21.6k
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4199
21.6k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4200
21.6k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4201
21.6k
  return res;
4202
21.6k
}
4203
4204
/* Insert "n" rows in the divs of "bmap".
4205
 *
4206
 * The number of columns is not changed, which means that the last
4207
 * dimensions of "bmap" are being reintepreted as the new divs.
4208
 * The space of "bmap" is not adjusted, however, which means
4209
 * that "bmap" is left in an inconsistent state.  Removing "n" dimensions
4210
 * from the space of "bmap" is the responsibility of the caller.
4211
 */
4212
static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap,
4213
  int n)
4214
119k
{
4215
119k
  int i;
4216
119k
  size_t row_size;
4217
119k
  isl_int **new_div;
4218
119k
  isl_int *old;
4219
119k
4220
119k
  bmap = isl_basic_map_cow(bmap);
4221
119k
  if (!bmap)
4222
0
    return NULL;
4223
119k
4224
119k
  row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + bmap->extra;
4225
119k
  old = bmap->block2.data;
4226
119k
  bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
4227
119k
          (bmap->extra + n) * (1 + row_size));
4228
119k
  if (!bmap->block2.data)
4229
0
    return isl_basic_map_free(bmap);
4230
119k
  new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
4231
119k
  if (!new_div)
4232
0
    return isl_basic_map_free(bmap);
4233
335k
  
for (i = 0; 119k
i < n;
++i215k
) {
4234
215k
    new_div[i] = bmap->block2.data +
4235
215k
        (bmap->extra + i) * (1 + row_size);
4236
215k
    isl_seq_clr(new_div[i], 1 + row_size);
4237
215k
  }
4238
126k
  for (i = 0; i < bmap->extra; 
++i6.85k
)
4239
6.85k
    new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
4240
119k
  free(bmap->div);
4241
119k
  bmap->div = new_div;
4242
119k
  bmap->n_div += n;
4243
119k
  bmap->extra += n;
4244
119k
4245
119k
  return bmap;
4246
119k
}
4247
4248
/* Drop constraints from "bmap" that only involve the variables
4249
 * of "type" in the range [first, first + n] that are not related
4250
 * to any of the variables outside that interval.
4251
 * These constraints cannot influence the values for the variables
4252
 * outside the interval, except in case they cause "bmap" to be empty.
4253
 * Only drop the constraints if "bmap" is known to be non-empty.
4254
 */
4255
static __isl_give isl_basic_map *drop_irrelevant_constraints(
4256
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
4257
  unsigned first, unsigned n)
4258
119k
{
4259
119k
  int i;
4260
119k
  int *groups;
4261
119k
  unsigned dim, n_div;
4262
119k
  isl_bool non_empty;
4263
119k
4264
119k
  non_empty = isl_basic_map_plain_is_non_empty(bmap);
4265
119k
  if (non_empty < 0)
4266
0
    return isl_basic_map_free(bmap);
4267
119k
  if (!non_empty)
4268
65.6k
    return bmap;
4269
53.7k
4270
53.7k
  dim = isl_basic_map_dim(bmap, isl_dim_all);
4271
53.7k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
4272
53.7k
  groups = isl_calloc_array(isl_basic_map_get_ctx(bmap), int, dim);
4273
53.7k
  if (!groups)
4274
0
    return isl_basic_map_free(bmap);
4275
53.7k
  first += isl_basic_map_offset(bmap, type) - 1;
4276
252k
  for (i = 0; i < first; 
++i198k
)
4277
198k
    groups[i] = -1;
4278
75.1k
  for (i = first + n; i < dim - n_div; 
++i21.3k
)
4279
21.3k
    groups[i] = -1;
4280
53.7k
4281
53.7k
  bmap = isl_basic_map_drop_unrelated_constraints(bmap, groups);
4282
53.7k
4283
53.7k
  return bmap;
4284
53.7k
}
4285
4286
/* Turn the n dimensions of type type, starting at first
4287
 * into existentially quantified variables.
4288
 *
4289
 * If a subset of the projected out variables are unrelated
4290
 * to any of the variables that remain, then the constraints
4291
 * involving this subset are simply dropped first.
4292
 */
4293
__isl_give isl_basic_map *isl_basic_map_project_out(
4294
    __isl_take isl_basic_map *bmap,
4295
    enum isl_dim_type type, unsigned first, unsigned n)
4296
146k
{
4297
146k
  isl_bool empty;
4298
146k
4299
146k
  if (n == 0)
4300
27.3k
    return basic_map_space_reset(bmap, type);
4301
119k
  if (type == isl_dim_div)
4302
119k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4303
119k
      "cannot project out existentially quantified variables",
4304
119k
      return isl_basic_map_free(bmap));
4305
119k
4306
119k
  empty = isl_basic_map_plain_is_empty(bmap);
4307
119k
  if (empty < 0)
4308
0
    return isl_basic_map_free(bmap);
4309
119k
  if (empty)
4310
1.58k
    bmap = isl_basic_map_set_to_empty(bmap);
4311
119k
4312
119k
  bmap = drop_irrelevant_constraints(bmap, type, first, n);
4313
119k
  if (!bmap)
4314
0
    return NULL;
4315
119k
4316
119k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
4317
119k
    
return isl_basic_map_remove_dims(bmap, type, first, n)39
;
4318
119k
4319
119k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
4320
0
    return isl_basic_map_free(bmap);
4321
119k
4322
119k
  bmap = move_last(bmap, type, first, n);
4323
119k
  bmap = isl_basic_map_cow(bmap);
4324
119k
  bmap = insert_div_rows(bmap, n);
4325
119k
  if (!bmap)
4326
0
    return NULL;
4327
119k
4328
119k
  bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
4329
119k
  if (!bmap->dim)
4330
0
    goto error;
4331
119k
  bmap = isl_basic_map_simplify(bmap);
4332
119k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4333
119k
  return isl_basic_map_finalize(bmap);
4334
0
error:
4335
0
  isl_basic_map_free(bmap);
4336
0
  return NULL;
4337
119k
}
4338
4339
/* Turn the n dimensions of type type, starting at first
4340
 * into existentially quantified variables.
4341
 */
4342
struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
4343
    enum isl_dim_type type, unsigned first, unsigned n)
4344
19.3k
{
4345
19.3k
  return bset_from_bmap(isl_basic_map_project_out(bset_to_bmap(bset),
4346
19.3k
              type, first, n));
4347
19.3k
}
4348
4349
/* Turn the n dimensions of type type, starting at first
4350
 * into existentially quantified variables.
4351
 */
4352
__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
4353
    enum isl_dim_type type, unsigned first, unsigned n)
4354
102k
{
4355
102k
  int i;
4356
102k
4357
102k
  if (!map)
4358
0
    return NULL;
4359
102k
4360
102k
  if (n == 0)
4361
37.1k
    return map_space_reset(map, type);
4362
65.5k
4363
65.5k
  isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
4364
65.5k
4365
65.5k
  map = isl_map_cow(map);
4366
65.5k
  if (!map)
4367
0
    return NULL;
4368
65.5k
4369
65.5k
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
4370
65.5k
  if (!map->dim)
4371
0
    goto error;
4372
65.5k
4373
108k
  
for (i = 0; 65.5k
i < map->n;
++i43.1k
) {
4374
43.1k
    map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
4375
43.1k
    if (!map->p[i])
4376
0
      goto error;
4377
43.1k
  }
4378
65.5k
4379
65.5k
  return map;
4380
0
error:
4381
0
  isl_map_free(map);
4382
0
  return NULL;
4383
65.5k
}
4384
4385
/* Turn the n dimensions of type type, starting at first
4386
 * into existentially quantified variables.
4387
 */
4388
__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
4389
    enum isl_dim_type type, unsigned first, unsigned n)
4390
22.9k
{
4391
22.9k
  return set_from_map(isl_map_project_out(set_to_map(set),
4392
22.9k
            type, first, n));
4393
22.9k
}
4394
4395
/* Return a map that projects the elements in "set" onto their
4396
 * "n" set dimensions starting at "first".
4397
 * "type" should be equal to isl_dim_set.
4398
 */
4399
__isl_give isl_map *isl_set_project_onto_map(__isl_take isl_set *set,
4400
  enum isl_dim_type type, unsigned first, unsigned n)
4401
371
{
4402
371
  int i;
4403
371
  int dim;
4404
371
  isl_map *map;
4405
371
4406
371
  if (!set)
4407
0
    return NULL;
4408
371
  if (type != isl_dim_set)
4409
371
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4410
371
      "only set dimensions can be projected out", goto error);
4411
371
  dim = isl_set_dim(set, isl_dim_set);
4412
371
  if (first + n > dim || first + n < first)
4413
371
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4414
371
      "index out of bounds", goto error);
4415
371
4416
371
  map = isl_map_from_domain(set);
4417
371
  map = isl_map_add_dims(map, isl_dim_out, n);
4418
742
  for (i = 0; i < n; 
++i371
)
4419
371
    map = isl_map_equate(map, isl_dim_in, first + i,
4420
371
          isl_dim_out, i);
4421
371
  return map;
4422
0
error:
4423
0
  isl_set_free(set);
4424
0
  return NULL;
4425
371
}
4426
4427
static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
4428
93.8k
{
4429
93.8k
  int i, j;
4430
93.8k
4431
241k
  for (i = 0; i < n; 
++i147k
) {
4432
147k
    j = isl_basic_map_alloc_div(bmap);
4433
147k
    if (j < 0)
4434
0
      goto error;
4435
147k
    isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
4436
147k
  }
4437
93.8k
  return bmap;
4438
0
error:
4439
0
  isl_basic_map_free(bmap);
4440
0
  return NULL;
4441
93.8k
}
4442
4443
struct isl_basic_map *isl_basic_map_apply_range(
4444
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4445
90.7k
{
4446
90.7k
  isl_space *dim_result = NULL;
4447
90.7k
  struct isl_basic_map *bmap;
4448
90.7k
  unsigned n_in, n_out, n, nparam, total, pos;
4449
90.7k
  struct isl_dim_map *dim_map1, *dim_map2;
4450
90.7k
4451
90.7k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4452
0
    goto error;
4453
90.7k
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_out,
4454
90.7k
            bmap2->dim, isl_dim_in))
4455
90.7k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4456
90.7k
      "spaces don't match", goto error);
4457
90.7k
4458
90.7k
  dim_result = isl_space_join(isl_space_copy(bmap1->dim),
4459
90.7k
          isl_space_copy(bmap2->dim));
4460
90.7k
4461
90.7k
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4462
90.7k
  n_out = isl_basic_map_dim(bmap2, isl_dim_out);
4463
90.7k
  n = isl_basic_map_dim(bmap1, isl_dim_out);
4464
90.7k
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4465
90.7k
4466
90.7k
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
4467
90.7k
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4468
90.7k
  dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
4469
90.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4470
90.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
4471
90.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4472
90.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
4473
90.7k
  isl_dim_map_div(dim_map1, bmap1, pos += n_out);
4474
90.7k
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4475
90.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4476
90.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4477
90.7k
4478
90.7k
  bmap = isl_basic_map_alloc_space(dim_result,
4479
90.7k
      bmap1->n_div + bmap2->n_div + n,
4480
90.7k
      bmap1->n_eq + bmap2->n_eq,
4481
90.7k
      bmap1->n_ineq + bmap2->n_ineq);
4482
90.7k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4483
90.7k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4484
90.7k
  bmap = add_divs(bmap, n);
4485
90.7k
  bmap = isl_basic_map_simplify(bmap);
4486
90.7k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4487
90.7k
  return isl_basic_map_finalize(bmap);
4488
0
error:
4489
0
  isl_basic_map_free(bmap1);
4490
0
  isl_basic_map_free(bmap2);
4491
0
  return NULL;
4492
90.7k
}
4493
4494
struct isl_basic_set *isl_basic_set_apply(
4495
    struct isl_basic_set *bset, struct isl_basic_map *bmap)
4496
4.41k
{
4497
4.41k
  if (!bset || !bmap)
4498
0
    goto error;
4499
4.41k
4500
4.41k
  isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
4501
4.41k
        goto error);
4502
4.41k
4503
4.41k
  return bset_from_bmap(isl_basic_map_apply_range(bset_to_bmap(bset),
4504
4.41k
              bmap));
4505
0
error:
4506
0
  isl_basic_set_free(bset);
4507
0
  isl_basic_map_free(bmap);
4508
0
  return NULL;
4509
4.41k
}
4510
4511
struct isl_basic_map *isl_basic_map_apply_domain(
4512
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4513
0
{
4514
0
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4515
0
    goto error;
4516
0
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_in,
4517
0
          bmap2->dim, isl_dim_in))
4518
0
    isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4519
0
      "spaces don't match", goto error);
4520
0
4521
0
  bmap1 = isl_basic_map_reverse(bmap1);
4522
0
  bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
4523
0
  return isl_basic_map_reverse(bmap1);
4524
0
error:
4525
0
  isl_basic_map_free(bmap1);
4526
0
  isl_basic_map_free(bmap2);
4527
0
  return NULL;
4528
0
}
4529
4530
/* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
4531
 * A \cap B -> f(A) + f(B)
4532
 */
4533
__isl_give isl_basic_map *isl_basic_map_sum(__isl_take isl_basic_map *bmap1,
4534
  __isl_take isl_basic_map *bmap2)
4535
24
{
4536
24
  unsigned n_in, n_out, nparam, total, pos;
4537
24
  struct isl_basic_map *bmap = NULL;
4538
24
  struct isl_dim_map *dim_map1, *dim_map2;
4539
24
  int i;
4540
24
4541
24
  if (!bmap1 || !bmap2)
4542
0
    goto error;
4543
24
4544
24
  isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim),
4545
24
    goto error);
4546
24
4547
24
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4548
24
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4549
24
  n_out = isl_basic_map_dim(bmap1, isl_dim_out);
4550
24
4551
24
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
4552
24
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4553
24
  dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
4554
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4555
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
4556
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4557
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4558
24
  isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
4559
24
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4560
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4561
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
4562
24
4563
24
  bmap = isl_basic_map_alloc_space(isl_space_copy(bmap1->dim),
4564
24
      bmap1->n_div + bmap2->n_div + 2 * n_out,
4565
24
      bmap1->n_eq + bmap2->n_eq + n_out,
4566
24
      bmap1->n_ineq + bmap2->n_ineq);
4567
48
  for (i = 0; i < n_out; 
++i24
) {
4568
24
    int j = isl_basic_map_alloc_equality(bmap);
4569
24
    if (j < 0)
4570
0
      goto error;
4571
24
    isl_seq_clr(bmap->eq[j], 1+total);
4572
24
    isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
4573
24
    isl_int_set_si(bmap->eq[j][1+pos+i], 1);
4574
24
    isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
4575
24
  }
4576
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4577
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4578
24
  bmap = add_divs(bmap, 2 * n_out);
4579
24
4580
24
  bmap = isl_basic_map_simplify(bmap);
4581
24
  return isl_basic_map_finalize(bmap);
4582
0
error:
4583
0
  isl_basic_map_free(bmap);
4584
0
  isl_basic_map_free(bmap1);
4585
0
  isl_basic_map_free(bmap2);
4586
0
  return NULL;
4587
24
}
4588
4589
/* Given two maps A -> f(A) and B -> g(B), construct a map
4590
 * A \cap B -> f(A) + f(B)
4591
 */
4592
__isl_give isl_map *isl_map_sum(__isl_take isl_map *map1,
4593
  __isl_take isl_map *map2)
4594
24
{
4595
24
  struct isl_map *result;
4596
24
  int i, j;
4597
24
4598
24
  if (!map1 || !map2)
4599
0
    goto error;
4600
24
4601
24
  isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
4602
24
4603
24
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
4604
24
        map1->n * map2->n, 0);
4605
24
  if (!result)
4606
0
    goto error;
4607
48
  
for (i = 0; 24
i < map1->n;
++i24
)
4608
48
    
for (j = 0; 24
j < map2->n;
++j24
) {
4609
24
      struct isl_basic_map *part;
4610
24
      part = isl_basic_map_sum(
4611
24
            isl_basic_map_copy(map1->p[i]),
4612
24
            isl_basic_map_copy(map2->p[j]));
4613
24
      if (isl_basic_map_is_empty(part))
4614
0
        isl_basic_map_free(part);
4615
24
      else
4616
24
        result = isl_map_add_basic_map(result, part);
4617
24
      if (!result)
4618
0
        goto error;
4619
24
    }
4620
24
  isl_map_free(map1);
4621
24
  isl_map_free(map2);
4622
24
  return result;
4623
0
error:
4624
0
  isl_map_free(map1);
4625
0
  isl_map_free(map2);
4626
0
  return NULL;
4627
24
}
4628
4629
__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
4630
  __isl_take isl_set *set2)
4631
0
{
4632
0
  return set_from_map(isl_map_sum(set_to_map(set1), set_to_map(set2)));
4633
0
}
4634
4635
/* Given a basic map A -> f(A), construct A -> -f(A).
4636
 */
4637
__isl_give isl_basic_map *isl_basic_map_neg(__isl_take isl_basic_map *bmap)
4638
1
{
4639
1
  int i, j;
4640
1
  unsigned off, n;
4641
1
4642
1
  bmap = isl_basic_map_cow(bmap);
4643
1
  if (!bmap)
4644
0
    return NULL;
4645
1
4646
1
  n = isl_basic_map_dim(bmap, isl_dim_out);
4647
1
  off = isl_basic_map_offset(bmap, isl_dim_out);
4648
2
  for (i = 0; i < bmap->n_eq; 
++i1
)
4649
2
    
for (j = 0; 1
j < n;
++j1
)
4650
1
      isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
4651
3
  for (i = 0; i < bmap->n_ineq; 
++i2
)
4652
4
    
for (j = 0; 2
j < n;
++j2
)
4653
2
      isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
4654
1
  for (i = 0; i < bmap->n_div; 
++i0
)
4655
0
    for (j = 0; j < n; ++j)
4656
0
      isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
4657
1
  bmap = isl_basic_map_gauss(bmap, NULL);
4658
1
  return isl_basic_map_finalize(bmap);
4659
1
}
4660
4661
__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset)
4662
0
{
4663
0
  return isl_basic_map_neg(bset);
4664
0
}
4665
4666
/* Given a map A -> f(A), construct A -> -f(A).
4667
 */
4668
__isl_give isl_map *isl_map_neg(__isl_take isl_map *map)
4669
1
{
4670
1
  int i;
4671
1
4672
1
  map = isl_map_cow(map);
4673
1
  if (!map)
4674
0
    return NULL;
4675
1
4676
2
  
for (i = 0; 1
i < map->n;
++i1
) {
4677
1
    map->p[i] = isl_basic_map_neg(map->p[i]);
4678
1
    if (!map->p[i])
4679
0
      goto error;
4680
1
  }
4681
1
4682
1
  return map;
4683
0
error:
4684
0
  isl_map_free(map);
4685
0
  return NULL;
4686
1
}
4687
4688
__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
4689
0
{
4690
0
  return set_from_map(isl_map_neg(set_to_map(set)));
4691
0
}
4692
4693
/* Given a basic map A -> f(A) and an integer d, construct a basic map
4694
 * A -> floor(f(A)/d).
4695
 */
4696
__isl_give isl_basic_map *isl_basic_map_floordiv(__isl_take isl_basic_map *bmap,
4697
    isl_int d)
4698
2.99k
{
4699
2.99k
  unsigned n_in, n_out, nparam, total, pos;
4700
2.99k
  struct isl_basic_map *result = NULL;
4701
2.99k
  struct isl_dim_map *dim_map;
4702
2.99k
  int i;
4703
2.99k
4704
2.99k
  if (!bmap)
4705
0
    return NULL;
4706
2.99k
4707
2.99k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4708
2.99k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4709
2.99k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4710
2.99k
4711
2.99k
  total = nparam + n_in + n_out + bmap->n_div + n_out;
4712
2.99k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4713
2.99k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
4714
2.99k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
4715
2.99k
  isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
4716
2.99k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
4717
2.99k
4718
2.99k
  result = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
4719
2.99k
      bmap->n_div + n_out,
4720
2.99k
      bmap->n_eq, bmap->n_ineq + 2 * n_out);
4721
2.99k
  result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map);
4722
2.99k
  result = add_divs(result, n_out);
4723
6.01k
  for (i = 0; i < n_out; 
++i3.01k
) {
4724
3.01k
    int j;
4725
3.01k
    j = isl_basic_map_alloc_inequality(result);
4726
3.01k
    if (j < 0)
4727
0
      goto error;
4728
3.01k
    isl_seq_clr(result->ineq[j], 1+total);
4729
3.01k
    isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
4730
3.01k
    isl_int_set_si(result->ineq[j][1+pos+i], 1);
4731
3.01k
    j = isl_basic_map_alloc_inequality(result);
4732
3.01k
    if (j < 0)
4733
0
      goto error;
4734
3.01k
    isl_seq_clr(result->ineq[j], 1+total);
4735
3.01k
    isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
4736
3.01k
    isl_int_set_si(result->ineq[j][1+pos+i], -1);
4737
3.01k
    isl_int_sub_ui(result->ineq[j][0], d, 1);
4738
3.01k
  }
4739
2.99k
4740
2.99k
  result = isl_basic_map_simplify(result);
4741
2.99k
  return isl_basic_map_finalize(result);
4742
0
error:
4743
0
  isl_basic_map_free(result);
4744
0
  return NULL;
4745
2.99k
}
4746
4747
/* Given a map A -> f(A) and an integer d, construct a map
4748
 * A -> floor(f(A)/d).
4749
 */
4750
__isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
4751
2.95k
{
4752
2.95k
  int i;
4753
2.95k
4754
2.95k
  map = isl_map_cow(map);
4755
2.95k
  if (!map)
4756
0
    return NULL;
4757
2.95k
4758
2.95k
  ISL_F_CLR(map, ISL_MAP_DISJOINT);
4759
2.95k
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4760
5.94k
  for (i = 0; i < map->n; 
++i2.99k
) {
4761
2.99k
    map->p[i] = isl_basic_map_floordiv(map->p[i], d);
4762
2.99k
    if (!map->p[i])
4763
0
      goto error;
4764
2.99k
  }
4765
2.95k
4766
2.95k
  return map;
4767
0
error:
4768
0
  isl_map_free(map);
4769
0
  return NULL;
4770
2.95k
}
4771
4772
/* Given a map A -> f(A) and an integer d, construct a map
4773
 * A -> floor(f(A)/d).
4774
 */
4775
__isl_give isl_map *isl_map_floordiv_val(__isl_take isl_map *map,
4776
  __isl_take isl_val *d)
4777
2.95k
{
4778
2.95k
  if (!map || !d)
4779
0
    goto error;
4780
2.95k
  if (!isl_val_is_int(d))
4781
2.95k
    
isl_die0
(isl_val_get_ctx(d), isl_error_invalid,
4782
2.95k
      "expecting integer denominator", goto error);
4783
2.95k
  map = isl_map_floordiv(map, d->n);
4784
2.95k
  isl_val_free(d);
4785
2.95k
  return map;
4786
0
error:
4787
0
  isl_map_free(map);
4788
0
  isl_val_free(d);
4789
0
  return NULL;
4790
2.95k
}
4791
4792
static __isl_give isl_basic_map *var_equal(__isl_take isl_basic_map *bmap,
4793
  unsigned pos)
4794
12.7k
{
4795
12.7k
  int i;
4796
12.7k
  unsigned nparam;
4797
12.7k
  unsigned n_in;
4798
12.7k
4799
12.7k
  i = isl_basic_map_alloc_equality(bmap);
4800
12.7k
  if (i < 0)
4801
0
    goto error;
4802
12.7k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4803
12.7k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4804
12.7k
  isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
4805
12.7k
  isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
4806
12.7k
  isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
4807
12.7k
  return isl_basic_map_finalize(bmap);
4808
0
error:
4809
0
  isl_basic_map_free(bmap);
4810
0
  return NULL;
4811
12.7k
}
4812
4813
/* Add a constraint to "bmap" expressing i_pos < o_pos
4814
 */
4815
static __isl_give isl_basic_map *var_less(__isl_take isl_basic_map *bmap,
4816
  unsigned pos)
4817
1.45k
{
4818
1.45k
  int i;
4819
1.45k
  unsigned nparam;
4820
1.45k
  unsigned n_in;
4821
1.45k
4822
1.45k
  i = isl_basic_map_alloc_inequality(bmap);
4823
1.45k
  if (i < 0)
4824
0
    goto error;
4825
1.45k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4826
1.45k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4827
1.45k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4828
1.45k
  isl_int_set_si(bmap->ineq[i][0], -1);
4829
1.45k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4830
1.45k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4831
1.45k
  return isl_basic_map_finalize(bmap);
4832
0
error:
4833
0
  isl_basic_map_free(bmap);
4834
0
  return NULL;
4835
1.45k
}
4836
4837
/* Add a constraint to "bmap" expressing i_pos <= o_pos
4838
 */
4839
static __isl_give isl_basic_map *var_less_or_equal(
4840
  __isl_take isl_basic_map *bmap, unsigned pos)
4841
2.04k
{
4842
2.04k
  int i;
4843
2.04k
  unsigned nparam;
4844
2.04k
  unsigned n_in;
4845
2.04k
4846
2.04k
  i = isl_basic_map_alloc_inequality(bmap);
4847
2.04k
  if (i < 0)
4848
0
    goto error;
4849
2.04k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4850
2.04k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4851
2.04k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4852
2.04k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4853
2.04k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4854
2.04k
  return isl_basic_map_finalize(bmap);
4855
0
error:
4856
0
  isl_basic_map_free(bmap);
4857
0
  return NULL;
4858
2.04k
}
4859
4860
/* Add a constraint to "bmap" expressing i_pos > o_pos
4861
 */
4862
static __isl_give isl_basic_map *var_more(__isl_take isl_basic_map *bmap,
4863
  unsigned pos)
4864
16.0k
{
4865
16.0k
  int i;
4866
16.0k
  unsigned nparam;
4867
16.0k
  unsigned n_in;
4868
16.0k
4869
16.0k
  i = isl_basic_map_alloc_inequality(bmap);
4870
16.0k
  if (i < 0)
4871
0
    goto error;
4872
16.0k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4873
16.0k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4874
16.0k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4875
16.0k
  isl_int_set_si(bmap->ineq[i][0], -1);
4876
16.0k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4877
16.0k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4878
16.0k
  return isl_basic_map_finalize(bmap);
4879
0
error:
4880
0
  isl_basic_map_free(bmap);
4881
0
  return NULL;
4882
16.0k
}
4883
4884
/* Add a constraint to "bmap" expressing i_pos >= o_pos
4885
 */
4886
static __isl_give isl_basic_map *var_more_or_equal(
4887
  __isl_take isl_basic_map *bmap, unsigned pos)
4888
1.45k
{
4889
1.45k
  int i;
4890
1.45k
  unsigned nparam;
4891
1.45k
  unsigned n_in;
4892
1.45k
4893
1.45k
  i = isl_basic_map_alloc_inequality(bmap);
4894
1.45k
  if (i < 0)
4895
0
    goto error;
4896
1.45k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4897
1.45k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4898
1.45k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4899
1.45k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4900
1.45k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4901
1.45k
  return isl_basic_map_finalize(bmap);
4902
0
error:
4903
0
  isl_basic_map_free(bmap);
4904
0
  return NULL;
4905
1.45k
}
4906
4907
__isl_give isl_basic_map *isl_basic_map_equal(
4908
  __isl_take isl_space *dim, unsigned n_equal)
4909
2.84k
{
4910
2.84k
  int i;
4911
2.84k
  struct isl_basic_map *bmap;
4912
2.84k
  bmap = isl_basic_map_alloc_space(dim, 0, n_equal, 0);
4913
2.84k
  if (!bmap)
4914
0
    return NULL;
4915
5.06k
  
for (i = 0; 2.84k
i < n_equal &&
bmap2.22k
;
++i2.22k
)
4916
2.22k
    bmap = var_equal(bmap, i);
4917
2.84k
  return isl_basic_map_finalize(bmap);
4918
2.84k
}
4919
4920
/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
4921
 */
4922
__isl_give isl_basic_map *isl_basic_map_less_at(__isl_take isl_space *dim,
4923
  unsigned pos)
4924
1.45k
{
4925
1.45k
  int i;
4926
1.45k
  struct isl_basic_map *bmap;
4927
1.45k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4928
1.45k
  if (!bmap)
4929
0
    return NULL;
4930
2.27k
  
for (i = 0; 1.45k
i < pos &&
bmap822
;
++i822
)
4931
822
    bmap = var_equal(bmap, i);
4932
1.45k
  if (bmap)
4933
1.45k
    bmap = var_less(bmap, pos);
4934
1.45k
  return isl_basic_map_finalize(bmap);
4935
1.45k
}
4936
4937
/* Return a relation on "dim" expressing i_[0..pos] <<= o_[0..pos]
4938
 */
4939
__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
4940
  __isl_take isl_space *dim, unsigned pos)
4941
2.04k
{
4942
2.04k
  int i;
4943
2.04k
  isl_basic_map *bmap;
4944
2.04k
4945
2.04k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4946
3.11k
  for (i = 0; i < pos; 
++i1.06k
)
4947
1.06k
    bmap = var_equal(bmap, i);
4948
2.04k
  bmap = var_less_or_equal(bmap, pos);
4949
2.04k
  return isl_basic_map_finalize(bmap);
4950
2.04k
}
4951
4952
/* Return a relation on "dim" expressing i_pos > o_pos
4953
 */
4954
__isl_give isl_basic_map *isl_basic_map_more_at(__isl_take isl_space *dim,
4955
  unsigned pos)
4956
16.0k
{
4957
16.0k
  int i;
4958
16.0k
  struct isl_basic_map *bmap;
4959
16.0k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4960
16.0k
  if (!bmap)
4961
0
    return NULL;
4962
22.7k
  
for (i = 0; 16.0k
i < pos &&
bmap6.64k
;
++i6.64k
)
4963
6.64k
    bmap = var_equal(bmap, i);
4964
16.0k
  if (bmap)
4965
16.0k
    bmap = var_more(bmap, pos);
4966
16.0k
  return isl_basic_map_finalize(bmap);
4967
16.0k
}
4968
4969
/* Return a relation on "dim" expressing i_[0..pos] >>= o_[0..pos]
4970
 */
4971
__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
4972
  __isl_take isl_space *dim, unsigned pos)
4973
1.45k
{
4974
1.45k
  int i;
4975
1.45k
  isl_basic_map *bmap;
4976
1.45k
4977
1.45k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4978
3.42k
  for (i = 0; i < pos; 
++i1.97k
)
4979
1.97k
    bmap = var_equal(bmap, i);
4980
1.45k
  bmap = var_more_or_equal(bmap, pos);
4981
1.45k
  return isl_basic_map_finalize(bmap);
4982
1.45k
}
4983
4984
static __isl_give isl_map *map_lex_lte_first(__isl_take isl_space *dims,
4985
  unsigned n, int equal)
4986
2.28k
{
4987
2.28k
  struct isl_map *map;
4988
2.28k
  int i;
4989
2.28k
4990
2.28k
  if (n == 0 && 
equal22
)
4991
11
    return isl_map_universe(dims);
4992
2.27k
4993
2.27k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
4994
2.27k
4995
3.51k
  for (i = 0; i + 1 < n; 
++i1.23k
)
4996
1.23k
    map = isl_map_add_basic_map(map,
4997
1.23k
          isl_basic_map_less_at(isl_space_copy(dims), i));
4998
2.27k
  if (n > 0) {
4999
2.26k
    if (equal)
5000
2.04k
      map = isl_map_add_basic_map(map,
5001
2.04k
            isl_basic_map_less_or_equal_at(dims, n - 1));
5002
218
    else
5003
218
      map = isl_map_add_basic_map(map,
5004
218
            isl_basic_map_less_at(dims, n - 1));
5005
2.26k
  } else
5006
11
    isl_space_free(dims);
5007
2.27k
5008
2.27k
  return map;
5009
2.27k
}
5010
5011
static __isl_give isl_map *map_lex_lte(__isl_take isl_space *dims, int equal)
5012
2.20k
{
5013
2.20k
  if (!dims)
5014
4
    return NULL;
5015
2.20k
  return map_lex_lte_first(dims, dims->n_out, equal);
5016
2.20k
}
5017
5018
__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *dim, unsigned n)
5019
73
{
5020
73
  return map_lex_lte_first(dim, n, 0);
5021
73
}
5022
5023
__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *dim, unsigned n)
5024
10
{
5025
10
  return map_lex_lte_first(dim, n, 1);
5026
10
}
5027
5028
__isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_dim)
5029
156
{
5030
156
  return map_lex_lte(isl_space_map_from_set(set_dim), 0);
5031
156
}
5032
5033
__isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_dim)
5034
2.05k
{
5035
2.05k
  return map_lex_lte(isl_space_map_from_set(set_dim), 1);
5036
2.05k
}
5037
5038
static __isl_give isl_map *map_lex_gte_first(__isl_take isl_space *dims,
5039
  unsigned n, int equal)
5040
1.71k
{
5041
1.71k
  struct isl_map *map;
5042
1.71k
  int i;
5043
1.71k
5044
1.71k
  if (n == 0 && 
equal0
)
5045
0
    return isl_map_universe(dims);
5046
1.71k
5047
1.71k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
5048
1.71k
5049
3.99k
  for (i = 0; i + 1 < n; 
++i2.28k
)
5050
2.28k
    map = isl_map_add_basic_map(map,
5051
2.28k
          isl_basic_map_more_at(isl_space_copy(dims), i));
5052
1.71k
  if (n > 0) {
5053
1.71k
    if (equal)
5054
1.45k
      map = isl_map_add_basic_map(map,
5055
1.45k
            isl_basic_map_more_or_equal_at(dims, n - 1));
5056
264
    else
5057
264
      map = isl_map_add_basic_map(map,
5058
264
            isl_basic_map_more_at(dims, n - 1));
5059
1.71k
  } else
5060
0
    isl_space_free(dims);
5061
1.71k
5062
1.71k
  return map;
5063
1.71k
}
5064
5065
static __isl_give isl_map *map_lex_gte(__isl_take isl_space *dims, int equal)
5066
1.71k
{
5067
1.71k
  if (!dims)
5068
2
    return NULL;
5069
1.71k
  return map_lex_gte_first(dims, dims->n_out, equal);
5070
1.71k
}
5071
5072
__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *dim, unsigned n)
5073
0
{
5074
0
  return map_lex_gte_first(dim, n, 0);
5075
0
}
5076
5077
__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *dim, unsigned n)
5078
0
{
5079
0
  return map_lex_gte_first(dim, n, 1);
5080
0
}
5081
5082
__isl_give isl_map *isl_map_lex_gt(__isl_take isl_space *set_dim)
5083
266
{
5084
266
  return map_lex_gte(isl_space_map_from_set(set_dim), 0);
5085
266
}
5086
5087
__isl_give isl_map *isl_map_lex_ge(__isl_take isl_space *set_dim)
5088
1.45k
{
5089
1.45k
  return map_lex_gte(isl_space_map_from_set(set_dim), 1);
5090
1.45k
}
5091
5092
__isl_give isl_map *isl_set_lex_le_set(__isl_take isl_set *set1,
5093
  __isl_take isl_set *set2)
5094
178
{
5095