Ineffecient codegen for loops

[chuggafan]

I'm investigating memcpy speedups and am going to base my code on modifications to output from the compiler (as a baseline), I'm reading the output of this specific function:

void* memcpy_basic(void* s1, const void* s2, size_t sz)
{
    for (size_t i = 0; i < sz; i++)
    {
        ((char*)s1)[i] = ((const char*)s2)[i];
    }
    return s1;
}

The assembly produced is:

[global _memcpy_basic]
; memcpy_basic
_memcpy_basic:
        push    ebx
        push    esi
        push    edi
L_1:
        mov     esi,dword [esp+0ch+0ch]
        mov     edx,dword [esp+08h+0ch]
        mov     eax,dword [esp+04h+0ch]
; Line 14:     for (size_t i = 0; i < sz; i++) 
L_10:
        xor     ebx,ebx
        cmp     ebx,esi
        jnc     L_6
L_4:
; Line 15:     { 
; Line 16:         ((char*)s1)[i] = ((const char*)s2)[i]; 
        mov     edi,ebx
        mov     cl,byte [edx+ebx]
        mov     byte [eax+ebx],cl
; Line 17:     } 
L_7:
        mov     ebx,edi
        inc     ebx
L_5:
        cmp     ebx,esi
        jc      L_4
L_6:
; Line 18:     return s1; 
; Line 19: } 
L_2:
        pop     edi
        pop     esi
        pop     ebx
        ret

For some reason every loop iteration ebx needs to be saved against edi, then restored, but ebx is never used in such a way to warrant this.
Something with the loop optimizer isn't inspecting between the two blocks of L_4 and L_7 and noticing that EBX is only incremented and not used, so the extra movs are wasted.

I don't know where that is coming up, but when I dump the icds:

; Unoptimized
L_4:
	DBG Block START
; Line 15:	    { 

	DBG Block START
; Line 16:	        ((char*)s1)[i] = ((const char*)s2)[i]; 

	T3.A =   _s2:LINK(8).A
	T2.UI =   _i:LINK(0).UI
	T4.I =   T2.UI
	T5.A = T3.A + T4.I
	T6.C =   *(T5).A.C
	T7.A =   _s1:LINK(4).A
	T8.A = T7.A + T4.I
	*(T8).A.C =   T6.C
; Line 17:	    } 

	DBG Block END
	DBG Block END
	BLOCK 5

L_7:
	T2.UI =   _i:LINK(0).UI
	T9.UI = T2.UI + #1.UI
	_i:LINK(0).UI =   T9.UI
	DBG Block END
	BLOCK 6

L_5:
	T1.UI =   _sz:LINK(12).UI
	T2.UI =   _i:LINK(0).UI
	CONDGO	L_4:PC ; T2.UI U< T1.UI
	BLOCK 7

L_4:
	DBG Block START
; Line 15:	    { 

	DBG Block START
; Line 16:	        ((char*)s1)[i] = ((const char*)s2)[i]; 

	T10(EDI).UI =   T12(EBX).UI
	T9(CL).C =   *(T2(EDX) + T12(EBX)).A.C
	*(T7(EAX) + T12(EBX)).A.C =   T9(CL).C
; Line 17:	    } 

	DBG Block END
	DBG Block END
	BLOCK END
	BLOCK 5

L_7:
	T12(EBX).UI = T10(EDI).UI + #1.UI
	DBG Block END
	BLOCK END
	BLOCK 6
L_5:
	T13(EDI).UI =   T1(ESI).UI
	T14(ECX).UI =   T12(EBX).UI
	CONDGO	L_4:PC ; T14(ECX).UI U< T13(EDI).UI
	BLOCK END
	BLOCK 7

To me, this looks like a redundancy pass wasn't had on that assignment and reassignment.
I have very little idea about the optimizer internals here, so I don't think I'd be too much of help outside of this identification of "What's going on over here?"

[LADSoft]

i hadnt noticed that one before... will see what I can do.

[chuggafan]

Another weird one that has come up during this:

