Coverage Report

Created: 2018-04-23 18:20

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_map.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 * Copyright 2012-2014 Ecole Normale Superieure
5
 * Copyright 2014      INRIA Rocquencourt
6
 * Copyright 2016      INRIA Paris
7
 * Copyright 2016      Sven Verdoolaege
8
 *
9
 * Use of this software is governed by the MIT license
10
 *
11
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
12
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
13
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
14
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
15
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
16
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
17
 * B.P. 105 - 78153 Le Chesnay, France
18
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
19
 * CS 42112, 75589 Paris Cedex 12, France
20
 */
21
22
#include <string.h>
23
#include <isl_ctx_private.h>
24
#include <isl_map_private.h>
25
#include <isl_blk.h>
26
#include <isl/id.h>
27
#include <isl/constraint.h>
28
#include "isl_space_private.h"
29
#include "isl_equalities.h"
30
#include <isl_lp_private.h>
31
#include <isl_seq.h>
32
#include <isl/set.h>
33
#include <isl/map.h>
34
#include <isl_reordering.h>
35
#include "isl_sample.h"
36
#include <isl_sort.h>
37
#include "isl_tab.h"
38
#include <isl/vec.h>
39
#include <isl_mat_private.h>
40
#include <isl_vec_private.h>
41
#include <isl_dim_map.h>
42
#include <isl_local_space_private.h>
43
#include <isl_aff_private.h>
44
#include <isl_options_private.h>
45
#include <isl_morph.h>
46
#include <isl_val_private.h>
47
48
#include <bset_to_bmap.c>
49
#include <bset_from_bmap.c>
50
#include <set_to_map.c>
51
#include <set_from_map.c>
52
53
static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
54
352k
{
55
352k
  switch (type) {
56
352k
  
case isl_dim_param: return dim->nparam8.41k
;
57
352k
  
case isl_dim_in:  return dim->n_in69.0k
;
58
352k
  
case isl_dim_out: return dim->n_out275k
;
59
352k
  
case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out128
;
60
352k
  
default:    return 00
;
61
0
  }
62
0
}
63
64
static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
65
122k
{
66
122k
  switch (type) {
67
122k
  
case isl_dim_param: return 1379
;
68
122k
  
case isl_dim_in:  return 1 + dim->nparam13.7k
;
69
122k
  
case isl_dim_out: return 1 + dim->nparam + dim->n_in107k
;
70
122k
  
default:    return 00
;
71
0
  }
72
0
}
73
74
unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
75
        enum isl_dim_type type)
76
43.7M
{
77
43.7M
  if (!bmap)
78
0
    return 0;
79
43.7M
  switch (type) {
80
43.7M
  
case isl_dim_cst: return 10
;
81
43.7M
  case isl_dim_param:
82
41.3M
  case isl_dim_in:
83
41.3M
  case isl_dim_out: return isl_space_dim(bmap->dim, type);
84
41.3M
  
case isl_dim_div: return bmap->n_div2.09M
;
85
41.3M
  
case isl_dim_all: return isl_basic_map_total_dim(bmap)286k
;
86
41.3M
  
default:    return 00
;
87
0
  }
88
0
}
89
90
/* Return the space of "map".
91
 */
92
__isl_keep isl_space *isl_map_peek_space(__isl_keep const isl_map *map)
93
3.98M
{
94
3.98M
  return map ? 
map->dim3.98M
: NULL;
95
3.98M
}
96
97
unsigned isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
98
197k
{
99
197k
  return map ? n(map->dim, type) : 
00
;
100
197k
}
101
102
unsigned isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
103
155k
{
104
155k
  return set ? n(set->dim, type) : 
00
;
105
155k
}
106
107
unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
108
          enum isl_dim_type type)
109
1.17M
{
110
1.17M
  isl_space *space;
111
1.17M
112
1.17M
  if (!bmap)
113
0
    return 0;
114
1.17M
115
1.17M
  space = bmap->dim;
116
1.17M
  switch (type) {
117
1.17M
  
case isl_dim_cst: return 00
;
118
1.17M
  
case isl_dim_param: return 14.22k
;
119
1.17M
  
case isl_dim_in:  return 1 + space->nparam229k
;
120
1.17M
  
case isl_dim_out: return 1 + space->nparam + space->n_in725k
;
121
1.17M
  case isl_dim_div: return 1 + space->nparam + space->n_in +
122
218k
                space->n_out;
123
1.17M
  
default:    return 00
;
124
0
  }
125
0
}
126
127
unsigned isl_basic_set_offset(__isl_keep isl_basic_set *bset,
128
          enum isl_dim_type type)
129
354
{
130
354
  return isl_basic_map_offset(bset, type);
131
354
}
132
133
static unsigned map_offset(__isl_keep isl_map *map, enum isl_dim_type type)
134
1.76k
{
135
1.76k
  return pos(map->dim, type);
136
1.76k
}
137
138
unsigned isl_basic_set_dim(__isl_keep isl_basic_set *bset,
139
        enum isl_dim_type type)
140
2.76M
{
141
2.76M
  return isl_basic_map_dim(bset, type);
142
2.76M
}
143
144
unsigned isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
145
1.47M
{
146
1.47M
  return isl_basic_set_dim(bset, isl_dim_set);
147
1.47M
}
148
149
unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
150
732k
{
151
732k
  return isl_basic_set_dim(bset, isl_dim_param);
152
732k
}
153
154
unsigned isl_basic_set_total_dim(__isl_keep const isl_basic_set *bset)
155
3.02M
{
156
3.02M
  if (!bset)
157
0
    return 0;
158
3.02M
  return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
159
3.02M
}
160
161
unsigned isl_set_n_dim(__isl_keep isl_set *set)
162
106k
{
163
106k
  return isl_set_dim(set, isl_dim_set);
164
106k
}
165
166
unsigned isl_set_n_param(__isl_keep isl_set *set)
167
560
{
168
560
  return isl_set_dim(set, isl_dim_param);
169
560
}
170
171
unsigned isl_basic_map_n_in(__isl_keep const isl_basic_map *bmap)
172
0
{
173
0
  return bmap ? bmap->dim->n_in : 0;
174
0
}
175
176
unsigned isl_basic_map_n_out(__isl_keep const isl_basic_map *bmap)
177
0
{
178
0
  return bmap ? bmap->dim->n_out : 0;
179
0
}
180
181
unsigned isl_basic_map_n_param(__isl_keep const isl_basic_map *bmap)
182
0
{
183
0
  return bmap ? bmap->dim->nparam : 0;
184
0
}
185
186
unsigned isl_basic_map_n_div(__isl_keep const isl_basic_map *bmap)
187
0
{
188
0
  return bmap ? bmap->n_div : 0;
189
0
}
190
191
unsigned isl_basic_map_total_dim(__isl_keep const isl_basic_map *bmap)
192
52.8M
{
193
52.8M
  return bmap ? isl_space_dim(bmap->dim, isl_dim_all) + bmap->n_div : 
00
;
194
52.8M
}
195
196
unsigned isl_map_n_in(__isl_keep const isl_map *map)
197
0
{
198
0
  return map ? map->dim->n_in : 0;
199
0
}
200
201
unsigned isl_map_n_out(__isl_keep const isl_map *map)
202
0
{
203
0
  return map ? map->dim->n_out : 0;
204
0
}
205
206
unsigned isl_map_n_param(__isl_keep const isl_map *map)
207
0
{
208
0
  return map ? map->dim->nparam : 0;
209
0
}
210
211
/* Return the number of equality constraints in the description of "bmap".
212
 * Return -1 on error.
213
 */
214
int isl_basic_map_n_equality(__isl_keep isl_basic_map *bmap)
215
344k
{
216
344k
  if (!bmap)
217
0
    return -1;
218
344k
  return bmap->n_eq;
219
344k
}
220
221
/* Return the number of equality constraints in the description of "bset".
222
 * Return -1 on error.
223
 */
224
int isl_basic_set_n_equality(__isl_keep isl_basic_set *bset)
225
1.76k
{
226
1.76k
  return isl_basic_map_n_equality(bset_to_bmap(bset));
227
1.76k
}
228
229
/* Return the number of inequality constraints in the description of "bmap".
230
 * Return -1 on error.
231
 */
232
int isl_basic_map_n_inequality(__isl_keep isl_basic_map *bmap)
233
369k
{
234
369k
  if (!bmap)
235
0
    return -1;
236
369k
  return bmap->n_ineq;
237
369k
}
238
239
/* Return the number of inequality constraints in the description of "bset".
240
 * Return -1 on error.
241
 */
242
int isl_basic_set_n_inequality(__isl_keep isl_basic_set *bset)
243
1.73k
{
244
1.73k
  return isl_basic_map_n_inequality(bset_to_bmap(bset));
245
1.73k
}
246
247
/* Do "bmap1" and "bmap2" have the same parameters?
248
 */
249
static isl_bool isl_basic_map_has_equal_params(__isl_keep isl_basic_map *bmap1,
250
  __isl_keep isl_basic_map *bmap2)
251
625k
{
252
625k
  isl_space *space1, *space2;
253
625k
254
625k
  space1 = isl_basic_map_peek_space(bmap1);
255
625k
  space2 = isl_basic_map_peek_space(bmap2);
256
625k
  return isl_space_has_equal_params(space1, space2);
257
625k
}
258
259
/* Do "map1" and "map2" have the same parameters?
260
 */
261
isl_bool isl_map_has_equal_params(__isl_keep isl_map *map1,
262
  __isl_keep isl_map *map2)
263
1.24M
{
264
1.24M
  isl_space *space1, *space2;
265
1.24M
266
1.24M
  space1 = isl_map_peek_space(map1);
267
1.24M
  space2 = isl_map_peek_space(map2);
268
1.24M
  return isl_space_has_equal_params(space1, space2);
269
1.24M
}
270
271
/* Do "map" and "set" have the same parameters?
272
 */
273
static isl_bool isl_map_set_has_equal_params(__isl_keep isl_map *map,
274
  __isl_keep isl_set *set)
275
12.0k
{
276
12.0k
  return isl_map_has_equal_params(map, set_to_map(set));
277
12.0k
}
278
279
isl_bool isl_map_compatible_domain(__isl_keep isl_map *map,
280
  __isl_keep isl_set *set)
281
106k
{
282
106k
  isl_bool m;
283
106k
  if (!map || !set)
284
0
    return isl_bool_error;
285
106k
  m = isl_map_has_equal_params(map, set_to_map(set));
286
106k
  if (m < 0 || !m)
287
0
    return m;
288
106k
  return isl_space_tuple_is_equal(map->dim, isl_dim_in,
289
106k
          set->dim, isl_dim_set);
290
106k
}
291
292
isl_bool isl_basic_map_compatible_domain(__isl_keep isl_basic_map *bmap,
293
  __isl_keep isl_basic_set *bset)
294
75.0k
{
295
75.0k
  isl_bool m;
296
75.0k
  if (!bmap || !bset)
297
0
    return isl_bool_error;
298
75.0k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
299
75.0k
  if (m < 0 || !m)
300
0
    return m;
301
75.0k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_in,
302
75.0k
          bset->dim, isl_dim_set);
303
75.0k
}
304
305
isl_bool isl_map_compatible_range(__isl_keep isl_map *map,
306
  __isl_keep isl_set *set)
307
5.09k
{
308
5.09k
  isl_bool m;
309
5.09k
  if (!map || !set)
310
0
    return isl_bool_error;
311
5.09k
  m = isl_map_has_equal_params(map, set_to_map(set));
312
5.09k
  if (m < 0 || !m)
313
0
    return m;
314
5.09k
  return isl_space_tuple_is_equal(map->dim, isl_dim_out,
315
5.09k
          set->dim, isl_dim_set);
316
5.09k
}
317
318
isl_bool isl_basic_map_compatible_range(__isl_keep isl_basic_map *bmap,
319
  __isl_keep isl_basic_set *bset)
320
6.49k
{
321
6.49k
  isl_bool m;
322
6.49k
  if (!bmap || !bset)
323
0
    return isl_bool_error;
324
6.49k
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
325
6.49k
  if (m < 0 || !m)
326
0
    return m;
327
6.49k
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_out,
328
6.49k
          bset->dim, isl_dim_set);
329
6.49k
}
330
331
isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
332
4.86M
{
333
4.86M
  return bmap ? bmap->ctx : NULL;
334
4.86M
}
335
336
isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
337
237k
{
338
237k
  return bset ? bset->ctx : NULL;
339
237k
}
340
341
isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
342
61.3k
{
343
61.3k
  return map ? map->ctx : NULL;
344
61.3k
}
345
346
isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
347
412k
{
348
412k
  return set ? set->ctx : NULL;
349
412k
}
350
351
/* Return the space of "bmap".
352
 */
353
__isl_keep isl_space *isl_basic_map_peek_space(
354
  __isl_keep const isl_basic_map *bmap)
355
5.77M
{
356
5.77M
  return bmap ? bmap->dim : NULL;
357
5.77M
}
358
359
/* Return the space of "bset".
360
 */
361
__isl_keep isl_space *isl_basic_set_peek_space(__isl_keep isl_basic_set *bset)
362
0
{
363
0
  return isl_basic_map_peek_space(bset_to_bmap(bset));
364
0
}
365
366
__isl_give isl_space *isl_basic_map_get_space(__isl_keep isl_basic_map *bmap)
367
675k
{
368
675k
  return isl_space_copy(isl_basic_map_peek_space(bmap));
369
675k
}
370
371
__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
372
199k
{
373
199k
  return isl_basic_map_get_space(bset_to_bmap(bset));
374
199k
}
375
376
/* Extract the divs in "bmap" as a matrix.
377
 */
378
__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap)
379
78.3k
{
380
78.3k
  int i;
381
78.3k
  isl_ctx *ctx;
382
78.3k
  isl_mat *div;
383
78.3k
  unsigned total;
384
78.3k
  unsigned cols;
385
78.3k
386
78.3k
  if (!bmap)
387
0
    return NULL;
388
78.3k
389
78.3k
  ctx = isl_basic_map_get_ctx(bmap);
390
78.3k
  total = isl_space_dim(bmap->dim, isl_dim_all);
391
78.3k
  cols = 1 + 1 + total + bmap->n_div;
392
78.3k
  div = isl_mat_alloc(ctx, bmap->n_div, cols);
393
78.3k
  if (!div)
394
0
    return NULL;
395
78.3k
396
91.1k
  
for (i = 0; 78.3k
i < bmap->n_div;
++i12.7k
)
397
12.7k
    isl_seq_cpy(div->row[i], bmap->div[i], cols);
398
78.3k
399
78.3k
  return div;
400
78.3k
}
401
402
/* Extract the divs in "bset" as a matrix.
403
 */
404
__isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset)
405
0
{
406
0
  return isl_basic_map_get_divs(bset);
407
0
}
408
409
__isl_give isl_local_space *isl_basic_map_get_local_space(
410
  __isl_keep isl_basic_map *bmap)
411
59.2k
{
412
59.2k
  isl_mat *div;
413
59.2k
414
59.2k
  if (!bmap)
415
0
    return NULL;
416
59.2k
417
59.2k
  div = isl_basic_map_get_divs(bmap);
418
59.2k
  return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div);
419
59.2k
}
420
421
__isl_give isl_local_space *isl_basic_set_get_local_space(
422
  __isl_keep isl_basic_set *bset)
423
7.23k
{
424
7.23k
  return isl_basic_map_get_local_space(bset);
425
7.23k
}
426
427
/* For each known div d = floor(f/m), add the constraints
428
 *
429
 *    f - m d >= 0
430
 *    -(f-(m-1)) + m d >= 0
431
 *
432
 * Do not finalize the result.
433
 */
434
static __isl_give isl_basic_map *add_known_div_constraints(
435
  __isl_take isl_basic_map *bmap)
436
138k
{
437
138k
  int i;
438
138k
  unsigned n_div;
439
138k
440
138k
  if (!bmap)
441
0
    return NULL;
442
138k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
443
138k
  if (n_div == 0)
444
105k
    return bmap;
445
32.7k
  bmap = isl_basic_map_cow(bmap);
446
32.7k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div);
447
32.7k
  if (!bmap)
448
0
    return NULL;
449
68.3k
  
for (i = 0; 32.7k
i < n_div;
++i35.6k
) {
450
35.6k
    if (isl_int_is_zero(bmap->div[i][0]))
451
35.6k
      
continue348
;
452
35.2k
    if (isl_basic_map_add_div_constraints(bmap, i) < 0)
453
0
      return isl_basic_map_free(bmap);
454
35.2k
  }
455
32.7k
456
32.7k
  return bmap;
457
32.7k
}
458
459
__isl_give isl_basic_map *isl_basic_map_from_local_space(
460
  __isl_take isl_local_space *ls)
461
135k
{
462
135k
  int i;
463
135k
  int n_div;
464
135k
  isl_basic_map *bmap;
465
135k
466
135k
  if (!ls)
467
0
    return NULL;
468
135k
469
135k
  n_div = isl_local_space_dim(ls, isl_dim_div);
470
135k
  bmap = isl_basic_map_alloc_space(isl_local_space_get_space(ls),
471
135k
          n_div, 0, 2 * n_div);
472
135k
473
166k
  for (i = 0; i < n_div; 
++i31.8k
)
474
31.8k
    if (isl_basic_map_alloc_div(bmap) < 0)
475
0
      goto error;
476
135k
477
166k
  
for (i = 0; 135k
i < n_div;
++i31.8k
)
478
31.8k
    isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col);
479
135k
  bmap = add_known_div_constraints(bmap);
480
135k
          
481
135k
  isl_local_space_free(ls);
482
135k
  return bmap;
483
0
error:
484
0
  isl_local_space_free(ls);
485
0
  isl_basic_map_free(bmap);
486
0
  return NULL;
487
135k
}
488
489
__isl_give isl_basic_set *isl_basic_set_from_local_space(
490
  __isl_take isl_local_space *ls)
491
20.7k
{
492
20.7k
  return isl_basic_map_from_local_space(ls);
493
20.7k
}
494
495
__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
496
716k
{
497
716k
  return isl_space_copy(isl_map_peek_space(map));
498
716k
}
499
500
__isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set)
501
268k
{
502
268k
  if (!set)
503
1
    return NULL;
504
268k
  return isl_space_copy(set->dim);
505
268k
}
506
507
__isl_give isl_basic_map *isl_basic_map_set_tuple_name(
508
  __isl_take isl_basic_map *bmap, enum isl_dim_type type, const char *s)
509
0
{
510
0
  bmap = isl_basic_map_cow(bmap);
511
0
  if (!bmap)
512
0
    return NULL;
513
0
  bmap->dim = isl_space_set_tuple_name(bmap->dim, type, s);
514
0
  if (!bmap->dim)
515
0
    goto error;
516
0
  bmap = isl_basic_map_finalize(bmap);
517
0
  return bmap;
518
0
error:
519
0
  isl_basic_map_free(bmap);
520
0
  return NULL;
521
0
}
522
523
__isl_give isl_basic_set *isl_basic_set_set_tuple_name(
524
  __isl_take isl_basic_set *bset, const char *s)
525
0
{
526
0
  return isl_basic_map_set_tuple_name(bset, isl_dim_set, s);
527
0
}
528
529
const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap,
530
  enum isl_dim_type type)
531
0
{
532
0
  return bmap ? isl_space_get_tuple_name(bmap->dim, type) : NULL;
533
0
}
534
535
__isl_give isl_map *isl_map_set_tuple_name(__isl_take isl_map *map,
536
  enum isl_dim_type type, const char *s)
537
0
{
538
0
  int i;
539
0
540
0
  map = isl_map_cow(map);
541
0
  if (!map)
542
0
    return NULL;
543
0
544
0
  map->dim = isl_space_set_tuple_name(map->dim, type, s);
545
0
  if (!map->dim)
546
0
    goto error;
547
0
548
0
  for (i = 0; i < map->n; ++i) {
549
0
    map->p[i] = isl_basic_map_set_tuple_name(map->p[i], type, s);
550
0
    if (!map->p[i])
551
0
      goto error;
552
0
  }
553
0
554
0
  return map;
555
0
error:
556
0
  isl_map_free(map);
557
0
  return NULL;
558
0
}
559
560
/* Replace the identifier of the tuple of type "type" by "id".
561
 */
562
__isl_give isl_basic_map *isl_basic_map_set_tuple_id(
563
  __isl_take isl_basic_map *bmap,
564
  enum isl_dim_type type, __isl_take isl_id *id)
565
0
{
566
0
  bmap = isl_basic_map_cow(bmap);
567
0
  if (!bmap)
568
0
    goto error;
569
0
  bmap->dim = isl_space_set_tuple_id(bmap->dim, type, id);
570
0
  if (!bmap->dim)
571
0
    return isl_basic_map_free(bmap);
572
0
  bmap = isl_basic_map_finalize(bmap);
573
0
  return bmap;
574
0
error:
575
0
  isl_id_free(id);
576
0
  return NULL;
577
0
}
578
579
/* Replace the identifier of the tuple by "id".
580
 */
581
__isl_give isl_basic_set *isl_basic_set_set_tuple_id(
582
  __isl_take isl_basic_set *bset, __isl_take isl_id *id)
583
0
{
584
0
  return isl_basic_map_set_tuple_id(bset, isl_dim_set, id);
585
0
}
586
587
/* Does the input or output tuple have a name?
588
 */
589
isl_bool isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type)
590
111
{
591
111
  return map ? isl_space_has_tuple_name(map->dim, type) : 
isl_bool_error0
;
592
111
}
593
594
const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
595
  enum isl_dim_type type)
596
24
{
597
24
  return map ? isl_space_get_tuple_name(map->dim, type) : NULL;
598
24
}
599
600
__isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set,
601
  const char *s)
602
0
{
603
0
  return set_from_map(isl_map_set_tuple_name(set_to_map(set),
604
0
            isl_dim_set, s));
605
0
}
606
607
__isl_give isl_map *isl_map_set_tuple_id(__isl_take isl_map *map,
608
  enum isl_dim_type type, __isl_take isl_id *id)
609
13.2k
{
610
13.2k
  map = isl_map_cow(map);
611
13.2k
  if (!map)
612
0
    goto error;
613
13.2k
614
13.2k
  map->dim = isl_space_set_tuple_id(map->dim, type, id);
615
13.2k
616
13.2k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
617
0
error:
618
0
  isl_id_free(id);
619
0
  return NULL;
620
13.2k
}
621
622
__isl_give isl_set *isl_set_set_tuple_id(__isl_take isl_set *set,
623
  __isl_take isl_id *id)
624
2.46k
{
625
2.46k
  return isl_map_set_tuple_id(set, isl_dim_set, id);
626
2.46k
}
627
628
__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
629
  enum isl_dim_type type)
630
5.91k
{
631
5.91k
  map = isl_map_cow(map);
632
5.91k
  if (!map)
633
0
    return NULL;
634
5.91k
635
5.91k
  map->dim = isl_space_reset_tuple_id(map->dim, type);
636
5.91k
637
5.91k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
638
5.91k
}
639
640
__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
641
5.91k
{
642
5.91k
  return isl_map_reset_tuple_id(set, isl_dim_set);
643
5.91k
}
644
645
isl_bool isl_map_has_tuple_id(__isl_keep isl_map *map, enum isl_dim_type type)
646
56
{
647
56
  return map ? isl_space_has_tuple_id(map->dim, type) : 
isl_bool_error0
;
648
56
}
649
650
__isl_give isl_id *isl_map_get_tuple_id(__isl_keep isl_map *map,
651
  enum isl_dim_type type)
