<p>I have some experience in writing stack based VM's and am now thinking about implementing an interpreter based on registers. I have not yet started anything and the project is still in planning phase. Before I start I wanted to ask a few questions.</p>
<ol>
<li>How many registers should I keep?</li>
<li>What to do if they are used up? Do I keep a backup stack for this case? Or do I keep the register count dynamic?</li>
<li>How to decide which register to use? How to find one which is empty <em>efficiently</em>?</li>
</ol>

<compilers><virtual-machine><registers>
What to do when registers are used up in a register based VM?
CC BY-SA 4.0
2024-07-30T09:29:49.067Z
'How to decide which register to use?' you need to make a register allocator https://en.wikipedia.org/wiki/Register_allocation.  i believe register-based bytecode vms typically use an infinite number of registers; if you do it that way then you do not have to worry about spilling
Moonchild
CC BY-SA 4.0
2024-07-30T09:38:51.110Z
As I generally code in rust, I looked up some examples and I found that the registers are generally implemented using an `enum`. But thanks for the help, will look into it
Timsib Adnap
CC BY-SA 4.0
2024-07-30T14:50:20.177Z
Lua is register based (actually, a weird hybrid thats actually really cool), and I can confirm it has infinite registers
Seggan
CC BY-SA 4.0
2024-07-30T19:57:50.197Z
"*do I keep the register count dynamic?*" - that sounds like just using RAM, i.e. global memory. Afaict, registers are used at all only because their fixed number enables certain optimisations (from hardware implementation to fixed register address size in instructions). Those may or may not matter for your VM.
Bergi
CC BY-SA 4.0
2024-07-31T03:26:55.713Z
I can't tell if your question is about what a front-end compiler should do when it runs out of registers targeting a register-based (VM) machine, or if it is about how to design the machine code instruction set for a register-based VM (e.g. so as to allow infinite registers and trade off encoding space for execution efficiency), or about how to do VM machine code register to CPU register mapping (given that real CPUs have fixed register resources).
Erik Eidt
CC BY-SA 4.0
2024-07-31T04:09:32.200Z
Well, I was asking about both actually, how many to set while designing the instruction set (sub question 1), as well as what to do when the decided number of registers are used up (sub question 2)
Timsib Adnap
<p>If you intend to allow recursion you need to have some kind of stack to store the stack frames anyway.</p>
<p>Then you can use that data structure as the backup stack.</p>
<p>With that you can restrict the amount of registers to whatever fits in your byte code and add some ways to read and write the stack into registers.</p>
<p>The simplest way to allocate registers starting from a stack-based VM is to treat the registers as a circular buffer representing the top of the stack.</p>
<p>To do this you need to keep track of the stack state as it would be executed. When you need a new register you push the bottom most variable still in a register to the stack. When you run out of values in the registers you start popping as needed.</p>

