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
//! 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.
//!
//! `texrs --tiers file.tex` 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,
}
/// What the tiers did with one chunk.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ChunkTiers {
/// Which chunk this is — `main` for a whole TeX document.
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 {
writeln!(
f,
"loop @{:<4} trace-eligible={} traced={} blacklisted={}",
l.anchor, l.trace_eligible, l.traced, l.blacklisted
)?;
}
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 it.
///
/// The document 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. Asking without running
/// would report on bytecode nothing had executed.
pub fn report(src: &str) -> Result<Report, String> {
// The chunk lowered here is the same bytecode the run below executes, and
// fusevm keys its compiled code by the chunk's op hash, so asking this copy
// is asking about the run that just happened.
let chunk = crate::compile(src).map_err(|e| e.0)?;
crate::run_messages(src).map_err(|e| e.0)?;
Ok(inspect(&chunk))
}
/// Report on an already-executed document chunk.
pub fn inspect(chunk: &Chunk) -> Report {
Report {
chunks: vec![inspect_chunk("main", chunk)],
}
}
/// 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),
})
.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,
}
}
/// Whether `chunk` has a loop in it at all.
///
/// This is what decides whether the tracing JIT is switched on for a run: it
/// exists for hot loops and has nothing to offer a straight-line program. See
/// `runtime::run_with`.
pub fn has_loop(chunk: &fusevm::Chunk) -> bool {
!loop_anchors(&chunk.ops).is_empty()
}
/// 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,
}
}
/// A document whose bytecode this module's tests measure: register arithmetic,
/// which is what texrs lowers to native ops.
#[cfg(test)]
const PROGRAM: &str = "\\catcode`\\{=1 \\catcode`\\}=2\n\\count1=7\n\\advance\\count1 by 5\n\\multiply\\count1 by 3\n\\message{\\the\\count1}\n\\end\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, 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.
///
/// TeX has no loop of its own in this milestone (plain's `\loop` is macro
/// recursion, which the expander does not carry yet), so the loop is built
/// against fusevm directly rather than written in TeX.
#[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}");
}
/// A document's own bytecode: register assignment and arithmetic, and the
/// two `\message` host calls. It has no loop, so nothing is traced — the
/// point of the report here is the block tier's verdict on the chunk and
/// the list of ops that verdict rests on.
#[test]
fn a_document_reports_its_block_tier_verdict() {
let report = report(PROGRAM).expect("runs");
let chunk = &report.chunks[0];
assert!(chunk.ops > 0, "{report}");
assert!(
chunk.loops.is_empty(),
"a document has no loop yet: {report}"
);
// The host calls `\message` lowers to are what the block tier refuses,
// so the ineligible list is the honest reason the whole chunk is not
// compiled in one piece. If that ever changes, this test says so.
assert_eq!(
chunk.block_eligible,
chunk.ineligible.is_empty(),
"{report}"
);
}
/// A TeX loop reaches native code.
///
/// This is the end of the chain the rest of the engine exists to make
/// possible: TeX's `\def\r{… \ifnum … \r \fi}` idiom is recognised as a
/// loop, lowered as a rotated conditional back edge — the one shape
/// fusevm's trace compiler accepts — and the run enables the tracing JIT, so
/// the loop is compiled rather than interpreted. Every link is needed: the
/// recogniser, the rotation, and the switch. This test fails if any of them
/// is removed, which is what it is for; a document that reaches no native
/// code at all is a frontend claiming a JIT it does not use.
#[test]
fn a_tex_loop_reaches_a_compiled_trace() {
let src = "\\catcode`\\{=1 \\catcode`\\}=2 \\catcode`\\#=6\n\
\\count1=0\n\
\\def\\r{\\advance\\count1 by 1 \\ifnum\\count1<100000 \\r \\fi}\n\
\\r\n\\message{\\the\\count1 }\n\\end\n";
let report = report(src).expect("runs");
let loops = &report.chunks[0].loops;
assert_eq!(
loops.len(),
1,
"the loop idiom was not recognised: {report}"
);
assert!(
loops[0].trace_eligible,
"the loop body holds something the tracing tier refuses: {report}"
);
assert!(
loops[0].traced,
"the loop was eligible and never compiled -- either the rotation or \
the tracing JIT is gone: {report}"
);
assert!(report.reaches_native(), "{report}");
}
/// The report is about the document that ran, not about a fresh one: the
/// same source twice gives the same verdict.
#[test]
fn the_report_is_stable_across_runs() {
let a = report(PROGRAM).expect("runs");
let b = report(PROGRAM).expect("runs");
assert_eq!(a, b);
}
}