Sven Verdoolaege [Sat, 13 Feb 2010 22:10:07 +0000 (23:10 +0100)]
isl_map_transitive_closure: construct general paths
Sven Verdoolaege [Sat, 13 Feb 2010 14:20:46 +0000 (15:20 +0100)]
isl_map_transitive_closure: prepare for the construction of general paths
In particular, integrate the collection of constant steps in construct_path.
Sven Verdoolaege [Sat, 13 Feb 2010 13:36:23 +0000 (14:36 +0100)]
isl_map_transitive_closure: construct paths that can be composed
In particular, keep track of the number of steps in an extra
coordinates such that composition simply sums the number of steps.
Sven Verdoolaege [Sat, 13 Feb 2010 13:51:44 +0000 (14:51 +0100)]
isl_transitive_closure: extract out construction of path from map_power
We want to generalize the construction to general mappings in a later
commit.
Sven Verdoolaege [Sat, 13 Feb 2010 13:02:00 +0000 (14:02 +0100)]
isl_map_transitive_closure: use more generic acyclicity test
Sven Verdoolaege [Mon, 15 Feb 2010 09:14:08 +0000 (10:14 +0100)]
isl_map_print: add parentheses around disjuncts
Sven Verdoolaege [Mon, 15 Feb 2010 09:00:39 +0000 (10:00 +0100)]
isl_hash_table: use size that corresponds to the number of bits
Sven Verdoolaege [Mon, 15 Feb 2010 08:46:01 +0000 (09:46 +0100)]
isl_hash_table: grow table when we run out of entries
Sven Verdoolaege [Mon, 15 Feb 2010 08:25:18 +0000 (09:25 +0100)]
isl_map_coalesce: only use non-redundant constraints as potential facets
Sven Verdoolaege [Sat, 13 Feb 2010 10:05:40 +0000 (11:05 +0100)]
add isl_set_fix_si
Sven Verdoolaege [Sat, 13 Feb 2010 09:39:01 +0000 (10:39 +0100)]
isl_map_read: accept chains of comparisons
Sven Verdoolaege [Wed, 10 Feb 2010 10:25:25 +0000 (11:25 +0100)]
export isl_map_align_divs
Sven Verdoolaege [Wed, 10 Feb 2010 10:14:17 +0000 (11:14 +0100)]
isl_map_read: forget existentially quantified variables after each disjunct
Sven Verdoolaege [Wed, 10 Feb 2010 10:08:06 +0000 (11:08 +0100)]
isl_input.c: remove needless indirection
Sven Verdoolaege [Tue, 9 Feb 2010 15:46:55 +0000 (16:46 +0100)]
doc: document how to inspect sets and relations
Sven Verdoolaege [Mon, 8 Feb 2010 19:17:39 +0000 (20:17 +0100)]
export isl_map_compute_divs
Sven Verdoolaege [Tue, 9 Feb 2010 10:48:38 +0000 (11:48 +0100)]
isl_constraint_div: make sure requested div is a known div
Sven Verdoolaege [Tue, 9 Feb 2010 10:39:55 +0000 (11:39 +0100)]
doc: drop documentation of _dump functions
We have proper output functions now, so these should no longer be used.
Sven Verdoolaege [Tue, 9 Feb 2010 10:26:08 +0000 (11:26 +0100)]
isl_map_print: improve output
Sven Verdoolaege [Tue, 9 Feb 2010 14:29:12 +0000 (15:29 +0100)]
add isl_basic_map_foreach_constraint
Sven Verdoolaege [Mon, 8 Feb 2010 18:24:16 +0000 (19:24 +0100)]
isl_map_coalesce: handle more cases
In particular, if one basic map has a single constraint that cuts
off all or part of the other basic map such that the part that is cut
off lies entirely on a hyperplane adjacent to the constraint,
then try to combine the two basic maps by adding some wrapping constraints.
Sven Verdoolaege [Fri, 5 Feb 2010 16:11:11 +0000 (17:11 +0100)]
privately export isl_set_wrap_facet
Sven Verdoolaege [Fri, 5 Feb 2010 13:29:44 +0000 (14:29 +0100)]
isl_convex_hull.c: wrap_facet: allow unbounded facets again.
This reverts commit 7c08353 (isl_convex_hull.c: update wrap_facet to
the fact we only apply it on polytopes).
We want to export wrap_facet and allow it to be called on unbounded
polyhedra.
Sven Verdoolaege [Mon, 8 Feb 2010 15:05:56 +0000 (16:05 +0100)]
doc: improve decription of isl_map_transitive_closure
Sven Verdoolaege [Mon, 8 Feb 2010 15:04:28 +0000 (16:04 +0100)]
isl_map_transitive_closure: improve test for exactness
Sven Verdoolaege [Fri, 5 Feb 2010 09:04:51 +0000 (10:04 +0100)]
add a counter example for Theorem 1 of the COCOA paper
Sven Verdoolaege [Mon, 8 Feb 2010 14:12:17 +0000 (15:12 +0100)]
add isl_map_lower_bound_si
Sven Verdoolaege [Mon, 8 Feb 2010 11:08:06 +0000 (12:08 +0100)]
isl_map_power: coalesce domain and range
Sven Verdoolaege [Mon, 8 Feb 2010 08:36:02 +0000 (09:36 +0100)]
isl_flow.c: add missing isl_access_info_free return type
Sven Verdoolaege [Fri, 5 Feb 2010 09:40:19 +0000 (10:40 +0100)]
isl_coalesce.c: fix typo in comment
Sven Verdoolaege [Sun, 7 Feb 2010 11:05:21 +0000 (12:05 +0100)]
include/isl_int.h: argument of mp_get_memory_functions should have C linkage
Sven Verdoolaege [Thu, 4 Feb 2010 21:51:15 +0000 (22:51 +0100)]
isl_map_read: accept lists of affine expressions in constraints
Sven Verdoolaege [Thu, 4 Feb 2010 21:48:48 +0000 (22:48 +0100)]
add isl_mat_from_row_vec and isl_mat_vec_concat
Sven Verdoolaege [Thu, 4 Feb 2010 17:26:23 +0000 (18:26 +0100)]
isl_map_read: read extended polylib format
Sven Verdoolaege [Thu, 4 Feb 2010 17:24:43 +0000 (18:24 +0100)]
add isl_stream_next_token_on_same_line
Sven Verdoolaege [Thu, 4 Feb 2010 16:51:11 +0000 (17:51 +0100)]
isl_map_read: make sure polylib constraint coefficients are on a single line
Sven Verdoolaege [Thu, 4 Feb 2010 16:50:36 +0000 (17:50 +0100)]
isl_{map,set}_dim: handle NULL input
Sven Verdoolaege [Thu, 4 Feb 2010 16:46:04 +0000 (17:46 +0100)]
isl_map_read: use more uniform way of reading in polylib constraint coefficients
Sven Verdoolaege [Thu, 4 Feb 2010 13:08:51 +0000 (14:08 +0100)]
isl_transitive_closure.c: fix typo in comment
Sven Verdoolaege [Thu, 4 Feb 2010 12:58:40 +0000 (13:58 +0100)]
isl_map_transitive_closure: use more relaxed exactness check on acyclic graphs
In particular, for the transitive closure, we only need to check that
there is a path of _some_ length with a valid initial segment.
However, we can only do this if the corresponding graph is acyclic.
For now, we restrict ourselves to graphs that are obviously acyclic.
Sven Verdoolaege [Wed, 3 Feb 2010 17:29:52 +0000 (18:29 +0100)]
add isl_map_power and isl_map_transitive_closure
Sven Verdoolaege [Wed, 3 Feb 2010 17:13:49 +0000 (18:13 +0100)]
isl_map_subtract.c: make some internal functions static
Sven Verdoolaege [Wed, 3 Feb 2010 15:53:39 +0000 (16:53 +0100)]
add generic isl_map_project_out
Sven Verdoolaege [Tue, 2 Feb 2010 14:21:58 +0000 (15:21 +0100)]
add isl_{map,set}_add
Sven Verdoolaege [Tue, 2 Feb 2010 13:39:25 +0000 (14:39 +0100)]
rename isl_{map,set}_add to isl_{map,set}_add_basic_{map,set}
Sven Verdoolaege [Tue, 2 Feb 2010 13:23:02 +0000 (14:23 +0100)]
isl_set_project_out: always update dimension, even for empty sets
Sven Verdoolaege [Tue, 2 Feb 2010 11:16:08 +0000 (12:16 +0100)]
isl_dim_join: don't require names of joined variables to match
Sven Verdoolaege [Mon, 1 Feb 2010 16:03:54 +0000 (17:03 +0100)]
add isl_map_from_domain_and_range
Sven Verdoolaege [Mon, 1 Feb 2010 13:04:17 +0000 (14:04 +0100)]
isl_stream: treat "-" as operator rather than as -1
Sven Verdoolaege [Mon, 1 Feb 2010 12:37:32 +0000 (13:37 +0100)]
isl_map_read: accept "strict" inequalities
Sven Verdoolaege [Mon, 1 Feb 2010 12:36:46 +0000 (13:36 +0100)]
isl_input.c: fix memory deallocation problem on missing operator
Sven Verdoolaege [Sun, 31 Jan 2010 20:15:48 +0000 (21:15 +0100)]
add dependence analysis
Sven Verdoolaege [Sun, 31 Jan 2010 21:01:41 +0000 (22:01 +0100)]
add isl_map_{partial_,}lexopt
Sven Verdoolaege [Thu, 14 Jan 2010 20:30:26 +0000 (21:30 +0100)]
add private isl_{set,map}_make_disjoint
Sven Verdoolaege [Sun, 31 Jan 2010 17:47:53 +0000 (18:47 +0100)]
basis_reduction_templ.c: fix typo in comment
Sven Verdoolaege [Sun, 31 Jan 2010 17:29:12 +0000 (18:29 +0100)]
isl_tab_pip.c: find_solutions: break when context becomes empty
Normally, find_solutions: always operates on a non-empty context.
However, when we discover a pure-parametric cut in the main
tableau, the result of adding this cut to the context may be
an empty context. In this case, we need to break out off the
main loop, because most code assumes the context is non-empty.
Sven Verdoolaege [Tue, 26 Jan 2010 14:40:02 +0000 (15:40 +0100)]
isl_dim_equal: don't require names of input and output variables to match
Sven Verdoolaege [Tue, 26 Jan 2010 19:50:12 +0000 (20:50 +0100)]
isl_dim_map: properly duplicate names
Sven Verdoolaege [Tue, 26 Jan 2010 19:49:11 +0000 (20:49 +0100)]
isl_dim_drop: properly adjust length of names array
Sven Verdoolaege [Tue, 26 Jan 2010 12:17:49 +0000 (13:17 +0100)]
doc: a bit more on integers
Sven Verdoolaege [Mon, 25 Jan 2010 21:09:20 +0000 (22:09 +0100)]
doc: describe input/output formats
Sven Verdoolaege [Mon, 25 Jan 2010 21:10:31 +0000 (22:10 +0100)]
doc: fix typo
Sven Verdoolaege [Sun, 24 Jan 2010 21:08:27 +0000 (22:08 +0100)]
add isl_cat test application
Sven Verdoolaege [Mon, 25 Jan 2010 16:57:33 +0000 (17:57 +0100)]
add omega output
Sven Verdoolaege [Mon, 25 Jan 2010 17:02:07 +0000 (18:02 +0100)]
add isl output
Sven Verdoolaege [Sun, 24 Jan 2010 13:23:06 +0000 (14:23 +0100)]
isl_test: use isl_set_read_from_str
Sven Verdoolaege [Sun, 24 Jan 2010 13:22:49 +0000 (14:22 +0100)]
add isl_set_read_from_str
Sven Verdoolaege [Sat, 23 Jan 2010 21:52:02 +0000 (22:52 +0100)]
add isl_map_read_from_str
Sven Verdoolaege [Fri, 22 Jan 2010 12:54:47 +0000 (13:54 +0100)]
isl_map_read_from_file: allow unions in isl format input
Sven Verdoolaege [Fri, 22 Jan 2010 11:48:23 +0000 (12:48 +0100)]
isl_basic_map_read: read definitions of existential variables
Sven Verdoolaege [Fri, 22 Jan 2010 11:45:05 +0000 (12:45 +0100)]
privately export isl_basic_map_add_div_constraints
Sven Verdoolaege [Fri, 22 Jan 2010 10:30:48 +0000 (11:30 +0100)]
isl_basic_map_read: read affine constraint as two affine expressions + operator
Sven Verdoolaege [Sun, 24 Jan 2010 21:30:12 +0000 (22:30 +0100)]
isl_input.c: optionally read parameters from input
Sven Verdoolaege [Thu, 21 Jan 2010 20:21:28 +0000 (21:21 +0100)]
tokenizer: accept "and" keyword
Sven Verdoolaege [Sun, 24 Jan 2010 23:32:03 +0000 (00:32 +0100)]
export isl_map_read_from_file
Sven Verdoolaege [Sat, 16 Jan 2010 15:16:14 +0000 (16:16 +0100)]
export isl_basic_map_read_from_str
Sven Verdoolaege [Sun, 24 Jan 2010 20:55:05 +0000 (21:55 +0100)]
drop redundant input_format argument from reading functions
Sven Verdoolaege [Sun, 24 Jan 2010 18:24:14 +0000 (19:24 +0100)]
isl_input.c: merge functions for reading PolyLib and omega-like input
Sven Verdoolaege [Sun, 24 Jan 2010 18:08:06 +0000 (19:08 +0100)]
isl_input_omega.c: accept PolyLib input
Sven Verdoolaege [Sun, 24 Jan 2010 17:58:24 +0000 (18:58 +0100)]
isl_input_omega.c: prepare for reading parametric unions
Sven Verdoolaege [Fri, 22 Jan 2010 12:58:23 +0000 (13:58 +0100)]
isl_input_omega.c: finalize and simplify resulting basic map
Sven Verdoolaege [Fri, 22 Jan 2010 10:41:19 +0000 (11:41 +0100)]
isl_input_omega.c: fix check for memory allocation error
Sven Verdoolaege [Sun, 24 Jan 2010 13:36:02 +0000 (14:36 +0100)]
isl_stream_next_token: skip comment lines
Sven Verdoolaege [Thu, 21 Jan 2010 09:54:51 +0000 (10:54 +0100)]
isl_tab_basic_map_partial_lexopt: properly handle empty input map
In particular, when no empty set is requested (i.e., empty == NULL),
then we shouldn't try to add the context to the empty set.
Sven Verdoolaege [Wed, 20 Jan 2010 16:50:28 +0000 (17:50 +0100)]
isl_basic_map_set_to_empty: remove sample (if any)
Sven Verdoolaege [Sun, 17 Jan 2010 19:50:31 +0000 (20:50 +0100)]
add isl_set_fast_is_empty
Sven Verdoolaege [Wed, 13 Jan 2010 08:59:16 +0000 (09:59 +0100)]
properly remove piplib submodule
309036c (add copyright statements) accidentally removed the piplib submodule.
Removing the piplib submodule was not a bad idea since we don't really need it
anymore, but it should be done properly.
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_map_update_from_tab: re-gauss resulting bmap
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Fri, 1 Jan 2010 17:02:30 +0000 (18:02 +0100)]
ax_submodule.m4: don't let --with-module conflict with --with-module-prefix=
Sven Verdoolaege [Sat, 12 Dec 2009 22:43:31 +0000 (23:43 +0100)]
add isl_set_follows_at
Sven Verdoolaege [Thu, 24 Dec 2009 18:02:26 +0000 (19:02 +0100)]
isl_basic_set_compare_at: compute result in terms of maximal (integral) difference
Computing the maximal instead of the minimal difference will allow
us to reuse much of the code in isl_basic_set_follows_at later.
Since we only need the sign of the optimum, we don't really need
the exact value.
Sven Verdoolaege [Thu, 24 Dec 2009 16:59:59 +0000 (17:59 +0100)]
isl_tab_pip.c: add cuts for all non-integer coordinates in lexmin context
The lexmin context applies basically the same algorithm that is
used in the main tableau to the context tableau.
In particular, each cut that is added is immediately used to move
to a lexico-greater point.
It was reported by François Galea, who was working on the implementation
of parametric integer programming in PPL, that first adding cuts
for all non-integer coordinates results in a significant speed
improvement on at least one example.
This patch implements the same idea and results in a similar improvement
on the same example.
Sven Verdoolaege [Sat, 19 Dec 2009 10:20:34 +0000 (11:20 +0100)]
isl_basic_map_gist: don't drop equalities from context
The context isn't cowed, so this dropping of equalities would
be visible to the caller. Instead, drop the equalities after
duplicating the context.
Sven Verdoolaege [Fri, 18 Dec 2009 22:41:29 +0000 (23:41 +0100)]
isl_convex_hull.c: initial_facet_constraint: drop all redundant bounds on face
While constructing an initial facet, we may end up with an intermediate
face that makes some of the as yet unconsidered bounds redundant.
Remove all of them, instead of only those that happen to vanish.
Sven Verdoolaege [Fri, 18 Dec 2009 20:26:31 +0000 (21:26 +0100)]
isl_convex_hull.c: is_independent_bound: normalize bounds
Sven Verdoolaege [Fri, 18 Dec 2009 19:53:46 +0000 (20:53 +0100)]
isl_convex_hull.c: extend: check hull argument
Sven Verdoolaege [Fri, 18 Dec 2009 19:52:33 +0000 (20:52 +0100)]
isl_mat_right_inverse: be more verbose on error condition
Sven Verdoolaege [Fri, 18 Dec 2009 17:26:58 +0000 (18:26 +0100)]
isl_constraint_dup: make sure line refers to equation in constraint's bmap
Sven Verdoolaege [Wed, 16 Dec 2009 19:25:40 +0000 (19:25 +0000)]
add copyright statements
Sven Verdoolaege [Wed, 16 Dec 2009 14:17:19 +0000 (14:17 +0000)]
remove functions for converting between isl and PolyLib
These functions could be seen as being derived work from PolyLib
and would therefore infect the whole library with the GPLv2 license.
They will be moved into a separate isl-polylib library.