path: root/test/analysis/data_flow.py

""" Test cases for dead code elimination"""
from __future__ import print_function

from future.utils import viewitems

from miasm.expression.expression import ExprId, ExprInt, ExprAssign, ExprMem
from miasm.core.locationdb import LocationDB
from miasm.analysis.data_flow import DeadRemoval, ReachingDefinitions, DiGraphDefUse
from miasm.ir.analysis import LifterModelCall
from miasm.ir.ir import IRBlock, AssignBlock

loc_db = LocationDB()

a = ExprId("a", 32)
b = ExprId("b", 32)
c = ExprId("c", 32)
d = ExprId("d", 32)
r = ExprId("r", 32)

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)

CST1 = ExprInt(0x11, 32)
CST2 = ExprInt(0x12, 32)
CST3 = ExprInt(0x13, 32)

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)

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))

    irs.append(AssignBlock({IRDst:dummy}))
    irbl = IRBlock(loc_db, 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 LifterTest(LifterModelCall):

    """Fake Lifter class for tests"""

    def __init__(self, loc_db):
        arch = Arch()
        super(LifterTest, self).__init__(arch, 32, loc_db)
        self.IRDst = IRDst
        self.ret_reg = r

    def get_out_regs(self, _):
        return set([self.ret_reg, self.sp])

Lifter = LifterTest(loc_db)
deadrm = DeadRemoval(Lifter)

# graph 1 : Simple graph with dead and alive variables

G1_cfg = Lifter.new_ircfg()

G1_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G1_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, b)]])
G1_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])

for irb in [G1_IRB0, G1_IRB1, G1_IRB2]:
    G1_cfg.add_irblock(irb)

G1_cfg.add_uniq_edge(G1_IRB0.loc_key, G1_IRB1.loc_key)
G1_cfg.add_uniq_edge(G1_IRB1.loc_key, G1_IRB2.loc_key)

# Expected output for graph 1
G1_EXP_cfg = Lifter.new_ircfg()

G1_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(b, CST2)]])
G1_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, b)]])
G1_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])

for irb in [G1_EXP_IRB0, G1_EXP_IRB1, G1_EXP_IRB2]:
    G1_EXP_cfg.add_irblock(irb)

# graph 2 : Natural loop with dead variable

G2_cfg = Lifter.new_ircfg()

G2_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(r, CST1)]])
G2_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G2_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, r)]])

for irb in [G2_IRB0, G2_IRB1, G2_IRB2]:
    G2_cfg.add_irblock(irb)

G2_cfg.add_uniq_edge(G2_IRB0.loc_key, G2_IRB1.loc_key)
G2_cfg.add_uniq_edge(G2_IRB1.loc_key, G2_IRB2.loc_key)
G2_cfg.add_uniq_edge(G2_IRB1.loc_key, G2_IRB1.loc_key)

# Expected output for graph 2
G2_EXP_cfg = Lifter.new_ircfg()

G2_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(r, CST1)]])
G2_EXP_IRB1 = gen_irblock(LBL1, [[]])
G2_EXP_IRB2 = gen_irblock(LBL2, [[]])

for irb in [G2_EXP_IRB0, G2_EXP_IRB1, G2_EXP_IRB2]:
    G2_EXP_cfg.add_irblock(irb)

# graph 3 : Natural loop with alive variables

G3_cfg = Lifter.new_ircfg()

G3_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G3_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G3_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])

for irb in [G3_IRB0, G3_IRB1, G3_IRB2]:
    G3_cfg.add_irblock(irb)

G3_cfg.add_uniq_edge(G3_IRB0.loc_key, G3_IRB1.loc_key)
G3_cfg.add_uniq_edge(G3_IRB1.loc_key, G3_IRB2.loc_key)
G3_cfg.add_uniq_edge(G3_IRB1.loc_key, G3_IRB1.loc_key)

# Expected output for graph 3
G3_EXP_cfg = Lifter.new_ircfg()

G3_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G3_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G3_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])

for irb in [G3_EXP_IRB0, G3_EXP_IRB1, G3_EXP_IRB2]:
    G3_EXP_cfg.add_irblock(irb)

# graph 4 : If/else with dead variables

G4_cfg = Lifter.new_ircfg()

G4_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G4_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G4_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G4_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, CST3)], [ExprAssign(r, a)]])

for irb in [G4_IRB0, G4_IRB1, G4_IRB2, G4_IRB3]:
    G4_cfg.add_irblock(irb)

