Mercurial > lcfOS
changeset 230:88a1e0baef65
Added some tests for IR-code
| author | Windel Bouwman |
|---|---|
| date | Sat, 13 Jul 2013 19:53:44 +0200 |
| parents | 51d5ed1bd503 |
| children | 521567d17388 |
| files | python/c3/astnodes.py python/c3/codegenerator.py python/c3/parser.py python/c3/typecheck.py python/c3/visitor.py python/ir/function.py python/ir/instruction.py python/ir/module.py python/testc3.py python/trunner.sh |
| diffstat | 10 files changed, 320 insertions(+), 94 deletions(-) [+] |
line wrap: on
line diff
--- a/python/c3/astnodes.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/c3/astnodes.py Sat Jul 13 19:53:44 2013 +0200 @@ -65,10 +65,13 @@ def __repr__(self): return '({}*)'.format(self.ptype) + class StructField: def __init__(self, name, typ): self.name = name self.typ = typ + self.offset = 0 + class StructureType(Type): def __init__(self, mems): @@ -76,17 +79,27 @@ for mem in mems: assert type(mem) is StructField assert type(mem.name) is str + def hasField(self, name): for mem in self.mems: if name == mem.name: return True return False + def fieldType(self, name): + return self.findField(name).typ + + def fieldOffset(self, name): + return self.findField(name).offset + + def findField(self, name): for mem in self.mems: if name == mem.name: - return mem.typ - raise Exception() + return mem + raise KeyError(name) + def __repr__(self): + return 'STRUCT' class DefinedType(Type): def __init__(self, name, typ, loc): @@ -94,15 +107,10 @@ self.name = name self.typ = typ self.loc = loc + def __repr__(self): return 'Named type {0} of type {1}'.format(self.name, self.typ) -class TypeCast(Node): - def __init__(self, to_type, x): - self.to_type = to_type - self.a = x - def __repr__(self): - return 'TYPECAST' # Variables, parameters, local variables, constants: class Symbol(Node): @@ -147,69 +155,82 @@ # Operations / Expressions: class Expression(Node): - pass + def __init__(self, loc): + self.loc = loc + class Deref(Expression): def __init__(self, ptr, loc): + super().__init__(loc) assert isinstance(ptr, Expression) self.ptr = ptr - self.loc = loc def __repr__(self): return 'DEREF {}'.format(self.ptr) + +class TypeCast(Expression): + def __init__(self, to_type, x, loc): + super().__init__(loc) + self.to_type = to_type + self.a = x + def __repr__(self): + return 'TYPECAST {}'.format(self.to_type) + + class FieldRef(Expression): def __init__(self, base, field, loc): + super().__init__(loc) assert isinstance(base, Expression) assert isinstance(field, str) self.base = base self.field = field - self.loc = loc def __repr__(self): return 'FIELD {}.{}'.format(self.base, self.field) + class Unop(Expression): def __init__(self, op, a, loc): + super().__init__(loc) assert isinstance(a, Expression) assert isinstance(op, str) self.a = a - self.op = op - self.loc = loc + self.op = op def __repr__(self): return 'UNOP {}'.format(self.op) class Binop(Expression): def __init__(self, a, op, b, loc): + super().__init__(loc) assert isinstance(a, Expression), type(a) assert isinstance(b, Expression) assert isinstance(op, str) self.a = a self.b = b self.op = op # Operation: '+', '-', '*', '/', 'mod' - self.loc = loc def __repr__(self): return 'BINOP {}'.format(self.op) class VariableUse(Expression): def __init__(self, target, loc): + super().__init__(loc) self.target = target - self.loc = loc def __repr__(self): nm = self.target return 'VAR USE {}'.format(nm) class Literal(Expression): def __init__(self, val, loc): + super().__init__(loc) self.val = val - self.loc = loc def __repr__(self): return 'LITERAL {}'.format(self.val) class FunctionCall(Expression): def __init__(self, proc, args, loc): + super().__init__(loc) self.proc = proc self.args = args - self.loc = loc def __repr__(self): return 'CALL {0} '.format(self.proc)
--- a/python/c3/codegenerator.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/c3/codegenerator.py Sat Jul 13 19:53:44 2013 +0200 @@ -2,6 +2,9 @@ from . import astnodes from .scope import boolType, intType from ppci import CompilerError +from .typecheck import resolveType + +tmpnames = {'+':'add', '-':'sub', '*': 'mul', '/':'div', '|':'or', '&':'and'} class CodeGenerator: """ Generates intermediate code from a package """ @@ -23,7 +26,7 @@ self.funcMap[s] = f for s in pkg.innerScope: if type(s) is astnodes.Variable: - v = self.builder.newVariable(s.name) + v = self.builder.newTmp(s.name) #self.builder.addIns(ir.Alloc(v)) self.varMap[s] = v elif type(s) is astnodes.Function: @@ -56,9 +59,7 @@ self.genCode(s) elif type(code) is astnodes.Assignment: re = self.genExprCode(code.rval) - # TODO: Handle pointers loc = self.genExprCode(code.lval) - # determine location of variable self.builder.addIns(ir.Store(loc, re)) elif type(code) is astnodes.ExpressionStatement: self.genExprCode(code.ex) @@ -94,6 +95,7 @@ self.builder.setBB(te) else: print('Unknown stmt:', code) + def genCondCode(self, expr, bbtrue, bbfalse): # Implement sequential logical operators assert expr.typ == boolType @@ -122,13 +124,25 @@ self.builder.addIns(ir.Branch(bbfalse)) else: print('Unknown cond', expr) + + 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 + 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: - tmpnames = {'+':'add', '-':'sub', '*': 'mul', '/':'div', '|':'or', '&':'and'} tmp = self.builder.newTmp(tmpnames[expr.op]) op = expr.op ins = ir.BinaryOperator(tmp, op, ra, rb) @@ -153,11 +167,8 @@ # TODO return tmp elif type(expr) is astnodes.VariableUse: - tmp = self.builder.newTmp() loc = self.varMap[expr.target] - i = ir.Load(loc, tmp) - self.builder.addIns(i) - return tmp + return self.cast_to_rvalue(expr, loc) elif type(expr) is astnodes.Deref: # dereference pointer type: addr = self.genExprCode(expr.ptr) @@ -166,10 +177,16 @@ self.builder.addIns(ins) return tmp elif type(expr) is astnodes.FieldRef: - tmp = self.builder.newTmp('struct_mem' + expr.field) - #ins = ir.BinaryOperator( - # TODO: add offset? - return tmp + b = self.genExprCode(expr.base) + offset = self.builder.newTmp('off_' + expr.field) + bt = resolveType(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) elif type(expr) is astnodes.Literal: tmp = self.builder.newTmp() ins = ir.ImmLoad(tmp, expr.val) @@ -177,13 +194,16 @@ return tmp elif type(expr) is astnodes.TypeCast: ar = self.genExprCode(expr.a) - if isinstance(expr.to_type, astnodes.PointerType): + tt = resolveType(expr.to_type) + if isinstance(tt, astnodes.PointerType): if expr.a.typ is intType: return ar elif isinstance(expr.a.typ, astnodes.PointerType): return ar else: raise Exception() + else: + raise Exception("not implemented") elif type(expr) is astnodes.FunctionCall: tmp = self.builder.newTmp("res") args = []
--- a/python/c3/parser.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/c3/parser.py Sat Jul 13 19:53:44 2013 +0200 @@ -309,17 +309,17 @@ so introduce extra keyword 'cast' """ if self.Peak == 'cast': - self.Consume('cast') + loc = self.Consume('cast').loc self.Consume('<') t = self.parseTypeSpec() self.Consume('>') self.Consume('(') ce = self.CastExpression() self.Consume(')') - return astnodes.TypeCast(t, ce) + return astnodes.TypeCast(t, ce, loc) else: return self.UnaryExpression() - + def UnaryExpression(self): if self.Peak in ['&', '*']: op = self.Consume(self.Peak)
--- a/python/c3/typecheck.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/c3/typecheck.py Sat Jul 13 19:53:44 2013 +0200 @@ -2,16 +2,20 @@ from .scope import * from .visitor import Visitor +def resolveType(t): + if type(t) is DefinedType: + return resolveType(t.typ) + return t + def equalTypes(a, b): - """ + """ Compare types a and b for equality. Not equal until proven otherwise. """ # Recurse into named types: - if type(a) is DefinedType: - return equalTypes(a.typ, b) - if type(b) is DefinedType: - return equalTypes(a, b.typ) + a = resolveType(a) + b = resolveType(b) + # Compare for structural equivalence: if type(a) is type(b): if type(a) is BaseType: @@ -30,19 +34,25 @@ return False def canCast(fromT, toT): + fromT = resolveType(fromT) + toT = resolveType(toT) if isinstance(fromT, PointerType) and isinstance(toT, PointerType): return True elif fromT is intType and isinstance(toT, PointerType): return True return False +def expectRval(s): + # TODO: solve this better + s.expect_rvalue = True + class TypeChecker: def __init__(self, diag): self.diag = diag def error(self, msg, loc): - """ - Wrapper that registers the message and marks the result invalid + """ + Wrapper that registers the message and marks the result invalid """ self.diag.error(msg, loc) self.ok = False @@ -56,14 +66,18 @@ def check2(self, sym): if type(sym) in [IfStatement, WhileStatement]: if not equalTypes(sym.condition.typ, boolType): - self.error('Condition must be of type {0}'.format(boolType), sym.condition.loc) + msg = 'Condition must be of type {}'.format(boolType) + self.error(msg, sym.condition.loc) elif type(sym) is Assignment: - if not equalTypes(sym.lval.typ, sym.rval.typ): - self.error('Cannot assign {0} to {1}'.format(sym.rval.typ, sym.lval.typ), sym.loc) - if not sym.lval.lvalue: - self.error('No valid lvalue {}'.format(sym.lval), sym.lval.loc) + l, r = sym.lval, sym.rval + if not equalTypes(l.typ, r.typ): + msg = 'Cannot assign {} to {}'.format(r.typ, l.typ) + self.error(msg, sym.loc) + if not l.lvalue: + self.error('No valid lvalue {}'.format(l), l.loc) #if sym.rval.lvalue: # self.error('Right hand side must be an rvalue', sym.rval.loc) + expectRval(sym.rval) elif type(sym) is ReturnStatement: pass elif type(sym) is FunctionCall: @@ -75,6 +89,7 @@ self.error('Function {2}: {0} arguments required, {1} given'.format(nreq, ngiv, sym.proc.name), sym.loc) else: for a, at in zip(sym.args, ptypes): + expectRval(a) if not equalTypes(a.typ, at): self.error('Got {0}, expected {1}'.format(a.typ, at), a.loc) # determine return type: @@ -106,9 +121,7 @@ # pointer deref sym.lvalue = True # check if the to be dereferenced variable is a pointer type: - ptype = sym.ptr.typ - if type(ptype) is DefinedType: - ptype = ptype.typ + ptype = resolveType(sym.ptr.typ) if type(ptype) is PointerType: sym.typ = ptype.ptype else: @@ -116,9 +129,8 @@ sym.typ = intType elif type(sym) is FieldRef: basetype = sym.base.typ - sym.lvalue = True - if type(basetype) is DefinedType: - basetype = basetype.typ + sym.lvalue = sym.base.lvalue + basetype = resolveType(basetype) if type(basetype) is StructureType: if basetype.hasField(sym.field): sym.typ = basetype.fieldType(sym.field) @@ -131,6 +143,8 @@ elif type(sym) is Binop: sym.lvalue = False if sym.op in ['+', '-', '*', '/']: + expectRval(sym.a) + expectRval(sym.b) if equalTypes(sym.a.typ, sym.b.typ): if equalTypes(sym.a.typ, intType): sym.typ = sym.a.typ @@ -169,12 +183,13 @@ if canCast(sym.a.typ, sym.to_type): sym.typ = sym.to_type else: - self.error('Cannot cast {} to {}'.format(sym.a.typ, sym.to_type)) + self.error('Cannot cast {} to {}'.format(sym.a.typ, sym.to_type), sym.loc) + sym.typ = intType elif type(sym) is Constant: if not equalTypes(sym.typ, sym.value.typ): self.error('Cannot assign {0} to {1}'.format(sym.value.typ, sym.typ), sym.loc) elif type(sym) in [CompoundStatement, Package, Function, FunctionType, ExpressionStatement, DefinedType]: - pass + pass else: raise Exception('Unknown type check {0}'.format(sym))
--- a/python/c3/visitor.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/c3/visitor.py Sat Jul 13 19:53:44 2013 +0200 @@ -24,8 +24,8 @@ self.do(s) self.do(node.body) elif type(node) is CompoundStatement: - for s in node.statements: - self.do(s) + for s in node.statements: + self.do(s) elif type(node) is IfStatement: self.do(node.condition) self.do(node.truestatement) @@ -53,15 +53,15 @@ elif type(node) is Deref: self.do(node.ptr) elif type(node) is Constant: - self.do(node.value) + self.do(node.value) elif type(node) in [VariableUse, Variable, Literal, FunctionType, DefinedType]: - # Those nodes do not have child nodes. - pass + # Those nodes do not have child nodes. + pass elif type(node) is WhileStatement: - self.do(node.condition) - self.do(node.statement) + self.do(node.condition) + self.do(node.statement) else: - raise Exception('Could not visit "{0}"'.format(node)) + raise Exception('Could not visit "{0}"'.format(node)) # run post function if self.f_post:
--- a/python/ir/function.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/ir/function.py Sat Jul 13 19:53:44 2013 +0200 @@ -1,25 +1,32 @@ from .basicblock import BasicBlock class Function: - def __init__(self, name): + def __init__(self, name): self.name = name self.bbs = [] self.entry = None - def __repr__(self): - return 'Function {0}'.format(self.name) + def __repr__(self): + return 'Function {0}'.format(self.name) - def addBB(self, bb): - self.bbs.append(bb) - bb.parent = self - addBasicBlock = addBB + def addBB(self, bb): + self.bbs.append(bb) + bb.parent = self + addBasicBlock = addBB - def removeBasicBlock(self, bb): - self.bbs.remove(bb) - bb.parent = None + def removeBasicBlock(self, bb): + self.bbs.remove(bb) + bb.parent = None + + def getBBs(self): + return self.bbs - def getBBs(self): - return self.bbs - BasicBlocks = property(getBBs) + def findBasicBlock(self, name): + for bb in self.bbs: + if bb.name == name: + return bb + raise KeyError(name) + + BasicBlocks = property(getBBs)
--- a/python/ir/instruction.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/ir/instruction.py Sat Jul 13 19:53:44 2013 +0200 @@ -3,15 +3,17 @@ class Value: - """ Temporary SSA value (value that is assigned only once! """ - def __init__(self, name): + """ 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 = [] - def __repr__(self): - return '{0}'.format(self.name) # + str(self.IsUsed) - @property - def IsUsed(self): + + def __repr__(self): + return '{0}'.format(self.name) # + str(self.IsUsed) + + @property + def IsUsed(self): return len(self.used_by) > 0 class Variable(Value): @@ -86,9 +88,9 @@ self.addUse(value) def __repr__(self): if self.value: - return 'Return {0}'.format(self.value) + return 'ret {0}'.format(self.value) else: - return 'Return' + return 'ret' def getTargets(self): return [] @@ -114,12 +116,12 @@ # Data operations class BinaryOperator(Instruction): - def __init__(self, result, operation, value1, value2): + def __init__(self, result, operation, value1, value2): super().__init__() #print('operation is in binops:', operation in BinOps) # Check types of the two operands: - assert type(value1) is Value - assert type(value2) is Value + assert type(value1) is Value, str(value1) + str(type(value1)) + assert type(value2) is Value, value2 self.result = result self.addDef(result) self.value1 = value1 @@ -127,8 +129,9 @@ self.addUse(value1) self.addUse(value2) self.operation = operation - def __repr__(self): - return '{0} = {2} {1} {3}'.format(self.result, self.operation, self.value1, self.value2) + def __repr__(self): + a, b = self.value1, self.value2 + return '{} = {} {} {}'.format(self.result, a, self.operation, b) # Memory functions: class Load(Instruction): @@ -141,19 +144,19 @@ self.location = location self.addUse(self.location) def __repr__(self): - return '{} <= [{}]'.format(self.value, self.location) + return '{} = [{}]'.format(self.value, self.location) class Store(Instruction): def __init__(self, location, value): super().__init__() - assert type(value) is Value + 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) def __repr__(self): - return '[{}] <= {}'.format(self.location, self.value) + return '[{}] = {}'.format(self.location, self.value) # Branching: class Branch(Terminator):
--- a/python/ir/module.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/ir/module.py Sat Jul 13 19:53:44 2013 +0200 @@ -41,6 +41,12 @@ return self.funcs Functions = property(getFunctions) + def findFunction(self, name): + for f in self.funcs: + if f.name == name: + return f + raise KeyError(name) + def dump(self): print(self) for v in self.Variables:
--- a/python/testc3.py Sat Jul 13 11:13:01 2013 +0200 +++ b/python/testc3.py Sat Jul 13 19:53:44 2013 +0200 @@ -14,7 +14,7 @@ const int A = 1337; -function void test1() +function void test1() { var int bdd; var int a = 10; @@ -112,6 +112,16 @@ self.assertTrue(ircode) return ircode + def expectIR(self, snippet, ir_out): + ircode = self.builder.build(snippet) + if not ircode: + self.diag.printErrors(snippet) + self.assertTrue(ircode) + actual_ins = [str(i) for i in ircode.Instructions] + expected_ins = [i.strip() for i in ir_out.split('\n')] + self.assertSequenceEqual(expected_ins, actual_ins) + return ircode + def testFunctArgs(self): snippet = """ package testargs; @@ -139,6 +149,39 @@ """ self.expectErrors(snippet, [8, 9, 10]) + def testExpression1(self): + snippet = """ + package testexpr1; + function void t() + { + var int a, b, c; + a = 1; + b = a * 2 + a * a; + c = b * a - 3; + } + """ + block_code = """ a0 = alloc + b1 = alloc + c2 = alloc + t3 = 1 + [a0] = t3 + t4 = [a0] + t5 = 2 + mul6 = t4 * t5 + t7 = [a0] + t8 = [a0] + mul9 = t7 * t8 + add10 = mul6 + mul9 + [b1] = add10 + t11 = [b1] + t12 = [a0] + mul13 = t11 * t12 + t14 = 3 + sub15 = mul13 - t14 + [c2] = sub15 + ret """ + self.expectIR(snippet, block_code) + def testEmpty(self): snippet = """ package A @@ -220,7 +263,53 @@ """ self.expectOK(snippet) - + def testLocalVariable(self): + snippet = """ + package testlocalvar; + function void t() + { + var int a, b; + a = 2; + b = a + 2; + } + """ + block_code = """a0 = alloc + b1 = alloc + t2 = 2 + [a0] = t2 + t3 = [a0] + t4 = 2 + add5 = t3 + t4 + [b1] = add5 + ret """ + self.expectIR(snippet, block_code) + + def testStruct1(self): + snippet = """ + package teststruct1; + function void t() + { + var struct {int x, y;} a; + a.x = 2; + a.y = a.x + 2; + } + """ + block_code = """a0 = alloc + t1 = 2 + off_x2 = 0 + adr_x3 = a0 + off_x2 + [adr_x3] = t1 + off_x4 = 0 + adr_x5 = a0 + off_x4 + t6 = [adr_x5] + t7 = 2 + add8 = t6 + t7 + off_y9 = 0 + adr_y10 = a0 + off_y9 + [adr_y10] = add8 + ret """ + self.expectIR(snippet, block_code) + def testPointerType1(self): snippet = """ package testpointer1; @@ -262,6 +351,71 @@ """ self.expectErrors(snippet, [6, 9, 10]) + def testPointerTypeIr(self): + snippet = """ + package testptr_ir; + function void t() + { + var int* a; + a = cast<int*>(40); + *a = 2; + } + """ + block_code = """a0 = alloc + t1 = 40 + [a0] = t1 + t2 = 2 + deref3 = [a0] + [deref3] = t2 + ret """ + self.expectIR(snippet, block_code) + + def testPointerTypeIr2(self): + snippet = """ + package testptr_ir; + type struct {int x,y;}* gpio; + function void t() + { + var gpio a; + a = cast<gpio>(40); + a->x = 2; + a->y = a->x - 14; + } + """ + block_code = """a0 = alloc + t1 = 40 + [a0] = t1 + t2 = 2 + deref3 = [a0] + off_x4 = 0 + adr_x5 = deref3 + off_x4 + [adr_x5] = t2 + deref6 = [a0] + off_x7 = 0 + adr_x8 = deref6 + off_x7 + t9 = [adr_x8] + t10 = 14 + sub11 = t9 - t10 + deref12 = [a0] + off_y13 = 0 + adr_y14 = deref12 + off_y13 + [adr_y14] = sub11 + ret """ + self.expectIR(snippet, block_code) + + def testWrongCast(self): + snippet = """ + package testptr_ir; + type struct {int x,y;}* gpio; + function void t() + { + var gpio a; + *cast<gpio>(*a); + } + """ + # TODO: remove the duplicate error: + self.expectErrors(snippet, [7, 7]) + def testComplexType(self): snippet = """ package testpointer;