Coverage Report

Created: 2018-04-24 22:41

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_constraint.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
11
 */
12
13
#include <isl_map_private.h>
14
#include <isl_constraint_private.h>
15
#include <isl_space_private.h>
16
#include <isl_seq.h>
17
#include <isl_aff_private.h>
18
#include <isl_local_space_private.h>
19
#include <isl_val_private.h>
20
#include <isl_vec_private.h>
21
22
#include <bset_to_bmap.c>
23
#include <bset_from_bmap.c>
24
25
#undef BASE
26
#define BASE constraint
27
28
#include <isl_list_templ.c>
29
30
isl_ctx *isl_constraint_get_ctx(__isl_keep isl_constraint *c)
31
38.1k
{
32
38.1k
  return c ? isl_local_space_get_ctx(c->ls) : NULL;
33
38.1k
}
34
35
static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
36
63.4k
{
37
63.4k
  return isl_local_space_dim(c->ls, type);
38
63.4k
}
39
40
static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
41
3.90k
{
42
3.90k
  return isl_local_space_offset(c->ls, type);
43
3.90k
}
44
45
static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
46
              enum isl_dim_type type)
47
659
{
48
659
  return type == isl_dim_div ? 
1 + isl_space_dim(bmap->dim, isl_dim_all)270
49
659
           : 
1 + isl_space_offset(bmap->dim, type)389
;
50
659
}
51
52
static unsigned basic_set_offset(struct isl_basic_set *bset,
53
              enum isl_dim_type type)
54
0
{
55
0
  isl_space *dim = bset->dim;
56
0
  switch (type) {
57
0
  case isl_dim_param: return 1;
58
0
  case isl_dim_in:  return 1 + dim->nparam;
59
0
  case isl_dim_out: return 1 + dim->nparam + dim->n_in;
60
0
  case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
61
0
  default:    return 0;
62
0
  }
63
0
}
64
65
__isl_give isl_constraint *isl_constraint_alloc_vec(int eq,
66
  __isl_take isl_local_space *ls, __isl_take isl_vec *v)
67
78.0k
{
68
78.0k
  isl_constraint *constraint;
69
78.0k
70
78.0k
  if (!ls || !v)
71
0
    goto error;
72
78.0k
73
78.0k
  constraint = isl_alloc_type(isl_vec_get_ctx(v), isl_constraint);
74
78.0k
  if (!constraint)
75
0
    goto error;
76
78.0k
77
78.0k
  constraint->ref = 1;
78
78.0k
  constraint->eq = eq;
79
78.0k
  constraint->ls = ls;
80
78.0k
  constraint->v = v;
81
78.0k
82
78.0k
  return constraint;
83
0
error:
84
0
  isl_local_space_free(ls);
85
0
  isl_vec_free(v);
86
0
  return NULL;
87
78.0k
}
88
89
__isl_give isl_constraint *isl_constraint_alloc(int eq,
90
  __isl_take isl_local_space *ls)
91
3.47k
{
92
3.47k
  isl_ctx *ctx;
93
3.47k
  isl_vec *v;
94
3.47k
95
3.47k
  if (!ls)
96
0
    return NULL;
97
3.47k
98
3.47k
  ctx = isl_local_space_get_ctx(ls);
99
3.47k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
100
3.47k
  v = isl_vec_clr(v);
101
3.47k
  return isl_constraint_alloc_vec(eq, ls, v);
102
3.47k
}
103
104
struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
105
  isl_int **line)
106
41.3k
{
107
41.3k
  int eq;
108
41.3k
  isl_ctx *ctx;
109
41.3k
  isl_vec *v;
110
41.3k
  isl_local_space *ls = NULL;
111
41.3k
  isl_constraint *constraint;
112
41.3k
113
41.3k
  if (!bmap || !line)
114
0
    goto error;
115
41.3k
116
41.3k
  eq = line >= bmap->eq;
117
41.3k
118
41.3k
  ctx = isl_basic_map_get_ctx(bmap);
119
41.3k
  ls = isl_basic_map_get_local_space(bmap);
120
41.3k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
121
41.3k
  if (!v)
122
0
    goto error;
123
41.3k
  isl_seq_cpy(v->el, line[0], v->size);
124
41.3k
  constraint = isl_constraint_alloc_vec(eq, ls, v);
125
41.3k
126
41.3k
  isl_basic_map_free(bmap);
127
41.3k
  return constraint;
128
0
error:
129
0
  isl_local_space_free(ls);
130
0
  isl_basic_map_free(bmap);
131
0
  return NULL;
132
41.3k
}
133
134
struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
135
  isl_int **line)
136
17
{
137
17
  return isl_basic_map_constraint(bset_to_bmap(bset), line);
138
17
}
139
140
__isl_give isl_constraint *isl_constraint_alloc_equality(
141
  __isl_take isl_local_space *ls)
142
2.24k
{
143
2.24k
  return isl_constraint_alloc(1, ls);
144
2.24k
}
145
146
__isl_give isl_constraint *isl_constraint_alloc_inequality(
147
  __isl_take isl_local_space *ls)
148
1.23k
{
149
1.23k
  return isl_constraint_alloc(0, ls);
150
1.23k
}
151
152
struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
153
2.11k
{
154
2.11k
  if (!c)
155
0
    return NULL;
156
2.11k
157
2.11k
  return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
158
2.11k
            isl_vec_copy(c->v));
159
2.11k
}
160
161
struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
162
16.5k
{
163
16.5k
  if (!c)
164
0
    return NULL;
165
16.5k
166
16.5k
  if (c->ref == 1)
167
14.4k
    return c;
168
2.11k
  c->ref--;
169
2.11k
  return isl_constraint_dup(c);
170
2.11k
}
171
172
struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
173
12.8k
{
174
12.8k
  if (!constraint)
175
0
    return NULL;
176
12.8k
177
12.8k
  constraint->ref++;
178
12.8k
  return constraint;
179
12.8k
}
180
181
__isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c)
182
88.8k
{
183
88.8k
  if (!c)
184
3
    return NULL;
185
88.8k
186
88.8k
  if (--c->ref > 0)
187
10.7k
    return NULL;
188
78.0k
189
78.0k
  isl_local_space_free(c->ls);
190
78.0k
  isl_vec_free(c->v);
191
78.0k
  free(c);
192
78.0k
193
78.0k
  return NULL;
194
78.0k
}
195
196
/* Return the number of constraints in "bmap", i.e., the
197
 * number of times isl_basic_map_foreach_constraint will
198
 * call the callback.
199
 */
