X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_tab_pip.c;h=7fb34c7f0d606b90f4afbbcb12bd260f7eb312ed;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=ded4b30e962c8f48755d30bb53ec4299e398351a;hpb=056289f285e62c52cc59ee826172e4d3092ef3fe;p=platform%2Fupstream%2Fisl.git diff --git a/isl_tab_pip.c b/isl_tab_pip.c index ded4b30..7fb34c7 100644 --- a/isl_tab_pip.c +++ b/isl_tab_pip.c @@ -102,6 +102,8 @@ struct isl_context_op { void *(*save)(struct isl_context *context); /* restore saved context */ void (*restore)(struct isl_context *context, void *); + /* discard saved context */ + void (*discard)(void *); /* invalidate context */ void (*invalidate)(struct isl_context *context); /* free context */ @@ -117,6 +119,14 @@ struct isl_context_lex { struct isl_tab *tab; }; +/* A stack (linked list) of solutions of subtrees of the search space. + * + * "M" describes the solution in terms of the dimensions of "dom". + * The number of columns of "M" is one more than the total number + * of dimensions of "dom". + * + * If "M" is NULL, then there is no solution on "dom". + */ struct isl_partial_sol { int level; struct isl_basic_set *dom; @@ -201,6 +211,7 @@ static void sol_push_sol(struct isl_sol *sol, return; error: isl_basic_set_free(dom); + isl_mat_free(M); sol->error = 1; } @@ -304,13 +315,26 @@ static void sol_pop(struct isl_sol *sol) sol_pop_one(sol); } else { struct isl_basic_set *bset; + isl_mat *M; + unsigned n; + n = isl_basic_set_dim(partial->next->dom, isl_dim_div); + n -= n_div; bset = sol_domain(sol); - isl_basic_set_free(partial->next->dom); partial->next->dom = bset; + M = partial->next->M; + if (M) { + M = isl_mat_drop_cols(M, M->n_col - n, n); + partial->next->M = M; + if (!M) + goto error; + } partial->next->level = sol->level; + if (!bset) + goto error; + sol->partial = partial->next; isl_basic_set_free(partial->dom); isl_mat_free(partial->M); @@ -318,6 +342,9 @@ static void sol_pop(struct isl_sol *sol) } } else sol_pop_one(sol); + + if (0) +error: sol->error = 1; } static void sol_dec_level(struct isl_sol *sol) @@ -1957,6 +1984,7 @@ static int add_parametric_cut(struct isl_tab *tab, int row, n = tab->n_div; d = context->op->get_div(context, tab, div); + isl_vec_free(div); if (d < 0) return -1; @@ -2022,8 +2050,6 @@ static int add_parametric_cut(struct isl_tab *tab, int row, if (tab->row_sign) tab->row_sign[tab->con[r].index] = isl_tab_row_neg; - isl_vec_free(div); - row = tab->con[r].index; if (d >= n && context->op->detect_equalities(context, tab) < 0) @@ -2418,6 +2444,10 @@ static void context_lex_restore(struct isl_context *context, void *save) } } +static void context_lex_discard(void *save) +{ +} + static int context_lex_is_ok(struct isl_context *context) { struct isl_context_lex *clex = (struct isl_context_lex *)context; @@ -2537,6 +2567,7 @@ struct isl_context_op isl_context_lex_op = { context_lex_is_ok, context_lex_save, context_lex_restore, + context_lex_discard, context_lex_invalidate, context_lex_free, }; @@ -2585,6 +2616,14 @@ error: return NULL; } +/* Representation of the context when using generalized basis reduction. + * + * "shifted" contains the offsets of the unit hypercubes that lie inside the + * context. Any rational point in "shifted" can therefore be rounded + * up to an integer point in the context. + * If the context is constrained by any equality, then "shifted" is not used + * as it would be empty. + */ struct isl_context_gbr { struct isl_context context; struct isl_tab *tab; @@ -2690,6 +2729,8 @@ static struct isl_basic_set *drop_constant_terms(struct isl_basic_set *bset) static int use_shifted(struct isl_context_gbr *cgbr) { + if (!cgbr->tab) + return 0; return cgbr->tab->bmap->n_eq == 0 && cgbr->tab->bmap->n_div == 0; } @@ -2808,6 +2849,15 @@ error: return NULL; } +/* Add the equality described by "eq" to the context. + * If "check" is set, then we check if the context is empty after + * adding the equality. + * If "update" is set, then we check if the samples are still valid. + * + * We do not explicitly add shifted copies of the equality to + * cgbr->shifted since they would conflict with each other. + * Instead, we directly mark cgbr->shifted empty. + */ static void context_gbr_add_eq(struct isl_context *context, isl_int *eq, int check, int update) { @@ -2815,6 +2865,11 @@ static void context_gbr_add_eq(struct isl_context *context, isl_int *eq, cgbr->tab = add_gbr_eq(cgbr->tab, eq); + if (cgbr->shifted && !cgbr->shifted->empty && use_shifted(cgbr)) { + if (isl_tab_mark_empty(cgbr->shifted) < 0) + goto error; + } + if (cgbr->cone && cgbr->cone->n_col != cgbr->cone->n_dead) { if (isl_tab_extend_cons(cgbr->cone, 2) < 0) goto error; @@ -3088,7 +3143,9 @@ static int context_gbr_detect_equalities(struct isl_context *context, n_ineq = cgbr->tab->bmap->n_ineq; cgbr->tab = isl_tab_detect_equalities(cgbr->tab, cgbr->cone); - if (cgbr->tab && cgbr->tab->bmap->n_ineq > n_ineq) + if (!cgbr->tab) + return -1; + if (cgbr->tab->bmap->n_ineq > n_ineq) propagate_equalities(cgbr, tab, n_ineq); return 0; @@ -3165,6 +3222,9 @@ static void *context_gbr_save(struct isl_context *context) struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context; struct isl_gbr_tab_undo *snap; + if (!cgbr->tab) + return NULL; + snap = isl_alloc_type(cgbr->tab->mat->ctx, struct isl_gbr_tab_undo); if (!snap) return NULL; @@ -3225,6 +3285,12 @@ error: cgbr->tab = NULL; } +static void context_gbr_discard(void *save) +{ + struct isl_gbr_tab_undo *snap = (struct isl_gbr_tab_undo *)save; + free(snap); +} + static int context_gbr_is_ok(struct isl_context *context) { struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context; @@ -3263,6 +3329,7 @@ struct isl_context_op isl_context_gbr_op = { context_gbr_is_ok, context_gbr_save, context_gbr_restore, + context_gbr_discard, context_gbr_invalidate, context_gbr_free, }; @@ -3561,6 +3628,8 @@ static void find_in_pos(struct isl_sol *sol, struct isl_tab *tab, isl_int *ineq) if (!sol->error) sol->context->op->restore(sol->context, saved); + else + sol->context->op->discard(saved); return; error: sol->error = 1; @@ -4521,7 +4590,7 @@ static union isl_lex_res basic_map_partial_lexopt_symm( bmap = isl_basic_map_finalize(bmap); n_div = isl_basic_set_dim(dom, isl_dim_div); - dom = isl_basic_set_add(dom, isl_dim_set, 1); + dom = isl_basic_set_add_dims(dom, isl_dim_set, 1); dom = isl_basic_set_extend_constraints(dom, 0, n); for (i = 0; i < n; ++i) { k = isl_basic_set_alloc_inequality(dom); @@ -4763,11 +4832,13 @@ int isl_basic_map_foreach_lexopt(__isl_keep isl_basic_map *bmap, int max, struct isl_sol_for *sol_for = NULL; bmap = isl_basic_map_copy(bmap); + bmap = isl_basic_map_detect_equalities(bmap); if (!bmap) return -1; - bmap = isl_basic_map_detect_equalities(bmap); sol_for = sol_for_init(bmap, max, fn, user); + if (!sol_for) + goto error; if (isl_basic_map_plain_is_empty(bmap)) /* nothing */; @@ -4966,13 +5037,19 @@ __isl_give isl_vec *isl_tab_basic_set_non_trivial_lexmin( { int i, j; int r; - isl_ctx *ctx = isl_basic_set_get_ctx(bset); + isl_ctx *ctx; isl_vec *v = NULL; - isl_vec *sol = isl_vec_alloc(ctx, 0); + isl_vec *sol = NULL; struct isl_tab *tab; struct isl_trivial *triv = NULL; int level, init; + if (!bset) + return NULL; + + ctx = isl_basic_set_get_ctx(bset); + sol = isl_vec_alloc(ctx, 0); + tab = tab_for_lexmin(bset, NULL, 0, 0); if (!tab) goto error; @@ -5088,6 +5165,9 @@ __isl_give isl_vec *isl_tab_basic_set_non_neg_lexmin( isl_ctx *ctx = isl_basic_set_get_ctx(bset); isl_vec *sol; + if (!bset) + return NULL; + tab = tab_for_lexmin(bset, NULL, 0, 0); if (!tab) goto error;