Examining code generated by the Visual Studio C++ compiler, part 1 [duplicate]

Question

Possible Duplicate:
Why is such complex code emitted for dividing a signed integer by a power of two?

Background

I'm just learning x86 asm by examining the binary code generated by the compiler.

Code compiled using the C++ compiler in Visual Studio 2010 beta 2.

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.21003.01 for 80x86

C code (sandbox.c)

int mainCRTStartup()
{
    int x=5;int y=1024;
    while(x) { x--; y/=2; }
    return x+y;
}

Compile it using the Visual Studio Command Prompt

cl /c /O2 /Oy- /MD sandbox.c
link /NODEFAULTLIB /MANIFEST:NO /SUBSYSTEM:CONSOLE sandbox.obj

Disasm sandbox.exe in OllyDgb

The following starts from the entry point.

00401000 >/$ B9 05000000    MOV ECX,5
00401005  |. B8 00040000    MOV EAX,400
0040100A  |. 8D9B 00000000  LEA EBX,DWORD PTR DS:[EBX]
00401010  |> 99             /CDQ
00401011  |. 2BC2           |SUB EAX,EDX
00401013  |. D1F8           |SAR EAX,1
00401015  |. 49             |DEC ECX
00401016  |.^75 F8          \JNZ SHORT sandbox.00401010
00401018  \. C3             RETN

Examination

MOV ECX, 5          int x=5;
MOV EAX, 400        int y=1024;
LEA  ...            // no idea what LEA does here. seems like ebx=ebx. elaborate please.
                    // in fact, NOPing it does nothing to the original procedure and the values.

CQD                 // sign extends EAX into EDX:EAX, which here: edx = 0. no idea why.
SUB EAX, EDX        // eax=eax-edx, here: eax=eax-0. no idea, pretty redundant. 
SAR EAX,1           // okay, y/= 2
DEC ECX             // okay, x--, sets the zero flag when reaches 0.
JNZ ...             // okay, jump back to CQD if the zero flag is not set.

This part bothers me:

0040100A  |. 8D9B 00000000  LEA EBX,DWORD PTR DS:[EBX]
00401010  |> 99             /CDQ
00401011  |. 2BC2           |SUB EAX,EDX

You can nop it all and the values of EAX and ECX will remain the same at the end. So, what's the point of these instructions?

Answer 1

The whole thing

00401010  |> 99             /CDQ
00401011  |. 2BC2           |SUB EAX,EDX
00401013  |. D1F8           |SAR EAX,1

stands for the y /= 2. You see, a standalone SAR would not perform the signed integer division the way the compiler authors intended. C++98 standard recommends that signed integer division rounds the result towards 0, while SAR alone would round towards the negative infinity. (It is permissible to round towards negative infinity, the choice is left to the implementation). In order to implement rounding to 0 for negative operands, the above trick is used. If you use an unsigned type instead of a signed one, then the compiler will generate just a single shift instruction, since the issue with negative division will not take place.

The trick is pretty simple: for negative y sign extension will place a pattern of 11111...1 in EDX, which is actually -1 in 2's complement representation. The following SUB will effectively add 1 to EAX if the original y value was negative. If the original y was positive (or 0), the EDX will hold 0 after the sign extension and EAX will remain unchanged.

In other words, when you write y /= 2 with signed y, the compiler generates the code that does something more like the following

y = (y < 0 ? y + 1 : y) >> 1;

or, better

y = (y + (y < 0)) >> 1;

Note, that C++ standard does not require the result of the division to be rounded towards zero, so the compiler has the right to do just a single shift even for signed types. However, normally compilers follow the recommendation to round towards zero (or offer an option to control the behavior).

P.S. I don't know for sure what the purpose of that LEA instruction is. It is indeed a no-op. However, I suspect that this might be just a placeholder instruction inserted into the code for further patching. If I remember correctly, MS compiler has an option that forces the insertion of placeholder instructions at the beginning and at the end of each function. In the future this instruction can be overwritten by the patcher with a CALL or JMP instruction that will execute the patch code. This specific LEA was chosen just because it produces the a no-op placeholder instruction of the correct length. Of course, it could be something completely different.