bound.c

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