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