March 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(termination): Turn off debugging output.
by Roberto Bagnara 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: termination Commit: 003fb0b786349b3da96d65bd4483f4982bf88294 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=003fb0b78634… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Mar 18 06:55:41 2010 +0400 Turn off debugging output. --- interfaces/Prolog/ppl_prolog_common.defs.hh | 2 +- src/termination.templates.hh | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/interfaces/Prolog/ppl_prolog_common.defs.hh b/interfaces/Prolog/ppl_prolog_common.defs.hh index 3457029..33af32d 100644 --- a/interfaces/Prolog/ppl_prolog_common.defs.hh +++ b/interfaces/Prolog/ppl_prolog_common.defs.hh @@ -37,7 +37,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <iostream> #ifndef PROLOG_TRACK_ALLOCATION -#define PROLOG_TRACK_ALLOCATION 1 +#define PROLOG_TRACK_ALLOCATION 0 #endif #ifndef NOISY_PROLOG_TRACK_ALLOCATION #define NOISY_PROLOG_TRACK_ALLOCATION 0 diff --git a/src/termination.templates.hh b/src/termination.templates.hh index d352a72..247a587 100644 --- a/src/termination.templates.hh +++ b/src/termination.templates.hh @@ -28,7 +28,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "BD_Shape.defs.hh" #include "Octagonal_Shape.defs.hh" -#define PRINT_DEBUG_INFO 1 +#define PRINT_DEBUG_INFO 0 #if PRINT_DEBUG_INFO #include <iostream>

1 0

[GIT] ppl/ppl(termination): Fixed two bogus invocations of PPL_WEAK_REGISTER.
by Roberto Bagnara 18 Mar '10

18 Mar '10

