isl_basic_set_full_compression: detect equalities in input first

Without this explicit detection of equalities, some equalities
may be discovered in the middle of the computation, possibly
leading to the introduction of existentially quantified variables,
while callers of isl_basic_set_full_compression typically do not
want such variables.

Since the detection of equalities can in some cases be fairly expensive,
we may have to find a better way of dealing with this problem at some point.

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

isl_stream_read_pw_qpolynomial: accept products of integer divisions

Before, we called accept_affine to parse an integer division that appears
inside a function, but accept_affine also parses a subsequent '*' and
then expects this '*' to be followed by a constant.
Call accept_div directly intead.

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

isl_union_set_product: call isl_set_product on entries

Before, we would simply delegate control to isl_union_map_product,
which calls isl_map_product on the entries.  This doesn't work
on isl_sets because they only have a "range" and no "domain".

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

isl_tab_pip.c: sol_add: skip empty contexts

If the context becomes non-empty inside find_solutions, we stop
looking for solutions since a89841a (isl_tab_pip.c: find_solutions: break
when context becomes empty, Sun Jan 31 18:29:12 2010 +0100), but
we still call sol_add.  We need to return from sol_add early in
such cases because there is nothing to do and, more importantly,
when a basic set is marked empty, its existentials are removed,
resulting in a mismatch in the number of dimensions.  In particular,
the basic set returned by sol_domain may not satisfy all assumptions
made by the remainder of sol_add.

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

isl_space_set_dim_id: also set id of parameter in nested spaces

A nested space is supposed to have the same parameters as
the nesting space, so if the id of a parameter in the nesting
space space changes, it has to be changed in the nested spaces too.

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

isl_space_set_dim_id: rename "dim" variable to "space"

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

schedule.c: split_parallel: avoid invalid memory accesses

The original code incorrectly assumed that the schedules for
all statements have the same number of columns, i.e., that the
dimensions of the iteration domains of all statements are the same.

We fix this up by simply bailing out if we find this assumption not to hold.
We will improve the applicability of the transformation performed by
split_parallel in a subsequent patch.

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

isl_pw_aff_non_zero_set: don't assume isl_pw_aff is total

Before, we would return the domain where the function is not zero
or undefined, whereas we should only return the domain where the function
is not zero.

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

isl_aff_nonneg_basic_set and isl_aff_zero_basic_set: simplify result

The constructed constraint may be a tautology in which case it needs
to be simplified away, especially if it is an equality.

We probably want to perform this simplification in
isl_basic_set_from_constraint instead, but CLooG currently depends
on the resulting basic set not being simplified.
We would have to fix CLooG first before we can change this behavior.

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

isl_tab_from_basic_map: preserve all constraints in input when tracking

If the user wants to keep track of a basic map representation of the tableau,
then we need to make sure that the initial tableau corresponds exactly to
the input.  In particular, we need to make sure that no (redundant) constraints
are removed.

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

isl_tab_track_bmap: drop sanity checks in case of empty tab

If tab is empty, then we may not have added all constraints of "bmap"
and so the number of constraints in tab and bmap may be different.

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

isl_tab_track_bmap: make sure we have a unique copy of the basic map

The basic map will be modified in place by isl_tab_add_ineq.
Some callers were passing a unique copy to isl_tab_track_bmap
already, but some others apparently were not.
It's safer to just let isl_tab_track_bmap take care of this.

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

isl_tab_track_bmap: fix memory leak on error path

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

isl_basic_map_remove_unknown_divs: restart whenever div has been removed

The call to isl_basic_map_remove_dims may end up calling
isl_basic_map_simplify, which may in turn remove additional divs
if they no longer occur in any constraint.

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

isl_map_simple_hull: improve error handling

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

isl_schedule.c: mark row constructed by compute_split_schedule as non-zero

compute_split_schedule is only called when no zero-distance schedule row
could be found on the entire graph.
We missed this part in ee1ca56 (isl_schedule.c: keep track of parallel loops,
Sun May 29 19:41:55 2011 +0200).

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

isl_map_project_out: properly handle named or nested spaces

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

isl_morph_{dom,ran}_params: add missing isl_morph_cow

Usually, isl_morph_remove_{dom,ran}_dims will call isl_morph_cow for us,
but not when n == 0.

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

isl 0.09

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

avoid "errno" argument name

On mingw, errno is defined as (*_errno()) in stdlib.h

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

add isl_morph_dump

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

rename isl_morph_dump to isl_morph_print_internal

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

