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