IR: add simplifier

6 files changed, 516 insertions, 291 deletions

diff --git a/example/disasm/full.py b/example/disasm/full.py
index 42d50216..19036882 100644
--- a/example/disasm/full.py
+++ b/example/disasm/full.py
@@ -6,17 +6,13 @@ from miasm2.analysis.binary import Container
 from miasm2.core.asmblock import log_asmblock, AsmCFG
 from miasm2.core.interval import interval
 from miasm2.analysis.machine import Machine
-from miasm2.analysis.data_flow import dead_simp, DiGraphDefUse, \
-    ReachingDefinitions, merge_blocks, remove_empty_assignblks, \
-    PropagateExpr, replace_stack_vars, load_from_int, \
-    del_unused_edges
+from miasm2.analysis.data_flow import dead_simp, \
+    DiGraphDefUse, ReachingDefinitions, \
+    replace_stack_vars, load_from_int, del_unused_edges
 from miasm2.expression.simplifications import expr_simp
 from miasm2.analysis.ssa import SSADiGraph
-from miasm2.analysis.outofssa import UnSSADiGraph
-from miasm2.analysis.data_flow import DiGraphLivenessSSA
 from miasm2.ir.ir import AssignBlock, IRBlock
-
-
+from miasm2.analysis.simplifier import IRCFGSimplifierCommon, IRCFGSimplifierSSA
 
 log = logging.getLogger("dis")
 console_handler = logging.StreamHandler()
@@ -207,7 +203,6 @@ open('lines.dot', 'w').write('\n'.join([str(l) for l in all_lines]))
 log.info('total lines %s' % total_l)
 
 
-
 if args.propagexpr:
     args.gen_ir = True
 
@@ -240,6 +235,9 @@ if args.gen_ir:
 
     ir_arch.blocks = {}
     ir_arch_a.blocks = {}
+
+    head = list(entry_points)[0]
+
     for ad, asmcfg in all_funcs_blocks.items():
         log.info("generating IR... %x" % ad)
         for block in asmcfg.blocks:
@@ -257,8 +255,9 @@ if args.gen_ir:
         print block
 
     if args.simplify > 0:
-        log.info("dead simp...")
-        dead_simp(ir_arch_a, ircfg_a)
+        log.info("Simplify...")
+        ircfg_simplifier = IRCFGSimplifierCommon(ir_arch_a)
+        ircfg_simplifier.simplify(ircfg_a, head)
         log.info("ok...")
 
     if args.defuse:
@@ -270,30 +269,14 @@ if args.gen_ir:
     out = ircfg_a.dot()
     open('graph_irflow.dot', 'w').write(out)
 
-    if args.simplify > 1:
-
-        ircfg_a.simplify(expr_simp)
-        modified = True
-        while modified:
-            modified = False
-            modified |= dead_simp(ir_arch_a, ircfg_a)
-            modified |= remove_empty_assignblks(ircfg_a)
-
-        open('graph_irflow_reduced.dot', 'w').write(ircfg_a.dot())
-
     if args.ssa and not args.propagexpr:
         if len(entry_points) != 1:
             raise RuntimeError("Your graph should have only one head")
-        head = list(entry_points)[0]
         ssa = SSADiGraph(ircfg_a)
         ssa.transform(head)
-
         open("ssa.dot", "wb").write(ircfg_a.dot())
 
 
-
-
-
 if args.propagexpr:
     class IRAOutRegs(ira):
         def get_out_regs(self, block):
@@ -324,8 +307,6 @@ if args.propagexpr:
 
 
 
