{"id":101046,"date":"2019-02-10T23:00:00","date_gmt":"2019-02-11T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=101046"},"modified":"2019-03-18T11:19:53","modified_gmt":"2019-03-18T18:19:53","slug":"20190211-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20190210-00\/?p=101046","title":{"rendered":"The Intel 80386, part 16: Code walkthrough"},"content":{"rendered":"

Let’s put into practice what we’ve learned so far by walking through a simple function and studying its disassembly. <\/p>\n

\n#define _lock_str(s)                    _lock(s+_STREAM_LOCKS)\n#define _unlock_str(s)                  _unlock(s+_STREAM_LOCKS)\n\nextern FILE _iob[];\n\nint fclose(FILE *stream)\n{\n    int result = EOF;\n\n    if (stream->_flag & _IOSTRG) {\n        stream->_flag = 0;\n    } else {\n        int index = stream - _iob;\n        _lock_str(index);\n        result = _fclose_lk(stream);\n        _unlock_str(index);\n    }\n\n    return result;\n}\n<\/pre>\n
This is a function from the C runtime library, so the functions use the __cdecl<\/code> calling convention. This means that the parameters are pushed right-to-left, and the caller is responsible for cleaning them from the stack. <\/p>\n
\n_fclose:\n    push    ebx\n    push    esi\n    push    edi\n<\/pre>\n
This code was compiled back in the days when frame pointer omission was fashionable. The function does not create a traditional stack frame with the ebp<\/var> register acting as frame pointer. <\/p>\n
The 80386 calling convention says that the ebx<\/var>, esi<\/var>, the edi<\/var>, and ebp<\/var> registers must be preserved across the call. <\/p>\n
\n    mov     esi,dword ptr [esp+10h] ; esi = stream\n<\/pre>\n
We will be using the stream<\/var> variable a lot, so we’ll load it into a register for convenient access. <\/p>\n
\n; int result = EOF;\n    mov     edi,0FFFFFFFFh          ; edi = result = EOF\n<\/pre>\n
The other variable is result<\/var>, which we will keep in the edi<\/var> register, and we set it to its initial value of −1. This is a straight MOV<\/code> instruction, which is five-byte encoding (one opcode byte plus a four-byte immediate). A smaller encoding would have been or edi, -1<\/code>, which uses two bytes for the opcode and one for the 8-bit signed immediate. But the smaller encoding comes at a perfornance cost because it creates a false dependency on the edi<\/var> register. (Mind you, the 80386 did not have out-of-order execution, so dependencies really aren’t a factor yet.) <\/p>\n
\n; if (stream->_flag & _IOSTRG) {\n    test    byte ptr [esi+0Ch],40h  ; is this a string?\n    je      not_string              ; N: then need a true flush\n<\/pre>\n
Even though _flag<\/var> is a 32-bit field, we use a byte test to save code size. This takes advantage of the fact that testing a single bit can be done by testing a single bit in a 32-bit field, or by testing a single bit in an 8-bit subfield. The _flag<\/var> field is at offset 0Ch<\/code>, and the value of _IOSTRG<\/code> is 0x40<\/code>, so the bit we want is in the first byte. <\/p>\n
We learned some time ago that this size optimization defeats the store-to-load forwarder<\/a>, but the 80386 didn’t have a store-to-load forwarder, so that wasn’t really a factor. <\/p>\n
\n; stream->_flag = 0;\n    mov     dword ptr [esi+0Ch],0\n<\/pre>\n
Again, the compiler chooses a full 32-bit immediate instead of using a smaller instruction. An alternative would have been and dword ptr [esi+0Ch], 0<\/code>, using a sign-extended 8-bit immediate instead of a 32-bit immediate, but at a cost of incurring a read-modify-write rather than simply a write. <\/p>\n
\n; return result;\n    mov     eax,edi                 ; eax = return value\n    pop     edi\n    pop     esi\n    pop     ebx\n    ret\n<\/pre>\n
The compiler chose to inline the common return<\/code> instruction into this branch of the if<\/code> statement. The value being returned is in the result<\/var> variable, which we had enregistered in the edi<\/var> register. The return value goes in the eax<\/var> register, so we move it there. And then we restore the registers we had saved on the stack and return to the caller. Since this function uses the __cdecl<\/code> calling convention, the function does no stack cleanup; it is the caller’s responsibility to clean the stack. <\/p>\n
\n    nop\n<\/pre>\n
This nop<\/code> instruction is padding to bring the next instruction, a jump target, to an address that is a multiple of 16. The 80386 fetches instructions in 16-byte chunks, and putting jump targets at the start of a 16-byte chunk means that all of the fetched bytes are potentially executable. <\/p>\n
\nnot_string:\n; int index = stream - _iob;\n    mov     ebx,esi                 ; ebx = stream\n    sub     ebx,77E243F0h           ; ebx = stream - _iob (byte offset)\n    sar     ebx,5                   ; ebx = stream - _iob (element offset)\n<\/pre>\n
This sequence of instructions calculates the value for the index<\/var> local variable, which the compiler chose to enregister in the ebx<\/var> register. We start with the value in the esi<\/var> register, which is the stream<\/var> variable. Next, we subtract the offset of the _iob<\/var> variable, which is a global variable, so its address looks like a constant in the code stream. We then take that byte offset and shift it right by 5, which means dividing by 32, which is the size of a FILE<\/var> structure in this particular implementation. The result now sits in the ebx<\/var> register. <\/p>\n
\n; _lock_str(index) ⇒ _lock(index+_STREAM_LOCKS)\n    add     ebx,19h                 ; add _STREAM_LOCKS\n    push    ebx                     ; the sole parameter\n    call    _lock                   ; call the function\n    add     esp,4                   ; clean stack arguments\n<\/pre>\n
The _lock_str<\/var> macro is a wrapper around the _lock<\/var> function. We add STREAM_<\/var>LOCKS<\/var>, which happens to be 25, or 0x19<\/code>, and the push it onto the stack as the sole parameter for the _lock<\/var> function. Since this is a __cdecl<\/code> function, it is the caller’s responsibility to clean the stack, so we add 4 (the number of bytes of parameters) to the esp<\/var> register to drop them from the stack. <\/p>\n
\n; result = _fclose_lk(stream)\n    push    esi                     ; the sole parameter\n    call    _fclose_lk              ; call the function\n    add     esp,4                   ; clean stack arguments\n    mov     edi,eax                 ; save in edi = result\n<\/pre>\n
Another function call: We push the sole parameter, call the function, and clean the stack. The return value was placed in the eax<\/var> register, so we move it into the edi<\/var> register, which we saw represents the result<\/var> variable. <\/p>\n
\n; _unlock_str(index) ⇒_unlock(index+_STREAM_LOCKS)\n    push    ebx                     ; the sole parameter\n    call    _unlock                 ; call the function\n    add     esp,4                   ; clean stack arguments\n<\/pre>\n
The compiler realized it could pull out the common subexpression s+_STREAM_<\/var>LOCKS<\/var> and stored the value of that subexpression in the ebx<\/var> register. It could therefore push the precomputed value (helpfully saved in the ebx<\/var> register) as the parameter for the _lock<\/vAR> function. <\/p>\n
\n; return result;\n    mov     eax,edi                 ; eax = return value\n    pop     edi\n    pop     esi\n    pop     ebx\n    ret\n<\/pre>\n
And this is the same code we saw last time. The return value (result<\/var>) is moved to the eax<\/var> register, which is where the __cdecl<\/code> calling convention places it. We then restore the registers we had saved at entry and return to our caller, leavving our caller to clean the stack parameters. <\/p>\n
The resulting function size is 81 bytes. <\/p>\n
Okay, now let’s see how we could optimize this function further. Let’s look closely at the calculation of index + _STREAM_<\/var>LOCKS<\/var>. <\/p>\n
\n    mov     ebx,esi                 ; ebx = stream\n    sub     ebx,77E243F0h           ; ebx = stream - _iob (byte offset)\n    sar     ebx,5                   ; ebx = stream - _iob (element offset)\n    add     ebx,19h                 ; add _STREAM_LOCKS\n<\/pre>\n
The first thing you might think of is combining the first two instructions into a single LEA<\/code> instruction: <\/p>\n
\n    lea     ebx,[esi+881dbc10h]     ; ebx = stream - _iob (byte offset)\n<\/pre>\n
The LEA<\/code> instruction lets us perform an addition operation in a single instruction by taking advantage of the effective address computation circuitry in the memory unit. The operation we want to perform is subtraction of a constant, which we can transform into an addition of the negative of that constant. <\/p>\n
Unfortunately, the trick doesn’t work in this case because the “constant” is a relocatable address, and there is no loader fixup type for “negative of the address of a variable.” <\/p>\n
But all is not lost. There’s another trick we could use: Fold in the subsequent addition. <\/p>\n\n\n\n\n\n
ebx<\/var><\/td>\n= ((esi<\/var> − 77E243F0h) >> 5) + 19h<\/td>\n<\/tr>\n
<\/td>\n= ((esi<\/var> − 77E243F0h) >> 5) + (320h >> 5)<\/td>\n<\/tr>\n
<\/td>\n= (esi<\/var> − 77E243F0h + 320h) >> 5 <\/tr>\n
<\/td>\n= (esi<\/var> − 77E240D0h) >> 5 <\/tr>\n<\/table>\n
Another way to do this calculation: <\/p>\n\n\n\n\n
adjusted_index <\/code><\/td>\n= stream - _iob + 0x19<\/code><\/td>\n<\/tr>\n
<\/td>\n= stream - (_iob - 0x19)<\/code><\/td>\n<\/tr>\n
<\/td>\n= stream - &_iob[-0x19]<\/code><\/td>\n<\/tr>\n<\/table>\n
Either way, the result is this: <\/p>\n
\n    mov     ebx,esi                 ; ebx = stream\n    sub     ebx,77E240D0h           ; ebx = stream - &_iob[-0x19] (byte offset)\n    sar     ebx,5                   ; ebx = stream - &_iob[-0x19] (element offset)\n<\/pre>\n
Another observation is that stream<\/var> and result<\/var> do not have overlapping useful lifetimes. The useful lifetime of result<\/var> doesn’t start until it receives the value from _fclose_lk<\/var>. Prior to that, its value is known at compile time to be EOF<\/code>, so there’s no need to devote a register to it. <\/p>\n
And we can combine the add esp, 4<\/code> with the subsequent push<\/code> (which decrements the esp<\/var> register) by simply storing the new value into the top-of-stack slot. <\/p>\n
The case of a string-based stream does not use the ebx<\/var> register, so we can use a technique know as shrink-wrapping<\/i>, where we start with one stack frame, and then expand it to a larger one on certain code paths. In this case, we start by saving only the esi<\/var> register, and then later save the ebx<\/var> register only if we realize that we need it. <\/p>\n
A simple size\/speed optimization (in favor of size) is to use the pop<\/code> instruction to pop a value off the stack (and ignore it). This replaces a three-byte add esp,4<\/code> with a one-byte register pop<\/code>. <\/p>\n
A very aggressive size optimization would be to replace the two-byte instructions mov eax, r<\/code> or mov r, eax<\/code> with the one-byte xchg eax, r<\/code> instruction. This assumes you need to move the value into or out of the eax<\/var> register and you don’t care about the source any more. <\/p>\n
Finally, a string-based stream is quite uncommon (and certainly the case of closing a string-based stream), so we’ll make that the out-of-line case, and we won’t bother optimizing the fetch of the jump target for the same reason. <\/p>\n
\n_fclose:\n    push    esi                     ; save register\n    mov     esi,dword ptr [esp+0Ch] ; esi = stream\n    test    byte ptr [esi+0Ch],40h  ; Is this an _IOSTRG?\n    jnz     is_string                  \n\n    push    ebx                     ; shrink-wrap\n    mov     ebx,esi\n    sub     ebx,77E240D0h           ; ebx = stream - &_iob[-0x19] (byte offset)\n    sar     ebx,5                   ; ebx = index + _STREAM_LOCKS\n    push    ebx\n    call    _lock                   ; call the function\n\n    mov    [esp],esi                ; parameter for _fclose_lk\n    call   _fclose_lk               ; close the stream\n\n    mov    [esp],ebx                ; parameter for _unlock\n    mov    ebx,eax                  ; ebx = result\n    call   _unlock\n\n    pop    eax                      ; clean the stack once\n    mov    eax,ebx                  ; eax = result\n    pop    ebx\n    pop    esi\n    ret\n\nis_string:\n    mov    dword ptr [esi+0Ch],0    ; stream->_flag = 0\n    or     eax,-1                   ; return EOF\n    pop    esi\n    ret\n<\/pre>\n
This reduces the function size to 65 bytes. <\/p>\n
Yet another trick is to pre-push the parameters for multiple function calls. <\/p>\n
\n_fclose:\n    mov     ecx,dword ptr [esp+8]   ; ecx = stream\n    test    byte ptr [ecx+0Ch],40h  ; Is this an _IOSTRG?\n    jnz     is_string               ; Y: handle strings out of line\n\n    push    ebx                     ; shrink-wrap\n    mov     ebx,ecx\n    sub     ebx,77E240D0h           ; ebx = stream - &_iob[-0x19] (byte offset)\n    sar     ebx,5                   ; ebx = index + _STREAM_LOCKS\n    push    ecx                     ; push for _fclose_lk\n    push    ebx                     ; push for _lock\n    call    _lock                   ; call the function\n    pop     eax                     ; discard arg to _lock\n    call    _fclose_lk              ; close the stream\n    mov     dword ptr [esp],ebx     ; parameter for _unlock\n    mov     ebx,eax                 ; save result\n    call    _unlock\n    pop     eax                     ; discard arg to _unlock\n    mov     eax,ebx                 ; recover result\n    pop     ebx\n    ret\n\nis_string:\n    mov    dword ptr [ecx+0Ch],0    ; stream->_flag = 0\n    or     eax,-1                   ; return EOF\n    ret\n<\/pre>\n
This brings us down to 57 bytes. <\/p>\n
If we abandon the idea of enregistering the result<\/var>, we can do this: <\/p>\n
\n_fclose:\n    mov     ecx,dword ptr [esp+8]   ; ecx = stream\n    test    byte ptr [ecx+0Ch],40h  ; Is this an _IOSTRG?\n    jnz     is_string               ; Y: handle strings out of line\n\n    mov     eax,ecx\n    sub     eax,77E240D0h           ; ebx = stream - &_iob[-0x19] (byte offset)\n    sar     eax,5                   ; ebx = index + _STREAM_LOCKS\n    push    ecx                     ; garbage (for future result)\n    push    eax                     ; push for _unlock\n    push    ecx                     ; push for _fclose_lk\n    push    eax                     ; push for _lock\n    call    _lock                   ; call the function\n    pop     eax                     ; discard arg to _lock\n    call    _fclose_lk              ; close the stream\n    mov     dword ptr [esp+0Ch],eax ; save result\n    pop     eax                     ; discard arg to _lock\n    call    _unlock\n    pop     eax                     ; discard arg to _unlock\n    pop     eax                     ; recover result\n    ret\n\nis_string:\n    mov    dword ptr [ecx+0Ch],0    ; stream->_flag = 0\n    or     eax,-1                   ; return EOF\n    ret\n<\/pre>\n
But this comes out to 59 bytes. <\/p>\n
Next time<\/a>, a bonus chapter on future developments to this architecture. <\/p>\n","protected":false},"excerpt":{"rendered":"
Putting the information into practice.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[2],"class_list":["post-101046","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-history"],"acf":[],"blog_post_summary":"
Putting the information into practice.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/101046","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=101046"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/101046\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=101046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=101046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=101046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}