/build/source/polly/lib/External/isl/isl_int

Bug Summary

File:	build/source/polly/lib/External/isl/isl_int_sioimath.h
Warning:	line 580, column 7 Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name isl_tab.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fdebug-prefix-map=/build/source/= -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-19/lib/clang/19 -I tools/polly/lib/External -I /build/source/polly/lib/External -I /build/source/polly/lib/External/isl -I /build/source/polly/lib/External/isl/include -I /build/source/polly/lib/External/isl/imath -I tools/polly/lib/External/isl -I tools/polly/include -I /build/source/polly/lib/External/pet/include -I tools/polly/lib/External/isl/include -I /build/source/polly/include -I include -I /build/source/llvm/include -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/llvm-19/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=../../../../ -fcoverage-prefix-map=/build/source/= -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -ferror-limit 19 -stack-protector 2 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2024-04-02-020108-72015-1 -x c /build/source/polly/lib/External/isl/isl_tab.c

/build/source/polly/lib/External/isl/isl_tab.c

→

1/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
* Copyright 2013      Ecole Normale Superieure
* Copyright 2014      INRIA Rocquencourt
* Copyright 2016      Sven Verdoolaege
*
* 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
* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
* B.P. 105 - 78153 Le Chesnay, France
*/

16#include <isl_ctx_private.h>
17#include <isl_mat_private.h>
18#include <isl_vec_private.h>
19#include "isl_map_private.h"
20#include "isl_tab.h"
21#include <isl_seq.h>
22#include <isl_config.h>

24#include <bset_to_bmap.c>
25#include <bset_from_bmap.c>

27/*
* The implementation of tableaus in this file was inspired by Section 8
* of David Detlefs, Greg Nelson and James B. Saxe, "Simplify: a theorem
* prover for program checking".
*/

33struct isl_tab *isl_tab_alloc(struct isl_ctx *ctx,
unsigned n_row, unsigned n_var, unsigned M)
35{
int i;
struct isl_tab *tab;
unsigned off = 2 + M;

tab = isl_calloc_type(ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_tab
)));
if (!tab)
return NULL((void*)0);
tab->mat = isl_mat_alloc(ctx, n_row, off + n_var);
if (!tab->mat)
goto error;
tab->var = isl_alloc_array(ctx, struct isl_tab_var, n_var)((struct isl_tab_var *)isl_malloc_or_die(ctx, (n_var)*sizeof(
struct isl_tab_var)));
if (n_var && !tab->var)
goto error;
tab->con = isl_alloc_array(ctx, struct isl_tab_var, n_row)((struct isl_tab_var *)isl_malloc_or_die(ctx, (n_row)*sizeof(
struct isl_tab_var)));
if (n_row && !tab->con)
goto error;
tab->col_var = isl_alloc_array(ctx, int, n_var)((int *)isl_malloc_or_die(ctx, (n_var)*sizeof(int)));
if (n_var && !tab->col_var)
goto error;
tab->row_var = isl_alloc_array(ctx, int, n_row)((int *)isl_malloc_or_die(ctx, (n_row)*sizeof(int)));
if (n_row && !tab->row_var)
goto error;
for (i = 0; i < n_var; ++i) {
tab->var[i].index = i;
tab->var[i].is_row = 0;
tab->var[i].is_nonneg = 0;
tab->var[i].is_zero = 0;
tab->var[i].is_redundant = 0;
tab->var[i].frozen = 0;
tab->var[i].negated = 0;
tab->col_var[i] = i;
}
tab->n_row = 0;
tab->n_con = 0;
tab->n_eq = 0;
tab->max_con = n_row;
tab->n_col = n_var;
tab->n_var = n_var;
tab->max_var = n_var;
tab->n_param = 0;
tab->n_div = 0;
tab->n_dead = 0;
tab->n_redundant = 0;
tab->strict_redundant = 0;
tab->need_undo = 0;
tab->rational = 0;
tab->empty = 0;
tab->in_undo = 0;
tab->M = M;
tab->cone = 0;
tab->bottom.type = isl_tab_undo_bottom;
tab->bottom.next = NULL((void*)0);
tab->top = &tab->bottom;

tab->n_zero = 0;
tab->n_unbounded = 0;
tab->basis = NULL((void*)0);

return tab;
95error:
isl_tab_free(tab);
return NULL((void*)0);
98}

100isl_ctx *isl_tab_get_ctx(struct isl_tab *tab)
101{
return tab ? isl_mat_get_ctx(tab->mat) : NULL((void*)0);
103}

105int isl_tab_extend_cons(struct isl_tab *tab, unsigned n_new)
106{
unsigned off;

if (!tab)
return -1;

off = 2 + tab->M;

if (tab->max_con < tab->n_con + n_new) {
struct isl_tab_var *con;

con = isl_realloc_array(tab->mat->ctx, tab->con,((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx
, tab->con, (tab->max_con + n_new)*sizeof(struct isl_tab_var
)))
		    struct isl_tab_var, tab->max_con + n_new)((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx
, tab->con, (tab->max_con + n_new)*sizeof(struct isl_tab_var
)));
if (!con)
	return -1;
tab->con = con;
tab->max_con += n_new;
}
if (tab->mat->n_row < tab->n_row + n_new) {
int *row_var;

tab->mat = isl_mat_extend(tab->mat,
			tab->n_row + n_new, off + tab->n_col);
if (!tab->mat)
	return -1;
row_var = isl_realloc_array(tab->mat->ctx, tab->row_var,((int *)isl_realloc_or_die(tab->mat->ctx, tab->row_var
, (tab->mat->n_row)*sizeof(int)))
			    int, tab->mat->n_row)((int *)isl_realloc_or_die(tab->mat->ctx, tab->row_var
, (tab->mat->n_row)*sizeof(int)));
if (!row_var)
	return -1;
tab->row_var = row_var;
if (tab->row_sign) {
	enum isl_tab_row_sign *s;
	s = isl_realloc_array(tab->mat->ctx, tab->row_sign,((enum isl_tab_row_sign *)isl_realloc_or_die(tab->mat->
ctx, tab->row_sign, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign
)))
			enum isl_tab_row_sign, tab->mat->n_row)((enum isl_tab_row_sign *)isl_realloc_or_die(tab->mat->
ctx, tab->row_sign, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign
)));
	if (!s)
		return -1;
	tab->row_sign = s;
}
}
return 0;
146}

148/* Make room for at least n_new extra variables.
* Return -1 if anything went wrong.
*/
151int isl_tab_extend_vars(struct isl_tab *tab, unsigned n_new)
152{
struct isl_tab_var *var;
unsigned off = 2 + tab->M;

if (tab->max_var < tab->n_var + n_new) {
var = isl_realloc_array(tab->mat->ctx, tab->var,((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx
, tab->var, (tab->n_var + n_new)*sizeof(struct isl_tab_var
)))
		    struct isl_tab_var, tab->n_var + n_new)((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx
, tab->var, (tab->n_var + n_new)*sizeof(struct isl_tab_var
)));
if (!var)
	return -1;
tab->var = var;
tab->max_var = tab->n_var + n_new;
}

if (tab->mat->n_col < off + tab->n_col + n_new) {
int *p;

tab->mat = isl_mat_extend(tab->mat,
		    tab->mat->n_row, off + tab->n_col + n_new);
if (!tab->mat)
	return -1;
p = isl_realloc_array(tab->mat->ctx, tab->col_var,((int *)isl_realloc_or_die(tab->mat->ctx, tab->col_var
, (tab->n_col + n_new)*sizeof(int)))
			    int, tab->n_col + n_new)((int *)isl_realloc_or_die(tab->mat->ctx, tab->col_var
, (tab->n_col + n_new)*sizeof(int)));
if (!p)
	return -1;
tab->col_var = p;
}

return 0;
180}

182static void free_undo_record(struct isl_tab_undo *undo)
183{
switch (undo->type) {
case isl_tab_undo_saved_basis:
free(undo->u.col_var);
break;
default:;
}
free(undo);
191}

193static void free_undo(struct isl_tab *tab)
194{
struct isl_tab_undo *undo, *next;

for (undo = tab->top; undo && undo != &tab->bottom; undo = next) {
next = undo->next;
free_undo_record(undo);
}
tab->top = undo;
202}

204void isl_tab_free(struct isl_tab *tab)
205{
if (!tab)
return;
free_undo(tab);
isl_mat_free(tab->mat);
isl_vec_free(tab->dual);
isl_basic_map_free(tab->bmap);
free(tab->var);
free(tab->con);
free(tab->row_var);
free(tab->col_var);
free(tab->row_sign);
isl_mat_free(tab->samples);
free(tab->sample_index);
isl_mat_free(tab->basis);
free(tab);
221}

223struct isl_tab *isl_tab_dup(struct isl_tab *tab)
224{
int i;
struct isl_tab *dup;
unsigned off;

if (!tab)
return NULL((void*)0);

off = 2 + tab->M;
dup = isl_calloc_type(tab->mat->ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(tab->mat->ctx, 1, sizeof
(struct isl_tab)));
if (!dup)
return NULL((void*)0);
dup->mat = isl_mat_dup(tab->mat);
if (!dup->mat)
goto error;
dup->var = isl_alloc_array(tab->mat->ctx, struct isl_tab_var, tab->max_var)((struct isl_tab_var *)isl_malloc_or_die(tab->mat->ctx,
 (tab->max_var)*sizeof(struct isl_tab_var)));
if (tab->max_var && !dup->var)
goto error;
for (i = 0; i < tab->n_var; ++i)
dup->var[i] = tab->var[i];
dup->con = isl_alloc_array(tab->mat->ctx, struct isl_tab_var, tab->max_con)((struct isl_tab_var *)isl_malloc_or_die(tab->mat->ctx,
 (tab->max_con)*sizeof(struct isl_tab_var)));
if (tab->max_con && !dup->con)
goto error;
for (i = 0; i < tab->n_con; ++i)
dup->con[i] = tab->con[i];
dup->col_var = isl_alloc_array(tab->mat->ctx, int, tab->mat->n_col - off)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->mat->
n_col - off)*sizeof(int)));
if ((tab->mat->n_col - off) && !dup->col_var)
goto error;
for (i = 0; i < tab->n_col; ++i)
dup->col_var[i] = tab->col_var[i];
dup->row_var = isl_alloc_array(tab->mat->ctx, int, tab->mat->n_row)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->mat->
n_row)*sizeof(int)));
if (tab->mat->n_row && !dup->row_var)
goto error;
for (i = 0; i < tab->n_row; ++i)
dup->row_var[i] = tab->row_var[i];
if (tab->row_sign) {
dup->row_sign = isl_alloc_array(tab->mat->ctx, enum isl_tab_row_sign,((enum isl_tab_row_sign *)isl_malloc_or_die(tab->mat->ctx
, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign)))
				tab->mat->n_row)((enum isl_tab_row_sign *)isl_malloc_or_die(tab->mat->ctx
, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign)));
if (tab->mat->n_row && !dup->row_sign)
	goto error;
for (i = 0; i < tab->n_row; ++i)
	dup->row_sign[i] = tab->row_sign[i];
}
if (tab->samples) {
dup->samples = isl_mat_dup(tab->samples);
if (!dup->samples)
	goto error;
dup->sample_index = isl_alloc_array(tab->mat->ctx, int,((int *)isl_malloc_or_die(tab->mat->ctx, (tab->samples
->n_row)*sizeof(int)))
					tab->samples->n_row)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->samples
->n_row)*sizeof(int)));
if (tab->samples->n_row && !dup->sample_index)
	goto error;
dup->n_sample = tab->n_sample;
dup->n_outside = tab->n_outside;
}
dup->n_row = tab->n_row;
dup->n_con = tab->n_con;
dup->n_eq = tab->n_eq;
dup->max_con = tab->max_con;
dup->n_col = tab->n_col;
dup->n_var = tab->n_var;
dup->max_var = tab->max_var;
dup->n_param = tab->n_param;
dup->n_div = tab->n_div;
dup->n_dead = tab->n_dead;
dup->n_redundant = tab->n_redundant;
dup->rational = tab->rational;
dup->empty = tab->empty;
dup->strict_redundant = 0;
dup->need_undo = 0;
dup->in_undo = 0;
dup->M = tab->M;
dup->cone = tab->cone;
dup->bottom.type = isl_tab_undo_bottom;
dup->bottom.next = NULL((void*)0);
dup->top = &dup->bottom;

dup->n_zero = tab->n_zero;
dup->n_unbounded = tab->n_unbounded;
dup->basis = isl_mat_dup(tab->basis);

return dup;
305error:
isl_tab_free(dup);
return NULL((void*)0);
308}

310/* Construct the coefficient matrix of the product tableau
* of two tableaus.
* mat{1,2} is the coefficient matrix of tableau {1,2}
* row{1,2} is the number of rows in tableau {1,2}
* col{1,2} is the number of columns in tableau {1,2}
* off is the offset to the coefficient column (skipping the
*	denominator, the constant term and the big parameter if any)
* r{1,2} is the number of redundant rows in tableau {1,2}
* d{1,2} is the number of dead columns in tableau {1,2}
*
* The order of the rows and columns in the result is as explained
* in isl_tab_product.
*/
323static __isl_give isl_mat *tab_mat_product(__isl_keep isl_mat *mat1,
__isl_keep isl_mat *mat2, unsigned row1, unsigned row2,
unsigned col1, unsigned col2,
unsigned off, unsigned r1, unsigned r2, unsigned d1, unsigned d2)
327{
int i;
struct isl_mat *prod;
unsigned n;

prod = isl_mat_alloc(mat1->ctx, mat1->n_row + mat2->n_row,
			off + col1 + col2);
if (!prod)
return NULL((void*)0);

n = 0;
for (i = 0; i < r1; ++i) {
isl_seq_cpy(prod->row[n + i], mat1->row[i], off + d1);
isl_seq_clr(prod->row[n + i] + off + d1, d2);
isl_seq_cpy(prod->row[n + i] + off + d1 + d2,
		mat1->row[i] + off + d1, col1 - d1);
isl_seq_clr(prod->row[n + i] + off + col1 + d1, col2 - d2);
}

n += r1;
for (i = 0; i < r2; ++i) {
isl_seq_cpy(prod->row[n + i], mat2->row[i], off);
isl_seq_clr(prod->row[n + i] + off, d1);
isl_seq_cpy(prod->row[n + i] + off + d1,
	    mat2->row[i] + off, d2);
isl_seq_clr(prod->row[n + i] + off + d1 + d2, col1 - d1);
isl_seq_cpy(prod->row[n + i] + off + col1 + d1,
	    mat2->row[i] + off + d2, col2 - d2);
}

n += r2;
for (i = 0; i < row1 - r1; ++i) {
isl_seq_cpy(prod->row[n + i], mat1->row[r1 + i], off + d1);
isl_seq_clr(prod->row[n + i] + off + d1, d2);
isl_seq_cpy(prod->row[n + i] + off + d1 + d2,
		mat1->row[r1 + i] + off + d1, col1 - d1);
isl_seq_clr(prod->row[n + i] + off + col1 + d1, col2 - d2);
}

n += row1 - r1;
for (i = 0; i < row2 - r2; ++i) {
isl_seq_cpy(prod->row[n + i], mat2->row[r2 + i], off);
isl_seq_clr(prod->row[n + i] + off, d1);
isl_seq_cpy(prod->row[n + i] + off + d1,
	    mat2->row[r2 + i] + off, d2);
isl_seq_clr(prod->row[n + i] + off + d1 + d2, col1 - d1);
isl_seq_cpy(prod->row[n + i] + off + col1 + d1,
	    mat2->row[r2 + i] + off + d2, col2 - d2);
}

return prod;
378}

380/* Update the row or column index of a variable that corresponds
* to a variable in the first input tableau.
*/
383static void update_index1(struct isl_tab_var *var,
unsigned r1, unsigned r2, unsigned d1, unsigned d2)
385{
if (var->index == -1)
return;
if (var->is_row && var->index >= r1)
var->index += r2;
if (!var->is_row && var->index >= d1)
var->index += d2;
392}

394/* Update the row or column index of a variable that corresponds
* to a variable in the second input tableau.
*/
397static void update_index2(struct isl_tab_var *var,
unsigned row1, unsigned col1,
unsigned r1, unsigned r2, unsigned d1, unsigned d2)
400{
if (var->index == -1)
return;
if (var->is_row) {
if (var->index < r2)
	var->index += r1;
else
	var->index += row1;
} else {
if (var->index < d2)
	var->index += d1;
else
	var->index += col1;
}
414}

416/* Create a tableau that represents the Cartesian product of the sets
* represented by tableaus tab1 and tab2.
* The order of the rows in the product is
*	- redundant rows of tab1
*	- redundant rows of tab2
*	- non-redundant rows of tab1
*	- non-redundant rows of tab2
* The order of the columns is
*	- denominator
*	- constant term
*	- coefficient of big parameter, if any
*	- dead columns of tab1
*	- dead columns of tab2
*	- live columns of tab1
*	- live columns of tab2
* The order of the variables and the constraints is a concatenation
* of order in the two input tableaus.
*/
434struct isl_tab *isl_tab_product(struct isl_tab *tab1, struct isl_tab *tab2)
435{
int i;
struct isl_tab *prod;
unsigned off;
unsigned r1, r2, d1, d2;

if (!tab1 || !tab2)
return NULL((void*)0);

isl_assert(tab1->mat->ctx, tab1->M == tab2->M, return NULL)do { if (tab1->M == tab2->M) break; do { isl_handle_error
(tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->M == tab2->M"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 444); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab1->rational == tab2->rational, return NULL)do { if (tab1->rational == tab2->rational) break; do { isl_handle_error
(tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->rational == tab2->rational"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 445); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab1->cone == tab2->cone, return NULL)do { if (tab1->cone == tab2->cone) break; do { isl_handle_error
(tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->cone == tab2->cone"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 446); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, !tab1->row_sign, return NULL)do { if (!tab1->row_sign) break; do { isl_handle_error(tab1
->mat->ctx, isl_error_unknown, "Assertion \"" "!tab1->row_sign"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 447); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, !tab2->row_sign, return NULL)do { if (!tab2->row_sign) break; do { isl_handle_error(tab1
->mat->ctx, isl_error_unknown, "Assertion \"" "!tab2->row_sign"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 448); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab1->n_param == 0, return NULL)do { if (tab1->n_param == 0) break; do { isl_handle_error(
tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->n_param == 0"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 449); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab2->n_param == 0, return NULL)do { if (tab2->n_param == 0) break; do { isl_handle_error(
tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab2->n_param == 0"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 450); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab1->n_div == 0, return NULL)do { if (tab1->n_div == 0) break; do { isl_handle_error(tab1
->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->n_div == 0"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 451); return
 ((void*)0); } while (0); } while (0);
isl_assert(tab1->mat->ctx, tab2->n_div == 0, return NULL)do { if (tab2->n_div == 0) break; do { isl_handle_error(tab1
->mat->ctx, isl_error_unknown, "Assertion \"" "tab2->n_div == 0"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 452); return
 ((void*)0); } while (0); } while (0);

off = 2 + tab1->M;
r1 = tab1->n_redundant;
r2 = tab2->n_redundant;
d1 = tab1->n_dead;
d2 = tab2->n_dead;
prod = isl_calloc_type(tab1->mat->ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(tab1->mat->ctx, 1,
 sizeof(struct isl_tab)));
if (!prod)
return NULL((void*)0);
prod->mat = tab_mat_product(tab1->mat, tab2->mat,
		tab1->n_row, tab2->n_row,
		tab1->n_col, tab2->n_col, off, r1, r2, d1, d2);
if (!prod->mat)
goto error;
prod->var = isl_alloc_array(tab1->mat->ctx, struct isl_tab_var,((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx
, (tab1->max_var + tab2->max_var)*sizeof(struct isl_tab_var
)))
			tab1->max_var + tab2->max_var)((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx
, (tab1->max_var + tab2->max_var)*sizeof(struct isl_tab_var
)));
if ((tab1->max_var + tab2->max_var) && !prod->var)
goto error;
for (i = 0; i < tab1->n_var; ++i) {
prod->var[i] = tab1->var[i];
update_index1(&prod->var[i], r1, r2, d1, d2);
}
for (i = 0; i < tab2->n_var; ++i) {
prod->var[tab1->n_var + i] = tab2->var[i];
update_index2(&prod->var[tab1->n_var + i],
		tab1->n_row, tab1->n_col,
		r1, r2, d1, d2);
}
prod->con = isl_alloc_array(tab1->mat->ctx, struct isl_tab_var,((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx
, (tab1->max_con + tab2->max_con)*sizeof(struct isl_tab_var
)))
			tab1->max_con +  tab2->max_con)((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx
, (tab1->max_con + tab2->max_con)*sizeof(struct isl_tab_var
)));
if ((tab1->max_con + tab2->max_con) && !prod->con)
goto error;
for (i = 0; i < tab1->n_con; ++i) {
prod->con[i] = tab1->con[i];
update_index1(&prod->con[i], r1, r2, d1, d2);
}
for (i = 0; i < tab2->n_con; ++i) {
prod->con[tab1->n_con + i] = tab2->con[i];
update_index2(&prod->con[tab1->n_con + i],
		tab1->n_row, tab1->n_col,
		r1, r2, d1, d2);
}
prod->col_var = isl_alloc_array(tab1->mat->ctx, int,((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->n_col
 + tab2->n_col)*sizeof(int)))
			tab1->n_col + tab2->n_col)((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->n_col
 + tab2->n_col)*sizeof(int)));
if ((tab1->n_col + tab2->n_col) && !prod->col_var)
goto error;
for (i = 0; i < tab1->n_col; ++i) {
int pos = i < d1 ? i : i + d2;
prod->col_var[pos] = tab1->col_var[i];
}
for (i = 0; i < tab2->n_col; ++i) {
int pos = i < d2 ? d1 + i : tab1->n_col + i;
int t = tab2->col_var[i];
if (t >= 0)
	t += tab1->n_var;
else
	t -= tab1->n_con;
prod->col_var[pos] = t;
}
prod->row_var = isl_alloc_array(tab1->mat->ctx, int,((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->mat
->n_row + tab2->mat->n_row)*sizeof(int)))
			tab1->mat->n_row + tab2->mat->n_row)((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->mat
->n_row + tab2->mat->n_row)*sizeof(int)));
if ((tab1->mat->n_row + tab2->mat->n_row) && !prod->row_var)
goto error;
for (i = 0; i < tab1->n_row; ++i) {
int pos = i < r1 ? i : i + r2;
prod->row_var[pos] = tab1->row_var[i];
}
for (i = 0; i < tab2->n_row; ++i) {
int pos = i < r2 ? r1 + i : tab1->n_row + i;
int t = tab2->row_var[i];
if (t >= 0)
	t += tab1->n_var;
else
	t -= tab1->n_con;
prod->row_var[pos] = t;
}
prod->samples = NULL((void*)0);
prod->sample_index = NULL((void*)0);
prod->n_row = tab1->n_row + tab2->n_row;
prod->n_con = tab1->n_con + tab2->n_con;
prod->n_eq = 0;
prod->max_con = tab1->max_con + tab2->max_con;
prod->n_col = tab1->n_col + tab2->n_col;
prod->n_var = tab1->n_var + tab2->n_var;
prod->max_var = tab1->max_var + tab2->max_var;
prod->n_param = 0;
prod->n_div = 0;
prod->n_dead = tab1->n_dead + tab2->n_dead;
prod->n_redundant = tab1->n_redundant + tab2->n_redundant;
prod->rational = tab1->rational;
prod->empty = tab1->empty || tab2->empty;
prod->strict_redundant = tab1->strict_redundant || tab2->strict_redundant;
prod->need_undo = 0;
prod->in_undo = 0;
prod->M = tab1->M;
prod->cone = tab1->cone;
prod->bottom.type = isl_tab_undo_bottom;
prod->bottom.next = NULL((void*)0);
prod->top = &prod->bottom;

prod->n_zero = 0;
prod->n_unbounded = 0;
prod->basis = NULL((void*)0);

return prod;
558error:
isl_tab_free(prod);
return NULL((void*)0);
561}

563static struct isl_tab_var *var_from_index(struct isl_tab *tab, int i)
564{
if (i >= 0)
return &tab->var[i];
else
return &tab->con[~i];
569}

571struct isl_tab_var *isl_tab_var_from_row(struct isl_tab *tab, int i)
572{
return var_from_index(tab, tab->row_var[i]);
574}

576static struct isl_tab_var *var_from_col(struct isl_tab *tab, int i)
577{
return var_from_index(tab, tab->col_var[i]);
579}

581/* Check if there are any upper bounds on column variable "var",
* i.e., non-negative rows where var appears with a negative coefficient.
* Return 1 if there are no such bounds.
*/
585static int max_is_manifestly_unbounded(struct isl_tab *tab,
struct isl_tab_var *var)
587{
int i;
unsigned off = 2 + tab->M;

if (var->is_row)
return 0;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
if (!isl_int_is_neg(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index
])) < 0))
	continue;
if (isl_tab_var_from_row(tab, i)->is_nonneg)
	return 0;
}
return 1;
600}

602/* Check if there are any lower bounds on column variable "var",
* i.e., non-negative rows where var appears with a positive coefficient.
* Return 1 if there are no such bounds.
*/
606static int min_is_manifestly_unbounded(struct isl_tab *tab,
struct isl_tab_var *var)
608{
int i;
unsigned off = 2 + tab->M;

if (var->is_row)
return 0;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
if (!isl_int_is_pos(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index
])) > 0))
	continue;
if (isl_tab_var_from_row(tab, i)->is_nonneg)
	return 0;
}
return 1;
621}