200
int isl_basic_map_n_constraint(__isl_keep isl_basic_map *bmap)
201
1.59k
{
202
1.59k
  if (!bmap)
203
0
    return -1;
204
1.59k
205
1.59k
  return bmap->n_eq + bmap->n_ineq;
206
1.59k
}
207
208
/* Return the number of constraints in "bset", i.e., the
209
 * number of times isl_basic_set_foreach_constraint will
210
 * call the callback.
211
 */
212
int isl_basic_set_n_constraint(__isl_keep isl_basic_set *bset)
213
2
{
214
2
  return isl_basic_map_n_constraint(bset);
215
2
}
216
217
isl_stat isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
218
  isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user)
219
10.1k
{
220
10.1k
  int i;
221
10.1k
  struct isl_constraint *c;
222
10.1k
223
10.1k
  if (!bmap)
224
0
    return isl_stat_error;
225
10.1k
226
10.1k
  isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
227
10.1k
      return isl_stat_error);
228
10.1k
229
20.0k
  
for (i = 0; 10.1k
i < bmap->n_eq;
++i9.91k
) {
230
9.91k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
231
9.91k
            &bmap->eq[i]);
232
9.91k
    if (!c)
233
0
      return isl_stat_error;
234
9.91k
    if (fn(c, user) < 0)
235
3
      return isl_stat_error;
236
9.91k
  }
237
10.1k
238
41.4k
  
for (i = 0; 10.1k
i < bmap->n_ineq;
++i31.2k
) {
239
31.2k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
240
31.2k
            &bmap->ineq[i]);
241
31.2k
    if (!c)
242
0
      return isl_stat_error;
243
31.2k
    if (fn(c, user) < 0)
244
3
      return isl_stat_error;
245
31.2k
  }
246
10.1k
247
10.1k
  
return isl_stat_ok10.1k
;
248
10.1k
}
249
250
isl_stat isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
251
  isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user)
252
8.57k
{
253
8.57k
  return isl_basic_map_foreach_constraint(bset_to_bmap(bset), fn, user);
254
8.57k
}
255
256
/* Add the constraint to the list that "user" points to, if it is not
257
 * a div constraint.
258
 */
259
static isl_stat collect_constraint(__isl_take isl_constraint *constraint,
260
  void *user)
261
2.11k
{
262
2.11k
  isl_constraint_list **list = user;
263
2.11k
264
2.11k
  if (isl_constraint_is_div_constraint(constraint))
265
32
    isl_constraint_free(constraint);
266
2.08k
  else
267
2.08k
    *list = isl_constraint_list_add(*list, constraint);
268
2.11k
269
2.11k
  return isl_stat_ok;
270
2.11k
}
271
272
/* Return a list of constraints that, when combined, are equivalent
273
 * to "bmap".  The input is required to have only known divs.
274
 *
275
 * There is no need to include the div constraints as they are
276
 * implied by the div expressions.
277
 */
278
__isl_give isl_constraint_list *isl_basic_map_get_constraint_list(
279
  __isl_keep isl_basic_map *bmap)
280
1.59k
{
281
1.59k
  int n;
282
1.59k
  int known;
283
1.59k
  isl_ctx *ctx;
284
1.59k
  isl_constraint_list *list;
285
1.59k
286
1.59k
  known = isl_basic_map_divs_known(bmap);
287
1.59k
  if (known < 0)
288
0
    return NULL;
289
1.59k
  ctx = isl_basic_map_get_ctx(bmap);
290
1.59k
  if (!known)
291
1.59k
    
isl_die0
(ctx, isl_error_invalid,
292
1.59k
      "input involves unknown divs", return NULL);
293
1.59k
294
1.59k
  n = isl_basic_map_n_constraint(bmap);
295
1.59k
  list = isl_constraint_list_alloc(ctx, n);
296
1.59k
  if (isl_basic_map_foreach_constraint(bmap,
297
1.59k
              &collect_constraint, &list) < 0)
298
0
    list = isl_constraint_list_free(list);
299
1.59k
300
1.59k
  return list;
301
1.59k
}
302
303
/* Return a list of constraints that, when combined, are equivalent
304
 * to "bset".  The input is required to have only known divs.
305
 */
306
__isl_give isl_constraint_list *isl_basic_set_get_constraint_list(
307
  __isl_keep isl_basic_set *bset)
308
1.59k
{
309
1.59k
  return isl_basic_map_get_constraint_list(bset);
310
1.59k
}
311
312
int isl_constraint_is_equal(struct isl_constraint *constraint1,
313
  struct isl_constraint *constraint2)
314
0
{
315
0
  int equal;
316
0
317
0
  if (!constraint1 || !constraint2)
318
0
    return 0;
319
0
  if (constraint1->eq != constraint2->eq)
320
0
    return 0;
321
0
  equal = isl_local_space_is_equal(constraint1->ls, constraint2->ls);
322
0
  if (equal < 0 || !equal)
323
0
    return equal;
324
0
  return isl_vec_is_equal(constraint1->v, constraint2->v);
325
0
}
326
327
struct isl_basic_map *isl_basic_map_add_constraint(
328
  struct isl_basic_map *bmap, struct isl_constraint *constraint)
329
4.90k
{
330
4.90k
  isl_ctx *ctx;
331
4.90k
  isl_space *dim;
332
4.90k
  int equal_space;
333
4.90k
334
4.90k
  if (!bmap || !constraint)
335
0
    goto error;
336
4.90k
337
4.90k
  ctx = isl_constraint_get_ctx(constraint);
338
4.90k
  dim = isl_constraint_get_space(constraint);
339
4.90k
  equal_space = isl_space_is_equal(bmap->dim, dim);
340
4.90k
  isl_space_free(dim);
341
4.90k
  isl_assert(ctx, equal_space, goto error);
342
4.90k
343
4.90k
  bmap = isl_basic_map_intersect(bmap,
344
4.90k
        isl_basic_map_from_constraint(constraint));
345
4.90k
  return bmap;
346
0
error:
347
0
  isl_basic_map_free(bmap);
348
0
  isl_constraint_free(constraint);
349
0
  return NULL;
350
4.90k
}
351
352
struct isl_basic_set *isl_basic_set_add_constraint(
353
  struct isl_basic_set *bset, struct isl_constraint *constraint)
354
4.43k
{
355
4.43k
  return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset),
356
4.43k
                  constraint));
357
4.43k
}
358
359
__isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
360
  __isl_take isl_constraint *constraint)
361
7.40k
{
362
7.40k
  isl_basic_map *bmap;
363
7.40k
364
7.40k
  bmap = isl_basic_map_from_constraint(constraint);
365
7.40k
  map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
366
7.40k
367
7.40k
  return map;
368
7.40k
}
369
370
__isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
371
  __isl_take isl_constraint *constraint)
