# HG changeset patch
# User Windel Bouwman
# Date 1380222865 -7200
# Node ID 046017431c6ad7b26f3bad9239ccb695210a13b9
# Parent  56d37ed4b4d27c9d814d36b7e94d6113caed6af8
Started register allocator

diff -r 56d37ed4b4d2 -r 046017431c6a python/codeedit.py
--- 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)
diff -r 56d37ed4b4d2 -r 046017431c6a python/codegenarm.py
--- 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:
diff -r 56d37ed4b4d2 -r 046017431c6a python/cortexm3.py
--- 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()
 
diff -r 56d37ed4b4d2 -r 046017431c6a python/cortexm3desc.py
--- 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.
-}
-
-
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/flowgraph.py
--- 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
 
 
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/graph.py
--- 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)
 
 
diff -r 56d37ed4b4d2 -r 046017431c6a python/ide.py
--- 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)
diff -r 56d37ed4b4d2 -r 046017431c6a python/interferencegraph.py
--- /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)
diff -r 56d37ed4b4d2 -r 046017431c6a python/ir.py
--- /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)
+
+
diff -r 56d37ed4b4d2 -r 046017431c6a python/ir/__init__.py
--- 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
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/ir/builder.py
--- 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)
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/ir/module.py
--- 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)
-
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/irmach.py
--- 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
         
 
diff -r 56d37ed4b4d2 -r 046017431c6a python/registerallocator.py
--- 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)
 
-
diff -r 56d37ed4b4d2 -r 046017431c6a python/target.py
--- 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))
 
diff -r 56d37ed4b4d2 -r 046017431c6a python/testasm.py
--- 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')
diff -r 56d37ed4b4d2 -r 046017431c6a python/testgraph.py
--- /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()
+
diff -r 56d37ed4b4d2 -r 046017431c6a python/testhexfile.py
--- 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)
diff -r 56d37ed4b4d2 -r 046017431c6a python/testir.py
--- 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()