September 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(floating_point): Now the trivial case of affine_image works.
by Fabio Bossi 11 Sep '09

11 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 589af008cb61b7ae84b5a7b4d83664282554ad5e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=589af008cb61… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Fri Sep 11 10:01:36 2009 +0200 Now the trivial case of affine_image works. --- src/Octagonal_Shape.templates.hh | 21 ++++++++++++++------- 1 files changed, 14 insertions(+), 7 deletions(-) diff --git a/src/Octagonal_Shape.templates.hh b/src/Octagonal_Shape.templates.hh index 645bd04..b891006 100644 --- a/src/Octagonal_Shape.templates.hh +++ b/src/Octagonal_Shape.templates.hh @@ -4724,6 +4724,11 @@ Octagonal_Shape<T>::affine_image(Variable var, const dimension_type n_var = 2*var_id; const FP_Interval_Type& b = lf.inhomogeneous_term(); + PPL_DIRTY_TEMP(N, b_lb); + PPL_DIRTY_TEMP(N, b_ub); + assign_r(b_lb, b.lower(), ROUND_NOT_NEEDED); + assign_r(b_ub, b.upper(), ROUND_NOT_NEEDED); + // `w' is the variable with index `w_id'. // Now we know the form of `lf': // - If t == 0, then lf == [lb;ub]; @@ -4734,18 +4739,20 @@ Octagonal_Shape<T>::affine_image(Variable var, if (t == 0) { // Case 1: lf = [lb;ub]; forget_all_octagonal_constraints(var_id); - FP_Interval_Type two_b(b); - two_b *= 2; + PPL_DIRTY_TEMP(N, two_mlb); + PPL_DIRTY_TEMP(N, two_ub); + neg_assign_r(two_mlb, b_lb, ROUND_NOT_NEEDED); + assign_r(two_ub, b_ub, ROUND_NOT_NEEDED); + add_assign_r(two_mlb, two_mlb, two_mlb, ROUND_UP); + add_assign_r(two_ub, two_ub, two_ub, ROUND_UP); // Add the constraint `var >= lb && var <= ub'. - add_octagonal_constraint(n_var+1, n_var, two_b.upper()); - add_octagonal_constraint(n_var, n_var+1, -two_b.lower()); + add_octagonal_constraint(n_var+1, n_var, two_ub); + add_octagonal_constraint(n_var, n_var+1, two_mlb); PPL_ASSERT(OK()); return; } - T lb = b.lower(); - T ub = b.upper(); - bool is_b_zero = (lb == 0 && ub == 0); + bool is_b_zero = (b_lb == 0 && b_ub == 0); if (t == 1) {

1 0

[GIT] ppl/ppl(floating_point): Written a preliminary, non working first part of our variant of
by Fabio Bossi 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 29936bbc3648a9831b4dd37c3901462cfd158cae URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=29936bbc3648… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Thu Sep 10 18:04:36 2009 +0200 Written a preliminary, non working first part of our variant of affine_image. --- src/Octagonal_Shape.templates.hh | 36 ++++++++++++++++++++++++++++++++++++ 1 files changed, 36 insertions(+), 0 deletions(-) diff --git a/src/Octagonal_Shape.templates.hh b/src/Octagonal_Shape.templates.hh index 69cf0eb..645bd04 100644 --- a/src/Octagonal_Shape.templates.hh +++ b/src/Octagonal_Shape.templates.hh @@ -4715,6 +4715,42 @@ Octagonal_Shape<T>::affine_image(Variable var, w_id = i; } + typedef typename OR_Matrix<N>::row_iterator Row_Iterator; + typedef typename OR_Matrix<N>::row_reference_type Row_Reference; + typedef typename OR_Matrix<N>::const_row_iterator Row_iterator; + typedef typename OR_Matrix<N>::const_row_reference_type Row_reference; + typedef Interval<T, Interval_Info> FP_Interval_Type; + + const dimension_type n_var = 2*var_id; + const FP_Interval_Type& b = lf.inhomogeneous_term(); + + // `w' is the variable with index `w_id'. + // Now we know the form of `lf': + // - If t == 0, then lf == [lb;ub]; + // - If t == 1, then lf == a*w + [lb;ub], where `w' can be `v' or another + // variable; + // - If t == 2, the `lf' is of the general form. + + if (t == 0) { + // Case 1: lf = [lb;ub]; + forget_all_octagonal_constraints(var_id); + FP_Interval_Type two_b(b); + two_b *= 2; + // Add the constraint `var >= lb && var <= ub'. + add_octagonal_constraint(n_var+1, n_var, two_b.upper()); + add_octagonal_constraint(n_var, n_var+1, -two_b.lower()); + PPL_ASSERT(OK()); + return; + } + + T lb = b.lower(); + T ub = b.upper(); + bool is_b_zero = (lb == 0 && ub == 0); + + if (t == 1) { + + } + // FIXME: complete the implementation. }

1 0

[Fwd: Re: PPL on a Power6 running AIX]
by Roberto Bagnara 10 Sep '09

10 Sep '09

-------- Original Message -------- Subject: Re: [PPL-devel] PPL on a Power6 running AIX Date: Thu, 10 Sep 2009 06:56:57 -0600 From: Davide Del Vento <ddvento(a)mail.ucar.edu> To: Roberto Bagnara <bagnara(a)cs.unipr.it> References: <4AA7F256.10007(a)ucar.edu> <4AA8A0AB.4070001(a)cs.unipr.it> Thanks a lot for your message! xlc and xlC are the IBM's compilers for c and c++ respectively. They do support several standards: http://publib.boulder.ibm.com/infocenter/lnxpcomp/v8v101/index.jsp?topic=/c… and sometimes are more nitpicking than gcc about the standards, as I believe it's happening here. I'll try to figure out (I am not fluent about C++ specs) and let you know. Compiling with gcc is possible, but there will be several linking problems with other libraries that I eventually need to link together (gcc binaries are not-linkable with xlc binaries). Thanks again ;Dav On Thu, 10 Sep 2009 08:46:03 +0200 Roberto Bagnara <bagnara(a)cs.unipr.it> wrote: > Davide Del Vento wrote: >> Folks, >> I am trying to compile the latest PPL on bluefire, an IBM Power6 >>running >> AIX 5.3, with IBM's compiler xlc/xlC >> (http://www.cisl.ucar.edu/docs/bluefire/be_quickstart.html#software) >> >> Unfortunately, while the configure script is happy (see config.log >>for >> details), the compilation fails as described in the attached >>make.log >> and I have no clues about it. >> >> Note that before it was failing with the following one, which I >>believe >> was due to a different make version being used, but might be the >>first >> culprit (I have the make.log for this too but I'm not sending it >>right now): >> >> /usr/bin/sed -f ./ppl-config.sed >ppl-config.h >> "../ppl-config.h", line 1.0: 1540-0809 (W) The source file is empty. >> >> Do you have any recommendations about what I can do to fix the >>issue? > > Hi Davide, > > looking at config.log, I gather you are using C and C++ compilers > called xlc and xlC, respectively. We never compiled the PPL using >those, > but this should not be a problem as long as they implement a large >enough > fragment of the C and C++ standards. > > Looking at make.log, I see something strange is happening. The >first errors, > that is, > > "Row.defs.hh", line 88.46: 1540-0063 (S) The text "Row_Impl_Handler" >is unexpected. > "Linear_Row.defs.hh", line 124.52: 1540-0063 (S) The text "Row" is >unexpected. > "Linear_Expression.defs.hh", line 236.60: 1540-0063 (S) The text >"Linear_Row" is unexpected. > "Linear_System.defs.hh", line 54.55: 1540-0063 (S) The text "Matrix" >is unexpected. > "Constraint_System.defs.hh", line 127.60: 1540-0063 (S) The text >"Linear_System" is unexpected. > "Constraint.defs.hh", line 260.53: 1540-0063 (S) The text >"Linear_Row" is unexpected. > "Congruence_System.defs.hh", line 120.60: 1540-0063 (S) The text >"Matrix" is unexpected. > > would be explained if you were including some funny header file >doing > > #define private > #define public > > I know, this is crazy, but how else could the text >"Row_Impl_Handler" > be unexpected in the lines > > class Parma_Polyhedra_Library::Row : private Row_Impl_Handler { > > and > > class Parma_Polyhedra_Library::Linear_Row : public Row { > > ? > > Do you have the option of compiling with GCC 4.0.3 or later version? > Otherwise, please use the -E option of your compiler to inspect the > preprocessor output, and check how the two lines above are >transformed. > >> PS: I speak Italian, but I'm not sure if this list is read just by >> Italian, despite its .it domain. > > This is an English-language mailing list indeed. > All the best, > > Roberto > > -- > Prof. Roberto Bagnara > Computer Science Group > Department of Mathematics, University of Parma, Italy > http://www.cs.unipr.it/~bagnara/ > mailto:bagnara@cs.unipr.it -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

[GIT] ppl/ppl(pip): Improved recently added helper functions.
by Enea Zaffanella 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: pip Commit: 4f1061d0e0fb1e9f5f8f49d7ad47b7cad681fdee URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4f1061d0e0fb… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 10 17:25:05 2009 +0200 Improved recently added helper functions. - avoid recomputing loop bounds at each iteration; - delay object definitions until actually needed and, if possible, provide them with an initializer. --- src/PIP_Tree.cc | 20 ++++++++++---------- 1 files changed, 10 insertions(+), 10 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 855ad88..041184e 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -25,28 +25,28 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <algorithm> -namespace PPL = Parma_Polyhedra_Library; +namespace Parma_Polyhedra_Library { namespace { // Compute x += c * y void -add_assign(PPL::Row& x, const PPL::Row& y, const PPL::Coefficient &c) { - for (PPL::dimension_type i=0; i<x.size(); ++i) - x[i] += c * y[i]; +add_assign(Row& x, const Row& y, Coefficient_traits::const_reference c) { + PPL_ASSERT(x.size() == y.size()); + for (dimension_type i = x.size(); i-- > 0; ) + add_mul_assign(x[i], c, y[i]); } // Merge constraint systems such as x = x U z void -merge(PPL::Constraint_System &x, const PPL::Constraint_System &y) { - PPL::Constraint_System::const_iterator i; - for (i=y.begin(); i!=y.end(); ++i) - x.insert(*i); +merge_assign(Constraint_System& x, const Constraint_System& y) { + for (Constraint_System::const_iterator y_i = y.begin(), + y_end = y.end(); y_i != y_end; ++y_i) + x.insert(*y_i); } } // namespace -namespace Parma_Polyhedra_Library { PIP_Decision_Node::~PIP_Decision_Node() { delete true_child; @@ -134,7 +134,7 @@ PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, PIP_Problem_Status stt; PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; Constraint_System context_true(context); - merge(context_true, constraints_); + merge_assign(context_true, constraints_); stt = true_child->solve(&true_child, context_true); if (false_child) { // Decision nodes with false child must have exactly one constraint

1 0

[GIT] ppl/ppl(pip): Fix compilation problems when assertions are turned on.
by Enea Zaffanella 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: pip Commit: 2747f04f7bcc20e051df967fc6d35f91b7f22605 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2747f04f7bcc… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 10 16:41:24 2009 +0200 Fix compilation problems when assertions are turned on. --- src/PIP_Tree.cc | 24 +++++++++++++++++++----- src/PIP_Tree.defs.hh | 10 +++++++++- 2 files changed, 28 insertions(+), 6 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 9f039ea..855ad88 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -23,6 +23,8 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <ppl-config.h> #include "PIP_Tree.defs.hh" +#include <algorithm> + namespace PPL = Parma_Polyhedra_Library; namespace { @@ -94,8 +96,20 @@ PIP_Decision_Node::as_decision() { return this; } +bool +PIP_Solution_Node::OK() const { + /* FIXME: write me! */ + return true; +} + +bool +PIP_Decision_Node::OK() const { + /* FIXME: write me! */ + return true; +} + void -PIP_Decision_Node::update_tableau(PIP_Tree_Node **parent_ref, +PIP_Decision_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */, dimension_type external_space_dim, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, @@ -124,7 +138,7 @@ PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, stt = true_child->solve(&true_child, context_true); if (false_child) { // Decision nodes with false child must have exactly one constraint - PPL_ASSERT(constraints_.num_rows() == 1); + PPL_ASSERT(1 == std::distance(constraints_.begin(), constraints_.end())); Constraint_System context_false(context); //FIXME: not implemented yet (constraint negation) //context_false.insert(!constraints_[0]); @@ -198,7 +212,7 @@ PIP_Solution_Node::ascii_load(std::istream& s) { } void -PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, +PIP_Solution_Node::update_tableau(PIP_Tree_Node ** /* parent_ref */, dimension_type external_space_dim, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, @@ -266,8 +280,8 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, } PIP_Problem_Status -PIP_Solution_Node::solve(PIP_Tree_Node **parent_ref, - const Constraint_System& context) { +PIP_Solution_Node::solve(PIP_Tree_Node** /* parent_ref */, + const Constraint_System& /* context */) { //FIXME return OPTIMIZED_PIP_PROBLEM; } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index e1555a2..c3c1b4b 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -26,7 +26,8 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "PIP_Tree.types.hh" #include "Variable.defs.hh" #include "Linear_Expression.types.hh" -#include "Constraint_System.types.hh" +#include "Constraint_System.defs.hh" +#include "Constraint_System.inlines.hh" #include "Constraint.defs.hh" #include "PIP_Problem.types.hh" #include "Matrix.defs.hh" @@ -56,6 +57,9 @@ public: //! Destructor. virtual ~PIP_Tree_Node(); + //! Returns \c true if and only if \p *this is well formed. + virtual bool OK() const = 0; + protected: //! A type alias for a sequence of constraints. typedef std::vector<Constraint> Constraint_Sequence; @@ -143,6 +147,8 @@ public: void ascii_dump(std::ostream& s) const; bool ascii_load(std::istream& s); + bool OK() const; + private: //! A rational matrix, with a common nenominator class Rational_Matrix : public Matrix { @@ -301,6 +307,8 @@ public: */ const Constraint_System& constraints(); + bool OK() const; + private: //! Pointer to the "true" child of \p *this. PIP_Tree_Node* true_child;

1 0

[GIT] ppl/ppl(pip): Identifiers starting with an underscore are reserved: avoid them.
by Enea Zaffanella 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: pip Commit: aa7e6d41189ddb3217c285569c828c418a725657 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=aa7e6d41189d… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 10 16:11:39 2009 +0200 Identifiers starting with an underscore are reserved: avoid them. --- src/PIP_Tree.cc | 6 +++--- src/PIP_Tree.defs.hh | 4 ++-- 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 42a903e..9f039ea 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -120,14 +120,14 @@ PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, PIP_Problem_Status stt; PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; Constraint_System context_true(context); - merge(context_true, _constraints); + merge(context_true, constraints_); stt = true_child->solve(&true_child, context_true); if (false_child) { // Decision nodes with false child must have exactly one constraint - PPL_ASSERT(_constraints.num_rows() == 1); + PPL_ASSERT(constraints_.num_rows() == 1); Constraint_System context_false(context); //FIXME: not implemented yet (constraint negation) - //context_false.insert(!_constraints[0]); + //context_false.insert(!constraints_[0]); stf = false_child->solve(&false_child, context_false); } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index f02631a..e1555a2 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -227,7 +227,7 @@ private: std::vector<dimension_type> mapping; //! The local system of parameter constraints - Constraint_System _constraints; + Constraint_System constraints_; protected: /*! \brief @@ -309,7 +309,7 @@ private: PIP_Tree_Node* false_child; //! The local system of parameter constraints - Constraint_System _constraints; + Constraint_System constraints_; /*! \brief Constructs if \p cs then \p tcp \p else \p fcp.

1 0

[GIT] ppl/ppl(pip): Implemented some helper functions for the PIP solver.
by François Galea 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: pip Commit: f6b3b1cf93a95d152d50a2fce5a3211cc8fa891f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6b3b1cf93a9… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Sep 10 15:46:25 2009 +0200 Implemented some helper functions for the PIP solver. --- src/PIP_Tree.cc | 48 +++++++++++++++++++++++++++++++++++------------- src/PIP_Tree.defs.hh | 19 +++++++++++-------- 2 files changed, 46 insertions(+), 21 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index db52260..42a903e 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -23,6 +23,27 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <ppl-config.h> #include "PIP_Tree.defs.hh" +namespace PPL = Parma_Polyhedra_Library; + +namespace { + +// Compute x += c * y +void +add_assign(PPL::Row& x, const PPL::Row& y, const PPL::Coefficient &c) { + for (PPL::dimension_type i=0; i<x.size(); ++i) + x[i] += c * y[i]; +} + +// Merge constraint systems such as x = x U z +void +merge(PPL::Constraint_System &x, const PPL::Constraint_System &y) { + PPL::Constraint_System::const_iterator i; + for (i=y.begin(); i!=y.end(); ++i) + x.insert(*i); +} + +} // namespace + namespace Parma_Polyhedra_Library { PIP_Decision_Node::~PIP_Decision_Node() { @@ -99,8 +120,7 @@ PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, PIP_Problem_Status stt; PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; Constraint_System context_true(context); - //FIXME: not implemented yet (merging of constraint systems) - //context_true.merge(_constraints); + merge(context_true, _constraints); stt = true_child->solve(&true_child, context_true); if (false_child) { // Decision nodes with false child must have exactly one constraint @@ -125,6 +145,12 @@ PIP_Solution_Node::Rational_Matrix::normalize() { //FIXME } +//! Returns the allocated capacity of each Row of the Matrix. +dimension_type +PIP_Solution_Node::Rational_Matrix::capacity() { + return row_capacity; +} + void PIP_Solution_Node::Rational_Matrix::ascii_dump(std::ostream& s) const { s << "denominator " << denominator << "\n"; @@ -177,7 +203,7 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters) { - dimension_type i, j; + dimension_type i; dimension_type n_params = parameters.size(); dimension_type n_vars = external_space_dim - n_params; dimension_type internal_space_dim = tableau.t.num_columns()-1; @@ -208,8 +234,8 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, cst < input_cs.end(); ++cst) { int v = 0; int p = 1; - Row var(n_vars, Row::Flags()); - Row param(n_params+1, Row::Flags()); + Row var(n_vars, tableau.s.capacity(), Row::Flags()); + Row param(n_params+1, tableau.t.capacity(), Row::Flags()); Coefficient cnst_term = -cst->inhomogeneous_term(); if (cst->is_strict_inequality()) // convert c > 0 <=> c-1 >= 0 @@ -219,19 +245,15 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, if (parameters.count(i) == 1) { param[p++] = cst->coefficient(Variable(i)) * denom_t; } else { - Coefficient c = cst->coefficient(Variable(i)) * denom_s; + Coefficient c = cst->coefficient(Variable(i)); dimension_type idx = mapping[v]; if (basis[v]) // Basic variable : add c * x_i - var[idx] += c; + var[idx] += c * denom_s; else { // Nonbasic variable : add c * row_i - const Row &sr = tableau.s[idx]; - const Row &st = tableau.t[idx]; - for (j=0; j<sr.size(); j++) - var[j] += c*sr[j]; - for (j=0; j<st.size(); j++) - param[j] += c*st[j]; + add_assign(var, tableau.s[idx], c); + add_assign(param, tableau.t[idx], c); } ++v; } diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 64debe6..f02631a 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -92,10 +92,10 @@ protected: /*! \brief Execute a parametric simplex on the tableau, under specified context. - + \param parent_ref a pointer to the parent reference to \p this - + \param context the context, being a set of constraints on the parameters @@ -132,7 +132,7 @@ public: /*! \brief Returns the system of parameter constraints controlling \p *this. - + The column indices in the constraints are numbered from \c 0 to <tt>np-1</tt>, where \c np is the total number of parameters. They are ordered with the same order as the parameter indices in the original @@ -178,6 +178,9 @@ private: */ void normalize(); + //! Returns the allocated capacity of each Row of the Matrix. + dimension_type capacity(); + //! Tests whether the matrix is integer, \e ie. the denominator is 1. bool is_integer() const; @@ -254,10 +257,10 @@ protected: /*! \brief Execute a parametric simplex on the tableau, under specified context. - + \param parent_ref a pointer to the parent reference to \p this - + \param context the context, being a set of constraints on the parameters @@ -290,7 +293,7 @@ public: /*! \brief Returns the system of parameter constraints controlling \p *this. - + The column indices in the constraints are numbered from \c 0 to <tt>np-1</tt>, where \c np is the total number of parameters. They are ordered with the same order as the parameter indices in the original @@ -372,10 +375,10 @@ protected: /*! \brief Execute a parametric simplex on the tableau, under specified context. - + \param parent_ref a pointer to the parent reference to \p this - + \param context the context, being a set of constraints on the parameters

1 0

[GIT] ppl/ppl(master): Suggest using -fno-elide-constructors when configuring for coverage.
by Enea Zaffanella 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: master Commit: 6a1b3b278146ed990e74b338c1608471d3314be8 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6a1b3b278146… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Sep 10 15:24:16 2009 +0200 Suggest using -fno-elide-constructors when configuring for coverage. --- STANDARDS | 17 +++++++++++------ 1 files changed, 11 insertions(+), 6 deletions(-) diff --git a/STANDARDS b/STANDARDS index 43654aa..e0096c7 100644 --- a/STANDARDS +++ b/STANDARDS @@ -566,12 +566,17 @@ o Ideally the tests should exercise every line of code in the library. Here we summarize the steps needed to produce coverage information using `lcov' (see below for a few hints on the direct use of `gcov'). The build tree under test must be configured with the - `--enable-coverage' and `--disable-optimization options' (and possibly - also with --enable-profiling). For example: - - $ configure --enable-coverage --disable-optimization \ - --enable-profiling \ - --enable-assertions --enable-more-assertions + `--enable-coverage' and `--disable-optimization' options (and possibly + also with --enable-profiling). Furthermore, according to this thread + http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12076 + GCC performs NRV (Named Return Value) transformations even when + optimizations are turned off; hence, to avoid spurious zero counts + in return statements, the compilation flag `-fno-elide-constructors' + is recommended. For example: + + $ configure --enable-coverage --enable-profiling \ + --disable-optimization --with-cxxflags='-fno-elide-constructors' \ + --enable-assertions --enable-more-assertions Running the tests (with `make check') produces many .gcno and .gcda files in src/.libs and in the test directories. These are data

1 0

[GIT] ppl/ppl(floating_point): Fixed another small documentation inconsistency.
by Fabio Bossi 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: floating_point Commit: 8131d3c11b8f1b15387a0cef569eeb319bc07119 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8131d3c11b8f… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Thu Sep 10 15:08:37 2009 +0200 Fixed another small documentation inconsistency. --- src/Variable_Floating_Point_Expression.defs.hh | 6 ++---- 1 files changed, 2 insertions(+), 4 deletions(-) diff --git a/src/Variable_Floating_Point_Expression.defs.hh b/src/Variable_Floating_Point_Expression.defs.hh index 3926033..2efcbc2 100644 --- a/src/Variable_Floating_Point_Expression.defs.hh +++ b/src/Variable_Floating_Point_Expression.defs.hh @@ -62,10 +62,8 @@ namespace Parma_Polyhedra_Library { we construct the interval linear form \f$\linexpr{v} \left \langle \rho^{\#}, \rho^{\#}_l \right \rangle\f$ as - \f$\rho^{\#}_l(v)\f$ if it is defined; otherwise we construct it as: - \f[ - \linexpr{v}\rho^{\#} = [-1;1]v. - \f] + \f$\rho^{\#}_l(v)\f$ if it is defined; otherwise we construct it as + \f$[-1;1]v\f$. */ template <typename FP_Interval_Type, typename FP_Format> class Variable_Floating_Point_Expression

1 0

[GIT] ppl/ppl(pip): Integrated the solve method in the different PIP_Tree node classes.
by François Galea 10 Sep '09

10 Sep '09

Module: ppl/ppl Branch: pip Commit: 2219c62d25286754de2df17ef5efc2cbd83c3085 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2219c62d2528… Author: François Galea <francois.galea(a)uvsq.fr> Date: Thu Sep 10 14:48:21 2009 +0200 Integrated the solve method in the different PIP_Tree node classes. --- src/PIP_Problem.cc | 6 ++-- src/PIP_Problem.defs.hh | 2 +- src/PIP_Tree.cc | 40 ++++++++++++++++++++++++-- src/PIP_Tree.defs.hh | 71 +++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 109 insertions(+), 10 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index f1b4977..86777f5 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -85,9 +85,9 @@ PPL::PIP_Problem::solve() const { input_cs, parameters); - //FIXME: implement the simplex algorithm - - return_value = OPTIMIZED_PIP_PROBLEM; + Constraint_System initial_context; + return_value = x.current_solution->solve(&x.current_solution, + initial_context); switch (return_value) { case UNFEASIBLE_PIP_PROBLEM: diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index c1f69eb..58ebff5 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -322,7 +322,7 @@ private: dimension_type first_pending_constraint; /*! \brief - A set containing all the indexes of space dimensions that are + A set containing all the indices of space dimensions that are interpreted as problem parameters. */ Variables_Set parameters; diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index fc6e1db..db52260 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -79,19 +79,46 @@ PIP_Decision_Node::update_tableau(PIP_Tree_Node **parent_ref, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters) { - true_child->update_tableau(parent_ref, + true_child->update_tableau(&true_child, external_space_dim, first_pending_constraint, input_cs, parameters); if (false_child) - false_child->update_tableau(parent_ref, + false_child->update_tableau(&false_child, external_space_dim, first_pending_constraint, input_cs, parameters); } +PIP_Problem_Status +PIP_Decision_Node::solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) { + PIP_Problem_Status return_status; + PIP_Problem_Status stt; + PIP_Problem_Status stf = UNFEASIBLE_PIP_PROBLEM; + Constraint_System context_true(context); + //FIXME: not implemented yet (merging of constraint systems) + //context_true.merge(_constraints); + stt = true_child->solve(&true_child, context_true); + if (false_child) { + // Decision nodes with false child must have exactly one constraint + PPL_ASSERT(_constraints.num_rows() == 1); + Constraint_System context_false(context); + //FIXME: not implemented yet (constraint negation) + //context_false.insert(!_constraints[0]); + stf = false_child->solve(&false_child, context_false); + } + + if (stt == UNFEASIBLE_PIP_PROBLEM && stf == UNFEASIBLE_PIP_PROBLEM) { + return_status = UNFEASIBLE_PIP_PROBLEM; + *parent_ref = 0; + delete this; + return UNFEASIBLE_PIP_PROBLEM; + } + return OPTIMIZED_PIP_PROBLEM; +} void PIP_Solution_Node::Rational_Matrix::normalize() { @@ -153,8 +180,6 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, dimension_type i, j; dimension_type n_params = parameters.size(); dimension_type n_vars = external_space_dim - n_params; - dimension_type n_vars_int = tableau.s.num_columns(); - dimension_type n_constr_int = tableau.s.num_rows(); dimension_type internal_space_dim = tableau.t.num_columns()-1; Constraint_Sequence::const_iterator cst; @@ -218,4 +243,11 @@ PIP_Solution_Node::update_tableau(PIP_Tree_Node **parent_ref, // FIXME: decide emptiness detection (and node removal) } +PIP_Problem_Status +PIP_Solution_Node::solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) { + //FIXME + return OPTIMIZED_PIP_PROBLEM; +} + } // namespace Parma_Polyhedra_Library diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index bf46c8e..64debe6 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -89,6 +89,22 @@ protected: dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters) = 0; + + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context) = 0; }; //! A tree node representing part of the space of solutions. @@ -114,7 +130,14 @@ public: */ const Linear_Expression& parametric_values(Variable v); - //! Returns the constraints (on variables and parameters) of \p *this. + /*! \brief + Returns the system of parameter constraints controlling \p *this. + + The column indices in the constraints are numbered from \c 0 to + <tt>np-1</tt>, where \c np is the total number of parameters. They are + ordered with the same order as the parameter indices in the original + problem. + */ const Constraint_System& constraints(); void ascii_dump(std::ostream& s) const; @@ -200,6 +223,9 @@ private: */ std::vector<dimension_type> mapping; + //! The local system of parameter constraints + Constraint_System _constraints; + protected: /*! \brief Populates the parametric simplex tableau using external data, if necessary @@ -226,6 +252,21 @@ protected: const Constraint_Sequence &input_cs, const Variables_Set &parameters); + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context); // FIXME: constructors to be decided. }; @@ -247,7 +288,14 @@ public: //! Returns a pointer to the \p v (true or false) branch of \p *this. PIP_Tree_Node* child_node(bool v); - //! Returns the system of constraints controlling \p *this. + /*! \brief + Returns the system of parameter constraints controlling \p *this. + + The column indices in the constraints are numbered from \c 0 to + <tt>np-1</tt>, where \c np is the total number of parameters. They are + ordered with the same order as the parameter indices in the original + problem. + */ const Constraint_System& constraints(); private: @@ -257,6 +305,9 @@ private: //! Pointer to the "false" child of \p *this. PIP_Tree_Node* false_child; + //! The local system of parameter constraints + Constraint_System _constraints; + /*! \brief Constructs if \p cs then \p tcp \p else \p fcp. @@ -318,6 +369,22 @@ protected: dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters); + + /*! \brief + Execute a parametric simplex on the tableau, under specified context. + + \param parent_ref + a pointer to the parent reference to \p this + + \param context + the context, being a set of constraints on the parameters + + \return + An PIP_Problem_Status flag indicating the outcome of the optimization + attempt (unfeasible or optimized problem). + */ + virtual PIP_Problem_Status solve(PIP_Tree_Node **parent_ref, + const Constraint_System& context); }; typedef const PIP_Tree_Node* PIP_Tree;

1 0