623static int row_cmp(struct isl_tab *tab, int r1, int r2, int c, isl_int *t)
624{
unsigned off = 2 + tab->M;

if (tab->M) {
int s;
isl_int_mul(*t, tab->mat->row[r1][2], tab->mat->row[r2][off+c])isl_sioimath_mul((*t), *(tab->mat->row[r1][2]), *(tab->
mat->row[r2][off+c]));
isl_int_submul(*t, tab->mat->row[r2][2], tab->mat->row[r1][off+c])isl_sioimath_submul((*t), *(tab->mat->row[r2][2]), *(tab
->mat->row[r1][off+c]));
s = isl_int_sgn(*t)isl_sioimath_sgn(*(*t));
if (s)
	return s;
}
isl_int_mul(*t, tab->mat->row[r1][1], tab->mat->row[r2][off + c])isl_sioimath_mul((*t), *(tab->mat->row[r1][1]), *(tab->
mat->row[r2][off + c]));
isl_int_submul(*t, tab->mat->row[r2][1], tab->mat->row[r1][off + c])isl_sioimath_submul((*t), *(tab->mat->row[r2][1]), *(tab
->mat->row[r1][off + c]));
return isl_int_sgn(*t)isl_sioimath_sgn(*(*t));
638}

640/* Given the index of a column "c", return the index of a row
* that can be used to pivot the column in, with either an increase
* (sgn > 0) or a decrease (sgn < 0) of the corresponding variable.
* If "var" is not NULL, then the row returned will be different from
* the one associated with "var".
*
* Each row in the tableau is of the form
*
*	x_r = a_r0 + \sum_i a_ri x_i
*
* Only rows with x_r >= 0 and with the sign of a_ri opposite to "sgn"
* impose any limit on the increase or decrease in the value of x_c
* and this bound is equal to a_r0 / |a_rc|.  We are therefore looking
* for the row with the smallest (most stringent) such bound.
* Note that the common denominator of each row drops out of the fraction.
* To check if row j has a smaller bound than row r, i.e.,
* a_j0 / |a_jc| < a_r0 / |a_rc| or a_j0 |a_rc| < a_r0 |a_jc|,
* we check if -sign(a_jc) (a_j0 a_rc - a_r0 a_jc) < 0,
* where -sign(a_jc) is equal to "sgn".
*/
660static int pivot_row(struct isl_tab *tab,
struct isl_tab_var *var, int sgn, int c)
662{
int j, r, tsgn;
isl_int t;
unsigned off = 2 + tab->M;

isl_int_init(t)isl_sioimath_init((t));
r = -1;
for (j = tab->n_redundant; j < tab->n_row; ++j) {
if (var && j == var->index)
	continue;
if (!isl_tab_var_from_row(tab, j)->is_nonneg)
	continue;
if (sgn * isl_int_sgn(tab->mat->row[j][off + c])isl_sioimath_sgn(*(tab->mat->row[j][off + c])) >= 0)
	continue;
if (r < 0) {
	r = j;
	continue;
}
tsgn = sgn * row_cmp(tab, r, j, c, &t);
if (tsgn < 0 || (tsgn == 0 &&
			    tab->row_var[j] < tab->row_var[r]))
	r = j;
}
isl_int_clear(t)isl_sioimath_clear((t));
return r;
687}

689/* Find a pivot (row and col) that will increase (sgn > 0) or decrease
* (sgn < 0) the value of row variable var.
* If not NULL, then skip_var is a row variable that should be ignored
* while looking for a pivot row.  It is usually equal to var.
*
* As the given row in the tableau is of the form
*
*	x_r = a_r0 + \sum_i a_ri x_i
*
* we need to find a column such that the sign of a_ri is equal to "sgn"
* (such that an increase in x_i will have the desired effect) or a
* column with a variable that may attain negative values.
* If a_ri is positive, then we need to move x_i in the same direction
* to obtain the desired effect.  Otherwise, x_i has to move in the
* opposite direction.
*/
705static void find_pivot(struct isl_tab *tab,
struct isl_tab_var *var, struct isl_tab_var *skip_var,
int sgn, int *row, int *col)
708{
int j, r, c;
isl_int *tr;

*row = *col = -1;

isl_assert(tab->mat->ctx, var->is_row, return)do { if (var->is_row) break; do { isl_handle_error(tab->
mat->ctx, isl_error_unknown, "Assertion \"" "var->is_row"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 714); return
; } while (0); } while (0);
tr = tab->mat->row[var->index] + 2 + tab->M;

c = -1;
for (j = tab->n_dead; j < tab->n_col; ++j) {
if (isl_int_is_zero(tr[j])(isl_sioimath_sgn(*(tr[j])) == 0))
	continue;
if (isl_int_sgn(tr[j])isl_sioimath_sgn(*(tr[j])) != sgn &&
    var_from_col(tab, j)->is_nonneg)
	continue;
if (c < 0 || tab->col_var[j] < tab->col_var[c])
	c = j;
}
if (c < 0)
return;

sgn *= isl_int_sgn(tr[c])isl_sioimath_sgn(*(tr[c]));
r = pivot_row(tab, skip_var, sgn, c);
*row = r < 0 ? var->index : r;
*col = c;
734}

736/* Return 1 if row "row" represents an obviously redundant inequality.
* This means
*	- it represents an inequality or a variable
*	- that is the sum of a non-negative sample value and a positive
*	  combination of zero or more non-negative constraints.
*/
742int isl_tab_row_is_redundant(struct isl_tab *tab, int row)
743{
int i;
unsigned off = 2 + tab->M;

if (tab->row_var[row] < 0 && !isl_tab_var_from_row(tab, row)->is_nonneg)
return 0;

if (isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0))
return 0;
if (tab->strict_redundant && isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0))
return 0;
if (tab->M && isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0))
return 0;

for (i = tab->n_dead; i < tab->n_col; ++i) {
if (isl_int_is_zero(tab->mat->row[row][off + i])(isl_sioimath_sgn(*(tab->mat->row[row][off + i])) == 0))
	continue;
if (tab->col_var[i] >= 0)
	return 0;
if (isl_int_is_neg(tab->mat->row[row][off + i])(isl_sioimath_sgn(*(tab->mat->row[row][off + i])) < 0
))
	return 0;
if (!var_from_col(tab, i)->is_nonneg)
	return 0;
}
return 1;
768}

770static void swap_rows(struct isl_tab *tab, int row1, int row2)
771{
int t;
enum isl_tab_row_sign s;

t = tab->row_var[row1];
tab->row_var[row1] = tab->row_var[row2];
tab->row_var[row2] = t;
isl_tab_var_from_row(tab, row1)->index = row1;
isl_tab_var_from_row(tab, row2)->index = row2;
tab->mat = isl_mat_swap_rows(tab->mat, row1, row2);

if (!tab->row_sign)
return;
s = tab->row_sign[row1];
tab->row_sign[row1] = tab->row_sign[row2];
tab->row_sign[row2] = s;
787}

789static isl_stat push_union(struct isl_tab *tab,
enum isl_tab_undo_type type, union isl_tab_undo_val u) WARN_UNUSED__attribute__((__warn_unused_result__));

792/* Push record "u" onto the undo stack of "tab", provided "tab"
* keeps track of undo information.
*
* If the record cannot be pushed, then mark the undo stack as invalid
* such that a later rollback attempt will not try to undo earlier
* records without having been able to undo the current record.
*/
799static isl_stat push_union(struct isl_tab *tab,
enum isl_tab_undo_type type, union isl_tab_undo_val u)
801{
struct isl_tab_undo *undo;

if (!tab)
return isl_stat_error;
if (!tab->need_undo)
return isl_stat_ok;

undo = isl_alloc_type(tab->mat->ctx, struct isl_tab_undo)((struct isl_tab_undo *)isl_malloc_or_die(tab->mat->ctx
, sizeof(struct isl_tab_undo)));
if (!undo)
goto error;
undo->type = type;
undo->u = u;
undo->next = tab->top;
tab->top = undo;

return isl_stat_ok;
818error:
free_undo(tab);
tab->top = NULL((void*)0);
return isl_stat_error;
822}

824isl_stat isl_tab_push_var(struct isl_tab *tab,
enum isl_tab_undo_type type, struct isl_tab_var *var)
826{
union isl_tab_undo_val u;
if (var->is_row)
u.var_index = tab->row_var[var->index];
else
u.var_index = tab->col_var[var->index];
return push_union(tab, type, u);
833}

835isl_stat isl_tab_push(struct isl_tab *tab, enum isl_tab_undo_type type)
836{
union isl_tab_undo_val u = { 0 };
return push_union(tab, type, u);
839}

841/* Push a record on the undo stack describing the current basic
* variables, so that the this state can be restored during rollback.
*/
844isl_stat isl_tab_push_basis(struct isl_tab *tab)
845{
int i;
union isl_tab_undo_val u;

u.col_var = isl_alloc_array(tab->mat->ctx, int, tab->n_col)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->n_col
)*sizeof(int)));
if (tab->n_col && !u.col_var)
return isl_stat_error;
for (i = 0; i < tab->n_col; ++i)
u.col_var[i] = tab->col_var[i];
return push_union(tab, isl_tab_undo_saved_basis, u);
855}

857isl_stat isl_tab_push_callback(struct isl_tab *tab,
struct isl_tab_callback *callback)
859{
union isl_tab_undo_val u;
u.callback = callback;
return push_union(tab, isl_tab_undo_callback, u);
863}

865struct isl_tab *isl_tab_init_samples(struct isl_tab *tab)
866{
if (!tab)
return NULL((void*)0);

tab->n_sample = 0;
tab->n_outside = 0;
tab->samples = isl_mat_alloc(tab->mat->ctx, 1, 1 + tab->n_var);
if (!tab->samples)
goto error;
tab->sample_index = isl_alloc_array(tab->mat->ctx, int, 1)((int *)isl_malloc_or_die(tab->mat->ctx, (1)*sizeof(int
)));
if (!tab->sample_index)
goto error;
return tab;
879error:
isl_tab_free(tab);
return NULL((void*)0);
882}

884int isl_tab_add_sample(struct isl_tab *tab, __isl_take isl_vec *sample)
885{
if (!tab || !sample)
goto error;

if (tab->n_sample + 1 > tab->samples->n_row) {
int *t = isl_realloc_array(tab->mat->ctx,((int *)isl_realloc_or_die(tab->mat->ctx, tab->sample_index
, (tab->n_sample + 1)*sizeof(int)))
	    tab->sample_index, int, tab->n_sample + 1)((int *)isl_realloc_or_die(tab->mat->ctx, tab->sample_index
, (tab->n_sample + 1)*sizeof(int)));
if (!t)
	goto error;
tab->sample_index = t;
}

tab->samples = isl_mat_extend(tab->samples,
		tab->n_sample + 1, tab->samples->n_col);
if (!tab->samples)
goto error;

isl_seq_cpy(tab->samples->row[tab->n_sample], sample->el, sample->size);
isl_vec_free(sample);
tab->sample_index[tab->n_sample] = tab->n_sample;
tab->n_sample++;

return 0;
908error:
isl_vec_free(sample);
return -1;
911}

913struct isl_tab *isl_tab_drop_sample(struct isl_tab *tab, int s)
914{
if (s != tab->n_outside) {
int t = tab->sample_index[tab->n_outside];
tab->sample_index[tab->n_outside] = tab->sample_index[s];
tab->sample_index[s] = t;
isl_mat_swap_rows(tab->samples, tab->n_outside, s);
}
tab->n_outside++;
if (isl_tab_push(tab, isl_tab_undo_drop_sample) < 0) {
isl_tab_free(tab);
return NULL((void*)0);
}

return tab;
928}

930/* Record the current number of samples so that we can remove newer
* samples during a rollback.
*/
933isl_stat isl_tab_save_samples(struct isl_tab *tab)
934{
union isl_tab_undo_val u;

if (!tab)
return isl_stat_error;

u.n = tab->n_sample;
return push_union(tab, isl_tab_undo_saved_samples, u);
942}

944/* Mark row with index "row" as being redundant.
* If we may need to undo the operation or if the row represents
* a variable of the original problem, the row is kept,
* but no longer considered when looking for a pivot row.
* Otherwise, the row is simply removed.
*
* The row may be interchanged with some other row.  If it
* is interchanged with a later row, return 1.  Otherwise return 0.
* If the rows are checked in order in the calling function,
* then a return value of 1 means that the row with the given
* row number may now contain a different row that hasn't been checked yet.
*/
956int isl_tab_mark_redundant(struct isl_tab *tab, int row)
957{
struct isl_tab_var *var = isl_tab_var_from_row(tab, row);
var->is_redundant = 1;
isl_assert(tab->mat->ctx, row >= tab->n_redundant, return -1)do { if (row >= tab->n_redundant) break; do { isl_handle_error
(tab->mat->ctx, isl_error_unknown, "Assertion \"" "row >= tab->n_redundant"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 960); return
 -1; } while (0); } while (0);
if (tab->preserve || tab->need_undo || tab->row_var[row] >= 0) {
if (tab->row_var[row] >= 0 && !var->is_nonneg) {
	var->is_nonneg = 1;
	if (isl_tab_push_var(tab, isl_tab_undo_nonneg, var) < 0)
		return -1;
}
if (row != tab->n_redundant)
	swap_rows(tab, row, tab->n_redundant);
tab->n_redundant++;
return isl_tab_push_var(tab, isl_tab_undo_redundant, var);
} else {
if (row != tab->n_row - 1)
	swap_rows(tab, row, tab->n_row - 1);
isl_tab_var_from_row(tab, tab->n_row - 1)->index = -1;
tab->n_row--;
return 1;
}
978}

980/* Mark "tab" as a rational tableau.
* If it wasn't marked as a rational tableau already and if we may
* need to undo changes, then arrange for the marking to be undone
* during the undo.
*/
985int isl_tab_mark_rational(struct isl_tab *tab)
986{
if (!tab)
return -1;
if (!tab->rational && tab->need_undo)
if (isl_tab_push(tab, isl_tab_undo_rational) < 0)
	return -1;
tab->rational = 1;
return 0;
994}

996isl_stat isl_tab_mark_empty(struct isl_tab *tab)
997{
if (!tab)
return isl_stat_error;
if (!tab->empty && tab->need_undo)
if (isl_tab_push(tab, isl_tab_undo_empty) < 0)
	return isl_stat_error;
tab->empty = 1;
return isl_stat_ok;
1005}

1007int isl_tab_freeze_constraint(struct isl_tab *tab, int con)
1008{
struct isl_tab_var *var;

if (!tab)
return -1;

var = &tab->con[con];
if (var->frozen)
return 0;
if (var->index < 0)
return 0;
var->frozen = 1;

if (tab->need_undo)
return isl_tab_push_var(tab, isl_tab_undo_freeze, var);

return 0;
1025}

1027/* Update the rows signs after a pivot of "row" and "col", with "row_sgn"
* the original sign of the pivot element.
* We only keep track of row signs during PILP solving and in this case
* we only pivot a row with negative sign (meaning the value is always
* non-positive) using a positive pivot element.
*
* For each row j, the new value of the parametric constant is equal to
*
*	a_j0 - a_jc a_r0/a_rc
*
* where a_j0 is the original parametric constant, a_rc is the pivot element,
* a_r0 is the parametric constant of the pivot row and a_jc is the
* pivot column entry of the row j.
* Since a_r0 is non-positive and a_rc is positive, the sign of row j
* remains the same if a_jc has the same sign as the row j or if
* a_jc is zero.  In all other cases, we reset the sign to "unknown".
*/
1044static void update_row_sign(struct isl_tab *tab, int row, int col, int row_sgn)
1045{
int i;
struct isl_mat *mat = tab->mat;
unsigned off = 2 + tab->M;

if (!tab->row_sign)
return;

if (tab->row_sign[row] == 0)
return;
isl_assert(mat->ctx, row_sgn > 0, return)do { if (row_sgn > 0) break; do { isl_handle_error(mat->
ctx, isl_error_unknown, "Assertion \"" "row_sgn > 0" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 1055); return; } while (
0); } while (0);
isl_assert(mat->ctx, tab->row_sign[row] == isl_tab_row_neg, return)do { if (tab->row_sign[row] == isl_tab_row_neg) break; do {
 isl_handle_error(mat->ctx, isl_error_unknown, "Assertion \""
 "tab->row_sign[row] == isl_tab_row_neg" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 1056); return; } while (0); } while (0);
tab->row_sign[row] = isl_tab_row_pos;
for (i = 0; i < tab->n_row; ++i) {
int s;
if (i == row)
	continue;
s = isl_int_sgn(mat->row[i][off + col])isl_sioimath_sgn(*(mat->row[i][off + col]));
if (!s)
	continue;
if (!tab->row_sign[i])
	continue;
if (s < 0 && tab->row_sign[i] == isl_tab_row_neg)
	continue;
if (s > 0 && tab->row_sign[i] == isl_tab_row_pos)
	continue;
tab->row_sign[i] = isl_tab_row_unknown;
}
1073}

1075/* Given a row number "row" and a column number "col", pivot the tableau
* such that the associated variables are interchanged.
* The given row in the tableau expresses
*
*	x_r = a_r0 + \sum_i a_ri x_i
*
* or
*
*	x_c = 1/a_rc x_r - a_r0/a_rc + sum_{i \ne r} -a_ri/a_rc
*
* Substituting this equality into the other rows
*
*	x_j = a_j0 + \sum_i a_ji x_i
*
* with a_jc \ne 0, we obtain
*
*	x_j = a_jc/a_rc x_r + a_j0 - a_jc a_r0/a_rc + sum a_ji - a_jc a_ri/a_rc 
*
* The tableau
*
*	n_rc/d_r		n_ri/d_r
*	n_jc/d_j		n_ji/d_j
*
* where i is any other column and j is any other row,
* is therefore transformed into
*
* s(n_rc)d_r/|n_rc|		-s(n_rc)n_ri/|n_rc|
* s(n_rc)d_r n_jc/(|n_rc| d_j)	(n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j)
*
* The transformation is performed along the following steps
*
*	d_r/n_rc		n_ri/n_rc
*	n_jc/d_j		n_ji/d_j
*
*	s(n_rc)d_r/|n_rc|	-s(n_rc)n_ri/|n_rc|
*	n_jc/d_j		n_ji/d_j
*
*	s(n_rc)d_r/|n_rc|	-s(n_rc)n_ri/|n_rc|
*	n_jc/(|n_rc| d_j)	n_ji/(|n_rc| d_j)
*
*	s(n_rc)d_r/|n_rc|	-s(n_rc)n_ri/|n_rc|
*	n_jc/(|n_rc| d_j)	(n_ji |n_rc|)/(|n_rc| d_j)
*
*	s(n_rc)d_r/|n_rc|	-s(n_rc)n_ri/|n_rc|
*	n_jc/(|n_rc| d_j)	(n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j)
*
* s(n_rc)d_r/|n_rc|		-s(n_rc)n_ri/|n_rc|
* s(n_rc)d_r n_jc/(|n_rc| d_j)	(n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j)
*
*/
1125int isl_tab_pivot(struct isl_tab *tab, int row, int col)
1126{
int i, j;
int sgn;
int t;
isl_ctx *ctx;
struct isl_mat *mat = tab->mat;
struct isl_tab_var *var;
unsigned off = 2 + tab->M;

ctx = isl_tab_get_ctx(tab);
if (isl_ctx_next_operation(ctx) < 0)
return -1;

isl_int_swap(mat->row[row][0], mat->row[row][off + col])isl_sioimath_swap((mat->row[row][0]), (mat->row[row][off
 + col]));
sgn = isl_int_sgn(mat->row[row][0])isl_sioimath_sgn(*(mat->row[row][0]));
if (sgn < 0) {
isl_int_neg(mat->row[row][0], mat->row[row][0])isl_sioimath_neg((mat->row[row][0]), *(mat->row[row][0]
));
isl_int_neg(mat->row[row][off + col], mat->row[row][off + col])isl_sioimath_neg((mat->row[row][off + col]), *(mat->row
[row][off + col]));
} else
for (j = 0; j < off - 1 + tab->n_col; ++j) {
	if (j == off - 1 + col)
		continue;
	isl_int_neg(mat->row[row][1 + j], mat->row[row][1 + j])isl_sioimath_neg((mat->row[row][1 + j]), *(mat->row[row
][1 + j]));
}
if (!isl_int_is_one(mat->row[row][0])(isl_sioimath_cmp_si(*(mat->row[row][0]), 1) == 0))
isl_seq_normalize(mat->ctx, mat->row[row], off + tab->n_col);
for (i = 0; i < tab->n_row; ++i) {
if (i == row)
	continue;
if (isl_int_is_zero(mat->row[i][off + col])(isl_sioimath_sgn(*(mat->row[i][off + col])) == 0))
	continue;
isl_int_mul(mat->row[i][0], mat->row[i][0], mat->row[row][0])isl_sioimath_mul((mat->row[i][0]), *(mat->row[i][0]), *
(mat->row[row][0]));
for (j = 0; j < off - 1 + tab->n_col; ++j) {
	if (j == off - 1 + col)
		continue;
	isl_int_mul(mat->row[i][1 + j],isl_sioimath_mul((mat->row[i][1 + j]), *(mat->row[i][1 +
 j]), *(mat->row[row][0]))
		    mat->row[i][1 + j], mat->row[row][0])isl_sioimath_mul((mat->row[i][1 + j]), *(mat->row[i][1 +
 j]), *(mat->row[row][0]));
	isl_int_addmul(mat->row[i][1 + j],isl_sioimath_addmul((mat->row[i][1 + j]), *(mat->row[i]
[off + col]), *(mat->row[row][1 + j]))
		    mat->row[i][off + col], mat->row[row][1 + j])isl_sioimath_addmul((mat->row[i][1 + j]), *(mat->row[i]
[off + col]), *(mat->row[row][1 + j]));
}
isl_int_mul(mat->row[i][off + col],isl_sioimath_mul((mat->row[i][off + col]), *(mat->row[i
][off + col]), *(mat->row[row][off + col]))
	    mat->row[i][off + col], mat->row[row][off + col])isl_sioimath_mul((mat->row[i][off + col]), *(mat->row[i
][off + col]), *(mat->row[row][off + col]));
if (!isl_int_is_one(mat->row[i][0])(isl_sioimath_cmp_si(*(mat->row[i][0]), 1) == 0))
	isl_seq_normalize(mat->ctx, mat->row[i], off + tab->n_col);
}
t = tab->row_var[row];
tab->row_var[row] = tab->col_var[col];
tab->col_var[col] = t;
var = isl_tab_var_from_row(tab, row);
var->is_row = 1;
var->index = row;
var = var_from_col(tab, col);
var->is_row = 0;
var->index = col;
update_row_sign(tab, row, col, sgn);
if (tab->in_undo)
return 0;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
if (isl_int_is_zero(mat->row[i][off + col])(isl_sioimath_sgn(*(mat->row[i][off + col])) == 0))
	continue;
if (!isl_tab_var_from_row(tab, i)->frozen &&
    isl_tab_row_is_redundant(tab, i)) {
	int redo = isl_tab_mark_redundant(tab, i);
	if (redo < 0)
		return -1;
	if (redo)
		--i;
}
}
return 0;
1196}

1198/* If "var" represents a column variable, then pivot is up (sgn > 0)
* or down (sgn < 0) to a row.  The variable is assumed not to be
* unbounded in the specified direction.
* If sgn = 0, then the variable is unbounded in both directions,
* and we pivot with any row we can find.
*/
1204static int to_row(struct isl_tab *tab, struct isl_tab_var *var, int sign) WARN_UNUSED__attribute__((__warn_unused_result__));
1205static int to_row(struct isl_tab *tab, struct isl_tab_var *var, int sign)
1206{
int r;
unsigned off = 2 + tab->M;

if (var->is_row)
return 0;

if (sign == 0) {
for (r = tab->n_redundant; r < tab->n_row; ++r)
	if (!isl_int_is_zero(tab->mat->row[r][off+var->index])(isl_sioimath_sgn(*(tab->mat->row[r][off+var->index]
)) == 0))
		break;
isl_assert(tab->mat->ctx, r < tab->n_row, return -1)do { if (r < tab->n_row) break; do { isl_handle_error(tab
->mat->ctx, isl_error_unknown, "Assertion \"" "r < tab->n_row"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1217); return
 -1; } while (0); } while (0);
} else {
r = pivot_row(tab, NULL((void*)0), sign, var->index);
isl_assert(tab->mat->ctx, r >= 0, return -1)do { if (r >= 0) break; do { isl_handle_error(tab->mat->
ctx, isl_error_unknown, "Assertion \"" "r >= 0" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 1220); return -1; } while
 (0); } while (0);
}

return isl_tab_pivot(tab, r, var->index);
1224}

1226/* Check whether all variables that are marked as non-negative
* also have a non-negative sample value.  This function is not
* called from the current code but is useful during debugging.
*/
1230static void check_table(struct isl_tab *tab) __attribute__ ((unused));
1231static void check_table(struct isl_tab *tab)
1232{
int i;

if (tab->empty)
return;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
struct isl_tab_var *var;
var = isl_tab_var_from_row(tab, i);
if (!var->is_nonneg)
	continue;
if (tab->M) {
	isl_assert(tab->mat->ctx,do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][2])) <
 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1244); abort
(); } while (0); } while (0)
		!isl_int_is_neg(tab->mat->row[i][2]), abort())do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][2])) <
 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1244); abort
(); } while (0); } while (0);
	if (isl_int_is_pos(tab->mat->row[i][2])(isl_sioimath_sgn(*(tab->mat->row[i][2])) > 0))
		continue;
}
isl_assert(tab->mat->ctx, !isl_int_is_neg(tab->mat->row[i][1]),do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][1])) <
 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1249); abort
(); } while (0); } while (0)
		abort())do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][1])) <
 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1249); abort
(); } while (0); } while (0);
}
1251}

1253/* Return the sign of the maximal value of "var".
* If the sign is not negative, then on return from this function,
* the sample value will also be non-negative.
*
* If "var" is manifestly unbounded wrt positive values, we are done.
* Otherwise, we pivot the variable up to a row if needed.
* Then we continue pivoting up until either
*	- no more up pivots can be performed
*	- the sample value is positive
*	- the variable is pivoted into a manifestly unbounded column
*/
1264static int sign_of_max(struct isl_tab *tab, struct isl_tab_var *var)
1265{
int row, col;

if (max_is_manifestly_unbounded(tab, var))
return 1;
if (to_row(tab, var, 1) < 0)
return -2;
while (!isl_int_is_pos(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) >
 0)) {
find_pivot(tab, var, var, 1, &row, &col);
if (row == -1)
	return isl_int_sgn(tab->mat->row[var->index][1])isl_sioimath_sgn(*(tab->mat->row[var->index][1]));
if (isl_tab_pivot(tab, row, col) < 0)
	return -2;
if (!var->is_row) /* manifestly unbounded */
	return 1;
}
return 1;
1282}

