Coverage Report

Created: 2017-11-23 03:11

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