isl_basic_set_compute_vertices: fix handling of lower-dimensional input

Support was broken by 9043b59 (explicitly differentiate between spaces
of maps, sets and parameter sets, Thu Aug 25 19:21:05 2011 +0200).
This fix should have gone in before that commit.

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

doc: improve consistency in list of schedule options

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

add Feautrier's scheduling algorithm

Offer Feautrier's algorithm as an alternative to isl's default scheduling
algorithm.  The schedule is extended to a full-dimensional schedule.
To select the scheduling algorithm to use, we introduce isl option
schedule-algorithm.

Signed-off-by: Sven van Haastregt <svhaastr@liacs.nl>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add option to bound the constant scheduling coefficients

If larger coefficients appear as part of the input dependences, the
schedule calculation can take a very long time. We observed that the
main overhead in this calculation is due to optimizing the constant
coefficients. They are misused to increase locality by merging several
unrelated dimensions into a single dimension. This unwanted optimization
increases the complexity of the code and slows down the generated code.

We introduce a new option that bounds the values in the constant
dimension by a user defined value. If the right value is choosen,
costly overoptimization can be prevented.

This solution works, but requires the user to specify the value by
which the constants are bound. For the moment, this is our best
solution, but we hope to to find a more generic one later on.

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

Introduce new ISL_CTX_(GET|SET)_INT_DEF macro

This macro uses the same implementation as the corresponding
BOOL and CHOICE macros. Hence, we simplify BOOL and CHOICE by
forwarding to the new INT macro.

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

Fix typo in documentation

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

Add interface to set schedule_maximize_band_depth

Previously, schedule_maximize_band_depth could only be set with the
corresponding command line option. This patch adds two functions
to change this option when using isl as a library.

int isl_options_set_schedule_maximize_band_depth(
isl_ctx *ctx, int val);
int isl_options_get_schedule_maximize_band_depth(
isl_ctx *ctx);

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

doc/SubmittingPatches: fix typo in email address

Signed-off-by: Sven van Haastregt <svhaastr@liacs.nl>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

export schedule_split_parallel option

Signed-off-by: Sven van Haastregt <svhaastr@liacs.nl>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_pw_multi_aff_get_pw_aff

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

Merge branch 'maint'

isl_map_from_pw_aff: handle NULL input

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

add isl_space_map_from_domain_and_range

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

Introduce option 'on_error'

The option on_error defines the behaviour of isl in case of an error.
By default, the option is set to 'warn'. This is the current behaviour
and means isl prints a warning and continues the execution of the
program. We also introduce two new modes: 'continue' and 'abort'.
'continue' does not print any warning, but continues execution and 'abort'
abort the program from within isl.  'abort' is useful for debuggers as
they automatically break at the place of the error condition.

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

export isl_map_eliminate

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

Improve message when ctx is freed, but still referenced

Instead of a cryptic 'Assertion "ctx->ref == 0" failed' we report
'isl_ctx freed, but some objects still reference it'.

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

add isl_local_space_range

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

Merge branch 'maint'

isl_pw_aff_scale: don't special case multiplication with zero

isl_pw_*_scale returns an empty result if a multiplication with zero
is being performed.  We do this because zero is the default value
for polynomials.  Affine expressions, by contrast, have no default value
and so we should not return an empty result in this case.

Reported-by: Tomofumi Yuki <tomofumi.yuki@gmail.com>
Tested-by: Tomofumi Yuki <tomofumi.yuki@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

add isl_set_find_dim_by_name

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

isl_basic_map_involves_dims: double-check divs

In principle, the extra test is not needed at this moment, but
this may change in future.

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

isl_schedule.c: fix typo in comment

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

configure.ac: only create interface/Makefile if user has clang

This allows users without clang to perform a "make dist".

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

add isl_pw_aff_has_dim_id

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

add missing namespace qualification on llvm::ArrayRef

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

Merge branch 'maint'

isl_union_pw_*_{intersect_domain,gist}: update to change of isl_pw_* space

In 3280c05 (make isl_pw_* object live in a map space,
Tue Aug 30 16:47:59 2011 +0200), the space in which objects live was
changed from that of its domain to that of a map, but
isl_union_pw_*_{intersect_domain,gist} were not changed accordingly.

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

isl_map_insert_dims: handle NULL input

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

isl_set_from_pw_aff: handle NULL input

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

document isl_basic_map_set_tuple_name

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

.gitignore: add isl_config.h.in~

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

isl_arg_parse: support string list arguments

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

hide isl_options structure

