isl_schedule_read.c

   1 #include <string.h>
   2
   3 #include <isl/schedule.h>
   4 #include <isl/stream.h>
   5 #include <isl_schedule_private.h>
   6 #include <isl_schedule_tree.h>
   7
   8 /* An enumeration of the various keys that may appear in a YAML mapping
   9  * of a schedule.
  10  */
  11 enum isl_schedule_key {
  12         isl_schedule_key_error = -1,
  13         isl_schedule_key_child,
  14         isl_schedule_key_coincident,
  15         isl_schedule_key_context,
  16         isl_schedule_key_contraction,
  17         isl_schedule_key_domain,
  18         isl_schedule_key_expansion,
  19         isl_schedule_key_filter,
  20         isl_schedule_key_leaf,
  21         isl_schedule_key_mark,
  22         isl_schedule_key_options,
  23         isl_schedule_key_permutable,
  24         isl_schedule_key_schedule,
  25         isl_schedule_key_sequence,
  26         isl_schedule_key_set
  27 };
  28
  29 /* Extract a mapping key from the token "tok".
  30  * Return isl_schedule_key_error on error, i.e., if "tok" does not
  31  * correspond to any known key.
  32  */
  33 static enum isl_schedule_key extract_key(__isl_keep isl_stream *s,
  34         struct isl_token *tok)
  35 {
  36         int type;
  37         char *name;
  38         enum isl_schedule_key key;
  39         isl_ctx *ctx;
  40
  41         ctx = isl_stream_get_ctx(s);
  42         type = isl_token_get_type(tok);
  43         if (type != ISL_TOKEN_IDENT && type != ISL_TOKEN_STRING) {
  44                 isl_stream_error(s, tok, "expecting key");
  45                 return isl_schedule_key_error;
  46         }
  47         name = isl_token_get_str(ctx, tok);
  48         if (!strcmp(name, "child"))
  49                 key = isl_schedule_key_child;
  50         else if (!strcmp(name, "coincident"))
  51                 key = isl_schedule_key_coincident;
  52         else if (!strcmp(name, "context"))
  53                 key = isl_schedule_key_context;
  54         else if (!strcmp(name, "contraction"))
  55                 key = isl_schedule_key_contraction;
  56         else if (!strcmp(name, "domain"))
  57                 key = isl_schedule_key_domain;
  58         else if (!strcmp(name, "expansion"))
  59                 key = isl_schedule_key_expansion;
  60         else if (!strcmp(name, "filter"))
  61                 key = isl_schedule_key_filter;
  62         else if (!strcmp(name, "leaf"))
  63                 key = isl_schedule_key_leaf;
  64         else if (!strcmp(name, "mark"))
  65                 key = isl_schedule_key_mark;
  66         else if (!strcmp(name, "options"))
  67                 key = isl_schedule_key_options;
  68         else if (!strcmp(name, "schedule"))
  69                 key = isl_schedule_key_schedule;
  70         else if (!strcmp(name, "sequence"))
  71                 key = isl_schedule_key_sequence;
  72         else if (!strcmp(name, "set"))
  73                 key = isl_schedule_key_set;
  74         else if (!strcmp(name, "permutable"))
  75                 key = isl_schedule_key_permutable;
  76         else
  77                 isl_die(ctx, isl_error_invalid, "unknown key",
  78                         key = isl_schedule_key_error);
  79         free(name);
  80         return key;
  81 }
  82
  83 /* Read a key from "s" and return the corresponding enum.
  84  * Return isl_schedule_key_error on error, i.e., if the first token
  85  * on the stream does not correspond to any known key.
  86  */
  87 static enum isl_schedule_key get_key(__isl_keep isl_stream *s)
  88 {
  89         struct isl_token *tok;
  90         enum isl_schedule_key key;
  91
  92         tok = isl_stream_next_token(s);
  93         key = extract_key(s, tok);
  94         isl_token_free(tok);
  95
  96         return key;
  97 }
  98
  99 static __isl_give isl_schedule_tree *isl_stream_read_schedule_tree(
 100         __isl_keep isl_stream *s);
 101
 102 /* Read a subtree with context root node from "s".
 103  */
 104 static __isl_give isl_schedule_tree *read_context(__isl_keep isl_stream *s)
 105 {
 106         isl_set *context = NULL;
 107         isl_schedule_tree *tree;
 108         isl_ctx *ctx;
 109         struct isl_token *tok;
 110         enum isl_schedule_key key;
 111         char *str;
 112         int more;
 113
 114         ctx = isl_stream_get_ctx(s);
 115
 116         key = get_key(s);
 117
 118         if (isl_stream_yaml_next(s) < 0)
 119                 return NULL;
 120
 121         tok = isl_stream_next_token(s);
 122         if (!tok) {
 123                 isl_stream_error(s, NULL, "unexpected EOF");
 124                 return NULL;
 125         }
 126         str = isl_token_get_str(ctx, tok);
 127         context = isl_set_read_from_str(ctx, str);
 128         free(str);
 129         isl_token_free(tok);
 130
 131         more = isl_stream_yaml_next(s);
 132         if (more < 0)
 133                 goto error;
 134         if (!more) {
 135                 tree = isl_schedule_tree_from_context(context);
 136         } else {
 137                 key = get_key(s);
 138                 if (key != isl_schedule_key_child)
 139                         isl_die(ctx, isl_error_invalid, "expecting child",
 140                                 goto error);
 141                 if (isl_stream_yaml_next(s) < 0)
 142                         goto error;
 143                 tree = isl_stream_read_schedule_tree(s);
 144                 tree = isl_schedule_tree_insert_context(tree, context);
 145         }
 146
 147         return tree;
 148 error:
 149         isl_set_free(context);
 150         return NULL;
 151 }
 152
 153 /* Read a subtree with domain root node from "s".
 154  */
 155 static __isl_give isl_schedule_tree *read_domain(__isl_keep isl_stream *s)
 156 {
 157         isl_union_set *domain = NULL;
 158         isl_schedule_tree *tree;
 159         isl_ctx *ctx;
 160         struct isl_token *tok;
 161         enum isl_schedule_key key;
 162         char *str;
 163         int more;
 164
 165         ctx = isl_stream_get_ctx(s);
 166
 167         key = get_key(s);
 168
 169         if (isl_stream_yaml_next(s) < 0)
 170                 return NULL;
 171
 172         tok = isl_stream_next_token(s);
 173         if (!tok) {
 174                 isl_stream_error(s, NULL, "unexpected EOF");
 175                 return NULL;
 176         }
 177         str = isl_token_get_str(ctx, tok);
 178         domain = isl_union_set_read_from_str(ctx, str);
 179         free(str);
 180         isl_token_free(tok);
 181
 182         more = isl_stream_yaml_next(s);
 183         if (more < 0)
 184                 goto error;
 185         if (!more) {
 186                 tree = isl_schedule_tree_from_domain(domain);
 187         } else {
 188                 key = get_key(s);
 189                 if (key != isl_schedule_key_child)
 190                         isl_die(ctx, isl_error_invalid, "expecting child",
 191                                 goto error);
 192                 if (isl_stream_yaml_next(s) < 0)
 193                         goto error;
 194                 tree = isl_stream_read_schedule_tree(s);
 195                 tree = isl_schedule_tree_insert_domain(tree, domain);
 196         }
 197
 198         return tree;
 199 error:
 200         isl_union_set_free(domain);
 201         return NULL;
 202 }
 203
 204 /* Read a subtree with expansion root node from "s".
 205  */
 206 static __isl_give isl_schedule_tree *read_expansion(isl_stream *s)
 207 {
 208         isl_ctx *ctx;
 209         isl_union_pw_multi_aff *contraction = NULL;
 210         isl_union_map *expansion = NULL;
 211         isl_schedule_tree *tree = NULL;
 212         int more;
 213
 214         ctx = isl_stream_get_ctx(s);
 215
 216         do {
 217                 struct isl_token *tok;
 218                 enum isl_schedule_key key;
 219                 char *str;
 220
 221                 key = get_key(s);
 222                 if (isl_stream_yaml_next(s) < 0)
 223                         goto error;
 224
 225                 switch (key) {
 226                 case isl_schedule_key_contraction:
 227                         isl_union_pw_multi_aff_free(contraction);
 228                         tok = isl_stream_next_token(s);
 229                         str = isl_token_get_str(ctx, tok);
 230                         contraction = isl_union_pw_multi_aff_read_from_str(ctx,
 231                                                                         str);
 232                         free(str);
 233                         isl_token_free(tok);
 234                         if (!contraction)
 235                                 goto error;
 236                         break;
 237                 case isl_schedule_key_expansion:
 238                         isl_union_map_free(expansion);
 239                         tok = isl_stream_next_token(s);
 240                         str = isl_token_get_str(ctx, tok);
 241                         expansion = isl_union_map_read_from_str(ctx, str);
 242                         free(str);
 243                         isl_token_free(tok);
 244                         if (!expansion)
 245                                 goto error;
 246                         break;
 247                 case isl_schedule_key_child:
 248                         isl_schedule_tree_free(tree);
 249                         tree = isl_stream_read_schedule_tree(s);
 250                         if (!tree)
 251                                 goto error;
 252                         break;
 253                 default:
 254                         isl_die(ctx, isl_error_invalid, "unexpected key",
 255                                 goto error);
 256                 }
 257         } while ((more = isl_stream_yaml_next(s)) > 0);
 258
 259         if (more < 0)
 260                 goto error;
 261
 262         if (!contraction)
 263                 isl_die(ctx, isl_error_invalid, "missing contraction",
 264                         goto error);
 265         if (!expansion)
 266                 isl_die(ctx, isl_error_invalid, "missing expansion",
 267                         goto error);
 268
 269         if (!tree)
 270                 return isl_schedule_tree_from_expansion(contraction, expansion);
 271         return isl_schedule_tree_insert_expansion(tree, contraction, expansion);
 272 error:
 273         isl_schedule_tree_free(tree);
 274         isl_union_pw_multi_aff_free(contraction);
 275         isl_union_map_free(expansion);
 276         return NULL;
 277 }
 278
 279 /* Read a subtree with filter root node from "s".
 280  */
 281 static __isl_give isl_schedule_tree *read_filter(__isl_keep isl_stream *s)
 282 {
 283         isl_union_set *filter = NULL;
 284         isl_schedule_tree *tree;
 285         isl_ctx *ctx;
 286         struct isl_token *tok;
 287         enum isl_schedule_key key;
 288         char *str;
 289         int more;
 290
 291         ctx = isl_stream_get_ctx(s);
 292
 293         key = get_key(s);
 294
 295         if (isl_stream_yaml_next(s) < 0)
 296                 return NULL;
 297
 298         tok = isl_stream_next_token(s);
 299         if (!tok) {
 300                 isl_stream_error(s, NULL, "unexpected EOF");
 301                 return NULL;
 302         }
 303         str = isl_token_get_str(ctx, tok);
 304         filter = isl_union_set_read_from_str(ctx, str);
 305         free(str);
 306         isl_token_free(tok);
 307
 308         more = isl_stream_yaml_next(s);
 309         if (more < 0)
 310                 goto error;
 311         if (!more) {
 312                 tree = isl_schedule_tree_from_filter(filter);
 313         } else {
 314                 key = get_key(s);
 315                 if (key != isl_schedule_key_child)
 316                         isl_die(ctx, isl_error_invalid, "expecting child",
 317                                 goto error);
 318                 if (isl_stream_yaml_next(s) < 0)
 319                         goto error;
 320                 tree = isl_stream_read_schedule_tree(s);
 321                 tree = isl_schedule_tree_insert_filter(tree, filter);
 322         }
 323
 324         return tree;
 325 error:
 326         isl_union_set_free(filter);
 327         return NULL;
 328 }
 329
 330 /* Read a subtree with mark root node from "s".
 331  */
 332 static __isl_give isl_schedule_tree *read_mark(isl_stream *s)
 333 {
 334         isl_id *mark;
 335         isl_schedule_tree *tree;
 336         isl_ctx *ctx;
 337         struct isl_token *tok;
 338         enum isl_schedule_key key;
 339         char *str;
 340         int more;
 341
 342         ctx = isl_stream_get_ctx(s);
 343
 344         key = get_key(s);
 345
 346         if (isl_stream_yaml_next(s) < 0)
 347                 return NULL;
 348
 349         tok = isl_stream_next_token(s);
 350         if (!tok) {
 351                 isl_stream_error(s, NULL, "unexpected EOF");
 352                 return NULL;
 353         }
 354         str = isl_token_get_str(ctx, tok);
 355         mark = isl_id_alloc(ctx, str, NULL);
 356         free(str);
 357         isl_token_free(tok);
 358
 359         more = isl_stream_yaml_next(s);
 360         if (more < 0)
 361                 goto error;
 362         if (!more) {
 363                 isl_die(ctx, isl_error_invalid, "expecting child",
 364                         goto error);
 365         } else {
 366                 key = get_key(s);
 367                 if (key != isl_schedule_key_child)
 368                         isl_die(ctx, isl_error_invalid, "expecting child",
 369                                 goto error);
 370                 if (isl_stream_yaml_next(s) < 0)
 371                         goto error;
 372                 tree = isl_stream_read_schedule_tree(s);
 373                 tree = isl_schedule_tree_insert_mark(tree, mark);
 374         }
 375
 376         return tree;
 377 error:
 378         isl_id_free(mark);
 379         return NULL;
 380 }
 381
 382 /* Read a sequence of integers from "s" (representing the coincident
 383  * property of a band node).
 384  */
 385 static __isl_give isl_val_list *read_coincident(__isl_keep isl_stream *s)
 386 {
 387         isl_ctx *ctx;
 388         isl_val_list *list;
 389         int more;
 390
 391         ctx = isl_stream_get_ctx(s);
 392
 393         if (isl_stream_yaml_read_start_sequence(s) < 0)
 394                 return NULL;
 395
 396         list = isl_val_list_alloc(ctx, 0);
 397         while  ((more = isl_stream_yaml_next(s)) > 0) {
 398                 isl_val *val;
 399
 400                 val = isl_stream_read_val(s);
 401                 list = isl_val_list_add(list, val);
 402         }
 403
 404         if (more < 0 || isl_stream_yaml_read_end_sequence(s))
 405                 list = isl_val_list_free(list);
 406
 407         return list;
 408 }
 409
 410 /* Set the (initial) coincident properties of "band" according to
 411  * the (initial) elements of "coincident".
 412  */
 413 static __isl_give isl_schedule_band *set_coincident(
 414         __isl_take isl_schedule_band *band, __isl_take isl_val_list *coincident)
 415 {
 416         int i;
 417         int n, m;
 418
 419         n = isl_schedule_band_n_member(band);
 420         m = isl_val_list_n_val(coincident);
 421
 422         for (i = 0; i < n && i < m; ++i) {
 423                 isl_val *v;
 424
 425                 v = isl_val_list_get_val(coincident, i);
 426                 if (!v)
 427                         band = isl_schedule_band_free(band);
 428                 band = isl_schedule_band_member_set_coincident(band, i,
 429                                                         !isl_val_is_zero(v));
 430                 isl_val_free(v);
 431         }
 432         isl_val_list_free(coincident);
 433         return band;
 434 }
 435
 436 /* Read a subtree with band root node from "s".
 437  */
 438 static __isl_give isl_schedule_tree *read_band(isl_stream *s)
 439 {
 440         isl_multi_union_pw_aff *schedule = NULL;
 441         isl_schedule_tree *tree = NULL;
 442         isl_val_list *coincident = NULL;
 443         isl_union_set *options = NULL;
 444         isl_ctx *ctx;
 445         isl_schedule_band *band;
 446         int permutable = 0;
 447         int more;
 448
 449         ctx = isl_stream_get_ctx(s);
 450
 451         do {
 452                 struct isl_token *tok;
 453                 enum isl_schedule_key key;
 454                 char *str;
 455                 isl_val *v;
 456
 457                 key = get_key(s);
 458                 if (isl_stream_yaml_next(s) < 0)
 459                         goto error;
 460
 461                 switch (key) {
 462                 case isl_schedule_key_schedule:
 463                         isl_multi_union_pw_aff_free(schedule);
 464                         tok = isl_stream_next_token(s);
 465                         if (!tok) {
 466                                 isl_stream_error(s, NULL, "unexpected EOF");
 467                                 goto error;
 468                         }
 469                         str = isl_token_get_str(ctx, tok);
 470                         schedule = isl_multi_union_pw_aff_read_from_str(ctx,
 471                                                                         str);
 472                         free(str);
 473                         isl_token_free(tok);
 474                         if (!schedule)
 475                                 goto error;
 476                         break;
 477                 case isl_schedule_key_coincident:
 478                         coincident = read_coincident(s);
 479                         if (!coincident)
 480                                 goto error;
 481                         break;
 482                 case isl_schedule_key_permutable:
 483                         v = isl_stream_read_val(s);
 484                         permutable = !isl_val_is_zero(v);
 485                         isl_val_free(v);
 486                         break;
 487                 case isl_schedule_key_options:
 488                         isl_union_set_free(options);
 489                         tok = isl_stream_next_token(s);
 490                         str = isl_token_get_str(ctx, tok);
 491                         options = isl_union_set_read_from_str(ctx, str);
 492                         free(str);
 493                         isl_token_free(tok);
 494                         if (!options)
 495                                 goto error;
 496                         break;
 497                 case isl_schedule_key_child:
 498                         isl_schedule_tree_free(tree);
 499                         tree = isl_stream_read_schedule_tree(s);
 500                         if (!tree)
 501                                 goto error;
 502                         break;
 503                 default:
 504                         isl_die(ctx, isl_error_invalid, "unexpected key",
 505                                 goto error);
 506                 }
 507         } while ((more = isl_stream_yaml_next(s)) > 0);
 508
 509         if (more < 0)
 510                 goto error;
 511
 512         if (!schedule)
 513                 isl_die(ctx, isl_error_invalid, "missing schedule", goto error);
 514
 515         band = isl_schedule_band_from_multi_union_pw_aff(schedule);
 516         band = isl_schedule_band_set_permutable(band, permutable);
 517         if (coincident)
 518                 band = set_coincident(band, coincident);
 519         if (options)
 520                 band = isl_schedule_band_set_ast_build_options(band, options);
 521         if (tree)
 522                 tree = isl_schedule_tree_insert_band(tree, band);
 523         else
 524                 tree = isl_schedule_tree_from_band(band);
 525
 526         return tree;
 527 error:
 528         isl_val_list_free(coincident);
 529         isl_union_set_free(options);
 530         isl_schedule_tree_free(tree);
 531         isl_multi_union_pw_aff_free(schedule);
 532         return NULL;
 533 }
 534
 535 /* Read a subtree with root node of type "type" from "s".
 536  * The node is represented by a sequence of children.
 537  */
 538 static __isl_give isl_schedule_tree *read_children(isl_stream *s,
 539         enum isl_schedule_node_type type)
 540 {
 541         isl_ctx *ctx;
 542         isl_schedule_tree_list *list;
 543         int more;
 544
 545         ctx = isl_stream_get_ctx(s);
 546
 547         isl_token_free(isl_stream_next_token(s));
 548
 549         if (isl_stream_yaml_next(s) < 0)
 550                 return NULL;
 551
 552         if (isl_stream_yaml_read_start_sequence(s))
 553                 return NULL;
 554
 555         list = isl_schedule_tree_list_alloc(ctx, 0);
 556         while ((more = isl_stream_yaml_next(s)) > 0) {
 557                 isl_schedule_tree *tree;
 558
 559                 tree = isl_stream_read_schedule_tree(s);
 560                 list = isl_schedule_tree_list_add(list, tree);
 561         }
 562
 563         if (more < 0 || isl_stream_yaml_read_end_sequence(s))
 564                 list = isl_schedule_tree_list_free(list);
 565
 566         return isl_schedule_tree_from_children(type, list);
 567 }
 568
 569 /* Read a subtree with sequence root node from "s".
 570  */
 571 static __isl_give isl_schedule_tree *read_sequence(isl_stream *s)
 572 {
 573         return read_children(s, isl_schedule_node_sequence);
 574 }
 575
 576 /* Read a subtree with set root node from "s".
 577  */
 578 static __isl_give isl_schedule_tree *read_set(isl_stream *s)
 579 {
 580         return read_children(s, isl_schedule_node_set);
 581 }
 582
 583 /* Read a schedule (sub)tree from "s".
 584  *
 585  * We first determine the type of the root node based on the first
 586  * mapping key and then hand over to a function tailored to reading
 587  * nodes of this type.
 588  */
 589 static __isl_give isl_schedule_tree *isl_stream_read_schedule_tree(
 590         struct isl_stream *s)
 591 {
 592         enum isl_schedule_key key;
 593         struct isl_token *tok;
 594         isl_schedule_tree *tree = NULL;
 595         int more;
 596
 597         if (isl_stream_yaml_read_start_mapping(s))
 598                 return NULL;
 599         more = isl_stream_yaml_next(s);
 600         if (more < 0)
 601                 return NULL;
 602         if (!more) {
 603                 isl_stream_error(s, NULL, "missing key");
 604                 return NULL;
 605         }
 606
 607         tok = isl_stream_next_token(s);
 608         key = extract_key(s, tok);
 609         isl_stream_push_token(s, tok);
 610         if (key < 0)
 611                 return NULL;
 612         switch (key) {
 613         case isl_schedule_key_context:
 614                 tree = read_context(s);
 615                 break;
 616         case isl_schedule_key_domain:
 617                 tree = read_domain(s);
 618                 break;
 619         case isl_schedule_key_contraction:
 620         case isl_schedule_key_expansion:
 621                 tree = read_expansion(s);
 622                 break;
 623         case isl_schedule_key_filter:
 624                 tree = read_filter(s);
 625                 break;
 626         case isl_schedule_key_leaf:
 627                 isl_token_free(isl_stream_next_token(s));
 628                 tree = isl_schedule_tree_leaf(isl_stream_get_ctx(s));
 629                 break;
 630         case isl_schedule_key_mark:
 631                 tree = read_mark(s);
 632                 break;
 633         case isl_schedule_key_sequence:
 634                 tree = read_sequence(s);
 635                 break;
 636         case isl_schedule_key_set:
 637                 tree = read_set(s);
 638                 break;
 639         case isl_schedule_key_schedule:
 640         case isl_schedule_key_coincident:
 641         case isl_schedule_key_options:
 642         case isl_schedule_key_permutable:
 643                 tree = read_band(s);
 644                 break;
 645         case isl_schedule_key_child:
 646                 isl_die(isl_stream_get_ctx(s), isl_error_unsupported,
 647                         "cannot identity node type", return NULL);
 648         case isl_schedule_key_error:
 649                 return NULL;
 650         }
 651
 652         if (isl_stream_yaml_read_end_mapping(s) < 0) {
 653                 isl_stream_error(s, NULL, "unexpected extra elements");
 654                 return isl_schedule_tree_free(tree);
 655         }
 656
 657         return tree;
 658 }
 659
 660 /* Read an isl_schedule from "s".
 661  */
 662 __isl_give isl_schedule *isl_stream_read_schedule(isl_stream *s)
 663 {
 664         isl_ctx *ctx;
 665         isl_schedule_tree *tree;
 666
 667         if (!s)
 668                 return NULL;
 669
 670         ctx = isl_stream_get_ctx(s);
 671         tree = isl_stream_read_schedule_tree(s);
 672         return isl_schedule_from_schedule_tree(ctx, tree);
 673 }
 674
 675 /* Read an isl_schedule from "input".
 676  */
 677 __isl_give isl_schedule *isl_schedule_read_from_file(isl_ctx *ctx, FILE *input)
 678 {
 679         struct isl_stream *s;
 680         isl_schedule *schedule;
 681
 682         s = isl_stream_new_file(ctx, input);
 683         if (!s)
 684                 return NULL;
 685         schedule = isl_stream_read_schedule(s);
 686         isl_stream_free(s);
 687
 688         return schedule;
 689 }
 690
 691 /* Read an isl_schedule from "str".
 692  */
 693 __isl_give isl_schedule *isl_schedule_read_from_str(isl_ctx *ctx,
 694         const char *str)
 695 {
 696         struct isl_stream *s;
 697         isl_schedule *schedule;
 698
 699         s = isl_stream_new_str(ctx, str);
 700         if (!s)
 701                 return NULL;
 702         schedule = isl_stream_read_schedule(s);
 703         isl_stream_free(s);
 704
 705         return schedule;
 706 }