Coverage Report

Created: 2017-11-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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
222
{
38
222
  int i, j, k;
39
222
  struct isl_basic_set *unit_box = NULL;
40
222
  unsigned total;
41
222
42
222
  if (!bset)
43
0
    goto error;
44
222
45
222
  if (bset->n_eq != 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
222
51
222
  total = isl_basic_set_total_dim(bset);
52
222
  unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset),
53
222
          0, 0, bset->n_ineq);
54
222
55
988
  for (i = 0; i < bset->n_ineq; 
++i766
) {
56
766
    k = isl_basic_set_alloc_inequality(unit_box);
57
766
    if (k < 0)
58
0
      goto error;
59
766
    isl_seq_cpy(unit_box->ineq[k], bset->ineq[i], 1 + total);
60
6.87k
    for (j = 0; j < total; 
++j6.10k
) {
61
6.10k
      if (isl_int_is_nonneg(unit_box->ineq[k][1 + j]))
62
6.10k
        
continue5.62k
;
63
479
      isl_int_add(unit_box->ineq[k][0],
64
479
        unit_box->ineq[k][0], unit_box->ineq[k][1 + j]);
65
479
    }
66
766
  }
67
222
68
222
  isl_basic_set_free(bset);
69
222
  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
222
}
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
222
{
87
222
  enum isl_lp_result res;
88
222
  struct isl_basic_set *unit_box;
89
222
  struct isl_vec *sol;
90
222
91
222
  unit_box = unit_box_base_points(isl_basic_set_copy(bset));
92
222
93
222
  res = isl_basic_set_solve_lp(unit_box, 0, f, bset->ctx->one,
94
222
          NULL, NULL, &sol);
95
222
  if (res == isl_lp_ok) {
96
5
    isl_basic_set_free(unit_box);
97
5
    return isl_vec_ceil(sol);
98
5
  }
99
217
100
217
  isl_basic_set_free(unit_box);
101
217
102
217
  return isl_basic_set_sample_vec(isl_basic_set_copy(bset));
103
217
}
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
148
{
110
148
  int k;
111
148
  unsigned total;
112
148
113
148
  total = isl_basic_set_total_dim(bset);
114
148
  bset = isl_basic_set_extend_constraints(bset, 0, 2);
115
148
116
148
  k = isl_basic_set_alloc_inequality(bset);
117
148
  if (k < 0)
118
0
    goto error;
119
148
  isl_seq_cpy(bset->ineq[k], f, 1 + total);
120
148
  isl_int_sub(bset->ineq[k][0], bset->ineq[k][0], l);
121
148
122
148
  k = isl_basic_set_alloc_inequality(bset);
123
148
  if (k < 0)
124
0
    goto error;
125
148
  isl_seq_neg(bset->ineq[k], f, 1 + total);
126
148
  isl_int_add(bset->ineq[k][0], bset->ineq[k][0], u);
127
148
128
148
  return bset;
129
0
error:
130
0
  isl_basic_set_free(bset);
131
0
  return NULL;
132
148
}
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
17
{
153
17
  isl_int tmp;
154
17
  int divide = 1;
155
17
156
17
  isl_int_init(tmp);
157
17
158
159
  while (isl_int_le(l, u)) {
159
148
    struct isl_basic_set *slice;
160
148
    struct isl_vec *sample;
161
148
162
148
    if (!divide)
163
148
      
isl_int_set7
(tmp, u);
164
148
    else {
165
141
      isl_int_sub(tmp, u, l);
166
141
      isl_int_fdiv_q_ui(tmp, tmp, 2);
167
141
      isl_int_add(tmp, tmp, l);
168
141
    }
169
148
    slice = add_bounds(isl_basic_set_copy(bset), f, l, tmp);
170
148
    sample = isl_basic_set_sample_vec(slice);
171
148
    if (!sample) {
172
0
      isl_vec_free(sol);
173
0
      sol = NULL;
174
0
      break;
175
0
    }
176
148
    if (sample->size > 0) {
177
134
      isl_vec_free(sol);
178
134
      sol = sample;
179
134
      isl_seq_inner_product(f, sol->el, sol->size, opt);
180
134
      isl_int_sub_ui(u, *opt, 1);
181
134
      divide = 1;
182
134
    } else {
183
14
      isl_vec_free(sample);
184
14
      if (!divide)
185
6
        break;
186
8
      isl_int_add_ui(l, tmp, 1);
187
8
      divide = 0;
188
8
    }
189
148
  }
190
17
191
17
  isl_int_clear(tmp);
192
17
193
17
  return sol;
194
17
}
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
3.57k
{
212
3.57k
  enum isl_lp_result res;
213
3.57k
  isl_int l, u;
214
3.57k
  struct isl_vec *sol;
215
3.57k
216
3.57k
  res = isl_basic_set_solve_lp(bset, 0, f, bset->ctx->one,
217
3.57k
          opt, NULL, &sol);
218
3.57k
  if (res == isl_lp_ok && 
isl_int_is_one3.36k
(sol->el[0])) {
219
3.35k
    if (sol_p)
220
0
      *sol_p = sol;
221
3.35k
    else
222
3.35k
      isl_vec_free(sol);
223
3.35k
    return isl_lp_ok;
224
3.35k
  }
225
223
  isl_vec_free(sol);
226
223
  if (res == isl_lp_error || res == isl_lp_empty)
227
1
    return res;
228
222
229
222
  sol = initial_solution(bset, f);
230
222
  if (!sol)
231
0
    return isl_lp_error;
232
222
  if (sol->size == 0) {
233
0
    isl_vec_free(sol);
234
0
    return isl_lp_empty;
235
0
  }
236
222
  if (res == isl_lp_unbounded) {
237
205
    isl_vec_free(sol);
238
205
    return isl_lp_unbounded;
239
205
  }
240
17
241
17
  isl_int_init(l);
242
17
  isl_int_init(u);
243
17
244
17
  isl_int_set(l, *opt);
245
17
246
17
  isl_seq_inner_product(f, sol->el, sol->size, opt);
247
17
  isl_int_sub_ui(u, *opt, 1);
248
17
249
17
  sol = solve_ilp_search(bset, f, opt, sol, l, u);
250
17
  if (!sol)
251
0
    res = isl_lp_error;
252
17
253
17
  isl_int_clear(l);
254
17
  isl_int_clear(u);
255
17
256
17
  if (sol_p)
257
0
    *sol_p = sol;
258
17
  else
259
17
    isl_vec_free(sol);
260
3.57k
261
3.57k
  return res;
262
3.57k
}
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
3.01k
{
267
3.01k
  unsigned dim;
268
3.01k
  enum isl_lp_result res;
269
3.01k
  struct isl_mat *T = NULL;
270
3.01k
  struct isl_vec *v;
271
3.01k
272
3.01k
  bset = isl_basic_set_copy(bset);
273
3.01k
  dim = isl_basic_set_total_dim(bset);
274
3.01k
  v = isl_vec_alloc(bset->ctx, 1 + dim);
275
3.01k
  if (!v)
276
0
    goto error;
277
3.01k
  isl_seq_cpy(v->el, f, 1 + dim);
278
3.01k
  bset = isl_basic_set_remove_equalities(bset, &T, NULL);
279
3.01k
  v = isl_vec_mat_product(v, isl_mat_copy(T));
280
3.01k
  if (!v)
281
0
    goto error;
282
3.01k
  res = isl_basic_set_solve_ilp(bset, max, v->el, opt, sol_p);
283
3.01k
  isl_vec_free(v);
284
3.01k
  if (res == isl_lp_ok && 
sol_p3.01k
) {
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
3.01k
    isl_mat_free(T);
290
3.01k
  isl_basic_set_free(bset);
291
3.01k
  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
3.01k
}
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
6.59k
{
309
6.59k
  unsigned dim;
310
6.59k
  enum isl_lp_result res;
311
6.59k
312
6.59k
  if (!bset)
313
0
    return isl_lp_error;
314
6.59k
  if (sol_p)
315
0
    *sol_p = NULL;
316
6.59k
317
6.59k
  isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0,
318
6.59k
    return isl_lp_error);
319
6.59k
320
6.59k
  if (isl_basic_set_plain_is_empty(bset))
321
1
    return isl_lp_empty;
322
6.59k
323
6.59k
  if (bset->n_eq)
324
3.01k
    return solve_ilp_with_eq(bset, max, f, opt, sol_p);
325
3.57k
326
3.57k
  dim = isl_basic_set_total_dim(bset);
327
3.57k
328
3.57k
  if (max)
329
3.56k
    isl_seq_neg(f, f, 1 + dim);
330
3.57k
331
3.57k
  res = solve_ilp(bset, f, opt, sol_p);
332
3.57k
333
3.57k
  if (max) {
334
3.56k
    isl_seq_neg(f, f, 1 + dim);
335
3.56k
    isl_int_neg(*opt, *opt);
336
3.56k
  }
337
6.59k
338
6.59k
  return res;
339
6.59k
}
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
3.57k
{
344
3.57k
  enum isl_lp_result res;
345
3.57k
346
3.57k
  if (!obj)
347
0
    return isl_lp_error;
348
3.57k
  bset = isl_basic_set_copy(bset);
349
3.57k
  bset = isl_basic_set_underlying_set(bset);
350
3.57k
  res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL);
