Re: failure due to compiler?

flake@elda.demon.co.uk (Peter L Flake) writes:


> The most obscure compiler bug I ever came across was in the Multics BCPL
> compiler. It had a code generation bug which depended on which procedure was
> done first. It also had a random number generator based on the CPU clock
> which determined the order in which code generation was done. So a correct
> BCPL program would sometimes compile correctly, and sometimes incorrectly!


> [Anyone got any insight into why in the world they made a non-deterministic
> compiler? -John]


I can't explain away a random number generator, but I have another possible
explanation for non-determinstic compiler effects... dynamically allocated
data structures which are at different addresses for different runs of the
same program with the same input data. As our group learned (the hard way),
if you have an algorithm which has implicit order dependencies on dynamic data
structure addresses, you can run into secondary or tertiary non-deterministic
effects.


In our group's Delta research compiler, written in SETL, the expression
simplifier used sets for certain unordered data structures (e.g., for the
arguments to associative commutative integer operators like + and *) because
they were much faster than tuples (SETL's primary ordered data structure).
Because our SETL implementation used the addresses of dynamically allocated
structures to decide what order to return set elements to the caller, it would
_randomly_ return set elements in different orders for exactly the same set
contents in different runs of Delta with the same FORTRAN program as
input... causing the simplifier to produce different output in different runs.
Even though this is not directly a problem (the different outputs are, after
all, mathematically equivalent), sometimes one output would trigger a bug
elsewhere and another would not... and, if a bug-inducing ordering only
happened once in a great while, it made fixing that bug a difficult problem.


So, when we implemented an expression simplifier in Polaris, our most recent
research compiler, we took a small performance hit (using strcmp instead of
address compare) by using a variable's name as its key in the simplifier's
data structures instead of the address of its underlying Symbol object...
this made the expression simplifier return the same results for the same
FORTRAN input on different runs of Polaris, which greatly eased debugging.
--
John R. Grout Center for Supercomputing R & D j-grout@uiuc.edu
Coordinated Science Laboratory University of Illinois at Urbana-Champaign
--

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