Merge pull request #899 from serpilliere/tssa_to_cssa

SSA: fix ssa to cssa, and naive out of cssa

7 files changed, 1686 insertions, 261 deletions

diff --git a/example/disasm/full.py b/example/disasm/full.py
index 4da32f67..153666f2 100644
--- a/example/disasm/full.py
+++ b/example/disasm/full.py
@@ -10,9 +10,11 @@ from miasm2.analysis.data_flow import dead_simp, DiGraphDefUse, \
     ReachingDefinitions, merge_blocks, remove_empty_assignblks, \
     PropagateExpr, replace_stack_vars, load_from_int
 from miasm2.expression.simplifications import expr_simp
-from miasm2.analysis.ssa import SSADiGraph, remove_phi
+from miasm2.analysis.ssa import SSADiGraph, UnSSADiGraph, DiGraphLivenessSSA
 from miasm2.ir.ir import AssignBlock, IRBlock
 
+
+
 log = logging.getLogger("dis")
 console_handler = logging.StreamHandler()
 console_handler.setFormatter(logging.Formatter("%(levelname)-5s: %(message)s"))
@@ -63,6 +65,10 @@ parser.add_argument('-y', "--stack2var", action="store_true",
                     help="*Try* to do transform stack accesses into variables. "
                     "Use only with --propagexpr option. "
                     "WARNING: not reliable, may fail.")
+parser.add_argument('-e', "--loadint", action="store_true",
+                    help="Load integers from binary in fixed memory lookup.")
+parser.add_argument('-j', "--calldontmodstack", action="store_true",
+                    help="Consider stack high is not modified in subcalls")
 
 
 args = parser.parse_args()
@@ -202,12 +208,29 @@ log.info('total lines %s' % total_l)
 if args.propagexpr:
     args.gen_ir = True
 
+
+class IRADelModCallStack(ira):
+
+        def call_effects(self, addr, instr):
+            assignblks, extra = super(IRADelModCallStack, self).call_effects(addr, instr)
+            if not args.calldontmodstack:
+                return assignblks, extra
+            out = []
+            for assignblk in assignblks:
+                dct = dict(assignblk)
+                dct = {
+                    dst:src for (dst, src) in dct.iteritems() if dst != self.sp
+                }
+                out.append(AssignBlock(dct, assignblk.instr))
+            return out, extra
+
+
 # Bonus, generate IR graph
 if args.gen_ir:
     log.info("generating IR and IR analysis")
 
     ir_arch = ir(mdis.loc_db)
-    ir_arch_a = ira(mdis.loc_db)
+    ir_arch_a = IRADelModCallStack(mdis.loc_db)
 
     ircfg = ir_arch.new_ircfg()
     ircfg_a = ir_arch.new_ircfg()
@@ -231,7 +254,9 @@ if args.gen_ir:
         print block
 
     if args.simplify > 0:
+        log.info("dead simp...")
         dead_simp(ir_arch_a, ircfg_a)
+        log.info("ok...")
 
     if args.defuse:
         reachings = ReachingDefinitions(ircfg_a)
@@ -250,7 +275,6 @@ if args.gen_ir:
             modified = False
             modified |= dead_simp(ir_arch_a, ircfg_a)
             modified |= remove_empty_assignblks(ircfg_a)
-            modified |= merge_blocks(ircfg_a, entry_points)
 
         open('graph_irflow_reduced.dot', 'w').write(ircfg_a.dot())
 
@@ -281,7 +305,6 @@ if args.propagexpr:
                         out[reg] = dst
             return set(out.values())
 
-
     # Add dummy dependency to uncover out regs affectation
     for loc in ircfg_a.leaves():
         irblock = ircfg_a.blocks.get(loc)
@@ -327,27 +350,22 @@ if args.propagexpr:
 
     head = list(entry_points)[0]
     heads = set([head])
-    all_ssa_vars = set()
+    all_ssa_vars = {}
 
     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)
-
-        ssa_regs = [reg for reg in ssa.expressions if reg.is_id()]
-        ssa_forbidden_regs.update(ssa_regs)
+        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)
+        ir_arch_a.ssa_var.update(ssa.ssa_variable_to_expr)
         if args.verbose > 3:
             open("ssa_orig.dot", "wb").write(ircfg_a.dot())
 
@@ -369,13 +387,16 @@ if args.propagexpr:
                 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 |= merge_blocks(ircfg_a, heads)
-                simp_modified |= load_from_int(ircfg_a, bs, is_addr_ro_variable)
+                if args.loadint:
+                    simp_modified |= load_from_int(ircfg_a, bs, is_addr_ro_variable)
                 modified |= simp_modified
                 index += 1
         if args.verbose > 3:
@@ -386,19 +407,46 @@ if args.propagexpr:
     if args.verbose > 3:
         open('final_pre.dot', 'w').write(ircfg_a.dot())
 
-    merge_blocks(ircfg_a, heads)
     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)
-    all_ssa_vars.update(ssa._ssa_variable_to_expr)
     print '*'*80, "Remove phi"
-    ssa._ssa_variable_to_expr = all_ssa_vars
     if args.verbose > 3:
         open('final_ssa.dot', 'w').write(ircfg_a.dot())
-    remove_phi(ssa, head)
+
+    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())
-    dead_simp(ir_arch_a, ircfg_a)
+
+    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())
diff --git a/example/ida/graph_ir.py b/example/ida/graph_ir.py
index b204b2b8..b04979ac 100644
--- a/example/ida/graph_ir.py
+++ b/example/ida/graph_ir.py
@@ -2,23 +2,81 @@ import os
 import tempfile
 
 import idaapi
+import ida_kernwin
 import idc
+import ida_funcs
 import idautils
-
-from miasm2.core.bin_stream_ida import bin_stream_ida
 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, DiGraphLivenessSSA
+
+from miasm2.analysis.data_flow import dead_simp,  \
+    merge_blocks, remove_empty_assignblks, \
+    PropagateExpr, load_from_int
 
-from miasm2.analysis.data_flow import dead_simp, DiGraphDefUse, \
-    ReachingDefinitions, merge_blocks, remove_empty_assignblks, \
-    PropagateExpr, replace_stack_vars, load_from_int, dead_simp, remove_empty_assignblks, \
-    read_mem, get_memlookup
 
-from miasm2.expression.simplifications import expr_simp
-from miasm2.analysis.ssa import SSADiGraph, remove_phi
-from miasm2.ir.ir import AssignBlock, IRBlock
 from utils import guess_machine, expr2colorstr
-from miasm2.expression.expression import ExprLoc, ExprMem, ExprId, ExprInt
+
+
+
+
+TYPE_GRAPH_IR = 0
+TYPE_GRAPH_IRSSA = 1
+TYPE_GRAPH_IRSSAUNSSA = 2
+
+OPTION_GRAPH_CODESIMPLIFY = 1
+OPTION_GRAPH_DONTMODSTACK = 2
+OPTION_GRAPH_LOADMEMINT = 4
+
+
+class GraphIRForm(ida_kernwin.Form):
+
+    def __init__(self):
+        ida_kernwin.Form.__init__(
+            self,
+            r"""BUTTON YES* Launch
+BUTTON CANCEL NONE
+Graph IR Settings
+
+{FormChangeCb}
+Analysis:
+<Graph IR :{rGraphIR}>
+<Graph IR + SSA :{rGraphIRSSA}>
+<Graph IR + SSA + UnSSA :{rGraphIRSSAUNSSA}>{cScope}>
+
+Options:
+<Simplify code:{rCodeSimplify}>
+<Subcalls dont change stack:{rDontModStack}>
+<Load static memory:{rLoadMemInt}>{cOptions}>
+""",
+            {
+                'FormChangeCb': ida_kernwin.Form.FormChangeCb(self.OnFormChange),
+                'cScope': ida_kernwin.Form.RadGroupControl(
+                    (
+                        "rGraphIR",
+                        "rGraphIRSSA",
+                        "rGraphIRSSAUNSSA"
+                    )
+                ),
+                'cOptions': ida_kernwin.Form.ChkGroupControl(
+                    (
+                        "rCodeSimplify",
+                        "rDontModStack",
+                        "rLoadMemInt"
+                    )
+                ),
+            }
+        )
+        form, _ = self.Compile()
+        form.rCodeSimplify.checked = True
+        form.rDontModStack.checked = False
+        form.rLoadMemInt.checked = False
+
+    def OnFormChange(self, _):
+        return 1
 
 
 # Override Miasm asmblock default label naming convention to shrink block size
@@ -34,17 +92,17 @@ def label_init(self, name="", offset=None):
         self.offset = None
     else:
         self.offset = int(offset)
+
+
 def label_str(self):
     if isinstance(self.offset, (int, long)):
         return "%s:0x%x" % (self.name, self.offset)
-    else:
-        return "%s:%s" % (self.name, str(self.offset))
-
+    return "%s:%s" % (self.name, str(self.offset))
 
 
 def color_irblock(irblock, ir_arch):
     out = []
