You are correct - the "as-if" rule lets the compiler re-order non-volatile accesses as it wants. It is only volatile accesses that must remain strictly in order. However, if the compiler does not know the details of a function, then any function call must be ordered as though it were a volatile access, since the compiler does not know that it does not contain volatile accesses. So in your example, it could not normally move the foo() or bar() calls above or below the volatile sum.
If the definitions of foo() and bar() are known to the compiler (or it knows other details, such as if they are declared with the gcc "const" attribute), so that the compiler knows it is safe, it can move them around.
This part of the paper is wrong. The loop does perform side-effecting operations, both the increments of i and the stores into buffer[i], and these must be done before the (volatile) assignment into buffer_ready.
Whether the consequences of using (volatile) in this way qualify as a mistake depends on other factors, notably the implementation-defined rule for what constitutes an access to a volatile-qualified variable. Perhaps what the paper means to say is that assuming this code will always work is a mistake, and that is in fact correct; but whether it must work is implementation dependent, so on some implementations it could be just fine.
The semantics of volatile are confusing, or at least expressed in a confusing way. What many people think are the rules for how volatiles are accessed and what the Standard says about how volatile-qualified objects must be treated are quite a bit different from each other.
In the examples below, the variables v, v1, v2, ..., are volatile, and other variables aren't. To keep things simple all the arithmetic types are (unsigned int).
First simple example:
x = a + b + c + v;
The first rule for volatile is captured in a single sentence in 6.7.3p6:
Therefore any expression referring to such an object [i.e., with volatile-qualified type] shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3.
The full expression assigning to x is an expression referring to an object with volatile-qualified type. Therefore that expression, the /entire/ expression, must be evaluated strictly according to the rules of the abstract machine. The sums must be formed in the right order; even though addition for (unsigned int) commutes, the additions must be done as (((a + b) + c) + v), and not, for example, as ((a + (b + c)) + v). Furthermore, the sum (a+b) must be performed, even if that value happens to be lying around conveniently in a register somewhere. These consequences follow because of the requirement than any volatile-referring expression be evaluated /strictly/ according to the rules of the abstract machine.
Now let's consider a multi-statement (and so multi-sequence-point) example:
foo(); x = a + b + c + v; bas();
To lend some concreteness, foo() increments a global variable foo_count, and bas increments a global varible bas_count. Neither foo_count nor bas_count is volatile. The functions foo() and bas() don't either read or write x, a, b, c, or v.
Question: can any part of the assignment expression (statement) be done before calling foo() or after calling bas()?
Answer: No.
Reason: The expression in question must be evaluated strictly according to the rules of the abstract machine, as described in
5.1.2.3. In particular, there is 5.1.2.3 p 2.
Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects,(11) which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place.
The assignment expression must be evaluated strictly according to this rule. As it follows a sequence point, all side effects of evalutions before that sequence point (namely, the call to foo()) must be complete. It has a sequence point at its end; all side effects of evaluations after that sequence point (namely, the call to bas()) must not have taken place. The act of calling foo() (or bas()) is itself a side effect, since an object is modified in its function body.
These kinds of consequences may seem counter-intuitive. Certainly they are not what many people expect. But the stated semantics for volatile, coupled with the abstract machine description in 5.1.2.3p2, impose very strict requirements for how much latitude is available for optimizing around expressions that access volatile objects.
Note also: apparently some of the people who are confused about volatile are compiler writers; hence, we have the results shown in
No, this is a misreading of the semantics of volatile as required by the description in 5.1.2.3 of how the abstract machine operates. Please see my last response in this thread.
Sequence points are just a kind of convenient reference point. Sequence points can be identified at the level of source code, and perhaps they "exist" in some sense in the abstract machine, but they don't have any meaning during an actual execution. The key thing is side effects; when starting to evaluate
a += b + c;
all the side effects of previous evaluations must be complete (and not just as-if!), and presumably the call to foo() qualifies because its body has a side effect of its own. The rule about side effects also includes assignment, and for() loops, assuming of course that there is incrementing or something else going on in the for() loop that qualifies as a side effect.
Minor correction: any side effect before a previous sequence point suffices. Presuming the definitions of foo() and bas() have side effects in their bodies, then calls to foo() or bas() also count as side effects.
Yes. On a broad scale it's right, but on the specific explanation for this case it's wrong.
Thank you thank you thank you Tim. So I'm not going senile. Or if I am, I'm not alone.
Looking forward to it. I'll probably have to wait until Sunday though...
Cheers, Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.
That is very interesting - I haven't read through the standards quite like that. Your interpretation may well be the correct one according to the standards (I don't know the priority of these rules and the "as-if" rule), but I think it is slightly different from what users and compiler writers expect, and slightly different from what they *want*. In particular, no one wants or expects the compiler to treat the "a + b + c" part of your expression in any special way just because there is a "+ v" added. They want and expect "v" to be read as a volatile access, but "a + b + c" should be subject to common expression and other optimisations.
As for whether code (in particular, non-volatile loads and stores) should be moveable around the volatile accesses, there are two camps - those who think it should not be possible (if your interpretation is correct, this is the standard's viewpoint), and those who think it is possible (and arguably desirable). The fact is, real compilers *do* move code around like that - if you want your code to run correctly, you have to assume that such re-ordering is possible.
Just for fun, I compiled this code with a couple of versions of gcc and different optimisation flags:
void test1(void) { v1 = a + b; foo(); x = a + b + c + v; bas(); v2 = a + b + c; x += 1; }
With avr-gcc 4.2 and 4.3, -Os optimisation, test1 is implemented as though it were:
void test1(void) { uint8_t r24, r25; // 8-bit registers r24 = b; r25 = a; r24 += r25; // a + b v1 = r24; // volatile store v1 = a + b r25 = c; r25 += r24; // a + b + c r24 = v; // volatile load v v2 = r25; // volatile store v2 = a + b + c r24 += 1; // v + 1 r24 += r25 // v + 1 + a + b + c x = r24; // Store x = a + b + c + v + 1 }
As you can see, calls to foo() and bas() have been eliminated, and there is a lot of re-use of the partial calculations. This is, in my opinion, correct code - the volatile accesses are correct, and in the correct order, and the rest of the code runs *as if* it were a direct translation. The generated code is also as small and fast as it possibly could be on the AVR.
The biggest problem with "volatile" in C is that the standards are vague, difficult to understand, and probably inconsistent. This will always lead to misunderstandings and disagreements about "volatile". comp.lang.c frequenters will often be interested in exactly what the standards say, while comp.arch.embedded frequenters will be more interested in what real-life compilers actually *do* (we are used not not-quite-standard compilers).
Sometime soon I'd like to post a more complete response that doesn't ignore this snipped portion, talking about the semantics of volatile. Right now the response will be just to the paragraph below.
This makes perfect sense, given both the problems of how volatile is described in the Standard, and what the priorities are of the two groups. Folks in comp.arch.embedded aren't going to care very much what compilers are supposed to do, if most compilers don't actually do what they're supposed to do -- and moreso if what they're supposed to do isn't clear.
However, it is in the interests of both groups -- in fact maybe even more in the interests of comp.arch.embedded than it is of comp.lang.c -- that what 'volatile' is supposed to do be well-understood, and that such understanding be shared by a broad community, in particular including lots of compiler people who produce the different implementations, and also including people like those in comp.arch.embedded who actually use 'volatile' in their C code. I'm much more of a comp.lang.c person than a comp.arch.embedded person, but the cross-pollination that's happened in this thread has been (at least IMO) a real boon, and I would like to see that continue during a further discussion of the semantics of volatile.
Also, on a personal note, a "thank you" to David Brown for taking the time to write/compile the example code that uses volatile to see what the compilers actually do with it.
Hoped-for followup discussing the semantics of volatile: as soon as I can get to it, but realistically that won't be before next week.
I'll look forward to that. I too enjoy a bit of cross-posting between these two groups - comp.lang.c is mostly a bit too theoretical for my tastes, but areas such as "volatile" are definitely in an overlap area, and it's good to get input from a different viewpoint.
Tim Rentsch wrote in news: snipped-for-privacy@alumnus.caltech.edu:
I disagree with this analysis. I think you're ascribing too pandemic a meaning to the phrase 'any expression referring to such an object...'.
As you say, the language syntax requires that the interpretation of the expression is "(((a + b) + c) + v)". However, decomposing that further shows that in the outermost expression, 'v' is being added to the result of another expression '((a + b) + c)'. This latter (sub-)expression references no volatile object and hence could be commuted as "(a + (b + c))" or could use an already computed sub-expression like (a + b). Once the '((a + b) + c)' is evaluated, the outermost expression (which *does* reference a volatile object) can then be evaluated 'strictly according to the rules of the abstract machine'.
In your explanation, you reference the term 'full expression'. But the term 'full expression' is explicitly defined in the standard (6.8p4): "A full expression is an expression that is not part of another expression or declarator. [...]" And it seems to have exactly the meaning you are arguing for here. But if 'full expression' was indeed what was intended in 6.7.3p6 as you argue, then wouldn't the well-defined term have been used there?
No-- accesses to global variables are not side effecting operations.
The definition of side effect in the C standard differs from the colloquial computer science definition:
"Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects,11) which are changes in the state of the execution environment."
Here the store into the non-volatile array has been moved below the volatile store by gcc-4.2 for x86. The latest (pre-4.4.0) version of gcc does the same thing, as does the current Intel CC. The current version of llvm-gcc does not, it stores to the flag last. This code example is from Arch Robison's blog.
Perhaps amusingly, when I talk to compiler developers about volatile bugs they are not at all surprised. Of course optimizers, like any other large and complex programs, contain bugs. Embedded developers tend to be more surprised and depressed (my gut reaction as well).
To make things worse we have also found regular old wrong-code errors in every compiler that we've tested, including a number of embedded compilers. This is for integer C programs: no pointers, no FP, not even any structs or unions.
One example: the gcc that shipped with Ubuntu Hardy for x86 miscompiled this function so that it returned 1 instead of 0:
int foo (void) { signed char l_11 =3D 1; unsigned char l_12 =3D -1; return (l_11 > l_12); }
The base version of gcc, 4.2.3, did not mess this up, but the Ubuntu people applied about 5 MB of patches in the released compiler and one of these broke it badly. They have since pushed out an update that fixes this. Did this bug put any security vulnerabilities into Ubuntu? Wish I knew how to answer that :).
Broadly speaking, embedded compilers seem to be worse than, for example, gcc for x86, in the sense that they produce wrong code for broader classes of inputs. It is hard to say what is going on, but I suspect that the cross-product of compiler vendors * target platforms results in a situation where each individual compiler cannot be tested nearly as thoroughly as a typical gcc for x86 release.
Hi! I am one of the authors of the paper in question.
I think that the cited portion of the paper is not wrong.
As described in other posts in this thread, Section 5.1.2.3 paragraph
2 describes a semantics in which "modifying an object" --- any object
--- is a side-effect. Side-effects are complete at sequence points.
But it is important to remember that this is a description of the abstract semantics, and the specification distinguishes between the abstract semantics and the semantics that are allowed by conforming implementations.
Paragraph 5 in the same section describes the minimum requirements for a conforming implementation, which are essentially that only volatile objects must be stable at sequence points. Paragraphs 8 and 9 provide further discussion, which help to clarify that the abstract semantics and the semantics of a conforming implementation may be different.
If I have missed some detail here, please let me know!
Thanks ---
Eric.
PS --- Please direct any email replies to snipped-for-privacy@cs.utah.edu, not the addess from which this message was posted.
There should not be any security vulnerabilities due to such a bug - the C code is clearly incorrect code, even though it is legal C, and security-critical code is often better checked than application-level code. Of course, *should not be* does not mean the same as *are not* ! Real bugs in heavily used features of heavily used compilers are rare, but not unknown - that's one reason you need to test software well (especially if it is critical to security or reliability).
I think that is a perfectly good explanation. Tools that are heavily used are going to have fewer bugs (at least, fewer bugs that are easily triggered) since there are more people using them. They also tend to have more resources in development. This is somewhat countered by the complexity of the software, which is often higher than for smaller tools. Certainly if you look at embedded compilers, the bugs are generally in the target-specific backends rather than the more generic front-ends.
The standard says that "*any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine". v is such an object. ``x = a + b + c + v'' is an "expression referring to such an object". Therefore ``x = a + b + c + v'' must be evaluated strictly according to the rules of the abstract machine. The statement in the standard, if taken literally (and I don't know how else one could reasonably take it) applies to the expressions ``v'', ``a + b + c + v'', and ``x = a + b + c + v''.
It's entirely possible that this wasn't the intent of the authors of the standard. In some cases, where the literal wording of the standard doesn't express the obvious intent, it can be reasonable to use a loose interpretation, but I don't see how to construct such an interpretation in this case, at least not in a way that everyone would agree on.
It doesn't need to be. A full expression is an expression. If the standard refers to "any expression", it must be referring to full expressions as well as to subexpressions.
--
Keith Thompson (The_Other_Keith) kst@mib.org
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
No, it's not. It's questionable, but way short of "clearly incorrect". As far as minimal examples checking for a possible compiler bug go, I find it to be just about perfect.
I don't see why. Note 3.1.2.5 Types: "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type."
So: unsigned char l_12 = -1; is guaranteed to set l_12 to UCHAR_MAX. No question.
--
Richard Heathfield
Email: -http://www. +rjh@
Google users:
"Usenet is a strange place" - dmr 29 July 1999
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.