Register-machine can shift graph-coloring from JIT to AOT
There are repeated holy wars at byte-code virtual machine interpreters - stack-machine vs register-machine.
One of the benefits of stack-machines is ease of allocating host machine's register at JIT compilation.
There is a decent assumption that the order of stack element matches access frequency.
Top element of stack has huge access frequency, then next element has next amount of frequency.
So, allocating host's registers from the element of stack top toward below elements of stack eliminates decent amount of memory access by accessing registers instead.
By contrast, it is believed that this scheme can't be applied to register-machines.
Since all virtual registers are symmetric, access frequncy of each register also should be symmetric.
This must be true, if byte-code generators also assume all virtual registers are symmetric.
But, if byte-code generators try creating deflection?
For example, a simplified graph-coloring algorithm from one by famous Gregory Chaitin can do that.
A vertex with N edges in the graph means this vertex can get registers within (N+1)th.
So N+1 regsiters are enough for a graph with vertices with max N edges.
Spilling vertices which have max edges from the graph reduce registers for the graph.
Then we'll get a graph with N registers allocated.
After getting the graph with N registers, we can get the graph with N+1 registers by restoring vertices spilled at time when the graph still contains vertices with N edges.
When we restore back vertices, all these vertices can get (N+1)th register without chainging register allocation for other vertices.
This means the register allocation result from this algorithm is incremental.
Leaving 1st register only and rest registers to spill is same result which this algorithm produces with one register at the beginning.
Then the result with 2nd register restored back is also same with the case there are two registers, and so on.
Under these byte-code generators for register-machine, register allocation at JIT becomes simple and powerful.
Only allocate host's register from 1st virtual register to Nth one in case host machine provides N register.
And you'll get the powerful result from graph-coloring schemes.
-- See also --
The design of the Inferno virtual machine
http://www.vitanuova.com/inferno/papers/hotchips.html
The authors of this virtual machine aim the performance with JIT.
But from tiny benchmarks on my environment, neither Inferno's byte-code generator nor JIT seams to treat register allocation yet.
Combining Offline and Online Optimizations: Register Allocation and Method Inlining
http://pdfs.semanticscholar.org/9a4a/d55afd9159f037aa163cbf4a5a770a49999c.pdf
What I wrote above is called "cumulative register assignment" on this thesis that such researchers visited before.
One of the benefits of stack-machines is ease of allocating host machine's register at JIT compilation.
There is a decent assumption that the order of stack element matches access frequency.
Top element of stack has huge access frequency, then next element has next amount of frequency.
So, allocating host's registers from the element of stack top toward below elements of stack eliminates decent amount of memory access by accessing registers instead.
By contrast, it is believed that this scheme can't be applied to register-machines.
Since all virtual registers are symmetric, access frequncy of each register also should be symmetric.
This must be true, if byte-code generators also assume all virtual registers are symmetric.
But, if byte-code generators try creating deflection?
For example, a simplified graph-coloring algorithm from one by famous Gregory Chaitin can do that.
A vertex with N edges in the graph means this vertex can get registers within (N+1)th.
So N+1 regsiters are enough for a graph with vertices with max N edges.
Spilling vertices which have max edges from the graph reduce registers for the graph.
Then we'll get a graph with N registers allocated.
After getting the graph with N registers, we can get the graph with N+1 registers by restoring vertices spilled at time when the graph still contains vertices with N edges.
When we restore back vertices, all these vertices can get (N+1)th register without chainging register allocation for other vertices.
This means the register allocation result from this algorithm is incremental.
Leaving 1st register only and rest registers to spill is same result which this algorithm produces with one register at the beginning.
Then the result with 2nd register restored back is also same with the case there are two registers, and so on.
Under these byte-code generators for register-machine, register allocation at JIT becomes simple and powerful.
Only allocate host's register from 1st virtual register to Nth one in case host machine provides N register.
And you'll get the powerful result from graph-coloring schemes.
-- See also --
The design of the Inferno virtual machine
http://www.vitanuova.com/inferno/papers/hotchips.html
The authors of this virtual machine aim the performance with JIT.
But from tiny benchmarks on my environment, neither Inferno's byte-code generator nor JIT seams to treat register allocation yet.
Combining Offline and Online Optimizations: Register Allocation and Method Inlining
http://pdfs.semanticscholar.org/9a4a/d55afd9159f037aa163cbf4a5a770a49999c.pdf
What I wrote above is called "cumulative register assignment" on this thesis that such researchers visited before.
