tJ

Wednesday, February 21, 1979

01:05:39

AI: LMODe; MACRO· .28

Page 1

The LISP Machine Macro-instruction Set.
·This docu~ent describes the LISPMachine~8 interpreted order code,referred to below -as ·"macrocode. w The .acrocode is designed to be highly
bi t-efficient, and ... ell-sui ted ta LISP. The campi latian of LISP into macrocode~8 very ~traightforuard, as uill be shown In examples below.
_Macrci~ode Is created by the wmacrocompi ler, W whi"ch is called wOCMP. W
It is· never neccesary to ..,rite out macrocode manually, because it correspondes
so closely _uith the LISP source code that It ...ould be easy to write the same thingin LISP.
.
_IJhen aCM? is run ona function, it is said to wmacrocompi lew the function.
It produces one "Function Entry Fr.ame,w referred to below as a FEF, for eachfunction compiled. The resulting LISP. pointer has datatype DTP-FEF-POINTER,
and points to the FEF, which is a block of memory at least 8 words long.
The FEF has several sections. The first section is always 1 words long.
and .contains various information about the format of the FEF and information
about ho~ the function should be invoked. For complete details of the bit
I~youts of these words, see the FORMAT document.
The next section of the FEF contains pointers to the VALUE celie and·
FUNCTION cells of symbols. These pointers are of datatype DTP-EXTERNAL-VALUE-CELL-POINTE!and are used as an "e~it vector", that is, compiled code can refer to these pointersin order to access special variables.
The next. section contains the Argu~ent Description List (ADL1.
The ADL contains one entry for each argument which the function expects to bepassed, and contains all relevant information about the argument: ~hether it is·required, optional, or rest, ho~ to initialize it if it is not provided,
uhether it·is local· or special, datatype checking information, and so on.
Sometimes the ADL can be dispensed with if the "fast argument option" canbe used instead; this helps save time and memory for small, simple functions.
ThE l.Ju t a i I ~ c.an bel oUfld in the FORMAT documen t.
'---'

The next section of the AOL contains various constants ~hlch thefunction might want to refer to: if the function includes (FOa '(A B)),then the list {A BJ ~ould be put in the constants area so that the microcode
can refer to. it.
The rest of the FEF is the actual macroinstructions themsel~es.
Each macroinstruction is 1S bits long, and so t~o macroinstructions
are stored in each word of the IISP machine. There are four ~onceptual"classes" of microinstructions, each of which is broken do",n into fields
in a different ~ay.
CLASS I;
343DEST.

OPCOOEREGISTER.

OFFSET

There are nine class I instructions, designated by 0 through 10 (octal)
in the OPCOOE field. Each instruction has a source, whose address
is computed from the "REGISTER" and OFFSET fields, and a destinationi.

Wednesday, February 21, 1979
given by the DESTINATION field.

01:05:39

AI:LMDOC;MACRO 28

Page 1.1

The instructions are:

OPCODE NAME------ CALL---"
1-CALLe

23-45S
78MOVE
CAR
COR
CADR
CODR
COAR
CAAR

Open a call ~Iock on the stack, to call the function
specified by the address. Uhatever the function returns
utll go to the destin~tion. The actual transfer of control
uill not happen until the arguments have been stored.
(See destinations NEXT and LAST.)CALL in the c~se of a function uith no arguments.The transfer ~f control happens immediately.
Move the contents of E to the destination.
Put the CAR of the c;ontents of E in the des t i nat ion.
Analogous.
Analogous.
Analogous.
Analogous.
Analogous.

The effective address, E, is computed from the "register" and the offset.
The instructions really use addressing relative to some convenient plac~ specified
by the "register" field. The register may be:

REG

FUNCTION

0FEF--123456
7=======ZI

This is the starting location of the currently-running
FEF. This is how the macrocode addresses the pointers
to value and-function cells, and the constants area.
Same as 0, plus 100 octal.
FEF+100
Analogous.
FEF+200
FEF+300
Analogous.
CONSTANTS PAGE This is a page of ~idely used constants, such as T. NIL. i
small numbers,ete. There 1s only one constant page in t!
mach i nee They are kept a lion one page so that they can !
be shnred among a' I FEFs, so that theyui II nnt haveto be -repeated in each FEF's constant area.
This is the address of the local block on the POL,LOCAL BLOCK
and is used for addressing local variable9~
This is the argument pointer i~t~ the POL, and Is
ARG POINTER
used for addressing arguments of the function.
The offset must be 77. The top of the stack isPOL. t
popped off and used as the operand. The otherI
possible values of offset are not currently _used.

(See the FORMAT file for how the POL frame-for each function is divided
up into header, argument block, local block, and intermediate result stack.)Note:
Note:

The first 4 addressing modes are all provided to allo~ an effective
8-bit offset into the FEF.
The same register-offset scheme Is used in the class 11 instructions.

An additional complication in computing the "effective address" comes frominvisible pointers. Once the register_and offset have been used to compute·an initial effective address E, the ~ord at that location is examined (evenif this is an instruction ~hich uses E as a destination.) If the data typeof that ~ord is ftEffective Address Invisible", the pointer field of that word
is used as the effective address E. This is used, for example, to accessWednesday, February 21. 1979

91:95:39

AI:lMDOC;MACAO 28

Page 1.2

value cells of special variables. The FEF "register" ie used, and the locationof the FEF addressed contains an effective address invisible pointer which
points t~ the desired value cell. This scheme saves bits in the instruction,
without requiring the' use of extra in~tructions to make special value cellsaddressable."..
. The destination field is someuhat more complicated. First of all.
befor"e the result is moved to the destination, two "indicators" are set •.
The indicators are each stored as'a bit, and corr~spond to processor statue flags
such as Nand Z on the PDP-11. They are called the ATOM indicator, 'which is set 1f'
the result of the operation is an atom, and the NIL indicator, which ie eet ifthe.resulY is NIL. The class III instructions (BRANCH) may look atthe indicators.
Note: In'actuality, there are not actually any physical indicators."
Instead, the last result computed is saved in·aninternal register, and examinedby the BRANCH instructions. The functional effect is the same.
The destinations are:
DESTFUNCTION-=-==-1:,-=-====-=_e

IGNORE

This is the simplest; the result is simply discarded.
It is still useful, because it sets the flags.
This pushes the destination on the stack, which Is
useful for passing arguments to Class IV instructions, etThis is actually the same thing as TO STACK, but it
is used for storing the next argument to the open
function when it is'computed.
This is used for storing the last argument of theopen function. It also .pushes the result on" the stack,and then it "activates" the open call ~lock. That is.
control will be passed to the function specified by
the last CALL instructi6n, and the va"ue returned by thefunction will be sent to the destinati~n s~ecified by thedestination fieid of the call Instruction. 'Return the result of the instructio~ as the value of ihis
function. (i.e. return from subroutine.)

1TO STACK

2TO NEXT

3TO LAST

4TO RETURN

5TO NEXT, QUOTED This is the same as TO NEXT, except that for error
checking, the USER-CONTROL bit of the word being,pushed is set, telling the called function that It
is getting a quoted argument (if it cares).
(This Is not implemented.)"TO LAST; QUOT~O Analogous.
TO NEXT LIST' "This one is fairly tricky. It is used in· conjunction
with the LIST (Class IV) instruction to efficiently,perform the lisp "LIST" function. It is documented
under the LIST instruction.

S

7

Note: 5 and 6 (the QUOTED) destinatioos have not been implemented as of 11/93/76.
Note: The same DESTINATION field is used by the class IV instructions.
CLASS II:- l.

•Wednesday. February 21, 1979

01:95:39

AI:LMDOC;MACRO 28

73s

OPCODEREGISTEROFFSET

Page 1.3 .

The class II~nst~uctions hav~ n~ destination field; the r~sult of theoperation (if any) Is either pushed on the st~ck (like a destination-TO STACK.
or TO NEXT in a class one instruction) or Is stored at the effective address.
The "register" and offset are used in exactly the same way
as in- the class I instructions, except that the E calculated is sometimes Used
as a destination instead of a source.
.
.. :. The instructions are broken up into three subgroups by the fir~t three bits.
of the opcode [in the microcode they are referred to as Non-destination instructiongroups 1. 2 and 3], and then into the separate instuctions by the next four bits
as fol lo~s: (a "-" In the left hand column-means that this instruction pops. the stack:a "+" Means that it pushes·something onto the stack.)
GRP.
OPCODE FUNCTION

111101

112
3
41111

11
11
11
125S
7e.

*I

ANDXORORc1212

12<1212121212

3EQ
SCOR
SCDOR

45S
713o1312133413+

Not used.
+

1313135S
713>. Adds C(E) to the top of the stack and replaces

the result on the stack.
Subtracts C(E) from the top of the stack.
Analogous.
Analogous.
Analogous.
Analogous.
Analogous.
\These compare C(E) to the top of the stack, and if theI-condition being tested is true,the NIL indicator 19 c1·I otherwise it is set. The stack is popped.
IGet the COR of C(E), and store it in E.
Analogous.
1+Analogous.
1Analogous.
BIND
The cell at E is bound to itself. The linear binding
pdl is used.
BINONIL The cell at E is bound to NIL.
BINDPOP The cell at E is bound to a value popped off the stack.
SETNIL Store NIL in E.
SETZERO Store fixnum e in E.
PUSH-E Push a locative pointer to E on the stack.
MOVEM Move the data on top of the stack to E.
POP
Pop the top of the stack into E.

CLASS III
34

9

BRANCH(14)

OFFSET

CODEII

The class III instruction is for branching. There is a 3 bit Branch
Code field which determines whether the branch happens, and sometimes
uhat to do if it fails. It is decoded as fallo~s:
BRANCH

.

,,"'.
"'

Wednesday, February 21, 1979

CODE

AI:LMDOC;MACRO 28

01:05:39

Page 1.4

FUNCTION

8ALWAVS
Always branch.
NILINO
Branch if the NIL indicator is set, else drop through.
NOT NILIND
Branch·if the NIL indicator is not set, else drop through
NILIND ELSE POP\These two are the same as NILlNO and NOT NILINO,
I except that if the condition fails,.
NOT NILIND ELSE POPI
the stack 1s popped •.
ATOMIND
Branch if the ATOM indicator is set, els8 drop through.
NOT ATOMIND
Analogou~.

123
45S

If the decision la made·to perform the branch the offset, considered as a signed(t~o's complement) offset is added to the PC (i. e. a relative branch, suchas is used by the POP-11). If the offset is 777, however, it is interpreted- as .
meaning that this is a long-distance branch, and the real offset is obtained froin thenext (IG-bit) halfuord. - The PC added to is aluays the incremented PC;· i.e. theaddress of the instruction +1 in' the short case, and the address of theinstruction +2 in the long case.
.
CLASS IV394.

.

-----------------------------------------~------

OESTe

(15)

OPCOOEThe class IV (miscellaneous) instructions take their arguments on thestack, and have a destination field which ~orks the same way as the Class 1
instructions. They all have 15 (octal) in the ope ode bits, and the actual
opcode is in the last 9 bits. Thus there can· be up to 512. of them.
Most of them may be called directlY'from interpretive LISP, and sosome of them duplicate functions available in classes I and II.
_[Note on implementation: since there are f~r too many class )J instructions
to disp~tch on using the dispatch memory of the CONS machine, the starting
locations of the routines are kept in main memory. The location of theb~se of the dispatch table is kept in A-V-MISC-BASE at all_ times.]
Since most of these functions are callable from interpretive level ..
(the normal LISP user sees them), they form part of the nuclear system, andso are documented in the Lisp Machine Nuclear System doc~ment (LMNUC ».
The first.2ee (octal) Class IV operations are not in the dispatch
table in main memory, but are specially checked for •. These are the "LIST"
instructions, ~hich ~ork in ~ooperation ~ith the NEXT-LIST destination.
.
Operations 0-77 are called LIST 0 through LIST 77. The list
<N> instruction allocates N a's in the default consing area [A-CNSADF1~hich is initialized to a COR-NEXT, COR-NIL style list of NILs.
Thenthe instruction pushes three ~ords on the stack:1) A pointer to the ne~ly allocated block,2) Th.e destination foeld of the LIST instruction.
3) A pointer to the ne~ly allocated block (another copy).
Note that the destination, as in the CALL instruction, is not used
instantly; it is saved and used later.After the LIST instruction has been performed, further
instructions can store to destination NEXT-LIST; once the macro-code
computes the next arg of ~hat ~as the LIST function in the source code

