Lecture 29, The Display
Part of
the notes for 22C:196:002 (CS:4908:0002)
|
Consider the following Kestrel program, a program that serves only to demonstrate nested procedures that call each other. The problems remain the same if these are initializers for types or other kinds of blocks:
a: var int32;
b: procedure
c: var int32;
c = a;
end;
d: procedure
e: var int32;
f: procedure
g: var int32;
g = e;
b;
end;
h: procedure
i: var int32;
i = a;
f;
end;
e = a;
h;
end;
a = 1;
d;
We have already described how this could be compiled if each block instance (procedure activation record, in this case) is given an up-link to the enclosing block instance. Here, we will recap this with Kestrel-like pseudocode. In effect, the up-link is a reference to the enclosing block, and it must be passed by the caller so that the called routine can know its static context. So, we rewrite the code as follows, adding explicit up-links everywhere, and assuming that the identifier self always refers to the current activation record:
a: var int32;
b: procedure( ref up:type_of_anonymous_outer_block )
c:var int32;
c = up.a;
end;
d: procedure( ref up:type_of_anonymous_outer_block )
e: var int32;
f: procedure( ref up:type_of_d )
g: var int32;
g = up.e;
b( up.up );
end;
h: procedure( ref up:type_of_d )
i: var int32;
i = up.up.a;
f( up );
end;
e = a;
h( self );
end;
a = 1;
d( self );
Clearly, small programs will rarely be deeply nested. In addition, there is an obvious optimization, making a special case of the anonymous outer block. There cannot be multiple instances of this block, so a compiler can use static addressing for the outer block. This makes variables in the anonymous outer block no different from global varibles in C or C++. We can even consider adopting the convention that public global variables are externally visible, thus allowing them to be linked to external variables in code written in languages like C.
If programs are large and therefore potentially deeply nested, up-level addressing can become inefficient. Some compiler writers make the mistaken assumption that, since this is unlikely, they need not bother with it. Unfortunately, as programs get large, the cost of dealing with such compiler limits, when they are unexpectedly encountered, can be quite large.
I recall a program I wrote that was on the order of 5000 lines of Pascal code. When I tried to port it to a new computer, a computer that featured an Pascal compiler that was advertised as fully conforming to the ANSI Pascal standard, I discovered that it only permitted on the order of 8 levels of nesting. My program required more like 10 levels. The result was a disaster, to that project. Rewriting a program that size to change a question of program structure is extremely difficult.
So, here, we will disregard the possibility of making a special case of global variables and investigate, instead, how to change our approach to compiling so that we eliminate the need for references of the form up.up.up regardless of how deeply the program is nested.
This problem was discovered by the implementors of Algol 60 on the Burroughs 5000 computer, and they solved the problem by the following scheme. They created a set of registers, inside the CPU, called the display registers. At any point in the program, when code was executing at static nesting level n, display registers 0 to n showed the addresses of the current activation records at levels 0 to n. Thus, for code at nexting level n, display register number n was the self pointer.
In the general case, where the number of nesting levels is unlimited, this scheme requires an array, the display, to hold the appropriate pointers. The finite store of registers inside the CPU is then used to cache frequently used nesting levels. Note that in deeply nested programs, most routines will not make use of more than a few of the enclosing blocks.
The following code is a rewrite of our original code using a display:
display: var array 0..2 of pointer_to_activation_record;
displaysave: var pointer_to_activation_record;
displaysave = display[0];
display[0] = self;
a: var int32;
b: procedure -- at level 1
displaysave: var pointer_to_activation_record;
displaysave = display[1];
display[1] = self;
c: var int32;
c = display[0]@.a;
display[1] = displaysave;
end;
d: procedure -- at level 1
displaysave: var pointer_to_activation_record;
displaysave = display[1];
display[1] = self;
e: var int32;
f: procedure -- at level 2
displaysave: var pointer_to_activation_record;
displaysave = display[2];
display[2] = self;
g: var int32;
g = display[1]@.e;
b;
display[2] = displaysave;
end;
procedure h
displaysave: var pointer_to_activation_record;
displaysave = display[2];
display[2] = self;
i: var int32;
i = display[0]@.a;
f;
display[2] = displaysave;
end;
e = display[0]@.a;
h;
display[1] = displaysave;
end;
a = 1;
d;
display[0] = displaysave;
Instead of elaborate code to follow a chain of up links, references to non local variables are now quite uniform: To reference a variable v declared at static nesting level n, we simply reference display[n]@.v. That is, we use indexed addressing off of an element of an array. If we cache commonly used display entries, this makes references to non-local variables potentially no more expensive than references to local variables.
The cost of this, aside from a statically allocated display array with as many entries as there are nesting levels in the program, is one additional location in every activation record, the display-save location. In addition, we add code on entry to each procedure to save the former display entry for that procedure's nesting level and set that display entry to point to the current activation record, and we add code just prior to the return from each procedure to restore that display entry to its previous value.
This scheme works perfectly so long as the only static contexts are procedures and functions, and so long as procedures and functions cannot be passed as parameters. In effect, both objects and the ability to pass procedures as parameters create problems that are difficult to solve when using a display.
There are workarounds for these issues, but they are ugly. Consider calling a method of a class: If the class is at nesting level x, the object itself is at level x-1, so method calls must involve saving, setting and restoring a minimum of two display levels. We must add a level of saving and restoring for each level that we reach through in order to grab a method. That is, if we call a@.b@.c, where b is a public component that itself has a public component c, then we may need to save and restore 3 nesting levels. The cost of doing this escalates rapidly, until there is considerable doubt that using a display offers any savings.
Oops. There are two general ways that the operation of returning a value from a function has been expressed in programming languages, illustrated by the difference between Pascal and C:
{ in Pascal }
function five:integer
begin
five := 5;
end;
/* in C */
int five() {
return 5
}
In Pascal, assignment to the function name behaved as if it was assigning to a write-only variable that served as the function return value. In C, there is a specific return statement to set the return value and (at the same time) return. Up to this point, we have assumed that Kestrel did the former, since function calls can easily reserve space on the stack for the return value, and the implementation of the return operation therefore involves assignment to a location that behaves as if it was a local variable.
But what of this function, declaredin Kestrel:
r: type range 0..1;
a: type array r of @r;
ob: var @r
trouble: function @r ( arg:r )
trouble(1) = ob;
trouble(1)@ = ob@;
end;
The problem is, the expression trouble(1) could either be a recursive call to trouble, or it could be a reference to the return value of trouble. As it stands, the language is unambiguous, but the reasoning it takes to determine what a program means is not trivial. The first line of the body of trouble above can only be interpreted as setting one element of the return value, while the second line can only be interpreted as a recursive call to determine the address of the variable to set to 1.
Despite the fact that is is unambiguous, it is ugly. There is no way for a compiler to determine what is intended until the very end of the reference. This is not good. We should add a return statement to Kestrel