Coverage Report

Created: 2017-03-27 23:01

/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
10.8k
{
33
10.8k
  return c ? isl_local_space_get_ctx(c->ls) : NULL;
34
10.8k
}
35
36
static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
37
32.8k
{
38
32.8k
  return isl_local_space_dim(c->ls, type);
39
32.8k
}
40
41
static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
42
1.95k
{
43
1.95k
  return isl_local_space_offset(c->ls, type);
44
1.95k
}
45
46
static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
47
              enum isl_dim_type type)
48
586
{
49
236
  return type == isl_dim_div ? 1 + isl_space_dim(bmap->dim, isl_dim_all)
50
350
           : 1 + isl_space_offset(bmap->dim, type);
51
586
}
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
38.7k
{
69
38.7k
  isl_constraint *constraint;
70
38.7k
71
38.7k
  if (
!ls || 38.7k
!v38.7k
)
72
0
    goto error;
73
38.7k
74
38.7k
  
constraint = 38.7k
isl_alloc_type38.7k
(isl_vec_get_ctx(v), isl_constraint);
75
38.7k
  if (!constraint)
76
0
    goto error;
77
38.7k
78
38.7k
  constraint->ref = 1;
79
38.7k
  constraint->eq = eq;
80
38.7k
  constraint->ls = ls;
81
38.7k
  constraint->v = v;
82
38.7k
83
38.7k
  return constraint;
84
0
error:
85
0
  isl_local_space_free(ls);
86
0
  isl_vec_free(v);
87
0
  return NULL;
88
38.7k
}
89
90
__isl_give isl_constraint *isl_constraint_alloc(int eq,
91
  __isl_take isl_local_space *ls)
92
2.49k
{
93
2.49k
  isl_ctx *ctx;
94
2.49k
  isl_vec *v;
95
2.49k
96
2.49k
  if (!ls)
97
0
    return NULL;
98
2.49k
99
2.49k
  ctx = isl_local_space_get_ctx(ls);
100
2.49k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
101
2.49k
  v = isl_vec_clr(v);
102
2.49k
  return isl_constraint_alloc_vec(eq, ls, v);
103
2.49k
}
104
105
struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
106
  isl_int **line)
107
13.8k
{
108
13.8k
  int eq;
109
13.8k
  isl_ctx *ctx;
110
13.8k
  isl_vec *v;
111
13.8k
  isl_local_space *ls = NULL;
112
13.8k
  isl_constraint *constraint;
113
13.8k
114
13.8k
  if (
!bmap || 13.8k
!line13.8k
)
115
0
    goto error;
116
13.8k
117
13.8k
  eq = line >= bmap->eq;
118
13.8k
119
13.8k
  ctx = isl_basic_map_get_ctx(bmap);
120
13.8k
  ls = isl_basic_map_get_local_space(bmap);
121
13.8k
  v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
122
13.8k
  if (!v)
123
0
    goto error;
124
13.8k
  isl_seq_cpy(v->el, line[0], v->size);
125
13.8k
  constraint = isl_constraint_alloc_vec(eq, ls, v);
126
13.8k
127
13.8k
  isl_basic_map_free(bmap);
128
13.8k
  return constraint;
129
0
error:
130
0
  isl_local_space_free(ls);
131
0
  isl_basic_map_free(bmap);
132
0
  return NULL;
133
13.8k
}
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
1.84k
{
144
1.84k
  return isl_constraint_alloc(1, ls);
145
1.84k
}
146
147
__isl_give isl_constraint *isl_constraint_alloc_inequality(
148
  __isl_take isl_local_space *ls)
149
654
{
150
654
  return isl_constraint_alloc(0, ls);
151
654
}
152
153
struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
154
0
{
155
0
  if (!c)
156
0
    return NULL;
157
0
158
0
  return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
159
0
            isl_vec_copy(c->v));
