4 #include <barvinok/options.h>
5 #include <barvinok/bernstein.h>
6 #include <barvinok/util.h>
7 #include <bound_common.h>
10 #include "evalue_read.h"
13 #ifdef HAVE_SYS_TIMES_H
15 #include <sys/times.h>
17 typedef clock_t my_clock_t
;
19 static my_clock_t
time_diff(struct tms
*before
, struct tms
*after
)
21 return after
->tms_utime
- before
->tms_utime
;
26 typedef int my_clock_t
;
29 static void times(struct tms
* time
)
32 static my_clock_t
time_diff(struct tms
*before
, struct tms
*after
)
42 { BV_BOUND_BERNSTEIN
},
46 #define nr_methods (sizeof(methods)/sizeof(*methods))
48 struct argp_option argp_options
[] = {
54 struct verify_options verify
;
58 static error_t
parse_opt(int key
, char *arg
, struct argp_state
*state
)
60 struct options
*options
= (struct options
*) state
->input
;
64 state
->child_inputs
[0] = options
->verify
.barvinok
;
65 state
->child_inputs
[1] = &options
->verify
;
72 return ARGP_ERR_UNKNOWN
;
79 double RE_sum
[nr_methods
];
81 my_clock_t ticks
[nr_methods
];
82 size_t size
[nr_methods
];
85 void result_data_init(struct result_data
*result
)
88 for (i
= 0; i
< nr_methods
; ++i
) {
89 result
->RE_sum
[i
] = 0;
93 isl_int_init(result
->n
);
96 void result_data_clear(struct result_data
*result
)
99 isl_int_clear(result
->n
);
102 void result_data_print(struct result_data
*result
, int n
)
106 fprintf(stderr
, "%d", result
->ticks
[0]/n
);
107 for (i
= 1; i
< nr_methods
; ++i
)
108 fprintf(stderr
, ", %d", result
->ticks
[i
]/n
);
109 fprintf(stderr
, "\n");
111 fprintf(stderr
, "%zd/%d", result
->size
[0], n
);
112 for (i
= 1; i
< nr_methods
; ++i
)
113 fprintf(stderr
, ", %zd/%d", result
->size
[i
], n
);
114 fprintf(stderr
, "\n");
116 fprintf(stderr
, "%g\n", isl_int_get_d(result
->n
));
117 fprintf(stderr
, "%g", result
->RE_sum
[0]/isl_int_get_d(result
->n
));
118 for (i
= 1; i
< nr_methods
; ++i
)
119 fprintf(stderr
, ", %g", result
->RE_sum
[i
]/isl_int_get_d(result
->n
));
120 fprintf(stderr
, "\n");
123 struct verify_point_bound
{
124 struct verify_point_data vpd
;
125 struct result_data
*result
;
126 isl_pw_qpolynomial
*pwqp
;
127 isl_pw_qpolynomial_fold
**pwf
;
130 static int verify_point(__isl_take isl_point
*pnt
, void *user
)
132 struct verify_point_bound
*vpb
= (struct verify_point_bound
*) user
;
133 const struct verify_options
*options
= vpb
->vpd
.options
;
136 isl_int max
, min
, exact
, approx
;
138 isl_qpolynomial
*opt
;
139 isl_pw_qpolynomial
*pwqp
;
147 isl_int_init(approx
);
151 pwqp
= isl_pw_qpolynomial_copy(vpb
->pwqp
);
153 nparam
= isl_pw_qpolynomial_dim(pwqp
, isl_dim_param
);
154 for (i
= 0; i
< nparam
; ++i
) {
155 isl_point_get_coordinate(pnt
, isl_dim_param
, i
, &n
);
156 pwqp
= isl_pw_qpolynomial_fix_dim(pwqp
, isl_dim_param
, i
, n
);
159 opt
= isl_pw_qpolynomial_max(isl_pw_qpolynomial_copy(pwqp
));
160 cst
= isl_qpolynomial_is_cst(opt
, &n
, &d
);
161 isl_qpolynomial_free(opt
);
163 isl_int_fdiv_q(max
, n
, d
);
165 opt
= isl_pw_qpolynomial_min(pwqp
);
166 cst
= isl_qpolynomial_is_cst(opt
, &n
, &d
);
167 isl_qpolynomial_free(opt
);
169 isl_int_cdiv_q(min
, n
, d
);
171 isl_int_sub(exact
, max
, min
);
172 isl_int_add_ui(exact
, exact
, 1);
174 if (options
->print_all
) {
175 fprintf(stderr
, "max: "); isl_int_print(stderr
, max
, 0);
176 fprintf(stderr
, ", min: "); isl_int_print(stderr
, min
, 0);
177 fprintf(stderr
, ", range: "); isl_int_print(stderr
, exact
, 0);
180 for (i
= 0; i
< nr_methods
; ++i
) {
183 opt
= isl_pw_qpolynomial_fold_eval(
184 isl_pw_qpolynomial_fold_copy(vpb
->pwf
[2 * i
]),
185 isl_point_copy(pnt
));
186 cst
= isl_qpolynomial_is_cst(opt
, &n
, &d
);
187 isl_qpolynomial_free(opt
);
189 isl_int_fdiv_q(max
, n
, d
);
191 opt
= isl_pw_qpolynomial_fold_eval(
192 isl_pw_qpolynomial_fold_copy(vpb
->pwf
[2 * i
+ 1]),
193 isl_point_copy(pnt
));
194 cst
= isl_qpolynomial_is_cst(opt
, &n
, &d
);
195 isl_qpolynomial_free(opt
);
197 isl_int_cdiv_q(min
, n
, d
);
199 isl_int_sub(approx
, max
, min
);
200 isl_int_add_ui(approx
, approx
, 1);
201 if (options
->print_all
) {
202 fprintf(stderr
, ", "); isl_int_print(stderr
, approx
, 0);
205 assert(isl_int_ge(approx
, exact
));
206 isl_int_sub(approx
, approx
, exact
);
208 error
= fabs(isl_int_get_d(approx
)) / isl_int_get_d(exact
);
209 if (options
->print_all
)
210 fprintf(stderr
, " (%g)", error
);
211 vpb
->result
->RE_sum
[i
] += error
;
214 if (options
->print_all
) {
215 fprintf(stderr
, "\n");
216 } else if ((vpb
->vpd
.n
% vpb
->vpd
.s
) == 0) {
223 isl_int_clear(exact
);
224 isl_int_clear(approx
);
233 static void test(evalue
*EP
, unsigned nvar
,
234 __isl_keep isl_pw_qpolynomial_fold
**pwf
, struct result_data
*result
,
235 struct verify_options
*options
)
237 struct verify_point_bound vpb
= { { options
}, result
};
246 ctx
= isl_pw_qpolynomial_fold_get_ctx(pwf
[0]);
247 nparam
= isl_pw_qpolynomial_fold_dim(pwf
[0], isl_dim_param
);
248 dim
= isl_dim_set_alloc(ctx
, nvar
+ nparam
, 0);
249 vpb
.pwqp
= isl_pw_qpolynomial_from_evalue(dim
, EP
);
250 vpb
.pwqp
= isl_pw_qpolynomial_move(vpb
.pwqp
, isl_dim_set
, 0,
251 isl_dim_param
, 0, nvar
);
252 context
= isl_pw_qpolynomial_domain(isl_pw_qpolynomial_copy(vpb
.pwqp
));
253 context
= isl_set_remove(context
, isl_dim_set
, 0, nvar
);
254 context
= verify_context_set_bounds(context
, options
);
256 r
= verify_point_data_init(&vpb
.vpd
, context
);
258 isl_int_set_si(result
->n
, vpb
.vpd
.n
);
260 isl_set_foreach_point(context
, verify_point
, &vpb
);
261 assert(!vpb
.vpd
.error
);
263 isl_set_free(context
);
264 isl_pw_qpolynomial_free(vpb
.pwqp
);
266 verify_point_data_fini(&vpb
.vpd
);
269 void handle(FILE *in
, struct result_data
*result
, struct verify_options
*options
)
272 evalue
*EP
, *upper
, *lower
;
273 const char **all_vars
= NULL
;
276 isl_ctx
*ctx
= isl_ctx_alloc();
278 isl_pw_qpolynomial_fold
*pwf
[2*nr_methods
];
280 EP
= evalue_read_from_file(in
, NULL
, &all_vars
,
281 &nvar
, &nparam
, options
->barvinok
->MaxRays
);
283 if (EVALUE_IS_ZERO(*EP
)) {
285 Free_ParamNames(all_vars
, nvar
+nparam
);
289 upper
= evalue_dup(EP
);
290 lower
= evalue_dup(EP
);
291 evalue_frac2polynomial(upper
, 1, options
->barvinok
->MaxRays
);
292 evalue_frac2polynomial(lower
, -1, options
->barvinok
->MaxRays
);
294 dim
= isl_dim_set_alloc(ctx
, nparam
, 0);
295 for (i
= 0; i
< nr_methods
; ++i
) {
301 for (j
= 0; j
< 2; ++j
) {
302 evalue
*poly
= j
== 0 ? upper
: lower
;
303 int sign
= j
== 0 ? BV_BERNSTEIN_MAX
: BV_BERNSTEIN_MIN
;
304 enum isl_fold type
= j
== 0 ? isl_fold_max
: isl_fold_min
;
306 isl_pw_qpolynomial
*pwqp
;
307 options
->barvinok
->bernstein_optimize
= sign
;
308 dim_poly
= isl_dim_insert(isl_dim_copy(dim
), isl_dim_param
, 0, nvar
);
309 pwqp
= isl_pw_qpolynomial_from_evalue(dim_poly
, poly
);
310 pwqp
= isl_pw_qpolynomial_move(pwqp
, isl_dim_set
, 0,
311 isl_dim_param
, 0, nvar
);
312 pwf
[2*i
+j
] = isl_pw_qpolynomial_bound(pwqp
, type
, methods
[i
].method
);
315 result
->ticks
[i
] = time_diff(&en_cpu
, &st_cpu
);
316 result
->size
[i
] = isl_pw_qpolynomial_fold_size(pwf
[2*i
]);
317 result
->size
[i
] = isl_pw_qpolynomial_fold_size(pwf
[2*i
+1]);
318 if (options
->barvinok
->verbose
) {
319 isl_printer
*p
= isl_printer_to_file(ctx
, stdout
);
320 for (j
= 0; j
< 2; ++j
) {
321 p
= isl_printer_print_pw_qpolynomial_fold(p
, pwf
[2*i
+j
]);
322 p
= isl_printer_end_line(p
);
328 test(EP
, nvar
, pwf
, result
, options
);
330 for (i
= 0; i
< 2*nr_methods
; ++i
)
331 isl_pw_qpolynomial_fold_free(pwf
[i
]);
335 Free_ParamNames(all_vars
, nvar
+nparam
);
340 int main(int argc
, char **argv
)
342 struct barvinok_options
*bv_options
= barvinok_options_new_with_defaults();
343 char path
[PATH_MAX
+1];
344 struct result_data all_result
;
346 static struct argp_child argp_children
[] = {
347 { &barvinok_argp
, 0, 0, 0 },
348 { &verify_argp
, 0, "verification", BV_GRP_LAST
+1 },
351 static struct argp argp
= { argp_options
, parse_opt
, 0, 0, argp_children
};
352 struct options options
;
354 options
.verify
.barvinok
= bv_options
;
355 set_program_name(argv
[0]);
356 argp_parse(&argp
, argc
, argv
, 0, 0, &options
);
358 if (options
.verify
.M
== INT_MIN
)
359 options
.verify
.M
= 100;
360 if (options
.verify
.m
== INT_MAX
)
361 options
.verify
.m
= -100;
363 result_data_init(&all_result
);
365 while (fgets(path
, sizeof(path
), stdin
)) {
366 struct result_data result
;
371 result_data_init(&result
);
372 fprintf(stderr
, "%s", path
);
373 *strchr(path
, '\n') = '\0';
374 in
= fopen(path
, "r");
376 handle(in
, &result
, &options
.verify
);
380 result_data_print(&result
, 1);
382 isl_int_add(all_result
.n
, all_result
.n
, result
.n
);
383 for (i
= 0; i
< nr_methods
; ++i
) {
384 all_result
.RE_sum
[i
] += result
.RE_sum
[i
];
385 all_result
.ticks
[i
] += result
.ticks
[i
];
386 all_result
.size
[i
] += result
.size
[i
];
389 result_data_clear(&result
);
391 if (!options
.quiet
) {
392 fprintf(stderr
, "average\n");
393 result_data_print(&all_result
, n
);
397 result_data_clear(&all_result
);
399 barvinok_options_free(bv_options
);