Mercurial > lcfOS
changeset 268:5ec7580976d9
Op naar tree-IR
| author | Windel Bouwman |
|---|---|
| date | Wed, 14 Aug 2013 20:12:40 +0200 |
| parents | e7c8f7eb3f59 |
| children | 5f8c04a8d26b |
| files | python/c3/codegenerator.py python/codegenarm.py python/cortexm3.py python/ir/__init__.py python/ir/basicblock.py python/ir/builder.py python/ir/function.py python/ir/instruction.py python/ir/module.py python/irmach.py python/optimize.py python/stm32f4/burn2.c3 python/testc3.py python/testcg.py python/testir.py |
| diffstat | 15 files changed, 351 insertions(+), 601 deletions(-) [+] |
line wrap: on
line diff
--- a/python/c3/codegenerator.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/c3/codegenerator.py Wed Aug 14 20:12:40 2013 +0200 @@ -5,203 +5,154 @@ from ppci import CompilerError from .typecheck import theType -tmpnames = {'+':'add', '-':'sub', '*': 'mul', '/':'div', '|':'or', \ - '&':'and', '>>':'shl', '<<':'shr'} -class CodeGenerator: +class CodeGenerator(ir.Builder): """ Generates intermediate code from a package """ def __init__(self): self.logger = logging.getLogger('c3cgen') def gencode(self, pkg): + self.prepare() assert type(pkg) is astnodes.Package self.logger.info('Generating ir-code for {}'.format(pkg.name)) self.varMap = {} # Maps variables to storage locations. self.funcMap = {} - self.builder = ir.Builder() - m = ir.Module(pkg.name) - self.builder.setModule(m) + self.m = ir.Module(pkg.name) self.genModule(pkg) - return m + return self.m # inner helpers: def genModule(self, pkg): - # Take care of forward declarations: - for s in pkg.innerScope.Functions: - f = self.builder.newFunction(s.name) + # Take care of forward declarations: + for s in pkg.innerScope.Functions: + f = self.newFunction(s.name) self.funcMap[s] = f - for s in pkg.innerScope: - if type(s) is astnodes.Variable: - v = self.builder.newTmp(s.name) - #self.builder.addIns(ir.Alloc(v)) - self.varMap[s] = v - elif type(s) is astnodes.Function: - # TODO: handle arguments - f = self.funcMap[s] - self.builder.setFunction(f) - bb = self.builder.newBB() - f.entry = bb - self.builder.setBB(bb) - # generate room for locals: + for s in pkg.innerScope: + if type(s) is astnodes.Variable: + #v = self.builder.newTmp(s.name) + self.varMap[s] = self.newTemp() + pass + elif type(s) is astnodes.Function: + self.genFunction(s) + else: + raise NotImplementedError(str(s)) - for sym in s.innerScope: - #print(sym, sym.isParameter) - # TODO: handle parameters different - v = self.builder.newTmp(sym.name) - self.builder.addIns(ir.Alloc(v)) - self.varMap[sym] = v + def genFunction(self, fn): + # TODO: handle arguments + f = self.funcMap[fn] + self.setFunction(f) + # generate room for locals: - self.genCode(s.body) - # TODO handle return? - self.builder.addIns(ir.Return()) - self.builder.setFunction(None) - else: - print(s) + for sym in fn.innerScope: + # TODO: handle parameters different + v = self.newTemp() + # TODO: make this ssa here?? + self.varMap[sym] = v + + self.genCode(fn.body) + # TODO handle return? + self.emit(ir.Return(ir.Const(0))) + self.setFunction(None) def genCode(self, code): assert isinstance(code, astnodes.Statement) - self.builder.setLoc(code.loc) + self.setLoc(code.loc) if type(code) is astnodes.CompoundStatement: for s in code.statements: self.genCode(s) elif type(code) is astnodes.Assignment: - re = self.genExprCode(code.rval) - loc = self.genExprCode(code.lval) - self.builder.addIns(ir.Store(loc, re)) + rval = self.genExprCode(code.rval) + lval = self.genExprCode(code.lval) + self.emit(ir.Move(lval, rval)) elif type(code) is astnodes.ExpressionStatement: self.genExprCode(code.ex) elif type(code) is astnodes.IfStatement: - bbtrue = self.builder.newBB() - bbfalse = self.builder.newBB() - te = self.builder.newBB() - self.genCondCode(code.condition, bbtrue, bbfalse) - self.builder.setBB(bbtrue) - self.genCode(code.truestatement) - self.builder.addIns(ir.Branch(te)) - self.builder.setBB(bbfalse) - if code.falsestatement: - self.genCode(code.falsestatement) - self.builder.addIns(ir.Branch(te)) - self.builder.setBB(te) + bbtrue = self.newBlock() + bbfalse = self.newBlock() + te = self.newBlock() + self.genCondCode(code.condition, bbtrue, bbfalse) + self.setBlock(bbtrue) + self.genCode(code.truestatement) + self.emit(ir.Jump(te)) + self.setBlock(bbfalse) + if code.falsestatement: + self.genCode(code.falsestatement) + self.emit(ir.Jump(te)) + self.setBlock(te) elif type(code) is astnodes.ReturnStatement: if code.expr: re = self.genExprCode(code.expr) - self.builder.addIns(ir.Return(re)) + self.emit(ir.Return(re)) else: self.builder.addIns(ir.Return()) elif type(code) is astnodes.WhileStatement: - bbdo = self.builder.newBB() - bbtest = self.builder.newBB() - te = self.builder.newBB() - self.builder.addIns(ir.Branch(bbtest)) - self.builder.setBB(bbtest) + bbdo = self.newBlock() + bbtest = self.newBlock() + te = self.newBlock() + self.emit(ir.Jump(bbtest)) + self.setBlock(bbtest) self.genCondCode(code.condition, bbdo, te) - self.builder.setBB(bbdo) + self.setBlock(bbdo) self.genCode(code.statement) - self.builder.addIns(ir.Branch(bbtest)) - self.builder.setBB(te) + self.emit(ir.Jump(bbtest)) + self.setBlock(te) else: - print('Unknown stmt:', code) - raise NotImplementedError() + raise NotImplementedError('Unknown stmt {}'.format(code)) def genCondCode(self, expr, bbtrue, bbfalse): # Implement sequential logical operators assert expr.typ == boolType if type(expr) is astnodes.Binop: - if expr.op == 'or': - l2 = self.builder.newBB() + if expr.op == 'or': + l2 = self.newBlock() self.genCondCode(expr.a, bbtrue, l2) - self.builder.setBB(l2) + self.setBlock(l2) self.genCondCode(expr.b, bbtrue, bbfalse) - elif expr.op == 'and': - l2 = self.builder.newBB() + elif expr.op == 'and': + l2 = self.newBlock() self.genCondCode(expr.a, l2, bbfalse) - self.builder.setBB(l2) + self.setBlock(l2) self.genCondCode(expr.b, bbtrue, bbfalse) - elif expr.op in ['==', '>', '<']: + elif expr.op in ['==', '>', '<']: ta = self.genExprCode(expr.a) tb = self.genExprCode(expr.b) - i = ir.ConditionalBranch(ta, expr.op, tb, bbtrue, bbfalse) - self.builder.addIns(i) - else: - raise NotImlementedError('Unknown condition {0}'.format(expr)) + self.emit(ir.CJump(ta, expr.op, tb, bbtrue, bbfalse)) + else: + raise NotImplementedError('Unknown condition {}'.format(expr)) elif type(expr) is astnodes.Literal: if expr.val: - self.builder.addIns(ir.Branch(bbtrue)) + self.emit(ir.Jump(bbtrue)) else: - self.builder.addIns(ir.Branch(bbfalse)) + self.emit(ir.Jump(bbfalse)) else: - print('Unknown cond', expr) - raise NotImplementedError() - - def cast_to_rvalue(self, expr, loc): - """ Cast lvalue to rvalue if required """ - if hasattr(expr, 'expect_rvalue'): - # Load value from memory location: - tmp = self.builder.newTmp() - i = ir.Load(loc, tmp) - self.builder.addIns(i) - return tmp - if expr.lvalue: - return loc + raise NotImplementedError('Unknown cond {}'.format(expr)) def genExprCode(self, expr): assert isinstance(expr, astnodes.Expression) - if type(expr) is astnodes.Binop: - ra = self.genExprCode(expr.a) - rb = self.genExprCode(expr.b) - ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] - if expr.op in ops: - tmp = self.builder.newTmp(tmpnames[expr.op]) - op = expr.op - ins = ir.BinaryOperator(tmp, op, ra, rb) - self.builder.addIns(ins) - return tmp - else: - raise NotImplementedError('Unknown {0}'.format(expr)) - tmp = self.builder.newTmp() - # TODO - return tmp - elif type(expr) is astnodes.Unop: + if type(expr) is astnodes.Binop and expr.op in ir.Binop.ops: ra = self.genExprCode(expr.a) - if expr.op == '&': - # Address of operator - tmp = self.builder.newTmp('addr') - return tmp - #self.builder.addIns(ins) - else: - raise NotImplementedError('Unknown {0}'.format(expr)) - elif type(expr) is astnodes.Constant: - tmp = self.builder.newTmp() - # TODO - return tmp + rb = self.genExprCode(expr.b) + return ir.Binop(ra, expr.op, rb) + elif type(expr) is astnodes.Unop and expr.op == '&': + ra = self.genExprCode(expr.a) + # TODO: Make this work? + return ra elif type(expr) is astnodes.VariableUse: - loc = self.varMap[expr.target] - return self.cast_to_rvalue(expr, loc) + return self.varMap[expr.target] elif type(expr) is astnodes.Deref: # dereference pointer type: addr = self.genExprCode(expr.ptr) - tmp = self.builder.newTmp('deref') - ins = ir.Load(addr, tmp) - self.builder.addIns(ins) - return tmp + return ir.Mem(addr) elif type(expr) is astnodes.FieldRef: b = self.genExprCode(expr.base) - offset = self.builder.newTmp('off_' + expr.field) + #b = b.e bt = theType(expr.base.typ) - ofs = bt.fieldOffset(expr.field) - ins = ir.ImmLoad(offset, ofs) - self.builder.addIns(ins) - tmp2 = self.builder.newTmp('adr_' + expr.field) - ins = ir.BinaryOperator(tmp2, '+', b, offset) - self.builder.addIns(ins) - return self.cast_to_rvalue(expr, tmp2) + offset = ir.Const(bt.fieldOffset(expr.field)) + return ir.Mem(ir.Binop(b, '+', offset)) elif type(expr) is astnodes.Literal: - tmp = self.builder.newTmp('const') - ins = ir.ImmLoad(tmp, expr.val) - self.builder.addIns(ins) - return tmp + return ir.Const(expr.val) elif type(expr) is astnodes.TypeCast: + # TODO: improve this mess: ar = self.genExprCode(expr.a) tt = theType(expr.to_type) if isinstance(tt, astnodes.PointerType): @@ -214,15 +165,9 @@ else: raise NotImplementedError("not implemented") elif type(expr) is astnodes.FunctionCall: - tmp = self.builder.newTmp("res") - args = [] - for arg in expr.args: - ar = self.genExprCode(arg) - args.append(ar) + args = [self.genExprCode(e) for e in expr.args] fn = self.funcMap[expr.proc] - ins = ir.Call(fn, args, tmp) - self.builder.addIns(ins) - return tmp + return ir.Call(fn, args) else: raise NotImplementedError('Unknown expr {}'.format(expr))
--- a/python/codegenarm.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/codegenarm.py Wed Aug 14 20:12:40 2013 +0200 @@ -7,14 +7,113 @@ class InstructionSelector: - pass + 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 +class ArmInstructionSelector(InstructionSelector): + def munchExpr(self, e): + if isinstance(e, ir.Alloc): + return 0 + elif isinstance(e, ir.Binop) and e.operation == '+': + a = self.munchExpr(e.value1) + b = self.munchExpr(e.value2) + 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('orrrr %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('lsl %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('mylll %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') + return d + elif isinstance(e, ir.Mem): + # Load from memory + loc = self.munchExpr(e.e) + d = self.newTmp() + self.emit('ldr %d0, [%s0]', src=[loc], dst=[d]) + return d + elif isinstance(e, ir.Temp): + return e + else: + raise NotImplementedError('--> {}'.format(e)) + + def munchStm(self, s): + if isinstance(s, ir.Move) and isinstance(s.dst, ir.Mem): + memloc = self.munchExpr(s.dst.e) + val = self.munchExpr(s.src) + 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]) + elif isinstance(s, ir.Return): + self.emit('ret') + elif isinstance(s, ir.Jump): + self.emit('jmp {}'.format(s)) + elif isinstance(s, ir.CJump): + self.munchExpr(s.a) + self.munchExpr(s.b) + self.emit('jmp {}'.format(s)) + else: + raise NotImplementedError('--> {}'.format(s)) + + class ArmCodeGenerator: + def __init__(self, outs): + 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) + + +class ArmCodeGenerator_old: """ Simple code generator Ad hoc implementation
--- a/python/cortexm3.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/cortexm3.py Wed Aug 14 20:12:40 2013 +0200 @@ -327,7 +327,6 @@ mnemonic = 'mov' opcode = 4 # 00100 Rd(3) imm8 operands = (RegOp, Imm8) - irpattern = ir.ImmLoad def __init__(self, rd, imm): self.imm = imm.imm self.r = rd.num
--- a/python/ir/__init__.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/__init__.py Wed Aug 14 20:12:40 2013 +0200 @@ -2,5 +2,5 @@ from .instruction import * from .function import Function from .builder import Builder -from .basicblock import BasicBlock +from .basicblock import Block
--- a/python/ir/basicblock.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/basicblock.py Wed Aug 14 20:12:40 2013 +0200 @@ -1,14 +1,19 @@ -class BasicBlock: - """ Uninterrupted sequence of instructions. """ +# from .instruction import Statement + +class Block: + """ + Uninterrupted sequence of instructions with a label at the start. + """ def __init__(self, name): self.name = name self.instructions = [] def __repr__(self): - return 'BasicBlock {0}'.format(self.name) + return 'Block {0}'.format(self.name) def addInstruction(self, i): + #assert isinstance(i, Statement) i.parent = self self.instructions.append(i) @@ -42,8 +47,7 @@ def getSuccessors(self): if not self.Empty: - i = self.LastInstruction - return i.Targets + return self.LastInstruction.Targets return [] Successors = property(getSuccessors) @@ -59,6 +63,5 @@ raise NotImplementedError() def check(self): - for ins in self.Instructions: - ins.check() + pass
--- a/python/ir/builder.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/builder.py Wed Aug 14 20:12:40 2013 +0200 @@ -1,71 +1,56 @@ -from . import Value, BasicBlock, Function, Variable +from . import Block, Function, Statement, Temp -class NameGenerator: - def __init__(self, prefix): +class NamedClassGenerator: + def __init__(self, prefix, cls): self.prefix = prefix + self.cls = cls def NumGen(): a = 0 while True: yield a a = a + 1 self.nums = NumGen() + def gen(self, prefix=None): if not prefix: prefix = self.prefix - return '{0}{1}'.format(prefix, self.nums.__next__()) + return self.cls('{0}{1}'.format(prefix, self.nums.__next__())) -class ValueGenerator(NameGenerator): - def __init__(self): - super().__init__('t') - def gen(self, prefix=None): - v = Value(super().gen(prefix)) - return v - -class BBGenerator(NameGenerator): - def __init__(self): - super().__init__('lab') - def gen(self): - v = BasicBlock(super().gen()) - return v class Builder: + """ Base class for ir code generators """ def __init__(self): - self.newTmp = ValueGenerator().gen - self.newBBint = BBGenerator().gen - self.bb = None - self.m = None - self.fn = None - self.loc = None + self.prepare() + + def prepare(self): + self.newTemp = NamedClassGenerator('reg', Temp).gen + self.newBlock = NamedClassGenerator('block', Block).gen + self.bb = None + self.m = None + self.fn = None + self.loc = None # Helpers: - def newBB(self): - bb = self.newBBint() - self.fn.addBB(bb) - return bb - def setModule(self, m): - self.m = m + self.m = m def newFunction(self, name): f = Function(name) self.m.addFunc(f) return f - def newVariable(self, name): - v = Variable(name) - self.m.addVariable(v) - return v + def setFunction(self, f): + self.fn = f + self.bb = f.entry if f else None - def setFunction(self, f): - self.fn = f - - def setBB(self, bb): - self.bb = bb + def setBlock(self, b): + self.bb = b def setLoc(self, l): self.loc = l - def addIns(self, i): + def emit(self, i): + assert isinstance(i, Statement) i.debugLoc = self.loc if not self.bb: raise Exception('No basic block')
--- a/python/ir/function.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/function.py Wed Aug 14 20:12:40 2013 +0200 @@ -1,10 +1,9 @@ -from .basicblock import BasicBlock +from .basicblock import Block class Function: def __init__(self, name): self.name = name - self.bbs = [] - self.entry = None + self.entry = Block('entry') def __repr__(self): return 'Function {0}'.format(self.name) @@ -19,7 +18,15 @@ bb.parent = None def getBBs(self): - return self.bbs + bbs = [self.entry] + worklist = [self.entry] + while worklist: + b = worklist.pop() + for sb in b.Successors: + if sb not in bbs: + bbs.append(sb) + worklist.append(sb) + return bbs def findBasicBlock(self, name): for bb in self.bbs:
--- a/python/ir/instruction.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/instruction.py Wed Aug 14 20:12:40 2013 +0200 @@ -1,325 +1,129 @@ -from .basicblock import BasicBlock from .function import Function - -class Value: - """ Temporary SSA value (value that is assigned only once! """ - def __init__(self, name): - # TODO: add typing? for now only handle integers - self.name = name - self.used_by = [] - self.Setter = None - - def __repr__(self): - return '{0}'.format(self.name) # + str(self.IsUsed) - - @property - def UsedInBlocks(self): - bbs = [i.parent for i in self.used_by + [self.Setter]] - assert all(isinstance(bb, BasicBlock) for bb in bbs) - return set(bbs) - - @property - def IsUsed(self): - return len(self.used_by) > 0 - - Used = IsUsed - - def onlyUsedInBlock(self, bb): - return all(use.Block is bb for use in self.used_by) - - def lastUse(self, ins): - assert ins in self.used_by - return all(not ins.precedes(ub) for ub in self.used_by) - - def replaceby(self, v2): - for use_ins in self.used_by: - use_ins.replaceValue(self, v2.value) - assert not self.Used - - -class Variable(Value): +class Expression: pass -class Use: - def __init__(self, user, val): - self.user = user - assert isinstance(val, Value) - self.val = val - self.val.used_by.append(self.user) - - def delete(self): - self.val.used_by.remove(self.user) - - -class Instruction: - """ Base class for all instructions. """ - def __init__(self): - # live variables at this node: - self.live_in = set() - self.live_out = set() - # What variables this instruction uses and defines: - self.defs = [] - self.uses = [] - - def delete(self): - while self.uses: - use = self.uses.pop() - use.delete() - while self.defs: - d = self.defs.pop() - d.Setter = None - - def addUse(self, val): - self.uses.append(Use(self, val)) - - def removeUse(self, val): - for u in self.uses: - if u.val is val: - theUse = u - theUse.delete() - self.uses.remove(theUse) - - def addDef(self, v): - self.defs.append(v) - assert v.Setter == None - v.Setter = self +class Const(Expression): + def __init__(self, value): + self.value = value - def removeDef(self, v): - assert v.Setter is self - v.Setter = None - self.defs.remove(v) - - def getParent(self): - return self.parent - - def setParent(self, p): - self.parent = p - Parent = property(getParent, setParent) - - def replaceValue(self, old, new): - # TODO: make this a generic function - raise NotImplementedError('{}'.format(type(self))) - - @property - def Position(self): - return self.Block.Instructions.index(self) - - def precedes(self, other): - assert isinstance(other, Instruction) - if self.Block is other.Block: - return other.Position > self.Position - else: - return self.Block.precedes(other.Block) - - def follows(self, other): - pass - - @property - def Function(self): - return self.Block.parent - - @property - def Block(self): - return self.Parent - - def check(self): - # Check that the variables defined by this instruction - # are only used in the same block - for v in self.defs: - assert v.Setter is self - for ub in v.used_by: - assert ub.Function == self.Function - - # Check that variables used are defined earlier: - for u in self.uses: - v = u.val - #assert self.Position > v.Setter.Position - + def __repr__(self): + return 'Constant {}'.format(self.value) # Function calling: -class Call(Instruction): - def __init__(self, callee, arguments, result=None): - super().__init__() - self.callee = callee - assert type(callee) is Function - self.arguments = arguments - for arg in arguments: - assert type(arg) is Value - self.addUse(arg) - self.result = result - if result: - assert type(result) is Value - self.addDef(result) - - def __repr__(self): - if self.result: - pfx = '{0} = '.format(self.result) - else: - pfx = '' - args = ','.join([str(arg) for arg in self.arguments]) - return pfx + '{0}({1})'.format(self.callee.name, args) - - -class Alloc(Instruction): - """ Allocates space on the stack """ - def __init__(self, value): - super().__init__() - assert isinstance(value, Value) - self.value = value - self.addDef(value) +class Call(Expression): + def __init__(self, f, arguments): + self.f = f + assert type(f) is Function + self.arguments = arguments def __repr__(self): - return '{0} = alloc'.format(self.value) - - -class ImmLoad(Instruction): - def __init__(self, target, value): - super().__init__() - assert type(target) is Value - self.target = target - self.value = value - self.addDef(target) - - def __repr__(self): - return '{} = {}'.format(self.target, self.value) + args = ','.join([str(arg) for arg in self.arguments]) + return '{}({})'.format(self.f.name, args) # Data operations -class BinaryOperator(Instruction): - def __init__(self, result, operation, value1, value2): - super().__init__() - assert type(value1) is Value, str(value1) + str(type(value1)) - assert type(value2) is Value, value2 - self.result = result - self.addDef(result) +class Binop(Expression): + ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] + def __init__(self, value1, operation, value2): + assert operation in Binop.ops self.value1 = value1 self.value2 = value2 - self.addUse(value1) - self.addUse(value2) self.operation = operation def __repr__(self): a, b = self.value1, self.value2 - return '{} = {} {} {}'.format(self.result, a, self.operation, b) + return '({} {} {})'.format(a, self.operation, b) + + +def Add(a, b): + return Binop(a, '+', b) + + +class Alloc(Expression): + """ Allocates space on the stack """ + def __init__(self): + super().__init__() - def replaceValue(self, old, new): - if old is self.value1: - self.value1 = new - elif old is self.value2: - self.value2 = new - elif old is self.result: - self.result = new - else: - raise Exception() - self.removeUse(old) - self.addUse(new) + def __repr__(self): + return 'Alloc' + + +class Temp(Expression): + """ Temporary storage, same as register """ + def __init__(self, name): + self.name = name + + def __repr__(self): + return 'T_{}_'.format(self.name) -# Memory functions: -class Load(Instruction): - def __init__(self, location, value): - super().__init__() - assert type(value) is Value - assert isinstance(location, Value), "Location must be a value" - self.value = value - self.addDef(value) - self.location = location - self.addUse(self.location) +class Mem(Expression): + def __init__(self, e): + self.e = e def __repr__(self): - return '{} = [{}]'.format(self.value, self.location) + return '[{}]'.format(self.e) + + +class Statement: + """ Base class for all instructions. """ + pass -class Store(Instruction): - def __init__(self, location, value): - super().__init__() - assert type(value) is Value, value - assert isinstance(location, Value), "Location must be a value" - self.location = location - self.value = value - self.addUse(value) - self.addUse(location) +class Move(Statement): + def __init__(self, dst, src): + self.dst = dst + self.src = src def __repr__(self): - return '[{}] = {}'.format(self.location, self.value) + return '{} = {}'.format(self.dst, self.src) + + +class Exp(Statement): + def __init__(self, e): + self.e = e + - def replaceValue(self, old, new): - if old is self.value: - self.value = new - elif old is self.location: - self.location = new - else: - raise Exception() - self.removeUse(old) - self.addUse(new) +class Label(Statement): + def __init__(self, name): + self.name = name + self.statements = [] + + def __repr__(self): + return 'LABEL {}:'.format(self.name) # Branching: -class Terminator(Instruction): - @property - def Targets(self): - return self.getTargets() - - def changeTarget(self, tfrom, tto): - pass - - -class Branch(Terminator): +class Jump(Statement): def __init__(self, target): - super().__init__() - assert type(target) is BasicBlock self.target = target + self.Targets = [target] def __repr__(self): - return 'BRANCH {0}'.format(self.target) - - def getTargets(self): - return [self.target] - - def changeTarget(self, tfrom, tto): - assert tfrom is self.target - self.target = tto + return 'BRANCH {}'.format(self.target.name) -class ConditionalBranch(Terminator): - def __init__(self, a, cond, b, lab1, lab2): - super().__init__() - self.a = a - assert type(a) is Value - self.cond = cond - assert cond in ['==', '<', '>'] - self.b = b - self.addUse(a) - self.addUse(b) - assert type(b) is Value - assert type(lab1) is BasicBlock - self.lab1 = lab1 - assert type(lab2) is BasicBlock - self.lab2 = lab2 +class CJump(Statement): + def __init__(self, a, cond, b, lab_yes, lab_no): + assert cond in ['==', '<', '>', '>=', '<=', '!='] + 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] def __repr__(self): - return 'IF {0} {1} {2} THEN {3} ELSE {4}'.format(self.a, self.cond, self.b, self.lab1, self.lab2) - - def getTargets(self): - return [self.lab1, self.lab2] - - def changeTarget(self, tfrom, tto): - assert tfrom is self.lab1 or tfrom is self.lab2 - if tfrom is self.lab1: - self.lab1 = tto - elif tfrom is self.lab2: - self.lab2 = tto + return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) -class Return(Terminator): - def __init__(self, value=None): - super().__init__() +class Return(Statement): + def __init__(self, value): self.value = value - if value: - self.addUse(value) + self.Targets = [] # TODO: Do this in another way def __repr__(self): if self.value: @@ -327,15 +131,4 @@ else: return 'ret' - def getTargets(self): - return [] - -class PhiNode(Instruction): - def __init__(self): - super().__init__() - self.incBB = [] - - def addIncoming(self, bb): - self.incBB.append(bb) -
--- a/python/ir/module.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/ir/module.py Wed Aug 14 20:12:40 2013 +0200 @@ -1,6 +1,6 @@ # IR-Structures: from .instruction import * -from .basicblock import BasicBlock +from .basicblock import Block class Module: """ Main container for a piece of code. """ @@ -81,10 +81,7 @@ def check(self): """ Perform sanity check on module """ for i in self.Instructions: - for t in i.defs: - assert type(t) is Value, "def must be Value, not {0}".format(type(t)) - for t in i.uses: - assert type(t) is Use, "use must be Value, not {0}".format(type(t)) + pass for f in self.Functions: f.check()
--- a/python/irmach.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/irmach.py Wed Aug 14 20:12:40 2013 +0200 @@ -15,9 +15,15 @@ self.instructions = [] -class MachIns: +class AbstractInstruction: """ Absract machine instruction """ - def __init__(self, mi): - self.mi = mi + def __init__(self, assem, src=(), dst=(), jumps=()): + self.assem = assem + self.src = tuple(src) + self.dst = tuple(dst) + self.jumps = tuple(jumps) + + def __repr__(self): + return self.assem + str(self.src) + str(self.dst)
--- a/python/optimize.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/optimize.py Wed Aug 14 20:12:40 2013 +0200 @@ -3,6 +3,7 @@ from transform import DeadCodeDeleter, ConstantFolder def optimize(ir): + return cf = ConstantFolder() dcd = DeadCodeDeleter() m2r = Mem2RegPromotor()
--- a/python/stm32f4/burn2.c3 Mon Aug 12 20:14:47 2013 +0200 +++ b/python/stm32f4/burn2.c3 Wed Aug 14 20:12:40 2013 +0200 @@ -24,7 +24,7 @@ var int pin; pin = 15; // PD13 == output (01) - GPIOD->MODER = (1 << (pin << 1)); + GPIOD->MODER = (1 << (pin * 2)); GPIOD->ODR = (1 << pin); }
--- a/python/testc3.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/testc3.py Wed Aug 14 20:12:40 2013 +0200 @@ -126,11 +126,11 @@ p1 = """package p1; type int A; """ + self.assertTrue(self.builder.build(p1)) p2 = """package p2; import p1; var A b; """ - self.assertTrue(self.builder.build(p1)) self.expectOK(p2) def testFunctArgs(self): @@ -171,27 +171,7 @@ c = b * a - 3; } """ - block_code = """ a0 = alloc - b1 = alloc - c2 = alloc - const3 = 1 - [a0] = const3 - t4 = [a0] - const5 = 2 - mul6 = t4 * const5 - t7 = [a0] - t8 = [a0] - mul9 = t7 * t8 - add10 = mul6 + mul9 - [b1] = add10 - t11 = [b1] - t12 = [a0] - mul13 = t11 * t12 - const14 = 3 - sub15 = mul13 - const14 - [c2] = sub15 - ret """ - self.expectIR(snippet, block_code) + self.expectOK(snippet) def testEmpty(self): snippet = """ @@ -284,16 +264,7 @@ b = a + 2; } """ - block_code = """a0 = alloc - b1 = alloc - const2 = 2 - [a0] = const2 - t3 = [a0] - const4 = 2 - add5 = t3 + const4 - [b1] = add5 - ret """ - self.expectIR(snippet, block_code) + self.expectOK(snippet) def testUnknownType(self): snippet = """package testlocalvar; @@ -314,21 +285,7 @@ a.y = a.x + 2; } """ - block_code = """a0 = alloc - const1 = 2 - off_x2 = 0 - adr_x3 = a0 + off_x2 - [adr_x3] = const1 - off_x4 = 0 - adr_x5 = a0 + off_x4 - t6 = [adr_x5] - const7 = 2 - add8 = t6 + const7 - off_y9 = 4 - adr_y10 = a0 + off_y9 - [adr_y10] = add8 - ret """ - self.expectIR(snippet, block_code) + self.expectOK(snippet) def testPointerType1(self): snippet = """ @@ -381,14 +338,7 @@ *a = 2; } """ - block_code = """a0 = alloc - const1 = 40 - [a0] = const1 - const2 = 2 - deref3 = [a0] - [deref3] = const2 - ret """ - self.expectIR(snippet, block_code) + self.expectOK(snippet) def testPointerTypeIr2(self): snippet = """ @@ -402,26 +352,7 @@ a->y = a->x - 14; } """ - block_code = """a0 = alloc - const1 = 40 - [a0] = const1 - const2 = 2 - deref3 = [a0] - off_x4 = 0 - adr_x5 = deref3 + off_x4 - [adr_x5] = const2 - deref6 = [a0] - off_x7 = 0 - adr_x8 = deref6 + off_x7 - t9 = [adr_x8] - const10 = 14 - sub11 = t9 - const10 - deref12 = [a0] - off_y13 = 4 - adr_y14 = deref12 + off_y13 - [adr_y14] = sub11 - ret """ - self.expectIR(snippet, block_code) + self.expectOK(snippet) def testWrongCast(self): snippet = """
--- a/python/testcg.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/testcg.py Wed Aug 14 20:12:40 2013 +0200 @@ -8,9 +8,7 @@ m = ir.Module('tst') f = ir.Function('tst') m.addFunction(f) - bb = ir.BasicBlock('entry') - f.addBasicBlock(bb) - return m, bb + return m, f.entry class testCodeGeneration(unittest.TestCase): @@ -19,8 +17,8 @@ def testFunction(self): m, bb = genTestFunction() - v = ir.Value('tst') - bb.addInstruction(ir.ImmLoad(v, 123)) + bb.addInstruction(ir.Const(123)) + bb.addInstruction(ir.Return(ir.Const(0))) m.check() obj = self.cg.generate(m) self.assertTrue(obj) @@ -31,15 +29,13 @@ s = outstream.OutputStream() cg = codegenarm.ArmCodeGenerator(s) m, bb = genTestFunction() - v = ir.Value('tst') - bb.addInstruction(ir.Alloc(v)) - v2 = ir.Value('tst2') - bb.addInstruction(ir.ImmLoad(v2, 22)) - bb.addInstruction(ir.Store(v, v2)) + bb.addInstruction(ir.Move(ir.Mem(ir.Const(1)), ir.Const(22))) + bb.addInstruction(ir.Return(ir.Const(0))) m.check() cg.generate(m) #s.dump() + if __name__ == '__main__': unittest.main()
--- a/python/testir.py Mon Aug 12 20:14:47 2013 +0200 +++ b/python/testir.py Wed Aug 14 20:12:40 2013 +0200 @@ -14,13 +14,12 @@ def testBuilder(self): f = self.b.newFunction('add') self.b.setFunction(f) - bb = self.b.newBB() - self.b.setBB(bb) - v1 = self.b.newTmp('t') - self.b.addIns(ir.Return(v1)) + bb = self.b.newBlock() + self.b.setBlock(bb) + self.b.emit(ir.Return(ir.Const(0))) self.m.check() # Run interpreter: - r = self.m.getFunction('add').call(1, 2) + # r = self.m.getFunction('add').call(1, 2) #self.assertEqual(3, r) class ConstantFolderTestCase(unittest.TestCase): @@ -33,30 +32,19 @@ def testBuilder(self): f = self.b.newFunction('test') self.b.setFunction(f) - bb = self.b.newBB() - self.b.setBB(bb) - v1 = self.b.newTmp('t') - v2 = self.b.newTmp('t') - v3 = self.b.newTmp('t') - self.b.addIns(ir.ImmLoad(v1, 5)) - self.b.addIns(ir.ImmLoad(v2, 7)) - self.b.addIns(ir.BinaryOperator(v3, '+', v1, v2)) - self.assertEqual(3, len(self.m.Instructions)) + self.b.setBlock(self.b.newBlock()) + v1 = ir.Const(5) + v2 = ir.Const(7) + v3 = ir.Add(v1, v2) self.cf.run(self.m) - self.assertEqual(3, len(self.m.Instructions)) - self.assertIsInstance(self.m.Instructions[-1], ir.ImmLoad) - self.assertEqual(12, self.m.Instructions[-1].value) def testAdd0(self): f = self.b.newFunction('test') self.b.setFunction(f) - bb = self.b.newBB() - self.b.setBB(bb) - v1 = self.b.newTmp('t') - v2 = self.b.newTmp('t') - v3 = self.b.newTmp('t') - self.b.addIns(ir.ImmLoad(v2, 0)) - self.b.addIns(ir.BinaryOperator(v3, '+', v1, v2)) + self.b.setBlock(self.b.newBlock()) + v1 = ir.Const(0) + v2 = ir.Const(0) + v3 = ir.Add(v1, v2) testsrc = """