Coverage Report

Created: 2018-10-23 09:19

/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
357k
{
55
357k
  switch (type) {
56
357k
  
case isl_dim_param: return dim->nparam8.51k
;
57
357k
  
case isl_dim_in: return dim->n_in70.4k
;
58
357k
  
case isl_dim_out: return dim->n_out278k
;
59
357k
  
case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out134
;
60
357k
  
default: return 00
;
61
357k
  }
62
357k
}
63
64
static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
65
123k
{
66
123k
  switch (type) {
67
123k
  
case isl_dim_param: return 1386
;
68
123k
  
case isl_dim_in: return 1 + dim->nparam13.8k
;
69
123k
  
case isl_dim_out: return 1 + dim->nparam + dim->n_in109k
;
70
123k
  
default: return 00
;
71
123k
  }
72
123k
}
73
74
unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
75
        enum isl_dim_type type)
76
43.9M
{
77
43.9M
  if (!bmap)
78
0
    return 0;
79
43.9M
  switch (type) {
80
43.9M
  
case isl_dim_cst: return 10
;
81
43.9M
  case isl_dim_param:
82
41.3M
  case isl_dim_in:
83
41.3M
  case isl_dim_out: return isl_space_dim(bmap->dim, type);
84
41.3M
  
case isl_dim_div: return bmap->n_div2.24M
;
85
41.3M
  
case isl_dim_all: return isl_basic_map_total_dim(bmap)302k
;
86
41.3M
  
default: return 00
;
87
43.9M
  }
88
43.9M
}
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.01M
{
94
4.01M
  return map ? 
map->dim4.01M
: NULL;
95
4.01M
}
96
97
unsigned isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
98
200k
{
99
200k
  return map ? n(map->dim, type) : 
00
;
100
200k
}
101
102
unsigned isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
103
156k
{
104
156k
  return set ? n(set->dim, type) : 
00
;
105
156k
}
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.19k
;
119
1.20M
  
case isl_dim_in: return 1 + space->nparam232k
;
120
1.20M
  
case isl_dim_out: return 1 + space->nparam + space->n_in737k
;
121
1.20M
  case isl_dim_div: return 1 + space->nparam + space->n_in +
122
232k
                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
300
{
130
300
  return isl_basic_map_offset(bset, type);
131
300
}
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.72M
{
141
2.72M
  return isl_basic_map_dim(bset, type);
142
2.72M
}
143
144
unsigned isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
145
1.44M
{
146
1.44M
  return isl_basic_set_dim(bset, isl_dim_set);
147
1.44M
}
148
149
unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
150
730k
{
151
730k
  return isl_basic_set_dim(bset, isl_dim_param);
152
730k
}
153
154
unsigned isl_basic_set_total_dim(__isl_keep const isl_basic_set *bset)
155
2.99M
{
156
2.99M
  if (!bset)
157
0
    return 0;
158
2.99M
  return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
159
2.99M
}
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
565
{
168
565
  return isl_set_dim(set, isl_dim_param);
169
565
}
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
53.5M
{
193
53.5M
  return bmap ? isl_space_dim(bmap->dim, isl_dim_all) + bmap->n_div : 
00
;
194
53.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
341k
{
216
341k
  if (!bmap)
217
0
    return -1;
218
341k
  return bmap->n_eq;
219
341k
}
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.73k
{
226
1.73k
  return isl_basic_map_n_equality(bset_to_bmap(bset));
227
1.73k
}
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
369k
{
234
369k
  if (!bmap)
235
0
    return -1;
236
369k
  return bmap->n_ineq;
237
369k
}
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.71k
{
244
1.71k
  return isl_basic_map_n_inequality(bset_to_bmap(bset));
245
1.71k
}
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
625k
{
252
625k
  isl_space *space1, *space2;
253
625k
254
625k
  space1 = isl_basic_map_peek_space(bmap1);
255
625k
  space2 = isl_basic_map_peek_space(bmap2);
256
625k
  return isl_space_has_equal_params(space1, space2);
257
625k
}
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.4k
{
295
76.4k
  isl_bool m;
296
76.4k
  if (!bmap || !bset)
297
0
    return isl_bool_error;
298
76.4k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
299
76.4k
  if (m < 0 || !m)
300
0
    return m;
301
76.4k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_in,
302
76.4k
          bset->dim, isl_dim_set);
303
76.4k
}
304
305
isl_bool isl_map_compatible_range(__isl_keep isl_map *map,
306
  __isl_keep isl_set *set)
307
5.05k
{
308
5.05k
  isl_bool m;
309
5.05k
  if (!map || !set)
310
0
    return isl_bool_error;
311
5.05k
  m = isl_map_has_equal_params(map, set_to_map(set));
312
5.05k
  if (m < 0 || !m)
313
0
    return m;
314
5.05k
  return isl_space_tuple_is_equal(map->dim, isl_dim_out,
315
5.05k
          set->dim, isl_dim_set);
316
5.05k
}
317
318
isl_bool isl_basic_map_compatible_range(__isl_keep isl_basic_map *bmap,
319
  __isl_keep isl_basic_set *bset)
320
6.47k
{
321
6.47k
  isl_bool m;
322
6.47k
  if (!bmap || !bset)
323
0
    return isl_bool_error;
324
6.47k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
325
6.47k
  if (m < 0 || !m)
326
0
    return m;
327
6.47k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_out,
328
6.47k
          bset->dim, isl_dim_set);
329
6.47k
}
330
331
isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
332
4.86M
{
333
4.86M
  return bmap ? bmap->ctx : NULL;
334
4.86M
}
335
336
isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
337
238k
{
338
238k
  return bset ? bset->ctx : NULL;
339
238k
}
340
341
isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
342
61.7k
{
343
61.7k
  return map ? map->ctx : NULL;
344
61.7k
}
345
346
isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
347
413k
{
348
413k
  return set ? set->ctx : NULL;
349
413k
}
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
6.02M
{
356
6.02M
  return bmap ? bmap->dim : NULL;
357
6.02M
}
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
685k
{
368
685k
  return isl_space_copy(isl_basic_map_peek_space(bmap));
369
685k
}
370
371
__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
372
201k
{
373
201k
  return isl_basic_map_get_space(bset_to_bmap(bset));
374
201k
}
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
74.6k
{
380
74.6k
  int i;
381
74.6k
  isl_ctx *ctx;
382
74.6k
  isl_mat *div;
383
74.6k
  unsigned total;
384
74.6k
  unsigned cols;
385
74.6k
386
74.6k
  if (!bmap)
387
0
    return NULL;
388
74.6k
389
74.6k
  ctx = isl_basic_map_get_ctx(bmap);
390
74.6k
  total = isl_space_dim(bmap->dim, isl_dim_all);
391
74.6k
  cols = 1 + 1 + total + bmap->n_div;
392
74.6k
  div = isl_mat_alloc(ctx, bmap->n_div, cols);
393
74.6k
  if (!div)
394
0
    return NULL;
395
74.6k
396
89.0k
  
for (i = 0; 74.6k
i < bmap->n_div;
++i14.3k
)
397
14.3k
    isl_seq_cpy(div->row[i], bmap->div[i], cols);
398
74.6k
399
74.6k
  return div;
400
74.6k
}
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
54.4k
{
412
54.4k
  isl_mat *div;
413
54.4k
414
54.4k
  if (!bmap)
415
0
    return NULL;
416
54.4k
417
54.4k
  div = isl_basic_map_get_divs(bmap);
418
54.4k
  return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div);
419
54.4k
}
420
421
__isl_give isl_local_space *isl_basic_set_get_local_space(
422
  __isl_keep isl_basic_set *bset)
423
7.29k
{
424
7.29k
  return isl_basic_map_get_local_space(bset);
425
7.29k
}
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
140k
{
437
140k
  int i;
438
140k
  unsigned n_div;
439
140k
440
140k
  if (!bmap)
441
0
    return NULL;
442
140k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
443
140k
  if (n_div == 0)
444
106k
    return bmap;
445
33.2k
  bmap = isl_basic_map_cow(bmap);
446
33.2k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div);
447
33.2k
  if (!bmap)
448
0
    return NULL;
449
69.7k
  
for (i = 0; 33.2k
i < n_div;
++i36.5k
) {
450
36.5k
    if (isl_int_is_zero(bmap->div[i][0]))
451
36.5k
      
continue365
;
452
36.1k
    if (isl_basic_map_add_div_constraints(bmap, i) < 0)
453
0
      return isl_basic_map_free(bmap);
454
36.1k
  }
455
33.2k
456
33.2k
  return bmap;
457
33.2k
}
458
459
__isl_give isl_basic_map *isl_basic_map_from_local_space(
460
  __isl_take isl_local_space *ls)
461
136k
{
462
136k
  int i;
463
136k
  int n_div;
464
136k
  isl_basic_map *bmap;
465
136k
466
136k
  if (!ls)
467
0
    return NULL;
468
136k
469
136k
  n_div = isl_local_space_dim(ls, isl_dim_div);
470
136k
  bmap = isl_basic_map_alloc_space(isl_local_space_get_space(ls),
471
136k
          n_div, 0, 2 * n_div);
472
136k
473
168k
  for (i = 0; i < n_div; 
++i32.2k
)
474
32.2k
    if (isl_basic_map_alloc_div(bmap) < 0)
475
0
      goto error;
476
136k
477
168k
  
for (i = 0; 136k
i < n_div;
++i32.2k
)
478
32.2k
    isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col);
479
136k
  bmap = add_known_div_constraints(bmap);
480
136k
          
481
136k
  isl_local_space_free(ls);
482
136k
  return bmap;
483
0
error:
484
0
  isl_local_space_free(ls);
485
0
  isl_basic_map_free(bmap);
486
0
  return NULL;
487
136k
}
488
489
__isl_give isl_basic_set *isl_basic_set_from_local_space(
490
  __isl_take isl_local_space *ls)
491
20.5k
{
492
20.5k
  return isl_basic_map_from_local_space(ls);
493
20.5k
}
494
495
__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
496
722k
{
497
722k
  return isl_space_copy(isl_map_peek_space(map));
498
722k
}
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
112
{
591
112
  return map ? isl_space_has_tuple_name(map->dim, type) : 
isl_bool_error0
;
592
112
}
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.47k
{
625
2.47k
  return isl_map_set_tuple_id(set, isl_dim_set, id);
626
2.47k
}
627
628
__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
629
  enum isl_dim_type type)
630
5.94k
{
631
5.94k
  map = isl_map_cow(map);
632
5.94k
  if (!map)
633
0
    return NULL;
634
5.94k
635
5.94k
  map->dim = isl_space_reset_tuple_id(map->dim, type);
636
5.94k
637
5.94k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
638
5.94k
}
639
640
__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
641
5.94k
{
642
5.94k
  return isl_map_reset_tuple_id(set, isl_dim_set);
643
5.94k
}
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
418
{
663
418
  return isl_map_get_tuple_id(set, isl_dim_set);
664
418
}
665
666
/* Does the set tuple have a name?
667
 */
668
isl_bool isl_set_has_tuple_name(__isl_keep isl_set *set)
669
147
{
670
147
  if (!set)
671
0
    return isl_bool_error;
672
147
  return isl_space_has_tuple_name(set->dim, isl_dim_set);
673
147
}
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
174
{
683
174
  return set ? isl_space_get_tuple_name(set->dim, isl_dim_set) : NULL;
684
174
}
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
119
{
848
119
  if (!map)
849
0
    return -1;
850
119
  return isl_space_find_dim_by_id(map->dim, type, id);
851
119
}
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
119
{
856
119
  return isl_map_find_dim_by_id(set, type, id);
857
119
}
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
918
{
874
918
  if (!map)
875
0
    return -1;
876
918
  return isl_space_find_dim_by_name(map->dim, type, name);
877
918
}
878
879
int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
880
  const char *name)
881
918
{
882
918
  return isl_map_find_dim_by_name(set, type, name);
883
918
}
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
386k
{
956
386k
  if (!bmap)
957
0
    return isl_bool_error;
958
386k
  return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
959
386k
}
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.79k
{
969
8.79k
  int i;
970
8.79k
  isl_bool rational;
971
8.79k
972
8.79k
  if (!map)
973
0
    return isl_bool_error;
974
8.79k
  if (map->n == 0)
975
0
    return isl_bool_false;
976
8.79k
  rational = isl_basic_map_is_rational(map->p[0]);
977
8.79k
  if (rational < 0)
978
0
    return rational;
979
9.65k
  
for (i = 1; 8.79k
i < map->n;
++i859
) {
980
859
    isl_bool rational_i;
981
859
982
859
    rational_i = isl_basic_map_is_rational(map->p[i]);
983
859
    if (rational_i < 0)
984
0
      return rational_i;
985
859
    if (rational != rational_i)
986
859
      
isl_die0
(isl_map_get_ctx(map), isl_error_unsupported,
987
859
        "mixed rational and integer basic maps "
988
859
        "not supported", return isl_bool_error);
989
859
  }
990
8.79k
991
8.79k
  return rational;
992
8.79k
}
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.79k
{
1002
8.79k
  return isl_map_is_rational(set);
1003
8.79k
}
1004
1005
int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
1006
45.7k
{
1007
45.7k
  return isl_basic_map_is_rational(bset);
1008
45.7k
}
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.9k
{
1018
91.9k
  isl_bool has_rational = isl_bool_true;
1019
91.9k
  unsigned total;
1020
91.9k
1021
91.9k
  if (!bmap)
1022
0
    return isl_bool_error;
1023
91.9k
  if (isl_basic_map_plain_is_empty(bmap))
1024
2
    return isl_bool_false;
1025
91.9k
  if (!isl_basic_map_is_rational(bmap))
1026
91.6k
    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.3k
{
1058
78.3k
  int i;
1059
78.3k
  isl_bool has_rational;
1060
78.3k
1061
78.3k
  if (!map)
1062
0
    return isl_bool_error;
1063
170k
  
for (i = 0; 78.3k
i < map->n;
++i91.6k
) {
1064
91.9k
    has_rational = isl_basic_map_has_rational(map->p[i]);
1065
91.9k
    if (has_rational < 0 || has_rational)
1066
306
      return has_rational;
1067
91.9k
  }
1068
78.3k
  
return isl_bool_false78.0k
;
1069
78.3k
}
1070
1071
/* Does "set" contain any rational points?
1072
 */
1073
isl_bool isl_set_has_rational(__isl_keep isl_set *set)
1074
26.1k
{
1075
26.1k
  return isl_map_has_rational(set);
1076
26.1k
}
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.4k
{
1091
64.4k
  if (!set)
1092
0
    return isl_bool_error;
1093
64.4k
  return isl_space_is_params(set->dim);
1094
64.4k
}
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
175
{
1102
175
  if (!map)
1103
0
    return isl_bool_error;
1104
175
  return isl_space_is_params(map->dim);
1105
175
}
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.59M
{
1111
4.59M
  int i;
1112
4.59M
  size_t row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + extra;
1113
4.59M
1114
4.59M
  bmap->ctx = ctx;
1115
4.59M
  isl_ctx_ref(ctx);
1116
4.59M
1117
4.59M
  bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
1118
4.59M
  if (isl_blk_is_error(bmap->block))
1119
0
    goto error;
1120
4.59M
1121
4.59M
  bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
1122
4.59M
  if ((n_ineq + n_eq) && 
!bmap->ineq3.33M
)
1123
0
    goto error;
1124
4.59M
1125
4.59M
  if (extra == 0) {
1126
4.29M
    bmap->block2 = isl_blk_empty();
1127
4.29M
    bmap->div = NULL;
1128
4.29M
  } else {
1129
297k
    bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
1130
297k
    if (isl_blk_is_error(bmap->block2))
1131
0
      goto error;
1132
297k
1133
297k
    bmap->div = isl_alloc_array(ctx, isl_int *, extra);
1134
297k
    if (!bmap->div)
1135
0
      goto error;
1136
4.59M
  }
1137
4.59M
1138
31.2M
  
for (i = 0; 4.59M
i < n_ineq + n_eq;
++i26.6M
)
1139
26.6M
    bmap->ineq[i] = bmap->block.data + i * row_size;
1140
4.59M
1141
5.15M
  for (i = 0; i < extra; 
++i561k
)
1142
561k
    bmap->div[i] = bmap->block2.data + i * (1 + row_size);
1143
4.59M
1144
4.59M
  bmap->ref = 1;
1145
4.59M
  bmap->flags = 0;
1146
4.59M
  bmap->c_size = n_eq + n_ineq;
1147
4.59M
  bmap->eq = bmap->ineq + n_ineq;
1148
4.59M
  bmap->extra = extra;
1149
4.59M
  bmap->n_eq = 0;
1150
4.59M
  bmap->n_ineq = 0;
1151
4.59M
  bmap->n_div = 0;
1152
4.59M
  bmap->sample = NULL;
1153
4.59M
1154
4.59M
  return bmap;
1155
0
error:
1156
0
  isl_basic_map_free(bmap);
1157
0
  return NULL;
1158
4.59M
}
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
275k
{
1164
275k
  struct isl_basic_map *bmap;
1165
275k
  isl_space *space;
1166
275k
1167
275k
  space = isl_space_set_alloc(ctx, nparam, dim);
1168
275k
  if (!space)
1169
0
    return NULL;
1170
275k
1171
275k
  bmap = isl_basic_map_alloc_space(space, extra, n_eq, n_ineq);
1172
275k
  return bset_from_bmap(bmap);
1173
275k
}
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
382k
{
1178
382k
  struct isl_basic_map *bmap;
1179
382k
  if (!dim)
1180
0
    return NULL;
1181
382k
  isl_assert(dim->ctx, dim->n_in == 0, goto error);
1182
382k
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1183
382k
  return bset_from_bmap(bmap);
1184
0
error:
1185
0
  isl_space_free(dim);
1186
0
  return NULL;
1187
382k
}
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.59M
{
1192
4.59M
  struct isl_basic_map *bmap;
1193
4.59M
1194
4.59M
  if (!dim)
1195
0
    return NULL;
1196
4.59M
  bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
1197
4.59M
  if (!bmap)
1198
1
    goto error;
1199
4.59M
  bmap->dim = dim;
1200
4.59M
1201
4.59M
  return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
1202
1
error:
1203
1
  isl_space_free(dim);
1204
1
  return NULL;
1205
4.59M
}
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.42M
{
1225
2.42M
  int i;
1226
2.42M
  unsigned total = isl_basic_map_total_dim(src);
1227
2.42M
1228
3.83M
  for (i = 0; i < src->n_eq; 
++i1.41M
) {
1229
1.41M
    int j = isl_basic_map_alloc_equality(dst);
1230
1.41M
    isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
1231
1.41M
  }
1232
2.42M
1233
17.0M
  for (i = 0; i < src->n_ineq; 
++i14.6M
) {
1234
14.6M
    int j = isl_basic_map_alloc_inequality(dst);
1235
14.6M
    isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
1236
14.6M
  }
1237
2.42M
1238
2.53M
  for (i = 0; i < src->n_div; 
++i114k
) {
1239
114k
    int j = isl_basic_map_alloc_div(dst);
1240
114k
    isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
1241
114k
  }
1242
2.42M
  ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
1243
2.42M
}
1244
1245
__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap)
1246
2.42M
{
1247
2.42M
  struct isl_basic_map *dup;
1248
2.42M
1249
2.42M
  if (!bmap)
1250
0
    return NULL;
1251
2.42M
  dup = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
1252
2.42M
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
1253
2.42M
  if (!dup)
1254
0
    return NULL;
1255
2.42M
  dup_constraints(dup, bmap);
1256
2.42M
  dup->flags = bmap->flags;
1257
2.42M
  dup->sample = isl_vec_copy(bmap->sample);
1258
2.42M
  return dup;
1259
2.42M
}
1260
1261
struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
1262
52.4k
{
1263
52.4k
  struct isl_basic_map *dup;
1264
52.4k
1265
52.4k
  dup = isl_basic_map_dup(bset_to_bmap(bset));
1266
52.4k
  return bset_from_bmap(dup);
1267
52.4k
}
1268
1269
__isl_give isl_basic_set *isl_basic_set_copy(__isl_keep isl_basic_set *bset)
1270
1.01M
{
1271
1.01M
  if (!bset)
1272
208
    return NULL;
1273
1.01M
1274
1.01M
  if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
1275
994k
    bset->ref++;
1276
994k
    return bset;
1277
994k
  }
