Mercurial > lcfOS
changeset 280:02385f62f250
Rework from str interface to Instruction interface
| author | Windel Bouwman |
|---|---|
| date | Sat, 02 Nov 2013 10:03:26 +0100 |
| parents | 2ccd57b1d78c |
| children | 4496cae24d7f |
| files | python/c3/codegenerator.py python/c3/examples/burn2.c3 python/c3/parser.py python/canon.py python/codeedit.py python/codegen.py python/codegenarm.py python/cortexm3.py python/instructionselector.py python/interferencegraph.py python/ir.py python/irmach.py python/old/codegenerator.py python/registerallocator.py python/target.py python/testc3.py python/testgraph.py python/testregalloc.py python/transform.py |
| diffstat | 19 files changed, 322 insertions(+), 691 deletions(-) [+] |
line wrap: on
line diff
--- a/python/c3/codegenerator.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/c3/codegenerator.py Sat Nov 02 10:03:26 2013 +0100 @@ -159,7 +159,11 @@ return ra.e elif type(expr) is astnodes.VariableUse: # This returns the dereferenced variable. - return ir.Mem(self.varMap[expr.target]) + if expr.target.isParameter: + # TODO: now parameters are handled different. Not nice? + return self.varMap[expr.target] + else: + return ir.Mem(self.varMap[expr.target]) elif type(expr) is astnodes.Deref: # dereference pointer type: addr = self.genExprCode(expr.ptr)
--- a/python/c3/examples/burn2.c3 Sat Oct 12 09:56:23 2013 +0200 +++ b/python/c3/examples/burn2.c3 Sat Nov 02 10:03:26 2013 +0100 @@ -10,8 +10,24 @@ import stm32f4xx; -function void init() +function int add(int a, int b) +{ + return a + b; +} + + +function void init(int pin) { + if (pin < 12) + { + return; + } + + /*if (pin > 15) + { + return; + }*/ + var RCC_Type RCC; RCC = cast<RCC_Type>(0x40023800); @@ -21,8 +37,6 @@ var GPIO_Type GPIOD; GPIOD = cast<GPIO_Type>(0x40020C00); - var int pin; - pin = 15; // PD13 == output (01) GPIOD->MODER = (1 << (pin << 1)); GPIOD->ODR = (1 << pin); @@ -31,13 +45,14 @@ function void main() { - init(); + // Vary between 12 and 15: + init(13); var int a; a = 0 while (a < 1000) { - a = a + 1; + a = a + 1; } while(true) {}
--- a/python/c3/parser.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/c3/parser.py Sat Nov 02 10:03:26 2013 +0100 @@ -139,31 +139,31 @@ self.Consume(';') def parseConstDef(self): - self.Consume('const') - t = self.parseTypeSpec() - def parseConst(): - name = self.Consume('ID') - self.Consume('=') - val = self.Expression() - c = astnodes.Constant(name.val, t, val) - c.loc = name.loc - parseConst() - while self.hasConsumed(','): - parseConst() - self.Consume(';') + self.Consume('const') + t = self.parseTypeSpec() + def parseConst(): + name = self.Consume('ID') + self.Consume('=') + val = self.Expression() + c = astnodes.Constant(name.val, t, val) + c.loc = name.loc + parseConst() + while self.hasConsumed(','): + parseConst() + self.Consume(';') # Procedures def parseFunctionDef(self): - loc = self.Consume('function').loc - returntype = self.parseTypeSpec() - fname = self.Consume('ID').val - f = astnodes.Function(fname, loc) - self.addDeclaration(f) - savePart = self.currentPart - self.currentPart = f - self.Consume('(') - parameters = [] - if not self.hasConsumed(')'): + loc = self.Consume('function').loc + returntype = self.parseTypeSpec() + fname = self.Consume('ID').val + f = astnodes.Function(fname, loc) + self.addDeclaration(f) + savePart = self.currentPart + self.currentPart = f + self.Consume('(') + parameters = [] + if not self.hasConsumed(')'): def parseParameter(): typ = self.parseTypeSpec() name = self.Consume('ID') @@ -175,10 +175,10 @@ while self.hasConsumed(','): parseParameter() self.Consume(')') - paramtypes = [p.typ for p in parameters] - f.typ = astnodes.FunctionType(paramtypes, returntype) - f.body = self.parseCompoundStatement() - self.currentPart = savePart + paramtypes = [p.typ for p in parameters] + f.typ = astnodes.FunctionType(paramtypes, returntype) + f.body = self.parseCompoundStatement() + self.currentPart = savePart # Statements: @@ -204,7 +204,10 @@ def parseReturnStatement(self): loc = self.Consume('return').loc - expr = self.Expression() + if self.Peak == ';': + expr = astnodes.Literal(0, loc) + else: + expr = self.Expression() self.Consume(';') return astnodes.ReturnStatement(expr, loc)
--- a/python/canon.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/canon.py Sat Nov 02 10:03:26 2013 +0100 @@ -1,4 +1,3 @@ - import ir from itertools import chain @@ -21,6 +20,7 @@ for stmt in block.instructions: rewriteStmt(stmt, frame) linearize(block) + # TODO: schedule here? # Visit all nodes with some function: # TODO: rewrite into visitor.
--- a/python/codeedit.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/codeedit.py Sat Nov 02 10:03:26 2013 +0100 @@ -273,6 +273,12 @@ return self.filename FileName = property(getFileName, setFileName) + def save(self): + if self.FileName: + s = self.Source + with open(self.FileName, 'w') as f: + f.write(s) + if __name__ == '__main__': app = QApplication(sys.argv)
--- a/python/codegen.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/codegen.py Sat Nov 02 10:03:26 2013 +0100 @@ -18,7 +18,7 @@ obj = object() for gvar in ircode.Variables: print(gvar) - print('TODO') + raise Exception() # TODO for f in ircode.Functions: for bb in f.Blocks: for ins in bb.Instructions:
--- a/python/codegenarm.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/codegenarm.py Sat Nov 02 10:03:26 2013 +0100 @@ -1,13 +1,15 @@ import logging import ir -from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo +from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo, Nop +from target import Imm3 import cortexm3 as arm from ppci import CompilerError import registerallocator from instructionselector import InstructionSelector import irmach -from irmach import makeIns +from irmach import AbstractInstruction as makeIns import canon +import transform import asm class ArmFrame(irmach.Frame): @@ -17,7 +19,7 @@ def __init__(self, name): # We use r7 as frame pointer. super().__init__(name) - self.regs = ['r0', 'r1', 'r2', 'r3', 'r4', 'r5', 'r6'] + self.regs = [arm.r0, arm.r1, arm.r2, arm.r3, arm.r4, arm.r5, arm.r6] self.rv = ir.Temp('special_RV') self.p1 = ir.Temp('special_P1') self.p2 = ir.Temp('special_P2') @@ -26,12 +28,12 @@ self.fp = ir.Temp('special_FP') # Pre-colored registers: self.tempMap = {} - self.tempMap[self.rv] = 'r0' - self.tempMap[self.p1] = 'r1' - self.tempMap[self.p2] = 'r2' - self.tempMap[self.p3] = 'r3' - self.tempMap[self.p4] = 'r4' - self.tempMap[self.fp] = 'r7' + self.tempMap[self.rv] = arm.r0 + self.tempMap[self.p1] = arm.r1 + self.tempMap[self.p2] = arm.r2 + self.tempMap[self.p3] = arm.r3 + self.tempMap[self.p4] = arm.r4 + self.tempMap[self.fp] = arm.r7 self.locVars = {} self.parMap = {} # Literal pool: @@ -68,20 +70,20 @@ Add code for the prologue and the epilogue. Add a label, the return instruction and the stack pointer adjustment for the frame. """ - self.instructions.insert(0, makeIns('{}:'.format(self.name))) - self.instructions.insert(1, makeIns('push {lr, r7}')) + self.instructions.insert(0, makeIns(arm.Label(self.name))) + self.instructions.insert(1, makeIns(arm.push_ins(arm.RegisterSet({arm.lr, arm.r7})))) # Reserve stack space for locals: - self.instructions.insert(2, makeIns('sub sp, sp, {}'.format(self.stacksize))) + self.instructions.insert(2, makeIns(arm.subspsp_ins(arm.sp, arm.sp, arm.Imm7(self.stacksize)))) # Setup frame pointer: - self.instructions.insert(3, makeIns('mov r7, sp')) + self.instructions.insert(3, makeIns(arm.movregreg_ext_ins(arm.r7, arm.sp))) # Stack grows downwards - self.instructions.append(makeIns('add sp, sp, {}'.format(self.stacksize))) - self.instructions.append(makeIns('pop {pc,r7}')) + self.instructions.append(makeIns(arm.addspsp_ins(arm.sp, arm.sp, arm.Imm7(self.stacksize)))) + self.instructions.append(makeIns(arm.pop_ins(arm.RegisterSet({arm.pc, arm.r7})))) # Add constant literals: - self.instructions.append(makeIns('align 4')) # Align at 4 bytes + self.instructions.append(makeIns(Alignment(4))) # Align at 4 bytes for ln, v in self.constants: - self.instructions.append(makeIns('{}:'.format(ln))) - self.instructions.append(makeIns('dcd {}'.format(v))) + self.instructions.append(makeIns(arm.Label(ln))) + self.instructions.append(makeIns(arm.dcd_ins(v))) class ArmInstructionSelector(InstructionSelector): @@ -94,39 +96,41 @@ isinstance(e.b, ir.Const) and e.b.value < 8: a = self.munchExpr(e.a) d = self.newTmp() - self.emit('add %d0, %s0, {}'.format(e.b.value), dst=[d], src=[a]) + c = Imm3(e.b.value) + self.emit(arm.addregregimm3_ins, others=[c], dst=[d], src=[a]) return d elif isinstance(e, ir.Binop) and e.operation == '+': a = self.munchExpr(e.a) b = self.munchExpr(e.b) d = self.newTmp() - self.emit('add %d0, %s0, %s1', dst=[d], src=[a, b]) + self.emit(arm.addregs_ins, dst=[d], src=[a, b]) return d elif isinstance(e, ir.Binop) and e.operation == '-' and \ isinstance(e.b, ir.Const) and e.b.value < 8: a = self.munchExpr(e.a) d = self.newTmp() - self.emit('sub %d0, %s0, {}'.format(e.b.value), dst=[d], src=[a]) + c = Imm3(e.b.value) + self.emit(arm.subregregimm3_ins, others=[c], dst=[d], src=[a]) return d elif isinstance(e, ir.Binop) and e.operation == '-': a = self.munchExpr(e.a) b = self.munchExpr(e.b) d = self.newTmp() - self.emit('sub %d0, %s0, %s1', dst=[d], src=[a, b]) + self.emit(arm.subregs_ins, dst=[d], src=[a, b]) return d elif isinstance(e, ir.Binop) and e.operation == '|': a = self.munchExpr(e.a) b = self.munchExpr(e.b) d = self.newTmp() self.move(d, a) - self.emit('orr %s1, %s0', dst=[], src=[b, d]) + self.emit(arm.orrregs_ins, dst=[], src=[b, d]) return d elif isinstance(e, ir.Binop) and e.operation == '<<': a = self.munchExpr(e.a) b = self.munchExpr(e.b) d = self.newTmp() self.move(d, a) - self.emit('lsl %s1, %s0', dst=[], src=[b, d]) # TODO: is d a source variable? + self.emit(arm.lslregs_ins, dst=[], src=[b, d]) # TODO: is d a source variable? return d elif isinstance(e, ir.Binop) and e.operation == '*': a = self.munchExpr(e.a) @@ -134,29 +138,29 @@ d = self.newTmp() self.move(d, a) # this mul instruction has operands swapped: - self.emit('mul %s0, %d0', dst=[d], src=[b, d]) + self.emit(arm.mulregreg_ins, dst=[d], src=[b, d]) return d elif isinstance(e, ir.Const) and e.value < 256: d = self.newTmp() - self.emit('mov %d0, {}'.format(e.value), dst=[d]) + self.emit(arm.mov_imm8_ins, others=[arm.Imm8(e.value)], dst=[d]) return d elif isinstance(e, ir.Const) and e.value < (2**31): d = self.newTmp() - ln = self.frame.addConstant(e.value) - self.emit('ldr %d0, {}'.format(ln), dst=[d]) + ln = LabelRef(self.frame.addConstant(e.value)) + self.emit(arm.ldr_pcrel, others=[ln], dst=[d]) return d elif isinstance(e, ir.Mem) and isinstance(e.e, ir.Binop) and \ e.e.operation == '+' and isinstance(e.e.b, ir.Const): base = self.munchExpr(e.e.a) d = self.newTmp() c = e.e.b.value - self.emit('ldr %d0, [%s0 + {}]'.format(c), src=[base], dst=[d]) + self.emit(arm.loadimm5_ins, others=[c], src=[base], dst=[d]) return d elif isinstance(e, ir.Mem): # Load from memory base = self.munchExpr(e.e) d = self.newTmp() - self.emit('ldr %d0, [%s0]', src=[base], dst=[d]) + self.emit(arm.loadimm5_ins, others=[0], src=[base], dst=[d]) return d elif isinstance(e, ir.Temp): return e @@ -169,7 +173,7 @@ self.munchStm(m) if isinstance(loc, ir.Temp): reguses.append(loc) - self.emit('bl {}'.format(e.f.name), src=reguses, dst=[self.frame.rv]) + self.emit(arm.bl_ins(LabelRef(e.f.name)), src=reguses, dst=[self.frame.rv]) d = self.newTmp() self.move(d, self.frame.rv) return d @@ -185,35 +189,39 @@ a = self.munchExpr(s.dst.e.a) val = self.munchExpr(s.src) c = s.dst.e.b.value - self.emit('str %s1, [%s0 + {}]'.format(c), src=[a, val]) + self.emit(arm.storeimm5_ins, others=[c], src=[a, val]) elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Mem): memloc = self.munchExpr(s.dst.e) val = self.munchExpr(s.src) - self.emit('str %s1, [%s0]', src=[memloc, val]) + self.emit(arm.storeimm5_ins, others=[0], src=[memloc, val]) elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Temp): val = self.munchExpr(s.src) dreg = s.dst - self.emit('mov %d0, %s0', dst=[dreg], src=[val]) + self.move(dreg, val) elif isinstance(s, ir.Exp): # Generate expression code and discard the result. x = self.munchExpr(s.e) - self.emit('nop', src=[x]) + self.emit(Nop(), src=[x]) elif isinstance(s, ir.Jump): tgt = self.targets[s.target] - self.emit('b {}'.format(s.target.name), jumps=[tgt]) + self.emit(arm.b_ins(LabelRef(s.target.name)), jumps=[tgt]) elif isinstance(s, ir.CJump): a = self.munchExpr(s.a) b = self.munchExpr(s.b) - self.emit('cmp %s0, %s1', src=[a, b]) + self.emit(arm.cmp_ins, src=[a, b]) ntgt = self.targets[s.lab_no] ytgt = self.targets[s.lab_yes] - jmp_ins = makeIns('b {}'.format(s.lab_no.name), jumps=[ntgt]) - # Explicitely add fallthrough: - self.emit('beq {}'.format(s.lab_yes.name), jumps=[ytgt, jmp_ins]) + jmp_ins = makeIns(arm.b_ins(LabelRef(s.lab_no.name)), jumps=[ntgt]) + opnames = {'<': arm.blt_ins, '>':arm.bgt_ins, '==':arm.beq_ins} + op = opnames[s.cond](LabelRef(s.lab_yes.name)) + self.emit(op, jumps=[ytgt, jmp_ins]) # Explicitely add fallthrough self.emit2(jmp_ins) else: raise NotImplementedError('Stmt --> {}'.format(s)) + def move(self, dst, src): + self.emit(arm.movregreg_ext_ins, src=[src], dst=[dst]) + # TODO: this class could be target independent: class ArmCodeGenerator: @@ -227,47 +235,45 @@ self.outs.getSection('data').address = 0x20000000 def generateFunc(self, irfunc): + """ Generate code for one function into a frame """ + # Cleanup function: + transform.removeEmptyBlocks(irfunc) + # Create a frame for this function: frame = ArmFrame(irfunc.name) # Canonicalize the intermediate language: canon.make(irfunc, frame) - print('after canonicalize:') - irfunc.dump() self.ins_sel.munchFunction(irfunc, frame) - print('Selected instructions:') - for i in frame.instructions: - print(i) # Do register allocation: self.ra.allocFrame(frame) # TODO: Peep-hole here? + # Can we materialize here?? + # Add label and return and stack adjustment: frame.EntryExitGlue3() + + # Materialize assembly + # Materialize the register allocated instructions into a stream of + # real instructions. + frame.lower_to(self.outs) return frame def generate(self, ircode): + self.outs.selectSection('code') + # assembly glue to make it work: + # TODO: this must be in source code, not in compiler + self.outs.emit(arm.dcd_ins(Imm32(0x20000678))) # initial SP + self.outs.emit(arm.dcd_ins(Imm32(0x08000009))) # reset vector + self.outs.emit(arm.b_ins(LabelRef('main'))) + # Munch program into a bunch of frames. One frame per function. # Each frame has a flat list of abstract instructions. # Generate code for all functions: self.frames = [self.generateFunc(func) for func in ircode.Functions] - # Materialize assembly - # Reparse the register allocated instructions into a stream of - # real instructions. - # TODO: this is ugly via string representations. This could be - # another interface? - assembler = asm.Assembler(target=arm.armtarget, stream=self.outs) - self.outs.selectSection('code') - # assembly glue to make it work: - self.outs.emit(arm.dcd_ins(Imm32(0x20000678))) # initial SP - self.outs.emit(arm.dcd_ins(Imm32(0x08000009))) # reset vector - self.outs.emit(arm.b_ins(LabelRef('main'))) - for frame in self.frames: - for i in frame.instructions: - assembler.assemble_line(str(i)) - # TODO: fixup references, do this in another way? self.outs.backpatch() self.outs.backpatch()
--- a/python/cortexm3.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/cortexm3.py Sat Nov 02 10:03:26 2013 +0100 @@ -1,6 +1,7 @@ import struct import types -from target import Register, Instruction, Target, Imm8, Label, Imm3, LabelRef, Imm32, Imm7 +from target import Register, Instruction, Target, Imm8, Label, Imm3, LabelRef +from target import Imm32, Imm7 from asmnodes import ASymbol, ANumber, AUnop, ABinop from ppci import CompilerError import ir @@ -101,6 +102,7 @@ class MemR8Rel: def __init__(self, basereg, offset): assert type(basereg) is Reg8Op + assert type(offset) is int self.basereg = basereg self.offset = offset @@ -185,11 +187,13 @@ lr = makeReg(ArmRegister, 14, 'lr') pc = makeReg(ArmRegister, 15, 'pc') +# Sanity checks: assert isinstance(sp, ArmRegister) assert isinstance(r3, ArmRegister) assert ArmRegister.Create(ASymbol('r3')) is r3 assert ArmRegister.Create(ASymbol('sp')) is sp + class ArmInstruction(Instruction): pass @@ -205,6 +209,9 @@ elif isinstance(expr, LabelRef): self.expr = 0 self.label = expr + elif isinstance(expr, int): + self.expr = expr + self.label = None else: raise NotImplementedError() @@ -218,6 +225,7 @@ def __repr__(self): return 'DCD 0x{0:X}'.format(self.expr) + @armtarget.instruction class nop_ins(ArmInstruction): mnemonic = 'nop' @@ -252,19 +260,32 @@ h = (self.opcode << 11) | (imm5 << 6) | (Rn << 3) | Rt return u16(h) + def __repr__(self): return '{} {}, {}'.format(self.mnemonic, self.rt, self.memloc) + @armtarget.instruction class storeimm5_ins(LS_imm5_base): mnemonic = 'STR' opcode = 0xC + @classmethod + def fromim(cls, im): + mem = MemR8Rel(im.src[0], im.others[0]) + return cls(im.src[1], mem) + + @armtarget.instruction class loadimm5_ins(LS_imm5_base): mnemonic = 'LDR' opcode = 0xD + @classmethod + def fromim(cls, im): + mem = MemR8Rel(im.src[0], im.others[0]) + return cls(im.dst[0], mem) + class ls_sp_base_imm8(ArmInstruction): operands = (Reg8Op, MemSpRel) def __init__(self, rt, memop): @@ -299,6 +320,10 @@ self.label = label self.offset = 0 + @classmethod + def fromim(cls, im): + return cls(im.dst[0], im.others[0]) + def resolve(self, f): la = f(self.label.name) sa = align(self.address + 2, 4) @@ -335,15 +360,23 @@ @armtarget.instruction -class mov_ins(ArmInstruction): +class mov_imm8_ins(ArmInstruction): """ mov Rd, imm8, move immediate value into register """ mnemonic = 'mov' opcode = 4 # 00100 Rd(3) imm8 operands = (Reg8Op, Imm8) def __init__(self, rd, imm): + if type(imm) is int: + imm = Imm8(imm) + assert type(imm) is Imm8 self.imm = imm.imm + assert type(rd) is Reg8Op, str(type(rd)) self.rd = rd + @classmethod + def fromim(cls, im): + return cls(im.dst[0], im.others[0]) + def encode(self): rd = self.rd.num opcode = self.opcode @@ -365,8 +398,13 @@ def __init__(self, rd, rn, imm3): self.rd = rd self.rn = rn + assert type(imm3) is Imm3 self.imm3 = imm3 + @classmethod + def fromim(cls, im): + return cls(im.dst[0], im.src[0], im.others[0]) + def encode(self): rd = self.rd.num rn = self.rn.num @@ -399,12 +437,18 @@ self.rd = rd self.rn = rn self.rm = rm + + @classmethod + def fromim(cls, im): + return cls(im.dst[0], im.src[0], im.src[1]) + def encode(self): rd = self.rd.num rn = self.rn.num rm = self.rm.num h = (self.opcode << 9) | (rm << 6) | (rn << 3) | rd return u16(h) + def __repr__(self): return '{} {}, {}, {}'.format(self.mnemonic, self.rd, self.rn, self.rm) @@ -424,12 +468,17 @@ @armtarget.instruction class movregreg_ext_ins(ArmInstruction): + """ mov rd, rm """ operands = (ArmRegister, ArmRegister) mnemonic = 'MOV' def __init__(self, rd, rm): self.rd = rd self.rm = rm + @classmethod + def fromim(cls, im): + return cls(im.dst[0], im.src[0]) + def encode(self): Rd = self.rd.num & 0x7 D = (self.rd.num >> 3) & 0x1 @@ -450,6 +499,11 @@ self.rn = rn self.rdm = rdm + @classmethod + def fromim(cls, im): + assert im.src[1] is im.dst[0] + return cls(im.src[0], im.dst[0]) + def encode(self): rn = self.rn.num rdm = self.rdm.num @@ -471,6 +525,10 @@ self.rdn = rdn self.rm = rm + @classmethod + def fromim(cls, im): + return cls(im.src[0], im.src[1]) + def encode(self): rdn = self.rdn.num rm = self.rm.num @@ -483,9 +541,9 @@ @armtarget.instruction class movregreg_ins(regreg_base): + """ mov Rd, Rm (reg8 operands) """ # TODO: match this: pattern = ir.Move(ir.Temp, ir.Temp) - """ mov Rd, Rm """ mnemonic = 'mov' opcode = 0 @@ -548,13 +606,11 @@ la = f(self.target.name) sa = self.address + 4 self.offset = (la - sa) - #if self.offset < 0: - # # TODO: handle negative jump - # self.offset = 0 def __repr__(self): return '{} {}'.format(self.mnemonic, self.target.name) + @armtarget.instruction class b_ins(jumpBase_ins): mnemonic = 'B' @@ -563,6 +619,7 @@ h = (0b11100 << 11) | imm11 # | 1 # 1 to enable thumb mode return u16(h) + @armtarget.instruction class bl_ins(jumpBase_ins): mnemonic = 'BL' @@ -577,6 +634,7 @@ h2 = (0b1101 << 12) | (j1 << 13) | (j2 << 11) | imm11 return u16(h1) + u16(h2) + class cond_base_ins(jumpBase_ins): def encode(self): imm8 = wrap_negative(self.offset >> 1, 8) @@ -603,7 +661,7 @@ @armtarget.instruction -class blt_ins(cond_base_ins): +class bgt_ins(cond_base_ins): mnemonic = 'bgt' cond = 0b1100 @@ -630,14 +688,18 @@ h = (0x5a << 9) | (M << 8) | reg_list return u16(h) + @armtarget.instruction class pop_ins(ArmInstruction): operands = (RegisterSet,) mnemonic = 'pop' + def __init__(self, regs): self.regs = regs + def __repr__(self): return '{0} {{{1}}}'.format(self.mnemonic, self.regs) + def encode(self): reg_list = 0 P = 0 @@ -651,10 +713,12 @@ h = (0x5E << 9) | (P << 8) | reg_list return u16(h) + @armtarget.instruction class yield_ins(ArmInstruction): operands = () mnemonic = 'yield' + def encode(self): return u16(0xbf10)
--- a/python/instructionselector.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/instructionselector.py Sat Nov 02 10:03:26 2013 +0100 @@ -1,6 +1,7 @@ import ir import irmach -from irmach import makeIns +from irmach import AbstractInstruction as makeIns +import target def genTemps(): n = 900 @@ -8,6 +9,7 @@ yield ir.Temp('t{}'.format(n)) n = n + 1 + class InstructionSelector: """ Base instruction selector. This class must be overridden by @@ -27,7 +29,7 @@ self.frame = frame # First define labels: for bb in f.Blocks: - itgt = makeIns('{}:'.format(bb.name)) + itgt = makeIns(target.Label(bb.name)) self.targets[bb] = itgt # Generate code for all blocks: for bb in f.Blocks: @@ -37,7 +39,7 @@ self.munchStm(ir.Move(self.frame.rv, f.return_value)) def move(self, dst, src): - self.emit('mov %d0, %s0', src=[src], dst=[dst]) + raise NotImplementedError('Not target implemented') def emit(self, *args, **kwargs): """ Abstract instruction emitter """
--- a/python/interferencegraph.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/interferencegraph.py Sat Nov 02 10:03:26 2013 +0100 @@ -70,7 +70,6 @@ for n in self.nodes: if tmp in n.temps: return n - print('new one!') n = InterferenceGraphNode(self, tmp) self.addNode(n) return n
--- a/python/ir.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/ir.py Sat Nov 02 10:03:26 2013 +0100 @@ -76,7 +76,9 @@ def __init__(self, name): self.name = name self.entry = Block('{}_entry'.format(name)) + self.entry.function = self self.epiloog = Block('{}_epilog'.format(name)) + self.epiloog.function = self self.epiloog.addInstruction(Terminator()) self.return_value = Temp('{}_retval'.format(name)) self.arguments = [] @@ -86,16 +88,15 @@ args = ','.join(str(a) for a in self.arguments) return 'Function {}({})'.format(self.name, args) - def addBB(self, bb): + def addBlock(self, bb): self.bbs.append(bb) - bb.parent = self - addBlock = addBB + bb.function = self - def removeBasicBlock(self, bb): - self.bbs.remove(bb) - bb.parent = None + def removeBlock(self, bb): + #self.bbs.remove(bb) + bb.function = None - def getBBs(self): + def getBlocks(self): bbs = [self.entry] worklist = [self.entry] while worklist: @@ -117,7 +118,7 @@ return bb raise KeyError(name) - Blocks = property(getBBs) + Blocks = property(getBlocks) @property def Entry(self): @@ -150,8 +151,11 @@ """ def __init__(self, name): self.name = name + self.function = None self.instructions = [] + parent = property(lambda s: s.function) + def __repr__(self): return 'Block {0}'.format(self.name) @@ -172,14 +176,14 @@ i.delete() self.instructions.remove(i) - def getInstructions(self): + @property + def Instructions(self): return self.instructions - Instructions = property(getInstructions) - def getLastIns(self): + @property + def LastInstruction(self): if not self.Empty: return self.instructions[-1] - LastInstruction = property(getLastIns) @property def Empty(self): @@ -197,7 +201,7 @@ def getPredecessors(self): preds = [] - for bb in self.parent.BasicBlocks: + for bb in self.parent.Blocks: if self in bb.Successors: preds.append(bb) return preds @@ -359,35 +363,32 @@ return '{}'.format(self.e) -class Label(Statement): - # TODO: is this duplicate with block? - def __init__(self, name): - self.name = name - self.statements = [] - - def __repr__(self): - return 'LABEL {}:'.format(self.name) - - # Branching: class LastStatement(Statement): - pass + def changeTarget(self, old, new): + idx = self.Targets.index(old) + self.Targets[idx] = new class Terminator(LastStatement): """ Instruction that terminates the terminal block """ - Targets = [] + def __init__(self): + self.Targets = [] + def __repr__(self): return 'Terminator' class Jump(LastStatement): def __init__(self, target): - self.target = target self.Targets = [target] + def setTarget(self, t): + self.Targets[0] = t + target = property(lambda s: s.Targets[0], setTarget) + def __repr__(self): - return 'BRANCH {}'.format(self.target.name) + return 'JUMP {}'.format(self.target.name) class CJump(LastStatement): @@ -397,10 +398,11 @@ self.a = a self.cond = cond self.b = b - self.lab_yes = lab_yes - self.lab_no = lab_no self.Targets = [lab_yes, lab_no] + lab_yes = property(lambda s: s.Targets[0]) + lab_no = property(lambda s: s.Targets[1]) + def __repr__(self): return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) @@ -431,7 +433,7 @@ def prepare(self): self.newTemp = NamedClassGenerator('reg', Temp).gen - self.newBlock = NamedClassGenerator('block', Block).gen + self.newBlock2 = NamedClassGenerator('block', Block).gen self.bb = None self.m = None self.fn = None @@ -442,9 +444,15 @@ self.m = m def newFunction(self, name): - f = Function(name) - self.m.addFunc(f) - return f + f = Function(name) + self.m.addFunc(f) + return f + + def newBlock(self): + assert self.fn + b = self.newBlock2() + b.function = self.fn + return b def setFunction(self, f): self.fn = f
--- a/python/irmach.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/irmach.py Sat Nov 02 10:03:26 2013 +0100 @@ -8,6 +8,8 @@ """ import ir +import target + class Frame: """ @@ -23,22 +25,29 @@ def __repr__(self): return 'Frame {}'.format(self.name) -def makeIns(*args, **kwargs): - return AbstractInstruction(*args, **kwargs) + def lower_to(self, outs): + for im in self.instructions: + if isinstance(im.assem, target.Instruction): + outs.emit(im.assem) + else: + outs.emit(im.assem.fromim(im)) + class AbstractInstruction: """ Abstract machine instruction class. This is a very simple abstraction of machine instructions. """ - def __init__(self, cls, ops=(), src=(), dst=(), jumps=()): + def __init__(self, cls, ops=(), src=(), dst=(), jumps=(), others=(), ismove=False): + assert type(cls) is type or isinstance(cls, target.Instruction) self.assem = cls - self.ops = ops + self.ops = tuple(ops) self.src = tuple(src) self.dst = tuple(dst) self.jumps = tuple(jumps) + self.others = tuple(others) c = lambda s: tuple(map(type, s)) == (ir.Temp, ) - self.ismove = c(src) and c(dst) and cls.lower().startswith('mov') + self.ismove = ismove def __repr__(self): return self.render()
--- a/python/old/codegenerator.py Sat Oct 12 09:56:23 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,487 +0,0 @@ -""" - Code generation for 64 bits intel processors -""" - -from .nodes import * -from .errors import Error -from .builtin import real, integer, boolean, char -from .assembler import * - -class CodeGenerator: - def __init__(self): - self.strings = [] - self.initialize() - def initialize(self): - # Register descriptors: - self.freeregs = 'r8,r9,r10,r11,r12,r13,r14,r15'.split(',') - self.usedregs = [] - # Members to accumulate the result into: - # The result is an image of bytecode and global variable space. - # Global variables a referenced by RIP relative addressing. - self.image = [] - self.rip = 0 # The current instruction pointer location. - # TODO: backpatch list here? - - # Functions to modify the code image - def addCode(self, code): - assert(type(code) is list) - self.image += code - self.rip += len(code) - def fixCode(self, position, code): - self.image[position:position+len(code)] = code - def align(self, b): - while (self.rip % b) != 0: - self.addCode([0]) - - def saveAllRegisters(self): - regs = list(self.usedregs.keys()) - for reg in regs: - code += self.saveRegister(reg) - - def saveRegister(self, reg): - code = [] - if reg in self.usedregs.keys(): - code.append('mov {0}, {1}'.format(self.usedregs[reg], reg)) - del self.usedregs[reg] - self.freeregs.append(reg) - - def getreg(self, node): - """ acquire a working register for a certain node.""" - # Temporary register bypass action: - if len(self.freeregs) > 0: - reg = self.freeregs.pop(0) - self.usedregs.append(reg) - else: - Error('No more free regs') - node.reg = reg - - def freereg(self, node): - reg = node.reg - node.reg = None - self.freeregs.append(reg) - self.usedregs.remove(reg) - - # Helpers to load and retrieve designated objects: - def storeRegInDesignator(self, reg, designator): - assert(type(reg) is str) - assert(type(designator) is Designator) - if len(designator.selectors) > 0: - self.gencode( designator ) # Load the pointer into some register - self.addCode( mov([designator.reg, 0x0], reg) ) - self.freereg( designator ) - else: - if designator.obj.isLocal: - # Relative from rbp register - mem = ['rbp', designator.obj.offset] - self.addCode( mov(mem, reg) ) - else: - # Relative from RIP after move - self.addCode( mov(['RIP', 0x0], reg) ) - self.fixCode(self.rip - 4, imm32(designator.obj.offset - self.rip) ) - - # Code generation functions: - def genexprcode(self, node): - """ - Generate code for expressions! - Recursively evaluates, and ensures a register contains the answer. - register is an integer register or a floating point reg - """ - if isinstance(node, Binop): - """ Handle a binary operation (two arguments) of some kind """ - self.genexprcode(node.a) - self.genexprcode(node.b) - - if node.op == 'mod': - assert(node.typ.isType(integer)) - self.addCode(mov('rax', node.a.reg)) - self.addCode(xorreg64('rdx', 'rdx')) # Extend divided number with zeros - self.addCode(idivreg64(node.b.reg)) # divide rdx:rax with reg - node.reg = node.a.reg - self.freereg(node.b) # give up register that contains b - self.addCode(mov(node.reg, 'rdx')) # move remainder into result - elif node.op == 'div': - assert(node.typ.isType(integer)) - self.addCode(mov('rax', node.a.reg)) - self.addCode(xorreg64('rdx', 'rdx')) # Extend divided number with zeros - self.addCode(idivreg64(node.b.reg)) # divide rdx:rax with reg - node.reg = node.a.reg - self.freereg(node.b) # give up register that contains b - self.addCode(mov(node.reg, 'rax')) # move result into reg - elif node.op == '*': - if node.typ.isType(integer): - self.addCode(imulreg64(node.a.reg, node.b.reg)) - node.reg = node.a.reg - self.freereg(node.b) - else: - Error('{0} for * not implemented'.format(node.typ)) - elif node.op == '+': - if node.typ.isType(integer): - self.addCode(addreg64(node.a.reg, node.b.reg)) - node.reg = node.a.reg - self.freereg(node.b) - else: - Error('{0} for + not implemented'.format(node.typ)) - elif node.op == '-': - if node.typ.isType(integer): - self.addCode(subreg64(node.a.reg, node.b.reg)) - node.reg = node.a.reg - self.freereg(node.b) - else: - Error('{0} for - not implemented'.format(node.typ)) - else: - Error('Unknown Binop {0}'.format(node.op)) - - elif type(node) is Unop: - if node.op == 'INTTOREAL': - self.genexprcode(node.a) - node.reg = node.a.reg - # TODO use 'FILD' instruction - freg = 12 - code.append('Unop inttoreal TODO') - elif node.op == 'ABS': - if isType(node.typ, real): - code = [0xD9, 0xE1] # st(0) = fabs st(0) - Error('ABS error integer') - elif isType(node.typ, integer): - code = [] - Error('ABS error integer') - else: - Error('ABS error') - else: - Error('Unknown Unop {0}'.format(node.op)) - - elif isinstance(node, Designator): - # dereference, array index. Make sure that the result comes into a register - if len(node.selectors) > 0: - self.gencode(node) # Load the pointer into some register - - # Now we can access the object at location '[node.reg]': - if node.typ.isType(integer): - self.addCode( mov(node.reg, [node.reg, 0x0]) ) - else: - Error('Only integer types implemented') - else: - # No selectors, load variable directly - if node.obj.typ.isType(integer): - if type(node.obj) is Constant: - self.genexprcode(node.obj) - node.reg = node.obj.reg - else: - self.getreg(node) - # Get a register to store the integer value - if node.obj.isLocal: - # relative to rbp: - self.addCode( mov(node.reg, ['rbp', node.obj.offset]) ) - else: - self.addCode(mov(node.reg, ['RIP', 0x0])) - self.fixCode(self.rip-4, imm32(node.obj.offset - self.rip)) - else: - Error('Cannot load variable type {0}'.format(node.typ)) - - elif isinstance(node, Relop): - # Create a boolean from operands - # TODO create an alternative for expressions used as conditions. - self.genexprcode(node.a) - self.genexprcode(node.b) - - if node.a.typ.isType(integer): - instructions = {'<': 'L', '>': 'G', '<>': 'NE', '>=': 'GE', '<=': 'LE', '=':'E'} - if not node.relop in instructions.keys(): - Error('Unimplemented relop: '+str(node.relop)) - instr = instructions[node.relop] - - node.reg = node.a.reg - self.addCode( cmpreg64(node.a.reg, node.b.reg) ) - self.addCode( shortjump(0x0, condition=instr) ) # jump over 0 code and jmp - fixloc1 = self.rip - 1 - rip1 = self.rip - self.addCode( xorreg64(node.reg, node.reg) ) - self.addCode( shortjump(0x0) ) # Jump over 1 code - fixloc2 = self.rip - 1 - self.fixCode(fixloc1, imm8(self.rip - rip1)) - rip2 = self.rip - self.addCode( xorreg64(node.reg, node.reg) ) - self.addCode( increg64(node.reg) ) - self.fixCode(fixloc2, imm8(self.rip - rip2)) - - self.freereg(node.b) - else: - Error('Relop not implemented for {0}'.format(node.a.typ)) - - elif type(node) is Constant: - if node.typ.isType(integer): - self.getreg(node) - self.addCode(mov(node.reg, node.value)) - elif node.typ.isType(real): - code += self.getreg(node) - Error('TODO: get real reg') - # TODO: get a fixed point reg, and load the variable in there - else: - Error('Howto generate code for {0}?'.format(node)) - - elif type(node) is ProcedureCall: - if type(node.proc.obj) is BuiltinProcedure: - # Handle builtin procedures different, these not always call - # a function, but generate code. - bi = node.proc.obj - if bi.name == 'chr': - arg = node.args[0] - self.genexprcode(arg) - # Store character in full width register: - # TODO: store in char only register - node.reg = arg.reg - else: - Error('Unknown builtin function {0}'.format(bi.name)) - else: - # Use generic procedure call first - self.gencode(node) - # Retrieve result: - if node.typ.isType(integer): - # Store result! - self.getreg(node) - self.addCode( mov(node.reg, 'rax') ) - else: - Error('Return type not supported {0}'.format(node.typ)) - else: - Error('Cannot generate expression code for: {0}'.format(node)) - - def gencode(self, node): - """ Code generation function for AST nodes """ - if isinstance(node, Module): - # for all imports make a list of pointer to the actual procedures: - for imp in node.imports: - imp.offset = self.rip - self.addCode( [0x0]*8 ) - # global variable storage allocation - variables = node.symtable.getAllLocal(Variable) - for var in variables: - var.isLocal = False - var.offset = self.rip - self.addCode( [0x00] * var.typ.size ) # TODO initial values here? - self.align(8) - # TODO: mark end of data and start of code inside image - # TODO: round data to page size to enable protection by loader. - # Procedure code generation: - procedures = node.symtable.getAllLocal(Procedure) - node.procs = procedures - for proc in procedures: - self.gencode(proc) - # Module init code: - node.initcodeentry = self.rip - self.gencode(node.initcode) - self.addCode( ret() ) - # TODO: how to return from module init code? far return?? - - elif type(node) is Procedure: - # calculate offsets for local variables and parameters - # Variable location relative to 'rbp' register - variables = node.symtable.getAllLocal(Variable) - offset = 0 - paramoffset = 16 - for var in variables: - var.isLocal = True - if not var.isParameter: - offset += var.typ.size - # Offset is negative of rbp in stack frame - var.offset = -offset - node.framesize = offset - # Calculate offsets of parameters relative to rbp register - for par in reversed(node.typ.parameters): - pvar = node.symtable.getLocal(Variable, par.name) - pvar.offset = paramoffset - paramoffset += pvar.typ.size - - # code generation - node.entrypoint = self.rip - self.addCode(push('rbp')) - self.addCode(mov('rbp', 'rsp')) # Setup the base pointer - self.addCode(subreg64('rsp', node.framesize)) # reserve space for locals - self.gencode(node.block) - if node.retexpr: - if node.retexpr.typ.isType(integer): - self.genexprcode(node.retexpr) - self.addCode( mov('rax', node.retexpr.reg) ) - self.freereg(node.retexpr) - else: - Error('Cannot return this kind yet {0}'.format(node.retexpr.typ)) - self.addCode( addreg64('rsp', node.framesize) ) - self.addCode( pop('rbp') ) - self.addCode( ret() ) - assert(len(self.usedregs) == 0) - - elif isinstance(node, StatementSequence): - for s in node.statements: - self.gencode(s) - - elif type(node) is ProcedureCall: - # Prepare parameters on the stack: - stacksize = 0 - assert(len(node.args) == len(node.proc.typ.parameters)) - for arg, param in zip(node.args, node.proc.typ.parameters): - - if param.kind == 'value': - self.genexprcode(arg) - self.addCode( push(arg.reg) ) - self.freereg( arg ) - stacksize += 8 - else: - Error('Parameter kind other than value') - - # Calculate address using designator - if type(node.proc.obj) is Procedure: - self.addCode( call(0x0) ) - self.fixCode( self.rip - 4, imm32(node.proc.obj.entrypoint - self.rip)) - elif type(node.proc.obj) is ImportedSymbol: - # Load the entry point of the import table - self.getreg(node.proc.obj) - # Load the address of the procedure: - self.addCode( mov(node.proc.obj.reg, ['RIP', 0x0]) ) - self.fixCode( self.rip - 4, imm32(node.proc.obj.offset - self.rip) ) - # Call to the address in register: - self.addCode( call(node.proc.obj.reg) ) - # Free register that holds the address of the object - self.freereg( node.proc.obj ) - elif type(node.proc.obj) is BuiltinProcedure: - if node.proc.obj.name == 'chr': - print('int to char') - else: - Error('Unknown builtin function {0}'.format(node.proc.obj.name)) - else: - Error('Cannot call designator of type {0}'.format(node.proc.obj)) - - # Restore stack (pop all arguments of): - self.addCode(addreg64('rsp', stacksize)) - - elif type(node) is Assignment: - if node.lval.typ.isType(integer): - # TODO if node.rval is Constant of some datatype, move it to mem directly - self.genexprcode(node.rval) # Calculate the value that has to be stored. - self.storeRegInDesignator(node.rval.reg, node.lval) - self.freereg(node.rval) - else: - Error('Assignments of other types not implemented') - # TODO if left and right are designators, do some sort of memcpy. - - elif type(node) is IfStatement: - self.genexprcode(node.condition) - self.addCode( cmpreg64(node.condition.reg, 1) ) - self.freereg(node.condition) - if node.falsestatement: - # If with else clause - self.addCode( nearjump(0x0, condition='NE') ) # if Not Equal jump to false - rip1 = self.rip - fixloc1 = self.rip - 4 - self.gencode(node.truestatement) - self.addCode( nearjump( 0x0 ) ) # jump over false code - fixloc2 = self.rip - 4 - self.fixCode(fixloc1, imm32(self.rip - rip1)) - rip2 = self.rip - self.gencode(node.falsestatement) - self.fixCode(fixloc2, imm32(self.rip - rip2)) - else: - # If without else clause - self.addCode( nearjump(0x0, condition='NE') ) # if Not Equal jump to false - rip1 = self.rip - fixloc1 = self.rip - 4 - self.gencode(node.truestatement) - self.fixCode(fixloc1, imm32(self.rip - rip1)) # Fixup near jump over true code. - - elif isinstance(node, WhileStatement): - rip1 = self.rip # Store the start of the while loop - self.genexprcode(node.condition) - self.addCode( cmpreg64(node.condition.reg, 1) ) # Test condition for true-ness - self.freereg(node.condition) - self.addCode( nearjump(0x0, condition='NE') ) # If Not Equal jump over while code AND jump back (fix later) - fixloc1 = self.rip - 4 - rip2 = self.rip - self.gencode(node.dostatements) - self.addCode( nearjump(0x0) ) # JMP to condition, fix exact jump position below - fixloc2 = self.rip - 4 - rip3 = self.rip # end of while loop - self.fixCode(fixloc2, imm32(rip1 - rip3)) # Fixup jump to start of while loop - self.fixCode(fixloc1, imm32(rip3 - rip2)) # Fixup jump out of while loop - - elif type(node) is ForStatement: - # Initial load of iterator variable: - self.genexprcode(node.begin) - self.genexprcode(node.end) - # TODO: link reg with variable so that a register is used instead of a variable - iterreg = node.begin.reg # Get the register used for the loop - #self.addCode(cmpreg64(iterreg, node.endvalue)) - rip1 = self.rip - self.gencode(node.statements) - #self.loadDesignatorInReg(node. - #self.addCode( addreg64(node.variable, node.increment) ) - self.addCode(nearjump(0x0)) - fixloc1 = self.rip - 4 - rip2 = self.rip - self.fixCode(fixloc1, imm32(rip1 - rip2)) - - self.freereg(node.begin) # Release register used in loop - self.freereg(node.end) - Error('No implementation of FOR statement') - - elif type(node) is AsmCode: - def processOperand(op): - if type(op) is list: - if type(op[0]) is Variable: - var = op[0] - if var.isLocal: - return ['rbp', var.offset] - else: - Error('Can only use local variables in inline assembler') - return op - for asmline in node.asmcode: - opcode, operands = asmline - operands = [processOperand(opx) for opx in operands] - print('assembling', opcode, *operands) - func,nargs = opcodes[opcode] - code = func(*operands) - self.addCode(code) - - elif isinstance(node, EmptyStatement): - pass - - - elif type(node) is StringConstant: - self.strings.append(node) - self.data.append(node.value) # Add string to the data section - - elif type(node) is Designator: - if len(node.selectors) > 0: - self.getreg(node) - # Load starting address - if node.obj.isLocal: - self.addCode( leareg64(node.reg, ['rbp', node.obj.offset]) ) - else: - # Global variables need to be relocated... - self.addCode(leareg64(node.reg, ['RIP', 0])) - self.fixCode(self.rip - 4, imm32(node.obj.offset - self.rip)) - # Loop over all designators.. - for selector in node.selectors: - if type(selector) is Index: - # Deref an array index - self.genexprcode(selector.index) - self.getreg(selector) - self.addCode( mov(selector.reg, selector.typ.elementType.size) ) - self.addCode( imulreg64(selector.reg, selector.index.reg ) ) - self.freereg(selector.index) - self.addCode(addreg64(node.reg, selector.reg)) - self.freereg(selector) - elif type(selector) is Field: - print('Field') - Error('Field not implemented') - else: - Error('Unknown selector') - else: - Error('Can only gencode for designator with selectors') - - else: - print('not generating code for {0}'.format(node)) - - def generatecode(self, ast): - """ code generation front end """ - self.initialize() - self.gencode(ast) - ast.image = self.image -
--- a/python/registerallocator.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/registerallocator.py Sat Nov 02 10:03:26 2013 +0100 @@ -44,7 +44,6 @@ """ 1. Construct interference graph from instruction list """ self.f.cfg = FlowGraph(self.f.instructions) self.f.ig = InterferenceGraph(self.f.cfg) - self.printLive() self.Node = self.f.ig.getNode @@ -53,7 +52,6 @@ self.precolored = set(self.Node(tmp) for tmp in pre_tmp) self.workSet = set(self.f.ig.nodes - self.precolored) - # Make degree table: for n in self.precolored: n.addDegree = 100 + len(self.f.ig.nodes) + self.K @@ -61,10 +59,8 @@ self.color = {} for tmp, c in self.f.tempMap.items(): self.color[self.Node(tmp)] = c - dict(self.f.tempMap) # start with pre-colored self.moves = [i for i in self.f.instructions if i.ismove] - print(self.moves) for mv in self.moves: self.Node(mv.src[0]).moves.add(mv) self.Node(mv.dst[0]).moves.add(mv)
--- a/python/target.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/target.py Sat Nov 02 10:03:26 2013 +0100 @@ -57,6 +57,7 @@ class LabelRef: def __init__(self, name): + assert type(name) is str self.name = name @classmethod @@ -71,6 +72,13 @@ pass +class Nop(Instruction): + """ Instruction that does nothing and has zero size """ + def encode(self): + return bytes() + + + class PseudoInstruction(Instruction): pass
--- a/python/testc3.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/testc3.py Sat Nov 02 10:03:26 2013 +0100 @@ -296,7 +296,9 @@ var int* pa, pb; function void t(int a, double b) { - pa = &a; + var int a2; + a2 = a; // parameters cannot be escaped for now.. + pa = &a2; pb = pa; *pa = 22; }
--- a/python/testgraph.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/testgraph.py Sat Nov 02 10:03:26 2013 +0100 @@ -5,11 +5,11 @@ import interferencegraph import flowgraph import ir -import irmach +from irmach import AbstractInstruction as AI +from target import Nop class GraphTestCase(unittest.TestCase): - def testEdge(self): g = graph.Graph() n1 = graph.Node(g) @@ -51,9 +51,9 @@ t5 = ir.Temp('t5') t6 = ir.Temp('t6') instrs = [] - instrs.append(irmach.makeIns('ld %d', dst=[t1])) - instrs.append(irmach.makeIns('ld %d', dst=[t2])) - instrs.append(irmach.makeIns('ld %d', dst=[t3])) + instrs.append(AI(Nop, dst=[t1])) + instrs.append(AI(Nop, dst=[t2])) + instrs.append(AI(Nop, dst=[t3])) cfg = flowgraph.FlowGraph(instrs) ig = interferencegraph.InterferenceGraph(cfg) @@ -63,20 +63,17 @@ t3 = ir.Temp('t3') t4 = ir.Temp('t4') instrs = [] - instrs.append(irmach.makeIns('ld %d0', dst=[t1])) - instrs.append(irmach.makeIns('ld %d0', dst=[t2])) - instrs.append(irmach.makeIns('ld %d0', dst=[t3])) - instrs.append(irmach.makeIns('mov %d0, %s0', dst=[t4], src=[t3])) - instrs.append(irmach.makeIns('st %s0', src=[t4])) - instrs.append(irmach.makeIns('st %s0', src=[t1])) - instrs.append(irmach.makeIns('st %s0', src=[t2])) + instrs.append(AI(Nop, dst=[t1])) + instrs.append(AI(Nop, dst=[t2])) + instrs.append(AI(Nop, dst=[t3])) + instrs.append(AI(Nop, dst=[t4], src=[t3])) + instrs.append(AI(Nop, src=[t4])) + instrs.append(AI(Nop, src=[t1])) + instrs.append(AI(Nop, src=[t2])) cfg = flowgraph.FlowGraph(instrs) ig = interferencegraph.InterferenceGraph(cfg) - ig.to_txt() ig.Combine(ig.getNode(t4), ig.getNode(t3)) self.assertIs(ig.getNode(t4), ig.getNode(t3)) - print('after') - ig.to_txt() if __name__ == '__main__':
--- a/python/testregalloc.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/testregalloc.py Sat Nov 02 10:03:26 2013 +0100 @@ -1,9 +1,10 @@ import unittest import os import sys -import irmach +from irmach import AbstractInstruction as makeIns, Frame import registerallocator import ir +from target import Nop class RegAllocTestCase(unittest.TestCase): @@ -11,7 +12,7 @@ self.ra = registerallocator.RegisterAllocator() def testRegAlloc(self): - f = irmach.Frame('tst') + f = Frame('tst') f.regs = [1,2,3,4,5,6] # for test use numbers! f.tempMap = {} t1 = ir.Temp('t1') @@ -19,12 +20,12 @@ t3 = ir.Temp('t3') t4 = ir.Temp('t4') t5 = ir.Temp('t5') - f.instructions.append(irmach.makeIns('ld %d0', dst=[t1])) - f.instructions.append(irmach.makeIns('ld %d0', dst=[t2])) - f.instructions.append(irmach.makeIns('ld %d0', dst=[t3])) - f.instructions.append(irmach.makeIns('add %d0, %s0, %s1', dst=[t4], src=[t1, t2])) - f.instructions.append(irmach.makeIns('add %d0, %s0, %s1', dst=[t5], src=[t4, t3])) - f.instructions.append(irmach.makeIns('st %s0', src=[t5])) + f.instructions.append(makeIns(Nop, dst=[t1])) + f.instructions.append(makeIns(Nop, dst=[t2])) + f.instructions.append(makeIns(Nop, dst=[t3])) + f.instructions.append(makeIns(Nop, dst=[t4], src=[t1, t2])) + f.instructions.append(makeIns(Nop, dst=[t5], src=[t4, t3])) + f.instructions.append(makeIns(Nop, src=[t5])) self.ra.allocFrame(f) self.conflict(t1, t2) self.conflict(t2, t3) @@ -33,7 +34,7 @@ self.assertNotEqual(self.ra.Node(ta).color, self.ra.Node(tb).color) def testRegCoalesc(self): - f = irmach.Frame('tst') + f = Frame('tst') f.regs = [1,2,3,4,5,6] # for test use numbers! f.tempMap = {} t1 = ir.Temp('t1') @@ -42,18 +43,15 @@ t4 = ir.Temp('t4') t5 = ir.Temp('t5') t6 = ir.Temp('t6') - f.instructions.append(irmach.makeIns('ld %d0', dst=[t1])) - f.instructions.append(irmach.makeIns('ld %d0', dst=[t2])) - f.instructions.append(irmach.makeIns('ld %d0', dst=[t3])) - f.instructions.append(irmach.makeIns('lsl %s0, %s1', dst=[t4], src=[t2, t1])) - f.instructions.append(irmach.makeIns('mov %d0, %s0', dst=[t5], src=[t3])) - f.instructions.append(irmach.makeIns('orr %s0, %s1', dst=[t5], src=[t4, t5])) - f.instructions.append(irmach.makeIns('mov %d0, %s0', dst=[t6], src=[t5])) - f.instructions.append(irmach.makeIns('st %s0', src=[t6])) + f.instructions.append(makeIns(Nop, dst=[t1])) + f.instructions.append(makeIns(Nop, dst=[t2])) + f.instructions.append(makeIns(Nop, dst=[t3])) + f.instructions.append(makeIns(Nop, dst=[t4], src=[t2, t1])) + f.instructions.append(makeIns(Nop, dst=[t5], src=[t3])) + f.instructions.append(makeIns(Nop, dst=[t5], src=[t4, t5])) + f.instructions.append(makeIns(Nop, dst=[t6], src=[t5])) + f.instructions.append(makeIns(Nop, src=[t6])) self.ra.allocFrame(f) - f.ig.to_txt() - for i in f.instructions: - print(i) self.conflict(t1, t2) self.conflict(t2, t3) self.conflict(t1, t3)
--- a/python/transform.py Sat Oct 12 09:56:23 2013 +0200 +++ b/python/transform.py Sat Nov 02 10:03:26 2013 +0100 @@ -46,10 +46,12 @@ """ Override this virtual method """ raise NotImplementedError() + class BasePass(BasicBlockPass): def onBasicBlock(self, bb): pass + # Usefull transforms: class ConstantFolder(BasePass): def __init__(self): @@ -62,10 +64,7 @@ def postExpr(self, expr): if type(i) is BinaryOperator and i.operation in self.ops.keys() and type(i.a) is Const and type(i.b) is Const: - op = i.operation - va = i.a.value - vb = i.b.value - vr = self.ops[i.operation](va, vb) + vr = self.ops[i.operation](i.a.value, i.b.value) return Const(vr) else: return expr @@ -123,22 +122,24 @@ class CleanPass(FunctionPass): def onFunction(self, f): - bbs = list(f.BasicBlocks) - for bb in bbs: - # If a block only contains a branch, it can be removed: - if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch: - # This block is empty. - # find predecessors of this block and replace this block reference with the jumped reference. - ins = bb.LastInstruction - preds = bb.Predecessors - if bb in preds: - # Do not remove if preceeded by itself - pass - else: - for pred in bb.Predecessors: - pred.LastInstruction.changeTarget(bb, ins.target) - f.removeBasicBlock(bb) + removeEmptyBasicBlocks(f) + + +def removeEmptyBlocks(f): + """ Remove empty basic blocks from function. """ + # If a block only contains a branch, it can be removed: + empty = lambda b: type(b.FirstInstruction) is ir.Jump + empty_blocks = list(filter(empty, f.Blocks)) + for b in empty_blocks: + # Update predecessors + preds = b.Predecessors + if b not in preds + [f.entry]: + # Do not remove if preceeded by itself + tgt = b.LastInstruction.target + for pred in preds: + pred.LastInstruction.changeTarget(b, tgt) + logging.debug('Removing empty block: {}'.format(b)) + f.removeBlock(b) -