1284int isl_tab_sign_of_max(struct isl_tab *tab, int con)
1285{
struct isl_tab_var *var;

if (!tab)
return -2;

var = &tab->con[con];
isl_assert(tab->mat->ctx, !var->is_redundant, return -2)do { if (!var->is_redundant) break; do { isl_handle_error(
tab->mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_redundant"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1292); return
 -2; } while (0); } while (0);
isl_assert(tab->mat->ctx, !var->is_zero, return -2)do { if (!var->is_zero) break; do { isl_handle_error(tab->
mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_zero"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1293); return
 -2; } while (0); } while (0);

return sign_of_max(tab, var);
1296}

1298static int row_is_neg(struct isl_tab *tab, int row)
1299{
if (!tab->M)
return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0);
if (isl_int_is_pos(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) > 0))
return 0;
if (isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0))
return 1;
return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0);
1307}

1309static int row_sgn(struct isl_tab *tab, int row)
1310{
if (!tab->M)
return isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1]));
if (!isl_int_is_zero(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) == 0))
return isl_int_sgn(tab->mat->row[row][2])isl_sioimath_sgn(*(tab->mat->row[row][2]));
else
return isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1]));
1317}

1319/* Perform pivots until the row variable "var" has a non-negative
* sample value or until no more upward pivots can be performed.
* Return the sign of the sample value after the pivots have been
* performed.
*/
1324static int restore_row(struct isl_tab *tab, struct isl_tab_var *var)
1325{
int row, col;

while (row_is_neg(tab, var->index)) {
find_pivot(tab, var, var, 1, &row, &col);
if (row == -1)
	break;
if (isl_tab_pivot(tab, row, col) < 0)
	return -2;
if (!var->is_row) /* manifestly unbounded */
	return 1;
}
return row_sgn(tab, var->index);
1338}

1340/* Perform pivots until we are sure that the row variable "var"
* can attain non-negative values.  After return from this
* function, "var" is still a row variable, but its sample
* value may not be non-negative, even if the function returns 1.
*/
1345static int at_least_zero(struct isl_tab *tab, struct isl_tab_var *var)
1346{
int row, col;

while (isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) <
 0)) {
find_pivot(tab, var, var, 1, &row, &col);
if (row == -1)
	break;
if (row == var->index) /* manifestly unbounded */
	return 1;
if (isl_tab_pivot(tab, row, col) < 0)
	return -1;
}
return !isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) <
 0);
1359}

1361/* Return a negative value if "var" can attain negative values.
* Return a non-negative value otherwise.
*
* If "var" is manifestly unbounded wrt negative values, we are done.
* Otherwise, if var is in a column, we can pivot it down to a row.
* Then we continue pivoting down until either
*	- the pivot would result in a manifestly unbounded column
*	  => we don't perform the pivot, but simply return -1
*	- no more down pivots can be performed
*	- the sample value is negative
* If the sample value becomes negative and the variable is supposed
* to be nonnegative, then we undo the last pivot.
* However, if the last pivot has made the pivoting variable
* obviously redundant, then it may have moved to another row.
* In that case we look for upward pivots until we reach a non-negative
* value again.
*/
1378static int sign_of_min(struct isl_tab *tab, struct isl_tab_var *var)
1379{
int row, col;
struct isl_tab_var *pivot_var = NULL((void*)0);

if (min_is_manifestly_unbounded(tab, var))
return -1;
if (!var->is_row) {
col = var->index;
row = pivot_row(tab, NULL((void*)0), -1, col);
pivot_var = var_from_col(tab, col);
if (isl_tab_pivot(tab, row, col) < 0)
	return -2;
if (var->is_redundant)
	return 0;
if (isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) <
 0)) {
	if (var->is_nonneg) {
		if (!pivot_var->is_redundant &&
		    pivot_var->index == row) {
			if (isl_tab_pivot(tab, row, col) < 0)
				return -2;
		} else
			if (restore_row(tab, var) < -1)
				return -2;
	}
	return -1;
}
}
if (var->is_redundant)
return 0;
while (!isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) <
 0)) {
find_pivot(tab, var, var, -1, &row, &col);
if (row == var->index)
	return -1;
if (row == -1)
	return isl_int_sgn(tab->mat->row[var->index][1])isl_sioimath_sgn(*(tab->mat->row[var->index][1]));
pivot_var = var_from_col(tab, col);
if (isl_tab_pivot(tab, row, col) < 0)
	return -2;
if (var->is_redundant)
	return 0;
}
if (pivot_var && var->is_nonneg) {
/* pivot back to non-negative value */
if (!pivot_var->is_redundant && pivot_var->index == row) {
	if (isl_tab_pivot(tab, row, col) < 0)
		return -2;
} else
	if (restore_row(tab, var) < -1)
		return -2;
}
return -1;
1430}

1432static int row_at_most_neg_one(struct isl_tab *tab, int row)
1433{
if (tab->M) {
if (isl_int_is_pos(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) > 0))
	return 0;
if (isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0))
	return 1;
}
return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0) &&
      isl_int_abs_ge(tab->mat->row[row][1],(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab->
mat->row[row][0])) >= 0)
	      tab->mat->row[row][0])(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab->
mat->row[row][0])) >= 0);
1443}

1445/* Return 1 if "var" can attain values <= -1.
* Return 0 otherwise.
*
* If the variable "var" is supposed to be non-negative (is_nonneg is set),
* then the sample value of "var" is assumed to be non-negative when the
* the function is called.  If 1 is returned then the constraint
* is not redundant and the sample value is made non-negative again before
* the function returns.
*/
1454int isl_tab_min_at_most_neg_one(struct isl_tab *tab, struct isl_tab_var *var)
1455{
int row, col;
struct isl_tab_var *pivot_var;

if (min_is_manifestly_unbounded(tab, var))
return 1;
if (!var->is_row) {
col = var->index;
row = pivot_row(tab, NULL((void*)0), -1, col);
pivot_var = var_from_col(tab, col);
if (isl_tab_pivot(tab, row, col) < 0)
	return -1;
if (var->is_redundant)
	return 0;
if (row_at_most_neg_one(tab, var->index)) {
	if (var->is_nonneg) {
		if (!pivot_var->is_redundant &&
		    pivot_var->index == row) {
			if (isl_tab_pivot(tab, row, col) < 0)
				return -1;
		} else
			if (restore_row(tab, var) < -1)
				return -1;
	}
	return 1;
}
}
if (var->is_redundant)
return 0;
do {
find_pivot(tab, var, var, -1, &row, &col);
if (row == var->index) {
	if (var->is_nonneg && restore_row(tab, var) < -1)
		return -1;
	return 1;
}
if (row == -1)
	return 0;
pivot_var = var_from_col(tab, col);
if (isl_tab_pivot(tab, row, col) < 0)
	return -1;
if (var->is_redundant)
	return 0;
} while (!row_at_most_neg_one(tab, var->index));
if (var->is_nonneg) {
/* pivot back to non-negative value */
if (!pivot_var->is_redundant && pivot_var->index == row)
	if (isl_tab_pivot(tab, row, col) < 0)
		return -1;
if (restore_row(tab, var) < -1)
	return -1;
}
return 1;
1508}

1510/* Return 1 if "var" can attain values >= 1.
* Return 0 otherwise.
*/
1513static int at_least_one(struct isl_tab *tab, struct isl_tab_var *var)
1514{
int row, col;
isl_int *r;

if (max_is_manifestly_unbounded(tab, var))
return 1;
if (to_row(tab, var, 1) < 0)
return -1;
r = tab->mat->row[var->index];
while (isl_int_lt(r[1], r[0])(isl_sioimath_cmp(*(r[1]), *(r[0])) < 0)) {
find_pivot(tab, var, var, 1, &row, &col);
if (row == -1)
	return isl_int_ge(r[1], r[0])(isl_sioimath_cmp(*(r[1]), *(r[0])) >= 0);
if (row == var->index) /* manifestly unbounded */
	return 1;
if (isl_tab_pivot(tab, row, col) < 0)
	return -1;
}
return 1;
1533}

1535static void swap_cols(struct isl_tab *tab, int col1, int col2)
1536{
int t;
unsigned off = 2 + tab->M;
t = tab->col_var[col1];
tab->col_var[col1] = tab->col_var[col2];
tab->col_var[col2] = t;
var_from_col(tab, col1)->index = col1;
var_from_col(tab, col2)->index = col2;
tab->mat = isl_mat_swap_cols(tab->mat, off + col1, off + col2);
1545}

1547/* Mark column with index "col" as representing a zero variable.
* If we may need to undo the operation the column is kept,
* but no longer considered.
* Otherwise, the column is simply removed.
*
* The column may be interchanged with some other column.  If it
* is interchanged with a later column, return 1.  Otherwise return 0.
* If the columns are checked in order in the calling function,
* then a return value of 1 means that the column with the given
* column number may now contain a different column that
* hasn't been checked yet.
*/
1559int isl_tab_kill_col(struct isl_tab *tab, int col)
1560{
var_from_col(tab, col)->is_zero = 1;
if (tab->need_undo) {
if (isl_tab_push_var(tab, isl_tab_undo_zero,
			    var_from_col(tab, col)) < 0)
	return -1;
if (col != tab->n_dead)
	swap_cols(tab, col, tab->n_dead);
tab->n_dead++;
return 0;
} else {
if (col != tab->n_col - 1)
	swap_cols(tab, col, tab->n_col - 1);
var_from_col(tab, tab->n_col - 1)->index = -1;
tab->n_col--;
return 1;
}
1577}

1579static int row_is_manifestly_non_integral(struct isl_tab *tab, int row)
1580{
unsigned off = 2 + tab->M;

if (tab->M && !isl_int_eq(tab->mat->row[row][2],(isl_sioimath_cmp(*(tab->mat->row[row][2]), *(tab->mat
->row[row][0])) == 0)
		  tab->mat->row[row][0])(isl_sioimath_cmp(*(tab->mat->row[row][2]), *(tab->mat
->row[row][0])) == 0))
return 0;
if (isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
		    tab->n_col - tab->n_dead) != -1)
return 0;

return !isl_int_is_divisible_by(tab->mat->row[row][1],isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), *
(tab->mat->row[row][0]))
			tab->mat->row[row][0])isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), *
(tab->mat->row[row][0]));
1592}

1594/* For integer tableaus, check if any of the coordinates are stuck
* at a non-integral value.
*/
1597static int tab_is_manifestly_empty(struct isl_tab *tab)
1598{
int i;

if (tab->empty)
return 1;
if (tab->rational)
return 0;

for (i = 0; i < tab->n_var; ++i) {
if (!tab->var[i].is_row)
	continue;
if (row_is_manifestly_non_integral(tab, tab->var[i].index))
	return 1;
}

return 0;
1614}

1616/* Row variable "var" is non-negative and cannot attain any values
* larger than zero.  This means that the coefficients of the unrestricted
* column variables are zero and that the coefficients of the non-negative
* column variables are zero or negative.
* Each of the non-negative variables with a negative coefficient can
* then also be written as the negative sum of non-negative variables
* and must therefore also be zero.
*
* If "temp_var" is set, then "var" is a temporary variable that
* will be removed after this function returns and for which
* no information is recorded on the undo stack.
* Do not add any undo records involving this variable in this case
* since the variable will have been removed before any future undo
* operations.  Also avoid marking the variable as redundant,
* since that either adds an undo record or needlessly removes the row
* (the caller will take care of removing the row).
*/
1633static isl_stat close_row(struct isl_tab *tab, struct isl_tab_var *var,
int temp_var) WARN_UNUSED__attribute__((__warn_unused_result__));
1635static isl_stat close_row(struct isl_tab *tab, struct isl_tab_var *var,
int temp_var)
1637{
int j;
struct isl_mat *mat = tab->mat;
unsigned off = 2 + tab->M;

if (!var->is_nonneg)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "expecting non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 1645); return isl_stat_error; } while (0)
	"expecting non-negative variable",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "expecting non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 1645); return isl_stat_error; } while (0)
	return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "expecting non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 1645); return isl_stat_error; } while (0);
var->is_zero = 1;
if (!temp_var && tab->need_undo)
if (isl_tab_push_var(tab, isl_tab_undo_zero, var) < 0)
	return isl_stat_error;
for (j = tab->n_dead; j < tab->n_col; ++j) {
int recheck;
if (isl_int_is_zero(mat->row[var->index][off + j])(isl_sioimath_sgn(*(mat->row[var->index][off + j])) == 0
))
	continue;
if (isl_int_is_pos(mat->row[var->index][off + j])(isl_sioimath_sgn(*(mat->row[var->index][off + j])) >
 0))
	isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row cannot have positive coefficients", "polly/lib/External/isl/isl_tab.c"
, 1657); return isl_stat_error; } while (0)
		"row cannot have positive coefficients",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row cannot have positive coefficients", "polly/lib/External/isl/isl_tab.c"
, 1657); return isl_stat_error; } while (0)
		return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row cannot have positive coefficients", "polly/lib/External/isl/isl_tab.c"
, 1657); return isl_stat_error; } while (0);
recheck = isl_tab_kill_col(tab, j);
if (recheck < 0)
	return isl_stat_error;
if (recheck)
	--j;
}
if (!temp_var && isl_tab_mark_redundant(tab, var->index) < 0)
return isl_stat_error;
if (tab_is_manifestly_empty(tab) && isl_tab_mark_empty(tab) < 0)
return isl_stat_error;
return isl_stat_ok;
1669}

1671/* Add a constraint to the tableau and allocate a row for it.
* Return the index into the constraint array "con".
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
1677int isl_tab_allocate_con(struct isl_tab *tab)
1678{
int r;

isl_assert(tab->mat->ctx, tab->n_row < tab->mat->n_row, return -1)do { if (tab->n_row < tab->mat->n_row) break; do {
 isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \""
 "tab->n_row < tab->mat->n_row" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 1681); return -1; } while (0); } while (0);
isl_assert(tab->mat->ctx, tab->n_con < tab->max_con, return -1)do { if (tab->n_con < tab->max_con) break; do { isl_handle_error
(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_con < tab->max_con"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1682); return
 -1; } while (0); } while (0);

r = tab->n_con;
tab->con[r].index = tab->n_row;
tab->con[r].is_row = 1;
tab->con[r].is_nonneg = 0;
tab->con[r].is_zero = 0;
tab->con[r].is_redundant = 0;
tab->con[r].frozen = 0;
tab->con[r].negated = 0;
tab->row_var[tab->n_row] = ~r;

tab->n_row++;
tab->n_con++;
if (isl_tab_push_var(tab, isl_tab_undo_allocate, &tab->con[r]) < 0)
return -1;

return r;
1700}

1702/* Move the entries in tab->var up one position, starting at "first",
* creating room for an extra entry at position "first".
* Since some of the entries of tab->row_var and tab->col_var contain
* indices into this array, they have to be updated accordingly.
*/
1707static int var_insert_entry(struct isl_tab *tab, int first)
1708{
int i;

if (tab->n_var >= tab->max_var)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "not enough room for new variable", "polly/lib/External/isl/isl_tab.c"
, 1713); return -1; } while (0)
	"not enough room for new variable", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "not enough room for new variable", "polly/lib/External/isl/isl_tab.c"
, 1713); return -1; } while (0);
if (first > tab->n_var)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid initial position", "polly/lib/External/isl/isl_tab.c"
, 1716); return -1; } while (0)
	"invalid initial position", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid initial position", "polly/lib/External/isl/isl_tab.c"
, 1716); return -1; } while (0);

for (i = tab->n_var - 1; i >= first; --i) {
tab->var[i + 1] = tab->var[i];
if (tab->var[i + 1].is_row)
	tab->row_var[tab->var[i + 1].index]++;
else
	tab->col_var[tab->var[i + 1].index]++;
}

tab->n_var++;

return 0;
1729}

1731/* Drop the entry at position "first" in tab->var, moving all
* subsequent entries down.
* Since some of the entries of tab->row_var and tab->col_var contain
* indices into this array, they have to be updated accordingly.
*/
1736static int var_drop_entry(struct isl_tab *tab, int first)
1737{
int i;

if (first >= tab->n_var)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid initial position", "polly/lib/External/isl/isl_tab.c"
, 1742); return -1; } while (0)
	"invalid initial position", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid initial position", "polly/lib/External/isl/isl_tab.c"
, 1742); return -1; } while (0);

tab->n_var--;

for (i = first; i < tab->n_var; ++i) {
tab->var[i] = tab->var[i + 1];
if (tab->var[i + 1].is_row)
	tab->row_var[tab->var[i].index]--;
else
	tab->col_var[tab->var[i].index]--;
}

return 0;
1755}

1757/* Add a variable to the tableau at position "r" and allocate a column for it.
* Return the index into the variable array "var", i.e., "r",
* or -1 on error.
*/
1761int isl_tab_insert_var(struct isl_tab *tab, int r)
1762{
int i;
unsigned off = 2 + tab->M;

isl_assert(tab->mat->ctx, tab->n_col < tab->mat->n_col, return -1)do { if (tab->n_col < tab->mat->n_col) break; do {
 isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \""
 "tab->n_col < tab->mat->n_col" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 1766); return -1; } while (0); } while (0);

if (var_insert_entry(tab, r) < 0)
return -1;

tab->var[r].index = tab->n_col;
tab->var[r].is_row = 0;
tab->var[r].is_nonneg = 0;
tab->var[r].is_zero = 0;
tab->var[r].is_redundant = 0;
tab->var[r].frozen = 0;
tab->var[r].negated = 0;
tab->col_var[tab->n_col] = r;

for (i = 0; i < tab->n_row; ++i)
isl_int_set_si(tab->mat->row[i][off + tab->n_col], 0)isl_sioimath_set_si((tab->mat->row[i][off + tab->n_col
]), 0);

tab->n_col++;
if (isl_tab_push_var(tab, isl_tab_undo_allocate, &tab->var[r]) < 0)
return -1;

return r;
1788}

1790/* Add a row to the tableau.  The row is given as an affine combination
* of the original variables and needs to be expressed in terms of the
* column variables.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*
* We add each term in turn.
* If r = n/d_r is the current sum and we need to add k x, then
* 	if x is a column variable, we increase the numerator of
*		this column by k d_r
*	if x = f/d_x is a row variable, then the new representation of r is
*
*		 n    k f   d_x/g n + d_r/g k f   m/d_r n + m/d_g k f
*		--- + --- = ------------------- = -------------------
*		d_r   d_r        d_r d_x/g                m
*
*	with g the gcd of d_r and d_x and m the lcm of d_r and d_x.
*
* If tab->M is set, then, internally, each variable x is represented
* as x' - M.  We then also need no subtract k d_r from the coefficient of M.
*/
1812int isl_tab_add_row(struct isl_tab *tab, isl_int *line)
1813{
int i;
int r;
isl_int *row;
isl_int a, b;
unsigned off = 2 + tab->M;

r = isl_tab_allocate_con(tab);
if (r < 0)
return -1;

isl_int_init(a)isl_sioimath_init((a));
isl_int_init(b)isl_sioimath_init((b));
row = tab->mat->row[tab->con[r].index];
isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1);
isl_int_set(row[1], line[0])isl_sioimath_set((row[1]), *(line[0]));
isl_seq_clr(row + 2, tab->M + tab->n_col);
for (i = 0; i < tab->n_var; ++i) {
if (tab->var[i].is_zero)
	continue;
if (tab->var[i].is_row) {
	isl_int_lcm(a,isl_sioimath_lcm((a), *(row[0]), *(tab->mat->row[tab->
var[i].index][0]))
		row[0], tab->mat->row[tab->var[i].index][0])isl_sioimath_lcm((a), *(row[0]), *(tab->mat->row[tab->
var[i].index][0]));
	isl_int_swap(a, row[0])isl_sioimath_swap((a), (row[0]));
	isl_int_divexact(a, row[0], a)isl_sioimath_tdiv_q((a), *(row[0]), *(a));
	isl_int_divexact(b,isl_sioimath_tdiv_q((b), *(row[0]), *(tab->mat->row[tab
->var[i].index][0]))
		row[0], tab->mat->row[tab->var[i].index][0])isl_sioimath_tdiv_q((b), *(row[0]), *(tab->mat->row[tab
->var[i].index][0]));
	isl_int_mul(b, b, line[1 + i])isl_sioimath_mul((b), *(b), *(line[1 + i]));
	isl_seq_combine(row + 1, a, row + 1,
	    b, tab->mat->row[tab->var[i].index] + 1,
	    1 + tab->M + tab->n_col);
} else
	isl_int_addmul(row[off + tab->var[i].index],isl_sioimath_addmul((row[off + tab->var[i].index]), *(line
[1 + i]), *(row[0]))
					line[1 + i], row[0])isl_sioimath_addmul((row[off + tab->var[i].index]), *(line
[1 + i]), *(row[0]));
if (tab->M && i >= tab->n_param && i < tab->n_var - tab->n_div)
	isl_int_submul(row[2], line[1 + i], row[0])isl_sioimath_submul((row[2]), *(line[1 + i]), *(row[0]));
}
isl_seq_normalize(tab->mat->ctx, row, off + tab->n_col);
isl_int_clear(a)isl_sioimath_clear((a));
isl_int_clear(b)isl_sioimath_clear((b));

if (tab->row_sign)
tab->row_sign[tab->con[r].index] = isl_tab_row_unknown;

return r;
1858}

1860static isl_stat drop_row(struct isl_tab *tab, int row)
1861{
isl_assert(tab->mat->ctx, ~tab->row_var[row] == tab->n_con - 1,do { if (~tab->row_var[row] == tab->n_con - 1) break; do
 { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \""
 "~tab->row_var[row] == tab->n_con - 1" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 1863); return isl_stat_error; } while (0); } while (0)
return isl_stat_error)do { if (~tab->row_var[row] == tab->n_con - 1) break; do
 { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \""
 "~tab->row_var[row] == tab->n_con - 1" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 1863); return isl_stat_error; } while (0); } while (0);
if (row != tab->n_row - 1)
swap_rows(tab, row, tab->n_row - 1);
tab->n_row--;
tab->n_con--;
return isl_stat_ok;
1869}

1871/* Drop the variable in column "col" along with the column.
* The column is removed first because it may need to be moved
* into the last position and this process requires
* the contents of the col_var array in a state
* before the removal of the variable.
*/
1877static isl_stat drop_col(struct isl_tab *tab, int col)
1878{
int var;

var = tab->col_var[col];
if (col != tab->n_col - 1)
swap_cols(tab, col, tab->n_col - 1);
tab->n_col--;
if (var_drop_entry(tab, var) < 0)
return isl_stat_error;
return isl_stat_ok;
1888}

1890/* Add inequality "ineq" and check if it conflicts with the
* previously added constraints or if it is obviously redundant.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
1896isl_stat isl_tab_add_ineq(struct isl_tab *tab, isl_int *ineq)
1897{
int r;
int sgn;
isl_int cst;

if (!tab13.1
'tab' is non-null
1
'tab' is non-null
)
14
←
Taking false branch→
return isl_stat_error;
if (tab->bmap) {
15
←
Assuming field 'bmap' is null→
16
←
Taking false branch→
struct isl_basic_map *bmap = tab->bmap;

isl_assert(tab->mat->ctx, tab->n_eq == bmap->n_eq,do { if (tab->n_eq == bmap->n_eq) break; do { isl_handle_error
(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_eq == bmap->n_eq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1908); return
 isl_stat_error; } while (0); } while (0)
	return isl_stat_error)do { if (tab->n_eq == bmap->n_eq) break; do { isl_handle_error
(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_eq == bmap->n_eq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1908); return
 isl_stat_error; } while (0); } while (0);
isl_assert(tab->mat->ctx,do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break
; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1911); return
 isl_stat_error; } while (0); } while (0)
	    tab->n_con == bmap->n_eq + bmap->n_ineq,do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break
; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1911); return
 isl_stat_error; } while (0); } while (0)
	    return isl_stat_error)do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break
; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1911); return
 isl_stat_error; } while (0); } while (0);
tab->bmap = isl_basic_map_add_ineq(tab->bmap, ineq);
if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0)
	return isl_stat_error;
if (!tab->bmap)
	return isl_stat_error;
}
if (tab->cone) {
17
←
Assuming field 'cone' is 0→
18
←
Taking false branch→
isl_int_init(cst)isl_sioimath_init((cst));
isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0);
isl_int_swap(ineq[0], cst)isl_sioimath_swap((ineq[0]), (cst));
}
r = isl_tab_add_row(tab, ineq);
if (tab->cone) {
19
←
Assuming field 'cone' is not equal to 0→
20
←
Taking true branch→
isl_int_swap(ineq[0], cst)isl_sioimath_swap((ineq[0]), (cst));
21
←
Calling 'isl_sioimath_swap'→
isl_int_clear(cst)isl_sioimath_clear((cst));
}
if (r < 0)
return isl_stat_error;
tab->con[r].is_nonneg = 1;
if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r]) < 0)
return isl_stat_error;
if (isl_tab_row_is_redundant(tab, tab->con[r].index)) {
if (isl_tab_mark_redundant(tab, tab->con[r].index) < 0)
	return isl_stat_error;
return isl_stat_ok;
}

sgn = restore_row(tab, &tab->con[r]);
if (sgn < -1)
return isl_stat_error;
if (sgn < 0)
return isl_tab_mark_empty(tab);
if (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)
	return isl_stat_error;
return isl_stat_ok;
1948}

1950/* Pivot a non-negative variable down until it reaches the value zero
* and then pivot the variable into a column position.
*/
1953static int to_col(struct isl_tab *tab, struct isl_tab_var *var) WARN_UNUSED__attribute__((__warn_unused_result__));
1954static int to_col(struct isl_tab *tab, struct isl_tab_var *var)
1955{
int i;
int row, col;
unsigned off = 2 + tab->M;

if (!var->is_row)
return 0;

while (isl_int_is_pos(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) >
 0)) {
find_pivot(tab, var, NULL((void*)0), -1, &row, &col);
isl_assert(tab->mat->ctx, row != -1, return -1)do { if (row != -1) break; do { isl_handle_error(tab->mat->
ctx, isl_error_unknown, "Assertion \"" "row != -1" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 1965); return -1; } while
 (0); } while (0);
if (isl_tab_pivot(tab, row, col) < 0)
	return -1;
if (!var->is_row)
	return 0;
}

