# HG changeset patch
# User Windel Bouwman
# Date 1380456495 -7200
# Node ID 9fca39eebe507c339fad8f8df24456af0ff113c2
# Parent  046017431c6ad7b26f3bad9239ccb695210a13b9
First implementation of regalloc with coalsesc

diff -r 046017431c6a -r 9fca39eebe50 python/flowgraph.py
--- a/python/flowgraph.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/flowgraph.py	Sun Sep 29 14:08:15 2013 +0200
@@ -1,7 +1,7 @@
 import graph
 
 
-class FlowGraphNode(graph.Node):
+class FlowGraphNode(graph.DiNode):
     """ A node in the flow graph """
     def __init__(self, g, ins):
         super().__init__(g)
@@ -20,14 +20,16 @@
         return r
 
 
-class FlowGraph(graph.Graph):
+class FlowGraph(graph.DiGraph):
     def __init__(self, instrs):
         """ Create a flowgraph from a list of abstract instructions """
-        super().__init__(True)
+        super().__init__()
         self._map = {}
         # Add nodes:
         for ins in instrs:
-            n = self.newNode(ins)
+            n = FlowGraphNode(self, ins)
+            self._map[ins] = n
+            self.addNode(n)
 
         # Make edges:
         prev = None
@@ -43,11 +45,4 @@
             else:
                 prev = n
 
-    def newNode(self, ins):
-        """ Override new node to make flow graph node """
-        n = FlowGraphNode(self, ins)
-        self._map[ins] = n
-        self.addNode(n)
-        return n
 
-
diff -r 046017431c6a -r 9fca39eebe50 python/graph.py
--- a/python/graph.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/graph.py	Sun Sep 29 14:08:15 2013 +0200
@@ -4,16 +4,10 @@
        Generic graph base class.
        Can dump to graphiz dot format for example!
     """
-    def __init__(self, directed):
-        self.directed = directed
+    def __init__(self):
         self.nodes = set()
         self.edges = set()
 
-    def newNode(self):
-        n = Node(self)
-        self.addNode(n)
-        return n
-
     def addNode(self, n):
         self.nodes.add(n)
 
@@ -22,36 +16,27 @@
 
     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.add((n, m))
+        self.edges.add((n, m))
+        self.edges.add((m, n))
 
     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
+        return (n, m) in self.edges
+
+    def delEdge(self, n, m):
+        self.edges.remove((n, m))
+        self.edges.remove((m, n))
 
     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
+        # TODO: this can be optimized for speed:
         return set(m for m in self.nodes if self.hasEdge(n, m))
         
     def to_dot(self, f):
         """ Generate graphviz dot representation """
-        #print('digraph G {', file=f)
         for node in self.nodes:
             print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f)
         for n, m in self.edges:
             print('{} -> {};'.format(id(n), id(m)), file=f)
-        #print('}', file=f)
 
 
 class Node:
@@ -60,22 +45,41 @@
     """
     def __init__(self, g):
         self.g = g
-
-    @property
-    def Succ(self):
-        return self.g.succeeding(self)
+        self.addDegree = 0 # Hack to increase degree
 
     @property
-    def Pred(self):
-        """ Return a set of predecessors """
-        return self.g.preceeding(self)
-
-    @property
-    def Adj(self):
+    def Adjecent(self):
         return self.g.adjecent(self)
 
     @property
     def Degree(self):
-        return len(self.Adj)
+        return len(self.Adjecent) + self.addDegree
 
 
+class DiGraph(Graph):
+    """
+        Directed graph.
+    """
+    def addEdge(self, n, m):
+        """ Add an edge from n to m """
+        self.edges.add((n, m))
+
+    def hasEdge(self, n, m):
+        return (n, m) in self.edges
+
+    def successors(self, n):
+        return set(m for m in self.nodes if self.hasEdge(n, m))
+
+    def predecessors(self, n):
+        return set(m for m in self.nodes if self.hasEdge(m, n))
+
+
+class DiNode(Node):
+    @property
+    def Succ(self):
+        return self.g.successors(self)
+
+    @property
+    def Pred(self):
+        return self.g.predecessors(self)
+
diff -r 046017431c6a -r 9fca39eebe50 python/interferencegraph.py
--- a/python/interferencegraph.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/interferencegraph.py	Sun Sep 29 14:08:15 2013 +0200
@@ -4,10 +4,11 @@
 class InterferenceGraphNode(graph.Node):
     def __init__(self, g, varname):
         super().__init__(g)
