isl_mat_drop_cols: special case dropping of zero columns

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

isl_tab_basic_map_partial_lexopt: better exploit partial solution cache

In 4fff507 (isl_tab_pip: keep cache of partial solutions,
Fri Oct 16 14:46:28 2009 +0200) we introduced a cache of partial solutions
so that we could attempt to merge them before adding them to the result.
The merging happens during backtracking, however, and once we reached
the end of the search tree, we would not backtrack back to the root anymore.

We now do track back to the root of the search tree such that partial
solution in the final part of the search tree could also potentially
be merged.  We only do this if there is some chance that we may find
identical partial solutions since the rollback of the context tableau
does not come for free.

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

isl_basic_map_lexopt: preinitialize domain

The original code would pass a universe domain to isl_basic_map_partial_lexopt,
but this means that the parametric integer programming engine will consider
all inequalities as splitting (with respect to the universe context),
resulting in a fair amount of wasted effort.
More importantly, the border constraints may be transferred to the
context in the middle of constraints that actually split the context
into parts with possibly different solutions.  The current heuristic
for merging solutions that turn out to be identical will not be able
to transfer solution across the border constraints since they only
allow for a solution on one side of the constraint.

By prepopulating the domain with some of the constraints from the input map,
we can avoid some redundant computations and we improve the opportunities
for merging identical partial solutions.

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

export isl_basic_map_drop_constraints_involving_dims

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

isl_basic_map_compute_divs: compress existentially quantified variables

This compression should simplify the computations during parametric
integer programming.

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

isl_basic_map_compute_divs: recursively remove parameter equalities

The removal of explicit equalities among the parameters may uncover
additional equalities.  If so, we now recurse in parameter_compute_divs
so that also these extra equalities are removed.
This will be important for the next commit where we will try to compress
the existentially quantified variables and this requires the absence
of equalities among the parameters.

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

isl_map.c: parameter_compute_divs: extract out first_parameter_equality

We will be able to reuse this function in the next commit.

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

isl_basic_set_parameter_compression: allow divs in input

For the purpose of compressing parameters, there should be no need
to make a distinction between set variables and existentially quantified
variables.
There does not appear to be any reason for not allowing existentially
quantified variables before other than the fact that we didn't need
to apply this function of basic sets with existentially quantified
variables before.  However, this will turn out to be useful when
we want to compress the unknown divs within isl_basic_map_compute_divs.

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

isl_basic_map_compute_divs: preserve already known divs

The purpose of isl_basic_map_compute_divs is to ensure that all divs
have an explicit representation.  If we already have an explicit
representation for some of the divs, then there is no need to
recompute an explicit representation for them.  Instead, we preserve
the explicit representations of the known divs and only compute
explicit representations for the currently unknown divs.

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

isl_basic_map_project_out: extract out insert_div_rows

The new insert_div_rows function will be reused in the next commit.

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

isl_basic_map_swap_div: extract out swap_div

The new swap_div will be reused in a subsequent commit.

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

Merge branch 'maint'

isl_map_coalesce: avoid dropping constraints redundant wrt implicit equalities

isl_map_coalesce first detects implicit equalities in the basic maps.
If two basic maps can indeed be coalesced, then fuse() would
only add this constraint to the fused basic map as an inequality.
Other constraints that imply that this constraint is actually an equality
are redundant with respect to the equality and would not get copied
inside fuse() either.  The end result is that we would lose information.

In principle, we could just modify fuse() to add the implicit equalities
to the fused basic map as equalities, but it seems more prudent to
turn them into explicit equalities from the start.

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

add isl_band_split

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

isl_schedule_get_band_forest: sort bands in band list

In particular if the partial schedule of the parent of a band list
assigns different constant values to the domains of the bands in the list,
then sort the bands according to those constant values.

This should provide for a more "natural" order to the user.
The need for sorting could be avoided entirely if we were to
construct a forest of bands directly from isl_union_set_compute_schedule.

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

declare isl_union_pw_multi_aff_intersect_domain

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

add tile_shift_point_loops option

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

add isl_union_pw_multi_aff_scale_vec

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

add isl_pw_multi_aff_scale_vec

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

add isl_multi_aff_scale_vec

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

isl_basic_map_simplify: avoid infinite loop on empty input

eliminate_divs_ineq skips the step of actually removing the div
if the basic map is marked empty.  This is needed because in the
process of marking the basic map empty, the constraints may have
been replaced by the canonical representation of an empty basic map
which does not have any divs.
However, the basic map may have already been marked empty before,
possibly without having the constraints replaced by the canonical
representation.  In such cases, we would also skip the step that
remove the div, but it would actually still be present and we would
keep making "progress" in every iteration of isl_basic_map_simplify,
resulting in an infinite loop.

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

generalize isl_union_pw_qpolynomial_sub to include isl_union_pw_multi_aff_sub

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

add isl_pw_multi_aff_sub

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

add isl_multi_aff_sub

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

generalize isl_multi_aff_add

In the short term, this generalization will be useful to implement
an isl_multi_aff_sub.

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

