• d-bugmail puremagic.com (160/160) Nov 29 2013 https://d.puremagic.com/issues/show_bug.cgi?id=11643

d-bugmail puremagic.com writes:

https://d.puremagic.com/issues/show_bug.cgi?id=11643

           Summary: Loop-invariant code motion optimization for
                    associative array literals
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



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

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------