Am Wed, 02 Apr 2014 07:47:23 +0000
schrieb "Sarath Kodali" <sarath@dummy.com>:

> On Tuesday, 1 April 2014 at 22:04:43 UTC, Timon Gehr wrote:
> > On 04/01/2014 08:40 PM, Sarath Kodali wrote:
> >> ...
> >>
> >> The evaluation order of assign operators should not be LTR as
> >> they have
> >> right associativity. In "a = b = c", c has to be evaluated
> >> first, then b
> >> and then a. Similarly, in "a = b + c", "b+c" has to be
> >> evaluated first
> >> before a is evaluated. Otherwise it will be very confusing,
> >> that in some
> >> cases it is LTR and in some it is RTL.
> >
> > Note that this is after a paragraph that suggests to make evaluation in some cases LTR and in some RTL.
> >
> 
> There are 2 evaluation orders that need to be considered while evaluating expressions - the evaluation order of operators and the the evaluation order of operands of an operator. The evaluation order of operators is well defined and is done according to its precedence and associativity. However the evaluation order of operands for some of the binary operators is not defined. D left it undefined for assign operator. So in "a=b", the compiler can choose to evaluate a first and then b. However in "a=b=c", "b=c" has to be evaluated first due to right associativity of '=' operator. Similarly in "a=b+c", "b+c" has to be evaluated first due to higher precedence of + operator over = operator.  In both these cases, the right operand of = operator is evaluated first and then the left operand. So it naturally follows that even in the unspecified case (a=b), the right operand should be evaluated first so that it is consistent with other cases of = operator. All this means, the evaluation order of operands also should be according to the associativity of its operator. You can test this with other right or left associative binary operators.

In a=b=c you have to do assignment b=c first, then assign a=b. But we're
talking about _side effects_ here, i.e. a() = b() = c(). And you can
evaluate the side effects in LTR order:

a() = b() = c();
==>
	auto tmp1 = &a();
	auto tmp2 = &b();
	*tmp2 = c();
	*tmp1 = *tmp2;

http://dpaste.dzfl.pl/19c118b7d368

Am Wed, 2 Apr 2014 10:48:33 +0200
schrieb Johannes Pfau <nospam@example.com>:

> http://dpaste.dzfl.pl/19c118b7d368

BTW: LDC and even very old versions of GDC already evaluate that LTR, you can switch the compiler to LDC to see that:

http://dpaste.dzfl.pl/cec5cc3b7dd7

On Wednesday, 2 April 2014 at 08:02:36 UTC, Iain Buclaw wrote:
> On 2 Apr 2014 09:52, "Sarath Kodali" <sarath@dummy.com> wrote:
>>
>> On Tuesday, 1 April 2014 at 22:04:43 UTC, Timon Gehr wrote:
>>>
>>> On 04/01/2014 08:40 PM, Sarath Kodali wrote:
>>>>
>>>> ...
>>>>
>>>> The evaluation order of assign operators should not be LTR as they have
>>>> right associativity. In "a = b = c", c has to be evaluated first, then b
>>>> and then a. Similarly, in "a = b + c", "b+c" has to be evaluated first
>>>> before a is evaluated. Otherwise it will be very confusing, that in some
>>>> cases it is LTR and in some it is RTL.
>>>
>>>
>>> Note that this is after a paragraph that suggests to make evaluation in
> some cases LTR and in some RTL.
>>>
>>
>> There are 2 evaluation orders that need to be considered while evaluating
> expressions - the evaluation order of operators and the the evaluation
> order of operands of an operator. The evaluation order of operators is well
> defined and is done according to its precedence and associativity. However
> the evaluation order of operands for some of the binary operators is not
> defined. D left it undefined for assign operator. So in "a=b", the compiler
> can choose to evaluate a first and then b. However in "a=b=c", "b=c" has to
> be evaluated first due to right associativity of '=' operator. Similarly in
> "a=b+c", "b+c" has to be evaluated first due to higher precedence of +
> operator over = operator.  In both these cases, the right operand of =
> operator is evaluated first and then the left operand. So it naturally
> follows that even in the unspecified case (a=b), the right operand should
> be evaluated first so that it is consistent with other cases of = operator.
> All this means, the evaluation order of operands also should be according
> to the associativity of its operator. You can test this with other right or
> left associative binary operators.
>>
>>
>>
>>>> Other binary operators like "+" have left associativity, and hence
>>>> evaluation for these should be LTR as mentioned in D spec.
>>>> ...
>>>
>>>
>>> What's the presumed relation between associativity and evaluation order?
>>>
>>> In particular, the ternary operator ?: is right associative. How on
> earth are you going to evaluate it right to left?
>>>
>>>> The C spec requires that the function arguments are to be pushed in RTL
>>>> order.
>>>
>>>
>>> [citation needed]
>>>
>>
>> You can get that info from any C ABI doc from Intel or AMD or some other
> arch.
>>
>
> That's order of pushing arguments, not order of evaluation.  Also, heavy
> stress on the words *Intel* and *AMD*.  That is in no way a C standard. :)

