View mode: basic / threaded / horizontal-split · Log in · Help
September 25, 2012
Order of evaluation - aka hidden undefined behaviours.
Pop quiz!

Analyse this code:
----
string abc;

float[] A()
{
    abc ~= "A";
    return [];
}

float[] B()
{
    abc ~= "B";
    return [];
}

float[] C()
{
    abc ~= "C";
    return [];
}

void main()
{
    A()[] = B()[] + C()[];
    assert(abc == "???");
}
----

Without cheating, I invite people to have a good guess what 'abc' 
is equal to, but just to narrow it down.

1)  It isn't "ABC".
2)  On x86/x86_64, it isn't "ACB".
3)  On everything else, it's the reverse of what you'd expect on 
x86/x86_64.

The problem here is that the array operation A[] = B[] + C[] gets 
transformed into an extern(C) call.  And because there's no 
strict rules in place over the order of which it's parameters are 
evaluated, it could go either way (LTR, or RTL).

Serious note: This test is bogus as this and similar other 
failing tests on non-x86 platforms are not at all obvious to the 
users who get issues. So what are we to do about it?


Regards,
Iain.
September 25, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 9/25/12 6:58 PM, Iain Buclaw wrote:
[snip]
> Serious note: This test is bogus as this and similar other failing tests
> on non-x86 platforms are not at all obvious to the users who get issues.
> So what are we to do about it?

The right answer is to have the front-end rewrite such expressions in a 
form that enforces correct order of operations.

Andrei
September 25, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 09/26/2012 12:58 AM, Iain Buclaw wrote:
> Pop quiz!
>
> Analyse this code:
> ----
> string abc;
>
> float[] A()
> {
>      abc ~= "A";
>      return [];
> }
>
> float[] B()
> {
>      abc ~= "B";
>      return [];
> }
>
> float[] C()
> {
>      abc ~= "C";
>      return [];
> }
>
> void main()
> {
>      A()[] = B()[] + C()[];
>      assert(abc == "???");
> }
> ----
>
> Without cheating, I invite people to have a good guess what 'abc' is
> equal to, but just to narrow it down.
>
> 1)  It isn't "ABC".
> 2)  On x86/x86_64, it isn't "ACB".
> 3)  On everything else, it's the reverse of what you'd expect on
> x86/x86_64.
>
> The problem here is that the array operation A[] = B[] + C[] gets
> transformed into an extern(C) call.  And because there's no strict rules
> in place over the order of which it's parameters are evaluated, it could
> go either way (LTR, or RTL).
>
> Serious note: This test is bogus as this and similar other failing tests
> on non-x86 platforms are not at all obvious to the users who get issues.
> So what are we to do about it?
>
>
> Regards,
> Iain.

As far as my understanding of the issue goes, the correct answer is
"ABC", and compilers that do not produce "ABC" are buggy.

The solution is to transform the code to code that evaluates the
arguments to the extern(C) call in the correct order and eg. stores
them in temporaries before passing them on.
September 25, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On Wed, Sep 26, 2012 at 01:10:00AM +0200, Timon Gehr wrote:
> On 09/26/2012 12:58 AM, Iain Buclaw wrote:
[...]
> >string abc;
> >
> >float[] A()
> >{
> >     abc ~= "A";
> >     return [];
> >}
> >
> >float[] B()
> >{
> >     abc ~= "B";
> >     return [];
> >}
> >
> >float[] C()
> >{
> >     abc ~= "C";
> >     return [];
> >}
> >
> >void main()
> >{
> >     A()[] = B()[] + C()[];
> >     assert(abc == "???");
> >}
> >----
> >
> >Without cheating, I invite people to have a good guess what 'abc' is
> >equal to, but just to narrow it down.
> >
> >1)  It isn't "ABC".
> >2)  On x86/x86_64, it isn't "ACB".
> >3)  On everything else, it's the reverse of what you'd expect on
> >x86/x86_64.
> >
> >The problem here is that the array operation A[] = B[] + C[] gets
> >transformed into an extern(C) call.  And because there's no strict rules
> >in place over the order of which it's parameters are evaluated, it could
> >go either way (LTR, or RTL).
> >
> >Serious note: This test is bogus as this and similar other failing tests
> >on non-x86 platforms are not at all obvious to the users who get issues.
> >So what are we to do about it?
[...]
> As far as my understanding of the issue goes, the correct answer is
> "ABC", and compilers that do not produce "ABC" are buggy.
> 
> The solution is to transform the code to code that evaluates the
> arguments to the extern(C) call in the correct order and eg. stores
> them in temporaries before passing them on.
[...]

