Re:Writing a register based VM in less than 125 lines of C code
by Joker_vD on Thursday December 09, 2021 @04:50AM
(#29495538)
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/RR20...
Re:Writing a register based VM in less than 125 lines of C code
by nomemory on Wednesday December 08, 2021 @08:46PM
(#29492857)
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.
Re:Writing a register based VM in less than 125 lines of C code
by userbinator on Thursday December 09, 2021 @12:14AM
(#29494067)
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.
* 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
2: https://link.springer.com/chapter/10.1007/978-3-540-25935-0_...
3: https://dl.acm.org/doi/10.1002/spe.434