bound.c

   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>
   6
   7 struct bound_options {
   8         struct isl_options      *isl;
   9         unsigned                 verify;
  10         int                      print_all;
  11         int                      continue_on_error;
  12 };
  13
  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
  21
  22 ISL_ARG_DEF(bound_options, struct bound_options, bound_options_args)
  23
  24 static __isl_give isl_set *set_bounds(__isl_take isl_set *set)
  25 {
  26         unsigned nparam;
  27         int i, r;
  28         isl_point *pt, *pt2;
  29         isl_set *box;
  30
  31         nparam = isl_set_dim(set, isl_dim_param);
  32         r = nparam >= 8 ? 5 : nparam >= 5 ? 15 : 50;
  33
  34         pt = isl_set_sample_point(isl_set_copy(set));
  35         pt2 = isl_point_copy(pt);
  36
  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);
  40         }
  41
  42         box = isl_set_box_from_points(pt, pt2);
  43
  44         return isl_set_intersect(set, box);
  45 }
  46
  47 struct verify_point_bound {
  48         struct bound_options *options;
  49         int stride;
  50         int n;
  51         int exact;
  52         int error;
  53
  54         isl_pw_qpolynomial_fold *pwf;
  55         isl_pw_qpolynomial_fold *bound;
  56 };
  57
  58 static int verify_point(__isl_take isl_point *pnt, void *user)
  59 {
  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;
  74
  75         vpb->n--;
  76
  77         if (1) {
  78                 minmax = "ub";
  79                 sign = 1;
  80         } else {
  81                 minmax = "lb";
  82                 sign = -1;
  83         }
  84
  85         isl_int_init(t);
  86
  87         pwf = isl_pw_qpolynomial_fold_copy(vpb->pwf);
  88
  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);
  93         }
  94
  95         bound = isl_pw_qpolynomial_fold_eval(
  96                                     isl_pw_qpolynomial_fold_copy(vpb->bound),
  97                                     isl_point_copy(pnt));
  98
  99         dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
 100         bounded = isl_set_is_bounded(dom);
 101
 102         if (bounded < 0)
 103                 goto error;
 104
 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));
 113
 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;
 124
 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);
 132                 }
 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);
 144         }
 145
 146         if (0) {
 147 error:
 148                 ok = 0;
 149         }
 150
 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);
 156
 157         isl_int_clear(t);
 158
 159         if (!ok)
 160                 vpb->error = 1;
 161
 162         if (vpb->options->continue_on_error)
 163                 ok = 1;
 164
 165         return (vpb->n >= 1 && ok) ? 0 : -1;
 166 }
 167
 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)
 171 {
 172         struct verify_point_bound vpb;
 173         isl_int count, max;
 174         isl_set *dom;
 175         isl_set *context;
 176         int i, r, n;
 177
 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);
 182
 183         isl_int_init(count);
 184         isl_int_init(max);
 185
 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);
 190
 191         isl_int_clear(max);
 192         isl_int_clear(count);
 193
 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;
 201
 202         if (!options->print_all) {
 203                 for (i = 0; i < vpb.n; i += vpb.stride)
 204                         printf(".");
 205                 printf("\r");
 206                 fflush(stdout);
 207         }
 208
 209         isl_set_foreach_point(context, verify_point, &vpb);
 210
 211         isl_set_free(context);
 212         isl_set_free(dom);
 213         isl_pw_qpolynomial_fold_free(pwf);
 214         isl_pw_qpolynomial_fold_free(bound);
 215
 216         if (!options->print_all)
 217                 printf("\n");
 218
 219         if (vpb.error) {
 220                 fprintf(stderr, "Check failed !\n");
 221                 return -1;
 222         }
 223
 224         return 0;
 225 }
 226
 227 int main(int argc, char **argv)
 228 {
 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;
 237
 238         options = bound_options_new_with_defaults();
 239         assert(options);
 240         argc = bound_options_parse(options, argc, argv, ISL_ARG_ALL);
 241
 242         ctx = isl_ctx_alloc_with_options(&bound_options_args, options);
 243
 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);
 254         }
 255
 256         if (options->verify)
 257                 copy = isl_pw_qpolynomial_fold_copy(pwf);
 258
 259         pwf = isl_pw_qpolynomial_fold_bound(pwf, &exact);
 260         pwf = isl_pw_qpolynomial_fold_coalesce(pwf);
 261
 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);
 270         }
 271
 272 error:
 273         isl_stream_free(s);
 274
 275         isl_ctx_free(ctx);
 276
 277         return r;
 278 }