May 2010 - PPL-devel - BUGSENG Mailman

Problems with test suite on alpha
by Michael Tautschnig 09 Sep '10

09 Sep '10

Hi PPL developers, I've reported problems with some test cases because of suspected gcc bugs on alpha earlier already. Now it seems that even more test cases are broken, most probably because of the very same bug (I suspect it to be http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966). My question now is: How to proceed? Shall I specifically disable the failing test cases by surrounding them with an #ifndef __alpha__ or disable the entire test suite on alpha? Thanks, Michael

2 6

Powerset of a set of convex sets.
by Amit Bhatia 26 May '10

26 May '10

Hello, I am a new user of PPL, and am trying to do the following using PPL. I have a bunch of convex sets (represented as intersection of half spaces), and would like to find the non empty elements of the powerset of this set of convex sets. It involves checking set intersections. I am wondering if PPL provides an elegant and efficient way to do this? The only other option I can think of is to consider every possible subset of the set, and then check for intersection by checking for feasibility using linear programming. thanks, amit.

2 1

Examples on using PPL.
by Amit Bhatia 25 May '10

25 May '10

Hi, I am a new user of PPL, and am trying to learn to use PPL. I was wondering if there are some examples that show how to use PPL? I looked in the documentation, but it provides details on classes and so on, but I could not find examples. thanks, amit.

2 1

Fwd: [Caml-list] A Tutorial on GNU Make with OCaml
by Roberto Bagnara 21 May '10

21 May '10

-------- Original Message -------- Subject: [Caml-list] A Tutorial on GNU Make with OCaml Date: Thu, 20 May 2010 23:53:14 -0400 From: Jeff Shaw <shawjef3(a)msu.edu> To: caml-list(a)inria.fr Dear OCamlers, I spent quite a lot of time today getting better acquainted with GNU make and decided I to share my experience and results. It's a bit on the newbie friendly side of instruction. http://shawjeff.blogspot.com/2010/05/this-is-storytutorial-about-how-i_20.h… I hope someone finds it helpful! Jeff Shaw shawjef3(a)msu.edu _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs

1 0

[GIT] ppl/w3ppl(master): Fixed CousotC79.
by Roberto Bagnara 16 May '10

16 May '10

Module: ppl/w3ppl Branch: master Commit: d94cb0c0ac21d2be3e299da99dfd6f0d4c705a31 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=d94cb0c0ac… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Sun May 16 11:24:48 2010 +0200 Fixed CousotC79. --- htdocs/Documentation/ppl.bib | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/htdocs/Documentation/ppl.bib b/htdocs/Documentation/ppl.bib index ccafdd8..f90eb93 100644 --- a/htdocs/Documentation/ppl.bib +++ b/htdocs/Documentation/ppl.bib @@ -1349,7 +1349,7 @@ Booktitle = "Proceedings of the Sixth Annual ACM Symposium on Principles of Programming Languages", Publisher = "ACM Press", - Address = "New York", + Address = "San Antonio, TX, USA", Pages = "269--282", Year = 1979, Abstract = "Semantic analysis of programs is essential in optimizing

1 0

Re: [PPL-devel] Merge from Graphite to trunk
by Roberto Bagnara 11 May '10

11 May '10

On 05/07/10 00:01, Sebastian Pop wrote: > 0003 allows GCC to use later versions of PPL, not only PPL-0.10. > PPL-0.11 will be released sometimes in May, but it is not yet > required to build GCC as we do not use its extra functionality (i.e., > the PIP "parametric integer programming" solver). Another > patch will require PPL-0.11 or later when the data dependence > analysis will use PIP. Hi there. Marco Poletti, in CC, is working on several alternative implementations of sparse matrices to be used in the PPL, particularly in the PIP solver. So this is the right time to provide us with examples, preferably tough ones, to experiment with. Cheers, Roberto -- Prof. Roberto Bagnara Applied Formal Methods Laboratory Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

[GIT] ppl/ppl(sparse_matrices): PIP_Solution_Node: optimize solve() method for sparse matrices.
by Marco Poletti 11 May '10

11 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 44c4824bb28d3d9c8bc263dd11e8ce2741e3396e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=44c4824bb28d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon May 10 21:32:55 2010 +0200 PIP_Solution_Node: optimize solve() method for sparse matrices. --- src/PIP_Tree.cc | 18 ++++++++++++------ 1 files changed, 12 insertions(+), 6 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b6683c8..57f1eb0 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2767,8 +2767,10 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, } PPL_ASSERT(product % s_pivot_pj == 0); exact_div_assign(product, product, s_pivot_pj); - s_i.find_create_hint_assign(j->first, itr); - itr->second -= product; + if (product != 0) { + s_i.find_create_hint_assign(j->first, itr); + itr->second -= product; + } } } } @@ -2793,7 +2795,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, } PPL_ASSERT(product % s_pivot_pj == 0); exact_div_assign(product, product, s_pivot_pj); - s_i[j->first] -= product; + if (product != 0) + s_i[j->first] -= product; } } } @@ -2868,8 +2871,10 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, } PPL_ASSERT(product % s_pivot_pj == 0); exact_div_assign(product, product, s_pivot_pj); - t_i.find_create_hint_assign(j->first, k); - k->second -= product; + if (product != 0) { + t_i.find_create_hint_assign(j->first, k); + k->second -= product; + } // Update row sign. Row_Sign& sign_i = sign[i]; @@ -2912,7 +2917,8 @@ PIP_Solution_Node::solve(const PIP_Problem& pip, } PPL_ASSERT(product % s_pivot_pj == 0); exact_div_assign(product, product, s_pivot_pj); - t_i[j->first] -= product; + if (product != 0) + t_i[j->first] -= product; // Update row sign. Row_Sign& sign_i = sign[i];

