Coverage Report

Created: 2017-08-21 19:50

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