July 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(master): Fixed several documentation bugs signalled by Doxygen.
by Roberto Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 0808b5bf178942fd085b4269180af38ed73046b6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0808b5bf1789… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Jul 13 15:55:59 2009 +0200 Fixed several documentation bugs signalled by Doxygen. --- src/Affine_Space.defs.hh | 8 ++++---- src/Grid.defs.hh | 4 ++++ src/Polyhedron.defs.hh | 4 ++++ 3 files changed, 12 insertions(+), 4 deletions(-) diff --git a/src/Affine_Space.defs.hh b/src/Affine_Space.defs.hh index 1d1facf..5d22ff7 100644 --- a/src/Affine_Space.defs.hh +++ b/src/Affine_Space.defs.hh @@ -1192,7 +1192,7 @@ public: /*! \brief Assigns to \p *this the image of \p *this with respect to - the \ref Affine_Space_Generalized_Image "generalized affine relation" + the \ref Generalized_Affine_Relations "generalized affine relation" \f$\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}\f$. @@ -1224,7 +1224,7 @@ public: /*! \brief Assigns to \p *this the preimage of \p *this with respect to the - \ref Affine_Space_Generalized_Image "generalized affine relation" + \ref Generalized_Affine_Relations "generalized affine relation" \f$\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}\f$. @@ -1256,7 +1256,7 @@ public: /*! \brief Assigns to \p *this the image of \p *this with respect to - the \ref Affine_Space_Generalized_Image "generalized affine relation" + the \ref Generalized_Affine_Relations "generalized affine relation" \f$\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}\f$. \param lhs @@ -1280,7 +1280,7 @@ public: /*! \brief Assigns to \p *this the preimage of \p *this with respect to the - \ref Affine_Space_Generalized_Image "generalized affine relation" + \ref Generalized_Affine_Relations "generalized affine relation" \f$\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}\f$. \param lhs diff --git a/src/Grid.defs.hh b/src/Grid.defs.hh index 628638e..5e9d1b3 100644 --- a/src/Grid.defs.hh +++ b/src/Grid.defs.hh @@ -1549,6 +1549,10 @@ public: Possibly tightens \p *this by dropping some points with non-integer coordinates for the space dimensions corresponding to \p vars. + \param vars + Points with non-integer coordinates for these variables/space-dimensions + can be discarded. + \param complexity The maximal complexity of any algorithms used. diff --git a/src/Polyhedron.defs.hh b/src/Polyhedron.defs.hh index 2def5e1..50d27a5 100644 --- a/src/Polyhedron.defs.hh +++ b/src/Polyhedron.defs.hh @@ -1493,6 +1493,10 @@ public: Possibly tightens \p *this by dropping some points with non-integer coordinates for the space dimensions corresponding to \p vars. + \param vars + Points with non-integer coordinates for these variables/space-dimensions + can be discarded. + \param complexity The maximal complexity of any algorithms used.

1 0

[GIT] ppl/ppl(master): Version number bumped.
by Roberto Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: e03b09806640e70bb5a5a00cdf792e422aea3145 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e03b09806640… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Jul 13 15:39:17 2009 +0200 Version number bumped. --- configure.ac | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/configure.ac b/configure.ac index fd5bc8c..f5c46e1 100644 --- a/configure.ac +++ b/configure.ac @@ -23,7 +23,7 @@ # Process this file with Autoconf to produce a configure script. # Every other copy of the package version number gets its value from here. -AC_INIT([the Parma Polyhedra Library], [0.11pre1], [ppl-devel(a)cs.unipr.it], [ppl]) +AC_INIT([the Parma Polyhedra Library], [0.11pre2], [ppl-devel(a)cs.unipr.it], [ppl]) # Minimum Autoconf version required. AC_PREREQ(2.61)

1 0

[GIT] ppl/ppl(master): Removed repeated declaration.
by Abramo Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 9d1496c72855a2a48c036926ec913541c2fe5231 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9d1496c72855… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Mon Jul 13 15:47:56 2009 +0200 Removed repeated declaration. --- src/assert.hh | 11 ----------- 1 files changed, 0 insertions(+), 11 deletions(-) diff --git a/src/assert.hh b/src/assert.hh index 6e8eb39..24e63f1 100644 --- a/src/assert.hh +++ b/src/assert.hh @@ -33,17 +33,6 @@ site: http://www.cs.unipr.it/ppl/ . */ #else -namespace Parma_Polyhedra_Library { - -namespace Implementation { - -//! Non zero during evaluation of PPL_ASSERT expression. -extern unsigned int in_assert; - -} // namespace Implementation - -} // namespace Parma_Polyhedra_Library - #define PPL_DEBUG_PPL_ASSERT 1 #if !PPL_DEBUG_PPL_ASSERT #define PPL_ASSERT(cond__) assert(cond__)