1278
20.0k
  return isl_basic_set_dup(bset);
1279
20.0k
}
1280
1281
__isl_give isl_set *isl_set_copy(__isl_keep isl_set *set)
1282
1.74M
{
1283
1.74M
  if (!set)
1284
18.4k
    return NULL;
1285
1.72M
1286
1.72M
  set->ref++;
1287
1.72M
  return set;
1288
1.72M
}
1289
1290
__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)
1291
3.87M
{
1292
3.87M
  if (!bmap)
1293
0
    return NULL;
1294
3.87M
1295
3.87M
  if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
1296
3.74M
    bmap->ref++;
1297
3.74M
    return bmap;
1298
3.74M
  }
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.33M
{
1307
1.33M
  if (!map)
1308
155
    return NULL;
1309
1.33M
1310
1.33M
  map->ref++;
1311
1.33M
  return map;
1312
1.33M
}
1313
1314
__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap)
1315
13.6M
{
1316
13.6M
  if (!bmap)
1317
6.52M
    return NULL;
1318
7.08M
1319
7.08M
  if (--bmap->ref > 0)
1320
2.49M
    return NULL;
1321
4.58M
1322
4.58M
  isl_ctx_deref(bmap->ctx);
1323
4.58M
  free(bmap->div);
1324
4.58M
  isl_blk_free(bmap->ctx, bmap->block2);
1325
4.58M
  free(bmap->ineq);
1326
4.58M
  isl_blk_free(bmap->ctx, bmap->block);
1327
4.58M
  isl_vec_free(bmap->sample);
1328
4.58M
  isl_space_free(bmap->dim);
1329
4.58M
  free(bmap);
1330
4.58M
1331
4.58M
  return NULL;
1332
4.58M
}
1333
1334
__isl_null isl_basic_set *isl_basic_set_free(__isl_take isl_basic_set *bset)
1335
1.68M
{
1336
1.68M
  return isl_basic_map_free(bset_to_bmap(bset));
1337
1.68M
}
1338
1339
static int room_for_con(struct isl_basic_map *bmap, unsigned n)
1340
5.67M
{
1341
5.67M
  return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
1342
5.67M
}
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
21.3k
{
1357
21.3k
  return isl_space_check_named_params(isl_basic_map_peek_space(bmap));
1358
21.3k
}
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
542k
{
1366
542k
  isl_bool match;
1367
542k
1368
542k
  match = isl_basic_map_has_equal_params(bmap1, bmap2);
1369
542k
  if (match < 0)
1370
0
    return isl_stat_error;
1371
542k
  if (!match)
1372
542k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
1373
542k
      "parameters don't match", return isl_stat_error);
1374
542k
  return isl_stat_ok;
1375
542k
}
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
10
    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
10
error:
1394
10
  isl_map_free(map1);
1395
10
  isl_map_free(map2);
1396
10
  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.8k
{
1403
63.8k
  isl_bool r;
1404
63.8k
1405
63.8k
  if (!map1 || !map2)
1406
0
    return isl_bool_error;
1407
63.8k
  if (isl_map_has_equal_params(map1, map2))
1408
61.3k
    return fn(map1, map2);
1409
2.54k
  if (isl_map_check_named_params(map1) < 0)
1410
0
    return isl_bool_error;
1411
2.54k
  if (isl_map_check_named_params(map2) < 0)
1412
0
    return isl_bool_error;
1413
2.54k
  map1 = isl_map_copy(map1);
1414
2.54k
  map2 = isl_map_copy(map2);
1415
2.54k
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
1416
2.54k
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
1417
2.54k
  r = fn(map1, map2);
1418
2.54k
  isl_map_free(map1);
1419
2.54k
  isl_map_free(map2);
1420
2.54k
  return r;
1421
2.54k
}
1422
1423
int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
1424
4.45M
{
1425
4.45M
  struct isl_ctx *ctx;
1426
4.45M
  if (!bmap)
1427
0
    return -1;
1428
4.45M
  ctx = bmap->ctx;
1429
4.45M
  isl_assert(ctx, room_for_con(bmap, 1), return -1);
1430
4.45M
  isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
1431
4.45M
      return -1);
1432
4.45M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1433
4.45M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1434
4.45M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1435
4.45M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1436
4.45M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1437
4.45M
  if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
1438
96.2k
    isl_int *t;
1439
96.2k
    int j = isl_basic_map_alloc_inequality(bmap);
1440
96.2k
    if (j < 0)
1441
0
      return -1;
1442
96.2k
    t = bmap->ineq[j];
1443
96.2k
    bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
1444
96.2k
    bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1445
96.2k
    bmap->eq[-1] = t;
1446
96.2k
    bmap->n_eq++;
1447
96.2k
    bmap->n_ineq--;
1448
96.2k
    bmap->eq--;
1449
96.2k
    return 0;
1450
96.2k
  }
1451
4.35M
  isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
1452
4.35M
          bmap->extra - bmap->n_div);
1453
4.35M
  return bmap->n_eq++;
1454
4.35M
}
1455
1456
int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
1457
1.06M
{
1458
1.06M
  return isl_basic_map_alloc_equality(bset_to_bmap(bset));
1459
1.06M
}
1460
1461
int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
1462
320k
{
1463
320k
  if (!bmap)
1464
0
    return -1;
1465
320k
  isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
1466
320k
  bmap->n_eq -= n;
1467
320k
  return 0;
1468
320k
}
1469
1470
int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
1471
549
{
1472
549
  return isl_basic_map_free_equality(bset_to_bmap(bset), n);
1473
549
}
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
263k
    t = bmap->eq[pos];
1484
263k
    bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
1485
263k
    bmap->eq[bmap->n_eq - 1] = t;
1486
263k
  }
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.02M
{
1501
1.02M
  isl_int *t;
1502
1.02M
1503
1.02M
  t = bmap->ineq[pos];
1504
1.02M
  bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1505
1.02M
  bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1506
1.02M
  bmap->eq[-1] = t;
1507
1.02M
  bmap->n_eq++;
1508
1.02M
  bmap->n_ineq--;
1509
1.02M
  bmap->eq--;
1510
1.02M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1511
1.02M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1512
1.02M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1513
1.02M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1514
1.02M
}
1515
1516
static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
1517
23.0M
{
1518
23.0M
  return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
1519
23.0M
}
1520
1521
int isl_basic_map_alloc_inequality(__isl_keep isl_basic_map *bmap)
1522
22.4M
{
1523
22.4M
  struct isl_ctx *ctx;
1524
22.4M
  if (!bmap)
1525
0
    return -1;
1526
22.4M
  ctx = bmap->ctx;
1527
22.4M
  isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
1528
22.4M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1529
22.4M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1530
22.4M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1531
22.4M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1532
22.4M
  isl_seq_clr(bmap->ineq[bmap->n_ineq] +
1533
22.4M
          1 + isl_basic_map_total_dim(bmap),
1534
22.4M
          bmap->extra - bmap->n_div);
1535
22.4M
  return bmap->n_ineq++;
1536
22.4M
}
1537
1538
int isl_basic_set_alloc_inequality(__isl_keep isl_basic_set *bset)
1539
737k
{
1540
737k
  return isl_basic_map_alloc_inequality(bset_to_bmap(bset));
1541
737k
}
1542
1543
int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
1544
967k
{
1545
967k
  if (!bmap)
1546
0
    return -1;
1547
967k
  isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
1548
967k
  bmap->n_ineq -= n;
1549
967k
  return 0;
1550
967k
}
1551
1552
int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
1553
5.63k
{
1554
5.63k
  return isl_basic_map_free_inequality(bset_to_bmap(bset), n);
1555
5.63k
}
1556
1557
int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
1558
7.62M
{
1559
7.62M
  isl_int *t;
1560
7.62M
  if (!bmap)
1561
0
    return -1;
1562
7.62M
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1563
7.62M
1564
7.62M
  if (pos != bmap->n_ineq - 1) {
1565
4.22M
    t = bmap->ineq[pos];
1566
4.22M
    bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1567
4.22M
    bmap->ineq[bmap->n_ineq - 1] = t;
1568
4.22M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1569
4.22M
  }
1570
7.62M
  bmap->n_ineq--;
1571
7.62M
  return 0;
1572
7.62M
}
1573
1574
int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
1575
19.3k
{
1576
19.3k
  return isl_basic_map_drop_inequality(bset_to_bmap(bset), pos);
1577
19.3k
}
1578
1579
__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
1580
  isl_int *eq)
1581
20.6k
{
1582
20.6k
  int k;
1583
20.6k
1584
20.6k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
1585
20.6k
  if (!bmap)
1586
0
    return NULL;
1587
20.6k
  k = isl_basic_map_alloc_equality(bmap);
1588
20.6k
  if (k < 0)
1589
0
    goto error;
1590
20.6k
  isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
1591
20.6k
  return bmap;
1592
0
error:
1593
0
  isl_basic_map_free(bmap);
1594
0
  return NULL;
1595
20.6k
}
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
394k
{
1606
394k
  int k;
1607
394k
1608
394k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
1609
394k
  if (!bmap)
1610
0
    return NULL;
1611
394k
  k = isl_basic_map_alloc_inequality(bmap);
1612
394k
  if (k < 0)
1613
0
    goto error;
1614
394k
  isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
1615
394k
  return bmap;
1616
0
error:
1617
0
  isl_basic_map_free(bmap);
1618
0
  return NULL;
1619
394k
}
1620
1621
__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
1622
  isl_int *ineq)
1623
22.0k
{
1624
22.0k
  return bset_from_bmap(isl_basic_map_add_ineq(bset_to_bmap(bset), ineq));
1625
22.0k
}
1626
1627
int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
1628
539k
{
1629
539k
  if (!bmap)
1630
0
    return -1;
1631
539k
  isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
1632
539k
  isl_seq_clr(bmap->div[bmap->n_div] +
1633
539k
          1 + 1 + isl_basic_map_total_dim(bmap),
1634
539k
          bmap->extra - bmap->n_div);
1635
539k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1636
539k
  return bmap->n_div++;
1637
539k
}
1638
1639
int isl_basic_set_alloc_div(struct isl_basic_set *bset)
1640
1.12k
{
1641
1.12k
  return isl_basic_map_alloc_div(bset_to_bmap(bset));
1642
1.12k
}
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
337k
{
1650
337k
  unsigned dim;
1651
337k
1652
337k
  if (!bmap)
1653
0
    return isl_stat_error;
1654
337k
  dim = isl_basic_map_dim(bmap, type);
1655
337k
  if (first + n > dim || first + n < first)
1656
337k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1657
337k
      "position or range out of bounds",
1658
337k
      return isl_stat_error);
1659
337k
  return isl_stat_ok;
1660
337k
}
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
4.10k
{
1671
4.10k
  int i, k;
1672
4.10k
1673
4.10k
  bmap = isl_basic_map_cow(bmap);
1674
4.10k
  if (!bmap || !div)
1675
0
    return isl_basic_map_free(bmap);
1676
4.10k
1677
4.10k
  if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all))
1678
4.10k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1679
4.10k
      "unexpected size", return isl_basic_map_free(bmap));
1680
4.10k
  if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0)
1681
0
    return isl_basic_map_free(bmap);
1682
4.10k
1683
4.10k
  bmap = isl_basic_map_extend_space(bmap,
1684
4.10k
          isl_basic_map_get_space(bmap), 1, 0, 2);
1685
4.10k
  k = isl_basic_map_alloc_div(bmap);
1686
4.10k
  if (k < 0)
1687
0
    return isl_basic_map_free(bmap);
1688
4.10k
  isl_seq_cpy(bmap->div[k], div->el, div->size);
1689
4.10k
  isl_int_set_si(bmap->div[k][div->size], 0);
1690
4.10k
1691
4.58k
  for (i = k; i > pos; 
--i482
)
1692
482
    isl_basic_map_swap_div(bmap, i, i - 1);
1693
4.10k
1694
4.10k
  return bmap;
1695
4.10k
}
1696
1697
isl_stat isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
1698
679k
{
1699
679k
  if (!bmap)
1700
0
    return isl_stat_error;
1701
679k
  isl_assert(bmap->ctx, n <= bmap->n_div, return isl_stat_error);
1702
679k
  bmap->n_div -= n;
1703
679k
  return isl_stat_ok;
1704
679k
}
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.07M
{
1715
6.07M
  unsigned src_nparam = isl_basic_map_dim(src_map, isl_dim_param);
1716
6.07M
  unsigned dst_nparam = isl_basic_map_dim(dst_map, isl_dim_param);
1717
6.07M
  unsigned src_in = isl_basic_map_dim(src_map, isl_dim_in);
1718
6.07M
  unsigned dst_in = isl_basic_map_dim(dst_map, isl_dim_in);
1719
6.07M
  unsigned src_out = isl_basic_map_dim(src_map, isl_dim_out);
1720
6.07M
  unsigned dst_out = isl_basic_map_dim(dst_map, isl_dim_out);
1721
6.07M
  isl_int_set(dst[0], src[0]);
1722
6.07M
  isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
1723
6.07M
  if (dst_nparam > src_nparam)
1724
0
    isl_seq_clr(dst+1+src_nparam,
1725
0
        dst_nparam - src_nparam);
1726
6.07M
  isl_seq_clr(dst+1+dst_nparam, in_off);
1727
6.07M
  isl_seq_cpy(dst+1+dst_nparam+in_off,
1728
6.07M
        src+1+src_nparam,
1729
6.07M
        isl_min(dst_in-in_off, src_in));
1730
6.07M
  if (dst_in-in_off > src_in)
1731
48.7k
    isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
1732
48.7k
        dst_in - in_off - src_in);
1733
6.07M
  isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
1734
6.07M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
1735
6.07M
        src+1+src_nparam+src_in,
1736
6.07M
        isl_min(dst_out-out_off, src_out));
1737
6.07M
  if (dst_out-out_off > src_out)
1738
502k
    isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
1739
502k
        dst_out - out_off - src_out);
1740
6.07M
  isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
1741
6.07M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
1742
6.07M
        src+1+src_nparam+src_in+src_out,
1743
6.07M
        isl_min(dst_map->extra-div_off, src_map->n_div));
1744
6.07M
  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.07M
}
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
138k
{
1754
138k
  isl_int_set(dst[0], src[0]);
1755
138k
  copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
1756
138k
}
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.15M
{
1762
1.15M
  int i;
1763
1.15M
  unsigned div_off;
1764
1.15M
1765
1.15M
  if (!bmap1 || 
!bmap21.15M
)
1766
1
    goto error;
1767
1.15M
1768
1.15M
  div_off = bmap1->n_div;
1769
1.15M
1770
1.91M
  for (i = 0; i < bmap2->n_eq; 
++i764k
) {
1771
764k
    int i1 = isl_basic_map_alloc_equality(bmap1);
1772
764k
    if (i1 < 0)
1773
0
      goto error;
1774
764k
    copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
1775
764k
        i_pos, o_pos, div_off);
1776
764k
  }
