Coverage Report

Created: 2017-03-24 03:18

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_ilp.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8
 */
9
10
#include <isl_ctx_private.h>
11
#include <isl_map_private.h>
12
#include <isl/ilp.h>
13
#include <isl/union_set.h>
14
#include "isl_sample.h"
15
#include <isl_seq.h>
16
#include "isl_equalities.h"
17
#include <isl_aff_private.h>
18
#include <isl_local_space_private.h>
19
#include <isl_mat_private.h>
20
#include <isl_val_private.h>
21
#include <isl_vec_private.h>
22
#include <isl_lp_private.h>
23
#include <isl_ilp_private.h>
24
#include <isl/deprecated/ilp_int.h>
25
26
/* Given a basic set "bset", construct a basic set U such that for
27
 * each element x in U, the whole unit box positioned at x is inside
28
 * the given basic set.
29
 * Note that U may not contain all points that satisfy this property.
30
 *
31
 * We simply add the sum of all negative coefficients to the constant
32
 * term.  This ensures that if x satisfies the resulting constraints,
33
 * then x plus any sum of unit vectors satisfies the original constraints.
34
 */
35
static struct isl_basic_set *unit_box_base_points(struct isl_basic_set *bset)
36
200
{
37
200
  int i, j, k;
38
200
  struct isl_basic_set *unit_box = NULL;
39
200
  unsigned total;
40
200
41
200
  if (!bset)
42
0
    goto error;
43
200
44
200
  
if (200
bset->n_eq != 0200
)
{0
45
0
    isl_space *space = isl_basic_set_get_space(bset);
46
0
    isl_basic_set_free(bset);
47
0
    return isl_basic_set_empty(space);
48
0
  }
49
200
50
200
  total = isl_basic_set_total_dim(bset);
51
200
  unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset),
52
200
          0, 0, bset->n_ineq);
53
200
54
626
  for (i = 0; 
i < bset->n_ineq626
;
++i426
)
{426
55
426
    k = isl_basic_set_alloc_inequality(unit_box);
56
426
    if (k < 0)
57
0
      goto error;
58
426
    isl_seq_cpy(unit_box->ineq[k], bset->ineq[i], 1 + total);
59
2.55k
    for (j = 0; 
j < total2.55k
;
++j2.12k
)
{2.12k
60
2.12k
      if (isl_int_is_nonneg(unit_box->ineq[k][1 + j]))
61
1.89k
        continue;
62
229
      
isl_int_add229
(unit_box->ineq[k][0],229
63
229
        unit_box->ineq[k][0], unit_box->ineq[k][1 + j]);
64
229
    }
65
426
  }
66
200
67
200
  isl_basic_set_free(bset);
68
200
  return unit_box;
69
0
error:
70
0
  isl_basic_set_free(bset);
71
0
  isl_basic_set_free(unit_box);
72
0
  return NULL;
73
200
}
74
75
/* Find an integer point in "bset", preferably one that is
76
 * close to minimizing "f".
77
 *
78
 * We first check if we can easily put unit boxes inside bset.
79
 * If so, we take the best base point of any of the unit boxes we can find
80
 * and round it up to the nearest integer.
81
 * If not, we simply pick any integer point in "bset".
82
 */
83
static struct isl_vec *initial_solution(struct isl_basic_set *bset, isl_int *f)
84
200
{
85
200
  enum isl_lp_result res;
86
200
  struct isl_basic_set *unit_box;
87
200
  struct isl_vec *sol;
88
200
89
200
  unit_box = unit_box_base_points(isl_basic_set_copy(bset));
90
200
91
200
  res = isl_basic_set_solve_lp(unit_box, 0, f, bset->ctx->one,
92
200
          NULL, NULL, &sol);
93
200
  if (
res == isl_lp_ok200
)
{4
94
4
    isl_basic_set_free(unit_box);
95
4
    return isl_vec_ceil(sol);
96
4
  }
97
200
98
196
  isl_basic_set_free(unit_box);
99
196
100
196
  return isl_basic_set_sample_vec(isl_basic_set_copy(bset));
101
200
}
102
103
/* Restrict "bset" to those points with values for f in the interval [l, u].
104
 */
105
static struct isl_basic_set *add_bounds(struct isl_basic_set *bset,
106
  isl_int *f, isl_int l, isl_int u)
