May 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Do not test for result dependent on floating point steepest edge heuristics .
by Enea Zaffanella 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: 4e772ae5ffad4a94f13dc446805cb2fc79353ebc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4e772ae5ffad… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon May 11 13:51:59 2009 +0200 Do not test for result dependent on floating point steepest edge heuristics. --- tests/MIP_Problem/mipproblem1.cc | 3 --- 1 files changed, 0 insertions(+), 3 deletions(-) diff --git a/tests/MIP_Problem/mipproblem1.cc b/tests/MIP_Problem/mipproblem1.cc index 22e14ba..17c441b 100644 --- a/tests/MIP_Problem/mipproblem1.cc +++ b/tests/MIP_Problem/mipproblem1.cc @@ -138,9 +138,6 @@ test01() { Generator pg = mip.optimizing_point(); nout << "Optimizing point = "; print_generator(pg); - Generator pg_kr = point(2*X21 + 44*X39); - if (pg != pg_kr) - return false; // Making mip unfeasible. Constraint_System further_cs;

1 0

[GIT] ppl/ppl(master): Avoid unnecessary unbounded precision value in floating point steepest edge .
by Enea Zaffanella 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: fbd07c16deb6fa87b4cc8995a548cb53e1a1916b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fbd07c16deb6… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon May 11 13:49:40 2009 +0200 Avoid unnecessary unbounded precision value in floating point steepest edge. --- src/MIP_Problem.cc | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 132912b..e26afe6 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -857,12 +857,13 @@ PPL::MIP_Problem::process_pending_constraints() { PPL::dimension_type PPL::MIP_Problem::steepest_edge_float_entering_index() const { - PPL_DIRTY_TEMP0(mpq_class, real_coeff); const dimension_type tableau_num_rows = tableau.num_rows(); assert(tableau_num_rows == base.size()); double challenger_num = 0.0; double challenger_den = 0.0; double current_value = 0.0; + double float_tableau_value = 0.0; + double float_tableau_denum = 0.0; dimension_type entering_index = 0; const int cost_sign = sgn(working_cost[working_cost.size() - 1]); for (dimension_type j = tableau.num_columns() - 1; j-- > 1; ) { @@ -880,10 +881,9 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { const Coefficient& tableau_ij = tableau_i[j]; if (tableau_ij != 0) { assert(tableau_i[base[i]] != 0); - assign_r(real_coeff.get_num(), tableau_ij, ROUND_NOT_NEEDED); - assign_r(real_coeff.get_den(), tableau_i[base[i]], ROUND_NOT_NEEDED); - real_coeff.canonicalize(); - double float_tableau_value = real_coeff.get_d(); + assign_r(float_tableau_value, tableau_ij, ROUND_IGNORE); + assign_r(float_tableau_denum, tableau_i[base[i]], ROUND_IGNORE); + float_tableau_value /= float_tableau_denum; challenger_den += float_tableau_value * float_tableau_value; } }

1 0

[GIT] ppl/ppl(master): Added a _draft_ description of the wrap operator for grids.
by Patricia Hill 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: a36b05302ae483bff5778a75ec5d1abe632db241 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a36b05302ae4… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon May 11 11:56:02 2009 +0100 Added a _draft_ description of the wrap operator for grids. --- doc/definitions.dox | 41 +++++++++++++++++++++++++++++++++++++++++ 1 files changed, 41 insertions(+), 0 deletions(-) diff --git a/doc/definitions.dox b/doc/definitions.dox index 75d30ce..a1cc335 100644 --- a/doc/definitions.dox +++ b/doc/definitions.dox @@ -2313,6 +2313,47 @@ A grid \f$\cL\f$ <EM>subsumes</EM> a (polyhedron) ray or line \f$g\f$ if adding the corresponding grid line to any grid generator system representing \f$\cL\f$ does not change \f$\cL\f$. +\subsection Wrapping_Operator Wrapping Operator + +The operator <CODE>wrap_assign</CODE> provided by the library, allows +for the wrapping of a subset of the set of space dimensions so to fit +the given bounded integer type and have the specified overflow behavior. + +Suppose \f$\cL \in \Gset_n\f$ is a grid and \f$J\f$ a subset of the +set of space dimensions \f$\{0, \ldots, n-1\}\f$. +Suppose also that the width of the bounded integer type is \f$w\f$ so that +the range of values can be \f$0 - 2^w-1\f$ if the type is unsigned +and \f$-2^{w-1} - 2^{w-1} - 1\f$ otherwise. +Consider a space dimension \f$j \in J\f$. + +If the value in \f$\cL\f$ for the dimension \f$j\f$ is bounded and +hence a constant, no wrapping can take place; in this case the +grid is unchanged. + +Otherwise the value for the dimension \f$j\f$ will be unbounded and +the result of the operation will depend on which of +three possible overflow behaviors has been specified. + +- Overflow impossible: in this case, it is known that no wrapping can + occur; if the grid has exactly one possible value for the given + bounded integer type, then the dimension \f$j\f$ is set equal to + that value, otherwise, the grid is unchanged. + +- Overflow undefined: in this case, the wrapped value can be any + integer within the range of the bounded integer type, so that the + parameter \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, where + \f$v_j = 1\f$ is added to the generator system. + +- Overflow wraps: in this case, the \f$j\f$ dimension can be wrapped to + a value modulo \f$2^w\f$, so that the parameter + \f$(0, \ldots, 0, v_j, 0, \dots, 0)\f$, where \f$v_j = 2^w\f$ + is added to the generator system. + +Note that the <CODE>wrap_assign</CODE> is intended for dimensions that +can take integral values; if this not the case for any of the +dimensions in \f$J\f$ for the grid \f$\cL\f$, the behavior is +undefined. + \subsection Grid_Widening Widening Operators The library provides <EM>grid widening</EM> operators for the domain of grids.

1 0

[GIT] ppl/ppl(master): Got rid of a TODO item.
by Enea Zaffanella 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: 71e9992afa9bc049b93d0b29fd9dbe52ead850cf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=71e9992afa9b… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon May 11 12:30:58 2009 +0200 Got rid of a TODO item. Also avoid an annoying warning about an uninitialized variable. --- TODO | 2 -- src/MIP_Problem.cc | 23 +++-------------------- 2 files changed, 3 insertions(+), 22 deletions(-) diff --git a/TODO b/TODO index c0a11a1..145be12 100644 --- a/TODO +++ b/TODO @@ -11,8 +11,6 @@ Enhancements for PPL 0.11 - Make all the *affine*image() methods uniform as far as the specification is concerned. - Check the use or the NOT_EQUAL Relation_Symbol everywhere. -- Get rid of ugly assign functions defined in anonymous namespace of - MIP_Problem.cc replacing it with a more general-purpose approach. - Reconsider the datatype for the units parameter in the Watchdog constructors: should we prefer an unsigned? - Rename set_rational_sqrt_precision_parameter to diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 1fb17cf..132912b 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -855,22 +855,6 @@ PPL::MIP_Problem::process_pending_constraints() { return true; } -namespace { - -inline void -assign(double& d, const mpz_class& c) { - d = c.get_d(); -} - -template <typename T, typename Policy> -inline void -assign(double& d, - const Parma_Polyhedra_Library::Checked_Number<T, Policy>& c) { - d = raw_value(c); -} - -} // namespace - PPL::dimension_type PPL::MIP_Problem::steepest_edge_float_entering_index() const { PPL_DIRTY_TEMP0(mpq_class, real_coeff); @@ -886,7 +870,7 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { if (sgn(cost_j) == cost_sign) { // We cannot compute the (exact) square root of abs(\Delta x_j). // The workaround is to compute the square of `cost[j]'. - assign(challenger_num, cost_j); + assign_r(challenger_num, cost_j, ROUND_IGNORE); challenger_num = fabs(challenger_num); // Due to our integer implementation, the `1' term in the denominator // of the original formula has to be replaced by `squared_lcm_basis'. @@ -899,8 +883,7 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { assign_r(real_coeff.get_num(), tableau_ij, ROUND_NOT_NEEDED); assign_r(real_coeff.get_den(), tableau_i[base[i]], ROUND_NOT_NEEDED); real_coeff.canonicalize(); - double float_tableau_value; - assign(float_tableau_value, real_coeff); + double float_tableau_value = real_coeff.get_d(); challenger_den += float_tableau_value * float_tableau_value; } } @@ -1565,7 +1548,7 @@ PPL::MIP_Problem::solve_mip(bool& have_incumbent_solution, bool found_satisfiable_generator = true; PPL_DIRTY_TEMP_COEFFICIENT(gcd); const Coefficient& p_divisor = p.divisor(); - dimension_type nonint_dim; + dimension_type nonint_dim = lp.space_dimension(); for (Variables_Set::const_iterator v_begin = i_vars.begin(), v_end = i_vars.end(); v_begin != v_end; ++v_begin) { gcd_assign(gcd, p.coefficient(Variable(*v_begin)), p_divisor);

1 0

[GIT] ppl/ppl(master): Redid the intended changes for the last commit for wrap_assign().
by Patricia Hill 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: e524876115832265137efe4a372b84236e6a0b26 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e52487611583… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon May 11 08:34:11 2009 +0100 Redid the intended changes for the last commit for wrap_assign(). --- src/Grid.defs.hh | 4 ++-- src/Grid_nonpublic.cc | 9 ++++++++- src/Grid_public.cc | 12 +----------- 3 files changed, 11 insertions(+), 14 deletions(-) diff --git a/src/Grid.defs.hh b/src/Grid.defs.hh index bd4babb..bfb6d12 100644 --- a/src/Grid.defs.hh +++ b/src/Grid.defs.hh @@ -2160,8 +2160,8 @@ private: \p val_n and \p val_d are left untouched. \warning - If \p expr and \p *this are dimension-incompatible, or the generators - are not minimized, then the behavior is undefined. + If \p expr and \p *this are dimension-incompatible, + then the behavior is undefined. */ bool frequency_no_check(const Linear_Expression& expr, Coefficient& freq_n, Coefficient& freq_d, diff --git a/src/Grid_nonpublic.cc b/src/Grid_nonpublic.cc index 12d5c6d..214948c 100644 --- a/src/Grid_nonpublic.cc +++ b/src/Grid_nonpublic.cc @@ -317,7 +317,14 @@ PPL::Grid::frequency_no_check(const Linear_Expression& expr, // The dimension of `expr' must be at most the dimension of *this. assert(space_dim >= expr.space_dimension()); - assert(generators_are_minimized() && !is_empty()); + + // The frequency is undefined if the grid is empty; return false. + if (marked_empty()) + return false; + if (!generators_are_minimized() && !minimize()) + return false; + + // The generators are up to date and minimized and the grid is non-empty. // If the grid is bounded for the expression `expr', // then `expr' has a constant value and the frequency is 0. diff --git a/src/Grid_public.cc b/src/Grid_public.cc index 68378d5..be66a1a 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -2659,11 +2659,7 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, if (vars.empty()) return; -<<<<<<< HEAD:src/Grid_public.cc - const dimension_type space_dim = space_dimension(); // Dimension-compatibility check of `vars'. -======= ->>>>>>> Improved and corrected draft code for wrap_assign() for grids.:src/Grid_public.cc const dimension_type min_space_dim = vars.space_dimension(); if (space_dim < min_space_dim) throw_dimension_incompatible("wrap_assign(vs, ...)", min_space_dim); @@ -2680,7 +2676,7 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, PPL_DIRTY_TEMP_COEFFICIENT(wrap_frequency); mul_2exp_assign(wrap_frequency, Coefficient_one(), w); - // Generators are up-to-date. + // Generators are up-to-date and minimized. const Grid gr = *this; // Overflow is impossible. So check if value might be constant. @@ -2720,14 +2716,8 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, for (Variables_Set::const_iterator i = vars.begin(), vars_end = vars.end(); i != vars.end(); ++i) { const Variable x = Variable(*i); -<<<<<<< HEAD:src/Grid_public.cc - - // If `x' is a constant, do nothing. - if (!gr.bounds(x, "wrap_assign(...)")) { -======= // If `x' is a constant, do nothing. if (!gr.bounds_no_check(x)) { ->>>>>>> Improved and corrected draft code for wrap_assign() for grids.:src/Grid_public.cc if (gr.constrains(x)) // We know that `x' is not a constant, // so `x' may wrap to any integral value.

1 0

[GIT] ppl/ppl(master): Improved wrap_assign() for grids.
by Patricia Hill 11 May '09

11 May '09

Module: ppl/ppl Branch: master Commit: 4bea722b328721dda174ad5e2c218695eacf9e49 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4bea722b3287… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon May 11 07:34:50 2009 +0100 Improved wrap_assign() for grids. Added private methods bounds_no_check() and frequency_no_check(). --- src/Grid.defs.hh | 48 +++++++++++++- src/Grid_nonpublic.cc | 88 ++++++++++++++++++++++++- src/Grid_public.cc | 81 ++++++++++++++++------ tests/Grid/wrap1.cc | 178 ++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 363 insertions(+), 32 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=4bea722b…

1 0

Re: [PPL-devel] [Fwd: Re: Some troubles I met while building PPL.]
by Enea Zaffanella 11 May '09

11 May '09

Yuriy Taraday wrote: > Oh, we didn't mention this function before. > I'm curious why "const jobject&"? jobject - just a pointer and constant > referencing to a pointer looks pointless. [...] > //! Returns a pointer to the C++ object wrapped by \p ppl_object. > void* > get_ptr(JNIEnv* env, const jobject& ppl_object); I guess that, since we are not JNI experts, we just tried to take a safer approach whereby the `jobject' datatype is treated as a black box. Usually, when we need to pass a "black box" datatype as an argument, we pass it by reference; since we do not need to modify it in this function, we also qualify it using const. I just realized that we haven't been fully systematic in this respect, since we also have the helper function //! Returns \c true if and only if \p obj is a null Java reference. jboolean is_null(JNIEnv* env, jobject obj); which is passing its jobject argument by copy. Cheers, Enea Zaffanella.

2 3

[GIT] ppl/ppl(bounded_arithmetic): Added umod_2exp and smod_2exp to checked numbers. Fixed rem for mpq to work similarly to other numeric types.
by Abramo Bagnara 10 May '09

10 May '09

Module: ppl/ppl Branch: bounded_arithmetic Commit: 80ba9754deb09f8d3a2d938d2aa6f0b93262f2ed URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=80ba9754deb0… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Sun May 10 19:30:17 2009 +0200 Added umod_2exp and smod_2exp to checked numbers. Fixed rem for mpq to work similarly to other numeric types. --- src/Checked_Number.defs.hh | 2 + src/Checked_Number.inlines.hh | 2 + src/Rounding_Dir.inlines.hh | 4 ++ src/checked.defs.hh | 12 +++++ src/checked_ext.inlines.hh | 34 +++++++++++++++ src/checked_float.inlines.hh | 45 +++++++++++++++++++- src/checked_int.inlines.hh | 92 +++++++++++++++++++++++++++++++++++++---- src/checked_mpq.inlines.hh | 37 +++++++++++++++- src/checked_mpz.inlines.hh | 25 +++++++++++ 9 files changed, 240 insertions(+), 13 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=80ba9754…

1 0

[GIT] ppl/ppl(bounded_arithmetic): Drafted specialized implementation for Box<ITV>::wrap_assign.
by Enea Zaffanella 09 May '09

09 May '09

Module: ppl/ppl Branch: bounded_arithmetic Commit: 98fb9c3061d18890418df3c8cfc7ff4370df134a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=98fb9c3061d1… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat May 9 14:22:25 2009 +0200 Drafted specialized implementation for Box<ITV>::wrap_assign. Code still commented out as it relies on a missing Interval method. --- src/Box.defs.hh | 57 ++++++++++++++++++++++ src/Box.inlines.hh | 46 +++++++++++------ src/Box.templates.hh | 121 ++++++++++++++++++++++++++++++++++++++++++++++ src/wrap_assign.hh | 4 +- tests/Box/Makefile.am | 3 + tests/Box/wrap1.cc | 129 +++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 342 insertions(+), 18 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=98fb9c30…

1 0

[GIT] ppl/ppl(master): Use the appropriate throw_dimension_incompatible() method in wrap_assign().
by Roberto Bagnara 09 May '09

09 May '09

Module: ppl/ppl Branch: master Commit: bd05d651cc3931ff02b0b57477bbca68c927f3ce URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bd05d651cc39… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Sat May 9 09:44:34 2009 +0200 Use the appropriate throw_dimension_incompatible() method in wrap_assign(). --- src/Grid_public.cc | 13 ++++--------- 1 files changed, 4 insertions(+), 9 deletions(-) diff --git a/src/Grid_public.cc b/src/Grid_public.cc index 1f2cda5..35fff9f 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -2660,13 +2660,9 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, const dimension_type space_dim = space_dimension(); // Dimension-compatibility check of `vars'. - if (space_dim < vars.space_dimension()) { - std::ostringstream s; - s << "PPL::Grid::wrap_assign(vars, ...):" << std::endl - << "this->space_dimension() == " << space_dim - << ", required space dimension == " << vars.space_dimension() << "."; - throw std::invalid_argument(s.str()); - } + const dimension_type min_space_dim = vars.space_dimension(); + if (space_dim < min_space_dim) + throw_dimension_incompatible("wrap_assign(vs, ...)", min_space_dim); // Wrapping an empty polyhedron is a no-op. if (marked_empty()) @@ -2683,10 +2679,9 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, if (o == OVERFLOW_UNDEFINED) { for (Variables_Set::const_iterator i = vars.begin(), vars_end = vars.end(); i != vars.end(); ++i) { - const Variable x = Variable(*i); - // If x is a constant, do nothing. + // If `x' is a constant, do nothing. if (!gr.bounds(x, "wrap_assign(...)")) { if (gr.constrains(x)) // We know that x is not a constant,

1 0