Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
An instruction selector in a rudimentary compiler.
"""
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)
('xor', vreg1, vreg1)
('move', vreg2, vreg1)
('sub', vreg2, 6)
('move', vreg3, vreg2)
('add', vreg3, 2)
"""
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))
"""
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
"""
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)
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment