[PPL-devel] simplify_using_context() vs. cloog_domain_simplify()

[Sebastian Pop]

Hi,

On Tue, Sep 16, 2008 at 11:42 AM, Enea Zaffanella
<zaffanella at 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