Coverage Report

Created: 2017-04-29 12:21

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