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 <assert.h>
11 #include <string.h>
12 #include <isl_map_private.h>
13 #include <isl/aff.h>
14 #include <isl/set.h>
15 #include "isl_tab.h"
16 #include "isl_sample.h"
17 #include "isl_scan.h"
18 #include <isl_seq.h>
19 #include <isl_ilp_private.h>
20 #include <isl/printer.h>
21 #include <isl_point_private.h>
22 #include <isl_vec_private.h>
23 #include <isl/options.h>
24 #include <isl_config.h>
25
26 /* The input of this program is the same as that of the "example" program
27 * from the PipLib distribution, except that the "big parameter column"
28 * should always be -1.
29 *
30 * Context constraints in PolyLib format
31 * -1
32 * Problem constraints in PolyLib format
33 * Optional list of options
34 *
35 * The options are
36 * Maximize compute maximum instead of minimum
37 * Rational compute rational optimum instead of integer optimum
38 * Urs_parms don't assume parameters are non-negative
39 * Urs_unknowns don't assume unknowns are non-negative
40 */
41
42 struct options {
43 struct isl_options *isl;
44 unsigned verify;
45 unsigned format;
46 };
47
48 #define FORMAT_SET 0
49 #define FORMAT_AFF 1
50
51 struct isl_arg_choice pip_format[] = {
52 {"set", FORMAT_SET},
53 {"affine", FORMAT_AFF},
54 {0}
55 };
56
ISL_ARGS_START(struct options,options_args)57 ISL_ARGS_START(struct options, options_args)
58 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
59 ISL_ARG_BOOL(struct options, verify, 'T', "verify", 0, NULL)
60 ISL_ARG_CHOICE(struct options, format, 0, "format",
61 pip_format, FORMAT_SET, "output format")
62 ISL_ARGS_END
63
64 ISL_ARG_DEF(options, struct options, options_args)
65
66 static __isl_give isl_basic_set *set_bounds(__isl_take isl_basic_set *bset)
67 {
68 isl_size nparam;
69 int i, r;
70 isl_point *pt, *pt2;
71 isl_basic_set *box;
72
73 nparam = isl_basic_set_dim(bset, isl_dim_param);
74 if (nparam < 0)
75 return isl_basic_set_free(bset);
76 r = nparam >= 8 ? 4 : nparam >= 5 ? 6 : 30;
77
78 pt = isl_basic_set_sample_point(isl_basic_set_copy(bset));
79 pt2 = isl_point_copy(pt);
80
81 for (i = 0; i < nparam; ++i) {
82 pt = isl_point_add_ui(pt, isl_dim_param, i, r);
83 pt2 = isl_point_sub_ui(pt2, isl_dim_param, i, r);
84 }
85
86 box = isl_basic_set_box_from_points(pt, pt2);
87
88 return isl_basic_set_intersect(bset, box);
89 }
90
to_parameter_domain(__isl_take isl_basic_set * context)91 static __isl_give isl_basic_set *to_parameter_domain(
92 __isl_take isl_basic_set *context)
93 {
94 isl_size dim;
95
96 dim = isl_basic_set_dim(context, isl_dim_set);
97 if (dim < 0)
98 return isl_basic_set_free(context);
99 context = isl_basic_set_move_dims(context, isl_dim_param, 0,
100 isl_dim_set, 0, dim);
101 context = isl_basic_set_params(context);
102 return context;
103 }
104
105 /* If "context" has more parameters than "bset", then reinterpret
106 * the last dimensions of "bset" as parameters.
107 */
move_parameters(__isl_take isl_basic_set * bset,__isl_keep isl_basic_set * context)108 static __isl_give isl_basic_set *move_parameters(__isl_take isl_basic_set *bset,
109 __isl_keep isl_basic_set *context)
110 {
111 isl_size nparam, nparam_bset, dim;
112
113 nparam = isl_basic_set_dim(context, isl_dim_param);
114 nparam_bset = isl_basic_set_dim(bset, isl_dim_param);
115 if (nparam < 0 | nparam_bset < 0)
116 return isl_basic_set_free(bset);
117 if (nparam == nparam_bset)
118 return bset;
119 dim = isl_basic_set_dim(bset, isl_dim_set);
120 if (dim < 0)
121 return isl_basic_set_free(bset);
122 bset = isl_basic_set_move_dims(bset, isl_dim_param, 0,
123 isl_dim_set, dim - nparam, nparam);
124 return bset;
125 }
126
127 /* Plug in the initial values of "params" for the parameters in "bset" and
128 * return the result. The remaining entries in "params", if any,
129 * correspond to the existentially quantified variables in the description
130 * of the original context and can be ignored.
131 */
plug_in_parameters(__isl_take isl_basic_set * bset,__isl_take isl_vec * params)132 static __isl_give isl_basic_set *plug_in_parameters(
133 __isl_take isl_basic_set *bset, __isl_take isl_vec *params)
134 {
135 int i;
136 isl_size n;
137
138 n = isl_basic_set_dim(bset, isl_dim_param);
139 if (n < 0)
140 bset = isl_basic_set_free(bset);
141 for (i = 0; i < n; ++i)
142 bset = isl_basic_set_fix(bset,
143 isl_dim_param, i, params->el[1 + i]);
144
145 bset = isl_basic_set_remove_dims(bset, isl_dim_param, 0, n);
146
147 isl_vec_free(params);
148
149 return bset;
150 }
151
152 /* Plug in the initial values of "params" for the parameters in "set" and
153 * return the result. The remaining entries in "params", if any,
154 * correspond to the existentially quantified variables in the description
155 * of the original context and can be ignored.
156 */
set_plug_in_parameters(__isl_take isl_set * set,__isl_take isl_vec * params)157 static __isl_give isl_set *set_plug_in_parameters(__isl_take isl_set *set,
158 __isl_take isl_vec *params)
159 {
160 int i;
161 isl_size n;
162
163 n = isl_set_dim(set, isl_dim_param);
164 if (n < 0)
165 set = isl_set_free(set);
166 for (i = 0; i < n; ++i)
167 set = isl_set_fix(set, isl_dim_param, i, params->el[1 + i]);
168
169 set = isl_set_remove_dims(set, isl_dim_param, 0, n);
170
171 isl_vec_free(params);
172
173 return set;
174 }
175
176 /* Compute the lexicographically minimal (or maximal if max is set)
177 * element of bset for the given values of the parameters, by
178 * successively solving an ilp problem in each direction.
179 */
opt_at(__isl_take isl_basic_set * bset,__isl_take isl_vec * params,int max)180 static __isl_give isl_vec *opt_at(__isl_take isl_basic_set *bset,
181 __isl_take isl_vec *params, int max)
182 {
183 isl_size dim;
184 isl_ctx *ctx;
185 struct isl_vec *opt;
186 struct isl_vec *obj;
187 int i;
188
189 dim = isl_basic_set_dim(bset, isl_dim_set);
190 if (dim < 0)
191 goto error;
192
193 bset = plug_in_parameters(bset, params);
194
195 ctx = isl_basic_set_get_ctx(bset);
196 if (isl_basic_set_plain_is_empty(bset)) {
197 opt = isl_vec_alloc(ctx, 0);
198 isl_basic_set_free(bset);
199 return opt;
200 }
201
202 opt = isl_vec_alloc(ctx, 1 + dim);
203 assert(opt);
204
205 obj = isl_vec_alloc(ctx, 1 + dim);
206 assert(obj);
207
208 isl_int_set_si(opt->el[0], 1);
209 isl_int_set_si(obj->el[0], 0);
210
211 for (i = 0; i < dim; ++i) {
212 enum isl_lp_result res;
213
214 isl_seq_clr(obj->el + 1, dim);
215 isl_int_set_si(obj->el[1 + i], 1);
216 res = isl_basic_set_solve_ilp(bset, max, obj->el,
217 &opt->el[1 + i], NULL);
218 if (res == isl_lp_empty)
219 goto empty;
220 assert(res == isl_lp_ok);
221 bset = isl_basic_set_fix(bset, isl_dim_set, i, opt->el[1 + i]);
222 }
223
224 isl_basic_set_free(bset);
225 isl_vec_free(obj);
226
227 return opt;
228 error:
229 isl_basic_set_free(bset);
230 isl_vec_free(params);
231 return NULL;
232 empty:
233 isl_vec_free(opt);
234 opt = isl_vec_alloc(ctx, 0);
235 isl_basic_set_free(bset);
236 isl_vec_free(obj);
237
238 return opt;
239 }
240
241 struct isl_scan_pip {
242 struct isl_scan_callback callback;
243 isl_basic_set *bset;
244 isl_set *sol;
245 isl_set *empty;
246 int stride;
247 int n;
248 int max;
249 };
250
251 /* Check if the "manually" computed optimum of bset at the "sample"
252 * values of the parameters agrees with the solution of pilp problem
253 * represented by the pair (sol, empty).
254 * In particular, if there is no solution for this value of the parameters,
255 * then it should be an element of the parameter domain "empty".
256 * Otherwise, the optimal solution, should be equal to the result of
257 * plugging in the value of the parameters in "sol".
258 */
scan_one(struct isl_scan_callback * callback,__isl_take isl_vec * sample)259 static isl_stat scan_one(struct isl_scan_callback *callback,
260 __isl_take isl_vec *sample)
261 {
262 struct isl_scan_pip *sp = (struct isl_scan_pip *)callback;
263 struct isl_vec *opt;
264
265 sp->n--;
266
267 opt = opt_at(isl_basic_set_copy(sp->bset), isl_vec_copy(sample), sp->max);
268 assert(opt);
269
270 if (opt->size == 0) {
271 isl_point *sample_pnt;
272 sample_pnt = isl_point_alloc(isl_set_get_space(sp->empty), sample);
273 assert(isl_set_contains_point(sp->empty, sample_pnt));
274 isl_point_free(sample_pnt);
275 isl_vec_free(opt);
276 } else {
277 isl_set *sol;
278 isl_set *opt_set;
279 opt_set = isl_set_from_basic_set(isl_basic_set_from_vec(opt));
280 sol = set_plug_in_parameters(isl_set_copy(sp->sol), sample);
281 assert(isl_set_is_equal(opt_set, sol));
282 isl_set_free(sol);
283 isl_set_free(opt_set);
284 }
285
286 if (!(sp->n % sp->stride)) {
287 printf("o");
288 fflush(stdout);
289 }
290
291 return sp->n >= 1 ? isl_stat_ok : isl_stat_error;
292 }
293
check_solution(isl_basic_set * bset,isl_basic_set * context,isl_set * sol,isl_set * empty,int max)294 static void check_solution(isl_basic_set *bset, isl_basic_set *context,
295 isl_set *sol, isl_set *empty, int max)
296 {
297 struct isl_scan_pip sp;
298 isl_int count, count_max;
299 int i, n;
300 int r;
301
302 context = set_bounds(context);
303 context = isl_basic_set_underlying_set(context);
304
305 isl_int_init(count);
306 isl_int_init(count_max);
307
308 isl_int_set_si(count_max, 2000);
309 r = isl_basic_set_count_upto(context, count_max, &count);
310 assert(r >= 0);
311 n = isl_int_get_si(count);
312
313 isl_int_clear(count_max);
314 isl_int_clear(count);
315
316 sp.callback.add = scan_one;
317 sp.bset = bset;
318 sp.sol = sol;
319 sp.empty = empty;
320 sp.n = n;
321 sp.stride = n > 70 ? 1 + (n + 1)/70 : 1;
322 sp.max = max;
323
324 for (i = 0; i < n; i += sp.stride)
325 printf(".");
326 printf("\r");
327 fflush(stdout);
328
329 isl_basic_set_scan(context, &sp.callback);
330
331 printf("\n");
332
333 isl_basic_set_free(bset);
334 }
335
main(int argc,char ** argv)336 int main(int argc, char **argv)
337 {
338 struct isl_ctx *ctx;
339 struct isl_basic_set *context, *bset, *copy, *context_copy;
340 struct isl_set *set = NULL;
341 struct isl_set *empty;
342 isl_pw_multi_aff *pma = NULL;
343 int neg_one;
344 char s[1024];
345 int urs_parms = 0;
346 int urs_unknowns = 0;
347 int max = 0;
348 int rational = 0;
349 int n;
350 struct options *options;
351
352 options = options_new_with_defaults();
353 assert(options);
354 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
355
356 ctx = isl_ctx_alloc_with_options(&options_args, options);
357
358 context = isl_basic_set_read_from_file(ctx, stdin);
359 assert(context);
360 n = fscanf(stdin, "%d", &neg_one);
361 assert(n == 1);
362 assert(neg_one == -1);
363 bset = isl_basic_set_read_from_file(ctx, stdin);
364
365 while (fgets(s, sizeof(s), stdin)) {
366 if (strncasecmp(s, "Maximize", 8) == 0)
367 max = 1;
368 if (strncasecmp(s, "Rational", 8) == 0) {
369 rational = 1;
370 bset = isl_basic_set_set_rational(bset);
371 }
372 if (strncasecmp(s, "Urs_parms", 9) == 0)
373 urs_parms = 1;
374 if (strncasecmp(s, "Urs_unknowns", 12) == 0)
375 urs_unknowns = 1;
376 }
377 if (!urs_parms)
378 context = isl_basic_set_intersect(context,
379 isl_basic_set_positive_orthant(isl_basic_set_get_space(context)));
380 context = to_parameter_domain(context);
381 bset = move_parameters(bset, context);
382 if (!urs_unknowns)
383 bset = isl_basic_set_intersect(bset,
384 isl_basic_set_positive_orthant(isl_basic_set_get_space(bset)));
385
386 if (options->verify) {
387 copy = isl_basic_set_copy(bset);
388 context_copy = isl_basic_set_copy(context);
389 }
390
391 if (options->format == FORMAT_AFF) {
392 if (max)
393 pma = isl_basic_set_partial_lexmax_pw_multi_aff(bset,
394 context, &empty);
395 else
396 pma = isl_basic_set_partial_lexmin_pw_multi_aff(bset,
397 context, &empty);
398 } else {
399 if (max)
400 set = isl_basic_set_partial_lexmax(bset,
401 context, &empty);
402 else
403 set = isl_basic_set_partial_lexmin(bset,
404 context, &empty);
405 }
406
407 if (options->verify) {
408 assert(!rational);
409 if (options->format == FORMAT_AFF)
410 set = isl_set_from_pw_multi_aff(pma);
411 check_solution(copy, context_copy, set, empty, max);
412 isl_set_free(set);
413 } else {
414 isl_printer *p;
415 p = isl_printer_to_file(ctx, stdout);
416 if (options->format == FORMAT_AFF)
417 p = isl_printer_print_pw_multi_aff(p, pma);
418 else
419 p = isl_printer_print_set(p, set);
420 p = isl_printer_end_line(p);
421 p = isl_printer_print_str(p, "no solution: ");
422 p = isl_printer_print_set(p, empty);
423 p = isl_printer_end_line(p);
424 isl_printer_free(p);
425 isl_set_free(set);
426 isl_pw_multi_aff_free(pma);
427 }
428
429 isl_set_free(empty);
430 isl_ctx_free(ctx);
431
432 return 0;
433 }
434