[GCC 4.2 Project] Omega data dependence test

[Daniel Berlin]

On Tue, 9 Aug 2005, Sebastian Pop wrote:

> Joe Buck wrote:
>> Algorithms that are sometimes exponential can still be used if there is
>> a cutoff mechanism, to abort the algorithm if it exceeds a budget.  This
>> assumes that we can then fall back to an algorithm that might produce
>> inferior results, but will produce something usable in reasonable time.
>>
>
> Okay, I stand corrected.  As a practical implementation we can have a
> mechanism as push/pop timevar, that would monitor the time and space
> of an algorithm and that can cancel the computation for failing on a
> safe approximation.  As a first concretization, I was thinking to use
> threads, but I'm not sure whether this is suitable for GCC.

A lot of data dependence related algorithms are exponential in the worst 
case, and work fine in production compilers, without cutoffs.

XLC uses fourier motzkin without any cutoffs, for example (as does intel, 
i believe) :)


>
>