Skip to content

Ghidrust provides a hyper fast, AI native reverse engineering platform built in Rust, inspired by Ghidra. Includes experimental GPU kernels to rapidly decompile large files, a decryption suite, and network monitor for packet to binary reverse engineering.

20.8 KB
Raw Blame
//! **Ghidrust SSA layer**: CFG construction, dominators, and full Cytron-
//! style SSA rename over [`ghidrust_ir::IrSequence`].
//!
//! `/Features/Decompiler` is the *reference* — implementation is
//! hand-rolled (no third-party SSA crates at runtime)
//! policy.
//!
//! # Overview
//!
//! * [`build_cfg`] partitions a lifted [`IrSequence`] into basic blocks using
//!   leader analysis (Aho–Sethi–Ullman style) and resolves intra-region
//!   successors from `Branch` / `CBranch` / `Return` ops.
//! * [`Cfg::dominators`] returns the immediate dominator array (Cooper–Harvey–
//!   Kennedy iterative algorithm).
//! * [`Cfg::dominance_frontiers`] gives per-block dominance frontiers.
//! * [`phi_placement`] returns the set of blocks needing a phi for each
//!   varnode (Cytron 1991).
//! * [`ssa::build_ssa`] produces a fully renamed [`ssa::SsaFunction`] with
//!   phi nodes and versioned operands ready for structuring / type recovery
//!   / Stage-1 C emit.
//! * [`ssa::copy_propagate`] is a small first-cut dataflow pass that walks
//!   `Copy` chains — the seed of Stage-1 expression recovery.

pub mod ssa;

pub use ssa::{
    build_ssa, const_fold, copy_propagate, dead_code_eliminate, dump_ssa, load_store_propagate,
    PhiNode, SsaBlock, SsaFunction, SsaOp, SsaOperand, SsaValue,
};

use ghidrust_ir::{BasicBlock, IrSequence, OpCode, PcodeOp, Varnode};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};

pub const ENTRY_BLOCK: u32 = 0;

/// Control-flow graph built over a sequence of address-tagged IR ops.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Cfg {
    pub blocks: Vec<BasicBlock>,
    /// Map from source-address (instruction start) to owning block id.
    pub block_of_addr: BTreeMap<u64, u32>,
    /// Blocks whose terminator is a direct branch to a target outside the
    /// analyzed region (e.g. inter-procedural jmp, unresolved indirect).
    pub external_exits: Vec<u32>,
}

impl Cfg {
    pub fn len(&self) -> usize {
        self.blocks.len()
    }

    pub fn is_empty(&self) -> bool {
        self.blocks.is_empty()
    }

    /// Return predecessors of block `id` (linear scan is fine at this scale).
    pub fn predecessors(&self, id: u32) -> Vec<u32> {
        self.blocks
            .iter()
            .filter(|b| b.successors.contains(&id))
            .map(|b| b.id)
            .collect()
    }

    /// Cooper–Harvey–Kennedy iterative immediate-dominators.
    ///
    /// `idom[ENTRY_BLOCK]` is self-referential (entry dominates itself).
    /// Blocks unreachable from entry receive [`u32::MAX`] and should be
    /// treated as "no dominator".
    pub fn dominators(&self) -> Vec<u32> {
        let n = self.blocks.len();
        if n == 0 {
            return Vec::new();
        }
        // Reverse post-order: entry gets rpo=0, leaves get larger numbers.
        let rpo = self.reverse_postorder();
        let mut rpo_of = vec![u32::MAX; n];
        for (i, &b) in rpo.iter().enumerate() {
            rpo_of[b as usize] = i as u32;
        }
        let mut idom = vec![u32::MAX; n];
        idom[ENTRY_BLOCK as usize] = ENTRY_BLOCK;

        let mut changed = true;
        while changed {
            changed = false;
            for &b in rpo.iter().skip(1) {
                let preds: Vec<u32> = self
                    .predecessors(b)
                    .into_iter()
                    .filter(|p| idom[*p as usize] != u32::MAX)
                    .collect();
                let Some(mut new_idom) = preds.first().copied() else {
                    continue;
                };
                for &p in preds.iter().skip(1) {
                    new_idom = intersect(&idom, &rpo_of, new_idom, p);
                }
                if idom[b as usize] != new_idom {
                    idom[b as usize] = new_idom;
                    changed = true;
                }
            }
        }
        idom
    }

