|
|
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
|
© 2009 Giampiero Caprino, Backer Street Software
|
|
|