--- a/python/registerallocator.py	Wed Aug 14 20:12:40 2013 +0200
+++ b/python/registerallocator.py	Sun Aug 18 17:43:18 2013 +0200
@@ -1,33 +1,73 @@
+
+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
+
 
 class RegisterAllocator:
-   def live_analyze(self):
-      # Determine liveness:
-      for i in self.Instructions:
-         i.live_in = set()
-         i.live_out = set()
-      for z in range(50):
-         # TODO iterate until converge
-         for i in self.Instructions:
-            lo_mk = i.live_out.difference(i.defs)
-            i.live_in = i.uses.union(lo_mk)
-            lo = set()
-            for s in i.succ:
-               lo = lo.union(s.live_in)
-            i.live_out = lo
-   def registerAllocate(self, ir, regs):
-      allVals = []
-      # construct interference:
-      for i in ir.Instructions:
-         for v in i.live_in:
-            allVals.append(v)
-            for v2 in i.live_in:
-               if v != v2:
-                  v.interferes.add(v2)
-      # assign random registers:
-      regs = set(regs)
-      for v in allVals:
-         takenregs = set([iv.reg for iv in v.interferes])
-         r2 = list(regs.difference(takenregs))
-         # Pick next available:
-         v.reg = r2[0]
+    """ Target independent register allocator """
+    def registerAllocate(self, ig, regs):
+        """ Color the given interference graph with the provided registers """
+        self.regMap = {}
+        # TODO: implement ;)
+        regs = set(regs)
+        for n in ig.nodes:
+            print(n)
 
+        # TODO: implement spilling
+        # TODO: implement coalescing
+