An instruction selector in a rudimentary compiler.

instruction_select.py

"""
    Select instructions to emit

    If I've read recent papers then this is not very different from what LLVM or GCC is doing.
"""
class Tile(object):
    def __init__(self, cost, pat, code):
        self.cost = cost
        self.pat = pat
        self.code = code

def choose(code, tiles):
    for node in code.postorder([]):
        best = float('inf')
        for pat, base, code in tiles:
            if pat.match(node):
                cost = pat.estimate(node, base)
                if cost < best:
                    best = cost
                    node.tile = Tile(cost, pat, code)

def gen(node, block):
    return node.tile.code(node, block)

def select(code, tiles, block):
    choose(code, tiles)
    return gen(code, block)

output

('xor', vreg1, vreg1)
('move', vreg2, vreg1)
('sub', vreg2, 6)
('move', vreg3, vreg2)
('add', vreg3, 2)

patterns.py

"""
    Forms the graphs to map instructions
    into tiles.
"""
from structures import *

class PFunc(object):
    def __init__(self, match):
        self.match = match

    def estimate(self, node, base):
        return base

    def tile_estimate(self, node):
        return node.tile.cost if node.tile is not None else float('inf')

class PConst(object):
    def __init__(self, value):
        self.value = value

    def match(self, node):
        if isinstance(node, Const):
            return node.value == self.value

    def estimate(self, node, base):
        return base

    def tile_estimate(self, node):
        return node.tile.cost if node.tile is not None else float('inf')

class POp(object):
    def __init__(self, name, operands):
        self.name = name
        self.operands = operands
        self.leaf = False

    def __getitem__(self, index):
        return self.operands[index]

    def __len__(self):
        return len(self.operands)

    def match(self, node):
        if not isinstance(node, Op):
            return False
        if node.name != self.name:
            return False
        if len(self) != len(node):
            return False
        return all(pat.match(sn) for pat, sn in zip(self, node))

    def estimate(self, node, base):
        return base + sum(pat.tile_estimate(sn) for pat, sn in zip(self, node))

    def tile_estimate(self, node):
        return self.estimate(node, 0)

Any = PFunc(lambda node: True)
Int = PFunc(lambda node: isinstance(node, Const) and isinstance(node.value, int))

scratch.py

"""
    This is the entry point.
"""
import instruction_select
from structures import *
from patterns import *
from x86_realmode_tiles import tiles

code = Op('add', [
    Op('sub', [Const(0), Const(6)]), Const(2)])

block = []
dst = instruction_select.select(code, tiles, block)
for row in block:
    print row

structures.py

"""
    Intermediate representation for
    programs.
"""
class Const(object):
    def __init__(self, value, klass=None):
        self.value = value
        self.klass = klass
        self.tile = None

    def postorder(self, prefix):
        prefix.append(self)
        return prefix

class Op(object):
    def __init__(self, name, operands):
        self.name = name
        self.operands = operands
        self.tile = None

    def __getitem__(self, index):
        return self.operands[index]

    def __len__(self):
        return len(self.operands)

    def postorder(self, prefix):
        for operand in self.operands:
            operand.postorder(prefix)
        prefix.append(self)
        return prefix

class VReg(object):
    next_uid = 1
    def __init__(self, assign=None, klass=None):
        self.assign = assign
        self.klass = klass
        self.uid = VReg.next_uid
        VReg.next_uid += 1

    def __repr__(self):
        return 'vreg{}'.format(self.uid)

x86_realmode_tiles.py

from instruction_select import gen
from structures import *
from patterns import *
tiles = []

def tile(pat, cost):
    def _deco_(code):
        tiles.append((pat, cost, code))
        return code
    return _deco_

@tile(PConst(0), 10)
def _(const, block):
    dst = VReg()
    block.append(('xor', dst, dst))
    return dst

@tile(Int, 10)
def _(const, block):
    dst = VReg()
    block.append(('move', dst, const.value))
    return dst

@tile(POp('add', [Any, Int]), 15)
def _(op, block):
    src1 = gen(op[0], block)
    src2 = op[1].value
    dst = VReg()
    block.append(('move', dst, src1))
    block.append(('add', dst, src2))
    return dst

@tile(POp('add', [Any, Any]), 20)
def _(op, block):
    src1 = gen(op[0], block)
    src2 = gen(op[1], block)
    dst = VReg()
    block.append(('move', dst, src1))
    block.append(('add', dst, src2))
    return dst

@tile(POp('sub', [Any, Int]), 15)
def _(op, block):
    src1 = gen(op[0], block)
    src2 = op[1].value
    dst = VReg()
    block.append(('move', dst, src1))
    block.append(('sub', dst, src2))
    return dst

@tile(POp('sub', [Any, Any]), 20)
def _(op, block):
    src1 = gen(op[0], block)
    src2 = gen(op[1], block)
    dst = VReg()
    block.append(('move', dst, src1))
    block.append(('sub', dst, src2))
    return dst