Subject: Generated Links, or how NOT to program a pdp-8

From: [email-masked] (Charles Lasner)
Date: 15 Feb 1995 00:47:44 GMT

Certain people have inquired about the PDP-8 assembly language
feature known as automatically generated links.  They assume that the
use of this quirk is a "feature" of the machine, since it's found in
most of the assemblers for the PDP-8 (PAL8, P?S/8 PAL, PAL-12,
PAL-12, DIAL-10, PAL-D, etc.).  Link generation is not for the
beginner, since it can "bite" you if you don't understand what's wrong
with it.  (And curiously, the more you know about it, the more you
don't want to use it!)

A generated link is an attempt to use assembler syntax to cover
impossible cases of off-page addressing, and the assembler's (poor)
attempt to synthesize a valid instruction to cover the user's
intention.

PDP-8's have a fixed addressing range, which is basically that
addresses must either be on page zero, or on the current page where
the instruction itself resides.  This applies to direct references to
instruction operands.

Indirectly, any address in the 4096 word field the current
instruction is in can be referenced.  However, the pointer address
that contains the address of any of these 4096 locations is itself
subject to the same rules as the direct reference.

These rules are not negotiable!  They are intrinsically in the
architecture of the machine.  (Sometimes programmers think it's
merely some demented "punishment" imposed on them by the assembler
:-).)

Extending the rules slightly, if the machine supports extended memory
(which most do), then there are auxiliary registers referred to as
the instruction field and the data field.  Either can be set to any
value in the range of 0-7 (other than in some extended addressing
machines using uncommon KT8A or MEC8 hardware; we leave these cases
out since they don't contribute to the mechanics of link generation,
etc.).

If the instruction field is changed (using an instruction such as
62N2 where N is the desired field 0-7) then the next instruction that
is a JMP or JMS will transfer the value from the 62N2 instruction
(since execution of the 62N2 this value is being held in a buffer
known as the instruction field buffer) into the instruction field
itself.  This means that at that point, the immediate next
instruction will be fetched from the new field N, i.e., all further
execution occurs in the 4096 words of field N; the old field is lost.
(Note: interrupts are inhibited when 62N2 is executed and are
allowable again only after the new field is established.  This
prevents interrupt-driven interaction with the field change!)

This hardware allows the programmer to write cross-field callable
subroutines that require some additional housekeeping instructions to
manage the disposition of the calling field, etc.  It is the
programmer's responsibility to both design and maintain the
conventions to be applied, etc. (A practical example will be presented 
later.)

The data field can be changed at any time using an instruction of the
form 62N1 where N is 0-7 to specify a new choice of data field.  The
data field is the field used whenever any of the following
instructions are used:

        AND I   xxxx
        TAD I   xxxx
        ISZ I   xxxx
        DCA I   xxxx

Explicitly, instructions of the form JMS I xxxx and JMP I xxxx *DO
NOT* use the data field.  This is actually the crux of the matter in
the problem with link generation.

Assuming that cross-field callability isn't a consideration,
subroutines are generally called as follows:

        *200

CALLER, JMS I   PSUB            /CALL THE SUBROUTINE

        *377

PSUB,   SUB

        *1000

SUB,    .-.                     /SUBROUTINE HEADER
        .                       /BODY OF SUBROUTINE
        .                       /"
        .                       /"
        JMP I   SUB             /RETURN TO CALLER

Thus, by using a local pointer to the subroutine SUB, callers can
call the subroutine from any page.  If there are sufficient callers,
it could make sense to move the pointer to page zero:

        *177

PSUB,   SUB

This would allow all callers to use the same pointer, thus saving
current page space on each page making one or more calls, etc.

An acceptable embellishment to this process is the use of literals.
Literal generation imposes a restriction on the design of the
program.  Specifically, the programmer gives up access to the end of
each current page and also to the end of page zero.  In exchange for
this, tables are automatically generated in these locations to
contain the pointers as required, etc.

Thus, the example can be embellished to:

        *200

CALLER, JMS I   (SUB)

which puts the pointer to SUB into 0377.

Or if there are sufficient callers to warrant a page zero reference:

CALLER, JMS I   [SUB]