160
0
}
161
162
struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
163
12.2k
{
164
12.2k
  if (!c)
165
0
    return NULL;
166
12.2k
167
12.2k
  
if (12.2k
c->ref == 112.2k
)
168
12.2k
    return c;
169
0
  c->ref--;
170
0
  return isl_constraint_dup(c);
171
12.2k
}
172
173
struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
174
6.13k
{
175
6.13k
  if (!constraint)
176
0
    return NULL;
177
6.13k
178
6.13k
  constraint->ref++;
179
6.13k
  return constraint;
180
6.13k
}
181
182
__isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c)
183
44.8k
{
184
44.8k
  if (!c)
185
3
    return NULL;
186
44.8k
187
44.8k
  
if (44.8k
--c->ref > 044.8k
)
188
6.13k
    return NULL;
189
44.8k
190
38.7k
  isl_local_space_free(c->ls);
191
38.7k
  isl_vec_free(c->v);
192
38.7k
  free(c);
193
38.7k
194
38.7k
  return NULL;
195
44.8k
}
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.46k
{
203
1.46k
  if (!bmap)
204
0
    return -1;
205
1.46k
206
1.46k
  return bmap->n_eq + bmap->n_ineq;
207
1.46k
}
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
4.53k
{
221
4.53k
  int i;
222
4.53k
  struct isl_constraint *c;
223
4.53k
224
4.53k
  if (!bmap)
225
0
    return isl_stat_error;
226
4.53k
227
4.53k
  
isl_assert4.53k
(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),4.53k
228
4.53k
      return isl_stat_error);
229
4.53k
230
8.10k
  
for (i = 0; 4.53k
i < bmap->n_eq8.10k
;
++i3.57k
)
{3.57k
231
3.57k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
232
3.57k
            &bmap->eq[i]);
233
3.57k
    if (!c)
234
0
      return isl_stat_error;
235
3.57k
    
if (3.57k
fn(c, user) < 03.57k
)
236
3
      return isl_stat_error;
237
3.57k
  }
238
4.53k
239
14.6k
  
for (i = 0; 4.53k
i < bmap->n_ineq14.6k
;
++i10.1k
)
{10.1k
240
10.1k
    c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
241
10.1k
            &bmap->ineq[i]);
242
10.1k
    if (!c)
243
0
      return isl_stat_error;
244
10.1k
    
if (10.1k
fn(c, user) < 010.1k
)
245
3
      return isl_stat_error;
246
10.1k
  }
247
4.53k
248
4.52k
  return isl_stat_ok;
249
4.53k
}
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.06k
{
254
3.06k
  return isl_basic_map_foreach_constraint(bset_to_bmap(bset), fn, user);
255
3.06k
}
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
1.97k
{
263
1.97k
  isl_constraint_list **list = user;
264
1.97k
265
1.97k
  if (isl_constraint_is_div_constraint(constraint))
266
12
    isl_constraint_free(constraint);
267
1.97k
  else
268
1.96k
    *list = isl_constraint_list_add(*list, constraint);
269
1.97k
270
1.97k
  return isl_stat_ok;
271
1.97k
}
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.46k
{
282
1.46k
  int n;
283
1.46k
  int known;
284
1.46k
  isl_ctx *ctx;
285
1.46k
  isl_constraint_list *list;
286
1.46k
287
1.46k
  known = isl_basic_map_divs_known(bmap);
288
1.46k
  if (known < 0)
289
0
    return NULL;
290
1.46k
  ctx = isl_basic_map_get_ctx(bmap);
291
1.46k
  if (!known)
292
0
    isl_die(ctx, isl_error_invalid,
293
1.46k
      "input involves unknown divs", return NULL);
294
1.46k
295
1.46k
  n = isl_basic_map_n_constraint(bmap);
296
1.46k
  list = isl_constraint_list_alloc(ctx, n);
297
1.46k
  if (isl_basic_map_foreach_constraint(bmap,
298
1.46k
              &collect_constraint, &list) < 0)
299
0
    list = isl_constraint_list_free(list);
300
1.46k
301
1.46k
  return list;
302
1.46k
}
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.39k
{
310
1.39k
  return isl_basic_map_get_constraint_list(bset);
311
1.39k
}
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.14k
{
331
1.14k
  isl_ctx *ctx;
332
1.14k
  isl_space *dim;
333
1.14k
  int equal_space;
334
1.14k
335
1.14k
  if (
!bmap || 1.14k
!constraint1.14k
)
336
0
    goto error;
337
1.14k
338
1.14k
  ctx = isl_constraint_get_ctx(constraint);
339
1.14k
  dim = isl_constraint_get_space(constraint);
340
1.14k
  equal_space = isl_space_is_equal(bmap->dim, dim);
341
1.14k
  isl_space_free(dim);
342
1.14k
  isl_assert(ctx, equal_space, goto error);
343
1.14k
344
1.14k
  bmap = isl_basic_map_intersect(bmap,
345
1.14k
        isl_basic_map_from_constraint(constraint));
346
1.14k
  return bmap;
347
0
error:
348
0
  isl_basic_map_free(bmap);
349
0
  isl_constraint_free(constraint);
350
0
  return NULL;
351
1.14k
}
352
353
struct isl_basic_set *isl_basic_set_add_constraint(
354
  struct isl_basic_set *bset, struct isl_constraint *constraint)
