DRAFT
SINGLE PROCESSOR OPERATION - VERSION 3
SINGLE PROCESSOR OPERATION - VERSION 3
DRAGON PROJECT — FOR INTERNAL XEROX USE ONLY
DRAGON PROJECT — FOR INTERNAL XEROX USE ONLY
DRAGON PROJECT — FOR INTERNAL XEROX USE ONLY
2.0 Single Processor Operation
Lissy Bland
Dragon-86-02   Revised March, 1987
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract: This chapter describes the Dragon processor, its accessible registers, the instruction formats, and the Field Unit.
Keywords: Dragon, multiprocessor, IFU, EU, Field Unit, instruction formats, operand specification, addressing modes, arithmetic operations, logical operations
FileName: [Indigo]<Dragon>Documentation>Princops>SingleProcOp.tioga, .ip
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304
2.0 Single Processor Operation
A Dragaon Processor consists of an Instruction Fetch Unit (IFU) and an Execution Unit (EU). The IFU and EU form a single logical entity and constitute the fixed-point execution engine of a Dragon Processor. The IFU reads and decodes a stream of variable-length machine instructions. It then directs the EU to perform the arithmetic, logical, shifting, fetching, and storing operations required. The IFU and EU make use of a pipeline which is 4 machine cycles long. As an instruction progresses through the pipeline, less and less work is done in the IFU and more is performed in the EU.
Each Dragon Processor contains a 128-registers for use in local frames, 12 registers for constants, and 16 auxiliary registers. The following figure shows the logical organization of a Dragon Processor's registers.
IFU/EU - A Logical Model
[Artwork node; type 'ArtworkInterpress on' to command tool]
The names of the registers come from the enumerated type, ProcessorRegister, which specifies logical names for physical registers. Here is a Cedar definition for ProcessorRegister:
ProcessorRegister: TYPE = MACHINE DEPENDENT {
Stack (0) the EU Stack (128 registers)
Spare (128) not used; possibly non-existent register
ToKBus (129) send result on K bus to IFU
MAR (130) MemoryAddressRegister
Field (131) Field register
Constants (132)  Base of EU constant register (12 regs)
AuxRegs (144) Base of EU aux registers (16 regs)
[160..239] don't correspond to any existing registers
YoungestStatus (240) youngest L in IFU stack
YoungestPC (241) youngest PC in IFU stack
EldestStatus (242) eldest L in IFU stack
EldestPC (243) eldest PC in IFU stack (rd removes, wt adds)
SLimit (244) stack limit register
[245..255] don't correspond to any existing registers
};
Some of the elements enumerated in ProcessorRegister are accessed from the IFU; some are accessed from the EU. The following sections on the IFU and EU provide explanations of these elements, as appropriate.

