?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
evalue_floor2frac: don't assume coefficients of floors are floors
[barvinok.git] / iscc.c
blob2d68062fc9f4562cc8c03e101f6b46b98461f055
1 #include <assert.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <isl_obj.h>
5 #include <isl_stream.h>
6 #include <isl_vertices.h>
7 #include <isl_obj_list.h>
8 #include <isl_obj_str.h>
9 #include <barvinok/barvinok.h>
10
11 #include "config.h"
12
13 #ifdef HAVE_CLOOG
14 #include <cloog/isl/cloog.h>
15 #endif
16
17 static int isl_bool_false = 0;
18 static int isl_bool_true = 1;
19 static int isl_bool_error = -1;
20
21 enum iscc_op { ISCC_READ, ISCC_SOURCE, ISCC_VERTICES,
22 ISCC_LAST, ISCC_ANY, ISCC_BEFORE, ISCC_UNDER, ISCC_N_OP };
23 static const char *op_name[ISCC_N_OP] = {
24 "read", "source", "vertices", "last", "any", "before", "under" };
25 static enum isl_token_type iscc_op[ISCC_N_OP];
26
27 struct isl_arg_choice iscc_format[] = {
28 {"isl", ISL_FORMAT_ISL},
29 {"omega", ISL_FORMAT_OMEGA},
30 {"polylib", ISL_FORMAT_POLYLIB},
31 {"ext-polylib", ISL_FORMAT_EXT_POLYLIB},
32 {"latex", ISL_FORMAT_LATEX},
33 {"C", ISL_FORMAT_C},
34 {0}
35 };
36
37 struct iscc_options {
38 struct barvinok_options *barvinok;
39 unsigned format;
40 };
41
42 struct isl_arg iscc_options_arg[] = {
43 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
44 "barvinok options")
45 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
46 iscc_format, ISL_FORMAT_ISL, "output format")
47 ISL_ARG_END
48 };
49
50 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)
51
52 static void *isl_obj_bool_copy(void *v)
53 {
54 return v;
55 }
56
57 static void isl_obj_bool_free(void *v)
58 {
59 }
60
61 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
62 void *v)
63 {
64 if (v == &isl_bool_true)
65 return isl_printer_print_str(p, "True");
66 else if (v == &isl_bool_false)
67 return isl_printer_print_str(p, "False");
68 else
69 return isl_printer_print_str(p, "Error");
70 }
71
72 static void *isl_obj_bool_add(void *v1, void *v2)
73 {
74 return v1;
75 }
76
77 struct isl_obj_vtable isl_obj_bool_vtable = {
78 isl_obj_bool_copy,
79 isl_obj_bool_add,
80 isl_obj_bool_print,
81 isl_obj_bool_free
82 };
83 #define isl_obj_bool (&isl_obj_bool_vtable)
84
85 int *isl_bool_from_int(int res)
86 {
87 return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
88 }
89
90 int *union_map_is_equal(__isl_take isl_union_map *map1,
91 __isl_take isl_union_map *map2)
92 {
93 int res = isl_union_map_is_equal(map1, map2);
94 isl_union_map_free(map1);
95 isl_union_map_free(map2);
96 return isl_bool_from_int(res);
97 }
98 int *union_set_is_equal(__isl_take isl_union_set *set1,
99 __isl_take isl_union_set *set2)
100 {
101 return union_map_is_equal((isl_union_map *)set1, (isl_union_map *)set2);
102 }
103
104 int *union_map_is_subset(__isl_take isl_union_map *map1,
105 __isl_take isl_union_map *map2)
106 {
107 int res = isl_union_map_is_subset(map1, map2);
108 isl_union_map_free(map1);
109 isl_union_map_free(map2);
110 return isl_bool_from_int(res);
111 }
112 int *union_set_is_subset(__isl_take isl_union_set *set1,
113 __isl_take isl_union_set *set2)
114 {
115 return union_map_is_subset((isl_union_map *)set1, (isl_union_map *)set2);
116 }
117
118 int *union_map_is_strict_subset(__isl_take isl_union_map *map1,
119 __isl_take isl_union_map *map2)
120 {
121 int res = isl_union_map_is_strict_subset(map1, map2);
122 isl_union_map_free(map1);
123 isl_union_map_free(map2);
124 return isl_bool_from_int(res);
125 }
126 int *union_set_is_strict_subset(__isl_take isl_union_set *set1,
127 __isl_take isl_union_set *set2)
128 {
129 return union_map_is_strict_subset((isl_union_map *)set1,
130 (isl_union_map *)set2);
131 }
132
133 int *union_map_is_superset(__isl_take isl_union_map *map1,
134 __isl_take isl_union_map *map2)
135 {
136 return union_map_is_subset(map2, map1);
137 }
138 int *union_set_is_superset(__isl_take isl_union_set *set1,
139 __isl_take isl_union_set *set2)
140 {
141 return union_set_is_subset(set2, set1);
142 }
143
144 int *union_map_is_strict_superset(__isl_take isl_union_map *map1,
145 __isl_take isl_union_map *map2)
146 {
147 return union_map_is_strict_subset(map2, map1);
148 }
149 int *union_set_is_strict_superset(__isl_take isl_union_set *set1,
150 __isl_take isl_union_set *set2)
151 {
152 return union_set_is_strict_subset(set2, set1);
153 }
154
155 extern struct isl_obj_vtable isl_obj_list_vtable;
156 #define isl_obj_list (&isl_obj_list_vtable)
157
158 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
159 struct isc_bin_op {
160 enum isl_token_type op;
161 isl_obj_type lhs;
162 isl_obj_type rhs;
163 isl_obj_type res;
164 isc_bin_op_fn fn;
165 };
166 struct isc_named_bin_op {
167 char *name;
168 struct isc_bin_op op;
169 };
170
171 struct iscc_at {
172 isl_union_pw_qpolynomial *upwqp;
173 isl_union_pw_qpolynomial *res;
174 };
175
176 static int eval_at(__isl_take isl_point *pnt, void *user)
177 {
178 struct iscc_at *at = (struct iscc_at *) user;
179 isl_qpolynomial *qp;
180 isl_set *set;
181
182 set = isl_set_from_point(isl_point_copy(pnt));
183 qp = isl_union_pw_qpolynomial_eval(
184 isl_union_pw_qpolynomial_copy(at->upwqp), pnt);
185
186 at->res = isl_union_pw_qpolynomial_add(at->res,
187 isl_union_pw_qpolynomial_from_pw_qpolynomial(
188 isl_pw_qpolynomial_alloc(set, qp)));
189
190 return 0;
191 }
192
193 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
194 __isl_take isl_union_pw_qpolynomial *upwqp,
195 __isl_take isl_union_set *uset)
196 {
197 struct iscc_at at;
198
199 at.upwqp = upwqp;
200 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
201
202 isl_union_set_foreach_point(uset, eval_at, &at);
203
204 isl_union_pw_qpolynomial_free(upwqp);
205 isl_union_set_free(uset);
206
207 return at.res;
208 }
209
210 struct iscc_fold_at {
211 isl_union_pw_qpolynomial_fold *upwf;
212 isl_union_pw_qpolynomial *res;
213 };
214
215 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
216 {
217 struct iscc_fold_at *at = (struct iscc_fold_at *) user;
218 isl_qpolynomial *qp;
219 isl_set *set;
220
221 set = isl_set_from_point(isl_point_copy(pnt));
222 qp = isl_union_pw_qpolynomial_fold_eval(
223 isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);
224
225 at->res = isl_union_pw_qpolynomial_add(at->res,
226 isl_union_pw_qpolynomial_from_pw_qpolynomial(
227 isl_pw_qpolynomial_alloc(set, qp)));
228
229 return 0;
230 }
231
232 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
233 __isl_take isl_union_pw_qpolynomial_fold *upwf,
234 __isl_take isl_union_set *uset)
235 {
236 struct iscc_fold_at at;
237
238 at.upwf = upwf;
239 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
240
241 isl_union_set_foreach_point(uset, eval_fold_at, &at);
242
243 isl_union_pw_qpolynomial_fold_free(upwf);
244 isl_union_set_free(uset);
245
246 return at.res;
247 }
248
249 static __isl_give isl_union_pw_qpolynomial_fold *union_pw_qpolynomial_add_union_pw_qpolynomial_fold(
250 __isl_take isl_union_pw_qpolynomial *upwqp,
251 __isl_take isl_union_pw_qpolynomial_fold *upwf)
252 {
253 return isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(upwf,
254 upwqp);
255 }
256
257 static __isl_give struct isl_list *union_map_apply_union_pw_qpolynomial_fold(
258 __isl_take isl_union_map *umap,
259 __isl_take isl_union_pw_qpolynomial_fold *upwf)
260 {
261 isl_ctx *ctx;
262 struct isl_list *list;
263 int tight;
264
265 ctx = isl_union_map_get_ctx(umap);
266 list = isl_list_alloc(ctx, 2);
267 if (!list)
268 goto error2;
269
270 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
271 list->obj[0].v = isl_union_map_apply_union_pw_qpolynomial_fold(umap,
272 upwf, &tight);
273 list->obj[1].type = isl_obj_bool;
274 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
275 if (tight < 0 || !list->obj[0].v)
276 goto error;
277
278 return list;
279 error2:
280 isl_union_map_free(umap);
281 isl_union_pw_qpolynomial_fold_free(upwf);
282 error:
283 isl_list_free(list);
284 return NULL;
285 }
286
287 struct isc_bin_op bin_ops[] = {
288 { '+', isl_obj_union_set, isl_obj_union_set,
289 isl_obj_union_set,
290 (isc_bin_op_fn) &isl_union_set_union },
291 { '+', isl_obj_union_map, isl_obj_union_map,
292 isl_obj_union_map,
293 (isc_bin_op_fn) &isl_union_map_union },
294 { '-', isl_obj_union_set, isl_obj_union_set,
295 isl_obj_union_set,
296 (isc_bin_op_fn) &isl_union_set_subtract },
297 { '-', isl_obj_union_map, isl_obj_union_map,
298 isl_obj_union_map,
299 (isc_bin_op_fn) &isl_union_map_subtract },
300 { '*', isl_obj_union_set, isl_obj_union_set,
301 isl_obj_union_set,
302 (isc_bin_op_fn) &isl_union_set_intersect },
303 { '*', isl_obj_union_map, isl_obj_union_map,
304 isl_obj_union_map,
305 (isc_bin_op_fn) &isl_union_map_intersect },
306 { '*', isl_obj_union_map, isl_obj_union_set,
307 isl_obj_union_map,
308 (isc_bin_op_fn) &isl_union_map_intersect_domain },
309 { '.', isl_obj_union_map, isl_obj_union_map,
310 isl_obj_union_map,
311 (isc_bin_op_fn) &isl_union_map_apply_range },
312 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial,
313 isl_obj_union_pw_qpolynomial,
314 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
315 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial_fold,
316 isl_obj_list,
317 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold },
318 { ISL_TOKEN_TO, isl_obj_union_set, isl_obj_union_set,
319 isl_obj_union_map,
320 (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
321 { '=', isl_obj_union_set, isl_obj_union_set, isl_obj_bool,
322 (isc_bin_op_fn) &union_set_is_equal },
323 { '=', isl_obj_union_map, isl_obj_union_map, isl_obj_bool,
324 (isc_bin_op_fn) &union_map_is_equal },
325 { ISL_TOKEN_LE, isl_obj_union_set, isl_obj_union_set,
326 isl_obj_bool, (isc_bin_op_fn) &union_set_is_subset },
327 { ISL_TOKEN_LE, isl_obj_union_map, isl_obj_union_map,
328 isl_obj_bool, (isc_bin_op_fn) &union_map_is_subset },
329 { ISL_TOKEN_LT, isl_obj_union_set, isl_obj_union_set,
330 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_subset },
331 { ISL_TOKEN_LT, isl_obj_union_map, isl_obj_union_map,
332 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_subset },
333 { ISL_TOKEN_GE, isl_obj_union_set, isl_obj_union_set,
334 isl_obj_bool, (isc_bin_op_fn) &union_set_is_superset },
335 { ISL_TOKEN_GE, isl_obj_union_map, isl_obj_union_map,
336 isl_obj_bool, (isc_bin_op_fn) &union_map_is_superset },
337 { ISL_TOKEN_GT, isl_obj_union_set, isl_obj_union_set,
338 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_superset },
339 { ISL_TOKEN_GT, isl_obj_union_map, isl_obj_union_map,
340 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_superset },
341 { ISL_TOKEN_LEX_LE, isl_obj_union_set, isl_obj_union_set,
342 isl_obj_union_map,
343 (isc_bin_op_fn) &isl_union_set_lex_le_union_set },
344 { ISL_TOKEN_LEX_LT, isl_obj_union_set, isl_obj_union_set,
345 isl_obj_union_map,
346 (isc_bin_op_fn) &isl_union_set_lex_lt_union_set },
347 { ISL_TOKEN_LEX_GE, isl_obj_union_set, isl_obj_union_set,
348 isl_obj_union_map,
349 (isc_bin_op_fn) &isl_union_set_lex_ge_union_set },
350 { ISL_TOKEN_LEX_GT, isl_obj_union_set, isl_obj_union_set,
351 isl_obj_union_map,
352 (isc_bin_op_fn) &isl_union_set_lex_gt_union_set },
353 { ISL_TOKEN_LEX_LE, isl_obj_union_map, isl_obj_union_map,
354 isl_obj_union_map,
355 (isc_bin_op_fn) &isl_union_map_lex_le_union_map },
356 { ISL_TOKEN_LEX_LT, isl_obj_union_map, isl_obj_union_map,
357 isl_obj_union_map,
358 (isc_bin_op_fn) &isl_union_map_lex_lt_union_map },
359 { ISL_TOKEN_LEX_GE, isl_obj_union_map, isl_obj_union_map,
360 isl_obj_union_map,
361 (isc_bin_op_fn) &isl_union_map_lex_ge_union_map },
362 { ISL_TOKEN_LEX_GT, isl_obj_union_map, isl_obj_union_map,
363 isl_obj_union_map,
364 (isc_bin_op_fn) &isl_union_map_lex_gt_union_map },
365 { '.', isl_obj_union_pw_qpolynomial_fold,
366 isl_obj_union_pw_qpolynomial_fold,
367 isl_obj_union_pw_qpolynomial_fold,
368 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_fold },
369 { '+', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
370 isl_obj_union_pw_qpolynomial,
371 (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
372 { '+', isl_obj_union_pw_qpolynomial,
373 isl_obj_union_pw_qpolynomial_fold,
374 isl_obj_union_pw_qpolynomial_fold,
375 (isc_bin_op_fn) &union_pw_qpolynomial_add_union_pw_qpolynomial_fold },
376 { '+', isl_obj_union_pw_qpolynomial_fold,
377 isl_obj_union_pw_qpolynomial,
378 isl_obj_union_pw_qpolynomial_fold,
379 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial },
380 { '-', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
381 isl_obj_union_pw_qpolynomial,
382 (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
383 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
384 isl_obj_union_pw_qpolynomial,
385 (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
386 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
387 isl_obj_union_pw_qpolynomial,
388 (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
389 { '*', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
390 isl_obj_union_pw_qpolynomial_fold,
391 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
392 { '@', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
393 isl_obj_union_pw_qpolynomial,
394 (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
395 { '@', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
396 isl_obj_union_pw_qpolynomial,
397 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
398 { '%', isl_obj_union_set, isl_obj_union_set,
399 isl_obj_union_set,
400 (isc_bin_op_fn) &isl_union_set_gist },
401 { '%', isl_obj_union_map, isl_obj_union_map,
402 isl_obj_union_map,
403 (isc_bin_op_fn) &isl_union_map_gist },
404 { '%', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
405 isl_obj_union_pw_qpolynomial,
406 (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
407 { '%', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
408 isl_obj_union_pw_qpolynomial_fold,
409 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
410 { '+', isl_obj_str, isl_obj_str, isl_obj_str,
411 (isc_bin_op_fn) &isl_str_concat },
412 0
413 };
414
415 static __isl_give isl_union_map *map_after_map(__isl_take isl_union_map *umap1,
416 __isl_take isl_union_map *umap2)
417 {
418 return isl_union_map_apply_range(umap2, umap1);
419 }
420
421 static __isl_give isl_union_pw_qpolynomial *qpolynomial_after_map(
422 __isl_take isl_union_pw_qpolynomial *upwqp,
423 __isl_take isl_union_map *umap)
424 {
425 return isl_union_map_apply_union_pw_qpolynomial(umap, upwqp);
426 }
427
428 static __isl_give struct isl_list *qpolynomial_fold_after_map(
429 __isl_take isl_union_pw_qpolynomial_fold *upwf,
430 __isl_take isl_union_map *umap)
431 {
432 return union_map_apply_union_pw_qpolynomial_fold(umap, upwf);
433 }
434
435 struct isc_named_bin_op named_bin_ops[] = {
436 { "after", { -1, isl_obj_union_map, isl_obj_union_map,
437 isl_obj_union_map,
438 (isc_bin_op_fn) &map_after_map } },
439 { "after", { -1, isl_obj_union_pw_qpolynomial,
440 isl_obj_union_map, isl_obj_union_pw_qpolynomial,
441 (isc_bin_op_fn) &qpolynomial_after_map } },
442 { "after", { -1, isl_obj_union_pw_qpolynomial_fold,
443 isl_obj_union_map, isl_obj_list,
444 (isc_bin_op_fn) &qpolynomial_fold_after_map } },
445 { "before", { -1, isl_obj_union_map, isl_obj_union_map,
446 isl_obj_union_map,
447 (isc_bin_op_fn) &isl_union_map_apply_range } },
448 { "before", { -1, isl_obj_union_map,
449 isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
450 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial } },
451 { "before", { -1, isl_obj_union_map,
452 isl_obj_union_pw_qpolynomial_fold, isl_obj_list,
453 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold } },
454 { "cross", { -1, isl_obj_union_set, isl_obj_union_set,
455 isl_obj_union_set,
456 (isc_bin_op_fn) &isl_union_set_product } },
457 { "cross", { -1, isl_obj_union_map, isl_obj_union_map,
458 isl_obj_union_map,
459 (isc_bin_op_fn) &isl_union_map_product } },
460 NULL
461 };
462
463 __isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
464 {
465 return isl_set_from_basic_set(isl_union_set_sample(uset));
466 }
467
468 __isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
469 {
470 return isl_map_from_basic_map(isl_union_map_sample(umap));
471 }
472
473 static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
474 __isl_take isl_union_pw_qpolynomial *upwqp)
475 {
476 isl_ctx *ctx;
477 struct isl_list *list;
478 int tight;
479
480 ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
481 list = isl_list_alloc(ctx, 2);
482 if (!list)
483 goto error2;
484
485 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
486 list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
487 isl_fold_max, &tight);
488 list->obj[1].type = isl_obj_bool;
489 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
490 if (tight < 0 || !list->obj[0].v)
491 goto error;
492
493 return list;
494 error2:
495 isl_union_pw_qpolynomial_free(upwqp);
496 error:
497 isl_list_free(list);
498 return NULL;
499 }
500
501 #ifdef HAVE_CLOOG
502 void *map_codegen(void *arg)
503 {
504 isl_dim *dim;
505 isl_union_map *umap = (isl_union_map *)arg;
506 isl_ctx *ctx = isl_union_map_get_ctx(umap);
507 CloogState *state;
508 CloogOptions *options;
509 CloogDomain *context;
510 CloogUnionDomain *ud;
511 CloogInput *input;
512 struct clast_stmt *stmt;
513
514 state = cloog_isl_state_malloc(ctx);
515 options = cloog_options_malloc(state);
516 options->language = LANGUAGE_C;
517 options->strides = 1;
518
519 ud = cloog_union_domain_from_isl_union_map(isl_union_map_copy(umap));
520
521 dim = isl_union_map_get_dim(umap);
522 context = cloog_domain_from_isl_set(isl_set_universe(dim));
523
524 input = cloog_input_alloc(context, ud);
525
526 stmt = cloog_clast_create_from_input(input, options);
527 clast_pprint(stdout, stmt, 0, options);
528 cloog_clast_free(stmt);
529
530 error:
531 cloog_options_free(options);
532 cloog_state_free(state);
533 isl_union_map_free(umap);
534 return NULL;
535 }
536
537 void *set_codegen(void *arg)
538 {
539 isl_dim *dim;
540 isl_union_set *uset = (isl_union_set *)arg;
541 isl_ctx *ctx = isl_union_set_get_ctx(uset);
542 CloogState *state;
543 CloogOptions *options;
544 CloogDomain *context;
545 CloogUnionDomain *ud;
546 CloogInput *input;
547 struct clast_stmt *stmt;
548
549 state = cloog_isl_state_malloc(ctx);
550 options = cloog_options_malloc(state);
551 options->language = LANGUAGE_C;
552 options->strides = 1;
553
554 ud = cloog_union_domain_from_isl_union_set(isl_union_set_copy(uset));
555
556 dim = isl_union_set_get_dim(uset);
557 context = cloog_domain_from_isl_set(isl_set_universe(dim));
558
559 input = cloog_input_alloc(context, ud);
560
561 stmt = cloog_clast_create_from_input(input, options);
562 clast_pprint(stdout, stmt, 0, options);
563 cloog_clast_free(stmt);
564
565 error:
566 cloog_options_free(options);
567 cloog_state_free(state);
568 isl_union_set_free(uset);
569 return NULL;
570 }
571 #endif
572
573 static int add_point(__isl_take isl_point *pnt, void *user)
574 {
575 isl_union_set **scan = (isl_union_set **) user;
576
577 *scan = isl_union_set_add_set(*scan, isl_set_from_point(pnt));
578
579 return 0;
580 }
581
582 static __isl_give isl_union_set *union_set_scan(__isl_take isl_union_set *uset)
583 {
584 isl_union_set *scan;
585
586 scan = isl_union_set_empty(isl_union_set_get_dim(uset));
587
588 if (isl_union_set_foreach_point(uset, add_point, &scan) < 0) {
589 isl_union_set_free(scan);
590 return uset;
591 }
592
593 isl_union_set_free(uset);
594 return scan;
595 }
596
597 static __isl_give isl_union_map *union_map_scan(__isl_take isl_union_map *umap)
598 {
599 return isl_union_set_unwrap(union_set_scan(isl_union_map_wrap(umap)));
600 }
601
602 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_poly(
603 __isl_take isl_union_pw_qpolynomial *upwqp)
604 {
605 return isl_union_pw_qpolynomial_to_polynomial(upwqp, 0);
606 }
607
608 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_lpoly(
609 __isl_take isl_union_pw_qpolynomial *upwqp)
610 {
611 return isl_union_pw_qpolynomial_to_polynomial(upwqp, -1);
612 }
613
614 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_upoly(
615 __isl_take isl_union_pw_qpolynomial *upwqp)
616 {
617 return isl_union_pw_qpolynomial_to_polynomial(upwqp, 1);
618 }
619
620 typedef void *(*isc_un_op_fn)(void *arg);
621 struct isc_un_op {
622 enum isl_token_type op;
623 isl_obj_type arg;
624 isl_obj_type res;
625 isc_un_op_fn fn;
626 };
627 struct isc_named_un_op {
628 char *name;
629 struct isc_un_op op;
630 };
631 struct isc_named_un_op named_un_ops[] = {
632 {"aff", { -1, isl_obj_union_map, isl_obj_union_map,
633 (isc_un_op_fn) &isl_union_map_affine_hull } },
634 {"aff", { -1, isl_obj_union_set, isl_obj_union_set,
635 (isc_un_op_fn) &isl_union_set_affine_hull } },
636 {"card", { -1, isl_obj_union_set,
637 isl_obj_union_pw_qpolynomial,
638 (isc_un_op_fn) &isl_union_set_card } },
639 {"card", { -1, isl_obj_union_map,
640 isl_obj_union_pw_qpolynomial,
641 (isc_un_op_fn) &isl_union_map_card } },
642 {"coalesce", { -1, isl_obj_union_set, isl_obj_union_set,
643 (isc_un_op_fn) &isl_union_set_coalesce } },
644 {"coalesce", { -1, isl_obj_union_map, isl_obj_union_map,
645 (isc_un_op_fn) &isl_union_map_coalesce } },
646 {"coalesce", { -1, isl_obj_union_pw_qpolynomial,
647 isl_obj_union_pw_qpolynomial,
648 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
649 {"coalesce", { -1, isl_obj_union_pw_qpolynomial_fold,
650 isl_obj_union_pw_qpolynomial_fold,
651 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
652 #ifdef HAVE_CLOOG
653 {"codegen", { -1, isl_obj_union_set, isl_obj_none,
654 &set_codegen } },
655 {"codegen", { -1, isl_obj_union_map, isl_obj_none,
656 &map_codegen } },
657 #endif
658 {"deltas", { -1, isl_obj_union_map, isl_obj_union_set,
659 (isc_un_op_fn) &isl_union_map_deltas } },
660 {"dom", { -1, isl_obj_union_map, isl_obj_union_set,
661 (isc_un_op_fn) &isl_union_map_domain } },
662 {"dom", { -1, isl_obj_union_pw_qpolynomial, isl_obj_union_set,
663 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
664 {"dom", { -1, isl_obj_union_pw_qpolynomial_fold,
665 isl_obj_union_set,
666 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
667 {"ran", { -1, isl_obj_union_map, isl_obj_union_set,
668 (isc_un_op_fn) &isl_union_map_range } },
669 {"identity", { -1, isl_obj_union_set, isl_obj_union_map,
670 (isc_un_op_fn) &isl_union_set_identity } },
671 {"lexmin", { -1, isl_obj_union_map, isl_obj_union_map,
672 (isc_un_op_fn) &isl_union_map_lexmin } },
673 {"lexmax", { -1, isl_obj_union_map, isl_obj_union_map,
674 (isc_un_op_fn) &isl_union_map_lexmax } },
675 {"lexmin", { -1, isl_obj_union_set, isl_obj_union_set,
676 (isc_un_op_fn) &isl_union_set_lexmin } },
677 {"lexmax", { -1, isl_obj_union_set, isl_obj_union_set,
678 (isc_un_op_fn) &isl_union_set_lexmax } },
679 {"poly", { -1, isl_obj_union_map, isl_obj_union_map,
680 (isc_un_op_fn) &isl_union_map_polyhedral_hull } },
681 {"poly", { -1, isl_obj_union_set, isl_obj_union_set,
682 (isc_un_op_fn) &isl_union_set_polyhedral_hull } },
683 {"poly", { -1, isl_obj_union_pw_qpolynomial,
684 isl_obj_union_pw_qpolynomial,
685 (isc_un_op_fn) &union_pw_qpolynomial_poly } },
686 {"lpoly", { -1, isl_obj_union_pw_qpolynomial,
687 isl_obj_union_pw_qpolynomial,
688 (isc_un_op_fn) &union_pw_qpolynomial_lpoly } },
689 {"upoly", { -1, isl_obj_union_pw_qpolynomial,
690 isl_obj_union_pw_qpolynomial,
691 (isc_un_op_fn) &union_pw_qpolynomial_upoly } },
692 {"sample", { -1, isl_obj_union_set, isl_obj_set,
693 (isc_un_op_fn) &union_set_sample } },
694 {"sample", { -1, isl_obj_union_map, isl_obj_map,
695 (isc_un_op_fn) &union_map_sample } },
696 {"scan", { -1, isl_obj_union_set, isl_obj_union_set,
697 (isc_un_op_fn) &union_set_scan } },
698 {"scan", { -1, isl_obj_union_map, isl_obj_union_map,
699 (isc_un_op_fn) &union_map_scan } },
700 {"sum", { -1, isl_obj_union_pw_qpolynomial,
701 isl_obj_union_pw_qpolynomial,
702 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
703 {"ub", { -1, isl_obj_union_pw_qpolynomial, isl_obj_list,
704 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
705 {"unwrap", { -1, isl_obj_union_set, isl_obj_union_map,
706 (isc_un_op_fn) &isl_union_set_unwrap } },
707 {"wrap", { -1, isl_obj_union_map, isl_obj_union_set,
708 (isc_un_op_fn) &isl_union_map_wrap } },
709 NULL
710 };
711
712 struct isl_named_obj {
713 char *name;
714 struct isl_obj obj;
715 };
716
717 static void free_obj(struct isl_obj obj)
718 {
719 obj.type->free(obj.v);
720 }
721
722 static int same_name(const void *entry, const void *val)
723 {
724 const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
725
726 return !strcmp(named->name, val);
727 }
728
729 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
730 char *name, struct isl_obj obj)
731 {
732 struct isl_hash_table_entry *entry;
733 uint32_t name_hash;
734 struct isl_named_obj *named;
735
736 name_hash = isl_hash_string(isl_hash_init(), name);
737 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
738 if (!entry)
739 goto error;
740 if (entry->data) {
741 named = entry->data;
742 free_obj(named->obj);
743 free(name);
744 } else {
745 named = isl_alloc_type(ctx, struct isl_named_obj);
746 if (!named)
747 goto error;
748 named->name = name;
749 entry->data = named;
750 }
751 named->obj = obj;
752
753 return 0;
754 error:
755 free_obj(obj);
756 free(name);
757 return -1;
758 }
759
760 static struct isl_obj stored_obj(struct isl_ctx *ctx,
761 struct isl_hash_table *table, char *name)
762 {
763 struct isl_obj obj = { isl_obj_none, NULL };
764 struct isl_hash_table_entry *entry;
765 uint32_t name_hash;
766
767 name_hash = isl_hash_string(isl_hash_init(), name);
768 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
769 if (entry) {
770 struct isl_named_obj *named;
771 named = entry->data;
772 obj = named->obj;
773 } else
774 fprintf(stderr, "unknown identifier '%s'\n", name);
775
776 free(name);
777 obj.v = obj.type->copy(obj.v);
778 return obj;
779 }
780
781 static int is_subtype(struct isl_obj obj, isl_obj_type super)
782 {
783 if (obj.type == super)
784 return 1;
785 if (obj.type == isl_obj_map && super == isl_obj_union_map)
786 return 1;
787 if (obj.type == isl_obj_set && super == isl_obj_union_set)
788 return 1;
789 if (obj.type == isl_obj_pw_qpolynomial &&
790 super == isl_obj_union_pw_qpolynomial)
791 return 1;
792 if (obj.type == isl_obj_pw_qpolynomial_fold &&
793 super == isl_obj_union_pw_qpolynomial_fold)
794 return 1;
795 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
796 return 1;
797 if (obj.type == isl_obj_list) {
798 struct isl_list *list = obj.v;
799 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
800 return is_subtype(list->obj[0], super);
801 }
802 if (super == isl_obj_str)
803 return 1;
804 return 0;
805 }
806
807 static struct isl_obj obj_at(struct isl_obj obj, int i)
808 {
809 struct isl_list *list = obj.v;
810
811 obj = list->obj[i];
812 obj.v = obj.type->copy(obj.v);
813
814 isl_list_free(list);
815
816 return obj;
817 }
818
819 static struct isl_obj convert(isl_ctx *ctx, struct isl_obj obj,
820 isl_obj_type type)
821 {
822 if (obj.type == type)
823 return obj;
824 if (obj.type == isl_obj_map && type == isl_obj_union_map) {
825 obj.type = isl_obj_union_map;
826 obj.v = isl_union_map_from_map(obj.v);
827 return obj;
828 }
829 if (obj.type == isl_obj_set && type == isl_obj_union_set) {
830 obj.type = isl_obj_union_set;
831 obj.v = isl_union_set_from_set(obj.v);
832 return obj;
833 }
834 if (obj.type == isl_obj_pw_qpolynomial &&
835 type == isl_obj_union_pw_qpolynomial) {
836 obj.type = isl_obj_union_pw_qpolynomial;
837 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
838 return obj;
839 }
840 if (obj.type == isl_obj_pw_qpolynomial_fold &&
841 type == isl_obj_union_pw_qpolynomial_fold) {
842 obj.type = isl_obj_union_pw_qpolynomial_fold;
843 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
844 return obj;
845 }
846 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
847 if (type == isl_obj_union_map) {
848 obj.type = isl_obj_union_map;
849 return obj;
850 }
851 if (type == isl_obj_union_pw_qpolynomial) {
852 isl_dim *dim = isl_union_set_get_dim(obj.v);
853 isl_union_set_free(obj.v);
854 obj.v = isl_union_pw_qpolynomial_zero(dim);
855 obj.type = isl_obj_union_pw_qpolynomial;
856 return obj;
857 }
858 if (type == isl_obj_union_pw_qpolynomial_fold) {
859 isl_dim *dim = isl_union_set_get_dim(obj.v);
860 isl_union_set_free(obj.v);
861 obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
862 isl_fold_list);
863 obj.type = isl_obj_union_pw_qpolynomial_fold;
864 return obj;
865 }
866 }
867 if (obj.type == isl_obj_list) {
868 struct isl_list *list = obj.v;
869 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
870 return convert(ctx, obj_at(obj, 0), type);
871 }
872 if (type == isl_obj_str) {
873 isl_str *str;
874 isl_printer *p;
875 char *s;
876
877 p = isl_printer_to_str(ctx);
878 if (!p)
879 goto error;
880 p = obj.type->print(p, obj.v);
881 s = isl_printer_get_str(p);
882 isl_printer_free(p);
883
884 str = isl_str_alloc(ctx);
885 if (!str) {
886 free(s);
887 goto error;
888 }
889 str->s = s;
890 free_obj(obj);
891 obj.v = str;
892 obj.type = isl_obj_str;
893 return obj;
894
895 }
896 error:
897 free_obj(obj);
898 obj.type = isl_obj_none;
899 obj.v = NULL;
900 return obj;
901 }
902
903 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
904 struct isl_obj lhs)
905 {
906 int i;
907 struct isl_token *tok;
908
909 tok = isl_stream_next_token(s);
910 if (!tok)
911 return NULL;
912
913 for (i = 0; ; ++i) {
914 if (!bin_ops[i].op)
915 break;
916 if (bin_ops[i].op != tok->type)
917 continue;
918 if (!is_subtype(lhs, bin_ops[i].lhs))
919 continue;
920
921 isl_token_free(tok);
922 return &bin_ops[i];
923 }
924
925 for (i = 0; ; ++i) {
926 if (!named_bin_ops[i].name)
927 break;
928 if (named_bin_ops[i].op.op != tok->type)
929 continue;
930 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
931 continue;
932
933 isl_token_free(tok);
934 return &named_bin_ops[i].op;
935 }
936
937 isl_stream_push_token(s, tok);
938
939 return NULL;
940 }
941
942 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
943 {
944 int i;
945 struct isl_token *tok;
946
947 tok = isl_stream_next_token(s);
948 if (!tok)
949 return NULL;
950
951 for (i = 0; ; ++i) {
952 if (!named_un_ops[i].name)
953 break;
954 if (named_un_ops[i].op.op != tok->type)
955 continue;
956
957 isl_token_free(tok);
958 return &named_un_ops[i].op;
959 }
960
961 isl_stream_push_token(s, tok);
962
963 return NULL;
964 }
965
966 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
967 struct isl_obj arg)
968 {
969 int i;
970
971 for (i = 0; ; ++i) {
972 if (!named_un_ops[i].name)
973 break;
974 if (named_un_ops[i].op.op != like->op)
975 continue;
976 if (!is_subtype(arg, named_un_ops[i].op.arg))
977 continue;
978
979 return &named_un_ops[i].op;
980 }
981
982 return NULL;
983 }
984
985 static int is_assign(struct isl_stream *s)
986 {
987 struct isl_token *tok;
988 struct isl_token *tok2;
989 int assign;
990
991 tok = isl_stream_next_token(s);
992 if (!tok)
993 return 0;
994 if (tok->type != ISL_TOKEN_IDENT) {
995 isl_stream_push_token(s, tok);
996 return 0;
997 }
998
999 tok2 = isl_stream_next_token(s);
1000 if (!tok2) {
1001 isl_stream_push_token(s, tok);
1002 return 0;
1003 }
1004 assign = tok2->type == ISL_TOKEN_DEF;
1005 isl_stream_push_token(s, tok2);
1006 isl_stream_push_token(s, tok);
1007
1008 return assign;
1009 }
1010
1011 static struct isl_obj read_obj(struct isl_stream *s,
1012 struct isl_hash_table *table);
1013 static struct isl_obj read_expr(struct isl_stream *s,
1014 struct isl_hash_table *table);
1015
1016 static struct isl_obj read_un_op_expr(struct isl_stream *s,
1017 struct isl_hash_table *table, struct isc_un_op *op)
1018 {
1019 struct isl_obj obj = { isl_obj_none, NULL };
1020
1021 obj = read_obj(s, table);
1022 if (!obj.v)
1023 goto error;
1024
1025 op = find_matching_un_op(op, obj);
1026
1027 isl_assert(s->ctx, op, goto error);
1028 obj = convert(s->ctx, obj, op->arg);
1029 obj.v = op->fn(obj.v);
1030 obj.type = op->res;
1031
1032 return obj;
1033 error:
1034 free_obj(obj);
1035 obj.type = isl_obj_none;
1036 obj.v = NULL;
1037 return obj;
1038 }
1039
1040 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
1041 {
1042 struct isl_list *list;
1043 int exact;
1044
1045 if (obj.type != isl_obj_union_map)
1046 obj = convert(ctx, obj, isl_obj_union_map);
1047 isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
1048 list = isl_list_alloc(ctx, 2);
1049 if (!list)
1050 goto error;
1051
1052 list->obj[0].type = isl_obj_union_map;
1053 list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
1054 list->obj[1].type = isl_obj_bool;
1055 list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
1056 obj.v = list;
1057 obj.type = isl_obj_list;
1058 if (exact < 0 || !list->obj[0].v)
1059 goto error;
1060
1061 return obj;
1062 error:
1063 free_obj(obj);
1064 obj.type = isl_obj_none;
1065 obj.v = NULL;
1066 return obj;
1067 }
1068
1069 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
1070 {
1071 struct isl_list *list = obj.v;
1072 struct isl_token *tok;
1073 int i;
1074
1075 tok = isl_stream_next_token(s);
1076 if (!tok || tok->type != ISL_TOKEN_VALUE) {
1077 isl_stream_error(s, tok, "expecting index");
1078 if (tok)
1079 isl_stream_push_token(s, tok);
1080 goto error;
1081 }
1082 i = isl_int_get_si(tok->u.v);
1083 isl_token_free(tok);
1084 isl_assert(s->ctx, i < list->n, goto error);
1085 if (isl_stream_eat(s, ']'))
1086 goto error;
1087
1088 return obj_at(obj, i);
1089 error:
1090 free_obj(obj);
1091 obj.type = isl_obj_none;
1092 obj.v = NULL;
1093 return obj;
1094 }
1095
1096 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
1097 struct isl_hash_table *table)
1098 {
1099 struct isl_obj obj;
1100
1101 obj = read_expr(s, table);
1102 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
1103 is_subtype(obj, isl_obj_union_map), goto error);
1104
1105 if (obj.type == isl_obj_list) {
1106 struct isl_list *list = obj.v;
1107 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1108 obj = obj_at(obj, 0);
1109 }
1110 if (obj.type == isl_obj_set)
1111 obj = convert(s->ctx, obj, isl_obj_union_set);
1112 else if (obj.type == isl_obj_map)
1113 obj = convert(s->ctx, obj, isl_obj_union_map);
1114 if (obj.type == isl_obj_union_set) {
1115 obj.v = isl_union_set_apply(obj.v, umap);
1116 } else
1117 obj.v = isl_union_map_apply_range(obj.v, umap);
1118 if (!obj.v)
1119 goto error2;
1120
1121 if (isl_stream_eat(s, ')'))
1122 goto error2;
1123
1124 return obj;
1125 error:
1126 isl_union_map_free(umap);
1127 error2:
1128 free_obj(obj);
1129 obj.type = isl_obj_none;
1130 obj.v = NULL;
1131 return obj;
1132 }
1133
1134 static struct isl_obj apply_fun(struct isl_stream *s,
1135 struct isl_obj obj, struct isl_hash_table *table)
1136 {
1137 struct isl_obj arg;
1138
1139 arg = read_expr(s, table);
1140 isl_assert(s->ctx, is_subtype(arg, isl_obj_union_map), goto error);
1141
1142 if (arg.type == isl_obj_list) {
1143 struct isl_list *list = arg.v;
1144 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1145 arg = obj_at(arg, 0);
1146 }
1147 if (arg.type == isl_obj_map)
1148 arg = convert(s->ctx, arg, isl_obj_union_map);
1149 if (obj.type == isl_obj_union_pw_qpolynomial) {
1150 obj.v = isl_union_map_apply_union_pw_qpolynomial(arg.v, obj.v);
1151 } else {
1152 obj.type = isl_obj_list;
1153 obj.v = union_map_apply_union_pw_qpolynomial_fold(arg.v, obj.v);
1154 }
1155 if (!obj.v)
1156 goto error2;
1157
1158 if (isl_stream_eat(s, ')'))
1159 goto error2;
1160
1161 return obj;
1162 error:
1163 free_obj(arg);
1164 error2:
1165 free_obj(obj);
1166 obj.type = isl_obj_none;
1167 obj.v = NULL;
1168 return obj;
1169 }
1170
1171 struct add_vertex_data {
1172 struct isl_list *list;
1173 int i;
1174 };
1175
1176 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
1177 {
1178 struct add_vertex_data *data = (struct add_vertex_data *)user;
1179 isl_basic_set *expr;
1180
1181 expr = isl_vertex_get_expr(vertex);
1182
1183 data->list->obj[data->i].type = isl_obj_set;
1184 data->list->obj[data->i].v = isl_set_from_basic_set(expr);
1185 data->i++;
1186
1187 isl_vertex_free(vertex);
1188
1189 return 0;
1190 }
1191
1192 static int set_vertices(__isl_take isl_set *set, void *user)
1193 {
1194 isl_ctx *ctx;
1195 isl_basic_set *hull;
1196 isl_vertices *vertices = NULL;
1197 struct isl_list *list = NULL;
1198 int r;
1199 struct add_vertex_data *data = (struct add_vertex_data *)user;
1200
1201 set = isl_set_remove_divs(set);
1202 hull = isl_set_convex_hull(set);
1203 vertices = isl_basic_set_compute_vertices(hull);
1204 isl_basic_set_free(hull);
1205
1206 list = data->list;
1207
1208 ctx = isl_vertices_get_ctx(vertices);
1209 data->list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1210 if (!data->list)
1211 goto error;
1212
1213 data->i = 0;
1214 r = isl_vertices_foreach_vertex(vertices, &add_vertex, user);
1215
1216 data->list = isl_list_concat(list, data->list);
1217
1218 isl_vertices_free(vertices);
1219
1220 return r;
1221 error:
1222 data->list = list;
1223 isl_vertices_free(vertices);
1224 return -1;
1225 }
1226
1227 static struct isl_obj vertices(struct isl_stream *s,
1228 struct isl_hash_table *table)
1229 {
1230 isl_ctx *ctx;
1231 struct isl_obj obj;
1232 struct isl_list *list = NULL;
1233 isl_union_set *uset;
1234 struct add_vertex_data data = { NULL };
1235
1236 obj = read_expr(s, table);
1237 obj = convert(s->ctx, obj, isl_obj_union_set);
1238 isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1239 uset = obj.v;
1240 obj.v = NULL;
1241
1242 ctx = isl_union_set_get_ctx(uset);
1243 list = isl_list_alloc(ctx, 0);
1244 if (!list)
1245 goto error;
1246
1247 data.list = list;
1248
1249 if (isl_union_set_foreach_set(uset, &set_vertices, &data) < 0)
1250 goto error;
1251
1252 isl_union_set_free(uset);
1253
1254 obj.type = isl_obj_list;
1255 obj.v = data.list;
1256
1257 return obj;
1258 error:
1259 isl_union_set_free(uset);
1260 isl_list_free(data.list);
1261 free_obj(obj);
1262 obj.type = isl_obj_none;
1263 obj.v = NULL;
1264 return obj;
1265 }
1266
1267 static __isl_give isl_union_map *read_map(struct isl_stream *s,
1268 struct isl_hash_table *table)
1269 {
1270 struct isl_obj obj;
1271
1272 obj = read_obj(s, table);
1273 obj = convert(s->ctx, obj, isl_obj_union_map);
1274 isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error);
1275 return obj.v;
1276 error:
1277 free_obj(obj);
1278 return NULL;
1279 }
1280
1281 static struct isl_obj last_any(struct isl_stream *s,
1282 struct isl_hash_table *table, __isl_take isl_union_map *must_source,
1283 __isl_take isl_union_map *may_source)
1284 {
1285 struct isl_obj obj = { isl_obj_none, NULL };
1286 isl_union_map *sink = NULL;
1287 isl_union_map *schedule = NULL;
1288 isl_union_map *may_dep;
1289 isl_union_map *must_dep;
1290
1291 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1292 goto error;
1293
1294 sink = read_map(s, table);
1295 if (!sink)
1296 goto error;
1297
1298 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1299 goto error;
1300
1301 schedule = read_map(s, table);
1302 if (!schedule)
1303 goto error;
1304
1305 if (isl_union_map_compute_flow(sink, must_source, may_source,
1306 schedule, &must_dep, &may_dep,
1307 NULL, NULL) < 0)
1308 return obj;
1309
1310 obj.type = isl_obj_union_map;
1311 obj.v = isl_union_map_union(must_dep, may_dep);
1312
1313 return obj;
1314 error:
1315 isl_union_map_free(may_source);
1316 isl_union_map_free(must_source);
1317 isl_union_map_free(sink);
1318 isl_union_map_free(schedule);
1319 free_obj(obj);
1320 obj.type = isl_obj_none;
1321 obj.v = NULL;
1322 return obj;
1323 }
1324
1325 static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table)
1326 {
1327 struct isl_obj obj = { isl_obj_none, NULL };
1328 isl_union_map *must_source = NULL;
1329 isl_union_map *may_source = NULL;
1330 isl_union_map *sink = NULL;
1331 isl_union_map *schedule = NULL;
1332 isl_union_map *may_dep;
1333
1334 may_source = read_map(s, table);
1335 if (!may_source)
1336 goto error;
1337
1338 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) {
1339 must_source = read_map(s, table);
1340 if (!must_source)
1341 goto error;
1342 return last_any(s, table, must_source, may_source);
1343 }
1344
1345 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1346 goto error;
1347
1348 sink = read_map(s, table);
1349 if (!sink)
1350 goto error;
1351
1352 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1353 goto error;
1354
1355 schedule = read_map(s, table);
1356 if (!schedule)
1357 goto error;
1358
1359 must_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1360 if (isl_union_map_compute_flow(sink, must_source, may_source,
1361 schedule, NULL, &may_dep,
1362 NULL, NULL) < 0)
1363 return obj;
1364
1365 obj.type = isl_obj_union_map;
1366 obj.v = may_dep;
1367
1368 return obj;
1369 error:
1370 isl_union_map_free(may_source);
1371 isl_union_map_free(must_source);
1372 isl_union_map_free(sink);
1373 isl_union_map_free(schedule);
1374 free_obj(obj);
1375 obj.type = isl_obj_none;
1376 obj.v = NULL;
1377 return obj;
1378 }
1379
1380 static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table)
1381 {
1382 struct isl_obj obj = { isl_obj_none, NULL };
1383 struct isl_list *list = NULL;
1384 isl_union_map *must_source = NULL;
1385 isl_union_map *may_source = NULL;
1386 isl_union_map *sink = NULL;
1387 isl_union_map *schedule = NULL;
1388 isl_union_map *must_dep;
1389 isl_union_set *must_no_source;
1390
1391 must_source = read_map(s, table);
1392 if (!must_source)
1393 goto error;
1394
1395 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) {
1396 may_source = read_map(s, table);
1397 if (!may_source)
1398 goto error;
1399 return last_any(s, table, must_source, may_source);
1400 }
1401
1402 list = isl_list_alloc(s->ctx, 2);
1403 if (!list)
1404 goto error;
1405
1406 if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1407 goto error;
1408
1409 sink = read_map(s, table);
1410 if (!sink)
1411 goto error;
1412
1413 if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1414 goto error;
1415
1416 schedule = read_map(s, table);
1417 if (!schedule)
1418 goto error;
1419
1420 may_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1421 if (isl_union_map_compute_flow(sink, must_source, may_source,
1422 schedule, &must_dep, NULL,
1423 &must_no_source, NULL) < 0)
1424 return obj;
1425
1426 list->obj[0].type = isl_obj_union_map;
1427 list->obj[0].v = must_dep;
1428 list->obj[1].type = isl_obj_union_set;
1429 list->obj[1].v = must_no_source;
1430
1431 obj.v = list;
1432 obj.type = isl_obj_list;
1433
1434 return obj;
1435 error:
1436 isl_list_free(list);
1437 isl_union_map_free(may_source);
1438 isl_union_map_free(must_source);
1439 isl_union_map_free(sink);
1440 isl_union_map_free(schedule);
1441 free_obj(obj);
1442 obj.type = isl_obj_none;
1443 obj.v = NULL;
1444 return obj;
1445 }
1446
1447 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1448 {
1449 struct isl_token *tok;
1450
1451 if (isl_stream_eat_if_available(s, '+'))
1452 return transitive_closure(s->ctx, obj);
1453
1454 tok = isl_stream_next_token(s);
1455 if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
1456 isl_stream_error(s, tok, "expecting -1");
1457 if (tok)
1458 isl_stream_push_token(s, tok);
1459 goto error;
1460 }
1461 isl_token_free(tok);
1462 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1463 if (obj.type != isl_obj_union_map)
1464 obj = convert(s->ctx, obj, isl_obj_union_map);
1465
1466 obj.v = isl_union_map_reverse(obj.v);
1467 if (!obj.v)
1468 goto error;
1469
1470 return obj;
1471 error:
1472 free_obj(obj);
1473 obj.type = isl_obj_none;
1474 obj.v = NULL;
1475 return obj;
1476 }
1477
1478 static struct isl_obj read_from_file(struct isl_stream *s)
1479 {
1480 struct isl_obj obj;
1481 struct isl_token *tok;
1482 struct isl_stream *s_file;
1483 FILE *file;
1484
1485 tok = isl_stream_next_token(s);
1486 if (!tok || tok->type != ISL_TOKEN_STRING) {
1487 isl_stream_error(s, tok, "expecting filename");
1488 isl_token_free(tok);
1489 goto error;
1490 }
1491
1492 file = fopen(tok->u.s, "r");
1493 isl_token_free(tok);
1494 isl_assert(s->ctx, file, goto error);
1495
1496 s_file = isl_stream_new_file(s->ctx, file);
1497 if (!s_file) {
1498 fclose(file);
1499 goto error;
1500 }
1501
1502 obj = isl_stream_read_obj(s_file);
1503
1504 isl_stream_free(s_file);
1505 fclose(file);
1506
1507 return obj;
1508 error:
1509 obj.type = isl_obj_none;
1510 obj.v = NULL;
1511 return obj;
1512 }
1513
1514 static struct isl_obj read_string_if_available(struct isl_stream *s)
1515 {
1516 struct isl_token *tok;
1517 struct isl_obj obj = { isl_obj_none, NULL };
1518
1519 tok = isl_stream_next_token(s);
1520 if (!tok)
1521 return obj;
1522 if (tok->type == ISL_TOKEN_STRING) {
1523 isl_str *str;
1524 str = isl_str_alloc(s->ctx);
1525 if (!str)
1526 goto error;
1527 str->s = strdup(tok->u.s);
1528 isl_token_free(tok);
1529 obj.v = str;
1530 obj.type = isl_obj_str;
1531 } else
1532 isl_stream_push_token(s, tok);
1533 return obj;
1534 error:
1535 isl_token_free(tok);
1536 return obj;
1537 }
1538
1539 static struct isl_obj read_obj(struct isl_stream *s,
1540 struct isl_hash_table *table)
1541 {
1542 struct isl_obj obj = { isl_obj_none, NULL };
1543 char *name = NULL;
1544 struct isc_un_op *op = NULL;
1545
1546 obj = read_string_if_available(s);
1547 if (obj.v)
1548 return obj;
1549 if (isl_stream_eat_if_available(s, '(')) {
1550 obj = read_expr(s, table);
1551 if (!obj.v || isl_stream_eat(s, ')'))
1552 goto error;
1553 } else {
1554 op = read_prefix_un_op_if_available(s);
1555 if (op)
1556 return read_un_op_expr(s, table, op);
1557
1558 if (isl_stream_eat_if_available(s, iscc_op[ISCC_READ]))
1559 return read_from_file(s);
1560 if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES]))
1561 return vertices(s, table);
1562 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY]))
1563 return any(s, table);
1564 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST]))
1565 return last(s, table);
1566
1567 name = isl_stream_read_ident_if_available(s);
1568 if (name)
1569 obj = stored_obj(s->ctx, table, name);
1570 else
1571 obj = isl_stream_read_obj(s);
1572 if (!obj.v)
1573 goto error;
1574 }
1575
1576 if (isl_stream_eat_if_available(s, '^'))
1577 obj = power(s, obj);
1578 else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1579 obj = obj_at_index(s, obj);
1580 else if (is_subtype(obj, isl_obj_union_map) &&
1581 isl_stream_eat_if_available(s, '(')) {
1582 obj = convert(s->ctx, obj, isl_obj_union_map);
1583 obj = apply(s, obj.v, table);
1584 } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial) &&
1585 isl_stream_eat_if_available(s, '(')) {
1586 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial);
1587 obj = apply_fun(s, obj, table);
1588 } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial_fold) &&
1589 isl_stream_eat_if_available(s, '(')) {
1590 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial_fold);
1591 obj = apply_fun(s, obj, table);
1592 }
1593
1594 return obj;
1595 error:
1596 free_obj(obj);
1597 obj.type = isl_obj_none;
1598 obj.v = NULL;
1599 return obj;
1600 }
1601
1602 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1603 struct isl_obj lhs, struct isl_obj rhs)
1604 {
1605 int i;
1606
1607 for (i = 0; ; ++i) {
1608 if (!bin_ops[i].op)
1609 break;
1610 if (bin_ops[i].op != like->op)
1611 continue;
1612 if (!is_subtype(lhs, bin_ops[i].lhs))
1613 continue;
1614 if (!is_subtype(rhs, bin_ops[i].rhs))
1615 continue;
1616
1617 return &bin_ops[i];
1618 }
1619
1620 for (i = 0; ; ++i) {
1621 if (!named_bin_ops[i].name)
1622 break;
1623 if (named_bin_ops[i].op.op != like->op)
1624 continue;
1625 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1626 continue;
1627 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1628 continue;
1629
1630 return &named_bin_ops[i].op;
1631 }
1632
1633 return NULL;
1634 }
1635
1636 static struct isl_obj read_expr(struct isl_stream *s,
1637 struct isl_hash_table *table)
1638 {
1639 struct isl_obj obj = { isl_obj_none, NULL };
1640 struct isl_obj right_obj = { isl_obj_none, NULL };
1641
1642 obj = read_obj(s, table);
1643 for (; obj.v;) {
1644 struct isc_bin_op *op = NULL;
1645
1646 op = read_bin_op_if_available(s, obj);
1647 if (!op)
1648 break;
1649
1650 right_obj = read_obj(s, table);
1651
1652 op = find_matching_bin_op(op, obj, right_obj);
1653
1654 isl_assert(s->ctx, op, goto error);
1655 obj = convert(s->ctx, obj, op->lhs);
1656 right_obj = convert(s->ctx, right_obj, op->rhs);
1657 obj.v = op->fn(obj.v, right_obj.v);
1658 obj.type = op->res;
1659 }
1660
1661 return obj;
1662 error:
1663 free_obj(right_obj);
1664 free_obj(obj);
1665 obj.type = isl_obj_none;
1666 obj.v = NULL;
1667 return obj;
1668 }
1669
1670 static __isl_give isl_printer *source_file(struct isl_stream *s,
1671 struct isl_hash_table *table, __isl_take isl_printer *p);
1672
1673 static __isl_give isl_printer *read_line(struct isl_stream *s,
1674 struct isl_hash_table *table, __isl_take isl_printer *p)
1675 {
1676 struct isl_obj obj = { isl_obj_none, NULL };
1677 char *lhs = NULL;
1678 int assign = 0;
1679 struct isc_bin_op *op = NULL;
1680
1681 if (!p)
1682 return NULL;
1683 if (isl_stream_is_empty(s))
1684 return p;
1685
1686 if (isl_stream_eat_if_available(s, iscc_op[ISCC_SOURCE]))
1687 return source_file(s, table, p);
1688
1689 assign = is_assign(s);
1690 if (assign) {
1691 lhs = isl_stream_read_ident_if_available(s);
1692 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1693 goto error;
1694 }
1695
1696 obj = read_expr(s, table);
1697 if (obj.type == isl_obj_none || obj.v == NULL)
1698 goto error;
1699 if (isl_stream_eat(s, ';'))
1700 goto error;
1701
1702 if (assign) {
1703 if (do_assign(s->ctx, table, lhs, obj))
1704 return;
1705 } else {
1706 p = obj.type->print(p, obj.v);
1707 p = isl_printer_end_line(p);
1708 free_obj(obj);
1709 }
1710
1711 return p;
1712 error:
1713 isl_stream_flush_tokens(s);
1714 isl_stream_skip_line(s);
1715 free(lhs);
1716 free_obj(obj);
1717 return p;
1718 }
1719
1720 int free_cb(void **entry, void *user)
1721 {
1722 struct isl_named_obj *named = *entry;
1723
1724 free_obj(named->obj);
1725 free(named->name);
1726 free(named);
1727
1728 return 0;
1729 }
1730
1731 static void register_named_ops(struct isl_stream *s)
1732 {
1733 int i;
1734
1735 for (i = 0; i < ISCC_N_OP; ++i) {
1736 iscc_op[i] = isl_stream_register_keyword(s, op_name[i]);
1737 assert(iscc_op[i] != ISL_TOKEN_ERROR);
1738 }
1739
1740 for (i = 0; ; ++i) {
1741 if (!named_un_ops[i].name)
1742 break;
1743 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1744 named_un_ops[i].name);
1745 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1746 }
1747
1748 for (i = 0; ; ++i) {
1749 if (!named_bin_ops[i].name)
1750 break;
1751 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1752 named_bin_ops[i].name);
1753 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1754 }
1755 }
1756
1757 static __isl_give isl_printer *source_file(struct isl_stream *s,
1758 struct isl_hash_table *table, __isl_take isl_printer *p)
1759 {
1760 struct isl_token *tok;
1761 struct isl_stream *s_file;
1762 FILE *file;
1763
1764 tok = isl_stream_next_token(s);
1765 if (!tok || tok->type != ISL_TOKEN_STRING) {
1766 isl_stream_error(s, tok, "expecting filename");
1767 isl_token_free(tok);
1768 return p;
1769 }
1770
1771 file = fopen(tok->u.s, "r");
1772 isl_token_free(tok);
1773 isl_assert(s->ctx, file, return p);
1774
1775 s_file = isl_stream_new_file(s->ctx, file);
1776 if (!s_file) {
1777 fclose(file);
1778 return p;
1779 }
1780
1781 register_named_ops(s_file);
1782
1783 while (!s_file->eof)
1784 p = read_line(s_file, table, p);
1785
1786 isl_stream_free(s_file);
1787 fclose(file);
1788
1789 isl_stream_eat(s, ';');
1790
1791 return p;
1792 }
1793
1794 int main(int argc, char **argv)
1795 {
1796 struct isl_ctx *ctx;
1797 struct isl_stream *s;
1798 struct isl_hash_table *table;
1799 struct iscc_options *options;
1800 isl_printer *p;
1801
1802 options = iscc_options_new_with_defaults();
1803 assert(options);
1804 argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
1805
1806 ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
1807 s = isl_stream_new_file(ctx, stdin);
1808 assert(s);
1809 table = isl_hash_table_alloc(ctx, 10);
1810 assert(table);
1811 p = isl_printer_to_file(ctx, stdout);
1812 p = isl_printer_set_output_format(p, options->format);
1813 assert(p);
1814
1815 register_named_ops(s);
1816
1817 while (p && !s->eof) {
1818 p = read_line(s, table, p);
1819 }
1820
1821 isl_printer_free(p);
1822 isl_hash_table_foreach(ctx, table, free_cb, NULL);
1823 isl_hash_table_free(ctx, table);
1824 isl_stream_free(s);
1825 isl_ctx_free(ctx);
1826
1827 return 0;
1828 }
lattice point enumeration library