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