polytope_scan.c: add missing include

fix return type of isl_div_free

isl_map_simplify.c: drop return from void function

isl_map_simplify.c: add missing include

isl_convex_hull.c: use isl_seq_get_hash instead of isl_seq_hash

declare flexarrays of size 1 to silence sun compiler

change isl_basic_map_empty interface for consistency

AX_SUBMODULE: mention default type of library to use

configure.ac: use AX_SUBMODULE for gmp for consistency

separate out config header from isl_ctx.h

pilp solver: don't ignore feasibility test on context

In the initial implementation, the sample point of the context was
kept integer.  This was later changed in such a way that now the
sample point is just lexico-smallest rational value.
This means that after checking for an integer point, we rollback
until the state before we performed this check.
However, the results of the feasibility test were only checked
after the rollback, completely ignoring the actual results of
the feasibility test.

isl_basic_map_gauss: try not to remove any div definitions

After computing divs, the result may get simplified and during
this simplification, isl_basic_map_gauss may actually remove some
divs because it is trying to play safe wrt circular div definitions.
By keeping the divs ordered, divs can safely be eliminated without
introducing any circular definitions.

add isl_map_sum

add isl_map_floordiv

add isl_map_neg

add isl_map_is_strict_subset

add isl_map_fast_is_fixed

add isl_map_identity_like

rename isl_map_identity_like to isl_map_identity_like_basic_map

add isl_polytope_scan application

isl_seq_normalize: use pre-allocated temporary variable in isl_ctx

This requires that we pass along an isl_ctx, but it removes
the need for allocating a temporary variable every time
isl_seq_normalize is called.
In some cases, up to 20% of the execution time of isl_seq_normalize
was wasted on initializing and clearing this temporary variable.

add isl_vec_normalize

isl_seq_normalize: no need to scale down by one

add isl_polyhedron_minimize application

add generalized basis reduction based ILP solver

add isl_vec_mat_product

export isl_vec_ceil

isl_basic_set_sample: only perform basis reduction once

On larger problem, much time was spent on repeated basis reductions
with little or no reduction on the number of points visited.
The initial basis reduction seems to be sufficient in most cases.

rename isl_solve_lp to isl_basic_{map,set}_solve_lp

isl_solve_lp: optionally return solution point

The caller may now not be interested in the optimal value anymore,
so make returning this optimal value optional.

export isl_vec header

add isl_int_fdiv_q_ui

add isl_vec_read_from_file

isl_basic_map_drop_redundant_divs: also investigate divs that have a definition

They may have become redundant after having been defined.

isl_basic_map_apply_{domain,range}: drop redundant divs in result

isl_map_simplify.c: fix typo in comment

isl_basic_set_project_out: drop redundant divs in result

isl_basic_map_remove: only drop divs if basic map did not turn out to be empty

If isl_basic_map_eliminate_vars finds that its argument is empty,
it resets its constraints to the canonical representation of an empty
set and drops all divs.

isl_basic_map_detect_equalities: explicitly keep track of any equalities found

The way extend_affine_hull works is that it starts off from an
under-approximation of the affine hull and then extends it with
each extra point found outside of the current approximation.
The affine hull is then determined by the equalities that remain.

However, during the computation, we may find an equality in
the current approximation such that there is no point in the set
outside of this equality.  If the approximation is later extended
with a point found outside some other equality, then this first
equality would get tested again.  If this is a difficult computation,
then we needlessly go through it again.

By explicitly storing the equality that we have detected in the set,
this computation becomes trivial, to there is no real harm in doing
again.  An alternative would be to keep track of all equalities found
in some additional data structure, but adding it to the original set
seems preferable since it may also simplify tests for points outside
other equalities.

Perhaps the calling convention should be changed such that
extend_affine_hull would return the original set intersected
with its affine hull, rather than the affine hull itself.

isl_basic_map_extend_dim: keep hold of sample if dimension doesn't change

isl_tab_min: read off all information from tableau before rollback

As it happens, the rollback has little effect in this case and
the information is still available, but we shouldn't depend on this.

isl_tab_add_valid_eq: keep track of whether equality is negated

This is important during generalized basis reduction, because
this procedure requires the dual variables of some of the
equalities added to the tableau.  If the original equality get
negated then the dual of the original equality will be the
opposite of the dual of the equality that was actually added.

Without this fix, gbr could in some cases make completely
inappropriate decisions.

configure.ac: no longer use piplib by default

add an internal parametric integer linear program solver

This removes the dependence on piplib.

The solver is very similar to the one in piplib.
In particular, as in piplib, the lexicographic solver is
used recursively on the context.  This means that the current
solver will run into the same problems the piplib solver runs into
while looking for an integer point in a context that no longer has any.

In the future, we will replace this recursive call by a call
to an incremental solver based on the generalized basis reduction solver.

isl_mat_extend: make sure the number of rows never decreases

isl_affine_hull.c: only construct affine hull in bounded directions

The affine hull of a set necessarily contains the directions
of the recession cone of the set.
Before we exploited this fact by adding these directions to
our initial approximation of the affine hull.
The set for which the affine hull was computed was not changed, however.
Now, we project out the recession cone and only construct an
affine hull in the remaining part.