1777
1.15M
1778
6.32M
  
for (i = 0; 1.15M
i < bmap2->n_ineq;
++i5.17M
) {
1779
5.17M
    int i1 = isl_basic_map_alloc_inequality(bmap1);
1780
5.17M
    if (i1 < 0)
1781
0
      goto error;
1782
5.17M
    copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
1783
5.17M
        i_pos, o_pos, div_off);
1784
5.17M
  }
1785
1.15M
1786
1.29M
  
for (i = 0; 1.15M
i < bmap2->n_div;
++i138k
) {
1787
138k
    int i1 = isl_basic_map_alloc_div(bmap1);
1788
138k
    if (i1 < 0)
1789
0
      goto error;
1790
138k
    copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
1791
138k
       i_pos, o_pos, div_off);
1792
138k
  }
1793
1.15M
1794
1.15M
  isl_basic_map_free(bmap2);
1795
1.15M
1796
1.15M
  return bmap1;
1797
1
1798
1
error:
1799
1
  isl_basic_map_free(bmap1);
1800
1
  isl_basic_map_free(bmap2);
1801
1
  return NULL;
1802
1.15M
}
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.35M
{
1815
1.35M
  struct isl_basic_map *ext;
1816
1.35M
  unsigned flags;
1817
1.35M
  int dims_ok;
1818
1.35M
1819
1.35M
  if (!dim)
1820
0
    goto error;
1821
1.35M
1822
1.35M
  if (!base)
1823
0
    goto error;
1824
1.35M
1825
1.35M
  dims_ok = isl_space_is_equal(base->dim, dim) &&
1826
1.35M
      
base->extra >= base->n_div + extra1.24M
;
1827
1.35M
1828
1.35M
  if (dims_ok && 
room_for_con(base, n_eq + n_ineq)1.22M
&&
1829
1.35M
           
room_for_ineq(base, n_ineq)575k
) {
1830
561k
    isl_space_free(dim);
1831
561k
    return base;
1832
561k
  }
1833
789k
1834
789k
  isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
1835
789k
  isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
1836
789k
  isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
1837
789k
  extra += base->extra;
1838
789k
  n_eq += base->n_eq;
1839
789k
  n_ineq += base->n_ineq;
1840
789k
1841
789k
  ext = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1842
789k
  dim = NULL;
1843
789k
  if (!ext)
1844
1
    goto error;
1845
789k
1846
789k
  if (dims_ok)
1847
660k
    ext->sample = isl_vec_copy(base->sample);
1848
789k
  flags = base->flags;
1849
789k
  ext = add_constraints(ext, base, 0, 0);
1850
789k
  if (ext) {
1851
789k
    ext->flags = flags;
1852
789k
    ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
1853
789k
  }
1854
789k
1855
789k
  return ext;
1856
1
1857
1
error:
1858
1
  isl_space_free(dim);
1859
1
  isl_basic_map_free(base);
1860
1
  return NULL;
1861
789k
}
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
723k
{
1875
723k
  if (!base)
1876
0
    return NULL;
1877
723k
  return isl_basic_map_extend_space(base, isl_space_copy(base->dim),
1878
723k
          0, n_eq, n_ineq);
1879
723k
}
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
144k
{
1885
144k
  struct isl_basic_map *bmap;
1886
144k
  isl_space *dim;
1887
144k
1888
144k
  if (!base)
1889
0
    return NULL;
1890
144k
  dim = isl_space_alloc(base->ctx, nparam, n_in, n_out);
1891
144k
  if (!dim)
1892
0
    goto error;
1893
144k
1894
144k
  bmap = isl_basic_map_extend_space(base, dim, extra, n_eq, n_ineq);
1895
144k
  return bmap;
1896
0
error:
1897
0
  isl_basic_map_free(base);
1898
0
  return NULL;
1899
144k
}
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
144k
{
1905
144k
  return bset_from_bmap(isl_basic_map_extend(bset_to_bmap(base),
1906
144k
          nparam, 0, dim, extra, n_eq, n_ineq));
1907
144k
}
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
879k
{
1919
879k
  return bset_from_bmap(isl_basic_map_cow(bset_to_bmap(bset)));
1920
879k
}
1921
1922
__isl_give isl_basic_map *isl_basic_map_cow(__isl_take isl_basic_map *bmap)
1923
5.06M
{
1924
5.06M
  if (!bmap)
1925
0
    return NULL;
1926
5.06M
1927
5.06M
  if (bmap->ref > 1) {
1928
2.24M
    bmap->ref--;
1929
2.24M
    bmap = isl_basic_map_dup(bmap);
1930
2.24M
  }
1931
5.06M
  if (bmap) {
1932
5.06M
    ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
1933
5.06M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
1934
5.06M
  }
1935
5.06M
  return bmap;
1936
5.06M
}
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.94M
{
1945
2.94M
  isl_basic_map_free(map->cached_simple_hull[0]);
1946
2.94M
  isl_basic_map_free(map->cached_simple_hull[1]);
1947
2.94M
  map->cached_simple_hull[0] = NULL;
1948
2.94M
  map->cached_simple_hull[1] = NULL;
1949
2.94M
  return map;
1950
2.94M
}
1951
1952
__isl_give isl_set *isl_set_cow(__isl_take isl_set *set)
1953
204k
{
1954
204k
  return isl_map_cow(set);
1955
204k
}
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.01M
{
1969
2.01M
  if (!map)
1970
19
    return NULL;
1971
2.01M
1972
2.01M
  if (map->ref == 1)
1973
1.40M
    return clear_caches(map);
1974
611k
  map->ref--;
1975
611k
  return isl_map_dup(map);
1976
611k
}
1977
1978
static void swap_vars(struct isl_blk blk, isl_int *a,
1979
      unsigned a_len, unsigned b_len)
1980
413k
{
1981
413k
  isl_seq_cpy(blk.data, a+a_len, b_len);
1982
413k
  isl_seq_cpy(blk.data+b_len, a, a_len);
1983
413k
  isl_seq_cpy(a, blk.data, b_len+a_len);
1984
413k
}
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
184k
{
1989
184k
  int i;
1990
184k
  struct isl_blk blk;
1991
184k
1992
184k
  if (!bmap)
1993
0
    goto error;
1994
184k
1995
184k
  isl_assert(bmap->ctx,
1996
184k
    pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);
1997
184k
1998
184k
  if (n1 == 0 || 
n2 == 073.4k
)
1999
118k
    return bmap;
2000
66.2k
2001
66.2k
  bmap = isl_basic_map_cow(bmap);
2002
66.2k
  if (!bmap)
2003
0
    return NULL;
2004
66.2k
2005
66.2k
  blk = isl_blk_alloc(bmap->ctx, n1 + n2);
2006
66.2k
  if (isl_blk_is_error(blk))
2007
0
    goto error;
2008
66.2k
2009
264k
  
for (i = 0; 66.2k
i < bmap->n_eq;
++i198k
)
2010
198k
    swap_vars(blk,
2011
198k
        bmap->eq[i] + pos, n1, n2);
2012
66.2k
2013
277k
  for (i = 0; i < bmap->n_ineq; 
++i211k
)
2014
211k
    swap_vars(blk,
2015
211k
        bmap->ineq[i] + pos, n1, n2);
2016
66.2k
2017
70.2k
  for (i = 0; i < bmap->n_div; 
++i4.06k
)
2018
4.06k
    swap_vars(blk,
2019
4.06k
        bmap->div[i]+1 + pos, n1, n2);
2020
66.2k
2021
66.2k
  isl_blk_free(bmap->ctx, blk);
2022
66.2k
2023
66.2k
  ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
2024
66.2k
  bmap = isl_basic_map_gauss(bmap, NULL);
2025
66.2k
  return isl_basic_map_finalize(bmap);
2026
0
error:
2027
0
  isl_basic_map_free(bmap);
2028
0
  return NULL;
2029
66.2k
}
2030
2031
__isl_give isl_basic_map *isl_basic_map_set_to_empty(
2032
  __isl_take isl_basic_map *bmap)
2033
202k
{
2034
202k
  int i = 0;
2035
202k
  unsigned total;
2036
202k
  if (!bmap)
2037
0
    goto error;
2038
202k
  total = isl_basic_map_total_dim(bmap);
2039
202k
  if (isl_basic_map_free_div(bmap, bmap->n_div) < 0)
2040
0
    return isl_basic_map_free(bmap);
2041
202k
  isl_basic_map_free_inequality(bmap, bmap->n_ineq);
2042
202k
  if (bmap->n_eq > 0)
2043
107k
    isl_basic_map_free_equality(bmap, bmap->n_eq-1);
2044
95.3k
  else {
2045
95.3k
    i = isl_basic_map_alloc_equality(bmap);
2046
95.3k
    if (i < 0)
2047
0
      goto error;
2048
202k
  }
2049
202k
  isl_int_set_si(bmap->eq[i][0], 1);
2050
202k
  isl_seq_clr(bmap->eq[i]+1, total);
2051
202k
  ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
2052
202k
  isl_vec_free(bmap->sample);
2053
202k
  bmap->sample = NULL;
2054
202k
  return isl_basic_map_finalize(bmap);
2055
0
error:
2056
0
  isl_basic_map_free(bmap);
2057
0
  return NULL;
2058
202k
}
2059
2060
__isl_give isl_basic_set *isl_basic_set_set_to_empty(
2061
  __isl_take isl_basic_set *bset)
2062
6.79k
{
2063
6.79k
  return bset_from_bmap(isl_basic_map_set_to_empty(bset_to_bmap(bset)));
2064
6.79k
}
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.18k
{
2136
9.18k
  isl_int *t = bmap->div[a];
2137
9.18k
  bmap->div[a] = bmap->div[b];
2138
9.18k
  bmap->div[b] = t;
2139
9.18k
}
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.96k
{
2146
8.96k
  int i;
2147
8.96k
  unsigned off = isl_space_dim(bmap->dim, isl_dim_all);
2148
8.96k
2149
8.96k
  swap_div(bmap, a, b);
2150
8.96k
2151
59.5k
  for (i = 0; i < bmap->n_eq; 
++i50.6k
)
2152
50.6k
    isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
2153
8.96k
2154
113k
  for (i = 0; i < bmap->n_ineq; 
++i104k
)
2155
104k
    isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
2156
8.96k
2157
55.1k
  for (i = 0; i < bmap->n_div; 
++i46.1k
)
2158
46.1k
    isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
2159
8.96k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2160
8.96k
}
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.62M
{
2172
7.62M
  isl_seq_cpy(c, c + n, rem);
2173
7.62M
  isl_seq_clr(c + rem, n);
2174
7.62M
}
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
163k
{
2186
163k
  return isl_basic_map_drop(bset_to_bmap(bset), isl_dim_set, first, n);
2187
163k
}
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
782
{
2194
782
  isl_int **div;
2195
782
  int i;
2196
782
2197
782
  if (first + n == bmap->n_div)
2198
679
    return bmap;
2199
103
2200
103
  div = isl_alloc_array(bmap->ctx, isl_int *, n);
2201
103
  if (!div)
2202
0
    goto error;
2203
206
  
for (i = 0; 103
i < n;
++i103
)
2204
103
    div[i] = bmap->div[first + i];
2205
266
  for (i = 0; i < bmap->n_div - first - n; 
++i163
)
2206
163
    bmap->div[first + i] = bmap->div[first + n + i];
2207
206
  for (i = 0; i < n; 
++i103
)
2208
103
    bmap->div[bmap->n_div - n + i] = div[i];
2209
103
  free(div);
2210
103
  return bmap;
2211
0
error:
2212
0
  isl_basic_map_free(bmap);
2213
0
  return NULL;
2214
103
}
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.9k
{
2222
83.9k
  if (!map)
2223
0
    return isl_stat_error;
2224
83.9k
  if (first + n > isl_map_dim(map, type) || first + n < first)
2225
83.9k
    
isl_die0
(isl_map_get_ctx(map), isl_error_invalid,
2226
83.9k
      "position or range out of bounds",
2227
83.9k
      return isl_stat_error);
2228
83.9k
  return isl_stat_ok;
2229
83.9k
}
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
536k
{
2241
536k
  int i;
2242
536k
  unsigned dim;
2243
536k
  unsigned offset;
2244
536k
  unsigned left;
2245
536k
2246
536k
  if (!bmap)
2247
0
    goto error;
2248
536k
2249
536k
  dim = isl_basic_map_dim(bmap, type);
2250
536k
  isl_assert(bmap->ctx, first + n <= dim, goto error);
2251
536k
2252
536k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)90.9k
)
2253
90.9k
    return bmap;
2254
445k
2255
445k
  bmap = isl_basic_map_cow(bmap);
2256
445k
  if (!bmap)
2257
0
    return NULL;
2258
445k
2259
445k
  offset = isl_basic_map_offset(bmap, type) + first;
2260
445k
  left = isl_basic_map_total_dim(bmap) - (offset - 1) - n;
2261
449k
  for (i = 0; i < bmap->n_eq; 
++i4.15k
)
2262
4.15k
    constraint_drop_vars(bmap->eq[i]+offset, n, left);
2263
445k
2264
2.05M
  for (i = 0; i < bmap->n_ineq; 
++i1.60M
)
2265
1.60M
    constraint_drop_vars(bmap->ineq[i]+offset, n, left);
2266
445k
2267
447k
  for (i = 0; i < bmap->n_div; 
++i2.18k
)
2268
2.18k
    constraint_drop_vars(bmap->div[i]+1+offset, n, left);
2269
445k
2270
445k
  if (type == isl_dim_div) {
2271
782
    bmap = move_divs_last(bmap, first, n);
2272
782
    if (!bmap)
2273
0
      goto error;
2274
782
    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
445k
  if (!bmap->dim)
2279
0
    goto error;
2280
445k
2281
445k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2282
445k
  bmap = isl_basic_map_simplify(bmap);
2283
445k
  return isl_basic_map_finalize(bmap);
2284
0
error:
2285
0
  isl_basic_map_free(bmap);
2286
0
  return NULL;
2287
445k
}
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
370k
{
2292
370k
  return bset_from_bmap(isl_basic_map_drop(bset_to_bmap(bset),
2293
370k
              type, first, n));
2294
370k
}
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.26M
{
2300
2.26M
  if (!map)
2301
0
    return NULL;
2302
2.26M
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2303
2.26M
  return map;
2304
2.26M
}
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
799
{
2309
799
  int i;
2310
799
2311
799
  if (isl_map_check_range(map, type, first, n) < 0)
2312
0
    return isl_map_free(map);
2313
799
2314
799
  if (n == 0 && 
!isl_space_is_named_or_nested(map->dim, type)0
)
2315
0
    return map;
2316
799
  map = isl_map_cow(map);
2317
799
  if (!map)
2318
0
    goto error;
2319
799
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
2320
799
  if (!map->dim)
2321
0
    goto error;
2322
799
2323
1.74k
  
for (i = 0; 799
i < map->n;
++i949
) {
2324
949
    map->p[i] = isl_basic_map_drop(map->p[i], type, first, n);
2325
949
    if (!map->p[i])
2326
0
      goto error;
2327
949
  }
2328
799
  map = isl_map_unmark_normalized(map);
2329
799
2330
799
  return map;
2331
0
error:
2332
0
  isl_map_free(map);
2333
0
  return NULL;
2334
799
}
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
475k
{
2348
475k
  int i;
2349
475k
  unsigned pos;
2350
475k
2351
475k
  if (!bmap)
2352
0
    goto error;
2353
475k
2354
475k
  pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;
2355
475k
2356
475k
  isl_assert(bmap->ctx, div < bmap->n_div, goto error);
2357
475k
2358
2.41M
  
for (i = 0; 475k
i < bmap->n_eq;
++i1.93M
)
2359
1.93M
    constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);
2360
475k
2361
3.45M
  for (i = 0; i < bmap->n_ineq; 
++i2.97M
) {
2362
2.97M
    if (!isl_int_is_zero(bmap->ineq[i][pos])) {
2363
21.7k
      isl_basic_map_drop_inequality(bmap, i);
2364
21.7k
      --i;
2365
21.7k
      continue;
2366
21.7k
    }
2367
2.95M
    constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
2368
2.95M
  }
2369
475k
2370
1.59M
  for (i = 0; i < bmap->n_div; 
++i1.11M
)
2371
1.11M
    constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);
2372
475k
2373
475k
  if (div != bmap->n_div - 1) {
2374
37.0k
    int j;
2375
37.0k
    isl_int *t = bmap->div[div];
2376
37.0k
2377
91.9k
    for (j = div; j < bmap->n_div - 1; 
++j54.9k
)
2378
54.9k
      bmap->div[j] = bmap->div[j+1];
2379
37.0k
2380
37.0k
    bmap->div[bmap->n_div - 1] = t;
2381
37.0k
  }
2382
475k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2383
475k
  if (isl_basic_map_free_div(bmap, 1) < 0)
2384
0
    return isl_basic_map_free(bmap);
2385
475k
2386
475k
  return bmap;
2387
0
error:
2388
0
  isl_basic_map_free(bmap);
2389
0
  return NULL;
2390
475k
}
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
18.1k
{
2399
18.1k
  int i;
2400
18.1k
2401
18.1k
  if (n == 0)
2402
6.88k
    return map;
2403
11.3k
2404
11.3k
  if (isl_map_check_range(map, type, first, n) < 0)
2405
0
    return isl_map_free(map);
2406
11.3k
2407
11.3k
  map = isl_map_cow(map);
2408
11.3k
  if (!map)
2409
0
    return NULL;
2410
11.3k
2411
22.7k
  
for (i = 0; 11.3k
i < map->n;
++i11.4k
) {
2412
11.4k
    map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n);
2413
11.4k
    if (!map->p[i])
2414
0
      goto error;
2415
11.4k
  }