-    lbl = idaapi.COLSTR(ir_arch.loc_db.pretty_str(irblock.loc_key), idaapi.SCOLOR_INSN)
+    lbl = idaapi.COLSTR("%s:" % ir_arch.loc_db.pretty_str(irblock.loc_key), idaapi.SCOLOR_INSN)
     out.append(lbl)
     for assignblk in irblock:
         for dst, src in sorted(assignblk.iteritems()):
@@ -54,9 +112,6 @@ def color_irblock(irblock, ir_arch):
             out.append('    %s' % line)
         out.append("")
     out.pop()
-    dst = str('    Dst: %s' % irblock.dst)
-    dst = idaapi.COLSTR(dst, idaapi.SCOLOR_RPTCMT)
-    out.append(dst)
     return "\n".join(out)
 
 
@@ -93,10 +148,10 @@ class GraphMiasmIR(idaapi.GraphViewer):
     def OnGetText(self, node_id):
         return str(self[node_id])
 
-    def OnSelect(self, node_id):
+    def OnSelect(self, _):
         return True
 
-    def OnClick(self, node_id):
+    def OnClick(self, _):
         return True
 
     def Show(self):
@@ -105,12 +160,40 @@ class GraphMiasmIR(idaapi.GraphViewer):
         return True
 
 
-def build_graph(verbose=False, simplify=False, ssa=False, ssa_simplify=False):
-    start_addr = idc.ScreenEA()
+def is_addr_ro_variable(bs, addr, size):
+    """
+    Return True if address at @addr is a read-only variable.
+    WARNING: Quick & Dirty
+
+    @addr: integer representing the address of the variable
+    @size: size in bits
 
+    """
+    try:
+        _ = bs.getbytes(addr, size/8)
+    except IOError:
+        return False
+    return True
+
+
+def build_graph(start_addr, type_graph, simplify=False, dontmodstack=True, loadint=False, verbose=False):
     machine = guess_machine(addr=start_addr)
     dis_engine, ira = machine.dis_engine, machine.ira
 
+    class IRADelModCallStack(ira):
+        def call_effects(self, addr, instr):
+            assignblks, extra = super(IRADelModCallStack, self).call_effects(addr, instr)
+            if not dontmodstack:
+                return assignblks, extra
+            out = []
+            for assignblk in assignblks:
+                dct = dict(assignblk)
+                dct = {
+                    dst:src for (dst, src) in dct.iteritems() if dst != self.sp
+                }
+                out.append(AssignBlock(dct, assignblk.instr))
+            return out, extra
+
 
     if verbose:
         print "Arch", dis_engine
@@ -121,7 +204,8 @@ def build_graph(verbose=False, simplify=False, ssa=False, ssa_simplify=False):
 
     bs = bin_stream_ida()
     mdis = dis_engine(bs)
-    ir_arch = ira(mdis.loc_db)
+    ir_arch = IRADelModCallStack(mdis.loc_db)
+
 
     # populate symbols with ida names
     for addr, name in idautils.Names():
@@ -136,15 +220,13 @@ def build_graph(verbose=False, simplify=False, ssa=False, ssa_simplify=False):
     if verbose:
         print "start disasm"
     if verbose:
-        print hex(addr)
+        print hex(start_addr)
 
     asmcfg = mdis.dis_multiblock(start_addr)
-
     entry_points = set([mdis.loc_db.get_offset_location(start_addr)])
     if verbose:
         print "generating graph"
         open('asm_flow.dot', 'w').write(asmcfg.dot())
-
         print "generating IR... %x" % start_addr
 
     ircfg = ir_arch.new_ircfg_from_asmcfg(asmcfg)
@@ -167,9 +249,9 @@ def build_graph(verbose=False, simplify=False, ssa=False, ssa_simplify=False):
         open(os.path.join(tempfile.gettempdir(), 'graph.dot'), 'wb').write(out)
     title = "Miasm IR graph"
 
+
     if simplify:
         dead_simp(ir_arch, ircfg)
-
         ircfg.simplify(expr_simp)
         modified = True
         while modified:
@@ -179,126 +261,143 @@ def build_graph(verbose=False, simplify=False, ssa=False, ssa_simplify=False):
             modified |= merge_blocks(ircfg, entry_points)
         title += " (simplified)"
 
-    graph = GraphMiasmIR(ircfg, title, None)
-
-    if ssa:
-        if len(entry_points) != 1:
-            raise RuntimeError("Your graph should have only one head")
-        head = list(entry_points)[0]
-        ssa = SSADiGraph(ircfg)
-        ssa.transform(head)
-        title += " (SSA)"
-        graph = GraphMiasmIR(ssa.graph, title, None)
-
-    if ssa_simplify:
-        class IRAOutRegs(ira):
-            def get_out_regs(self, block):
-                regs_todo = super(self.__class__, self).get_out_regs(block)
-                out = {}
-                for assignblk in block:
-                    for dst in assignblk:
-                        reg = self.ssa_var.get(dst, None)
-                        if reg is None:
-                            continue
-                        if reg in regs_todo:
-                            out[reg] = dst
-                return set(out.values())
-
-        # Add dummy dependency to uncover out regs affectation
-        for loc in ircfg.leaves():
-            irblock = ircfg.blocks.get(loc)
-            if irblock is None:
-                continue
-            regs = {}
-            for reg in ir_arch.get_out_regs(irblock):
-                regs[reg] = reg
-            assignblks = list(irblock)
-            new_assiblk = AssignBlock(regs, assignblks[-1].instr)
-            assignblks.append(new_assiblk)
-            new_irblock = IRBlock(irblock.loc_key, assignblks)
-            ircfg.blocks[loc] = new_irblock
-
+    if type_graph == TYPE_GRAPH_IR:
+        graph = GraphMiasmIR(ircfg, title, None)
+        graph.Show()
+        return
 
+    head = list(entry_points)[0]
 
-        ir_arch = IRAOutRegs(mdis.loc_db)
 
-        def is_addr_ro_variable(bs, addr, size):
-            """
-            Return True if address at @addr is a read-only variable.
-            WARNING: Quick & Dirty
+    class IRAOutRegs(ira):
+        def get_out_regs(self, block):
+            regs_todo = super(IRAOutRegs, self).get_out_regs(block)
+            out = {}
+            for assignblk in block:
+                for dst in assignblk:
+                    reg = self.ssa_var.get(dst, None)
+                    if reg is None:
+                        continue
+                    if reg in regs_todo:
+                        out[reg] = dst
+            return set(out.values())
 
-            @addr: integer representing the address of the variable
-            @size: size in bits
 
-            """
-            try:
-                _ = bs.getbytes(addr, size/8)
-            except IOError:
-                return False
-            return True
-
-
-        ir_arch.ssa_var = {}
-        index = 0
-        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 = set()
-
-        propagate_expr = PropagateExpr()
+    # Add dummy dependency to uncover out regs affectation
+    for loc in ircfg.leaves():
+        irblock = ircfg.blocks.get(loc)
+        if irblock is None:
+            continue
+        regs = {}
+        for reg in ir_arch.get_out_regs(irblock):
+            regs[reg] = reg
+        assignblks = list(irblock)
+        new_assiblk = AssignBlock(regs, assignblks[-1].instr)
+        assignblks.append(new_assiblk)
+        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()
+
+    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)
 
+    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)
 
-            all_ssa_vars.update(ssa._ssa_variable_to_expr)
-
-            ssa_regs = [reg for reg in ssa.expressions if reg.is_id()]
-            ssa_forbidden_regs.update(ssa_regs)
-
-
-            ir_arch.ssa_var.update(ssa._ssa_variable_to_expr)
+            ir_arch.ssa_var.update(ssa.ssa_variable_to_expr)
 
             while modified:
-                index += 1
                 modified = False
                 modified |= propagate_expr.propagate(ssa, head)
                 modified |= ircfg.simplify(expr_simp)
                 simp_modified = True
                 while simp_modified:
-                    index += 1
                     simp_modified = False
                     simp_modified |= dead_simp(ir_arch, ircfg)
-                    index += 1
                     simp_modified |= remove_empty_assignblks(ircfg)
-                    simp_modified |= merge_blocks(ircfg, heads)
                     simp_modified |= load_from_int(ircfg, bs, is_addr_ro_variable)
                     modified |= simp_modified
-                    index += 1
 
 
-        merge_blocks(ircfg, heads)
-        ssa = SSADiGraph(ircfg)
-        ssa.immutable_ids.update(ssa_forbidden_regs)
-        ssa.transform(head)
-        all_ssa_vars.update(ssa._ssa_variable_to_expr)
-        ssa._ssa_variable_to_expr = all_ssa_vars
-        dead_simp(ir_arch, ssa.graph)
+    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)
 
-        title += " (SSA Simplified)"
+    if type_graph == TYPE_GRAPH_IRSSA:
         graph = GraphMiasmIR(ssa.graph, title, None)
+        graph.Show()
+        return
+
+    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()
+
+
+def function_graph_ir():
+    # Get settings
+    settings = GraphIRForm()
+    ret = settings.Execute()
+    if not ret:
+        return
 
