Mercurial > lcfOS
changeset 296:9417caea2eb3
Directorized some backend files
| author | Windel Bouwman |
|---|---|
| date | Sun, 01 Dec 2013 13:36:58 +0100 |
| parents | 917eab04b8b7 |
| children | a6f61e9a9d5c |
| files | kernel/kernel.c3 kernel/make.py kernel/memory.c3 kernel/process.c3 kernel/schedule.c3 python/asm.py python/c3/parser.py python/canon.py python/codegen.py python/codegen/__init__.py python/codegen/canon.py python/codegen/codegen.py python/codegen/dag.py python/codegen/flowgraph.py python/codegen/graph.py python/codegen/interferencegraph.py python/codegen/registerallocator.py python/dag.py python/flowgraph.py python/graph.py python/interferencegraph.py python/mem2reg.py python/outstream.py python/ppci/errors.py python/registerallocator.py python/transform.py python/zcc.py test/runtests.sh test/testgraph.py test/testregalloc.py |
| diffstat | 29 files changed, 739 insertions(+), 747 deletions(-) [+] |
line wrap: on
line diff
--- a/kernel/kernel.c3 Thu Nov 28 21:10:32 2013 +0100 +++ b/kernel/kernel.c3 Sun Dec 01 13:36:58 2013 +0100 @@ -12,9 +12,9 @@ memory:init(); - Process proc = new process:Process(); + //Process proc = new process:Process(); - scheduler:queue(proc); + //scheduler:queue(proc); }
--- a/kernel/make.py Thu Nov 28 21:10:32 2013 +0100 +++ b/kernel/make.py Sun Dec 01 13:36:58 2013 +0100 @@ -5,7 +5,7 @@ sys.path.insert(0, os.path.join('..', 'python')) import zcc -arglist = ['memory.c3', 'kernel.c3', 'syscall.c3'] +arglist = ['memory.c3', 'kernel.c3', 'syscall.c3', 'process.c3', 'schedule.c3'] arglist += ['--target', 'arm'] arglist += ['--dumpasm'] arglist += ['--log', 'debug']
--- a/kernel/memory.c3 Thu Nov 28 21:10:32 2013 +0100 +++ b/kernel/memory.c3 Sun Dec 01 13:36:58 2013 +0100 @@ -2,11 +2,11 @@ import process; -var uint8_t* ptr; +var u8* ptr; -function uint8_t* Alloc(int size) +function u8* Alloc(int size) { - ptr += size; + ptr = ptr + size; return ptr; }
--- a/kernel/process.c3 Thu Nov 28 21:10:32 2013 +0100 +++ b/kernel/process.c3 Sun Dec 01 13:36:58 2013 +0100 @@ -3,19 +3,19 @@ import kernel; // process type definition: -typedef struct { +type struct { int id; int status; } process_t; // Or, use this list structure: -List<process_t> procs; +// List<process_t> procs; // init is the root of all processes: var process_t* init = 0; var int next_pid = 0; -public function void init() +function void init() { next_pid = 0; init = Create(); @@ -24,7 +24,7 @@ /* Create a new process. */ -public func process_t* Create() +function process_t* Create() { process_t* p = memory.Alloc(sizeof(process_t)); p->id = next_pid;
--- a/kernel/schedule.c3 Thu Nov 28 21:10:32 2013 +0100 +++ b/kernel/schedule.c3 Sun Dec 01 13:36:58 2013 +0100 @@ -1,7 +1,7 @@ -module schedule.c3; +module scheduler; -func void executeNext() +function void executeNext() { process_t *old;
--- a/python/c3/parser.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/c3/parser.py Sun Dec 01 13:36:58 2013 +0100 @@ -1,6 +1,14 @@ import logging from .lexer import Lexer -from . import astnodes +from .astnodes import FieldRef, Literal, TypeCast, Unop, Binop +from .astnodes import Assignment, ExpressionStatement, CompoundStatement +from .astnodes import ReturnStatement, WhileStatement, IfStatement +from .astnodes import FunctionType, Function, FormalParameter +from .astnodes import StructureType, DefinedType, PointerType +from .astnodes import Constant, Variable +from .astnodes import StructField, Deref +from .astnodes import Package, ImportDesignator +from .astnodes import Designator, VariableUse, FunctionCall from ppci import CompilerError @@ -67,7 +75,7 @@ self.Consume('module') name = self.Consume('ID') self.Consume(';') - self.mod = astnodes.Package(name.val, name.loc) + self.mod = Package(name.val, name.loc) self.currentPart = self.mod while self.Peak != 'END': self.parseTopLevel() @@ -92,9 +100,9 @@ name = self.Consume('ID') if self.hasConsumed(':'): name2 = self.Consume('ID') - return astnodes.ImportDesignator(name.val, name2.val, name.loc) + return ImportDesignator(name.val, name2.val, name.loc) else: - return astnodes.Designator(name.val, name.loc) + return Designator(name.val, name.loc) # Type system def parseTypeSpec(self): @@ -107,18 +115,18 @@ while self.Peak != '}': mem_t = self.parseTypeSpec() mem_n = self.Consume('ID').val - mems.append(astnodes.StructField(mem_n, mem_t)) + mems.append(StructField(mem_n, mem_t)) while self.hasConsumed(','): mem_n = self.Consume('ID').val - mems.append(astnodes.StructField(mem_n, mem_t)) + mems.append(StructField(mem_n, mem_t)) self.Consume(';') self.Consume('}') - theT = astnodes.StructureType(mems) + theT = StructureType(mems) else: theT = self.parseDesignator() # Check for pointer suffix: while self.hasConsumed('*'): - theT = astnodes.PointerType(theT) + theT = PointerType(theT) return theT def parseTypeDef(self): @@ -126,7 +134,7 @@ newtype = self.parseTypeSpec() typename = self.Consume('ID') self.Consume(';') - df = astnodes.DefinedType(typename.val, newtype, typename.loc) + df = DefinedType(typename.val, newtype, typename.loc) self.addDeclaration(df) # Variable declarations: @@ -135,7 +143,7 @@ t = self.parseTypeSpec() def parseVar(): name = self.Consume('ID') - v = astnodes.Variable(name.val, t) + v = Variable(name.val, t) v.loc = name.loc if self.hasConsumed('='): v.ival = self.Expression() @@ -152,7 +160,7 @@ name = self.Consume('ID') self.Consume('=') val = self.Expression() - c = astnodes.Constant(name.val, t, val) + c = Constant(name.val, t, val) c.loc = name.loc parseConst() while self.hasConsumed(','): @@ -164,7 +172,7 @@ loc = self.Consume('function').loc returntype = self.parseTypeSpec() fname = self.Consume('ID').val - f = astnodes.Function(fname, loc) + f = Function(fname, loc) self.addDeclaration(f) savePart = self.currentPart self.currentPart = f @@ -174,7 +182,7 @@ def parseParameter(): typ = self.parseTypeSpec() name = self.Consume('ID') - param = astnodes.FormalParameter(name.val, typ) + param = FormalParameter(name.val, typ) param.loc = name.loc self.addDeclaration(param) parameters.append(param) @@ -183,7 +191,7 @@ parseParameter() self.Consume(')') paramtypes = [p.typ for p in parameters] - f.typ = astnodes.FunctionType(paramtypes, returntype) + f.typ = FunctionType(paramtypes, returntype) f.body = self.parseCompoundStatement() self.currentPart = savePart @@ -199,7 +207,7 @@ no = self.parseCompoundStatement() else: no = None - return astnodes.IfStatement(condition, yes, no, loc) + return IfStatement(condition, yes, no, loc) def parseWhileStatement(self): loc = self.Consume('while').loc @@ -207,16 +215,16 @@ condition = self.Expression() self.Consume(')') statements = self.parseCompoundStatement() - return astnodes.WhileStatement(condition, statements, loc) + return WhileStatement(condition, statements, loc) def parseReturnStatement(self): loc = self.Consume('return').loc if self.Peak == ';': - expr = astnodes.Literal(0, loc) + expr = Literal(0, loc) else: expr = self.Expression() self.Consume(';') - return astnodes.ReturnStatement(expr, loc) + return ReturnStatement(expr, loc) def parseCompoundStatement(self): self.Consume('{') @@ -226,7 +234,7 @@ if s is None: continue statements.append(s) - return astnodes.CompoundStatement(statements) + return CompoundStatement(statements) def Statement(self): # Determine statement type based on the pending token: @@ -251,9 +259,9 @@ # We enter assignment mode here. loc = self.Consume('=').loc rhs = self.Expression() - return astnodes.Assignment(x, rhs, loc) + return Assignment(x, rhs, loc) else: - return astnodes.ExpressionStatement(x, x.loc) + return ExpressionStatement(x, x.loc) # Expression section: # We not implement these C constructs: @@ -266,7 +274,7 @@ while self.Peak == 'or': loc = self.Consume('or').loc e2 = self.LogicalAndExpression() - exp = astnodes.Binop(exp, 'or', e2, loc) + exp = Binop(exp, 'or', e2, loc) return exp def LogicalAndExpression(self): @@ -274,7 +282,7 @@ while self.Peak == 'and': loc = self.Consume('and').loc o2 = self.EqualityExpression() - o = astnodes.Binop(o, 'and', o2, loc) + o = Binop(o, 'and', o2, loc) return o def EqualityExpression(self): @@ -282,7 +290,7 @@ while self.Peak in ['<', '==', '>']: op = self.Consume(self.Peak) ee2 = self.SimpleExpression() - ee = astnodes.Binop(ee, op.typ, ee2, op.loc) + ee = Binop(ee, op.typ, ee2, op.loc) return ee def SimpleExpression(self): @@ -291,7 +299,7 @@ while self.Peak in ['>>', '<<']: op = self.Consume(self.Peak) e2 = self.AddExpression() - e = astnodes.Binop(e, op.typ, e2, op.loc) + e = Binop(e, op.typ, e2, op.loc) return e def AddExpression(self): @@ -299,7 +307,7 @@ while self.Peak in ['+', '-']: op = self.Consume(self.Peak) e2 = self.Term() - e = astnodes.Binop(e, op.typ, e2, op.loc) + e = Binop(e, op.typ, e2, op.loc) return e def Term(self): @@ -307,7 +315,7 @@ while self.Peak in ['*', '/']: op = self.Consume(self.Peak) t2 = self.BitwiseOr() - t = astnodes.Binop(t, op.typ, t2, op.loc) + t = Binop(t, op.typ, t2, op.loc) return t def BitwiseOr(self): @@ -315,7 +323,7 @@ while self.Peak in ['|']: op = self.Consume(self.Peak) b = self.BitwiseAnd() - a = astnodes.Binop(a, op.typ, b, op.loc) + a = Binop(a, op.typ, b, op.loc) return a def BitwiseAnd(self): @@ -323,7 +331,7 @@ while self.Peak in ['&']: op = self.Consume(self.Peak) b = self.CastExpression() - a = astnodes.Binop(a, op.typ, b, op.loc) + a = Binop(a, op.typ, b, op.loc) return a # Domain of unary expressions: @@ -341,7 +349,7 @@ self.Consume('(') ce = self.Expression() self.Consume(')') - return astnodes.TypeCast(t, ce, loc) + return TypeCast(t, ce, loc) else: return self.UnaryExpression() @@ -350,9 +358,9 @@ op = self.Consume(self.Peak) ce = self.CastExpression() if op.val == '*': - return astnodes.Deref(ce, op.loc) + return Deref(ce, op.loc) else: - return astnodes.Unop(op.typ, ce, op.loc) + return Unop(op.typ, ce, op.loc) else: return self.PostFixExpression() @@ -369,14 +377,14 @@ while self.hasConsumed(','): args.append(self.Expression()) self.Consume(')') - pfe = astnodes.FunctionCall(pfe, args, pfe.loc) + pfe = FunctionCall(pfe, args, pfe.loc) elif self.hasConsumed('->'): field = self.Consume('ID') - pfe = astnodes.Deref(pfe, pfe.loc) - pfe = astnodes.FieldRef(pfe, field.val, field.loc) + pfe = Deref(pfe, pfe.loc) + pfe = FieldRef(pfe, field.val, field.loc) elif self.hasConsumed('.'): field = self.Consume('ID') - pfe = astnodes.FieldRef(pfe, field.val, field.loc) + pfe = FieldRef(pfe, field.val, field.loc) else: raise Exception() return pfe @@ -388,17 +396,17 @@ return e elif self.Peak == 'NUMBER': val = self.Consume('NUMBER') - return astnodes.Literal(val.val, val.loc) + return Literal(val.val, val.loc) elif self.Peak == 'REAL': val = self.Consume('REAL') - return astnodes.Literal(val.val, val.loc) + return Literal(val.val, val.loc) elif self.Peak == 'true': val = self.Consume('true') - return astnodes.Literal(True, val.loc) + return Literal(True, val.loc) elif self.Peak == 'false': val = self.Consume('false') - return astnodes.Literal(False, val.loc) + return Literal(False, val.loc) elif self.Peak == 'ID': d = self.parseDesignator() - return astnodes.VariableUse(d, d.loc) + return VariableUse(d, d.loc) self.Error('Expected NUM, ID or (expr), got {0}'.format(self.Peak))
--- a/python/canon.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,128 +0,0 @@ -import ir -from itertools import chain - -def make(function, frame): - """ - Create canonicalized version of the IR-code. This means: - - Calls out of expressions. - - Other things? - """ - # Change the tree. This modifies the IR-tree! - # Move all parameters into registers - parmoves = [] - for p in function.arguments: - pt = newTemp() - frame.parMap[p] = pt - parmoves.append(ir.Move(pt, frame.argLoc(p.num))) - function.entry.instructions = parmoves + function.entry.instructions - - for block in function.Blocks: - for stmt in block.instructions: - rewriteStmt(stmt, frame) - linearize(block) - # TODO: schedule here? - -# Visit all nodes with some function: -# TODO: rewrite into visitor. - -# Rewrite rewrites call instructions into Eseq instructions. - -def rewriteStmt(stmt, frame): - if isinstance(stmt, ir.Jump): - pass - elif isinstance(stmt, ir.CJump): - stmt.a = rewriteExp(stmt.a, frame) - stmt.b = rewriteExp(stmt.b, frame) - elif isinstance(stmt, ir.Move): - stmt.src = rewriteExp(stmt.src, frame) - stmt.dst = rewriteExp(stmt.dst, frame) - elif isinstance(stmt, ir.Terminator): - pass - elif isinstance(stmt, ir.Exp): - stmt.e = rewriteExp(stmt.e, frame) - else: - raise NotImplementedError('STMT NI: {}'.format(stmt)) - -newTemp = ir.NamedClassGenerator('canon_reg', ir.Temp).gen - -def rewriteExp(exp, frame): - if isinstance(exp, ir.Binop): - exp.a = rewriteExp(exp.a, frame) - exp.b = rewriteExp(exp.b, frame) - return exp - elif isinstance(exp, ir.Const): - return exp - elif isinstance(exp, ir.Temp): - return exp - elif isinstance(exp, ir.Parameter): - return frame.parMap[exp] - elif isinstance(exp, ir.LocalVariable): - offset = frame.allocVar(exp) - return ir.Add(frame.fp, ir.Const(offset)) - elif isinstance(exp, ir.Mem): - exp.e = rewriteExp(exp.e, frame) - return exp - elif isinstance(exp, ir.Call): - exp.arguments = [rewriteExp(p, frame) for p in exp.arguments] - # Rewrite call into eseq: - t = newTemp() - return ir.Eseq(ir.Move(t, exp), t) - else: - raise NotImplementedError('NI: {}'.format(exp)) - -# The flatten functions pull out seq instructions to the sequence list. - -def flattenExp(exp): - if isinstance(exp, ir.Binop): - exp.a, sa = flattenExp(exp.a) - exp.b, sb = flattenExp(exp.b) - return exp, sa + sb - elif isinstance(exp, ir.Temp): - return exp, [] - elif isinstance(exp, ir.Const): - return exp, [] - elif isinstance(exp, ir.Mem): - exp.e, s = flattenExp(exp.e) - return exp, s - elif isinstance(exp, ir.Eseq): - s = flattenStmt(exp.stmt) - exp.e, se = flattenExp(exp.e) - return exp.e, s + se - elif isinstance(exp, ir.Call): - sp = [] - p = [] - for p_, sp_ in (flattenExp(p) for p in exp.arguments): - p.append(p_) - sp.extend(sp_) - exp.arguments = p - return exp, sp - else: - raise NotImplementedError('NI: {}'.format(exp)) - -def flattenStmt(stmt): - if isinstance(stmt, ir.Jump): - return [stmt] - elif isinstance(stmt, ir.CJump): - stmt.a, sa = flattenExp(stmt.a) - stmt.b, sb = flattenExp(stmt.b) - return sa + sb + [stmt] - elif isinstance(stmt, ir.Move): - stmt.dst, sd = flattenExp(stmt.dst) - stmt.src, ss = flattenExp(stmt.src) - return sd + ss + [stmt] - elif isinstance(stmt, ir.Terminator): - return [stmt] - elif isinstance(stmt, ir.Exp): - stmt.e, se = flattenExp(stmt.e) - return se + [stmt] - else: - raise NotImplementedError('STMT NI: {}'.format(stmt)) - - -def linearize(block): - """ - Move seq instructions to top and flatten these in an instruction list - """ - i = list(flattenStmt(s) for s in block.instructions) - block.instructions = list(chain.from_iterable(i)) -
--- a/python/codegen.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,52 +0,0 @@ -import ir -from target import Target -from ppci import CompilerError -import transform -import canon -import registerallocator - - -class CodeGenerator: - """ Generic code generator """ - def __init__(self, target): - # TODO: schedule traces in better order. - # This is optional! - assert isinstance(target, Target), target - self.target = target - self.ins_sel = target.ins_sel - self.ra = registerallocator.RegisterAllocator() - - def generateFunc(self, irfunc, outs): - """ Generate code for one function into a frame """ - # Cleanup function: - transform.removeEmptyBlocks(irfunc) - - # Create a frame for this function: - frame = self.target.FrameClass(irfunc.name) - - # Canonicalize the intermediate language: - canon.make(irfunc, frame) - self.ins_sel.munchFunction(irfunc, frame) - - # Do register allocation: - self.ra.allocFrame(frame) - # TODO: Peep-hole 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(outs) - return frame - - def generate(self, ircode, outs): - assert isinstance(ircode, ir.Module) - outs.selectSection('code') - - # 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, outs) for func in ircode.Functions] - return self.frames
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/__init__.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,1 @@ +from .codegen import CodeGenerator
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/canon.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,128 @@ +import ir +from itertools import chain + +def make(function, frame): + """ + Create canonicalized version of the IR-code. This means: + - Calls out of expressions. + - Other things? + """ + # Change the tree. This modifies the IR-tree! + # Move all parameters into registers + parmoves = [] + for p in function.arguments: + pt = newTemp() + frame.parMap[p] = pt + parmoves.append(ir.Move(pt, frame.argLoc(p.num))) + function.entry.instructions = parmoves + function.entry.instructions + + for block in function.Blocks: + for stmt in block.instructions: + rewriteStmt(stmt, frame) + linearize(block) + # TODO: schedule here? + +# Visit all nodes with some function: +# TODO: rewrite into visitor. + +# Rewrite rewrites call instructions into Eseq instructions. + +def rewriteStmt(stmt, frame): + if isinstance(stmt, ir.Jump): + pass + elif isinstance(stmt, ir.CJump): + stmt.a = rewriteExp(stmt.a, frame) + stmt.b = rewriteExp(stmt.b, frame) + elif isinstance(stmt, ir.Move): + stmt.src = rewriteExp(stmt.src, frame) + stmt.dst = rewriteExp(stmt.dst, frame) + elif isinstance(stmt, ir.Terminator): + pass + elif isinstance(stmt, ir.Exp): + stmt.e = rewriteExp(stmt.e, frame) + else: + raise NotImplementedError('STMT NI: {}'.format(stmt)) + +newTemp = ir.NamedClassGenerator('canon_reg', ir.Temp).gen + +def rewriteExp(exp, frame): + if isinstance(exp, ir.Binop): + exp.a = rewriteExp(exp.a, frame) + exp.b = rewriteExp(exp.b, frame) + return exp + elif isinstance(exp, ir.Const): + return exp + elif isinstance(exp, ir.Temp): + return exp + elif isinstance(exp, ir.Parameter): + return frame.parMap[exp] + elif isinstance(exp, ir.LocalVariable): + offset = frame.allocVar(exp) + return ir.Add(frame.fp, ir.Const(offset)) + elif isinstance(exp, ir.Mem): + exp.e = rewriteExp(exp.e, frame) + return exp + elif isinstance(exp, ir.Call): + exp.arguments = [rewriteExp(p, frame) for p in exp.arguments] + # Rewrite call into eseq: + t = newTemp() + return ir.Eseq(ir.Move(t, exp), t) + else: + raise NotImplementedError('NI: {}'.format(exp)) + +# The flatten functions pull out seq instructions to the sequence list. + +def flattenExp(exp): + if isinstance(exp, ir.Binop): + exp.a, sa = flattenExp(exp.a) + exp.b, sb = flattenExp(exp.b) + return exp, sa + sb + elif isinstance(exp, ir.Temp): + return exp, [] + elif isinstance(exp, ir.Const): + return exp, [] + elif isinstance(exp, ir.Mem): + exp.e, s = flattenExp(exp.e) + return exp, s + elif isinstance(exp, ir.Eseq): + s = flattenStmt(exp.stmt) + exp.e, se = flattenExp(exp.e) + return exp.e, s + se + elif isinstance(exp, ir.Call): + sp = [] + p = [] + for p_, sp_ in (flattenExp(p) for p in exp.arguments): + p.append(p_) + sp.extend(sp_) + exp.arguments = p + return exp, sp + else: + raise NotImplementedError('NI: {}'.format(exp)) + +def flattenStmt(stmt): + if isinstance(stmt, ir.Jump): + return [stmt] + elif isinstance(stmt, ir.CJump): + stmt.a, sa = flattenExp(stmt.a) + stmt.b, sb = flattenExp(stmt.b) + return sa + sb + [stmt] + elif isinstance(stmt, ir.Move): + stmt.dst, sd = flattenExp(stmt.dst) + stmt.src, ss = flattenExp(stmt.src) + return sd + ss + [stmt] + elif isinstance(stmt, ir.Terminator): + return [stmt] + elif isinstance(stmt, ir.Exp): + stmt.e, se = flattenExp(stmt.e) + return se + [stmt] + else: + raise NotImplementedError('STMT NI: {}'.format(stmt)) + + +def linearize(block): + """ + Move seq instructions to top and flatten these in an instruction list + """ + i = list(flattenStmt(s) for s in block.instructions) + block.instructions = list(chain.from_iterable(i)) +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/codegen.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,48 @@ +import ir +from target import Target +from ppci import CompilerError +from .canon import make as canonicalize +from .registerallocator import RegisterAllocator + + +class CodeGenerator: + """ Generic code generator """ + def __init__(self, target): + # TODO: schedule traces in better order. + # This is optional! + assert isinstance(target, Target), target + self.target = target + self.ins_sel = target.ins_sel + self.ra = RegisterAllocator() + + def generateFunc(self, irfunc, outs): + """ Generate code for one function into a frame """ + # Create a frame for this function: + frame = self.target.FrameClass(irfunc.name) + + # Canonicalize the intermediate language: + canonicalize(irfunc, frame) + self.ins_sel.munchFunction(irfunc, frame) + + # Do register allocation: + self.ra.allocFrame(frame) + # TODO: Peep-hole here? + + # Add label and return and stack adjustment: + frame.EntryExitGlue3() + + # Materialize the register allocated instructions into a stream of + # real instructions. + frame.lower_to(outs) + return frame + + def generate(self, ircode, outs): + """ Generate code into output stream """ + assert isinstance(ircode, ir.Module) + outs.selectSection('code') + + # 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(f, outs) for f in ircode.Functions] + return self.frames
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/dag.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,59 @@ + +# Instruction selection with DAG (Directed Acyclic Graph) +class DagLeaf: + def __init__(self, v): + self.v = v + +class DagNode: + def __init__(self, name): + self.name = name + self.children = [] + def __repr__(self): + return str(self.name) + +class Dag: + def __init__(self, bb): + self.mapping = {} + self.buildFromBB(bb) + + def buildFromBB(self, bb): + for ins in bb.Instructions: + if type(ins) is ir.BinaryOperator: + if not ins.value1 in self.mapping: + self.mapping[ins.value1] = DagNode(ins.value1) + if not ins.value2 in self.mapping: + self.mapping[ins.value2] = DagNode(ins.value2) + # look for op with left and right operand the same: + N = None + lnode = self.mapping[ins.value1] + rnode = self.mapping[ins.value2] + for node in self.mapping.values(): + if node.name == ins.operation: + if node.children[0] == lnode and node.children[1] == rnode: + N = node + break + if not N: + # Create a node. + N = DagNode(ins.operation) + N.children.append(lnode) + N.children.append(rnode) + self.mapping[ins.result] = N + else: + pass + + def dumpgv(self, outf): + outf.write('subgraph {0} {{\n'.format(id(self))) + for node in self.mapping.values(): + outf.write('{0} [label="{1}"];\n'.format(id(node), node.name)) + for c in node.children: + outf.write('{0} -> {1};\n'.format(id(node), id(c))) + outf.write('label="dag"}\n') + +def insSelect(mod): + """ Create DAG from ir-code """ + for bb in mod.BasicBlocks: + print(bb) + dag = Dag(bb) + print(dag.mapping) + bb.dag = dag +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/flowgraph.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,46 @@ +from .graph import DiGraph, DiNode + + +class FlowGraphNode(DiNode): + """ A node in the flow graph """ + def __init__(self, g, ins): + super().__init__(g) + self.ins = ins + self.uses = set(ins.src) + self.defs = set(ins.dst) + self.live_in = set() + self.live_out = set() + + def __repr__(self): + r = '{}'.format(self.ins) + if self.uses: + r += ' uses:' + ', '.join(str(u) for u in self.uses) + if self.defs: + r += ' defs:' + ', '.join(str(d) for d in self.defs) + return r + + +class FlowGraph(DiGraph): + def __init__(self, instrs): + """ Create a flowgraph from a list of abstract instructions """ + super().__init__() + self._map = {} + # Add nodes: + for ins in instrs: + n = FlowGraphNode(self, ins) + self._map[ins] = n + self.addNode(n) + + # Make edges: + prev = None + for ins in instrs: + n = self._map[ins] + if prev: + self.addEdge(prev, n) + if ins.jumps: + prev = None + for j in ins.jumps: + to_n = self._map[j] + self.addEdge(n, to_n) + else: + prev = n
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/graph.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,84 @@ + +class Graph: + """ + Generic graph base class. + Can dump to graphiz dot format for example! + """ + def __init__(self): + self.nodes = set() + self.edges = set() + + def addNode(self, n): + self.nodes.add(n) + + def delNode(self, n): + self.nodes.remove(n) + + def addEdge(self, n, m): + """ Add an edge from n to m """ + self.edges.add((n, m)) + self.edges.add((m, n)) + + def hasEdge(self, n, m): + return (n, m) in self.edges + + def delEdge(self, n, m): + self.edges.remove((n, m)) + self.edges.remove((m, n)) + + def adjecent(self, n): + """ Return all nodes with edges to n """ + # TODO: this can be optimized for speed: + return set(m for m in self.nodes if self.hasEdge(n, m)) + + def to_dot(self, f): + """ Generate graphviz dot representation """ + for n in self.nodes: + print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f) + for n, m in self.edges: + print('{} -> {};'.format(id(n), id(m)), file=f) + + +class Node: + """ + Node in a graph. + """ + def __init__(self, g): + self.g = g + self.addDegree = 0 # Hack to increase degree + + @property + def Adjecent(self): + return self.g.adjecent(self) + + @property + def Degree(self): + return len(self.Adjecent) + self.addDegree + + +class DiGraph(Graph): + """ + Directed graph. + """ + def addEdge(self, n, m): + """ Add an edge from n to m """ + self.edges.add((n, m)) + + def hasEdge(self, n, m): + return (n, m) in self.edges + + def successors(self, n): + return set(m for m in self.nodes if self.hasEdge(n, m)) + + def predecessors(self, n): + return set(m for m in self.nodes if self.hasEdge(m, n)) + + +class DiNode(Node): + @property + def Succ(self): + return self.g.successors(self) + + @property + def Pred(self): + return self.g.predecessors(self)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/interferencegraph.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,89 @@ +from .graph import Graph, Node + + +class InterferenceGraphNode(Node): + def __init__(self, g, varname): + super().__init__(g) + self.temps = [varname] + self.moves = set() + self.color = None + + def __repr__(self): + return '{}({})'.format(self.temps, self.color) + + +class InterferenceGraph(Graph): + """ + Interference graph. + """ + def __init__(self, flowgraph): + """ Create a new interference graph from a flowgraph """ + super().__init__() + # Calculate liveness in CFG: + ### + # Liveness: + # in[n] = use[n] UNION (out[n] - def[n]) + # out[n] = for s in n.succ in union in[s] + ### + for n in flowgraph.nodes: + n.live_in = set() + n.live_out = set() + + # Dataflow fixed point iteration: + change = True + while change: + change = False + for n in flowgraph.nodes: + _in = n.live_in + _out = n.live_out + n.live_in = n.uses | (n.live_out - n.defs) + if n.Succ: + n.live_out = set.union(*(s.live_in for s in n.Succ)) + else: + n.live_out = set() + change = change or (_in != n.live_in) or (_out != n.live_out) + + # Construct interference graph: + for n in flowgraph.nodes: + for tmp in n.live_out: + n1 = self.getNode(tmp) + for tmp2 in (n.live_out - {tmp}): + n2 = self.getNode(tmp2) + self.addEdge(n1, n2) + + def to_dot(self, f): + """ Generate graphviz dot representation """ + for n in self.nodes: + print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f) + for n, m in self.edges: + print('{} -> {};'.format(id(n), id(m)), file=f) + + def to_txt(self): + for node in self.nodes: + print('{} interferes: {}'.format(node, node.Adjecent)) + + def getNode(self, tmp): + # Linear search + # TODO: can be improved for speed! + for n in self.nodes: + if tmp in n.temps: + return n + n = InterferenceGraphNode(self, tmp) + self.addNode(n) + return n + + def Combine(self, n, m): + """ Combine n and m into n """ + n.temps.extend(m.temps) + n.moves.update(m.moves) + # Reroute all edges: + e1 = [e for e in self.edges if e[0] is m] + e2 = [e for e in self.edges if e[1] is m] + for e in e1: + self.edges.remove(e) + self.addEdge(n, e[1]) + for e in e2: + self.edges.remove(e) + self.addEdge(n, e[0]) + # Remove node m: + self.delNode(m)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/codegen/registerallocator.py Sun Dec 01 13:36:58 2013 +0100 @@ -0,0 +1,200 @@ +from .flowgraph import FlowGraph +from .interferencegraph import InterferenceGraph + +# Nifty first function: +first = lambda x: next(iter(x)) + +class RegisterAllocator: + """ + Target independent register allocator. + + Algorithm is iterated register coalescing by Appel and George. + + Chaitin's algorithm: remove all nodes with less than K neighbours. + These nodes can be colored when added back. + + The process consists of the following steps: + - build interference graph from the instruction list + - remove low degree non move related nodes. + - (optional) coalesc registers to remove redundant moves + - (optional) spill registers + - select registers + """ + + def InitData(self, f): + self.f = f + # Register information: + self.regs = set(f.regs) + self.K = len(self.regs) + + # Move related sets: + self.coalescedMoves = set() + self.constrainedMoves = set() + self.frozenMoves = set() + self.activeMoves = set() + self.worklistMoves = set() + + def printLive(self): + print('Liveness:') + for i in self.f.instructions: + cfgn = self.f.cfg._map[i] + print(i, cfgn.live_in) + + def Build(self): + """ 1. Construct interference graph from instruction list """ + self.f.cfg = FlowGraph(self.f.instructions) + self.f.ig = InterferenceGraph(self.f.cfg) + + self.Node = self.f.ig.getNode + + # Divide nodes into pre-colored and initial: + pre_tmp = list(self.f.tempMap.keys()) + self.precolored = set(self.Node(tmp) for tmp in pre_tmp) + self.workSet = set(self.f.ig.nodes - self.precolored) + + for n in self.precolored: + n.addDegree = 100 + len(self.f.ig.nodes) + self.K + + # Initialize color map: + self.color = {} + for tmp, c in self.f.tempMap.items(): + self.color[self.Node(tmp)] = c + + self.moves = [i for i in self.f.instructions if i.ismove] + for mv in self.moves: + self.Node(mv.src[0]).moves.add(mv) + self.Node(mv.dst[0]).moves.add(mv) + + def NodeMoves(self, n): + return n.moves & (self.activeMoves | self.worklistMoves) + + def MoveRelated(self, n): + return bool(self.NodeMoves(n)) + + @property + def SpillWorkSet(self): + c = lambda n: n.Degree >= self.K + return set(filter(c, self.workSet)) + + @property + def FreezeWorkSet(self): + c = lambda n: n.Degree < self.K and self.MoveRelated(n) + return set(filter(c, self.workSet)) + + @property + def SimplifyWorkSet(self): + c = lambda n: n.Degree < self.K and not self.MoveRelated(n) + return set(filter(c, self.workSet)) + + def makeWorkList(self): + """ Divide initial nodes into worklists """ + self.selectStack = [] + + # Fill initial move set: + for m in self.moves: + self.worklistMoves.add(m) + + def Simplify(self): + """ 2. Remove nodes from the graph """ + n = first(self.SimplifyWorkSet) + self.workSet.remove(n) + self.selectStack.append(n) + # Pop out of graph: + self.f.ig.delNode(n) + + def EnableMoves(self, nodes): + for n in nodes: + for m in self.NodeMoves(n): + if m in self.activeMoves: + self.activeMoves.remove(m) + self.worklistMoves.add(m) + + def Coalesc(self): + """ Coalesc conservative. """ + m = first(self.worklistMoves) + x = self.Node(m.dst[0]) + y = self.Node(m.src[0]) + u, v = (y, x) if y in self.precolored else (x, y) + self.worklistMoves.remove(m) + if u is v: + self.coalescedMoves.add(m) + elif v in self.precolored or self.f.ig.hasEdge(u, v): + self.constrainedMoves.add(m) + elif u not in self.precolored and self.Conservative(u, v): + self.coalescedMoves.add(m) + self.workSet.remove(v) + self.f.ig.Combine(u, v) + else: + self.activeMoves.add(m) + + def Conservative(self, u, v): + """ Briggs conservative criteria for coalesc """ + nodes = u.Adjecent | v.Adjecent + c = lambda n: n.Degree >= self.K + k = len(list(filter(c, nodes))) + return k < self.K + + def Freeze(self): + """ Give up coalescing on some node """ + u = first(self.FreezeWorkSet) + self.freezeMoves(u) + + def freezeMoves(self, u): + """ Freeze moves for node u """ + for m in self.NodeMoves(u): + if m in self.activeMoves: + self.activeMoves.remove(m) + else: + sekf.worklistMoves.remove(m) + self.frozenMoves.add(m) + # Check other part of the move for still being move related: + v = m.src[0] if u is m.dst[0] else m.dst[0] + + def SelectSpill(self): + # TODO + pass + + def AssignColors(self): + """ Add nodes back to the graph to color it. """ + # Add nodes back to the graph: + while self.selectStack: + n = self.selectStack.pop(-1) + self.f.ig.addNode(n) + takenregs = set(self.color[m] for m in n.Adjecent) + okColors = self.regs - takenregs + if okColors: + self.color[n] = first(okColors) + n.color = self.color[n] + else: + raise NotImplementedError('Spill required here!') + + def ApplyColors(self): + # Remove coalesced moves: + for mv in self.coalescedMoves: + self.f.instructions.remove(mv) + + # Use allocated registers: + lookup = lambda t: self.color[self.Node(t)] + for i in self.f.instructions: + i.src = tuple(map(lookup, i.src)) + i.dst = tuple(map(lookup, i.dst)) + + def allocFrame(self, f): + """ Do iterated register allocation for a single stack frame. """ + self.InitData(f) + self.Build() + self.makeWorkList() + while True: + if self.SimplifyWorkSet: + self.Simplify() + elif self.worklistMoves: + self.Coalesc() + elif self.FreezeWorkSet: + self.Freeze() + elif self.SpillWorkSet: + raise NotImplementedError('Spill not implemented') + else: + break # Done! + self.AssignColors() + self.ApplyColors() +
--- a/python/dag.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,59 +0,0 @@ - -# Instruction selection with DAG (Directed Acyclic Graph) -class DagLeaf: - def __init__(self, v): - self.v = v - -class DagNode: - def __init__(self, name): - self.name = name - self.children = [] - def __repr__(self): - return str(self.name) - -class Dag: - def __init__(self, bb): - self.mapping = {} - self.buildFromBB(bb) - - def buildFromBB(self, bb): - for ins in bb.Instructions: - if type(ins) is ir.BinaryOperator: - if not ins.value1 in self.mapping: - self.mapping[ins.value1] = DagNode(ins.value1) - if not ins.value2 in self.mapping: - self.mapping[ins.value2] = DagNode(ins.value2) - # look for op with left and right operand the same: - N = None - lnode = self.mapping[ins.value1] - rnode = self.mapping[ins.value2] - for node in self.mapping.values(): - if node.name == ins.operation: - if node.children[0] == lnode and node.children[1] == rnode: - N = node - break - if not N: - # Create a node. - N = DagNode(ins.operation) - N.children.append(lnode) - N.children.append(rnode) - self.mapping[ins.result] = N - else: - pass - - def dumpgv(self, outf): - outf.write('subgraph {0} {{\n'.format(id(self))) - for node in self.mapping.values(): - outf.write('{0} [label="{1}"];\n'.format(id(node), node.name)) - for c in node.children: - outf.write('{0} -> {1};\n'.format(id(node), id(c))) - outf.write('label="dag"}\n') - -def insSelect(mod): - """ Create DAG from ir-code """ - for bb in mod.BasicBlocks: - print(bb) - dag = Dag(bb) - print(dag.mapping) - bb.dag = dag -
--- a/python/flowgraph.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -import graph - - -class FlowGraphNode(graph.DiNode): - """ A node in the flow graph """ - def __init__(self, g, ins): - super().__init__(g) - self.ins = ins - self.uses = set(ins.src) - self.defs = set(ins.dst) - self.live_in = set() - self.live_out = set() - - def __repr__(self): - r = '{}'.format(self.ins) - if self.uses: - r += ' uses:' + ', '.join(str(u) for u in self.uses) - if self.defs: - r += ' defs:' + ', '.join(str(d) for d in self.defs) - return r - - -class FlowGraph(graph.DiGraph): - def __init__(self, instrs): - """ Create a flowgraph from a list of abstract instructions """ - super().__init__() - self._map = {} - # Add nodes: - for ins in instrs: - n = FlowGraphNode(self, ins) - self._map[ins] = n - self.addNode(n) - - # Make edges: - prev = None - for ins in instrs: - n = self._map[ins] - if prev: - self.addEdge(prev, n) - if ins.jumps: - prev = None - for j in ins.jumps: - to_n = self._map[j] - self.addEdge(n, to_n) - else: - prev = n - -
--- a/python/graph.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,85 +0,0 @@ - -class Graph: - """ - Generic graph base class. - Can dump to graphiz dot format for example! - """ - def __init__(self): - self.nodes = set() - self.edges = set() - - def addNode(self, n): - self.nodes.add(n) - - def delNode(self, n): - self.nodes.remove(n) - - def addEdge(self, n, m): - """ Add an edge from n to m """ - self.edges.add((n, m)) - self.edges.add((m, n)) - - def hasEdge(self, n, m): - return (n, m) in self.edges - - def delEdge(self, n, m): - self.edges.remove((n, m)) - self.edges.remove((m, n)) - - def adjecent(self, n): - """ Return all nodes with edges to n """ - # TODO: this can be optimized for speed: - return set(m for m in self.nodes if self.hasEdge(n, m)) - - def to_dot(self, f): - """ Generate graphviz dot representation """ - for node in self.nodes: - print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) - for n, m in self.edges: - print('{} -> {};'.format(id(n), id(m)), file=f) - - -class Node: - """ - Node in a graph. - """ - def __init__(self, g): - self.g = g - self.addDegree = 0 # Hack to increase degree - - @property - def Adjecent(self): - return self.g.adjecent(self) - - @property - def Degree(self): - return len(self.Adjecent) + self.addDegree - - -class DiGraph(Graph): - """ - Directed graph. - """ - def addEdge(self, n, m): - """ Add an edge from n to m """ - self.edges.add((n, m)) - - def hasEdge(self, n, m): - return (n, m) in self.edges - - def successors(self, n): - return set(m for m in self.nodes if self.hasEdge(n, m)) - - def predecessors(self, n): - return set(m for m in self.nodes if self.hasEdge(m, n)) - - -class DiNode(Node): - @property - def Succ(self): - return self.g.successors(self) - - @property - def Pred(self): - return self.g.predecessors(self) -
--- a/python/interferencegraph.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,92 +0,0 @@ -import graph - - -class InterferenceGraphNode(graph.Node): - def __init__(self, g, varname): - super().__init__(g) - self.temps = [varname] - self.moves = set() - self.color = None - - def __repr__(self): - return '{}({})'.format(self.temps, self.color) - - -class InterferenceGraph(graph.Graph): - """ - Interference graph. - """ - def __init__(self, flowgraph): - """ - Create a new interference graph from a flowgraph - """ - super().__init__() - # Calculate liveness in CFG: - ### - # Liveness: - # in[n] = use[n] UNION (out[n] - def[n]) - # out[n] = for s in n.succ in union in[s] - ### - for n in flowgraph.nodes: - n.live_in = set() - n.live_out = set() - - # Dataflow fixed point iteration: - change = True - while change: - change = False - for n in flowgraph.nodes: - _in = n.live_in - _out = n.live_out - n.live_in = n.uses | (n.live_out - n.defs) - if n.Succ: - n.live_out = set.union(*(s.live_in for s in n.Succ)) - else: - n.live_out = set() - change = change or (_in != n.live_in) or (_out != n.live_out) - - # Construct interference graph: - for n in flowgraph.nodes: - for tmp in n.live_out: - n1 = self.getNode(tmp) - for tmp2 in (n.live_out - {tmp}): - n2 = self.getNode(tmp2) - self.addEdge(n1, n2) - - def to_dot(self, f): - """ Generate graphviz dot representation """ - for node in self.nodes: - print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) - for n, m in self.edges: - print('{} -> {};'.format(id(n), id(m)), file=f) - - def to_txt(self): - for node in self.nodes: - print('{} interferes: {}'.format(node, node.Adjecent)) - - def getNode(self, tmp): - # Linear search - # TODO: can be improved for speed! - for n in self.nodes: - if tmp in n.temps: - return n - n = InterferenceGraphNode(self, tmp) - self.addNode(n) - return n - - def Combine(self, n, m): - """ Combine n and m into n """ - n.temps.extend(m.temps) - n.moves.update(m.moves) - # Reroute all edges: - e1 = [e for e in self.edges if e[0] is m] - e2 = [e for e in self.edges if e[1] is m] - for e in e1: - self.edges.remove(e) - self.addEdge(n, e[1]) - for e in e2: - self.edges.remove(e) - self.addEdge(n, e[0]) - # Remove node m: - self.delNode(m) -
--- a/python/mem2reg.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/mem2reg.py Sun Dec 01 13:36:58 2013 +0100 @@ -68,4 +68,3 @@ for i in allocs: if isAllocPromotable(i): self.promote(i) -
--- a/python/outstream.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/outstream.py Sun Dec 01 13:36:58 2013 +0100 @@ -90,9 +90,11 @@ else: print(' 0x{0:08x} 0x{1} {2}'.format(addr, insword, asm)) + class TextOutputStream(OutputStream): pass + class BinOutputStream(OutputStream): @property @@ -105,5 +107,3 @@ self.backpatch() section = self.sections[list(self.sections.keys())[0]] return section.to_bytes() - -
--- a/python/ppci/errors.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/ppci/errors.py Sun Dec 01 13:36:58 2013 +0100 @@ -6,6 +6,7 @@ import logging from . import SourceLocation + class CompilerError(Exception): def __init__(self, msg, loc=None): self.msg = msg @@ -33,7 +34,7 @@ self.sources[name] = src def addDiag(self, d): - self.logger.warning(str(d.msg)) + #self.logger.warning(str(d.msg)) self.diags.append(d) def error(self, msg, loc):
--- a/python/registerallocator.py Thu Nov 28 21:10:32 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,200 +0,0 @@ -from flowgraph import FlowGraph -from interferencegraph import InterferenceGraph - -# Nifty first function: -first = lambda x: next(iter(x)) - -class RegisterAllocator: - """ - Target independent register allocator. - - Algorithm is iterated register coalescing by Appel and George. - - Chaitin's algorithm: remove all nodes with less than K neighbours. - These nodes can be colored when added back. - - The process consists of the following steps: - - build interference graph from the instruction list - - remove low degree non move related nodes. - - (optional) coalesc registers to remove redundant moves - - (optional) spill registers - - select registers - """ - - def InitData(self, f): - self.f = f - # Register information: - self.regs = set(f.regs) - self.K = len(self.regs) - - # Move related sets: - self.coalescedMoves = set() - self.constrainedMoves = set() - self.frozenMoves = set() - self.activeMoves = set() - self.worklistMoves = set() - - def printLive(self): - print('Liveness:') - for i in self.f.instructions: - cfgn = self.f.cfg._map[i] - print(i, cfgn.live_in) - - def Build(self): - """ 1. Construct interference graph from instruction list """ - self.f.cfg = FlowGraph(self.f.instructions) - self.f.ig = InterferenceGraph(self.f.cfg) - - self.Node = self.f.ig.getNode - - # Divide nodes into pre-colored and initial: - pre_tmp = list(self.f.tempMap.keys()) - self.precolored = set(self.Node(tmp) for tmp in pre_tmp) - self.workSet = set(self.f.ig.nodes - self.precolored) - - for n in self.precolored: - n.addDegree = 100 + len(self.f.ig.nodes) + self.K - - # Initialize color map: - self.color = {} - for tmp, c in self.f.tempMap.items(): - self.color[self.Node(tmp)] = c - - self.moves = [i for i in self.f.instructions if i.ismove] - for mv in self.moves: - self.Node(mv.src[0]).moves.add(mv) - self.Node(mv.dst[0]).moves.add(mv) - - def NodeMoves(self, n): - return n.moves & (self.activeMoves | self.worklistMoves) - - def MoveRelated(self, n): - return bool(self.NodeMoves(n)) - - @property - def SpillWorkSet(self): - c = lambda n: n.Degree >= self.K - return set(filter(c, self.workSet)) - - @property - def FreezeWorkSet(self): - c = lambda n: n.Degree < self.K and self.MoveRelated(n) - return set(filter(c, self.workSet)) - - @property - def SimplifyWorkSet(self): - c = lambda n: n.Degree < self.K and not self.MoveRelated(n) - return set(filter(c, self.workSet)) - - def makeWorkList(self): - """ Divide initial nodes into worklists """ - self.selectStack = [] - - # Fill initial move set: - for m in self.moves: - self.worklistMoves.add(m) - - def Simplify(self): - """ 2. Remove nodes from the graph """ - n = first(self.SimplifyWorkSet) - self.workSet.remove(n) - self.selectStack.append(n) - # Pop out of graph: - self.f.ig.delNode(n) - - def EnableMoves(self, nodes): - for n in nodes: - for m in self.NodeMoves(n): - if m in self.activeMoves: - self.activeMoves.remove(m) - self.worklistMoves.add(m) - - def Coalesc(self): - """ Coalesc conservative. """ - m = first(self.worklistMoves) - x = self.Node(m.dst[0]) - y = self.Node(m.src[0]) - u, v = (y, x) if y in self.precolored else (x, y) - self.worklistMoves.remove(m) - if u is v: - self.coalescedMoves.add(m) - elif v in self.precolored or self.f.ig.hasEdge(u, v): - self.constrainedMoves.add(m) - elif u not in self.precolored and self.Conservative(u, v): - self.coalescedMoves.add(m) - self.workSet.remove(v) - self.f.ig.Combine(u, v) - else: - self.activeMoves.add(m) - - def Conservative(self, u, v): - """ Briggs conservative criteria for coalesc """ - nodes = u.Adjecent | v.Adjecent - c = lambda n: n.Degree >= self.K - k = len(list(filter(c, nodes))) - return k < self.K - - def Freeze(self): - """ Give up coalescing on some node """ - u = first(self.FreezeWorkSet) - self.freezeMoves(u) - - def freezeMoves(self, u): - """ Freeze moves for node u """ - for m in self.NodeMoves(u): - if m in self.activeMoves: - self.activeMoves.remove(m) - else: - sekf.worklistMoves.remove(m) - self.frozenMoves.add(m) - # Check other part of the move for still being move related: - v = m.src[0] if u is m.dst[0] else m.dst[0] - - def SelectSpill(self): - # TODO - pass - - def AssignColors(self): - """ Add nodes back to the graph to color it. """ - # Add nodes back to the graph: - while self.selectStack: - n = self.selectStack.pop(-1) - self.f.ig.addNode(n) - takenregs = set(self.color[m] for m in n.Adjecent) - okColors = self.regs - takenregs - if okColors: - self.color[n] = first(okColors) - n.color = self.color[n] - else: - raise NotImplementedError('Spill required here!') - - def ApplyColors(self): - # Remove coalesced moves: - for mv in self.coalescedMoves: - self.f.instructions.remove(mv) - - # Use allocated registers: - lookup = lambda t: self.color[self.Node(t)] - for i in self.f.instructions: - i.src = tuple(map(lookup, i.src)) - i.dst = tuple(map(lookup, i.dst)) - - def allocFrame(self, f): - """ Do iterated register allocation for a single stack frame. """ - self.InitData(f) - self.Build() - self.makeWorkList() - while True: - if self.SimplifyWorkSet: - self.Simplify() - elif self.worklistMoves: - self.Coalesc() - elif self.FreezeWorkSet: - self.Freeze() - elif self.SpillWorkSet: - raise NotImplementedError('Spill not implemented') - else: - break # Done! - self.AssignColors() - self.ApplyColors() -
--- a/python/transform.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/transform.py Sun Dec 01 13:36:58 2013 +0100 @@ -140,6 +140,3 @@ pred.LastInstruction.changeTarget(b, tgt) logging.debug('Removing empty block: {}'.format(b)) f.removeBlock(b) - - -
--- a/python/zcc.py Thu Nov 28 21:10:32 2013 +0100 +++ b/python/zcc.py Sun Dec 01 13:36:58 2013 +0100 @@ -32,7 +32,7 @@ parser.add_argument('source', type=argparse.FileType('r'), \ help='the source file to build', nargs="+") parser.add_argument('-i', '--imp', type=argparse.FileType('r'), \ - help='Possible import module', action='append') + help='Possible import module', action='append', default=[]) parser.add_argument('--dumpir', action='store_true', help="Dump IR-code") parser.add_argument('--dumpasm', action='store_true', help="Dump ASM-code") @@ -80,15 +80,11 @@ def main(args): logging.basicConfig(format=logformat, level=args.log) - src = args.source - imps = args.imp - if not imps: - imps = [] tg = targets[args.target] diag = ppci.DiagnosticsManager() outs = outstream.TextOutputStream() - res = zcc(src, imps, tg, outs, diag, dumpir=args.dumpir) + res = zcc(args.source, args.imp, tg, outs, diag, dumpir=args.dumpir) if not res: diag.printErrors() return 1
--- a/test/runtests.sh Thu Nov 28 21:10:32 2013 +0100 +++ b/test/runtests.sh Sun Dec 01 13:36:58 2013 +0100 @@ -5,7 +5,7 @@ if [ $1 == "loop" ]; then DIR=.. while :; do - python -m unittest -v + python -m unittest cd gui #python -m unittest -v cd ..
--- a/test/testgraph.py Thu Nov 28 21:10:32 2013 +0100 +++ b/test/testgraph.py Sun Dec 01 13:36:58 2013 +0100 @@ -1,9 +1,9 @@ #!/usr/bin/python import unittest -import graph -import interferencegraph -import flowgraph +from codegen.graph import Graph, Node +from codegen.interferencegraph import InterferenceGraph +from codegen.flowgraph import FlowGraph import ir from irmach import AbstractInstruction as AI from target import Nop @@ -11,10 +11,10 @@ class GraphTestCase(unittest.TestCase): def testEdge(self): - g = graph.Graph() - n1 = graph.Node(g) + g = Graph() + n1 = Node(g) g.addNode(n1) - n2 = graph.Node(g) + n2 = Node(g) g.addNode(n2) g.addEdge(n1, n2) self.assertTrue(g.hasEdge(n2, n1)) @@ -23,12 +23,12 @@ g.delNode(n2) def testDegree(self): - g = graph.Graph() - n1 = graph.Node(g) + g = Graph() + n1 = Node(g) g.addNode(n1) - n2 = graph.Node(g) + n2 = Node(g) g.addNode(n2) - n3 = graph.Node(g) + n3 = Node(g) g.addNode(n3) g.addEdge(n1, n2) g.addEdge(n1, n3) @@ -54,8 +54,8 @@ 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) + cfg = FlowGraph(instrs) + ig = InterferenceGraph(cfg) def testCombine(self): t1 = ir.Temp('t1') @@ -70,8 +70,8 @@ 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) + cfg = FlowGraph(instrs) + ig = InterferenceGraph(cfg) ig.Combine(ig.getNode(t4), ig.getNode(t3)) self.assertIs(ig.getNode(t4), ig.getNode(t3))
--- a/test/testregalloc.py Thu Nov 28 21:10:32 2013 +0100 +++ b/test/testregalloc.py Sun Dec 01 13:36:58 2013 +0100 @@ -2,14 +2,14 @@ import os import sys from irmach import AbstractInstruction as makeIns, Frame -import registerallocator +from codegen.registerallocator import RegisterAllocator import ir from target import Nop class RegAllocTestCase(unittest.TestCase): def setUp(self): - self.ra = registerallocator.RegisterAllocator() + self.ra = RegisterAllocator() def testRegAlloc(self): f = Frame('tst')