for (i = tab->n_dead; i < tab->n_col; ++i)
if (!isl_int_is_zero(tab->mat->row[var->index][off + i])(isl_sioimath_sgn(*(tab->mat->row[var->index][off + i
])) == 0))
	break;

isl_assert(tab->mat->ctx, i < tab->n_col, return -1)do { if (i < tab->n_col) break; do { isl_handle_error(tab
->mat->ctx, isl_error_unknown, "Assertion \"" "i < tab->n_col"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 1976); return
 -1; } while (0); } while (0);
if (isl_tab_pivot(tab, var->index, i) < 0)
return -1;

return 0;
1981}

1983/* We assume Gaussian elimination has been performed on the equalities.
* The equalities can therefore never conflict.
* Adding the equalities is currently only really useful for a later call
* to isl_tab_ineq_type.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
1991static struct isl_tab *add_eq(struct isl_tab *tab, isl_int *eq)
1992{
int i;
int r;

if (!tab)
return NULL((void*)0);
r = isl_tab_add_row(tab, eq);
if (r < 0)
goto error;

r = tab->con[r].index;
i = isl_seq_first_non_zero(tab->mat->row[r] + 2 + tab->M + tab->n_dead,
			tab->n_col - tab->n_dead);
isl_assert(tab->mat->ctx, i >= 0, goto error)do { if (i >= 0) break; do { isl_handle_error(tab->mat->
ctx, isl_error_unknown, "Assertion \"" "i >= 0" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 2005); goto error; } while
 (0); } while (0);
i += tab->n_dead;
if (isl_tab_pivot(tab, r, i) < 0)
goto error;
if (isl_tab_kill_col(tab, i) < 0)
goto error;
tab->n_eq++;

return tab;
2014error:
isl_tab_free(tab);
return NULL((void*)0);
2017}

2019/* Does the sample value of row "row" of "tab" involve the big parameter,
* if any?
*/
2022static int row_is_big(struct isl_tab *tab, int row)
2023{
return tab->M && !isl_int_is_zero(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) == 0);
2025}

2027static int row_is_manifestly_zero(struct isl_tab *tab, int row)
2028{
unsigned off = 2 + tab->M;

if (!isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0))
return 0;
if (row_is_big(tab, row))
return 0;
return isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
			tab->n_col - tab->n_dead) == -1;
2037}

2039/* Add an equality that is known to be valid for the given tableau.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
2044int isl_tab_add_valid_eq(struct isl_tab *tab, isl_int *eq)
2045{
struct isl_tab_var *var;
int r;

if (!tab)
return -1;
r = isl_tab_add_row(tab, eq);
if (r < 0)
return -1;

var = &tab->con[r];
r = var->index;
if (row_is_manifestly_zero(tab, r)) {
var->is_zero = 1;
if (isl_tab_mark_redundant(tab, r) < 0)
	return -1;
return 0;
}

if (isl_int_is_neg(tab->mat->row[r][1])(isl_sioimath_sgn(*(tab->mat->row[r][1])) < 0)) {
isl_seq_neg(tab->mat->row[r] + 1, tab->mat->row[r] + 1,
	    1 + tab->n_col);
var->negated = 1;
}
var->is_nonneg = 1;
if (to_col(tab, var) < 0)
return -1;
var->is_nonneg = 0;
if (isl_tab_kill_col(tab, var->index) < 0)
return -1;

return 0;
2077}

2079/* Add a zero row to "tab" and return the corresponding index
* in the constraint array.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
2085static int add_zero_row(struct isl_tab *tab)
2086{
int r;
isl_int *row;

r = isl_tab_allocate_con(tab);
if (r < 0)
return -1;

row = tab->mat->row[tab->con[r].index];
isl_seq_clr(row + 1, 1 + tab->M + tab->n_col);
isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1);

return r;
2099}

2101/* Add equality "eq" and check if it conflicts with the
* previously added constraints or if it is obviously redundant.
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
* If tab->bmap is set, then two rows are needed instead of one.
*/
2108isl_stat isl_tab_add_eq(struct isl_tab *tab, isl_int *eq)
2109{
struct isl_tab_undo *snap = NULL((void*)0);
struct isl_tab_var *var;
int r;
int row;
int sgn;
isl_int cst;

if (!tab)
return isl_stat_error;
isl_assert(tab->mat->ctx, !tab->M, return isl_stat_error)do { if (!tab->M) break; do { isl_handle_error(tab->mat
->ctx, isl_error_unknown, "Assertion \"" "!tab->M" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 2119); return isl_stat_error
; } while (0); } while (0);

if (tab->need_undo)
snap = isl_tab_snap(tab);

if (tab->cone) {
isl_int_init(cst)isl_sioimath_init((cst));
isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0);
isl_int_swap(eq[0], cst)isl_sioimath_swap((eq[0]), (cst));
}
r = isl_tab_add_row(tab, eq);
if (tab->cone) {
isl_int_swap(eq[0], cst)isl_sioimath_swap((eq[0]), (cst));
isl_int_clear(cst)isl_sioimath_clear((cst));
}
if (r < 0)
return isl_stat_error;

var = &tab->con[r];
row = var->index;
if (row_is_manifestly_zero(tab, row)) {
if (snap)
	return isl_tab_rollback(tab, snap);
return drop_row(tab, row);
}

if (tab->bmap) {
tab->bmap = isl_basic_map_add_ineq(tab->bmap, eq);
if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0)
	return isl_stat_error;
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)
	return isl_stat_error;
if (!tab->bmap)
	return isl_stat_error;
if (add_zero_row(tab) < 0)
	return isl_stat_error;
}

sgn = isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1]));

if (sgn > 0) {
isl_seq_neg(tab->mat->row[row] + 1, tab->mat->row[row] + 1,
	    1 + tab->n_col);
var->negated = 1;
sgn = -1;
}

if (sgn < 0) {
sgn = sign_of_max(tab, var);
if (sgn < -1)
	return isl_stat_error;
if (sgn < 0) {
	if (isl_tab_mark_empty(tab) < 0)
		return isl_stat_error;
	return isl_stat_ok;
}
}

var->is_nonneg = 1;
if (to_col(tab, var) < 0)
return isl_stat_error;
var->is_nonneg = 0;
if (isl_tab_kill_col(tab, var->index) < 0)
return isl_stat_error;

return isl_stat_ok;
2188}

2190/* Construct and return an inequality that expresses an upper bound
* on the given div.
* In particular, if the div is given by
*
*	d = floor(e/m)
*
* then the inequality expresses
*
*	m d <= e
*/
2200static __isl_give isl_vec *ineq_for_div(__isl_keep isl_basic_map *bmap,
unsigned div)
2202{
isl_size total;
unsigned div_pos;
struct isl_vec *ineq;

total = isl_basic_map_dim(bmap, isl_dim_all);
if (total < 0)
return NULL((void*)0);

div_pos = 1 + total - bmap->n_div + div;

ineq = isl_vec_alloc(bmap->ctx, 1 + total);
if (!ineq)
return NULL((void*)0);

isl_seq_cpy(ineq->el, bmap->div[div] + 1, 1 + total);
isl_int_neg(ineq->el[div_pos], bmap->div[div][0])isl_sioimath_neg((ineq->el[div_pos]), *(bmap->div[div][
0]));
return ineq;
2220}

2222/* For a div d = floor(f/m), add the constraints
*
*		f - m d >= 0
*		-(f-(m-1)) + m d >= 0
*
* Note that the second constraint is the negation of
*
*		f - m d >= m
*
* If add_ineq is not NULL, then this function is used
* instead of isl_tab_add_ineq to effectively add the inequalities.
*
* This function assumes that at least two more rows and at least
* two more elements in the constraint array are available in the tableau.
*/
2237static isl_stat add_div_constraints(struct isl_tab *tab, unsigned div,
isl_stat (*add_ineq)(void *user, isl_int *), void *user)
2239{
isl_size total;
unsigned div_pos;
struct isl_vec *ineq;

total = isl_basic_map_dim(tab->bmap, isl_dim_all);
if (total < 0)
return isl_stat_error;
div_pos = 1 + total - tab->bmap->n_div + div;

ineq = ineq_for_div(tab->bmap, div);
if (!ineq)
goto error;

if (add_ineq) {
if (add_ineq(user, ineq->el) < 0)
	goto error;
} else {
if (isl_tab_add_ineq(tab, ineq->el) < 0)
	goto error;
}

isl_seq_neg(ineq->el, tab->bmap->div[div] + 1, 1 + total);
isl_int_set(ineq->el[div_pos], tab->bmap->div[div][0])isl_sioimath_set((ineq->el[div_pos]), *(tab->bmap->div
[div][0]));
isl_int_add(ineq->el[0], ineq->el[0], ineq->el[div_pos])isl_sioimath_add((ineq->el[0]), *(ineq->el[0]), *(ineq->
el[div_pos]));
isl_int_sub_ui(ineq->el[0], ineq->el[0], 1)isl_sioimath_sub_ui((ineq->el[0]), *(ineq->el[0]), 1);

if (add_ineq) {
if (add_ineq(user, ineq->el) < 0)
	goto error;
} else {
if (isl_tab_add_ineq(tab, ineq->el) < 0)
	goto error;
}

isl_vec_free(ineq);

return isl_stat_ok;
2277error:
isl_vec_free(ineq);
return isl_stat_error;
2280}

2282/* Check whether the div described by "div" is obviously non-negative.
* If we are using a big parameter, then we will encode the div
* as div' = M + div, which is always non-negative.
* Otherwise, we check whether div is a non-negative affine combination
* of non-negative variables.
*/
2288static int div_is_nonneg(struct isl_tab *tab, __isl_keep isl_vec *div)
2289{
int i;

if (tab->M)
return 1;

if (isl_int_is_neg(div->el[1])(isl_sioimath_sgn(*(div->el[1])) < 0))
return 0;

for (i = 0; i < tab->n_var; ++i) {
if (isl_int_is_neg(div->el[2 + i])(isl_sioimath_sgn(*(div->el[2 + i])) < 0))
	return 0;
if (isl_int_is_zero(div->el[2 + i])(isl_sioimath_sgn(*(div->el[2 + i])) == 0))
	continue;
if (!tab->var[i].is_nonneg)
	return 0;
}

return 1;
2308}

2310/* Insert an extra div, prescribed by "div", to the tableau and
* the associated bmap (which is assumed to be non-NULL).
* The extra integer division is inserted at (tableau) position "pos".
* Return "pos" or -1 if an error occurred.
*
* If add_ineq is not NULL, then this function is used instead
* of isl_tab_add_ineq to add the div constraints.
* This complication is needed because the code in isl_tab_pip
* wants to perform some extra processing when an inequality
* is added to the tableau.
*/
2321int isl_tab_insert_div(struct isl_tab *tab, int pos, __isl_keep isl_vec *div,
isl_stat (*add_ineq)(void *user, isl_int *), void *user)
2323{
int r;
int nonneg;
isl_size n_div;
int o_div;

if (!tab || !div)
return -1;

if (div->size != 1 + 1 + tab->n_var)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "unexpected size", "polly/lib/External/isl/isl_tab.c", 2334
); return -1; } while (0)
	"unexpected size", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "unexpected size", "polly/lib/External/isl/isl_tab.c", 2334
); return -1; } while (0);

n_div = isl_basic_map_dim(tab->bmap, isl_dim_div);
if (n_div < 0)
return -1;
o_div = tab->n_var - n_div;
if (pos < o_div || pos > tab->n_var)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "invalid position", "polly/lib/External/isl/isl_tab.c", 2342
); return -1; } while (0)
	"invalid position", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "invalid position", "polly/lib/External/isl/isl_tab.c", 2342
); return -1; } while (0);

nonneg = div_is_nonneg(tab, div);

if (isl_tab_extend_cons(tab, 3) < 0)
return -1;
if (isl_tab_extend_vars(tab, 1) < 0)
return -1;
r = isl_tab_insert_var(tab, pos);
if (r < 0)
return -1;

if (nonneg)
tab->var[r].is_nonneg = 1;

tab->bmap = isl_basic_map_insert_div(tab->bmap, pos - o_div, div);
if (!tab->bmap)
return -1;
if (isl_tab_push_var(tab, isl_tab_undo_bmap_div, &tab->var[r]) < 0)
return -1;

if (add_div_constraints(tab, pos - o_div, add_ineq, user) < 0)
return -1;

return r;
2367}

2369/* Add an extra div, prescribed by "div", to the tableau and
* the associated bmap (which is assumed to be non-NULL).
*/
2372int isl_tab_add_div(struct isl_tab *tab, __isl_keep isl_vec *div)
2373{
if (!tab)
return -1;
return isl_tab_insert_div(tab, tab->n_var, div, NULL((void*)0), NULL((void*)0));
2377}

2379/* If "track" is set, then we want to keep track of all constraints in tab
* in its bmap field.  This field is initialized from a copy of "bmap",
* so we need to make sure that all constraints in "bmap" also appear
* in the constructed tab.
*/
2384__isl_give struct isl_tab *isl_tab_from_basic_map(
__isl_keep isl_basic_map *bmap, int track)
2386{
int i;
struct isl_tab *tab;
isl_size total;

total = isl_basic_map_dim(bmap, isl_dim_all);
if (total < 0)
2
←
Assuming 'total' is >= 0→
3
←
Taking false branch→
return NULL((void*)0);
tab = isl_tab_alloc(bmap->ctx, total + bmap->n_ineq + 1, total, 0);
if (!tab)
4
←
Assuming 'tab' is non-null→
5
←
Taking false branch→
return NULL((void*)0);
tab->preserve = track;
tab->rational = ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)(!!(((bmap)->flags) & ((1 << 4))));
6
←
Assuming the condition is false→
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)(!!(((bmap)->flags) & ((1 << 1))))) {
7
←
Assuming the condition is true→
8
←
Taking false branch→
if (isl_tab_mark_empty(tab) < 0)
	goto error;
goto done;
}
for (i = 0; i < bmap->n_eq; ++i) {
9
←
Assuming 'i' is >= field 'n_eq'→
10
←
Loop condition is false. Execution continues on line 2409→
tab = add_eq(tab, bmap->eq[i]);
if (!tab)
	return tab;
}
for (i = 0; i < bmap->n_ineq; ++i) {
11
←
Assuming 'i' is < field 'n_ineq'→
12
←
Loop condition is true.  Entering loop body→
if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0)
13
←
Calling 'isl_tab_add_ineq'→
	goto error;
if (tab->empty)
	goto done;
}
2415done:
if (track && isl_tab_track_bmap(tab, isl_basic_map_copy(bmap)) < 0)
goto error;
return tab;
2419error:
isl_tab_free(tab);
return NULL((void*)0);
2422}

2424__isl_give struct isl_tab *isl_tab_from_basic_set(
__isl_keep isl_basic_setisl_basic_map *bset, int track)
2426{
return isl_tab_from_basic_map(bset, track);
1
Calling 'isl_tab_from_basic_map'→
2428}

2430/* Construct a tableau corresponding to the recession cone of "bset".
*/
2432struct isl_tab *isl_tab_from_recession_cone(__isl_keep isl_basic_setisl_basic_map *bset,
int parametric)
2434{
isl_int cst;
int i;
struct isl_tab *tab;
isl_size offset = 0;
isl_size total;

total = isl_basic_set_dim(bset, isl_dim_all);
if (parametric)
offset = isl_basic_set_dim(bset, isl_dim_param);
if (total < 0 || offset < 0)
return NULL((void*)0);
tab = isl_tab_alloc(bset->ctx, bset->n_eq + bset->n_ineq,
		total - offset, 0);
if (!tab)
return NULL((void*)0);
tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL)(!!(((bset)->flags) & ((1 << 4))));
tab->cone = 1;

isl_int_init(cst)isl_sioimath_init((cst));
isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0);
for (i = 0; i < bset->n_eq; ++i) {
isl_int_swap(bset->eq[i][offset], cst)isl_sioimath_swap((bset->eq[i][offset]), (cst));
if (offset > 0) {
	if (isl_tab_add_eq(tab, bset->eq[i] + offset) < 0)
		goto error;
} else
	tab = add_eq(tab, bset->eq[i]);
isl_int_swap(bset->eq[i][offset], cst)isl_sioimath_swap((bset->eq[i][offset]), (cst));
if (!tab)
	goto done;
}
for (i = 0; i < bset->n_ineq; ++i) {
int r;
isl_int_swap(bset->ineq[i][offset], cst)isl_sioimath_swap((bset->ineq[i][offset]), (cst));
r = isl_tab_add_row(tab, bset->ineq[i] + offset);
isl_int_swap(bset->ineq[i][offset], cst)isl_sioimath_swap((bset->ineq[i][offset]), (cst));
if (r < 0)
	goto error;
tab->con[r].is_nonneg = 1;
if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r]) < 0)
	goto error;
}
2477done:
isl_int_clear(cst)isl_sioimath_clear((cst));
return tab;
2480error:
isl_int_clear(cst)isl_sioimath_clear((cst));
isl_tab_free(tab);
return NULL((void*)0);
2484}

2486/* Assuming "tab" is the tableau of a cone, check if the cone is
* bounded, i.e., if it is empty or only contains the origin.
*/
2489isl_bool isl_tab_cone_is_bounded(struct isl_tab *tab)
2490{
int i;

if (!tab)
return isl_bool_error;
if (tab->empty)
return isl_bool_true;
if (tab->n_dead == tab->n_col)
return isl_bool_true;

for (;;) {
for (i = tab->n_redundant; i < tab->n_row; ++i) {
	struct isl_tab_var *var;
	int sgn;
	var = isl_tab_var_from_row(tab, i);
	if (!var->is_nonneg)
		continue;
	sgn = sign_of_max(tab, var);
	if (sgn < -1)
		return isl_bool_error;
	if (sgn != 0)
		return isl_bool_false;
	if (close_row(tab, var, 0) < 0)
		return isl_bool_error;
	break;
}
if (tab->n_dead == tab->n_col)
	return isl_bool_true;
if (i == tab->n_row)
	return isl_bool_false;
}
2521}

2523int isl_tab_sample_is_integer(struct isl_tab *tab)
2524{
int i;

if (!tab)
return -1;

for (i = 0; i < tab->n_var; ++i) {
int row;
if (!tab->var[i].is_row)
	continue;
row = tab->var[i].index;
if (!isl_int_is_divisible_by(tab->mat->row[row][1],isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), *
(tab->mat->row[row][0]))
				tab->mat->row[row][0])isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), *
(tab->mat->row[row][0])))
	return 0;
}
return 1;
2540}

2542static struct isl_vec *extract_integer_sample(struct isl_tab *tab)
2543{
int i;
struct isl_vec *vec;

vec = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var);
if (!vec)
return NULL((void*)0);

isl_int_set_si(vec->block.data[0], 1)isl_sioimath_set_si((vec->block.data[0]), 1);
for (i = 0; i < tab->n_var; ++i) {
if (!tab->var[i].is_row)
	isl_int_set_si(vec->block.data[1 + i], 0)isl_sioimath_set_si((vec->block.data[1 + i]), 0);
else {
	int row = tab->var[i].index;
	isl_int_divexact(vec->block.data[1 + i],isl_sioimath_tdiv_q((vec->block.data[1 + i]), *(tab->mat
->row[row][1]), *(tab->mat->row[row][0]))
		tab->mat->row[row][1], tab->mat->row[row][0])isl_sioimath_tdiv_q((vec->block.data[1 + i]), *(tab->mat
->row[row][1]), *(tab->mat->row[row][0]));
}
}

return vec;
2563}

2565__isl_give isl_vec *isl_tab_get_sample_value(struct isl_tab *tab)
2566{
int i;
struct isl_vec *vec;
isl_int m;

if (!tab)
return NULL((void*)0);

vec = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var);
if (!vec)
return NULL((void*)0);

isl_int_init(m)isl_sioimath_init((m));

isl_int_set_si(vec->block.data[0], 1)isl_sioimath_set_si((vec->block.data[0]), 1);
for (i = 0; i < tab->n_var; ++i) {
int row;
if (!tab->var[i].is_row) {
	isl_int_set_si(vec->block.data[1 + i], 0)isl_sioimath_set_si((vec->block.data[1 + i]), 0);
	continue;
}
row = tab->var[i].index;
isl_int_gcd(m, vec->block.data[0], tab->mat->row[row][0])isl_sioimath_gcd((m), *(vec->block.data[0]), *(tab->mat
->row[row][0]));
isl_int_divexact(m, tab->mat->row[row][0], m)isl_sioimath_tdiv_q((m), *(tab->mat->row[row][0]), *(m)
);
isl_seq_scale(vec->block.data, vec->block.data, m, 1 + i);
isl_int_divexact(m, vec->block.data[0], tab->mat->row[row][0])isl_sioimath_tdiv_q((m), *(vec->block.data[0]), *(tab->
mat->row[row][0]));
isl_int_mul(vec->block.data[1 + i], m, tab->mat->row[row][1])isl_sioimath_mul((vec->block.data[1 + i]), *(m), *(tab->
mat->row[row][1]));
}
vec = isl_vec_normalize(vec);

isl_int_clear(m)isl_sioimath_clear((m));
return vec;
2598}

2600/* Store the sample value of "var" of "tab" rounded up (if sgn > 0)
* or down (if sgn < 0) to the nearest integer in *v.
*/
2603static void get_rounded_sample_value(struct isl_tab *tab,
struct isl_tab_var *var, int sgn, isl_int *v)
2605{
if (!var->is_row)
isl_int_set_si(*v, 0)isl_sioimath_set_si((*v), 0);
else if (sgn > 0)
isl_int_cdiv_q(*v, tab->mat->row[var->index][1],isl_sioimath_cdiv_q((*v), *(tab->mat->row[var->index
][1]), *(tab->mat->row[var->index][0]))
		   tab->mat->row[var->index][0])isl_sioimath_cdiv_q((*v), *(tab->mat->row[var->index
][1]), *(tab->mat->row[var->index][0]));
else
isl_int_fdiv_q(*v, tab->mat->row[var->index][1],isl_sioimath_fdiv_q((*v), *(tab->mat->row[var->index
][1]), *(tab->mat->row[var->index][0]))
		   tab->mat->row[var->index][0])isl_sioimath_fdiv_q((*v), *(tab->mat->row[var->index
][1]), *(tab->mat->row[var->index][0]));
2614}

2616/* Update "bmap" based on the results of the tableau "tab".
* In particular, implicit equalities are made explicit, redundant constraints
* are removed and if the sample value happens to be integer, it is stored
* in "bmap" (unless "bmap" already had an integer sample).
*
* The tableau is assumed to have been created from "bmap" using
* isl_tab_from_basic_map.
*/
2624__isl_give isl_basic_map *isl_basic_map_update_from_tab(
__isl_take isl_basic_map *bmap, struct isl_tab *tab)
2626{
int i;
unsigned n_eq;

if (!bmap)
return NULL((void*)0);
if (!tab)
return bmap;

n_eq = tab->n_eq;
if (tab->empty)
bmap = isl_basic_map_set_to_empty(bmap);
else
for (i = bmap->n_ineq - 1; i >= 0; --i) {
	if (isl_tab_is_equality(tab, n_eq + i))
		isl_basic_map_inequality_to_equality(bmap, i);
	else if (isl_tab_is_redundant(tab, n_eq + i))
		isl_basic_map_drop_inequality(bmap, i);
}
if (bmap->n_eq != n_eq)
bmap = isl_basic_map_gauss(bmap, NULL((void*)0));
if (!tab->rational &&
   bmap && !bmap->sample && isl_tab_sample_is_integer(tab))
bmap->sample = extract_integer_sample(tab);
return bmap;
2651}

2653__isl_give isl_basic_setisl_basic_map *isl_basic_set_update_from_tab(
__isl_take isl_basic_setisl_basic_map *bset, struct isl_tab *tab)
2655{
return bset_from_bmap(isl_basic_map_update_from_tab(bset_to_bmap(bset),
						tab));
2658}

2660/* Drop the last constraint added to "tab" in position "r".
* The constraint is expected to have remained in a row.
*/
2663static isl_stat drop_last_con_in_row(struct isl_tab *tab, int r)
2664{
if (!tab->con[r].is_row)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row unexpectedly moved to column", "polly/lib/External/isl/isl_tab.c"
, 2668); return isl_stat_error; } while (0)
	"row unexpectedly moved to column",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row unexpectedly moved to column", "polly/lib/External/isl/isl_tab.c"
, 2668); return isl_stat_error; } while (0)
	return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "row unexpectedly moved to column", "polly/lib/External/isl/isl_tab.c"
, 2668); return isl_stat_error; } while (0);
if (r + 1 != tab->n_con)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "additional constraints added", "polly/lib/External/isl/isl_tab.c"
, 2671); return isl_stat_error; } while (0)
	"additional constraints added", return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "additional constraints added", "polly/lib/External/isl/isl_tab.c"
, 2671); return isl_stat_error; } while (0);
if (drop_row(tab, tab->con[r].index) < 0)
return isl_stat_error;

return isl_stat_ok;
2676}