107
35
{
108
35
  int k;
109
35
  unsigned total;
110
35
111
35
  total = isl_basic_set_total_dim(bset);
112
35
  bset = isl_basic_set_extend_constraints(bset, 0, 2);
113
35
114
35
  k = isl_basic_set_alloc_inequality(bset);
115
35
  if (k < 0)
116
0
    goto error;
117
35
  isl_seq_cpy(bset->ineq[k], f, 1 + total);
118
35
  isl_int_sub(bset->ineq[k][0], bset->ineq[k][0], l);
119
35
120
35
  k = isl_basic_set_alloc_inequality(bset);
121
35
  if (k < 0)
122
0
    goto error;
123
35
  isl_seq_neg(bset->ineq[k], f, 1 + total);
124
35
  isl_int_add(bset->ineq[k][0], bset->ineq[k][0], u);
125
35
126
35
  return bset;
127
0
error:
128
0
  isl_basic_set_free(bset);
129
0
  return NULL;
130
35
}
131
132
/* Find an integer point in "bset" that minimizes f (in any) such that
133
 * the value of f lies inside the interval [l, u].
134
 * Return this integer point if it can be found.
135
 * Otherwise, return sol.
136
 *
137
 * We perform a number of steps until l > u.
138
 * In each step, we look for an integer point with value in either
139
 * the whole interval [l, u] or half of the interval [l, l+floor(u-l-1/2)].
140
 * The choice depends on whether we have found an integer point in the
141
 * previous step.  If so, we look for the next point in half of the remaining
142
 * interval.
143
 * If we find a point, the current solution is updated and u is set
144
 * to its value minus 1.
145
 * If no point can be found, we update l to the upper bound of the interval
146
 * we checked (u or l+floor(u-l-1/2)) plus 1.
147
 */
148
static struct isl_vec *solve_ilp_search(struct isl_basic_set *bset,
149
  isl_int *f, isl_int *opt, struct isl_vec *sol, isl_int l, isl_int u)
150
5
{
151
5
  isl_int tmp;
152
5
  int divide = 1;
153
5
154
5
  isl_int_init(tmp);
155
5
156
36
  while (
isl_int_le36
(l, u))
{35
157
35
    struct isl_basic_set *slice;
158
35
    struct isl_vec *sample;
159
35
160
35
    if (!divide)
161
4
      isl_int_set(tmp, u);
162
31
    else {
163
31
      isl_int_sub(tmp, u, l);
164
31
      isl_int_fdiv_q_ui(tmp, tmp, 2);
165
31
      isl_int_add(tmp, tmp, l);
166
31
    }
167
35
    slice = add_bounds(isl_basic_set_copy(bset), f, l, tmp);
168
35
    sample = isl_basic_set_sample_vec(slice);
169
35
    if (
!sample35
)
{0
170
0
      isl_vec_free(sol);
171
0
      sol = NULL;
172
0
      break;
173
0
    }
174
35
    
if (35
sample->size > 035
)
{27
175
27
      isl_vec_free(sol);
176
27
      sol = sample;
177
27
      isl_seq_inner_product(f, sol->el, sol->size, opt);
178
27
      isl_int_sub_ui(u, *opt, 1);
179
27
      divide = 1;
180
8
    } else {
181
8
      isl_vec_free(sample);
182
8
      if (!divide)
183
4
        break;
184
4
      
isl_int_add_ui4
(l, tmp, 1);4
185
4
      divide = 0;
186
4
    }
187
35
  }
188
5
189
5
  isl_int_clear(tmp);
190
5
191
5
  return sol;
192
5
}
193
194
/* Find an integer point in "bset" that minimizes f (if any).
195
 * If sol_p is not NULL then the integer point is returned in *sol_p.
196
 * The optimal value of f is returned in *opt.
197
 *
198
 * The algorithm maintains a currently best solution and an interval [l, u]
199
 * of values of f for which integer solutions could potentially still be found.
200
 * The initial value of the best solution so far is any solution.
201
 * The initial value of l is minimal value of f over the rationals
202
 * (rounded up to the nearest integer).
203
 * The initial value of u is the value of f at the initial solution minus 1.
204
 *
205
 * We then call solve_ilp_search to perform a binary search on the interval.
206
 */
207
static enum isl_lp_result solve_ilp(struct isl_basic_set *bset,
208
              isl_int *f, isl_int *opt,
209
              struct isl_vec **sol_p)