    /// Cytron dominance frontiers, one set per block.
    pub fn dominance_frontiers(&self) -> Vec<BTreeSet<u32>> {
        let idom = self.dominators();
        let n = self.blocks.len();
        let mut df = vec![BTreeSet::new(); n];
        for b in 0..n as u32 {
            let preds = self.predecessors(b);
            if preds.len() >= 2 {
                for p in preds {
                    let mut runner = p;
                    while runner != idom[b as usize] && runner != u32::MAX {
                        df[runner as usize].insert(b);
                        let next = idom[runner as usize];
                        if next == runner {
                            break;
                        }
                        runner = next;
                    }
                }
            }
        }
        df
    }

    fn reverse_postorder(&self) -> Vec<u32> {
        let n = self.blocks.len();
        if n == 0 {
            return Vec::new();
        }
        let mut order = Vec::with_capacity(n);
        let mut visited = vec![false; n];
        let mut stack = vec![(ENTRY_BLOCK, false)];
        while let Some((b, processed)) = stack.pop() {
            if processed {
                order.push(b);
                continue;
            }
            if visited[b as usize] {
                continue;
            }
            visited[b as usize] = true;
            stack.push((b, true));
            for &s in &self.blocks[b as usize].successors {
                if !visited[s as usize] {
                    stack.push((s, false));
                }
            }
        }
        order.reverse();
        order
    }
}

fn intersect(idom: &[u32], rpo_of: &[u32], mut b1: u32, mut b2: u32) -> u32 {
    // Cooper–Harvey–Kennedy `intersect`, expressed over reverse post-order
    // indices (entry = 0, leaves = large). To climb toward entry we follow
    // `idom` until both fingers meet.
    while b1 != b2 {
        while rpo_of[b1 as usize] > rpo_of[b2 as usize] {
            let next = idom[b1 as usize];
            if next == b1 || next == u32::MAX {
                break;
            }
            b1 = next;
        }
        while rpo_of[b2 as usize] > rpo_of[b1 as usize] {
            let next = idom[b2 as usize];
            if next == b2 || next == u32::MAX {
                break;
            }
            b2 = next;
        }
        if rpo_of[b1 as usize] == rpo_of[b2 as usize] && b1 != b2 {
            // Distinct unreachable siblings — fall back to entry to keep the
            // walk finite.
            return ENTRY_BLOCK;
        }
    }
    b1
}

fn is_terminator(op: &PcodeOp) -> bool {
    matches!(
        op.opcode,
        OpCode::Branch
            | OpCode::CBranch
            | OpCode::BranchInd
            | OpCode::Return
            | OpCode::Call
            | OpCode::CallInd
    )
}

fn branch_target(op: &PcodeOp) -> Option<u64> {
    match op.opcode {
        OpCode::Branch => op.inputs.first().and_then(constant_value),
        OpCode::CBranch => op.inputs.get(1).and_then(constant_value),
        _ => None,
    }
}

fn constant_value(v: &Varnode) -> Option<u64> {
    match v.space {
        ghidrust_ir::AddrSpace::Constant => Some(v.offset),
        _ => None,
    }
}

/// Build a CFG from a lifted [`IrSequence`]. The sequence must include the
/// per-op source addresses via [`IrSequence::push_addressed`] (which
/// [`ghidrust_lift::lift_instructions`] does automatically).
///
/// `region_start` and `region_end_exclusive` bound the addresses considered
/// "internal" (used to decide whether a branch target is an intra-function
/// edge or an external exit).
pub fn build_cfg(seq: &IrSequence, region_start: u64, region_end_exclusive: u64) -> Cfg {
    build_cfg_with_leaders(seq, region_start, region_end_exclusive, &[])
}

