llvm dev - Jul 2006 - [LLVMdev] Correctness of Optimization Phases

I may sound stupid but can someone tell me that after applying
optimization sequences randomly whether we can surely say that the final
output is correct?

I mean if we apply 12 options in random sequence provided by 'opt'
command
is the output is always correct  (i.e. program does the same thing and
results
are same as expected) ?

Is it Yes by implemention of LLVM or we have to check everytime?

Thanks.

On Wed, Jul 19, 2006 at 03:09:44AM +0800, deveshti at comp.nus.edu.sg
wrote:
> I may sound stupid but can someone tell me that after applying
> optimization sequences randomly whether we can surely say that the
> final output is correct?
Answering this question is equivalent to solving the Halting Problem.
 
> I mean if we apply 12 options in random sequence provided by 'opt'
> command is the output is always correct  (i.e. program does the same
> thing and results are same as expected) ?
>
> Is it Yes by implemention of LLVM or we have to check everytime?
It is the intended effect that the output is always correct, but LLVM
has no proof of this happening.  Testing on lots and lots of programs
and inputs is what is currently done to find whether there are bugs.

-- 
Misha Brukman :: http://misha.brukman.net

>> I may sound stupid but can someone tell me that after applying
>> optimization sequences randomly whether we can surely say that the
>> final output is correct?
>
> Answering this question is equivalent to solving the Halting Problem.
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.

Aaron

Hi,

I tried this thing (Optimization phase sequence) randomly and found that
original fear that they might not produce the same output is true. :-(

Yes, I think only load of testing is the only way out, if you want to get
out.




On Wed, July 19, 2006 5:57 am, Misha Brukman wrote:
> On Wed, Jul 19, 2006 at 03:09:44AM +0800, deveshti at comp.nus.edu.sg
> wrote:
>> I may sound stupid but can someone tell me that after applying
>> optimization sequences randomly whether we can surely say that the
>> final output is correct?
>
> Answering this question is equivalent to solving the Halting Problem.
>
>> I mean if we apply 12 options in random sequence provided by
'opt'
>> command is the output is always correct  (i.e. program does the same
>> thing and results are same as expected) ?
>>
>> Is it Yes by implemention of LLVM or we have to check everytime?
>
> It is the intended effect that the output is always correct, but LLVM
> has no proof of this happening.  Testing on lots and lots of programs
> and inputs is what is currently done to find whether there are bugs.
>
> --
> Misha Brukman :: http://misha.brukman.net
>