/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
+ * Copyright 2010 INRIA Saclay
*
* Use of this software is governed by the GNU LGPLv2.1 license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
+ * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
+ * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
*/
+#include <isl_ctx_private.h>
#include "isl_map_private.h"
-#include "isl_seq.h"
+#include <isl/seq.h>
#include "isl_tab.h"
#include "isl_sample.h"
+#include <isl_mat_private.h>
/*
* The implementation of parametric integer linear programming in this file
* The strategy used for obtaining a feasible solution is different
* from the one used in isl_tab.c. In particular, in isl_tab.c,
* upon finding a constraint that is not yet satisfied, we pivot
- * in a row that increases the constant term of row holding the
+ * in a row that increases the constant term of the row holding the
* constraint, making sure the sample solution remains feasible
* for all the constraints it already satisfied.
* Here, we always pivot in the row holding the constraint,
* then the initial sample value may be chosen equal to zero.
* However, we will not make this assumption. Instead, we apply
* the "big parameter" trick. Any variable x is then not directly
- * used in the tableau, but instead it its represented by another
+ * used in the tableau, but instead it is represented by another
* variable x' = M + x, where M is an arbitrarily large (positive)
* value. x' is therefore always non-negative, whatever the value of x.
- * Taking as initial smaple value x' = 0 corresponds to x = -M,
+ * Taking as initial sample value x' = 0 corresponds to x = -M,
* which is always smaller than any possible value of x.
*
* The big parameter trick is used in the main tableau and
struct isl_basic_set *bset = NULL;
struct isl_mat *mat = NULL;
unsigned off;
- int row, i;
+ int row;
isl_int m;
if (sol->error || !tab)
isl_seq_clr(mat->row[1 + row], mat->n_col);
if (!tab->var[i].is_row) {
- /* no unbounded */
- isl_assert(mat->ctx, !tab->M, goto error2);
+ if (tab->M)
+ isl_die(mat->ctx, isl_error_invalid,
+ "unbounded optimum", goto error2);
continue;
}
r = tab->var[i].index;
- /* no unbounded */
- if (tab->M)
- isl_assert(mat->ctx, isl_int_eq(tab->mat->row[r][2],
- tab->mat->row[r][0]),
- goto error2);
+ if (tab->M &&
+ isl_int_ne(tab->mat->row[r][2], tab->mat->row[r][0]))
+ isl_die(mat->ctx, isl_error_invalid,
+ "unbounded optimum", goto error2);
isl_int_gcd(m, mat->row[0][0], tab->mat->row[r][0]);
isl_int_divexact(m, tab->mat->row[r][0], m);
scale_rows(mat, m, 1 + row);
error:
isl_basic_set_free(bset);
isl_mat_free(mat);
- sol_free(sol);
+ sol->error = 1;
}
struct isl_sol_map {
static void sol_map_free(struct isl_sol_map *sol_map)
{
+ if (!sol_map)
+ return;
if (sol_map->sol.context)
sol_map->sol.context->op->free(sol_map->sol.context);
isl_map_free(sol_map->map);
{
int i;
struct isl_basic_map *bmap = NULL;
- isl_basic_set *context_bset;
unsigned n_eq;
unsigned n_ineq;
unsigned nparam;
}
/* Return the first known violated constraint, i.e., a non-negative
- * contraint that currently has an either obviously negative value
+ * constraint that currently has an either obviously negative value
* or a previously determined to be negative value.
*
* If any constraint has a negative coefficient for the big parameter,
return -1;
}
+/* Check whether the invariant that all columns are lexico-positive
+ * is satisfied. This function is not called from the current code
+ * but is useful during debugging.
+ */
+static void check_lexpos(struct isl_tab *tab)
+{
+ unsigned off = 2 + tab->M;
+ int col;
+ int var;
+ int row;
+
+ for (col = tab->n_dead; col < tab->n_col; ++col) {
+ if (tab->col_var[col] >= 0 &&
+ (tab->col_var[col] < tab->n_param ||
+ tab->col_var[col] >= tab->n_var - tab->n_div))
+ continue;
+ for (var = tab->n_param; var < tab->n_var - tab->n_div; ++var) {
+ if (!tab->var[var].is_row) {
+ if (tab->var[var].index == col)
+ break;
+ else
+ continue;
+ }
+ row = tab->var[var].index;
+ if (isl_int_is_zero(tab->mat->row[row][off + col]))
+ continue;
+ if (isl_int_is_pos(tab->mat->row[row][off + col]))
+ break;
+ fprintf(stderr, "lexneg column %d (row %d)\n",
+ col, row);
+ }
+ if (var >= tab->n_var - tab->n_div)
+ fprintf(stderr, "zero column %d\n", col);
+ }
+}
+
+/* Report to the caller that the given constraint is part of an encountered
+ * conflict.
+ */
+static int report_conflicting_constraint(struct isl_tab *tab, int con)
+{
+ return tab->conflict(con, tab->conflict_user);
+}
+
+/* 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.
+ */
+static int report_conflict(struct isl_tab *tab, int row)
+{
+ int j;
+ isl_int *tr;
+
+ if (!tab->conflict)
+ return 0;
+
+ if (tab->row_var[row] < 0 &&
+ report_conflicting_constraint(tab, ~tab->row_var[row]) < 0)
+ return -1;
+
+ tr = tab->mat->row[row] + 2 + tab->M;
+
+ for (j = tab->n_dead; j < tab->n_col; ++j) {
+ if (tab->col_var[j] >= 0 &&
+ (tab->col_var[j] < tab->n_param ||
+ tab->col_var[j] >= tab->n_var - tab->n_div))
+ continue;
+
+ if (!isl_int_is_neg(tr[j]))
+ continue;
+
+ if (tab->col_var[j] < 0 &&
+ report_conflicting_constraint(tab, ~tab->col_var[j]) < 0)
+ return -1;
+ }
+
+ return 0;
+}
+
/* Resolve all known or obviously violated constraints through pivoting.
* In particular, as long as we can find any violated constraint, we
- * look for a pivoting column that would result in the lexicographicallly
+ * look for a pivoting column that would result in the lexicographically
* smallest increment in the sample point. If there is no such column
* then the tableau is infeasible.
*/
-static struct isl_tab *restore_lexmin(struct isl_tab *tab) WARN_UNUSED;
-static struct isl_tab *restore_lexmin(struct isl_tab *tab)
+static int restore_lexmin(struct isl_tab *tab) WARN_UNUSED;
+static int restore_lexmin(struct isl_tab *tab)
{
int row, col;
if (!tab)
- return NULL;
+ return -1;
if (tab->empty)
- return tab;
+ return 0;
while ((row = first_neg(tab)) != -1) {
col = lexmin_pivot_col(tab, row);
if (col >= tab->n_col) {
+ if (report_conflict(tab, row) < 0)
+ return -1;
if (isl_tab_mark_empty(tab) < 0)
- goto error;
- return tab;
+ return -1;
+ return 0;
}
if (col < 0)
- goto error;
+ return -1;
if (isl_tab_pivot(tab, row, col) < 0)
- goto error;
+ return -1;
}
- return tab;
-error:
- isl_tab_free(tab);
- return NULL;
+ return 0;
}
/* Given a row that represents an equality, look for an appropriate
if (isl_tab_kill_col(tab, i) < 0)
goto error;
tab->n_eq++;
-
- tab = restore_lexmin(tab);
}
return tab;
* In the end we try to use one of the two constraints to eliminate
* a column.
*/
-static struct isl_tab *add_lexmin_eq(struct isl_tab *tab, isl_int *eq) WARN_UNUSED;
-static struct isl_tab *add_lexmin_eq(struct isl_tab *tab, isl_int *eq)
+static int add_lexmin_eq(struct isl_tab *tab, isl_int *eq) WARN_UNUSED;
+static int add_lexmin_eq(struct isl_tab *tab, isl_int *eq)
{
int r1, r2;
int row;
struct isl_tab_undo *snap;
if (!tab)
- return NULL;
+ return -1;
snap = isl_tab_snap(tab);
r1 = isl_tab_add_row(tab, eq);
if (r1 < 0)
- goto error;
+ return -1;
tab->con[r1].is_nonneg = 1;
if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r1]) < 0)
- goto error;
+ return -1;
row = tab->con[r1].index;
if (is_constant(tab, row)) {
if (!isl_int_is_zero(tab->mat->row[row][1]) ||
(tab->M && !isl_int_is_zero(tab->mat->row[row][2]))) {
if (isl_tab_mark_empty(tab) < 0)
- goto error;
- return tab;
+ return -1;
+ return 0;
}
if (isl_tab_rollback(tab, snap) < 0)
- goto error;
- return tab;
+ return -1;
+ return 0;
}
- tab = restore_lexmin(tab);
- if (!tab || tab->empty)
- return tab;
+ if (restore_lexmin(tab) < 0)
+ return -1;
+ if (tab->empty)
+ return 0;
isl_seq_neg(eq, eq, 1 + tab->n_var);
r2 = isl_tab_add_row(tab, eq);
if (r2 < 0)
- goto error;
+ return -1;
tab->con[r2].is_nonneg = 1;
if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r2]) < 0)
- goto error;
+ return -1;
- tab = restore_lexmin(tab);
- if (!tab || tab->empty)
- return tab;
+ if (restore_lexmin(tab) < 0)
+ return -1;
+ if (tab->empty)
+ return 0;
if (!tab->con[r1].is_row) {
if (isl_tab_kill_col(tab, tab->con[r1].index) < 0)
- goto error;
+ return -1;
} else if (!tab->con[r2].is_row) {
if (isl_tab_kill_col(tab, tab->con[r2].index) < 0)
- goto error;
- } else if (isl_int_is_zero(tab->mat->row[tab->con[r1].index][1])) {
- unsigned off = 2 + tab->M;
- int i;
- int row = tab->con[r1].index;
- i = isl_seq_first_non_zero(tab->mat->row[row]+off+tab->n_dead,
- tab->n_col - tab->n_dead);
- if (i != -1) {
- if (isl_tab_pivot(tab, row, tab->n_dead + i) < 0)
- goto error;
- if (isl_tab_kill_col(tab, tab->n_dead + i) < 0)
- goto error;
- }
+ return -1;
}
if (tab->bmap) {
tab->bmap = isl_basic_map_add_ineq(tab->bmap, eq);
if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0)
- goto error;
+ return -1;
isl_seq_neg(eq, eq, 1 + tab->n_var);
tab->bmap = isl_basic_map_add_ineq(tab->bmap, eq);
isl_seq_neg(eq, eq, 1 + tab->n_var);
if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0)
- goto error;
+ return -1;
if (!tab->bmap)
- goto error;
+ return -1;
}
- return tab;
-error:
- isl_tab_free(tab);
- return NULL;
+ return 0;
}
/* Add an inequality to the tableau, resolving violations using
return tab;
}
- tab = restore_lexmin(tab);
- if (tab && !tab->empty && tab->con[r].is_row &&
+ if (restore_lexmin(tab) < 0)
+ goto error;
+ if (!tab->empty && tab->con[r].is_row &&
isl_tab_row_is_redundant(tab, tab->con[r].index))
if (isl_tab_mark_redundant(tab, tab->con[r].index) < 0)
goto error;
if (row < 0)
goto error;
} while ((var = next_non_integer_var(tab, var, &flags)) != -1);
- tab = restore_lexmin(tab);
- if (!tab || tab->empty)
+ if (restore_lexmin(tab) < 0)
+ goto error;
+ if (tab->empty)
break;
}
return tab;
static struct isl_tab *check_integer_feasible(struct isl_tab *tab)
{
struct isl_tab_undo *snap;
- int feasible;
if (!tab)
return NULL;
return i < tab->n_sample;
}
-/* Add a div specifed by "div" to the tableau "tab" and return
+/* Add a div specified by "div" to the tableau "tab" and return
* 1 if the div is obviously non-negative.
*/
static int context_tab_add_div(struct isl_tab *tab, struct isl_vec *div,
if (!tab || tab->empty)
return tab;
}
+ if (bmap->n_eq && restore_lexmin(tab) < 0)
+ goto error;
for (i = 0; i < bmap->n_ineq; ++i) {
if (max)
isl_seq_neg(bmap->ineq[i] + 1 + tab->n_param,
struct isl_context_lex *clex = (struct isl_context_lex *)context;
if (isl_tab_extend_cons(clex->tab, 2) < 0)
goto error;
- clex->tab = add_lexmin_eq(clex->tab, eq);
+ if (add_lexmin_eq(clex->tab, eq) < 0)
+ goto error;
if (check) {
int v = tab_has_valid_sample(clex->tab, eq, 1);
if (v < 0)
return get_div(tab, context, div);
}
+/* Add a div specified by "div" to the context tableau and return
+ * 1 if the div is obviously non-negative.
+ * context_tab_add_div will always return 1, because all variables
+ * in a isl_context_lex tableau are non-negative.
+ * However, if we are using a big parameter in the context, then this only
+ * reflects the non-negativity of the variable used to _encode_ the
+ * div, i.e., div' = M + div, so we can't draw any conclusions.
+ */
static int context_lex_add_div(struct isl_context *context, struct isl_vec *div)
{
struct isl_context_lex *clex = (struct isl_context_lex *)context;
- return context_tab_add_div(clex->tab, div,
+ int nonneg;
+ nonneg = context_tab_add_div(clex->tab, div,
context_lex_add_ineq_wrap, context);
+ if (nonneg < 0)
+ return -1;
+ if (clex->tab->M)
+ return 0;
+ return nonneg;
}
static int context_lex_detect_equalities(struct isl_context *context,
return -1;
r = best_split(tab, clex->tab);
- if (isl_tab_rollback(clex->tab, snap) < 0)
+ if (r >= 0 && isl_tab_rollback(clex->tab, snap) < 0)
return -1;
return r;
struct isl_context_lex *clex = (struct isl_context_lex *)context;
struct isl_tab_undo *snap;
+ if (!tab)
+ return NULL;
+
snap = isl_tab_snap(clex->tab);
if (isl_tab_push_basis(clex->tab) < 0)
goto error;
clex->context.op = &isl_context_lex_op;
clex->tab = context_tab_for_lexmin(isl_basic_set_copy(dom));
- clex->tab = restore_lexmin(clex->tab);
+ if (restore_lexmin(clex->tab) < 0)
+ goto error;
clex->tab = check_integer_feasible(clex->tab);
if (!clex->tab)
goto error;
struct isl_context *context, struct isl_tab *tab)
{
struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context;
+ if (!tab)
+ return NULL;
return tab_detect_nonnegative_parameters(tab, cgbr->tab);
}
static struct isl_tab *add_gbr_eq(struct isl_tab *tab, isl_int *eq)
{
- int r;
-
if (!tab)
return NULL;
if (isl_tab_extend_cons(tab, 2) < 0)
goto error;
- tab = isl_tab_add_eq(tab, eq);
+ if (isl_tab_add_eq(tab, eq) < 0)
+ goto error;
return tab;
error:
if (cgbr->cone && cgbr->cone->n_col != cgbr->cone->n_dead) {
if (isl_tab_extend_cons(cgbr->cone, 2) < 0)
goto error;
- cgbr->cone = isl_tab_add_eq(cgbr->cone, eq);
+ if (isl_tab_add_eq(cgbr->cone, eq) < 0)
+ goto error;
}
if (check) {
{
int i;
int col;
- unsigned dim = tab->n_var - tab->n_param - tab->n_div;
if (tab->n_var == 0)
return -1;
if (isl_tab_kill_col(tab, j) < 0)
goto error;
- tab = restore_lexmin(tab);
+ if (restore_lexmin(tab) < 0)
+ goto error;
}
isl_vec_free(eq);
{
struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context;
struct isl_ctx *ctx;
- int i;
- enum isl_lp_result res;
unsigned n_ineq;
ctx = cgbr->tab->mat->ctx;
snap = isl_tab_snap(cgbr->tab);
r = best_split(tab, cgbr->tab);
- if (isl_tab_rollback(cgbr->tab, snap) < 0)
+ if (r >= 0 && isl_tab_rollback(cgbr->tab, snap) < 0)
return -1;
return r;
static struct isl_sol_map *sol_map_init(struct isl_basic_map *bmap,
struct isl_basic_set *dom, int track_empty, int max)
{
- struct isl_sol_map *sol_map;
+ struct isl_sol_map *sol_map = NULL;
+
+ if (!bmap)
+ goto error;
- sol_map = isl_calloc_type(bset->ctx, struct isl_sol_map);
+ sol_map = isl_calloc_type(bmap->ctx, struct isl_sol_map);
if (!sol_map)
goto error;
find_solutions(sol, tab);
- sol->context->op->restore(sol->context, saved);
+ if (!sol->error)
+ sol->context->op->restore(sol->context, saved);
return;
error:
sol->error = 1;
int empty;
void *saved;
- if (!sol->context)
+ if (!sol->context || sol->error)
goto error;
saved = sol->context->op->save(sol->context);
* coefficient are integral, then there is nothing that can be done
* and the tableau has no integral solution.
* If, on the other hand, one or more of the other columns have rational
- * coeffcients, but the parameter coefficients are all integral, then
+ * coefficients, but the parameter coefficients are all integral, then
* we can perform a regular (non-parametric) cut.
* Finally, if there is any parameter coefficient that is non-integral,
* then we need to involve the context tableau. There are two cases here.
static void find_solutions(struct isl_sol *sol, struct isl_tab *tab)
{
struct isl_context *context;
+ int r;
if (!tab || sol->error)
goto error;
if (context->op->is_empty(context))
goto done;
- for (; tab && !tab->empty; tab = restore_lexmin(tab)) {
+ for (r = 0; r >= 0 && tab && !tab->empty; r = restore_lexmin(tab)) {
int flags;
int row;
enum isl_tab_row_sign sgn;
row = split;
isl_seq_neg(ineq->el, ineq->el, ineq->size);
isl_int_sub_ui(ineq->el[0], ineq->el[0], 1);
- context->op->add_ineq(context, ineq->el, 0, 1);
+ if (!sol->error)
+ context->op->add_ineq(context, ineq->el, 0, 1);
isl_vec_free(ineq);
if (sol->error)
goto error;
if (d < 0)
goto error;
ineq = ineq_for_div(context->op->peek_basic_set(context), d);
+ if (!ineq)
+ goto error;
sol_inc_level(sol);
no_sol_in_strict(sol, tab, ineq);
isl_seq_neg(ineq->el, ineq->el, ineq->size);
if (row < 0)
goto error;
}
+ if (r < 0)
+ goto error;
done:
sol_add(sol, tab);
isl_tab_free(tab);
return;
error:
isl_tab_free(tab);
- sol_free(sol);
+ sol->error = 1;
}
/* Compute the lexicographic minimum of the set represented by the main
{
int row;
+ if (!tab)
+ goto error;
+
sol->level = 0;
for (row = tab->n_redundant; row < tab->n_row; ++row) {
+ tab->n_param - (tab->n_var - tab->n_div);
eq = isl_vec_alloc(tab->mat->ctx, 1+tab->n_param+tab->n_div);
+ if (!eq)
+ goto error;
get_row_parameter_line(tab, row, eq->el);
isl_int_neg(eq->el[1 + p], tab->mat->row[row][0]);
eq = isl_vec_normalize(eq);
return;
error:
isl_tab_free(tab);
- sol_free(sol);
+ sol->error = 1;
}
static void sol_map_find_solutions(struct isl_sol_map *sol_map,
return NULL;
}
-/* Compute the lexicographic minimum (or maximum if "max" is set)
- * of "bmap" over the domain "dom" and return the result as a map.
- * If "empty" is not NULL, then *empty is assigned a set that
- * contains those parts of the domain where there is no solution.
- * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL),
- * then we compute the rational optimum. Otherwise, we compute
- * the integral optimum.
+/* Base case of isl_tab_basic_map_partial_lexopt, after removing
+ * some obvious symmetries.
*
- * We perform some preprocessing. As the PILP solver does not
- * handle implicit equalities very well, we first make sure all
- * the equalities are explicitly available.
- * We also make sure the divs in the domain are properly order,
+ * We make sure the divs in the domain are properly ordered,
* because they will be added one by one in the given order
* during the construction of the solution map.
*/
-struct isl_map *isl_tab_basic_map_partial_lexopt(
- struct isl_basic_map *bmap, struct isl_basic_set *dom,
- struct isl_set **empty, int max)
+static __isl_give isl_map *basic_map_partial_lexopt_base(
+ __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,
+ __isl_give isl_set **empty, int max)
{
+ isl_map *result = NULL;
struct isl_tab *tab;
- struct isl_map *result = NULL;
struct isl_sol_map *sol_map = NULL;
struct isl_context *context;
- struct isl_basic_map *eq;
-
- if (empty)
- *empty = NULL;
- if (!bmap || !dom)
- goto error;
-
- isl_assert(bmap->ctx,
- isl_basic_map_compatible_domain(bmap, dom), goto error);
-
- eq = isl_basic_map_copy(bmap);
- eq = isl_basic_map_intersect_domain(eq, isl_basic_set_copy(dom));
- eq = isl_basic_map_affine_hull(eq);
- bmap = isl_basic_map_intersect(bmap, eq);
if (dom->n_div) {
dom = isl_basic_set_order_divs(dom);
goto error;
context = sol_map->sol.context;
- if (isl_basic_set_fast_is_empty(context->op->peek_basic_set(context)))
+ if (isl_basic_set_plain_is_empty(context->op->peek_basic_set(context)))
/* nothing */;
- else if (isl_basic_map_fast_is_empty(bmap))
+ else if (isl_basic_map_plain_is_empty(bmap))
sol_map_add_empty_if_needed(sol_map,
isl_basic_set_copy(context->op->peek_basic_set(context)));
else {
return NULL;
}
+/* Structure used during detection of parallel constraints.
+ * n_in: number of "input" variables: isl_dim_param + isl_dim_in
+ * n_out: number of "output" variables: isl_dim_out + isl_dim_div
+ * val: the coefficients of the output variables
+ */
+struct isl_constraint_equal_info {
+ isl_basic_map *bmap;
+ unsigned n_in;
+ unsigned n_out;
+ isl_int *val;
+};
+
+/* Check whether the coefficients of the output variables
+ * of the constraint in "entry" are equal to info->val.
+ */
+static int constraint_equal(const void *entry, const void *val)
+{
+ isl_int **row = (isl_int **)entry;
+ const struct isl_constraint_equal_info *info = val;
+
+ return isl_seq_eq((*row) + 1 + info->n_in, info->val, info->n_out);
+}
+
+/* Check whether "bmap" has a pair of constraints that have
+ * the same coefficients for the output variables.
+ * Note that the coefficients of the existentially quantified
+ * variables need to be zero since the existentially quantified
+ * of the result are usually not the same as those of the input.
+ * the isl_dim_out and isl_dim_div dimensions.
+ * If so, return 1 and return the row indices of the two constraints
+ * in *first and *second.
+ */
+static int parallel_constraints(__isl_keep isl_basic_map *bmap,
+ int *first, int *second)
+{
+ int i;
+ isl_ctx *ctx = isl_basic_map_get_ctx(bmap);
+ struct isl_hash_table *table = NULL;
+ struct isl_hash_table_entry *entry;
+ struct isl_constraint_equal_info info;
+ unsigned n_out;
+ unsigned n_div;
+
+ ctx = isl_basic_map_get_ctx(bmap);
+ table = isl_hash_table_alloc(ctx, bmap->n_ineq);
+ if (!table)
+ goto error;
+
+ info.n_in = isl_basic_map_dim(bmap, isl_dim_param) +
+ isl_basic_map_dim(bmap, isl_dim_in);
+ info.bmap = bmap;
+ n_out = isl_basic_map_dim(bmap, isl_dim_out);
+ n_div = isl_basic_map_dim(bmap, isl_dim_div);
+ info.n_out = n_out + n_div;
+ for (i = 0; i < bmap->n_ineq; ++i) {
+ uint32_t hash;
+
+ info.val = bmap->ineq[i] + 1 + info.n_in;
+ if (isl_seq_first_non_zero(info.val, n_out) < 0)
+ continue;
+ if (isl_seq_first_non_zero(info.val + n_out, n_div) >= 0)
+ continue;
+ hash = isl_seq_get_hash(info.val, info.n_out);
+ entry = isl_hash_table_find(ctx, table, hash,
+ constraint_equal, &info, 1);
+ if (!entry)
+ goto error;
+ if (entry->data)
+ break;
+ entry->data = &bmap->ineq[i];
+ }
+
+ if (i < bmap->n_ineq) {
+ *first = ((isl_int **)entry->data) - bmap->ineq;
+ *second = i;
+ }
+
+ isl_hash_table_free(ctx, table);
+
+ return i < bmap->n_ineq;
+error:
+ isl_hash_table_free(ctx, table);
+ return -1;
+}
+
+/* Given a set of upper bounds on the last "input" variable m,
+ * construct a set that assigns the minimal upper bound to m, i.e.,
+ * construct a set that divides 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 result
+ * consists of n basic sets, each one of the form
+ *
+ * m = b_i
+ * b_i <= b_j for j > i
+ * b_i < b_j for j < i
+ */
+static __isl_give isl_set *set_minimum(__isl_take isl_dim *dim,
+ __isl_take isl_mat *var)
+{
+ int i, j, k;
+ isl_basic_set *bset = NULL;
+ isl_ctx *ctx;
+ isl_set *set = NULL;
+
+ if (!dim || !var)
+ goto error;
+
+ ctx = isl_dim_get_ctx(dim);
+ set = isl_set_alloc_dim(isl_dim_copy(dim),
+ var->n_row, ISL_SET_DISJOINT);
+
+ for (i = 0; i < var->n_row; ++i) {
+ bset = isl_basic_set_alloc_dim(isl_dim_copy(dim), 0,
+ 1, var->n_row - 1);
+ k = isl_basic_set_alloc_equality(bset);
+ if (k < 0)
+ goto error;
+ isl_seq_cpy(bset->eq[k], var->row[i], var->n_col);
+ isl_int_set_si(bset->eq[k][var->n_col], -1);
+ for (j = 0; j < var->n_row; ++j) {
+ if (j == i)
+ continue;
+ k = isl_basic_set_alloc_inequality(bset);
+ if (k < 0)
+ goto error;
+ isl_seq_combine(bset->ineq[k], ctx->one, var->row[j],
+ ctx->negone, var->row[i],
+ var->n_col);
+ isl_int_set_si(bset->ineq[k][var->n_col], 0);
+ if (j < i)
+ isl_int_sub_ui(bset->ineq[k][0],
+ bset->ineq[k][0], 1);
+ }
+ bset = isl_basic_set_finalize(bset);
+ set = isl_set_add_basic_set(set, bset);
+ }
+
+ isl_dim_free(dim);
+ isl_mat_free(var);
+ return set;
+error:
+ isl_basic_set_free(bset);
+ isl_set_free(set);
+ isl_dim_free(dim);
+ isl_mat_free(var);
+ return NULL;
+}
+
+/* Given that the last input variable of "bmap" represents the minimum
+ * of the bounds in "cst", check whether we need to split the domain
+ * based on which bound attains the minimum.
+ *
+ * A split is needed when the minimum appears in an integer division
+ * or in an equality. Otherwise, it is only needed if it appears in
+ * an upper bound that is different from the upper bounds on which it
+ * is defined.
+ */
+static int need_split_map(__isl_keep isl_basic_map *bmap,
+ __isl_keep isl_mat *cst)
+{
+ int i, j;
+ unsigned total;
+ unsigned pos;
+
+ pos = cst->n_col - 1;
+ total = isl_basic_map_dim(bmap, isl_dim_all);
+
+ for (i = 0; i < bmap->n_div; ++i)
+ if (!isl_int_is_zero(bmap->div[i][2 + pos]))
+ return 1;
+
+ for (i = 0; i < bmap->n_eq; ++i)
+ if (!isl_int_is_zero(bmap->eq[i][1 + pos]))
+ return 1;
+
+ for (i = 0; i < bmap->n_ineq; ++i) {
+ if (isl_int_is_nonneg(bmap->ineq[i][1 + pos]))
+ continue;
+ if (!isl_int_is_negone(bmap->ineq[i][1 + pos]))
+ return 1;
+ if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + pos + 1,
+ total - pos - 1) >= 0)
+ return 1;
+
+ for (j = 0; j < cst->n_row; ++j)
+ if (isl_seq_eq(bmap->ineq[i], cst->row[j], cst->n_col))
+ break;
+ if (j >= cst->n_row)
+ return 1;
+ }
+
+ return 0;
+}
+
+static int need_split_set(__isl_keep isl_basic_set *bset,
+ __isl_keep isl_mat *cst)
+{
+ return need_split_map((isl_basic_map *)bset, cst);
+}
+
+/* Given a set of which the last set variable is the minimum
+ * of the bounds in "cst", split each basic set in the set
+ * in pieces where one of the bounds is (strictly) smaller than the others.
+ * This subdivision is given in "min_expr".
+ * The variable is subsequently projected out.
+ *
+ * We only do the split when it is needed.
+ * For example if the last input variable m = min(a,b) and the only
+ * constraints in the given basic set are lower bounds on m,
+ * i.e., l <= m = min(a,b), then we can simply project out m
+ * to obtain l <= a and l <= b, without having to split on whether
+ * m is equal to a or b.
+ */
+static __isl_give isl_set *split(__isl_take isl_set *empty,
+ __isl_take isl_set *min_expr, __isl_take isl_mat *cst)
+{
+ int n_in;
+ int i;
+ isl_dim *dim;
+ isl_set *res;
+
+ if (!empty || !min_expr || !cst)
+ goto error;
+
+ n_in = isl_set_dim(empty, isl_dim_set);
+ dim = isl_set_get_dim(empty);
+ dim = isl_dim_drop(dim, isl_dim_set, n_in - 1, 1);
+ res = isl_set_empty(dim);
+
+ for (i = 0; i < empty->n; ++i) {
+ isl_set *set;
+
+ set = isl_set_from_basic_set(isl_basic_set_copy(empty->p[i]));
+ if (need_split_set(empty->p[i], cst))
+ set = isl_set_intersect(set, isl_set_copy(min_expr));
+ set = isl_set_remove_dims(set, isl_dim_set, n_in - 1, 1);
+
+ res = isl_set_union_disjoint(res, set);
+ }
+
+ isl_set_free(empty);
+ isl_set_free(min_expr);
+ isl_mat_free(cst);
+ return res;
+error:
+ isl_set_free(empty);
+ isl_set_free(min_expr);
+ isl_mat_free(cst);
+ return NULL;
+}
+
+/* Given a map of which the last input variable is the minimum
+ * of the bounds in "cst", split each basic set in the set
+ * in pieces where one of the bounds is (strictly) smaller than the others.
+ * This subdivision is given in "min_expr".
+ * The variable is subsequently projected out.
+ *
+ * The implementation is essentially the same as that of "split".
+ */
+static __isl_give isl_map *split_domain(__isl_take isl_map *opt,
+ __isl_take isl_set *min_expr, __isl_take isl_mat *cst)
+{
+ int n_in;
+ int i;
+ isl_dim *dim;
+ isl_map *res;
+
+ if (!opt || !min_expr || !cst)
+ goto error;
+
+ n_in = isl_map_dim(opt, isl_dim_in);
+ dim = isl_map_get_dim(opt);
+ dim = isl_dim_drop(dim, isl_dim_in, n_in - 1, 1);
+ res = isl_map_empty(dim);
+
+ for (i = 0; i < opt->n; ++i) {
+ isl_map *map;
+
+ map = isl_map_from_basic_map(isl_basic_map_copy(opt->p[i]));
+ if (need_split_map(opt->p[i], cst))
+ map = isl_map_intersect_domain(map,
+ isl_set_copy(min_expr));
+ map = isl_map_remove_dims(map, isl_dim_in, n_in - 1, 1);
+
+ res = isl_map_union_disjoint(res, map);
+ }
+
+ isl_map_free(opt);
+ isl_set_free(min_expr);
+ isl_mat_free(cst);
+ return res;
+error:
+ isl_map_free(opt);
+ isl_set_free(min_expr);
+ isl_mat_free(cst);
+ return NULL;
+}
+
+static __isl_give isl_map *basic_map_partial_lexopt(
+ __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,
+ __isl_give isl_set **empty, int max);
+
+/* Given a basic map with at least two parallel constraints (as found
+ * by the function parallel_constraints), first look for more constraints
+ * parallel to the two constraint and replace the found list of parallel
+ * constraints by a single constraint with as "input" part the minimum
+ * of the input parts of the list of constraints. Then, recursively call
+ * basic_map_partial_lexopt (possibly finding more parallel constraints)
+ * and plug in the definition of the minimum in the result.
+ *
+ * More specifically, given a set of constraints
+ *
+ * a x + b_i(p) >= 0
+ *
+ * Replace this set by a single constraint
+ *
+ * a x + u >= 0
+ *
+ * with u a new parameter with constraints
+ *
+ * u <= b_i(p)
+ *
+ * Any solution to the new system is also a solution for the original system
+ * since
+ *
+ * a x >= -u >= -b_i(p)
+ *
+ * Moreover, m = min_i(b_i(p)) satisfies the constraints on u and can
+ * therefore be plugged into the solution.
+ */
+static __isl_give isl_map *basic_map_partial_lexopt_symm(
+ __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,
+ __isl_give isl_set **empty, int max, int first, int second)
+{
+ int i, n, k;
+ int *list = NULL;
+ unsigned n_in, n_out, n_div;
+ isl_ctx *ctx;
+ isl_vec *var = NULL;
+ isl_mat *cst = NULL;
+ isl_map *opt;
+ isl_set *min_expr;
+ isl_dim *map_dim, *set_dim;
+
+ map_dim = isl_basic_map_get_dim(bmap);
+ set_dim = empty ? isl_basic_set_get_dim(dom) : NULL;
+
+ n_in = isl_basic_map_dim(bmap, isl_dim_param) +
+ isl_basic_map_dim(bmap, isl_dim_in);
+ n_out = isl_basic_map_dim(bmap, isl_dim_all) - n_in;
+
+ ctx = isl_basic_map_get_ctx(bmap);
+ list = isl_alloc_array(ctx, int, bmap->n_ineq);
+ var = isl_vec_alloc(ctx, n_out);
+ if (!list || !var)
+ goto error;
+
+ list[0] = first;
+ list[1] = second;
+ isl_seq_cpy(var->el, bmap->ineq[first] + 1 + n_in, n_out);
+ for (i = second + 1, n = 2; i < bmap->n_ineq; ++i) {
+ if (isl_seq_eq(var->el, bmap->ineq[i] + 1 + n_in, n_out))
+ list[n++] = i;
+ }
+
+ cst = isl_mat_alloc(ctx, n, 1 + n_in);
+ if (!cst)
+ goto error;
+
+ for (i = 0; i < n; ++i)
+ isl_seq_cpy(cst->row[i], bmap->ineq[list[i]], 1 + n_in);
+
+ bmap = isl_basic_map_cow(bmap);
+ if (!bmap)
+ goto error;
+ for (i = n - 1; i >= 0; --i)
+ if (isl_basic_map_drop_inequality(bmap, list[i]) < 0)
+ goto error;
+
+ bmap = isl_basic_map_add(bmap, isl_dim_in, 1);
+ bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
+ k = isl_basic_map_alloc_inequality(bmap);
+ if (k < 0)
+ goto error;
+ isl_seq_clr(bmap->ineq[k], 1 + n_in);
+ isl_int_set_si(bmap->ineq[k][1 + n_in], 1);
+ isl_seq_cpy(bmap->ineq[k] + 1 + n_in + 1, var->el, n_out);
+ 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_extend_constraints(dom, 0, n);
+ for (i = 0; i < n; ++i) {
+ k = isl_basic_set_alloc_inequality(dom);
+ if (k < 0)
+ goto error;
+ isl_seq_cpy(dom->ineq[k], cst->row[i], 1 + n_in);
+ isl_int_set_si(dom->ineq[k][1 + n_in], -1);
+ isl_seq_clr(dom->ineq[k] + 1 + n_in + 1, n_div);
+ }
+
+ min_expr = set_minimum(isl_basic_set_get_dim(dom), isl_mat_copy(cst));
+
+ isl_vec_free(var);
+ free(list);
+
+ opt = basic_map_partial_lexopt(bmap, dom, empty, max);
+
+ if (empty) {
+ *empty = split(*empty,
+ isl_set_copy(min_expr), isl_mat_copy(cst));
+ *empty = isl_set_reset_dim(*empty, set_dim);
+ }
+
+ opt = split_domain(opt, min_expr, cst);
+ opt = isl_map_reset_dim(opt, map_dim);
+
+ return opt;
+error:
+ isl_dim_free(map_dim);
+ isl_dim_free(set_dim);
+ isl_mat_free(cst);
+ isl_vec_free(var);
+ free(list);
+ isl_basic_set_free(dom);
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+/* Recursive part of isl_tab_basic_map_partial_lexopt, after detecting
+ * equalities and removing redundant constraints.
+ *
+ * We first check if there are any parallel constraints (left).
+ * If not, we are in the base case.
+ * If there are parallel constraints, we replace them by a single
+ * constraint in basic_map_partial_lexopt_symm and then call
+ * this function recursively to look for more parallel constraints.
+ */
+static __isl_give isl_map *basic_map_partial_lexopt(
+ __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,
+ __isl_give isl_set **empty, int max)
+{
+ int par = 0;
+ int first, second;
+
+ if (!bmap)
+ goto error;
+
+ if (bmap->ctx->opt->pip_symmetry)
+ par = parallel_constraints(bmap, &first, &second);
+ if (par < 0)
+ goto error;
+ if (!par)
+ return basic_map_partial_lexopt_base(bmap, dom, empty, max);
+
+ return basic_map_partial_lexopt_symm(bmap, dom, empty, max,
+ first, second);
+error:
+ isl_basic_set_free(dom);
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+/* Compute the lexicographic minimum (or maximum if "max" is set)
+ * of "bmap" over the domain "dom" and return the result as a map.
+ * If "empty" is not NULL, then *empty is assigned a set that
+ * contains those parts of the domain where there is no solution.
+ * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL),
+ * then we compute the rational optimum. Otherwise, we compute
+ * the integral optimum.
+ *
+ * We perform some preprocessing. As the PILP solver does not
+ * handle implicit equalities very well, we first make sure all
+ * the equalities are explicitly available.
+ *
+ * We also add context constraints to the basic map and remove
+ * redundant constraints. This is only needed because of the
+ * way we handle simple symmetries. In particular, we currently look
+ * for symmetries on the constraints, before we set up the main tableau.
+ * It is then no good to look for symmetries on possibly redundant constraints.
+ */
+struct isl_map *isl_tab_basic_map_partial_lexopt(
+ struct isl_basic_map *bmap, struct isl_basic_set *dom,
+ struct isl_set **empty, int max)
+{
+ if (empty)
+ *empty = NULL;
+ if (!bmap || !dom)
+ goto error;
+
+ isl_assert(bmap->ctx,
+ isl_basic_map_compatible_domain(bmap, dom), goto error);
+
+ if (isl_basic_set_dim(dom, isl_dim_all) == 0)
+ return basic_map_partial_lexopt(bmap, dom, empty, max);
+
+ bmap = isl_basic_map_intersect_domain(bmap, isl_basic_set_copy(dom));
+ bmap = isl_basic_map_detect_equalities(bmap);
+ bmap = isl_basic_map_remove_redundancies(bmap);
+
+ return basic_map_partial_lexopt(bmap, dom, empty, max);
+error:
+ isl_basic_set_free(dom);
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
struct isl_sol_for {
struct isl_sol sol;
int (*fn)(__isl_take isl_basic_set *dom,
*
* Instead of constructing a basic map, this function calls a user
* defined function with the current context as a basic set and
- * an affine matrix reprenting the relation between the input and output.
+ * an affine matrix representing the relation between the input and output.
* The number of rows in this matrix is equal to one plus the number
* of output variables. The number of columns is equal to one plus
* the total dimension of the context, i.e., the number of parameters,
if (sol->sol.error || !dom || !M)
goto error;
- dom = isl_basic_set_simplify(dom);
dom = isl_basic_set_finalize(dom);
if (sol->fn(isl_basic_set_copy(dom), isl_mat_copy(M), sol->user) < 0)
struct isl_dim *dom_dim;
struct isl_basic_set *dom = NULL;
- sol_for = isl_calloc_type(bset->ctx, struct isl_sol_for);
+ sol_for = isl_calloc_type(bmap->ctx, struct isl_sol_for);
if (!sol_for)
goto error;
bmap = isl_basic_map_detect_equalities(bmap);
sol_for = sol_for_init(bmap, max, fn, user);
- if (isl_basic_map_fast_is_empty(bmap))
+ if (isl_basic_map_plain_is_empty(bmap))
/* nothing */;
else {
struct isl_tab *tab;
{
return isl_basic_map_foreach_lexopt(bmap, 1, fn, user);
}
+
+/* Check if the given sequence of len variables starting at pos
+ * represents a trivial (i.e., zero) solution.
+ * The variables are assumed to be non-negative and to come in pairs,
+ * with each pair representing a variable of unrestricted sign.
+ * The solution is trivial if each such pair in the sequence consists
+ * of two identical values, meaning that the variable being represented
+ * has value zero.
+ */
+static int region_is_trivial(struct isl_tab *tab, int pos, int len)
+{
+ int i;
+
+ if (len == 0)
+ return 0;
+
+ for (i = 0; i < len; i += 2) {
+ int neg_row;
+ int pos_row;
+
+ neg_row = tab->var[pos + i].is_row ?
+ tab->var[pos + i].index : -1;
+ pos_row = tab->var[pos + i + 1].is_row ?
+ tab->var[pos + i + 1].index : -1;
+
+ if ((neg_row < 0 ||
+ isl_int_is_zero(tab->mat->row[neg_row][1])) &&
+ (pos_row < 0 ||
+ isl_int_is_zero(tab->mat->row[pos_row][1])))
+ continue;
+
+ if (neg_row < 0 || pos_row < 0)
+ return 0;
+ if (isl_int_ne(tab->mat->row[neg_row][1],
+ tab->mat->row[pos_row][1]))
+ return 0;
+ }
+
+ return 1;
+}
+
+/* Return the index of the first trivial region or -1 if all regions
+ * are non-trivial.
+ */
+static int first_trivial_region(struct isl_tab *tab,
+ int n_region, struct isl_region *region)
+{
+ int i;
+
+ for (i = 0; i < n_region; ++i) {
+ if (region_is_trivial(tab, region[i].pos, region[i].len))
+ return i;
+ }
+
+ return -1;
+}
+
+/* Check if the solution is optimal, i.e., whether the first
+ * n_op entries are zero.
+ */
+static int is_optimal(__isl_keep isl_vec *sol, int n_op)
+{
+ int i;
+
+ for (i = 0; i < n_op; ++i)
+ if (!isl_int_is_zero(sol->el[1 + i]))
+ return 0;
+ return 1;
+}
+
+/* Add constraints to "tab" that ensure that any solution is significantly
+ * better that that represented by "sol". That is, find the first
+ * relevant (within first n_op) non-zero coefficient and force it (along
+ * with all previous coefficients) to be zero.
+ * If the solution is already optimal (all relevant coefficients are zero),
+ * then just mark the table as empty.
+ */
+static int force_better_solution(struct isl_tab *tab,
+ __isl_keep isl_vec *sol, int n_op)
+{
+ int i;
+ isl_ctx *ctx;
+ isl_vec *v = NULL;
+
+ if (!sol)
+ return -1;
+
+ for (i = 0; i < n_op; ++i)
+ if (!isl_int_is_zero(sol->el[1 + i]))
+ break;
+
+ if (i == n_op) {
+ if (isl_tab_mark_empty(tab) < 0)
+ return -1;
+ return 0;
+ }
+
+ ctx = isl_vec_get_ctx(sol);
+ v = isl_vec_alloc(ctx, 1 + tab->n_var);
+ if (!v)
+ return -1;
+
+ for (; i >= 0; --i) {
+ v = isl_vec_clr(v);
+ isl_int_set_si(v->el[1 + i], -1);
+ if (add_lexmin_eq(tab, v->el) < 0)
+ goto error;
+ }
+
+ isl_vec_free(v);
+ return 0;
+error:
+ isl_vec_free(v);
+ return -1;
+}
+
+struct isl_trivial {
+ int update;
+ int region;
+ int side;
+ struct isl_tab_undo *snap;
+};
+
+/* Return the lexicographically smallest non-trivial solution of the
+ * given ILP problem.
+ *
+ * All variables are assumed to be non-negative.
+ *
+ * n_op is the number of initial coordinates to optimize.
+ * That is, once a solution has been found, we will only continue looking
+ * for solution that result in significantly better values for those
+ * initial coordinates. That is, we only continue looking for solutions
+ * that increase the number of initial zeros in this sequence.
+ *
+ * A solution is non-trivial, if it is non-trivial on each of the
+ * specified regions. Each region represents a sequence of pairs
+ * of variables. A solution is non-trivial on such a region if
+ * at least one of these pairs consists of different values, i.e.,
+ * such that the non-negative variable represented by the pair is non-zero.
+ *
+ * Whenever a conflict is encountered, all constraints involved are
+ * reported to the caller through a call to "conflict".
+ *
+ * We perform a simple branch-and-bound backtracking search.
+ * Each level in the search represents initially trivial region that is forced
+ * to be non-trivial.
+ * At each level we consider n cases, where n is the length of the region.
+ * In terms of the n/2 variables of unrestricted signs being encoded by
+ * the region, we consider the cases
+ * x_0 >= 1
+ * x_0 <= -1
+ * x_0 = 0 and x_1 >= 1
+ * x_0 = 0 and x_1 <= -1
+ * x_0 = 0 and x_1 = 0 and x_2 >= 1
+ * x_0 = 0 and x_1 = 0 and x_2 <= -1
+ * ...
+ * The cases are considered in this order, assuming that each pair
+ * x_i_a x_i_b represents the value x_i_b - x_i_a.
+ * That is, x_0 >= 1 is enforced by adding the constraint
+ * x_0_b - x_0_a >= 1
+ */
+__isl_give isl_vec *isl_tab_basic_set_non_trivial_lexmin(
+ __isl_take isl_basic_set *bset, int n_op, int n_region,
+ struct isl_region *region,
+ int (*conflict)(int con, void *user), void *user)
+{
+ int i, j;
+ int r;
+ isl_ctx *ctx = isl_basic_set_get_ctx(bset);
+ isl_vec *v = NULL;
+ isl_vec *sol = isl_vec_alloc(ctx, 0);
+ struct isl_tab *tab;
+ struct isl_trivial *triv = NULL;
+ int level, init;
+
+ tab = tab_for_lexmin(isl_basic_map_from_range(bset), NULL, 0, 0);
+ if (!tab)
+ goto error;
+ tab->conflict = conflict;
+ tab->conflict_user = user;
+
+ v = isl_vec_alloc(ctx, 1 + tab->n_var);
+ triv = isl_calloc_array(ctx, struct isl_trivial, n_region);
+ if (!v || !triv)
+ goto error;
+
+ level = 0;
+ init = 1;
+
+ while (level >= 0) {
+ int side, base;
+
+ if (init) {
+ tab = cut_to_integer_lexmin(tab);
+ if (!tab)
+ goto error;
+ if (tab->empty)
+ goto backtrack;
+ r = first_trivial_region(tab, n_region, region);
+ if (r < 0) {
+ for (i = 0; i < level; ++i)
+ triv[i].update = 1;
+ isl_vec_free(sol);
+ sol = isl_tab_get_sample_value(tab);
+ if (!sol)
+ goto error;
+ if (is_optimal(sol, n_op))
+ break;
+ goto backtrack;
+ }
+ if (level >= n_region)
+ isl_die(ctx, isl_error_internal,
+ "nesting level too deep", goto error);
+ if (isl_tab_extend_cons(tab,
+ 2 * region[r].len + 2 * n_op) < 0)
+ goto error;
+ triv[level].region = r;
+ triv[level].side = 0;
+ }
+
+ r = triv[level].region;
+ side = triv[level].side;
+ base = 2 * (side/2);
+
+ if (side >= region[r].len) {
+backtrack:
+ level--;
+ init = 0;
+ if (level >= 0)
+ if (isl_tab_rollback(tab, triv[level].snap) < 0)
+ goto error;
+ continue;
+ }
+
+ if (triv[level].update) {
+ if (force_better_solution(tab, sol, n_op) < 0)
+ goto error;
+ triv[level].update = 0;
+ }
+
+ if (side == base && base >= 2) {
+ for (j = base - 2; j < base; ++j) {
+ v = isl_vec_clr(v);
+ isl_int_set_si(v->el[1 + region[r].pos + j], 1);
+ if (add_lexmin_eq(tab, v->el) < 0)
+ goto error;
+ }
+ }
+
+ triv[level].snap = isl_tab_snap(tab);
+ if (isl_tab_push_basis(tab) < 0)
+ goto error;
+
+ v = isl_vec_clr(v);
+ isl_int_set_si(v->el[0], -1);
+ isl_int_set_si(v->el[1 + region[r].pos + side], -1);
+ isl_int_set_si(v->el[1 + region[r].pos + (side ^ 1)], 1);
+ tab = add_lexmin_ineq(tab, v->el);
+
+ triv[level].side++;
+ level++;
+ init = 1;
+ }
+
+ free(triv);
+ isl_vec_free(v);
+ isl_tab_free(tab);
+ isl_basic_set_free(bset);
+
+ return sol;
+error:
+ free(triv);
+ isl_vec_free(v);
+ isl_tab_free(tab);
+ isl_basic_set_free(bset);
+ isl_vec_free(sol);
+ return NULL;
+}
+
+/* Return the lexicographically smallest rational point in "bset",
+ * assuming that all variables are non-negative.
+ * If "bset" is empty, then return a zero-length vector.
+ */
+ __isl_give isl_vec *isl_tab_basic_set_non_neg_lexmin(
+ __isl_take isl_basic_set *bset)
+{
+ struct isl_tab *tab;
+ isl_ctx *ctx = isl_basic_set_get_ctx(bset);
+ isl_vec *sol;
+
+ tab = tab_for_lexmin(isl_basic_map_from_range(bset), NULL, 0, 0);
+ if (!tab)
+ goto error;
+ if (tab->empty)
+ sol = isl_vec_alloc(ctx, 0);
+ else
+ sol = isl_tab_get_sample_value(tab);
+ isl_tab_free(tab);
+ isl_basic_set_free(bset);
+ return sol;
+error:
+ isl_tab_free(tab);
+ isl_basic_set_free(bset);
+ return NULL;
+}