-        self.varname = varname
+        self.temps = [varname]
+        self.moves = set()
 
     def __repr__(self):
-        return '{}'.format(self.varname)
+        return 'IGN<{}>'.format(self.temps)
 
 
 class InterferenceGraph(graph.Graph):
@@ -18,10 +19,7 @@
         """ 
             Create a new interference graph from a flowgraph 
         """
-        super().__init__(False)
-        # Mapping from node to live set
-        self.liveMap = {}
-        self.tempMap = {}
+        super().__init__()
         # Calculate liveness in CFG:
         ###
         # Liveness:
@@ -55,15 +53,20 @@
                     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)
+        # Linear search
+        # TODO: can be improved for speed!
+        for n in self.nodes:
+            if tmp in n.temps:
+                return n
+        n = InterferenceGraphNode(self, tmp)
         self.addNode(n)
         return n
 
-    def combine(self, n, m):
-        self.nodes.remove(m)
-        n.varnames.extend(m.varnames)
+    def Combine(self, n, m):
+        """ Combine n and m into n """
+        n.temps.extend(m.temps)
+        n.moves.update(m.moves)
+        for t in m.Adjecent:
+            self.addEdge(n, t)
+        self.delNode(m)
+
diff -r 046017431c6a -r 9fca39eebe50 python/registerallocator.py
--- a/python/registerallocator.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/registerallocator.py	Sun Sep 29 14:08:15 2013 +0200
@@ -1,125 +1,193 @@
 from flowgraph import FlowGraph
 from interferencegraph import InterferenceGraph
 
+# Nifty first function:
+first = lambda x: next(iter(x))
 
 class RegisterAllocator:
     """
         Target independent register allocator.
 
-        Algorithm is iterated .. (ITR) by Appel and George
+        Algorithm is iterated register coalescing by Appel and George.
+
+        Chaitin's algorithm: remove all nodes with less than K neighbours.
+        These nodes can be colored when added back.
 
         The process consists of the following steps:
         - build interference graph from the instruction list
+        - remove low degree non move related nodes.
         - (optional) coalesc registers to remove redundant moves
         - (optional) spill registers
         - select registers
     """
