GitCorner

Code

ossartcraftcraftanything๐ŸŒ
642d5a256791
//! A small, honest pseudo-C lifter. It works at register level (no type recovery), turns each
//! basic block into C-like statements, and structures the control-flow graph into `if`/`else`
//! and `while` using dominators and post-dominators, falling back to labels and `goto` where the
//! graph isn't structured. Calls get resolved names and arguments from the calling convention;
//! string literals are inlined.

use crate::decode::{ArmConsts, Cond, Flow, Insn, Kind, MemOp, Mode, Op, Shift, canonical_reg};
use crate::image::Image;
use crate::program::{Function, Program};
use craft_anything_formats::Format;
use serde::Serialize;
use std::collections::{BTreeMap, BTreeSet};

/// Blocks above this are listed linearly with labels instead of being structured.
const MAX_STRUCTURED_BLOCKS: usize = 1500;
const MAX_DEPTH: usize = 64;

#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct Pseudo {
    pub signature: String,
    pub text: String,
    /// Names of everything called.
    pub calls: Vec<String>,
    /// String literals used.
    pub strings: Vec<String>,
    pub gotos: usize,
    /// Instructions shown as `__asm(...)` because the lifter has no rule for them.
    pub asm_fallbacks: usize,
    /// True when the control flow was fully structured (no gotos, no linear fallback).
    pub structured: bool,
    pub limitations: Vec<(String, String)>,
}

#[derive(Debug, Clone)]
struct Line {
    indent: usize,
    text: String,
    label: Option<u64>,
    loop_end: bool,
}

struct BlockCode {
    stmts: Vec<String>,
    cond: Option<String>,
    /// Condition is for the taken edge; `taken` is its target.
    taken: Option<u64>,
}

/// Source expression and read-dependencies for an assignment that may be folded into a later call.
struct InlineExpr {
    idx: usize,
    expr: String,
    deps: Vec<String>,
    /// The memory the expression reads, if any: a later store that may overlap it changes the
    /// value, so the expression can't move past that store.
    mem: Option<MemOp>,
}

/// Latest assignment to a register or outgoing stack slot in the current basic block.
/// While `inline` is `Some`, its RHS can be folded straight into a call and its statement removed;
/// if a source dependency changes before the call, `inline` clears to `None` so the statement stays
/// emitted and the call receives the assigned target name (`rsi`, `stack_20`, etc.).
struct PendingAssign {
    target: String,
    inline: Option<InlineExpr>,
}

/// Clear `inline` on pending assignments that read any canonical register overwritten in `written`,
/// keeping the target slot registered so callers still pass the preserved register or stack slot.
fn invalidate_dependents<K: Ord>(map: &mut BTreeMap<K, PendingAssign>, written: &[String]) {
    if written.is_empty() {
        return;
    }
    for assign in map.values_mut() {
        if assign.inline.as_ref().is_some_and(|e| e.deps.iter().any(|r| written.contains(r))) {
            assign.inline = None;
        }
    }
}

/// Registers that can be distinguished from static addresses in this function and block.
#[derive(Clone, Copy)]
struct FrameBases {
    stack: bool,
    pointer: Option<&'static str>,
}

/// An A64 stack adjustment by an immediate preserves the stack base. A new value from
/// another register can point into static storage, including in a later block.
fn replaces_a64_stack(i: &Insn) -> bool {
    if !i.writes.iter().any(|r| r == "sp") {
        return false;
    }
    match (i.kind, i.ops.as_slice()) {
        (Kind::Add | Kind::Sub | Kind::Mov, [Op::Reg(dst), Op::Reg(src), Op::Imm(_)]) if dst == "sp" && src == "sp" => false,
        // Scalar LDR/STR and pair writebacks have an immediate offset. Vector structure
        // loads and stores can take their increment from a register.
        (Kind::Load | Kind::Store, [_, Op::Mem(m)]) if m.base.as_deref() == Some("sp") && (i.mnemonic.starts_with("ldr") || i.mnemonic.starts_with("str")) => {
            false
        }
        (Kind::StorePair | Kind::LoadPair, [_, _, Op::Mem(m)]) if m.base.as_deref() == Some("sp") => false,
        _ => true,
    }
}

/// Keep the x86 stack distinct from static data only while stack writes preserve its base.
fn replaces_x86_stack(i: &Insn) -> bool {
    if !i.writes.iter().any(|r| r == "rsp") {
        return false;
    }
    match (i.kind, i.ops.as_slice()) {
        (Kind::Add | Kind::Sub, [Op::Reg(dst), Op::Imm(_)]) if dst == "rsp" => false,
        (Kind::Lea, [Op::Reg(dst), Op::Mem(m)]) if dst == "rsp" && m.base.as_deref() == Some("rsp") && m.index.is_none() && m.seg.is_none() => false,
        _ => true,
    }
}

/// Clear `inline` on pending assignments whose expression reads memory that a write to `written`
/// may overlap. `None` is a write whose bytes aren't known, which may overlap any read.
fn invalidate_memory_readers(map: &mut BTreeMap<String, PendingAssign>, written: Option<&MemOp>, frame: FrameBases) {
    for assign in map.values_mut() {
        if assign.inline.as_ref().and_then(|e| e.mem.as_ref()).is_some_and(|read| written.is_none_or(|w| may_overlap(read, w, frame))) {
            assign.inline = None;
        }
    }
}

/// Clear `inline` on Win64 outgoing stack arguments (`[rsp+off]`, eight bytes) that a write to
/// `written` may change, so the call passes the slot as it is and the store that set it stays.
fn invalidate_stack_slots(slots: &mut BTreeMap<i64, PendingAssign>, written: Option<&MemOp>, frame: FrameBases) {
    if let Some(w) = written
        && w.base.as_deref() == Some("rsp")
        && w.index.is_none()
        && w.seg.is_none()
        && w.addr.is_none()
        && w.size > 0
    {
        let first = w.disp.saturating_sub(7);
        let last = w.disp.saturating_add(i64::from(w.size) - 1);
        for (_, assign) in slots.range_mut(first..=last) {
            assign.inline = None;
        }
        return;
    }
    for (&off, assign) in slots.iter_mut() {
        let slot = MemOp { base: Some("rsp".into()), index: None, index_shift: None, scale: 1, disp: off, size: 8, addr: None, seg: None };
        if written.is_none_or(|w| may_overlap(&slot, w, frame)) {
            assign.inline = None;
        }
    }
}

/// Size of an A64 data register in bytes.
fn reg_width(o: Option<&Op>) -> u8 {
    match o {
        Some(Op::Reg(r)) => match r.as_bytes().first() {
            Some(b'x') => 8,
            Some(b'w') => 4,
            Some(b'q') => 16,
            Some(b'd') => 8,
            Some(b's') if r != "sp" => 4,
            Some(b'h') => 2,
            Some(b'b') => 1,
            _ => 0,
        },
        _ => 0,
    }
}

/// Memory width and sign extension of a scalar A64 load.
fn scalar_load(i: &Insn) -> (u8, bool) {
    match i.mnemonic.as_str() {
        "ldrb" | "ldurb" | "ldarb" => (1, false),
        "ldrh" | "ldurh" | "ldarh" => (2, false),
        "ldrsb" | "ldursb" => (1, true),
        "ldrsh" | "ldursh" => (2, true),
        "ldrsw" | "ldursw" => (4, true),
        _ => (reg_width(i.ops.first()), false),
    }
}

/// Memory footprint used to check whether a pending argument survives a write.
fn accessed(mode: Mode, i: &Insn, m: &MemOp) -> MemOp {
    let pair_width = |start: usize| {
        let (a, b) = (reg_width(i.ops.get(start)), reg_width(i.ops.get(start + 1)));
        if a == 0 || b == 0 { 0 } else { a + b }
    };
    let size = match (m.size, mode, i.kind) {
        (0, Mode::A64, Kind::Store) if matches!(i.mnemonic.as_str(), "stxp" | "stlxp") => pair_width(1),
        (0, Mode::A64, Kind::Store) if matches!(i.mnemonic.as_str(), "stxr" | "stxrb" | "stxrh" | "stlxr" | "stlxrb" | "stlxrh") => reg_width(i.ops.get(1)),
        (0, Mode::A64, Kind::Load) => scalar_load(i).0,
        (0, Mode::A64, Kind::Store) => reg_width(i.ops.first()),
        (0, Mode::A64, Kind::LoadPair | Kind::StorePair) => pair_width(0),
        (s, ..) => s,
    };
    let addr = if mode == Mode::A64 && matches!(i.kind, Kind::Load | Kind::Store) && matches!(i.ops.get(1), Some(Op::Mem(_))) {
        m.addr.or_else(|| i.refs.first().copied())
    } else {
        m.addr
    };
    MemOp { size, addr, ..m.clone() }
}

/// Whether two memory operands can share a byte. Without a known overlap they are assumed to:
/// only the same absolute address range, or the same segment, base and index with displacements
/// far enough apart, are told apart, and an unindexed, unsegmented frame slot never overlaps an
/// absolute address. An access of unknown width (0) may reach any byte from its start on.
fn may_overlap(a: &MemOp, b: &MemOp, frame: FrameBases) -> bool {
    // A segment base (`fs:[rax]`) moves the address by an amount that isn't known here.
    if a.seg != b.seg {
        return true;
    }
    let ends_by = |x: i64, m: &MemOp, y: i64| m.size != 0 && x.saturating_add(i64::from(m.size)) <= y;
    let apart = |x: i64, y: i64| ends_by(x, a, y) || ends_by(y, b, x);
    let is_frame = |m: &MemOp| {
        m.addr.is_none()
            && m.index.is_none()
            && m.seg.is_none()
            && m.base.as_deref().is_some_and(|r| frame.stack && (matches!(r, "rsp" | "esp" | "sp") || Some(r) == frame.pointer))
    };
    match (a.addr, b.addr) {
        (Some(x), Some(y)) => !apart(x as i64, y as i64),
        (Some(_), None) => !is_frame(b),
        (None, Some(_)) => !is_frame(a),
        (None, None) => {
            let same = |p: &Option<String>, q: &Option<String>| p.as_deref().map(canonical_reg) == q.as_deref().map(canonical_reg);
            // The scale and extension only matter with an index.
            let same_index = same(&a.index, &b.index) && (a.index.is_none() || (a.scale == b.scale && a.index_shift == b.index_shift));
            if same(&a.base, &b.base) && same_index { !apart(a.disp, b.disp) } else { true }
        }
    }
}

struct Lifter<'a> {
    img: &'a Image,
    prog: &'a Program,
    names: &'a dyn Fn(u64) -> Option<String>,
    mode: Mode,
    arg_regs: &'static [&'static str],
    /// Win64: calls take arguments 5+ from the stack at `[rsp+0x20]`, `[rsp+0x28]`, โ€ฆ
    win64: bool,
    /// Jump targets that leave the function (tail calls).
    tail_calls: &'a [u64],
    ret_reg: String,
    calls: BTreeSet<String>,
    strings: Vec<String>,
    asm_fallbacks: usize,
}

fn escape(s: &str) -> String {
    let mut out = String::new();
    for (i, c) in s.chars().enumerate() {
        if i >= 120 {
            out.push_str("...");
            break;
        }
        match c {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            c if c.is_control() => out.push_str(&format!("\\x{:02x}", c as u32)),
            c => out.push(c),
        }
    }
    out
}

