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>

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_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>

isl_basic_map_zip: always call isl_basic_map_cow

We were relying on isl_basic_map_swap_vars calling isl_basic_map_cow for us,
but if no actual swapping needs to be performed (because the number
of variables to swap is zero), then isl_basic_map_swap_vars will not call
isl_basic_map_cow.

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

isl_morph.c: add_strides: clear newly added divs

Although we know what the divs should look like, we leave it to
isl_basic_map_simplify to extract them from the equalities we add.
However, we should at least mark them as (initially) unknown as
isl_basic_map_simplify may perform some other simplifications based
on the div expressions.

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

isl_tab_pip.c: fix typos in comment

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

isl_test: be more verbose

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

isl_aff_floor: add special case for constant arguments

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

doc: explain isl_*_is_subset

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

isl_map_order_gt: add special case for ordering a dimension wrt itself

Ordering a dimension with respect to itself isn't very useful, but we
should still produce the correct result.

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

add tests for isl_map_oppose

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

isl_map_equate: add special case for equating a dimension to itself

Equating a dimension to itself isn't very useful, but we should still
produce the correct result.

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

add isl_schedule_foreach_band

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

add isl_band_list_foreach_band

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

add isl_band_tile

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

add isl_band_dup

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

isl_schedule.c: extract out isl_band_alloc

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

isl_schedule_get_map: extract schedule from band forest if available

In the next commits, we will allow the user to modify the band forest.
This means that the schedule represented by the modified band forest
may not be the same as the schedule that was originally computed.
We therefore need to extract it from this forest if the forest
has been constructed already.

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

isl_band.c: extract out isl_band_list_get_suffix_schedule

This cleans up the code a little bit and will be useful in the next commit.

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

isl_band: use isl_union_pw_multi_aff to represent partial schedule

An isl_multi_aff is a more natural representation for the kind of schedules
we are constructing and will make it easier to perform tiling.

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

isl_schedule_node: represent schedule using isl_multi_aff

An isl_multi_aff is a more natural representation for the kind of schedules
we are constructing and will make it easier to perform tiling on the resulting
bands.

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

isl_union_set_compute_schedule: separate components by default

Serialize (weakly connected) components by assigning them separate
values at an outer dimension by default.
Although it is possible for independent components to be executed
in parallel, it is usually not a good idea to do so.

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

isl_union_set_compute_schedule: components may also involve proximity edges

When looking for (weakly connected) components, we used to only consider
validity dependences, but the presence of a proximity dependence may
also be a reason for keeping two nodes together.

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

isl_union_set_compute_schedule: also keep track of proximity edges in hash table

We don't use this additional hash table yet, but we will need it the next
commit. A separate hash table is needed because the entries are keyed
by the source and destination node, so there can be only one edge
between a given pair of nodes in a single table.

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

isl_schedule.c: extract out graph_edge_table_add

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

isl_union_set_compute_schedule: only carry validity dependences

If we are forced to try and carry come dependences because of some conflict,
then we only need to carry those dependences that may lead to a conflict.
That is, we only need to carry validity dependences.

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

isl_schedule.c: simplify computation of number of constraints

Instead of telling count_constraints how many times it should
count any given constraint, we now tell it whether we want to
compute the number of constraints for the main LP or for the
carrying LP.

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

isl_schedule.c: fix typos in comments

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

add isl_basic_map_is_single_valued

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

add isl_basic_map_equate

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

add isl_basic_set_get_dim_id

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

add isl_printer_get_output_format

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

add isl_local_space_has_dim_name

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

add isl_constraint_get_local_space

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

add isl_constraint_is_{lower,upper}_bound

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

add isl_basic_set_n_constraint

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

doc: document isl_basic_set_foreach_constraint

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

add isl_set_has_tuple_name

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

add isl_space_has_tuple_name

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

isl_aff_private.h: add missing include

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

add isl_seq_dump

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

add isl_printer_get_file

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

add isl_union_map_curry

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

