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