bound.cc: drop dead code
[barvinok.git] / bound.cc
blob84620cb908485286ad60c4630be6e489f6b80235
1 #include <assert.h>
2 #include <iostream>
3 #include <barvinok/evalue.h>
4 #include <barvinok/options.h>
5 #include <barvinok/util.h>
6 #include <barvinok/barvinok.h>
7 #include "bound_options.h"
8 #include "evalue_convert.h"
9 #include "evalue_read.h"
10 #include "verify.h"
12 using std::cout;
13 using std::cerr;
14 using std::endl;
16 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
18 struct verify_point_bound {
19 struct verify_point_data vpd;
20 isl_pw_qpolynomial *pwqp;
21 isl_pw_qpolynomial_fold *pwf;
22 enum isl_fold type;
25 static int verify_point(__isl_take isl_point *pnt, void *user)
27 int i;
28 unsigned nparam;
29 struct verify_point_bound *vpb = (struct verify_point_bound *) user;
30 isl_int v, n, d, b, t;
31 isl_pw_qpolynomial *pwqp;
32 isl_qpolynomial *bound;
33 isl_qpolynomial *opt;
34 const char *minmax;
35 int sign;
36 int ok;
37 int cst;
38 FILE *out = vpb->vpd.options->print_all ? stdout : stderr;
40 vpb->vpd.n--;
42 if (vpb->type == isl_fold_max) {
43 minmax = "max";
44 sign = 1;
45 } else {
46 minmax = "min";
47 sign = -1;
50 isl_int_init(b);
51 isl_int_init(t);
52 isl_int_init(v);
53 isl_int_init(n);
54 isl_int_init(d);
56 pwqp = isl_pw_qpolynomial_copy(vpb->pwqp);
58 nparam = isl_pw_qpolynomial_dim(pwqp, isl_dim_param);
59 for (i = 0; i < nparam; ++i) {
60 isl_point_get_coordinate(pnt, isl_dim_param, i, &v);
61 pwqp = isl_pw_qpolynomial_fix_dim(pwqp, isl_dim_param, i, v);
64 bound = isl_pw_qpolynomial_fold_eval(isl_pw_qpolynomial_fold_copy(vpb->pwf),
65 isl_point_copy(pnt));
67 if (sign > 0)
68 opt = isl_pw_qpolynomial_max(pwqp);
69 else
70 opt = isl_pw_qpolynomial_min(pwqp);
72 cst = isl_qpolynomial_is_cst(opt, &n, &d);
73 if (cst != 1)
74 goto error;
75 if (sign > 0)
76 isl_int_fdiv_q(v, n, d);
77 else
78 isl_int_cdiv_q(v, n, d);
80 cst = isl_qpolynomial_is_cst(bound, &n, &d);
81 if (cst != 1)
82 goto error;
83 if (sign > 0)
84 isl_int_fdiv_q(b, n, d);
85 else
86 isl_int_cdiv_q(b, n, d);
88 if (sign > 0)
89 ok = value_ge(b, v);
90 else
91 ok = value_le(b, v);
93 if (vpb->vpd.options->print_all || !ok) {
94 fprintf(out, "%s(", minmax);
95 for (i = 0; i < nparam; ++i) {
96 if (i)
97 fprintf(out, ", ");
98 isl_point_get_coordinate(pnt, isl_dim_param, i, &t);
99 isl_int_print(out, t, 0);
101 fprintf(out, ") = ");
102 isl_int_print(out, n, 0);
103 if (!isl_int_is_one(d)) {
104 fprintf(out, "/");
105 isl_int_print(out, d, 0);
106 fprintf(out, " (");
107 isl_int_print(out, b, 0);
108 fprintf(out, ")");
110 fprintf(out, ", %s(EP) = ", minmax);
111 isl_int_print(out, v, 0);
112 if (ok)
113 fprintf(out, ". OK\n");
114 else
115 fprintf(out, ". NOT OK\n");
116 } else if ((vpb->vpd.n % vpb->vpd.s) == 0) {
117 printf("o");
118 fflush(stdout);
121 if (0) {
122 error:
123 ok = 0;
126 isl_qpolynomial_free(bound);
127 isl_qpolynomial_free(opt);
128 isl_point_free(pnt);
130 isl_int_clear(t);
131 isl_int_clear(d);
132 isl_int_clear(n);
133 isl_int_clear(v);
134 isl_int_clear(b);
136 if (!ok)
137 vpb->vpd.error = 1;
139 if (vpb->vpd.options->continue_on_error)
140 ok = 1;
142 return (vpb->vpd.n >= 1 && ok) ? 0 : -1;
145 static int verify(__isl_keep isl_pw_qpolynomial_fold *pwf,
146 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
147 struct verify_options *options)
149 struct verify_point_bound vpb = { { options } };
150 isl_set *context;
151 int r;
153 vpb.pwf = pwf;
154 vpb.type = type;
155 vpb.pwqp = pwqp;
156 context = isl_pw_qpolynomial_fold_domain(
157 isl_pw_qpolynomial_fold_copy(vpb.pwf));
158 context = verify_context_set_bounds(context, options);
160 r = verify_point_data_init(&vpb.vpd, context);
162 if (r == 0)
163 isl_set_foreach_point(context, verify_point, &vpb);
164 if (vpb.vpd.error)
165 r = -1;
167 isl_set_free(context);
168 isl_pw_qpolynomial_free(pwqp);
170 verify_point_data_fini(&vpb.vpd);
172 return r;
175 static __isl_give isl_pw_qpolynomial_fold *iterate(
176 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type)
178 isl_dim *dim = isl_pw_qpolynomial_get_dim(pwqp);
179 isl_set *set;
180 isl_qpolynomial *qp;
181 isl_qpolynomial_fold *fold;
182 unsigned nvar;
184 assert(isl_dim_size(dim, isl_dim_param) == 0);
185 nvar = isl_dim_size(dim, isl_dim_set);
187 if (type == isl_fold_min)
188 qp = isl_pw_qpolynomial_min(pwqp);
189 else
190 qp = isl_pw_qpolynomial_max(pwqp);
192 qp = isl_qpolynomial_drop_dims(qp, isl_dim_set, 0, nvar);
193 fold = isl_qpolynomial_fold_alloc(type, qp);
194 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
195 set = isl_set_universe(dim);
197 return isl_pw_qpolynomial_fold_alloc(type, set, fold);
200 struct bv_split_data {
201 int size;
202 __isl_give isl_pw_qpolynomial *pwqp_less;
203 __isl_give isl_pw_qpolynomial *pwqp_more;
206 static int split_on_size(__isl_take isl_set *set,
207 __isl_take isl_qpolynomial *qp, void *user)
209 struct bv_split_data *data = (struct bv_split_data *)user;
210 int bounded;
211 isl_set *set_np;
212 isl_pw_qpolynomial *pwqp;
213 int nparam;
215 nparam = isl_set_dim(set, isl_dim_param);
216 set_np = isl_set_move_dims(isl_set_copy(set), isl_dim_set, 0,
217 isl_dim_param, 0, nparam);
218 bounded = isl_set_is_bounded(set_np);
219 assert(bounded >= 0);
220 if (bounded) {
221 isl_pw_qpolynomial *pwqp;
222 isl_qpolynomial *cst;
223 isl_int m;
224 int is_cst;
226 pwqp = isl_set_card(set_np);
227 cst = isl_pw_qpolynomial_max(pwqp);
228 isl_int_init(m);
229 is_cst = isl_qpolynomial_is_cst(cst, &m, NULL);
230 isl_qpolynomial_free(cst);
231 assert(is_cst);
232 bounded = isl_int_cmp_si(m, data->size) <= 0;
233 isl_int_clear(m);
234 } else
235 isl_set_free(set_np);
237 pwqp = isl_pw_qpolynomial_alloc(set, qp);
238 if (bounded)
239 data->pwqp_less = isl_pw_qpolynomial_add_disjoint(
240 data->pwqp_less, pwqp);
241 else
242 data->pwqp_more = isl_pw_qpolynomial_add_disjoint(
243 data->pwqp_more, pwqp);
245 return 0;
249 * Split (partition) pwpq into a partition with (sub)domains containing
250 * size integer points or less and a partition with (sub)domains
251 * containing more integer points.
253 static int split_on_domain_size(__isl_take isl_pw_qpolynomial *pwqp,
254 __isl_give isl_pw_qpolynomial **pwqp_less,
255 __isl_give isl_pw_qpolynomial **pwqp_more,
256 int size)
258 isl_dim *dim;
259 struct bv_split_data data = { size };
260 int r;
262 dim = isl_pw_qpolynomial_get_dim(pwqp);
263 data.pwqp_less = isl_pw_qpolynomial_zero(isl_dim_copy(dim));
264 data.pwqp_more = isl_pw_qpolynomial_zero(dim);
265 r = isl_pw_qpolynomial_foreach_piece(pwqp, &split_on_size, &data);
266 *pwqp_less = data.pwqp_less;
267 *pwqp_more = data.pwqp_more;
268 isl_pw_qpolynomial_free(pwqp);
270 return r;
273 static __isl_give isl_pw_qpolynomial_fold *optimize(
274 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
275 struct options *options)
277 isl_pw_qpolynomial_fold *pwf;
279 if (options->iterate > 0) {
280 isl_pw_qpolynomial *pwqp_less, *pwqp_more;
281 isl_pw_qpolynomial_fold *pwf_less, *pwf_more;
282 split_on_domain_size(pwqp, &pwqp_less, &pwqp_more, options->iterate);
283 pwf_less = iterate(pwqp_less, type);
284 pwf_more = isl_pw_qpolynomial_bound(pwqp_more, type, NULL);
285 pwf = isl_pw_qpolynomial_fold_fold(pwf_less, pwf_more);
286 } else if (options->iterate)
287 pwf = iterate(pwqp, type);
288 else
289 pwf = isl_pw_qpolynomial_bound(pwqp, type, NULL);
290 return pwf;
293 static int optimize(__isl_take isl_pw_qpolynomial *pwqp, struct options *options)
295 int print_solution = 1;
296 int result = 0;
297 isl_pw_qpolynomial_fold *pwf;
298 enum isl_fold type = options->lower ? isl_fold_min : isl_fold_max;
300 if (options->verify->verify) {
301 isl_dim *dim = isl_pw_qpolynomial_get_dim(pwqp);
302 unsigned total = isl_dim_total(dim);
303 isl_dim_free(dim);
304 verify_options_set_range(options->verify, total);
305 if (!options->verify->barvinok->verbose)
306 print_solution = 0;
309 pwf = optimize(isl_pw_qpolynomial_copy(pwqp), type, options);
310 assert(pwf);
311 if (print_solution) {
312 isl_ctx *ctx = isl_pw_qpolynomial_get_ctx(pwqp);
313 isl_printer *p = isl_printer_to_file(ctx, stdout);
314 p = isl_printer_print_pw_qpolynomial_fold(p, pwf);
315 p = isl_printer_end_line(p);
316 isl_printer_free(p);
318 if (options->verify->verify) {
319 enum isl_fold type = options->lower ? isl_fold_min : isl_fold_max;
320 result = verify(pwf, pwqp, type, options->verify);
321 } else
322 isl_pw_qpolynomial_free(pwqp);
323 isl_pw_qpolynomial_fold_free(pwf);
325 return result;
328 int main(int argc, char **argv)
330 evalue *EP;
331 const char **all_vars = NULL;
332 unsigned nvar;
333 unsigned nparam;
334 struct options *options = options_new_with_defaults();
335 isl_ctx *ctx;
336 isl_dim *dim;
337 isl_pw_qpolynomial *pwqp;
338 int result = 0;
340 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
341 ctx = isl_ctx_alloc_with_options(options_arg, options);
343 EP = evalue_read_from_file(stdin, options->var_list, &all_vars,
344 &nvar, &nparam, options->verify->barvinok->MaxRays);
345 assert(EP);
347 evalue_convert(EP, options->convert, options->verify->barvinok->verbose,
348 nvar+nparam, all_vars);
350 dim = isl_dim_set_alloc(ctx, nparam, 0);
351 for (int i = 0; i < nparam; ++i)
352 dim = isl_dim_set_name(dim, isl_dim_param, i, all_vars[nvar + i]);
353 dim = isl_dim_insert(dim, isl_dim_param, 0, nvar);
354 pwqp = isl_pw_qpolynomial_from_evalue(dim, EP);
355 pwqp = isl_pw_qpolynomial_move_dims(pwqp, isl_dim_set, 0, isl_dim_param, 0, nvar);
356 evalue_free(EP);
358 if (options->split)
359 pwqp = isl_pw_qpolynomial_split_periods(pwqp, options->split);
361 result = optimize(pwqp, options);
363 Free_ParamNames(all_vars, nvar+nparam);
364 isl_ctx_free(ctx);
365 return result;