Decompiler Design - The Stack
Prev: Expression Propagation
Until now we have considered only code and memory accesses to global variables and registers. However, many variables are allocated on the stack as variables locals to functions. To discover those variables we need to analyze instructions that access the stack.
But the stack is not used only to store local variables. Its purposes include:
All of these tasks are performed sometimes with very little clues left by the compiler in the instruction stream. Reconstructing accesses to the stack adds significant complexity to the expression evaluator, and it deserves its own specialized module inside the decompiler architecture. In fact, more than one module may be devoted to stack reconstruction, so we'll spend some time describing how these modules operate for the different pieces of information that are linked to the stack.
Note that the stack is not directly visible to a high-level language like C or C++ (and even less so to languages like Java and C#), except for the fact that some variables are declared as automatic variables (with the optional, and obsolete C keyword "auto"). Therefore a decompiler should remove all stack references found in the instruction stream as they were certainly not present in the original high-level program.
To understand how to remove references to the stack it is useful to understand how the stack is partitioned by the compiler. Most non-optimized programs generate code that use a fixed register to access the stack, called the frame pointer (often abbreviated as FP, although in the x86 architecture register EBP is usually dedicated to this task. We will mostly use FP, since it's processor neutral, except when showing x86 code.)
The frame pointer is used to point to the head of a linked list of frames. Each frame holds data that is specific to a function invocation. The use of a frame pointer simplifies the compiler's job of generating code (yielding faster compilations), and especially the debugger's job of locating local variables, saved registers and return addresses.
It's important to note that there is one frame per each active invocation of a function, so if you're writing a debugger you should assume that there may be multiple frames for the same function, in case the function is recursive. Since a decompiler does not deal with run-time information, this is not a concern for the decompiler writer, except in one case which we'll talk about in the advanced section.
However, for programs compiled by an optimizing compiler, the frame is usually not generated. This has the advantage that the FP register is free to be used for other purposes, and that the generated code is shorter and faster, as the entry and exit code don't need to create an entry in the linked list of frame pointers. Unfortunately this creates a lot of problems for decompilers (as well as for debuggers), because now the decompiler does not know how big is the local variable area for each function.
To understand better the role of the stack, lets first consider framed functions and then move to the more complex frame-less functions.
Next: Stack Frames