iscc.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <isl_obj.h>
   5 #include <isl_stream.h>
   6 #include <isl_obj_list.h>
   7 #include <barvinok/barvinok.h>
   8
   9 #include "config.h"
  10 #ifdef HAVE_GINAC
  11 #include <barvinok/bernstein.h>
  12 #endif
  13
  14 static int isl_bool_false = 0;
  15 static int isl_bool_true = 1;
  16 static int isl_bool_error = -1;
  17
  18 static void *isl_obj_bool_copy(void *v)
  19 {
  20         return v;
  21 }
  22
  23 static void isl_obj_bool_free(void *v)
  24 {
  25 }
  26
  27 static void isl_obj_bool_print(void *v, FILE *out)
  28 {
  29         if (v == &isl_bool_true)
  30                 fprintf(out, "True");
  31         else if (v == &isl_bool_false)
  32                 fprintf(out, "False");
  33         else
  34                 fprintf(out, "Error");
  35 }
  36
  37 static void *isl_obj_bool_add(void *v1, void *v2)
  38 {
  39         return v1;
  40 }
  41
  42 struct isl_obj_vtable isl_obj_bool_vtable = {
  43         isl_obj_bool_copy,
  44         isl_obj_bool_add,
  45         isl_obj_bool_print,
  46         isl_obj_bool_free
  47 };
  48 #define isl_obj_bool            (&isl_obj_bool_vtable)
  49
  50 extern struct isl_obj_vtable isl_obj_list_vtable;
  51 #define isl_obj_list            (&isl_obj_list_vtable)
  52
  53 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
  54 struct isc_bin_op {
  55         enum isl_token_type     op;
  56         isl_obj_type            lhs;
  57         isl_obj_type            rhs;
  58         isl_obj_type            res;
  59         isc_bin_op_fn           fn;
  60 };
  61
  62 struct iscc_at {
  63         isl_pw_qpolynomial *pwqp;
  64         isl_pw_qpolynomial *res;
  65 };
  66
  67 static int eval_at(__isl_take isl_point *pnt, void *user)
  68 {
  69         struct iscc_at *at = (struct iscc_at *) user;
  70         isl_qpolynomial *qp;
  71         isl_set *set;
  72
  73         set = isl_set_from_point(isl_point_copy(pnt));
  74         qp = isl_pw_qpolynomial_eval(isl_pw_qpolynomial_copy(at->pwqp), pnt);
  75
  76         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
  77                         isl_pw_qpolynomial_alloc(set, qp));
  78
  79         return 0;
  80 }
  81
  82 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_at(
  83         __isl_take isl_pw_qpolynomial *pwqp, __isl_take isl_set *set)
  84 {
  85         struct iscc_at at;
  86
  87         at.pwqp = pwqp;
  88         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
  89
  90         isl_set_foreach_point(set, eval_at, &at);
  91
  92         isl_pw_qpolynomial_free(pwqp);
  93         isl_set_free(set);
  94
  95         return at.res;
  96 }
  97
  98 struct iscc_fold_at {
  99         isl_pw_qpolynomial_fold *pwf;
 100         isl_pw_qpolynomial *res;
 101 };
 102
 103 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
 104 {
 105         struct iscc_fold_at *at = (struct iscc_fold_at *) user;
 106         isl_qpolynomial *qp;
 107         isl_set *set;
 108
 109         set = isl_set_from_point(isl_point_copy(pnt));
 110         qp = isl_pw_qpolynomial_fold_eval(isl_pw_qpolynomial_fold_copy(at->pwf),
 111                                                 pnt);
 112
 113         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
 114                         isl_pw_qpolynomial_alloc(set, qp));
 115
 116         return 0;
 117 }
 118
 119 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_fold_at(
 120         __isl_take isl_pw_qpolynomial_fold *pwf, __isl_take isl_set *set)
 121 {
 122         struct iscc_fold_at at;
 123
 124         at.pwf = pwf;
 125         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
 126
 127         isl_set_foreach_point(set, eval_fold_at, &at);
 128
 129         isl_pw_qpolynomial_fold_free(pwf);
 130         isl_set_free(set);
 131
 132         return at.res;
 133 }
 134
 135 struct isc_bin_op bin_ops[] = {
 136         { '+',  isl_obj_set,    isl_obj_set,
 137                 isl_obj_set,
 138                 (isc_bin_op_fn) &isl_set_union },
 139         { '+',  isl_obj_map,    isl_obj_map,
 140                 isl_obj_map,
 141                 (isc_bin_op_fn) &isl_map_union },
 142         { '-',  isl_obj_set,    isl_obj_set,
 143                 isl_obj_set,
 144                 (isc_bin_op_fn) &isl_set_subtract },
 145         { '-',  isl_obj_map,    isl_obj_map,
 146                 isl_obj_map,
 147                 (isc_bin_op_fn) &isl_map_subtract },
 148         { '*',  isl_obj_set,    isl_obj_set,
 149                 isl_obj_set,
 150                 (isc_bin_op_fn) &isl_set_intersect },
 151         { '*',  isl_obj_map,    isl_obj_map,
 152                 isl_obj_map,
 153                 (isc_bin_op_fn) &isl_map_intersect },
 154         { '*',  isl_obj_map,    isl_obj_set,
 155                 isl_obj_map,
 156                 (isc_bin_op_fn) &isl_map_intersect_domain },
 157         { '.',  isl_obj_map,    isl_obj_map,
 158                 isl_obj_map,
 159                 (isc_bin_op_fn) &isl_map_apply_range },
 160         { ISL_TOKEN_TO, isl_obj_set,    isl_obj_set,    isl_obj_map,
 161                 (isc_bin_op_fn) &isl_map_from_domain_and_range },
 162         { '+',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 163                 isl_obj_pw_qpolynomial,
 164                 (isc_bin_op_fn) &isl_pw_qpolynomial_add },
 165         { '-',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 166                 isl_obj_pw_qpolynomial,
 167                 (isc_bin_op_fn) &isl_pw_qpolynomial_sub },
 168         { '*',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 169                 isl_obj_pw_qpolynomial,
 170                 (isc_bin_op_fn) &isl_pw_qpolynomial_mul },
 171         { '*',  isl_obj_pw_qpolynomial, isl_obj_set,
 172                 isl_obj_pw_qpolynomial,
 173                 (isc_bin_op_fn) &isl_pw_qpolynomial_intersect_domain },
 174         { '*',  isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 175                 isl_obj_pw_qpolynomial_fold,
 176                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_intersect_domain },
 177         { '@',  isl_obj_pw_qpolynomial, isl_obj_set,
 178                 isl_obj_pw_qpolynomial,
 179                 (isc_bin_op_fn) &isl_pw_qpolynomial_at },
 180         { '@',  isl_obj_pw_qpolynomial_fold, isl_obj_set,
 181                 isl_obj_pw_qpolynomial,
 182                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_at },
 183         0
 184 };
 185
 186 __isl_give isl_set *set_sample(__isl_take isl_set *set)
 187 {
 188         return isl_set_from_basic_set(isl_set_sample(set));
 189 }
 190
 191 __isl_give isl_map *map_sample(__isl_take isl_map *map)
 192 {
 193         return isl_map_from_basic_map(isl_map_sample(map));
 194 }
 195
 196 static __isl_give isl_set *set_affine_hull(__isl_take isl_set *set)
 197 {
 198         return isl_set_from_basic_set(isl_set_affine_hull(set));
 199 }
 200
 201 static __isl_give isl_map *map_affine_hull(__isl_take isl_map *map)
 202 {
 203         return isl_map_from_basic_map(isl_map_affine_hull(map));
 204 }
 205
 206 typedef void *(*isc_un_op_fn)(void *arg);
 207 struct isc_un_op {
 208         enum isl_token_type     op;
 209         isl_obj_type            arg;
 210         isl_obj_type            res;
 211         isc_un_op_fn            fn;
 212 };
 213 struct isc_named_un_op {
 214         char                    *name;
 215         struct isc_un_op        op;
 216 };
 217 struct isc_named_un_op named_un_ops[] = {
 218         {"aff", { -1,   isl_obj_map,    isl_obj_map,
 219                 (isc_un_op_fn) &map_affine_hull } },
 220         {"aff", { -1,   isl_obj_set,    isl_obj_set,
 221                 (isc_un_op_fn) &set_affine_hull } },
 222         {"card",        { -1,   isl_obj_set,    isl_obj_pw_qpolynomial,
 223                 (isc_un_op_fn) &isl_set_card } },
 224         {"card",        { -1,   isl_obj_map,    isl_obj_pw_qpolynomial,
 225                 (isc_un_op_fn) &isl_map_card } },
 226         {"dom", { -1,   isl_obj_map,    isl_obj_set,
 227                 (isc_un_op_fn) &isl_map_domain } },
 228         {"dom", { -1,   isl_obj_pw_qpolynomial, isl_obj_set,
 229                 (isc_un_op_fn) &isl_pw_qpolynomial_domain } },
 230         {"dom", { -1,   isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 231                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_domain } },
 232         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 233                 (isc_un_op_fn) &isl_map_range } },
 234         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 235                 (isc_un_op_fn) &isl_map_lexmin } },
 236         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 237                 (isc_un_op_fn) &isl_map_lexmax } },
 238         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 239                 (isc_un_op_fn) &isl_set_lexmin } },
 240         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 241                 (isc_un_op_fn) &isl_set_lexmax } },
 242         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 243                 (isc_un_op_fn) &set_sample } },
 244         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 245                 (isc_un_op_fn) &map_sample } },
 246         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 247                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 248 #ifdef HAVE_GINAC
 249         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial_fold,
 250                 (isc_un_op_fn) &isl_pw_qpolynomial_upper_bound } },
 251 #endif
 252         NULL
 253 };
 254
 255 struct isl_named_obj {
 256         char            *name;
 257         struct isl_obj  obj;
 258 };
 259
 260 static void free_obj(struct isl_obj obj)
 261 {
 262         obj.type->free(obj.v);
 263 }
 264
 265 static int same_name(const void *entry, const void *val)
 266 {
 267         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 268
 269         return !strcmp(named->name, val);
 270 }
 271
 272 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 273         char *name, struct isl_obj obj)
 274 {
 275         struct isl_hash_table_entry *entry;
 276         uint32_t name_hash;
 277         struct isl_named_obj *named;
 278
 279         name_hash = isl_hash_string(isl_hash_init(), name);
 280         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 281         if (!entry)
 282                 goto error;
 283         if (entry->data) {
 284                 named = entry->data;
 285                 free_obj(named->obj);
 286                 free(name);
 287         } else {
 288                 named = isl_alloc_type(ctx, struct isl_named_obj);
 289                 if (!named)
 290                         goto error;
 291                 named->name = name;
 292                 entry->data = named;
 293         }
 294         named->obj = obj;
 295
 296         return 0;
 297 error:
 298         free_obj(obj);
 299         free(name);
 300         return -1;
 301 }
 302
 303 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 304         struct isl_hash_table *table, char *name)
 305 {
 306         struct isl_obj obj = { isl_obj_none, NULL };
 307         struct isl_hash_table_entry *entry;
 308         uint32_t name_hash;
 309
 310         name_hash = isl_hash_string(isl_hash_init(), name);
 311         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 312         if (entry) {
 313                 struct isl_named_obj *named;
 314                 named = entry->data;
 315                 obj = named->obj;
 316         }
 317
 318         free(name);
 319         obj.v = obj.type->copy(obj.v);
 320         return obj;
 321 }
 322
 323 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 324         isl_obj_type lhs)
 325 {
 326         int i;
 327         struct isl_token *tok;
 328
 329         tok = isl_stream_next_token(s);
 330         if (!tok)
 331                 return NULL;
 332
 333         for (i = 0; ; ++i) {
 334                 if (!bin_ops[i].op)
 335                         break;
 336                 if (bin_ops[i].op != tok->type)
 337                         continue;
 338                 if (bin_ops[i].lhs != lhs)
 339                         continue;
 340
 341                 isl_token_free(tok);
 342                 return &bin_ops[i];
 343         }
 344
 345         isl_stream_push_token(s, tok);
 346
 347         return NULL;
 348 }
 349
 350 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 351 {
 352         int i;
 353         struct isl_token *tok;
 354
 355         tok = isl_stream_next_token(s);
 356         if (!tok)
 357                 return NULL;
 358
 359         for (i = 0; ; ++i) {
 360                 if (!named_un_ops[i].op.op)
 361                         break;
 362                 if (named_un_ops[i].op.op != tok->type)
 363                         continue;
 364
 365                 isl_token_free(tok);
 366                 return &named_un_ops[i].op;
 367         }
 368
 369         isl_stream_push_token(s, tok);
 370
 371         return NULL;
 372 }
 373
 374 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 375         isl_obj_type arg)
 376 {
 377         int i;
 378
 379         for (i = 0; ; ++i) {
 380                 if (!named_un_ops[i].op.op)
 381                         break;
 382                 if (named_un_ops[i].op.op != like->op)
 383                         continue;
 384                 if (named_un_ops[i].op.arg != arg)
 385                         continue;
 386
 387                 return &named_un_ops[i].op;
 388         }
 389
 390         return NULL;
 391 }
 392
 393 static int is_assign(struct isl_stream *s)
 394 {
 395         struct isl_token *tok;
 396         struct isl_token *tok2;
 397         int assign;
 398
 399         tok = isl_stream_next_token(s);
 400         if (!tok)
 401                 return 0;
 402         if (tok->type != ISL_TOKEN_IDENT) {
 403                 isl_stream_push_token(s, tok);
 404                 return 0;
 405         }
 406
 407         tok2 = isl_stream_next_token(s);
 408         if (!tok2) {
 409                 isl_stream_push_token(s, tok);
 410                 return 0;
 411         }
 412         assign = tok2->type == ISL_TOKEN_DEF;
 413         isl_stream_push_token(s, tok2);
 414         isl_stream_push_token(s, tok);
 415
 416         return assign;
 417 }
 418
 419 static struct isl_obj read_obj(struct isl_stream *s,
 420         struct isl_hash_table *table);
 421 static struct isl_obj read_expr(struct isl_stream *s,
 422         struct isl_hash_table *table);
 423
 424 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 425         struct isl_hash_table *table, struct isc_un_op *op)
 426 {
 427         struct isl_obj obj = { isl_obj_none, NULL };
 428
 429         obj = read_obj(s, table);
 430
 431         op = find_matching_un_op(op, obj.type);
 432
 433         isl_assert(s->ctx, op, goto error);
 434         obj.v = op->fn(obj.v);
 435         obj.type = op->res;
 436
 437         return obj;
 438 error:
 439         free_obj(obj);
 440         obj.type = isl_obj_none;
 441         obj.v = NULL;
 442         return obj;
 443 }
 444
 445 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 446 {
 447         struct isl_list *list;
 448         int exact;
 449
 450         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 451         list = isl_list_alloc(ctx, 2);
 452         if (!list)
 453                 goto error;
 454
 455         list->obj[0].type = isl_obj_map;
 456         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 457         list->obj[1].type = isl_obj_bool;
 458         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 459         obj.v = list;
 460         obj.type = isl_obj_list;
 461         if (exact < 0 || !list->obj[0].v)
 462                 goto error;
 463
 464         return obj;
 465 error:
 466         free_obj(obj);
 467         obj.type = isl_obj_none;
 468         obj.v = NULL;
 469         return obj;
 470 }
 471
 472 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 473 {
 474         struct isl_list *list = obj.v;
 475         struct isl_token *tok;
 476         int i;
 477
 478         tok = isl_stream_next_token(s);
 479         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 480                 isl_stream_error(s, tok, "expecting index");
 481                 if (tok)
 482                         isl_stream_push_token(s, tok);
 483                 goto error;
 484         }
 485         i = isl_int_get_si(tok->u.v);
 486         isl_token_free(tok);
 487         isl_assert(s, i < list->n, goto error);
 488         if (isl_stream_eat(s, ']'))
 489                 goto error;
 490
 491         obj = list->obj[i];
 492         obj.v = obj.type->copy(obj.v);
 493
 494         isl_list_free(list);
 495
 496         return obj;
 497 error:
 498         free_obj(obj);
 499         obj.type = isl_obj_none;
 500         obj.v = NULL;
 501         return obj;
 502 }
 503
 504 static struct isl_obj read_obj(struct isl_stream *s,
 505         struct isl_hash_table *table)
 506 {
 507         struct isl_obj obj = { isl_obj_none, NULL };
 508         char *name = NULL;
 509         struct isc_un_op *op = NULL;
 510
 511         if (isl_stream_eat_if_available(s, '(')) {
 512                 obj = read_expr(s, table);
 513                 if (isl_stream_eat(s, ')'))
 514                         goto error;
 515         } else {
 516                 op = read_prefix_un_op_if_available(s);
 517                 if (op)
 518                         return read_un_op_expr(s, table, op);
 519
 520                 name = isl_stream_read_ident_if_available(s);
 521                 if (name) {
 522                         obj = stored_obj(s->ctx, table, name);
 523                 } else {
 524                         obj = isl_stream_read_obj(s);
 525                         assert(obj.v);
 526                 }
 527         }
 528
 529         if (isl_stream_eat_if_available(s, '^')) {
 530                 if (isl_stream_eat(s, '+'))
 531                         goto error;
 532                 obj = transitive_closure(s->ctx, obj);
 533         } else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 534                 obj = obj_at_index(s, obj);
 535
 536         return obj;
 537 error:
 538         free_obj(obj);
 539         obj.type = isl_obj_none;
 540         obj.v = NULL;
 541         return obj;
 542 }
 543
 544 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
 545         isl_obj_type lhs, isl_obj_type rhs)
 546 {
 547         int i;
 548
 549         for (i = 0; ; ++i) {
 550                 if (!bin_ops[i].op)
 551                         break;
 552                 if (bin_ops[i].op != like->op)
 553                         continue;
 554                 if (bin_ops[i].lhs != lhs)
 555                         continue;
 556                 if (bin_ops[i].rhs != rhs)
 557                         continue;
 558
 559                 return &bin_ops[i];
 560         }
 561
 562         return NULL;
 563 }
 564
 565 static struct isl_obj read_expr(struct isl_stream *s,
 566         struct isl_hash_table *table)
 567 {
 568         struct isl_obj obj = { isl_obj_none, NULL };
 569         struct isl_obj right_obj = { isl_obj_none, NULL };
 570
 571         obj = read_obj(s, table);
 572         for (;;) {
 573                 struct isc_bin_op *op = NULL;
 574
 575                 op = read_bin_op_if_available(s, obj.type);
 576                 if (!op)
 577                         break;
 578
 579                 right_obj = read_obj(s, table);
 580
 581                 op = find_matching_bin_op(op, obj.type, right_obj.type);
 582
 583                 isl_assert(s->ctx, op, goto error);
 584                 obj.v = op->fn(obj.v, right_obj.v);
 585                 obj.type = op->res;
 586         }
 587
 588         return obj;
 589 error:
 590         free_obj(right_obj);
 591         free_obj(obj);
 592         obj.type = isl_obj_none;
 593         obj.v = NULL;
 594         return obj;
 595 }
 596
 597 static void read_line(struct isl_stream *s, struct isl_hash_table *table)
 598 {
 599         struct isl_obj obj = { isl_obj_none, NULL };
 600         char *lhs = NULL;
 601         int assign = 0;
 602         struct isc_bin_op *op = NULL;
 603
 604         if (isl_stream_is_empty(s))
 605                 return;
 606
 607         assign = is_assign(s);
 608         if (assign) {
 609                 lhs = isl_stream_read_ident_if_available(s);
 610                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 611                         goto error;
 612         }
 613
 614         obj = read_expr(s, table);
 615         if (obj.type == isl_obj_none || obj.v == NULL)
 616                 goto error;
 617         if (isl_stream_eat(s, ';'))
 618                 goto error;
 619
 620         if (assign) {
 621                 if (do_assign(s->ctx, table, lhs, obj))
 622                         return;
 623         } else {
 624                 obj.type->print(obj.v, stdout);
 625                 printf("\n");
 626                 free_obj(obj);
 627         }
 628
 629         return;
 630 error:
 631         free(lhs);
 632         free_obj(obj);
 633 }
 634
 635 int free_cb(void *entry)
 636 {
 637         struct isl_named_obj *named = entry;
 638
 639         free_obj(named->obj);
 640         free(named->name);
 641         free(named);
 642
 643         return 0;
 644 }
 645
 646 static void register_named_ops(struct isl_stream *s)
 647 {
 648         int i;
 649
 650         for (i = 0; ; ++i) {
 651                 if (!named_un_ops[i].name)
 652                         break;
 653                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
 654                                                         named_un_ops[i].name);
 655                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
 656         }
 657 }
 658
 659 int main(int argc, char **argv)
 660 {
 661         struct isl_ctx *ctx;
 662         struct isl_stream *s;
 663         struct isl_hash_table *table;
 664
 665         ctx = isl_ctx_alloc();
 666         s = isl_stream_new_file(ctx, stdin);
 667         assert(s);
 668         table = isl_hash_table_alloc(ctx, 10);
 669         assert(table);
 670
 671         register_named_ops(s);
 672
 673         while (!feof(stdin)) {
 674                 read_line(s, table);
 675         }
 676
 677         isl_hash_table_foreach(ctx, table, free_cb);
 678         isl_hash_table_free(ctx, table);
 679         isl_stream_free(s);
 680         isl_ctx_free(ctx);
 681
 682         return 0;
 683 }