Please do not get confused between operands evaluation order in an expression and arguments passing order to a function. Those are two different things. I was talking about both of them because both of them are involved in the evaluation of a()[] = b()[] + c()[]. To a programmer this is an expression that should follow expression evaluation rules. To a compiler implementer, this is a builtin function call whose arguments should be evaluated such that the expression evaluation rules are not broken.

If you read the last para in my first post, I was talking about argument pushing order *not* evaluation order for function args. The function argument passing order (called calling convention) is not defined by C spec, but by C ABI spec of any architecture. In all the C calling conventions, the first few arguments are passed in registers and the remaining on the stack. On Linux+x86, all the arguments are passed on the stack. For C, the arguments that are passed on the stack are in reverse order i.e RTL. Since the proposal was to change the argument evaluation order for extern(C) functions, I was merely pointing out that this will have an impact on the dmd backend because it uses pushl instructions. Notice that for extern (C) functions, the argument evaluation order and argument pushing order is same. So dmd evaluates an argument and pushes it immediately. If the evaluation order is opposite to that of the pushing order, then it cannot immediately push the argument that it has evaluated. However if it uses movl instructions as is done by gcc backend, then there is no issue.

- Sarath

* pushl and movl are x86 instructions.

On Wednesday, 2 April 2014 at 08:50:17 UTC, Johannes Pfau wrote:
> Am Wed, 02 Apr 2014 07:47:23 +0000
> schrieb "Sarath Kodali" <sarath@dummy.com>:
>
>> On Tuesday, 1 April 2014 at 22:04:43 UTC, Timon Gehr wrote:
>> > On 04/01/2014 08:40 PM, Sarath Kodali wrote:
>> >> ...
>> >>
>> >> The evaluation order of assign operators should not be LTR as they have
>> >> right associativity. In "a = b = c", c has to be evaluated first, then b
>> >> and then a. Similarly, in "a = b + c", "b+c" has to be evaluated first
>> >> before a is evaluated. Otherwise it will be very confusing, that in some
>> >> cases it is LTR and in some it is RTL.
>> >
>> > Note that this is after a paragraph that suggests to make evaluation in some cases LTR and in some RTL.
>> >
>> 
>> There are 2 evaluation orders that need to be considered while evaluating expressions - the evaluation order of operators and the the evaluation order of operands of an operator. The evaluation order of operators is well defined and is done according to its precedence and associativity. However the evaluation order of operands for some of the binary operators is not defined. D left it undefined for assign operator. So in "a=b", the compiler can choose to evaluate a first and then b. However in "a=b=c", "b=c" has to be evaluated first due to right associativity of '=' operator. Similarly in "a=b+c", "b+c" has to be evaluated first due to higher precedence of + operator over = operator.  In both these cases, the right operand of = operator is evaluated first and then the left operand. So it naturally follows that even in the unspecified case (a=b), the right operand should be evaluated first so that it is consistent with other cases of = operator. All this means, the evaluation order of operands also should be according to the associativity of its operator. You can test this with other right or left associative binary operators.
>
> In a=b=c you have to do assignment b=c first, then assign a=b. But we're
> talking about _side effects_ here, i.e. a() = b() = c(). And you can
> evaluate the side effects in LTR order:
>
> a() = b() = c();
> ==>
> 	auto tmp1 = &a();
> 	auto tmp2 = &b();
> 	*tmp2 = c();
> 	*tmp1 = *tmp2;
>
> http://dpaste.dzfl.pl/19c118b7d368