2678/* Given a non-negative variable "var", temporarily add a new non-negative
* variable that is the opposite of "var", ensuring that "var" can only attain
* the value zero.  The new variable is removed again before this function
* returns.  However, the effect of forcing "var" to be zero remains.
* If var = n/d is a row variable, then the new variable = -n/d.
* If var is a column variables, then the new variable = -var.
* If the new variable cannot attain non-negative values, then
* the resulting tableau is empty.
* Otherwise, we know the value will be zero and we close the row.
*/
2688static isl_stat cut_to_hyperplane(struct isl_tab *tab, struct isl_tab_var *var)
2689{
unsigned r;
isl_int *row;
int sgn;
unsigned off = 2 + tab->M;

if (var->is_zero)
return isl_stat_ok;
if (var->is_redundant || !var->is_nonneg)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "expecting non-redundant non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 2700); return isl_stat_error; } while (0)
	"expecting non-redundant non-negative variable",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "expecting non-redundant non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 2700); return isl_stat_error; } while (0)
	return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "expecting non-redundant non-negative variable", "polly/lib/External/isl/isl_tab.c"
, 2700); return isl_stat_error; } while (0);

if (isl_tab_extend_cons(tab, 1) < 0)
return isl_stat_error;

r = tab->n_con;
tab->con[r].index = tab->n_row;
tab->con[r].is_row = 1;
tab->con[r].is_nonneg = 0;
tab->con[r].is_zero = 0;
tab->con[r].is_redundant = 0;
tab->con[r].frozen = 0;
tab->con[r].negated = 0;
tab->row_var[tab->n_row] = ~r;
row = tab->mat->row[tab->n_row];

if (var->is_row) {
isl_int_set(row[0], tab->mat->row[var->index][0])isl_sioimath_set((row[0]), *(tab->mat->row[var->index
][0]));
isl_seq_neg(row + 1,
	    tab->mat->row[var->index] + 1, 1 + tab->n_col);
} else {
isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1);
isl_seq_clr(row + 1, 1 + tab->n_col);
isl_int_set_si(row[off + var->index], -1)isl_sioimath_set_si((row[off + var->index]), -1);
}

tab->n_row++;
tab->n_con++;

sgn = sign_of_max(tab, &tab->con[r]);
if (sgn < -1)
return isl_stat_error;
if (sgn < 0) {
if (drop_last_con_in_row(tab, r) < 0)
	return isl_stat_error;
if (isl_tab_mark_empty(tab) < 0)
	return isl_stat_error;
return isl_stat_ok;
}
tab->con[r].is_nonneg = 1;
/* sgn == 0 */
if (close_row(tab, &tab->con[r], 1) < 0)
return isl_stat_error;
if (drop_last_con_in_row(tab, r) < 0)
return isl_stat_error;

return isl_stat_ok;
2747}

2749/* Check that "con" is a valid constraint position for "tab".
*/
2751static isl_stat isl_tab_check_con(struct isl_tab *tab, int con)
2752{
if (!tab)
return isl_stat_error;
if (con < 0 || con >= tab->n_con)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "position out of bounds", "polly/lib/External/isl/isl_tab.c"
, 2757); return isl_stat_error; } while (0)
	"position out of bounds", return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "position out of bounds", "polly/lib/External/isl/isl_tab.c"
, 2757); return isl_stat_error; } while (0);
return isl_stat_ok;
2759}

2761/* Given a tableau "tab" and an inequality constraint "con" of the tableau,
* relax the inequality by one.  That is, the inequality r >= 0 is replaced
* by r' = r + 1 >= 0.
* If r is a row variable, we simply increase the constant term by one
* (taking into account the denominator).
* If r is a column variable, then we need to modify each row that
* refers to r = r' - 1 by substituting this equality, effectively
* subtracting the coefficient of the column from the constant.
* We should only do this if the minimum is manifestly unbounded,
* however.  Otherwise, we may end up with negative sample values
* for non-negative variables.
* So, if r is a column variable with a minimum that is not
* manifestly unbounded, then we need to move it to a row.
* However, the sample value of this row may be negative,
* even after the relaxation, so we need to restore it.
* We therefore prefer to pivot a column up to a row, if possible.
*/
2778int isl_tab_relax(struct isl_tab *tab, int con)
2779{
struct isl_tab_var *var;

if (!tab)
return -1;

var = &tab->con[con];

if (var->is_row && (var->index < 0 || var->index < tab->n_redundant))
isl_die(tab->mat->ctx, isl_error_invalid,do { isl_handle_error(tab->mat->ctx, isl_error_invalid,
 "cannot relax redundant constraint", "polly/lib/External/isl/isl_tab.c"
, 2789); return -1; } while (0)
	"cannot relax redundant constraint", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_invalid,
 "cannot relax redundant constraint", "polly/lib/External/isl/isl_tab.c"
, 2789); return -1; } while (0);
if (!var->is_row && (var->index < 0 || var->index < tab->n_dead))
isl_die(tab->mat->ctx, isl_error_invalid,do { isl_handle_error(tab->mat->ctx, isl_error_invalid,
 "cannot relax dead constraint", "polly/lib/External/isl/isl_tab.c"
, 2792); return -1; } while (0)
	"cannot relax dead constraint", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_invalid,
 "cannot relax dead constraint", "polly/lib/External/isl/isl_tab.c"
, 2792); return -1; } while (0);

if (!var->is_row && !max_is_manifestly_unbounded(tab, var))
if (to_row(tab, var, 1) < 0)
	return -1;
if (!var->is_row && !min_is_manifestly_unbounded(tab, var))
if (to_row(tab, var, -1) < 0)
	return -1;

if (var->is_row) {
isl_int_add(tab->mat->row[var->index][1],isl_sioimath_add((tab->mat->row[var->index][1]), *(tab
->mat->row[var->index][1]), *(tab->mat->row[var
->index][0]))
    tab->mat->row[var->index][1], tab->mat->row[var->index][0])isl_sioimath_add((tab->mat->row[var->index][1]), *(tab
->mat->row[var->index][1]), *(tab->mat->row[var
->index][0]));
if (restore_row(tab, var) < 0)
	return -1;
} else {
int i;
unsigned off = 2 + tab->M;

for (i = 0; i < tab->n_row; ++i) {
	if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index
])) == 0))
		continue;
	isl_int_sub(tab->mat->row[i][1], tab->mat->row[i][1],isl_sioimath_sub((tab->mat->row[i][1]), *(tab->mat->
row[i][1]), *(tab->mat->row[i][off + var->index]))
	    tab->mat->row[i][off + var->index])isl_sioimath_sub((tab->mat->row[i][1]), *(tab->mat->
row[i][1]), *(tab->mat->row[i][off + var->index]));
}

}

if (isl_tab_push_var(tab, isl_tab_undo_relax, var) < 0)
return -1;

return 0;
2823}

2825/* Replace the variable v at position "pos" in the tableau "tab"
* by v' = v + shift.
*
* If the variable is in a column, then we first check if we can
* simply plug in v = v' - shift.  The effect on a row with
* coefficient f/d for variable v is that the constant term c/d
* is replaced by (c - f * shift)/d.  If shift is positive and
* f is negative for each row that needs to remain non-negative,
* then this is clearly safe.  In other words, if the minimum of v
* is manifestly unbounded, then we can keep v in a column position.
* Otherwise, we can pivot it down to a row.
* Similarly, if shift is negative, we need to check if the maximum
* of is manifestly unbounded.
*
* If the variable is in a row (from the start or after pivoting),
* then the constant term c/d is replaced by (c + d * shift)/d.
*/
2842int isl_tab_shift_var(struct isl_tab *tab, int pos, isl_int shift)
2843{
struct isl_tab_var *var;

if (!tab)
return -1;
if (isl_int_is_zero(shift)(isl_sioimath_sgn(*(shift)) == 0))
return 0;

var = &tab->var[pos];
if (!var->is_row) {
if (isl_int_is_neg(shift)(isl_sioimath_sgn(*(shift)) < 0)) {
	if (!max_is_manifestly_unbounded(tab, var))
		if (to_row(tab, var, 1) < 0)
			return -1;
} else {
	if (!min_is_manifestly_unbounded(tab, var))
		if (to_row(tab, var, -1) < 0)
			return -1;
}
}

if (var->is_row) {
isl_int_addmul(tab->mat->row[var->index][1],isl_sioimath_addmul((tab->mat->row[var->index][1]), *
(shift), *(tab->mat->row[var->index][0]))
		shift, tab->mat->row[var->index][0])isl_sioimath_addmul((tab->mat->row[var->index][1]), *
(shift), *(tab->mat->row[var->index][0]));
} else {
int i;
unsigned off = 2 + tab->M;

for (i = 0; i < tab->n_row; ++i) {
	if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index
])) == 0))
		continue;
	isl_int_submul(tab->mat->row[i][1],isl_sioimath_submul((tab->mat->row[i][1]), *(shift), *(
tab->mat->row[i][off + var->index]))
		    shift, tab->mat->row[i][off + var->index])isl_sioimath_submul((tab->mat->row[i][1]), *(shift), *(
tab->mat->row[i][off + var->index]));
}

}

return 0;
2881}

2883/* 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.
*/
2888int isl_tab_unrestrict(struct isl_tab *tab, int con)
2889{
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;
2904}

2906int isl_tab_select_facet(struct isl_tab *tab, int con)
2907{
if (!tab)
return -1;

return cut_to_hyperplane(tab, &tab->con[con]);
2912}

2914static int may_be_equality(struct isl_tab *tab, int row)
2915{
return tab->rational ? isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0)
	     : isl_int_lt(tab->mat->row[row][1],(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat
->row[row][0])) < 0)
			    tab->mat->row[row][0])(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat
->row[row][0])) < 0);
2919}

2921/* Return an isl_tab_var that has been marked or NULL if no such
* variable can be found.
* The marked field has only been set for variables that
* appear in non-redundant rows or non-dead columns.
*
* Pick the last constraint variable that is marked and
* that appears in either a non-redundant row or a non-dead columns.
* Since the returned variable is tested for being a redundant constraint or
* an implicit equality, there is no need to return any tab variable that
* corresponds to a variable.
*/
2932static struct isl_tab_var *select_marked(struct isl_tab *tab)
2933{
int i;
struct isl_tab_var *var;

for (i = tab->n_con - 1; i >= 0; --i) {
var = &tab->con[i];
if (var->index < 0)
	continue;
if (var->is_row && var->index < tab->n_redundant)
	continue;
if (!var->is_row && var->index < tab->n_dead)
	continue;
if (var->marked)
	return var;
}

return NULL((void*)0);
2950}

2952/* Check for (near) equalities among the constraints.
* A constraint is an equality if it is non-negative and if
* its maximal value is either
*	- zero (in case of rational tableaus), or
*	- strictly less than 1 (in case of integer tableaus)
*
* We first mark all non-redundant and non-dead variables that
* are not frozen and not obviously not an equality.
* Then we iterate over all marked variables if they can attain
* any values larger than zero or at least one.
* If the maximal value is zero, we mark any column variables
* that appear in the row as being zero and mark the row as being redundant.
* Otherwise, if the maximal value is strictly less than one (and the
* tableau is integer), then we restrict the value to being zero
* by adding an opposite non-negative variable.
* The order in which the variables are considered is not important.
*/
2969int isl_tab_detect_implicit_equalities(struct isl_tab *tab)
2970{
int i;
unsigned n_marked;

if (!tab)
return -1;
if (tab->empty)
return 0;
if (tab->n_dead == tab->n_col)
return 0;

n_marked = 0;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
struct isl_tab_var *var = isl_tab_var_from_row(tab, i);
var->marked = !var->frozen && var->is_nonneg &&
	may_be_equality(tab, i);
if (var->marked)
	n_marked++;
}
for (i = tab->n_dead; i < tab->n_col; ++i) {
struct isl_tab_var *var = var_from_col(tab, i);
var->marked = !var->frozen && var->is_nonneg;
if (var->marked)
	n_marked++;
}
while (n_marked) {
struct isl_tab_var *var;
int sgn;
var = select_marked(tab);
if (!var)
	break;
var->marked = 0;
n_marked--;
sgn = sign_of_max(tab, var);
if (sgn < 0)
	return -1;
if (sgn == 0) {
	if (close_row(tab, var, 0) < 0)
		return -1;
} else if (!tab->rational && !at_least_one(tab, var)) {
	if (cut_to_hyperplane(tab, var) < 0)
		return -1;
	return isl_tab_detect_implicit_equalities(tab);
}
for (i = tab->n_redundant; i < tab->n_row; ++i) {
	var = isl_tab_var_from_row(tab, i);
	if (!var->marked)
		continue;
	if (may_be_equality(tab, i))
		continue;
	var->marked = 0;
	n_marked--;
}
}

return 0;
3026}

3028/* 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".
*/
3031static int update_con_after_move(struct isl_tab *tab, int i, int old)
3032{
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,do { isl_handle_error(tab->mat->ctx, isl_error_internal
, "broken internal state", "polly/lib/External/isl/isl_tab.c"
, 3042); return -1; } while (0)
	"broken internal state", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_internal
, "broken internal state", "polly/lib/External/isl/isl_tab.c"
, 3042); return -1; } while (0);
p[index] = ~i;

return 0;
3046}

3048/* Interchange constraints "con1" and "con2" in "tab".
* In particular, interchange the contents of these entries in tab->con.
* Since tab->col_var and tab->row_var point back into this array,
* they need to be updated accordingly.
*/
3053isl_stat isl_tab_swap_constraints(struct isl_tab *tab, int con1, int con2)
3054{
struct isl_tab_var var;

if (isl_tab_check_con(tab, con1) < 0 ||
   isl_tab_check_con(tab, con2) < 0)
return isl_stat_error;

var = tab->con[con1];
tab->con[con1] = tab->con[con2];
if (update_con_after_move(tab, con1, con2) < 0)
return isl_stat_error;
tab->con[con2] = var;
if (update_con_after_move(tab, con2, con1) < 0)
return isl_stat_error;

return isl_stat_ok;
3070}

3072/* Rotate the "n" constraints starting at "first" to the right,
* putting the last constraint in the position of the first constraint.
*/
3075static int rotate_constraints(struct isl_tab *tab, int first, int n)
3076{
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;
3095}

3097/* Drop the "n" entries starting at position "first" in tab->con, moving all
* subsequent entries down.
* Since some of the entries of tab->row_var and tab->col_var contain
* indices into this array, they have to be updated accordingly.
*/
3102static isl_stat con_drop_entries(struct isl_tab *tab,
unsigned first, unsigned n)
3104{
int i;

if (first + n > tab->n_con || first + n < first)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid range", "polly/lib/External/isl/isl_tab.c", 3109);
 return isl_stat_error; } while (0)
	"invalid range", return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "invalid range", "polly/lib/External/isl/isl_tab.c", 3109);
 return isl_stat_error; } while (0);

tab->n_con -= n;

for (i = first; i < tab->n_con; ++i) {
tab->con[i] = tab->con[i + n];
if (update_con_after_move(tab, i, i + n) < 0)
	return isl_stat_error;
}

return isl_stat_ok;
3120}

3122/* isl_basic_map_gauss5 callback that gets called when
* two (equality) constraints "a" and "b" get interchanged
* in the basic map.  Perform the same interchange in "tab".
*/
3126static isl_stat swap_eq(unsigned a, unsigned b, void *user)
3127{
struct isl_tab *tab = user;

return isl_tab_swap_constraints(tab, a, b);
3131}

3133/* isl_basic_map_gauss5 callback that gets called when
* the final "n" equality constraints get removed.
* As a special case, if "n" is equal to the total number
* of equality constraints, then this means the basic map
* turned out to be empty.
* Drop the same number of equality constraints from "tab" or
* mark it empty in the special case.
*/
3141static isl_stat drop_eq(unsigned n, void *user)
3142{
struct isl_tab *tab = user;

if (tab->n_eq == n)
return isl_tab_mark_empty(tab);

tab->n_eq -= n;
return con_drop_entries(tab, tab->n_eq, n);
3150}

3152/* If "bmap" has more than a single reference, then call
* isl_basic_map_gauss on it, updating "tab" accordingly.
*/
3155static __isl_give isl_basic_map *gauss_if_shared(__isl_take isl_basic_map *bmap,
struct isl_tab *tab)
3157{
isl_bool single;

single = isl_basic_map_has_single_reference(bmap);
if (single < 0)
return isl_basic_map_free(bmap);
if (single)
return bmap;
return isl_basic_map_gauss5(bmap, NULL((void*)0), &swap_eq, &drop_eq, tab);
3166}

3168/* 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 only calls isl_basic_map_gauss
* (in case some equality constraints got detected)
* if "bmap" has more than one reference.
* If it only has a single reference, then it is left in a temporary state,
* because the caller may require this state.
* Calling isl_basic_map_gauss is then the responsibility of the caller.
*/
3201__isl_give isl_basic_map *isl_tab_make_equalities_explicit(struct isl_tab *tab,
__isl_take isl_basic_map *bmap)
3203{
int i;
unsigned n_eq;

if (!tab || !bmap)
return isl_basic_map_free(bmap);
if (tab->empty)
return bmap;

n_eq = tab->n_eq;
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++;
}

if (n_eq != tab->n_eq)
bmap = gauss_if_shared(bmap, tab);

return bmap;
3229}

3231static int con_is_redundant(struct isl_tab *tab, struct isl_tab_var *var)
3232{
if (!tab)
return -1;
if (tab->rational) {
int sgn = sign_of_min(tab, var);
if (sgn < -1)
	return -1;
return sgn >= 0;
} else {
int irred = isl_tab_min_at_most_neg_one(tab, var);
if (irred < 0)
	return -1;
return !irred;
}
3246}

3248/* Check for (near) redundant constraints.
* A constraint is redundant if it is non-negative and if
* its minimal value (temporarily ignoring the non-negativity) is either
*	- zero (in case of rational tableaus), or
*	- strictly larger than -1 (in case of integer tableaus)
*
* We first mark all non-redundant and non-dead variables that
* are not frozen and not obviously negatively unbounded.
* Then we iterate over all marked variables if they can attain
* any values smaller than zero or at most negative one.
* If not, we mark the row as being redundant (assuming it hasn't
* been detected as being obviously redundant in the mean time).
*/
3261int isl_tab_detect_redundant(struct isl_tab *tab)
3262{
int i;
unsigned n_marked;

if (!tab)
return -1;
if (tab->empty)
return 0;
if (tab->n_redundant == tab->n_row)
return 0;

n_marked = 0;
for (i = tab->n_redundant; i < tab->n_row; ++i) {
struct isl_tab_var *var = isl_tab_var_from_row(tab, i);
var->marked = !var->frozen && var->is_nonneg;
if (var->marked)
	n_marked++;
}
for (i = tab->n_dead; i < tab->n_col; ++i) {
struct isl_tab_var *var = var_from_col(tab, i);
var->marked = !var->frozen && var->is_nonneg &&
	!min_is_manifestly_unbounded(tab, var);
if (var->marked)
	n_marked++;
}
while (n_marked) {
struct isl_tab_var *var;
int red;
var = select_marked(tab);
if (!var)
	break;
var->marked = 0;
n_marked--;
red = con_is_redundant(tab, var);
if (red < 0)
	return -1;
if (red && !var->is_redundant)
	if (isl_tab_mark_redundant(tab, var->index) < 0)
		return -1;
for (i = tab->n_dead; i < tab->n_col; ++i) {
	var = var_from_col(tab, i);
	if (!var->marked)
		continue;
	if (!min_is_manifestly_unbounded(tab, var))
		continue;
	var->marked = 0;
	n_marked--;
}
}

return 0;
3313}

3315int isl_tab_is_equality(struct isl_tab *tab, int con)
3316{
int row;
unsigned off;

if (!tab)
return -1;
if (tab->con[con].is_zero)
return 1;
if (tab->con[con].is_redundant)
return 0;
if (!tab->con[con].is_row)
return tab->con[con].index < tab->n_dead;

row = tab->con[con].index;

off = 2 + tab->M;
return isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0) &&
!row_is_big(tab, row) &&
isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
			tab->n_col - tab->n_dead) == -1;
3336}

3338/* Return the minimal value of the affine expression "f" with denominator
* "denom" in *opt, *opt_denom, assuming the tableau is not empty and
* the expression cannot attain arbitrarily small values.
* If opt_denom is NULL, then *opt is rounded up to the nearest integer.
* The return value reflects the nature of the result (empty, unbounded,
* minimal value returned in *opt).
*
* This function assumes that at least one more row and at least
* one more element in the constraint array are available in the tableau.
*/
3348enum isl_lp_result isl_tab_min(struct isl_tab *tab,
isl_int *f, isl_int denom, isl_int *opt, isl_int *opt_denom,
unsigned flags)
3351{
int r;
enum isl_lp_result res = isl_lp_ok;
struct isl_tab_var *var;
struct isl_tab_undo *snap;

if (!tab)
return isl_lp_error;

if (tab->empty)
return isl_lp_empty;

snap = isl_tab_snap(tab);
r = isl_tab_add_row(tab, f);
if (r < 0)
return isl_lp_error;
var = &tab->con[r];
for (;;) {
int row, col;
find_pivot(tab, var, var, -1, &row, &col);
if (row == var->index) {
	res = isl_lp_unbounded;
	break;
}
if (row == -1)
	break;
if (isl_tab_pivot(tab, row, col) < 0)
	return isl_lp_error;
}
isl_int_mul(tab->mat->row[var->index][0],isl_sioimath_mul((tab->mat->row[var->index][0]), *(tab
->mat->row[var->index][0]), *(denom))
    tab->mat->row[var->index][0], denom)isl_sioimath_mul((tab->mat->row[var->index][0]), *(tab
->mat->row[var->index][0]), *(denom));
if (ISL_FL_ISSET(flags, ISL_TAB_SAVE_DUAL)(!!((flags) & ((1 << 0))))) {
int i;

isl_vec_free(tab->dual);
tab->dual = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_con);
if (!tab->dual)
	return isl_lp_error;
isl_int_set(tab->dual->el[0], tab->mat->row[var->index][0])isl_sioimath_set((tab->dual->el[0]), *(tab->mat->
row[var->index][0]));
for (i = 0; i < tab->n_con; ++i) {
	int pos;
	if (tab->con[i].is_row) {
		isl_int_set_si(tab->dual->el[1 + i], 0)isl_sioimath_set_si((tab->dual->el[1 + i]), 0);
		continue;
	}
	pos = 2 + tab->M + tab->con[i].index;
	if (tab->con[i].negated)
		isl_int_neg(tab->dual->el[1 + i],isl_sioimath_neg((tab->dual->el[1 + i]), *(tab->mat->
row[var->index][pos]))
			    tab->mat->row[var->index][pos])isl_sioimath_neg((tab->dual->el[1 + i]), *(tab->mat->
row[var->index][pos]));
	else
		isl_int_set(tab->dual->el[1 + i],isl_sioimath_set((tab->dual->el[1 + i]), *(tab->mat->
row[var->index][pos]))
			    tab->mat->row[var->index][pos])isl_sioimath_set((tab->dual->el[1 + i]), *(tab->mat->
row[var->index][pos]));
}
}
if (opt && res == isl_lp_ok) {
if (opt_denom) {
	isl_int_set(*opt, tab->mat->row[var->index][1])isl_sioimath_set((*opt), *(tab->mat->row[var->index]
[1]));
	isl_int_set(*opt_denom, tab->mat->row[var->index][0])isl_sioimath_set((*opt_denom), *(tab->mat->row[var->
index][0]));
} else
	get_rounded_sample_value(tab, var, 1, opt);
}
if (isl_tab_rollback(tab, snap) < 0)
return isl_lp_error;
return res;
3415}

3417/* Is the constraint at position "con" marked as being redundant?
* If it is marked as representing an equality, then it is not
* considered to be redundant.
* Note that isl_tab_mark_redundant marks both the isl_tab_var as
* redundant and moves the corresponding row into the first
* tab->n_redundant positions (or removes the row, assigning it index -1),
* so the final test is actually redundant itself.
*/
3425int isl_tab_is_redundant(struct isl_tab *tab, int con)
3426{
if (isl_tab_check_con(tab, con) < 0)
return -1;
if (tab->con[con].is_zero)
return 0;
if (tab->con[con].is_redundant)
return 1;
return tab->con[con].is_row && tab->con[con].index < tab->n_redundant;
3434}

3436/* Is variable "var" of "tab" fixed to a constant value by its row
* in the tableau?
* If so and if "value" is not NULL, then store this constant value
* in "value".
*
* That is, is it a row variable that only has non-zero coefficients
* for dead columns?
*/
3444static isl_bool is_constant(struct isl_tab *tab, struct isl_tab_var *var,
isl_int *value)
3446{
unsigned off = 2 + tab->M;
isl_mat *mat = tab->mat;
int n;
int row;
int pos;

if (!var->is_row)
return isl_bool_false;
row = var->index;
if (row_is_big(tab, row))
return isl_bool_false;
n = tab->n_col - tab->n_dead;
pos = isl_seq_first_non_zero(mat->row[row] + off + tab->n_dead, n);
if (pos != -1)
return isl_bool_false;
if (value)
isl_int_divexact(*value, mat->row[row][1], mat->row[row][0])isl_sioimath_tdiv_q((*value), *(mat->row[row][1]), *(mat->
row[row][0]));
return isl_bool_true;
3465}

3467/* Has the variable "var' of "tab" reached a value that is greater than
* or equal (if sgn > 0) or smaller than or equal (if sgn < 0) to "target"?
* "tmp" has been initialized by the caller and can be used
* to perform local computations.
*
* If the sample value involves the big parameter, then any value
* is reached.
* Otherwise check if n/d >= t, i.e., n >= d * t (if sgn > 0)
* or n/d <= t, i.e., n <= d * t (if sgn < 0).
*/
3477static int reached(struct isl_tab *tab, struct isl_tab_var *var, int sgn,
isl_int target, isl_int *tmp)
3479{
if (row_is_big(tab, var->index))
return 1;
isl_int_mul(*tmp, tab->mat->row[var->index][0], target)isl_sioimath_mul((*tmp), *(tab->mat->row[var->index]
[0]), *(target));
if (sgn > 0)
return isl_int_ge(tab->mat->row[var->index][1], *tmp)(isl_sioimath_cmp(*(tab->mat->row[var->index][1]), *
(*tmp)) >= 0);
else
return isl_int_le(tab->mat->row[var->index][1], *tmp)(isl_sioimath_cmp(*(tab->mat->row[var->index][1]), *
(*tmp)) <= 0);
3487}