/// True when `op` is the AArch64 zero register (`wzr` or `xzr`).
fn is_zero_reg(op: Option<&Op>) -> bool {
    matches!(op, Some(Op::Reg(r)) if matches!(r.as_str(), "wzr" | "xzr"))
}

fn ty(size: u8) -> &'static str {
    match size {
        1 => "uint8_t",
        2 => "uint16_t",
        4 => "uint32_t",
        8 => "uint64_t",
        16 => "uint128_t",
        _ => "void",
    }
}

/// Dereference a scalar load with its encoded width and sign extension.
fn scalar_deref(mode: Mode, i: &Insn, addr: &str) -> String {
    let word = matches!(i.ops.first(), Some(Op::Reg(r)) if r.starts_with('w'));
    let ty = match mode {
        Mode::A32 | Mode::T32 => "uint32_t",
        Mode::A64 => {
            let (width, signed) = scalar_load(i);
            let name = ty(width);
            if signed {
                name.trim_start_matches('u')
            } else if width == 0 {
                "uint64_t"
            } else {
                name
            }
        }
        _ => "uint64_t",
    };
    // Writing W zeroes the high half of X even for a sign-extending load.
    let cast = if word && ty.starts_with("int") { "(uint32_t)" } else { "" };
    format!("{cast}*({ty}*){addr}")
}

/// A shifted or extended register as C: the shift's signedness and width are spelled out, since
/// registers have no types here.
fn shifted(reg: &str, shift: Shift, n: u8) -> String {
    let bits: u8 = if reg.starts_with('w') { 32 } else { 64 };
    // (the extension, the 64-bit type it widens to before a shift)
    let (cast, wide) = match shift {
        Shift::Lsl => return format!("({reg} << {n})"),
        Shift::Lsr => return format!("((uint{bits}_t){reg} >> {n})"),
        Shift::Asr => return format!("((int{bits}_t){reg} >> {n})"),
        Shift::Ror => {
            return match bits.checked_sub(n) {
                Some(back) if n > 0 && back > 0 => format!("((uint{bits}_t){reg} >> {n} | (uint{bits}_t){reg} << {back})"),
                _ => reg.to_string(),
            };
        }
        Shift::Uxtb => ("uint8_t", "uint64_t"),
        Shift::Uxth => ("uint16_t", "uint64_t"),
        Shift::Uxtw => ("uint32_t", "uint64_t"),
        Shift::Uxtx => ("uint64_t", "uint64_t"),
        Shift::Sxtb => ("int8_t", "int64_t"),
        Shift::Sxth => ("int16_t", "int64_t"),
        Shift::Sxtw => ("int32_t", "int64_t"),
        Shift::Sxtx => ("int64_t", "int64_t"),
    };
    // Extend, then widen before shifting, so the shift can't lose the bits C's narrower type would drop.
    match n {
        0 => format!("({cast}){reg}"),
        _ if cast == wide => format!("(({wide}){reg} << {n})"),
        _ => format!("(({wide})({cast}){reg} << {n})"),
    }
}

fn imm(v: i64) -> String {
    if (-16..=16).contains(&v) {
        v.to_string()
    } else if v < 0 {
        format!("-{:#x}", v.unsigned_abs())
    } else {
        format!("{v:#x}")
    }
}

