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
Sven Verdoolaege [Thu, 19 Mar 2009 09:22:38 +0000 (10:22 +0100)]
add isl_map_universe
Sven Verdoolaege [Thu, 19 Mar 2009 08:50:34 +0000 (09:50 +0100)]
add isl_basic_map_fast_is_empty
Sven Verdoolaege [Wed, 18 Mar 2009 17:30:39 +0000 (18:30 +0100)]
isl_basic_map_gist: replace by new version based on tableaus
The new version should be a little bit more efficient because
it only constructs a single tableau.
More importantly, the new version keeps better track of the original
constraints and never introduces an inequality constraint in the result
that did not appear in the input.
This is especially important in the presence of divs.
Throught variable compression, the original version would sometimes
translate constraints that did not involve any divs into constraints
that did involve divs.
Sven Verdoolaege [Wed, 18 Mar 2009 16:43:38 +0000 (17:43 +0100)]
isl_map_simplify.c: compute_elimination_index: don't assume equalities are in order
Sven Verdoolaege [Wed, 18 Mar 2009 16:35:41 +0000 (17:35 +0100)]
add isl_map_implicit_equalities
Sven Verdoolaege [Wed, 18 Mar 2009 12:09:24 +0000 (13:09 +0100)]
add isl_basic_set_free_equality
Sven Verdoolaege [Tue, 10 Mar 2009 12:46:08 +0000 (13:46 +0100)]
isl_map_convex_hull: mark result as not having any implicit equalities
Sven Verdoolaege [Tue, 17 Mar 2009 13:46:50 +0000 (14:46 +0100)]
convex_hull: coalesce set first
Sven Verdoolaege [Mon, 16 Mar 2009 10:58:57 +0000 (11:58 +0100)]
add isl_set_coalesce
Sven Verdoolaege [Fri, 20 Mar 2009 15:21:58 +0000 (16:21 +0100)]
isl_input_omega.c: basic_map_read: accept "+" in constraints
Sven Verdoolaege [Mon, 16 Mar 2009 10:55:08 +0000 (11:55 +0100)]
add isl_basic_set_alloc_div
Sven Verdoolaege [Sun, 15 Mar 2009 21:21:40 +0000 (22:21 +0100)]
add isl_set_align_divs
Sven Verdoolaege [Sat, 14 Mar 2009 12:03:52 +0000 (13:03 +0100)]
uset_affine_hull: ignore directions in affine hull of recession cone
Sven Verdoolaege [Wed, 18 Mar 2009 16:34:58 +0000 (17:34 +0100)]
isl_basic_map_implicit_equalities: perform Gaussian elimination on result
Sven Verdoolaege [Fri, 13 Mar 2009 23:41:10 +0000 (00:41 +0100)]
isl_affine_hull.c: outside_point: check for obvious candidate first
Sven Verdoolaege [Fri, 13 Mar 2009 23:40:21 +0000 (00:40 +0100)]
privately export isl_basic_set_contains
Sven Verdoolaege [Fri, 13 Mar 2009 23:39:50 +0000 (00:39 +0100)]
isl_ctx: add negone
Sven Verdoolaege [Fri, 13 Mar 2009 20:19:36 +0000 (21:19 +0100)]
isl_vec_dump: handle NULL vec
Sven Verdoolaege [Wed, 18 Mar 2009 18:56:55 +0000 (19:56 +0100)]
isl_affine_hull.c: extract uset_affine_hull
Sven Verdoolaege [Thu, 12 Mar 2009 13:44:21 +0000 (14:44 +0100)]
isl_mat_transpose: handle non-rectangular matrices
Sven Verdoolaege [Wed, 11 Mar 2009 11:42:27 +0000 (12:42 +0100)]
isl_map_simple_hull: compute affine hull before aligning divs
Computing the affine hull may change the internal representation.
In particular, it may simplify div constraints that are added
during the alignment to constraints that did not appear in the
original set and we do not want to introduce such constraints
in the simple hull.
Sven Verdoolaege [Wed, 11 Mar 2009 09:43:38 +0000 (10:43 +0100)]
isl_map_simple_hull: mark result as not having any implicit equalities
Sven Verdoolaege [Wed, 11 Mar 2009 08:10:07 +0000 (09:10 +0100)]
add isl_set_bounded_simple_hull
Sven Verdoolaege [Tue, 10 Mar 2009 12:45:31 +0000 (13:45 +0100)]
isl_map_affine_hull: detect equalities of integer affine hull before cowing
Sven Verdoolaege [Tue, 10 Mar 2009 12:29:41 +0000 (13:29 +0100)]
isl_basic_map_dup: copy flags of original to duplicate
Before, the copied flags would get removed by the subsequent dup_constraints.
Some other code depended on isl_basic_map_cow clearing all flags and
failed to clear some flags.
Sven Verdoolaege [Tue, 10 Mar 2009 10:06:43 +0000 (11:06 +0100)]
isl_basic_map_extend_dim: move responsibility of cow'ing to the caller
Some callers, notably isl_basic_map_detect_equalities, want to
extend the basic map to add equalities that are implicit to the
basic map. These equalities should be added to all copies,
so we definitely do not want to cow in such cases.
Sven Verdoolaege [Tue, 10 Mar 2009 09:51:09 +0000 (10:51 +0100)]
isl_basic_map_extend_dim: only extend constraint matrix if needed
Sven Verdoolaege [Sun, 8 Mar 2009 14:09:50 +0000 (15:09 +0100)]
isl_solve_lp: use tableaus instead of calling piplib (by default)
Sven Verdoolaege [Sat, 7 Mar 2009 22:24:40 +0000 (23:24 +0100)]
isl_solve_lp: accept affine object function instead of linear function
Sven Verdoolaege [Sat, 7 Mar 2009 13:19:31 +0000 (14:19 +0100)]
isl_map_simple_hull: use hash tables and tableaus
Sven Verdoolaege [Fri, 6 Mar 2009 16:59:33 +0000 (17:59 +0100)]
isl_convex_hull.c: extract out uset_simple_hull
Sven Verdoolaege [Tue, 3 Mar 2009 20:43:36 +0000 (21:43 +0100)]
isl_convex_hull.c: extend: avoid wrapping around already known ridges
Sven Verdoolaege [Tue, 3 Mar 2009 18:04:39 +0000 (19:04 +0100)]
isl_convex_hull.c: introduce proto_hull based on obvious facet constraints
proto_hull looks for for obvious facet constraints.
If any such constraints can be found, then the calling function
no longer needs to call initial_hull.
Sven Verdoolaege [Tue, 3 Mar 2009 14:02:53 +0000 (15:02 +0100)]
isl_convex_hull.c: move initial hull construction into separate function
Sven Verdoolaege [Tue, 3 Mar 2009 13:30:32 +0000 (14:30 +0100)]
isl_convex_hull.c: move computation of bounds into uset_convex_hull_wrap
Sven Verdoolaege [Tue, 3 Mar 2009 13:29:10 +0000 (14:29 +0100)]
isl_map_convex_hull: check for boundedness using recession cone
Sven Verdoolaege [Fri, 27 Feb 2009 21:20:21 +0000 (22:20 +0100)]
isl_basic_map_convex_hull: use tableau to detect redundant constraints
Sven Verdoolaege [Wed, 4 Mar 2009 17:12:30 +0000 (18:12 +0100)]
isl_affine_hull.c: use tableau to detect implicit equalities
Sven Verdoolaege [Sun, 15 Mar 2009 09:49:48 +0000 (10:49 +0100)]
isl_tab.c: don't detect equalities while setting up tableau
The original description of the algorithm tries to detect equalities
as soon as possible. In our application it may be best to wait
until all constraints are available. In some case we are not
even interested in the equalities.
Sven Verdoolaege [Wed, 4 Mar 2009 17:12:30 +0000 (18:12 +0100)]
add internal representation of LP tableaus
Sven Verdoolaege [Wed, 11 Mar 2009 16:23:09 +0000 (17:23 +0100)]
add isl_mat_extend
Sven Verdoolaege [Mon, 9 Mar 2009 10:44:05 +0000 (11:44 +0100)]
add isl_set_dim
Sven Verdoolaege [Tue, 3 Mar 2009 20:28:00 +0000 (21:28 +0100)]
privately export isl_basic_{set,map}_normalize_constraints
Sven Verdoolaege [Tue, 3 Mar 2009 14:01:51 +0000 (15:01 +0100)]
add isl_basic_set_extend_dim
Sven Verdoolaege [Sun, 1 Mar 2009 22:16:04 +0000 (23:16 +0100)]
isl_basic_map_eliminate_vars: clear divs first
Sven Verdoolaege [Sat, 28 Feb 2009 14:16:44 +0000 (15:16 +0100)]
isl_basic_map_eliminate_vars: remove all dependent vars first
Sven Verdoolaege [Fri, 6 Mar 2009 17:26:34 +0000 (18:26 +0100)]
add isl_hash_table_alloc and isl_hash_table_free
Sven Verdoolaege [Tue, 3 Mar 2009 14:54:03 +0000 (15:54 +0100)]
isl_hash_table_init: take minimal size instead of number of bits needed
Sven Verdoolaege [Tue, 3 Mar 2009 21:08:14 +0000 (22:08 +0100)]
isl_{basic_,}set_preimage: drop ctx argument
Sven Verdoolaege [Fri, 27 Feb 2009 10:18:01 +0000 (11:18 +0100)]
isl_basic_map_intersect: reuse sample value of either basic map if possible
If the sample value stored in one of the two basic maps is an element
of both basic maps, then we can keep it as sample value for the intersection.
Sven Verdoolaege [Thu, 26 Feb 2009 18:25:42 +0000 (19:25 +0100)]
add isl_int_ge
Sven Verdoolaege [Tue, 10 Mar 2009 18:23:24 +0000 (19:23 +0100)]
isl_basic_set_has_defining_inequalities: fix typo
Sven Verdoolaege [Mon, 9 Mar 2009 12:22:45 +0000 (13:22 +0100)]
isl_constraint_div: perform required reference increase on basic map
Both divs and constraints own their contained basic maps, so we
can't just steal the basic map from the constraint.
Sven Verdoolaege [Thu, 26 Feb 2009 15:38:45 +0000 (16:38 +0100)]
isl_basic_map: put inequalities before equalities
When confronted with a list of inequalities that need to be
turned into equalities, we want to handle the inequalities
in the same order in which we handle inequalities that can
be removed. Eventually, we would want to do these at the
same time.
Sven Verdoolaege [Thu, 26 Feb 2009 11:35:55 +0000 (12:35 +0100)]
add isl_seq_normalize
Sven Verdoolaege [Thu, 26 Feb 2009 11:14:21 +0000 (12:14 +0100)]
isl_ctx.h: make FL_ISSET return a boolean value
Sven Verdoolaege [Wed, 4 Mar 2009 10:44:51 +0000 (11:44 +0100)]
rename F_ and FL_ macros to ISL_F_ and ISL_FL_ to avoid name clashes
Sven Verdoolaege [Thu, 26 Feb 2009 10:59:03 +0000 (11:59 +0100)]
add isl_mat_swap_cols
Sven Verdoolaege [Wed, 25 Feb 2009 20:01:24 +0000 (21:01 +0100)]
isl_mat_dump: also indent NULL mat
Sven Verdoolaege [Wed, 25 Feb 2009 20:00:47 +0000 (21:00 +0100)]
add isl_calloc_type
Sven Verdoolaege [Mon, 2 Mar 2009 22:20:19 +0000 (23:20 +0100)]
isl_map_convex_hull: normalize map first
Sven Verdoolaege [Tue, 3 Mar 2009 09:49:52 +0000 (10:49 +0100)]
isl_set_preimage: clear ISL_SET_NORMALIZED flag
Sven Verdoolaege [Sun, 22 Feb 2009 15:58:56 +0000 (16:58 +0100)]
add isl_basic_map_detect_equalities