Coverage Report

Created: 2018-06-24 14:39

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