-    ir_arch_a = IRAOutRegs(mdis.loc_db)
-
     def is_addr_ro_variable(bs, addr, size):
         """
         Return True if address at @addr is a read-only variable.
@@ -341,118 +322,21 @@ if args.propagexpr:
             return False
         return True
 
+    ir_arch_a = IRAOutRegs(mdis.loc_db)
 
-    ir_arch_a.ssa_var = {}
-    index = 0
-    modified = True
-    ssa_forbidden_regs = set([
-        ir_arch_a.pc,
-        ir_arch_a.IRDst,
-        ir_arch_a.arch.regs.exception_flags
-    ])
 
-    head = list(entry_points)[0]
-    heads = set([head])
-    all_ssa_vars = {}
+    class CustomIRCFGSimplifierSSA(IRCFGSimplifierSSA):
+        def do_simplify(self, ssa, head):
+            modified = super(CustomIRCFGSimplifierSSA, self).do_simplify(ssa, head)
+            if args.loadint:
+                modified |= load_from_int(ssa.graph, bs, is_addr_ro_variable)
+            if args.stack2var:
+                modified |= replace_stack_vars(self.ir_arch, ssa)
+            return modified
 
-    propagate_expr = PropagateExpr()
-    ssa_variable_to_expr = {}
 
-    while modified:
-        ssa = SSADiGraph(ircfg_a)
-        ssa.immutable_ids.update(ssa_forbidden_regs)
-        ssa.ssa_variable_to_expr.update(all_ssa_vars)
-        ssa.transform(head)
-        all_ssa_vars.update(ssa.ssa_variable_to_expr)
-
-        if args.verbose > 3:
-            open("ssa_%d.dot" % index, "wb").write(ircfg_a.dot())
-
-        ir_arch_a.ssa_var.update(ssa.ssa_variable_to_expr)
-        if args.verbose > 3:
-            open("ssa_orig.dot", "wb").write(ircfg_a.dot())
-
-        while modified:
-            log.debug('Loop %d', index)
-            index += 1
-            modified = False
-            if args.verbose > 3:
-                open('tmp_before_%d.dot' % index, 'w').write(ircfg_a.dot())
-            modified |= propagate_expr.propagate(ssa, head)
-            if args.verbose > 3:
-                open('tmp_adter_%d.dot' % index, 'w').write(ircfg_a.dot())
-            modified |= ircfg_a.simplify(expr_simp)
-            if args.verbose > 3:
-                open('tmp_simp_%d.dot' % index, 'w').write(ircfg_a.dot())
-            simp_modified = True
-            while simp_modified:
-                index += 1
-                if args.verbose > 3:
-                    open('tmp_before_%d.dot' % index, 'w').write(ircfg_a.dot())
-                simp_modified = False
-                log.info("dead simp...")
-                simp_modified |= dead_simp(ir_arch_a, ircfg_a)
-                log.info("ok...")
-
-                index += 1
-                if args.verbose > 3:
-                    open('tmp_after_%d.dot' % index, 'w').write(ircfg_a.dot())
-                simp_modified |= remove_empty_assignblks(ircfg_a)
-                simp_modified |= del_unused_edges(ircfg_a, heads)
-                simp_modified |= merge_blocks(ircfg_a, heads)
-
-                if args.loadint:
-                    simp_modified |= load_from_int(ircfg_a, bs, is_addr_ro_variable)
-                modified |= simp_modified
-                index += 1
-        if args.verbose > 3:
-            open('stack_%d.dot' % index, 'w').write(ircfg_a.dot())
-        if args.stack2var:
-            modified |= replace_stack_vars(ir_arch_a, ssa)
-
-    if args.verbose > 3:
-        open('final_pre.dot', 'w').write(ircfg_a.dot())
-
-    if args.verbose > 3:
-        open('final_merge.dot', 'w').write(ircfg_a.dot())
-    ssa = SSADiGraph(ircfg_a)
-    ssa.immutable_ids.update(ssa_forbidden_regs)
-    ssa.ssa_variable_to_expr.update(all_ssa_vars)
-    ssa.transform(head)
-    print '*'*80, "Remove phi"
-    if args.verbose > 3:
-        open('final_ssa.dot', 'w').write(ircfg_a.dot())
-
-    cfg_liveness = DiGraphLivenessSSA(ircfg_a)
-    cfg_liveness.init_var_info(ir_arch_a)
-    cfg_liveness.compute_liveness()
-
-    unssa = UnSSADiGraph(ssa, head, cfg_liveness)
-
-    if args.verbose > 3:
-        open('final_no_phi.dot', 'w').write(ircfg_a.dot())
-
-    modified = True
-    while modified:
-        log.debug('Loop %d', index)
-        index += 1
-        modified = False
-        modified |= ircfg_a.simplify(expr_simp)
-        if args.verbose > 3:
-            open('tmp_simp_%d.dot' % index, 'w').write(ircfg_a.dot())
-        simp_modified = True
-        while simp_modified:
-            index += 1
-            if args.verbose > 3:
-                open('tmp_before_%d.dot' % index, 'w').write(ircfg_a.dot())
-            simp_modified = False
-            simp_modified |= dead_simp(ir_arch_a, ircfg_a)
-            index += 1
-            if args.verbose > 3:
-                open('tmp_after_%d.dot' % index, 'w').write(ircfg_a.dot())
-            simp_modified |= remove_empty_assignblks(ircfg_a)
-            simp_modified |= merge_blocks(ircfg_a, heads)
-            modified |= simp_modified
-            index += 1
-
-    open('final.dot', 'w').write(ircfg_a.dot())
+    head = list(entry_points)[0]
+    ir_arch_a = IRAOutRegs(mdis.loc_db)
+    simplifier = CustomIRCFGSimplifierSSA(ir_arch_a)
+    ircfg = simplifier.simplify(ircfg_a, head)
+    open('final.dot', 'w').write(ircfg.dot())
diff --git a/example/ida/graph_ir.py b/example/ida/graph_ir.py
index f9c61c2c..8026174d 100644
--- a/example/ida/graph_ir.py
+++ b/example/ida/graph_ir.py
@@ -10,16 +10,9 @@ from miasm2.core.asmblock import is_int
 from miasm2.core.bin_stream_ida import bin_stream_ida
 from miasm2.expression.simplifications import expr_simp
 from miasm2.ir.ir import IRBlock, AssignBlock
-
-from miasm2.analysis.ssa import SSADiGraph, UnSSADiGraph
-
-from miasm2.analysis.data_flow import dead_simp,  \
-    merge_blocks, remove_empty_assignblks, \
-    PropagateExpr, load_from_int, \
-    DiGraphLivenessSSA
-
-
+from miasm2.analysis.data_flow import load_from_int
 from utils import guess_machine, expr2colorstr
+from miasm2.analysis.simplifier import IRCFGSimplifierCommon, IRCFGSimplifierSSA
 
 
 
@@ -251,15 +244,11 @@ def build_graph(start_addr, type_graph, simplify=False, dontmodstack=True, loadi
     title = "Miasm IR graph"
 
 
+    head = list(entry_points)[0]
+
     if simplify:
-        dead_simp(ir_arch, ircfg)
-        ircfg.simplify(expr_simp)
-        modified = True
-        while modified:
-            modified = False
-            modified |= dead_simp(ir_arch, ircfg)
-            modified |= remove_empty_assignblks(ircfg)
-            modified |= merge_blocks(ircfg, entry_points)
+        ircfg_simplifier = IRCFGSimplifierCommon(ir_arch)
+        ircfg_simplifier.simplify(ircfg, head)
         title += " (simplified)"
 
     if type_graph == TYPE_GRAPH_IR:
@@ -267,8 +256,6 @@ def build_graph(start_addr, type_graph, simplify=False, dontmodstack=True, loadi
         graph.Show()
         return
 
-    head = list(entry_points)[0]
-
 
     class IRAOutRegs(ira):
         def get_out_regs(self, block):
@@ -299,86 +286,38 @@ def build_graph(start_addr, type_graph, simplify=False, dontmodstack=True, loadi
         new_irblock = IRBlock(irblock.loc_key, assignblks)
         ircfg.blocks[loc] = new_irblock
 
-    ir_arch = IRAOutRegs(mdis.loc_db)
-    ir_arch.ssa_var = {}
-    modified = True
-    ssa_forbidden_regs = set([
-        ir_arch.pc,
-        ir_arch.IRDst,
-        ir_arch.arch.regs.exception_flags
-    ])
 
-    head = list(entry_points)[0]
-    heads = set([head])
-    all_ssa_vars = {}
-
-    propagate_expr = PropagateExpr()
+    class CustomIRCFGSimplifierSSA(IRCFGSimplifierSSA):
+        def do_simplify(self, ssa, head):
+            modified = super(CustomIRCFGSimplifierSSA, self).do_simplify(ssa, head)
+            if loadint:
+                modified |= load_from_int(ssa.graph, bs, is_addr_ro_variable)
+            return modified
 
-    ssa = SSADiGraph(ircfg)
-    ssa.immutable_ids.update(ssa_forbidden_regs)
-    ssa.ssa_variable_to_expr.update(all_ssa_vars)
-    ssa.transform(head)
-    all_ssa_vars.update(ssa.ssa_variable_to_expr)
+        def simplify(self, ircfg, head):
+            ssa = self.ircfg_to_ssa(ircfg, head)
+            ssa = self.do_simplify_loop(ssa, head)
 
-    ir_arch.ssa_var.update(ssa.ssa_variable_to_expr)
+            if type_graph == TYPE_GRAPH_IRSSA:
+                ret = ssa.graph
+            elif type_graph == TYPE_GRAPH_IRSSAUNSSA:
+                ircfg = self.ssa_to_unssa(ssa, head)
+                ircfg_simplifier = IRCFGSimplifierCommon(self.ir_arch)
+                ircfg_simplifier.simplify(ircfg, head)
+                ret = ircfg
+            else:
+                raise ValueError("Unknown option")
+            return ret
 
-    if simplify:
 
-        while modified:
-            ssa = SSADiGraph(ircfg)
-            ssa.immutable_ids.update(ssa_forbidden_regs)
-            ssa.ssa_variable_to_expr.update(all_ssa_vars)
-            ssa.transform(head)
-            all_ssa_vars.update(ssa.ssa_variable_to_expr)
-
-            ir_arch.ssa_var.update(ssa.ssa_variable_to_expr)
-
-            while modified:
-                modified = False
-                modified |= propagate_expr.propagate(ssa, head)
-                modified |= ircfg.simplify(expr_simp)
-                simp_modified = True
-                while simp_modified:
-                    simp_modified = False
-                    simp_modified |= dead_simp(ir_arch, ircfg)
-                    simp_modified |= remove_empty_assignblks(ircfg)
-                    simp_modified |= load_from_int(ircfg, bs, is_addr_ro_variable)
-                    modified |= simp_modified
-
-
-    ssa = SSADiGraph(ircfg)
-    ssa.immutable_ids.update(ssa_forbidden_regs)
-    ssa.ssa_variable_to_expr.update(all_ssa_vars)
-    ssa.transform(head)
-    all_ssa_vars.update(ssa.ssa_variable_to_expr)
-
-    if type_graph == TYPE_GRAPH_IRSSA:
-        graph = GraphMiasmIR(ssa.graph, title, None)
-        graph.Show()
-        return
+    head = list(entry_points)[0]
+    simplifier = CustomIRCFGSimplifierSSA(ir_arch)
+    ircfg = simplifier.simplify(ircfg, head)
+    open('final.dot', 'w').write(ircfg.dot())
 
-    if type_graph == TYPE_GRAPH_IRSSAUNSSA:
-
-        cfg_liveness = DiGraphLivenessSSA(ssa.graph)
-        cfg_liveness.init_var_info(ir_arch)
-        cfg_liveness.compute_liveness()
-
-        UnSSADiGraph(ssa, head, cfg_liveness)
-        if simplify:
-            modified = True
-            while modified:
-                modified = False
-                modified |= ssa.graph.simplify(expr_simp)
-                simp_modified = True
-                while simp_modified:
-                    simp_modified = False
-                    simp_modified |= dead_simp(ir_arch, ssa.graph)
-                    simp_modified |= remove_empty_assignblks(ssa.graph)
-                    simp_modified |= merge_blocks(ssa.graph, heads)
-                    modified |= simp_modified
-        graph = GraphMiasmIR(ssa.graph, title, None)
-        graph.Show()
 
+    graph = GraphMiasmIR(ircfg, title, None)
+    graph.Show()
 
 def function_graph_ir():
     # Get settings
diff --git a/miasm2/analysis/data_flow.py b/miasm2/analysis/data_flow.py
index 53033d7e..fb09a6cb 100644
--- a/miasm2/analysis/data_flow.py
+++ b/miasm2/analysis/data_flow.py
@@ -11,6 +11,7 @@ from miasm2.expression.expression_helper import possible_values
 from miasm2.analysis.ssa import get_phi_sources_parent_block, \
     irblock_has_phi
 
+
 class ReachingDefinitions(dict):
     """
     Computes for each assignblock the set of reaching definitions.