/// Hint-aware CFG build. `extra_leaders` seeds additional block-leader
/// addresses (typically switch-case target VAs recovered from the shipped
/// `Decompiler Switch Analysis` analyzer). Also seeds each extra leader as
/// a successor of any block ending in [`OpCode::BranchInd`] so downstream
/// structuring can lift the indirect jump into a real `switch` region
/// instead of an unresolved `goto`.
pub fn build_cfg_with_leaders(
    seq: &IrSequence,
    region_start: u64,
    region_end_exclusive: u64,
    extra_leaders: &[u64],
) -> Cfg {
    if seq.addressed.is_empty() {
        return Cfg {
            blocks: Vec::new(),
            block_of_addr: BTreeMap::new(),
            external_exits: Vec::new(),
        };
    }

    // 1. Determine leader addresses.
    let mut leaders = BTreeSet::new();
    leaders.insert(seq.addressed[0].address);
    for &l in extra_leaders {
        if l >= region_start && l < region_end_exclusive {
            leaders.insert(l);
        }
    }
    let mut op_index_by_addr: BTreeMap<u64, usize> = BTreeMap::new();
    for (i, aop) in seq.addressed.iter().enumerate() {
        op_index_by_addr.entry(aop.address).or_insert(i);
    }
    let instruction_starts: BTreeSet<u64> = seq.addressed.iter().map(|a| a.address).collect();

    for i in 0..seq.addressed.len() {
        let aop = &seq.addressed[i];
        if is_terminator(&aop.op) {
            // fall-through address = last op of source instruction + length
            let after = aop.address.wrapping_add(aop.length as u64);
            if instruction_starts.contains(&after) && aop.op.opcode != OpCode::Return {
                leaders.insert(after);
            }
            if let Some(t) = branch_target(&aop.op) {
                if t >= region_start && t < region_end_exclusive && instruction_starts.contains(&t)
                {
                    leaders.insert(t);
                }
            }
        }
    }

    // 2. Partition ops into blocks by leader.
    let mut blocks: Vec<BasicBlock> = Vec::new();
    let mut block_of_addr: BTreeMap<u64, u32> = BTreeMap::new();
    let mut current: Option<BasicBlock> = None;
    let mut current_end: Option<u64> = None;
    let mut _prev_terminator = false;
    for (i, aop) in seq.addressed.iter().enumerate() {
        let start_new = leaders.contains(&aop.address)
            && current
                .as_ref()
                .map(|b| b.start != Some(aop.address))
                .unwrap_or(true);
        if start_new {
            if let Some(mut prev) = current.take() {
                prev.end = current_end;
                block_of_addr.insert(prev.start.unwrap(), prev.id);
                blocks.push(prev);
            }
            let bb = BasicBlock {
                id: blocks.len() as u32,
                start: Some(aop.address),
                end: None,
                ops: Vec::new(),
                successors: Vec::new(),
                predecessors: Vec::new(),
            };
            current = Some(bb);
        }
        if let Some(bb) = current.as_mut() {
            bb.ops.push(aop.op.clone());
        }
        current_end = Some(aop.address.wrapping_add(aop.length as u64));
        _prev_terminator = is_terminator(&aop.op);
        let _ = i;
    }
    if let Some(mut prev) = current.take() {
        prev.end = current_end;
        block_of_addr.insert(prev.start.unwrap(), prev.id);
        blocks.push(prev);
    }

    // 3. Wire successors.
    let mut external_exits = Vec::new();
    for bi in 0..blocks.len() {
        // Look at the last *addressed* op that came from this block's address
        // range to decide edges. We recover it by pulling the source address
        // of the block's last op.
        let last_op = blocks[bi].ops.last().cloned();
        let last_addr = block_last_source_address(seq, &blocks[bi]);
        let fallthrough = blocks[bi].end;

        let mut successors: Vec<u32> = Vec::new();
        match last_op.as_ref().map(|o| o.opcode) {
            Some(OpCode::Return) => {}
            Some(OpCode::Branch) => {
                if let Some(t) = last_op.as_ref().and_then(branch_target) {
                    if let Some(&tid) = block_of_addr.get(&t) {
                        successors.push(tid);
                    } else {
                        external_exits.push(bi as u32);
                    }
                }
            }
            Some(OpCode::CBranch) => {
                if let Some(t) = last_op.as_ref().and_then(branch_target) {
                    if let Some(&tid) = block_of_addr.get(&t) {
                        successors.push(tid);
                    } else {
                        external_exits.push(bi as u32);
                    }
                }
                if let Some(fa) = fallthrough {
                    if let Some(&fid) = block_of_addr.get(&fa) {
                        successors.push(fid);
                    }
                }
            }
            Some(OpCode::BranchInd) => {
                let mut had_any = false;
                for &l in extra_leaders {
                    if let Some(&tid) = block_of_addr.get(&l) {
                        successors.push(tid);
                        had_any = true;
                    }
                }
                if !had_any {
                    external_exits.push(bi as u32);
                }
            }
            Some(OpCode::Call) | Some(OpCode::CallInd) => {
                // Calls fall through unless annotated no-return.
                if let Some(fa) = fallthrough {
                    if let Some(&fid) = block_of_addr.get(&fa) {
                        successors.push(fid);
                    }
                }
            }
            _ => {
                if let Some(fa) = fallthrough {
                    if let Some(&fid) = block_of_addr.get(&fa) {
                        successors.push(fid);
                    }
                }
            }
        }
        let _ = last_addr;
        blocks[bi].successors = successors;
    }

    // 4. Populate predecessors.
    let mut predmap: HashMap<u32, Vec<u32>> = HashMap::new();
    for b in &blocks {
        for &s in &b.successors {
            predmap.entry(s).or_default().push(b.id);
        }
    }
    for b in &mut blocks {
        if let Some(p) = predmap.get(&b.id) {
            b.predecessors = p.clone();
        }
    }

    Cfg {
        blocks,
        block_of_addr,
        external_exits,
    }
}

