[Fwd: Re: patch for merging graphite branch (before tuplification)]
-------- Original Message -------- Subject: Re: patch for merging graphite branch (before tuplification) Date: Sat, 2 Aug 2008 19:26:18 -0500 From: Sebastian Pop sebpop@gmail.com To: Richard Guenther richard.guenther@gmail.com CC: GCC Patches gcc-patches@gcc.gnu.org, Mark Mitchell mark@codesourcery.com, Jakub Jelinek jakub@redhat.com, David Edelsohn edelsohn@gmail.com, Harle, Christophe christophe.harle@amd.com, Tobias Grosser grosser@fim.uni-passau.de, Konrad Trifunovic konrad.trifunovic@gmail.com, Albert Cohen Albert.Cohen@inria.fr, Roberto Bagnara bagnara@cs.unipr.it References: cb9d34b20807251914jb7fb76q4452be18461d7464@mail.gmail.com 84fc9c000807260228h12552595x17b2a7556d35913b@mail.gmail.com
Hi,
The graphite branch has been tuplified and the port to PPL passes the graphite testsuite. For building the graphite branch right now, here are the steps you'll have to go through:
You have to get a copy of the release 0.9 of PPL from: http://www.cs.unipr.it/ppl/Download/
cd ppl ./configure --prefix=/somewhere make make install
Then you can get a copy of the port of Cloog to PPL as follows:
cd cloog git-init git-pull http://repo.or.cz/w/cloog-ppl.git aclocal autoconf ./configure --with-ppl=/somewhere --prefix=/somewhere make make install
Then grab a version of graphite branch and configure like this:
cd gcc/build ../configure --with-cloog=/somewhere --with-ppl=/somewhere make
For the moment I think that building the cloog and ppl libs in the gcc directory is broken. I have not been able to configure ppl within the build of gcc because ieeefp.h has not been found on my ubuntu system. I will try to see how that can be fixed, or better, not provide this functionality and expect all the time the cloog and ppl libs to be installed on the system.
Note that ppl and polylib are two backends of cloog, and one has the choice of the polyhedral library to be used. For the moment the code generated by the ppl backend contains much more conditions that are redundant with respect to the enclosing loops because of the cloog_domain_simplify operation that is still very inefficient in the ppl backend. This should be improved either in newer versions of PPL.
Sebastian Pop -- AMD - GNU Tools
Hi,
Just a follow-up to this message that I sent to the GCC mailing list. This was more an executive level summary of the changes, so I'm going to give you some more details on the low level changes and the missing parts from PPL that I had to adapt for replacing PolyLib. Hopefully this code can be included in the PPL, or you already have support for it that I missed when I coded. The plan is to clean up CLooG's PPL back-end, by pushing as much of the missing functionality in PPL.
The main missing part in PPL is the union of convex polyhedra and the operations on them. For example, have a look at the first polyhedral operation that I ported, cloog_domain_intersection in this commit: http://repo.or.cz/w/cloog-ppl.git?a=commitdiff;h=d78c8bb5f121aaaa78f69b643c2... at the end of this commit, there is code that implements around the ppl_Polyhedron_intersection_assign the missing parts to work on unions of convex polyhedra.
There were also some missing functions like the comparison function between two polyhedra, and then a topological sort based on it: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=b2a471f465823452c2c6750c21dc628... more specifically in domain.c:cloog_domain_polyhedron_compare and cloog_domain_sort. IMHO these are good candidates to extend the available functionality of PPL.
The last missing part is the simplification of domains in this commit: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=da969835f0d86b4b1d2dff3b5bca479... and you can see that in the commit changelog there are some directions on how to fix domain.c:cloog_domain_simplify.
"For matching the PolyLib implementation the code to detect redundant constraints should be more accurate. One solution could be to use the GLPK solver that can be bound in with PPL to minimize the constraint systems."
Let me explain a little bit more what I was meaning by:
For the moment the code generated by the ppl backend contains much more conditions that are redundant with respect to the enclosing loops because of the cloog_domain_simplify operation that is still very inefficient in the ppl backend.
Here is what cloog_domain_simplify is doing:
/* Simplifies DOM1 in the context of DOM2. For example, DOM1 can contain the following conditions: i >= 0, i <= 5, and DOM2 is a loop around, i.e. the context of DOM1, that also contains the conditions i >= 0, i <= 5. So instead of generating a loop like:
| for (i = 0; i < 6; i++) | { | if (i >= 0 && i <= 5) | S; | }
this function allows to detect that in the context of DOM2, the constraints of DOM1 are redundant, and so the following code should be produced:
| for (i = 0; i < 6; i++) | S; */ CloogDomain * cloog_domain_simplify (CloogDomain * dom1, CloogDomain * dom2)
The current implementation of this function tries to exploit the fact that PPL can minimize constraint and generator systems, but this is not enough to detect some constraints that are subsumed by others. A huge amount of code in PolyLib deals with the simplification of redundant constraint that are then removed from the polyhedra. I was thinking that this could be done by formulating the problem as ILP and then solve it using a generic ILP solver like the GLPK, but I didn't thought long enough to see how this can be implemented. The quality of the code generated by cloog heavily depends on an efficient implementation of this function. For example, have a look at the changes in cloog's testsuite for the same commit: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=da969835f0d86b4b1d2dff3b5bca479...
Sebastian Pop -- AMD - GNU Tools
On Sun, Aug 3, 2008 at 12:48 PM, Sven Verdoolaege skimo@kotnet.org wrote:
Why *I*LP?!?? Surely that's way overkill.
I'm open to suggestions on LP as well ;-)
Thanks, Sebastian
Sebastian Pop wrote:
Just a follow-up to this message that I sent to the GCC mailing list.
Hi there,
I finally succeeded in building Cloog (the problem was due to a conflict between Libtool 2.2.4 ---which I use--- and the configuration scripts of cloog ---which assume older versions of the Autotools---).
The first thing I did was to compile Cloog against PPL 0.10: I had to rename a few symbols, but it was a 5-minutes affair... a patch for Cloog is attached.
I would also like to let you know that we, the PPL developers, have changed our priorities in order to release PPL 0.10 as soon as possible. All the best,
Roberto
Roberto Bagnara wrote:
The first thing I did was to compile Cloog against PPL 0.10: I had to rename a few symbols, but it was a 5-minutes affair... a patch for Cloog is attached.
Here is the patch. By the way, please accept my apologies if I am mailing someone unnecessarily or if I missed someone else. Is there a mailing list for this project? For PPL-related messages it is very easy: mail ppl-devel@cs.unipr.it (only). Cheers,
Roberto
On Fri, Aug 15, 2008 at 04:10:53PM +0200, Roberto Bagnara wrote:
Is there a mailing list for this project?
Not that I'm aware of. Note that we haven't decided yet if we are going to take the ppl port patches. They have to be cleaned up first anyway. If this happens, then I assume Sebastian will include your patch(es) in his repo before asking me or Cedric to merge it.
skimo
Sven Verdoolaege wrote:
On Fri, Aug 15, 2008 at 04:10:53PM +0200, Roberto Bagnara wrote:
Is there a mailing list for this project?
Not that I'm aware of.
OK: just let me know if you want me to mail more or less people.
Note that we haven't decided yet if we are going to take the ppl port patches. They have to be cleaned up first anyway.
OK: the PPL development team is willing to help to the extent of its possibilities. Cheers,
Roberto
On Fri, Aug 15, 2008 at 9:10 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
Roberto Bagnara wrote:
The first thing I did was to compile Cloog against PPL 0.10: I had to rename a few symbols, but it was a 5-minutes affair... a patch for Cloog is attached.
Here is the patch. By the way, please accept my apologies if I am mailing someone unnecessarily or if I missed someone else. Is there a mailing list for this project? For PPL-related messages it is very easy: mail ppl-devel@cs.unipr.it (only). Cheers,
Thanks for the patch, I committed it to the public git, except a small part in configure.in:
-AC_PROG_LIBTOOL +LT_INIT([dlopen,win32-dll])
If I remove AC_PROG_LIBTOOL, I get this error:
Remember to add `AC_PROG_LIBTOOL' to `configure.in'. You should update your `aclocal.m4' by running aclocal. Putting files in AC_CONFIG_AUX_DIR, `autoconf'. Makefile.am:44: Libtool library used but `LIBTOOL' is undefined Makefile.am:44: The usual way to define `LIBTOOL' is to add `AC_PROG_LIBTOOL' Makefile.am:44: to `configure.in' and run `aclocal' and `autoconf' again. Makefile.am:44: If `AC_PROG_LIBTOOL' is in `configure.in', make sure Makefile.am:44: its definition is in aclocal's search path.
Now, if I include back AC_PROG_LIBTOOL and do a make, it fails with the following error:
./configure: line 19943: syntax error near unexpected token `dlopen,win32-dll' ./configure: line 19943: `LT_INIT(dlopen,win32-dll)' make: *** [config.status] Error 2
Any hint of why I get these errors if I include your change? It seems like an autoconf problem. I'm using autoconf (GNU Autoconf) 2.61.
Sebastian Pop -- AMD - GNU Tools
Hi,
CLooG and Graphite are now expecting PPL 0.10 to be installed. You will have to git-pull again the code for CLooG and install a new PPL version. Without that, the current head of the graphite branch won't compile anymore. Instructions on how to build the branch are on http://gcc.gnu.org/wiki/Graphite
I recommend that you use the latest snapshots of PPL, right now ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre22.tar.bz2 as I will clean up the code of the CLooG-PPL backend and it will rely on new functionality that is present only on beta22.
Attached is the patch that checks for the version 0.10 of PPL. Paolo, does this patch look good to you?
Thanks, Sebastian Pop -- AMD - GNU Tools
Sebastian Pop wrote:
Hi,
CLooG and Graphite are now expecting PPL 0.10 to be installed. You will have to git-pull again the code for CLooG and install a new PPL version. Without that, the current head of the graphite branch won't compile anymore. Instructions on how to build the branch are on http://gcc.gnu.org/wiki/Graphite
I recommend that you use the latest snapshots of PPL, right now ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre22.tar.bz2 as I will clean up the code of the CLooG-PPL backend and it will rely on new functionality that is present only on beta22.
Attached is the patch that checks for the version 0.10 of PPL. Paolo, does this patch look good to you?
Yes, thanks.
Paolo
Sebastian, Do you have a patch for allowing graphite to build against polylib as well as ppl yet? The current graphite branch patches and ppl 1.0pre22 still appears unable to do any actual loop optimizations so I would like to be able to go back to using polylib for some polyhedron 2005 benchmarks of the new loop optimizations. Thanks in advance. Jack
On Thu, Aug 21, 2008 at 03:20:34PM +0200, Paolo Bonzini wrote:
Sebastian Pop wrote:
Hi,
CLooG and Graphite are now expecting PPL 0.10 to be installed. You will have to git-pull again the code for CLooG and install a new PPL version. Without that, the current head of the graphite branch won't compile anymore. Instructions on how to build the branch are on http://gcc.gnu.org/wiki/Graphite
I recommend that you use the latest snapshots of PPL, right now ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre22.tar.bz2 as I will clean up the code of the CLooG-PPL backend and it will rely on new functionality that is present only on beta22.
Attached is the patch that checks for the version 0.10 of PPL. Paolo, does this patch look good to you?
Yes, thanks.
Paolo
Jack Howarth wrote:
The current graphite branch patches and ppl 1.0pre22 still appears unable to do any actual loop optimizations [...]
Hi there,
I don't know if the reason of this was the lack of a simplification operation in the PPL. This has now be implemented and is available in the snapshot
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre23.tar.bz2
All the best,
Roberto
On Thu, Aug 21, 2008 at 12:09 PM, Roberto Bagnara bagnara@cs.unipr.it wrote:
I don't know if the reason of this was the lack of a simplification operation in the PPL. This has now be implemented and is available in the snapshot
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre23.tar.bz2
Excellent! Many thanks Roberto for this quick fix ;-) I'm going to modify CLooG to call this function and see what happens to CLooG's testsuite.
Sebastian
On Thu, Aug 21, 2008 at 12:40:08PM -0500, Sebastian Pop wrote:
On Thu, Aug 21, 2008 at 12:09 PM, Roberto Bagnara bagnara@cs.unipr.it wrote:
I don't know if the reason of this was the lack of a simplification operation in the PPL. This has now be implemented and is available in the snapshot
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre23.tar.bz2
Excellent! Many thanks Roberto for this quick fix ;-) I'm going to modify CLooG to call this function and see what happens to CLooG's testsuite.
Sebastian
Sebastian, Are there options in graphite to dump the loop optimization details for each loop detected; similar to how vectorization will report...
a.f90:8: note: not vectorized: data ref analysis failed D.1462_61 = (*aa_60(D))[D.1461_59]
for code like...
subroutine sub(aa,bb,n,m) implicit none integer, intent(in) :: n,m real, intent(inout) :: aa(n,m) real, intent(in) :: bb(n,m) integer :: i,j do i = 1,m do j= 2,n aa(i,j)= aa(i,j-1)+bb(i,j-1) enddo enddo do j= 2,n do i = 1,m aa(i,j)= aa(i,j-1)+bb(i,j-1) enddo enddo end subroutine
that can't currently be vectorized. Jack
On Thu, Aug 21, 2008 at 2:29 PM, Jack Howarth howarth@bromo.msbb.uc.edu wrote:
Are there options in graphite to dump the loop optimization details for each loop detected; similar to how vectorization will report...
You can try -fdump-tree-graphite-all Though, the messages are probably not yet as precise as for the vectorizer.
Sebastian
Robert, Is the external ABI of ppl the same between 1.0pre22 and 1.0pre23? I am wondering if I should just be able to install the new 1.0pre23 or if I need to rebuild both cloog-ppl git and gcc against it as well. Jack
On Thu, Aug 21, 2008 at 07:09:40PM +0200, Roberto Bagnara wrote:
Jack Howarth wrote:
The current graphite branch patches and ppl 1.0pre22 still appears unable to do any actual loop optimizations [...]
Hi there,
I don't know if the reason of this was the lack of a simplification operation in the PPL. This has now be implemented and is available in the snapshot
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre23.tar.bz2All 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
On Thu, Aug 21, 2008 at 2:18 PM, Jack Howarth howarth@bromo.msbb.uc.edu wrote:
Is the external ABI of ppl the same between 1.0pre22 and 1.0pre23? I am wondering if I should just be able to install the new 1.0pre23 or if I need to rebuild both cloog-ppl git and gcc against it as well.
pre23 contains more functions for domain_simplify, but these are not yet used in cloog.git. I will send a note when CLooG is using these and when you'll have to update cloog and ppl. For the moment either pre22 or pre23 should just work.
Sebastian
Jack Howarth wrote:
Is the external ABI of ppl the same between 1.0pre22 and 1.0pre23?
Hi Jack,
the answer is negative.
I am wondering if I should just be able to install the new 1.0pre23 or if I need to rebuild both cloog-ppl git and gcc against it as well.
In general, until we make an officiao release, we do not worry about the ABI. So recompilation is almost always necessary. Cheers,
Roberto
Hi there,
a new snapshot release of PPL 0.10 has been uploaded:
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre24.tar.bz2
This contains the latest fixes and improvements to the "simplify using context" operation. Please let us know if, whith this one, the graphite branch performs the expected loop optimizations. Let us also know if you want us to add other functionalities to PPL 0.10. All the best,
Roberto
On Fri, Aug 22, 2008 at 11:19 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
a new snapshot release of PPL 0.10 has been uploaded:
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre24.tar.bz2
As well, you should git-pull again the Cloog changes.
Sebastian
On Fri, Aug 22, 2008 at 11:55:05AM -0500, Sebastian Pop wrote:
On Fri, Aug 22, 2008 at 11:19 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
a new snapshot release of PPL 0.10 has been uploaded:
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre24.tar.bz2
As well, you should git-pull again the Cloog changes.
Sebastian
Sebastian, So cloog-ppl git is now modified to use the new simplification routines and graphite will now actually perform optimizations on the generated code? Jack
On Fri, Aug 22, 2008 at 1:09 PM, Jack Howarth howarth@bromo.msbb.uc.edu wrote:
So cloog-ppl git is now modified to use the new simplification routines and graphite will now actually perform optimizations on the generated code?
Wait till end of today to try graphite branch, otherwise you'll get all the errors we saw. We're fixing these right now.
Thanks, Sebastian
On Fri, Aug 22, 2008 at 01:47:20PM -0500, Sebastian Pop wrote:
On Fri, Aug 22, 2008 at 1:09 PM, Jack Howarth howarth@bromo.msbb.uc.edu wrote:
So cloog-ppl git is now modified to use the new simplification routines and graphite will now actually perform optimizations on the generated code?
Wait till end of today to try graphite branch, otherwise you'll get all the errors we saw. We're fixing these right now.
Thanks, Sebastian
Sebastian, With tonight's graphite branch changes added to the rest on top of gcc trunk and using current clogg-ppl git with ppl-1.0rc24, I see two gcc.dg/graphite/graphite.exp testsuite failures on i686-apple-darwin9...
FAIL: gcc.dg/graphite/block-1.c (internal compiler error) FAIL: gcc.dg/graphite/block-1.c (test for excess errors) FAIL: gcc.dg/graphite/block-1.c scan-tree-dump-times graphite "Loop blocked" 3 FAIL: gcc.dg/graphite/scop-16.c (internal compiler error) FAIL: gcc.dg/graphite/scop-16.c (test for excess errors)
which are...
Executing on host: /sw/src/fink.build/gcc44-4.3.999-20080822/darwin_objdir/gcc/xgcc -B/sw/src/fink.build/gcc44-4.3.999-20080822/darwin_objdir/gc c/ /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/block-1.c -O2 -floop-block -fdump-tree-graphite-al l -S -o block-1.s (timeout = 300) /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/block-1.c: In function 'main': /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/block-1.c:6: error: found a real definition for a non-r egister /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/block-1.c:6: error: in statement D.1950_13 = A_68 + graphiteIV.24_4; /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/block-1.c:6: internal compiler error: verify_ssa failed Please submit a full bug report, with preprocessed source if appropriate. See http://gcc.gnu.org/bugs.html for instructions.
xecuting on host: /sw/src/fink.build/gcc44-4.3.999-20080822/darwin_objdir/gcc/xgcc -B/sw/src/fink.build/gcc44-4.3.999-20080822/darwin_objdir/gc c/ /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/scop-16.c -O2 -floop-block -fdump-tree-graphite-al l -S -o scop-16.s (timeout = 300) /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/scop-16.c: In function 'test': /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/scop-16.c:5: error: found a real definition for a non-r egister /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/scop-16.c:5: error: in statement # VUSE <a_83> { a } D.1955_21 = a[graphiteIV.37_78][a_83]; /sw/src/fink.build/gcc44-4.3.999-20080822/gcc-4.4-20080822/gcc/testsuite/gcc.dg/graphite/scop-16.c:5: internal compiler error: verify_ssa failed Please submit a full bug report, with preprocessed source if appropriate. See http://gcc.gnu.org/bugs.html for instructions.
I assume these are the remaining errors unfixed from...
http://gcc.gnu.org/ml/gcc-patches/2008-08/msg01715.html
Is that correct? Thanks for any clarifications. Jack
Sebastian, Which version of cloog should one use with polylib and graphite? I assume the cloog-ppl git should still build fine against polylib for use with graphite, correct? Are there non-ppl related fixes for graphite in the cloog-ppl git which would be applicable to polylib as well? Jack
Sebastian Pop wrote:
On Fri, Aug 15, 2008 at 9:10 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
Roberto Bagnara wrote:
The first thing I did was to compile Cloog against PPL 0.10: I had to rename a few symbols, but it was a 5-minutes affair... a patch for Cloog is attached.
Here is the patch. By the way, please accept my apologies if I am mailing someone unnecessarily or if I missed someone else. Is there a mailing list for this project? For PPL-related messages it is very easy: mail ppl-devel@cs.unipr.it (only). Cheers,
Thanks for the patch, I committed it to the public git, except a small part in configure.in:
-AC_PROG_LIBTOOL +LT_INIT([dlopen,win32-dll])
If I remove AC_PROG_LIBTOOL, I get this error:
Remember to add `AC_PROG_LIBTOOL' to `configure.in'. You should update your `aclocal.m4' by running aclocal. Putting files in AC_CONFIG_AUX_DIR, `autoconf'. Makefile.am:44: Libtool library used but `LIBTOOL' is undefined Makefile.am:44: The usual way to define `LIBTOOL' is to add `AC_PROG_LIBTOOL' Makefile.am:44: to `configure.in' and run `aclocal' and `autoconf' again. Makefile.am:44: If `AC_PROG_LIBTOOL' is in `configure.in', make sure Makefile.am:44: its definition is in aclocal's search path.
Now, if I include back AC_PROG_LIBTOOL and do a make, it fails with the following error:
./configure: line 19943: syntax error near unexpected token `dlopen,win32-dll' ./configure: line 19943: `LT_INIT(dlopen,win32-dll)' make: *** [config.status] Error 2
Any hint of why I get these errors if I include your change? It seems like an autoconf problem. I'm using autoconf (GNU Autoconf) 2.61.
You are probably using an old version of Libtool: AC_PROG_LIBTOOL is a deprecated name for LT_INIT (see http://www.gnu.org/software/libtool/manual/libtool.html#LT_005fINIT). Cheers,
Roberto
On Wed, Aug 20, 2008 at 09:34:22PM +0200, Roberto Bagnara wrote:
Sebastian Pop wrote:
On Fri, Aug 15, 2008 at 9:10 AM, Roberto Bagnara bagnara@cs.unipr.it
-AC_PROG_LIBTOOL +LT_INIT([dlopen,win32-dll])
You are probably using an old version of Libtool: AC_PROG_LIBTOOL is a deprecated name for LT_INIT (see http://www.gnu.org/software/libtool/manual/libtool.html#LT_005fINIT).
That doesn't explain why you specified the dlopen and win32-dll options.
skimo
Sven Verdoolaege wrote:
On Wed, Aug 20, 2008 at 09:34:22PM +0200, Roberto Bagnara wrote:
Sebastian Pop wrote:
On Fri, Aug 15, 2008 at 9:10 AM, Roberto Bagnara bagnara@cs.unipr.it
-AC_PROG_LIBTOOL +LT_INIT([dlopen,win32-dll])
You are probably using an old version of Libtool: AC_PROG_LIBTOOL is a deprecated name for LT_INIT (see http://www.gnu.org/software/libtool/manual/libtool.html#LT_005fINIT).
That doesn't explain why you specified the dlopen and win32-dll options.
It was not meant to explain that. Let us separate the issues:
- dlopen: it is there because we use the -dlopen libtool flag in some of the foreign interfaces; - win32-dll: I am indeed surprised by the documentation of that option in Libtool 2.2.4. I wonder if the option used to have a different semantics... because now it would seem completely useless. Do you agree?
Thanks,
Roberto
On Wed, Aug 20, 2008 at 11:18:36PM +0200, Roberto Bagnara wrote:
- dlopen: it is there because we use the -dlopen libtool flag in some of the foreign interfaces;
This would need to be mentioned in the commit message of any commit that ends up in my tree.
- win32-dll: I am indeed surprised by the documentation of that option in Libtool 2.2.4. I wonder if the option used to have a different semantics... because now it would seem completely useless. Do you agree?
I have no idea what the option used to mean. Also, I'm pleased to say I'm not very familiar with win32.
skimo
Sven Verdoolaege wrote:
On Wed, Aug 20, 2008 at 11:18:36PM +0200, Roberto Bagnara wrote:
- dlopen: it is there because we use the -dlopen libtool flag in some of the foreign interfaces;
This would need to be mentioned in the commit message of any commit that ends up in my tree.
Sorry: only now I see what you meant. You were talking about the use of LT_INIT in CLooG, I was talking about the use of LT_INIT in the PPL (I simply copy-and-pasted the line from PPL's configure.ac). It is likely in CLooG you should use LT_INIT without any option. Cheers,
Roberto
Sebastian Pop wrote:
The main missing part in PPL is the union of convex polyhedra and the operations on them. For example, have a look at the first polyhedral operation that I ported, cloog_domain_intersection in this commit: http://repo.or.cz/w/cloog-ppl.git?a=commitdiff;h=d78c8bb5f121aaaa78f69b643c2... at the end of this commit, there is code that implements around the ppl_Polyhedron_intersection_assign the missing parts to work on unions of convex polyhedra.
Hi Sebastian,
I am not sure I understand. PPL 0.10 has makes available the Pointset_Powerset abstract domain from within all the foreign interfaces (including of course the C one). This domain used not to be in the list of instantiations provided by default; the user has to request it at configure-time by using the --enable-instantiations option. To simplify things for you, I have just added the domains
Pointset_Powerset<C_Polyhedron>
and
Pointset_Powerset<NNC_Polyhedron>
to the set of instantiations that are generated by default. I am uploading the 0.10pre22 snapshots, which contain this change, to
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/
Cheers,
Roberto
Sebastian Pop wrote:
There were also some missing functions like the comparison function between two polyhedra, and then a topological sort based on it: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=b2a471f465823452c2c6750c21dc628... more specifically in domain.c:cloog_domain_polyhedron_compare and cloog_domain_sort. IMHO these are good candidates to extend the available functionality of PPL.
Hi again,
we have checked this code and found that it has several memory leaks you may want to fix. We also agree that the compare function would be nice to have in the PPL. However, can you please specify exactly the functionality you would like to have? The comment says:
/* Compares P1 to P2: returns 0 when the polyhedra don't overlap, returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">" relation is the "contains" relation. */
What should be returned if P1 and P2 do overlap and neither is contained into the other?
Concerning the sort function, we are not sure which place it could have in the PPL. The Pointset_Powerset domain is a set, so the ordering is an implementation detail that should not concern the client application. Moreover, a reduced Pointset_Powerset never contains two polyhedra one of which is contained into the other. Cheers,
Roberto
Sebastian Pop wrote:
The last missing part is the simplification of domains in this commit: [...]
The current implementation of this function tries to exploit the fact that PPL can minimize constraint and generator systems, but this is not enough to detect some constraints that are subsumed by others. A huge amount of code in PolyLib deals with the simplification of redundant constraint that are then removed from the polyhedra.
Hi again.
Sorry, but I am not following. When you obtain a minimized constraint or generator system for a polyhedron from the PPL, you don't get any redundancy. In particular, you do not get constraints that are subsumed by others. Can you specify precisely the operation that you would like the PPL to provide? Cheers,
Roberto
Hi Roberto,
Sorry, but I am not following. When you obtain a minimized constraint or generator system for a polyhedron from the PPL, you don't get any redundancy. In particular, you do not get constraints that are subsumed by others. Can you specify precisely the operation that you would like the PPL to provide? Cheers,
The concept is called "gist" in Omega, and simplification under a context in PolyLib. You'd like to run the simplification with the assumption that some constraints are already enforced, and only retain the additional constraints (minimized) to define a given sub-polyhedron.
Albert
Albert Cohen wrote:
Sorry, but I am not following. When you obtain a minimized constraint or generator system for a polyhedron from the PPL, you don't get any redundancy. In particular, you do not get constraints that are subsumed by others. Can you specify precisely the operation that you would like the PPL to provide? Cheers,
The concept is called "gist" in Omega, and simplification under a context in PolyLib. You'd like to run the simplification with the assumption that some constraints are already enforced, and only retain the additional constraints (minimized) to define a given sub-polyhedron.
Hi Albert,
we need to have a more precise specification of the required operation. In particular, for the simplification of { A <= 0 } under the context { A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
Thanks,
Roberto
On Mon, Aug 18, 2008 at 05:17:01PM +0200, Roberto Bagnara wrote:
Albert Cohen wrote:
The concept is called "gist" in Omega, and simplification under a context in PolyLib. You'd like to run the simplification with the assumption that some constraints are already enforced, and only retain the additional constraints (minimized) to define a given sub-polyhedron.
Hi Albert,
we need to have a more precise specification of the required operation. In particular, for the simplification of { A <= 0 } under the context
I assume you mean { A = 0 } here (as { A <= 0 } is not a subset of {A >= 0}).
{ A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
I asked the same question on the polylib mailing list many years ago but got no answer.
skimo
Sven Verdoolaege wrote:
On Mon, Aug 18, 2008 at 05:17:01PM +0200, Roberto Bagnara wrote:
Albert Cohen wrote:
The concept is called "gist" in Omega, and simplification under a context in PolyLib. You'd like to run the simplification with the assumption that some constraints are already enforced, and only retain the additional constraints (minimized) to define a given sub-polyhedron.
Hi Albert,
we need to have a more precise specification of the required operation. In particular, for the simplification of { A <= 0 } under the context
I assume you mean { A = 0 } here (as { A <= 0 } is not a subset of {A >= 0}).
I don't follow: why should the first polyhedron (the one to simplify) be a subset of the second polyhedron (the context)?
{ A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
I asked the same question on the polylib mailing list many years ago but got no answer.
I see. However, I am interested in understanding the real needs of Cloog independently from what PolyLib does. Cheers,
Roberto
On Mon, Aug 18, 2008 at 08:21:55PM +0200, Roberto Bagnara wrote:
we need to have a more precise specification of the required operation. In particular, for the simplification of { A <= 0 } under the context
I assume you mean { A = 0 } here (as { A <= 0 } is not a subset of {A >= 0}).
I don't follow: why should the first polyhedron (the one to simplify) be a subset of the second polyhedron (the context)?
A generic "gist" should not restrict in any way the polyhedron to be simplified w.r.t. the context polyhedron (both could be unions, in fact). So your example makes perfect sense, but maybe Skimo had stg else in mind?
{ A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
I asked the same question on the polylib mailing list many years ago but got no answer.
Strange.
I did not check what the PolyLib or Omega do, but {A=0} whould make more sense although it may cost more to achieve. We do not need to work on integer points only for this simplification, though, and I don't think the PolyLib implements more than a bunch of special cases here (but I'm not at all familiar with that code).
I see. However, I am interested in understanding the real needs of Cloog independently from what PolyLib does.
It's hard to define formally, but generally speaking, I would say the shortest the constraint list the better, and the simplest the expressions the better (involving less variables). There is probably not a unique optimal solution, but the intuition is that code has to be generated from these contraints (loop bounds or conditionals), and more constraints or more terms means more costly control flow and boolean expressions.
Albert
On Mon, Aug 18, 2008 at 10:25:09PM +0200, Albert Cohen wrote:
A generic "gist" should not restrict in any way the polyhedron to be simplified w.r.t. the context polyhedron (both could be unions, in fact). So your example makes perfect sense, but maybe Skimo had stg else in mind?
I thought that's how you described the problem, and that's IIRC how it is used in CLooG, but sure, you can do it more generally.
{ A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
I asked the same question on the polylib mailing list many years ago but got no answer.
Strange.
I did not check what the PolyLib or Omega do, but {A=0} whould make more sense although it may cost more to achieve. We do not need to work on integer points only for this simplification, though, and I
Why are you talking about integer points?
don't think the PolyLib implements more than a bunch of special cases here (but I'm not at all familiar with that code).
There's no special cases in the PolyLib implementation that I'm aware of.
I see. However, I am interested in understanding the real needs of Cloog independently from what PolyLib does.
It's hard to define formally,
It's defined in section 4.8 of PI-785 as the largest set C such that C \cap B = A \cap B (where A is the original set and B is the context). So, if you use this definition, it should return { A <= 0 }. However, if you give it { A = 0 } as the original set, PolyLib will or at least used to return { A = 0 }. I don't think I've ever fixed this, given that there was effectively zero interest.
As to CLooG, IMHO, it doesn't really matter which of the two you give, although to a human reader, { A = 0 } may be more intuitive.
skimo
I did not check what the PolyLib or Omega do, but {A=0} whould make more sense although it may cost more to achieve. We do not need to work on integer points only for this simplification, though, and I
Why are you talking about integer points?
The simplification could take into account the integer hull of the context to further reduce the system, but this would be combinatorially expensive.
don't think the PolyLib implements more than a bunch of special cases here (but I'm not at all familiar with that code).
There's no special cases in the PolyLib implementation that I'm aware of.
OK. I probably misunderstood the discussion on the big bunch of PolyLib code dedicated to this simplification in a context. We need to understand why it is so big, as Sebastian said :-).
I see. However, I am interested in understanding the real needs of Cloog independently from what PolyLib does.
It's hard to define formally,
It's defined in section 4.8 of PI-785 as the largest set C such that C \cap B = A \cap B (where A is the original set and B is the context). So, if you use this definition, it should return { A <= 0 }.
This is right, and is the most canonical definition I can see. However it is not necessarily CLooG-optimal, e.g., when the largest set is described by a union where it could be reduced into single half-space intersection.
However, if you give it { A = 0 } as the original set, PolyLib will or at least used to return { A = 0 }. I don't think I've ever fixed this, given that there was effectively zero interest.
As to CLooG, IMHO, it doesn't really matter which of the two you give, although to a human reader, { A = 0 } may be more intuitive.
Right, but I would recommend the PPL to follow the canonical definition above, as it has always been considered sufficient so far.
Albert
Sven Verdoolaege wrote:
On Mon, Aug 18, 2008 at 05:17:01PM +0200, Roberto Bagnara wrote:
Albert Cohen wrote:
The concept is called "gist" in Omega, and simplification under a context in PolyLib. You'd like to run the simplification with the assumption that some constraints are already enforced, and only retain the additional constraints (minimized) to define a given sub-polyhedron.
Hi Albert,
we need to have a more precise specification of the required operation. In particular, for the simplification of { A <= 0 } under the context
I assume you mean { A = 0 } here (as { A <= 0 } is not a subset of {A >= 0}).
{ A >= 0 }, what do you consider simpler?
Possibility 1: { A <= 0 } Possibility 2: { A = 0 }.
I asked the same question on the polylib mailing list many years ago but got no answer.
Dear Sven,
if you run the attached input through PolyLib's polytestgmp, you will obtain:
$ ./polytestgmp </tmp/simplify_bug.in 1 3 1 0 1
This would seem to indicate that the simplification of the domain { {A>=0} } (i.e., the singleton set of polyhedra containing only the polyhedron defined by the single equality A >= 0) in the context { {A<=0} } gives the universe as the result. Can you confirm that this is a bug in PolyLib? Cheers,
Roberto
On Wed, Aug 20, 2008 at 09:46:07PM +0200, Roberto Bagnara wrote:
if you run the attached input through PolyLib's polytestgmp, you will obtain:
$ ./polytestgmp </tmp/simplify_bug.in 1 3 1 0 1
I don't think so:
bash-3.00$ ~/obj/barvinok/polylib/polytestgmp < simplify_bug.in 2 3 1 1 0 1 0 1
What version of PolyLib are you using?
skimo
Sven Verdoolaege wrote:
On Wed, Aug 20, 2008 at 09:46:07PM +0200, Roberto Bagnara wrote:
if you run the attached input through PolyLib's polytestgmp, you will obtain:
$ ./polytestgmp </tmp/simplify_bug.in 1 3 1 0 1
I don't think so:
bash-3.00$ ~/obj/barvinok/polylib/polytestgmp < simplify_bug.in 2 3 1 1 0 1 0 1
What version of PolyLib are you using?
The latest one: 5.22.3. And you?
On Wed, Aug 20, 2008 at 11:11:30PM +0200, Roberto Bagnara wrote:
The latest one: 5.22.3. And you?
The lastest one: polylib-5.22.3-43-g1968911
Well what do you know, it appears someone fixed that http://repo.or.cz/w/polylib.git?a=commitdiff;h=5b7afefb3078f5c75e0beb80ccc97... I had forgotton all about that.
Vincent, maybe we should cut a new release in the not too distant future.
skimo
Sebastian Pop wrote:
The last missing part is the simplification of domains in this commit: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=da969835f0d86b4b1d2dff3b5bca479... and you can see that in the commit changelog there are some directions on how to fix domain.c:cloog_domain_simplify.
Hi Sebastian,
the PPL 0.10 snapshot at
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre23.tar.bz2
has the new functionality required. From the C interface, this is available as
int ppl_Polyhedron_simplify_using_context_assign(ppl_Polyhedron_t x, ppl_const_Polyhedron_t y);
where `x' is the polyhedron to be simplified, `y' is the context, and the return value is
= 0, if `x' intersected with `y' is empty; < 0, if an error occurred (as usual); > 0, otherwise.
Of course, this has received very little testing: please let us know how it goes. Cheers,
Roberto
Sebastian,
did you receive this message I sent you one week ago? It really seems in CLooG you are duplicating much of the functionalities of our Pointset_Powerset construction. Cheers,
Roberto
Sebastian Pop wrote:
The main missing part in PPL is the union of convex polyhedra and the operations on them. For example, have a look at the first polyhedral operation that I ported, cloog_domain_intersection in this commit: http://repo.or.cz/w/cloog-ppl.git?a=commitdiff;h=d78c8bb5f121aaaa78f69b643c2... at the end of this commit, there is code that implements around the ppl_Polyhedron_intersection_assign the missing parts to work on unions of convex polyhedra.
Hi Sebastian,
I am not sure I understand. PPL 0.10 has makes available the Pointset_Powerset abstract domain from within all the foreign interfaces (including of course the C one). This domain used not to be in the list of instantiations provided by default; the user has to request it at configure-time by using the --enable-instantiations option. To simplify things for you, I have just added the domains
Pointset_Powerset<C_Polyhedron>
and
Pointset_Powerset<NNC_Polyhedron>
to the set of instantiations that are generated by default. I am uploading the 0.10pre22 snapshots, which contain this change, to
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/
Cheers,
Roberto
On Fri, Aug 22, 2008 at 11:21 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
did you receive this message I sent you one week ago?
Yes.
It really seems in CLooG you are duplicating much of the functionalities of our Pointset_Powerset construction.
This cleanup was the next thing on my todo list.
Sebastian
Sebastian Pop wrote:
It really seems in CLooG you are duplicating much of the functionalities of our Pointset_Powerset construction.
This cleanup was the next thing on my todo list.
Another issue is: do you really need NNC polyhedra? I am asking because I guess you only work with integer variables: in this case, C polyhedra should suffice. Moreover, there is a performance penalty to be paid for NNC polyhedra (think about a factor 2, both in space and time, for typical computations). Cheers,
Roberto
On Sun, Aug 24, 2008 at 11:32 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
Another issue is: do you really need NNC polyhedra?
I used NNC because I have not looked carefully at the definitions.
I am asking because I guess you only work with integer variables: in this case, C polyhedra should suffice. Moreover, there is a performance penalty to be paid for NNC polyhedra (think about a factor 2, both in space and time, for typical computations).
Thanks for spotting this inefficiency. I used the attached patch and the testsuite of CLooG passed.
Sebastian
This also remained unanswered (I guess that, on the way back from holidays, you found zillions of messages pending... I know it is not an easy situation). If you can clarify the semantics of the comparison operation you need, we will add it to the library. Cheers,
Roberto
Sebastian Pop wrote:
There were also some missing functions like the comparison function between two polyhedra, and then a topological sort based on it: http://repo.or.cz/w/cloog-ppl.git?a=commit;h=b2a471f465823452c2c6750c21dc628... more specifically in domain.c:cloog_domain_polyhedron_compare and cloog_domain_sort. IMHO these are good candidates to extend the available functionality of PPL.
Hi again,
we have checked this code and found that it has several memory leaks you may want to fix. We also agree that the compare function would be nice to have in the PPL. However, can you please specify exactly the functionality you would like to have? The comment says:
/* Compares P1 to P2: returns 0 when the polyhedra don't overlap, returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">" relation is the "contains" relation. */
What should be returned if P1 and P2 do overlap and neither is contained into the other?
Concerning the sort function, we are not sure which place it could have in the PPL. The Pointset_Powerset domain is a set, so the ordering is an implementation detail that should not concern the client application. Moreover, a reduced Pointset_Powerset never contains two polyhedra one of which is contained into the other. Cheers,
Roberto
On Fri, Aug 22, 2008 at 11:23 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
This also remained unanswered (I guess that, on the way back from holidays, you found zillions of messages pending... I know it is not an easy situation). If you can clarify the semantics of the comparison operation you need, we will add it to the library.
Cool, thanks.
/* Compares P1 to P2: returns 0 when the polyhedra don't overlap, returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">" relation is the "contains" relation. */
What should be returned if P1 and P2 do overlap and neither is contained into the other?
In that case, if p1 has constraints that are larger than p2, then 1, else -1.
i.e.
if p1 \ (p1 inter p2) is bigger than p2, then 1, else -1.
Concerning the sort function, we are not sure which place it could have in the PPL. The Pointset_Powerset domain is a set, so the ordering is an implementation detail that should not concern the client application. Moreover, a reduced Pointset_Powerset never contains two polyhedra one of which is contained into the other.
Could you return a "ppl_Polyhedron_t *" vector that contains pointers to the polyhedra in the set in that "topological order"?
Thanks, Sebastian
Hi Sebastian.
I am afraid I am not following your answer here below.
Sebastian Pop wrote:
On Fri, Aug 22, 2008 at 11:23 AM, Roberto Bagnara bagnara@cs.unipr.it wrote:
This also remained unanswered (I guess that, on the way back from holidays, you found zillions of messages pending... I know it is not an easy situation). If you can clarify the semantics of the comparison operation you need, we will add it to the library.
Cool, thanks.
/* Compares P1 to P2: returns 0 when the polyhedra don't overlap, returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">" relation is the "contains" relation. */
What should be returned if P1 and P2 do overlap and neither is contained into the other?
In that case, if p1 has constraints that are larger than p2, then 1, else -1.
i.e.
if p1 \ (p1 inter p2) is bigger than p2, then 1, else -1.
In the current sources of cloog_ppl, we have the following:
static int cloog_domain_polyhedron_compare (CloogMatrix *m1, CloogMatrix *m2, int level, int nb_par, int dimension)
I can guess (please correct me if I am wrong) that:
a) `m1' and `m2' are the constraints describing polyhedra p1 and p2;
b) the two polyhedra have space dimension `dimension';
c) `nb_par' should be the number of parameters and it must satisfy the precondition 0 <= nb_par <= dimension;
d) `level' seems to identify a dimension of the polyhedron and, according to a comment to the corresponding code in polylib, it must satisfy the precondition 1 <= level <= dimension However, from the way it is used, it seems to me (but I am not sure about it) that it should also satisfy the stronger precondition 1 <= level <= dimension - nb_par (as a side note, this stronger property would imply dimension > 0).
Now, looking at the code for the cloog function above I see this formal parameter `level' playing a non-trivial role, so that it seems strange to me that it is not mentioned at all in the comment quoted by Roberto.
Can you please clarify its meaning?
Note that any strengthening of the preconditions above (e.g., replacing a non-strict inequality <= by a strict inequality <) will be really helpful.
Ciao, Enea.
On Sat, Aug 23, 2008 at 5:48 AM, Enea Zaffanella zaffanella@cs.unipr.it wrote:
In the current sources of cloog_ppl, we have the following:
static int cloog_domain_polyhedron_compare (CloogMatrix *m1, CloogMatrix *m2, int level, int nb_par, int dimension)
I can guess (please correct me if I am wrong) that:
a) `m1' and `m2' are the constraints describing polyhedra p1 and p2;
b) the two polyhedra have space dimension `dimension';
c) `nb_par' should be the number of parameters and it must satisfy the precondition 0 <= nb_par <= dimension;
d) `level' seems to identify a dimension of the polyhedron and, according to a comment to the corresponding code in polylib, it must satisfy the precondition 1 <= level <= dimension However, from the way it is used, it seems to me (but I am not sure about it) that it should also satisfy the stronger precondition 1 <= level <= dimension - nb_par (as a side note, this stronger property would imply dimension > 0).
Yes, all this is correct.
Now, looking at the code for the cloog function above I see this formal parameter `level' playing a non-trivial role, so that it seems strange to me that it is not mentioned at all in the comment quoted by Roberto.
Can you please clarify its meaning?
A little more detail of what nb_par and level are: nb_par represents the number of variables that are not known at compile time but that do not vary in the loop nest that is considered. For example, parameters can be loop bounds. The first dimensions in a polyhedron represent iteration domains: 1 <= level <= dimension - nb_par, and level is one of these loop iterators. Polyhedra are sorted following the value of their constraints in dimension "level".
Note that any strengthening of the preconditions above (e.g., replacing a non-strict inequality <= by a strict inequality <) will be really helpful.
Remember that in PolyLib format, the first column of a constraint matrix represents the {eq, ineq} boolean for the row. In PPL format: 0 <= level < dimension - nb_par dimension - nb_par <= parameter < dimension
Does this help?
Sebastian
Sebastian Pop wrote:
On Sat, Aug 23, 2008 at 5:48 AM, Enea Zaffanella zaffanella@cs.unipr.it wrote:
In the current sources of cloog_ppl, we have the following:
static int cloog_domain_polyhedron_compare (CloogMatrix *m1, CloogMatrix *m2, int level, int nb_par, int dimension)
I can guess (please correct me if I am wrong) that:
a) `m1' and `m2' are the constraints describing polyhedra p1 and p2;
b) the two polyhedra have space dimension `dimension';
c) `nb_par' should be the number of parameters and it must satisfy the precondition 0 <= nb_par <= dimension;
d) `level' seems to identify a dimension of the polyhedron and, according to a comment to the corresponding code in polylib, it must satisfy the precondition 1 <= level <= dimension However, from the way it is used, it seems to me (but I am not sure about it) that it should also satisfy the stronger precondition 1 <= level <= dimension - nb_par (as a side note, this stronger property would imply dimension > 0).
Yes, all this is correct.
Now, looking at the code for the cloog function above I see this formal parameter `level' playing a non-trivial role, so that it seems strange to me that it is not mentioned at all in the comment quoted by Roberto.
Can you please clarify its meaning?
A little more detail of what nb_par and level are: nb_par represents the number of variables that are not known at compile time but that do not vary in the loop nest that is considered. For example, parameters can be loop bounds. The first dimensions in a polyhedron represent iteration domains: 1 <= level <= dimension - nb_par, and level is one of these loop iterators. Polyhedra are sorted following the value of their constraints in dimension "level".
Note that any strengthening of the preconditions above (e.g., replacing a non-strict inequality <= by a strict inequality <) will be really helpful.
Remember that in PolyLib format, the first column of a constraint matrix represents the {eq, ineq} boolean for the row. In PPL format: 0 <= level < dimension - nb_par dimension - nb_par <= parameter < dimension
Does this help?
Sebastian
Yes, thanks, this was useful to help me understand the implementation.
This functionality is indeed ad-hoc for your purposes: it assumes some very specific meaning for the space dimensions, hence it is difficult to provide it with a *clean* specification.
I doubt its inclusion in the PPL would be a good thing.
On the other hand, having worked on it, I can fairly say that such an inclusion in the PPL would not buy much in terms of efficiency: all the potential efficiency improvements that I spot when looking at your code are indeed available through the current PPL public interface. See the attached file: it is C++ (due to my own taste), but it shouldn't be difficult to convert it so as to use the C interface of the library.
The main improvements wrt your version are the following:
(1) Before computing the intersection polyhedron q, you first throw away all constraints on the non-parameter variables having index >= level-1. This can be coded (in a simpler way) using C function
int ppl_Polyhedron_unconstrain_space_dimensions (ppl_Polyhedron_t ph, ppl_dimension_type ds[], size_t n);
where ds is the array of space dimension indices, of length n, encoding the set of vars to be unconstrained (this function is new to PPL 0.10).
(2) When the code tests for conditions for returning -1, you have two nested loops iterating on the constraints of q1 and q2 (named q_x and q_y in my C++ code). Here, we have two kinds of improvements:
(2a) use iterating functions on PPL constraint systems instead of converting back and forth between PPL and cloog matrix representations.
(2b) MORE IMPORTANTLY, the test for non-empty intersection in the inner loop can be coded more efficiently using the "relation_with" functionality of the PPL, i.e., the C function
int ppl_Polyhedron_relation_with_Constraint (ppl_const_Polyhedron_t ph, ppl_const_Constraint_t c);
and testing whether the result *entails* the value PPL_POLY_CON_RELATION_IS_DISJOINT (i.e., testing if this bit is set in the returned value). This should be a big win, as it avoids the creation/disposal of a quadratic number of polyhedra.
Hope the explanation above, together with the attached C++ code, is helpful enough. The easier way would be to write a C stub calling the attached C++ code ... provided you allow for compiling some C++ in cloog.
Ciao, Enea.
On Mon, Aug 25, 2008 at 3:01 AM, Enea Zaffanella zaffanella@cs.unipr.it wrote:
This functionality is indeed ad-hoc for your purposes: it assumes some very specific meaning for the space dimensions,
Right. We can just have this sorting function in the cloog-ppl back-end. I don't understand very well the implications of replacing this ordering with another one for the generated code, but I did experimented with some unusual sortings and the code generated did not looked the same...
On the other hand, having worked on it, I can fairly say that such an inclusion in the PPL would not buy much in terms of efficiency:
Thanks for the detailed improvement descriptions. I will try to get these implemented.
Sebastian
Hi Sebastian (and colleagues).
I have a question regarding the cloog_domain_simplify operator.
I would like to know the result that should be expected when simplifying the following domain, having just a single polyhedron which is the two dimensional square [ { 10 <= x <= 40, 10 <= y <= 40 } ]
with respect to the following domain context, which is composed by four disjoint squares, all having a proper intersection with the square above: [ { 0 <= x <= 20, 0 <= y <= 20 }, { 0 <= x <= 20, 30 <= y <= 50 }, { 30 <= x <= 50, 0 <= y <= 20 }, { 30 <= x <= 50, 30 <= y <= 50 } ]
If we encode the two unions above in PPL and run the simplify_using_context() on our Pointset_Powerset domain, we will obtain no simplification at all, i.e., the result is indeed the singleton input square. This makes sense, as far as I can see, since no constraint in the input polyhedron is redundant for all the disjuncts of the context.
I am wondering if this is the expected result and, most importantly, whether or not the algorithm that is currently implemented in cloog (it is meant, by cloog when using the PPL) provides the same result. My wild guess is that the cloog algorithm is computing something different ... and probably wrong. It seems that it would add to the result a lot of polyhedra, among which the universe polyhedron, which causes all of the other polyhedra in the union to be simplified away. That is, it will obtain a singleton union containing the universe polyhedron.
To my eyes, returning the universe domain is wrong, in that it won't be preserving the intersection of the two input domains.
I would have run some test on cloog myself, but I can't see how to (easily) feed in the specific input above. So I am asking if you can help me in this respect. Let us know, if possible, the result actually computed by cloog on the example above, as well as comments on whether or not the result computed by the PPL makes any sense.
Cheers, Enea Zaffanella.
Resending (with apologies) after correcting the subject line.
Enea Zaffanella wrote:
Hi Sebastian (and colleagues).
I have a question regarding the cloog_domain_simplify operator.
I would like to know the result that should be expected when simplifying the following domain, having just a single polyhedron which is the two dimensional square [ { 10 <= x <= 40, 10 <= y <= 40 } ]
with respect to the following domain context, which is composed by four disjoint squares, all having a proper intersection with the square above: [ { 0 <= x <= 20, 0 <= y <= 20 }, { 0 <= x <= 20, 30 <= y <= 50 }, { 30 <= x <= 50, 0 <= y <= 20 }, { 30 <= x <= 50, 30 <= y <= 50 } ]
If we encode the two unions above in PPL and run the simplify_using_context() on our Pointset_Powerset domain, we will obtain no simplification at all, i.e., the result is indeed the singleton input square. This makes sense, as far as I can see, since no constraint in the input polyhedron is redundant for all the disjuncts of the context.
I am wondering if this is the expected result and, most importantly, whether or not the algorithm that is currently implemented in cloog (it is meant, by cloog when using the PPL) provides the same result. My wild guess is that the cloog algorithm is computing something different ... and probably wrong. It seems that it would add to the result a lot of polyhedra, among which the universe polyhedron, which causes all of the other polyhedra in the union to be simplified away. That is, it will obtain a singleton union containing the universe polyhedron.
To my eyes, returning the universe domain is wrong, in that it won't be preserving the intersection of the two input domains.
I would have run some test on cloog myself, but I can't see how to (easily) feed in the specific input above. So I am asking if you can help me in this respect. Let us know, if possible, the result actually computed by cloog on the example above, as well as comments on whether or not the result computed by the PPL makes any sense.
Cheers, Enea Zaffanella.
Hi,
On Tue, Sep 16, 2008 at 11:42 AM, Enea Zaffanella zaffanella@cs.unipr.it wrote:
I would like to know the result that should be expected when simplifying the following domain, having just a single polyhedron which is the two dimensional square
Let's call this the iteration domain D:
[ { 10 <= x <= 40, 10 <= y <= 40 } ]
with respect to the following domain context, which is composed by four disjoint squares, all having a proper intersection with the square above:
Let's call this the context C:
[ { 0 <= x <= 20, 0 <= y <= 20 }, { 0 <= x <= 20, 30 <= y <= 50 }, { 30 <= x <= 50, 0 <= y <= 20 }, { 30 <= x <= 50, 30 <= y <= 50 } ]
I'm looking at the simplification algorithm from a program transform standpoint. The above problem is then formulated as, given a loop nest iterating over D:
for (x = 10; x <= 40; x++) for (y = 10; y <= 40; y++) stmt0 (x, y);
and knowing that "stmt0 (x, y)" is a nop for all the points in the context C, i.e. for example "stmt0 (x, y)" could be:
if (!C) stmt1 (x, y);
The domain simplification would try to remove the condition "if (!C)", and this can potentially split the convex polyhedron D into a union of convex polyhedra: in this case it would be the cross remaining after removing the corners of D. The separate convex domains of the result are then scanned one by one: distinct loop nests are generated for each convex component of the union.
If we encode the two unions above in PPL and run the simplify_using_context() on our Pointset_Powerset domain, we will obtain no simplification at all, i.e., the result is indeed the singleton input square. This makes sense, as far as I can see, since no constraint in the input polyhedron is redundant for all the disjuncts of the context.
Returning the original polyhedron D is safe.
I am wondering if this is the expected result and, most importantly, whether or not the algorithm that is currently implemented in cloog (it is meant, by cloog when using the PPL) provides the same result. My wild guess is that the cloog algorithm is computing something different ... and probably wrong. It seems that it would add to the result a lot of polyhedra, among which the universe polyhedron, which causes all of the other polyhedra in the union to be simplified away. That is, it will obtain a singleton union containing the universe polyhedron.
To my eyes, returning the universe domain is wrong, in that it won't be preserving the intersection of the two input domains.
You are right, this is an implementation error in the cloog-ppl backend.
I would have run some test on cloog myself, but I can't see how to (easily) feed in the specific input above. So I am asking if you can help me in this respect. Let us know, if possible, the result actually computed by cloog on the example above, as well as comments on whether or not
you would have to write a program using cloog_domain_union_read and then pass on stdin the matrix representation of domains: for example
D = [ { 10 <= x <= 40, 10 <= y <= 40 } ]
should be encoded like this:
4 4 1 1 0 -10 1 -1 0 40 1 0 1 -10 1 0 -1 40
then call cloog_domain_simplify on the domains, or DomainSimplify on the PolyLib polyhedra. I agree that this interface is painful to use.
the result computed by the PPL makes any sense.
Yes, the result computed by the PPL is correct.
Sebastian
On Tue, Sep 16, 2008 at 02:55:10PM -0500, Sebastian Pop wrote:
then call cloog_domain_simplify on the domains, or DomainSimplify on the PolyLib polyhedra. I agree that this interface is painful to use.
Suggestions for a better interface are welcome.
skimo
Sebastian Pop wrote:
Hi,
[...]
You are right, this is an implementation error in the cloog-ppl backend.
[...]
Yes, the result computed by the PPL is correct.
Sebastian
Sebastian,
if you are interested, I have ready (see attached file) a replacement of function cloog_simplify_domain that uses the PPL implementation: it translates the two cloog input domains into PPL powersets, do the job, and translates back the result into a cloog domain.
Note that in order to use this function you will have to wait for the next PPL snapshot (the last snapshot does not include a few fixes regarding the C interface for powersets). If really impatient, you can try it with the CVS version.
Enea.
Enea Zaffanella wrote:
Sebastian Pop wrote:
Hi,
[...]
You are right, this is an implementation error in the cloog-ppl backend.
[...]
Yes, the result computed by the PPL is correct.
Sebastian
Sebastian,
if you are interested, I have ready (see attached file) a replacement of function cloog_simplify_domain that uses the PPL implementation: it translates the two cloog input domains into PPL powersets, do the job, and translates back the result into a cloog domain.
Note that in order to use this function you will have to wait for the next PPL snapshot (the last snapshot does not include a few fixes regarding the C interface for powersets).
Hi there,
the new snapshot is online:
ftp://ftp.cs.unipr.it/pub/ppl/snapshots/ppl-0.10pre30.tar.bz2
Please, let us know how it goes. All the best,
Roberto
participants (8)
-
Albert Cohen -
Enea Zaffanella -
Jack Howarth -
Paolo Bonzini -
Roberto Bagnara -
Sebastian Pop -
Sven Verdoolaege -
Vincent Loechner