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]

"Udo A. Steinberg" <st*******@doma in.invalidwrite s:

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]

Udo A. Steinberg wrote:

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[i]`
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.

--
Chris "the rule of invisible sneakiness" Dollin
Meaning precedes definition.

[Udo A. Steinberg]

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

CDUdo 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>
CDYes, 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
CDcan do anything that provides the same result so long as its sneakiness
CDis 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]

Udo A. Steinberg <st*******@doma in.invalidwrote :

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

la************@ ugs.com writes:

Udo A. Steinberg <st*******@doma in.invalidwrote :

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

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.

>
-Larry Jones

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

[Christopher Benson-Manica]

la************@ ugs.com 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.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gma il.com | don't, I need to know. Flames welcome.

[Christopher Benson-Manica]

Richard <rg****@gmail.c omwrote:

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

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gma il.com | don't, I need to know. Flames welcome.

[Eric Sosman]

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

la************@ ugs.com writes:

>>Udo A. Steinberg <st*******@doma in.invalidwrote :

>>>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*
speculative ly 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.

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

--
Er*********@sun .com

[Dik T. Winter]

In article <87************ @mail.comRichar d <rg****@gmail.c omwrites:

la************@ ugs.com writes:

Udo A. Steinberg <st*******@doma in.invalidwrote :

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.

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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/