isl_space.c: avoid use of "0" as pointer value

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

add isl_map_order_gt

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

add isl_map_from_aff

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

isl_args_parse: optionally ignore --help

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

move generic part of isl_union_pw_qpolynomial_mul to isl_union_templ.c

This simplifies the interface of match_bin_op, even though it is currently
only used in one place.

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

add isl_union_pw_multi_aff_flat_range_product

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

isl_pw_*_on_shared_domain: allow specification of target space

We will need exploit this possibility in the next commit.

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

add isl_union_map_from_union_pw_multi_aff

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

isl_aff.c: fix typo in comment

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

add isl_union_pw_multi_aff_from_domain

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

add isl_union_pw_multi_aff

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

isl_union_pw_*: don't assume zero is the default value

Although we consider an isl_pw_qpolynomial to be zero by default,
we will not do so for the isl_pw_multi_affs we will introduce next.

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

add isl_pw_multi_aff_from_multi_aff

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

export isl_multi_aff_set_aff

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

add isl_multi_aff_zero

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

add isl_map_from_multi_aff

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

isl_basic_set_parameter_compression: use isl_vec_set

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

isl_flow.c: use public isl_vec interface

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

add isl_vec_set_si

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

add isl_vec_set

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

add public isl_vec interface

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

add isl_seq_set_si

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

isl_union_pw_*_free: return NULL

Returning NULL helps to simplify error handling code.

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

split off declarations of isl_union_map and isl_union_set

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

isl_map_deltas: add memory management annotations

Signed-off-by: Riyadh Baghdadi <baghdadi.m.riyadh@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_access_info: change interface for specifying restrictions

The original interface would only allow the user to restrict the source
iterations, while the user may also want to restrict the sink iterations.
The new interface also makes it more convenient for the user to specify
that no restriction should be applied and allows for a restriction
on the result of the maximization problem.

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

isl_map_coalesce: only coalesce pairs of basic maps with the same divs

Most of the heuristics won't be able to find any coalescing opportunities
on basic maps with different divs, so it's not worth it to even try.
A notable exception is the subset test, which is now handled separately.

Since we only perform the tests after checking that the divs are the same,
there is no point in aligning the divs over all basic maps.  This could
be a very expensive operation, especially if some divs are unknown as it
would then compute explicit representations for all divs.  This could have
the counter-intuitive effect that the ouptut of isl_map_coalesce would have
_more_ basic maps (because of the splits introduced during the computation
of explicit representations) than the input.
Instead, we know simply sort the known divs.

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

isl_coalesce.c: change interface of {in,}eq_status_in

We will want to call them on a modified basic map in the next commit.

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

add isl_map_sort_divs

Sorting divs should improve the effectiveness of isl_merge_divs.

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

add isl_set_coalesce test case

We will be making changes to isl_map_coalesce and we want to make sure
we won't break this case.

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

add isl_basic_map_get_divs

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

isl_merge_divs: handle NULL input

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

Merge branch 'maint'

isl_local_space_alloc_div: fix error handling

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

isl_union_set_compute_schedule: ignore backward proximity edges on split

Proximity edges are not taken into account during the detection
of strongly connected components.  When we split the dependence graph
based on these SCCs, we may therefore have proximity edges that go
back from a SCC behind the split to a SCC ahead of the split.  These should
be ignored, just like those edges that go from ahead of the split to behind
the split.

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

isl_basic_map_insert: preserve emptiness

isl_basic_map_plain_is_empty doesn't look at the constraints but only
at the ISL_BASIC_MAP_EMPTY flag.  We therefore need to make sure the
flag is set on the output of isl_basic_map_insert if it was set on the
input.

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

isl_basic_set_total_dim: handle NULL input

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

isl_term_get_div: support nested divs

Ever since 028d1a7 (drop isl_div abstraction, Fri Sep 9 14:55:16 2011 +0200),
the result of isl_term_get_div is an isl_aff and it can handle nested divs
just fine.  We therefore simply need to remove the now redundant check.

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