351
3.57k
  isl_basic_set_free(bset);
352
3.57k
  return res;
353
3.57k
}
354
355
static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset)
356
80
{
357
80
  int i;
358
80
  isl_ctx *ctx = isl_basic_set_get_ctx(bset);
359
80
  isl_mat *div;
360
80
361
80
  div = isl_mat_alloc(ctx, bset->n_div,
362
80
          1 + 1 + isl_basic_set_total_dim(bset));
363
80
  if (!div)
364
0
    return NULL;
365
80
366
160
  
for (i = 0; 80
i < bset->n_div;
++i80
)
367
80
    isl_seq_cpy(div->row[i], bset->div[i], div->n_col);
368
80
369
80
  return div;
370
80
}
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
3.57k
{
375
3.57k
  int *exp1 = NULL;
376
3.57k
  int *exp2 = NULL;
377
3.57k
  isl_ctx *ctx;
378
3.57k
  isl_mat *bset_div = NULL;
379
3.57k
  isl_mat *div = NULL;
380
3.57k
  enum isl_lp_result res;
381
3.57k
  int bset_n_div, obj_n_div;
382
3.57k
383
3.57k
  if (!bset || !obj)
384
0
    return isl_lp_error;
385
3.57k
386
3.57k
  ctx = isl_aff_get_ctx(obj);
387
3.57k
  if (!isl_space_is_equal(bset->dim, obj->ls->dim))
388
3.57k
    
isl_die0
(ctx, isl_error_invalid,
389
3.57k
      "spaces don't match", return isl_lp_error);
390
3.57k
  if (!isl_int_is_one(obj->v->el[0]))
391
3.57k
    
isl_die0
(ctx, isl_error_unsupported,
392
3.57k
      "expecting integer affine expression",
393
3.57k
      return isl_lp_error);
394
3.57k
395
3.57k
  bset_n_div = isl_basic_set_dim(bset, isl_dim_div);
396
3.57k
  obj_n_div = isl_aff_dim(obj, isl_dim_div);
397
3.57k
  if (bset_n_div == 0 && 
obj_n_div == 03.49k
)
398
3.49k
    return basic_set_opt(bset, max, obj, opt);
399
80
400
80
  bset = isl_basic_set_copy(bset);
401
80
  obj = isl_aff_copy(obj);
402
80
403
80
  bset_div = extract_divs(bset);
404
80
  exp1 = isl_alloc_array(ctx, int, bset_n_div);
405
80
  exp2 = isl_alloc_array(ctx, int, obj_n_div);
406
80
  if (!bset_div || (bset_n_div && !exp1) || (obj_n_div && !exp2))
407
0
    goto error;
408
80
409
80
  div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2);