@@ -510,17 +511,19 @@ def remove_empty_assignblks(ircfg):
     modified = False
     for loc_key, block in ircfg.blocks.iteritems():
         irs = []
+        block_modified = False
         for assignblk in block:
             if len(assignblk):
                 irs.append(assignblk)
             else:
-                modified = True
-        ircfg.blocks[loc_key] = IRBlock(loc_key, irs)
-
+                block_modified = True
+        if block_modified:
+            new_irblock = IRBlock(loc_key, irs)
+            ircfg.blocks[loc_key] = new_irblock
+            modified = True
     return modified
 
 
-
 class SSADefUse(DiGraph):
     """
     Generate DefUse information from SSA transformation
@@ -635,17 +638,16 @@ def expr_has_call(expr):
     return expr_test_visit(expr, expr_has_call_test)
 
 
-class PropagateExpr(object):
-
-    def assignblk_is_propagation_barrier(self, assignblk):
-        for dst, src in assignblk.iteritems():
-            if expr_has_call(src):
-                return True
-            if dst.is_mem():
-                return True
-        return False
+class PropagateThroughExprId(object):
+    """
+    Propagate expressions though ExprId
+    """
 
     def has_propagation_barrier(self, assignblks):
+        """
+        Return True if propagation cannot cross the @assignblks
+        @assignblks: list of AssignBlock to check
+        """
         for assignblk in assignblks:
             for dst, src in assignblk.iteritems():
                 if expr_has_call(src):
@@ -655,13 +657,19 @@ class PropagateExpr(object):
         return False
 
     def is_mem_written(self, ssa, node, successor):
+        """
+        Return True if memory is written at least once between @node and
+        @successor
+
+        @node: Location of the block to start with
+        @successor: Location of last block
+        """
         loc_a, index_a, reg_a = node
         loc_b, index_b, reg_b = successor
         block_b = ssa.graph.blocks[loc_b]
 
         nodes_to_do = self.compute_reachable_nodes_from_a_to_b(ssa.graph, loc_a, loc_b)
 
-
         if loc_a == loc_b:
             # src is dst
             assert nodes_to_do == set([loc_a])
@@ -703,7 +711,7 @@ class PropagateExpr(object):
             return False
         return True
 
-    def propagate(self, ssa, head):
+    def get_candidates(self, ssa, head, max_expr_depth):
         defuse = SSADefUse.from_ssa(ssa)
         to_replace = {}
         node_to_reg = {}
@@ -717,9 +725,20 @@ class PropagateExpr(object):
                 continue
             if node.var.is_mem():
                 continue
+            if max_expr_depth is not None and len(str(src)) > max_expr_depth:
+                continue
             to_replace[node.var] = src
             node_to_reg[node] = node.var
+        return node_to_reg, to_replace, defuse
 
+    def propagate(self, ssa, head, max_expr_depth=None):
+        """
+        Do expression propagation
+        @ssa: SSADiGraph instance
+        @head: the head location of the graph
+        @max_expr_depth: the maximum allowed depth of an expression
+        """
+        node_to_reg, to_replace, defuse = self.get_candidates(ssa, head, max_expr_depth)
         modified = False
         for node, reg in node_to_reg.iteritems():
             for successor in defuse.successors(node):
@@ -741,8 +760,7 @@ class PropagateExpr(object):
                         continue
 
                     if src.is_mem():
-                        ptr = src.ptr
-                        ptr = ptr.replace_expr(replace)
+                        ptr = src.ptr.replace_expr(replace)
                         new_src = ExprMem(ptr, src.size)
                     else:
                         new_src = src.replace_expr(replace)
@@ -750,8 +768,7 @@ class PropagateExpr(object):
                     if dst.is_id():
                         new_dst = dst
                     elif dst.is_mem():
-                        ptr = dst.ptr
-                        ptr = ptr.replace_expr(replace)
+                        ptr = dst.ptr.replace_expr(replace)
                         new_dst = ExprMem(ptr, dst.size)
                     else:
                         new_dst = dst.replace_expr(replace)
@@ -764,6 +781,105 @@ class PropagateExpr(object):
                 assignblks[node_b.index] = out
                 new_block = IRBlock(block.loc_key, assignblks)
                 ssa.graph.blocks[block.loc_key] = new_block
+
+        return modified
+
+
+
+class PropagateExprIntThroughExprId(PropagateThroughExprId):
+    """
+    Propagate ExprInt though ExprId: classic constant propagation
+    This is a sub family of PropagateThroughExprId.
+    It reduces leaves in expressions of a program.
+    """
+
+    def get_candidates(self, ssa, head, max_expr_depth):
+        defuse = SSADefUse.from_ssa(ssa)
+
+        to_replace = {}
+        node_to_reg = {}
+        for node in defuse.nodes():
+            src = defuse.get_node_target(node)
+            if not src.is_int():
+                continue
+            if expr_has_call(src):
+                continue
+            if node.var.is_mem():
+                continue
+            to_replace[node.var] = src
+            node_to_reg[node] = node.var
+        return node_to_reg, to_replace, defuse
+
+    def propagation_allowed(self, ssa, to_replace, node_a, node_b):
+        """
+        Propagating ExprInt is always ok
+        """
+        return True
+
+
+class PropagateThroughExprMem(object):
+    """
+    Propagate through ExprMem in very simple cases:
+    - if no memory write between source and target
+    - if source does not contain any memory reference
+    """
+
+    def propagate(self, ssa, head, max_expr_depth=None):
+        ircfg = ssa.graph
+        todo = set()
+        modified = False
+        for block in ircfg.blocks.itervalues():
+            for i, assignblk in enumerate(block):
+                for dst, src in assignblk.iteritems():
+                    if not dst.is_mem():
+                        continue
+                    if expr_has_mem(src):
+                        continue
+                    todo.add((block.loc_key, i + 1, dst, src))
+                    ptr = dst.ptr
+                    for size in xrange(8, dst.size, 8):
+                        todo.add((block.loc_key, i + 1, ExprMem(ptr, size), src[:size]))
+
+        while todo:
+            loc_key, index, mem_dst, mem_src = todo.pop()
+            block = ircfg.blocks[loc_key]
+            assignblks = list(block)
+            block_modified = False
+            for i in xrange(index, len(block)):
+                assignblk = block[i]
+                write_mem = False
+                assignblk_modified = False
+                out = dict(assignblk)
+                out_new = {}
+                for dst, src in out.iteritems():
+                    if dst.is_mem():
+                        write_mem = True
+                    if dst != mem_dst and mem_dst in dst:
+                        dst = dst.replace_expr({mem_dst:mem_src})
+                    if mem_dst in src:
+                        src = src.replace_expr({mem_dst:mem_src})
+                    out_new[dst] = src
+                if out != out_new:
+                    assignblk_modified = True
+
+                if assignblk_modified:
+                    assignblks[i] = AssignBlock(out_new, assignblk.instr)
+                    block_modified = True
+                if write_mem:
+                    break
+            else:
+                # If no memory written, we may propagate to sons
+                # if son has only parent
+                for successor in ircfg.successors(loc_key):
+                    predecessors = ircfg.predecessors(successor)
+                    if len(predecessors) != 1:
+                        continue
+                    todo.add((successor, 0, mem_dst, mem_src))
+
+            if block_modified:
+                modified = True
+                new_block = IRBlock(block.loc_key, assignblks)
+                ircfg.blocks[block.loc_key] = new_block
         return modified
 
 
@@ -971,7 +1087,7 @@ def load_from_int(ir_arch, bs, is_addr_ro_variable):
     """
 
     modified = False