2416
11.3k
  return map;
2417
0
error:
2418
0
  isl_map_free(map);
2419
0
  return NULL;
2420
11.3k
}
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.2k
{
2429
14.2k
  return set_from_map(isl_map_eliminate(set_to_map(set), type, first, n));
2430
14.2k
}
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.89k
{
2445
2.89k
  if (!bmap)
2446
0
    return NULL;
2447
2.89k
  bmap = isl_basic_map_eliminate_vars(bmap,
2448
2.89k
          isl_space_dim(bmap->dim, isl_dim_all), bmap->n_div);
2449
2.89k
  if (!bmap)
2450
0
    return NULL;
2451
2.89k
  bmap->n_div = 0;
2452
2.89k
  return isl_basic_map_finalize(bmap);
2453
2.89k
}
2454
2455
__isl_give isl_basic_set *isl_basic_set_remove_divs(
2456
  __isl_take isl_basic_set *bset)
2457
806
{
2458
806
  return bset_from_bmap(isl_basic_map_remove_divs(bset_to_bmap(bset)));
2459
806
}
2460
2461
__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
2462
5.64k
{
2463
5.64k
  int i;
2464
5.64k
2465
5.64k
  if (!map)
2466
0
    return NULL;
2467
5.64k
  if (map->n == 0)
2468
4.43k
    return map;
2469
1.21k
2470
1.21k
  map = isl_map_cow(map);
2471
1.21k
  if (!map)
2472
0
    return NULL;
2473
1.21k
  
2474
3.26k
  
for (i = 0; 1.21k
i < map->n;
++i2.05k
) {
2475
2.05k
    map->p[i] = isl_basic_map_remove_divs(map->p[i]);
2476
2.05k
    if (!map->p[i])
2477
0
      goto error;
2478
2.05k
  }
2479
1.21k
  return map;
2480
0
error:
2481
0
  isl_map_free(map);
2482
0
  return NULL;
2483
1.21k
}
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.21k
{
2494
4.21k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2495
0
    return isl_basic_map_free(bmap);
2496
4.21k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)2.56k
)
2497
2.56k
    return bmap;
2498
1.64k
  bmap = isl_basic_map_eliminate_vars(bmap,
2499
1.64k
      isl_basic_map_offset(bmap, type) - 1 + first, n);
2500
1.64k
  if (!bmap)
2501
0
    return bmap;
2502
1.64k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && 
type == isl_dim_div31
)
2503
31
    return bmap;
2504
1.61k
  bmap = isl_basic_map_drop(bmap, type, first, n);
2505
1.61k
  return bmap;
2506
1.61k
}
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.29k
{
2514
1.29k
  int i;
2515
1.29k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
2516
1.29k
2517
1.29k
  if (isl_int_is_zero(bmap->div[div][0]))
2518
1.29k
    
return isl_bool_false365
;
2519
930
  if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0)
2520
92
    return isl_bool_true;
2521
838
2522
1.84k
  
for (i = bmap->n_div - 1; 838
i >= 0;
--i1.01k
) {
2523
1.01k
    isl_bool involves;
2524
1.01k
2525
1.01k
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
2526
1.01k
      continue;
2527
0
    involves = div_involves_vars(bmap, i, first, n);
2528
0
    if (involves < 0 || involves)
2529
0
      return involves;
2530
0
  }
2531
838
2532
838
  return isl_bool_false;
2533
838
}
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
92
{
2686
92
  int i;
2687
92
  int check_lb, check_ub;
2688
92
  isl_int v;
2689
92
  unsigned total;
2690
92
2691
92
  if (!bmap)
2692
0
    return NULL;
2693
92
2694
92
  if (isl_int_is_zero(bmap->div[div][0]))
2695
92
    
return bmap0
;
2696
92
2697
92
  total = isl_space_dim(bmap->dim, isl_dim_all);
2698
92
2699
92
  check_lb = 0;
2700
92
  check_ub = 0;
2701
433
  for (i = 0; (!check_lb || 
!check_ub27
) &&
i < bmap->n_ineq414
;
++i341
) {
2702
341
    int s = isl_int_sgn(bmap->ineq[i][1 + total + div]);
2703
341
    if (s > 0)
2704
19
      check_ub = 1;
2705
341
    if (s < 0)
2706
20
      check_lb = 1;
2707
341
  }
2708
92
2709
92
  if (!check_lb && 
!check_ub73
)
2710
73
    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.8k
{
2734
10.8k
  int i;
2735
10.8k
2736
10.8k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2737
0
    return isl_basic_map_free(bmap);
2738
10.8k
  first += isl_basic_map_offset(bmap, type);
2739
10.8k
2740
12.1k
  for (i = bmap->n_div - 1; i >= 0; 
--i1.29k
) {
2741
1.29k
    isl_bool involves;
2742
1.29k
2743
1.29k
    involves = div_involves_vars(bmap, i, first, n);
2744
1.29k
    if (involves < 0)
2745
0
      return isl_basic_map_free(bmap);
2746
1.29k
    if (!involves)
2747
1.20k
      continue;
2748
92
    bmap = insert_bounds_on_div(bmap, i);
2749
92
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
2750
92
    if (!bmap)
2751
0
      return NULL;
2752
92
    i = bmap->n_div;
2753
92
  }
2754
10.8k
2755
10.8k
  return bmap;
2756
10.8k
}
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.44k
{
2768
8.44k
  int i;
2769
8.44k
2770
8.44k
  if (!map)
2771
0
    return NULL;
2772
8.44k
  if (map->n == 0)
2773
250
    return map;
2774
8.19k
2775
8.19k
  map = isl_map_cow(map);
2776
8.19k
  if (!map)
2777
0
    return NULL;
2778
8.19k
2779
17.6k
  
for (i = 0; 8.19k
i < map->n;
++i9.42k
) {
2780
9.42k
    map->p[i] = isl_basic_map_remove_divs_involving_dims(map->p[i],
2781
9.42k
                type, first, n);
2782
9.42k
    if (!map->p[i])
2783
0
      goto error;
2784
9.42k
  }
2785
8.19k
  return map;
2786
0
error:
2787
0
  isl_map_free(map);
2788
0
  return NULL;
2789
8.19k
}
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.44k
{
2794
8.44k
  return set_from_map(isl_map_remove_divs_involving_dims(set_to_map(set),
2795
8.44k
                    type, first, n));
2796
8.44k
}
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
61.5k
{
2807
61.5k
  int i;
2808
61.5k
2809
61.5k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2810
0
    return isl_bool_error;
2811
61.5k
2812
61.5k
  first += isl_basic_map_offset(bmap, type);
2813
128k
  for (i = 0; i < bmap->n_eq; 
++i66.8k
)
2814
91.8k
    if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
2815
25.0k
      return isl_bool_true;
2816
86.5k
  
for (i = 0; 36.5k
i < bmap->n_ineq;
++i50.0k
)
2817
55.5k
    if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0)
2818
5.52k
      return isl_bool_true;
2819
36.5k
  
for (i = 0; 31.0k
i < bmap->n_div31.1k
;
++i89
) {
2820
89
    if (isl_int_is_zero(bmap->div[i][0]))
2821
89
      
continue0
;
2822
89
    if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0)
2823
0
      return isl_bool_true;
2824
89
  }
2825
31.0k
2826
31.0k
  return isl_bool_false;
2827
31.0k
}
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.96k
{
2832
4.96k
  int i;
2833
4.96k
2834
4.96k
  if (isl_map_check_range(map, type, first, n) < 0)
2835
0
    return isl_bool_error;
2836
4.96k
2837
9.90k
  
for (i = 0; 4.96k
i < map->n;
++i4.93k
) {
2838
5.11k
    isl_bool involves = isl_basic_map_involves_dims(map->p[i],
2839
5.11k
                  type, first, n);
2840
5.11k
    if (involves < 0 || involves)
2841
184
      return involves;
2842
5.11k
  }
2843
4.96k
2844
4.96k
  
return isl_bool_false4.78k
;
2845
4.96k
}
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
56.4k
{
2850
56.4k
  return isl_basic_map_involves_dims(bset, type, first, n);
2851
56.4k
}
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.46k
{
2856
4.46k
  return isl_map_involves_dims(set, type, first, n);
2857
4.46k
}
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
535k
{
2865
535k
  int i;
2866
535k
2867
535k
  if (n == 0)
2868
90.9k
    return bmap;
2869
444k
2870
444k
  bmap = isl_basic_map_cow(bmap);
2871
444k
2872
444k
  if (!bmap)
2873
0
    return NULL;
2874
444k
2875
448k
  
for (i = bmap->n_eq - 1; 444k
i >= 0;
--i4.01k
) {
2876
4.01k
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
2877
3.47k
      continue;
2878
542
    isl_basic_map_drop_equality(bmap, i);
2879
542
  }
2880
444k
2881
10.6M
  for (i = bmap->n_ineq - 1; i >= 0; 
--i10.2M
) {
2882
10.2M
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
2883
4.16M
      continue;
2884
6.03M
    isl_basic_map_drop_inequality(bmap, i);
2885
6.03M
  }
2886
444k
2887
444k
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2888
444k
  return bmap;
2889
444k
}
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
534k
{
2897
534k
  return isl_basic_map_drop_constraints_involving(bset, first, n);
2898
534k
}
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
948
{
2907
948
  int i;
2908
948
2909
948
  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
910
  bmap = isl_basic_map_cow(bmap);
2915
910
  if (!bmap)
2916
0
    return NULL;
2917
910
2918
910
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2919
0
    return isl_basic_map_free(bmap);
2920
910
2921
910
  first += isl_basic_map_offset(bmap, type) - 1;
2922
910
2923
1.07k
  for (i = bmap->n_eq - 1; i >= 0; 
--i167
) {
2924
167
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
2925
83
      continue;
2926
84
    isl_basic_map_drop_equality(bmap, i);
2927
84
  }
2928
910
2929
3.53k
  for (i = bmap->n_ineq - 1; i >= 0; 
--i2.62k
) {
2930
2.62k
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
2931
1.77k
      continue;
2932
849
    isl_basic_map_drop_inequality(bmap, i);
2933
849
  }
2934
910
2935
910
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2936
910
  return bmap;
2937
910
}
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
730
{
2946
730
  return isl_basic_map_drop_constraints_not_involving_dims(bset,
2947
730
                  type, first, n);
2948
730
}
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
59.6k
{
2957
59.6k
  if (!bmap)
2958
0
    return NULL;
2959
59.6k
  if (n == 0)
2960
58.2k
    return bmap;
2961
1.47k
2962
1.47k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2963
0
    return isl_basic_map_free(bmap);
2964
1.47k
2965
1.47k
  bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
2966
1.47k
  first += isl_basic_map_offset(bmap, type) - 1;
2967
1.47k
  return isl_basic_map_drop_constraints_involving(bmap, first, n);
2968
1.47k
}
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
730
{
2977
730
  return isl_basic_map_drop_constraints_involving_dims(bset,
2978
730
                  type, first, n);
2979
730
}
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
151
{
2988
151
  int i;
2989
151
2990
151
  if (isl_map_check_range(map, type, first, n) < 0)
2991
0
    return isl_map_free(map);
2992
151
2993
151
  map = isl_map_cow(map);
2994
151
  if (!map)
2995
0
    return NULL;
2996
151
2997
409
  
for (i = 0; 151
i < map->n;
++i258
) {
2998
258
    map->p[i] = drop(map->p[i], type, first, n);
2999
258
    if (!map->p[i])
3000
0
      return isl_map_free(map);
3001
258
  }
3002
151
3003
151
  if (map->n > 1)
3004
151
    ISL_F_CLR(map, ISL_MAP_DISJOINT);
3005
151
3006
151
  return map;
3007
151
}
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
92
{
3016
92
  if (n == 0)
3017
7
    return map;
3018
85
  return drop_constraints(map, type, first, n,
3019
85
        &isl_basic_map_drop_constraints_involving_dims);
3020
85
}
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
66
{
3029
66
  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
66
  return drop_constraints(map, type, first, n,
3035
66
          &isl_basic_map_drop_constraints_not_involving_dims);
3036
66
}
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
68
{
3045
68
  return isl_map_drop_constraints_involving_dims(set, type, first, n);
3046
68
}
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
66
{
3055
66
  return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
3056
66
}
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
80.5k
{
3066
80.5k
  int i;
3067
80.5k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
3068
80.5k
  isl_bool marked;
3069
80.5k
3070
80.5k
  marked = isl_basic_map_div_is_marked_unknown(bmap, div);
3071
80.5k
  if (marked < 0 || marked)
3072
14.6k
    return isl_bool_not(marked);
3073
65.8k
3074
180k
  
for (i = bmap->n_div - 1; 65.8k
i >= 0;
--i114k
) {
3075
114k
    isl_bool known;
3076
114k
3077
114k
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
3078
114k
      
continue113k
;
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.8k
3084
65.8k
  return isl_bool_true;
3085
65.8k
}
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
195k
{
3092
195k
  int i;
3093
195k
3094
195k
  if (!bmap)
3095
0
    return NULL;
3096
195k
3097
196k
  
for (i = bmap->n_div - 1; 195k
i >= 0;
--i1.16k
) {
3098
1.16k
    if (isl_basic_map_div_is_known(bmap, i))
3099
1.16k
      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
195k
3106
195k
  return bmap;
3107
195k
}
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.94k
{
3114
5.94k
  return isl_basic_map_remove_unknown_divs(bset);
3115
5.94k
}
3116
3117
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
3118
173k
{
3119
173k
  int i;
3120
173k
3121
173k
  if (!map)
3122
0
    return NULL;
3123
173k
  if (map->n == 0)
3124
250
    return map;
3125
173k
3126
173k
  map = isl_map_cow(map);
3127
173k
  if (!map)
3128
0
    return NULL;
3129
173k
3130
362k
  
for (i = 0; 173k
i < map->n;
++i189k
) {
3131
189k
    map->p[i] = isl_basic_map_remove_unknown_divs(map->p[i]);
3132
189k
    if (!map->p[i])
3133
0
      goto error;
3134
189k
  }
3135
173k
  return map;
3136
0
error:
3137
0
  isl_map_free(map);
3138
0
  return NULL;
3139
173k
}
3140
3141
__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
3142
9.17k
{
3143
9.17k
  return set_from_map(isl_map_remove_unknown_divs(set_to_map(set)));
3144
9.17k
}
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.35k
{
3150
3.35k
  isl_basic_map *bmap = bset_to_bmap(bset);
3151
3.35k
  bmap = isl_basic_map_remove_dims(bmap, type, first, n);
3152
3.35k
  return bset_from_bmap(bmap);
3153
3.35k
}
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.80k
{
3158
1.80k
  int i;
3159
1.80k
3160
1.80k
  if (n == 0)
3161
1.22k
    return map;
3162
577
3163
577
  map = isl_map_cow(map);
3164
577
  if (isl_map_check_range(map, type, first, n) < 0)
3165
0
    return isl_map_free(map);
3166
577
  
3167
1.30k
  
for (i = 0; 577
i < map->n;
++i727
) {
3168
727
    map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
3169
727
      isl_basic_map_offset(map->p[i], type) - 1 + first, n);
3170
727
    if (!map->p[i])
3171
0
      goto error;
3172
727
  }
3173
577
  map = isl_map_drop(map, type, first, n);
3174
577
  return map;
3175
0
error:
3176
0
  isl_map_free(map);
3177
0
  return NULL;
3178
577
}
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
21.3k
{
3344
21.3k
  unsigned total;
3345
21.3k
  if (!bmap)
3346
0
    return -1;
3347
21.3k
  total = isl_basic_map_total_dim(bmap);
3348
21.3k
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
3349
21.3k
  isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
3350
21.3k
  isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
3351
21.3k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
3352
21.3k
  return 0;
3353
21.3k
}
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.25k
{
3373
6.25k
  int i;
3374
6.25k
  struct isl_map *grown = NULL;
3375
6.25k
3376
6.25k
  if (!map)
3377
0
    return NULL;
3378
6.25k
  isl_assert(map->ctx, n >= 0, goto error);
3379
6.25k
  if (map->n + n <= map->size)
3380
5.94k
    return map;
3381
315
  grown = isl_map_alloc_space(isl_map_get_space(map), map->n + n, map->flags);
3382
315
  if (!grown)
3383
0
    goto error;
3384
715
  
for (i = 0; 315
i < map->n;
++i400
) {
3385
400
    grown->p[i] = isl_basic_map_copy(map->p[i]);
3386
400
    if (!grown->p[i])
3387
0
      goto error;
3388
400
    grown->n++;
3389
400
  }
3390
315
  isl_map_free(map);
3391
315
  return grown;
3392
0
error:
3393
0
  isl_map_free(grown);
3394
0
  isl_map_free(map);
3395
0
  return NULL;
3396
315
}
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
2.85k
{
3402
2.85k
  return set_from_map(isl_map_grow(set_to_map(set), n));
3403
2.85k
}
3404
3405
__isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset)
3406
82.0k
{
3407
82.0k
  return isl_map_from_basic_map(bset);
3408
82.0k
}
3409
3410
__isl_give isl_map *isl_map_from_basic_map(__isl_take isl_basic_map *bmap)
3411
202k
{
3412
202k
  struct isl_map *map;
3413
202k
3414
202k
  if (!bmap)
3415
0
    return NULL;
3416
202k
3417
202k
  map = isl_map_alloc_space(isl_space_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
3418
202k
  return isl_map_add_basic_map(map, bmap);
3419
202k
}
3420
3421
__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
3422
            __isl_take isl_basic_set *bset)
