D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 11643 - Loop-invariant code motion optimization for associative array literals
Summary: Loop-invariant code motion optimization for associative array literals
Status: RESOLVED DUPLICATE of issue 4453
Alias: None
Product: D
Classification: Unclassified
Component: dmd (show other issues)
Version: D2
Hardware: All All
: P2 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-11-29 05:06 UTC by bearophile_hugs
Modified: 2022-08-16 11:14 UTC (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2013-11-29 05:06:05 UTC
A common idiom in scripting languages like Python is to define and use in-place associative arrays. Thanks to the handy D associative array literals this idiom is usable in D too:


void main() {
    import core.stdc.stdio: printf;
    foreach (immutable i; 0 .. 10)
        printf("%d ", [1: 10, 2: 20].get(i, -1));
}


Output:
-1 10 20 -1 -1 -1 -1 -1 -1 -1


Unfortunately the associative array is rebuilt at every loop (dmd 2.065alpa not optimized built):


__Dmain:
L0:     enter   01Ch,0
        push    EBX
        push    ESI
        mov dword ptr -01Ch[EBP],0
LD:     cmp dword ptr -01Ch[EBP],0Ah
        jge L7F
        mov EAX,-01Ch[EBP]
        mov -018h[EBP],EAX
        push    dword ptr -018h[EBP]
        mov ECX,offset FLAT:_D4temp4mainFZv12__dgliteral1MFNaNbNfZi
        xor EBX,EBX
        push    ECX
        push    EBX
        mov EDX,1
        mov -014h[EBP],EDX
        mov dword ptr -010h[EBP],2
        mov dword ptr -0Ch[EBP],0Ah
        mov dword ptr -8[EBP],014h
        lea ESI,-0Ch[EBP]
        push    ESI
        push    2
        lea ECX,-014h[EBP]
        mov EAX,2
        push    ECX
        push    EAX
        mov EBX,offset FLAT:_D12TypeInfo_Hii6__initZ
        push    EBX
        call    near ptr __d_assocarrayliteralTX
        add ESP,014h
        mov -4[EBP],EAX
        lea EAX,-4[EBP]
        call    near ptr _D6object26__T16AssociativeArrayTiTiZ16AssociativeArray3getMFNaiLiZi
        push    EAX
        mov EDX,offset FLAT:_DATA
        push    EDX
        call    near ptr _printf
        add ESP,8
        inc dword ptr -01Ch[EBP]
        jmp short   LD
L7F:        xor EAX,EAX
        pop ESI
        pop EBX
        leave
        ret


Even compiling that code with ldc2 0.12.0, with -O (optimized build), the problem is still present:

__Dmain:
    pushl   %edi
    pushl   %esi
    subl    $24, %esp
    xorl    %esi, %esi
    leal    20(%esp), %edi
    .align  16, 0x90
LBB0_1:
    movl    $_.aaValuesStorage, 16(%esp)
    movl    $2, 12(%esp)
    movl    $_.aaKeysStorage, 8(%esp)
    movl    $2, 4(%esp)
    movl    $__D12TypeInfo_Hii6__initZ, (%esp)
    calll   __d_assocarrayliteralTX
    movl    %esi, 20(%esp)
    movl    %edi, 8(%esp)
    movl    %eax, (%esp)
    movl    $__D10TypeInfo_i6__initZ, 4(%esp)
    calll   __aaInX
    movl    $-1, %ecx
    testl   %eax, %eax
    je  LBB0_3
    movl    (%eax), %ecx
LBB0_3:
    movl    %ecx, 4(%esp)
    movl    $_.str, (%esp)
    calll   ___mingw_printf
    incl    %esi
    cmpl    $10, %esi
    jne LBB0_1
    xorl    %eax, %eax
    addl    $24, %esp
    popl    %esi
    popl    %edi
    ret
    


So I suggest to introduce some loop-invariant code motion optimization, and initialize the associative array only once out of the loop (dmd asm coming from modified code):

__Dmain:
L0:     enter   020h,0
        push    EBX
        push    ESI
        mov dword ptr -018h[EBP],1
        mov dword ptr -014h[EBP],2
        mov dword ptr -010h[EBP],0Ah
        mov dword ptr -0Ch[EBP],014h
        lea EAX,-010h[EBP]
        push    EAX
        push    2
        lea ECX,-018h[EBP]
        mov EBX,2
        push    ECX
        push    EBX
        mov EDX,offset FLAT:_D12TypeInfo_Hii6__initZ
        push    EDX
        call    near ptr __d_assocarrayliteralTX
        mov -020h[EBP],EAX
        mov dword ptr -8[EBP],0
        add ESP,014h
L4A:        cmp dword ptr -8[EBP],0Ah
        jge L7E
        mov ESI,-8[EBP]
        mov -4[EBP],ESI
        push    dword ptr -4[EBP]
        mov ECX,offset FLAT:_D4temp4mainFZv12__dgliteral1MFNaNbNfZi
        xor EAX,EAX
        push    ECX
        push    EAX
        lea EAX,-020h[EBP]
        call    near ptr _D6object26__T16AssociativeArrayTiTiZ16AssociativeArray3getMFNaiLiZi
        push    EAX
        mov EDX,offset FLAT:_DATA
        push    EDX
        call    near ptr _printf
        add ESP,8
        inc dword ptr -8[EBP]
        jmp short   L4A
L7E:        xor EAX,EAX
        pop ESI
        pop EBX
        leave
        ret
Comment 1 RazvanN 2022-08-16 11:14:04 UTC

*** This issue has been marked as a duplicate of issue 4453 ***