Coverage Report

Created: 2017-06-28 17:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
12.7k
{
33
12.7k
  return c ? isl_local_space_get_ctx(c->ls) : NULL;
34
12.7k
}
35
36
static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
37
36.3k
{
38
36.3k
  return isl_local_space_dim(c->ls, type);
39
36.3k
}
40
41
static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
42
2.20k
{
43
2.20k
  return isl_local_space_offset(c->ls, type);
44
2.20k
}
45
46
static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
47
              enum isl_dim_type type)
48
603
{
49
244
  return type == isl_dim_div ? 1 + isl_space_dim(bmap->dim, isl_dim_all)
50
359
           : 1 + isl_space_offset(bmap->dim, type);
51
603
}
52
53
static unsigned basic_set_offset(struct isl_basic_set *bset,
54
              enum isl_dim_type type)
55
{
56
  isl_space *dim = bset->dim;
57
  switch (type) {
58
  case isl_dim_param: return 1;
59
  case isl_dim_in:  return 1 + dim->nparam;
60
  case isl_dim_out: return 1 + dim->nparam + dim->n_in;
61
  case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
62
  default:    return 0;
63
  }
64
}
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
44.6k
{
69
44.6k
  isl_constraint *constraint;
70
44.6k
71
44.6k
  if (
!ls || 44.6k
!v44.6k
)
72
0
    goto error;
73
44.6k
74
44.6k
  
constraint = 44.6k
isl_alloc_type44.6k
(isl_vec_get_ctx(v), isl_constraint);
75
44.6k
  if (!constraint)
76
0
    goto error;
77
44.6k
78
44.6k
  constraint->ref = 1;
79
44.6k
  constraint->eq = eq;
80
44.6k
  constraint->ls = ls;
81
44.6k
  constraint->v = v;
82
44.6k
83
44.6k
  return constraint;
84
0
error:
85
0
  isl_local_space_free(ls);
86
0
  isl_vec_free(v);
87
0
  return NULL;
88
44.6k
}
89
90
__isl_give isl_constraint *isl_constraint_alloc(int eq,
91
  __isl_take isl_local_space *ls)
92
2.69k
{
93
2.69k
  isl_ctx *ctx;
94
2.69k
  isl_vec *v;
95
2.69k
96
2.69k
  if (!ls)
97
0
    return NULL;
98
2.69k
99
2.69k
  ctx = isl_local_space_get_ctx(ls);
100
2.69k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
101
2.69k
  v = isl_vec_clr(v);
102
2.69k
  return isl_constraint_alloc_vec(eq, ls, v);
103
2.69k
}
104
105
struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
106
  isl_int **line)
107
15.3k
{
108
15.3k
  int eq;
109
15.3k
  isl_ctx *ctx;
110
15.3k
  isl_vec *v;
111
15.3k
  isl_local_space *ls = NULL;
112
15.3k
  isl_constraint *constraint;
113
15.3k
114
15.3k
  if (
!bmap || 15.3k
!line15.3k
)
115
0
    goto error;
116
15.3k
117
15.3k
  eq = line >= bmap->eq;
118
15.3k
119
15.3k
  ctx = isl_basic_map_get_ctx(bmap);
120
15.3k
  ls = isl_basic_map_get_local_space(bmap);
121
15.3k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
122
15.3k
  if (!v)
123
0
    goto error;
124
15.3k
  isl_seq_cpy(v->el, line[0], v->size);
125
15.3k
  constraint = isl_constraint_alloc_vec(eq, ls, v);
126
15.3k
127
15.3k
  isl_basic_map_free(bmap);
128
15.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
15.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.00k
{
144
2.00k
  return isl_constraint_alloc(1, ls);
145
2.00k
}
146
147
__isl_give isl_constraint *isl_constraint_alloc_inequality(
148
  __isl_take isl_local_space *ls)
149
691
{
150
691
  return isl_constraint_alloc(0, ls);
151
691
}
152
153
struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
154
2.02k
{
155
2.02k
  if (!c)
156
0
    return NULL;
157
2.02k
158
2.02k
  return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
159
2.02k
            isl_vec_copy(c->v));
160
2.02k
}
161
162
struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
163
13.2k
{
164
13.2k
  if (!c)
165
0
    return NULL;
166
13.2k
167
13.2k
  
if (13.2k
c->ref == 113.2k
)
168
11.2k
    return c;
169
2.02k
  c->ref--;
170
2.02k
  return isl_constraint_dup(c);
171
13.2k
}
172
173
struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
174
9.56k
{
175
9.56k
  if (!constraint)
176
0
    return NULL;
177
9.56k
178
9.56k
  constraint->ref++;
179
9.56k
  return constraint;
180
9.56k
}
181
182
__isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c)
183
52.2k
{
184
52.2k
  if (!c)
185
3
    return NULL;
186
52.2k
187
52.2k
  
if (52.2k
--c->ref > 052.2k
)
188
7.54k
    return NULL;
189
52.2k
190
44.6k
  isl_local_space_free(c->ls);
191
44.6k
  isl_vec_free(c->v);
192
44.6k
  free(c);
193
44.6k
194
44.6k
  return NULL;
195
52.2k
}
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.61k
{
203
1.61k
  if (!bmap)
204
0
    return -1;
205
1.61k
206
1.61k
  return bmap->n_eq + bmap->n_ineq;
207
1.61k
}
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
5.29k
{
221
5.29k
  int i;
222
5.29k
  struct isl_constraint *c;
223
5.29k
224
5.29k
  if (!bmap)
225
0
    return isl_stat_error;
226
5.29k
227
5.29k
  
isl_assert5.29k
(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),5.29k
228
5.29k
      return isl_stat_error);
