--- a/python/registerallocator.py	Sun Aug 18 17:43:18 2013 +0200
+++ b/python/registerallocator.py	Mon Aug 19 21:14:28 2013 +0200
@@ -62,11 +62,31 @@
     """ Target independent register allocator """
     def registerAllocate(self, ig, regs):
         """ Color the given interference graph with the provided registers """
-        self.regMap = {}
-        # TODO: implement ;)
+        regMap = {}
         regs = set(regs)
-        for n in ig.nodes:
-            print(n)
+        K = len(regs)
+        allvars = list(ig.nodes)
+
+        # 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]
+            if not less_k:
+                raise NotImplementedError('Spilling not implemented')
+            n = less_k[0]
+            worklist.append(n)
+            allvars.remove(n)
+
+        # 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)
+            regMap[n.varname] = list(possibleregs)[0]
+        # We have a register mapping!
+        #print(self.regMap)
+        return regMap
 
         # TODO: implement spilling
         # TODO: implement coalescing