smryan@garth.UUCP (Steven Ryan) (06/09/88)
This is getting ridiculous. I propose a formal schism between the AI church that believes computers can do anything and a pragmatic church that believes computers are stupid. This is the class of conflict that makes both the roman catholic church and eastern orthdox the one true Christian church.
chris@mimsy.UUCP (Chris Torek) (06/09/88)
In article <705@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >This is getting ridiculous. I propose a formal schism between the AI church >that believes computers can do anything and a pragmatic church that believes >computers are stupid. (Apologies for the harsh tone, but it is obvious that those who are objecting to my reasoning have not thought about implmentations and their difficulties. I thought a bit of chastisement in order. :-) ) I am guessing that this is in response to my suggestion that whenever a programmer can discover that *(int *)0xf0 is not volatile, but *(int *) 0xff4 is, by reading a manual, a hypothetical perfect compiler can do the same by reading `(the electronic version of) the manual'. Those who believe that this implies `computers can do anything' have not exercised their brain cells about it. Why must the compiler's version of the manual be the same as the programmer's, or even be exclusively in some natural language? The compiler's electronic version of the manual might even read volatile 0xff0..0xf9f In this case, even though the word `volatile' appears *somewhere*, it is nowhere in the C source, and hence the language proper has no volatile keyword. For those who will claim that this is mere trickery, again, you have not thought hard enough about the issue. Instead of `volatile 0xff0..0xf9f' the manual might instead say `ram 0x0..0xeff; ram 0x4000..0xbfffffff'. Instead of saying what *is* volatile, this says what *cannot* *be* volatile. And if the electronic manual does not exist, or if my hypothetical perfect compiler does not exist, as it does not, or even if it *cannot* exist, what then? Is the volatile keyword necessary? No. Consider the IBM PC. (This since I was flamed for using Unix compilers as an example.) In the following (toy) large model program, which assignments might be (not *are*, just *might* *be*) volatile? #define DISPLAY 0xc000000 /* or whatever */ main() { int i, *p1, *p2; p1 = &i; /* 1 */ p2 = (int *)DISPLAY; /* 2 */ *p1 = 3; /* 3 */ *p2 = 'k'; /* 4 */ for (; i < 100; i++) { if (rand()) p1 = p2; /* 5 */ *p1 = 0; /* 6 */ } exit(0); } Even without knowing whether 0xc000000 is display RAM, I can accurately predict that assignments number 1, 2, 3, and 5 are *not* into volatile memory; only assignments 4 and 6 can possibly write volatile locations. Whether 4 and 6 actually do write volatile locations (and if I got the display address right, they do not) is not important: all the other assignments do not, and may therefore be optimised. If you claim that this analysis cannot be extended beyond toy programs, then again you have not used your brain. It not only *can* *be* done, it *has* *been* done. You can buy a C compiler today% that does cross-module optimisation. That compiler may not run on an IBM PC. Well, I never said it would be *easy*. And that compiler may produce suboptimal code for assignments that *could* *be* volatile but (as it happens) are not. Well, I said that too. If you believe this argument means I think the volatile keyword is bad, go back and read <11837@mimsy.UUCP>. All I have said is that the keyword is not necessary, not even for optimisation. ----- % One such compiler is the one MIPS uses. I know it does final code generation at link time. Whether it tries to do alias detection at this time I cannot say; but ruling out volatility is a special case of alias detection (`does this pointer alias an unknown variable'). Given that their compiler has the `volatile' keyword, I imagine it does not bother. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/10/88)
In article <225800035@uxe.cso.uiuc.edu> mcdonald@uxe.cso.uiuc.edu writes: >I think Chris is assuming too much here. He must live in a different >world than I do. I don't see how a manual is going to know what's in >a computer. But you forget that the compiler is also supposed to help write the manual. Down with people; they just get in the way!
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/10/88)
In article <796@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >... Now it is essential that the computation of >random() be done at _each_ call. Volatile beats all of the kludges I >have seen to accomplish this. >If some better method than a subroutine call is used for each number, >the problem is still there, and I know of no better way than to use >volatile. Sorry, I didn't follow this. "volatile" doesn't help (is not needed) to ensure that the function really is called each time in the iteration. It also is not needed if you implement your own in-line pseudo-random number generation algorithm. The only time it would help would be if you had an addressible memory location that was really a hardware RNG register.
levy@ttrdc.UUCP (Daniel R. Levy) (06/10/88)
In article <11837@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: # READ THE WHOLE THING BEFORE YOU FLAME. # Given that the keyword is not absolutely necessary, # is it of any use? # # Yes. If the keyword exists, compilers are free to assume that any # variable not tagged by the keyword is truly not volatile. This is a # very easy way to discover which variables should be considered to have # the attribute, and, knowing which variables are not volatile, the # compiler can make a number of optimisations that might otherwise be # unsafe. This is not without its cost: With such a compiler, the ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # programmer must correctly label any variables which do have the ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # volatility attribute. But because the scheme is simple, compilers that ^^^^^^^^^^^^^^^^^^^^^ # use it can be faster than, and need not be as complex as, compilers # that attempt to find `real volatility' with less help from the # programmer. Being less complex, such compilers are more likely to # be correct; being faster, they are more pleasant to use. And therein lies a problem. This could easily break old, "volatile-less" code. I would certainly want such a compiler to have some way of turning off this behavior while still keeping the "obviously" safe optimizations (however the term "obviously" might be defined depending on the smarts in the compiler in question). A compiler which could NOT turn off this "volatile"-assuming optimization would make me nervous whenever reuse of old code is concerned. For argument's sake, is this something which could potentially be specified in the proposed ANSI C specification? Does the spec have any notion of the existence of "compiler flags," i.e., furnishing information not in the source code itself to the compiler at compile time? -- |------------Dan Levy------------| THE OPINIONS EXPRESSED HEREIN ARE MINE ONLY | AT&T Data Systems Group | Weinberg's Principle: An expert is a | Skokie, Illinois | person who avoids the small errors while |-----Path: att!ttbcad!levy-----| sweeping on to the grand fallacy.
chris@mimsy.UUCP (Chris Torek) (06/10/88)
>In article <11848@mimsy.UUCP> I included the line >>A perfect compiler would know as much as all its programmers combined ... but I also included something very important that was subsequently deleted: OF COURSE, NO PERFECT COMPILERS EXIST, NOR ARE ANY LIKELY TO BE WRITTEN IN THE FORESEEABLE FUTURE. In article <691@creare.UUCP> inb@creare.UUCP (Ian Brown) writes: >In other words, with a perfect compiler, who needs programmers? :-) Actually, if you augment it with a perfect language, yes. (There may be an inherent conflict between unambiguous languages and natural languages, which might make perfect languages impossible.) Again from my original article: But good compilers do exist, and better ones are conceivable; a very good compiler could use external information to find most (but not all) variables that are certain *not* to have the attribute, and could then assume that all others do, and this would suffice. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
karl@haddock.ISC.COM (Karl Heuer) (06/10/88)
In article <796@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >[In the code fragment "x = random();"] it is essential that the computation >of random() be done at _each_ call. Volatile beats all of the kludges I >have seen to accomplish this. I don't see what this has to do with the |volatile| in dpANS. C makes no provisions for pure functions, so random() (or getchar()) must always be invoked no matter what (subject, as always, to the as-if rule). Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
cunniff@hpfcdc.HP.COM (Ross Cunniff) (06/11/88)
In article <11884@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: > ...whenever a > programmer can discover that *(int *)0xf0 is not volatile, but *(int *) > 0xff4 is, by reading a manual, a hypothetical perfect compiler can do > the same by reading `(the electronic version of) the manual'.... > ...The compiler's electronic > version of the manual might even read > > volatile 0xff0..0xf9f > > In this case, even though the word `volatile' appears *somewhere*, it > is nowhere in the C source, and hence the language proper has no > volatile keyword. > > For those who will claim that this is mere trickery, again, you have > not thought hard enough about the issue. Instead of `volatile > 0xff0..0xf9f' the manual might instead say `ram 0x0..0xeff; ram > 0x4000..0xbfffffff'. Instead of saying what *is* volatile, this says > what *cannot* *be* volatile. And if the electronic manual does not > exist, or if my hypothetical perfect compiler does not exist, as it > does not, or even if it *cannot* exist, what then? Is the volatile > keyword necessary? No. This is all fine and dandy for those volatile hardware addresses which a C program may access. It doesn't do diddly-squat for the following type of program (this example should but doesn't use volatile): /* foo.c */ extern int *p; foo( x ) { int i; *p = x; if( *p == x ) { /* With an optimizing compiler, this part of the */ /* 'if' is likely ALWAYS to be executed, regardless */ /* of whethter other processes are playing with */ /* shared memory */ printf( "Nobody else is plaing with shared memory\n" ); } else { printf( "Wow! somebody else is out there...\n" ); } } /* main.c */ int *p; char *shm_get(); main() { p = (int *)shm_get( 3000, "foobar" ); foo( getpid() ); } Note that there is *NO WAY* for the compiler *OR* the linker to know where the shm_get thingie is going to attach the shared memory segment. Oh, sure, you could have a dictionary that says that 'volatile shm_get', but if you're going to go that far, you might as well just add volatile to the standard (oh, we're already doing that?). Ross Cunniff Hewlett-Packard HP-UX DCE lab ...{ucbvax,hplabs}!hpda!cunniff cunniff%hpda@hplabs.ARPA
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/11/88)
In article <2742@ttrdc.UUCP> levy@ttrdc.UUCP (Daniel R. Levy) writes: >For argument's sake, is this something which could potentially be specified >in the proposed ANSI C specification? Does the spec have any notion of >the existence of "compiler flags," i.e., furnishing information not in the >source code itself to the compiler at compile time? No -- every different way of invoking a compiler constitutes a different implementation from the standards viewpoint. Some implementations will be Standard conforming and some will not.
chris@mimsy.UUCP (Chris Torek) (06/13/88)
In article <5080025@hpfcdc.HP.COM> cunniff@hpfcdc.HP.COM (Ross Cunniff) writes: [stuff about shared memory] >Oh, sure, you could have a dictionary that says that 'volatile shm_get', (Well, at least you thought about it.) Yes, you would have to do exactly that, or else not optimise anything that comes back from a system call. >but if you're going to go that far, you might as well just add volatile >to the standard (oh, we're already doing that?). The point is that it is not *necessary* to add volatile as a keyword in the language. I will not go as far as Robert Firth and call it `stupid'; indeed, I happen to like the keyword, even though it is a `hacker's solution'. It is fast and easy, whereas a detailed analysis of possible aliasing and volatility is hard and likely to be slow. Having the keyword is much like having assembly language handy: when you want to do something unusual, it is easy. Error-prone and kludgey, perhaps, but definitely easy. It is just not *necessary*. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
terry@wsccs.UUCP (Every system needs one) (06/14/88)
In article <3811@pasteur.Berkeley.Edu>, faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: > In article <11837@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: > > Is the [volatile] keyword necessary? > > > > 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'. Yes yes yes. > The problem is that these rules may be in the manual for the graphics > board the programmer is writing a driver for. Say there are two memory > mapped registers, "model_number" and "time_of_day", declared as > > int *model_number = (int *) 0xf0; /* Shouldn't be volatile. */ > int *time_of_day = (int *) 0ff4; /* Should be volatile. */ > > model_number will never change, but time_of_day will. How is the compiler > going to tell the difference, without volatile? No no no. The compiler will know because, as part of the board installation, you will tell it... or we could make a hardware-standard (I know; too much to ask for) method of asking it. The machine should "know" about the machine. How can you possibly expect it to know if you don't tell it ("how can you have any pudding if you don't eat your meat?"). The question raised by your new board is whether "volitility" will be defined in an installation dependant way by the programmer, or in an installation independant way by the installer. We have a great deal of hardware-specific kernel information already there... what's the point in providing yet another method of making "magic" numbers "known" to the computer via "volitile" in the compiler when it is just as easily done by reference to a device configuration file? This file would not only be useful to the compiler, it would allow configuration, and possibly even machine independant installation of drivers and devices. | Terry Lambert UUCP: ...{ decvax, ihnp4 } ...utah-cs!century!terry | | @ Century Software OR: ...utah-cs!uplherc!sp7040!obie!wsccs!terry | | SLC, Utah | | These opinions are not my companies, but if you find them | | useful, send a $20.00 donation to Brisbane Australia... | | 'Signatures; it's not how long you make them, it's how you make them long!' |
peter@athena.mit.edu (Peter J Desnoyers) (06/15/88)
...
[Ross Cunniff argues that you could defeat a compiler 'manual' of
volatile locations; Chris Torek argues that extending the manual would
take care of the problem.]
I think that there are things out there not dreamt of in Chris'
philosphy. For instance, if I have an i/o chip that does complicated
dma, how do you tell the compiler that when I add `buffer' to a
certain queue, all locations starting at &buffer +
sizeof(buffer.header), for &buffer.length {bytes/words/bits} are
volatile until the buffer is taken from another queue? Will your
mechanism work for another, even more complicated dma scheme? What if
you can change the dma model by writing to a device register?
One (unrelated) deficiency I see in |volatile| involves the generation
of spurious writes. In a perfect world, *p = x would generate one
write and no read cycles, at least if *p were volatile. (Read and
write do screwy things with some dumb i/o devices.) I don't have a
copy of the draft standard, but I would assume that this is the sort
of thing that ANSI would never dream of specifying, as it might
prevent a correct implementation on some architecture. I hope that the
people who write cross-compilers keep this in mind when they add ANSI
features, but from what I've seen of current cross-compilers, I don't
have much hope that they will concentrate on making their products
useful. (1/2 :-)
Peter Desnoyers
peter@athena.mit.educhris@mimsy.UUCP (Chris Torek) (06/15/88)
In article <5766@bloom-beacon.MIT.EDU> peter@athena.mit.edu (Peter J Desnoyers) writes: >...For instance, if I have an i/o chip that does complicated >dma, how do you tell the compiler that when I add `buffer' to a >certain queue, all locations starting at &buffer + >sizeof(buffer.header), for &buffer.length {bytes/words/bits} are >volatile until the buffer is taken from another queue? Well, how did you tell me? (I am not sure you *did* tell me. I suspect you meant `buffer.length'. This is the kind of things you would like to describe [correctly] just once, then be able to refer to `that horrid little device over there'.) >Will your mechanism work for another, even more complicated dma >scheme? What if you can change the dma model by writing to a device >register? If the compiler is to compute its own idea of volatility, it must understand all of this. Given that programmers already have enough trouble with `clr' instructions that use RMW cycles, making a compiler understand complicated DMA models would be quite difficult (but again, I claim, not impossible). I would be wary of a compiler that tries to do this (note phrasing :-) ), but I would still like to see it done. Incidentally, will 68000 (note three 0s) compilers studiously avoid `clr.l ea' for `ea' volatile? One would hope so, but putting that into a C language standard is clearly wrong. >One (unrelated) deficiency I see in |volatile| involves the generation >of spurious writes. Or reads. >In a perfect world, *p = x would generate one write and no read cycles, >at least if *p were volatile. ... I would assume that this is the sort >of thing that ANSI would never dream of specifying, as it might >prevent a correct implementation on some architecture. You are correct. Note that, for instance, volatile int *word = (int *)FOO; int tmp; tmp = *word; must generate two read cycles on an eight-bit peripheral attached to a 16-bit machine. (A common hardware hack to work around this problem, incidentally, is to wire [eg] the Z80 SIO chip to A1..An+1 instead of A0..An; Heurikon does this on the 68010 boards we have in McMob. All the device structures are full of pad bytes.) >I hope that the people who write cross-compilers keep this in mind >when they add ANSI features .... This is what X3J11 calls a `quality of implementation issue'. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
ljz@fxgrp.UUCP (Lloyd Zusman) (06/17/88)
In article <580@wsccs.UUCP> terry@wsccs.UUCP (Every system needs one) writes: In article <3811@pasteur.Berkeley.Edu>, faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: > In article <11837@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: > > Is the [volatile] keyword necessary? > > > > 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'. Yes yes yes. > The problem is that these rules may be in the manual for the graphics > board the programmer is writing a driver for. Say there are two memory > mapped registers, "model_number" and "time_of_day", declared as > > int *model_number = (int *) 0xf0; /* Shouldn't be volatile. */ > int *time_of_day = (int *) 0ff4; /* Should be volatile. */ > > model_number will never change, but time_of_day will. How is the compiler > going to tell the difference, without volatile? No no no. The compiler will know because, as part of the board installation, you will tell it... or we could make a hardware-standard (I know; too much to ask for) method of asking it. The machine should "know" about the machine. How can you possibly expect it to know if you don't tell it ("how can you have any pudding if you don't eat your meat?"). ... But what if the value of the address isn't known at compile time? Suppose I am using the following code: extern int *model_addr(); extern int *time_addr(); main() { int *model_number; int *time_of_day; ... model_number = model_addr(); time_of_day = time_addr(); ... while (*time_of_day != 0) { ... } } Perhaps the routines model_addr() and time_addr() look at some system configuration file AT RUN TIME. How can I tell my compiler that the model_number and time_of_day variables should still be treated as "volatile" entities, such as in the 'while' loop near the end of my example? Your suggestion that the *compiler* read a configuration file wouldn't work in this case. However, the programmer still knows that the model_number and time_of_day variables are to be treated as "volatile". I don't understand why there is so much resistance to "volatile". If you don't like it, just don't use it. If you can write an optimizer that somehow can correctly determine all volatility in all cases, then write one ... it could then treat "volatile" as a no-op (as, for example, do some IBM PC based C compilers with the 'register' keyword). But why prevent the rest of us from using it if we want? Besides, I don't believe that anyone *can* write an optimizer that will always correctly identify all volatility, even with the machine configuration file that is proposed (unless, of course, this optimizer treated *all* variables as volatile). -- Lloyd Zusman UUCP: ...!ames!fxgrp!ljz Master Byte Software Internet: ljz%fx.com@ames.arc.nasa.gov Los Gatos, California or try: fxgrp!ljz@ames.arc.nasa.gov "We take things well in hand."
scs@athena.mit.edu (Steve Summit) (06/17/88)
In article <11837@mimsy.UUCP>, chris@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'. In article <700@fxgrp.UUCP> ljz%fx.com@ames.arc.nasa.gov (Lloyd Zusman) writes: >But what if... as have many others. You people need to understand that Chris is being extremely theoretical, to the point of pedagogy (not meant pejoratively), here. It took me several readings of several of his articles (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 _i_s _c_o_r_r_e_c_t when he says that "a perfect compiler would not need volatile" but he is _n_o_t 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. Every article that suggests yet another funky architectural scenario in which it would be next-to-impossible for the compiler to reasonably "figure out" which variables should be volatile overlooks one of the following: 1. There are ways other than a "volatile" keyword to tell a compiler which memory locations are volatile: a configuration file, for instance, not only solves the frequently suggested cross-compilation situations, but is also a better way of handling things like device registers: if location 0xABCD is a keyboard input buffer, it should really be volatile whether or not the programmer remembers to use (or knows about) the "volatile" keyword. 2. If there are ambiguous or computationally undecidable cases, the compiler can always err conservatively by treating questionable variables as volatile (i.e. not optimizing away memory references). Finally, the fact that (2) leads to unacceptable compromises like "all system call return values are volatile," and the fact that other cases are computationally horrendous, is why the "volatile" keyword is useful. Please don't post more "proofs" or counterexamples; when you triumphantly say "So there! No compiler can reasonably get this one right without volatile!" Chris is only going to say "Well, you're right; it could theoretically get it right, but not reasonably, so that's why we'll stick the `volatile' qualifier in." My $0.02 worth: a command-line flag or pragma to effectively make everything volatile would be very nice so that old programs can be "correctly" (if inefficiently) compiled by the newer compilers that make the kinds of optimizations that "volatile" is intended to inhibit. Steve Summit scs@adam.pika.mit.edu
smryan@garth.UUCP (Steven Ryan) (06/18/88)
>You people need to understand that Chris is being extremely >theoretical, to the point of pedagogy (not meant pejoratively), >here. It took me several readings of several of his articles >(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. Of course if such a perfect compiler exists (even if only in the abstract sense), ... The problem is his assertion such a compiler exists without proof, demonstration, argument, or any other foundation. It is as silly to argue what a hypothetical compiler, whose existence is merely asserted, what it can do as to argue that a tree falling in an empty forest makes no sound. If such a compiler can be shown to exist, reasonable or unreasonable, his argument about the necessity of volatile is correct. If such a compiler is shown to be impossible, his argument is wrong. Remember the mess mathmatics was in at the end of the last century because people went around asserting their theorems without a solid foundation or a formal proof. (Who will be Hilbert of computer science? Dijkstra? Hoare?)
chris@mimsy.UUCP (Chris Torek) (06/19/88)
[a defense of me, deleted] >>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. In article <751@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: >The problem is his assertion such a compiler exists without proof, >demonstration, argument, or any other foundation. I asserted not that it does exist, nor even that it could exist, but only that one `perfect enough' to understand volatility (the attribute, not the keyword: the keyword is trivial) in a way that is `good enough' (produces decent code even in the presence of its conservative erring) *could* *be* *written* at some time in the future. This assertion I make without proof or demonstration, but most certainly not without foundation and argument. The problem is reducible to a class of aliasing problems, and even now there are compilers that handle aliasing in a limited fashion. That they will improve is certain; that they will become `good enough' at the volatility class is not, but it looks like a very safe bet to me. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
smryan@garth.UUCP (Steven Ryan) (06/20/88)
In article <12020@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >>>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. >I asserted not that it does exist, nor even that it could exist, but >only that one `perfect enough' to understand volatility ?????? > in a way that is `good enough' >(produces decent code even in the presence of its conservative erring) >*could* *be* *written* at some time in the future. Either it's perfect or it isn't. (Is `perfect enough' like `barely pregnant?') If it isn't perfect, and it can't be, then the original argument that volatile is never necessary is worthless. Obviously one could write a total recursive predicate that partitions what can be handled by a `perfect enough' compiler if conservative erring is accepted. What about what cannot be handled? Is it deemed not worthy of optimisation? Property X (X=volatile or anything else) cannot be determined for these outcasts. Either they are not optimised or a `perfect enough' compiler must be given hints (maybe we could create something like #hint or #pragma or create a new keyword like volatile). sm ryan Arrakis teaches the attitude of the knife: you cut that which is incomplete and say it is complete, because it ends here. -- Frank Herbet/Dune
mouse@mcgill-vision.UUCP (der Mouse) (06/20/88)
In article <796@l.cc.purdue.edu>, cik@l.cc.purdue.edu (Herman Rubin) writes: > [pseudo-random numbers] At each stage, one wishes to get the _next_ > number. There are many ways to do this; the simplest, and one of the > slowest, is to do something like > x = random(); > each time one is needed. Now it is essential that the computation of > random() be done at _each_ call. Volatile beats all of the kludges I > have seen to accomplish this. Volatile is not necessary to ensure this. The compiler is required to behave as if the calls were made as written; since random() has side effects, this involves performing those side effects. This means either actually performing the calls or somehow moving the computation that goes on in random() into the caller - effectively inlining the call. Either way is fine: you get a new "random" number each time flow-of-control passes that point, which is what you wanted. The compiler is not permitted to use CSE as an excuse to throw away routine calls (in the absence of hard information that it's safe to do so, for example, a declaration that the routine is a pure function, or source code to it being available at the time). Imagine what could happen if this were done to read(), for example.... der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
faustus@ic.Berkeley.EDU (Wayne A. Christopher) (06/21/88)
Here is a (stupid) program that proves you cannot always infer volatility:
main() {
int *device_address, i;
printf("Please input \"0x4f0\", the address of the t-o-d register\n");
scanf("%x", (int *) &i);
device_address = (int *) i;
while (*device_address < 43200) /* noon */
;
}
Waynechris@mimsy.UUCP (Chris Torek) (06/21/88)
In article <761@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >(Is `perfect enough' like `barely pregnant?') Use `good enough' if you prefer; it is a better phrasing, anyway. >... Obviously one could write a total recursive >predicate that partitions what can be handled by a `perfect enough' compiler >if conservative erring is accepted. What about what cannot be handled? Is it >deemed not worthy of optimisation? Yes. The real idea is that, if the compilers get it right more often than the programmers, we (Robert Firth and I) would rather have the compilers do it. >Property X (X=volatile or anything else) cannot be determined for these >outcasts. Either they are not optimised or a `perfect enough' compiler >must be given hints .... The same logic can be used to show that whatever optimisation algorithms you use will miss a few `outcasts'. We already accept this. In extreme cases some of us resort to assembly language programming. Others add more algorithms---more hints, as it were. After a while the hints become more expensive than the lost optimisations. (I happen to think that point is not yet reached until *after* the volatile keyword has been added, but that the point is a mvoing target which will eventually move to before that point. Already `register' is fast becoming a noise word.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
smryan@garth.UUCP (Steven Ryan) (06/22/88)
>The real idea is that, if the compilers get it right more often than the >programmers, we (Robert Firth and I) would rather have the compilers do it. That's fine. ANSI is not a law enforcement agency. If the majority of paying customers don't want volatile, it will wither away. If they do, everybody else will have to live with it (unless their compiler has switch to ignore it). There is a lot of muck out in the real world, but calling it stupid is a personal reflection and calling it unnecessary doesn't say to whom.
bill@proxftl.UUCP (T. William Wells) (06/22/88)
In article <11837@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: > [volatile] is a keyword in the draft proposed ANSI C standard, and > it is an attribute of some kinds of variables. As an attribute, it can > be applied to objects such as device registers or shared memory > regions, but not to `ordinary memory'. Uh, didn't you forget things referenced by signal handlers? > > Is volatile necessary? > > This question must be broken down to parts before it can be answered. > Is the concept necessary? Is the keyword necessary? Is the keyword > useful? Is the keyword a `good thing'? > > Is the concept necessary? That is, is the `volatility attribute' > a real thing? > > Not always. Many applications have no need for the concept. Programs > that compute Fibonacci numbers, or that list files, or do any number > of useful things may never care about it. It can be vital to others, > such as device drivers. > > Is the keyword necessary? > > No. (As an existence proof, consider compilers that do not now have > the keyword. Most of them work by not doing much in the way of > optimisation. There is more to it, though.) This is really quite irrelevant. One could ask the question: is C really necessary, and answer: No. For the same "reason". (As an existence proof, consider human existence, which was and still would be doing fine without C. Most people today do not even know it exists.) Such is the nature of this kind of "reasoning". The question, when asking about some human invention, is not: is it necessary, but rather: does it serve a need? There also is the subsidiary question: assuming it does serve a need, does it create more of a problem than it solves? > 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'. As I have said in a previous posting, `real volatility', while it may be apparent in a program, is not an attribute of the program or of any part of it; rather, it is an attribute of the design of the program. Thus, while a compiler MAY be able to discover that the design implies volatility of an object, there is no way, short of telling it, that the design requires volatility. Recall my example of a UNIX scheduler. > (Note that computing `real volatility' can be as hard as solving the > halting problem. I claim only that the compiler can use the same rules > that a programmer would use. Let me repeat... volatility is NOT an attribute of the program. As another example, and one I hope will lay this to rest, consider two programs, both illustrating the use of semaphores. The only difference between the programs is that one has the semaphore variable declared volatile and the other does not. Your professor hands you both and says: run the non-volatile version and make it break, thus illustrating the necessity of the volatile keyword when using semaphores. Then, run the second one through whatever tests you can come up with to demonstrate that it won't break. Both programs are valid: both serve their purpose. The only difference between them is the volatility of the semaphore variable. No compiler CAN decide whether the variable should be volatile. Admittedly, this example is contrived. (So don't bother to flame about that.) But it does serve the purpose: to illustrate my point about designed-in volatility vs. the kind of volatility that everybody else seems to be talking about. They are not the same. In the real world, this designed-in volatility is not always relevant, many programs will have only the "standard" volatility whose presence or absence could be discoved by the compiler. (But note that in my contrived example, said compiler will give the WRONG result.) However, certain systems have the characteristic that their correct function depends on certain objects being volatile, but nowhere in the program does there have to be evidence of this. As I said in my previous posting, resource managers (operating systems, for example) are prone to this problem. (Here also, the compiler could be mistaken.) So, what does the volatile keyword get you? It informs the compiler of the fact that a program will not run as intended, for whatever reason, unless the compiler assumes that something outside its paradigm can change the object at any time. It is telling the compiler that it is a matter of DESIGN of the program that it will not work without this assumption. By having a keyword to inform the compiler of this fact, the compiler may validly assume that any objects not so tagged are not volatile, thus permitting a greater degree of optimization. Thus the answer to the question "does it serve a need?" is definitely yes. The basic problem with adding things like the volatile keyword to the language is that by making the language bigger it makes things more difficult all around. Fortunately for this keyword, there are only two groups of people who even have to know that it exists: compiler writers and those who need to use volatile objects. The first group of people do not seem to be terribly put out by the volatile keyword (and, since I have a good idea of what implementing it entails, I am not really surprised). The second group of people are the specific people for whom the volatile keyword was created, they are certainly not going to be inconvenienced by its existence! The subsidiary question "does it create more of a problem than it solves?" also has an easy answer: no. > Summary of the summary: > Is the concept necessary? Yes. > Is the keyword necessary? No. > Is the keyword useful? Yes. > Is the keyword a `good thing'? Opinion: yes. Given these two answers, I think it more than mere opinion that the volatile keyword is a good thing. > -- > In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) > Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris We do not disagree about the desirability of volatile. My basic reason for harping on this is to make sure that all understand that there is information that the programmer knows which is not present in the program itself. (It is another argument as to whether it OUGHT to be in the program, and how it ought to be presented; this is how I view the volatile argument.) This is true of a lot of information, not just volatility of objects.
peter@athena.mit.edu (Peter J Desnoyers) (06/23/88)
In article <5807@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes: >In article <11837@mimsy.UUCP>, chris@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@athena.mit.edu
chris@mimsy.UUCP (Chris Torek) (06/26/88)
In article <5874@bloom-beacon.MIT.EDU> peter@athena.mit.edu (Peter J Desnoyers) writes: [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. Oops. In the most general case, this is true (although that depends on the details of cr_shr_mem). Hence I must back down a bit. I will ask, though, that if anything in [p..maxmem) could be volatile, how are you as a programmer going to deal with it? How do *you* know what the range of `size' will be? -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
dsill@nswc-oas.arpa (Dave Sill) (07/01/88)
Peter J Desnoyers <peter%athena.mit.edu@BRL.ARPA> writes: >How do programmers decide questions that are not decidable by the >compiler? They don't. They avoid them. No they don't. They decide them by making assumptions or using information that is not available to the compiler. I say we should give the compiler the same information so it can potentially do the same thing the programmer would do. Just how we do this is not clear. In the case of volatility it appears that the best solution for now is the `volatile' storage class. In the case of aliasing we aren't able to agree on a solution, yet. My fear is that we'll just keep adding new storage classes or other keywords as they are needed, making the language more and more complicated, rather than trying to develop a more general solution that fits within the current language. >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. If the programs work, it's because the assumption that the arguments are non-aliased is true. In general, this is not an accident, but is a result of the programmer being aware of the aliasing restriction. Although the aliasing problem in general is undecidable, in reality this is not a problem. In Fortran code using such vector operations the arguments are usually hard-coded arrays and there is no possibility of overlap. In C, things are a little more complicated, particularly due to the use of pointers. It's not always obvious by looking at the code whether aliasing occurs or not. Should we let the programmer say explicitly that aliasing is not occurring (based on his assumptions), or should we make him tell the compiler what those assumptions are so they can be verified? ========= The opinions expressed above are mine. "A well-written program is its own heaven; a poorly written program its own hell." -- The Tao of Programming
smryan@garth.UUCP (Steven Ryan) (07/03/88)
> My fear is that we'll just keep adding >new storage classes or other keywords as they are needed, making the >language more and more complicated, rather than trying to develop a >more general solution that fits within the current language. My personal favorite is to first come up a computable total predicate that verifies aliassing or whatever. Give the predicate a name the compiler knows about, possibly restricting it to assertions, so that one could write assert(distinct(a,b)) Then the compiler is given a predicate it can recognise and use for optimisation and the programmer is given a construct that can (optionally) verify the stated conditions. If the compiler can prove the predicate, it can delete, otherwise its inclusion is left to the programmer. Subscript checking is sometimes done in this fashion, although the assert mechanism is often hidden.