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>

isl_ast_expr: add isl_ast_op_lt and isl_ast_op_gt operations

isl_ast_op_lt will be useful in the next commit.
isl_ast_op_gt is added for consistency.

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

add isl_basic_set_from_params

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

isl_ast_expr_from_aff: try harder to use isl_ast_op_pdiv_{q,r}

When generating C code, we prefer to generate "/" (or "%") rather
than "floord" because "floord" has an implicit condition on the
sign of the first argument.
We would already generate isl_ast_op_pdiv_q instead of isl_ast_op_fdiv_q
if we detect that the first argument is non-negative.
Now, we also check if the first argument is smaller than the second.
If so, we can rewrite

floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)

and still use isl_ast_op_pdiv_q.

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

isl_ast_build_expr.c: separate out extract_modulo function

This will make it easier to improve the extraction of modulos
in a subsequent commit.

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

isl_ast_build_expr.c: fix typo in comment

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

isl_ast_build_expr.c: remove remnants of code removed before inclusion

The AST generation code has undergone many changes before it was
included in the master branch.  Some references to old code got left in
by mistake.

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

add extra AST generation test case from CLooG

The test case was not added before because the output had not been
tested yet.

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

isl_printer_print_str: handle NULL input

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

isl_ast_expr_mod: perform missing multiplication

The function was documented as multiplying the constructed modulo expression
by the first argument, but failed to do so.
The problem went unnoticed because the first argument is usually equal to 1.

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

Make sed expression in Makefile compatible with BSD style sed

Apparently sed as available on Mac, requires a terminating semicolon
in the command list. As gnu-sed is OK with and without the semicolon
we add it for compatibility.

Note that the "{" command of historical seds may not support multiple
commands on a single line.

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

add isl_id_set_free_user

Allow the user to specify a callback to be called on the user pointer
when the last reference to the isl_id disappears.  This is convenient
for attaching dynamically allocated data structures to isl_ids,
especially in annotations to AST nodes.

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

isl_printer_print_pw_aff: use isl_ast_expr when printing in C format

isl_ast_expr_from_aff tries a bit harder to print a nice result,
so we might as well reuse that functionality.

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

add support for generating ASTs from schedule relations

This functionality is similar to that offered by CLooG and codegen(+).
The implementation in isl allows for a bit more control on how
the ASTs are generated by means of fairly flexible options.
It also has proper support for nested AST generation.

The outputs of all test cases have been verified by parsing them
using pet and then checking that the set of calls corresponds exactly
to the domain of the schedule and that they are called in an order
that matches the schedule.

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

add ISL_CTX_{GET,SET}_STR_DEF macros

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

doc: separate out polyhedral compilation functionality

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

add isl_set_dim_has_{lower,upper}_bound

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

isl_basic_set_substitute: check that input affine expression is integral

Otherwise, we may have to add stride constraints.

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

isl_pw_multi_aff_substitute: improve error handling

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

isl_basic_map_align_divs: fix potential invalid access

isl_basic_map_align_divs is currently only called on inputs that are
known not to be NULL, but since we check whether they are NULL anyway,
we might as well only access them after this test.

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

isl_pw_multi_aff_from_map: detect strides in output dimensions

If the input map is of the form

{ [i] -> [j] : exists a: j = 4 a and i - 1 <= j <= i }

then the detection mechanism of the previous commit will not
be able to read off the definition of j directly from the constraints.
However, if we plug in j = 4 j', we obtain

