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