Sven Verdoolaege [Wed, 21 Apr 2010 13:53:01 +0000 (15:53 +0200)]
isl_map_transitive_closure, omega-like: only use ?-closure if result is exact
Sven Verdoolaege [Tue, 20 Apr 2010 22:05:02 +0000 (00:05 +0200)]
isl_map_transitive_closure: use simple hull in omega-like implementation
Sven Verdoolaege [Fri, 16 Apr 2010 15:36:29 +0000 (17:36 +0200)]
isl_map_transitive_closure: try and compute closure incrementally
Sven Verdoolaege [Sun, 18 Apr 2010 15:50:05 +0000 (17:50 +0200)]
isl_map_coalesce: allow wrapping in sets that stick out in different directions
Before, we would only wrap in sets that extend beyond exactly
one facet of a given set and such that the wrapped in set itself
has a facet that is adjacent to this facet.
We now extend this process in several ways.
First, the wrapped-in set is allowed to extend beyond several facets.
Second, the wrapped-in set need not have facets adjacent to these facets.
It is sufficient that the adjacent facets are valid for the wrapped-in set.
Finally, the wrapped-in set is allowed to be of a lower dimension.
Sven Verdoolaege [Sun, 18 Apr 2010 16:37:56 +0000 (18:37 +0200)]
isl_map_coalesce: allowing cutting equalities in adjacent facet
From the start, we have been very careful not to allow any cutting
equalities anywhere. However, it makes sense to wrap in a piece
of a hyperplane adjacent to a facet, even if this piece is
lower-dimensional.
Sven Verdoolaege [Thu, 22 Apr 2010 06:42:32 +0000 (08:42 +0200)]
add some more coalescing test cases
Sven Verdoolaege [Fri, 23 Apr 2010 10:00:58 +0000 (12:00 +0200)]
isl_basic_map_gist: be more aggressive in removing constraints
In particular, detect equalities in intersection of input and context
and check for each constraint if negating it would lead to a contradiction.
Sven Verdoolaege [Thu, 22 Apr 2010 05:50:49 +0000 (07:50 +0200)]
isl_stream: accept string tokens
Sven Verdoolaege [Thu, 22 Apr 2010 11:07:22 +0000 (13:07 +0200)]
isl_tab_rollback: restore rows that are no longer marked redundant
When a row is marked redundant, it may have a negative (but strictly
larger than -1) sample value. When undoing this marking, we need
to make sure the sample value is restored to a non-negative value.
Sven Verdoolaege [Wed, 21 Apr 2010 15:15:51 +0000 (17:15 +0200)]
doc: document simple hull
Sven Verdoolaege [Wed, 21 Apr 2010 15:11:29 +0000 (17:11 +0200)]
doc: emphasize that we are dealing with integer sets
Sven Verdoolaege [Wed, 21 Apr 2010 11:40:26 +0000 (13:40 +0200)]
isl_transitive_closure.c: path_along_delta: only avoid splitting off identity
Commit 39345fc (isl_transitive_closure.c: path_along_delta: try and avoid
splitting off identity) attempted to avoid splitting off the identity mapping.
However, it would only check if relaxing the length to zero would
not introduce any extra elements. The path may have constraints
on the parameters, though, and so we may actually be removing elements.
This means that we need to check for equality with the identity relation.
Perhaps this makes the whole optimization pointless.
Sven Verdoolaege [Tue, 20 Apr 2010 21:44:38 +0000 (23:44 +0200)]
isl_map_transitive_closure: compute divs of input
Sven Verdoolaege [Wed, 21 Apr 2010 15:42:24 +0000 (17:42 +0200)]
isl_map_compute_divs: make sure result is gaussed and finalized
In particular, when the variables in the input can be compressed,
basic_set_append_equalities should gauss and finalize the result
of adding the equalities back in.
Sven Verdoolaege [Wed, 21 Apr 2010 11:37:47 +0000 (13:37 +0200)]
isl_printer_print_pw_qpolynomial: properly print constraints in C format
In particular, use an explicit multiplication in affine expressions.
Sven Verdoolaege [Mon, 19 Apr 2010 15:56:54 +0000 (17:56 +0200)]
isl_pip and isl_cat: terminate isl_arg array with ISL_ARG_END
On most systems, leaving it out apparently just happens to work,
but not so on MacOS X.
Problem reported and analyzed by Tomofumi Yuki <yuki@cs.colostate.edu>
Sven Verdoolaege [Mon, 19 Apr 2010 09:27:52 +0000 (11:27 +0200)]
doc: document setting and getting of dimension names
Sven Verdoolaege [Mon, 19 Apr 2010 09:18:42 +0000 (11:18 +0200)]
doc: document *_get_dim functions
Sven Verdoolaege [Mon, 19 Apr 2010 08:53:13 +0000 (10:53 +0200)]
isl_map_convex_hull: handle non full-dimensional pairs of basic sets
Sven Verdoolaege [Mon, 19 Apr 2010 08:38:54 +0000 (10:38 +0200)]
isl_convex_hull.c: modulo_affine_hull: drop redundant argument
Sven Verdoolaege [Mon, 19 Apr 2010 07:23:55 +0000 (09:23 +0200)]
isl_convex_hull.c: convex_hull_pair: skip direction change if result is bounded
Sven Verdoolaege [Sun, 18 Apr 2010 19:55:05 +0000 (21:55 +0200)]
isl_printer_print_basic_set: fix up printing to string printer
In particular, only print prefix and suffix (and call strlen on them)
if they are not NULL.
Problem reported by Tomofumi Yuki <yuki@cs.colostate.edu>
Sven Verdoolaege [Sat, 17 Apr 2010 15:49:42 +0000 (17:49 +0200)]
add isl_set_neg and isl_set_sum
Sven Verdoolaege [Fri, 16 Apr 2010 15:36:07 +0000 (17:36 +0200)]
isl_transitive_closure.c: fix documentation of construct_component
Sven Verdoolaege [Thu, 15 Apr 2010 18:30:48 +0000 (20:30 +0200)]
isl_map_coalesce: make sure result still contains set after wrapping in a facet
Sven Verdoolaege [Thu, 15 Apr 2010 14:47:35 +0000 (16:47 +0200)]
isl_map_transitive_closure: Floyd-Warshall: properly keep track of current group
Sven Verdoolaege [Wed, 14 Apr 2010 10:25:19 +0000 (12:25 +0200)]
isl_map_transitive_closure: use Floyd-Warshall on disjoint domains and ranges
Sven Verdoolaege [Thu, 15 Apr 2010 09:09:37 +0000 (11:09 +0200)]
isl_transitive_closure.c: extract out isl_set_overlaps
Sven Verdoolaege [Wed, 14 Apr 2010 11:10:50 +0000 (13:10 +0200)]
isl_map_transitive_closure: project out length on each component separately
There is no need to keep track of the length over multiple components.
Sven Verdoolaege [Wed, 14 Apr 2010 11:00:18 +0000 (13:00 +0200)]
isl_transitive_closure.c: construct_component: don't include identity in result
Sven Verdoolaege [Wed, 14 Apr 2010 10:39:56 +0000 (12:39 +0200)]
isl_map_transitive_closure: don't add length parameter
Just project out the final coordinates, intead of equating the difference
to a parameter and then projecting out the difference.
Sven Verdoolaege [Thu, 15 Apr 2010 09:12:53 +0000 (11:12 +0200)]
doc: fix typos
Sven Verdoolaege [Tue, 13 Apr 2010 17:41:50 +0000 (19:41 +0200)]
isl_set_gist: make context argument an isl_set for consistency
Sven Verdoolaege [Tue, 13 Apr 2010 08:07:14 +0000 (10:07 +0200)]
isl_map_transitive_closure: coalesce input map
Sven Verdoolaege [Tue, 13 Apr 2010 07:54:17 +0000 (09:54 +0200)]
isl_transitive_closure.c: construct_component: always include identity
Commit e06f258 (isl_map_transitive_closure: break early if input map
doesn't compose with itself) added a special case to construct_component,
but neglected to include the identity map in the result.
Sven Verdoolaege [Tue, 13 Apr 2010 07:31:58 +0000 (09:31 +0200)]
doc: cite Omega library documentation on computation of underapproximations
Sven Verdoolaege [Tue, 13 Apr 2010 07:30:02 +0000 (09:30 +0200)]
add isl_stream_read_map
Sven Verdoolaege [Tue, 13 Apr 2010 07:29:38 +0000 (09:29 +0200)]
isl_arg.h: add missing include
Sven Verdoolaege [Sun, 11 Apr 2010 11:36:38 +0000 (13:36 +0200)]
isl_basic_map_move_dims: normalize equalities
Sven Verdoolaege [Sun, 11 Apr 2010 10:43:27 +0000 (12:43 +0200)]
rename isl_map_move to isl_map_move_dims
Sven Verdoolaege [Sat, 10 Apr 2010 15:54:28 +0000 (17:54 +0200)]
isl_options_parse: only parse known options by default
That is, only barf on unknown options when the user explicitly
asks for this behavior.
Sven Verdoolaege [Thu, 8 Apr 2010 08:04:46 +0000 (10:04 +0200)]
isl_map_closure: optionally use Omega-like algorithm
Sven Verdoolaege [Thu, 8 Apr 2010 08:09:01 +0000 (10:09 +0200)]
isl_closure: take options
Sven Verdoolaege [Sat, 10 Apr 2010 14:19:23 +0000 (16:19 +0200)]
isl_map_affine_hull: handle non-obviously empty input
In particular, detect equalities before checking whether the input is empty.
Otherwise, we could be accessing the first element of an empty list.
Sven Verdoolaege [Sat, 10 Apr 2010 14:15:38 +0000 (16:15 +0200)]
isl_map_compute_divs: handle non-obviously empty input
In particular, properly handle the case where variable compression
detects that the input map is actually empty.
Sven Verdoolaege [Sat, 10 Apr 2010 14:13:46 +0000 (16:13 +0200)]
isl_basic_set_preimage: add extra sanity check
Sven Verdoolaege [Sat, 10 Apr 2010 14:13:10 +0000 (16:13 +0200)]
isl_basic_map_set_to_empty: add missing assignment
Sven Verdoolaege [Sat, 10 Apr 2010 14:12:26 +0000 (16:12 +0200)]
isl_equalities.c: isl_mat_variable_compression: clarify result
Sven Verdoolaege [Sat, 10 Apr 2010 13:44:03 +0000 (15:44 +0200)]
isl_sample.c: initial_basis: set n_unbounded and n_zero
n_unbounded and n_zero are initialized to zero, but they can
be set to non-zero values in isl_tab_set_initial_basis_with_cone.
If isl_tab_sample is later called on an updated tab, but with
the old basis removed, then these values, in particular n_unbounded,
may not be valid anymore.
In particular, this happens in isl_tab_pip.c's gbr_get_sample.
Arguably, gbr_get_sample should reset the values of n_zero and n_unbounded
when it drops the basis, but it doens't hurt for initial_basis
to reset those values too.
Sven Verdoolaege [Fri, 9 Apr 2010 11:10:03 +0000 (13:10 +0200)]
isl_map_coalesce: only use non-redundant constraints during wrapping
Constraints that have been marked redundant are ignored and may
no longer be valid, so they shouldn't be taken into account during wrapping.
Sven Verdoolaege [Fri, 9 Apr 2010 10:52:47 +0000 (12:52 +0200)]
isl_map_print: allow empty constraints
A basic map that is passed to the user should never contain a constraint
"0 >= 0". However, internally, such constraints can exist for a while
and for debugging purposes, it's convenient to be able to print
basic maps with such constraints.
Sven Verdoolaege [Fri, 9 Apr 2010 09:04:30 +0000 (11:04 +0200)]
isl_options.h: allow inclusion from C++
Sven Verdoolaege [Fri, 9 Apr 2010 09:04:17 +0000 (11:04 +0200)]
isl_arg.h: allow inclusion from C++
Sven Verdoolaege [Mon, 5 Apr 2010 20:55:17 +0000 (22:55 +0200)]
isl_map_transitive_closure: handle existentials
Sven Verdoolaege [Wed, 7 Apr 2010 15:18:06 +0000 (17:18 +0200)]
isl_map_deltas: preserve dimension names
Sven Verdoolaege [Wed, 7 Apr 2010 14:03:00 +0000 (16:03 +0200)]
isl_map_print: support LaTeX output format
Sven Verdoolaege [Wed, 7 Apr 2010 13:59:02 +0000 (15:59 +0200)]
isl_map_simplify: don't remove any div definitions if all divs are known
isl_map_simplify is called from within compute_divs, so we need
to make sure it doesn't remove any divs just computed.
Unfortunately, being more strict about not removing any div definition
means that we break some test cases, so they are disabled now.
Perhaps we can think of a better way of making the tests pass later.
Sven Verdoolaege [Mon, 5 Apr 2010 17:57:27 +0000 (19:57 +0200)]
isl_map_intersect: add special cases for empty input maps
In particular, if both input maps consist of a single basic map
and that of the first map turns out to be empty, then we need
to take into account that after cowing the map, it may not
have any basic maps anymore.
Sven Verdoolaege [Mon, 5 Apr 2010 15:03:33 +0000 (17:03 +0200)]
isl_transitive_closure.c: path_along_delta: share code for handling {in,}equalities
Sven Verdoolaege [Mon, 5 Apr 2010 14:30:49 +0000 (16:30 +0200)]
isl_transitive_closure.c: path_along_delta: try and avoid splitting off identity
Usually, path_along_delta returns a union of the identity mapping and
of paths of length at least 1. In some cases, the paths of length
0 correspond exactly to the identity mapping and then it is more
efficient to return a single mapping with paths of length at least 0.
Sven Verdoolaege [Sun, 4 Apr 2010 13:41:21 +0000 (15:41 +0200)]
export isl_qpolynomial_move_dims
Sven Verdoolaege [Sat, 3 Apr 2010 14:47:27 +0000 (16:47 +0200)]
add isl_qpolynomial_get_ctx
Sven Verdoolaege [Sat, 3 Apr 2010 13:10:15 +0000 (15:10 +0200)]
add isl_pw_qpolynomial_fold_get_dim
Sven Verdoolaege [Sat, 3 Apr 2010 09:08:29 +0000 (11:08 +0200)]
add some qpolynomial test functions
Sven Verdoolaege [Sat, 3 Apr 2010 08:49:39 +0000 (10:49 +0200)]
add isl_pw_qpolynomial_fold_{max,min}
Sven Verdoolaege [Fri, 2 Apr 2010 20:59:43 +0000 (22:59 +0200)]
isl_tab_min_at_most_neg_one: restore sample value of non-redundant constraints
Sven Verdoolaege [Fri, 2 Apr 2010 20:45:57 +0000 (22:45 +0200)]
isl_map_coalesce: avoid reconsidering pairs considered before on change
Before, whenever anything changed (two elements get fused or one
element gets dropped), we would start all over from scratch.
Pairs that were already considered before and that are not related
to the change do not need to be reconsidered.
We may still reconsider some pairs, even after this commit.
In particular, if one element gets dropped, then we will still reconsider
all combinations with the element that did not get dropped.
Sven Verdoolaege [Fri, 2 Apr 2010 15:37:02 +0000 (17:37 +0200)]
isl_tab.c: update debugging aid check_table to presence of big parameter
Sven Verdoolaege [Fri, 2 Apr 2010 15:34:02 +0000 (17:34 +0200)]
isl_tab_relax: make sure no non-negative rows get a negative sample value
Sven Verdoolaege [Fri, 2 Apr 2010 10:13:22 +0000 (12:13 +0200)]
isl_tab_pip.c: always set row sign of found row to isl_tab_row_neg
first_neg returns row that is obviously negative and usually
sets the sign of the row to isl_tab_row_neg. However, if
the row happens to be obviously negative because the big parameter
has a negative coefficient, then it would fail to set the row sign,
while update_row_sign check that the row sign is effectively set
to isl_tab_row_neg.
Sven Verdoolaege [Fri, 2 Apr 2010 09:03:50 +0000 (11:03 +0200)]
isl_printer_print_basic_{set,map}: add closing "}"
They were removed by accident in commit 5aef299 (add isl_printer).
Sven Verdoolaege [Thu, 1 Apr 2010 16:13:51 +0000 (18:13 +0200)]
export isl_set_split_dims
Sven Verdoolaege [Thu, 1 Apr 2010 15:17:42 +0000 (17:17 +0200)]
add isl_set_recession_cone
Sven Verdoolaege [Thu, 1 Apr 2010 14:39:52 +0000 (16:39 +0200)]
add isl_set_dim_is_bounded
Sven Verdoolaege [Wed, 31 Mar 2010 19:37:00 +0000 (21:37 +0200)]
isl_map_transitive_closure: break early if input map doesn't compose with itself
Sven Verdoolaege [Wed, 31 Mar 2010 19:19:22 +0000 (21:19 +0200)]
isl_map_transitive_closure: coalesce after each step
Without coalescing, the number of disjuncts in the result
is exponential in the number of disjuncts in the input.
Sven Verdoolaege [Tue, 30 Mar 2010 15:26:11 +0000 (17:26 +0200)]
export isl_pw_qpolynomial_coalesce
Sven Verdoolaege [Tue, 30 Mar 2010 09:56:41 +0000 (11:56 +0200)]
isl_tab.c: unrelax: restore row if variable is non-negative
Unrelaxing a constraint means that the constraint is tightened.
The sample value may therefore become negative and then have to
restore the row again. This is guaranteed to succeed because
the tableau was supposed to be in a valid state before the constraint
was relaxed.
Sven Verdoolaege [Tue, 30 Mar 2010 09:49:21 +0000 (11:49 +0200)]
isl_tab.c: cut_to_hyperplane: add extra sanity check
Sven Verdoolaege [Sun, 28 Mar 2010 11:11:55 +0000 (13:11 +0200)]
add isl_pw_qpolynomial_fold_size
Sven Verdoolaege [Sun, 28 Mar 2010 11:10:40 +0000 (13:10 +0200)]
add isl_pw_qpolynomial_split_dims
Sven Verdoolaege [Sat, 27 Mar 2010 12:21:00 +0000 (13:21 +0100)]
isl_qpolynomial_max: fix detection of inactive variables
Without this patch, some active set dimensions would be treated
as inactive and effectively be removed, resulting in an incorrect maximum.
Sven Verdoolaege [Thu, 25 Mar 2010 15:21:08 +0000 (16:21 +0100)]
doc: fix transitive closure example
Sven Verdoolaege [Tue, 23 Mar 2010 23:07:14 +0000 (00:07 +0100)]
isl_convex_hull.c: valid_direction: properly normalize valid direction
The original code would only normalize all but one of the coordinates
of the valid direction, possibly resulting in a scaled direction, which
may no longer be valid. Normalize the whole vector, resulting in only
a change of representation and not a change of direction.
Sven Verdoolaege [Tue, 23 Mar 2010 13:46:50 +0000 (14:46 +0100)]
isl_convex_hull.c: simplify computation of initial facet constraint
The old implementation was needlessly complicated and apparently
incorrect (witness the extra test case).
The simplified version passes the new test case.
The new test case is based on a bug report for CLooG/isl
by Muthu Manikandan <muthumanikandan@gmail.com>.
Sven Verdoolaege [Mon, 22 Mar 2010 20:09:55 +0000 (21:09 +0100)]
export isl_pw_qpolynomial_is_zero
Sven Verdoolaege [Mon, 22 Mar 2010 18:21:21 +0000 (19:21 +0100)]
add isl_pw_qpolynomial_fold_dim
Sven Verdoolaege [Mon, 22 Mar 2010 14:15:19 +0000 (15:15 +0100)]
add isl_int_get_d
Sven Verdoolaege [Mon, 22 Mar 2010 12:20:44 +0000 (13:20 +0100)]
add isl_pw_qpolynomial_min
Sven Verdoolaege [Mon, 22 Mar 2010 12:04:52 +0000 (13:04 +0100)]
add isl_pw_qpolynomial_fix_dim
Sven Verdoolaege [Sun, 21 Mar 2010 15:36:46 +0000 (16:36 +0100)]
add isl_pw_qpolynomial_add_dims
Sven Verdoolaege [Sun, 21 Mar 2010 14:42:00 +0000 (15:42 +0100)]
export isl_dim_move
Sven Verdoolaege [Sun, 21 Mar 2010 13:48:48 +0000 (14:48 +0100)]
isl_pw_qpolynomial_fold_add: remove redundant quasipolynomials from folds
Sven Verdoolaege [Sun, 21 Mar 2010 13:06:48 +0000 (14:06 +0100)]
isl_qpolynomial_alloc: take initial struct isl_upoly as argument
Sven Verdoolaege [Sun, 21 Mar 2010 12:24:47 +0000 (13:24 +0100)]
add isl_set_solve_lp
Sven Verdoolaege [Sat, 20 Mar 2010 16:15:51 +0000 (17:15 +0100)]
isl_polynomial.c: separate out fold functionality to isl_fold.c
Sven Verdoolaege [Sat, 20 Mar 2010 15:58:39 +0000 (16:58 +0100)]
isl_pw_qpolynomial_{fold_,}print: set output format
Sven Verdoolaege [Sat, 20 Mar 2010 14:46:54 +0000 (15:46 +0100)]
improve isl_pw_qpolynomial_move
Sven Verdoolaege [Sat, 20 Mar 2010 13:19:05 +0000 (14:19 +0100)]
add isl_mat_move_cols
Sven Verdoolaege [Fri, 19 Mar 2010 16:51:21 +0000 (17:51 +0100)]
add isl_pw_qpolynomial_drop_dims