February 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(pip): Improving test coverage ratio.
by Enea Zaffanella 07 Feb '10

07 Feb '10

Module: ppl/ppl Branch: pip Commit: 847a8a5f360d997af43c423a25e091ab747719fe URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=847a8a5f360d… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 6 17:16:05 2010 +0100 Improving test coverage ratio. --- tests/PIP_Problem/ascii_dump_load1.cc | 33 ++++++++ tests/PIP_Problem/exceptions1.cc | 143 +++++++++++++++++++++++++++++++++ tests/PIP_Problem/pipproblem1.cc | 34 ++++++++ 3 files changed, 210 insertions(+), 0 deletions(-) diff --git a/tests/PIP_Problem/ascii_dump_load1.cc b/tests/PIP_Problem/ascii_dump_load1.cc index 3ff394b..a89c8a1 100644 --- a/tests/PIP_Problem/ascii_dump_load1.cc +++ b/tests/PIP_Problem/ascii_dump_load1.cc @@ -143,6 +143,38 @@ test04() { return ok; } +bool +test05() { + const char* my_file = "ascii_dump_load1.dat"; + + Variable A(0); + Variable P(1); + Constraint_System cs; + cs.insert(A >= 1); + cs.insert(A <= 0); + + PIP_Problem pip1(2, cs.begin(), cs.end(), Variables_Set(P)); + pip1.set_control_parameter(PIP_Problem::CUTTING_STRATEGY_ALL); + pip1.set_big_parameter_dimension(1); + pip1.solve(); + + fstream f; + open(f, my_file, ios_base::out); + pip1.ascii_dump(f); + close(f); + + open(f, my_file, ios_base::in); + PIP_Problem pip2; + pip2.ascii_load(f); + close(f); + + bool ok = pip1.space_dimension() == pip2.space_dimension() + && 2 == std::distance(pip1.constraints_begin(), pip1.constraints_end()) + && 2 == std::distance(pip2.constraints_begin(), pip2.constraints_end()); + + return ok; +} + } // namespace BEGIN_MAIN @@ -150,4 +182,5 @@ BEGIN_MAIN DO_TEST(test02); DO_TEST(test03); DO_TEST(test04); + DO_TEST(test05); END_MAIN diff --git a/tests/PIP_Problem/exceptions1.cc b/tests/PIP_Problem/exceptions1.cc index c227c1f..5b27b09 100644 --- a/tests/PIP_Problem/exceptions1.cc +++ b/tests/PIP_Problem/exceptions1.cc @@ -121,6 +121,143 @@ test05() { return false; } +bool +test06() { + PIP_Problem pip; + try { + // Adding invalid parameter space dimensions. + Variable m(4); + pip.add_to_parameter_space_dimensions(Variables_Set(m)); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + +bool +test07() { + PIP_Problem pip; + try { + // Adding space dimension incompatible constraint. + Variable x(2); + pip.add_constraint(x >= 0); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + +bool +test08() { + PIP_Problem pip; + try { + // Setting an invalid control parameter value. + pip.set_control_parameter(PIP_Problem::CONTROL_PARAMETER_VALUE_SIZE); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + +bool +test09() { + Variable X1(0); + Variable X2(1); + Variable I0(2); + Variable J0(3); + Variable N(4); + Variables_Set params(I0, N); + + Constraint_System cs; + cs.insert(-X1 + N - 1 >= 0); + cs.insert(X1 - X2 >= 0); + cs.insert(X1 + I0 == N); + cs.insert(X2 + J0 - N - 1 >= 0); + cs.insert(I0 >= 1); + cs.insert(N >= 1); + + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + (void) pip.is_satisfiable(); + // Adding 2 additional space dimensions. + pip.add_space_dimensions_and_embed(2, 0); + + try { + // Trying to mark a problem variable as a parameter. + pip.add_to_parameter_space_dimensions(Variables_Set(X1)); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + +bool +test10() { + PIP_Problem pip; + + try { + // Trying to set an invalid big parameter dimension. + pip.set_big_parameter_dimension(1); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + +bool +test11() { + Variable X1(0); + Variable X2(1); + Variable I0(2); + Variable J0(3); + Variable N(4); + Variables_Set params(I0, N); + + Constraint_System cs; + cs.insert(-X1 + N - 1 >= 0); + cs.insert(X1 - X2 >= 0); + cs.insert(X1 + I0 == N); + cs.insert(X2 + J0 - N - 1 >= 0); + cs.insert(I0 >= 1); + cs.insert(N >= 1); + + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + (void) pip.is_satisfiable(); + // Adding 2 additional space dimensions. + pip.add_space_dimensions_and_embed(2, 0); + + try { + // Trying to set an invalid big parameter dimension. + pip.set_big_parameter_dimension(3); + } + catch (std::invalid_argument& e) { + nout << "invalid_argument: " << e.what() << endl << endl; + return true; + } + catch (...) { + } + return false; +} + } // namespace BEGIN_MAIN @@ -129,4 +266,10 @@ BEGIN_MAIN DO_TEST(test03); DO_TEST(test04); DO_TEST(test05); + DO_TEST(test06); + DO_TEST(test07); + DO_TEST(test08); + DO_TEST(test09); + DO_TEST(test10); + DO_TEST(test11); END_MAIN diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index a90ab9d..113ac3e 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -277,6 +277,39 @@ test07() { return ok; } +bool +test08() { + Variable i(0); + Variable j(1); + Variable m(2); + Variable n(3); + Variables_Set params(m, n); + + PIP_Problem pip(4); + pip.add_to_parameter_space_dimensions(params); + + Constraint_System cs; + cs.insert(3*j >= -2*i+8); + cs.insert(j <= 4*i - 4); + cs.insert(i <= n); + cs.insert(n >= 3); + cs.insert(j <= m); + + pip.add_constraints(cs); + + pip.set_control_parameter(PIP_Problem::PIVOT_ROW_STRATEGY_MAX_COLUMN); + + bool ok = pip.is_satisfiable(); + if (ok) { + const PIP_Tree solution = pip.optimizing_solution(); + display_solution(solution, params, Variables_Set(i, j), + pip.space_dimension()); + pip.clear(); + } + + return ok; +} + } // namespace BEGIN_MAIN @@ -287,4 +320,5 @@ BEGIN_MAIN DO_TEST(test05); DO_TEST(test06); DO_TEST(test07); + DO_TEST(test08); END_MAIN

