July 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Forgotten file.
by Abramo Bagnara 11 Jul '09

11 Jul '09

Module: ppl/ppl Branch: master Commit: 99d4c96253e1e775d022baaa67e496ccd8b14fe4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=99d4c96253e1… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Sat Jul 11 18:14:42 2009 +0200 Forgotten file. --- Watchdog/src/Weightwatch.cc | 36 ++++++++++++++++++++++++++++++++++++ 1 files changed, 36 insertions(+), 0 deletions(-) diff --git a/Watchdog/src/Weightwatch.cc b/Watchdog/src/Weightwatch.cc new file mode 100644 index 0000000..821d04f --- /dev/null +++ b/Watchdog/src/Weightwatch.cc @@ -0,0 +1,36 @@ +/* Weightwatch and associated classes' implementation (non-inline functions). + Copyright (C) 2001-2009 Roberto Bagnara <bagnara(a)cs.unipr.it> + +This file is part of the Parma Watchdog Library (PWL). + +The PWL is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3 of the License, or (at your +option) any later version. + +The PWL is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software Foundation, +Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. + +For the most up-to-date information see the Parma Polyhedra Library +site: http://www.cs.unipr.it/ppl/ . */ + +#include <pwl-config.h> + +#include "Weightwatch.defs.hh" + +namespace Parma_Watchdog_Library { + +#if 0 +// The ordered queue of pending thresholds. +Weightwatch::WW_Pending_List Weightwatch::pending; + +void (**Weightwatch::check_hook_ptr)(void) = 0; +#endif + +}

1 0

[GIT] ppl/ppl(master): Weightwatch are now generic threshold watchdog.
by Abramo Bagnara 11 Jul '09

11 Jul '09

Module: ppl/ppl Branch: master Commit: d8e99fc18a85d66fad6977a5e4e84f88e42cbebd URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8e99fc18a85… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Sat Jul 11 18:13:39 2009 +0200 Weightwatch are now generic threshold watchdog. --- Watchdog/src/Makefile.am | 3 +- Watchdog/src/Pending_List.defs.hh | 2 +- Watchdog/src/Pending_List.inlines.hh | 30 +++++----- Watchdog/src/Pending_List.templates.hh | 26 ++++---- Watchdog/src/Pending_List.types.hh | 2 +- Watchdog/src/Watchdog.defs.hh | 3 +- Watchdog/src/Weightwatch.cc | 96 -------------------------------- Watchdog/src/Weightwatch.defs.hh | 53 ++++++++--------- Watchdog/src/Weightwatch.inlines.hh | 18 +++--- Watchdog/src/Weightwatch.templates.hh | 77 +++++++++++++++++++++++++ Watchdog/src/Weightwatch.types.hh | 3 +- 11 files changed, 148 insertions(+), 165 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=d8e99fc1…

1 0

[GIT] ppl/ppl(master): Weightwatch are now independent from client code.
by Abramo Bagnara 11 Jul '09

11 Jul '09