229
5.29k
230
9.42k
  
for (i = 0; 5.29k
i < bmap->n_eq9.42k
;
++i4.13k
)
{4.14k
231
4.14k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
232
4.14k
            &bmap->eq[i]);
233
4.14k
    if (!c)
234
0
      return isl_stat_error;
235
4.14k
    
if (4.14k
fn(c, user) < 04.14k
)
236
3
      return isl_stat_error;
237
4.14k
  }
238
5.29k
239
16.4k
  
for (i = 0; 5.28k
i < bmap->n_ineq16.4k
;
++i11.1k
)
{11.1k
240
11.1k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
241
11.1k
            &bmap->ineq[i]);
242
11.1k
    if (!c)
243
0
      return isl_stat_error;
244
11.1k
    
if (11.1k
fn(c, user) < 011.1k
)
245
3
      return isl_stat_error;
246
11.1k
  }
247
5.28k
248
5.28k
  return isl_stat_ok;
249
5.28k
}
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
3.67k
{
254
3.67k
  return isl_basic_map_foreach_constraint(bset_to_bmap(bset), fn, user);
255
3.67k
}
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.15k
{
263
2.15k
  isl_constraint_list **list = user;
264
2.15k
265
2.15k
  if (isl_constraint_is_div_constraint(constraint))
266
12
    isl_constraint_free(constraint);
267
2.15k
  else
268
2.14k
    *list = isl_constraint_list_add(*list, constraint);
269
2.15k
270
2.15k
  return isl_stat_ok;
271
2.15k
}
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.61k
{
282
1.61k
  int n;
283
1.61k
  int known;
284
1.61k
  isl_ctx *ctx;
285
1.61k
  isl_constraint_list *list;
286
1.61k
287
1.61k
  known = isl_basic_map_divs_known(bmap);
288
1.61k
  if (known < 0)
289
0
    return NULL;
290
1.61k
  ctx = isl_basic_map_get_ctx(bmap);
291
1.61k
  if (!known)
292
0
    isl_die(ctx, isl_error_invalid,
293
1.61k
      "input involves unknown divs", return NULL);
294
1.61k
295
1.61k
  n = isl_basic_map_n_constraint(bmap);
296
1.61k
  list = isl_constraint_list_alloc(ctx, n);
297
1.61k
  if (isl_basic_map_foreach_constraint(bmap,
298
1.61k
              &collect_constraint, &list) < 0)
299
0
    list = isl_constraint_list_free(list);
300
1.61k
301
1.61k
  return list;
302
1.61k
}
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.53k
{
310
1.53k
  return isl_basic_map_get_constraint_list(bset);
311
1.53k
}
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 || 0
!constraint20
)
319
0
    return 0;
320
0
  
if (0
constraint1->eq != constraint2->eq0
)
321
0
    return 0;
322
0
  equal = isl_local_space_is_equal(constraint1->ls, constraint2->ls);
