X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_tab.c;h=e4cc386679d8760504af441f0741f9241120f479;hb=bebe6a21ae5f0d8eed204ad491154d3dfb916091;hp=a5e55b066ae29b265018c7e831d3bc6a7dc30633;hpb=747237f4a946ad88d45822eb281dc70665b81a76;p=platform%2Fupstream%2Fisl.git diff --git a/isl_tab.c b/isl_tab.c index a5e55b0..e4cc386 100644 --- a/isl_tab.c +++ b/isl_tab.c @@ -1,10 +1,12 @@ /* * Copyright 2008-2009 Katholieke Universiteit Leuven + * Copyright 2013 Ecole Normale Superieure * - * 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 + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include @@ -87,6 +89,11 @@ error: return NULL; } +isl_ctx *isl_tab_get_ctx(struct isl_tab *tab) +{ + return tab ? isl_mat_get_ctx(tab->mat) : NULL; +} + int isl_tab_extend_cons(struct isl_tab *tab, unsigned n_new) { unsigned off; @@ -787,6 +794,8 @@ static int push_union(struct isl_tab *tab, { struct isl_tab_undo *undo; + if (!tab) + return -1; if (!tab->need_undo) return 0; @@ -2596,6 +2605,29 @@ error: return NULL; } +/* Remove the sign constraint from constraint "con". + * + * If the constraint variable was originally marked non-negative, + * then we make sure we mark it non-negative again during rollback. + */ +int isl_tab_unrestrict(struct isl_tab *tab, int con) +{ + struct isl_tab_var *var; + + if (!tab) + return -1; + + var = &tab->con[con]; + if (!var->is_nonneg) + return 0; + + var->is_nonneg = 0; + if (isl_tab_push_var(tab, isl_tab_undo_unrestrict, var) < 0) + return -1; + + return 0; +} + int isl_tab_select_facet(struct isl_tab *tab, int con) { if (!tab) @@ -2697,6 +2729,106 @@ int isl_tab_detect_implicit_equalities(struct isl_tab *tab) return 0; } +/* Update the element of row_var or col_var that corresponds to + * constraint tab->con[i] to a move from position "old" to position "i". + */ +static int update_con_after_move(struct isl_tab *tab, int i, int old) +{ + int *p; + int index; + + index = tab->con[i].index; + if (index == -1) + return 0; + p = tab->con[i].is_row ? tab->row_var : tab->col_var; + if (p[index] != ~old) + isl_die(tab->mat->ctx, isl_error_internal, + "broken internal state", return -1); + p[index] = ~i; + + return 0; +} + +/* Rotate the "n" constraints starting at "first" to the right, + * putting the last constraint in the position of the first constraint. + */ +static int rotate_constraints(struct isl_tab *tab, int first, int n) +{ + int i, last; + struct isl_tab_var var; + + if (n <= 1) + return 0; + + last = first + n - 1; + var = tab->con[last]; + for (i = last; i > first; --i) { + tab->con[i] = tab->con[i - 1]; + if (update_con_after_move(tab, i, i - 1) < 0) + return -1; + } + tab->con[first] = var; + if (update_con_after_move(tab, first, last) < 0) + return -1; + + return 0; +} + +/* Make the equalities that are implicit in "bmap" but that have been + * detected in the corresponding "tab" explicit in "bmap" and update + * "tab" to reflect the new order of the constraints. + * + * In particular, if inequality i is an implicit equality then + * isl_basic_map_inequality_to_equality will move the inequality + * in front of the other equality and it will move the last inequality + * in the position of inequality i. + * In the tableau, the inequalities of "bmap" are stored after the equalities + * and so the original order + * + * E E E E E A A A I B B B B L + * + * is changed into + * + * I E E E E E A A A L B B B B + * + * where I is the implicit equality, the E are equalities, + * the A inequalities before I, the B inequalities after I and + * L the last inequality. + * We therefore need to rotate to the right two sets of constraints, + * those up to and including I and those after I. + * + * If "tab" contains any constraints that are not in "bmap" then they + * appear after those in "bmap" and they should be left untouched. + * + * Note that this function leaves "bmap" in a temporary state + * as it does not call isl_basic_map_gauss. Calling this function + * is the responsibility of the caller. + */ +__isl_give isl_basic_map *isl_tab_make_equalities_explicit(struct isl_tab *tab, + __isl_take isl_basic_map *bmap) +{ + int i; + + if (!tab || !bmap) + return isl_basic_map_free(bmap); + if (tab->empty) + return bmap; + + for (i = bmap->n_ineq - 1; i >= 0; --i) { + if (!isl_tab_is_equality(tab, bmap->n_eq + i)) + continue; + isl_basic_map_inequality_to_equality(bmap, i); + if (rotate_constraints(tab, 0, tab->n_eq + i + 1) < 0) + return isl_basic_map_free(bmap); + if (rotate_constraints(tab, tab->n_eq + i + 1, + bmap->n_ineq - i) < 0) + return isl_basic_map_free(bmap); + tab->n_eq++; + } + + return bmap; +} + static int con_is_redundant(struct isl_tab *tab, struct isl_tab_var *var) { if (!tab) @@ -2947,6 +3079,21 @@ static int unrelax(struct isl_tab *tab, struct isl_tab_var *var) return 0; } +/* Undo the operation performed by isl_tab_unrestrict. + * + * In particular, mark the variable as being non-negative and make + * sure the sample value respects this constraint. + */ +static int ununrestrict(struct isl_tab *tab, struct isl_tab_var *var) +{ + var->is_nonneg = 1; + + if (var->is_row && restore_row(tab, var) < -1) + return -1; + + return 0; +} + static int perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo) WARN_UNUSED; static int perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo) { @@ -2989,6 +3136,8 @@ static int perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo) break; case isl_tab_undo_relax: return unrelax(tab, var); + case isl_tab_undo_unrestrict: + return ununrestrict(tab, var); default: isl_die(tab->mat->ctx, isl_error_internal, "perform_undo_var called on invalid undo record", @@ -3089,6 +3238,7 @@ static int perform_undo(struct isl_tab *tab, struct isl_tab_undo *undo) case isl_tab_undo_zero: case isl_tab_undo_allocate: case isl_tab_undo_relax: + case isl_tab_undo_unrestrict: return perform_undo_var(tab, undo); case isl_tab_undo_bmap_eq: return isl_basic_map_free_equality(tab->bmap, 1);