Once the evaluation order of an operator is defined, it should be consistent in all the cases. Otherwise it will be very confusing to the programmer.

- Sarath

On 2 April 2014 15:04, Sarath Kodali <sarath@dummy.com> wrote:
> On Wednesday, 2 April 2014 at 08:02:36 UTC, Iain Buclaw wrote:
>>
>> On 2 Apr 2014 09:52, "Sarath Kodali" <sarath@dummy.com> wrote:
>>>
>>>
>>> On Tuesday, 1 April 2014 at 22:04:43 UTC, Timon Gehr wrote:
>>>>
>>>>
>>>> On 04/01/2014 08:40 PM, Sarath Kodali wrote:
>>>>>
>>>>>
>>>>> ...
>>>>>
>>>>> The evaluation order of assign operators should not be LTR as they have
>>>>> right associativity. In "a = b = c", c has to be evaluated first, then
>>>>> b
>>>>> and then a. Similarly, in "a = b + c", "b+c" has to be evaluated first
>>>>> before a is evaluated. Otherwise it will be very confusing, that in
>>>>> some
>>>>> cases it is LTR and in some it is RTL.
>>>>
>>>>
>>>>
>>>> Note that this is after a paragraph that suggests to make evaluation in
>>
>> some cases LTR and in some RTL.
>>>>
>>>>
>>>
>>> There are 2 evaluation orders that need to be considered while evaluating
>>
>> expressions - the evaluation order of operators and the the evaluation
>> order of operands of an operator. The evaluation order of operators is
>> well
>> defined and is done according to its precedence and associativity. However
>> the evaluation order of operands for some of the binary operators is not
>> defined. D left it undefined for assign operator. So in "a=b", the
>> compiler
>> can choose to evaluate a first and then b. However in "a=b=c", "b=c" has
>> to
>> be evaluated first due to right associativity of '=' operator. Similarly
>> in
>> "a=b+c", "b+c" has to be evaluated first due to higher precedence of +
>> operator over = operator.  In both these cases, the right operand of =
>> operator is evaluated first and then the left operand. So it naturally
>> follows that even in the unspecified case (a=b), the right operand should
>> be evaluated first so that it is consistent with other cases of =
>> operator.
>> All this means, the evaluation order of operands also should be according
>> to the associativity of its operator. You can test this with other right
>> or
>> left associative binary operators.
>>>
>>>
>>>
>>>
>>>>> Other binary operators like "+" have left associativity, and hence
>>>>> evaluation for these should be LTR as mentioned in D spec.
>>>>> ...
>>>>
>>>>
>>>>
>>>> What's the presumed relation between associativity and evaluation order?
>>>>
>>>> In particular, the ternary operator ?: is right associative. How on
>>
>> earth are you going to evaluate it right to left?
>>>>
>>>>
>>>>> The C spec requires that the function arguments are to be pushed in RTL order.
>>>>
>>>>
>>>>
>>>> [citation needed]
>>>>
>>>
>>> You can get that info from any C ABI doc from Intel or AMD or some other
>>
>> arch.
>>>
>>>
>>
>> That's order of pushing arguments, not order of evaluation.  Also, heavy stress on the words *Intel* and *AMD*.  That is in no way a C standard. :)
>
>
> Please do not get confused between operands evaluation order in an expression and arguments passing order to a function. Those are two different things. I was talking about both of them because both of them are involved in the evaluation of a()[] = b()[] + c()[]. To a programmer this is an expression that should follow expression evaluation rules. To a compiler implementer, this is a builtin function call whose arguments should be evaluated such that the expression evaluation rules are not broken.
>

Right.  But order of evaluation is Language-specific, order of pushing arguments is Target-specific.  Both are completely indifferent from each other, and this is what I think you are not understanding.


> If you read the last para in my first post, I was talking about argument pushing order *not* evaluation order for function args. The function argument passing order (called calling convention) is not defined by C spec, but by C ABI spec of any architecture. In all the C calling conventions, the first few arguments are passed in registers and the remaining on the stack. On Linux+x86, all the arguments are passed on the stack. For C, the arguments that are passed on the stack are in reverse order i.e RTL. Since the proposal was to change the argument evaluation order for extern(C) functions,

