When I first came across SUBLEQ, I really liked the beauty and simplicity of the design. However, I have now been experimenting with it for quite a while and have noticed one aspect of the standard implementation that I am not so happy with. In the standard implementation, negative numbers are used for Input/Output Ports or to Halt the machine in the case of a branch destination. This seems such as waste of the negative numbers, as generally only a couple will be used meaning that nearly half of the addressing capacity is lost for little gain. I propose the following improvement to the standard SUBLEQ design.
Design Improvement Options
While working out how to stop the waste of negative numbers, I considered the following factors: beauty, ease of implementation/simplicity, instructions executed, number of memory accesses and code size. A number of options were looked at, including negative numbers representing: literals, relative addressing and in-direct addressing.
Improved Design
The improved design is similar to the standard design as described in my article: SUBLEQ - A One Instruction Set Computer (OISC). The key difference is that negative numbers now refer to in-direct addressing.
The improved design is described as follows:
SUBLEQ - Subtract and Branch if Less then or Equal to zero
In cases where a, b and c are ≥ 0 the following holds true:
SUBLEQ a, b, c
Mem[b] := Mem[b] - Mem[a]
if (Mem[b] ≤ 0) goto c
Where a or b or c < 0 then in-direct addressing takes effect in the following way:
If a < 0 then Mem[a] above becomes Mem[Mem[|a|]]
If b < 0 then Mem[b] above becomes Mem[Mem[|b|]]
If c < 0 then goto c above becomes goto Mem[|c|]
To refer to ports I suggest that certain memory locations be mapped to the ports. For example Mem[0] could be mapped to the Standard Input Port and Mem[1] could be mapped to the Standard Output Port. Then the code would start at the next address say, Mem[2].
Comparison of the Two Implementations
To compare the standard implementation with the improved implementation of SUBLEQ, I have chosen three tests that I am particularly interested in:
- Call and Return
- Call
- Calls a function by first pushing the return address onto a return stack and then jumping to the address of the function.
- Return
- Returns from a function by popping the return address from the return stack and jumping to it.
- Push and Pop
- Push
- Pushes a word onto a data stack.
- Pop
- Pops a word off of a data stack.
- Block Memory Move
- BlockMove
- Moves a block of memory from one address to another.
The code for the three tests can be found in the Appendix at the bottom of this article.
To work out the number of Memory Accesses for each Instruction Executed, I took 5 Memory Accesses as the standard number when using direct addressing: 3 to read in the instruction plus 2 to read in the locations that the a and b fields refer to. I then added 1 Memory Access for each in-direct field used.
Below are tables comparing the performance of the two designs:
Call and Return
| Case | Instructions Executed | Memory Accesses | Code Size in Words |
|---|---|---|---|
| Original SUBLEQ | 18 | 90 | 55 |
| Improved SUBLEQ | 7 | 39 | 22 |
Push and Pop
| Case | Instructions Executed | Memory Accesses | Code Size in Words |
|---|---|---|---|
| Original SUBLEQ | 20 | 100 | 60 |
| Improved SUBLEQ | 10 | 54 | 30 |
Block Memory Move (50 Words Moved)
| Case | Instructions Executed | Memory Accesses | Code Size in Words |
|---|---|---|---|
| Original SUBLEQ | 468 | 2340 | 82 |
| Improved SUBLEQ | 364 | 1974 | 66 |
Summary
It can be seen from the comparisons above that the improved design reduces the number of instructions executed, memory accesses and code size. I believe that it would not add much to the complexity of implementation and that it enhances the beauty of the design. My only remaining dissatisfaction with the design is that the branch address is rarely used, therefore wasting one word and one memory access per instruction. I intend to tackle this remaining problem in a future article.Appendix
Implementation Test Examples
The test examples given below are implemented as macros to ensure some uniformity in testing. I appreciate that if macros were not used that there are quicker ways of implementing some of these tests, particularly the block memory move. However, I wanted a way to compare general programming techniques.The following conventions hold true to the code examples given below:
| * | Before a field means that the address is in-direct, otherwise it is direct |
| . | At the start of a line means that it is not an instruction |
| ? | Indicates the current address |
| Z | This is a memory address normally containing 0 |
| ONE | This is a memory address normally containing 1 |
| MO | This is a memory address normally containing -1 |
| : | Indicates that the text before it is a label. Labels within macros are local to that macro. |
Original SUBLEQ Code
Below are the implementations of the Macros in the standard form of SUBLEQ.;---------------------------------------------------------------------------
; Calls a subroutine by first pushing the return address
; onto the return stack and then jumping to the subroutine's address.
; Assumes mem[Z] = 0, mem[MO] = -1
; and mem[returnStackPtr] points to memory to use as the return stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Call address
; Zero Top Of Return Stack and Copy Return Stack Pointer
zeroTORS zeroTORS
zeroTORS+1 zeroTORS+1
add+1 add+1
returnStackPtr Z
Z zeroTORS
Z zeroTORS+1
Z add+1
zeroTORS: Z Z
; Copy Return Address to Return Stack
Z Z
returnAddress Z
add: Z Z
MO returnStackPtr ; Increment Stack pointer
Z Z address ; Jump to the address
. returnAddress: ?+1 ; Label to indicate return address
EndMacro
Call: Instructions executed: 13 Memory Accesses: 65 Code Size: 40
;---------------------------------------------------------------------------
; Returns from a subroutine call by popping the return address and then
; jumping to it.
; Assumes mem[Z] = 0, mem[ONE] = 1
; and mem[returnStackPtr] points to memory to use as the return stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Ret
; Decrement Stack pointer
ONE returnStackPtr
; Copy Return Stack Pointer
jump+2 jump+2
returnStackPtr Z
Z jump+2
; Jump to return address
jump: Z Z Z
EndMacro
Ret: Instructions executed: 5 Memory Accesses: 25 Code Size: 15
Call and Ret Total: Instructions executed: 18 Memory Accesses: 90 Code Size: 55
;---------------------------------------------------------------------------
; Pushes word at address onto Data Stack.
; Assumes mem[Z] = 0
; and mem[stackPtr] points to memory to use as the data stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Push address
; Zero Top of Data Stack
zeroTODS zeroTODS
zeroTODS+1 zeroTODS+1
add+1 add+1
stackPtr Z
Z zeroTODS
Z zeroTODS+1
Z add+1
zeroTODS: Z Z
Z Z
; Copy data at address to Top of Data Stack
address Z
add: Z Z
; Increments Stack Pointer
MO stackPtr
Z Z
End Macro
Push: Instructions executed: 13 Memory Accesses: 65 Code Size: 39
;---------------------------------------------------------------------------
; Pops word off Data Stack into address.
; Assumes mem[Z] = 0, mem[ONE] = 1
; and mem[stackPtr] points to memory to use as the data stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Pop address
; Decrement Stack Pointer
ONE stackPtr
; Zero destination address
address address
; Pop the data off the stack
add add
stackPtr Z
Z add
add: Z address
Z Z
End Macro
Pop: Instructions executed: 7 Memory Accesses: 35 Code Size: 21
Push and Pop Total: Instructions executed: 20 Memory Accesses: 100 Code Size: 60
;---------------------------------------------------------
; Moves numWords of memory from srcAddress to dstAddress.
; Assumes mem[Z] = 0, mem[MO] = -1 and mem[ONE] = 1
; Leaves mem[Z] = 0
; Doesn't alter mem[MO] or mem[ONE]
;---------------------------------------------------------
Macro BlockMove srcAddress dstAddress numWords
; Copy macro parameters to working storage
getSrc getSrc
srcCopy Z
Z getSrc
Z Z
zeroDst zeroDst
zeroDst+1 zeroDst+1
add+1 add+1
dstCopy Z
Z zeroDst
Z zeroDst+1
Z add+1
Z Z
counter counter
wordsCopy Z
Z counter
Z Z
MO counter ; Increment num of words for loop below
loop: ONE counter moveFinished ; Decrement num of words working copy and loop until all copied
; Move source to destination
zeroDst: dstAddress dstAddress
getSrc: srcAddress Z
add: Z dstAddress
; Increment source and destination pointers
MO zeroDst
MO zeroDst+1
MO getSrc
MO add
Z Z loop
; Working copies of the macro parameters
. counter: 0
; Copies of the macro parameters so as not to alter their values if used again
. srcCopy: srcAddress
. dstCopy: dstAddress
. wordsCopy: numWords
movedFinished:
EndMacro
BlockMove: Instructions executed: 468 Memory Accesses: 2340 Code Size: 82
Improved SUBLEQ Code
Below are the implementations of the Macros in the improved form of SUBLEQ that uses negative numbers for in-direct addressing.;---------------------------------------------------------------------------
; Calls a subroutine by first pushing the return address
; onto the return stack and then jumping to the subroutine's address.
; Assumes mem[Z] = 0, mem[MO] = -1
; and mem[returnStackPtr] points to memory to use as the return stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Call address
; Copy return address to stack
*returnStackPtr *returnStackPtr ; Zero stack entry
returnAddress Z
Z *returnStackPtr
MO returnStackPtr ; Increment Stack pointer
Z Z address ; Jump to the address
returnAddress: ?+1 ; Label to indicate return address
returnLabel:
End Macro
Call: Instructions executed: 5 Memory Accesses: 28 Code Size: 16
;---------------------------------------------------------------------------
; Returns from a subroutine call by popping the return address and then
; jumping to it.
; Assumes mem[Z] = 0, mem[ONE] = 1
; and mem[returnStackPtr] points to memory to use as the return stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Ret
One returnStackPtr ; Decrement Stack pointer
Z Z *returnStackPtr ; Jump to return address
End Macro
Ret: Instructions executed: 2 Memory Accesses: 11 Code Size: 6
;---------------------------------------------------------------------------
; Pushes word at address onto Data Stack.
; Assumes mem[Z] = 0
; and mem[stackPtr] points to memory to use as the data stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Push address
*stackPtr *stackPtr ; Zero stack entry
; Copy data at address to Stack
address Z
Z *stackPtr
MO stackPtr ; Increments Stack Pointer
Z Z
End Macro
Push: Instructions executed: 5 Memory Accesses: 28 Code Size: 15
;---------------------------------------------------------------------------
; Pops word off Data Stack into address.
; Assumes mem[Z] = 0, mem[ONE] = 1
; and mem[stackPtr] points to memory to use as the data stack.
; Leaves mem[Z] = 0
;---------------------------------------------------------------------------
Macro Pop address
One stackPtr ; Decrement Stack Pointer
address address ; Zero destination address
; Pop the data off the stack
*stackPtr Z
Z address ; Pop data from stack into address
Z Z
End Macro
Pop: Instructions executed: 5 Memory Accesses: 26 Code Size: 15
Push and Pop Total: Instructions executed: 10 Memory Accesses: 54 Code Size: 30
;---------------------------------------------------------
; Moves numWords of memory from srcAddress to dstAddress.
; Assumes mem[Z] = 0, mem[MO] = -1 and mem[ONE] = 1
; Leaves mem[Z] = 0
; Doesn't alter mem[MO] or mem[ONE]
;---------------------------------------------------------
Macro BlockMove srcAddress dstAddress numWords
; Copy macro parameters to working storage
srcWrk srcWrk
srcCopy Z
Z srcWrk
Z Z
dstWrk dstWrk
dstWrk Z
Z dstWrk
Z Z
numWrk numWrk
numWrk Z
Z numWrk
Z Z
MO numWrk ; Increment num of words for loop below
loop: ONE numWrk moveFinished ; Decrement num of words working copy and loop until all copied
; Zero destination
*dstWrk *dstWrk
; Add source to destination
*srkWrk Z
Z *dstWrk
; Increment srcWrk and dstWrk
MO srcWrk
MO dstWrk
Z Z loop
; Working copies of the macro parameters
. srcWrk: 0
. dstWrk: 0
. numWrk: 0
; Copies of the macro parameters so as not to alter their values if used again
. srcCopy: srcAddress
. dstCopy: dstAddress
. wordsCopy: numWords
movedFinished:
EndMacro
BlockMove: Instructions executed: 364 Memory Accesses: 1974 Code Size: 66
