Re: Stack frames & static predecessors

Robert A Duff <bobduff@shell01.TheWorld.com>
Sat, 25 Aug 2007 16:07:40 -0400

          From comp.compilers

Related articles
[3 earlier articles]
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: Robert A Duff <bobduff@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Sat, 25 Aug 2007 16:07:40 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-08-065 07-08-072
Keywords: code, Pascal, storage

Gene <gene.ressler@gmail.com> writes:


> 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).
    ^^^^^^^^^ I think that's a typo -- you meant "dynamically"
That is, the dynamic link points to the caller's stack frame.
The static link points to the stack frame of the procedure
that statically encloses the callee.


> Displays can access any scope with at most one dereference. Static
> link chains need one dereference per scope, a small performance
> penalty.


Right, but for many languages and programming styles, the number of
links traversed is typically small -- an average of approximately one
link. Furthermore, multiple references to the same outer scope can be
optimized (I'm thinking of a loop that references an outer variable --
you only need to chase down the chain once).


You also need to consider the overhead of managing the display.


>...But static link chains make function/procedure pointers and
> arguments simpler.


Yes. Simpler and more efficient.


>...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.


Right. The length of the display is the max nesting depth, which is not
known until link time (unless you arbitrarily limit nesting depth).


- Bob


Post a followup to this message

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