1 0

[GIT] ppl/ppl(pip): Improved exception safety in method PIP_Solution_Node:: solve().
by Enea Zaffanella 06 Feb '10

06 Feb '10

Module: ppl/ppl Branch: pip Commit: 543d508d1069e2c910427abb8563c739c83adaf1 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=543d508d1069… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Feb 6 14:37:30 2010 +0100 Improved exception safety in method PIP_Solution_Node::solve(). --- src/PIP_Tree.cc | 50 +++++++++++++++++++++++++++++++------------------- 1 files changed, 31 insertions(+), 19 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b179e00..29cc047 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -25,6 +25,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "PIP_Problem.defs.hh" #include <algorithm> +#include <memory> namespace Parma_Polyhedra_Library { @@ -1882,26 +1883,28 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, #endif // #ifdef NOISY_PIP // Create a solution node for the "true" version of current node. - // FIXME: this is not exception safe. PIP_Tree_Node* t_node = new PIP_Solution_Node(*this, No_Constraints()); - context.add_row(t_test); + // Protect it from exception safety issues via std::auto_ptr. + std::auto_ptr<PIP_Tree_Node> wrapped_node(t_node); - // Recusively solve true node. + // Add parametric constraint to context. + context.add_row(t_test); + // Recusively solve true node wrt updated context. t_node = t_node->solve(problem, context, parameters, space_dim); - // Modify *this in place to become "false" version of current node. + // Modify *this in place to become the "false" version of current node. PIP_Tree_Node* f_node = this; // Swap aside constraints and artificial parameters - // (these could be later restored if needed). + // (these will be later restored if needed). Constraint_System cs; Artificial_Parameter_Sequence aps; - cs.swap(constraints_); - aps.swap(artificial_parameters); - // Negate the condition constraint used for the "true" node. + cs.swap(f_node->constraints_); + aps.swap(f_node->artificial_parameters); + // Compute the complement of the constraint used for the "true" node. Row& f_test = context[context.num_rows()-1]; complement_assign(f_test, t_test, 1); - // Recusively solve false node. + // Recusively solve false node wrt updated context. f_node = f_node->solve(problem, context, parameters, space_dim); // Case analysis on recursive resolution calls outcome. @@ -1912,13 +1915,13 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, } else { // t_node unfeasible, f_node feasible: - // restore cs and aps into *this. - constraints_.swap(cs); - artificial_parameters.swap(aps); - // Add f_test to constraints. - add_constraint(f_test, parameters); + // restore cs and aps into f_node (i.e., this). PPL_ASSERT(f_node == this); - return this; + f_node->constraints_.swap(cs); + f_node->artificial_parameters.swap(aps); + // Add f_test to constraints. + f_node->add_constraint(f_test, parameters); + return f_node; } } else if (f_node == 0) { @@ -1928,23 +1931,32 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, t_node->artificial_parameters.swap(aps); // Add t_test to t_nodes's constraints. t_node->add_constraint(t_test, parameters); - return t_node; + // It is now safe to release previously wrapped t_node pointer + // and return it to caller. + return wrapped_node.release(); } // Here both t_node and f_node are feasible: // create a new decision node. - // FIXME: this is not exception safe. - PIP_Decision_Node* parent = new PIP_Decision_Node(f_node, t_node); + PIP_Tree_Node* parent = new PIP_Decision_Node(f_node, t_node); + // Protect 'parent' from exception safety issues + // (previously wrapped t_node is now safe). + wrapped_node.release(); + wrapped_node = std::auto_ptr<PIP_Tree_Node>(parent); + + // Add t_test to the constraints of the new decision node. parent->add_constraint(t_test, parameters); if (!cs.empty()) { // If node to be solved had tautologies, // store them in a new decision node. - // FIXME: this is not exception safe. + // NOTE: this is exception safe. parent = new PIP_Decision_Node(0, parent); parent->constraints_.swap(cs); } parent->artificial_parameters.swap(aps); + // It is now safe to release previously wrapped decision node. + wrapped_node.release(); return parent; } // if (first_mixed != not_a_dim)

1 0

[GIT] ppl/ppl(pip): Clarified proper usage of PIP_Solution_Node alternative copy constructor.
by Enea Zaffanella 06 Feb '10

06 Feb '10

