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]

Re: Ternary operator and memory access

"Udo A. Steinberg" <steinberg@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]

Re: Ternary operator and memory access

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]

Re: Ternary operator and memory access

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

Re: Ternary operator and memory access

Udo A. Steinberg <steinberg@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]

Re: Ternary operator and memory access

lawrence.jones@ ugs.com writes:

Udo A. Steinberg <steinberg@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]

Re: Ternary operator and memory access

lawrence.jones@ 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]

Re: Ternary operator and memory access

Richard <rgrdev@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]

Re: Ternary operator and memory access



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

lawrence.jones@ ugs.com writes:
>
>

>>Udo A. Steinberg <steinberg@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

--
Eric.Sosman@sun .com

[Richard]

Re: Ternary operator and memory access

Eric Sosman <Eric.Sosman@su n.comwrites:

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

>lawrence.jones@ ugs.com writes:
>>
>>

>>>Udo A. Steinberg <steinberg@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*
>>>speculativel y 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 ? (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]

Re: Ternary operator and memory access

Christopher Benson-Manica <ataru@ukato.fr eeshell.orgwrit es:

Richard <rgrdev@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).

Thanks : I'll have a look.

[Dik T. Winter]

Re: Ternary operator and memory access

In article <87bqqwipya.fsf @mail.comRichar d <rgrdev@gmail.c omwrites:

lawrence.jones@ ugs.com writes:

Udo A. Steinberg <steinberg@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, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Eric Sosman]

Re: Ternary operator and memory access



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

Eric Sosman <Eric.Sosman@su n.comwrites:
>
>

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

>>>lawrence.jon es@ugs.com writes:
>>>
>>>
>>>
>>>>Udo A. Steinberg <steinberg@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
>>>>evaluatin g.
>>>
>>>
>>>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 ? (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).

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.

--
Eric.Sosman@sun .com

[Richard]

Re: Ternary operator and memory access

Eric Sosman <Eric.Sosman@su n.comwrites:

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

>Eric Sosman <Eric.Sosman@su n.comwrites:
>>
>>

>>>Richard wrote On 08/07/06 10:24,:
>>>
>>>>lawrence.jo nes@ugs.com writes:
>>>>
>>>>
>>>>
>>>>>Udo A. Steinberg <steinberg@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*
>>>>>speculativ ely 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 ? (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).

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

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

[Eric Sosman]

Re: Ternary operator and memory access



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

Eric Sosman <Eric.Sosman@su n.comwrites:

>[...]
>>
> 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 "unnecessar y" 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.

--
Eric.Sosman@sun .com