Re: Stack frames & static predecessors

On Aug 23, 8:10 pm, Till Wollenberg <wollenb...@web.de> wrote:
> I'm currently preparing for an exam in 'compiler construction' and
> wondered how the following problem is solved in real world compilers:
> if some code of an inner function ('bar') accesses a local variable
> ('x') of an outer function ('foo') how is the address (on the stack)
> of this variable determined? ...


> [The calling procedure passes in pointers to the stack frames of all
> of the lexically enclosing procedures, a structure known as a display.
> The code to create the display at each call point is tedious but not
> complex, and the techniques have been known since Algol 60, if not
> longer. This used to be a standard topic in compiler texts, at least
> until the academic world switched from Pascal to C. Take a look at the
> x86 ENTER instruction, which is specifically designed to create stack
> frames with displays. -John]


John's note on displays great. A display is conventionally an array
of pointers to stack frames of lexically enclosing scopes. Another
technique connects successive lexically enclosing scopes in a linked
list (actually a child-to-parent-connected tree if you look at it
globally). For this purpose, each scope contains a pointer called a
"static link" (vice the dynamic link, which always points to the next
lexically enclosing scope, regardless of its lexical nesting).
Displays can access any scope with at most one dereference. Static
link chains need one dereference per scope, a small performance
penalty. But static link chains make function/procedure pointers and
arguments simpler. Pointers to functions/procedures that access
variables outside their body scopes are really structures (sometimes
called thunks) containing the usual code pointer plus pointers to
enclosing scopes. For a linked list only the end of the chain is
needed; for displays, something fancier. Aho et al. Principles of
Compiler Design covers this topic thoroughly with good examples.

Return to the comp.compilers page.
Search the comp.compilers archives again.