# HG changeset patch
# User Windel Bouwman
# Date 1376939668 -7200
# Node ID cdc76d183bcc37d6723e275e02c5198856811d3d
# Parent  5f8c04a8d26bb198f792d11e3b1aad730fa61c43
first register allocator

diff -r 5f8c04a8d26b -r cdc76d183bcc python/codegenarm.py
--- a/python/codegenarm.py	Sun Aug 18 17:43:18 2013 +0200
+++ b/python/codegenarm.py	Mon Aug 19 21:14:28 2013 +0200
@@ -3,7 +3,6 @@
 from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo
 import cortexm3 as arm
 from ppci import CompilerError
-import graph
 import flowgraph
 import registerallocator
 from instructionselector import InstructionSelector
@@ -100,9 +99,20 @@
         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 = []
+        for d in (i.dst for i in inslist):
+            print(d)
+            defTemps.append(d)
+        useTemps = [d for d in ([i.src] for i in inslist)]
+        print(defTemps)
+        print(useTemps)
+
     def generate(self, ircode, cfg_file=None, ig_file=None):
-        x = self.ins_sel.munchProgram(ircode)
-        cfg = flowgraph.FlowGraph(x)
+        ir2 = self.ins_sel.munchProgram(ircode)
+        self.useUnused(ir2)
+        cfg = flowgraph.FlowGraph(ir2)
         if cfg_file:
             cfg.to_dot(cfg_file)
         ig = registerallocator.InterferenceGraph(cfg)
@@ -111,6 +121,12 @@
 
         regs = ['r0', 'r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7']
         ra = registerallocator.RegisterAllocator()
-        ra.registerAllocate(ig, regs)
+        regMap = ra.registerAllocate(ig, regs)
+        print(regMap)
+        for i in ir2:
+            i.src = tuple(regMap[t] for t in i.src)
+            i.dst = tuple(regMap[t] for t in i.dst)
+            print(i)
 
 
+
diff -r 5f8c04a8d26b -r cdc76d183bcc python/graph.py
--- a/python/graph.py	Sun Aug 18 17:43:18 2013 +0200
+++ b/python/graph.py	Mon Aug 19 21:14:28 2013 +0200
@@ -43,3 +43,8 @@
         self.succ = []
         self.pred = []
 
+    @property
+    def Adj(self):
+        return set(self.succ) | set(self.pred)
+
+
diff -r 5f8c04a8d26b -r cdc76d183bcc python/ir/function.py
--- a/python/ir/function.py	Sun Aug 18 17:43:18 2013 +0200
+++ b/python/ir/function.py	Mon Aug 19 21:14:28 2013 +0200
@@ -28,7 +28,8 @@
                     bbs.append(sb)
                     worklist.append(sb)
         bbs.remove(self.entry)
-        bbs.remove(self.epiloog)
+        if self.epiloog in bbs:
+            bbs.remove(self.epiloog)
         bbs.insert(0, self.entry)
         bbs.append(self.epiloog)
         return bbs
diff -r 5f8c04a8d26b -r cdc76d183bcc python/irmach.py
--- a/python/irmach.py	Sun Aug 18 17:43:18 2013 +0200
+++ b/python/irmach.py	Mon Aug 19 21:14:28 2013 +0200
@@ -1,6 +1,10 @@
 
 """
-  Abstract assembly language instructions
+  Abstract assembly language instructions.
+
+  This is the second intermediate representation.
+  
+  Instructions are selected and scheduled at this stage.
 """
 
 
diff -r 5f8c04a8d26b -r cdc76d183bcc python/registerallocator.py
--- 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