210
969
{
211
969
  enum isl_lp_result res;
212
969
  isl_int l, u;
213
969
  struct isl_vec *sol;
214
969
215
969
  res = isl_basic_set_solve_lp(bset, 0, f, bset->ctx->one,
216
969
          opt, NULL, &sol);
217
969
  if (
res == isl_lp_ok && 969
isl_int_is_one773
(sol->el[0]))
{768
218
768
    if (sol_p)
219
0
      *sol_p = sol;
220
768
    else
221
768
      isl_vec_free(sol);
222
768
    return isl_lp_ok;
223
768
  }
224
201
  isl_vec_free(sol);
225
201
  if (
res == isl_lp_error || 201
res == isl_lp_empty201
)
226
1
    return res;
227
201
228
200
  sol = initial_solution(bset, f);
229
200
  if (!sol)
230
0
    return isl_lp_error;
231
200
  
if (200
sol->size == 0200
)
{0
232
0
    isl_vec_free(sol);
233
0
    return isl_lp_empty;
234
0
  }
235
200
  
if (200
res == isl_lp_unbounded200
)
{195
236
195
    isl_vec_free(sol);
237
195
    return isl_lp_unbounded;
238
195
  }
239
200
240
5
  
isl_int_init5
(l);5
241
5
  isl_int_init(u);
242
5
243
5
  isl_int_set(l, *opt);
244
5
245
5
  isl_seq_inner_product(f, sol->el, sol->size, opt);
246
5
  isl_int_sub_ui(u, *opt, 1);
247
5
248
5
  sol = solve_ilp_search(bset, f, opt, sol, l, u);
249
5
  if (!sol)
250
0
    res = isl_lp_error;
251
5
252
5
  isl_int_clear(l);
253
5
  isl_int_clear(u);
254
5
255
5
  if (sol_p)
256
0
    *sol_p = sol;
257
5
  else
258
5
    isl_vec_free(sol);
259
5
260
5
  return res;
261
200
}
262
263
static enum isl_lp_result solve_ilp_with_eq(struct isl_basic_set *bset, int max,
264
              isl_int *f, isl_int *opt,
265
              struct isl_vec **sol_p)
266
597
{
267
597
  unsigned dim;
268
597
  enum isl_lp_result res;
269
597
  struct isl_mat *T = NULL;
270
597
  struct isl_vec *v;
271
597
272
597
  bset = isl_basic_set_copy(bset);
273
597
  dim = isl_basic_set_total_dim(bset);
274
597
  v = isl_vec_alloc(bset->ctx, 1 + dim);
275
597
  if (!v)
276
0
    goto error;
277
597
  isl_seq_cpy(v->el, f, 1 + dim);
278
597
  bset = isl_basic_set_remove_equalities(bset, &T, NULL);
279
597
  v = isl_vec_mat_product(v, isl_mat_copy(T));
280
597
  if (!v)
281
0
    goto error;
282
597
  res = isl_basic_set_solve_ilp(bset, max, v->el, opt, sol_p);
283
597
  isl_vec_free(v);
284
597
  if (
res == isl_lp_ok && 597
sol_p596
)
{0
285
0
    *sol_p = isl_mat_vec_product(T, *sol_p);
286
0
    if (!*sol_p)
287
0
      res = isl_lp_error;
288
0
  } else
289
597
    isl_mat_free(T);
290
597
  isl_basic_set_free(bset);
291
597
  return res;
292
0
error:
293
0
  isl_mat_free(T);
294
0
  isl_basic_set_free(bset);
295
0
  return isl_lp_error;
296
597
}
297
298
/* Find an integer point in "bset" that minimizes (or maximizes if max is set)
299
 * f (if any).
300
 * If sol_p is not NULL then the integer point is returned in *sol_p.
301
 * The optimal value of f is returned in *opt.
302
 *
303
 * If there is any equality among the points in "bset", then we first
304
 * project it out.  Otherwise, we continue with solve_ilp above.
305
 */
306
enum isl_lp_result isl_basic_set_solve_ilp(struct isl_basic_set *bset, int max,
307
              isl_int *f, isl_int *opt,
308
              struct isl_vec **sol_p)
