# HG changeset patch # User Windel Bouwman # Date 1366392172 -7200 # Node ID 3eb06f5fb9873ceb2a5504b5161629b6d9b85c92 # Parent c1d2b6b9f9a7aafafaab9a3e64e7357aafb070b5 Added memory alloc for locals diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/c3/codegenerator.py --- a/python/c3/codegenerator.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/c3/codegenerator.py Fri Apr 19 19:22:52 2013 +0200 @@ -6,6 +6,7 @@ """ Generates intermediate code from a package """ def gencode(self, pkg): assert type(pkg) is astnodes.Package + self.varMap = {} # Maps variables to storage locations. self.builder = ir.Builder() m = ir.Module(pkg.name) self.builder.setModule(m) @@ -25,6 +26,13 @@ bb = self.builder.newBB() f.entry = bb self.builder.setBB(bb) + # generate room for locals: + + for sym in s.scope: + v = self.builder.newTmp(sym.name) + self.builder.addIns(ir.Alloc(v)) + self.varMap[sym] = v + self.genCode(s.body) # TODO handle return? self.builder.addIns(ir.Return()) @@ -38,7 +46,9 @@ self.genCode(s) elif type(code) is astnodes.Assignment: re = self.genExprCode(code.rval) - self.builder.addIns(ir.Store(code.lval, re)) + print(code.lval) + loc = self.varMap[code.lval.target] + self.builder.addIns(ir.Store(loc, re)) elif type(code) is astnodes.IfStatement: bbtrue = self.builder.newBB() bbfalse = self.builder.newBB() @@ -56,7 +66,11 @@ elif type(code) is astnodes.EmptyStatement: pass elif type(code) is astnodes.ReturnStatement: - pass + if code.expr: + re = self.genExprCode(code.expr) + self.builder.addIns(ir.Return(re)) + else: + self.builder.addIns(ir.Return()) else: print('Unknown stmt:', code) def genCondCode(self, expr, bbtrue, bbfalse): @@ -79,8 +93,7 @@ i = ir.ConditionalBranch(ta, expr.op, tb, bbtrue, bbfalse) self.builder.addIns(i) else: - raise NotImlementedError() - print('Unknown cond', expr) + raise NotImlementedError('Unknown condition {0}'.format(expr)) elif type(expr) is astnodes.Literal: if expr.val: self.builder.addIns(ir.BranchInstruction(bbtrue)) @@ -109,7 +122,8 @@ return tmp elif type(expr) is astnodes.VariableUse: tmp = self.builder.newTmp() - i = ir.Load(expr, tmp) + loc = self.varMap[expr.target] + i = ir.Load(loc, tmp) self.builder.addIns(i) return tmp elif type(expr) is astnodes.Literal: diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/ir/basicblock.py --- a/python/ir/basicblock.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/ir/basicblock.py Fri Apr 19 19:22:52 2013 +0200 @@ -1,6 +1,6 @@ class BasicBlock: - # Uninterrupted sequence of instructions. + """ Uninterrupted sequence of instructions. """ def __init__(self, name): self.name = name self.instructions = [] @@ -13,6 +13,7 @@ def replaceInstruction(self, i1, i2): idx = self.instructions.index(i1) i1.parent = None + i1.delete() i2.parent = self self.instructions[idx] = i2 def removeInstruction(self, i): @@ -20,10 +21,16 @@ self.instructions.remove(i) def getInstructions(self): return self.instructions - Instructions = property(getInstructions) + def setInstructions(self, ins): + for i in self.instructions: + i.parent = None + self.instructions = ins + for i in self.instructions: + i.parent = self + Instructions = property(getInstructions, setInstructions) def getLastIns(self): return self.instructions[-1] - LastIns = property(getLastIns) + LastInstruction = property(getLastIns) @property def Empty(self): return len(self.instructions) == 0 @@ -33,8 +40,11 @@ FirstIns = FirstInstruction def getSuccessors(self): if not self.Empty: - i = self.LastIns + i = self.LastInstruction return i.Targets return [] Successors = property(getSuccessors) + def getPredecessors(self): + return [] + Predecessors = property(getPredecessors) diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/ir/builder.py --- a/python/ir/builder.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/ir/builder.py Fri Apr 19 19:22:52 2013 +0200 @@ -9,14 +9,16 @@ yield a a = a + 1 self.nums = NumGen() - def gen(self): - return '{0}{1}'.format(self.prefix, self.nums.__next__()) + def gen(self, prefix=None): + if not prefix: + prefix = self.prefix + return '{0}{1}'.format(prefix, self.nums.__next__()) class ValueGenerator(NameGenerator): def __init__(self): super().__init__('t') - def gen(self): - v = Value(super().gen()) + def gen(self, prefix=None): + v = Value(super().gen(prefix)) return v class BBGenerator(NameGenerator): diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/ir/instruction.py --- a/python/ir/instruction.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/ir/instruction.py Fri Apr 19 19:22:52 2013 +0200 @@ -7,12 +7,24 @@ self.name = name self.interferes = set() self.reg = None + self.used_by = [] def __repr__(self): if self.reg: n = self.reg else: n = self.name - return '{0}'.format(n) + return '{0}'.format(n) # + str(self.IsUsed) + @property + def IsUsed(self): + return len(self.used_by) > 0 + +class Use: + def __init__(self, user, val): + self.user = user + 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. """ @@ -21,11 +33,21 @@ self.live_in = set() self.live_out = set() # What variables this instruction uses and defines: - self.defs = set() - self.uses = set() + self.defs = [] + self.uses = [] + def delete(self): + for use in self.uses: + use.delete() + self.uses.clear() + def addUse(self, val): + self.uses.append(Use(self, val)) + def addDef(self, v): + self.defs.append(v) def getParent(self): return self.parent - Parent = property(getParent) + def setParent(self, p): + self.parent = p + Parent = property(getParent, setParent) @property def Targets(self): return self.getTargets() @@ -40,17 +62,34 @@ return 'CALL {0}'.format(self.callee) class Return(Instruction): + def __init__(self, value=None): + super().__init__() + self.value = value + if value: + self.addUse(value) def __repr__(self): - return 'RET' + if self.value: + return 'Return {0}'.format(self.value) + else: + return 'Return' def getTargets(self): return [] +class Alloc(Instruction): + """ Allocates space on the stack """ + def __init__(self, value): + super().__init__() + self.value = value + self.addDef(value) + def __repr__(self): + return '{0} = alloc'.format(self.value) + class ImmLoad(Instruction): def __init__(self, target, value): super().__init__() self.target = target self.value = value - self.defs.add(target) + self.addDef(target) def __repr__(self): return '{0} = {1}'.format(self.target, self.value) @@ -61,33 +100,38 @@ #print('operation is in binops:', operation in BinOps) # Check types of the two operands: self.result = result - self.defs.add(result) + self.addDef(result) self.value1 = value1 self.value2 = value2 - self.uses.add(value1) - self.uses.add(value2) + 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) # Memory functions: class Load(Instruction): - def __init__(self, name, value): + def __init__(self, location, value): super().__init__() + assert type(value) is Value + assert type(location) is Value, "Location must be a value" self.value = value - self.defs.add(value) - self.name = name + self.addDef(value) + self.location = location + self.addUse(self.location) def __repr__(self): - return '{1} = [{0}]'.format(self.name, self.value) + return '{1} = [{0}]'.format(self.location, self.value) class Store(Instruction): - def __init__(self, name, value): + def __init__(self, location, value): super().__init__() - self.name = name + assert type(value) is Value + assert type(location) is Value, "Location must be a value" + self.location = location self.value = value - self.uses.add(value) + self.addUse(value) def __repr__(self): - return '[{0}] = {1}'.format(self.name, self.value) + return '[{0}] = {1}'.format(self.location, self.value) # Branching: class Branch(Instruction): @@ -107,8 +151,8 @@ assert type(a) is Value self.cond = cond self.b = b - self.uses.add(a) - self.uses.add(b) + self.addUse(a) + self.addUse(b) assert type(b) is Value assert type(lab1) is BasicBlock self.lab1 = lab1 diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/ir/module.py --- a/python/ir/module.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/ir/module.py Fri Apr 19 19:22:52 2013 +0200 @@ -38,11 +38,11 @@ def dumpgv(self, outf): outf.write('digraph G \n{\n') for f in self.Functions: - outf.write('{0} [label="{1}"]\n'.format(id(f), f)) + outf.write('{0} [label="{1}" shape=box3d]\n'.format(id(f), f)) for bb in f.BasicBlocks: contents = str(bb) + '\n' contents += '\n'.join([str(i) for i in bb.Instructions]) - outf.write('{0} [label="{1}"];\n'.format(id(bb), contents)) + outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents)) for successor in bb.Successors: outf.write('"{0}" -> "{1}"\n'.format(id(bb), id(successor))) outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry))) @@ -55,5 +55,5 @@ 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 Value, "use must be Value, not {0}".format(type(t)) + assert type(t) is Use, "use must be Value, not {0}".format(type(t)) diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/testir.py --- a/python/testir.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/testir.py Fri Apr 19 19:22:52 2013 +0200 @@ -27,7 +27,11 @@ function int add2(int x, int y) { var int res; - res = x + y; + res = x + y + 2 - 7 + 2; + if (x > 13) + { + res = res + 2; + } return res; } @@ -60,4 +64,3 @@ ir.dumpgv(f) os.system('dot -Tpdf -ograaf.pdf graaf.gv') - diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/transform.py --- a/python/transform.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/transform.py Fri Apr 19 19:22:52 2013 +0200 @@ -20,7 +20,7 @@ class InstructionPass(BasicBlockPass): def onBasicBlock(self, bb): - for ins in bb.Instructions: + for ins in iter(bb.Instructions): self.onInstruction(ins) def onInstruction(self, ins): """ Override this virtual method """ @@ -50,9 +50,15 @@ print(i2) i.Parent.replaceInstruction(i, i2) -class DeadCodeDeleter(InstructionPass): - def onInstruction(self, ins): - print(ins, ins.Users) - if not ins.defs in ins.live_out: - ins.Parent.removeInstruction(ins) +class DeadCodeDeleter(BasicBlockPass): + def onBasicBlock(self, bb): + def instructionUsed(ins): + if len(ins.defs) == 0: + # In case this instruction does not define any variables, assume it is usefull. + return True + for d in ins.defs: + if d.IsUsed: + return True + return False + bb.Instructions = list(filter(instructionUsed, bb.Instructions)) diff -r c1d2b6b9f9a7 -r 3eb06f5fb987 python/x86.py --- a/python/x86.py Fri Apr 19 12:42:21 2013 +0200 +++ b/python/x86.py Fri Apr 19 19:22:52 2013 +0200 @@ -35,18 +35,18 @@ self.asm = [] # Allocate registers: ra = registerallocator.RegisterAllocator() + # TODO: do not register allocate on intermediate code: ra.registerAllocate(ir, self.regs) self.genModule(ir) return self.asm def genModule(self, ir): - #for f in ir.Functions: - # self.genFunction(f) - for bb in ir.BasicBlocks: - self.genBB(bb) + for f in ir.Functions: + self.genFunction(f) def genFunction(self, f): self.emit('global {0}'.format(f.name)) self.emit(AsmLabel(f.name)) + self.emit(Jmp('jmp', f.entry.name)) for bb in f.BasicBlocks: self.genBB(bb) def genBB(self, bb): @@ -62,7 +62,7 @@ else: raise NotImplementedError('op {0}'.format(i.operation)) elif type(i) is ir.Load: - self.emit(Op('mov', i.value, '[{0}]'.format(i.name))) + self.emit(Op('mov', i.value, '[{0}]'.format(i.location))) elif type(i) is ir.Return: self.emit('ret') elif type(i) is ir.Call: @@ -70,7 +70,7 @@ elif type(i) is ir.ImmLoad: self.emit(Op('mov', i.target, i.value)) elif type(i) is ir.Store: - self.emit(Op('mov', '[{0}]'.format(i.name), i.value)) + self.emit(Op('mov', '[{0}]'.format(i.location), i.value)) elif type(i) is ir.ConditionalBranch: self.emit(Op('cmp', i.a, i.b)) jmps = {'>':'jg', '<':'jl', '==':'je'} @@ -82,6 +82,8 @@ self.emit(Jmp('jmp', i.lab2.name)) elif type(i) is ir.Branch: self.emit(Jmp('jmp', i.target.name)) + elif type(i) is ir.Alloc: + pass else: raise NotImplementedError('{0}'.format(i))