platform/upstream/isl.git
12 years agoadd isl_basic_map_get_divs
Sven Verdoolaege [Wed, 18 Apr 2012 08:48:16 +0000 (10:48 +0200)]
add isl_basic_map_get_divs

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_merge_divs: handle NULL input
Sven Verdoolaege [Wed, 18 Apr 2012 08:31:50 +0000 (10:31 +0200)]
isl_merge_divs: handle NULL input

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Wed, 18 Apr 2012 08:54:21 +0000 (10:54 +0200)]
Merge branch 'maint'

12 years agoisl_local_space_alloc_div: fix error handling
Sven Verdoolaege [Wed, 18 Apr 2012 08:46:20 +0000 (10:46 +0200)]
isl_local_space_alloc_div: fix error handling

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_union_set_compute_schedule: ignore backward proximity edges on split
Sven Verdoolaege [Sat, 14 Apr 2012 21:21:55 +0000 (23:21 +0200)]
isl_union_set_compute_schedule: ignore backward proximity edges on split

Proximity edges are not taken into account during the detection
of strongly connected components.  When we split the dependence graph
based on these SCCs, we may therefore have proximity edges that go
back from a SCC behind the split to a SCC ahead of the split.  These should
be ignored, just like those edges that go from ahead of the split to behind
the split.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_insert: preserve emptiness
Sven Verdoolaege [Tue, 17 Apr 2012 10:50:27 +0000 (12:50 +0200)]
isl_basic_map_insert: preserve emptiness

isl_basic_map_plain_is_empty doesn't look at the constraints but only
at the ISL_BASIC_MAP_EMPTY flag.  We therefore need to make sure the
flag is set on the output of isl_basic_map_insert if it was set on the
input.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_set_total_dim: handle NULL input
Sven Verdoolaege [Tue, 17 Apr 2012 10:34:22 +0000 (12:34 +0200)]
isl_basic_set_total_dim: handle NULL input

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_term_get_div: support nested divs
Sven Verdoolaege [Fri, 30 Mar 2012 13:14:54 +0000 (15:14 +0200)]
isl_term_get_div: support nested divs

Ever since 028d1a7 (drop isl_div abstraction, Fri Sep 9 14:55:16 2011 +0200),
the result of isl_term_get_div is an isl_aff and it can handle nested divs
just fine.  We therefore simply need to remove the now redundant check.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_term_get_div: normalize result
Sven Verdoolaege [Fri, 30 Mar 2012 13:18:35 +0000 (15:18 +0200)]
isl_term_get_div: normalize result

In particular, remove unused divs from the result.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_access_info_compute_flow: sort accesses in textual order
Sven Verdoolaege [Thu, 5 Apr 2012 08:31:04 +0000 (10:31 +0200)]
isl_access_info_compute_flow: sort accesses in textual order

Before, we tried to be clever and sorted the accesses in order
of increasing number of shared levels with the sink access.
However, this has little advantage over textual order.
Textually later accesses that cannot precede the sink at a given level
are simply skipped.
On the other hand, when we consider a loop level, we usually
do want to consider the textually last access first and not some
textually earlier access that happens to share more levels with the sink.
In particular, if this textually last access covers all the pending
sink accesses, there is no need to consider earlier accesses,
whereas you would always have to consider later accesses if you started
out with an earlier access.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_flow.c: access_sort_cmp: use isl_quicksort
Sven Verdoolaege [Fri, 13 Apr 2012 14:43:57 +0000 (16:43 +0200)]
isl_flow.c: access_sort_cmp: use isl_quicksort

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_qsort.h: fix whitespace
Sven Verdoolaege [Fri, 13 Apr 2012 14:39:04 +0000 (16:39 +0200)]
isl_qsort.h: fix whitespace

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_map_coalesce: optionally bound the coefficients of wrapping constraints
Sven Verdoolaege [Wed, 11 Apr 2012 08:54:37 +0000 (10:54 +0200)]
isl_map_coalesce: optionally bound the coefficients of wrapping constraints

