diff options
| -rw-r--r-- | example/disasm/full.py | 16 | ||||
| -rw-r--r-- | example/expression/constant_propagation.py | 9 | ||||
| -rw-r--r-- | miasm2/analysis/data_flow.py | 253 | ||||
| -rw-r--r-- | miasm2/analysis/depgraph.py | 4 | ||||
| -rw-r--r-- | miasm2/ir/ir.py | 173 | ||||
| -rw-r--r-- | test/ir/reduce_graph.py | 531 | ||||
| -rwxr-xr-x | test/test_all.py | 1 |
7 files changed, 828 insertions, 159 deletions
diff --git a/example/disasm/full.py b/example/disasm/full.py index fdd220ca..9e1c422d 100644 --- a/example/disasm/full.py +++ b/example/disasm/full.py @@ -7,7 +7,8 @@ from miasm2.core.asmblock import log_asmblock, AsmCFG from miasm2.expression.expression import ExprId from miasm2.core.interval import interval from miasm2.analysis.machine import Machine -from miasm2.analysis.data_flow import dead_simp, DiGraphDefUse, ReachingDefinitions +from miasm2.analysis.data_flow import dead_simp, DiGraphDefUse, \ + ReachingDefinitions, merge_blocks, remove_empty_assignblks from miasm2.expression.simplifications import expr_simp from miasm2.analysis.ssa import SSAPath, SSADiGraph @@ -119,6 +120,7 @@ all_funcs_blocks = {} done_interval = interval() finish = False +entry_points = set() # Main disasm loop while not finish and todo: while not finish and todo: @@ -127,6 +129,7 @@ while not finish and todo: continue done.add(ad) asmcfg = mdis.dis_multiblock(ad) + entry_points.add(mdis.loc_db.get_offset_location(ad)) log.info('func ok %.16x (%d)' % (ad, len(all_funcs))) @@ -229,22 +232,21 @@ if args.gen_ir: open('graph_irflow_raw.dot', 'w').write(out) if args.simplify > 1: + ircfg_a.simplify(expr_simp) modified = True while modified: modified = False modified |= dead_simp(ir_arch_a, ircfg_a) - modified |= ircfg_a.remove_empty_assignblks() - modified |= ircfg_a.remove_jmp_blocks() - modified |= ircfg_a.merge_blocks() + modified |= remove_empty_assignblks(ircfg_a) + modified |= merge_blocks(ircfg_a, entry_points) open('graph_irflow_reduced.dot', 'w').write(ircfg_a.dot()) if args.ssa: - heads = ircfg_a.heads() - if len(heads) != 1: + if len(entry_points) != 1: raise RuntimeError("Your graph should have only one head") - head = list(heads)[0] + head = list(entry_points)[0] ssa = SSADiGraph(ircfg_a) ssa.transform(head) diff --git a/example/expression/constant_propagation.py b/example/expression/constant_propagation.py index d9c5fe65..0798c404 100644 --- a/example/expression/constant_propagation.py +++ b/example/expression/constant_propagation.py @@ -10,7 +10,8 @@ from miasm2.arch.x86.disasm import dis_x86_32 as dis_engine from miasm2.analysis.machine import Machine from miasm2.analysis.binary import Container from miasm2.analysis.cst_propag import propagate_cst_expr -from miasm2.analysis.data_flow import dead_simp +from miasm2.analysis.data_flow import dead_simp, \ + merge_blocks, remove_empty_assignblks from miasm2.expression.simplifications import expr_simp @@ -33,6 +34,7 @@ addr = int(args.address, 0) asmcfg = mdis.dis_multiblock(addr) ircfg = ir_arch.new_ircfg_from_asmcfg(asmcfg) +entry_points = set([mdis.loc_db.get_offset_location(addr)]) init_infos = ir_arch.arch.regs.regs_init cst_propag_link = propagate_cst_expr(ir_arch, ircfg, addr, init_infos) @@ -43,9 +45,8 @@ if args.simplify: while modified: modified = False modified |= dead_simp(ir_arch, ircfg) - modified |= ircfg.remove_empty_assignblks() - modified |= ircfg.remove_jmp_blocks() - modified |= ircfg.merge_blocks() + modified |= remove_empty_assignblks(ircfg) + modified |= merge_blocks(ircfg, entry_points) open("%s.propag.dot" % args.filename, 'w').write(ircfg.dot()) diff --git a/miasm2/analysis/data_flow.py b/miasm2/analysis/data_flow.py index 9e5203a6..d0f2a0b1 100644 --- a/miasm2/analysis/data_flow.py +++ b/miasm2/analysis/data_flow.py @@ -3,6 +3,8 @@ from collections import namedtuple from miasm2.core.graph import DiGraph from miasm2.ir.ir import AssignBlock, IRBlock +from miasm2.expression.expression import ExprLoc + class ReachingDefinitions(dict): """ @@ -95,6 +97,7 @@ ATTR_DEP = {"color" : "black", AssignblkNode = namedtuple('AssignblkNode', ['label', 'index', 'var']) + class DiGraphDefUse(DiGraph): """Representation of a Use-Definition graph as defined by Kennedy, K. (1979). A survey of data flow analysis techniques. @@ -118,7 +121,7 @@ class DiGraphDefUse(DiGraph): def __init__(self, reaching_defs, deref_mem=False, *args, **kwargs): - """Instanciate a DiGraphIR + """Instanciate a DiGraph @blocks: IR blocks """ self._edge_attr = {} @@ -217,17 +220,16 @@ def dead_simp_useful_assignblks(irarch, defuse, reaching_defs): valid_definitions = reaching_defs.get_definitions(block_lbl, len(block)) for lval, definitions in valid_definitions.iteritems(): - if (lval in irarch.get_out_regs(block) - or keep_all_definitions): + if lval in irarch.get_out_regs(block) or keep_all_definitions: for definition in definitions: useful.add(AssignblkNode(definition[0], definition[1], lval)) # Force keeping of specific cases for index, assignblk in enumerate(block): for lval, rval in assignblk.iteritems(): - if (lval.is_mem() - or irarch.IRDst == lval - or rval.is_function_call()): + if (lval.is_mem() or + irarch.IRDst == lval or + rval.is_function_call()): useful.add(AssignblkNode(block_lbl, index, lval)) # Useful nodes dependencies @@ -235,6 +237,7 @@ def dead_simp_useful_assignblks(irarch, defuse, reaching_defs): for parent in defuse.reachable_parents(node): yield parent + def dead_simp(irarch, ircfg): """ Remove useless affectations. @@ -263,3 +266,241 @@ def dead_simp(irarch, ircfg): irs.append(AssignBlock(new_assignblk, assignblk.instr)) ircfg.blocks[block.loc_key] = IRBlock(block.loc_key, irs) return modified + + +def _test_merge_next_block(ircfg, loc_key): + """ + Test if the irblock at @loc_key can be merge with its son + @ircfg: IRCFG instance + @loc_key: LocKey instance of the candidate parent irblock + """ + + if loc_key not in ircfg.blocks: + return None + sons = ircfg.successors(loc_key) + if len(sons) != 1: + return None + son = list(sons)[0] + if ircfg.predecessors(son) != [loc_key]: + return None + if son not in ircfg.blocks: + return None + return son + + +def _do_merge_blocks(ircfg, loc_key, son_loc_key): + """ + Merge two irblocks at @loc_key and @son_loc_key + + @ircfg: DiGrpahIR + @loc_key: LocKey instance of the parent IRBlock + @loc_key: LocKey instance of the son IRBlock + """ + + assignblks = [] + for assignblk in ircfg.blocks[loc_key]: + if ircfg.IRDst not in assignblk: + assignblks.append(assignblk) + continue + affs = {} + for dst, src in assignblk.iteritems(): + if dst != ircfg.IRDst: + affs[dst] = src + if affs: + assignblks.append(AssignBlock(affs, assignblk.instr)) + + assignblks += ircfg.blocks[son_loc_key].assignblks + new_block = IRBlock(loc_key, assignblks) + + ircfg.discard_edge(loc_key, son_loc_key) + + for son_successor in ircfg.successors(son_loc_key): + ircfg.add_uniq_edge(loc_key, son_successor) + ircfg.discard_edge(son_loc_key, son_successor) + del ircfg.blocks[son_loc_key] + ircfg.del_node(son_loc_key) + ircfg.blocks[loc_key] = new_block + + +def _test_jmp_only(ircfg, loc_key): + """ + If irblock at @loc_key sets only IRDst to an ExprLoc, return the + corresponding loc_key target. + None in other cases. + + @ircfg: IRCFG instance + @loc_key: LocKey instance of the candidate irblock + + """ + + if loc_key not in ircfg.blocks: + return None + irblock = ircfg.blocks[loc_key] + if len(irblock.assignblks) != 1: + return None + items = dict(irblock.assignblks[0]).items() + if len(items) != 1: + return None + dst, src = items[0] + assert dst.is_id("IRDst") + if not src.is_loc(): + return None + return src.loc_key + + +def _relink_block_node(ircfg, loc_key, son_loc_key, replace_dct): + """ + Link loc_key's parents to parents directly to son_loc_key + """ + for parent in set(ircfg.predecessors(loc_key)): + parent_block = ircfg.blocks[parent] + + new_block = parent_block.modify_exprs( + lambda expr:expr.replace_expr(replace_dct), + lambda expr:expr.replace_expr(replace_dct) + ) + + # Link parent to new dst + ircfg.add_edge(parent, son_loc_key) + + # Unlink block + ircfg.blocks[new_block.loc_key] = new_block + ircfg.del_node(loc_key) + + +def _remove_to_son(ircfg, loc_key, son_loc_key): + """ + Merge irblocks; The final block has the @son_loc_key loc_key + Update references + + Condition: + - irblock at @loc_key is a pure jump block + - @loc_key is not an entry point (can be removed) + + @irblock: IRCFG instance + @loc_key: LocKey instance of the parent irblock + @son_loc_key: LocKey instance of the son irblock + """ + + # Ircfg loop => don't mess + if loc_key == son_loc_key: + return False + + # Unlink block destinations + ircfg.del_edge(loc_key, son_loc_key) + del ircfg.blocks[loc_key] + + replace_dct = { + ExprLoc(loc_key, ircfg.IRDst.size):ExprLoc(son_loc_key, ircfg.IRDst.size) + } + + _relink_block_node(ircfg, loc_key, son_loc_key, replace_dct) + + return True + + +def _remove_to_parent(ircfg, loc_key, son_loc_key): + """ + Merge irblocks; The final block has the @loc_key loc_key + Update references + + Condition: + - irblock at @loc_key is a pure jump block + - @son_loc_key is not an entry point (can be removed) + + @irblock: IRCFG instance + @loc_key: LocKey instance of the parent irblock + @son_loc_key: LocKey instance of the son irblock + """ + + # Ircfg loop => don't mess + if loc_key == son_loc_key: + return False + + # Unlink block destinations + ircfg.del_edge(loc_key, son_loc_key) + + old_irblock = ircfg.blocks[son_loc_key] + new_irblock = IRBlock(loc_key, old_irblock.assignblks) + + ircfg.blocks[son_loc_key] = new_irblock + + del ircfg.blocks[son_loc_key] + ircfg.add_irblock(new_irblock) + + replace_dct = { + ExprLoc(son_loc_key, ircfg.IRDst.size):ExprLoc(loc_key, ircfg.IRDst.size) + } + + _relink_block_node(ircfg, son_loc_key, loc_key, replace_dct) + + return True + + +def merge_blocks(ircfg, loc_key_entries): + """ + This function modifies @ircfg to apply the following transformations: + - group an irblock with its son if the irblock has one and only one son and + this son has one and only one parent (spaghetti code). + - if an irblock is only made of an assignment to IRDst with a given label, + this irblock is dropped and its parent destination targets are + updated. The irblock must have a parent (avoid deleting the function head) + - if an irblock is a head of the graph and is only made of an assignment to + IRDst with a given label, this irblock is dropped and its son becomes the + head. References are fixed + + Return True if at least an irblock has been modified + + @ircfg: IRCFG instance + @loc_key_entries: loc_key to keep + """ + + modified = False + todo = set(ircfg.nodes()) + while todo: + loc_key = todo.pop() + + # Test merge block + son = _test_merge_next_block(ircfg, loc_key) + if son is not None and son not in loc_key_entries: + _do_merge_blocks(ircfg, loc_key, son) + todo.add(loc_key) + modified = True + continue + + # Test jmp only block + son = _test_jmp_only(ircfg, loc_key) + if son is not None and loc_key not in loc_key_entries: + modified |= _remove_to_son(ircfg, loc_key, son) + todo.add(loc_key) + continue + + # Test head jmp only block + if son is not None and son not in loc_key_entries: + # jmp only test done previously + modified |= _remove_to_parent(ircfg, loc_key, son) + todo.add(loc_key) + continue + + + return modified + + +def remove_empty_assignblks(ircfg): + """ + Remove empty assignblks in irblocks of @ircfg + Return True if at least an irblock has been modified + + @ircfg: IRCFG instance + """ + modified = False + for loc_key, block in ircfg.blocks.iteritems(): + irs = [] + for assignblk in block: + if len(assignblk): + irs.append(assignblk) + else: + modified = True + ircfg.blocks[loc_key] = IRBlock(loc_key, irs) + + return modified diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 93b3edb5..a5f3f0fd 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -452,7 +452,7 @@ class DependencyGraph(object): follow_call=True): """Create a DependencyGraph linked to @ircfg - @ircfg: DiGraphIR instance + @ircfg: IRCFG instance @implicit: (optional) Track IRDst for each block in the resulting path Following arguments define filters used to generate dependencies @@ -590,7 +590,7 @@ class DependencyGraph(object): def get(self, loc_key, elements, line_nb, heads): """Compute the dependencies of @elements at line number @line_nb in - the block named @loc_key in the current DiGraphIR, before the execution of + the block named @loc_key in the current IRCFG, before the execution of this line. Dependency check stop if one of @heads is reached @loc_key: LocKey instance @element: set of Expr instances diff --git a/miasm2/ir/ir.py b/miasm2/ir/ir.py index bf9b4e9a..721101e2 100644 --- a/miasm2/ir/ir.py +++ b/miasm2/ir/ir.py @@ -302,6 +302,20 @@ class IRBlock(object): self._dst = None self._dst_linenb = None + def __eq__(self, other): + if self.__class__ is not other.__class__: + return False + if self.loc_key != other.loc_key: + return False + if len(self.assignblks) != len(other.assignblks): + return False + for assignblk1, assignblk2 in zip(self.assignblks, other.assignblks): + if assignblk1 != assignblk2: + return False + return True + + def __ne__(self, other): + return not self.__eq__(other) def get_label(self): warnings.warn('DEPRECATION WARNING: use ".loc_key" instead of ".label"') @@ -421,7 +435,7 @@ class IRBlock(object): node_name = "".join("%s:\n" % name for name in names) out.append(node_name) - for i, assignblk in enumerate(self): + for assignblk in self: out.append(assignblk.to_string(loc_db)) return '\n'.join(out) @@ -437,12 +451,12 @@ class irbloc(IRBlock): super(irbloc, self).__init__(loc_key, irs) -class DiGraphIR(DiGraph): +class IRCFG(DiGraph): """DiGraph for IR instances""" def __init__(self, irdst, loc_db, blocks=None, *args, **kwargs): - """Instanciate a DiGraphIR + """Instanciate a IRCFG @loc_db: LocationDB instance @blocks: IR blocks """ @@ -451,7 +465,7 @@ class DiGraphIR(DiGraph): blocks = {} self._blocks = blocks self._irdst = irdst - super(DiGraphIR, self).__init__(*args, **kwargs) + super(IRCFG, self).__init__(*args, **kwargs) @property def IRDst(self): @@ -463,7 +477,7 @@ class DiGraphIR(DiGraph): def add_irblock(self, irblock): """ - Add the @irblock to the current DiGraphIR + Add the @irblock to the current IRCFG @irblock: IRBlock instance """ self.blocks[irblock.loc_key] = irblock @@ -533,7 +547,7 @@ class DiGraphIR(DiGraph): node """ self._dot_offset = offset - return super(DiGraphIR, self).dot() + return super(IRCFG, self).dot() def get_loc_key(self, addr): """Transforms an ExprId/ExprInt/loc_key/int into a loc_key @@ -661,137 +675,16 @@ class DiGraphIR(DiGraph): return done - def remove_empty_assignblks(self): - modified = False - for loc_key, block in self.blocks.iteritems(): - irs = [] - for assignblk in block: - if len(assignblk): - irs.append(assignblk) - else: - modified = True - self.blocks[loc_key] = IRBlock(loc_key, irs) - return modified - - def remove_jmp_blocks(self): - """ - Remove irblock with only IRDst set, by linking it's parent destination to - the block destination. - """ - - # Find candidates - jmp_blocks = set() - for block in self.blocks.itervalues(): - if len(block) != 1: - continue - assignblk = block[0] - if len(assignblk) > 1: - continue - assert set(assignblk.keys()) == set([self.IRDst]) - if len(self.successors(block.loc_key)) != 1: - continue - if not assignblk[self.IRDst].is_loc(): - continue - dst = assignblk[self.IRDst].loc_key - if dst == block.loc_key: - # Infinite loop block - continue - jmp_blocks.add(block.loc_key) - - # Remove them, relink graph - modified = False - for loc_key in jmp_blocks: - block = self.blocks[loc_key] - dst_loc_key = block.dst - parents = self.predecessors(block.loc_key) - for lbl in parents: - parent = self.blocks.get(lbl, None) - if parent is None: - continue - dst = parent.dst - if dst.is_id(block.loc_key): - dst = m2_expr.ExprLoc(dst_loc_key, dst.size) - - self.discard_edge(lbl, block.loc_key) - self.discard_edge(block.loc_key, dst_loc_key) - self.add_uniq_edge(lbl, dst_loc_key) - modified = True - elif dst.is_cond(): - src1, src2 = dst.src1, dst.src2 - if src1.is_id(block.loc_key): - dst = m2_expr.ExprCond(dst.cond, m2_expr.ExprLoc(dst_loc_key, dst.size), dst.src2) - self.discard_edge(lbl, block.loc_key) - self.discard_edge(block.loc_key, dst_loc_key) - self.add_uniq_edge(lbl, dst_loc_key) - modified = True - if src2.is_id(block.loc_key): - dst = m2_expr.ExprCond(dst.cond, dst.src1, m2_expr.ExprLoc(dst_loc_key, dst.size)) - self.discard_edge(lbl, block.loc_key) - self.discard_edge(block.loc_key, dst_loc_key) - self.add_uniq_edge(lbl, dst_loc_key) - modified = True - if dst.src1 == dst.src2: - dst = dst.src1 - else: - continue - new_parent = parent.set_dst(dst) - self.blocks[parent.loc_key] = new_parent - - # Remove unlinked useless nodes - for loc_key in jmp_blocks: - if (len(self.predecessors(loc_key)) == 0 and - len(self.successors(loc_key)) == 0): - self.del_node(loc_key) - del self.blocks[loc_key] - return modified +class DiGraphIR(IRCFG): + """ + DEPRECATED object + Use IRCFG instead of DiGraphIR + """ - def merge_blocks(self): - """ - Group irblock with one and only one son if this son has one and only one - parent - """ - modified = False - todo = set(self.nodes()) - while todo: - block = todo.pop() - sons = self.successors(block) - if len(sons) != 1: - continue - son = list(sons)[0] - if self.predecessors(son) != [block]: - continue - if block not in self.blocks: - continue - if son not in self.blocks: - continue - # Block has one son, son has one parent => merge - assignblks = [] - for assignblk in self.blocks[block]: - if self.IRDst not in assignblk: - assignblks.append(assignblk) - continue - affs = {} - for dst, src in assignblk.iteritems(): - if dst != self.IRDst: - affs[dst] = src - assignblks.append(AssignBlock(affs, assignblk.instr)) - - assignblks += self.blocks[son].assignblks - new_block = IRBlock(block, assignblks) - - self.discard_edge(block, son) - - for lson in self.successors(son): - self.add_uniq_edge(block, lson) - self.discard_edge(son, lson) - del self.blocks[son] - self.del_node(son) - - self.blocks[block] = new_block - todo.add(block) - modified = True - return modified + def __init__(self, irdst, loc_db, blocks=None, *args, **kwargs): + warnings.warn('DEPRECATION WARNING: use "IRCFG" instead of "DiGraphIR"') + super(IRCFG, self).__init__(irdst, loc_db, blocks=None, *args, **kwargs) class IntermediateRepresentation(object): @@ -814,17 +707,17 @@ class IntermediateRepresentation(object): def new_ircfg(self, *args, **kwargs): """ - Return a new instance of DiGraphIR + Return a new instance of IRCFG """ - return DiGraphIR(self.IRDst, self.loc_db, *args, **kwargs) + return IRCFG(self.IRDst, self.loc_db, *args, **kwargs) def new_ircfg_from_asmcfg(self, asmcfg, *args, **kwargs): """ - Return a new instance of DiGraphIR from an @asmcfg + Return a new instance of IRCFG from an @asmcfg @asmcfg: AsmCFG instance """ - ircfg = DiGraphIR(self.IRDst, self.loc_db, *args, **kwargs) + ircfg = IRCFG(self.IRDst, self.loc_db, *args, **kwargs) for block in asmcfg.blocks: self.add_asmblock_to_ircfg(block, ircfg) return ircfg @@ -888,7 +781,7 @@ class IntermediateRepresentation(object): """ Add a native block to the current IR @block: native assembly block - @ircfg: DiGraphIR instance + @ircfg: IRCFG instance @gen_pc_updt: insert PC update effects between instructions """ diff --git a/test/ir/reduce_graph.py b/test/ir/reduce_graph.py new file mode 100644 index 00000000..d8b78c90 --- /dev/null +++ b/test/ir/reduce_graph.py @@ -0,0 +1,531 @@ +"""Regression test module for DependencyGraph""" +from pdb import pm + +from miasm2.expression.expression import ExprId, ExprInt, ExprAff, ExprCond, \ + ExprLoc, LocKey + +from miasm2.core.locationdb import LocationDB +from miasm2.ir.analysis import ira +from miasm2.ir.ir import IRBlock, AssignBlock, IRCFG +from miasm2.analysis.data_flow import merge_blocks + +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) + +IRDst = ExprId("IRDst", 32) +PC = ExprId("pc", 32) +SP = ExprId("sp", 32) + +CST0 = ExprInt(0x0, 32) +CST1 = ExprInt(0x1, 32) +CST2 = ExprInt(0x2, 32) +CST3 = ExprInt(0x3, 32) +CST22 = ExprInt(0x22, 32) +CST23 = ExprInt(0x23, 32) +CST24 = ExprInt(0x24, 32) +CST33 = ExprInt(0x33, 32) +CST35 = ExprInt(0x35, 32) +CST37 = ExprInt(0x37, 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) + + +class Regs(object): + + """Fake registers for tests """ + regs_init = {A: A_INIT, B: B_INIT, C: C_INIT, D: D_INIT} + all_regs_ids = [A, B, C, D, SP, PC, R] + + +class Arch(object): + + """Fake architecture for tests """ + regs = Regs() + + def getpc(self, attrib): + return PC + + def getsp(self, attrib): + return SP + + +class IRATest(ira): + + """Fake IRA class for tests""" + + def __init__(self, loc_db=None): + arch = Arch() + 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]) + + +def gen_irblock(label, exprs_list): + """ Returns an IRBlock. + Used only for tests purpose + """ + irs = [] + for exprs in exprs_list: + if isinstance(exprs, AssignBlock): + irs.append(exprs) + else: + irs.append(AssignBlock(exprs)) + + irbl = IRBlock(label, irs) + return irbl + + + + +############# Tests ############# +IRA = IRATest(loc_db) + + +########## G1 ########## +# Input +G1 = IRA.new_ircfg() + +G1_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(B, C), + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + +G1_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(IRDst, ExprLoc(LBL2, 32)), + ] + ] +) + +G1_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(A, B), + ExprAff(IRDst, C), + ] + ] +) + +for irb in [G1_IRB0, G1_IRB1, G1_IRB2]: + G1.add_irblock(irb) + +# Result +G1_RES = IRA.new_ircfg() + +G1_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(B, C), + ], + [ + ExprAff(A, B), + ExprAff(IRDst, C), + ] + + ] +) + + + +for irb in [G1_RES_IRB0]: + G1_RES.add_irblock(irb) + + + +def cmp_ir_graph(g1, g2): + assert g1.blocks.items() == g2.blocks.items() + assert set(g1.edges()) == set(g2.edges()) + + + +########## G2 ########## +# Input + +G2 = IRA.new_ircfg() + +G2_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + +G2_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(A, C), + ExprAff(IRDst, C), + ] + ] +) + +for irb in [G2_IRB0, G2_IRB1]: + G2.add_irblock(irb) + + +# Result +G2_RES = IRA.new_ircfg() + +G2_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(A, C), + ExprAff(IRDst, C), + ] + ] +) + + +for irb in [G2_RES_IRB0]: + G2_RES.add_irblock(irb) + + +########## G3 ########## +# Input + +G3 = IRA.new_ircfg() + +G3_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + +G3_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(A, C), + ExprAff(IRDst, ExprLoc(LBL2, 32)), + ] + ] +) + +G3_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, C), + ] + ] +) + + +for irb in [G3_IRB0, G3_IRB1, G3_IRB2]: + G3.add_irblock(irb) + + +# Result +G3_RES = IRA.new_ircfg() + +G3_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(A, C), + ], + [ + ExprAff(D, A), + ExprAff(IRDst, C), + ] + ] +) + + +for irb in [G3_RES_IRB0]: + G3_RES.add_irblock(irb) + + + + +########## G4 ########## +# Input + +G4 = IRA.new_ircfg() + +G4_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + +G4_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(A, C), + ExprAff(IRDst, ExprLoc(LBL2, 32)), + ] + ] +) + +G4_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + + +for irb in [G4_IRB0, G4_IRB1, G4_IRB2]: + G4.add_irblock(irb) + + +# Result +G4_RES = IRA.new_ircfg() + +G4_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(A, C), + ], + [ + ExprAff(D, A), + ExprAff(IRDst, ExprLoc(LBL0, 32)), + ] + ] +) + + +for irb in [G4_RES_IRB0 ]: + G4_RES.add_irblock(irb) + + + +########## G5 ########## +# Input + +G5 = IRA.new_ircfg() + +G5_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprLoc(LBL1, 32)), + ] + ] +) + +G5_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(A, C), + ExprAff(IRDst, ExprLoc(LBL2, 32)), + ] + ] +) + +G5_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, ExprCond(C, ExprLoc(LBL1, 32), ExprLoc(LBL3, 32))), + ] + ] +) + + +G5_IRB3 = gen_irblock( + LBL3, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, C), + ] + ] +) + + +for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3]: + G5.add_irblock(irb) + + +# Result +G5_RES = IRA.new_ircfg() + +G5_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(A, C), + ], + [ + ExprAff(D, A), + ExprAff(IRDst, ExprCond(C, ExprLoc(LBL0, 32), ExprLoc(LBL3, 32))), + ] + ] +) + + +G5_RES_IRB3 = gen_irblock( + LBL3, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, C), + ] + ] +) + +for irb in [G5_RES_IRB0, G5_RES_IRB3 ]: + G5_RES.add_irblock(irb) + + + +########## G6 ########## +# Input + +G6 = IRA.new_ircfg() + +G6_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprCond(C, ExprLoc(LBL1, 32), ExprLoc(LBL2, 32))), + ] + ] +) + +G6_IRB1 = gen_irblock( + LBL1, + [ + [ + ExprAff(IRDst, ExprLoc(LBL3, 32)), + ] + ] +) + +G6_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, D), + ] + ] +) + + +G6_IRB3 = gen_irblock( + LBL3, + [ + [ + ExprAff(A, D), + ExprAff(IRDst, ExprLoc(LBL3, 32)), + ] + ] +) + + +for irb in [G6_IRB0, G6_IRB1, G6_IRB2, G6_IRB3]: + G6.add_irblock(irb) + + +# Result +G6_RES = IRA.new_ircfg() + +G6_RES_IRB0 = gen_irblock( + LBL0, + [ + [ + ExprAff(IRDst, ExprCond(C, ExprLoc(LBL3, 32), ExprLoc(LBL2, 32))), + ] + ] +) + + +G6_RES_IRB2 = gen_irblock( + LBL2, + [ + [ + ExprAff(D, A), + ExprAff(IRDst, D), + ] + ] +) + + +G6_RES_IRB3 = gen_irblock( + LBL3, + [ + [ + ExprAff(A, D), + ExprAff(IRDst, ExprLoc(LBL3, 32)), + ] + ] +) + + +for irb in [G6_RES_IRB0, G6_RES_IRB2, G6_RES_IRB3 ]: + G6_RES.add_irblock(irb) + + + +################# Tests + + +for i, (g_test, g_ref) in enumerate( + [ + (G1, G1_RES), + (G2, G2_RES), + (G3, G3_RES), + (G4, G4_RES), + (G5, G5_RES), + (G6, G6_RES), + ], 1): + + heads = g_test.heads() + print '*'*10, 'Test', i, "*"*10 + open('test_in_%d.dot' % i, 'w').write(g_test.dot()) + merge_blocks(g_test, heads) + open('test_out_%d.dot' % i, 'w').write(g_test.dot()) + open('test_ref_%d.dot' % i, 'w').write(g_ref.dot()) + + cmp_ir_graph(g_test, g_ref) + print '\t', 'OK' diff --git a/test/test_all.py b/test/test_all.py index 1c521ab0..665fc3a5 100755 --- a/test/test_all.py +++ b/test/test_all.py @@ -266,6 +266,7 @@ testset += RegressionTest(["test_chandler.py"], base_dir="expr_type", ## IR for script in ["symbexec.py", "ir.py", + "reduce_graph.py" ]: testset += RegressionTest([script], base_dir="ir") |