synth_core/
stack_depth.rs

1//! RQ-71-STACKDEPTH (#1341) types: the per-function stack profile and the
2//! settled per-export answer.
3//!
4//! These live in synth-core for the same reason `WcetIntermediate` does —
5//! `CompiledFunction` carries one, and synth-core cannot depend on the
6//! backend. The ANALYSIS (which needs `ArmInstruction` and the tripwired
7//! `may_move_sp` enumeration) stays in `synth_backend::stack_depth`.
8//!
9//! The composition rule is a MAX over the call tree, not a trip-weighted
10//! sum: a callee invoked 1000 times in a loop costs 1000x the cycles and
11//! ONCE the stack. See the backend module's docs for why that distinction
12//! is what makes this a sibling of the WCET pass rather than a field on it.
13
14use serde::{Deserialize, Serialize};
15
16/// Why no finite stack bound exists. Deliberately NOT `WcetDecline`: the two
17/// sets differ (see the module docs), and sharing the enum would silently tie
18/// a stack refusal to a cycle-counting one.
19#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
20pub enum StackDecline {
21    /// A cycle in the direct call graph — no finite depth exists.
22    Recursion,
23    /// `call_indirect`: the callee set is not statically known, so neither is
24    /// the depth below this point.
25    IndirectCall,
26    /// A direct call to a function outside this module (an import). Its frame
27    /// belongs to code synth did not emit.
28    ExternalCall,
29    /// A callee declined, and a decline propagates UP: a caller cannot be
30    /// bounded by an unbounded subtree.
31    CalleeUnbounded,
32    /// An instruction moves SP in a way this walker cannot price. The
33    /// give-up direction is a DECLINE, never a lower bound.
34    UnknownSpMove,
35}
36
37impl StackDecline {
38    /// The machine-readable reason string carried into the sidecar. The
39    /// `stack_depth_1341.py` oracle asserts on these exact spellings.
40    pub fn as_str(&self) -> &'static str {
41        match self {
42            StackDecline::Recursion => "recursion",
43            StackDecline::IndirectCall => "call_indirect",
44            StackDecline::ExternalCall => "external-call",
45            StackDecline::CalleeUnbounded => "callee-unbounded",
46            StackDecline::UnknownSpMove => "unknown-sp-move",
47        }
48    }
49}
50
51/// One function's own stack behaviour, before composition.
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct StackFrame {
54    pub name: String,
55    /// Maximum bytes below entry SP reached ANYWHERE in this function's own
56    /// body — prologue plus any transient push inside an expansion. Excludes
57    /// callees; composition adds the deepest one.
58    pub own_bytes: u64,
59    /// Direct-call labels (`func_<idx>`), in program order. Duplicates are kept:
60    /// resolving them is the composer's job, and the MAX is insensitive to
61    /// repeats anyway.
62    pub calls: Vec<String>,
63    /// Set when this function alone cannot be bounded.
64    pub decline: Option<StackDecline>,
65}
66
67/// The settled answer for one function.
68#[derive(Debug, Clone, Serialize, Deserialize)]
69pub enum StackResult {
70    Bounded { name: String, bytes: u64 },
71    Declined { name: String, reason: StackDecline },
72}
73
74/// The `synth-stack-v1` sidecar: one entry per compiled function, each either a
75/// bounded maximum native stack depth or a NAMED decline.
76///
77/// Keyed `exports` rather than `functions` because the number an embedder needs
78/// is per ENTRY POINT — it sizes the region a call into that export will use.
79#[derive(Debug, Clone, Serialize, Deserialize)]
80pub struct StackReport {
81    pub schema: String,
82    pub module: String,
83    pub exports: Vec<StackEntry>,
84}
85
86/// One export's settled answer, flattened for the sidecar.
87#[derive(Debug, Clone, Serialize, Deserialize)]
88pub struct StackEntry {
89    pub name: String,
90    /// `"bounded"` or `"declined"`.
91    pub status: String,
92    /// Present when bounded: the maximum bytes of native stack a call into this
93    /// export can consume, across the whole direct call tree.
94    #[serde(skip_serializing_if = "Option::is_none")]
95    pub bytes: Option<u64>,
96    /// Present when declined: the machine-readable reason.
97    #[serde(skip_serializing_if = "Option::is_none")]
98    pub reason: Option<String>,
99}
100
101impl StackReport {
102    pub fn new(module: impl Into<String>) -> Self {
103        StackReport {
104            schema: "synth-stack-v1".to_string(),
105            module: module.into(),
106            exports: Vec::new(),
107        }
108    }
109
110    /// `<output>.stack.json`, beside the object — the same shape `--emit-wcet`
111    /// uses, so a build step finds both the same way.
112    pub fn sidecar_path(output: &std::path::Path) -> std::path::PathBuf {
113        let mut s = output.as_os_str().to_os_string();
114        s.push(".stack.json");
115        std::path::PathBuf::from(s)
116    }
117
118    pub fn to_json(&self) -> Result<String, serde_json::Error> {
119        serde_json::to_string_pretty(self)
120    }
121}
122
123impl From<StackResult> for StackEntry {
124    fn from(r: StackResult) -> Self {
125        match r {
126            StackResult::Bounded { name, bytes } => StackEntry {
127                name,
128                status: "bounded".to_string(),
129                bytes: Some(bytes),
130                reason: None,
131            },
132            StackResult::Declined { name, reason } => StackEntry {
133                name,
134                status: "declined".to_string(),
135                bytes: None,
136                reason: Some(reason.as_str().to_string()),
137            },
138        }
139    }
140}
synth_core/stack_depth.rs

synth_core/
stack_depth.rs
