Sven Verdoolaege [Wed, 29 Jul 2009 12:33:14 +0000 (14:33 +0200)]
rename isl_basic_map_lex{min,max} to isl_basic_map_partial_lex{min,max}
Sven Verdoolaege [Tue, 28 Jul 2009 14:21:42 +0000 (16:21 +0200)]
add isl_basic_set_free_div
Sven Verdoolaege [Tue, 28 Jul 2009 11:48:54 +0000 (13:48 +0200)]
isl_set_dim: support isl_dim_all
Sven Verdoolaege [Fri, 24 Jul 2009 15:47:35 +0000 (17:47 +0200)]
isl_tab: store index of variable in undo record instead of pointer to variable
The row of variables might get reallocated between pushing the undo
record and performing the undo, invalidating the pointer.
Sven Verdoolaege [Fri, 24 Jul 2009 10:22:14 +0000 (12:22 +0200)]
add isl_{set,map}_grow
Sven Verdoolaege [Sun, 2 Aug 2009 17:11:15 +0000 (19:11 +0200)]
add isl_map_get_dim
Sven Verdoolaege [Sun, 2 Aug 2009 17:05:36 +0000 (19:05 +0200)]
add isl_basic_map_get_dim
Sven Verdoolaege [Tue, 4 Aug 2009 17:39:23 +0000 (19:39 +0200)]
add isl_tab_dup
Sven Verdoolaege [Tue, 4 Aug 2009 17:33:09 +0000 (19:33 +0200)]
export isl_mat_dup
Sven Verdoolaege [Thu, 23 Jul 2009 16:51:26 +0000 (18:51 +0200)]
isl_tab.c: mark_redundant: only mark variable nonneg if they weren't already
More imporantly, don't undo such a mark during rollback.
Sven Verdoolaege [Thu, 23 Jul 2009 16:15:17 +0000 (18:15 +0200)]
isl_tab.c: to_row: allow pivoting in arbitrary direction
While undoing the allocation of a row, we may be dealing with
a row that was unbounded in both directions and is now in a column.
To move the column back to a row, we just pivot using any non-zero entry.
Sven Verdoolaege [Thu, 23 Jul 2009 13:29:44 +0000 (15:29 +0200)]
isl_tab.c: simplify code by letting mark_empty return tab
Sven Verdoolaege [Thu, 23 Jul 2009 09:46:25 +0000 (11:46 +0200)]
add isl_seq_last_non_zero
Sven Verdoolaege [Thu, 23 Jul 2009 09:40:43 +0000 (11:40 +0200)]
isl_tab.c: simplify add_eq
Sven Verdoolaege [Thu, 23 Jul 2009 07:24:41 +0000 (09:24 +0200)]
isl_tab.c: extract allocate_con
Sven Verdoolaege [Wed, 22 Jul 2009 11:39:26 +0000 (13:39 +0200)]
privately export isl_basic_set_set_rational
Sven Verdoolaege [Wed, 22 Jul 2009 19:35:40 +0000 (21:35 +0200)]
configure.ac: explicitly set AC_CONFIG_AUX_DIR
Without it, libtool can apparently get confused about which
ltmain.sh to use.
Sven Verdoolaege [Tue, 21 Jul 2009 11:37:22 +0000 (13:37 +0200)]
convex_hull: coalesce set during facet computation
Sven Verdoolaege [Tue, 21 Jul 2009 11:31:47 +0000 (13:31 +0200)]
isl_map_coalesce: don't drop rational flag from result if set in input
Sven Verdoolaege [Mon, 20 Jul 2009 19:46:14 +0000 (21:46 +0200)]
isl_tab_cone_is_bounded: start over after computing sign_of_max
sign_of_max may have made some rows redundant and may therefore
invalidate the iteration over all non-redundant rows.
Problem reported by Uday Kumar <udayreddy@gmail.com>
Sven Verdoolaege [Sat, 18 Jul 2009 16:06:02 +0000 (18:06 +0200)]
isl_basic_set_dim_residue_class: only set *modulo to 0 when dimension is fixed
Before, when no residue class could be detected, *modulo was sometimes
set to 0 and sometimes to 1. Now *modulo is always set to 1 in these
cases, except when the specified dimension has a fixed constant value,
in which case *modulo is set to 0 and *residue to the fixed value.
Sven Verdoolaege [Sat, 18 Jul 2009 16:00:14 +0000 (18:00 +0200)]
add isl_basic_set_fast_dim_is_fixed
Sven Verdoolaege [Thu, 16 Jul 2009 18:03:29 +0000 (20:03 +0200)]
isl_tab: drop isl_ctx argument where not absolutely required
Sven Verdoolaege [Thu, 16 Jul 2009 17:16:06 +0000 (19:16 +0200)]
isl_mat: keep track of isl_ctx
Sven Verdoolaege [Thu, 16 Jul 2009 09:00:32 +0000 (11:00 +0200)]
isl_basic_set_sample: don't project out lineality space up front
For the pip based sampler, projecting out the lineality space
is part of isl_basic_set_skew_to_positive_orthant, so there is
no need for a separate projection step before the skewing.
For the gbr based sampler, there is no need to project out the lineality
space. The lineality space will simply be part of the recession cone,
which is handled more efficiently than the projection.
In particular, for systems with many variables, the unimodular transformation
used in the projection may have very large coefficients, which in turn
leads to constraints with large coefficients. Since there is no need
to do this projection, it is best to avoid it.
Sven Verdoolaege [Wed, 15 Jul 2009 08:35:43 +0000 (10:35 +0200)]
isl_basic_map_fix_pos: micro-optimization
Sven Verdoolaege [Tue, 14 Jul 2009 13:34:00 +0000 (15:34 +0200)]
move isl_basic_set_skew_to_positive_orthant to isl_sample.c
Also, replace independent_bounds in isl_sample.c by that
of isl_sample_piplib.c
The difference is that the latter returns affine bounds
rather than linear bounds and that it return the actual
bounds from the set rather than some linear combinations
of bounds.
It is usually better to use the original bounds as
the linearly transformed bounds may have bigger coefficients
and may therefore be more difficult to process.
Sven Verdoolaege [Mon, 13 Jul 2009 15:02:37 +0000 (17:02 +0200)]
isl_tab.c: fix typo in comment
Sven Verdoolaege [Mon, 13 Jul 2009 10:23:49 +0000 (12:23 +0200)]
isl_basic_set_sample: break early if sample found in basic_set_range
Sven Verdoolaege [Mon, 13 Jul 2009 09:49:43 +0000 (11:49 +0200)]
export isl_tab_sample_is_integer
Sven Verdoolaege [Mon, 13 Jul 2009 09:23:06 +0000 (11:23 +0200)]
isl_basic_set_sample: check sample stored by isl_basic_map_is_empty first
Sven Verdoolaege [Mon, 13 Jul 2009 09:22:10 +0000 (11:22 +0200)]
isl_basic_map_is_empty: remove stale sample
Sven Verdoolaege [Mon, 15 Jun 2009 10:02:54 +0000 (12:02 +0200)]
add isl_polyhedron_sample application
Sven Verdoolaege [Mon, 15 Jun 2009 10:02:54 +0000 (12:02 +0200)]
introduce generalized basis reduction based sampling
Also make gbr the default for computing sample integer points.
It may be a bit slower than pip on easy problems, but pip can
sometimes get into serious problems, especially in cases where
the given set does not contain any integer points. The gbr
method performs much better in these cases.
Sven Verdoolaege [Wed, 15 Jul 2009 09:00:18 +0000 (11:00 +0200)]
add isl_seq_cdiv_q
Sven Verdoolaege [Sun, 12 Jul 2009 10:30:49 +0000 (12:30 +0200)]
isl_sample.c: interval_sample: drop redundant argument
Sven Verdoolaege [Sun, 12 Jul 2009 16:47:58 +0000 (18:47 +0200)]
isl_sample.c: clean up handling of lineality space
Sven Verdoolaege [Sun, 12 Jul 2009 09:43:03 +0000 (11:43 +0200)]
isl_sample.c: extract out sample_eq
Sven Verdoolaege [Sun, 12 Jul 2009 09:16:34 +0000 (11:16 +0200)]
isl_sample.c: interval_sample: handle equalities directly
Sven Verdoolaege [Sun, 12 Jul 2009 08:47:22 +0000 (10:47 +0200)]
isl_sample.c: extract out empty_sample
Sven Verdoolaege [Sat, 11 Jul 2009 17:56:06 +0000 (19:56 +0200)]
isl_sample.c: generalize point_sample to zero_sample
Sven Verdoolaege [Sat, 11 Jul 2009 13:40:41 +0000 (15:40 +0200)]
isl_tab: don't create new undo records during rollback
Sven Verdoolaege [Sat, 11 Jul 2009 13:33:25 +0000 (15:33 +0200)]
isl_tab_min: use general rollback mechanism
Sven Verdoolaege [Sat, 11 Jul 2009 13:15:26 +0000 (15:15 +0200)]
isl_tab: optionally save dual solution
Sven Verdoolaege [Sat, 11 Jul 2009 12:26:15 +0000 (14:26 +0200)]
isl_tab: add isl_tab_add_valid_eq
Sven Verdoolaege [Sat, 11 Jul 2009 09:11:23 +0000 (11:11 +0200)]
export isl_tab_alloc
Sven Verdoolaege [Fri, 10 Jul 2009 16:00:48 +0000 (18:00 +0200)]
add isl_int_le
Sven Verdoolaege [Thu, 9 Jul 2009 14:20:47 +0000 (16:20 +0200)]
privately export isl_basic_set_recession_cone
Sven Verdoolaege [Thu, 9 Jul 2009 13:49:07 +0000 (15:49 +0200)]
isl_convex_hull.c: add missing assignment
Sven Verdoolaege [Thu, 9 Jul 2009 13:15:51 +0000 (15:15 +0200)]
privately export isl_basic_set_lineality_space
Sven Verdoolaege [Thu, 9 Jul 2009 09:16:41 +0000 (11:16 +0200)]
isl_vec: keep track of isl_ctx
Sven Verdoolaege [Sun, 12 Jul 2009 10:23:35 +0000 (12:23 +0200)]
isl_coalesce.c: fix typo
Sven Verdoolaege [Sat, 13 Jun 2009 11:20:54 +0000 (13:20 +0200)]
update piplib for change in configure arguments
Sven Verdoolaege [Mon, 25 May 2009 21:43:50 +0000 (23:43 +0200)]
isl_basic_map_drop_redundant_divs: coalesce divs if possible
Sven Verdoolaege [Fri, 22 May 2009 10:17:00 +0000 (12:17 +0200)]
isl_basic_map_drop_redundant_divs: set div expression if obvious from constraints
Sven Verdoolaege [Sat, 23 May 2009 11:59:32 +0000 (13:59 +0200)]
isl_basic_map_drop_redundant_divs: drop more kinds of redundant divs
Sven Verdoolaege [Fri, 22 May 2009 09:26:31 +0000 (11:26 +0200)]
isl_map_compute_divs: drop obviously redundant divs first
Sven Verdoolaege [Fri, 22 May 2009 09:18:26 +0000 (11:18 +0200)]
isl_map_piplib.c: extremum_on: detect equalities first
In a map with several divs, there may be some that are
actually equal to each other (up to a constant). Any
div present in the map will make the search for the
lexicographic maximum or minimum more difficult, so
we want to remove such duplicate divs before embarking
on the search.
This situation occurs especially during dependence
analysis (in an outside user of isl). Perhaps it
would be best if the outside user would attempt
to remove duplicate divs instead of doing it
indiscriminately inside the library, but for now
it is easiest to just put it here.
Sven Verdoolaege [Mon, 25 May 2009 10:59:23 +0000 (12:59 +0200)]
isl_pip_basic_map_compute_divs: remove some equalities first
Sven Verdoolaege [Sun, 24 May 2009 14:18:34 +0000 (16:18 +0200)]
isl_pip_basic_map_compute_divs: separate out dimension games
We want to do some additional transformations on the input
set and it is easier to perform these transformations
with the existential variables considered as output variables.
Sven Verdoolaege [Mon, 25 May 2009 10:10:38 +0000 (12:10 +0200)]
isl_basic_set_preimage: handle divs in input
Sven Verdoolaege [Sun, 7 Jun 2009 14:29:08 +0000 (16:29 +0200)]
isl_input_omega.c: make variable_{free,new} static
Sven Verdoolaege [Sun, 7 Jun 2009 14:24:47 +0000 (16:24 +0200)]
isl_map.c: make add_divs static
Sven Verdoolaege [Tue, 2 Jun 2009 13:05:56 +0000 (15:05 +0200)]
isl_basic_map_simplify: detect div constraints while looking for duplicates
During the detection of duplicate constraints we also look for pairs
of opposite constraints and these can potentially be used to define
a div.
Sven Verdoolaege [Fri, 22 May 2009 19:25:49 +0000 (21:25 +0200)]
isl_basic_map_drop: properly handle dimensions of type isl_dim_div
Sven Verdoolaege [Mon, 25 May 2009 14:40:27 +0000 (16:40 +0200)]
add isl_int_mul_ui
Sven Verdoolaege [Mon, 25 May 2009 15:06:22 +0000 (17:06 +0200)]
add isl_seq_fdiv_q
Sven Verdoolaege [Fri, 22 May 2009 10:33:20 +0000 (12:33 +0200)]
add isl_seq_fdiv_r
Sven Verdoolaege [Tue, 2 Jun 2009 17:41:40 +0000 (19:41 +0200)]
isl_basic_map_detect_equalities: properly handle empty basic sets
If we find out during the computation of the equalities in
the basic map that it was empty, then there is no point in
trying to add any equalities we may have found.
Sven Verdoolaege [Tue, 2 Jun 2009 17:32:23 +0000 (19:32 +0200)]
isl_basic_map_is_empty: explicitly mark basic sets determined to be empty
Sven Verdoolaege [Sat, 6 Jun 2009 09:12:57 +0000 (11:12 +0200)]
isl_map.c: order_divs: swap with correct div
The bug in the original code could result in a div being swapped
with itself, in turn resulting in an infinite loop.
Sven Verdoolaege [Sun, 7 Jun 2009 08:42:28 +0000 (10:42 +0200)]
isl_map_coalesce: remove extra divs introduced by isl_map_align_divs
Sven Verdoolaege [Mon, 25 May 2009 12:01:02 +0000 (14:01 +0200)]
add isl_map_coalesce
Sven Verdoolaege [Tue, 19 May 2009 10:38:47 +0000 (12:38 +0200)]
add isl_set_product
Sven Verdoolaege [Tue, 19 May 2009 08:59:14 +0000 (10:59 +0200)]
export isl_map_dim
Sven Verdoolaege [Mon, 13 Apr 2009 21:11:19 +0000 (23:11 +0200)]
isl_map_convex_hull: handle unbounded, but pointed, case using wrapping
The case where the convex hull may be unbounded (but still pointed)
cannot be handled directly using wrapping. However, by changing
the homogeneous direction, we can in such cases always transform
the input polyhedra to polytopes, compute the hull and then transform back.
Since we already handle the case where the convex hull may not be
pointed, we can now handle all cases using wrapping.
The convex_hull_pair_elim function is therefore no longer used.
We leave it in, because we may want to allow the user to choose
in future which convex hull algorithm to use.
Sven Verdoolaege [Wed, 15 Apr 2009 18:43:08 +0000 (20:43 +0200)]
privately export isl_mat_unimodular_complete
Sven Verdoolaege [Mon, 13 Apr 2009 19:19:41 +0000 (21:19 +0200)]
isl_tab.c: add isl_tab_get_sample_value
Sven Verdoolaege [Mon, 13 Apr 2009 15:51:08 +0000 (17:51 +0200)]
isl_map_convex_hull: avoid introducing lineality spaces in convex hull of pairs
Sven Verdoolaege [Mon, 13 Apr 2009 13:59:33 +0000 (15:59 +0200)]
add two more convex hull test cases
Sven Verdoolaege [Wed, 25 Mar 2009 18:30:41 +0000 (19:30 +0100)]
isl_map_convex_hull: remove lineality space if any before computing convex hull
Sven Verdoolaege [Tue, 24 Mar 2009 19:34:46 +0000 (20:34 +0100)]
add isl_basic_set_is_universe
Sven Verdoolaege [Tue, 24 Mar 2009 19:34:16 +0000 (20:34 +0100)]
add isl_set_get_dim
Sven Verdoolaege [Fri, 17 Apr 2009 15:00:44 +0000 (17:00 +0200)]
isl_convex_hull.c: update wrap_facet to the fact we only apply it on polytopes
Sven Verdoolaege [Fri, 17 Apr 2009 14:41:16 +0000 (16:41 +0200)]
isl_convex_hull.c: fix typo in comment
Sven Verdoolaege [Thu, 16 Apr 2009 15:16:12 +0000 (17:16 +0200)]
isl_coalesce.c: fix typo in comment
Sven Verdoolaege [Thu, 16 Apr 2009 08:24:44 +0000 (10:24 +0200)]
isl_tab.c: fix typo in comment
Sven Verdoolaege [Sun, 3 May 2009 21:26:16 +0000 (22:26 +0100)]
configure.in: set AC_CONFIG_MACRO_DIR
Sven Verdoolaege [Sun, 22 Mar 2009 21:00:14 +0000 (22:00 +0100)]
add isl_basic_set_get_dim
Sven Verdoolaege [Sun, 22 Mar 2009 17:36:52 +0000 (18:36 +0100)]
isl_basic_map_gist: normalize divs (if any) in context
Sven Verdoolaege [Sun, 22 Mar 2009 17:21:09 +0000 (18:21 +0100)]
isl_basic_map_simplify: remove duplicate divs before dropping divs
The equalities on the duplicate but separate divs may
entail additional equalities among the variables that we do
not want to ignore.
Sven Verdoolaege [Sun, 22 Mar 2009 17:20:26 +0000 (18:20 +0100)]
add isl_basic_set_div
Sven Verdoolaege [Sun, 22 Mar 2009 17:19:32 +0000 (18:19 +0100)]
change calling convention of isl_basic_map_div
Sven Verdoolaege [Sat, 21 Mar 2009 13:26:33 +0000 (14:26 +0100)]
isl_map_simplify.c: uset_gist: break early if there are no inequalities
Sven Verdoolaege [Sat, 21 Mar 2009 11:47:42 +0000 (12:47 +0100)]
isl_map_simplify.c: uset_gist: break early if intersection is empty
Sven Verdoolaege [Sat, 21 Mar 2009 11:43:58 +0000 (12:43 +0100)]
add isl_basic_set_fast_is_empty
Sven Verdoolaege [Sun, 22 Mar 2009 20:11:22 +0000 (21:11 +0100)]
update piplib to 1.4.0
Sven Verdoolaege [Mon, 23 Mar 2009 08:21:22 +0000 (09:21 +0100)]
isl_tab.c: store number of equalities among the constraints in tableau
Before, we would check the bmap to figure out how many equalities we
had added, but there was at least one instance where we didn't actually
store the equalities in the tableau, leading to problems if any additional
equalities would be found in the tableau.
Sven Verdoolaege [Mon, 23 Mar 2009 08:21:10 +0000 (09:21 +0100)]
isl_mat_extend: properly extend matrices with reordered rows
Sven Verdoolaege [Thu, 19 Mar 2009 09:46:05 +0000 (10:46 +0100)]
isl_map_gist: handle some special cases