sp1_recursion_executor/
analyzed.rs

1use serde::{Deserialize, Serialize};
2
3use crate::{
4    instruction::{HintBitsInstr, HintExt2FeltsInstr, HintInstr, Instruction},
5    program::RawProgram,
6    BasicBlock, RecursionAirEventCount, SeqBlock,
7};
8
9/// An instruction that has been analyzed to find where it should insert its events.
10#[derive(Debug, Clone, Serialize, Deserialize)]
11pub struct AnalyzedInstruction<F> {
12    pub(crate) inner: Instruction<F>,
13    pub(crate) offset: usize,
14}
15
16impl<F> AnalyzedInstruction<F> {
17    pub const fn new(inner: Instruction<F>, offset: usize) -> Self {
18        Self { inner, offset }
19    }
20
21    pub const fn inner(&self) -> &Instruction<F> {
22        &self.inner
23    }
24}
25
26impl<F> RawProgram<Instruction<F>> {
27    /// Analyze the program to link an instruction to its corresponding event count.
28    ///
29    /// This allows the executor to preallocate the correct number of events and avoid copies
30    /// across blocks.
31    ///
32    /// This method is not unsafe, but the correctness of this method is a safety condition of
33    /// [`crate::Runtime::execute_raw`].
34    pub fn analyze(self) -> (RawProgram<AnalyzedInstruction<F>>, RecursionAirEventCount) {
35        fn analyze_block<T>(
36            block: SeqBlock<Instruction<T>>,
37            counts: &mut RecursionAirEventCount,
38        ) -> SeqBlock<AnalyzedInstruction<T>> {
39            /// Increment a counter and return the previous value.
40            fn incr(num: &mut usize, amt: usize) -> usize {
41                let start = *num;
42                *num += amt;
43
44                start
45            }
46
47            match block {
48                SeqBlock::Basic(instrs) => {
49                    let analyzed = instrs
50                        .instrs
51                        .into_iter()
52                        .map(|instr| {
53                            let start_offset = match &instr {
54                                Instruction::BaseAlu(_) => incr(&mut counts.base_alu_events, 1),
55                                Instruction::ExtAlu(_) => incr(&mut counts.ext_alu_events, 1),
56                                Instruction::Mem(_) => incr(&mut counts.mem_const_events, 1),
57                                Instruction::ExtFelt(_) => {
58                                    incr(&mut counts.ext_felt_conversion_events, 1)
59                                }
60                                Instruction::Poseidon2(_) => {
61                                    incr(&mut counts.poseidon2_wide_events, 1)
62                                }
63                                Instruction::Poseidon2LinearLayer(_) => {
64                                    incr(&mut counts.poseidon2_linear_layer_events, 1)
65                                }
66                                Instruction::Poseidon2SBox(_) => {
67                                    incr(&mut counts.poseidon2_sbox_events, 1)
68                                }
69                                Instruction::Select(_) => incr(&mut counts.select_events, 1),
70                                Instruction::Hint(HintInstr { output_addrs_mults })
71                                | Instruction::HintBits(HintBitsInstr {
72                                    output_addrs_mults,
73                                    input_addr: _, // No receive interaction for the hint operation
74                                }) => incr(&mut counts.mem_var_events, output_addrs_mults.len()),
75                                Instruction::HintExt2Felts(HintExt2FeltsInstr {
76                                    output_addrs_mults,
77                                    input_addr: _, // No receive interaction for the hint operation
78                                }) => incr(&mut counts.mem_var_events, output_addrs_mults.len()),
79                                Instruction::PrefixSumChecks(instr) => {
80                                    incr(&mut counts.prefix_sum_checks_events, instr.addrs.x1.len())
81                                }
82                                Instruction::HintAddCurve(instr) => incr(
83                                    &mut counts.mem_var_events,
84                                    instr.output_x_addrs_mults.len()
85                                        + instr.output_y_addrs_mults.len(),
86                                ),
87                                Instruction::CommitPublicValues(_) => {
88                                    incr(&mut counts.commit_pv_hash_events, 1)
89                                }
90                                // Just return 0 as a place holder, the executor code will not
91                                // create any events on these types anyway.
92                                Instruction::Print(_) | Instruction::DebugBacktrace(_) => 0,
93                            };
94
95                            AnalyzedInstruction::new(instr, start_offset)
96                        })
97                        .collect();
98
99                    SeqBlock::Basic(BasicBlock { instrs: analyzed })
100                }
101                SeqBlock::Parallel(par_blocks) => {
102                    let analyzed = par_blocks
103                        .into_iter()
104                        .map(|basic_blocks| {
105                            let analyzed: Vec<_> = basic_blocks
106                                .seq_blocks
107                                .into_iter()
108                                .map(|block| analyze_block(block, counts))
109                                .collect();
110
111                            RawProgram { seq_blocks: analyzed }
112                        })
113                        .collect();
114
115                    SeqBlock::Parallel(analyzed)
116                }
117            }
118        }
119
120        let mut counts = RecursionAirEventCount::default();
121        let analyzed_blocks =
122            self.seq_blocks.into_iter().map(|block| analyze_block(block, &mut counts)).collect();
123
124        (RawProgram { seq_blocks: analyzed_blocks }, counts)
125    }
126}
sp1_recursion_executor/analyzed.rs

sp1_recursion_executor/
analyzed.rs