One of the methods for combining pairs of basic relations is based on wrapping.
The coefficients of these wrapping constraints may be much larger than
those of the constraints in the input.  If isl_map_coalesce is called
to simplify the representation of a relation, then constraints with
large coefficients are typically undesirable.  We therefore do not allow
the coefficients in the wrapping constraints to be larger than those
in the input, but we allow the user to override this choice.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_seq_abs_max
Sven Verdoolaege [Wed, 11 Apr 2012 08:53:10 +0000 (10:53 +0200)]
add isl_seq_abs_max

12 years agoMerge branch 'maint'
Sven Verdoolaege [Fri, 13 Apr 2012 11:29:57 +0000 (13:29 +0200)]
Merge branch 'maint'

12 years agoisl_map_coalesce: don't try to relax (implicit) equalities
Sven Verdoolaege [Tue, 10 Apr 2012 16:41:28 +0000 (18:41 +0200)]
isl_map_coalesce: don't try to relax (implicit) equalities

An inequality that turns out to be an equality may have been removed
from the tableau, so we cannot relax it.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_tab_relax: prevent relaxation on dead or redundant constraints
Sven Verdoolaege [Fri, 13 Apr 2012 11:01:21 +0000 (13:01 +0200)]
isl_tab_relax: prevent relaxation on dead or redundant constraints

Trying to relax such constraints can only lead to problems,
especially if the constraints have been removed from the tableau.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_union: plug memory leak on error path
Sven Verdoolaege [Wed, 11 Apr 2012 12:15:29 +0000 (14:15 +0200)]
isl_basic_map_union: plug memory leak on error path

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoFix a typo in isl_term_dup
Louis-Noel Pouchet [Wed, 11 Apr 2012 14:08:15 +0000 (10:08 -0400)]
Fix a typo in isl_term_dup

Signed-off-by: Louis-Noel Pouchet <pouchet@cse.ohio-state.edu>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_stream_read_map: allow "not" at start of grouped expression
Sven Verdoolaege [Fri, 6 Apr 2012 09:58:03 +0000 (11:58 +0200)]
isl_stream_read_map: allow "not" at start of grouped expression

Reported-by: Vladimir Klebanov <vladimir@cost-ic0701.org>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_test: test_parse_map_equal: return result of test
Sven Verdoolaege [Sat, 7 Apr 2012 14:19:07 +0000 (16:19 +0200)]
isl_test: test_parse_map_equal: return result of test

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Sat, 7 Apr 2012 14:07:44 +0000 (16:07 +0200)]
Merge branch 'maint'

12 years agoisl_pw_*_on_shared_domain: improve error handling
Sven Verdoolaege [Thu, 1 Mar 2012 10:25:22 +0000 (11:25 +0100)]
isl_pw_*_on_shared_domain: improve error handling

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agolink in new -lclangEdit when available
Sven Verdoolaege [Tue, 27 Mar 2012 10:57:25 +0000 (12:57 +0200)]
link in new -lclangEdit when available

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_*alloc macros: return expression of desired type
Sven Verdoolaege [Fri, 16 Mar 2012 14:42:50 +0000 (15:42 +0100)]
isl_*alloc macros: return expression of desired type

The type information was dropped in 157122e (Check the ctx argument of the
memory macros, Tue Jun 7 16:15:15 2011 -0300).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_map_fixed_power and isl_union_map_fixed_power
Sven Verdoolaege [Wed, 7 Mar 2012 09:08:50 +0000 (10:08 +0100)]
add isl_map_fixed_power and isl_union_map_fixed_power

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_token: change type of "type" field from enum isl_token_type to int
Sven Verdoolaege [Wed, 29 Feb 2012 17:54:28 +0000 (18:54 +0100)]
isl_token: change type of "type" field from enum isl_token_type to int

The field is also assigned values outside the enum.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Tue, 6 Mar 2012 13:31:02 +0000 (14:31 +0100)]
Merge branch 'maint'

