When functions dissolve

by

A tail call occurs when a subroutine ends with a call to another subroutine. In high level language this happens in the following cases: 

void g();

void f() {
    g();
    return;
}

This is also a tail call, because we return what the other function returned: 

int g(int x);

int f() {
    return g(42);
}

This is not a tail call: after calling the function we need to multiply its result by some other number. we wait till then fact(n-1) Completes its execution, and then uses its results in other calculations. Note that in this example the function calls itself rather than another function, but this is unimportant. 

int fact( int n ) {
  if (n < 2) return 1;
  return n * fact(n-1);
}

At the assembly level, the tail call corresponds to the following pattern of instructions:

This pair of instructions is located in a function that we are going to call fThe control accesses this function from another function, say, f_caller,

Let’s follow the state of the stack through execution f_caller, f And otherFor this we expand it to include this code f_caller And other Work. 

f_caller:

...
   call f
    instruction> ; mark 4
...

f:            ; mark 1
  ...
  call other
  ret         ; mark 3
...
other:        ; mark 2
   ...
   ret
  • when we start executing f The stack holds the return address in f_caller (We reach mark 1).
  • when we call other holds return addresses for the stack f_callerThen f At the top (we reach mark 2).
  • subroutine other Return also, at this moment we only have the return address f_caller At the top of the pile (we reach mark 3).
  • subroutine f return, popping return address f_caller From the pile (we reach mark 4).

The last two steps were essentially popping two return addresses off the stack consecutively. It suggests that the first (return address). f) is useless and we don’t need to store it. We are really right.

call other The instruction is equivalent to a pair of pseudoinstructions: 

push rip    ; rip is the program counter register
jmp other

If we don’t need to push the return address fSo we can just replace this instruction jmp and get rid of one ret, 

f_caller:

...
   call f
    instruction>
...

f:
  ...
  jmp other
...
other:
   ...
   ret     ; will return directly to f_caller

subroutine other Basically the continuation of the subroutine becomes fwe pass by f To other Through a simple branching instruction.

Coming back to our example, we can rewrite it as: 

print_char:
   ...
   ret

print_newline:
    mov rdi, 0xA          ; code
    jmp print_char



Leave a Comment