isl_reordering_extend_dim: don't mess with copies of input

In particular, perform an isl_reordering_cow before changing anythin.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_qpolynomial_insert_dims: properly handle named or nested spaces

For consistency, we remove any naming or nesting even if n == 0.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_qpolynomial_drop_dims: properly handle nested spaces

For consistency, we remove the nesting even if n == 0.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_qpolynomial_insert_dims: insert zero columns in div matrix

In order to insert dimensions, columns corresponding to
these extra dimensions need to be inserted into the matrix
representing the integer divisions.  Before, arbitrary columns
were being added, but the divs have zero coefficients for these
new dimensions, so we should make sure the columns are zero.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_qpolynomial_is_equal: also compare spaces and divs

Before, isl_qpolynomial_is_equal would only consider the "shape"
of the polynomial, meaning that two polynomial living in different
spaces could be considered equal.  Worse, expressions in terms
of different integer divisions could also be considered equal.
We now take into account both space and divs so that we no longer
produce false positives.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

bound.c: verify_point: make sure spaces of compared qpolynomials are the same

The current isl_qpolynomial_is_equal doesn't care about the space
in which a qpolynomial lives and so we were allowed to be sloppy before.
Unfortunately, the current isl_qpolynomial_is_equal also completely
ignores the definitions of the integer divisions, so it will have to
be fixed.  This means we can't be sloppy anymore.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_remove_divs_involving_dims: handle disappearance of divs

The internal call to isl_basic_map_remove_dims may remove more divs
than explicitly asked for (or it may reorder them) because it involves
a simplification step.  We therefore have to reconsider all the divs
after calling isl_basic_map_remove_dims.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_union_map_range_product: only consider pairs of maps with matching domains

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_mat_scale_down: avoid trampling over aliased matrices

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_qpolynomial_* constructors: check dim before accessing fields

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_range: correctly handle maps with 0D domains

Internally, sets are represented as maps with unnamed, unstructured
0D domains.  isl_map_range takes advantage of this fact, but only
checked for 0D domains.  This was correct when isl_map_range was added,
but it should have been updated when named and structured spaces were
introduced.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_list.h: allow inclusion from C++

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip: don't simplify domain in isl_for_add

As the comment above the function explains, the domain should not
be simplified.  Unfortunately, an isl_basic_set_simplify snuck in
in 8b88ebf (isl_tab_pip.c: remove some code duplication between
isl_map_add and isl_for_add, Fri Oct 16 14:10:59 2009 +0200).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_affine_hull: finalize result

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab: alway free saved basis undo record

Before, it would only get freed if it was actually used.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

make sure destination for GDB module exists before installing

Usually, this directory already exists because the library has
been copied there, but during a parallel make install this may
not have happened yet.

Reported-by: dirtyepic <dirtyepic.sk@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip.c: add_lexmin_eq: remove misguided optimizations

After adding a pair of inequalities corresponding to the equality,
the code tries to reduce the dimensionality of the problem by
removing a column.  If one of the added constraints happens to have
been pivoted into a column, then it can easily be removed.
Otherwise, the code tries to pivot the row into a column and
then remove the column.

This pivot may disrupt the lexico-positiveness of the columns however.
At the first least, the code should check that the pivot entry
is negative, but it should also avoid pivoting out a column corresponding
to a parameter.

Since this optimization shouldn't have that much of an effect anyway,
we choose here to just remove it for now.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: fix handling of divs in tuples

Supoprt for them was broken in f1ea969 (isl_stream_read_map: treat divs
as output variables while adding constraints, Thu Mar 17 16:29:06 2011 +0100).
When treating divs as output variables, we need to make sure that
each of them is backed by a variable in the list of active variables.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_mat_left_hermite: plug memory leak on error path

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

plug memory leak in isl_mat_product

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl 0.06

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

doc: add some implementation details on parametric integer programming

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_lp.c: avoid clang warning

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept floord and ceild expressions in constraints

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept min and max expressions in constraints

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: properly read nested divs

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: treat divs as output variables while adding constraints

This will allow us to more easily handle other extra variables.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_coalesce: plug memory leak on error path

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_mat_extend: avoid memory leak when realloc fails

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_overlying_set: avoid memory leak when realloc fails

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_getc: avoid memory leak when realloc fails

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

rudimentary support for asynchronous termination of computations

Most operations end up using a tableau at some point, so we
currently only check for the termination condition during pivoting.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

hide isl_ctx internals

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_vec_read_from_file: drop input_format argument

Ideally, we should autodetect the input format and we currently
only support one format anyway.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map.c: drop unused error label

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_input.c: drop unused error label

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

respect DESTDIR when installing isl.py

Reported-by: Kpucko <slashdevslashzerr0@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: accept "$" token

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_union_map_power

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

change isl_map_power interface

The old interface could not be extended to union maps, while
the new interface exploits nested spaces.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_union_map_zip

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add private isl_basic_map_swap_vars

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_union_map_deltas_map

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

Merge branch 'maint'

isl_map_deltas: don't copy flags from input

