?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
verify_point_data_init: use isl_set_card to count elements in context
[barvinok.git] / iscc.c
blob418fb6a1c856f014fd9f6810371217bc2a434e6f
1 #include <assert.h>
2 #include <ctype.h>
3 #include <stdio.h>
4 #include <string.h>
5 #include <unistd.h>
6 #include <isl/obj.h>
7 #include <isl/stream.h>
8 #include <isl/set.h>
9 #include <isl/map.h>
10 #include <isl/vertices.h>
11 #include <isl/flow.h>
12 #include <isl/band.h>
13 #include <isl/schedule.h>
14 #include <isl/ast_build.h>
15 #include <isl_obj_list.h>
16 #include <isl_obj_str.h>
17 #include <barvinok/isl.h>
18 #include <barvinok/options.h>
19 #include "lattice_width.h"
20
21 #include "config.h"
22
23 #ifdef HAVE_SIGACTION
24 #include <signal.h>
25
26 static isl_ctx *main_ctx;
27
28 static void handler(int signum)
29 {
30 if (isl_ctx_aborted(main_ctx))
31 exit(EXIT_FAILURE);
32 isl_ctx_abort(main_ctx);
33 }
34
35 static struct sigaction sa_old;
36
37 static void install_signal_handler(isl_ctx *ctx)
38 {
39 struct sigaction sa;
40
41 main_ctx = ctx;
42
43 memset(&sa, 0, sizeof(struct sigaction));
44 sa.sa_handler = &handler;
45 sa.sa_flags = SA_RESTART;
46 sigaction(SIGINT, &sa, &sa_old);
47 }
48
49 static void remove_signal_handler(isl_ctx *ctx)
50 {
51 sigaction(SIGINT, &sa_old, NULL);
52 }
53
54 #else
55
56 static void install_signal_handler(isl_ctx *ctx)
57 {
58 }
59
60 static void remove_signal_handler(isl_ctx *ctx)
61 {
62 }
63
64 #endif
65
66 #ifdef HAVE_PET
67 #include <pet.h>
68 #else
69 struct pet_options;
70 int pet_options_set_autodetect(isl_ctx *ctx, int val)
71 {
72 return -1;
73 }
74 #endif
75
76 static int isl_bool_false = 0;
77 static int isl_bool_true = 1;
78 static int isl_bool_error = -1;
79
80 enum iscc_op { ISCC_READ, ISCC_WRITE, ISCC_SOURCE, ISCC_VERTICES,
81 ISCC_LAST, ISCC_ANY, ISCC_BEFORE, ISCC_UNDER,
82 ISCC_SCHEDULE, ISCC_SCHEDULE_FOREST,
83 ISCC_MINIMIZING, ISCC_RESPECTING,
84 ISCC_CODEGEN, ISCC_USING,
85 ISCC_TYPEOF, ISCC_PRINT, ISCC_ASSERT,
86 ISCC_N_OP };
87 static const char *op_name[ISCC_N_OP] = {
88 [ISCC_ASSERT] = "assert",
89 [ISCC_READ] = "read",
90 [ISCC_WRITE] = "write",
91 [ISCC_PRINT] = "print",
92 [ISCC_SOURCE] = "source",
93 [ISCC_VERTICES] = "vertices",
94 [ISCC_LAST] = "last",
95 [ISCC_ANY] = "any",
96 [ISCC_BEFORE] = "before",
97 [ISCC_UNDER] = "under",
98 [ISCC_SCHEDULE] = "schedule",
99 [ISCC_SCHEDULE_FOREST] = "schedule_forest",
100 [ISCC_MINIMIZING] = "minimizing",
101 [ISCC_RESPECTING] = "respecting",
102 [ISCC_CODEGEN] = "codegen",
103 [ISCC_USING] = "using",
104 [ISCC_TYPEOF] = "typeof"
105 };
106 static enum isl_token_type iscc_op[ISCC_N_OP];
107
108 struct isl_arg_choice iscc_format[] = {
109 {"isl", ISL_FORMAT_ISL},
110 {"omega", ISL_FORMAT_OMEGA},
111 {"polylib", ISL_FORMAT_POLYLIB},
112 {"ext-polylib", ISL_FORMAT_EXT_POLYLIB},
113 {"latex", ISL_FORMAT_LATEX},
114 {"C", ISL_FORMAT_C},
115 {0}
116 };
117
118 struct iscc_options {
119 struct barvinok_options *barvinok;
120 struct pet_options *pet;
121 unsigned format;
122 int io;
123 };
124
125 ISL_ARGS_START(struct iscc_options, iscc_options_args)
126 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", &barvinok_options_args,
127 "barvinok options")
128 #ifdef HAVE_PET
129 ISL_ARG_CHILD(struct iscc_options, pet, "pet", &pet_options_args, "pet options")
130 #endif
131 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
132 iscc_format, ISL_FORMAT_ISL, "output format")
133 ISL_ARG_BOOL(struct iscc_options, io, 0, "io", 1,
134 "allow read and write operations")
135 ISL_ARGS_END
136
137 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_args)
138 ISL_ARG_CTX_DEF(iscc_options, struct iscc_options, iscc_options_args)
139
140 static void *isl_obj_bool_copy(void *v)
141 {
142 return v;
143 }
144
145 static void isl_obj_bool_free(void *v)
146 {
147 }
148
149 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
150 void *v)
151 {
152 if (v == &isl_bool_true)
153 return isl_printer_print_str(p, "True");
154 else if (v == &isl_bool_false)
155 return isl_printer_print_str(p, "False");
156 else
157 return isl_printer_print_str(p, "Error");
158 }
159
160 static void *isl_obj_bool_add(void *v1, void *v2)
161 {
162 return v1;
163 }
164
165 struct isl_obj_vtable isl_obj_bool_vtable = {
166 isl_obj_bool_copy,
167 isl_obj_bool_add,
168 isl_obj_bool_print,
169 isl_obj_bool_free
170 };
171 #define isl_obj_bool (&isl_obj_bool_vtable)
172
173 int *isl_bool_from_int(int res)
174 {
175 return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
176 }
177
178 static int isl_union_map_is_superset(__isl_take isl_union_map *map1,
179 __isl_take isl_union_map *map2)
180 {
181 return isl_union_map_is_subset(map2, map1);
182 }
183 static int isl_union_set_is_superset(__isl_take isl_union_set *set1,
184 __isl_take isl_union_set *set2)
185 {
186 return isl_union_set_is_subset(set2, set1);
187 }
188
189 static int isl_union_map_is_strict_superset(__isl_take isl_union_map *map1,
190 __isl_take isl_union_map *map2)
191 {
192 return isl_union_map_is_strict_subset(map2, map1);
193 }
194 static int isl_union_set_is_strict_superset(__isl_take isl_union_set *set1,
195 __isl_take isl_union_set *set2)
196 {
197 return isl_union_set_is_strict_subset(set2, set1);
198 }
199
200 extern struct isl_obj_vtable isl_obj_list_vtable;
201 #define isl_obj_list (&isl_obj_list_vtable)
202
203 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
204 typedef int (*isc_bin_test_fn)(void *lhs, void *rhs);
205 struct isc_bin_op {
206 enum isl_token_type op;
207 isl_obj_type lhs;
208 isl_obj_type rhs;
209 isl_obj_type res;
210 union {
211 isc_bin_op_fn fn;
212 isc_bin_test_fn test;
213 } o;
214 };
215 struct isc_named_bin_op {
216 char *name;
217 struct isc_bin_op op;
218 };
219
220 struct iscc_at {
221 isl_union_pw_qpolynomial *upwqp;
222 isl_union_pw_qpolynomial *res;
223 };
224
225 static int eval_at(__isl_take isl_point *pnt, void *user)
226 {
227 struct iscc_at *at = (struct iscc_at *) user;
228 isl_val *v;
229 isl_qpolynomial *qp;
230 isl_set *set;
231
232 set = isl_set_from_point(isl_point_copy(pnt));
233 v = isl_union_pw_qpolynomial_eval(
234 isl_union_pw_qpolynomial_copy(at->upwqp), pnt);
235 qp = isl_qpolynomial_val_on_domain(isl_set_get_space(set), v);
236
237 at->res = isl_union_pw_qpolynomial_add(at->res,
238 isl_union_pw_qpolynomial_from_pw_qpolynomial(
239 isl_pw_qpolynomial_alloc(set, qp)));
240
241 return 0;
242 }
243
244 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
245 __isl_take isl_union_pw_qpolynomial *upwqp,
246 __isl_take isl_union_set *uset)
247 {
248 struct iscc_at at;
249
250 at.upwqp = upwqp;
251 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_space(uset));
252
253 isl_union_set_foreach_point(uset, eval_at, &at);
254
255 isl_union_pw_qpolynomial_free(upwqp);
256 isl_union_set_free(uset);
257
258 return at.res;
259 }
260
261 struct iscc_fold_at {
262 isl_union_pw_qpolynomial_fold *upwf;
263 isl_union_pw_qpolynomial *res;
264 };
265
266 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
267 {
268 struct iscc_fold_at *at = (struct iscc_fold_at *) user;
269 isl_val *v;
270 isl_qpolynomial *qp;
271 isl_set *set;
272
273 set = isl_set_from_point(isl_point_copy(pnt));
274 v = isl_union_pw_qpolynomial_fold_eval(
275 isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);
276 qp = isl_qpolynomial_val_on_domain(isl_set_get_space(set), v);
277
278 at->res = isl_union_pw_qpolynomial_add(at->res,
279 isl_union_pw_qpolynomial_from_pw_qpolynomial(
280 isl_pw_qpolynomial_alloc(set, qp)));
281
282 return 0;
283 }
284
285 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
286 __isl_take isl_union_pw_qpolynomial_fold *upwf,
287 __isl_take isl_union_set *uset)
288 {
289 struct iscc_fold_at at;
290
291 at.upwf = upwf;
292 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_space(uset));
293
294 isl_union_set_foreach_point(uset, eval_fold_at, &at);
295
296 isl_union_pw_qpolynomial_fold_free(upwf);
297 isl_union_set_free(uset);
298
299 return at.res;
300 }
301
302 static __isl_give isl_union_pw_qpolynomial_fold *union_pw_qpolynomial_add_union_pw_qpolynomial_fold(
303 __isl_take isl_union_pw_qpolynomial *upwqp,
304 __isl_take isl_union_pw_qpolynomial_fold *upwf)
305 {
306 return isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(upwf,
307 upwqp);
308 }
309
310 static __isl_give struct isl_list *union_map_apply_union_pw_qpolynomial_fold(
311 __isl_take isl_union_map *umap,
312 __isl_take isl_union_pw_qpolynomial_fold *upwf)
313 {
314 isl_ctx *ctx;
315 struct isl_list *list;
316 int tight;
317
318 ctx = isl_union_map_get_ctx(umap);
319 list = isl_list_alloc(ctx, 2);
320 if (!list)
321 goto error2;
322
323 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
324 list->obj[0].v = isl_union_map_apply_union_pw_qpolynomial_fold(umap,
325 upwf, &tight);
326 list->obj[1].type = isl_obj_bool;
327 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
328 if (tight < 0 || !list->obj[0].v)
329 goto error;
330
331 return list;
332 error2:
333 isl_union_map_free(umap);
334 isl_union_pw_qpolynomial_fold_free(upwf);
335 error:
336 isl_list_free(list);
337 return NULL;
338 }
339
340 static __isl_give struct isl_list *union_set_apply_union_pw_qpolynomial_fold(
341 __isl_take isl_union_set *uset,
342 __isl_take isl_union_pw_qpolynomial_fold *upwf)
343 {
344 isl_ctx *ctx;
345 struct isl_list *list;
346 int tight;
347
348 ctx = isl_union_set_get_ctx(uset);
349 list = isl_list_alloc(ctx, 2);
350 if (!list)
351 goto error2;
352
353 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
354 list->obj[0].v = isl_union_set_apply_union_pw_qpolynomial_fold(uset,
355 upwf, &tight);
356 list->obj[1].type = isl_obj_bool;
357 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
358 if (tight < 0 || !list->obj[0].v)
359 goto error;
360
361 return list;
362 error2:
363 isl_union_set_free(uset);
364 isl_union_pw_qpolynomial_fold_free(upwf);
365 error:
366 isl_list_free(list);
367 return NULL;
368 }
369
370 static __isl_give isl_union_pw_qpolynomial *isl_val_mul_union_pw_qpolynomial(
371 __isl_take isl_val *v, __isl_take isl_union_pw_qpolynomial *upwqp)
372 {
373 return isl_union_pw_qpolynomial_scale_val(upwqp, v);
374 }
375
376 static __isl_give isl_union_pw_qpolynomial_fold *
377 int_val_mul_union_pw_qpolynomial_fold(__isl_take isl_val *v,
378 __isl_take isl_union_pw_qpolynomial_fold *upwf)
379 {
380 return isl_union_pw_qpolynomial_fold_scale_val(upwf, v);
381 }
382
383 struct isc_bin_op bin_ops[] = {
384 { '+', isl_obj_val, isl_obj_val, isl_obj_val,
385 (isc_bin_op_fn) &isl_val_add },
386 { '-', isl_obj_val, isl_obj_val, isl_obj_val,
387 (isc_bin_op_fn) &isl_val_sub },
388 { '*', isl_obj_val, isl_obj_val, isl_obj_val,
389 (isc_bin_op_fn) &isl_val_mul },
390 { '+', isl_obj_union_set, isl_obj_union_set,
391 isl_obj_union_set,
392 (isc_bin_op_fn) &isl_union_set_union },
393 { '+', isl_obj_union_map, isl_obj_union_map,
394 isl_obj_union_map,
395 (isc_bin_op_fn) &isl_union_map_union },
396 { '-', isl_obj_union_set, isl_obj_union_set,
397 isl_obj_union_set,
398 (isc_bin_op_fn) &isl_union_set_subtract },
399 { '-', isl_obj_union_map, isl_obj_union_map,
400 isl_obj_union_map,
401 (isc_bin_op_fn) &isl_union_map_subtract },
402 { '*', isl_obj_union_set, isl_obj_union_set,
403 isl_obj_union_set,
404 (isc_bin_op_fn) &isl_union_set_intersect },
405 { '*', isl_obj_union_map, isl_obj_union_map,
406 isl_obj_union_map,
407 (isc_bin_op_fn) &isl_union_map_intersect },
408 { '*', isl_obj_union_map, isl_obj_union_set,
409 isl_obj_union_map,
410 (isc_bin_op_fn) &isl_union_map_intersect_domain },
411 { '.', isl_obj_union_map, isl_obj_union_map,
412 isl_obj_union_map,
413 (isc_bin_op_fn) &isl_union_map_apply_range },
414 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial,
415 isl_obj_union_pw_qpolynomial,
416 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
417 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial_fold,
418 isl_obj_list,
419 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold },
420 { ISL_TOKEN_TO, isl_obj_union_set, isl_obj_union_set,
421 isl_obj_union_map,
422 (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
423 { '=', isl_obj_union_set, isl_obj_union_set, isl_obj_bool,
424 { .test = (isc_bin_test_fn) &isl_union_set_is_equal } },
425 { '=', isl_obj_union_map, isl_obj_union_map, isl_obj_bool,
426 { .test = (isc_bin_test_fn) &isl_union_map_is_equal } },
427 { ISL_TOKEN_LE, isl_obj_union_set, isl_obj_union_set,
428 isl_obj_bool,
429 { .test = (isc_bin_test_fn) &isl_union_set_is_subset } },
430 { ISL_TOKEN_LE, isl_obj_union_map, isl_obj_union_map,
431 isl_obj_bool,
432 { .test = (isc_bin_test_fn) &isl_union_map_is_subset } },
433 { ISL_TOKEN_LT, isl_obj_union_set, isl_obj_union_set,
434 isl_obj_bool,
435 { .test = (isc_bin_test_fn) &isl_union_set_is_strict_subset } },
436 { ISL_TOKEN_LT, isl_obj_union_map, isl_obj_union_map,
437 isl_obj_bool,
438 { .test = (isc_bin_test_fn) &isl_union_map_is_strict_subset } },
439 { ISL_TOKEN_GE, isl_obj_union_set, isl_obj_union_set,
440 isl_obj_bool,
441 { .test = (isc_bin_test_fn) &isl_union_set_is_superset } },
442 { ISL_TOKEN_GE, isl_obj_union_map, isl_obj_union_map,
443 isl_obj_bool,
444 { .test = (isc_bin_test_fn) &isl_union_map_is_superset } },
445 { ISL_TOKEN_GT, isl_obj_union_set, isl_obj_union_set,
446 isl_obj_bool,
447 { .test =
448 (isc_bin_test_fn) &isl_union_set_is_strict_superset } },
449 { ISL_TOKEN_GT, isl_obj_union_map, isl_obj_union_map,
450 isl_obj_bool,
451 { .test =
452 (isc_bin_test_fn) &isl_union_map_is_strict_superset } },
453 { ISL_TOKEN_LEX_LE, isl_obj_union_set, isl_obj_union_set,
454 isl_obj_union_map,
455 (isc_bin_op_fn) &isl_union_set_lex_le_union_set },
456 { ISL_TOKEN_LEX_LT, isl_obj_union_set, isl_obj_union_set,
457 isl_obj_union_map,
458 (isc_bin_op_fn) &isl_union_set_lex_lt_union_set },
459 { ISL_TOKEN_LEX_GE, isl_obj_union_set, isl_obj_union_set,
460 isl_obj_union_map,
461 (isc_bin_op_fn) &isl_union_set_lex_ge_union_set },
462 { ISL_TOKEN_LEX_GT, isl_obj_union_set, isl_obj_union_set,
463 isl_obj_union_map,
464 (isc_bin_op_fn) &isl_union_set_lex_gt_union_set },
465 { ISL_TOKEN_LEX_LE, isl_obj_union_map, isl_obj_union_map,
466 isl_obj_union_map,
467 (isc_bin_op_fn) &isl_union_map_lex_le_union_map },
468 { ISL_TOKEN_LEX_LT, isl_obj_union_map, isl_obj_union_map,
469 isl_obj_union_map,
470 (isc_bin_op_fn) &isl_union_map_lex_lt_union_map },
471 { ISL_TOKEN_LEX_GE, isl_obj_union_map, isl_obj_union_map,
472 isl_obj_union_map,
473 (isc_bin_op_fn) &isl_union_map_lex_ge_union_map },
474 { ISL_TOKEN_LEX_GT, isl_obj_union_map, isl_obj_union_map,
475 isl_obj_union_map,
476 (isc_bin_op_fn) &isl_union_map_lex_gt_union_map },
477 { '.', isl_obj_union_pw_qpolynomial_fold,
478 isl_obj_union_pw_qpolynomial_fold,
479 isl_obj_union_pw_qpolynomial_fold,
480 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_fold },
481 { '+', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
482 isl_obj_union_pw_qpolynomial,
483 (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
484 { '+', isl_obj_union_pw_qpolynomial,
485 isl_obj_union_pw_qpolynomial_fold,
486 isl_obj_union_pw_qpolynomial_fold,
487 (isc_bin_op_fn) &union_pw_qpolynomial_add_union_pw_qpolynomial_fold },
488 { '+', isl_obj_union_pw_qpolynomial_fold,
489 isl_obj_union_pw_qpolynomial,
490 isl_obj_union_pw_qpolynomial_fold,
491 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial },
492 { '-', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
493 isl_obj_union_pw_qpolynomial,
494 (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
495 { '*', isl_obj_val, isl_obj_union_pw_qpolynomial,
496 isl_obj_union_pw_qpolynomial,
497 (isc_bin_op_fn) &isl_val_mul_union_pw_qpolynomial },
498 { '*', isl_obj_union_pw_qpolynomial, isl_obj_val,
499 isl_obj_union_pw_qpolynomial,
500 (isc_bin_op_fn) &isl_union_pw_qpolynomial_scale_val },
501 { '*', isl_obj_val, isl_obj_union_pw_qpolynomial_fold,
502 isl_obj_union_pw_qpolynomial_fold,
503 (isc_bin_op_fn) &int_val_mul_union_pw_qpolynomial_fold },
504 { '*', isl_obj_union_pw_qpolynomial_fold, isl_obj_val,
505 isl_obj_union_pw_qpolynomial_fold,
506 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_scale_val },
507 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
508 isl_obj_union_pw_qpolynomial,
509 (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
510 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
511 isl_obj_union_pw_qpolynomial,
512 (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
513 { '*', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
514 isl_obj_union_pw_qpolynomial_fold,
515 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
516 { '@', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
517 isl_obj_union_pw_qpolynomial,
518 (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
519 { '@', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
520 isl_obj_union_pw_qpolynomial,
521 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
522 { '%', isl_obj_union_set, isl_obj_union_set,
523 isl_obj_union_set,
524 (isc_bin_op_fn) &isl_union_set_gist },
525 { '%', isl_obj_union_map, isl_obj_union_map,
526 isl_obj_union_map,
527 (isc_bin_op_fn) &isl_union_map_gist },
528 { '%', isl_obj_union_map, isl_obj_union_set,
529 isl_obj_union_map,
530 (isc_bin_op_fn) &isl_union_map_gist_domain },
531 { '%', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
532 isl_obj_union_pw_qpolynomial,
533 (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
534 { '%', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
535 isl_obj_union_pw_qpolynomial_fold,
536 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
537 { ISL_TOKEN_EQ_EQ, isl_obj_union_pw_qpolynomial,
538 isl_obj_union_pw_qpolynomial, isl_obj_bool,
539 { .test = (isc_bin_test_fn)
540 &isl_union_pw_qpolynomial_plain_is_equal } },
541 { ISL_TOKEN_EQ_EQ, isl_obj_union_pw_qpolynomial_fold,
542 isl_obj_union_pw_qpolynomial_fold, isl_obj_bool,
543 { .test = (isc_bin_test_fn)
544 &isl_union_pw_qpolynomial_fold_plain_is_equal } },
545 { '+', isl_obj_str, isl_obj_str, isl_obj_str,
546 (isc_bin_op_fn) &isl_str_concat },
547 0
548 };
549
550 static __isl_give isl_union_map *map_after_map(__isl_take isl_union_map *umap1,
551 __isl_take isl_union_map *umap2)
552 {
553 return isl_union_map_apply_range(umap2, umap1);
554 }
555
556 static __isl_give isl_union_pw_qpolynomial *qpolynomial_after_map(
557 __isl_take isl_union_pw_qpolynomial *upwqp,
558 __isl_take isl_union_map *umap)
559 {
560 return isl_union_map_apply_union_pw_qpolynomial(umap, upwqp);
561 }
562
563 static __isl_give struct isl_list *qpolynomial_fold_after_map(
564 __isl_take isl_union_pw_qpolynomial_fold *upwf,
565 __isl_take isl_union_map *umap)
566 {
567 return union_map_apply_union_pw_qpolynomial_fold(umap, upwf);
568 }
569
570 struct isc_named_bin_op named_bin_ops[] = {
571 { "after", { -1, isl_obj_union_map, isl_obj_union_map,
572 isl_obj_union_map,
573 (isc_bin_op_fn) &map_after_map } },
574 { "after", { -1, isl_obj_union_pw_qpolynomial,
575 isl_obj_union_map, isl_obj_union_pw_qpolynomial,
576 (isc_bin_op_fn) &qpolynomial_after_map } },
577 { "after", { -1, isl_obj_union_pw_qpolynomial_fold,
578 isl_obj_union_map, isl_obj_list,
579 (isc_bin_op_fn) &qpolynomial_fold_after_map } },
580 { "before", { -1, isl_obj_union_map, isl_obj_union_map,
581 isl_obj_union_map,
582 (isc_bin_op_fn) &isl_union_map_apply_range } },
583 { "before", { -1, isl_obj_union_map,
584 isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
585 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial } },
586 { "before", { -1, isl_obj_union_map,
587 isl_obj_union_pw_qpolynomial_fold, isl_obj_list,
588 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold } },
589 { "cross", { -1, isl_obj_union_set, isl_obj_union_set,
590 isl_obj_union_set,
591 (isc_bin_op_fn) &isl_union_set_product } },
592 { "cross", { -1, isl_obj_union_map, isl_obj_union_map,
593 isl_obj_union_map,
594 (isc_bin_op_fn) &isl_union_map_product } },
595 NULL
596 };
597
598 __isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
599 {
600 return isl_set_from_basic_set(isl_union_set_sample(uset));
601 }
602
603 __isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
604 {
605 return isl_map_from_basic_map(isl_union_map_sample(umap));
606 }
607
608 static __isl_give struct isl_list *union_map_power(
609 __isl_take isl_union_map *umap)
610 {
611 isl_ctx *ctx;
612 struct isl_list *list;
613 int exact;
614
615 ctx = isl_union_map_get_ctx(umap);
616 list = isl_list_alloc(ctx, 2);
617 if (!list)
618 goto error2;
619
620 list->obj[0].type = isl_obj_union_map;
621 list->obj[0].v = isl_union_map_power(umap, &exact);
622 list->obj[1].type = isl_obj_bool;
623 list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
624 if (exact < 0 || !list->obj[0].v)
625 goto error;
626
627 return list;
628 error2:
629 isl_union_map_free(umap);
630 error:
631 isl_list_free(list);
632 return NULL;
633 }
634
635 static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
636 __isl_take isl_union_pw_qpolynomial *upwqp)
637 {
638 isl_ctx *ctx;
639 struct isl_list *list;
640 int tight;
641
642 ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
643 list = isl_list_alloc(ctx, 2);
644 if (!list)
645 goto error2;
646
647 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
648 list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
649 isl_fold_max, &tight);
650 list->obj[1].type = isl_obj_bool;
651 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
652 if (tight < 0 || !list->obj[0].v)
653 goto error;
654
655 return list;
656 error2:
657 isl_union_pw_qpolynomial_free(upwqp);
658 error:
659 isl_list_free(list);
660 return NULL;
661 }
662
663 #ifdef HAVE_PET
664 static __isl_give isl_list *parse(__isl_take isl_str *str)
665 {
666 isl_ctx *ctx;
667 struct isl_list *list;
668 struct pet_scop *scop;
669 isl_union_map *sched, *reads, *writes;
670 isl_union_set *domain;
671 struct iscc_options *options;
672
673 if (!str)
674 return NULL;
675 ctx = str->ctx;
676
677 options = isl_ctx_peek_iscc_options(ctx);
678 if (!options || !options->io) {
679 isl_str_free(str);
680 isl_die(ctx, isl_error_invalid,
681 "parse_file operation not allowed", return NULL);
682 }
683
684 list = isl_list_alloc(ctx, 4);
685 if (!list)
686 goto error;
687
688 scop = pet_scop_extract_from_C_source(ctx, str->s, NULL);
689 domain = pet_scop_collect_domains(scop);
690 sched = pet_scop_collect_schedule(scop);
691 reads = pet_scop_collect_reads(scop);
692 writes = pet_scop_collect_writes(scop);
693 pet_scop_free(scop);
694
695 list->obj[0].type = isl_obj_union_set;
696 list->obj[0].v = domain;
697 list->obj[1].type = isl_obj_union_map;
698 list->obj[1].v = writes;
699 list->obj[2].type = isl_obj_union_map;
700 list->obj[2].v = reads;
701 list->obj[3].type = isl_obj_union_map;
702 list->obj[3].v = sched;
703
704 if (!list->obj[0].v || !list->obj[1].v ||
705 !list->obj[2].v || !list->obj[3].v)
706 goto error;
707
708 isl_str_free(str);
709 return list;
710 error:
711 isl_list_free(list);
712 isl_str_free(str);
713 return NULL;
714 }
715 #endif
716
717 static int add_point(__isl_take isl_point *pnt, void *user)
718 {
719 isl_union_set **scan = (isl_union_set **) user;
720
721 *scan = isl_union_set_add_set(*scan, isl_set_from_point(pnt));
722
723 return 0;
724 }
725
726 static __isl_give isl_union_set *union_set_scan(__isl_take isl_union_set *uset)
727 {
728 isl_union_set *scan;
729
730 scan = isl_union_set_empty(isl_union_set_get_space(uset));
731
732 if (isl_union_set_foreach_point(uset, add_point, &scan) < 0) {
733 isl_union_set_free(scan);
734 return uset;
735 }
736
737 isl_union_set_free(uset);
738 return scan;
739 }
740
741 static __isl_give isl_union_map *union_map_scan(__isl_take isl_union_map *umap)
742 {
743 return isl_union_set_unwrap(union_set_scan(isl_union_map_wrap(umap)));
744 }
745
746 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_poly(
747 __isl_take isl_union_pw_qpolynomial *upwqp)
748 {
749 return isl_union_pw_qpolynomial_to_polynomial(upwqp, 0);
750 }
751
752 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_lpoly(
753 __isl_take isl_union_pw_qpolynomial *upwqp)
754 {
755 return isl_union_pw_qpolynomial_to_polynomial(upwqp, -1);
756 }
757
758 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_upoly(
759 __isl_take isl_union_pw_qpolynomial *upwqp)
760 {
761 return isl_union_pw_qpolynomial_to_polynomial(upwqp, 1);
762 }
763
764 typedef void *(*isc_un_op_fn)(void *arg);
765 struct isc_un_op {
766 enum isl_token_type op;
767 isl_obj_type arg;
768 isl_obj_type res;
769 isc_un_op_fn fn;
770 };
771 struct isc_named_un_op {
772 char *name;
773 struct isc_un_op op;
774 };
775 struct isc_named_un_op named_un_ops[] = {
776 {"aff", { -1, isl_obj_union_map, isl_obj_union_map,
777 (isc_un_op_fn) &isl_union_map_affine_hull } },
778 {"aff", { -1, isl_obj_union_set, isl_obj_union_set,
779 (isc_un_op_fn) &isl_union_set_affine_hull } },
780 {"card", { -1, isl_obj_union_set,
781 isl_obj_union_pw_qpolynomial,
782 (isc_un_op_fn) &isl_union_set_card } },
783 {"card", { -1, isl_obj_union_map,
784 isl_obj_union_pw_qpolynomial,
785 (isc_un_op_fn) &isl_union_map_card } },
786 {"coalesce", { -1, isl_obj_union_set, isl_obj_union_set,
787 (isc_un_op_fn) &isl_union_set_coalesce } },
788 {"coalesce", { -1, isl_obj_union_map, isl_obj_union_map,
789 (isc_un_op_fn) &isl_union_map_coalesce } },
790 {"coalesce", { -1, isl_obj_union_pw_qpolynomial,
791 isl_obj_union_pw_qpolynomial,
792 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
793 {"coalesce", { -1, isl_obj_union_pw_qpolynomial_fold,
794 isl_obj_union_pw_qpolynomial_fold,
795 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
796 {"coefficients", { -1, isl_obj_union_set,
797 isl_obj_union_set,
798 (isc_un_op_fn) &isl_union_set_coefficients } },
799 {"solutions", { -1, isl_obj_union_set, isl_obj_union_set,
800 (isc_un_op_fn) &isl_union_set_solutions } },
801 {"deltas", { -1, isl_obj_union_map, isl_obj_union_set,
802 (isc_un_op_fn) &isl_union_map_deltas } },
803 {"deltas_map", { -1, isl_obj_union_map, isl_obj_union_map,
804 (isc_un_op_fn) &isl_union_map_deltas_map } },
805 {"dom", { -1, isl_obj_union_map, isl_obj_union_set,
806 (isc_un_op_fn) &isl_union_map_domain } },
807 {"dom", { -1, isl_obj_union_pw_qpolynomial, isl_obj_union_set,
808 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
809 {"dom", { -1, isl_obj_union_pw_qpolynomial_fold,
810 isl_obj_union_set,
811 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
812 {"domain", { -1, isl_obj_union_map, isl_obj_union_set,
813 (isc_un_op_fn) &isl_union_map_domain } },
814 {"domain", { -1, isl_obj_union_pw_qpolynomial,
815 isl_obj_union_set,
816 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
817 {"domain", { -1, isl_obj_union_pw_qpolynomial_fold,
818 isl_obj_union_set,
819 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
820 {"domain_map", { -1, isl_obj_union_map, isl_obj_union_map,
821 (isc_un_op_fn) &isl_union_map_domain_map } },
822 {"ran", { -1, isl_obj_union_map, isl_obj_union_set,
823 (isc_un_op_fn) &isl_union_map_range } },
824 {"range", { -1, isl_obj_union_map, isl_obj_union_set,
825 (isc_un_op_fn) &isl_union_map_range } },
826 {"range_map", { -1, isl_obj_union_map, isl_obj_union_map,
827 (isc_un_op_fn) &isl_union_map_range_map } },
828 {"identity", { -1, isl_obj_union_set, isl_obj_union_map,
829 (isc_un_op_fn) &isl_union_set_identity } },
830 {"lattice_width", { -1, isl_obj_union_set,
831 isl_obj_union_pw_qpolynomial,
832 (isc_un_op_fn) &isl_union_set_lattice_width } },
833 {"lexmin", { -1, isl_obj_union_map, isl_obj_union_map,
834 (isc_un_op_fn) &isl_union_map_lexmin } },
835 {"lexmax", { -1, isl_obj_union_map, isl_obj_union_map,
836 (isc_un_op_fn) &isl_union_map_lexmax } },
837 {"lexmin", { -1, isl_obj_union_set, isl_obj_union_set,
838 (isc_un_op_fn) &isl_union_set_lexmin } },
839 {"lexmax", { -1, isl_obj_union_set, isl_obj_union_set,
840 (isc_un_op_fn) &isl_union_set_lexmax } },
841 {"lift", { -1, isl_obj_union_set, isl_obj_union_set,
842 (isc_un_op_fn) &isl_union_set_lift } },
843 {"params", { -1, isl_obj_union_map, isl_obj_set,
844 (isc_un_op_fn) &isl_union_map_params } },
845 {"params", { -1, isl_obj_union_set, isl_obj_set,
846 (isc_un_op_fn) &isl_union_set_params } },
847 {"poly", { -1, isl_obj_union_map, isl_obj_union_map,
848 (isc_un_op_fn) &isl_union_map_polyhedral_hull } },
849 {"poly", { -1, isl_obj_union_set, isl_obj_union_set,
850 (isc_un_op_fn) &isl_union_set_polyhedral_hull } },
851 {"poly", { -1, isl_obj_union_pw_qpolynomial,
852 isl_obj_union_pw_qpolynomial,
853 (isc_un_op_fn) &union_pw_qpolynomial_poly } },
854 {"lpoly", { -1, isl_obj_union_pw_qpolynomial,
855 isl_obj_union_pw_qpolynomial,
856 (isc_un_op_fn) &union_pw_qpolynomial_lpoly } },
857 {"upoly", { -1, isl_obj_union_pw_qpolynomial,
858 isl_obj_union_pw_qpolynomial,
859 (isc_un_op_fn) &union_pw_qpolynomial_upoly } },
860 #ifdef HAVE_PET
861 {"parse_file", { -1, isl_obj_str, isl_obj_list,
862 (isc_un_op_fn) &parse } },
863 #endif
864 {"pow", { -1, isl_obj_union_map, isl_obj_list,
865 (isc_un_op_fn) &union_map_power } },
866 {"sample", { -1, isl_obj_union_set, isl_obj_set,
867 (isc_un_op_fn) &union_set_sample } },
868 {"sample", { -1, isl_obj_union_map, isl_obj_map,
869 (isc_un_op_fn) &union_map_sample } },
870 {"scan", { -1, isl_obj_union_set, isl_obj_union_set,
871 (isc_un_op_fn) &union_set_scan } },
872 {"scan", { -1, isl_obj_union_map, isl_obj_union_map,
873 (isc_un_op_fn) &union_map_scan } },
874 {"sum", { -1, isl_obj_union_pw_qpolynomial,
875 isl_obj_union_pw_qpolynomial,
876 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
877 {"ub", { -1, isl_obj_union_pw_qpolynomial, isl_obj_list,
878 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
879 {"unwrap", { -1, isl_obj_union_set, isl_obj_union_map,
880 (isc_un_op_fn) &isl_union_set_unwrap } },
881 {"wrap", { -1, isl_obj_union_map, isl_obj_union_set,
882 (isc_un_op_fn) &isl_union_map_wrap } },
883 {"zip", { -1, isl_obj_union_map, isl_obj_union_map,
884 (isc_un_op_fn) &isl_union_map_zip } },
885 NULL
886 };
887
888 struct isl_named_obj {
889 char *name;
890 struct isl_obj obj;
891 };
892
893 static void free_obj(struct isl_obj obj)
894 {
895 obj.type->free(obj.v);
896 }
897
898 static int same_name(const void *entry, const void *val)
899 {
900 const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
901
902 return !strcmp(named->name, val);
903 }
904
905 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
906 char *name, struct isl_obj obj)
907 {
908 struct isl_hash_table_entry *entry;
909 uint32_t name_hash;
910 struct isl_named_obj *named;
911
912 name_hash = isl_hash_string(isl_hash_init(), name);
913 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
914 if (!entry)
915 goto error;
916 if (entry->data) {
917 named = entry->data;
918 free_obj(named->obj);
919 free(name);
920 } else {
921 named = isl_alloc_type(ctx, struct isl_named_obj);
922 if (!named)
923 goto error;
924 named->name = name;
925 entry->data = named;
926 }
927 named->obj = obj;
928
929 return 0;
930 error:
931 free_obj(obj);
932 free(name);
933 return -1;
934 }
935
936 static struct isl_obj stored_obj(struct isl_ctx *ctx,
937 struct isl_hash_table *table, char *name)
938 {
939 struct isl_obj obj = { isl_obj_none, NULL };
940 struct isl_hash_table_entry *entry;
941 uint32_t name_hash;
942
943 name_hash = isl_hash_string(isl_hash_init(), name);
944 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
945 if (entry) {
946 struct isl_named_obj *named;
947 named = entry->data;
948 obj = named->obj;
949 } else if (isdigit(name[0]))
950 fprintf(stderr, "unknown identifier '$%s'\n", name);
951 else
952 fprintf(stderr, "unknown identifier '%s'\n", name);
953
954 free(name);
955 obj.v = obj.type->copy(obj.v);
956 return obj;
957 }
958
959 static int is_subtype(struct isl_obj obj, isl_obj_type super)
960 {
961 if (obj.type == super)
962 return 1;
963 if (obj.type == isl_obj_map && super == isl_obj_union_map)
964 return 1;
965 if (obj.type == isl_obj_set && super == isl_obj_union_set)
966 return 1;
967 if (obj.type == isl_obj_pw_qpolynomial &&
968 super == isl_obj_union_pw_qpolynomial)
969 return 1;
970 if (obj.type == isl_obj_pw_qpolynomial_fold &&
971 super == isl_obj_union_pw_qpolynomial_fold)
972 return 1;
973 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
974 return 1;
975 if (obj.type == isl_obj_list) {
976 struct isl_list *list = obj.v;
977 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
978 return is_subtype(list->obj[0], super);
979 }
980 if (super == isl_obj_str)
981 return 1;
982 return 0;
983 }
984
985 static struct isl_obj obj_at(struct isl_obj obj, int i)
986 {
987 struct isl_list *list = obj.v;
988
989 obj = list->obj[i];
990 obj.v = obj.type->copy(obj.v);
991
992 isl_list_free(list);
993
994 return obj;
995 }
996
997 static struct isl_obj convert(isl_ctx *ctx, struct isl_obj obj,
998 isl_obj_type type)
999 {
1000 if (obj.type == type)
1001 return obj;
1002 if (obj.type == isl_obj_map && type == isl_obj_union_map) {
1003 obj.type = isl_obj_union_map;
1004 obj.v = isl_union_map_from_map(obj.v);
1005 return obj;
1006 }
1007 if (obj.type == isl_obj_set && type == isl_obj_union_set) {
1008 obj.type = isl_obj_union_set;
1009 obj.v = isl_union_set_from_set(obj.v);
1010 return obj;
1011 }
1012 if (obj.type == isl_obj_pw_qpolynomial &&
1013 type == isl_obj_union_pw_qpolynomial) {
1014 obj.type = isl_obj_union_pw_qpolynomial;
1015 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
1016 return obj;
1017 }
1018 if (obj.type == isl_obj_pw_qpolynomial_fold &&
1019 type == isl_obj_union_pw_qpolynomial_fold) {
1020 obj.type = isl_obj_union_pw_qpolynomial_fold;
1021 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
1022 return obj;
1023 }
1024 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
1025 if (type == isl_obj_union_map) {
1026 obj.type = isl_obj_union_map;
1027 return obj;
1028 }
1029 if (type == isl_obj_union_pw_qpolynomial) {
1030 isl_space *dim = isl_union_set_get_space(obj.v);
1031 isl_union_set_free(obj.v);
1032 obj.v = isl_union_pw_qpolynomial_zero(dim);
1033 obj.type = isl_obj_union_pw_qpolynomial;
1034 return obj;
1035 }
1036 if (type == isl_obj_union_pw_qpolynomial_fold) {
1037 isl_space *dim = isl_union_set_get_space(obj.v);
1038 isl_union_set_free(obj.v);
1039 obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
1040 isl_fold_list);
1041 obj.type = isl_obj_union_pw_qpolynomial_fold;
1042 return obj;
1043 }
1044 }
1045 if (obj.type == isl_obj_list) {
1046 struct isl_list *list = obj.v;
1047 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1048 return convert(ctx, obj_at(obj, 0), type);
1049 }
1050 if (type == isl_obj_str) {
1051 isl_str *str;
1052 isl_printer *p;
1053 char *s;
1054
1055 p = isl_printer_to_str(ctx);
1056 if (!p)
1057 goto error;
1058 p = obj.type->print(p, obj.v);
1059 s = isl_printer_get_str(p);
1060 isl_printer_free(p);
1061
1062 str = isl_str_from_string(ctx, s);
1063 if (!str)
1064 goto error;
1065 free_obj(obj);
1066 obj.v = str;
1067 obj.type = isl_obj_str;
1068 return obj;
1069
1070 }
1071 error:
1072 free_obj(obj);
1073 obj.type = isl_obj_none;
1074 obj.v = NULL;
1075 return obj;
1076 }
1077
1078 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
1079 struct isl_obj lhs)
1080 {
1081 int i;
1082 struct isl_token *tok;
1083
1084 tok = isl_stream_next_token(s);
1085 if (!tok)
1086 return NULL;
1087
1088 for (i = 0; ; ++i) {
1089 if (!bin_ops[i].op)
1090 break;
1091 if (bin_ops[i].op != isl_token_get_type(tok))
1092 continue;
1093 if (!is_subtype(lhs, bin_ops[i].lhs))
1094 continue;
1095
1096 isl_token_free(tok);
1097 return &bin_ops[i];
1098 }
1099
1100 for (i = 0; ; ++i) {
1101 if (!named_bin_ops[i].name)
1102 break;
1103 if (named_bin_ops[i].op.op != isl_token_get_type(tok))
1104 continue;
1105 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1106 continue;
1107
1108 isl_token_free(tok);
1109 return &named_bin_ops[i].op;
1110 }
1111
1112 isl_stream_push_token(s, tok);
1113
1114 return NULL;
1115 }
1116
1117 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
1118 {
1119 int i;
1120 struct isl_token *tok;
1121
1122 tok = isl_stream_next_token(s);
1123 if (!tok)
1124 return NULL;
1125
1126 for (i = 0; ; ++i) {
1127 if (!named_un_ops[i].name)
1128 break;
1129 if (named_un_ops[i].op.op != isl_token_get_type(tok))
1130 continue;
1131
1132 isl_token_free(tok);
1133 return &named_un_ops[i].op;
1134 }
1135
1136 isl_stream_push_token(s, tok);
1137
1138 return NULL;
1139 }
1140
1141 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
1142 struct isl_obj arg)
1143 {
1144 int i;
1145
1146 for (i = 0; ; ++i) {
1147 if (!named_un_ops[i].name)
1148 break;
1149 if (named_un_ops[i].op.op != like->op)
1150 continue;
1151 if (!is_subtype(arg, named_un_ops[i].op.arg))
1152 continue;
1153
1154 return &named_un_ops[i].op;
1155 }
1156
1157 return NULL;
1158 }
1159
1160 static int is_assign(struct isl_stream *s)
1161 {
1162 struct isl_token *tok;
1163 struct isl_token *tok2;
1164 int assign;
1165
1166 tok = isl_stream_next_token(s);
1167 if (!tok)
1168 return 0;
1169 if (isl_token_get_type(tok) != ISL_TOKEN_IDENT) {
1170 isl_stream_push_token(s, tok);
1171 return 0;
1172 }
1173
1174 tok2 = isl_stream_next_token(s);
1175 if (!tok2) {
1176 isl_stream_push_token(s, tok);
1177 return 0;
1178 }
1179 assign = isl_token_get_type(tok2) == ISL_TOKEN_DEF;
1180 isl_stream_push_token(s, tok2);
1181 isl_stream_push_token(s, tok);
1182
1183 return assign;
1184 }
1185
1186 static struct isl_obj read_obj(struct isl_stream *s,
1187 struct isl_hash_table *table);
1188 static struct isl_obj read_expr(struct isl_stream *s,
1189 struct isl_hash_table *table);
1190
1191 static struct isl_obj read_un_op_expr(struct isl_stream *s,
1192 struct isl_hash_table *table, struct isc_un_op *op)
1193 {
1194 struct isl_obj obj = { isl_obj_none, NULL };
1195
1196 obj = read_obj(s, table);
1197 if (!obj.v)
1198 goto error;
1199
1200 op = find_matching_un_op(op, obj);
1201
1202 if (!op)
1203 isl_die(s->ctx, isl_error_invalid,
1204 "no such unary operator defined on given operand",
1205 goto error);
1206
1207 obj = convert(s->ctx, obj, op->arg);
1208 obj.v = op->fn(obj.v);
1209 obj.type = op->res;
1210
1211 return obj;
1212 error:
1213 free_obj(obj);
1214 obj.type = isl_obj_none;
1215 obj.v = NULL;
1216 return obj;
1217 }
1218
1219 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
1220 {
1221 struct isl_list *list;
1222 int exact;
1223
1224 if (obj.type != isl_obj_union_map)
1225 obj = convert(ctx, obj, isl_obj_union_map);
1226 isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
1227 list = isl_list_alloc(ctx, 2);
1228 if (!list)
1229 goto error;
1230
1231 list->obj[0].type = isl_obj_union_map;
1232 list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
1233 list->obj[1].type = isl_obj_bool;
1234 list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
1235 obj.v = list;
1236 obj.type = isl_obj_list;
1237 if (exact < 0 || !list->obj[0].v)
1238 goto error;
1239
1240 return obj;
1241 error:
1242 free_obj(obj);
1243 obj.type = isl_obj_none;
1244 obj.v = NULL;
1245 return obj;
1246 }
1247
1248 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
1249 {
1250 struct isl_list *list = obj.v;
1251 struct isl_token *tok;
1252 isl_val *v;
1253 int i;
1254
1255 tok = isl_stream_next_token(s);
1256 if (!tok || isl_token_get_type(tok) != ISL_TOKEN_VALUE) {
1257 isl_stream_error(s, tok, "expecting index");
1258 if (tok)
1259 isl_stream_push_token(s, tok);
1260 goto error;
1261 }
1262 v = isl_token_get_val(s->ctx, tok);
1263 i = isl_val_get_num_si(v);
1264 isl_val_free(v);
1265 isl_token_free(tok);
1266 isl_assert(s->ctx, i < list->n, goto error);
1267 if (isl_stream_eat(s, ']'))
1268 goto error;
1269
1270 return obj_at(obj, i);
1271 error:
1272 free_obj(obj);
1273 obj.type = isl_obj_none;
1274 obj.v = NULL;
1275 return obj;
1276 }
1277
1278 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
1279 struct isl_hash_table *table)
1280 {
1281 struct isl_obj obj;
1282
1283 obj = read_expr(s, table);
1284 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
1285 is_subtype(obj, isl_obj_union_map), goto error);
1286
1287 if (obj.type == isl_obj_list) {
1288 struct isl_list *list = obj.v;
1289 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1290 obj = obj_at(obj, 0);
1291 }
1292 if (obj.type == isl_obj_set)
1293 obj = convert(s->ctx, obj, isl_obj_union_set);
1294 else if (obj.type == isl_obj_map)
1295 obj = convert(s->ctx, obj, isl_obj_union_map);
1296 if (obj.type == isl_obj_union_set) {
1297 obj.v = isl_union_set_apply(obj.v, umap);
1298 } else
1299 obj.v = isl_union_map_apply_range(obj.v, umap);
1300 if (!obj.v)
1301 goto error2;
1302
1303 if (isl_stream_eat(s, ')'))
1304 goto error2;
1305
1306 return obj;
1307 error:
1308 isl_union_map_free(umap);
1309 error2:
1310 free_obj(obj);
1311 obj.type = isl_obj_none;
1312 obj.v = NULL;
1313 return obj;
1314 }
1315
1316 static struct isl_obj apply_fun_set(struct isl_obj obj,
1317 __isl_take isl_union_set *uset)
1318 {
1319 if (obj.type == isl_obj_union_pw_qpolynomial) {
1320 obj.v = isl_union_set_apply_union_pw_qpolynomial(uset, obj.v);
1321 } else {
1322 obj.type = isl_obj_list;
1323 obj.v = union_set_apply_union_pw_qpolynomial_fold(uset, obj.v);
1324 }
1325 return obj;
1326 }
1327
1328 static struct isl_obj apply_fun_map(struct isl_obj obj,
1329 __isl_take isl_union_map *umap)
1330 {
1331 if (obj.type == isl_obj_union_pw_qpolynomial) {
1332 obj.v = isl_union_map_apply_union_pw_qpolynomial(umap, obj.v);
1333 } else {
1334 obj.type = isl_obj_list;
1335 obj.v = union_map_apply_union_pw_qpolynomial_fold(umap, obj.v);
1336 }
1337 return obj;
1338 }
1339
1340 static struct isl_obj apply_fun(struct isl_stream *s,
1341 struct isl_obj obj, struct isl_hash_table *table)
1342 {
1343 struct isl_obj arg;
1344
1345 arg = read_expr(s, table);
1346 if (!is_subtype(arg, isl_obj_union_map) &&
1347 !is_subtype(arg, isl_obj_union_set))
1348 isl_die(s->ctx, isl_error_invalid,
1349 "expecting set of map argument", goto error);
1350
1351 if (arg.type == isl_obj_list) {
1352 struct isl_list *list = arg.v;
1353 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1354 arg = obj_at(arg, 0);
1355 }
1356 if (arg.type == isl_obj_set)
1357 arg = convert(s->ctx, arg, isl_obj_union_set);
1358 else if (arg.type == isl_obj_map)
1359 arg = convert(s->ctx, arg, isl_obj_union_map);
1360 if (arg.type == isl_obj_union_set)
1361 obj = apply_fun_set(obj, arg.v);
1362 else
1363 obj = apply_fun_map(obj, arg.v);
1364 if (!obj.v)
1365 goto error2;
1366
1367 if (isl_stream_eat(s, ')'))
1368 goto error2;
1369
1370 return obj;
1371 error:
1372 free_obj(arg);
1373 error2:
1374 free_obj(obj);
1375 obj.type = isl_obj_none;
1376 obj.v = NULL;
1377 return obj;
1378 }
1379
1380 struct add_vertex_data {
1381 struct isl_list *list;
1382 int i;
1383 };
1384
1385 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
1386 {
1387 struct add_vertex_data *data = (struct add_vertex_data *)user;
1388 isl_basic_set *expr;
1389
1390 expr = isl_vertex_get_expr(vertex);
1391
1392 data->list->obj[data->i].type = isl_obj_set;
1393 data->list->obj[data->i].v = isl_set_from_basic_set(expr);
1394 data->i++;
1395
1396 isl_vertex_free(vertex);
1397
1398 return 0;
1399 }
1400
1401 static int set_vertices(__isl_take isl_set *set, void *user)
1402 {
1403 isl_ctx *ctx;
1404 isl_basic_set *hull;
1405 isl_vertices *vertices = NULL;
1406 struct isl_list *list = NULL;
1407 int r;
1408 struct add_vertex_data *data = (struct add_vertex_data *)user;
1409
1410 set = isl_set_remove_divs(set);
1411 hull = isl_set_convex_hull(set);
1412 vertices = isl_basic_set_compute_vertices(hull);
1413 isl_basic_set_free(hull);
1414
1415 list = data->list;
1416
1417 ctx = isl_vertices_get_ctx(vertices);
1418 data->list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1419 if (!data->list)
1420 goto error;
1421
1422 data->i = 0;
1423 r = isl_vertices_foreach_vertex(vertices, &add_vertex, user);
1424
1425 data->list = isl_list_concat(list, data->list);
1426
1427 isl_vertices_free(vertices);
1428
1429 return r;
1430 error:
1431 data->list = list;
1432 isl_vertices_free(vertices);
1433 return -1;
1434 }
1435
1436 static struct isl_obj vertices(struct isl_stream *s,
1437 struct isl_hash_table *table)
1438 {
1439 isl_ctx *ctx;
1440 struct isl_obj obj;
1441 struct isl_list *list = NULL;
1442 isl_union_set *uset;
1443 struct add_vertex_data data = { NULL };
1444
1445 obj = read_expr(s, table);
1446 obj = convert(s->ctx, obj, isl_obj_union_set);
1447 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1448 uset = obj.v;
1449 obj.v = NULL;
1450
1451 ctx = isl_union_set_get_ctx(uset);
1452 list = isl_list_alloc(ctx, 0);
1453 if (!list)
1454 goto error;
1455
1456 data.list = list;
1457
1458 if (isl_union_set_foreach_set(uset, &set_vertices, &data) < 0)
1459 goto error;
1460
1461 isl_union_set_free(uset);
1462
1463 obj.type = isl_obj_list;
1464 obj.v = data.list;
1465
1466 return obj;
1467 error:
1468 isl_union_set_free(uset);
1469 isl_list_free(data.list);
1470 free_obj(obj);
1471 obj.type = isl_obj_none;
1472 obj.v = NULL;
1473 return obj;
1474 }
1475
1476 static struct isl_obj type_of(struct isl_stream *s,
1477 struct isl_hash_table *table)
1478 {
1479 isl_ctx *ctx;
1480 struct isl_obj obj;
1481 const char *type = "unknown";
1482
1483 obj = read_expr(s, table);
1484
1485 if (obj.type == isl_obj_map ||
1486 obj.type == isl_obj_union_map)
1487 type = "map";
1488 if (obj.type == isl_obj_set ||
1489 obj.type == isl_obj_union_set)
1490 type = "set";
1491 if (obj.type == isl_obj_pw_qpolynomial ||
1492 obj.type == isl_obj_union_pw_qpolynomial)
1493 type = "piecewise quasipolynomial";
1494 if (obj.type == isl_obj_pw_qpolynomial_fold ||
1495 obj.type == isl_obj_union_pw_qpolynomial_fold)
1496 type = "piecewise quasipolynomial fold";
1497 if (obj.type == isl_obj_list)
1498 type = "list";
1499 if (obj.type == isl_obj_bool)
1500 type = "boolean";
1501 if (obj.type == isl_obj_str)
1502 type = "string";
1503 if (obj.type == isl_obj_val)
1504 type = "value";
1505
1506 free_obj(obj);
1507 obj.type = isl_obj_str;
1508 obj.v = isl_str_from_string(s->ctx, strdup(type));
1509
1510 return obj;
1511 }
1512
1513 static __isl_give isl_union_set *read_set(struct isl_stream *s,
1514 struct isl_hash_table *table)
1515 {
1516 struct isl_obj obj;
1517
1518 obj = read_obj(s, table);
1519 obj = convert(s->ctx, obj, isl_obj_union_set);
1520 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1521 return obj.v;
1522 error:
1523 free_obj(obj);
1524 return NULL;
1525 }
1526
1527 static __isl_give isl_union_map *read_map(struct isl_stream *s,
1528 struct isl_hash_table *table)
1529 {
1530 struct isl_obj obj;
1531
1532 obj = read_obj(s, table);
1533 obj = convert(s->ctx, obj, isl_obj_union_map);
1534 isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error);
1535 return obj.v;
1536 error:
1537 free_obj(obj);
1538 return NULL;
1539 }
1540
1541 static struct isl_obj last_any(struct isl_stream *s,
1542 struct isl_hash_table *table, __isl_take isl_union_map *must_source,
1543 __isl_take isl_union_map *may_source)
1544 {
1545 struct isl_obj obj = { isl_obj_none, NULL };
1546 isl_union_map *sink = NULL;
1547 isl_union_map *schedule = NULL;
1548 isl_union_map *may_dep;
1549 isl_union_map *must_dep;
1550
1551 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1552 goto error;
1553
1554 sink = read_map(s, table);
1555 if (!sink)
1556 goto error;
1557
1558 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1559 goto error;
1560
1561 schedule = read_map(s, table);
1562 if (!schedule)
1563 goto error;
1564
1565 if (isl_union_map_compute_flow(sink, must_source, may_source,
1566 schedule, &must_dep, &may_dep,
1567 NULL, NULL) < 0)
1568 return obj;
1569
1570 obj.type = isl_obj_union_map;
1571 obj.v = isl_union_map_union(must_dep, may_dep);
1572
1573 return obj;
1574 error:
1575 isl_union_map_free(may_source);
1576 isl_union_map_free(must_source);
1577 isl_union_map_free(sink);
1578 isl_union_map_free(schedule);
1579 free_obj(obj);
1580 obj.type = isl_obj_none;
1581 obj.v = NULL;
1582 return obj;
1583 }
1584
1585 static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table)
1586 {
1587 struct isl_obj obj = { isl_obj_none, NULL };
1588 isl_union_map *must_source = NULL;
1589 isl_union_map *may_source = NULL;
1590 isl_union_map *sink = NULL;
1591 isl_union_map *schedule = NULL;
1592 isl_union_map *may_dep;
1593
1594 may_source = read_map(s, table);
1595 if (!may_source)
1596 goto error;
1597
1598 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) {
1599 must_source = read_map(s, table);
1600 if (!must_source)
1601 goto error;
1602 return last_any(s, table, must_source, may_source);
1603 }
1604
1605 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1606 goto error;
1607
1608 sink = read_map(s, table);
1609 if (!sink)
1610 goto error;
1611
1612 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1613 goto error;
1614
1615 schedule = read_map(s, table);
1616 if (!schedule)
1617 goto error;
1618
1619 must_source = isl_union_map_empty(isl_union_map_get_space(sink));
1620 if (isl_union_map_compute_flow(sink, must_source, may_source,
1621 schedule, NULL, &may_dep,
1622 NULL, NULL) < 0)
1623 return obj;
1624
1625 obj.type = isl_obj_union_map;
1626 obj.v = may_dep;
1627
1628 return obj;
1629 error:
1630 isl_union_map_free(may_source);
1631 isl_union_map_free(must_source);
1632 isl_union_map_free(sink);
1633 isl_union_map_free(schedule);
1634 free_obj(obj);
1635 obj.type = isl_obj_none;
1636 obj.v = NULL;
1637 return obj;
1638 }
1639
1640 static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table)
1641 {
1642 struct isl_obj obj = { isl_obj_none, NULL };
1643 struct isl_list *list = NULL;
1644 isl_union_map *must_source = NULL;
1645 isl_union_map *may_source = NULL;
1646 isl_union_map *sink = NULL;
1647 isl_union_map *schedule = NULL;
1648 isl_union_map *must_dep;
1649 isl_union_map *must_no_source;
1650
1651 must_source = read_map(s, table);
1652 if (!must_source)
1653 goto error;
1654
1655 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) {
1656 may_source = read_map(s, table);
1657 if (!may_source)
1658 goto error;
1659 return last_any(s, table, must_source, may_source);
1660 }
1661
1662 list = isl_list_alloc(s->ctx, 2);
1663 if (!list)
1664 goto error;
1665
1666 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1667 goto error;
1668
1669 sink = read_map(s, table);
1670 if (!sink)
1671 goto error;
1672
1673 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1674 goto error;
1675
1676 schedule = read_map(s, table);
1677 if (!schedule)
1678 goto error;
1679
1680 may_source = isl_union_map_empty(isl_union_map_get_space(sink));
1681 if (isl_union_map_compute_flow(sink, must_source, may_source,
1682 schedule, &must_dep, NULL,
1683 &must_no_source, NULL) < 0) {
1684 isl_list_free(list);
1685 return obj;
1686 }
1687
1688 list->obj[0].type = isl_obj_union_map;
1689 list->obj[0].v = must_dep;
1690 list->obj[1].type = isl_obj_union_map;
1691 list->obj[1].v = must_no_source;
1692
1693 obj.v = list;
1694 obj.type = isl_obj_list;
1695
1696 return obj;
1697 error:
1698 isl_list_free(list);
1699 isl_union_map_free(may_source);
1700 isl_union_map_free(must_source);
1701 isl_union_map_free(sink);
1702 isl_union_map_free(schedule);
1703 free_obj(obj);
1704 obj.type = isl_obj_none;
1705 obj.v = NULL;
1706 return obj;
1707 }
1708
1709 static __isl_give isl_schedule *get_schedule(struct isl_stream *s,
1710 struct isl_hash_table *table)
1711 {
1712 isl_union_set *domain;
1713 isl_union_map *validity;
1714 isl_union_map *proximity;
1715
1716 domain = read_set(s, table);
1717 if (!domain)
1718 return NULL;
1719
1720 validity = isl_union_map_empty(isl_union_set_get_space(domain));
1721 proximity = isl_union_map_empty(isl_union_set_get_space(domain));
1722
1723 for (;;) {
1724 isl_union_map *umap;
1725 if (isl_stream_eat_if_available(s, iscc_op[ISCC_RESPECTING])) {
1726 umap = read_map(s, table);
1727 validity = isl_union_map_union(validity, umap);
1728 } else if (isl_stream_eat_if_available(s, iscc_op[ISCC_MINIMIZING])) {
1729 umap = read_map(s, table);
1730 proximity = isl_union_map_union(proximity, umap);
1731 } else
1732 break;
1733 }
1734
1735 return isl_union_set_compute_schedule(domain, validity, proximity);
1736 }
1737
1738 static struct isl_obj schedule(struct isl_stream *s,
1739 struct isl_hash_table *table)
1740 {
1741 struct isl_obj obj = { isl_obj_none, NULL };
1742 isl_schedule *schedule;
1743
1744 schedule = get_schedule(s, table);
1745
1746 obj.v = isl_schedule_get_map(schedule);
1747 obj.type = isl_obj_union_map;
1748
1749 isl_schedule_free(schedule);
1750
1751 return obj;
1752 }
1753
1754 /* Read a schedule for code generation.
1755 * If the input is a set rather than a map, then we construct
1756 * an identity schedule on the given set.
1757 */
1758 static __isl_give isl_union_map *get_codegen_schedule(struct isl_stream *s,
1759 struct isl_hash_table *table)
1760 {
1761 struct isl_obj obj;
1762
1763 obj = read_obj(s, table);
1764
1765 if (is_subtype(obj, isl_obj_union_map)) {
1766 obj = convert(s->ctx, obj, isl_obj_union_map);
1767 return obj.v;
1768 }
1769
1770 if (is_subtype(obj, isl_obj_union_set)) {
1771 obj = convert(s->ctx, obj, isl_obj_union_set);
1772 return isl_union_set_identity(obj.v);
1773 }
1774
1775 free_obj(obj);
1776 isl_die(s->ctx, isl_error_invalid, "expecting set or map", return NULL);
1777 }
1778
1779 /* Generate an AST for the given schedule and options and print
1780 * the AST on the printer.
1781 */
1782 static __isl_give isl_printer *print_code(__isl_take isl_printer *p,
1783 __isl_take isl_union_map *schedule,
1784 __isl_take isl_union_map *options)
1785 {
1786 isl_space *space;
1787 isl_set *context;
1788 isl_ast_build *build;
1789 isl_ast_node *tree;
1790 int format;
1791
1792 space = isl_union_map_get_space(schedule);
1793 context = isl_set_universe(isl_space_params(space));
1794
1795 build = isl_ast_build_from_context(context);
1796 build = isl_ast_build_set_options(build, options);
1797 tree = isl_ast_build_ast_from_schedule(build, schedule);
1798 isl_ast_build_free(build);
1799
1800 if (!tree)
1801 return p;
1802
1803 format = isl_printer_get_output_format(p);
1804 p = isl_printer_set_output_format(p, ISL_FORMAT_C);
1805 p = isl_printer_print_ast_node(p, tree);
1806 p = isl_printer_set_output_format(p, format);
1807
1808 isl_ast_node_free(tree);
1809
1810 return p;
1811 }
1812
1813 /* Perform the codegen operation.
1814 * In particular, read a schedule, check if the user has specified any options
1815 * and then generate an AST from the schedule (and options) and print it.
1816 */
1817 static __isl_give isl_printer *codegen(struct isl_stream *s,
1818 struct isl_hash_table *table, __isl_take isl_printer *p)
1819 {
1820 isl_union_map *schedule;
1821 isl_union_map *options;
1822
1823 schedule = get_codegen_schedule(s, table);
1824 if (!schedule)
1825 return p;
1826
1827 if (isl_stream_eat_if_available(s, iscc_op[ISCC_USING]))
1828 options = read_map(s, table);
1829 else
1830 options = isl_union_map_empty(
1831 isl_union_map_get_space(schedule));
1832
1833 p = print_code(p, schedule, options);
1834
1835 isl_stream_eat(s, ';');
1836
1837 return p;
1838 }
1839
1840 static struct isl_obj band_list_to_obj_list(__isl_take isl_band_list *bands);
1841
1842 static struct isl_obj band_to_obj_list(__isl_take isl_band *band)
1843 {
1844 struct isl_obj obj = { isl_obj_none, NULL };
1845 isl_ctx *ctx = isl_band_get_ctx(band);
1846 struct isl_list *list;
1847
1848 list = isl_list_alloc(ctx, 2);
1849 if (!list)
1850 goto error;
1851
1852 obj.v = list;
1853 obj.type = isl_obj_list;
1854
1855 list->obj[0].type = isl_obj_union_map;
1856 list->obj[0].v = isl_band_get_partial_schedule(band);
1857
1858 if (isl_band_has_children(band)) {
1859 isl_band_list *children;
1860
1861 children = isl_band_get_children(band);
1862 list->obj[1] = band_list_to_obj_list(children);
1863 } else {
1864 list->obj[1].type = isl_obj_list;
1865 list->obj[1].v = isl_list_alloc(ctx, 0);
1866 }
1867
1868 if (!list->obj[0].v || !list->obj[1].v)
1869 goto error;
1870
1871 isl_band_free(band);
1872
1873 return obj;
1874 error:
1875 isl_band_free(band);
1876 free_obj(obj);
1877 obj.type = isl_obj_none;
1878 obj.v = NULL;
1879 return obj;
1880 }
1881
1882 static struct isl_obj band_list_to_obj_list(__isl_take isl_band_list *bands)
1883 {
1884 struct isl_obj obj = { isl_obj_none, NULL };
1885 isl_ctx *ctx = isl_band_list_get_ctx(bands);
1886 struct isl_list *list;
1887 int i, n;
1888
1889 n = isl_band_list_n_band(bands);
1890 list = isl_list_alloc(ctx, n);
1891 if (!list)
1892 goto error;
1893
1894 obj.v = list;
1895 obj.type = isl_obj_list;
1896
1897 for (i = 0; i < n; ++i) {
1898 isl_band *band;
1899
1900 band = isl_band_list_get_band(bands, i);
1901 list->obj[i] = band_to_obj_list(band);
1902 if (!list->obj[i].v)
1903 goto error;
1904 }
1905
1906 isl_band_list_free(bands);
1907
1908 return obj;
1909 error:
1910 isl_band_list_free(bands);
1911 free_obj(obj);
1912 obj.type = isl_obj_none;
1913 obj.v = NULL;
1914 return obj;
1915 }
1916
1917 static struct isl_obj schedule_forest(struct isl_stream *s,
1918 struct isl_hash_table *table)
1919 {
1920 struct isl_obj obj = { isl_obj_none, NULL };
1921 isl_schedule *schedule;
1922 isl_band_list *roots;
1923
1924 schedule = get_schedule(s, table);
1925 if (!schedule)
1926 return obj;
1927
1928 roots = isl_schedule_get_band_forest(schedule);
1929 isl_schedule_free(schedule);
1930
1931 return band_list_to_obj_list(roots);
1932 }
1933
1934 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1935 {
1936 struct isl_token *tok;
1937 isl_val *v;
1938
1939 if (isl_stream_eat_if_available(s, '+'))
1940 return transitive_closure(s->ctx, obj);
1941
1942 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1943 if (obj.type != isl_obj_union_map)
1944 obj = convert(s->ctx, obj, isl_obj_union_map);
1945
1946 tok = isl_stream_next_token(s);
1947 if (!tok || isl_token_get_type(tok) != ISL_TOKEN_VALUE) {
1948 isl_stream_error(s, tok, "expecting integer exponent");
1949 if (tok)
1950 isl_stream_push_token(s, tok);
1951 goto error;
1952 }
1953
1954 v = isl_token_get_val(s->ctx, tok);
1955 if (isl_val_is_zero(v)) {
1956 isl_stream_error(s, tok, "expecting non-zero exponent");
1957 isl_val_free(v);
1958 if (tok)
1959 isl_stream_push_token(s, tok);
1960 goto error;
1961 }
1962
1963 obj.v = isl_union_map_fixed_power_val(obj.v, v);
1964 isl_token_free(tok);
1965 if (!obj.v)
1966 goto error;
1967
1968 return obj;
1969 error:
1970 free_obj(obj);
1971 obj.type = isl_obj_none;
1972 obj.v = NULL;
1973 return obj;
1974 }
1975
1976 static struct isl_obj check_assert(struct isl_stream *s,
1977 struct isl_hash_table *table)
1978 {
1979 struct isl_obj obj;
1980
1981 obj = read_expr(s, table);
1982 if (obj.type != isl_obj_bool)
1983 isl_die(s->ctx, isl_error_invalid,
1984 "expecting boolean expression", goto error);
1985 if (obj.v != &isl_bool_true)
1986 isl_die(s->ctx, isl_error_unknown,
1987 "assertion failed", abort());
1988 error:
1989 free_obj(obj);
1990 obj.type = isl_obj_none;
1991 obj.v = NULL;
1992 return obj;
1993 }
1994
1995 static struct isl_obj read_from_file(struct isl_stream *s)
1996 {
1997 struct isl_obj obj;
1998 struct isl_token *tok;
1999 struct isl_stream *s_file;
2000 struct iscc_options *options;
2001 char *name;
2002 FILE *file;
2003
2004 tok = isl_stream_next_token(s);
2005 if (!tok || isl_token_get_type(tok) != ISL_TOKEN_STRING) {
2006 isl_stream_error(s, tok, "expecting filename");
2007 isl_token_free(tok);
2008 goto error;
2009 }
2010
2011 options = isl_ctx_peek_iscc_options(s->ctx);
2012 if (!options || !options->io) {
2013 isl_token_free(tok);
2014 isl_die(s->ctx, isl_error_invalid,
2015 "read operation not allowed", goto error);
2016 }
2017
2018 name = isl_token_get_str(s->ctx, tok);
2019 isl_token_free(tok);
2020 file = fopen(name, "r");
2021 free(name);
2022 isl_assert(s->ctx, file, goto error);
2023
2024 s_file = isl_stream_new_file(s->ctx, file);
2025 if (!s_file) {
2026 fclose(file);
2027 goto error;
2028 }
2029
2030 obj = isl_stream_read_obj(s_file);
2031
2032 isl_stream_free(s_file);
2033 fclose(file);
2034
2035 return obj;
2036 error:
2037 obj.type = isl_obj_none;
2038 obj.v = NULL;
2039 return obj;
2040 }
2041
2042 static struct isl_obj write_to_file(struct isl_stream *s,
2043 struct isl_hash_table *table)
2044 {
2045 struct isl_obj obj;
2046 struct isl_token *tok;
2047 struct isl_stream *s_file;
2048 struct iscc_options *options;
2049 char *name;
2050 FILE *file;
2051 isl_printer *p;
2052
2053 tok = isl_stream_next_token(s);
2054 if (!tok || isl_token_get_type(tok) != ISL_TOKEN_STRING) {
2055 isl_stream_error(s, tok, "expecting filename");
2056 isl_token_free(tok);
2057 goto error;
2058 }
2059
2060 obj = read_expr(s, table);
2061
2062 options = isl_ctx_peek_iscc_options(s->ctx);
2063 if (!options || !options->io) {
2064 isl_token_free(tok);
2065 isl_die(s->ctx, isl_error_invalid,
2066 "write operation not allowed", goto error);
2067 }
2068
2069 name = isl_token_get_str(s->ctx, tok);
2070 isl_token_free(tok);
2071 file = fopen(name, "w");
2072 free(name);
2073 if (!file)
2074 isl_die(s->ctx, isl_error_unknown,
2075 "could not open file for writing", goto error);
2076
2077 p = isl_printer_to_file(s->ctx, file);
2078 p = isl_printer_set_output_format(p, options->format);
2079 p = obj.type->print(p, obj.v);
2080 p = isl_printer_end_line(p);
2081 isl_printer_free(p);
2082
2083 fclose(file);
2084 error:
2085 free_obj(obj);
2086 obj.type = isl_obj_none;
2087 obj.v = NULL;
2088 return obj;
2089 }
2090
2091 static struct isl_obj read_string_if_available(struct isl_stream *s)
2092 {
2093 struct isl_token *tok;
2094 struct isl_obj obj = { isl_obj_none, NULL };
2095
2096 tok = isl_stream_next_token(s);
2097 if (!tok)
2098 return obj;
2099 if (isl_token_get_type(tok) == ISL_TOKEN_STRING) {
2100 isl_str *str;
2101 str = isl_str_alloc(s->ctx);
2102 if (!str)
2103 goto error;
2104 str->s = isl_token_get_str(s->ctx, tok);
2105 isl_token_free(tok);
2106 obj.v = str;
2107 obj.type = isl_obj_str;
2108 } else
2109 isl_stream_push_token(s, tok);
2110 return obj;
2111 error:
2112 isl_token_free(tok);
2113 return obj;
2114 }
2115
2116 static struct isl_obj read_bool_if_available(struct isl_stream *s)
2117 {
2118 struct isl_token *tok;
2119 struct isl_obj obj = { isl_obj_none, NULL };
2120 int type;
2121
2122 tok = isl_stream_next_token(s);
2123 if (!tok)
2124 return obj;
2125 type = isl_token_get_type(tok);
2126 if (type == ISL_TOKEN_FALSE || type == ISL_TOKEN_TRUE) {
2127 int is_true = type == ISL_TOKEN_TRUE;
2128 isl_token_free(tok);
2129 obj.v = is_true ? &isl_bool_true : &isl_bool_false;
2130 obj.type = isl_obj_bool;
2131 } else
2132 isl_stream_push_token(s, tok);
2133 return obj;
2134 }
2135
2136 static __isl_give char *read_ident(struct isl_stream *s)
2137 {
2138 char *name;
2139 isl_val *v;
2140 struct isl_token *tok, *tok2;
2141
2142 name = isl_stream_read_ident_if_available(s);
2143 if (name)
2144 return name;
2145
2146 tok = isl_stream_next_token(s);
2147 if (!tok)
2148 return NULL;
2149 if (isl_token_get_type(tok) != '$') {
2150 isl_stream_push_token(s, tok);
2151 return NULL;
2152 }
2153 tok2 = isl_stream_next_token(s);
2154 if (!tok2 || isl_token_get_type(tok2) != ISL_TOKEN_VALUE) {
2155 if (tok2)
2156 isl_stream_push_token(s, tok2);
2157 isl_stream_push_token(s, tok);
2158 return NULL;
2159 }
2160
2161 v = isl_token_get_val(s->ctx, tok2);
2162 name = isl_val_to_str(v);
2163 isl_val_free(v);
2164 isl_token_free(tok);
2165 isl_token_free(tok2);
2166
2167 return name;
2168 }
2169
2170 static struct isl_obj read_list(struct isl_stream *s,
2171 struct isl_hash_table *table, struct isl_obj obj)
2172 {
2173 struct isl_list *list;
2174
2175 list = isl_list_alloc(s->ctx, 2);
2176 if (!list)
2177 goto error;
2178 list->obj[0] = obj;
2179 list->obj[1] = read_obj(s, table);
2180 obj.v = list;
2181 obj.type = isl_obj_list;
2182
2183 if (!list->obj[1].v)
2184 goto error;
2185
2186 while (isl_stream_eat_if_available(s, ',')) {
2187 obj.v = list = isl_list_add_obj(list, read_obj(s, table));
2188 if (!obj.v)
2189 goto error;
2190 }
2191
2192 return obj;
2193 error:
2194 free_obj(obj);
2195 obj.type = isl_obj_none;
2196 obj.v = NULL;
2197 return obj;
2198 }
2199
2200 static struct isl_obj read_obj(struct isl_stream *s,
2201 struct isl_hash_table *table)
2202 {
2203 struct isl_obj obj = { isl_obj_none, NULL };
2204 char *name = NULL;
2205 struct isc_un_op *op = NULL;
2206
2207 obj = read_string_if_available(s);
2208 if (obj.v)
2209 return obj;
2210 obj = read_bool_if_available(s);
2211 if (obj.v)
2212 return obj;
2213 if (isl_stream_eat_if_available(s, '(')) {
2214 if (isl_stream_next_token_is(s, ')')) {
2215 obj.type = isl_obj_list;
2216 obj.v = isl_list_alloc(s->ctx, 0);
2217 } else {
2218 obj = read_expr(s, table);
2219 if (obj.v && isl_stream_eat_if_available(s, ','))
2220 obj = read_list(s, table, obj);
2221 }
2222 if (!obj.v || isl_stream_eat(s, ')'))
2223 goto error;
2224 } else {
2225 op = read_prefix_un_op_if_available(s);
2226 if (op)
2227 return read_un_op_expr(s, table, op);
2228
2229 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ASSERT]))
2230 return check_assert(s, table);
2231 if (isl_stream_eat_if_available(s, iscc_op[ISCC_READ]))
2232 return read_from_file(s);
2233 if (isl_stream_eat_if_available(s, iscc_op[ISCC_WRITE]))
2234 return write_to_file(s, table);
2235 if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES]))
2236 return vertices(s, table);
2237 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY]))
2238 return any(s, table);
2239 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST]))
2240 return last(s, table);
2241 if (isl_stream_eat_if_available(s, iscc_op[ISCC_SCHEDULE]))
2242 return schedule(s, table);
2243 if (isl_stream_eat_if_available(s, iscc_op[ISCC_SCHEDULE_FOREST]))
2244 return schedule_forest(s, table);
2245 if (isl_stream_eat_if_available(s, iscc_op[ISCC_TYPEOF]))
2246 return type_of(s, table);
2247
2248 name = read_ident(s);
2249 if (name)
2250 obj = stored_obj(s->ctx, table, name);
2251 else
2252 obj = isl_stream_read_obj(s);
2253 if (!obj.v)
2254 goto error;
2255 }
2256
2257 if (isl_stream_eat_if_available(s, '^'))
2258 obj = power(s, obj);
2259 else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
2260 obj = obj_at_index(s, obj);
2261 else if (is_subtype(obj, isl_obj_union_map) &&
2262 isl_stream_eat_if_available(s, '(')) {
2263 obj = convert(s->ctx, obj, isl_obj_union_map);
2264 obj = apply(s, obj.v, table);
2265 } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial) &&
2266 isl_stream_eat_if_available(s, '(')) {
2267 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial);
2268 obj = apply_fun(s, obj, table);
2269 } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial_fold) &&
2270 isl_stream_eat_if_available(s, '(')) {
2271 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial_fold);
2272 obj = apply_fun(s, obj, table);
2273 }
2274
2275 return obj;
2276 error:
2277 free_obj(obj);
2278 obj.type = isl_obj_none;
2279 obj.v = NULL;
2280 return obj;
2281 }
2282
2283 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
2284 struct isl_obj lhs, struct isl_obj rhs)
2285 {
2286 int i;
2287
2288 for (i = 0; ; ++i) {
2289 if (!bin_ops[i].op)
2290 break;
2291 if (bin_ops[i].op != like->op)
2292 continue;
2293 if (!is_subtype(lhs, bin_ops[i].lhs))
2294 continue;
2295 if (!is_subtype(rhs, bin_ops[i].rhs))
2296 continue;
2297
2298 return &bin_ops[i];
2299 }
2300
2301 for (i = 0; ; ++i) {
2302 if (!named_bin_ops[i].name)
2303 break;
2304 if (named_bin_ops[i].op.op != like->op)
2305 continue;
2306 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
2307 continue;
2308 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
2309 continue;
2310
2311 return &named_bin_ops[i].op;
2312 }
2313
2314 return NULL;
2315 }
2316
2317 static int next_is_neg_int(struct isl_stream *s)
2318 {
2319 struct isl_token *tok;
2320 int ret;
2321
2322 tok = isl_stream_next_token(s);
2323 if (tok && isl_token_get_type(tok) == ISL_TOKEN_VALUE) {
2324 isl_val *v;
2325 v = isl_token_get_val(s->ctx, tok);
2326 ret = isl_val_is_neg(v);
2327 isl_val_free(v);
2328 } else
2329 ret = 0;
2330 isl_stream_push_token(s, tok);
2331
2332 return ret;
2333 }
2334
2335 static struct isl_obj call_bin_op(isl_ctx *ctx, struct isc_bin_op *op,
2336 struct isl_obj lhs, struct isl_obj rhs)
2337 {
2338 struct isl_obj obj;
2339
2340 lhs = convert(ctx, lhs, op->lhs);
2341 rhs = convert(ctx, rhs, op->rhs);
2342 if (op->res != isl_obj_bool)
2343 obj.v = op->o.fn(lhs.v, rhs.v);
2344 else {
2345 int res = op->o.test(lhs.v, rhs.v);
2346 free_obj(lhs);
2347 free_obj(rhs);
2348 obj.v = isl_bool_from_int(res);
2349 }
2350 obj.type = op->res;
2351
2352 return obj;
2353 }
2354
2355 static struct isl_obj read_expr(struct isl_stream *s,
2356 struct isl_hash_table *table)
2357 {
2358 struct isl_obj obj = { isl_obj_none, NULL };
2359 struct isl_obj right_obj = { isl_obj_none, NULL };
2360
2361 obj = read_obj(s, table);
2362 for (; obj.v;) {
2363 struct isc_bin_op *op = NULL;
2364
2365 op = read_bin_op_if_available(s, obj);
2366 if (!op)
2367 break;
2368
2369 right_obj = read_obj(s, table);
2370
2371 op = find_matching_bin_op(op, obj, right_obj);
2372
2373 if (!op)
2374 isl_die(s->ctx, isl_error_invalid,
2375 "no such binary operator defined on given operands",
2376 goto error);
2377
2378 obj = call_bin_op(s->ctx, op, obj, right_obj);
2379 }
2380
2381 if (obj.type == isl_obj_val && next_is_neg_int(s)) {
2382 right_obj = read_obj(s, table);
2383 obj.v = isl_val_add(obj.v, right_obj.v);
2384 }
2385
2386 return obj;
2387 error:
2388 free_obj(right_obj);
2389 free_obj(obj);
2390 obj.type = isl_obj_none;
2391 obj.v = NULL;
2392 return obj;
2393 }
2394
2395 static __isl_give isl_printer *source_file(struct isl_stream *s,
2396 struct isl_hash_table *table, __isl_take isl_printer *p);
2397
2398 static __isl_give isl_printer *read_line(struct isl_stream *s,
2399 struct isl_hash_table *table, __isl_take isl_printer *p, int tty)
2400 {
2401 struct isl_obj obj = { isl_obj_none, NULL };
2402 char *lhs = NULL;
2403 int assign = 0;
2404 int only_print = 0;
2405 struct isc_bin_op *op = NULL;
2406 char buf[30];
2407
2408 if (!p)
2409 return NULL;
2410 if (isl_stream_is_empty(s))
2411 return p;
2412
2413 if (isl_stream_eat_if_available(s, iscc_op[ISCC_SOURCE]))
2414 return source_file(s, table, p);
2415 if (isl_stream_eat_if_available(s, iscc_op[ISCC_CODEGEN]))
2416 return codegen(s, table, p);
2417
2418 assign = is_assign(s);
2419 if (assign) {
2420 lhs = isl_stream_read_ident_if_available(s);
2421 if (isl_stream_eat(s, ISL_TOKEN_DEF))
2422 goto error;
2423 } else if (isl_stream_eat_if_available(s, iscc_op[ISCC_PRINT]))
2424 only_print = 1;
2425 else if (!tty)
2426 only_print = 1;
2427
2428 obj = read_expr(s, table);
2429 if (isl_ctx_last_error(s->ctx) == isl_error_abort) {
2430 fprintf(stderr, "Interrupted\n");
2431 isl_ctx_reset_error(s->ctx);
2432 }
2433 if (isl_stream_eat(s, ';'))
2434 goto error;
2435
2436 if (only_print) {
2437 if (obj.type != isl_obj_none && obj.v != NULL) {
2438 p = obj.type->print(p, obj.v);
2439 p = isl_printer_end_line(p);
2440 }
2441 free_obj(obj);
2442 return p;
2443 }
2444 if (!assign && obj.type != isl_obj_none && obj.v != NULL) {
2445 static int count = 0;
2446 snprintf(buf, sizeof(buf), "$%d", count++);
2447 lhs = strdup(buf + 1);
2448
2449 p = isl_printer_print_str(p, buf);
2450 p = isl_printer_print_str(p, " := ");
2451 p = obj.type->print(p, obj.v);
2452 p = isl_printer_end_line(p);
2453 }
2454 if (lhs && do_assign(s->ctx, table, lhs, obj))
2455 return p;
2456
2457 return p;
2458 error:
2459 isl_stream_flush_tokens(s);
2460 isl_stream_skip_line(s);
2461 free(lhs);
2462 free_obj(obj);
2463 return p;
2464 }
2465
2466 int free_cb(void **entry, void *user)
2467 {
2468 struct isl_named_obj *named = *entry;
2469
2470 free_obj(named->obj);
2471 free(named->name);
2472 free(named);
2473
2474 return 0;
2475 }
2476
2477 static void register_named_ops(struct isl_stream *s)
2478 {
2479 int i;
2480
2481 for (i = 0; i < ISCC_N_OP; ++i) {
2482 iscc_op[i] = isl_stream_register_keyword(s, op_name[i]);
2483 assert(iscc_op[i] != ISL_TOKEN_ERROR);
2484 }
2485
2486 for (i = 0; ; ++i) {
2487 if (!named_un_ops[i].name)
2488 break;
2489 named_un_ops[i].op.op = isl_stream_register_keyword(s,
2490 named_un_ops[i].name);
2491 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
2492 }
2493
2494 for (i = 0; ; ++i) {
2495 if (!named_bin_ops[i].name)
2496 break;
2497 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
2498 named_bin_ops[i].name);
2499 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
2500 }
2501 }
2502
2503 static __isl_give isl_printer *source_file(struct isl_stream *s,
2504 struct isl_hash_table *table, __isl_take isl_printer *p)
2505 {
2506 struct isl_token *tok;
2507 struct isl_stream *s_file;
2508 char *name;
2509 FILE *file;
2510
2511 tok = isl_stream_next_token(s);
2512 if (!tok || isl_token_get_type(tok) != ISL_TOKEN_STRING) {
2513 isl_stream_error(s, tok, "expecting filename");
2514 isl_token_free(tok);
2515 return p;
2516 }
2517
2518 name = isl_token_get_str(s->ctx, tok);
2519 isl_token_free(tok);
2520 file = fopen(name, "r");
2521 free(name);
2522 isl_assert(s->ctx, file, return p);
2523
2524 s_file = isl_stream_new_file(s->ctx, file);
2525 if (!s_file) {
2526 fclose(file);
2527 return p;
2528 }
2529
2530 register_named_ops(s_file);
2531
2532 while (!s_file->eof)
2533 p = read_line(s_file, table, p, 0);
2534
2535 isl_stream_free(s_file);
2536 fclose(file);
2537
2538 isl_stream_eat(s, ';');
2539
2540 return p;
2541 }
2542
2543 int main(int argc, char **argv)
2544 {
2545 struct isl_ctx *ctx;
2546 struct isl_stream *s;
2547 struct isl_hash_table *table;
2548 struct iscc_options *options;
2549 isl_printer *p;
2550 int tty = isatty(0);
2551
2552 options = iscc_options_new_with_defaults();
2553 assert(options);
2554
2555 ctx = isl_ctx_alloc_with_options(&iscc_options_args, options);
2556 pet_options_set_autodetect(ctx, 1);
2557 argc = isl_ctx_parse_options(ctx, argc, argv, ISL_ARG_ALL);
2558 s = isl_stream_new_file(ctx, stdin);
2559 assert(s);
2560 table = isl_hash_table_alloc(ctx, 10);
2561 assert(table);
2562 p = isl_printer_to_file(ctx, stdout);
2563 p = isl_printer_set_output_format(p, options->format);
2564 assert(p);
2565
2566 register_named_ops(s);
2567
2568 install_signal_handler(ctx);
2569
2570 while (p && !s->eof) {
2571 isl_ctx_resume(ctx);
2572 p = read_line(s, table, p, tty);
2573 }
2574
2575 remove_signal_handler(ctx);
2576
2577 isl_printer_free(p);
2578 isl_hash_table_foreach(ctx, table, free_cb, NULL);
2579 isl_hash_table_free(ctx, table);
2580 isl_stream_free(s);
2581 isl_ctx_free(ctx);
2582
2583 return 0;
2584 }
lattice point enumeration library