Shouldn't it be BCA? I'd expect the assignment operation to take place
last, so the corresponding expression should be evaluated last.


T

-- 
Leather is waterproof.  Ever see a cow with an umbrella?
September 25, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 9/25/2012 3:58 PM, Iain Buclaw wrote:
> The problem here is that the array operation A[] = B[] + C[] gets transformed
> into an extern(C) call.  And because there's no strict rules in place over the
> order of which it's parameters are evaluated, it could go either way (LTR, or RTL).
>
> Serious note: This test is bogus as this and similar other failing tests on
> non-x86 platforms are not at all obvious to the users who get issues. So what
> are we to do about it?

D needs to move towards a defined order of evaluation. I understand that there's 
a problem when using parts of a C compiler that feels free to reorder within the 
C rules. It's something we have to deal with sooner or later, by either:

1. adjusting the C optimizer so it follows D rules for D code

2. assigning terms to temporaries that are executed in a specific order by C rules
September 25, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 09/26/2012 01:31 AM, H. S. Teoh wrote:
> On Wed, Sep 26, 2012 at 01:10:00AM +0200, Timon Gehr wrote:
>> On 09/26/2012 12:58 AM, Iain Buclaw wrote:
> [...]
>>> string abc;
>>>
>>> float[] A()
>>> {
>>>      abc ~= "A";
>>>      return [];
>>> }
>>>
>>> float[] B()
>>> {
>>>      abc ~= "B";
>>>      return [];
>>> }
>>>
>>> float[] C()
>>> {
>>>      abc ~= "C";
>>>      return [];
>>> }
>>>
>>> void main()
>>> {
>>>      A()[] = B()[] + C()[];
>>>      assert(abc == "???");
>>> }
>>> ----
>>>
>>> Without cheating, I invite people to have a good guess what 'abc' is
>>> equal to, but just to narrow it down.
>>>
>>> 1)  It isn't "ABC".
>>> 2)  On x86/x86_64, it isn't "ACB".
>>> 3)  On everything else, it's the reverse of what you'd expect on
>>> x86/x86_64.
>>>
>>> The problem here is that the array operation A[] = B[] + C[] gets
>>> transformed into an extern(C) call.  And because there's no strict rules
>>> in place over the order of which it's parameters are evaluated, it could
>>> go either way (LTR, or RTL).
>>>
>>> Serious note: This test is bogus as this and similar other failing tests
>>> on non-x86 platforms are not at all obvious to the users who get issues.
>>> So what are we to do about it?
> [...]
>> As far as my understanding of the issue goes, the correct answer is
>> "ABC", and compilers that do not produce "ABC" are buggy.
>>
>> The solution is to transform the code to code that evaluates the
>> arguments to the extern(C) call in the correct order and eg. stores
>> them in temporaries before passing them on.
> [...]
>
> Shouldn't it be BCA? I'd expect the assignment operation to take place
> last, so the corresponding expression should be evaluated last.
>
>
> T
>

There are 3 'corresponding' side-effecting expressions.
I expect left-to right, top to bottom evaluation. If BCA is desired it 
is possible to do

auto b = B(), c = C();
A()[] = b[] + c[];