12 years agoisl_union_map_is_subset: properly handle non-obviously empty subsets
Sven Verdoolaege [Sat, 3 Mar 2012 22:52:06 +0000 (23:52 +0100)]
isl_union_map_is_subset: properly handle non-obviously empty subsets

If the first argument of isl_union_map_is_subset contains an empty
set in some space that is not present in the second argument,
then isl_union_map_is_subset would incorrectly draw the conclusion
that the first is not a subset of the second.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_pw_aff_cond: change first argument from an isl_set to an isl_pw_aff
Sven Verdoolaege [Sun, 26 Feb 2012 15:07:55 +0000 (16:07 +0100)]
isl_pw_aff_cond: change first argument from an isl_set to an isl_pw_aff

An isl_pw_aff can also convey information about whether the expression
is defined.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_set_{lower,upper}_bound
Sven Verdoolaege [Mon, 16 Jan 2012 19:21:19 +0000 (20:21 +0100)]
add isl_set_{lower,upper}_bound

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_pw_aff_n_piece
Sven Verdoolaege [Tue, 6 Mar 2012 09:20:03 +0000 (10:20 +0100)]
add isl_pw_aff_n_piece

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_set_indicator_function
Sven Verdoolaege [Sun, 26 Feb 2012 14:23:37 +0000 (15:23 +0100)]
add isl_set_indicator_function

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_affine_hull: consider points adjacent to any point found
Sven Verdoolaege [Wed, 18 Jan 2012 10:26:53 +0000 (11:26 +0100)]
isl_basic_map_affine_hull: consider points adjacent to any point found

This is usually a fairly cheap way of finding additional points in
the affine hull and may in some cases eliminate constraints with large
coefficients in the current approximation of the hull.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_set_has_dim_name
Sven Verdoolaege [Tue, 17 Jan 2012 11:04:12 +0000 (12:04 +0100)]
add isl_set_has_dim_name

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agodoc: minor clean-up
Sven Verdoolaege [Sun, 26 Feb 2012 08:10:21 +0000 (09:10 +0100)]
doc: minor clean-up

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_space_has_dim_name
Sven Verdoolaege [Tue, 17 Jan 2012 11:04:02 +0000 (12:04 +0100)]
add isl_space_has_dim_name

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoconfigure.ac: remove spurious ","
Sven Verdoolaege [Sat, 25 Feb 2012 09:11:47 +0000 (10:11 +0100)]
configure.ac: remove spurious ","

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agodoc: fix typo
Sven Verdoolaege [Fri, 24 Feb 2012 15:26:26 +0000 (16:26 +0100)]
doc: fix typo

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_set_sample: perform basis reduction at each level by default
Sven Verdoolaege [Fri, 24 Feb 2012 09:03:22 +0000 (10:03 +0100)]
isl_basic_set_sample: perform basis reduction at each level by default

Although always performing basis reduction can lead to slow-downs
on larger problems, only performing it once can result in some
relatively simple problems taking an inordinate amount of time.
We therefore revert back to the default from before 8db0a80
(isl_basic_set_sample: only perform basis reduction once,
Sun Aug 9 11:42:41 2009 +0200).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_basic_set_is_subset
Sven Verdoolaege [Fri, 24 Feb 2012 08:55:43 +0000 (09:55 +0100)]
add isl_basic_set_is_subset

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoexport isl_basic_map_is_subset
Sven Verdoolaege [Fri, 24 Feb 2012 14:36:51 +0000 (15:36 +0100)]
export isl_basic_map_is_subset

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_basic_set_sample
Sven Verdoolaege [Fri, 24 Feb 2012 08:50:57 +0000 (09:50 +0100)]
add isl_basic_set_sample

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agodoc: document *_sample functions
Sven Verdoolaege [Fri, 24 Feb 2012 14:30:16 +0000 (15:30 +0100)]
doc: document *_sample functions

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Thu, 23 Feb 2012 16:04:38 +0000 (17:04 +0100)]
Merge branch 'maint'