323
0
  if (
equal < 0 || 0
!equal0
)
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
1.40k
{
331
1.40k
  isl_ctx *ctx;
332
1.40k
  isl_space *dim;
333
1.40k
  int equal_space;
334
1.40k
335
1.40k
  if (
!bmap || 1.40k
!constraint1.40k
)
336
0
    goto error;
337
1.40k
338
1.40k
  ctx = isl_constraint_get_ctx(constraint);
339
1.40k
  dim = isl_constraint_get_space(constraint);
340
1.40k
  equal_space = isl_space_is_equal(bmap->dim, dim);
341
1.40k
  isl_space_free(dim);
342
1.40k
  isl_assert(ctx, equal_space, goto error);
343
1.40k
344
1.40k
  bmap = isl_basic_map_intersect(bmap,
345
1.40k
        isl_basic_map_from_constraint(constraint));
346
1.40k
  return bmap;
347
0
error:
348
0
  isl_basic_map_free(bmap);
349
0
  isl_constraint_free(constraint);
350
0
  return NULL;
351
1.40k
}
352
353
struct isl_basic_set *isl_basic_set_add_constraint(
354
  struct isl_basic_set *bset, struct isl_constraint *constraint)
355
1.36k
{
356
1.36k
  return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset),
357
1.36k
                  constraint));
358
1.36k
}
359
360
__isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
361
  __isl_take isl_constraint *constraint)
362
3.99k
{
363
3.99k
  isl_basic_map *bmap;
364
3.99k
365
3.99k
  bmap = isl_basic_map_from_constraint(constraint);
366
3.99k
  map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
367
3.99k
368
3.99k
  return map;
369
3.99k
}
370
371
__isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
372
  __isl_take isl_constraint *constraint)
373
1.89k
{
374
1.89k
  return isl_map_add_constraint(set, constraint);
375
1.89k
}
376
377
__isl_give isl_space *isl_constraint_get_space(
378
  __isl_keep isl_constraint *constraint)
379
1.40k
{
380
1.40k
  return constraint ? isl_local_space_get_space(constraint->ls) : NULL;
381
1.40k
}
382
383
__isl_give isl_local_space *isl_constraint_get_local_space(
384
  __isl_keep isl_constraint *constraint)
385
264
{
386
264
  return constraint ? isl_local_space_copy(constraint->ls) : NULL;
387
264
}
388
389
int isl_constraint_dim(struct isl_constraint *constraint,
390
  enum isl_dim_type type)
391
36.3k
{
392
36.3k
  if (!constraint)
393
0
    return -1;
394
36.3k
  return n(constraint, type);
395
36.3k
}
396
397
isl_bool isl_constraint_involves_dims(__isl_keep isl_constraint *constraint,
398
  enum isl_dim_type type, unsigned first, unsigned n)
399
3.67k
{
400
3.67k
  int i;
401
3.67k
  isl_ctx *ctx;
402
3.67k
  int *active = NULL;
403
3.67k
  isl_bool involves = isl_bool_false;
404
3.67k
405
3.67k
  if (!constraint)
406
0
    return isl_bool_error;
407
3.67k
  
if (3.67k
n == 03.67k
)
408
0
    return isl_bool_false;
409
3.67k
410
3.67k
  ctx = isl_constraint_get_ctx(constraint);
411
3.67k
  if (first + n > isl_constraint_dim(constraint, type))
412
0
    isl_die(ctx, isl_error_invalid,
413
3.67k
      "range out of bounds", return isl_bool_error);
414
3.67k
415
3.67k
  active = isl_local_space_get_active(constraint->ls,
416
3.67k
              constraint->v->el + 1);
417
3.67k
  if (!active)
418
0
    goto error;
419
3.67k
420
3.67k
  first += isl_local_space_offset(constraint->ls, type) - 1;
421
4.95k
  for (i = 0; 
i < n4.95k
;
++i1.28k
)
422
3.67k
    
if (3.67k
active[first + i]3.67k
)
{2.39k
423
2.39k
      involves = isl_bool_true;
424
2.39k
      break;
425
2.39k
    }
426
3.67k
427
3.67k
  free(active);
428
3.67k
429
3.67k
  return involves;
430
0
error:
431
0
  free(active);
432
0
  return isl_bool_error;
433
3.67k
}
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
13.4k
{
441
13.4k
  if (!constraint)
442
0
    return isl_bool_error;
443
13.4k
444
13.4k
  
if (13.4k
pos >= isl_local_space_dim(constraint->ls, type)13.4k
)
445
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
446
13.4k
      "position out of bounds", return isl_bool_error);