G4_cfg.add_uniq_edge(G4_IRB0.loc_key, G4_IRB1.loc_key)
G4_cfg.add_uniq_edge(G4_IRB0.loc_key, G4_IRB2.loc_key)
G4_cfg.add_uniq_edge(G4_IRB1.loc_key, G4_IRB3.loc_key)
G4_cfg.add_uniq_edge(G4_IRB2.loc_key, G4_IRB3.loc_key)

# Expected output for graph 4
G4_EXP_cfg = Lifter.new_ircfg()

G4_EXP_IRB0 = gen_irblock(LBL0, [[]])
G4_EXP_IRB1 = gen_irblock(LBL1, [[]])
G4_EXP_IRB2 = gen_irblock(LBL2, [[]])
G4_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, CST3)], [ExprAssign(r, a)]])

for irb in [G4_EXP_IRB0, G4_EXP_IRB1, G4_EXP_IRB2, G4_EXP_IRB3]:
    G4_EXP_cfg.add_irblock(irb)

# graph 5 : Loop and If/else with dead variables

G5_cfg = Lifter.new_ircfg()

G5_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G5_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G5_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G5_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST3)]])
G5_IRB4 = gen_irblock(LBL4, [[ExprAssign(a, a+CST1)]])
G5_IRB5 = gen_irblock(LBL5, [[ExprAssign(a, r)]])

for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3, G5_IRB4, G5_IRB5]:
    G5_cfg.add_irblock(irb)

G5_cfg.add_uniq_edge(G5_IRB0.loc_key, G5_IRB1.loc_key)
G5_cfg.add_uniq_edge(G5_IRB1.loc_key, G5_IRB2.loc_key)
G5_cfg.add_uniq_edge(G5_IRB1.loc_key, G5_IRB3.loc_key)
G5_cfg.add_uniq_edge(G5_IRB2.loc_key, G5_IRB4.loc_key)
G5_cfg.add_uniq_edge(G5_IRB3.loc_key, G5_IRB4.loc_key)
G5_cfg.add_uniq_edge(G5_IRB4.loc_key, G5_IRB5.loc_key)
G5_cfg.add_uniq_edge(G5_IRB4.loc_key, G5_IRB1.loc_key)

# Expected output for graph 5
G5_EXP_cfg = Lifter.new_ircfg()

G5_EXP_IRB0 = gen_irblock(LBL0, [[]])
G5_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G5_EXP_IRB2 = gen_irblock(LBL2, [[]])
G5_EXP_IRB3 = gen_irblock(LBL3, [[]])
G5_EXP_IRB4 = gen_irblock(LBL4, [[]])
G5_EXP_IRB5 = gen_irblock(LBL5, [[]])

for irb in [G5_EXP_IRB0, G5_EXP_IRB1, G5_EXP_IRB2,
            G5_EXP_IRB3, G5_EXP_IRB4, G5_EXP_IRB5]:
    G5_EXP_cfg.add_irblock(irb)

# graph 6 : Natural loop with dead variables symmetric assignment
# (a = b <-> b = a )

G6_cfg = Lifter.new_ircfg()

G6_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G6_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G6_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, b)]])
G6_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST2)]])

for irb in [G6_IRB0, G6_IRB1, G6_IRB2, G6_IRB3]:
    G6_cfg.add_irblock(irb)

G6_cfg.add_uniq_edge(G6_IRB0.loc_key, G6_IRB1.loc_key)
G6_cfg.add_uniq_edge(G6_IRB1.loc_key, G6_IRB2.loc_key)
G6_cfg.add_uniq_edge(G6_IRB2.loc_key, G6_IRB1.loc_key)
G6_cfg.add_uniq_edge(G6_IRB2.loc_key, G6_IRB3.loc_key)

# Expected output for graph 6
G6_EXP_cfg = Lifter.new_ircfg()

G6_EXP_IRB0 = gen_irblock(LBL0, [[]])
G6_EXP_IRB1 = gen_irblock(LBL1, [[]])
G6_EXP_IRB2 = gen_irblock(LBL2, [[]])
G6_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST2)]])

for irb in [G6_EXP_IRB0, G6_EXP_IRB1, G6_EXP_IRB2, G6_EXP_IRB3]:
    G6_EXP_cfg.add_irblock(irb)

# graph 7 : Double entry loop with dead variables

G7_cfg = Lifter.new_ircfg()

G7_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(r, CST1)]])
G7_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G7_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G7_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, r)]])