which puts the pointer to SUB into 0177.

In all cases, literals are generated with addresses decrementing as
required.  A PE or Page Exceeded error is the case where the highest
address of the code stream or user-defined storage or constants would
overlap with the lowest address of the table, i.e., there isn't
enough room on the page for that many instructions and literals.
Something must be moved off the page to make it fit correctly.
(Note: there is no "punishment" here!  If no literals were being
used, and each instruction referenced a user-defined address, the
code still would be too large to fit.  However, the exact address of
the first noted assembly error could perhaps be in a different
place.) Similarly, a ZE or page Zero Exceeded error means the same
thing has occurred on page zero.

So far, the programmer has complete addressing control of his program
(other than the automatic table generation within the scope of
literal generation if opted for).  Now we come to link generation.

A lazy programmer (LP) can ask the assembler to "fake" certain things for
him using literals.  For example, the LP can use the following syntax

        *200

CALLER, JMS     SUB

(rest of example is as above)

What the assembler is prepared to do (if link generation is enabled
and not flagged as an error) is to FAKE the operation using precisely
what the syntax of the literal form would be.  Thus, the ACTUAL
instructions generated are:

        *200

CALLER, JMS I   0377

        *0377

        SUB

In fact, if the syntax were mixed, i.e., some cases of using JMS I
(SUB) and some lazy usages of JMS SUB, the literal generator would
even optimize the code and use the same literal!  (Score one point in
favor of the lazy programmer! :-))

LP's will defend their laziness with some "interesting" notions.  For
example, they "know" that the assembler will just "figure out" all of
the inappropriately called subroutines, so they never have to worry
about where the calls wind up, etc.  While this is largely true,
there are some shortcomings:

1)  If there are sufficient callers on different pages to a
subroutine on yet a different page, then it would be more space
efficient to elect to use a page zero pointer for all of the calls.
This would eliminate the space wasted by all of the different current
page links.

2)  Link generation encourages general sloppiness, i.e., no attempt
is made to group subroutines to fit on the same page as the bulk of
their callers.  In many situations, proper ordering of code can
eliminate most if not all links entirely.

Similarly, if programs do occasional JMP instructions to another
page, the generated link can make the LP's intention generate code to
match the attempt, albeit taking more space than it might, etc.

So far, the use of link generation isn't "fatal" since the program
*does* still follow the intended logic, even if sloppy.

However, the link generation mechanism DOES NOT follow the above
mechanism.  Instead, ALL addressing instructions use the same
assembler mechanism to attempt to fix up the LP's input, even if the
hardware doesn't support it!

Consider the following:

        *200

        TAD     TOOFAR

        *400

TOOFAR,

This sequence will of course generate the same code as:

        *200

        TAD I   0377

        *0377

        400

Assuming the program strictly operates in a 4K machine, the link
generation would be valid.  But if the machine actually has extended
memory hardware (8K or more), the assembler has no way of knowing
what the dynamic data field of the moment is at the point of
execution!

Thus, the following represents an unrecoverable sloppiness:

        *200

        CDF     00
        JMS     SUB

        *400

        CDF     10
        JMS     SUB

        *1000

SUB,    .-.
        TAD     TOOFAR
        JMP I   SUB

        *1200

TOOFAR,

In this case, the TAD TOOFAR actually generates TAD I 1177 where 1177
in turn gets the value 1200.  In the cases where the data field
incidentally matches the program's instruction field, the generated
link actually works as intended.  But in the other case where the
data field is set to another field, the code erroneously references
location 1200 in that other field!

In essence, use of generated links means that the LP has to also be
non-lazy, but in a different way:

The LP has to hand inspect a listing of his program, searching out
each and every assembler statement where a LG (link generated)
exists.  If this is not flagged as an error, the only indication is
that the octal value of the instruction is appended with a '
character to indicate the generated link.

For each and every link-infested line, the programmer must determine
if the link pertains to a JMP or JMS.  For all others, the programmer
must then spend time analyzing the extended memory consequences of
whether the data field would ever differ from the instruction field
at that particular point of the code.

Since the assembler never makes any distinction, it's always
necessary to perform this manual check.  It would appear to be more
productive to merely NEVER USE LINKS in the first place!

