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