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