diff options
Diffstat (limited to 'test/analysis/data_flow.py')
| -rw-r--r-- | test/analysis/data_flow.py | 362 |
1 files changed, 190 insertions, 172 deletions
diff --git a/test/analysis/data_flow.py b/test/analysis/data_flow.py index d0a85e13..d0dbbd8d 100644 --- a/test/analysis/data_flow.py +++ b/test/analysis/data_flow.py @@ -1,10 +1,12 @@ """ Test cases for dead code elimination""" from miasm2.expression.expression import ExprId, ExprInt, ExprAff, ExprMem -from miasm2.core.asmblock import AsmLabel +from miasm2.core.locationdb import LocationDB from miasm2.analysis.data_flow import * from miasm2.ir.analysis import ira from miasm2.ir.ir import IRBlock, AssignBlock +loc_db = LocationDB() + a = ExprId("a", 32) b = ExprId("b", 32) c = ExprId("c", 32) @@ -24,13 +26,13 @@ CST1 = ExprInt(0x11, 32) CST2 = ExprInt(0x12, 32) CST3 = ExprInt(0x13, 32) -LBL0 = AsmLabel("lbl0") -LBL1 = AsmLabel("lbl1") -LBL2 = AsmLabel("lbl2") -LBL3 = AsmLabel("lbl3") -LBL4 = AsmLabel("lbl4") -LBL5 = AsmLabel("lbl5") -LBL6 = AsmLabel("lbl6") +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) @@ -66,117 +68,122 @@ class IRATest(ira): """Fake IRA class for tests""" - def __init__(self, symbol_pool=None): + def __init__(self, loc_db=None): arch = Arch() - super(IRATest, self).__init__(arch, 32, symbol_pool) + super(IRATest, 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]) +IRA = IRATest(loc_db) + # graph 1 : Simple graph with dead and alive variables -G1_IRA = IRATest() +G1_IRA = IRA.new_ircfg() 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]} +for irb in [G1_IRB0, G1_IRB1, G1_IRB2]: + G1_IRA.add_irblock(irb) -G1_IRA.graph.add_uniq_edge(G1_IRB0.label, G1_IRB1.label) -G1_IRA.graph.add_uniq_edge(G1_IRB1.label, G1_IRB2.label) +G1_IRA.add_uniq_edge(G1_IRB0.loc_key, G1_IRB1.loc_key) +G1_IRA.add_uniq_edge(G1_IRB1.loc_key, G1_IRB2.loc_key) # Expected output for graph 1 -G1_EXP_IRA = IRATest() +G1_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G1_EXP_IRB0, G1_EXP_IRB1, G1_EXP_IRB2]: + G1_EXP_IRA.add_irblock(irb) # graph 2 : Natural loop with dead variable -G2_IRA = IRATest() +G2_IRA = IRA.new_ircfg() 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]} +for irb in [G2_IRB0, G2_IRB1, G2_IRB2]: + G2_IRA.add_irblock(irb) -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) +G2_IRA.add_uniq_edge(G2_IRB0.loc_key, G2_IRB1.loc_key) +G2_IRA.add_uniq_edge(G2_IRB1.loc_key, G2_IRB2.loc_key) +G2_IRA.add_uniq_edge(G2_IRB1.loc_key, G2_IRB1.loc_key) # Expected output for graph 2 -G2_EXP_IRA = IRATest() +G2_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G2_EXP_IRB0, G2_EXP_IRB1, G2_EXP_IRB2]: + G2_EXP_IRA.add_irblock(irb) # graph 3 : Natural loop with alive variables -G3_IRA = IRATest() +G3_IRA = IRA.new_ircfg() 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]} +for irb in [G3_IRB0, G3_IRB1, G3_IRB2]: + G3_IRA.add_irblock(irb) -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) +G3_IRA.add_uniq_edge(G3_IRB0.loc_key, G3_IRB1.loc_key) +G3_IRA.add_uniq_edge(G3_IRB1.loc_key, G3_IRB2.loc_key) +G3_IRA.add_uniq_edge(G3_IRB1.loc_key, G3_IRB1.loc_key) # Expected output for graph 3 -G3_EXP_IRA = IRATest() +G3_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G3_EXP_IRB0, G3_EXP_IRB1, G3_EXP_IRB2]: + G3_EXP_IRA.add_irblock(irb) # graph 4 : If/else with dead variables -G4_IRA = IRATest() +G4_IRA = IRA.new_ircfg() 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]} +for irb in [G4_IRB0, G4_IRB1, G4_IRB2, G4_IRB3]: + G4_IRA.add_irblock(irb) -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) +G4_IRA.add_uniq_edge(G4_IRB0.loc_key, G4_IRB1.loc_key) +G4_IRA.add_uniq_edge(G4_IRB0.loc_key, G4_IRB2.loc_key) +G4_IRA.add_uniq_edge(G4_IRB1.loc_key, G4_IRB3.loc_key) +G4_IRA.add_uniq_edge(G4_IRB2.loc_key, G4_IRB3.loc_key) # Expected output for graph 4 -G4_EXP_IRA = IRATest() +G4_EXP_IRA = IRA.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, [[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]} +for irb in [G4_EXP_IRB0, G4_EXP_IRB1, G4_EXP_IRB2, G4_EXP_IRB3]: + G4_EXP_IRA.add_irblock(irb) # graph 5 : Loop and If/else with dead variables -G5_IRA = IRATest() +G5_IRA = IRA.new_ircfg() G5_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)]]) G5_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) @@ -185,19 +192,19 @@ 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]} +for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3, G5_IRB4, G5_IRB5]: + G5_IRA.add_irblock(irb) -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) +G5_IRA.add_uniq_edge(G5_IRB0.loc_key, G5_IRB1.loc_key) +G5_IRA.add_uniq_edge(G5_IRB1.loc_key, G5_IRB2.loc_key) +G5_IRA.add_uniq_edge(G5_IRB1.loc_key, G5_IRB3.loc_key) +G5_IRA.add_uniq_edge(G5_IRB2.loc_key, G5_IRB4.loc_key) +G5_IRA.add_uniq_edge(G5_IRB3.loc_key, G5_IRB4.loc_key) +G5_IRA.add_uniq_edge(G5_IRB4.loc_key, G5_IRB5.loc_key) +G5_IRA.add_uniq_edge(G5_IRB4.loc_key, G5_IRB1.loc_key) # Expected output for graph 5 -G5_EXP_IRA = IRATest() +G5_EXP_IRA = IRA.new_ircfg() G5_EXP_IRB0 = gen_irblock(LBL0, [[]]) G5_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) @@ -206,72 +213,72 @@ 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]} +for irb in [G5_EXP_IRB0, G5_EXP_IRB1, G5_EXP_IRB2, + G5_EXP_IRB3, G5_EXP_IRB4, G5_EXP_IRB5]: + G5_EXP_IRA.add_irblock(irb) # graph 6 : Natural loop with dead variables symetric affectation # (a = b <-> b = a ) -G6_IRA = IRATest() +G6_IRA = IRA.new_ircfg() 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]} +for irb in [G6_IRB0, G6_IRB1, G6_IRB2, G6_IRB3]: + G6_IRA.add_irblock(irb) -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) +G6_IRA.add_uniq_edge(G6_IRB0.loc_key, G6_IRB1.loc_key) +G6_IRA.add_uniq_edge(G6_IRB1.loc_key, G6_IRB2.loc_key) +G6_IRA.add_uniq_edge(G6_IRB2.loc_key, G6_IRB1.loc_key) +G6_IRA.add_uniq_edge(G6_IRB2.loc_key, G6_IRB3.loc_key) # Expected output for graph 6 -G6_EXP_IRA = IRATest() +G6_EXP_IRA = IRA.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, [[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]} +for irb in [G6_EXP_IRB0, G6_EXP_IRB1, G6_EXP_IRB2, G6_EXP_IRB3]: + G6_EXP_IRA.add_irblock(irb) # graph 7 : Double entry loop with dead variables -G7_IRA = IRATest() +G7_IRA = IRA.new_ircfg() 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]} +for irb in [G7_IRB0, G7_IRB1, G7_IRB2, G7_IRB3]: + G7_IRA.add_irblock(irb) -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) +G7_IRA.add_uniq_edge(G7_IRB0.loc_key, G7_IRB1.loc_key) +G7_IRA.add_uniq_edge(G7_IRB1.loc_key, G7_IRB2.loc_key) +G7_IRA.add_uniq_edge(G7_IRB2.loc_key, G7_IRB1.loc_key) +G7_IRA.add_uniq_edge(G7_IRB2.loc_key, G7_IRB3.loc_key) +G7_IRA.add_uniq_edge(G7_IRB0.loc_key, G7_IRB2.loc_key) # Expected output for graph 7 -G7_EXP_IRA = IRATest() +G7_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G7_EXP_IRB0, G7_EXP_IRB1, G7_EXP_IRB2, G7_EXP_IRB3]: + G7_EXP_IRA.add_irblock(irb) # graph 8 : Nested loops with dead variables -G8_IRA = IRATest() +G8_IRA = IRA.new_ircfg() G8_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]]) G8_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)]]) @@ -279,31 +286,31 @@ 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]} +for irb in [G8_IRB0, G8_IRB1, G8_IRB2, G8_IRB3]: + G8_IRA.add_irblock(irb) -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) +G8_IRA.add_uniq_edge(G8_IRB0.loc_key, G8_IRB1.loc_key) +G8_IRA.add_uniq_edge(G8_IRB1.loc_key, G8_IRB2.loc_key) +G8_IRA.add_uniq_edge(G8_IRB2.loc_key, G8_IRB1.loc_key) +G8_IRA.add_uniq_edge(G8_IRB2.loc_key, G8_IRB3.loc_key) +G8_IRA.add_uniq_edge(G8_IRB3.loc_key, G8_IRB2.loc_key) # Expected output for graph 8 -G8_EXP_IRA = IRATest() +G8_EXP_IRA = IRA.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, [[]]) -G8_EXP_IRA.blocks = {irb.label : irb for irb in [G8_EXP_IRB0, G8_EXP_IRB1, - G8_EXP_IRB2, G8_EXP_IRB3]} +for irb in [G8_EXP_IRB0, G8_EXP_IRB1, G8_EXP_IRB2, G8_EXP_IRB3]: + G8_EXP_IRA.add_irblock(irb) # graph 9 : Miultiple-exits loops with dead variables -G9_IRA = IRATest() +G9_IRA = IRA.new_ircfg() G9_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST1)]]) G9_IRB1 = gen_irblock(LBL1, [[ExprAff(a, a+CST1)], [ExprAff(b, b+CST1)]]) @@ -311,22 +318,22 @@ 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]} +for irb in [G9_IRB0, G9_IRB1, G9_IRB2, G9_IRB3, G9_IRB4]: + G9_IRA.add_irblock(irb) -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) +G9_IRA.add_uniq_edge(G9_IRB0.loc_key, G9_IRB4.loc_key) +G9_IRA.add_uniq_edge(G9_IRB0.loc_key, G9_IRB1.loc_key) +G9_IRA.add_uniq_edge(G9_IRB1.loc_key, G9_IRB0.loc_key) +G9_IRA.add_uniq_edge(G9_IRB1.loc_key, G9_IRB4.loc_key) +G9_IRA.add_uniq_edge(G9_IRB1.loc_key, G9_IRB2.loc_key) +G9_IRA.add_uniq_edge(G9_IRB2.loc_key, G9_IRB0.loc_key) +G9_IRA.add_uniq_edge(G9_IRB2.loc_key, G9_IRB3.loc_key) +G9_IRA.add_uniq_edge(G9_IRB3.loc_key, G9_IRB4.loc_key) # Expected output for graph 9 -G9_EXP_IRA = IRATest() +G9_EXP_IRA = IRA.new_ircfg() G9_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAff(b, CST1)]]) G9_EXP_IRB1 = gen_irblock(LBL1, [[], [ExprAff(b, b+CST1)]]) @@ -334,42 +341,42 @@ 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]} +for irb in [G9_EXP_IRB0, G9_EXP_IRB1, G9_EXP_IRB2, G9_EXP_IRB3, G9_EXP_IRB4]: + G9_EXP_IRA.add_irblock(irb) # graph 10 : Natural loop with alive variables symetric affectation # (a = b <-> b = a ) -G10_IRA = IRATest() +G10_IRA = IRA.new_ircfg() 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]} +for irb in [G10_IRB0, G10_IRB1, G10_IRB2, G10_IRB3]: + G10_IRA.add_irblock(irb) + -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) +G10_IRA.add_uniq_edge(G10_IRB0.loc_key, G10_IRB1.loc_key) +G10_IRA.add_uniq_edge(G10_IRB1.loc_key, G10_IRB2.loc_key) +G10_IRA.add_uniq_edge(G10_IRB2.loc_key, G10_IRB1.loc_key) +G10_IRA.add_uniq_edge(G10_IRB2.loc_key, G10_IRB3.loc_key) # Expected output for graph 10 -G10_EXP_IRA = IRATest() +G10_EXP_IRA = IRA.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, [[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]} +for irb in [G10_EXP_IRB0, G10_EXP_IRB1, G10_EXP_IRB2, G10_EXP_IRB3]: + G10_EXP_IRA.add_irblock(irb) # graph 11 : If/Else conditions with alive variables -G11_IRA = IRATest() +G11_IRA = IRA.new_ircfg() G11_IRB0 = gen_irblock(LBL0, [[ExprAff(a, b)]]) G11_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) @@ -378,17 +385,18 @@ 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]} +for irb in [G11_IRB0, G11_IRB1, G11_IRB2]: + G11_IRA.add_irblock(irb) -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) +G11_IRA.add_uniq_edge(G11_IRB0.loc_key, G11_IRB1.loc_key) +#G11_IRA.add_uniq_edge(G11_IRB3.loc_key, G11_IRB1.loc_key) +G11_IRA.add_uniq_edge(G11_IRB1.loc_key, G11_IRB0.loc_key) +#G11_IRA.add_uniq_edge(G11_IRB4.loc_key, G11_IRB0.loc_key) +G11_IRA.add_uniq_edge(G11_IRB1.loc_key, G11_IRB2.loc_key) # Expected output for graph 11 -G11_EXP_IRA = IRATest() +G11_EXP_IRA = IRA.new_ircfg() G11_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, b)]]) G11_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(b, a)]]) @@ -396,13 +404,14 @@ 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]} +for irb in [G11_EXP_IRB0, G11_EXP_IRB1, + G11_EXP_IRB2]: + G11_EXP_IRA.add_irblock(irb) # graph 12 : Graph with multiple out points and useless definitions # of return register -G12_IRA = IRATest() +G12_IRA = IRA.new_ircfg() G12_IRB0 = gen_irblock(LBL0, [[ExprAff(r, CST1)], [ExprAff(a, CST2)]]) G12_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) @@ -411,17 +420,17 @@ 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]} +for irb in [G12_IRB0, G12_IRB1, G12_IRB2, G12_IRB3, G12_IRB4, G12_IRB5]: + G12_IRA.add_irblock(irb) -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) +G12_IRA.add_uniq_edge(G12_IRB0.loc_key, G12_IRB1.loc_key) +G12_IRA.add_uniq_edge(G12_IRB0.loc_key, G12_IRB2.loc_key) +G12_IRA.add_uniq_edge(G12_IRB2.loc_key, G12_IRB3.loc_key) +G12_IRA.add_uniq_edge(G12_IRB2.loc_key, G12_IRB4.loc_key) +G12_IRA.add_uniq_edge(G12_IRB4.loc_key, G12_IRB5.loc_key) # Expected output for graph 12 -G12_EXP_IRA = IRATest() +G12_EXP_IRA = IRA.new_ircfg() G12_EXP_IRB0 = gen_irblock(LBL0, [[], []]) G12_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, CST2)]]) @@ -431,13 +440,14 @@ 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]} +for irb in [G12_EXP_IRB0, G12_EXP_IRB1, + G12_EXP_IRB2, G12_EXP_IRB3, + G12_EXP_IRB4, G12_EXP_IRB5]: + G12_EXP_IRA.add_irblock(irb) # graph 13 : Graph where a leaf has lost its son -G13_IRA = IRATest() +G13_IRA = IRA.new_ircfg() G13_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]]) G13_IRB1 = gen_irblock(LBL1, [[ExprAff(r, b)]]) @@ -446,16 +456,16 @@ G13_IRB2 = gen_irblock(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1), 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]} +for irb in [G13_IRB0, G13_IRB1, G13_IRB2, G13_IRB4]: + G13_IRA.add_irblock(irb) -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) +G13_IRA.add_uniq_edge(G13_IRB0.loc_key, G13_IRB1.loc_key) +G13_IRA.add_uniq_edge(G13_IRB0.loc_key, G13_IRB4.loc_key) +G13_IRA.add_uniq_edge(G13_IRB2.loc_key, G13_IRB3.loc_key) +G13_IRA.add_uniq_edge(G13_IRB4.loc_key, G13_IRB2.loc_key) # Expected output for graph 13 -G13_EXP_IRA = IRATest() +G13_EXP_IRA = IRA.new_ircfg() G13_EXP_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1)], [ExprAff(b, CST2)]]) G13_EXP_IRB1 = gen_irblock(LBL1, [[ExprAff(r, b)]]) @@ -464,58 +474,62 @@ G13_EXP_IRB2 = gen_irblock(LBL2, [[ExprAff(d, CST2)], [ExprAff(a, b+CST1), 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]} +for irb in [G13_EXP_IRB0, G13_EXP_IRB1, G13_EXP_IRB2, G13_EXP_IRB4]: + G13_EXP_IRA.add_irblock(irb) #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_IRA = IRA.new_ircfg() 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]} +for irb in [G14_IRB0, G14_IRB1]: + G14_IRA.add_irblock(irb) -G14_IRA.graph.add_uniq_edge(G14_IRB0.label, G14_IRB1.label) +G14_IRA.add_uniq_edge(G14_IRB0.loc_key, G14_IRB1.loc_key) # Expected output for graph 1 -G14_EXP_IRA = IRATest() +G14_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G14_EXP_IRB0, G14_EXP_IRB1]: + G14_EXP_IRA.add_irblock(irb) # graph 15 : Graph where variable assigned multiple and read at the same time, # but useless -G15_IRA = IRATest() +G15_IRA = IRA.new_ircfg() 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]} +for irb in [G15_IRB0, G15_IRB1]: + G15_IRA.add_irblock(irb) -G15_IRA.graph.add_uniq_edge(G15_IRB0.label, G15_IRB1.label) +G15_IRA.add_uniq_edge(G15_IRB0.loc_key, G15_IRB1.loc_key) # Expected output for graph 1 -G15_EXP_IRA = IRATest() +G15_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G15_EXP_IRB0, G15_EXP_IRB1]: + G15_EXP_IRA.add_irblock(irb) # graph 16 : Graph where variable assigned multiple times in the same bloc -G16_IRA = IRATest() +G16_IRA = IRA.new_ircfg() G16_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1), ExprAff(b, CST2), ExprAff(c, CST3)], [ExprAff(a, c+CST1), @@ -523,25 +537,28 @@ G16_IRB0 = gen_irblock(LBL0, [[ExprAff(a, CST1), ExprAff(b, 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]} +for irb in [G16_IRB0, G16_IRB1]: + G16_IRA.add_irblock(irb) -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.add_uniq_edge(G16_IRB0.loc_key, G16_IRB1.loc_key) +G16_IRA.add_uniq_edge(G16_IRB1.loc_key, G16_IRB2.loc_key) -G16_IRA.blocks = {irb.label : irb for irb in [G16_IRB0, G16_IRB1]} +for irb in [G16_IRB0, G16_IRB1]: + G16_IRA.add_irblock(irb) # Expected output for graph 1 -G16_EXP_IRA = IRATest() +G16_EXP_IRA = IRA.new_ircfg() 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]} +for irb in [G16_EXP_IRB0, G16_EXP_IRB1]: + G16_EXP_IRA.add_irblock(irb) # graph 17 : parallel ir -G17_IRA = IRATest() +G17_IRA = IRA.new_ircfg() G17_IRB0 = gen_irblock(LBL0, [[ExprAff(a, a*b), ExprAff(b, c), @@ -597,12 +614,13 @@ G17_IRB0 = gen_irblock(LBL0, [[ExprAff(a, a*b), ]) -G17_IRA.blocks = {irb.label : irb for irb in [G17_IRB0]} +for irb in [G17_IRB0]: + G17_IRA.add_irblock(irb) -G17_IRA.graph.add_node(G17_IRB0.label) +#G17_IRA.graph.add_node(G17_IRB0.loc_key) # Expected output for graph 17 -G17_EXP_IRA = IRATest() +G17_EXP_IRA = IRA.new_ircfg() G17_EXP_IRB0 = gen_irblock(LBL0, [[], @@ -639,7 +657,8 @@ G17_EXP_IRB0 = gen_irblock(LBL0, [[], # Trick because a+b+c != ((a+b)+c) ]) -G17_EXP_IRA.blocks = {irb.label : irb for irb in [G17_EXP_IRB0]} +for irb in [G17_EXP_IRB0]: + G17_EXP_IRA.add_irblock(irb) # Begining of tests @@ -667,17 +686,16 @@ for test_nb, test in enumerate([(G1_IRA, G1_EXP_IRA), print "[+] Test", test_nb+1 # Print initial graph, for debug - open("graph_%02d.dot" % (test_nb+1), "w").write(g_ira.graph.dot()) + open("graph_%02d.dot" % (test_nb+1), "w").write(g_ira.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) + dead_simp(IRA, g_ira) # # Print simplified graph, for debug - open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ira.graph.dot()) + open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ira.dot()) # Same number of blocks assert len(g_ira.blocks) == len(g_exp_ira.blocks) |