Coverage Report

Created: 2017-10-03 07:32

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