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) :)