309
1.56k
{
310
1.56k
  unsigned dim;
311
1.56k
  enum isl_lp_result res;
312
1.56k
313
1.56k
  if (!bset)
314
0
    return isl_lp_error;
315
1.56k
  
if (1.56k
sol_p1.56k
)
316
0
    *sol_p = NULL;
317
1.56k
318
1.56k
  isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0,
319
1.56k
    return isl_lp_error);
320
1.56k
321
1.56k
  
if (1.56k
isl_basic_set_plain_is_empty(bset)1.56k
)
322
1
    return isl_lp_empty;
323
1.56k
324
1.56k
  
if (1.56k
bset->n_eq1.56k
)
325
597
    return solve_ilp_with_eq(bset, max, f, opt, sol_p);
326
1.56k
327
969
  dim = isl_basic_set_total_dim(bset);
328
969
329
969
  if (max)
330
965
    isl_seq_neg(f, f, 1 + dim);
331
969
332
969
  res = solve_ilp(bset, f, opt, sol_p);
333
969
334
969
  if (
max969
)
{965
335
965
    isl_seq_neg(f, f, 1 + dim);
336
965
    isl_int_neg(*opt, *opt);
337
965
  }
338
969
339
969
  return res;
340
1.56k
}
341
342
static enum isl_lp_result basic_set_opt(__isl_keep isl_basic_set *bset, int max,
343
  __isl_keep isl_aff *obj, isl_int *opt)
344
970
{
345
970
  enum isl_lp_result res;
346
970
347
970
  if (!obj)
348
0
    return isl_lp_error;
349
970
  bset = isl_basic_set_copy(bset);
350
970
  bset = isl_basic_set_underlying_set(bset);
351
970
  res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL);
352
970
  isl_basic_set_free(bset);
353
970
  return res;
354
970
}
355
356
static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset)
357
5
{
358
5
  int i;
359
5
  isl_ctx *ctx = isl_basic_set_get_ctx(bset);
360
5
  isl_mat *div;
361
5
362
5
  div = isl_mat_alloc(ctx, bset->n_div,
363
5
          1 + 1 + isl_basic_set_total_dim(bset));
364
5
  if (!div)
365
0
    return NULL;
366
5
367
10
  
for (i = 0; 5
i < bset->n_div10
;
++i5
)
368
5
    isl_seq_cpy(div->row[i], bset->div[i], div->n_col);
369
5
370
5
  return div;
371
5
}
372
373
enum isl_lp_result isl_basic_set_opt(__isl_keep isl_basic_set *bset, int max,
374
  __isl_keep isl_aff *obj, isl_int *opt)
375
970
{
376
970
  int *exp1 = NULL;
377
970
  int *exp2 = NULL;
378
970
  isl_ctx *ctx;
379
970
  isl_mat *bset_div = NULL;
380
970
  isl_mat *div = NULL;
381
970
  enum isl_lp_result res;
382
970
  int bset_n_div, obj_n_div;
383
970
384
970
  if (
!bset || 970
!obj970
)
385
0
    return isl_lp_error;
386
970
387
970
  ctx = isl_aff_get_ctx(obj);
388
970
  if (!isl_space_is_equal(bset->dim, obj->ls->dim))
389
0
    isl_die(ctx, isl_error_invalid,
390
970
      "spaces don't match", return isl_lp_error);
391
970
  
if (970
!970
isl_int_is_one970
(obj->v->el[0]))
392
0
    isl_die(ctx, isl_error_unsupported,
393
970
      "expecting integer affine expression",
394
970
      return isl_lp_error);
395
970
396
970
  bset_n_div = isl_basic_set_dim(bset, isl_dim_div);
397
970
  obj_n_div = isl_aff_dim(obj, isl_dim_div);
398
970
  if (
bset_n_div == 0 && 970
obj_n_div == 0965
)
399
965
    return basic_set_opt(bset, max, obj, opt);
400
970
401
5
  bset = isl_basic_set_copy(bset);
402
5
  obj = isl_aff_copy(obj);
403
5
404
5
  bset_div = extract_divs(bset);
405
5
  exp1 = isl_alloc_array(ctx, int, bset_n_div);
406
5
  exp2 = isl_alloc_array(ctx, int, obj_n_div);
407
5
  if (
!bset_div || 5
(bset_n_div && 5
!exp15
) ||
(obj_n_div && 5
!exp25
))
408
0
    goto error;
409
5
410
5
  div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2);
411
5
412
5
  bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1);