for irb in [G7_IRB0, G7_IRB1, G7_IRB2, G7_IRB3]:
    G7_cfg.add_irblock(irb)

G7_cfg.add_uniq_edge(G7_IRB0.loc_key, G7_IRB1.loc_key)
G7_cfg.add_uniq_edge(G7_IRB1.loc_key, G7_IRB2.loc_key)
G7_cfg.add_uniq_edge(G7_IRB2.loc_key, G7_IRB1.loc_key)
G7_cfg.add_uniq_edge(G7_IRB2.loc_key, G7_IRB3.loc_key)
G7_cfg.add_uniq_edge(G7_IRB0.loc_key, G7_IRB2.loc_key)


# Expected output for graph 7
G7_EXP_cfg = Lifter.new_ircfg()

G7_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(r, CST1)]])
G7_EXP_IRB1 = gen_irblock(LBL1, [[]])
G7_EXP_IRB2 = gen_irblock(LBL2, [[]])
G7_EXP_IRB3 = gen_irblock(LBL3, [[]])

for irb in [G7_EXP_IRB0, G7_EXP_IRB1, G7_EXP_IRB2, G7_EXP_IRB3]:
    G7_EXP_cfg.add_irblock(irb)

# graph 8 : Nested loops with dead variables

G8_cfg = Lifter.new_ircfg()

G8_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST1)]])
G8_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G8_IRB2 = gen_irblock(LBL2, [[ExprAssign(b, b+CST2)]])
G8_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, b)]])


for irb in [G8_IRB0, G8_IRB1, G8_IRB2, G8_IRB3]:
    G8_cfg.add_irblock(irb)

G8_cfg.add_uniq_edge(G8_IRB0.loc_key, G8_IRB1.loc_key)
G8_cfg.add_uniq_edge(G8_IRB1.loc_key, G8_IRB2.loc_key)
G8_cfg.add_uniq_edge(G8_IRB2.loc_key, G8_IRB1.loc_key)
G8_cfg.add_uniq_edge(G8_IRB2.loc_key, G8_IRB3.loc_key)
G8_cfg.add_uniq_edge(G8_IRB3.loc_key, G8_IRB2.loc_key)


# Expected output for graph 8

G8_EXP_cfg = Lifter.new_ircfg()

G8_EXP_IRB0 = gen_irblock(LBL0, [[], []])
G8_EXP_IRB1 = gen_irblock(LBL1, [[]])
G8_EXP_IRB2 = gen_irblock(LBL2, [[]])
G8_EXP_IRB3 = gen_irblock(LBL3, [[]])

for irb in [G8_EXP_IRB0, G8_EXP_IRB1, G8_EXP_IRB2, G8_EXP_IRB3]:
    G8_EXP_cfg.add_irblock(irb)

# graph 9 : Miultiple-exits loops with dead variables

G9_cfg = Lifter.new_ircfg()

G9_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST1)]])
G9_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)], [ExprAssign(b, b+CST1)]])
G9_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)], [ExprAssign(b, b+CST2)]])
G9_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, b)]])
G9_IRB4 = gen_irblock(LBL4, [[ExprAssign(r, a)], [ExprAssign(r, b)]])

for irb in [G9_IRB0, G9_IRB1, G9_IRB2, G9_IRB3, G9_IRB4]:
    G9_cfg.add_irblock(irb)

G9_cfg.add_uniq_edge(G9_IRB0.loc_key, G9_IRB4.loc_key)
G9_cfg.add_uniq_edge(G9_IRB0.loc_key, G9_IRB1.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB0.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB4.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB2.loc_key)
G9_cfg.add_uniq_edge(G9_IRB2.loc_key, G9_IRB0.loc_key)
G9_cfg.add_uniq_edge(G9_IRB2.loc_key, G9_IRB3.loc_key)
G9_cfg.add_uniq_edge(G9_IRB3.loc_key, G9_IRB4.loc_key)


# Expected output for graph 9

G9_EXP_cfg = Lifter.new_ircfg()

G9_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(b, CST1)]])
G9_EXP_IRB1 = gen_irblock(LBL1, [[], [ExprAssign(b, b+CST1)]])
G9_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAssign(b, b+CST2)]])
G9_EXP_IRB3 = gen_irblock(LBL3, [[]])
G9_EXP_IRB4 = gen_irblock(LBL4, [[], [ExprAssign(r, b)]])

for irb in [G9_EXP_IRB0, G9_EXP_IRB1, G9_EXP_IRB2, G9_EXP_IRB3, G9_EXP_IRB4]:
    G9_EXP_cfg.add_irblock(irb)