Module: ppl/ppl Branch: master Commit: a2845d7717669addb44c47793cd92446b51751a0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a2845d771766… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Sat Jul 11 14:07:36 2009 +0200 Weightwatch are now independent from client code. --- Watchdog/src/Weightwatch.cc | 64 ++++++++++++++++++++++++++-------- Watchdog/src/Weightwatch.defs.hh | 21 ++++++++--- Watchdog/src/Weightwatch.inlines.hh | 22 ------------ 3 files changed, 64 insertions(+), 43 deletions(-) diff --git a/Watchdog/src/Weightwatch.cc b/Watchdog/src/Weightwatch.cc index 1da5575..7dae6c9 100644 --- a/Watchdog/src/Weightwatch.cc +++ b/Watchdog/src/Weightwatch.cc @@ -29,34 +29,68 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <string> #include <string.h> -namespace PWL = Parma_Watchdog_Library; +namespace Parma_Watchdog_Library { // The ordered queue of pending weight thresholds. -PWL::Weightwatch::WW_Pending_List PWL::Weightwatch::pending; +Weightwatch::WW_Pending_List Weightwatch::pending; -PWL::Weight PWL::Weightwatch::weight_so_far = 0; +Weight* Weightwatch::current_weight_ptr = 0; +void (**Weightwatch::check_hook_ptr)(void) = 0; -PWL::Weightwatch::WW_Pending_List::Iterator -PWL::Weightwatch::new_weight_threshold(int units, +#ifndef NDEBUG +Weight Weightwatch::previous_weight = 0; +#endif + +Weightwatch::WW_Pending_List::Iterator +Weightwatch::new_weight_threshold(int units, const Handler& handler, bool& expired_flag) { assert(units > 0); - if (weight_so_far == 0) - weight_so_far = 1; - return pending.insert(weight_so_far + units, handler, expired_flag); + assert(current_weight_ptr); + *check_hook_ptr = Weightwatch::check; + return pending.insert(*current_weight_ptr + units, handler, expired_flag); } -void -PWL::Weightwatch::remove_weight_threshold(WW_Pending_List::Iterator position) { - pending.erase(position); +Weightwatch::WW_Pending_List::Iterator +Weightwatch::remove_weight_threshold(WW_Pending_List::Iterator position) { + Weightwatch::WW_Pending_List::Iterator i = pending.erase(position); if (pending.empty()) - weight_so_far = 0; + *check_hook_ptr = 0; + return i; } -PWL::Weightwatch::~Weightwatch() { - if (!expired) { +Weightwatch::~Weightwatch() { + if (!expired) remove_weight_threshold(pending_position); - } delete &handler; } +void +Weightwatch::check() { + assert(current_weight_ptr); + WW_Pending_List::Iterator i = pending.begin(); + assert(i != pending.end()); + assert(*current_weight_ptr - previous_weight < 1U << (sizeof(Weight)*8-1)); +#ifndef NDEBUG + previous_weight = *current_weight_ptr; +#endif + while (*current_weight_ptr - i->deadline() < 1U << (sizeof(Weight)*8-1)) { + i->handler().act(); + i->expired_flag() = true; + i = remove_weight_threshold(i); + if (i == pending.end()) + break; + } +} + +void +Weightwatch::initialize(Weight& current_weight, void (*&check_hook)(void)) { + current_weight_ptr = &current_weight; + check_hook_ptr = &check_hook; + check_hook = 0; +#ifndef NDEBUG + previous_weight = current_weight; +#endif +} + +} diff --git a/Watchdog/src/Weightwatch.defs.hh b/Watchdog/src/Weightwatch.defs.hh index dfa4c04..f22de5d 100644 --- a/Watchdog/src/Weightwatch.defs.hh +++ b/Watchdog/src/Weightwatch.defs.hh @@ -30,7 +30,7 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace Parma_Watchdog_Library { -typedef unsigned long long Weight; +typedef unsigned int Weight; //! A watchdog for computational weight. class Weightwatch { @@ -40,8 +40,7 @@ public: Weightwatch(int units, void (*function)()); ~Weightwatch(); - static void add(unsigned int units, unsigned int iterations); - static void check(); + static void initialize(Weight& current_weight, void (*&check_hook)(void)); private: typedef Pending_List<Weight> WW_Pending_List; @@ -58,8 +57,16 @@ private: //! The ordered queue of pending weight thresholds. static WW_Pending_List pending; - //! Current weight. - static Weight weight_so_far; + //! Pointer to current weight. + static Weight *current_weight_ptr; + + //! Pointer to check hook. + static void (**check_hook_ptr)(void); + +#ifndef NDEBUG + //! Weight at previous check. + static Weight previous_weight; +#endif // Handle the addition of a new weight threshold. static WW_Pending_List::Iterator new_weight_threshold(int units, @@ -67,8 +74,10 @@ private: bool& expired_flag); // Handle the removal of a weight threshold. - void remove_weight_threshold(WW_Pending_List::Iterator position); + static WW_Pending_List::Iterator remove_weight_threshold(WW_Pending_List::Iterator position); + //! Check weight threshold reaching. + static void check(); }; } // namespace Parma_Watchdog_Library diff --git a/Watchdog/src/Weightwatch.inlines.hh b/Watchdog/src/Weightwatch.inlines.hh index 8102799..e792449 100644 --- a/Watchdog/src/Weightwatch.inlines.hh +++ b/Watchdog/src/Weightwatch.inlines.hh @@ -48,28 +48,6 @@ Weightwatch::Weightwatch(int units, void (*function)()) pending_position = new_weight_threshold(units, handler, expired); } -inline void -Weightwatch::add(unsigned int units, unsigned int iterations) { - if (weight_so_far == 0) - return; - weight_so_far += (Weight)units * iterations; -} - -inline void -Weightwatch::check() { - if (weight_so_far == 0) - return; - WW_Pending_List::Iterator i = pending.begin(); - assert(i != pending.end()); - while (weight_so_far >= i->deadline()) { - i->handler().act(); - i->expired_flag() = true; - i = pending.erase(i); - if (i == pending.end()) - weight_so_far = 0; - } -} - } // namespace Parma_Watchdog_Library #endif // !defined(PWL_Weightwatch_inlines_hh)