410
80
411
80
  bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1);
412
80
  obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2);
413
80
414
80
  res = basic_set_opt(bset, max, obj, opt);
415
80
416
80
  isl_mat_free(bset_div);
417
80
  isl_mat_free(div);
418
80
  free(exp1);
419
80
  free(exp2);
420
80
  isl_basic_set_free(bset);
421
80
  isl_aff_free(obj);
422
80
423
80
  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
3.57k
}
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
2.78k
{
442
2.78k
  int i;
443
2.78k
  enum isl_lp_result res;
444
2.78k
  int empty = 1;
445
2.78k
  isl_int opt_i;
446
2.78k
447
2.78k
  if (!set || !obj)
448
0
    return isl_lp_error;
449
2.78k
  if (set->n == 0)
450
0
    return isl_lp_empty;
451
2.78k
452
2.78k
  res = isl_basic_set_opt(set->p[0], max, obj, opt);
453
2.78k
  if (res == isl_lp_error || res == isl_lp_unbounded)
454
205
    return res;
455
2.58k
  if (set->n == 1)
456
1.79k
    return res;
457
786
  if (res == isl_lp_ok)
458
786
    empty = 0;
459
786
460
786
  isl_int_init(opt_i);
461
1.57k
  for (i = 1; i < set->n; 
++i786
) {
462
786
    res = isl_basic_set_opt(set->p[i], max, obj, &opt_i);
463
786
    if (res == isl_lp_error || res == isl_lp_unbounded) {
464
0
      isl_int_clear(opt_i);
465
0
      return res;
466
0
    }
467
786
    if (res == isl_lp_empty)
468
1
      continue;
469
785
    empty = 0;
470
785
    if (max ? 
isl_int_gt784
(opt_i, *opt) :
isl_int_lt1
(opt_i, *opt))
471
785
      
isl_int_set1
(*opt, opt_i);
472
786
  }
473
786
  isl_int_clear(opt_i);
474
786
475
786
  return empty ? 
isl_lp_empty0
: isl_lp_ok;
476
2.78k
}
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
2.78k
{
484
2.78k
  enum isl_lp_result res;
485
2.78k
  isl_bool aligned;
486
2.78k
487
2.78k
  if (!set || !obj)
488
0
    return isl_lp_error;
489
2.78k
490
2.78k
  aligned = isl_set_space_has_equal_params(set, obj->ls->dim);
491
2.78k
  if (aligned < 0)
492
0
    return isl_lp_error;
493
2.78k
  if (aligned)
494
2.78k
    return isl_set_opt_aligned(set, max, obj, opt);
495
0
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
0
}
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
2.78k
{
540
2.78k
  isl_ctx *ctx;
541
2.78k
542
2.78k
  if (lp_res == isl_lp_ok) {
543
2.58k
    isl_int_set_si(v->d, 1);
544
2.58k
    return isl_val_normalize(v);
545
2.58k
  }
546
206
  ctx = isl_val_get_ctx(v);
547
206
  isl_val_free(v);
548
206
  if (lp_res == isl_lp_error)
549
0
    return NULL;
550
206
  if (lp_res == isl_lp_empty)
551
1
    return isl_val_nan(ctx);
552
205
  if (max)
553
205
    return isl_val_infty(ctx);
554
0
  else
555
0
    return isl_val_neginfty(ctx);
556
2.78k
}
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 || !obj)
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
2.78k
{
607
2.78k
  isl_ctx *ctx;
608
2.78k
  isl_val *res;
609
2.78k
  enum isl_lp_result lp_res;
610
2.78k
611
2.78k
  if (!set || !obj)
612
0
    return NULL;
613
2.78k
614
2.78k
  ctx = isl_aff_get_ctx(obj);
615
2.78k
  res = isl_val_alloc(ctx);
616
2.78k
  if (!res)
617
0
    return NULL;
618
2.78k
  lp_res = isl_set_opt(set, max, obj, &res->n);
619
2.78k
  return convert_lp_result(lp_res, res, max);
620
2.78k
}
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
2.78k
{
643
2.78k
  return isl_set_opt_val(set, 1, obj);
644
2.78k
}
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 || !v2)
654
0
    goto error;
655
0
  if (isl_val_is_nan(v1)) {
656
0
    isl_val_free(v1);
657
0
    return v2;
658
0
  }
659
0
  if (isl_val_is_nan(v2)) {
660
0
    isl_val_free(v2);
661
0
    return v1;
662
0
  }
663
0
  if (max)
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 || !obj)
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 < n; ++i) {
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
}