Coverage Report

Created: 2017-11-21 16:49

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