CC BY-SA 4.0
2024-07-30T10:00:15.660Z
2024-07-30T10:00:15.660Z
ratchet freak
CC BY-SA 4.0
2024-07-30T13:27:22.903Z
So what I understand is
- A stack is required in any case, which can also be used a backup
- Implement the register as _array_ (kind of stack) for fixed size?
Timsib Adnap
CC BY-SA 4.0
2024-07-30T13:29:54.687Z
in this particular register allocation scheme the registers are a cache of the top of the stack and have a fixed mapping. More complex allocation schemes exist and might be worth looking into. I just wanted to highlight a simple one that would allow you to get started.
ratchet freak
CC BY-SA 4.0
2024-07-30T13:35:43.787Z
Oh, okay I understand the use of register along side stack as a cache. As for other allocation schemes are you talking about Naive, Linear Scan and the likewise?
Timsib Adnap
CC BY-SA 4.0
2024-07-30T14:36:14.013Z
or some of the fancy algorithms that do larger lifetime analysis
ratchet freak
<blockquote>
<p>how many to set while designing the instruction set (sub question 1),</p>
</blockquote>
<p>In industry, this would typically be done by research: analysis of studies.  Proposals would be made and analyzed against certain workloads.  Ideally, a (front-end) compiler would be mocked up (but hand writing/tuning also a possibility).  And also a (cycle accurate) instruction set simulator to capture performance including instruction cache misses &amp; possibly page faults, which is where code density comes into play as excessively large instructions will cause code bloat and show up here.  Simulations would be run and the best of a set of candidates would emerge.  So, maybe 4-bit register fields would be put up against 6-bit register fields, for example.  (YMMV whether targeting new hardware designs, a software interpreter, or a dynamic JIT compiler.)</p>
<p>The (front-end) compiler should employ some kind of register allocation — the smarter the better (e.g. graph coloring with other optimizations), since these tools run at development time, by developers, and typically on superior hardware.  The compilers will need some general way to access local memory, such as when the input code declares a local array.  If a compilation runs out of (VM) registers, then the compiler will (allocate and) spill/reload (VM) registers as necessary to local stack storage (equivalent to read/write to a local array at some constant index), so that the VM never really sees an out of (VM) registers situation — there's no real way for the VM bytecode to be sure that the program/procedure is actually out of registers or not, since, by definition, there's an architectural limit and mitigation is the front-end compiler's job.</p>
<p>If the VM instruction set's choice of registers available is small then the VM interpreter / JIT compiler may have little difficulty mapping VM registers to hardware resources; however, if the VM's choice of registers is large, then might have greater difficulty especially on hardware with limited internal register resources, and put greater pressure on the interpreter/JIT to manage the registers.  However, I would assert that the interpreter/JIT could allocate the first N (lowest N) VM registers to hardware registers and any rest to hardware local stack memory.  Thus, it would be simpler for the interpreter/JIT — though then that puts more pressure on the the (front-end) compiler as should now also then favor lower register numbers even when there is a large VM register set available — this applies especially for heavily used registers as user variables (the more heavily used, the lower its register number), and also implies reuse of lower numbered VM registers for non-overlapping temporaries, rather than grabbing a new higher numbered (as yet unused) register.</p>
<p>Lets' further note that if your target is JIT'ting, then code density at the VM instruction set level is of only minor concern as the input bytecode will be translated to native anyway, vs. interpretation or hardware implementation where this is more important.</p>

CC BY-SA 4.0
2024-07-31T13:36:52.420Z
2024-07-31T17:46:29.433Z
2024-07-31T17:46:29.433Z
Erik Eidt
<p>The way it's phrased, the answer would be gracefully crash, i.e. stop execution, unwind stacks, execute finalizers, release resources.
The rationale behind the answer is that the sub question one is virtually infinite, likely 2^32 per stack frame. Sub question two no longer makes sense. Sub question three is answered by &quot;just pick the next every time you need a register&quot;.</p>
<p>The overall rationale behind the position is that if you do not need to optimize, it's easy to use and easy to implement. If you need to optimize, you are in a good starting position for optimizations because adequate lifetimes can still be deduced.</p>

CC BY-SA 4.0
2024-07-30T15:00:17.930Z
2024-07-30T15:00:17.930Z
feldentm
# What to do when registers are used up in a register based VM?
Posted by: username_0 on 2024-07-30
I have some experience in writing stack based VM's and am now thinking about implementing an interpreter based on registers. I have not yet started anything and the project is still in planning phase. Before I start I wanted to ask a few questions.

1. How many registers should I keep?
2. What to do if they are used up? Do I keep a backup stack for this case? Or do I keep the register count dynamic?
3. How to decide which register to use? How to find one which is empty *efficiently*?
**Tags:** compilers virtual-machine registers
> **Comments:**
> **username_1**: 'How to decide which register to use?' you need to make a register allocator https://en.wikipedia.org/wiki/Register_allocation.  i believe register-based bytecode vms typically use an infinite number of registers; if you do it that way then you do not have to worry about spilling  
> **username_0**: As I generally code in rust, I looked up some examples and I found that the registers are generally implemented using an `enum`. But thanks for the help, will look into it  
> **username_2**: Lua is register based (actually, a weird hybrid thats actually really cool), and I can confirm it has infinite registers  
> **username_3**: "*do I keep the register count dynamic?*" - that sounds like just using RAM, i.e. global memory. Afaict, registers are used at all only because their fixed number enables certain optimisations (from hardware implementation to fixed register address size in instructions). Those may or may not matter for your VM.  
> **username_4**: I can't tell if your question is about what a front-end compiler should do when it runs out of registers targeting a register-based (VM) machine, or if it is about how to design the machine code instruction set for a register-based VM (e.g. so as to allow infinite registers and trade off encoding space for execution efficiency), or about how to do VM machine code register to CPU register mapping (given that real CPUs have fixed register resources).  
> **username_0**: Well, I was asking about both actually, how many to set while designing the instruction set (sub question 1), as well as what to do when the decided number of registers are used up (sub question 2)  
---
## 3 answers
### Answer by username_5 on 2024-07-30. Score: 1 | Accepted answer
If you intend to allow recursion you need to have some kind of stack to store the stack frames anyway.

