Wombat4w CPUSim machine design

To define a CPU Sim machine, I need:

Hardware Components

Registers

I should be able to follow the register pattern of the existing Wombat machines. I should be able to share the mar and mdr for the Stack and Heap RAMs. The ir (instruction register) is essentially the memory data register for the Main RAM (instructions).

I'll have to analyze what the frames look like.

buffer1 32
buffer2 32
ir 24
mar 16
mdr 32
pc 16
status 3
top 16

Register arrays

A 8 32

Addressed by 3 bits in an instruction.

Condition bits

OK.

RAMs

I need:

A Main RAM for the code area.
A Stack RAM for the stack.
A Heap RAM for the heap.

I'll make all of these of size 65536, addressable with 16 bits.

Microinstructions

Set
Test
Increment
Shift
Logical
Arithmetic
Branch
TransferRtoR
TransferRtoA
TransferAtoR
Decode
Set Condition Bit
IO
Memory Access

EQUs

I could also use local EQUs for symbolic local variable definitions. I would have to be careful whether I am addressing off the frame pointer or the stack pointer.

Fetch sequence

Should be the same, modified for instruction size.

Machine instructions

Wombat4 machine instructions

This is the Wombat4 as it was.

stop 0000 16
load 01 5 2 9
store 02 5 2 9
read 03 5 11
write 04 5 11
add 05 5 2 9
subtract 06 5 2 9
multiply 07 5 2 9
divide 08 5 2 9
jump 09 5 11
jumpz 0A 5 2 9
jumpn 0B 5 2 9
move 0C 5 2 9
push 0D 5 11
pop 0E 5 11
call 0F 5 11
return 8000 16
load_s 11 5 2 9
store_s 12 5 2 9

Wombat4w 24 bit instruction revision

This is my revision to allow 24 bit instructions.

stop 000000 24
load 01 5 3 16
store 02 5 3 16
read 03 5 19
write 04 5 19
add 05 5 3 16
subtract 06 5 3 16
multiply 07 5 3 16
divide 08 5 3 16
jump 09 5 19
jumpz 0A 5 3 16
jumpn 0B 5 3 16
move 0C 5 3 16
push 0D 5 19
pop 0E 5 19
call 0F 5 19
return 800000 24
load_s 11 5 3 16
store_s 12 5 3 16

This ought to be enough.

I could allow 4 bits per register for 16 registers in the A array, but this cuts down the memory too much.

Then I need to change the microinstructions to pick out the right bits.

First five bits (opcode): 0-4
Next three bits (first register operand): 5-7
Rest of instruction (address operand): 8-23

First 5 bits (opcode): 0-4
Next three bits (first register operand): 5-7
Last three bits (second register operand): 21-23

I either have to cut back to 8 registers or half my memory. I'll give up the registers and cut back to 8 with three bit addressing to keep the 65536 memory locations, 65K.

Upgrade to CPUSim

I've downloaded CPU Sim 3.1.18. I've also moved the instructor's manual folder up out of the 3.1.17 folder to the D:\uofm\c4041s2005 directory and deleted the 3.1.15 and 3.1.18 folders. This will help me keep things clean if new versions come out.

Work on Wombat4w implementation

Now I need to modify the Wombat4 machine into Wombat4w and make it work.

I take it that each RAM can have its own cell size.

I also should write a program or two and try it to make sure that it is working.

Tiles and machine instructions

I have found that the idea in setting up tiles to tile the intermediate code tree is not to list a catalog of tiles for each machine instruction. Instead, I need to start with the kinds of tiles that I need to cover the tree and then come up with machine instructions to describe them. Some tiles will take more than one instruction.

For example, the nodes for addition represent three temporaries: two for the inputs and one for the output. But the Wombat machines use two register instructions, of the form:

add A1 A2

which adds the contents of A1 and A2 and puts the results in A1. So to implement a BINOP node with an addition operation, I need to do this. The move instruction has the source first, the target second.

;; Generate first operand into t1
;; Generate second operand into t2
move t1 t3
add t3 t2

It will be the job of the register allocator to try to eliminate these move instructions by assigning the intermediate results to the appropriate actual registers.

Modify Wombat4 to get Wombat4w

Now it is time to start modifying the Wombat4.

First, I'll save it as Wombat4w. I've saved the file D:\uofm\c4041s2005\CPU Sim 3.1 Instr Manual folder\Wombat4w.cpu.

Now I'll start modifying it.

Registers

I'm making these as listed above. Done.

Register arrays

Done.

Condition bits

No change.

RAMs

Done. This seems to be working well.

Microinstructions

This needs to be a pretty thoroughgoing revision.

Set

Changed

Test

Changed

Increment

Inc2-pc This increments the PC by 2. Only the fetch sequence uses it. Since I have changed the instructions to have width 3, I need to change this to Inc3-pc and change its delta to 3.

I also need to change the increment and decrement top microinstructions to change by 4 instead of 2. Done.

Shift

None

Logical

None

Arithmetic

No change

Branch

None