-    for label, block in ir_arch.blocks.iteritems():
+    for block in ir_arch.blocks.itervalues():
         assignblks = list()
         for assignblk in block:
             out = {}
diff --git a/miasm2/analysis/simplifier.py b/miasm2/analysis/simplifier.py
new file mode 100644
index 00000000..ca8e74fb
--- /dev/null
+++ b/miasm2/analysis/simplifier.py
@@ -0,0 +1,303 @@
+"""
+Apply simplification passes to an IR cfg
+"""
+
+import logging
+from functools import wraps
+from miasm2.analysis.ssa import SSADiGraph
+from miasm2.analysis.outofssa import UnSSADiGraph
+from miasm2.analysis.data_flow import DiGraphLivenessSSA
+from miasm2.expression.simplifications import expr_simp
+from miasm2.analysis.data_flow import dead_simp, \
+    merge_blocks, remove_empty_assignblks, \
+    PropagateExprIntThroughExprId, PropagateThroughExprId, \
+    PropagateThroughExprMem, del_unused_edges
+
+
+log = logging.getLogger("simplifier")
+console_handler = logging.StreamHandler()
+console_handler.setFormatter(logging.Formatter("%(levelname)-5s: %(message)s"))
+log.addHandler(console_handler)
+log.setLevel(logging.WARNING)
+
+
+def fix_point(func):
+    @wraps(func)
+    def ret_func(self, ircfg, head):
+        log.debug('[%s]: start', func.func_name)
+        has_been_modified = False
+        modified = True
+        while modified:
+            modified = func(self, ircfg, head)
+            has_been_modified |= modified
+        log.debug(
+            '[%s]: stop %r',
+            func.func_name,
+            has_been_modified
+        )
+        return has_been_modified
+    return ret_func
+
+
+class IRCFGSimplifier(object):
+    """
+    Simplify an IRCFG
+    This class applies passes until reaching a fix point
+    """
+
+    def __init__(self, ir_arch):
+        self.ir_arch = ir_arch
+        self.init_passes()
+
+    def init_passes(self):
+        """
+        Init the array of simplification passes
+        """
+        self.passes = []
+
+    @fix_point
+    def simplify(self, ircfg, head):
+        """
+        Apply passes until reaching a fix point
+        Return True if the graph has been modified
+
+        @ircfg: IRCFG instance to simplify
+        @head: Location instance of the ircfg head
+        """
+        modified = False
+        for simplify_pass in self.passes:
+            modified |= simplify_pass(ircfg, head)
+        return modified
+
+    def __call__(self, ircfg, head):
+        return self.simplify(ircfg, head)
+
+
+class IRCFGSimplifierCommon(IRCFGSimplifier):
+    """
+    Simplify an IRCFG
+    This class applies following passes until reaching a fix point:
+    - simplify_ircfg
+    - do_dead_simp_ircfg
+    """
+    def __init__(self, ir_arch, expr_simp=expr_simp):
+        self.expr_simp = expr_simp
+        super(IRCFGSimplifierCommon, self).__init__(ir_arch)
+
+    def init_passes(self):
+        self.passes = [
+            self.simplify_ircfg,
+            self.do_dead_simp_ircfg,
+        ]
+
+    @fix_point
+    def simplify_ircfg(self, ircfg, _head):
+        """
+        Apply self.expr_simp on the @ircfg until reaching fix point
+        Return True if the graph has been modified
+
+        @ircfg: IRCFG instance to simplify
+        """
+        modified = ircfg.simplify(self.expr_simp)
+        return modified
+
+    @fix_point
+    def do_dead_simp_ircfg(self, ircfg, head):
+        """
+        Apply:
+        - dead_simp
+        - remove_empty_assignblks
+        - merge_blocks
+        on the @ircfg until reaching fix point
+        Return True if the graph has been modified
+
+        @ircfg: IRCFG instance to simplify
+        @head: Location instance of the ircfg head
+        """
+        modified = dead_simp(self.ir_arch, ircfg)
+        modified |= remove_empty_assignblks(ircfg)
+        modified |= merge_blocks(ircfg, set([head]))
+        return modified
+
+
+class IRCFGSimplifierSSA(IRCFGSimplifierCommon):
+    """
+    Simplify an IRCFG.
+    The IRCF is first transformed in SSA, then apply transformations passes
+    and apply out-of-ssa. Final passes of IRcfgSimplifier are applied
+
+    This class apply following pass until reaching a fix point:
+    - do_propagate_int
+    - do_propagate_mem
+    - do_propagate_expr
+    - do_dead_simp_ssa
+    """
+
+    def __init__(self, ir_arch, expr_simp=expr_simp):
+        super(IRCFGSimplifierSSA, self).__init__(ir_arch, expr_simp)
+
+        self.ir_arch.ssa_var = {}
+        self.all_ssa_vars = {}
+
+        self.ssa_forbidden_regs = self.get_forbidden_regs()
+
+        self.propag_int = PropagateExprIntThroughExprId()
+        self.propag_expr = PropagateThroughExprId()
+        self.propag_mem = PropagateThroughExprMem()
+
+    def get_forbidden_regs(self):
+        """
+        Return a set of immutable register during SSA transformation
+        """
+        regs = set(
+            [
+                self.ir_arch.pc,
+                self.ir_arch.IRDst,
+                self.ir_arch.arch.regs.exception_flags
+            ]
+        )
+        return regs
+
+    def init_passes(self):
+        """
+        Init the array of simplification passes
+        """
+        self.passes = [
+            self.simplify_ssa,
+            self.do_propagate_int,
+            self.do_propagate_mem,
+            self.do_propagate_expr,
+            self.do_dead_simp_ssa,
+        ]
+
+    def ircfg_to_ssa(self, ircfg, head):
+        """
+        Apply the SSA transformation to @ircfg using it's @head
+
+        @ircfg: IRCFG instance to simplify
+        @head: Location instance of the ircfg head
+        """
+        ssa = SSADiGraph(ircfg)
+        ssa.immutable_ids.update(self.ssa_forbidden_regs)
+        ssa.ssa_variable_to_expr.update(self.all_ssa_vars)
+        ssa.transform(head)
+        self.all_ssa_vars.update(ssa.ssa_variable_to_expr)
+        self.ir_arch.ssa_var.update(ssa.ssa_variable_to_expr)
+        return ssa
+
+    def ssa_to_unssa(self, ssa, head):
+        """
+        Apply the out-of-ssa transformation to @ssa using it's @head
+
+        @ssa: SSADiGraph instance
+        @head: Location instance of the graph head
+        """
+        cfg_liveness = DiGraphLivenessSSA(ssa.graph)
+        cfg_liveness.init_var_info(self.ir_arch)
+        cfg_liveness.compute_liveness()
+
+        UnSSADiGraph(ssa, head, cfg_liveness)
+        return ssa.graph
+
+    @fix_point
+    def simplify_ssa(self, ssa, _head):
+        """
+        Apply self.expr_simp on the @ssa.graph until reaching fix point
+        Return True if the graph has been modified
+
+        @ssa: SSADiGraph instance
+        """
+        modified = ssa.graph.simplify(self.expr_simp)
+        return modified
+
+    @fix_point
+    def do_propagate_int(self, ssa, head):
+        """
+        Constant propagation in the @ssa graph
+        @head: Location instance of the graph head
+        """
+        modified = self.propag_int.propagate(ssa, head)
+        modified |= ssa.graph.simplify(self.expr_simp)
+        modified |= del_unused_edges(ssa.graph, set([head]))
+        return modified
+
+    @fix_point
+    def do_propagate_mem(self, ssa, head):
+        """
+        Propagation of expression based on ExprInt/ExprId in the @ssa graph
+        @head: Location instance of the graph head
+        """
+        modified = self.propag_mem.propagate(ssa, head)
+        modified |= ssa.graph.simplify(self.expr_simp)
+        modified |= del_unused_edges(ssa.graph, set([head]))
+        return modified
+
+    @fix_point
+    def do_propagate_expr(self, ssa, head):
+        """
+        Expressions propagation through ExprId in the @ssa graph
+        @head: Location instance of the graph head
+        """
+        modified = self.propag_expr.propagate(ssa, head)
+        modified |= ssa.graph.simplify(self.expr_simp)
+        modified |= del_unused_edges(ssa.graph, set([head]))
+        return modified
+
+    @fix_point
+    def do_dead_simp_ssa(self, ssa, head):
+        """
+        Apply:
+        - dead_simp
+        - remove_empty_assignblks
+        - del_unused_edges
+        - merge_blocks
+        on the @ircfg until reaching fix point
+        Return True if the graph has been modified
+
+        @ircfg: IRCFG instance to simplify
+        @head: Location instance of the ircfg head
+        """
+        modified = dead_simp(self.ir_arch, ssa.graph)
+        modified |= remove_empty_assignblks(ssa.graph)
+        modified |= del_unused_edges(ssa.graph, set([head]))
+        modified |= merge_blocks(ssa.graph, set([head]))
+        return modified
+
+    def do_simplify(self, ssa, head):
+        """
+        Apply passes until reaching a fix point
+        Return True if the graph has been modified
+        """
+        return super(IRCFGSimplifierSSA, self).simplify(ssa, head)
+
+    def do_simplify_loop(self, ssa, head):
+        """
+        Apply do_simplify until reaching a fix point
+        SSA is updated between each do_simplify
+        Return True if the graph has been modified
+        """
+        modified = True
+        while modified:
+            modified = self.do_simplify(ssa, head)
+            # Update ssa structs
+            ssa = self.ircfg_to_ssa(ssa.graph, head)
+        return ssa
+
+    def simplify(self, ircfg, head):
+        """
+        Apply SSA transformation to @ircfg
+        Apply passes until reaching a fix point
+        Apply out-of-ssa transformation
+        Apply post simplification passes
+
+        Updated simplified IRCFG instance and return it
+
+        @ircfg: IRCFG instance to simplify
+        @head: Location instance of the ircfg head
+        """
+        ssa = self.ircfg_to_ssa(ircfg, head)
+        ssa = self.do_simplify_loop(ssa, head)
+        ircfg = self.ssa_to_unssa(ssa, head)
+        ircfg_simplifier = IRCFGSimplifierCommon(self.ir_arch)
+        ircfg_simplifier.simplify(ircfg, head)
+        return ircfg
diff --git a/miasm2/analysis/ssa.py b/miasm2/analysis/ssa.py
index 5e1a872b..036d92ca 100644
--- a/miasm2/analysis/ssa.py
+++ b/miasm2/analysis/ssa.py
@@ -595,10 +595,11 @@ class SSADiGraph(SSA):
         # Replace non modified node used in phi with new variable
         self.ircfg.simplify(lambda expr:expr.replace_expr(var_to_newname))
 
