--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/python/ppci/codegen/interferencegraph.py	Thu Dec 05 17:02:38 2013 +0100
@@ -0,0 +1,89 @@
+from .graph import Graph, Node
+
+
+class InterferenceGraphNode(Node):
+    def __init__(self, g, varname):
+        super().__init__(g)
+        self.temps = [varname]
+        self.moves = set()
+        self.color = None
+
+    def __repr__(self):
+        return '{}({})'.format(self.temps, self.color)
+
+
+class InterferenceGraph(Graph):
+    """
+        Interference graph.
+    """
+    def __init__(self, flowgraph):
+        """ Create a new interference graph from a flowgraph """
+        super().__init__()
+        # 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 to_dot(self, f):
+        """ Generate graphviz dot representation """
+        for n in self.nodes:
+            print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f)
+        for n, m in self.edges:
+            print('{} -> {};'.format(id(n), id(m)), file=f)
+
+    def to_txt(self):
+        for node in self.nodes:
+            print('{} interferes: {}'.format(node, node.Adjecent))
+
+    def getNode(self, tmp):
+        # 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):
+        """ Combine n and m into n """
+        n.temps.extend(m.temps)
+        n.moves.update(m.moves)
+        # Reroute all edges:
+        e1 = [e for e in self.edges if e[0] is m]
+        e2 = [e for e in self.edges if e[1] is m]
+        for e in e1:
+            self.edges.remove(e)
+            self.addEdge(n, e[1])
+        for e in e2:
+            self.edges.remove(e)
+            self.addEdge(n, e[0])
+        # Remove node m:
+        self.delNode(m)