Ternary operator and memory access

[Udo A. Steinberg]

Hi all,

In a ternary statement such as: x = (cond ? a : b); it is obviously guaranteed
that "x" will be equal to "a" only if the condition "cond" holds. Assuming that
"a" is a memory location, is it also guaranteed that "a" will not be accessed
in memory if the condition does not hold?

Or, in other words, is a compiler allowed to speculatively fetch a and b from
memory and then assign one of them to x based on the condition?

- Udo

 

[Richard]

Hi all,

In a ternary statement such as: x = (cond ? a : b); it is obviously guaranteed
that "x" will be equal to "a" only if the condition "cond" holds. Assuming that
"a" is a memory location, is it also guaranteed that "a" will not be accessed
in memory if the condition does not hold?

Or, in other words, is a compiler allowed to speculatively fetch a and b from
memory and then assign one of them to x based on the condition?

- Udo

Is it handled any different from

if(cond)
x=a;
else
x=b;

I hope not : because if it was there would be hell to pay if "a" became
"a()", or "b" became "b()" - or if "a" or "b" were special memory locations
hardwired to slow response HW.

 

[Chris Dollin]

In a ternary statement such as: x = (cond ? a : b);

(It's not a "ternary statement". It's an assignment expression where the
source operand is a ternary equiv. conditional expression.)

it is obviously guaranteed
that "x" will be equal to "a" only if the condition "cond" holds.

Not actually true: `a` and `b` may be equal.

Assuming that "a" is a memory location, is it also guaranteed
that "a" will not be accessed in memory if the condition does not hold?

`a` will be evaluated only if the condition compares unequal to 0.

But ...

Or, in other words, is a compiler allowed to speculatively fetch a and b from
memory and then assign one of them to x based on the condition?

Yes, if you can't tell the difference [with conforming C code]; this is the
"as if" rule. The standard specifies the semantics, and the implementation
can do anything that provides the same result so long as its sneakiness
is invisible.

So if `a` is a local or global variable [1], it can prefetch `a` - you
can't tell that it has. But if `a` is eg `pointer->aField` or `array`
it can't -- because the pointer might be null, or the index out of
bounds -- unless it can /also/ prove that the pointer is valid, or
the index in range (or that wild fetches are harmless, which they might
be in some implementations).

[1] Unless it's volatile.

 

[Udo A. Steinberg]

On Mon, 07 Aug 2006 14:43:47 +0100 Chris Dollin (CD) wrote:

CD> Udo A. Steinberg wrote:
CD>
CD> > Or, in other words, is a compiler allowed to speculatively fetch a and b
CD> > from memory and then assign one of them to x based on the condition?
CD>
CD> Yes, if you can't tell the difference [with conforming C code]; this is the
CD> "as if" rule. The standard specifies the semantics, and the implementation
CD> can do anything that provides the same result so long as its sneakiness
CD> is invisible.

How well defined is "invisible sneakiness"? In my case "a" is only mapped in
virtual memory if the condition is true. Otherwise access to "a" causes a page
fault. Here the compiler sneakiness becomes visible to the user. However, if
the compiler can always assume that all memory is mapped, then the sneakiness
is indeed invisible.

- Udo

 

[lawrence.jones]

In a ternary statement such as: x = (cond ? a : b); it is obviously guaranteed
that "x" will be equal to "a" only if the condition "cond" holds. Assuming that
"a" is a memory location, is it also guaranteed that "a" will not be accessed
in memory if the condition does not hold?

Yes. The ?: operator is defined to only evaluate one of a and b, it is
not permitted to evaluate both. On the other hand, compilers are free
to do whatever they want, as long as a strictly conforming program can't
tell any difference. So a particular implementation *could*
speculatively evaluate both a and b as long as it ensures that nothing
bad (like a trap) happens when evaluating something it shouldn't be
evaluating.

-Larry Jones

It must be sad being a species with so little imagination. -- Calvin

 

[Richard]

Yes. The ?: operator is defined to only evaluate one of a and b, it is
not permitted to evaluate both. On the other hand, compilers are free
to do whatever they want, as long as a strictly conforming program can't
tell any difference. So a particular implementation *could*
speculatively evaluate both a and b as long as it ensures that nothing
bad (like a trap) happens when evaluating something it shouldn't be
evaluating.