447
13.4k
448
13.4k
  pos += isl_local_space_offset(constraint->ls, type);
449
13.4k
  return isl_int_is_pos(constraint->v->el[pos]);
450
13.4k
}
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.77k
{
458
1.77k
  if (!constraint)
459
0
    return isl_bool_error;
460
1.77k
461
1.77k
  
if (1.77k
pos >= isl_local_space_dim(constraint->ls, type)1.77k
)
462
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
463
1.77k
      "position out of bounds", return isl_bool_error);
464
1.77k
465
1.77k
  pos += isl_local_space_offset(constraint->ls, type);
466
1.77k
  return isl_int_is_neg(constraint->v->el[pos]);
467
1.77k
}
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
125
{
479
125
  if (!constraint)
480
0
    return;
481
125
  
isl_int_set125
(*v, constraint->v->el[0]);125
482
125
}
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
322
{
489
322
  isl_ctx *ctx;
490
322
491
322
  if (!constraint)
492
0
    return NULL;
493
322
494
322
  ctx = isl_constraint_get_ctx(constraint);
495
322
  return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
496
322
}
497
498
void isl_constraint_get_coefficient(struct isl_constraint *constraint,
499
  enum isl_dim_type type, int pos, isl_int *v)
500
125
{
501
125
  if (!constraint)
502
0
    return;
503
125
504
125
  
if (125
pos >= isl_local_space_dim(constraint->ls, type)125
)
505
0
    isl_die(constraint->v->ctx, isl_error_invalid,
506
125
      "position out of bounds", return);
507
125
508
125
  pos += isl_local_space_offset(constraint->ls, type);
509
125
  isl_int_set(*v, constraint->v->el[pos]);
510
125
}
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
2.96k
{
518
2.96k
  isl_ctx *ctx;
519
2.96k
520
2.96k
  if (!constraint)
521
0
    return NULL;
522
2.96k
523
2.96k
  ctx = isl_constraint_get_ctx(constraint);
524
2.96k
  if (
pos < 0 || 2.96k
pos >= isl_local_space_dim(constraint->ls, type)2.96k
)
525
0
    isl_die(ctx, isl_error_invalid,
526
2.96k
      "position out of bounds", return NULL);
527
2.96k
528
2.96k
  pos += isl_local_space_offset(constraint->ls, type);
529
2.96k
  return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
530
2.96k
}
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_set11
(constraint->v->el[0], v);11
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
275
{
561
275
  constraint = isl_constraint_cow(constraint);
562
275
  if (
!constraint || 275
!v275
)
563
0
    goto error;
564
275
  
if (275
!isl_val_is_int(v)275
)
565
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
566
275
      "expecting integer value", goto error);
567
275
  constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
568
275
  if (!constraint->v)
569
0
    constraint = isl_constraint_free(constraint);
570
275
  return constraint;
571
0
error:
572
0
  isl_val_free(v);
573
0
  return isl_constraint_free(constraint);
574
275
}
575
576
__isl_give isl_constraint *isl_constraint_set_constant_si(
577
  __isl_take isl_constraint *constraint, int v)
578
1.78k
{
579
1.78k
  constraint = isl_constraint_cow(constraint);
580
1.78k
  if (!constraint)
581
0
    return NULL;
582
1.78k
583
1.78k
  constraint->v = isl_vec_cow(constraint->v);
584
1.78k
  if (!constraint->v)
585
0
    return isl_constraint_free(constraint);
586
1.78k
587
1.78k
  
isl_int_set_si1.78k
(constraint->v->el[0], v);1.78k
588
1.78k
  return constraint;
589
1.78k
}
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 (44
pos >= isl_local_space_dim(constraint->ls, type)44
)
600
0
    isl_die(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 || 0
!v0
)
627
0
    goto error;
628
0
  
if (0
!isl_val_is_int(v)0
)
629
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
630
0
      "expecting integer value", goto error);
631
0
632
0
  