#include <stdint.h>
inline void* memmove_backwards_basic(void* s1, const void* s2, size_t sz)
{

    while (sz > 0)
    {
        sz--;
        ((char*)s1)[sz] = ((const char*)s2)[sz];
    }
    return s1;
}
void* memmove_backwards(void* s1, const void* s2, size_t sz)
{
    if (sz < 256)
    {
        return memmove_backwards_basic(s1, s2, sz);
    }
    asm
    {
        mov esi, [s2];
        mov edi, [s1];
        mov ecx, [sz];
        std;
        rep movsb;
        cld;
    }
    return s1;
}

occ /S test.c
produces:

section code
[global _memmove_backwards]
; memmove_backwards
_memmove_backwards:
; Line 12: void* memmove_backwards(void* s1, const void* s2, size_t sz) 
        push    ecx
        push    ecx
        push    ecx
        push    ebx
        push    esi
        push    edi
L_1:
; ...omitted for brevity...
        rep movsb
; Line 25:         cld; 
        cld
; Line 26:     } 
; Line 27:     return s1; 
        mov     eax,dword [esp+04h+018h]
; Line 28: } 
L_2:
        pop     edi
        pop     esi
        pop     ebx
        pop     ecx
        pop     ecx
        pop     ecx
        ret

The ICD2 section that's relevant looks like this:

_memmove_backwards:
; Line 12:	void* memmove_backwards(void* s1, const void* s2, size_t sz) 


	BLOCK 1
	PROLOGUE	#80000000000000C8.UI,#C.UI
	BLOCK END
	BLOCK 2

L_1:
	DBG Block START
; Line 14:	    if (sz < 256) 

	DBG Block START
	T9(EAX).UI =   _sz:LINK(12).UI
	CONDGO	L_4:PC ; T9(EAX).UI U>= #100.UI
	BLOCK END
	BLOCK 3
	DBG Block START

No idea how that changes into pushing and popping ECX 3 times.

Also, a note for future "optimization work" is that we can move the size check outside of the function and then just jmp to memmove_backwards_basic before even pushing to the stack, such a move should be easy to do (Quick condition check without calls to a stack-object's raw value? Promote BB infront of the Prologue and convert the call to a jmp if it's being returned immediately out of the BB, no need to generate a return statement as our return address doesn't change, no idea how easy this is to implement especially since assembly-containing functions are optimization-disabled here, but for other cases this can be more efficient).

[LADSoft]

sorry for the delays... i hope to get to this one soon. I found out that my last inclusion on the main line resulted in a bunch of build failures and I've been slowly working on fixing it... i can't spend as much time because now I'm back to real life lol...

I looked briefly at the libcxx tests. A lot are failing... i hope to get to that as soon as I resolve the issues in this issue...

The deal with the 'push ecx' is it is reserving space for local variables. This is meant to be some sort of optimization over sub esp,12.... occ has a problem where it sometimes reserves space for unused variables. Another thing I suppose I ought to get serious about fixing sigh....

[chuggafan]

Looking at the Agner Fog instruction tables, push ecx is outright slower in all cases from just doing the sub, would it be alright during this optimization pass to just outright delete the push ecx stack reservation codegen as part of this?

[LADSoft]

hm that is what i get for never looking at cycle counts lol.... yeah i'll fix that too.

[chuggafan]

It makes sense when I stop and think especially, push accesses main memory vs sub which doesn't require the extra fetch or even arguably cache hit.

[LADSoft]

i did fix the push ecx part of this but haven't pushed it yet...

[chuggafan]

I actually included that ecx fix as part of #1112 but I can drop off that part and merge your work on it ;)
My work at the moment is stalling on strlen, I'm going to be less able to work on that this week, I'm probably going to go take a look at glibc's implementation of memmove and memset and see what I can take from there, because the backwards copy loop is still going to be a slowdown for the memmove impl in #1112

[LADSoft]

sorry i ddn't realize you were doing that or i would have just let it be. I think it is great if you can fix things like this!