And how would a compiler determine that at compile time? It cant as far
as I can see in the case of variable memory references. So it shouldnt
access the non matching expression.

 

[Christopher Benson-Manica]

(e-mail address removed) wrote:

(WRT the conditional operator)

tell any difference. So a particular implementation *could*
speculatively evaluate both a and b as long as it ensures that nothing
bad (like a trap) happens when evaluating something it shouldn't be
evaluating.

Not only must nothing bad happen, the program must not be able to
determine that the prohibited evaluation occurred.

 

[Christopher Benson-Manica]

Is it handled any different from

if(cond)
x=a;
else
x=b;

It is different, but in rather subtle ways. 6.5.15 of n869 places a
number of conditions on what a and b may be, as well as the type of
the result of (cond?a:b).

 

[Eric Sosman]

Richard wrote On 08/07/06 10:24,:

And how would a compiler determine that at compile time? It cant as far
as I can see in the case of variable memory references. So it shouldnt
access the non matching expression.

int a = f();
int b = g();
int x = cond ? a : b;

"Hmmm. As the compiler, I happen to know that register
R0 still contains the value returned by g(), the thing I just
stored into b a moment ago. So if cond turns out to be false,
I don't need to fetch anything from memory; I've already got
exactly what's needed right here in R0. Hey, look: I've just
``evaluated'' b before testing cond, and in perfect safety!"

Generated code:

call f
store r0,a
call g
store r0,b
load r1,cond
jzero r1,label
load r0,a
label:
store r0,x

 

[Dik T. Winter]

>
> And how would a compiler determine that at compile time? It cant as far
> as I can see in the case of variable memory references. So it shouldnt
> access the non matching expression.

The 'a' in the code above is a variable, and so, as far as the compiler
is concerned, has been assigned an address in memory. If it has not
been assigned an address, the implementation appears to be very strange.

 

[Richard]

Richard wrote On 08/07/06 10:24,:

int a = f();
int b = g();
int x = cond ? (1) a : b (2);

"Hmmm. As the compiler, I happen to know that register
R0 still contains the value returned by g(), the thing I just
stored into b a moment ago. So if cond turns out to be false,
I don't need to fetch anything from memory; I've already got
exactly what's needed right here in R0. Hey, look: I've just
``evaluated'' b before testing cond, and in perfect safety!"

Generated code:

call f
store r0,a
call g
store r0,b
load r1,cond
jzero r1,label
load r0,a
label:
store r0,x

Possibly we are talking of different things. I am referring to it
accessing expression (2) when the condition is supposed to be triggering
(1). Possibly I overs implified it : there is no issue with HW if the
"result" of b=g() is used from a register. But clearly if expressions
(1) and (2) are of the form "*a" or "*b" then it would be madness for
the compiler to access *b if the condition is true. Or?

 

[Richard]

It is different, but in rather subtle ways. 6.5.15 of n869 places a
number of conditions on what a and b may be, as well as the type of
the result of (cond?a:b).

Thanks : I'll have a look.

 

[Eric Sosman]

Richard wrote On 08/07/06 11:05,:

Possibly we are talking of different things. I am referring to it
accessing expression (2) when the condition is supposed to be triggering
(1).

Same code, different execution path. The compiler
has "evaluated" b before testing cond, even if the test
says that a's value is chosen instead.

Possibly I overs implified it : there is no issue with HW if the
"result" of b=g() is used from a register. But clearly if expressions
(1) and (2) are of the form "*a" or "*b" then it would be madness for
the compiler to access *b if the condition is true. Or?

The compiler might not know whether *a,*b are or aren't
safe, but it might be able to tell that it makes no difference.

int *a = ...;
int *b = ...;
*a = 42; /* die here if *a unsafe */
*b = 56; /* die here if *b unsafe */
x = cond ? *a : *b;

The compiler might conclude that if *a,*b are unsafe the final
line won't be executed anyhow, hence a speculative fetch adds
no new failure mode to the program.