I think having a simple consistent rule for evaluation order is desirable.
September 26, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On Tuesday, 25 September 2012 at 23:39:39 UTC, Walter Bright 
wrote:
> On 9/25/2012 3:58 PM, Iain Buclaw wrote:
>> The problem here is that the array operation A[] = B[] + C[] 
>> gets transformed
>> into an extern(C) call.  And because there's no strict rules 
>> in place over the
>> order of which it's parameters are evaluated, it could go 
>> either way (LTR, or RTL).
>>
>> Serious note: This test is bogus as this and similar other 
>> failing tests on
>> non-x86 platforms are not at all obvious to the users who get 
>> issues. So what
>> are we to do about it?
>
> D needs to move towards a defined order of evaluation. I 
> understand that there's a problem when using parts of a C 
> compiler that feels free to reorder within the C rules. It's 
> something we have to deal with sooner or later, by either:
>
> 1. adjusting the C optimizer so it follows D rules for D code
>
> 2. assigning terms to temporaries that are executed in a 
> specific order by C rules


Indeed, but where does that leave code that gets compiled down to 
a extern(C) call?

eg, in the OP, the following is generated:
_arraySliceSliceAddSliceAssign_f(A[], C[], B[]);

To say that all extern(C) calls must follow D rules for D code 
(LTR evaluation), is to change the current behaviour of array 
operations on it's head, so we'll have to correct a whole lotta 
changes in code generation to alter the order of parameters, and 
ensure that both DRT supplied and internally generated functions 
are corrected for this.

Well... someone's got to do the grizzly bits that no one else 
wants to do. :~)


Regards,
Iain.
September 26, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 9/26/2012 12:36 AM, Iain Buclaw wrote:
> On Tuesday, 25 September 2012 at 23:39:39 UTC, Walter Bright wrote:
>> On 9/25/2012 3:58 PM, Iain Buclaw wrote:
>>> The problem here is that the array operation A[] = B[] + C[] gets transformed
>>> into an extern(C) call.  And because there's no strict rules in place over the
>>> order of which it's parameters are evaluated, it could go either way (LTR, or
>>> RTL).
>>>
>>> Serious note: This test is bogus as this and similar other failing tests on
>>> non-x86 platforms are not at all obvious to the users who get issues. So what
>>> are we to do about it?
>>
>> D needs to move towards a defined order of evaluation. I understand that
>> there's a problem when using parts of a C compiler that feels free to reorder
>> within the C rules. It's something we have to deal with sooner or later, by
>> either:
>>
>> 1. adjusting the C optimizer so it follows D rules for D code
>>
>> 2. assigning terms to temporaries that are executed in a specific order by C
>> rules
>
>
> Indeed, but where does that leave code that gets compiled down to a extern(C) call?

C functions all seem to evaluate their args right-to-left, even though the C 
Standard doesn't specify that. So we should be all right by simply defining that 
D do it that way for C functions.

It doesn't actually matter what order D does things, we just have to pick one. 
And so we might as well pick one that C compilers naturally do anyway.