413
5
  obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2);
414
5
415
5
  res = basic_set_opt(bset, max, obj, opt);
416
5
417
5
  isl_mat_free(bset_div);
418
5
  isl_mat_free(div);
419
5
  free(exp1);
420
5
  free(exp2);
421
5
  isl_basic_set_free(bset);
422
5
  isl_aff_free(obj);
423
5
424
5
  return res;
425
0
error:
426
0
  isl_mat_free(div);
427
0
  isl_mat_free(bset_div);
428
0
  free(exp1);
429
0
  free(exp2);
430
0
  isl_basic_set_free(bset);
431
0
  isl_aff_free(obj);
432
0
  return isl_lp_error;
433
5
}
434
435
/* Compute the minimum (maximum if max is set) of the integer affine
436
 * expression obj over the points in set and put the result in *opt.
437
 *
438
 * The parameters are assumed to have been aligned.
439
 */
440
static enum isl_lp_result isl_set_opt_aligned(__isl_keep isl_set *set, int max,
441
  __isl_keep isl_aff *obj, isl_int *opt)
442
963
{
443
963
  int i;
444
963
  enum isl_lp_result res;
445
963
  int empty = 1;
446
963
  isl_int opt_i;
447
963
448
963
  if (
!set || 963
!obj963
)
449
0
    return isl_lp_error;
450
963
  
if (963
set->n == 0963
)
451
0
    return isl_lp_empty;
452
963
453
963
  res = isl_basic_set_opt(set->p[0], max, obj, opt);
454
963
  if (
res == isl_lp_error || 963
res == isl_lp_unbounded963
)
455
195
    return res;
456
768
  
if (768
set->n == 1768
)
457
762
    return res;
458
6
  
if (6
res == isl_lp_ok6
)
459
6
    empty = 0;
460
6
461
6
  isl_int_init(opt_i);
462
12
  for (i = 1; 
i < set->n12
;
++i6
)
{6
463
6
    res = isl_basic_set_opt(set->p[i], max, obj, &opt_i);
464
6
    if (
res == isl_lp_error || 6
res == isl_lp_unbounded6
)
{0
465
0
      isl_int_clear(opt_i);
466
0
      return res;
467
0
    }
468
6
    
if (6
res == isl_lp_empty6
)
469
1
      continue;
470
5
    empty = 0;
471
5
    if (
max ? 5
isl_int_gt4
(opt_i, *opt) :
isl_int_lt1
(opt_i, *opt))
472
1
      isl_int_set(*opt, opt_i);
473
5
  }
474
6
  
isl_int_clear6
(opt_i);6
475
6
476
6
  return empty ? 
isl_lp_empty0
:
isl_lp_ok6
;
477
6
}
478
479
/* Compute the minimum (maximum if max is set) of the integer affine
480
 * expression obj over the points in set and put the result in *opt.
481
 */
482
enum isl_lp_result isl_set_opt(__isl_keep isl_set *set, int max,
483
  __isl_keep isl_aff *obj, isl_int *opt)
484
963
{
485
963
  enum isl_lp_result res;
486
963
  isl_bool aligned;
487
963
488
963
  if (
!set || 963
!obj963
)
489
0
    return isl_lp_error;
490
963
491
963
  aligned = isl_set_space_has_equal_params(set, obj->ls->dim);
492
963
  if (aligned < 0)
493
0
    return isl_lp_error;
494
963
  
if (963
aligned963
)
495
963
    return isl_set_opt_aligned(set, max, obj, opt);
496
963
497
0
  set = isl_set_copy(set);
498
0
  obj = isl_aff_copy(obj);
499
0
  set = isl_set_align_params(set, isl_aff_get_domain_space(obj));
500
0
  obj = isl_aff_align_params(obj, isl_set_get_space(set));
501
0
502
0
  res = isl_set_opt_aligned(set, max, obj, opt);
503
0
504
0
  isl_set_free(set);
505
0
  isl_aff_free(obj);
506
0
507
0
  return res;
508
963
}
509
510
enum isl_lp_result isl_basic_set_max(__isl_keep isl_basic_set *bset,
511
  __isl_keep isl_aff *obj, isl_int *opt)
512
0
{
513
0
  return isl_basic_set_opt(bset, 1, obj, opt);
514
0
}
515
516
enum isl_lp_result isl_set_max(__isl_keep isl_set *set,
517
  __isl_keep isl_aff *obj, isl_int *opt)
