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