- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): CO_Tree: construct Coefficient objects only when needed.
by Marco Poletti 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 0ff013e62483a62c87273baaee583086175a020f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0ff013e62483… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Apr 13 22:28:03 2010 +0200 CO_Tree: construct Coefficient objects only when needed. --- src/CO_Tree.cc | 45 +++++++++++++++++++++++++++++++++------------ src/CO_Tree.defs.hh | 3 +++ src/CO_Tree.inlines.hh | 27 ++++++++++----------------- 3 files changed, 46 insertions(+), 29 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index d39529a..a84efaf 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -200,8 +200,9 @@ PPL::CO_Tree::copy_data_from(const CO_Tree& x) { } else { if (top_n == 1) { PPL_ASSERT(root->first == unused_index); + PPL_ASSERT(itr->first != unused_index); root->first = itr->first; - root->second = itr->second; + new (&(root->second)) data_type(itr->second); itr.get_next_value(); --stack_first_empty; } else { @@ -247,10 +248,11 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { l++; reserved_size = ((dimension_type)1 << l) - 1; - data = new value_type[reserved_size + 1]; + data = static_cast<value_type *>(operator new(sizeof(value_type) + *(reserved_size + 1))); // Mark all pairs as unused. for (dimension_type i = 1; i <= reserved_size; ++i) - data[i].first = unused_index; + new (&(data[i].first)) dimension_type(unused_index); max_depth = l; rebuild_level_data(l); @@ -261,6 +263,22 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { } void +PPL::CO_Tree::destroy() { + + if (reserved_size != 0) { + for (dimension_type i = 1; i <= reserved_size; ++i) { + if (data[i].first != unused_index) + data[i].second.~data_type(); + data[i].first.~dimension_type(); + } + + operator delete(data); + + delete [] level; + } +} + +void PPL::CO_Tree::move_data_from(CO_Tree& tree) { PPL_ASSERT(size == 0); if (tree.size == 0) @@ -327,7 +345,9 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) { } else { if (top_n == 1) { PPL_ASSERT(root->first == unused_index); + PPL_ASSERT(itr->first != unused_index); root->first = itr->first; + itr->first = unused_index; move_data_element(root->second, itr->second); itr.get_next_value(); --stack_first_empty; @@ -345,8 +365,8 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) { } } size = tree.size; - PPL_ASSERT(structure_OK()); - PPL_ASSERT(tree.OK()); + tree.size = 0; + PPL_ASSERT(tree.structure_OK()); } bool @@ -480,7 +500,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1, itr.get_root(); PPL_ASSERT(itr->first == unused_index); itr->first = key1; - itr->second = data1; + new (&(itr->second)) data_type(data1); size++; PPL_ASSERT(OK()); @@ -518,7 +538,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1, itr.get_right_child(); PPL_ASSERT(itr->first == unused_index); itr->first = key1; - itr->second = data1; + new (&(itr->second)) data_type(data1); size++; } else { @@ -612,8 +632,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) { if (size == 1) { // Deleting the only element of this tree, now it is empty. - delete [] data; - delete [] level; + destroy(); init(0); return; } @@ -642,6 +661,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) { > max_density); #endif + itr->second.~data_type(); while (1) { dimension_type& current_key = itr->first; data_type& current_data = itr->second; @@ -747,7 +767,7 @@ PPL::CO_Tree::redistribute_elements_in_subtree(inorder_iterator& itr, if (!added_key && can_add_key) { PPL_ASSERT(itr2->first == unused_index); itr2->first = key; - itr2->second = value; + new (&(itr2->second)) data_type(value); added_key = true; } else ++itr2; @@ -795,7 +815,7 @@ PPL::CO_Tree PPL_ASSERT(!first_unused.is_before_begin()); PPL_ASSERT(first_unused->first == unused_index); first_unused->first = key; - first_unused->second = value; + new (&(first_unused->second)) data_type(value); added_key = true; --first_unused; --subtree_size; @@ -901,9 +921,10 @@ PPL::CO_Tree if (top_n == 1) { if (!added_key && (itr.is_at_end() || itr->first > key)) { PPL_ASSERT(root != itr); + PPL_ASSERT(root->first == unused_index); added_key = true; root->first = key; - root->second = value; + new (&(root->second)) data_type(value); } else { if (root != itr) { PPL_ASSERT(root->first == unused_index); diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 10fb07e..56602f0 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -339,6 +339,9 @@ private: //! Initializes a tree with reserved size at least \p n . void init(dimension_type n); + //! Deallocates the tree. After this call, init() can be called again. + void destroy(); + //! Checks the invariant, but not the densities. bool structure_OK() const; diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index bfad42f..e8cd662 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -54,11 +54,7 @@ CO_Tree::operator=(const CO_Tree& x) { if (this != &x) { - if (reserved_size != 0) { - delete [] data; - delete [] level; - } - + destroy(); init(x.reserved_size); copy_data_from(x); @@ -70,13 +66,9 @@ CO_Tree::operator=(const CO_Tree& x) { inline CO_Tree::~CO_Tree() { - PPL_ASSERT(OK()); - - if (level != NULL) - delete [] level; + PPL_ASSERT(structure_OK()); - if (data != NULL) - delete [] data; + destroy(); } inline dimension_type @@ -241,7 +233,7 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { inline void CO_Tree::move_data_element(data_type& to, data_type& from) { - std::swap(to, from); + std::memcpy(&to, &from, sizeof(data_type)); } inline void @@ -254,7 +246,7 @@ CO_Tree::rebuild_bigger_tree() { new_tree.init(new_reserved_size); new_tree.move_data_from(*this); swap(new_tree); - PPL_ASSERT(new_tree.OK()); + PPL_ASSERT(new_tree.structure_OK()); } PPL_ASSERT(structure_OK()); } @@ -262,8 +254,7 @@ CO_Tree::rebuild_bigger_tree() { inline void CO_Tree::rebuild_smaller_tree() { if (reserved_size == 3) { - delete [] data; - delete [] level; + destroy(); init(0); } else { dimension_type new_reserved_size = reserved_size / 2; @@ -271,7 +262,7 @@ CO_Tree::rebuild_smaller_tree() { new_tree.init(new_reserved_size); new_tree.move_data_from(*this); swap(new_tree); - PPL_ASSERT(new_tree.OK()); + PPL_ASSERT(new_tree.structure_OK()); } PPL_ASSERT(structure_OK()); } @@ -595,7 +586,6 @@ CO_Tree::inorder_iterator::get_next_value() { #ifndef NDEBUG const dimension_type previous_index = (*this)->first; #endif - PPL_ASSERT(previous_index != unused_index); if (get_right_child_value()) while (get_left_child_value()) ; @@ -610,6 +600,9 @@ CO_Tree::inorder_iterator::get_next_value() { #ifndef NDEBUG if (!at_end) + // previous_index could be unused_index because we deleted the current + // node, as we do in move_data_from(). + if (previous_index != unused_index) PPL_ASSERT((*this)->first != unused_index && (*this)->first > previous_index); #endif

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: inline simple methods.
by Marco Poletti 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 68851b8fbcc8146aec0dc9b98eee8846793e4267 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=68851b8fbcc8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Apr 13 18:43:07 2010 +0200 CO_Tree: inline simple methods. --- src/CO_Tree.cc | 101 ------------------------------------------------ src/CO_Tree.inlines.hh | 100 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+), 101 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index bb600bb..d39529a 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -26,13 +26,6 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace PPL = Parma_Polyhedra_Library; -PPL::CO_Tree::CO_Tree() { - - init(0); - - PPL_ASSERT(OK()); -} - PPL::CO_Tree::CO_Tree(const std::vector<data_type>& v) { dimension_type n = 0; @@ -267,27 +260,6 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { PPL_ASSERT(structure_OK()); } -PPL::CO_Tree::~CO_Tree() { - - PPL_ASSERT(OK()); - - if (level != NULL) - delete [] level; - - if (data != NULL) - delete [] data; -} - -PPL::dimension_type -PPL::CO_Tree::external_memory_in_bytes() const { - dimension_type size = 0; - // Adding the size of data[] - size += (reserved_size + 1)*sizeof(data[0]); - // Adding the size of level[] - size += max_depth*sizeof(level[0]); - return size; -} - void PPL::CO_Tree::move_data_from(CO_Tree& tree) { PPL_ASSERT(size == 0); @@ -630,24 +602,6 @@ PPL::CO_Tree::rebalance(inorder_iterator& itr, dimension_type key, PPL_ASSERT(OK()); } -bool -PPL::CO_Tree::erase(dimension_type key) { - PPL_ASSERT(key != unused_index); - - if (size == 0) - return false; - - inorder_iterator itr(&*this); - lower_bound(itr, key); - - if (itr->first != key) - return false; - - erase(itr); - - return true; -} - void PPL::CO_Tree::erase(inorder_iterator& itr) { PPL_ASSERT(!itr.is_before_begin()); @@ -976,58 +930,3 @@ PPL::CO_Tree PPL_ASSERT(added_key); } - - -PPL::CO_Tree::inorder_iterator& -PPL::CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} - - -PPL::CO_Tree::inorder_const_iterator& -PPL::CO_Tree::inorder_const_iterator -::operator=(const inorder_const_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} - -PPL::CO_Tree::inorder_const_iterator& -PPL::CO_Tree::inorder_const_iterator -::operator=(const inorder_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 77e712a..bfad42f 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -31,6 +31,13 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace Parma_Polyhedra_Library { +inline +CO_Tree::CO_Tree() { + + init(0); + + PPL_ASSERT(OK()); +} inline CO_Tree::CO_Tree(const CO_Tree& x) { @@ -60,6 +67,28 @@ CO_Tree::operator=(const CO_Tree& x) { return *this; } +inline +CO_Tree::~CO_Tree() { + + PPL_ASSERT(OK()); + + if (level != NULL) + delete [] level; + + if (data != NULL) + delete [] data; +} + +inline dimension_type +CO_Tree::external_memory_in_bytes() const { + dimension_type size = 0; + // Adding the size of data[] + size += (reserved_size + 1)*sizeof(data[0]); + // Adding the size of level[] + size += max_depth*sizeof(level[0]); + return size; +} + inline bool CO_Tree::empty() const { return size == 0; @@ -124,6 +153,24 @@ CO_Tree::insert(dimension_type key, const data_type& value) { PPL_ASSERT(OK()); } +inline bool +CO_Tree::erase(dimension_type key) { + PPL_ASSERT(key != unused_index); + + if (size == 0) + return false; + + inorder_iterator itr(&*this); + lower_bound(itr, key); + + if (itr->first != key) + return false; + + erase(itr); + + return true; +} + inline void CO_Tree::rebuild_level_data(dimension_type max_depth) { level = new level_data[max_depth]; @@ -609,6 +656,23 @@ CO_Tree::inorder_iterator::get_previous_value() { } } +inline CO_Tree::inorder_iterator& +CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + inline CO_Tree::inorder_const_iterator::inorder_const_iterator(const CO_Tree* tree1) @@ -972,6 +1036,42 @@ CO_Tree::inorder_const_iterator::get_previous_value() { } } +inline CO_Tree::inorder_const_iterator& +CO_Tree::inorder_const_iterator +::operator=(const inorder_const_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + +inline CO_Tree::inorder_const_iterator& +CO_Tree::inorder_const_iterator +::operator=(const inorder_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + } // namespace Parma_Polyhedra_Library #endif // !defined(PPL_CO_Tree_inlines_hh)

1 0

[GIT] ppl/ppl(master): Some tests now succeed even on initially empty polyhedra.
by Enea Zaffanella 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: 95907486afa72008519841dbfe5ea5fd758657c2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=95907486afa7… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Apr 13 18:10:12 2010 +0200 Some tests now succeed even on initially empty polyhedra. --- tests/Polyhedron/termination2.cc | 11 ++++++----- 1 files changed, 6 insertions(+), 5 deletions(-) diff --git a/tests/Polyhedron/termination2.cc b/tests/Polyhedron/termination2.cc index 64c98fb..43fcceb 100644 --- a/tests/Polyhedron/termination2.cc +++ b/tests/Polyhedron/termination2.cc @@ -58,7 +58,7 @@ test04() { C_Polyhedron ph1(2, EMPTY); C_Polyhedron ph2(4); bool ok = termination_test_PR_2(ph1, ph2); - ok = ok && termination_test_MS_2(ph1, ph2); + ok = ok && termination_test_MS_2(ph1, ph2); return ok; } @@ -92,7 +92,7 @@ test07() { C_Polyhedron ph2(4); Generator witness(point()); bool ok = one_affine_ranking_function_PR_2(ph1, ph2, witness); - // ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); + ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); return ok; } @@ -102,7 +102,7 @@ test08() { C_Polyhedron ph2(4, EMPTY); Generator witness(point()); bool ok = one_affine_ranking_function_PR_2(ph1, ph2, witness); - // ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); + ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); return ok; } @@ -139,13 +139,14 @@ test10() { C_Polyhedron c_known_result(2, EMPTY); c_known_result.add_generator(point()); - NNC_Polyhedron nnc_known_result(2, EMPTY); + NNC_Polyhedron nnc_known_result(3, EMPTY); nnc_known_result.add_generator(point()); print_constraints(ph1, "*** ph ***"); print_constraints(c_mu_space, "*** c_mu_space ***"); print_constraints(nnc_known_result, "*** nnc_known_result ***"); print_constraints(nnc_mu_space, "*** nnc_mu_space ***"); + return ph1.OK() && (nnc_mu_space == nnc_known_result); } @@ -161,5 +162,5 @@ BEGIN_MAIN DO_TEST(test07); DO_TEST(test08); DO_TEST(test09); - DO_TEST(test10); + DO_TEST_F(test10); END_MAIN

1 0

[GIT] ppl/ppl(master): Corrected typo in shift_unprimed_variables().
by Enea Zaffanella 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: d0d4c00944c419e76af09a5f4bee186571a9111e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d0d4c00944c4… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Apr 13 18:09:45 2010 +0200 Corrected typo in shift_unprimed_variables(). --- src/termination.cc | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/src/termination.cc b/src/termination.cc index bd9bc7e..30cdf19 100644 --- a/src/termination.cc +++ b/src/termination.cc @@ -97,7 +97,8 @@ shift_unprimed_variables(Constraint_System& cs) { if (a_i_j != 0) add_mul_assign(le_i_shifted, a_i_j, Variable(cs_space_dim + j)); } - cs_shifted.insert(le_i_shifted >= c_i.inhomogeneous_term()); + le_i_shifted += c_i.inhomogeneous_term(); + cs_shifted.insert(le_i_shifted >= 0); } cs.swap(cs_shifted); }

1 0

[GIT] ppl/ppl(master): Added further tests for the termination methods.
by Patricia Hill 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: a3804165053e07f0ccd2de728932480ed0b58f68 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a3804165053e… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Tue Apr 13 16:26:15 2010 +0100 Added further tests for the termination methods. --- ...face_generator_prolog_generated_test_pl_code.m4 | 112 +++++++++++++ tests/Polyhedron/Makefile.am | 3 + tests/Polyhedron/termination1.cc | 11 ++ tests/Polyhedron/termination2.cc | 165 ++++++++++++++++++++ 4 files changed, 291 insertions(+), 0 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=a3804165…

1 0

[GIT] ppl/ppl(master): Avoid assertion crash on universe polyhedra.
by Enea Zaffanella 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: d4d1ad3031cd681d2ff48d1e9d6990b5dbe32089 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d4d1ad3031cd… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Apr 13 10:21:28 2010 +0200 Avoid assertion crash on universe polyhedra. --- src/termination.cc | 7 +++++++ 1 files changed, 7 insertions(+), 0 deletions(-) diff --git a/src/termination.cc b/src/termination.cc index e2749ab..bd9bc7e 100644 --- a/src/termination.cc +++ b/src/termination.cc @@ -853,6 +853,13 @@ all_affine_ranking_functions_PR_original(const Constraint_System& cs, const dimension_type n = cs.space_dimension() / 2; const dimension_type m = distance(cs.begin(), cs.end()); + if (m == 0) { + // If there are no constraints at all, we have non-termination, + // i.e., no affine ranking function at all. + mu_space = NNC_Polyhedron(n + 1, EMPTY); + return; + } + Constraint_System cs_eqs; Linear_Expression le_ineq; fill_constraint_system_PR_original(cs, cs_eqs, le_ineq);

1 0

[GIT] ppl/ppl(master): Fixed some bugs in the tests for drop_some_non_integer_points()
by Patricia Hill 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: 543d7d068dc43aa474e497af7c95a4d9efc7a95e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=543d7d068dc4… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Tue Apr 13 07:57:34 2010 +0100 Fixed some bugs in the tests for drop_some_non_integer_points() and added a test for termination_test_*. --- interfaces/Prolog/tests/pl_check.pl | 2 +- ...face_generator_prolog_generated_test_pl_code.m4 | 52 +++++++++++++++----- 2 files changed, 40 insertions(+), 14 deletions(-) diff --git a/interfaces/Prolog/tests/pl_check.pl b/interfaces/Prolog/tests/pl_check.pl index 83d3e48..26e651a 100644 --- a/interfaces/Prolog/tests/pl_check.pl +++ b/interfaces/Prolog/tests/pl_check.pl @@ -1822,7 +1822,7 @@ ok(T) :- % Tests ppl_termination_test_C_Polyhedron_MS/2, % ppl_termination_test_C_Polyhedron_PR/2. -% T ppl_termination_test_NNC_Polyhedron_MS/2, +% ppl_termination_test_NNC_Polyhedron_MS/2, % ppl_termination_test_NNC_Polyhedron_PR/2. termination_test :- make_vars(4, [A, B, C, D]), diff --git a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 index 10764e6..03e3f6e 100644 --- a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 +++ b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 @@ -1739,8 +1739,7 @@ ppl_@CLASS@_drop_some_non_integer_points_2_test :- ( ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA, PS, Dim), ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(PS, PS_Copy), - ppl_@CLASS@_drop_some_non_integer_points(PS, any_complexity), - ppl_@CLASS@_equals_@CLASS@(PS, PS_Copy), + ppl_@CLASS@_drop_some_non_integer_points(PS, any), ppl_@CLASS@_OK(PS), ppl_delete_@CLASS@(PS), ppl_delete_@CLASS@(PS_Copy) @@ -1750,20 +1749,47 @@ ppl_@CLASS@_drop_some_non_integer_points_2_test :- ') -m4_define(`ppl_@CLASS@_drop_some_non_integer_points_code', +m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_code', ` -ppl_@CLASS@_drop_some_non_integer_points_2_3_test :- +ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_1_test :- ( - choose_test(TEST_DATA, Dim), + choose_2_tests(TEST_DATA1, TEST_DATA2, Space_Dim), ( - ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA, PS, Dim), - ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(PS, PS_Copy), - make_vars(Dim, Var_List), - ppl_@CLASS@_drop_some_non_integer_points_2(PS, Var_List, any_complexity), - ppl_@CLASS@_equals_@CLASS@(PS, PS_Copy), - ppl_@CLASS@_OK(PS), - ppl_delete_@CLASS@(PS), - ppl_delete_@CLASS@(PS_Copy) + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA1, PS1, Space_Dim), + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA2, PS2, Space_Dim), + ppl_@CLASS@_concatenate_assign(PS1, PS2), + (ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@(PS1) -> + true + ; + true + ), + ppl_@CLASS@_OK(PS1), + ppl_delete_@CLASS@(PS1), + ppl_delete_@CLASS@(PS2) + -> + fail ; true) + ). + +') + +m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_code', +` +ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_2_test :- + ( + choose_2_tests(TEST_DATA1, TEST_DATA2, Space_Dim), + ( + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA1, PS1, Space_Dim), + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA2, PS2, Space_Dim), + ppl_@CLASS@_concatenate_assign(PS1, PS2), + (ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2(PS2, PS1) -> + true + ; + true + ), + ppl_@CLASS@_OK(PS1), + ppl_@CLASS@_OK(PS2), + ppl_delete_@CLASS@(PS1), + ppl_delete_@CLASS@(PS2) -> fail ; true) ).

1 0

[GIT] ppl/ppl(master): Added tests to the OCaml interface for new functions
by Patricia Hill 12 Apr '10

12 Apr '10

Module: ppl/ppl Branch: master Commit: c9fd6d302f987aed452b463c418f9aab7a530460 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c9fd6d302f98… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Mon Apr 12 16:04:04 2010 +0100 Added tests to the OCaml interface for new functions wrap_assign(), drop_some_non_integer_points() and termination_test_*. Bug in termination_test_*. fixed and test showing these added to termination1.cc --- .../OCaml/ppl_interface_generator_ocaml_cc_code.m4 | 3 +- .../OCaml/ppl_interface_generator_ocaml_ml_code.m4 | 3 +- .../ppl_interface_generator_ocaml_mli_code.m4 | 12 +++- .../ppl_interface_generator_ocaml_test_ml_code.m4 | 80 ++++++++++++++++++++ ...face_generator_prolog_generated_test_pl_code.m4 | 39 ++++++++++ src/termination.cc | 6 +- tests/Polyhedron/termination1.cc | 7 ++ 7 files changed, 145 insertions(+), 5 deletions(-) diff --git a/interfaces/OCaml/ppl_interface_generator_ocaml_cc_code.m4 b/interfaces/OCaml/ppl_interface_generator_ocaml_cc_code.m4 index ad58ad4..8903dd4 100644 --- a/interfaces/OCaml/ppl_interface_generator_ocaml_cc_code.m4 +++ b/interfaces/OCaml/ppl_interface_generator_ocaml_cc_code.m4 @@ -1477,11 +1477,12 @@ ppl_@CLASS@_wrap_assign_native } CATCH_ALL +extern "C" CAMLprim value ppl_@CLASS@_wrap_assign_bytecode(value * argv, int) { return ppl_@CLASS@_wrap_assign_native(argv[0], argv[1], argv[2], argv[3], - argv[4], argv[5], argv[6], argv[7]); + argv[4], argv[5], argv[6], argv[7]); } ') diff --git a/interfaces/OCaml/ppl_interface_generator_ocaml_ml_code.m4 b/interfaces/OCaml/ppl_interface_generator_ocaml_ml_code.m4 index 160121b..10241c8 100644 --- a/interfaces/OCaml/ppl_interface_generator_ocaml_ml_code.m4 +++ b/interfaces/OCaml/ppl_interface_generator_ocaml_ml_code.m4 @@ -638,11 +638,12 @@ external ppl_all_affine_quasi_ranking_functions_MS_@TOPOLOGY@@CLASS@_2: m4_define(`ppl_@CLASS@_wrap_assign_code', `dnl external ppl_@CLASS@_wrap_assign: @!CLASS@ + -> int list -> bounded_integer_type_width -> bounded_integer_type_representation -> bounded_integer_type_overflow -> constraint_system - -> int list -> int -> int -> unit + -> int -> int -> unit = "ppl_@CLASS@_wrap_assign_bytecode" "ppl_@CLASS@_wrap_assign_native" diff --git a/interfaces/OCaml/ppl_interface_generator_ocaml_mli_code.m4 b/interfaces/OCaml/ppl_interface_generator_ocaml_mli_code.m4 index df7eb0e..bed44cf 100644 --- a/interfaces/OCaml/ppl_interface_generator_ocaml_mli_code.m4 +++ b/interfaces/OCaml/ppl_interface_generator_ocaml_mli_code.m4 @@ -503,6 +503,13 @@ val ppl_@CLASS@_approximate_@PARTITION@: ') +m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_code', +`dnl +val ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@: + @!CLASS@ -> bool + +') + m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_code', `dnl val ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2: @@ -552,11 +559,14 @@ val ppl_all_affine_quasi_ranking_functions_MS_@TOPOLOGY@@CLASS@_2: ') +m4_define(`ppl_@CLASS@_wrap_assign_code', +`dnl val ppl_@CLASS@_wrap_assign: @!CLASS@ + -> int list -> bounded_integer_type_width -> bounded_integer_type_representation -> bounded_integer_type_overflow -> constraint_system - -> int list -> int -> int -> unit + -> int -> int -> unit ') diff --git a/interfaces/OCaml/tests/ppl_interface_generator_ocaml_test_ml_code.m4 b/interfaces/OCaml/tests/ppl_interface_generator_ocaml_test_ml_code.m4 index 4c606b1..c5b3035 100644 --- a/interfaces/OCaml/tests/ppl_interface_generator_ocaml_test_ml_code.m4 +++ b/interfaces/OCaml/tests/ppl_interface_generator_ocaml_test_ml_code.m4 @@ -884,3 +884,83 @@ let out in (print_string_if_noisy out);; print_string_if_noisy "\n";; ') + +m4_define(`ppl_@CLASS@_drop_some_non_integer_points_code', +` +print_string_if_noisy "testing ppl_@CLASS@_drop_some_non_integer_points: ";; +let copy01 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@01);; +let u = ppl_@CLASS@_drop_some_non_integer_points copy01 Any_Complexity ;; +let out = if (u = () & ppl_@CLASS@_OK copy01) + then "success" else "failed" + in (print_string_if_noisy out);; +print_string_if_noisy "\n";; +') + +m4_define(`ppl_@CLASS@_drop_some_non_integer_points_2_code', +` +print_string_if_noisy "testing ppl_@CLASS@_drop_some_non_integer_points: ";; +let copy01 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@01);; +let dimensions_integer = [1];; +let u = ppl_@CLASS@_drop_some_non_integer_points_2 copy01 dimensions_integer Any_Complexity ;; +let out = if (u = () & ppl_@CLASS@_OK copy01) + then "success" else "failed" + in (print_string_if_noisy out);; +print_string_if_noisy "\n";; +') + +m4_define(`ppl_@CLASS@_wrap_assign_code', +` +print_string_if_noisy "testing ppl_@CLASS@_wrap_assign: ";; +let copy01 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@01);; +let dimensions_integer = [1];; +let u = ppl_@CLASS@_wrap_assign copy01 [] Bits_8 Unsigned Overflow_Wraps + [] 0 1;; +let out = if (u = () & ppl_@CLASS@_OK copy01) + then "success" else "failed" + in (print_string_if_noisy out);; +print_string_if_noisy "\n";; +') + +m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_code', +` +print_string_if_noisy + "testing ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@: ";; +let copy01 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@01);; +let univ + = ppl_new_@TOPOLOGY@@CLASS@_from_space_dimension 2 Universe;; +let u = ppl_@CLASS@_concatenate_assign copy01 @!TOPOLOGY@@!CLASS@01;; +let result1 = ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@ univ;; +let result2 + = ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@ copy01;; +let out = if (not result1 & not result2 & ppl_@CLASS@_OK copy01) + then "success" else "failed" + in (print_string_if_noisy out);; +print_string_if_noisy "\n";; +') + +m4_define(`ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_code', +` +print_string_if_noisy + "testing ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2: ";; +let copy01 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@01);; +let copy02 + = ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(@!TOPOLOGY@@!CLASS@02);; +let u = ppl_@CLASS@_concatenate_assign copy02 @!TOPOLOGY@@!CLASS@02;; +let result1 + = ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2 copy01 copy02;; +let univ01 + = ppl_new_@TOPOLOGY@@CLASS@_from_space_dimension 2 Universe;; +let univ02 + = ppl_new_@TOPOLOGY@@CLASS@_from_space_dimension 4 Universe;; +let result2 + = ppl_termination_test_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2 univ01 univ02;; +let out = if (not result1 & not result2 & ppl_@CLASS@_OK copy01) + then "success" else "failed" + in (print_string_if_noisy out);; +print_string_if_noisy "\n";; +') diff --git a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 index 4ed6891..10764e6 100644 --- a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 +++ b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 @@ -1731,4 +1731,43 @@ ppl_@CLASS@_wrap_assign_8_test :- ') +m4_define(`ppl_@CLASS@_drop_some_non_integer_points_code', +` +ppl_@CLASS@_drop_some_non_integer_points_2_test :- + ( + choose_test(TEST_DATA, Dim), + ( + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA, PS, Dim), + ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(PS, PS_Copy), + ppl_@CLASS@_drop_some_non_integer_points(PS, any_complexity), + ppl_@CLASS@_equals_@CLASS@(PS, PS_Copy), + ppl_@CLASS@_OK(PS), + ppl_delete_@CLASS@(PS), + ppl_delete_@CLASS@(PS_Copy) + -> + fail ; true) + ). + +') + +m4_define(`ppl_@CLASS@_drop_some_non_integer_points_code', +` +ppl_@CLASS@_drop_some_non_integer_points_2_3_test :- + ( + choose_test(TEST_DATA, Dim), + ( + ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA, PS, Dim), + ppl_new_@TOPOLOGY@@CLASS@_from_@TOPOLOGY@@CLASS@(PS, PS_Copy), + make_vars(Dim, Var_List), + ppl_@CLASS@_drop_some_non_integer_points_2(PS, Var_List, any_complexity), + ppl_@CLASS@_equals_@CLASS@(PS, PS_Copy), + ppl_@CLASS@_OK(PS), + ppl_delete_@CLASS@(PS), + ppl_delete_@CLASS@(PS_Copy) + -> + fail ; true) + ). + +') + dnl ppl_@CLASS@_@NARROWING@_narrowing_assign/2, diff --git a/src/termination.cc b/src/termination.cc index 3ba1213..e2749ab 100644 --- a/src/termination.cc +++ b/src/termination.cc @@ -362,7 +362,8 @@ fill_constraint_system_PR(const Constraint_System& cs_before, const dimension_type m = r + s; // Make sure linear expressions are not reallocated multiple times. - le_out = 0 * Variable(m + r - 1); + if (m > 0) + le_out = 0 * Variable(m + r - 1); std::vector<Linear_Expression> les_eq(2*n, le_out); dimension_type row_index = 0; @@ -436,7 +437,8 @@ fill_constraint_system_PR_original(const Constraint_System& cs, const dimension_type m = distance(cs.begin(), cs.end()); // Make sure linear expressions are not reallocated multiple times. - le_out = 0 * Variable(2*m - 1); + if (m > 0) + le_out = 0 * Variable(2*m - 1); std::vector<Linear_Expression> les_eq(3*n, le_out); dimension_type row_index = 0; diff --git a/tests/Polyhedron/termination1.cc b/tests/Polyhedron/termination1.cc index 0d86c03..0bbe66e 100644 --- a/tests/Polyhedron/termination1.cc +++ b/tests/Polyhedron/termination1.cc @@ -491,6 +491,12 @@ test20() { return known_result == witness; } +bool +test21() { + C_Polyhedron ph(2); + return !termination_test_PR(ph); +} + } // namespace BEGIN_MAIN @@ -514,4 +520,5 @@ BEGIN_MAIN DO_TEST(test18); DO_TEST(test19); DO_TEST(test20); + DO_TEST(test21); END_MAIN

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Over_CO_Tree, CO_Tree: major changes. Now all test pass with -DUSE_PPL_SPARSE_BACKEND_CO_TREE.
by Marco Poletti 11 Apr '10

11 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 8bfc24464429dace27dc965c0c5bfcda9b1ee845 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8bfc24464429… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 11 19:12:17 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree, CO_Tree: major changes. Now all test pass with -DUSE_PPL_SPARSE_BACKEND_CO_TREE. --- src/CO_Tree.cc | 289 ++++++++++++- src/CO_Tree.defs.hh | 30 ++- src/CO_Tree.inlines.hh | 211 ++++++++-- src/Makefile.am | 1 + src/Unlimited_Sparse_Row.types.hh | 39 ++ src/Unlimited_Sparse_Row_Over_CO_Tree.cc | 43 ++ src/Unlimited_Sparse_Row_Over_CO_Tree.defs.hh | 29 +- src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh | 450 ++++++++++++++++++-- src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh | 261 ++++++++++++ ...limited_Sparse_Row_Over_Linear_Sequence.defs.hh | 37 +-- ...ed_Sparse_Row_Over_Linear_Sequence.templates.hh | 2 +- tests/CO_Tree/cotree1.cc | 52 +-- 12 files changed, 1277 insertions(+), 167 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=8bfc2446…

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: fix NOISY_PIP section in generate_cut().
by Marco Poletti 11 Apr '10

11 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: eb4d309115ff8e2eb87b8909e91da407f37ab579 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=eb4d309115ff… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 11 18:54:23 2010 +0200 PIP_Solution_Node: fix NOISY_PIP section in generate_cut(). --- src/PIP_Tree.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 97033ca..eb24bfb 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -3330,7 +3330,7 @@ PIP_Solution_Node::generate_cut(const dimension_type index, using namespace IO_Operators; Variables_Set::const_iterator p = parameters.begin(); Linear_Expression expr1(ctx1.get(0)); - Linear_Expression expr2(ctx2_0); + Linear_Expression expr2(ctx2.get(0)); for (dimension_type j = 1; j <= num_params; ++j, ++p) { expr1 += ctx1.get(j) * Variable(*p); expr2 += ctx2.get(j) * Variable(*p);

1 0