+    func = ida_funcs.get_func(idc.ScreenEA())
+    func_addr = func.startEA
 
-    graph.Show()
+    build_graph(
+        func_addr,
+        settings.cScope.value,
+        simplify=settings.cOptions.value & OPTION_GRAPH_CODESIMPLIFY,
+        dontmodstack=settings.cOptions.value & OPTION_GRAPH_DONTMODSTACK,
+        loadint=settings.cOptions.value & OPTION_GRAPH_LOADMEMINT,
+        verbose=False
+    )
+    return
 
 if __name__ == "__main__":
-    build_graph(verbose=True, simplify=False)
+    function_graph_ir()
diff --git a/example/ida/menu.py b/example/ida/menu.py
index a0eecf67..f98bd75e 100644
--- a/example/ida/menu.py
+++ b/example/ida/menu.py
@@ -3,13 +3,12 @@
 - Miasm > Symbolic execution (icon 81, F3)
 - Miasm > Dependency graph (icon 79, F4)
 - Miasm > Graph IR (icon 188, F7)
-- Miasm > Graph IR (simplified) (icon 191, F8)
 - Miasm > RPYC server (icon 182, F10)
 - Miasm > Type propagation (icon 38, F11)
 """
 
 from symbol_exec import symbolic_exec
-from graph_ir import build_graph
+from graph_ir import function_graph_ir
 try:
     from rpyc_ida import serve_threaded
 except ImportError:
@@ -59,22 +58,10 @@ handler_symb.attach_to_menu("Miasm/Symbolic exec")
 handler_depgraph = Handler(launch_depgraph)
 handler_depgraph.register("miasm:depgraph", "Dependency graph", shortcut="F4", icon=79)
 handler_depgraph.attach_to_menu("Miasm/Dependency graph")
-handler_graph = Handler(build_graph)
+
+handler_graph = Handler(function_graph_ir)
 handler_graph.register("miasm:graphir", "Graph IR", shortcut="F7", icon=188)
 handler_graph.attach_to_menu("Miasm/Graph IR")
-handler_graph_simp = Handler(lambda: build_graph(simplify=True))
-handler_graph_simp.register("miasm:graphirsimp",
-                            "Graph IR (simplified)", shortcut="F8", icon=191)
-handler_graph_simp.attach_to_menu("Miasm/Graph IR (simplified)")
-handler_graph_simp = Handler(lambda: build_graph(simplify=True, ssa=True))
-handler_graph_simp.register("miasm:graphirssa",
-                            "Graph IR (SSA)", shortcut="F8", icon=191)
-handler_graph_simp.attach_to_menu("Miasm/Graph IR (SSA)")
-
-handler_graph_simp = Handler(lambda: build_graph(simplify=True, ssa_simplify=True))
-handler_graph_simp.register("miasm:graphirssasimple",
-                            "Graph IR (SSA Simplified)", shortcut="F8", icon=191)
-handler_graph_simp.attach_to_menu("Miasm/Graph IR (SSA Simplified)")
 
 if serve_threaded is not None:
     handler_rpyc = Handler(serve_threaded)
diff --git a/miasm2/analysis/data_flow.py b/miasm2/analysis/data_flow.py
index 23e2f77e..b90bdaf9 100644
--- a/miasm2/analysis/data_flow.py
+++ b/miasm2/analysis/data_flow.py
@@ -3,7 +3,8 @@
 from collections import namedtuple
 from miasm2.core.graph import DiGraph
 from miasm2.ir.ir import AssignBlock, IRBlock
-from miasm2.expression.expression import ExprLoc, ExprMem, ExprId, ExprInt
+from miasm2.expression.expression import ExprLoc, ExprMem, ExprId, ExprInt,\
+    ExprAssign
 from miasm2.expression.simplifications import expr_simp
 from miasm2.core.interval import interval
 
@@ -1006,3 +1007,208 @@ def load_from_int(ir_arch, bs, is_addr_ro_variable):
         block = IRBlock(block.loc_key, assignblks)
         ir_arch.blocks[block.loc_key] = block
     return modified
+
+
+class AssignBlockLivenessInfos(object):
+    """
+    Description of live in / live out of an AssignBlock
+    """
+
+    __slots__ = ["gen", "kill", "var_in", "var_out", "live", "assignblk"]
+
+    def __init__(self, assignblk, gen, kill):
+        self.gen = gen
+        self.kill = kill
+        self.var_in = set()
+        self.var_out = set()
+        self.live = set()
+        self.assignblk = assignblk
+
+    def __str__(self):
+        out = []
+        out.append("\tVarIn:" + ", ".join(str(x) for x in self.var_in))
+        out.append("\tGen:" + ", ".join(str(x) for x in self.gen))
+        out.append("\tKill:" + ", ".join(str(x) for x in self.kill))
+        out.append(
+            '\n'.join(
+                "\t%s = %s" % (dst, src)
+                for (dst, src) in self.assignblk.iteritems()
+            )
+        )
+        out.append("\tVarOut:" + ", ".join(str(x) for x in self.var_out))
+        return '\n'.join(out)
+
+
+class IRBlockLivenessInfos(object):
+    """
+    Description of live in / live out of an AssignBlock
+    """
+    __slots__ = ["loc_key", "infos", "assignblks"]
+
+
+    def __init__(self, irblock):
+        self.loc_key = irblock.loc_key
+        self.infos = []
+        self.assignblks = []
+        for assignblk in irblock:
+            gens, kills = set(), set()
+            for dst, src in assignblk.iteritems():
+                expr = ExprAssign(dst, src)
+                read = expr.get_r(mem_read=True)
+                write = expr.get_w()
+                gens.update(read)
+                kills.update(write)
+            self.infos.append(AssignBlockLivenessInfos(assignblk, gens, kills))
+            self.assignblks.append(assignblk)
+
+    def __getitem__(self, index):
+        """Getitem on assignblks"""
+        return self.assignblks.__getitem__(index)
+
+    def __str__(self):
+        out = []
+        out.append("%s:" % self.loc_key)
+        for info in self.infos:
+            out.append(str(info))
+            out.append('')
+        return "\n".join(out)
+
+
+class DiGraphLiveness(DiGraph):
+    """
+    DiGraph representing variable liveness
+    """
+
+    def __init__(self, ircfg, loc_db=None):
+        super(DiGraphLiveness, self).__init__()
+        self.ircfg = ircfg
+        self.loc_db = loc_db
+        self._blocks = {}
+        # Add irblocks gen/kill
+        for node in ircfg.nodes():
+            irblock = ircfg.blocks[node]
+            irblockinfos = IRBlockLivenessInfos(irblock)
+            self.add_node(irblockinfos.loc_key)
+            self.blocks[irblockinfos.loc_key] = irblockinfos
+            for succ in ircfg.successors(node):
+                self.add_uniq_edge(node, succ)
+            for pred in ircfg.predecessors(node):
+                self.add_uniq_edge(pred, node)
+
+    @property
+    def blocks(self):
+        return self._blocks
+
+    def init_var_info(self):
+        """Add ircfg out regs"""
+        raise NotImplementedError("Abstract method")
+
+    def node2lines(self, node):
+        """
+        Output liveness information in dot format
+        """
+        if self.loc_db is None:
+            node_name = str(node)
+        else:
+            names = self.loc_db.get_location_names(node)
+            if not names:
+                node_name = self.loc_db.pretty_str(node)
+            else:
+                node_name = "".join("%s:\n" % name for name in names)
+        yield self.DotCellDescription(
+            text="%s" % node_name,
+            attr={
+                'align': 'center',
+                'colspan': 2,
+                'bgcolor': 'grey',
+            }
+        )
+        if node not in self._blocks:
+            yield [self.DotCellDescription(text="NOT PRESENT", attr={})]
+            raise StopIteration
+
+        for i, info in enumerate(self._blocks[node].infos):
+            var_in = "VarIn:" + ", ".join(str(x) for x in info.var_in)
+            var_out = "VarOut:" + ", ".join(str(x) for x in info.var_out)
+
+            assignmnts = ["%s = %s" % (dst, src) for (dst, src) in info.assignblk.iteritems()]
+
+            if i == 0:
+                yield self.DotCellDescription(
+                    text=var_in,
+                    attr={
+                        'bgcolor': 'green',
+                    }
+                )
+
+            for assign in assignmnts:
+                yield self.DotCellDescription(text=assign, attr={})
+            yield self.DotCellDescription(
+                text=var_out,
+                attr={
+                    'bgcolor': 'green',
+                }
+            )
+            yield self.DotCellDescription(text="", attr={})
+
+    def back_propagate_compute(self, block):
+        """
+        Compute the liveness information in the @block.
+        @block: AssignBlockLivenessInfos instance
+        """
+        infos = block.infos
+        modified = False
+        for i in reversed(xrange(len(infos))):
+            new_vars = set(infos[i].gen.union(infos[i].var_out.difference(infos[i].kill)))
+            if infos[i].var_in != new_vars:
+                modified = True
+                infos[i].var_in = new_vars
+            if i > 0 and infos[i - 1].var_out != set(infos[i].var_in):
+                modified = True
+                infos[i - 1].var_out = set(infos[i].var_in)
+        return modified
+
+    def back_propagate_to_parent(self, todo, node, parent):
+        """
+        Back propagate the liveness information from @node to @parent.
+        @node: loc_key of the source node
+        @parent: loc_key of the node to update
+        """
+        parent_block = self.blocks[parent]
+        cur_block = self.blocks[node]
+        if cur_block.infos[0].var_in == parent_block.infos[-1].var_out:
+            return
+        var_info = cur_block.infos[0].var_in.union(parent_block.infos[-1].var_out)
+        parent_block.infos[-1].var_out = var_info
+        todo.add(parent)
+
+    def compute_liveness(self):
+        """
+        Compute the liveness information for the digraph.
+        """
+        todo = set(self.leaves())
+        while todo:
+            node = todo.pop()
+            cur_block = self.blocks[node]
+            modified = self.back_propagate_compute(cur_block)
+            if not modified:
+                continue
+            # We modified parent in, propagate to parents
+            for pred in self.predecessors(node):
+                self.back_propagate_to_parent(todo, node, pred)
+        return True
+
+
+class DiGraphLivenessIRA(DiGraphLiveness):
+    """
+    DiGraph representing variable liveness for IRA
+    """
+
+    def init_var_info(self, ir_arch_a):
+        """Add ircfg out regs"""
+
+        for node in self.leaves():
+            irblock = self.ircfg.blocks[node]
+            var_out = ir_arch_a.get_out_regs(irblock)
+            irblock_liveness = self.blocks[node]
+            irblock_liveness.infos[-1].var_out = var_out
diff --git a/miasm2/analysis/ssa.py b/miasm2/analysis/ssa.py
index c22aae59..b68eef7c 100644
--- a/miasm2/analysis/ssa.py
+++ b/miasm2/analysis/ssa.py
@@ -1,10 +1,10 @@
 from collections import deque
 
+from miasm2.analysis.data_flow import DiGraphLivenessIRA, remove_empty_assignblks
 from miasm2.expression.expression import ExprId, ExprAssign, ExprOp, get_expr_ids
 from miasm2.ir.ir import AssignBlock, IRBlock
 
 
-
 class SSA(object):
     """
     Generic class for static single assignment (SSA) transformation
