addresses of variables

[James Kuyper]

Concrete example:

int quux(void)
{
int foo = 42;
int *bar = &foo;
return foo;
}

1. Both foo and bar start out in memory.
2. foo can't be migrated to a register because of the &foo.
3. bar is eliminated via dead code elimination.
4. foo can now be migrated to a register.
5. No address is needed for either foo or bar.

A prime example of a situation where neither foo, nor bar, nor the
address of foo, are needed.

OTOH, say you have this:

#include <stdio.h>
int quux(void)
{
int foo = 42;
int *bar = &foo;
printf("%p\n", (void*)bar);
return foo;
}

1. Both foo and bar start out in memory.
2. foo can't be migrated to a register because of the &foo.
3. bar is migrated to a register.
4. An address is needed for foo but not for bar.

Can you give a similar example for what you're describing--and your
mental model of what a compiler would do with it?

Yes, the second case you've just given fits what I'm talking about
exactly. Having recognized that there's absolutely no need to store 42
anywhere, the compiler reserves an arbitrary address for foo, but never
bothers storing anything at that address. That address is stored in a
register and passed to printf(), and is used for no other purpose. The
compiler need only ensure that the address is not used for any other
object that might have a lifetime that overlaps the call to quux(),
which is something it would have had to do anyway, if 42 had been stored
there.

If foo had static storage duration, there would be the possibility that
some other part of the code could ask the user to give foo's address
back to it, and then dereference a pointer to foo, which would make this
no longer a valid optimization. Because foo actually has automatic
storage duration, there's no possible way to write code which is
guaranteed to use that address during foo's lifetime, not even with
multi-threaded code.

Note: I'm winging it on that last statement. I've not had time to
assimilate C's new support for multi-threaded code. If there's some way
to guarantee that a scanf() call followed by a dereference in some other
part of the program will be executed between the printf() and the return
in quux(), then I'm wrong. But I'd expect that the ability to guarantee
such sequencing would require executing a call to one of the new
thread-related functions between the printf() and the return. Code where
such sequencing is merely possible, but not guaranteed, has undefined
behavior if it doesn't execute in that sequence, thereby allowing the
optimization.

 

[Jens Gustedt]

Hello,

Am 03/22/2012 11:22 AM, schrieb James Kuyper:

Note: I'm winging it on that last statement. I've not had time to
assimilate C's new support for multi-threaded code. If there's some way
to guarantee that a scanf() call followed by a dereference in some other
part of the program will be executed between the printf() and the return
in quux(), then I'm wrong.

has nothing to do with threads. printf is a library function, yes, but
there is no guarantee, I think that it has no right to at least
inspect the contents that the argument is pointing to.

But I'd expect that the ability to guarantee
such sequencing would require executing a call to one of the new
thread-related functions between the printf() and the return. Code where
such sequencing is merely possible, but not guaranteed, has undefined
behavior if it doesn't execute in that sequence, thereby allowing the
optimization.

No. The other thread could know by some other magic when doing this
if the thread here still is alive and thus the pointer is still
valid. (E.g all threads might be serialized and the other thread can
inspect a table of all running threads.)

As a side note, in C11 it is implementation specific if a thread has
the right to poke into memory that resides on the stack of another
thread.

Jens

 

[James Kuyper]

Hello,

Am 03/22/2012 11:22 AM, schrieb James Kuyper:

has nothing to do with threads. printf is a library function, yes, but
there is no guarantee, I think that it has no right to at least
inspect the contents that the argument is pointing to.

How does "no guarantee" and "no right" fit together - or is the
guarantee you're referring something other than "printf()" is guaranteed
to not dereference the pointer? I've routinely passed null pointers to
printf("%p") - if there's no such guarantee, that's undefined behavior.

No. The other thread could know by some other magic when doing this
if the thread here still is alive and thus the pointer is still
valid. (E.g all threads might be serialized and the other thread can
inspect a table of all running threads.)

That's outside the scope of the C standard (unless there's some features
of the new threading library that I'm unfamiliar with - which is quite
possible). Therefore whether or not a given implementation can do the
optimization I'm talking about depends in part upon whether it provides
such mechanisms to make it invalid.

 

[Jens Gustedt]

Am 03/23/2012 02:06 PM, schrieb James Kuyper:

That's outside the scope of the C standard (unless there's some features
of the new threading library that I'm unfamiliar with - which is quite
possible). Therefore whether or not a given implementation can do the
optimization I'm talking about depends in part upon whether it provides
such mechanisms to make it invalid.

No it isn't outside the scope of the standard. Undefined behavior only
occurs when some thread effectively accesses a pointer who's object's
lifetime has ended. The only potential that such undefined behavior
might occur (or not) is not by itself undefined behavior. Whenever a
thread could access such a pointer legally the "as if" rule applies, so
the pointer must be a real thing pointing to the real data. What the
thread might use to determine that this is legal is out of the scope of
the standard.

BTW, again you don't need threads for such a discussion. Even without
threads you can have execution of other parts of the program outside the
usual control flow, e.g through a signal handler.

Jens

 

[James Kuyper]

Am 03/23/2012 02:06 PM, schrieb James Kuyper:

No it isn't outside the scope of the standard. Undefined behavior only
occurs when some thread effectively accesses a pointer who's object's
lifetime has ended.

Correct. Therefore, an implementation which provides, as a non-standard
extension, the ability to guarantee that such code will execute during
the object's lifetime, cannot use undefined behavior as an excuse to
perform the optimization I'm talking about. However, a fully conforming
implementation that provides no such mechanism CAN perform such an
optimization. To provide such a guarantee in a portable fashion would
require a re-write to the example code; it can't exist with the code as
written.

BTW, again you don't need threads for such a discussion. Even without
threads you can have execution of other parts of the program outside the
usual control flow, e.g through a signal handler.