372
5.06k
{
373
5.06k
  return isl_map_add_constraint(set, constraint);
374
5.06k
}
375
376
__isl_give isl_space *isl_constraint_get_space(
377
  __isl_keep isl_constraint *constraint)
378
4.90k
{
379
4.90k
  return constraint ? isl_local_space_get_space(constraint->ls) : NULL;
380
4.90k
}
381
382
__isl_give isl_local_space *isl_constraint_get_local_space(
383
  __isl_keep isl_constraint *constraint)
384
0
{
385
0
  return constraint ? isl_local_space_copy(constraint->ls) : NULL;
386
0
}
387
388
int isl_constraint_dim(struct isl_constraint *constraint,
389
  enum isl_dim_type type)
390
63.4k
{
391
63.4k
  if (!constraint)
392
0
    return -1;
393
63.4k
  return n(constraint, type);
394
63.4k
}
395
396
isl_bool isl_constraint_involves_dims(__isl_keep isl_constraint *constraint,
397
  enum isl_dim_type type, unsigned first, unsigned n)
398
18.0k
{
399
18.0k
  int i;
400
18.0k
  isl_ctx *ctx;
401
18.0k
  int *active = NULL;
402
18.0k
  isl_bool involves = isl_bool_false;
403
18.0k
404
18.0k
  if (!constraint)
405
0
    return isl_bool_error;
406
18.0k
  if (n == 0)
407
0
    return isl_bool_false;
408
18.0k
409
18.0k
  ctx = isl_constraint_get_ctx(constraint);
410
18.0k
  if (first + n > isl_constraint_dim(constraint, type))
411
18.0k
    
isl_die0
(ctx, isl_error_invalid,
412
18.0k
      "range out of bounds", return isl_bool_error);
413
18.0k
414
18.0k
  active = isl_local_space_get_active(constraint->ls,
415
18.0k
              constraint->v->el + 1);
416
18.0k
  if (!active)
417
0
    goto error;
418
18.0k
419
18.0k
  first += isl_local_space_offset(constraint->ls, type) - 1;
420
29.2k
  for (i = 0; i < n; 
++i11.2k
)
421
18.0k
    if (active[first + i]) {
422
6.78k
      involves = isl_bool_true;
423
6.78k
      break;
424
6.78k
    }
425
18.0k
426
18.0k
  free(active);
427
18.0k
428
18.0k
  return involves;
429
0
error:
430
0
  free(active);
431
0
  return isl_bool_error;
432
18.0k
}
433
434
/* Does the given constraint represent a lower bound on the given
435
 * dimension?
436
 */
437
isl_bool isl_constraint_is_lower_bound(__isl_keep isl_constraint *constraint,
438
  enum isl_dim_type type, unsigned pos)
439
34.7k
{
440
34.7k
  if (!constraint)
441
0
    return isl_bool_error;
442
34.7k
443
34.7k
  if (pos >= isl_local_space_dim(constraint->ls, type))
444
34.7k
    
isl_die0
(isl_constraint_get_ctx(constraint), isl_error_invalid,
445
34.7k
      "position out of bounds", return isl_bool_error);
446
34.7k
447
34.7k
  pos += isl_local_space_offset(constraint->ls, type);
448
34.7k
  return isl_int_is_pos(constraint->v->el[pos]);
449
34.7k
}
450
451
/* Does the given constraint represent an upper bound on the given
452
 * dimension?
453
 */
454
isl_bool isl_constraint_is_upper_bound(__isl_keep isl_constraint *constraint,
455
  enum isl_dim_type type, unsigned pos)
456
1.86k
{
457
1.86k
  if (!constraint)
458
0
    return isl_bool_error;
459
1.86k
460
1.86k
  if (pos >= isl_local_space_dim(constraint->ls, type))
461
1.86k
    
isl_die0
(isl_constraint_get_ctx(constraint), isl_error_invalid,
462
1.86k
      "position out of bounds", return isl_bool_error);
463
1.86k
464
1.86k
  pos += isl_local_space_offset(constraint->ls, type);
465
1.86k
  return isl_int_is_neg(constraint->v->el[pos]);
466
1.86k
}
467
468
const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
469
  enum isl_dim_type type, unsigned pos)
470
0
{
471
0
  return constraint ?
472
0
      isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL;
473
0
}
474
475
void isl_constraint_get_constant(__isl_keep isl_constraint *constraint,
476
  isl_int *v)
477
139
{
478
139
  if (!constraint)
479
0
    return;
480
139
  isl_int_set(*v, constraint->v->el[0]);
481
139
}
482
483
/* Return the constant term of "constraint".
484
 */
485
__isl_give isl_val *isl_constraint_get_constant_val(
486
  __isl_keep isl_constraint *constraint)
487
261
{
488
261
  isl_ctx *ctx;
489
261
490
261
  if (!constraint)
491
0
    return NULL;
492
261
493
261
  ctx = isl_constraint_get_ctx(constraint);
494
261
  return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
495
261
}
496
497
void isl_constraint_get_coefficient(struct isl_constraint *constraint,
498
  enum isl_dim_type type, int pos, isl_int *v)
499
139
{
500
139
  if (!constraint)
501
0
    return;
502
139
503
139
  if (pos >= isl_local_space_dim(constraint->ls, type))
504
139
    
isl_die0
(constraint->v->ctx, isl_error_invalid,
505
139
      "position out of bounds", return);
506
139
507
139
  pos += isl_local_space_offset(constraint->ls, type);
508
139
  isl_int_set(*v, constraint->v->el[pos]);
509
139
}
510
511
/* Return the coefficient of the variable of type "type" at position "pos"
512
 * of "constraint".
513
 */
514
__isl_give isl_val *isl_constraint_get_coefficient_val(
515
  __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
516
5.75k
{
517
5.75k
  isl_ctx *ctx;
518
5.75k
519
5.75k
  if (!constraint)
520
0
    return NULL;
521
5.75k
522
5.75k
  ctx = isl_constraint_get_ctx(constraint);
523
5.75k
  if (pos < 0 || pos >= isl_local_space_dim(constraint->ls, type))
524
5.75k
    
isl_die0
(ctx, isl_error_invalid,
525
5.75k
      "position out of bounds", return NULL);
526
5.75k
527
5.75k
  pos += isl_local_space_offset(constraint->ls, type);
528
5.75k
  return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
529
5.75k
}
530
531
__isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint,
532
  int pos)
