In the compiler I'm writing, it uses temporary registers for values such as array subscript offsets, dereferenced values, and results of calculations. My target architecture doesn't have a set amount of registers, and the compiler can't know how many registers there are at compile time; there are at least two general purpose, one flag register, and stack, base, and instruction pointer registers.
Does anyone have an idea how I can use allocate temporary registers if they are there, and otherwise use the stack or another solution if I don't have enough/run out?
[Edited by - Ectara on December 7, 2010 6:35:05 PM]
[C] Temporary Register Allocation
Quote:My target architecture doesn't have a set amount of registers,All architectures have fixed known number of registers. Otherwise the instruction set would become prohibitively verbose.
Quote:Does anyone have an idea how I can use allocate temporary registersRegisters are not allocated, they are a piece of hardware, actual gates in the chip.
Maybe you're asking about a different problem related to register allocation - given local variables and temporaries in source code, how to make most efficient use of CPU registers.
Author
Quote:All architectures have fixed known number of registers. Otherwise the instruction set would become prohibitively verbose.
This architecture is a VM, and has a compile-time constant of how many registers are available.
Quote:Registers are not allocated, they are a piece of hardware, actual gates in the chip.
Quote:Maybe you're asking about a different problem related to register allocation - given local variables and temporaries in source code, how to make most efficient use of CPU registers.
I'm referring to the use of registers for temporary values in an algorithm or compound instructions; with an indefinite amount of registers, incrementing which register is occupied with a temporary risks running out, and using only the basic two registers suffers from not using as many registers as it could.
Quote:Original post by Ectara
This architecture is a VM, and has a compile-time constant of how many registers are available.
What does the VM spec say how this should be handled?
Author
Nothing yet; I haven't gotten around to writing the specification, because I'm not sure how it should be handled, myself. :D
But it must have from 6 to _64_ registers.
EDIT: Clarification
[Edited by - Ectara on December 7, 2010 8:01:17 PM]
But it must have from 6 to _64_ registers.
EDIT: Clarification
[Edited by - Ectara on December 7, 2010 8:01:17 PM]
Quote:Original post by EctaraAh, so this is about finding a solution to a problem that solves the problem that doesn't exist yet.
Nothing yet; I haven't gotten around to writing it. :D
In words of Keanu: Whoa.
Quote:But it must have from 6 to 256 registers.
And how will these registers be addressed? What will the not-yet-existent opcodes for a not-yet-existent VM look like?
It's easy, you need to sum up 256 numbers. How would the assembly look like if it were written manually?
Typically, for load-store architecture, it's something like this:
mov ra, mem[0];mov rb, mem[1]mov rc, mem[2]...mov rz, mem[26]add ra, rbadd ra, rc...add ra, rz// ra now holds sum of first 26 numbers, repeat until doneBut the above are mnemonics - what would opcodes be like: [instr][register_idx][params]?
In that case, what happens if I write [add][137][211] when machine only has 200 registers. Or only 100?
However, given that there are always at least two registers, writing a VM(2) on top of VM(1) would work. VM(2) would then be responsible for generating VM(1) bytecode based on number of registers available.
It might also be fun to implement JVM as VM(3) on top of that and run Ruby as VM(4) on it. Perhaps running some DSL as VM(5) inside it.
But I heard you like VMs, so ...
Author
Quote:Quote:Original post by Ectara
Nothing yet; I haven't gotten around to writing it. :D
Ah, so this is about finding a solution to a problem that solves the problem that doesn't exist yet.
In words of Keanu: Whoa.
What I meant to say was, the VM is written, and there's an ASM and a C compiler that I've written for it already; just a solution to this particular problem is missing. Currently the register count is 16 and I haven't changed that yet, but changing the define changes the number of available registers.
Also, did I say 256? I meant to say 64. Changes in the design later on reduced the upper limit to 64.
Quote:
It's easy, you need to sum up 256 numbers. How would the assembly look like if it were written manually?
Typically, for load-store architecture, it's something like this:
-snip-
The operation could be explained as such:
typedef struct operand{ int flags: 2; int value: 6;};typedef struct operation{ unsigned char opcode; operand operands[3];};If no bits are set in the flags field of an operand, the value bits specify which register.
If the most significant bit is set in the flags field, it is a constant, and the value bits specify the type of constant, which follows the operation after the operands in memory.
If the least significant bit is set of the flags, it is allocated memory, or a variable, and the value bits specify the type, and a 32bit constant containing a hash key for a special variable.
If both bits of the flags are set, it is dereferencing, and the value bits specify which register; to dereference, one must first move the pointer to a register.
It's a bit RISC-like.
But, adding many numbers is no big deal. One could write:
move reg1, $256
move reg0, $0
move reg2, mem ; A pointer, perhaps?
loop:
add reg0, reg0, [reg2]
add reg2, reg2, $4 ; Assuming 32bit integers in contiguous memory.
dec reg1
jnz loop, reg1
Quote:In that case, what happens if I write [add][137][211] when machine only has 200 registers. Or only 100?
If those are register indices, my VM would currently overrun the boundaries, and probably corrupt the stack.
Quote:But I heard you like VMs, so ...
Thanks, Xzibit. :P
How do you plan on writing a compiler if the target architecture isn't fully known? There will be so many things unpredictable that emitting efficient code will be all but impossible.
The best thing I could suggest would be to have the compiler support a variable number of registers in the register scheduler, and just recompile your binaries if the VM's register count changes.
The best thing I could suggest would be to have the compiler support a variable number of registers in the register scheduler, and just recompile your binaries if the VM's register count changes.
Author
Eh... The architecture was designed around the same binary running on all incarnations of the VM. I suppose having to recompile would break that. So, basically, I'd have to have a fixed register count, no matter what? One other idea I had, was to query if there were registers left, and if so, use a register, and if not, have to push something on the stack, and use registers, then pop things back, or dereference the stack pointer, whatever method I'd end up using to free up registers for temporary use.
You could, of course, write the compiler so that it takes "number of registers" as a command-line argument, implements the register allocation assuming that number of registers, and emits the corresponding bytecode. You would, of course, have to recompile each program in order to run on a differently-compiled VM; and this assumes that the number of registers somehow doesn't have a major effect on the instruction set (e.g. the fields in opcodes that specify register ID are always 6 bits wide, just that accessing nonexistent registers causes an exception or "hardware" interrupt or something). Otherwise, I hope you're prepared to buckle down and write 59 separate compilers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