Module: ppl/ppl Branch: pip Commit: 51e0707e9e734ceb72382bf004e69a1076ec46c2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=51e0707e9e73… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 5 19:02:44 2010 +0100 Clarified proper usage of PIP_Solution_Node alternative copy constructor. The Boolean argument replaced by a tag struct type, since it was only used for overloading resolution purposes. --- src/PIP_Tree.cc | 8 ++------ src/PIP_Tree.defs.hh | 12 ++++++++---- 2 files changed, 10 insertions(+), 10 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index cb62db1..b179e00 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -365,7 +365,7 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node& y) } PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node& y, - bool empty_constraints) + No_Constraints) : PIP_Tree_Node(), tableau(y.tableau), basis(y.basis), @@ -377,10 +377,6 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node& y, sign(y.sign), solution(y.solution), solution_valid(y.solution_valid) { - if (!empty_constraints) { - constraints_ = y.constraints_; - artificial_parameters = y.artificial_parameters; - } } PIP_Decision_Node::PIP_Decision_Node(PIP_Tree_Node* fcp, @@ -1887,7 +1883,7 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, // Create a solution node for the "true" version of current node. // FIXME: this is not exception safe. - PIP_Tree_Node* t_node = new PIP_Solution_Node(*this, true); + PIP_Tree_Node* t_node = new PIP_Solution_Node(*this, No_Constraints()); context.add_row(t_test); // Recusively solve true node. diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 4190f55..b1a233f 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -514,11 +514,15 @@ protected: //! Copy constructor. PIP_Solution_Node(const PIP_Solution_Node& y); - /*! \brief - Copy constructor, allowing not to copy the constraint system and - artificial parameters + //! A tag type to select the alternative copy constructor. + struct No_Constraints {}; + + //! Alternative copy constructor. + /*! + This constructor differs from the default copy constructor in that + it will not copy the constraint system, nor the artificial parameters. */ - PIP_Solution_Node(const PIP_Solution_Node& y, bool empty_constraints); + PIP_Solution_Node(const PIP_Solution_Node& y, No_Constraints); /*! \brief Populates the parametric simplex tableau using external data, if necessary

1 0

[GIT] ppl/ppl(pip): Add new friend function add_mul_assign() for Linear_Expression.
by Enea Zaffanella 05 Feb '10

05 Feb '10

Module: ppl/ppl Branch: pip Commit: be3472f9d7b15cb7b31834a6f4e23a6fdd8bcf68 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=be3472f9d7b1… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 5 15:59:56 2010 +0100 Add new friend function add_mul_assign() for Linear_Expression. Used new function to optimize a couple of computations in PIP_Tree.cc. --- src/Linear_Expression.cc | 19 ++++++++++++++++++ src/Linear_Expression.defs.hh | 10 +++++++++ src/PIP_Tree.cc | 42 ++++++++++++++++++++++++++-------------- 3 files changed, 56 insertions(+), 15 deletions(-) diff --git a/src/Linear_Expression.cc b/src/Linear_Expression.cc index 4ffc709..f7d50a3 100644 --- a/src/Linear_Expression.cc +++ b/src/Linear_Expression.cc @@ -354,6 +354,25 @@ PPL::operator*=(Linear_Expression& e, Coefficient_traits::const_reference n) { return e; } +/*! \relates Parma_Polyhedra_Library::Linear_Expression */ +PPL::Linear_Expression& +PPL::add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, + const Variable v) { + const dimension_type v_space_dim = v.space_dimension(); + if (v_space_dim > Linear_Expression::max_space_dimension()) + throw std::length_error("Linear_Expression& " + "PPL::add_mul_assign(e, n, v):\n" + "v exceeds the maximum allowed space dimension."); + const dimension_type e_size = e.size(); + if (e_size <= v_space_dim) { + Linear_Expression new_e(e, v_space_dim+1); + e.swap(new_e); + } + e[v_space_dim] += n; + return e; +} + bool PPL::Linear_Expression::OK() const { return Linear_Row::OK(); diff --git a/src/Linear_Expression.defs.hh b/src/Linear_Expression.defs.hh index 2367c94..b4ce1e0 100644 --- a/src/Linear_Expression.defs.hh +++ b/src/Linear_Expression.defs.hh @@ -166,6 +166,12 @@ operator-=(Linear_Expression& e, Coefficient_traits::const_reference n); Linear_Expression& operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); +//! Returns the linear expression \p e + \p n * \p v and assigns it to \p e. +/*! \relates Linear_Expression */ +Linear_Expression& +add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, Variable v); + namespace IO_Operators { //! Output operator. @@ -451,6 +457,10 @@ private: friend Linear_Expression& operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); + friend Linear_Expression& + add_mul_assign(Linear_Expression& e, + Coefficient_traits::const_reference n, Variable v); + friend std::ostream& Parma_Polyhedra_Library::IO_Operators ::operator<<(std::ostream& s, const Linear_Expression& e); diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index c007c25..cb62db1 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -518,15 +518,21 @@ PIP_Tree_Node::OK() const { void PIP_Tree_Node ::add_constraint(const Row& row, const Variables_Set& parameters) { - const Variables_Set::const_iterator p_begin = parameters.begin(); - const Variables_Set::const_iterator p_end = parameters.end(); - PPL_ASSERT(static_cast<dimension_type>(std::distance(p_begin, p_end)) + 1 - == row.size()); - // FIXME: optimize the computation of expr. + const dimension_type num_params = parameters.size(); + PPL_ASSERT(num_params + 1 == row.size()); + + // Compute the expression for the parameter constraint. Linear_Expression expr = Linear_Expression(row[0]); - dimension_type j = 1; - for (Variables_Set::const_iterator pj = p_begin; pj != p_end; ++pj, ++j) - expr += row[j] * Variable(*pj); + // NOTE: iterating downward on parameters to avoid reallocations. + Variables_Set::const_reverse_iterator p_j = parameters.rbegin(); + // NOTE: index j spans [1..num_params] downwards. + for (dimension_type j = num_params; j > 0; --j) { + add_mul_assign(expr, row[j], Variable(*p_j)); + // Move to previous parameter. + ++p_j; + } + + // Add the parameter constraint. constraints_.insert(expr >= 0); } @@ -1723,8 +1729,6 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, } // Compute columns t[*][j] : - // t[i][j] -= t[i][pj] * t_pivot[j] / s_pivot_pj; - // ENEA: FIXME: according to code below, this comment should read: // t[i][j] -= s[i][pj] * t_pivot[j] / s_pivot_pj; for (dimension_type j = num_params; j-- > 0; ) { const Coefficient& t_pivot_j = t_pivot[j]; @@ -2094,6 +2098,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index, const Coefficient& den = tableau.get_denominator(); PPL_DIRTY_TEMP_COEFFICIENT(mod); + PPL_DIRTY_TEMP_COEFFICIENT(coeff); #ifdef NOISY_PIP std::cout << "Row " << index << " contains non-integer coefficients. " @@ -2125,15 +2130,22 @@ PIP_Solution_Node::generate_cut(const dimension_type index, mod_assign(mod, row_t[0], den); Linear_Expression expr; if (mod != 0) { + // Optimizing computation: expr += (den - mod); expr += den; expr -= mod; } - Variables_Set::const_iterator p = parameters.begin(); - for (dimension_type j = 1; j < num_params; ++j, ++p) { + // NOTE: iterating downwards on parameters to avoid reallocations. + Variables_Set::const_reverse_iterator p_j = parameters.rbegin(); + // NOTE: index j spans [1..num_params-1] downwards. + for (dimension_type j = num_params; j-- > 1; ) { mod_assign(mod, row_t[j], den); - // FIXME: find a way to optimize the following. - if (mod != 0) - expr += (den - mod) * Variable(*p); + if (mod != 0) { + // Optimizing computation: expr += (den - mod) * Variable(*p_j); + coeff = den - mod; + add_mul_assign(expr, coeff, Variable(*p_j)); + } + // Mode to previous parameter. + ++p_j; } // Generate new artificial parameter. Artificial_Parameter ap(expr, den);

