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