# graph 10 : Natural loop with alive variables symmetric assignment
# (a = b <-> b = a )

G10_cfg = Lifter.new_ircfg()

G10_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G10_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G10_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, b)]])
G10_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST1)]])

for irb in [G10_IRB0, G10_IRB1, G10_IRB2, G10_IRB3]:
    G10_cfg.add_irblock(irb)


G10_cfg.add_uniq_edge(G10_IRB0.loc_key, G10_IRB1.loc_key)
G10_cfg.add_uniq_edge(G10_IRB1.loc_key, G10_IRB2.loc_key)
G10_cfg.add_uniq_edge(G10_IRB2.loc_key, G10_IRB1.loc_key)
G10_cfg.add_uniq_edge(G10_IRB2.loc_key, G10_IRB3.loc_key)

# Expected output for graph 10
G10_EXP_cfg = Lifter.new_ircfg()

G10_EXP_IRB0 = gen_irblock(LBL0, [[]])
G10_EXP_IRB1 = gen_irblock(LBL1, [[]])
G10_EXP_IRB2 = gen_irblock(LBL2, [[]])
G10_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST1)]])

for irb in [G10_EXP_IRB0, G10_EXP_IRB1, G10_EXP_IRB2, G10_EXP_IRB3]:
    G10_EXP_cfg.add_irblock(irb)

# graph 11 : If/Else conditions with alive variables

G11_cfg = Lifter.new_ircfg()

G11_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, b)]])
G11_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G11_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
G11_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST1)]])
G11_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, b+CST1)]])


for irb in [G11_IRB0, G11_IRB1, G11_IRB2]:
    G11_cfg.add_irblock(irb)

G11_cfg.add_uniq_edge(G11_IRB0.loc_key, G11_IRB1.loc_key)
#G11_cfg.add_uniq_edge(G11_IRB3.loc_key, G11_IRB1.loc_key)
G11_cfg.add_uniq_edge(G11_IRB1.loc_key, G11_IRB0.loc_key)
#G11_cfg.add_uniq_edge(G11_IRB4.loc_key, G11_IRB0.loc_key)
G11_cfg.add_uniq_edge(G11_IRB1.loc_key, G11_IRB2.loc_key)


# Expected output for graph 11
G11_EXP_cfg = Lifter.new_ircfg()

G11_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, b)]])
G11_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G11_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
#G11_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST1)]])
#G11_EXP_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, b+CST1)]])

for irb in [G11_EXP_IRB0, G11_EXP_IRB1,
            G11_EXP_IRB2]:
    G11_EXP_cfg.add_irblock(irb)

# graph 12 : Graph with multiple out points and useless definitions
# of return register

G12_cfg = Lifter.new_ircfg()

G12_IRB0 = gen_irblock(LBL0, [[ExprAssign(r, CST1)], [ExprAssign(a, CST2)]])
G12_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G12_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)], [ExprAssign(b, CST3)]])
G12_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST3)]])
G12_IRB4 = gen_irblock(LBL4, [[ExprAssign(r, CST2)]])
G12_IRB5 = gen_irblock(LBL5, [[ExprAssign(r, b)]])

for irb in [G12_IRB0, G12_IRB1, G12_IRB2, G12_IRB3, G12_IRB4, G12_IRB5]:
    G12_cfg.add_irblock(irb)

G12_cfg.add_uniq_edge(G12_IRB0.loc_key, G12_IRB1.loc_key)
G12_cfg.add_uniq_edge(G12_IRB0.loc_key, G12_IRB2.loc_key)
G12_cfg.add_uniq_edge(G12_IRB2.loc_key, G12_IRB3.loc_key)
G12_cfg.add_uniq_edge(G12_IRB2.loc_key, G12_IRB4.loc_key)
G12_cfg.add_uniq_edge(G12_IRB4.loc_key, G12_IRB5.loc_key)

# Expected output for graph 12
G12_EXP_cfg = Lifter.new_ircfg()

G12_EXP_IRB0 = gen_irblock(LBL0, [[], []])
G12_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G12_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAssign(b, CST3)]])
G12_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST3)]])
G12_EXP_IRB4 = gen_irblock(LBL4, [[]])
G12_EXP_IRB5 = gen_irblock(LBL5, [[ExprAssign(r, b)]])


