# pylint:disable=too-many-boolean-expressions,consider-using-enumerate
from __future__ import annotations
from typing import Any, TYPE_CHECKING
from collections.abc import Container
from collections.abc import Iterable
from collections import defaultdict
from enum import Enum
import logging

import networkx

from angr.ailment import AILBlockRewriter, AILBlockViewer
from angr.ailment.block import Block
from angr.ailment.statement import (
    Statement,
    Assignment,
    Store,
    Call,
    ConditionalJump,
    DirtyStatement,
    WeakAssignment,
    Return,
)
from angr.ailment.expression import (
    Register,
    Convert,
    Load,
    StackBaseOffset,
    Expression,
    DirtyExpression,
    VEXCCallExpression,
    Tmp,
    Const,
    BinaryOp,
    VirtualVariable,
    UnaryOp,
)

from angr.analyses.s_propagator import SPropagatorAnalysis
from angr.analyses.s_reaching_definitions import SRDAModel, SReachingDefinitionsAnalysis
from angr.utils.ail import is_phi_assignment, HasExprWalker, is_expr_used_as_reg_base_value
from angr.utils.ssa import (
    has_call_in_between_stmts,
    has_store_stmt_in_between_stmts,
    has_load_expr_in_between_stmts,
    is_vvar_eliminatable,
)
from angr.code_location import AILCodeLocation
from angr.sim_variable import SimStackVariable, SimMemoryVariable, SimVariable
from angr.knowledge_plugins.propagations.states import Equivalence
from angr.knowledge_plugins.key_definitions import atoms
from angr.knowledge_plugins.key_definitions.definition import Definition
from angr.knowledge_plugins.key_definitions.constants import OP_BEFORE
from angr.errors import AngrRuntimeError
from angr.analyses import Analysis, AnalysesHub
from angr.utils.timing import timethis
from .ailgraph_walker import AILGraphWalker
from .expression_narrower import ExprNarrowingInfo, NarrowingInfoExtractor, ExpressionNarrower
from .block_simplifier import BlockSimplifier
from .ccall_rewriters import CCALL_REWRITERS
from .dirty_rewriters import DIRTY_REWRITERS
from .counters.expression_counters import SingleExpressionCounter

if TYPE_CHECKING:
    from angr.ailment.manager import Manager


_l = logging.getLogger(__name__)


class HasCallNotification(Exception):
    """
    Notifies the existence of a call statement.
    """


class HasVVarNotification(Exception):
    """
    Notifies the existence of a VirtualVariable.
    """


class HasRefVVarNotification(Exception):
    """
    Notifies the existence of a reference to a VirtualVariable.
    """


class AILBlockTempCollector(AILBlockViewer):
    """
    Collects any temporaries used in a block.
    """

    def __init__(self, **kwargs):
        super().__init__(**kwargs)
        self.temps = set()
        self.expr_handlers[Tmp] = self._handle_Tmp

    # pylint:disable=unused-argument
    def _handle_Tmp(self, expr_idx: int, expr: Expression, stmt_idx: int, stmt: Statement | None, block):
        if isinstance(expr, Tmp):
            self.temps.add(expr)


class DefEqRelation(Enum):
    """
    Describes the location relationship between a virtual variable definition and the equivalence statement.
    """

    UNKNOWN = 0
    DEF_IS_FUNCARG = 1
    DEF_EQ_SAME_BLOCK = 2
    DEF_IN_EQ_PRED_BLOCK = 3


