[PPL-devel] PPL and simplification of polyhedra

[Albert Cohen]

On Mon, Aug 18, 2008 at 08:21:55PM +0200, Roberto Bagnara wrote:

> >> we need to have a more precise specification of the required operation.
> >> In particular, for the simplification of  { A <= 0 } under the context
> > 
> > I assume you mean { A = 0 } here (as { A <= 0 } is not a subset of
> > {A >= 0}).
> 
> I don't follow: why should the first polyhedron (the one to simplify)
> be a subset of the second polyhedron (the context)?

A generic "gist" should not restrict in any way the polyhedron to be
simplified w.r.t. the context polyhedron (both could be unions, in
fact). So your example makes perfect sense, but maybe Skimo had stg
else in mind?

> >> { A >= 0 }, what do you consider simpler?
> >>
> >> Possibility 1:  { A <= 0 }
> >> Possibility 2:  { A = 0 }.
> > 
> > I asked the same question on the polylib mailing list many
> > years ago but got no answer.

Strange.

I did not check what the PolyLib or Omega do, but {A=0} whould make
more sense although it may cost more to achieve. We do not need to
work on integer points only for this simplification, though, and I
don't think the PolyLib implements more than a bunch of special cases
here (but I'm not at all familiar with that code).

> I see.  However, I am interested in understanding the real needs of Cloog
> independently from what PolyLib does.

It's hard to define formally, but generally speaking, I would say the
shortest the constraint list the better, and the simplest the
expressions the better (involving less variables). There is probably
not a unique optimal solution, but the intuition is that code has to
be generated from these contraints (loop bounds or conditionals), and
more constraints or more terms means more costly control flow and
boolean expressions.

Albert

-- 
Albert Cohen                            http://www-rocq.inria.fr/~acohen