isl_basic_set_parameter_compression: extend assertion

We were only checking if the number of equalities is less than
or equal to the number of variables, while the code also assumes
that all of the equalities involves at least one variable.

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

isl_map.c: parameter_compute_divs: check result of isl_basic_set_gauss call

The return value has been completely ignored ever since the call
was introduced in 2bc8301 (isl_pip_basic_map_compute_divs: remove some
equalities first, Mon May 25 12:59:23 2009 +0200).  This may be harmless
in practice at the moment, but it may lead to future bugs.

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

isl_arg.c: drop_argument: avoid out-of-bounds array accesses

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

isl_map_gist_basic_map: avoid invalid access on error

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

isl_ast_build_ast_from_schedule: avoid introducing iterator in hoisted condition

ast_graft_list_fuse was being passed the build of the inner level from
create_node_scaled, which could result in the current loop iterator
getting introduced in the hoisted condition.
Since we need the inner build for simplifying the expressions generated
from the conditions that are not hoisted out, we now pass two builds
to ast_graft_list_fuse.

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

isl_ast_build_ast_from_schedule: make construction of ors in ifs optional

If disjunctions in if conditions are not allowed by the user, then
the node is duplicated and each each disjunct is inserted separately.

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

Merge branch 'maint'

isl_basic_set_sort_constraints: take into account all coefficients

The comparison function was mistakenly not taking into account
the coefficient of the last variable.  By ignoring this last
coefficient, the comparison could not guarantee the property required
by uset_gist.
Moreover, since constraints that only differ in this last coefficient
would compare equal to each other, the order of such constraints
could depend on the implementation of qsort, resulting in failing
test cases on Solaris 10.

We fix this problem by ignoring the constant term instead of
the last coefficient.  If two constraints only differ in the
constant term, then one of them should have been eliminated
already.

Reported-by: Amos <a.goo0h@gmail.com>
Tested-by: Marc Girod <marc.girod@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_ast_build_ast_from_schedule: fix unrolling corner case

In some rare cases, the constraint added to perform the unrolling
could get simplied away and then dropped after a simplification
of the domain.  We add the constraint back after the simplification
to ensure that it is present in the result.

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

isl_basic_map_uncurry: add missing isl_basic_map_cow

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

isl_basic_map_curry: add missing isl_basic_map_cow

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

codegen_test.sh: avoid use of constructs not supported by /bin/sh on Solaris

Reported-by: Amos <a.goo0h@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_arg.c: extract out free_child

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

isl_arg.c: extract out free_user

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

argument parsing: set structure field even if setter is available

If a setter is available for an option, we would only call the setter
and not make any changes to the structure field itself.  It turns out
that the first thing each of the setters does is to set the structure
field to the given value, so we might as well do that directly.
We set the value before calling the setter such that the setter can
still override the value.

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

argument parsing: handle --help option in order

In the original code, we would first scan for any --help option
before processing any other options.  Now we first consider the options
before --help.  If any of these options change the defaults for any other
options, then those changed defaults will be reflected in the --help output.

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

isl_map_simplify.c: check_for_div_constraints: also check for "better" ones

In check_for_div_constraints we check if two "opposite" constraints
can be used to define a div.  However, a given div may be definable
by multiple pairs of constraints and then we would just pick the pair
we come across.

We now also consider possible defining constraints for divs for which
we already have a definition, which makes the result less dependent
on the order of the constraints.

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

isl_aff_scale: special case scaling by a factor of the denominator

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

document that isl_local_space_get_div cannot be used on map spaces

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

codegen_test.sh: keep track of failure rather than exiting on first failure

If some change to isl changes the code generation output, we usually
want to see all such changes together.

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

Merge branch 'maint'

isl_ast_codegen.c: generate_domain: avoid infinite recursion

generate_domain checks if the inverse schedule is single-valued
so that the inverse schedule can be extended if needed.
Since this check is performed on the gisted inverse schedule,
it may fail even in a recursive call on an inverse schedule
that has been extended to ensure that it is single valued.
We may then end up in an infinite recursion.

To avoid this problem, we keep track of the fact that we have
already extended the inverse schedule to not be single-valued.
In such cases, we revert to the ungisted inverse schedule
if the gisted inverse schedule turns out not to be single-valued.

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

isl_schedule.c: fix typo in comment

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

isl_band_tile: set parent field of the child band

The original code would leave it pointing to the parent of the original
band, i.e., the grandparent of the child band.

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

isl_pw_multi_aff_drop_dims: fix dropping of output dimensions

Most isl_pw_*_drop_dims functions don't support dropping of output dimensions
because their pieces have a fixed single output dimension.
However, the pieces of isl_pw_multi_* objects do support dropping of output
dimensions and therefore so should the isl_pw_multi_*_drop_dims functions.

We simply need to skip dropping dimensions from the domains.
The original code would leave the result in an inconsistent state.

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

isl_ast_graft.c: extract_hoistable_guard: drop divs involving current depth