class PartialConstantExprRewriter(AILBlockRewriter):
    """
    Rewrites expressions whose high bits are definitely zero to constants (if possible) or mask them with masks
    properly.
    """

    def __init__(self, varid: int, zero_high_bits: int):
        super().__init__(update_block=False)
        self.varid = varid
        self.zero_high_bits = zero_high_bits

    def _handle_BinaryOp(  # type:ignore
        self, expr_idx: int, expr: BinaryOp, stmt_idx: int, stmt: Statement, block: Block | None
    ):
        if (
            expr.op == "And"
            and isinstance(expr.operands[0], VirtualVariable)
            and expr.operands[0].varid == self.varid
            and isinstance(expr.operands[1], Const)
            and expr.operands[1].is_int
        ):
            vvar = expr.operands[0]
            mask_expr = expr.operands[1]
            mask = mask_expr.value
            assert isinstance(mask, int)
            # high_bits_mask[vvar.bits - 1:vvar.bits - self.zero_high_bits] == 0
            high_bits_mask = ((1 << vvar.bits) - 1) ^ ((1 << (vvar.bits - self.zero_high_bits)) - 1)
            high_bits_mask &= mask  # in case high bits of mask are zero
            new_mask = mask ^ high_bits_mask
            if new_mask == mask:
                return expr
            if new_mask == 0:
                return Const(expr_idx, None, 0, expr.bits, **expr.tags)
            new_mask_expr = Const(mask_expr.idx, mask_expr.variable, new_mask, mask_expr.bits, **mask_expr.tags)
            return BinaryOp(expr_idx, expr.op, [vvar, new_mask_expr], bits=expr.bits, **expr.tags)
        return super()._handle_BinaryOp(expr_idx, expr, stmt_idx, stmt, block)