1 0

[GIT] ppl/ppl(master): Moved in_assert in Implementation namespace.
by Abramo Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 18547b9dda76478b54c4d10901dfd9eb5f1ec34a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=18547b9dda76… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Mon Jul 13 15:13:27 2009 +0200 Moved in_assert in Implementation namespace. --- src/assert.hh | 25 ++++++++++++++++--------- src/globals.cc | 16 +++++++++++----- src/globals.inlines.hh | 10 ++++++++-- 3 files changed, 35 insertions(+), 16 deletions(-) diff --git a/src/assert.hh b/src/assert.hh index 4a22012..6e8eb39 100644 --- a/src/assert.hh +++ b/src/assert.hh @@ -26,8 +26,6 @@ site: http://www.cs.unipr.it/ppl/ . */ #include <cassert> #include "globals.defs.hh" -namespace Parma_Polyhedra_Library { - #if defined(NDEBUG) #define PPL_ASSERT(cond__) @@ -35,6 +33,17 @@ namespace Parma_Polyhedra_Library { #else +namespace Parma_Polyhedra_Library { + +namespace Implementation { + +//! Non zero during evaluation of PPL_ASSERT expression. +extern unsigned int in_assert; + +} // namespace Implementation + +} // namespace Parma_Polyhedra_Library + #define PPL_DEBUG_PPL_ASSERT 1 #if !PPL_DEBUG_PPL_ASSERT #define PPL_ASSERT(cond__) assert(cond__) @@ -50,14 +59,12 @@ namespace Parma_Polyhedra_Library { } while(0) #endif -#define PPL_ASSERT_HEAVY(cond__) \ - do { \ - ++Parma_Polyhedra_Library::in_assert; \ - assert(cond__); \ - --Parma_Polyhedra_Library::in_assert; \ +#define PPL_ASSERT_HEAVY(cond__) \ + do { \ + ++Parma_Polyhedra_Library::Implementation::in_assert; \ + assert(cond__); \ + --Parma_Polyhedra_Library::Implementation::in_assert; \ } while (0) #endif -} // namespace Parma_Polyhedra_Library - #endif // !defined(PPL_assert_hh) diff --git a/src/globals.cc b/src/globals.cc index 337190e..1f2c262 100644 --- a/src/globals.cc +++ b/src/globals.cc @@ -26,12 +26,18 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "Constraint.defs.hh" #include "Generator.defs.hh" -namespace PPL = Parma_Polyhedra_Library; +namespace Parma_Polyhedra_Library { -const PPL::Throwable* volatile PPL::abandon_expensive_computations = 0; +const Throwable* volatile abandon_expensive_computations = 0; // Initialize Weightwatch_Traits static data members. -PPL::Weightwatch_Traits::Threshold PPL::Weightwatch_Traits::weight = 0; -void (*PPL::Weightwatch_Traits::check_function)(void) = 0; +Weightwatch_Traits::Threshold Weightwatch_Traits::weight = 0; +void (*Weightwatch_Traits::check_function)(void) = 0; -int PPL::in_assert = 0; +#ifndef NDEBUG +namespace Implementation { +unsigned int in_assert = 0; +} +#endif + +} // namespace Parma_Polyhedra_Library diff --git a/src/globals.inlines.hh b/src/globals.inlines.hh index 80201b6..b3779af 100644 --- a/src/globals.inlines.hh +++ b/src/globals.inlines.hh @@ -53,13 +53,19 @@ Throwable::~Throwable() { } #ifndef NDEBUG -extern int in_assert; +namespace Implementation { + +//! Non zero during evaluation of PPL_ASSERT expression. +extern unsigned int in_assert; + +} // namespace Implementation + #endif inline void maybe_abandon() { #ifndef NDEBUG - if (in_assert) + if (Implementation::in_assert) return; #endif ++Weightwatch_Traits::weight;

1 0

