It still can be done much cheaper. I just fixed my excessively cheap register allocator for my c compiler rcc.<p>The register allocator is a simple first-fit bitmask with no spilling to stack except for the two predefined spill slots. Only if all 8 registers are in use, it spills the additional registers on the stack.
What they call guest registers. 
No SSA and no BB needed. No crazy mem2reg or graph-coloring. Only once per function.<p>Only for very big functions one register is spilled, usually just rsi.<p>Benchmarks:<p><pre><code>    | Compiler | Compile (ms) | Execute (ms) | Total (ms) |
    | :------- | -----------: | -----------: | ---------: |
    | RCC      |           61 |          754 |        815 |
    | TCC      |            8 |          628 |        636 |
    | SLIMCC   |           74 |          642 |        716 |
    | KEFIR    |          270 |          765 |       1035 |
    | GCC0     |           83 |          637 |        720 |
    | GCCO2    |          204 |          227 |        431 |
    | CLANG0   |          377 |          620 |        997 |
    | CLANGO2  |          310 |          221 |        531 |</code></pre>

HN

Low-Compilation-Cost Register Allocation in LLVM-Based Binary Translation

Comments (4)