Merge branch 'maint'
[platform/upstream/isl.git] / bound.c
1 #include <assert.h>
2 #include <isl/stream.h>
3 #include <isl_polynomial_private.h>
4 #include <isl_scan.h>
5 #include <isl/options.h>
6
7 struct bound_options {
8         struct isl_options      *isl;
9         unsigned                 verify;
10         int                      print_all;
11         int                      continue_on_error;
12 };
13
14 ISL_ARGS_START(struct bound_options, bound_options_args)
15 ISL_ARG_CHILD(struct bound_options, isl, "isl", &isl_options_args,
16         "isl options")
17 ISL_ARG_BOOL(struct bound_options, verify, 'T', "verify", 0, NULL)
18 ISL_ARG_BOOL(struct bound_options, print_all, 'A', "print-all", 0, NULL)
19 ISL_ARG_BOOL(struct bound_options, continue_on_error, '\0', "continue-on-error", 0, NULL)
20 ISL_ARGS_END
21
22 ISL_ARG_DEF(bound_options, struct bound_options, bound_options_args)
23
24 static __isl_give isl_set *set_bounds(__isl_take isl_set *set)
25 {
26         unsigned nparam;
27         int i, r;
28         isl_point *pt, *pt2;
29         isl_set *box;
30
31         nparam = isl_set_dim(set, isl_dim_param);
32         r = nparam >= 8 ? 5 : nparam >= 5 ? 15 : 50;
33
34         pt = isl_set_sample_point(isl_set_copy(set));
35         pt2 = isl_point_copy(pt);
36
37         for (i = 0; i < nparam; ++i) {
38                 pt = isl_point_add_ui(pt, isl_dim_param, i, r);
39                 pt2 = isl_point_sub_ui(pt2, isl_dim_param, i, r);
40         }
41
42         box = isl_set_box_from_points(pt, pt2);
43
44         return isl_set_intersect(set, box);
45 }
46
47 struct verify_point_bound {
48         struct bound_options *options;
49         int stride;
50         int n;
51         int exact;
52         int error;
53
54         isl_pw_qpolynomial_fold *pwf;
55         isl_pw_qpolynomial_fold *bound;
56 };
57
58 static int verify_point(__isl_take isl_point *pnt, void *user)
59 {
60         int i;
61         unsigned nvar;
62         unsigned nparam;
63         struct verify_point_bound *vpb = (struct verify_point_bound *) user;
64         isl_int t;
65         isl_ctx *ctx;
66         isl_pw_qpolynomial_fold *pwf;
67         isl_qpolynomial *bound = NULL;
68         isl_qpolynomial *opt = NULL;
69         isl_set *dom = NULL;
70         isl_printer *p;
71         const char *minmax;
72         int bounded;
73         int sign;
74         int ok;
75         FILE *out = vpb->options->print_all ? stdout : stderr;
76
77         vpb->n--;
78
79         if (1) {
80                 minmax = "ub";
81                 sign = 1;
82         } else {
83                 minmax = "lb";
84                 sign = -1;
85         }
86
87         ctx = isl_point_get_ctx(pnt);
88         p = isl_printer_to_file(ctx, out);
89
90         isl_int_init(t);
91
92         pwf = isl_pw_qpolynomial_fold_copy(vpb->pwf);
93
94         nparam = isl_pw_qpolynomial_fold_dim(pwf, isl_dim_param);
95         for (i = 0; i < nparam; ++i) {
96                 isl_point_get_coordinate(pnt, isl_dim_param, i, &t);
97                 pwf = isl_pw_qpolynomial_fold_fix_dim(pwf, isl_dim_param, i, t);
98         }
99
100         bound = isl_pw_qpolynomial_fold_eval(
101                                     isl_pw_qpolynomial_fold_copy(vpb->bound),
102                                     isl_point_copy(pnt));
103
104         dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
105         bounded = isl_set_is_bounded(dom);
106
107         if (bounded < 0)
108                 goto error;
109
110         if (!bounded)
111                 opt = isl_pw_qpolynomial_fold_eval(
112                                     isl_pw_qpolynomial_fold_copy(pwf),
113                                     isl_set_sample_point(isl_set_copy(dom)));
114         else if (sign > 0)
115                 opt = isl_pw_qpolynomial_fold_max(isl_pw_qpolynomial_fold_copy(pwf));
116         else
117                 opt = isl_pw_qpolynomial_fold_min(isl_pw_qpolynomial_fold_copy(pwf));
118
119         nvar = isl_set_dim(dom, isl_dim_set);
120         opt = isl_qpolynomial_project_domain_on_params(opt);
121         if (vpb->exact && bounded)
122                 ok = isl_qpolynomial_plain_is_equal(opt, bound);
123         else if (sign > 0)
124                 ok = isl_qpolynomial_le_cst(opt, bound);
125         else
126                 ok = isl_qpolynomial_le_cst(bound, opt);
127         if (ok < 0)
128                 goto error;
129
130         if (vpb->options->print_all || !ok) {
131                 p = isl_printer_print_str(p, minmax);
132                 p = isl_printer_print_str(p, "(");
133                 for (i = 0; i < nparam; ++i) {
134                         if (i)
135                                 p = isl_printer_print_str(p, ", ");
136                         isl_point_get_coordinate(pnt, isl_dim_param, i, &t);
137                         p = isl_printer_print_isl_int(p, t);
138                 }
139                 p = isl_printer_print_str(p, ") = ");
140                 p = isl_printer_print_qpolynomial(p, bound);
141                 p = isl_printer_print_str(p, ", ");
142                 p = isl_printer_print_str(p, bounded ? "opt" : "sample");
143                 p = isl_printer_print_str(p, " = ");
144                 p = isl_printer_print_qpolynomial(p, opt);
145                 if (ok)
146                         p = isl_printer_print_str(p, ". OK");
147                 else
148                         p = isl_printer_print_str(p, ". NOT OK");
149                 p = isl_printer_end_line(p);
150         } else if ((vpb->n % vpb->stride) == 0) {
151                 p = isl_printer_print_str(p, "o");
152                 p = isl_printer_flush(p);
153         }
154
155         if (0) {
156 error:
157                 ok = 0;
158         }
159
160         isl_pw_qpolynomial_fold_free(pwf);
161         isl_qpolynomial_free(bound);
162         isl_qpolynomial_free(opt);
163         isl_point_free(pnt);
164         isl_set_free(dom);
165
166         isl_int_clear(t);
167
168         isl_printer_free(p);
169
170         if (!ok)
171                 vpb->error = 1;
172
173         if (vpb->options->continue_on_error)
174                 ok = 1;
175
176         return (vpb->n >= 1 && ok) ? 0 : -1;
177 }
178
179 static int check_solution(__isl_take isl_pw_qpolynomial_fold *pwf,
180         __isl_take isl_pw_qpolynomial_fold *bound, int exact,
181         struct bound_options *options)
182 {
183         struct verify_point_bound vpb;
184         isl_int count, max;
185         isl_set *dom;
186         isl_set *context;
187         int i, r, n;
188
189         dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
190         context = isl_set_params(isl_set_copy(dom));
191         context = isl_set_remove_divs(context);
192         context = set_bounds(context);
193
194         isl_int_init(count);
195         isl_int_init(max);
196
197         isl_int_set_si(max, 200);
198         r = isl_set_count_upto(context, max, &count);
199         assert(r >= 0);
200         n = isl_int_get_si(count);
201
202         isl_int_clear(max);
203         isl_int_clear(count);
204
205         vpb.options = options;
206         vpb.pwf = pwf;
207         vpb.bound = bound;
208         vpb.n = n;
209         vpb.stride = n > 70 ? 1 + (n + 1)/70 : 1;
210         vpb.error = 0;
211         vpb.exact = exact;
212
213         if (!options->print_all) {
214                 for (i = 0; i < vpb.n; i += vpb.stride)
215                         printf(".");
216                 printf("\r");
217                 fflush(stdout);
218         }
219
220         isl_set_foreach_point(context, verify_point, &vpb);
221
222         isl_set_free(context);
223         isl_set_free(dom);
224         isl_pw_qpolynomial_fold_free(pwf);
225         isl_pw_qpolynomial_fold_free(bound);
226
227         if (!options->print_all)
228                 printf("\n");
229
230         if (vpb.error) {
231                 fprintf(stderr, "Check failed !\n");
232                 return -1;
233         }
234
235         return 0;
236 }
237
238 int main(int argc, char **argv)
239 {
240         isl_ctx *ctx;
241         isl_pw_qpolynomial_fold *copy;
242         isl_pw_qpolynomial_fold *pwf;
243         struct isl_stream *s;
244         struct isl_obj obj;
245         struct bound_options *options;
246         int exact;
247         int r = 0;
248
249         options = bound_options_new_with_defaults();
250         assert(options);
251         argc = bound_options_parse(options, argc, argv, ISL_ARG_ALL);
252
253         ctx = isl_ctx_alloc_with_options(&bound_options_args, options);
254
255         s = isl_stream_new_file(ctx, stdin);
256         obj = isl_stream_read_obj(s);
257         if (obj.type == isl_obj_pw_qpolynomial)
258                 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
259                                                                   obj.v);
260         else if (obj.type == isl_obj_pw_qpolynomial_fold)
261                 pwf = obj.v;
262         else {
263                 obj.type->free(obj.v);
264                 isl_die(ctx, isl_error_invalid, "invalid input", goto error);
265         }
266
267         if (options->verify)
268                 copy = isl_pw_qpolynomial_fold_copy(pwf);
269
270         pwf = isl_pw_qpolynomial_fold_bound(pwf, &exact);
271         pwf = isl_pw_qpolynomial_fold_coalesce(pwf);
272
273         if (options->verify) {
274                 r = check_solution(copy, pwf, exact, options);
275         } else {
276                 if (!exact)
277                         printf("# NOT exact\n");
278                 isl_pw_qpolynomial_fold_print(pwf, stdout, 0);
279                 fprintf(stdout, "\n");
280                 isl_pw_qpolynomial_fold_free(pwf);
281         }
282
283 error:
284         isl_stream_free(s);
285
286         isl_ctx_free(ctx);
287
288         return r;
289 }