[LLVMdev] Correctness of Optimization Phases

[Rafael Espíndola]

> Prooving correctness of a compiler is really an NP problem. This goes for
> any compiler backend. All you can do is have enough test cases.
No. To be in NP it would be necessary for a Non-deterministic
Polynomial algorithm to exist. There is no such algorithm. The problem
is undecidable.

It doesn't means that it is impossible to prove the correctness of a
compiler. It means that no algorithm can do it.

>From a practical point of view, I think that the original question was:

Are the different optimizations "expected" to work in any order or do
they have some inter dependencies?
(I don't know the answer)

> Aaron

Rafael