652
28.0k
{
653
28.0k
  return map ? 
isl_space_get_tuple_id(map->dim, type)28.0k
: NULL;
654
28.0k
}
655
656
isl_bool isl_set_has_tuple_id(__isl_keep isl_set *set)
657
0
{
658
0
  return isl_map_has_tuple_id(set, isl_dim_set);
659
0
}
660
661
__isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
662
542
{
663
542
  return isl_map_get_tuple_id(set, isl_dim_set);
664
542
}
665
666
/* Does the set tuple have a name?
667
 */
668
isl_bool isl_set_has_tuple_name(__isl_keep isl_set *set)
669
144
{
670
144
  if (!set)
671
0
    return isl_bool_error;
672
144
  return isl_space_has_tuple_name(set->dim, isl_dim_set);
673
144
}
674
675
676
const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
677
0
{
678
0
  return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL;
679
0
}
680
681
const char *isl_set_get_tuple_name(__isl_keep isl_set *set)
682
171
{
683
171
  return set ? isl_space_get_tuple_name(set->dim, isl_dim_set) : NULL;
684
171
}
685
686
const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap,
687
  enum isl_dim_type type, unsigned pos)
688
0
{
689
0
  return bmap ? isl_space_get_dim_name(bmap->dim, type, pos) : NULL;
690
0
}
691
692
const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset,
693
  enum isl_dim_type type, unsigned pos)
694
0
{
695
0
  return bset ? isl_space_get_dim_name(bset->dim, type, pos) : NULL;
696
0
}
697
698
/* Does the given dimension have a name?
699
 */
700
isl_bool isl_map_has_dim_name(__isl_keep isl_map *map,
701
  enum isl_dim_type type, unsigned pos)
702
0
{
703
0
  if (!map)
704
0
    return isl_bool_error;
705
0
  return isl_space_has_dim_name(map->dim, type, pos);
706
0
}
707
708
const char *isl_map_get_dim_name(__isl_keep isl_map *map,
709
  enum isl_dim_type type, unsigned pos)
710
0
{
711
0
  return map ? isl_space_get_dim_name(map->dim, type, pos) : NULL;
712
0
}
713
714
const char *isl_set_get_dim_name(__isl_keep isl_set *set,
715
  enum isl_dim_type type, unsigned pos)
716
2
{
717
2
  return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL;
718
2
}
719
720
/* Does the given dimension have a name?
721
 */
722
isl_bool isl_set_has_dim_name(__isl_keep isl_set *set,
723
  enum isl_dim_type type, unsigned pos)
724
0
{
725
0
  if (!set)
726
0
    return isl_bool_error;
727
0
  return isl_space_has_dim_name(set->dim, type, pos);
728
0
}
729
730
__isl_give isl_basic_map *isl_basic_map_set_dim_name(
731
  __isl_take isl_basic_map *bmap,
732
  enum isl_dim_type type, unsigned pos, const char *s)
733
0
{
734
0
  bmap = isl_basic_map_cow(bmap);
735
0
  if (!bmap)
736
0
    return NULL;
737
0
  bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s);
738
0
  if (!bmap->dim)
739
0
    goto error;
740
0
  return isl_basic_map_finalize(bmap);
741
0
error:
742
0
  isl_basic_map_free(bmap);
743
0
  return NULL;
744
0
}
745
746
__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
747
  enum isl_dim_type type, unsigned pos, const char *s)
748
0
{
749
0
  int i;
750
0
751
0
  map = isl_map_cow(map);
752
0
  if (!map)
753
0
    return NULL;
754
0
755
0
  map->dim = isl_space_set_dim_name(map->dim, type, pos, s);
756
0
  if (!map->dim)
757
0
    goto error;
758
0
759
0
  for (i = 0; i < map->n; ++i) {
760
0
    map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s);
761
0
    if (!map->p[i])
762
0
      goto error;
763
0
  }
764
0
765
0
  return map;
766
0
error:
767
0
  isl_map_free(map);
768
0
  return NULL;
769
0
}
770
771
__isl_give isl_basic_set *isl_basic_set_set_dim_name(
772
  __isl_take isl_basic_set *bset,
773
  enum isl_dim_type type, unsigned pos, const char *s)
774
0
{
775
0
  return bset_from_bmap(isl_basic_map_set_dim_name(bset_to_bmap(bset),
776
0
              type, pos, s));
777
0
}
778
779
__isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set,
780
  enum isl_dim_type type, unsigned pos, const char *s)
781
0
{
782
0
  return set_from_map(isl_map_set_dim_name(set_to_map(set),
783
0
              type, pos, s));
784
0
}
785
786
isl_bool isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
787
  enum isl_dim_type type, unsigned pos)
788
0
{
789
0
  if (!bmap)
790
0
    return isl_bool_error;
791
0
  return isl_space_has_dim_id(bmap->dim, type, pos);
792
0
}
793
794
__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset,
795
  enum isl_dim_type type, unsigned pos)
796
0
{
797
0
  return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL;
798
0
}
799
800
isl_bool isl_map_has_dim_id(__isl_keep isl_map *map,
801
  enum isl_dim_type type, unsigned pos)
802
0
{
803
0
  return map ? isl_space_has_dim_id(map->dim, type, pos) : isl_bool_error;
804
0
}
805
806
__isl_give isl_id *isl_map_get_dim_id(__isl_keep isl_map *map,
807
  enum isl_dim_type type, unsigned pos)
808
295
{
809
295
  return map ? isl_space_get_dim_id(map->dim, type, pos) : NULL;
810
295
}
811
812
isl_bool isl_set_has_dim_id(__isl_keep isl_set *set,
813
  enum isl_dim_type type, unsigned pos)
814
0
{
815
0
  return isl_map_has_dim_id(set, type, pos);
816
0
}
817
818
__isl_give isl_id *isl_set_get_dim_id(__isl_keep isl_set *set,
819
  enum isl_dim_type type, unsigned pos)
820
123
{
821
123
  return isl_map_get_dim_id(set, type, pos);
822
123
}
823
824
__isl_give isl_map *isl_map_set_dim_id(__isl_take isl_map *map,
825
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
826
1.32k
{
827
1.32k
  map = isl_map_cow(map);
828
1.32k
  if (!map)
829
0
    goto error;
830
1.32k
831
1.32k
  map->dim = isl_space_set_dim_id(map->dim, type, pos, id);
832
1.32k
833
1.32k
  return isl_map_reset_space(map, isl_space_copy(map->dim));
834
0
error:
835
0
  isl_id_free(id);
836
0
  return NULL;
837
1.32k
}
838
839
__isl_give isl_set *isl_set_set_dim_id(__isl_take isl_set *set,
840
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
841
61
{
842
61
  return isl_map_set_dim_id(set, type, pos, id);
843
61
}
844
845
int isl_map_find_dim_by_id(__isl_keep isl_map *map, enum isl_dim_type type,
846
  __isl_keep isl_id *id)
847
118
{
848
118
  if (!map)
849
0
    return -1;
850
118
  return isl_space_find_dim_by_id(map->dim, type, id);
851
118
}
852
853
int isl_set_find_dim_by_id(__isl_keep isl_set *set, enum isl_dim_type type,
854
  __isl_keep isl_id *id)
855
118
{
856
118
  return isl_map_find_dim_by_id(set, type, id);
857
118
}
858
859
/* Return the position of the dimension of the given type and name
860
 * in "bmap".
861
 * Return -1 if no such dimension can be found.
862
 */
863
int isl_basic_map_find_dim_by_name(__isl_keep isl_basic_map *bmap,
864
  enum isl_dim_type type, const char *name)
865
0
{
866
0
  if (!bmap)
867
0
    return -1;
868
0
  return isl_space_find_dim_by_name(bmap->dim, type, name);
869
0
}
870
871
int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type,
872
  const char *name)
873
875
{
874
875
  if (!map)
875
0
    return -1;
876
875
  return isl_space_find_dim_by_name(map->dim, type, name);
877
875
}
878
879
int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
880
  const char *name)
881
875
{
882
875
  return isl_map_find_dim_by_name(set, type, name);
883
875
}
884
885
/* Check whether equality i of bset is a pure stride constraint
886
 * on a single dimension, i.e., of the form
887
 *
888
 *  v = k e
889
 *
890
 * with k a constant and e an existentially quantified variable.
891
 */
892
isl_bool isl_basic_set_eq_is_stride(__isl_keep isl_basic_set *bset, int i)
893
0
{
894
0
  unsigned nparam;
895
0
  unsigned d;
896
0
  unsigned n_div;
897
0
  int pos1;
898
0
  int pos2;
899
0
900
0
  if (!bset)
901
0
    return isl_bool_error;
902
0
903
0
  if (!isl_int_is_zero(bset->eq[i][0]))
904
0
    return isl_bool_false;
905
0
906
0
  nparam = isl_basic_set_dim(bset, isl_dim_param);
907
0
  d = isl_basic_set_dim(bset, isl_dim_set);
908
0
  n_div = isl_basic_set_dim(bset, isl_dim_div);
909
0
910
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1, nparam) != -1)
911
0
    return isl_bool_false;
912
0
  pos1 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam, d);
913
0
  if (pos1 == -1)
914
0
    return isl_bool_false;
915
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + pos1 + 1,
916
0
          d - pos1 - 1) != -1)
917
0
    return isl_bool_false;
918
0
919
0
  pos2 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d, n_div);
920
0
  if (pos2 == -1)
921
0
    return isl_bool_false;
922
0
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d  + pos2 + 1,
923
0
           n_div - pos2 - 1) != -1)
924
0
    return isl_bool_false;
925
0
  if (!isl_int_is_one(bset->eq[i][1 + nparam + pos1]) &&
926
0
      !isl_int_is_negone(bset->eq[i][1 + nparam + pos1]))
927
0
    return isl_bool_false;
928
0
929
0
  return isl_bool_true;
930
0
}
931
932
/* Reset the user pointer on all identifiers of parameters and tuples
933
 * of the space of "map".
934
 */
935
__isl_give isl_map *isl_map_reset_user(__isl_take isl_map *map)
936
0
{
937
0
  isl_space *space;
938
0
939
0
  space = isl_map_get_space(map);
940
0
  space = isl_space_reset_user(space);
941
0
  map = isl_map_reset_space(map, space);
942
0
943
0
  return map;
944
0
}
945
946
/* Reset the user pointer on all identifiers of parameters and tuples
947
 * of the space of "set".
948
 */
949
__isl_give isl_set *isl_set_reset_user(__isl_take isl_set *set)
950
0
{
951
0
  return isl_map_reset_user(set);
952
0
}
953
954
isl_bool isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
955
380k
{
956
380k
  if (!bmap)
957
0
    return isl_bool_error;
958
380k
  return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
959
380k
}
960
961
/* Has "map" been marked as a rational map?
962
 * In particular, have all basic maps in "map" been marked this way?
963
 * An empty map is not considered to be rational.
964
 * Maps where only some of the basic maps are marked rational
965
 * are not allowed.
966
 */
967
isl_bool isl_map_is_rational(__isl_keep isl_map *map)
968
8.52k
{
969
8.52k
  int i;
970
8.52k
  isl_bool rational;
971
8.52k
972
8.52k
  if (!map)
973
0
    return isl_bool_error;
974
8.52k
  if (map->n == 0)
975
0
    return isl_bool_false;
976
8.52k
  rational = isl_basic_map_is_rational(map->p[0]);
977
8.52k
  if (rational < 0)
978
0
    return rational;
979
9.15k
  
for (i = 1; 8.52k
i < map->n;
++i625
) {
980
625
    isl_bool rational_i;
981
625
982
625
    rational_i = isl_basic_map_is_rational(map->p[i]);
983
625
    if (rational_i < 0)
984
0
      return rational_i;
985
625
    if (rational != rational_i)
986
625
      
isl_die0
(isl_map_get_ctx(map), isl_error_unsupported,
987
625
        "mixed rational and integer basic maps "
988
625
        "not supported", return isl_bool_error);
989
625
  }
990
8.52k
991
8.52k
  return rational;
992
8.52k
}
993
994
/* Has "set" been marked as a rational set?
995
 * In particular, have all basic set in "set" been marked this way?
996
 * An empty set is not considered to be rational.
997
 * Sets where only some of the basic sets are marked rational
998
 * are not allowed.
999
 */
1000
isl_bool isl_set_is_rational(__isl_keep isl_set *set)
1001
8.52k
{
1002
8.52k
  return isl_map_is_rational(set);
1003
8.52k
}
1004
1005
int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
1006
45.6k
{
1007
45.6k
  return isl_basic_map_is_rational(bset);
1008
45.6k
}
1009
1010
/* Does "bmap" contain any rational points?
1011
 *
1012
 * If "bmap" has an equality for each dimension, equating the dimension
1013
 * to an integer constant, then it has no rational points, even if it
1014
 * is marked as rational.
1015
 */
1016
isl_bool isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
1017
90.7k
{
1018
90.7k
  isl_bool has_rational = isl_bool_true;
1019
90.7k
  unsigned total;
1020
90.7k
1021
90.7k
  if (!bmap)
1022
0
    return isl_bool_error;
1023
90.7k
  if (isl_basic_map_plain_is_empty(bmap))
1024
2
    return isl_bool_false;
1025
90.7k
  if (!isl_basic_map_is_rational(bmap))
1026
90.4k
    return isl_bool_false;
1027
302
  bmap = isl_basic_map_copy(bmap);
1028
302
  bmap = isl_basic_map_implicit_equalities(bmap);
1029
302
  if (!bmap)
1030
0
    return isl_bool_error;
1031
302
  total = isl_basic_map_total_dim(bmap);
1032
302
  if (bmap->n_eq == total) {
1033
2
    int i, j;
1034
3
    for (i = 0; i < bmap->n_eq; 
++i1
) {
1035
2
      j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);
1036
2
      if (j < 0)
1037
0
        break;
1038
2
      if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
1039
2
          
!1
isl_int_is_negone1
(bmap->eq[i][1 + j]))
1040
2
        
break1
;
1041
1
      j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1,
1042
1
                total - j - 1);
1043
1
      if (j >= 0)
1044
0
        break;
1045
1
    }
1046
2
    if (i == bmap->n_eq)
1047
1
      has_rational = isl_bool_false;
1048
2
  }
1049
302
  isl_basic_map_free(bmap);
1050
302
1051
302
  return has_rational;
1052
302
}
1053
1054
/* Does "map" contain any rational points?
1055
 */
1056
isl_bool isl_map_has_rational(__isl_keep isl_map *map)
1057
77.8k
{
1058
77.8k
  int i;
1059
77.8k
  isl_bool has_rational;
1060
77.8k
1061
77.8k
  if (!map)
1062
0
    return isl_bool_error;
1063
168k
  
for (i = 0; 77.8k
i < map->n;
++i90.4k
) {
1064
90.7k
    has_rational = isl_basic_map_has_rational(map->p[i]);
1065
90.7k
    if (has_rational < 0 || has_rational)
1066
301
      return has_rational;
1067
90.7k
  }
1068
77.8k
  
return isl_bool_false77.5k
;
1069
77.8k
}
1070
1071
/* Does "set" contain any rational points?
1072
 */
1073
isl_bool isl_set_has_rational(__isl_keep isl_set *set)
1074
26.1k
{
1075
26.1k
  return isl_map_has_rational(set);
1076
26.1k
}
1077
1078
/* Is this basic set a parameter domain?
1079
 */
1080
isl_bool isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
1081
62
{
1082
62
  if (!bset)
1083
0
    return isl_bool_error;
1084
62
  return isl_space_is_params(bset->dim);
1085
62
}
1086
1087
/* Is this set a parameter domain?
1088
 */
1089
isl_bool isl_set_is_params(__isl_keep isl_set *set)
1090
64.1k
{
1091
64.1k
  if (!set)
1092
0
    return isl_bool_error;
1093
64.1k
  return isl_space_is_params(set->dim);
1094
64.1k
}
1095
1096
/* Is this map actually a parameter domain?
1097
 * Users should never call this function.  Outside of isl,
1098
 * a map can never be a parameter domain.
1099
 */
1100
isl_bool isl_map_is_params(__isl_keep isl_map *map)
1101
171
{
1102
171
  if (!map)
1103
0
    return isl_bool_error;
1104
171
  return isl_space_is_params(map->dim);
1105
171
}
1106
1107
static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
1108
    struct isl_basic_map *bmap, unsigned extra,
1109
    unsigned n_eq, unsigned n_ineq)
1110
4.65M
{
1111
4.65M
  int i;
1112
4.65M
  size_t row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + extra;
1113
4.65M
1114
4.65M
  bmap->ctx = ctx;
1115
4.65M
  isl_ctx_ref(ctx);
1116
4.65M
1117
4.65M
  bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
1118
4.65M
  if (isl_blk_is_error(bmap->block))
1119
0
    goto error;
1120
4.65M
1121
4.65M
  bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
1122
4.65M
  if ((n_ineq + n_eq) && 
!bmap->ineq3.36M
)
1123
0
    goto error;
1124
4.65M
1125
4.65M
  if (extra == 0) {
1126
4.39M
    bmap->block2 = isl_blk_empty();
1127
4.39M
    bmap->div = NULL;
1128
4.39M
  } else {
1129
256k
    bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
1130
256k
    if (isl_blk_is_error(bmap->block2))
1131
0
      goto error;
1132
256k
1133
256k
    bmap->div = isl_alloc_array(ctx, isl_int *, extra);
1134
256k
    if (!bmap->div)
1135
0
      goto error;
1136
4.65M
  }
1137
4.65M
1138
31.6M
  
for (i = 0; 4.65M
i < n_ineq + n_eq;
++i26.9M
)
1139
26.9M
    bmap->ineq[i] = bmap->block.data + i * row_size;
1140
4.65M
1141
5.09M
  for (i = 0; i < extra; 
++i446k
)
1142
446k
    bmap->div[i] = bmap->block2.data + i * (1 + row_size);
1143
4.65M
1144
4.65M
  bmap->ref = 1;
1145
4.65M
  bmap->flags = 0;
1146
4.65M
  bmap->c_size = n_eq + n_ineq;
1147
4.65M
  bmap->eq = bmap->ineq + n_ineq;
1148
4.65M
  bmap->extra = extra;
1149
4.65M
  bmap->n_eq = 0;
1150
4.65M
  bmap->n_ineq = 0;
1151
4.65M
  bmap->n_div = 0;
1152
4.65M
  bmap->sample = NULL;
1153
4.65M
1154
4.65M
  return bmap;
1155
0
error:
1156
0
  isl_basic_map_free(bmap);
1157
0
  return NULL;
1158
4.65M
}
1159
1160
struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
1161
    unsigned nparam, unsigned dim, unsigned extra,
1162
    unsigned n_eq, unsigned n_ineq)
1163
285k
{
1164
285k
  struct isl_basic_map *bmap;
1165
285k
  isl_space *space;
1166
285k
1167
285k
  space = isl_space_set_alloc(ctx, nparam, dim);
1168
285k
  if (!space)
1169
0
    return NULL;
1170
285k
1171
285k
  bmap = isl_basic_map_alloc_space(space, extra, n_eq, n_ineq);
1172
285k
  return bset_from_bmap(bmap);
1173
285k
}
1174
1175
__isl_give isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *dim,
1176
    unsigned extra, unsigned n_eq, unsigned n_ineq)
1177
386k
{
1178
386k
  struct isl_basic_map *bmap;
1179
386k
  if (!dim)
1180
0
    return NULL;
1181
386k
  isl_assert(dim->ctx, dim->n_in == 0, goto error);
1182
386k
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1183
386k
  return bset_from_bmap(bmap);
1184
0
error:
1185
0
  isl_space_free(dim);
1186
0
  return NULL;
1187
386k
}
1188
1189
struct isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *dim,
1190
    unsigned extra, unsigned n_eq, unsigned n_ineq)
1191
4.65M
{
1192
4.65M
  struct isl_basic_map *bmap;
1193
4.65M
1194
4.65M
  if (!dim)
1195
0
    return NULL;
1196
4.65M
  bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
1197
4.65M
  if (!bmap)
1198
0
    goto error;
1199
4.65M
  bmap->dim = dim;
1200
4.65M
1201
4.65M
  return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
1202
0
error:
1203
0
  isl_space_free(dim);
1204
0
  return NULL;
1205
4.65M
}
1206
1207
struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
1208
    unsigned nparam, unsigned in, unsigned out, unsigned extra,
1209
    unsigned n_eq, unsigned n_ineq)
1210
105
{
1211
105
  struct isl_basic_map *bmap;
1212
105
  isl_space *dim;
1213
105
1214
105
  dim = isl_space_alloc(ctx, nparam, in, out);
1215
105
  if (!dim)
1216
0
    return NULL;
1217
105
1218
105
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1219
105
  return bmap;
1220
105
}
1221
1222
static void dup_constraints(
1223
    struct isl_basic_map *dst, struct isl_basic_map *src)
1224
2.48M
{
1225
2.48M
  int i;
1226
2.48M
  unsigned total = isl_basic_map_total_dim(src);
1227
2.48M
1228
3.86M
  for (i = 0; i < src->n_eq; 
++i1.37M
) {
1229
1.37M
    int j = isl_basic_map_alloc_equality(dst);
1230
1.37M
    isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
1231
1.37M
  }
1232
2.48M
1233
17.5M
  for (i = 0; i < src->n_ineq; 
++i15.0M
) {
1234
15.0M
    int j = isl_basic_map_alloc_inequality(dst);
1235
15.0M
    isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
1236
15.0M
  }
1237
2.48M
1238
2.57M
  for (i = 0; i < src->n_div; 
++i89.8k
) {
1239
89.8k
    int j = isl_basic_map_alloc_div(dst);
1240
89.8k
    isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
1241
89.8k
  }
1242
2.48M
  ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
1243
2.48M
}
1244
1245
__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap)
1246
2.48M
{
1247
2.48M
  struct isl_basic_map *dup;
1248
2.48M
1249
2.48M
  if (!bmap)
1250
0
    return NULL;
1251
2.48M
  dup = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
1252
2.48M
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
1253
2.48M
  if (!dup)
1254
0
    return NULL;
1255
2.48M
  dup_constraints(dup, bmap);
1256
2.48M
  dup->flags = bmap->flags;
1257
2.48M
  dup->sample = isl_vec_copy(bmap->sample);
1258
2.48M
  return dup;
1259
2.48M
}
1260
1261
struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
1262
50.4k
{
1263
50.4k
  struct isl_basic_map *dup;
1264
50.4k
1265
50.4k
  dup = isl_basic_map_dup(bset_to_bmap(bset));
1266
50.4k
  return bset_from_bmap(dup);
1267
50.4k
}
1268
1269
__isl_give isl_basic_set *isl_basic_set_copy(__isl_keep isl_basic_set *bset)
1270
1.01M
{
1271
1.01M
  if (!bset)
1272
206
    return NULL;
1273
1.01M
1274
1.01M
  if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
1275
992k
    bset->ref++;
1276
992k
    return bset;
1277
992k
  }
1278
19.2k
  return isl_basic_set_dup(bset);