355
1.10k
{
356
1.10k
  return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset),
357
1.10k
                  constraint));
358
1.10k
}
359
360
__isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
361
  __isl_take isl_constraint *constraint)
362
3.53k
{
363
3.53k
  isl_basic_map *bmap;
364
3.53k
365
3.53k
  bmap = isl_basic_map_from_constraint(constraint);
366
3.53k
  map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
367
3.53k
368
3.53k
  return map;
369
3.53k
}
370
371
__isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
372
  __isl_take isl_constraint *constraint)
373
1.60k
{
374
1.60k
  return isl_map_add_constraint(set, constraint);
375
1.60k
}
376
377
__isl_give isl_space *isl_constraint_get_space(
378
  __isl_keep isl_constraint *constraint)
379
1.14k
{
380
1.14k
  return constraint ? isl_local_space_get_space(constraint->ls) : NULL;
381
1.14k
}
382
383
__isl_give isl_local_space *isl_constraint_get_local_space(
384
  __isl_keep isl_constraint *constraint)
385
240
{
386
240
  return constraint ? isl_local_space_copy(constraint->ls) : NULL;
387
240
}
388
389
int isl_constraint_dim(struct isl_constraint *constraint,
390
  enum isl_dim_type type)
391
32.8k
{
392
32.8k
  if (!constraint)
393
0
    return -1;
394
32.8k
  return n(constraint, type);
395
32.8k
}
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.25k
{
400
3.25k
  int i;
401
3.25k
  isl_ctx *ctx;
402
3.25k
  int *active = NULL;
403
3.25k
  isl_bool involves = isl_bool_false;
404
3.25k
405
3.25k
  if (!constraint)
406
0
    return isl_bool_error;
407
3.25k
  
if (3.25k
n == 03.25k
)
408
0
    return isl_bool_false;
409
3.25k
410
3.25k
  ctx = isl_constraint_get_ctx(constraint);
411
3.25k
  if (first + n > isl_constraint_dim(constraint, type))
412
0
    isl_die(ctx, isl_error_invalid,
413
3.25k
      "range out of bounds", return isl_bool_error);
414
3.25k
415
3.25k
  active = isl_local_space_get_active(constraint->ls,
416
3.25k
              constraint->v->el + 1);
417
3.25k
  if (!active)
418
0
    goto error;
419
3.25k
420
3.25k
  first += isl_local_space_offset(constraint->ls, type) - 1;
421
4.53k
  for (i = 0; 
i < n4.53k
;
++i1.28k
)
422
3.25k
    
if (3.25k
active[first + i]3.25k
)
{1.97k
423
1.97k
      involves = isl_bool_true;
424
1.97k
      break;
425
1.97k
    }
426
3.25k
427
3.25k
  free(active);
428
3.25k
429
3.25k
  return involves;
430
0
error:
431
0
  free(active);
432
0
  return isl_bool_error;
433
3.25k
}
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
12.2k
{
441
12.2k
  if (!constraint)
442
0
    return isl_bool_error;
443
12.2k
444
12.2k
  
if (12.2k
pos >= isl_local_space_dim(constraint->ls, type)12.2k
)
445
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
446
12.2k
      "position out of bounds", return isl_bool_error);