Module: ppl/ppl Branch: termination Commit: 72e0e99576d4a6508c6a7078cd37207833c54f2b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=72e0e99576d4… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Mar 18 06:52:45 2010 +0400 Fixed two bogus invocations of PPL_WEAK_REGISTER. --- interfaces/Prolog/ppl_prolog_common.cc | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/interfaces/Prolog/ppl_prolog_common.cc b/interfaces/Prolog/ppl_prolog_common.cc index 94202f3..5a186e8 100644 --- a/interfaces/Prolog/ppl_prolog_common.cc +++ b/interfaces/Prolog/ppl_prolog_common.cc @@ -2544,7 +2544,7 @@ ppl_PIP_Problem_solution(Prolog_term_ref t_pip, Prolog_term_ref t_sol = Prolog_new_term_ref(); Prolog_put_address(t_sol, sol); if (Prolog_unify(t_pip_tree, t_sol)) { - PPL_WEAK_REGISTER(t_pip_tree); + PPL_REGISTER(sol); return PROLOG_SUCCESS; } } @@ -2562,7 +2562,7 @@ ppl_PIP_Problem_optimizing_solution(Prolog_term_ref t_pip, Prolog_term_ref t_sol = Prolog_new_term_ref(); Prolog_put_address(t_sol, sol); if (Prolog_unify(t_pip_tree, t_sol)) { - PPL_WEAK_REGISTER(t_pip_tree); + PPL_REGISTER(sol); return PROLOG_SUCCESS; } }

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Problem: optimize solve() method for sparse matrices.
by Marco Poletti 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 0ee77779d7a558144c70ee5420899c6de44ce529 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0ee77779d7a5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 23:10:30 2010 +0100 PIP_Problem: optimize solve() method for sparse matrices. --- src/PIP_Problem.cc | 6 ++++-- 1 files changed, 4 insertions(+), 2 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 3eca9e7..71a798f 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -204,8 +204,10 @@ PPL::PIP_Problem::solve() const { // If it is an equality, also insert its negation. if (c.is_equality()) { - for (dimension_type i = new_num_cols; i-- > 0; ) - neg_assign(row[i], row[i]); + matrix_row_iterator i = row.begin(); + matrix_row_iterator i_end = row.end(); + for ( ; i!=i_end; ++i) + neg_assign((*i).second); // Insert new row into initial context. x.initial_context.add_row(row);

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Problem: optimize solve() method for sparse matrices.
by Marco Poletti 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: d1d4d7cf65e4a694c16bbd7a41e934eae00fcdd4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d1d4d7cf65e4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 23:07:59 2010 +0100 PIP_Problem: optimize solve() method for sparse matrices. --- src/PIP_Problem.cc | 49 +++++++++++++++++++++++++++++++++++++++---------- 1 files changed, 39 insertions(+), 10 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index f1191be..3eca9e7 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -155,20 +155,49 @@ PPL::PIP_Problem::solve() const { // Translate constraint into context row. matrix_row_copy_type row(new_num_cols); - row[0] = c.inhomogeneous_term(); { + matrix_row_copy_iterator itr = row.end(); + + if (c.inhomogeneous_term() != 0) { + itr = row.find_create(0,c.inhomogeneous_term()); + // Adjust inhomogenous term if strict. + if (c.is_strict_inequality()) + --((*itr).second); + } else { + // Adjust inhomogenous term if strict. + if (c.is_strict_inequality()) + itr = row.find_create(0,-1); + } dimension_type i = 1; - for (Variables_Set::const_iterator - pi = param_begin; pi != param_end; ++pi, ++i) { - if (*pi < c_space_dim) - row[i] = c.coefficient(Variable(*pi)); - else - break; + bool continue_looping = true; + Variables_Set::const_iterator pi = param_begin; + + if (itr == row.end()) + for ( ; pi != param_end; ++pi, ++i) { + if (*pi < c_space_dim) { + const Coefficient& x = c.coefficient(Variable(*pi)); + if (x != 0) { + itr = row.find_create(i,x); + // itr is now initialized, use it in the next iterations. + ++pi; + ++i; + break; + } + } else + continue_looping = false; + } + if (continue_looping) { + for ( ; pi != param_end; ++pi, ++i) { + PPL_ASSERT(itr != row.end()); + if (*pi < c_space_dim) { + const Coefficient& x = c.coefficient(Variable(*pi)); + if (x != 0) + itr = row.find_create(i,x); + } else + break; + } } } - // Adjust inhomogenous term if strict. - if (c.is_strict_inequality()) - --row[0]; // Insert new row into initial context. x.initial_context.add_row(row);

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Problem: add typedefs for matrix_row_copy_iterator and matrix_row_copy_const_iterator .
by Marco Poletti 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 86958cc77c3e82b205156cd5c9d2880e173e399f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=86958cc77c3e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 23:07:25 2010 +0100 PIP_Problem: add typedefs for matrix_row_copy_iterator and matrix_row_copy_const_iterator. --- src/PIP_Problem.defs.hh | 4 ++++ 1 files changed, 4 insertions(+), 0 deletions(-) diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 6bb28da..51f7547 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -342,6 +342,8 @@ public: typedef Dense_Row::iterator matrix_row_iterator; typedef Dense_Row::const_iterator matrix_row_const_iterator; typedef Dense_Row matrix_row_copy_type; + typedef Dense_Row::iterator matrix_row_copy_iterator; + typedef Dense_Row::const_iterator matrix_row_copy_const_iterator; #else typedef Sparse_Matrix matrix_type; typedef Sparse_Row_Reference matrix_row_reference_type; @@ -351,6 +353,8 @@ public: typedef Sparse_Row_Reference::iterator matrix_row_iterator; typedef Sparse_Row_Reference::const_iterator matrix_row_const_iterator; typedef Sparse_Row matrix_row_copy_type; + typedef Sparse_Row::iterator matrix_row_copy_iterator; + typedef Sparse_Row::const_iterator matrix_row_copy_const_iterator; #endif //! Builds a trivial PIP problem.

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: correct typo in comment.
by Marco Poletti 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: 4ee8ffded7315cf6ff6d51a5f62f48bbad7b526a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4ee8ffded731… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 22:41:28 2010 +0100 MIP_Problem: correct typo in comment. --- src/MIP_Problem.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index fb44001..d01d1a5 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -2314,7 +2314,7 @@ PPL::MIP_Problem::OK() const { } } { - // Needed to sort accesses to tableau_j, improving preformance. + // Needed to sort accesses to tableau_j, improving performance. std::map<dimension_type,dimension_type> var_in_base; for (dimension_type i = base.size(); i-- > 0; ) var_in_base[base[i]] = i;

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: use matrix_row_const_iterator instead of matrix_row_iterator in erase_artificials ().
by Marco Poletti 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: sparse_matrices Commit: d4414b4f8f43ec0decc00a580b54a7354ab2689b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d4414b4f8f43… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 22:40:02 2010 +0100 MIP_Problem: use matrix_row_const_iterator instead of matrix_row_iterator in erase_artificials(). --- src/MIP_Problem.cc | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 1d04ebf..fb44001 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1657,8 +1657,8 @@ PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials, // Search for a non-zero element to enter the base. matrix_row_reference_type tableau_i = tableau[i]; bool redundant = true; - matrix_row_iterator j = tableau_i.begin(); - matrix_row_iterator j_end = tableau_i.end(); + matrix_row_const_iterator j = tableau_i.begin(); + matrix_row_const_iterator j_end = tableau_i.end(); // Skip the first element if (j != j_end && (*j).first == 0) ++j;

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 17 Mar '10

17 Mar '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8d36d4d6d832… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 22:33:41 2010 +0100 MIP_Problem: add another version of linear_combine() for sparse backends that define PPL_SPARSE_BACKEND_SLOW_INSERTIONS. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e0c200993bcf… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 22:32:39 2010 +0100 MIP_Problem: add typedefs for matrix_row_copy_type, matrix_row_copy_iterator and matrix_row_copy_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ac91af14b5c2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 22:24:20 2010 +0100 Sparse_Row_Reference: define previously-declared swap() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a2555c4398fd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 21:49:07 2010 +0100 MIP_Problem: use find_create() instead of operator[] in process_pending_constraints(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=091a91e946c5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 21:33:06 2010 +0100 Indentation fixes. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=55a49cfb8dd7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:58:11 2010 +0100 Sparse_Row, Sparse_Row_Reference: add some other find_create() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=38df6db146bd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:41:09 2010 +0100 Unlimited_Sparse_Row: add some other find_create() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2c2d6bf52e70… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:40:07 2010 +0100 Unlimited_Sparse_Row: require backends to have a three-argument insert() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=890176ad24e6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:39:17 2010 +0100 Unlimited_Sparse_Row_Custom_Slist_Backend: add three-argument insert(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dfd8700135f9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:38:21 2010 +0100 Unlimited_Sparse_Row_Std_Vector_Backend: add three-argument insert(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e28dfd42d7b6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Mar 17 20:38:02 2010 +0100 Unlimited_Sparse_Row_Std_List_Backend: add three-argument insert().

1 0

[GIT] ppl/ppl(termination): Fixed several typos.
by Roberto Bagnara 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: termination Commit: ff0e20fbd91fea45e9eb2bd2c90a92291e22d02f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ff0e20fbd91f… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Mar 17 21:11:12 2010 +0400 Fixed several typos. --- interfaces/Prolog/tests/pl_check.pl | 18 +++++++++--------- 1 files changed, 9 insertions(+), 9 deletions(-) diff --git a/interfaces/Prolog/tests/pl_check.pl b/interfaces/Prolog/tests/pl_check.pl index a7b9d38..5abfb02 100644 --- a/interfaces/Prolog/tests/pl_check.pl +++ b/interfaces/Prolog/tests/pl_check.pl @@ -1823,20 +1823,20 @@ ok(T) :- % ppl_termination_test_NNC_Polyhedron_PR/2. termination_test :- make_vars(4, [A, B, C, D]), - clean_ppl_new_Polyhedron_from_constraints(C, + clean_ppl_new_Polyhedron_from_constraints(c, [A - C >= 0, - -A + C >= 0; - -B + D >= 1; - B >= 0; + -A + C >= 0, + -B + D >= 1, + B >= 0, A >= 1], P1), ppl_termination_test_C_Polyhedron_MS(P1), ppl_termination_test_C_Polyhedron_PR(P1), - clean_ppl_new_Polyhedron_from_constraints(NNC, + clean_ppl_new_Polyhedron_from_constraints(nnc, [A - C >= 0, - -A + C >= 0; - -B + D >= 1; - B >= 0; - P2), + -A + C >= 0, + -B + D >= 1, + B >= 0], + P2), ppl_termination_test_NNC_Polyhedron_MS(P2), ppl_termination_test_NNC_Polyhedron_PR(P2), !,

1 0

[GIT] ppl/ppl(termination): Fixed some invocations of PPL_CHECK.
by Roberto Bagnara 17 Mar '10

17 Mar '10

Module: ppl/ppl Branch: termination Commit: 1dcffed9f68fd428fe5c6aaf9fbf1140f3c57303 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1dcffed9f68f… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Mar 17 20:56:40 2010 +0400 Fixed some invocations of PPL_CHECK. --- .../ppl_interface_generator_prolog_cc_code.m4 | 11 +++++++---- 1 files changed, 7 insertions(+), 4 deletions(-) diff --git a/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 b/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 index b1c5f4f..2a28c89 100644 --- a/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 +++ b/interfaces/Prolog/ppl_interface_generator_prolog_cc_code.m4 @@ -1235,7 +1235,7 @@ m4_define(`ppl_termination_test_@TOPOLOGY@@CLASS@_@TERMINATION_ID@_code', static const char* where = "ppl_termination_test_@TOPOLOGY@@CLASS@_@TERMINATION_ID@/1"; try { @TOPOLOGY@@CPP_CLASS@* pset = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset, where); - PPL_CHECK(ph); + PPL_CHECK(pset); if (Parma_Polyhedra_Library::termination_test_@TERMINATION_ID@(*pset)) return PROLOG_SUCCESS; } @@ -1255,7 +1255,8 @@ m4_define(`ppl_termination_test_@TOPOLOGY@@CLASS@_@TERMINATION_ID@_2_code', = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_before, where); @TOPOLOGY@@CPP_CLASS@* pset_after = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_after, where); - PPL_CHECK(ph); + PPL_CHECK(pset_before); + PPL_CHECK(pset_after); if (Parma_Polyhedra_Library ::termination_test_@TERMINATION_ID@_2(*pset_before, *pset_after)) return PROLOG_SUCCESS; @@ -1300,7 +1301,8 @@ m4_define(`ppl_one_affine_ranking_function_@TOPOLOGY@@CLASS@_@TERMINATION_ID@_2_ @TOPOLOGY@@CPP_CLASS@* pset_after = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_after, where); Generator gg(point()); - PPL_CHECK(pset); + PPL_CHECK(pset_before); + PPL_CHECK(pset_after); if (Parma_Polyhedra_Library ::one_affine_ranking_function_@TERMINATION_ID@_2(*pset_before, *pset_after, @@ -1353,7 +1355,8 @@ m4_define(`ppl_all_affine_ranking_functions_@TOPOLOGY@@CLASS@_@TERMINATION_ID@_2 = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_before, where); @TOPOLOGY@@CPP_CLASS@* pset_after = term_to_handle<@TOPOLOGY@@CPP_CLASS@ >(t_pset_after, where); - PPL_CHECK(pset); + PPL_CHECK(pset_before); + PPL_CHECK(pset_after); C_Polyhedron* ph = new C_Polyhedron(); Parma_Polyhedra_Library ::all_affine_ranking_functions_@TERMINATION_ID@_2(*pset_before,

1 0