Rename headers from isl_header.h to isl/header.h
[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         int cst;
72         FILE *out = vpb->options->print_all ? stdout : stderr;
73
74         vpb->n--;
75
76         if (1) {
77                 minmax = "ub";
78                 sign = 1;
79         } else {
80                 minmax = "lb";
81                 sign = -1;
82         }
83
84         isl_int_init(t);
85
86         pwf = isl_pw_qpolynomial_fold_copy(vpb->pwf);
87
88         nparam = isl_pw_qpolynomial_fold_dim(pwf, isl_dim_param);
89         for (i = 0; i < nparam; ++i) {
90                 isl_point_get_coordinate(pnt, isl_dim_param, i, &t);
91                 pwf = isl_pw_qpolynomial_fold_fix_dim(pwf, isl_dim_param, i, t);
92         }
93
94         bound = isl_pw_qpolynomial_fold_eval(
95                                     isl_pw_qpolynomial_fold_copy(vpb->bound),
96                                     isl_point_copy(pnt));
97
98         dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
99         bounded = isl_set_is_bounded(dom);
100
101         if (bounded < 0)
102                 goto error;
103
104         if (!bounded)
105                 opt = isl_pw_qpolynomial_fold_eval(
106                                     isl_pw_qpolynomial_fold_copy(pwf),
107                                     isl_set_sample_point(isl_set_copy(dom)));
108         else if (sign > 0)
109                 opt = isl_pw_qpolynomial_fold_max(isl_pw_qpolynomial_fold_copy(pwf));
110         else
111                 opt = isl_pw_qpolynomial_fold_min(isl_pw_qpolynomial_fold_copy(pwf));
112
113         if (vpb->exact && bounded)
114                 ok = isl_qpolynomial_is_equal(opt, bound);
115         else if (sign > 0)
116                 ok = isl_qpolynomial_le_cst(opt, bound);
117         else
118                 ok = isl_qpolynomial_le_cst(bound, opt);
119         if (ok < 0)
120                 goto error;
121
122         if (vpb->options->print_all || !ok) {
123                 fprintf(out, "%s(", minmax);
124                 for (i = 0; i < nparam; ++i) {
125                         if (i)
126                                 fprintf(out, ", ");
127                         isl_point_get_coordinate(pnt, isl_dim_param, i, &t);
128                         isl_int_print(out, t, 0);
129                 }
130                 fprintf(out, ") = ");
131                 isl_qpolynomial_print(bound, out, ISL_FORMAT_ISL);
132                 fprintf(out, ", %s = ", bounded ? "opt" : "sample");
133                 isl_qpolynomial_print(opt, out, ISL_FORMAT_ISL);
134                 if (ok)
135                         fprintf(out, ". OK\n");
136                 else
137                         fprintf(out, ". NOT OK\n");
138         } else if ((vpb->n % vpb->stride) == 0) {
139                 printf("o");
140                 fflush(stdout);
141         }
142
143         if (0) {
144 error:
145                 ok = 0;
146         }
147
148         isl_pw_qpolynomial_fold_free(pwf);
149         isl_qpolynomial_free(bound);
150         isl_qpolynomial_free(opt);
151         isl_point_free(pnt);
152         isl_set_free(dom);
153
154         isl_int_clear(t);
155
156         if (!ok)
157                 vpb->error = 1;
158
159         if (vpb->options->continue_on_error)
160                 ok = 1;
161
162         return (vpb->n >= 1 && ok) ? 0 : -1;
163 }
164
165 static int check_solution(__isl_take isl_pw_qpolynomial_fold *pwf,
166         __isl_take isl_pw_qpolynomial_fold *bound, int exact,
167         struct bound_options *options)
168 {
169         struct verify_point_bound vpb;
170         isl_int count, max;
171         isl_set *dom;
172         isl_set *context;
173         int i, r, n;
174
175         dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
176         context = isl_set_remove_dims(isl_set_copy(dom), isl_dim_set,
177                                         0, isl_set_dim(dom, isl_dim_set));
178         context = isl_set_remove_divs(context);
179         context = set_bounds(context);
180
181         isl_int_init(count);
182         isl_int_init(max);
183
184         isl_int_set_si(max, 200);
185         r = isl_set_count_upto(context, max, &count);
186         assert(r >= 0);
187         n = isl_int_get_si(count);
188
189         isl_int_clear(max);
190         isl_int_clear(count);
191
192         vpb.options = options;
193         vpb.pwf = pwf;
194         vpb.bound = bound;
195         vpb.n = n;
196         vpb.stride = n > 70 ? 1 + (n + 1)/70 : 1;
197         vpb.error = 0;
198         vpb.exact = exact;
199
200         if (!options->print_all) {
201                 for (i = 0; i < vpb.n; i += vpb.stride)
202                         printf(".");
203                 printf("\r");
204                 fflush(stdout);
205         }
206
207         isl_set_foreach_point(context, verify_point, &vpb);
208
209         isl_set_free(context);
210         isl_set_free(dom);
211         isl_pw_qpolynomial_fold_free(pwf);
212         isl_pw_qpolynomial_fold_free(bound);
213
214         if (!options->print_all)
215                 printf("\n");
216
217         if (vpb.error) {
218                 fprintf(stderr, "Check failed !\n");
219                 return -1;
220         }
221
222         return 0;
223 }
224
225 int main(int argc, char **argv)
226 {
227         isl_ctx *ctx;
228         isl_pw_qpolynomial_fold *copy;
229         isl_pw_qpolynomial_fold *pwf;
230         struct isl_stream *s;
231         struct isl_obj obj;
232         struct bound_options *options;
233         int exact;
234         int r = 0;
235
236         options = bound_options_new_with_defaults();
237         assert(options);
238         argc = bound_options_parse(options, argc, argv, ISL_ARG_ALL);
239
240         ctx = isl_ctx_alloc_with_options(bound_options_arg, options);
241
242         s = isl_stream_new_file(ctx, stdin);
243         obj = isl_stream_read_obj(s);
244         if (obj.type == isl_obj_pw_qpolynomial)
245                 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
246                                                                   obj.v);
247         else if (obj.type == isl_obj_pw_qpolynomial_fold)
248                 pwf = obj.v;
249         else {
250                 obj.type->free(obj.v);
251                 isl_die(ctx, isl_error_invalid, "invalid input", goto error);
252         }
253
254         if (options->verify)
255                 copy = isl_pw_qpolynomial_fold_copy(pwf);
256
257         pwf = isl_pw_qpolynomial_fold_bound(pwf, &exact);
258         pwf = isl_pw_qpolynomial_fold_coalesce(pwf);
259
260         if (options->verify) {
261                 r = check_solution(copy, pwf, exact, options);
262         } else {
263                 if (!exact)
264                         printf("# NOT exact\n");
265                 isl_pw_qpolynomial_fold_print(pwf, stdout, 0);
266                 fprintf(stdout, "\n");
267                 isl_pw_qpolynomial_fold_free(pwf);
268         }
269
270 error:
271         isl_stream_free(s);
272
273         isl_ctx_free(ctx);
274
275         return r;
276 }