1 0

Re: [PPL-devel] integer versus rational solutions
by Tobias Grosser 10 Jul '09

10 Jul '09

On Fri, 2009-07-10 at 17:23 +0200, Albert Cohen wrote: > Thank you Roberto for the long and detailed email. > > Indeed, we should keep in mind to always ask on the ppl mailing list > early on. > > Regarding the need to solve integer programming problems, my view is > twofold: > 1. For the case of Array Dataflow Analysis, it is critical to have a > parametric integer linear programming solver, in the form of the > evolution of PIP you are working on. We can leave without it for early > experiments, but it will be needed for any scalable (and precise) analysis. > 2. For plain dependence analysis and testing (the problem that triggered > the whole thread), it is certainly not critical. It would of course > improve precision, but the problems raised by Konrad and Li were due to > a wrong design that was re-analysing the polyhedral representation AFTER > strip-mining of loops, itself responsible for the introduction of large > constants. Konrad is updating the dependence analysis and the > strip-minig API such that this won't be necessary anymore. Stop. Do I understand this correctly. You do not want to check dependencies after strip mining? I am very concerned about that, as one of the benefits of working on the polytop model I thought is, that we can schedule transformations in an arbitrary order. So it is required to to reanalyze strip mined loops. This is also necessary for the dependency checking we use for autopar. It would be nice to read a post about what assumptions/solutions you want to take to make sure this complexity problems will not appear again. Do they limit our ability to run optimizations after we strip mined a loop? Another thing I do not understand is that you are often referring to "large constants". I thought complexity problems mainly appear because of a high number of dimensions, but not because of high values in a (in)equality. Can you explain this to me? Thanks Tobi

2 1

[GIT] ppl/ppl(master): Added Weightwatch.
by Abramo Bagnara 10 Jul '09

10 Jul '09

Module: ppl/ppl Branch: master Commit: 98c1aa19dbcd4f9920f523ed54b5928a4c66a5bc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=98c1aa19dbcd… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Fri Jul 10 21:20:57 2009 +0200 Added Weightwatch. --- Watchdog/src/EList.inlines.hh | 2 + Watchdog/src/Makefile.am | 11 ++- Watchdog/src/Pending_Element.cc | 32 -------- Watchdog/src/Pending_Element.defs.hh | 10 +- Watchdog/src/Pending_Element.inlines.hh | 33 ++++++--- Watchdog/src/Pending_Element.types.hh | 1 + Watchdog/src/Pending_List.defs.hh | 14 ++- Watchdog/src/Pending_List.inlines.hh | 26 ++++-- .../{Pending_List.cc => Pending_List.templates.hh} | 36 ++++++---- Watchdog/src/Pending_List.types.hh | 1 + Watchdog/src/Watchdog.cc | 12 ++-- Watchdog/src/Watchdog.defs.hh | 9 +- Watchdog/src/Weightwatch.cc | 62 +++++++++++++++ Watchdog/src/Weightwatch.defs.hh | 79 ++++++++++++++++++++ Watchdog/src/Weightwatch.inlines.hh | 75 +++++++++++++++++++ Watchdog/src/Weightwatch.types.hh | 19 +++++ 16 files changed, 333 insertions(+), 89 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=98c1aa19…