impl Lifter<'_> {
    fn addr_name(&self, a: u64) -> Option<String> {
        (self.names)(a).or_else(|| self.prog.name_at(a))
    }

    /// Inline a string literal at `a`, slicing by byte offset for UTF-8 and 2-byte code-unit offset
    /// for UTF-16LE while rejecting misaligned interior addresses.
    fn string_lit(&mut self, a: u64) -> Option<String> {
        let s = self.prog.string_at(a)?;
        let off = usize::try_from(a.checked_sub(s.addr)?).ok()?;
        let text = match s.encoding {
            craft_anything_formats::strings::Encoding::Ascii | craft_anything_formats::strings::Encoding::Utf8 => {
                let tail = s.text.get(off..)?;
                if off > 0 && tail.is_empty() {
                    return None;
                }
                tail.to_string()
            }
            craft_anything_formats::strings::Encoding::Utf16le => {
                if off == 0 {
                    s.text.clone()
                } else {
                    if !off.is_multiple_of(2) {
                        return None;
                    }
                    let units: Vec<u16> = s.text.encode_utf16().collect();
                    let tail = units.get(off / 2..)?;
                    if tail.is_empty() {
                        return None;
                    }
                    String::from_utf16(tail).ok()?
                }
            }
        };
        if !self.strings.contains(&text) && self.strings.len() < 256 {
            self.strings.push(text.clone());
        }
        Some(format!("\"{}\"", escape(&text)))
    }

    /// `&thing` for an address-of.
    fn address_of(&mut self, a: u64) -> String {
        if let Some(s) = self.string_lit(a) {
            return s;
        }
        match self.addr_name(a) {
            Some(n) => format!("&{n}"),
            None => {
                if self.img.is_exec(a) {
                    format!("sub_{a:x}")
                } else {
                    format!("&data_{a:x}")
                }
            }
        }
    }

    /// The address arithmetic of a memory operand, without dereferencing it.
    fn mem_addr(&mut self, m: &MemOp) -> String {
        if let Some(a) = m.addr {
            return self.address_of(a);
        }
        let mut parts = Vec::new();
        if let Some(b) = &m.base {
            parts.push(b.clone());
        }
        if let Some(i) = &m.index {
            parts.push(self.index_expr(i, m));
        }
        if m.disp != 0 || parts.is_empty() {
            parts.push(imm(m.disp));
        }
        parts.join(" + ").replace("+ -", "- ")
    }

    fn mem(&mut self, m: &MemOp) -> String {
        if let Some(seg) = &m.seg {
            return format!("{seg}:[{}]", self.mem_addr(m));
        }
        if let Some(a) = m.addr {
            if let Some(n) = self.addr_name(a) {
                return n;
            }
            return format!("*({}*){a:#x}", ty(m.size));
        }
        let frame = matches!(m.base.as_deref(), Some("rbp" | "ebp" | "bp" | "x29"));
        let stack = matches!(m.base.as_deref(), Some("rsp" | "esp" | "sp"));
        if m.index.is_none() && (frame || stack) {
            let prefix = if frame { if m.disp < 0 { "var" } else { "arg" } } else { "stack" };
            return format!("{prefix}_{:x}", m.disp.unsigned_abs());
        }
        let mut parts = Vec::new();
        if let Some(b) = &m.base {
            parts.push(b.clone());
        }
        if let Some(i) = &m.index {
            parts.push(self.index_expr(i, m));
        }
        if m.disp != 0 || parts.is_empty() {
            parts.push(imm(m.disp));
        }
        format!("*({}*)({})", ty(m.size), parts.join(" + ").replace("+ -", "- "))
    }

    /// An index register as it enters the address: extended when the instruction extends it
    /// (`[x1, w2, sxtw #2]`), scaled when the encoding only says a scale (x86), plain otherwise.
    fn index_expr(&mut self, index: &str, m: &MemOp) -> String {
        match m.index_shift {
            Some(s) => shifted(index, s.shift, s.amount),
            None if m.scale > 1 => format!("{index} * {}", m.scale),
            None => index.to_string(),
        }
    }

    fn op(&mut self, o: &Op) -> String {
        match o {
            Op::Reg(r) => r.clone(),
            Op::Imm(v) => imm(*v),
            Op::Mem(m) => self.mem(m),
            Op::Addr(a) => self.address_of(*a),
            Op::Shifted { reg, shift, amount } => shifted(reg, *shift, *amount),
        }
    }

    fn call_name(&self, i: &Insn) -> String {
        match i.flow {
            Flow::Call { target } => self.addr_name(target).unwrap_or_else(|| format!("sub_{target:x}")),
            Flow::IndirectCall { slot: Some(s) } => {
                self.prog.import_slots.get(&s).map(|x| x.name.clone()).or_else(|| self.addr_name(s)).unwrap_or_else(|| format!("(*{s:#x})"))
            }
            _ => match i.ops.first() {
                Some(Op::Reg(r)) => format!("(*{r})"),
                Some(Op::Mem(m)) => {
                    let m = m.clone();
                    let mut tmp = Lifter {
                        img: self.img,
                        prog: self.prog,
                        names: self.names,
                        mode: self.mode,
                        arg_regs: self.arg_regs,
                        win64: self.win64,
                        tail_calls: self.tail_calls,
                        ret_reg: String::new(),
                        calls: BTreeSet::new(),
                        strings: Vec::new(),
                        asm_fallbacks: 0,
                    };
                    format!("(*{})", tmp.mem(&m))
                }
                _ => "(*unknown)".into(),
            },
        }
    }

    /// Register arguments of a call: up to the last argument register assigned in this block (at
    /// least `min`). Assignments whose dependencies stay intact are folded into the call; invalidated
    /// ones keep their emitted statement and pass the register name itself.
    fn reg_args(&self, defs: &BTreeMap<String, PendingAssign>, dead: &mut BTreeSet<usize>, min: usize) -> Vec<String> {
        let n = self.arg_regs.iter().rposition(|r| defs.contains_key(*r)).map(|p| p + 1).unwrap_or(0).max(min).min(self.arg_regs.len());
        self.arg_regs
            .iter()
            .take(n)
            .map(|r| match defs.get(*r) {
                Some(assign) => match &assign.inline {
                    Some(def) => {
                        dead.insert(def.idx);
                        def.expr.clone()
                    }
                    None => assign.target.clone(),
                },
                None => (*r).to_string(),
            })
            .collect()
    }

    /// Statements for one block plus its branch condition.
    fn block(&mut self, insns: &[Insn], entry_or_exit: bool, stack_is_frame: bool) -> BlockCode {
        let mut stmts: Vec<String> = Vec::new();
        // canonical reg โ†’ pending assignment of its latest value in this block
        let mut defs: BTreeMap<String, PendingAssign> = BTreeMap::new();
        // canonical reg โ†’ (statement index, value) while that assignment is a plain constant,
        // so a following MOVK can fold with it
        let mut consts: BTreeMap<String, (usize, u64)> = BTreeMap::new();
        let mut pushes: Vec<String> = Vec::new();
        let mut flag_src: Option<&Insn> = None;
        let mut cond = None;
        let mut taken = None;
        let mut dead: BTreeSet<usize> = BTreeSet::new();
        // Win64 outgoing stack arguments stored in this block: rsp offset โ†’ pending assignment.
        let mut stack_args: BTreeMap<i64, PendingAssign> = BTreeMap::new();
        // A split argument may be initialized high half first, before its low-address store.
        let mut written_slots = BTreeSet::new();
        // Registers assigned in this block whose assignment a later read took out of `defs`:
        // still set here, so a memory-indirect call's base among them is still an argument.
        let mut read_after_set: BTreeSet<String> = BTreeSet::new();
        let mut frame = FrameBases { stack: stack_is_frame, pointer: None };
        for (k, i) in insns.iter().enumerate() {
            if i.writes.iter().any(|r| matches!(r.as_str(), "rbp" | "x29")) {
                frame.pointer = match (i.kind, i.ops.as_slice()) {
                    (Kind::Mov, [Op::Reg(dst), Op::Reg(src)]) if i.mnemonic == "mov" && dst == "rbp" && src == "rsp" => Some("rbp"),
                    (Kind::Add | Kind::Mov, [Op::Reg(dst), Op::Reg(src), Op::Imm(_)]) if dst == "x29" && src == "sp" => Some("x29"),
                    _ => None,
                };
            }
            let exclusive_memory = self.mode == Mode::A64
                && matches!(
                    i.mnemonic.as_str(),
                    "ldxr"
                        | "ldxrb"
                        | "ldxrh"
                        | "ldaxr"
                        | "ldaxrb"
                        | "ldaxrh"
                        | "ldxp"
                        | "ldaxp"
                        | "stxr"
                        | "stxrb"
                        | "stxrh"
                        | "stlxr"
                        | "stlxrb"
                        | "stlxrh"
                        | "stxp"
                        | "stlxp"
                );
            // The constant a MOVK is about to fold with, before its own read of the destination
            // hides the assignment (the read-removal below is what makes the pair two statements).
            let insert_dst = (self.mode == Mode::A64 && i.kind == Kind::Insert)
                .then(|| i.ops.first().and_then(|o| if let Op::Reg(r) = o { Some(canonical_reg(r)) } else { None }))
                .flatten();
            let insert_src = insert_dst.as_ref().and_then(|r| consts.get(r).copied());
            // A register read by a later instruction (including an indirect call's target,
            // address base/index, or pointer-authentication modifier) keeps its assignment
            // instead of being folded away as a call argument.
            //
            // The base of a memory-indirect call (`call [rdi + 16]`) is usually the object the
            // callee is reached through, so an argument register there still counts as an
            // argument: it is passed by name and its assignment stays visible. A register target,
            // an index or a modifier only addresses the callee.
            let call_base = match (&i.flow, i.ops.first()) {
                (Flow::IndirectCall { .. }, Some(Op::Mem(m))) => m.base.as_deref().map(canonical_reg),
                _ => None,
            };
            for r in &i.reads {
                consts.remove(r);
                if call_base.as_ref() == Some(r) {
                    if let Some(base) = defs.get_mut(r) {
                        base.inline = None;
                        continue;
                    }
                    if read_after_set.contains(r) {
                        defs.insert(r.clone(), PendingAssign { target: r.clone(), inline: None });
                        continue;
                    }
                }
                if defs.remove(r).is_some() {
                    read_after_set.insert(r.clone());
                }
            }
            for w in &i.writes {
                read_after_set.remove(w);
            }
            // A memory write moves no load past it that may read the bytes it writes, and an
            // outgoing stack argument it may change no longer folds to the value stored before it.
            let mem_op = |o: &Op| if let Op::Mem(m) = o { Some(accessed(self.mode, i, m)) } else { None };
            let written: Option<Option<MemOp>> = match i.kind {
                Kind::Store | Kind::StorePair => i.ops.iter().find_map(mem_op).map(Some),
                Kind::Mov
                | Kind::Add
                | Kind::Sub
                | Kind::And
                | Kind::Or
                | Kind::Xor
                | Kind::Inc
                | Kind::Dec
                | Kind::Not
                | Kind::Neg
                | Kind::Shl
                | Kind::Shr
                | Kind::Sar => i.ops.first().and_then(mem_op).map(Some),
                // An instruction the lifter doesn't model (A32 `strb`, x86 `stosb`) may write its
                // memory operand at a width that isn't known, or memory it doesn't name at all.
                Kind::Other if self.mode.is_x86() => match (i.mnemonic.split_ascii_whitespace().next_back(), i.ops.as_slice()) {
                    (Some("bts" | "btr" | "btc"), [Op::Mem(_), Op::Reg(_)]) => Some(None),
                    (Some("movdir64b"), [Op::Reg(base), Op::Mem(_)]) if self.mode == Mode::X64 && canonical_reg(base) != *base => Some(None),
                    (Some("movdir64b"), [Op::Reg(base), Op::Mem(_)]) => {
                        Some(Some(MemOp { base: Some(base.clone()), index: None, index_shift: None, scale: 1, disp: 0, size: 64, addr: None, seg: None }))
                    }
                    _ => Some(i.ops.iter().find_map(mem_op).map(|m| MemOp { size: 0, ..m })),
                },
                Kind::Other => Some(i.ops.iter().find_map(mem_op).map(|m| MemOp { size: 0, ..m })),
                _ => None,
            };
            let mut prior_slot_write = false;
            if let Some(w) = &written {
                if self.win64
                    && let Some(w) = w
                    && w.base.as_deref() == Some("rsp")
                    && w.index.is_none()
                    && w.seg.is_none()
                    && w.size > 0
                {
                    let first = (w.disp & !7).max(0x20);
                    let last = w.disp.saturating_add(i64::from(w.size) - 1) & !7;
                    for slot in (first..=last).step_by(8) {
                        if !written_slots.insert(slot) && slot == w.disp {
                            prior_slot_write = true;
                        }
                    }
                }
                invalidate_memory_readers(&mut defs, w.as_ref(), frame);
                invalidate_stack_slots(&mut stack_args, w.as_ref(), frame);
            }
            // AArch64 page loads and import-slot loads are shown through what uses them.
            if i.kind == Kind::Adrp
                || (self.mode == Mode::A64
                    && !exclusive_memory
                    && i.kind == Kind::Load
                    && i.refs.first().is_some_and(|r| self.prog.import_slots.contains_key(r)))
            {
                // The skipped instruction still overwrites its destination: no constant,
                // assignment, or pending expression reading it survives.
                invalidate_dependents(&mut defs, &i.writes);
                invalidate_dependents(&mut stack_args, &i.writes);
                for w in &i.writes {
                    defs.remove(w);
                    consts.remove(w);
                }
                if i.writes.iter().any(|w| w == "rsp") {
                    stack_args.clear();
                    written_slots.clear();
                }
                continue;
            }
            let d = i.ops.first().map(|o| self.op(o));
            let s = i.ops.get(1).map(|o| self.op(o));
            let t = i.ops.get(2).map(|o| self.op(o));
            let mut stmt: Option<String> = None;
            // set when this statement leaves its destination holding a known constant
            let mut const_def: Option<(String, u64)> = None;
            // A store's first operand is the register it reads (`str r1, [r4]`), not a destination:
            // recording it would fold the store's own statement away as that register's value.
            let dest_reg = match (i.kind, i.ops.first()) {
                (Kind::Store | Kind::StorePair, _) => None,
                (_, Some(Op::Reg(r))) => Some(canonical_reg(r)),
                _ => None,
            };
            // The memory this instruction's value comes from (a load, or an operation with a memory
            // source); `lea` only computes an address. A PC-relative literal load names its fixed
            // address as an `Addr` operand.
            let read_mem = match i.kind {
                Kind::Lea | Kind::Store | Kind::StorePair => None,
                _ => i.ops.iter().skip(1).find_map(|o| match o {
                    Op::Mem(m) => Some(accessed(self.mode, i, m)),
                    &Op::Addr(a) if i.kind == Kind::Load => Some(accessed(
                        self.mode,
                        i,
                        &MemOp { base: None, index: None, index_shift: None, scale: 0, disp: 0, size: 0, addr: Some(a), seg: None },
                    )),
                    _ => None,
                }),
            };
            let frame_reg = |r: &str| matches!(canonical_reg(r).as_str(), "rsp" | "rbp" | "sp" | "x29" | "x30");
            match (i.kind, &i.flow) {
                // Keep the exclusive monitor and unrepresented SIMD pair operands in assembly.
                _ if exclusive_memory || (i.kind == Kind::StorePair && !matches!(i.ops.first(), Some(Op::Reg(_)))) => {
                    self.asm_fallbacks += 1;
                    stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
                }
                (_, Flow::Call { .. } | Flow::IndirectCall { .. }) => {
                    let name = self.call_name(i);
                    if self.calls.len() < 512 {
                        self.calls.insert(name.trim_start_matches("(*").trim_end_matches(')').to_string());
                    }
                    let args = if self.mode == Mode::X32 || self.mode == Mode::X16 {
                        let a = pushes.iter().rev().cloned().collect();
                        pushes.clear();
                        a
                    } else {
                        // Win64 calls into imports: contiguous stores at [rsp+0x20], [rsp+0x28], โ€ฆ
                        // are arguments 5, 6, โ€ฆ
                        let import: Option<&str> = match i.flow {
                            Flow::IndirectCall { slot: Some(s) } => self.prog.import_slots.get(&s).map(|si| si.name.as_str()),
                            Flow::Call { target } => self
                                .prog
                                .import_slots
                                .get(&target)
                                .map(|si| si.name.as_str())
                                .or_else(|| self.prog.functions.get(&target).and_then(|f| f.thunk_of.as_deref())),
                            _ => None,
                        };
                        let mut stack = Vec::new();
                        if self.win64 && import.is_some() {
                            let mut off = 0x20i64;
                            while let Some(arg) = stack_args.get(&off) {
                                match &arg.inline {
                                    Some(def) => {
                                        dead.insert(def.idx);
                                        stack.push(def.expr.clone());
                                    }
                                    None => stack.push(arg.target.clone()),
                                }
                                off += 8;
                            }
                        }
                        // A known library function shows all its register arguments, even ones set
                        // outside this block (they read as the register itself).
                        let known = import.and_then(crate::arity::import_arity).unwrap_or(0);
                        let mut a = self.reg_args(&defs, &mut dead, if stack.is_empty() { known } else { known.max(4) });
                        a.extend(stack);
                        a
                    };
                    stack_args.clear();
                    written_slots.clear();
                    let uses_ret = insns
                        .get(k + 1..)
                        .unwrap_or(&[])
                        .iter()
                        .take(6)
                        .take_while(|n| !matches!(n.flow, Flow::Call { .. } | Flow::IndirectCall { .. }))
                        .find_map(|n| {
                            let r = n.reads.iter().any(|x| *x == self.ret_canon());
                            let w = n.writes.iter().any(|x| *x == self.ret_canon());
                            if r {
                                Some(true)
                            } else if w {
                                Some(false)
                            } else {
                                None
                            }
                        });
                    let call = format!("{name}({})", args.join(", "));
                    stmt = Some(if uses_ret == Some(true) { format!("{} = {call};", self.ret_reg_name()) } else { format!("{call};") });
                    // Calls clobber argument registers.
                    defs.clear();
                    read_after_set.clear();
                    consts.clear();
                }
                (_, Flow::Return) => {
                    stmt = Some(if self.ret_reg.is_empty() { "return;".into() } else { format!("return {};", self.ret_reg) });
                }
                (_, Flow::Jump { target }) if self.tail_calls.contains(target) => {
                    // A jump out of the function is a tail call: it returns what the callee returns.
                    let name = self.addr_name(*target).unwrap_or_else(|| format!("sub_{target:x}"));
                    if self.calls.len() < 512 {
                        self.calls.insert(name.clone());
                    }
                    let args = self.reg_args(&defs, &mut dead, 0);
                    stmt = Some(format!("return {name}({}); /* tail call */", args.join(", ")));
                }
                (_, Flow::Jump { .. } | Flow::Cond { .. } | Flow::Stop) => {
                    if let Flow::Cond { target } = i.flow {
                        cond = Some(self.condition(i.cond.as_ref(), flag_src));
                        taken = Some(target);
                    }
                    if matches!(i.flow, Flow::Stop) {
                        stmt = Some(if i.mnemonic.starts_with("int3") || i.mnemonic == "brk" {
                            "__debugbreak();".into()
                        } else {
                            "__halt(); /* stops here */".into()
                        });
                    }
                }
                (_, Flow::IndirectJump { slot }) => {
                    let import = slot.and_then(|s| self.prog.import_slots.get(&s)).map(|si| si.name.clone());
                    stmt = Some(match import {
                        // A jump through an import slot (an x86 `jmp [slot]` or ARM `ldr pc` GOT
                        // thunk) is a tail call: it passes the block's argument registers and is
                        // recorded like any other call.
                        Some(name) => {
                            if self.calls.len() < 512 {
                                self.calls.insert(name.clone());
                            }
                            let args = self.reg_args(&defs, &mut dead, crate::arity::import_arity(&name).unwrap_or(0));
                            format!("return {name}({}); /* tail call */", args.join(", "))
                        }
                        None => format!("goto *{}; /* computed jump */", d.clone().unwrap_or_default()),
                    });
                }
                (Kind::Nop | Kind::Leave, _) => {}
                (Kind::Push, _) => {
                    let v = d.clone().unwrap_or_default();
                    if !(entry_or_exit && matches!(i.ops.first(), Some(Op::Reg(_)))) {
                        pushes.push(v);
                    }
                }
                (Kind::Pop, _) => {
                    if !entry_or_exit {
                        stmt = Some(format!("{} = pop();", d.clone().unwrap_or_default()));
                    }
                }
                (Kind::Cmp | Kind::Test, _) => flag_src = Some(i),
                (Kind::Mov | Kind::MovSx | Kind::MovZx, _) if i.ops.len() >= 2 => {
                    let (dd, ss) = (d.clone().unwrap_or_default(), s.clone().unwrap_or_default());
                    let zero_dst = self.mode == Mode::A64 && is_zero_reg(i.ops.first());
                    if (frame_reg(&dd) && dest_reg.is_some()) || dd == ss || zero_dst {
                        // frame setup (mov rbp, rsp / mov x29, sp) or discarded write to wzr/xzr
                    } else {
                        stmt = Some(format!("{dd} = {ss};"));
                    }
                    // A register set to a plain immediate holds a constant a MOVK can fold with
                    // (a W register's constant lives in the low 32 bits).
                    if !zero_dst && let (Some(Op::Reg(r)), Some(Op::Imm(v))) = (i.ops.first(), i.ops.get(1)) {
                        let value = if r.starts_with('w') { u64::from(*v as u32) } else { *v as u64 };
                        const_def = Some((canonical_reg(r), value));
                    }
                }
                (Kind::Insert, _) => match (i.ops.get(1), i.ops.get(2)) {
                    (Some(Op::Imm(v)), Some(Op::Imm(keep))) => {
                        let dd = d.clone().unwrap_or_default();
                        // A MOVZ (or an earlier folded MOVK) beside this MOVK is one constant:
                        // fold the pair into a single assignment.
                        if let (Some((idx, base)), Some(dr)) = (insert_src, dest_reg.as_ref())
                            && !dead.contains(&idx)
                        {
                            let combined = (base & (*keep as u64)) | (*v as u64);
                            dead.insert(idx);
                            stmt = Some(format!("{dd} = {};", imm(combined as i64)));
                            const_def = Some((dr.clone(), combined));
                        } else {
                            stmt = Some(format!("{dd} = ({dd} & {:#x}) | {:#x};", *keep as u64, *v as u64));
                        }
                    }
                    _ => {
                        self.asm_fallbacks += 1;
                        stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
                    }
                },
                (Kind::Lea, _) => {
                    let e = match i.ops.get(1) {
                        Some(Op::Mem(m)) => match m.addr {
                            Some(a) => self.address_of(a),
                            None => {
                                let frame = matches!(m.base.as_deref(), Some("rbp" | "ebp" | "rsp" | "esp" | "x29" | "sp")) && m.index.is_none();
                                if frame { format!("&{}", self.mem(m)) } else { self.mem_addr(m) }
                            }
                        },
                        _ => s.clone().unwrap_or_default(),
                    };
                    stmt = Some(format!("{} = {e};", d.clone().unwrap_or_default()));
                }
                (Kind::Adrp | Kind::Adr, _) => {
                    let e = match i.ops.get(1) {
                        Some(Op::Addr(a)) if i.kind == Kind::Adr => self.address_of(*a),
                        Some(Op::Addr(a)) => format!("{a:#x} /* page */"),
                        _ => s.clone().unwrap_or_default(),
                    };
                    stmt = Some(format!("{} = {e};", d.clone().unwrap_or_default()));
                }
                (Kind::Add | Kind::Sub | Kind::And | Kind::Or | Kind::Xor | Kind::Shl | Kind::Shr | Kind::Sar | Kind::Mul, _) => {
                    let sym = match i.kind {
                        Kind::Add => "+",
                        Kind::Sub => "-",
                        Kind::And => "&",
                        Kind::Or => "|",
                        Kind::Xor => "^",
                        Kind::Shl => "<<",
                        Kind::Shr | Kind::Sar => ">>",
                        _ => "*",
                    };
                    let dd = d.clone().unwrap_or_default();
                    if i.sets_flags {
                        flag_src = Some(i);
                    }
                    if dest_reg.as_deref().is_some_and(frame_reg) && matches!(i.kind, Kind::Add | Kind::Sub) {
                        // stack frame adjustment
                    } else if self.mode == Mode::A64 && is_zero_reg(i.ops.first()) {
                        // discarded write to wzr/xzr (e.g. `cmn` = `adds xzr, โ€ฆ`); flags are kept above
                    } else if i.kind == Kind::Xor && i.ops.len() == 2 && i.ops.first() == i.ops.get(1) {
                        stmt = Some(format!("{dd} = 0;"));
                    } else if self.mode == Mode::A64 && i.kind == Kind::Add && i.refs.first().is_some_and(|r| self.prog.string_at(*r).is_some()) {
                        let r = i.refs.first().copied().unwrap_or(0);
                        let lit = self.address_of(r);
                        stmt = Some(format!("{dd} = {lit};"));
                    } else if let Some(t) = t.clone() {
                        let ss = s.clone().unwrap_or_default();
                        stmt = Some(if ss == dd { format!("{dd} {sym}= {t};") } else { format!("{dd} = {ss} {sym} {t};") });
                    } else if let Some(ss) = s.clone() {
                        stmt = Some(format!("{dd} {sym}= {ss};"));
                    } else {
                        stmt = Some(format!("{dd} = {dd} {sym} ...; /* {} */", i.text()));
                    }
                    if self.mode.is_x86() && i.ops.len() == 1 && i.kind == Kind::Mul {
                        stmt = Some(format!("rdx:rax = rax * {dd};"));
                    }
                }
                (Kind::Inc, _) => {
                    flag_src = Some(i);
                    stmt = Some(format!("{}++;", d.clone().unwrap_or_default()));
                }
                (Kind::Dec, _) => {
                    flag_src = Some(i);
                    stmt = Some(format!("{}--;", d.clone().unwrap_or_default()));
                }
                (Kind::Not, _) => stmt = Some(format!("{0} = ~{0};", d.clone().unwrap_or_default())),
                (Kind::Neg, _) => stmt = Some(format!("{0} = -{0};", d.clone().unwrap_or_default())),
                (Kind::Load, _) if i.ops.len() >= 2 => {
                    let e = match i.refs.first() {
                        Some(&r) => self.addr_name(r).unwrap_or_else(|| scalar_deref(self.mode, i, &format!("{r:#x}"))),
                        None if self.mode == Mode::A64
                            && scalar_load(i).0 < reg_width(i.ops.first())
                            && let Some(Op::Mem(m)) = i.ops.get(1) =>
                        {
                            scalar_deref(self.mode, i, &format!("({})", self.mem_addr(m)))
                        }
                        None => s.clone().unwrap_or_default(),
                    };
                    let e = if e.starts_with("&") && i.refs.is_empty() { e.trim_start_matches('&').to_string() } else { e };
                    stmt = Some(format!("{} = {};", d.clone().unwrap_or_default(), e.trim_start_matches("&")));
                }
                (Kind::Store, _) if i.ops.len() >= 2 => {
                    let target = match i.refs.first() {
                        Some(&r) => self.addr_name(r).unwrap_or_else(|| format!("*(uint64_t*){r:#x}")),
                        None => s.clone().unwrap_or_default(),
                    };
                    stmt = Some(format!("{} = {};", target.trim_start_matches('&'), d.clone().unwrap_or_default()));
                }
                (Kind::LoadPair | Kind::StorePair, _) => {
                    let all_frame = i.ops.iter().take(2).all(|o| matches!(o, Op::Reg(r) if frame_reg(r)));
                    let stack_pair = matches!(i.ops.get(2), Some(Op::Mem(m)) if m.base.as_deref() == Some("sp") && m.index.is_none());
                    let frame_save = i.kind == Kind::StorePair
                        && i.mnemonic == "stp"
                        && matches!(i.ops.as_slice(), [Op::Reg(fp), Op::Reg(lr), _] if fp == "x29" && lr == "x30")
                        && matches!(i.ops.get(2), Some(Op::Mem(m)) if m.disp < 0)
                        && i.writes.iter().any(|r| r == "sp");
                    if !(entry_or_exit && all_frame && stack_pair && frame.stack && (i.kind == Kind::LoadPair || frame_save)) {
                        let (a, b) = (d.clone().unwrap_or_default(), s.clone().unwrap_or_default());
                        if i.kind == Kind::LoadPair {
                            let m = t.clone().unwrap_or_default();
                            stmt = Some(format!("{a} = {m}[0]; {b} = {m}[1];"));
                        } else if let Some(Op::Mem(m)) = i.ops.get(2) {
                            if m.base.as_ref().is_some_and(|base| i.writes.contains(base)) {
                                self.asm_fallbacks += 1;
                                stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
                            } else {
                                let elem = ty(reg_width(i.ops.first()));
                                let base = m.addr.map(|addr| format!("{addr:#x}")).unwrap_or_else(|| self.mem_addr(m));
                                let ptr = format!("(({elem}*)({base}))");
                                stmt = Some(format!("{ptr}[0] = {a}; {ptr}[1] = {b};"));
                            }
                        }
                    }
                }
                _ => {
                    if i.sets_flags {
                        flag_src = Some(i);
                    }
                    self.asm_fallbacks += 1;
                    stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
                }
            }
            // Writing a register invalidates earlier pending expressions that read it (before
            // recording this instruction's own new pending expression). For calls, arguments were
            // already consumed above so post-call register clobbers still invalidate surviving slots.
            invalidate_dependents(&mut defs, &i.writes);
            invalidate_dependents(&mut stack_args, &i.writes);
            if let Some(st) = stmt {
                stmts.push(st);
                if self.win64
                    && matches!(i.kind, Kind::Mov | Kind::Store)
                    && let Some(Op::Mem(m)) = i.ops.first()
                    && m.base.as_deref() == Some("rsp")
                    && m.index.is_none()
                    && m.seg.is_none()
                    && m.disp >= 0x20
                    && m.disp % 8 == 0
                    && let Some((lhs, rhs)) = stmts.last().and_then(|l| l.split_once(" = "))
                {
                    let target = lhs.trim().to_string();
                    let v = rhs.trim_end_matches(';').to_string();
                    let inline = (m.size == 8 || (m.size > 0 && m.size < 8 && !prior_slot_write)).then(|| InlineExpr {
                        idx: stmts.len() - 1,
                        expr: v,
                        deps: i.reads.clone(),
                        mem: None,
                    });
                    stack_args.insert(m.disp, PendingAssign { target, inline });
                }
                if let Some(r) = &dest_reg {
                    let expr = stmts.last().and_then(|l| l.split_once(" = ").map(|(_, e)| e.trim_end_matches(';').to_string()));
                    match expr {
                        Some(e) if !e.contains(';') && !matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) => {
                            let deps = if const_def.is_some() { Vec::new() } else { i.reads.clone() };
                            defs.insert(
                                r.clone(),
                                PendingAssign { target: r.clone(), inline: Some(InlineExpr { idx: stmts.len() - 1, expr: e, deps, mem: read_mem.clone() }) },
                            );
                        }
                        _ => {
                            defs.remove(r);
                        }
                    }
                    match const_def {
                        Some((cr, v)) if cr == *r => {
                            consts.insert(r.clone(), (stmts.len() - 1, v));
                        }
                        _ => {
                            consts.remove(r);
                        }
                    }
                }
                for w in &i.writes {
                    if dest_reg.as_ref() != Some(w) {
                        defs.remove(w);
                        consts.remove(w);
                    }
                }
            } else {
                for w in &i.writes {
                    defs.remove(w);
                    consts.remove(w);
                }
            }
            // Moving the stack pointer shifts every slot: forget the pending stack arguments.
            if i.writes.iter().any(|w| w == "rsp") {
                stack_args.clear();
                written_slots.clear();
            }
        }
        let stmts = stmts.into_iter().enumerate().filter(|(i, _)| !dead.contains(i)).map(|(_, s)| s).collect();
        BlockCode { stmts, cond, taken }
    }

    fn ret_canon(&self) -> String {
        match self.mode {
            Mode::A64 => "x0".into(),
            Mode::A32 | Mode::T32 => "r0".into(),
            _ => "rax".into(),
        }
    }

    fn ret_reg_name(&self) -> String {
        if self.ret_reg.is_empty() { self.ret_canon() } else { self.ret_reg.clone() }
    }

    fn condition(&mut self, c: Option<&Cond>, src: Option<&Insn>) -> String {
        let Some(c) = c else { return "/* condition */ flags".into() };
        match c {
            Cond::RegZero(r) => return format!("{r} == 0"),
            Cond::RegNonZero(r) => return format!("{r} != 0"),
            Cond::BitClear(r, b) => return format!("(({r} >> {b}) & 1) == 0"),
            Cond::BitSet(r, b) => return format!("(({r} >> {b}) & 1) != 0"),
            _ => {}
        }
        let opstr = match c {
            Cond::Sign => Some("<"),
            Cond::NotSign => Some(">="),
            other => other.op(),
        };
        let Some(src) = src else { return format!("/* {c:?} */ flags") };
        let zero_dst = self.mode == Mode::A64 && is_zero_reg(src.ops.first());
        let a = src.ops.first().map(|o| self.op(o)).unwrap_or_default();
        // ARM compare/test/cmn aliases encode the zero register first.
        let (a, b) = if self.mode == Mode::A64 && (matches!(src.kind, Kind::Cmp | Kind::Test) || (src.kind == Kind::Add && zero_dst)) {
            (src.ops.get(1).map(|o| self.op(o)).unwrap_or_default(), src.ops.get(2).map(|o| self.op(o)).unwrap_or_default())
        } else {
            (a, src.ops.get(1).map(|o| self.op(o)).unwrap_or_default())
        };
        let Some(op) = opstr else { return format!("/* {c:?} after {} */ flags", src.mnemonic) };
        let unsigned = if c.unsigned() { " /* unsigned */" } else { "" };
        match src.kind {
            Kind::Cmp => {
                if matches!(c, Cond::Sign | Cond::NotSign) {
                    format!("{a} - {b} {op} 0")
                } else {
                    format!("{a} {op} {b}{unsigned}")
                }
            }
            Kind::Test => {
                if a == b || b.is_empty() {
                    format!("{a} {op} 0{unsigned}")
                } else {
                    format!("({a} & {b}) {op} 0")
                }
            }
            Kind::Add if zero_dst => format!("({a} + {b}) {op} 0{unsigned}"),
            _ => format!("{a} {op} 0{unsigned}"),
        }
    }
}