-    def __init__(self):
+
+    def InitData(self, f):
+        self.f = f
+        # Register information:
+        self.regs = set(f.regs)
+        self.K = len(self.regs)
+
+        # Move related sets:
+        self.coalescedMoves = set()
+        self.constrainedMoves = set()
+        self.frozenMoves = set()
+        self.activeMoves = set()
+        self.worklistMoves = set()
+
+    def Build(self):
+        """ 1. Construct interference graph from instruction list """
+        self.f.cfg = FlowGraph(self.f.instructions)
+        self.f.ig = InterferenceGraph(self.f.cfg)
+        self.Node = self.f.ig.getNode
+
+        # Divide nodes into pre-colored and initial:
+        pre_tmp = list(self.f.tempMap.keys())
+        self.precolored = set(self.Node(tmp) for tmp in pre_tmp)
+        self.workSet = set(self.f.ig.nodes - self.precolored)
+
+        # Make degree table:
+        for n in self.precolored:
+            n.addDegree = 100 + len(self.f.ig.nodes) + self.K
+
+        # Initialize color map:
+        self.color = {}
+        for tmp, c in self.f.tempMap.items():
+            self.color[self.Node(tmp)] = c
+        dict(self.f.tempMap) # start with pre-colored
+
+        self.moves = [i for i in self.f.instructions if i.ismove]
+        for mv in self.moves:
+            self.Node(mv.src[0]).moves.add(mv)
+            self.Node(mv.dst[0]).moves.add(mv)
+
+    def NodeMoves(self, n):
+        return n.moves & (self.activeMoves | self.worklistMoves)
+    
+    def MoveRelated(self, n):
+        return bool(self.NodeMoves(n))
+
+    @property
+    def SpillWorkSet(self):
+        c = lambda n: n.Degree >= self.K
+        return set(filter(c, self.workSet))
+
+    @property
+    def FreezeWorkSet(self):
+        c = lambda n: n.Degree < self.K and self.MoveRelated(n)
+        return set(filter(c, self.workSet))
+
+    @property
+    def SimplifyWorkSet(self):
+        c = lambda n: n.Degree < self.K and not self.MoveRelated(n)
+        return set(filter(c, self.workSet))
+
+    def makeWorkList(self):
+        """ Divide initial nodes into worklists """
+        self.selectStack = []
+
+        # Fill initial move set:
+        for m in self.moves:
+            self.worklistMoves.add(m)
+
+    def Simplify(self):
+        """ 2. Remove nodes from the graph """
+        n = first(self.SimplifyWorkSet)
+        self.workSet.remove(n)
+        self.selectStack.append(n)
+        # Pop out of graph:
+        self.f.ig.delNode(n)
+
+    def EnableMoves(self, nodes):
+        for n in nodes:
+            for m in self.NodeMoves(n):
+                if m in self.activeMoves:
+                    self.activeMoves.remove(m)
+                    self.worklistMoves.add(m)
+                
+    def Coalesc(self):
+        """ Coalesc conservative. """
+        m = first(self.worklistMoves)
+        x = self.Node(m.dst[0])
+        y = self.Node(m.src[0])
+        u, v = (y, x) if y in self.precolored else (x, y)
+        self.worklistMoves.remove(m)
+        if u is v:
+            self.coalescedMoves.add(m)
+        elif v in self.precolored or self.f.ig.hasEdge(u, v):
+            self.constrainedMoves.add(m)
+        elif u not in self.precolored and self.Conservative(u, v):
+            self.coalescedMoves.add(m)
+            self.workSet.remove(v)
+            self.f.ig.Combine(u, v)
+        else:
+            self.activeMoves.add(m)
+        
+    def Conservative(self, u, v):
+        """ Briggs conservative criteria for coalesc """
+        nodes = u.Adjecent | v.Adjecent
+        c = lambda n: n.Degree >= self.K
+        k = len(list(filter(c, nodes)))
+        return k < self.K
+
+    def Freeze(self):
+        """ Give up coalescing on some node """
+        u = first(self.FreezeWorkSet)
+        self.freezeMoves(u)
+
+    def freezeMoves(self, u):
+        """ Freeze moves for node u """
+        for m in self.NodeMoves(u):
+            if m in self.activeMoves:
+                self.activeMoves.remove(m)
+            else:
+                sekf.worklistMoves.remove(m)
+            self.frozenMoves.add(m)
+            # Check other part of the move for still being move related:
+            v = m.src[0] if u is m.dst[0] else m.dst[0]
+    
+    def SelectSpill(self):
+        # TODO
         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 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]
-            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
-
+    def AssignColors(self):
+        """ Add nodes back to the graph to color it. """
         # Add nodes back to the graph: 
-        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)
+        while self.selectStack:
+            n = self.selectStack.pop(-1)
+            self.f.ig.addNode(n)
+            takenregs = set(self.color[m] for m in n.Adjecent)
+            okColors = self.regs - takenregs
+            if okColors:
+                self.color[n] = first(okColors)
+            else:
+                raise NotImplementedError('Spill required here!')
+        
+    def ApplyColors(self):
+        # Remove coalesced moves:
+        for mv in self.coalescedMoves:
+            self.f.instructions.remove(mv)
         # Use allocated registers:
-        lookup = lambda t: regMap[t]
-        for i in f.instructions:
+        lookup = lambda t: self.color[self.Node(t)]
+        for i in self.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
-        #self.coalesc(f) # Optional!
-        self.select(f)
+        self.InitData(f)
+        self.Build()
+        self.makeWorkList()
+        while True:
+            if self.SimplifyWorkSet:
+                self.Simplify()
+            elif self.worklistMoves:
+                self.Coalesc()
+            elif self.FreezeWorkSet:
+                self.Freeze()
+            elif self.SpillWorkSet:
+                raise NotImplementedError('Spill not implemented')
+            else:
+                break # Done!
+        self.AssignColors()
+        self.ApplyColors()
 