3489/* Can variable "var" of "tab" attain the value "target" by
* pivoting up (if sgn > 0) or down (if sgn < 0)?
* If not, then pivot up [down] to the greatest [smallest]
* rational value.
* "tmp" has been initialized by the caller and can be used
* to perform local computations.
*
* If the variable is manifestly unbounded in the desired direction,
* then it can attain any value.
* Otherwise, it can be moved to a row.
* Continue pivoting until the target is reached.
* If no more pivoting can be performed, the maximal [minimal]
* rational value has been reached and the target cannot be reached.
* If the variable would be pivoted into a manifestly unbounded column,
* then the target can be reached.
*/
3505static isl_bool var_reaches(struct isl_tab *tab, struct isl_tab_var *var,
int sgn, isl_int target, isl_int *tmp)
3507{
int row, col;

if (sgn < 0 && min_is_manifestly_unbounded(tab, var))
return isl_bool_true;
if (sgn > 0 && max_is_manifestly_unbounded(tab, var))
return isl_bool_true;
if (to_row(tab, var, sgn) < 0)
return isl_bool_error;
while (!reached(tab, var, sgn, target, tmp)) {
find_pivot(tab, var, var, sgn, &row, &col);
if (row == -1)
	return isl_bool_false;
if (row == var->index)
	return isl_bool_true;
if (isl_tab_pivot(tab, row, col) < 0)
	return isl_bool_error;
}

return isl_bool_true;
3527}

3529/* Check if variable "var" of "tab" can only attain a single (integer)
* value, and, if so, add an equality constraint to fix the variable
* to this single value and store the result in "target".
* "target" and "tmp" have been initialized by the caller.
*
* Given the current sample value, round it down and check
* whether it is possible to attain a strictly smaller integer value.
* If so, the variable is not restricted to a single integer value.
* Otherwise, the search stops at the smallest rational value.
* Round up this value and check whether it is possible to attain
* a strictly greater integer value.
* If so, the variable is not restricted to a single integer value.
* Otherwise, the search stops at the greatest rational value.
* If rounding down this value yields a value that is different
* from rounding up the smallest rational value, then the variable
* cannot attain any integer value.  Mark the tableau empty.
* Otherwise, add an equality constraint that fixes the variable
* to the single integer value found.
*/
3548static isl_bool detect_constant_with_tmp(struct isl_tab *tab,
struct isl_tab_var *var, isl_int *target, isl_int *tmp)
3550{
isl_bool reached;
isl_vec *eq;
int pos;
isl_stat r;

get_rounded_sample_value(tab, var, -1, target);
isl_int_sub_ui(*target, *target, 1)isl_sioimath_sub_ui((*target), *(*target), 1);
reached = var_reaches(tab, var, -1, *target, tmp);
if (reached < 0 || reached)
return isl_bool_not(reached);
get_rounded_sample_value(tab, var, 1, target);
isl_int_add_ui(*target, *target, 1)isl_sioimath_add_ui((*target), *(*target), 1);
reached = var_reaches(tab, var, 1, *target, tmp);
if (reached < 0 || reached)
return isl_bool_not(reached);
get_rounded_sample_value(tab, var, -1, tmp);
isl_int_sub_ui(*target, *target, 1)isl_sioimath_sub_ui((*target), *(*target), 1);
if (isl_int_ne(*target, *tmp)(isl_sioimath_cmp(*(*target), *(*tmp)) != 0)) {
if (isl_tab_mark_empty(tab) < 0)
	return isl_bool_error;
return isl_bool_false;
}

if (isl_tab_extend_cons(tab, 1) < 0)
return isl_bool_error;
eq = isl_vec_alloc(isl_tab_get_ctx(tab), 1 + tab->n_var);
if (!eq)
return isl_bool_error;
pos = var - tab->var;
isl_seq_clr(eq->el + 1, tab->n_var);
isl_int_set_si(eq->el[1 + pos], -1)isl_sioimath_set_si((eq->el[1 + pos]), -1);
isl_int_set(eq->el[0], *target)isl_sioimath_set((eq->el[0]), *(*target));
r = isl_tab_add_eq(tab, eq->el);
isl_vec_free(eq);

return r < 0 ? isl_bool_error : isl_bool_true;
3587}

3589/* Check if variable "var" of "tab" can only attain a single (integer)
* value, and, if so, add an equality constraint to fix the variable
* to this single value and store the result in "value" (if "value"
* is not NULL).
*
* If the current sample value involves the big parameter,
* then the variable cannot have a fixed integer value.
* If the variable is already fixed to a single value by its row, then
* there is no need to add another equality constraint.
*
* Otherwise, allocate some temporary variables and continue
* with detect_constant_with_tmp.
*/
3602static isl_bool get_constant(struct isl_tab *tab, struct isl_tab_var *var,
isl_int *value)
3604{
isl_int target, tmp;
isl_bool is_cst;

if (var->is_row && row_is_big(tab, var->index))
return isl_bool_false;
is_cst = is_constant(tab, var, value);
if (is_cst < 0 || is_cst)
return is_cst;

if (!value)
isl_int_init(target)isl_sioimath_init((target));
isl_int_init(tmp)isl_sioimath_init((tmp));

is_cst = detect_constant_with_tmp(tab, var,
			    value ? value : &target, &tmp);

isl_int_clear(tmp)isl_sioimath_clear((tmp));
if (!value)
isl_int_clear(target)isl_sioimath_clear((target));

return is_cst;
3626}

3628/* Check if variable "var" of "tab" can only attain a single (integer)
* value, and, if so, add an equality constraint to fix the variable
* to this single value and store the result in "value" (if "value"
* is not NULL).
*
* For rational tableaus, nothing needs to be done.
*/
3635isl_bool isl_tab_is_constant(struct isl_tab *tab, int var, isl_int *value)
3636{
if (!tab)
return isl_bool_error;
if (var < 0 || var >= tab->n_var)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "position out of bounds", "polly/lib/External/isl/isl_tab.c"
, 3641); return isl_bool_error; } while (0)
	"position out of bounds", return isl_bool_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "position out of bounds", "polly/lib/External/isl/isl_tab.c"
, 3641); return isl_bool_error; } while (0);
if (tab->rational)
return isl_bool_false;

return get_constant(tab, &tab->var[var], value);
3646}

3648/* Check if any of the variables of "tab" can only attain a single (integer)
* value, and, if so, add equality constraints to fix those variables
* to these single values.
*
* For rational tableaus, nothing needs to be done.
*/
3654isl_stat isl_tab_detect_constants(struct isl_tab *tab)
3655{
int i;

if (!tab)
return isl_stat_error;
if (tab->rational)
return isl_stat_ok;

for (i = 0; i < tab->n_var; ++i) {
if (get_constant(tab, &tab->var[i], NULL((void*)0)) < 0)
	return isl_stat_error;
}

return isl_stat_ok;
3669}

3671/* Take a snapshot of the tableau that can be restored by a call to
* isl_tab_rollback.
*/
3674struct isl_tab_undo *isl_tab_snap(struct isl_tab *tab)
3675{
if (!tab)
return NULL((void*)0);
tab->need_undo = 1;
return tab->top;
3680}

3682/* Does "tab" need to keep track of undo information?
* That is, was a snapshot taken that may need to be restored?
*/
3685isl_bool isl_tab_need_undo(struct isl_tab *tab)
3686{
if (!tab)
return isl_bool_error;

return isl_bool_ok(tab->need_undo);
3691}

3693/* Remove all tracking of undo information from "tab", invalidating
* any snapshots that may have been taken of the tableau.
* Since all snapshots have been invalidated, there is also
* no need to start keeping track of undo information again.
*/
3698void isl_tab_clear_undo(struct isl_tab *tab)
3699{
if (!tab)
return;

free_undo(tab);
tab->need_undo = 0;
3705}

3707/* Undo the operation performed by isl_tab_relax.
*/
3709static isl_stat unrelax(struct isl_tab *tab, struct isl_tab_var *var)
WARN_UNUSED__attribute__((__warn_unused_result__));
3711static isl_stat unrelax(struct isl_tab *tab, struct isl_tab_var *var)
3712{
unsigned off = 2 + tab->M;

if (!var->is_row && !max_is_manifestly_unbounded(tab, var))
if (to_row(tab, var, 1) < 0)
	return isl_stat_error;

if (var->is_row) {
isl_int_sub(tab->mat->row[var->index][1],isl_sioimath_sub((tab->mat->row[var->index][1]), *(tab
->mat->row[var->index][1]), *(tab->mat->row[var
->index][0]))
    tab->mat->row[var->index][1], tab->mat->row[var->index][0])isl_sioimath_sub((tab->mat->row[var->index][1]), *(tab
->mat->row[var->index][1]), *(tab->mat->row[var
->index][0]));
if (var->is_nonneg) {
	int sgn = restore_row(tab, var);
	isl_assert(tab->mat->ctx, sgn >= 0,do { if (sgn >= 0) break; do { isl_handle_error(tab->mat
->ctx, isl_error_unknown, "Assertion \"" "sgn >= 0" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 3725); return isl_stat_error
; } while (0); } while (0)
		return isl_stat_error)do { if (sgn >= 0) break; do { isl_handle_error(tab->mat
->ctx, isl_error_unknown, "Assertion \"" "sgn >= 0" "\" failed"
, "polly/lib/External/isl/isl_tab.c", 3725); return isl_stat_error
; } while (0); } while (0);
}
} else {
int i;

for (i = 0; i < tab->n_row; ++i) {
	if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index
])) == 0))
		continue;
	isl_int_add(tab->mat->row[i][1], tab->mat->row[i][1],isl_sioimath_add((tab->mat->row[i][1]), *(tab->mat->
row[i][1]), *(tab->mat->row[i][off + var->index]))
	    tab->mat->row[i][off + var->index])isl_sioimath_add((tab->mat->row[i][1]), *(tab->mat->
row[i][1]), *(tab->mat->row[i][off + var->index]));
}

}

return isl_stat_ok;
3740}

3742/* 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.
*/
3747static isl_stat ununrestrict(struct isl_tab *tab, struct isl_tab_var *var)
3748{
var->is_nonneg = 1;

if (var->is_row && restore_row(tab, var) < -1)
return isl_stat_error;

return isl_stat_ok;
3755}

3757/* Unmark the last redundant row in "tab" as being redundant.
* This undoes part of the modifications performed by isl_tab_mark_redundant.
* In particular, remove the redundant mark and make
* sure the sample value respects the constraint again.
* A variable that is marked non-negative by isl_tab_mark_redundant
* is covered by a separate undo record.
*/
3764static isl_stat restore_last_redundant(struct isl_tab *tab)
3765{
struct isl_tab_var *var;

if (tab->n_redundant < 1)
isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "no redundant rows", "polly/lib/External/isl/isl_tab.c", 3770
); return isl_stat_error; } while (0)
	"no redundant rows", return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "no redundant rows", "polly/lib/External/isl/isl_tab.c", 3770
); return isl_stat_error; } while (0);

var = isl_tab_var_from_row(tab, tab->n_redundant - 1);
var->is_redundant = 0;
tab->n_redundant--;
restore_row(tab, var);

return isl_stat_ok;
3778}

3780static isl_stat perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo)
WARN_UNUSED__attribute__((__warn_unused_result__));
3782static isl_stat perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo)
3783{
struct isl_tab_var *var = var_from_index(tab, undo->u.var_index);
switch (undo->type) {
case isl_tab_undo_nonneg:
var->is_nonneg = 0;
break;
case isl_tab_undo_redundant:
if (!var->is_row || var->index != tab->n_redundant - 1)
	isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "not undoing last redundant row", "polly/lib/External/isl/isl_tab.c"
, 3793); return isl_stat_error; } while (0)
		"not undoing last redundant row",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "not undoing last redundant row", "polly/lib/External/isl/isl_tab.c"
, 3793); return isl_stat_error; } while (0)
		return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal
, "not undoing last redundant row", "polly/lib/External/isl/isl_tab.c"
, 3793); return isl_stat_error; } while (0);
return restore_last_redundant(tab);
case isl_tab_undo_freeze:
var->frozen = 0;
break;
case isl_tab_undo_zero:
var->is_zero = 0;
if (!var->is_row)
	tab->n_dead--;
break;
case isl_tab_undo_allocate:
if (undo->u.var_index >= 0) {
	isl_assert(tab->mat->ctx, !var->is_row,do { if (!var->is_row) break; do { isl_handle_error(tab->
mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_row"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 3806); return
 isl_stat_error; } while (0); } while (0)
		return isl_stat_error)do { if (!var->is_row) break; do { isl_handle_error(tab->
mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_row"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 3806); return
 isl_stat_error; } while (0); } while (0);
	return drop_col(tab, var->index);
}
if (!var->is_row) {
	if (!max_is_manifestly_unbounded(tab, var)) {
		if (to_row(tab, var, 1) < 0)
			return isl_stat_error;
	} else if (!min_is_manifestly_unbounded(tab, var)) {
		if (to_row(tab, var, -1) < 0)
			return isl_stat_error;
	} else
		if (to_row(tab, var, 0) < 0)
			return isl_stat_error;
}
return drop_row(tab, var->index);
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,do { isl_handle_error(tab->mat->ctx, isl_error_internal
, "perform_undo_var called on invalid undo record", "polly/lib/External/isl/isl_tab.c"
, 3828); return isl_stat_error; } while (0)
	"perform_undo_var called on invalid undo record",do { isl_handle_error(tab->mat->ctx, isl_error_internal
, "perform_undo_var called on invalid undo record", "polly/lib/External/isl/isl_tab.c"
, 3828); return isl_stat_error; } while (0)
	return isl_stat_error)do { isl_handle_error(tab->mat->ctx, isl_error_internal
, "perform_undo_var called on invalid undo record", "polly/lib/External/isl/isl_tab.c"
, 3828); return isl_stat_error; } while (0);
}

return isl_stat_ok;
3832}

3834/* Restore all rows that have been marked redundant by isl_tab_mark_redundant
* and that have been preserved in the tableau.
* Note that isl_tab_mark_redundant may also have marked some variables
* as being non-negative before marking them redundant.  These need
* to be removed as well as otherwise some constraints could end up
* getting marked redundant with respect to the variable.
*/
3841isl_stat isl_tab_restore_redundant(struct isl_tab *tab)
3842{
if (!tab)
return isl_stat_error;

if (tab->need_undo)
isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "manually restoring redundant constraints " "interferes with undo history"
, "polly/lib/External/isl/isl_tab.c", 3850); return isl_stat_error
; } while (0)
	"manually restoring redundant constraints "do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "manually restoring redundant constraints " "interferes with undo history"
, "polly/lib/External/isl/isl_tab.c", 3850); return isl_stat_error
; } while (0)
	"interferes with undo history",do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "manually restoring redundant constraints " "interferes with undo history"
, "polly/lib/External/isl/isl_tab.c", 3850); return isl_stat_error
; } while (0)
	return isl_stat_error)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid
, "manually restoring redundant constraints " "interferes with undo history"
, "polly/lib/External/isl/isl_tab.c", 3850); return isl_stat_error
; } while (0);

while (tab->n_redundant > 0) {
if (tab->row_var[tab->n_redundant - 1] >= 0) {
	struct isl_tab_var *var;

	var = isl_tab_var_from_row(tab, tab->n_redundant - 1);
	var->is_nonneg = 0;
}
restore_last_redundant(tab);
}
return isl_stat_ok;
3862}

3864/* Undo the addition of an integer division to the basic map representation
* of "tab" in position "pos".
*/
3867static isl_stat drop_bmap_div(struct isl_tab *tab, int pos)
3868{
int off;
isl_size n_div;

n_div = isl_basic_map_dim(tab->bmap, isl_dim_div);
if (n_div < 0)
return isl_stat_error;
off = tab->n_var - n_div;
tab->bmap = isl_basic_map_drop_div(tab->bmap, pos - off);
if (!tab->bmap)
return isl_stat_error;
if (tab->samples) {
tab->samples = isl_mat_drop_cols(tab->samples, 1 + pos, 1);
if (!tab->samples)
	return isl_stat_error;
}

return isl_stat_ok;
3886}

3888/* Restore the tableau to the state where the basic variables
* are those in "col_var".
* We first construct a list of variables that are currently in
* the basis, but shouldn't.  Then we iterate over all variables
* that should be in the basis and for each one that is currently
* not in the basis, we exchange it with one of the elements of the
* list constructed before.
* We can always find an appropriate variable to pivot with because
* the current basis is mapped to the old basis by a non-singular
* matrix and so we can never end up with a zero row.
*/
3899static int restore_basis(struct isl_tab *tab, int *col_var)
3900{
int i, j;
int n_extra = 0;
int *extra = NULL((void*)0);	/* current columns that contain bad stuff */
unsigned off = 2 + tab->M;

extra = isl_alloc_array(tab->mat->ctx, int, tab->n_col)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->n_col
)*sizeof(int)));
if (tab->n_col && !extra)
goto error;
for (i = 0; i < tab->n_col; ++i) {
for (j = 0; j < tab->n_col; ++j)
	if (tab->col_var[i] == col_var[j])
		break;
if (j < tab->n_col)
	continue;
extra[n_extra++] = i;
}
for (i = 0; i < tab->n_col && n_extra > 0; ++i) {
struct isl_tab_var *var;
int row;

for (j = 0; j < tab->n_col; ++j)
	if (col_var[i] == tab->col_var[j])
		break;
if (j < tab->n_col)
	continue;
var = var_from_index(tab, col_var[i]);
row = var->index;
for (j = 0; j < n_extra; ++j)
	if (!isl_int_is_zero(tab->mat->row[row][off+extra[j]])(isl_sioimath_sgn(*(tab->mat->row[row][off+extra[j]])) ==
 0))
		break;
isl_assert(tab->mat->ctx, j < n_extra, goto error)do { if (j < n_extra) break; do { isl_handle_error(tab->
mat->ctx, isl_error_unknown, "Assertion \"" "j < n_extra"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 3931); goto
 error; } while (0); } while (0);
if (isl_tab_pivot(tab, row, extra[j]) < 0)
	goto error;
extra[j] = extra[--n_extra];
}

free(extra);
return 0;
3939error:
free(extra);
return -1;
3942}

3944/* Remove all samples with index n or greater, i.e., those samples
* that were added since we saved this number of samples in
* isl_tab_save_samples.
*/
3948static void drop_samples_since(struct isl_tab *tab, int n)
3949{
int i;

for (i = tab->n_sample - 1; i >= 0 && tab->n_sample > n; --i) {
if (tab->sample_index[i] < n)
	continue;

if (i != tab->n_sample - 1) {
	int t = tab->sample_index[tab->n_sample-1];
	tab->sample_index[tab->n_sample-1] = tab->sample_index[i];
	tab->sample_index[i] = t;
	isl_mat_swap_rows(tab->samples, tab->n_sample-1, i);
}
tab->n_sample--;
}
3964}

3966static isl_stat perform_undo(struct isl_tab *tab, struct isl_tab_undo *undo)
WARN_UNUSED__attribute__((__warn_unused_result__));
3968static isl_stat perform_undo(struct isl_tab *tab, struct isl_tab_undo *undo)
3969{
switch (undo->type) {
case isl_tab_undo_rational:
tab->rational = 0;
break;
case isl_tab_undo_empty:
tab->empty = 0;
break;
case isl_tab_undo_nonneg:
case isl_tab_undo_redundant:
case isl_tab_undo_freeze:
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:
tab->bmap = isl_basic_map_free_equality(tab->bmap, 1);
return tab->bmap ? isl_stat_ok : isl_stat_error;
case isl_tab_undo_bmap_ineq:
tab->bmap = isl_basic_map_free_inequality(tab->bmap, 1);
return tab->bmap ? isl_stat_ok : isl_stat_error;
case isl_tab_undo_bmap_div:
return drop_bmap_div(tab, undo->u.var_index);
case isl_tab_undo_saved_basis:
if (restore_basis(tab, undo->u.col_var) < 0)
	return isl_stat_error;
break;
case isl_tab_undo_drop_sample:
tab->n_outside--;
break;
case isl_tab_undo_saved_samples:
drop_samples_since(tab, undo->u.n);
break;
case isl_tab_undo_callback:
return undo->u.callback->run(undo->u.callback);
default:
isl_assert(tab->mat->ctx, 0, return isl_stat_error)do { if (0) break; do { isl_handle_error(tab->mat->ctx,
 isl_error_unknown, "Assertion \"" "0" "\" failed", "polly/lib/External/isl/isl_tab.c"
, 4006); return isl_stat_error; } while (0); } while (0);
}
return isl_stat_ok;
4009}

4011/* Return the tableau to the state it was in when the snapshot "snap"
* was taken.
*/
4014isl_stat isl_tab_rollback(struct isl_tab *tab, struct isl_tab_undo *snap)
4015{
struct isl_tab_undo *undo, *next;

if (!tab)
return isl_stat_error;

tab->in_undo = 1;
for (undo = tab->top; undo && undo != &tab->bottom; undo = next) {
next = undo->next;
if (undo == snap)
	break;
if (perform_undo(tab, undo) < 0) {
	tab->top = undo;
	free_undo(tab);
	tab->in_undo = 0;
	return isl_stat_error;
}
free_undo_record(undo);
}
tab->in_undo = 0;
tab->top = undo;
if (!undo)
return isl_stat_error;
return isl_stat_ok;
4039}

4041/* The given row "row" represents an inequality violated by all
* points in the tableau.  Check for some special cases of such
* separating constraints.
* In particular, if the row has been reduced to the constant -1,
* then we know the inequality is adjacent (but opposite) to
* an equality in the tableau.
* If the row has been reduced to r = c*(-1 -r'), with r' an inequality
* of the tableau and c a positive constant, then the inequality
* is adjacent (but opposite) to the inequality r'.
*/
4051static enum isl_ineq_type separation_type(struct isl_tab *tab, unsigned row)
4052{
int pos;
unsigned off = 2 + tab->M;

if (tab->rational)
return isl_ineq_separate;

if (!isl_int_is_one(tab->mat->row[row][0])(isl_sioimath_cmp_si(*(tab->mat->row[row][0]), 1) == 0))
return isl_ineq_separate;

pos = isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead,
			tab->n_col - tab->n_dead);
if (pos == -1) {
if (isl_int_is_negone(tab->mat->row[row][1])(isl_sioimath_cmp_si(*(tab->mat->row[row][1]), -1) == 0
))
	return isl_ineq_adj_eq;
else
	return isl_ineq_separate;
}

if (!isl_int_eq(tab->mat->row[row][1],(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat
->row[row][off + tab->n_dead + pos])) == 0)
	tab->mat->row[row][off + tab->n_dead + pos])(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat
->row[row][off + tab->n_dead + pos])) == 0))
return isl_ineq_separate;

pos = isl_seq_first_non_zero(
	tab->mat->row[row] + off + tab->n_dead + pos + 1,
	tab->n_col - tab->n_dead - pos - 1);

return pos == -1 ? isl_ineq_adj_ineq : isl_ineq_separate;
4080}

4082/* Check the effect of inequality "ineq" on the tableau "tab".
* The result may be
*	isl_ineq_redundant:	satisfied by all points in the tableau
*	isl_ineq_separate:	satisfied by no point in the tableau
*	isl_ineq_cut:		satisfied by some by not all points
*	isl_ineq_adj_eq:	adjacent to an equality
*	isl_ineq_adj_ineq:	adjacent to an inequality.
*/
4090enum isl_ineq_type isl_tab_ineq_type(struct isl_tab *tab, isl_int *ineq)
4091{
enum isl_ineq_type type = isl_ineq_error;
struct isl_tab_undo *snap = NULL((void*)0);
int con;
int row;

if (!tab)
return isl_ineq_error;

if (isl_tab_extend_cons(tab, 1) < 0)
return isl_ineq_error;

snap = isl_tab_snap(tab);

con = isl_tab_add_row(tab, ineq);
if (con < 0)
goto error;

row = tab->con[con].index;
if (isl_tab_row_is_redundant(tab, row))
type = isl_ineq_redundant;
else if (isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0) &&
 (tab->rational ||
    isl_int_abs_ge(tab->mat->row[row][1],(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab->
mat->row[row][0])) >= 0)
		   tab->mat->row[row][0])(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab->
mat->row[row][0])) >= 0))) {
int nonneg = at_least_zero(tab, &tab->con[con]);
if (nonneg < 0)
	goto error;
if (nonneg)
	type = isl_ineq_cut;
else
	type = separation_type(tab, row);
} else {
int red = con_is_redundant(tab, &tab->con[con]);
if (red < 0)
	goto error;
if (!red)
	type = isl_ineq_cut;
else
	type = isl_ineq_redundant;
}

if (isl_tab_rollback(tab, snap))
return isl_ineq_error;
return type;
4136error:
return isl_ineq_error;
4138}

4140isl_stat isl_tab_track_bmap(struct isl_tab *tab, __isl_take isl_basic_map *bmap)
4141{
bmap = isl_basic_map_cow(bmap);
if (!tab || !bmap)
goto error;

if (tab->empty) {
bmap = isl_basic_map_set_to_empty(bmap);
if (!bmap)
	goto error;
tab->bmap = bmap;
return isl_stat_ok;
}

isl_assert(tab->mat->ctx, tab->n_eq == bmap->n_eq, goto error)do { if (tab->n_eq == bmap->n_eq) break; do { isl_handle_error
(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_eq == bmap->n_eq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 4154); goto
 error; } while (0); } while (0);
isl_assert(tab->mat->ctx,do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break
; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 4156); goto
 error; } while (0); } while (0)
    tab->n_con == bmap->n_eq + bmap->n_ineq, goto error)do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break
; do { isl_handle_error(tab->mat->ctx, isl_error_unknown
, "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq"
 "\" failed", "polly/lib/External/isl/isl_tab.c", 4156); goto
 error; } while (0); } while (0);

tab->bmap = bmap;