fn cond_negate_text(c: &str) -> String {
    for (a, b) in [(" == ", " != "), (" != ", " == "), (" <= ", " > "), (" >= ", " < "), (" < ", " >= "), (" > ", " <= ")] {
        if let Some((l, r)) = c.split_once(a)
            && !r.contains(" == ")
            && !r.contains(" != ")
            && !l.contains(" == ")
        {
            return format!("{l}{b}{r}");
        }
    }
    format!("!({c})")
}

/// Bitset-backed dominator sets.
fn dominators(n: usize, entry: usize, preds: &[Vec<usize>]) -> Vec<Vec<u64>> {
    let words = n.div_ceil(64);
    let full = vec![u64::MAX; words];
    let mut dom: Vec<Vec<u64>> = vec![full; n];
    if let Some(d) = dom.get_mut(entry) {
        *d = vec![0; words];
        set(d, entry);
    }
    let mut changed = true;
    let mut rounds = 0;
    while changed && rounds < 200 {
        changed = false;
        rounds += 1;
        for b in 0..n {
            if b == entry {
                continue;
            }
            let mut new = vec![u64::MAX; words];
            let mut any = false;
            for &p in preds.get(b).map(Vec::as_slice).unwrap_or(&[]) {
                if let Some(pd) = dom.get(p) {
                    any = true;
                    for (x, y) in new.iter_mut().zip(pd) {
                        *x &= *y;
                    }
                }
            }
            if !any {
                new = vec![0; words];
            }
            set(&mut new, b);
            if dom.get(b) != Some(&new) {
                if let Some(d) = dom.get_mut(b) {
                    *d = new;
                }
                changed = true;
            }
        }
    }
    dom
}