And the pushing order is unaffected, so why bring it up in the first place?


> I was merely pointing out that this will have an impact on the
> dmd backend because it uses pushl instructions. Notice that for extern (C)
> functions, the argument evaluation order and argument pushing order is same.
> So dmd evaluates an argument and pushes it immediately. If the evaluation
> order is opposite to that of the pushing order, then it cannot immediately
> push the argument that it has evaluated. However if it uses movl
> instructions as is done by gcc backend, then there is no issue.
>

Actually, the gcc backend does the same if the parameter passed has not had all side effects removed from it.

On 04/02/2014 09:47 AM, Sarath Kodali wrote:
> On Tuesday, 1 April 2014 at 22:04:43 UTC, Timon Gehr wrote:
>> On 04/01/2014 08:40 PM, Sarath Kodali wrote:
>>> ...
>>>
>>> The evaluation order of assign operators should not be LTR as they have
>>> right associativity. In "a = b = c", c has to be evaluated first, then b
>>> and then a. Similarly, in "a = b + c", "b+c" has to be evaluated first
>>> before a is evaluated. Otherwise it will be very confusing, that in some
>>> cases it is LTR and in some it is RTL.
>>
>> Note that this is after a paragraph that suggests to make evaluation
>> in some cases LTR and in some RTL.
>>
>
> There are 2 evaluation orders that need to be considered while
> evaluating expressions - the evaluation order of operators and the the
> evaluation order of operands of an operator.
> The evaluation order of operators is well defined