518
0
{
519
0
  return isl_set_opt(set, 1, obj, opt);
520
0
}
521
522
enum isl_lp_result isl_set_min(__isl_keep isl_set *set,
523
  __isl_keep isl_aff *obj, isl_int *opt)
524
0
{
525
0
  return isl_set_opt(set, 0, obj, opt);
526
0
}
527
528
/* Convert the result of a function that returns an isl_lp_result
529
 * to an isl_val.  The numerator of "v" is set to the optimal value
530
 * if lp_res is isl_lp_ok.  "max" is set if a maximum was computed.
531
 *
532
 * Return "v" with denominator set to 1 if lp_res is isl_lp_ok.
533
 * Return NULL on error.
534
 * Return a NaN if lp_res is isl_lp_empty.
535
 * Return infinity or negative infinity if lp_res is isl_lp_unbounded,
536
 * depending on "max".
537
 */
538
static __isl_give isl_val *convert_lp_result(enum isl_lp_result lp_res,
539
  __isl_take isl_val *v, int max)
540
964
{
541
964
  isl_ctx *ctx;
542
964
543
964
  if (
lp_res == isl_lp_ok964
)
{768
544
768
    isl_int_set_si(v->d, 1);
545
768
    return isl_val_normalize(v);
546
768
  }
547
196
  ctx = isl_val_get_ctx(v);
548
196
  isl_val_free(v);
549
196
  if (lp_res == isl_lp_error)
550
0
    return NULL;
551
196
  
if (196
lp_res == isl_lp_empty196
)
552
1
    return isl_val_nan(ctx);
553
195
  
if (195
max195
)
554
195
    return isl_val_infty(ctx);
555
195
  else
556
0
    return isl_val_neginfty(ctx);
557
195
}
558
559
/* Return the minimum (maximum if max is set) of the integer affine
560
 * expression "obj" over the points in "bset".
561
 *
562
 * Return infinity or negative infinity if the optimal value is unbounded and
563
 * NaN if "bset" is empty.
564
 *
565
 * Call isl_basic_set_opt and translate the results.
566
 */
567
__isl_give isl_val *isl_basic_set_opt_val(__isl_keep isl_basic_set *bset,
568
  int max, __isl_keep isl_aff *obj)
569
1
{
570
1
  isl_ctx *ctx;
571
1
  isl_val *res;
572
1
  enum isl_lp_result lp_res;
573
1
574
1
  if (
!bset || 1
!obj1
)
575
0
    return NULL;
576
1
577
1
  ctx = isl_aff_get_ctx(obj);
578
1
  res = isl_val_alloc(ctx);
579
1
  if (!res)
580
0
    return NULL;
581
1
  lp_res = isl_basic_set_opt(bset, max, obj, &res->n);
582
1
  return convert_lp_result(lp_res, res, max);
583
1
}
584
585
/* Return the maximum of the integer affine
586
 * expression "obj" over the points in "bset".
587
 *
588
 * Return infinity or negative infinity if the optimal value is unbounded and
589
 * NaN if "bset" is empty.
590
 */
591
__isl_give isl_val *isl_basic_set_max_val(__isl_keep isl_basic_set *bset,
592
  __isl_keep isl_aff *obj)
593
1
{
594
1
  return isl_basic_set_opt_val(bset, 1, obj);
595
1
}
596
597
/* Return the minimum (maximum if max is set) of the integer affine
598
 * expression "obj" over the points in "set".
599
 *
600
 * Return infinity or negative infinity if the optimal value is unbounded and
601
 * NaN if "set" is empty.
602
 *
603
 * Call isl_set_opt and translate the results.
604
 */
605
__isl_give isl_val *isl_set_opt_val(__isl_keep isl_set *set, int max,
606
  __isl_keep isl_aff *obj)
607
963
{
608
963
  isl_ctx *ctx;
609
963
  isl_val *res;
610
963
  enum isl_lp_result lp_res;
611
963
612
963
  if (
!set || 963
!obj963
)
613
0
    return NULL;
614
963
615
963
  ctx = isl_aff_get_ctx(obj);
616
963
  res = isl_val_alloc(ctx);
617
963
  if (!res)
618
0
    return NULL;
619
963
  lp_res = isl_set_opt(set, max, obj, &res->n);
620
963
  return convert_lp_result(lp_res, res, max);
621
963
}
622
623
/* Return the minimum of the integer affine
624
 * expression "obj" over the points in "set".
625
 *
626
 * Return infinity or negative infinity if the optimal value is unbounded and
627
 * NaN if "set" is empty.
628
 */