fn set(v: &mut [u64], i: usize) {
    if let Some(w) = v.get_mut(i / 64) {
        *w |= 1 << (i % 64);
    }
}

fn has(v: &[u64], i: usize) -> bool {
    v.get(i / 64).is_some_and(|w| w & (1 << (i % 64)) != 0)
}

fn count(v: &[u64]) -> u32 {
    v.iter().map(|w| w.count_ones()).sum()
}

/// Immediate (post-)dominator: the strict dominator with the largest dominator set.
fn immediate(sets: &[Vec<u64>], n: usize, b: usize) -> Option<usize> {
    let s = sets.get(b)?;
    if count(s) as usize >= n && n > 1 {
        return None; // unreachable / never reaches exit: set stayed full
    }
    (0..n).filter(|&d| d != b && has(s, d)).max_by_key(|&d| sets.get(d).map(|x| count(x)).unwrap_or(0))
}

struct Graph {
    starts: Vec<u64>,
    succs: Vec<Vec<usize>>,
    idom: Vec<Option<usize>>,
    ipdom: Vec<Option<usize>>,
    dom: Vec<Vec<u64>>,
    /// header โ†’ (loop body, follow)
    loops: BTreeMap<usize, (BTreeSet<usize>, Option<usize>)>,
}

fn build_graph(f: &Function) -> Graph {
    let n = f.blocks.len();
    let starts: Vec<u64> = f.blocks.iter().map(|b| b.start).collect();
    let index: BTreeMap<u64, usize> = starts.iter().enumerate().map(|(i, s)| (*s, i)).collect();
    let succs: Vec<Vec<usize>> = f.blocks.iter().map(|b| b.succs.iter().filter_map(|s| index.get(s).copied()).collect()).collect();
    let mut preds = vec![Vec::new(); n];
    for (i, ss) in succs.iter().enumerate() {
        for &s in ss {
            if let Some(p) = preds.get_mut(s) {
                p.push(i);
            }
        }
    }
    let entry = index.get(&f.entry).copied().unwrap_or(0);
    let dom = dominators(n, entry, &preds);
    // Post-dominators: reverse graph with a virtual exit (index n).
    let mut rpreds: Vec<Vec<usize>> = succs.clone();
    for (i, ss) in succs.iter().enumerate() {
        if ss.is_empty()
            && let Some(r) = rpreds.get_mut(i)
        {
            r.push(n);
        }
    }
    rpreds.push(Vec::new());
    let pdom = dominators(n + 1, n, &rpreds);
    let idom = (0..n).map(|b| immediate(&dom, n, b)).collect();
    let ipdom = (0..n).map(|b| immediate(&pdom, n + 1, b).filter(|&d| d < n)).collect();
    // Natural loops from back edges u โ†’ h where h dominates u.
    let mut loops: BTreeMap<usize, (BTreeSet<usize>, Option<usize>)> = BTreeMap::new();
    for (u, ss) in succs.iter().enumerate() {
        for &h in ss {
            if dom.get(u).is_some_and(|d| has(d, h)) {
                let body = &mut loops.entry(h).or_insert_with(|| (BTreeSet::from([h]), None)).0;
                let mut stack = vec![u];
                while let Some(x) = stack.pop() {
                    if body.insert(x) {
                        for &p in preds.get(x).map(Vec::as_slice).unwrap_or(&[]) {
                            stack.push(p);
                        }
                    }
                }
            }
        }
    }
    let ipd: Vec<Option<usize>> = (0..n).map(|b| immediate(&pdom, n + 1, b).filter(|&d| d < n)).collect();
    for (h, (body, follow)) in loops.iter_mut() {
        let exits: BTreeSet<usize> = body.iter().flat_map(|&b| succs.get(b).cloned().unwrap_or_default()).filter(|s| !body.contains(s)).collect();
        *follow = ipd
            .get(*h)
            .copied()
            .flatten()
            .filter(|p| !body.contains(p))
            .or_else(|| exits.iter().min_by_key(|&&e| starts.get(e).copied().unwrap_or(0)).copied());
    }
    Graph { starts, succs, idom, ipdom, dom, loops }
}

enum Edge {
    Continue,
    Break,
    To(usize),
}

struct Emitter<'a> {
    g: &'a Graph,
    code: &'a [BlockCode],
    emitted: Vec<bool>,
    lines: Vec<Line>,
    labels: BTreeSet<u64>,
    gotos: usize,
    loop_stack: Vec<(usize, Option<usize>)>,
    pending_label: Option<u64>,
}