-        irblock = self.ircfg.blocks[head]
-        assignblks = list(irblock)
-        assignblks[0:0] = [AssignBlock(newname_to_var, assignblks[0].instr)]
-        self.ircfg.blocks[head] = IRBlock(head, assignblks)
+        if newname_to_var:
+            irblock = self.ircfg.blocks[head]
+            assignblks = list(irblock)
+            assignblks[0:0] = [AssignBlock(newname_to_var, assignblks[0].instr)]
+            self.ircfg.blocks[head] = IRBlock(head, assignblks)
 
         # Updt structure
         for loc_key in self._phinodes:
diff --git a/test/analysis/unssa.py b/test/analysis/unssa.py
index ae9566ee..a796f3b6 100644
--- a/test/analysis/unssa.py
+++ b/test/analysis/unssa.py
@@ -1,14 +1,10 @@
 """ Test cases for dead code elimination"""
-from pdb import pm
-from pprint import pprint as pp
 from miasm2.expression.expression import ExprId, ExprInt, ExprAssign, ExprMem, \
-    ExprCond, ExprOp, ExprLoc
+    ExprCond, ExprLoc
 from miasm2.core.locationdb import LocationDB
-from miasm2.analysis.data_flow import DiGraphLivenessSSA, dead_simp, PropagateExpr
+from miasm2.analysis.simplifier import IRCFGSimplifierSSA
 from miasm2.ir.analysis import ira
 from miasm2.ir.ir import IRCFG, IRBlock, AssignBlock