class AILSimplifier(Analysis):
    """
    Perform function-level simplifications.
    """

    def __init__(
        self,
        func,
        func_graph=None,
        remove_dead_memdefs=False,
        stack_arg_offsets: set[tuple[int, int]] | None = None,
        unify_variables=False,
        ail_manager: Manager | None = None,
        gp: int | None = None,
        narrow_expressions=False,
        only_consts=False,
        fold_callexprs_into_conditions=False,
        use_callee_saved_regs_at_return=True,
        rewrite_ccalls=True,
        rename_ccalls=True,
        rewrite_dirty=True,
        removed_vvar_ids: set[int] | None = None,
        arg_vvars: dict[int, tuple[VirtualVariable, SimVariable]] | None = None,
        avoid_vvar_ids: set[int] | None = None,
        secondary_stackvars: set[int] | None = None,
    ):
        self.func = func
        self.func_graph = func_graph if func_graph is not None else func.graph
        self._reaching_definitions: SRDAModel | None = None
        self._propagator: SPropagatorAnalysis | None = None

        self._remove_dead_memdefs = remove_dead_memdefs
        self._stack_arg_offsets = stack_arg_offsets
        self._unify_vars = unify_variables
        self._ail_manager: Manager | None = ail_manager
        self._gp = gp
        self._narrow_expressions = narrow_expressions
        self._only_consts = only_consts
        self._fold_callexprs_into_conditions = fold_callexprs_into_conditions
        self._use_callee_saved_regs_at_return = use_callee_saved_regs_at_return
        self._should_rewrite_ccalls = rewrite_ccalls
        self._should_rename_ccalls = rename_ccalls
        self._should_rewrite_dirty = rewrite_dirty
        self._removed_vvar_ids = removed_vvar_ids if removed_vvar_ids is not None else set()
        self._arg_vvars = arg_vvars
        self._avoid_vvar_ids = avoid_vvar_ids if avoid_vvar_ids is not None else set()
        self._propagator_dead_vvar_ids: set[int] = set()
        self._secondary_stackvars: set[int] = secondary_stackvars if secondary_stackvars is not None else set()

        self._calls_to_remove: set[AILCodeLocation] = set()
        self._assignments_to_remove: set[AILCodeLocation] = set()
        self.blocks = {}  # Mapping nodes to simplified blocks

        self.simplified: bool = False
        self._simplify()

    def _simplify(self):
        if self._narrow_expressions:
            _l.debug("Removing dead assignments before narrowing expressions")
            r = self._iteratively_remove_dead_assignments()
            if r:
                _l.debug("... dead assignments removed")
                self.simplified = True

            _l.debug("Narrowing expressions")
            narrowed_exprs = self._narrow_exprs()
            self.simplified |= narrowed_exprs
            if narrowed_exprs:
                _l.debug("... expressions narrowed")
                self._rebuild_func_graph()
                self._clear_cache()

        _l.debug("Folding expressions")
        folded_exprs = self._fold_exprs()
        self.simplified |= folded_exprs
        if folded_exprs:
            _l.debug("... expressions folded")
            self._rebuild_func_graph()
            # reaching definition analysis results are no longer reliable
            self._clear_cache()

        _l.debug("Propagating partial-constant expressions")
        pconst_propagated = self._propagate_partial_constant_exprs()
        self.simplified |= pconst_propagated
        if pconst_propagated:
            _l.debug("... partial-constant expressions propagated")
            self._rebuild_func_graph()
            # reaching definition analysis results are no longer reliable
            self._clear_cache()

        _l.debug("Rewriting constant expressions with phi variables")
        phi_const_rewritten = self._rewrite_phi_const_exprs()
        self.simplified |= phi_const_rewritten
        if phi_const_rewritten:
            _l.debug("... constant expressions with phi variables rewritten")
            self._rebuild_func_graph()
            # reaching definition analysis results are no longer reliable
            self._clear_cache()

        if self._only_consts:
            return

        _l.debug("Removing dead assignments")
        r = self._iteratively_remove_dead_assignments()
        if r:
            _l.debug("... dead assignments removed")
            self.simplified = True

        if self._should_rewrite_ccalls:
            _l.debug("Rewriting ccalls")
            ccalls_rewritten = self._rewrite_ccalls()
            self.simplified |= ccalls_rewritten
            if ccalls_rewritten:
                _l.debug("... ccalls rewritten")
                self._rebuild_func_graph()
                self._clear_cache()

        if self._should_rewrite_dirty:
            _l.debug("Rewriting dirty expressions/statements")
            dirty_rewritten = self._rewrite_dirty_calls()
            self.simplified |= dirty_rewritten
            if dirty_rewritten:
                _l.debug("... dirty expressions/statements rewritten")
                self._rebuild_func_graph()
                self._clear_cache()

        if self._unify_vars:
            _l.debug("Removing dead assignments")
            r = self._iteratively_remove_dead_assignments()
            if r:
                _l.debug("... dead assignments removed")
                self.simplified = True

            _l.debug("Unifying local variables")
            r = self._unify_local_variables()
            if r:
                _l.debug("... local variables unified")
                self.simplified = True
                self._rebuild_func_graph()

            # _fold_call_exprs() may set self._calls_to_remove, which will be honored in _remove_dead_assignments()
            _l.debug("Folding call expressions")
            r = self._fold_call_exprs()
            if r:
                _l.debug("... call expressions folded")
                self.simplified = True
                self._rebuild_func_graph()
                self._clear_cache()

        _l.debug("Removing dead assignments")
        r = self._iteratively_remove_dead_assignments()
        if r:
            _l.debug("... dead assignments removed")
            self.simplified = True

    def _rebuild_func_graph(self):
        def _handler(node):
            return self.blocks.get(node, None)

        AILGraphWalker(self.func_graph, _handler, replace_nodes=True).walk()
        self.blocks = {}

    def _compute_reaching_definitions(self) -> SRDAModel:
        # Computing reaching definitions or return the cached one
        if self._reaching_definitions is not None:
            return self._reaching_definitions
        func_args = {vvar for vvar, _ in self._arg_vvars.values()} if self._arg_vvars else set()
        rd = (
            self.project.analyses[SReachingDefinitionsAnalysis]
            .prep()(
                subject=self.func,
                func_graph=self.func_graph,
                func_args=func_args,
                use_callee_saved_regs_at_return=self._use_callee_saved_regs_at_return,
                # track_tmps=True,
            )
            .model
        )
        self._reaching_definitions = rd
        return rd

    @timethis
    def _compute_propagation(self) -> SPropagatorAnalysis:
        # Propagate expressions or return the existing result
        if self._propagator is not None:
            return self._propagator
        func_args = {vvar for vvar, _ in self._arg_vvars.values()} if self._arg_vvars else set()
        prop = self.project.analyses[SPropagatorAnalysis].prep(fail_fast=self._fail_fast)(
            subject=self.func,
            func_graph=self.func_graph,
            func_args=func_args,
            # gp=self._gp,
            only_consts=self._only_consts,
        )
        self._propagator = prop
        self._propagator_dead_vvar_ids = prop.dead_vvar_ids
        return prop

    @timethis
    def _compute_equivalence(self) -> set[Equivalence]:
        equivalence = set()
        for block in self.func_graph:
            for stmt_idx, stmt in enumerate(block.statements):
                if isinstance(stmt, Assignment):
                    if isinstance(stmt.dst, VirtualVariable) and isinstance(
                        stmt.src, (VirtualVariable, Tmp, Call, Convert)
                    ):
                        codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                        equivalence.add(Equivalence(codeloc, stmt.dst, stmt.src))
                elif isinstance(stmt, WeakAssignment):
                    codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                    equivalence.add(Equivalence(codeloc, stmt.dst, stmt.src, is_weakassignment=True))
                elif isinstance(stmt, Call):
                    if isinstance(stmt.ret_expr, (VirtualVariable, Load)):
                        codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                        equivalence.add(Equivalence(codeloc, stmt.ret_expr, stmt))
                    elif isinstance(stmt.fp_ret_expr, (VirtualVariable, Load)):
                        codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                        equivalence.add(Equivalence(codeloc, stmt.fp_ret_expr, stmt))
                elif (
                    isinstance(stmt, Store)
                    and isinstance(stmt.size, int)
                    and isinstance(stmt.data, (VirtualVariable, Tmp, Call, Convert))
                ):
                    if isinstance(stmt.addr, StackBaseOffset) and isinstance(stmt.addr.offset, int):
                        # stack variable
                        atom = SimStackVariable(stmt.addr.offset, stmt.size)
                        codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                        equivalence.add(Equivalence(codeloc, atom, stmt.data))
                    elif isinstance(stmt.addr, Const):
                        # global variable
                        atom = SimMemoryVariable(stmt.addr.value, stmt.size)
                        codeloc = AILCodeLocation(block.addr, block.idx, stmt_idx, stmt.tags.get("ins_addr"))
                        equivalence.add(Equivalence(codeloc, atom, stmt.data))
        return equivalence

    def _clear_cache(self) -> None:
        self._propagator = None
        self._reaching_definitions = None

    def _clear_propagator_cache(self) -> None:
        self._propagator = None

    def _clear_reaching_definitions_cache(self) -> None:
        self._reaching_definitions = None

    #
    # Expression narrowing
    #

    @timethis
    def _narrow_exprs(self) -> bool:
        """
        A register may be used with full width even when only the lower bytes are really needed. This results in the
        incorrect determination of wider variables while the actual variable is narrower (e.g., int64 vs char). This
        optimization narrows a register definition if all its uses are narrower than the definition itself.

        Note that at this point, we must account for all uses of any narrowed expressions. This means expression
        narrowing must be done _after_ making call sites instead of before making call sites.
        """

        narrowed = False

        addr_and_idx_to_block: dict[tuple[int, int | None], Block] = {}
        for block in self.func_graph.nodes():
            addr_and_idx_to_block[(block.addr, block.idx)] = block

        rd = self._compute_reaching_definitions()
        sorted_defs = sorted(rd.all_definitions, key=lambda d: d.codeloc, reverse=True)

        # compute effective sizes for each vvar
        effective_sizes = self._compute_effective_sizes(rd, sorted_defs, addr_and_idx_to_block)

        narrowing_candidates: dict[int, tuple[Definition, ExprNarrowingInfo]] = {}
        for def_ in sorted_defs:
            if isinstance(def_.atom, atoms.VirtualVariable) and (def_.atom.was_reg or def_.atom.was_parameter):
                # only do this for general purpose register
                skip_def = False
                reg = None
                for reg in self.project.arch.register_list:
                    if reg.vex_offset == def_.atom.reg_offset:
                        if not reg.artificial and not reg.general_purpose and not reg.vector:
                            skip_def = True
                        break

                if skip_def:
                    continue

                narrow = self._narrowing_needed(def_, rd, addr_and_idx_to_block, effective_sizes)
                if narrow.narrowable:
                    # we cannot narrow it immediately because any definition that is used by phi variables must be
                    # narrowed together with all other definitions that can reach the phi variables.
                    # so we record the information and decide if we are going to narrow these expressions or not at the
                    # end of the loop.
                    narrowing_candidates[def_.atom.varid] = def_, narrow

        # first, determine which phi vars need to be narrowed and can be narrowed.
        # a phi var can only be narrowed if all its source vvars are narrowable
        vvar_to_narrowing_size = {}
        for def_varid, (_, narrow_info) in narrowing_candidates.items():
            vvar_to_narrowing_size[def_varid] = narrow_info.to_size

        blacklist_varids = set()
        while True:
            repeat, narrowables = self._compute_narrowables_once(
                rd, narrowing_candidates, vvar_to_narrowing_size, blacklist_varids
            )
            if not repeat:
                break

        if not narrowables:
            # nothing to narrow
            return False

        # let's narrow them (finally)
        narrower = ExpressionNarrower(self.project, rd, narrowables, addr_and_idx_to_block, self.blocks)
        for old_block in addr_and_idx_to_block.values():
            new_block = self.blocks.get(old_block, old_block)
            new_block = narrower.walk(new_block)
            if narrower.narrowed_any:
                narrowed = True
                self.blocks[old_block] = new_block

        # update self._arg_vvars if necessary
        for new_vvars in narrower.replacement_core_vvars.values():
            for new_vvar in new_vvars:
                if new_vvar.was_parameter and self._arg_vvars:
                    for func_arg_idx in list(self._arg_vvars):
                        vvar, simvar = self._arg_vvars[func_arg_idx]
                        if vvar.varid == new_vvar.varid:
                            simvar_new = simvar.copy()
                            simvar_new._hash = None
                            simvar_new.size = new_vvar.size
                            self._arg_vvars[func_arg_idx] = new_vvar, simvar_new

        return narrowed

    def _compute_effective_sizes(self, rd, defs, addr_and_idx_to_block) -> dict[int, int]:

        vvar_effective_sizes: dict[int, int] = {}

        # determine effective sizes for non-phi vvars
        for def_ in defs:
            # find its def statement
            old_block = addr_and_idx_to_block.get((def_.codeloc.block_addr, def_.codeloc.block_idx), None)
            if old_block is None:
                continue
            block = self.blocks.get(old_block, old_block)
            if def_.codeloc.stmt_idx is None or def_.codeloc.stmt_idx >= len(block.statements):
                continue
            def_stmt = block.statements[def_.codeloc.stmt_idx]
            if (
                isinstance(def_stmt, Assignment)
                and isinstance(def_stmt.src, Convert)
                and not def_stmt.src.is_signed
                and def_stmt.src.from_type == Convert.TYPE_INT
                and def_stmt.src.to_type == Convert.TYPE_INT
                and def_stmt.src.from_bits < def_stmt.src.to_bits
            ):
                effective_size = def_stmt.src.from_bits // self.project.arch.byte_width
                vvar_effective_sizes[def_.atom.varid] = effective_size

        # update effective sizes for phi vvars
        changed = True
        while changed:
            changed = False
            for phi_vvar in rd.phivarid_to_varids:
                if phi_vvar in vvar_effective_sizes:
                    continue
                if rd.phivarid_to_varids[phi_vvar] and all(
                    src_vvar in vvar_effective_sizes for src_vvar in rd.phivarid_to_varids[phi_vvar]
                ):
                    effective_size = max(vvar_effective_sizes[src_vvar] for src_vvar in rd.phivarid_to_varids[phi_vvar])
                    vvar_effective_sizes[phi_vvar] = effective_size
                    changed = True

        return vvar_effective_sizes

    @staticmethod
    def _compute_narrowables_once(
        rd, narrowing_candidates: dict, vvar_to_narrowing_size: dict[int, int], blacklist_varids: set
    ):
        repeat = False
        narrowable_phivarids = set()
        for def_vvarid in narrowing_candidates:
            if def_vvarid in blacklist_varids:
                continue
            if def_vvarid in rd.phi_vvar_ids:
                narrowing_sizes = set()
                src_vvarids = rd.phivarid_to_varids[def_vvarid]
                for vvarid in src_vvarids:
                    if vvarid in blacklist_varids:
                        narrowing_sizes.add(None)
                    else:
                        narrowing_sizes.add(vvar_to_narrowing_size.get(vvarid))
                if len(narrowing_sizes) == 1 and None not in narrowing_sizes:
                    # we can narrow this phi vvar!
                    narrowable_phivarids.add(def_vvarid)
                else:
                    # blacklist it for now
                    blacklist_varids.add(def_vvarid)

        # now determine what to narrow!
        narrowables = []

        for def_, narrow_info in narrowing_candidates.values():
            if def_.atom.varid in blacklist_varids:
                continue
            if not narrow_info.phi_vars:
                # not used by any other phi variables. good!
                narrowables.append((def_, narrow_info))
            else:
                if {phivar.varid for phivar in narrow_info.phi_vars}.issubset(narrowable_phivarids):
                    # all phi vvars that use this definition can be narrowed
                    narrowables.append((def_, narrow_info))
                else:
                    # this vvar cannot be narrowed
                    # note that all phi variables that relies on this vvar also cannot be narrowed! we must analyze
                    # again
                    repeat = True
                    blacklist_varids.add(def_.atom.varid)
                    blacklist_varids |= {phivar.varid for phivar in narrow_info.phi_vars}

        return repeat, narrowables

    def _narrowing_needed(
        self, def_: Definition, rd: SRDAModel, addr_and_idx_to_block, effective_sizes: dict[int, int]
    ) -> ExprNarrowingInfo:

        def_size = def_.size
        # find its uses
        # some use locations are phi assignments. we keep tracking the uses of phi variables and update the dictionary
        result = self._get_vvar_use_and_exprs_recursive(def_.atom, rd, addr_and_idx_to_block)
        if result is None:
            return ExprNarrowingInfo(False)
        use_and_exprs, phi_vars = result

        all_used_sizes = set()
        noncall_used_sizes = set()
        used_by: list[tuple[atoms.VirtualVariable, AILCodeLocation, tuple[str, tuple[Expression, ...]]]] = []
        used_by_loc = defaultdict(list)

        for atom, loc, expr in use_and_exprs:
            old_block = addr_and_idx_to_block.get((loc.block_addr, loc.block_idx), None)
            if old_block is None:
                # missing a block for whatever reason
                return ExprNarrowingInfo(False)

            block = self.blocks.get(old_block, old_block)
            assert loc.stmt_idx is not None
            if loc.stmt_idx >= len(block.statements):
                # missing a statement for whatever reason
                return ExprNarrowingInfo(False)
            stmt = block.statements[loc.stmt_idx]

            # special case: if the statement is a Call statement and expr is None, it means we have not been able to
            # determine if the expression is really used by the call or not. skip it in this case
            if isinstance(stmt, Call) and expr is None:
                all_used_sizes.add(atom.size)
                continue
            # special case: if the statement is a phi statement, we ignore it
            if is_phi_assignment(stmt):
                continue
            # special case: if the statement is an assignment to a destination vvar A, and the source is the bitwise-or
            # of two expressions where one of them is the high bits of expr, and expr is a phi var that relies on
            # vvar A, then we skip it.
            if is_expr_used_as_reg_base_value(stmt, expr, rd):
                continue

            expr_size, used_by_exprs = self._extract_expression_effective_size(stmt, expr)
            if expr_size is None:
                # it's probably used in full width
                return ExprNarrowingInfo(False)

            all_used_sizes.add(expr_size)
            if not isinstance(stmt, Call):
                noncall_used_sizes.add(expr_size)
            used_by_loc[loc].append((atom, used_by_exprs))

        target_size = None
        if len(all_used_sizes) >= 1 and max(all_used_sizes) < def_size:
            target_size = max(all_used_sizes)
        else:
            effective_size = effective_sizes.get(def_.atom.varid, None)
            if (
                effective_size is not None
                and any(used_size <= effective_size for used_size in all_used_sizes)
                and all(used_size <= effective_size for used_size in noncall_used_sizes)
            ):
                # special case: sometimes we have an explicit Convert that narrows the value, all other uses are either
                # in the effective size or narrower, but we pass the full register to a function call as an argument
                # because we do not know the real type of the argument, or there are cases like putchar(int ch) while
                # ch is actually a char. We use effective size in such cases to narrow the variable.
                target_size = effective_size

        if target_size is not None:
            for loc, atom_expr_pairs in used_by_loc.items():
                if len(atom_expr_pairs) == 1:
                    atom, used_by_exprs = atom_expr_pairs[0]
                    used_by.append((atom, loc, used_by_exprs))
                else:
                    # the order matters - we must replace the outer expressions first, then replace the inner
                    # expressions. replacing in the wrong order will lead to expressions that are not replaced in the
                    # end.
                    ordered = []
                    for atom, used_by_exprs in atom_expr_pairs:
                        last_inclusion = len(ordered) - 1  # by default we append at the end of the list
                        for idx in range(len(ordered)):
                            if self._is_expr0_included_in_expr1(ordered[idx][1], used_by_exprs):
                                # this element must be inserted before idx
                                ordered.insert(idx, (atom, used_by_exprs))
                                break
                            if self._is_expr0_included_in_expr1(used_by_exprs, ordered[idx][1]):
                                # this element can be inserted after this element. record the index
                                last_inclusion = idx
                        else:
                            ordered.insert(last_inclusion + 1, (atom, used_by_exprs))

                    for atom, used_by_exprs in ordered:
                        used_by.append((atom, loc, used_by_exprs))

            return ExprNarrowingInfo(True, to_size=target_size, use_exprs=used_by, phi_vars=phi_vars)

        return ExprNarrowingInfo(False)

    @staticmethod
    def _exprs_from_used_by_exprs(used_by_exprs) -> set[Expression]:
        use_type, expr_tuple = used_by_exprs
        match use_type:
            case "expr" | "mask" | "convert":
                return {expr_tuple[1]} if len(expr_tuple) == 2 else {expr_tuple[0]}
            case "phi-src-expr":
                return {expr_tuple[0]}
            case "binop-convert":
                return {expr_tuple[0], expr_tuple[1]}
            case _:
                return set()

    def _is_expr0_included_in_expr1(self, used_by_exprs0, used_by_exprs1) -> bool:
        # extract expressions
        exprs0 = self._exprs_from_used_by_exprs(used_by_exprs0)
        exprs1 = self._exprs_from_used_by_exprs(used_by_exprs1)

        # test for inclusion
        for expr1 in exprs1:
            walker = HasExprWalker(exprs0)
            walker.walk_expression(expr1)
            if walker.contains_exprs:
                return True
        return False

    def _get_vvar_use_and_exprs_recursive(
        self, initial_atom: atoms.VirtualVariable, rd, block_dict: dict[tuple[int, int | None], Block]
    ) -> tuple[list[tuple[atoms.VirtualVariable, AILCodeLocation, Expression]], set[VirtualVariable]] | None:
        result = []
        atom_queue = [initial_atom]
        phi_vars = set()
        seen = set()
        while atom_queue:
            atom = atom_queue.pop(0)
            seen.add(atom)

            expr_and_uses = rd.all_vvar_uses[atom.varid]

            for expr, loc in set(expr_and_uses):
                old_block = block_dict.get((loc.block_addr, loc.block_idx), None)
                if old_block is None:
                    # missing a block for whatever reason
                    return None

                block: Block = self.blocks.get(old_block, old_block)
                if loc.stmt_idx >= len(block.statements):
                    # missing a statement for whatever reason
                    return None
                stmt = block.statements[loc.stmt_idx]

                if is_phi_assignment(stmt):
                    phi_vars.add(stmt.dst)
                    new_atom = atoms.VirtualVariable(
                        stmt.dst.varid, stmt.dst.size, stmt.dst.category, oident=stmt.dst.oident
                    )
                    if new_atom not in seen:
                        atom_queue.append(new_atom)
                        seen.add(new_atom)
                else:
                    result.append((atom, loc, expr))
        return result, phi_vars

    def _extract_expression_effective_size(
        self, statement, expr
    ) -> tuple[int | None, tuple[str, tuple[Expression, ...]] | None]:
        """
        Determine the effective size of an expression when it's used.
        """

        walker = NarrowingInfoExtractor(expr)
        walker.walk_statement(statement)
        if not walker.operations:
            if expr is None:
                return None, None
            return expr.size, ("expr", (expr,))

        ops = walker.operations
        first_op = ops[0]
        if isinstance(first_op, BinaryOp) and first_op.op in {"Add", "Sub"}:
            # expr + x
            ops = ops[1:]
            if not ops:
                if expr is None:
                    return None, None
                return expr.size, ("expr", (expr,))
            first_op = ops[0]
        if isinstance(first_op, Convert) and first_op.to_bits >= self.project.arch.byte_width:
            # we need at least one byte!
            if (
