Re: [4.2 projects] Omega data dependence test

[Daniel Berlin <dberlin at dberlin dot org>]

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

The plan was to use it as one of the data dependence testers for, well,
data dependence :)

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

My goal with Omega (which may not be sebastians) was to use it when the
cheaper tests fail.

This is fairly typical usage of data dependence testers, testing with
progressively more expensive ones up to one that can you an exact result.

OTOH, Omega was relatively cheap (compared to other non-simplifying
exact techniques) when it was written (1992), and it's probably even
cheaper now.

IIRC, it was like 89ms per test back in 1992.


>> Index: omega.c
>> > ===================================================================
>> > --- omega.c	(revision 0)
>> > +++ omega.c	(revision 0)
>> > @@ -0,0 +1,5575 @@
>> > +/* Source code for an implementation of the Omega test, an integer
>> > +   programming algorithm for dependence analysis, by William Pugh,
>> > +   appeared in Supercomputing '91 and CACM Aug 92.
>> > +
>> > +   This code has no license restrictions, and is considered public
>> > +   domain.
>> > +
> Hmm, I do not know how we handle public domain code in GCC.  You will
> have to ask the SC about this.
>
I asked various people before we started down this road, and was told it
was fine.
Maybe this is different due to recent events.
The author of the code is happy to verify it really is public domain,
and has absolutley no license restrictions, if that is what is wanted.