Skip to main content

wazabin_qcode_sleigh/
lib.rs

1//! Lift decoded [`sleigh::Instruction`]s into QCode.
2//!
3//! This crate is the integration boundary between `wazabin-sleigh` and
4//! `qcode`. It consumes SLEIGH's flat p-code API rather
5//! than its source-shaped AST, keeping both core crates independent.
6//!
7//! Construct a [`SleighLifter`] once per compiled specification. Its
8//! [`SleighLifter::new_context`] method clones a prebuilt QCode context with
9//! spaces, registers, and user p-code operations already installed. Reuse an
10//! [`AddressIndex`] with [`SleighLifter::lift_instruction_indexed`] when
11//! lifting multiple instructions.
12//!
13//! # Example
14//!
15//! Decode one x86-64 instruction and lift it into a QCode context:
16//!
17//! ```no_run
18//! use sleigh::Decoder;
19//! use sleigh_precompile::x64;
20//! use qcode::address_index::AddressIndex;
21//! use wazabin_qcode_sleigh::{FlatPcode, SleighLifter};
22//!
23//! let spec = x64::spec();
24//!
25//! // `48 89 d8` is `MOV RAX, RBX`.
26//! let instruction = Decoder::new(spec)
27//!     .decode_one(0x1000, &[0x48, 0x89, 0xd8], &spec.new_context())
28//!     .expect("the bytes decode");
29//! let flat = FlatPcode::lower(&instruction).expect("the semantics emit");
30//!
31//! let lifter = SleighLifter::new(spec);
32//! let mut ctx = lifter.new_context();
33//! let mut addresses = AddressIndex::analyze(&ctx);
34//! lifter
35//!     .lift_pcode_indexed(&mut ctx, &mut addresses, &flat, None)
36//!     .expect("the p-code lowers");
37//!
38//! println!("{ctx}");
39//! ```
40//!
41//! # Memoized lifting
42//!
43//! Machine code repeats, and lowering the busiest x86-64 forms costs
44//! hundreds of microseconds each. A [`cache::LiftCache`] shared by the
45//! sessions of a lifter remembers what every encoding lowered to and
46//! replays it at any other address, exactly — see the [`cache`] module for
47//! how that is measured rather than assumed. A scratch session serves a hit
48//! without decoding or lowering anything:
49//!
50//! ```no_run
51//! use std::sync::Arc;
52//! use sleigh_precompile::x64;
53//! use wazabin_qcode_sleigh::{SleighLifter, cache::LiftCache, session::ScratchSession};
54//!
55//! let lifter = SleighLifter::new(x64::spec()).with_flat_control_flow();
56//! let cache = Arc::new(LiftCache::new(lifter.spec()));
57//! let mut session = ScratchSession::new(&lifter).with_cache(Arc::clone(&cache));
58//! for address in [0x1000, 0x2000] {
59//!     let lifted = session.lift(address, &[0xde, 0xc9]).expect("FMULP lifts");
60//!     println!("{} blocks, cached: {}", lifted.blocks().count(), lifted.is_cached());
61//! }
62//! println!("{:?}", cache.stats());
63//! ```
64//!
65//! The `qcode-dump` example prints every stage — disassembly text, SLEIGH AST,
66//! flat p-code, and the resulting QCode:
67//!
68//! ```sh
69//! cargo run --example qcode-dump -- 4889d8
70//! ```
71
72pub mod cache;
73pub mod decode;
74pub mod session;
75pub mod vm_source;
76
77use std::{borrow::Cow, cell::RefCell};
78
79use jstd::registry::Registry;
80use qcode::{
81    address_index::AddressIndex,
82    builder::Builder,
83    context::{ArchitectureId, Context},
84    lift::{
85        CallTarget, Construction, Continuation, Emitter, ExitArm, ExitKind, LiftTarget, Lifted,
86        Promotion, TargetError, Transfer,
87    },
88    space::SpaceType,
89    value::{
90        BlockId, FunctionBody, FunctionId, InstructionId, QCodeView, Renameable, TempId, Value,
91        ValueId,
92        insn::{Callee, PCodeOpId},
93        varnode::Varnode as QcodeVarnode,
94    },
95};
96use rustc_hash::FxHashMap as HashMap;
97use sleigh::{
98    CompiledSpec, Decoder, EmitError, Instruction, InstructionPcode, LabelId, Opcode, PcodeOp,
99    PcodePlan, PcodeSink, SPACE_CONST, SpaceId, SpecFingerprint, Varnode,
100};
101
102/// Already-flattened p-code of one instruction, with the identity of the
103/// specification that produced it.
104///
105/// Flat p-code names registers by space and offset, which mean what a lifter's
106/// specification says they mean; p-code of another specification would be
107/// lowered against the wrong registers, silently. A decoded [`Instruction`]
108/// carries its specification, so lowering it is checked; this type carries the
109/// same provenance for p-code that has left the instruction behind — kept for
110/// inspection, cached, or deserialized — so the flat entry points can check it
111/// too. [`lower`](Self::lower) takes it from the instruction; [`from_parts`](Self::from_parts)
112/// is for p-code stored with its fingerprint.
113#[derive(Debug, Clone, PartialEq, Eq)]
114pub struct FlatPcode {
115    fingerprint: SpecFingerprint,
116    address: u64,
117    length: usize,
118    pcode: InstructionPcode,
119}
120
121impl FlatPcode {
122    /// Flattens `instruction`'s semantics and records which specification
123    /// they came from.
124    pub fn lower(instruction: &Instruction<'_, '_>) -> Result<Self, EmitError> {
125        Ok(Self {
126            fingerprint: instruction.spec().fingerprint(),
127            address: instruction.address(),
128            length: instruction.len(),
129            pcode: instruction.pcode_ops()?,
130        })
131    }
132
133    /// Wraps p-code the caller kept, with the fingerprint of the specification
134    /// that produced it — which the caller must have stored alongside it, as
135    /// the p-code itself does not say. A wrong fingerprint is the caller's
136    /// bug: the lifter trusts it.
137    pub fn from_parts(
138        fingerprint: SpecFingerprint,
139        address: u64,
140        length: usize,
141        pcode: InstructionPcode,
142    ) -> Self {
143        Self {
144            fingerprint,
145            address,
146            length,
147            pcode,
148        }
149    }
150
151    /// The specification the p-code was produced by.
152    pub fn fingerprint(&self) -> SpecFingerprint {
153        self.fingerprint
154    }
155
156    pub fn address(&self) -> u64 {
157        self.address
158    }
159
160    pub fn length(&self) -> usize {
161        self.length
162    }
163
164    /// The operations, for inspection.
165    pub fn pcode(&self) -> &InstructionPcode {
166        &self.pcode
167    }
168
169    pub fn ops(&self) -> &[PcodeOp] {
170        &self.pcode.ops
171    }
172
173    /// Takes the operations back out.
174    pub fn into_pcode(self) -> InstructionPcode {
175        self.pcode
176    }
177}
178
179/// Failure while converting flat p-code to QCode.
180#[derive(Debug, Clone, PartialEq, Eq)]
181pub enum LiftError {
182    /// An operation did not have the number of operands required by its opcode.
183    InvalidArity {
184        opcode: Opcode,
185        expected: usize,
186        actual: usize,
187    },
188    /// A flat varnode is neither a constant, a SLEIGH unique temporary, nor a
189    /// register installed in this lifter's base context.
190    UnknownVarnode(Varnode),
191    /// A raw operation has no QCode equivalent yet.
192    UnsupportedOpcode(Opcode),
193    /// A relative local branch pointed outside its instruction's op sequence.
194    InvalidLocalBranch { op: usize, relative: i64 },
195    /// A direct control-flow target did not name an address-space varnode.
196    InvalidDirectTarget(Opcode),
197    /// A `SUBPIECE` range was outside its input value.
198    InvalidSubPiece { offset: usize, size: usize },
199    /// SLEIGH could not expand or flatten an instruction's semantics.
200    Sleigh(String),
201    /// The destination refused the instruction: its address is taken, a
202    /// target belongs to another function, or the index is stale.
203    Target(TargetError),
204    /// The context was not built for this lifter's specification: it carries
205    /// no architecture stamp, or another specification's.
206    IncompatibleContext,
207    /// The decoded instruction or flat p-code was produced by a different
208    /// specification than this lifter's, so its varnodes name registers this
209    /// lifter cannot map.
210    IncompatibleSpec,
211    /// The bytes did not decode.
212    Decode(sleigh::DecodeError),
213}
214
215impl std::fmt::Display for LiftError {
216    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
217        match self {
218            Self::InvalidArity {
219                opcode,
220                expected,
221                actual,
222            } => {
223                write!(f, "{opcode:?} needs {expected} inputs, got {actual}")
224            }
225            Self::UnknownVarnode(varnode) => write!(f, "unknown flat varnode {varnode:?}"),
226            Self::UnsupportedOpcode(opcode) => {
227                write!(f, "unsupported flat p-code opcode {opcode:?}")
228            }
229            Self::InvalidLocalBranch { op, relative } => {
230                write!(
231                    f,
232                    "local branch at op {op} has invalid relative target {relative}"
233                )
234            }
235            Self::InvalidDirectTarget(opcode) => write!(f, "invalid direct target for {opcode:?}"),
236            Self::InvalidSubPiece { offset, size } => {
237                write!(
238                    f,
239                    "SUBPIECE [{offset}..{}) is outside its input",
240                    offset + size
241                )
242            }
243            Self::Sleigh(error) => f.write_str(error),
244            Self::Target(error) => error.fmt(f),
245            Self::IncompatibleContext => {
246                f.write_str("the context was not built for this specification")
247            }
248            Self::IncompatibleSpec => {
249                f.write_str("the instruction was decoded by another specification")
250            }
251            Self::Decode(error) => error.fmt(f),
252        }
253    }
254}
255
256impl From<sleigh::DecodeError> for LiftError {
257    fn from(error: sleigh::DecodeError) -> Self {
258        Self::Decode(error)
259    }
260}
261
262impl std::error::Error for LiftError {}
263
264impl From<TargetError> for LiftError {
265    fn from(error: TargetError) -> Self {
266        Self::Target(error)
267    }
268}
269
270impl From<sleigh::EmitError> for LiftError {
271    fn from(error: sleigh::EmitError) -> Self {
272        Self::Sleigh(error.to_string())
273    }
274}
275
276/// Specification-specific state reused across all lifting sessions.
277///
278/// Building the base context interns every SLEIGH register and installs all
279/// spaces and `define pcodeop` names once. A session obtains a prebuilt clone via
280/// [`new_context`](Self::new_context), avoiding per-instruction registry setup
281/// and name hashing.
282pub struct SleighLifter<'spec> {
283    spec: &'spec CompiledSpec,
284    /// The specification's identity, as stamped on every context this lifter
285    /// builds and required of every one it lowers into.
286    architecture: ArchitectureId,
287    base: Context<'static>,
288    unique_space: SpaceId,
289    flat_control_flow: bool,
290}
291
292impl<'spec> SleighLifter<'spec> {
293    /// Lowers the guest's calls and returns as plain jumps.
294    ///
295    /// A guest `call` is a push and a jump, and a `ret` is a pop and an
296    /// indirect jump. SLEIGH already emits both halves: the stack write and the
297    /// stack read are ordinary p-code, and the `CALL`/`RETURN` operations on
298    /// top of them are nothing but the transfer of control. So lowering those
299    /// to [`Branch`](qcode::value::insn::Branch) and
300    /// [`BranchInd`](qcode::value::insn::BranchInd) loses no semantics.
301    ///
302    /// What it avoids is the *function structure* that a real `Call` implies —
303    /// a callee `FunctionId`, entered through that function's root block. An
304    /// emulator has no use for it: the guest keeps its own stack, and its code
305    /// is flat, with branch targets rather than a call graph. Worse, imposing
306    /// it is not merely useless but unsound for code discovered on demand,
307    /// because guest code branches across function boundaries freely, and a
308    /// block belongs to exactly one function's arena.
309    ///
310    /// A decompiler wants the opposite and gets it by default. This is for
311    /// running code, not for understanding it.
312    pub fn with_flat_control_flow(mut self) -> Self {
313        self.flat_control_flow = true;
314        self
315    }
316
317    /// Creates a lifter for `spec` and prebuilds its immutable QCode state.
318    pub fn new(spec: &'spec CompiledSpec) -> Self {
319        let architecture = ArchitectureId::new(spec.fingerprint().as_u128());
320        let mut base = Context::default();
321        base.set_architecture(architecture);
322        base.shared.default_space = spec.default_space();
323        let unique_space = spec
324            .spaces()
325            .find(|space| matches!(&space.space().ty, SpaceType::Unique))
326            .expect("compiled SLEIGH specifications always have a unique space")
327            .id;
328
329        // Both registries retain SLEIGH's stable IDs, so flat p-code space and
330        // user-op IDs can be used directly on the hot path.
331        let spaces: Registry<SpaceId, qcode::space::Space> =
332            spec.spaces().map(|space| space.space().clone()).collect();
333        base.load_spaces(spaces);
334        base.shared.pcode_ops = spec
335            .pcode_ops()
336            .map(Box::<str>::from)
337            .collect::<Registry<PCodeOpId, Box<str>>>();
338        for space in spec.spaces() {
339            if let Some(name) = space.name() {
340                base.shared.named_spaces.insert(Box::from(name), space.id);
341            }
342        }
343
344        for register in spec.registers() {
345            let id = QcodeVarnode::make(
346                &mut base,
347                register.offset() as i64,
348                register.size(),
349                register.space(),
350            )
351            .with_name(Cow::Owned(register.name().to_owned()))
352            .expect("SLEIGH register names are unique")
353            .id;
354            base.shared.registers.insert(register.id, id);
355        }
356
357        Self {
358            spec,
359            architecture,
360            base,
361            unique_space,
362            flat_control_flow: false,
363        }
364    }
365
366    /// Returns the compiled SLEIGH specification used by this lifter.
367    pub fn spec(&self) -> &'spec CompiledSpec {
368        self.spec
369    }
370
371    /// Whether the guest's calls and returns are lowered as jumps; see
372    /// [`with_flat_control_flow`](Self::with_flat_control_flow).
373    pub fn flat_control_flow(&self) -> bool {
374        self.flat_control_flow
375    }
376
377    /// Creates a QCode module initialized for this specification.
378    pub fn new_context(&self) -> Context<'static> {
379        self.base.clone()
380    }
381
382    /// Decodes one instruction from `bytes` and lowers its flat p-code into
383    /// `ctx`.
384    ///
385    /// This is the byte-oriented entry point for clients that need only the
386    /// SLEIGH-to-QCode boundary, not a binary container or recursive discovery
387    /// engine. Bulk lifters should retain an address index and use
388    /// [`decode_and_lift_indexed`](Self::decode_and_lift_indexed).
389    pub fn decode_and_lift(
390        &self,
391        ctx: &mut Context<'static>,
392        address: u64,
393        bytes: &[u8],
394        function: Option<FunctionId>,
395    ) -> Result<Lifted, LiftError> {
396        let mut addresses = AddressIndex::analyze(ctx);
397        self.decode_and_lift_indexed(ctx, &mut addresses, address, bytes, function)
398    }
399
400    /// Decodes one instruction from `bytes` and lowers it while reusing
401    /// `addresses` across a lifting session.
402    pub fn decode_and_lift_indexed(
403        &self,
404        ctx: &mut Context<'static>,
405        addresses: &mut AddressIndex,
406        address: u64,
407        bytes: &[u8],
408        function: Option<FunctionId>,
409    ) -> Result<Lifted, LiftError> {
410        let decode_context = self.spec.new_context();
411        let instruction = Decoder::new(self.spec).decode_one(address, bytes, &decode_context)?;
412        self.lift_instruction_indexed(ctx, addresses, &instruction, function)
413    }
414
415    /// Lowers a decoded instruction's flat p-code into `ctx`.
416    ///
417    /// This convenience method builds an address index. Bulk lifters should use
418    /// [`lift_instruction_indexed`](Self::lift_instruction_indexed) instead.
419    pub fn lift_instruction(
420        &self,
421        ctx: &mut Context<'static>,
422        instruction: &Instruction<'_, '_>,
423        function: Option<FunctionId>,
424    ) -> Result<Lifted, LiftError> {
425        let mut addresses = AddressIndex::analyze(ctx);
426        self.lift_instruction_indexed(ctx, &mut addresses, instruction, function)
427    }
428
429    /// Lowers a decoded instruction while reusing `addresses` across a lifting
430    /// session.
431    ///
432    /// This is the indexed entry point: `addresses` must be current for `ctx`,
433    /// which is the caller's to keep. Without `function`, the instruction is
434    /// lowered into the function at its address, made if there is none — a
435    /// function per isolated instruction, which bulk lifters avoid by naming
436    /// their host. See [`lift_into`](Self::lift_into) for the checked form.
437    pub fn lift_instruction_indexed(
438        &self,
439        ctx: &mut Context<'static>,
440        addresses: &mut AddressIndex,
441        instruction: &Instruction<'_, '_>,
442        function: Option<FunctionId>,
443    ) -> Result<Lifted, LiftError> {
444        // Both checks precede `function_for`, so a refused instruction never
445        // leaves even a host function behind.
446        self.check_instruction(instruction)?;
447        self.check_compatible(ctx)?;
448        let function = self.function_for(ctx, addresses, instruction.address(), function);
449        let mut target = LiftTarget::bind_indexed(ctx, addresses, function)?;
450        self.lift_into(&mut target, instruction)
451    }
452
453    /// Lowers a decoded instruction into a bound target.
454    ///
455    /// This is the one lowering of decoded input: every byte-oriented and
456    /// indexed entry point decodes or binds and then comes here. The
457    /// instruction is constructed transactionally — see
458    /// [`qcode::lift::target`] — so an error leaves the target as it was.
459    pub fn lift_into(
460        &self,
461        target: &mut LiftTarget<'_, 'static>,
462        instruction: &Instruction<'_, '_>,
463    ) -> Result<Lifted, LiftError> {
464        self.lower(target, instruction, self.flat_control_flow)
465    }
466
467    /// [`lift_into`](Self::lift_into) with the control-flow lowering chosen
468    /// by the caller rather than the lifter: a scratch session lowers calls
469    /// as jumps whatever the lifter would, since a callee function cannot be
470    /// discarded with the instruction that made it.
471    pub(crate) fn lower(
472        &self,
473        target: &mut LiftTarget<'_, 'static>,
474        instruction: &Instruction<'_, '_>,
475        flat: bool,
476    ) -> Result<Lifted, LiftError> {
477        self.check_instruction(instruction)?;
478        self.check_compatible(target.context())?;
479        let mut construction = target.begin(instruction.address(), instruction.len())?;
480        // The plan carries every fact needed before the builder borrows the
481        // function body, so no flat p-code vector is built or re-scanned.
482        instruction
483            .try_pcode_ops_streamed(|plan| self.emitter(&mut construction, plan, flat))?
484            .finish()?;
485        Ok(construction.commit()?)
486    }
487
488    /// Resolves the function an instruction at `address` belongs to.
489    fn function_for(
490        &self,
491        ctx: &mut Context<'static>,
492        addresses: &mut AddressIndex,
493        address: u64,
494        function: Option<FunctionId>,
495    ) -> FunctionId {
496        match function {
497            Some(function) => function,
498            None => FunctionBody::from_addr_or_create_indexed(ctx, addresses, address).id,
499        }
500    }
501
502    /// Refuses a context that was not built for this lifter's specification.
503    ///
504    /// Compatibility is identity, not resemblance: the context must carry the
505    /// [architecture stamp](Context::architecture) of this specification's
506    /// [fingerprint](CompiledSpec::fingerprint), which
507    /// [`new_context`](Self::new_context) — of this lifter or of any lifter for
508    /// the same specification — put there. A context of another specification
509    /// is refused even when its spaces and registers happen to coincide with
510    /// this one's, and so is a context built by hand or reloaded from before
511    /// stamps existed: this lifter's register map names varnodes by the ids
512    /// its own base assigned, and only the stamp says the destination assigned
513    /// them the same way.
514    fn check_compatible(&self, ctx: &Context<'static>) -> Result<(), LiftError> {
515        if ctx.architecture() != Some(self.architecture) {
516            return Err(LiftError::IncompatibleContext);
517        }
518        Ok(())
519    }
520
521    /// Refuses an instruction decoded by another specification.
522    ///
523    /// The instruction's varnodes only mean what this lifter's register map
524    /// says if it was decoded by this specification, so the fingerprints must
525    /// agree. A foreign-spec instruction would otherwise be lowered against
526    /// the wrong registers, silently.
527    fn check_instruction(&self, instruction: &Instruction<'_, '_>) -> Result<(), LiftError> {
528        self.check_fingerprint(instruction.spec().fingerprint())
529    }
530
531    fn check_fingerprint(&self, fingerprint: SpecFingerprint) -> Result<(), LiftError> {
532        if fingerprint != self.spec.fingerprint() {
533            return Err(LiftError::IncompatibleSpec);
534        }
535        Ok(())
536    }
537
538    /// Creates the emitter for one instruction, resolving all module-owned
539    /// blocks and callees from `plan` before borrowing the function body.
540    fn emitter<'c, 'a>(
541        &self,
542        construction: &'c mut Construction<'_, 'a, 'static>,
543        plan: &PcodePlan,
544        flat: bool,
545    ) -> Result<FlatEmitter<'_, 'static, 'c>, LiftError> {
546        let address = construction.address();
547        let length = construction.length();
548
549        let mut workspace = take_workspace();
550        // A direct jump — or the fall-through — to another function's entry
551        // is a tail call: it lands in a block of this instruction that holds
552        // the `TailCall`, made once the builder exists (see `FlatEmitter::new`).
553        let mut tails: Vec<(u64, Callee)> = Vec::new();
554        let filled = (|| {
555            for &target in plan.direct_branches() {
556                match construction.transfer_at(target, Promotion::Refuse)? {
557                    Transfer::Block(block) => {
558                        workspace.branches.insert(target, block);
559                    }
560                    Transfer::Function(callee) => tails.push((target, callee)),
561                }
562            }
563            for &target in plan.direct_calls() {
564                if flat {
565                    // Just another branch target, resolved in this same function.
566                    workspace
567                        .branches
568                        .insert(target, construction.block_at(target)?);
569                } else {
570                    workspace
571                        .calls
572                        .insert(target, construction.callee_at(target)?);
573                }
574            }
575            construction.transfer_at(address + length as u64, Promotion::Refuse)
576        })();
577        let next = match filled {
578            Ok(next) => next,
579            Err(error) => {
580                return_workspace(workspace);
581                return Err(error.into());
582            }
583        };
584
585        Ok(FlatEmitter::new(
586            next,
587            tails,
588            construction.emitter(),
589            self.spec,
590            self.unique_space,
591            workspace,
592            address,
593            length,
594            plan,
595            flat,
596        ))
597    }
598
599    /// Lowers already-flattened p-code, which must be this specification's
600    /// (see [`FlatPcode`]). This is useful for cached or differentially-tested
601    /// instruction semantics.
602    pub fn lift_pcode_indexed(
603        &self,
604        ctx: &mut Context<'static>,
605        addresses: &mut AddressIndex,
606        flat: &FlatPcode,
607        function: Option<FunctionId>,
608    ) -> Result<Lifted, LiftError> {
609        // Both checks precede `function_for`, so refused p-code never leaves
610        // even a host function behind.
611        self.check_fingerprint(flat.fingerprint())?;
612        self.check_compatible(ctx)?;
613        let function = self.function_for(ctx, addresses, flat.address(), function);
614        let mut target = LiftTarget::bind_indexed(ctx, addresses, function)?;
615        self.lift_pcode_into(&mut target, flat)
616    }
617
618    /// Lowers already-flattened p-code into a bound target. See
619    /// [`lift_pcode_indexed`](Self::lift_pcode_indexed).
620    ///
621    /// Unlike the streamed path this has no plan, so it recovers the same facts
622    /// by scanning the operations: their direct targets, and the operation
623    /// indices local branches resolve to.
624    pub fn lift_pcode_into(
625        &self,
626        target: &mut LiftTarget<'_, 'static>,
627        flat: &FlatPcode,
628    ) -> Result<Lifted, LiftError> {
629        self.check_fingerprint(flat.fingerprint())?;
630        self.check_compatible(target.context())?;
631        let address = flat.address();
632        let length = flat.length();
633        let pcode = flat.ops();
634        let plan = Self::plan_from_ops(pcode, self.flat_control_flow)?;
635        let mut construction = target.begin(address, length)?;
636        let mut emitter = self.emitter(&mut construction, &plan.plan, self.flat_control_flow)?;
637        for (index, op) in pcode.iter().enumerate() {
638            if let Some(&label) = plan.labels.get(&index) {
639                emitter.label(label);
640            }
641            match (op.opcode, op.inputs.first()) {
642                (Opcode::Branch | Opcode::CBranch, Some(target)) if target.space == SPACE_CONST => {
643                    let target = Self::local_target(index, target.offset, pcode.len())?;
644                    let condition = (op.opcode == Opcode::CBranch)
645                        .then(|| op.inputs.get(1).copied())
646                        .flatten();
647                    match plan.labels.get(&target) {
648                        Some(&label) => emitter.branch_label(op.opcode, label, condition),
649                        // A branch past the last operation is the machine
650                        // instruction's fall-through, not a local block.
651                        None => emitter.branch_next(op.opcode, condition),
652                    }
653                }
654                _ => emitter.op(op.opcode, op.output, &op.inputs),
655            }
656        }
657        emitter.finish()?;
658        Ok(construction.commit()?)
659    }
660
661    /// Rebuilds the plan facts of an already-flattened instruction.
662    fn plan_from_ops(pcode: &[PcodeOp], flat_control_flow: bool) -> Result<VectorPlan, LiftError> {
663        let mut plan = PcodePlan::default();
664        let mut labels = HashMap::default();
665        for (index, op) in pcode.iter().enumerate() {
666            let Some(target) = op.inputs.first() else {
667                continue;
668            };
669            match op.opcode {
670                Opcode::Branch | Opcode::CBranch if target.space == SPACE_CONST => {
671                    let target = Self::local_target(index, target.offset, pcode.len())?;
672                    if target < pcode.len() && !labels.contains_key(&target) {
673                        labels.insert(target, plan.declare_label(&format!("pcode_{target}")));
674                    }
675                }
676                Opcode::Branch | Opcode::CBranch => plan.declare_direct_branch(target.offset),
677                Opcode::Call if target.space != SPACE_CONST => {
678                    if flat_control_flow {
679                        plan.declare_direct_branch(target.offset);
680                    } else {
681                        plan.declare_direct_call(target.offset);
682                    }
683                }
684                _ => {}
685            }
686        }
687        Ok(VectorPlan { plan, labels })
688    }
689
690    fn local_target(op: usize, raw: u64, len: usize) -> Result<usize, LiftError> {
691        let relative = raw as i64;
692        let target = isize::try_from(relative)
693            .ok()
694            .and_then(|relative| op.checked_add_signed(relative))
695            .filter(|target| *target <= len);
696        target.ok_or(LiftError::InvalidLocalBranch { op, relative })
697    }
698}
699
700/// A plan recovered from already-flattened p-code, with the operation index
701/// each of its labels stands at.
702struct VectorPlan {
703    plan: PcodePlan,
704    labels: HashMap<usize, LabelId>,
705}
706
707/// One operation as it reaches the emitter, borrowed from either a streaming
708/// p-code sink or an already-flattened operation vector.
709struct OpRef<'a> {
710    opcode: Opcode,
711    output: Option<Varnode>,
712    inputs: &'a [Varnode],
713}
714
715/// The per-instruction tables of a [`FlatEmitter`], kept between
716/// instructions so their capacity is: an instruction fills them, the next
717/// one clears them, and neither allocates once the tables have seen the
718/// busiest lowering of the session.
719#[derive(Default)]
720struct Workspace {
721    unique_storage: HashMap<Varnode, UniqueSlot>,
722    dirty: Vec<Varnode>,
723    branches: HashMap<u64, BlockId>,
724    calls: HashMap<u64, Callee>,
725    labels: Vec<Option<BlockId>>,
726}
727
728impl Workspace {
729    fn clear(&mut self) {
730        self.unique_storage.clear();
731        self.dirty.clear();
732        self.branches.clear();
733        self.calls.clear();
734        self.labels.clear();
735    }
736}
737
738thread_local! {
739    /// The workspace of the last emitter on this thread, empty. A nested
740    /// lowering — there is none — would find it taken and start from empty.
741    static WORKSPACE: RefCell<Workspace> = RefCell::default();
742}
743
744fn take_workspace() -> Workspace {
745    WORKSPACE.with(|slot| std::mem::take(&mut *slot.borrow_mut()))
746}
747
748fn return_workspace(mut workspace: Workspace) {
749    workspace.clear();
750    WORKSPACE.with(|slot| *slot.borrow_mut() = workspace);
751}
752
753/// Where one instruction-local unique varnode lives.
754///
755/// Flat p-code writes its uniques as mutable locations, but nearly all of them
756/// are written once and read in the same straight-line run of operations, so
757/// the emitter keeps a unique as the SSA value last written to it and gives it
758/// memory only when that value has to cross a block boundary — or when it is
759/// read before it is written, which is the p-code's bug to have and the
760/// temporary's to absorb.
761#[derive(Default, Clone, Copy)]
762struct UniqueSlot {
763    /// The SSA value holding the unique's contents, valid within the current
764    /// block; a value from an earlier block is dropped when a new one opens.
765    value: Option<ValueId>,
766    /// The body-local temporary the unique spills to, made on first need.
767    temp: Option<TempId>,
768    /// Whether `value` has been written since it was last stored to `temp`.
769    dirty: bool,
770}
771
772/// Emits QCode for one instruction's flat p-code.
773///
774/// The emitter is a [`PcodeSink`]: it never sees a flat p-code vector, and it
775/// takes its whole-instruction facts — the blocks its direct branches and
776/// calls reach — from the plan its owner resolved before borrowing the body.
777struct FlatEmitter<'spec, 'str, 'ctx> {
778    /// The builder into the construction, which also takes the record of the
779    /// instruction's blocks and exits at the operations that open and take
780    /// them — before `flat` decides what they lower to.
781    builder: Emitter<'ctx, 'str>,
782    /// The specification, which names the register a varnode is; the
783    /// context maps that register to its varnode.
784    spec: &'spec CompiledSpec,
785    /// SLEIGH's unique space, whose varnodes are instruction-local.
786    unique_space: SpaceId,
787    /// Per-instruction unique-space locations. Unlike register locations these
788    /// must not be shared, because SLEIGH's unique space is instruction-local.
789    unique_storage: HashMap<Varnode, UniqueSlot>,
790    /// The uniques written since their last spill, in write order, so a spill
791    /// stores them deterministically.
792    dirty: Vec<Varnode>,
793    /// Whether the plan has a label that opens a block of this instruction.
794    /// Without one, no p-code after an unconditional transfer can run, so
795    /// nothing needs to survive it.
796    has_local_blocks: bool,
797    branches: HashMap<u64, BlockId>,
798    calls: HashMap<u64, Callee>,
799    /// Blocks for the plan's instruction-local labels, made on first mention.
800    labels: Vec<Option<BlockId>>,
801    /// The fall-through block: `None` until first needed when the next
802    /// instruction is another function's entry (`next_tail`), since most
803    /// instructions before a function entry (a `ret`, a `jmp`) never fall
804    /// through and a tail-call block made for nothing would be dead.
805    next: Option<BlockId>,
806    /// The function the fall-through tail-calls, when it is another's entry.
807    next_tail: Option<Callee>,
808    /// The tail-call blocks made so far, by target address.
809    tail_blocks: Vec<(u64, BlockId)>,
810    address: u64,
811    length: usize,
812    fallthrough: usize,
813    /// Lower the guest's calls and returns as jumps. See
814    /// [`SleighLifter::with_flat_control_flow`].
815    flat: bool,
816    /// A sink cannot fail, so the first failure is latched and the rest of the
817    /// instruction is ignored; its caller discards a partial instruction.
818    error: Option<LiftError>,
819}
820
821impl<'spec, 'str, 'ctx> FlatEmitter<'spec, 'str, 'ctx> {
822    #[allow(clippy::too_many_arguments)]
823    fn new(
824        next: Transfer,
825        tails: Vec<(u64, Callee)>,
826        builder: Emitter<'ctx, 'str>,
827        spec: &'spec CompiledSpec,
828        unique_space: SpaceId,
829        workspace: Workspace,
830        address: u64,
831        length: usize,
832        plan: &PcodePlan,
833        flat: bool,
834    ) -> Self {
835        let (next, next_tail) = match next {
836            Transfer::Block(block) => (Some(block), None),
837            Transfer::Function(callee) => (None, Some(callee)),
838        };
839        let terminal =
840            (0..plan.labels().len()).any(|index| plan.is_terminal(LabelId::from_index(index)));
841        let mut this = Self {
842            builder,
843            spec,
844            unique_space,
845            unique_storage: workspace.unique_storage,
846            dirty: workspace.dirty,
847            has_local_blocks: (0..plan.labels().len())
848                .any(|index| !plan.is_terminal(LabelId::from_index(index))),
849            branches: workspace.branches,
850            calls: workspace.calls,
851            labels: workspace.labels,
852            next,
853            next_tail,
854            tail_blocks: Vec::new(),
855            address,
856            length,
857            fallthrough: 0,
858            flat,
859            error: None,
860        };
861        for (target, callee) in tails {
862            let block = this.tail_block(target, callee);
863            this.branches.insert(target, block);
864        }
865        // A terminal label is the instruction's fall-through, not a block, so
866        // an instruction that has one needs the fall-through block now.
867        let next = if terminal {
868            Some(this.next_block())
869        } else {
870            None
871        };
872        this.labels.extend(
873            (0..plan.labels().len())
874                .map(|index| next.filter(|_| plan.is_terminal(LabelId::from_index(index)))),
875        );
876        this
877    }
878
879    /// The fall-through block, made on first need when it is a tail call.
880    fn next_block(&mut self) -> BlockId {
881        if let Some(next) = self.next {
882            return next;
883        }
884        let callee = self
885            .next_tail
886            .expect("a fall-through is a block or a tail call");
887        let next = self.tail_block(self.address.wrapping_add(self.length as u64), callee);
888        self.next = Some(next);
889        next
890    }
891
892    /// A block of this instruction that tail-calls `callee`, the function at
893    /// `target`: where a direct transfer to another function's entry lands.
894    fn tail_block(&mut self, target: u64, callee: Callee) -> BlockId {
895        if let Some(&(_, block)) = self.tail_blocks.iter().find(|(at, _)| *at == target) {
896            return block;
897        }
898        let address = self.address;
899        let block = self.fresh_block(|| format!("pcode_tail_{address:x}_{target:x}"));
900        self.builder.block(block);
901        let current = self.builder.current_block();
902        self.builder.switch_to_block(block);
903        self.builder.set_address(address);
904        self.builder.push_tail_call(callee);
905        self.builder.clear_address();
906        self.builder.switch_to_block(current);
907        self.tail_blocks.push((target, block));
908        block
909    }
910
911    /// Closes the instruction. Running off the end of its p-code is a
912    /// fall-through.
913    fn finish(mut self) -> Result<(), LiftError> {
914        if let Some(error) = self.error.take() {
915            return Err(error);
916        }
917        if !self.builder.is_terminated() {
918            let next = self.next_block();
919            let site = self.builder.push_branch(next).id;
920            self.builder
921                .exit(site, ExitArm::Unconditional, ExitKind::Fallthrough);
922        }
923        Ok(())
924    }
925
926    /// Branches to the instruction's fall-through, the target of a local
927    /// branch past the last operation.
928    fn branch_next(&mut self, opcode: Opcode, condition: Option<Varnode>) {
929        let next = self.next_block();
930        if let Some((site, arm)) = self.branch_to(opcode, next, condition) {
931            self.builder.exit(site, arm, ExitKind::Fallthrough);
932        }
933    }
934
935    fn block_for(&mut self, label: LabelId) -> BlockId {
936        if let Some(block) = self.labels[label.index()] {
937            return block;
938        }
939        let (address, index) = (self.address, label.index());
940        let block = self.fresh_block(|| format!("pcode_{address:x}_{index}"));
941        self.labels[label.index()] = Some(block);
942        self.builder.block(block);
943        block
944    }
945
946    /// Terminates the current block with a branch to `target`, conditionally
947    /// if `opcode` says so, and continues in the not-taken block. Returns the
948    /// branch and which of its arms reaches `target`, or nothing once the
949    /// instruction has failed.
950    fn branch_to(
951        &mut self,
952        opcode: Opcode,
953        target: BlockId,
954        condition: Option<Varnode>,
955    ) -> Option<(InstructionId, ExitArm)> {
956        let condition = match (opcode, condition) {
957            (Opcode::CBranch, Some(condition)) => match self.raw_value(condition) {
958                Ok(condition) => Some(self.ensure_bool(condition)),
959                Err(error) => {
960                    self.fail(error);
961                    return None;
962                }
963            },
964            (Opcode::CBranch, None) => {
965                self.fail(LiftError::InvalidArity {
966                    opcode,
967                    expected: 2,
968                    actual: 1,
969                });
970                return None;
971            }
972            _ => None,
973        };
974        Some(match condition {
975            Some(condition) => {
976                self.leave_block(true);
977                let fallthrough = self.open_fallthrough();
978                let site = self.builder.push_cbranch(condition, target, fallthrough).id;
979                self.builder.switch_to_block(fallthrough);
980                self.enter_block();
981                (site, ExitArm::Taken)
982            }
983            None => {
984                self.leave_block(false);
985                (self.builder.push_branch(target).id, ExitArm::Unconditional)
986            }
987        })
988    }
989
990    fn fail(&mut self, error: LiftError) {
991        self.error.get_or_insert(error);
992    }
993
994    fn open_fallthrough(&mut self) -> BlockId {
995        let (address, index) = (self.address, self.fallthrough);
996        let label = self.fresh_block(|| format!("pcode_fallthrough_{address:x}_{index}"));
997        self.fallthrough += 1;
998        self.builder.block(label);
999        label
1000    }
1001
1002    /// A new block of the host for this instruction's own control flow,
1003    /// named by `name` when the builder names things. The emitter keeps its
1004    /// own handle on every block it makes, so it never looks one up by name.
1005    fn fresh_block(&mut self, name: impl FnOnce() -> String) -> BlockId {
1006        if self.builder.naming() {
1007            self.builder.get_or_make_local_label(Cow::Owned(name()))
1008        } else {
1009            self.builder.push_anonymous_block()
1010        }
1011    }
1012
1013    /// Opens a block for p-code that follows a terminator: the continuation
1014    /// of a call, or code only local branches reach.
1015    fn open_continuation(&mut self) {
1016        if !self.builder.is_terminated() {
1017            return;
1018        }
1019        let label = self.open_fallthrough();
1020        self.builder.switch_to_block(label);
1021        self.builder.continue_in(label);
1022        self.enter_block();
1023    }
1024
1025    fn input(&mut self, op: &OpRef<'_>, index: usize) -> Result<ValueId, LiftError> {
1026        let value = self.input_varnode(op, index)?;
1027        self.value(value)
1028    }
1029
1030    /// An input read as held, for the consumers that want a `bool`.
1031    fn raw_input(&mut self, op: &OpRef<'_>, index: usize) -> Result<ValueId, LiftError> {
1032        let value = self.input_varnode(op, index)?;
1033        self.raw_value(value)
1034    }
1035
1036    fn input_varnode(&self, op: &OpRef<'_>, index: usize) -> Result<Varnode, LiftError> {
1037        op.inputs
1038            .get(index)
1039            .copied()
1040            .ok_or(LiftError::InvalidArity {
1041                opcode: op.opcode,
1042                expected: index + 1,
1043                actual: op.inputs.len(),
1044            })
1045    }
1046
1047    /// Reads a varnode as an integer operand. A unique that holds a `bool`
1048    /// value — a comparison's result — is widened to its byte here, which is
1049    /// what its memory temporary would have held.
1050    fn value(&mut self, varnode: Varnode) -> Result<ValueId, LiftError> {
1051        let value = self.raw_value(varnode)?;
1052        let ty = self.builder.view().type_of(value);
1053        if self.builder.shr().types.is_bool(ty) {
1054            return Ok(self.builder.push_zext(value, 1).id());
1055        }
1056        Ok(value)
1057    }
1058
1059    /// Reads a varnode as it is held: a `bool` stays a `bool`, for the
1060    /// consumers that want one.
1061    fn raw_value(&mut self, varnode: Varnode) -> Result<ValueId, LiftError> {
1062        if varnode.space == SPACE_CONST {
1063            return Ok(self.builder.shr().get_const(varnode.offset, varnode.size));
1064        }
1065        if varnode.space == self.unique_space {
1066            return Ok(self.read_unique(varnode));
1067        }
1068        let value = self.base_storage(varnode)?;
1069        Ok(self.builder.ensure_local(value))
1070    }
1071
1072    /// Resolves an architectural varnode's QCode location: the specification
1073    /// says which register it is, the context which varnode that register has.
1074    fn base_storage(&self, varnode: Varnode) -> Result<ValueId, LiftError> {
1075        self.spec
1076            .register_at(varnode)
1077            .and_then(|register| self.builder.shr().registers.get(&register))
1078            .copied()
1079            .map(ValueId::Varnode)
1080            .ok_or(LiftError::UnknownVarnode(varnode))
1081    }
1082
1083    /// The SSA value of a unique: the one last written in this block, else a
1084    /// load of its temporary, which is made here if the unique is read before
1085    /// it is ever written. Each unique varnode — by space, offset and size —
1086    /// has its own slot, so overlapping uniques stay isolated as their storage
1087    /// identity requires.
1088    fn read_unique(&mut self, varnode: Varnode) -> ValueId {
1089        let slot = self.unique_storage.entry(varnode).or_default();
1090        if let Some(value) = slot.value {
1091            return value;
1092        }
1093        let temp = *slot
1094            .temp
1095            .get_or_insert_with(|| self.builder.make_temp(varnode.size));
1096        let value = self.builder.ensure_local(ValueId::Temp(temp));
1097        let slot = self
1098            .unique_storage
1099            .get_mut(&varnode)
1100            .expect("the slot was just made");
1101        slot.value = Some(value);
1102        slot.dirty = false;
1103        value
1104    }
1105
1106    fn write(&mut self, output: Option<Varnode>, value: ValueId) -> Result<(), LiftError> {
1107        let Some(output) = output else {
1108            return Ok(());
1109        };
1110        if output.space == SPACE_CONST {
1111            return Err(LiftError::UnknownVarnode(output));
1112        }
1113        if output.space == self.unique_space {
1114            let slot = self.unique_storage.entry(output).or_default();
1115            slot.value = Some(value);
1116            if !slot.dirty {
1117                slot.dirty = true;
1118                self.dirty.push(output);
1119            }
1120            return Ok(());
1121        }
1122        let destination = self.base_storage(output)?;
1123        self.builder.push_copy(value, destination);
1124        Ok(())
1125    }
1126
1127    /// Stores every unique written since the last spill to its temporary, so
1128    /// a block the control flow reaches next can load it.
1129    fn spill(&mut self) {
1130        for varnode in std::mem::take(&mut self.dirty) {
1131            let slot = self
1132                .unique_storage
1133                .get_mut(&varnode)
1134                .expect("a dirty unique has a slot");
1135            let value = slot.value.expect("a dirty unique holds a value");
1136            slot.dirty = false;
1137            let temp = *slot
1138                .temp
1139                .get_or_insert_with(|| self.builder.make_temp(varnode.size));
1140            self.builder.push_copy(value, ValueId::Temp(temp));
1141        }
1142    }
1143
1144    /// Prepares to end the current block with a transfer. Uniques must be in
1145    /// memory if p-code of this instruction can run afterwards: always when
1146    /// the transfer `continues` in a block of its own (a conditional branch's
1147    /// fall-through, a call's continuation), otherwise only when a label can
1148    /// bring control back.
1149    fn leave_block(&mut self, continues: bool) {
1150        if continues || self.has_local_blocks {
1151            self.spill();
1152        }
1153    }
1154
1155    /// Notes that a new block is current: values held from the previous one
1156    /// are not usable in it, so the next read of each unique loads it.
1157    fn enter_block(&mut self) {
1158        debug_assert!(self.dirty.is_empty(), "a block was left without a spill");
1159        for slot in self.unique_storage.values_mut() {
1160            slot.value = None;
1161        }
1162    }
1163
1164    fn emit_op(&mut self, op: &OpRef<'_>) -> Result<(), LiftError> {
1165        use Opcode::*;
1166        let unary = |this: &mut Self, f: fn(&mut Builder<'str, 'ctx>, ValueId) -> ValueId| {
1167            let input = this.input(op, 0)?;
1168            let value = f(&mut this.builder, input);
1169            this.write(op.output, value)
1170        };
1171        let binary =
1172            |this: &mut Self, f: fn(&mut Builder<'str, 'ctx>, ValueId, ValueId) -> ValueId| {
1173                let lhs = this.input(op, 0)?;
1174                let rhs = this.input(op, 1)?;
1175                let value = f(&mut this.builder, lhs, rhs);
1176                this.write(op.output, value)
1177            };
1178        match op.opcode {
1179            Copy => {
1180                let value = self.input(op, 0)?;
1181                self.write(op.output, value)
1182            }
1183            IntAdd => binary(self, |b, a, c| b.push_add(a, c).id()),
1184            IntSub => binary(self, |b, a, c| b.push_sub(a, c).id()),
1185            IntMult => binary(self, |b, a, c| b.push_mul(a, c).id()),
1186            IntDiv => binary(self, |b, a, c| b.push_div(a, c).id()),
1187            IntSDiv => binary(self, |b, a, c| b.push_sdiv(a, c).id()),
1188            IntRem => binary(self, |b, a, c| b.push_mod(a, c).id()),
1189            IntSRem => binary(self, |b, a, c| b.push_smod(a, c).id()),
1190            IntAnd => binary(self, |b, a, c| b.push_bit_and(a, c).id()),
1191            IntOr => binary(self, |b, a, c| b.push_bit_or(a, c).id()),
1192            IntXor => binary(self, |b, a, c| b.push_bit_xor(a, c).id()),
1193            IntLeft => binary(self, |b, a, c| b.push_shl(a, c).id()),
1194            IntRight => binary(self, |b, a, c| b.push_shr(a, c).id()),
1195            IntSRight => binary(self, |b, a, c| b.push_sshr(a, c).id()),
1196            IntEqual => binary(self, |b, a, c| b.push_eq(a, c).id()),
1197            IntNotEqual => binary(self, |b, a, c| b.push_ne(a, c).id()),
1198            IntSLess => binary(self, |b, a, c| b.push_slt(a, c).id()),
1199            IntSLessEqual => binary(self, |b, a, c| b.push_sle(a, c).id()),
1200            IntLess => binary(self, |b, a, c| b.push_lt(a, c).id()),
1201            IntLessEqual => binary(self, |b, a, c| b.push_le(a, c).id()),
1202            IntCarry => binary(self, |b, a, c| b.push_carry(a, c).id()),
1203            IntSCarry => binary(self, |b, a, c| b.push_scarry(a, c).id()),
1204            IntSBorrow => binary(self, |b, a, c| b.push_sborrow(a, c).id()),
1205            IntNegate => unary(self, |b, a| b.push_bit_negate(a).id()),
1206            Int2Comp => unary(self, |b, a| b.push_neg(a).id()),
1207            BoolNegate => {
1208                let input = self.raw_input(op, 0)?;
1209                let input = self.ensure_bool(input);
1210                let value = self.builder.push_bool_not(input).id();
1211                self.write(op.output, value)
1212            }
1213            BoolXor => self.bool_binop(op, |b, a, c| b.push_bool_xor(a, c).id()),
1214            BoolAnd => self.bool_binop(op, |b, a, c| b.push_bool_and(a, c).id()),
1215            BoolOr => self.bool_binop(op, |b, a, c| b.push_bool_or(a, c).id()),
1216            FloatAdd => binary(self, |b, a, c| b.push_fadd(a, c).id()),
1217            FloatSub => binary(self, |b, a, c| b.push_fsub(a, c).id()),
1218            FloatMult => binary(self, |b, a, c| b.push_fmul(a, c).id()),
1219            FloatDiv => binary(self, |b, a, c| b.push_fdiv(a, c).id()),
1220            FloatEqual => binary(self, |b, a, c| b.push_feq(a, c).id()),
1221            FloatNotEqual => binary(self, |b, a, c| b.push_fne(a, c).id()),
1222            FloatLess => binary(self, |b, a, c| b.push_flt(a, c).id()),
1223            FloatLessEqual => binary(self, |b, a, c| b.push_fle(a, c).id()),
1224            FloatNeg => unary(self, |b, a| b.push_fneg(a).id()),
1225            FloatNan => unary(self, |b, a| b.push_is_nan(a).id()),
1226            FloatAbs => unary(self, |b, a| b.push_abs(a).id()),
1227            FloatSqrt => unary(self, |b, a| b.push_sqrt(a).id()),
1228            FloatCeil => unary(self, |b, a| b.push_ceil(a).id()),
1229            FloatFloor => unary(self, |b, a| b.push_floor(a).id()),
1230            FloatRound => unary(self, |b, a| b.push_round(a).id()),
1231            IntZext => self.convert(op, |b, value, size| b.push_zext(value, size).id()),
1232            IntSext => self.convert(op, |b, value, size| b.push_sext(value, size).id()),
1233            FloatInt2Float => {
1234                self.convert(op, |b, value, size| b.push_int_to_float(value, size).id())
1235            }
1236            FloatFloat2Float => {
1237                self.convert(op, |b, value, size| b.push_float_to_float(value, size).id())
1238            }
1239            FloatTrunc => self.convert(op, |b, value, size| b.push_trunc(value, size).id()),
1240            PopCount => self.convert(op, |b, value, size| b.push_popcount(value, size).id()),
1241            LzCount => self.convert(op, |b, value, size| b.push_lzcount(value, size).id()),
1242            Load => {
1243                let output = op.output.ok_or(LiftError::InvalidArity {
1244                    opcode: op.opcode,
1245                    expected: 2,
1246                    actual: op.inputs.len(),
1247                })?;
1248                let space = self.space(op, 0)?;
1249                let ptr = self.input(op, 1)?;
1250                let value = self.builder.push_load::<true>(ptr, output.size, space).id();
1251                self.write(Some(output), value)
1252            }
1253            Store => {
1254                let space = self.space(op, 0)?;
1255                let ptr = self.input(op, 1)?;
1256                let value = self.input(op, 2)?;
1257                self.builder.push_store(value, ptr, space);
1258                Ok(())
1259            }
1260            SubPiece => {
1261                let src = self.input(op, 0)?;
1262                let offset = self.input_raw(op, 1)? as usize;
1263                let output = op.output.ok_or(LiftError::InvalidArity {
1264                    opcode: op.opcode,
1265                    expected: 2,
1266                    actual: op.inputs.len(),
1267                })?;
1268                let value = self
1269                    .builder
1270                    .get_range(src, offset..offset + output.size)
1271                    .ok_or(LiftError::InvalidSubPiece {
1272                        offset,
1273                        size: output.size,
1274                    })?
1275                    .id();
1276                self.write(Some(output), value)
1277            }
1278            CallOther => {
1279                let id = PCodeOpId::new(self.input_raw(op, 0)? as usize);
1280                let mut args = Vec::with_capacity(op.inputs.len().saturating_sub(1));
1281                for input in op.inputs.iter().skip(1).copied() {
1282                    args.push(self.value(input)?);
1283                }
1284                let size = op.output.map_or(0, |output| output.size);
1285                let value = self.builder.push_pcode_op(id, args, None, size).id();
1286                self.write(op.output, value)
1287            }
1288            Branch | CBranch => self.direct_branch(op),
1289            BranchInd => {
1290                let target = self.input(op, 0)?;
1291                self.leave_block(false);
1292                let site = self.builder.push_branchind(target).id;
1293                self.builder
1294                    .exit(site, ExitArm::Unconditional, ExitKind::BranchInd);
1295                Ok(())
1296            }
1297            Call => {
1298                let target = op.inputs.first().ok_or(LiftError::InvalidArity {
1299                    opcode: op.opcode,
1300                    expected: 1,
1301                    actual: 0,
1302                })?;
1303                // The return address is already on the guest's stack by now —
1304                // SLEIGH wrote it with ordinary p-code — so in flat mode all
1305                // that is left of the call is the jump.
1306                self.leave_block(!self.flat);
1307                let site = if self.flat {
1308                    let block = self
1309                        .branches
1310                        .get(&target.offset)
1311                        .copied()
1312                        .ok_or(LiftError::InvalidDirectTarget(op.opcode))?;
1313                    self.builder.push_branch(block).id
1314                } else {
1315                    let callee = self
1316                        .calls
1317                        .get(&target.offset)
1318                        .copied()
1319                        .ok_or(LiftError::InvalidDirectTarget(op.opcode))?;
1320                    self.builder.push_call(callee).id
1321                };
1322                self.builder.exit(
1323                    site,
1324                    ExitArm::Unconditional,
1325                    ExitKind::Call {
1326                        callee: CallTarget::Address(target.offset),
1327                        continuation: Continuation::Next,
1328                    },
1329                );
1330                Ok(())
1331            }
1332            CallInd => {
1333                let target = self.input(op, 0)?;
1334                self.leave_block(!self.flat);
1335                let site = if self.flat {
1336                    self.builder.push_branchind(target).id
1337                } else {
1338                    self.builder.push_call_ind(target).id
1339                };
1340                self.builder.exit(
1341                    site,
1342                    ExitArm::Unconditional,
1343                    ExitKind::CallInd {
1344                        continuation: Continuation::Next,
1345                    },
1346                );
1347                Ok(())
1348            }
1349            Return => {
1350                let target = self.input(op, 0)?;
1351                // The stack has already been popped into this value; returning
1352                // is a jump to it.
1353                self.leave_block(false);
1354                let site = if self.flat {
1355                    self.builder.push_branchind(target).id
1356                } else {
1357                    self.builder.push_return(target).id
1358                };
1359                self.builder
1360                    .exit(site, ExitArm::Unconditional, ExitKind::Return);
1361                Ok(())
1362            }
1363            _ => Err(LiftError::UnsupportedOpcode(op.opcode)),
1364        }
1365    }
1366
1367    fn ensure_bool(&mut self, value: ValueId) -> ValueId {
1368        let ty = self.builder.view().type_of(value);
1369        if self.builder.shr().types.is_bool(ty) {
1370            return value;
1371        }
1372        let size = self.builder.shr().types.size_of(ty).max(1);
1373        let zero = self.builder.shr().get_const(0, size);
1374        self.builder.push_ne(value, zero).id()
1375    }
1376
1377    fn bool_binop(
1378        &mut self,
1379        op: &OpRef<'_>,
1380        f: fn(&mut Builder<'str, 'ctx>, ValueId, ValueId) -> ValueId,
1381    ) -> Result<(), LiftError> {
1382        let lhs = self.raw_input(op, 0)?;
1383        let lhs = self.ensure_bool(lhs);
1384        let rhs = self.raw_input(op, 1)?;
1385        let rhs = self.ensure_bool(rhs);
1386        let value = f(&mut self.builder, lhs, rhs);
1387        self.write(op.output, value)
1388    }
1389
1390    fn convert(
1391        &mut self,
1392        op: &OpRef<'_>,
1393        f: fn(&mut Builder<'str, 'ctx>, ValueId, usize) -> ValueId,
1394    ) -> Result<(), LiftError> {
1395        let output = op.output.ok_or(LiftError::InvalidArity {
1396            opcode: op.opcode,
1397            expected: 1,
1398            actual: op.inputs.len(),
1399        })?;
1400        let input = self.input(op, 0)?;
1401        let value = f(&mut self.builder, input, output.size);
1402        self.write(Some(output), value)
1403    }
1404
1405    fn input_raw(&self, op: &OpRef<'_>, index: usize) -> Result<u64, LiftError> {
1406        let value = op.inputs.get(index).ok_or(LiftError::InvalidArity {
1407            opcode: op.opcode,
1408            expected: index + 1,
1409            actual: op.inputs.len(),
1410        })?;
1411        if value.space != SPACE_CONST {
1412            return Err(LiftError::InvalidDirectTarget(op.opcode));
1413        }
1414        Ok(value.offset)
1415    }
1416
1417    fn space(&self, op: &OpRef<'_>, index: usize) -> Result<SpaceId, LiftError> {
1418        let raw = self.input_raw(op, index)?;
1419        usize::try_from(raw)
1420            .ok()
1421            .map(SpaceId::new)
1422            .ok_or(LiftError::InvalidDirectTarget(op.opcode))
1423    }
1424
1425    /// Emits a branch out of this instruction. Instruction-local targets
1426    /// never reach here: they arrive as [`PcodeSink::branch_label`].
1427    fn direct_branch(&mut self, op: &OpRef<'_>) -> Result<(), LiftError> {
1428        let target = op.inputs.first().ok_or(LiftError::InvalidArity {
1429            opcode: op.opcode,
1430            expected: 1 + usize::from(op.opcode == Opcode::CBranch),
1431            actual: 0,
1432        })?;
1433        if target.space == SPACE_CONST {
1434            return Err(LiftError::InvalidDirectTarget(op.opcode));
1435        }
1436        let block = *self
1437            .branches
1438            .get(&target.offset)
1439            .ok_or(LiftError::InvalidDirectTarget(op.opcode))?;
1440        let condition = op.inputs.get(1).copied();
1441        if let Some((site, arm)) = self.branch_to(op.opcode, block, condition) {
1442            self.builder.exit(
1443                site,
1444                arm,
1445                ExitKind::Branch {
1446                    target: target.offset,
1447                },
1448            );
1449        }
1450        Ok(())
1451    }
1452}
1453
1454impl Drop for FlatEmitter<'_, '_, '_> {
1455    fn drop(&mut self) {
1456        return_workspace(Workspace {
1457            unique_storage: std::mem::take(&mut self.unique_storage),
1458            dirty: std::mem::take(&mut self.dirty),
1459            branches: std::mem::take(&mut self.branches),
1460            calls: std::mem::take(&mut self.calls),
1461            labels: std::mem::take(&mut self.labels),
1462        });
1463    }
1464}
1465
1466impl PcodeSink for FlatEmitter<'_, '_, '_> {
1467    fn op(&mut self, opcode: Opcode, output: Option<Varnode>, inputs: &[Varnode]) {
1468        if self.error.is_some() {
1469            return;
1470        }
1471        self.open_continuation();
1472        self.builder.set_address(self.address);
1473        let op = OpRef {
1474            opcode,
1475            output,
1476            inputs,
1477        };
1478        if let Err(error) = self.emit_op(&op) {
1479            self.fail(error);
1480        }
1481        self.builder.clear_address();
1482    }
1483
1484    fn label(&mut self, label: LabelId) {
1485        if self.error.is_some() {
1486            return;
1487        }
1488        let block = self.block_for(label);
1489        // A terminal label is the instruction's fall-through: execution
1490        // reaches it by falling out of the instruction, not through a block.
1491        if Some(block) == self.next || self.builder.current_block() == block {
1492            return;
1493        }
1494        if !self.builder.is_terminated() {
1495            self.spill();
1496            self.builder.push_branch(block);
1497        }
1498        self.builder.switch_to_block(block);
1499        self.builder.continue_in(block);
1500        self.enter_block();
1501    }
1502
1503    fn branch_label(&mut self, opcode: Opcode, label: LabelId, condition: Option<Varnode>) {
1504        if self.error.is_some() {
1505            return;
1506        }
1507        self.open_continuation();
1508        self.builder.set_address(self.address);
1509        let target = self.block_for(label);
1510        if Some(target) == self.next {
1511            // A branch to the terminal label leaves the instruction.
1512            self.branch_next(opcode, condition);
1513        } else {
1514            self.branch_to(opcode, target, condition);
1515        }
1516        self.builder.clear_address();
1517    }
1518}
1519
1520#[cfg(test)]
1521mod tests {
1522    use super::{FlatPcode, SleighLifter};
1523    use qcode::address_index::AddressIndex;
1524    use qcode::lift::{CallTarget, Continuation, Exit, ExitArm, ExitKind, Lifted};
1525    use qcode::value::{BasicBlock, Instruction};
1526    use qcode_emulator::Emulator;
1527    use sleigh::{CompiledSpec, Compiler, Decoder, SourceDb};
1528
1529    /// Lifts one x86-64 instruction at 0x1000 in both lowering modes.
1530    fn lift_x64_both_modes(bytes: &[u8]) -> [(qcode::context::Context<'static>, Lifted); 2] {
1531        let spec = sleigh_precompile::x64::spec();
1532        [
1533            SleighLifter::new(spec),
1534            SleighLifter::new(spec).with_flat_control_flow(),
1535        ]
1536        .map(|lifter| {
1537            let instruction = Decoder::new(spec)
1538                .decode_one(0x1000, bytes, &spec.new_context())
1539                .unwrap();
1540            let mut ctx = lifter.new_context();
1541            let lifted = lifter
1542                .lift_instruction(&mut ctx, &instruction, None)
1543                .unwrap();
1544            (ctx, lifted)
1545        })
1546    }
1547
1548    fn kinds(lifted: &Lifted) -> Vec<(ExitArm, ExitKind)> {
1549        lifted
1550            .exits()
1551            .iter()
1552            .map(|exit| (exit.arm(), exit.kind().clone()))
1553            .collect()
1554    }
1555
1556    /// The opcode of the instruction an exit is recorded at.
1557    fn site_opcode(ctx: &qcode::context::Context<'static>, exit: &Exit) -> &'static str {
1558        Instruction::from_id(ctx, exit.site()).mnemonic().opcode()
1559    }
1560
1561    fn tiny_spec(constructors: &str) -> CompiledSpec {
1562        let mut sources = SourceDb::new();
1563        let root = sources.add_file(
1564            "tiny.slaspec",
1565            format!(
1566                "define endian=little;
1567                 define space ram type=ram_space size=4 default;
1568                 define space register type=register_space size=4;
1569                 define register offset=0 size=4 [ r0 ];
1570                 define token instr(8) op=(0,7);
1571                 {constructors}"
1572            ),
1573        );
1574        Compiler::new(&mut sources).compile(root).unwrap()
1575    }
1576
1577    fn lift_tiny(
1578        spec: &CompiledSpec,
1579        byte: u8,
1580        flat: bool,
1581    ) -> (qcode::context::Context<'static>, Lifted) {
1582        let bytes = [byte];
1583        let instruction = Decoder::new(spec)
1584            .decode_one(0x1000, &bytes, &spec.new_context())
1585            .unwrap();
1586        let mut lifter = SleighLifter::new(spec);
1587        if flat {
1588            lifter = lifter.with_flat_control_flow();
1589        }
1590        let mut ctx = lifter.new_context();
1591        let lifted = lifter
1592            .lift_instruction(&mut ctx, &instruction, None)
1593            .unwrap();
1594        (ctx, lifted)
1595    }
1596
1597    #[test]
1598    fn a_jump_to_its_own_address_is_a_machine_transfer() {
1599        for (bytes, name) in [(b"\xeb\xfe".as_slice(), "jmp $"), (b"\xf4", "hlt")] {
1600            for (_, lifted) in lift_x64_both_modes(bytes) {
1601                assert_eq!(
1602                    kinds(&lifted),
1603                    [(ExitArm::Unconditional, ExitKind::Branch { target: 0x1000 })],
1604                    "{name}"
1605                );
1606                assert_eq!(lifted.blocks(), &[lifted.entry()], "{name}");
1607                assert!(!lifted.falls_through(), "{name}");
1608            }
1609        }
1610    }
1611
1612    #[test]
1613    fn a_conditional_jump_reports_its_taken_arm_and_the_fallthrough() {
1614        // `jz +5`, then the same with a branch-hint prefix, one byte longer.
1615        for (bytes, target, next) in [
1616            (b"\x74\x05".as_slice(), 0x1007, 0x1002),
1617            (b"\x2e\x74\x05", 0x1008, 0x1003),
1618        ] {
1619            for (ctx, lifted) in lift_x64_both_modes(bytes) {
1620                assert_eq!(lifted.next_address(), next);
1621                assert_eq!(
1622                    kinds(&lifted),
1623                    [
1624                        (ExitArm::Taken, ExitKind::Branch { target }),
1625                        (ExitArm::Unconditional, ExitKind::Fallthrough),
1626                    ],
1627                    "{bytes:02x?}"
1628                );
1629                assert_eq!(site_opcode(&ctx, &lifted.exits()[0]), "cbranch");
1630                assert_eq!(site_opcode(&ctx, &lifted.exits()[1]), "branch");
1631                // The entry and the not-taken block; the target and the next
1632                // instruction's placeholders are not the instruction's.
1633                assert_eq!(lifted.blocks().len(), 2, "{bytes:02x?}");
1634                assert!(lifted.falls_through());
1635            }
1636        }
1637    }
1638
1639    #[test]
1640    fn calls_and_returns_keep_their_kind_under_flat_control_flow() {
1641        let cases: [(&[u8], ExitKind); 4] = [
1642            (
1643                b"\xe8\x10\x00\x00\x00",
1644                ExitKind::Call {
1645                    callee: CallTarget::Address(0x1015),
1646                    continuation: Continuation::Next,
1647                },
1648            ),
1649            (
1650                b"\xff\xd0",
1651                ExitKind::CallInd {
1652                    continuation: Continuation::Next,
1653                },
1654            ),
1655            (b"\xc3", ExitKind::Return),
1656            (b"\xff\xe0", ExitKind::BranchInd),
1657        ];
1658        for (bytes, kind) in cases {
1659            let [(structured, lifted), (flat, flat_lifted)] = lift_x64_both_modes(bytes);
1660            assert_eq!(kinds(&lifted), [(ExitArm::Unconditional, kind.clone())]);
1661            assert_eq!(kinds(&flat_lifted), kinds(&lifted), "{bytes:02x?}");
1662            assert!(!lifted.falls_through());
1663
1664            let expected = match kind {
1665                ExitKind::Call { .. } => ("call", "branch"),
1666                ExitKind::CallInd { .. } => ("callind", "branchind"),
1667                ExitKind::Return => ("return", "branchind"),
1668                _ => ("branchind", "branchind"),
1669            };
1670            assert_eq!(site_opcode(&structured, &lifted.exits()[0]), expected.0);
1671            assert_eq!(site_opcode(&flat, &flat_lifted.exits()[0]), expected.1);
1672        }
1673    }
1674
1675    #[test]
1676    fn rep_movsb_leaves_by_its_count_check_and_returns_to_itself() {
1677        for (_, lifted) in lift_x64_both_modes(b"\xf3\xa4") {
1678            assert_eq!(
1679                kinds(&lifted),
1680                [
1681                    (ExitArm::Taken, ExitKind::Branch { target: 0x1002 }),
1682                    (ExitArm::Unconditional, ExitKind::Branch { target: 0x1000 }),
1683                ]
1684            );
1685            assert!(lifted.falls_through(), "an exhausted count continues");
1686        }
1687    }
1688
1689    #[test]
1690    fn a_call_followed_by_pcode_continues_in_the_instruction() {
1691        let spec = tiny_spec(":callx is op=3 { call 0x2000; r0 = 1:4; }");
1692        for flat in [false, true] {
1693            let (ctx, lifted) = lift_tiny(&spec, 3, flat);
1694            let [call, fallthrough] = lifted.exits() else {
1695                panic!("{:?}", lifted.exits());
1696            };
1697            let ExitKind::Call {
1698                callee: CallTarget::Address(0x2000),
1699                continuation: Continuation::Block(block),
1700            } = call.kind().clone()
1701            else {
1702                panic!("{call:?}");
1703            };
1704            assert_eq!(fallthrough.kind(), &ExitKind::Fallthrough);
1705            assert_eq!(lifted.blocks(), &[lifted.entry(), block]);
1706            // The continuation holds the rest of the p-code and leaves by the
1707            // fall-through.
1708            let continuation = BasicBlock::from_id(&ctx, block);
1709            assert_eq!(
1710                Instruction::from_id(&ctx, fallthrough.site())
1711                    .block()
1712                    .map(|b| b.id),
1713                Some(continuation.id)
1714            );
1715        }
1716    }
1717
1718    #[test]
1719    fn a_conditional_branch_to_the_terminal_label_is_a_taken_fallthrough() {
1720        let spec = tiny_spec(":cset is op=4 { if (r0 == 0:4) goto <skip>; r0 = 1:4; <skip> }");
1721        let (ctx, lifted) = lift_tiny(&spec, 4, false);
1722        assert_eq!(
1723            kinds(&lifted),
1724            [
1725                (ExitArm::Taken, ExitKind::Fallthrough),
1726                (ExitArm::Unconditional, ExitKind::Fallthrough),
1727            ]
1728        );
1729        assert_eq!(site_opcode(&ctx, &lifted.exits()[0]), "cbranch");
1730        assert_eq!(lifted.blocks().len(), 2);
1731    }
1732
1733    #[test]
1734    fn a_failed_instruction_leaves_the_context_as_it_was() {
1735        let spec = tiny_spec(
1736            ":bad is op=6 { r0 = 1:4; r0 = newobject(r0); }
1737             :good is op=7 { r0 = 2:4; }",
1738        );
1739        let instruction = Decoder::new(&spec)
1740            .decode_one(0x1000, &[6], &spec.new_context())
1741            .unwrap();
1742        assert!(
1743            instruction
1744                .pcode_ops()
1745                .unwrap()
1746                .ops
1747                .iter()
1748                .any(|op| op.opcode == sleigh::Opcode::New),
1749            "the fixture relies on NEW being unsupported"
1750        );
1751        let lifter = SleighLifter::new(&spec);
1752        let mut ctx = lifter.new_context();
1753        let function = ctx.anon_function();
1754        let mut addresses = AddressIndex::analyze(&ctx);
1755        let before = ctx.to_string();
1756
1757        let error = lifter
1758            .lift_instruction_indexed(&mut ctx, &mut addresses, &instruction, Some(function))
1759            .unwrap_err();
1760        assert_eq!(
1761            error,
1762            super::LiftError::UnsupportedOpcode(sleigh::Opcode::New)
1763        );
1764        assert_eq!(
1765            ctx.to_string(),
1766            before,
1767            "the partial instruction was undone"
1768        );
1769        assert!(addresses.is_empty(), "no placeholder survived");
1770
1771        // The address lifts afterwards, and so does another instruction.
1772        let good = Decoder::new(&spec)
1773            .decode_one(0x1000, &[7], &spec.new_context())
1774            .unwrap();
1775        let lifted = lifter
1776            .lift_instruction_indexed(&mut ctx, &mut addresses, &good, Some(function))
1777            .unwrap();
1778        assert!(lifted.falls_through());
1779        assert_eq!(addresses.block_at(0x1000), Some(lifted.entry()));
1780    }
1781
1782    #[test]
1783    fn an_address_is_lifted_once() {
1784        let spec = sleigh_precompile::x64::spec();
1785        let lifter = SleighLifter::new(spec);
1786        let instruction = Decoder::new(spec)
1787            .decode_one(0x1000, b"\x48\x89\xd8", &spec.new_context())
1788            .unwrap();
1789        let mut ctx = lifter.new_context();
1790        let function = ctx.anon_function();
1791        let mut addresses = AddressIndex::analyze(&ctx);
1792        let lifted = lifter
1793            .lift_instruction_indexed(&mut ctx, &mut addresses, &instruction, Some(function))
1794            .unwrap();
1795        let again = lifter
1796            .lift_instruction_indexed(&mut ctx, &mut addresses, &instruction, Some(function))
1797            .unwrap_err();
1798        assert_eq!(
1799            again,
1800            super::LiftError::Target(qcode::lift::TargetError::AlreadyLifted {
1801                address: 0x1000,
1802                block: lifted.entry()
1803            })
1804        );
1805        // The fall-through placeholder is empty and takes its instruction.
1806        let next = Decoder::new(spec)
1807            .decode_one(0x1003, b"\x48\x89\xd8", &spec.new_context())
1808            .unwrap();
1809        lifter
1810            .lift_instruction_indexed(&mut ctx, &mut addresses, &next, Some(function))
1811            .unwrap();
1812    }
1813
1814    /// Lifts `bytes` at 0x1000 into a function there, in a context that also
1815    /// has a function at 0x2000 and one at the instruction's next address:
1816    /// the structured lowering of a transfer into another function.
1817    fn lift_beside_functions(
1818        bytes: &[u8],
1819        flat: bool,
1820    ) -> (
1821        qcode::context::Context<'static>,
1822        Lifted,
1823        [qcode::value::FunctionId; 3],
1824    ) {
1825        use qcode::value::FunctionBody;
1826        let spec = sleigh_precompile::x64::spec();
1827        let mut lifter = SleighLifter::new(spec);
1828        if flat {
1829            lifter = lifter.with_flat_control_flow();
1830        }
1831        let instruction = Decoder::new(spec)
1832            .decode_one(0x1000, bytes, &spec.new_context())
1833            .unwrap();
1834        let mut ctx = lifter.new_context();
1835        let mut addresses = AddressIndex::analyze(&ctx);
1836        let host = FunctionBody::make_at_addr_indexed(&mut ctx, &mut addresses, 0x1000, None).id;
1837        let other = FunctionBody::make_at_addr_indexed(&mut ctx, &mut addresses, 0x2000, None).id;
1838        let next = 0x1000 + instruction.len() as u64;
1839        let after = FunctionBody::make_at_addr_indexed(&mut ctx, &mut addresses, next, None).id;
1840        let lifted = lifter
1841            .lift_instruction_indexed(&mut ctx, &mut addresses, &instruction, Some(host))
1842            .unwrap();
1843        (ctx, lifted, [host, other, after])
1844    }
1845
1846    /// The tail call a block of `lifted` makes, if one does.
1847    fn tail_callee(
1848        ctx: &qcode::context::Context<'static>,
1849        block: qcode::value::BlockId,
1850    ) -> Option<qcode::value::FunctionId> {
1851        use qcode::value::insn::Mnemonic;
1852        let last = BasicBlock::from_id(ctx, block).iter().last()?;
1853        match last.mnemonic() {
1854            Mnemonic::TailCall(call) => call.target.real(),
1855            _ => None,
1856        }
1857    }
1858
1859    #[test]
1860    fn a_jump_into_another_function_is_a_tail_call() {
1861        // jmp 0x2000 (e9 rel32 from 0x1005)
1862        for flat in [false, true] {
1863            let (ctx, lifted, [_, other, _]) = lift_beside_functions(b"\xe9\xfb\x0f\x00\x00", flat);
1864            assert_eq!(
1865                kinds(&lifted),
1866                vec![(ExitArm::Unconditional, ExitKind::Branch { target: 0x2000 })]
1867            );
1868            // The entry branches to a block of the instruction that tail-calls
1869            // the other function; the fall-through, never taken, made nothing.
1870            assert_eq!(lifted.blocks().len(), 2, "{}", ctx);
1871            assert_eq!(tail_callee(&ctx, lifted.blocks()[1]), Some(other));
1872            let exit = &lifted.exits()[0];
1873            assert_eq!(site_opcode(&ctx, exit), "branch");
1874        }
1875    }
1876
1877    #[test]
1878    fn a_conditional_jump_into_another_function_tail_calls_on_its_taken_arm() {
1879        // je 0x2000 (0f 84 rel32 from 0x1006); the next address is a function too.
1880        let (ctx, lifted, [_, other, after]) =
1881            lift_beside_functions(b"\x0f\x84\xfa\x0f\x00\x00", false);
1882        let callees: Vec<_> = lifted.blocks()[1..]
1883            .iter()
1884            .map(|&b| tail_callee(&ctx, b))
1885            .collect();
1886        assert!(callees.contains(&Some(other)), "{ctx}");
1887        assert!(callees.contains(&Some(after)), "{ctx}");
1888        assert_eq!(
1889            kinds(&lifted),
1890            vec![
1891                (ExitArm::Taken, ExitKind::Branch { target: 0x2000 }),
1892                (ExitArm::Unconditional, ExitKind::Fallthrough)
1893            ]
1894        );
1895    }
1896
1897    #[test]
1898    fn a_fall_through_into_another_function_is_a_tail_call_and_a_ret_makes_none() {
1899        // mov rax, rbx: falls into the function after it.
1900        let (ctx, lifted, [_, _, after]) = lift_beside_functions(b"\x48\x89\xd8", false);
1901        assert_eq!(lifted.blocks().len(), 2);
1902        assert_eq!(tail_callee(&ctx, lifted.blocks()[1]), Some(after));
1903        // ret: never falls through, so no tail-call block is made.
1904        let (ctx, lifted, _) = lift_beside_functions(b"\xc3", false);
1905        assert_eq!(lifted.blocks().len(), 1, "{ctx}");
1906        // A structured call to the other function is a call, whose continuation
1907        // (the next function) is left to the caller: no block for it either.
1908        let (ctx, lifted, [_, other, _]) = lift_beside_functions(b"\xe8\xfb\x0f\x00\x00", false);
1909        assert_eq!(lifted.blocks().len(), 1, "{ctx}");
1910        let last = BasicBlock::from_id(&ctx, lifted.entry())
1911            .iter()
1912            .last()
1913            .unwrap();
1914        assert!(
1915            matches!(last.mnemonic(), qcode::value::insn::Mnemonic::Call(c) if c.target.real() == Some(other))
1916        );
1917    }
1918
1919    #[test]
1920    fn a_context_of_another_specification_is_refused() {
1921        let tiny = tiny_spec(":set is op=1 { r0 = 1:4; }");
1922        let x64 = sleigh_precompile::x64::spec();
1923        let instruction = Decoder::new(x64)
1924            .decode_one(0x1000, b"\x48\x89\xd8", &x64.new_context())
1925            .unwrap();
1926        let mut ctx = SleighLifter::new(&tiny).new_context();
1927        assert_eq!(
1928            SleighLifter::new(x64)
1929                .lift_instruction(&mut ctx, &instruction, None)
1930                .unwrap_err(),
1931            super::LiftError::IncompatibleContext
1932        );
1933        assert_eq!(ctx.functions().count(), 0, "nothing was created first");
1934    }
1935
1936    #[test]
1937    fn an_instruction_of_another_specification_is_refused() {
1938        // A compatible destination, but the instruction was decoded by x86, so
1939        // its varnodes do not name this x64 lifter's registers.
1940        let x64 = sleigh_precompile::x64::spec();
1941        let x86 = sleigh_precompile::x86::spec();
1942        let instruction = Decoder::new(x86)
1943            .decode_one(0x1000, b"\x89\xd8", &x86.new_context())
1944            .unwrap();
1945        let lifter = SleighLifter::new(x64);
1946        let mut ctx = lifter.new_context();
1947        assert_eq!(
1948            lifter
1949                .lift_instruction(&mut ctx, &instruction, None)
1950                .unwrap_err(),
1951            super::LiftError::IncompatibleSpec
1952        );
1953        assert_eq!(ctx.functions().count(), 0, "nothing was created first");
1954    }
1955
1956    #[test]
1957    fn a_look_alike_specification_is_refused_before_anything_is_mutated() {
1958        // Two specifications with the same spaces and the same register at the
1959        // same place, one constructor's semantics apart. Structurally they are
1960        // indistinguishable; by identity they are not the same specification,
1961        // and neither's lifter accepts the other's context, instruction or
1962        // flat p-code.
1963        let first = tiny_spec(":set is op=1 { r0 = 1:4; }");
1964        let alike = tiny_spec(":set is op=1 { r0 = 2:4; }");
1965        assert_ne!(first.fingerprint(), alike.fingerprint());
1966        let lifter = SleighLifter::new(&first);
1967        let other = SleighLifter::new(&alike);
1968
1969        let mut ctx = other.new_context();
1970        let before = (ctx.to_string(), ctx.revision());
1971        let instruction = Decoder::new(&first)
1972            .decode_one(0x1000, &[1], &first.new_context())
1973            .unwrap();
1974        assert_eq!(
1975            lifter.lift_instruction(&mut ctx, &instruction, None).err(),
1976            Some(super::LiftError::IncompatibleContext)
1977        );
1978        assert_eq!(
1979            (ctx.to_string(), ctx.revision()),
1980            before,
1981            "refused untouched"
1982        );
1983
1984        let mut ctx = lifter.new_context();
1985        let before = (ctx.to_string(), ctx.revision());
1986        let foreign = Decoder::new(&alike)
1987            .decode_one(0x1000, &[1], &alike.new_context())
1988            .unwrap();
1989        assert_eq!(
1990            lifter.lift_instruction(&mut ctx, &foreign, None).err(),
1991            Some(super::LiftError::IncompatibleSpec)
1992        );
1993        let flat = FlatPcode::lower(&foreign).unwrap();
1994        let mut addresses = AddressIndex::analyze(&ctx);
1995        assert_eq!(
1996            lifter
1997                .lift_pcode_indexed(&mut ctx, &mut addresses, &flat, None)
1998                .err(),
1999            Some(super::LiftError::IncompatibleSpec)
2000        );
2001        assert_eq!(
2002            (ctx.to_string(), ctx.revision()),
2003            before,
2004            "refused untouched"
2005        );
2006        // And through a bound target.
2007        let function = ctx.anon_function();
2008        let before = ctx.to_string();
2009        let mut addresses = AddressIndex::analyze(&ctx);
2010        let mut target =
2011            qcode::lift::LiftTarget::bind_indexed(&mut ctx, &mut addresses, function).unwrap();
2012        assert_eq!(
2013            lifter.lift_pcode_into(&mut target, &flat).err(),
2014            Some(super::LiftError::IncompatibleSpec)
2015        );
2016        let _ = target;
2017        assert_eq!(ctx.to_string(), before, "refused untouched");
2018    }
2019
2020    #[test]
2021    fn cached_pcode_is_trusted_on_the_fingerprint_it_claims() {
2022        // The provenance of cached p-code is the caller's claim: the one
2023        // honest way to lift cached p-code is to store the fingerprint with
2024        // it, and p-code of a look-alike specification passes under a
2025        // forged one.
2026        let first = tiny_spec(":set is op=1 { r0 = 1:4; }");
2027        let alike = tiny_spec(":set is op=1 { r0 = 2:4; }");
2028        let lifter = SleighLifter::new(&first);
2029        let foreign = Decoder::new(&alike)
2030            .decode_one(0x1000, &[1], &alike.new_context())
2031            .unwrap();
2032        let flat = FlatPcode::lower(&foreign).unwrap();
2033        let claimed = FlatPcode::from_parts(
2034            first.fingerprint(),
2035            flat.address(),
2036            flat.length(),
2037            flat.pcode().clone(),
2038        );
2039        let mut ctx = lifter.new_context();
2040        let mut addresses = AddressIndex::analyze(&ctx);
2041        assert_eq!(
2042            lifter
2043                .lift_pcode_indexed(&mut ctx, &mut addresses, &flat, None)
2044                .err(),
2045            Some(super::LiftError::IncompatibleSpec)
2046        );
2047        lifter
2048            .lift_pcode_indexed(&mut ctx, &mut addresses, &claimed, None)
2049            .unwrap();
2050    }
2051
2052    #[test]
2053    fn the_stamp_is_the_specifications_identity_and_survives_a_clone_and_a_reload() {
2054        let first = tiny_spec(":set is op=1 { r0 = 1:4; }");
2055        let lifter = SleighLifter::new(&first);
2056        let instruction = Decoder::new(&first)
2057            .decode_one(0x1000, &[1], &first.new_context())
2058            .unwrap();
2059
2060        // A hand-built module has no stamp, and no lifter accepts it.
2061        let mut bare = qcode::context::Context::new();
2062        assert_eq!(
2063            lifter.lift_instruction(&mut bare, &instruction, None).err(),
2064            Some(super::LiftError::IncompatibleContext)
2065        );
2066
2067        // Identity, not instance: another lifter for the same specification
2068        // builds an acceptable context.
2069        let twin = SleighLifter::new(&first);
2070        let mut ctx = twin.new_context();
2071        lifter
2072            .lift_instruction(&mut ctx, &instruction, None)
2073            .unwrap();
2074        let mut cloned = ctx.clone();
2075        let next = Decoder::new(&first)
2076            .decode_one(0x1001, &[1], &first.new_context())
2077            .unwrap();
2078        lifter.lift_instruction(&mut cloned, &next, None).unwrap();
2079        let bytes = bincode::serde::encode_to_vec(&ctx, bincode::config::standard()).unwrap();
2080        let (mut reloaded, _): (qcode::context::Context<'static>, _) =
2081            bincode::serde::decode_from_slice(&bytes, bincode::config::standard()).unwrap();
2082        assert_eq!(reloaded.architecture(), ctx.architecture());
2083        lifter.lift_instruction(&mut reloaded, &next, None).unwrap();
2084    }
2085
2086    #[test]
2087    fn a_function_of_another_context_is_refused() {
2088        let spec = sleigh_precompile::x64::spec();
2089        let lifter = SleighLifter::new(spec);
2090        let instruction = Decoder::new(spec)
2091            .decode_one(0x1000, b"\x48\x89\xd8", &spec.new_context())
2092            .unwrap();
2093        let mut other = lifter.new_context();
2094        other.anon_function();
2095        let foreign = other.anon_function();
2096        let mut ctx = lifter.new_context();
2097        assert_eq!(
2098            lifter
2099                .lift_instruction(&mut ctx, &instruction, Some(foreign))
2100                .unwrap_err(),
2101            super::LiftError::Target(qcode::lift::TargetError::UnknownFunction(foreign))
2102        );
2103    }
2104
2105    #[test]
2106    fn an_internal_loop_has_no_exits() {
2107        let spec = tiny_spec(":spin is op=5 { <again> r0 = r0 + 1:4; goto <again>; }");
2108        let (_, lifted) = lift_tiny(&spec, 5, false);
2109        assert!(lifted.exits().is_empty(), "{:?}", lifted.exits());
2110        assert!(!lifted.falls_through());
2111        assert_eq!(lifted.blocks().len(), 2, "the entry and the loop block");
2112    }
2113
2114    /// The streamed path and the already-flattened path must lower the same
2115    /// instruction to the same QCode.
2116    #[test]
2117    fn streamed_and_flat_pcode_lift_identically() {
2118        let spec = sleigh_precompile::x64::spec();
2119        let lifter = SleighLifter::new(spec);
2120        for bytes in [
2121            b"\x48\x89\xd8".as_slice(),
2122            b"\x48\x01\xd8",
2123            b"\x74\x05",
2124            b"\xe8\x10\x00\x00\x00",
2125            b"\xff\xe0",
2126            b"\xc3",
2127            b"\x0f\xb0\x1d\x00\xf1\x9a\xff",
2128            b"\xf7\xf1",
2129            b"\x48\x0f\xaf\xc3",
2130        ] {
2131            let instruction = Decoder::new(spec)
2132                .decode_one(0x1000, bytes, &spec.new_context())
2133                .unwrap();
2134
2135            let mut streamed = lifter.new_context();
2136            let streamed_lifted = lifter
2137                .lift_instruction(&mut streamed, &instruction, None)
2138                .unwrap();
2139
2140            let pcode = FlatPcode::lower(&instruction).unwrap();
2141            let mut flat = lifter.new_context();
2142            let mut addresses = AddressIndex::analyze(&flat);
2143            let flat_lifted = lifter
2144                .lift_pcode_indexed(&mut flat, &mut addresses, &pcode, None)
2145                .unwrap();
2146
2147            assert_eq!(
2148                streamed.to_string(),
2149                flat.to_string(),
2150                "{bytes:02x?} lifts differently"
2151            );
2152            assert_eq!(
2153                streamed_lifted, flat_lifted,
2154                "{bytes:02x?} reports different results"
2155            );
2156        }
2157    }
2158
2159    #[test]
2160    fn lifts_flat_register_copy_from_a_decoded_instruction() {
2161        let mut sources = SourceDb::new();
2162        let root = sources.add_file(
2163            "tiny.slaspec",
2164            "define endian=little;
2165             define space ram type=ram_space size=4 default;
2166             define space register type=register_space size=4;
2167             define register offset=0 size=4 [ r0 ];
2168             define token instr(8) op=(0,7);
2169             :set is op=1 { r0 = 0x12345678:4; }
2170             :add is op=2 { r0 = r0 + 1:4; }",
2171        );
2172        let spec = Compiler::new(&mut sources).compile(root).unwrap();
2173        let instruction = Decoder::new(&spec)
2174            .decode_one(0x1000, &[1], &spec.new_context())
2175            .unwrap();
2176        assert_eq!(instruction.pcode_ops().unwrap().ops.len(), 1);
2177
2178        let lifter = SleighLifter::new(&spec);
2179        let mut ctx = lifter.new_context();
2180        lifter
2181            .lift_instruction(&mut ctx, &instruction, None)
2182            .unwrap();
2183        // COPY to r0 plus the explicit machine-instruction fall-through.
2184        assert_eq!(ctx.instructions().count(), 2);
2185    }
2186
2187    #[test]
2188    fn decodes_and_lifts_bytes_without_a_product_disassembler() {
2189        let spec = sleigh_precompile::x64::spec();
2190        let lifter = SleighLifter::new(spec);
2191        let mut ctx = lifter.new_context();
2192
2193        lifter
2194            .decode_and_lift(&mut ctx, 0x1000, b"\x48\x89\xd8", None)
2195            .unwrap();
2196
2197        assert!(ctx.instructions().count() > 1);
2198    }
2199
2200    #[test]
2201    fn lifts_terminal_local_branch_to_instruction_fallthrough() {
2202        let spec = sleigh_precompile::x64::spec();
2203        let instruction = Decoder::new(spec)
2204            .decode_one(0x1000, b"\x0f\xb0\x1d\x00\xf1\x9a\xff", &spec.new_context())
2205            .unwrap();
2206        let lifter = SleighLifter::new(spec);
2207        let mut ctx = lifter.new_context();
2208        lifter
2209            .lift_instruction(&mut ctx, &instruction, None)
2210            .unwrap();
2211    }
2212
2213    #[test]
2214    fn lifts_x64_non_rep_string_forms_from_the_binit_corpus() {
2215        let spec = sleigh_precompile::x64::spec();
2216        let lifter = SleighLifter::new(spec);
2217        for bytes in [
2218            b"\xa4".as_slice(),
2219            b"\x66\xa5",
2220            b"\xa5",
2221            b"\x48\xa5",
2222            b"\xa6",
2223            b"\x66\xa7",
2224            b"\xa7",
2225            b"\x48\xa7",
2226            b"\xac",
2227            b"\x66\xad",
2228            b"\xad",
2229            b"\x48\xad",
2230            b"\xae",
2231            b"\x66\xaf",
2232            b"\xaf",
2233            b"\x48\xaf",
2234            b"\xaa",
2235            b"\x66\xab",
2236            b"\xab",
2237            b"\x48\xab",
2238        ] {
2239            let instruction = Decoder::new(spec)
2240                .decode_one(0x1000, bytes, &spec.new_context())
2241                .unwrap();
2242            let mut ctx = lifter.new_context();
2243            lifter
2244                .lift_instruction(&mut ctx, &instruction, None)
2245                .unwrap();
2246        }
2247    }
2248
2249    #[test]
2250    fn lifts_x64_unsized_unary_and_carry_literals() {
2251        let spec = sleigh_precompile::x64::spec();
2252        let lifter = SleighLifter::new(spec);
2253        for bytes in [
2254            b"\x48\x0f\xb3\xd8".as_slice(), // BTR RAX,RBX
2255            b"\x0f\x06",                    // CLTS
2256            b"\x48\xf7\xd8",                // NEG RAX
2257        ] {
2258            let instruction = Decoder::new(spec)
2259                .decode_one(0x1000, bytes, &spec.new_context())
2260                .unwrap();
2261            let mut ctx = lifter.new_context();
2262            lifter
2263                .lift_instruction(&mut ctx, &instruction, None)
2264                .unwrap();
2265        }
2266    }
2267
2268    #[test]
2269    fn emulates_loop_carried_unique_pcode_temporaries() {
2270        let spec = sleigh_precompile::x64::spec();
2271        let lifter = SleighLifter::new(spec);
2272        for (bytes, inputs, output_name, expected) in [
2273            (
2274                b"\x66\xf3\x0f\xbc\xc3".as_slice(),
2275                &[("BX", 0)][..],
2276                "AX",
2277                16,
2278            ),
2279            (b"\x48\x0f\xbd\xc3", &[("RBX", 1)], "RAX", 0),
2280            (
2281                b"\xc4\xe2\x63\xf5\xc1",
2282                &[("EBX", 1), ("ECX", 0x8000_0000)],
2283                "EAX",
2284                0x8000_0000,
2285            ),
2286            (
2287                b"\xc4\xe2\x62\xf5\xc1",
2288                &[("EBX", 0x8000_0000), ("ECX", 0x8000_0000)],
2289                "EAX",
2290                1,
2291            ),
2292        ] {
2293            let instruction = Decoder::new(spec)
2294                .decode_one(0x1000, bytes, &spec.new_context())
2295                .unwrap();
2296            let output_id = spec
2297                .registers()
2298                .find(|register| register.name() == output_name)
2299                .unwrap()
2300                .id;
2301            let mut ctx = lifter.new_context();
2302            lifter
2303                .lift_instruction(&mut ctx, &instruction, None)
2304                .unwrap();
2305
2306            let mut emulator = Emulator::from_address(&ctx, 0x1000);
2307            for &(name, value) in inputs {
2308                let id = spec
2309                    .registers()
2310                    .find(|register| register.name() == name)
2311                    .unwrap()
2312                    .id;
2313                emulator.set_register(id, value).unwrap();
2314            }
2315            for _ in 0..1000 {
2316                if emulator.block().address() == Some(0x1000 + bytes.len() as u64) {
2317                    break;
2318                }
2319                emulator.step().unwrap();
2320            }
2321            assert_eq!(
2322                emulator.block().address(),
2323                Some(0x1000 + bytes.len() as u64),
2324                "{instruction} did not reach its fall-through block"
2325            );
2326            assert_eq!(
2327                emulator.read_register(output_id),
2328                Some(expected),
2329                "{instruction}"
2330            );
2331        }
2332    }
2333
2334    /// A specification whose `r0` and `r1` are 4-byte registers, with one
2335    /// instruction per test of the unique-space lowering.
2336    fn unique_spec() -> CompiledSpec {
2337        let mut sources = SourceDb::new();
2338        let root = sources.add_file(
2339            "uniques.slaspec",
2340            "define endian=little;
2341             define space ram type=ram_space size=4 default;
2342             define space register type=register_space size=4;
2343             define register offset=0 size=4 [ r0 r1 ];
2344             define token instr(8) op=(0,7);
2345             :chain is op=2 { local t:4 = r0 + 1:4; r0 = t * 2:4; }
2346             :cross is op=3 {
2347                 local t:4 = r0 + 1:4;
2348                 if (r0 == 0:4) goto <done>;
2349                 r0 = t;
2350                 <done>
2351                 r1 = t;
2352             }",
2353        );
2354        Compiler::new(&mut sources).compile(root).unwrap()
2355    }
2356
2357    fn register(spec: &CompiledSpec, name: &str) -> sleigh::RegisterId {
2358        spec.registers()
2359            .find(|register| register.name() == name)
2360            .unwrap()
2361            .id
2362    }
2363
2364    #[test]
2365    fn uniques_read_in_their_own_block_are_values_not_memory() {
2366        let spec = unique_spec();
2367        let instruction = Decoder::new(&spec)
2368            .decode_one(0x1000, &[2], &spec.new_context())
2369            .unwrap();
2370        let lifter = SleighLifter::new(&spec);
2371        let mut ctx = lifter.new_context();
2372        lifter
2373            .lift_instruction(&mut ctx, &instruction, None)
2374            .unwrap();
2375        // Register load, add, multiply, register copy, and machine
2376        // fall-through: the unique `t` is the add's result, never stored.
2377        assert_eq!(ctx.instructions().count(), 5, "{ctx}");
2378
2379        let mut emulator = Emulator::from_address(&ctx, 0x1000);
2380        emulator.set_register(register(&spec, "r0"), 5).unwrap();
2381        while emulator.block().address() != Some(0x1001) {
2382            emulator.step().unwrap();
2383        }
2384        assert_eq!(emulator.read_register(register(&spec, "r0")), Some(12));
2385    }
2386
2387    #[test]
2388    fn uniques_read_across_a_block_boundary_go_through_memory() {
2389        let spec = unique_spec();
2390        let instruction = Decoder::new(&spec)
2391            .decode_one(0x1000, &[3], &spec.new_context())
2392            .unwrap();
2393        let lifter = SleighLifter::new(&spec);
2394        let mut ctx = lifter.new_context();
2395        lifter
2396            .lift_instruction(&mut ctx, &instruction, None)
2397            .unwrap();
2398        // The entry block: two register loads, the add, the compare, a store
2399        // of `t` and of the condition to their temporaries, and the branch.
2400        // Then the not-taken block and the label's block each load `t`, store
2401        // it to a register, and jump.
2402        assert_eq!(ctx.instructions().count(), 13, "{ctx}");
2403
2404        for (r0, expected_r0, expected_r1) in [(5, 6, 6), (0, 0, 1)] {
2405            let mut emulator = Emulator::from_address(&ctx, 0x1000);
2406            emulator.set_register(register(&spec, "r0"), r0).unwrap();
2407            while emulator.block().address() != Some(0x1001) {
2408                emulator.step().unwrap();
2409            }
2410            assert_eq!(
2411                emulator.read_register(register(&spec, "r0")),
2412                Some(expected_r0)
2413            );
2414            assert_eq!(
2415                emulator.read_register(register(&spec, "r1")),
2416                Some(expected_r1)
2417            );
2418        }
2419    }
2420
2421    #[test]
2422    fn lifts_flat_arithmetic_without_rewalking_the_sleigh_ast() {
2423        let mut sources = SourceDb::new();
2424        let root = sources.add_file(
2425            "tiny.slaspec",
2426            "define endian=little;
2427             define space ram type=ram_space size=4 default;
2428             define space register type=register_space size=4;
2429             define register offset=0 size=4 [ r0 ];
2430             define token instr(8) op=(0,7);
2431             :add is op=2 { r0 = r0 + 1:4; }",
2432        );
2433        let spec = Compiler::new(&mut sources).compile(root).unwrap();
2434        let instruction = Decoder::new(&spec)
2435            .decode_one(0x1000, &[2], &spec.new_context())
2436            .unwrap();
2437        assert_eq!(
2438            instruction.pcode_ops().unwrap().ops[0].opcode,
2439            sleigh::Opcode::IntAdd
2440        );
2441
2442        let lifter = SleighLifter::new(&spec);
2443        let mut ctx = lifter.new_context();
2444        lifter
2445            .lift_instruction(&mut ctx, &instruction, None)
2446            .unwrap();
2447        // Register load, add, register copy, and machine fall-through.
2448        assert_eq!(ctx.instructions().count(), 4);
2449    }
2450}