# HG changeset patch # User Windel Bouwman # Date 1386259358 -3600 # Node ID 6753763d3bec83e2af46c07227c53783ddf7c1c8 # Parent 158068af716c67c47fabfe0dfc77b65fb267dfa3 merge codegen into ppci package diff -r 158068af716c -r 6753763d3bec doc/compiler.rst --- a/doc/compiler.rst Tue Dec 03 18:00:22 2013 +0100 +++ b/doc/compiler.rst Thu Dec 05 17:02:38 2013 +0100 @@ -62,11 +62,11 @@ 40 -> 99 } -.. autoclass:: c3.Builder +.. autoclass:: ppci.c3.Builder -.. autoclass:: c3.Parser +.. autoclass:: ppci.c3.Parser -.. autoclass:: c3.CodeGenerator +.. autoclass:: ppci.c3.CodeGenerator Back-end -------- diff -r 158068af716c -r 6753763d3bec kernel/kernel.c3 --- a/kernel/kernel.c3 Tue Dec 03 18:00:22 2013 +0100 +++ b/kernel/kernel.c3 Thu Dec 05 17:02:38 2013 +0100 @@ -9,7 +9,7 @@ function void start() { process:init(); - memory:init(); + //memory:init(); //Process proc = new process:Process(); diff -r 158068af716c -r 6753763d3bec kernel/memory.c3 --- a/kernel/memory.c3 Tue Dec 03 18:00:22 2013 +0100 +++ b/kernel/memory.c3 Thu Dec 05 17:02:38 2013 +0100 @@ -2,12 +2,12 @@ import process; -var u8* ptr; +var int ptr; function u8* Alloc(int size) { ptr = ptr + size; - return ptr; + return cast(ptr); } diff -r 158068af716c -r 6753763d3bec kernel/process.c3 --- a/kernel/process.c3 Tue Dec 03 18:00:22 2013 +0100 +++ b/kernel/process.c3 Thu Dec 05 17:02:38 2013 +0100 @@ -27,7 +27,8 @@ */ function process_t* Create() { - // process_t* p = memory.Alloc(sizeof(process_t)); + var process_t* p; + //= memory.Alloc(sizeof(process_t)); p->id = next_pid; next_pid = next_pid + 1; return p; diff -r 158068af716c -r 6753763d3bec kernel/schedule.c3 --- a/kernel/schedule.c3 Tue Dec 03 18:00:22 2013 +0100 +++ b/kernel/schedule.c3 Thu Dec 05 17:02:38 2013 +0100 @@ -1,13 +1,17 @@ module scheduler; +import process; + +var process:process_t *current; + function void executeNext() { - process_t *old; + var process:process_t *old; if (old != current) { - execute(current); + //execute(current); } } diff -r 158068af716c -r 6753763d3bec kernel/syscall.c3 --- a/kernel/syscall.c3 Tue Dec 03 18:00:22 2013 +0100 +++ b/kernel/syscall.c3 Thu Dec 05 17:02:38 2013 +0100 @@ -4,61 +4,59 @@ This module handles all the system calls from user space. */ -/* -enum { - SendMsg = 1, - ReceiveMsg = 2, +import arch; +import scheduler; +import process; + -} syscall_t; -*/ +const int SendMsg = 1; +const int ReceiveMsg = 2; +const int Reboot = 3; -type int syscall_t; // System call handlers. System calls are made from user space. function void handle_system_call(int callId, int a, int b, int c, int d) { // Main entry, check what to do here - switch(callId) + if (callId == 1) + { + handle_send_msg(); + var process:process_t* proc; + proc = process:byId(a); + // proc.setMessage(); + // scheduler.current.setState(Sleep); + } + else { - case SendMsg: - handle_send_msg(); - proc = process.byId(a); - if (not proc) + if (callId == 2) + { + handle_recv_msg(); + } + else + { + if (callId == 3) { - panic(); + //arch:reboot(); } - - proc.setMessage(); - // scheduler.current.setState(Sleep); - break; - case ReceiveMsg: - break; - case Reboot: - arch.reboot(); - break; - default: - return NO_SUCH_CALL; + else + { + return 2; + } + } } - return OK; + return 0; } // Handle send message syscall -func void handle_send_msg() +function void handle_send_msg() { - p = process.byId(msg.to_id); - scheduler.attempt(p); } -func handle_recv_msg() +function void handle_recv_msg() { // Block until we have a message - currentProc->setState(Sleep); - scheduler.executeNext(); + //currentProc->setState(Sleep); + //scheduler:executeNext(); } -func handle_reboot() -{ - reboot(); -} - diff -r 158068af716c -r 6753763d3bec python/codegen/__init__.py --- a/python/codegen/__init__.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -from .codegen import CodeGenerator diff -r 158068af716c -r 6753763d3bec python/codegen/canon.py --- a/python/codegen/canon.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,129 +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)) diff -r 158068af716c -r 6753763d3bec python/codegen/codegen.py --- a/python/codegen/codegen.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -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 diff -r 158068af716c -r 6753763d3bec python/codegen/dag.py --- a/python/codegen/dag.py Tue Dec 03 18:00:22 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 - diff -r 158068af716c -r 6753763d3bec python/codegen/flowgraph.py --- a/python/codegen/flowgraph.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -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 diff -r 158068af716c -r 6753763d3bec python/codegen/graph.py --- a/python/codegen/graph.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,84 +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 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) diff -r 158068af716c -r 6753763d3bec python/codegen/interferencegraph.py --- a/python/codegen/interferencegraph.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -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) diff -r 158068af716c -r 6753763d3bec python/codegen/registerallocator.py --- a/python/codegen/registerallocator.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,201 +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() - diff -r 158068af716c -r 6753763d3bec python/ir.py --- a/python/ir.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,477 +0,0 @@ -""" -Intermediate representation (IR) code classes. -""" - - -def dumpgv(m, outf): - print('digraph G ', file=outf) - print('{', file=outf) - for f in m.Functions: - print('{} [label="{}" shape=box3d]'.format(id(f), f),file=outf) - for bb in f.Blocks: - contents = str(bb) + '\n' - contents += '\n'.join([str(i) for i in bb.Instructions]) - outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents)) - for successor in bb.Successors: - print('"{}" -> "{}"\n'.format(id(bb), id(successor)), file=outf) - - outf.write('"{}" -> "{}" [label="entry"]\n'.format(id(f), id(f.entry))) - print('}', file=outf) - - -class Module: - """ Main container of variables and functions. """ - def __init__(self, name): - self.name = name - self.funcs = [] - self.variables = [] - - def __repr__(self): - return 'IR-module [{0}]'.format(self.name) - - def addFunc(self, f): - self.funcs.append(f) - - addFunction = addFunc - - def addVariable(self, v): - self.variables.append(v) - - def getVariables(self): - return self.variables - - Variables = property(getVariables) - - def getFunctions(self): - return self.funcs - - Functions = property(getFunctions) - - def findFunction(self, name): - for f in self.funcs: - if f.name == name: - return f - raise KeyError(name) - - getFunction = findFunction - - def dump(self, indent=' '): - print(self) - for v in self.Variables: - print(indent, v) - for fn in self.Functions: - fn.dump(indent=indent+' ') - - # Analysis functions: - def check(self): - """ Perform sanity check on module """ - for f in self.Functions: - f.check() - - -class Function: - """ - Function definition. Contains an entry block. - """ - def __init__(self, name): - self.name = name - self.entry = Block('{}_entry'.format(name)) - self.entry.function = self - self.epiloog = Block('{}_epilog'.format(name)) - self.epiloog.function = self - self.epiloog.addInstruction(Terminator()) - self.return_value = Temp('{}_retval'.format(name)) - self.arguments = [] - self.localvars = [] - - def __repr__(self): - args = ','.join(str(a) for a in self.arguments) - return 'Function {}({})'.format(self.name, args) - - def addBlock(self, bb): - self.bbs.append(bb) - bb.function = self - - def removeBlock(self, bb): - #self.bbs.remove(bb) - bb.function = None - - def getBlocks(self): - 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) - bbs.remove(self.entry) - if self.epiloog in bbs: - bbs.remove(self.epiloog) - bbs.insert(0, self.entry) - bbs.append(self.epiloog) - return bbs - - def findBasicBlock(self, name): - for bb in self.bbs: - if bb.name == name: - return bb - raise KeyError(name) - - Blocks = property(getBlocks) - - @property - def Entry(self): - return self.entry - - def check(self): - for b in self.Blocks: - b.check() - - def addParameter(self, p): - assert type(p) is Parameter - p.num = len(self.arguments) - self.arguments.append(p) - - def addLocal(self, l): - assert type(l) is LocalVariable - self.localvars.append(l) - - def dump(self, indent=''): - print(indent+str(self)) - for bb in self.Blocks: - print(indent+' '+str(bb)) - for ins in bb.Instructions: - print(indent +' '*2 + str(ins)) - - -class Block: - """ - Uninterrupted sequence of instructions with a label at the start. - """ - def __init__(self, name): - self.name = name - self.function = None - self.instructions = [] - - parent = property(lambda s: s.function) - - def __repr__(self): - return 'Block {0}'.format(self.name) - - def addInstruction(self, i): - i.parent = self - assert not isinstance(self.LastInstruction, LastStatement) - self.instructions.append(i) - - 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): - i.parent = None - i.delete() - self.instructions.remove(i) - - @property - def Instructions(self): - return self.instructions - - @property - def LastInstruction(self): - if not self.Empty: - return self.instructions[-1] - - @property - def Empty(self): - return len(self.instructions) == 0 - - @property - def FirstInstruction(self): - return self.instructions[0] - - def getSuccessors(self): - if not self.Empty: - return self.LastInstruction.Targets - return [] - Successors = property(getSuccessors) - - def getPredecessors(self): - preds = [] - for bb in self.parent.Blocks: - if self in bb.Successors: - preds.append(bb) - return preds - Predecessors = property(getPredecessors) - - def precedes(self, other): - raise NotImplementedError() - - def check(self): - assert isinstance(self.LastInstruction, LastStatement) - for i in self.instructions[:-1]: - assert not isinstance(i, LastStatement) - - -# Instructions: -class Term: - def __init__(self, x): - self.x = x - -def match_tree(tree, pattern): - if type(pattern) is Term: - return True, {pattern: tree} - elif type(pattern) is Binop and type(tree) is Binop and tree.operation == pattern.operation: - res_a, mp_a = match_tree(tree.a, pattern.a) - res_b, mp_b = match_tree(tree.b, pattern.b) - assert not (mp_a.keys() & mp_b.keys()) - mp_a.update(mp_b) - return res_a and res_b, mp_a - elif type(pattern) is Const and type(tree) is Const and pattern.value == tree.value: - return True, {} - else: - return False, {} - - -class Expression: - pass - - -class Const(Expression): - def __init__(self, value): - self.value = value - - def __repr__(self): - return 'Const {}'.format(self.value) - - -# Function calling: -class Call(Expression): - def __init__(self, f, arguments): - self.f = f - assert type(f) is Function - self.arguments = arguments - - def __repr__(self): - args = ', '.join([str(arg) for arg in self.arguments]) - return '{}({})'.format(self.f.name, args) - - -# Data operations -class Binop(Expression): - ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] - def __init__(self, value1, operation, value2): - assert operation in Binop.ops - self.a = value1 - self.b = value2 - self.operation = operation - - def __repr__(self): - a, b = self.a, self.b - return '({} {} {})'.format(a, self.operation, b) - - -def Add(a, b): - """ Convenience call """ - return Binop(a, '+', b) - - -def Sub(a, b): - return Binop(a, '-', b) - - -def Mul(a, b): - return Binop(a, '*', b) - - -def Div(a, b): - return Binop(a, '/', b) - -class Eseq(Expression): - """ Sequence of instructions where the last is an expression """ - def __init__(self, stmt, e): - self.stmt = stmt - self.e = e - - def __repr__(self): - return '({}, {})'.format(self.stmt, self.e) - - -class Alloc(Expression): - """ Allocates space on the stack """ - def __init__(self): - super().__init__() - - def __repr__(self): - return 'Alloc' - - -class Variable(Expression): - def __init__(self, name): - self.name = name - - def __repr__(self): - return 'Var {}'.format(self.name) - - -class LocalVariable(Variable): - def __repr__(self): - return 'Local {}'.format(self.name) - - -class Parameter(Variable): - def __repr__(self): - return 'Param {}'.format(self.name) - - -class Temp(Expression): - """ Temporary storage, same as register """ - def __init__(self, name): - self.name = name - - def __repr__(self): - return 'TMP_{}'.format(self.name) - - -class Mem(Expression): - def __init__(self, e): - self.e = e - - def __repr__(self): - return '[{}]'.format(self.e) - - -class Statement: - """ Base class for all instructions. """ - pass - - -class Move(Statement): - def __init__(self, dst, src): - self.dst = dst - self.src = src - - def __repr__(self): - return '{} = {}'.format(self.dst, self.src) - - -class Exp(Statement): - def __init__(self, e): - self.e = e - - def __repr__(self): - return '{}'.format(self.e) - - -# Branching: -class LastStatement(Statement): - def changeTarget(self, old, new): - idx = self.Targets.index(old) - self.Targets[idx] = new - - -class Terminator(LastStatement): - """ Instruction that terminates the terminal block """ - def __init__(self): - self.Targets = [] - - def __repr__(self): - return 'Terminator' - - -class Jump(LastStatement): - def __init__(self, target): - self.Targets = [target] - - def setTarget(self, t): - self.Targets[0] = t - target = property(lambda s: s.Targets[0], setTarget) - - def __repr__(self): - return 'JUMP {}'.format(self.target.name) - - -class CJump(LastStatement): - conditions = ['==', '<', '>', '>=', '<=', '!='] - def __init__(self, a, cond, b, lab_yes, lab_no): - assert cond in CJump.conditions - self.a = a - self.cond = cond - self.b = b - self.Targets = [lab_yes, lab_no] - - lab_yes = property(lambda s: s.Targets[0]) - lab_no = property(lambda s: s.Targets[1]) - - def __repr__(self): - return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) - - -# Constructing IR: - -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 self.cls('{0}{1}'.format(prefix, self.nums.__next__())) - - -class Builder: - """ Base class for ir code generators """ - def __init__(self): - self.prepare() - - def prepare(self): - self.newTemp = NamedClassGenerator('reg', Temp).gen - self.newBlock2 = NamedClassGenerator('block', Block).gen - self.bb = None - self.m = None - self.fn = None - self.loc = None - - # Helpers: - def setModule(self, m): - self.m = m - - def newFunction(self, name): - f = Function(name) - self.m.addFunc(f) - return f - - def newBlock(self): - assert self.fn - b = self.newBlock2() - b.function = self.fn - return b - - def setFunction(self, f): - self.fn = f - self.bb = f.entry if f else None - - def setBlock(self, b): - self.bb = b - - def setLoc(self, l): - self.loc = l - - def emit(self, i): - assert isinstance(i, Statement) - i.debugLoc = self.loc - if not self.bb: - raise Exception('No basic block') - self.bb.addInstruction(i) - - diff -r 158068af716c -r 6753763d3bec python/irmach.py --- a/python/irmach.py Tue Dec 03 18:00:22 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ - -""" - Abstract assembly language instructions. - - This is the second intermediate representation. - - Instructions are selected and scheduled at this stage. -""" - -from target import Instruction - - -class Frame: - """ - Activation record abstraction. This class contains a flattened - function. Instructions are selected and scheduled at this stage. - Frames differ per machine. - """ - def __init__(self, name): - self.name = name - self.instructions = [] - self.stacksize = 0 - - def __repr__(self): - return 'Frame {}'.format(self.name) - - def lower_to(self, outs): - for im in self.instructions: - if isinstance(im.assem, Instruction): - outs.emit(im.assem) - else: - outs.emit(im.assem.fromim(im)) - - -class AbstractInstruction: - """ - Abstract machine instruction class. This is a very simple - abstraction of machine instructions. - """ - def __init__(self, cls, ops=(), src=(), dst=(), jumps=(), others=(), ismove=False): - assert type(cls) is type or isinstance(cls, Instruction) - self.assem = cls - self.ops = tuple(ops) - self.src = tuple(src) - self.dst = tuple(dst) - self.jumps = tuple(jumps) - self.others = tuple(others) - self.ismove = ismove - - def __repr__(self): - return self.render() - - def render(self): - """ - Substitutes source, dst and labels in the string - """ - x = str(self.assem) - for i, s in enumerate(self.src): - p = '%s{}'.format(i) - x = x.replace(p, str(s)) - for i, d in enumerate(self.dst): - p = '%d{}'.format(i) - x = x.replace(p, str(d)) - for i, j in enumerate(self.jumps): - p = '%l{}'.format(i) - x = x.replace(p, str(j)) - return x - - -makeIns = AbstractInstruction diff -r 158068af716c -r 6753763d3bec python/ppci/c3/analyse.py --- a/python/ppci/c3/analyse.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/c3/analyse.py Thu Dec 05 17:02:38 2013 +0100 @@ -80,12 +80,14 @@ continue ip = packageDict[i] pkg.scope.addSymbol(ip) - FixRefs(self.diag).fixRefs(pkg) - return self.ok + fr = FixRefs(self.diag) + fr.fixRefs(pkg) + return self.ok and fr.ok class FixRefs(C3Pass): def fixRefs(self, pkg): + self.ok = True self.logger.info('Resolving references for {}'.format(pkg.name)) self.visitor.visit(pkg, self.findRefs) @@ -236,11 +238,8 @@ sym.typ = sym.proc.typ.returntype elif type(sym) is VariableUse: sym.lvalue = True - if isinstance(sym.target, Variable): - sym.typ = sym.target.typ - else: - print('warning {} has no target, defaulting to int'.format(sym)) - sym.typ = intType + assert isinstance(sym.target, Variable), sym.target + sym.typ = sym.target.typ elif type(sym) is Literal: sym.lvalue = False if type(sym.val) is int: diff -r 158068af716c -r 6753763d3bec python/ppci/c3/astnodes.py --- a/python/ppci/c3/astnodes.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/c3/astnodes.py Thu Dec 05 17:02:38 2013 +0100 @@ -27,9 +27,9 @@ # Modules -class Package(Node): +class Package(Symbol): def __init__(self, name, loc): - self.name = name + super().__init__(name) self.loc = loc self.declarations = [] self.imports = [] diff -r 158068af716c -r 6753763d3bec python/ppci/c3/builder.py --- a/python/ppci/c3/builder.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/c3/builder.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,5 +1,4 @@ import logging -import ppci from .parser import Parser from .analyse import TypeChecker, Analyzer from .codegenerator import CodeGenerator @@ -11,7 +10,7 @@ Generates IR-code from c3 source. Reports errors to the diagnostics system. """ - def __init__(self, diag): + def __init__(self, diag, target): self.logger = logging.getLogger('c3') self.diag = diag self.parser = Parser(diag) @@ -58,7 +57,7 @@ def build(self, srcs, imps=[]): """ Create IR-code from sources """ - self.logger.info('Starting build with {}'.format(srcs)) + self.logger.info('Starting build with {} source files'.format(len(srcs))) self.ok = True for pkg in self.checkSource(srcs, imps): # Only return ircode when everything is OK diff -r 158068af716c -r 6753763d3bec python/ppci/c3/codegenerator.py --- a/python/ppci/c3/codegenerator.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/c3/codegenerator.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,5 +1,5 @@ import logging -import ir +from .. import ir from . import astnodes from .scope import boolType, intType from ppci import CompilerError diff -r 158068af716c -r 6753763d3bec python/ppci/c3/parser.py --- a/python/ppci/c3/parser.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/c3/parser.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,4 +1,5 @@ import logging +from ppci import CompilerError from .lexer import Lexer from .astnodes import FieldRef, Literal, TypeCast, Unop, Binop from .astnodes import Assignment, ExpressionStatement, CompoundStatement @@ -9,7 +10,6 @@ from .astnodes import StructField, Deref from .astnodes import Package, ImportDesignator from .astnodes import Designator, VariableUse, FunctionCall -from ppci import CompilerError class Parser: @@ -96,7 +96,7 @@ self.Error('Expected function, var, const or type') def parseDesignator(self): - """ A designator designates an object """ + """ A designator designates an object with a name. """ name = self.Consume('ID') if self.hasConsumed(':'): name2 = self.Consume('ID') @@ -107,7 +107,6 @@ # Type system def parseTypeSpec(self): # For now, do simple type spec, just parse an ID: - #return self.parseDesignator() if self.Peak == 'struct': self.Consume('struct') self.Consume('{') @@ -368,27 +367,28 @@ def PostFixExpression(self): pfe = self.PrimaryExpression() - while self.Peak in ['[', '(', '.', '->']: - if self.hasConsumed('['): - pass - elif self.hasConsumed('('): - # Function call - args = [] - if not self.hasConsumed(')'): + if self.hasConsumed('('): + # Function call + args = [] + if not self.hasConsumed(')'): + args.append(self.Expression()) + while self.hasConsumed(','): args.append(self.Expression()) - while self.hasConsumed(','): - args.append(self.Expression()) - self.Consume(')') - pfe = FunctionCall(pfe, args, pfe.loc) - elif self.hasConsumed('->'): - field = self.Consume('ID') - pfe = Deref(pfe, pfe.loc) - pfe = FieldRef(pfe, field.val, field.loc) - elif self.hasConsumed('.'): - field = self.Consume('ID') - pfe = FieldRef(pfe, field.val, field.loc) - else: - raise Exception() + self.Consume(')') + pfe = FunctionCall(pfe, args, pfe.loc) + else: + while self.Peak in ['[', '.', '->']: + if self.hasConsumed('['): + raise NotImplementedError('Array not yet implemented') + elif self.hasConsumed('->'): + field = self.Consume('ID') + pfe = Deref(pfe, pfe.loc) + pfe = FieldRef(pfe, field.val, field.loc) + elif self.hasConsumed('.'): + field = self.Consume('ID') + pfe = FieldRef(pfe, field.val, field.loc) + else: + raise Exception() return pfe def PrimaryExpression(self): diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/__init__.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/__init__.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,1 @@ +from .codegen import CodeGenerator diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/canon.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/canon.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,129 @@ +from .. 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)) diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/codegen.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/codegen.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,48 @@ +from ..ir import Module +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, 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 diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/dag.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/dag.py Thu Dec 05 17:02:38 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 + diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/flowgraph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/flowgraph.py Thu Dec 05 17:02:38 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 diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/graph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/graph.py Thu Dec 05 17:02:38 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) diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/interferencegraph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/interferencegraph.py Thu Dec 05 17:02:38 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) diff -r 158068af716c -r 6753763d3bec python/ppci/codegen/registerallocator.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/codegen/registerallocator.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,201 @@ +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() + diff -r 158068af716c -r 6753763d3bec python/ppci/ir.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/ir.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,477 @@ +""" +Intermediate representation (IR) code classes. +""" + + +def dumpgv(m, outf): + print('digraph G ', file=outf) + print('{', file=outf) + for f in m.Functions: + print('{} [label="{}" shape=box3d]'.format(id(f), f),file=outf) + for bb in f.Blocks: + contents = str(bb) + '\n' + contents += '\n'.join([str(i) for i in bb.Instructions]) + outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents)) + for successor in bb.Successors: + print('"{}" -> "{}"\n'.format(id(bb), id(successor)), file=outf) + + outf.write('"{}" -> "{}" [label="entry"]\n'.format(id(f), id(f.entry))) + print('}', file=outf) + + +class Module: + """ Main container of variables and functions. """ + def __init__(self, name): + self.name = name + self.funcs = [] + self.variables = [] + + def __repr__(self): + return 'IR-module [{0}]'.format(self.name) + + def addFunc(self, f): + self.funcs.append(f) + + addFunction = addFunc + + def addVariable(self, v): + self.variables.append(v) + + def getVariables(self): + return self.variables + + Variables = property(getVariables) + + def getFunctions(self): + return self.funcs + + Functions = property(getFunctions) + + def findFunction(self, name): + for f in self.funcs: + if f.name == name: + return f + raise KeyError(name) + + getFunction = findFunction + + def dump(self, indent=' '): + print(self) + for v in self.Variables: + print(indent, v) + for fn in self.Functions: + fn.dump(indent=indent+' ') + + # Analysis functions: + def check(self): + """ Perform sanity check on module """ + for f in self.Functions: + f.check() + + +class Function: + """ + Function definition. Contains an entry block. + """ + def __init__(self, name): + self.name = name + self.entry = Block('{}_entry'.format(name)) + self.entry.function = self + self.epiloog = Block('{}_epilog'.format(name)) + self.epiloog.function = self + self.epiloog.addInstruction(Terminator()) + self.return_value = Temp('{}_retval'.format(name)) + self.arguments = [] + self.localvars = [] + + def __repr__(self): + args = ','.join(str(a) for a in self.arguments) + return 'Function {}({})'.format(self.name, args) + + def addBlock(self, bb): + self.bbs.append(bb) + bb.function = self + + def removeBlock(self, bb): + #self.bbs.remove(bb) + bb.function = None + + def getBlocks(self): + 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) + bbs.remove(self.entry) + if self.epiloog in bbs: + bbs.remove(self.epiloog) + bbs.insert(0, self.entry) + bbs.append(self.epiloog) + return bbs + + def findBasicBlock(self, name): + for bb in self.bbs: + if bb.name == name: + return bb + raise KeyError(name) + + Blocks = property(getBlocks) + + @property + def Entry(self): + return self.entry + + def check(self): + for b in self.Blocks: + b.check() + + def addParameter(self, p): + assert type(p) is Parameter + p.num = len(self.arguments) + self.arguments.append(p) + + def addLocal(self, l): + assert type(l) is LocalVariable + self.localvars.append(l) + + def dump(self, indent=''): + print(indent+str(self)) + for bb in self.Blocks: + print(indent+' '+str(bb)) + for ins in bb.Instructions: + print(indent +' '*2 + str(ins)) + + +class Block: + """ + Uninterrupted sequence of instructions with a label at the start. + """ + def __init__(self, name): + self.name = name + self.function = None + self.instructions = [] + + parent = property(lambda s: s.function) + + def __repr__(self): + return 'Block {0}'.format(self.name) + + def addInstruction(self, i): + i.parent = self + assert not isinstance(self.LastInstruction, LastStatement) + self.instructions.append(i) + + 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): + i.parent = None + i.delete() + self.instructions.remove(i) + + @property + def Instructions(self): + return self.instructions + + @property + def LastInstruction(self): + if not self.Empty: + return self.instructions[-1] + + @property + def Empty(self): + return len(self.instructions) == 0 + + @property + def FirstInstruction(self): + return self.instructions[0] + + def getSuccessors(self): + if not self.Empty: + return self.LastInstruction.Targets + return [] + Successors = property(getSuccessors) + + def getPredecessors(self): + preds = [] + for bb in self.parent.Blocks: + if self in bb.Successors: + preds.append(bb) + return preds + Predecessors = property(getPredecessors) + + def precedes(self, other): + raise NotImplementedError() + + def check(self): + assert isinstance(self.LastInstruction, LastStatement) + for i in self.instructions[:-1]: + assert not isinstance(i, LastStatement) + + +# Instructions: +class Term: + def __init__(self, x): + self.x = x + +def match_tree(tree, pattern): + if type(pattern) is Term: + return True, {pattern: tree} + elif type(pattern) is Binop and type(tree) is Binop and tree.operation == pattern.operation: + res_a, mp_a = match_tree(tree.a, pattern.a) + res_b, mp_b = match_tree(tree.b, pattern.b) + assert not (mp_a.keys() & mp_b.keys()) + mp_a.update(mp_b) + return res_a and res_b, mp_a + elif type(pattern) is Const and type(tree) is Const and pattern.value == tree.value: + return True, {} + else: + return False, {} + + +class Expression: + pass + + +class Const(Expression): + def __init__(self, value): + self.value = value + + def __repr__(self): + return 'Const {}'.format(self.value) + + +# Function calling: +class Call(Expression): + def __init__(self, f, arguments): + self.f = f + assert type(f) is Function + self.arguments = arguments + + def __repr__(self): + args = ', '.join([str(arg) for arg in self.arguments]) + return '{}({})'.format(self.f.name, args) + + +# Data operations +class Binop(Expression): + ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] + def __init__(self, value1, operation, value2): + assert operation in Binop.ops + self.a = value1 + self.b = value2 + self.operation = operation + + def __repr__(self): + a, b = self.a, self.b + return '({} {} {})'.format(a, self.operation, b) + + +def Add(a, b): + """ Convenience call """ + return Binop(a, '+', b) + + +def Sub(a, b): + return Binop(a, '-', b) + + +def Mul(a, b): + return Binop(a, '*', b) + + +def Div(a, b): + return Binop(a, '/', b) + +class Eseq(Expression): + """ Sequence of instructions where the last is an expression """ + def __init__(self, stmt, e): + self.stmt = stmt + self.e = e + + def __repr__(self): + return '({}, {})'.format(self.stmt, self.e) + + +class Alloc(Expression): + """ Allocates space on the stack """ + def __init__(self): + super().__init__() + + def __repr__(self): + return 'Alloc' + + +class Variable(Expression): + def __init__(self, name): + self.name = name + + def __repr__(self): + return 'Var {}'.format(self.name) + + +class LocalVariable(Variable): + def __repr__(self): + return 'Local {}'.format(self.name) + + +class Parameter(Variable): + def __repr__(self): + return 'Param {}'.format(self.name) + + +class Temp(Expression): + """ Temporary storage, same as register """ + def __init__(self, name): + self.name = name + + def __repr__(self): + return 'TMP_{}'.format(self.name) + + +class Mem(Expression): + def __init__(self, e): + self.e = e + + def __repr__(self): + return '[{}]'.format(self.e) + + +class Statement: + """ Base class for all instructions. """ + pass + + +class Move(Statement): + def __init__(self, dst, src): + self.dst = dst + self.src = src + + def __repr__(self): + return '{} = {}'.format(self.dst, self.src) + + +class Exp(Statement): + def __init__(self, e): + self.e = e + + def __repr__(self): + return '{}'.format(self.e) + + +# Branching: +class LastStatement(Statement): + def changeTarget(self, old, new): + idx = self.Targets.index(old) + self.Targets[idx] = new + + +class Terminator(LastStatement): + """ Instruction that terminates the terminal block """ + def __init__(self): + self.Targets = [] + + def __repr__(self): + return 'Terminator' + + +class Jump(LastStatement): + def __init__(self, target): + self.Targets = [target] + + def setTarget(self, t): + self.Targets[0] = t + target = property(lambda s: s.Targets[0], setTarget) + + def __repr__(self): + return 'JUMP {}'.format(self.target.name) + + +class CJump(LastStatement): + conditions = ['==', '<', '>', '>=', '<=', '!='] + def __init__(self, a, cond, b, lab_yes, lab_no): + assert cond in CJump.conditions + self.a = a + self.cond = cond + self.b = b + self.Targets = [lab_yes, lab_no] + + lab_yes = property(lambda s: s.Targets[0]) + lab_no = property(lambda s: s.Targets[1]) + + def __repr__(self): + return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) + + +# Constructing IR: + +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 self.cls('{0}{1}'.format(prefix, self.nums.__next__())) + + +class Builder: + """ Base class for ir code generators """ + def __init__(self): + self.prepare() + + def prepare(self): + self.newTemp = NamedClassGenerator('reg', Temp).gen + self.newBlock2 = NamedClassGenerator('block', Block).gen + self.bb = None + self.m = None + self.fn = None + self.loc = None + + # Helpers: + def setModule(self, m): + self.m = m + + def newFunction(self, name): + f = Function(name) + self.m.addFunc(f) + return f + + def newBlock(self): + assert self.fn + b = self.newBlock2() + b.function = self.fn + return b + + def setFunction(self, f): + self.fn = f + self.bb = f.entry if f else None + + def setBlock(self, b): + self.bb = b + + def setLoc(self, l): + self.loc = l + + def emit(self, i): + assert isinstance(i, Statement) + i.debugLoc = self.loc + if not self.bb: + raise Exception('No basic block') + self.bb.addInstruction(i) + + diff -r 158068af716c -r 6753763d3bec python/ppci/irmach.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/irmach.py Thu Dec 05 17:02:38 2013 +0100 @@ -0,0 +1,70 @@ + +""" + Abstract assembly language instructions. + + This is the second intermediate representation. + + Instructions are selected and scheduled at this stage. +""" + +from target import Instruction + + +class Frame: + """ + Activation record abstraction. This class contains a flattened + function. Instructions are selected and scheduled at this stage. + Frames differ per machine. + """ + def __init__(self, name): + self.name = name + self.instructions = [] + self.stacksize = 0 + + def __repr__(self): + return 'Frame {}'.format(self.name) + + def lower_to(self, outs): + for im in self.instructions: + if isinstance(im.assem, Instruction): + outs.emit(im.assem) + else: + outs.emit(im.assem.fromim(im)) + + +class AbstractInstruction: + """ + Abstract machine instruction class. This is a very simple + abstraction of machine instructions. + """ + def __init__(self, cls, ops=(), src=(), dst=(), jumps=(), others=(), ismove=False): + assert type(cls) is type or isinstance(cls, Instruction) + self.assem = cls + self.ops = tuple(ops) + self.src = tuple(src) + self.dst = tuple(dst) + self.jumps = tuple(jumps) + self.others = tuple(others) + self.ismove = ismove + + def __repr__(self): + return self.render() + + def render(self): + """ + Substitutes source, dst and labels in the string + """ + x = str(self.assem) + for i, s in enumerate(self.src): + p = '%s{}'.format(i) + x = x.replace(p, str(s)) + for i, d in enumerate(self.dst): + p = '%d{}'.format(i) + x = x.replace(p, str(d)) + for i, j in enumerate(self.jumps): + p = '%l{}'.format(i) + x = x.replace(p, str(j)) + return x + + +makeIns = AbstractInstruction diff -r 158068af716c -r 6753763d3bec python/ppci/transform.py --- a/python/ppci/transform.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/ppci/transform.py Thu Dec 05 17:02:38 2013 +0100 @@ -3,7 +3,7 @@ """ import logging -import ir +from . import ir # Standard passes: class FunctionPass: diff -r 158068af716c -r 6753763d3bec python/target/__init__.py --- a/python/target/__init__.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/target/__init__.py Thu Dec 05 17:02:38 2013 +0100 @@ -17,3 +17,8 @@ #from .msp430target import msp430target target_list = [armtarget] + + +class SimpleTarget(Target): + def __init__(self): + super().__init__('SimpleTarget') diff -r 158068af716c -r 6753763d3bec python/target/armframe.py --- a/python/target/armframe.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/target/armframe.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,7 +1,7 @@ -import ir +from ppci import ir from .basetarget import Label, Comment, Alignment, LabelRef, DebugInfo, Nop from .basetarget import Imm7 -from irmach import makeIns, Frame +from ppci.irmach import makeIns, Frame from .arminstructions import Dcd, AddSp, SubSp, Push, Pop, Mov2 from .arminstructions import R0, R1, R2, R3, R4, R5, R6, R7, LR, PC, SP diff -r 158068af716c -r 6753763d3bec python/target/arminstructionselector.py --- a/python/target/arminstructionselector.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/target/arminstructionselector.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,5 +1,5 @@ -import ir -from irmach import AbstractInstruction as makeIns +from ppci import ir +from ppci.irmach import AbstractInstruction as makeIns from .basetarget import Label, Comment, Alignment, LabelRef, DebugInfo, Nop from .instructionselector import InstructionSelector from .arminstructions import Orr, Lsl, Str2, Ldr2, Ldr3, B, Bl, Bgt, Blt, Beq diff -r 158068af716c -r 6753763d3bec python/target/instructionselector.py --- a/python/target/instructionselector.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/target/instructionselector.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,6 +1,6 @@ -import ir -import irmach -from irmach import AbstractInstruction as makeIns +from ppci import ir +from ppci import irmach +from ppci.irmach import AbstractInstruction as makeIns import target def genTemps(): diff -r 158068af716c -r 6753763d3bec python/zcc.py --- a/python/zcc.py Tue Dec 03 18:00:22 2013 +0100 +++ b/python/zcc.py Thu Dec 05 17:02:38 2013 +0100 @@ -6,7 +6,7 @@ from ppci.c3 import Builder import ppci -import codegen +from ppci.codegen import CodeGenerator import outstream from utils import HexFile import target @@ -52,8 +52,8 @@ """ logging.info('Zcc started') # Front end: - c3b = Builder(diag) - cg = codegen.CodeGenerator(tg) + c3b = Builder(diag, tg) + cg = CodeGenerator(tg) # TODO: remove this arm specifics: outs.getSection('code').address = 0x08000000 diff -r 158068af716c -r 6753763d3bec test/testc3.py --- a/test/testc3.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testc3.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,4 +1,5 @@ from ppci.c3 import Builder, Lexer +from target import SimpleTarget import ppci import unittest import io @@ -41,7 +42,7 @@ class testBuilder(unittest.TestCase): def setUp(self): self.diag = ppci.DiagnosticsManager() - self.builder = Builder(self.diag) + self.builder = Builder(self.diag, SimpleTarget()) self.diag.clear() def expectErrors(self, snippet, rows): diff -r 158068af716c -r 6753763d3bec test/testcg.py --- a/test/testcg.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testcg.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,7 +1,7 @@ import unittest import ppci -from codegen import CodeGenerator -import ir +from ppci.codegen import CodeGenerator +from ppci import ir from target import armtarget import outstream diff -r 158068af716c -r 6753763d3bec test/testgraph.py --- a/test/testgraph.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testgraph.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,11 +1,11 @@ #!/usr/bin/python import unittest -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 ppci.codegen.graph import Graph, Node +from ppci.codegen.interferencegraph import InterferenceGraph +from ppci.codegen.flowgraph import FlowGraph +from ppci import ir +from ppci.irmach import AbstractInstruction as AI from target import Nop diff -r 158068af716c -r 6753763d3bec test/testir.py --- a/test/testir.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testir.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,7 +1,8 @@ -import unittest, os +import unittest +import os import sys import ppci -import ir +from ppci import ir from ppci.transform import ConstantFolder diff -r 158068af716c -r 6753763d3bec test/testparserlib.py --- a/test/testparserlib.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testparserlib.py Thu Dec 05 17:02:38 2013 +0100 @@ -58,4 +58,3 @@ if __name__ == '__main__': unittest.main() - diff -r 158068af716c -r 6753763d3bec test/testregalloc.py --- a/test/testregalloc.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testregalloc.py Thu Dec 05 17:02:38 2013 +0100 @@ -1,9 +1,9 @@ import unittest import os import sys -from irmach import makeIns, Frame -from codegen.registerallocator import RegisterAllocator -import ir +from ppci.irmach import makeIns, Frame +from ppci.codegen.registerallocator import RegisterAllocator +from ppci import ir from target import Nop diff -r 158068af716c -r 6753763d3bec test/testzcc.py --- a/test/testzcc.py Tue Dec 03 18:00:22 2013 +0100 +++ b/test/testzcc.py Thu Dec 05 17:02:38 2013 +0100 @@ -34,7 +34,7 @@ self.do(['functions.c3']) def testSectionAddress(self): - src = """module tst; + src = """module tst; function void t2() {var int t3; t3 = 2;} """ f = io.StringIO(src)