(That's a somewhat strong/ill-formed statement, as operator applications will in general occur as operands.)

> and is done according to its precedence and
> associativity.

Evaluation order is according to data dependencies. (But C does not even guarantee this.) Expressions are _parsed_ according to precedence and associativity. Precedence and associativity are determined roughly according to common usage to reduce the number of parentheses needed to write down a typical expression.

> However the evaluation order of operands for some of the
> binary operators is not defined. D left it undefined for assign
> operator. So in "a=b", the compiler can choose to evaluate a first and
> then b. However in "a=b=c", "b=c" has to be evaluated first

Before the outer assignment, not necessarily before 'a'.

> due to right associativity of '=' operator.
> Similarly in "a=b+c", "b+c" has to be
> evaluated first

Again, evaluated before the assignment, not necessarily before 'a'.

> due to higher precedence of + operator over = operator.
> In both these cases, the right operand of = operator is evaluated first
> and then the left operand.

No, neither of the two cases made any point about the left operand.

> So it naturally follows

I disagree here. Doing it the same way consistently for all operations is more 'natural' a priori. Deviations should be justified by actual semantics, not parsing details. (E.g. a hypothetical argument might be that 'ref' returns are less dangerous with RTL evaluation of assignments.) Such arguments, if convincing ones exist, would not necessarily generalize to all right-associative expressions.

> that even in the unspecified case (a=b), the right operand should be evaluated first so
> that it is consistent with other cases of = operator. All this means,
> the evaluation order of operands also should be according to the
> associativity of its operator.
> You can test this with other right or left associative binary operators.
>

int a = 1;
int b = (a++)^^(a++)^^(a++); // 1 is a fine value

On Wednesday, 2 April 2014 at 14:43:44 UTC, Iain Buclaw wrote:
>>
>>
>> Please do not get confused between operands evaluation order in an
>> expression and arguments passing order to a function. Those are two
>> different things. I was talking about both of them because both of them are
>> involved in the evaluation of a()[] = b()[] + c()[]. To a programmer this is
>> an expression that should follow expression evaluation rules. To a compiler
>> implementer, this is a builtin function call whose arguments should be
>> evaluated such that the expression evaluation rules are not broken.
>>
>
> Right.  But order of evaluation is Language-specific, order of pushing
> arguments is Target-specific.  Both are completely indifferent from
> each other, and this is what I think you are not understanding.
>
>
I started my career, 19 years back, as a C compiler developer. So I know what is evaluation order and argument passing order. And more importantly, the discussion is about the *evaluation order* of "a()[] = b()[] + c()[]" and not about what I understand or don't! So if you have any valid points that says why this expression should be evaluated in LTR order (i.e. first a then b and then c) let us discuss that.
You can write a small code that evaluates "a()[] = b()[] + c()[]" before and after the proposed modifications and check whether the evaluation order is same w.r.t dmd. DMD v2.64 evaluates first b, then c and then a. This behaviour conforms to the D spec.

>> If you read the last para in my first post, I was talking about argument
>> pushing order *not* evaluation order for function args. The function
>> argument passing order (called calling convention) is not defined by C spec,
>> but by C ABI spec of any architecture. In all the C calling conventions, the
>> first few arguments are passed in registers and the remaining on the stack.
>> On Linux+x86, all the arguments are passed on the stack. For C, the
>> arguments that are passed on the stack are in reverse order i.e RTL. Since
>> the proposal was to change the argument evaluation order for extern(C)
>> functions,
>
> And the pushing order is unaffected, so why bring it up in the first place?
>

Let me take an example to explain what I'm trying to say.

extern (C) int foo(int a, int b);

void main(void)
{
    foo(a(), b());
}

With RTL function argument evaluation order and with push instructions, the above code gets compiled by dmd as (only relevant asm code shown) (on x86)

main:
   call b
   push %eax
   call a
   push %eax
   call foo

Now if the evaluation order of function args is changed to LTR, the new asm code would be

main:
    call a
    mov %eax, %esi
    call b
    push %eax
    push %esi
    call foo

Notice the additional mov instruction to save the return value of a() in a temporary.  This is the impact that I'm talking about. Now if dmd backend uses mov instructions to push args on to the stack instead of push, then there will not be a need for temporary. But the code size will increase as push is only 1 byte where as mov %eax offset(%esp) is 3 to 4 bytes long.

Asm code with LTR func args evaluation order for extern(C) foo with mov instrs
main:
     call a
     mov %eax, (%esp)
     call b
     mov %eax, 0x4(%esp)
     call foo

Notice that the args are still pushed in RTL order.

>
>> I was merely pointing out that this will have an impact on the
>> dmd backend because it uses pushl instructions. Notice that for extern (C)
>> functions, the argument evaluation order and argument pushing order is same.
>> So dmd evaluates an argument and pushes it immediately. If the evaluation
>> order is opposite to that of the pushing order, then it cannot immediately
>> push the argument that it has evaluated. However if it uses movl
>> instructions as is done by gcc backend, then there is no issue.
>>
>
> Actually, the gcc backend does the same if the parameter passed has
> not had all side effects removed from it.

- Sarath

On 2 Apr 2014 21:00, "Sarath Kodali" <sarath@dummy.com> wrote:
>
> On Wednesday, 2 April 2014 at 14:43:44 UTC, Iain Buclaw wrote:
>>>
>>>
>>>
>>> Please do not get confused between operands evaluation order in an expression and arguments passing order to a function. Those are two different things. I was talking about both of them because both of them
are
>>> involved in the evaluation of a()[] = b()[] + c()[]. To a programmer
this is
>>> an expression that should follow expression evaluation rules. To a
compiler
>>> implementer, this is a builtin function call whose arguments should be evaluated such that the expression evaluation rules are not broken.
>>>
>>
>> Right.  But order of evaluation is Language-specific, order of pushing arguments is Target-specific.  Both are completely indifferent from each other, and this is what I think you are not understanding.
>>
>>
> I started my career, 19 years back, as a C compiler developer. So I know
what is evaluation order and argument passing order. And more importantly,
the discussion is about the *evaluation order* of "a()[] = b()[] + c()[]"
and not about what I understand or don't! So if you have any valid points
that says why this expression should be evaluated in LTR order (i.e. first
a then b and then c) let us discuss that.
> You can write a small code that evaluates "a()[] = b()[] + c()[]" before
and after the proposed modifications and check whether the evaluation order is same w.r.t dmd. DMD v2.64 evaluates first b, then c and then a. This behaviour conforms to the D spec.
>

Array ops follow a different behaviour to what is what normally expected.
In a() = b() + c(), the order is abc, not bca.

The fact that the current behaviour is written in the spec is not a good reason to keep it.

>>> If you read the last para in my first post, I was talking about argument pushing order *not* evaluation order for function args. The function argument passing order (called calling convention) is not defined by C
spec,
>>> but by C ABI spec of any architecture. In all the C calling
conventions, the
>>> first few arguments are passed in registers and the remaining on the
stack.
>>> On Linux+x86, all the arguments are passed on the stack. For C, the arguments that are passed on the stack are in reverse order i.e RTL.
Since
>>> the proposal was to change the argument evaluation order for extern(C)
>>> functions,
>>
>>
>> And the pushing order is unaffected, so why bring it up in the first
place?
>>
>
> Let me take an example to explain what I'm trying to say.
>
> extern (C) int foo(int a, int b);
>
> void main(void)
> {
>     foo(a(), b());
> }
>
> With RTL function argument evaluation order and with push instructions,
the above code gets compiled by dmd as (only relevant asm code shown) (on
x86)
>
> main:
>    call b
>    push %eax
>    call a
>    push %eax
>    call foo
>
> Now if the evaluation order of function args is changed to LTR, the new
asm code would be
>
> main:
>     call a
>     mov %eax, %esi
>     call b
>     push %eax
>     push %esi
>     call foo
>
> Notice the additional mov instruction to save the return value of a() in
a temporary.  This is the impact that I'm talking about. Now if dmd backend uses mov instructions to push args on to the stack instead of push, then there will not be a need for temporary. But the code size will increase as push is only 1 byte where as mov %eax offset(%esp) is 3 to 4 bytes long.
>
> Asm code with LTR func args evaluation order for extern(C) foo with mov
instrs
> main:
>      call a
>      mov %eax, (%esp)
>      call b
>      mov %eax, 0x4(%esp)
>      call foo
>
> Notice that the args are still pushed in RTL order.
>

Your point?

Now I'm working to fix issue 6620

https://issues.dlang.org/show_bug.cgi?id=6620 https://github.com/D-Programming-Language/dmd/pull/4035

Kenji Hara

2014-04-01 20:49 GMT+09:00 Johannes Pfau <nospam@example.com>:

> I started fixing GDC bug #8 (*) which is basically that array op
> evaluation order currently depends on the target architecture. Consider
> this example:
> a()[] = b()[] + c()[];
> The order in which c,a,b are called is currently architecture specific.
> As stated in that bug report by Andrei we want this to evaluate LTR, so
> a() first, then b(), then c().
>
> These operations are actually rewritten to calls to extern(C) functions. Arguments to C function should be evaluated LTR as well, but dmd currently evaluates them RTL (GDC: architecture dependent). In order to fix the array op bug in gdc we have to define the evaluation order for extern(C) function parameters.
>
> So I've changed extern(C) functions to evaluate LTR in GDC and then had
> to change the array op code, cause that assumed extern(C) function
> evaluate RTL. Now I'd like to push these array op changes into dmd as we
> want to keep as few gdc specific changes as possible and dmd (and ldc)
> will need these changes anyway as soon as they implement extern(C)
> functions as LTR. This is required by dmd issue #6620 (**) and the
> language spec (***).
>
> However, if we apply only these changes the array op order reverses for DMD as it evaluates extern(C) function arguments RTL.
>
> So I need someone with dmd backend knowledge to fix the evaluation
> order of extern(C) function parameters to be LTR.
> Evaluation order of assignments should also be fixed to be LTR in the
> dmd backend. Although not strictly required for the array op changes
> it'd be inconsistent to have array op assignments execute LTR but
> normal assignments RTL:
> a()[] = b()[] + c()[]; //Array op assignment
> a() = b() + c();       //Normal assignment
>  |      |    |
>  1      2    3
>
> The frontend changes for dmd are here:
> https://github.com/jpf91/dmd/tree/fixOrder
> Frontend:
>
> https://github.com/jpf91/dmd/commit/5d61b812977dbdc1f99100e2fbaf1f45e9d25b03 Test cases:
>
> https://github.com/jpf91/dmd/commit/82bffe0862b272f02c27cc428b22a7dd113b4a07
>
> Druntime changes (need to be applied at the same time as dmd changes) https://github.com/jpf91/druntime/tree/fixOrder
>
> https://github.com/jpf91/druntime/commit/f3f6f49c595d4fb25fb298e435ad1874abac516d
>
>
> (*)   http://bugzilla.gdcproject.org/show_bug.cgi?id=8
> (**)  https://d.puremagic.com/issues/show_bug.cgi?id=6620
> (***) https://github.com/D-Programming-Language/dlang.org/pull/6
>