Lecture 29, The Display
Part of
the notes for 22C:196:002 (CS:4908:0002)
|
Consider the following Falcon 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:
var a:int32;
procedure b
var c:int32;
code c = a;
end;
procedure d
var e:int32;
procedure f
var g:int32;
code g = e;
b;
end;
procedure h
var i:int32;
code i = a;
f;
end;
code e = a;
h;
end;
code a = 1;
d;
end;
We have already described how this could be compiled if each procedure is given an up-link to the enclosing block. Here, we will recap this with code entirely presented in Falcon. 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:
var a:int32;
procedure b( ref up:type_of_anonymous_outer_block )
var c:int32;
code c = up.a;
end;
procedure d( ref up:type_of_anonymous_outer_block )
var e:int32;
procedure f( ref up:type_of_d )
var g:int32;
code g = up.e;
b( up.up );
end;
procedure h( ref up:type_of_d )
var i:int32;
code i = up.up.a;
f( up );
end;
code e = a;
h( self );
end;
code a = 1;
d( self );
end;
Clearly, small programs will rarely be deeply nested. In addition, there is an obvious optimization, making a special case of the anonymous outer block. In Falcon, the anonymous outer block is always statically allocated. There cannot be multiple instances of this block, so a compiler can use static addressing for the outer block.
Here, though, we are interested in the possibility that programs are large and therefore, potentially deeply nested. 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:
var display: array 0..2 of pointer_to_activation_record;
displaysave: pointer_to_activation_record;
code displaysave = display[1];
display[0] = self;
var a:int32;
procedure b -- at level 1
var displaysave: pointer_to_activation_record;
code displaysave = display[1];
display[1] = self;
var c:int32;
code c = display[0]@.a;
display[1] = displaysave;
end;
procedure d -- at level 1
var displaysave: pointer_to_activation_record;
code displaysave = display[1];
display[1] = self;
var e:int32;
procedure f -- at level 2
var displaysave: pointer_to_activation_record;
code displaysave = display[1];
display[2] = self;
var g:int32;
code g = display[1]@.e;
b;
display[2] = displaysave;
end;
procedure h
var displaysave: pointer_to_activation_record;
code displaysave = display[1];
display[2] = self;
var i:int32;
code i = display[0]@.a;
f;
display[2] = displaysave;
end;
code e = display[0]@.a;
h;
display[1] = displaysave;
end;
code a = 1;
d;
display[0] = displaysave;
end;
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. Things get even worse if blocks are used to represent classes, with public procedures and functions representing methods.
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 Falcon 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 Falcon:
type r = range 0..1;
type a = array r of @r;
var ob:@r
function trouble( arg:r ): @r -- and why not allow a semicolon here?
trouble(1) = ob;
trouble(1)@ = 1;
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 completely unambiguous. The first line of the body of trouble above sets one element of the return value, while the second line is 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.