TransferRtoR

buffer1->mdr change amount to 32
mdr->buffer1 change amount to 32
mdr->ir change amount to 24, left starts alone ??
mdr->pc
Others changed.

TransferRtoA

buf1->A[ir(14-15)]  Changed to 21-23
buf1->A[ir(5-6)]   Changed to 5-7

TransferAtoR

Similar.

Decode

No change.

Set Condition Bit

No change.

IO

No change.

Memory access

I need to add memory access microinstructions for the heap.

I added two instructions identical to the Main instructions, except that they access the heap.

Heap[mar]->mdr
mdr->Heap[mar]

EQUs

I need to add 4 more for the new registers! Added A4 through A7.

Fetch sequence

Should be OK.

Machine instructions

I need to add some load and store instructions for the heap.

Heap management

I have to be a bit careful about loading from the heap. I can't just say load from an address in the instruction, and I can't just say load from an address in a register. Well, I guess that I could. But I would like to be able to use the address in memory as an offset for a register on the stack.

What do I need to do to load from the heap?
What do I need to do to store on the heap?

I need an address in the heap. This could be the actual address, or it could be the base address of the object, offset with a value in the instruction. I need the base address somewhere. This is essentially pushing part of the intermediate code tree into the microcode.

OK, it looks like I need the base address in a register, then the ability to add to it an offset from the instruction. So the steps are:

Get the object's start address in t0.
Load relative to it in t1.

The problem here is that I have to split the address field of the machine instruction. I need a new instruction of the form

load_h target base fixed_offset
5 3 3 13
0-4 5-7 8-10 11-24
store_h source base fixed_offset

So I need new microinstructions to load and store from a base and offset into the heap.

New microinsructions needed:

ir(11-24)->mar
A[ir(8-10)]->buf1
mar+buf1->mar

Heap[mar]->mdr  (already added)

Microinstructions for load_h

clear-mar          ;; zero out the mar
ir(11-24)->mar     ;; transfer the offset to the mar
A[ir(8-10)]->buf1  ;; copy the base address from an A register to buffer1
mar+buf1->mar      ;; add the contents of buffer1 to the mar
;; this places the actual address in mar
Heap[mar]->mdr     ;; Copy the heap value to the mdr
mdr->buffer1       ;; Copy to buffer1
buf1->A[ir(5-7)]   ;; Place result in target register
End

New microinstructions needed:

(The same as above)

mdr->Heap[mar]  (already added)

Microinstructions for store_h

clear-mar          ;; zero out the mar
ir(11-24)->mar     ;; transfer the offset to the mar
A[ir(8-10)]->buf1  ;; copy the base address from an A register to buffer1
mar+buf1->mar      ;; add the contents of buffer1 to the mar
;; this places the actual address in mar
A[ir(5-7)]->buf1   ;; copy the value to be stored to the buffer1
buffer1->mdr       ;; Copy to the memory data register
mdr->Heap[mar]     ;; Store the data value in the heap
End

Assembly language heap management functions

Well, it looks like I have the machine about ready. The only thing is that I need to write an assembly language function or two. I need one to allocate an array, and I need one to allocate an object.

It seems to be working, at least for one simple test. I need more tests, of course.

To do this, I need both functions in the same file, and I need a common shared variable to hold the address of the next available slot on the heap. This is a very simple minded approach, with no garbage collection.

I see that Dale Skrien did his JVM heap in microcode. If he could do that, I should be able to implement it in assembly language fairly easily.

I may want to add a load constant instruction load_c.

;; Do I need to multiply by four here?
nextHeap: .data 2 0 ; initial heap address
; Expects one argument in register A0:
; A0 The size of the class binding
; Returns in A0 its result: the address of the allocated block.
; Needs one local register: a place to load the base address to compute the
; new heap offset
malloc:
push A1 ; save register A1 to use in computation
move A0 A1 ; get the amount to reserve in A1, free A0 for return value
load A0 nextHeap ; place return value in A1
add A1 A0 ; increment the pointer to the next available slot
store A1 nextHeap ; store the next available slot pointer for use later
pop A1 ; restore A1 from the stack
return

; Expects two arguments in registers A0 and A1:
; A0 the array size
; A1 the initial value
; Returns in A0 its result: the address of the allocated block.
; Initializes all values in the array to the given initial value.
; Needs one local register to keep track of the address being filled ??
initArray:
push A2 ; save register A1 to use in computation
push A3

pop A3
pop A2

I may punt on this and do it the way Dale did it in JVM3.

1/5/2005

I'm studying the Wombat6 and comparing what he did with my Wombat4w. I don't think I'll add all the logical and bitwise instructions, since I don't think we need them. I shall add his loadc, loadi, and storei, and revise my stuff to use A[7] instead of top as he does.

The push and pop instructions will become relatively obsolete.

If I do the memory allocation in microcode, then I don't need the assembly language functions that I was writing above. I'll see what he does in the JVM3 and adapt it.

 Create your own free wiki!HelpPublic, not yet premium Privacy Policy RSS