We also add some getters and setters for options that are known to
be used from outside of isl.

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

introduce isl_args structure that constains isl_arg list and size of options

Before, the size of the options structure of a submodule was stored
inside the corresponding child option of the parent.
This however, requires that the options structure of the submodule
is visible to the parent so that it can compute the size of this structure.
Moreover, if the size of this structure changes, then the code
containing the child option, which may reside in a different module,
would have to be recompiled.

Now, we store the size of the options structure together with the list
of option descriptions.  In particular, it is stored in the same module
as the options structure itself, so that this structure no longer needs
to be exposed.

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

add isl_ctx_parse_options

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

isl_arg_parse: print current option values as defaults

In the --help output, we used to print the default values stored
in the isl_arg objects as the defaults for options.
It is however sometimes convenient to change some of the options
to values different from their true defaults before allowing
the user to override these options.  It then makes more sense
to print the current values of the options as defaults, rather
than the defaults that were used during the construction of
options object.

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

use the clang driver to obtain command line arguments for the clang frontend

Recent clang perform the Linux header searching in the driver instead
of the fronted.  We therefore need to call the driver to obtain
the system include paths and pass them along to the frontend.

Helped-by: Chandler Carruth <chandlerc@google.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

support more recent LLVMs

In particular, getHostTriple has been renamed to getDefaultTargetTriple.

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

add isl_map_subtract_range

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

allow --with-gmp=build

This patch allows --with-gmp=build (and thus makes --with-gmp-builddir= work)

This patch is required to restore possibility to build gmp and cloog in a
combined tree with gcc.

Signed-off-by: Serge Belyshev <belyshev@depni.sinp.msu.ru>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_gist: return empty set if context is obviously empty

This is more consistent with what happens if the intersection
of input and context turns out to be empty.

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

add isl_map_gist_range

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

add isl_map_subtract_domain

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

add isl_set_upper_bound_si

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

document *lower_bound_si functions

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

isl_union_pw_*_gist: special case gist with respect to parameter domains

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

add isl_union_pw_*_gist_params

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

add isl_pw_*_gist_params

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

export isl_pw_multi_aff_gist

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

add isl_multi_aff_gist_params

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

add isl_qpolynomial_gist_params

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

add isl_qpolynomial_fold_gist_params

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

export isl_qpolynomial_fold_gist

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

add isl_aff_gist_params

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

add isl_set_gist_params_basic_set

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

add isl_basic_set_intersect_params

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

isl_union_pw_*_intersect_domain: special case parameter domains

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

add union_pw_*_intersect_params

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

add isl_pw_*_intersect_params

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

add isl_union_map_params

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

doc: explain direction of dependence relations from the start

Reported-by: Yi Zhang <yizhang84@gmail.com>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_map_is_subset: align parameters if needed

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

isl_pw_*_opt: use correct space in case of empty input

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

isl_tab_pip.c: sol_pma_add: add missing finalize

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

isl_id_alloc: allow isl_ids with the same name but different user value

Although isl_ids were documented as being identified by the pair
of name and pointer value, this was not implemented as such.
Instead, only the name was taken into account.

This commit fixes isl_id_alloc to also take into account the user value.
We also avoid dereferencing possible NULL names.

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

Add missing cow to isl_{basic_,}map_set_dim_name()

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

isl_union_set_gist: special case gist with respect to parameter domains

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

isl_map_alloc_space: fix memory leak on error path

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

isl 0.08

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

interface/Makefile.am: append extra copy of CLANG_LDFLAGS to LDADD

For some reason, llvm-config includes system libraries as part of
--ldflags instead of --libs.  Since some of the libraries in
CLANG_LIBS may depend on the system libraries, we need to make
sure those system libraries are (also) listed after CLANG_LIBS.

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

isl_tab_pip.c: set_row_cst_to_div: don't assume coefficient of div is zero

The function is supposed to increment the coefficient of the given
div by one, but instead it would simply set the coefficient to one.
This is fine if the div is new and therefore has a zero coefficient,
but it does not work if the div already appeared in the constraint.

Reported-by: Armin Größlinger <armin.groesslinger@uni-passau.de>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

isl_tab_pip.c: fix typo in comment

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

remove undocumented isl_basic_{set,map}_foreach_lex{min,max}

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

isl_test: test isl_basic_map_lexmin_pw_multi_aff

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

add isl_union_map_gist_domain

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

add isl_map_gist_domain

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

add isl_union_map_gist_params

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

isl_union_map_intersect_domain: special case intersection with parameter domain

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