miasm/analysis/simplifier.py

"""
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