[PPL-devel] [Fwd: Re: patch for merging graphite branch (before tuplification)]

[Sebastian Pop]

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=d78c8bb5f121aaaa78f69b643c26dde11c909755;hp=fbc2c6b341f5a1dadaa4f76cb07f9cbb1e9a7f8b
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=b2a471f465823452c2c6750c21dc628ea9bf9bd8
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=da969835f0d86b4b1d2dff3b5bca479ee9c47241
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=da969835f0d86b4b1d2dff3b5bca479ee9c47241

Sebastian Pop
--
AMD - GNU Tools