instruction re-ordering

[loic-dev]

Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

Thanks in advance!
Loic.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

[e-mail] wrote:

Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

[jacob navia]

Harald van Dijk a écrit :

[e-mail] wrote:

>>Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

That could be done only if

call_once(int* restrict done, void(*routine)(void))

If the "restrict" keywords would have been used yes, you could have done it.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

jacob navia wrote:

Harald van Dijk a écrit :

[e-mail] wrote:

>Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

That could be done only if

call_once(int* restrict done, void(*routine)(void))

If the "restrict" keywords would have been used yes, you could have done it.

It can also be done if the compiler chooses to inline a specific call
to call_once.

[David T. Ashley]

"Harald van D?k" <tr*****@gmail.comwrote in message
news:11*********************@38g2000cwa.googlegrou ps.com...

[e-mail] wrote:

>Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

Your observation now has me shaking in my boots!

You are scaring me!

We all know that the "volatile" keyword tells the compiler that it can't
reduce this:

<BEGIN>
volatile int x;
int y, z;

while (y = x) /* Notice this is assignment, not comparision. */
{
z += y;
}
<END>

to this:

<BEGIN>
volatile int x;
int y;
int z;

y = x;

if (y != 0)
{
while (TRUE)
{
z += y;
}
}
<END>

But your comment scares me because "volatile" variables (in microcontroller
work, often hardware control registers) often are linked because groups of
them collectively control [typically] hardware peripherals. These are not
simple assignments or tests, i.e.

CR1 = 0;
CR2 = 0;

may have a very different effect than:

CR2 = 0;
CR1 = 0;

So, in the OP's example, if routine() modifies a hardware control register
and *done is one also, REORDERING THE STATEMENTS WOULD POTENTIALLY HAVE AN
EFFECT, EVEN THOUGH THE COMPILER COULD NOT DETERMINE ANY "INTERACTION"
BETWEEN THE TWO REGISTERS.

I need to look up "volatile" in the standard. This is scaring me.