629
__isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set,
630
  __isl_keep isl_aff *obj)
631
2
{
632
2
  return isl_set_opt_val(set, 0, obj);
633
2
}
634
635
/* Return the maximum of the integer affine
636
 * expression "obj" over the points in "set".
637
 *
638
 * Return infinity or negative infinity if the optimal value is unbounded and
639
 * NaN if "set" is empty.
640
 */
641
__isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set,
642
  __isl_keep isl_aff *obj)
643
961
{
644
961
  return isl_set_opt_val(set, 1, obj);
645
961
}
646
647
/* Return the optimum (min or max depending on "max") of "v1" and "v2",
648
 * where either may be NaN, signifying an uninitialized value.
649
 * That is, if either is NaN, then return the other one.
650
 */
651
static __isl_give isl_val *val_opt(__isl_take isl_val *v1,
652
  __isl_take isl_val *v2, int max)
653
0
{
654
0
  if (
!v1 || 0
!v20
)
655
0
    goto error;
656
0
  
if (0
isl_val_is_nan(v1)0
)
{0
657
0
    isl_val_free(v1);
658
0
    return v2;
659
0
  }
660
0
  
if (0
isl_val_is_nan(v2)0
)
{0
661
0
    isl_val_free(v2);
662
0
    return v1;
663
0
  }
664
0
  
if (0
max0
)
665
0
    return isl_val_max(v1, v2);
666
0
  else
667
0
    return isl_val_min(v1, v2);
668
0
error:
669
0
  isl_val_free(v1);
670
0
  isl_val_free(v2);
671
0
  return NULL;
672
0
}
673
674
/* Internal data structure for isl_set_opt_pw_aff.
675
 *
676
 * "max" is set if the maximum should be computed.
677
 * "set" is the set over which the optimum should be computed.
678
 * "res" contains the current optimum and is initialized to NaN.
679
 */
680
struct isl_set_opt_data {
681
  int max;
682
  isl_set *set;
683
684
  isl_val *res;
685
};
686
687
/* Update the optimum in data->res with respect to the affine function
688
 * "aff" defined over "set".
689
 */
690
static isl_stat piece_opt(__isl_take isl_set *set, __isl_take isl_aff *aff,
691
  void *user)
692
0
{
693
0
  struct isl_set_opt_data *data = user;
694
0
  isl_val *opt;
695
0
696
0
  set = isl_set_intersect(set, isl_set_copy(data->set));
697
0
  opt = isl_set_opt_val(set, data->max, aff);
698
0
  isl_set_free(set);
699
0
  isl_aff_free(aff);
700
0
701
0
  data->res = val_opt(data->res, opt, data->max);
702
0
  if (!data->res)
703
0
    return isl_stat_error;
704
0
705
0
  return isl_stat_ok;
706
0
}
707
708
/* Return the minimum (maximum if "max" is set) of the integer piecewise affine
709
 * expression "obj" over the points in "set".
710
 *
711
 * Return infinity or negative infinity if the optimal value is unbounded and
712
 * NaN if the intersection of "set" with the domain of "obj" is empty.
713
 *
714
 * Initialize the result to NaN and then update it for each of the pieces
715
 * in "obj".
716
 */
717
static __isl_give isl_val *isl_set_opt_pw_aff(__isl_keep isl_set *set, int max,
718
  __isl_keep isl_pw_aff *obj)
719
0
{
720
0
  struct isl_set_opt_data data = { max, set };
721
0
722
0
  data.res = isl_val_nan(isl_set_get_ctx(set));
723
0
  if (isl_pw_aff_foreach_piece(obj, &piece_opt, &data) < 0)
724
0
    return isl_val_free(data.res);
725
0
726
0
  return data.res;
727
0
}
728
729
/* Internal data structure for isl_union_set_opt_union_pw_aff.
730
 *
731
 * "max" is set if the maximum should be computed.
732
 * "obj" is the objective function that needs to be optimized.
733
 * "res" contains the current optimum and is initialized to NaN.
734
 */