3423
140k
{
3424
140k
  return set_from_map(isl_map_add_basic_map(set_to_map(set),
3425
140k
            bset_to_bmap(bset)));
3426
140k
}
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
0
    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
0
error:
3497
0
  isl_basic_map_free(bmap);
3498
0
  isl_basic_set_free(bset);
3499
0
  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
6.47k
{
3507
6.47k
  isl_bool ok;
3508
6.47k
3509
6.47k
  ok = isl_basic_map_compatible_range(bmap, bset);
3510
6.47k
  if (ok < 0)
3511
0
    return isl_stat_error;
3512
6.47k
  if (!ok)
3513
6.47k
    
isl_die0
(isl_basic_set_get_ctx(bset), isl_error_invalid,
3514
6.47k
      "incompatible spaces", return isl_stat_error);
3515
6.47k
3516
6.47k
  return isl_stat_ok;
3517
6.47k
}
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
6.48k
{
3522
6.48k
  struct isl_basic_map *bmap_range;
3523
6.48k
3524
6.48k
  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
3525
0
    goto error;
3526
6.48k
3527
6.48k
  if (isl_space_dim(bset->dim, isl_dim_set) != 0 &&
3528
6.48k
      
isl_basic_map_check_compatible_range(bmap, bset) < 06.47k
)
3529
0
    goto error;
3530
6.48k
3531
6.48k
  if (isl_basic_set_plain_is_universe(bset)) {
3532
0
    isl_basic_set_free(bset);
3533
0
    return bmap;
3534
0
  }
3535
6.48k
3536
6.48k
  bmap = isl_basic_map_cow(bmap);
3537
6.48k
  if (!bmap)
3538
0
    goto error;
3539
6.48k
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
3540
6.48k
      bset->n_div, bset->n_eq, bset->n_ineq);
3541
6.48k
  bmap_range = bset_to_bmap(bset);
3542
6.48k
  bmap = add_constraints(bmap, bmap_range, 0, 0);
3543
6.48k
3544
6.48k
  bmap = isl_basic_map_simplify(bmap);
3545
6.48k
  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
6.48k
}
3551
3552
isl_bool isl_basic_map_contains(__isl_keep isl_basic_map *bmap,
3553
  __isl_keep isl_vec *vec)
3554
1.62M
{
3555
1.62M
  int i;
3556
1.62M
  unsigned total;
3557
1.62M
  isl_int s;
3558
1.62M
3559
1.62M
  if (!bmap || !vec)
3560
0
    return isl_bool_error;
3561
1.62M
3562
1.62M
  total = 1 + isl_basic_map_total_dim(bmap);
3563
1.62M
  if (total != vec->size)
3564
31.5k
    return isl_bool_false;
3565
1.59M
3566
1.59M
  isl_int_init(s);
3567
1.59M
3568
2.72M
  for (i = 0; i < bmap->n_eq; 
++i1.12M
) {
3569
1.52M
    isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
3570
1.52M
    if (!isl_int_is_zero(s)) {
3571
400k
      isl_int_clear(s);
3572
400k
      return isl_bool_false;
3573
400k
    }
3574
1.52M
  }
3575
1.59M
3576
6.54M
  
for (i = 0; 1.19M
i < bmap->n_ineq;
++i5.35M
) {
3577
5.77M
    isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
3578
5.77M
    if (isl_int_is_neg(s)) {
3579
414k
      isl_int_clear(s);
3580
414k
      return isl_bool_false;
3581
414k
    }
3582
5.77M
  }
3583
1.19M
3584
1.19M
  
isl_int_clear777k
(s);
3585
777k
3586
777k
  return isl_bool_true;
3587
1.19M
}
3588
3589
isl_bool isl_basic_set_contains(__isl_keep isl_basic_set *bset,
3590
  __isl_keep isl_vec *vec)
3591
828k
{
3592
828k
  return isl_basic_map_contains(bset_to_bmap(bset), vec);
3593
828k
}
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
290k
{
3598
290k
  struct isl_vec *sample = NULL;
3599
290k
3600
290k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
3601
0
    goto error;
3602
290k
  if (isl_space_dim(bmap1->dim, isl_dim_all) ==
3603
290k
        isl_space_dim(bmap1->dim, isl_dim_param) &&
3604
290k
      isl_space_dim(bmap2->dim, isl_dim_all) !=
3605
73.0k
        isl_space_dim(bmap2->dim, isl_dim_param))
3606
0
    return isl_basic_map_intersect(bmap2, bmap1);
3607
290k
3608
290k
  if (isl_space_dim(bmap2->dim, isl_dim_all) !=
3609
290k
          isl_space_dim(bmap2->dim, isl_dim_param))
3610
290k
    isl_assert(bmap1->ctx,
3611
290k
          isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);
3612
290k
3613
290k
  if (isl_basic_map_plain_is_empty(bmap1)) {
3614
43
    isl_basic_map_free(bmap2);
3615
43
    return bmap1;
3616
43
  }
3617
290k
  if (isl_basic_map_plain_is_empty(bmap2)) {
3618
0
    isl_basic_map_free(bmap1);
3619
0
    return bmap2;
3620
0
  }
3621
290k
3622
290k
  if (bmap1->sample &&
3623
290k
      
isl_basic_map_contains(bmap1, bmap1->sample) > 0142k
&&
3624
290k
      
isl_basic_map_contains(bmap2, bmap1->sample) > 0130k
)
3625
33.6k
    sample = isl_vec_copy(bmap1->sample);
3626
256k
  else if (bmap2->sample &&
3627
256k
      
isl_basic_map_contains(bmap1, bmap2->sample) > 0120k
&&
3628
256k
      
isl_basic_map_contains(bmap2, bmap2->sample) > 021.4k
)
3629
21.1k
    sample = isl_vec_copy(bmap2->sample);
3630
290k
3631
290k
  bmap1 = isl_basic_map_cow(bmap1);
3632
290k
  if (!bmap1)
3633
0
    goto error;
3634
290k
  bmap1 = isl_basic_map_extend_space(bmap1, isl_space_copy(bmap1->dim),
3635
290k
      bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
3636
290k
  bmap1 = add_constraints(bmap1, bmap2, 0, 0);
3637
290k
3638
290k
  if (!bmap1)
3639
0
    isl_vec_free(sample);
3640
290k
  else if (sample) {
3641
54.8k
    isl_vec_free(bmap1->sample);
3642
54.8k
    bmap1->sample = sample;
3643
54.8k
  }
3644
290k
3645
290k
  bmap1 = isl_basic_map_simplify(bmap1);
3646
290k
  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
290k
}
3654
3655
struct isl_basic_set *isl_basic_set_intersect(
3656
    struct isl_basic_set *bset1, struct isl_basic_set *bset2)
3657
74.2k
{
3658
74.2k
  return bset_from_bmap(isl_basic_map_intersect(bset_to_bmap(bset1),
3659
74.2k
              bset_to_bmap(bset2)));
3660
74.2k
}
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.00k
    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.6k
    map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
3694
19.7k
  else
3695
19.7k
    map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
3696
19.7k
              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.91k
    isl_basic_map_free(map1->p[0]);
3705
5.91k
    map1->n = 0;
3706
5.91k
  }
3707
40.3k
3708
40.3k
  isl_map_free(map2);
3709
40.3k
3710
40.3k
  map1 = isl_map_unmark_normalized(map1);
3711
40.3k
  return map1;
3712
0
error:
3713
0
  isl_map_free(map1);
3714
0
  isl_map_free(map2);
3715
0
  return NULL;
3716
40.3k
}
3717
3718
/* map2 may be either a parameter domain or a map living in the same
3719
 * space as map1.
3720
 */
3721
static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1,
3722
  __isl_take isl_map *map2)
3723
413k
{
3724
413k
  unsigned flags = 0;
3725
413k
  isl_bool equal;
3726
413k
  isl_map *result;
3727
413k
  int i, j;
3728
413k
3729
413k
  if (!map1 || !map2)
3730
0
    goto error;
3731
413k
3732
413k
  if ((isl_map_plain_is_empty(map1) ||
3733
413k
       
isl_map_plain_is_universe(map2)400k
) &&
3734
413k
      
isl_space_is_equal(map1->dim, map2->dim)223k
) {
3735
205k
    isl_map_free(map2);
3736
205k
    return map1;
3737
205k
  }
3738
207k
  if ((isl_map_plain_is_empty(map2) ||
3739
207k
       
isl_map_plain_is_universe(map1)202k
) &&
3740
207k
      
isl_space_is_equal(map1->dim, map2->dim)112k
) {
3741
85.8k
    isl_map_free(map1);
3742
85.8k
    return map2;
3743
85.8k
  }
3744
121k
3745
121k
  if (map1->n == 1 && 
map2->n == 1108k
&&
3746
121k
      
map1->p[0]->n_div == 0102k
&&
map2->p[0]->n_div == 099.5k
&&
3747
121k
      
isl_space_is_equal(map1->dim, map2->dim)98.4k
&&
3748
121k
      
(70.6k
map1->p[0]->n_eq + map1->p[0]->n_ineq == 170.6k
||
3749
70.6k
       
map2->p[0]->n_eq + map2->p[0]->n_ineq == 159.0k
))
3750
43.4k
    return map_intersect_add_constraint(map1, map2);
3751
78.5k
3752
78.5k
  equal = isl_map_plain_is_equal(map1, map2);
3753
78.5k
  if (equal < 0)
3754
0
    goto error;
3755
78.5k
  if (equal) {
3756
10.9k
    isl_map_free(map2);
3757
10.9k
    return map1;
3758
10.9k
  }
3759
67.5k
3760
67.5k
  if (isl_space_dim(map2->dim, isl_dim_all) !=
3761
67.5k
        isl_space_dim(map2->dim, isl_dim_param))
3762
67.5k
    isl_assert(map1->ctx,
3763
67.5k
          isl_space_is_equal(map1->dim, map2->dim), goto error);
3764
67.5k
3765
67.5k
  if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
3766
67.5k
      
ISL_F_ISSET52.7k
(map2, ISL_MAP_DISJOINT))
3767
67.5k
    
ISL_FL_SET48.9k
(flags, ISL_MAP_DISJOINT);
3768
67.5k
3769
67.5k
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
3770
67.5k
        map1->n * map2->n, flags);
3771
67.5k
  if (!result)
3772
0
    goto error;
3773
157k
  
for (i = 0; 67.5k
i < map1->n;
++i90.2k
)
3774
253k
    
for (j = 0; 90.2k
j < map2->n;
++j163k
) {
3775
163k
      struct isl_basic_map *part;
3776
163k
      part = isl_basic_map_intersect(
3777
163k
            isl_basic_map_copy(map1->p[i]),
3778
163k
            isl_basic_map_copy(map2->p[j]));
3779
163k
      if (isl_basic_map_is_empty(part) < 0)
3780
0
        part = isl_basic_map_free(part);
3781
163k
      result = isl_map_add_basic_map(result, part);
3782
163k
      if (!result)
3783
0
        goto error;
3784
163k
    }
3785
67.5k
  isl_map_free(map1);
3786
67.5k
  isl_map_free(map2);
3787
67.5k
  return result;
3788
0
error:
3789
0
  isl_map_free(map1);
3790
0
  isl_map_free(map2);
3791
0
  return NULL;
3792
67.5k
}
3793
3794
static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
3795
  __isl_take isl_map *map2)
3796
365k
{
3797
365k
  if (!map1 || !map2)
3798
0
    goto error;
3799
365k
  if (!isl_space_is_equal(map1->dim, map2->dim))
3800
365k
    
isl_die0
(isl_map_get_ctx(map1), isl_error_invalid,
3801
365k
      "spaces don't match", goto error);
3802
365k
  return map_intersect_internal(map1, map2);
3803
0
error:
3804
0
  isl_map_free(map1);
3805
0
  isl_map_free(map2);
3806
0
  return NULL;
3807
365k
}
3808
3809
__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
3810
  __isl_take isl_map *map2)
3811
365k
{
3812
365k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect);
3813
365k
}
3814
3815
struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
3816
292k
{
3817
292k
  return set_from_map(isl_map_intersect(set_to_map(set1),
3818
292k
                set_to_map(set2)));
3819
292k
}
3820
3821
/* map_intersect_internal accepts intersections
3822
 * with parameter domains, so we can just call that function.
3823
 */
3824
static __isl_give isl_map *map_intersect_params(__isl_take isl_map *map,
3825
    __isl_take isl_set *params)
3826
48.0k
{
3827
48.0k
  return map_intersect_internal(map, params);
3828
48.0k
}
3829
3830
__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1,
3831
  __isl_take isl_map *map2)
3832
48.0k
{
3833
48.0k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect_params);
3834
48.0k
}
3835
3836
__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
3837
    __isl_take isl_set *params)
3838
16.3k
{
3839
16.3k
  return isl_map_intersect_params(set, params);
3840
16.3k
}
3841
3842
__isl_give isl_basic_map *isl_basic_map_reverse(__isl_take isl_basic_map *bmap)
3843
182k
{
3844
182k
  isl_space *space;
3845
182k
  unsigned pos, n1, n2;
3846
182k
3847
182k
  if (!bmap)
3848
1
    return NULL;
3849
182k
  bmap = isl_basic_map_cow(bmap);
3850
182k
  if (!bmap)
3851
0
    return NULL;
3852
182k
  space = isl_space_reverse(isl_space_copy(bmap->dim));
3853
182k
  pos = isl_basic_map_offset(bmap, isl_dim_in);
3854
182k
  n1 = isl_basic_map_dim(bmap, isl_dim_in);
3855
182k
  n2 = isl_basic_map_dim(bmap, isl_dim_out);
3856
182k
  bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
3857
182k
  return isl_basic_map_reset_space(bmap, space);
3858
182k
}
3859
3860
static __isl_give isl_basic_map *basic_map_space_reset(
3861
  __isl_take isl_basic_map *bmap, enum isl_dim_type type)
3862
47.9k
{
3863
47.9k
  isl_space *space;
3864
47.9k
3865
47.9k
  if (!bmap)
3866
0
    return NULL;
3867
47.9k
  if (!isl_space_is_named_or_nested(bmap->dim, type))
3868
43.8k
    return bmap;
3869
4.10k
3870
4.10k
  space = isl_basic_map_get_space(bmap);
3871
4.10k
  space = isl_space_reset(space, type);
3872
4.10k
  bmap = isl_basic_map_reset_space(bmap, space);
3873
4.10k
  return bmap;
3874
4.10k
}
3875
3876
__isl_give isl_basic_map *isl_basic_map_insert_dims(
3877
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
3878
  unsigned pos, unsigned n)
3879
80.5k
{
3880
80.5k
  isl_bool rational;
3881
80.5k
  isl_space *res_space;
3882
80.5k
  struct isl_basic_map *res;
3883
80.5k
  struct isl_dim_map *dim_map;
3884
80.5k
  unsigned total, off;
3885
80.5k
  enum isl_dim_type t;
3886
80.5k
3887
80.5k
  if (n == 0)
3888
19.6k
    return basic_map_space_reset(bmap, type);
3889
60.9k
3890
60.9k
  res_space = isl_space_insert_dims(isl_basic_map_get_space(bmap),
3891
60.9k
          type, pos, n);
3892
60.9k
  if (!res_space)
3893
0
    return isl_basic_map_free(bmap);
3894
60.9k
3895
60.9k
  total = isl_basic_map_total_dim(bmap) + n;
3896
60.9k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
3897
60.9k
  off = 0;
3898
243k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t182k
) {
3899
182k
    if (t != type) {
3900
121k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
3901
121k
    } else {
3902
60.9k
      unsigned size = isl_basic_map_dim(bmap, t);
3903
60.9k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3904
60.9k
            0, pos, off);
3905
60.9k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3906
60.9k
            pos, size - pos, off + pos + n);
3907
60.9k
    }
3908
182k
    off += isl_space_dim(res_space, t);
3909
182k
  }
3910
60.9k
  isl_dim_map_div(dim_map, bmap, off);
3911
60.9k
3912
60.9k
  res = isl_basic_map_alloc_space(res_space,
3913
60.9k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
3914
60.9k
  rational = isl_basic_map_is_rational(bmap);
3915
60.9k
  if (rational < 0)
3916
0
    res = isl_basic_map_free(res);
3917
60.9k
  if (rational)
3918
0
    res = isl_basic_map_set_rational(res);
3919
60.9k
  if (isl_basic_map_plain_is_empty(bmap)) {
3920
1.60k
    isl_basic_map_free(bmap);
3921
1.60k
    free(dim_map);
3922
1.60k
    return isl_basic_map_set_to_empty(res);
3923
1.60k
  }
3924
59.3k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
3925
59.3k
  return isl_basic_map_finalize(res);
3926
59.3k
}
3927
3928
__isl_give isl_basic_set *isl_basic_set_insert_dims(
3929
  __isl_take isl_basic_set *bset,
3930
  enum isl_dim_type type, unsigned pos, unsigned n)
3931
0
{
3932
0
  return isl_basic_map_insert_dims(bset, type, pos, n);
3933
0
}
3934
3935
__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap,
3936
    enum isl_dim_type type, unsigned n)
3937
29.7k
{
3938
29.7k
  if (!bmap)
3939
0
    return NULL;
3940
29.7k
  return isl_basic_map_insert_dims(bmap, type,
3941
29.7k
          isl_basic_map_dim(bmap, type), n);
3942
29.7k
}
3943
3944
__isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset,
3945
    enum isl_dim_type type, unsigned n)
