Compiler In Plain Python: Register Allocation

Followup to the Instruction Select

The latest code compiles out actual real-mode x86 assembly code that could run, although it wouldn't do anything interesting yet. Theoretically I could have done this in few hours after the previous changes, but there have been other things pressing on. Anyway there you have it: Early results from a real, parametric, retargetable compiler:

use16
org 0x0
xor ax, ax
sub ax, 6
mov cx, ax
add cx, 2
xor ax, ax
sub ax, 6
mov bx, ax
add bx, 2
mov ax, cx
sub ax, bx

To make it possible I had to make the instruction tiling functions generate code -objects that have their data flow annotated. Using the data flow, I generated an interference graph. Since the graph isn't very complex in the above sample, it is trivially colorable. I could've just colored it, but instead I did it in a way that'd let me build a chaitin-briggs allocator out of it eventually. Actually, I'm not sure if it's good idea to build that kind of allocator. The greedy interval based register allocation scheme once used by LLVM seems quite simple to implement in python. Anyway next I may do some of the following:

More instruction tilings and a simple program that is able to run in place of MenuetOS kernel.
Control flow graphs and rest of the NOLTIS algorithm.
Coalescing and spilling into register allocator.
Stack reservation and allocation to allow spilling.
Name and repository for the project.
Considerations for other target machines.
Type differentiation into instruction selection patterns.

Though it may be weeks or months until I return to this project.

Compiler In Plain Python: Register Allocation

Similar posts