X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_tab_pip.c;h=2592a285c0e179164254439f4b2c0e0d84bd12ed;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=4e613f5e5351d77a7886b8da5b614337db735aa9;hpb=6817c5f804b1f77ab174af03b960e7c2e10fe342;p=platform%2Fupstream%2Fisl.git diff --git a/isl_tab_pip.c b/isl_tab_pip.c index 4e613f5..2592a28 100644 --- a/isl_tab_pip.c +++ b/isl_tab_pip.c @@ -2,7 +2,7 @@ * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * - * Use of this software is governed by the GNU LGPLv2.1 license + * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium @@ -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) @@ -789,8 +816,8 @@ static struct isl_vec *get_row_parameter_div(struct isl_tab *tab, int row) isl_int_set(div->el[0], tab->mat->row[row][0]); get_row_parameter_line(tab, row, div->el + 1); - normalize_div(div); isl_seq_neg(div->el + 1, div->el + 1, div->size - 1); + normalize_div(div); isl_seq_fdiv_r(div->el + 1, div->el + 1, div->el[0], div->size - 1); return div; @@ -1177,8 +1204,8 @@ static int report_conflicting_constraint(struct isl_tab *tab, int con) /* Given a conflicting row in the tableau, report all constraints * involved in the row to the caller. That is, the row itself - * (if represents a constraint) and all constraint columns with - * non-zero (and therefore negative) coefficient. + * (if it represents a constraint) and all constraint columns with + * non-zero (and therefore negative) coefficients. */ static int report_conflict(struct isl_tab *tab, int row) { @@ -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; @@ -2808,6 +2847,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 +2863,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 +3141,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; @@ -3225,6 +3280,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 +3324,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 +3623,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; @@ -3812,6 +3876,24 @@ error: sol->error = 1; } +/* Does "sol" contain a pair of partial solutions that could potentially + * be merged? + * + * We currently only check that "sol" is not in an error state + * and that there are at least two partial solutions of which the final two + * are defined at the same level. + */ +static int sol_has_mergeable_solutions(struct isl_sol *sol) +{ + if (sol->error) + return 0; + if (!sol->partial) + return 0; + if (!sol->partial->next) + return 0; + return sol->partial->level == sol->partial->next->level; +} + /* Compute the lexicographic minimum of the set represented by the main * tableau "tab" within the context "sol->context_tab". * @@ -3822,10 +3904,20 @@ error: * corresponding rows may not be marked as being non-negative. * In parts of the context where the added equality does not hold, * the main tableau is marked as being empty. + * + * Before we embark on the actual computation, we save a copy + * of the context. When we return, we check if there are any + * partial solutions that can potentially be merged. If so, + * we perform a rollback to the initial state of the context. + * The merging of partial solutions happens inside calls to + * sol_dec_level that are pushed onto the undo stack of the context. + * If there are no partial solutions that can potentially be merged + * then the rollback is skipped as it would just be wasted effort. */ static void find_solutions_main(struct isl_sol *sol, struct isl_tab *tab) { int row; + void *saved; if (!tab) goto error; @@ -3875,8 +3967,15 @@ static void find_solutions_main(struct isl_sol *sol, struct isl_tab *tab) row = tab->n_redundant - 1; } + saved = sol->context->op->save(sol->context); + find_solutions(sol, tab); + if (sol_has_mergeable_solutions(sol)) + sol->context->op->restore(sol->context, saved); + else + sol->context->op->discard(saved); + sol->level = 0; sol_pop(sol); @@ -4521,7 +4620,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 +4862,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 +5067,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 +5195,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;