1279
19.2k
}
1280
1281
__isl_give isl_set *isl_set_copy(__isl_keep isl_set *set)
1282
1.66M
{
1283
1.66M
  if (!set)
1284
16.1k
    return NULL;
1285
1.64M
1286
1.64M
  set->ref++;
1287
1.64M
  return set;
1288
1.64M
}
1289
1290
__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)
1291
3.78M
{
1292
3.78M
  if (!bmap)
1293
0
    return NULL;
1294
3.78M
1295
3.78M
  if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
1296
3.65M
    bmap->ref++;
1297
3.65M
    return bmap;
1298
3.65M
  }
1299
121k
  bmap = isl_basic_map_dup(bmap);
1300
121k
  if (bmap)
1301
121k
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
1302
121k
  return bmap;
1303
121k
}
1304
1305
__isl_give isl_map *isl_map_copy(__isl_keep isl_map *map)
1306
1.20M
{
1307
1.20M
  if (!map)
1308
150
    return NULL;
1309
1.20M
1310
1.20M
  map->ref++;
1311
1.20M
  return map;
1312
1.20M
}
1313
1314
__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap)
1315
13.4M
{
1316
13.4M
  if (!bmap)
1317
6.47M
    return NULL;
1318
6.98M
1319
6.98M
  if (--bmap->ref > 0)
1320
2.33M
    return NULL;
1321
4.65M
1322
4.65M
  isl_ctx_deref(bmap->ctx);
1323
4.65M
  free(bmap->div);
1324
4.65M
  isl_blk_free(bmap->ctx, bmap->block2);
1325
4.65M
  free(bmap->ineq);
1326
4.65M
  isl_blk_free(bmap->ctx, bmap->block);
1327
4.65M
  isl_vec_free(bmap->sample);
1328
4.65M
  isl_space_free(bmap->dim);
1329
4.65M
  free(bmap);
1330
4.65M
1331
4.65M
  return NULL;
1332
4.65M
}
1333
1334
__isl_null isl_basic_set *isl_basic_set_free(__isl_take isl_basic_set *bset)
1335
1.70M
{
1336
1.70M
  return isl_basic_map_free(bset_to_bmap(bset));
1337
1.70M
}
1338
1339
static int room_for_con(struct isl_basic_map *bmap, unsigned n)
1340
5.44M
{
1341
5.44M
  return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
1342
5.44M
}
1343
1344
/* Check that "map" has only named parameters, reporting an error
1345
 * if it does not.
1346
 */
1347
isl_stat isl_map_check_named_params(__isl_keep isl_map *map)
1348
177k
{
1349
177k
  return isl_space_check_named_params(isl_map_peek_space(map));
1350
177k
}
1351
1352
/* Check that "bmap1" and "bmap2" have the same parameters,
1353
 * reporting an error if they do not.
1354
 */
1355
static isl_stat isl_basic_map_check_equal_params(
1356
  __isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2)
1357
543k
{
1358
543k
  isl_bool match;
1359
543k
1360
543k
  match = isl_basic_map_has_equal_params(bmap1, bmap2);
1361
543k
  if (match < 0)
1362
0
    return isl_stat_error;
1363
543k
  if (!match)
1364
543k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
1365
543k
      "parameters don't match", return isl_stat_error);
1366
543k
  return isl_stat_ok;
1367
543k
}
1368
1369
__isl_give isl_map *isl_map_align_params_map_map_and(
1370
  __isl_take isl_map *map1, __isl_take isl_map *map2,
1371
  __isl_give isl_map *(*fn)(__isl_take isl_map *map1,
1372
            __isl_take isl_map *map2))
1373
1.03M
{
1374
1.03M
  if (!map1 || 
!map21.03M
)
1375
10
    goto error;
1376
1.03M
  if (isl_map_has_equal_params(map1, map2))
1377
998k
    return fn(map1, map2);
1378
34.8k
  if (isl_map_check_named_params(map1) < 0)
1379
0
    goto error;
1380
34.8k
  if (isl_map_check_named_params(map2) < 0)
1381
0
    goto error;
1382
34.8k
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
1383
34.8k
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
1384
34.8k
  return fn(map1, map2);
1385
10
error:
1386
10
  isl_map_free(map1);
1387
10
  isl_map_free(map2);
1388
10
  return NULL;
1389
34.8k
}
1390
1391
isl_bool isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1,
1392
  __isl_keep isl_map *map2,
1393
  isl_bool (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2))
1394
61.1k
{
1395
61.1k
  isl_bool r;
1396
61.1k
1397
61.1k
  if (!map1 || !map2)
1398
0
    return isl_bool_error;
1399
61.1k
  if (isl_map_has_equal_params(map1, map2))
1400
58.5k
    return fn(map1, map2);
1401
2.55k
  if (isl_map_check_named_params(map1) < 0)
1402
0
    return isl_bool_error;
1403
2.55k
  if (isl_map_check_named_params(map2) < 0)
1404
0
    return isl_bool_error;
1405
2.55k
  map1 = isl_map_copy(map1);
1406
2.55k
  map2 = isl_map_copy(map2);
1407
2.55k
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
1408
2.55k
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
1409
2.55k
  r = fn(map1, map2);
1410
2.55k
  isl_map_free(map1);
1411
2.55k
  isl_map_free(map2);
1412
2.55k
  return r;
1413
2.55k
}
1414
1415
int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
1416
4.24M
{
1417
4.24M
  struct isl_ctx *ctx;
1418
4.24M
  if (!bmap)
1419
0
    return -1;
1420
4.24M
  ctx = bmap->ctx;
1421
4.24M
  isl_assert(ctx, room_for_con(bmap, 1), return -1);
1422
4.24M
  isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
1423
4.24M
      return -1);
1424
4.24M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1425
4.24M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1426
4.24M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1427
4.24M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1428
4.24M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1429
4.24M
  if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
1430
105k
    isl_int *t;
1431
105k
    int j = isl_basic_map_alloc_inequality(bmap);
1432
105k
    if (j < 0)
1433
0
      return -1;
1434
105k
    t = bmap->ineq[j];
1435
105k
    bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
1436
105k
    bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1437
105k
    bmap->eq[-1] = t;
1438
105k
    bmap->n_eq++;
1439
105k
    bmap->n_ineq--;
1440
105k
    bmap->eq--;
1441
105k
    return 0;
1442
105k
  }
1443
4.13M
  isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
1444
4.13M
          bmap->extra - bmap->n_div);
1445
4.13M
  return bmap->n_eq++;
1446
4.13M
}
1447
1448
int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
1449
1.08M
{
1450
1.08M
  return isl_basic_map_alloc_equality(bset_to_bmap(bset));
1451
1.08M
}
1452
1453
int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
1454
305k
{
1455
305k
  if (!bmap)
1456
0
    return -1;
1457
305k
  isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
1458
305k
  bmap->n_eq -= n;
1459
305k
  return 0;
1460
305k
}
1461
1462
int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
1463
502
{
1464
502
  return isl_basic_map_free_equality(bset_to_bmap(bset), n);
1465
502
}
1466
1467
int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
1468
611k
{
1469
611k
  isl_int *t;
1470
611k
  if (!bmap)
1471
0
    return -1;
1472
611k
  isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
1473
611k
1474
611k
  if (pos != bmap->n_eq - 1) {
1475
217k
    t = bmap->eq[pos];
1476
217k
    bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
1477
217k
    bmap->eq[bmap->n_eq - 1] = t;
1478
217k
  }
1479
611k
  bmap->n_eq--;
1480
611k
  return 0;
1481
611k
}
1482
1483
/* Turn inequality "pos" of "bmap" into an equality.
1484
 *
1485
 * In particular, we move the inequality in front of the equalities
1486
 * and move the last inequality in the position of the moved inequality.
1487
 * Note that isl_tab_make_equalities_explicit depends on this particular
1488
 * change in the ordering of the constraints.
1489
 */
1490
void isl_basic_map_inequality_to_equality(
1491
    struct isl_basic_map *bmap, unsigned pos)
1492
1.06M
{
1493
1.06M
  isl_int *t;
1494
1.06M
1495
1.06M
  t = bmap->ineq[pos];
1496
1.06M
  bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1497
1.06M
  bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
1498
1.06M
  bmap->eq[-1] = t;
1499
1.06M
  bmap->n_eq++;
1500
1.06M
  bmap->n_ineq--;
1501
1.06M
  bmap->eq--;
1502
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1503
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1504
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1505
1.06M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1506
1.06M
}
1507
1508
static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
1509
23.5M
{
1510
23.5M
  return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
1511
23.5M
}
1512
1513
int isl_basic_map_alloc_inequality(__isl_keep isl_basic_map *bmap)
1514
22.9M
{
1515
22.9M
  struct isl_ctx *ctx;
1516
22.9M
  if (!bmap)
1517
0
    return -1;
1518
22.9M
  ctx = bmap->ctx;
1519
22.9M
  isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
1520
22.9M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
1521
22.9M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1522
22.9M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1523
22.9M
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
1524
22.9M
  isl_seq_clr(bmap->ineq[bmap->n_ineq] +
1525
22.9M
          1 + isl_basic_map_total_dim(bmap),
1526
22.9M
          bmap->extra - bmap->n_div);
1527
22.9M
  return bmap->n_ineq++;
1528
22.9M
}
1529
1530
int isl_basic_set_alloc_inequality(__isl_keep isl_basic_set *bset)
1531
774k
{
1532
774k
  return isl_basic_map_alloc_inequality(bset_to_bmap(bset));
1533
774k
}
1534
1535
int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
1536
928k
{
1537
928k
  if (!bmap)
1538
0
    return -1;
1539
928k
  isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
1540
928k
  bmap->n_ineq -= n;
1541
928k
  return 0;
1542
928k
}
1543
1544
int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
1545
5.39k
{
1546
5.39k
  return isl_basic_map_free_inequality(bset_to_bmap(bset), n);
1547
5.39k
}
1548
1549
int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
1550
7.80M
{
1551
7.80M
  isl_int *t;
1552
7.80M
  if (!bmap)
1553
0
    return -1;
1554
7.80M
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
1555
7.80M
1556
7.80M
  if (pos != bmap->n_ineq - 1) {
1557
4.38M
    t = bmap->ineq[pos];
1558
4.38M
    bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
1559
4.38M
    bmap->ineq[bmap->n_ineq - 1] = t;
1560
4.38M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1561
4.38M
  }
1562
7.80M
  bmap->n_ineq--;
1563
7.80M
  return 0;
1564
7.80M
}
1565
1566
int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
1567
17.9k
{
1568
17.9k
  return isl_basic_map_drop_inequality(bset_to_bmap(bset), pos);
1569
17.9k
}
1570
1571
__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
1572
  isl_int *eq)
1573
19.6k
{
1574
19.6k
  int k;
1575
19.6k
1576
19.6k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
1577
19.6k
  if (!bmap)
1578
0
    return NULL;
1579
19.6k
  k = isl_basic_map_alloc_equality(bmap);
1580
19.6k
  if (k < 0)
1581
0
    goto error;
1582
19.6k
  isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
1583
19.6k
  return bmap;
1584
0
error:
1585
0
  isl_basic_map_free(bmap);
1586
0
  return NULL;
1587
19.6k
}
1588
1589
__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
1590
  isl_int *eq)
1591
0
{
1592
0
  return bset_from_bmap(isl_basic_map_add_eq(bset_to_bmap(bset), eq));
1593
0
}
1594
1595
__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
1596
  isl_int *ineq)
1597
365k
{
1598
365k
  int k;
1599
365k
1600
365k
  bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
1601
365k
  if (!bmap)
1602
0
    return NULL;
1603
365k
  k = isl_basic_map_alloc_inequality(bmap);
1604
365k
  if (k < 0)
1605
0
    goto error;
1606
365k
  isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
1607
365k
  return bmap;
1608
0
error:
1609
0
  isl_basic_map_free(bmap);
1610
0
  return NULL;
1611
365k
}
1612
1613
__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
1614
  isl_int *ineq)
1615
21.0k
{
1616
21.0k
  return bset_from_bmap(isl_basic_map_add_ineq(bset_to_bmap(bset), ineq));
1617
21.0k
}
1618
1619
int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
1620
419k
{
1621
419k
  if (!bmap)
1622
0
    return -1;
1623
419k
  isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
1624
419k
  isl_seq_clr(bmap->div[bmap->n_div] +
1625
419k
          1 + 1 + isl_basic_map_total_dim(bmap),
1626
419k
          bmap->extra - bmap->n_div);
1627
419k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
1628
419k
  return bmap->n_div++;
1629
419k
}
1630
1631
int isl_basic_set_alloc_div(struct isl_basic_set *bset)
1632
1.13k
{
1633
1.13k
  return isl_basic_map_alloc_div(bset_to_bmap(bset));
1634
1.13k
}
1635
1636
/* Check that there are "n" dimensions of type "type" starting at "first"
1637
 * in "bmap".
1638
 */
1639
static isl_stat isl_basic_map_check_range(__isl_keep isl_basic_map *bmap,
1640
  enum isl_dim_type type, unsigned first, unsigned n)
1641
316k
{
1642
316k
  unsigned dim;
1643
316k
1644
316k
  if (!bmap)
1645
0
    return isl_stat_error;
1646
316k
  dim = isl_basic_map_dim(bmap, type);
1647
316k
  if (first + n > dim || first + n < first)
1648
316k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1649
316k
      "position or range out of bounds",
1650
316k
      return isl_stat_error);
1651
316k
  return isl_stat_ok;
1652
316k
}
1653
1654
/* Insert an extra integer division, prescribed by "div", to "bmap"
1655
 * at (integer division) position "pos".
1656
 *
1657
 * The integer division is first added at the end and then moved
1658
 * into the right position.
1659
 */
1660
__isl_give isl_basic_map *isl_basic_map_insert_div(
1661
  __isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div)
1662
2.21k
{
1663
2.21k
  int i, k;
1664
2.21k
1665
2.21k
  bmap = isl_basic_map_cow(bmap);
1666
2.21k
  if (!bmap || !div)
1667
0
    return isl_basic_map_free(bmap);
1668
2.21k
1669
2.21k
  if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all))
1670
2.21k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
1671
2.21k
      "unexpected size", return isl_basic_map_free(bmap));
1672
2.21k
  if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0)
1673
0
    return isl_basic_map_free(bmap);
1674
2.21k
1675
2.21k
  bmap = isl_basic_map_extend_space(bmap,
1676
2.21k
          isl_basic_map_get_space(bmap), 1, 0, 2);
1677
2.21k
  k = isl_basic_map_alloc_div(bmap);
1678
2.21k
  if (k < 0)
1679
0
    return isl_basic_map_free(bmap);
1680
2.21k
  isl_seq_cpy(bmap->div[k], div->el, div->size);
1681
2.21k
  isl_int_set_si(bmap->div[k][div->size], 0);
1682
2.21k
1683
2.71k
  for (i = k; i > pos; 
--i494
)
1684
494
    isl_basic_map_swap_div(bmap, i, i - 1);
1685
2.21k
1686
2.21k
  return bmap;
1687
2.21k
}
1688
1689
isl_stat isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
1690
616k
{
1691
616k
  if (!bmap)
1692
0
    return isl_stat_error;
1693
616k
  isl_assert(bmap->ctx, n <= bmap->n_div, return isl_stat_error);
1694
616k
  bmap->n_div -= n;
1695
616k
  return isl_stat_ok;
1696
616k
}
1697
1698
/* Copy constraint from src to dst, putting the vars of src at offset
1699
 * dim_off in dst and the divs of src at offset div_off in dst.
1700
 * If both sets are actually map, then dim_off applies to the input
1701
 * variables.
1702
 */
1703
static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
1704
          struct isl_basic_map *src_map, isl_int *src,
1705
          unsigned in_off, unsigned out_off, unsigned div_off)
1706
6.08M
{
1707
6.08M
  unsigned src_nparam = isl_basic_map_dim(src_map, isl_dim_param);
1708
6.08M
  unsigned dst_nparam = isl_basic_map_dim(dst_map, isl_dim_param);
1709
6.08M
  unsigned src_in = isl_basic_map_dim(src_map, isl_dim_in);
1710
6.08M
  unsigned dst_in = isl_basic_map_dim(dst_map, isl_dim_in);
1711
6.08M
  unsigned src_out = isl_basic_map_dim(src_map, isl_dim_out);
1712
6.08M
  unsigned dst_out = isl_basic_map_dim(dst_map, isl_dim_out);
1713
6.08M
  isl_int_set(dst[0], src[0]);
1714
6.08M
  isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
1715
6.08M
  if (dst_nparam > src_nparam)
1716
0
    isl_seq_clr(dst+1+src_nparam,
1717
0
        dst_nparam - src_nparam);
1718
6.08M
  isl_seq_clr(dst+1+dst_nparam, in_off);
1719
6.08M
  isl_seq_cpy(dst+1+dst_nparam+in_off,
1720
6.08M
        src+1+src_nparam,
1721
6.08M
        isl_min(dst_in-in_off, src_in));
1722
6.08M
  if (dst_in-in_off > src_in)
1723
48.5k
    isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
1724
48.5k
        dst_in - in_off - src_in);
1725
6.08M
  isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
1726
6.08M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
1727
6.08M
        src+1+src_nparam+src_in,
1728
6.08M
        isl_min(dst_out-out_off, src_out));
1729
6.08M
  if (dst_out-out_off > src_out)
1730
500k
    isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
1731
500k
        dst_out - out_off - src_out);
1732
6.08M
  isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
1733
6.08M
  isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
1734
6.08M
        src+1+src_nparam+src_in+src_out,
1735
6.08M
        isl_min(dst_map->extra-div_off, src_map->n_div));
1736
6.08M
  if (dst_map->n_div-div_off > src_map->n_div)
1737
0
    isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
1738
0
        div_off+src_map->n_div,
1739
0
        dst_map->n_div - div_off - src_map->n_div);
1740
6.08M
}
1741
1742
static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
1743
         struct isl_basic_map *src_map, isl_int *src,
1744
         unsigned in_off, unsigned out_off, unsigned div_off)
1745
103k
{
1746
103k
  isl_int_set(dst[0], src[0]);
1747
103k
  copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
1748
103k
}
1749
1750
static __isl_give isl_basic_map *add_constraints(
1751
  __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2,
1752
  unsigned i_pos, unsigned o_pos)
1753
1.16M
{
1754
1.16M
  int i;
1755
1.16M
  unsigned div_off;
1756
1.16M
1757
1.16M
  if (!bmap1 || !bmap2)
1758
0
    goto error;
1759
1.16M
1760
1.16M
  div_off = bmap1->n_div;
1761
1.16M
1762
1.86M
  for (i = 0; i < bmap2->n_eq; 
++i703k
) {
1763
703k
    int i1 = isl_basic_map_alloc_equality(bmap1);
1764
703k
    if (i1 < 0)
1765
0
      goto error;
1766
703k
    copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
1767
703k
        i_pos, o_pos, div_off);
1768
703k
  }
1769
1.16M
1770
6.44M
  
for (i = 0; 1.16M
i < bmap2->n_ineq;
++i5.28M
) {
1771
5.28M
    int i1 = isl_basic_map_alloc_inequality(bmap1);
1772
5.28M
    if (i1 < 0)
1773
0
      goto error;
1774
5.28M
    copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
1775
5.28M
        i_pos, o_pos, div_off);
1776
5.28M
  }
1777
1.16M
1778
1.26M
  
for (i = 0; 1.16M
i < bmap2->n_div;
++i103k
) {
1779
103k
    int i1 = isl_basic_map_alloc_div(bmap1);
1780
103k
    if (i1 < 0)
1781
0
      goto error;
1782
103k
    copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
1783
103k
       i_pos, o_pos, div_off);
1784
103k
  }
1785
1.16M
1786
1.16M
  isl_basic_map_free(bmap2);
1787
1.16M
1788
1.16M
  return bmap1;
1789
0
1790
0
error:
1791
0
  isl_basic_map_free(bmap1);
1792
0
  isl_basic_map_free(bmap2);
1793
0
  return NULL;
1794
1.16M
}
1795
1796
struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
1797
    struct isl_basic_set *bset2, unsigned pos)
1798
0
{
1799
0
  return bset_from_bmap(add_constraints(bset_to_bmap(bset1),
1800
0
            bset_to_bmap(bset2), 0, pos));
1801
0
}
1802
1803
__isl_give isl_basic_map *isl_basic_map_extend_space(
1804
  __isl_take isl_basic_map *base, __isl_take isl_space *dim,
1805
  unsigned extra, unsigned n_eq, unsigned n_ineq)
