X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_input.c;h=a1cf268b36a4ae223b72ba45f7044858d57311ec;hb=264fb60022ac3e67a8453d73086816d6bdc5e425;hp=4f472ff57c5bed6016f81b995476565f8df320fe;hpb=67fc9fa26dc328e157c46682167f216f897c115f;p=platform%2Fupstream%2Fisl.git diff --git a/isl_input.c b/isl_input.c index 4f472ff..a1cf268 100644 --- a/isl_input.c +++ b/isl_input.c @@ -13,17 +13,24 @@ #include #include #include -#include -#include -#include -#include "isl_stream.h" -#include "isl_map_private.h" -#include "isl_obj.h" +#include +#include +#include +#include +#include +#include +#include #include "isl_polynomial_private.h" +#include +#include struct variable { char *name; int pos; + isl_vec *def; + /* non-zero if variable represents a min (-1) or a max (1) */ + int sign; + isl_mat *list; struct variable *next; }; @@ -49,6 +56,8 @@ static void variable_free(struct variable *var) { while (var) { struct variable *next = var->next; + isl_mat_free(var->list); + isl_vec_free(var->def); free(var->name); free(var); var = next; @@ -67,7 +76,7 @@ static void vars_drop(struct vars *v, int n) { struct variable *var; - if (!v) + if (!v || !v->v) return; v->n -= n; @@ -75,6 +84,8 @@ static void vars_drop(struct vars *v, int n) var = v->v; while (--n >= 0) { struct variable *next = var->next; + isl_mat_free(var->list); + isl_vec_free(var->def); free(var->name); free(var); var = next; @@ -86,12 +97,13 @@ static struct variable *variable_new(struct vars *v, const char *name, int len, int pos) { struct variable *var; - var = isl_alloc_type(v->ctx, struct variable); + var = isl_calloc_type(v->ctx, struct variable); if (!var) goto error; var->name = strdup(name); var->name[len] = '\0'; var->pos = pos; + var->def = NULL; var->next = v->v; return var; error: @@ -122,6 +134,17 @@ static int vars_pos(struct vars *v, const char *s, int len) return pos; } +static int vars_add_anon(struct vars *v) +{ + v->v = variable_new(v, "", 0, v->n); + + if (!v->v) + return -1; + v->n++; + + return 0; +} + static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, char *name) { @@ -135,16 +158,221 @@ static __isl_give isl_basic_map *set_name(__isl_take isl_basic_map *bmap, prime = strchr(name, '\''); if (prime) *prime = '\0'; - bmap->dim = isl_dim_set_name(bmap->dim, type, pos, name); + bmap = isl_basic_map_set_dim_name(bmap, type, pos, name); if (prime) *prime = '\''; - if (!bmap->dim) + return bmap; +} + +/* Obtain next token, with some preprocessing. + * In particular, evaluate expressions of the form x^y, + * with x and y values. + */ +static struct isl_token *next_token(struct isl_stream *s) +{ + struct isl_token *tok, *tok2; + + tok = isl_stream_next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) + return tok; + if (!isl_stream_eat_if_available(s, '^')) + return tok; + tok2 = isl_stream_next_token(s); + if (!tok2 || tok2->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok2, "expecting constant value"); goto error; + } - return bmap; + isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v)); + + isl_token_free(tok2); + return tok; error: - isl_basic_map_free(bmap); + isl_token_free(tok); + isl_token_free(tok2); + return NULL; +} + +static int accept_cst_factor(struct isl_stream *s, isl_int *f) +{ + struct isl_token *tok; + + tok = next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting constant value"); + goto error; + } + + isl_int_mul(*f, *f, tok->u.v); + + isl_token_free(tok); + + if (isl_stream_eat_if_available(s, '*')) + return accept_cst_factor(s, f); + + return 0; +error: + isl_token_free(tok); + return -1; +} + +/* Given an affine expression aff, return an affine expression + * for aff % d, with d the next token on the stream, which is + * assumed to be a constant. + * + * We introduce an integer division q = [aff/d] and the result + * is set to aff - d q. + */ +static __isl_give isl_vec *affine_mod(struct isl_stream *s, + struct vars *v, __isl_take isl_vec *aff) +{ + struct isl_token *tok; + struct variable *var; + isl_vec *mod; + + tok = next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting constant value"); + goto error; + } + + if (vars_add_anon(v) < 0) + goto error; + + var = v->v; + + var->def = isl_vec_alloc(s->ctx, 2 + v->n); + if (!var->def) + goto error; + isl_seq_cpy(var->def->el + 1, aff->el, aff->size); + isl_int_set_si(var->def->el[1 + aff->size], 0); + isl_int_set(var->def->el[0], tok->u.v); + + mod = isl_vec_alloc(v->ctx, 1 + v->n); + if (!mod) + goto error; + + isl_seq_cpy(mod->el, aff->el, aff->size); + isl_int_neg(mod->el[aff->size], tok->u.v); + + isl_vec_free(aff); + isl_token_free(tok); + return mod; +error: + isl_vec_free(aff); + isl_token_free(tok); + return NULL; +} + +static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v); +static int read_div_definition(struct isl_stream *s, struct vars *v); +static int read_minmax_definition(struct isl_stream *s, struct vars *v); + +static __isl_give isl_vec *accept_affine_factor(struct isl_stream *s, + struct vars *v) +{ + struct isl_token *tok = NULL; + isl_vec *aff = NULL; + + tok = next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + goto error; + } + if (tok->type == ISL_TOKEN_IDENT) { + int n = v->n; + int pos = vars_pos(v, tok->u.s, -1); + if (pos < 0) + goto error; + if (pos >= n) { + isl_stream_error(s, tok, "unknown identifier"); + goto error; + } + + aff = isl_vec_alloc(v->ctx, 1 + v->n); + if (!aff) + goto error; + isl_seq_clr(aff->el, aff->size); + isl_int_set_si(aff->el[1 + pos], 1); + isl_token_free(tok); + } else if (tok->type == ISL_TOKEN_VALUE) { + if (isl_stream_eat_if_available(s, '*')) { + aff = accept_affine_factor(s, v); + aff = isl_vec_scale(aff, tok->u.v); + } else { + aff = isl_vec_alloc(v->ctx, 1 + v->n); + if (!aff) + goto error; + isl_seq_clr(aff->el, aff->size); + isl_int_set(aff->el[0], tok->u.v); + } + isl_token_free(tok); + } else if (tok->type == '(') { + isl_token_free(tok); + tok = NULL; + aff = accept_affine(s, v); + if (!aff) + goto error; + if (isl_stream_eat(s, ')')) + goto error; + } else if (tok->type == '[' || + tok->type == ISL_TOKEN_FLOORD || + tok->type == ISL_TOKEN_CEILD) { + int ceil = tok->type == ISL_TOKEN_CEILD; + struct variable *var; + if (vars_add_anon(v) < 0) + goto error; + var = v->v; + aff = isl_vec_alloc(v->ctx, 1 + v->n); + if (!aff) + goto error; + isl_seq_clr(aff->el, aff->size); + isl_int_set_si(aff->el[1 + v->n - 1], ceil ? -1 : 1); + isl_stream_push_token(s, tok); + tok = NULL; + if (read_div_definition(s, v) < 0) + goto error; + if (ceil) + isl_seq_neg(var->def->el + 1, var->def->el + 1, + var->def->size - 1); + aff = isl_vec_zero_extend(aff, 1 + v->n); + } else if (tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX) { + if (vars_add_anon(v) < 0) + goto error; + aff = isl_vec_alloc(v->ctx, 1 + v->n); + if (!aff) + goto error; + isl_seq_clr(aff->el, aff->size); + isl_int_set_si(aff->el[1 + v->n - 1], 1); + isl_stream_push_token(s, tok); + tok = NULL; + if (read_minmax_definition(s, v) < 0) + goto error; + aff = isl_vec_zero_extend(aff, 1 + v->n); + } else { + isl_stream_error(s, tok, "expecting factor"); + goto error; + } + if (isl_stream_eat_if_available(s, '%')) + return affine_mod(s, v, aff); + if (isl_stream_eat_if_available(s, '*')) { + isl_int f; + isl_int_init(f); + isl_int_set_si(f, 1); + if (accept_cst_factor(s, &f) < 0) { + isl_int_clear(f); + goto error2; + } + aff = isl_vec_scale(aff, f); + isl_int_clear(f); + } + + return aff; +error: + isl_token_free(tok); +error2: + isl_vec_free(aff); return NULL; } @@ -155,81 +383,173 @@ static struct isl_vec *accept_affine(struct isl_stream *s, struct vars *v) int sign = 1; aff = isl_vec_alloc(v->ctx, 1 + v->n); - isl_seq_clr(aff->el, aff->size); if (!aff) return NULL; + isl_seq_clr(aff->el, aff->size); for (;;) { - tok = isl_stream_next_token(s); + tok = next_token(s); if (!tok) { isl_stream_error(s, NULL, "unexpected EOF"); goto error; } - if (tok->type == ISL_TOKEN_IDENT) { - int n = v->n; - int pos = vars_pos(v, tok->u.s, -1); - if (pos < 0) - goto error; - if (pos >= n) { - isl_stream_error(s, tok, "unknown identifier"); - isl_token_free(tok); + if (tok->type == '-') { + sign = -sign; + isl_token_free(tok); + continue; + } + if (tok->type == '(' || tok->type == '[' || + tok->type == ISL_TOKEN_MIN || tok->type == ISL_TOKEN_MAX || + tok->type == ISL_TOKEN_FLOORD || + tok->type == ISL_TOKEN_CEILD || + tok->type == ISL_TOKEN_IDENT) { + isl_vec *aff2; + isl_stream_push_token(s, tok); + tok = NULL; + aff2 = accept_affine_factor(s, v); + if (sign < 0) + aff2 = isl_vec_scale(aff2, s->ctx->negone); + aff = isl_vec_zero_extend(aff, 1 + v->n); + aff = isl_vec_add(aff, aff2); + if (!aff) goto error; - } - if (sign > 0) - isl_int_add_ui(aff->el[1 + pos], - aff->el[1 + pos], 1); - else - isl_int_sub_ui(aff->el[1 + pos], - aff->el[1 + pos], 1); sign = 1; } else if (tok->type == ISL_TOKEN_VALUE) { - struct isl_token *tok2; - int n = v->n; - int pos = -1; - tok2 = isl_stream_next_token(s); - if (tok2 && tok2->type == ISL_TOKEN_IDENT) { - pos = vars_pos(v, tok2->u.s, -1); - if (pos < 0) - goto error; - if (pos >= n) { - isl_stream_error(s, tok2, - "unknown identifier"); - isl_token_free(tok); - isl_token_free(tok2); - goto error; - } - isl_token_free(tok2); - } else if (tok2) - isl_stream_push_token(s, tok2); if (sign < 0) isl_int_neg(tok->u.v, tok->u.v); - isl_int_add(aff->el[1 + pos], - aff->el[1 + pos], tok->u.v); + if (isl_stream_eat_if_available(s, '*') || + isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { + isl_vec *aff2; + aff2 = accept_affine_factor(s, v); + aff2 = isl_vec_scale(aff2, tok->u.v); + aff = isl_vec_zero_extend(aff, 1 + v->n); + aff = isl_vec_add(aff, aff2); + if (!aff) + goto error; + } else { + isl_int_add(aff->el[0], aff->el[0], tok->u.v); + } sign = 1; - } else if (tok->type == '-') { + } else { + isl_stream_error(s, tok, "unexpected isl_token"); + isl_stream_push_token(s, tok); + isl_vec_free(aff); + return NULL; + } + isl_token_free(tok); + + tok = next_token(s); + if (tok && tok->type == '-') { sign = -sign; - } else if (tok->type == '+') { + isl_token_free(tok); + } else if (tok && tok->type == '+') { /* nothing */ - } else { + isl_token_free(tok); + } else if (tok && tok->type == ISL_TOKEN_VALUE && + isl_int_is_neg(tok->u.v)) { isl_stream_push_token(s, tok); + } else { + if (tok) + isl_stream_push_token(s, tok); break; } - isl_token_free(tok); } return aff; error: + isl_token_free(tok); isl_vec_free(aff); return NULL; } +/* Add any variables in the variable list "v" that are not already in "bmap" + * as existentially quantified variables in "bmap". + */ +static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap, + struct vars *v) +{ + int i; + int extra; + struct variable *var; + + extra = v->n - isl_basic_map_total_dim(bmap); + + if (extra == 0) + return bmap; + + bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap), + extra, 0, 2 * extra); + + for (i = 0; i < extra; ++i) + if (isl_basic_map_alloc_div(bmap) < 0) + goto error; + + for (i = 0, var = v->v; i < extra; ++i, var = var->next) { + int k = bmap->n_div - 1 - i; + + isl_seq_cpy(bmap->div[k], var->def->el, var->def->size); + isl_seq_clr(bmap->div[k] + var->def->size, + 2 + v->n - var->def->size); + + if (isl_basic_map_add_div_constraints(bmap, k) < 0) + goto error; + } + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +static __isl_give isl_basic_map *read_var_def(struct isl_stream *s, + __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) +{ + isl_dim *dim; + isl_basic_map *def = NULL; + struct isl_vec *vec; + int k; + int n; + + if (vars_add_anon(v) < 0) + goto error; + n = v->n; + + vec = accept_affine(s, v); + if (!vec) + goto error; + + dim = isl_basic_map_get_dim(bmap); + def = isl_basic_map_universe(dim); + def = add_divs(def, v); + def = isl_basic_map_extend_constraints(def, 1, 0); + k = isl_basic_map_alloc_equality(def); + if (k >= 0) { + isl_seq_cpy(def->eq[k], vec->el, vec->size); + isl_int_set_si(def->eq[k][1 + n - 1], -1); + } + isl_vec_free(vec); + if (k < 0) + goto error; + + vars_drop(v, v->n - n); + + def = isl_basic_map_simplify(def); + def = isl_basic_map_finalize(def); + bmap = isl_basic_map_intersect(bmap, def); + return bmap; +error: + isl_basic_map_free(bmap); + isl_basic_map_free(def); + return NULL; +} + static __isl_give isl_basic_map *read_var_list(struct isl_stream *s, __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) { int i = 0; struct isl_token *tok; - while ((tok = isl_stream_next_token(s)) != NULL) { + while ((tok = next_token(s)) != NULL) { int new_name = 0; if (tok->type == ISL_TOKEN_IDENT) { @@ -245,9 +565,9 @@ static __isl_give isl_basic_map *read_var_list(struct isl_stream *s, bmap = set_name(bmap, type, i, v->v->name); isl_token_free(tok); } else if (tok->type == ISL_TOKEN_IDENT || - tok->type == ISL_TOKEN_VALUE) { - struct isl_vec *vec; - int k; + tok->type == ISL_TOKEN_VALUE || + tok->type == '-' || + tok->type == '(') { if (type == isl_dim_param) { isl_stream_error(s, tok, "expecting unique identifier"); @@ -255,28 +575,17 @@ static __isl_give isl_basic_map *read_var_list(struct isl_stream *s, } isl_stream_push_token(s, tok); tok = NULL; - vec = accept_affine(s, v); - if (!vec) - goto error; - v->v = variable_new(v, "", 0, v->n); - if (!v->v) - goto error; - v->n++; bmap = isl_basic_map_add(bmap, type, 1); - bmap = isl_basic_map_extend_constraints(bmap, 1, 0); - k = isl_basic_map_alloc_equality(bmap); - if (k >= 0) { - isl_seq_cpy(bmap->eq[k], vec->el, vec->size); - isl_int_set_si(bmap->eq[k][vec->size], -1); - } - isl_vec_free(vec); - if (k < 0) - goto error; + bmap = read_var_def(s, bmap, type, v); } else break; tok = isl_stream_next_token(s); - if (!tok || tok->type != ',') + if (tok && tok->type == ']' && + isl_stream_next_token_is(s, '[')) { + isl_token_free(tok); + tok = isl_stream_next_token(s); + } else if (!tok || tok->type != ',') break; isl_token_free(tok); @@ -317,6 +626,7 @@ static __isl_give isl_mat *accept_affine_list(struct isl_stream *s, isl_token_free(tok); vec = accept_affine(s, v); + mat = isl_mat_add_zero_cols(mat, 1 + v->n - isl_mat_cols(mat)); mat = isl_mat_vec_concat(mat, vec); if (!mat) return NULL; @@ -328,53 +638,111 @@ error: return NULL; } -static struct isl_basic_map *add_div_definition(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap, int k) +static int read_minmax_definition(struct isl_stream *s, struct vars *v) { struct isl_token *tok; - int seen_paren = 0; - struct isl_vec *aff; + struct variable *var; - if (isl_stream_eat(s, '[')) - goto error; + var = v->v; tok = isl_stream_next_token(s); if (!tok) - goto error; - if (tok->type == '(') { - seen_paren = 1; - isl_token_free(tok); - } else - isl_stream_push_token(s, tok); + return -1; + var->sign = tok->type == ISL_TOKEN_MIN ? -1 : 1; + isl_token_free(tok); + + if (isl_stream_eat(s, '(')) + return -1; + + var->list = accept_affine_list(s, v); + if (!var->list) + return -1; + + if (isl_stream_eat(s, ')')) + return -1; + + return 0; +} + +static int read_div_definition(struct isl_stream *s, struct vars *v) +{ + struct isl_token *tok; + int seen_paren = 0; + struct isl_vec *aff; + struct variable *var; + int fc = 0; + + if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD) || + isl_stream_eat_if_available(s, ISL_TOKEN_CEILD)) { + fc = 1; + if (isl_stream_eat(s, '(')) + return -1; + } else { + if (isl_stream_eat(s, '[')) + return -1; + if (isl_stream_eat_if_available(s, '(')) + seen_paren = 1; + } + + var = v->v; aff = accept_affine(s, v); if (!aff) - goto error; + return -1; - isl_seq_cpy(bmap->div[k] + 1, aff->el, aff->size); + var->def = isl_vec_alloc(s->ctx, 2 + v->n); + if (!var->def) { + isl_vec_free(aff); + return -1; + } + + isl_seq_cpy(var->def->el + 1, aff->el, aff->size); isl_vec_free(aff); - if (seen_paren && isl_stream_eat(s, ')')) - goto error; - if (isl_stream_eat(s, '/')) - goto error; + if (fc) { + if (isl_stream_eat(s, ',')) + return -1; + } else { + if (seen_paren && isl_stream_eat(s, ')')) + return -1; + if (isl_stream_eat(s, '/')) + return -1; + } - tok = isl_stream_next_token(s); + tok = next_token(s); if (!tok) - goto error; + return -1; if (tok->type != ISL_TOKEN_VALUE) { isl_stream_error(s, tok, "expected denominator"); isl_stream_push_token(s, tok); - goto error; + return -1; } - isl_int_set(bmap->div[k][0], tok->u.v); + isl_int_set(var->def->el[0], tok->u.v); isl_token_free(tok); - if (isl_stream_eat(s, ']')) + if (fc) { + if (isl_stream_eat(s, ')')) + return -1; + } else { + if (isl_stream_eat(s, ']')) + return -1; + } + + return 0; +} + +static struct isl_basic_map *add_div_definition(struct isl_stream *s, + struct vars *v, struct isl_basic_map *bmap, int pos) +{ + struct variable *var = v->v; + unsigned o_out = isl_basic_map_offset(bmap, isl_dim_out) - 1; + + if (read_div_definition(s, v) < 0) goto error; - if (isl_basic_map_add_div_constraints(bmap, k) < 0) + if (isl_basic_map_add_div_constraints_var(bmap, o_out + pos, + var->def->el) < 0) goto error; return bmap; @@ -389,10 +757,9 @@ static struct isl_basic_map *read_defined_var_list(struct isl_stream *s, struct isl_token *tok; while ((tok = isl_stream_next_token(s)) != NULL) { - int k; int p; int n = v->n; - unsigned total = isl_basic_map_total_dim(bmap); + unsigned n_out = isl_basic_map_dim(bmap, isl_dim_out); if (tok->type != ISL_TOKEN_IDENT) break; @@ -404,20 +771,17 @@ static struct isl_basic_map *read_defined_var_list(struct isl_stream *s, isl_stream_error(s, tok, "expecting unique identifier"); goto error; } - isl_token_free(tok); bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_add(bmap, isl_dim_out, 1); bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), - 1, 0, 2); - - if ((k = isl_basic_map_alloc_div(bmap)) < 0) - goto error; - isl_seq_clr(bmap->div[k], 1 + 1 + total); + 0, 0, 2); + isl_token_free(tok); tok = isl_stream_next_token(s); if (tok && tok->type == '=') { isl_token_free(tok); - bmap = add_div_definition(s, v, bmap, k); + bmap = add_div_definition(s, v, bmap, n_out); tok = isl_stream_next_token(s); } @@ -436,66 +800,106 @@ error: return NULL; } -static __isl_give isl_basic_map *read_tuple(struct isl_stream *s, - __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) +static int next_is_tuple(struct isl_stream *s) { struct isl_token *tok; + int is_tuple; tok = isl_stream_next_token(s); - if (!tok || tok->type != '[') { - isl_stream_error(s, tok, "expecting '['"); - goto error; + if (!tok) + return 0; + if (tok->type == '[') { + isl_stream_push_token(s, tok); + return 1; } - isl_token_free(tok); - bmap = read_var_list(s, bmap, type, v); - tok = isl_stream_next_token(s); - if (!tok || tok->type != ']') { - isl_stream_error(s, tok, "expecting ']'"); - goto error; + if (tok->type != ISL_TOKEN_IDENT && !tok->is_keyword) { + isl_stream_push_token(s, tok); + return 0; } - isl_token_free(tok); + is_tuple = isl_stream_next_token_is(s, '['); + + isl_stream_push_token(s, tok); + + return is_tuple; +} + +static __isl_give isl_basic_map *read_tuple(struct isl_stream *s, + __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v); + +static __isl_give isl_basic_map *read_nested_tuple(struct isl_stream *s, + __isl_take isl_basic_map *bmap, struct vars *v) +{ + bmap = read_tuple(s, bmap, isl_dim_in, v); + if (isl_stream_eat(s, ISL_TOKEN_TO)) + goto error; + bmap = read_tuple(s, bmap, isl_dim_out, v); + bmap = isl_basic_map_from_range(isl_basic_map_wrap(bmap)); return bmap; error: - if (tok) - isl_token_free(tok); isl_basic_map_free(bmap); return NULL; } -static struct isl_basic_map *add_constraints(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap); - -static struct isl_basic_map *add_exists(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap) +static __isl_give isl_basic_map *read_tuple(struct isl_stream *s, + __isl_take isl_basic_map *bmap, enum isl_dim_type type, struct vars *v) { struct isl_token *tok; - int n = v->n; - int extra; - int seen_paren = 0; - int i; - unsigned total; + char *name = NULL; tok = isl_stream_next_token(s); - if (!tok) - goto error; - if (tok->type == '(') { - seen_paren = 1; + if (tok && (tok->type == ISL_TOKEN_IDENT || tok->is_keyword)) { + name = strdup(tok->u.s); + if (!name) + goto error; isl_token_free(tok); + tok = isl_stream_next_token(s); + } + if (!tok || tok->type != '[') { + isl_stream_error(s, tok, "expecting '['"); + goto error; + } + isl_token_free(tok); + if (type != isl_dim_param && next_is_tuple(s)) { + isl_dim *dim = isl_basic_map_get_dim(bmap); + int nparam = isl_dim_size(dim, isl_dim_param); + int n_in = isl_dim_size(dim, isl_dim_in); + isl_basic_map *nested; + if (type == isl_dim_out) + dim = isl_dim_move(dim, isl_dim_param, nparam, + isl_dim_in, 0, n_in); + nested = isl_basic_map_alloc_dim(dim, 0, 0, 0); + nested = read_nested_tuple(s, nested, v); + if (type == isl_dim_in) { + nested = isl_basic_map_reverse(nested); + bmap = isl_basic_map_intersect(nested, bmap); + } else { + isl_basic_set *bset; + dim = isl_dim_range(isl_basic_map_get_dim(nested)); + dim = isl_dim_drop(dim, isl_dim_param, nparam, n_in); + dim = isl_dim_join(isl_basic_map_get_dim(bmap), dim); + bset = isl_basic_map_domain(bmap); + nested = isl_basic_map_reset_dim(nested, dim); + bmap = isl_basic_map_intersect_domain(nested, bset); + } } else - isl_stream_push_token(s, tok); - - bmap = read_defined_var_list(s, v, bmap); - if (!bmap) + bmap = read_var_list(s, bmap, type, v); + tok = isl_stream_next_token(s); + if (!tok || tok->type != ']') { + isl_stream_error(s, tok, "expecting ']'"); goto error; + } + isl_token_free(tok); + + if (name) { + bmap = isl_basic_map_set_tuple_name(bmap, type, name); + free(name); + } - if (isl_stream_eat(s, ':')) - goto error; - bmap = add_constraints(s, v, bmap); - if (seen_paren && isl_stream_eat(s, ')')) - goto error; return bmap; error: + if (tok) + isl_token_free(tok); isl_basic_map_free(bmap); return NULL; } @@ -564,24 +968,49 @@ static int is_comparator(struct isl_token *tok) } } +/* Add any variables in the variable list "v" that are not already in "bmap" + * as output variables in "bmap". + */ +static __isl_give isl_basic_map *add_lifted_divs(__isl_take isl_basic_map *bmap, + struct vars *v) +{ + int i; + int extra; + struct variable *var; + + extra = v->n - isl_basic_map_total_dim(bmap); + + if (extra == 0) + return bmap; + + bmap = isl_basic_map_add(bmap, isl_dim_out, extra); + bmap = isl_basic_map_extend_dim(bmap, isl_basic_map_get_dim(bmap), + 0, 0, 2 * extra); + + for (i = 0, var = v->v; i < extra; ++i, var = var->next) { + if (!var->def) + continue; + var->def = isl_vec_zero_extend(var->def, 2 + v->n); + if (!var->def) + goto error; + if (isl_basic_map_add_div_constraints_var(bmap, var->pos, + var->def->el) < 0) + goto error; + } + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + static struct isl_basic_map *add_constraint(struct isl_stream *s, struct vars *v, struct isl_basic_map *bmap) { int i, j; - unsigned total = isl_basic_map_total_dim(bmap); struct isl_token *tok = NULL; struct isl_mat *aff1 = NULL, *aff2 = NULL; - tok = isl_stream_next_token(s); - if (!tok) - goto error; - if (tok->type == ISL_TOKEN_EXISTS) { - isl_token_free(tok); - return add_exists(s, v, bmap); - } - isl_stream_push_token(s, tok); - tok = NULL; - bmap = isl_basic_map_cow(bmap); aff1 = accept_affine_list(s, v); @@ -595,13 +1024,15 @@ static struct isl_basic_map *add_constraint(struct isl_stream *s, tok = NULL; goto error; } - isl_assert(aff1->ctx, aff1->n_col == 1 + total, goto error); for (;;) { aff2 = accept_affine_list(s, v); if (!aff2) goto error; - isl_assert(aff2->ctx, aff2->n_col == 1 + total, goto error); + aff1 = isl_mat_add_zero_cols(aff1, aff2->n_col - aff1->n_col); + if (!aff1) + goto error; + bmap = add_lifted_divs(bmap, v); bmap = isl_basic_map_extend_constraints(bmap, 0, aff1->n_row * aff2->n_row); for (i = 0; i < aff1->n_row; ++i) @@ -621,117 +1052,350 @@ static struct isl_basic_map *add_constraint(struct isl_stream *s, } isl_mat_free(aff1); - return bmap; + return bmap; +error: + if (tok) + isl_token_free(tok); + isl_mat_free(aff1); + isl_mat_free(aff2); + isl_basic_map_free(bmap); + return NULL; +} + +/* Return first variable, starting at n, representing a min or max, + * or NULL if there is no such variable. + */ +static struct variable *first_minmax(struct vars *v, int n) +{ + struct variable *first = NULL; + struct variable *var; + + for (var = v->v; var && var->pos >= n; var = var->next) + if (var->list) + first = var; + + return first; +} + +/* Check whether the variable at the given position only occurs in + * inequalities and only with the given sign. + */ +static int all_coefficients_of_sign(__isl_keep isl_map *map, int pos, int sign) +{ + int i, j; + + if (!map) + return -1; + + for (i = 0; i < map->n; ++i) { + isl_basic_map *bmap = map->p[i]; + + for (j = 0; j < bmap->n_eq; ++j) + if (!isl_int_is_zero(bmap->eq[j][1 + pos])) + return 0; + for (j = 0; j < bmap->n_ineq; ++j) { + int s = isl_int_sgn(bmap->ineq[j][1 + pos]); + if (s == 0) + continue; + if (s != sign) + return 0; + } + } + + return 1; +} + +/* Given a variable m which represents a min or a max of n expressions + * b_i, add the constraints + * + * m <= b_i + * + * in case of a min (var->sign < 0) and m >= b_i in case of a max. + */ +static __isl_give isl_map *bound_minmax(__isl_take isl_map *map, + struct variable *var) +{ + int i, k; + isl_basic_map *bound; + int total; + + total = isl_map_dim(map, isl_dim_all); + bound = isl_basic_map_alloc_dim(isl_map_get_dim(map), + 0, 0, var->list->n_row); + + for (i = 0; i < var->list->n_row; ++i) { + k = isl_basic_map_alloc_inequality(bound); + if (k < 0) + goto error; + if (var->sign < 0) + isl_seq_cpy(bound->ineq[k], var->list->row[i], + var->list->n_col); + else + isl_seq_neg(bound->ineq[k], var->list->row[i], + var->list->n_col); + isl_int_set_si(bound->ineq[k][1 + var->pos], var->sign); + isl_seq_clr(bound->ineq[k] + var->list->n_col, + 1 + total - var->list->n_col); + } + + map = isl_map_intersect(map, isl_map_from_basic_map(bound)); + + return map; +error: + isl_basic_map_free(bound); + isl_map_free(map); + return NULL; +} + +/* Given a variable m which represents a min (or max) of n expressions + * b_i, add constraints that assigns the minimal upper bound to m, i.e., + * divide the space into cells where one + * of the upper bounds is smaller than all the others and assign + * this upper bound to m. + * + * In particular, if there are n bounds b_i, then the input map + * is split into n pieces, each with the extra constraints + * + * m = b_i + * b_i <= b_j for j > i + * b_i < b_j for j < i + * + * in case of a min (var->sign < 0) and similarly in case of a max. + * + * Note: this function is very similar to set_minimum in isl_tab_pip.c + * Perhaps we should try to merge the two. + */ +static __isl_give isl_map *set_minmax(__isl_take isl_map *map, + struct variable *var) +{ + int i, j, k; + isl_basic_map *bmap = NULL; + isl_ctx *ctx; + isl_map *split = NULL; + int total; + + ctx = isl_map_get_ctx(map); + total = isl_map_dim(map, isl_dim_all); + split = isl_map_alloc_dim(isl_map_get_dim(map), + var->list->n_row, ISL_SET_DISJOINT); + + for (i = 0; i < var->list->n_row; ++i) { + bmap = isl_basic_map_alloc_dim(isl_map_get_dim(map), 0, + 1, var->list->n_row - 1); + k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + goto error; + isl_seq_cpy(bmap->eq[k], var->list->row[i], var->list->n_col); + isl_int_set_si(bmap->eq[k][1 + var->pos], -1); + for (j = 0; j < var->list->n_row; ++j) { + if (j == i) + continue; + k = isl_basic_map_alloc_inequality(bmap); + if (k < 0) + goto error; + if (var->sign < 0) + isl_seq_combine(bmap->ineq[k], + ctx->one, var->list->row[j], + ctx->negone, var->list->row[i], + var->list->n_col); + else + isl_seq_combine(bmap->ineq[k], + ctx->negone, var->list->row[j], + ctx->one, var->list->row[i], + var->list->n_col); + isl_seq_clr(bmap->ineq[k] + var->list->n_col, + 1 + total - var->list->n_col); + if (j < i) + isl_int_sub_ui(bmap->ineq[k][0], + bmap->ineq[k][0], 1); + } + bmap = isl_basic_map_finalize(bmap); + split = isl_map_add_basic_map(split, bmap); + } + + map = isl_map_intersect(map, split); + + return map; error: - if (tok) - isl_token_free(tok); - isl_mat_free(aff1); - isl_mat_free(aff2); isl_basic_map_free(bmap); + isl_map_free(split); + isl_map_free(map); return NULL; } -static struct isl_basic_map *add_constraints(struct isl_stream *s, - struct vars *v, struct isl_basic_map *bmap) +/* Plug in the definitions of all min and max expressions. + * If a min expression only appears in inequalities and only + * with a positive coefficient, then we can simply bound + * the variable representing the min by its defining terms + * and similarly for a max expression. + * Otherwise, we have to assign the different terms to the + * variable under the condition that the assigned term is smaller + * than the other terms. + */ +static __isl_give isl_map *add_minmax(__isl_take isl_map *map, + struct vars *v, int n) { - struct isl_token *tok; + struct variable *var; - for (;;) { - bmap = add_constraint(s, v, bmap); - if (!bmap) - return NULL; - tok = isl_stream_next_token(s); - if (!tok) { - isl_stream_error(s, NULL, "unexpected EOF"); - goto error; - } - if (tok->type != ISL_TOKEN_AND) + while (n < v->n) { + var = first_minmax(v, n); + if (!var) break; - isl_token_free(tok); + if (all_coefficients_of_sign(map, var->pos, -var->sign)) + map = bound_minmax(map, var); + else + map = set_minmax(map, var); + n = var->pos + 1; } - isl_stream_push_token(s, tok); - return bmap; -error: - if (tok) - isl_token_free(tok); - isl_basic_map_free(bmap); - return NULL; + return map; } -static struct isl_basic_map *read_disjunct(struct isl_stream *s, - struct vars *v, __isl_take isl_dim *dim) +static isl_map *read_constraint(struct isl_stream *s, + struct vars *v, __isl_take isl_basic_map *bmap) { - int seen_paren = 0; - struct isl_token *tok; - struct isl_basic_map *bmap; + int n = v->n; + isl_map *map; + unsigned total; - bmap = isl_basic_map_alloc_dim(dim, 0, 0, 0); if (!bmap) return NULL; - tok = isl_stream_next_token(s); - if (!tok) - goto error; - if (tok->type == '(') { - seen_paren = 1; - isl_token_free(tok); - } else - isl_stream_push_token(s, tok); + bmap = isl_basic_set_unwrap(isl_basic_set_lift(isl_basic_map_wrap(bmap))); + total = isl_basic_map_total_dim(bmap); + while (v->n < total) + if (vars_add_anon(v) < 0) + goto error; - bmap = add_constraints(s, v, bmap); + bmap = add_constraint(s, v, bmap); bmap = isl_basic_map_simplify(bmap); bmap = isl_basic_map_finalize(bmap); - if (seen_paren && isl_stream_eat(s, ')')) - goto error; + map = isl_map_from_basic_map(bmap); - return bmap; + map = add_minmax(map, v, n); + + map = isl_set_unwrap(isl_map_domain(map)); + + vars_drop(v, v->n - n); + + return map; error: isl_basic_map_free(bmap); return NULL; } static struct isl_map *read_disjuncts(struct isl_stream *s, - struct vars *v, __isl_take isl_dim *dim) + struct vars *v, __isl_take isl_basic_map *bmap); + +static __isl_give isl_map *read_exists(struct isl_stream *s, + struct vars *v, __isl_take isl_basic_map *bmap) { - struct isl_token *tok; - struct isl_map *map; + int n = v->n; + int seen_paren = isl_stream_eat_if_available(s, '('); + isl_map *map = NULL; - tok = isl_stream_next_token(s); - if (!tok) { - isl_stream_error(s, NULL, "unexpected EOF"); + bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap)); + bmap = read_defined_var_list(s, v, bmap); + + if (isl_stream_eat(s, ':')) + goto error; + + map = read_disjuncts(s, v, bmap); + map = isl_set_unwrap(isl_map_domain(map)); + bmap = NULL; + + vars_drop(v, v->n - n); + if (seen_paren && isl_stream_eat(s, ')')) goto error; + + return map; +error: + isl_basic_map_free(bmap); + isl_map_free(map); + return NULL; +} + +static __isl_give isl_map *read_conjunct(struct isl_stream *s, + struct vars *v, __isl_take isl_basic_map *bmap) +{ + isl_map *map; + + if (isl_stream_eat_if_available(s, '(')) { + map = read_disjuncts(s, v, bmap); + if (isl_stream_eat(s, ')')) + goto error; + return map; } - if (tok->type == '}') { - isl_stream_push_token(s, tok); - return isl_map_universe(dim); + + if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS)) + return read_exists(s, v, bmap); + + if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE)) + return isl_map_from_basic_map(bmap); + + if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) { + isl_dim *dim = isl_basic_map_get_dim(bmap); + isl_basic_map_free(bmap); + return isl_map_empty(dim); } - isl_stream_push_token(s, tok); + + return read_constraint(s, v, bmap); +error: + isl_map_free(map); + return NULL; +} - map = isl_map_empty(isl_dim_copy(dim)); - for (;;) { - struct isl_basic_map *bmap; - int n = v->n; +static __isl_give isl_map *read_conjuncts(struct isl_stream *s, + struct vars *v, __isl_take isl_basic_map *bmap) +{ + isl_map *map; + int negate; + + negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); + map = read_conjunct(s, v, isl_basic_map_copy(bmap)); + if (negate) { + isl_map *t; + t = isl_map_from_basic_map(isl_basic_map_copy(bmap)); + map = isl_map_subtract(t, map); + } - bmap = read_disjunct(s, v, isl_dim_copy(dim)); - map = isl_map_union(map, isl_map_from_basic_map(bmap)); + while (isl_stream_eat_if_available(s, ISL_TOKEN_AND)) { + isl_map *map_i; - vars_drop(v, v->n - n); + negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT); + map_i = read_conjunct(s, v, isl_basic_map_copy(bmap)); + if (negate) + map = isl_map_subtract(map, map_i); + else + map = isl_map_intersect(map, map_i); + } - tok = isl_stream_next_token(s); - if (!tok || tok->type != ISL_TOKEN_OR) - break; - isl_token_free(tok); + isl_basic_map_free(bmap); + return map; +} + +static struct isl_map *read_disjuncts(struct isl_stream *s, + struct vars *v, __isl_take isl_basic_map *bmap) +{ + struct isl_map *map; + + if (isl_stream_next_token_is(s, '}')) { + isl_dim *dim = isl_basic_map_get_dim(bmap); + isl_basic_map_free(bmap); + return isl_map_universe(dim); } - if (tok) - isl_stream_push_token(s, tok); - isl_dim_free(dim); + map = read_conjuncts(s, v, isl_basic_map_copy(bmap)); + while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) { + isl_map *map_i; + + map_i = read_conjuncts(s, v, isl_basic_map_copy(bmap)); + map = isl_map_union(map, map_i); + } + + isl_basic_map_free(bmap); return map; -error: - isl_dim_free(dim); - return NULL; } static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos) @@ -852,6 +1516,13 @@ static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s, isl_stream_error(s, NULL, "unexpected EOF"); return NULL; } + if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) { + isl_stream_push_token(s, tok2); + isl_stream_push_token(s, tok); + isl_stream_error(s, NULL, + "expecting constraint matrix dimensions"); + return NULL; + } n_row = isl_int_get_si(tok->u.v); n_col = isl_int_get_si(tok2->u.v); on_new_line = tok2->on_new_line; @@ -918,6 +1589,7 @@ static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s, int k = isl_basic_map_alloc_div(bmap); if (k < 0) goto error; + isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local); } for (i = 0; i < n_row; ++i) @@ -930,54 +1602,373 @@ static __isl_give isl_basic_map *basic_map_read_polylib(struct isl_stream *s, goto error; } - bmap = isl_basic_map_simplify(bmap); - bmap = isl_basic_map_finalize(bmap); - return bmap; -error: - isl_basic_map_free(bmap); - return NULL; + bmap = isl_basic_map_simplify(bmap); + bmap = isl_basic_map_finalize(bmap); + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam) +{ + struct isl_token *tok; + struct isl_token *tok2; + int i, n; + struct isl_map *map; + + tok = isl_stream_next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + return NULL; + } + tok2 = isl_stream_next_token_on_same_line(s); + if (tok2 && tok2->type == ISL_TOKEN_VALUE) { + isl_stream_push_token(s, tok2); + isl_stream_push_token(s, tok); + return isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + } + if (tok2) { + isl_stream_error(s, tok2, "unexpected token"); + isl_stream_push_token(s, tok2); + isl_stream_push_token(s, tok); + return NULL; + } + n = isl_int_get_si(tok->u.v); + isl_token_free(tok); + + isl_assert(s->ctx, n >= 1, return NULL); + + map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + + for (i = 1; map && i < n; ++i) + map = isl_map_union(map, + isl_map_from_basic_map(basic_map_read_polylib(s, nparam))); + + return map; +} + +static int optional_power(struct isl_stream *s) +{ + int pow; + struct isl_token *tok; + + tok = isl_stream_next_token(s); + if (!tok) + return 1; + if (tok->type != '^') { + isl_stream_push_token(s, tok); + return 1; + } + isl_token_free(tok); + tok = isl_stream_next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting exponent"); + if (tok) + isl_stream_push_token(s, tok); + return 1; + } + pow = isl_int_get_si(tok->u.v); + isl_token_free(tok); + return pow; +} + +static __isl_give isl_div *read_div(struct isl_stream *s, + __isl_take isl_dim *dim, struct vars *v) +{ + int n; + isl_basic_map *bmap; + + n = v->n; + bmap = isl_basic_map_universe(dim); + + if (vars_add_anon(v) < 0) + goto error; + if (read_div_definition(s, v) < 0) + goto error; + bmap = add_divs(bmap, v); + bmap = isl_basic_map_order_divs(bmap); + if (!bmap) + goto error; + vars_drop(v, v->n - n); + + return isl_basic_map_div(bmap, bmap->n_div - 1); +error: + isl_basic_map_free(bmap); + return NULL; +} + +static __isl_give isl_qpolynomial *read_term(struct isl_stream *s, + __isl_keep isl_basic_map *bmap, struct vars *v); + +static __isl_give isl_qpolynomial *read_factor(struct isl_stream *s, + __isl_keep isl_basic_map *bmap, struct vars *v) +{ + struct isl_qpolynomial *qp; + struct isl_token *tok; + + tok = next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + return NULL; + } + if (tok->type == '(') { + int pow; + + isl_token_free(tok); + qp = read_term(s, bmap, v); + if (!qp) + return NULL; + if (isl_stream_eat(s, ')')) + goto error; + pow = optional_power(s); + qp = isl_qpolynomial_pow(qp, pow); + } else if (tok->type == ISL_TOKEN_VALUE) { + struct isl_token *tok2; + tok2 = isl_stream_next_token(s); + if (tok2 && tok2->type == '/') { + isl_token_free(tok2); + tok2 = next_token(s); + if (!tok2 || tok2->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok2, "expected denominator"); + isl_token_free(tok); + isl_token_free(tok2); + return NULL; + } + qp = isl_qpolynomial_rat_cst(isl_basic_map_get_dim(bmap), + tok->u.v, tok2->u.v); + isl_token_free(tok2); + } else { + isl_stream_push_token(s, tok2); + qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap), + tok->u.v); + } + isl_token_free(tok); + } else if (tok->type == ISL_TOKEN_INFTY) { + isl_token_free(tok); + qp = isl_qpolynomial_infty(isl_basic_map_get_dim(bmap)); + } else if (tok->type == ISL_TOKEN_NAN) { + isl_token_free(tok); + qp = isl_qpolynomial_nan(isl_basic_map_get_dim(bmap)); + } else if (tok->type == ISL_TOKEN_IDENT) { + int n = v->n; + int pos = vars_pos(v, tok->u.s, -1); + int pow; + if (pos < 0) { + isl_token_free(tok); + return NULL; + } + if (pos >= n) { + vars_drop(v, v->n - n); + isl_stream_error(s, tok, "unknown identifier"); + isl_token_free(tok); + return NULL; + } + isl_token_free(tok); + pow = optional_power(s); + qp = isl_qpolynomial_var_pow(isl_basic_map_get_dim(bmap), pos, pow); + } else if (tok->type == '[') { + isl_div *div; + int pow; + + isl_stream_push_token(s, tok); + div = read_div(s, isl_basic_map_get_dim(bmap), v); + pow = optional_power(s); + qp = isl_qpolynomial_div_pow(div, pow); + } else if (tok->type == '-') { + struct isl_qpolynomial *qp2; + + isl_token_free(tok); + qp = isl_qpolynomial_cst(isl_basic_map_get_dim(bmap), + s->ctx->negone); + qp2 = read_factor(s, bmap, v); + qp = isl_qpolynomial_mul(qp, qp2); + } else { + isl_stream_error(s, tok, "unexpected isl_token"); + isl_stream_push_token(s, tok); + return NULL; + } + + if (isl_stream_eat_if_available(s, '*') || + isl_stream_next_token_is(s, ISL_TOKEN_IDENT)) { + struct isl_qpolynomial *qp2; + + qp2 = read_factor(s, bmap, v); + qp = isl_qpolynomial_mul(qp, qp2); + } + + return qp; +error: + isl_qpolynomial_free(qp); + return NULL; +} + +static __isl_give isl_qpolynomial *read_term(struct isl_stream *s, + __isl_keep isl_basic_map *bmap, struct vars *v) +{ + struct isl_token *tok; + struct isl_qpolynomial *qp; + + qp = read_factor(s, bmap, v); + + for (;;) { + tok = next_token(s); + if (!tok) + return qp; + + if (tok->type == '+') { + struct isl_qpolynomial *qp2; + + isl_token_free(tok); + qp2 = read_factor(s, bmap, v); + qp = isl_qpolynomial_add(qp, qp2); + } else if (tok->type == '-') { + struct isl_qpolynomial *qp2; + + isl_token_free(tok); + qp2 = read_factor(s, bmap, v); + qp = isl_qpolynomial_sub(qp, qp2); + } else if (tok->type == ISL_TOKEN_VALUE && + isl_int_is_neg(tok->u.v)) { + struct isl_qpolynomial *qp2; + + isl_stream_push_token(s, tok); + qp2 = read_factor(s, bmap, v); + qp = isl_qpolynomial_add(qp, qp2); + } else { + isl_stream_push_token(s, tok); + break; + } + } + + return qp; } -static struct isl_map *map_read_polylib(struct isl_stream *s, int nparam) +static __isl_give isl_map *read_optional_disjuncts(struct isl_stream *s, + __isl_take isl_basic_map *bmap, struct vars *v) { struct isl_token *tok; - struct isl_token *tok2; - int i, n; struct isl_map *map; tok = isl_stream_next_token(s); if (!tok) { isl_stream_error(s, NULL, "unexpected EOF"); - return NULL; + goto error; } - tok2 = isl_stream_next_token_on_same_line(s); - if (tok2) { - isl_stream_push_token(s, tok2); + map = isl_map_from_basic_map(isl_basic_map_copy(bmap)); + if (tok->type == ':' || + (tok->type == ISL_TOKEN_OR && !strcmp(tok->u.s, "|"))) { + isl_token_free(tok); + map = isl_map_intersect(map, + read_disjuncts(s, v, isl_basic_map_copy(bmap))); + } else isl_stream_push_token(s, tok); - return isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + + isl_basic_map_free(bmap); + + return map; +error: + isl_basic_map_free(bmap); + return NULL; +} + +static struct isl_obj obj_read_poly(struct isl_stream *s, + __isl_take isl_basic_map *bmap, struct vars *v, int n) +{ + struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL }; + struct isl_pw_qpolynomial *pwqp; + struct isl_qpolynomial *qp; + struct isl_map *map; + struct isl_set *set; + + qp = read_term(s, bmap, v); + map = read_optional_disjuncts(s, bmap, v); + set = isl_map_range(map); + + pwqp = isl_pw_qpolynomial_alloc(set, qp); + + vars_drop(v, v->n - n); + + obj.v = pwqp; + return obj; +} + +static struct isl_obj obj_read_poly_or_fold(struct isl_stream *s, + __isl_take isl_basic_map *bmap, struct vars *v, int n) +{ + struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL }; + isl_qpolynomial *qp; + isl_qpolynomial_fold *fold = NULL; + isl_pw_qpolynomial_fold *pwf; + isl_map *map; + isl_set *set; + + if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX)) + return obj_read_poly(s, bmap, v, n); + + if (isl_stream_eat(s, '(')) + goto error; + + qp = read_term(s, bmap, v); + fold = isl_qpolynomial_fold_alloc(isl_fold_max, qp); + + while (isl_stream_eat_if_available(s, ',')) { + isl_qpolynomial_fold *fold_i; + qp = read_term(s, bmap, v); + fold_i = isl_qpolynomial_fold_alloc(isl_fold_max, qp); + fold = isl_qpolynomial_fold_fold(fold, fold_i); } - n = isl_int_get_si(tok->u.v); - isl_token_free(tok); - isl_assert(s->ctx, n >= 1, return NULL); + if (isl_stream_eat(s, ')')) + goto error; - map = isl_map_from_basic_map(basic_map_read_polylib(s, nparam)); + map = read_optional_disjuncts(s, bmap, v); + set = isl_map_range(map); + pwf = isl_pw_qpolynomial_fold_alloc(isl_fold_max, set, fold); - for (i = 1; i < n; ++i) - map = isl_map_union(map, - isl_map_from_basic_map(basic_map_read_polylib(s, nparam))); + vars_drop(v, v->n - n); - return map; + obj.v = pwf; + return obj; +error: + isl_basic_map_free(bmap); + isl_qpolynomial_fold_free(fold); + obj.type = isl_obj_none; + return obj; +} + +static int is_rational(struct isl_stream *s) +{ + struct isl_token *tok; + + tok = isl_stream_next_token(s); + if (!tok) + return 0; + if (tok->type == ISL_TOKEN_RAT && isl_stream_next_token_is(s, ':')) { + isl_token_free(tok); + isl_stream_eat(s, ':'); + return 1; + } + + isl_stream_push_token(s, tok); + + return 0; } static struct isl_obj obj_read_body(struct isl_stream *s, - __isl_take isl_basic_map *bmap, struct vars *v, isl_obj_type type) + __isl_take isl_basic_map *bmap, struct vars *v) { struct isl_map *map = NULL; struct isl_token *tok; - struct isl_obj obj = { type, NULL }; + struct isl_obj obj = { isl_obj_set, NULL }; int n = v->n; + if (is_rational(s)) + bmap = isl_basic_map_set_rational(bmap); + + if (!next_is_tuple(s)) + return obj_read_poly_or_fold(s, bmap, v, n); + bmap = read_tuple(s, bmap, isl_dim_in, v); if (!bmap) goto error; @@ -985,6 +1976,10 @@ static struct isl_obj obj_read_body(struct isl_stream *s, if (tok && tok->type == ISL_TOKEN_TO) { obj.type = isl_obj_map; isl_token_free(tok); + if (!next_is_tuple(s)) { + bmap = isl_basic_map_reverse(bmap); + return obj_read_poly_or_fold(s, bmap, v, n); + } bmap = read_tuple(s, bmap, isl_dim_out, v); if (!bmap) goto error; @@ -993,22 +1988,11 @@ static struct isl_obj obj_read_body(struct isl_stream *s, if (tok) isl_stream_push_token(s, tok); } - tok = isl_stream_next_token(s); - if (!tok) { - isl_stream_error(s, NULL, "unexpected EOF"); - goto error; - } - map = isl_map_from_basic_map(isl_basic_map_copy(bmap)); - if (tok->type == ':') { - isl_token_free(tok); - map = isl_map_intersect(map, - read_disjuncts(s, v, isl_basic_map_get_dim(bmap))); - } else - isl_stream_push_token(s, tok); + + map = read_optional_disjuncts(s, bmap, v); vars_drop(v, v->n - n); - isl_basic_map_free(bmap); obj.v = map; return obj; error: @@ -1017,10 +2001,71 @@ error: return obj; } +static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj) +{ + if (obj.type == isl_obj_map) { + obj.v = isl_union_map_from_map(obj.v); + obj.type = isl_obj_union_map; + } else if (obj.type == isl_obj_set) { + obj.v = isl_union_set_from_set(obj.v); + obj.type = isl_obj_union_set; + } else if (obj.type == isl_obj_pw_qpolynomial) { + obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v); + obj.type = isl_obj_union_pw_qpolynomial; + } else if (obj.type == isl_obj_pw_qpolynomial_fold) { + obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v); + obj.type = isl_obj_union_pw_qpolynomial_fold; + } else + isl_assert(ctx, 0, goto error); + return obj; +error: + obj.type->free(obj.v); + obj.type = isl_obj_none; + return obj; +} + static struct isl_obj obj_add(struct isl_ctx *ctx, struct isl_obj obj1, struct isl_obj obj2) { + if (obj1.type == isl_obj_set && obj2.type == isl_obj_union_set) + obj1 = to_union(ctx, obj1); + if (obj1.type == isl_obj_union_set && obj2.type == isl_obj_set) + obj2 = to_union(ctx, obj2); + if (obj1.type == isl_obj_map && obj2.type == isl_obj_union_map) + obj1 = to_union(ctx, obj1); + if (obj1.type == isl_obj_union_map && obj2.type == isl_obj_map) + obj2 = to_union(ctx, obj2); + if (obj1.type == isl_obj_pw_qpolynomial && + obj2.type == isl_obj_union_pw_qpolynomial) + obj1 = to_union(ctx, obj1); + if (obj1.type == isl_obj_union_pw_qpolynomial && + obj2.type == isl_obj_pw_qpolynomial) + obj2 = to_union(ctx, obj2); + if (obj1.type == isl_obj_pw_qpolynomial_fold && + obj2.type == isl_obj_union_pw_qpolynomial_fold) + obj1 = to_union(ctx, obj1); + if (obj1.type == isl_obj_union_pw_qpolynomial_fold && + obj2.type == isl_obj_pw_qpolynomial_fold) + obj2 = to_union(ctx, obj2); isl_assert(ctx, obj1.type == obj2.type, goto error); + if (obj1.type == isl_obj_map && !isl_map_has_equal_dim(obj1.v, obj2.v)) { + obj1 = to_union(ctx, obj1); + obj2 = to_union(ctx, obj2); + } + if (obj1.type == isl_obj_set && !isl_set_has_equal_dim(obj1.v, obj2.v)) { + obj1 = to_union(ctx, obj1); + obj2 = to_union(ctx, obj2); + } + if (obj1.type == isl_obj_pw_qpolynomial && + !isl_pw_qpolynomial_has_equal_dim(obj1.v, obj2.v)) { + obj1 = to_union(ctx, obj1); + obj2 = to_union(ctx, obj2); + } + if (obj1.type == isl_obj_pw_qpolynomial_fold && + !isl_pw_qpolynomial_fold_has_equal_dim(obj1.v, obj2.v)) { + obj1 = to_union(ctx, obj1); + obj2 = to_union(ctx, obj2); + } obj1.v = obj1.type->add(obj1.v, obj2.v); return obj1; error: @@ -1033,18 +2078,31 @@ error: static struct isl_obj obj_read(struct isl_stream *s, int nparam) { - struct isl_basic_map *bmap = NULL; + isl_basic_map *bmap = NULL; struct isl_token *tok; struct vars *v = NULL; struct isl_obj obj = { isl_obj_set, NULL }; - tok = isl_stream_next_token(s); + tok = next_token(s); if (!tok) { isl_stream_error(s, NULL, "unexpected EOF"); goto error; } if (tok->type == ISL_TOKEN_VALUE) { + struct isl_token *tok2; struct isl_map *map; + + tok2 = isl_stream_next_token(s); + if (!tok2 || tok2->type != ISL_TOKEN_VALUE || + isl_int_is_neg(tok2->u.v)) { + if (tok2) + isl_stream_push_token(s, tok2); + obj.type = isl_obj_int; + obj.v = isl_int_obj_alloc(s->ctx, tok->u.v); + isl_token_free(tok); + return obj; + } + isl_stream_push_token(s, tok2); isl_stream_push_token(s, tok); map = map_read_polylib(s, nparam); if (!map) @@ -1055,6 +2113,10 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) return obj; } v = vars_new(s->ctx); + if (!v) { + isl_stream_push_token(s, tok); + goto error; + } bmap = isl_basic_map_alloc(s->ctx, 0, 0, 0, 0, 0, 0); if (tok->type == '[') { isl_stream_push_token(s, tok); @@ -1072,7 +2134,7 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) } isl_token_free(tok); tok = isl_stream_next_token(s); - } if (nparam > 0) + } else if (nparam > 0) bmap = isl_basic_map_add(bmap, isl_dim_param, nparam); if (!tok || tok->type != '{') { isl_stream_error(s, tok, "expecting '{'"); @@ -1082,23 +2144,47 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) } isl_token_free(tok); + tok = isl_stream_next_token(s); + if (!tok) + ; + else if (tok->type == ISL_TOKEN_IDENT && !strcmp(tok->u.s, "Sym")) { + isl_token_free(tok); + if (isl_stream_eat(s, '=')) + goto error; + bmap = read_tuple(s, bmap, isl_dim_param, v); + if (!bmap) + goto error; + if (nparam >= 0) + isl_assert(s->ctx, nparam == v->n, goto error); + } else if (tok->type == '}') { + obj.type = isl_obj_union_set; + obj.v = isl_union_set_empty(isl_basic_map_get_dim(bmap)); + isl_token_free(tok); + goto done; + } else + isl_stream_push_token(s, tok); + for (;;) { struct isl_obj o; tok = NULL; - o = obj_read_body(s, isl_basic_map_copy(bmap), v, obj.type); - if (o.type == isl_obj_none) - break; + o = obj_read_body(s, isl_basic_map_copy(bmap), v); + if (o.type == isl_obj_none || !o.v) + goto error; if (!obj.v) obj = o; else { obj = obj_add(s->ctx, obj, o); - if (obj.type == isl_obj_none) - break; + if (obj.type == isl_obj_none || !obj.v) + goto error; } tok = isl_stream_next_token(s); if (!tok || tok->type != ';') break; isl_token_free(tok); + if (isl_stream_next_token_is(s, '}')) { + tok = isl_stream_next_token(s); + break; + } } if (tok && tok->type == '}') { @@ -1109,6 +2195,7 @@ static struct isl_obj obj_read(struct isl_stream *s, int nparam) isl_token_free(tok); goto error; } +done: vars_free(v); isl_basic_map_free(bmap); @@ -1127,6 +2214,76 @@ struct isl_obj isl_stream_read_obj(struct isl_stream *s) return obj_read(s, -1); } +__isl_give isl_map *isl_stream_read_map(struct isl_stream *s, int nparam) +{ + struct isl_obj obj; + + obj = obj_read(s, nparam); + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_map || + obj.type == isl_obj_set, goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + +__isl_give isl_set *isl_stream_read_set(struct isl_stream *s, int nparam) +{ + struct isl_obj obj; + + obj = obj_read(s, nparam); + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_set, goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + +__isl_give isl_union_map *isl_stream_read_union_map(struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s, -1); + if (obj.type == isl_obj_map) { + obj.type = isl_obj_union_map; + obj.v = isl_union_map_from_map(obj.v); + } + if (obj.type == isl_obj_set) { + obj.type = isl_obj_union_set; + obj.v = isl_union_set_from_set(obj.v); + } + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_union_map || + obj.type == isl_obj_union_set, goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + +__isl_give isl_union_set *isl_stream_read_union_set(struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s, -1); + if (obj.type == isl_obj_set) { + obj.type = isl_obj_union_set; + obj.v = isl_union_set_from_set(obj.v); + } + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + static struct isl_basic_map *basic_map_read(struct isl_stream *s, int nparam) { struct isl_obj obj; @@ -1208,27 +2365,25 @@ error: __isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx, FILE *input, int nparam) { - struct isl_obj obj; struct isl_map *map; struct isl_stream *s = isl_stream_new_file(ctx, input); if (!s) return NULL; - obj = obj_read(s, nparam); + map = isl_stream_read_map(s, nparam); isl_stream_free(s); - return obj.v; + return map; } __isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx, const char *str, int nparam) { - struct isl_obj obj; struct isl_map *map; struct isl_stream *s = isl_stream_new_str(ctx, str); if (!s) return NULL; - obj = obj_read(s, nparam); + map = isl_stream_read_map(s, nparam); isl_stream_free(s); - return obj.v; + return map; } __isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx, @@ -1259,58 +2414,141 @@ error: return NULL; } -static char *next_line(FILE *input, char *line, unsigned len) +__isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx, + FILE *input) { - char *p; + isl_union_map *umap; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) + return NULL; + umap = isl_stream_read_union_map(s); + isl_stream_free(s); + return umap; +} - do { - if (!(p = fgets(line, len, input))) - return NULL; - while (isspace(*p) && *p != '\n') - ++p; - } while (*p == '#' || *p == '\n'); +__isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx, + const char *str) +{ + isl_union_map *umap; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + umap = isl_stream_read_union_map(s); + isl_stream_free(s); + return umap; +} - return p; +__isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx, + FILE *input) +{ + isl_union_set *uset; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) + return NULL; + uset = isl_stream_read_union_set(s); + isl_stream_free(s); + return uset; } -static struct isl_vec *isl_vec_read_from_file_polylib(struct isl_ctx *ctx, - FILE *input) +__isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx, + const char *str) +{ + isl_union_set *uset; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + uset = isl_stream_read_union_set(s); + isl_stream_free(s); + return uset; +} + +static __isl_give isl_vec *isl_vec_read_polylib(struct isl_stream *s) { struct isl_vec *vec = NULL; - char line[1024]; - char val[1024]; - char *p; + struct isl_token *tok; unsigned size; int j; - int n; - int offset; - isl_assert(ctx, next_line(input, line, sizeof(line)), return NULL); - isl_assert(ctx, sscanf(line, "%u", &size) == 1, return NULL); + tok = isl_stream_next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting vector length"); + goto error; + } - vec = isl_vec_alloc(ctx, size); + size = isl_int_get_si(tok->u.v); + isl_token_free(tok); - p = next_line(input, line, sizeof(line)); - isl_assert(ctx, p, goto error); + vec = isl_vec_alloc(s->ctx, size); for (j = 0; j < size; ++j) { - n = sscanf(p, "%s%n", val, &offset); - isl_assert(ctx, n != 0, goto error); - isl_int_read(vec->el[j], val); - p += offset; + tok = isl_stream_next_token(s); + if (!tok || tok->type != ISL_TOKEN_VALUE) { + isl_stream_error(s, tok, "expecting constant value"); + goto error; + } + isl_int_set(vec->el[j], tok->u.v); + isl_token_free(tok); } return vec; error: + isl_token_free(tok); isl_vec_free(vec); return NULL; } -struct isl_vec *isl_vec_read_from_file(struct isl_ctx *ctx, - FILE *input, unsigned input_format) +static __isl_give isl_vec *vec_read(struct isl_stream *s) { - if (input_format == ISL_FORMAT_POLYLIB) - return isl_vec_read_from_file_polylib(ctx, input); - else - isl_assert(ctx, 0, return NULL); + return isl_vec_read_polylib(s); +} + +__isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input) +{ + isl_vec *v; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) + return NULL; + v = vec_read(s); + isl_stream_free(s); + return v; +} + +__isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial( + struct isl_stream *s) +{ + struct isl_obj obj; + + obj = obj_read(s, -1); + if (obj.v) + isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial, + goto error); + + return obj.v; +error: + obj.type->free(obj.v); + return NULL; +} + +__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx, + const char *str) +{ + isl_pw_qpolynomial *pwqp; + struct isl_stream *s = isl_stream_new_str(ctx, str); + if (!s) + return NULL; + pwqp = isl_stream_read_pw_qpolynomial(s); + isl_stream_free(s); + return pwqp; +} + +__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx, + FILE *input) +{ + isl_pw_qpolynomial *pwqp; + struct isl_stream *s = isl_stream_new_file(ctx, input); + if (!s) + return NULL; + pwqp = isl_stream_read_pw_qpolynomial(s); + isl_stream_free(s); + return pwqp; }