Work on Wombat5w
Changes to Wombat4w to make it more like Wombat6. I'm creating a Wombat5w.
I have to deal with the top register: get rid of it and change its uses to A[7].
Microinstructions that use top:
Increment
Inc4-top Increments the top register by 4 when pushing a value.
dec4-top Decrements the top register by 4 when popping a value.
Changed to:
Inc4-A[7]
dec4-A[7]
Arithmetic
top+mar->top Adds the contents of MAR to top to give an offset?
top-mar->top Subtracts the contents of MAR from top to give an offset?
Changed to:
A[7]+mar->A[7]
A[7]-mar->A[7]
top->mar Copy the contents of top to mar.
Never used: deleted.
Memory Access
Stack[top]->mdr load the contents of the top of the stack in the mdr.
mdr->Stack[top] store the contents of the mdr on the top of the stack.
Change to:
Stack[A[7]]->mdr
mdr->Stack[A[7]]
Machine instructions
store_s uses top-mar->top, mdr->Stack[top], top+mar->top
load_s uses top-mar->top, Stack[top]->mdr, top+mar->top
call uses mdr->Stack[top], Inc4-top
return uses dec4-top, Stack[top]->mdr
push uses mdr->Stack[top], Inc4-top
pop uses dec4-top, Stack[top]->mdr
Hold it. I just realized that my old top had 16 bits, whereas the A[7] has 32 bits. This could cause a bit of a problem. I guess I just have to be careful.
Well, now I need to add the new machine instructions and change the names and possibly implementations of some of the old ones. I also need to fix them by clearing the mar when needed.
store_h change to storeh changed
load_h change to loadh changed
store_s change to stores fixed
load_s change to loads fixed
Add these:
loadc
loadi
storei
These are a bit tricky in that they involve a shift.
To add loadc, I need these new microinstructions:
TransferRtoR
ir(8-23)->buf1(0-15) added
Shift
buf1 RSA 8 added
TransferRtoA
buf1->A[ir(5-7)] already exists
To add loadi, I need these new microinstructions:
TransferRtoR
buffer1(16-31)->mar added
Memory Access
Stack[mar]->mdr added
To add storei, I need these new microinstructions: none.
TransferRtoR
buffer1(16-31)->mar added
Memory Access
mdr->Stack[mar] added
I now have the Wombat5w updated with the load and store instructions. The next task is to examine the JVM3 machine and see how he handles the heap.
His newarray just allocates space and does not initialize it. He uses registers to hold the positions.
I would need instructions like this:
new A0 On input, A0 holds the number of slots in the object. On output, it holds the address of the newly created object. Not needed.
newArray A0 A1 On input, A0 holds the number of slots in the array.
Multiply it by 4 to get the actual size. On output, A0 holds the address of the newly created object. On input, A1 holds the value to place in each slot. On output, it is garbage.
Garbage collection idea
1/6/2005
Idea: I could implement a copying collector by having another heap RAM, and keeping a flag of which heap was in use. I could then copy live records from one heap to the other and change the flag. There would be a microcode instruction to check the condition bit and branch on it. Each machine instruction that refers to heap memory would have to check this bit before accessing memory to determine which heap to use. The problem with this is that I would have to modify all the references to each reference in the old heap to the correct offset in the new compacted heap.
The problem with a mark sweep collector is that I would have to have some way to identify memory blocks and somewhere to store the marks.
I have to decide how to handle object and array creation and initialization. The book suggests using a function malloc() to allocate uninitialized space for an object, then initializing it in IR code and assembly code. It also suggests having an initArray() function to allocate an initialize an array.
So the question is:
Do I use one generic malloc() function for and generate IR code to initialize in both cases? The code could be different: a loop for the array.
Do I use an initArray() function to allocate and initialize arrays?
Do I do the initialization in assembly language or microcode?
For garbage collection, which I am not doing now, I would need to include additional information in each allocated record somehow, to allow for marking.
I'm going to write the array initialization code generically, in pseudo assembly code, not worrying about registers or saving registers. I wrote malloc() above.
newHeap holds next available heap pointer.
address initArray (rawSize, initialValue)
address <- newHeap
newHeap <- new
??
I'm about ready to ditch the initArray() concept. I'll try generating IR code to initialize the array, and just worry about malloc(). I could even have a microcode instruction like the one that JVM3 has for getting an uninitialized block of memory. And translate calls to malloc to use that.
Then calls to new object and new array would both change to calls to malloc().
Let's try again, assuming that I have malloc() available, and write pseudocode to set up an array. Then I'll try translating it to IR code.
// wordSize is a macro for the size of a word on this machine (4).
// malloc(rawSize) returns a pointer to a newly allocated block of that size
// and updates the newHeap pointer, which can be hidden.
// Inputs:
// size -- number of array elements
// initValue -- the initial value of each element
// Effect:
// Allocate a new block of size wordSize * (size + 1).
// Initialize the zeroth position to the array size.
// Initialize all other positions to the initValue.
// Return:
// A pointer to the beginning of the initialized array.
rawSize <- (size + 1) * wordSize
address <- malloc(rawSize)
heap[address] <- size
wordPosition <- address + wordSize // offset by one slot
count <- size
loop:
if size == 0 goto endLoop
heap[wordPosition] <- initValue
goto loop
endLoop:
returnValue <- address
return returnValue
Intermediate code and multiple RAMs
I just noticed something: the intermediate code assumes that there is only one block of memory. There is no way to refer to different kinds of memory. That pretty well knocks this whole multiple memory idea out unless I can figure some way to deduce the memory being used from context.
I'm not sure whether this will be a problem. I do have a slot in the MEM nodes for a variable binding. I could also place something here to indicate that it is an array.
But the simplest thing might still be to leave the IR alone, use initArray(), and let the code generator handle it.
Now I'll try translating the pseudo code into Wombat5w assembly code. The code generator could inline this code whenever needed, or I could write it as an actual initArray() function. I'll try that first.
I'm going to add an increment instruction to the Wombat5w. This will require a new increment microinstruction. It will use an offset in the register telling how much to increment. I'll have to be careful to use a different instruction length. I can't use 5 and use 10000 since that would shadow the return instruction with a longer length. I'll try using length 6 and use 100001 as the opcode. This is 10 0001 or 21 in hex. I'll then need more TransferRtoR microinstructions, and possibly a clear buffer micro instruction.
100001
0-5 6-8 9-23
inc 21 6 3 15
A[ir(6-8)]->buf1 // copy register to increment TransferAtoR Done
ir(9-23)->buffer2(0-14) // transfer 15 bits of increment TransferRtoR Done
buf2 RSA 17 // arithmetic shift right 17 of increment Shift Done
buf1+buf2->buf1 // add the increment to the register value Already there
buf1->A[ir(6-8)] // copy modified value back to register TransferRtoA
End
I've added this. Now I can use it in my programs.
I may want to get rid of it and replace it with an alloc instruction. No, I
should change it to a 7 bit instruction so that I can have two instructions
of this length.
; malloc(rawSize) returns a pointer to a newly allocated block of that size
; and updates the newHeap pointer, which can be hidden.
; Expects two arguments in registers A0 and A1:
; A0 the array size (number of slots)
; A1 the initial value
; Returns in A0 its result: the address of the allocated block.
; Places the size in the initial slot.
; 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 A2 to use in computation
push A3 ; save register A3 to use in computation
; Compute raw byte size of array in A2
loadc A2 1 ; Set up to add one slot at the beginning to hold the array size
add A2 A0 ; Compute size plus one for extra slot
loadc A3 4 ; Load the word size
multiply A2 A3 ; Compute the raw array byte size as (size + 1) * 4
; Can resuse A2 since raw size is no longer needed after this
alloc A2 A2 ; Allocate a block of size in A2, leave result in A2 !! Need instr
storeh A0 A2 0 ; Store array size in A0 in slot 0 offset from address in A2
; A0 contains the size of the array in slots
; A1 contains the initial value to place in each slot
; A2 contains the address of the allocated block to return
; A3 contains the word size
; Now we must place the proper initValue in each slot
push A2 ; Save the current allocated address to pop back into A0!
add A2 A3 ; Increment A2 by the wordSize: first location into which to store
; A0 contains the number of slots yet to fill
; A1 contains the initial value to place in each slot
; A2 contains the location into which to store
; A3 contains the word size
loop:
jumpz A0 endLoop ; If no more slots to store, then finish
storeh A1 A2 0 ; Store the initValue (A1) in slot 0 offset from address in A2
add A2 A3 ; Point A2 to the next word in which to store
inc A0 -1 ; Decrement the count of slots yet to fill
jump loop ; Go back and do it again
endLoop:
pop A0 ; Get the return address from the stack back into A0
pop A3 ; restore saved A3
pop A2 ; restore saved A2
return
To change the instruction to use seven bits
1000001 or 100 0001
0-6 7-9 10-23
inc 41 7 3 14
A[ir(7-9)]->buf1 // copy register to increment TransferAtoR Done
ir(10-23)->buffer2(0-13) // transfer 14 bits of increment TransferRtoR Done
buf2 RSA 18 // arithmetic shift right 18 of increment Shift Done
buf1+buf2->buf1 // add the increment to the register value Already there
buf1->A[ir(7-9)] // copy modified value back to register TransferRtoA
End
1000010 or 100 0010
alloc 42 7 3 14
Analysis of the current newarray in JVM3
; tos holds the value on the top of the stack in a register
; the tos holds the number of slots in the array
tos->mdr ; Load the number of slots in the array in mdr
mdr<<2 ; Multiply by 4 to get array byte size
mdr->opc ; Save array byte size in opc
heap->mdr ; Load the current next heap address in mdr
mdr->Stack[sp] ; Replace the current top of stack with the next heap address
mdr->tos ; Place the next heap address in tos register also
mdr=mdr+opc ; calculate the new next heap address (address plus byte size)
mdr->heap ; Store the revised address back in the heap register for later
End
Use a register nextHeap to hold heap pointer to next available slot on heap.
alloc sizeReg returnReg
nextHeap->buf2 ; Copy the current nextHeap pointer to buffer2 TransferRtoR
A[ir(7-9)]->buf1 ; Copy raw byte size to alloc into buffer1
buf1+buf2->buf1 ; Calculate new nextHeap size
buf1->nextHeap ; Store new nextHeap, old one is still in buf2 TransferRtoR
buf2->A[ir(21-23)] ; Store old nextHeap in output register TransferRtoA
or
nextHeap->buf2 ; Copy the current nextHeap pointer to buffer2 TransferRtoR
A[ir(7-9)]->buf1 ; Copy raw byte size to alloc into buffer1
buf2->A[ir(21-23)] ; Store old nextHeap in output register TransferRtoA
buf1+buf2->buf1 ; Calculate new nextHeap size
buf1->nextHeap ; Store new nextHeap, old one is still in buf2 TransferRtoR
or
A[ir(7-9)]->buf1 ; Copy raw byte size to alloc into buffer1
nextHeap->A[ir(21-23)] ; Store old nextHeap in output register TransferRtoA
nextHeap+buf1->nextHeap ; Calculate new nextHeap size
Not yet.
clear-buf2
nextHeap->buf2(16-31) ; Copy the current nextHeap pointer to buffer2 TransferRtoR
A[ir(7-9)]->buf1 ; Copy raw byte size to alloc into buffer1 first
buf2->A[ir(21-23)] ; Store old nextHeap in output register TransferRtoA
buf1+buf2->buf1 ; Calculate new nextHeap size
buf1(16-31)->nextHeap ; Store new nextHeap, old one is still in buf2 TransferRtoR
I suppose that, here I really ought to do something about over allocation. I could possibly do it by using different buffer registers to do arithmetic on the addresses in 16 bit mode.
abuffer1 16
abuffer2 16 XX
abuf1+buf2->abuf1 with overflow and carry triggering a halt.
clear-buf2
nextHeap->buf2(16-31) ; Copy the current nextHeap pointer to buffer2 TransferRtoR
A[ir(7-9)](16-31)->abuf1
buf2->A[ir(21-23)] ; Store old nextHeap in output register TransferRtoA
abuf1+buf2->abuf1 ; Calculate new nextHeap size
abuf1->nextHeap ; Store new nextHeap, old one is still in buf2 TransferRtoR
I think that this has finally done it. This will halt on failed allocation. Now calls to malloc can compile to an alloc instruction.
I have to be sure to place the return value of a call always in A0.
Now I am about ready to start modifying things to generate new frames.
I'll create a package directory wombat5w and create frames for it.
I'll eventually have to create an assembly language file with the initArray() function in it. The initArray() will have to generate an external call.
I've created the wombat5w code in chapters 6 and 7. I suspect that I'll have to modify the procEntryExit1() and externalCall() in chapter 7.
I want to include the batch file in the zip file that I take home.
This is about all that I can do on chapter 7 until I get the chapter 9 stuff going.
I don't understand why I used the type binding from the frame pointer in the MEM nodes that I created in chapter 7.
I'll probably enhance this once I start chapter 9 for it and understand what is going on.
I also need to change my later Mains to create the new kind of frame for the wombat5w.
I may be able to revise my TestAssemblyCode visitor to take a codegen to use, and then move it to a different package, perhaps.
1/7/2005
Now it's time to start looking at the code generator and revising it to generate Wombat5w code. I'll have to be careful to get the registers right, especially on function calls.
I started another analysis of the code generator here. As of 10/15/2005, I moved it to codegen.txt.
1/9/2005
I have copied the changes back to my home PC, since I have an assignment at work that will probably take time, and I need to work on it at home now.
Something that I need to do soon and might as well do now is to change the scripts to have a setup script that sets the directories containing the class and source files so that I can make the other scripts more platform independent. I'll start back with where I first use the scripts.
I'm making these changes in the "native" copies, not the directory that I downloaded.
C:\c4041s2005\src
setmain.bat (particular to this machine)
C:\c4041s2005\src\chap2\javacc
compile.bat
runmain.bat
C:\c4041s2005\src\chap3\javacc
compile.bat
runmain.bat
I've done all the batch files, with the exception of the ones for tools.
Comments (0)
You don't have permission to comment on this page.