Coverage Report

Created: 2017-06-28 17:40

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