735
struct isl_union_set_opt_data {
736
  int max;
737
  isl_union_pw_aff *obj;
738
739
  isl_val *res;
740
};
741
742
/* Update the optimum in data->res with the optimum over "set".
743
 * Do so by first extracting the matching objective function
744
 * from data->obj.
745
 */
746
static isl_stat set_opt(__isl_take isl_set *set, void *user)
747
0
{
748
0
  struct isl_union_set_opt_data *data = user;
749
0
  isl_space *space;
750
0
  isl_pw_aff *pa;
751
0
  isl_val *opt;
752
0
753
0
  space = isl_set_get_space(set);
754
0
  space = isl_space_from_domain(space);
755
0
  space = isl_space_add_dims(space, isl_dim_out, 1);
756
0
  pa = isl_union_pw_aff_extract_pw_aff(data->obj, space);
757
0
  opt = isl_set_opt_pw_aff(set, data->max, pa);
758
0
  isl_pw_aff_free(pa);
759
0
  isl_set_free(set);
760
0
761
0
  data->res = val_opt(data->res, opt, data->max);
762
0
  if (!data->res)
763
0
    return isl_stat_error;
764
0
765
0
  return isl_stat_ok;
766
0
}
767
768
/* Return the minimum (maximum if "max" is set) of the integer piecewise affine
769
 * expression "obj" over the points in "uset".
770
 *
771
 * Return infinity or negative infinity if the optimal value is unbounded and
772
 * NaN if the intersection of "uset" with the domain of "obj" is empty.
773
 *
774
 * Initialize the result to NaN and then update it for each of the sets
775
 * in "uset".
776
 */
777
static __isl_give isl_val *isl_union_set_opt_union_pw_aff(
778
  __isl_keep isl_union_set *uset, int max,
779
  __isl_keep isl_union_pw_aff *obj)
780
0
{
781
0
  struct isl_union_set_opt_data data = { max, obj };
782
0
783
0
  data.res = isl_val_nan(isl_union_set_get_ctx(uset));
784
0
  if (isl_union_set_foreach_set(uset, &set_opt, &data) < 0)
785
0
    return isl_val_free(data.res);
786
0
787
0
  return data.res;
788
0
}
789
790
/* Return a list of minima (maxima if "max" is set) over the points in "uset"
791
 * for each of the expressions in "obj".
792
 *
793
 * An element in the list is infinity or negative infinity if the optimal
794
 * value of the corresponding expression is unbounded and
795
 * NaN if the intersection of "uset" with the domain of the expression
796
 * is empty.
797
 *
798
 * Iterate over all the expressions in "obj" and collect the results.
799
 */
800
static __isl_give isl_multi_val *isl_union_set_opt_multi_union_pw_aff(
801
  __isl_keep isl_union_set *uset, int max,
802
  __isl_keep isl_multi_union_pw_aff *obj)
803
0
{
804
0
  int i, n;
805
0
  isl_multi_val *mv;
806
0
807
0
  if (
!uset || 0
!obj0
)
808
0
    return NULL;
809
0
810
0
  n = isl_multi_union_pw_aff_dim(obj, isl_dim_set);
811
0
  mv = isl_multi_val_zero(isl_multi_union_pw_aff_get_space(obj));
812
0
813
0
  for (i = 0; 
i < n0
;
++i0
)
{0
814
0
    isl_val *v;
815
0
    isl_union_pw_aff *upa;
816
0
817
0
    upa = isl_multi_union_pw_aff_get_union_pw_aff(obj, i);
818
0
    v = isl_union_set_opt_union_pw_aff(uset, max, upa);
819
0
    isl_union_pw_aff_free(upa);
820
0
    mv = isl_multi_val_set_val(mv, i, v);
821
0
  }
822
0
823
0
  return mv;
824
0
}
825
826
/* Return a list of minima over the points in "uset"
827
 * for each of the expressions in "obj".
828
 *
829
 * An element in the list is infinity or negative infinity if the optimal
830
 * value of the corresponding expression is unbounded and
831
 * NaN if the intersection of "uset" with the domain of the expression
832
 * is empty.
833
 */
834
__isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff(
835
  __isl_keep isl_union_set *uset, __isl_keep isl_multi_union_pw_aff *obj)
836
0
{
837
0
  return isl_union_set_opt_multi_union_pw_aff(uset, 0, obj);
838
0
}