12 years agoisl_coalesce.c: wrap_in_facets: bail out if any of the facets are empty
Sven Verdoolaege [Thu, 23 Feb 2012 14:51:59 +0000 (15:51 +0100)]
isl_coalesce.c: wrap_in_facets: bail out if any of the facets are empty

It the tableau corresponding to a facet is empty, then we don't have
accurate information on the ridges and we can't call add_wraps.
The facet can have no integer points due to other constraints.
An alternative would be to temporarily treat the tableau as a rational
tableau.

Reported-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_test: test_coalesce_set: fail if coalescing failed
Sven Verdoolaege [Thu, 23 Feb 2012 15:16:56 +0000 (16:16 +0100)]
isl_test: test_coalesce_set: fail if coalescing failed

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoexport isl_map_plain_is_single_valued
Sven Verdoolaege [Tue, 21 Feb 2012 17:00:37 +0000 (18:00 +0100)]
export isl_map_plain_is_single_valued

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_tab_basic_map_partial_lexopt: properly normalize divs
Sven Verdoolaege [Tue, 21 Feb 2012 15:27:28 +0000 (16:27 +0100)]
isl_tab_basic_map_partial_lexopt: properly normalize divs

We were only dividing out common divisors that also divide
the constant term, but we should ignore the constant term
while determining the greatest common divisor.

We already properly normalize the constraints and not properly
normalizing the divs could result in div constraints not being
recognized as such.  In particular, inside isl_map_affine_hull,
div constraints are added inside the call to isl_basic_map_overlying_set.
Usually, these constraints are removed again in remove_redundant_divs,
but they would remain if the the divs are not properly normalized.

Now, arguably, we shouldn't be adding div constraints inside
isl_map_affine_hull, but a proper normalization of divs is useful in any case.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_map_complement
Sven Verdoolaege [Sat, 18 Feb 2012 13:10:04 +0000 (14:10 +0100)]
add isl_map_complement

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoscheduler: allow to bound the coefficients in the calculated schedule
Tobias Grosser [Sun, 19 Feb 2012 13:05:50 +0000 (14:05 +0100)]
scheduler: allow to bound the coefficients in the calculated schedule

isl already supports the bounding of the constant term of the calculated
schedule, but within polybench there are several cases where bounding
the coefficients of parameter and variable dimensions is also needed.

With a bound of 20 Polly can run the isl scheduler on all polybench 2.0 kernels
and takes for each less than 5 seconds, whereas without the bound five test
cases had scheduling times larger than 40 seconds. This is still slower, than
scheduling with gist simplified dependences but it yields better results.
The bounded, non-gist-simplified schedule yields for dynprog, lu, reg_detect
and trmm to faster code compared to scheduling with gist simplified
dependences. For gramschmidt it yields slower code.

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_tab_basic_set_non_trivial_lexmin: do not add cuts for all variables
Tobias Grosser [Sat, 18 Feb 2012 15:13:23 +0000 (16:13 +0100)]
isl_tab_basic_set_non_trivial_lexmin: do not add cuts for all variables

We found a test case where adding cuts for all variables can increase
the time of the scheduling algorithm significantly (from ms to never
seen terminating). Even though we did not understand the problem
entirely, the intuition we have is the following:

When using isl_tab_basic_set_non_trivial_lexmin, the ILP problem is
(usually) not empty, but infinite. Adding all cuts, seems to increase
the objective function only in very small steps. Adding only one cut at
a time allows us to increase it with a step as big as possible.

This patch does not change the behaviour when calling
check_integer_feasible.  In case we're calling cut_to_integer_lexmin
from check_integer_feasible, if it takes a long time to compute, then
it's "usually" because the context is empty and it's just taking a long
time for us to discover that it's empty. We believe in that case it
could still make sense to add all cuts.