533
0
{
534
0
  if (!constraint)
535
0
    return NULL;
536
0
537
0
  return isl_local_space_get_div(constraint->ls, pos);
538
0
}
539
540
__isl_give isl_constraint *isl_constraint_set_constant(
541
  __isl_take isl_constraint *constraint, isl_int v)
542
0
{
543
0
  constraint = isl_constraint_cow(constraint);
544
0
  if (!constraint)
545
0
    return NULL;
546
0
547
0
  constraint->v = isl_vec_cow(constraint->v);
548
0
  if (!constraint->v)
549
0
    return isl_constraint_free(constraint);
550
0
551
0
  isl_int_set(constraint->v->el[0], v);
552
0
  return constraint;
553
0
}
554
555
/* Replace the constant term of "constraint" by "v".
556
 */
557
__isl_give isl_constraint *isl_constraint_set_constant_val(
558
  __isl_take isl_constraint *constraint, __isl_take isl_val *v)
559
266
{
560
266
  constraint = isl_constraint_cow(constraint);
561
266
  if (!constraint || !v)
562
0
    goto error;
563
266
  if (!isl_val_is_int(v))
564
266
    
isl_die0
(isl_constraint_get_ctx(constraint), isl_error_invalid,
565
266
      "expecting integer value", goto error);
566
266
  constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
567
266
  if (!constraint->v)
568
0
    constraint = isl_constraint_free(constraint);
569
266
  return constraint;
570
0
error:
571
0
  isl_val_free(v);
572
0
  return isl_constraint_free(constraint);
573
266
}
574
575
__isl_give isl_constraint *isl_constraint_set_constant_si(
576
  __isl_take isl_constraint *constraint, int v)
577
2.04k
{
578
2.04k
  constraint = isl_constraint_cow(constraint);
579
2.04k
  if (!constraint)
580
0
    return NULL;
581
2.04k
582
2.04k
  constraint->v = isl_vec_cow(constraint->v);
583
2.04k
  if (!constraint->v)
584
0
    return isl_constraint_free(constraint);
585
2.04k
586
2.04k
  isl_int_set_si(constraint->v->el[0], v);
587
2.04k
  return constraint;
588
2.04k
}
589
590
__isl_give isl_constraint *isl_constraint_set_coefficient(
591
  __isl_take isl_constraint *constraint,
592
  enum isl_dim_type type, int pos, isl_int v)
593
0
{
594
0
  constraint = isl_constraint_cow(constraint);
595
0
  if (!constraint)
596
0
    return NULL;
597
0
598
0
  if (pos >= isl_local_space_dim(constraint->ls, type))
599
0
    isl_die(constraint->v->ctx, isl_error_invalid,
600
0
      "position out of bounds",
601
0
      return isl_constraint_free(constraint));
602
0
603
0
  constraint = isl_constraint_cow(constraint);
604
0
  if (!constraint)
605
0
    return NULL;
606
0
607
0
  constraint->v = isl_vec_cow(constraint->v);
608
0
  if (!constraint->v)
609
0
    return isl_constraint_free(constraint);
610
0
611
0
  pos += isl_local_space_offset(constraint->ls, type);
612
0
  isl_int_set(constraint->v->el[pos], v);
613
0
614
0
  return constraint;
615
0
}
616
617
/* Replace the coefficient of the variable of type "type" at position "pos"
618
 * of "constraint" by "v".
619
 */
620
__isl_give isl_constraint *isl_constraint_set_coefficient_val(
621
  __isl_take isl_constraint *constraint,
622
  enum isl_dim_type type, int pos, __isl_take isl_val *v)
623
0
{
624
0
  constraint = isl_constraint_cow(constraint);
625
0
  if (!constraint || !v)
626
0
    goto error;
627
0
  if (!isl_val_is_int(v))
628
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
629
0
      "expecting integer value", goto error);
630
0
631
0
  if (pos >= isl_local_space_dim(constraint->ls, type))
632
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
633
0
      "position out of bounds", goto error);
634
0
635
0
  pos += isl_local_space_offset(constraint->ls, type);
636
0
  constraint->v = isl_vec_set_element_val(constraint->v, pos, v);
637
0
  if (!constraint->v)
638
0
    constraint = isl_constraint_free(constraint);
639
0
  return constraint;
640
0
error:
641
0
  isl_val_free(v);
642
0
  return isl_constraint_free(constraint);
643
0
}
644
645
__isl_give isl_constraint *isl_constraint_set_coefficient_si(
646
  __isl_take isl_constraint *constraint,
647
  enum isl_dim_type type, int pos, int v)
648
7.13k
{
649
7.13k
  constraint = isl_constraint_cow(constraint);
650
7.13k
  if (!constraint)
651
0
    return NULL;
652
7.13k
653
7.13k
  if (pos >= isl_local_space_dim(constraint->ls, type))
654
7.13k
    
isl_die0
(constraint->v->ctx, isl_error_invalid,
655
7.13k
      "position out of bounds",
656
7.13k
      return isl_constraint_free(constraint));
657
7.13k
658
7.13k
  constraint = isl_constraint_cow(constraint);
659
7.13k
  if (!constraint)
660
0
    return NULL;
661
7.13k
662
7.13k
  constraint->v = isl_vec_cow(constraint->v);
663
7.13k
  if (!constraint->v)
664
0
    return isl_constraint_free(constraint);
665
7.13k
666
7.13k
  pos += isl_local_space_offset(constraint->ls, type);
667
7.13k
  isl_int_set_si(constraint->v->el[pos], v);
668
7.13k
669
7.13k
  return constraint;
670
7.13k
}
671
672
struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
673
0
{
674
0
  isl_ctx *ctx;
675
0
676
0
  constraint = isl_constraint_cow(constraint);
677
0
  if (!constraint)
678
0
    return NULL;
679
0
680
0
  ctx = isl_constraint_get_ctx(constraint);
681
0
  if (isl_constraint_is_equality(constraint))
682
0
    isl_die(ctx, isl_error_invalid, "cannot negate equality",
683
0
      return isl_constraint_free(constraint));
684
0
  constraint->v = isl_vec_neg(constraint->v);
685
0
  constraint->v = isl_vec_cow(constraint->v);
686
0
  if (!constraint->v)
687
0
    return isl_constraint_free(constraint);
688
0
  isl_int_sub_ui(constraint->v->el[0], constraint->v->el[0], 1);
689
0
  return constraint;
690
0
}
691
692
isl_bool isl_constraint_is_equality(struct isl_constraint *constraint)
693
48.9k
{
694
48.9k
  if (!constraint)
695
0
    return isl_bool_error;
696
48.9k
  return constraint->eq;
697
48.9k
}
698
699
int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
700
2.11k
{
701
2.11k
  int i;
702
2.11k
  int n_div;
703
2.11k
704
2.11k
  if (!constraint)
705
0
    return -1;
706
2.11k
  if (isl_constraint_is_equality(constraint))
707
87
    return 0;
708
2.02k
  n_div = isl_constraint_dim(constraint, isl_dim_div);
709
2.06k
  for (i = 0; i < n_div; 
++i44
) {
710
76
    isl_bool is_div;
711
76
    is_div = isl_local_space_is_div_constraint(constraint->ls,
712
76
              constraint->v->el, i);
713
76
    if (is_div < 0 || is_div)
714
32
      return is_div;
715
76
  }
716
2.02k
717
2.02k
  
return 01.99k
;
718
2.02k
}
719
720
/* We manually set ISL_BASIC_SET_FINAL instead of calling
721
 * isl_basic_map_finalize because we want to keep the position
722
 * of the divs and we therefore do not want to throw away redundant divs.
723
 * This is arguably a bit fragile.
724
 */
