--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/python/interferencegraph.py	Thu Sep 26 21:14:25 2013 +0200
@@ -0,0 +1,69 @@
+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):
+    """
+        Interference graph.
+    """
+    def __init__(self, flowgraph):
+        """ 
+            Create a new interference graph from a flowgraph 
+        """
+        super().__init__(False)
+        # 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.addNode(n)
+        return n
+
+    def combine(self, n, m):
+        self.nodes.remove(m)
+        n.varnames.extend(m.varnames)