export isl_multi_aff_set_aff
[isl.git] / bound.c
bloba0772b7b98e87a756ad32f200b631f3cc7369885
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>
7 struct bound_options {
8 struct isl_options *isl;
9 unsigned verify;
10 int print_all;
11 int continue_on_error;
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
22 ISL_ARG_DEF(bound_options, struct bound_options, bound_options_args)
24 static __isl_give isl_set *set_bounds(__isl_take isl_set *set)
26 unsigned nparam;
27 int i, r;
28 isl_point *pt, *pt2;
29 isl_set *box;
31 nparam = isl_set_dim(set, isl_dim_param);
32 r = nparam >= 8 ? 5 : nparam >= 5 ? 15 : 50;
34 pt = isl_set_sample_point(isl_set_copy(set));
35 pt2 = isl_point_copy(pt);
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);
42 box = isl_set_box_from_points(pt, pt2);
44 return isl_set_intersect(set, box);
47 struct verify_point_bound {
48 struct bound_options *options;
49 int stride;
50 int n;
51 int exact;
52 int error;
54 isl_pw_qpolynomial_fold *pwf;
55 isl_pw_qpolynomial_fold *bound;
58 static int verify_point(__isl_take isl_point *pnt, void *user)
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;
75 vpb->n--;
77 if (1) {
78 minmax = "ub";
79 sign = 1;
80 } else {
81 minmax = "lb";
82 sign = -1;
85 isl_int_init(t);
87 pwf = isl_pw_qpolynomial_fold_copy(vpb->pwf);
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);
95 bound = isl_pw_qpolynomial_fold_eval(
96 isl_pw_qpolynomial_fold_copy(vpb->bound),
97 isl_point_copy(pnt));
99 dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
100 bounded = isl_set_is_bounded(dom);
102 if (bounded < 0)
103 goto error;
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));
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;
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);
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);
146 if (0) {
147 error:
148 ok = 0;
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);
157 isl_int_clear(t);
159 if (!ok)
160 vpb->error = 1;
162 if (vpb->options->continue_on_error)
163 ok = 1;
165 return (vpb->n >= 1 && ok) ? 0 : -1;
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)
172 struct verify_point_bound vpb;
173 isl_int count, max;
174 isl_set *dom;
175 isl_set *context;
176 int i, r, n;
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);
183 isl_int_init(count);
184 isl_int_init(max);
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);
191 isl_int_clear(max);
192 isl_int_clear(count);
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;
202 if (!options->print_all) {
203 for (i = 0; i < vpb.n; i += vpb.stride)
204 printf(".");
205 printf("\r");
206 fflush(stdout);
209 isl_set_foreach_point(context, verify_point, &vpb);
211 isl_set_free(context);
212 isl_set_free(dom);
213 isl_pw_qpolynomial_fold_free(pwf);
214 isl_pw_qpolynomial_fold_free(bound);
216 if (!options->print_all)
217 printf("\n");
219 if (vpb.error) {
220 fprintf(stderr, "Check failed !\n");
221 return -1;
224 return 0;
227 int main(int argc, char **argv)
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;
238 options = bound_options_new_with_defaults();
239 assert(options);
240 argc = bound_options_parse(options, argc, argv, ISL_ARG_ALL);
242 ctx = isl_ctx_alloc_with_options(&bound_options_args, options);
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);
256 if (options->verify)
257 copy = isl_pw_qpolynomial_fold_copy(pwf);
259 pwf = isl_pw_qpolynomial_fold_bound(pwf, &exact);
260 pwf = isl_pw_qpolynomial_fold_coalesce(pwf);
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);
272 error:
273 isl_stream_free(s);
275 isl_ctx_free(ctx);
277 return r;