Sven Verdoolaege [Sun, 6 Sep 2009 11:36:21 +0000 (13:36 +0200)]
isl_convex_hull.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:34:20 +0000 (13:34 +0200)]
isl_constraint.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:30:12 +0000 (13:30 +0200)]
isl_tab.c: sign_of_min: only pivot back if we performed any pivot
Sven Verdoolaege [Sun, 6 Sep 2009 11:23:29 +0000 (13:23 +0200)]
isl_tab.c: isl_tab_mark_redundant: fix up error return
Sven Verdoolaege [Sun, 6 Sep 2009 11:22:11 +0000 (13:22 +0200)]
isl_tab.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:20:49 +0000 (13:20 +0200)]
isl_tab_pip.c: remove unused variables
Sven Verdoolaege [Sun, 6 Sep 2009 11:19:05 +0000 (13:19 +0200)]
isl_vec.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:18:31 +0000 (13:18 +0200)]
isl_test.c: remove unused variable
Sven Verdoolaege [Sun, 6 Sep 2009 11:17:35 +0000 (13:17 +0200)]
isl_assert: validate all arguments and fix up fallout
Sven Verdoolaege [Sun, 6 Sep 2009 11:03:24 +0000 (13:03 +0200)]
polyhedron_sample.c: add missing include
Sven Verdoolaege [Sun, 6 Sep 2009 11:01:40 +0000 (13:01 +0200)]
isl_pip.c: check return value of fscanf
Sven Verdoolaege [Sun, 6 Sep 2009 10:59:59 +0000 (12:59 +0200)]
polyhedron_minimize.c: handle all enumeration values in switch
Sven Verdoolaege [Sun, 6 Sep 2009 10:57:03 +0000 (12:57 +0200)]
configure.ac: set maximal optimization compiler flags
Sven Verdoolaege [Sat, 5 Sep 2009 22:16:09 +0000 (00:16 +0200)]
isl_set_copy_basic_set: add missing return
Sven Verdoolaege [Sat, 5 Sep 2009 22:09:54 +0000 (00:09 +0200)]
isl_set_drop_basic_set: add missing return
Sven Verdoolaege [Sat, 5 Sep 2009 21:56:57 +0000 (23:56 +0200)]
isl_set_coalesce: add missing return
Sven Verdoolaege [Sat, 5 Sep 2009 21:51:22 +0000 (23:51 +0200)]
isl_coalesce.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:34:18 +0000 (23:34 +0200)]
isl_test: check srcdir has been set
Sven Verdoolaege [Sat, 5 Sep 2009 21:28:59 +0000 (23:28 +0200)]
privately export isl_tab_kill_col
Sven Verdoolaege [Sat, 5 Sep 2009 21:27:34 +0000 (23:27 +0200)]
isl_tab.c: fix up to_col
Sven Verdoolaege [Sat, 5 Sep 2009 21:25:58 +0000 (23:25 +0200)]
isl_tab_pip.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:25:31 +0000 (23:25 +0200)]
isl_vec.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:24:30 +0000 (23:24 +0200)]
export isl_seq_cmp
Sven Verdoolaege [Sat, 5 Sep 2009 21:23:23 +0000 (23:23 +0200)]
fix return type of isl_constraint_free
Sven Verdoolaege [Sat, 5 Sep 2009 21:22:20 +0000 (23:22 +0200)]
export isl_token_free and isl_stream_error
Sven Verdoolaege [Sat, 5 Sep 2009 21:20:32 +0000 (23:20 +0200)]
isl_list.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:19:29 +0000 (23:19 +0200)]
isl_div.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:18:55 +0000 (23:18 +0200)]
isl_constraint.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:18:20 +0000 (23:18 +0200)]
basis_reduction_tab.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:17:46 +0000 (23:17 +0200)]
isl_map_no_piplib.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:17:05 +0000 (23:17 +0200)]
ax_create_stdint_h.m4: protect some limits from redefinition
Sven Verdoolaege [Sat, 5 Sep 2009 21:08:59 +0000 (23:08 +0200)]
polytope_scan.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:06:33 +0000 (23:06 +0200)]
fix return type of isl_div_free
Sven Verdoolaege [Sat, 5 Sep 2009 21:05:44 +0000 (23:05 +0200)]
isl_map_simplify.c: drop return from void function
Sven Verdoolaege [Sat, 5 Sep 2009 21:04:05 +0000 (23:04 +0200)]
isl_map_simplify.c: add missing include
Sven Verdoolaege [Sat, 5 Sep 2009 21:03:19 +0000 (23:03 +0200)]
isl_convex_hull.c: use isl_seq_get_hash instead of isl_seq_hash
Sven Verdoolaege [Sat, 5 Sep 2009 20:58:22 +0000 (22:58 +0200)]
declare flexarrays of size 1 to silence sun compiler
Sven Verdoolaege [Sat, 5 Sep 2009 20:21:10 +0000 (22:21 +0200)]
change isl_basic_map_empty interface for consistency
Sven Verdoolaege [Sat, 5 Sep 2009 13:02:29 +0000 (15:02 +0200)]
AX_SUBMODULE: mention default type of library to use
Sven Verdoolaege [Sat, 5 Sep 2009 12:53:04 +0000 (14:53 +0200)]
configure.ac: use AX_SUBMODULE for gmp for consistency
Sven Verdoolaege [Sat, 5 Sep 2009 12:32:01 +0000 (14:32 +0200)]
separate out config header from isl_ctx.h
Sven Verdoolaege [Fri, 4 Sep 2009 21:39:57 +0000 (23:39 +0200)]
pilp solver: don't ignore feasibility test on context
In the initial implementation, the sample point of the context was
kept integer. This was later changed in such a way that now the
sample point is just lexico-smallest rational value.
This means that after checking for an integer point, we rollback
until the state before we performed this check.
However, the results of the feasibility test were only checked
after the rollback, completely ignoring the actual results of
the feasibility test.
Sven Verdoolaege [Tue, 1 Sep 2009 20:59:21 +0000 (22:59 +0200)]
isl_basic_map_gauss: try not to remove any div definitions
After computing divs, the result may get simplified and during
this simplification, isl_basic_map_gauss may actually remove some
divs because it is trying to play safe wrt circular div definitions.
By keeping the divs ordered, divs can safely be eliminated without
introducing any circular definitions.
Sven Verdoolaege [Sun, 30 Aug 2009 08:01:08 +0000 (10:01 +0200)]
add isl_map_sum
Sven Verdoolaege [Sun, 30 Aug 2009 07:54:40 +0000 (09:54 +0200)]
add isl_map_floordiv
Sven Verdoolaege [Sun, 30 Aug 2009 07:51:39 +0000 (09:51 +0200)]
add isl_map_neg
Sven Verdoolaege [Sun, 30 Aug 2009 07:43:49 +0000 (09:43 +0200)]
add isl_map_is_strict_subset
Sven Verdoolaege [Sun, 30 Aug 2009 07:17:52 +0000 (09:17 +0200)]
add isl_map_fast_is_fixed
Sven Verdoolaege [Sun, 30 Aug 2009 07:11:09 +0000 (09:11 +0200)]
add isl_map_identity_like
Sven Verdoolaege [Sun, 30 Aug 2009 07:05:56 +0000 (09:05 +0200)]
rename isl_map_identity_like to isl_map_identity_like_basic_map
Sven Verdoolaege [Mon, 17 Aug 2009 08:13:56 +0000 (10:13 +0200)]
add isl_polytope_scan application
Sven Verdoolaege [Sat, 15 Aug 2009 14:46:16 +0000 (16:46 +0200)]
isl_seq_normalize: use pre-allocated temporary variable in isl_ctx
This requires that we pass along an isl_ctx, but it removes
the need for allocating a temporary variable every time
isl_seq_normalize is called.
In some cases, up to 20% of the execution time of isl_seq_normalize
was wasted on initializing and clearing this temporary variable.
Sven Verdoolaege [Sat, 15 Aug 2009 14:33:27 +0000 (16:33 +0200)]
add isl_vec_normalize
Sven Verdoolaege [Sat, 15 Aug 2009 14:20:38 +0000 (16:20 +0200)]
isl_seq_normalize: no need to scale down by one
Sven Verdoolaege [Fri, 7 Aug 2009 19:31:45 +0000 (21:31 +0200)]
add isl_polyhedron_minimize application
Sven Verdoolaege [Mon, 10 Aug 2009 19:04:00 +0000 (21:04 +0200)]
add generalized basis reduction based ILP solver
Sven Verdoolaege [Sat, 15 Aug 2009 09:08:13 +0000 (11:08 +0200)]
add isl_vec_mat_product
Sven Verdoolaege [Sun, 9 Aug 2009 16:12:57 +0000 (18:12 +0200)]
export isl_vec_ceil
Sven Verdoolaege [Sun, 9 Aug 2009 09:42:41 +0000 (11:42 +0200)]
isl_basic_set_sample: only perform basis reduction once
On larger problem, much time was spent on repeated basis reductions
with little or no reduction on the number of points visited.
The initial basis reduction seems to be sufficient in most cases.
Sven Verdoolaege [Sun, 9 Aug 2009 16:08:09 +0000 (18:08 +0200)]
rename isl_solve_lp to isl_basic_{map,set}_solve_lp
Sven Verdoolaege [Sat, 8 Aug 2009 10:20:56 +0000 (12:20 +0200)]
isl_solve_lp: optionally return solution point
The caller may now not be interested in the optimal value anymore,
so make returning this optimal value optional.
Sven Verdoolaege [Sun, 9 Aug 2009 15:20:27 +0000 (17:20 +0200)]
export isl_vec header
Sven Verdoolaege [Sat, 8 Aug 2009 10:20:01 +0000 (12:20 +0200)]
add isl_int_fdiv_q_ui
Sven Verdoolaege [Fri, 7 Aug 2009 19:31:27 +0000 (21:31 +0200)]
add isl_vec_read_from_file
Sven Verdoolaege [Fri, 14 Aug 2009 11:38:03 +0000 (13:38 +0200)]
isl_basic_map_drop_redundant_divs: also investigate divs that have a definition
They may have become redundant after having been defined.
Sven Verdoolaege [Fri, 14 Aug 2009 11:37:31 +0000 (13:37 +0200)]
isl_basic_map_apply_{domain,range}: drop redundant divs in result
Sven Verdoolaege [Thu, 13 Aug 2009 18:09:49 +0000 (20:09 +0200)]
isl_map_simplify.c: fix typo in comment
Sven Verdoolaege [Thu, 13 Aug 2009 14:49:43 +0000 (16:49 +0200)]
isl_basic_set_project_out: drop redundant divs in result
Sven Verdoolaege [Fri, 28 Aug 2009 17:40:58 +0000 (19:40 +0200)]
isl_basic_map_remove: only drop divs if basic map did not turn out to be empty
If isl_basic_map_eliminate_vars finds that its argument is empty,
it resets its constraints to the canonical representation of an empty
set and drops all divs.
Sven Verdoolaege [Thu, 13 Aug 2009 14:01:56 +0000 (16:01 +0200)]
isl_basic_map_detect_equalities: explicitly keep track of any equalities found
The way extend_affine_hull works is that it starts off from an
under-approximation of the affine hull and then extends it with
each extra point found outside of the current approximation.
The affine hull is then determined by the equalities that remain.
However, during the computation, we may find an equality in
the current approximation such that there is no point in the set
outside of this equality. If the approximation is later extended
with a point found outside some other equality, then this first
equality would get tested again. If this is a difficult computation,
then we needlessly go through it again.
By explicitly storing the equality that we have detected in the set,
this computation becomes trivial, to there is no real harm in doing
again. An alternative would be to keep track of all equalities found
in some additional data structure, but adding it to the original set
seems preferable since it may also simplify tests for points outside
other equalities.
Perhaps the calling convention should be changed such that
extend_affine_hull would return the original set intersected
with its affine hull, rather than the affine hull itself.
Sven Verdoolaege [Thu, 13 Aug 2009 14:01:12 +0000 (16:01 +0200)]
isl_basic_map_extend_dim: keep hold of sample if dimension doesn't change
Sven Verdoolaege [Sat, 8 Aug 2009 18:08:16 +0000 (20:08 +0200)]
isl_tab_min: read off all information from tableau before rollback
As it happens, the rollback has little effect in this case and
the information is still available, but we shouldn't depend on this.
Sven Verdoolaege [Sat, 8 Aug 2009 18:02:40 +0000 (20:02 +0200)]
isl_tab_add_valid_eq: keep track of whether equality is negated
This is important during generalized basis reduction, because
this procedure requires the dual variables of some of the
equalities added to the tableau. If the original equality get
negated then the dual of the original equality will be the
opposite of the dual of the equality that was actually added.
Without this fix, gbr could in some cases make completely
inappropriate decisions.
Sven Verdoolaege [Fri, 7 Aug 2009 12:29:56 +0000 (14:29 +0200)]
configure.ac: no longer use piplib by default
Sven Verdoolaege [Wed, 22 Jul 2009 12:48:07 +0000 (14:48 +0200)]
add an internal parametric integer linear program solver
This removes the dependence on piplib.
The solver is very similar to the one in piplib.
In particular, as in piplib, the lexicographic solver is
used recursively on the context. This means that the current
solver will run into the same problems the piplib solver runs into
while looking for an integer point in a context that no longer has any.
In the future, we will replace this recursive call by a call
to an incremental solver based on the generalized basis reduction solver.
Sven Verdoolaege [Thu, 6 Aug 2009 14:15:56 +0000 (16:15 +0200)]
isl_mat_extend: make sure the number of rows never decreases
Sven Verdoolaege [Thu, 6 Aug 2009 10:20:46 +0000 (12:20 +0200)]
isl_affine_hull.c: only construct affine hull in bounded directions
The affine hull of a set necessarily contains the directions
of the recession cone of the set.
Before we exploited this fact by adding these directions to
our initial approximation of the affine hull.
The set for which the affine hull was computed was not changed, however.
Now, we project out the recession cone and only construct an
affine hull in the remaining part.
Sven Verdoolaege [Fri, 7 Aug 2009 08:07:44 +0000 (10:07 +0200)]
isl_tab: add support for keeping track of samples
Sven Verdoolaege [Wed, 5 Aug 2009 09:01:05 +0000 (11:01 +0200)]
isl_tab: optionally keep track of row signs
Sven Verdoolaege [Wed, 5 Aug 2009 08:49:48 +0000 (10:49 +0200)]
isl_tab: add isl_basic_set field for optionally keeping track of inequalities
Sven Verdoolaege [Wed, 5 Aug 2009 08:22:52 +0000 (10:22 +0200)]
isl_tab: introduce support for "big parameters"
These will be used while solving PILP problems.
Sven Verdoolaege [Wed, 5 Aug 2009 08:02:02 +0000 (10:02 +0200)]
isl_tab: allow introduction of extra variables
Sven Verdoolaege [Wed, 5 Aug 2009 08:08:04 +0000 (10:08 +0200)]
isl_tab: introduce parameters and divs
Sven Verdoolaege [Fri, 7 Aug 2009 09:39:50 +0000 (11:39 +0200)]
isl_tab.h: fix typo in comment
Sven Verdoolaege [Wed, 5 Aug 2009 07:46:00 +0000 (09:46 +0200)]
isl_tab: allow saving and restoring the complete basis
Sven Verdoolaege [Wed, 5 Aug 2009 07:37:07 +0000 (09:37 +0200)]
isl_tab: privately export some functionality
Sven Verdoolaege [Wed, 5 Aug 2009 07:25:40 +0000 (09:25 +0200)]
isl_tab: store undo argument in a union for future extensions
Sven Verdoolaege [Thu, 6 Aug 2009 10:35:46 +0000 (12:35 +0200)]
add isl_basic_set_sample_bounded
Sven Verdoolaege [Tue, 4 Aug 2009 15:17:26 +0000 (17:17 +0200)]
privately export isl_basic_set_order_divs
Sven Verdoolaege [Tue, 4 Aug 2009 15:00:43 +0000 (17:00 +0200)]
isl_map_simplify.c: remove_dependent_vars: only remove definitions of divs
Don't remove the dependent divs themselves, because in particular
eliminate_divs_ineq does not expect any other divs to get removed.
Sven Verdoolaege [Mon, 3 Aug 2009 18:40:22 +0000 (20:40 +0200)]
isl_basic_map_compute_divs: use isl_basic_set_lexmin and move to isl_map.c
There is no need for the core of isl_basic_map_compute_divs to use any
piplib specific code. We therefore move the code to isl_map.c so
that it can also be used on top of another PILP solver.
Sven Verdoolaege [Mon, 3 Aug 2009 17:58:51 +0000 (19:58 +0200)]
isl_pip_basic_map_compute_divs: don't turn divs into output dimensions
There is no practical reason why we should want to do this transformation
and removing it makes it possible to you use the standard interface
to pip in the next commit.
Sven Verdoolaege [Mon, 3 Aug 2009 14:20:01 +0000 (16:20 +0200)]
privately export isl_basic_map_swap_div
Sven Verdoolaege [Mon, 3 Aug 2009 10:01:57 +0000 (12:01 +0200)]
isl_{set,map}_add: don't add obviously empty basic sets/maps
Sven Verdoolaege [Sun, 2 Aug 2009 17:46:30 +0000 (19:46 +0200)]
combine isl_pip_basic_map_lex{min,max} into isl_pip_basic_map_lexopt
Sven Verdoolaege [Sun, 2 Aug 2009 11:46:17 +0000 (13:46 +0200)]
make piplib headers private
Sven Verdoolaege [Sun, 2 Aug 2009 08:51:34 +0000 (10:51 +0200)]
isl_mat: keep track of the actual number of columns in a row
We need this number to perform extensions after dropping columns.
Sven Verdoolaege [Sat, 1 Aug 2009 17:32:04 +0000 (19:32 +0200)]
isl_tab_pivot: fix typo that prevented normalization of rows
Sven Verdoolaege [Wed, 29 Jul 2009 13:18:47 +0000 (15:18 +0200)]
add isl_basic_set_positive_orthant
Sven Verdoolaege [Wed, 29 Jul 2009 12:40:46 +0000 (14:40 +0200)]
add isl_basic_set_partial_lex{min,max}