1806
1.32M
{
1807
1.32M
  struct isl_basic_map *ext;
1808
1.32M
  unsigned flags;
1809
1.32M
  int dims_ok;
1810
1.32M
1811
1.32M
  if (!dim)
1812
0
    goto error;
1813
1.32M
1814
1.32M
  if (!base)
1815
0
    goto error;
1816
1.32M
1817
1.32M
  dims_ok = isl_space_is_equal(base->dim, dim) &&
1818
1.32M
      
base->extra >= base->n_div + extra1.22M
;
1819
1.32M
1820
1.32M
  if (dims_ok && 
room_for_con(base, n_eq + n_ineq)1.20M
&&
1821
1.32M
           
room_for_ineq(base, n_ineq)551k
) {
1822
537k
    isl_space_free(dim);
1823
537k
    return base;
1824
537k
  }
1825
790k
1826
790k
  isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
1827
790k
  isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
1828
790k
  isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
1829
790k
  extra += base->extra;
1830
790k
  n_eq += base->n_eq;
1831
790k
  n_ineq += base->n_ineq;
1832
790k
1833
790k
  ext = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
1834
790k
  dim = NULL;
1835
790k
  if (!ext)
1836
0
    goto error;
1837
790k
1838
790k
  if (dims_ok)
1839
665k
    ext->sample = isl_vec_copy(base->sample);
1840
790k
  flags = base->flags;
1841
790k
  ext = add_constraints(ext, base, 0, 0);
1842
790k
  if (ext) {
1843
790k
    ext->flags = flags;
1844
790k
    ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
1845
790k
  }
1846
790k
1847
790k
  return ext;
1848
0
1849
0
error:
1850
0
  isl_space_free(dim);
1851
0
  isl_basic_map_free(base);
1852
0
  return NULL;
1853
790k
}
1854
1855
__isl_give isl_basic_set *isl_basic_set_extend_space(
1856
  __isl_take 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
686k
{
1867
686k
  if (!base)
1868
0
    return NULL;
1869
686k
  return isl_basic_map_extend_space(base, isl_space_copy(base->dim),
1870
686k
          0, n_eq, n_ineq);
1871
686k
}
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
146k
{
1877
146k
  struct isl_basic_map *bmap;
1878
146k
  isl_space *dim;
1879
146k
1880
146k
  if (!base)
1881
0
    return NULL;
1882
146k
  dim = isl_space_alloc(base->ctx, nparam, n_in, n_out);
1883
146k
  if (!dim)
1884
0
    goto error;
1885
146k
1886
146k
  bmap = isl_basic_map_extend_space(base, dim, extra, n_eq, n_ineq);
1887
146k
  return bmap;
1888
0
error:
1889
0
  isl_basic_map_free(base);
1890
0
  return NULL;
1891
146k
}
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
146k
{
1897
146k
  return bset_from_bmap(isl_basic_map_extend(bset_to_bmap(base),
1898
146k
          nparam, 0, dim, extra, n_eq, n_ineq));
1899
146k
}
1900
1901
struct isl_basic_set *isl_basic_set_extend_constraints(
1902
    struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
1903
12.0k
{
1904
12.0k
  isl_basic_map *bmap = bset_to_bmap(base);
1905
12.0k
  bmap = isl_basic_map_extend_constraints(bmap, n_eq, n_ineq);
1906
12.0k
  return bset_from_bmap(bmap);
1907
12.0k
}
1908
1909
__isl_give isl_basic_set *isl_basic_set_cow(__isl_take isl_basic_set *bset)
1910
891k
{
1911
891k
  return bset_from_bmap(isl_basic_map_cow(bset_to_bmap(bset)));
1912
891k
}
1913
1914
__isl_give isl_basic_map *isl_basic_map_cow(__isl_take isl_basic_map *bmap)
1915
5.13M
{
1916
5.13M
  if (!bmap)
1917
0
    return NULL;
1918
5.13M
1919
5.13M
  if (bmap->ref > 1) {
1920
2.31M
    bmap->ref--;
1921
2.31M
    bmap = isl_basic_map_dup(bmap);
1922
2.31M
  }
1923
5.13M
  if (bmap) {
1924
5.13M
    ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
1925
5.13M
    ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
1926
5.13M
  }
1927
5.13M
  return bmap;
1928
5.13M
}
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.93M
{
1937
2.93M
  isl_basic_map_free(map->cached_simple_hull[0]);
1938
2.93M
  isl_basic_map_free(map->cached_simple_hull[1]);
1939
2.93M
  map->cached_simple_hull[0] = NULL;
1940
2.93M
  map->cached_simple_hull[1] = NULL;
1941
2.93M
  return map;
1942
2.93M
}
1943
1944
__isl_give isl_set *isl_set_cow(__isl_take isl_set *set)
1945
204k
{
1946
204k
  return isl_map_cow(set);
1947
204k
}
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.99M
{
1961
1.99M
  if (!map)
1962
17
    return NULL;
1963
1.99M
1964
1.99M
  if (map->ref == 1)
1965
1.40M
    return clear_caches(map);
1966
597k
  map->ref--;
1967
597k
  return isl_map_dup(map);
1968
597k
}
1969
1970
static void swap_vars(struct isl_blk blk, isl_int *a,
1971
      unsigned a_len, unsigned b_len)
1972
400k
{
1973
400k
  isl_seq_cpy(blk.data, a+a_len, b_len);
1974
400k
  isl_seq_cpy(blk.data+b_len, a, a_len);
1975
400k
  isl_seq_cpy(a, blk.data, b_len+a_len);
1976
400k
}
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
181k
{
1981
181k
  int i;
1982
181k
  struct isl_blk blk;
1983
181k
1984
181k
  if (!bmap)
1985
0
    goto error;
1986
181k
1987
181k
  isl_assert(bmap->ctx,
1988
181k
    pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);
1989
181k
1990
181k
  if (n1 == 0 || 
n2 == 072.2k
)
1991
116k
    return bmap;
1992
64.9k
1993
64.9k
  bmap = isl_basic_map_cow(bmap);
1994
64.9k
  if (!bmap)
1995
0
    return NULL;
1996
64.9k
1997
64.9k
  blk = isl_blk_alloc(bmap->ctx, n1 + n2);
1998
64.9k
  if (isl_blk_is_error(blk))
1999
0
    goto error;
2000
64.9k
2001
258k
  
for (i = 0; 64.9k
i < bmap->n_eq;
++i193k
)
2002
193k
    swap_vars(blk,
2003
193k
        bmap->eq[i] + pos, n1, n2);
2004
64.9k
2005
268k
  for (i = 0; i < bmap->n_ineq; 
++i203k
)
2006
203k
    swap_vars(blk,
2007
203k
        bmap->ineq[i] + pos, n1, n2);
2008
64.9k
2009
68.4k
  for (i = 0; i < bmap->n_div; 
++i3.51k
)
2010
3.51k
    swap_vars(blk,
2011
3.51k
        bmap->div[i]+1 + pos, n1, n2);
2012
64.9k
2013
64.9k
  isl_blk_free(bmap->ctx, blk);
2014
64.9k
2015
64.9k
  ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
2016
64.9k
  bmap = isl_basic_map_gauss(bmap, NULL);
2017
64.9k
  return isl_basic_map_finalize(bmap);
2018
0
error:
2019
0
  isl_basic_map_free(bmap);
2020
0
  return NULL;
2021
64.9k
}
2022
2023
__isl_give isl_basic_map *isl_basic_map_set_to_empty(
2024
  __isl_take isl_basic_map *bmap)
2025
196k
{
2026
196k
  int i = 0;
2027
196k
  unsigned total;
2028
196k
  if (!bmap)
2029
0
    goto error;
2030
196k
  total = isl_basic_map_total_dim(bmap);
2031
196k
  if (isl_basic_map_free_div(bmap, bmap->n_div) < 0)
2032
0
    return isl_basic_map_free(bmap);
2033
196k
  isl_basic_map_free_inequality(bmap, bmap->n_ineq);
2034
196k
  if (bmap->n_eq > 0)
2035
91.6k
    isl_basic_map_free_equality(bmap, bmap->n_eq-1);
2036
105k
  else {
2037
105k
    i = isl_basic_map_alloc_equality(bmap);
2038
105k
    if (i < 0)
2039
0
      goto error;
2040
196k
  }
2041
196k
  isl_int_set_si(bmap->eq[i][0], 1);
2042
196k
  isl_seq_clr(bmap->eq[i]+1, total);
2043
196k
  ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
2044
196k
  isl_vec_free(bmap->sample);
2045
196k
  bmap->sample = NULL;
2046
196k
  return isl_basic_map_finalize(bmap);
2047
0
error:
2048
0
  isl_basic_map_free(bmap);
2049
0
  return NULL;
2050
196k
}
2051
2052
__isl_give isl_basic_set *isl_basic_set_set_to_empty(
2053
  __isl_take isl_basic_set *bset)
2054
6.74k
{
2055
6.74k
  return bset_from_bmap(isl_basic_map_set_to_empty(bset_to_bmap(bset)));
2056
6.74k
}
2057
2058
__isl_give isl_basic_map *isl_basic_map_set_rational(
2059
  __isl_take isl_basic_map *bmap)
2060
86.6k
{
2061
86.6k
  if (!bmap)
2062
0
    return NULL;
2063
86.6k
2064
86.6k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
2065
86.6k
    
return bmap53.9k
;
2066
32.7k
2067
32.7k
  bmap = isl_basic_map_cow(bmap);
2068
32.7k
  if (!bmap)
2069
0
    return NULL;
2070
32.7k
2071
32.7k
  ISL_F_SET(bmap, ISL_BASIC_MAP_RATIONAL);
2072
32.7k
2073
32.7k
  return isl_basic_map_finalize(bmap);
2074
32.7k
}
2075
2076
__isl_give isl_basic_set *isl_basic_set_set_rational(
2077
  __isl_take isl_basic_set *bset)
2078
27.2k
{
2079
27.2k
  return isl_basic_map_set_rational(bset);
2080
27.2k
}
2081
2082
__isl_give isl_basic_set *isl_basic_set_set_integral(
2083
  __isl_take isl_basic_set *bset)
2084
15
{
2085
15
  if (!bset)
2086
0
    return NULL;
2087
15
2088
15
  if (!ISL_F_ISSET(bset, ISL_BASIC_MAP_RATIONAL))
2089
15
    
return bset0
;
2090
15
2091
15
  bset = isl_basic_set_cow(bset);
2092
15
  if (!bset)
2093
0
    return NULL;
2094
15
2095
15
  ISL_F_CLR(bset, ISL_BASIC_MAP_RATIONAL);
2096
15
2097
15
  return isl_basic_set_finalize(bset);
2098
15
}
2099
2100
__isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map)
2101
32.4k
{
2102
32.4k
  int i;
2103
32.4k
2104
32.4k
  map = isl_map_cow(map);
2105
32.4k
  if (!map)
2106
0
    return NULL;
2107
91.8k
  
for (i = 0; 32.4k
i < map->n;
++i59.4k
) {
2108
59.4k
    map->p[i] = isl_basic_map_set_rational(map->p[i]);
2109
59.4k
    if (!map->p[i])
2110
0
      goto error;
2111
59.4k
  }
2112
32.4k
  return map;
2113
0
error:
2114
0
  isl_map_free(map);
2115
0
  return NULL;
2116
32.4k
}
2117
2118
__isl_give isl_set *isl_set_set_rational(__isl_take isl_set *set)
2119
32.4k
{
2120
32.4k
  return isl_map_set_rational(set);
2121
32.4k
}
2122
2123
/* Swap divs "a" and "b" in "bmap" (without modifying any of the constraints
2124
 * of "bmap").
2125
 */
2126
static void swap_div(__isl_keep isl_basic_map *bmap, int a, int b)
2127
6.32k
{
2128
6.32k
  isl_int *t = bmap->div[a];
2129
6.32k
  bmap->div[a] = bmap->div[b];
2130
6.32k
  bmap->div[b] = t;
2131
6.32k
}
2132
2133
/* Swap divs "a" and "b" in "bmap" and adjust the constraints and
2134
 * div definitions accordingly.
2135
 */
2136
void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
2137
6.10k
{
2138
6.10k
  int i;
2139
6.10k
  unsigned off = isl_space_dim(bmap->dim, isl_dim_all);
2140
6.10k
2141
6.10k
  swap_div(bmap, a, b);
2142
6.10k
2143
25.2k
  for (i = 0; i < bmap->n_eq; 
++i19.1k
)
2144
19.1k
    isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
2145
6.10k
2146
79.2k
  for (i = 0; i < bmap->n_ineq; 
++i73.1k
)
2147
73.1k
    isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
2148
6.10k
2149
32.1k
  for (i = 0; i < bmap->n_div; 
++i26.0k
)
2150
26.0k
    isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
2151
6.10k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2152
6.10k
}
2153
2154
/* Swap divs "a" and "b" in "bset" and adjust the constraints and
2155
 * div definitions accordingly.
2156
 */
2157
void isl_basic_set_swap_div(__isl_keep isl_basic_set *bset, int a, int b)
2158
0
{
2159
0
  isl_basic_map_swap_div(bset, a, b);
2160
0
}
2161
2162
static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
2163
6.65M
{
2164
6.65M
  isl_seq_cpy(c, c + n, rem);
2165
6.65M
  isl_seq_clr(c + rem, n);
2166
6.65M
}
2167
2168
/* Drop n dimensions starting at first.
2169
 *
2170
 * In principle, this frees up some extra variables as the number
2171
 * of columns remains constant, but we would have to extend
2172
 * the div array too as the number of rows in this array is assumed
2173
 * to be equal to extra.
2174
 */
2175
__isl_give isl_basic_set *isl_basic_set_drop_dims(
2176
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
2177
167k
{
2178
167k
  return isl_basic_map_drop(bset_to_bmap(bset), isl_dim_set, first, n);
2179
167k
}
2180
2181
/* Move "n" divs starting at "first" to the end of the list of divs.
2182
 */
2183
static struct isl_basic_map *move_divs_last(struct isl_basic_map *bmap,
2184
  unsigned first, unsigned n)
2185
762
{
2186
762
  isl_int **div;
2187
762
  int i;
2188
762
2189
762
  if (first + n == bmap->n_div)
2190
678
    return bmap;
2191
84
2192
84
  div = isl_alloc_array(bmap->ctx, isl_int *, n);
2193
84
  if (!div)
2194
0
    goto error;
2195
168
  
for (i = 0; 84
i < n;
++i84
)
2196
84
    div[i] = bmap->div[first + i];
2197
220
  for (i = 0; i < bmap->n_div - first - n; 
++i136
)
2198
136
    bmap->div[first + i] = bmap->div[first + n + i];
2199
168
  for (i = 0; i < n; 
++i84
)
2200
84
    bmap->div[bmap->n_div - n + i] = div[i];
2201
84
  free(div);
2202
84
  return bmap;
2203
0
error:
2204
0
  isl_basic_map_free(bmap);
2205
0
  return NULL;
2206
84
}
2207
2208
/* Check that there are "n" dimensions of type "type" starting at "first"
2209
 * in "map".
2210
 */
2211
static isl_stat isl_map_check_range(__isl_keep isl_map *map,
2212
  enum isl_dim_type type, unsigned first, unsigned n)
2213
83.6k
{
2214
83.6k
  if (!map)
2215
0
    return isl_stat_error;
2216
83.6k
  if (first + n > isl_map_dim(map, type) || first + n < first)
2217
83.6k
    
isl_die0
(isl_map_get_ctx(map), isl_error_invalid,
2218
83.6k
      "position or range out of bounds",
2219
83.6k
      return isl_stat_error);
2220
83.6k
  return isl_stat_ok;
2221
83.6k
}
2222
2223
/* Drop "n" dimensions of type "type" starting at "first".
2224
 *
2225
 * In principle, this frees up some extra variables as the number
2226
 * of columns remains constant, but we would have to extend
2227
 * the div array too as the number of rows in this array is assumed
2228
 * to be equal to extra.
2229
 */
2230
__isl_give isl_basic_map *isl_basic_map_drop(__isl_take isl_basic_map *bmap,
2231
  enum isl_dim_type type, unsigned first, unsigned n)
2232
531k
{
2233
531k
  int i;
2234
531k
  unsigned dim;
2235
531k
  unsigned offset;
2236
531k
  unsigned left;
2237
531k
2238
531k
  if (!bmap)
2239
0
    goto error;
2240
531k
2241
531k
  dim = isl_basic_map_dim(bmap, type);
2242
531k
  isl_assert(bmap->ctx, first + n <= dim, goto error);
2243
531k
2244
531k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)90.9k
)
2245
90.9k
    return bmap;
2246
440k
2247
440k
  bmap = isl_basic_map_cow(bmap);
2248
440k
  if (!bmap)
2249
0
    return NULL;
2250
440k
2251
440k
  offset = isl_basic_map_offset(bmap, type) + first;
2252
440k
  left = isl_basic_map_total_dim(bmap) - (offset - 1) - n;
2253
443k
  for (i = 0; i < bmap->n_eq; 
++i3.51k
)
2254
3.51k
    constraint_drop_vars(bmap->eq[i]+offset, n, left);
2255
440k
2256
2.17M
  for (i = 0; i < bmap->n_ineq; 
++i1.73M
)
2257
1.73M
    constraint_drop_vars(bmap->ineq[i]+offset, n, left);
2258
440k
2259
442k
  for (i = 0; i < bmap->n_div; 
++i2.14k
)
2260
2.14k
    constraint_drop_vars(bmap->div[i]+1+offset, n, left);
2261
440k
2262
440k
  if (type == isl_dim_div) {
2263
762
    bmap = move_divs_last(bmap, first, n);
2264
762
    if (!bmap)
2265
0
      goto error;
2266
762
    if (isl_basic_map_free_div(bmap, n) < 0)
2267
0
      return isl_basic_map_free(bmap);
2268
439k
  } else
2269
439k
    bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
2270
440k
  if (!bmap->dim)
2271
0
    goto error;
2272
440k
2273
440k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2274
440k
  bmap = isl_basic_map_simplify(bmap);
2275
440k
  return isl_basic_map_finalize(bmap);
2276
0
error:
2277
0
  isl_basic_map_free(bmap);
2278
0
  return NULL;
2279
440k
}
2280
2281
__isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset,
2282
  enum isl_dim_type type, unsigned first, unsigned n)
2283
360k
{
2284
360k
  return bset_from_bmap(isl_basic_map_drop(bset_to_bmap(bset),
2285
360k
              type, first, n));
2286
360k
}
2287
2288
__isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
2289
  enum isl_dim_type type, unsigned first, unsigned n)
2290
792
{
2291
792
  int i;
2292
792
2293
792
  if (isl_map_check_range(map, type, first, n) < 0)
2294
0
    return isl_map_free(map);
2295
792
2296
792
  if (n == 0 && 
!isl_space_is_named_or_nested(map->dim, type)0
)
2297
0
    return map;
2298
792
  map = isl_map_cow(map);
2299
792
  if (!map)
2300
0
    goto error;
2301
792
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
2302
792
  if (!map->dim)
2303
0
    goto error;
2304
792
2305
1.72k
  
for (i = 0; 792
i < map->n;
++i928
) {
2306
928
    map->p[i] = isl_basic_map_drop(map->p[i], type, first, n);
2307
928
    if (!map->p[i])
2308
0
      goto error;
2309
928
  }
2310
792
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
2311
792
2312
792
  return map;
2313
0
error:
2314
0
  isl_map_free(map);
2315
0
  return NULL;
2316
792
}
2317
2318
__isl_give isl_set *isl_set_drop(__isl_take isl_set *set,
2319
  enum isl_dim_type type, unsigned first, unsigned n)
2320
218
{
2321
218
  return set_from_map(isl_map_drop(set_to_map(set), type, first, n));
2322
218
}
2323
2324
/*
2325
 * We don't cow, as the div is assumed to be redundant.
2326
 */
2327
__isl_give isl_basic_map *isl_basic_map_drop_div(
2328
  __isl_take isl_basic_map *bmap, unsigned div)
2329
419k
{
2330
419k
  int i;
2331
419k
  unsigned pos;
2332
419k
2333
419k
  if (!bmap)
2334
0
    goto error;
2335
419k
2336
419k
  pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;
2337
419k
2338
419k
  isl_assert(bmap->ctx, div < bmap->n_div, goto error);
2339
419k
2340
1.86M
  
for (i = 0; 419k
i < bmap->n_eq;
++i1.44M
)
2341
1.44M
    constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);
2342
419k
2343
3.00M
  for (i = 0; i < bmap->n_ineq; 
++i2.58M
) {
2344
2.58M
    if (!isl_int_is_zero(bmap->ineq[i][pos])) {
2345
20.3k
      isl_basic_map_drop_inequality(bmap, i);
2346
20.3k
      --i;
2347
20.3k
      continue;
2348
20.3k
    }
2349
2.56M
    constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
2350
2.56M
  }
2351
419k
2352
1.32M
  for (i = 0; i < bmap->n_div; 
++i905k
)
2353
905k
    constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);
2354
419k
2355
419k
  if (div != bmap->n_div - 1) {
2356
23.9k
    int j;
2357
23.9k
    isl_int *t = bmap->div[div];
2358
23.9k
2359
59.6k
    for (j = div; j < bmap->n_div - 1; 
++j35.6k
)
2360
35.6k
      bmap->div[j] = bmap->div[j+1];
2361
23.9k
2362
23.9k
    bmap->div[bmap->n_div - 1] = t;
2363
23.9k
  }
2364
419k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2365
419k
  if (isl_basic_map_free_div(bmap, 1) < 0)
2366
0
    return isl_basic_map_free(bmap);
2367
419k
2368
419k
  return bmap;
2369
0
error:
2370
0
  isl_basic_map_free(bmap);
2371
0
  return NULL;
2372
419k
}
2373
2374
/* Eliminate the specified n dimensions starting at first from the
2375
 * constraints, without removing the dimensions from the space.
2376
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2377
 */
2378
__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
2379
  enum isl_dim_type type, unsigned first, unsigned n)
2380
17.9k
{
2381
17.9k
  int i;
2382
17.9k
2383
17.9k
  if (n == 0)
2384
6.77k
    return map;
2385
11.1k
2386
11.1k
  if (isl_map_check_range(map, type, first, n) < 0)
2387
0
    return isl_map_free(map);
2388
11.1k
2389
11.1k
  map = isl_map_cow(map);
2390
11.1k
  if (!map)
2391
0
    return NULL;
2392
11.1k
2393
22.4k
  
for (i = 0; 11.1k
i < map->n;
++i11.2k
) {
2394
11.2k
    map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n);
2395
11.2k
    if (!map->p[i])
2396
0
      goto error;
2397
11.2k
  }
2398
11.1k
  return map;
2399
0
error:
2400
0
  isl_map_free(map);
2401
0
  return NULL;
2402
11.1k
}
2403
2404
/* Eliminate the specified n dimensions starting at first from the
2405
 * constraints, without removing the dimensions from the space.
2406
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2407
 */
2408
__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
2409
  enum isl_dim_type type, unsigned first, unsigned n)
2410
14.0k
{
2411
14.0k
  return set_from_map(isl_map_eliminate(set_to_map(set), type, first, n));
2412
14.0k
}
2413
2414
/* Eliminate the specified n dimensions starting at first from the
2415
 * constraints, without removing the dimensions from the space.
2416
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
2417
 */
2418
__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
2419
  unsigned first, unsigned n)
2420
0
{
2421
0
  return isl_set_eliminate(set, isl_dim_set, first, n);
2422
0
}
2423
2424
__isl_give isl_basic_map *isl_basic_map_remove_divs(
2425
  __isl_take isl_basic_map *bmap)
2426
2.67k
{
2427
2.67k
  if (!bmap)
2428
0
    return NULL;
2429
2.67k
  bmap = isl_basic_map_eliminate_vars(bmap,
2430
2.67k
          isl_space_dim(bmap->dim, isl_dim_all), bmap->n_div);
2431
2.67k
  if (!bmap)
2432
0
    return NULL;
2433
2.67k
  bmap->n_div = 0;
2434
2.67k
  return isl_basic_map_finalize(bmap);
2435
2.67k
}
2436
2437
__isl_give isl_basic_set *isl_basic_set_remove_divs(
2438
  __isl_take isl_basic_set *bset)
2439
799
{
2440
799
  return bset_from_bmap(isl_basic_map_remove_divs(bset_to_bmap(bset)));
2441
799
}
2442
2443
__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
2444
5.63k
{
2445
5.63k
  int i;
2446
5.63k
2447
5.63k
  if (!map)
2448
0
    return NULL;
2449
5.63k
  if (map->n == 0)
2450
4.42k
    return map;
2451
1.21k
2452
1.21k
  map = isl_map_cow(map);
2453
1.21k
  if (!map)
2454
0
    return NULL;
2455
1.21k
  
2456
3.05k
  
for (i = 0; 1.21k
i < map->n;
++i1.84k
) {
2457
1.84k
    map->p[i] = isl_basic_map_remove_divs(map->p[i]);
2458
1.84k
    if (!map->p[i])
2459
0
      goto error;
2460
1.84k
  }
2461
1.21k
  return map;
2462
0
error:
2463
0
  isl_map_free(map);
2464
0
  return NULL;
2465
1.21k
}
2466
2467
__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
2468
5.50k
{
2469
5.50k
  return isl_map_remove_divs(set);
2470
5.50k
}
2471
2472
__isl_give isl_basic_map *isl_basic_map_remove_dims(
2473
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
2474
  unsigned first, unsigned n)
2475
3.92k
{
2476
3.92k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2477
0
    return isl_basic_map_free(bmap);
2478
3.92k
  if (n == 0 && 
!isl_space_is_named_or_nested(bmap->dim, type)2.47k
)
2479
2.47k
    return bmap;
2480
1.44k
  bmap = isl_basic_map_eliminate_vars(bmap,
2481
1.44k
      isl_basic_map_offset(bmap, type) - 1 + first, n);
2482
1.44k
  if (!bmap)
2483
0
    return bmap;
2484
1.44k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && 
type == isl_dim_div25
)
2485
25
    return bmap;
