Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > addresses of variables

Reply
Thread Tools

addresses of variables

 
 
James Kuyper
Guest
Posts: n/a
 
      03-22-2012
On 03/22/2012 12:53 AM, Stephen Sprunk wrote:
> On 21-Mar-12 19:24, James Kuyper wrote:
>> On 03/21/2012 06:58 PM, Stephen Sprunk wrote:
>>> On 20-Mar-12 17:37, James Kuyper wrote:

>> ...
>>>> implementation would produce such an optimization. But the key point is
>>>> that taking the address is not the right trigger - it's what happens to
>>>> that address that matters. If nothing "meaningful" happens to it, the
>>>> address doesn't have to mean anything real, and actual storage of the
>>>> value at the addressed location doesn't have to happen.
>>>
>>> If nothing "meaningful" was done with the address, then presumably other
>>> optimizations would eliminate the code that generated it, thus allowing
>>> the compiler to migrate or eliminate the variable.

>>
>> I don't follow that - why would a situation that renders it unnecessary
>> to store a variable in addressable memory imply that it's unnecessary to
>> store it anywhere?

>
> 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.
--
James Kuyper
 
Reply With Quote
 
 
 
 
Jens Gustedt
Guest
Posts: n/a
 
      03-23-2012
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
 
Reply With Quote
 
 
 
 
James Kuyper
Guest
Posts: n/a
 
      03-23-2012
On 03/23/2012 08:41 AM, Jens Gustedt wrote:
> 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.


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.

>> 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.)


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.
--
James Kuyper
 
Reply With Quote
 
Jens Gustedt
Guest
Posts: n/a
 
      03-23-2012
Am 03/23/2012 02:06 PM, schrieb James Kuyper:
>> 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.


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

 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      03-23-2012
On 03/23/2012 02:47 PM, Jens Gustedt wrote:
> Am 03/23/2012 02:06 PM, schrieb James Kuyper:
>>> 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.

>
> 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.
 
Reply With Quote
 
Jens Gustedt
Guest
Posts: n/a
 
      03-23-2012
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

 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      03-24-2012
On 03/23/2012 07:19 PM, Jens Gustedt wrote:
> 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.


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.

>> - 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. ...


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.

.....
>> 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.


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.
--
James Kuyper
 
Reply With Quote
 
Jens Gustedt
Guest
Posts: n/a
 
      03-24-2012
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
 
Reply With Quote
 
Stephen Sprunk
Guest
Posts: n/a
 
      03-24-2012
On 22-Mar-12 11:01, Kenneth Brody wrote:
> On 3/22/2012 6:22 AM, James Kuyper wrote:
>> On 03/22/2012 12:53 AM, Stephen Sprunk wrote:
>>> 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.

>
> 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.

>>> 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

>
> 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

--
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
Put variables into member variables or function variables? tjumail@gmail.com C++ 9 03-23-2008 04:03 PM
How to implement a firewall for Windows platform that blocks based on Mac addresses instead of IP addresses cagdas.gerede@gmail.com C Programming 1 12-07-2006 04:30 AM
Physical Addresses VS. Logical Addresses namespace1 C++ 3 11-29-2006 03:07 PM
assigning array addresses to integer variables and vice versa anonymous C Programming 28 11-29-2005 12:23 PM



Advertisments