if (0
pos >= isl_local_space_dim(constraint->ls, type)0
)
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
5.54k
{
650
5.54k
  constraint = isl_constraint_cow(constraint);
651
5.54k
  if (!constraint)
652
0
    return NULL;
653
5.54k
654
5.54k
  
if (5.54k
pos >= isl_local_space_dim(constraint->ls, type)5.54k
)
655
0
    isl_die(constraint->v->ctx, isl_error_invalid,
656
5.54k
      "position out of bounds",
657
5.54k
      return isl_constraint_free(constraint));
658
5.54k
659
5.54k
  constraint = isl_constraint_cow(constraint);
660
5.54k
  if (!constraint)
661
0
    return NULL;
662
5.54k
663
5.54k
  constraint->v = isl_vec_cow(constraint->v);
664
5.54k
  if (!constraint->v)
665
0
    return isl_constraint_free(constraint);
666
5.54k
667
5.54k
  pos += isl_local_space_offset(constraint->ls, type);
668
5.54k
  isl_int_set_si(constraint->v->el[pos], v);
669
5.54k
670
5.54k
  return constraint;
671
5.54k
}
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_ui0
(constraint->v->el[0], constraint->v->el[0], 1);0
690
0
  return constraint;
691
0
}
692
693
isl_bool isl_constraint_is_equality(struct isl_constraint *constraint)
694
34.7k
{
695
34.7k
  if (!constraint)
696
0
    return isl_bool_error;
697
34.7k
  return constraint->eq;
698
34.7k
}
699
700
int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
701
2.15k
{
702
2.15k
  int i;
703
2.15k
  int n_div;
704
2.15k
705
2.15k
  if (!constraint)
706
0
    return -1;
707
2.15k
  
if (2.15k
isl_constraint_is_equality(constraint)2.15k
)
708
225
    return 0;
709
1.93k
  n_div = isl_constraint_dim(constraint, isl_dim_div);
710
1.95k
  for (i = 0; 
i < n_div1.95k
;
++i23
)
{35
711
35
    isl_bool is_div;
712
35
    is_div = isl_local_space_is_div_constraint(constraint->ls,
713
35
              constraint->v->el, i);
714
35
    if (
is_div < 0 || 35
is_div35
)
715
12
      return is_div;
716
35
  }
717
1.93k
718
1.92k
  return 0;
719
1.93k
}
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
29.1k
{
729
29.1k
  int k;
730
29.1k
  isl_local_space *ls;
731
29.1k
  struct isl_basic_map *bmap;
732
29.1k
  isl_int *c;
733
29.1k
  unsigned total;
734
29.1k
735
29.1k
  if (!constraint)
736
0
    return NULL;
737
29.1k
738
29.1k
  ls = isl_local_space_copy(constraint->ls);
739
29.1k
  bmap = isl_basic_map_from_local_space(ls);
740
29.1k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
741
29.1k
  if (
isl_constraint_is_equality(constraint)29.1k
)
{12.5k
742
12.5k
    k = isl_basic_map_alloc_equality(bmap);
743
12.5k
    if (k < 0)
744
0
      goto error;
745
12.5k
    c = bmap->eq[k];
746
12.5k
  }
747
16.5k
  else {
748
16.5k
    k = isl_basic_map_alloc_inequality(bmap);
749
16.5k
    if (k < 0)
750
0
      goto error;
751
16.5k
    c = bmap->ineq[k];
752
16.5k
  }
753
29.1k
  total = isl_basic_map_total_dim(bmap);
754
29.1k
  isl_seq_cpy(c, constraint->v->el, 1 + total);
755
29.1k
  isl_constraint_free(constraint);
756
29.1k
  if (bmap)
757
29.1k
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
758
29.1k
  return bmap;
759
0
error:
760
0
  isl_constraint_free(constraint);
761
0
  isl_basic_map_free(bmap);
762
0
  return NULL;
763
29.1k
}
764
765
__isl_give isl_basic_set *isl_basic_set_from_constraint(
766
  __isl_take isl_constraint *constraint)
767
23.7k
{
768
23.7k
  if (!constraint)
769
0
    return NULL;
770
23.7k
771
23.7k
  
if (23.7k
isl_constraint_dim(constraint, isl_dim_in) != 023.7k
)
772
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
773
23.7k
      "not a set constraint", goto error);
774
23.7k
  return bset_from_bmap(isl_basic_map_from_constraint(constraint));
775
0
error:
776
0
  isl_constraint_free(constraint);
777
0
  return NULL;