[GIT] ppl/ppl(master): Warnings avoided.
by Roberto Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: b3f9c1cc75c580fac8c0b01741797cd99b421db7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b3f9c1cc75c5… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Jul 13 14:50:55 2009 +0200 Warnings avoided. --- src/Grid_public.cc | 6 ++++-- 1 files changed, 4 insertions(+), 2 deletions(-) diff --git a/src/Grid_public.cc b/src/Grid_public.cc index b5ff074..4b144fa 100644 --- a/src/Grid_public.cc +++ b/src/Grid_public.cc @@ -1242,8 +1242,9 @@ PPL::Grid::add_recycled_grid_generators(Grid_Generator_System& gs) { if (space_dim == 0) { if (marked_empty()) set_zero_dim_univ(); - else + else { PPL_ASSERT(gs.has_points()); + } PPL_ASSERT(OK(true)); return; } @@ -2771,12 +2772,13 @@ PPL::Grid::wrap_assign(const Variables_Set& vars, unconstrain(x); add_constraint(x == v_n); } - else + else { // If overflow is impossible but the grid frequency is less than // half the wrap frequency, then there is more than one possible // value for `x' in the range of the bounded integer type, // so the grid is unchanged. PPL_ASSERT(o == OVERFLOW_IMPOSSIBLE && 2*f_n < wrap_frequency); + } } return; }

1 0

[GIT] ppl/ppl(master): Warnings avoided.
by Roberto Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 78a7c4b60e7e5a9b7b2a6995263ac701105d5ee9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=78a7c4b60e7e… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Jul 13 14:47:51 2009 +0200 Warnings avoided. --- src/Boundary.defs.hh | 12 ++++++++---- 1 files changed, 8 insertions(+), 4 deletions(-) diff --git a/src/Boundary.defs.hh b/src/Boundary.defs.hh index df927c9..db66bbf 100644 --- a/src/Boundary.defs.hh +++ b/src/Boundary.defs.hh @@ -122,10 +122,12 @@ set_minus_infinity(Boundary_Type type, T& x, Info& info, bool open = false) { || std::numeric_limits<T>::has_infinity, "minus infinity is not representable"); */ - if (open) + if (open) { PPL_ASSERT(type == LOWER); - else + } + else { PPL_ASSERT(Info::may_contain_infinity); + } Result r; if (Info::store_special) { PPL_ASSERT(type == LOWER); @@ -148,10 +150,12 @@ set_plus_infinity(Boundary_Type type, T& x, Info& info, bool open = false) { || std::numeric_limits<T>::has_infinity, "minus infinity is not representable"); */ - if (open) + if (open) { PPL_ASSERT(type == UPPER); - else + } + else { PPL_ASSERT(Info::may_contain_infinity); + } Result r; if (Info::store_special) { PPL_ASSERT(type == UPPER);

1 0

[GIT] ppl/ppl(master): Spurious parenthesis removed.
by Roberto Bagnara 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 4b767ed368ed505a43766cceda3a9003a8e515da URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4b767ed368ed… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Mon Jul 13 14:47:39 2009 +0200 Spurious parenthesis removed. --- src/Matrix.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/Matrix.cc b/src/Matrix.cc index 0c59aeb..890f9d8 100644 --- a/src/Matrix.cc +++ b/src/Matrix.cc @@ -35,7 +35,7 @@ PPL::Matrix::Matrix(const dimension_type n_rows, Row::Flags row_flags) : #ifdef NDEBUG - rows(n_rows)), + rows(n_rows), #else rows(n_rows <= max_num_rows() ? n_rows : 0), #endif

1 0

[GIT] ppl/ppl(master): Announced availability of the deterministic timeout facilities.
by Enea Zaffanella 13 Jul '09

13 Jul '09

Module: ppl/ppl Branch: master Commit: 35bcf04d2922768393bb5e2551e51e5a99bc4bdb URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=35bcf04d2922… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Mon Jul 13 14:32:04 2009 +0200 Announced availability of the deterministic timeout facilities. --- NEWS | 6 ++++++ 1 files changed, 6 insertions(+), 0 deletions(-) diff --git a/NEWS b/NEWS index adb43c5..6543155 100644 --- a/NEWS +++ b/NEWS @@ -20,6 +20,12 @@ o When the PPL has been configured with o New configure option --with-gmp-prefix supersedes the (now removed) options --with-libgmp-prefix and --with-libgmpxx-prefix. +o New "deterministic" timeout computation facilities: it is now possible + to set computational bounds (on the library calls taking exponential time) + that do not depend on the actual elapsed time and hence are independent + from the actual computation environment (CPU, operating system, etc.). + Still under alpha testing. + o The Java interface has to be explicitly initialized before use by calling static method Parma_Polyhedra_Library.initialize_library(). Initialization makes more explicit the exact point where PPL

1 0

[GIT] ppl/ppl(master): Converted assert in PPL_ASSERT.
by Abramo Bagnara 13 Jul '09

13 Jul '09

1 0

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

13 Jul '09

On Fri, 2009-07-10 at 23:57 +0200, Albert Cohen wrote: > Hi Tobias. > > Tobias Grosser wrote: > > 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. > > As presented in Austin in November, it is much preferable to follow the > transformation composition approach of Girbal and Vasilache that does > not require intermediate steps of dependence analysis and legality checking. You are referring to "Facilitating the search for compositions of program transformations"? > In this framework, the typical/ideal flow of transformation construction > is the following: > > 1. Compute dependence relations for all pairs and store it persistently. > > 2. Select a primitive transformation and apply it to the polyhedral > representation. > 2.1. If the transformation involved strip-mining, update the > dependence information such that all the polyhedra associated with the > strip-mined statements get one extra "time column" filled only with > zeroes; you may check that this is correct and strictly equivalent to > recomputing dependence information in the case of the isolated > application of strip-mining (not composed with other transformations) > and of an exact integral polyhedral computation. > > 3. If the transformation computed so far is not good enough, compose > with another one by iterating to step 2. For example, start with > strip-mining, then interchange, to achieve tiling. Of course, much more > complex schemes should be crafted later on. > > 4. When you are sick of composing more and more primitive > transformations into a big complex one, check the legality of the result > by comparing the transformed schedule with the stored dependence > relations (updated through the strip-mining steps). > > Of course, Step 2 should be a little careful to select only > transformations that will not cause trouble later in step 4. A simple > way is to add a Step 2.2 that checks for legality after transforming the > schedule, and backtracks if it fails, attempting another transformation > selection. Thanks for explaining. > Konrad is working on Step 2.1 (enhancing strip-mine to update the > dependence info). Then, if you agree, he will help restructure the API > such a that dependence computation and dependence checking are ALWAYS > called explicitely, rather than implicitely in the transformation > primitives. Sure. I would like us to be even able to call them after any single transformation. A loop like would be nice for the optimizations. while (select_and_apply_transform (scop)) { check_dependencies(); } I know this will be expensive and we want to disable this in the production compiler. But I want us to be able to use this loop for debugging. > > If you do not agree or fully understand the motivations for this scheme, > I'm happy to discuss it further, but I'll be barely available next week > due to an overload of paper deadlines and the ACACES summer school of > the HiPEAC network (where I would gladly invite you to apply, for next > year :-)). > > > 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? > > No, as explained above, we only want to avoid running dependence > ANALYSIS after applying transformations. Running dependence CHECK for > legality should be fine, although for compilation time reasons it is > better to avoid it whenever possible (other concrete algorithms exist to > correct transformations, complement transformations, or constrain > transformations to span only legal points, but we can look at this later). I totally agree that it is useful to avoid polyhedral computations, as they tend to be expensive. However I still want to be able to do CHECK and ANALYSIS at every single step, as it will show us assumptions that we took to optimize compile time. If we take any assumptions (that might be necessary), I would like them to not be hidden by avoiding dependency ANALYSIS, but I want our (nightly) test to fail. This will allow a analysis/discussion of the assumptions we took. Maybe we can avoid them, if not we know we have to document them. Every assumption has to be written down at a well known place so that future developers will not be surprised. > > 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? > > As mentioned several times, big constants tend to break the "structure" > of ILP problems or other polyhedral operations, leading to combinatorial > explosions. This is well known even in the case of simple algorithms > like Fourier Motzkin. They also increase the risk of memory overflow. OK. I definitely believe you, but as this seems to become one of the important points for Graphite performance I would like to understand this well. Maybe we can also write a Wiki page to explain which constructs should be avoided. We already learned NNC_Polyhedron are bad, but what else is dangerous. Here I am still not getting the problem. I looked again into Fourier Motzkin and on the first look I could not find anything in it's complexity depending on the values of the dimensions of the (in)equalities. Any pointer or example that might help me understanding this problem would be really helpful. > Eventually, the bigger the constant the higher the loss of information > when relaxing to rational polyhedra. OK. However when we do not put the additional restrictions the information would never have been available. Or are we loosing other information because of putting additional restrictions? > All of this is very informal/intuitive of course. There are some/few > theoretical results about this, but Roberto and other experts are better > placed than myself to answer it! @Roberto: Can you give us some hints, what is really expensive and what should we avoid when constructing polyhedrons in the PPL? Tobi

3 2