Merge pull request #154 from carolineLe/dead_code_simp

IR: Improve dead code elimination

5 files changed, 966 insertions, 164 deletions

diff --git a/miasm2/expression/expression.py b/miasm2/expression/expression.py
index 154da7cc..2b51ef61 100644
--- a/miasm2/expression/expression.py
+++ b/miasm2/expression/expression.py
@@ -152,6 +152,11 @@ class Expr(object):
     def get_w(self):
         return self.arg.get_w()
 
+    def is_function_call(self):
+        """Returns true if the considered Expr is a function call
+        """
+        return False
+
     def __repr__(self):
         if self._repr is None:
             self._repr = self._exprrepr()
@@ -512,6 +517,9 @@ class ExprAff(Expr):
         else:
             return self._dst.get_w()
 
+    def is_function_call(self):
+        return isinstance(self.src, ExprOp) and self.src.op.startswith('call')
+
     def _exprhash(self):
         return hash((EXPRAFF, hash(self._dst), hash(self._src)))
 
diff --git a/miasm2/ir/analysis.py b/miasm2/ir/analysis.py
index ad37a1df..87c53d44 100644
--- a/miasm2/ir/analysis.py
+++ b/miasm2/ir/analysis.py
@@ -6,7 +6,7 @@ import logging
 from miasm2.ir.symbexec import symbexec
 from miasm2.core.graph import DiGraph
 from miasm2.expression.expression \
-    import ExprAff, ExprCond, ExprId, ExprInt, ExprMem, ExprOp
+    import ExprAff, ExprCond, ExprId, ExprInt, ExprMem
 
 log = logging.getLogger("analysis")
 console_handler = logging.StreamHandler()
@@ -16,6 +16,10 @@ log.setLevel(logging.WARNING)
 
 class ira:
 
+    def ira_regs_ids(self):
+        """Returns ids of all registers used in the IR"""
+        return self.arch.regs.all_regs_ids + [self.IRDst]
+
     def sort_dst(self, todo, done):
         out = set()
         while todo:
@@ -115,194 +119,244 @@ class ira:
         out += '}'
         return out
 
-    def remove_dead(self, irb):
-        """Remove dead affectations using previous liveness analysis
+    def remove_dead_instr(self, irb, useful):
+        """Remove dead affectations using previous reaches analysis
         @irb: irbloc instance
-        Return True iff the bloc state has changed
-        PRE: compute_in_out(@irb)
+        @useful: useful statements from previous reach analysis
+        Return True iff the block state has changed
+        PRE: compute_reach(self)
         """
-
-        # print 'state1'
-        # self.dump_bloc_state(irb)
-
         modified = False
-        for ir, _, c_out in zip(irb.irs, irb.c_in, irb.c_out):
+        for k, ir in enumerate(irb.irs):
             j = 0
             while j < len(ir):
-                i_cur = ir[j]
-                if not isinstance(i_cur.dst, ExprId):
-                    pass
-                elif i_cur.dst == self.IRDst:
-                    # never delete irdst
-                    pass
-                elif (isinstance(i_cur.src, ExprOp) and
-                    i_cur.src.op.startswith('call')):
-                    # /!\ never remove ir calls
-                    pass
-                elif i_cur.dst not in c_out:
-                    del(ir[j])
+                cur_instr = ir[j]
+                if (isinstance(cur_instr.dst, ExprId)
+                    and (irb.label, k, cur_instr) not in useful):
+                    del ir[j]
                     modified = True
-                    continue
-                j += 1
+                else:
+                    j += 1
+        return modified
 
-        # print 'state2'
-        # self.dump_bloc_state(irb)
+    def init_useful_instr(self):
+        """Computes a set of triples (block, instruction number, instruction)
+        containing initially useful instructions :
+          - Instructions affecting final value of return registers
+          - Instructions affecting IRDst register
+          - Instructions writing in memory
+          - Function call instructions
+        Return set of intial useful instructions
+        """
 
-        return modified
+        useful = set()
+
+        for node in self.g.nodes():
+            if node not in self.blocs:
+                continue
+
+            block = self.blocs[node]
+            successors = self.g.successors(node)
+            has_son = bool(successors)
+            for p_son in successors:
+                if p_son not in self.blocs:
+                    # Leaf has lost its son: don't remove anything
+                    # reaching this block
+                    for r in self.ira_regs_ids():
+                        useful.update(block.cur_reach[-1][r].union(
+                                block.defout[-1][r]))
+
+            # Function call, memory write or IRDst affectation
+            for k, ir in enumerate(block.irs):
+                for i_cur in ir:
+                    if i_cur.is_function_call():
+                        # /!\ never remove ir calls
+                        useful.add((block.label, k, i_cur))
+                    if isinstance(i_cur.dst, ExprMem):
+                        useful.add((block.label, k, i_cur))
+                    useful.update(block.defout[k][self.IRDst])
+
+            # Affecting return registers
+            if not has_son:
+                for r in self.get_out_regs(block):
+                    useful.update(block.defout[-1][r]
+                                  if block.defout[-1][r] else
+                                  block.cur_reach[-1][r])
+
+        return useful
+
+    def _mark_useful_code(self):
+        """Mark useful statements using previous reach analysis
+
+        Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
+        IBM Thomas J. Watson Research Division,  Algorithm MK
+
+        Return a set of triplets (block, instruction number, instruction) of
+        useful instructions
+        PRE: compute_reach(self)
 
-    def remove_blocs_dead(self):
-        """Call remove_dead on each irbloc
-        Return True iff one of the bloc state has changed
         """
+
+        useful = self.init_useful_instr()
+        worklist = useful.copy()
+        while worklist:
+            elem = worklist.pop()
+            useful.add(elem)
+            irb, irs_ind, ins = elem
+
+            block = self.blocs[irb]
+            instr_defout = block.defout[irs_ind]
+            cur_kill = block.cur_kill[irs_ind]
+            cur_reach = block.cur_reach[irs_ind]
+
+            # Handle dependencies of used variables in ins
+            for reg in ins.get_r(True).intersection(self.ira_regs_ids()):
+                worklist.update(
+                    cur_reach[reg].difference(useful).difference(
+                        cur_kill[reg]
+                        if not instr_defout[reg] else
+                        set()))
+                for _, _, i in instr_defout[reg]:
+                    # Loop case (i in defout of current block)
+                    if i == ins:
+                        worklist.update(cur_reach[reg].difference(useful))
+        return useful
+
+    def remove_dead_code(self):
+        """Remove dead instructions in each block of the graph using the reach
+        analysis .
+        Returns True if a block has been modified
+        PRE : compute_reach(self)
+        """
+        useful = self._mark_useful_code()
         modified = False