return isl_stat_ok;
4161error:
isl_basic_map_free(bmap);
return isl_stat_error;
4164}

4166isl_stat isl_tab_track_bset(struct isl_tab *tab, __isl_take isl_basic_setisl_basic_map *bset)
4167{
return isl_tab_track_bmap(tab, bset_to_bmap(bset));
4169}

4171__isl_keep isl_basic_setisl_basic_map *isl_tab_peek_bset(struct isl_tab *tab)
4172{
if (!tab)
return NULL((void*)0);

return bset_from_bmap(tab->bmap);
4177}

4179static void isl_tab_print_internal(__isl_keep struct isl_tab *tab,
FILE *out, int indent)
4181{
unsigned r, c;
int i;

if (!tab) {
fprintf(out, "%*snull tab\n", indent, "")__fprintf_chk (out, 2 - 1, "%*snull tab\n", indent, "");
return;
}
fprintf(out, "%*sn_redundant: %d, n_dead: %d", indent, "",__fprintf_chk (out, 2 - 1, "%*sn_redundant: %d, n_dead: %d", indent
, "", tab->n_redundant, tab->n_dead)
tab->n_redundant, tab->n_dead)__fprintf_chk (out, 2 - 1, "%*sn_redundant: %d, n_dead: %d", indent
, "", tab->n_redundant, tab->n_dead);
if (tab->rational)
fprintf(out, ", rational")__fprintf_chk (out, 2 - 1, ", rational");
if (tab->empty)
fprintf(out, ", empty")__fprintf_chk (out, 2 - 1, ", empty");
fprintf(out, "\n")__fprintf_chk (out, 2 - 1, "\n");
fprintf(out, "%*s[", indent, "")__fprintf_chk (out, 2 - 1, "%*s[", indent, "");
for (i = 0; i < tab->n_var; ++i) {
if (i)
	fprintf(out, (i == tab->n_param ||__fprintf_chk (out, 2 - 1, (i == tab->n_param || i == tab->
n_var - tab->n_div) ? "; " : ", ")
		      i == tab->n_var - tab->n_div) ? "; "__fprintf_chk (out, 2 - 1, (i == tab->n_param || i == tab->
n_var - tab->n_div) ? "; " : ", ")
						    : ", ")__fprintf_chk (out, 2 - 1, (i == tab->n_param || i == tab->
n_var - tab->n_div) ? "; " : ", ");
fprintf(out, "%c%d%s", tab->var[i].is_row ? 'r' : 'c',__fprintf_chk (out, 2 - 1, "%c%d%s", tab->var[i].is_row ? 'r'
 : 'c', tab->var[i].index, tab->var[i].is_zero ? " [=0]"
 : tab->var[i].is_redundant ? " [R]" : "")
			tab->var[i].index,__fprintf_chk (out, 2 - 1, "%c%d%s", tab->var[i].is_row ? 'r'
 : 'c', tab->var[i].index, tab->var[i].is_zero ? " [=0]"
 : tab->var[i].is_redundant ? " [R]" : "")
			tab->var[i].is_zero ? " [=0]" :__fprintf_chk (out, 2 - 1, "%c%d%s", tab->var[i].is_row ? 'r'
 : 'c', tab->var[i].index, tab->var[i].is_zero ? " [=0]"
 : tab->var[i].is_redundant ? " [R]" : "")
			tab->var[i].is_redundant ? " [R]" : "")__fprintf_chk (out, 2 - 1, "%c%d%s", tab->var[i].is_row ? 'r'
 : 'c', tab->var[i].index, tab->var[i].is_zero ? " [=0]"
 : tab->var[i].is_redundant ? " [R]" : "");
}
fprintf(out, "]\n")__fprintf_chk (out, 2 - 1, "]\n");
fprintf(out, "%*s[", indent, "")__fprintf_chk (out, 2 - 1, "%*s[", indent, "");
for (i = 0; i < tab->n_con; ++i) {
if (i)
	fprintf(out, ", ")__fprintf_chk (out, 2 - 1, ", ");
fprintf(out, "%c%d%s", tab->con[i].is_row ? 'r' : 'c',__fprintf_chk (out, 2 - 1, "%c%d%s", tab->con[i].is_row ? 'r'
 : 'c', tab->con[i].index, tab->con[i].is_zero ? " [=0]"
 : tab->con[i].is_redundant ? " [R]" : "")
			tab->con[i].index,__fprintf_chk (out, 2 - 1, "%c%d%s", tab->con[i].is_row ? 'r'
 : 'c', tab->con[i].index, tab->con[i].is_zero ? " [=0]"
 : tab->con[i].is_redundant ? " [R]" : "")
			tab->con[i].is_zero ? " [=0]" :__fprintf_chk (out, 2 - 1, "%c%d%s", tab->con[i].is_row ? 'r'
 : 'c', tab->con[i].index, tab->con[i].is_zero ? " [=0]"
 : tab->con[i].is_redundant ? " [R]" : "")
			tab->con[i].is_redundant ? " [R]" : "")__fprintf_chk (out, 2 - 1, "%c%d%s", tab->con[i].is_row ? 'r'
 : 'c', tab->con[i].index, tab->con[i].is_zero ? " [=0]"
 : tab->con[i].is_redundant ? " [R]" : "");
}
fprintf(out, "]\n")__fprintf_chk (out, 2 - 1, "]\n");
fprintf(out, "%*s[", indent, "")__fprintf_chk (out, 2 - 1, "%*s[", indent, "");
for (i = 0; i < tab->n_row; ++i) {
const char *sign = "";
if (i)
	fprintf(out, ", ")__fprintf_chk (out, 2 - 1, ", ");
if (tab->row_sign) {
	if (tab->row_sign[i] == isl_tab_row_unknown)
		sign = "?";
	else if (tab->row_sign[i] == isl_tab_row_neg)
		sign = "-";
	else if (tab->row_sign[i] == isl_tab_row_pos)
		sign = "+";
	else
		sign = "+-";
}
fprintf(out, "r%d: %d%s%s", i, tab->row_var[i],__fprintf_chk (out, 2 - 1, "r%d: %d%s%s", i, tab->row_var[
i], isl_tab_var_from_row(tab, i)->is_nonneg ? " [>=0]" :
 "", sign)
    isl_tab_var_from_row(tab, i)->is_nonneg ? " [>=0]" : "", sign)__fprintf_chk (out, 2 - 1, "r%d: %d%s%s", i, tab->row_var[
i], isl_tab_var_from_row(tab, i)->is_nonneg ? " [>=0]" :
 "", sign);
}
fprintf(out, "]\n")__fprintf_chk (out, 2 - 1, "]\n");
fprintf(out, "%*s[", indent, "")__fprintf_chk (out, 2 - 1, "%*s[", indent, "");
for (i = 0; i < tab->n_col; ++i) {
if (i)
	fprintf(out, ", ")__fprintf_chk (out, 2 - 1, ", ");
fprintf(out, "c%d: %d%s", i, tab->col_var[i],__fprintf_chk (out, 2 - 1, "c%d: %d%s", i, tab->col_var[i]
, var_from_col(tab, i)->is_nonneg ? " [>=0]" : "")
    var_from_col(tab, i)->is_nonneg ? " [>=0]" : "")__fprintf_chk (out, 2 - 1, "c%d: %d%s", i, tab->col_var[i]
, var_from_col(tab, i)->is_nonneg ? " [>=0]" : "");
}
fprintf(out, "]\n")__fprintf_chk (out, 2 - 1, "]\n");
r = tab->mat->n_row;
tab->mat->n_row = tab->n_row;
c = tab->mat->n_col;
tab->mat->n_col = 2 + tab->M + tab->n_col;
isl_mat_print_internal(tab->mat, out, indent);
tab->mat->n_row = r;
tab->mat->n_col = c;
if (tab->bmap)
isl_basic_map_print_internal(tab->bmap, out, indent);
4254}

4256void isl_tab_dump(__isl_keep struct isl_tab *tab)
4257{
isl_tab_print_internal(tab, stderrstderr, 0);
4259}

←

/build/source/polly/lib/External/isl/isl_int_sioimath.h

1/*
* Copyright 2015 INRIA Paris-Rocquencourt
*
* Use of this software is governed by the MIT license
*
* Written by Michael Kruse, INRIA Paris-Rocquencourt,
* Domaine de Voluceau, Rocquenqourt, B.P. 105,
* 78153 Le Chesnay Cedex France
*/
10#ifndef ISL_INT_SIOIMATH_H
11#define ISL_INT_SIOIMATH_H

13#include <inttypes.h>
14#include <limits.h>
15#include <stdint.h>
16#include <stdlib.h>

18#include <isl_imath.h>
19#include <isl/hash.h>

21#define ARRAY_SIZE(array)(sizeof(array)/sizeof(*array)) (sizeof(array)/sizeof(*array))

23/* Visual Studio before VS2015 does not support the inline keyword when
* compiling in C mode because it was introduced in C99 which it does not
* officially support.  Instead, it has a proprietary extension using __inline.
*/
27#if defined(_MSC_VER) && (_MSC_VER < 1900)
28#define inline __inline
29#endif

31/* The type to represent integers optimized for small values. It is either a
* pointer to an mp_int ( = mpz_t*; big representation) or an int32_t (small
* represenation) with a discriminator at the least significant bit. In big
* representation it will be always zero because of heap alignment. It is set
* to 1 for small representation and use the 32 most significant bits for the
* int32_t.
*
* Structure on 64 bit machines, with 8-byte aligment (3 bits):
*
* Big representation:
* MSB                                                          LSB
* |------------------------------------------------------------000
* |                            mpz_t*                            |
* |                           != NULL                            |
*
* Small representation:
* MSB                           32                             LSB
* |------------------------------|00000000000000000000000000000001
* |          int32_t             |
* |  2147483647 ... -2147483647  |
*                                                                ^
*                                                                |
*                                                        discriminator bit
*
* On 32 bit machines isl_sioimath type is blown up to 8 bytes, i.e.
* isl_sioimath is guaranteed to be at least 8 bytes. This is to ensure the
* int32_t can be hidden in that type without data loss. In the future we might
* optimize this to use 31 hidden bits in a 32 bit pointer. We may also use 63
* bits on 64 bit machines, but this comes with the cost of additional overflow
* checks because there is no standardized 128 bit integer we could expand to.
*
* We use native integer types and avoid union structures to avoid assumptions
* on the machine's endianness.
*
* This implementation makes the following assumptions:
* - long can represent any int32_t
* - mp_small is signed long
* - mp_usmall is unsigned long
* - adresses returned by malloc are aligned to 2-byte boundaries (leastmost
*   bit is zero)
*/
72#if UINT64_MAX(18446744073709551615UL) > UINTPTR_MAX(18446744073709551615UL)
73typedef uint64_t isl_sioimath;
74#else
75typedef uintptr_t isl_sioimath;
76#endif

78/* The negation of the smallest possible number in int32_t, INT32_MIN
* (0x80000000u, -2147483648), cannot be represented in an int32_t, therefore
* every operation that may produce this value needs to special-case it.
* The operations are:
* abs(INT32_MIN)
* -INT32_MIN   (negation)
* -1 * INT32_MIN (multiplication)
* INT32_MIN/-1 (any division: divexact, fdiv, cdiv, tdiv)
* To avoid checking these cases, we exclude INT32_MIN from small
* representation.
*/
89#define ISL_SIOIMATH_SMALL_MIN(-(2147483647)) (-INT32_MAX(2147483647))

91/* Largest possible number in small representation */
92#define ISL_SIOIMATH_SMALL_MAX(2147483647) INT32_MAX(2147483647)

94/* Used for function parameters the function modifies. */
95typedef isl_sioimath *isl_sioimath_ptr;

97/* Used for function parameters that are read-only. */
98typedef isl_sioimath isl_sioimath_src;

100/* Return whether the argument is stored in small representation.
*/
102inline int isl_sioimath_is_small(isl_sioimath val)
103{
return val & 0x00000001;
105}

107/* Return whether the argument is stored in big representation.
*/
109inline int isl_sioimath_is_big(isl_sioimath val)
110{
return !isl_sioimath_is_small(val);
112}

114/* Get the number of an isl_int in small representation. Result is undefined if
* val is not stored in that format.
*/
117inline int32_t isl_sioimath_get_small(isl_sioimath val)
118{
return val >> 32;
120}

122/* Get the number of an in isl_int in big representation. Result is undefined if
* val is not stored in that format.
*/
125inline mp_int isl_sioimath_get_big(isl_sioimath val)
126{
return (mp_int)(uintptr_t) val;
128}

130/* Return 1 if val is stored in small representation and store its value to
* small. We rely on the compiler to optimize the isl_sioimath_get_small such
* that the shift is moved into the branch that executes in case of small
* representation. If there is no such branch, then a single shift is still
* cheaper than introducing branching code.
*/
136inline int isl_sioimath_decode_small(isl_sioimath val, int32_t *small)
137{
*small = isl_sioimath_get_small(val);
return isl_sioimath_is_small(val);
140}

142/* Return 1 if val is stored in big representation and store its value to big.
*/
144inline int isl_sioimath_decode_big(isl_sioimath val, mp_int *big)
145{
*big = isl_sioimath_get_big(val);
return isl_sioimath_is_big(val);
148}

150/* Encode a small representation into an isl_int.
*/
152inline isl_sioimath isl_sioimath_encode_small(int32_t val)
153{
return ((isl_sioimath) val) << 32 | 0x00000001;
155}

157/* Encode a big representation.
*/
159inline isl_sioimath isl_sioimath_encode_big(mp_int val)
160{
return (isl_sioimath)(uintptr_t) val;
162}

164/* A common situation is to call an IMath function with at least one argument
* that is currently in small representation or an integer parameter, i.e. a big
* representation of the same number is required. Promoting the original
* argument comes with multiple problems, such as modifying a read-only
* argument, the responsibility of deallocation and the execution cost. Instead,
* we make a copy by 'faking' the IMath internal structure.
*
* We reserve the maximum number of required digits on the stack to avoid heap
* allocations.
*
* mp_digit can be uint32_t or uint16_t. This code must work for little and big
* endian digits. The structure for an uint64_t argument and 32-bit mp_digits is
* sketched below.
*
* |----------------------------|
*            uint64_t
*
* |-------------||-------------|
*    mp_digit        mp_digit
*    digits[1]       digits[0]
* Most sig digit  Least sig digit
*/
186typedef struct {
mpz_t big;
mp_digit digits[(sizeof(uintmax_t) + sizeof(mp_digit) - 1) /
               sizeof(mp_digit)];
190} isl_sioimath_scratchspace_t;

192/* Convert a native integer to IMath's digit representation. A native integer
* might be big- or little endian, but IMath always stores the least significant
* digit in the lowest array indices.  memcpy therefore is not possible.
*
* We also have to consider that long and mp_digit can be of different sizes,
* depending on the compiler (LP64, LLP64) and IMath's USE_64BIT_WORDS. This
* macro should work for all of them.
*
* "used" is set to the number of written digits. It must be minimal (IMath
* checks zeroness using the used field), but always at least one.  Also note
* that the result of num>>(sizeof(num)*CHAR_BIT) is undefined.
*/
204#define ISL_SIOIMATH_TO_DIGITS(num, digits, used)do { int i = 0; do { (digits)[i] = ((num) >> (sizeof(mp_digit
) * 8 * i)); i += 1; if (i >= (sizeof(num) + sizeof(mp_digit
) - 1) / sizeof(mp_digit)) break; if (((num) >> (sizeof
(mp_digit) * 8 * i)) == 0) break; } while (1); (used) = i; } while
 (0)                              \
do {                                                                   \
int i = 0;                                                     \
do {                                                           \
	(digits)[i] =                                          \
	    ((num) >> (sizeof(mp_digit) * CHAR_BIT8 * i));      \
	i += 1;                                                \
	if (i >= (sizeof(num) + sizeof(mp_digit) - 1) /        \
	             sizeof(mp_digit))                         \
		break;                                         \
	if (((num) >> (sizeof(mp_digit) * CHAR_BIT8 * i)) == 0) \
		break;                                         \
} while (1);                                                   \
(used) = i;                                                    \
} while (0)

220inline void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits,
mp_size *used)
222{
ISL_SIOIMATH_TO_DIGITS(num, digits, *used)do { int i = 0; do { (digits)[i] = ((num) >> (sizeof(mp_digit
) * 8 * i)); i += 1; if (i >= (sizeof(num) + sizeof(mp_digit
) - 1) / sizeof(mp_digit)) break; if (((num) >> (sizeof
(mp_digit) * 8 * i)) == 0) break; } while (1); (*used) = i; }
 while (0);
224}

226inline void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits,
mp_size *used)
228{
ISL_SIOIMATH_TO_DIGITS(num, digits, *used)do { int i = 0; do { (digits)[i] = ((num) >> (sizeof(mp_digit
) * 8 * i)); i += 1; if (i >= (sizeof(num) + sizeof(mp_digit
) - 1) / sizeof(mp_digit)) break; if (((num) >> (sizeof
(mp_digit) * 8 * i)) == 0) break; } while (1); (*used) = i; }
 while (0);
230}

232inline void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits,
mp_size *used)
234{
ISL_SIOIMATH_TO_DIGITS(num, digits, *used)do { int i = 0; do { (digits)[i] = ((num) >> (sizeof(mp_digit
) * 8 * i)); i += 1; if (i >= (sizeof(num) + sizeof(mp_digit
) - 1) / sizeof(mp_digit)) break; if (((num) >> (sizeof
(mp_digit) * 8 * i)) == 0) break; } while (1); (*used) = i; }
 while (0);
236}

238/* Get the IMath representation of an isl_int without modifying it.
* For the case it is not in big representation yet, pass some scratch space we
* can use to store the big representation in.
* In order to avoid requiring init and free on the scratch space, we directly
* modify the internal representation.
*
* The name derives from its indented use: getting the big representation of an
* input (src) argument.
*/
247inline mp_int isl_sioimath_bigarg_src(isl_sioimath arg,
isl_sioimath_scratchspace_t *scratch)
249{
mp_int big;
int32_t small;
uint32_t num;

if (isl_sioimath_decode_big(arg, &big))
return big;

small = isl_sioimath_get_small(arg);
scratch->big.digits = scratch->digits;
scratch->big.alloc = ARRAY_SIZE(scratch->digits)(sizeof(scratch->digits)/sizeof(*scratch->digits));
if (small >= 0) {
scratch->big.sign = MP_ZPOS;
num = small;
} else {
scratch->big.sign = MP_NEG;
num = -small;
}

isl_siomath_uint32_to_digits(num, scratch->digits, &scratch->big.used);
return &scratch->big;
270}

272/* Create a temporary IMath mp_int for a signed long.
*/
274inline mp_int isl_sioimath_siarg_src(signed long arg,
isl_sioimath_scratchspace_t *scratch)
276{
unsigned long num;

scratch->big.digits = scratch->digits;
scratch->big.alloc = ARRAY_SIZE(scratch->digits)(sizeof(scratch->digits)/sizeof(*scratch->digits));
if (arg >= 0) {
scratch->big.sign = MP_ZPOS;
num = arg;
} else {
scratch->big.sign = MP_NEG;
num = (arg == LONG_MIN(-9223372036854775807L -1L)) ? ((unsigned long) LONG_MAX9223372036854775807L) + 1 : -arg;
}

isl_siomath_ulong_to_digits(num, scratch->digits, &scratch->big.used);
return &scratch->big;
291}

293/* Create a temporary IMath mp_int for an int64_t.
*/
295inline mp_int isl_sioimath_si64arg_src(int64_t arg,
isl_sioimath_scratchspace_t *scratch)
297{
uint64_t num;

scratch->big.digits = scratch->digits;
scratch->big.alloc = ARRAY_SIZE(scratch->digits)(sizeof(scratch->digits)/sizeof(*scratch->digits));
if (arg >= 0) {
scratch->big.sign = MP_ZPOS;
num = arg;
} else {
scratch->big.sign = MP_NEG;
num = (arg == INT64_MIN(-9223372036854775807L -1)) ? ((uint64_t) INT64_MAX(9223372036854775807L)) + 1 : -arg;
}

isl_siomath_uint64_to_digits(num, scratch->digits, &scratch->big.used);
return &scratch->big;
312}

314/* Create a temporary IMath mp_int for an unsigned long.
*/
316inline mp_int isl_sioimath_uiarg_src(unsigned long arg,
isl_sioimath_scratchspace_t *scratch)
318{
scratch->big.digits = scratch->digits;
scratch->big.alloc = ARRAY_SIZE(scratch->digits)(sizeof(scratch->digits)/sizeof(*scratch->digits));
scratch->big.sign = MP_ZPOS;

isl_siomath_ulong_to_digits(arg, scratch->digits, &scratch->big.used);
return &scratch->big;
325}

327/* Ensure big representation. Does not preserve the current number.
* Callers may use the fact that the value _is_ preserved if the presentation
* was big before.
*/
331inline mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr)
332{
if (isl_sioimath_is_small(*ptr))
*ptr = isl_sioimath_encode_big(mp_int_alloc());
return isl_sioimath_get_big(*ptr);
336}

338/* Set ptr to a number in small representation.
*/
340inline void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val)
341{
if (isl_sioimath_is_big(*ptr))
mp_int_free(isl_sioimath_get_big(*ptr));
*ptr = isl_sioimath_encode_small(val);
345}

347/* Set ptr to val, choosing small representation if possible.
*/
349inline void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val)
350{
if (ISL_SIOIMATH_SMALL_MIN(-(2147483647)) <= val && val <= ISL_SIOIMATH_SMALL_MAX(2147483647)) {
isl_sioimath_set_small(ptr, val);
return;
}

mp_int_init_value(isl_sioimath_reinit_big(ptr), val);
357}

359/* Assign an int64_t number using small representation if possible.
*/
361inline void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val)
362{
if (ISL_SIOIMATH_SMALL_MIN(-(2147483647)) <= val && val <= ISL_SIOIMATH_SMALL_MAX(2147483647)) {
isl_sioimath_set_small(ptr, val);
return;
}

isl_sioimath_scratchspace_t scratch;
mp_int_copy(isl_sioimath_si64arg_src(val, &scratch),
   isl_sioimath_reinit_big(ptr));
371}

373/* Convert to big representation while preserving the current number.
*/
375inline void isl_sioimath_promote(isl_sioimath_ptr dst)
376{
int32_t small;

if (isl_sioimath_is_big(*dst))
return;

small = isl_sioimath_get_small(*dst);
mp_int_set_value(isl_sioimath_reinit_big(dst), small);
384}

386/* Convert to small representation while preserving the current number. Does
* nothing if dst doesn't fit small representation.
*/
389inline void isl_sioimath_try_demote(isl_sioimath_ptr dst)
390{
mp_small small;

if (isl_sioimath_is_small(*dst))
return;

if (mp_int_to_int(isl_sioimath_get_big(*dst), &small) != MP_OK)
return;

if (ISL_SIOIMATH_SMALL_MIN(-(2147483647)) <= small && small <= ISL_SIOIMATH_SMALL_MAX(2147483647))
isl_sioimath_set_small(dst, small);
401}

403/* Initialize an isl_int. The implicit value is 0 in small representation.
*/
405inline void isl_sioimath_init(isl_sioimath_ptr dst)
406{
*dst = isl_sioimath_encode_small(0);
408}

410/* Free the resources taken by an isl_int.
*/
412inline void isl_sioimath_clear(isl_sioimath_ptr dst)
413{
if (isl_sioimath_is_small(*dst))
return;

mp_int_free(isl_sioimath_get_big(*dst));
418}

420/* Copy the value of one isl_int to another.
*/
422inline void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val)
423{
if (isl_sioimath_is_small(val)) {
isl_sioimath_set_small(dst, isl_sioimath_get_small(val));
return;
}

mp_int_copy(isl_sioimath_get_big(val), isl_sioimath_reinit_big(dst));
430}

432/* Store a signed long into an isl_int.
*/
434inline void isl_sioimath_set_si(isl_sioimath_ptr dst, long val)
435{
if (ISL_SIOIMATH_SMALL_MIN(-(2147483647)) <= val && val <= ISL_SIOIMATH_SMALL_MAX(2147483647)) {
isl_sioimath_set_small(dst, val);
return;
}

mp_int_set_value(isl_sioimath_reinit_big(dst), val);
442}

444/* Store an unsigned long into an isl_int.
*/
446inline void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val)
447{
if (val <= ISL_SIOIMATH_SMALL_MAX(2147483647)) {
isl_sioimath_set_small(dst, val);
return;
}

mp_int_set_uvalue(isl_sioimath_reinit_big(dst), val);
454}

456/* Return whether a number can be represented by a signed long.
*/
458inline int isl_sioimath_fits_slong(isl_sioimath_src val)
459{
mp_small dummy;

if (isl_sioimath_is_small(val))
return 1;

return mp_int_to_int(isl_sioimath_get_big(val), &dummy) == MP_OK;
466}

468/* Return a number as signed long. Result is undefined if the number cannot be
* represented as long.
*/
471inline long isl_sioimath_get_si(isl_sioimath_src val)
472{
mp_small result;

if (isl_sioimath_is_small(val))
return isl_sioimath_get_small(val);

mp_int_to_int(isl_sioimath_get_big(val), &result);
return result;
480}

482/* Return whether a number can be represented as unsigned long.
*/
484inline int isl_sioimath_fits_ulong(isl_sioimath_src val)
485{
mp_usmall dummy;

if (isl_sioimath_is_small(val))
return isl_sioimath_get_small(val) >= 0;

return mp_int_to_uint(isl_sioimath_get_big(val), &dummy) == MP_OK;
492}

494/* Return a number as unsigned long. Result is undefined if the number cannot be
* represented as unsigned long.
*/
497inline unsigned long isl_sioimath_get_ui(isl_sioimath_src val)
498{
mp_usmall result;

if (isl_sioimath_is_small(val))
return isl_sioimath_get_small(val);

mp_int_to_uint(isl_sioimath_get_big(val), &result);
return result;
506}