@@ -44,7 +44,7 @@ class SSA(object):
         # stack for LHS
         self._stack_lhs = {}
 
-        self._ssa_variable_to_expr = {}
+        self.ssa_variable_to_expr = {}
 
         # dict of SSA expressions
         self.expressions = {}
@@ -78,7 +78,7 @@ class SSA(object):
         :param ssa_var: ExprId, variable in SSA form
         :return: ExprId, variable in non-SSA form
         """
-        expr = self._ssa_variable_to_expr.get(ssa_var, ssa_var)
+        expr = self.ssa_variable_to_expr.get(ssa_var, ssa_var)
         return expr
 
     def reset(self):
@@ -99,7 +99,7 @@ class SSA(object):
         index = stack[expr]
         name = "%s.%d" % (expr.name, index)
         ssa_var = ExprId(name, expr.size)
-        self._ssa_variable_to_expr[ssa_var] = expr
+        self.ssa_variable_to_expr[ssa_var] = expr
 
         return ssa_var
 
@@ -250,7 +250,7 @@ class SSA(object):
 
             # transform LHS
             for expr in instructions:
-                if expr.dst in self.immutable_ids:
+                if expr.dst in self.immutable_ids or expr.dst in self.ssa_variable_to_expr:
                     dst_ssa = expr.dst
                 else:
                     dst_ssa = self._transform_expression_lhs(expr.dst)
@@ -372,6 +372,7 @@ class SSADiGraph(SSA):
         self._rename(head)
         self._insert_phi()
         self._convert_phi()
+        self._fix_no_def_var(head)
 
     def reset(self):
         """Resets SSA transformation"""
@@ -400,7 +401,7 @@ class SSADiGraph(SSA):
                     # enforce ExprId
                     if dst.is_id():
                         # exclude immutable ids
-                        if dst in self.immutable_ids:
+                        if dst in self.immutable_ids or dst in self.ssa_variable_to_expr:
                             continue
                         # map variable definition to blocks
                         self.defs.setdefault(dst, set()).add(irblock.loc_key)
@@ -438,13 +439,11 @@ class SSADiGraph(SSA):
                 for node in frontier.get(loc_key, []):
                     if node in done:
                         continue
-
                     # place empty phi functions for a variable
                     empty_phi = self._gen_empty_phi(variable)
 
                     # add empty phi node for variable in node
                     self._phinodes.setdefault(node, {})[variable] = empty_phi.src
-
                     done.add(node)
 
                     if node not in intodo:
@@ -575,120 +574,553 @@ class SSADiGraph(SSA):
             new_irs = IRBlock(loc_key, [assignblk] + list(irblock.assignblks))
             self.ircfg.blocks[loc_key] = new_irs
 
+    def _fix_no_def_var(self, head):
+        """
+        Replace phi source variables which are not ssa vars by ssa vars.
+        @head: loc_key of the graph head
+        """
+        var_to_insert = set()
+        for loc_key in self._phinodes:
+            for dst, sources in self._phinodes[loc_key].iteritems():
+                for src in sources.args:
+                    if src in self.ssa_variable_to_expr:
+                        continue
+                    var_to_insert.add(src)
+        var_to_newname = {}
+        newname_to_var = {}
+        for var in var_to_insert:
+            new_var = self._transform_var_lhs(var)
+            var_to_newname[var] = new_var
+            newname_to_var[new_var] = var
+
+        # 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)
+
+        # Updt structure
+        for loc_key in self._phinodes:
+            for dst, sources in self._phinodes[loc_key].items():
+                self._phinodes[loc_key][dst] = sources.replace_expr(var_to_newname)
+
+        for var, (loc_key, index) in self.ssa_to_location.items():
+            if loc_key == head:
+                self.ssa_to_location[var] = loc_key, index + 1
+
+        for newname, var in newname_to_var.iteritems():
+            self.ssa_to_location[newname] = head, 0
+            self.ssa_variable_to_expr[newname] = var
+            self.immutable_ids.add(newname)
+            self.expressions[newname] = var
 
 
-def get_assignblk(graph, loc, index):
+def irblock_has_phi(irblock):
     """
-    Return the dictionary of the AssignBlock from @graph at location @loc at
-    @index
-    @graph: IRCFG instance
-    @loc: Location instance
-    @index: assignblock index
+    Return True if @irblock has Phi assignments
+    @irblock: IRBlock instance
     """
+    if not irblock.assignblks:
+        return False
+    for src in irblock[0].itervalues():
+        return src.is_op('Phi')
+    return False
 
-    irblock = graph.blocks[loc]
-    assignblks = irblock.assignblks
-    assignblk = assignblks[index]
-    assignblk_dct = dict(assignblk)
-    return assignblk_dct
 
+class Varinfo(object):
+    """Store liveness information for a variable"""
+    __slots__ = ["live_index", "loc_key", "index"]
+
+    def __init__(self, live_index, loc_key, index):
+        self.live_index = live_index
+        self.loc_key = loc_key
+        self.index = index
 
-def set_assignblk(graph, loc, index, assignblk_dct):
-    """
-    Set the Assignblock in @graph at location @loc at @index using dictionary
-    @assignblk_dct
 
-    @graph: IRCFG instance
-    @loc: Location instance
-    @index: assignblock index
-    @assignblk_dct: dictionary representing the AssignBlock
+def get_var_assignment_src(ircfg, node, variables):
+    """
+    Return the variable of @variables which is written by the irblock at @node
+    @node: Location
+    @variables: a set of variable to test
     """
+    irblock = ircfg.blocks[node]
+    for assignblk in irblock:
+        result = set(assignblk).intersection(variables)
+        if not result:
+            continue
+        assert len(result) == 1
+        return list(result)[0]
+    return None
 
-    irblock = graph.blocks[loc]
-    assignblks = list(irblock.assignblks)
-    assignblk = assignblks[index]
 
-    assignblks[index] = AssignBlock(
-        assignblk_dct,
-        assignblk.instr
-    )
-    new_irblock = IRBlock(loc, assignblks)
-    return new_irblock
+def get_phi_sources_parent_block(ircfg, loc_key, sources):
+    """
+    Return a dictionary linking a variable to it's direct parent label
+    which belong to a path which affects the node.
+    @loc_key: the starting node
+    @sources: set of variables to resolve
+    """
+    source_to_parent = {}
+    for parent in ircfg.predecessors(loc_key):
+        done = set()
+        todo = set([parent])
+        found = False
+        while todo:
+            node = todo.pop()
+            if node in done:
+                continue
+            done.add(node)
+            ret = get_var_assignment_src(ircfg, node, sources)
+            if ret:
+                source_to_parent.setdefault(ret, set()).add(parent)
+                found = True
+                break
+            for pred in ircfg.predecessors(node):
+                todo.add(pred)
+        assert found
+    return source_to_parent
 
 
-def remove_phi(ssa, head):
+class UnSSADiGraph(object):
     """
-    Remove Phi using naive algorithm
-    Note: The _ssa_variable_to_expr must be up to date
-
-    @ssa: a SSADiGraph instance
-    @head: the loc_key of the graph head
+    Implements unssa algorithm
+    Revisiting Out-of-SSA Translation for Correctness, Code Quality, and
+    Efficiency
     """
 