-        for b in self.blocs.values():
-            modified |= self.remove_dead(b)
+        for block in self.blocs.values():
+            modified |= self.remove_dead_instr(block, useful)
         return modified
 
-    # for test XXX TODO
     def set_dead_regs(self, b):
         pass
 
     def add_unused_regs(self):
         pass
 
+    @staticmethod
+    def print_set(v_set):
+        """Print each triplet contained in a set
+        @v_set: set containing triplets elements
+        """
+        for p in v_set:
+            print '    (%s, %s, %s)' % p
+
     def dump_bloc_state(self, irb):
         print '*'*80
-        for i, (ir, c_in, c_out) in enumerate(zip(irb.irs, irb.c_in, irb.c_out)):
-            print 'ir'
-            for x in ir:
-                print '\t', x
-            print 'R', [str(x) for x in irb.r[i]]#c_in]
-            print 'W', [str(x) for x in irb.w[i]]#c_out]
-            print 'IN', [str(x) for x in c_in]
-            print 'OUT', [str(x) for x in c_out]
-
-
-    def compute_in_out(self, irb):
-        """Liveness computation for a single bloc
+        for k, irs in enumerate(irb.irs):
+            for i in xrange(len(irs)):
+                print 5*"-"
+                print 'instr', k, irs[i]
+                print 5*"-"
+                for v in self.ira_regs_ids():
+                    if irb.cur_reach[k][v]:
+                        print 'REACH[%d][%s]' % (k, v)
+                        self.print_set(irb.cur_reach[k][v])
+                    if irb.cur_kill[k][v]:
+                        print 'KILL[%d][%s]' % (k, v)
+                        self.print_set(irb.cur_kill[k][v])
+                    if irb.defout[k][v]:
+                        print 'DEFOUT[%d][%s]' % (k, v)
+                        self.print_set(irb.defout[k][v])
+
+    def compute_reach_block(self, irb):
+        """Variable influence computation for a single block
         @irb: irbloc instance
-        Return True iff bloc state has changed
+        PRE: init_reach()
         """
-        modified = False
-
-        # Compute OUT for last irb entry
-        c_out = set()
-        has_son = False
-        for n_son in self.g.successors(irb.label):
-            has_son = True
-            if n_son not in self.blocs:
-                # If the son is not defined, we will propagate our current out
-                # nodes to the in nodes's son
-                son_c_in = irb.c_out_missing
-            else:
-                son_c_in = self.blocs[n_son].c_in[0]
-            c_out.update(son_c_in)
-        if not has_son:
-            # Special case: leaf nodes architecture dependant
-            c_out = self.get_out_regs(irb)
-
-        if irb.c_out[-1] != c_out:
-            irb.c_out[-1] = c_out
-            modified = True
-
-        # Compute out/in intra bloc
-        for i in reversed(xrange(len(irb.irs))):
-            new_in = set(irb.r[i].union(irb.c_out[i].difference(irb.w[i])))
-            if irb.c_in[i] != new_in:
-                irb.c_in[i] = new_in
-                modified = True
-
-            if i >= len(irb.irs) - 1:
-                # Last out has been previously updated
-                continue
-            new_out = set(irb.c_in[i + 1])
-            if irb.c_out[i] != new_out:
-                irb.c_out[i] = new_out
-                modified = True
 
-        return modified
-
-    def test_in_out_fix(self):
-        """Return True iff a fixed point has been reached during liveness
+        reach_block = {key: value.copy()
+                      for key, value in irb.cur_reach[0].iteritems()}
+
+        # Compute reach from predecessors
+        for n_pred in self.g.predecessors(irb.label):
+            p_block = self.blocs[n_pred]
+
+            # Handle each register definition
+            for c_reg in self.ira_regs_ids():
+                # REACH(n) = U[p in pred] DEFOUT(p) U REACH(p)\KILL(p)
+                pred_through = p_block.defout[-1][c_reg].union(
+                    p_block.cur_reach[-1][c_reg].difference(
+                        p_block.cur_kill[-1][c_reg]))
+                reach_block[c_reg].update(pred_through)
+
+        # If a predecessor has changed
+        if reach_block != irb.cur_reach[0]:
+            irb.cur_reach[0] = reach_block
+            for c_reg in self.ira_regs_ids():
+                if irb.defout[0][c_reg]:
+                    # KILL(n) = DEFOUT(n) ? REACH(n)\DEFOUT(n) : EMPTY
+                    irb.cur_kill[0][c_reg].update(
+                        reach_block[c_reg].difference(irb.defout[0][c_reg]))
+
+        # Compute reach and kill for block's instructions
+        for i in xrange(1, len(irb.irs)):
+            for c_reg in self.ira_regs_ids():
+                # REACH(n) = U[p in pred] DEFOUT(p) U REACH(p)\KILL(p)
+                pred_through = irb.defout[i - 1][c_reg].union(
+                    irb.cur_reach[i - 1][c_reg].difference(
+                        irb.cur_kill[i - 1][c_reg]))
+                irb.cur_reach[i][c_reg].update(pred_through)
+                if irb.defout[i][c_reg]:
+                    # KILL(n) = DEFOUT(n) ? REACH(n)\DEFOUT(n) : EMPTY
+                    irb.cur_kill[i][c_reg].update(
+                        irb.cur_reach[i][c_reg].difference(
+                            irb.defout[i][c_reg]))
+
+    def _test_kill_reach_fix(self):
+        """Return True iff a fixed point has been reached during reach
         analysis"""
 
         fixed = True
         for node in self.g.nodes():