508/* Return a number as floating point value.
*/
510inline double isl_sioimath_get_d(isl_sioimath_src val)
511{
mp_int big;
double result = 0;
int i;

if (isl_sioimath_is_small(val))
return isl_sioimath_get_small(val);

big = isl_sioimath_get_big(val);
for (i = 0; i < big->used; ++i)
result = result * (double) ((uintmax_t) MP_DIGIT_MAX((4294967295U) * 1UL) + 1) +
         (double) big->digits[i];

if (big->sign == MP_NEG)
result = -result;

return result;
528}

530/* Format a number as decimal string.
*
* The largest possible string from small representation is 12 characters
* ("-2147483647").
*/
535inline char *isl_sioimath_get_str(isl_sioimath_src val)
536{
char *result;

if (isl_sioimath_is_small(val)) {
result = malloc(12);
snprintf(result, 12, "%" PRIi32, isl_sioimath_get_small(val))__builtin___snprintf_chk (result, 12, 2 - 1, __builtin_object_size
 (result, 2 > 1), "%" "i", isl_sioimath_get_small(val));
return result;
}

return impz_get_str(NULL((void*)0), 10, isl_sioimath_get_big(val));
546}

548/* Return the absolute value.
*/
550inline void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg)
551{
if (isl_sioimath_is_small(arg)) {
isl_sioimath_set_small(dst, labs(isl_sioimath_get_small(arg)));
return;
}

mp_int_abs(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst));
558}

560/* Return the negation of a number.
*/
562inline void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg)
563{
if (isl_sioimath_is_small(arg)) {
isl_sioimath_set_small(dst, -isl_sioimath_get_small(arg));
return;
}

mp_int_neg(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst));
570}

572/* Swap two isl_ints.
*
* isl_sioimath can be copied bytewise; nothing depends on its address. It can
* also be stored in a CPU register.
*/
577inline void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs)
578{
isl_sioimath tmp = *lhs;
*lhs = *rhs;
22
←
Assigned value is garbage or undefined
*rhs = tmp;
582}

584/* Add an unsigned long to the number.
*
* On LP64 unsigned long exceeds the range of an int64_t, therefore we check in
* advance whether small representation possibly overflows.
*/
589inline void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
unsigned long rhs)
591{
int32_t smalllhs;
isl_sioimath_scratchspace_t lhsscratch;

if (isl_sioimath_decode_small(lhs, &smalllhs) &&
   (rhs <= (uint64_t) INT64_MAX(9223372036854775807L) - (uint64_t) ISL_SIOIMATH_SMALL_MAX(2147483647))) {
isl_sioimath_set_int64(dst, (int64_t) smalllhs + rhs);
return;
}

impz_add_ui(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs);
isl_sioimath_try_demote(dst);
604}

606/* Subtract an unsigned long.
*
* On LP64 unsigned long exceeds the range of an int64_t.  If
* ISL_SIOIMATH_SMALL_MIN-rhs>=INT64_MIN we can do the calculation using int64_t
* without risking an overflow.
*/
612inline void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
		unsigned long rhs)
614{
int32_t smalllhs;
isl_sioimath_scratchspace_t lhsscratch;

if (isl_sioimath_decode_small(lhs, &smalllhs) &&
   (rhs < (uint64_t) INT64_MIN(-9223372036854775807L -1) - (uint64_t) ISL_SIOIMATH_SMALL_MIN(-(2147483647)))) {
isl_sioimath_set_int64(dst, (int64_t) smalllhs - rhs);
return;
}

impz_sub_ui(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs);
isl_sioimath_try_demote(dst);
627}

629/* Sum of two isl_ints.
*/
631inline void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
633{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs, smallrhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) &&
   isl_sioimath_decode_small(rhs, &smallrhs)) {
isl_sioimath_set_int64(
    dst, (int64_t) smalllhs + (int64_t) smallrhs);
return;
}

mp_int_add(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_bigarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
648}

650/* Subtract two isl_ints.
*/
652inline void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
654{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs, smallrhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) &&
   isl_sioimath_decode_small(rhs, &smallrhs)) {
isl_sioimath_set_int64(
    dst, (int64_t) smalllhs - (int64_t) smallrhs);
return;
}

mp_int_sub(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_bigarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
669}

671/* Multiply two isl_ints.
*/
673inline void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
675{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs, smallrhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) &&
   isl_sioimath_decode_small(rhs, &smallrhs)) {
isl_sioimath_set_int64(
    dst, (int64_t) smalllhs * (int64_t) smallrhs);
return;
}

mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_bigarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
690}

692/* Shift lhs by rhs bits to the left and store the result in dst. Effectively,
* this operation computes 'lhs * 2^rhs'.
*/
695inline void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs,
unsigned long rhs)
697{
isl_sioimath_scratchspace_t scratchlhs;
int32_t smalllhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs <= 32ul)) {
isl_sioimath_set_int64(dst, ((int64_t) smalllhs) << rhs);
return;
}

mp_int_mul_pow2(isl_sioimath_bigarg_src(lhs, &scratchlhs), rhs,
   isl_sioimath_reinit_big(dst));
708}

710/* Multiply an isl_int and a signed long.
*/
712inline void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs,
signed long rhs)
714{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs > LONG_MIN(-9223372036854775807L -1L)) &&
   (labs(rhs) <= UINT32_MAX(4294967295U))) {
isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs);
return;
}

mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_siarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
728}

730/* Multiply an isl_int and an unsigned long.
*/
732inline void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
unsigned long rhs)
734{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs;

if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs <= UINT32_MAX(4294967295U))) {
isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs);
return;
}

mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_uiarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
747}

749/* Compute the power of an isl_int to an unsigned long.
* Always let IMath do it; the result is unlikely to be small except in some
* special cases.
* Note: 0^0 == 1
*/
754inline void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
756{
isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
int32_t smalllhs;

switch (rhs) {
case 0:
isl_sioimath_set_small(dst, 1);
return;
case 1:
isl_sioimath_set(dst, lhs);
return;
case 2:
isl_sioimath_mul(dst, lhs, lhs);
return;
}

if (isl_sioimath_decode_small(lhs, &smalllhs)) {
switch (smalllhs) {
case 0:
	isl_sioimath_set_small(dst, 0);
	return;
case 1:
	isl_sioimath_set_small(dst, 1);
	return;
case 2:
	isl_sioimath_set_small(dst, 1);
	isl_sioimath_mul_2exp(dst, *dst, rhs);
	return;
default:
	if ((MP_SMALL_MIN(-9223372036854775807L -1L) <= rhs) && (rhs <= MP_SMALL_MAX9223372036854775807L)) {
		mp_int_expt_value(smalllhs, rhs,
		    isl_sioimath_reinit_big(dst));
		isl_sioimath_try_demote(dst);
		return;
	}
}
}

mp_int_expt_full(isl_sioimath_bigarg_src(lhs, &scratchlhs),
   isl_sioimath_uiarg_src(rhs, &scratchrhs),
   isl_sioimath_reinit_big(dst));
isl_sioimath_try_demote(dst);
798}

800/* Fused multiply-add.
*/
802inline void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
804{
isl_sioimath tmp;
isl_sioimath_init(&tmp);
isl_sioimath_mul(&tmp, lhs, rhs);
isl_sioimath_add(dst, *dst, tmp);
isl_sioimath_clear(&tmp);
810}

812/* Fused multiply-add with an unsigned long.
*/
814inline void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
816{
isl_sioimath tmp;
isl_sioimath_init(&tmp);
isl_sioimath_mul_ui(&tmp, lhs, rhs);
isl_sioimath_add(dst, *dst, tmp);
isl_sioimath_clear(&tmp);
822}

824/* Fused multiply-subtract.
*/
826inline void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
828{
isl_sioimath tmp;
isl_sioimath_init(&tmp);
isl_sioimath_mul(&tmp, lhs, rhs);
isl_sioimath_sub(dst, *dst, tmp);
isl_sioimath_clear(&tmp);
834}

836/* Fused multiply-add with an unsigned long.
*/
838inline void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
840{
isl_sioimath tmp;
isl_sioimath_init(&tmp);
isl_sioimath_mul_ui(&tmp, lhs, rhs);
isl_sioimath_sub(dst, *dst, tmp);
isl_sioimath_clear(&tmp);
846}

848void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs,
      isl_sioimath_src rhs);
850void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs,
      isl_sioimath_src rhs);

853/* Divide lhs by rhs, rounding to zero (Truncate).
*/
855inline void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
857{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, rhssmall;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall)) {
isl_sioimath_set_small(dst, lhssmall / rhssmall);
return;
}

mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch),
   isl_sioimath_reinit_big(dst), NULL((void*)0));
isl_sioimath_try_demote(dst);
return;
872}

874/* Divide lhs by an unsigned long rhs, rounding to zero (Truncate).
*/
876inline void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
878{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall;

if (isl_sioimath_is_small(lhs) && (rhs <= (unsigned long) INT32_MAX(2147483647))) {
lhssmall = isl_sioimath_get_small(lhs);
isl_sioimath_set_small(dst, lhssmall / (int32_t) rhs);
return;
}

if (rhs <= MP_SMALL_MAX9223372036854775807L) {
mp_int_div_value(isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs,
    isl_sioimath_reinit_big(dst), NULL((void*)0));
isl_sioimath_try_demote(dst);
return;
}

mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_uiarg_src(rhs, &rhsscratch),
   isl_sioimath_reinit_big(dst), NULL((void*)0));
isl_sioimath_try_demote(dst);
899}

901/* Divide lhs by rhs, rounding to positive infinity (Ceil).
*/
903inline void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
905{
int32_t lhssmall, rhssmall;
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t q;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall)) {
if ((lhssmall >= 0) && (rhssmall >= 0))
	q = ((int64_t) lhssmall + (int64_t) rhssmall - 1) /
	    rhssmall;
else if ((lhssmall < 0) && (rhssmall < 0))
	q = ((int64_t) lhssmall + (int64_t) rhssmall + 1) /
	    rhssmall;
else
	q = lhssmall / rhssmall;
isl_sioimath_set_small(dst, q);
return;
}

impz_cdiv_q(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch));
isl_sioimath_try_demote(dst);
928}

930/* Compute the division of lhs by a rhs of type unsigned long, rounding towards
* positive infinity (Ceil).
*/
933inline void isl_sioimath_cdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
935{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, q;

if (isl_sioimath_decode_small(lhs, &lhssmall) && (rhs <= INT32_MAX(2147483647))) {
if (lhssmall >= 0)
	q = ((int64_t) lhssmall + ((int64_t) rhs - 1)) /
	    (int64_t) rhs;
else
	q = lhssmall / (int32_t) rhs;
isl_sioimath_set_small(dst, q);
return;
}

impz_cdiv_q(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_uiarg_src(rhs, &rhsscratch));
isl_sioimath_try_demote(dst);
953}

955/* Divide lhs by rhs, rounding to negative infinity (Floor).
*/
957inline void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
959{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, rhssmall;
int32_t q;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall)) {
if ((lhssmall < 0) && (rhssmall >= 0))
	q = ((int64_t) lhssmall - ((int64_t) rhssmall - 1)) /
	    rhssmall;
else if ((lhssmall >= 0) && (rhssmall < 0))
	q = ((int64_t) lhssmall - ((int64_t) rhssmall + 1)) /
	    rhssmall;
else
	q = lhssmall / rhssmall;
isl_sioimath_set_small(dst, q);
return;
}

impz_fdiv_q(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch));
isl_sioimath_try_demote(dst);
982}

984/* Compute the division of lhs by a rhs of type unsigned long, rounding towards
* negative infinity (Floor).
*/
987inline void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
unsigned long rhs)
989{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, q;

if (isl_sioimath_decode_small(lhs, &lhssmall) && (rhs <= INT32_MAX(2147483647))) {
if (lhssmall >= 0)
	q = (uint32_t) lhssmall / rhs;
else
	q = ((int64_t) lhssmall - ((int64_t) rhs - 1)) /
	    (int64_t) rhs;
isl_sioimath_set_small(dst, q);
return;
}

impz_fdiv_q(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_uiarg_src(rhs, &rhsscratch));
isl_sioimath_try_demote(dst);
1007}

1009/* Get the remainder of: lhs divided by rhs rounded towards negative infinite
* (Floor).
*/
1012inline void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs,
isl_sioimath_src rhs)
1014{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int64_t lhssmall, rhssmall;
int32_t r;

if (isl_sioimath_is_small(lhs) && isl_sioimath_is_small(rhs)) {
lhssmall = isl_sioimath_get_small(lhs);
rhssmall = isl_sioimath_get_small(rhs);
r = (rhssmall + lhssmall % rhssmall) % rhssmall;
isl_sioimath_set_small(dst, r);
return;
}

impz_fdiv_r(isl_sioimath_reinit_big(dst),
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch));
isl_sioimath_try_demote(dst);
1031}

1033void isl_sioimath_read(isl_sioimath_ptr dst, const char *str);

1035/* Return:
*   +1 for a positive number
*   -1 for a negative number
*    0 if the number is zero
*/
1040inline int isl_sioimath_sgn(isl_sioimath_src arg)
1041{
int32_t small;

if (isl_sioimath_decode_small(arg, &small))
return (small > 0) - (small < 0);

return mp_int_compare_zero(isl_sioimath_get_big(arg));
1048}

1050/* Return:
*   +1 if lhs > rhs
*   -1 if lhs < rhs
*    0 if lhs = rhs
*/
1055inline int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs)
1056{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, rhssmall;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall))
return (lhssmall > rhssmall) - (lhssmall < rhssmall);

if (isl_sioimath_decode_small(rhs, &rhssmall))
return mp_int_compare_value(
    isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall);

if (isl_sioimath_decode_small(lhs, &lhssmall))
return -mp_int_compare_value(
           isl_sioimath_bigarg_src(rhs, &rhsscratch), lhssmall);

return mp_int_compare(
   isl_sioimath_get_big(lhs), isl_sioimath_get_big(rhs));
1074}

1076/* As isl_sioimath_cmp, but with signed long rhs.
*/
1078inline int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs)
1079{
int32_t lhssmall;

if (isl_sioimath_decode_small(lhs, &lhssmall))
return (lhssmall > rhs) - (lhssmall < rhs);

return mp_int_compare_value(isl_sioimath_get_big(lhs), rhs);
1086}

1088/* Return:
*   +1 if |lhs| > |rhs|
*   -1 if |lhs| < |rhs|
*    0 if |lhs| = |rhs|
*/
1093inline int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs)
1094{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, rhssmall;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall)) {
lhssmall = labs(lhssmall);
rhssmall = labs(rhssmall);
return (lhssmall > rhssmall) - (lhssmall < rhssmall);
}

return mp_int_compare_unsigned(
   isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch));
1108}

1110/* Return whether lhs is divisible by rhs.
* In particular, can rhs be multiplied by some integer to result in lhs?
* If rhs is zero, then this means lhs has to be zero too.
*/
1114inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
			isl_sioimath_src rhs)
1116{
isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
int32_t lhssmall, rhssmall;
mpz_t rem;
int cmp;

if (isl_sioimath_sgn(rhs) == 0)
return isl_sioimath_sgn(lhs) == 0;

if (isl_sioimath_decode_small(lhs, &lhssmall) &&
   isl_sioimath_decode_small(rhs, &rhssmall))
return lhssmall % rhssmall == 0;

if (isl_sioimath_decode_small(rhs, &rhssmall))
return mp_int_divisible_value(
    isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall);

mp_int_init(&rem);
mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
   isl_sioimath_bigarg_src(rhs, &rhsscratch), NULL((void*)0), &rem);
cmp = mp_int_compare_zero(&rem);
mp_int_clear(&rem);
return cmp == 0;
1139}

1141/* Return a hash code of an isl_sioimath.
* The hash code for a number in small and big representation must be identical
* on the same machine because small representation if not obligatory if fits.
*/
1145inline uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash)
1146{
int32_t small;
int i;
uint32_t num;
mp_digit digits[(sizeof(uint32_t) + sizeof(mp_digit) - 1) /
               sizeof(mp_digit)];
mp_size used;
const unsigned char *digitdata = (const unsigned char *) &digits;

if (isl_sioimath_decode_small(arg, &small)) {
if (small < 0)
	isl_hash_byte(hash, 0xFF)do { hash *= 16777619; hash ^= 0xFF; } while(0);
num = labs(small);

isl_siomath_uint32_to_digits(num, digits, &used);
for (i = 0; i < used * sizeof(mp_digit); i += 1)
	isl_hash_byte(hash, digitdata[i])do { hash *= 16777619; hash ^= digitdata[i]; } while(0);
return hash;
}

return isl_imath_hash(isl_sioimath_get_big(arg), hash);
1167}

1169/* Return the number of digits in a number of the given base or more, i.e. the
* string length without sign and null terminator.
*
* Current implementation for small representation returns the maximal number
* of binary digits in that representation, which can be much larger than the
* smallest possible solution.
*/
1176inline size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base)
1177{
int32_t small;

if (isl_sioimath_decode_small(arg, &small))
return sizeof(int32_t) * CHAR_BIT8 - 1;

return impz_sizeinbase(isl_sioimath_get_big(arg), base);
1184}

1186void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width);
1187void isl_sioimath_dump(isl_sioimath_src arg);

1189typedef isl_sioimath isl_int[1];
1190#define isl_int_init(i)isl_sioimath_init((i))			isl_sioimath_init((i))
1191#define isl_int_clear(i)isl_sioimath_clear((i))		isl_sioimath_clear((i))

1193#define isl_int_set(r, i)isl_sioimath_set((r), *(i))		isl_sioimath_set((r), *(i))
1194#define isl_int_set_si(r, i)isl_sioimath_set_si((r), i)		isl_sioimath_set_si((r), i)
1195#define isl_int_set_ui(r, i)isl_sioimath_set_ui((r), i)		isl_sioimath_set_ui((r), i)
1196#define isl_int_fits_slong(r)isl_sioimath_fits_slong(*(r))		isl_sioimath_fits_slong(*(r))
1197#define isl_int_get_si(r)isl_sioimath_get_si(*(r))		isl_sioimath_get_si(*(r))
1198#define isl_int_fits_ulong(r)isl_sioimath_fits_ulong(*(r))		isl_sioimath_fits_ulong(*(r))
1199#define isl_int_get_ui(r)isl_sioimath_get_ui(*(r))		isl_sioimath_get_ui(*(r))
1200#define isl_int_get_d(r)isl_sioimath_get_d(*(r))		isl_sioimath_get_d(*(r))
1201#define isl_int_get_str(r)isl_sioimath_get_str(*(r))		isl_sioimath_get_str(*(r))
1202#define isl_int_abs(r, i)isl_sioimath_abs((r), *(i))		isl_sioimath_abs((r), *(i))
1203#define isl_int_neg(r, i)isl_sioimath_neg((r), *(i))		isl_sioimath_neg((r), *(i))
1204#define isl_int_swap(i, j)isl_sioimath_swap((i), (j))		isl_sioimath_swap((i), (j))
1205#define isl_int_swap_or_set(i, j)isl_sioimath_swap((i), (j))	isl_sioimath_swap((i), (j))
1206#define isl_int_add_ui(r, i, j)isl_sioimath_add_ui((r), *(i), j)		isl_sioimath_add_ui((r), *(i), j)
1207#define isl_int_sub_ui(r, i, j)isl_sioimath_sub_ui((r), *(i), j)		isl_sioimath_sub_ui((r), *(i), j)

1209#define isl_int_add(r, i, j)isl_sioimath_add((r), *(i), *(j))		isl_sioimath_add((r), *(i), *(j))
1210#define isl_int_sub(r, i, j)isl_sioimath_sub((r), *(i), *(j))		isl_sioimath_sub((r), *(i), *(j))
1211#define isl_int_mul(r, i, j)isl_sioimath_mul((r), *(i), *(j))		isl_sioimath_mul((r), *(i), *(j))
1212#define isl_int_mul_2exp(r, i, j)isl_sioimath_mul_2exp((r), *(i), j)	isl_sioimath_mul_2exp((r), *(i), j)
1213#define isl_int_mul_si(r, i, j)isl_sioimath_mul_si((r), *(i), j)		isl_sioimath_mul_si((r), *(i), j)
1214#define isl_int_mul_ui(r, i, j)isl_sioimath_mul_ui((r), *(i), j)		isl_sioimath_mul_ui((r), *(i), j)
1215#define isl_int_pow_ui(r, i, j)isl_sioimath_pow_ui((r), *(i), j)		isl_sioimath_pow_ui((r), *(i), j)
1216#define isl_int_addmul(r, i, j)isl_sioimath_addmul((r), *(i), *(j))		isl_sioimath_addmul((r), *(i), *(j))
1217#define isl_int_addmul_ui(r, i, j)isl_sioimath_addmul_ui((r), *(i), j)	isl_sioimath_addmul_ui((r), *(i), j)
1218#define isl_int_submul(r, i, j)isl_sioimath_submul((r), *(i), *(j))		isl_sioimath_submul((r), *(i), *(j))
1219#define isl_int_submul_ui(r, i, j)isl_sioimath_submul_ui((r), *(i), j)	isl_sioimath_submul_ui((r), *(i), j)

1221#define isl_int_gcd(r, i, j)isl_sioimath_gcd((r), *(i), *(j))		isl_sioimath_gcd((r), *(i), *(j))
1222#define isl_int_lcm(r, i, j)isl_sioimath_lcm((r), *(i), *(j))		isl_sioimath_lcm((r), *(i), *(j))
1223#define isl_int_divexact(r, i, j)isl_sioimath_tdiv_q((r), *(i), *(j))	isl_sioimath_tdiv_q((r), *(i), *(j))
1224#define isl_int_divexact_ui(r, i, j)isl_sioimath_tdiv_q_ui((r), *(i), j)	isl_sioimath_tdiv_q_ui((r), *(i), j)
1225#define isl_int_tdiv_q(r, i, j)isl_sioimath_tdiv_q((r), *(i), *(j))		isl_sioimath_tdiv_q((r), *(i), *(j))
1226#define isl_int_cdiv_q(r, i, j)isl_sioimath_cdiv_q((r), *(i), *(j))		isl_sioimath_cdiv_q((r), *(i), *(j))
1227#define isl_int_cdiv_q_ui(r, i, j)isl_sioimath_cdiv_q_ui((r), *(i), j)	isl_sioimath_cdiv_q_ui((r), *(i), j)
1228#define isl_int_fdiv_q(r, i, j)isl_sioimath_fdiv_q((r), *(i), *(j))		isl_sioimath_fdiv_q((r), *(i), *(j))
1229#define isl_int_fdiv_r(r, i, j)isl_sioimath_fdiv_r((r), *(i), *(j))		isl_sioimath_fdiv_r((r), *(i), *(j))
1230#define isl_int_fdiv_q_ui(r, i, j)isl_sioimath_fdiv_q_ui((r), *(i), j)	isl_sioimath_fdiv_q_ui((r), *(i), j)

1232#define isl_int_read(r, s)isl_sioimath_read((r), s)		isl_sioimath_read((r), s)
1233#define isl_int_sgn(i)isl_sioimath_sgn(*(i))			isl_sioimath_sgn(*(i))
1234#define isl_int_cmp(i, j)isl_sioimath_cmp(*(i), *(j))		isl_sioimath_cmp(*(i), *(j))
1235#define isl_int_cmp_si(i, si)isl_sioimath_cmp_si(*(i), si)		isl_sioimath_cmp_si(*(i), si)
1236#define isl_int_eq(i, j)(isl_sioimath_cmp(*(i), *(j)) == 0)		(isl_sioimath_cmp(*(i), *(j)) == 0)
1237#define isl_int_ne(i, j)(isl_sioimath_cmp(*(i), *(j)) != 0)		(isl_sioimath_cmp(*(i), *(j)) != 0)
1238#define isl_int_lt(i, j)(isl_sioimath_cmp(*(i), *(j)) < 0)		(isl_sioimath_cmp(*(i), *(j)) < 0)
1239#define isl_int_le(i, j)(isl_sioimath_cmp(*(i), *(j)) <= 0)		(isl_sioimath_cmp(*(i), *(j)) <= 0)
1240#define isl_int_gt(i, j)(isl_sioimath_cmp(*(i), *(j)) > 0)		(isl_sioimath_cmp(*(i), *(j)) > 0)
1241#define isl_int_ge(i, j)(isl_sioimath_cmp(*(i), *(j)) >= 0)		(isl_sioimath_cmp(*(i), *(j)) >= 0)
1242#define isl_int_abs_cmp(i, j)isl_sioimath_abs_cmp(*(i), *(j))		isl_sioimath_abs_cmp(*(i), *(j))
1243#define isl_int_abs_eq(i, j)(isl_sioimath_abs_cmp(*(i), *(j)) == 0)		(isl_sioimath_abs_cmp(*(i), *(j)) == 0)
1244#define isl_int_abs_ne(i, j)(isl_sioimath_abs_cmp(*(i), *(j)) != 0)		(isl_sioimath_abs_cmp(*(i), *(j)) != 0)
1245#define isl_int_abs_lt(i, j)(isl_sioimath_abs_cmp(*(i), *(j)) < 0)		(isl_sioimath_abs_cmp(*(i), *(j)) < 0)
1246#define isl_int_abs_gt(i, j)(isl_sioimath_abs_cmp(*(i), *(j)) > 0)		(isl_sioimath_abs_cmp(*(i), *(j)) > 0)
1247#define isl_int_abs_ge(i, j)(isl_sioimath_abs_cmp(*(i), *(j)) >= 0)		(isl_sioimath_abs_cmp(*(i), *(j)) >= 0)
1248#define isl_int_is_divisible_by(i, j)isl_sioimath_is_divisible_by(*(i), *(j))	isl_sioimath_is_divisible_by(*(i), *(j))

1250#define isl_int_hash(v, h)isl_sioimath_hash(*(v), h)		isl_sioimath_hash(*(v), h)
1251#define isl_int_free_str(s)free(s)		free(s)
1252#define isl_int_print(out, i, width)isl_sioimath_print(out, *(i), width)	isl_sioimath_print(out, *(i), width)

1254#endif /* ISL_INT_SIOIMATH_H */