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
use serde::{Deserialize, Serialize};
use crate::{
instruction::{HintBitsInstr, HintExt2FeltsInstr, HintInstr, Instruction},
program::RawProgram,
BasicBlock, RecursionAirEventCount, SeqBlock,
};
/// An instruction that has been analyzed to find where it should insert its events.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct AnalyzedInstruction<F> {
pub(crate) inner: Instruction<F>,
pub(crate) offset: usize,
}
impl<F> AnalyzedInstruction<F> {
pub const fn new(inner: Instruction<F>, offset: usize) -> Self {
Self { inner, offset }
}
pub const fn inner(&self) -> &Instruction<F> {
&self.inner
}
}
impl<F> RawProgram<Instruction<F>> {
/// Analyze the program to link an instruction to its corresponding event count.
///
/// This allows the executor to preallocate the correct number of events and avoid copies
/// across blocks.
///
/// This method is not unsafe, but the correctness of this method is a safety condition of
/// [`crate::Runtime::execute_raw`].
pub fn analyze(self) -> (RawProgram<AnalyzedInstruction<F>>, RecursionAirEventCount) {
fn analyze_block<T>(
block: SeqBlock<Instruction<T>>,
counts: &mut RecursionAirEventCount,
) -> SeqBlock<AnalyzedInstruction<T>> {
/// Increment a counter and return the previous value.
fn incr(num: &mut usize, amt: usize) -> usize {
let start = *num;
*num += amt;
start
}
match block {
SeqBlock::Basic(instrs) => {
let analyzed = instrs
.instrs
.into_iter()
.map(|instr| {
let start_offset = match &instr {
Instruction::BaseAlu(_) => incr(&mut counts.base_alu_events, 1),
Instruction::ExtAlu(_) => incr(&mut counts.ext_alu_events, 1),
Instruction::Mem(_) => incr(&mut counts.mem_const_events, 1),
Instruction::ExtFelt(_) => {
incr(&mut counts.ext_felt_conversion_events, 1)
}
Instruction::Poseidon2(_) => {
incr(&mut counts.poseidon2_wide_events, 1)
}
Instruction::Poseidon2LinearLayer(_) => {
incr(&mut counts.poseidon2_linear_layer_events, 1)
}
Instruction::Poseidon2SBox(_) => {
incr(&mut counts.poseidon2_sbox_events, 1)
}
Instruction::Select(_) => incr(&mut counts.select_events, 1),
Instruction::Hint(HintInstr { output_addrs_mults })
| Instruction::HintBits(HintBitsInstr {
output_addrs_mults,
input_addr: _, // No receive interaction for the hint operation
}) => incr(&mut counts.mem_var_events, output_addrs_mults.len()),
Instruction::HintExt2Felts(HintExt2FeltsInstr {
output_addrs_mults,
input_addr: _, // No receive interaction for the hint operation
}) => incr(&mut counts.mem_var_events, output_addrs_mults.len()),
Instruction::PrefixSumChecks(instr) => {
incr(&mut counts.prefix_sum_checks_events, instr.addrs.x1.len())
}
Instruction::HintAddCurve(instr) => incr(
&mut counts.mem_var_events,
instr.output_x_addrs_mults.len()
+ instr.output_y_addrs_mults.len(),
),
Instruction::CommitPublicValues(_) => {
incr(&mut counts.commit_pv_hash_events, 1)
}
// Just return 0 as a place holder, the executor code will not
// create any events on these types anyway.
Instruction::Print(_) | Instruction::DebugBacktrace(_) => 0,
};
AnalyzedInstruction::new(instr, start_offset)
})
.collect();
SeqBlock::Basic(BasicBlock { instrs: analyzed })
}
SeqBlock::Parallel(par_blocks) => {
let analyzed = par_blocks
.into_iter()
.map(|basic_blocks| {
let analyzed: Vec<_> = basic_blocks
.seq_blocks
.into_iter()
.map(|block| analyze_block(block, counts))
.collect();
RawProgram { seq_blocks: analyzed }
})
.collect();
SeqBlock::Parallel(analyzed)
}
}
}
let mut counts = RecursionAirEventCount::default();
let analyzed_blocks =
self.seq_blocks.into_iter().map(|block| analyze_block(block, &mut counts)).collect();
(RawProgram { seq_blocks: analyzed_blocks }, counts)
}
}