This patch was tested on polybench 2.0 with Polly and minimal fusion.
On the larger kernels, it could not solve any infinite scheduling time
problems, but it was able to speed up one test case by 2x and did not
yield increased scheduling time for the other test cases.

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_map_fix_si: drop basic maps that have become empty
Sven Verdoolaege [Tue, 14 Feb 2012 23:18:59 +0000 (00:18 +0100)]
isl_map_fix_si: drop basic maps that have become empty

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_map.c: extract out common remove_if_empty
Sven Verdoolaege [Tue, 14 Feb 2012 23:18:21 +0000 (00:18 +0100)]
isl_map.c: extract out common remove_if_empty

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_map_coalesce: drop empty parts before checking the number of parts
Sven Verdoolaege [Tue, 14 Feb 2012 23:15:55 +0000 (00:15 +0100)]
isl_map_coalesce: drop empty parts before checking the number of parts

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Tue, 14 Feb 2012 23:22:47 +0000 (00:22 +0100)]
Merge branch 'maint'

12 years agoisl_convex_hull.c: uset_convex_hull_wrap_bounded: remove redundant constraints
Sven Verdoolaege [Tue, 14 Feb 2012 22:55:22 +0000 (23:55 +0100)]
isl_convex_hull.c: uset_convex_hull_wrap_bounded: remove redundant constraints

The caller compute_facet expects the result to not contain any redundant
constraints.  The input to uset_convex_hull_wrap_bounded, however, might
contain redundant constraints so if this input consists of only one
basic set, we need to make sure redundant constraints are removed.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_realign: preserve (most) flags
Sven Verdoolaege [Tue, 14 Feb 2012 19:02:43 +0000 (20:02 +0100)]
isl_basic_map_realign: preserve (most) flags

In particular, preserve the ISL_BASIC_MAP_EMPTY flag.
Many parts of the code check for this flags so they do not have
to deal with the "1 = 0" constraint.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_printer_print_pw_aff test
Sven Verdoolaege [Tue, 7 Feb 2012 11:26:43 +0000 (12:26 +0100)]
add isl_printer_print_pw_aff test

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_foreach_lexopt: normalize isl_affs
Sven Verdoolaege [Tue, 7 Feb 2012 11:26:20 +0000 (12:26 +0100)]
isl_basic_map_foreach_lexopt: normalize isl_affs

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_pw_*_union_add: don't subtract non-overlapping cells
Sven Verdoolaege [Tue, 7 Feb 2012 11:19:20 +0000 (12:19 +0100)]
isl_pw_*_union_add: don't subtract non-overlapping cells

There is no point in subtracting a cell from another if their intersection
is empty.  It can only lead to a further subdivision of the other cell.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_printer_print_pw_aff: skip constraints implied by div expression
Sven Verdoolaege [Tue, 7 Feb 2012 11:17:03 +0000 (12:17 +0100)]
isl_printer_print_pw_aff: skip constraints implied by div expression

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_basic_set_is_div_constraint
Sven Verdoolaege [Tue, 7 Feb 2012 11:11:26 +0000 (12:11 +0100)]
add isl_basic_set_is_div_constraint

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Tue, 7 Feb 2012 11:58:43 +0000 (12:58 +0100)]
Merge branch 'maint'

Conflicts:
isl_output.c

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_printer_print_pw_aff: fix printing in C format
Sven Verdoolaege [Tue, 7 Feb 2012 11:13:23 +0000 (12:13 +0100)]
isl_printer_print_pw_aff: fix printing in C format

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_printer_print_pw_aff was not changed accordingly.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_stream_read_pw_aff: call isl_pw_aff_union_add instead of isl_pw_aff_add
Sven Verdoolaege [Tue, 7 Feb 2012 11:09:03 +0000 (12:09 +0100)]
isl_stream_read_pw_aff: call isl_pw_aff_union_add instead of isl_pw_aff_add

We missed this in 7a86dd8 (rename isl_pw_aff_add to isl_pw_aff_union_add,
Thu Oct 13 12:16:45 2011 +0200).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_vertices.c: compute_chambers: avoid access to freed data structure
Sven Verdoolaege [Tue, 7 Feb 2012 11:55:43 +0000 (12:55 +0100)]
isl_vertices.c: compute_chambers: avoid access to freed data structure

