isl_test: generalize subset test

This will make it easier to add additional test cases.

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

rename isl_set_dim_has_*_bound to isl_set_dim_has_any_*_bound

The original names more accurately describe functions that check
that there is a bound in each of basic sets.

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

relicense isl under the MIT license

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Andreas Kloeckner <kloeckner@cims.nyu.edu>
Signed-off-by: Todor Stefanov <stefanov@liacs.nl>
Signed-off-by: Sven van Haastregt <svhaastr@liacs.nl>
Signed-off-by: Isabelle Ryl <isabelle.ryl@inria.fr>
Signed-off-by: Mythri Alle <mythri.allel@gmail.com>
Signed-off-by: Wim De Clercq <Wim.DeClercq@lrd.kuleuven.be>
Signed-off-by: Anne Cormier <Anne.Cormier@ens.fr>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

configure.ac: link against same LLVM components as libclang.so

Since 74e0407 (configure.ac: only link against libraries from LLVM
analysis component, Wed Jan 18 16:47:38 2012 +0100), we only link
against some components of LLVM, but the choice of which components
to include was made fairly arbitrarily.
This appeared to work, but fails do so on more recent versions of clang.
Instead, we now link against the same LLVM components as libclang.so.

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

Merge branch 'maint'

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

isl_map_intersect: fix error handling

The original code would simply drop basic sets that resulted in errors
instead of propagating the error to the caller.

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

isl_access_info_add_source: plug memory leak on error path

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

isl_set_dim_residue_class: correctly consider all basic sets in the set

This commit fixes two closely related problems.
Due to a typo, isl_set_dim_residue_class would only consider one of
the basic sets in the input set.  The information obtained from the
individual basic sets was also combined incorrectly.
In particular, the code would insist that all basic sets have the
same residue if they have the same modulo and not consider adjusting
the modulo of the combined basic sets to accommodate for the difference
in residues.

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

isl_map_subtract: handle duplicate divs in subtrahend

A simplified basic map is not expected to have duplicate divs,
but it may still happen if a div is discovered by isl_basic_map_gauss
without subsequently being compared to other divs.

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

isl_aff_scale_down: check for scaling down by zero

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

add isl_*_list_drop

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

isl_*_list_add: dynamically grow list to accomodate extra element

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

configure.ac: don't allow installation in source or build directory

This will fail at some point during the installation anyway,
so it's better to check early.

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

add isl_space_is_range

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

export isl_space_is_domain

We cannot simply export the private isl_space_is_domain however, since
that one is also used in cases where the first argument is a parameter
space and the second argument is a set space.

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

doc: document isl_space_is_equal

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

add isl_space_is_map

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

declare isl_pw_multi_aff_project_domain_on_params

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

add isl_map_has_tuple_name

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

AUTHORS: add Mythri Alle

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

isl_printer_free: return NULL

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

declare isl_pw_multi_aff_drop_dims

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

export isl_multi_aff_gist_params

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

extract common implementation of Tarjan's algorithm

We had two nearly identical implementations in isl_schedule.c
and isl_transitive_closure.c.

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

add isl_point_dump

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

isl_union_map_extract_map: ignore parameters in space argument

They may be different from the parameters in the isl_union_map, while
they are irrelevant for determining which map to extract.

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

isl_union_map_extract_map: rename dim argument to space

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

isl_map_simplify.c: eliminate_var_using_equality: normalize divs after elimination

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

isl_stream_read_map: force result to be a map

In particular, if obj_read returns a set, then turn it into a map.

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

isl_stream_read_map: accept rational affine expressions

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

add isl_map_{lexmin,lexmax}_pw_multi_aff

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

declare isl_map_remove_unknown_divs

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

doc: document isl_set_remove_unknown_divs

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

declare isl_map_remove_divs_involving_dims

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

add isl_basic_set_remove_divs_involving_dims

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

doc: document isl_set_remove_divs_involving_dims

This function is used by CLooG.

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

add isl_basic_set_eliminate

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

add isl_union_set_from_basic_set and isl_union_map_from_basic_map

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

add isl_basic_{set,map}_insert_dims

We already had a (private) isl_basic_map_insert, but we rename it to
isl_basic_map_insert_dims for consistency with isl_map_insert_dims.

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

add isl_basic_{set,map}_align_params

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

add isl_union_map_domain_product

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

declare isl_basic_map_product

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

add isl_pw_multi_aff_product

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

add isl_pw_multi_aff_union_{lexmin,lexmax}

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

isl_set_free: return NULL

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

add isl_multi_aff_lex_{le,ge}_set

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

declare isl_multi_aff_get_domain_space

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

add isl_multi_aff_identity

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

add isl_aff_neg_basic_set

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

add isl_aff_add_constant_num{,_si}

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

add isl_id_list

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

add isl_*_list_set_*

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

add isl_pw_multi_aff_has_tuple_name

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

declare isl_pw_aff_get_tuple_id

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

add isl_map_has_dim_name

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

add isl_local_space_has_dim_id and isl_local_space_get_dim_id

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

isl_set_opt: align parameters

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

isl_multi_*_set_*: check that parameters and domains match

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

isl_basic_map_range_product: check that parameters match

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

isl_basic_map_simplify: eliminate known divs that appear with unit coefficient