1 0

[GIT] ppl/ppl(pip): Helper function negate_assign() rnamed as complement_assign().
by Enea Zaffanella 05 Feb '10

05 Feb '10

Module: ppl/ppl Branch: pip Commit: 8b91cc59d73c37b101cd4a24e7a4c983667ae0d7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8b91cc59d73c… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 5 14:52:15 2010 +0100 Helper function negate_assign() rnamed as complement_assign(). --- src/PIP_Tree.cc | 24 +++++++++++++++--------- 1 files changed, 15 insertions(+), 9 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index d85e325..c007c25 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -93,15 +93,21 @@ neg_assign_row(Row& x, const Row& y) { neg_assign(x[i], y[i]); } -// FIXME: find better name and improve comment. -// Tranform expression "expr" into "-expr-1", using scaling +// Given context row \p y and denominator \p den, +// to be interpreted as expression expr = y / den, +// assigns to context row \p x a new value such that +// x / den == - expr - 1. inline void -negate_assign(Row& x, const Row& y, Coefficient_traits::const_reference sc) { +complement_assign(Row& x, const Row& y, + Coefficient_traits::const_reference den) { + PPL_ASSERT(den > 0); neg_assign_row(x, y); - if (sc != 0) { + if (den == 1) + --x[0]; + else { PPL_DIRTY_TEMP_COEFFICIENT(mod); - mod_assign(mod, x[0], sc); - x[0] -= ((mod == 0) ? sc : mod); + mod_assign(mod, x[0], den); + x[0] -= (mod == 0) ? den : mod; } } @@ -664,7 +670,7 @@ PIP_Decision_Node::solve(const PIP_Problem& problem, update_context(context_false, artificial_parameters); merge_assign(context_false, constraints_, parameters); Row& last = context_false[context_false.num_rows()-1]; - negate_assign(last, last, 1); + complement_assign(last, last, 1); false_child = false_child->solve(problem, context_false, parameters, space_dimension); } @@ -1543,7 +1549,7 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, // Check compatibility for constraint t_i(z) < 0, // i.e., -t_i(z) - 1 >= 0. Row c(num_params, Row::Flags()); - negate_assign(c, t_i, tableau_den); + complement_assign(c, t_i, tableau_den); if (compatibility_check(context, c)) new_sign = (new_sign == POSITIVE) ? MIXED : NEGATIVE; // Update sign for parameter row i. @@ -1893,7 +1899,7 @@ PIP_Solution_Node::solve(const PIP_Problem& problem, aps.swap(artificial_parameters); // Negate the condition constraint used for the "true" node. Row& f_test = context[context.num_rows()-1]; - negate_assign(f_test, t_test, 1); + complement_assign(f_test, t_test, 1); // Recusively solve false node. f_node = f_node->solve(problem, context, parameters, space_dim);

1 0

[GIT] ppl/ppl(pip): Simplified interface for virtual method PIP_Tree_Node:: solve().
by Enea Zaffanella 05 Feb '10