I don't know how commonly compilers "reason" this way, but
I've certainly seen compilers generate speculative fetches and
pre-fetches, sometimes far in advance of the use of the datum.
On modern machines there's a lot of incentive to do so, what
with memory being so much slower than CPUs.

 

[Richard]

Richard wrote On 08/07/06 11:05,:

Same code, different execution path. The compiler
has "evaluated" b before testing cond, even if the test
says that a's value is chosen instead.


The compiler might not know whether *a,*b are or aren't
safe, but it might be able to tell that it makes no difference.

int *a = ...;
int *b = ...;
*a = 42; /* die here if *a unsafe */
*b = 56; /* die here if *b unsafe */
x = cond ? *a : *b;

The compiler might conclude that if *a,*b are unsafe the final
line won't be executed anyhow, hence a speculative fetch adds
no new failure mode to the program.

I don't know how commonly compilers "reason" this way, but
I've certainly seen compilers generate speculative fetches and
pre-fetches, sometimes far in advance of the use of the datum.
On modern machines there's a lot of incentive to do so, what
with memory being so much slower than CPUs.

true : and I guess the old "volatile" can protect any "dodgy" memory locations?

 

[Eric Sosman]

Richard wrote On 08/07/06 12:11,:

[...]

I don't know how commonly compilers "reason" this way, but
I've certainly seen compilers generate speculative fetches and
pre-fetches, sometimes far in advance of the use of the datum.
On modern machines there's a lot of incentive to do so, what
with memory being so much slower than CPUs.

true : and I guess the old "volatile" can protect any "dodgy" memory locations?

That's the intent. `volatile' says (roughly) that the
access to the variable has side-effects. This prevents the
compiler from eliminating "unnecessary" accesses; even if
the value is known, the side-effect of the access itself
may be required. Also, the access cannot be moved outside
its bracketing sequence points: containment of side-effects
is what sequence points are all about.

Unfortunately, there's a huge loophole: The implementation
gets to define what an "access" is, and the definition may or
may not match the programmer's intent. Most effective uses of
`volatile' thus require some intimacy with the implementation's
documentation suite.

 

[Ancient_Hacker]

Eric Sosman wrote:

Unfortunately, there's a huge loophole: The implementation
gets to define what an "access" is, and the definition may or
may not match the programmer's intent. Most effective uses of
`volatile' thus require some intimacy with the implementation's
documentation suite.

Yes, there can be very very touchy variables, where something that
seems innocuous, like just evaluating their address can cause
side-effects. For example on machines with many segment registers,
just loading up an address into an address register can cause "seg
fault"-like traps. Best example, the x86 in 16-bit protected mode.
Peeking at any segment value that hasnt been explicitly allocated to
your program will trap out. You're typically handed just 4 out of 8192
possible segments, so the odds arent good if the goods are odd.

So compilers, when in that code-generating mode, have to be very
conservative. No loading up of arbitrary addresses, no stuffing extra
info into the top bits of pointers.

 

[Skarmander]

On Mon, 07 Aug 2006 14:43:47 +0100 Chris Dollin (CD) wrote:

CD> Udo A. Steinberg wrote:
CD>
CD> > Or, in other words, is a compiler allowed to speculatively fetch a and b
CD> > from memory and then assign one of them to x based on the condition?
CD>
CD> Yes, if you can't tell the difference [with conforming C code]; this is the
CD> "as if" rule. The standard specifies the semantics, and the implementation
CD> can do anything that provides the same result so long as its sneakiness
CD> is invisible.

How well defined is "invisible sneakiness"?

Almost exactly, since it's fully defined by the language specification. Any
two pieces of behavior that have equal semantics according to the standard
are interchangeable, even if they are observably different. The key is that
"observation" happens on the concrete machine, while the standard only
defines semantics in terms of an abstract machine.

In my case "a" is only mapped in virtual memory if the condition is true.
Otherwise access to "a" causes a page fault. Here the compiler sneakiness
becomes visible to the user. However, if the compiler can always assume
that all memory is mapped, then the sneakiness is indeed invisible.

