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