Re: [4.2 projects] Omega data dependence test

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Diego Novillo wrote:
> I guess your idea is to use Omega as one of the data dependency
> analyzers in GRAPHITE?  

Yes, this is the plan.  For GRAPHITE we'll need a much more precise
dependence information than what we have in tree-data-ref at the moment.

> Omega is generally a fairly expensive
> analyzer, is your goal replacing the data dependency routines that we
> already have in tree-data-ref.c?
> 

I will not replace the existing analyzers with the omega test.  As
Daniel said, the existing filter of dependnece tests gradually grow in
complexity of the computation, and this is also what other compilers
are doing.

> I'm a bit concerned about a potential explosion of different
> experimental analyzers.  I'm not opposed to extending GCC's
> capabilities in this area, on the contrary, we badly need smarter LNO
> techniques.  However, I also don't want to move into a purely research
> direction.  What are your long terms plans here?
> 

For the moment as you saw in the patch, the use of the omega solver is
limited to setting problems whose solutions are the distance vectors.
This is mainly useful for correcting and checking the existing
routines in tree-data-ref.  For being honest, the dependence
information is not yet used enough for being confident on the changes
that go to the data dependence tests.  I have already seen that some
corrections to the dependence analyzer have introduced bugs, and
without an alternate way to compute the same information it is hard to
check the information provided by the tests.

The next step will be the use of the omega test in dependency testing
for the fortran front-end.  The main difference with the routines in
tree-data-ref is that omega is working only on integers and does not
expect any strange IR to be built.  In this respect the omega test is
simpler to integrate in other parts of the compiler.  The problems
that we'll have to construct in the fortran front-end will have very
limited sizes: one loop and two variables or so, and thus even
exponential behavior will be harmless for such reduced systems.

The new functionalities of the LNO will however need the full power of
omega until more specialised algorithms are integrated: the code
generation from a polyhedral representation is based on reductions of
the iteration space by projections.  At the origin the omega solver
has been designed for testing data dependences, and thus it might be
more expensive than other algorithms, I'm thinking about the algorithm
in piplib.org.

On a more "political" point of view, attracting the research community
around GCC by proposing state of the art techniques that can easily be
extended is one of the goals to make GCC the de facto compiler for
compiler research.  The functionality that we will add is badly needed
for making GCC compete with the same weapons as other industrial
compilers.

> A bit of usage documentation, including a brief overview of how the
> solver works and examples at the top of the file would be useful.
> 
> I still have not finished reading the whole patch.  It mostly looks fine,
> though.  Instead of waiting until I'm done with it, we can get started with
> some initial feedback.
> 

Thanks, I will prepare an updated patch and will commit all these
requested changes to autovect branch.

Sebastian