12.1.5 The Display

After reading the previous section you might get the idea that one should never use non-local variables, or limit non-local accesses to those variables declared at lex level zero. After all, it's often easy enough to put all shared variables at lex level zero. If you are designing a programming language, you can adopt the C language designer's philosophy and simply not provide block structure. Such compromises turn out to be unnecessary. There is a data structure, the display, that provides efficient access to any set of non-local variables.

A display is simply an array of pointers to activation records. Display[0] contains a pointer to the most recent activation record for lex level zero, Display[1] contains a pointer to the most recent activation record for lex level one, and so on. Assuming you've maintained the Display array in the current data segment (always a good place to keep it) it only takes two instructions to access any non-local variable. Pictorially, the display works as shown below:

Note that the entries in the display always point at the most recent activation record for a procedure at the given lex level. If there is no active activation record for a particular lex level (e.g., lex level six above), then the entry in the display contains garbage.

The maximum lexical nesting level in your program determines how many elements there must be in the display. Most programs have only three or four nested procedures (if that many) so the display is usually quite small. Generally, you will rarely require more than 10 or so elements in the display.

Another advantage to using a display is that each individual procedure can maintain the display information itself, the caller need not get involved. When using static links the calling code has to compute and pass the appropriate static link to a procedure. Not only is this slow, but the code to do this must appear before every call. If your program uses a display, the callee, rather than the caller, maintains the display so you only need one copy of the code per procedure. Furthermore, as the next example shows, the code to handle the display is short and fast.

Maintaining the display is very easy. Upon initial entry into a procedure you must first save the contents of the display array at the current lex level and then store the pointer to the current activation record into that same spot. Accessing a non-local variable requires only two instructions, one to load an element of the display into a register and a second to access the variable. The following code implements the Outer, Middle, and Inner procedures from the static link examples.

; Assume Outer is at lex level 1, Middle is at lex level 2, and
; Inner is at lex level 3. Keep in mind that each entry in the
; display is two bytes. Presumably, the variable Display is defined
; in the data segment.

Outer           proc    near
                push    bp
                mov     bp, sp
                push    Display[2]              ;Save current Display Entry
                sub     sp, 2                   ;Make room for I.

                mov     word ptr [bp-4],1       ;Set I to one.
                call    Middle

                add     sp, 2                   ;Remove local variables
                pop     Display[2]              ;Restore previous value.
                pop     bp
                ret
Outer           endp

Middle          proc    near
                push    bp                      ;Save dynamic link.
                mov     bp, sp                  ;Set up our activation record.
                push    Display[4]              ;Save old Display value.
                sub     sp, 2                   ;Make room for J.

                mov     word ptr [bp-2],2       ;J := 2;
                mov     bx, Display[2]          ;Get static link to prev LL.
                mov     ax, ss:[bx-4]           ;Get I's value.
                add     ax, [bp-2]              ;Add to J and then
                puti                            ; print the sum.
                putcr
                call    Inner

                add     sp, 2                   ;Remnove local variable.
                pop     Display[4]              ;Restore old Display value.
                pop     bp
                ret
Middle          endp

Inner           proc    near
                push    bp                      ;Save dynamic link
                mov     bp, sp                  ;Set up activation record.
                push    Display[6]              ;Save old display value
                sub     sp, 2                   ;Make room for K.

                mov     word ptr [bp-2],2       ;K := 3;
                mov     bx, Display[4]          ;Get static link to prev LL.
                mov     ax, ss:[bx-4]           ;Get J's value.
                add     ax, [bp-2]              ;Add to K

                mov     bx, Display[2]          ;Get ptr to Outer's Act Rec.
                add     ax, ss:[bx-4]           ;Add in I's value and then
                puti                            ; print the sum.
                putcr

                add     sp, 2
                pop     Display [6]
                pop     bp
                ret
Inner           endp

Although this code doesn't look particularly better than the former code, using a display is often much more efficient than using static links.

12.1.6 The 80286 ENTER and LEAVE Instructions

When designing the 80286, Intel's CPU designers decided to add two instructions to help maintain displays. Unfortunately, although their design works, is very general, and only requires data in the stack segment, it is very slow; much slower than using the techniques in the previous section. Although many non-optimizing compilers use these instructions, the best compilers avoid using them, if possible.

