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