pQ..

.."

&{J14

Wednesday. February 21, 1979

01:95:39

AI:LMDOC;MACRO 28

Page 1.5

it stores it to NEXT LIST. What destination NEXT LIST does is: the uord onthe top of the stack is taken to be a pointer to the next allocatedcel I. The pointer is popped. the result of the instruction is stored~here it points, ~nd then the COR of the pointer is pushed back on to the stack.
If the COR ~as NIL ho~ever, then ue must be finished ~ith the LIST
operation, so the NIL 'is popped' off the stack and discarded and a pointerto the ne~ly allocated area (another copy of ~hich uas thoughtfully stored
on the stack) is sent to the destination of the LIST <n> instruction (~hich~as also stored on the stack), and the two remaining words which theLIST <n> pushed are popped off •.
CLASS VOpcodes 1S and 17 (octal) are-not used and reserved for future expansion.
EXAMPLES:
Here is a (very) typical Lisp function, for computing factorials.
'(defun fact (x)(cond ({zerop xli)(t (* x {fact (1- x))))))
This is the macrocode produced by the compiler, typed out by th~ DISASSEMBLEfunction on the Lisp Machine.
22 NOVE O-PDL ARGI0;X
23 MISC O-IGNORE ZEROP
24 SR-NIL 26
25 MOVE O-RETURN 'I
26 MOVE D-POL ARGI0;X
27 CALL O-POL FEF 110;@FUNCTION-CELL FACT
30 MOVE D-POL ARGI9;X31 MISC. D-LAST 132 * POL-POP
33 MOVE D-RETURN POL-POP
The first thing (line 22) is to push argument e {xl onto the stack,and (line 23) check if it is equal to zero. Line 23 uses the.ZEROP miscellaneousfunction, ~hich sets the "indicators" to NIL if the quantity ~as not ZERO.
Line 24 -is a branch instruction which tests the "indicators"; if NIL is set,it~ill branch to 26.
If NIL ~as not set (the number ~aszero). it falls throughto line 25, &..shieh returns the value 1.
.
If the number ~as not zero (the second clause of the COND in the so~rce).
then control passes to line 26, &..shieh pushes X on the POL (ftrst argument tothe multiply on line 32). Next line 27 opens a call to FACT. Line 30 subtracts 1
fr6m X (~ith the 1- miscellaneous function), and moves ihe result to "destin~tion LAST".
This result is thus the first and only argument to the recursive
invok~tion of FACT, the result of &..shieh is left on the POL because of thedestination field of the CALL instrucfion on line 27.
No~ (FACT (1- )()) and X are on the POL, and they are mu I t fp 1 i ed by themulti-ply instruction on line 32. It leaves its result on the POL, to be found by line
33, ~hjch returns the result.