2.1 Instruction Fetch Unit
The IFU contains a small stack of the most recent procedure contexts. A procedure context for the IFU includes a program counter (PC) and one word of status information (Status). Status contains the following information: 1) the version number of the Dragon Processor which is a constant, 2) flags, and 3) an index, L, into the EU stack which is the base register of the local variables. Here is the Cedar definition for Status:
Status: TYPE = MACHINE DEPENDENT RECORD [
version (0: 00..07): [0..255] ← 0,
padBits (0: 08..13): [0..63] ← 0,
userMode (0: 14..14): BOOL ← FALSE, -- TRUE => user, FALSE => kernel
trapsEnabled (0: 15..15): BOOL ← FALSE,
padByte (0: 16..23): [0..255] ← 0,
LBase (0: 24..31): [0..255] ← 0 ]; -- EU local frame base
Five of the locations in the IFU may be read and written using the LIP (Load from Internal Processor register) and SIP (Store to Internal Processor register) instructions. These locations include the top and bottom of the stack (YoungestPC, YoungestStatus, EldestPC, EldestStatus) as well as the SLimit. Definitions for the IFU registers are given below:
PC (Program Counter)
PC is the program counter (a byte address). Instruction space is limited to 232 bytes (roughly 4 gigabytes), even though the full Dragon address space is 232 words.
S (Stack pointer)
S is a 7-bit index into Stack.
SLimit (Stack Limit)
SLimit gives the limit for S. A stack overflow occurs when an instruction modifies S in such a way that the new value of S is in the range [SLimit..SLimit+16).
L (Local frame base)
L is a 7-bit index into Stack which serves as the base register for the current local frame. The first 16 registers at or above L are easily addressable through the instruction set.
EldestStatus
EldestStatus contains the status word for the oldest procedure context in the IFU stack.
EldestPC
EldestPC is read by the LIP (Load from Internal Processor register) instruction. A read does the following:
Stack[S+1] ← IFUStack[EldestPC]; S ← S + 1;
Eldest ← Eldest + 1;
EldestPC is written by the SIP (Store to Internal Processor register) instruction:
IFUStack[EldestPC - 1] ← Stack[S]; S ← S — 1;
Eldest ← Eldest — 1;
Eldest points to PC/Status pairs (64 bits). Each time Eldest is incremented, it points to a location that is 64 bits from the previous one.
If traps are enabled and there are already 11 entries in the IFU Stack, any instruction which would cause another entry will instead generate an IFU overflow trap. Upon entry into the overflow routine, the PC and Status of the offending instruction are recorded as the last values in the IFU Stack.
YoungestStatus
YoungestStatus contains the status word of the most recent procedure context in the IFU stack.
YoungestPC
YoungestPC contains the PC of the most recent procedure context in the IFU stack. This is useful in trap routines that need to examine code, or in cases where the trap routine wants to skip the instruction that caused the trap.
Note: Arithmetic involving S and L is always performed modulo the size of the EU stack, without detection of underflow or overflow; it produces values in the range [0..127]. If traps are enabled and the stack pointer S is in the range [SLimit..SLimit + 16) at the end of any instruction, an EU stack overflow trap occurs.
2.1.1 The Instruction Fetch/Execute Loop
Given the following definitions:
------------------- instructionLength ----------------
opcode | a | b | g | d
The instruction fetch/execute loop has the following semantics:
Do
opcode ← FetchByte[PC];
instructionLength ← InstructionBytes[opcode]; -- 1, 2, 3, 5 --
nextPC ← PC + instructionLength;
If instructionLength > 1 then a ← FetchByte[PC +1];
If instructionLength > 2 then b ← FetchByte[PC +2];
If instructionLength > 3 then g ← FetchByte[PC +3];
If instructionLength > 4 then d ← FetchByte[PC +4];
DoInstruction[];
PC ← nextPC;
EndLoop;
Where PC is the PC of the current instruction. And nextPC can be incremented by DoInstruction[].
2.2 The Execution Unit
The Execution Unit (EU) contains a 32-bit Arithmetic Logic Unit (ALU) and a Field Unit (FU) for shifting, masking and inserting fields. The EU contains the address and data pathway to its data cache (or caches) but does not control these caches. It also contains several multiplexers to select operands and implement pipeline short-circuits.
The Execution Unit contains a bank of registers that are 32 bits wide. These registers contain the most recent elements of the data stack for a process. There are also registers that contain constants, as well as special purpose quantities. This architecture permits most elementary operations involving local variables to be performed in 1 EU cycle. However, this architecture requires special attention be paid to migrating the contents of a process stack between registers and memory.
The EU has the following registers:
Stack
Stack indicates the 128 registers used for local variables in recent local frames.
Locals
Locals indicates the 16 local registers in Stack used for the current local frame. The L register in the IFU points at the base of Locals. When the local frame has fewer than 16 registers, the excess locals are synonomous with lower positions on the Stack.
AuxRegs
AuxRegs indicates the 16 auxilliary registers. Most of these registers will be used for the runtime support of higher-level languages. It is illegal to write into the first 8 auxiliary registers when in User mode.
Constants
Constants indicates the 12 registers normally used to hold constants. Although these registers are not really constant as far as the hardware is concerned, they are used to hold constants for runtime environments. They are more general in that they can be used in more addressing modes than the AuxRegs. It is illegal to write any constant in User mode.
Field (Field unit register)
Field indicates a special register which can be loaded by the FSDB instruction; the value in this register is used by the RFU (Register Field Unit) instruction to control the Field Unit.
MAR (Memory Address Register)
The MAR register is loaded with the memory address whenever an EU memory reference is delayed by the Wait signal from the cache. In the event of a page or write protect fault, MAR must be read by the fault routine before it issues any EU memory references.
ToKBus
ToKBus is loaded with the value being sent from the EU back to the IFU on SFC, SFCI, SJ, and SIP instructions. Writing this register with SIP serves no useful purpose and might interfere with normal use of the K bus.
Carry
A 1-bit register which is discussed in the Chapter 2.2.1.1 entitled, Arithmetic Operations, below.
2.2.1 Arithmetic and Logical Unit (ALU)
2.2.1.1 Arithmetic Operations
The Dragon Processor provides efficient instruction-level support for 32-bit 2's-complement integer arithmetic. N-precision 2's-complement arithmetic is also supported but needs a little instruction level support. In constrast, 32-bit cardinal arithmetic and 1's-complement arithmetic are only incidentally supported.
Arithmetic operands are treated in one of three ways: as signed numbers (or twos-complement integers) in the range [-231..231); as unsigned numbers (or cardinals) in the range [0..232); or as Lisp integers in the range [-229..229), where the top three bits must be either all 0's or all 1's.
These different interpretations of the operands require different handling of the Carry and overflow conditions. Accordingly, five distinct operations are defined for addition/subtraction operations:
Unsigned
On addition, the 1-bit Carry supplies the adder's carry-in and is loaded from the adder carry-out; on subtraction, the complement of Carry bit supplies the adder carry-in, and Carry is loaded from the complement of the adder's carry-out. No traps are taken. The only instructions using this kind of arithmetic are RUADD and RUSUB, and executing one of these operations is the only way to load Carry with the value 1. Unsigned (= cardinal) arithmetic is used for the low-order terms of multiple-precision arithmetic.
Signed
On addition, the Carry bit supplies the carry-in, and on subtraction it supplies the complement of carry-in, just as in Unsigned arithmetic. Carry is always loaded with 0 at the end of the instruction. Overflow, which causes a Trap, is defined to occur when the numerical result is not in the range [-231..231), or, equivalently, when the carry out of bit 0 is unequal to the carry out of bit 1. The integer overflow trap, like other traps, occurs before any machine state has been modified, so no information is lost when it is taken. Many instructions use this kind of arithmetic.
Lisp
The Carry is not used as an input, and is always set to 0. If either of the operands or the result is not in the range [-229..229) (top three bits being all 0s or all 1s), a Lisp NaN (Not a Number) trap is taken. This trap instruction is executed by software. It has no side effects, so no information is lost when it is taken.
Small Integer
Integers in the range [0..127]. The Carry bit is neither used nor set. No overflow checking is performed, and no traps can result. The small integer interpretation is used exclusively for operations involving S or L that are performed modulo the size of the EU stack.
Vanilla
The 1-bit Carry flip-flop is not used as an input and is not modified. No traps are taken. The only instructions using this kind of arithmetic are RVADD and RVSUB, which are intended for situations where overflow may occur but does not represent an error.
Instructions facilitating multiply and divide do not exist but will be provided later by an Arithmetic Unit (AU) that will be part of every Dragon processor. The AU will also support both 32-bit and 64-bit IEEE standard floating point arithmetic. It will be controlled from the P bus using IO instructions. In all other respects the AU is not presently defined.
The Carry bit may only be addressed indirectly. To read the Carry bit into Rc execute a RUADD instruction: Stack[S+1] ← Constant[0] + Constant[0]; S ← S + 1. This will yield a 1 on the top of Stack if the Carry was set to 1, and a 0 if it was not. To set the Carry bit, load the saved Carry bit onto the Stack and execute a RUSUB instruction: Stack[S] ← Constant[0] — Stack[S]; S ← S — 1. This instruction will set the Carry bit in the EU and a word will be discarded from Stack.
The notation A-B-Carry is an abbreviation for A+~B+~Carry, where ~B is the 32-bit complement of B, and ~Carry is the 1-bit complement of Carry. The notation A-B, where A and B are 32-bit quantities, denotes the 3-way, signed addition of A+~B+1. It is worth noting the clever trick of complementing the value in Carry for subtraction, which allows the signed subtraction instructions also to be used for the high-order subtraction of two n-precision numbers.
Lisp arithmetic is intended for an implementation in which pointers to storage and numbers occur within the same 32-bit space. For example, it is tentatively proposed that the 32-bit address space be divided according to the high-order 3 bits of an address as follows:
7 Negative Lisp integers
6 Negative floating point numbers
5 Negative floating point numbers
4 Cons storage
3 Ref storage
2 Positive floating point numbers
1 Positive floating point numbers
0 Positive Lisp integers and Kernel
With this arrangement, arbitrary-precision integers can be implemented as follows: An integer in the range 2[-229..229) is encoded as a Lisp integer; integers outside this range are stored in a vector in Ref space where the first word of an entry gives the number of 32-bit words in the integer, and words 1 to n are the n-precision integer. Under the assumption that integers in the range [-229..229 ) are vastly more common than those outside this range, addition and subtraction are compiled, respectively, into Lisp add or subtract instructions, which will trap and be interpreted by the NaN trap software in the uncommon case. (Arbitrary-precision floating point numbers embedded in pointers like the Lisp integers have also been discussed, as suggested in this table.)
To support 32-bit cardinal arithmetic, instructions which trapped on adder carry-out = 1 (i.e., on Cardinal overflow) would be needed; these do not exist, though the Vanilla or Unsigned arithmetic operations might be used. It is possible to carry out cardinal addition and subtraction as follows: First, complement the sign bit of each operand. Then execute an integer operation. Finally, complement the sign bit of the result. It can easily be shown that a cardinal comparison is equivalent to an integer comparison with the sign bit of the two operands complemented.
2.2.1.2 Logical Operations
Logical operations are performed on 32-bit quantities that are treated as arrays of 32 booleans. For example, the Or instruction reads: Stack[S-1] ← Stack[S] or Stack[S-1]; S ← S — 1. It performs a logical OR for each of the 32 bit positions.
2.2.1.3 Comparative Operations
Comparative operations are performed on 32-bit signed quantities. The Carry bit is not used or set. For example, the Jump Not Equal Byte Byte instruction reads: If Stack[S] ~= zExt[literal], then PC ← PC + sExt[displacement]; S ← S — 1. Note: Numbers that are zero-extended are understood to be positive (see the definition of zExt in Section 2.3.
2.2.2 Instruction Execution and Sequencing
2.2.3 Field Unit Operations
The field unit enables shifting, rotation, insertion, and masking of fields. It takes two words, and produces a one word result, under the control of a field descriptor. It is supplied either through a 16-bit constant or through the Field register in the EU; it has the following format:
0 1 2 3 4 10 15
r1|r2|r3|insert| width | shift
Note: Insert is not drawn to scale.
The four fields are defined as follows:
r1 - r3
r1 - r3 are bits that are not currently used and must be set to zero.
insert
insert governs the choice of background and low bits of the mask. If insert is false the output of the instruction is the logical And of the width and shift. If insert is true the instruction performs an insert operation.
width
Width gives the number of right-justified one's in the mask. (If width = 0, there are no one's. If width = 32, the mask is entirely one's.)
shift
Shift gives the number of bits to left-shift. the double word.
A Cedar program, entitled FieldUnit, describes the operation of the Field Unit. Here are definitions used by the FieldUnit program:
DragonTooth: CEDAR DEFINITIONS = {
Dragon teeth determine how big dragon bytes are.
Bit: TYPE = MACHINE DEPENDENT {zero (0), one (1)};
Zero: Bit = zero;
One: Bit = one;
BitsPerWord: CARDINAL = 32;
BitIndex: TYPE = CARDINAL [0..BitsPerWord);
FieldWidth: TYPE = CARDINAL [0..BitsPerWord];
ShiftIndex: TYPE = CARDINAL [0..BitsPerWord];
Word: TYPE = ARRAY BitIndex OF Bit;
ZeroesWord: Word = ALL[Zero];
OnesWord: Word = ALL[One];
}.
Here is the user interface to the FieldUnitImpl procedure:
DIRECTORY
DragonTooth;
FieldUnit: CEDAR DEFINITIONS = {
FieldDescriptor: TYPE = MACHINE DEPENDENT RECORD [
r1, r2, r3: DragonTooth.Bit ← DragonTooth.Zero,
Not currently used (reserved) but must be set to 0.
insert: BOOL ← FALSE,
The choice of background and low bits of mask.
width: DragonTooth.FieldWidth ← LAST[DragonTooth.FieldWidth],
When insert is FALSE (the easy case), this is the width of the field being extracted.
When insert is TRUE (the hard case), this is the width of the field plus the shift amount.
Note that width should always be greater than or equal to the shift amount to assure that extraction takes place from the left Word. If the width is smaller than the shift amount the behavior of the Field Unit is and will remain unspecified.
shift: DragonTooth.ShiftIndex ← FIRST[DragonTooth.ShiftIndex]
the number of bits to left-shift the concatenation of left and right.
];
Operate: PROCEDURE [left, right: DragonTooth.Word, fieldOp: FieldDescriptor] RETURNS [output: DragonTooth.Word];
There are two cases,
either
double-word-left-shifting left and right and returning some right-justified field from the result. This case is also useful for single-word-left-shifting (ZeroesWord as right), rotating (use the same value for left and right), and right-shifting (ZeroesWord as left, and left-shift by BitsPerWord minus the desired right shift).
or
extracting a right-justified field from left and inserting it into the middle of right.
}.
Here are definitions for procedures called by the FieldUnit program:
DragonToothOps: CEDAR DEFINITIONS = {
Operations on Dragon bits.
BitWiseAnd: PROCEDURE [this, that: DragonTooth.Word] RETURNS [DragonTooth.Word];
Form the logical AND of the bits in the two words.
BitWiseOr: PROCEDURE [this, that: DragonTooth.Word] RETURNS [DragonTooth.Word];
Form the logical OR of the bits in the two words.
BitWiseNot: PROCEDURE [this: DragonTooth.Word] RETURNS [DragonTooth.Word];
Form the logical NOT of the bits in the word.
BitWiseMultiplex: PROCEDURE [ifZero, ifOne, selector: DragonTooth.Word] RETURNS [DragonTooth.Word];
Use the bits of selector to choose the corresponding bits from either ifZero or ifOne.
DoubleWordShiftLeft: PROCEDURE [left, right: DragonTooth.Word, shiftAmount: DragonTooth.ShiftIndex] RETURNS [DragonTooth.Word];
Shifts two words left by shiftAmount and returns the resulting leftmost word.
}.
Here is the implementation of the FieldUnit program:
DIRECTORY
FieldUnit,
DragonTooth USING [Word, ZeroesWord, OnesWord],
DragonToothOps USING [BitWiseAnd, BitWiseMultiplex, DoubleWordShiftLeft];
FieldUnitImpl: CEDAR PROGRAM
IMPORTS DragonToothOps
EXPORTS FieldUnit = {
Operate: PUBLIC PROCEDURE [left, right: DragonTooth.Word, fieldOp: FieldUnit.FieldDescriptor] RETURNS [output: DragonTooth.Word] = {
There are two cases,
either
double-word-left-shifting left and right and returning some right-justified field from the result. This case is also useful for single-word-left-shifting (ZeroesWord as right), rotating (use the same value for left and right), and right-shifting (ZeroesWord as left, and left-shift by BitsPerWord minus the desired right shift).
or
extracting a right-justified field from left and inserting it into the middle of right.
widthMask: DragonTooth.Word ← DragonToothOps.DoubleWordShiftLeft[left: DragonTooth.ZeroesWord, right: DragonTooth.OnesWord, shiftAmount: fieldOp.width];
A mask for a right-justified field of length fieldOp.width.
shifted: DragonTooth.Word ← DragonToothOps.DoubleWordShiftLeft[left: left, right: right, shiftAmount: fieldOp.shift];
shift the contents of the field into position.
IF fieldOp.insert
THEN {
This is the hard case, where a right-justified field is extracted from left and inserted into the middle of right. In this case the operands aren't named very well.
`left' holds the right-justified source bits to be inserted,
and so `shifted' holds the source bits shifted into alignment with the destination bits.
`right' holds the word into which the field is inserted,
`widthMask' holds a mask for the field plus `shift' extra bits on the right.
`shiftMask' (defined below) will be used to mask off those extra bits.
The mask for the field is constructed and then used to extract the source bits from `shifted' and to extract the bits around the destination from `right'.
shiftMask: DragonTooth.Word ← DragonToothOps.DoubleWordShiftLeft[left: DragonTooth.OnesWord, right: DragonTooth.ZeroesWord, shiftAmount: fieldOp.shift];
fieldMask: DragonTooth.Word ← DragonToothOps.BitWiseAnd[widthMask, shiftMask];
note that if fieldOp.shift e fieldOp.width then fieldMask is all 0's.
output ← DragonToothOps.BitWiseMultiplex[ifZero: right, ifOne: shifted, selector: fieldMask];
the source bits from `shifted' and the surrounding bits of `right'.
}
ELSE {
The easy case, extract a right-justified field from the shifted Words.
output ← DragonToothOps.BitWiseAnd[shifted, widthMask];
};
};
}.
2.3 Instruction formats
There are twelve instruction formats. They vary in length from 1 to 5 bytes and specify operations on from 0 to 3 operands. Ten of the formats have an opcode occupying 8 bits. Two formats have a 4-bit opcode followed by a 4-bit specification for an operand. The operands may be specified implicitly or explicitly; they may be registers or be determined from an index register and an offset. In all cases the way in which the operands are specified is determined implicitly from the opcode.
Here are brief definitions of terms and abbreviations used in describing the instruction formats and instructions:
Implicit (abbreviated I) — The location of the operands are implicit in the opcode of the instruction. Some of the instructions specify some operands implicitly and some operands explicitly. The term implicit is used to describe the format for a particular instruction if and only if no operands are designated explicitly.
Literal (abbreviated L)— The instruction contains the operand itself, rather than an address or other information describing where the operand is. A frequently-used synonym for the term literal is immediate.
Register (abbreviated R) — The address fields of the instruction specify register operands.
Indexed Register (abbreviated X) — Indexed-Register instructions have an operand whose address is the sum of an offset and the contents of a register.
Mem — memory word
Mem[addr] — the contents of that register or memory at address addr
Aux — auxiliary register
Const — constants register
ProcReg — processor register
ProcBus — processor bus
FieldDesc — field unit descriptor
FieldOp — field operation
FP — floating point
Offset — offset indicates a non-negative byte displacement.
Displacement — displacement indicates a signed byte displacement.
sExt[x] — The signed magnitude of x, a 2's complement number, is extended to the width of the destination.
zExt[x] — The unsigned (positive) magnitude of x is extended of the width of the destination.
m — an integer in the range [0..12)
n — an integer in the range [0..16)
Implicit Operand Specification:
I Implicit
0 7
opcode
This format is used to perform stack operations. The operand (if any) is implicitly specified by in the opcode.
Example: Add. ADD: Stack[S-1] ← Stack[S] + Stack[S-1] + Carry; Carry ← 0; S ← S — 1;
Literal Operand Specification:
LB Literal Byte
0 8 15
opcode | literal
For LB instructions the literal byte following the opcode is used in 1 of 3 ways. It is zero-extended to 32 bits for stack operations: operand ← zExt[literal]. It is used as a 32-bit signed displacement when computing a new PC: operand ← sExt[literal]. And, it is used to calculate a displacement from S or L: operand ← literal. In calculating displacement from S or L, all arithmetic is performed modulo the size of the EU Stack.
Example: Add Byte. ADDB: Stack[S] ← Stack[S] + zExt[literal] + Carry; Carry ← 0.
LH Literal Halfword
0 8 23
opcode | literal
For LH instructions the literal halfword following the opcode is used in 1 of 3 ways. It is zero-extended to 32 bits for stack operations: operand ← zExt[literal]. It is used as a 32-bit signed displacement when computing a new PC: operand ← sExt[literal]. The low-order 13 bits are used as a descriptor for Field Unit operations: operand ← Low13Bits[literal].
Example: Load Immediate Double Byte. Stack[S+1] ← zExt[literal]; S ← S + 1.
LW Literal Word
0 8 39
opcode | literal
For LW instructions the operand is the 32-bit literal quantity following the opcode, operand ← literal.
Example: Load Immediate Quad Byte. LIQB: Stack[S+1] ← literal; S ← S + 1.
LBD Literal Byte Displacement
0 8 16 23
opcode | literal | displ
LBD instructions have two operands. The first operand is a literal used for comparison with the top of the stack, operand1 ← zExt[literal]. The second operand is a signed displacement, operand2 ← sExt[displacement], used in computing the new PC, PC ← PC+operand2.
Example: Jump Equal Byte Byte. JEBB: If Stack[S] = zExt[literal] then PC ← PC + sExt[displacement]; S ← S — 1.
LIO Literal Input/Output
0 8 16 23
opcode | address | PCommand
The LIO format is used exclusively for instructions that perform input or output. The IO instructions have two explicit operands and one or two implicit operands. The first explicit operand contains the address that is to be read or written. The second explicit operand contains the actual PBus command to be performed.
The implicit operands are taken from Stack. If the instruction performs a read, it reads data into the location specified by the first implicit operand, and may use a second implicit operand to increment the address information contained in the explicit address field. If the instruction performs a write, the first implicit operand contains the data to be written, and may use a second implicit operand to increment the address information contained in the explicit address field.
Example:
IsRead[PCommand] => Stack[S+1] ← Dispatch[Address, PCommand]; S ← S + 1; IsWrite[PCommand] => [] ← Dispatch[Address, Stack[S], PCommand]; S ← S - 1;
Register Operand Specification:
The Registers to Register, Quick Register and Register Displacement formats take operands from registers. The Registers to Register format selects a destination operand (Rc) and 2 source operands (Ra and Rb). The Quick Register format is a tighter form of the Registers to Register format; it provides the same decoding as the Registers to Register format for the Rb operand, but limits the possibilities for Ra and Rc to 4 different pairs of locations. The Register Displacement format provides the same decoding as the Registers to Register format for the Rb operand and gives 4 possibilities for the second operand, Rs. (Rs stands for short source register.)
The algorithms used to select Rc, Ra and Rb, and Rs are given here by the CEDAR program, OperandSpeciferImpl.
Here are the definitions used by the CEDAR implementation.
OperandSpecifier: CEDAR DEFINITIONS = {
Here are the type definitions used in accessing Locals[], AuxRegs[] and Constants[]:
AuxiliaryRegisterIndex: TYPE = CARDINAL [0..15];
LocalRegisterIndex: TYPE = CARDINAL [0..15];
ConstantRegisterIndex: TYPE = CARDINAL [0..11];
ShortConstantIndex: TYPE = ConstantRegisterIndex [0..1];
Some types for strong type checking.
SourceDeltaS: TYPE = INTEGER [-1..0];
DestinationDeltaS: TYPE = INTEGER [0..+1];
Here are the abstract locations and specifiers for source operands (Ra and Rb):
SourceLocation: TYPE = {AuxReg, Local, Constant, Top, Under};
SourceSpecifier: TYPE = RECORD [
SELECT location: SourceLocation FROM
AuxReg => [aux: AuxiliaryRegisterIndex],
Local => [local: LocalRegisterIndex],
Constant => [constant: ConstantRegisterIndex],
Top => [deltaS: SourceDeltaS],
Under => [deltaS: SourceDeltaS],
ENDCASE
];
Here are the abstract locations and specifiers for destination operands (Rc):
DestinationLocation: TYPE = {AuxReg, Local, Constant, Top, Under, Push};
DestinationSpecifier: TYPE = RECORD [
SELECT location: DestinationLocation FROM
AuxReg => [aux: AuxiliaryRegisterIndex],
Local => [local: LocalRegisterIndex],
Constant => [constant: ConstantRegisterIndex],
Top => [-- deltaS: 0 --],
Under => [-- deltaS: 0 --],
Push => [-- deltaS: 1 --],
ENDCASE
];
Here are the abstract locations and specifiers for shortCASpecifier operands (Rc and Ra):
ShortCASpecifier: TYPE = RECORD [
location: ShortCASelector
];
These are the supporting definitions that reflect the mappings between bit patterns and names
SourceSelector: TYPE = MACHINE DEPENDENT {
Constant0 (0), Constant1, Constant2, Constant3,
Constant4 (4), Constant5, Constant6, Constant7,
Constant8 (8), Constant9, Constant10, Constant11,
Top (12), Under, PopTop, PopUnder (15)
};
DestinationSelector: TYPE = MACHINE DEPENDENT {
Constant0 (0),  Constant1,  Constant2,  Constant3,
Constant4 (4),  Constant5,  Constant6,  Constant7,
Constant8 (8),  Constant9, Constant10,  Constant11,
Top (12),  Under,  Push,  Reserved (15)
};
ShortCASelector: TYPE = MACHINE DEPENDENT {
TopAtop(0), PushAtop, PushA0, PushA1 (3)
};
ShortSourceSelector: TYPE = MACHINE DEPENDENT {
Constant0 (0), Constant1, Top, PopTop (3)
};
Translations from bit patterns to operand specifiers
SourceOperand: PUBLIC PROCEDURE [auxFlag: BOOL, operandFlag: BOOL, operandSelector: SourceSelector] RETURNS [SourceSpecifier];
DestinationOperand: PUBLIC PROCEDURE [auxFlag: BOOL, operandFlag: BOOL, operandSelector: DestinationSelector] RETURNS [DestinationSpecifier];
ShortCAOperand: PUBLIC PROCEDURE [operandSelector: OperandSpecifier.ShortCASelector] RETURNS [C: OperandSpecifier.DestinationSpecifier, A: OperandSpecifier.SourceSpecifier];
ShortSourceOperand: PUBLIC PROCEDURE [operandSelector: ShortSourceSelector] RETURNS [SourceSpecifier];
}.
Here is the code that actually selects the registers to be used for destination operands (Rc), source operands (Ra and Rb) and short source operands (Rs):
DIRECTORY
OperandSpecifier;
OperandSpecifierImpl: CEDAR PROGRAM
EXPORTS OperandSpecifier = {
SourceOperand: PUBLIC PROCEDURE [auxFlag: BOOL, operandFlag: BOOL, operandSelector: OperandSpecifier.SourceSelector] RETURNS [OperandSpecifier.SourceSpecifier] = {
IF NOT operandFlag
THEN
IF auxFlag
THEN RETURN [[AuxReg[aux: ORD[operandSelector]]]]
ELSE RETURN [[Local[local: ORD[operandSelector]]]]
ELSE
SELECT operandSelector FROM
IN [Constant0..Constant11] =>
RETURN [[Constant[constant: ORD[operandSelector]]]];
Top =>
RETURN [[Top[deltaS: 0]]];
Under =>
RETURN [[Under[deltaS: 0]]];
PopTop =>
RETURN [[Top[deltaS: -1]]];
PopUnder =>
RETURN [[Under[deltaS: -1]]];
ENDCASE =>
ERROR;
};
DestinationOperand: PUBLIC PROCEDURE [auxFlag: BOOL, operandFlag: BOOL, operandSelector: OperandSpecifier.DestinationSelector] RETURNS [OperandSpecifier.DestinationSpecifier] = {
IF NOT operandFlag
THEN
IF auxFlag
THEN RETURN [[AuxReg[aux: ORD[operandSelector]]]]
ELSE RETURN [[Local[local: ORD[operandSelector]]]]
ELSE
SELECT operandSelector FROM
IN [Constant0..Constant11] =>
RETURN [[Constant[constant: ORD[operandSelector]]]];
Top =>
RETURN [[Top[-- deltaS: 0 --]]];
Under =>
RETURN [[Under[-- deltaS: 0 --]]];
Push =>
RETURN [[Push[-- deltaS: +1 --]]];
Reserved =>
ERROR;
ENDCASE =>
ERROR;
};
Short encoding for C and A operands of the QR format instructions. The B operand is always a general operand.
ShortCAOperand: PUBLIC PROCEDURE [operandSelector: OperandSpecifier.ShortCASelector] RETURNS [C: OperandSpecifier.DestinationSpecifier, A: OperandSpecifier.SourceSpecifier] = {
SELECT operandSelector FROM
TopAtop =>
RETURN [[Top[--deltaS: 0--]], [Top[deltaS: 0]]];
PushAtop =>
RETURN [[Push[--deltaS: 1--]], [Top[deltaS: 0]]];
PushA0 =>
RETURN [[Push[--deltaS: 1--]], [Constant[constant: 0]]];
PushA1 =>
RETURN [[Push[--deltaS: 1--]], [Constant[constant: 1]]];
ENDCASE =>
ERROR;
};
ShortSourceOperand: PUBLIC PROCEDURE [operandSelector: OperandSpecifier.ShortSourceSelector] RETURNS [OperandSpecifier.SourceSpecifier] = {
SELECT operandSelector FROM
Constant0 =>
RETURN [[Constant[constant: 0]]];
Constant1 =>
RETURN [[Constant[constant: 1]]];
Top =>
RETURN [[Top[deltaS: 0]]];
PopTop =>
RETURN [[Top[deltaS: -1]]];
ENDCASE =>
ERROR;
};
}.
RRR Registers to Register
0 8 12 16 20 23
opcode | F[] | b | c | a
Instructions in the RRR format perform an operation with the contents of 2 registers and store the result in a third register, Rc ← Ra op Rb. F[] contains four flags that determine which registers the three operand specifiers, a, b, and c, refer to. Here is a magnified view of bits 8-11 of the RRR format:
8 9 10 11
aOpt|cOpt|bOpt|auxFlag
The aOpt flag and auxFlag control the meaning of the third operand, a. The cOpt flag and auxFlag control the meaning of the second operand, c. And bOpt and auxFlag control the meaning of the first operand, b. The unexpected ordering of the boolean flags allows the RRR format to overlap to the maximum degree with the Quick Register (QR) and and Register Displacement (RD) formats. These formats have only one operand, b, following the flags.
Using the code for operand specifiers given above, Ra, Rb and Rc are specified by the following procedure calls:
Ra: OperandSpecifier.SourceSpecifier ← OperandSpecifier.SourceOperand[auxFlag: F[4], operandFlag: F[1], operandSelector: a];
Rb: OperandSpecifier.SourceSpecifier ← OperandSpecifier.SourceOperand[auxFlag: F[4], operandFlag: F[3], operandSelector: b];
Rc: OperandSpecifier.DestinationSpecifier ← OperandSpecifier.DestinationOperand: [auxFlag: F[4], operandFlag: F[2], operandSelector: c];
Effects on deltaS are accumulated as registers are specified. The final value contained in deltaS is added to the Stack pointer, S, after all registers have been specified.
Example: Register OR. ROR: Rc ← Ra or Rb.
Here are three of the most significant uses of the RRR instruction:
Rb Rc Ra
Locals[0..15] ← Locals[0..15] @ Locals[0..15];
opcode |0|0|0|0|Locals |Locals |Locals
Instructions using this combination of booleans include: RADD, RAND, ROR, RRX, RSUB, RUADD, RUSUB, RVADD, RVSUB, RXOR
Stack[S] ← Stack[S] @ Stack[S];
opcode |1|1|1|0| Top | Top | Top
This instruction is an optimization of DUP followed by an operation. It saves a memory reference.
Stack[S-1] ← Stack[S] @ Constants[0..11].
S ← S -1;
opcode |1|1|1|0| Const | Under | PopTop
This is a general case of EXDIS.
QR Quick Register
0 8 10 12 15
opcode |c|a|F[]| b
The QR format is a tighter encoding of the RRR format. Rb is specified in the same manner that it is specified in the RRR format. Ra and Rc can take on 4 different pairs of values:
Stack[S] ← Stack[S] @ Rb;
opcode |0|0|F[]| b
Stack[S+1] ← Stack[S] @ Rb;
S ← S +1.
opcode |0|1|F[]| b
Stack[S+1] ← Constant[0] @ Rb;
S ← S +1.
opcode |1|0|F[]| b
Stack[S+1] ← Constant[1] @ Rb;
S ← S +1.
opcode |1|1|F[]| b
Instructions in the QR format take less space than instructions in the RRR format; consequently, more of them can fit into the IFU cache. QR instructions will execute faster than RRR instructions and should be used when possible.
Using the code for operand specifiers given above, Ra, Rb and Rc are specified by the following procedure calls:
Ra & Rc: OperandSpecifier.ShortCASpecifier ← OperandSpecifier.ShortCAOperand[operandSelector: ShortCASelector];
Rb: OperandSpecifier.SourceSpecifier ← OperandSpecifier.SourceOperand[[auxFlag: F[2], operandFlag: F[1], operandSelector: b];
Example: Quick Lisp SUBtract. QLSUB: Stack[S] ← Stack[S] — Rb. Carry ← 0.
RD Register Displacement
0 8 10 12 16 23
opcode |Rs|F[]| b | displ
This format provides access to 3 operands, Rs (short source register), Rb, and a displacement. Instructions using this format compare Rs and Rb and jump to the PC given by PC+sExt[displacement] if the indicated comparision of Rs with Rb is true.
Using the code for operand specifiers given above, Rs and Rb are specified by the following procedure calls:
Rs: OperandSpecifierShort.SourceSpecifier ← OperandSpecifier.ShortSourceOperand[operandSelector: Rs];
Rb: OperandSpecifier.SourceSpecifier ← OperandSpecifier.SourceOperand[[auxFlag: F[2], operandFlag: F[1], operandSelector: b];
Example: Register Jump Equal Byte. RJEB: If Rs = Rb then PC ← PC + sExt[displacement].
LR Locals Register
0 4 7
op | n
LR instructions have a 4-bit opcode. The next 4 bits are an index into Locals and specify the operand, operand = Locals[n].
Example: Store Register n. SRn: Locals[n] ← Stack[S]; S ← S — 1. { :n| 0 <= n < 16}.
Indexed Register Operand Specification:
XO Index Register Offset
0 4 8 15
op | n | offset
zExt(offset)
This format provides access to an operand at a given offset from the index register, Locals[n]. The operand is Mem[Locals[n]+ zExt[offset]].
Example: SRIn: Stack[S+1] ←Mem[Locals[n] + zExt[offset]]; S ← S + 1. {:n| 0 <= n < 16}
XRO Index-Register Register-Offset
0 8 16 20 23
opcode | offset | regA | regB
This format addresses 2 operands. The first operand specifies a Locals register, Locals[regA]. The second operand is used in 2 ways: it can be used to specify a memory location that is the sum of a Locals register and an offset, Mem[Locals[regB] + zExt[offset]], or it can indicate a memory location that is the sum of a register from AuxRegs and an offset, Mem[AuxRegs[regB] + zExt[offset].
Example: WRI: Mem[Locals[regB]+ zExt[offset]] ← Locals[regA].