>
> eg, in the OP, the following is generated:
> _arraySliceSliceAddSliceAssign_f(A[], C[], B[]);
>
> To say that all extern(C) calls must follow D rules for D code (LTR evaluation),
> is to change the current behaviour of array operations on it's head, so we'll
> have to correct a whole lotta changes in code generation to alter the order of
> parameters, and ensure that both DRT supplied and internally generated functions
> are corrected for this.
>
> Well... someone's got to do the grizzly bits that no one else wants to do. :~)
>
>
> Regards,
> Iain.
September 26, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On 26/09/12 01:31, H. S. Teoh wrote:
> On Wed, Sep 26, 2012 at 01:10:00AM +0200, Timon Gehr wrote:
>> On 09/26/2012 12:58 AM, Iain Buclaw wrote:
> [...]
>>> string abc;
>>>
>>> float[] A()
>>> {
>>>      abc ~= "A";
>>>      return [];
>>> }
>>>
>>> float[] B()
>>> {
>>>      abc ~= "B";
>>>      return [];
>>> }
>>>
>>> float[] C()
>>> {
>>>      abc ~= "C";
>>>      return [];
>>> }
>>>
>>> void main()
>>> {
>>>      A()[] = B()[] + C()[];
>>>      assert(abc == "???");
>>> }
>>> ----
>>>
>>> Without cheating, I invite people to have a good guess what 'abc' is
>>> equal to, but just to narrow it down.
>>>
>>> 1)  It isn't "ABC".
>>> 2)  On x86/x86_64, it isn't "ACB".
>>> 3)  On everything else, it's the reverse of what you'd expect on
>>> x86/x86_64.
>>>
>>> The problem here is that the array operation A[] = B[] + C[] gets
>>> transformed into an extern(C) call.  And because there's no strict rules
>>> in place over the order of which it's parameters are evaluated, it could
>>> go either way (LTR, or RTL).
>>>
>>> Serious note: This test is bogus as this and similar other failing tests
>>> on non-x86 platforms are not at all obvious to the users who get issues.
>>> So what are we to do about it?
> [...]
>> As far as my understanding of the issue goes, the correct answer is
>> "ABC", and compilers that do not produce "ABC" are buggy.
>>
>> The solution is to transform the code to code that evaluates the
>> arguments to the extern(C) call in the correct order and eg. stores
>> them in temporaries before passing them on.
> [...]
>
> Shouldn't it be BCA? I'd expect the assignment operation to take place
> last, so the corresponding expression should be evaluated last.

I expected "BCA" too. Left associative expressions evaluated 
left-to-right, right associative expressions evaluated right-to-left.
September 26, 2012
Re: Order of evaluation - aka hidden undefined behaviours.
On Wednesday, 26 September 2012 at 08:12:16 UTC, Walter Bright 
wrote:
> On 9/26/2012 12:36 AM, Iain Buclaw wrote:
>> On Tuesday, 25 September 2012 at 23:39:39 UTC, Walter Bright 
>> wrote:
>>> On 9/25/2012 3:58 PM, Iain Buclaw wrote:
>>>> The problem here is that the array operation A[] = B[] + C[] 
>>>> gets transformed
>>>> into an extern(C) call.  And because there's no strict rules 
>>>> in place over the
>>>> order of which it's parameters are evaluated, it could go 
>>>> either way (LTR, or
>>>> RTL).
>>>>
>>>> Serious note: This test is bogus as this and similar other 
>>>> failing tests on
>>>> non-x86 platforms are not at all obvious to the users who 
>>>> get issues. So what
>>>> are we to do about it?
>>>
>>> D needs to move towards a defined order of evaluation. I 
>>> understand that
>>> there's a problem when using parts of a C compiler that feels 
>>> free to reorder
>>> within the C rules. It's something we have to deal with 
>>> sooner or later, by
>>> either:
>>>
>>> 1. adjusting the C optimizer so it follows D rules for D code
>>>
>>> 2. assigning terms to temporaries that are executed in a 
>>> specific order by C
>>> rules
>>
>>
>> Indeed, but where does that leave code that gets compiled down 
>> to a extern(C) call?
>
> C functions all seem to evaluate their args right-to-left, even 
> though the C Standard doesn't specify that. So we should be all 
> right by simply defining that D do it that way for C functions.
>
> It doesn't actually matter what order D does things, we just 
> have to pick one. And so we might as well pick one that C 
> compilers naturally do anyway.
>

Speaking as a generalisation, no that is not true.  C functions 
for x86/x86_64 all seem to evaluate their args right-to-left.  
However - and this may be different from compiler to compiler - 
GCC at least does left-to-right evaluation for everything else 
(ARM, SPARC, etc) because that is the order that arguments are 
pushed onto the stack for those architecture backends.

If right-to-left should be the strict standard to follow for 
extern(C), then document this behaviour as part of the 
specification, and I'll implement it. :~)

Regards
Iain
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home