isl_basic_map_extend_dim: move responsibility of cow'ing to the caller

Some callers, notably isl_basic_map_detect_equalities, want to
extend the basic map to add equalities that are implicit to the
basic map.  These equalities should be added to all copies,
so we definitely do not want to cow in such cases.

isl_basic_map_extend_dim: only extend constraint matrix if needed

isl_solve_lp: use tableaus instead of calling piplib (by default)

isl_solve_lp: accept affine object function instead of linear function

isl_map_simple_hull: use hash tables and tableaus

isl_convex_hull.c: extract out uset_simple_hull

isl_convex_hull.c: extend: avoid wrapping around already known ridges

isl_convex_hull.c: introduce proto_hull based on obvious facet constraints

proto_hull looks for for obvious facet constraints.
If any such constraints can be found, then the calling function
no longer needs to call initial_hull.

isl_convex_hull.c: move initial hull construction into separate function

isl_convex_hull.c: move computation of bounds into uset_convex_hull_wrap

isl_map_convex_hull: check for boundedness using recession cone

isl_basic_map_convex_hull: use tableau to detect redundant constraints

isl_affine_hull.c: use tableau to detect implicit equalities

isl_tab.c: don't detect equalities while setting up tableau

The original description of the algorithm tries to detect equalities
as soon as possible.  In our application it may be best to wait
until all constraints are available.  In some case we are not
even interested in the equalities.

add internal representation of LP tableaus

add isl_mat_extend

add isl_set_dim

privately export isl_basic_{set,map}_normalize_constraints

add isl_basic_set_extend_dim

isl_basic_map_eliminate_vars: clear divs first

isl_basic_map_eliminate_vars: remove all dependent vars first

add isl_hash_table_alloc and isl_hash_table_free

isl_hash_table_init: take minimal size instead of number of bits needed

isl_{basic_,}set_preimage: drop ctx argument

isl_basic_map_intersect: reuse sample value of either basic map if possible

If the sample value stored in one of the two basic maps is an element
of both basic maps, then we can keep it as sample value for the intersection.

add isl_int_ge

isl_basic_set_has_defining_inequalities: fix typo

isl_constraint_div: perform required reference increase on basic map

Both divs and constraints own their contained basic maps, so we
can't just steal the basic map from the constraint.

isl_basic_map: put inequalities before equalities

When confronted with a list of inequalities that need to be
turned into equalities, we want to handle the inequalities
in the same order in which we handle inequalities that can
be removed.  Eventually, we would want to do these at the
same time.

add isl_seq_normalize

isl_ctx.h: make FL_ISSET return a boolean value

rename F_ and FL_ macros to ISL_F_ and ISL_FL_ to avoid name clashes

add isl_mat_swap_cols

isl_mat_dump: also indent NULL mat

add isl_calloc_type

isl_map_convex_hull: normalize map first

isl_set_preimage: clear ISL_SET_NORMALIZED flag

add isl_basic_map_detect_equalities

add isl_map_remove

export isl_basic_map_is_equal

add isl_basic_map_remove

add isl_dim_range

add isl_map_product

add isl_basic_map_add_constraint

add isl_dim_add

isl_map_piplib.c: isl_map_from_quast: properly keep track of dimension names

change calling convention of isl_basic_map_{equal,less_at,more_at}

add isl_map_copy_basic_map and isl_map_drop_basic_map

add isl_map_from_range

add isl_map_fast_is_empty

change calling convention of isl_map_empty and add isl_map_empty_like

isl_map_intersect_{domain,range}: allow intersection with parameter constraints

isl_map_intersect: allow intersection with pure parameter constraints

isl_basic_map_affine_hull: fix search for integer points

Before, we would mistakenly only look for integer points
in adjacent hyperplanes.  This would be sufficient if we
were looking instead for rational points, although we could
then obtain an over-approximation of the integer affine hull.

isl_basic_map_overlying_set: don't add div constraints for unknown divs

Constructing div constraints as if the div were known, results in
unsatisfiable constraints.
Perhaps isl_basic_map_overlying_set shouldn't get called with a model
with unknown divs, but we currently allow it.

isl_dim.c: update n_name (only) when changing names

fix serious error in isl_mat_parameter_compression

The old version would sometimes remove valid solutions.
Since isl_mat_parameter_compression is used during simplification
on practically any set containing existentially quantified variables
involved in equalities, any such set could get corrupted.

export isl_basic_map_intersect_range

add isl_basic_map_floordiv

add isl_basic_map_fast_is_fixed

add isl_basic_map_neg