{ [i] -> [j'] : i - 1 <= 4 j' <= i }

from which we can read off j' = floor(i/4), which can then be plugged
back into j = 4 j' to obitain j = 4 * floor(i/4).

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

isl_pw_multi_aff_from_map: detect easy floors directly from constraints

If the input map has constraints of the form

{ [i] -> [j] : i - 1 <= 2 j <= i }

then we can easily detect that j can be taken to be equal to floor(i / 2).
Detecting these conditions directly from the constraints saves us
from having to compute a minimum on this dimension
using parametric integer programming.  Not only can such an operation
be fairly costly, it can also lead to needless subdivisions if there
are any other constraints on the dimension to be minimized.

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

privately export isl_map_is_set

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

add isl_pw_*_pullback_pw_multi_aff

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

add isl_pw_*_pullback_multi_aff

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

add isl_multi_aff_pullback_multi_aff

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

add isl_aff_pullback_multi_aff

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

add isl_local_space_preimage_multi_aff

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

add isl_set_preimage_pw_multi_aff

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

add isl_set_preimage_multi_aff

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

add isl_basic_set_preimage_multi_aff

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

isl_stream_new_str: fail on NULL input

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

privately export isl_multi_aff_align_divs

We will need it in the next commit.

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

add isl_basic_set_add_div_constraints

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

isl_map_is_subset: support rational maps

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

isl_stream_read_map: fix parsing of Omega input

Support for parsing such input was broken by fc5018d (isl_stream_read_map:
accept alternative [i][j] tuple syntax, Sun Jul 3 21:01:01 2011 +0200)
as the two tuples in, say, {Sym=[n] [i] : i <= n } would get merged
into a single tuple (i.e., [n,i]).

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

isl_stream_read_map: add partial support for reading rational sets

The support is incomplete, but enough to read the inputs in the test
cases of the next commit.

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

isl_pw_aff_nonneg_set: return a rational set if the input is marked rational

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

isl_pw_aff_zero_set: return a rational set if the input is marked rational

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

add isl_pw_aff_list_set_rational

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

add isl_pw_aff_set_rational

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

privately export isl_set_set_rational

We will need it in the next commit.

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

add isl_set_has_rational

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

reimplement isl_stream_read_aff in terms of isl_stream_read_multi_aff

Reading an isl_aff is essentially a special case of reading an isl_multi_aff.
We therefore do not need any special code for reading an isl_aff, but can
instead read it as an isl_multi_aff and then extract out the isl_aff.

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

declare isl_stream_read_multi_aff

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

isl_stream_read_multi_aff: read tuples directly

The original code would call isl_stream_read_pw_multi_aff, which in
turn first parsed the input as a map.  Not only does this lead to
needless, potentially expensive, conversions, it also makes it difficult
to parse rational expressions.

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

isl_input.c: change tuple parsing

Instead of immediately updating an isl_map, we first collect the
information in an isl_multi_pw_aff and then update the isl_map
based on this information.
This will allow us to reuse the tuple parsing in an improved
isl_stream_read_multi_aff.

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

add isl_pw_multi_aff_range_product

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

add isl_multi_*_splice

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

add isl_multi_*_range_splice

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

add isl_multi_*_set_tuple_name

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

add isl_multi_*_range_product

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

add isl_multi_*_add_dims

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

add isl_multi_*_insert_dims

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

add isl_multi_pw_aff

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

add isl_multi_aff_from_aff

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

isl_multi_templ.c: rename align_params_multi_set_and to include MULTI(BASE)

This allows isl_pw_multi.c to be included twice from the same file.

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

isl_multi_templ.h: avoid reference to explicit element type

This will make it easier to create additional isl_multi_* types.

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

isl_multi_*_reset_space_and_domain: call isl_*_reset_domain_space

The original code would call isl_*_reset_space_and_domain,
but the space of the multi_* is clearly different from the space of the *,
so it does not make sense to pass that space to the *.
In case of isl_multi_aff, this does not cause any problems because
isl_aff_reset_space_and_domain ignore the first argument.
However, for an isl_multi_pw_aff, this would cause problems.
Call isl_*_reset_domain_space instead.

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

generalize isl_multi_aff_flat_range_product

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

generalize isl_multi_aff_drop_dims

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

generalize isl_multi_aff_set_dim_name

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

generalize isl_multi_aff_zero

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

generalize isl_multi_aff_identity

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

add isl_pw_aff_zero_on_domain

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

add isl_pw_aff_var_on_domain

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

add isl_aff_var_on_domain

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

isl_input.c: obj_read_body: simplify error handling

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

add isl_basic_set_drop_constraints_not_involving_dims

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

add isl_{set,map}_drop_constraints_involving_dims

We implement these functions on top of the existing
isl_basic_set_drop_constraints_involving which handles dimensions
in terms of absolute positions.  We may want to convert the users
of this old function over to the new functions at some point.

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

add isl_set_unshifted_simple_hull

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

isl_stream_read_union_map: force result to be a map

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

add isl_union_map_subtract_range

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

isl_set_from_pw_multi_aff: handle NULL input

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

isl_union_map.c: plain_injective_on_range: silence clang warning

Recent clangs complain that "n" may be used uninitialized in the call
to free_isl_fixed_map_array.  However, this only happens data.v is NULL,
in which case free_isl_fixed_map_array does not even look at n.

By moving the initialization of n up, we can silence this warning.

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

isl_transitive_closure.c: union_components: avoid invalid access on error path

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

isl_range.c qpolynomial_bound_on_domain_range: avoid invalid access on error path

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

isl_convex_hull.c: initial_facet_constraint: avoid invalid access on error path

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

isl_map_union: special case universal input

In particular, there is no need to construct a new isl_map
as we can simply return the universal input map.

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

isl_map_gist: special case universal and equal inputs

In both these cases, the solution is trivial and we do not need to
go into the regular computation.
Moreover, if the inputs are equal but not convex, then the original
code would not be able to come to the conclusion that the gist
is the universe.

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

export isl_set_plain_cmp

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

doc: clarify use of identifiers

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

add isl_basic_set_remove_unknown_divs

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

and isl_pw_aff_tdiv_q and isl_pw_aff_tdiv_r

These are useful for expressing the result of the corresponding C operators.

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

add isl_pw_aff_div

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

add isl_set_is_disjoint

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

isl_map_plain_is_disjoint: special case obviously empty inputs

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

isl_basic_map_is_empty: special case universal input

In particular, there is no need to compute any sample point on
universal inputs.

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