[Arthur J. O'Dwyer]

On Fri, 12 Jan 2007, David T. Ashley wrote:

"Harald van D?k" <tr*****@gmail.comwrote in message...

>[e-mail] wrote:

>>>
Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

Your observation now has me shaking in my boots!

You are scaring me!

We all know that the "volatile" keyword [...]

Before turning on the sarcasm full force, be sure you proofread
both the original post and your response. There was no 'volatile'
anywhere in the OP. Harald's interpretation is 100% correct.

[...]

So, in the OP's example, if routine() modifies a hardware control register
and *done is one also, REORDERING THE STATEMENTS WOULD POTENTIALLY HAVE AN
EFFECT, EVEN THOUGH THE COMPILER COULD NOT DETERMINE ANY "INTERACTION"
BETWEEN THE TWO REGISTERS.

If *done is a hardware control register, then the user probably
made a mistake in not declaring it 'volatile'. But that's irrelevant;
you don't need to invoke weird 'volatile' objects in order to come
up with a scenario where reordering the statements would be invalid.

HTH,
-Arthur

[David T. Ashley]

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrote in message
news:Pi***********************************@unix32. andrew.cmu.edu...

>
If *done is a hardware control register, then the user probably
made a mistake in not declaring it 'volatile'. But that's irrelevant;
you don't need to invoke weird 'volatile' objects in order to come
up with a scenario where reordering the statements would be invalid.

You genuinely did not understand the technical nuances of my post.

The issue is that even if you declare a data item "volatile", there is the
notion of effectively "co-volatile", where volatile data items are not
independent.

The issue isn't whether one can come up with a scenario where reordering is
invalid ... the issue is whether one can come up with a scenario where
reordering is invalid and the compiler can't detect it.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

David T. Ashley wrote:

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrote in message
news:Pi***********************************@unix32. andrew.cmu.edu...

If *done is a hardware control register, then the user probably
made a mistake in not declaring it 'volatile'. But that's irrelevant;
you don't need to invoke weird 'volatile' objects in order to come
up with a scenario where reordering the statements would be invalid.

You genuinely did not understand the technical nuances of my post.

The issue is that even if you declare a data item "volatile", there is the
notion of effectively "co-volatile", where volatile data items are not
independent.

It's the other way around. Compilers are not allowed to assume volatile
data accesses are independent.

[David T. Ashley]

"Harald van D?k" <tr*****@gmail.comwrote in message
news:11**********************@51g2000cwl.googlegro ups.com...

David T. Ashley wrote:

>"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrote in message
news:Pi***********************************@unix32 .andrew.cmu.edu...

>
If *done is a hardware control register, then the user probably
made a mistake in not declaring it 'volatile'. But that's irrelevant;
you don't need to invoke weird 'volatile' objects in order to come
up with a scenario where reordering the statements would be invalid.

You genuinely did not understand the technical nuances of my post.

The issue is that even if you declare a data item "volatile", there is
the
notion of effectively "co-volatile", where volatile data items are not
independent.

It's the other way around. Compilers are not allowed to assume volatile
data accesses are independent.

OK, fair enough. But is there anything in the standard that says the
compiler can't reorder this:

volatile int x,y;
x = 0;
y = 1;

to

volatile int x,y;
y = 1;
x = 0;

Now, the reasons for reordering could be subtle. For example, "1" may
already be in a CPU register and it is more efficient to do the "1"
assignment before the "0" assignment.

Is this prohibited?

Dave.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

David T. Ashley wrote:

"Harald van D?k" <tr*****@gmail.comwrote in message
news:11**********************@51g2000cwl.googlegro ups.com...

David T. Ashley wrote:

"Arthur J. O'Dwyer" <aj*******@andrew.cmu.eduwrote in message
news:Pi***********************************@unix32. andrew.cmu.edu...

If *done is a hardware control register, then the user probably
made a mistake in not declaring it 'volatile'. But that's irrelevant;
you don't need to invoke weird 'volatile' objects in order to come
up with a scenario where reordering the statements would be invalid.

You genuinely did not understand the technical nuances of my post.

The issue is that even if you declare a data item "volatile", there is
the
notion of effectively "co-volatile", where volatile data items are not
independent.

It's the other way around. Compilers are not allowed to assume volatile
data accesses are independent.

OK, fair enough. But is there anything in the standard that says the
compiler can't reorder this:

volatile int x,y;
x = 0;
y = 1;

to

volatile int x,y;
y = 1;
x = 0;

That's a special case, since the compiler might be able to know that
it's impossible for x and y to be stored in memory where access order
matters. I'll pretend you used "extern volatile int x,y;" instead.
Then, since the compiler can only perform that optimisation if the
accesses are independent, and the accesses can't be proven to be
independent, that optimisation is not valid.

[Keith Thompson]

"David T. Ashley" <dt*@e3ft.comwrites:
[...]

OK, fair enough. But is there anything in the standard that says the
compiler can't reorder this:

volatile int x,y;
x = 0;
y = 1;

to

volatile int x,y;
y = 1;
x = 0;

[...]

Yes. C99 6.7.3p6 says:

An object that has volatile-qualified type may be modified in ways
unknown to the implementation or have other unknown side
effects. Therefore any expression referring to such an object
shall be evaluated strictly according to the rules of the abstract
machine, as described in 5.1.2.3. Furthermore, at every sequence
point the value last stored in the object shall agree with that
prescribed by the abstract machine, except as modified by the
unknown factors mentioned previously.

Modification of a volatile object cannot be moved across a sequence
point.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[David T. Ashley]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"David T. Ashley" <dt*@e3ft.comwrites:
[...]

>OK, fair enough. But is there anything in the standard that says the
compiler can't reorder this:

volatile int x,y;
x = 0;
y = 1;

to

volatile int x,y;
y = 1;
x = 0;

[...]

Yes. C99 6.7.3p6 says:

An object that has volatile-qualified type may be modified in ways
unknown to the implementation or have other unknown side
effects. Therefore any expression referring to such an object
shall be evaluated strictly according to the rules of the abstract
machine, as described in 5.1.2.3. Furthermore, at every sequence
point the value last stored in the object shall agree with that
prescribed by the abstract machine, except as modified by the
unknown factors mentioned previously.

Modification of a volatile object cannot be moved across a sequence
point.

Thanks for the great answer.

I suspected that. OK, I can sleep at night again.

There are contexts with volatile objects where the order above makes a
difference. It makes sense that things can't be shuffled beyond sequence
points.

In my mind at least, the property addressed by the above is different than
my mental notion of volatile.

My mental notion of volatile is "can change separate from the thread being
compiled".

My next mental notion of volatile is "a read or write cycle might have other
effects than it would with memory, i.e. reading it once might be different
than reading it twice".

But the property I'm speaking of is "co-volatility", where volatile objects
are interdependent ... the sequence point restriction seems to address that.

[junky_fellow]

Harald van Dijk wrote:

[e-mail] wrote:

Hello everybody!

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

Does that mean if a break point is set at line L3, it could be possible
that *done = 1 and routine is not called yet ? Debugging such a
program (instruction reordered) would be a pain. Any suggestions on how
to debug such programs ?
Also, do you think this is an incorrect way of coding ? if yes, then
what should be the best way to code such scenarios ?

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

ju**********@yahoo.co.in wrote:

Harald van Dijk wrote:

[e-mail] wrote:

Hello everybody!
>
Assume that I have the following function:
>
void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}
>
Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