725
__isl_give isl_basic_map *isl_basic_map_from_constraint(
726
  __isl_take isl_constraint *constraint)
727
39.6k
{
728
39.6k
  int k;
729
39.6k
  isl_local_space *ls;
730
39.6k
  struct isl_basic_map *bmap;
731
39.6k
  isl_int *c;
732
39.6k
  unsigned total;
733
39.6k
734
39.6k
  if (!constraint)
735
0
    return NULL;
736
39.6k
737
39.6k
  ls = isl_local_space_copy(constraint->ls);
738
39.6k
  bmap = isl_basic_map_from_local_space(ls);
739
39.6k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
740
39.6k
  if (isl_constraint_is_equality(constraint)) {
741
21.0k
    k = isl_basic_map_alloc_equality(bmap);
742
21.0k
    if (k < 0)
743
0
      goto error;
744
21.0k
    c = bmap->eq[k];
745
21.0k
  }
746
18.6k
  else {
747
18.6k
    k = isl_basic_map_alloc_inequality(bmap);
748
18.6k
    if (k < 0)
749
0
      goto error;
750
18.6k
    c = bmap->ineq[k];
751
18.6k
  }
752
39.6k
  total = isl_basic_map_total_dim(bmap);
753
39.6k
  isl_seq_cpy(c, constraint->v->el, 1 + total);
754
39.6k
  isl_constraint_free(constraint);
755
39.6k
  if (bmap)
756
39.6k
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
757
39.6k
  return bmap;
758
0
error:
759
0
  isl_constraint_free(constraint);
760
0
  isl_basic_map_free(bmap);
761
0
  return NULL;
762
39.6k
}
763
764
__isl_give isl_basic_set *isl_basic_set_from_constraint(
765
  __isl_take isl_constraint *constraint)
766
27.3k
{
767
27.3k
  if (!constraint)
768
0
    return NULL;
769
27.3k
770
27.3k
  if (isl_constraint_dim(constraint, isl_dim_in) != 0)
771
27.3k
    
isl_die0
(isl_constraint_get_ctx(constraint), isl_error_invalid,
772
27.3k
      "not a set constraint", goto error);
773
27.3k
  return bset_from_bmap(isl_basic_map_from_constraint(constraint));
774
0
error:
775
0
  isl_constraint_free(constraint);
776
0
  return NULL;
777
27.3k
}
778
779
/* Is the variable of "type" at position "pos" of "bmap" defined
780
 * in terms of earlier dimensions through an equality?
781
 *
782
 * If so, and if c is not NULL, then return a copy of this equality in *c.
783
 */
784
isl_bool isl_basic_map_has_defining_equality(
785
  __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
786
  __isl_give isl_constraint **c)
787
659
{
788
659
  int i;
789
659
  unsigned offset;
790
659
  unsigned total;
791
659
792
659
  if (!bmap)
793
0
    return isl_bool_error;
794
659
  offset = basic_map_offset(bmap, type);
795
659
  total = isl_basic_map_total_dim(bmap);
796
659
  if (pos >= isl_basic_map_dim(bmap, type))
797
659
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
798
659
      "invalid position", return isl_bool_error);
799
678
  
for (i = 0; 659
i < bmap->n_eq;
++i19
) {
800
166
    if (isl_int_is_zero(bmap->eq[i][offset + pos]) ||
801
166
        isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
802
149
             1+total-offset-pos-1) != -1)
803
19
      continue;
804
147
    if (c)
805
139
      *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
806
139
                &bmap->eq[i]);
807
147
    return isl_bool_true;
808
147
  }
809
659
  
return isl_bool_false512
;
810
659
}
811
812
/* Is the variable of "type" at position "pos" of "bset" defined
813
 * in terms of earlier dimensions through an equality?
814
 *
815
 * If so, and if c is not NULL, then return a copy of this equality in *c.
816
 */
817
isl_bool isl_basic_set_has_defining_equality(
818
  __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
819
  __isl_give isl_constraint **c)
820
389
{
821
389
  return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
822
389
                type, pos, c);
823
389
}
824
825
isl_bool isl_basic_set_has_defining_inequalities(
826
  struct isl_basic_set *bset, enum isl_dim_type type, int pos,
827
  struct isl_constraint **lower,
828
  struct isl_constraint **upper)
829
0
{
830
0
  int i, j;
831
0
  unsigned offset;
832
0
  unsigned total;
833
0
  isl_int m;
834
0
  isl_int **lower_line, **upper_line;
835
0
836
0
  if (!bset)
837
0
    return isl_bool_error;
838
0
  offset = basic_set_offset(bset, type);
839
0
  total = isl_basic_set_total_dim(bset);
840
0
  if (pos >= isl_basic_set_dim(bset, type))
841
0
    isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
842
0
      "invalid position", return isl_bool_error);
843
0
  isl_int_init(m);
844
0
  for (i = 0; i < bset->n_ineq; ++i) {
845
0
    if (isl_int_is_zero(bset->ineq[i][offset + pos]))
846
0
      continue;
847
0
    if (isl_int_is_one(bset->ineq[i][offset + pos]))
848
0
      continue;
849
0
    if (isl_int_is_negone(bset->ineq[i][offset + pos]))
850
0
      continue;
851
0
    if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
852
0
            1+total-offset-pos-1) != -1)
853
0
      continue;
854
0
    for (j = i + 1; j < bset->n_ineq; ++j) {
855
0
      if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
856
0
              total))
857
0
        continue;
858
0
      isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
859
0
      if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
860
0
        continue;