-from miasm2.analysis.ssa import SSADiGraph
-from miasm2.analysis.outofssa import UnSSADiGraph
 
 loc_db = LocationDB()
 
@@ -595,6 +591,18 @@ def add_out_reg_end(ir_arch_a, ircfg_a):
 ir_arch_a = IRAOutRegs(loc_db)
 
 
+class CustomIRCFGSimplifierSSA(IRCFGSimplifierSSA):
+    def get_forbidden_regs(self):
+        """
+        Return a set of immutable register during SSA transformation
+        """
+        regs = set(
+            [
+                self.ir_arch.pc,
+                self.ir_arch.IRDst,
+            ]
+        )
+        return regs
 
 for test_nb, ircfg in enumerate(
         [
@@ -620,34 +628,8 @@ for test_nb, ircfg in enumerate(
 
     # SSA
     head = LBL0
-    ssa = SSADiGraph(ircfg)
-    ssa.transform(head)
-
-    ir_arch_a.ssa_var = ssa.ssa_variable_to_expr
-    dead_simp(ir_arch_a, ssa.graph)
-
-    open("ssa_%d.dot" % test_nb, "wb").write(ssa.graph.dot())
-
-
-
-    # Un SSA
-    ir_arch_a.ssa_var = ssa.ssa_variable_to_expr
-
-    propagate_expr = PropagateExpr()
-    modified = True
-    while modified:
-        modified = False
-        modified |= propagate_expr.propagate(ssa, head)
-
-    open('tmp_%d.dot' % test_nb, 'w').write(ssa.graph.dot())
-
-    cfg_liveness = DiGraphLivenessSSA(ssa.graph)
-    cfg_liveness.init_var_info(ir_arch_a)
-    cfg_liveness.compute_liveness()
-
-    open('liveness_%d.dot' % test_nb, 'w').write(cfg_liveness.dot())
-
-    unssa = UnSSADiGraph(ssa, head, cfg_liveness)
-    open('final_%d.dot' % test_nb, 'w').write(unssa.ssa.graph.dot())
+    simplifier = CustomIRCFGSimplifierSSA(ir_arch_a)
+    ircfg = simplifier(ircfg, head)
+    open('final_%d.dot' % test_nb, 'w').write(ircfg.dot())
 
     # XXX TODO: add real regression test