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