Decompiler Design - Saved Registers
Prev: Frame-less Functions
The final part of the stack frame analysis involves the detection of saved registers.
Saved registers are those registers that are mandated by a certain calling convention to be preserved across function calls. This concept is very important for a compiler (and thus for a decompiler) to be able to allocate variables to registers and to avoid having to save to memory those registers whenever there is a call to a function that could have been generated by another compiler.
It is worth noting that different calling conventions define different sets of registers to be preserved across function calls. This is because as long as both sides, the calling side and called function side, agree on which information is to be preserved, then the compiler can generate the most efficient code for that particular call.
In the context of a decompiler, we must detect which registers are preserved by each function, so that we can exactly compute the liveness information for each register.
The basic code to save registers is generated by compilers as part of the function's prologue after having set up the stack frame. Correspondingly, each register is restored in the function's epilogue, before de-allocating the stack frame. For example:
FP = SP
SP -= #local_size SP -= #local_size
PUSH R1 PUSH R1
PUSH R2 PUSH R2
POP R2 POP R2
POP R1 POP R1
SP = FP SP += #local_size
How does saved registers information affect the compression of expressions? Consider the following code sequence:
R1 = 1
R2 = 2 R2 = 2
CALL FUNC FUNC(R1) FUNC(1)
ADD SP, #4
M1400 = R2 M1400 = R2 M1400 = 2?
How can we be sure that the value 2 is still in register R2 after the function call? Only if we know that FUNC() does not use nor change R2 then we can collapse the R2 = 2 and the M1400 = R2 into a single statement. If FUNC() uses R2 as one of its input values, then we cannot remove the R2 = 2 assignment. If FUNC() changes R2, it's possible that R2 is actually an output of the function, and we may actually have to translate the call into M1400 = FUNC(R1).
Collapsing the R2 = 2 and M1400 = R2 can be done using liveness information, but only if the liveness information is accurate for FUNC(). That means that we need to translate FUNC() before we translate the function that calls FUNC(). How do we decide the order to analyze functions? We can use a proven technique, that is, computing the depth-first order (DFO) for each function, and then visiting the functions with the highest DFO id first.
The following algorithm computes the DFO id for each function:
id = procList.length
for each function in procList in reverse order
function.visited = true
for each destFunc in function.callsTo
function.dfoID = id
After this algorithm, each function will have a DFO id, with leaf functions (functions that don't call any other function) with higher ids, while functions closer to the entry point will have lower ids.
We can then analyze functions with the highest DFO id. Those will initially be leaf functions. Since they won't have any function call, we can precisely compute the set of input registers, output registers and saved registers. As we continue to analyze functions with lower DFO ids, we can be sure that all the functions they call will have been already analyzed, thus we can be sure of which registers are alive at any given point in the program.
Next: Recovering Types