1#include <assert.h>
2#include <isl/stream.h>
3#include <isl_map_private.h>
4#include <isl/polynomial.h>
5#include <isl_scan.h>
6#include <isl/val.h>
7#include <isl/options.h>
8
9struct bound_options {
10 struct isl_options *isl;
11 unsigned verify;
12 int print_all;
13 int continue_on_error;
14};
15
16ISL_ARGS_START(struct bound_options, bound_options_args)
17ISL_ARG_CHILD(struct bound_options, isl, "isl", &isl_options_args,
18 "isl options")
19ISL_ARG_BOOL(struct bound_options, verify, 'T', "verify", 0, NULL)
20ISL_ARG_BOOL(struct bound_options, print_all, 'A', "print-all", 0, NULL)
21ISL_ARG_BOOL(struct bound_options, continue_on_error, '\0', "continue-on-error", 0, NULL)
22ISL_ARGS_END
23
24ISL_ARG_DEF(bound_options, struct bound_options, bound_options_args)
25
26static __isl_give isl_set *set_bounds(__isl_take isl_set *set)
27{
28 isl_size nparam;
29 int i, r;
30 isl_point *pt, *pt2;
31 isl_set *box;
32
33 nparam = isl_set_dim(set, type: isl_dim_param);
34 if (nparam < 0)
35 return isl_set_free(set);
36 r = nparam >= 8 ? 5 : nparam >= 5 ? 15 : 50;
37
38 pt = isl_set_sample_point(set: isl_set_copy(set));
39 pt2 = isl_point_copy(pnt: pt);
40
41 for (i = 0; i < nparam; ++i) {
42 pt = isl_point_add_ui(pnt: pt, type: isl_dim_param, pos: i, val: r);
43 pt2 = isl_point_sub_ui(pnt: pt2, type: isl_dim_param, pos: i, val: r);
44 }
45
46 box = isl_set_box_from_points(pnt1: pt, pnt2: pt2);
47
48 return isl_set_intersect(set1: set, set2: box);
49}
50
51struct verify_point_bound {
52 struct bound_options *options;
53 int stride;
54 int n;
55 int exact;
56 int error;
57
58 isl_pw_qpolynomial_fold *pwf;
59 isl_pw_qpolynomial_fold *bound;
60};
61
62static isl_stat verify_point(__isl_take isl_point *pnt, void *user)
63{
64 int i;
65 isl_size nparam;
66 struct verify_point_bound *vpb = (struct verify_point_bound *) user;
67 isl_val *v;
68 isl_ctx *ctx;
69 isl_pw_qpolynomial_fold *pwf;
70 isl_val *bound = NULL;
71 isl_val *opt = NULL;
72 isl_set *dom = NULL;
73 isl_printer *p;
74 const char *minmax;
75 isl_bool bounded;
76 int sign;
77 int ok;
78 FILE *out = vpb->options->print_all ? stdout : stderr;
79
80 vpb->n--;
81
82 if (1) {
83 minmax = "ub";
84 sign = 1;
85 } else {
86 minmax = "lb";
87 sign = -1;
88 }
89
90 ctx = isl_point_get_ctx(pnt);
91 p = isl_printer_to_file(ctx, file: out);
92
93 pwf = isl_pw_qpolynomial_fold_copy(pwf: vpb->pwf);
94
95 nparam = isl_pw_qpolynomial_fold_dim(pwf, type: isl_dim_param);
96 if (nparam < 0)
97 pwf = isl_pw_qpolynomial_fold_free(pwf);
98 for (i = 0; i < nparam; ++i) {
99 v = isl_point_get_coordinate_val(pnt, type: isl_dim_param, pos: i);
100 pwf = isl_pw_qpolynomial_fold_fix_val(pwf, type: isl_dim_param, n: i, v);
101 }
102
103 bound = isl_pw_qpolynomial_fold_eval(
104 pwf: isl_pw_qpolynomial_fold_copy(pwf: vpb->bound),
105 pnt: isl_point_copy(pnt));
106
107 dom = isl_pw_qpolynomial_fold_domain(pwf: isl_pw_qpolynomial_fold_copy(pwf));
108 bounded = isl_set_is_bounded(set: dom);
109
110 if (bounded < 0)
111 goto error;
112
113 if (!bounded)
114 opt = isl_pw_qpolynomial_fold_eval(
115 pwf: isl_pw_qpolynomial_fold_copy(pwf),
116 pnt: isl_set_sample_point(set: isl_set_copy(set: dom)));
117 else if (sign > 0)
118 opt = isl_pw_qpolynomial_fold_max(pwf: isl_pw_qpolynomial_fold_copy(pwf));
119 else
120 opt = isl_pw_qpolynomial_fold_min(pwf: isl_pw_qpolynomial_fold_copy(pwf));
121
122 if (vpb->exact && bounded)
123 ok = isl_val_eq(v1: opt, v2: bound);
124 else if (sign > 0)
125 ok = isl_val_le(v1: opt, v2: bound);
126 else
127 ok = isl_val_le(v1: bound, v2: opt);
128 if (ok < 0)
129 goto error;
130
131 if (vpb->options->print_all || !ok) {
132 p = isl_printer_print_str(p, s: minmax);
133 p = isl_printer_print_str(p, s: "(");
134 for (i = 0; i < nparam; ++i) {
135 if (i)
136 p = isl_printer_print_str(p, s: ", ");
137 v = isl_point_get_coordinate_val(pnt, type: isl_dim_param, pos: i);
138 p = isl_printer_print_val(p, v);
139 isl_val_free(v);
140 }
141 p = isl_printer_print_str(p, s: ") = ");
142 p = isl_printer_print_val(p, v: bound);
143 p = isl_printer_print_str(p, s: ", ");
144 p = isl_printer_print_str(p, s: bounded ? "opt" : "sample");
145 p = isl_printer_print_str(p, s: " = ");
146 p = isl_printer_print_val(p, v: opt);
147 if (ok)
148 p = isl_printer_print_str(p, s: ". OK");
149 else
150 p = isl_printer_print_str(p, s: ". NOT OK");
151 p = isl_printer_end_line(p);
152 } else if ((vpb->n % vpb->stride) == 0) {
153 p = isl_printer_print_str(p, s: "o");
154 p = isl_printer_flush(p);
155 }
156
157 if (0) {
158error:
159 ok = 0;
160 }
161
162 isl_pw_qpolynomial_fold_free(pwf);
163 isl_val_free(v: bound);
164 isl_val_free(v: opt);
165 isl_point_free(pnt);
166 isl_set_free(set: dom);
167
168 isl_printer_free(printer: 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) ? isl_stat_ok : isl_stat_error;
177}
178
179static 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(pwf: isl_pw_qpolynomial_fold_copy(pwf));
190 context = isl_set_params(set: isl_set_copy(set: dom));
191 context = isl_set_remove_divs(set: 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(set: context, max, count: &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(format: ".");
216 printf(format: "\r");
217 fflush(stdout);
218 }
219
220 isl_set_foreach_point(set: context, fn: verify_point, user: &vpb);
221
222 isl_set_free(set: context);
223 isl_set_free(set: dom);
224 isl_pw_qpolynomial_fold_free(pwf);
225 isl_pw_qpolynomial_fold_free(pwf: bound);
226
227 if (!options->print_all)
228 printf(format: "\n");
229
230 if (vpb.error) {
231 fprintf(stderr, format: "Check failed !\n");
232 return -1;
233 }
234
235 return 0;
236}
237
238int main(int argc, char **argv)
239{
240 isl_ctx *ctx;
241 isl_pw_qpolynomial_fold *copy;
242 isl_pw_qpolynomial_fold *pwf;
243 isl_stream *s;
244 struct isl_obj obj;
245 struct bound_options *options;
246 isl_bool exact;
247 int r = 0;
248
249 options = bound_options_new_with_defaults();
250 assert(options);
251 argc = bound_options_parse(opt: options, argc, argv, ISL_ARG_ALL);
252
253 ctx = isl_ctx_alloc_with_options(args: &bound_options_args, opt: 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(type: isl_fold_max,
259 pwqp: 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, tight: &exact);
271 pwf = isl_pw_qpolynomial_fold_coalesce(pwf);
272
273 if (options->verify) {
274 r = check_solution(pwf: copy, bound: pwf, exact, options);
275 } else {
276 if (!exact)
277 printf(format: "# NOT exact\n");
278 isl_pw_qpolynomial_fold_print(pwf, stdout, output_format: 0);
279 fprintf(stdout, format: "\n");
280 isl_pw_qpolynomial_fold_free(pwf);
281 }
282
283error:
284 isl_stream_free(s);
285
286 isl_ctx_free(ctx);
287
288 return r;
289}
290

source code of polly/lib/External/isl/bound.c