447
12.2k
448
12.2k
  pos += isl_local_space_offset(constraint->ls, type);
449
12.2k
  return isl_int_is_pos(constraint->v->el[pos]);
450
12.2k
}
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.65k
{
458
1.65k
  if (!constraint)
459
0
    return isl_bool_error;
460
1.65k
461
1.65k
  
if (1.65k
pos >= isl_local_space_dim(constraint->ls, type)1.65k
)
462
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
463
1.65k
      "position out of bounds", return isl_bool_error);
464
1.65k
465
1.65k
  pos += isl_local_space_offset(constraint->ls, type);
466
1.65k
  return isl_int_is_neg(constraint->v->el[pos]);
467
1.65k
}
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
116
{
479
116
  if (!constraint)
480
0
    return;
481
116
  
isl_int_set116
(*v, constraint->v->el[0]);116
482
116
}
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
248
{
489
248
  isl_ctx *ctx;
490
248
491
248
  if (!constraint)
492
0
    return NULL;
493
248
494
248
  ctx = isl_constraint_get_ctx(constraint);
495
248
  return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
496
248
}
497
498
void isl_constraint_get_coefficient(struct isl_constraint *constraint,
499
  enum isl_dim_type type, int pos, isl_int *v)
500
116
{
501
116
  if (!constraint)
502
0
    return;
503
116
504
116
  
if (116
pos >= isl_local_space_dim(constraint->ls, type)116
)
505
0
    isl_die(constraint->v->ctx, isl_error_invalid,
506
116
      "position out of bounds", return);
507
116
508
116
  pos += isl_local_space_offset(constraint->ls, type);
509
116
  isl_int_set(*v, constraint->v->el[pos]);
510
116
}
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.48k
{
518
2.48k
  isl_ctx *ctx;
519
2.48k
520
2.48k
  if (!constraint)
521
0
    return NULL;
522
2.48k
523
2.48k
  ctx = isl_constraint_get_ctx(constraint);
524
2.48k
  if (
pos < 0 || 2.48k
pos >= isl_local_space_dim(constraint->ls, type)2.48k
)
525
0
    isl_die(ctx, isl_error_invalid,
526
2.48k
      "position out of bounds", return NULL);
527
2.48k
528
2.48k
  pos += isl_local_space_offset(constraint->ls, type);
529
2.48k
  return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
530
2.48k
}
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
209
{
561
209
  constraint = isl_constraint_cow(constraint);
562
209
  if (
!constraint || 209
!v209
)
563
0
    goto error;
564
209
  
if (209
!isl_val_is_int(v)209
)
565
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
566
209
      "expecting integer value", goto error);
567
209
  constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
568
209
  if (!constraint->v)
569
0
    constraint = isl_constraint_free(constraint);
570
209
  return constraint;
571
0
error:
572
0
  isl_val_free(v);
573
0
  return isl_constraint_free(constraint);
574
209
}
575
576
__isl_give isl_constraint *isl_constraint_set_constant_si(
577
  __isl_take isl_constraint *constraint, int v)