The problem was introduced in 328c78f (isl_tab_from_basic_map: preserve all
constraints in input when tracking, Mon Jan 16 16:55:44 2012 +0100).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoexport isl_pw_multi_aff_coalesce
Sven Verdoolaege [Sun, 29 Jan 2012 15:52:15 +0000 (16:52 +0100)]
export isl_pw_multi_aff_coalesce

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoexport isl_pw_multi_aff_domain
Sven Verdoolaege [Sun, 29 Jan 2012 17:15:51 +0000 (18:15 +0100)]
export isl_pw_multi_aff_domain

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_aff_normalize: remove unused divs
Sven Verdoolaege [Mon, 30 Jan 2012 12:18:09 +0000 (13:18 +0100)]
isl_aff_normalize: remove unused divs

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_pw_multi_aff_from_map: add a special case where result can be read off
Sven Verdoolaege [Thu, 2 Feb 2012 11:01:53 +0000 (12:01 +0100)]
isl_pw_multi_aff_from_map: add a special case where result can be read off

If all output dimensions are uniquely defined in terms of the parameters
and input dimensions, we can directly read off the desired isl_pw_multi_aff.
This usually results in much simpler expressions.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoprivately export isl_basic_map_plain_is_single_valued
Sven Verdoolaege [Thu, 2 Feb 2012 09:29:43 +0000 (10:29 +0100)]
privately export isl_basic_map_plain_is_single_valued

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_printer_print_pw_aff: simplify domain expression in C format
Sven Verdoolaege [Thu, 2 Feb 2012 09:45:48 +0000 (10:45 +0100)]
isl_printer_print_pw_aff: simplify domain expression in C format

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_morph.c: fix typo in comment
Sven Verdoolaege [Wed, 1 Feb 2012 16:11:38 +0000 (17:11 +0100)]
isl_morph.c: fix typo in comment

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Wed, 1 Feb 2012 21:50:00 +0000 (22:50 +0100)]
Merge branch 'maint'

12 years agoisl_basic_set_full_compression: detect equalities in input first
Sven Verdoolaege [Wed, 1 Feb 2012 17:01:31 +0000 (18:01 +0100)]
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>
12 years agoisl_stream_read_pw_qpolynomial: accept products of integer divisions
Sven Verdoolaege [Wed, 1 Feb 2012 11:34:30 +0000 (12:34 +0100)]
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>
12 years agoisl_union_set_product: call isl_set_product on entries
Sven Verdoolaege [Tue, 31 Jan 2012 18:18:23 +0000 (19:18 +0100)]
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>
12 years agoisl_tab_pip.c: sol_add: skip empty contexts
Sven Verdoolaege [Tue, 31 Jan 2012 14:09:12 +0000 (15:09 +0100)]
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>
12 years agoisl_space_set_dim_id: also set id of parameter in nested spaces
Sven Verdoolaege [Tue, 31 Jan 2012 11:27:09 +0000 (12:27 +0100)]
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>
12 years agoisl_space_set_dim_id: rename "dim" variable to "space"
Sven Verdoolaege [Tue, 31 Jan 2012 11:24:38 +0000 (12:24 +0100)]
isl_space_set_dim_id: rename "dim" variable to "space"

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoscheduler: replace split_parallel by split_scaled option
Sven Verdoolaege [Sun, 29 Jan 2012 13:42:16 +0000 (14:42 +0100)]
scheduler: replace split_parallel by split_scaled option

The split_parallel option was ill-conceived.
The condition split_parallel looked for was too specific
and the implementation was wrong.  Part of this has been fixed
in 1b2fdb6 (schedule.c: split_parallel: avoid invalid memory accesses,
Mon Jan 30 15:23:18 2012 +0100), but the code could in principle
still produce an incorrect schedule because it didn't check the sizes
of the constant terms.

