# 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