Thus, a well-organized program would use no links, and instead make
link generation either an error, or a disabled feature.  In PAL8,
links cannot be disabled, but they can be made into assembly errors
using the /E switch.  In P?S/8 PAL, there are actually four
possibilities.  Links generation requires literal generation as a
subset.  In P?S/8 PAL, literal generation is itself an option.  Thus:

<none>          Do not generate literals or links
/Q              Generate literals; do not generate links
/O              Generate literals and links, but flag links as errors
/Q and /O       Generate literals and links, don't flag LG errors

The last two cases are equivalent to what PAL8 does.  If links are
disabled, the error reduces to the PAL III-compatible Illegal
Reference IR error, meaning an attempt to reference an address off
the current page.  Note: in all cases, syntax such as:

        JMS I   TOOFAR

        PAGE

TOOFAR,

Is flagged as at least an Illegal Indirect II error, since the
instruction is already indirect and not possibly a candidate for a
link generation.  In P?S/8 PAL with links disabled, this is merely an
IR error.

(Note: the reason for the first two P?S/8 options is that P?S/8 PAL
is a 4K assembler that takes advantage of 8K or more only if
available.  Thus, if certain features are disabled, it may still be
possible to assemble small programs in less memory.  PAL8 always runs
in 8K minimum, thus there was never felt a design need to make the
assembler more "frugal".  Thus, there are a small class of assembler
options in P?S/8 PAL that are deletable only to allow the possibly
better use of remaining memory, etc.  When P?S/8 PAL concludes an
assembly, it reports the minimum amount of memory actually required
to assemble a program given the options enabled.  This value is
actually reported to the nearest 1K, as P?S/8 configurations may
involve fractions of a field, etc.  Thus, the user has an idea of how
much memory would be needed were the program assembled on a smaller
machine, etc.  Options may have to be deleted to accommodate this
value as necessary, etc.)

A practical cross-field-callable subroutine mechanism is included
here:

    By restricting the data field to be that of the calling field, a
subroutine can do all things subroutines ordinarily do, such as
parsing off arguments, making in-line/skipped returns, etc.
Arguments must either have implicit fields, or alternatively must be
restricted to being in the same field as the caller.

Consider the P?S/8 system handler call:

        FIELD   3               /AN ARBITRARY FIELD

        *200                    /AN ARBITRARY ADDRESS

        CDF     30              /SET THE DATA FIELD TO OUR OWN FIELD
        CIF     00              /THE SUBROUTINE IS IN FIELD 0
        JMS I   (7640)          /THE SUBROUTINE ENTERS IN 07640
        ADDRESS                 /ADDRESS OF DISK BUFFER IN FIELD 4
        200+40                  /READ TWO BLOCKS INTO FIELD 4
        100                     /WANT TO READ BLOCK 100 AND 101
        HLT                     /RETURNS HERE

        FIELD   4               /AN ARBITRARY FIELD

        *1000                   /AN ARBITRARY ADDRESS

ADDRESS,                        /DISK BUFFER HERE

In this case, the caller indicates calling from field 3 by setting
the data field accordingly.  Inline arguments are allowed which
indicate all parameters of a read call involving a totally different
field.

A fragment of the system handler to deal with this might look like
this:

        FIELD   0               /WHERE THE HANDLER IS

        *7640                   /WHERE IT ENTERS

HANDLER,.-.                     /ENTRY POINT OF HANDLER
        CLA                     /CLEAN UP; DIRTY CALLERS COULD HURT!
        RDF                     /GET CALLING FIELD
        TAD     (CIF CDF)       /FORM CIF CDF CALLING FIELD
        DCA     EXITINS         /STORE FOR LATER
        TAD I   HANDLER         /GET FIRST ARGUMENT IN CALLER'S FIELD
        DCA     WHAT1           /STASH IT
        ISZ     HANDLER         /BUMP TO NEXT ARGUMENT
        TAD I   HANDLER         /GET SECOND ARGUMENT FROM CALLER
        AND     (70)            /JUST FIELD BITS
        TAD     (CDF)           /FORM CDF TO CALLER'S DISK BUFFER
        DCA     DSTRINS         /STORE FOR LATER
        ISZ     HANDLER         /BUMP TO THIRD ARGUMENT
        TAD I   HANDLER         /GET BLOCK ARGUMENT
        DCA     BLKWHAT         /STORE FOR LATER
        ISZ     HANDLER         /BUMP PAST LAST ARGUMENT
        CDF     00              /WE NEED TO OPERATE ON OUR OWN FIELD
        .                       /BODY OF HANDLER
        .                       /"