diff -r 046017431c6a -r 9fca39eebe50 python/tcodegen.py
--- a/python/tcodegen.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/tcodegen.py	Sun Sep 29 14:08:15 2013 +0200
@@ -75,6 +75,19 @@
    ab(ab(a, b) + ab(9,b), 0);
 }
 """
+
+testsrc = """
+package test3;
+
+function int ab(int a, int b)
+{
+  var int c;
+  c = 0;
+  c = c + a + b;
+  return c; 
+}
+
+"""
 def dump_cfg(cga, cfg_file):
     print('digraph G {', file=cfg_file)
     #print('edge [constraint=none]', file=cfg_file)
@@ -107,23 +120,23 @@
     if not irc:
         diag.printErrors(testsrc)
     irc.check()
-    irc.dump()
+    #irc.dump()
     with open('ir.gv', 'w') as f:
         ir.dumpgv(irc, f)
     outs = outstream.TextOutputStream()
     cga = codegenarm.ArmCodeGenerator(outs)
     ir2 = cga.generate(irc)
 
-    with open('cfg.gv', 'w') as cfg_file:
-        dump_cfg(cga, cfg_file)
+    #with open('cfg.gv', 'w') as cfg_file:
+    #    dump_cfg(cga, cfg_file)
 
-    with open('ig.gv', 'w') as ig_file:
-        dump_ig(cga, ig_file)
+    #with open('ig.gv', 'w') as ig_file:
+    #    dump_ig(cga, ig_file)
         
-    for f in ir2:
-        print(f)
-        for i in f.instructions:
-            print('   {}'.format(i))
+    #for f in ir2:
+    #    print(f)
+    #    for i in f.instructions:
+    #        print('   {}'.format(i))
 
     outs.dump()
 
diff -r 046017431c6a -r 9fca39eebe50 python/testgraph.py
--- a/python/testgraph.py	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/testgraph.py	Sun Sep 29 14:08:15 2013 +0200
@@ -5,9 +5,11 @@
 
 class GraphTestCase(unittest.TestCase):
     def testEdge(self):
-        g = graph.Graph(False)
-        n1 = g.newNode()
-        n2 = g.newNode()
+        g = graph.Graph()
+        n1 = graph.Node(g)
+        g.addNode(n1)
+        n2 = graph.Node(g)
+        g.addNode(n2)
         g.addEdge(n1, n2)
         self.assertTrue(g.hasEdge(n2, n1))
         self.assertTrue(g.hasEdge(n1, n2))
@@ -15,10 +17,13 @@
         g.delNode(n2)
 
     def testDegree(self):
-        g = graph.Graph(False)
-        n1 = g.newNode()
-        n2 = g.newNode()
-        n3 = g.newNode()
+        g = graph.Graph()
+        n1 = graph.Node(g)
+        g.addNode(n1)
+        n2 = graph.Node(g)
+        g.addNode(n2)
+        n3 = graph.Node(g)
+        g.addNode(n3)
         g.addEdge(n1, n2)
         g.addEdge(n1, n3)
         self.assertEqual(2, n1.Degree)
diff -r 046017431c6a -r 9fca39eebe50 python/trunner2.sh
--- a/python/trunner2.sh	Thu Sep 26 21:14:25 2013 +0200
+++ b/python/trunner2.sh	Sun Sep 29 14:08:15 2013 +0200
@@ -5,9 +5,9 @@
   python tcodegen.py
 
   # Create svg from dot file:
-  dot -Tpdf -o ir.pdf ir.gv
-  dot -Tpdf -o cfg.pdf cfg.gv
-  dot -Tpdf -o ig.pdf ig.gv
+  # dot -Tpdf -o ir.pdf ir.gv
+  #dot -Tpdf -o cfg.pdf cfg.gv
+  #dot -Tpdf -o ig.pdf ig.gv
   echo "Awaiting changes in $DIR"
   inotifywait -r -e modify $DIR
 done