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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
//! Which fusevm execution tier a program's bytecode actually reaches.
//!
//! Enabling the JIT is not the same as being compiled by it, and the only
//! honest way to tell the two apart is to ask the VM. This module runs a
//! program and then queries fusevm's own eligibility and cache predicates —
//! `is_block_eligible`, `block_jit_is_compiled`, `trace_is_compiled`,
//! `find_jit_region` — so the answer comes from the compiler that would have
//! done the work rather than from an assumption about it.
//!
//! `python --tiers script.py` prints the report.
use std::collections::BTreeMap;
use fusevm::{Chunk, ChunkBuilder, JitCompiler, Op};
/// A loop header — the target of a backward branch — and what became of it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Loop {
/// Op index of the loop header the backward branch jumps to.
pub anchor: usize,
/// Whether fusevm would accept this loop's body as a trace. Asked of
/// `is_trace_eligible` with the body's ops — the same predicate the
/// recorder applies to what it recorded, which for a loop whose body has
/// no early exit is the same op sequence.
pub trace_eligible: bool,
/// Whether a compiled trace is installed for this header after the run.
pub traced: bool,
/// Whether the tracing JIT gave up on this header.
pub blacklisted: bool,
/// The function whose copy in `main` holds this loop, for a loop in a body
/// the compiler linked there (`FuncDef::linked`). `None` is the chunk's
/// own code.
pub linked_from: Option<String>,
}
/// What the tiers did with one chunk.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ChunkTiers {
/// Which chunk this is — `main` for a whole Python program.
pub name: String,
/// Ops in the compiled chunk.
pub ops: usize,
/// Whether every op in the chunk is block-JIT eligible, which is what the
/// whole-chunk block tier requires.
pub block_eligible: bool,
/// Whether the block tier holds compiled native code for this chunk.
pub block_compiled: bool,
/// The largest contiguous block-eligible op range, if any is large enough
/// for fusevm to consider it worth compiling.
pub largest_eligible_region: Option<(usize, usize)>,
/// Every loop header, and whether the tracing JIT compiled it.
pub loops: Vec<Loop>,
/// Op kinds the **block** tier refuses, by occurrence count — what keeps
/// the whole chunk from being compiled in one piece.
///
/// Not the same question as whether a loop is traced: the tracing tier
/// takes `GetVar` / `SetVar` (fusevm promotes a referenced global to a
/// register at trace entry and spills it at every exit), so a chunk can
/// list those here and still reach native code through a trace.
pub ineligible: BTreeMap<String, usize>,
}
impl ChunkTiers {
/// Whether any tier holds compiled native code for this chunk.
pub fn reaches_native(&self) -> bool {
self.block_compiled || self.loops.iter().any(|l| l.traced)
}
}
/// What the tiers did with one program.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Report {
/// Every chunk the program compiled to, in the order they were lowered.
pub chunks: Vec<ChunkTiers>,
}
impl Report {
/// Whether any tier holds compiled native code for any of the program's
/// chunks.
pub fn reaches_native(&self) -> bool {
self.chunks.iter().any(|c| c.reaches_native())
}
}
impl std::fmt::Display for ChunkTiers {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
writeln!(f, "ops {}", self.ops)?;
writeln!(f, "block-JIT eligible {}", self.block_eligible)?;
writeln!(f, "block-JIT compiled {}", self.block_compiled)?;
match self.largest_eligible_region {
Some((s, e)) => writeln!(f, "largest eligible region {s}..{e} ({} ops)", e - s)?,
None => writeln!(f, "largest eligible region none")?,
}
if self.loops.is_empty() {
writeln!(f, "loops none")?;
}
for l in &self.loops {
write!(
f,
"loop @{:<4} trace-eligible={} traced={} blacklisted={}",
l.anchor, l.trace_eligible, l.traced, l.blacklisted
)?;
match &l.linked_from {
Some(func) => writeln!(f, " (in the linked copy of fn {func})")?,
None => writeln!(f)?,
}
}
if self.ineligible.is_empty() {
writeln!(f, "block-ineligible ops none")?;
} else {
writeln!(f, "block-ineligible ops")?;
for (name, count) in &self.ineligible {
writeln!(f, " {name:<22}{count}")?;
}
}
Ok(())
}
}
impl std::fmt::Display for Report {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
// A single-chunk program needs no section headers; the fleet's
// multi-chunk frontends label each one.
let label = self.chunks.len() > 1;
for c in &self.chunks {
if label {
writeln!(f, "== {} ==", c.name)?;
}
write!(f, "{c}")?;
}
write!(f, "reaches native code {}", self.reaches_native())
}
}
/// Compile and run `src`, then report which tiers took each of its chunks.
///
/// The program is run because tier membership is a runtime fact: the block tier
/// compiles after its warmup threshold and the tracing tier only after a loop
/// has gone round enough times to be recorded. pythonrs writes program output
/// straight to the process stdout, so the program's own output precedes the
/// report — what is measured is what an ordinary run does.
///
/// The inspection compile happens *before* the run and never loads onto the
/// host, so both compiles see func/try id offsets of 0 (`rebase_program` is a
/// no-op there) and emit byte-identical ops. That is what lets fusevm's
/// op-hash-keyed caches answer for the run that just happened.
pub fn report(src: &str) -> Result<Report, String> {
let prog = crate::compile(src)?;
let named = program_chunks(&prog);
crate::eval_str(src)?;
let mut report = inspect_all(&named);
label_linked_loops(&mut report.chunks[0], &prog);
Ok(report)
}
/// Name, for each loop in `main`, the function whose linked copy holds it.
/// The copies sit back to back after the module code, so a loop belongs to the
/// last copy starting at or before its header.
fn label_linked_loops(main: &mut ChunkTiers, prog: &crate::compiler::Program) {
let mut copies: Vec<(usize, &str)> = prog
.functions
.iter()
.filter_map(|(_, f)| Some((f.linked? as usize, f.qualname.as_str())))
.collect();
copies.sort_unstable();
for l in &mut main.loops {
l.linked_from = copies
.iter()
.rev()
.find(|(entry, _)| *entry <= l.anchor)
.map(|(_, name)| name.to_string());
}
}
/// Every chunk a compiled program holds, named for the report.
///
/// A Python program is not one chunk: the module body, every `def`, every
/// comprehension/lambda body, and every arm of a `try` lower to their own
/// chunk. A hot loop usually lives in one of the latter, so reporting only
/// `main` would answer the wrong question. `main` also holds a copy of each
/// function the compiler linked into it, which is where a loop in a function
/// called from module code runs; its loops are labelled with that function.
fn program_chunks(prog: &crate::compiler::Program) -> Vec<(String, Chunk)> {
let mut out = vec![("main".to_string(), prog.main.clone())];
for (_, f) in &prog.functions {
out.push((format!("fn {}", f.qualname), f.chunk.clone()));
}
for (i, p) in prog.procs.iter().enumerate() {
out.push((format!("proc #{i} ({})", p.name), p.chunk.clone()));
}
for (i, t) in prog.tries.iter().enumerate() {
out.push((format!("try #{i} body"), t.body.clone()));
for (j, h) in t.handlers.iter().enumerate() {
if let Some(ty) = &h.typ {
out.push((format!("try #{i} except[{j}] type"), ty.clone()));
}
out.push((format!("try #{i} except[{j}]"), h.body.clone()));
}
if let Some(c) = &t.orelse {
out.push((format!("try #{i} else"), c.clone()));
}
if let Some(c) = &t.finalbody {
out.push((format!("try #{i} finally"), c.clone()));
}
}
out
}
/// Report on one already-executed chunk, as a whole-program report. Used by
/// tests that build a chunk by hand.
pub fn inspect(chunk: &Chunk) -> Report {
Report {
chunks: vec![inspect_chunk("main", chunk)],
}
}
/// Report on every chunk a compiled program holds, in lowering order.
pub fn inspect_all(named: &[(String, Chunk)]) -> Report {
Report {
chunks: named.iter().map(|(n, c)| inspect_chunk(n, c)).collect(),
}
}
/// Report on one already-executed chunk.
pub fn inspect_chunk(name: &str, chunk: &Chunk) -> ChunkTiers {
let jit = JitCompiler::new();
let loops = loop_anchors(&chunk.ops)
.into_iter()
.map(|anchor| Loop {
anchor,
trace_eligible: body_of(&chunk.ops, anchor)
.is_some_and(|body| jit.is_trace_eligible(body, anchor)),
traced: jit.trace_is_compiled(chunk, anchor),
blacklisted: jit.trace_is_blacklisted(chunk, anchor),
linked_from: None,
})
.collect();
let mut ineligible: BTreeMap<String, usize> = BTreeMap::new();
for op in &chunk.ops {
if !op_is_eligible(&jit, op) {
*ineligible.entry(op_name(op)).or_default() += 1;
}
}
ChunkTiers {
name: name.to_string(),
ops: chunk.ops.len(),
block_eligible: jit.is_block_eligible(chunk),
block_compiled: jit.block_jit_is_compiled(chunk),
largest_eligible_region: jit.find_jit_region(chunk),
loops,
ineligible,
}
}
/// Every op index a backward branch jumps to — fusevm anchors a trace at each.
fn loop_anchors(ops: &[Op]) -> Vec<usize> {
let mut anchors: Vec<usize> = ops
.iter()
.enumerate()
.filter_map(|(ip, op)| match op {
Op::Jump(t)
| Op::JumpIfTrue(t)
| Op::JumpIfFalse(t)
| Op::JumpIfTrueKeep(t)
| Op::JumpIfFalseKeep(t)
if *t <= ip =>
{
Some(*t)
}
_ => None,
})
.collect();
anchors.sort_unstable();
anchors.dedup();
anchors
}
/// The op sequence one iteration of the loop at `anchor` runs: from the header
/// through the backward branch that closes it. `None` when nothing closes it.
fn body_of(ops: &[Op], anchor: usize) -> Option<&[Op]> {
let close = ops.iter().enumerate().position(|(ip, op)| {
ip >= anchor
&& matches!(
op,
Op::Jump(t) | Op::JumpIfTrue(t) | Op::JumpIfFalse(t)
if *t == anchor
)
})?;
Some(&ops[anchor..=close])
}
/// Whether fusevm's block tier accepts this op, asked by handing the JIT a
/// chunk holding just that op. Whole-chunk eligibility is the conjunction of
/// the per-op decision, so a one-op chunk isolates it.
fn op_is_eligible(jit: &JitCompiler, op: &Op) -> bool {
let mut b = ChunkBuilder::new();
b.emit(op.clone(), 1);
jit.is_block_eligible(&b.build())
}
/// An op's variant name, without its operands, so occurrences group.
fn op_name(op: &Op) -> String {
let text = format!("{op:?}");
match text.split_once('(') {
Some((name, _)) => name.to_string(),
None => text,
}
}
/// The counted loop this module's tests measure, in the frontend's own syntax.
#[cfg(test)]
const PROGRAM: &str = "def f(n):\n t = 0\n i = 0\n while i < n:\n t += i\n i += 1\n return t\n\nf(200000)\n";
#[cfg(test)]
mod tests {
use super::*;
/// The report can say yes. A counted loop built by hand in the rotated
/// shape — entered at its body, closed by a conditional backward branch —
/// is the one shape fusevm's trace compiler accepts (`jit.rs` compiles a
/// `JumpIfTrue`/`JumpIfFalse` close and bails on an unconditional `Jump`),
/// and after a run the report finds the installed trace. Without this,
/// every "not traced" below could be a report that only ever says no.
#[test]
fn a_rotated_slot_loop_reaches_a_compiled_trace() {
let mut b = ChunkBuilder::new();
b.emit(Op::LoadInt(0), 1);
b.emit(Op::SetSlot(0), 1);
let enter = b.emit(Op::Jump(usize::MAX), 1);
let body = b.current_pos();
b.emit(Op::GetSlot(0), 1);
b.emit(Op::LoadInt(1), 1);
b.emit(Op::Add, 1);
b.emit(Op::SetSlot(0), 1);
let cond = b.current_pos();
b.patch_jump(enter, cond);
b.emit(Op::GetSlot(0), 1);
b.emit(Op::LoadInt(200_000), 1);
b.emit(Op::NumLt, 1);
b.emit(Op::JumpIfTrue(body), 1);
b.emit(Op::GetSlot(0), 1);
let chunk = b.build();
let mut vm = fusevm::VM::new(chunk.clone());
vm.enable_tracing_jit();
vm.run();
let report = inspect(&chunk);
assert_eq!(report.chunks[0].loops.len(), 1, "{report}");
assert!(report.chunks[0].loops[0].traced, "{report}");
assert!(report.reaches_native(), "{report}");
}
/// The top level is not where the loop is — the report has to walk every
/// chunk to find it. This pins the multi-chunk walk itself: reporting only
/// `main` would find no loop of the module's own for a program that plainly
/// has one. The loop `main` does hold is its linked copy of `f`, and is
/// labelled as such.
#[test]
fn the_loop_lives_in_a_chunk_other_than_main() {
let report = report(PROGRAM).expect("runs");
assert!(report.chunks.len() > 1, "{report}");
assert!(
report.chunks[0]
.loops
.iter()
.all(|l| l.linked_from.as_deref() == Some("f")),
"main has no loop of its own: {report}"
);
assert!(
report.chunks[1..].iter().any(|c| !c.loops.is_empty()),
"{report}"
);
}
/// Python reaches native code. A function's locals are frame slots and its
/// `while` is emitted closing on a conditional backward branch, which is
/// the shape fusevm's trace compiler accepts — so the loop is recorded,
/// compiled, and installed. This is the assertion that would fail first if
/// the loop lowering or the slot allocation regressed.
#[test]
fn a_function_local_counted_loop_reaches_a_compiled_trace() {
let report = report(PROGRAM).expect("runs");
let looped = report
.chunks
.iter()
.find(|c| !c.loops.is_empty())
.unwrap_or_else(|| panic!("a chunk with a loop: {report}"));
assert!(looped.loops[0].trace_eligible, "{report}");
assert!(looped.loops[0].traced, "{report}");
assert!(!looped.loops[0].blacklisted, "{report}");
assert!(report.reaches_native(), "{report}");
}
}