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