--- a/python/c3/codegenerator.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/c3/codegenerator.py	Mon Apr 22 23:54:54 2013 +0200
@@ -124,15 +124,17 @@
       if type(expr) is astnodes.Binop:
          ra = self.genExprCode(expr.a)
          rb = self.genExprCode(expr.b)
-         tmp = self.builder.newTmp()
-         ops = ['+', '-', '*', '/', 'and', 'or']
+         ops = ['+', '-', '*', '/']
          if expr.op in ops:
+            tmpnames = {'+':'addtmp', '-':'subtmp', '*': 'multmp', '/':'divtmp'}
+            tmp = self.builder.newTmp(tmpnames[expr.op])
             op = expr.op
             ins = ir.BinaryOperator(tmp, op, ra, rb)
             self.builder.addIns(ins)
             return tmp
          else:
             print('Unknown {0}'.format(expr))
+            tmp = self.builder.newTmp()
             # TODO
             return tmp
       elif type(expr) is astnodes.Constant:

--- a/python/ir/basicblock.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/ir/basicblock.py	Mon Apr 22 23:54:54 2013 +0200
@@ -41,10 +41,15 @@
    def getSuccessors(self):
       if not self.Empty:
          i = self.LastInstruction
+         print(i)
          return i.Targets
       return []
    Successors = property(getSuccessors)
    def getPredecessors(self):
-      return []
+      preds = []
+      for bb in self.parent.BasicBlocks:
+         if self in bb.Successors:
+            preds.append(bb)
+      return preds
    Predecessors = property(getPredecessors)
 

--- a/python/ir/function.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/ir/function.py	Mon Apr 22 23:54:54 2013 +0200
@@ -9,6 +9,10 @@
       return 'Function {0}'.format(self.name)
    def addBB(self, bb):
       self.bbs.append(bb)
+      bb.parent = self
+   def removeBasicBlock(self, bb):
+      self.bbs.remove(bb)
+      bb.parent = None
    def getBBs(self):
       return self.bbs
    BasicBlocks = property(getBBs)

--- a/python/ir/instruction.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/ir/instruction.py	Mon Apr 22 23:54:54 2013 +0200
@@ -43,9 +43,13 @@
    def setParent(self, p):
       self.parent = p
    Parent = property(getParent, setParent)
+
+class Terminator(Instruction):
    @property
    def Targets(self):
       return self.getTargets()
+   def changeTarget(self, tfrom, tto):
+      pass
 
 # Function calling:
 class Call(Instruction):
@@ -69,7 +73,7 @@
       args = ','.join([str(arg) for arg in self.arguments])
       return pfx + '{0}({1})'.format(self.callee.name, args)
 
-class Return(Instruction):
+class Return(Terminator):
    def __init__(self, value=None):
       super().__init__()
       self.value = value
@@ -143,7 +147,7 @@
       return '[{0}] = {1}'.format(self.location, self.value)
 
 # Branching:
-class Branch(Instruction):
+class Branch(Terminator):
    def __init__(self, target):
       super().__init__()
       assert type(target) is BasicBlock
@@ -152,8 +156,11 @@
       return 'BRANCH {0}'.format(self.target)
    def getTargets(self):
       return [self.target]
+   def changeTarget(self, tfrom, tto):
+      if tfrom is self.target:
+         self.target = tto
 
-class ConditionalBranch(Instruction):
+class ConditionalBranch(Terminator):
    def __init__(self, a, cond, b, lab1, lab2):
       super().__init__()
       self.a = a
@@ -171,6 +178,11 @@
       return 'IF {0} {1} {2} THEN {3} ELSE {4}'.format(self.a, self.cond, self.b, self.lab1, self.lab2)
    def getTargets(self):
       return [self.lab1, self.lab2]
+   def changeTarget(self, tfrom, tto):
+      if tfrom is self.lab1:
+         self.lab1 = tto
+      if tfrom is self.lab2:
+         self.lab2 = tto
 
 class PhiNode(Instruction):
    def __init__(self):

--- a/python/ir/module.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/ir/module.py	Mon Apr 22 23:54:54 2013 +0200
@@ -45,6 +45,11 @@
             outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents))
             for successor in bb.Successors:
                outf.write('"{0}" -> "{1}"\n'.format(id(bb), id(successor)))
+            # Draw dags if any:
+            if hasattr(bb, 'dag'):
+               outf.write('{0} -> {1}\n'.format(id(bb), id(bb.dag)))
+               bb.dag.dumpgv(outf)
+
          outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry)))
       outf.write('}\n')
 

--- a/python/testir.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/testir.py	Mon Apr 22 23:54:54 2013 +0200
@@ -34,6 +34,8 @@
    //   return y - 33;
    //}
 
+   res = res + (x + 2 * y) + (x + 2 * y) + (2*8) + (2*8);
+
    if (x > 13)
    {
       while (y > 1337)
@@ -57,10 +59,14 @@
    cf = transform.ConstantFolder()
    dcd = transform.DeadCodeDeleter()
    m2r = transform.Mem2RegPromotor()
+   clr = transform.CleanPass()
    ir.check()
    cf.run(ir)
    dcd.run(ir)
+   clr.run(ir)
    m2r.run(ir)
+   for bb in ir.BasicBlocks:
+      bb.dag = x86.Dag(bb)
    #ir.dump()
 
    # Dump a graphiz file:

--- a/python/transform.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/transform.py	Mon Apr 22 23:54:54 2013 +0200
@@ -77,6 +77,21 @@
          otherUse = True
    return True
 
+class CleanPass(FunctionPass):
+   def onFunction(self, f):
+      bbs = list(f.BasicBlocks)
+      for bb in bbs:
+         # TODO: determine check for 'empty'
+         if len(bb.Instructions) == 1:
+            # This block is empty.
+            # find predecessors of this block and replace this block reference with the jumped reference.
+            ins = bb.LastInstruction
+            if type(ins) is Branch:
+               print(ins, bb.Predecessors)
+               for pred in bb.Predecessors:
+                  pred.LastInstruction.changeTarget(bb, ins.target)
+            f.removeBasicBlock(bb)
+
 class Mem2RegPromotor(FunctionPass):
    def onFunction(self, f):
       # TODO

--- a/python/x86.py	Sat Apr 20 12:00:51 2013 +0200
+++ b/python/x86.py	Mon Apr 22 23:54:54 2013 +0200
@@ -2,6 +2,63 @@
 import ir
 import registerallocator
 
+# 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
+
+# x86 specific:
 class AsmLabel:
    def __init__(self, lab):
       self.lab = lab
@@ -34,6 +91,7 @@
    def genBin(self, ir):
       self.asm = []
       # Allocate registers:
+      insSelect(ir)
       ra = registerallocator.RegisterAllocator()
       # TODO: do not register allocate on intermediate code:
       ra.registerAllocate(ir, self.regs)