Then you can use that data structure as the backup stack.

With that you can restrict the amount of registers to whatever fits in your byte code and add some ways to read and write the stack into registers.

The simplest way to allocate registers starting from a stack-based VM is to treat the registers as a circular buffer representing the top of the stack.

To do this you need to keep track of the stack state as it would be executed. When you need a new register you push the bottom most variable still in a register to the stack. When you run out of values in the registers you start popping as needed.
> **Comments:**
> **username_0** (2024-07-30): So what I understand is
- A stack is required in any case, which can also be used a backup
- Implement the register as _array_ (kind of stack) for fixed size?  
> **username_5** (2024-07-30): in this particular register allocation scheme the registers are a cache of the top of the stack and have a fixed mapping. More complex allocation schemes exist and might be worth looking into. I just wanted to highlight a simple one that would allow you to get started.  
> **username_0** (2024-07-30): Oh, okay I understand the use of register along side stack as a cache. As for other allocation schemes are you talking about Naive, Linear Scan and the likewise?  
> **username_5** (2024-07-30): or some of the fancy algorithms that do larger lifetime analysis  
---
### Answer by username_4 on 2024-07-31. Score: 1
> how many to set while designing the instruction set (sub question 1),

In industry, this would typically be done by research: analysis of studies.  Proposals would be made and analyzed against certain workloads.  Ideally, a (front-end) compiler would be mocked up (but hand writing/tuning also a possibility).  And also a (cycle accurate) instruction set simulator to capture performance including instruction cache misses & possibly page faults, which is where code density comes into play as excessively large instructions will cause code bloat and show up here.  Simulations would be run and the best of a set of candidates would emerge.  So, maybe 4-bit register fields would be put up against 6-bit register fields, for example.  (YMMV whether targeting new hardware designs, a software interpreter, or a dynamic JIT compiler.)

The (front-end) compiler should employ some kind of register allocation — the smarter the better (e.g. graph coloring with other optimizations), since these tools run at development time, by developers, and typically on superior hardware.  The compilers will need some general way to access local memory, such as when the input code declares a local array.  If a compilation runs out of (VM) registers, then the compiler will (allocate and) spill/reload (VM) registers as necessary to local stack storage (equivalent to read/write to a local array at some constant index), so that the VM never really sees an out of (VM) registers situation — there's no real way for the VM bytecode to be sure that the program/procedure is actually out of registers or not, since, by definition, there's an architectural limit and mitigation is the front-end compiler's job.

If the VM instruction set's choice of registers available is small then the VM interpreter / JIT compiler may have little difficulty mapping VM registers to hardware resources; however, if the VM's choice of registers is large, then might have greater difficulty especially on hardware with limited internal register resources, and put greater pressure on the interpreter/JIT to manage the registers.  However, I would assert that the interpreter/JIT could allocate the first N (lowest N) VM registers to hardware registers and any rest to hardware local stack memory.  Thus, it would be simpler for the interpreter/JIT — though then that puts more pressure on the the (front-end) compiler as should now also then favor lower register numbers even when there is a large VM register set available — this applies especially for heavily used registers as user variables (the more heavily used, the lower its register number), and also implies reuse of lower numbered VM registers for non-overlapping temporaries, rather than grabbing a new higher numbered (as yet unused) register.

Lets' further note that if your target is JIT'ting, then code density at the VM instruction set level is of only minor concern as the input bytecode will be translated to native anyway, vs. interpretation or hardware implementation where this is more important.
---
### Answer by username_6 on 2024-07-30. Score: 1
The way it's phrased, the answer would be gracefully crash, i.e. stop execution, unwind stacks, execute finalizers, release resources.
The rationale behind the answer is that the sub question one is virtually infinite, likely 2^32 per stack frame. Sub question two no longer makes sense. Sub question three is answered by "just pick the next every time you need a register".

The overall rationale behind the position is that if you do not need to optimize, it's easy to use and easy to implement. If you need to optimize, you are in a good starting position for optimizations because adequate lifetimes can still be deduced.
---
