Mercurial > lcfOS
changeset 269:5f8c04a8d26b
Towards better modularity
author | Windel Bouwman |
---|---|
date | Sun, 18 Aug 2013 17:43:18 +0200 |
parents | 5ec7580976d9 |
children | cdc76d183bcc |
files | python/c3/codegenerator.py python/codegenarm.py python/flowgraph.py python/graph.py python/instructionselector.py python/ir/basicblock.py python/ir/function.py python/irmach.py python/registerallocator.py python/tcodegen.py python/trunner.sh python/trunner2.sh |
diffstat | 12 files changed, 351 insertions(+), 285 deletions(-) [+] |
line wrap: on
line diff
--- a/python/c3/codegenerator.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/c3/codegenerator.py Sun Aug 18 17:43:18 2013 +0200 @@ -40,7 +40,11 @@ def genFunction(self, fn): # TODO: handle arguments f = self.funcMap[fn] + # TODO reserve room for stack, this can be done at later point? self.setFunction(f) + l2 = self.newBlock() + self.emit(ir.Jump(l2)) + self.setBlock(l2) # generate room for locals: for sym in fn.innerScope: @@ -51,7 +55,8 @@ self.genCode(fn.body) # TODO handle return? - self.emit(ir.Return(ir.Const(0))) + self.emit(ir.Jump(f.epiloog)) + #self.emit(ir.Return(ir.Const(0))) self.setFunction(None) def genCode(self, code):
--- a/python/codegenarm.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/codegenarm.py Sun Aug 18 17:43:18 2013 +0200 @@ -3,40 +3,14 @@ from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo import cortexm3 as arm from ppci import CompilerError -import irmach - - -class InstructionSelector: - def newTmp(self): - return 't999' - - def munchProgram(self, p): - assert isinstance(p, ir.Module) - self.result = [] - for f in p.Functions: - for bb in f.BasicBlocks: - for i in bb.Instructions: - self.munchStm(i) - return self.result - - def emit(self, *args, **kwargs): - """ Abstract instruction emitter """ - i = irmach.AbstractInstruction(*args, **kwargs) - self.result.append(i) - - def munchStm(self, s): - raise NotImplementedError() - - def munchExpr(self, e): - raise NotImplementedError() - - -class RegisterAllocator: - """ Target independent register allocator """ - pass +import graph +import flowgraph +import registerallocator +from instructionselector import InstructionSelector class ArmInstructionSelector(InstructionSelector): + """ Instruction selector for the arm architecture """ def munchExpr(self, e): if isinstance(e, ir.Alloc): return 0 @@ -46,11 +20,17 @@ d = self.newTmp() self.emit('add %d0, %s0, %s1', dst=[d], src=[a, b]) return d + elif isinstance(e, ir.Binop) and e.operation == '-': + a = self.munchExpr(e.value1) + b = self.munchExpr(e.value2) + d = self.newTmp() + self.emit('sub %d0, %s0, %s1', dst=[d], src=[a, b]) + return d elif isinstance(e, ir.Binop) and e.operation == '|': a = self.munchExpr(e.value1) b = self.munchExpr(e.value2) d = self.newTmp() - self.emit('orrrr %d0, %s0, %s1', dst=[d], src=[a, b]) + self.emit('or %d0, %s0, %s1', dst=[d], src=[a, b]) return d elif isinstance(e, ir.Binop) and e.operation == '<<': a = self.munchExpr(e.value1) @@ -62,14 +42,14 @@ a = self.munchExpr(e.value1) b = self.munchExpr(e.value2) d = self.newTmp() - self.emit('mylll %d0, %s0, %s1', dst=[d], src=[a, b]) + self.emit('mul %d0, %s0, %s1', dst=[d], src=[a, b]) return d elif isinstance(e, ir.Const): d = self.newTmp() if e.value < 256: self.emit('ldr %d0, {}'.format(e.value), dst=[d]) else: - self.emit('ldrpcrel TODO') + self.emit('ldrpcrel TODO', dst=[d]) return d elif isinstance(e, ir.Mem): # Load from memory @@ -78,7 +58,7 @@ self.emit('ldr %d0, [%s0]', src=[loc], dst=[d]) return d elif isinstance(e, ir.Temp): - return e + return self.getTempReg(e) else: raise NotImplementedError('--> {}'.format(e)) @@ -89,217 +69,48 @@ self.emit('str [%s0], %s1') elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Temp): val = self.munchExpr(s.src) - self.emit('str %d0, %s0', dst=[s.dst], src=[val]) + dreg = self.getTempReg(s.dst) + self.emit('mov %d0, %s0', dst=[dreg], src=[val]) elif isinstance(s, ir.Return): - self.emit('ret') + #etgt = self.targets[ + self.emit('jmp exit', jumps=[]) elif isinstance(s, ir.Jump): - self.emit('jmp {}'.format(s)) + tgt = self.targets[s.target] + self.emit('jmp {}'.format(s), jumps=[tgt]) elif isinstance(s, ir.CJump): - self.munchExpr(s.a) - self.munchExpr(s.b) - self.emit('jmp {}'.format(s)) + a = self.munchExpr(s.a) + b = self.munchExpr(s.b) + self.emit('cmp %s0, %s1', src=[a, b]) + ntgt = self.targets[s.lab_no] + ytgt = self.targets[s.lab_yes] + jmp_ins = self.makeIns('jmp {}'.format(s.lab_no), jumps=[ntgt]) + # Explicitely add fallthrough: + self.emit('jeq {}'.format(s.lab_yes), jumps=[ytgt, jmp_ins]) + self.emit2(jmp_ins) else: raise NotImplementedError('--> {}'.format(s)) class ArmCodeGenerator: def __init__(self, outs): + # TODO: schedule traces in better order. + # This is optional! self.ins_sel = ArmInstructionSelector() self.outs = outs self.outs.getSection('code').address = 0x08000000 self.outs.getSection('data').address = 0x20000000 - def generate(self, ircode): - self.ins_sel.munchProgram(ircode) + def generate(self, ircode, cfg_file=None, ig_file=None): + x = self.ins_sel.munchProgram(ircode) + cfg = flowgraph.FlowGraph(x) + if cfg_file: + cfg.to_dot(cfg_file) + ig = registerallocator.InterferenceGraph(cfg) + if ig_file: + ig.to_dot(ig_file) + + regs = ['r0', 'r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7'] + ra = registerallocator.RegisterAllocator() + ra.registerAllocate(ig, regs) -class ArmCodeGenerator_old: - """ - Simple code generator - Ad hoc implementation - """ - def __init__(self, out): - self.outs = out - self.logger = logging.getLogger('codegenarm') - - def emit(self, item): - self.outs.emit(item) - - def generate(self, ircode): - assert isinstance(ircode, ir.Module) - self.logger.info('Generating arm code for {}'.format(ircode.name)) - self.available_regs = {arm.r3, arm.r4, arm.r5, arm.r6, arm.r7} - self.regmap = {} - # TODO: get these from linker descriptor? - self.outs.getSection('code').address = 0x08000000 - self.outs.getSection('data').address = 0x20000000 - self.outs.selectSection('data') - - for gvar in ircode.Variables: - self.emit(Label(gvar.name)) - # TODO: use initial value: - self.dcd(0) - - self.imms = [] # list with immediates relative to PC. - self.outs.selectSection('code') - - # Manually inserted startup code: - self.dcd(0x20000678) # initial stack ptr - # TODO: use label here: - #self.emit(arm.dcd_ins(LabelRef('reset'))) # reset vector - self.dcd(0x08000009) # reset vector, lsb indicates thumb mode - self.emit(arm.bl_ins(LabelRef('main'))) - - self.emit(Label('reset')) - for f in ircode.Functions: - self.localVars = [] - # Add global variable addresses to immediate list: - for gvar in ircode.Variables: - pass #self.imms.append(( - - self.stack_frame = [] - self.emit(Label(f.name)) - # Save some registers: - self.emit(arm.push_ins(arm.RegisterSet({arm.r3, arm.r4, arm.r5, arm.r6,arm.r7,arm.lr}))) - for bb in f.BasicBlocks: - self.emit(Label(bb.name)) - for ins in bb.Instructions: - self.generateInstruction(ins) - - self.align() - while self.imms: - l, v = self.imms.pop() - self.emit(Label(l)) - self.dcd(v) - self.align() - self.outs.backpatch() - self.outs.backpatch() - codesize = self.outs.getSection('code').Size - self.logger.info('Generated {} bytes code'.format(codesize)) - - def dcd(self, x): - self.emit(arm.dcd_ins(Imm32(x))) - - def align(self): - self.outs.emit(Alignment(4)) - - # Helper functions: - def getStack(self, v): - off = self.stack_frame.index(v) - return off * 4 - - def addStack(self, v): - self.stack_frame.append(v) - return self.getStack(v) - - def getGlobal(self, r, g): - _global_address = g.name + '__global' - self.emit(arm.ldr_pcrel(r, LabelRef(_global_address))) - - def loadStack(self, reg, val): - self.emit(arm.ldr_sprel(reg, arm.MemSpRel(self.getStack(val)))) - - def getreg(self, v): - if not v in self.regmap: - self.regmap[v] = self.available_regs.pop() - return self.regmap[v] - - def freereg(self, v, ins): - if v.lastUse(ins): - r = self.regmap.pop(v) - assert r not in self.regmap.values() - self.available_regs.add(r) - - def comment(self, txt): - self.emit(Comment(txt)) - - def debugInfo(self, loc): - if loc: - self.emit(DebugInfo(loc)) - - def generateInstruction(self, ins): - self.comment(str(ins)) - if hasattr(ins, 'debugLoc'): - self.debugInfo(ins.debugLoc) - if type(ins) is ir.Branch: - tgt = LabelRef(ins.target.name) - self.emit(arm.b_ins(tgt)) - elif type(ins) is ir.ImmLoad: - lname = ins.target.name + '_ivalue' - r0 = self.getreg(ins.target) - self.emit(arm.ldr_pcrel(r0, LabelRef(lname))) - self.imms.append((lname, ins.value)) - elif type(ins) is ir.Store: - # Load value in r0: - r0 = self.getreg(ins.value) - # store in memory: - # TODO: split globals and locals?? - #self.getGlobal(arm.r1, ins.location) - # Horrible hack with localVars - if ins.location in self.localVars: - # The value was alloc'ed - self.emit(arm.str_sprel(r0, arm.MemSpRel(self.getStack(ins.location)))) - else: - r1 = self.getreg(ins.location) - self.emit(arm.storeimm5_ins(r0, arm.MemR8Rel(r1, 0))) - self.freereg(ins.location, ins) - self.freereg(ins.value, ins) - elif type(ins) is ir.Load: - # TODO: differ global and local?? - #self.getGlobal(arm.r0, ins.location) - r0 = self.getreg(ins.value) - if ins.location in self.localVars: - self.emit(arm.ldr_sprel(r0, arm.MemSpRel(self.getStack(ins.location)))) - else: - r2 = self.getreg(ins.location) - self.emit(arm.loadimm5_ins(r0, arm.MemR8Rel(r2, 0))) - self.freereg(ins.location, ins) - elif type(ins) is ir.BinaryOperator: - # Load operands: - r0 = self.getreg(ins.value1) - r1 = self.getreg(ins.value2) - r2 = self.getreg(ins.result) - # do operation: - if ins.operation == '+': - self.emit(arm.addregs_ins(r2, r0, r1)) - elif ins.operation == '<<': - self.emit(arm.movregreg_ins(r2, r0)) - self.emit(arm.lslregs_ins(r2, r1)) - elif ins.operation == '|': - self.emit(arm.movregreg_ins(r2, r0)) - self.emit(arm.orrregs_ins(r2, r1)) - else: - raise NotImplementedError('operation {} not implemented'.format(ins.operation)) - self.freereg(ins.value1, ins) - self.freereg(ins.value2, ins) - elif type(ins) is ir.Call: - # TODO: prep parameters: - self.emit(arm.bl_ins(LabelRef(ins.callee.name))) - elif type(ins) is ir.Return: - self.emit(arm.pop_ins(arm.RegisterSet({arm.r3, arm.r4, arm.r5, arm.r6, arm.r7, arm.pc}))) - elif type(ins) is ir.ConditionalBranch: - r0 = self.getreg(ins.a) - r1 = self.getreg(ins.b) - self.emit(arm.cmp_ins(r1, r0)) - tgt_yes = LabelRef(ins.lab1.name) - if ins.cond == '==': - self.emit(arm.beq_ins(tgt_yes)) - elif ins.cond == '<': - self.emit(arm.blt_ins(tgt_yes)) - elif ins.cond == '>': - self.emit(arm.bgt_ins(tgt_yes)) - else: - raise NotImplementedError('"{}" not covered'.format(ins.cond)) - tgt_no = LabelRef(ins.lab2.name) - self.emit(arm.b_ins(tgt_no)) - self.freereg(ins.a, ins) - self.freereg(ins.b, ins) - elif type(ins) is ir.Alloc: - # Local variables are added to stack - self.addStack(ins.value) - self.localVars.append(ins.value) - # load address into variable: - else: - raise NotImplementedError('IR "{}" not covered'.format(ins)) - -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/flowgraph.py Sun Aug 18 17:43:18 2013 +0200 @@ -0,0 +1,50 @@ + + +import graph + +class FlowGraphNode(graph.Node): + """ A node in the flow graph """ + def __init__(self, g, ins): + super().__init__(g) + self.ins = ins + self.uses = set(ins.src) + self.defs = set(ins.dst) + self.live_in = set() + self.live_out = set() + + def __repr__(self): + return '{}, use={}, def={}'.format(self.ins, self.uses, self.defs) + + +class FlowGraph(graph.Graph): + def __init__(self, instrs): + """ Create a flowgraph from a list of abstract instructions """ + super().__init__() + self._map = {} + # Add nodes: + for ins in instrs: + n = self.newNode(ins) + self._map[ins] = n + + # Make edges: + prev = None + for ins in instrs: + n = self._map[ins] + if prev: + self.addEdge(prev, n) + if ins.jumps: + prev = None + for j in ins.jumps: + to_n = self._map[j] + self.addEdge(n, to_n) + else: + prev = n + + def newNode(self, ins): + """ Override new node to make flow graph node """ + n = FlowGraphNode(self, ins) + self.nodes.append(n) + return n + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/graph.py Sun Aug 18 17:43:18 2013 +0200 @@ -0,0 +1,45 @@ + +class Graph: + """ + Generic graph base class. + Can dump to graphiz dot format for example! + """ + def __init__(self): + self.nodes = [] + self.edges = [] + + def newNode(self): + n = Node(self) + self.nodes.append(n) + return n + + def addEdge(self, n, m): + """ Add an edge from n to m """ + if (n, m) not in self.edges and (m, n) not in self.edges: + self.edges.append((n, m)) + n.succ.append(m) + m.pred.append(n) + + def delEdge(self): + # TODO + pass + + def to_dot(self, f): + """ Generate graphviz dot representation """ + print('digraph G {', file=f) + for node in self.nodes: + print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) + for n, m in self.edges: + print('{} -> {};'.format(id(n), id(m)), file=f) + print('}', file=f) + + +class Node: + """ + Node in a graph. + """ + def __init__(self, g): + self.g = g + self.succ = [] + self.pred = [] +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/instructionselector.py Sun Aug 18 17:43:18 2013 +0200 @@ -0,0 +1,60 @@ + +import ir +import irmach + +def genTemps(): + n = 900 + while True: + yield 't{}'.format(n) + n = n + 1 + +class InstructionSelector: + """ + Base instruction selector. This class must be overridden by + backends. + """ + def newTmp(self): + return self.temps.__next__() + + def getTempReg(self, tmp): + if tmp not in self.tempMap: + self.tempMap[tmp] = self.newTmp() + return self.tempMap[tmp] + + def munchProgram(self, p): + # Entry point for instruction selection + self.temps = genTemps() + assert isinstance(p, ir.Module) + self.result = [] + self.targets = {} + self.tempMap = {} # Mapping from temporaries to infinite register + for f in p.Functions: + # First define labels: + for bb in f.BasicBlocks: + itgt = self.makeIns('{}:'.format(bb.name)) + self.targets[bb] = itgt + for bb in f.BasicBlocks: + self.emit2(self.targets[bb]) + for i in bb.Instructions: + self.munchStm(i) + bb.machIns = self.result + return self.result + + def makeIns(self, *args, **kwargs): + return irmach.AbstractInstruction(*args, **kwargs) + + def emit(self, *args, **kwargs): + """ Abstract instruction emitter """ + i = self.makeIns(*args, **kwargs) + return self.emit2(i) + + def emit2(self, i): + self.result.append(i) + return i + + def munchStm(self, s): + raise NotImplementedError() + + def munchExpr(self, e): + raise NotImplementedError() +
--- a/python/ir/basicblock.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/ir/basicblock.py Sun Aug 18 17:43:18 2013 +0200 @@ -1,5 +1,3 @@ - -# from .instruction import Statement class Block: """ @@ -13,7 +11,6 @@ return 'Block {0}'.format(self.name) def addInstruction(self, i): - #assert isinstance(i, Statement) i.parent = self self.instructions.append(i)
--- a/python/ir/function.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/ir/function.py Sun Aug 18 17:43:18 2013 +0200 @@ -2,8 +2,9 @@ class Function: def __init__(self, name): - self.name = name - self.entry = Block('entry') + self.name = name + self.entry = Block('{}_entry'.format(name)) + self.epiloog = Block('{}_epilog'.format(name)) def __repr__(self): return 'Function {0}'.format(self.name) @@ -26,6 +27,10 @@ if sb not in bbs: bbs.append(sb) worklist.append(sb) + bbs.remove(self.entry) + bbs.remove(self.epiloog) + bbs.insert(0, self.entry) + bbs.append(self.epiloog) return bbs def findBasicBlock(self, name): @@ -38,7 +43,7 @@ @property def Entry(self): - return self.BasicBlocks[0] + return self.entry def check(self): for bb in self.BasicBlocks:
--- a/python/irmach.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/irmach.py Sun Aug 18 17:43:18 2013 +0200 @@ -1,18 +1,7 @@ - -class MachProgram: - pass - - -class MachFunction: - def __init__(self, name): - self.name = name - self.entry = None - - -class MachBlock: - def __init__(self): - self.instructions = [] +""" + Abstract assembly language instructions +""" class AbstractInstruction:
--- a/python/registerallocator.py Wed Aug 14 20:12:40 2013 +0200 +++ b/python/registerallocator.py Sun Aug 18 17:43:18 2013 +0200 @@ -1,33 +1,73 @@ + +import graph + +class InterferenceGraphNode(graph.Node): + def __init__(self, g, varname): + super().__init__(g) + self.varname = varname + + def __repr__(self): + return '{}'.format(self.varname) + + +class InterferenceGraph(graph.Graph): + def __init__(self, flowgraph): + """ Create a new interference graph from a flowgraph """ + super().__init__() + # Mapping from node to live set + self.liveMap = {} + self.tempMap = {} + # Calculate liveness in CFG: + ### + # Liveness: + # in[n] = use[n] UNION (out[n] - def[n]) + # out[n] = for s in n.succ in union in[s] + ### + for n in flowgraph.nodes: + n.live_in = set() + n.live_out = set() + # Dataflow fixed point iteration: + change = True + while change: + change = False + for n in flowgraph.nodes: + _in = n.live_in + _out = n.live_out + n.live_in = n.uses | (n.live_out - n.defs) + if n.succ: + n.live_out = set.union(*(s.live_in for s in n.succ)) + else: + n.live_out = set() + change = change or (_in != n.live_in) or (_out != n.live_out) + # Construct interference graph: + for n in flowgraph.nodes: + for tmp in n.live_out: + n1 = self.getNode(tmp) + for tmp2 in (n.live_out - {tmp}): + n2 = self.getNode(tmp2) + self.addEdge(n1, n2) + + def getNode(self, tmp): + if tmp not in self.tempMap: + self.tempMap[tmp] = self.newNode(tmp) + return self.tempMap[tmp] + + def newNode(self, varname): + n = InterferenceGraphNode(self, varname) + self.nodes.append(n) + return n + class RegisterAllocator: - def live_analyze(self): - # Determine liveness: - for i in self.Instructions: - i.live_in = set() - i.live_out = set() - for z in range(50): - # TODO iterate until converge - for i in self.Instructions: - lo_mk = i.live_out.difference(i.defs) - i.live_in = i.uses.union(lo_mk) - lo = set() - for s in i.succ: - lo = lo.union(s.live_in) - i.live_out = lo - def registerAllocate(self, ir, regs): - allVals = [] - # construct interference: - for i in ir.Instructions: - for v in i.live_in: - allVals.append(v) - for v2 in i.live_in: - if v != v2: - v.interferes.add(v2) - # assign random registers: - regs = set(regs) - for v in allVals: - takenregs = set([iv.reg for iv in v.interferes]) - r2 = list(regs.difference(takenregs)) - # Pick next available: - v.reg = r2[0] + """ Target independent register allocator """ + def registerAllocate(self, ig, regs): + """ Color the given interference graph with the provided registers """ + self.regMap = {} + # TODO: implement ;) + regs = set(regs) + for n in ig.nodes: + print(n) + # TODO: implement spilling + # TODO: implement coalescing +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/tcodegen.py Sun Aug 18 17:43:18 2013 +0200 @@ -0,0 +1,49 @@ + +""" + Test individual parts of the code generation for arm using the c3 frontend. +""" + +import c3 +import ppci +import codegenarm +import outstream + +testsrc = """ +package test2; + +function void tesssst(int henkie) +{ + var int a, b, cee; + a = 2 * 33 - 12; + b = a * 2; + a = b + a; + cee = a; + cee = cee * 2 + cee; + if (cee + a > b and b - a+b== 3*6-b) + { + var int x = a; + x = b - a; + a = x * (x + a); + } + else + { + a = b + (a + b); + } + var int y; + y = a - b * 53; +} +""" + +if __name__ == '__main__': + diag = ppci.DiagnosticsManager() + builder = c3.Builder(diag) + ir = builder.build(testsrc) + ir.dump() + outs = outstream.TextOutputStream() + cga = codegenarm.ArmCodeGenerator(outs) + cfg_file = open('cfg.gv', 'w') + ig_file = open('ig.gv', 'w') + cga.generate(ir, cfg_file=cfg_file, ig_file=ig_file) + cfg_file.close() + ig_file.close() +
--- a/python/trunner.sh Wed Aug 14 20:12:40 2013 +0200 +++ b/python/trunner.sh Sun Aug 18 17:43:18 2013 +0200 @@ -2,9 +2,9 @@ DIR=. while :; do + python -m unittest echo "Awaiting changes in $DIR" inotifywait -r -e modify $DIR - python -m unittest done
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/trunner2.sh Sun Aug 18 17:43:18 2013 +0200 @@ -0,0 +1,15 @@ +#!/usr/bin/bash + +DIR=. +while :; do + python tcodegen.py + + # Create svg from dot file: + dot -Tpdf -o cfg.pdf cfg.gv + dot -Tpdf -o ig.pdf ig.gv + echo "Awaiting changes in $DIR" + inotifywait -r -e modify $DIR +done + + +