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