3946
27.4k
{
3947
27.4k
  if (!bset)
3948
0
    return NULL;
3949
27.4k
  isl_assert(bset->ctx, type != isl_dim_in, goto error);
3950
27.4k
  return isl_basic_map_add_dims(bset, type, n);
3951
0
error:
3952
0
  isl_basic_set_free(bset);
3953
0
  return NULL;
3954
27.4k
}
3955
3956
static __isl_give isl_map *map_space_reset(__isl_take isl_map *map,
3957
  enum isl_dim_type type)
3958
43.7k
{
3959
43.7k
  isl_space *space;
3960
43.7k
3961
43.7k
  if (!map || !isl_space_is_named_or_nested(map->dim, type))
3962
9.15k
    return map;
3963
34.6k
3964
34.6k
  space = isl_map_get_space(map);
3965
34.6k
  space = isl_space_reset(space, type);
3966
34.6k
  map = isl_map_reset_space(map, space);
3967
34.6k
  return map;
3968
34.6k
}
3969
3970
__isl_give isl_map *isl_map_insert_dims(__isl_take isl_map *map,
3971
    enum isl_dim_type type, unsigned pos, unsigned n)
3972
35.0k
{
3973
35.0k
  int i;
3974
35.0k
3975
35.0k
  if (n == 0)
3976
2.90k
    return map_space_reset(map, type);
3977
32.1k
3978
32.1k
  map = isl_map_cow(map);
3979
32.1k
  if (!map)
3980
0
    return NULL;
3981
32.1k
3982
32.1k
  map->dim = isl_space_insert_dims(map->dim, type, pos, n);
3983
32.1k
  if (!map->dim)
3984
0
    goto error;
3985
32.1k
3986
65.7k
  
for (i = 0; 32.1k
i < map->n;
++i33.5k
) {
3987
33.5k
    map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n);
3988
33.5k
    if (!map->p[i])
3989
0
      goto error;
3990
33.5k
  }
3991
32.1k
3992
32.1k
  return map;
3993
0
error:
3994
0
  isl_map_free(map);
3995
0
  return NULL;
3996
32.1k
}
3997
3998
__isl_give isl_set *isl_set_insert_dims(__isl_take isl_set *set,
3999
    enum isl_dim_type type, unsigned pos, unsigned n)
4000
7.19k
{
4001
7.19k
  return isl_map_insert_dims(set, type, pos, n);
4002
7.19k
}
4003
4004
__isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map,
4005
    enum isl_dim_type type, unsigned n)
4006
27.8k
{
4007
27.8k
  if (!map)
4008
0
    return NULL;
4009
27.8k
  return isl_map_insert_dims(map, type, isl_map_dim(map, type), n);
4010
27.8k
}
4011
4012
__isl_give isl_set *isl_set_add_dims(__isl_take isl_set *set,
4013
    enum isl_dim_type type, unsigned n)
4014
22.2k
{
4015
22.2k
  if (!set)
4016
0
    return NULL;
4017
22.2k
  isl_assert(set->ctx, type != isl_dim_in, goto error);
4018
22.2k
  return set_from_map(isl_map_add_dims(set_to_map(set), type, n));
4019
0
error:
4020
0
  isl_set_free(set);
4021
0
  return NULL;
4022
22.2k
}
4023
4024
__isl_give isl_basic_map *isl_basic_map_move_dims(
4025
  __isl_take isl_basic_map *bmap,
4026
  enum isl_dim_type dst_type, unsigned dst_pos,
4027
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4028
1.06k
{
4029
1.06k
  struct isl_dim_map *dim_map;
4030
1.06k
  struct isl_basic_map *res;
4031
1.06k
  enum isl_dim_type t;
4032
1.06k
  unsigned total, off;
4033
1.06k
4034
1.06k
  if (!bmap)
4035
0
    return NULL;
4036
1.06k
  if (n == 0) {
4037
647
    bmap = isl_basic_map_reset(bmap, src_type);
4038
647
    bmap = isl_basic_map_reset(bmap, dst_type);
4039
647
    return bmap;
4040
647
  }
4041
413
4042
413
  if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0)
4043
0
    return isl_basic_map_free(bmap);
4044
413
4045
413
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4046
0
    return bmap;
4047
413
4048
413
  isl_assert(bmap->ctx, dst_type != src_type, goto error);
4049
413
4050
413
  if (pos(bmap->dim, dst_type) + dst_pos ==
4051
413
      pos(bmap->dim, src_type) + src_pos +
4052
413
              ((src_type < dst_type) ? 
n123
:
0290
)) {
4053
299
    bmap = isl_basic_map_cow(bmap);
4054
299
    if (!bmap)
4055
0
      return NULL;
4056
299
4057
299
    bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4058
299
            src_type, src_pos, n);
4059
299
    if (!bmap->dim)
4060
0
      goto error;
4061
299
4062
299
    bmap = isl_basic_map_finalize(bmap);
4063
299
4064
299
    return bmap;
4065
299
  }
4066
114
4067
114
  total = isl_basic_map_total_dim(bmap);
4068
114
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4069
114
4070
114
  off = 0;
4071
456
  for (t = isl_dim_param; t <= isl_dim_out; 
++t342
) {
4072
342
    unsigned size = isl_space_dim(bmap->dim, t);
4073
342
    if (t == dst_type) {
4074
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4075
114
              0, dst_pos, off);
4076
114
      off += dst_pos;
4077
114
      isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
4078
114
              src_pos, n, off);
4079
114
      off += n;
4080
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4081
114
              dst_pos, size - dst_pos, off);
4082
114
      off += size - dst_pos;
4083
228
    } else if (t == src_type) {
4084
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4085
114
              0, src_pos, off);
4086
114
      off += src_pos;
4087
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4088
114
          src_pos + n, size - src_pos - n, off);
4089
114
      off += size - src_pos - n;
4090
114
    } else {
4091
114
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4092
114
      off += size;
4093
114
    }
4094
342
  }
4095
114
  isl_dim_map_div(dim_map, bmap, off);
4096
114
4097
114
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4098
114
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4099
114
  bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4100
114
  if (!bmap)
4101
0
    goto error;
4102
114
4103
114
  bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4104
114
          src_type, src_pos, n);
4105
114
  if (!bmap->dim)
4106
0
    goto error;
4107
114
4108
114
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
4109
114
  bmap = isl_basic_map_gauss(bmap, NULL);
4110
114
  bmap = isl_basic_map_finalize(bmap);
4111
114
4112
114
  return bmap;
4113
0
error:
4114
0
  isl_basic_map_free(bmap);
4115
0
  return NULL;
4116
114
}
4117
4118
__isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
4119
  enum isl_dim_type dst_type, unsigned dst_pos,
4120
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4121
8
{
4122
8
  isl_basic_map *bmap = bset_to_bmap(bset);
4123
8
  bmap = isl_basic_map_move_dims(bmap, dst_type, dst_pos,
4124
8
          src_type, src_pos, n);
4125
8
  return bset_from_bmap(bmap);
4126
8
}
4127
4128
__isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
4129
  enum isl_dim_type dst_type, unsigned dst_pos,
4130
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4131
1
{
4132
1
  if (!set)
4133
0
    return NULL;
4134
1
  isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
4135
1
  return set_from_map(isl_map_move_dims(set_to_map(set),
4136
1
            dst_type, dst_pos, src_type, src_pos, n));
4137
0
error:
4138
0
  isl_set_free(set);
4139
0
  return NULL;
4140
1
}
4141
4142
__isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
4143
  enum isl_dim_type dst_type, unsigned dst_pos,
4144
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
4145
158
{
4146
158
  int i;
4147
158
4148
158
  if (n == 0) {
4149
0
    map = isl_map_reset(map, src_type);
4150
0
    map = isl_map_reset(map, dst_type);
4151
0
    return map;
4152
0
  }
4153
158
4154
158
  if (isl_map_check_range(map, src_type, src_pos, n))
4155
0
    return isl_map_free(map);
4156
158
4157
158
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4158
0
    return map;
4159
158
4160
158
  isl_assert(map->ctx, dst_type != src_type, goto error);
4161
158
4162
158
  map = isl_map_cow(map);
4163
158
  if (!map)
4164
0
    return NULL;
4165
158
4166
158
  map->dim = isl_space_move_dims(map->dim, dst_type, dst_pos, src_type, src_pos, n);
4167
158
  if (!map->dim)
4168
0
    goto error;
4169
158
4170
338
  
for (i = 0; 158
i < map->n;
++i180
) {
4171
180
    map->p[i] = isl_basic_map_move_dims(map->p[i],
4172
180
            dst_type, dst_pos,
4173
180
            src_type, src_pos, n);
4174
180
    if (!map->p[i])
4175
0
      goto error;
4176
180
  }
4177
158
4178
158
  return map;
4179
0
error:
4180
0
  isl_map_free(map);
4181
0
  return NULL;
4182
158
}
4183
4184
/* Move the specified dimensions to the last columns right before
4185
 * the divs.  Don't change the dimension specification of bmap.
4186
 * That's the responsibility of the caller.
4187
 */
4188
static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
4189
  enum isl_dim_type type, unsigned first, unsigned n)
4190
121k
{
4191
121k
  struct isl_dim_map *dim_map;
4192
121k
  struct isl_basic_map *res;
4193
121k
  enum isl_dim_type t;
4194
121k
  unsigned total, off;
4195
121k
4196
121k
  if (!bmap)
4197
0
    return NULL;
4198
121k
  if (pos(bmap->dim, type) + first + n ==
4199
121k
        1 + isl_space_dim(bmap->dim, isl_dim_all))
4200
99.2k
    return bmap;
4201
21.9k
4202
21.9k
  total = isl_basic_map_total_dim(bmap);
4203
21.9k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4204
21.9k
4205
21.9k
  off = 0;
4206
87.9k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t65.9k
) {
4207
65.9k
    unsigned size = isl_space_dim(bmap->dim, t);
4208
65.9k
    if (t == type) {
4209
21.9k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4210
21.9k
              0, first, off);
4211
21.9k
      off += first;
4212
21.9k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4213
21.9k
              first, n, total - bmap->n_div - n);
4214
21.9k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4215
21.9k
              first + n, size - (first + n), off);
4216
21.9k
      off += size - (first + n);
4217
43.9k
    } else {
4218
43.9k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4219
43.9k
      off += size;
4220
43.9k
    }
4221
65.9k
  }
4222
21.9k
  isl_dim_map_div(dim_map, bmap, off + n);
4223
21.9k
4224
21.9k
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4225
21.9k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4226
21.9k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4227
21.9k
  return res;
4228
21.9k
}
4229
4230
/* Insert "n" rows in the divs of "bmap".
4231
 *
4232
 * The number of columns is not changed, which means that the last
4233
 * dimensions of "bmap" are being reintepreted as the new divs.
4234
 * The space of "bmap" is not adjusted, however, which means
4235
 * that "bmap" is left in an inconsistent state.  Removing "n" dimensions
4236
 * from the space of "bmap" is the responsibility of the caller.
4237
 */
4238
static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap,
4239
  int n)
4240
121k
{
4241
121k
  int i;
4242
121k
  size_t row_size;
4243
121k
  isl_int **new_div;
4244
121k
  isl_int *old;
4245
121k
4246
121k
  bmap = isl_basic_map_cow(bmap);
4247
121k
  if (!bmap)
4248
0
    return NULL;
4249
121k
4250
121k
  row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + bmap->extra;
4251
121k
  old = bmap->block2.data;
4252
121k
  bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
4253
121k
          (bmap->extra + n) * (1 + row_size));
4254
121k
  if (!bmap->block2.data)
4255
0
    return isl_basic_map_free(bmap);
4256
121k
  new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
4257
121k
  if (!new_div)
4258
0
    return isl_basic_map_free(bmap);
4259
342k
  
for (i = 0; 121k
i < n;
++i220k
) {
4260
220k
    new_div[i] = bmap->block2.data +
4261
220k
        (bmap->extra + i) * (1 + row_size);
4262
220k
    isl_seq_clr(new_div[i], 1 + row_size);
4263
220k
  }
4264
128k
  for (i = 0; i < bmap->extra; 
++i7.51k
)
4265
7.51k
    new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
4266
121k
  free(bmap->div);
4267
121k
  bmap->div = new_div;
4268
121k
  bmap->n_div += n;
4269
121k
  bmap->extra += n;
4270
121k
4271
121k
  return bmap;
4272
121k
}
4273
4274
/* Drop constraints from "bmap" that only involve the variables
4275
 * of "type" in the range [first, first + n] that are not related
4276
 * to any of the variables outside that interval.
4277
 * These constraints cannot influence the values for the variables
4278
 * outside the interval, except in case they cause "bmap" to be empty.
4279
 * Only drop the constraints if "bmap" is known to be non-empty.
4280
 */
4281
static __isl_give isl_basic_map *drop_irrelevant_constraints(
4282
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
4283
  unsigned first, unsigned n)
4284
121k
{
4285
121k
  int i;
4286
121k
  int *groups;
4287
121k
  unsigned dim, n_div;
4288
121k
  isl_bool non_empty;
4289
121k
4290
121k
  non_empty = isl_basic_map_plain_is_non_empty(bmap);
4291
121k
  if (non_empty < 0)
4292
0
    return isl_basic_map_free(bmap);
4293
121k
  if (!non_empty)
4294
65.8k
    return bmap;
4295
55.4k
4296
55.4k
  dim = isl_basic_map_dim(bmap, isl_dim_all);
4297
55.4k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
4298
55.4k
  groups = isl_calloc_array(isl_basic_map_get_ctx(bmap), int, dim);
4299
55.4k
  if (!groups)
4300
0
    return isl_basic_map_free(bmap);
4301
55.4k
  first += isl_basic_map_offset(bmap, type) - 1;
4302
262k
  for (i = 0; i < first; 
++i206k
)
4303
206k
    groups[i] = -1;
4304
77.0k
  for (i = first + n; i < dim - n_div; 
++i21.6k
)
4305
21.6k
    groups[i] = -1;
4306
55.4k
4307
55.4k
  bmap = isl_basic_map_drop_unrelated_constraints(bmap, groups);
4308
55.4k
4309
55.4k
  return bmap;
4310
55.4k
}
4311
4312
/* Turn the n dimensions of type type, starting at first
4313
 * into existentially quantified variables.
4314
 *
4315
 * If a subset of the projected out variables are unrelated
4316
 * to any of the variables that remain, then the constraints
4317
 * involving this subset are simply dropped first.
4318
 */
4319
__isl_give isl_basic_map *isl_basic_map_project_out(
4320
    __isl_take isl_basic_map *bmap,
4321
    enum isl_dim_type type, unsigned first, unsigned n)
4322
149k
{
4323
149k
  isl_bool empty;
4324
149k
4325
149k
  if (n == 0)
4326
28.3k
    return basic_map_space_reset(bmap, type);
4327
121k
  if (type == isl_dim_div)
4328
121k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4329
121k
      "cannot project out existentially quantified variables",
4330
121k
      return isl_basic_map_free(bmap));
4331
121k
4332
121k
  empty = isl_basic_map_plain_is_empty(bmap);
4333
121k
  if (empty < 0)
4334
0
    return isl_basic_map_free(bmap);
4335
121k
  if (empty)
4336
1.60k
    bmap = isl_basic_map_set_to_empty(bmap);
4337
121k
4338
121k
  bmap = drop_irrelevant_constraints(bmap, type, first, n);
4339
121k
  if (!bmap)
4340
0
    return NULL;
4341
121k
4342
121k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
4343
121k
    
return isl_basic_map_remove_dims(bmap, type, first, n)39
;
4344
121k
4345
121k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
4346
0
    return isl_basic_map_free(bmap);
4347
121k
4348
121k
  bmap = move_last(bmap, type, first, n);
4349
121k
  bmap = isl_basic_map_cow(bmap);
4350
121k
  bmap = insert_div_rows(bmap, n);
4351
121k
  if (!bmap)
4352
0
    return NULL;
4353
121k
4354
121k
  bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
4355
121k
  if (!bmap->dim)
4356
0
    goto error;
4357
121k
  bmap = isl_basic_map_simplify(bmap);
4358
121k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4359
121k
  return isl_basic_map_finalize(bmap);
4360
0
error:
4361
0
  isl_basic_map_free(bmap);
4362
0
  return NULL;
4363
121k
}
4364
4365
/* Turn the n dimensions of type type, starting at first
4366
 * into existentially quantified variables.
4367
 */
4368
struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
4369
    enum isl_dim_type type, unsigned first, unsigned n)
4370
19.9k
{
4371
19.9k
  return bset_from_bmap(isl_basic_map_project_out(bset_to_bmap(bset),
4372
19.9k
              type, first, n));
4373
19.9k
}
4374
4375
/* Turn the n dimensions of type type, starting at first
4376
 * into existentially quantified variables.
4377
 */
4378
__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
4379
    enum isl_dim_type type, unsigned first, unsigned n)
4380
106k
{
4381
106k
  int i;
4382
106k
4383
106k
  if (n == 0)
4384
40.8k
    return map_space_reset(map, type);
4385
66.0k
4386
66.0k
  if (isl_map_check_range(map, type, first, n) < 0)
4387
0
    return isl_map_free(map);
4388
66.0k
4389
66.0k
  map = isl_map_cow(map);
4390
66.0k
  if (!map)
4391
0
    return NULL;
4392
66.0k
4393
66.0k
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
4394
66.0k
  if (!map->dim)
4395
0
    goto error;
4396
66.0k
4397
109k
  
for (i = 0; 66.0k
i < map->n;
++i43.9k
) {
4398
43.9k
    map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
4399
43.9k
    if (!map->p[i])
4400
0
      goto error;
4401
43.9k
  }
4402
66.0k
4403
66.0k
  return map;
4404
0
error:
4405
0
  isl_map_free(map);
4406
0
  return NULL;
4407
66.0k
}
4408
4409
/* Turn all the dimensions of type "type", except the "n" starting at "first"
4410
 * into existentially quantified variables.
4411
 */
