March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Made a pass on the documentation of class PIP_Problem.
by Enea Zaffanella 02 Mar '10

02 Mar '10

Module: ppl/ppl Branch: master Commit: 6503e77440bc1ab0482fa58fcd6fad7043d01cbf URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6503e77440bc… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Mar 2 14:59:10 2010 +0100 Made a pass on the documentation of class PIP_Problem. --- interfaces/C/ppl_c_header.h | 13 +++ src/PIP_Problem.defs.hh | 200 ++++++++++++++++++++++++++----------------- 2 files changed, 135 insertions(+), 78 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=6503e774…

1 0

[GIT] ppl/ppl(master): Method PIP_Tree_Node::solve() now checks context feasibility when needed.
by Enea Zaffanella 02 Mar '10

02 Mar '10

Module: ppl/ppl Branch: master Commit: 802e03131e75ff1962b42a6b071afca7cdf65b85 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=802e03131e75… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Mar 1 23:58:07 2010 +0100 Method PIP_Tree_Node::solve() now checks context feasibility when needed. --- src/PIP_Problem.cc | 1 + src/PIP_Tree.cc | 24 ++++++++++++++++++++---- src/PIP_Tree.defs.hh | 7 +++++++ 3 files changed, 28 insertions(+), 4 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 953ed23..1acb759 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -207,6 +207,7 @@ PPL::PIP_Problem::solve() const { // Actually solve problem. x.current_solution = x.current_solution->solve(*this, + check_feasible_context, initial_context, parameters, external_space_dim); diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 5a0aafd..45427ae 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -678,6 +678,7 @@ PIP_Decision_Node::update_tableau(const PIP_Problem& pip, PIP_Tree_Node* PIP_Decision_Node::solve(const PIP_Problem& pip, + const bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim) { @@ -688,7 +689,8 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, add_artificial_parameters(context_true, all_params, space_dim, num_art_params); merge_assign(context_true, constraints_, all_params); - true_child = true_child->solve(pip, context_true, all_params, space_dim); + true_child = true_child->solve(pip, check_feasible_context, + context_true, all_params, space_dim); if (false_child) { // Decision nodes with false child must have exactly one constraint @@ -697,7 +699,8 @@ PIP_Decision_Node::solve(const PIP_Problem& pip, Matrix& context_false = context_true; Row& last = context_false[context_false.num_rows()-1]; complement_assign(last, last, 1); - false_child = false_child->solve(pip, context_false, all_params, space_dim); + false_child = false_child->solve(pip, check_feasible_context, + context_false, all_params, space_dim); } if (true_child != 0 || false_child != 0) { @@ -1603,6 +1606,7 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& pip, PIP_Tree_Node* PIP_Solution_Node::solve(const PIP_Problem& pip, + const bool check_feasible_context, const Matrix& ctx, const Variables_Set& params, dimension_type space_dim) { @@ -1614,6 +1618,16 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, const dimension_type num_art_params = artificial_parameters.size(); add_artificial_parameters(context, all_params, space_dim, num_art_params); merge_assign(context, constraints_, all_params); + + // If needed, (re-)check feasibility of context. + if (check_feasible_context) { + Matrix ctx_copy(context); + if (!compatibility_check(ctx_copy)) { + delete this; + return 0; + } + } + const dimension_type not_a_dim = not_a_dimension(); // Main loop of the simplex algorithm. @@ -2001,7 +2015,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, // Add parametric constraint to context. context.add_row(t_test); // Recusively solve true node wrt updated context. - t_node = t_node->solve(pip, context, all_params, space_dim); + t_node = t_node->solve(pip, check_feasible_context, + context, all_params, space_dim); // Modify *this in place to become the "false" version of current node. PIP_Tree_Node* f_node = this; @@ -2016,7 +2031,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, complement_assign(f_test, t_test, 1); // Recusively solve false node wrt updated context. - f_node = f_node->solve(pip, context, all_params, space_dim); + f_node = f_node->solve(pip, check_feasible_context, + context, all_params, space_dim); // Case analysis on recursive resolution calls outcome. if (t_node == 0) { diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 54fcde9..ef6e23a 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -190,6 +190,10 @@ protected: \param pip The PIP_Problem object containing this node. + \param check_feasible_context + Whether the resolution process should (re-)check feasibility of + context (since the initial context may have been modified). + \param context The context, being a set of constraints on the parameters. @@ -200,6 +204,7 @@ protected: The space dimension of parent, including artificial parameters. */ virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim) = 0; @@ -632,6 +637,7 @@ protected: //! Implements pure virtual method PIP_Tree_Node::solve. virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim); @@ -765,6 +771,7 @@ protected: //! Implements pure virtual method PIP_Tree_Node::solve. virtual PIP_Tree_Node* solve(const PIP_Problem& pip, + bool check_feasible_context, const Matrix& context, const Variables_Set& params, dimension_type space_dim);

1 0

[GIT] ppl/ppl(master): Corrected typo in test19().
by Enea Zaffanella 02 Mar '10

02 Mar '10

Module: ppl/ppl Branch: master Commit: 893ad34ee7a5e376f94cd8ef7a49168c30021dd7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=893ad34ee7a5… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Mar 1 23:57:03 2010 +0100 Corrected typo in test19(). --- tests/PIP_Problem/pipproblem1.cc | 5 ++--- 1 files changed, 2 insertions(+), 3 deletions(-) diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index ed1783d..b10b076 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -545,7 +545,6 @@ test19() { cs.insert(3*j >= -2*i+8); cs.insert(j <= 4*i - 4); cs.insert(j <= m); - //cs.insert(j >= 0); cs.insert(i <= n); PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); @@ -557,7 +556,7 @@ test19() { pip.print_solution(nout); } - cs.insert(n <= 1); + pip.add_constraint(n <= 1); ok &= (pip.solve() == UNFEASIBLE_PIP_PROBLEM); return ok; @@ -584,5 +583,5 @@ BEGIN_MAIN DO_TEST(test16); DO_TEST(test17); DO_TEST(test18); - DO_TEST_F(test19); + DO_TEST_F8(test19); END_MAIN

1 0

[GIT] ppl/ppl(master): Several minor improvements to the PIP_Problem resolution process.
by Enea Zaffanella 02 Mar '10

02 Mar '10

Module: ppl/ppl Branch: master Commit: 8daf23edd9ad7af29aa77ca72740ffe7a95f05ec URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8daf23edd9ad… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Mar 1 23:43:41 2010 +0100 Several minor improvements to the PIP_Problem resolution process. Reorganized helper functions update_context() and compatibility_check(). --- src/PIP_Problem.cc | 43 +++++++------- src/PIP_Tree.cc | 151 ++++++++++++++++++++++++++----------------------- src/PIP_Tree.defs.hh | 152 +++++++++++++------------------------------------- 3 files changed, 142 insertions(+), 204 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=8daf23ed…

1 0

[GIT] ppl/ppl(master): The wrap_assign has only been added to the C interface
by Patricia Hill 01 Mar '10

01 Mar '10

Module: ppl/ppl Branch: master Commit: 90f18fa7da955d2a811e70d8927ba7c283205e7b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=90f18fa7da95… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon Mar 1 11:05:37 2010 +0000 The wrap_assign has only been added to the C interface so the procedure must be local to the C interface. --- ...l_interface_generator_c_procedure_generators.m4 | 1 + ...erface_generator_common_procedure_generators.m4 | 1 - 2 files changed, 1 insertions(+), 1 deletions(-) diff --git a/interfaces/C/ppl_interface_generator_c_procedure_generators.m4 b/interfaces/C/ppl_interface_generator_c_procedure_generators.m4 index fde20b3..9aa2a19 100644 --- a/interfaces/C/ppl_interface_generator_c_procedure_generators.m4 +++ b/interfaces/C/ppl_interface_generator_c_procedure_generators.m4 @@ -43,5 +43,6 @@ m4_define(`m4_procedure_list', ppl_new_@TOPOLOGY@@CLASS@_recycle_@BUILD_REPRESENT@s +simple, ppl_assign_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@ +simple, ppl_@CLASS@_add_recycled_@CLASS_REPRESENT@s +simple, +ppl_@CLASS@_wrap_assign +simple, ) ') diff --git a/interfaces/ppl_interface_generator_common_procedure_generators.m4 b/interfaces/ppl_interface_generator_common_procedure_generators.m4 index 32ea300..a6242ce 100644 --- a/interfaces/ppl_interface_generator_common_procedure_generators.m4 +++ b/interfaces/ppl_interface_generator_common_procedure_generators.m4 @@ -91,7 +91,6 @@ ppl_@CLASS@_fold_space_dimensions/3 +all, ppl_@CLASS@_map_space_dimensions/2 +all, ppl_@CLASS@_ascii_dump/1 +all, ppl_@CLASS@_@MEMBYTES@/2 +all, -ppl_@CLASS@_wrap_assign/8 +simple, dnl dnl NOTE: The next few schemas provide special widenings and dnl extrapolations that depend on the domains.

1 0

[GIT] ppl/ppl(master): Completed removal of support for circular intervals.
by Enea Zaffanella 01 Mar '10

01 Mar '10

Module: ppl/ppl Branch: master Commit: 0a65a2985d7b8856807ee8b4d6390fa57530ec20 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0a65a2985d7b… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Mar 1 11:15:05 2010 +0100 Completed removal of support for circular intervals. Removed now ambiguous method CC76_narrowing_assign(). While at it, also wrapped a few long lines. --- src/Box.defs.hh | 15 +++++++++------ src/Box.templates.hh | 18 +++++++++--------- 2 files changed, 18 insertions(+), 15 deletions(-) diff --git a/src/Box.defs.hh b/src/Box.defs.hh index 52c201f..b6d8a92 100644 --- a/src/Box.defs.hh +++ b/src/Box.defs.hh @@ -1311,7 +1311,9 @@ public: Thrown if \p *this and \p y are dimension-incompatible. */ template <typename T> - typename Enable_If<Is_Same<T, Box>::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type + typename Enable_If<Is_Same<T, Box>::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type CC76_widening_assign(const T& y, unsigned* tp = 0); /*! \brief @@ -1331,7 +1333,9 @@ public: Thrown if \p *this and \p y are dimension-incompatible. */ template <typename T, typename Iterator> - typename Enable_If<Is_Same<T, Box>::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type + typename Enable_If<Is_Same<T, Box>::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type CC76_widening_assign(const T& y, Iterator first, Iterator last); @@ -1382,10 +1386,9 @@ public: the result of the computation \f$\mathtt{y} \Delta \mathtt{x}\f$. */ template <typename T> - typename Enable_If<Is_Same<T, Box>::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type - CC76_narrowing_assign(const T& y); - template <typename T> - typename Enable_If<Is_Same<T, Box>::value, void>::type + typename Enable_If<Is_Same<T, Box>::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type CC76_narrowing_assign(const T& y); //@} Space-Dimension Preserving Member Functions that May Modify [...] diff --git a/src/Box.templates.hh b/src/Box.templates.hh index 3de3094..9e8af10 100644 --- a/src/Box.templates.hh +++ b/src/Box.templates.hh @@ -3540,7 +3540,9 @@ Box<ITV>::generalized_affine_preimage(const Linear_Expression& lhs, template <typename ITV> template <typename T, typename Iterator> -typename Enable_If<Is_Same<T, Box<ITV> >::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type +typename Enable_If<Is_Same<T, Box<ITV> >::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type Box<ITV>::CC76_widening_assign(const T& y, Iterator first, Iterator last) { if (y.is_empty()) return; @@ -3553,7 +3555,9 @@ Box<ITV>::CC76_widening_assign(const T& y, Iterator first, Iterator last) { template <typename ITV> template <typename T> -typename Enable_If<Is_Same<T, Box<ITV> >::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type +typename Enable_If<Is_Same<T, Box<ITV> >::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type Box<ITV>::CC76_widening_assign(const T& y, unsigned* tp) { static typename ITV::boundary_type stop_points[] = { typename ITV::boundary_type(-2), @@ -3660,7 +3664,9 @@ Box<ITV>::limited_CC76_extrapolation_assign(const Box& y, template <typename ITV> template <typename T> -typename Enable_If<Is_Same<T, Box<ITV> >::value && Is_Same_Or_Derived<Interval_Base, ITV>::value, void>::type +typename Enable_If<Is_Same<T, Box<ITV> >::value + && Is_Same_Or_Derived<Interval_Base, ITV>::value, + void>::type Box<ITV>::CC76_narrowing_assign(const T& y) { const dimension_type space_dim = space_dimension(); @@ -3707,12 +3713,6 @@ Box<ITV>::CC76_narrowing_assign(const T& y) { } template <typename ITV> -template <typename T> -typename Enable_If<Is_Same<T, Box<ITV> >::value, void>::type -Box<ITV>::CC76_narrowing_assign(const T& y) { -} - -template <typename ITV> Constraint_System Box<ITV>::constraints() const { Constraint_System cs;

1 0

[GIT] ppl/ppl(master): Added C interface for wrap_assign.
by Patricia Hill 01 Mar '10

01 Mar '10

Module: ppl/ppl Branch: master Commit: 57c7504c6e09c1d523e6286f792580a9e0c2af76 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=57c7504c6e09… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon Mar 1 08:45:34 2010 +0000 Added C interface for wrap_assign. Minor NELS improvements to documentation describing Wrapping Operator (should be checked by the author of these notes). --- doc/definitions.dox | 18 +++--- interfaces/C/C_interface.dox | 56 ++++++++++++++++ interfaces/C/ppl_c_header.h | 67 ++++++++++++++++++++ interfaces/C/ppl_c_implementation_common.defs.hh | 6 ++ .../C/ppl_c_implementation_common.inlines.hh | 44 +++++++++++++ interfaces/C/ppl_interface_generator_c_cc_code.m4 | 29 +++++++++ interfaces/C/ppl_interface_generator_c_h_code.m4 | 15 +++++ ...erface_generator_common_procedure_generators.m4 | 1 + 8 files changed, 227 insertions(+), 9 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=57c7504c…

1 0