The compiler is allowed to do this, according to the standard, even if the
page fault involved releasing a carrier pigeon that flies to Mount
Kilimanjaro to retrieve the information you requested -- the standard does
not say how memory retrieval is implemented, in particular not what its
performance characteristics are. Of course, implementations are expected to
be "reasonable" to give the poor programmer a fighting chance.

The sort of guarantees you're looking for require intimate knowledge of the
platform(s) you're compiling on (which includes the compiler). Aside from
"volatile", you have little to no way to reliably influence the compiler's
behavior with regards to memory access, and even "volatile" has its fuzzy areas.

You can try to make prefetching the values as difficult or unattractive as
possible, you can try disabling optimization for this particular piece of
code, you can try compiler-specific extensions, or you could write the parts
you don't want the compiler to ever optimize in assembler. All of these
approaches require an amount of nonportable code, but since you're
specifically dealing with virtual memory that you have some sort of
interface to, this shouldn't be a big problem. Just make sure you document
clearly what you're trying to achieve in each instance, so your code won't
mysteriously break when the platform changes and human beings won't undo
your carefully crafted compiler conning.

S.

 

[Richard]

You can try to make prefetching the values as difficult or
unattractive as possible, you can try disabling optimization for this
particular piece of code, you can try compiler-specific extensions, or
you could write the parts you don't want the compiler to ever optimize
in assembler. All of these approaches require an amount of nonportable
code, but since you're specifically dealing with virtual memory that
you have some sort of interface to, this shouldn't be a big
problem. Just make sure you document clearly what you're trying to
achieve in each instance, so your code won't mysteriously break when
the platform changes and human beings won't undo your carefully
crafted compiler conning.

S.

Surely its as simple as just replacing variables with function calls to
retrieve them? get() calls if you will.

There is no way the compiler will generate a call to the function
outside of the condition being matched.

Or? ...

 

[Skarmander]

Surely its as simple as just replacing variables with function calls to
retrieve them? get() calls if you will.

There is no way the compiler will generate a call to the function
outside of the condition being matched.

Provided that the compiler does not (partially) inline the functions and the
functions produce an observable side effect, and assuming of course that
we're not running on a DS9K.

Tricking a compiler can be arbitrarily complicated, depending on how smart
the compiler is. There is no language construct that will guarantee that no
virtual memory access will be generated to an object; a compiler would in
principle be free to do this "whenever it felt like it", provided it could
guarantee this would not cause the program to abort or invoke other
nonconforming behavior. If the only penalty is speed, though, there are no
standards-imposed limits to what the compiler can or can't do, just
considerations of reasonability and (conservative) practicality.

S.

 

[Chris Torek]

Richard wrote On 08/07/06 11:05,:
Or, more specifically, suppose we have:

int f(int x, int *ap, int *bp) {
return x ? *ap : *bp;
}

(which is of course just the conditional operator itself, written in
function form, with type restricted to "int" and pointers for the
values involved).

The compiler might not know whether *a,*b are or aren't
safe, but it might be able to tell that it makes no difference.

int *a = ...;
int *b = ...;
*a = 42; /* die here if *a unsafe */
*b = 56; /* die here if *b unsafe */
x = cond ? *a : *b;

The compiler might conclude that if *a,*b are unsafe the final
line won't be executed anyhow, hence a speculative fetch adds
no new failure mode to the program.

Or, the machine may have a "load from memory, but if there is a
fault during loading, ignore it" instruction -- often actually
spelled "prefetch" and having no target register -- in which case,
it can generate:

f_: .global f_
# inputs: r1 = x, r2 = ap, r3 = bp
pref (r2) # prefetch from *ap
pref (r3) # prefetch from *bp
tst r1 # which one should we use?
bz L1
ld r0,(r2) # x != 0, so fetch from *ap
ret
L1:
ld r0,(r3) # fetch from *bp
ret

The two "extra" instructions start RAM -> cache transfers, which
typically take dozens of CPU cycles, if needed. Meanwhile the CPU
can still execute instructions. This means that the during the
delay caused by testing r1 (i.e., x), something useful is still
going on.

(These "prefetch" instructions would be more useful if they were
placed further back in the instruction stream, which is of course
only possible if the routine f() is expanded in line.)