778
23.7k
}
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
603
{
789
603
  int i;
790
603
  unsigned offset;
791
603
  unsigned total;
792
603
793
603
  if (!bmap)
794
0
    return isl_bool_error;
795
603
  offset = basic_map_offset(bmap, type);
796
603
  total = isl_basic_map_total_dim(bmap);
797
603
  if (pos >= isl_basic_map_dim(bmap, type))
798
0
    isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
799
603
      "invalid position", return isl_bool_error);
800
609
  
for (i = 0; 603
i < bmap->n_eq609
;
++i6
)
{139
801
139
    if (
isl_int_is_zero139
(bmap->eq[i][offset + pos]) ||139
802
133
        isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
803
133
             1+total-offset-pos-1) != -1)
804
6
      continue;
805
133
    
if (133
c133
)
806
125
      *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
807
125
                &bmap->eq[i]);
808
133
    return isl_bool_true;
809
139
  }
810
470
  return isl_bool_false;
811
603
}
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
359
{
822
359
  return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
823
359
                type, pos, c);
824
359
}
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_init0
(m);0
845
0
  for (i = 0; 
i < bset->n_ineq0
;
++i0
)
{0
846
0
    if (isl_int_is_zero(bset->ineq[i][offset + pos]))
847
0
      continue;
848
0
    
if (0
isl_int_is_one0
(bset->ineq[i][offset + pos]))
849
0
      continue;
850
0
    
if (0
isl_int_is_negone0
(bset->ineq[i][offset + pos]))
851
0
      continue;
852
0
    
if (0
isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,0
853
0
            1+total-offset-pos-1) != -1)
854
0
      continue;
855
0
    
for (j = i + 1; 0
j < bset->n_ineq0
;
++j0
)
{0
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_add0
(m, bset->ineq[i][0], bset->ineq[j][0]);0
860
0
      if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
861
0
        continue;
862
0
863
0
      
if (0
isl_int_is_pos0
(bset->ineq[i][offset+pos]))
{0
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_ineq21
;
++j13
)
{13
942
13
    if (j == u)
943
8
      continue;
944
5
    
if (5
!5
isl_int_is_neg5
(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_ineq23
;
++j14
)
{14
972
14
    if (j == l)
973
9
      continue;
974
5
    
if (5
!5
isl_int_is_pos5
(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_ineq21
;
++i13
)
{13
998
13
    if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
999
5
      continue;
1000
13
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)8
)
{0
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 || 8
!context_i8
)
1010
0
      goto error;
1011
8
    
if (8
fn(NULL, upper, context_i, user) < 08
)
1012
0
      break;
1013
8
  }
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_ineq23
;
++i14
)
{14
1040
14
    if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1041
5
      continue;
1042
14
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)9
)
{0
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 || 9
!context_i9
)
1052
0
      goto error;
1053
9
    
if (9
fn(lower, NULL, context_i, user) < 09
)
1054
0
      break;
1055
9
  }
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_ineq0
;
++i0
)
{0
1083
0
    if (
!0
isl_int_is_pos0
(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)0
)
{0
1089
0
      isl_basic_set_free(context_i);
1090
0
      continue;
1091
0
    }
1092
0
1093
0
    
for (j = 0; 0
j < bset->n_ineq0
;
++j0
)
{0
1094
0
      if (
!0
isl_int_is_neg0
(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)0
)
{0
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 || 0
!upper0
||
!context_j0
)
1114
0
        goto error;
1115
0
      
if (0
fn(lower, upper, context_j, user) < 00
)
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_assert17
(bset->ctx, pos < isl_basic_set_dim(bset, type),17
1172
17
    return isl_stat_error);
1173
17
  
isl_assert17
(bset->ctx, type == isl_dim_param || type == isl_dim_set,17
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_eq17
;
++i0
)
{0
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 || 0
!upper0
||
!context0
)
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_ineq44
;
++i27
)
{27
1197
27
    if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1198
9
      n_lower++;
1199
18
    else 
if (18
isl_int_is_neg18
(bset->ineq[i][1 + abs_pos]))
1200
8
      n_upper++;
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 >= 044
;
--i27
)
1208
27
    
if (27
!27
isl_int_is_zero27
(context->ineq[i][1 + abs_pos]))
1209
17
      isl_basic_set_drop_inequality(context, i);
1210
17
1211
17
  context = isl_basic_set_drop(context, type, pos, 1);
1212
17
  if (
!n_lower && 17
!n_upper8
)
1213
0
    return fn(NULL, NULL, context, user);
1214
17
  
if (17
!n_lower17
)
1215
8
    return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1216
8
            fn, user);