-            if node not in self.blocs:
-                # leaf has lost her son
-                continue
-            irb = self.blocs[node]
-            if irb.c_in != irb.l_in or irb.c_out != irb.l_out:
-                fixed = False
-            irb.l_in = [set(x) for x in irb.c_in]
-            irb.l_out = [set(x) for x in irb.c_out]
+            if node in self.blocs:
+                irb = self.blocs[node]
+                if (irb.cur_reach != irb.prev_reach or
+                    irb.cur_kill != irb.prev_kill):
+                    fixed = False
+                    irb.prev_reach = irb.cur_reach[:]
+                    irb.prev_kill = irb.cur_kill[:]
         return fixed
 
-    def fill_missing_son_c_in(self):
-        """Find nodes with missing sons in graph, and add virtual link to all
-        written variables of all parents.
-        PRE: gen_graph() and get_rw()"""
+    def compute_reach(self):
+        """
+        Compute reach, defout and kill sets until a fixed point is reached.
+
+        Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
+        IBM Thomas J. Watson Research Division, page 43
 
-        for node in self.g.nodes():
-            if node not in self.blocs:
-                continue
-            self.blocs[node].c_out_missing = set()
-            has_all_son = True
-            for node_son in self.g.successors(node):
-                if node_son not in self.blocs:
-                    has_all_son = False
-                    break
-            if has_all_son:
-                continue
-            parents = self.g.reachable_parents(node)
-            for parent in parents:
-                irb = self.blocs[parent]
-                for var_w in irb.w:
-                    self.blocs[node].c_out_missing.update(var_w)
-
-    def compute_dead(self):
-        """Iterate liveness analysis until a fixed point is reached.
         PRE: gen_graph()
         """
-
-        it = 0
         fixed_point = False
         log.debug('iteration...')
         while not fixed_point:
-            log.debug(it)
-            it += 1
-            for n in self.g.nodes():
-                if n not in self.blocs:
-                    # leaf has lost her son
-                    continue
-                irb = self.blocs[n]
-                self.compute_in_out(irb)
-
-            fixed_point = self.test_in_out_fix()
+            for node in self.g.nodes():
+                if node in self.blocs:
+                    self.compute_reach_block(self.blocs[node])
+            fixed_point = self._test_kill_reach_fix()
 
     def dead_simp(self):
-        """This function is used to analyse relation of a * complete function *
-        This mean the blocs under study represent a solid full function graph.
-
-        Ref: CS 5470 Compiler Techniques and Principles (Liveness
-        analysis/Dataflow equations)
-
-        PRE: call to gen_graph
         """
+        This function is used to analyse relation of a * complete function *
+        This means the blocks under study represent a solid full function graph.
 
-        modified = True
-        while modified:
-            log.debug('dead_simp step')
-
-            # Update r/w variables for all irblocs
-            self.get_rw()
-            # Fill c_in for missing sons
-            self.fill_missing_son_c_in()
-
-            # Liveness step
-            self.compute_dead()
-            modified = self.remove_blocs_dead()
+        Source : Kennedy, K. (1979). A survey of data flow analysis techniques.
+        IBM Thomas J. Watson Research Division, page 43
 
+        PRE: gen_graph()
+        """
+        # Update r/w variables for all irblocs
+        self.get_rw(self.ira_regs_ids())
+        # Liveness step
+        self.compute_reach()
+        self.remove_dead_code()
         # Simplify expressions
         self.simplify_blocs()
 
diff --git a/miasm2/ir/ir.py b/miasm2/ir/ir.py
index 5d77c5a1..32c97661 100644
--- a/miasm2/ir/ir.py
+++ b/miasm2/ir/ir.py
@@ -73,27 +73,40 @@ class irbloc(object):
         """Line number of the IRDst setting statement in the current irs"""
         return self._dst_linenb
 
-    def get_rw(self):
+    def get_rw(self, regs_ids):
+        """
+        Computes the variables read and written by each instructions
+        Initialize attributes needed for in/out and reach computation.
+        @regs_ids : ids of registers used in IR
+        """
         self.r = []
         self.w = []
-        self.c_out = []
-        self.c_in = []
-        self.l_out = []
-        self.l_in = []
-        for ir in self.irs:
+        self.cur_reach = [{reg: set() for reg in regs_ids}
+                          for _ in xrange(len(self.irs))]
+        self.prev_reach = [{reg: set() for reg in regs_ids}
+                           for _ in xrange(len(self.irs))]
+        self.cur_kill = [{reg: set() for reg in regs_ids}
+                         for _ in xrange(len(self.irs))]
+        self.prev_kill = [{reg: set() for reg in regs_ids}
+                          for _ in xrange(len(self.irs))]
+        self.defout = [{reg: set() for reg in regs_ids}
+                       for _ in xrange(len(self.irs))]
+
+        for k, ir in enumerate(self.irs):
             r, w = set(), set()
             for i in ir:
-                r.update([x for x in i.get_r(True) if isinstance(x, m2_expr.ExprId)])
-                w.update([x for x in i.get_w() if isinstance(x, m2_expr.ExprId)])
+                r.update(x for x in i.get_r(True)
+                         if isinstance(x, m2_expr.ExprId))
+                w.update(x for x in i.get_w()
+                         if isinstance(x, m2_expr.ExprId))
                 if isinstance(i.dst, m2_expr.ExprMem):
-                    r.update([x for x in i.dst.arg.get_r(True)
-                    if isinstance(x, m2_expr.ExprId)])
+                    r.update(x for x in i.dst.arg.get_r(True)
+                             if isinstance(x, m2_expr.ExprId))
+                self.defout[k].update((x, {(self.label, k, i)})
+                                      for x in i.get_w()
+                                      if isinstance(x, m2_expr.ExprId))
             self.r.append(r)
             self.w.append(w)
-            self.c_out.append(set())
-            self.c_in.append(set())
-            self.l_out.append(set())
-            self.l_in.append(set())
 
     def __str__(self):
         o = []
@@ -301,9 +314,13 @@ class ir(object):
             for i, l in enumerate(irs):
                 irs[i] = l.replace_expr(rep)
 
-    def get_rw(self):
+    def get_rw(self, regs_ids = []):
+        """
+        Calls get_rw(irb) for each bloc
+        @regs_ids : ids of registers used in IR
+        """
         for b in self.blocs.values():