2486
1.42k
  bmap = isl_basic_map_drop(bmap, type, first, n);
2487
1.42k
  return bmap;
2488
1.42k
}
2489
2490
/* Return true if the definition of the given div (recursively) involves
2491
 * any of the given variables.
2492
 */
2493
static isl_bool div_involves_vars(__isl_keep isl_basic_map *bmap, int div,
2494
  unsigned first, unsigned n)
2495
1.18k
{
2496
1.18k
  int i;
2497
1.18k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
2498
1.18k
2499
1.18k
  if (isl_int_is_zero(bmap->div[div][0]))
2500
1.18k
    
return isl_bool_false348
;
2501
840
  if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0)
2502
88
    return isl_bool_true;
2503
752
2504
1.61k
  
for (i = bmap->n_div - 1; 752
i >= 0;
--i865
) {
2505
865
    isl_bool involves;
2506
865
2507
865
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
2508
865
      continue;
2509
0
    involves = div_involves_vars(bmap, i, first, n);
2510
0
    if (involves < 0 || involves)
2511
0
      return involves;
2512
0
  }
2513
752
2514
752
  return isl_bool_false;
2515
752
}
2516
2517
/* Try and add a lower and/or upper bound on "div" to "bmap"
2518
 * based on inequality "i".
2519
 * "total" is the total number of variables (excluding the divs).
2520
 * "v" is a temporary object that can be used during the calculations.
2521
 * If "lb" is set, then a lower bound should be constructed.
2522
 * If "ub" is set, then an upper bound should be constructed.
2523
 *
2524
 * The calling function has already checked that the inequality does not
2525
 * reference "div", but we still need to check that the inequality is
2526
 * of the right form.  We'll consider the case where we want to construct
2527
 * a lower bound.  The construction of upper bounds is similar.
2528
 *
2529
 * Let "div" be of the form
2530
 *
2531
 *  q = floor((a + f(x))/d)
2532
 *
2533
 * We essentially check if constraint "i" is of the form
2534
 *
2535
 *  b + f(x) >= 0
2536
 *
2537
 * so that we can use it to derive a lower bound on "div".
2538
 * However, we allow a slightly more general form
2539
 *
2540
 *  b + g(x) >= 0
2541
 *
2542
 * with the condition that the coefficients of g(x) - f(x) are all
2543
 * divisible by d.
2544
 * Rewriting this constraint as
2545
 *
2546
 *  0 >= -b - g(x)
2547
 *
2548
 * adding a + f(x) to both sides and dividing by d, we obtain
2549
 *
2550
 *  (a + f(x))/d >= (a-b)/d + (f(x)-g(x))/d
2551
 *
2552
 * Taking the floor on both sides, we obtain
2553
 *
2554
 *  q >= floor((a-b)/d) + (f(x)-g(x))/d
2555
 *
2556
 * or
2557
 *
2558
 *  (g(x)-f(x))/d + ceil((b-a)/d) + q >= 0
2559
 *
2560
 * In the case of an upper bound, we construct the constraint
2561
 *
2562
 *  (g(x)+f(x))/d + floor((b+a)/d) - q >= 0
2563
 *
2564
 */
2565
static __isl_give isl_basic_map *insert_bounds_on_div_from_ineq(
2566
  __isl_take isl_basic_map *bmap, int div, int i,
2567
  unsigned total, isl_int v, int lb, int ub)
2568
68
{
2569
68
  int j;
2570
68
2571
257
  for (j = 0; (lb || 
ub68
) &&
j < total + bmap->n_div222
;
++j189
) {
2572
189
    if (lb) {
2573
168
      isl_int_sub(v, bmap->ineq[i][1 + j],
2574
168
          bmap->div[div][1 + 1 + j]);
2575
168
      lb = isl_int_is_divisible_by(v, bmap->div[div][0]);
2576
168
    }
2577
189
    if (ub) {
2578
163
      isl_int_add(v, bmap->ineq[i][1 + j],
2579
163
          bmap->div[div][1 + 1 + j]);
2580
163
      ub = isl_int_is_divisible_by(v, bmap->div[div][0]);
2581
163
    }
2582
189
  }
2583
68
  if (!lb && 
!ub47
)
2584
35
    return bmap;
2585
33
2586
33
  bmap = isl_basic_map_cow(bmap);
2587
33
  bmap = isl_basic_map_extend_constraints(bmap, 0, lb + ub);
2588
33
  if (lb) {
2589
21
    int k = isl_basic_map_alloc_inequality(bmap);
2590
21
    if (k < 0)
2591
0
      goto error;
2592
115
    
for (j = 0; 21
j < 1 + total + bmap->n_div;
++j94
) {
2593
94
      isl_int_sub(bmap->ineq[k][j], bmap->ineq[i][j],
2594
94
          bmap->div[div][1 + j]);
2595
94
      isl_int_cdiv_q(bmap->ineq[k][j],
2596
94
          bmap->ineq[k][j], bmap->div[div][0]);
2597
94
    }
2598
21
    isl_int_set_si(bmap->ineq[k][1 + total + div], 1);
2599
21
  }
2600
33
  if (ub) {
2601
18
    int k = isl_basic_map_alloc_inequality(bmap);
2602
18
    if (k < 0)
2603
0
      goto error;
2604
99
    
for (j = 0; 18
j < 1 + total + bmap->n_div;
++j81
) {
2605
81
      isl_int_add(bmap->ineq[k][j], bmap->ineq[i][j],
2606
81
          bmap->div[div][1 + j]);
2607
81
      isl_int_fdiv_q(bmap->ineq[k][j],
2608
81
          bmap->ineq[k][j], bmap->div[div][0]);
2609
81
    }
2610
18
    isl_int_set_si(bmap->ineq[k][1 + total + div], -1);
2611
18
  }
2612
33
2613
33
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2614
33
  return bmap;
2615
0
error:
2616
0
  isl_basic_map_free(bmap);
2617
0
  return NULL;
2618
33
}
2619
2620
/* This function is called right before "div" is eliminated from "bmap"
2621
 * using Fourier-Motzkin.
2622
 * Look through the constraints of "bmap" for constraints on the argument
2623
 * of the integer division and use them to construct constraints on the
2624
 * integer division itself.  These constraints can then be combined
2625
 * during the Fourier-Motzkin elimination.
2626
 * Note that it is only useful to introduce lower bounds on "div"
2627
 * if "bmap" already contains upper bounds on "div" as the newly
2628
 * introduce lower bounds can then be combined with the pre-existing
2629
 * upper bounds.  Similarly for upper bounds.
2630
 * We therefore first check if "bmap" contains any lower and/or upper bounds
2631
 * on "div".
2632
 *
2633
 * It is interesting to note that the introduction of these constraints
2634
 * can indeed lead to more accurate results, even when compared to
2635
 * deriving constraints on the argument of "div" from constraints on "div".
2636
 * Consider, for example, the set
2637
 *
2638
 *  { [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }
2639
 *
2640
 * The second constraint can be rewritten as
2641
 *
2642
 *  2 * [(-i-2j+3)/4] + k >= 0
2643
 *
2644
 * from which we can derive
2645
 *
2646
 *  -i - 2j + 3 >= -2k
2647
 *
2648
 * or
2649
 *
2650
 *  i + 2j <= 3 + 2k
2651
 *
2652
 * Combined with the first constraint, we obtain
2653
 *
2654
 *  -3 <= 3 + 2k  or  k >= -3
2655
 *
2656
 * If, on the other hand we derive a constraint on [(i+2j)/4] from
2657
 * the first constraint, we obtain
2658
 *
2659
 *  [(i + 2j)/4] >= [-3/4] = -1
2660
 *
2661
 * Combining this constraint with the second constraint, we obtain
2662
 *
2663
 *  k >= -2
2664
 */
2665
static __isl_give isl_basic_map *insert_bounds_on_div(
2666
  __isl_take isl_basic_map *bmap, int div)
2667
88
{
2668
88
  int i;
2669
88
  int check_lb, check_ub;
2670
88
  isl_int v;
2671
88
  unsigned total;
2672
88
2673
88
  if (!bmap)
2674
0
    return NULL;
2675
88
2676
88
  if (isl_int_is_zero(bmap->div[div][0]))
2677
88
    
return bmap0
;
2678
88
2679
88
  total = isl_space_dim(bmap->dim, isl_dim_all);
2680
88
2681
88
  check_lb = 0;
2682
88
  check_ub = 0;
2683
397
  for (i = 0; (!check_lb || 
!check_ub27
) &&
i < bmap->n_ineq378
;
++i309
) {
2684
309
    int s = isl_int_sgn(bmap->ineq[i][1 + total + div]);
2685
309
    if (s > 0)
2686
19
      check_ub = 1;
2687
309
    if (s < 0)
2688
20
      check_lb = 1;
2689
309
  }
2690
88
2691
88
  if (!check_lb && 
!check_ub69
)
2692
69
    return bmap;
2693
19
2694
19
  isl_int_init(v);
2695
19
2696
177
  for (i = 0; bmap && i < bmap->n_ineq; 
++i158
) {
2697
158
    if (!isl_int_is_zero(bmap->ineq[i][1 + total + div]))
2698
158
      
continue90
;
2699
68
2700
68
    bmap = insert_bounds_on_div_from_ineq(bmap, div, i, total, v,
2701
68
              check_lb, check_ub);
2702
68
  }
2703
19
2704
19
  isl_int_clear(v);
2705
19
2706
19
  return bmap;
2707
19
}
2708
2709
/* Remove all divs (recursively) involving any of the given dimensions
2710
 * in their definitions.
2711
 */
2712
__isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
2713
  __isl_take isl_basic_map *bmap,
2714
  enum isl_dim_type type, unsigned first, unsigned n)
2715
10.5k
{
2716
10.5k
  int i;
2717
10.5k
2718
10.5k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2719
0
    return isl_basic_map_free(bmap);
2720
10.5k
  first += isl_basic_map_offset(bmap, type);
2721
10.5k
2722
11.7k
  for (i = bmap->n_div - 1; i >= 0; 
--i1.18k
) {
2723
1.18k
    isl_bool involves;
2724
1.18k
2725
1.18k
    involves = div_involves_vars(bmap, i, first, n);
2726
1.18k
    if (involves < 0)
2727
0
      return isl_basic_map_free(bmap);
2728
1.18k
    if (!involves)
2729
1.10k
      continue;
2730
88
    bmap = insert_bounds_on_div(bmap, i);
2731
88
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
2732
88
    if (!bmap)
2733
0
      return NULL;
2734
88
    i = bmap->n_div;
2735
88
  }
2736
10.5k
2737
10.5k
  return bmap;
2738
10.5k
}
2739
2740
__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
2741
  __isl_take isl_basic_set *bset,
2742
  enum isl_dim_type type, unsigned first, unsigned n)
2743
0
{
2744
0
  return isl_basic_map_remove_divs_involving_dims(bset, type, first, n);
2745
0
}
2746
2747
__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
2748
  enum isl_dim_type type, unsigned first, unsigned n)
2749
8.31k
{
2750
8.31k
  int i;
2751
8.31k
2752
8.31k
  if (!map)
2753
0
    return NULL;
2754
8.31k
  if (map->n == 0)
2755
250
    return map;
2756
8.06k
2757
8.06k
  map = isl_map_cow(map);
2758
8.06k
  if (!map)
2759
0
    return NULL;
2760
8.06k
2761
17.1k
  
for (i = 0; 8.06k
i < map->n;
++i9.12k
) {
2762
9.12k
    map->p[i] = isl_basic_map_remove_divs_involving_dims(map->p[i],
2763
9.12k
                type, first, n);
2764
9.12k
    if (!map->p[i])
2765
0
      goto error;
2766
9.12k
  }
2767
8.06k
  return map;
2768
0
error:
2769
0
  isl_map_free(map);
2770
0
  return NULL;
2771
8.06k
}
2772
2773
__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set,
2774
  enum isl_dim_type type, unsigned first, unsigned n)
2775
8.31k
{
2776
8.31k
  return set_from_map(isl_map_remove_divs_involving_dims(set_to_map(set),
2777
8.31k
                    type, first, n));
2778
8.31k
}
2779
2780
/* Does the description of "bmap" depend on the specified dimensions?
2781
 * We also check whether the dimensions appear in any of the div definitions.
2782
 * In principle there is no need for this check.  If the dimensions appear
2783
 * in a div definition, they also appear in the defining constraints of that
2784
 * div.
2785
 */
2786
isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
2787
  enum isl_dim_type type, unsigned first, unsigned n)
2788
59.9k
{
2789
59.9k
  int i;
2790
59.9k
2791
59.9k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2792
0
    return isl_bool_error;
2793
59.9k
2794
59.9k
  first += isl_basic_map_offset(bmap, type);
2795
124k
  for (i = 0; i < bmap->n_eq; 
++i64.9k
)
2796
89.4k
    if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
2797
24.4k
      return isl_bool_true;
2798
82.5k
  
for (i = 0; 35.5k
i < bmap->n_ineq;
++i47.0k
)
2799
51.9k
    if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0)
2800
4.93k
      return isl_bool_true;
2801
35.5k
  
for (i = 0; 30.6k
i < bmap->n_div30.7k
;
++i85
) {
2802
85
    if (isl_int_is_zero(bmap->div[i][0]))
2803
85
      
continue0
;
2804
85
    if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0)
2805
0
      return isl_bool_true;
2806
85
  }
2807
30.6k
2808
30.6k
  return isl_bool_false;
2809
30.6k
}
2810
2811
isl_bool isl_map_involves_dims(__isl_keep isl_map *map,
2812
  enum isl_dim_type type, unsigned first, unsigned n)
2813
4.89k
{
2814
4.89k
  int i;
2815
4.89k
2816
4.89k
  if (isl_map_check_range(map, type, first, n) < 0)
2817
0
    return isl_bool_error;
2818
4.89k
2819
9.80k
  
for (i = 0; 4.89k
i < map->n;
++i4.91k
) {
2820
5.10k
    isl_bool involves = isl_basic_map_involves_dims(map->p[i],
2821
5.10k
                  type, first, n);
2822
5.10k
    if (involves < 0 || involves)
2823
195
      return involves;
2824
5.10k
  }
2825
4.89k
2826
4.89k
  
return isl_bool_false4.69k
;
2827
4.89k
}
2828
2829
isl_bool isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset,
2830
  enum isl_dim_type type, unsigned first, unsigned n)
2831
54.8k
{
2832
54.8k
  return isl_basic_map_involves_dims(bset, type, first, n);
2833
54.8k
}
2834
2835
isl_bool isl_set_involves_dims(__isl_keep isl_set *set,
2836
  enum isl_dim_type type, unsigned first, unsigned n)
2837
4.39k
{
2838
4.39k
  return isl_map_involves_dims(set, type, first, n);
2839
4.39k
}
2840
2841
/* Drop all constraints in bmap that involve any of the dimensions
2842
 * first to first+n-1.
2843
 */
2844
static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
2845
  __isl_take isl_basic_map *bmap, unsigned first, unsigned n)
2846
530k
{
2847
530k
  int i;
2848
530k
2849
530k
  if (n == 0)
2850
90.9k
    return bmap;
2851
439k
2852
439k
  bmap = isl_basic_map_cow(bmap);
2853
439k
2854
439k
  if (!bmap)
2855
0
    return NULL;
2856
439k
2857
442k
  
for (i = bmap->n_eq - 1; 439k
i >= 0;
--i3.24k
) {
2858
3.24k
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
2859
2.76k
      continue;
2860
486
    isl_basic_map_drop_equality(bmap, i);
2861
486
  }
2862
439k
2863
10.7M
  for (i = bmap->n_ineq - 1; i >= 0; 
--i10.3M
) {
2864
10.3M
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
2865
4.29M
      continue;
2866
6.05M
    isl_basic_map_drop_inequality(bmap, i);
2867
6.05M
  }
2868
439k
2869
439k
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2870
439k
  return bmap;
2871
439k
}
2872
2873
/* Drop all constraints in bset that involve any of the dimensions
2874
 * first to first+n-1.
2875
 */
2876
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
2877
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
2878
528k
{
2879
528k
  return isl_basic_map_drop_constraints_involving(bset, first, n);
2880
528k
}
2881
2882
/* Drop all constraints in bmap that do not involve any of the dimensions
2883
 * first to first + n - 1 of the given type.
2884
 */
2885
__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
2886
  __isl_take isl_basic_map *bmap,
2887
  enum isl_dim_type type, unsigned first, unsigned n)
2888
865
{
2889
865
  int i;
2890
865
2891
865
  if (n == 0) {
2892
38
    isl_space *space = isl_basic_map_get_space(bmap);
2893
38
    isl_basic_map_free(bmap);
2894
38
    return isl_basic_map_universe(space);
2895
38
  }
2896
827
  bmap = isl_basic_map_cow(bmap);
2897
827
  if (!bmap)
2898
0
    return NULL;
2899
827
2900
827
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2901
0
    return isl_basic_map_free(bmap);
2902
827
2903
827
  first += isl_basic_map_offset(bmap, type) - 1;
2904
827
2905
945
  for (i = bmap->n_eq - 1; i >= 0; 
--i118
) {
2906
118
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
2907
68
      continue;
2908
50
    isl_basic_map_drop_equality(bmap, i);
2909
50
  }
2910
827
2911
2.72k
  for (i = bmap->n_ineq - 1; i >= 0; 
--i1.89k
) {
2912
1.89k
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
2913
1.58k
      continue;
2914
310
    isl_basic_map_drop_inequality(bmap, i);
2915
310
  }
2916
827
2917
827
  bmap = isl_basic_map_add_known_div_constraints(bmap);
2918
827
  return bmap;
2919
827
}
2920
2921
/* Drop all constraints in bset that do not involve any of the dimensions
2922
 * first to first + n - 1 of the given type.
2923
 */
2924
__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
2925
  __isl_take isl_basic_set *bset,
2926
  enum isl_dim_type type, unsigned first, unsigned n)
2927
700
{
2928
700
  return isl_basic_map_drop_constraints_not_involving_dims(bset,
2929
700
                  type, first, n);
2930
700
}
2931
2932
/* Drop all constraints in bmap that involve any of the dimensions
2933
 * first to first + n - 1 of the given type.
2934
 */
2935
__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
2936
  __isl_take isl_basic_map *bmap,
2937
  enum isl_dim_type type, unsigned first, unsigned n)
2938
59.2k
{
2939
59.2k
  if (!bmap)
2940
0
    return NULL;
2941
59.2k
  if (n == 0)
2942
57.8k
    return bmap;
2943
1.39k
2944
1.39k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
2945
0
    return isl_basic_map_free(bmap);
2946
1.39k
2947
1.39k
  bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
2948
1.39k
  first += isl_basic_map_offset(bmap, type) - 1;
2949
1.39k
  return isl_basic_map_drop_constraints_involving(bmap, first, n);
2950
1.39k
}
2951
2952
/* Drop all constraints in bset that involve any of the dimensions
2953
 * first to first + n - 1 of the given type.
2954
 */
2955
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
2956
  __isl_take isl_basic_set *bset,
2957
  enum isl_dim_type type, unsigned first, unsigned n)
2958
700
{
2959
700
  return isl_basic_map_drop_constraints_involving_dims(bset,
2960
700
                  type, first, n);
2961
700
}
2962
2963
/* Drop constraints from "map" by applying "drop" to each basic map.
2964
 */
2965
static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
2966
  enum isl_dim_type type, unsigned first, unsigned n,
2967
  __isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
2968
    enum isl_dim_type type, unsigned first, unsigned n))
2969
128
{
2970
128
  int i;
2971
128
2972
128
  if (isl_map_check_range(map, type, first, n) < 0)
2973
0
    return isl_map_free(map);
2974
128
2975
128
  map = isl_map_cow(map);
2976
128
  if (!map)
2977
0
    return NULL;
2978
128
2979
325
  
for (i = 0; 128
i < map->n;
++i197
) {
2980
197
    map->p[i] = drop(map->p[i], type, first, n);
2981
197
    if (!map->p[i])
2982
0
      return isl_map_free(map);
2983
197
  }
2984
128
2985
128
  if (map->n > 1)
2986
128
    ISL_F_CLR(map, ISL_MAP_DISJOINT);
2987
128
2988
128
  return map;
2989
128
}
2990
2991
/* Drop all constraints in map that involve any of the dimensions
2992
 * first to first + n - 1 of the given type.
2993
 */
2994
__isl_give isl_map *isl_map_drop_constraints_involving_dims(
2995
  __isl_take isl_map *map,
2996
  enum isl_dim_type type, unsigned first, unsigned n)
2997
91
{
2998
91
  if (n == 0)
2999
7
    return map;
3000
84
  return drop_constraints(map, type, first, n,
3001
84
        &isl_basic_map_drop_constraints_involving_dims);
3002
84
}
3003
3004
/* Drop all constraints in "map" that do not involve any of the dimensions
3005
 * first to first + n - 1 of the given type.
3006
 */
3007
__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
3008
  __isl_take isl_map *map,
3009
  enum isl_dim_type type, unsigned first, unsigned n)
3010
44
{
3011
44
  if (n == 0) {
3012
0
    isl_space *space = isl_map_get_space(map);
3013
0
    isl_map_free(map);
3014
0
    return isl_map_universe(space);
3015
0
  }
3016
44
  return drop_constraints(map, type, first, n,
3017
44
          &isl_basic_map_drop_constraints_not_involving_dims);
3018
44
}
3019
3020
/* Drop all constraints in set that involve any of the dimensions
3021
 * first to first + n - 1 of the given type.
3022
 */
3023
__isl_give isl_set *isl_set_drop_constraints_involving_dims(
3024
  __isl_take isl_set *set,
3025
  enum isl_dim_type type, unsigned first, unsigned n)
3026
67
{
3027
67
  return isl_map_drop_constraints_involving_dims(set, type, first, n);
3028
67
}
3029
3030
/* Drop all constraints in "set" that do not involve any of the dimensions
3031
 * first to first + n - 1 of the given type.
3032
 */
3033
__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
3034
  __isl_take isl_set *set,
3035
  enum isl_dim_type type, unsigned first, unsigned n)
3036
44
{
3037
44
  return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
3038
44
}
3039
3040
/* Does local variable "div" of "bmap" have a complete explicit representation?
3041
 * Having a complete explicit representation requires not only
3042
 * an explicit representation, but also that all local variables
3043
 * that appear in this explicit representation in turn have
3044
 * a complete explicit representation.
3045
 */
3046
isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div)
3047
70.0k
{
3048
70.0k
  int i;
3049
70.0k
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
3050
70.0k
  isl_bool marked;
3051
70.0k
3052
70.0k
  marked = isl_basic_map_div_is_marked_unknown(bmap, div);
3053
70.0k
  if (marked < 0 || marked)
3054
13.0k
    return isl_bool_not(marked);
3055
56.9k
3056
153k
  
for (i = bmap->n_div - 1; 56.9k
i >= 0;
--i96.8k
) {
3057
96.8k
    isl_bool known;
3058
96.8k
3059
96.8k
    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
3060
96.8k
      
continue95.1k
;
3061
1.70k
    known = isl_basic_map_div_is_known(bmap, i);
3062
1.70k
    if (known < 0 || !known)
3063
0
      return known;
3064
1.70k
  }
3065
56.9k
3066
56.9k
  return isl_bool_true;
3067
56.9k
}
3068
3069
/* Remove all divs that are unknown or defined in terms of unknown divs.
3070
 */
