Question

Question: Can we use the tail-call optimization in this function? If no, explain why not. If yes, what is the difference in the number of executed instructions in f with and without the optimization?

Short answer

Yes, tail-call optimization can be implemented in this function. Only one instruction will be reduced with optimization.

Step-by-step solution

Determine the tail-call optimization

Tail call optimization will reduce the need for additional stack frames. This will make the program more efficient. Tail-call will make a call to a function, that contains another function that takes no return values and any additional stack space.

Determine whether that tail-call optimization can be used in the given function

Given function: (refer 2.33 and 2.34)

int f(int a, int b, int c, int d)

{

return func(func(a,b),c+d);

}

MIPS code:

f: addi $sp,$sp,-12

sw $ra,8($sp)

sw $s1,4($sp)

sw $s0,0($sp)

move $s1,$a2

move $s0,$a3

jal func

move $a0,$v0

add $a1,$s0,$s1

jal func

lw $ra,8($sp)

lw $s1,4($sp)

lw $s0,0($sp)

addi $sp,$sp,12

jr $ra

Yes, tail-call optimization can be used in the function for the second call to func. If it is implemented, then the registers $ra, $s0,$sp must be restored before the call.

This implementation will save only one instruction that denies the second function call is jr $ra.