IR: Improve dead code elimination

Dead code analysis computed using Ken Kennedy Algorithm

Ref: A survey of data flow analysis techniques, IBM Thomas J. Watson Research Division, 1979

4 files changed, 923 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..b70a09fc
--- /dev/null
+++ b/test/ir/analysis.py
@@ -0,0 +1,680 @@
+from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprMem, ExprOp
+from miasm2.core.asmbloc import asm_label
+from miasm2.ir.analysis import ira
+from miasm2.ir.ir import ir, irbloc
+from miasm2.core.graph import DiGraph
+from pdb import pm
+
+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(lbl, exprs):
+    lines = [None for i in xrange(len(exprs))]
+    irb = irbloc(lbl, exprs, lines)
+    return irb
+
+
+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, attrib):
+        return pc
+
+    def getsp(self, attrib):
+        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, b):
+        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]} #, g11_irb3, g11_irb4]}
+
+# 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]} #, g11_exp_irb3, g11_exp_irb4]}
+
+# graph 12 : Graph with multiple out points and useless definitions of out 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)
+                                 #[ExprAff(ExprMem(ExprId('d', 32), 32), ExprOp('+', ExprOp('+', ExprId('a', 32), ExprId('b', 32)), ExprId('c', 32)))]
+                          ])
+
+g17_exp_ira.blocs = {irb.label : irb for irb in [g17_exp_irb0]}
+
+# Begining  of tests
+
+for i, 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", i+1
+
+    # Print initial graph, for debug
+    open("graph_%02d.dot" % (i+1), "w").write(g_ira.graph())
+
+    # Simplify graph
+    g_ira.dead_simp()
+
+    # Print simplified graph, for debug
+    open("simp_graph_%02d.dot" % (i+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])