fn block_last_source_address(seq: &IrSequence, bb: &BasicBlock) -> Option<u64> {
    let start = bb.start?;
    let end = bb.end.unwrap_or(u64::MAX);
    let mut last = None;
    for a in &seq.addressed {
        if a.address >= start && a.address < end {
            last = Some(a.address);
        }
    }
    last
}

/// Convenience: the set of varnodes written by each block (`defs[i]`) — input
/// to Cytron phi placement. Deliberately returns owned data so callers can
/// mutate without borrowing the CFG.
pub fn block_defs(cfg: &Cfg) -> Vec<HashSet<(ghidrust_ir::AddrSpace, u64)>> {
    let mut out = Vec::with_capacity(cfg.blocks.len());
    for b in &cfg.blocks {
        let mut set = HashSet::new();
        for op in &b.ops {
            if let Some(v) = &op.output {
                set.insert((v.space, v.offset));
            }
        }
        out.push(set);
    }
    out
}

/// Compute phi-placement candidates: for each variable, the union of
/// dominance-frontier blocks reached by its defs. Output maps
/// `(space, offset) → set of block ids needing a phi`. This is the direct
/// input for the rename pass we will land next.
pub fn phi_placement(cfg: &Cfg) -> BTreeMap<(ghidrust_ir::AddrSpace, u64), BTreeSet<u32>> {
    let df = cfg.dominance_frontiers();
    let defs = block_defs(cfg);
    let mut needs: BTreeMap<(ghidrust_ir::AddrSpace, u64), BTreeSet<u32>> = BTreeMap::new();
    // Build inverse: variable -> blocks that define it.
    let mut var_defs: BTreeMap<(ghidrust_ir::AddrSpace, u64), Vec<u32>> = BTreeMap::new();
    for (bi, set) in defs.iter().enumerate() {
        for v in set {
            var_defs.entry(*v).or_default().push(bi as u32);
        }
    }
    for (var, def_blocks) in var_defs {
        let mut worklist: Vec<u32> = def_blocks.clone();
        let mut seen: BTreeSet<u32> = def_blocks.iter().copied().collect();
        while let Some(b) = worklist.pop() {
            for &y in &df[b as usize] {
                let entry = needs.entry(var).or_default();
                if entry.insert(y) && !seen.contains(&y) {
                    seen.insert(y);
                    worklist.push(y);
                }
            }
        }
    }
    needs
}

#[cfg(test)]
mod tests {
    use super::*;
    use ghidrust_decode::decode_bytes;
    use ghidrust_ir::AddrSpace;
    use ghidrust_lift::lift_instructions;

    fn cfg_for(bytes: &[u8], base: u64) -> Cfg {
        let insns = decode_bytes(bytes, base, 32).unwrap();
        let last = insns.last().unwrap();
        let end = last.address + last.length as u64;
        let seq = lift_instructions(&insns);
        build_cfg(&seq, base, end)
    }

