4 ms·

Skimmed over this... nice write up so far! Notes: * Would be nice to have a TOC for such a long article. * I never implemented a register based VM but I think

Skimmed over this... nice write up so far! Notes: * Would be nice to have a TOC for such a long article. * I never implemented a register based VM but I think I remember one of the trickiest things is to allocate the registers when compiling from a higher level language [1], which I don't think is mentioned in the article? I think the article doesn't concern with this since the sample program just uses the bytecode directly. * Random: been thinking of a DSL that would be able to express a VM logic without having to deal with all the micro details of C... Just found a few academic papers on a quick search investigating the idea, fwiw. [2] [3] 1: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation 2: https://link.springer.com/chapter/10.1007/978-3-540-25935-0_12 https://link.springer.com/chapter/10.1007/978-3-540-25935-0_... 3: https://dl.acm.org/doi/10.1002/spe.434 https://dl.acm.org/doi/10.1002/spe.434

nomemory 5y ago
Thanks for the feedback, I appreciate it. You are right about the TOC, my other long articles have them, but for this one I simply forgot to generate one. I will generate it tomorrow. There's no compiler, and yes you are right managing a limited set of registers is hard when compiling from higher level languages. But there are a few compilers for LC3, so it's not impossible to write them even for such a limiting number of registers. But this is not my area of expertise, so someone more knowledgeable can comment on that.
- userbinator 5y ago
  If 8 registers is "limiting", I don't know what you'd call something like a PIC which has a single accumulator... and yet, C compilers exist for those too. On the bright side, it really reduces the number of choices for register allocation.
  - andi999 5y ago
    I call it painful.
Joker_vD 5y ago
Register allocation is not that hard, especially if you don't do it via graph coloring and have more than 2 general-purpose registers available. Build SSA form, remove critical edges, spill temporaries until the number of simultaneously live temporaries is strictly less than the number of available registers, assign registers in a straightforward manner, move out of SSA (that's where that one unused register may come in handy). See [0] and its bibliography for more details. [0] https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR2006-13.pdf https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR20...

nomemory 5y ago

Thanks for the feedback, I appreciate it. You are right about the TOC, my other long articles have them, but for this one I simply forgot to generate one. I will generate it tomorrow. There's no compiler, and yes you are right managing a limited set of registers is hard when compiling from higher level languages. But there are a few compilers for LC3, so it's not impossible to write them even for such a limiting number of registers. But this is not my area of expertise, so someone more knowledgeable can comment on that.

userbinator 5y ago
If 8 registers is "limiting", I don't know what you'd call something like a PIC which has a single accumulator... and yet, C compilers exist for those too. On the bright side, it really reduces the number of choices for register allocation.
- andi999 5y ago
  I call it painful.

Joker_vD 5y ago

Register allocation is not that hard, especially if you don't do it via graph coloring and have more than 2 general-purpose registers available. Build SSA form, remove critical edges, spill temporaries until the number of simultaneously live temporaries is strictly less than the number of available registers, assign registers in a straightforward manner, move out of SSA (that's where that one unused register may come in handy). See [0] and its bibliography for more details. [0] https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR2006-13.pdf https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR20...