The new option essentially applies strip-mining and should therefore
be safe.  In particular, it is applied when the linear parts of the
schedules have a non-trivial common divisor.  The strip-mining is
then performed with respect to this common divisor.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoadd isl_mat_scale_down_row
Sven Verdoolaege [Sun, 29 Jan 2012 13:42:01 +0000 (14:42 +0100)]
add isl_mat_scale_down_row

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoAdd isl_union_map_gist_range
Tobias Grosser [Mon, 30 Jan 2012 12:19:38 +0000 (13:19 +0100)]
Add isl_union_map_gist_range

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoscheduler: add an option to configure the level of fusing
Sven Verdoolaege [Sat, 26 Nov 2011 14:52:07 +0000 (15:52 +0100)]
scheduler: add an option to configure the level of fusing

We currently only support maximal (the old behavior) and minimal fusion.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Mon, 30 Jan 2012 14:28:04 +0000 (15:28 +0100)]
Merge branch 'maint'

12 years agoschedule.c: split_parallel: avoid invalid memory accesses
Sven Verdoolaege [Mon, 30 Jan 2012 14:23:18 +0000 (15:23 +0100)]
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>
12 years agoupdate for change in clang's HandleTopLevelDecl return type
Sven Verdoolaege [Wed, 18 Jan 2012 13:18:26 +0000 (14:18 +0100)]
update for change in clang's HandleTopLevelDecl return type

In recent versions of clang, HandleTopLevelDecl should return a boolean
indicating whether parsing should continue.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoconfigure.ac: only link against libraries from LLVM analysis component
Sven Verdoolaege [Wed, 18 Jan 2012 15:47:38 +0000 (16:47 +0100)]
configure.ac: only link against libraries from LLVM analysis component

Before, we would link against all LLVM components, which would make
us depend on google-test.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoput annotations after "struct"
Sven Verdoolaege [Wed, 18 Jan 2012 15:49:19 +0000 (16:49 +0100)]
put annotations after "struct"

Recent versions of clang require the annotations to be placed after "struct".

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoMerge branch 'maint'
Sven Verdoolaege [Wed, 18 Jan 2012 17:41:37 +0000 (18:41 +0100)]
Merge branch 'maint'

12 years agoisl_pw_aff_non_zero_set: don't assume isl_pw_aff is total
Sven Verdoolaege [Tue, 17 Jan 2012 12:52:09 +0000 (13:52 +0100)]
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>
12 years agoisl_aff_nonneg_basic_set and isl_aff_zero_basic_set: simplify result
Sven Verdoolaege [Wed, 18 Jan 2012 17:36:53 +0000 (18:36 +0100)]
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>
12 years agoisl_tab_from_basic_map: preserve all constraints in input when tracking
Sven Verdoolaege [Mon, 16 Jan 2012 15:55:44 +0000 (16:55 +0100)]
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>
12 years agoisl_tab_track_bmap: drop sanity checks in case of empty tab
Sven Verdoolaege [Mon, 16 Jan 2012 15:46:55 +0000 (16:46 +0100)]
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>
12 years agoisl_tab_track_bmap: make sure we have a unique copy of the basic map
Sven Verdoolaege [Mon, 16 Jan 2012 15:21:49 +0000 (16:21 +0100)]
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>
12 years agoisl_tab_track_bmap: fix memory leak on error path
Sven Verdoolaege [Mon, 16 Jan 2012 11:59:33 +0000 (12:59 +0100)]
isl_tab_track_bmap: fix memory leak on error path

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoisl_basic_map_remove_unknown_divs: restart whenever div has been removed
Sven Verdoolaege [Sun, 15 Jan 2012 15:12:49 +0000 (16:12 +0100)]
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>
12 years agoisl_map_simple_hull: improve error handling
Sven Verdoolaege [Sun, 15 Jan 2012 14:21:17 +0000 (15:21 +0100)]
isl_map_simple_hull: improve error handling

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
12 years agoexport isl_multi_aff_drop_dims
Sven Verdoolaege [Thu, 12 Jan 2012 14:49:38 +0000 (15:49 +0100)]
export isl_multi_aff_drop_dims

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