--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/python/dag.py	Sun May 26 15:28:07 2013 +0200
@@ -0,0 +1,57 @@
+
+# Instruction selection with DAG (Directed Acyclic Graph)
+class DagLeaf:
+   def __init__(self, v):
+      self.v = v
+
+class DagNode:
+   def __init__(self, name):
+      self.name = name
+      self.children = []
+   def __repr__(self):
+      return str(self.name)
+
+class Dag:
+   def __init__(self, bb):
+      self.mapping = {}
+      self.buildFromBB(bb)
+   def buildFromBB(self, bb):
+      for ins in bb.Instructions:
+         if type(ins) is ir.BinaryOperator:
+            if not ins.value1 in self.mapping:
+               self.mapping[ins.value1] = DagNode(ins.value1)
+            if not ins.value2 in self.mapping:
+               self.mapping[ins.value2] = DagNode(ins.value2)
+            # look for op with left and right operand the same:
+            N = None
+            lnode = self.mapping[ins.value1]
+            rnode = self.mapping[ins.value2]
+            for node in self.mapping.values():
+               if node.name == ins.operation:
+                  if node.children[0] == lnode and node.children[1] == rnode:
+                     N = node
+                     break
+            if not N:
+               # Create a node.
+               N = DagNode(ins.operation)
+               N.children.append(lnode)
+               N.children.append(rnode)
+            self.mapping[ins.result] = N
+         else:
+            pass
+   def dumpgv(self, outf):
+      outf.write('subgraph {0} {{\n'.format(id(self)))
+      for node in self.mapping.values():
+         outf.write('{0} [label="{1}"];\n'.format(id(node), node.name))
+         for c in node.children:
+            outf.write('{0} -> {1};\n'.format(id(node), id(c)))
+      outf.write('label="dag"}\n')
+
+def insSelect(mod):
+   """ Create DAG from ir-code """
+   for bb in mod.BasicBlocks:
+      print(bb)
+      dag = Dag(bb)
+      print(dag.mapping)
+      bb.dag = dag
+