bound.c

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