diff options
Diffstat (limited to 'miasm/analysis/simplifier.py')
| -rw-r--r-- | miasm/analysis/simplifier.py | 325 |
1 files changed, 0 insertions, 325 deletions
diff --git a/miasm/analysis/simplifier.py b/miasm/analysis/simplifier.py deleted file mode 100644 index a7c29b06..00000000 --- a/miasm/analysis/simplifier.py +++ /dev/null @@ -1,325 +0,0 @@ -""" -Apply simplification passes to an IR cfg -""" - -import logging -import warnings -from functools import wraps -from miasm.analysis.ssa import SSADiGraph -from miasm.analysis.outofssa import UnSSADiGraph -from miasm.analysis.data_flow import DiGraphLivenessSSA -from miasm.expression.simplifications import expr_simp -from miasm.ir.ir import AssignBlock, IRBlock -from miasm.analysis.data_flow import DeadRemoval, \ - merge_blocks, remove_empty_assignblks, \ - del_unused_edges, \ - PropagateExpressions, DelDummyPhi - - -log = logging.getLogger("simplifier") -console_handler = logging.StreamHandler() -console_handler.setFormatter(logging.Formatter("[%(levelname)-8s]: %(message)s")) -log.addHandler(console_handler) -log.setLevel(logging.WARNING) - - -def fix_point(func): - @wraps(func) - def ret_func(self, ircfg, head): - log.debug('[%s]: start', func.__name__) - has_been_modified = False - modified = True - while modified: - modified = func(self, ircfg, head) - has_been_modified |= modified - log.debug( - '[%s]: stop %r', - func.__name__, - has_been_modified - ) - return has_been_modified - return ret_func - - -class IRCFGSimplifier(object): - """ - Simplify an IRCFG - This class applies passes until reaching a fix point - """ - - def __init__(self, lifter): - self.lifter = lifter - self.init_passes() - - @property - def ir_arch(self): - warnings.warn('DEPRECATION WARNING: use ".lifter" instead of ".ir_arch"') - return self.lifter - - def init_passes(self): - """ - Init the array of simplification passes - """ - self.passes = [] - - @fix_point - def simplify(self, ircfg, head): - """ - Apply passes until reaching a fix point - Return True if the graph has been modified - - @ircfg: IRCFG instance to simplify - @head: Location instance of the ircfg head - """ - modified = False - for simplify_pass in self.passes: - modified |= simplify_pass(ircfg, head) - return modified - - def __call__(self, ircfg, head): - return self.simplify(ircfg, head) - - -class IRCFGSimplifierCommon(IRCFGSimplifier): - """ - Simplify an IRCFG - This class applies following passes until reaching a fix point: - - simplify_ircfg - - do_dead_simp_ircfg - """ - def __init__(self, lifter, expr_simp=expr_simp): - self.expr_simp = expr_simp - super(IRCFGSimplifierCommon, self).__init__(lifter) - self.deadremoval = DeadRemoval(self.lifter) - - def init_passes(self): - self.passes = [ - self.simplify_ircfg, - self.do_dead_simp_ircfg, - ] - - @fix_point - def simplify_ircfg(self, ircfg, _head): - """ - Apply self.expr_simp on the @ircfg until reaching fix point - Return True if the graph has been modified - - @ircfg: IRCFG instance to simplify - """ - modified = ircfg.simplify(self.expr_simp) - return modified - - @fix_point - def do_dead_simp_ircfg(self, ircfg, head): - """ - Apply: - - dead_simp - - remove_empty_assignblks - - merge_blocks - on the @ircfg until reaching fix point - Return True if the graph has been modified - - @ircfg: IRCFG instance to simplify - @head: Location instance of the ircfg head - """ - modified = self.deadremoval(ircfg) - modified |= remove_empty_assignblks(ircfg) - modified |= merge_blocks(ircfg, set([head])) - return modified - - -class IRCFGSimplifierSSA(IRCFGSimplifierCommon): - """ - Simplify an IRCFG. - The IRCF is first transformed in SSA, then apply transformations passes - and apply out-of-ssa. Final passes of IRcfgSimplifier are applied - - This class apply following pass until reaching a fix point: - - do_propagate_expressions - - do_dead_simp_ssa - """ - - def __init__(self, lifter, expr_simp=expr_simp): - super(IRCFGSimplifierSSA, self).__init__(lifter, expr_simp) - - self.lifter.ssa_var = {} - self.all_ssa_vars = {} - - self.ssa_forbidden_regs = self.get_forbidden_regs() - - self.propag_expressions = PropagateExpressions() - self.del_dummy_phi = DelDummyPhi() - - self.deadremoval = DeadRemoval(self.lifter, self.all_ssa_vars) - - def get_forbidden_regs(self): - """ - Return a set of immutable register during SSA transformation - """ - regs = set( - [ - self.lifter.pc, - self.lifter.IRDst, - self.lifter.arch.regs.exception_flags - ] - ) - return regs - - def init_passes(self): - """ - Init the array of simplification passes - """ - self.passes = [ - self.simplify_ssa, - self.do_propagate_expressions, - self.do_del_dummy_phi, - self.do_dead_simp_ssa, - self.do_remove_empty_assignblks, - self.do_del_unused_edges, - self.do_merge_blocks, - ] - - - - def ircfg_to_ssa(self, ircfg, head): - """ - Apply the SSA transformation to @ircfg using it's @head - - @ircfg: IRCFG instance to simplify - @head: Location instance of the ircfg head - """ - ssa = SSADiGraph(ircfg) - ssa.immutable_ids.update(self.ssa_forbidden_regs) - ssa.ssa_variable_to_expr.update(self.all_ssa_vars) - ssa.transform(head) - self.all_ssa_vars.update(ssa.ssa_variable_to_expr) - self.lifter.ssa_var.update(ssa.ssa_variable_to_expr) - return ssa - - def ssa_to_unssa(self, ssa, head): - """ - Apply the out-of-ssa transformation to @ssa using it's @head - - @ssa: SSADiGraph instance - @head: Location instance of the graph head - """ - cfg_liveness = DiGraphLivenessSSA(ssa.graph) - cfg_liveness.init_var_info(self.lifter) - cfg_liveness.compute_liveness() - - UnSSADiGraph(ssa, head, cfg_liveness) - return ssa.graph - - @fix_point - def simplify_ssa(self, ssa, _head): - """ - Apply self.expr_simp on the @ssa.graph until reaching fix point - Return True if the graph has been modified - - @ssa: SSADiGraph instance - """ - modified = ssa.graph.simplify(self.expr_simp) - return modified - - @fix_point - def do_del_unused_edges(self, ssa, head): - """ - Del unused edges of the ssa graph - @head: Location instance of the graph head - """ - modified = del_unused_edges(ssa.graph, set([head])) - return modified - - def do_propagate_expressions(self, ssa, head): - """ - Expressions propagation through ExprId in the @ssa graph - @head: Location instance of the graph head - """ - modified = self.propag_expressions.propagate(ssa, head) - return modified - - @fix_point - def do_del_dummy_phi(self, ssa, head): - """ - Del dummy phi - @head: Location instance of the graph head - """ - modified = self.del_dummy_phi.del_dummy_phi(ssa, head) - return modified - - @fix_point - def do_remove_empty_assignblks(self, ssa, head): - """ - Remove empty assignblks - @head: Location instance of the graph head - """ - modified = remove_empty_assignblks(ssa.graph) - return modified - - @fix_point - def do_merge_blocks(self, ssa, head): - """ - Merge blocks with one parent/son - @head: Location instance of the graph head - """ - modified = merge_blocks(ssa.graph, set([head])) - return modified - - @fix_point - def do_dead_simp_ssa(self, ssa, head): - """ - Apply: - - deadrm - - remove_empty_assignblks - - del_unused_edges - - merge_blocks - on the @ircfg until reaching fix point - Return True if the graph has been modified - - @ircfg: IRCFG instance to simplify - @head: Location instance of the ircfg head - """ - modified = self.deadremoval(ssa.graph) - return modified - - def do_simplify(self, ssa, head): - """ - Apply passes until reaching a fix point - Return True if the graph has been modified - """ - return super(IRCFGSimplifierSSA, self).simplify(ssa, head) - - def do_simplify_loop(self, ssa, head): - """ - Apply do_simplify until reaching a fix point - SSA is updated between each do_simplify - Return True if the graph has been modified - """ - modified = True - while modified: - modified = self.do_simplify(ssa, head) - # Update ssa structs - ssa = self.ircfg_to_ssa(ssa.graph, head) - return ssa - - def simplify(self, ircfg, head): - """ - Add access to "abi out regs" in each leaf block - Apply SSA transformation to @ircfg - Apply passes until reaching a fix point - Apply out-of-ssa transformation - Apply post simplification passes - - Updated simplified IRCFG instance and return it - - @ircfg: IRCFG instance to simplify - @head: Location instance of the ircfg head - """ - - ssa = self.ircfg_to_ssa(ircfg, head) - ssa = self.do_simplify_loop(ssa, head) - ircfg = self.ssa_to_unssa(ssa, head) - ircfg_simplifier = IRCFGSimplifierCommon(self.lifter) - ircfg_simplifier.deadremoval.add_expr_to_original_expr(self.all_ssa_vars) - ircfg_simplifier.simplify(ircfg, head) - return ircfg |