They can be eliminated without loss of accuracy and this elimination
results in "simpler" constraints.

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

isl_basic_map_remove_divs_involving_dims: insert bounds before removing divs

The div will be removed using Fourier-Motzkin elimination and the extra
bounds can be used to improve accuracy of the result.

For example, eliminating the div from the following set

{ [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }

we now first use the first constraint to derive a lower bound
on the div:

[(i + 2j)/4] >= [-3/4] = -1

During the elimination, this bound can be combined with the upper bound
to result in the additional constraint

k >= -2

Although this technique can be applied in general, it is especially
useful after the next commit, where we will eliminate divs
that appear with a unit coefficient.  If the same div also appears
in other constraints with a non-unit coefficient, and we later
decide to eliminate the div, then this technique can be used to
recover some of those constraints so that we can avoid losing accuracy.

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

isl_basic_map_simplify: normalize div expressions

That is, remove common divisors in numerator and denominator.

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

Use an MIT licensed mergesort as the sorting algorithm for isl

This patch replaces the old LGPL licenced quicksort implementation taken
from glibc.
The call sites are adjusted to the fact that isl_sort can now fail
(due to failed memory allocation).

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_access_info_free: return NULL

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

add isl_printer_print_double

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

doc: add a note on isl_dim_type

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

doc: add a note about isl_*_intersect and parametric sets

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

doc: add missing documentation for some scheduling options

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

Merge branch 'maint'

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

isl_pw_*_realign_domain: plug memory leak on error path

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

isl_handle_error: avoid use of isl_options_get_on_error

isl_options_get_on_error could end up calling isl_handle_error
recursively, resulting in an infinite calling sequence.

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

isl_space_extend_domain_with_range: handle ranges with a nested space

The original code would only take into account the number of dimensions
and the tuple name.

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

isl_map_eliminate: check for overflow in computation of last dimension

In particular, if the computation of the last dimension overflows,
then at least one of the dimensions is out of bounds.

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

isl_*_eliminate: update comments to reflect recent change

In particular, since baf22b7 (isl_*_eliminate: perform integer elimination,
Tue Apr 17 12:29:41 2012 +0200), the elimination is no longer performed
using Fourier-Motzkin (unless the input is marked rational).

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

Merge branch 'maint'

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

isl_multi_aff_set_dim_name: do not set name of elements if type is isl_dim_out

An isl_aff does not keep track of the name of its output dimension.
Even if it did, we would have to change the name of only the specified
element and not of all elements as we did before this commit.

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

add doc/SubmittingPatches to the distribution

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

doc: fix typos

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

isl_*_eliminate: perform integer elimination

The original code would perform the elimination "rationally" by
simply applying Fourier-Motzkin on them.  If the input
is an integer set or map, this could drop information on other dimensions.
For example, eliminating the second dimension of

        { [i, j] : i = 2 j }

would result in

        { [i, j] }

while it should result in

        { [i, j] : exists a : i = 2 a }

We now perform an integer elimination (on integer sets and maps).

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

privately export isl_basic_map_insert

We need it in the next commit.

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

isl_hash.c: reset the number of entries to 0 when growing the hash table

The hash table is grown by creating a new table and adding the entries
of the old table to the new table.  Since the new table starts out as
being empty, the number of entries should be reset to 0.

Not only would the old code result in isl_union_map_n_map returing
the wrong value if the underlying hash table had ever been grown,
it would also result in the table subsequently being grown again
far too early.

Signed-off-by: Mythri Alle <mythri.alle@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_flow.c: merge isl_restriction_none and isl_restriction_empty

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

isl_tab_basic_map_partial_lexopt: don't normalize intermediate div expressions

The function get_row_parameter_div would call normalize_div before finishing
the construction of the div expression.  In particular, it would call
normalize_div before negating the coefficients.  Since normalize_div may round
down the constant term, the result of first normalizing and then negating
may result in a different div than first negating and then normalizing.
Call normalize_div only after negating the coefficients.

Reported-by: Alexandre Isoard <alexandre.isoard@ens-lyon.fr>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl 0.10

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

isl_space.c: avoid icc warning

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

isl_schedule.c: fix types of enum isl_edge_type iterators

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

isl_input.c: construct_constraints: avoid icc warning

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

isl_handle_error: fix type of error argument

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

update AUTHORS

add isl_map_order_lt

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

isl_space_unwrap: fix error message

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

Merge branch 'maint'

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

isl_union_set_compute_schedule: fix computation of maximal number of rows

The original computation wasn't documented, but was probably wrong.
The maximal number of schedule rows is now computed in a separate
and documented function.

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

isl_space_insert_dims: fix handling of nested spaces

In particular, if we are inserting parameters, then we should also
insert them in any nested spaces.

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

isl_restriction_{none,empty}: "take" argument for consistency

The other isl_restriction constructors "take" their arguments,
so it seems more consistent for isl_restriction_none and
isl_restriction_empty to do so as well.

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

Add isl_restriction_get_ctx

Signed-off-by: Andreas Kloeckner <inform@tiker.net>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_space.c: document name_ok

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

Merge branch 'maint'

Call finalize in isl_basic_map_set_dim_name

Signed-off-by: Andreas Kloeckner <inform@tiker.net>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_space_set_dim_name: handle NULL name

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