861
0
862
0
      if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
863
0
        lower_line = &bset->ineq[i];
864
0
        upper_line = &bset->ineq[j];
865
0
      } else {
866
0
        lower_line = &bset->ineq[j];
867
0
        upper_line = &bset->ineq[i];
868
0
      }
869
0
      *lower = isl_basic_set_constraint(
870
0
          isl_basic_set_copy(bset), lower_line);
871
0
      *upper = isl_basic_set_constraint(
872
0
          isl_basic_set_copy(bset), upper_line);
873
0
      isl_int_clear(m);
874
0
      return isl_bool_true;
875
0
    }
876
0
  }
877
0
  *lower = NULL;
878
0
  *upper = NULL;
879
0
  isl_int_clear(m);
880
0
  return isl_bool_false;
881
0
}
882
883
/* Given two constraints "a" and "b" on the variable at position "abs_pos"
884
 * (in "a" and "b"), add a constraint to "bset" that ensures that the
885
 * bound implied by "a" is (strictly) larger than the bound implied by "b".
886
 *
887
 * If both constraints imply lower bounds, then this means that "a" is
888
 * active in the result.
889
 * If both constraints imply upper bounds, then this means that "b" is
890
 * active in the result.
891
 */
892
static __isl_give isl_basic_set *add_larger_bound_constraint(
893
  __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
894
  unsigned abs_pos, int strict)
895
0
{
896
0
  int k;
897
0
  isl_int t;
898
0
  unsigned total;
899
0
900
0
  k = isl_basic_set_alloc_inequality(bset);
901
0
  if (k < 0)
902
0
    goto error;
903
0
904
0
  total = isl_basic_set_dim(bset, isl_dim_all);
905
0
906
0
  isl_int_init(t);
907
0
  isl_int_neg(t, b[1 + abs_pos]);
908
0
909
0
  isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
910
0
  isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
911
0
    t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
912
0
    total - abs_pos);
913
0
914
0
  if (strict)
915
0
    isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
916
0
917
0
  isl_int_clear(t);
918
0
919
0
  return bset;
920
0
error:
921
0
  isl_basic_set_free(bset);
922
0
  return NULL;
923
0
}
924
925
/* Add constraints to "context" that ensure that "u" is the smallest
926
 * (and therefore active) upper bound on "abs_pos" in "bset" and return
927
 * the resulting basic set.
928
 */
929
static __isl_give isl_basic_set *set_smallest_upper_bound(
930
  __isl_keep isl_basic_set *context,
931
  __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
932
8
{
933
8
  int j;
934
8
935
8
  context = isl_basic_set_copy(context);
936
8
  context = isl_basic_set_cow(context);
937
8
938
8
  context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
939
8
940
21
  for (j = 0; j < bset->n_ineq; 
++j13
) {
941
13
    if (j == u)
942
8
      continue;
943
5
    if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
944
5
      continue;
945
0
    context = add_larger_bound_constraint(context,
946
0
      bset->ineq[j], bset->ineq[u], abs_pos, j > u);
947
0
  }
948
8
949
8
  context = isl_basic_set_simplify(context);
950
8
  context = isl_basic_set_finalize(context);
951
8
952
8
  return context;
953
8
}
954
955
/* Add constraints to "context" that ensure that "u" is the largest
956
 * (and therefore active) upper bound on "abs_pos" in "bset" and return
957
 * the resulting basic set.
958
 */
959
static __isl_give isl_basic_set *set_largest_lower_bound(
960
  __isl_keep isl_basic_set *context,
961
  __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
962
9
{
963
9
  int j;
964
9
965
9
  context = isl_basic_set_copy(context);
966
9
  context = isl_basic_set_cow(context);
967
9
968
9
  context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
969
9
970
23
  for (j = 0; j < bset->n_ineq; 
++j14
) {
971
14
    if (j == l)
972
9
      continue;
973
5
    if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
974
5
      continue;
975
0
    context = add_larger_bound_constraint(context,
976
0
      bset->ineq[l], bset->ineq[j], abs_pos, j > l);
977
0
  }
978
9
979
9
  context = isl_basic_set_simplify(context);
980
9
  context = isl_basic_set_finalize(context);
981
9
982
9
  return context;
983
9
}
984
985
static isl_stat foreach_upper_bound(__isl_keep isl_basic_set *bset,
986
  enum isl_dim_type type, unsigned abs_pos,
987
  __isl_take isl_basic_set *context, int n_upper,
988
  isl_stat (*fn)(__isl_take isl_constraint *lower,
989
      __isl_take isl_constraint *upper,
990
      __isl_take isl_basic_set *bset, void *user), void *user)
991
8
{
992
8
  isl_basic_set *context_i;
993
8
  isl_constraint *upper = NULL;
994
8
  int i;
995
8
996
21
  for (i = 0; i < bset->n_ineq; 
++i13
) {
997
13
    if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
998
13
      
continue5
;
999
8
1000
8
    context_i = set_smallest_upper_bound(context, bset,
1001
8
              abs_pos, n_upper, i);
1002
8
    if (isl_basic_set_is_empty(context_i)) {
1003
0
      isl_basic_set_free(context_i);
1004
0
      continue;
1005
0
    }
1006
8
    upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1007
8
            &bset->ineq[i]);
1008
8
    if (!upper || !context_i)
1009
0
      goto error;
1010
8
    if (fn(NULL, upper, context_i, user) < 0)
1011
0
      break;
1012
8
  }
1013
8
1014
8
  isl_basic_set_free(context);
1015
8
1016
8
  if (i < bset->n_ineq)
1017
0
    return isl_stat_error;
1018
8
1019
8
  return isl_stat_ok;
1020
0
error:
1021
0
  isl_constraint_free(upper);
1022
0
  isl_basic_set_free(context_i);
1023
0
  isl_basic_set_free(context);
1024
0
  return isl_stat_error;
1025
8
}
1026
1027
static isl_stat foreach_lower_bound(__isl_keep isl_basic_set *bset,
1028
  enum isl_dim_type type, unsigned abs_pos,
1029
  __isl_take isl_basic_set *context, int n_lower,
1030
  isl_stat (*fn)(__isl_take isl_constraint *lower,
1031
      __isl_take isl_constraint *upper,
1032
      __isl_take isl_basic_set *bset, void *user), void *user)
1033
9
{
1034
9
  isl_basic_set *context_i;
1035
9
  isl_constraint *lower = NULL;
1036
9
  int i;
1037
9
1038
23
  for (i = 0; i < bset->n_ineq; 
++i14
) {
1039
14
    if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1040
14
      
continue5
;
1041
9
1042
9
    context_i = set_largest_lower_bound(context, bset,
1043
9
              abs_pos, n_lower, i);
1044
9
    if (isl_basic_set_is_empty(context_i)) {
1045
0
      isl_basic_set_free(context_i);
1046
0
      continue;
1047
0
    }
1048
9
    lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1049
9
            &bset->ineq[i]);
1050
9
    if (!lower || !context_i)
1051
0
      goto error;
1052
9
    if (fn(lower, NULL, context_i, user) < 0)
1053
0
      break;
1054
9
  }
1055
9
1056
9
  isl_basic_set_free(context);
1057
9
1058
9
  if (i < bset->n_ineq)
1059
0
    return isl_stat_error;
1060
9
1061
9
  return isl_stat_ok;
1062
0
error:
1063
0
  isl_constraint_free(lower);
1064
0
  isl_basic_set_free(context_i);
1065
0
  isl_basic_set_free(context);
1066
0
  return isl_stat_error;
1067
9
}
1068
1069
static isl_stat foreach_bound_pair(__isl_keep isl_basic_set *bset,
1070
  enum isl_dim_type type, unsigned abs_pos,
1071
  __isl_take isl_basic_set *context, int n_lower, int n_upper,
1072
  isl_stat (*fn)(__isl_take isl_constraint *lower,
1073
      __isl_take isl_constraint *upper,
1074
      __isl_take isl_basic_set *bset, void *user), void *user)
