On Mon, Aug 08, 2005 at 08:35:31PM +0200, Sebastian Pop wrote: > I'll try to explain again the goal of the project in a shorter > version. I have implemented a data dependence analysis, and I want to > validate the results that it produces. For this, I'm proposing to > compute the same information using another algorithm, and finally do a > diff. > > The second implementation of the data dependence analysis is using the > Omega solver. However, this solver is known to be exponential on some > cases (not all the cases, and in practice when used for basic data > dependence problems it is fast). So the only option we have is to not > expose this solver to our users, but use it for debugging and > improving the compiler.
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. For example, binary decision diagrams are commonly used in digital logic optimization and formal verification, even though they can require exponential space.
