jingle 0.6.8

SMT Modeling for Ghidra's PCODE
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

use std::collections::HashMap;
use std::fmt::Display;
use std::hash::Hash;
use std::marker::PhantomData;
use std::sync::Arc;

use crate::analysis::cfg::CfgState;
use crate::analysis::cpa::lattice::JoinSemiLattice;
use crate::analysis::cpa::residue::liveness_map::LivenessMapReducer;
use crate::analysis::cpa::{ConfigurableProgramAnalysis, RunnableConfigurableProgramAnalysis};
use crate::analysis::linkage::PcodeReverseLinkage;
use crate::analysis::liveness::cpa_state::LivenessCpaState;
use crate::analysis::pcode_store::PcodeStore;

pub mod annotated;
pub mod cpa_state;
pub mod state;

pub use annotated::LivenessAnnotated;
pub use state::LivenessState;

/// Self-contained backward liveness analysis.
///
/// Wraps a [`PcodeReverseLinkage<N>`] and drives the classic union-based
/// liveness computation:
///
/// ```text
/// live_in(node) = gen(node) ∪ (live_out(node) − kill(node))
/// ```
///
/// Use [`LivenessAnalysis::run_from_leaves`] to obtain a
/// `HashMap<N, LivenessState>` mapping every CFG node to its live-in set.
pub struct LivenessAnalysis<N: CfgState, L: PcodeReverseLinkage<N>> {
    linkage: Arc<L>,
    _phantom: PhantomData<N>,
}

impl<N, L> LivenessAnalysis<N, L>
where
    N: CfgState + JoinSemiLattice + Display + PartialOrd + Hash + Eq + 'static,
    L: PcodeReverseLinkage<N> + 'static,
{
    /// Construct a liveness analysis from any [`PcodeReverseLinkage`] implementor.
    #[must_use]
    pub fn new(linkage: Arc<L>) -> Self {
        Self {
            linkage,
            _phantom: PhantomData,
        }
    }

    /// Run backward liveness analysis from every leaf node, returning
    /// `live_in` sets keyed by CFG node.
    ///
    /// When multiple leaves can reach the same node, their liveness
    /// contributions are joined (union).
    pub fn run_from_leaves<'op, T: PcodeStore<'op> + ?Sized>(
        &self,
        store: &'op T,
    ) -> HashMap<N, LivenessState>
    where
        LivenessCpaState<N, L>: 'op,
    {
        let mut result: HashMap<N, LivenessState> = HashMap::new();
        for leaf in self.linkage.leaf_nodes() {
            // Compute live_in[leaf] = reads(leaf_op) when the op is available
            // (e.g. LoadedSleighContext), or empty when the store is a PcodeCfg
            // that only indexes ops keyed by edge sources (leaf has no outgoing
            // edges, so its op is absent from the CFG op map).
            let initial_live = leaf
                .concrete_location()
                .and_then(|addr| store.get_pcode_op_at(addr))
                .map(|op| LivenessState::empty().apply_transfer(op.as_ref()))
                .unwrap_or_else(LivenessState::empty);
            let initial = LivenessCpaState {
                location: leaf,
                live: initial_live,
                linkage: Arc::clone(&self.linkage),
            };
            let partial: HashMap<N, LivenessState> = self.run_cpa(initial, store);
            for (node, liveness) in partial {
                result
                    .entry(node)
                    .and_modify(|e| e.join(&liveness))
                    .or_insert(liveness);
            }
        }
        result
    }
}

impl<N, L> ConfigurableProgramAnalysis for LivenessAnalysis<N, L>
where
    N: CfgState + JoinSemiLattice + Display + PartialOrd + Hash + Eq + 'static,
    L: PcodeReverseLinkage<N> + 'static,
{
    type State = LivenessCpaState<N, L>;
    type Reducer<'op> = LivenessMapReducer<N, L>;
}