Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is there three leal instructions for this IA32 assembly code?

I compiled this C function:

int calc(int x, int y, int z) {
   return x + 3*y + 19*z;
}

And I got this in calc.s, and I am annotating what is happening:

        .file   "calc.c"
        .text
.globl calc
        .type   calc, @function
calc:
        pushl   %ebp                    //Save paramaters
        movl    %esp, %ebp              //Move stack pointer into %ebp
        movl    12(%ebp), %eax          //Move y into %eax
        movl    16(%ebp), %ecx          //Move z into %ecx
        leal    (%eax,%eax,2), %eax     //%eax = 3*y
        addl    8(%ebp), %eax           //%eax = x+3y
        leal    (%ecx,%ecx,8), %edx     // ?
        leal    (%ecx,%edx,2), %edx     // ?
        addl    %edx, %eax              //%eax = (x+3*y)+(19*z)
        popl    %ebp                    //Pop the previous pointer
        ret
        .size   calc, .-calc
        .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
        .section        .note.GNU-stack,"",@progbits

I understand everything up to the last two leal instructions. Why do you need two leal instructions for 19*z whereas 3*y is accomplished in one instruction.

like image 900
MeesterMarcus Avatar asked Mar 19 '14 16:03

MeesterMarcus


3 Answers

leal is a way to perform a multiplication by a small constant on a cheap, if the constant is a power of two plus one. The idea is that leal without an offset is equivalent to "Reg1 = Reg2+Reg3*Scale". If Reg2 and Reg3 happen to match, that means "Reg1=Reg2*(Scale+1).

leal only supports scale factors up to 8, so to multiply by 19, you need two.

The effect of

leal   (%eax,%eax,2), %eax

is:

eax = eax + eax*2

which is to say, multiplication by three.

The second two leals together perform multiplication by 19:

leal    (%ecx,%ecx,8), %edx     // edx = ecx+ecx*8
leal    (%ecx,%edx,2), %edx     // edx = ecx+edx*2 (but edx is already z*9)
like image 189
Seva Alekseyev Avatar answered Sep 20 '22 19:09

Seva Alekseyev


leal    (%ecx,%ecx,8), %edx # edx = ecx + 8*ecx = 9*ecx = 9 * z
leal    (%ecx,%edx,2), %edx
# edx = ecx + 2*edx = ecx + 2 * (ecx + 8*ecx) = z + 2 * 9 * z = 19 * z

The reason for this that the lea instruction uses add and bitshifts and is faster then using mul for integer multiplication. Lea is limited though to multiplication factors of 1, 2, 4 and 8 - thus two instructions.

like image 38
Sergey L. Avatar answered Sep 23 '22 19:09

Sergey L.


lea serves a double purpose one is to calculate addresses but it can also be used for arithmetic with some constraints, as you observe with your code. Two calls are needed because the scalar multiplier of lea is limited to 1, 2, 4 or 8 which means to get your multiplication by 19 requires two calls to lea:

[...]The scalar multiplier is limited to constant values 1, 2, 4, or 8 for byte, word, double word or quad word offsets respectively. This by itself allows for multiplication of a general register by constant values 2, 3, 4, 5, 8 and 9,[...]

so in your case you have:

leal    (%ecx,%ecx,8), %edx     // edx = ecx + ecx*8 which is z*8 + z = z*9
leal    (%ecx,%edx,2), %edx     // edx = ecx + edx*2 which gives us (z*9)*2 + z
                                // for a total of 19z
like image 36
Shafik Yaghmour Avatar answered Sep 24 '22 19:09

Shafik Yaghmour