isl_tab: add support for keeping track of samples

isl_tab: optionally keep track of row signs

isl_tab: add isl_basic_set field for optionally keeping track of inequalities

isl_tab: introduce support for "big parameters"

These will be used while solving PILP problems.

isl_tab: allow introduction of extra variables

isl_tab: introduce parameters and divs

isl_tab.h: fix typo in comment

isl_tab: allow saving and restoring the complete basis

isl_tab: privately export some functionality

isl_tab: store undo argument in a union for future extensions

add isl_basic_set_sample_bounded

privately export isl_basic_set_order_divs

isl_map_simplify.c: remove_dependent_vars: only remove definitions of divs

Don't remove the dependent divs themselves, because in particular
eliminate_divs_ineq does not expect any other divs to get removed.

isl_basic_map_compute_divs: use isl_basic_set_lexmin and move to isl_map.c

There is no need for the core of isl_basic_map_compute_divs to use any
piplib specific code.  We therefore move the code to isl_map.c so
that it can also be used on top of another PILP solver.

isl_pip_basic_map_compute_divs: don't turn divs into output dimensions

There is no practical reason why we should want to do this transformation
and removing it makes it possible to you use the standard interface
to pip in the next commit.

privately export isl_basic_map_swap_div

isl_{set,map}_add: don't add obviously empty basic sets/maps

combine isl_pip_basic_map_lex{min,max} into isl_pip_basic_map_lexopt

make piplib headers private

isl_mat: keep track of the actual number of columns in a row

We need this number to perform extensions after dropping columns.

isl_tab_pivot: fix typo that prevented normalization of rows

add isl_basic_set_positive_orthant

add isl_basic_set_partial_lex{min,max}

rename isl_basic_map_lex{min,max} to isl_basic_map_partial_lex{min,max}

add isl_basic_set_free_div

isl_set_dim: support isl_dim_all

isl_tab: store index of variable in undo record instead of pointer to variable

The row of variables might get reallocated between pushing the undo
record and performing the undo, invalidating the pointer.

add isl_{set,map}_grow

add isl_map_get_dim

add isl_basic_map_get_dim

add isl_tab_dup

export isl_mat_dup

isl_tab.c: mark_redundant: only mark variable nonneg if they weren't already

More imporantly, don't undo such a mark during rollback.

isl_tab.c: to_row: allow pivoting in arbitrary direction

While undoing the allocation of a row, we may be dealing with
a row that was unbounded in both directions and is now in a column.
To move the column back to a row, we just pivot using any non-zero entry.

isl_tab.c: simplify code by letting mark_empty return tab

add isl_seq_last_non_zero

isl_tab.c: simplify add_eq

isl_tab.c: extract allocate_con

privately export isl_basic_set_set_rational

configure.ac: explicitly set AC_CONFIG_AUX_DIR

Without it, libtool can apparently get confused about which
ltmain.sh to use.

convex_hull: coalesce set during facet computation

isl_map_coalesce: don't drop rational flag from result if set in input

isl_tab_cone_is_bounded: start over after computing sign_of_max

sign_of_max may have made some rows redundant and may therefore
invalidate the iteration over all non-redundant rows.

Problem reported by Uday Kumar <udayreddy@gmail.com>

isl_basic_set_dim_residue_class: only set *modulo to 0 when dimension is fixed

Before, when no residue class could be detected, *modulo was sometimes
set to 0 and sometimes to 1.  Now *modulo is always set to 1 in these
cases, except when the specified dimension has a fixed constant value,
in which case *modulo is set to 0 and *residue to the fixed value.

add isl_basic_set_fast_dim_is_fixed

isl_tab: drop isl_ctx argument where not absolutely required

isl_mat: keep track of isl_ctx

isl_basic_set_sample: don't project out lineality space up front

For the pip based sampler, projecting out the lineality space
is part of isl_basic_set_skew_to_positive_orthant, so there is
no need for a separate projection step before the skewing.

For the gbr based sampler, there is no need to project out the lineality
space.  The lineality space will simply be part of the recession cone,
which is handled more efficiently than the projection.
In particular, for systems with many variables, the unimodular transformation
used in the projection may have very large coefficients, which in turn
leads to constraints with large coefficients.  Since there is no need
to do this projection, it is best to avoid it.

isl_basic_map_fix_pos: micro-optimization

move isl_basic_set_skew_to_positive_orthant to isl_sample.c

Also, replace independent_bounds in isl_sample.c by that
of isl_sample_piplib.c
The difference is that the latter returns affine bounds
rather than linear bounds and that it return the actual
bounds from the set rather than some linear combinations
of bounds.

It is usually better to use the original bounds as
the linearly transformed bounds may have bigger coefficients
and may therefore be more difficult to process.

isl_tab.c: fix typo in comment

isl_basic_set_sample: break early if sample found in basic_set_range

export isl_tab_sample_is_integer

isl_basic_set_sample: check sample stored by isl_basic_map_is_empty first