It is allowed to do that if and only if it can know that the behaviour
for both sequences is the same. So if it doesn't know whether routine
can access *done, it can't reorder the statements.

Does that mean if a break point is set at line L3, it could be possible
that *done = 1 and routine is not called yet ?

Yes.

Debugging such a
program (instruction reordered) would be a pain. Any suggestions on how
to debug such programs ?

Use a compiler-specific option to disable this reordering. Or, if your
compiler and debugger make this available, look at the (hopefully
annotated) assembly code.

Also, do you think this is an incorrect way of coding ? if yes, then
what should be the best way to code such scenarios ?

Incorrect? Depending on how it's used, I might move the variable and
the check into the routine itself, but it may not always be an option.
Even when it is an option, it's nothing more than that, the code as
given would function just as well.

[Stephen Sprunk]

<ju**********@yahoo.co.inwrote in message
news:11**********************@a75g2000cwd.googlegr oups.com...

Does that mean if a break point is set at line L3, it could be
possible
that *done = 1 and routine is not called yet ? Debugging such a
program (instruction reordered) would be a pain. Any suggestions on
how to debug such programs ?

Virtually anything is possible, provided the resulting program still
obeys the "as if" rule. Optimizing compilers do all sorts of strange
and wonderful things to your code to make it run faster, and for complex
code you'd need to be very familar with assembly coding to be able to
figure out what the heck the output is doing and why. Since this is
what the debugger has to work with, it can be downright confusing trying
to correlate anything at that level with the original source if
optimizations are used.

For this reason, it's best to thoroughly check the program for
correctness, including any necessary trips through the debugger, without
any optimization enabled. Then, when you're reasonably sure the code is
correct, you kick up the compiler's optimization level and verify it's
still behaving correctly. Odds are it will, but now and then you'll
find things that weren't actually correct but weren't exposed in the
unoptimized code for some reason. Very, very rarely you'll find a bug
in the optimizations; I've found exactly one in GCC in over a decade of
coding, and it had already been fixed in a later release than I was
using at the time.

Also, do you think this is an incorrect way of coding ? if yes, then
what should be the best way to code such scenarios ?

This is a pretty simple example, and I doubt any compiler will manage to
improve it much; it'd probably still be recognizable at the highest
optimization levels. Most compilers don't bother trying to optimize
across procedure boundaries, and even those that do will likely be
stymied by calling a function that's passed in as an argument. And,
when they can't prove an optimization is "safe", they have to fall back
to actually emitting code that does what you said to do and how you said
to do it.

As noted elsewhere in the thread, the "volatile" keyword is an explicit
notification to the compiler that many (most?) optimizations aren't
"safe" when the designated variables are involved. At least, that's how
I think of how compilers interpret it; the standard is more precise but
IMHO less clear.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
--
Posted via a free Usenet account from http://www.teranews.com

[loic-dev]

Hello,

Assume that I have the following function:

void
call_once(int* done, void(*routine)(void))
{
if (!(*done)) { /* L1 */
routine(); /* L2 */
*done = 1; /* L3 */
}
}

Is an ANSI C compliant compiler authorized to re-order L2 and L3, i.e.
execute the following sequence instead:
*done = 1;
routine();

Thanks everybody for your interesting replies. Since the restrict
keyword hasn't been used for the prototype, and since the compiler does
not know anything about the routine() function when call_once() is
compiled, it follows that re-ordering cannot occur in this case.

Thanks again and enjoy!
Loic.