iscc.c

   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 typedef void *(*isc_un_op_fn)(void *arg);
 603 struct isc_un_op {
 604         enum isl_token_type     op;
 605         isl_obj_type            arg;
 606         isl_obj_type            res;
 607         isc_un_op_fn            fn;
 608 };
 609 struct isc_named_un_op {
 610         char                    *name;
 611         struct isc_un_op        op;
 612 };
 613 struct isc_named_un_op named_un_ops[] = {
 614         {"aff", { -1,   isl_obj_union_map,      isl_obj_union_map,
 615                 (isc_un_op_fn) &isl_union_map_affine_hull } },
 616         {"aff", { -1,   isl_obj_union_set,      isl_obj_union_set,
 617                 (isc_un_op_fn) &isl_union_set_affine_hull } },
 618         {"card",        { -1,   isl_obj_union_set,
 619                 isl_obj_union_pw_qpolynomial,
 620                 (isc_un_op_fn) &isl_union_set_card } },
 621         {"card",        { -1,   isl_obj_union_map,
 622                 isl_obj_union_pw_qpolynomial,
 623                 (isc_un_op_fn) &isl_union_map_card } },
 624         {"coalesce",    { -1,   isl_obj_union_set,      isl_obj_union_set,
 625                 (isc_un_op_fn) &isl_union_set_coalesce } },
 626         {"coalesce",    { -1,   isl_obj_union_map,      isl_obj_union_map,
 627                 (isc_un_op_fn) &isl_union_map_coalesce } },
 628         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial,
 629                 isl_obj_union_pw_qpolynomial,
 630                 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
 631         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial_fold,
 632                 isl_obj_union_pw_qpolynomial_fold,
 633                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
 634 #ifdef HAVE_CLOOG
 635         {"codegen",     { -1,   isl_obj_union_set, isl_obj_none,
 636                 &set_codegen } },
 637         {"codegen",     { -1,   isl_obj_union_map, isl_obj_none,
 638                 &map_codegen } },
 639 #endif
 640         {"deltas",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 641                 (isc_un_op_fn) &isl_union_map_deltas } },
 642         {"dom", { -1,   isl_obj_union_map,      isl_obj_union_set,
 643                 (isc_un_op_fn) &isl_union_map_domain } },
 644         {"dom", { -1,   isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 645                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 646         {"dom", { -1,   isl_obj_union_pw_qpolynomial_fold,
 647                 isl_obj_union_set,
 648                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 649         {"ran", { -1,   isl_obj_union_map,      isl_obj_union_set,
 650                 (isc_un_op_fn) &isl_union_map_range } },
 651         {"identity",    { -1,   isl_obj_union_set,      isl_obj_union_map,
 652                 (isc_un_op_fn) &isl_union_set_identity } },
 653         {"lexmin",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 654                 (isc_un_op_fn) &isl_union_map_lexmin } },
 655         {"lexmax",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 656                 (isc_un_op_fn) &isl_union_map_lexmax } },
 657         {"lexmin",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 658                 (isc_un_op_fn) &isl_union_set_lexmin } },
 659         {"lexmax",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 660                 (isc_un_op_fn) &isl_union_set_lexmax } },
 661         {"poly",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 662                 (isc_un_op_fn) &isl_union_map_polyhedral_hull } },
 663         {"poly",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 664                 (isc_un_op_fn) &isl_union_set_polyhedral_hull } },
 665         {"sample",      { -1,   isl_obj_union_set,      isl_obj_set,
 666                 (isc_un_op_fn) &union_set_sample } },
 667         {"sample",      { -1,   isl_obj_union_map,      isl_obj_map,
 668                 (isc_un_op_fn) &union_map_sample } },
 669         {"scan",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 670                 (isc_un_op_fn) &union_set_scan } },
 671         {"scan",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 672                 (isc_un_op_fn) &union_map_scan } },
 673         {"sum",         { -1,   isl_obj_union_pw_qpolynomial,
 674                 isl_obj_union_pw_qpolynomial,
 675                 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
 676         {"ub",          { -1,   isl_obj_union_pw_qpolynomial, isl_obj_list,
 677                 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
 678         {"unwrap",      { -1,   isl_obj_union_set,      isl_obj_union_map,
 679                 (isc_un_op_fn) &isl_union_set_unwrap } },
 680         {"wrap",        { -1,   isl_obj_union_map,      isl_obj_union_set,
 681                 (isc_un_op_fn) &isl_union_map_wrap } },
 682         NULL
 683 };
 684
 685 struct isl_named_obj {
 686         char            *name;
 687         struct isl_obj  obj;
 688 };
 689
 690 static void free_obj(struct isl_obj obj)
 691 {
 692         obj.type->free(obj.v);
 693 }
 694
 695 static int same_name(const void *entry, const void *val)
 696 {
 697         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 698
 699         return !strcmp(named->name, val);
 700 }
 701
 702 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 703         char *name, struct isl_obj obj)
 704 {
 705         struct isl_hash_table_entry *entry;
 706         uint32_t name_hash;
 707         struct isl_named_obj *named;
 708
 709         name_hash = isl_hash_string(isl_hash_init(), name);
 710         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 711         if (!entry)
 712                 goto error;
 713         if (entry->data) {
 714                 named = entry->data;
 715                 free_obj(named->obj);
 716                 free(name);
 717         } else {
 718                 named = isl_alloc_type(ctx, struct isl_named_obj);
 719                 if (!named)
 720                         goto error;
 721                 named->name = name;
 722                 entry->data = named;
 723         }
 724         named->obj = obj;
 725
 726         return 0;
 727 error:
 728         free_obj(obj);
 729         free(name);
 730         return -1;
 731 }
 732
 733 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 734         struct isl_hash_table *table, char *name)
 735 {
 736         struct isl_obj obj = { isl_obj_none, NULL };
 737         struct isl_hash_table_entry *entry;
 738         uint32_t name_hash;
 739
 740         name_hash = isl_hash_string(isl_hash_init(), name);
 741         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 742         if (entry) {
 743                 struct isl_named_obj *named;
 744                 named = entry->data;
 745                 obj = named->obj;
 746         } else
 747                 fprintf(stderr, "unknown identifier '%s'\n", name);
 748
 749         free(name);
 750         obj.v = obj.type->copy(obj.v);
 751         return obj;
 752 }
 753
 754 static int is_subtype(struct isl_obj obj, isl_obj_type super)
 755 {
 756         if (obj.type == super)
 757                 return 1;
 758         if (obj.type == isl_obj_map && super == isl_obj_union_map)
 759                 return 1;
 760         if (obj.type == isl_obj_set && super == isl_obj_union_set)
 761                 return 1;
 762         if (obj.type == isl_obj_pw_qpolynomial &&
 763             super == isl_obj_union_pw_qpolynomial)
 764                 return 1;
 765         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 766             super == isl_obj_union_pw_qpolynomial_fold)
 767                 return 1;
 768         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
 769                 return 1;
 770         if (obj.type == isl_obj_list) {
 771                 struct isl_list *list = obj.v;
 772                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
 773                         return is_subtype(list->obj[0], super);
 774         }
 775         if (super == isl_obj_str)
 776                 return 1;
 777         return 0;
 778 }
 779
 780 static struct isl_obj obj_at(struct isl_obj obj, int i)
 781 {
 782         struct isl_list *list = obj.v;
 783
 784         obj = list->obj[i];
 785         obj.v = obj.type->copy(obj.v);
 786
 787         isl_list_free(list);
 788
 789         return obj;
 790 }
 791
 792 static struct isl_obj convert(isl_ctx *ctx, struct isl_obj obj,
 793         isl_obj_type type)
 794 {
 795         if (obj.type == type)
 796                 return obj;
 797         if (obj.type == isl_obj_map && type == isl_obj_union_map) {
 798                 obj.type = isl_obj_union_map;
 799                 obj.v = isl_union_map_from_map(obj.v);
 800                 return obj;
 801         }
 802         if (obj.type == isl_obj_set && type == isl_obj_union_set) {
 803                 obj.type = isl_obj_union_set;
 804                 obj.v = isl_union_set_from_set(obj.v);
 805                 return obj;
 806         }
 807         if (obj.type == isl_obj_pw_qpolynomial &&
 808             type == isl_obj_union_pw_qpolynomial) {
 809                 obj.type = isl_obj_union_pw_qpolynomial;
 810                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
 811                 return obj;
 812         }
 813         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 814             type == isl_obj_union_pw_qpolynomial_fold) {
 815                 obj.type = isl_obj_union_pw_qpolynomial_fold;
 816                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
 817                 return obj;
 818         }
 819         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
 820                 if (type == isl_obj_union_map) {
 821                         obj.type = isl_obj_union_map;
 822                         return obj;
 823                 }
 824                 if (type == isl_obj_union_pw_qpolynomial) {
 825                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 826                         isl_union_set_free(obj.v);
 827                         obj.v = isl_union_pw_qpolynomial_zero(dim);
 828                         obj.type = isl_obj_union_pw_qpolynomial;
 829                         return obj;
 830                 }
 831                 if (type == isl_obj_union_pw_qpolynomial_fold) {
 832                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 833                         isl_union_set_free(obj.v);
 834                         obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
 835                                                                 isl_fold_list);
 836                         obj.type = isl_obj_union_pw_qpolynomial_fold;
 837                         return obj;
 838                 }
 839         }
 840         if (obj.type == isl_obj_list) {
 841                 struct isl_list *list = obj.v;
 842                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
 843                         return convert(ctx, obj_at(obj, 0), type);
 844         }
 845         if (type == isl_obj_str) {
 846                 isl_str *str;
 847                 isl_printer *p;
 848                 char *s;
 849
 850                 p = isl_printer_to_str(ctx);
 851                 if (!p)
 852                         goto error;
 853                 p = obj.type->print(p, obj.v);
 854                 s = isl_printer_get_str(p);
 855                 isl_printer_free(p);
 856
 857                 str = isl_str_alloc(ctx);
 858                 if (!str) {
 859                         free(s);
 860                         goto error;
 861                 }
 862                 str->s = s;
 863                 free_obj(obj);
 864                 obj.v = str;
 865                 obj.type = isl_obj_str;
 866                 return obj;
 867
 868         }
 869 error:
 870         free_obj(obj);
 871         obj.type = isl_obj_none;
 872         obj.v = NULL;
 873         return obj;
 874 }
 875
 876 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 877         struct isl_obj lhs)
 878 {
 879         int i;
 880         struct isl_token *tok;
 881
 882         tok = isl_stream_next_token(s);
 883         if (!tok)
 884                 return NULL;
 885
 886         for (i = 0; ; ++i) {
 887                 if (!bin_ops[i].op)
 888                         break;
 889                 if (bin_ops[i].op != tok->type)
 890                         continue;
 891                 if (!is_subtype(lhs, bin_ops[i].lhs))
 892                         continue;
 893
 894                 isl_token_free(tok);
 895                 return &bin_ops[i];
 896         }
 897
 898         for (i = 0; ; ++i) {
 899                 if (!named_bin_ops[i].name)
 900                         break;
 901                 if (named_bin_ops[i].op.op != tok->type)
 902                         continue;
 903                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
 904                         continue;
 905
 906                 isl_token_free(tok);
 907                 return &named_bin_ops[i].op;
 908         }
 909
 910         isl_stream_push_token(s, tok);
 911
 912         return NULL;
 913 }
 914
 915 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 916 {
 917         int i;
 918         struct isl_token *tok;
 919
 920         tok = isl_stream_next_token(s);
 921         if (!tok)
 922                 return NULL;
 923
 924         for (i = 0; ; ++i) {
 925                 if (!named_un_ops[i].name)
 926                         break;
 927                 if (named_un_ops[i].op.op != tok->type)
 928                         continue;
 929
 930                 isl_token_free(tok);
 931                 return &named_un_ops[i].op;
 932         }
 933
 934         isl_stream_push_token(s, tok);
 935
 936         return NULL;
 937 }
 938
 939 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 940         struct isl_obj arg)
 941 {
 942         int i;
 943
 944         for (i = 0; ; ++i) {
 945                 if (!named_un_ops[i].name)
 946                         break;
 947                 if (named_un_ops[i].op.op != like->op)
 948                         continue;
 949                 if (!is_subtype(arg, named_un_ops[i].op.arg))
 950                         continue;
 951
 952                 return &named_un_ops[i].op;
 953         }
 954
 955         return NULL;
 956 }
 957
 958 static int is_assign(struct isl_stream *s)
 959 {
 960         struct isl_token *tok;
 961         struct isl_token *tok2;
 962         int assign;
 963
 964         tok = isl_stream_next_token(s);
 965         if (!tok)
 966                 return 0;
 967         if (tok->type != ISL_TOKEN_IDENT) {
 968                 isl_stream_push_token(s, tok);
 969                 return 0;
 970         }
 971
 972         tok2 = isl_stream_next_token(s);
 973         if (!tok2) {
 974                 isl_stream_push_token(s, tok);
 975                 return 0;
 976         }
 977         assign = tok2->type == ISL_TOKEN_DEF;
 978         isl_stream_push_token(s, tok2);
 979         isl_stream_push_token(s, tok);
 980
 981         return assign;
 982 }
 983
 984 static struct isl_obj read_obj(struct isl_stream *s,
 985         struct isl_hash_table *table);
 986 static struct isl_obj read_expr(struct isl_stream *s,
 987         struct isl_hash_table *table);
 988
 989 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 990         struct isl_hash_table *table, struct isc_un_op *op)
 991 {
 992         struct isl_obj obj = { isl_obj_none, NULL };
 993
 994         obj = read_obj(s, table);
 995         if (!obj.v)
 996                 goto error;
 997
 998         op = find_matching_un_op(op, obj);
 999
1000         isl_assert(s->ctx, op, goto error);
1001         obj = convert(s->ctx, obj, op->arg);
1002         obj.v = op->fn(obj.v);
1003         obj.type = op->res;
1004
1005         return obj;
1006 error:
1007         free_obj(obj);
1008         obj.type = isl_obj_none;
1009         obj.v = NULL;
1010         return obj;
1011 }
1012
1013 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
1014 {
1015         struct isl_list *list;
1016         int exact;
1017
1018         if (obj.type != isl_obj_union_map)
1019                 obj = convert(ctx, obj, isl_obj_union_map);
1020         isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
1021         list = isl_list_alloc(ctx, 2);
1022         if (!list)
1023                 goto error;
1024
1025         list->obj[0].type = isl_obj_union_map;
1026         list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
1027         list->obj[1].type = isl_obj_bool;
1028         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
1029         obj.v = list;
1030         obj.type = isl_obj_list;
1031         if (exact < 0 || !list->obj[0].v)
1032                 goto error;
1033
1034         return obj;
1035 error:
1036         free_obj(obj);
1037         obj.type = isl_obj_none;
1038         obj.v = NULL;
1039         return obj;
1040 }
1041
1042 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
1043 {
1044         struct isl_list *list = obj.v;
1045         struct isl_token *tok;
1046         int i;
1047
1048         tok = isl_stream_next_token(s);
1049         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1050                 isl_stream_error(s, tok, "expecting index");
1051                 if (tok)
1052                         isl_stream_push_token(s, tok);
1053                 goto error;
1054         }
1055         i = isl_int_get_si(tok->u.v);
1056         isl_token_free(tok);
1057         isl_assert(s->ctx, i < list->n, goto error);
1058         if (isl_stream_eat(s, ']'))
1059                 goto error;
1060
1061         return obj_at(obj, i);
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 apply(struct isl_stream *s, __isl_take isl_union_map *umap,
1070         struct isl_hash_table *table)
1071 {
1072         struct isl_obj obj;
1073
1074         obj = read_expr(s, table);
1075         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
1076                            is_subtype(obj, isl_obj_union_map), goto error);
1077
1078         if (obj.type == isl_obj_list) {
1079                 struct isl_list *list = obj.v;
1080                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1081                         obj = obj_at(obj, 0);
1082         }
1083         if (obj.type == isl_obj_set)
1084                 obj = convert(s->ctx, obj, isl_obj_union_set);
1085         else if (obj.type == isl_obj_map)
1086                 obj = convert(s->ctx, obj, isl_obj_union_map);
1087         if (obj.type == isl_obj_union_set) {
1088                 obj.v = isl_union_set_apply(obj.v, umap);
1089         } else
1090                 obj.v = isl_union_map_apply_range(obj.v, umap);
1091         if (!obj.v)
1092                 goto error2;
1093
1094         if (isl_stream_eat(s, ')'))
1095                 goto error2;
1096
1097         return obj;
1098 error:
1099         isl_union_map_free(umap);
1100 error2:
1101         free_obj(obj);
1102         obj.type = isl_obj_none;
1103         obj.v = NULL;
1104         return obj;
1105 }
1106
1107 static struct isl_obj apply_fun(struct isl_stream *s,
1108         struct isl_obj obj, struct isl_hash_table *table)
1109 {
1110         struct isl_obj arg;
1111
1112         arg = read_expr(s, table);
1113         isl_assert(s->ctx, is_subtype(arg, isl_obj_union_map), goto error);
1114
1115         if (arg.type == isl_obj_list) {
1116                 struct isl_list *list = arg.v;
1117                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1118                         arg = obj_at(arg, 0);
1119         }
1120         if (arg.type == isl_obj_map)
1121                 arg = convert(s->ctx, arg, isl_obj_union_map);
1122         if (obj.type == isl_obj_union_pw_qpolynomial) {
1123                 obj.v = isl_union_map_apply_union_pw_qpolynomial(arg.v, obj.v);
1124         } else {
1125                 obj.type = isl_obj_list;
1126                 obj.v = union_map_apply_union_pw_qpolynomial_fold(arg.v, obj.v);
1127         }
1128         if (!obj.v)
1129                 goto error2;
1130
1131         if (isl_stream_eat(s, ')'))
1132                 goto error2;
1133
1134         return obj;
1135 error:
1136         free_obj(arg);
1137 error2:
1138         free_obj(obj);
1139         obj.type = isl_obj_none;
1140         obj.v = NULL;
1141         return obj;
1142 }
1143
1144 struct add_vertex_data {
1145         struct isl_list *list;
1146         int i;
1147 };
1148
1149 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
1150 {
1151         struct add_vertex_data *data = (struct add_vertex_data *)user;
1152         isl_basic_set *expr;
1153
1154         expr = isl_vertex_get_expr(vertex);
1155
1156         data->list->obj[data->i].type = isl_obj_set;
1157         data->list->obj[data->i].v = isl_set_from_basic_set(expr);
1158         data->i++;
1159
1160         isl_vertex_free(vertex);
1161
1162         return 0;
1163 }
1164
1165 static int set_vertices(__isl_take isl_set *set, void *user)
1166 {
1167         isl_ctx *ctx;
1168         isl_basic_set *hull;
1169         isl_vertices *vertices = NULL;
1170         struct isl_list *list = NULL;
1171         int r;
1172         struct add_vertex_data *data = (struct add_vertex_data *)user;
1173
1174         set = isl_set_remove_divs(set);
1175         hull = isl_set_convex_hull(set);
1176         vertices = isl_basic_set_compute_vertices(hull);
1177         isl_basic_set_free(hull);
1178
1179         list = data->list;
1180
1181         ctx = isl_vertices_get_ctx(vertices);
1182         data->list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1183         if (!data->list)
1184                 goto error;
1185
1186         data->i = 0;
1187         r = isl_vertices_foreach_vertex(vertices, &add_vertex, user);
1188
1189         data->list = isl_list_concat(list, data->list);
1190
1191         isl_vertices_free(vertices);
1192
1193         return r;
1194 error:
1195         data->list = list;
1196         isl_vertices_free(vertices);
1197         return -1;
1198 }
1199
1200 static struct isl_obj vertices(struct isl_stream *s,
1201         struct isl_hash_table *table)
1202 {
1203         isl_ctx *ctx;
1204         struct isl_obj obj;
1205         struct isl_list *list = NULL;
1206         isl_union_set *uset;
1207         struct add_vertex_data data = { NULL };
1208
1209         obj = read_expr(s, table);
1210         obj = convert(s->ctx, obj, isl_obj_union_set);
1211         isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1212         uset = obj.v;
1213         obj.v = NULL;
1214
1215         ctx = isl_union_set_get_ctx(uset);
1216         list = isl_list_alloc(ctx, 0);
1217         if (!list)
1218                 goto error;
1219
1220         data.list = list;
1221
1222         if (isl_union_set_foreach_set(uset, &set_vertices, &data) < 0)
1223                 goto error;
1224
1225         isl_union_set_free(uset);
1226
1227         obj.type = isl_obj_list;
1228         obj.v = data.list;
1229
1230         return obj;
1231 error:
1232         isl_union_set_free(uset);
1233         isl_list_free(data.list);
1234         free_obj(obj);
1235         obj.type = isl_obj_none;
1236         obj.v = NULL;
1237         return obj;
1238 }
1239
1240 static __isl_give isl_union_map *read_map(struct isl_stream *s,
1241         struct isl_hash_table *table)
1242 {
1243         struct isl_obj obj;
1244
1245         obj = read_obj(s, table);
1246         obj = convert(s->ctx, obj, isl_obj_union_map);
1247         isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error);
1248         return obj.v;
1249 error:
1250         free_obj(obj);
1251         return NULL;
1252 }
1253
1254 static struct isl_obj last_any(struct isl_stream *s,
1255         struct isl_hash_table *table, __isl_take isl_union_map *must_source,
1256         __isl_take isl_union_map *may_source)
1257 {
1258         struct isl_obj obj = { isl_obj_none, NULL };
1259         isl_union_map *sink = NULL;
1260         isl_union_map *schedule = NULL;
1261         isl_union_map *may_dep;
1262         isl_union_map *must_dep;
1263
1264         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1265                 goto error;
1266
1267         sink = read_map(s, table);
1268         if (!sink)
1269                 goto error;
1270
1271         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1272                 goto error;
1273
1274         schedule = read_map(s, table);
1275         if (!schedule)
1276                 goto error;
1277
1278         if (isl_union_map_compute_flow(sink, must_source, may_source,
1279                                        schedule, &must_dep, &may_dep,
1280                                        NULL, NULL) < 0)
1281                 return obj;
1282
1283         obj.type = isl_obj_union_map;
1284         obj.v = isl_union_map_union(must_dep, may_dep);
1285
1286         return obj;
1287 error:
1288         isl_union_map_free(may_source);
1289         isl_union_map_free(must_source);
1290         isl_union_map_free(sink);
1291         isl_union_map_free(schedule);
1292         free_obj(obj);
1293         obj.type = isl_obj_none;
1294         obj.v = NULL;
1295         return obj;
1296 }
1297
1298 static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table)
1299 {
1300         struct isl_obj obj = { isl_obj_none, NULL };
1301         isl_union_map *must_source = NULL;
1302         isl_union_map *may_source = NULL;
1303         isl_union_map *sink = NULL;
1304         isl_union_map *schedule = NULL;
1305         isl_union_map *may_dep;
1306
1307         may_source = read_map(s, table);
1308         if (!may_source)
1309                 goto error;
1310
1311         if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) {
1312                 must_source = read_map(s, table);
1313                 if (!must_source)
1314                         goto error;
1315                 return last_any(s, table, must_source, may_source);
1316         }
1317
1318         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1319                 goto error;
1320
1321         sink = read_map(s, table);
1322         if (!sink)
1323                 goto error;
1324
1325         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1326                 goto error;
1327
1328         schedule = read_map(s, table);
1329         if (!schedule)
1330                 goto error;
1331
1332         must_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1333         if (isl_union_map_compute_flow(sink, must_source, may_source,
1334                                        schedule, NULL, &may_dep,
1335                                        NULL, NULL) < 0)
1336                 return obj;
1337
1338         obj.type = isl_obj_union_map;
1339         obj.v = may_dep;
1340
1341         return obj;
1342 error:
1343         isl_union_map_free(may_source);
1344         isl_union_map_free(must_source);
1345         isl_union_map_free(sink);
1346         isl_union_map_free(schedule);
1347         free_obj(obj);
1348         obj.type = isl_obj_none;
1349         obj.v = NULL;
1350         return obj;
1351 }
1352
1353 static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table)
1354 {
1355         struct isl_obj obj = { isl_obj_none, NULL };
1356         struct isl_list *list = NULL;
1357         isl_union_map *must_source = NULL;
1358         isl_union_map *may_source = NULL;
1359         isl_union_map *sink = NULL;
1360         isl_union_map *schedule = NULL;
1361         isl_union_map *must_dep;
1362         isl_union_set *must_no_source;
1363
1364         must_source = read_map(s, table);
1365         if (!must_source)
1366                 goto error;
1367
1368         if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) {
1369                 may_source = read_map(s, table);
1370                 if (!may_source)
1371                         goto error;
1372                 return last_any(s, table, must_source, may_source);
1373         }
1374
1375         list = isl_list_alloc(s->ctx, 2);
1376         if (!list)
1377                 goto error;
1378
1379         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1380                 goto error;
1381
1382         sink = read_map(s, table);
1383         if (!sink)
1384                 goto error;
1385
1386         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1387                 goto error;
1388
1389         schedule = read_map(s, table);
1390         if (!schedule)
1391                 goto error;
1392
1393         may_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1394         if (isl_union_map_compute_flow(sink, must_source, may_source,
1395                                        schedule, &must_dep, NULL,
1396                                        &must_no_source, NULL) < 0)
1397                 return obj;
1398
1399         list->obj[0].type = isl_obj_union_map;
1400         list->obj[0].v = must_dep;
1401         list->obj[1].type = isl_obj_union_set;
1402         list->obj[1].v = must_no_source;
1403
1404         obj.v = list;
1405         obj.type = isl_obj_list;
1406
1407         return obj;
1408 error:
1409         isl_list_free(list);
1410         isl_union_map_free(may_source);
1411         isl_union_map_free(must_source);
1412         isl_union_map_free(sink);
1413         isl_union_map_free(schedule);
1414         free_obj(obj);
1415         obj.type = isl_obj_none;
1416         obj.v = NULL;
1417         return obj;
1418 }
1419
1420 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1421 {
1422         struct isl_token *tok;
1423
1424         if (isl_stream_eat_if_available(s, '+'))
1425                 return transitive_closure(s->ctx, obj);
1426
1427         tok = isl_stream_next_token(s);
1428         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
1429                 isl_stream_error(s, tok, "expecting -1");
1430                 if (tok)
1431                         isl_stream_push_token(s, tok);
1432                 goto error;
1433         }
1434         isl_token_free(tok);
1435         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1436         if (obj.type != isl_obj_union_map)
1437                 obj = convert(s->ctx, obj, isl_obj_union_map);
1438
1439         obj.v = isl_union_map_reverse(obj.v);
1440         if (!obj.v)
1441                 goto error;
1442
1443         return obj;
1444 error:
1445         free_obj(obj);
1446         obj.type = isl_obj_none;
1447         obj.v = NULL;
1448         return obj;
1449 }
1450
1451 static struct isl_obj read_from_file(struct isl_stream *s)
1452 {
1453         struct isl_obj obj;
1454         struct isl_token *tok;
1455         struct isl_stream *s_file;
1456         FILE *file;
1457
1458         tok = isl_stream_next_token(s);
1459         if (!tok || tok->type != ISL_TOKEN_STRING) {
1460                 isl_stream_error(s, tok, "expecting filename");
1461                 isl_token_free(tok);
1462                 goto error;
1463         }
1464
1465         file = fopen(tok->u.s, "r");
1466         isl_token_free(tok);
1467         isl_assert(s->ctx, file, goto error);
1468
1469         s_file = isl_stream_new_file(s->ctx, file);
1470         if (!s_file) {
1471                 fclose(file);
1472                 goto error;
1473         }
1474
1475         obj = isl_stream_read_obj(s_file);
1476
1477         isl_stream_free(s_file);
1478         fclose(file);
1479
1480         return obj;
1481 error:
1482         obj.type = isl_obj_none;
1483         obj.v = NULL;
1484         return obj;
1485 }
1486
1487 static struct isl_obj read_string_if_available(struct isl_stream *s)
1488 {
1489         struct isl_token *tok;
1490         struct isl_obj obj = { isl_obj_none, NULL };
1491
1492         tok = isl_stream_next_token(s);
1493         if (!tok)
1494                 return obj;
1495         if (tok->type == ISL_TOKEN_STRING) {
1496                 isl_str *str;
1497                 str = isl_str_alloc(s->ctx);
1498                 if (!str)
1499                         goto error;
1500                 str->s = strdup(tok->u.s);
1501                 isl_token_free(tok);
1502                 obj.v = str;
1503                 obj.type = isl_obj_str;
1504         } else
1505                 isl_stream_push_token(s, tok);
1506         return obj;
1507 error:
1508         isl_token_free(tok);
1509         return obj;
1510 }
1511
1512 static struct isl_obj read_obj(struct isl_stream *s,
1513         struct isl_hash_table *table)
1514 {
1515         struct isl_obj obj = { isl_obj_none, NULL };
1516         char *name = NULL;
1517         struct isc_un_op *op = NULL;
1518
1519         obj = read_string_if_available(s);
1520         if (obj.v)
1521                 return obj;
1522         if (isl_stream_eat_if_available(s, '(')) {
1523                 obj = read_expr(s, table);
1524                 if (!obj.v || isl_stream_eat(s, ')'))
1525                         goto error;
1526         } else {
1527                 op = read_prefix_un_op_if_available(s);
1528                 if (op)
1529                         return read_un_op_expr(s, table, op);
1530
1531                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_READ]))
1532                         return read_from_file(s);
1533                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES]))
1534                         return vertices(s, table);
1535                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY]))
1536                         return any(s, table);
1537                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST]))
1538                         return last(s, table);
1539
1540                 name = isl_stream_read_ident_if_available(s);
1541                 if (name)
1542                         obj = stored_obj(s->ctx, table, name);
1543                 else
1544                         obj = isl_stream_read_obj(s);
1545                 if (!obj.v)
1546                         goto error;
1547         }
1548
1549         if (isl_stream_eat_if_available(s, '^'))
1550                 obj = power(s, obj);
1551         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1552                 obj = obj_at_index(s, obj);
1553         else if (is_subtype(obj, isl_obj_union_map) &&
1554                  isl_stream_eat_if_available(s, '(')) {
1555                 obj = convert(s->ctx, obj, isl_obj_union_map);
1556                 obj = apply(s, obj.v, table);
1557         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial) &&
1558                    isl_stream_eat_if_available(s, '(')) {
1559                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial);
1560                 obj = apply_fun(s, obj, table);
1561         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial_fold) &&
1562                    isl_stream_eat_if_available(s, '(')) {
1563                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial_fold);
1564                 obj = apply_fun(s, obj, table);
1565         }
1566
1567         return obj;
1568 error:
1569         free_obj(obj);
1570         obj.type = isl_obj_none;
1571         obj.v = NULL;
1572         return obj;
1573 }
1574
1575 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1576         struct isl_obj lhs, struct isl_obj rhs)
1577 {
1578         int i;
1579
1580         for (i = 0; ; ++i) {
1581                 if (!bin_ops[i].op)
1582                         break;
1583                 if (bin_ops[i].op != like->op)
1584                         continue;
1585                 if (!is_subtype(lhs, bin_ops[i].lhs))
1586                         continue;
1587                 if (!is_subtype(rhs, bin_ops[i].rhs))
1588                         continue;
1589
1590                 return &bin_ops[i];
1591         }
1592
1593         for (i = 0; ; ++i) {
1594                 if (!named_bin_ops[i].name)
1595                         break;
1596                 if (named_bin_ops[i].op.op != like->op)
1597                         continue;
1598                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1599                         continue;
1600                 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1601                         continue;
1602
1603                 return &named_bin_ops[i].op;
1604         }
1605
1606         return NULL;
1607 }
1608
1609 static struct isl_obj read_expr(struct isl_stream *s,
1610         struct isl_hash_table *table)
1611 {
1612         struct isl_obj obj = { isl_obj_none, NULL };
1613         struct isl_obj right_obj = { isl_obj_none, NULL };
1614
1615         obj = read_obj(s, table);
1616         for (; obj.v;) {
1617                 struct isc_bin_op *op = NULL;
1618
1619                 op = read_bin_op_if_available(s, obj);
1620                 if (!op)
1621                         break;
1622
1623                 right_obj = read_obj(s, table);
1624
1625                 op = find_matching_bin_op(op, obj, right_obj);
1626
1627                 isl_assert(s->ctx, op, goto error);
1628                 obj = convert(s->ctx, obj, op->lhs);
1629                 right_obj = convert(s->ctx, right_obj, op->rhs);
1630                 obj.v = op->fn(obj.v, right_obj.v);
1631                 obj.type = op->res;
1632         }
1633
1634         return obj;
1635 error:
1636         free_obj(right_obj);
1637         free_obj(obj);
1638         obj.type = isl_obj_none;
1639         obj.v = NULL;
1640         return obj;
1641 }
1642
1643 static __isl_give isl_printer *source_file(struct isl_stream *s,
1644         struct isl_hash_table *table, __isl_take isl_printer *p);
1645
1646 static __isl_give isl_printer *read_line(struct isl_stream *s,
1647         struct isl_hash_table *table, __isl_take isl_printer *p)
1648 {
1649         struct isl_obj obj = { isl_obj_none, NULL };
1650         char *lhs = NULL;
1651         int assign = 0;
1652         struct isc_bin_op *op = NULL;
1653
1654         if (!p)
1655                 return NULL;
1656         if (isl_stream_is_empty(s))
1657                 return p;
1658
1659         if (isl_stream_eat_if_available(s, iscc_op[ISCC_SOURCE]))
1660                 return source_file(s, table, p);
1661
1662         assign = is_assign(s);
1663         if (assign) {
1664                 lhs = isl_stream_read_ident_if_available(s);
1665                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1666                         goto error;
1667         }
1668
1669         obj = read_expr(s, table);
1670         if (obj.type == isl_obj_none || obj.v == NULL)
1671                 goto error;
1672         if (isl_stream_eat(s, ';'))
1673                 goto error;
1674
1675         if (assign) {
1676                 if (do_assign(s->ctx, table, lhs, obj))
1677                         return;
1678         } else {
1679                 p = obj.type->print(p, obj.v);
1680                 p = isl_printer_end_line(p);
1681                 free_obj(obj);
1682         }
1683
1684         return p;
1685 error:
1686         isl_stream_flush_tokens(s);
1687         isl_stream_skip_line(s);
1688         free(lhs);
1689         free_obj(obj);
1690         return p;
1691 }
1692
1693 int free_cb(void **entry, void *user)
1694 {
1695         struct isl_named_obj *named = *entry;
1696
1697         free_obj(named->obj);
1698         free(named->name);
1699         free(named);
1700
1701         return 0;
1702 }
1703
1704 static void register_named_ops(struct isl_stream *s)
1705 {
1706         int i;
1707
1708         for (i = 0; i < ISCC_N_OP; ++i) {
1709                 iscc_op[i] = isl_stream_register_keyword(s, op_name[i]);
1710                 assert(iscc_op[i] != ISL_TOKEN_ERROR);
1711         }
1712
1713         for (i = 0; ; ++i) {
1714                 if (!named_un_ops[i].name)
1715                         break;
1716                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1717                                                         named_un_ops[i].name);
1718                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1719         }
1720
1721         for (i = 0; ; ++i) {
1722                 if (!named_bin_ops[i].name)
1723                         break;
1724                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1725                                                         named_bin_ops[i].name);
1726                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1727         }
1728 }
1729
1730 static __isl_give isl_printer *source_file(struct isl_stream *s,
1731         struct isl_hash_table *table, __isl_take isl_printer *p)
1732 {
1733         struct isl_token *tok;
1734         struct isl_stream *s_file;
1735         FILE *file;
1736
1737         tok = isl_stream_next_token(s);
1738         if (!tok || tok->type != ISL_TOKEN_STRING) {
1739                 isl_stream_error(s, tok, "expecting filename");
1740                 isl_token_free(tok);
1741                 return p;
1742         }
1743
1744         file = fopen(tok->u.s, "r");
1745         isl_token_free(tok);
1746         isl_assert(s->ctx, file, return p);
1747
1748         s_file = isl_stream_new_file(s->ctx, file);
1749         if (!s_file) {
1750                 fclose(file);
1751                 return p;
1752         }
1753
1754         register_named_ops(s_file);
1755
1756         while (!s_file->eof)
1757                 p = read_line(s_file, table, p);
1758
1759         isl_stream_free(s_file);
1760         fclose(file);
1761
1762         isl_stream_eat(s, ';');
1763
1764         return p;
1765 }
1766
1767 int main(int argc, char **argv)
1768 {
1769         struct isl_ctx *ctx;
1770         struct isl_stream *s;
1771         struct isl_hash_table *table;
1772         struct iscc_options *options;
1773         isl_printer *p;
1774
1775         options = iscc_options_new_with_defaults();
1776         assert(options);
1777         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
1778
1779         ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
1780         s = isl_stream_new_file(ctx, stdin);
1781         assert(s);
1782         table = isl_hash_table_alloc(ctx, 10);
1783         assert(table);
1784         p = isl_printer_to_file(ctx, stdout);
1785         p = isl_printer_set_output_format(p, options->format);
1786         assert(p);
1787
1788         register_named_ops(s);
1789
1790         while (p && !s->eof) {
1791                 p = read_line(s, table, p);
1792         }
1793
1794         isl_printer_free(p);
1795         isl_hash_table_foreach(ctx, table, free_cb, NULL);
1796         isl_hash_table_free(ctx, table);
1797         isl_stream_free(s);
1798         isl_ctx_free(ctx);
1799
1800         return 0;
1801 }