add isl_basic_map_sum

add isl_map_fix_si, a generalization of isl_basic_map_fix_input_si

isl_map_simplify.c: remove_duplicate_divs: remove divs from last to first

isl_basic_map_gauss: be careful not to introduce circular div definitions

add functions for setting isl_divs

isl_map_from_quast: don't throw away any bottom leaves

Before, we would perform an "optimization" that would simply
discard any leaves with a bottom when we hadn't seen any leaves
with a solution yet, the intention being that we don't need
to collect bottom leaves if there are no solutions.
However, the bottom leaves may precede solution leaves and
then we would erroneously discard them.

isl_map_simplify.c: normalize_divs: fix use of variable compression

When there is a div that depends on another div, then we need
to be careful not to look for the other div in the variable
compression matrix.

isl_mat_variable_compression: fix use after free

isl_map_simplify.c: normalize_divs: ensure enough existentials are available

Before, we would assume that normalizing the divs could never
increase the number of existential variables, but as shown by
the added test case, this isn't always true.

isl_hash_table_remove: update number of entries

Otherwise, removing an element and later adding it back again
would increase the number of elements in the table, quickly
leading to overflows.

isl_map_simple_hull: plug memory leak

The leak was introduced in 4433b45d31f7f5461ee372a8a4aa2d3a955f96b5
(isl_map_underlying_set: align divs before calling this function).

add std::ostream &operator<<(std::ostream &os, isl_int i) (for C++ builds)

normalize divs involved in equalities

isl_map_underlying_set: drop names from dimesion in underlying set

When applying isl_mat transforamtions on sets, we currently
assume that these sets have no names for the dimensions.

add isl_mat_parameter_compression

isl_equalities.c: extract and export isl_mat_variable_compression

add isl_basic_set_is_empty

add isl_mat_right_kernel

add isl_mat_col_submul

add isl_seq_submul

isl_map_simplify.c: extract out simplify and related code from isl_map.c

isl_constraint: add limited support for adding divs

change calling conventions of isl_basic_set_has_defining_{,in}equalit{y,ies}

Before, these functions would only allow detection of defining
(in)equalities on set dimensions.  Rather than providing new
functions for detection on other kinds of variables, we generalize
the existing implementation to handle all kinds of variables.

add isl_basic_{set,map}_dim

isl_basic_map_gist: also exploit equalities in gisted set

Some inequalities in the gisted set may only be redundant
wrt the context inside the affine hull of the gisted set.
Although we did add the equalities to the (combined) context
before checking for redundancy, we did not perform any kind
of simplification in the combined context.
In particular, we did not perform any Gaussian elimination,
confusing the heuristic in isl_basic_map_constraint_is_redundant.

isl_basic_map_overlying_set: simplify resulting basic map

isl_stream: properly reference ctx

isl_stream.c: extracted from isl_input_omega.c

add isl_basic_set_read_from_str

export isl_set_compute_divs

isl_basic_map_align_divs: check divs of src basic map are known before sorting

isl_map_gist: ensure divs of map are known

We assume that the divs of the context are known, because we currently
only support gisting in the context of a basic map and computing the
divs of a basic map may result in a union of basic maps.

isl_basic_map_compute_divs: only (re)compute divs if any div is unknown

isl_basic_map_eliminate_vars: better handling of divs

In particular, if any div depends on one of the variables that is
being eliminated, then they should be eliminated too.
Furthermore, if a div is eliminated, then its definition should
be removed as well.

add isl_div abstraction, similar to isl_constraint

isl_basic_set_compare_at: combine constraints before setting up objective

The number of columns in the objective function should be equal
to the number of columns in the domain, but this number may change
during the call to add_constraints if bmap2 has any divs.

isl_map_underlying_set: align divs before calling this function

We need to know the meaning of the variables of the set returned by
isl_map_underlying_set in order to add it back in isl_basic_map_overlying_set,
but the number and the order of the existentially quantified variables
may change during a call to isl_map_align_divs.
We therefore need to call isl_map_align_divs first and use one of
the resulting basic maps as a model in our call to isl_basic_map_overlying_set.

isl_basic_map_overlying_set: properly handle divs in model

Before, we would extend the set after resetting the dimension
but before adding the divs from the model.  Any coefficients
in the divs would therefore not be copied.

isl_basic_map_align_divs: don't make assumptions on the number of divs in dst

In particular, we shouldn't assume that the number of divs in dst
is bigger than the number of divs in src.

We _can_ and do assume that any previous divs have already been aligned
so we don't need to check the next div against previously aligned divs.