Going from Assembly to C code

Question

This is in AT&T syntax

.global bar
.type bar, @function

bar:

pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $20, %esp
movl 8($ebp), %ebx
movl $1, %eax
cmpl $1, %ebx
jle .L3
leal -1(%ebx), %eax  //subtracts 1 from ebx and stores into eax
movl %eax, (%esp)    //putting on stack frame
call bar             //recursive call
addl %ebx, %eax      // adds %ebx and %eax


.L3                  //returns %eax
addl $20, %esp
popl %ebx
popl %ebp
ret                  //end of bar

So what I think happens here is basically it checks if %ebx is <= 1 and if it is, it returns one. otherwise, it calls bar with x--;

So my C code is:

int bar (int x)
{
if (x<= 1)
return 1;
else
return x + bar(x-1);
}

The recursive call is really tricking me up here. I realize it calls bar with the new %eax register (which basically becomes x-1). So does it just return the sum of the numbers?

Answer 1

I'd annotate it this way:

bar:                     // bar() {
    pushl %ebp           //   function prologue
    movl %esp, %ebp      //
    pushl %ebx           //
    subl $20, %esp       //
    movl 8($ebp), %ebx   //   %ebx = x
    movl $1, %eax        //   %eax = 1
    cmpl $1, %ebx        //   if (x > 1)
    jle .L3              //   {
    leal -1(%ebx), %eax  //     %eax = x - 1
    movl %eax, (%esp)    //     put (x - 1) on stack
    call bar             //     %eax = bar(x - 1)
    addl %ebx, %eax      //     %eax += x
.L3                      //   }
    addl $20, %esp       //   function epilogue
    popl %ebx            //
    popl %ebp            //
    ret                  //   return %eax
                         // }

So the C looks quite equivalent to what you posted:

int bar (int x)
{
  if (x > 1)
    return bar(x - 1) + x;

  return 1;
}

---

For historical interest: I compiled your original (incorrect) C code using clang -m32 -S and after "optimizing" slightly by hand to eliminate a store/load pair, I got something resembling your assembly code, but it was pretty clear you had it wrong at that moment. You fixed it since then.

Answer 2

int bar(int x)
{
if (x<= 1)
return 1;
else
return x+bar(x-1);
}

sums x to 1 in ascending order