Coverage Report

Created: 2017-03-28 09:59

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