    #[test]
    fn cfg_single_block_for_linear_prologue() {
        // push rbp; mov rbp,rsp; xor eax,eax; pop rbp; ret
        let bytes = [0x55, 0x48, 0x89, 0xe5, 0x31, 0xc0, 0x5d, 0xc3];
        let cfg = cfg_for(&bytes, 0x1000);
        assert_eq!(cfg.len(), 1, "linear region should be single block");
        assert!(cfg.blocks[0].successors.is_empty(), "return has no succ");
        assert!(cfg.external_exits.is_empty());
    }

    #[test]
    fn cfg_conditional_splits_and_wires_fallthrough() {
        // 39 c1  cmp ecx, eax
        // 74 02  je  +2  (target = 0x2006)
        // 31 c0  xor eax, eax
        // c3     ret
        // 31 c9  xor ecx, ecx  (target lands here)
        // c3     ret
        let bytes = [0x39, 0xc1, 0x74, 0x02, 0x31, 0xc0, 0xc3, 0x31, 0xc9, 0xc3];
        let cfg = cfg_for(&bytes, 0x2000);
        assert!(
            cfg.len() >= 2,
            "expected multiple blocks, got {}",
            cfg.len()
        );
        // Entry block ends with CBranch → two successors.
        assert!(cfg.blocks[0].successors.len() >= 2);
        // Everything must be reachable from entry.
        let idom = cfg.dominators();
        assert!(idom.iter().any(|&d| d != u32::MAX));
    }

    #[test]
    fn dominance_frontiers_diamond() {
        // Construct a diamond CFG synthetically using known IR shape.
        let mut seq = IrSequence::new();
        // Block 0: cbranch to 0x100
        seq.push_addressed(
            0x0,
            2,
            PcodeOp::new(
                OpCode::CBranch,
                None,
                vec![Varnode::unique(0, 1), Varnode::constant(0x100, 8)],
            ),
        );
        // Block 1 (fallthrough at 0x2): branch to 0x200
        seq.push_addressed(
            0x2,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x200, 8)]),
        );
        // Block 2 (0x100): branch to 0x200
        seq.push_addressed(
            0x100,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x200, 8)]),
        );
        // Block 3 (0x200): ret
        seq.push_addressed(0x200, 1, PcodeOp::new(OpCode::Return, None, vec![]));
        let cfg = build_cfg(&seq, 0x0, 0x201);
        assert_eq!(cfg.len(), 4);
        let df = cfg.dominance_frontiers();
        // The join block (0x200) must appear in DF of both branch arms.
        let join_id = cfg.block_of_addr[&0x200];
        let arm1 = cfg.block_of_addr[&0x2];
        let arm2 = cfg.block_of_addr[&0x100];
        assert!(df[arm1 as usize].contains(&join_id));
        assert!(df[arm2 as usize].contains(&join_id));
    }

    #[test]
    fn phi_placement_returns_join_for_shared_def() {
        // Two blocks both write RAX before joining — the join should need a phi.
        let mut seq = IrSequence::new();
        let rax = Varnode::register(0, 8);
        // Block 0: cbranch to 0x100
        seq.push_addressed(
            0x0,
            2,
            PcodeOp::new(
                OpCode::CBranch,
                None,
                vec![Varnode::unique(0, 1), Varnode::constant(0x100, 8)],
            ),
        );
        // Block 1 (0x2): rax = 1; jmp 0x200
        seq.push_addressed(
            0x2,
            3,
            PcodeOp::new(
                OpCode::Copy,
                Some(rax.clone()),
                vec![Varnode::constant(1, 8)],
            ),
        );
        seq.push_addressed(
            0x5,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x200, 8)]),
        );
        // Block 2 (0x100): rax = 2; jmp 0x200
        seq.push_addressed(
            0x100,
            3,
            PcodeOp::new(
                OpCode::Copy,
                Some(rax.clone()),
                vec![Varnode::constant(2, 8)],
            ),
        );
        seq.push_addressed(
            0x103,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x200, 8)]),
        );
        // Block 3 (0x200): ret
        seq.push_addressed(0x200, 1, PcodeOp::new(OpCode::Return, None, vec![]));
        let cfg = build_cfg(&seq, 0x0, 0x201);
        let phis = phi_placement(&cfg);
        let join_id = cfg.block_of_addr[&0x200];
        let places = phis.get(&(AddrSpace::Register, 0)).expect("rax needs phi");
        assert!(places.contains(&join_id));
    }
}