1075
0
{
1076
0
  isl_basic_set *context_i, *context_j;
1077
0
  isl_constraint *lower = NULL;
1078
0
  isl_constraint *upper = NULL;
1079
0
  int i, j;
1080
0
1081
0
  for (i = 0; i < bset->n_ineq; ++i) {
1082
0
    if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1083
0
      continue;
1084
0
1085
0
    context_i = set_largest_lower_bound(context, bset,
1086
0
              abs_pos, n_lower, i);
1087
0
    if (isl_basic_set_is_empty(context_i)) {
1088
0
      isl_basic_set_free(context_i);
1089
0
      continue;
1090
0
    }
1091
0
1092
0
    for (j = 0; j < bset->n_ineq; ++j) {
1093
0
      if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1094
0
        continue;
1095
0
1096
0
      context_j = set_smallest_upper_bound(context_i, bset,
1097
0
                  abs_pos, n_upper, j);
1098
0
      context_j = isl_basic_set_extend_constraints(context_j,
1099
0
                  0, 1);
1100
0
      context_j = add_larger_bound_constraint(context_j,
1101
0
        bset->ineq[i], bset->ineq[j], abs_pos, 0);
1102
0
      context_j = isl_basic_set_simplify(context_j);
1103
0
      context_j = isl_basic_set_finalize(context_j);
1104
0
      if (isl_basic_set_is_empty(context_j)) {
1105
0
        isl_basic_set_free(context_j);
1106
0
        continue;
1107
0
      }
1108
0
      lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1109
0
              &bset->ineq[i]);
1110
0
      upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1111
0
              &bset->ineq[j]);
1112
0
      if (!lower || !upper || !context_j)
1113
0
        goto error;
1114
0
      if (fn(lower, upper, context_j, user) < 0)
1115
0
        break;
1116
0
    }
1117
0
1118
0
    isl_basic_set_free(context_i);
1119
0
1120
0
    if (j < bset->n_ineq)
1121
0
      break;
1122
0
  }
1123
0
1124
0
  isl_basic_set_free(context);
1125
0
1126
0
  if (i < bset->n_ineq)
1127
0
    return isl_stat_error;
1128
0
1129
0
  return isl_stat_ok;
1130
0
error:
1131
0
  isl_constraint_free(lower);
1132
0
  isl_constraint_free(upper);
1133
0
  isl_basic_set_free(context_i);
1134
0
  isl_basic_set_free(context_j);
1135
0
  isl_basic_set_free(context);
1136
0
  return isl_stat_error;
1137
0
}
1138
1139
/* For each pair of lower and upper bounds on the variable "pos"
1140
 * of type "type", call "fn" with these lower and upper bounds and the
1141
 * set of constraints on the remaining variables where these bounds
1142
 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1143
 *
1144
 * If the designated variable is equal to an affine combination of the
1145
 * other variables then fn is called with both lower and upper
1146
 * set to the corresponding equality.
1147
 *
1148
 * If there is no lower (or upper) bound, then NULL is passed
1149
 * as the corresponding bound.
1150
 *
1151
 * We first check if the variable is involved in any equality.
1152
 * If not, we count the number of lower and upper bounds and
1153
 * act accordingly.
1154
 */
1155
isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
1156
  enum isl_dim_type type, unsigned pos,
1157
  isl_stat (*fn)(__isl_take isl_constraint *lower,
1158
      __isl_take isl_constraint *upper,
1159
      __isl_take isl_basic_set *bset, void *user), void *user)
1160
17
{
1161
17
  int i;
1162
17
  isl_constraint *lower = NULL;
1163
17
  isl_constraint *upper = NULL;
1164
17
  isl_basic_set *context = NULL;
1165
17
  unsigned abs_pos;
1166
17
  int n_lower, n_upper;
1167
17
1168
17
  if (!bset)
1169
0
    return isl_stat_error;
1170
17
  isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type),
1171
17
    return isl_stat_error);
1172
17
  isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1173
17
    return isl_stat_error);
1174
17
1175
17
  abs_pos = pos;
1176
17
  if (type == isl_dim_set)
1177
17
    abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1178
17
1179
17
  for (i = 0; i < bset->n_eq; 
++i0
) {
1180
0
    if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1181
0
      continue;
1182
0
1183
0
    lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1184
0
            &bset->eq[i]);
1185
0
    upper = isl_constraint_copy(lower);
1186
0
    context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1187
0
          type, pos, 1);
1188
0
    if (!lower || !upper || !context)
1189
0
      goto error;
1190
0
    return fn(lower, upper, context, user);
1191
0
  }
1192
17
1193
17
  n_lower = 0;
1194
17
  n_upper = 0;
1195
44
  for (i = 0; i < bset->n_ineq; 
++i27
) {
1196
27
    if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1197
27
      
n_lower++9
;
1198
18
    else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1199
18
      
n_upper++8
;
1200
27
  }
1201
17
1202
17
  context = isl_basic_set_copy(bset);
1203
17
  context = isl_basic_set_cow(context);
1204
17
  if (!context)
1205
0
    goto error;
1206
44
  
for (i = context->n_ineq - 1; 17
i >= 0;
--i27
)
1207
27
    if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1208
