volatile: a summary

[Peter J Desnoyers]

In article <5807 at bloom-beacon.MIT.EDU> scs at adam.pika.mit.edu (Steve Summit) writes:
>In article <11837 at mimsy.UUCP>, chris at mimsy.UUCP (Chris Torek) writes:
>> A perfect compiler would know as much as all its programmers combined,
>> and could use whatever rules those programmers would use to detect
>> `real volatility'.
>(which I was quite willing to do, because Chris is a trustworthy
>sort) to realize that he does, as usual, know what he is talking
>about.  Chris is correct when he says that "a perfect compiler
                  -------
>would not need volatile" but he is not saying that such a
>compiler would be reasonable.  He has stated several times that
>an explicit "volatile" keyword is an eminently reasonable
>pragmatic solution to a theoretically difficult problem, a
>position with which I certainly agree.

I am not saying that such a compiler is unreasonable; we all know
that. I'm trying to say that it is uncomputable.

I think my example posted recently (a hairy dma i/o device) was not
examined closely enough. In order to spare you a few pages of
pseudo-math, I'll use a simpler example - shared memory.

If p = cr_shr_mem( size)    (I don't remember the name or all the args)
then the compiler must assume that memory from p to p+size is
volatile. However, if `size' is computed at run time, it is not
known to the compiler. (computing its range is equivalent to solving
the halting problem) Thus anything between p and the top of memory is
volatile. In fact, anything aliased with (p,maxmem) is volatile, and
deciding aliasing is not computable. Thus your whole data space is
volatile. 

The original proposal was for a mechanism to flag specific volatile
addresses to the compiler in a startup file, so that the compiler
would know as much as the programmer, e.g.
  volatile 0x4e00 .. 0x4e10;	/* sio chip */
This is obviously computable, but not sufficient to handle more
complicated cases of volatility like shared memory or dma buffers.

I'm not sure, but I think that if the compiler is to halt, any more
complicated specifications (e.g. shared memory above) are equivalent
to specifying all memory as volatile. Thus the programmer knows more
than the compiler, and a volatile keyword is in theory, as well as in
practice, more useful. 

How do programmers decide questions that are not decidable by the
compiler? They don't. They avoid them. Compilers cannot avoid any
construct that is legal in the language, while programmers can and do
in the name of decent programming style.  Fortran programmers
routinely use vector operations that require non-aliased arguments.
Whether or not the arguments are aliased is not decidable, but the
programs work. 

				Peter Desnoyers
				peter at athena.mit.edu