1 0

[GIT] ppl/ppl(master): Moved Katy Dobson to the list of past contributors.
by Roberto Bagnara 10 May '10

10 May '10

Module: ppl/ppl Branch: master Commit: 24d6f3e03340f2c8ae7ded09b2087bd22c71e31e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=24d6f3e03340… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon May 10 14:04:20 2010 +0200 Moved Katy Dobson to the list of past contributors. --- CREDITS | 20 ++++++++++---------- 1 files changed, 10 insertions(+), 10 deletions(-) diff --git a/CREDITS b/CREDITS index b96409d..6ba8c92 100644 --- a/CREDITS +++ b/CREDITS @@ -56,15 +56,10 @@ Current Contributors: at the implementation of the Parametric Integer Programming solver. - Katy Dobson [4] (University of Leeds) is working on the - formalization and definition of algorithms for - rational grids and products of grids and - polyhedra. - - Enric Rodriguez Carbonell [5] (Technical University of Catalonia) is + Enric Rodriguez Carbonell [4] (Technical University of Catalonia) is working on the implementation of polynomial spaces. - Alessandro Zaccagnini [6] (University of Parma) has helped with + Alessandro Zaccagnini [5] (University of Parma) has helped with the efficient implementation of GCD and LCM for checked numbers. He is now working on the definitions of interval arithmetic operations. @@ -93,6 +88,11 @@ Past Contributors: one of the four students with which the PPL project started. + Katy Dobson [6] (University of Leeds) worked on the + formalization and definition of algorithms for + rational grids and products of grids and + polyhedra. + Giordano Fracasso (University of Parma) wrote the initial version of the support for native and checked integer coefficients. @@ -362,9 +362,9 @@ projects and organizations: [2] http://www.comp.leeds.ac.uk/hill/ [3] http://www.cs.unipr.it/~zaffanella/ [*] http://www.prism.uvsq.fr/~fgalea/ - [4] http://www.comp.leeds.ac.uk/katyd/ - [5] http://www.lsi.upc.edu/~erodri/ - [6] http://www.math.unipr.it/~zaccagni/ + [4] http://www.lsi.upc.edu/~erodri/ + [5] http://www.math.unipr.it/~zaccagni/ + [6] http://www.comp.leeds.ac.uk/katyd/ [7] http://www.mundell.ukfsn.org/ [8] http://www.irisa.fr/lande/fbesson/fbesson.html [9] http://www.cs.ucsb.edu/~bultan/

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize further lower_bound() for the DFS layout.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 4f4c3d79d1458b66d21c2cf5041c1ad7cc28ffd9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4f4c3d79d145… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun May 9 12:42:47 2010 +0200 CO_Tree: optimize further lower_bound() for the DFS layout. --- src/CO_Tree.inlines.hh | 88 ++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 86 insertions(+), 2 deletions(-) diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index f91f8ac..391894e 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -366,7 +366,49 @@ CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { return; dimension_type low_index = itr.i; - dimension_type high_index = reserved_size; + dimension_type high_index; + + // Logarithmic search of an interval in which the key will be searched. + // Near (and small) intervals are tried first, to exploit the caches. + { + dimension_type hop = 1; + dimension_type last_low_index = low_index; + + while (1) { + + if (low_index > reserved_size) + low_index = reserved_size + 1; + else + while (indexes[low_index] == unused_index) + ++low_index; + + PPL_ASSERT(indexes[low_index] != unused_index); + + if (low_index > reserved_size) { + PPL_ASSERT(low_index <= reserved_size + 1); + high_index = low_index - 1; + low_index = last_low_index; + break; + } + + if (indexes[low_index] == key) { + itr.i = low_index; + return; + } + + if (indexes[low_index] > key) { + high_index = low_index - 1; + low_index = last_low_index; + break; + } + + PPL_ASSERT(indexes[low_index] < key); + + last_low_index = low_index; + low_index += hop; + hop *= 2; + } + } PPL_ASSERT(low_index > 0); @@ -461,7 +503,49 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { return; dimension_type low_index = itr.i; - dimension_type high_index = reserved_size; + dimension_type high_index; + + // Logarithmic search of an interval in which the key will be searched. + // Near (and small) intervals are tried first, to exploit the caches. + { + dimension_type hop = 1; + dimension_type last_low_index = low_index; + + while (1) { + + if (low_index > reserved_size) + low_index = reserved_size + 1; + else + while (indexes[low_index] == unused_index) + ++low_index; + + PPL_ASSERT(indexes[low_index] != unused_index); + + if (low_index > reserved_size) { + PPL_ASSERT(low_index <= reserved_size + 1); + high_index = low_index - 1; + low_index = last_low_index; + break; + } + + if (indexes[low_index] == key) { + itr.i = low_index; + return; + } + + if (indexes[low_index] > key) { + high_index = low_index - 1; + low_index = last_low_index; + break; + } + + PPL_ASSERT(indexes[low_index] < key); + + last_low_index = low_index; + low_index += hop; + hop *= 2; + } + } PPL_ASSERT(low_index > 0);

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize go_down_searching_key() for the DFS layout.
by Marco Poletti 09 May '10

09 May '10

Module: ppl/ppl Branch: sparse_matrices Commit: 633bb9f9ad12fb4995c3dee47e111bfd09c02b4f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=633bb9f9ad12… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat May 8 18:35:00 2010 +0200 CO_Tree: optimize go_down_searching_key() for the DFS layout. --- src/CO_Tree.defs.hh | 6 +-- src/CO_Tree.inlines.hh | 132 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 134 insertions(+), 4 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 21fcd1e..c185103 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -583,8 +583,7 @@ private: //! The tree the iterator points to. const CO_Tree* tree; - friend dimension_type - CO_Tree::count_used_in_subtree(inorder_const_iterator& itr); + friend class CO_Tree; }; class CO_Tree::inorder_iterator { @@ -743,8 +742,7 @@ private: friend inorder_const_iterator& inorder_const_iterator::operator=(const inorder_iterator&); - friend dimension_type - CO_Tree::count_used_in_subtree(inorder_iterator& itr); + friend class CO_Tree; }; } // namespace Parma_Polyhedra_Library diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 8797d65..f91f8ac 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -353,7 +353,71 @@ CO_Tree::go_down_searching_key(inorder_const_iterator& itr, inline void CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { +#ifdef USE_PPL_CO_TREE_DFS_LAYOUT + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_before_begin()) + ++itr; + + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_at_end()) + return; + + dimension_type low_index = itr.i; + dimension_type high_index = reserved_size; + + PPL_ASSERT(low_index > 0); + + while (low_index + 1 < high_index) { + + dimension_type avg = (low_index + high_index) / 2; + dimension_type index = avg; + + while (indexes[index] == unused_index) + ++index; + + if (index > high_index || indexes[index] > key) { + high_index = avg; + } else { + low_index = index; + } + } + + if (low_index == high_index) { + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + while (indexes[low_index] == unused_index) + ++low_index; + + } else { + PPL_ASSERT(low_index + 1 == high_index); + if (indexes[low_index] == unused_index || indexes[low_index] < key) { + ++low_index; + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + } + while (indexes[low_index] == unused_index) + ++low_index; + } + + itr.i = low_index; + +#ifndef NDEBUG + inorder_iterator itr2 = itr; + itr2.get_previous_value(); + PPL_ASSERT(itr2.is_before_begin() || itr2->first < key); + itr2.get_next_value(); + PPL_ASSERT(itr2 == itr); +#endif + + PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT) + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); if (itr->first <= key) while (itr.has_parent() && itr->first < key) itr.get_parent(); @@ -378,11 +442,77 @@ CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) { itr.get_next_value(); #endif PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } inline void CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { +#ifdef USE_PPL_CO_TREE_DFS_LAYOUT + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_before_begin()) + ++itr; + + PPL_ASSERT(itr.is_at_end() || itr->first <= key); + + if (itr.is_at_end()) + return; + + dimension_type low_index = itr.i; + dimension_type high_index = reserved_size; + + PPL_ASSERT(low_index > 0); + + while (low_index + 1 < high_index) { + + dimension_type avg = (low_index + high_index) / 2; + dimension_type index = avg; + + while (indexes[index] == unused_index) + ++index; + + if (index > high_index || indexes[index] > key) { + high_index = avg; + } else { + low_index = index; + } + } + + if (low_index == high_index) { + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + while (indexes[low_index] == unused_index) + ++low_index; + + } else { + PPL_ASSERT(low_index + 1 == high_index); + if (indexes[low_index] == unused_index || indexes[low_index] < key) { + ++low_index; + if (indexes[low_index] == unused_index || indexes[low_index] < key) + ++low_index; + } + while (indexes[low_index] == unused_index) + ++low_index; + } + + itr.i = low_index; + +#ifndef NDEBUG + inorder_const_iterator itr2 = itr; + itr2.get_previous_value(); + PPL_ASSERT(itr2.is_before_begin() || itr2->first < key); + itr2.get_next_value(); + PPL_ASSERT(itr2 == itr); +#endif + + PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT) + PPL_ASSERT(!empty()); + PPL_ASSERT(itr.is_at_end() || itr->first <= key); if (itr->first <= key) while (itr.has_parent() && itr->first < key) itr.get_parent(); @@ -407,6 +537,8 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { itr.get_next_value(); #endif PPL_ASSERT(itr.is_at_end() || itr->first >= key); + +#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } inline void

1 0