isl_ast_build_expr_from_pw_aff: exploit domain constraints of pieces

That is, for an isl_pw_aff that would be generated as

	n >= 0 ? floord(n, 2) : 0

take into account that n >= 0 in the first piece and use
that to simplify the associated quasi-affine expression,
producing

	n >= 0 ? n / 2 : 0

instead.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_codegen.c: add_node: replace gist by pure specialization

The main purpose of the "domain" set computed in add_node
is to detect strides.  The same set is later also used
to intersect "bounds" with additional equalities and
in the calls to exact_bound from refine_generic in
case there are no lower or upper bounds in "bounds".
The set is also used inside add_node to check if "bounds"
conflict with the build domain.

The call to isl_ast_build_compute_gist has several effects
- it plugs in the known values of outer loop iterators
- it detects conflicts with the build domain
- it may detect additional equalities
- it computes explicit representations for the divs
- it removes some constraints implied by the build domain

The final effect is undesired as it may result in the loss
of stride information as in the new test case.
In particular, the generated code would look like

    for (int c0 = 0; c0 < n - 1; c0 += 32)
      for (int c1 = c0 - 30; c1 < n; c1 += 1)
	if (c1 % 32 == 0)

instead of

    for (int c0 = 0; c0 < n - 1; c0 += 32)
      for (int c1 = c0; c1 < n; c1 += 32)

because in part of the schedule domain c0 and c1 are equal and
we already know that c0 is a multiple of 32.  In that part of
the schedule domain, the gist therefore drops the information
that c1 is also a multiple of 32.

We therefore remove the gist computation and restrict
ourselves to plugging in the known values of outer loop iterators.

It is not clear if the computation of explicit representations
was intended, but it does seem to have a significant effect
on some of the test cases.  We therefore keep this computation,
but we have to do it explicitly now.
We may want to reconsider whether this computation should
be performed at a later stage.

The check for conflicts with the build domain is also made
explicit in this commit.

The only effect we do not keep here is the possible detection
of additional equalities.  It is not clear if this ever has
any effect in practical cases, but we can still add it back later
if it turns out to be useful later.

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

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

This will be useful for isl_set_unshifted_simple_hull_from_basic_set_list.

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

This will be useful for isl_set_unshifted_simple_hull_from_basic_set_list.

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

This will be useful for isl_set_unshifted_simple_hull_from_basic_set_list.

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

This will be useful for isl_set_unshifted_simple_hull_from_set_list.

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

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_graft.c: extract_hoistable_guard: extract out hoist_guard

This simplifies the extract_hoistable_guard code somewhat and
we will be able to reuse the new function in the next commit.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
AST generator: perform more aggressive guard hoisting

In particular, take into account both enforced constraints and
constraints that still need to be generated while
looking for hoistable guards.  This allows us to hoist guards
that are only explicit in some of the grafts and implicit in
the others (through the enforced or pending constraints).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
AST generator: take into account some parameter constraints early on

In particular, intersect the executed relation with some
of the parameter constraints.  We want to avoid breaking
up the executed relation into several pieces, so we only
intersect with a single disjunct parameter domain.

Taking into account these parameter constraints from the
start allows us to avoid investigating some cases that
will turn out to be impossible.

For example, for the omega/ts1d-mp-i_ts-m_b-0.a test case,
isl used to generate a loop

    for (int c1 = -1; c1 < (T >= 1 ? T : 0); c1 += 1)

because it needs to combine a disjunct where the bound is T
and a disjunct where the bound is 0 (and T is unconstrained).
By including the constraint T >= 0 from the context, this bound
can be directly constructed as in

    for (int c1 = -1; c1 < T; c1 += 1)

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

This will allow us to avoid looking at the isl_ast_build internals
in some places.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_codegen.c: generate_next_level: use isl_ast_build_dim

Do so instead of looking into the internals of the isl_ast_build.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_build.c: update_values: explicitly take into account stride constraint

Before this commit we would rely on the caller to add the stride constraint
to the build domain.  However, we want to avoid adding this stride constraint
to the build domain in some cases and so we have to take it into account
explicitly while checking if the dimension attains a single value.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
push isl_ast_build_include_stride into isl_ast_build_set_loop_bounds

We want to avoid adding the stride constraint to the build domain
in case of an eliminated schedule dimension.  Since we only find out
whether a schedule dimension is eliminated inside
isl_ast_build_set_loop_bounds, we first push the call to
isl_ast_build_include_stride into this function.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_build_set_loop_bounds: do not add stride constraint in eliminated case

We used to add the stride constraint unconditionally, but this meant
that we had to eliminate the current dimension from the build domain
if it turns out that the dimension has a fixed affine value.
Since we have this fixed value, there is no point in adding the
stride constraint since that information will never be used,
especially since we then eliminate the dimension from the stride constraint.
The result of this elimination could however get used and we had
to take special measures to ensure that this information is actually
enforced by the AST.

It is much simpler to not add the stride constraint to the build domain
in the first place.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_codegen.c: move up add_stride_guard definition

This will allow us to reuse this function from refine_degenerate.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_ast_codegen.c: refine_eliminated: do not add stride guard

Now that we no longer add the stride constraint to the build domain
in case of an eliminated loop, there is no longer any need
to add the stride guard to the graft guard.

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

We will be able to reuse this function when we inline
isl_ast_graft_alloc_level into create_node_scaled.

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

We will need this when we move some of the isl_ast_graft_alloc_level
functionality to isl_ast_codegen.c.

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