Coverage Report

Created: 2017-06-23 12:40

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