for irb in [G12_EXP_IRB0, G12_EXP_IRB1,
            G12_EXP_IRB2, G12_EXP_IRB3,
            G12_EXP_IRB4, G12_EXP_IRB5]:
    G12_EXP_cfg.add_irblock(irb)

# graph 13 : Graph where a leaf has lost its son

G13_cfg = Lifter.new_ircfg()

G13_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G13_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, b)]])
G13_IRB2 = gen_irblock(LBL2, [[ExprAssign(d, CST2)], [ExprAssign(a, b+CST1),
                                                   ExprAssign(c, a+b)]])
G13_IRB3 = gen_irblock(LBL3, [[]]) # lost son
G13_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, CST2)]])

for irb in [G13_IRB0, G13_IRB1, G13_IRB2, G13_IRB4]:
    G13_cfg.add_irblock(irb)

G13_cfg.add_uniq_edge(G13_IRB0.loc_key, G13_IRB1.loc_key)
G13_cfg.add_uniq_edge(G13_IRB0.loc_key, G13_IRB4.loc_key)
G13_cfg.add_uniq_edge(G13_IRB2.loc_key, G13_IRB3.loc_key)
G13_cfg.add_uniq_edge(G13_IRB4.loc_key, G13_IRB2.loc_key)

# Expected output for graph 13
G13_EXP_cfg = Lifter.new_ircfg()

G13_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G13_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, b)]])
G13_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(d, CST2)], [ExprAssign(a, b+CST1),
                                                       ExprAssign(c, a+b)]])
G13_EXP_IRB3 = gen_irblock(LBL3, [[]])
G13_EXP_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, CST2)]])

for irb in [G13_EXP_IRB0, G13_EXP_IRB1, G13_EXP_IRB2, G13_EXP_IRB4]:
    G13_EXP_cfg.add_irblock(irb)

#G13_EXP_cfg = G13_cfg

# graph 14 : Graph where variable assigned multiple times in a block but still
# useful in the end

G14_cfg = Lifter.new_ircfg()

G14_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(c, a)],
                              [ExprAssign(a, CST2)]])
G14_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+c)]])

for irb in [G14_IRB0, G14_IRB1]:
    G14_cfg.add_irblock(irb)

G14_cfg.add_uniq_edge(G14_IRB0.loc_key, G14_IRB1.loc_key)

# Expected output for graph 1
G14_EXP_cfg = Lifter.new_ircfg()

G14_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(c, a)],
                                  [ExprAssign(a, CST2)]])
G14_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+c)]])

for irb in [G14_EXP_IRB0, G14_EXP_IRB1]:
    G14_EXP_cfg.add_irblock(irb)

# graph 15 : Graph where variable assigned multiple and read at the same time,
# but useless

G15_cfg = Lifter.new_ircfg()

G15_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST2)], [ExprAssign(a, CST1),
                                                   ExprAssign(b, a+CST2),
                                                   ExprAssign(c, CST1)]])
G15_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a)]])

for irb in [G15_IRB0, G15_IRB1]:
    G15_cfg.add_irblock(irb)

G15_cfg.add_uniq_edge(G15_IRB0.loc_key, G15_IRB1.loc_key)

# Expected output for graph 1
G15_EXP_cfg = Lifter.new_ircfg()

G15_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(a, CST1)]])
G15_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a)]])

for irb in [G15_EXP_IRB0, G15_EXP_IRB1]:
    G15_EXP_cfg.add_irblock(irb)

# graph 16 : Graph where variable assigned multiple times in the same block

G16_cfg = Lifter.new_ircfg()

G16_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1), ExprAssign(b, CST2),
                               ExprAssign(c, CST3)], [ExprAssign(a, c+CST1),
                                                   ExprAssign(b, c+CST2)]])
G16_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+b)], [ExprAssign(r, c+r)]])
G16_IRB2 = gen_irblock(LBL2, [[]])

for irb in [G16_IRB0, G16_IRB1]:
    G16_cfg.add_irblock(irb)

G16_cfg.add_uniq_edge(G16_IRB0.loc_key, G16_IRB1.loc_key)
G16_cfg.add_uniq_edge(G16_IRB1.loc_key, G16_IRB2.loc_key)

for irb in [G16_IRB0, G16_IRB1]:
    G16_cfg.add_irblock(irb)

# Expected output for graph 1
G16_EXP_cfg = Lifter.new_ircfg()

G16_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(c, CST3)], [ExprAssign(a, c + CST1),
                                                       ExprAssign(b, c + CST2)]])
G16_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+b)], [ExprAssign(r, c+r)]])