3071
__isl_give isl_basic_map *isl_basic_map_remove_unknown_divs(
3072
  __isl_take isl_basic_map *bmap)
3073
194k
{
3074
194k
  int i;
3075
194k
3076
194k
  if (!bmap)
3077
0
    return NULL;
3078
194k
3079
195k
  
for (i = bmap->n_div - 1; 194k
i >= 0;
--i1.12k
) {
3080
1.12k
    if (isl_basic_map_div_is_known(bmap, i))
3081
1.12k
      continue;
3082
0
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
3083
0
    if (!bmap)
3084
0
      return NULL;
3085
0
    i = bmap->n_div;
3086
0
  }
3087
194k
3088
194k
  return bmap;
3089
194k
}
3090
3091
/* Remove all divs that are unknown or defined in terms of unknown divs.
3092
 */
3093
__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
3094
  __isl_take isl_basic_set *bset)
3095
5.84k
{
3096
5.84k
  return isl_basic_map_remove_unknown_divs(bset);
3097
5.84k
}
3098
3099
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
3100
172k
{
3101
172k
  int i;
3102
172k
3103
172k
  if (!map)
3104
0
    return NULL;
3105
172k
  if (map->n == 0)
3106
250
    return map;
3107
172k
3108
172k
  map = isl_map_cow(map);
3109
172k
  if (!map)
3110
0
    return NULL;
3111
172k
3112
360k
  
for (i = 0; 172k
i < map->n;
++i188k
) {
3113
188k
    map->p[i] = isl_basic_map_remove_unknown_divs(map->p[i]);
3114
188k
    if (!map->p[i])
3115
0
      goto error;
3116
188k
  }
3117
172k
  return map;
3118
0
error:
3119
0
  isl_map_free(map);
3120
0
  return NULL;
3121
172k
}
3122
3123
__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
3124
9.04k
{
3125
9.04k
  return set_from_map(isl_map_remove_unknown_divs(set_to_map(set)));
3126
9.04k
}
3127
3128
__isl_give isl_basic_set *isl_basic_set_remove_dims(
3129
  __isl_take isl_basic_set *bset,
3130
  enum isl_dim_type type, unsigned first, unsigned n)
3131
3.09k
{
3132
3.09k
  isl_basic_map *bmap = bset_to_bmap(bset);
3133
3.09k
  bmap = isl_basic_map_remove_dims(bmap, type, first, n);
3134
3.09k
  return bset_from_bmap(bmap);
3135
3.09k
}
3136
3137
__isl_give isl_map *isl_map_remove_dims(__isl_take isl_map *map,
3138
  enum isl_dim_type type, unsigned first, unsigned n)
3139
1.80k
{
3140
1.80k
  int i;
3141
1.80k
3142
1.80k
  if (n == 0)
3143
1.22k
    return map;
3144
574
3145
574
  map = isl_map_cow(map);
3146
574
  if (isl_map_check_range(map, type, first, n) < 0)
3147
0
    return isl_map_free(map);
3148
574
  
3149
1.28k
  
for (i = 0; 574
i < map->n;
++i710
) {
3150
710
    map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
3151
710
      isl_basic_map_offset(map->p[i], type) - 1 + first, n);
3152
710
    if (!map->p[i])
3153
0
      goto error;
3154
710
  }
3155
574
  map = isl_map_drop(map, type, first, n);
3156
574
  return map;
3157
0
error:
3158
0
  isl_map_free(map);
3159
0
  return NULL;
3160
574
}
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.69k
{
3165
1.69k
  return set_from_map(isl_map_remove_dims(set_to_map(bset),
3166
1.69k
            type, first, n));
3167
1.69k
}
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 (!isl_int_is_one(c))
3187
0
      isl_int_print(out, c, 0);
3188
0
    if (pos < 1 + nparam) {
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 (pos < 1 + nparam + in)
3196
0
      fprintf(out, "i%d", pos - 1 - nparam);
3197
0
    else if (pos < 1 + nparam + dim)
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 < len; ++i) {
3214
0
    if (isl_int_sgn(c[i]) * sign <= 0)
3215
0
      continue;
3216
0
    if (!first)
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->extra; ++i) {
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 < n; ++i)
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 + total; ++j) {
3266
0
    if (isl_int_is_zero(exp[j]))
3267
0
      continue;
3268
0
    if (!first && isl_int_is_pos(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_div; ++i) {
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 (!bset) {
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 (!bmap) {
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
20.3k
{
3326
20.3k
  unsigned total;
3327
20.3k
  if (!bmap)
3328
0
    return -1;
3329
20.3k
  total = isl_basic_map_total_dim(bmap);
3330
20.3k
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
3331
20.3k
  isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
3332
20.3k
  isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
3333
20.3k
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
3334
20.3k
  return 0;
3335
20.3k
}
3336
3337
__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *space, int n,
3338
  unsigned flags)
3339
267k
{
3340
267k
  if (!space)
3341
0
    return NULL;
3342
267k
  if (isl_space_dim(space, isl_dim_in) != 0)
3343
267k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
3344
267k
      "set cannot have input dimensions", goto error);
3345
267k
  return isl_map_alloc_space(space, n, flags);
3346
0
error:
3347
0
  isl_space_free(space);
3348
0
  return NULL;
3349
267k
}
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
6.48k
{
3355
6.48k
  int i;
3356
6.48k
  struct isl_map *grown = NULL;
3357
6.48k
3358
6.48k
  if (!map)
3359
0
    return NULL;
3360
6.48k
  isl_assert(map->ctx, n >= 0, goto error);
3361
6.48k
  if (map->n + n <= map->size)
3362
6.09k
    return map;
3363
385
  grown = isl_map_alloc_space(isl_map_get_space(map), map->n + n, map->flags);
3364
385
  if (!grown)
3365
0
    goto error;
3366
885
  
for (i = 0; 385
i < map->n;
++i500
) {
3367
500
    grown->p[i] = isl_basic_map_copy(map->p[i]);
3368
500
    if (!grown->p[i])
3369
0
      goto error;
3370
500
    grown->n++;
3371
500
  }
3372
385
  isl_map_free(map);
3373
385
  return grown;
3374
0
error:
3375
0
  isl_map_free(grown);
3376
0
  isl_map_free(map);
3377
0
  return NULL;
3378
385
}
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
3.07k
{
3384
3.07k
  return set_from_map(isl_map_grow(set_to_map(set), n));
3385
3.07k
}
3386
3387
__isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset)
3388
81.2k
{
3389
81.2k
  return isl_map_from_basic_map(bset);
3390
81.2k
}
3391
3392
__isl_give isl_map *isl_map_from_basic_map(__isl_take isl_basic_map *bmap)
3393
200k
{
3394
200k
  struct isl_map *map;
3395
200k
3396
200k
  if (!bmap)
3397
0
    return NULL;
3398
200k
3399
200k
  map = isl_map_alloc_space(isl_space_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
3400
200k
  return isl_map_add_basic_map(map, bmap);
3401
200k
}
3402
3403
__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
3404
            __isl_take isl_basic_set *bset)
3405
139k
{
3406
139k
  return set_from_map(isl_map_add_basic_map(set_to_map(set),
3407
139k
            bset_to_bmap(bset)));
3408
139k
}
3409
3410
__isl_null isl_set *isl_set_free(__isl_take isl_set *set)
3411
1.58M
{
3412
1.58M
  return isl_map_free(set);
3413
1.58M
}
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 (!set) {
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->n; ++i) {
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 (!map) {
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->n; ++i) {
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
64.5k
{
3459
64.5k
  struct isl_basic_map *bmap_domain;
3460
64.5k
3461
64.5k
  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
3462
0
    goto error;
3463
64.5k
3464
64.5k
  if (isl_space_dim(bset->dim, isl_dim_set) != 0)
3465
64.5k
    isl_assert(bset->ctx,
3466
64.5k
        isl_basic_map_compatible_domain(bmap, bset), goto error);
3467
64.5k
3468
64.5k
  bmap = isl_basic_map_cow(bmap);
3469
64.5k
  if (!bmap)
3470
0
    goto error;
3471
64.5k
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
3472
64.5k
      bset->n_div, bset->n_eq, bset->n_ineq);
3473
64.5k
  bmap_domain = isl_basic_map_from_domain(bset);
3474
64.5k
  bmap = add_constraints(bmap, bmap_domain, 0, 0);
3475
64.5k
3476
64.5k
  bmap = isl_basic_map_simplify(bmap);
3477
64.5k
  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
64.5k
}
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
6.49k
{
3489
6.49k
  isl_bool ok;
3490
6.49k
3491
6.49k
  ok = isl_basic_map_compatible_range(bmap, bset);
3492
6.49k
  if (ok < 0)
3493
0
    return isl_stat_error;
3494
6.49k
  if (!ok)
3495
6.49k
    
isl_die0
(isl_basic_set_get_ctx(bset), isl_error_invalid,
3496
6.49k
      "incompatible spaces", return isl_stat_error);
3497
6.49k
3498
6.49k
  return isl_stat_ok;
3499
6.49k
}
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
6.50k
{
3504
6.50k
  struct isl_basic_map *bmap_range;
3505
6.50k
3506
6.50k
  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
3507
0
    goto error;
3508
6.50k
3509
6.50k
  if (isl_space_dim(bset->dim, isl_dim_set) != 0 &&
3510
6.50k
      
isl_basic_map_check_compatible_range(bmap, bset) < 06.49k
)
3511
0
    goto error;
3512
6.50k
3513
6.50k
  if (isl_basic_set_plain_is_universe(bset)) {
3514
0
    isl_basic_set_free(bset);
3515
0
    return bmap;
3516
0
  }
3517
6.50k
3518
6.50k
  bmap = isl_basic_map_cow(bmap);
3519
6.50k
  if (!bmap)
3520
0
    goto error;
3521
6.50k
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
3522
6.50k
      bset->n_div, bset->n_eq, bset->n_ineq);
3523
6.50k
  bmap_range = bset_to_bmap(bset);
3524
6.50k
  bmap = add_constraints(bmap, bmap_range, 0, 0);
3525
6.50k
3526
6.50k
  bmap = isl_basic_map_simplify(bmap);
3527
6.50k
  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
6.50k
}
3533
3534
isl_bool isl_basic_map_contains(__isl_keep isl_basic_map *bmap,
3535
  __isl_keep isl_vec *vec)
3536
1.52M
{
3537
1.52M
  int i;
3538
1.52M
  unsigned total;
3539
1.52M
  isl_int s;
3540
1.52M
3541
1.52M
  if (!bmap || !vec)
3542
0
    return isl_bool_error;
3543
1.52M
3544
1.52M
  total = 1 + isl_basic_map_total_dim(bmap);
3545
1.52M
  if (total != vec->size)
3546
16.3k
    return isl_bool_false;
3547
1.50M
3548
1.50M
  isl_int_init(s);
3549
1.50M
3550
2.49M
  for (i = 0; i < bmap->n_eq; 
++i988k
) {
3551
1.38M
    isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
3552
1.38M
    if (!isl_int_is_zero(s)) {
3553
398k
      isl_int_clear(s);
3554
398k
      return isl_bool_false;
3555
398k
    }
3556
1.38M
  }
3557
1.50M
3558
6.51M
  
for (i = 0; 1.10M
i < bmap->n_ineq;
++i5.41M
) {
3559
5.77M
    isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
3560
5.77M
    if (isl_int_is_neg(s)) {
3561
367k
      isl_int_clear(s);
3562
367k
      return isl_bool_false;
3563
367k
    }
3564
5.77M
  }
3565
1.10M
3566
1.10M
  
isl_int_clear739k
(s);
3567
739k
3568
739k
  return isl_bool_true;
3569
1.10M
}
3570
3571
isl_bool isl_basic_set_contains(__isl_keep isl_basic_set *bset,
3572
  __isl_keep isl_vec *vec)
3573
837k
{
3574
837k
  return isl_basic_map_contains(bset_to_bmap(bset), vec);
3575
837k
}
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
304k
{
3580
304k
  struct isl_vec *sample = NULL;
3581
304k
3582
304k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
3583
0
    goto error;
3584
304k
  if (isl_space_dim(bmap1->dim, isl_dim_all) ==
3585
304k
        isl_space_dim(bmap1->dim, isl_dim_param) &&
3586
304k
      isl_space_dim(bmap2->dim, isl_dim_all) !=
3587
86.2k
        isl_space_dim(bmap2->dim, isl_dim_param))
3588
0
    return isl_basic_map_intersect(bmap2, bmap1);
3589
304k
3590
304k
  if (isl_space_dim(bmap2->dim, isl_dim_all) !=
3591
304k
          isl_space_dim(bmap2->dim, isl_dim_param))
3592
304k
    isl_assert(bmap1->ctx,
3593
304k
          isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);
3594
304k
3595
304k
  if (isl_basic_map_plain_is_empty(bmap1)) {
3596
42
    isl_basic_map_free(bmap2);
3597
42
    return bmap1;
3598
42
  }
3599
303k
  if (isl_basic_map_plain_is_empty(bmap2)) {
3600
0
    isl_basic_map_free(bmap1);
3601
0
    return bmap2;
3602
0
  }
3603
303k
3604
303k
  if (bmap1->sample &&
3605
303k
      
isl_basic_map_contains(bmap1, bmap1->sample) > 0111k
&&
3606
303k
      
isl_basic_map_contains(bmap2, bmap1->sample) > 0100k
)
3607
38.7k
    sample = isl_vec_copy(bmap1->sample);
3608
265k
  else if (bmap2->sample &&
3609
265k
      
isl_basic_map_contains(bmap1, bmap2->sample) > 096.8k
&&
3610
265k
      
isl_basic_map_contains(bmap2, bmap2->sample) > 021.6k
)
3611
21.4k
    sample = isl_vec_copy(bmap2->sample);
3612
303k
3613
303k
  bmap1 = isl_basic_map_cow(bmap1);
3614
303k
  if (!bmap1)
3615
0
    goto error;
3616
303k
  bmap1 = isl_basic_map_extend_space(bmap1, isl_space_copy(bmap1->dim),
3617
303k
      bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
3618
303k
  bmap1 = add_constraints(bmap1, bmap2, 0, 0);
3619
303k
3620
303k
  if (!bmap1)
3621
0
    isl_vec_free(sample);
3622
303k
  else if (sample) {
3623
60.2k
    isl_vec_free(bmap1->sample);
3624
60.2k
    bmap1->sample = sample;
3625
60.2k
  }
3626
303k
3627
303k
  bmap1 = isl_basic_map_simplify(bmap1);
3628
303k
  return isl_basic_map_finalize(bmap1);
3629
0
error:
3630
0
  if (sample)
3631
0
    isl_vec_free(sample);
3632
0
  isl_basic_map_free(bmap1);
3633
0
  isl_basic_map_free(bmap2);
3634
0
  return NULL;
3635
303k
}
3636
3637
struct isl_basic_set *isl_basic_set_intersect(
3638
    struct isl_basic_set *bset1, struct isl_basic_set *bset2)
3639
73.6k
{
3640
73.6k
  return bset_from_bmap(isl_basic_map_intersect(bset_to_bmap(bset1),
3641
73.6k
              bset_to_bmap(bset2)));
3642
73.6k
}
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
41.4k
{
3658
41.4k
  isl_assert(map1->ctx, map1->n == 1, goto error);
3659
41.4k
  isl_assert(map2->ctx, map1->n == 1, goto error);
3660
41.4k
  isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
3661
41.4k
  isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
3662
41.4k
3663
41.4k
  if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
3664
2.76k
    return isl_map_intersect(map2, map1);
3665
38.6k
3666
38.6k
  map1 = isl_map_cow(map1);
3667
38.6k
  if (!map1)
3668
0
    goto error;
3669
38.6k
  if (isl_map_plain_is_empty(map1)) {
3670
0
    isl_map_free(map2);
3671
0
    return map1;
3672
0
  }
3673
38.6k
  map1->p[0] = isl_basic_map_cow(map1->p[0]);
3674
38.6k
  if (map2->p[0]->n_eq == 1)
3675
19.6k
    map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
3676
19.0k
  else
3677
19.0k
    map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
3678
19.0k
              map2->p[0]->ineq[0]);
3679
38.6k
3680
38.6k
  map1->p[0] = isl_basic_map_simplify(map1->p[0]);
3681
38.6k
  map1->p[0] = isl_basic_map_finalize(map1->p[0]);
3682
38.6k
  if (!map1->p[0])
3683
0
    goto error;
3684
38.6k
3685
38.6k
  if (isl_basic_map_plain_is_empty(map1->p[0])) {
3686
4.98k
    isl_basic_map_free(map1->p[0]);
3687
4.98k
    map1->n = 0;
3688
4.98k
  }
3689
38.6k
3690
38.6k
  isl_map_free(map2);
3691
38.6k
3692
38.6k
  return map1;
3693
0
error:
3694
0
  isl_map_free(map1);
3695
0
  isl_map_free(map2);
3696
0
  return NULL;
3697
38.6k
}
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
410k
{
3705
410k
  unsigned flags = 0;
3706
410k
  isl_map *result;
3707
410k
  int i, j;
3708
410k
3709
410k
  if (!map1 || !map2)
3710
0
    goto error;
3711
410k
3712
410k
  if ((isl_map_plain_is_empty(map1) ||
3713
410k
       
isl_map_plain_is_universe(map2)397k
) &&
3714
410k
      
isl_space_is_equal(map1->dim, map2->dim)223k
) {
3715
205k
    isl_map_free(map2);
3716
205k
    return map1;
3717
205k
  }
3718
205k
  if ((isl_map_plain_is_empty(map2) ||
3719
205k
       
isl_map_plain_is_universe(map1)200k
) &&
3720
205k
      
isl_space_is_equal(map1->dim, map2->dim)112k
) {
3721
85.7k
    isl_map_free(map1);
3722
85.7k
    return map2;
3723
85.7k
  }
3724
119k
3725
119k
  if (map1->n == 1 && 
map2->n == 1106k
&&
3726
119k
      
map1->p[0]->n_div == 0100k
&&
map2->p[0]->n_div == 096.8k
&&
3727
119k
      
isl_space_is_equal(map1->dim, map2->dim)95.9k
&&
3728
119k
      
(68.2k
map1->p[0]->n_eq + map1->p[0]->n_ineq == 168.2k
||
3729
68.2k
       
map2->p[0]->n_eq + map2->p[0]->n_ineq == 158.0k
))
3730
41.4k
    return map_intersect_add_constraint(map1, map2);
3731
77.9k
3732
77.9k
  if (isl_space_dim(map2->dim, isl_dim_all) !=
3733
77.9k
        isl_space_dim(map2->dim, isl_dim_param))
3734
77.9k
    isl_assert(map1->ctx,
3735
77.9k
          isl_space_is_equal(map1->dim, map2->dim), goto error);
3736
77.9k
3737
77.9k
  if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
3738
77.9k
      
ISL_F_ISSET62.1k
(map2, ISL_MAP_DISJOINT))
3739
77.9k
    
ISL_FL_SET58.3k
(flags, ISL_MAP_DISJOINT);
3740
77.9k
3741
77.9k
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
3742
77.9k
        map1->n * map2->n, flags);
3743
77.9k
  if (!result)
3744
0
    goto error;
3745
181k
  
for (i = 0; 77.9k
i < map1->n;
++i103k
)
3746
289k
    
for (j = 0; 103k
j < map2->n;
++j185k
) {
3747
185k
      struct isl_basic_map *part;
3748
185k
      part = isl_basic_map_intersect(
3749
185k
            isl_basic_map_copy(map1->p[i]),
3750
185k
            isl_basic_map_copy(map2->p[j]));
3751
185k
      if (isl_basic_map_is_empty(part) < 0)
3752
0
        part = isl_basic_map_free(part);
3753
185k
      result = isl_map_add_basic_map(result, part);
3754
185k
      if (!result)
3755
0
        goto error;
3756
185k
    }
3757
77.9k
  isl_map_free(map1);
3758
77.9k
  isl_map_free(map2);
3759
77.9k
  return result;
3760
0
error:
3761
0
  isl_map_free(map1);
3762
0
  isl_map_free(map2);
3763
0
  return NULL;
3764
77.9k
}
3765
3766
static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
3767
  __isl_take isl_map *map2)
3768
362k
{
3769
362k
  if (!map1 || !map2)
3770
0
    goto error;
3771
362k
  if (!isl_space_is_equal(map1->dim, map2->dim))
3772
362k
    
isl_die0
(isl_map_get_ctx(map1), isl_error_invalid,
3773
362k
      "spaces don't match", goto error);
3774
362k
  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
362k
}
3780
3781
__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
3782
  __isl_take isl_map *map2)
3783
362k
{
3784
362k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect);
3785
362k
}
3786
3787
struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
3788
290k
{
3789
290k
  return set_from_map(isl_map_intersect(set_to_map(set1),
3790
290k
                set_to_map(set2)));
3791
290k
}
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
47.9k
{
3799
47.9k
  return map_intersect_internal(map, params);
3800
47.9k
}
3801
3802
__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1,
3803
  __isl_take isl_map *map2)
3804
47.9k
{
3805
47.9k
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect_params);
3806
47.9k
}
3807
3808
__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
3809
    __isl_take isl_set *params)
3810
16.2k
{
3811
16.2k
  return isl_map_intersect_params(set, params);
3812
16.2k
}
3813
3814
__isl_give isl_basic_map *isl_basic_map_reverse(__isl_take isl_basic_map *bmap)
3815
180k
{
3816
180k
  isl_space *space;
3817
180k
  unsigned pos, n1, n2;
3818
180k
3819
180k
  if (!bmap)
3820
0
    return NULL;
3821
180k
  bmap = isl_basic_map_cow(bmap);
3822
180k
  if (!bmap)
3823
0
    return NULL;
3824
180k
  space = isl_space_reverse(isl_space_copy(bmap->dim));
3825
180k
  pos = isl_basic_map_offset(bmap, isl_dim_in);
3826
180k
  n1 = isl_basic_map_dim(bmap, isl_dim_in);
3827
180k
  n2 = isl_basic_map_dim(bmap, isl_dim_out);
3828
180k
  bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
3829
180k
  return isl_basic_map_reset_space(bmap, space);
3830
180k
}
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
47.2k
{
3835
47.2k
  isl_space *space;
3836
47.2k
3837
47.2k
  if (!bmap)
3838
0
    return NULL;
3839
47.2k
  if (!isl_space_is_named_or_nested(bmap->dim, type))
3840
43.1k
    return bmap;
3841
4.11k
3842
4.11k
  space = isl_basic_map_get_space(bmap);
3843
4.11k
  space = isl_space_reset(space, type);
3844
4.11k
  bmap = isl_basic_map_reset_space(bmap, space);
3845
4.11k
  return bmap;
3846
4.11k
}
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
79.3k
{
3852
79.3k
  isl_bool rational;
3853
79.3k
  isl_space *res_dim;
3854
79.3k
  struct isl_basic_map *res;
3855
79.3k
  struct isl_dim_map *dim_map;
3856
79.3k
  unsigned total, off;
3857
79.3k
  enum isl_dim_type t;
3858
79.3k
3859
79.3k
  if (n == 0)
3860
19.2k
    return basic_map_space_reset(bmap, type);
3861
60.1k
3862
60.1k
  if (!bmap)
3863
0
    return NULL;
3864
60.1k
3865
60.1k
  res_dim = isl_space_insert_dims(isl_basic_map_get_space(bmap), type, pos, n);
3866
60.1k
3867
60.1k
  total = isl_basic_map_total_dim(bmap) + n;
3868
60.1k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
3869
60.1k
  off = 0;
3870
240k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t180k
) {
3871
180k
    if (t != type) {
3872
120k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
3873
120k
    } else {
3874
60.1k
      unsigned size = isl_basic_map_dim(bmap, t);
3875
60.1k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3876
60.1k
            0, pos, off);
3877
60.1k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
3878
60.1k
            pos, size - pos, off + pos + n);