-    phivar2var = {}
+    def __init__(self, ssa, head, cfg_liveness):
+        self.cfg_liveness = cfg_liveness
+        self.ssa = ssa
+        self.head = head
+
+        # Set of created variables
+        self.copy_vars = set()
+        # Virtual parallel copies
+
+        # On loc_key's Phi node dst -> set((parent, src))
+        self.phi_parent_sources = {}
+        # On loc_key's Phi node, loc_key -> set(Phi dsts)
+        self.phi_destinations = {}
+        # Phi's dst -> new var
+        self.phi_new_var = {}
+        # For a new_var representing dst:
+        # new_var -> set(parents of Phi's src in dst = Phi(src,...))
+        self.new_var_to_srcs_parents = {}
+        # new_var -> set(variables to be coalesced with, named "merge_set")
+        self.merge_state = {}
+
+        # Launch the algorithm in several steps
+        self.isolate_phi_nodes_block()
+        self.init_phis_merge_state()
+        self.order_ssa_var_dom()
+        self.aggressive_coalesce_block()
+        self.insert_parallel_copy()
+        self.replace_merge_sets()
+        self.remove_assign_eq()
+        remove_empty_assignblks(self.ssa.graph)
+
+    def insert_parallel_copy(self):
+        """
+        Naive Out-of-SSA from CSSA (without coalescing for now)
+        - Replace Phi
+        - Create room for parallel copies in Phi's parents
+        """
+        ircfg = self.ssa.graph
 
-    all_ssa_vars = ssa._ssa_variable_to_expr
+        for irblock in ircfg.blocks.values():
+            if not irblock_has_phi(irblock):
+                continue
 
-    # Retrieve Phi nodes
-    phi_nodes = []
-    for irblock in ssa.graph.blocks.itervalues():
-        for index, assignblk in enumerate(irblock):
-            for dst, src in assignblk.iteritems():
-                if src.is_op('Phi'):
-                    phi_nodes.append((irblock.loc_key, index))
+            # Replace Phi with Phi's dst = new_var
+            parallel_copies = {}
+            for dst in self.phi_destinations[irblock.loc_key]:
+                new_var = self.phi_new_var[dst]
+                parallel_copies[dst] = new_var
+
+            assignblks = list(irblock)
+            assignblks[0] = AssignBlock(parallel_copies, irblock[0].instr)
+            new_irblock = IRBlock(irblock.loc_key, assignblks)
+            ircfg.blocks[irblock.loc_key] = new_irblock
+
+            # Insert new_var = src in each Phi's parent, at the end of the block
+            parent_to_parallel_copies = {}
+            parallel_copies = {}
+            for dst in irblock[0]:
+                new_var = self.phi_new_var[dst]
+                for parent, src in self.phi_parent_sources[dst]:
+                    parent_to_parallel_copies.setdefault(parent, {})[new_var] = src
+
+            for parent, parallel_copies in parent_to_parallel_copies.iteritems():
+                parent = ircfg.blocks[parent]
+                assignblks = list(parent)
+                assignblks.append(AssignBlock(parallel_copies, parent[-1].instr))
+                new_irblock = IRBlock(parent.loc_key, assignblks)
+                ircfg.blocks[parent.loc_key] = new_irblock
+
+    def create_copy_var(self, var):
+        """
+        Generate a new var standing for @var
+        @var: variable to replace
+        """
+        new_var = ExprId('var%d' % len(self.copy_vars), var.size)
+        self.copy_vars.add(new_var)
+        return new_var
 
+    def isolate_phi_nodes_block(self):
+        """
+        Init structures and virtually insert parallel copy before/after each phi
+        node
+        """
+        ircfg = self.ssa.graph
+        for irblock in ircfg.blocks.itervalues():
+            if not irblock_has_phi(irblock):
+                continue
+            for dst, sources in irblock[0].iteritems():
+                assert sources.is_op('Phi')
+                new_var = self.create_copy_var(dst)
+                self.phi_new_var[dst] = new_var
+
+                var_to_parents = get_phi_sources_parent_block(
+                    self.ssa.graph,
+                    irblock.loc_key,
+                    sources.args
+                )
+
+                for src in sources.args:
+                    parents = var_to_parents[src]
+                    self.new_var_to_srcs_parents.setdefault(new_var, set()).update(parents)
+                    parent_dsts = set((parent, src) for parent in parents)
+                    for parent in parents:
+                        self.phi_parent_sources.setdefault(dst, set()).add((parent, src))
+
+            self.phi_destinations[irblock.loc_key] = set(irblock[0])
+
+    def init_phis_merge_state(self):
+        """
+        Generate trivial coalescing of phi variable and itself
+        """
+        for phi_new_var in self.phi_new_var.itervalues():
+            self.merge_state.setdefault(phi_new_var, set([phi_new_var]))
 