4412
__isl_give isl_map *isl_map_project_onto(__isl_take isl_map *map,
4413
  enum isl_dim_type type, unsigned first, unsigned n)
4414
0
{
4415
0
  unsigned dim;
4416
0
4417
0
  if (isl_map_check_range(map, type, first, n) < 0)
4418
0
    return isl_map_free(map);
4419
0
  dim = isl_map_dim(map, type);
4420
0
  map = isl_map_project_out(map, type, first + n, dim - (first + n));
4421
0
  map = isl_map_project_out(map, type, 0, first);
4422
0
  return map;
4423
0
}
4424
4425
/* Turn the n dimensions of type type, starting at first
4426
 * into existentially quantified variables.
4427
 */
4428
__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
4429
    enum isl_dim_type type, unsigned first, unsigned n)
4430
23.0k
{
4431
23.0k
  return set_from_map(isl_map_project_out(set_to_map(set),
4432
23.0k
            type, first, n));
4433
23.0k
}
4434
4435
/* Return a map that projects the elements in "set" onto their
4436
 * "n" set dimensions starting at "first".
4437
 * "type" should be equal to isl_dim_set.
4438
 */
4439
__isl_give isl_map *isl_set_project_onto_map(__isl_take isl_set *set,
4440
  enum isl_dim_type type, unsigned first, unsigned n)
4441
363
{
4442
363
  int i;
4443
363
  int dim;
4444
363
  isl_map *map;
4445
363
4446
363
  if (!set)
4447
0
    return NULL;
4448
363
  if (type != isl_dim_set)
4449
363
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4450
363
      "only set dimensions can be projected out", goto error);
4451
363
  dim = isl_set_dim(set, isl_dim_set);
4452
363
  if (first + n > dim || first + n < first)
4453
363
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4454
363
      "index out of bounds", goto error);
4455
363
4456
363
  map = isl_map_from_domain(set);
4457
363
  map = isl_map_add_dims(map, isl_dim_out, n);
4458
726
  for (i = 0; i < n; 
++i363
)
4459
363
    map = isl_map_equate(map, isl_dim_in, first + i,
4460
363
          isl_dim_out, i);
4461
363
  return map;
4462
0
error:
4463
0
  isl_set_free(set);
4464
0
  return NULL;
4465
363
}
4466
4467
static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
4468
103k
{
4469
103k
  int i, j;
4470
103k
4471
290k
  for (i = 0; i < n; 
++i187k
) {
4472
187k
    j = isl_basic_map_alloc_div(bmap);
4473
187k
    if (j < 0)
4474
0
      goto error;
4475
187k
    isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
4476
187k
  }
4477
103k
  return bmap;
4478
0
error:
4479
0
  isl_basic_map_free(bmap);
4480
0
  return NULL;
4481
103k
}
4482
4483
struct isl_basic_map *isl_basic_map_apply_range(
4484
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4485
100k
{
4486
100k
  isl_space *dim_result = NULL;
4487
100k
  struct isl_basic_map *bmap;
4488
100k
  unsigned n_in, n_out, n, nparam, total, pos;
4489
100k
  struct isl_dim_map *dim_map1, *dim_map2;
4490
100k
4491
100k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4492
0
    goto error;
4493
100k
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_out,
4494
100k
            bmap2->dim, isl_dim_in))
4495
100k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4496
100k
      "spaces don't match", goto error);
4497
100k
4498
100k
  dim_result = isl_space_join(isl_space_copy(bmap1->dim),
4499
100k
          isl_space_copy(bmap2->dim));
4500
100k
4501
100k
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4502
100k
  n_out = isl_basic_map_dim(bmap2, isl_dim_out);
4503
100k
  n = isl_basic_map_dim(bmap1, isl_dim_out);
4504
100k
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4505
100k
4506
100k
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
4507
100k
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4508
100k
  dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
4509
100k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4510
100k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
4511
100k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4512
100k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
4513
100k
  isl_dim_map_div(dim_map1, bmap1, pos += n_out);
4514
100k
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4515
100k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4516
100k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4517
100k
4518
100k
  bmap = isl_basic_map_alloc_space(dim_result,
4519
100k
      bmap1->n_div + bmap2->n_div + n,
4520
100k
      bmap1->n_eq + bmap2->n_eq,
4521
100k
      bmap1->n_ineq + bmap2->n_ineq);
4522
100k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4523
100k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4524
100k
  bmap = add_divs(bmap, n);
4525
100k
  bmap = isl_basic_map_simplify(bmap);
4526
100k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4527
100k
  return isl_basic_map_finalize(bmap);
4528
0
error:
4529
0
  isl_basic_map_free(bmap1);
4530
0
  isl_basic_map_free(bmap2);
4531
0
  return NULL;
4532
100k
}
4533
4534
struct isl_basic_set *isl_basic_set_apply(
4535
    struct isl_basic_set *bset, struct isl_basic_map *bmap)
4536
4.41k
{
4537
4.41k
  if (!bset || !bmap)
4538
0
    goto error;
4539
4.41k
4540
4.41k
  isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
4541
4.41k
        goto error);
4542
4.41k
4543
4.41k
  return bset_from_bmap(isl_basic_map_apply_range(bset_to_bmap(bset),
4544
4.41k
              bmap));
4545
0
error:
4546
0
  isl_basic_set_free(bset);
4547
0
  isl_basic_map_free(bmap);
4548
0
  return NULL;
4549
4.41k
}
4550
4551
struct isl_basic_map *isl_basic_map_apply_domain(
4552
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4553
0
{
4554
0
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4555
0
    goto error;
4556
0
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_in,
4557
0
          bmap2->dim, isl_dim_in))
4558
0
    isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4559
0
      "spaces don't match", goto error);
4560
0
4561
0
  bmap1 = isl_basic_map_reverse(bmap1);
4562
0
  bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
4563
0
  return isl_basic_map_reverse(bmap1);
4564
0
error:
4565
0
  isl_basic_map_free(bmap1);
4566
0
  isl_basic_map_free(bmap2);
4567
0
  return NULL;
4568
0
}
4569
4570
/* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
4571
 * A \cap B -> f(A) + f(B)
4572
 */
4573
__isl_give isl_basic_map *isl_basic_map_sum(__isl_take isl_basic_map *bmap1,
4574
  __isl_take isl_basic_map *bmap2)
4575
24
{
4576
24
  unsigned n_in, n_out, nparam, total, pos;
4577
24
  struct isl_basic_map *bmap = NULL;
4578
24
  struct isl_dim_map *dim_map1, *dim_map2;
4579
24
  int i;
4580
24
4581
24
  if (!bmap1 || !bmap2)
4582
0
    goto error;
4583
24
4584
24
  isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim),
4585
24
    goto error);
4586
24
4587
24
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4588
24
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4589
24
  n_out = isl_basic_map_dim(bmap1, isl_dim_out);
4590
24
4591
24
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
4592
24
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4593
24
  dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
4594
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4595
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
4596
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4597
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4598
24
  isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
4599
24
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4600
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4601
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
4602
24
4603
24
  bmap = isl_basic_map_alloc_space(isl_space_copy(bmap1->dim),
4604
24
      bmap1->n_div + bmap2->n_div + 2 * n_out,
4605
24
      bmap1->n_eq + bmap2->n_eq + n_out,
4606
24
      bmap1->n_ineq + bmap2->n_ineq);
4607
48
  for (i = 0; i < n_out; 
++i24
) {
4608
24
    int j = isl_basic_map_alloc_equality(bmap);
4609
24
    if (j < 0)
4610
0
      goto error;
4611
24
    isl_seq_clr(bmap->eq[j], 1+total);
4612
24
    isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
4613
24
    isl_int_set_si(bmap->eq[j][1+pos+i], 1);
4614
24
    isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
4615
24
  }
4616
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4617
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4618
24
  bmap = add_divs(bmap, 2 * n_out);
4619
24
4620
24
  bmap = isl_basic_map_simplify(bmap);
4621
24
  return isl_basic_map_finalize(bmap);
4622
0
error:
4623
0
  isl_basic_map_free(bmap);
4624
0
  isl_basic_map_free(bmap1);
4625
0
  isl_basic_map_free(bmap2);
4626
0
  return NULL;
4627
24
}
4628
4629
/* Given two maps A -> f(A) and B -> g(B), construct a map
4630
 * A \cap B -> f(A) + f(B)
4631
 */
4632
__isl_give isl_map *isl_map_sum(__isl_take isl_map *map1,
4633
  __isl_take isl_map *map2)
4634
24
{
4635
24
  struct isl_map *result;
4636
24
  int i, j;
4637
24
4638
24
  if (!map1 || !map2)
4639
0
    goto error;
4640
24
4641
24
  isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
4642
24
4643
24
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
4644
24
        map1->n * map2->n, 0);
4645
24
  if (!result)
4646
0
    goto error;
4647
48
  
for (i = 0; 24
i < map1->n;
++i24
)
4648
48
    
for (j = 0; 24
j < map2->n;
++j24
) {
4649
24
      struct isl_basic_map *part;
4650
24
      part = isl_basic_map_sum(
4651
24
            isl_basic_map_copy(map1->p[i]),
4652
24
            isl_basic_map_copy(map2->p[j]));
4653
24
      if (isl_basic_map_is_empty(part))
4654
0
        isl_basic_map_free(part);
4655
24
      else
4656
24
        result = isl_map_add_basic_map(result, part);
4657
24
      if (!result)
4658
0
        goto error;
4659
24
    }
4660
24
  isl_map_free(map1);
4661
24
  isl_map_free(map2);
4662
24
  return result;
4663
0
error:
4664
0
  isl_map_free(map1);
4665
0
  isl_map_free(map2);
4666
0
  return NULL;
4667
24
}
4668
4669
__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
4670
  __isl_take isl_set *set2)
4671
0
{
4672
0
  return set_from_map(isl_map_sum(set_to_map(set1), set_to_map(set2)));
4673
0
}
4674
4675
/* Given a basic map A -> f(A), construct A -> -f(A).
4676
 */
4677
__isl_give isl_basic_map *isl_basic_map_neg(__isl_take isl_basic_map *bmap)
4678
1
{
4679
1
  int i, j;
4680
1
  unsigned off, n;
4681
1
4682
1
  bmap = isl_basic_map_cow(bmap);
4683
1
  if (!bmap)
4684
0
    return NULL;
4685
1
4686
1
  n = isl_basic_map_dim(bmap, isl_dim_out);
4687
1
  off = isl_basic_map_offset(bmap, isl_dim_out);
4688
2
  for (i = 0; i < bmap->n_eq; 
++i1
)
4689
2
    
for (j = 0; 1
j < n;
++j1
)
4690
1
      isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
4691
3
  for (i = 0; i < bmap->n_ineq; 
++i2
)
4692
4
    
for (j = 0; 2
j < n;
++j2
)
4693
2
      isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
4694
1
  for (i = 0; i < bmap->n_div; 
++i0
)
4695
0
    for (j = 0; j < n; ++j)
4696
0
      isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
4697
1
  bmap = isl_basic_map_gauss(bmap, NULL);
4698
1
  return isl_basic_map_finalize(bmap);
4699
1
}
4700
4701
__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset)
4702
0
{
4703
0
  return isl_basic_map_neg(bset);
4704
0
}
4705
4706
/* Given a map A -> f(A), construct A -> -f(A).
4707
 */
4708
__isl_give isl_map *isl_map_neg(__isl_take isl_map *map)
4709
1
{
4710
1
  int i;
4711
1
4712
1
  map = isl_map_cow(map);
4713
1
  if (!map)
4714
0
    return NULL;
4715
1
4716
2
  
for (i = 0; 1
i < map->n;
++i1
) {
4717
1
    map->p[i] = isl_basic_map_neg(map->p[i]);
4718
1
    if (!map->p[i])
4719
0
      goto error;
4720
1
  }
4721
1
4722
1
  return map;
4723
0
error:
4724
0
  isl_map_free(map);
4725
0
  return NULL;
4726
1
}
4727
4728
__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
4729
0
{
4730
0
  return set_from_map(isl_map_neg(set_to_map(set)));
4731
0
}
4732
4733
/* Given a basic map A -> f(A) and an integer d, construct a basic map
4734
 * A -> floor(f(A)/d).
4735
 */
4736
__isl_give isl_basic_map *isl_basic_map_floordiv(__isl_take isl_basic_map *bmap,
4737
    isl_int d)
4738
3.02k
{
4739
3.02k
  unsigned n_in, n_out, nparam, total, pos;
4740
3.02k
  struct isl_basic_map *result = NULL;
4741
3.02k
  struct isl_dim_map *dim_map;
4742
3.02k
  int i;
4743
3.02k
4744
3.02k
  if (!bmap)
4745
0
    return NULL;
4746
3.02k
4747
3.02k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4748
3.02k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4749
3.02k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4750
3.02k
4751
3.02k
  total = nparam + n_in + n_out + bmap->n_div + n_out;
4752
3.02k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4753
3.02k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
4754
3.02k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
4755
3.02k
  isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
4756
3.02k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
4757
3.02k
4758
3.02k
  result = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
4759
3.02k
      bmap->n_div + n_out,
4760
3.02k
      bmap->n_eq, bmap->n_ineq + 2 * n_out);
4761
3.02k
  result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map);
4762
3.02k
  result = add_divs(result, n_out);
4763
6.06k
  for (i = 0; i < n_out; 
++i3.04k
) {
4764
3.04k
    int j;
4765
3.04k
    j = isl_basic_map_alloc_inequality(result);
4766
3.04k
    if (j < 0)
4767
0
      goto error;
4768
3.04k
    isl_seq_clr(result->ineq[j], 1+total);
4769
3.04k
    isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
4770
3.04k
    isl_int_set_si(result->ineq[j][1+pos+i], 1);
4771
3.04k
    j = isl_basic_map_alloc_inequality(result);
4772
3.04k
    if (j < 0)
4773
0
      goto error;
4774
3.04k
    isl_seq_clr(result->ineq[j], 1+total);
4775
3.04k
    isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
4776
3.04k
    isl_int_set_si(result->ineq[j][1+pos+i], -1);
4777
3.04k
    isl_int_sub_ui(result->ineq[j][0], d, 1);
4778
3.04k
  }
4779
3.02k
4780
3.02k
  result = isl_basic_map_simplify(result);
4781
3.02k
  return isl_basic_map_finalize(result);
4782
0
error:
4783
0
  isl_basic_map_free(result);
4784
0
  return NULL;
4785
3.02k
}
4786
4787
/* Given a map A -> f(A) and an integer d, construct a map
4788
 * A -> floor(f(A)/d).
4789
 */
4790
__isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
4791
2.96k
{
4792
2.96k
  int i;
4793
2.96k
4794
2.96k
  map = isl_map_cow(map);
4795
2.96k
  if (!map)
4796
0
    return NULL;
4797
2.96k
4798
2.96k
  ISL_F_CLR(map, ISL_MAP_DISJOINT);
4799
5.98k
  for (i = 0; i < map->n; 
++i3.02k
) {
4800
3.02k
    map->p[i] = isl_basic_map_floordiv(map->p[i], d);
4801
3.02k
    if (!map->p[i])
4802
0
      goto error;
4803
3.02k
  }
4804
2.96k
  map = isl_map_unmark_normalized(map);
4805
2.96k
4806
2.96k
  return map;
4807
0
error:
4808
0
  isl_map_free(map);
4809
0
  return NULL;
4810
2.96k
}
4811
4812
/* Given a map A -> f(A) and an integer d, construct a map
4813
 * A -> floor(f(A)/d).
4814
 */
4815
__isl_give isl_map *isl_map_floordiv_val(__isl_take isl_map *map,
4816
  __isl_take isl_val *d)
4817
2.96k
{
4818
2.96k
  if (!map || !d)
4819
0
    goto error;
4820
2.96k
  if (!isl_val_is_int(d))
4821
2.96k
    
isl_die0
(isl_val_get_ctx(d), isl_error_invalid,
4822
2.96k
      "expecting integer denominator", goto error);
4823
2.96k
  map = isl_map_floordiv(map, d->n);
4824
2.96k
  isl_val_free(d);
4825
2.96k
  return map;
4826
0
error:
4827
0
  isl_map_free(map);
4828
0
  isl_val_free(d);
4829
0
  return NULL;
4830
2.96k
}
4831
4832
static __isl_give isl_basic_map *var_equal(__isl_take isl_basic_map *bmap,
4833
  unsigned pos)
4834
14.1k
{
4835
14.1k
  int i;
4836
14.1k
  unsigned nparam;
4837
14.1k
  unsigned n_in;
4838
14.1k
4839
14.1k
  i = isl_basic_map_alloc_equality(bmap);
4840
14.1k
  if (i < 0)
4841
0
    goto error;
4842
14.1k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4843
14.1k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4844
14.1k
  isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
4845
14.1k
  isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
4846
14.1k
  isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
4847
14.1k
  return isl_basic_map_finalize(bmap);
4848
0
error:
4849
0
  isl_basic_map_free(bmap);
4850
0
  return NULL;
4851
14.1k
}
4852
4853
/* Add a constraint to "bmap" expressing i_pos < o_pos
4854
 */
4855
static __isl_give isl_basic_map *var_less(__isl_take isl_basic_map *bmap,
4856
  unsigned pos)