If the current guard involves any integer divisions that refer
to the dimension corresponding to the current depth, then the expressions
for these integer divisions will be invalidated after projecting out
this dimension.  This means that new expressions will have to be computed
and this may in some cases lead to complicated results with many subcases.
Such complicated guards will not be useful for the purpose of simplifying
the AST and so there is little point in hoisting such guards.

We therefore first drop any integer divisions that refer
to the dimension corresponding to the current depth.
This should typically lead to simpler hoisted guards.

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

declare isl_union_pw_multi_aff_to_str

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

declare isl_union_pw_multi_aff_dump

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

add isl_union_pw_multi_aff_read_from_str

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

add isl_union_pw_multi_aff_from_union_set

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

isl_ctx_free: properly free allocated options

The original code would only free the outer structure, without
freeing any of the internally allocated memory.

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

isl_union_map_alloc: project space argument onto its parameters

We are only interested in the parameters anyway, so we might as well
project out all the other dimensions.

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

isl_input.c: read_conjuncts: stop parsing conjuncts after first error

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

isl_input.c: accept_affine_factor: drop unexpected unknown identifier

accept_affine_factor errors out on seeing an unknown identifier, but
the identifier was incorrectly kept in the vars data structure,
possibly resulting in bad accesses if parsing continues after the error.

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

Merge branch 'maint'

interface/python.cc: add missing include

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

isl_ast_codegen.c: compute_class_domains: compute gist of class domains

The class domains may reference variables that been eliminated from
the "executed" map.  Constraints involving these variables may
therefore get accidentally reintroduced into the "executed" map,
which can render the AST build unable to detect whether the inner
"executed" map is single-valued, possibly causing an infinite recursion.
Plug in the values that caused the variables to be eliminated from
the "executed" map to remove any reference to them from the class domains.

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

isl_basic_map_from_constraint_matrices: (simplify and) finalize result

isl_basic_map_from_constraint_matrices belongs to the public API so it
should return a finalized basic relation.  The user probably expects
the result to be simplified as well.

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

isl_stream_read_map: allow anonymous unconstrained dimensions

In particular, allow a '*' in tuples to represent such anonymous
unconstrained dimensions.  The same syntax is used by Omega.

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

isl 0.11.1

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

isl_map_inline_foreach_basic_map: drop basic maps that have become empty

In particular, drop basic maps that have become empty in
isl_map_detect_equalities (which calls isl_map_inline_foreach_basic_map).

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

isl_hash_dim: make result independent of endianness

The result computed by isl_hash_dim may affect the order of maps
in a union map, which may in turn affect the result of AST generation.
In particular, we would generate slightly different output depending
on endianness, causing the tests to fail on big endian machines since
the generated output is compared to output generated on a little endian
machine.

Instead of hashing in the dimensions of the space as integers,
we now only hash in the least significant byte.
This has some effect on the results of AST generation, but the output
should now be the same on little endian and big endian.

Reported-by: Richard Biener <rguenther@suse.de>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_basic_map_move_dims: avoid invalid access on error

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

isl_basic_set_expand_divs: avoid invalid access on error

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

add LICENSE to the distribution

Reported-by: Richard Biener <rguenther@suse.de>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_schedule.c: add_inter_constraints: avoid invalid access on error

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

isl_schedule.c: add_intra_constraints: avoid invalid access on error

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

isl_tab_basic_set_non_neg_lexmin: handle NULL input

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

isl 0.11

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

isl_schedule.c: add_inter_validity_constraints: avoid invalid access on error

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

isl_tab_basic_set_non_trivial_lexmin: handle NULL input

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

isl_tab.c: push_union: handle NULL input

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

isl_mat_transpose: handle NULL input

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

isl_basic_map_foreach_lexopt: avoid invalid access on error

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

isl_pw_*_on_shared_domain_in: avoid double free on error path

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

isl_output.c: print_set_c: handle NULL input

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

isl_basic_map_eliminate_vars: avoid invalid access on error

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

isl_map_simplify.c: remove_dependent_vars: handle NULL input

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

isl_tab_pip.c: sol_pop: avoid invalid access on error

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

isl_basic_map_deltas: fix error handling

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

isl_ast_codegen.c: generate_sorted_domains: avoid invalid access on error

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

isl_test.c: test_ast: avoid invalid access on error

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

isl_parameter_alignment_reordering: fix error handling

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

isl_basic_map_normalize: avoid invalid access on error

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

isl_map.c: basic_set_maximal_difference_at: fix error handling

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

isl_convex_hull.c: map_simple_hull: avoid invalid access on error

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

isl_ast_codegen.c: compute_domains: avoid invalid access on error

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

isl_basic_map_is_empty: avoid invalid access on error

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

isl_space_extend: avoid invalid access on error

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

isl_map_subtract.c: basic_map_collect_diff: avoid invalid access on error

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

isl_basic_map_overlying_set: avoid invalid access on error

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

isl_map.c: basic_map_space_reset: handle NULL input

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

isl_basic_set_swap_vars: handle NULL input

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

isl_input.c: construct_constraints: respect memory management annotations

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

isl_ast_codegen.c: create_node: avoid invalid access on error

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