The leave instruction is very simple to understand. It performs the same operation as the two instructions:

                mov     sp, bp
                pop     bp

Therefore, you may use the instruction for the standard procedure exit code if you have an 80286 or later microprocessor. On an 80386 or earlier processor, the leave instruction is shorter and faster than the equivalent move and pop sequence. However, the leave instruction is slower on 80486 and later processors.

The enter instruction takes two operands. The first is the number of bytes of local storage the current procedure requires, the second is the lex level of the current procedure. The enter instruction does the following:

; ENTER Locals, LexLevel

                push    bp              ;Save dynamic link.
                mov     tempreg, sp     ;Save for later.
                cmp     LexLevel, 0     ;Done if this is lex level zero.
                je      Lex0
lp:             dec     LexLevel
                jz      Done            ;Quit if at last lex level.
                sub     bp, 2           ;Index into display in prev act rec
                push    [bp]            ; and push each element there.
                jmp     lp              ;Repeat for each entry.

Done:           push    tempreg         ;Add entry for current lex level.
Lex0:           mov     bp, tempreg     ;Ptr to current act rec.
                sub     sp, Locals      ;Allocate local storage

As you can see from this code, the enter instruction copies the display from activation record to activation record. This can get quite expensive if you nest the procedures to any depth. Most HLLs, if they use the enter instruction at all, always specify a nesting level of zero to avoid copying the display throughout the stack.

The enter instruction puts the value for the display[n] entry at location BP-(n*2). The enter instruction does not copy the value for display[0] into each stack frame. Intel assumes that you will keep the main program's global variables in the data segment. To save time and memory, they do not bother copying the display[0] entry.

The enter instruction is very slow, particularly on 80486 and later processors. If you really want to copy the display from activation record to activation record it is probably a better idea to push the items yourself. The following code snippets show how to do this:

; enter n, 0    ;14 cycles on the 486

                push    bp              ;1 cycle on the 486
                sub     sp, n           ;1 cycle on the 486

; enter n, 1    ;17 cycles on the 486

                push    bp              ;1 cycle on the 486
                push    [bp-2]          ;4 cycles on the 486
                mov     bp, sp          ;1 cycle on the 486
                add     bp, 2           ;1 cycle on the 486
                sub     sp, n           ;1 cycle on the 486

; enter n, 2    ;20 cycles on the 486

                push    bp              ;1 cycle on the 486
                push    [bp-2]          ;4 cycles on the 486
                push    [bp-4]          ;4 cycles on the 486
                mov     bp, sp          ;1 cycle on the 486
                add     bp, 4           ;1 cycle on the 486
                sub     sp, n           ;1 cycle on the 486

; enter n, 3    ;23 cycles on the 486

                push    bp              ;1 cycle on the 486
                push    [bp-2]          ;4 cycles on the 486
                push    [bp-4]          ;4 cycles on the 486
                push    [bp-6]          ;4 cycles on the 486
                mov     bp, sp          ;1 cycle on the 486
                add     bp, 6           ;1 cycle on the 486
                sub     sp, n           ;1 cycle on the 486

; enter n, 4    ;26 cycles on the 486

                push    bp              ;1 cycle on the 486
                push    [bp-2]          ;4 cycles on the 486
                push    [bp-4]          ;4 cycles on the 486
                push    [bp-6]          ;4 cycles on the 486
                push    [bp-8]          ;4 cycles on the 486
                mov     bp, sp          ;1 cycle on the 486
                add     bp, 8           ;1 cycle on the 486
                sub     sp, n           ;1 cycle on the 486

; etc.

If you are willing to believe Intel's cycle timings, you can see that the enter instruction is almost never faster than a straight line sequence of instructions that accomplish the same thing. If you are interested in saving space rather than writing fast code, the enter instruction is generally a better alternative. The same is generally true for the leave instruction as well. It is only one byte long, but it is slower than the corresponding mov bp,sp and pop bp instructions.

Accessing non-local variables using the displays created by enter appears in the exercises.

Chapter Twelve: Procedures: Advanced Topics (Part 3)
27 SEP 1996