diff options
Diffstat (limited to 'test/analysis/data_flow.py')
| -rw-r--r-- | test/analysis/data_flow.py | 685 |
1 files changed, 685 insertions, 0 deletions
diff --git a/test/analysis/data_flow.py b/test/analysis/data_flow.py new file mode 100644 index 00000000..a40d000a --- /dev/null +++ b/test/analysis/data_flow.py @@ -0,0 +1,685 @@ +""" Test cases for dead code elimination""" +from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprMem +from miasm2.core.asmblock import AsmLabel +from miasm2.analysis.data_flow import * +from miasm2.ir.analysis import ira +from miasm2.ir.ir import IRBlock, AssignBlock + +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 = AsmLabel("lbl0") +LBL1 = AsmLabel("lbl1") +LBL2 = AsmLabel("lbl2") +LBL3 = AsmLabel("lbl3") +LBL4 = AsmLabel("lbl4") +LBL5 = AsmLabel("lbl5") +LBL6 = AsmLabel("lbl6") + + + +def gen_irblock(label, exprs_list): + lines = [None for _ in xrange(len(exprs_list))] + irs = [] + for exprs in exprs_list: + if isinstance(exprs, AssignBlock): + irs.append(exprs) + else: + irs.append(AssignBlock(exprs)) + + irbl = IRBlock(label, irs, 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(ira): + + """Fake IRA class for tests""" + + def __init__(self, symbol_pool=None): + arch = Arch() + super(IRATest, self).__init__(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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]]) +G1_IRB1 = gen_irblock(LBL1, [[ExprAff(a, b)]]) +G1_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) + +G1_IRA.blocks = {irb.label : irb for irb in [G1_IRB0, G1_IRB1, G1_IRB2]} + +G1_IRA.graph.add_uniq_edge(G1_IRB0.label, G1_IRB1.label) +G1_IRA.graph.add_uniq_edge(G1_IRB1.label, G1_IRB2.label) + +# Expected output for graph 1 +G1_EXP_IRA = IRATest() + +G1_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(b, CST2)]]) +G1_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(a, b)]]) +G1_EXP_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) + +G1_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(r, CST1)]]) +G2_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G2_IRB2 = gen_irblock(LBL2, [[ExprAff(a, r)]]) + +G2_IRA.blocks = {irb.label : irb for irb in [G2_IRB0, G2_IRB1, G2_IRB2]} + +G2_IRA.graph.add_uniq_edge(G2_IRB0.label, G2_IRB1.label) +G2_IRA.graph.add_uniq_edge(G2_IRB1.label, G2_IRB2.label) +G2_IRA.graph.add_uniq_edge(G2_IRB1.label, G2_IRB1.label) + +# Expected output for graph 2 +G2_EXP_IRA = IRATest() + +G2_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(r, CST1)]]) +G2_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G2_EXP_IRB2 = gen_irblock(LBL2, [[]]) + +G2_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)]]) +G3_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G3_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) + +G3_IRA.blocks = {irb.label : irb for irb in [G3_IRB0, G3_IRB1, G3_IRB2]} + +G3_IRA.graph.add_uniq_edge(G3_IRB0.label, G3_IRB1.label) +G3_IRA.graph.add_uniq_edge(G3_IRB1.label, G3_IRB2.label) +G3_IRA.graph.add_uniq_edge(G3_IRB1.label, G3_IRB1.label) + +# Expected output for graph 3 +G3_EXP_IRA = IRATest() + +G3_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)]]) +G3_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G3_EXP_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) + +G3_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)]]) +G4_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G4_IRB2 = gen_irblock(LBL2, [[ExprAff(a, a+CST2)]]) +G4_IRB3 = gen_irblock(LBL3, [[ExprAff(a, CST3)], [ExprAff(r, a)]]) + +G4_IRA.blocks = {irb.label : irb for irb in [G4_IRB0, G4_IRB1, G4_IRB2, + G4_IRB3]} + +G4_IRA.graph.add_uniq_edge(G4_IRB0.label, G4_IRB1.label) +G4_IRA.graph.add_uniq_edge(G4_IRB0.label, G4_IRB2.label) +G4_IRA.graph.add_uniq_edge(G4_IRB1.label, G4_IRB3.label) +G4_IRA.graph.add_uniq_edge(G4_IRB2.label, G4_IRB3.label) + +# Expected output for graph 4 +G4_EXP_IRA = IRATest() + +G4_EXP_IRB0 = gen_irblock(LBL0, [[]]) +G4_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G4_EXP_IRB2 = gen_irblock(LBL2, [[]]) +G4_EXP_IRB3 = gen_irblock(LBL3, [[ExprAff(a, CST3)], [ExprAff(r, a)]]) + +G4_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)]]) +G5_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) +G5_IRB2 = gen_irblock(LBL2, [[ExprAff(a, a+CST2)]]) +G5_IRB3 = gen_irblock(LBL3, [[ExprAff(a, a+CST3)]]) +G5_IRB4 = gen_irblock(LBL4, [[ExprAff(a, a+CST1)]]) +G5_IRB5 = gen_irblock(LBL5, [[ExprAff(a, r)]]) + +G5_IRA.blocks = {irb.label : irb for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3, + G5_IRB4, G5_IRB5]} + +G5_IRA.graph.add_uniq_edge(G5_IRB0.label, G5_IRB1.label) +G5_IRA.graph.add_uniq_edge(G5_IRB1.label, G5_IRB2.label) +G5_IRA.graph.add_uniq_edge(G5_IRB1.label, G5_IRB3.label) +G5_IRA.graph.add_uniq_edge(G5_IRB2.label, G5_IRB4.label) +G5_IRA.graph.add_uniq_edge(G5_IRB3.label, G5_IRB4.label) +G5_IRA.graph.add_uniq_edge(G5_IRB4.label, G5_IRB5.label) +G5_IRA.graph.add_uniq_edge(G5_IRB4.label, G5_IRB1.label) + +# Expected output for graph 5 +G5_EXP_IRA = IRATest() + +G5_EXP_IRB0 = gen_irblock(LBL0, [[]]) +G5_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(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, [[]]) + +G5_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)]]) +G6_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) +G6_IRB2 = gen_irblock(LBL2, [[ExprAff(a, b)]]) +G6_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST2)]]) + +G6_IRA.blocks = {irb.label : irb for irb in [G6_IRB0, G6_IRB1, G6_IRB2, + G6_IRB3]} + +G6_IRA.graph.add_uniq_edge(G6_IRB0.label, G6_IRB1.label) +G6_IRA.graph.add_uniq_edge(G6_IRB1.label, G6_IRB2.label) +G6_IRA.graph.add_uniq_edge(G6_IRB2.label, G6_IRB1.label) +G6_IRA.graph.add_uniq_edge(G6_IRB2.label, G6_IRB3.label) + +# Expected output for graph 6 +G6_EXP_IRA = IRATest() + +G6_EXP_IRB0 = gen_irblock(LBL0, [[]]) +G6_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G6_EXP_IRB2 = gen_irblock(LBL2, [[]]) +G6_EXP_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST2)]]) + +G6_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(r, CST1)]]) +G7_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G7_IRB2 = gen_irblock(LBL2, [[ExprAff(a, a+CST2)]]) +G7_IRB3 = gen_irblock(LBL3, [[ExprAff(a, r)]]) + +G7_IRA.blocks = {irb.label : irb for irb in [G7_IRB0, G7_IRB1, G7_IRB2, + G7_IRB3]} + +G7_IRA.graph.add_uniq_edge(G7_IRB0.label, G7_IRB1.label) +G7_IRA.graph.add_uniq_edge(G7_IRB1.label, G7_IRB2.label) +G7_IRA.graph.add_uniq_edge(G7_IRB2.label, G7_IRB1.label) +G7_IRA.graph.add_uniq_edge(G7_IRB2.label, G7_IRB3.label) +G7_IRA.graph.add_uniq_edge(G7_IRB0.label, G7_IRB2.label) + + +# Expected output for graph 7 +G7_EXP_IRA = IRATest() + +G7_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(r, CST1)]]) +G7_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G7_EXP_IRB2 = gen_irblock(LBL2, [[]]) +G7_EXP_IRB3 = gen_irblock(LBL3, [[]]) + +G7_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]]) +G8_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) +G8_IRB2 = gen_irblock(LBL2, [[ExprAff(b, b+CST2)]]) +G8_IRB3 = gen_irblock(LBL3, [[ExprAff(a, b)]]) + + +G8_IRA.blocks = {irb.label : irb for irb in [G8_IRB0, G8_IRB1, G8_IRB2, + G8_IRB3]} + +G8_IRA.graph.add_uniq_edge(G8_IRB0.label, G8_IRB1.label) +G8_IRA.graph.add_uniq_edge(G8_IRB1.label, G8_IRB2.label) +G8_IRA.graph.add_uniq_edge(G8_IRB2.label, G8_IRB1.label) +G8_IRA.graph.add_uniq_edge(G8_IRB2.label, G8_IRB3.label) +G8_IRA.graph.add_uniq_edge(G8_IRB3.label, G8_IRB2.label) + + +# Expected output for graph 8 + +G8_EXP_IRA = IRATest() + +G8_EXP_IRB0 = gen_irblock(LBL0, [[], []]) +G8_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G8_EXP_IRB2 = gen_irblock(LBL2, [[]]) +G8_EXP_IRB3 = gen_irblock(LBL3, [[]]) + +G8_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]]) +G9_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)], [ExprAff(b, b+CST1)]]) +G9_IRB2 = gen_irblock(LBL2, [[ExprAff(a, a+CST2)], [ExprAff(b, b+CST2)]]) +G9_IRB3 = gen_irblock(LBL3, [[ExprAff(a, b)]]) +G9_IRB4 = gen_irblock(LBL4, [[ExprAff(r, a)], [ExprAff(r, b)]]) + +G9_IRA.blocks = {irb.label : irb for irb in [G9_IRB0, G9_IRB1, G9_IRB2, + G9_IRB3, G9_IRB4]} + +G9_IRA.graph.add_uniq_edge(G9_IRB0.label, G9_IRB4.label) +G9_IRA.graph.add_uniq_edge(G9_IRB0.label, G9_IRB1.label) +G9_IRA.graph.add_uniq_edge(G9_IRB1.label, G9_IRB0.label) +G9_IRA.graph.add_uniq_edge(G9_IRB1.label, G9_IRB4.label) +G9_IRA.graph.add_uniq_edge(G9_IRB1.label, G9_IRB2.label) +G9_IRA.graph.add_uniq_edge(G9_IRB2.label, G9_IRB0.label) +G9_IRA.graph.add_uniq_edge(G9_IRB2.label, G9_IRB3.label) +G9_IRA.graph.add_uniq_edge(G9_IRB3.label, G9_IRB4.label) + + +# Expected output for graph 9 + +G9_EXP_IRA = IRATest() + +G9_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(b, CST1)]]) +G9_EXP_IRB1 = gen_irblock(LBL1, [[], [ExprAff(b, b+CST1)]]) +G9_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAff(b, b+CST2)]]) +G9_EXP_IRB3 = gen_irblock(LBL3, [[]]) +G9_EXP_IRB4 = gen_irblock(LBL4, [[], [ExprAff(r, b)]]) + +G9_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)]]) +G10_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) +G10_IRB2 = gen_irblock(LBL2, [[ExprAff(a, b)]]) +G10_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST1)]]) + +G10_IRA.blocks = {irb.label : irb for irb in [G10_IRB0, G10_IRB1, + G10_IRB2, G10_IRB3]} + +G10_IRA.graph.add_uniq_edge(G10_IRB0.label, G10_IRB1.label) +G10_IRA.graph.add_uniq_edge(G10_IRB1.label, G10_IRB2.label) +G10_IRA.graph.add_uniq_edge(G10_IRB2.label, G10_IRB1.label) +G10_IRA.graph.add_uniq_edge(G10_IRB2.label, G10_IRB3.label) + +# Expected output for graph 10 +G10_EXP_IRA = IRATest() + +G10_EXP_IRB0 = gen_irblock(LBL0, [[]]) +G10_EXP_IRB1 = gen_irblock(LBL1, [[]]) +G10_EXP_IRB2 = gen_irblock(LBL2, [[]]) +G10_EXP_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST1)]]) + +G10_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, b)]]) +G11_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) +G11_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) +G11_IRB3 = gen_irblock(LBL3, [[ExprAff(a, a+CST1)]]) +G11_IRB4 = gen_irblock(LBL4, [[ExprAff(b, b+CST1)]]) + + +G11_IRA.blocks = {irb.label : irb for irb in [G11_IRB0, G11_IRB1, G11_IRB2]} + +G11_IRA.graph.add_uniq_edge(G11_IRB0.label, G11_IRB1.label) +#G11_IRA.graph.add_uniq_edge(G11_IRB3.label, G11_IRB1.label) +G11_IRA.graph.add_uniq_edge(G11_IRB1.label, G11_IRB0.label) +#G11_IRA.graph.add_uniq_edge(G11_IRB4.label, G11_IRB0.label) +G11_IRA.graph.add_uniq_edge(G11_IRB1.label, G11_IRB2.label) + + +# Expected output for graph 11 +G11_EXP_IRA = IRATest() + +G11_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, b)]]) +G11_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) +G11_EXP_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)]]) +#G11_EXP_IRB3 = gen_irblock(LBL3, [[ExprAff(a, a+CST1)]]) +#G11_EXP_IRB4 = gen_irblock(LBL4, [[ExprAff(b, b+CST1)]]) + +G11_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(r, CST1)], [ExprAff(a, CST2)]]) +G12_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) +G12_IRB2 = gen_irblock(LBL2, [[ExprAff(r, a)], [ExprAff(b, CST3)]]) +G12_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST3)]]) +G12_IRB4 = gen_irblock(LBL4, [[ExprAff(r, CST2)]]) +G12_IRB5 = gen_irblock(LBL5, [[ExprAff(r, b)]]) + +G12_IRA.blocks = {irb.label : irb for irb in [G12_IRB0, G12_IRB1, G12_IRB2, + G12_IRB3, G12_IRB4, G12_IRB5]} + +G12_IRA.graph.add_uniq_edge(G12_IRB0.label, G12_IRB1.label) +G12_IRA.graph.add_uniq_edge(G12_IRB0.label, G12_IRB2.label) +G12_IRA.graph.add_uniq_edge(G12_IRB2.label, G12_IRB3.label) +G12_IRA.graph.add_uniq_edge(G12_IRB2.label, G12_IRB4.label) +G12_IRA.graph.add_uniq_edge(G12_IRB4.label, G12_IRB5.label) + +# Expected output for graph 12 +G12_EXP_IRA = IRATest() + +G12_EXP_IRB0 = gen_irblock(LBL0, [[], []]) +G12_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) +G12_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAff(b, CST3)]]) +G12_EXP_IRB3 = gen_irblock(LBL3, [[ExprAff(r, CST3)]]) +G12_EXP_IRB4 = gen_irblock(LBL4, [[]]) +G12_EXP_IRB5 = gen_irblock(LBL5, [[ExprAff(r, b)]]) + + +G12_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]]) +G13_IRB1 = gen_irblock(LBL1, [[ExprAff(r, b)]]) +G13_IRB2 = gen_irblock(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1), + ExprAff(c, a+b)]]) +G13_IRB3 = gen_irblock(LBL3, [[]]) # lost son +G13_IRB4 = gen_irblock(LBL4, [[ExprAff(b, CST2)]]) + +G13_IRA.blocks = {irb.label : irb for irb in [G13_IRB0, G13_IRB1, G13_IRB2, + G13_IRB4]} + +G13_IRA.graph.add_uniq_edge(G13_IRB0.label, G13_IRB1.label) +G13_IRA.graph.add_uniq_edge(G13_IRB0.label, G13_IRB4.label) +G13_IRA.graph.add_uniq_edge(G13_IRB2.label, G13_IRB3.label) +G13_IRA.graph.add_uniq_edge(G13_IRB4.label, G13_IRB2.label) + +# Expected output for graph 13 +G13_EXP_IRA = IRATest() + +G13_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]]) +G13_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, b)]]) +G13_EXP_IRB2 = gen_irblock(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1), + ExprAff(c, a+b)]]) +G13_EXP_IRB3 = gen_irblock(LBL3, [[]]) +G13_EXP_IRB4 = gen_irblock(LBL4, [[ExprAff(b, CST2)]]) + +G13_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(c, a)], + [ExprAff(a, CST2)]]) +G14_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a+c)]]) + +G14_IRA.blocks = {irb.label : irb for irb in [G14_IRB0, G14_IRB1]} + +G14_IRA.graph.add_uniq_edge(G14_IRB0.label, G14_IRB1.label) + +# Expected output for graph 1 +G14_EXP_IRA = IRATest() + +G14_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(c, a)], + [ExprAff(a, CST2)]]) +G14_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a+c)]]) + +G14_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST2)], [ExprAff(a, CST1), + ExprAff(b, a+CST2), + ExprAff(c, CST1)]]) +G15_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a)]]) + +G15_IRA.blocks = {irb.label : irb for irb in [G15_IRB0, G15_IRB1]} + +G15_IRA.graph.add_uniq_edge(G15_IRB0.label, G15_IRB1.label) + +# Expected output for graph 1 +G15_EXP_IRA = IRATest() + +G15_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(a, CST1)]]) +G15_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a)]]) + +G15_EXP_IRA.blocks = {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_irblock(LBL0, [[ExprAff(a, CST1), ExprAff(b, CST2), + ExprAff(c, CST3)], [ExprAff(a, c+CST1), + ExprAff(b, c+CST2)]]) +G16_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a+b)], [ExprAff(r, c+r)]]) +G16_IRB2 = gen_irblock(LBL2, [[]]) + +G16_IRA.blocks = {irb.label : irb for irb in [G16_IRB0, G16_IRB1]} + +G16_IRA.graph.add_uniq_edge(G16_IRB0.label, G16_IRB1.label) +G16_IRA.graph.add_uniq_edge(G16_IRB1.label, G16_IRB2.label) + +G16_IRA.blocks = {irb.label : irb for irb in [G16_IRB0, G16_IRB1]} + +# Expected output for graph 1 +G16_EXP_IRA = IRATest() + +G16_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(c, CST3)], [ExprAff(a, c + CST1), + ExprAff(b, c + CST2)]]) +G16_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, a+b)], [ExprAff(r, c+r)]]) + +G16_EXP_IRA.blocks = {irb.label: irb for irb in [G16_EXP_IRB0, G16_EXP_IRB1]} + +# graph 17 : parallel ir + +G17_IRA = IRATest() + +G17_IRB0 = gen_irblock(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.blocks = {irb.label : irb for irb in [G17_IRB0]} + +G17_IRA.graph.add_node(G17_IRB0.label) + +# Expected output for graph 17 +G17_EXP_IRA = IRATest() + +G17_EXP_IRB0 = gen_irblock(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.blocks = {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.dot()) + + reaching_defs = ReachingDefinitions(g_ira) + defuse = DiGraphDefUse(reaching_defs, deref_mem=True) + #open("defuse_%02d.dot" % (test_nb+1), "w").write(defuse.dot()) + + # # Simplify graph + dead_simp(g_ira) + + # # Print simplified graph, for debug + open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ira.graph.dot()) + + # Same number of blocks + assert len(g_ira.blocks) == len(g_exp_ira.blocks) + # Check that each expr in the blocks are the same + for lbl, irb in g_ira.blocks.iteritems(): + exp_irb = g_exp_ira.blocks[lbl] + assert exp_irb.irs == irb.irs |