The deltas sets of disjoint relations may not be disjoint
and the entire result will not be normalized.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept constant expressions of the form x^y

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: accept "/\" and "\/" as alternatives for "and" and "or"

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: only quote newline using '\'

This is all we need to support line continuation.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: maintain private ungetc buffer

We may want to unget more than one character.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_set_lifting: simplify and finalize result

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

doc: fix typo

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

doc: drop long outdated note on transitive closures

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_set_get_dim_name

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_identity: take dimension specification of map as input

Before, isl_basic_map_identity and isl_map_identity would take
the dimension specification of a set as input, but this could be
confusing for users.  Moreover, by taking the specification of a map
as input, we can now also construct canonical mappings between spaces
with the same dimension, but with different names or internal structure.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

rename isl_dim_map to isl_dim_map_from_set

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

transitive closure: project out parameters when any constraints are impure

The resulting delta set can lead to extra constraints on the path,
resulting in a possibly more accurate approximation.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

privately export isl_basic_set_reset_dim

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_set_lift: preserve structure of space

Before, we would simply add extra variables to the dimension specification,
if needed, destroying any internal structure.  Now, we retain the original
dimension specification as the domain of a wrapped map.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_pw_qpolynomial_bound: handle combination of wrapping and existentials

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip.c: fix typo in comment

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab: check for obviously empty tableaus after discovering an equality

After a new equality has been discovered, it may turn out that one
of the coordinates is stuck at a non-integral value.  If so, we can
mark the tableau empty.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_gist: prefer contraints without existentially quantified variables

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_sort_constraints: change comparison routine

In particular, before we would simply sort the constraints lexicographically.
Now, we first check for the last non-zero coefficients and only when those
positions are the same do we continue with the lexicographical order.
The new ordering is the same as that used to order divs in isl_polynomial.c

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_ineq_type: classify more constraints as being adjacent to an inequality

In particular, if one constraint b is equal to a c * (-1 - a), with c
a positive constant and A some other constraints, then b can also
be considered to be adjacent to a as relaxing a by one will result
in an overlap with b.  Note that if c is larger than one, then a
will not be considered to be adjacent to b, so this change will not
affect pairs of inequalities.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_coalesce: be more relaxed about multiple equalities being adjacent

We try to avoid wrapping in a basic map that has multiple equalities
that are adjacent to inequalities in the other basic map, because that
may lead to more complicated constraints.
The original check would, however, also prevent the extension of
one basic map with an other if they happened to lie in a shared
affine subspace.  By moving the test for multiple equalities after
the check for extensions, we allow such extensions, while still
preventing undesired wrapping.

We can probably do better by explicitly detecting and exploiting
the shared affine subspace.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_map_from_domain_and_range

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_set_neg

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_set_flat_product

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

export isl_basic_map_flatten

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_map_from_qpolynomial

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: support \<newline> line continuation

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_union_map_read_from_file

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept 'true' and 'false' constraints

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: allow extra ';' at end of map description

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: allow negations

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: allow existential quantification over disjunctions

Before, we would only allow existential quantification within a single
disjunct because the existentially quantified variables were being
added directly to a basic map.
Now, we first add extra output variables and project them out at the end.
The disadvantage is that we currently lose any explicit definition of
the existentially quantified variables in the input.  Usually, we can
recover them from the constraints that are added when we meet such a
definition, but it does require some extra processing.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

privately export isl_basic_map_add_div_constraints_var

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_morph_basic_set: preserve rationality of input

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_set_is_rational

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_printer_print_basic_map: explicitly mark rational maps

isl_stream_read_map: read rational maps

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_insert: preserve rationality of input

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_basic_map_set_rational

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_fast_cmp: differentiate between rational and integer sets

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_output.c: remove some code duplication

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_printer_print_basic_{set,map}: don't start new line in isl format

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept '|' at start of constraints

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream: keep track of textual representation of tokens for better error reporting

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_input.c: clean up read_disjuncts

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_stream_read_map: accept disjunctions within a conjunct

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_convex_hull.c: explicitly mark wrapping lp problem as rational

This shouldn't have any effect at the moment, but in future we may
want to be more aggressive on non-rational tableau.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_min: micro-optimization: postpone taking into account denominator

The denominator of the affine expression shouldn't have any effect
on the point where the minimum is reached.  Moreover, for non-rational
tableaus, it may be confusing for future optimizations to have a row
that may attain rational values.  It is therefore beter to multiply
in the denominator after the optimum has been computed.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

Merge branch 'maint'

isl_tab_add_row: add further explanation

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab.c: fix typos in comments

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip.c: correctly detect non-negativity of divs in lexmin contexts

In particular, the variables used to encode the div in the context
tableau is always non-negative, but the actual variable used in the main
tableau may not be non-negative.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add test

test both context handling mechanisms of isl_pip

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_is_equality: properly support "big parameter"

An attempt was made in 40b68af (isl_tab: introduce support for "big parameters",
Wed Aug 5 10:22:52 2009 +0200), but the change to isl_tab_is_equality
was incomplete.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip.c: fix typo in comment

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>