Is there a standard algorithm for converting stack machine ISA to register machine ISA ? In particular, the register allocation part of it.
Example: IIRC, JVM instruction set if stack machine but runs on register machines.
IIRC wasm32 also supports both stack machine and register machine instrs.
Stack machines can converted to SSA form by allocating new SSA values every time you push and keeping a stack of SSA values during translation. For example cranelift-wasm does this. Once you get it into SSA form you can either convert it directly to registers of you have an infinite amount of registers (by implementing phi as moving to the register in the predecessors of the block containing the phi) or use a register allocator if you have a finite amount.
I remember having a cute algorithm for allocating x86 registers when writing compiler backends a long time ago ( like maybe 30 years ago ). I don't quite remember everything about it, but very roughly speaking it could very efficiently decide if the register allocation "problem" was soluble (some kind of counting algorithm), and then if it wasn't, some variable (span) was mapped to local stack storage, the fast (incremental) test was performed again, etc, until a viable allocation was obtained. It had to run very fast, especially as computers were not so fast in those days. That's as much as I can remember right now. It worked very well.
I believe that is similar to what the old cranelift register allocator did. AFAICT it first spilled values as necessary and then did a graph coloring with the knowledge that the graph coloring must exist. It kept 1 register unused to allow for swapping registers as necessary to apply the solution of the graph coloring.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.