Re: How to verify that optimizations preserve semantics

"Stephan Ceram" <linuxkaffee_@_gmx.net> wrote in message
> I was wondering how compiler optimisations can be verified,
> i.e. whether they perform always valid code modifications? How is it
> done in practice?


> I assume that the only safe way would be to formulate the applied code
> modifications as formal transformations that model every possible
> situation that can ever occur. But on the other hand this seems to be
> infeasible for most optimisations since they are too complex for
> analytical models.


well, one can use their head, but not necessarily in the formal sense.


namely, one can try to think of any case where the optimization could risk
changing the external/observable behavior of a piece of code.


if there is such a change, one can then be left to consider the likely
impacts and/or remedies, or if it would be better not to do so.




> An alternative would be regression tests, but are such tests safe? I
> mean you can never be sure that you did not miss a scenario that may
> occur in practice.
>


good tests can easily catch maybe 90% of most problems which will pop up (if
not more, if the tests are good).


this is because most breaks will pop up readily...


one example of a kind of test would be to have the compiler compile itself
and see if the newly built compiler can in turn compile itself without
crashing or producing different output (ignoring any values generated by
TRNG's or similar, which in my case are typically internal "gensym's").


admittedly, this test requires the compiler and target language to be the
same:
for example, a C compiler to compile a compiler written in C.


typically, any other large piece of code can be used similarly.




also common is the "corpus" strategy, where one has a collection of smaller
programs each designed to try to test a different feature or exploit the
compiler in a certain way, and one can run these tests and see which of them
either break the compiler, or produce divergent results.






another test strategy, which may work well (for code that one is already
fairly sure works), is to start feeding it "well-formed-garbage", where one
can basically have a program randomly throw together tests using whatever
parts it has at its disposal, then this test is fed through the tool, and
the output is verified to work (presumably, the tool auto-generating the
tests has a good understanding of the formal model and can predict the
expected output).


another possibility is to design tests that are in themselves basically
large hash-functions (in a "Rube Goldberg" sort of way), and then verify
that the final expected hash-value is generated.




note:
also worthwhile for an optimization is to verify that the optimization
actually makes things any faster...
(rather than "could make things faster" or "sounds nice on paper"...).


this can also be done via tests, where one can measure the running time, and
then come up with averages estimating the performance, ...






side note:
I have not done anywhere near this level of testing with my compiler, as
admittedly, it has thus far not even really managed to fully pass my tests
for known good (conventional) code.


it is a long and gradual process of beating out bugs and improving
performance.


but, FWIW, I have little intention to compete with conventional static
compilers (mostly I use it for scripting), so bugs are something to be
addressed (eventually), rather than the death-toll for the project (as would
be more the case if intending to compete with existing compilers...).


but, in its newer task of information mining/..., addressing bugs/... has
become more of an issue.
as well, it may well get up to being fast enough to actually be useful for
scripting... (for a script compiler, lower-millisecond or less compile-times
are preferable... vs upper-millisecond or second-range times...).


(one may be left tempted to move to a hybrid-interpreter strategy in the
quest to improve compile-times...).




but, there are a great many concerns for a compiler:
how reliable it is (accepts valid input, produces solid code, ...);
how good is the code it produces (size, speed, ...);
how quickly it can compile the code (less of an issue for static compilers,
so long as the times are not absurd, it is acceptable...);

Return to the comp.compilers page.
Search the comp.compilers archives again.