Decompiler Design - The Stack

 

Prev: Expression Propagation

The Stack

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:

  • provide storage for variables local to functions, including creating multiple copies of the same variable(s) in case of recursive functions.
  • provide a place to save registers that cannot be changed across a function call, as set forth by the calling conventions for that processor, compiler, and operating system.
  • provide a place to save the frame pointer and the return address, as well as arguments passed to the function that cannot be passed via registers.
  • Sometimes, the stack is also used to provide temporary memory to return structures, or any value that cannot be returned via registers.
  • Finally, the stack can be used to save and restore registers during complex expressions evaluation, when there are not enough registers to hold all the operands of the expression.

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.

Framed vs. frame-less functions

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