1 0

[GIT] ppl/ppl(master): Fixed a (potential) exception safety bug in class MIP_Problem.
by Enea Zaffanella 10 Jul '09

10 Jul '09

Module: ppl/ppl Branch: master Commit: 9806b1f8969f83070f4c3b5e8ac850132c2ea8b1 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9806b1f8969f… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Jul 10 18:05:14 2009 +0200 Fixed a (potential) exception safety bug in class MIP_Problem. Added an helper class (implementing RAII technique) to safely relax a MIP problem into an LP problem and ensure that integer variables are restored even in the presence of exceptional execution paths. Improved interface (and a few comments) for private methods dealing with MIP optimization and satisfiability. --- src/MIP_Problem.cc | 130 ++++++++++++++++++++++------------------------ src/MIP_Problem.defs.hh | 57 ++++++++++++++------- 2 files changed, 101 insertions(+), 86 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=9806b1f8…

1 0

Re: [PPL-devel] integer versus rational solutions
by Roberto Bagnara 10 Jul '09

10 Jul '09

Konrad Trifunovic wrote: > I attach a patch that uses 'integer existence test'. > I have forced the use of dependence check. Hi there. I am sorry if the answer is obvious, but I am wondering why you are using NNC polyhedra (NNC_Polyhedron) instead of ordinary polyhedra (C_Polyhedron). Do you need to characterize rational solutions and use strict constraints? All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

4 9

Re: [PPL-devel] integer versus rational solutions
by Roberto Bagnara 10 Jul '09

10 Jul '09

Sebastian Pop wrote: > On Thu, Jul 9, 2009 at 07:12, Michael > Classen<michael.classen(a)uni-passau.de> wrote: >> Maybe it could also be possible to use the Parma Watchdog Library >> (PWL) for providing a timeout for the precise method and falling back >> to the more conservative method once a certain timeout is reached? > > Not in GCC. > This would make the compiler non deterministic. We have developed a deterministic alternative. Give us a couple of days to migrate it into the main Git repository. Cheers, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

2 1

[GIT] ppl/ppl(products): Corrected test as already corrected in the master branch.
by Patricia Hill 09 Jul '09

09 Jul '09

Module: ppl/ppl Branch: products Commit: bbb1ff43e555dabda36b8d5838092ebade985c54 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bbb1ff43e555… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Thu Jul 9 14:30:29 2009 +0100 Corrected test as already corrected in the master branch. --- tests/Box/congruences1.cc | 6 ++---- 1 files changed, 2 insertions(+), 4 deletions(-) diff --git a/tests/Box/congruences1.cc b/tests/Box/congruences1.cc index 39158d0..ed1be18 100644 --- a/tests/Box/congruences1.cc +++ b/tests/Box/congruences1.cc @@ -142,16 +142,14 @@ test06() { Congruence_System cgs; cgs.insert((A %= 7) / 0); cgs.insert((B %= 3) / 0); - // This inconsistent equality is ignored when refining. + // This inconsistent equality is not ignored when refining. cgs.insert((A + B %= 0) / 0); cgs.insert(C %= 7); TBox box(cgs.space_dimension(), UNIVERSE); box.refine_with_congruences(cgs); - Rational_Box known_result(3); - known_result.add_constraint(A == 7); - known_result.add_constraint(B == 3); + Rational_Box known_result(3, EMPTY); bool ok = check_result(box, known_result);

1 0

Re: [PPL-devel] integer versus rational solutions
by Roberto Bagnara 09 Jul '09

09 Jul '09

Michael Classen wrote: > On Wed, Jul 8, 2009 at 3:32 AM, Konrad > Trifunovic<konrad.trifunovic(a)gmail.com> wrote: >> I tried to reduce the size of the iteration domains and size of the >> matrices (in the original block-1.c). It seems that PPL is not able to >> deal with efficiently with big constants... Hi Konrad, I don't understand. What do you mean by "PPL is not able to deal with efficiently with big constants"? How can we reproduce your observations? All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

2 1