Decompiler Design - Frame-less Functions
Prev: Stack Frames
Dealing with framed functions makes it easy for a decompiler to identify local variables and parameters. Unfortunately, optimizing compiler don't generate a frame pointer for most functions. After all, the main reason for using a frame pointer is to help a debugger to traverse the list of active functions to tell the user how the current function was reached, and how to easily locate local variables and parameters (as well as registers that are saved across function calls).
The reason that a compiler can forget about the frame pointer is that the compiler knows exactly how to access each local variable or parameter at every point in the function. So, let's see the difference in code generated between framed functions and frame-less functions:
PUSH FP SP -= #local_size
FP = SP
SP -= #local_size int var1;
// access local var1
R1 = FP[-8] R1 = SP[#local_size-8]
PUSH R1 PUSH R1
// access local var1 again
R2 = FP[-8] R2 = SP[#local_size-8+4]
PUSH R2 PUSH R2
func() func() func(var1,var1);
// deallocate parameters
SP += 8 SP += 8
SP = FP SP += #local_size }
Detecting the size of the locals is fairly easy even for frame-less functions. Just look for the allocation of the local variables area by the "SP -= #local_size" instruction in the prologue of the function, and a corresponding de-allocation of the local variables in the epilogue of the function.
But detecting local variables is more difficult. When using a frame pointer, the expression used to access a local variable or parameter is always the same, regardless of how many parameters are being passed to a function being called, because the frame pointer register is not affected by the PUSH instructions used to pass the parameters.
This is not true for frame-less functions: the expression used to access the same local depends on how the stack pointer has changed since the start of the function. This is because the stack pointer is used both to access the variables and also to pass parameters to other functions. Therefore, for frame-less functions, a decompiler must compute a stack pointer adjustment factor for each instruction, to be added to the initial location of each local variable.
Note that this has to happen even when computing the location of the variables themselves!
So we cannot use the same algorithm we used to create local variables and parameters for framed functions in the presence of frame-less functions. For example:
Instruction stream SP adjustment
variable var. location
SP -= #local_size 0 SP's value = &CFA
R1 = SP[#local_size-8] 0 var1 CFA - 8
R1 = SP[#local_size-4] 4 var1 CFA - 8
R1 = SP[#local_size-4] 8 var2 CFA - 12
SP += 8
R1 = SP[#local_size-8] 0 var1 CFA - 8
We use here the concept of CFA, as defined in the DWARF debug format, to mean the value of the stack pointer at the entry point of the function. This is the value we use as reference throughout the function, and the value we use to identify variables locations. So we store var1 as having location "CFA - 8", and var2 as having location "CFA - 12". With this approach, we can easily determine whether a variable is a local variable or an incoming parameter, since the value of the offset to CFA is negative for local variables, and positive for parameters, just as we had for the framed function case.
Converting locations in the instruction stream is easily performed with the following algorithm:
sp_adjust = 0
for each instruction i in block
if i.opcode == Push
sp_adjust += i.operand_size
if i.opcode == Pop
sp_adjust -= i.operand_size
if block == entry_block
local_size = i.op2.value
sp_adjust -= i.op2.value
sp_adjust += i.op2.value
i.result = replaceSPreferences(i.result)
i.op1 = replaceSPreferences(i.op1)
i.op2 = replaceSPreferences(i.op2)
Node replaceSPreferences(Node n)
if n == null
n.op1 = replaceSPreferences(n.op1)
n.op2 = replaceSPreferences(n.op2)
n = new AddNode(CFA, local_size - sp_adjust)
n = new SubNode(CFA, local_size - sp_adjust)
This algorithm is not perfect, as it makes a few assumptions:
Due to this limitations, it is not always possible to reconstruct local variables and parameters for frame-less functions. Fortunately, this kind of function is not common (except maybe in gcc, which makes plenty of use of "alloca(size)" calls), so it's possible to mark these functions and ask the user to provide additional information interactively.
Next: Saved Register