05 Feb '10

Module: ppl/ppl Branch: pip Commit: 2cf07608658891e0916de858fc519a082fed02c3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2cf076086588… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Feb 5 14:05:42 2010 +0100 Simplified interface for virtual method PIP_Tree_Node::solve(). No longer using the PIP_Tree_Node*& parent_ref argument and direclty returning the solution PIP_Tree_Node* instead of a status flag. --- src/PIP_Problem.cc | 23 ++++++---------- src/PIP_Tree.cc | 60 ++++++++++++++++++------------------------- src/PIP_Tree.defs.hh | 69 ++++++++++++++++++++----------------------------- 3 files changed, 62 insertions(+), 90 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=2cf07608…

1 0

[GIT] ppl/w3ppl(master): Added TrifunovicCEFG+10.
by Roberto Bagnara 05 Feb '10

05 Feb '10

Module: ppl/w3ppl Branch: master Commit: 49e60ed4ff338a1dc9873feb198d0378d36dfcc9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=49e60ed4ff… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Feb 5 09:09:24 2010 +0100 Added TrifunovicCEFG+10. --- htdocs/Documentation/ppl_citations.bib | 32 ++++++++++++++++++++++++++++++++ 1 files changed, 32 insertions(+), 0 deletions(-) diff --git a/htdocs/Documentation/ppl_citations.bib b/htdocs/Documentation/ppl_citations.bib index 2dab641..a83eb79 100644 --- a/htdocs/Documentation/ppl_citations.bib +++ b/htdocs/Documentation/ppl_citations.bib @@ -2553,6 +2553,38 @@ parameter valuations that satisfy the formulae." } +@Inproceedings{TrifunovicCEFG+10, + Author = "K. Trifunovic and A. Cohen and D. Edelsohn and L. Feng + and T. Grosser and H. Jagasia and R. Ladelsky and S. Pop + and J. Sj{\"o}din and R. Upadrasta", + Title = "{GRAPHITE} Two Years After: + First Lessons Learned From Real-World Polyhedral Compilation", + Booktitle = "Proceedings of the 2nd International Workshop on + GCC Research Opportunities (GROW'10)", + Address = "Pisa, Italy", + Year = 2010, + Pages = "4--19", + Abstract = "Modern compilers are responsible for adapting the + semantics of source programs into a form that makes + efficient use of a highly complex, heterogeneous + machine. This adaptation amounts to solve an + optimization problem in a huge and unstructured search + space, while predicting the performance outcome of + complex sequences of program transformations. The + polyhedral model of compilation is aimed at these + challenges. Its geometrical, non-inductive semantics + enables the construction of better-structured + optimization problems and precise analytical + models. Recent work demonstrated the scalability of the + main polyhedral algorithms to real-world programs. Its + integration into production compilers is under way, + pioneered by the graphite branch of the GNU Compiler + Collection (GCC). Two years after the effective + beginning of the project, this paper reports on original + questions and innovative solutions that arose during the + design and implementation of \textsc{graphite}." +} + @Techreport{UchoaFLPPdAA06TR, Author = "E. Uchoa and R. Fukasawa and J. Lysgaard and A. Pessoa and M. {Poggi de Arag\~ao} and D. Andrade",

1 0

[GIT] ppl/ppl(pip): Improved class PIP_Tree_Node::Artificial_Parameter.
by Enea Zaffanella 04 Feb '10

04 Feb '10

Module: ppl/ppl Branch: pip Commit: d7ab70ac7775d4c05233236d54e3387d6286d6bf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d7ab70ac7775… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Feb 4 16:39:39 2010 +0100 Improved class PIP_Tree_Node::Artificial_Parameter. --- src/PIP_Tree.cc | 13 +++++-- src/PIP_Tree.defs.hh | 93 ++++++++++++++++++++++++++++++++--------------- src/PIP_Tree.inlines.hh | 15 ++++++-- 3 files changed, 84 insertions(+), 37 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 1194450..423ab70 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -300,23 +300,28 @@ operator==(const PIP_Tree_Node::Artificial_Parameter& x, void PIP_Tree_Node::Artificial_Parameter::ascii_dump(std::ostream& s) const { - s << "\ndenominator " << denominator << "\n"; + s << "artificial_parameter "; Linear_Expression::ascii_dump(s); + s << " / " << denominator << "\n"; } bool PIP_Tree_Node::Artificial_Parameter::ascii_load(std::istream& s) { std::string str; - if (!(s >> str) || str != "denominator") - return false; - if (!(s >> denominator)) + if (!(s >> str) || str != "artificial_parameter") return false; if (!Linear_Expression::ascii_load(s)) return false; + if (!(s >> str) || str != "/") + return false; + if (!(s >> denominator)) + return false; PPL_ASSERT(OK()); return true; } +PPL_OUTPUT_DEFINITIONS(PIP_Tree_Node::Artificial_Parameter) + PIP_Decision_Node::~PIP_Decision_Node() { delete true_child; delete false_child; diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 9c9f412..6bfa57d 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -79,36 +79,7 @@ public: */ const Constraint_System& constraints() const; - /*! \brief - A class to store the expession of artificial parameters in solution trees. - - These locally new parameters are of the form of the integer division of a - linear expression of the other parameters (constant term included), by a - coefficient. Coefficients at indexes corresponding to variables always are - zero. - */ - class Artificial_Parameter : public Linear_Expression { - public: - Artificial_Parameter(); - Artificial_Parameter(const Linear_Expression& e, - Coefficient_traits::const_reference d); - Artificial_Parameter(const Artificial_Parameter& y); - - Coefficient_traits::const_reference get_denominator() const; - - //! Returns \b true if \p x and \p y are equal. - friend bool operator==(const Artificial_Parameter& x, - const Artificial_Parameter& y); - - void ascii_dump(std::ostream& s) const; - bool ascii_load(std::istream& s); - - //! Returns \c true if and only if the parameter is well-formed. - bool OK() const; - - private: - Coefficient denominator; - }; // class Artificial_Parameter + class Artificial_Parameter; //! A type alias for a sequence of Artificial_Parameter's. typedef std::vector<Artificial_Parameter> Artificial_Parameter_Sequence; @@ -232,6 +203,68 @@ protected: }; // class PIP_Tree_Node +/*! \brief + Artificial parameters in PIP solution trees. + + These parameters are built from a linear expression combining other + parameters (constant term included) divided by a positive integer + denominator. Coefficients at variables indices corresponding to + PIP problem variables are always zero. +*/ +class PIP_Tree_Node::Artificial_Parameter + : public Linear_Expression { +public: + //! Default constructor: builds a zero artificial parameter. + Artificial_Parameter(); + + //! Constructor. + /*! + Builds artificial parameter \f$\frac{\mathit{expr}}{\mathit{den}}\f$. + + \param expr + The expression that, after normalization, will form the numerator of + the artificial parameter. + + \param den + The integer constant thatm after normalization, will form the + denominator of the artificial parameter. + + \exception std::invalid_argument + Thrown if \p den is zero. + + Normalization will ensure that the denominator is positive. + */ + Artificial_Parameter(const Linear_Expression& expr, + Coefficient_traits::const_reference den); + + //! Copy constructor. + Artificial_Parameter(const Artificial_Parameter& y); + + //! Returns the normalized (i.e., positive) denominator. + Coefficient_traits::const_reference get_denominator() const; + + //! Returns \b true if \p x and \p y are equal. + friend bool operator==(const Artificial_Parameter& x, + const Artificial_Parameter& y); + + PPL_OUTPUT_DECLARATIONS + + /*! \brief + Loads from \p s an ASCII representation (as produced by + ascii_dump(std::ostream&) const) and sets \p *this accordingly. + Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. + */ + bool ascii_load(std::istream& s); + + //! Returns \c true if and only if the parameter is well-formed. + bool OK() const; + +private: + //! The normalized (i.e., positive) denominator. + Coefficient denominator; +}; // class PIP_Tree_Node::Artificial_Parameter + + //! A tree node representing part of the space of solutions. class PIP_Solution_Node : public PIP_Tree_Node { public: diff --git a/src/PIP_Tree.inlines.hh b/src/PIP_Tree.inlines.hh index 2ea2d93..6544e59 100644 --- a/src/PIP_Tree.inlines.hh +++ b/src/PIP_Tree.inlines.hh @@ -118,9 +118,18 @@ PIP_Tree_Node::Artificial_Parameter::Artificial_Parameter() inline PIP_Tree_Node::Artificial_Parameter -::Artificial_Parameter(const Linear_Expression &e, - Coefficient_traits::const_reference d) - : Linear_Expression(e), denominator(d) { +::Artificial_Parameter(const Linear_Expression& expr, + Coefficient_traits::const_reference den) + : Linear_Expression(expr), denominator(den) { + if (denominator == 0) + throw std::invalid_argument("PIP_Tree_Node::Artificial_Parameter(e, d): " + "denominator d is zero."); + // Normalize if needed. + if (denominator < 0) { + neg_assign(denominator); + Linear_Expression& expr = *this; + expr *= -1; + } PPL_ASSERT(OK()); }

1 0

[GIT] ppl/ppl(pip): Some improvements to method PIP_Problem::solve().
by Enea Zaffanella 04 Feb '10

04 Feb '10

Module: ppl/ppl Branch: pip Commit: ecd41d0c27ce3afc1312114df44c33d0038f81e3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ecd41d0c27ce… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Feb 4 10:54:27 2010 +0100 Some improvements to method PIP_Problem::solve(). --- src/PIP_Problem.cc | 94 ++++++++++++++++++++++++++++++---------------------- 1 files changed, 54 insertions(+), 40 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 0e48871..720613b 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -88,17 +88,18 @@ PPL::PIP_Problem::control_parameters_copy(const PIP_Problem& y) { PPL::PIP_Problem_Status PPL::PIP_Problem::solve() const { switch (status) { + case UNSATISFIABLE: PPL_ASSERT(OK()); return UNFEASIBLE_PIP_PROBLEM; + case OPTIMIZED: PPL_ASSERT(OK()); return OPTIMIZED_PIP_PROBLEM; + case PARTIALLY_SATISFIABLE: { PIP_Problem& x = const_cast<PIP_Problem&>(*this); - PIP_Problem_Status return_value; - if (current_solution == 0) x.current_solution = new PIP_Solution_Node(); if (input_cs.empty()) { @@ -107,50 +108,59 @@ PPL::PIP_Problem::solve() const { return OPTIMIZED_PIP_PROBLEM; } - // Look for constraints with only parameter coefficients. - const Constraint_Sequence::const_iterator c_begin = input_cs.begin(); - const Constraint_Sequence::const_iterator c_end = input_cs.end(); - Constraint_Sequence::const_iterator c; + // Properly resize context matrix. + const dimension_type num_params = parameters.size() + 1; + const dimension_type num_cols = initial_context.num_columns(); + if (num_cols < num_params) + x.initial_context.add_zero_columns(num_params - num_cols); + + // Computed once for all (to be used inside loop). const Variables_Set::iterator param_begin = parameters.begin(); const Variables_Set::iterator param_end = parameters.end(); - Variables_Set::iterator pi; - dimension_type i; - // Resize context matrix properly. - dimension_type num_params = parameters.size() + 1; - dimension_type num_cols = initial_context.num_columns(); - if (num_cols < num_params) - x.initial_context.add_zero_columns(num_params - num_cols); + // Go through all pending constraints. + for (Constraint_Sequence::const_iterator + cs_i = input_cs.begin() + first_pending_constraint, + cs_end = input_cs.end(); cs_i != cs_end; ++cs_i) { + const Constraint& c = *cs_i; + const dimension_type c_space_dim = c.space_dimension(); + PPL_ASSERT(external_space_dim >= c_space_dim); - for (c = c_begin + first_pending_constraint; c != c_end; ++c) { - const dimension_type c_space_dim = c->space_dimension(); - if (external_space_dim < c_space_dim) - x.external_space_dim = c_space_dim; + // Check if constraint has a non-zero variable coefficient. bool has_nonzero_variable_coefficient = false; - for (i = 0; i < c_space_dim; ++i) { - if (c->coefficient(Variable(i)) != 0 && parameters.count(i) == 0) { - /* Constraint should not be inserted in context. */ + for (dimension_type i = c_space_dim; i-- > 0; ) { + if (c.coefficient(Variable(i)) != 0 + && parameters.count(i) == 0) { has_nonzero_variable_coefficient = true; break; } } - if (!has_nonzero_variable_coefficient) { - // At this point, the constraint must be translated into context row. - Row row(num_params, Row::Flags()); - for (pi = param_begin, i = 1; pi != param_end; ++pi, ++i) - row[i] = c->coefficient(Variable(*pi)); - row[0] = c->inhomogeneous_term(); - if (c->is_strict_inequality()) - --row[0]; + // Constraints having a non-zero variable coefficient + // should not be inserted in context. + if (has_nonzero_variable_coefficient) + continue; + + // Translate constraint into context row. + Row row(num_params, Row::Flags()); + row[0] = c.inhomogeneous_term(); + dimension_type i = 1; + for (Variables_Set::iterator + pi = param_begin; pi != param_end; ++pi, ++i) + row[i] = c.coefficient(Variable(*pi)); + // Adjust inhomogenous term if strict. + if (c.is_strict_inequality()) + --row[0]; + // Insert new row into context. + x.initial_context.add_row(row); + // If it is an equality, also insert its negation. + if (c.is_equality()) { + for (dimension_type i = num_params; i-- > 0; ) + neg_assign(row[i], row[i]); x.initial_context.add_row(row); - if (c->is_equality()) { - for (i = 0; i < num_params; ++i) - row[i] = -row[i]; - x.initial_context.add_row(row); - } } } + // Update tableau and mark constraints as no longer pending. x.current_solution->update_tableau(*this, external_space_dim, first_pending_constraint, @@ -159,11 +169,13 @@ PPL::PIP_Problem::solve() const { x.internal_space_dim = external_space_dim; x.first_pending_constraint = input_cs.size(); - return_value = x.current_solution->solve(x.current_solution, - *this, - initial_context, parameters, - external_space_dim); - + // Actually solve problem. + PIP_Problem_Status return_value + = x.current_solution->solve(x.current_solution, + *this, + initial_context, parameters, + external_space_dim); + // Update problem status. switch (return_value) { case UNFEASIBLE_PIP_PROBLEM: x.status = UNSATISFIABLE; @@ -174,8 +186,10 @@ PPL::PIP_Problem::solve() const { } PPL_ASSERT(OK()); return return_value; - } - } + } // End of handler for PARTIALLY_SATISFIABLE case. + + } // End of switch. + // We should not be here! throw std::runtime_error("PPL internal error"); }

1 0

[GIT] ppl/ppl(pip): Improved the last part of method PIP_Solution_Node:: solve().
by Enea Zaffanella 03 Feb '10

03 Feb '10

Module: ppl/ppl Branch: pip Commit: 8fe9538a0dade2eed5ef50bab52f76339f9476b0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8fe9538a0dad… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Wed Feb 3 19:00:36 2010 +0100 Improved the last part of method PIP_Solution_Node::solve(). --- src/PIP_Tree.cc | 126 ++++++++++++++++++++++++++++--------------------------- 1 files changed, 64 insertions(+), 62 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 0a7eec8..1194450 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1959,119 +1959,121 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, #endif tableau.normalize(); - // Look for a row with non integer parameter coefficients (first is okay) - const Coefficient& d = tableau.get_denominator(); - dimension_type i; - for (i = 0; i < num_vars; ++i) { - if (basis[i]) - // basic variable = 0 -> integer + // Look for any row having non integer parameter coefficients. + const Coefficient& den = tableau.get_denominator(); + for (dimension_type k = 0; k < num_vars; ++k) { + if (basis[k]) + // Basic variable = 0, hence integer. continue; - const Row& row = tableau.t[mapping[i]]; - for (dimension_type j = 0; j < num_params; ++j) { - if (row[j] % d != 0) - goto endsearch; + const dimension_type i = mapping[k]; + const Row& t_i = tableau.t[i]; + for (dimension_type j = num_params; j-- > 0; ) { + if (t_i[j] % den != 0) + goto non_integer; } } - endsearch: - - if (i == num_vars) { - /* The solution is integer */ + // The goto was not taken, the solution is integer. #ifdef NOISY_PIP - std::cout << "Solution found for problem in current node." - << std::endl; + std::cout << "Solution found for problem in current node.\n"; #endif - return OPTIMIZED_PIP_PROBLEM; - } - /* The solution is non-integer. We have to generate a cut. */ + return OPTIMIZED_PIP_PROBLEM; + + non_integer: + // The solution is non-integer: generate a cut. PPL_DIRTY_TEMP_COEFFICIENT(mod); + dimension_type best_i = not_a_dim; + dimension_type best_pcount = not_a_dim; + const PIP_Problem::Control_Parameter_Value cutting_strategy = problem.control_parameters[PIP_Problem::CUTTING_STRATEGY]; + if (cutting_strategy == PIP_Problem::CUTTING_STRATEGY_FIRST) { // Find the first row with simplest parametric part. - dimension_type best_i = not_a_dim; - dimension_type best_pcount = not_a_dim; - dimension_type pcount; for (dimension_type k = 0; k < num_vars; ++k) { if (basis[k]) continue; - i = mapping[k]; - const Row& row_t = tableau.t[i]; - pcount = 0; - for (dimension_type j = 0; j < num_params; ++j) { - mod_assign(mod, row_t[j], d); + const dimension_type i = mapping[k]; + const Row& t_i = tableau.t[i]; + // Count the number of non-integer parameter coefficients. + dimension_type pcount = 0; + for (dimension_type j = num_params; j-- > 0; ) { + mod_assign(mod, t_i[j], den); if (mod != 0) ++pcount; } - if (pcount != 0 && (best_i == not_a_dim || (pcount < best_pcount))) { + if (pcount > 0 && (best_i == not_a_dim || pcount < best_pcount)) { best_pcount = pcount; best_i = i; } } + // Generate cut using 'best_i'. generate_cut(best_i, parameters, context, space_dim); } else { assert(cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST || cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL); - /* Find the row with simplest parametric part which will generate - the "deepest" cut */ - PPL_DIRTY_TEMP_COEFFICIENT(score); - PPL_DIRTY_TEMP_COEFFICIENT(score2); + // Find the row with simplest parametric part + // which will generate the "deepest" cut. PPL_DIRTY_TEMP_COEFFICIENT(best_score); best_score = 0; - dimension_type best_i = not_a_dim; - dimension_type best_pcount = not_a_dim; - dimension_type pcount; + PPL_DIRTY_TEMP_COEFFICIENT(score); + PPL_DIRTY_TEMP_COEFFICIENT(s_score); std::vector<dimension_type> all_best_is; + for (dimension_type k = 0; k < num_vars; ++k) { if (basis[k]) continue; - i = mapping[k]; - const Row& row_t = tableau.t[i]; - const Row& row_s = tableau.s[i]; + const dimension_type i = mapping[k]; + // Compute score and pcount. score = 0; - pcount = 0; - for (dimension_type j = 0; j < num_params; ++j) { - mod_assign(mod, row_t[j], d); + dimension_type pcount = 0; + const Row& t_i = tableau.t[i]; + for (dimension_type j = num_params; j-- > 0; ) { + mod_assign(mod, t_i[j], den); if (mod != 0) { - score += d - mod; + score += den; + score -= mod; ++pcount; } } - score2 = 0; - for (dimension_type j = 0; j < num_vars; ++j) { - mod_assign(mod, row_s[j], d); - score2 += d - mod; + // Compute s_score. + s_score = 0; + const Row& s_i = tableau.s[i]; + for (dimension_type j = num_vars; j-- > 0; ) { + mod_assign(mod, s_i[j], den); + s_score += den; + s_score -= mod; } - score *= score2; - /* Choose row i if: - row i is non-integer - AND (no row has been chosen yet - OR row i has number of non-integer parameter - coefficients lower than the current best row - OR row i has the same number of non-integer parameter - coefficients as the current best row, and its score is - better) + // Combine 'score' and 's_score'. + score *= s_score; + /* + Select row i if it is non integer AND + - no row has been chosen yet; OR + - it has fewer non-integer parameter coefficients; OR + - it has the same number of non-integer parameter coefficients, + but its score is greater. */ if (pcount != 0 && (best_i == not_a_dim - || (pcount < best_pcount) + || pcount < best_pcount || (pcount == best_pcount && score > best_score))) { if (pcount < best_pcount) all_best_is.clear(); - best_score = score; - best_pcount = pcount; best_i = i; + best_pcount = pcount; + best_score = score; } if (pcount > 0) all_best_is.push_back(i); } if (cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST) generate_cut(best_i, parameters, context, space_dim); - else /* cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL */ { - for (i = all_best_is.size(); i-- > 0; ) - generate_cut(all_best_is[i], parameters, context, space_dim); + else { + PPL_ASSERT(cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL); + for (dimension_type k = all_best_is.size(); k-- > 0; ) + generate_cut(all_best_is[k], parameters, context, space_dim); } - } + } // End of processing for non-integer solutions. } // Main loop of the simplex algorithm

1 0