impl Emitter<'_> {
    fn push(&mut self, indent: usize, text: impl Into<String>) {
        let label = self.pending_label.take();
        self.lines.push(Line { indent, text: text.into(), label, loop_end: false });
    }

    fn edge(&self, to: usize) -> Edge {
        if let Some(&(h, follow)) = self.loop_stack.last() {
            if to == h {
                return Edge::Continue;
            }
            if Some(to) == follow {
                return Edge::Break;
            }
        }
        Edge::To(to)
    }

    fn goto(&mut self, indent: usize, b: usize) {
        let s = self.g.starts.get(b).copied().unwrap_or(0);
        self.labels.insert(s);
        self.gotos += 1;
        self.push(indent, format!("goto label_{s:x};"));
    }

    fn in_current_loop(&self, b: usize) -> bool {
        match self.loop_stack.last() {
            Some((h, _)) => self.g.loops.get(h).is_some_and(|(body, _)| body.contains(&b)),
            None => true,
        }
    }

    /// Emit from block `b` until `stop`.
    fn region(&mut self, mut b: Option<usize>, stop: Option<usize>, indent: usize, depth: usize) {
        while let Some(cur) = b {
            if Some(cur) == stop {
                return;
            }
            if depth > MAX_DEPTH || indent > MAX_DEPTH {
                self.goto(indent, cur);
                return;
            }
            if !self.in_current_loop(cur) {
                // Leaving the loop other than through its follow.
                self.goto(indent, cur);
                return;
            }
            if self.emitted.get(cur).copied().unwrap_or(true) {
                let tiny_exit = self.g.succs.get(cur).is_some_and(|s| s.is_empty()) && self.code.get(cur).is_some_and(|c| c.stmts.len() <= 4);
                if tiny_exit {
                    for st in self.code.get(cur).map(|c| c.stmts.clone()).unwrap_or_default() {
                        self.push(indent, st);
                    }
                } else {
                    self.goto(indent, cur);
                }
                return;
            }
            let is_header = self.g.loops.contains_key(&cur) && self.loop_stack.last().map(|(h, _)| *h) != Some(cur);
            if is_header {
                let follow = self.g.loops.get(&cur).and_then(|(_, f)| *f);
                self.push(indent, "while (true) {");
                self.loop_stack.push((cur, follow));
                self.body(cur, indent + 1, depth + 1);
                self.loop_stack.pop();
                // drop a trailing continue
                if self.lines.last().is_some_and(|l| l.text == "continue;" && l.indent == indent + 1) {
                    self.lines.pop();
                }
                self.lines.push(Line { indent, text: "}".into(), label: None, loop_end: true });
                b = follow;
                continue;
            }
            b = self.body(cur, indent, depth);
        }
    }

    /// Emit one block and its branch; returns where straight-line emission continues.
    fn body(&mut self, cur: usize, indent: usize, depth: usize) -> Option<usize> {
        if let Some(e) = self.emitted.get_mut(cur) {
            *e = true;
        }
        let start = self.g.starts.get(cur).copied().unwrap_or(0);
        let first_line = self.lines.len();
        let (stmts, cond, taken) = match self.code.get(cur) {
            Some(c) => (c.stmts.clone(), c.cond.clone(), c.taken),
            None => (Vec::new(), None, None),
        };
        for s in stmts {
            self.push(indent, s);
        }
        if let Some(l) = self.lines.get_mut(first_line) {
            l.label = Some(start);
        } else {
            self.pending_label = Some(start);
        }
        let succs = self.g.succs.get(cur).cloned().unwrap_or_default();
        match succs.as_slice() {
            [] => None,
            [s] => match self.edge(*s) {
                Edge::Continue => {
                    self.push(indent, "continue;");
                    None
                }
                Edge::Break => {
                    self.push(indent, "break;");
                    None
                }
                Edge::To(t) => Some(t),
            },
            _ => {
                let taken_idx = taken.and_then(|t| self.g.starts.iter().position(|s| *s == t));
                let Some(t) = taken_idx.filter(|t| succs.contains(t)) else {
                    // switch / multiway: one case per target
                    let selector = match self.lines.last() {
                        Some(l) if l.text.starts_with("goto *") && l.label.is_none() => {
                            let sel = l.text.trim_start_matches("goto *").split(';').next().unwrap_or("").to_string();
                            self.lines.pop();
                            sel
                        }
                        _ => "/* computed */".to_string(),
                    };
                    self.push(indent, format!("switch ({selector}) {{"));
                    for s in succs {
                        let st = self.g.starts.get(s).copied().unwrap_or(0);
                        self.push(indent + 1, format!("case_{st:x}:"));
                        match self.edge(s) {
                            Edge::Continue => self.push(indent + 2, "continue;"),
                            Edge::Break => self.push(indent + 2, "break;"),
                            Edge::To(x) => {
                                if self.emitted.get(x).copied().unwrap_or(true) {
                                    self.goto(indent + 2, x);
                                } else {
                                    let join = self.g.ipdom.get(cur).copied().flatten();
                                    self.region(Some(x), join, indent + 2, depth + 1);
                                    if !self.lines.last().is_some_and(|l| l.text.starts_with("return") || l.text.starts_with("goto ")) {
                                        self.push(indent + 2, "break;");
                                    }
                                }
                            }
                        }
                    }
                    self.push(indent, "}");
                    return self.g.ipdom.get(cur).copied().flatten().filter(|j| !self.emitted.get(*j).copied().unwrap_or(true));
                };
                let f = succs.iter().copied().find(|s| *s != t).unwrap_or(t);
                let cond = cond.unwrap_or_else(|| "/* condition */ flags".into());
                let join =
                    self.g.ipdom.get(cur).copied().flatten().filter(|j| self.in_current_loop(*j) || self.loop_stack.last().and_then(|(_, f)| *f) == Some(*j));
                let arm = |me: &mut Self, x: usize, ind: usize| -> bool {
                    // returns true when something was emitted
                    match me.edge(x) {
                        Edge::Continue => {
                            me.push(ind, "continue;");
                            true
                        }
                        Edge::Break => {
                            me.push(ind, "break;");
                            true
                        }
                        Edge::To(y) => {
                            if Some(y) == join {
                                false
                            } else {
                                let before = me.lines.len();
                                me.region(Some(y), join, ind, depth + 1);
                                me.lines.len() > before
                            }
                        }
                    }
                };
                let jumpy = |e: &Edge| matches!(e, Edge::Continue | Edge::Break);
                let (et, ef) = (self.edge(t), self.edge(f));
                if jumpy(&et) && jumpy(&ef) {
                    let word = |e: &Edge| if matches!(e, Edge::Break) { "break;" } else { "continue;" };
                    if matches!(et, Edge::Break) {
                        self.push(indent, format!("if ({cond}) {}", word(&et)));
                        self.push(indent, word(&ef));
                    } else {
                        self.push(indent, format!("if ({}) {}", cond_negate_text(&cond), word(&ef)));
                        self.push(indent, word(&et));
                    }
                    return None;
                }
                let t_empty = matches!(self.edge(t), Edge::To(y) if Some(y) == join);
                let f_empty = matches!(self.edge(f), Edge::To(y) if Some(y) == join);
                if t_empty && f_empty {
                    // both go to the join: nothing to branch on
                } else if t_empty {
                    self.push(indent, format!("if ({}) {{", cond_negate_text(&cond)));
                    arm(self, f, indent + 1);
                    self.push(indent, "}");
                } else if f_empty {
                    self.push(indent, format!("if ({cond}) {{"));
                    arm(self, t, indent + 1);
                    self.push(indent, "}");
                } else {
                    self.push(indent, format!("if ({cond}) {{"));
                    arm(self, t, indent + 1);
                    self.push(indent, "} else {");
                    arm(self, f, indent + 1);
                    self.push(indent, "}");
                }
                match join {
                    Some(j) => match self.edge(j) {
                        Edge::Continue => None,
                        Edge::Break => {
                            self.push(indent, "break;");
                            None
                        }
                        Edge::To(j) => Some(j),
                    },
                    None => None,
                }
            }
        }
    }
}

fn simplify(lines: &mut Vec<Line>) {
    // `} else {` directly followed by `}` โ†’ `}`; `if (c) {` directly followed by `}` โ†’ nothing.
    let mut changed = true;
    while changed {
        changed = false;
        let mut i = 0;
        while i + 1 < lines.len() {
            let (Some(a), Some(b)) = (lines.get(i), lines.get(i + 1)) else { break };
            if b.text == "}" && a.indent == b.indent && a.label.is_none() && b.label.is_none() && !b.loop_end {
                if a.text == "} else {" {
                    lines.remove(i);
                    changed = true;
                    continue;
                }
                if a.text.starts_with("if (") && a.text.ends_with(") {") {
                    lines.drain(i..i + 2);
                    changed = true;
                    continue;
                }
            }
            i += 1;
        }
    }
    // `if (c) { break; }` โ†’ `if (c) break;`
    let mut out: Vec<Line> = Vec::with_capacity(lines.len());
    let mut i = 0;
    while i < lines.len() {
        if let (Some(a), Some(b), Some(c)) = (lines.get(i), lines.get(i + 1), lines.get(i + 2))
            && a.text.starts_with("if (")
            && a.text.ends_with(") {")
            && matches!(b.text.as_str(), "break;" | "continue;" | "return;")
            && c.text == "}"
            && c.indent == a.indent
            && b.label.is_none()
        {
            let head = a.text.trim_end_matches(" {");
            out.push(Line { indent: a.indent, text: format!("{head} {}", b.text), label: a.label, loop_end: false });
            i += 3;
            continue;
        }
        if let Some(l) = lines.get(i) {
            out.push(l.clone());
        }
        i += 1;
    }
    *lines = out;
}