-    for phi_loc, phi_index in phi_nodes:
-        assignblk_dct = get_assignblk(ssa.graph, phi_loc, phi_index)
-        for dst, src in assignblk_dct.iteritems():
-            if src.is_op('Phi'):
-                break
-        else:
-            raise RuntimeError('Cannot find phi?')
-        node_src = src
-        var = dst
-
-        # Create new variable
-        new_var = ExprId('var%d' % len(phivar2var), var.size)
-        phivar2var[var] = new_var
-        phi_sources = set(node_src.args)
-
-        # Place var init for non ssa variables
-        to_remove = set()
-        for phi_source in list(phi_sources):
-            if phi_source not in all_ssa_vars.union(phivar2var.values()):
-                assignblk_dct = get_assignblk(ssa.graph, head, 0)
-                assignblk_dct[new_var] = phi_source
-                new_irblock = set_assignblk(ssa.graph, head, 0, assignblk_dct)
-                ssa.graph.blocks[head] = new_irblock
-                to_remove.add(phi_source)
-        phi_sources.difference_update(to_remove)
-
-        var_to_replace = set([var])
-        var_to_replace.update(phi_sources)
-
-
-
-
-        # Replace variables
-        to_replace_dct = {x:new_var for x in var_to_replace}
-        for loc in ssa.graph.blocks:
-            irblock = ssa.graph.blocks[loc]
-            assignblks = []
-            for assignblk in irblock:
-                assignblk_dct = {}
+    def order_ssa_var_dom(self):
+        """Compute dominance order of each ssa variable"""
+        ircfg = self.ssa.graph
+
+        # compute dominator tree
+        dominator_tree = ircfg.compute_dominator_tree(self.head)
+
+        # variable -> Varinfo
+        self.var_to_varinfo = {}
+        # live_index can later be used to compare dominance of AssignBlocks
+        live_index = 0
+
+        # walk in DFS over the dominator tree
+        for loc_key in dominator_tree.walk_depth_first_forward(self.head):
+            irblock = ircfg.blocks[loc_key]
+
+            # Create live index for phi new vars
+            # They do not exist in the graph yet, so index is set to None
+            if irblock_has_phi(irblock):
+                for dst in irblock[0]:
+                    if not dst.is_id():
+                        continue
+                    new_var = self.phi_new_var[dst]
+                    self.var_to_varinfo[new_var] = Varinfo(live_index, loc_key, None)
+
+                live_index += 1
+
+            # Create live index for remaining assignments
+            for index, assignblk in enumerate(irblock):
+                used = False
+                for dst in assignblk:
+                    if not dst.is_id():
+                        continue
+                    if dst in self.ssa.immutable_ids:
+                        # Will not be considered by the current algo, ignore it
+                        # (for instance, IRDst)
+                        continue
+
+                    assert dst not in self.var_to_varinfo
+                    self.var_to_varinfo[dst] = Varinfo(live_index, loc_key, index)
+                    used = True
+                if used:
+                    live_index += 1
+
+
+    def ssa_def_dominates(self, node_a, node_b):
+        """
+        Return living index order of @node_a and @node_b
+        @node_a: Varinfo instance
+        @node_b: Varinfo instance
+        """
+        ret = self.var_to_varinfo[node_a].live_index <= self.var_to_varinfo[node_b].live_index
+        return ret
+
+    def merge_set_sort(self, merge_set):
+        """
+        Return a sorted list of (live_index, var) from @merge_set in dominance
+        order
+        @merge_set: set of coalescing variables
+        """
+        return sorted(
+            (self.var_to_varinfo[var].live_index, var)
+            for var in merge_set
+        )
+
+    def ssa_def_is_live_at(self, node_a, node_b, parent):
+        """
+        Return True if @node_a is live during @node_b definition
+        If @parent is None, this is a liveness test for a post phi variable;
+        Else, it is a liveness test for a variable source of the phi node
+
+        @node_a: Varinfo instance
+        @node_b: Varinfo instance
+        @parent: Optional parent location of the phi source
+        """
+        loc_key_b, index_b = self.var_to_varinfo[node_b].loc_key, self.var_to_varinfo[node_b].index
+        if parent and index_b is None:
+            index_b = 0
+        if node_a not in self.new_var_to_srcs_parents:
+            # node_a is not a new var (it is a "classic" var)
+            # -> use a basic liveness test
+            liveness_b = self.cfg_liveness.blocks[loc_key_b].infos[index_b]
+            return node_a in liveness_b.var_out
+
+        for def_loc_key in self.new_var_to_srcs_parents[node_a]:
+            # Consider node_a as defined at the end of its parents blocks
+            # and compute liveness check accordingly
+
+            if def_loc_key == parent:
+                # Same path as node_a definition, so SSA ensure b cannot be live
+                # on this path (otherwise, a Phi would already happen earlier)
+                continue
+            liveness_end_block = self.cfg_liveness.blocks[def_loc_key].infos[-1]
+            if node_b in liveness_end_block.var_out:
+                return True
+        return False
+
+    def merge_nodes_interfere(self, node_a, node_b, parent):
+        """
+        Return True if @node_a and @node_b interfere
+        @node_a: variable
+        @node_b: variable
+        @parent: Optional parent location of the phi source for liveness tests
+
+        Interference check is: is x live at y definition (or reverse)
+        TODO: add Value-based interference improvement
+        """
+        if self.var_to_varinfo[node_a].live_index == self.var_to_varinfo[node_b].live_index:
+            # Defined in the same AssignBlock -> interfere
+            return True
+
+        if self.var_to_varinfo[node_a].live_index < self.var_to_varinfo[node_b].live_index:
+            return self.ssa_def_is_live_at(node_a, node_b, parent)
+        return self.ssa_def_is_live_at(node_b, node_a, parent)
+
+    def merge_sets_interfere(self, merge_a, merge_b, parent):
+        """
+        Return True if no variable in @merge_a and @merge_b interferes.
+
+        Implementation of "Algorithm 2: Check intersection in a set of variables"
+
+        @merge_a: a dom ordered list of equivalent variables
+        @merge_b: a dom ordered list of equivalent variables
+        @parent: Optional parent location of the phi source for liveness tests
+        """
+        if merge_a == merge_b:
+            # No need to consider interference if equal
+            return False
+
+        merge_a_list = self.merge_set_sort(merge_a)
+        merge_b_list = self.merge_set_sort(merge_b)
+        dom = []
+        while merge_a_list or merge_b_list:
+            if not merge_a_list:
+                _, current = merge_b_list.pop(0)
+            elif not merge_b_list:
+                _, current = merge_a_list.pop(0)
+            else:
+                # compare live_indexes (standing for dominance)
+                if merge_a_list[-1] < merge_b_list[-1]:
+                    _, current = merge_a_list.pop(0)
+                else:
+                    _, current = merge_b_list.pop(0)
+            while dom and not self.ssa_def_dominates(dom[-1], current):
+                dom.pop()
+
+            # Don't test node in same merge_set
+            if (
+                    # Is stack not empty?
+                    dom and
+                    # Trivial non-interference if dom.top() and current come
+                    # from the same merge set
+                    not (dom[-1] in merge_a and current in merge_a) and
+                    not (dom[-1] in merge_b and current in merge_b) and
+                    # Actually test for interference
+                    self.merge_nodes_interfere(current, dom[-1], parent)
+            ):
+                    return True
+            dom.append(current)
+        return False
+
+    def aggressive_coalesce_parallel_copy(self, parallel_copies, parent):
+        """
+        Try to coalesce variables each dst/src couple together from
+        @parallel_copies
+
+        @parallel_copies: a dictionary representing dst/src parallel
+        assignments.
+        @parent: Optional parent location of the phi source for liveness tests
+        """
+        for dst, src in parallel_copies.iteritems():
+            dst_merge = self.merge_state.setdefault(dst, set([dst]))
+            src_merge = self.merge_state.setdefault(src, set([src]))
+            if not self.merge_sets_interfere(dst_merge, src_merge, parent):
+                dst_merge.update(src_merge)
+                for node in dst_merge:
+                    self.merge_state[node] = dst_merge
+
+    def aggressive_coalesce_block(self):
+        """Try to coalesce phi var with their pre/post variables"""
+
+        ircfg = self.ssa.graph
+
+        # Run coalesce on the post phi parallel copy
+        for irblock in ircfg.blocks.values():
+            if not irblock_has_phi(irblock):
+                continue
+            parallel_copies = {}
+            for dst in self.phi_destinations[irblock.loc_key]:
+                parallel_copies[dst] = self.phi_new_var[dst]
+            self.aggressive_coalesce_parallel_copy(parallel_copies, None)
+
+            # Run coalesce on the pre phi parallel copy
+
+            # Stand for the virtual parallel copies at the end of Phi's block
+            # parents
+            parent_to_parallel_copies = {}
+            for dst in irblock[0]:
+                new_var = self.phi_new_var[dst]
+                for parent, src in self.phi_parent_sources[dst]:
+                    parent_to_parallel_copies.setdefault(parent, {})[new_var] = src
+
+            for parent, parallel_copies in parent_to_parallel_copies.iteritems():
+                self.aggressive_coalesce_parallel_copy(parallel_copies, parent)
+
+    def get_best_merge_set_name(self, merge_set):
+        """
+        For a given @merge_set, prefer an original SSA variable instead of a
+        created copy. In other case, take a random name.
+        @merge_set: set of equivalent expressions
+        """
+        if not merge_set:
+            raise RuntimeError("Merge set should not be empty")
+        for var in merge_set:
+            if var not in self.copy_vars:
+                return var
+        # Get random name
+        return var
+
+
+    def replace_merge_sets(self):
+        """
+        In the graph, replace all variables from merge state by their
+        representative variable
+        """
+        replace = {}
+        merge_sets = set()
+
+        # Elect representative for merge sets
+        merge_set_to_name = {}
+        for merge_set in self.merge_state.itervalues():
+            frozen_merge_set = frozenset(merge_set)
+            merge_sets.add(frozen_merge_set)
+            var_name = self.get_best_merge_set_name(merge_set)
+            merge_set_to_name[frozen_merge_set] = var_name
+
+        # Generate replacement of variable by their representative
+        for merge_set in merge_sets:
+            var_name = merge_set_to_name[merge_set]
+            merge_set = list(merge_set)
+            for var in merge_set:
+                replace[var] = var_name
+
+        self.ssa.graph.simplify(lambda x: x.replace_expr(replace))
+
+    def remove_phi(self):
+        """
+        Remove phi operators in @ifcfg
+        @ircfg: IRDiGraph instance
+        """
+
+        for irblock in self.ssa.graph.blocks.values():
+            assignblks = list(irblock)
+            out = {}
+            for dst, src in assignblks[0].iteritems():
+                if src.is_op('Phi'):
+                    assert set([dst]) == set(src.args)
+                    continue
+                out[dst] = src
+            assignblks[0] = AssignBlock(out, assignblks[0].instr)
+            self.ssa.graph.blocks[irblock.loc_key] = IRBlock(irblock.loc_key, assignblks)
+
+    def remove_assign_eq(self):
+        """
+        Remove trivial expressions (a=a) in the current graph
+        """
+        for irblock in self.ssa.graph.blocks.values():
+            assignblks = list(irblock)
+            for i, assignblk in enumerate(assignblks):
+                out = {}
                 for dst, src in assignblk.iteritems():
-                    dst = dst.replace_expr(to_replace_dct)
-                    src = src.replace_expr(to_replace_dct)
-                    assignblk_dct[dst] = src
-                assignblks.append(AssignBlock(assignblk_dct, assignblk.instr))
-            new_irblock = IRBlock(loc, assignblks)
-            ssa.graph.blocks[loc] = new_irblock
+                    if dst == src:
+                        continue
+                    out[dst] = src
+                assignblks[i] = AssignBlock(out, assignblk.instr)
+            self.ssa.graph.blocks[irblock.loc_key] = IRBlock(irblock.loc_key, assignblks)
+
+
+class DiGraphLivenessSSA(DiGraphLivenessIRA):
+    """
+    DiGraph representing variable liveness is a SSA graph
+    """
+    def __init__(self, ircfg):
+        super(DiGraphLivenessSSA, self).__init__(ircfg)
+
+        self.loc_key_to_phi_parents = {}
+        for irblock in self.blocks.values():
+            if not irblock_has_phi(irblock):
+                continue
+            out = {}
+            for sources in irblock[0].itervalues():
+                var_to_parents = get_phi_sources_parent_block(self, irblock.loc_key, sources.args)
+                for var, var_parents in var_to_parents.iteritems():
+                    out.setdefault(var, set()).update(var_parents)
+            self.loc_key_to_phi_parents[irblock.loc_key] = out
+
+    def back_propagate_to_parent(self, todo, node, parent):
+        parent_block = self.blocks[parent]
+        cur_block = self.blocks[node]
+        irblock = self.ircfg.blocks[node]
+        if cur_block.infos[0].var_in == parent_block.infos[-1].var_out:
+            return
+        var_info = cur_block.infos[0].var_in.union(parent_block.infos[-1].var_out)
+
+        if irblock_has_phi(irblock):
+            # Remove phi special case
+            out = set()
+            phi_sources = self.loc_key_to_phi_parents[irblock.loc_key]
+            for var in var_info:
+                if var not in phi_sources:
+                    out.add(var)
+                    continue
+                if parent in phi_sources[var]:
+                    out.add(var)
+            var_info = out
 