3879
60.1k
    }
3880
180k
    off += isl_space_dim(res_dim, t);
3881
180k
  }
3882
60.1k
  isl_dim_map_div(dim_map, bmap, off);
3883
60.1k
3884
60.1k
  res = isl_basic_map_alloc_space(res_dim,
3885
60.1k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
3886
60.1k
  rational = isl_basic_map_is_rational(bmap);
3887
60.1k
  if (rational < 0)
3888
0
    res = isl_basic_map_free(res);
3889
60.1k
  if (rational)
3890
0
    res = isl_basic_map_set_rational(res);
3891
60.1k
  if (isl_basic_map_plain_is_empty(bmap)) {
3892
1.58k
    isl_basic_map_free(bmap);
3893
1.58k
    free(dim_map);
3894
1.58k
    return isl_basic_map_set_to_empty(res);
3895
1.58k
  }
3896
58.5k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
3897
58.5k
  return isl_basic_map_finalize(res);
3898
58.5k
}
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
28.9k
{
3910
28.9k
  if (!bmap)
3911
0
    return NULL;
3912
28.9k
  return isl_basic_map_insert_dims(bmap, type,
3913
28.9k
          isl_basic_map_dim(bmap, type), n);
3914
28.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
26.6k
{
3919
26.6k
  if (!bset)
3920
0
    return NULL;
3921
26.6k
  isl_assert(bset->ctx, type != isl_dim_in, goto error);
3922
26.6k
  return isl_basic_map_add_dims(bset, type, n);
3923
0
error:
3924
0
  isl_basic_set_free(bset);
3925
0
  return NULL;
3926
26.6k
}
3927
3928
static __isl_give isl_map *map_space_reset(__isl_take isl_map *map,
3929
  enum isl_dim_type type)
3930
41.2k
{
3931
41.2k
  isl_space *space;
3932
41.2k
3933
41.2k
  if (!map || !isl_space_is_named_or_nested(map->dim, type))
3934
9.12k
    return map;
3935
32.1k
3936
32.1k
  space = isl_map_get_space(map);
3937
32.1k
  space = isl_space_reset(space, type);
3938
32.1k
  map = isl_map_reset_space(map, space);
3939
32.1k
  return map;
3940
32.1k
}
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
35.1k
{
3945
35.1k
  int i;
3946
35.1k
3947
35.1k
  if (n == 0)
3948
2.91k
    return map_space_reset(map, type);
3949
32.1k
3950
32.1k
  map = isl_map_cow(map);
3951
32.1k
  if (!map)
3952
0
    return NULL;
3953
32.1k
3954
32.1k
  map->dim = isl_space_insert_dims(map->dim, type, pos, n);
3955
32.1k
  if (!map->dim)
3956
0
    goto error;
3957
32.1k
3958
65.6k
  
for (i = 0; 32.1k
i < map->n;
++i33.4k
) {
3959
33.4k
    map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n);
3960
33.4k
    if (!map->p[i])
3961
0
      goto error;
3962
33.4k
  }
3963
32.1k
3964
32.1k
  return map;
3965
0
error:
3966
0
  isl_map_free(map);
3967
0
  return NULL;
3968
32.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
7.19k
{
3973
7.19k
  return isl_map_insert_dims(set, type, pos, n);
3974
7.19k
}
3975
3976
__isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map,
3977
    enum isl_dim_type type, unsigned n)
3978
27.9k
{
3979
27.9k
  if (!map)
3980
0
    return NULL;
3981
27.9k
  return isl_map_insert_dims(map, type, isl_map_dim(map, type), n);
3982
27.9k
}
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.3k
{
3987
22.3k
  if (!set)
3988
0
    return NULL;
3989
22.3k
  isl_assert(set->ctx, type != isl_dim_in, goto error);
3990
22.3k
  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.3k
}
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
1.04k
{
4001
1.04k
  struct isl_dim_map *dim_map;
4002
1.04k
  struct isl_basic_map *res;
4003
1.04k
  enum isl_dim_type t;
4004
1.04k
  unsigned total, off;
4005
1.04k
4006
1.04k
  if (!bmap)
4007
0
    return NULL;
4008
1.04k
  if (n == 0) {
4009
647
    bmap = isl_basic_map_reset(bmap, src_type);
4010
647
    bmap = isl_basic_map_reset(bmap, dst_type);
4011
647
    return bmap;
4012
647
  }
4013
401
4014
401
  if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0)
4015
0
    return isl_basic_map_free(bmap);
4016
401
4017
401
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4018
0
    return bmap;
4019
401
4020
401
  isl_assert(bmap->ctx, dst_type != src_type, goto error);
4021
401
4022
401
  if (pos(bmap->dim, dst_type) + dst_pos ==
4023
401
      pos(bmap->dim, src_type) + src_pos +
4024
401
              ((src_type < dst_type) ? 
n111
:
0290
)) {
4025
287
    bmap = isl_basic_map_cow(bmap);
4026
287
    if (!bmap)
4027
0
      return NULL;
4028
287
4029
287
    bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4030
287
            src_type, src_pos, n);
4031
287
    if (!bmap->dim)
4032
0
      goto error;
4033
287
4034
287
    bmap = isl_basic_map_finalize(bmap);
4035
287
4036
287
    return bmap;
4037
287
  }
4038
114
4039
114
  total = isl_basic_map_total_dim(bmap);
4040
114
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4041
114
4042
114
  off = 0;
4043
456
  for (t = isl_dim_param; t <= isl_dim_out; 
++t342
) {
4044
342
    unsigned size = isl_space_dim(bmap->dim, t);
4045
342
    if (t == dst_type) {
4046
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4047
114
              0, dst_pos, off);
4048
114
      off += dst_pos;
4049
114
      isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
4050
114
              src_pos, n, off);
4051
114
      off += n;
4052
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4053
114
              dst_pos, size - dst_pos, off);
4054
114
      off += size - dst_pos;
4055
228
    } else if (t == src_type) {
4056
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4057
114
              0, src_pos, off);
4058
114
      off += src_pos;
4059
114
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4060
114
          src_pos + n, size - src_pos - n, off);
4061
114
      off += size - src_pos - n;
4062
114
    } else {
4063
114
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4064
114
      off += size;
4065
114
    }
4066
342
  }
4067
114
  isl_dim_map_div(dim_map, bmap, off);
4068
114
4069
114
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4070
114
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4071
114
  bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4072
114
  if (!bmap)
4073
0
    goto error;
4074
114
4075
114
  bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
4076
114
          src_type, src_pos, n);
4077
114
  if (!bmap->dim)
4078
0
    goto error;
4079
114
4080
114
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
4081
114
  bmap = isl_basic_map_gauss(bmap, NULL);
4082
114
  bmap = isl_basic_map_finalize(bmap);
4083
114
4084
114
  return bmap;
4085
0
error:
4086
0
  isl_basic_map_free(bmap);
4087
0
  return NULL;
4088
114
}
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_assert(set->ctx, dst_type != isl_dim_in, goto error);
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
157
{
4118
157
  int i;
4119
157
4120
157
  if (n == 0) {
4121
0
    map = isl_map_reset(map, src_type);
4122
0
    map = isl_map_reset(map, dst_type);
4123
0
    return map;
4124
0
  }
4125
157
4126
157
  if (isl_map_check_range(map, src_type, src_pos, n))
4127
0
    return isl_map_free(map);
4128
157
4129
157
  if (dst_type == src_type && 
dst_pos == src_pos0
)
4130
0
    return map;
4131
157
4132
157
  isl_assert(map->ctx, dst_type != src_type, goto error);
4133
157
4134
157
  map = isl_map_cow(map);
4135
157
  if (!map)
4136
0
    return NULL;
4137
157
4138
157
  map->dim = isl_space_move_dims(map->dim, dst_type, dst_pos, src_type, src_pos, n);
4139
157
  if (!map->dim)
4140
0
    goto error;
4141
157
4142
325
  
for (i = 0; 157
i < map->n;
++i168
) {
4143
168
    map->p[i] = isl_basic_map_move_dims(map->p[i],
4144
168
            dst_type, dst_pos,
4145
168
            src_type, src_pos, n);
4146
168
    if (!map->p[i])
4147
0
      goto error;
4148
168
  }
4149
157
4150
157
  return map;
4151
0
error:
4152
0
  isl_map_free(map);
4153
0
  return NULL;
4154
157
}
4155
4156
/* Move the specified dimensions to the last columns right before
4157
 * the divs.  Don't change the dimension specification of bmap.
4158
 * That's the responsibility of the caller.
4159
 */
4160
static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
4161
  enum isl_dim_type type, unsigned first, unsigned n)
4162
119k
{
4163
119k
  struct isl_dim_map *dim_map;
4164
119k
  struct isl_basic_map *res;
4165
119k
  enum isl_dim_type t;
4166
119k
  unsigned total, off;
4167
119k
4168
119k
  if (!bmap)
4169
0
    return NULL;
4170
119k
  if (pos(bmap->dim, type) + first + n ==
4171
119k
        1 + isl_space_dim(bmap->dim, isl_dim_all))
4172
97.7k
    return bmap;
4173
21.7k
4174
21.7k
  total = isl_basic_map_total_dim(bmap);
4175
21.7k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4176
21.7k
4177
21.7k
  off = 0;
4178
87.1k
  for (t = isl_dim_param; t <= isl_dim_out; 
++t65.3k
) {
4179
65.3k
    unsigned size = isl_space_dim(bmap->dim, t);
4180
65.3k
    if (t == type) {
4181
21.7k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4182
21.7k
              0, first, off);
4183
21.7k
      off += first;
4184
21.7k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4185
21.7k
              first, n, total - bmap->n_div - n);
4186
21.7k
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
4187
21.7k
              first + n, size - (first + n), off);
4188
21.7k
      off += size - (first + n);
4189
43.5k
    } else {
4190
43.5k
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
4191
43.5k
      off += size;
4192
43.5k
    }
4193
65.3k
  }
4194
21.7k
  isl_dim_map_div(dim_map, bmap, off + n);
4195
21.7k
4196
21.7k
  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
4197
21.7k
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
4198
21.7k
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
4199
21.7k
  return res;
4200
21.7k
}
4201
4202
/* Insert "n" rows in the divs of "bmap".
4203
 *
4204
 * The number of columns is not changed, which means that the last
4205
 * dimensions of "bmap" are being reintepreted as the new divs.
4206
 * The space of "bmap" is not adjusted, however, which means
4207
 * that "bmap" is left in an inconsistent state.  Removing "n" dimensions
4208
 * from the space of "bmap" is the responsibility of the caller.
4209
 */
4210
static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap,
4211
  int n)
4212
119k
{
4213
119k
  int i;
4214
119k
  size_t row_size;
4215
119k
  isl_int **new_div;
4216
119k
  isl_int *old;
4217
119k
4218
119k
  bmap = isl_basic_map_cow(bmap);
4219
119k
  if (!bmap)
4220
0
    return NULL;
4221
119k
4222
119k
  row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + bmap->extra;
4223
119k
  old = bmap->block2.data;
4224
119k
  bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
4225
119k
          (bmap->extra + n) * (1 + row_size));
4226
119k
  if (!bmap->block2.data)
4227
0
    return isl_basic_map_free(bmap);
4228
119k
  new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
4229
119k
  if (!new_div)
4230
0
    return isl_basic_map_free(bmap);
4231
334k
  
for (i = 0; 119k
i < n;
++i215k
) {
4232
215k
    new_div[i] = bmap->block2.data +
4233
215k
        (bmap->extra + i) * (1 + row_size);
4234
215k
    isl_seq_clr(new_div[i], 1 + row_size);
4235
215k
  }
4236
126k
  for (i = 0; i < bmap->extra; 
++i6.81k
)
4237
6.81k
    new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
4238
119k
  free(bmap->div);
4239
119k
  bmap->div = new_div;
4240
119k
  bmap->n_div += n;
4241
119k
  bmap->extra += n;
4242
119k
4243
119k
  return bmap;
4244
119k
}
4245
4246
/* Drop constraints from "bmap" that only involve the variables
4247
 * of "type" in the range [first, first + n] that are not related
4248
 * to any of the variables outside that interval.
4249
 * These constraints cannot influence the values for the variables
4250
 * outside the interval, except in case they cause "bmap" to be empty.
4251
 * Only drop the constraints if "bmap" is known to be non-empty.
4252
 */
4253
static __isl_give isl_basic_map *drop_irrelevant_constraints(
4254
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
4255
  unsigned first, unsigned n)
4256
119k
{
4257
119k
  int i;
4258
119k
  int *groups;
4259
119k
  unsigned dim, n_div;
4260
119k
  isl_bool non_empty;
4261
119k
4262
119k
  non_empty = isl_basic_map_plain_is_non_empty(bmap);
4263
119k
  if (non_empty < 0)
4264
0
    return isl_basic_map_free(bmap);
4265
119k
  if (!non_empty)
4266
65.5k
    return bmap;
4267
53.9k
4268
53.9k
  dim = isl_basic_map_dim(bmap, isl_dim_all);
4269
53.9k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
4270
53.9k
  groups = isl_calloc_array(isl_basic_map_get_ctx(bmap), int, dim);
4271
53.9k
  if (!groups)
4272
0
    return isl_basic_map_free(bmap);
4273
53.9k
  first += isl_basic_map_offset(bmap, type) - 1;
4274
252k
  for (i = 0; i < first; 
++i198k
)
4275
198k
    groups[i] = -1;
4276
75.4k
  for (i = first + n; i < dim - n_div; 
++i21.4k
)
4277
21.4k
    groups[i] = -1;
4278
53.9k
4279
53.9k
  bmap = isl_basic_map_drop_unrelated_constraints(bmap, groups);
4280
53.9k
4281
53.9k
  return bmap;
4282
53.9k
}
4283
4284
/* Turn the n dimensions of type type, starting at first
4285
 * into existentially quantified variables.
4286
 *
4287
 * If a subset of the projected out variables are unrelated
4288
 * to any of the variables that remain, then the constraints
4289
 * involving this subset are simply dropped first.
4290
 */
4291
__isl_give isl_basic_map *isl_basic_map_project_out(
4292
    __isl_take isl_basic_map *bmap,
4293
    enum isl_dim_type type, unsigned first, unsigned n)
4294
147k
{
4295
147k
  isl_bool empty;
4296
147k
4297
147k
  if (n == 0)
4298
28.0k
    return basic_map_space_reset(bmap, type);
4299
119k
  if (type == isl_dim_div)
4300
119k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4301
119k
      "cannot project out existentially quantified variables",
4302
119k
      return isl_basic_map_free(bmap));
4303
119k
4304
119k
  empty = isl_basic_map_plain_is_empty(bmap);
4305
119k
  if (empty < 0)
4306
0
    return isl_basic_map_free(bmap);
4307
119k
  if (empty)
4308
1.58k
    bmap = isl_basic_map_set_to_empty(bmap);
4309
119k
4310
119k
  bmap = drop_irrelevant_constraints(bmap, type, first, n);
4311
119k
  if (!bmap)
4312
0
    return NULL;
4313
119k
4314
119k
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
4315
119k
    
return isl_basic_map_remove_dims(bmap, type, first, n)39
;
4316
119k
4317
119k
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
4318
0
    return isl_basic_map_free(bmap);
4319
119k
4320
119k
  bmap = move_last(bmap, type, first, n);
4321
119k
  bmap = isl_basic_map_cow(bmap);
4322
119k
  bmap = insert_div_rows(bmap, n);
4323
119k
  if (!bmap)
4324
0
    return NULL;
4325
119k
4326
119k
  bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
4327
119k
  if (!bmap->dim)
4328
0
    goto error;
4329
119k
  bmap = isl_basic_map_simplify(bmap);
4330
119k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4331
119k
  return isl_basic_map_finalize(bmap);
4332
0
error:
4333
0
  isl_basic_map_free(bmap);
4334
0
  return NULL;
4335
119k
}
4336
4337
/* Turn the n dimensions of type type, starting at first
4338
 * into existentially quantified variables.
4339
 */
4340
struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
4341
    enum isl_dim_type type, unsigned first, unsigned n)
4342
19.4k
{
4343
19.4k
  return bset_from_bmap(isl_basic_map_project_out(bset_to_bmap(bset),
4344
19.4k
              type, first, n));
4345
19.4k
}
4346
4347
/* Turn the n dimensions of type type, starting at first
4348
 * into existentially quantified variables.
4349
 */
4350
__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
4351
    enum isl_dim_type type, unsigned first, unsigned n)
4352
104k
{
4353
104k
  int i;
4354
104k
4355
104k
  if (n == 0)
4356
38.3k
    return map_space_reset(map, type);
4357
65.9k
4358
65.9k
  if (isl_map_check_range(map, type, first, n) < 0)
4359
0
    return isl_map_free(map);
4360
65.9k
4361
65.9k
  map = isl_map_cow(map);
4362
65.9k
  if (!map)
4363
0
    return NULL;
4364
65.9k
4365
65.9k
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
4366
65.9k
  if (!map->dim)
4367
0
    goto error;
4368
65.9k
4369
109k
  
for (i = 0; 65.9k
i < map->n;
++i43.4k
) {
4370
43.4k
    map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
4371
43.4k
    if (!map->p[i])
4372
0
      goto error;
4373
43.4k
  }
4374
65.9k
4375
65.9k
  return map;
4376
0
error:
4377
0
  isl_map_free(map);
4378
0
  return NULL;
4379
65.9k
}
4380
4381
/* Turn all the dimensions of type "type", except the "n" starting at "first"
4382
 * into existentially quantified variables.
4383
 */
4384
__isl_give isl_map *isl_map_project_onto(__isl_take isl_map *map,
4385
  enum isl_dim_type type, unsigned first, unsigned n)
4386
0
{
4387
0
  unsigned dim;
4388
0
4389
0
  if (isl_map_check_range(map, type, first, n) < 0)
4390
0
    return isl_map_free(map);
4391
0
  dim = isl_map_dim(map, type);
4392
0
  map = isl_map_project_out(map, type, first + n, dim - (first + n));
4393
0
  map = isl_map_project_out(map, type, 0, first);
4394
0
  return map;
4395
0
}
4396
4397
/* Turn the n dimensions of type type, starting at first
4398
 * into existentially quantified variables.
4399
 */
4400
__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
4401
    enum isl_dim_type type, unsigned first, unsigned n)
4402
23.1k
{
4403
23.1k
  return set_from_map(isl_map_project_out(set_to_map(set),
4404
23.1k
            type, first, n));
4405
23.1k
}
4406
4407
/* Return a map that projects the elements in "set" onto their
4408
 * "n" set dimensions starting at "first".
4409
 * "type" should be equal to isl_dim_set.
4410
 */
4411
__isl_give isl_map *isl_set_project_onto_map(__isl_take isl_set *set,
4412
  enum isl_dim_type type, unsigned first, unsigned n)
4413
371
{
4414
371
  int i;
4415
371
  int dim;
4416
371
  isl_map *map;
4417
371
4418
371
  if (!set)
4419
0
    return NULL;
4420
371
  if (type != isl_dim_set)
4421
371
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4422
371
      "only set dimensions can be projected out", goto error);
4423
371
  dim = isl_set_dim(set, isl_dim_set);
4424
371
  if (first + n > dim || first + n < first)
4425
371
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4426
371
      "index out of bounds", goto error);
4427
371
4428
371
  map = isl_map_from_domain(set);
4429
371
  map = isl_map_add_dims(map, isl_dim_out, n);
4430
742
  for (i = 0; i < n; 
++i371
)
4431
371
    map = isl_map_equate(map, isl_dim_in, first + i,
4432
371
          isl_dim_out, i);
4433
371
  return map;
4434
0
error:
4435
0
  isl_set_free(set);
4436
0
  return NULL;
4437
371
}
4438
4439
static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
4440
94.8k
{
4441
94.8k
  int i, j;
4442
94.8k
4443
243k
  for (i = 0; i < n; 
++i148k
) {
4444
148k
    j = isl_basic_map_alloc_div(bmap);
4445
148k
    if (j < 0)
4446
0
      goto error;
4447
148k
    isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
4448
148k
  }
4449
94.8k
  return bmap;
4450
0
error:
4451
0
  isl_basic_map_free(bmap);
4452
0
  return NULL;
4453
94.8k
}
4454
4455
struct isl_basic_map *isl_basic_map_apply_range(
4456
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4457
91.7k
{
4458
91.7k
  isl_space *dim_result = NULL;
4459
91.7k
  struct isl_basic_map *bmap;
4460
91.7k
  unsigned n_in, n_out, n, nparam, total, pos;
4461
91.7k
  struct isl_dim_map *dim_map1, *dim_map2;
4462
91.7k
4463
91.7k
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4464
0
    goto error;
4465
91.7k
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_out,
4466
91.7k
            bmap2->dim, isl_dim_in))
4467
91.7k
    
isl_die0
(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4468
91.7k
      "spaces don't match", goto error);
4469
91.7k
4470
91.7k
  dim_result = isl_space_join(isl_space_copy(bmap1->dim),
4471
91.7k
          isl_space_copy(bmap2->dim));
4472
91.7k
4473
91.7k
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4474
91.7k
  n_out = isl_basic_map_dim(bmap2, isl_dim_out);
4475
91.7k
  n = isl_basic_map_dim(bmap1, isl_dim_out);
4476
91.7k
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4477
91.7k
4478
91.7k
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
4479
91.7k
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4480
91.7k
  dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
4481
91.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4482
91.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
4483
91.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4484
91.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
4485
91.7k
  isl_dim_map_div(dim_map1, bmap1, pos += n_out);
4486
91.7k
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4487
91.7k
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4488
91.7k
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4489
91.7k
4490
91.7k
  bmap = isl_basic_map_alloc_space(dim_result,
4491
91.7k
      bmap1->n_div + bmap2->n_div + n,
4492
91.7k
      bmap1->n_eq + bmap2->n_eq,
4493
91.7k
      bmap1->n_ineq + bmap2->n_ineq);
4494
91.7k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4495
91.7k
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4496
91.7k
  bmap = add_divs(bmap, n);
4497
91.7k
  bmap = isl_basic_map_simplify(bmap);
4498
91.7k
  bmap = isl_basic_map_drop_redundant_divs(bmap);
4499
91.7k
  return isl_basic_map_finalize(bmap);
4500
0
error:
4501
0
  isl_basic_map_free(bmap1);
4502
0
  isl_basic_map_free(bmap2);
4503
0
  return NULL;