/// Lift `f` to pseudo-C. `names` resolves user-given names (annotations) first.
pub fn lift(img: &Image, prog: &Program, f: &Function, names: &dyn Fn(u64) -> Option<String>) -> Pseudo {
    let mode = prog.mode;
    let arg_regs: &'static [&'static str] = match mode {
        Mode::X64 if img.bin.format == Format::Pe => &["rcx", "rdx", "r8", "r9"],
        Mode::X64 => &["rdi", "rsi", "rdx", "rcx", "r8", "r9"],
        Mode::A64 => &["x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7"],
        Mode::A32 | Mode::T32 => &["r0", "r1", "r2", "r3"],
        _ => &[],
    };
    let mut limitations: Vec<(String, String)> = vec![
        ("register_level".into(), "variables are machine registers and stack slots; types are not recovered".into()),
        ("calling_convention_assumed".into(), format!("call arguments follow the usual {} convention and may be wrong for unusual functions", mode.name())),
        ("conditions_from_flags".into(), "branch conditions are rebuilt from the last compare and may be approximate".into()),
    ];
    // Decode every block.
    let mut per_block: Vec<Vec<Insn>> = Vec::new();
    for b in &f.blocks {
        let mut v = Vec::new();
        let mut consts = ArmConsts::default();
        let mut a = b.start;
        while a < b.end && v.len() < 20_000 {
            let Some(mut i) = img.decode(a, true) else { break };
            if mode == Mode::A64 {
                consts.apply(&mut i);
            }
            a = i.end();
            v.push(i);
        }
        per_block.push(v);
    }
    // Return register: the widest name written to the return register anywhere.
    let ret_canon = if mode == Mode::A64 {
        "x0"
    } else if matches!(mode, Mode::A32 | Mode::T32) {
        "r0"
    } else {
        "rax"
    };
    let mut ret_reg = String::new();
    'outer: for v in per_block.iter().rev() {
        for i in v.iter().rev() {
            if matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) {
                ret_reg = ret_canon.into();
                break 'outer;
            }
            if i.writes.iter().any(|w| w == ret_canon)
                && let Some(Op::Reg(r)) = i.ops.first()
            {
                ret_reg = r.clone();
                break 'outer;
            }
        }
    }
    // Parameters: argument registers read before written in the entry block.
    let mut params = Vec::new();
    if let Some(entry_block) = f.blocks.iter().position(|b| b.start == f.entry).and_then(|i| per_block.get(i)) {
        let mut written: BTreeSet<String> = BTreeSet::new();
        for i in entry_block {
            if matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) {
                break;
            }
            for r in &i.reads {
                if arg_regs.contains(&r.as_str()) && !written.contains(r) && !params.contains(r) {
                    params.push(r.clone());
                }
            }
            written.extend(i.writes.iter().cloned());
        }
    }
    params.sort_by_key(|p| arg_regs.iter().position(|r| r == p).unwrap_or(99));
    let name = names(f.entry).unwrap_or_else(|| f.name.clone());
    let ret_ty = if ret_reg.is_empty() {
        "void"
    } else if ret_reg.starts_with('e') || ret_reg.starts_with('w') {
        "int32_t"
    } else {
        "int64_t"
    };
    let signature = format!("{ret_ty} {name}({})", params.iter().map(|p| format!("int64_t {p}")).collect::<Vec<_>>().join(", "));
    let win64 = mode == Mode::X64 && img.bin.format == Format::Pe;
    let mut lifter =
        Lifter { img, prog, names, mode, arg_regs, win64, tail_calls: &f.tail_calls, ret_reg, calls: BTreeSet::new(), strings: Vec::new(), asm_fallbacks: 0 };
    let n = f.blocks.len();
    let stack_is_frame = match mode {
        Mode::A64 => !per_block.iter().flatten().any(replaces_a64_stack),
        Mode::X64 => !per_block.iter().flatten().any(replaces_x86_stack),
        _ => true,
    };
    let codes: Vec<BlockCode> = per_block
        .iter()
        .zip(&f.blocks)
        .map(|(v, b)| {
            let edge = b.start == f.entry || b.succs.is_empty();
            lifter.block(v, edge, stack_is_frame)
        })
        .collect();
    let structured_ok = n <= MAX_STRUCTURED_BLOCKS;
    let graph = if structured_ok {
        build_graph(f)
    } else {
        Graph { starts: f.blocks.iter().map(|b| b.start).collect(), succs: vec![], idom: vec![], ipdom: vec![], dom: vec![], loops: BTreeMap::new() }
    };
    let mut emitter = Emitter {
        g: &graph,
        code: &codes,
        emitted: vec![false; n],
        lines: Vec::new(),
        labels: BTreeSet::new(),
        gotos: 0,
        loop_stack: Vec::new(),
        pending_label: None,
    };
    if structured_ok {
        let entry = graph.starts.iter().position(|s| *s == f.entry).unwrap_or(0);
        emitter.region(Some(entry), None, 1, 0);
        // Anything unreachable from the entry (e.g. only via unresolved jumps) goes after.
        for i in 0..n {
            if !emitter.emitted.get(i).copied().unwrap_or(true) {
                emitter.region(Some(i), None, 1, 0);
            }
        }
    } else {
        limitations.push(("not_structured".into(), format!("{n} blocks is above the structuring limit; shown as labelled blocks with gotos")));
        for (i, b) in f.blocks.iter().enumerate() {
            let first = emitter.lines.len();
            for s in codes.get(i).map(|c| c.stmts.clone()).unwrap_or_default() {
                emitter.push(1, s);
            }
            if let Some(c) = codes.get(i)
                && let (Some(cond), Some(t)) = (&c.cond, c.taken)
            {
                emitter.labels.insert(t);
                emitter.gotos += 1;
                emitter.push(1, format!("if ({cond}) goto label_{t:x};"));
            }
            if emitter.lines.len() == first {
                emitter.push(1, ";");
            }
            if let Some(l) = emitter.lines.get_mut(first) {
                l.label = Some(b.start);
            }
            emitter.labels.insert(b.start);
        }
    }
    let _ = (&graph.idom, &graph.dom);
    if emitter.pending_label.is_some() {
        emitter.push(1, ";");
    }
    let mut lines = std::mem::take(&mut emitter.lines);
    simplify(&mut lines);
    let mut text = format!("{signature}\n{{\n");
    for l in &lines {
        if let Some(lab) = l.label
            && emitter.labels.contains(&lab)
        {
            text.push_str(&format!("label_{lab:x}:\n"));
        }
        let _ = l.loop_end;
        text.push_str(&"    ".repeat(l.indent));
        text.push_str(&l.text);
        text.push('\n');
    }
    text.push_str("}\n");
    if emitter.gotos > 0 {
        limitations.push(("unstructured_flow".into(), format!("{} gotos remain where the control flow isn't a simple if/loop", emitter.gotos)));
    }
    if lifter.asm_fallbacks > 0 {
        limitations.push(("inline_asm".into(), format!("{} instructions have no C rule and are shown as __asm(...)", lifter.asm_fallbacks)));
    }
    if f.unresolved_indirect_jumps > 0 {
        limitations.push(("indirect_jumps_unresolved".into(), "some indirect jumps were not resolved, so code may be missing".into()));
    }
    if f.truncated {
        limitations.push(("function_truncated".into(), "the function hit the instruction limit; the end is missing".into()));
    }
    Pseudo {
        signature,
        text,
        calls: lifter.calls.into_iter().collect(),
        strings: lifter.strings,
        gotos: emitter.gotos,
        asm_fallbacks: lifter.asm_fallbacks,
        structured: structured_ok && emitter.gotos == 0,
        limitations,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::NoControl;
    use crate::program::Limits;
    use craft_anything_testkit as tk;
    use std::sync::Arc;

    /// The eight-byte slots straddling the write are the only ones that lose their values.
    #[test]
    fn fixed_stack_writes_invalidate_only_intersecting_slots() {
        let mut slots = (0..10_000)
            .map(|offset| {
                let expr = InlineExpr { idx: 0, expr: String::new(), deps: Vec::new(), mem: None };
                (offset, PendingAssign { target: String::new(), inline: Some(expr) })
            })
            .collect::<BTreeMap<_, _>>();
        let write = MemOp { base: Some("rsp".into()), index: None, index_shift: None, scale: 1, disp: 32, size: 4, addr: None, seg: None };
        invalidate_stack_slots(&mut slots, Some(&write), FrameBases { stack: true, pointer: None });
        let invalid: Vec<_> = slots.iter().filter(|(_, assign)| assign.inline.is_none()).map(|(&off, _)| off).collect();
        assert_eq!(invalid, (25..=35).collect::<Vec<_>>());
    }

    fn setup(bytes: Vec<u8>) -> (Image, Program) {
        let img = Image::parse(Arc::from(bytes)).unwrap();
        let p = Program::analyze(&img, &Limits::default(), &NoControl).unwrap();
        (img, p)
    }

    #[test]
    fn calls_into_known_imports_show_their_arguments() {
        // pe64 reuses the System V code, so nothing loads rcx before `puts`: Win64's first argument
        // register. The call still has its one argument, shown as the register.
        let (img, p) = setup(tk::pe64());
        let none = |_: u64| None;
        let entry = img.bin.entry.unwrap();
        let f = p.functions.get(&entry).unwrap();
        let text = lift(&img, &p, f, &none).text;
        assert!(text.contains("puts(rcx)"), "{text}");
        assert!(!text.contains("puts()"), "{text}");
    }

    /// `sub w9, w9, w9, lsl #3` came out as `w9 -= w9;`: the shift of a register operand was dropped.
    #[test]
    fn aarch64_shifted_operands_keep_their_shift() {
        // add w9, w10, w9, lsr #31; sub w9, w9, w9, lsl #3; add x0, x1, x2, asr #4;
        // add x3, x1, w2, sxtw #2; add x4, x1, w2, uxtw; orr x5, x1, x2, ror #8; ret
        let words = [0x0b49_7d49u32, 0x4b09_0d29, 0x8b82_1020, 0x8b22_c823, 0x8b22_4024, 0xaac2_2025, 0xd65f_03c0];
        let bytes: Vec<u8> = words.iter().flat_map(|w| w.to_le_bytes()).collect();
        let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
        let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
        let p = lift(&image, &program, program.functions.get(&0x1000).unwrap(), &|_| None);
        for want in [
            "w9 = w10 + ((uint32_t)w9 >> 31);",
            "w9 -= (w9 << 3);",
            "x0 = x1 + ((int64_t)x2 >> 4);",
            "x3 = x1 + ((int64_t)(int32_t)w2 << 2);",
            "x4 = x1 + (uint32_t)w2;",
            "x5 = x1 | ((uint64_t)x2 >> 8 | (uint64_t)x2 << 56);",
        ] {
            assert!(p.text.contains(want), "{want}\n{}", p.text);
        }
        assert!(!p.text.contains("w9 -= w9;"), "{}", p.text);
    }

    #[test]
    fn main_and_helper_read_like_c() {
        let (elf, _) = tk::elf64(tk::ElfArch::X86_64, true);
        let (img, p) = setup(elf);
        let none = |_: u64| None;
        let main = lift(&img, &p, p.function_by_name("main").unwrap(), &none);
        assert!(main.text.contains("puts(\"Hello, Craft!\")"), "{}", main.text);
        assert!(main.text.contains("helper(5)"), "{}", main.text);
        assert!(main.calls.contains(&"dispatch".to_string()));
        assert_eq!(main.strings, vec![tk::HELLO.to_string()]);
        let helper = lift(&img, &p, p.function_by_name("helper").unwrap(), &none);
        assert!(helper.text.contains("while (true)"), "{}", helper.text);
        assert!(helper.text.contains("if (edi"), "{}", helper.text);
        assert!(helper.signature.contains("edi") || helper.signature.contains("rdi"), "{}", helper.signature);
        assert!(helper.structured, "{}", helper.text);
        let renamed = |a: u64| (a == p.function_by_name("helper").unwrap().entry).then(|| "sum_to".to_string());
        let main2 = lift(&img, &p, p.function_by_name("main").unwrap(), &renamed);
        assert!(main2.text.contains("sum_to(5)"), "{}", main2.text);
        let d = lift(&img, &p, p.function_by_name("dispatch").unwrap(), &none);
        assert!(d.text.contains("return"), "{}", d.text);
    }

    #[test]
    fn win64_stack_args_and_tail_call() {
        // main, patched: six arguments to the `puts` import (four in registers, two on the
        // stack), then a tail jump to `helper`.
        let mut pe = tk::pe64();
        let code: [u8; 58] = [
            0x48, 0x83, 0xec, 0x68, // sub rsp, 0x68
            0x48, 0xc7, 0x44, 0x24, 0x28, 0x07, 0x00, 0x00, 0x00, // mov qword [rsp+0x28], 7
            0xc7, 0x44, 0x24, 0x20, 0x05, 0x00, 0x00, 0x00, // mov dword [rsp+0x20], 5
            0x41, 0xb9, 0x04, 0x00, 0x00, 0x00, // mov r9d, 4
            0x41, 0xb8, 0x03, 0x00, 0x00, 0x00, // mov r8d, 3
            0xba, 0x02, 0x00, 0x00, 0x00, // mov edx, 2
            0xb9, 0x01, 0x00, 0x00, 0x00, // mov ecx, 1
            0xff, 0x15, 0x2f, 0x11, 0x00, 0x00, // call [rip+0x112f] (the puts IAT slot)
            0x48, 0x83, 0xc4, 0x68, // add rsp, 0x68
            0xe9, 0x06, 0x00, 0x00, 0x00, // jmp helper
        ];
        pe[0x400..0x400 + code.len()].copy_from_slice(&code);
        let (img, p) = setup(pe);
        let main = p.functions.get(&(tk::PE_BASE + tk::PE_TEXT_RVA)).unwrap();
        let out = lift(&img, &p, main, &|_| None);
        assert!(out.text.contains("puts(1, 2, 3, 4, 5, 7);"), "{}", out.text);
        assert!(!out.text.contains("stack_20"), "{}", out.text);
        assert!(out.text.contains("return helper();"), "{}", out.text);
        assert!(out.calls.contains(&"helper".to_string()));
    }

    #[test]
    fn aarch64_lifts() {
        let (elf, _) = tk::elf64(tk::ElfArch::Aarch64, true);
        let (img, p) = setup(elf);
        let none = |_: u64| None;
        let main = lift(&img, &p, p.function_by_name("main").unwrap(), &none);
        assert!(main.text.contains("puts(\"Hello, Craft!\")"), "{}", main.text);
        let helper = lift(&img, &p, p.function_by_name("helper").unwrap(), &none);
        assert!(helper.text.contains("w0 == 0") || helper.text.contains("w0 != 0"), "{}", helper.text);
    }

    fn lift_a64(words: &[u32]) -> Pseudo {
        let bytes: Vec<u8> = words.iter().flat_map(|w| w.to_le_bytes()).collect();
        let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
        let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
        let f = program.functions.get(&0x1000).unwrap();
        lift(&image, &program, f, &|_| None)
    }

    /// `mov w9, #0x2493` followed by `movk w9, #0x9249, lsl #16` read as two statements, not
    /// one constant (R3.11).
    #[test]
    fn aarch64_movz_movk_pairs_fold_into_one_constant() {
        // mov w9, #0x2493; movk w9, #0x9249, lsl #16
        let p = lift_a64(&[0x5284_9269, 0x72b2_4929, 0xd65f_03c0]);
        assert!(p.text.contains("w9 = 0x92492493;"), "{}", p.text);
        assert!(!p.text.contains("(w9 & "), "{}", p.text);

        // mov x10, #0x1122; movk ร—4: the whole 64-bit constant, one statement
        let p = lift_a64(&[0xd282_244a, 0xf2a6_688a, 0xf2ca_acca, 0xf2ee_f10a, 0xd65f_03c0]);
        assert!(p.text.contains("x10 = 0x7788556633441122;"), "{}", p.text);
        assert!(!p.text.contains("(x10 & "), "{}", p.text);

        // A W pair over a MOVN keeps its inverted low half
        let p = lift_a64(&[0x1280_000d, 0x72b2_492d, 0xd65f_03c0]);
        assert!(p.text.contains("w13 = 0x9249ffff;"), "{}", p.text);

        // A read between the pair keeps both statements
        let p = lift_a64(&[0xd284_926e, 0x8b0e_01cf, 0xf2b2_492e, 0xd65f_03c0]);
        assert!(p.text.contains("x14 = 0x2493;"), "{}", p.text);
        assert!(p.text.contains("x15 = x14 + x14;"), "{}", p.text);
        assert!(p.text.contains("x14 = (x14 & 0xffffffff0000ffff) | 0x92490000;"), "{}", p.text);
        // A page load between the pair overwrites the register: the MOVK folds with nothing
        let p = lift_a64(&[0xd284_9269, 0x9000_0009, 0xf2b2_4929, 0xd65f_03c0]);
        assert!(p.text.contains("x9 = 0x2493;"), "{}", p.text);
        assert!(p.text.contains("x9 = (x9 & 0xffffffff0000ffff) | 0x92490000;"), "{}", p.text);
        assert!(!p.text.contains("x9 = 0x92492493;"), "{}", p.text);
    }

    /// `ldr w0, [x1, w2, sxtw #2]` read the index as the plain register, so the address lost
    /// the sign extension (R3.11).
    #[test]
    fn aarch64_extended_memory_indices_keep_the_extension() {
        // ldr w0, [x1, w2, sxtw #2]; ldr x6, [x7, x8, lsl #3]; ldr x24, [x25, w26, uxtw];
        // ldr x15, [x16, x17]; str w9, [x10, w11, sxtw #2]; ret
        let words = [0xb862_d820u32, 0xf868_78e6, 0xf87a_4b38, 0xf871_6a0f, 0xb82b_d949, 0xd65f_03c0];
        let p = lift_a64(&words);
        for want in [
            "w0 = *(void*)(x1 + ((int64_t)(int32_t)w2 << 2));",
            "x6 = *(void*)(x7 + (x8 << 3));",
            "x24 = *(void*)(x25 + (uint32_t)w26);",
            "x15 = *(void*)(x16 + x17);",
            "*(void*)(x10 + ((int64_t)(int32_t)w11 << 2)) = w9;",
        ] {
            assert!(p.text.contains(want), "{want}\n{}", p.text);
        }
        assert!(!p.text.contains("*(void*)(x1 + x2)"), "{}", p.text);
        assert!(!p.text.contains("*(void*)(x10 + x11)"), "{}", p.text);
    }

    /// `mov x19, x0` came out as `x19 = xzr;`: the zero register of its ORR form was taken as the value.
    #[test]
    fn aarch64_moves_copy_the_source_not_the_zero_register() {
        // mov x19, x0; mov w1, w2; mov w0, #0xff00ff00; ret
        let p = lift_a64(&[0xaa00_03f3, 0x2a02_03e1, 0x3208_9fe0, 0xd65f_03c0]);
        assert!(p.text.contains("x19 = x0;") && p.text.contains("w1 = w2;"), "{}", p.text);
        assert!(p.text.contains("w0 = 0xff00ff00;"), "{}", p.text);
        assert!(!p.text.contains("zr"), "{}", p.text);
    }

    #[test]
    fn every_function_of_damaged_inputs_lifts_without_panicking() {
        let (elf, _) = tk::elf64(tk::ElfArch::X86_64, false);
        for m in tk::mutations(&elf).into_iter().step_by(3) {
            if let Ok(img) = Image::parse(Arc::from(m))
                && let Ok(p) = Program::analyze(&img, &Limits::default(), &NoControl)
            {
                for f in p.functions.values() {
                    let _ = lift(&img, &p, f, &|_| None);
                }
            }
        }
        for seed in 0..12 {
            let raw = Image::raw(Arc::from(tk::noise(seed, 2048)), craft_anything_formats::Arch::X86_64, 0x1000);
            if let Ok(p) = Program::analyze(&raw, &Limits::default(), &NoControl) {
                for f in p.functions.values().take(50) {
                    let _ = lift(&raw, &p, f, &|_| None);
                }
            }
        }
    }

    #[test]
    fn arm32_calls_keep_their_return_value_in_r0() {
        use craft_anything_formats::Arch;
        fn words(ws: &[u32]) -> Vec<u8> {
            ws.iter().flat_map(|w| w.to_le_bytes()).collect()
        }
        fn arm_elf(code: &[u8], thumb: bool) -> Vec<u8> {
            let mut b = vec![0u8; 0x100];
            b[0..7].copy_from_slice(b"\x7fELF\x01\x01\x01");
            for (o, v) in [(16, 2u16), (18, 40), (40, 52), (42, 32), (44, 1)] {
                b[o..o + 2].copy_from_slice(&v.to_le_bytes());
            }
            let n = code.len() as u32;
            for (o, v) in [(20, 1u32), (24, 0x1000 | u32::from(thumb)), (28, 52), (36, 0x0500_0000), (52, 1)] {
                b[o..o + 4].copy_from_slice(&v.to_le_bytes());
            }
            for (o, v) in [(56, 0x100u32), (60, 0x1000), (64, 0x1000), (68, n), (72, n), (76, 5), (80, 0x100)] {
                b[o..o + 4].copy_from_slice(&v.to_le_bytes());
            }
            b.extend_from_slice(code);
            b
        }
        fn lift_entry(image: Image) -> String {
            let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
            let f = program.functions.get(&0x1000).unwrap();
            lift(&image, &program, f, &|_| None).text
        }

        let call_ret = words(&[0xe92d_4010, 0xeb00_0001, 0xe8bd_8010, 0xe320_f000, 0xe3a0_0007, 0xe12f_ff1e]);
        let used_call = words(&[0xe92d_4010, 0xeb00_0002, 0xe280_1001, 0xe1a0_0001, 0xe8bd_8010, 0xe3a0_0007, 0xe12f_ff1e]);
        let leaf = words(&[0xe3a0_0007, 0xe12f_ff1e]);

        let ar = lift_entry(Image::raw(Arc::from(call_ret.clone()), Arch::Arm, 0x1000));
        let au = lift_entry(Image::raw(Arc::from(used_call), Arch::Arm, 0x1000));
        let al = lift_entry(Image::raw(Arc::from(leaf), Arch::Arm, 0x1000));
        let ae = lift_entry(Image::parse(Arc::from(arm_elf(&call_ret, false))).unwrap());
        let tr = lift_entry(Image::parse(Arc::from(arm_elf(&[0x10, 0xb5, 0x98, 0x47, 0x10, 0xbd], true))).unwrap());

        assert!(ar.contains("return r0;") && !ar.contains("rax"), "{ar}");
        assert!(ae.contains("return r0;") && !ae.contains("rax"), "{ae}");
        assert!(tr.contains("return r0;") && !tr.contains("rax"), "{tr}");
        assert!(au.contains("r0 = sub_1014();") && au.contains("r1 = r0 + 1;") && au.contains("return r0;"), "{au}");
        assert!(al.contains("r0 = 7;") && al.contains("return r0;") && !al.contains("rax"), "{al}");
    }

    /// #277: ARM32 loads and stores came out as `r0 = 0;` and `0 = r0;`.
    #[test]
    fn arm32_loads_and_stores_keep_their_addresses() {
        use craft_anything_formats::Arch;
        let lift_words = |ws: &[u32]| {
            let bytes: Vec<u8> = ws.iter().flat_map(|w| w.to_le_bytes()).collect();
            let image = Image::raw(Arc::from(bytes), Arch::Arm, 0x1000);
            let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
            let f = program.functions.get(&0x1000).unwrap();
            lift(&image, &program, f, &|_| None)
        };
        // ldr r0, [r1, #4]; str r0, [r2]; bx lr
        let p = lift_words(&[0xe591_0004, 0xe582_0000, 0xe12f_ff1e]);
        assert!(p.text.contains("r0 = *(uint32_t*)(r1 + 4);") && p.text.contains("*(uint32_t*)(r2) = r0;"), "{}", p.text);
        assert_eq!(p.asm_fallbacks, 0);
        // ldr r0, [r1, #-8]
        let p = lift_words(&[0xe511_0008, 0xe12f_ff1e]);
        assert!(p.text.contains("r0 = *(uint32_t*)(r1 - 8);"), "{}", p.text);
        // ldr r0, [r1], #4 also moves r1, which no statement here says: it's shown as written.
        let p = lift_words(&[0xe491_0004, 0xe12f_ff1e]);
        assert!(p.text.contains("__asm(") && !p.text.contains("r0 = 0;") && p.asm_fallbacks == 1, "{}", p.text);
        let i = crate::decode::decode(Mode::A32, &0xe591_0004u32.to_le_bytes(), 0x1000, false).unwrap();
        assert!(i.reads.contains(&"r1".to_string()) && i.writes == ["r0"], "{i:?}");
    }

    /// `movk w9, #0x9249, lsl #16` came out as `w9 = 0x92490000;`, losing the low half set just
    /// before, and `mov w0, #-1` (MOVN) as `w0 = 0;`.
    #[test]
    fn aarch64_move_wide_immediates_keep_their_value() {
        // mov w9, #0x2493; movk w9, #0x9249, lsl #16; mov w0, #-1; ret
        let bytes: Vec<u8> = [0x5284_9269u32, 0x72b2_4929, 0x1280_0000, 0xd65f_03c0].iter().flat_map(|w| w.to_le_bytes()).collect();
        let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
        let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
        let p = lift(&image, &program, program.functions.get(&0x1000).unwrap(), &|_| None);
        // The pair folds into one constant, whose low half is the MOVZ's
        assert!(p.text.contains("w9 = 0x92492493;"), "{}", p.text);
        assert!(!p.text.contains("w9 = 0x92490000;"), "{}", p.text);
        assert!(p.text.contains("w0 = -1;") && !p.text.contains("w0 = 0;"), "{}", p.text);
        assert_eq!(p.asm_fallbacks, 0, "{}", p.text);
    }
}