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>

isl_ast_codegen.c: after_each_for: add missing return on error path

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

reintroduce isl_basic_set_add symbol

This function was renamed in 461a2cd (rename isl_basic_set_add to
isl_basic_set_add_dims, Mon Oct 1 10:55:08 2012 +0200), but it appears
that it is being used by CLooG.  Reintroduce the symbol for backward
compatibility, but mark it "deprecated" so that it will hopefully
not be used by new users.

Reported-by: Jack Howarth <howarth@bromo.med.uc.edu>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_union_map_uncurry

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

configure.ac: check if TargetInfo::CreateTargetInfo takes TargetOptions pointer

Newer versions of clang take a pointer, while older versions take a reference.

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

interface/extract_interface.cc: take TargetOptions object from CompilerInstance

The memory management of TargetOptions has changed in recent clangs.
Taking TargetOptions from the CompilerInstance seems to work in both
older and newer versions of clang.

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

AST printing callbacks: pass isl_ast_print_options

The callback may want to pass control back to isl_ast_node_*_print,
for which it needs an isl_ast_print_options object.  Since the
caller of the callback already has a reference to such an object,
we might as well pass it along to the callback.

Since the callback may want to modifiy the isl_ast_print_options
object, we turn it into a properly reference counted isl object.

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

doc: fix typo

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

add before_each_for/after_each_for callbacks

isl_ast_build_from_context: allow unnamed set dimensions

The original code would assume all dimensions have an associated isl_id.

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

isl_basic_map_gist: drop irrelevant constraints from the context

The context may contain constraints on variables that do not even
appear in the input basic map.  The constraints therefore cannot
be exploited to simplify the input and only serve to make some
of the internal computations more expensive, in particular the
computation of the affine hull of the intersection of input and context
and the emptiness checks used in the final determination of
the redundancy of a constraint.
It's therefore more efficient to remove those irrelevant constraints.

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

isl_map_simplify.c: fix typo in comment

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

isl_ast_build_eliminate_divs: remove unknown divs before divs involving depth

Occasionally, eliminating unknown divs may turn other unknown divs
into known divs, which may depend on the current depth.

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

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

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

change prototype of isl_factorizer_dump

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

isl_tab_sample: perform greedy search before performing basis reduction

While basis reduction is very useful on difficult problems, it is
overkill on easy problems.  In fact, the basis reduction computation
can be quite expensive, especially in the presence of large coefficients.
This may happen in particular during the affine hull computation
when only a few sample points have been found so far.  If these
points have large values, then the equalities that describe their
affine hull may have coefficients with larger values still.

Perform a greedy search before computing a reduced basis.
We also perform a greedy search after computing the reduced basis
just in case the problem has become easy through this basis reduction.

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

isl_tab_sample: extract out compute_min and compute_max

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

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

isl_tab_sample: treat emptiness of tableau as error

We only modify the tableau through calls to isl_tab_add_valid_eq,
which should never result in an empty tableau, given that
the tableau was initially not empty.

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

AST generation: fix handling of separation classes

In particular, make sure that the classes remain separate.
After removing the previous classes from the current class,
we would intersect the result with the schedule domain
and then eliminate inner dimensions.  This elimination process
may drop some constraints that are needed to ensure that the
current class is disjoint from the previous classes.
We therefore intersect the result of the elimination step
with the current separation class domain.

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

isl_printer_print_{basic_,}{set,map}: don't start new line in omega format

For the isl format, the new line was removed in 9a54ed5
(isl_printer_print_basic_{set,map}: don't start new line in isl format,
Sun Feb 13 09:05:48 2011 +0100).

Additionally, remove the parameter declaration.
Printing out the parameter declaration for each (basic) set or map
is not very convenient.  Instead, we now support printing the parameter
declaration through isl_printer_print_space.

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

isl_printer_print_space: support printing in "omega" format

In particular, print a declaration for the parameters in the space.

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

rename isl_basic_set_add to isl_basic_set_add_dims

For consistency with isl_set_add_dims and isl_basic_set_insert_dims.

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

isl_aff_normalize: plug in divs with unit coefficient in other divs

The outer div expression can then be simplified and the inner div
expression may be removed if it was only used inside the outer div
expression.

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

isl_local_space_substitute_seq: take argument for the number of divs to modify

This will allow us to modify a single div in the next commit.

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

isl_aff_floor: normalize result

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

isl_aff_ceil: compute ceil(e/m) as floor((e + m - 1)/m)

The original implementation would compute ceil(e/m) as -floor(-e/m).
Although both are correct, floor((e + m - 1)/m) is probably less
surprising.

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

isl_aff_gist: add missing isl_vec_cow

We could end up modifying a different isl_aff that originated from
the same isl_aff as the one being modified.

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

isl_union_set_compute_schedule: double check that we do not run out of rows

The previous commit fixed a case where we would generate more schedule
rows than anticipated.  Make sure we do not run into this situation again.

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

isl_union_set_compute_schedule: ensure carry_dependences makes progress

If solve_lp is unable to find a solution, then compute_schedule_wcc
calls carry_dependences to carry as many dependences as possible.

However, the reason that solve_lp was unable to find a solution
may be due to proximity dependences.  In particular, if there are
an infinite number of dependences with the same starting or ending
itereration, then the way proximity dependences are currently handled
may force some of the schedule coefficients to be zero based solely
on those proximity dependences.

carry_dependences may then fail to carry any (validity) dependences
simply because there are no validity dependences.
More generally, it may produce a non-trivial solution on only some
of the nodes.  This may result in a number of schedule rows (infinite
in the worst case) that is larger than the maximum computed in
compute_max_row, leading to out-of-bounds accesses.

We therefore check that the schedule row computed by carry_dependences
is non-trivial on all the nodes where it should be non-trivial.
If not, we try again on each dependence graph component separately
or fail if there is only one component.

Note that this commit does not fix the problem that the presence
of proximity dependences may eliminate some valid solutions,
but it should solve the out-of-bounds accesses.

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

update for change in clang's DiagnosticOptions

DiagnosticOptions was moved from Frontend to Basic and
createDiagnostics now takes a pointer to a DiagnosticOptions object.

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

isl_map_plain_is_disjoint: handle inputs with different parameters

In particular, make sure we do not call isl_basic_map_plain_is_disjoint
if the input relations do not have the same parameters.

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

add README

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

Introduce isl_int_free_str to remove GMP dependency in isl_int interface

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

isl_union_set_compute_schedule: handle result with zero bands

The code in extract_schedule would assume that there is at least
one band in the resulting schedule.  Skip the parts that depend
on this assumption when the number of bands is zero.

Reported-by: Sameer Sahasrabuddhe <Sameer.Sahasrabuddhe@amd.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_ast_codegen.c: generate_domain: postpone single-valuedness test

In particular, perform the test on the map that will actually be used
to construct the call expression.

The original code would first perform the test and then construct
the call expression from a map with a simplified domain.
This construction may fail because after simplification of the domain,
the map may no longer be single valued.

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

isl_ast_build_ast_from_schedule: make construction of else branches optional

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

isl_ast_build_ast_from_schedule: use "<" if upper bound has negative constant

This is a purely cosmetic change.
In particular, we prefer

    for (int c1 = max(0, c0); c1 < min(N, N + c0); c1 += 1)

over

    for (int c1 = max(0, c0); c1 <= min(N - 1, N + c0 - 1); c1 += 1)

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