Bug 13381 – Two cases of array literal that can be stack-allocated

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

I agree.

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) {} }

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

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

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

(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

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

(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

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

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

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

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 }

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

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

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 .. $]; }

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

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

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/18874 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB