Mercurial > lcfOS
changeset 277:046017431c6a
Started register allocator
| author | Windel Bouwman |
|---|---|
| date | Thu, 26 Sep 2013 21:14:25 +0200 |
| parents | 56d37ed4b4d2 |
| children | 9fca39eebe50 |
| files | python/codeedit.py python/codegenarm.py python/cortexm3.py python/cortexm3desc.py python/flowgraph.py python/graph.py python/ide.py python/interferencegraph.py python/ir.py python/ir/__init__.py python/ir/builder.py python/ir/module.py python/irmach.py python/registerallocator.py python/target.py python/testasm.py python/testgraph.py python/testhexfile.py python/testir.py |
| diffstat | 19 files changed, 854 insertions(+), 703 deletions(-) [+] |
line wrap: on
line diff
--- a/python/codeedit.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/codeedit.py Thu Sep 26 21:14:25 2013 +0200 @@ -170,7 +170,7 @@ painter.drawText(xpos, ypos, self.getRow(row)) if self.arrow and self.arrow.row == row: painter.drawPixmap(self.xposERR, ypos + ydt, self.arrowPixmap) - curErrors = [e for e in self.errorlist if e.loc.row == row] + curErrors = [e for e in self.errorlist if e.loc and e.loc.row == row] for e in curErrors: painter.drawPixmap(self.xposERR, ypos + ydt, self.errorPixmap) painter.setPen(errorPen)
--- a/python/codegenarm.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/codegenarm.py Thu Sep 26 21:14:25 2013 +0200 @@ -3,7 +3,6 @@ from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo import cortexm3 as arm from ppci import CompilerError -import flowgraph import registerallocator from instructionselector import InstructionSelector import irmach @@ -210,59 +209,26 @@ # TODO: schedule traces in better order. # This is optional! self.ins_sel = ArmInstructionSelector() + self.ra = registerallocator.RegisterAllocator() self.outs = outs self.outs.getSection('code').address = 0x08000000 self.outs.getSection('data').address = 0x20000000 - def useUnused(self, inslist): - # Use unused temporaries at the end of the list - defTemps = [] - useTemps = [] - for i in inslist: - for d in iter(i.dst): - defTemps.append(d) - for s in iter(i.src): - useTemps.append(s) - defTemps = set(defTemps) - useTemps = set(useTemps) - unUsed = defTemps - useTemps - assert not unUsed - for uu in unUsed: - inslist.append(irmach.AbstractInstruction('use %s0', src=[uu])) - #print(useTemps) - - def allocFrame(self, f): - """ - Do register allocation for a single stack frame. - """ - ilist = f.instructions - self.useUnused(ilist) - cfg = flowgraph.FlowGraph(ilist) - f.cfg = cfg - ig = registerallocator.InterferenceGraph(cfg) - f.ig = ig - - ra = registerallocator.RegisterAllocator() - regMap = ra.registerAllocate(ig, f.regs, f.tempMap) - # Use allocated registers: - for i in ilist: - i.src = tuple(regMap[t] for t in i.src) - i.dst = tuple(regMap[t] for t in i.dst) - def generateFunc(self, irfunc): # Create a frame for this function: frame = ArmFrame(irfunc.name) + # Canonicalize the intermediate language: canon.make(irfunc, frame) - # print('after canonicalize:') - # irfunc.dump() + print('after canonicalize:') + irfunc.dump() self.ins_sel.munchFunction(irfunc, frame) - # print('Selected instructions:') - #for i in frame.instructions: - # print(i) + print('Selected instructions:') + for i in frame.instructions: + print(i) # Do register allocation: - self.allocFrame(frame) + self.ra.allocFrame(frame) # TODO: Peep-hole here? # Add label and return and stack adjustment:
--- a/python/cortexm3.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/cortexm3.py Thu Sep 26 21:14:25 2013 +0200 @@ -16,18 +16,14 @@ armtarget = Target('arm') -class ArmReg(Register): +class ArmRegister(Register): def __init__(self, num, name): super().__init__(name) self.num = num + def __repr__(self): return self.name -class RegOp: - def __init__(self, num): - assert num < 16 - self.num = num - @classmethod def Create(cls, vop): if type(vop) is ASymbol: @@ -37,41 +33,17 @@ regs[r.name] = r if name in regs: r = regs[name] - return cls(r.num) + if isinstance(r, cls): + return r -class Reg8Op: - def __init__(self, num): - assert num < 8 - self.num = num - @classmethod - def Create(cls, vop): - if type(vop) is ASymbol: - name = vop.name - regs = {} - for r in armtarget.registers: - regs[r.name] = r - if name in regs: - r = regs[name] - if r.num < 8: - return cls(r.num) +class Reg8Op(ArmRegister): + pass + -class Reg16Op: - def __init__(self, num): - assert num < 16 - self.num = num +class Reg16Op(ArmRegister): + pass - @classmethod - def Create(cls, vop): - if type(vop) is ASymbol: - name = vop.name - regs = {} - for r in armtarget.registers: - regs[r.name] = r - if name in regs: - r = regs[name] - if r.num < 16: - return cls(r.num) class RegSpOp: @classmethod @@ -128,7 +100,7 @@ class MemR8Rel: def __init__(self, basereg, offset): - assert type(basereg) is ArmReg + assert type(basereg) is Reg8Op self.basereg = basereg self.offset = offset @@ -173,13 +145,13 @@ regs = set() for arg in vop.arg: if type(arg) is ASymbol: - reg = RegOp.Create(arg) + reg = ArmRegister.Create(arg) if not reg: return regs.add(reg) elif type(arg) is ABinop and arg.op == '-': - reg1 = RegOp.Create(arg.arg1) - reg2 = RegOp.Create(arg.arg2) + reg1 = ArmRegister.Create(arg.arg1) + reg2 = ArmRegister.Create(arg.arg2) if not reg1: return if not reg2: @@ -193,32 +165,30 @@ def registerNumbers(self): return [r.num for r in self.regs] +def makeReg(cls, num, name): + r = cls(num, name) + armtarget.registers.append(r) + return r + # 8 bit registers: -r0 = ArmReg(0, 'r0') -armtarget.registers.append(r0) -r1 = ArmReg(1, 'r1') -armtarget.registers.append(r1) -r2 = ArmReg(2, 'r2') -armtarget.registers.append(r2) -r3 = ArmReg(3, 'r3') -armtarget.registers.append(r3) -r4 = ArmReg(4, 'r4') -armtarget.registers.append(r4) -r5 = ArmReg(5, 'r5') -armtarget.registers.append(r5) -r6 = ArmReg(6, 'r6') -armtarget.registers.append(r6) -r7 = ArmReg(7, 'r7') -armtarget.registers.append(r7) +r0 = makeReg(Reg8Op, 0, 'r0') +r1 = makeReg(Reg8Op, 1, 'r1') +r2 = makeReg(Reg8Op, 2, 'r2') +r3 = makeReg(Reg8Op, 3, 'r3') +r4 = makeReg(Reg8Op, 4, 'r4') +r5 = makeReg(Reg8Op, 5, 'r5') +r6 = makeReg(Reg8Op, 6, 'r6') +r7 = makeReg(Reg8Op, 7, 'r7') # Other registers: # TODO -sp = ArmReg(13, 'sp') -armtarget.registers.append(sp) -lr = ArmReg(14, 'lr') -armtarget.registers.append(lr) -pc = ArmReg(15, 'pc') -armtarget.registers.append(pc) +sp = makeReg(ArmRegister, 13, 'sp') +lr = makeReg(ArmRegister, 14, 'lr') +pc = makeReg(ArmRegister, 15, 'pc') +assert isinstance(sp, ArmRegister) +assert isinstance(r3, ArmRegister) +assert ArmRegister.Create(ASymbol('r3')) is r3 +assert ArmRegister.Create(ASymbol('sp')) is sp class ArmInstruction(Instruction): pass @@ -307,11 +277,12 @@ x = x + 1 return x + @armtarget.instruction class ldr_pcrel(ArmInstruction): """ ldr Rt, LABEL, load value from pc relative position """ mnemonic = 'ldr' - operands = (RegOp, LabelRef) + operands = (Reg8Op, LabelRef) def __init__(self, rt, label): assert isinstance(label, LabelRef) self.rt = rt @@ -337,38 +308,40 @@ def __repr__(self): return 'LDR {}, {}'.format(self.rt, self.label.name) + @armtarget.instruction class ldr_sprel(ls_sp_base_imm8): """ ldr Rt, [SP, imm8] """ mnemonic = 'LDR' opcode = 0x98 + @armtarget.instruction class str_sprel(ls_sp_base_imm8): """ str Rt, [SP, imm8] """ mnemonic = 'STR' opcode = 0x90 + @armtarget.instruction class mov_ins(ArmInstruction): """ mov Rd, imm8, move immediate value into register """ mnemonic = 'mov' opcode = 4 # 00100 Rd(3) imm8 - operands = (RegOp, Imm8) + operands = (Reg8Op, Imm8) def __init__(self, rd, imm): self.imm = imm.imm - self.r = rd.num + self.rd = rd def encode(self): - rd = self.r + rd = self.rd.num opcode = self.opcode imm8 = self.imm h = (opcode << 11) | (rd << 8) | imm8 return u16(h) + def __repr__(self): - return 'MOV {0}, xx?'.format(self.r) - - + return 'MOV {}, {}'.format(self.rd, self.imm) @@ -382,6 +355,7 @@ self.rd = rd self.rn = rn self.imm3 = imm3 + def encode(self): rd = self.rd.num rn = self.rn.num @@ -390,6 +364,8 @@ h = (self.opcode << 9) | (imm3 << 6) | (rn << 3) | rd return u16(h) + def __repr__(self): + return '{} {}, {}, {}'.format(self.mnemonic, self.rd, self.rn, self.imm3.imm) @armtarget.instruction class addregregimm3_ins(regregimm3_base): @@ -421,30 +397,35 @@ def __repr__(self): return '{} {}, {}, {}'.format(self.mnemonic, self.rd, self.rn, self.rm) + @armtarget.instruction class addregs_ins(regregreg_base): mnemonic = 'ADD' opcode = 0b0001100 + @armtarget.instruction class subregs_ins(regregreg_base): mnemonic = 'SUB' opcode = 0b0001101 + @armtarget.instruction class movregreg_ext_ins(ArmInstruction): - operands = (Reg16Op, Reg16Op) + operands = (ArmRegister, ArmRegister) mnemonic = 'MOV' def __init__(self, rd, rm): self.rd = rd self.rm = rm + def encode(self): Rd = self.rd.num & 0x7 D = (self.rd.num >> 3) & 0x1 Rm = self.rm.num opcode = 0b01000110 return u16((opcode << 8) | (D << 7) |(Rm << 3) | Rd) + def __repr__(self): return '{} {}, {}'.format(self.mnemonic, self.rd, self.rm) @@ -457,50 +438,65 @@ def __init__(self, rn, rdm): self.rn = rn self.rdm = rdm + def encode(self): rn = self.rn.num rdm = self.rdm.num opcode = 0b0100001101 h = (opcode << 6) | (rn << 3) | rdm return u16(h) + def __repr__(self): - return '{} {}, {}'.format(self.mnemonic, self.rdn, self.rm) + return '{} {}, {}'.format(self.mnemonic, self.rn, self.rdm) + class regreg_base(ArmInstruction): """ ??? Rdn, Rm """ operands = (Reg8Op, Reg8Op) + # TODO: integrate with the code gen interface: + src = (0, 1) + dst = (0,) def __init__(self, rdn, rm): self.rdn = rdn self.rm = rm + def encode(self): rdn = self.rdn.num rm = self.rm.num h = (self.opcode << 6) | (rm << 3) | rdn return u16(h) + def __repr__(self): return '{} {}, {}'.format(self.mnemonic, self.rdn, self.rm) + @armtarget.instruction class movregreg_ins(regreg_base): + # TODO: match this: + pattern = ir.Move(ir.Temp, ir.Temp) """ mov Rd, Rm """ mnemonic = 'mov' opcode = 0 + @armtarget.instruction class andregs_ins(regreg_base): mnemonic = 'AND' opcode = 0b0100000000 + @armtarget.instruction class orrregs_ins(regreg_base): mnemonic = 'ORR' opcode = 0b0100001100 + @armtarget.instruction class cmp_ins(regreg_base): mnemonic = 'CMP' opcode = 0b0100001010 + @armtarget.instruction class lslregs_ins(regreg_base): mnemonic = 'LSL' @@ -511,7 +507,7 @@ """ cmp Rn, imm8 """ mnemonic = 'cmp' opcode = 5 # 00101 - operands = (RegOp, Imm8) + operands = (Reg8Op, Imm8) def __init__(self, rn, imm): self.rn = rn self.imm = imm @@ -522,6 +518,7 @@ h = (opcode << 11) | (rn << 8) | imm return u16(h) + # Jumping: def wrap_negative(x, bits): @@ -653,29 +650,29 @@ # misc: # add/sub SP: -@armtarget.instruction -class addspsp_ins(ArmInstruction): +class addspsp_base(ArmInstruction): operands = (RegSpOp, RegSpOp, Imm7) - mnemonic = 'add' def __init__(self, _sp, _sp2, imm7): self.imm7 = imm7.imm assert self.imm7 % 4 == 0 self.imm7 >>= 2 def encode(self): - return u16((0b101100000 << 7) |self.imm7) + return u16((self.opcode << 7) |self.imm7) + + def __repr__(self): + return '{} sp, sp, {}'.format(self.mnemonic, self.imm7 << 2) @armtarget.instruction -class subspsp_ins(ArmInstruction): - operands = (RegSpOp, RegSpOp, Imm7) +class addspsp_ins(addspsp_base): + mnemonic = 'add' + opcode = 0b101100000 + + +@armtarget.instruction +class subspsp_ins(addspsp_base): mnemonic = 'sub' - def __init__(self, _sp, _sp2, imm7): - self.imm7 = imm7.imm - assert self.imm7 % 4 == 0 - self.imm7 >>= 2 - - def encode(self): - return u16((0b101100001 << 7) |self.imm7) + opcode = 0b101100001 armtarget.check()
--- a/python/cortexm3desc.py Mon Sep 16 21:51:17 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ - -# Patterns - -import cortexm3 -import ir - - -{ -""" -v3 = const1 -v1 = v2 + v3 -[v1] = v3 -""": cortexm3. -} - - -
--- a/python/flowgraph.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/flowgraph.py Thu Sep 26 21:14:25 2013 +0200 @@ -1,6 +1,5 @@ - +import graph -import graph class FlowGraphNode(graph.Node): """ A node in the flow graph """ @@ -24,12 +23,11 @@ class FlowGraph(graph.Graph): def __init__(self, instrs): """ Create a flowgraph from a list of abstract instructions """ - super().__init__() + super().__init__(True) self._map = {} # Add nodes: for ins in instrs: n = self.newNode(ins) - self._map[ins] = n # Make edges: prev = None @@ -48,8 +46,8 @@ def newNode(self, ins): """ Override new node to make flow graph node """ n = FlowGraphNode(self, ins) - self.nodes.append(n) + self._map[ins] = n + self.addNode(n) return n -
--- a/python/graph.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/graph.py Thu Sep 26 21:14:25 2013 +0200 @@ -4,25 +4,45 @@ Generic graph base class. Can dump to graphiz dot format for example! """ - def __init__(self): - self.nodes = [] - self.edges = [] + def __init__(self, directed): + self.directed = directed + self.nodes = set() + self.edges = set() def newNode(self): n = Node(self) - self.nodes.append(n) + self.addNode(n) return n + 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 """ if (n, m) not in self.edges and (m, n) not in self.edges: - self.edges.append((n, m)) - n.succ.append(m) - m.pred.append(n) + self.edges.add((n, m)) + + def hasEdge(self, n, m): + # This can be directional or not :) + if self.directed: + return (n, m) in self.edges + else: + return (n, m) in self.edges or (m, n) in self.edges - def delEdge(self): - # TODO - pass + def adjecent(self, n): + """ Return all nodes with edges to n """ + return set(m for m in self.nodes if self.hasEdge(n, m)) + + def preceeding(self, n): + assert self.directed + return set(m for m in self.nodes if self.hasEdge(m, n)) + + def succeeding(self, n): + assert self.directed + return set(m for m in self.nodes if self.hasEdge(n, m)) def to_dot(self, f): """ Generate graphviz dot representation """ @@ -40,11 +60,22 @@ """ def __init__(self, g): self.g = g - self.succ = [] - self.pred = [] + + @property + def Succ(self): + return self.g.succeeding(self) + + @property + def Pred(self): + """ Return a set of predecessors """ + return self.g.preceeding(self) @property def Adj(self): - return set(self.succ) | set(self.pred) + return self.g.adjecent(self) + + @property + def Degree(self): + return len(self.Adj)
--- a/python/ide.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/ide.py Thu Sep 26 21:14:25 2013 +0200 @@ -52,9 +52,11 @@ for e in errorlist: item = QStandardItem(self.errorIcon, str(e.msg)) item.setData(e) - irow = QStandardItem(str(e.loc.row)) + row = str(e.loc.row) if e.loc else '' + irow = QStandardItem(row) irow.setData(e) - icol = QStandardItem(str(e.loc.col)) + col = str(e.loc.col) if e.loc else '' + icol = QStandardItem(col) icol.setData(e) self.model.appendRow([item, irow, icol]) @@ -223,7 +225,8 @@ self.restoreGeometry(self.settings.value('mainwindowgeometry')) if self.settings.contains('lastfiles'): lfs = self.settings.value('lastfiles') - self.to_open_files.extend(lfs) + if lfs: + self.to_open_files.extend(lfs) def showEvent(self, ev): super().showEvent(ev)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/interferencegraph.py Thu Sep 26 21:14:25 2013 +0200 @@ -0,0 +1,69 @@ +import graph + + +class InterferenceGraphNode(graph.Node): + def __init__(self, g, varname): + super().__init__(g) + self.varname = varname + + def __repr__(self): + return '{}'.format(self.varname) + + +class InterferenceGraph(graph.Graph): + """ + Interference graph. + """ + def __init__(self, flowgraph): + """ + Create a new interference graph from a flowgraph + """ + super().__init__(False) + # Mapping from node to live set + self.liveMap = {} + self.tempMap = {} + # 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 getNode(self, tmp): + if tmp not in self.tempMap: + self.tempMap[tmp] = self.newNode(tmp) + return self.tempMap[tmp] + + def newNode(self, varname): + n = InterferenceGraphNode(self, varname) + self.addNode(n) + return n + + def combine(self, n, m): + self.nodes.remove(m) + n.varnames.extend(m.varnames)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ir.py Thu Sep 26 21:14:25 2013 +0200 @@ -0,0 +1,456 @@ +""" +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.epiloog = Block('{}_epilog'.format(name)) + 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 addBB(self, bb): + self.bbs.append(bb) + bb.parent = self + addBlock = addBB + + def removeBasicBlock(self, bb): + self.bbs.remove(bb) + bb.parent = None + + def getBBs(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(getBBs) + + @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.instructions = [] + + 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) + + def getInstructions(self): + return self.instructions + Instructions = property(getInstructions) + + def getLastIns(self): + if not self.Empty: + return self.instructions[-1] + LastInstruction = property(getLastIns) + + @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.BasicBlocks: + 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) + + +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) + + +class Label(Statement): + # TODO: is this duplicate with block? + def __init__(self, name): + self.name = name + self.statements = [] + + def __repr__(self): + return 'LABEL {}:'.format(self.name) + + +# Branching: +class LastStatement(Statement): + pass + + +class Terminator(LastStatement): + """ Instruction that terminates the terminal block """ + Targets = [] + def __repr__(self): + return 'Terminator' + + +class Jump(LastStatement): + def __init__(self, target): + self.target = target + self.Targets = [target] + + def __repr__(self): + return 'BRANCH {}'.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.lab_yes = lab_yes + self.lab_no = lab_no + self.Targets = [lab_yes, lab_no] + + def __repr__(self): + return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) + + +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.newBlock = 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 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) + +
--- a/python/ir/__init__.py Mon Sep 16 21:51:17 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ -from .module import * -from .builder import Builder, NamedClassGenerator -
--- a/python/ir/builder.py Mon Sep 16 21:51:17 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,58 +0,0 @@ -from . import Block, Function, Statement, Temp - -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.newBlock = 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 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) -
--- a/python/ir/module.py Mon Sep 16 21:51:17 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,379 +0,0 @@ -# IR-Structures: - - -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.epiloog = Block('{}_epilog'.format(name)) - 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 addBB(self, bb): - self.bbs.append(bb) - bb.parent = self - addBlock = addBB - - def removeBasicBlock(self, bb): - self.bbs.remove(bb) - bb.parent = None - - def getBBs(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(getBBs) - - @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.instructions = [] - - 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) - - def getInstructions(self): - return self.instructions - Instructions = property(getInstructions) - - def getLastIns(self): - if not self.Empty: - return self.instructions[-1] - LastInstruction = property(getLastIns) - - @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.BasicBlocks: - 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 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) - - -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) - - -class Label(Statement): - # TODO: is this duplicate with block? - def __init__(self, name): - self.name = name - self.statements = [] - - def __repr__(self): - return 'LABEL {}:'.format(self.name) - - -# Branching: -class LastStatement(Statement): - pass - - -class Terminator(LastStatement): - """ Instruction that terminates the terminal block """ - Targets = [] - def __repr__(self): - return 'Terminator' - - -class Jump(LastStatement): - def __init__(self, target): - self.target = target - self.Targets = [target] - - def __repr__(self): - return 'BRANCH {}'.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.lab_yes = lab_yes - self.lab_no = lab_no - self.Targets = [lab_yes, lab_no] - - def __repr__(self): - return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) - -
--- a/python/irmach.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/irmach.py Thu Sep 26 21:14:25 2013 +0200 @@ -7,6 +7,8 @@ Instructions are selected and scheduled at this stage. """ +import ir + class Frame: """ Activation record abstraction. This class contains a flattened @@ -29,24 +31,23 @@ Abstract machine instruction class. This is a very simple abstraction of machine instructions. """ - def __init__(self, assem, src=(), dst=(), jumps=()): - self.assem = assem + def __init__(self, cls, ops=(), src=(), dst=(), jumps=()): + self.assem = cls + self.ops = ops self.src = tuple(src) self.dst = tuple(dst) self.jumps = tuple(jumps) + c = lambda s: tuple(map(type, s)) == (ir.Temp, ) + self.ismove = c(src) and c(dst) and cls.lower().startswith('mov') def __repr__(self): - s = str(self.src) if self.src else '' - d = str(self.dst) if self.dst else '' - l = str(self.jumps) if self.jumps else '' - #return self.assem + s + d + l return self.render() def render(self): """ Substitutes source, dst and labels in the string """ - x = self.assem + x = str(self.assem) for i, s in enumerate(self.src): p = '%s{}'.format(i) x = x.replace(p, str(s)) @@ -56,7 +57,6 @@ for i, j in enumerate(self.jumps): p = '%l{}'.format(i) x = x.replace(p, str(j)) - return x
--- a/python/registerallocator.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/registerallocator.py Thu Sep 26 21:14:25 2013 +0200 @@ -1,97 +1,125 @@ - -import graph - -class InterferenceGraphNode(graph.Node): - def __init__(self, g, varname): - super().__init__(g) - self.varname = varname - - def __repr__(self): - return '{}'.format(self.varname) - - -class InterferenceGraph(graph.Graph): - def __init__(self, flowgraph): - """ - Create a new interference graph from a flowgraph - """ - super().__init__() - # Mapping from node to live set - self.liveMap = {} - self.tempMap = {} - # 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 getNode(self, tmp): - if tmp not in self.tempMap: - self.tempMap[tmp] = self.newNode(tmp) - return self.tempMap[tmp] - - def newNode(self, varname): - n = InterferenceGraphNode(self, varname) - self.nodes.append(n) - return n +from flowgraph import FlowGraph +from interferencegraph import InterferenceGraph class RegisterAllocator: - """ Target independent register allocator """ - def registerAllocate(self, ig, regs, precolored): - """ - Color the given interference graph with the provided registers - """ - regMap = dict(precolored) - regs = set(regs) - K = len(regs) - allvars = list(n for n in ig.nodes if n.varname not in regMap) + """ + Target independent register allocator. + + Algorithm is iterated .. (ITR) by Appel and George + + The process consists of the following steps: + - build interference graph from the instruction list + - (optional) coalesc registers to remove redundant moves + - (optional) spill registers + - select registers + """ + def __init__(self): + pass + + def useUnused(self, inslist): + # Use unused temporaries at the end of the list + defTemps = [] + useTemps = [] + for i in inslist: + for d in iter(i.dst): + defTemps.append(d) + for s in iter(i.src): + useTemps.append(s) + defTemps = set(defTemps) + useTemps = set(useTemps) + unUsed = defTemps - useTemps + assert not unUsed + def build(self, f): + """ 1. Construct interference graph from instruction list """ + self.useUnused(f.instructions) + f.cfg = FlowGraph(f.instructions) + f.ig = InterferenceGraph(f.cfg) + self.pre_colored = set(n for n in f.ig.nodes if n.varname in f.tempMap.keys()) + print('pre-colored:', self.pre_colored) + self.moves = [i for i in f.instructions if i.ismove] + print('move instructions:', self.moves) + self.nodestack = [] + + def getMoveRelated(self, f): + mr = set() + for i in self.moves: + mr.add(f.ig.getNode(i.src[0])) + mr.add(f.ig.getNode(i.dst[0])) + return mr + + def simplify(self, f): + """ 2. Remove nodes from the graph """ # Chaitin's algorithm: - # remove all nodes that have less than K neighbours: - worklist = [] - while allvars: - less_k = [n for n in allvars if len(n.Adj - set(worklist)) < K] + # remove all non move related nodes that have less than K neighbours: + # Also do not remove pre-colored nodes. + # move_related = self.getMoveRelated(f) + #print('move related', move_related) + # o_nodes = f.ig.nodes - (self.pre_colored | move_related) + o_nodes = f.ig.nodes - self.pre_colored + #print('o_nodes', o_nodes) + while o_nodes: + less_k = [n for n in o_nodes if n.Degree < self.K] if not less_k: raise NotImplementedError('Spilling not implemented') n = less_k[0] - worklist.append(n) - allvars.remove(n) + self.nodestack.append(n) + f.ig.delNode(n) + o_nodes.remove(n) + + def coalesc(self, f): + # for mov in ins: + # if mov.src is not connected to mov.dst + # and the node being coalesced has less than K nodes + # of significant degree, then the node can be coalesced. + # This is briggs algorithm. + for m in self.moves: + src = f.ig.getNode(m.src[0]) + dst = f.ig.getNode(m.dst[0]) + assert not f.ig.hasEdge(src, dst) + neighbours = src.Adj | dst.Adj + # neighbours with significant degree: + sd_nb = set(n for n in neighbours if n.Degree >= self.K) + print('neighbours with significant degree', sd_nb) + if len(sd_nb) < self.K: + print('Coalesc:', m) + if dst in self.pre_colored: + if src in self.pre_colored: + break + v2 = src + for i in f.instructions: + rf = lambda x: x + i.src = rf(i.src) + i.dst = rf(i.dst) + f.instructions.remove(m) + + def select(self, f): + """ Add nodes of less than K degree back to the graph to color it. """ + regMap = dict(f.tempMap) # start with pre-colored # Add nodes back to the graph: - while worklist: - n = worklist.pop(-1) - adj = n.Adj - set(worklist) - possibleregs = set(regs) - set(regMap[n.varname] for n in adj) + while self.nodestack: + n = self.nodestack.pop(-1) + f.ig.addNode(n) + takenregs = set(regMap[m.varname] for m in n.Adj) + possibleregs = set(self.regs) - takenregs regMap[n.varname] = list(possibleregs)[0] # We have a register mapping! - # print(regMap) + print(regMap) + # Use allocated registers: + lookup = lambda t: regMap[t] + for i in f.instructions: + i.src = tuple(map(lookup, i.src)) + i.dst = tuple(map(lookup, i.dst)) + + def allocFrame(self, f): + """ Do register allocation for a single stack frame. """ + self.regs = set(f.regs) + self.K = len(self.regs) + self.build(f) + self.simplify(f) # TODO: implement spilling - # TODO: implement coalescing - return regMap + #self.coalesc(f) # Optional! + self.select(f) -
--- a/python/target.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/target.py Thu Sep 26 21:14:25 2013 +0200 @@ -184,8 +184,7 @@ rops = [roptype.Create(vop) for roptype, vop in zip(ic.operands, vi.operands)] # Check if we succeeded: - optypes = tuple(map(type, rops)) - if ic.operands == optypes: + if all(isinstance(rop, optype) for rop, optype in zip(rops, ic.operands)): return ic(*rops) raise CompilerError('No suitable instruction found for "{0}"'.format(vi))
--- a/python/testasm.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/testasm.py Thu Sep 26 21:14:25 2013 +0200 @@ -183,6 +183,11 @@ self.feed('mov r4, 100') self.check('6424') + @unittest.skip + def testMovExt(self): + self.feed('mov r3, sp') + self.check('') + def testYield(self): self.feed('yield') self.check('10bf')
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/testgraph.py Thu Sep 26 21:14:25 2013 +0200 @@ -0,0 +1,35 @@ +#!/usr/bin/python + +import unittest +import graph + +class GraphTestCase(unittest.TestCase): + def testEdge(self): + g = graph.Graph(False) + n1 = g.newNode() + n2 = g.newNode() + g.addEdge(n1, n2) + self.assertTrue(g.hasEdge(n2, n1)) + self.assertTrue(g.hasEdge(n1, n2)) + g.delNode(n1) + g.delNode(n2) + + def testDegree(self): + g = graph.Graph(False) + n1 = g.newNode() + n2 = g.newNode() + n3 = g.newNode() + g.addEdge(n1, n2) + g.addEdge(n1, n3) + self.assertEqual(2, n1.Degree) + self.assertEqual(1, n2.Degree) + g.delNode(n2) + self.assertEqual(1, n1.Degree) + +class DigraphTestCase(unittest.TestCase): + pass + + +if __name__ == '__main__': + unittest.main() +
--- a/python/testhexfile.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/testhexfile.py Thu Sep 26 21:14:25 2013 +0200 @@ -28,13 +28,11 @@ hf.addRegion(0xFFFE, bytes.fromhex('aabbcc')) self.saveload(hf) - @unittest.skip def testSave4(self): hf = HexFile() hf.addRegion(0xF000, bytes.fromhex('ab')*0x10000) self.saveload(hf) - @unittest.skip def testSave5(self): hf = HexFile() hf.addRegion(0xF003, bytes.fromhex('ab')*0x10000)
--- a/python/testir.py Mon Sep 16 21:51:17 2013 +0200 +++ b/python/testir.py Thu Sep 26 21:14:25 2013 +0200 @@ -26,6 +26,29 @@ #self.assertEqual(3, r) +class PatternMatchTestCase(unittest.TestCase): + def testSimpleTree(self): + t = ir.Term('x') + pat = ir.Binop(ir.Const(2), '+', t) + res, mp = ir.match_tree(ir.Binop(ir.Const(2), '+', 3), pat) + self.assertTrue(res) + self.assertIn(t, mp) + self.assertEqual(3, mp[t]) + + def testSimpleTree2(self): + t = ir.Term('x') + t2 = ir.Term('y') + pat = ir.Binop(ir.Const(2), '+', ir.Binop(t, '-', t2)) + res, mp = ir.match_tree(ir.Binop(ir.Const(2), '+', ir.Binop(2,'-',3)), pat) + self.assertTrue(res) + self.assertIn(t, mp) + self.assertEqual(2, mp[t]) + self.assertIn(t2, mp) + self.assertEqual(3, mp[t2]) + res, mp = ir.match_tree(ir.Const(2), pat) + self.assertFalse(res) + + class ConstantFolderTestCase(unittest.TestCase): def setUp(self): self.b = ir.Builder()