578
1.63k
{
579
1.63k
  constraint = isl_constraint_cow(constraint);
580
1.63k
  if (!constraint)
581
0
    return NULL;
582
1.63k
583
1.63k
  constraint->v = isl_vec_cow(constraint->v);
584
1.63k
  if (!constraint->v)
585
0
    return isl_constraint_free(constraint);
586
1.63k
587
1.63k
  
isl_int_set_si1.63k
(constraint->v->el[0], v);1.63k
588
1.63k
  return constraint;
589
1.63k
}
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.13k
{
650
5.13k
  constraint = isl_constraint_cow(constraint);
651
5.13k
  if (!constraint)
652
0
    return NULL;
653
5.13k
654
5.13k
  
if (5.13k
pos >= isl_local_space_dim(constraint->ls, type)5.13k
)
655
0
    isl_die(constraint->v->ctx, isl_error_invalid,
656
5.13k
      "position out of bounds",
657
5.13k
      return isl_constraint_free(constraint));
658
5.13k
659
5.13k
  constraint = isl_constraint_cow(constraint);
660
5.13k
  if (!constraint)
661
0
    return NULL;
662
5.13k
663
5.13k
  constraint->v = isl_vec_cow(constraint->v);
664
5.13k
  if (!constraint->v)
665
0
    return isl_constraint_free(constraint);
666
5.13k
667
5.13k
  pos += isl_local_space_offset(constraint->ls, type);
668
5.13k
  isl_int_set_si(constraint->v->el[pos], v);
669
5.13k
670
5.13k
  return constraint;
671
5.13k
}
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
31.3k
{
695
31.3k
  if (!constraint)
696
0
    return isl_bool_error;
697
31.3k
  return constraint->eq;
698
31.3k
}
699
700
int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
701
1.97k
{
702
1.97k
  int i;
703
1.97k
  int n_div;
704
1.97k
705
1.97k
  if (!constraint)
706
0
    return -1;
707
1.97k
  
if (1.97k
isl_constraint_is_equality(constraint)1.97k
)
708
210
    return 0;
709
1.76k
  n_div = isl_constraint_dim(constraint, isl_dim_div);
710
1.79k
  for (i = 0; 
i < n_div1.79k
;
++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.76k
718
1.75k
  return 0;
719
1.76k
}
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
26.4k
{
729
26.4k
  int k;
730
26.4k
  isl_local_space *ls;
731
26.4k
  struct isl_basic_map *bmap;
732
26.4k
  isl_int *c;
733
26.4k
  unsigned total;
734
26.4k
735
26.4k
  if (!constraint)
736
0
    return NULL;
737
26.4k
738
26.4k
  ls = isl_local_space_copy(constraint->ls);
739
26.4k
  bmap = isl_basic_map_from_local_space(ls);
740
26.4k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
741
26.4k
  if (
isl_constraint_is_equality(constraint)26.4k
)
{11.1k
742
11.1k
    k = isl_basic_map_alloc_equality(bmap);
743
11.1k
    if (k < 0)
744
0
      goto error;
745
11.1k
    c = bmap->eq[k];
746
11.1k
  }
747
15.2k
  else {
748
15.2k
    k = isl_basic_map_alloc_inequality(bmap);
749
15.2k
    if (k < 0)
750
0
      goto error;
751
15.2k
    c = bmap->ineq[k];
752
15.2k
  }
753
26.4k
  total = isl_basic_map_total_dim(bmap);
754
26.4k
  isl_seq_cpy(c, constraint->v->el, 1 + total);
755
26.4k
  isl_constraint_free(constraint);
756
26.4k
  if (bmap)
757
26.4k
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
758
26.4k
  return bmap;
759
0
error:
760
0
  isl_constraint_free(constraint);
761
0
  isl_basic_map_free(bmap);
762
0
  return NULL;
763
26.4k
}
764
765
struct isl_basic_set *isl_basic_set_from_constraint(
766
  struct isl_constraint *constraint)
767
21.7k
{
768
21.7k
  if (!constraint)
769
0
    return NULL;
770
21.7k
771
21.7k
  
if (21.7k
isl_constraint_dim(constraint, isl_dim_in) != 021.7k
)
772
0
    isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
773
21.7k
      "not a set constraint", goto error);
774
21.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
21.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
586
{
789
586
  int i;
790
586
  unsigned offset;
791
586
  unsigned total;
792
586
793
586
  if (!bmap)
794
0
    return isl_bool_error;
795
586
  offset = basic_map_offset(bmap, type);
796
586
  total = isl_basic_map_total_dim(bmap);
797
586
  if (pos >= isl_basic_map_dim(bmap, type))
798
0
    isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
799
586
      "invalid position", return isl_bool_error);
800
592
  
for (i = 0; 586
i < bmap->n_eq592
;
++i6
)
{126
801
126
    if (
isl_int_is_zero126
(bmap->eq[i][offset + pos]) ||126
802
120
        isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
803
120
             1+total-offset-pos-1) != -1)
804
6
      continue;
805
120
    
if (120
c120
)
806
116
      *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
807
116
                &bmap->eq[i]);