4504
91.7k
}
4505
4506
struct isl_basic_set *isl_basic_set_apply(
4507
    struct isl_basic_set *bset, struct isl_basic_map *bmap)
4508
4.41k
{
4509
4.41k
  if (!bset || !bmap)
4510
0
    goto error;
4511
4.41k
4512
4.41k
  isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
4513
4.41k
        goto error);
4514
4.41k
4515
4.41k
  return bset_from_bmap(isl_basic_map_apply_range(bset_to_bmap(bset),
4516
4.41k
              bmap));
4517
0
error:
4518
0
  isl_basic_set_free(bset);
4519
0
  isl_basic_map_free(bmap);
4520
0
  return NULL;
4521
4.41k
}
4522
4523
struct isl_basic_map *isl_basic_map_apply_domain(
4524
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4525
0
{
4526
0
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
4527
0
    goto error;
4528
0
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_in,
4529
0
          bmap2->dim, isl_dim_in))
4530
0
    isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
4531
0
      "spaces don't match", goto error);
4532
0
4533
0
  bmap1 = isl_basic_map_reverse(bmap1);
4534
0
  bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
4535
0
  return isl_basic_map_reverse(bmap1);
4536
0
error:
4537
0
  isl_basic_map_free(bmap1);
4538
0
  isl_basic_map_free(bmap2);
4539
0
  return NULL;
4540
0
}
4541
4542
/* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
4543
 * A \cap B -> f(A) + f(B)
4544
 */
4545
__isl_give isl_basic_map *isl_basic_map_sum(__isl_take isl_basic_map *bmap1,
4546
  __isl_take isl_basic_map *bmap2)
4547
24
{
4548
24
  unsigned n_in, n_out, nparam, total, pos;
4549
24
  struct isl_basic_map *bmap = NULL;
4550
24
  struct isl_dim_map *dim_map1, *dim_map2;
4551
24
  int i;
4552
24
4553
24
  if (!bmap1 || !bmap2)
4554
0
    goto error;
4555
24
4556
24
  isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim),
4557
24
    goto error);
4558
24
4559
24
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
4560
24
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
4561
24
  n_out = isl_basic_map_dim(bmap1, isl_dim_out);
4562
24
4563
24
  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
4564
24
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
4565
24
  dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
4566
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
4567
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
4568
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
4569
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
4570
24
  isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
4571
24
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
4572
24
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
4573
24
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);
4574
24
4575
24
  bmap = isl_basic_map_alloc_space(isl_space_copy(bmap1->dim),
4576
24
      bmap1->n_div + bmap2->n_div + 2 * n_out,
4577
24
      bmap1->n_eq + bmap2->n_eq + n_out,
4578
24
      bmap1->n_ineq + bmap2->n_ineq);
4579
48
  for (i = 0; i < n_out; 
++i24
) {
4580
24
    int j = isl_basic_map_alloc_equality(bmap);
4581
24
    if (j < 0)
4582
0
      goto error;
4583
24
    isl_seq_clr(bmap->eq[j], 1+total);
4584
24
    isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
4585
24
    isl_int_set_si(bmap->eq[j][1+pos+i], 1);
4586
24
    isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
4587
24
  }
4588
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
4589
24
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
4590
24
  bmap = add_divs(bmap, 2 * n_out);
4591
24
4592
24
  bmap = isl_basic_map_simplify(bmap);
4593
24
  return isl_basic_map_finalize(bmap);
4594
0
error:
4595
0
  isl_basic_map_free(bmap);
4596
0
  isl_basic_map_free(bmap1);
4597
0
  isl_basic_map_free(bmap2);
4598
0
  return NULL;
4599
24
}
4600
4601
/* Given two maps A -> f(A) and B -> g(B), construct a map
4602
 * A \cap B -> f(A) + f(B)
4603
 */
4604
__isl_give isl_map *isl_map_sum(__isl_take isl_map *map1,
4605
  __isl_take isl_map *map2)
4606
24
{
4607
24
  struct isl_map *result;
4608
24
  int i, j;
4609
24
4610
24
  if (!map1 || !map2)
4611
0
    goto error;
4612
24
4613
24
  isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
4614
24
4615
24
  result = isl_map_alloc_space(isl_space_copy(map1->dim),
4616
24
        map1->n * map2->n, 0);
4617
24
  if (!result)
4618
0
    goto error;
4619
48
  
for (i = 0; 24
i < map1->n;
++i24
)
4620
48
    
for (j = 0; 24
j < map2->n;
++j24
) {
4621
24
      struct isl_basic_map *part;
4622
24
      part = isl_basic_map_sum(
4623
24
            isl_basic_map_copy(map1->p[i]),
4624
24
            isl_basic_map_copy(map2->p[j]));
4625
24
      if (isl_basic_map_is_empty(part))
4626
0
        isl_basic_map_free(part);
4627
24
      else
4628
24
        result = isl_map_add_basic_map(result, part);
4629
24
      if (!result)
4630
0
        goto error;
4631
24
    }
4632
24
  isl_map_free(map1);
4633
24
  isl_map_free(map2);
4634
24
  return result;
4635
0
error:
4636
0
  isl_map_free(map1);
4637
0
  isl_map_free(map2);
4638
0
  return NULL;
4639
24
}
4640
4641
__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
4642
  __isl_take isl_set *set2)
4643
0
{
4644
0
  return set_from_map(isl_map_sum(set_to_map(set1), set_to_map(set2)));
4645
0
}
4646
4647
/* Given a basic map A -> f(A), construct A -> -f(A).
4648
 */
4649
__isl_give isl_basic_map *isl_basic_map_neg(__isl_take isl_basic_map *bmap)
4650
1
{
4651
1
  int i, j;
4652
1
  unsigned off, n;
4653
1
4654
1
  bmap = isl_basic_map_cow(bmap);
4655
1
  if (!bmap)
4656
0
    return NULL;
4657
1
4658
1
  n = isl_basic_map_dim(bmap, isl_dim_out);
4659
1
  off = isl_basic_map_offset(bmap, isl_dim_out);
4660
2
  for (i = 0; i < bmap->n_eq; 
++i1
)
4661
2
    
for (j = 0; 1
j < n;
++j1
)
4662
1
      isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
4663
3
  for (i = 0; i < bmap->n_ineq; 
++i2
)
4664
4
    
for (j = 0; 2
j < n;
++j2
)
4665
2
      isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
4666
1
  for (i = 0; i < bmap->n_div; 
++i0
)
4667
0
    for (j = 0; j < n; ++j)
4668
0
      isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
4669
1
  bmap = isl_basic_map_gauss(bmap, NULL);
4670
1
  return isl_basic_map_finalize(bmap);
4671
1
}
4672
4673
__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset)
4674
0
{
4675
0
  return isl_basic_map_neg(bset);
4676
0
}
4677
4678
/* Given a map A -> f(A), construct A -> -f(A).
4679
 */
4680
__isl_give isl_map *isl_map_neg(__isl_take isl_map *map)
4681
1
{
4682
1
  int i;
4683
1
4684
1
  map = isl_map_cow(map);
4685
1
  if (!map)
4686
0
    return NULL;
4687
1
4688
2
  
for (i = 0; 1
i < map->n;
++i1
) {
4689
1
    map->p[i] = isl_basic_map_neg(map->p[i]);
4690
1
    if (!map->p[i])
4691
0
      goto error;
4692
1
  }
4693
1
4694
1
  return map;
4695
0
error:
4696
0
  isl_map_free(map);
4697
0
  return NULL;
4698
1
}
4699
4700
__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
4701
0
{
4702
0
  return set_from_map(isl_map_neg(set_to_map(set)));
4703
0
}
4704
4705
/* Given a basic map A -> f(A) and an integer d, construct a basic map
4706
 * A -> floor(f(A)/d).
4707
 */
4708
__isl_give isl_basic_map *isl_basic_map_floordiv(__isl_take isl_basic_map *bmap,
4709
    isl_int d)
4710
3.01k
{
4711
3.01k
  unsigned n_in, n_out, nparam, total, pos;
4712
3.01k
  struct isl_basic_map *result = NULL;
4713
3.01k
  struct isl_dim_map *dim_map;
4714
3.01k
  int i;
4715
3.01k
4716
3.01k
  if (!bmap)
4717
0
    return NULL;
4718
3.01k
4719
3.01k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4720
3.01k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4721
3.01k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4722
3.01k
4723
3.01k
  total = nparam + n_in + n_out + bmap->n_div + n_out;
4724
3.01k
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
4725
3.01k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
4726
3.01k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
4727
3.01k
  isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
4728
3.01k
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);
4729
3.01k
4730
3.01k
  result = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
4731
3.01k
      bmap->n_div + n_out,
4732
3.01k
      bmap->n_eq, bmap->n_ineq + 2 * n_out);
4733
3.01k
  result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map);
4734
3.01k
  result = add_divs(result, n_out);
4735
6.04k
  for (i = 0; i < n_out; 
++i3.03k
) {
4736
3.03k
    int j;
4737
3.03k
    j = isl_basic_map_alloc_inequality(result);
4738
3.03k
    if (j < 0)
4739
0
      goto error;
4740
3.03k
    isl_seq_clr(result->ineq[j], 1+total);
4741
3.03k
    isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
4742
3.03k
    isl_int_set_si(result->ineq[j][1+pos+i], 1);
4743
3.03k
    j = isl_basic_map_alloc_inequality(result);
4744
3.03k
    if (j < 0)
4745
0
      goto error;
4746
3.03k
    isl_seq_clr(result->ineq[j], 1+total);
4747
3.03k
    isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
4748
3.03k
    isl_int_set_si(result->ineq[j][1+pos+i], -1);
4749
3.03k
    isl_int_sub_ui(result->ineq[j][0], d, 1);
4750
3.03k
  }
4751
3.01k
4752
3.01k
  result = isl_basic_map_simplify(result);
4753
3.01k
  return isl_basic_map_finalize(result);
4754
0
error:
4755
0
  isl_basic_map_free(result);
4756
0
  return NULL;
4757
3.01k
}
4758
4759
/* Given a map A -> f(A) and an integer d, construct a map
4760
 * A -> floor(f(A)/d).
4761
 */
4762
__isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
4763
2.96k
{
4764
2.96k
  int i;
4765
2.96k
4766
2.96k
  map = isl_map_cow(map);
4767
2.96k
  if (!map)
4768
0
    return NULL;
4769
2.96k
4770
2.96k
  ISL_F_CLR(map, ISL_MAP_DISJOINT);
4771
2.96k
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
4772
5.98k
  for (i = 0; i < map->n; 
++i3.01k
) {
4773
3.01k
    map->p[i] = isl_basic_map_floordiv(map->p[i], d);
4774
3.01k
    if (!map->p[i])
4775
0
      goto error;
4776
3.01k
  }
4777
2.96k
4778
2.96k
  return map;
4779
0
error:
4780
0
  isl_map_free(map);
4781
0
  return NULL;
4782
2.96k
}
4783
4784
/* Given a map A -> f(A) and an integer d, construct a map
4785
 * A -> floor(f(A)/d).
4786
 */
4787
__isl_give isl_map *isl_map_floordiv_val(__isl_take isl_map *map,
4788
  __isl_take isl_val *d)
4789
2.96k
{
4790
2.96k
  if (!map || !d)
4791
0
    goto error;
4792
2.96k
  if (!isl_val_is_int(d))
4793
2.96k
    
isl_die0
(isl_val_get_ctx(d), isl_error_invalid,
4794
2.96k
      "expecting integer denominator", goto error);
4795
2.96k
  map = isl_map_floordiv(map, d->n);
4796
2.96k
  isl_val_free(d);
4797
2.96k
  return map;
4798
0
error:
4799
0
  isl_map_free(map);
4800
0
  isl_val_free(d);
4801
0
  return NULL;
4802
2.96k
}
4803
4804
static __isl_give isl_basic_map *var_equal(__isl_take isl_basic_map *bmap,
4805
  unsigned pos)
4806
12.7k
{
4807
12.7k
  int i;
4808
12.7k
  unsigned nparam;
4809
12.7k
  unsigned n_in;
4810
12.7k
4811
12.7k
  i = isl_basic_map_alloc_equality(bmap);
4812
12.7k
  if (i < 0)
4813
0
    goto error;
4814
12.7k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4815
12.7k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4816
12.7k
  isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
4817
12.7k
  isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
4818
12.7k
  isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
4819
12.7k
  return isl_basic_map_finalize(bmap);
4820
0
error:
4821
0
  isl_basic_map_free(bmap);
4822
0
  return NULL;
4823
12.7k
}
4824
4825
/* Add a constraint to "bmap" expressing i_pos < o_pos
4826
 */
4827
static __isl_give isl_basic_map *var_less(__isl_take isl_basic_map *bmap,
4828
  unsigned pos)
4829
1.46k
{
4830
1.46k
  int i;
4831
1.46k
  unsigned nparam;
4832
1.46k
  unsigned n_in;
4833
1.46k
4834
1.46k
  i = isl_basic_map_alloc_inequality(bmap);
4835
1.46k
  if (i < 0)
4836
0
    goto error;
4837
1.46k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4838
1.46k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4839
1.46k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4840
1.46k
  isl_int_set_si(bmap->ineq[i][0], -1);
4841
1.46k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4842
1.46k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4843
1.46k
  return isl_basic_map_finalize(bmap);
4844
0
error:
4845
0
  isl_basic_map_free(bmap);
4846
0
  return NULL;
4847
1.46k
}
4848
4849
/* Add a constraint to "bmap" expressing i_pos <= o_pos
4850
 */
4851
static __isl_give isl_basic_map *var_less_or_equal(
4852
  __isl_take isl_basic_map *bmap, unsigned pos)
4853
2.06k
{
4854
2.06k
  int i;
4855
2.06k
  unsigned nparam;
4856
2.06k
  unsigned n_in;
4857
2.06k
4858
2.06k
  i = isl_basic_map_alloc_inequality(bmap);
4859
2.06k
  if (i < 0)
4860
0
    goto error;
4861
2.06k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4862
2.06k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4863
2.06k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4864
2.06k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
4865
2.06k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
4866
2.06k
  return isl_basic_map_finalize(bmap);
4867
0
error:
4868
0
  isl_basic_map_free(bmap);
4869
0
  return NULL;
4870
2.06k
}
4871
4872
/* Add a constraint to "bmap" expressing i_pos > o_pos
4873
 */
4874
static __isl_give isl_basic_map *var_more(__isl_take isl_basic_map *bmap,
4875
  unsigned pos)
4876
16.1k
{
4877
16.1k
  int i;
4878
16.1k
  unsigned nparam;
4879
16.1k
  unsigned n_in;
4880
16.1k
4881
16.1k
  i = isl_basic_map_alloc_inequality(bmap);
4882
16.1k
  if (i < 0)
4883
0
    goto error;
4884
16.1k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4885
16.1k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4886
16.1k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4887
16.1k
  isl_int_set_si(bmap->ineq[i][0], -1);
4888
16.1k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4889
16.1k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4890
16.1k
  return isl_basic_map_finalize(bmap);
4891
0
error:
4892
0
  isl_basic_map_free(bmap);
4893
0
  return NULL;
4894
16.1k
}
4895
4896
/* Add a constraint to "bmap" expressing i_pos >= o_pos
4897
 */
4898
static __isl_give isl_basic_map *var_more_or_equal(
4899
  __isl_take isl_basic_map *bmap, unsigned pos)
4900
1.40k
{
4901
1.40k
  int i;
4902
1.40k
  unsigned nparam;
4903
1.40k
  unsigned n_in;
4904
1.40k
4905
1.40k
  i = isl_basic_map_alloc_inequality(bmap);
4906
1.40k
  if (i < 0)
4907
0
    goto error;
4908
1.40k
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
4909
1.40k
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
4910
1.40k
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
4911
1.40k
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
4912
1.40k
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
4913
1.40k
  return isl_basic_map_finalize(bmap);
4914
0
error:
4915
0
  isl_basic_map_free(bmap);
4916
0
  return NULL;
4917
1.40k
}
4918
4919
__isl_give isl_basic_map *isl_basic_map_equal(
4920
  __isl_take isl_space *dim, unsigned n_equal)
4921
2.87k
{
4922
2.87k
  int i;
4923
2.87k
  struct isl_basic_map *bmap;
4924
2.87k
  bmap = isl_basic_map_alloc_space(dim, 0, n_equal, 0);
4925
2.87k
  if (!bmap)
4926
0
    return NULL;
4927
5.12k
  
for (i = 0; 2.87k
i < n_equal &&
bmap2.25k
;
++i2.25k
)
4928
2.25k
    bmap = var_equal(bmap, i);
4929
2.87k
  return isl_basic_map_finalize(bmap);
4930
2.87k
}
4931
4932
/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
4933
 */
4934
__isl_give isl_basic_map *isl_basic_map_less_at(__isl_take isl_space *dim,
4935
  unsigned pos)
4936
1.46k
{
4937
1.46k
  int i;
4938
1.46k
  struct isl_basic_map *bmap;
4939
1.46k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4940
1.46k
  if (!bmap)
4941
0
    return NULL;
4942
2.29k
  
for (i = 0; 1.46k
i < pos &&
bmap826
;
++i826
)
4943
826
    bmap = var_equal(bmap, i);
4944
1.46k
  if (bmap)
4945
1.46k
    bmap = var_less(bmap, pos);
4946
1.46k
  return isl_basic_map_finalize(bmap);
4947
1.46k
}
4948
4949
/* Return a relation on "dim" expressing i_[0..pos] <<= o_[0..pos]
4950
 */
4951
__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
4952
  __isl_take isl_space *dim, unsigned pos)
4953
2.06k
{
4954
2.06k
  int i;
4955
2.06k
  isl_basic_map *bmap;
4956
2.06k
4957
2.06k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4958
3.13k
  for (i = 0; i < pos; 
++i1.07k
)
4959
1.07k
    bmap = var_equal(bmap, i);
4960
2.06k
  bmap = var_less_or_equal(bmap, pos);
4961
2.06k
  return isl_basic_map_finalize(bmap);
4962
2.06k
}
4963
4964
/* Return a relation on "dim" expressing i_pos > o_pos
4965
 */
4966
__isl_give isl_basic_map *isl_basic_map_more_at(__isl_take isl_space *dim,
4967
  unsigned pos)
4968
16.1k
{
4969
16.1k
  int i;
4970
16.1k
  struct isl_basic_map *bmap;
4971
16.1k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4972
16.1k
  if (!bmap)
4973
0
    return NULL;
4974
22.8k
  
for (i = 0; 16.1k
i < pos &&
bmap6.67k
;
++i6.67k
)
4975
6.67k
    bmap = var_equal(bmap, i);
4976
16.1k
  if (bmap)
4977
16.1k
    bmap = var_more(bmap, pos);
4978
16.1k
  return isl_basic_map_finalize(bmap);
4979
16.1k
}
4980
4981
/* Return a relation on "dim" expressing i_[0..pos] >>= o_[0..pos]
4982
 */
4983
__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
4984
  __isl_take isl_space *dim, unsigned pos)
4985
1.40k
{
4986
1.40k
  int i;
4987
1.40k
  isl_basic_map *bmap;
4988
1.40k
4989
1.40k
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
4990
3.32k
  for (i = 0; i < pos; 
++i1.92k
)
4991
1.92k
    bmap = var_equal(bmap, i);
4992
1.40k
  bmap = var_more_or_equal(bmap, pos);
4993
1.40k
  return isl_basic_map_finalize(bmap);
4994
1.40k
}
4995
4996
static __isl_give isl_map *map_lex_lte_first(__isl_take isl_space *dims,
4997
  unsigned n, int equal)
4998
2.30k
{
4999
2.30k
  struct isl_map *map;
5000
2.30k
  int i;
5001
2.30k
5002
2.30k
  if (n == 0 && 
equal22
)
5003
11
    return isl_map_universe(dims);
5004
2.29k
5005
2.29k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
5006
2.29k
5007
3.53k
  for (i = 0; i + 1 < n; 
++i1.24k
)
5008
1.24k
    map = isl_map_add_basic_map(map,
5009
1.24k
          isl_basic_map_less_at(isl_space_copy(dims), i));
5010
2.29k
  if (n > 0) {
5011
2.28k
    if (equal)
5012
2.06k
      map = isl_map_add_basic_map(map,
5013
2.06k
            isl_basic_map_less_or_equal_at(dims, n - 1));
5014
221
    else
5015
221
      map = isl_map_add_basic_map(map,
5016
221
            isl_basic_map_less_at(dims, n - 1));
5017
2.28k
  } else
5018
11
    isl_space_free(dims);
5019
2.29k
5020
2.29k
  return map;
5021
2.29k
}
5022
5023
static __isl_give isl_map *map_lex_lte(__isl_take isl_space *dims, int equal)
5024
2.22k
{
5025
2.22k
  if (!dims)
5026
4
    return NULL;
5027
2.22k
  return map_lex_lte_first(dims, dims->n_out, equal);
5028
2.22k
}
5029
5030
__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *dim, unsigned n)
5031
73
{
5032
73
  return map_lex_lte_first(dim, n, 0);
5033
73
}
5034
5035
__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *dim, unsigned n)
5036
10
{
5037
10
  return map_lex_lte_first(dim, n, 1);
5038
10
}
5039
5040
__isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_dim)
5041
159
{
5042
159
  return map_lex_lte(isl_space_map_from_set(set_dim), 0);
5043
159
}
5044
5045
__isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_dim)
5046
2.06k
{
5047
2.06k
  return map_lex_lte(isl_space_map_from_set(set_dim), 1);
5048
2.06k
}
5049
5050
static __isl_give isl_map *map_lex_gte_first(__isl_take isl_space *dims,
5051
  unsigned n, int equal)
5052
1.67k
{
5053
1.67k
  struct isl_map *map;
5054
1.67k
  int i;
5055
1.67k
5056
1.67k
  if (n == 0 && 
equal0
)
5057
0
    return isl_map_universe(dims);
5058
1.67k
5059
1.67k
  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);
5060
1.67k
5061
3.90k
  for (i = 0; i + 1 < n; 
++i2.23k
)
5062
2.23k
    map = isl_map_add_basic_map(map,
5063
2.23k
          isl_basic_map_more_at(isl_space_copy(dims), i));
5064
1.67k
  if (n > 0) {
5065
1.67k
    if (equal)
5066
1.40k
      map = isl_map_add_basic_map(map,
5067
1.40k
            isl_basic_map_more_or_equal_at(dims, n - 1));
5068
268
    else
5069
268
      map = isl_map_add_basic_map(map,
5070
268
            isl_basic_map_more_at(dims, n - 1));
5071
1.67k
  } else
5072
0
    isl_space_free(dims);
5073
1.67k
5074
1.67k
  return map;
5075
1.67k
}
5076
5077
static __isl_give isl_map *map_lex_gte(__isl_take isl_space *dims, int equal)
5078
1.67k
{
5079
1.67k
  if (!dims)
5080
2
    return NULL;
5081
1.67k
  return map_lex_gte_first(dims, dims->n_out, equal);
5082
1.67k
}
5083
5084
__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *dim, unsigned n)
5085
0
{
5086
0
  return map_lex_gte_first(dim, n, 0);
5087
0
}
5088
5089
__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *dim, unsigned n)
5090
0
{
5091
0
  return map_lex_gte_first(dim, n, 1);
5092
0
}
5093
<