27
      
isl_basic_set_drop_inequality(context, i)17
;
1209
17
1210
17
  context = isl_basic_set_drop(context, type, pos, 1);
1211
17
  if (!n_lower && 
!n_upper8
)
1212
0
    return fn(NULL, NULL, context, user);
1213
17
  if (!n_lower)
1214
8
    return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1215
8
            fn, user);
1216
9
  if (!n_upper)
1217
9
    return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1218
9
            fn, user);
1219
0
  return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1220
0
          fn, user);
1221
0
error:
1222
0
  isl_constraint_free(lower);
1223
0
  isl_constraint_free(upper);
1224
0
  isl_basic_set_free(context);
1225
0
  return -1;
1226
0
}
1227
1228
__isl_give isl_aff *isl_constraint_get_bound(
1229
  __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1230
3.90k
{
1231
3.90k
  isl_aff *aff;
1232
3.90k
  isl_ctx *ctx;
1233
3.90k
1234
3.90k
  if (!constraint)
1235
0
    return NULL;
1236
3.90k
  ctx = isl_constraint_get_ctx(constraint);
1237
3.90k
  if (pos >= isl_constraint_dim(constraint, type))
1238
3.90k
    
isl_die0
(ctx, isl_error_invalid,
1239
3.90k
      "index out of bounds", return NULL);
1240
3.90k
  if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1241
3.90k
    
isl_die0
(ctx, isl_error_invalid,
1242
3.90k
      "not a set constraint", return NULL);
1243
3.90k
1244
3.90k
  pos += offset(constraint, type);
1245
3.90k
  if (isl_int_is_zero(constraint->v->el[pos]))
1246
3.90k
    
isl_die0
(ctx, isl_error_invalid,
1247
3.90k
      "constraint does not define a bound on given dimension",
1248
3.90k
      return NULL);
1249
3.90k
1250
3.90k
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1251
3.90k
  if (!aff)
1252
0
    return NULL;
1253
3.90k
1254
3.90k
  if (isl_int_is_neg(constraint->v->el[pos]))
1255
3.90k
    
isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1)773
;
1256
3.12k
  else
1257
3.12k
    isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1258
3.90k
  isl_int_set_si(aff->v->el[1 + pos], 0);
1259
3.90k
  isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1260
3.90k
1261
3.90k
  return aff;
1262
3.90k
}
1263
1264
/* For an inequality constraint
1265
 *
1266
 *  f >= 0
1267
 *
1268
 * or an equality constraint
1269
 *
1270
 *  f = 0
1271
 *
1272
 * return the affine expression f.
1273
 */
1274
__isl_give isl_aff *isl_constraint_get_aff(
1275
  __isl_keep isl_constraint *constraint)
1276
604
{
1277
604
  isl_aff *aff;
1278
604
1279
604
  if (!constraint)
1280
0
    return NULL;
1281
604
1282
604
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1283
604
  if (!aff)
1284
0
    return NULL;
1285
604
1286
604
  isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1287
604
  isl_int_set_si(aff->v->el[0], 1);
1288
604
1289
604
  return aff;
1290
604
}
1291
1292
/* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1293
 * In particular, construct aff >= 0 or aff = 0.
1294
 *
1295
 * The denominator of "aff" can be ignored.
1296
 */
1297
static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq,
1298
  __isl_take isl_aff *aff)
1299
31.1k
{
1300
31.1k
  isl_local_space *ls;
1301
31.1k
  isl_vec *v;
1302
31.1k
1303
31.1k
  if (!aff)
1304
0
    return NULL;
1305
31.1k
  ls = isl_aff_get_domain_local_space(aff);
1306
31.1k
  v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1307
31.1k
  isl_aff_free(aff);
1308
31.1k
1309
31.1k
  return isl_constraint_alloc_vec(eq, ls, v);
1310
31.1k
}
1311
1312
/* Construct an equality constraint equating the given affine expression
1313
 * to zero.
1314
 */
1315
__isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1316
14.2k
{
1317
14.2k
  return isl_constraint_alloc_aff(1, aff);
1318
14.2k
}
1319
1320
/* Construct an inequality constraint enforcing the given affine expression
1321
 * to be non-negative.
1322
 */
1323
__isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1324
16.8k
{
1325
16.8k
  return isl_constraint_alloc_aff(0, aff);
1326
16.8k
}
1327
1328
/* Compare two isl_constraints.
1329
 *
1330
 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1331
 * than "c2" and 0 if they are equal.
1332
 *
1333
 * The order is fairly arbitrary.  We do consider constraints that only involve
1334
 * earlier dimensions as "smaller".
1335
 */
1336
int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1,
1337
  __isl_keep isl_constraint *c2)
1338
21
{
1339
21
  int cmp;
1340
21
  int last1, last2;
1341
21
1342
21
  if (c1 == c2)
1343
0
    return 0;
1344
21
  if (!c1)
1345
0
    return -1;
1346
21
  if (!c2)
1347
0
    return 1;
1348
21
  cmp = isl_local_space_cmp(c1->ls, c2->ls);
1349
21
  if (cmp != 0)
1350
0
    return cmp;
1351
21
1352
21
  last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1353
21
  last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1354
21
  if (last1 != last2)
1355
0
    return last1 - last2;
1356
21
1357
21
  return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1358
21
}
1359
1360
/* Compare two constraints based on their final (non-zero) coefficients.
1361
 * In particular, the constraint that involves later variables or
1362
 * that has a larger coefficient for a shared latest variable
1363
 * is considered "greater" than the other constraint.
1364
 *
1365
 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1366
 * than "c2" and 0 if they are equal.
1367
 *
1368
 * If the constraints live in different local spaces, then we cannot
1369
 * really compare the constraints so we compare the local spaces instead.
1370
 */
1371
int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1,
1372
  __isl_keep isl_constraint *c2)
1373
103
{
1374
103
  int cmp;
1375
103
  int last1, last2;
1376
103
1377
103
  if (c1 == c2)
1378
0
    return 0;
1379
103
  if (!c1)
1380
0
    return -1;
1381
103
  if (!c2)
1382
0
    return 1;
1383
103
  cmp = isl_local_space_cmp(c1->ls, c2->ls);
1384
103
  if (cmp != 0)
1385
0
    return cmp;
1386
103
1387
103
  last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1388
103
  last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1389
103
  if (last1 != last2)
1390
82
    return last1 - last2;
1391
21
  if (last1 == -1)
1392
0
    return 0;
1393
21
  return isl_int_abs_cmp(c1->v->el[1 + last1], c2->v->el[1 + last2]);
1394
21
}