Comment by emmanueloga_ | Hacker News Reader

Comment by emmanueloga_ | Hacker News Reader

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

2: https://link.springer.com/chapter/10.1007/978-3-540-25935-0_...

3: https://dl.acm.org/doi/10.1002/spe.434

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...

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.

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.

I call it painful.

Reply on news.ycombinator.com