-            b.get_rw()
+            b.get_rw(regs_ids)
 
     def ExprIsLabel(self, l):
         return isinstance(l, m2_expr.ExprId) and isinstance(l.name,
diff --git a/test/ir/analysis.py b/test/ir/analysis.py
new file mode 100755
index 00000000..92aa4aba
--- /dev/null
+++ b/test/ir/analysis.py
@@ -0,0 +1,718 @@
+""" Test cases for dead code elimination"""
+from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprMem
+from miasm2.core.asmbloc import asm_label
+from miasm2.ir.analysis import ira
+from miasm2.ir.ir import ir, irbloc
+
+a = ExprId("a")
+b = ExprId("b")
+c = ExprId("c")
+d = ExprId("d")
+r = ExprId("r")
+
+a_init = ExprId("a_init")
+b_init = ExprId("b_init")
+c_init = ExprId("c_init")
+d_init = ExprId("d_init")
+r_init = ExprId("r_init") # Return register
+
+pc = ExprId("pc")
+sp = ExprId("sp")
+
+CST1 = ExprInt32(0x11)
+CST2 = ExprInt32(0x12)
+CST3 = ExprInt32(0x13)
+
+LBL0 = asm_label("lbl0")
+LBL1 = asm_label("lbl1")
+LBL2 = asm_label("lbl2")
+LBL3 = asm_label("lbl3")
+LBL4 = asm_label("lbl4")
+LBL5 = asm_label("lbl5")
+LBL6 = asm_label("lbl6")
+
+
+
+def gen_irbloc(label, exprs):
+    lines = [None for _ in xrange(len(exprs))]
+    irbl = irbloc(label, exprs, lines)
+    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(ir, ira):
+
+    def __init__(self, symbol_pool=None):
+        arch = Arch()
+        ir.__init__(self, arch, 32, symbol_pool)
+        self.IRDst = pc
+        self.ret_reg = r
+
+    def get_out_regs(self, _):
+        return set([self.ret_reg, self.sp])
+
+# graph 1 : Simple graph with dead and alive variables
+
+G1_IRA = IRATest()
+
+G1_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]])
+G1_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, b)]])
+G1_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+
+G1_IRA.gen_graph()
+
+G1_IRA.g.add_uniq_edge(G1_IRB0.label, G1_IRB1.label)
+G1_IRA.g.add_uniq_edge(G1_IRB1.label, G1_IRB2.label)
+
+G1_IRA.blocs = {irb.label : irb for irb in [G1_IRB0, G1_IRB1, G1_IRB2]}
+
+# Expected output for graph 1
+G1_EXP_IRA = IRATest()
+
+G1_EXP_IRB0 = gen_irbloc(LBL0, [[], [ExprAff(b, CST2)]])
+G1_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, b)]])
+G1_EXP_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+
+G1_EXP_IRA.blocs = {irb.label : irb for irb in [G1_EXP_IRB0, G1_EXP_IRB1,
+                                                G1_EXP_IRB2]}
+
+# graph 2 : Natural loop with dead variable
+
+G2_IRA = IRATest()
+
+G2_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(r, CST1)]])
+G2_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G2_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, r)]])
+
+G2_IRA.gen_graph()
+
+G2_IRA.g.add_uniq_edge(G2_IRB0.label, G2_IRB1.label)
+G2_IRA.g.add_uniq_edge(G2_IRB1.label, G2_IRB2.label)
+G2_IRA.g.add_uniq_edge(G2_IRB1.label, G2_IRB1.label)
+
+G2_IRA.blocs = {irb.label : irb for irb in [G2_IRB0, G2_IRB1, G2_IRB2]}
+
+# Expected output for graph 2
+G2_EXP_IRA = IRATest()
+
+G2_EXP_IRB0 = gen_irbloc(LBL0, [[], [ExprAff(r, CST1)]])
+G2_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G2_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+
+G2_EXP_IRA.blocs = {irb.label : irb for irb in [G2_EXP_IRB0, G2_EXP_IRB1,
+                                                G2_EXP_IRB2]}
+
+# graph 3 : Natural loop with alive variables
+
+G3_IRA = IRATest()
+
+G3_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G3_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G3_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+
+G3_IRA.gen_graph()
+
+G3_IRA.g.add_uniq_edge(G3_IRB0.label, G3_IRB1.label)
+G3_IRA.g.add_uniq_edge(G3_IRB1.label, G3_IRB2.label)
+G3_IRA.g.add_uniq_edge(G3_IRB1.label, G3_IRB1.label)
+
+G3_IRA.blocs = {irb.label : irb for irb in [G3_IRB0, G3_IRB1, G3_IRB2]}
+
+# Expected output for graph 3
+G3_EXP_IRA = IRATest()
+
+G3_EXP_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G3_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G3_EXP_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+
+G3_EXP_IRA.blocs = {irb.label : irb for irb in [G3_EXP_IRB0, G3_EXP_IRB1,
+                                                G3_EXP_IRB2]}
+
+# graph 4 : If/else with dead variables
+
+G4_IRA = IRATest()
+
+G4_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G4_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G4_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, a+CST2)]])
+G4_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, CST3)], [ExprAff(r, a)]])
+
+G4_IRA.gen_graph()
+
+G4_IRA.g.add_uniq_edge(G4_IRB0.label, G4_IRB1.label)
+G4_IRA.g.add_uniq_edge(G4_IRB0.label, G4_IRB2.label)
+G4_IRA.g.add_uniq_edge(G4_IRB1.label, G4_IRB3.label)
+G4_IRA.g.add_uniq_edge(G4_IRB2.label, G4_IRB3.label)
+
+G4_IRA.blocs = {irb.label : irb for irb in [G4_IRB0, G4_IRB1, G4_IRB2,
+                                            G4_IRB3]}
+
+# Expected output for graph 4
+G4_EXP_IRA = IRATest()
+
+G4_EXP_IRB0 = gen_irbloc(LBL0, [[]])
+G4_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G4_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G4_EXP_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, CST3)], [ExprAff(r, a)]])
+
+G4_EXP_IRA.gen_graph()
+
+G4_EXP_IRA.blocs = {irb.label : irb for irb in [G4_EXP_IRB0, G4_EXP_IRB1,
+                                                G4_EXP_IRB2, G4_EXP_IRB3]}
+
+# graph 5 : Loop and If/else with dead variables
+
+G5_IRA = IRATest()
+
+G5_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G5_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, CST2)]])
+G5_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, a+CST2)]])
+G5_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, a+CST3)]])
+G5_IRB4 = gen_irbloc(LBL4, [[ExprAff(a, a+CST1)]])
+G5_IRB5 = gen_irbloc(LBL5, [[ExprAff(a, r)]])
+
+G5_IRA.gen_graph()
+
+G5_IRA.g.add_uniq_edge(G5_IRB0.label, G5_IRB1.label)
+G5_IRA.g.add_uniq_edge(G5_IRB1.label, G5_IRB2.label)
+G5_IRA.g.add_uniq_edge(G5_IRB1.label, G5_IRB3.label)
+G5_IRA.g.add_uniq_edge(G5_IRB2.label, G5_IRB4.label)
+G5_IRA.g.add_uniq_edge(G5_IRB3.label, G5_IRB4.label)
+G5_IRA.g.add_uniq_edge(G5_IRB4.label, G5_IRB5.label)
+G5_IRA.g.add_uniq_edge(G5_IRB4.label, G5_IRB1.label)
+
+G5_IRA.blocs = {irb.label : irb for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3,
+                                            G5_IRB4, G5_IRB5]}
+
+# Expected output for graph 5
+G5_EXP_IRA = IRATest()
+
+G5_EXP_IRB0 = gen_irbloc(LBL0, [[]])
+G5_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, CST2)]])
+G5_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G5_EXP_IRB3 = gen_irbloc(LBL3, [[]])
+G5_EXP_IRB4 = gen_irbloc(LBL4, [[]])
+G5_EXP_IRB5 = gen_irbloc(LBL5, [[]])
+
+G5_EXP_IRA.gen_graph()
+
+G5_EXP_IRA.blocs = {irb.label : irb for irb in [G5_EXP_IRB0, G5_EXP_IRB1,
+                                                G5_EXP_IRB2, G5_EXP_IRB3,
+                                                G5_EXP_IRB4, G5_EXP_IRB5]}
+
+# graph 6 : Natural loop with dead variables symetric affectation
+# (a = b <-> b = a )
+
+G6_IRA = IRATest()
+
+G6_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G6_IRB1 = gen_irbloc(LBL1, [[ExprAff(b, a)]])
+G6_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, b)]])
+G6_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST2)]])
+
+
+G6_IRA.gen_graph()
+
+G6_IRA.g.add_uniq_edge(G6_IRB0.label, G6_IRB1.label)
+G6_IRA.g.add_uniq_edge(G6_IRB1.label, G6_IRB2.label)
+G6_IRA.g.add_uniq_edge(G6_IRB2.label, G6_IRB1.label)
+G6_IRA.g.add_uniq_edge(G6_IRB2.label, G6_IRB3.label)
+
+G6_IRA.blocs = {irb.label : irb for irb in [G6_IRB0, G6_IRB1, G6_IRB2,
+                                            G6_IRB3]}
+
+# Expected output for graph 6
+G6_EXP_IRA = IRATest()
+
+G6_EXP_IRB0 = gen_irbloc(LBL0, [[]])
+G6_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G6_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G6_EXP_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST2)]])
+
+G6_EXP_IRA.blocs = {irb.label : irb for irb in [G6_EXP_IRB0, G6_EXP_IRB1,
+                                                G6_EXP_IRB2, G6_EXP_IRB3]}
+
+# graph 7 : Double entry loop with dead variables
+
+G7_IRA = IRATest()
+
+G7_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(r, CST1)]])
+G7_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G7_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, a+CST2)]])
+G7_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, r)]])
+
+
+G7_IRA.gen_graph()
+
+G7_IRA.g.add_uniq_edge(G7_IRB0.label, G7_IRB1.label)
+G7_IRA.g.add_uniq_edge(G7_IRB1.label, G7_IRB2.label)
+G7_IRA.g.add_uniq_edge(G7_IRB2.label, G7_IRB1.label)
+G7_IRA.g.add_uniq_edge(G7_IRB2.label, G7_IRB3.label)
+G7_IRA.g.add_uniq_edge(G7_IRB0.label, G7_IRB2.label)
+
+
+G7_IRA.blocs = {irb.label : irb for irb in [G7_IRB0, G7_IRB1, G7_IRB2,
+                                            G7_IRB3]}
+
+# Expected output for graph 7
+G7_EXP_IRA = IRATest()
+
+G7_EXP_IRB0 = gen_irbloc(LBL0, [[], [ExprAff(r, CST1)]])
+G7_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G7_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G7_EXP_IRB3 = gen_irbloc(LBL3, [[]])
+
+G7_EXP_IRA.blocs = {irb.label : irb for irb in [G7_EXP_IRB0, G7_EXP_IRB1,
+                                                G7_EXP_IRB2, G7_EXP_IRB3]}
+
+# graph 8 : Nested loops with dead variables
+
+G8_IRA = IRATest()
+
+G8_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]])
+G8_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)]])
+G8_IRB2 = gen_irbloc(LBL2, [[ExprAff(b, b+CST2)]])
+G8_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, b)]])
+
+
+G8_IRA.gen_graph()
+
+G8_IRA.g.add_uniq_edge(G8_IRB0.label, G8_IRB1.label)
+G8_IRA.g.add_uniq_edge(G8_IRB1.label, G8_IRB2.label)
+G8_IRA.g.add_uniq_edge(G8_IRB2.label, G8_IRB1.label)
+G8_IRA.g.add_uniq_edge(G8_IRB2.label, G8_IRB3.label)
+G8_IRA.g.add_uniq_edge(G8_IRB3.label, G8_IRB2.label)
+
+
+G8_IRA.blocs = {irb.label : irb for irb in [G8_IRB0, G8_IRB1, G8_IRB2,
+                                            G8_IRB3]}
+
+# Expected output for graph 8
+
+G8_EXP_IRA = IRATest()
+
+G8_EXP_IRB0 = gen_irbloc(LBL0, [[], []])
+G8_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G8_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G8_EXP_IRB3 = gen_irbloc(LBL3, [[]])
+
+G8_EXP_IRA.blocs = {irb.label : irb for irb in [G8_EXP_IRB0, G8_EXP_IRB1,
+                                                G8_EXP_IRB2, G8_EXP_IRB3]}
+
+# graph 9 : Miultiple-exits loops with dead variables
+
+G9_IRA = IRATest()
+
+G9_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]])
+G9_IRB1 = gen_irbloc(LBL1, [[ExprAff(a, a+CST1)], [ExprAff(b, b+CST1)]])
+G9_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, a+CST2)], [ExprAff(b, b+CST2)]])
+G9_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, b)]])
+G9_IRB4 = gen_irbloc(LBL4, [[ExprAff(r, a)], [ExprAff(r, b)]])
+
+
+G9_IRA.gen_graph()
+
+G9_IRA.g.add_uniq_edge(G9_IRB0.label, G9_IRB4.label)
+G9_IRA.g.add_uniq_edge(G9_IRB0.label, G9_IRB1.label)
+G9_IRA.g.add_uniq_edge(G9_IRB1.label, G9_IRB0.label)
+G9_IRA.g.add_uniq_edge(G9_IRB1.label, G9_IRB4.label)
+G9_IRA.g.add_uniq_edge(G9_IRB1.label, G9_IRB2.label)
+G9_IRA.g.add_uniq_edge(G9_IRB2.label, G9_IRB0.label)
+G9_IRA.g.add_uniq_edge(G9_IRB2.label, G9_IRB3.label)
+G9_IRA.g.add_uniq_edge(G9_IRB3.label, G9_IRB4.label)
+
+
+G9_IRA.blocs = {irb.label : irb for irb in [G9_IRB0, G9_IRB1, G9_IRB2,
+                                            G9_IRB3, G9_IRB4]}
+
+# Expected output for graph 9
+
+G9_EXP_IRA = IRATest()
+
+G9_EXP_IRB0 = gen_irbloc(LBL0, [[], [ExprAff(b, CST1)]])
+G9_EXP_IRB1 = gen_irbloc(LBL1, [[], [ExprAff(b, b+CST1)]])
+G9_EXP_IRB2 = gen_irbloc(LBL2, [[], [ExprAff(b, b+CST2)]])
+G9_EXP_IRB3 = gen_irbloc(LBL3, [[]])
+G9_EXP_IRB4 = gen_irbloc(LBL4, [[], [ExprAff(r, b)]])
+
+G9_EXP_IRA.blocs = {irb.label : irb for irb in [G9_EXP_IRB0, G9_EXP_IRB1,
+                                                G9_EXP_IRB2, G9_EXP_IRB3,
+                                                G9_EXP_IRB4]}
+
+# graph 10 : Natural loop with alive variables symetric affectation
+# (a = b <-> b = a )
+
+G10_IRA = IRATest()
+
+G10_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)]])
+G10_IRB1 = gen_irbloc(LBL1, [[ExprAff(b, a)]])
+G10_IRB2 = gen_irbloc(LBL2, [[ExprAff(a, b)]])
+G10_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST1)]])
+
+
+G10_IRA.gen_graph()
+
+G10_IRA.g.add_uniq_edge(G10_IRB0.label, G10_IRB1.label)
+G10_IRA.g.add_uniq_edge(G10_IRB1.label, G10_IRB2.label)
+G10_IRA.g.add_uniq_edge(G10_IRB2.label, G10_IRB1.label)
+G10_IRA.g.add_uniq_edge(G10_IRB2.label, G10_IRB3.label)
+
+G10_IRA.blocs = {irb.label : irb for irb in [G10_IRB0, G10_IRB1,
+                                             G10_IRB2, G10_IRB3]}
+
+# Expected output for graph 10
+G10_EXP_IRA = IRATest()
+
+G10_EXP_IRB0 = gen_irbloc(LBL0, [[]])
+G10_EXP_IRB1 = gen_irbloc(LBL1, [[]])
+G10_EXP_IRB2 = gen_irbloc(LBL2, [[]])
+G10_EXP_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST1)]])
+
+G10_EXP_IRA.blocs = {irb.label : irb for irb in [G10_EXP_IRB0, G10_EXP_IRB1,
+                                                 G10_EXP_IRB2, G10_EXP_IRB3]}
+
+# graph 11 : If/Else conditions with alive variables
+
+G11_IRA = IRATest()
+
+G11_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, b)]])
+G11_IRB1 = gen_irbloc(LBL1, [[ExprAff(b, a)]])
+G11_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+G11_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, a+CST1)]])
+G11_IRB4 = gen_irbloc(LBL4, [[ExprAff(b, b+CST1)]])
+
+
+G11_IRA.gen_graph()
+
+G11_IRA.g.add_uniq_edge(G11_IRB0.label, G11_IRB1.label)
+#G11_IRA.g.add_uniq_edge(G11_IRB3.label, G11_IRB1.label)
+G11_IRA.g.add_uniq_edge(G11_IRB1.label, G11_IRB0.label)
+#G11_IRA.g.add_uniq_edge(G11_IRB4.label, G11_IRB0.label)
+G11_IRA.g.add_uniq_edge(G11_IRB1.label, G11_IRB2.label)
+
+G11_IRA.blocs = {irb.label : irb for irb in [G11_IRB0, G11_IRB1, G11_IRB2]}
+
+# Expected output for graph 11
+G11_EXP_IRA = IRATest()
+
+G11_EXP_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, b)]])
+G11_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(b, a)]])
+G11_EXP_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)]])
+#G11_EXP_IRB3 = gen_irbloc(LBL3, [[ExprAff(a, a+CST1)]])
+#G11_EXP_IRB4 = gen_irbloc(LBL4, [[ExprAff(b, b+CST1)]])
+
+G11_EXP_IRA.blocs = {irb.label : irb for irb in [G11_EXP_IRB0, G11_EXP_IRB1,
+                                                 G11_EXP_IRB2]}
+
+# graph 12 : Graph with multiple out points and useless definitions
+# of return register
+
+G12_IRA = IRATest()
+
+G12_IRB0 = gen_irbloc(LBL0, [[ExprAff(r, CST1)], [ExprAff(a, CST2)]])
+G12_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, CST2)]])
+G12_IRB2 = gen_irbloc(LBL2, [[ExprAff(r, a)], [ExprAff(b, CST3)]])
+G12_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST3)]])
+G12_IRB4 = gen_irbloc(LBL4, [[ExprAff(r, CST2)]])
+G12_IRB5 = gen_irbloc(LBL5, [[ExprAff(r, b)]])
+
+G12_IRA.gen_graph()
+
+G12_IRA.g.add_uniq_edge(G12_IRB0.label, G12_IRB1.label)
+G12_IRA.g.add_uniq_edge(G12_IRB0.label, G12_IRB2.label)
+G12_IRA.g.add_uniq_edge(G12_IRB2.label, G12_IRB3.label)
+G12_IRA.g.add_uniq_edge(G12_IRB2.label, G12_IRB4.label)
+G12_IRA.g.add_uniq_edge(G12_IRB4.label, G12_IRB5.label)
+
+G12_IRA.blocs = {irb.label : irb for irb in [G12_IRB0, G12_IRB1, G12_IRB2,
+                                             G12_IRB3, G12_IRB4, G12_IRB5]}
+
+# Expected output for graph 12
+G12_EXP_IRA = IRATest()
+
+G12_EXP_IRB0 = gen_irbloc(LBL0, [[], []])
+G12_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, CST2)]])
+G12_EXP_IRB2 = gen_irbloc(LBL2, [[], [ExprAff(b, CST3)]])
+G12_EXP_IRB3 = gen_irbloc(LBL3, [[ExprAff(r, CST3)]])
+G12_EXP_IRB4 = gen_irbloc(LBL4, [[]])
+G12_EXP_IRB5 = gen_irbloc(LBL5, [[ExprAff(r, b)]])
+
+
+G12_EXP_IRA.blocs = {irb.label : irb for irb in [G12_EXP_IRB0, G12_EXP_IRB1,
+                                                 G12_EXP_IRB2, G12_EXP_IRB3,
+                                                 G12_EXP_IRB4, G12_EXP_IRB5]}
+
+# graph 13 : Graph where a leaf has lost its son
+
+G13_IRA = IRATest()
+
+G13_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]])
+G13_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, b)]])
+G13_IRB2 = gen_irbloc(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1),
+                                                   ExprAff(c, a+b)]])
+G13_IRB3 = gen_irbloc(LBL3, [[]]) # lost son
+G13_IRB4 = gen_irbloc(LBL4, [[ExprAff(b, CST2)]])
+
+G13_IRA.gen_graph()
+
+G13_IRA.g.add_uniq_edge(G13_IRB0.label, G13_IRB1.label)
+G13_IRA.g.add_uniq_edge(G13_IRB0.label, G13_IRB4.label)
+G13_IRA.g.add_uniq_edge(G13_IRB2.label, G13_IRB3.label)
+G13_IRA.g.add_uniq_edge(G13_IRB4.label, G13_IRB2.label)
+
+G13_IRA.blocs = {irb.label : irb for irb in [G13_IRB0, G13_IRB1, G13_IRB2,
+                                             G13_IRB4]}
+
+# Expected output for graph 13
+G13_EXP_IRA = IRATest()
+
+G13_EXP_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]])
+G13_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, b)]])
+G13_EXP_IRB2 = gen_irbloc(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1),
+                                                      ExprAff(c, a+b)]])
+G13_EXP_IRB3 = gen_irbloc(LBL3, [[]])
+G13_EXP_IRB4 = gen_irbloc(LBL4, [[ExprAff(b, CST2)]])
+
+G13_EXP_IRA.blocs = {irb.label: irb for irb in [G13_EXP_IRB0, G13_EXP_IRB1,
+                                                G13_EXP_IRB2, G13_EXP_IRB4]}
+
+#G13_EXP_IRA = G13_IRA
+
+# graph 14 : Graph where variable assigned multiple times in a block but still
+# useful in the end
+
+G14_IRA = IRATest()
+
+G14_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(c, a)],
+                             [ExprAff(a, CST2)]])
+G14_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a+c)]])
+
+G14_IRA.gen_graph()
+
+G14_IRA.g.add_uniq_edge(G14_IRB0.label, G14_IRB1.label)
+
+G14_IRA.blocs = {irb.label : irb for irb in [G14_IRB0, G14_IRB1]}
+
+# Expected output for graph 1
+G14_EXP_IRA = IRATest()
+
+G14_EXP_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1)], [ExprAff(c, a)],
+                                 [ExprAff(a, CST2)]])
+G14_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a+c)]])
+
+G14_EXP_IRA.blocs = {irb.label: irb for irb in [G14_EXP_IRB0, G14_EXP_IRB1]}
+
+# graph 15 : Graph where variable assigned multiple and read at the same time,
+# but useless
+
+G15_IRA = IRATest()
+
+G15_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST2)], [ExprAff(a, CST1),
+                                                  ExprAff(b, a+CST2),
+                                                  ExprAff(c, CST1)]])
+G15_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a)]])
+
+G15_IRA.gen_graph()
+
+G15_IRA.g.add_uniq_edge(G15_IRB0.label, G15_IRB1.label)
+
+G15_IRA.blocs = {irb.label : irb for irb in [G15_IRB0, G15_IRB1]}
+
+# Expected output for graph 1
+G15_EXP_IRA = IRATest()
+
+G15_EXP_IRB0 = gen_irbloc(LBL0, [[], [ExprAff(a, CST1)]])
+G15_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a)]])
+
+G15_EXP_IRA.blocs = {irb.label: irb for irb in [G15_EXP_IRB0, G15_EXP_IRB1]}
+
+# graph 16 : Graph where variable assigned multiple times in the same bloc
+
+G16_IRA = IRATest()
+
+G16_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, CST1), ExprAff(b, CST2),
+                              ExprAff(c, CST3)], [ExprAff(a, c+CST1),
+                              ExprAff(b, c+CST2)]])
+G16_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a+b)], [ExprAff(r, c+r)]])
+G16_IRB2 = gen_irbloc(LBL2, [[]])
+
+G16_IRA.gen_graph()
+
+G16_IRA.g.add_uniq_edge(G16_IRB0.label, G16_IRB1.label)
+G16_IRA.g.add_uniq_edge(G16_IRB1.label, G16_IRB2.label)
+
+G16_IRA.blocs = {irb.label : irb for irb in [G16_IRB0, G16_IRB1]}
+
+# Expected output for graph 1
+G16_EXP_IRA = IRATest()
+
+G16_EXP_IRB0 = gen_irbloc(LBL0, [[ExprAff(c, CST3)], [ExprAff(a, c + CST1),
+                                                      ExprAff(b, c + CST2)]])
+G16_EXP_IRB1 = gen_irbloc(LBL1, [[ExprAff(r, a+b)], [ExprAff(r, c+r)]])
+
+G16_EXP_IRA.blocs = {irb.label: irb for irb in [G16_EXP_IRB0, G16_EXP_IRB1]}
+
+# graph 17 : parallel ir
+
+G17_IRA = IRATest()
+
+G17_IRB0 = gen_irbloc(LBL0, [[ExprAff(a, a*b),
+                               ExprAff(b, c),
+                               ExprAff(c, CST1)],
+
+                              [ExprAff(d, d+ CST2)],
+
+                              [ExprAff(a, CST1),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(ExprMem(d+CST1), a),
+                               ExprAff(a, b),
+                               ExprAff(b, c),
+                               ExprAff(c, CST1)],
+
+                              [ExprAff(a, CST1),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(ExprMem(d+CST2), a),
+                               ExprAff(a, b),
+                               ExprAff(b, c),
+                               ExprAff(c, CST1)],
+
+
+                              [ExprAff(a, CST2),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(a, a+CST1)],
+
+                              [ExprAff(d, a),
+                               ExprAff(a, d)],
+
+                              [ExprAff(d, d+CST1)],
+
+                              [ExprAff(a, CST2),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(a, a+CST2)],
+
+                              [ExprAff(a, CST2),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(a, CST1),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              [ExprAff(ExprMem(d), a+b+c)],
+
+                         ])
+
+G17_IRA.gen_graph()
+
+G17_IRA.blocs = {irb.label : irb for irb in [G17_IRB0]}
+
+G17_IRA.g.add_node(G17_IRB0.label)
+
+# Expected output for graph 17
+G17_EXP_IRA = IRATest()
+
+G17_EXP_IRB0 = gen_irbloc(LBL0, [[],
+
+                              [ExprAff(d, d+ CST2)],
+
+                              [ExprAff(a, CST1)],
+
+                              [ExprAff(ExprMem(d+CST1), a)],
+
+                              [ExprAff(a, CST1)],
+
+                              [ExprAff(ExprMem(d+CST2), a)],
+
+                              [ExprAff(a, CST2)],
+
+                              [ExprAff(a, a+CST1)],
+
+                              [ExprAff(d, a)],
+
+                              [ExprAff(d, d+CST1)],
+
+                              [ExprAff(a, CST2)],
+
+                              [ExprAff(a, a+CST2)],
+
+                              [ExprAff(a, CST2),
+                               ExprAff(b, a)],
+
+                              [ExprAff(a, CST1),
+                               ExprAff(b, a),
+                               ExprAff(c, b)],
+
+                              G17_IRB0.irs[14]
+                            # Trick because a+b+c != ((a+b)+c)
+                         ])
+
+G17_EXP_IRA.blocs = {irb.label : irb for irb in [G17_EXP_IRB0]}
+
+# Begining  of tests
+
+for test_nb, test in enumerate([(G1_IRA, G1_EXP_IRA),
+                          (G2_IRA, G2_EXP_IRA),
+                          (G3_IRA, G3_EXP_IRA),
+                          (G4_IRA, G4_EXP_IRA),
+                          (G5_IRA, G5_EXP_IRA),
+                          (G6_IRA, G6_EXP_IRA),
+                          (G7_IRA, G7_EXP_IRA),
+                          (G8_IRA, G8_EXP_IRA),
+                          (G9_IRA, G9_EXP_IRA),
+                          (G10_IRA, G10_EXP_IRA),
+                          (G11_IRA, G11_EXP_IRA),
+                          (G12_IRA, G12_EXP_IRA),
+                          (G13_IRA, G13_EXP_IRA),
+                          (G14_IRA, G14_EXP_IRA),
+                          (G15_IRA, G15_EXP_IRA),
+                          (G16_IRA, G16_EXP_IRA),
+                          (G17_IRA, G17_EXP_IRA)
+                     ]):
+    # Extract test elements
+    g_ira, g_exp_ira = test
+
+    print "[+] Test", test_nb+1
+
+    # Print initial graph, for debug
+    open("graph_%02d.dot" % (test_nb+1), "w").write(g_ira.graph())
+
+    # Simplify graph
+    g_ira.dead_simp()
+
+    # Print simplified graph, for debug
+    open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ira.graph())
+
+    # Same number of blocks
+    assert len(g_ira.blocs) == len(g_exp_ira.blocs)
+    # Check that each expr in the blocs are the same
+    for lbl, irb in g_ira.blocs.iteritems():
+        exp_irb = g_exp_ira.blocs[lbl]
+        assert len(irb.irs) == len(exp_irb.irs), "(%s)  %d / %d" %(
+            lbl, len(irb.irs), len(exp_irb.irs))
+        for i in xrange(0, len(exp_irb.irs)):
+            assert len(irb.irs[i]) == len(exp_irb.irs[i]), "(%s:%d) %d / %d" %(
+                lbl, i, len(irb.irs[i]), len(exp_irb.irs[i]))
+            for s_instr in xrange(len(irb.irs[i])):
+                assert irb.irs[i][s_instr] == exp_irb.irs[i][s_instr],\
+                    "(%s:%d)  %s / %s" %(
+                        lbl, i, irb.irs[i][s_instr], exp_irb.irs[i][s_instr])
diff --git a/test/test_all.py b/test/test_all.py
index df07aac5..f52856a3 100644
--- a/test/test_all.py
+++ b/test/test_all.py
@@ -117,6 +117,11 @@ for script in ["ir2C.py",
                "symbexec.py",
                ]:
     testset += RegressionTest([script], base_dir="ir")
+testset += RegressionTest(["analysis.py"], base_dir="ir",
+                          products=[fname for fnames in (
+            ["simp_graph_%02d.dot" % test_nb, "graph_%02d.dot" % test_nb]
+            for test_nb in xrange(1, 18))
+                                    for fname in fnames])
 testset += RegressionTest(["z3_ir.py"], base_dir="ir/translators",
                           tags=[TAGS["z3"]])
 ## OS_DEP