DSTRINS,.-.                     /WILL BE CDF TO CALLER'S DISK FIELD
        .                       /MORE HANDLER
        .                       /"
EXITINS,.-.                     /WILL BE CIF CDF CALLER'S FIELD
        JMP I   HANDLER         /RETURN TO CALLER PAST HIS ARGUMENTS

The body of the subroutine operates in field 0.  At some point, it
needs to access the caller's disk buffer using a CDF to that field,
so an in-line instruction for that purpose is manufactured.
Eventually, the program exits using a CIF CDF instruction to the
caller's field.

Other mechanisms are possible, such as passing the address of where
in an implied field an argument must be.  In P?S/8 non-system
handlers, a pointer to a group of three arguments is used, similar to
the above example.  The only restriction is that the three argument
group must itself be in the caller's field.  The pointer to the group
is one of the passed arguments in-line to the call and skipped around
when exiting back to the caller, etc.

As bad as generated links are, there is an assembler that takes this
process to a "higher plane" called PAGE8.

In PAGE8, PDP-8 code need not be organized according to the
conventional page boundaries!  Instead, the code is faked using link
generation as a starting point.  Considering the following
subroutine:

        *371                    /REAL NEAR THE END OF A PAGE

SUB,    .-.                     /ENTRY POINT
        TAD I   SUB             /GET IN-LINE ARGUMENT
        DCA     TEMP            /STORE IT
        ISZ     SUB             /SKIP PAST IN-LINE ARGUMENT
        CLA                     /SOME MORE INSTRUCTIONS
        NOP                     /"
        JMP I   SUB             /RETURN TO CALLER

TEMP,   .-.                     /TEMPORARY STORAGE

How could such an example work?  The answer is that the following
code gets generated:

        *371                    /REAL NEAR THE END OF A PAGE

SUB,    .-.                     /ENTRY POINT
        TAD I   SUB             /GET IN-LINE ARGUMENT
        DCA I   0375            /STORE IT
        JMP I   0376            /CONTINUE ON NEXT PAGE        

        TEMP
        NEXTPAGE
JUMPRET,JMP I   SUB             /NEEDED TO EXIT

        *400

        ISZ I   577             /SKIP PAST IN-LINE ARGUMENT
        CLA                     /SOME MORE INSTRUCTIONS
        NOP                     /"
        JMP I   576             /JUMP BACK TO THE "JMP I SUB"

TEMP,   .-.                     /TEMPORARY STORAGE

        *576

        JUMPRET
        SUB

In essence, if a subroutine can't fit, a JMP I SUB instruction is
reserved at the end of the page because the only way to execute this
instruction is on the original page.  In fact, any form of indirect
addressing requires some fixup code generation, possibly in the form
of subroutines merely to execute an indirect instruction from the
only page where it can do the proper thing, but called from the page
of the additional fixup, etc.

Additional literal-like words are generated as various forms of fixup
on either side of the hardware page break to allow each portion of
the split code to create indirect instructions that carry out the
intention of the original code, etc.

There are numerous holes in this exercise where the data field can
make the entire thing break down as in the more trivial case of
generated links!

(Note: the examples here are mythical; PAGE8 actually uses a syntax
reminiscent of IBM 360/370 assembler including DC, EQU, etc.
However, the essential logic of the code generation is presented
accurately enough to point out the shortcoming regarding the
inability to depend on the data field, etc.  As to whether anyone
wants to program the PDP-8 using older IBM-like assembler syntax is
an entirely different matter!)

Thus, anyone considering programming in PDP-8 assembly language is
advised to use features that actually match the hardware.  It's not
necessarily true that all available utilities adhere to that
requirement!

cjl