Sure - for instance, a fully portable way to do this by modifying the
function would be to create a volatile sig_atomic_type object visible
from both this function and the signal handler, initialized to 0, set to
1 after the call to printf(), and set back to 0 before the execution of
the return statement, and modified by no other part of the program. If
the function itself is never called by a signal handler, and if the
signal handler sees that the value of that object is 1, then it can
guarantee that it's executing it's own code during the lifetime of the
object pointed at by that pointer, and can therefore safely dereference
that pointer.
Under those circumstances, the implementation would be prohibited from
performing the kind of optimization I'm talking about.

At least, that would be the case if the restrictions on what you can do
with standard-defined behavior inside a signal handler weren't so severe
(I've not had time to see if they've relaxed those restriction in C2011
- but in C99 every method I can think of for getting the address that
was printed out by printf() into the signal handler's scope would have
had undefined behavior - for one thing, it would require fflush(stdout),
and then some interaction with the user through stdin, both of which
would violate the prohibition on calling standard library functions
(7.1.4p4 and footnote 188 of n1570.pdf).

The key point is that execution of the signal handler code during the
pointed-at object's lifetime must be guaranteed, not merely a
possibility. In the absence of something that forces the access through
the pointer to be sequenced between the start and the end of the
pointed-at object's lifetime, an implementation is free to optimize the
object's lifetime down to 0 seconds, giving such code exactly 0% chance
of executing during the non-existing time interval in which
dereferencing the address would have defined behavior.

 

[Jens Gustedt]

Am 03/23/2012 09:04 PM, schrieb James Kuyper:

At least, that would be the case if the restrictions on what you can do
with standard-defined behavior inside a signal handler weren't so severe
(I've not had time to see if they've relaxed those restriction in C2011

C11 adds all _Atomic qualified objects that are lock-free to the list
of objects that are allowed to be accessed.

- but in C99 every method I can think of for getting the address that
was printed out by printf() into the signal handler's scope would have
had undefined behavior - for one thing, it would require fflush(stdout),
and then some interaction with the user through stdin, both of which
would violate the prohibition on calling standard library functions
(7.1.4p4 and footnote 188 of n1570.pdf).

The feedback of the information (of the pointer value) must not
necessarily be through a read from a FILE*. Input can come through a
volatile qualified variable. For C99 this would have to be of type
sig_atomic_t, or if that is not wide enough you would have to stitch
together several of them to reconstruct the pointer value. For C99 a
volatile and _Atomic qualified pointer type could suffice (if it is
lockfree).

The key point is that execution of the signal handler code during the
pointed-at object's lifetime must be guaranteed, not merely a
possibility.

printf is doing IO. On modern OS signal handlers kick into its
execution all the time.

key point is that for the optimization to be valid you'd have to prove
that the use of the pointer value is impossible under all
circumstances.

Jens

 

[James Kuyper]

Am 03/23/2012 09:04 PM, schrieb James Kuyper:


C11 adds all _Atomic qualified objects that are lock-free to the list
of objects that are allowed to be accessed.

I expected as much - I look forward to the day when I can afford to sit
down and study C2011 carefully enough to fully understand the meaning of
that statement. Unfortunately, that day's no likely to come any time soon.

The feedback of the information (of the pointer value) must not
necessarily be through a read from a FILE*. Input can come through a
volatile qualified variable. ...

How? After the printf(), the only place that the address has been
communicated to is stdout. How do you get the address back inside the
program without engaging in I/O of some kind? Even if you're writing to
a pipe, the other end of which is connected to the same program, it's
still I/O.

.....

printf is doing IO. On modern OS signal handlers kick into its
execution all the time.

The information about the pointer's address has not been completely
communicated to stdout until after printf() has done just about
everything it needs to do.

key point is that for the optimization to be valid you'd have to prove
that the use of the pointer value is impossible under all
circumstances.

More accurately, you need to prove that it impossible for the pointer
value to be retrieved by code with standard-defined behavior. Since that
behavior is defined only if the the relevant code MUST be sequenced
between the start and the end of the object's life time, the burden of
proof is on the code that supposedly achieves that result; it's not very
difficult, in many cases, such as this one, to show that there can be no
such code. At least, it's not difficult on implementations that don't
provide special additional hooks for guaranteeing that sequence.

 

[Jens Gustedt]

Am 03/24/2012 03:20 AM, schrieb James Kuyper:

How? After the printf(), the only place that the address has been
communicated to is stdout. How do you get the address back inside the
program without engaging in I/O of some kind? Even if you're writing to
a pipe, the other end of which is connected to the same program, it's
still I/O.

A device, volatile variables were invented for that. IO is not only
done through the stdio interfaces but any variable that is declared
volatile can have values that are not predictable. An atomic
variable that is attached to an input device can play back any value
that you want to the program. And as I said this works already for C99
at least, though sig_atomic_t is not too comfortable to program with.

Jens

 

[Stephen Sprunk]

In fact, foo itself becomes unnecessary. My compiler optimizes this to
the equivalent of "return 42;".

True in theory, but every implementation I'm familiar with passes the
return value in a register, so the output is the same whether the
compiler eliminates foo or not.

Note that this is only due to the "special knowledge" that the compiler
may have for the printf() function. Had the line been this:

plugh("%p\n", (void *)bar);

instead, then the assumption that the address will never be dereferenced
would be invalid, and the 42 must be stored there.

Exactly my point.

Note, however, that even with the plugh() call, my compiler has still
eliminated bar entirely, and simply passes &foo directly. (In both
cases, however, my compiler stores the 42.)

Good point; I was thinking of systems where arguments are passed in
registers or must be in a register to be pushed onto the stack. If
neither of those applies, bar can be eliminated.

S