Two cases of array literal that can be stack-allocated

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2014-08-27T09:39:19Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=13381

CC List

• Nick Treleaven (@ntrel)
• yebblies

Description

I think this is an array literal usage pattern where the compiler can allocate the array on the stack, allowing the function foo to be @nogc:


void foo(in uint[] a) @nogc {
    if (a == [1]) {}
}
void main() {}


Currently dmd 2.067alpha gives:

temp.d(2,14): Error: array literal in @nogc function foo may cause GC allocation

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T09:05:58Z

I agree.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-31T10:07:39Z

Given this code:

void foo(uint[] a) @nogc {
    if (a == [1, 2]) {}
}


One way to rewrite it is (the immutable can't be always used):


void foo(uint[] a) @nogc {
    immutable static uint[2] __foo_aux0 == [1, 2];
    if (a == __foo_aux0) {}
}


Or more efficient:

void foo(uint[] a) @nogc {
    if (a.length == 2 && a[0] == 1 && a[1] == 2) {}
}

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T10:12:33Z

(In reply to bearophile_hugs from comment #2)
> 
> One way to rewrite it is (the immutable can't be always used):
> 

While re-writes are certainly the simplest way to explain it, using them in the compiler often leads to complications, especially with error messages referring to the re-written code instead of the original.

For this case, and similar cases, the compiler can simply type the array literal as a static array, because it knows that == can't escape any references.  It already does something like this for indexing array literals.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-31T10:42:32Z

(In reply to yebblies from comment #3)

> For this case, and similar cases, the compiler can simply type the array
> literal as a static array, because it knows that == can't escape any
> references.  It already does something like this for indexing array literals.

I see. I have suggested a rewrite like this:

if (a.length == 2 && a[0] == 1 && a[1] == 2) {}

Because most array literals used for equality or comparison are short or very short, so calling == or < on few single items is much more efficient than calling a runtime function that works on whole arrays.

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T10:50:13Z

(In reply to bearophile_hugs from comment #4)
> (In reply to yebblies from comment #3)
> 
> > For this case, and similar cases, the compiler can simply type the array
> > literal as a static array, because it knows that == can't escape any
> > references.  It already does something like this for indexing array literals.
> 
> I see. I have suggested a rewrite like this:
> 
> if (a.length == 2 && a[0] == 1 && a[1] == 2) {}
> 
> Because most array literals used for equality or comparison are short or
> very short, so calling == or < on few single items is much more efficient
> than calling a runtime function that works on whole arrays.

Ideally the optimizer would do this by itself, once the literal is stack-allocated.  I suspect it already does in some cases for gdc/ldc.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-31T11:00:06Z

(In reply to yebblies from comment #5)

> Ideally the optimizer would do this by itself, once the literal is
> stack-allocated.  I suspect it already does in some cases for gdc/ldc.

If I compile this program:


bool foo(in int[] a) {
    return a == [1, 2, 3];
}
void main() {}


With the latest ldc2 with:

ldmd2 -O -release -inline -noboundscheck -output-s test.d


The asm of foo is:

__D4test3fooFxAiZb:
    subl    $20, %esp
    movl    $3, 4(%esp)
    movl    $__D12TypeInfo_xAi6__initZ, (%esp)
    calll   __d_newarrayvT
    movl    $3, 8(%edx)
    movl    $2, 4(%edx)
    movl    $1, (%edx)
    movl    %edx, 12(%esp)
    movl    %eax, 8(%esp)
    movl    28(%esp), %eax
    movl    %eax, 4(%esp)
    movl    24(%esp), %eax
    movl    %eax, (%esp)
    movl    $__D12TypeInfo_Axi6__initZ, 16(%esp)
    calll   __adEq2
    testl   %eax, %eax
    setne   %al
    addl    $20, %esp
    ret $8

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T11:02:05Z

(In reply to bearophile_hugs from comment #6)
> (In reply to yebblies from comment #5)
> 
> > Ideally the optimizer would do this by itself, once the literal is
> > stack-allocated.  I suspect it already does in some cases for gdc/ldc.
> 
> If I compile this program:
> 

Like I said, once the literal is stack-allocated it's more likely to work.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-31T11:04:34Z

(In reply to yebblies from comment #7)

> Like I said, once the literal is stack-allocated it's more likely to work.

OK, another experiment:


bool foo(in int[] a) {
    immutable static int[3] aux = [1, 2, 3];
    return a == aux;
}
void main() {}


__D4test3fooFxAiZb:
    subl    $20, %esp
    movl    28(%esp), %eax
    movl    %eax, 4(%esp)
    movl    24(%esp), %eax
    movl    %eax, (%esp)
    movl    $__D12TypeInfo_Axi6__initZ, 16(%esp)
    movl    $__D4test3fooFxAiZb3auxyG3i, 12(%esp)
    movl    $3, 8(%esp)
    calll   __adEq2
    testl   %eax, %eax
    setne   %al
    addl    $20, %esp
    ret $8

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T11:10:39Z

(In reply to bearophile_hugs from comment #8)
> (In reply to yebblies from comment #7)
> 
> > Like I said, once the literal is stack-allocated it's more likely to work.
> 
> OK, another experiment:
> 
> 
> bool foo(in int[] a) {
>     immutable static int[3] aux = [1, 2, 3];
>     return a == aux;
> }
> void main() {}
> 
> 
> __D4test3fooFxAiZb:
>     subl    $20, %esp
>     movl    28(%esp), %eax
>     movl    %eax, 4(%esp)
>     movl    24(%esp), %eax
>     movl    %eax, (%esp)
>     movl    $__D12TypeInfo_Axi6__initZ, 16(%esp)
>     movl    $__D4test3fooFxAiZb3auxyG3i, 12(%esp)
>     movl    $3, 8(%esp)
>     calll   __adEq2
>     testl   %eax, %eax
>     setne   %al
>     addl    $20, %esp
>     ret $8

Which compiler?  I'd say it's worth filing an optimizer enhancement.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-31T11:24:40Z

(In reply to yebblies from comment #9)

> Which compiler?

The latest ldc2, version   0.14.0 (DMD v2.065, LLVM 3.4.2).

dmd is not doing better.
I don't know what gdc does in this case.


> I'd say it's worth filing an optimizer enhancement.

I don't know.

[dlangBugzillaToGithub]

yebblies commented on 2014-08-31T11:40:24Z

(In reply to bearophile_hugs from comment #10)
> 
> dmd is not doing better.

Haha no surprise there.

> 
> > I'd say it's worth filing an optimizer enhancement.
> 
> I don't know.

Actually this is the same thing as general inlining and expanding of array ops, which I think you've already filed.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-09-16T10:00:37Z

Another case worth optimizing:


void main() @nogc {
    import std.traits: EnumMembers;
    enum Foo { A, B, C, D }
    size_t i = 2;
    Foo[4] foos = [EnumMembers!Foo]; // OK
    auto r1 = foos[i];
    auto r2 = [EnumMembers!Foo][i]; // Error: array literal in @nogc
}

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-10-06T17:26:58Z

A case (from Issue 13576 ):


immutable int[] a;
static this() @nogc {
    a = [1];
}
void main() {}


dmd 2.067alpha gives:

temp.d(3,9): Error: array literal in @nogc function _staticCtor1 may cause GC allocation

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-10-06T17:27:40Z

*** Issue 13576 has been marked as a duplicate of this issue. ***

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-10-31T10:27:14Z

Another common case where I'd like the compiler to avoid GC-allocations:

void main() @nogc {
    immutable int[4] a1 = [1, 2, 4, 5];
    size_t i = 2;
    immutable int[5] a2 = a1[0 .. i] ~ 3 ~ a1[i .. $];
}


Currently you have to write this more bug-prone code and the 'a2' variable can't be immutable:

void main() @nogc {
    immutable int[4] a1 = [1, 2, 4, 5];
    size_t i = 2;
    int[5] a2 = void;
    a2[0 .. i] = a1[0 .. i];
    a2[2] = 3;
    a2[i + 1 .. $] = a1[i .. $];
}

[dlangBugzillaToGithub]

nick (@ntrel) commented on 2024-07-22T13:33:15Z

Code in comment #0 and comment #12 now compile.
Comment #13 and comment #19 do not.

[dlangBugzillaToGithub]

nick (@ntrel) commented on 2024-11-29T13:47:56Z

Allowing comment #13 code depends on fixing Issue 20712.

> and comment #19 do not.

I meant comment #15 does not:

>     immutable int[5] a2 = a1[0 .. i] ~ 3 ~ a1[i .. $];

I don't see how that could be allowed because `i` is a runtime value, so the compiler has to make a GC array allocation (at least in the general case).