for irb in [G16_EXP_IRB0, G16_EXP_IRB1]:
    G16_EXP_cfg.add_irblock(irb)

# graph 17 : parallel ir

G17_cfg = Lifter.new_ircfg()

G17_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, a*b),
                               ExprAssign(b, c),
                               ExprAssign(c, CST1)],

                              [ExprAssign(d, d+ CST2)],

                              [ExprAssign(a, CST1),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(ExprMem(d+CST1, 32), a),
                               ExprAssign(a, b),
                               ExprAssign(b, c),
                               ExprAssign(c, CST1)],

                              [ExprAssign(a, CST1),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(ExprMem(d+CST2, 32), a),
                               ExprAssign(a, b),
                               ExprAssign(b, c),
                               ExprAssign(c, CST1)],


                              [ExprAssign(a, CST2),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(a, a+CST1)],

                              [ExprAssign(d, a),
                               ExprAssign(a, d)],

                              [ExprAssign(d, d+CST1)],

                              [ExprAssign(a, CST2),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(a, a+CST2)],

                              [ExprAssign(a, CST2),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(a, CST1),
                               ExprAssign(b, a),
                               ExprAssign(c, b)],

                              [ExprAssign(ExprMem(d, 32), a+b+c)],

                         ])

for irb in [G17_IRB0]:
    G17_cfg.add_irblock(irb)

#G17_cfg.graph.add_node(G17_IRB0.loc_key)

# Expected output for graph 17
G17_EXP_cfg = Lifter.new_ircfg()

G17_EXP_IRB0 = gen_irblock(LBL0, [[],

                                  [ExprAssign(d, d+ CST2)],

                                  [ExprAssign(a, CST1)],

                                  [ExprAssign(ExprMem(d+CST1, 32), a)],

                                  [ExprAssign(a, CST1)],

                                  [ExprAssign(ExprMem(d+CST2, 32), a)],

                                  [ExprAssign(a, CST2)],

                                  [ExprAssign(a, a+CST1)],

                                  [ExprAssign(d, a)],

                                  [ExprAssign(d, d+CST1)],

                                  [ExprAssign(a, CST2)],

                                  [ExprAssign(a, a+CST2)],

                                  [ExprAssign(a, CST2),
                                   ExprAssign(b, a)],

                                  [ExprAssign(a, CST1),
                                   ExprAssign(b, a),
                                   ExprAssign(c, b)],

                                  G17_IRB0[14]
                                  # Trick because a+b+c != ((a+b)+c)
                                 ])

for irb in [G17_EXP_IRB0]:
    G17_EXP_cfg.add_irblock(irb)

# Beginning  of tests

for test_nb, test in enumerate([(G1_cfg, G1_EXP_cfg),
                                (G2_cfg, G2_EXP_cfg),
                                (G3_cfg, G3_EXP_cfg),
                                (G4_cfg, G4_EXP_cfg),
                                (G5_cfg, G5_EXP_cfg),
                                (G6_cfg, G6_EXP_cfg),
                                (G7_cfg, G7_EXP_cfg),
                                (G8_cfg, G8_EXP_cfg),
                                (G9_cfg, G9_EXP_cfg),
                                (G10_cfg, G10_EXP_cfg),
                                (G11_cfg, G11_EXP_cfg),
                                (G12_cfg, G12_EXP_cfg),
                                (G13_cfg, G13_EXP_cfg),
                                (G14_cfg, G14_EXP_cfg),
                                (G15_cfg, G15_EXP_cfg),
                                (G16_cfg, G16_EXP_cfg),
                                (G17_cfg, G17_EXP_cfg)
]):
    # Extract test elements
    g_ircfg, g_exp_ircfg = test

    print("[+] Test", test_nb+1)

    # Print initial graph, for debug
    open("graph_%02d.dot" % (test_nb+1), "w").write(g_ircfg.dot())

    reaching_defs = ReachingDefinitions(g_ircfg)
    defuse = DiGraphDefUse(reaching_defs, deref_mem=True)

    # # Simplify graph
    deadrm(g_ircfg)

    # # Print simplified graph, for debug
    open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ircfg.dot())

    # Same number of blocks
    assert len(g_ircfg.blocks) == len(g_exp_ircfg.blocks)
    # Check that each expr in the blocks are the same
    for lbl, irb in viewitems(g_ircfg.blocks):
        exp_irb = g_exp_ircfg.blocks[lbl]
        assert exp_irb.assignblks == irb.assignblks