The Itty Bitty Stack Machine (IBSM) is a virtual computer with a
relatively simple but powerful architecture and instruction set. In addition
to 8K 16-bit words of memory, it has four registers to control program
execution:
PC -- The Program Counter always points to the next memory word from which the processor will fetch instructions.
SP -- The Stack Pointer always points to the top of the expression and control stack, which typically holds the last number pushed but not yet popped. Unlike most computers, the IBSM stack grows up toward increasingly positive addresses.
LR -- The Limit Register is used to check for stack runaway; an error interrupt occurs if the SP grows past the current LR or shrinks below the current FP.
FP -- The Frame Pointer points into the current stack, and serves as a reference point for local variable access. After a procedure or function has been called and properly entered, its stack frame will look somewhat like this:
[ ] <-- SP, last local variable
...
[ ]
[ ] <-- first local variable, FP+3
[ ] <-- saved caller's FP
[ ] <-- saved caller's PC
[ ] <-- FP, typically the static link
[ ] <-- last (nth) parameter, FP-1
...
[ ] <-- first parameter, FP-n
[ ] <-- function value, caller's SP upon return
The IBSM starts up by taking the address loaded into memory location
0000 as the initial SP. It pops an initial LR, FP, and finally PC from
the stack at that address (see XFR instruction, below),
then begins execution. A simple compiler should load program code starting
from address 4 or later, then follow that with the run-time stack, initially
loaded with the address of the main program, then a word that points to
itself for an initial FP, then some large number above that for a LR. The
address of the LR value on the top of the stack should then be stored in
memory location 0. The following startup configuration is recommended:
[E] <-- T: top of loaded memory, = initial LR
[F] <-- T-1: initial FP
[C] <-- T-2: initial PC
[ ] <-- last global variable, will be top of stack
...
[F] <-- F: typically the base of global variables
[ ] <-- last word of code
...
[ ] <-- C: beginning of code
...
[T] <-- 0: initial stack pointer SP at startup
The virtual machine memory loaded takes decimal numbers for its
data, beginning at 0. All data should be positive integers between 0 and
65535 separated by white space (spaces and/or returns). Loading may be
non-sequential by inserting a one's complement address number (negative
load address -1), but attempting to overload a non-zero memory location
will terminate the load, as will also an address out of range. We recommend
ending the file with a large negative number like -9999.
The instructio0ns marked with * can be safely ignored for simple programs:
00 -- NOP. Use this to fill out a word when packing fewer than 3 instructions. Loose code can be packed one per word (one instruction, plus two NOPs); dense code can be packed three per word. However, jumps always go to the first instruction in a word, so the previous code may need to fill out with NOPs for alignment.
01 -- BZ, Branch on Zero. This instruction pops two numbers off the stack. The top number (last pushed) is an address offset, which is added to the current PC if the second number (first pushed) is zero, and not otherwise. The address offset is always relative to the next word after the word containing the BZ instruction; a zero value simply skips over the remaining instructions in the current instruction word. An unconditioinal jump is effected by preceding the BZ with a ZERO instruction to push a zero.
02 -- TRAP, * direct subroutine calls through a table beginning in absolute address 4. This could be used for system calls. The table offset is taken off the stack.
03 -- CALL, the normal subroutine calling mechanism. This pops an absolute address off the stack, pushes the current PC, then jumps to the address. The normal calling protocol is to push a space to hold the function return value (if any), then all the parameters, then the called routine's parent frame pointer, if any, then the address of the subroutine, and finally executing the CALL instruction. The return will always be to the next word, so the CALL should be the last instruction in its word.
04 -- ENTER, for initializing the FP in a subroutine. This instruction pops off the stack a number representing how many words to reserve for local variables, and replaces it with the caller's FP, and finally adjusts the stack pointer to accomodate the local variables. The normal entry protocol is to push onto the stack a number representing the number of local variable words, then execute ENTER.
05 -- EXIT, for returning from a subroutine to its caller. This instruction pops off the stack a number representing how many parameters to be deleted, restores the caller's saved FP and PC from the stack, then pops off the specified additional number of parameter words. The next instruction to execute will be in the word after the caller's CALL instruction.
06 -- PRIOR. * Sets thread priority from the popped value.
07 -- XFR, * for transferring to a coroutine. This instruction pops off the stack an address representing the SP of the thread being transferred to, and replaces it with the current PC, FP, and LR. Then the caller's SP is exchanged at the specified address for the couroutine's LR, FP, and PC, with execution resuming at the word following that thread's XFR instruction. Normally it would save the stack top in a coroutine variable for later use by another XFR instruction.
08 -- DUPE, duplicates (pushes a copy of) the top of stack. To discard the top word from the stack (for example the remainder or quotient from DVMOD, when the desired result is the other value), use the succession of [ZERO;AND;OR].
09 -- SWAP, exchanges the top two words on the stack. You can use this to bring the quotient from DVMOD to the top so it can be discarded, when the desired result is the remainder, or to push the address for ST down under the value if they were computed in the wrong order.
10 -- DVMOD, Divides the top of stack into the next word, then pushes the integer quotient and the remainder (in that order) to replace the dividend and divisor. If the divisor is zero, an error interrupt occurs.
11 -- MPY, pops the top two numbers off the stack and replaces them with a single word product.
12 -- ADD, pops the top two numbers off the stack and replaces them with their sum.
13 -- XOR, pops the top two numbers off the stack and replaces them with their bitwise exclusive-XOR.
14 -- OR, pops the top two numbers off the stack and replaces them with their bitwise inclusive-OR.
15 -- AND, pops the top two numbers off the stack and replaces them with their bitwise AND.
16 -- EQUAL, pops the top two numbers off the stack and replaces them with the value 1 if they are equal, or 0 if they are unequal.
17 -- LESS, pops the top two numbers off the stack and replaces them with the value 1 if the top number is greater than the other, or 0 otherwise. Note that if the two values are pushed in lexical order, then this instruction tests whether the first is less than the second.
18 -- GRTR, pops the top two numbers off the stack and replaces them with the value 1 if the top number is less than the other, or 0 otherwise. Note that if the two values are pushed in lexical order, then this instruction tests whether the first is greater than the second.
19 -- NOT, replaces the top number on the stack with its bitwise (one's) complement.
20 -- NEG, replaces the top number on the stack with its (two's complement) negative.
23 -- DEBUG, * sets the virtual machine trace mode to the value popped off the stack. Four bits are significant:
2: Trace writes to memory24 -- STOP. Stop execution. The operator may resume with the next instruction.
4: Trace any sequence change (CALL, EXIT, XFR, TRAP, or BZ taken)
8: Trace only CALL, EXIT, XFR and TRAP
16: Trace all instructions
25 -- GLOB, to adjust an absolute address relative to the current FP, so that it works correctly. Normal local variable access is accomplished by pushing the frame offset of the variable then loading or storing. To access a global variable you should insert a GLOB instruction after pushing the absolute memory location before executing the load or store.
26 -- ST, pop a value off the stack and store it in the local variable whose frame offset is next popped off the stack. Normal assignment pushes the address of the variable, optionally followed by GLOB for global variables, then the value to be stored there, then execute the ST instruction. Storing to (global) address -1 outputs one character to the terminal display panel.
27 -- LD, pop a frame-relative address off the stack and replace it with the value fetched from that variable. Normal variable access pushes the address of the variable, optionally followed by GLOB for global variables, then execute the LD instruction. Loading (global) address -1 inputs one character from the terminal input panel.
28 -- LDC pushes the next instruction word as a constant onto the stack, then increments the PC past it. Any additional instructions in the current instruction word continue to execute before resuming after the constant word; if they include additional LDC instructions, several consecutive constant words may be pushed and skipped over.
29 -- NIBL pushes onto the stack a 5-bit constant taken from the current instruction word, then skips over it before executing any additional instructions in the current word. If the NIBL instruction is the third instruction in its word, then a zero (or perhaps one) is pushed from the remaining single bit; the constant is never fetch from the next instruction word.
30 -- ZERO pushes a constant zero.
31 -- ONE pushes a constant one.
abc = x+3;To test global variable flg<-3 and replace it with the value returned by function Proc(x) if so (assuming no parent frame pointer to pass, as in C); we assume also that instructions start word aligned and are packed:NIBL abc -- perhaps offset 5 in current frame
NIBL x -- maybe offset 7
LD
NIBL 3
ADD
ST -- store sum into abc
if (flg<-3) {flg=Proc(x);}LDC -- global address of flg in next word
GLOB
LD
------ end of 1st word
(flg)
------ end of 2nd word
NIBL 3
NEG
------ end of 3rd word
GRTR
NIBL 4 -- BZ skips over 4 words (to word 10 from 6th word)
------ end of 4th word
BZ
LDC -- flg
GLOB
------ end of 5th word
(flg)
------ end of 6th word
ZERO -- reserve space for return value
NIBL x -- get parameter
------ end of 7th word
LD
LDC -- Proc
CALL
------ end of 8th word
(Proc)
------ end of 9th word
ST -- store result into flg
NOP -- filler, so BZ can land on next instruction
NOP
------ end of 9th word
// Test program ...
class xyz {
int x;
void main () { x=3; }
}
The object file looks like this (the second "-1 23" is used to terminate
the load:
-5 156 0 31 13182Note that some of the words of code have multiple instructions packed in them. When you click tyhe Load button in the simulator and select this file, the loader will disassemble the code as follows:
25 125 26 31 5
// Startup code @13
30 894 157
3 24 4030 52 20 13 20 99
-1
23
-1
23
4: 156 LDC ENTERClick the Step button to trace execution one instruction word (up to three instructions) at a time. Or set the trace mode bits in the top center field (see DEBUG above) and click the Run button to run until the next Stop.
5: 0
6: 31 ONE
7: 13182 ZERO LD ADD
8: 25 GLOB
9: 125 NIBL 3
10: 26 ST
11: 31 ONE
12: 5 EXIT
13: 30 ZERO
14: 894 ZERO LD
15: 157 NIBL 4
16: 3 CALL
17: 24 STOP
18: 4030 ZERO NIBL 3
19: 52 NEG BZ
20: 20 NEG
21: 13 XOR
22: 20 NEG
23: 99 CALL CALL
0: 23
---- SP=23, Lim=99, FP=20, PC=13
Rev. 2003 February 17