1217
9
  
if (9
!n_upper9
)
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
9
}
1228
1229
__isl_give isl_aff *isl_constraint_get_bound(
1230
  __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1231
2.20k
{
1232
2.20k
  isl_aff *aff;
1233
2.20k
  isl_ctx *ctx;
1234
2.20k
1235
2.20k
  if (!constraint)
1236
0
    return NULL;
1237
2.20k
  ctx = isl_constraint_get_ctx(constraint);
1238
2.20k
  if (pos >= isl_constraint_dim(constraint, type))
1239
0
    isl_die(ctx, isl_error_invalid,
1240
2.20k
      "index out of bounds", return NULL);
1241
2.20k
  
if (2.20k
isl_constraint_dim(constraint, isl_dim_in) != 02.20k
)
1242
0
    isl_die(ctx, isl_error_invalid,
1243
2.20k
      "not a set constraint", return NULL);
1244
2.20k
1245
2.20k
  pos += offset(constraint, type);
1246
2.20k
  if (isl_int_is_zero(constraint->v->el[pos]))
1247
0
    isl_die(ctx, isl_error_invalid,
1248
2.20k
      "constraint does not define a bound on given dimension",
1249
2.20k
      return NULL);
1250
2.20k
1251
2.20k
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1252
2.20k
  if (!aff)
1253
0
    return NULL;
1254
2.20k
1255
2.20k
  
if (2.20k
isl_int_is_neg2.20k
(constraint->v->el[pos]))
1256
745
    isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1257
2.20k
  else
1258
1.45k
    isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1259
2.20k
  isl_int_set_si(aff->v->el[1 + pos], 0);
1260
2.20k
  isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1261
2.20k
1262
2.20k
  return aff;
1263
2.20k
}
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
536
{
1278
536
  isl_aff *aff;
1279
536
1280
536
  if (!constraint)
1281
0
    return NULL;
1282
536
1283
536
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1284
536
  if (!aff)
1285
0
    return NULL;
1286
536
1287
536
  isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1288
536
  isl_int_set_si(aff->v->el[0], 1);
1289
536
1290
536
  return aff;
1291
536
}
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
24.5k
{
1301
24.5k
  isl_local_space *ls;
1302
24.5k
  isl_vec *v;
1303
24.5k
1304
24.5k
  if (!aff)
1305
0
    return NULL;
1306
24.5k
  ls = isl_aff_get_domain_local_space(aff);
1307
24.5k
  v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1308
24.5k
  isl_aff_free(aff);
1309
24.5k
1310
24.5k
  return isl_constraint_alloc_vec(eq, ls, v);
1311
24.5k
}
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
9.17k
{
1318
9.17k
  return isl_constraint_alloc_aff(1, aff);
1319
9.17k
}
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
15.3k
{
1326
15.3k
  return isl_constraint_alloc_aff(0, aff);
1327
15.3k
}
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
23
{
1340
23
  int cmp;
1341
23
  int last1, last2;
1342
23
1343
23
  if (c1 == c2)
1344
0
    return 0;
1345
23
  
if (23
!c123
)
1346
0
    return -1;
1347
23
  
if (23
!c223
)
1348
0
    return 1;
1349
23
  cmp = isl_local_space_cmp(c1->ls, c2->ls);
1350
23
  if (cmp != 0)
1351
0
    return cmp;
1352
23
1353
23
  last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1354
23
  last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1355
23
  if (last1 != last2)
1356
0
    return last1 - last2;
1357
23
1358
23
  return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1359
23
}
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
104
{
1375
104
  int cmp;
1376
104
  int last1, last2;
1377
104
1378
104
  if (c1 == c2)
1379
0
    return 0;
1380
104
  
if (104
!c1104
)
1381
0
    return -1;
1382
104
  
if (104
!c2104
)
1383
0
    return 1;
1384
104
  cmp = isl_local_space_cmp(c1->ls, c2->ls);
1385
104
  if (cmp != 0)
1386
0
    return cmp;
1387
104
1388
104
  last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1389
104
  last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1390
104
  if (last1 != last2)
1391
81
    return last1 - last2;
1392
23
  
if (23
last1 == -123
)
1393
0
    return 0;
1394
23
  
return 23
isl_int_abs_cmp23
(c1->v->el[1 + last1], c2->v->el[1 + last2]);
1395
23
}