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.