Re: Stack frames & static predecessors

Gene <gene.ressler@gmail.com>
Fri, 24 Aug 2007 19:42:41 -0700

          From comp.compilers

Related articles
Stack frames & static predecessors wollenberg@web.de (Till Wollenberg) (2007-08-24)
Re: Stack frames & static predecessors torbenm@app-3.diku.dk (2007-08-24)
Re: Stack frames & static predecessors gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-08-24)
Re: Stack frames & static predecessors tk@ic.unicamp.br (Tomasz Kowaltowski) (2007-08-24)
Re: Stack frames & static predecessors bonzini@gnu.org (Paolo Bonzini) (2007-08-24)
Re: Stack frames & static predecessors gene.ressler@gmail.com (Gene) (2007-08-24)
Re: Stack frames & static predecessors anton@mips.complang.tuwien.ac.at (2007-08-25)
Re: Stack frames & static predecessors dnovillo@acm.org (Diego Novillo) (2007-08-25)
Re: Stack frames & static predecessors bobduff@shell01.TheWorld.com (Robert A Duff) (2007-08-25)
Re: Stack frames & static predecessors bobduff@shell01.TheWorld.com (Robert A Duff) (2007-08-25)
Re: Stack frames & static predecessors DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-08-26)
| List of all articles for this month |

From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Fri, 24 Aug 2007 19:42:41 -0700
Organization: Compilers Central
References: 07-08-065
Keywords: Pascal, code

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.


Post a followup to this message

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