Re: PCODE Interpereters 101

Tom Lane <tgl@netcom.com> wrote:


>sda@rt66.com (Scott Amspoker) writes:


>> I always felt that P-code's static links weren't a very efficient way
>> to handle the problem.


>...Static links are
>cheaper to update at procedure call & return than a "display" array
>is; moreover they can be optimized away entirely for outermost-level
>procedures. A display array allows cheaper access to more-than-one-
>level-out nested local variables, but it offers no advantage for local
>variables, global variables, or one-level-out nested locals.


Actually, displays can be very efficient at the procedure call point.
Consider a recursive call from a level 5 routine to a level 2 routine.
If I recall correctly, Pcode (using static links) would issue a CALL
instruction that included the difference in levels as an argument. In
this case, that would be -3:


CALL someprocedure,-3


The entry code for the procedure would have to step back through the
chain of static links to find the stack frame for the previous level 1
and link to it.


With a display, each procedure would only have to push the frame
pointer for it's lexical level in the display. The CALL instruction
would not have to pass a level difference argument. The procedure
entry code would do something like:


PUSHDISPLAY 2


That would result in the following:


push display[2] ; save old level 2 frame on the stack
move sp -> display[2] ; set new one


The exit code would have an extra pop operation to restore the saved
display value.


For optimization, the display push/pop is not necessary unless the
procedure calls a nested procedure and only if its frame will be
accessed by the nested procedure (or one of its descendants). That's
quite easily determined by the compiler. Furthermore, a nested
procedure that is only called by one other procedure (parent, sibling,
or descendant of sibling) can simply treat its stack frame as a mere
runtime extension to the caller's frame. That could be extended
through many levels thus allowing direct access to intermediate frames
in some situations. Such optimizations would seem to also apply to
static links as well.


My point here is that a display can be implemented that will have zero
impact on the common C-style model (all stack frames are level 1, all
calls are from level 1 to level 1). In fact, it can also have zero
impact on many common uses of nested functions. As with static links,
it can kick in only when it's needed but it beats walking a static
link chain on procedure entry and on access to intermediate frames.


From a compiler standpoint, it can be implemented reasonably well
without support from the hardware. An intermediate frame pointer
loaded from the display can be optimized just like any other pointer -
held in a register while it's needed, etc. And regardless of the
frame level being accessed, the instruction sequence to locate a frame
is always the same cost:


load display[x] -> address register


With static links, multiple loads might have to be generated to locate
an intermediate frame (although register optimizations are certainly
possible and could get quite interesting). In the end, the tradeoffs
are probably negligible since lexical depth is unlikely to ever get
more than a few levels. I just feel that the display approach is
easier to implement and has a constant cost factor comparable to the
best case cost of static links.




It's also worth debating the general usefulness of lexical procedure
nesting. My main axe these days is C++ and I often have a situation
where I would use lexical nesting if I could. Instead, I end up with
a little static "helper" procedure that is called only from one other
procedure. If it does some function on the caller's data, parameters
must be passed for access. If it's in a class, then the little helper
routine is even exposed in the header file! It might not seem like a
big deal but it affects the way we think about our code.


Hell, we have lexically nested structs and classes, why not
procedures? Most programmers today think only in terms of global
vs. local with regard to data visibility. That leads to the idea that
global data is bad or unsafe. I prefer to think of "global" as a
relative thing with multiple levels of ambience. Each level is no
more good or evil than any other. C programmers tend to regard global
data with suspicion because, due to the lack of function nesting and
controlled "sharing", global data is often misused.


Now it's become pretty common to work with a process/thread execution
model. The issue of thread local storage is reopening the debate
about controlled sharing, visibility, and global data. I don't know
where it will all lead, but it's pretty clear that the mainstream
languages today need to rethink some fundamental concepts.


Scott Amspoker |
sda@rt66.com |
http://www.rt66.com/sda |

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