Re: Omega data dependence test for trunk

["Sebastian Pop" <sebastian dot pop at inria dot fr>]

Hi,

On 3/6/07, Diego Novillo <dnovillo@redhat.com> wrote:
> OK with some minor corrections.  Thanks for your patience.

Thanks for the review.  I committed the patch with the modifications
after bootstrap and testing on i686-linux as revision 122749.
I'm sending just the diffs against the previous diff, such that I don't
spam all the mailing list again with the huge patch.

> Could you add an entry for the Omega solver in doc/loop.texi?  We need
> enough high-level description so that people can get basic usage information.

Here is the documentation for the Omega solver.

Index: gcc/doc/loop.texi
===================================================================
--- gcc/doc/loop.texi	(revision 122747)
+++ gcc/doc/loop.texi	(working copy)
@@ -26,6 +26,7 @@ variable analysis and number of iteratio
* Number of iterations::	Number of iterations analysis.
* Dependency analysis::		Data dependency analysis.
* Lambda::			Linear loop transformations framework.
+* Omega::			A solver for linear programming problems.
@end menu

@node Loop representation
@@ -623,3 +624,32 @@ Given a transformed loopnest, conversion
@code{lambda_loopnest_to_gcc_loopnest}.  This function will modify the
loops so that they match the transformed loopnest.

+
+@node Omega
+@section Omega a solver for linear programming problems
+@cindex Omega a solver for linear programming problems
+
+The data dependence analysis contains several solvers triggered
+sequentially from the less complex ones to the more sophisticated.
+For ensuring the consistency of the results of these solvers, a data
+dependence check pass has been implemented based on two different
+solvers.  The second method that has been integrated to GCC is based
+on the Omega dependence solver, written in the 1990's by William Pugh
+and David Wonnacott.  Data dependence tests can be formulated using a
+subset of the Presburger arithmetics that can be translated to linear
+constraint systems.  These linear constraint systems can then be
+solved using the Omega solver.
+
+The Omega solver is using Fourier-Motzkin's algorithm for variable
+elimination: a linear constraint system containing @code{n} variables
+is reduced to a linear constraint system with @code{n-1} variables.
+The Omega solver can also be used for solving other problems that can
+be expressed under the form of a system of linear equalities and
+inequalities.  The Omega solver is known to have an exponential worst
+case, also known under the name of ``omega nightmare'' in the
+literature, but in practice, the omega test is known to be efficient
+for the common data dependence tests.
+
+The interface used by the Omega solver for describing the linear
+programming problems is described in @file{omega.h}, and the solver is
+@code{omega_solve_problem}.


> > +/* Normalizes PB by removing redundant constraints.  Returns
> > +   normalize_false when the constraints system has no solution,
> > +   otherwise returns normalize_coupled or normalize_uncoupled.  */
> > +
> > +static normalize_return_type
> > +normalize_omega_problem (omega_pb pb)
> > +{
>
> This could use some comments or, better, some factorization.  It's
> rather long and cryptic.

I will rework that part as a separate patch.


> Simpler to use XNEW.

fixed.

> We are leaking memory here (the three *eqs arrays).

fixed.

> > +  /* ELIMINATE_REDUNDANT_CONSTRAINTS: use expensive methods to
> > +     eliminate all redundant constraints
> > +
> > +     #ifdef ELIMINATE_REDUNDANT_CONSTRAINTS
> > +     if (!omega_eliminate_redundant (pb, true))
> > +     return;
> > +     #endif
> > +  */
> > +
>
> Are you thinking of resurrecting this?  Perhaps make it a --params?

Transformed into a param.

> > +/* */
> > +
> > +static enum omega_result
> > +parallel_splinter (omega_pb pb, int e, int diff,
> > +                enum omega_result desired_res)
>
> Ahem ;)  Several functions are still missing documentation for their
> arguments as well.

fixed.

> > +/* Helper function: solve equations one at a time.  */
> > +
> > +static enum omega_result
> > +omega_solve_geq (omega_pb pb, enum omega_result desired_res)
> > +{
>
> Another long and cryptic function.  Can it be factored or at least
> heavily commented?

I will document and try to split it in smaller pieces in the next patch.

> > +  /*
> > +     #ifdef clearForwardingPointers
> > +     for (i = 1; i <= pb->num_vars; i++)
> > +     if (!omega_wildcard_p (pb, i))
> > +     pb->forwarding_address[pb->var[i]] = 0;
> > +     #endif
> > +  */
> > +
>
> Same question as before.  If this is not coming back, better take it out.

removed.

Thanks again,
Sebastian