808
120
    return isl_bool_true;
809
126
  }
810
466
  return isl_bool_false;
811
586
}
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
350
{
822
350
  return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
823
350
                type, pos, c);
824
350
}
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
1.95k
{
1232
1.95k
  isl_aff *aff;
1233
1.95k
  isl_ctx *ctx;
1234
1.95k
1235
1.95k
  if (!constraint)
1236
0
    return NULL;
1237
1.95k
  ctx = isl_constraint_get_ctx(constraint);
1238
1.95k
  if (pos >= isl_constraint_dim(constraint, type))
1239
0
    isl_die(ctx, isl_error_invalid,
1240
1.95k
      "index out of bounds", return NULL);
1241
1.95k
  
if (1.95k
isl_constraint_dim(constraint, isl_dim_in) != 01.95k
)
1242
0
    isl_die(ctx, isl_error_invalid,
1243
1.95k
      "not a set constraint", return NULL);
1244
1.95k
1245
1.95k
  pos += offset(constraint, type);
1246
1.95k
  if (isl_int_is_zero(constraint->v->el[pos]))
1247
0
    isl_die(ctx, isl_error_invalid,
1248
1.95k
      "constraint does not define a bound on given dimension",
1249
1.95k
      return NULL);
1250
1.95k
1251
1.95k
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1252
1.95k
  if (!aff)
1253
0
    return NULL;
1254
1.95k
1255
1.95k
  
if (1.95k
isl_int_is_neg1.95k
(constraint->v->el[pos]))
1256
687
    isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1257
1.95k
  else
1258
1.27k
    isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1259
1.95k
  isl_int_set_si(aff->v->el[1 + pos], 0);
1260
1.95k
  isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1261
1.95k
1262
1.95k
  return aff;
1263
1.95k
}
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
486
{
1278
486
  isl_aff *aff;
1279
486
1280
486
  if (!constraint)
1281
0
    return NULL;
1282
486
1283
486
  aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1284
486
  if (!aff)
1285
0
    return NULL;
1286
486
1287
486
  isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1288
486
  isl_int_set_si(aff->v->el[0], 1);
1289
486
1290
486
  return aff;
1291
486
}
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
22.3k
{
1301
22.3k
  isl_local_space *ls;
1302
22.3k
  isl_vec *v;
1303
22.3k
1304
22.3k
  if (!aff)
1305
0
    return NULL;
1306
22.3k
  ls = isl_aff_get_domain_local_space(aff);
1307
22.3k
  v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1308
22.3k
  isl_aff_free(aff);
1309
22.3k
1310
22.3k
  return isl_constraint_alloc_vec(eq, ls, v);
1311
22.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
8.16k
{
1318
8.16k
  return isl_constraint_alloc_aff(1, aff);
1319
8.16k
}
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
14.2k
{
1326
14.2k
  return isl_constraint_alloc_aff(0, aff);
1327
14.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
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
}