4857
1.47k
{
4858
1.47k
  int i;
4859
1.47k
  unsigned nparam;
4860
1.47k
  unsigned n_in;
4861
1.47k
4862
1.47k
  i = isl_basic_map_alloc_inequality(bmap);
4863
1.47k
  if (i < 0)
4864
0
    goto error;
4865
1.47k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4866
1.47k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4867
1.47k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4868
1.47k
  isl_int_set_si(bmap->ineq[i][0], -1);
4869
1.47k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4870
1.47k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4871
1.47k
  return isl_basic_map_finalize(bmap);
4872
0
error:
4873
0
  isl_basic_map_free(bmap);
4874
0
  return NULL;
4875
1.47k
}
4876
4877
/* Add a constraint to "bmap" expressing i_pos <= o_pos
4878
 */
4879
static __isl_give isl_basic_map *var_less_or_equal(
4880
  __isl_take isl_basic_map *bmap, unsigned pos)
4881
2.05k
{
4882
2.05k
  int i;
4883
2.05k
  unsigned nparam;
4884
2.05k
  unsigned n_in;
4885
2.05k
4886
2.05k
  i = isl_basic_map_alloc_inequality(bmap);
4887
2.05k
  if (i < 0)
4888
0
    goto error;
4889
2.05k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4890
2.05k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4891
2.05k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4892
2.05k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4893
2.05k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4894
2.05k
  return isl_basic_map_finalize(bmap);
4895
0
error:
4896
0
  isl_basic_map_free(bmap);
4897
0
  return NULL;
4898
2.05k
}
4899
4900
/* Add a constraint to "bmap" expressing i_pos > o_pos
4901
 */
4902
static __isl_give isl_basic_map *var_more(__isl_take isl_basic_map *bmap,
4903
  unsigned pos)
4904
16.6k
{
4905
16.6k
  int i;
4906
16.6k
  unsigned nparam;
4907
16.6k
  unsigned n_in;
4908
16.6k
4909
16.6k
  i = isl_basic_map_alloc_inequality(bmap);
4910
16.6k
  if (i < 0)
4911
0
    goto error;
4912
16.6k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4913
16.6k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4914
16.6k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4915
16.6k
  isl_int_set_si(bmap->ineq[i][0], -1);
4916
16.6k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4917
16.6k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4918
16.6k
  return isl_basic_map_finalize(bmap);
4919
0
error:
4920
0
  isl_basic_map_free(bmap);
4921
0
  return NULL;
4922
16.6k
}
4923
4924
/* Add a constraint to "bmap" expressing i_pos >= o_pos
4925
 */
4926
static __isl_give isl_basic_map *var_more_or_equal(
4927
  __isl_take isl_basic_map *bmap, unsigned pos)
4928
1.47k
{
4929
1.47k
  int i;
4930
1.47k
  unsigned nparam;
4931
1.47k
  unsigned n_in;
4932
1.47k
4933
1.47k
  i = isl_basic_map_alloc_inequality(bmap);
4934
1.47k
  if (i < 0)
4935
0
    goto error;
4936
1.47k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4937
1.47k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4938
1.47k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4939
1.47k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4940
1.47k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4941
1.47k
  return isl_basic_map_finalize(bmap);
4942
0
error:
4943
0
  isl_basic_map_free(bmap);
4944
0
  return NULL;
4945
1.47k
}
4946
4947
__isl_give isl_basic_map *isl_basic_map_equal(
4948
  __isl_take isl_space *dim, unsigned n_equal)
4949
2.84k
{
4950
2.84k
  int i;
4951
2.84k
  struct isl_basic_map *bmap;
4952
2.84k
  bmap = isl_basic_map_alloc_space(dim, 0, n_equal, 0);
4953
2.84k
  if (!bmap)
4954
0
    return NULL;
4955
5.10k
  
for (i = 0; 2.84k
i < n_equal &&
bmap2.25k
;
++i2.25k
)
4956
2.25k
    bmap = var_equal(bmap, i);
4957
2.84k
  return isl_basic_map_finalize(bmap);
4958
2.84k
}
4959
4960
/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
4961
 */
4962
__isl_give isl_basic_map *isl_basic_map_less_at(__isl_take isl_space *dim,
4963
  unsigned pos)
4964
1.47k
{
4965
1.47k
  int i;
4966
1.47k
  struct isl_basic_map *bmap;
4967
1.47k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4968
1.47k
  if (!bmap)
4969
0
    return NULL;
4970
2.30k
  
for (i = 0; 1.47k
i < pos &&
bmap833
;
++i833
)
4971
833
    bmap = var_equal(bmap, i);
4972
1.47k
  if (bmap)
4973
1.47k
    bmap = var_less(bmap, pos);
4974
1.47k
  return isl_basic_map_finalize(bmap);
4975
1.47k
}
4976
4977
/* Return a relation on "dim" expressing i_[0..pos] <<= o_[0..pos]
4978
 */
4979
__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
4980
  __isl_take isl_space *dim, unsigned pos)
4981
2.05k
{
4982
2.05k
  int i;
4983
2.05k
  isl_basic_map *bmap;
4984
2.05k
4985
2.05k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4986
3.14k
  for (i = 0; i < pos; 
++i1.08k
)
4987
1.08k
    bmap = var_equal(bmap, i);
4988
2.05k
  bmap = var_less_or_equal(bmap, pos);
4989
2.05k
  return isl_basic_map_finalize(bmap);
4990
2.05k
}
4991
4992
/* Return a relation on "dim" expressing i_pos > o_pos
4993
 */
4994
__isl_give isl_basic_map *isl_basic_map_more_at(__isl_take isl_space *dim,
4995
  unsigned pos)
4996
16.6k
{
4997
16.6k
  int i;
4998
16.6k
  struct isl_basic_map *bmap;
4999
16.6k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
5000
16.6k
  if (!bmap)
5001
0
    return NULL;
5002
24.1k
  
for (i = 0; 16.6k
i < pos &&
bmap7.57k
;
++i7.57k
)
5003
7.57k
    bmap = var_equal(bmap, i);
5004
16.6k
  if (bmap)
5005
16.6k
    bmap = var_more(bmap, pos);
5006
16.6k
  return isl_basic_map_finalize(bmap);
5007
16.6k
}
5008
5009
/* Return a relation on "dim" expressing i_[0..pos] >>= o_[0..pos]
5010
 */
5011
__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
5012
  __isl_take isl_space *dim, unsigned pos)
5013
1.47k
{
5014
1.47k
  int i;
5015
1.47k
  isl_basic_map *bmap;
5016
1.47k
5017
1.47k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
5018
3.87k
  for (i = 0; i < pos; 
++i2.40k
)
5019
2.40k
    bmap = var_equal(bmap, i);
5020
1.47k
  bmap = var_more_or_equal(bmap, pos);
5021
1.47k
  return isl_basic_map_finalize(bmap);
5022
1.47k
}
5023
5024
static __isl_give isl_map *map_lex_lte_first(__isl_take isl_space *dims,
5025
  unsigned n, int equal)
5026
2.30k
{
5027
2.30k
  struct isl_map *map;
5028
2.30k
  int i;
5029
2.30k
5030
2.30k
  if (n == 0 && 
equal22
)
5031
11
    return isl_map_universe(dims);
5032
2.29k
5033
2.29k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
5034
2.29k
5035
3.54k
  for (i = 0; i + 1 < n; 
++i1.25k
)
5036
1.25k
    map = isl_map_add_basic_map(map,
5037
1.25k
          isl_basic_map_less_at(isl_space_copy(dims), i));
5038
2.29k
  if (n > 0) {
5039
2.28k
    if (equal)
5040
2.05k
      map = isl_map_add_basic_map(map,
5041
2.05k
            isl_basic_map_less_or_equal_at(dims, n - 1));
5042
221
    else
5043
221
      map = isl_map_add_basic_map(map,
5044
221
            isl_basic_map_less_at(dims, n - 1));
5045
2.28k
  } else
5046
11
    isl_space_free(dims);
5047
2.29k
5048
2.29k
  return map;
5049
2.29k
}
5050
5051
static __isl_give isl_map *map_lex_lte(__isl_take isl_space *dims, int equal)
5052
2.22k
{
5053
2.22k
  if (!dims)
5054
5
    return NULL;
5055
2.21k
  return map_lex_lte_first(dims, dims->n_out, equal);
5056
2.21k
}
5057
5058
__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *dim, unsigned n)
5059
73
{
5060
73
  return map_lex_lte_first(dim, n, 0);
5061
73
}
5062
5063
__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *dim, unsigned n)
5064
10
{
5065
10
  return map_lex_lte_first(dim, n, 1);
5066
10
}
5067
5068
__isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_dim)
5069
159
{
5070
159
  return map_lex_lte(isl_space_map_from_set(set_dim), 0);
5071
159
}
5072
5073
__isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_dim)
5074
2.06k
{
5075
2.06k
  return map_lex_lte(isl_space_map_from_set(set_dim), 1);
5076
2.06k
}
5077
5078
static __isl_give isl_map *map_lex_gte_first(__isl_take isl_space *dims,
5079
  unsigned n, int equal)
5080
1.70k
{
5081
1.70k
  struct isl_map *map;
5082
1.70k
  int i;
5083
1.70k
5084
1.70k
  if (n == 0 && 
equal0
)
5085
0
    return isl_map_universe(dims);
5086
1.70k
5087
1.70k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
5088
1.70k
5089
4.38k
  for (i = 0; i + 1 < n; 
++i2.67k
)
5090
2.67k
    map = isl_map_add_basic_map(map,
5091
2.67k
          isl_basic_map_more_at(isl_space_copy(dims), i));
5092
1.70k
  if (n > 0) {
5093
1.70k
    if (equal)
5094
1.47k
      map = isl_map_add_basic_map(map,
5095
1.47k
            isl_basic_map_more_or_equal_at(dims, n - 1));
5096
238
    else
5097
238
      map = isl_map_add_basic_map(map,
5098
238
            isl_basic_map_more_at(dims, n - 1));
5099
1.70k
  } else
5100
0
    isl_space_free(dims);
5101
1.70k
5102
1.70k
  return map;
5103
1.70k
}
5104
5105
static __isl_give isl_map *map_lex_gte(__isl_take isl_space *dims, int equal)
5106
1.71k
{
5107
1.71k
  if (!dims)
5108
2
    return NULL;
5109
1.70k
  return map_lex_gte_first(dims, dims->n_out, equal);
5110
1.70k
}
5111
5112
__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *dim, unsigned n)
5113
0
{
5114
0
  return map_lex_gte_first(dim, n, 0);
5115
0
}
5116
5117
__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *dim, unsigned n)
5118
0
{
5119
0
  return map_lex_gte_first(dim, n, 1);
5120
0
}
5121
5122
__isl_give isl_map *isl_map_lex_gt(__isl_take isl_space *set_dim)
5123
240
{
5124
240
  return map_lex_gte(isl_space_map_from_set(set_dim), 0);
5125
240
}
5126
5127
__isl_give isl_map *isl_map_lex_ge(__isl_take isl_space *set_dim)
5128
1.47k
{
5129
1.47k
  return map_lex_gte(isl_space_map_from_set(set_dim), 1);
5130
1.47k
}
5131
5132
__isl_give isl_map *isl_set_lex_le_set(__isl_take isl_set *set1,
5133
  __isl_take isl_set *set2)
5134
180
{
5135
180
  isl_map *map;
5136
180
  map = isl_map_lex_le(isl_set_get_space(set1));
5137
180
  map = isl_map_intersect_domain(map, set1);
5138
180
  map = isl_map_intersect_range(map, set2);
5139
180
  return map;
5140
180
}
5141
5142
__isl_give isl_map *isl_set_lex_lt_set(__isl_take isl_set *set1,
5143
  __isl_take isl_set *set2)
5144
1
{
5145
1
  isl_map *map;
5146
1
  map = isl_map_lex_lt(isl_set_get_space(set1));
5147
1
  map = isl_map_intersect_domain(map, set1);
5148
1
  map = isl_map_intersect_range(map, set2);
5149
1
  return map;
5150
1
}
5151
5152
__isl_give isl_map *isl_set_lex_ge_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_ge(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_set_lex_gt_set(__isl_take isl_set *set1,
5163
  __isl_take isl_set *set2)
5164
0
{
5165
0
  isl_map *map;
5166
0
  map = isl_map_lex_gt(isl_set_get_space(set1));
5167
0
  map = isl_map_intersect_domain(map, set1);
5168
0
  map = isl_map_intersect_range(map, set2);
5169
0
  return map;
5170
0
}
5171
5172
__isl_give isl_map *isl_map_lex_le_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_le(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_lt_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_lt(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_ge_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_ge(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
__isl_give isl_map *isl_map_lex_gt_map(__isl_take isl_map *map1,
5203
  __isl_take isl_map *map2)
5204
0
{
5205
0
  isl_map *map;
5206
0
  map = isl_map_lex_gt(isl_space_range(isl_map_get_space(map1)));
5207
0
  map = isl_map_apply_domain(map, isl_map_reverse(map1));
5208
0
  map = isl_map_apply_range(map, isl_map_reverse(map2));
5209
0
  return map;
5210
0
}
5211
5212
/* For a div d = floor(f/m), add the constraint
5213
 *
5214
 *    f - m d >= 0
5215
 */
5216
static isl_stat add_upper_div_constraint(__isl_keep isl_basic_map *bmap,
5217
  unsigned pos, isl_int *div)
5218
52.1k
{
5219
52.1k
  int i;
5220
52.1k
  unsigned total = isl_basic_map_total_dim(bmap);
5221
52.1k
5222
52.1k
  i = isl_basic_map_alloc_inequality(bmap);
5223
52.1k
  if (i < 0)
5224
0
    return isl_stat_error;
5225
52.1k
  isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
5226
52.1k
  isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
5227
52.1k
5228
52.1k
  return isl_stat_ok;
5229
52.1k
}
5230
5231
/* For a div d = floor(f/m), add the constraint
5232
 *
5233
 *    -(f-(m-1)) + m d >= 0
5234
 */
5235
static isl_stat add_lower_div_constraint(__isl_keep isl_basic_map *bmap,
5236
  unsigned pos, isl_int *div)
5237
52.6k
{
5238
52.6k
  int i;
5239
52.6k
  unsigned total = isl_basic_map_total_dim(bmap);
5240
52.6k
5241
52.6k
  i = isl_basic_map_alloc_inequality(bmap);
5242
52.6k
  if (i < 0)
5243
0
    return isl_stat_error;
5244
52.6k
  isl_seq_neg(bmap->ineq[i], div + 1, 1 + total);
5245
52.6k
  isl_int_set(bmap->ineq[i][1 + pos], div[0]);
5246
52.6k
  isl_int_add(bmap->ineq[i][0], bmap->ineq[i][0], bmap->ineq[i][1 + pos]);
5247
52.6k
  isl_int_sub_ui(bmap->ineq[i][0], bmap->ineq[i][0], 1);
5248
52.6k
5249
52.6k
  return isl_stat_ok;
5250
52.6k
}
5251
5252
/* For a div d = floor(f/m), add the constraints
5253
 *
5254
 *    f - m d >= 0
5255
 *    -(f-(m-1)) + m d >= 0
5256
 *
5257
 * Note that the second constraint is the negation of
5258
 *
5259
 *    f - m d >= m
5260
 */
5261
int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
5262
  unsigned pos, isl_int *div)
5263
48.0k
{
5264
48.0k
  if (add_upper_div_constraint(bmap, pos, div) < 0)
5265
0
    return -1;
5266
48.0k
  if (add_lower_div_constraint(bmap, pos, div) < 0)
5267
0
    return -1;
5268
48.0k
  return 0;
5269
48.0k
}
5270
5271
int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
5272
  unsigned pos, isl_int *div)
5273
29
{
5274
29
  return isl_basic_map_add_div_constraints_var(bset_to_bmap(bset),
5275
29
              pos, div);
5276
29
}
5277
5278
int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
5279
48.0k
{
5280
48.0k
  unsigned total = isl_basic_map_total_dim(bmap);
5281
48.0k
  unsigned div_pos = total - bmap->n_div + div;
5282
48.0k
5283
48.0k
  return isl_basic_map_add_div_constraints_var(bmap, div_pos,
5284
48.0k
              bmap->div[div]);
5285
48.0k
}
5286
5287
/* For each known div d = floor(f/m), add the constraints
5288
 *
5289
 *    f - m d >= 0
5290
 *    -(f-(m-1)) + m d >= 0
5291
 *
5292
 * Remove duplicate constraints in case of some these div constraints
5293
 * already appear in "bmap".
5294
 */
5295
__isl_give isl_basic_map *isl_basic_map_add_known_div_constraints(
5296
  __isl_take isl_basic_map *bmap)
5297
448k
{
5298
448k
  unsigned n_div;
5299
448k
5300
448k
  if (!bmap)
5301
0
    return NULL;
5302
448k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
5303
448k
  if (n_div == 0)
5304
444k
    return bmap;
5305
3.49k
5306
3.49k
  bmap = add_known_div_constraints(bmap);
5307
3.49k
  bmap = isl_basic_map_remove_duplicate_constraints(bmap, NULL, 0);
5308
3.49k
  bmap = isl_basic_map_finalize(bmap);
5309
3.49k
  return bmap;
5310
3.49k
}
5311
5312
/* Add the div constraint of sign "sign" for div "div" of "bmap".
5313
 *
5314
 * In particular, if this div is of the form d = floor(f/m),
5315
 * then add the constraint
5316
 *
5317
 *    f - m d >= 0
5318
 *
5319
 * if sign < 0 or the constraint
5320
 *
5321
 *    -(f-(m-1)) + m d >= 0
5322
 *
5323
 * if sign > 0.
5324
 */
5325
int isl_basic_map_add_div_constraint(__isl_keep isl_basic_map *bmap,
5326
  unsigned div, int sign)
5327
8.71k
{
5328
8.71k
  unsigned total;
5329