-        # Remove phi
-        assignblk_dct = get_assignblk(ssa.graph, phi_loc, phi_index)
-        del assignblk_dct[new_var]
+        parent_block.infos[-1].var_out = var_info
+        todo.add(parent)
 
 
-        new_irblock = set_assignblk(ssa.graph, phi_loc, phi_index, assignblk_dct)
-        ssa.graph.blocks[phi_loc] = new_irblock
diff --git a/test/analysis/unssa.py b/test/analysis/unssa.py
new file mode 100644
index 00000000..244b5436
--- /dev/null
+++ b/test/analysis/unssa.py
@@ -0,0 +1,652 @@
+""" 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
+from miasm2.core.locationdb import LocationDB
+from miasm2.analysis.data_flow import *
+from miasm2.ir.analysis import ira
+from miasm2.ir.ir import IRCFG, IRBlock, AssignBlock
+from miasm2.analysis.ssa import SSADiGraph, UnSSADiGraph, DiGraphLivenessSSA
+
+loc_db = LocationDB()
+
+a = ExprId("a", 32)
+b = ExprId("b", 32)
+c = ExprId("c", 32)
+d = ExprId("d", 32)
+r = ExprId("r", 32)
+x = ExprId("x", 32)
+y = ExprId("y", 32)
+u8 = ExprId("u8", 8)
+zf = ExprId('zf', 1)
+
+a_init = ExprId("a_init", 32)
+b_init = ExprId("b_init", 32)
+c_init = ExprId("c_init", 32)
+d_init = ExprId("d_init", 32)
+r_init = ExprId("r_init", 32) # Return register
+
+pc = ExprId("pc", 32)
+sp = ExprId("sp", 32)
+
+CST0 = ExprInt(0x0, 32)
+CST1 = ExprInt(0x1, 32)
+CST2 = ExprInt(0x2, 32)
+CST3 = ExprInt(0x3, 32)
+CSTX_8 = ExprInt(12, 8)
+
+LBL0 = loc_db.add_location("lbl0", 0)
+LBL1 = loc_db.add_location("lbl1", 1)
+LBL2 = loc_db.add_location("lbl2", 2)
+LBL3 = loc_db.add_location("lbl3", 3)
+LBL4 = loc_db.add_location("lbl4", 4)
+LBL5 = loc_db.add_location("lbl5", 5)
+LBL6 = loc_db.add_location("lbl6", 6)
+LBL7 = loc_db.add_location("lbl7", 7)
+
+IRDst = ExprId('IRDst', 32)
+dummy = ExprId('dummy', 32)
+
+
+def gen_irblock(label, exprs_list):
+    irs = []
+    for exprs in exprs_list:
+        if isinstance(exprs, AssignBlock):
+            irs.append(exprs)
+        else:
+            irs.append(AssignBlock(exprs))
+
+    irbl = IRBlock(label, irs)
+    return irbl
+
+
+class Regs(object):
+    regs_init = {a: a_init, b: b_init, c: c_init, d: d_init, r: r_init}
+    all_regs_ids = [a, b, c, d, r, sp, pc]
+
+class Arch(object):
+    regs = Regs()
+
+    def getpc(self, _):
+        return pc
+
+    def getsp(self, _):
+        return sp
+
+class IRATest(ira):
+
+    """Fake IRA class for tests"""
+
+    def __init__(self, loc_db=None):
+        arch = Arch()
+        super(IRATest, self).__init__(arch, 32, loc_db)
+        self.IRDst = IRDst
+        self.ret_reg = r
+
+    def get_out_regs(self, xx):
+        out = set()
+        """
+        for assignblk in xx:
+            for dst in assignblk:
+                if str(dst).startswith("r"):
+                    out.add(dst)
+        """
+        out.add(r)
+        return out
+
+IRA = IRATest(loc_db)
+END = ExprId("END", IRDst.size)
+
+G0_IRA = IRA.new_ircfg()
+
+G0_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G0_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(a, a+CST1)],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+G0_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G0_IRB0, G0_IRB1, G0_IRB2]:
+    G0_IRA.add_irblock(irb)
+
+
+
+G1_IRA = IRA.new_ircfg()
+
+G1_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST1)],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+G1_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(a, a+CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL3, 32))]
+])
+G1_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(a, a+CST2)],
+    [ExprAssign(IRDst, ExprLoc(LBL3, 32))]
+])
+G1_IRB3 = gen_irblock(LBL3, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G1_IRB0, G1_IRB1, G1_IRB2, G1_IRB3]:
+    G1_IRA.add_irblock(irb)
+
+
+
+
+
+G2_IRA = IRA.new_ircfg()
+
+G2_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST1)],
+    [ExprAssign(b, CST2)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G2_IRB1 = gen_irblock(LBL1, [
+    [
+        ExprAssign(a, b),
+        ExprAssign(b, a),
+    ],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+G2_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G2_IRB0, G2_IRB1, G2_IRB2]:
+    G2_IRA.add_irblock(irb)
+
+
+
+
+G3_IRA = IRA.new_ircfg()
+
+G3_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G3_IRB1 = gen_irblock(LBL1, [
+    [
+        ExprAssign(a, a + CST1),
+    ],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL2, 32),
+                                ExprCond(y,
+                                         ExprLoc(LBL3, 32),
+                                         ExprLoc(LBL5, 32)
+                                )
+    ))]
+])
+
+G3_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(a, a + CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+
+G3_IRB3 = gen_irblock(LBL3, [
+    [ExprAssign(a, a + CST2)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+
+G3_IRB4 = gen_irblock(LBL4, [
+    [ExprAssign(r, a + CST3)],
+    [
+        ExprAssign(IRDst,
+                   ExprCond(y,
+                            ExprLoc(LBL1, 32),
+                            ExprLoc(LBL5, 32)
+                   )
+        )
+    ]
+])
+
+
+G3_IRB5 = gen_irblock(LBL5, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G3_IRB0, G3_IRB1, G3_IRB2, G3_IRB3, G3_IRB5]:
+    G3_IRA.add_irblock(irb)
+
+
+
+
+
+
+G4_IRA = IRA.new_ircfg()
+
+G4_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G4_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL2, 32),
+                                ExprLoc(LBL3, 32)
+                                )
+    )]
+])
+G4_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(a, a+CST2)],
+    [ExprAssign(IRDst, ExprLoc(LBL4, 32))]
+])
+G4_IRB3 = gen_irblock(LBL3, [
+    [ExprAssign(a, a+CST3)],
+    [ExprAssign(IRDst, ExprLoc(LBL4, 32))]
+])
+G4_IRB4 = gen_irblock(LBL4, [
+    [ExprAssign(a, a+CST1)],
+    [
+        ExprAssign(
+            IRDst,
+            ExprCond(
+                x,
+                ExprLoc(LBL5, 32),
+                ExprLoc(LBL1, 32)
+            )
+        )
+    ]
+])
+
+G4_IRB5 = gen_irblock(LBL5, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G4_IRB0, G4_IRB1, G4_IRB2, G4_IRB3, G4_IRB4, G4_IRB5]:
+    G4_IRA.add_irblock(irb)
+
+
+
+
+
+G5_IRA = IRA.new_ircfg()
+
+G5_IRB0 = gen_irblock(LBL0, [
+    [
+        ExprAssign(a, CST1),
+        ExprAssign(b, CST1),
+    ],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+G5_IRB1 = gen_irblock(LBL1, [
+    [
+        ExprAssign(b, a),
+        ExprAssign(a, a+CST1)
+    ],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+G5_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(r, b)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G5_IRB0, G5_IRB1, G5_IRB2]:
+    G5_IRA.add_irblock(irb)
+
+
+
+G6_IRA = IRA.new_ircfg()
+
+G6_IRB0 = gen_irblock(LBL0, [
+    [
+        ExprAssign(a, CST1),
+        ExprAssign(b, CST1),
+    ],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+
+
+G6_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(a, a + CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL5, 32))]
+])
+
+
+G6_IRB2 = gen_irblock(LBL2, [
+    [
+        ExprAssign(a, a + CST1),
+    ],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL3, 32),
+                                ExprLoc(LBL4, 32)
+                                )
+    )]
+])
+
+G6_IRB3 = gen_irblock(LBL3, [
+    [
+        ExprAssign(b, a + CST1),
+    ],
+    [ExprAssign(IRDst, ExprLoc(LBL5, 32))],
+])
+
+
+G6_IRB4 = gen_irblock(LBL4, [
+    [
+        ExprAssign(b, a + CST1),
+    ],
+    [ExprAssign(IRDst, ExprLoc(LBL5, 32))],
+])
+
+G6_IRB5 = gen_irblock(LBL5, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G6_IRB0, G6_IRB1, G6_IRB2, G6_IRB3, G6_IRB4, G6_IRB5]:
+    G6_IRA.add_irblock(irb)
+
+
+
+
+
+G7_IRA = IRA.new_ircfg()
+
+G7_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, a + CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G7_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL2, 32),
+                                ExprLoc(LBL3, 32)
+                                )
+    )]
+])
+G7_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(IRDst, ExprLoc(LBL4, 32))]
+])
+G7_IRB3 = gen_irblock(LBL3, [
+    [ExprAssign(a, a+CST3)],
+    [ExprAssign(IRDst, ExprLoc(LBL4, 32))]
+])
+G7_IRB4 = gen_irblock(LBL4, [
+    [
+        ExprAssign(
+            IRDst,
+            ExprCond(
+                x,
+                ExprLoc(LBL5, 32),
+                ExprLoc(LBL1, 32)
+            )
+        )
+    ]
+])
+
+G7_IRB5 = gen_irblock(LBL5, [
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G7_IRB0, G7_IRB1, G7_IRB2, G7_IRB3, G7_IRB4, G7_IRB5]:
+    G7_IRA.add_irblock(irb)
+
+
+
+
+
+
+G8_IRA = IRA.new_ircfg()
+
+G8_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST0)],
+    [ExprAssign(b, c)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+
+G8_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(u8, ExprMem(b, 8))],
+    [
+        ExprAssign(
+            IRDst,
+            ExprCond(
+                u8,
+                ExprLoc(LBL2, 32),
+                ExprLoc(LBL7, 32)
+            )
+        )
+    ]
+])
+
+
+G8_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(b, b + CST1)],
+    [
+        ExprAssign(
+            IRDst,
+            ExprCond(
+                u8 + CSTX_8,
+                ExprLoc(LBL1, 32),
+                ExprLoc(LBL3, 32)
+            )
+        )
+    ]
+])
+
+
+
+G8_IRB3 = gen_irblock(LBL3, [
+    [
+        ExprAssign(a, (ExprMem(b, 8) + u8).zeroExtend(32))
+    ],
+    [
+        ExprAssign(
+            IRDst,
+            ExprLoc(LBL1, 32)
+        )
+    ]
+])
+
+
+
+G8_IRB4 = gen_irblock(LBL4, [
+    [ExprAssign(b, b + CST1)],
+    [ExprAssign(d, CST0)],
+    [ExprAssign(IRDst, ExprLoc(LBL6, 32))]
+])
+
+
+G8_IRB5 = gen_irblock(LBL5, [
+    [ExprAssign(d, CST1)],
+    [ExprAssign(IRDst, ExprLoc(LBL6, 32))]
+])
+
+
+G8_IRB6 = gen_irblock(LBL6, [
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+G8_IRB7 = gen_irblock(LBL7, [
+    [ExprAssign(b, CST2)],
+    [ExprAssign(r, a)],
+    [ExprAssign(IRDst, END)]
+])
+
+
+for irb in [G8_IRB0, G8_IRB1, G8_IRB2, G8_IRB3, G8_IRB7]:
+    G8_IRA.add_irblock(irb)
+
+
+
+G9_IRA = IRA.new_ircfg()
+
+G9_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+G9_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(b, CST1)],
+    [ExprAssign(IRDst, ExprCond(x,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+G9_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(r, b)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G9_IRB0, G9_IRB1, G9_IRB2]:
+    G9_IRA.add_irblock(irb)
+
+
+
+
+
+G10_IRA = IRA.new_ircfg()
+
+G10_IRB0 = gen_irblock(LBL0, [
+    [ExprAssign(a, CST0)],
+    [ExprAssign(IRDst, ExprLoc(LBL1, 32))]
+])
+
+G10_IRB1 = gen_irblock(LBL1, [
+    [ExprAssign(a, a+CST1)],
+    [ExprAssign(IRDst, ExprCond(a,
+                                ExprLoc(LBL1, 32),
+                                ExprLoc(LBL2, 32)
+                                )
+    )]
+])
+
+G10_IRB2 = gen_irblock(LBL2, [
+    [ExprAssign(r, CST1)],
+    [ExprAssign(IRDst, END)]
+])
+
+for irb in [G10_IRB0, G10_IRB1, G10_IRB2]:
+    G10_IRA.add_irblock(irb)
+
+
+
+
+ExprId.__repr__ = ExprId.__str__
+
+
+
+class IRAOutRegs(IRATest):
+    def get_out_regs(self, block):
+        regs_todo = super(self.__class__, self).get_out_regs(block)
+        out = {}
+        for assignblk in block:
+            for dst in assignblk:
+                reg = self.ssa_var.get(dst, None)
+                if reg is None:
+                    continue
+                if reg in regs_todo:
+                    out[reg] = dst
+        return set(out.values())
+
+
+
+def add_out_reg_end(ir_arch_a, ircfg_a):
+    # Add dummy dependency to uncover out regs affectation
+    for loc in ircfg_a.leaves():
+        irblock = ircfg_a.blocks.get(loc)
+        if irblock is None:
+            continue
+        regs = {}
+        for reg in ir_arch_a.get_out_regs(irblock):
+            regs[reg] = reg
+        assignblks = list(irblock)
+        new_assiblk = AssignBlock(regs, assignblks[-1].instr)
+        assignblks.append(new_assiblk)
+        new_irblock = IRBlock(irblock.loc_key, assignblks)
+        ircfg_a.blocks[loc] = new_irblock
+
+
+ir_arch_a = IRAOutRegs(loc_db)
+
+
+
+for test_nb, ircfg in enumerate(
+        [
+            G0_IRA,
+            G1_IRA,
+            G2_IRA,
+            G3_IRA,
+            G4_IRA,
+            G5_IRA,
+            G6_IRA,
+            G7_IRA,
+            G8_IRA,
+            G9_IRA,
+            G10_IRA,
+        ]):
+
+    open('graph_%d.dot' % test_nb, 'w').write(ircfg.dot())
+
+    # Save a copy of ircfg
+    ircfg_orig = IRCFG(IRDst, loc_db)
+    for irblock in ircfg.blocks.values():
+        ircfg_orig.add_irblock(irblock)
+
+    # 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())
+
+    # XXX TODO: add real regression test
diff --git a/test/test_all.py b/test/test_all.py
index f3bcc477..008d837f 100755
--- a/test/test_all.py
+++ b/test/test_all.py
@@ -384,6 +384,7 @@ testset += RegressionTest(["data_flow.py"], base_dir="analysis",
             ["simp_graph_%02d.dot" % test_nb, "graph_%02d.dot" % test_nb]
             for test_nb in xrange(1, 18))
                                     for fname in fnames])
+testset += RegressionTest(["unssa.py"], base_dir="analysis")
 
 for i in xrange(1, 21):
     input_name = "cst_propag/x86_32_sc_%d" % i
@@ -604,17 +605,17 @@ class ExampleDisasmFull(ExampleDisassembler):
 
 
 testset += ExampleDisasmFull(["arml", Example.get_sample("demo_arm_l.bin"),
-                              "0"], depends=[test_arml])
+                              "0x2c", "-z"], depends=[test_arml])
 testset += ExampleDisasmFull(["armb", Example.get_sample("demo_arm_b.bin"),
-                              "0"], depends=[test_armb])
+                              "0x2c", "-z"], depends=[test_armb])
 testset += ExampleDisasmFull(["arml", Example.get_sample("demo_arm2_l.bin"),
-                              "0"], depends=[test_arml_sc])
+                              "0x0", "-z"], depends=[test_arml_sc])
 testset += ExampleDisasmFull(["armb", Example.get_sample("demo_arm2_b.bin"),
-                              "0"], depends=[test_armb_sc])
+                              "0x0", "-z"], depends=[test_armb_sc])
 testset += ExampleDisasmFull(["armtl", Example.get_sample("demo_armt_l.bin"),
-                              "0"], depends=[test_armtl])
+                              "0x2c", "-z"], depends=[test_armtl])
 testset += ExampleDisasmFull(["armtb", Example.get_sample("demo_armt_b.bin"),
-                              "0"], depends=[test_armtb])
+                              "0x2c", "-z"], depends=[test_armtb])
 testset += ExampleDisasmFull(["aarch64l", Example.get_sample("demo_aarch64_l.bin"),
                               "0"], depends=[test_aarch64l])
 testset += ExampleDisasmFull(["aarch64b", Example.get_sample("demo_aarch64_b.bin"),