🚀 go-pugleaf

[re static links vs displays vs trampolines]

In article <KANZE.95Sep26113747@slsvhdt.lts.sel.alcatel.de> James
Kanze US/ESC 60/3/141 #40763 <kanze@lts.sel.alcatel.de> writes:
>I know that when I was working on compilers (and the Dragon book had
>just appeared), we used displays.  But that was ten years ago; I
>simply supposed that things had evolved since then.

Trampolines are new, not in the sense that no one ever thought of
them before[%], but rather in the sense that no one ever thought
they were a good idea before. :-)
-----
% It is possible that no one thought of them, but most `new' programming
  constructs have been around for years.  In fact, I think philosophers
  in Ancient Greece used to sit around the campfire thinking up
  programming constructs, and then saying, `Damn, if only we had
  some computers.'
-----

To illustrate, imagine you have a program P with nested functions F1
through F5 and G1 through G3:

	program P {
	    -- imagine some variables here and in the functions

	    function F1(arg1, arg2) {
		function F2 {
		    function F3 {
			function F4 {
			    function F5 {
				...
			    }
			    F5(...);
			}
			F4(...);
		    }
		    F3(...);
		}
		F2(...);
	    }

	    function G1(arg1) {
		function G2 {
		    function G3 {
			...
		    }
		}
	    }

	    -- call some of the functions
	    F1(a, b);
	    G1(c);
	}

The `static links' concept is pretty simple: at each call to a
function, you provide an extra argument -- call it `arg0', making
F1 take three arguments, for instance -- which is a pointer to the
activation record (`stack frame', but it does not have to be on a
stack) for whatever is running at the time.  Thus, the call:

	F1(a, b)

really passes to F1 not only `a' and `b', but also a pointer to
the set of variables local to program P.  When F1 calls F2, F1
passes to F2 a pointer to F1's locals; when F2 calls F3, F2 passes
a pointer to F2's locals, and so on.  One element in each activation
record is the pointer to the previous activation record.

If F5 wants to get to something that is four layers out (in F1),
it simply follows its static link argument to find F4's activation
record.  In here it finds F4's static link to F3, and from there it
finds F3's link to F2, and F2's link to F1, and now it can get to
the variables in F1's activation record.

The compiler always knows at compile time where it put F1's variables
within F1's activation record / stack frame -- it needs this
information to compile F1 anyway -- and also where it stores each
static link, and it knows while compiling F5 that a reference to
(say) `i' is to F1's `i' and that F1 is four layers out, so it can
easily generate code to find F1's `i'.

The move from `static links' to `displays' is straightforward.  We
see that moving out N layers requires following N static links.
If we think this is terribly inefficient, we can simply copy the
links into an array (of size [1..N]), and then instead of going
link1->link2->link3->link4, we just take display[4].  A little bit
of optimization work shows that a function at level K can use the
existing display set up by calls in [1..K-1].  Moreover, the compiler
can determine the size of the display array at compile time: it is
simply the deepest lexical nesting in the program.  (In program P
above, it is either 5 or 6, depending on whether variables local
to program P have static storage duration.  Some languages might
prefer to give them automatic duration, so that multiple copies of
P can run in the same address space.)

When an inner function (such as F5) calls an outer function (such
as F2), the inner function may have to salt away part of the display,
because new calls within F2 may overwrite those parts.  (In the
static link scheme, the call from inner to outer simply locates
and passes the appropriate static link.)

The details get a little trickier when one can pass pointers to
functions; I leave this to the reader. :-)

It turns out that, in general, if the compiler is any good at
optimizing, displays perform worse than static links.  The reasons
are simple:  first, uplevel accesses are rare in real code; second,
when they do occur, the compiler can often follow the static links
as needed *outside* any inner loops, so that the extra work needed
to follow several links is small.  Static links amount to lazy
evaluation, and when a feature is rarely used, lazy evaluation is
the right idea.

Now, the problem with putting either of these into C is that both
approaches require passing an extra (hidden) parameter: the static
link or display entry.  If you have a bunch of existing object code
that you want to continue using, you are stuck.  (If you can recompile
all the existing object code, you can use static links or displays.)
Hence the idea of `trampolines': instead of passing an extra parameter,
you compile code on the fly that squirrels away the extra parameter.
Instead of calling the nested function, you bounce off the trampoline,
which sets up the static link (or virtual equivalent) and jumps to
the nested function.

>During the discussions in the C++ committee, it was pointed out that
>it was not necessary that code and data share the same address space,
>*IF* there was some way of mapping the distinct address spaces to the
>same physical addresses.

This has always been true; consider split I&D on the PDP-11.  (C
worked fine there, once they put in the data shim to make sure that
no object had &x==NULL.)  However, since trampolines are an
implementation technique, it is still possible to legislate that
`NC' (New C) have nested functions, at the cost of object compatibility
with old split I&D PDP-11 binaries.

Is it a good idea?  The Greek philosophers were split on the issue. :-)
-- 
In-Real-Life: Chris Torek, Berkeley Software Design Inc
Berkeley, CA	Domain:	torek@bsdi.com	+1 510 549 1145
  `... if we wish to count lines of code, we should not regard them as
   ``lines produced'' but as ``lines spent.'' '  --Edsger Dijkstra