isl_ast_build_set_loop_bounds: compute divs after eliminating strided dimension

Although it is unlikely that the elimination would result in any unknown divs,
we had better make sure to preserve the invariant that build->domain does not
have any unknown divs.

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

isl_map_simplify.c: normalize_divs_in_context: improve error handling

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

isl_map_simplify.c: div_is_redundant: ignore coefficients of unknown divs

If a div is unknown, then its coefficients are undefined so we should
not take them into account while checking if some other div is redundant.
In rare cases, looking at those undefined coefficients could result
in system dependent behavior.

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

isl_ast_build_ast_from_schedule: properly handle union atomic options

In particular, if the domain for which a given dimension should
be atomic is a union of basic sets, then the actual atomic domain
may be larger than this union and we need to make sure that this
larger set is removed from the remainder domain to preserve
the invariant that the elements of the list computed by compute_domains
are disjoint.

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

isl_ast_codegen.c: update_unrolling_lower_bound: check for overflow

If the number of slices along a given lower bound exceeds the maximal
value of an integer, then it would mistakenly be replaced by its
least signficant bits, resulting in slices being dropped if the lower
bound ends up being selected as the best (based on the wrong number).
If the number of slices really exceeds the maximal value of an integer,
then we do not want to honor the request of the user anyway.
We should probably set an even smaller limit.

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

isl_basic_map_insert_dims: plug memory leak when called on empty input

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

ChangeLog: drop some text that appears to have been copied by mistake

In particular, the text was copied by 9fe3e28 (isl 0.10,
Sun Jun 3 15:47:09 2012 +0200).

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

isl 0.11.2

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

add missing interface/all.h and interface/isl.py.top to distribution

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

isl_schedule_get_map: pad schedule map with zeros if reconstructed from bands

The schedule map extracted from the isl_schedule_nodes is padded with zeros
by construction.  However, if the schedule map is reconstructed from the
band forest, then the schedule map was not be padded with zeros.
Pad this schedule as well.

We may want to change isl_band_list_get_suffix_schedule to perform this
padded instead.

Reported-by: Ali El Moussawi <elmoussawi.ali@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_ast_node_print: avoid duplicate declarations in printed code

If a loop has only one iteration but if the expression
for this single iteration is too complicated to be substituted into the AST,
then the expression is assigned to a variable corresponding to the loop
iterator.
If two such loops occur in the same block, then we would end up with
two declarations of the same variable.  Avoid this problem by introducing
a block around the declaration if it appears in a sequence of statements.

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

isl_ast.c: extract out start_block and end_block from print_ast_node_c

We will be able to reuse them in the next commit.

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

configure.ac: explicitly link in llvm bitreader component in extract_interface

Apparently, the bitreader component is required for ASTReader and
is no longer included implicitly.

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

update for change in arguments of clang's HeaderSearchOptions::AddPath

In particular, the IsUserSpecified argument has been removed.

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

update for change in arguments of clang's CompilerInstance::createDiagnostics

In particular, CompilerInstance::createDiagnostics no longer takes
argc and argv as arugments.

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

isl_tab_basic_map_partial_lexopt: disable use of shifted tableau on equalities

If the input context already involves equalities then the shfited tableau
is not used as it would be empty.  However, if equalities are added at
a later stage (e.g., transferred for the input map), then we would fail
to disable the use of the shifted tableau, possibly resulting in invalid
sample values being computing from this shifted tableau.

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

isl_tab_pip.c: context_gbr_detect_equalities: improve error handling

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

isl_basic_map_foreach_lexopt: properly merge partial solutions

If we detect two identical solutions in adjacent parts of the search space,
then we merge them into a single solution.  The combined domain may however
have fewer existentially quantified variables and so we also need to adjust
the matrix representing the solution on that domain to no longer refer
to the extra existentially quantified variables.  Otherwise, the code
in sol_for_add could end up accessing elements of aff->v outside its bounds.
Note that it is safe to remove the columns that refer to the extra
existentially quantified variables since their coefficients need to be zero
for the two partial solutions to be considered identical.

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

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>

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>

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

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 0.11.1

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>

isl_ast_codegen.c: for_inc: handle NULL input

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

isl_pw_aff_set_rational: avoid invalid access on error

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

isl_vec_dup: avoid invalid accesses on error

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

isl_map.c: map_intersect_internal: properly plug memory leak on error path

The proposed fix in f85421c (isl_map.c: map_intersect_internal: plug memory
leak on error path, Fri Nov 30 18:10:08 2012 +0100) would only free "result",
but not "part".  Revert that commit and make sure both are freed.

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

update for change in the constructor of the clang Driver

In particular, the Driver constructor no longer takes an IsProduction argument.

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

isl_vertices.c: vertices_from_list: plug memory leak on error path

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

isl_basic_set_compute_vertices: plug memory leak on error path

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

isl_test.c: fix typo

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

isl_test.c: test_output: avoid invalid access on error

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

isl_test.c: before_for: return early on error

In particular, don't print any spurious error messages.

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

isl_test.c: test_sample: return early on error

In particular, don't print any spurious error messages.

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

isl_tab_pip.c: find_in_pos: plug memory leak on error path

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

isl_tab_pip.c: add_parametric_cut: plug memory leak on error path

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

isl_tab_pip.c: sol_push_sol: plug memory leak on error path

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

isl_space_dup: avoid invalid accesses on error

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

isl_schedule.c: add_*_constraints: avoid invalid accesses on error

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

isl_reordering_extend_space: fix error handling

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

isl_multi_*_realign_domain: plug memory leak on error path

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

isl_map_subtract.c: map_is_subset: fix error handling

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

isl_map.c: update_dim_opt: return early on error

In particular, don't print any error messages based on the number
of elements in the list if the list doesn't exist.

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

isl_basic_map_underlying_set: plug memory leak on error path

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

isl_map.c: map_intersect_internal: plug memory leak on error path

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

isl_ast_build_init_derived: check build->domain

If something has gone wrong during the construction of the isl_ast_build,
its domain field may be NULL.  Since isl_ast_build_get_ctx obtains
the isl_ctx from this field, we should not continue if build->domain is NULL.

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

isl_input.c: read_aff_domain: remove spurious vars_free on error path

The vars structure passed to read_aff_domain is owned by the caller.

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

isl_input.c: read_map_tuple: return early on error

This avoids spurious error messages.

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

isl_input.c: accept_affine_list: plug memory leak on error path

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

isl_affine_hull.c: equalities_in_underlying_set: plug memory leak on error path

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

isl_tab_detect_equalities: plug memory leak on error path

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