openvm_circuit/arch/
execution.rs

1use openvm_circuit_primitives::AlignedBytesBorrow;
2use openvm_circuit_primitives_derive::AlignedBorrow;
3use openvm_instructions::{
4    instruction::Instruction, program::DEFAULT_PC_STEP, PhantomDiscriminant, VmOpcode,
5};
6use openvm_stark_backend::{
7    interaction::{BusIndex, InteractionBuilder, PermutationCheckBus},
8    p3_field::FieldAlgebra,
9};
10use rand::rngs::StdRng;
11use serde::{Deserialize, Serialize};
12use thiserror::Error;
13
14use super::{execution_mode::ExecutionCtxTrait, Streams, VmExecState};
15#[cfg(feature = "tco")]
16use crate::arch::interpreter::InterpretedInstance;
17#[cfg(feature = "metrics")]
18use crate::metrics::VmMetrics;
19use crate::{
20    arch::{execution_mode::MeteredExecutionCtxTrait, ExecutorInventoryError, MatrixRecordArena},
21    system::{
22        memory::online::{GuestMemory, TracingMemory},
23        program::ProgramBus,
24    },
25};
26
27#[derive(Error, Debug)]
28pub enum ExecutionError {
29    #[error("execution failed at pc {pc}, err: {msg}")]
30    Fail { pc: u32, msg: &'static str },
31    #[error("pc {0} out of bounds")]
32    PcOutOfBounds(u32),
33    #[error("unreachable instruction at pc {0}")]
34    Unreachable(u32),
35    #[error("at pc {pc}, opcode {opcode} was not enabled")]
36    DisabledOperation { pc: u32, opcode: VmOpcode },
37    #[error("at pc = {pc}")]
38    HintOutOfBounds { pc: u32 },
39    #[error("at pc {pc}, tried to publish into index {public_value_index} when num_public_values = {num_public_values}")]
40    PublicValueIndexOutOfBounds {
41        pc: u32,
42        num_public_values: usize,
43        public_value_index: usize,
44    },
45    #[error("at pc {pc}, tried to publish {new_value} into index {public_value_index} but already had {existing_value}")]
46    PublicValueNotEqual {
47        pc: u32,
48        public_value_index: usize,
49        existing_value: usize,
50        new_value: usize,
51    },
52    #[error("at pc {pc}, phantom sub-instruction not found for discriminant {}", .discriminant.0)]
53    PhantomNotFound {
54        pc: u32,
55        discriminant: PhantomDiscriminant,
56    },
57    #[error("at pc {pc}, discriminant {}, phantom error: {inner}", .discriminant.0)]
58    Phantom {
59        pc: u32,
60        discriminant: PhantomDiscriminant,
61        inner: eyre::Error,
62    },
63    #[error("program must terminate")]
64    DidNotTerminate,
65    #[error("program exit code {0}")]
66    FailedWithExitCode(u32),
67    #[error("trace buffer out of bounds: requested {requested} but capacity is {capacity}")]
68    TraceBufferOutOfBounds { requested: usize, capacity: usize },
69    #[error("instruction counter overflow: {instret} + {num_insns} > u64::MAX")]
70    InstretOverflow { instret: u64, num_insns: u64 },
71    #[error("inventory error: {0}")]
72    Inventory(#[from] ExecutorInventoryError),
73    #[error("static program error: {0}")]
74    Static(#[from] StaticProgramError),
75}
76
77/// Errors in the program that can be statically analyzed before runtime.
78#[derive(Error, Debug)]
79pub enum StaticProgramError {
80    #[error("invalid instruction at pc {0}")]
81    InvalidInstruction(u32),
82    #[error("Too many executors")]
83    TooManyExecutors,
84    #[error("at pc {pc}, opcode {opcode} was not enabled")]
85    DisabledOperation { pc: u32, opcode: VmOpcode },
86    #[error("Executor not found for opcode {opcode}")]
87    ExecutorNotFound { opcode: VmOpcode },
88}
89
90/// Function pointer for interpreter execution with function signature `(pre_compute, instret, pc,
91/// arg, exec_state)`. The `pre_compute: &[u8]` is a pre-computed buffer of data
92/// corresponding to a single instruction. The contents of `pre_compute` are determined from the
93/// program code as specified by the [Executor] and [MeteredExecutor] traits.
94/// `arg` is a runtime constant that we want to keep in register:
95/// - For pure execution it is `instret_end`
96/// - For metered cost execution it is the `max_execution_cost`
97/// - For metered execution it is `segment_check_insns`
98pub type ExecuteFunc<F, CTX> = unsafe fn(
99    pre_compute: &[u8],
100    instret: &mut u64,
101    pc: &mut u32,
102    arg: u64,
103    exec_state: &mut VmExecState<F, GuestMemory, CTX>,
104);
105
106/// Handler for tail call elimination. The `CTX` is assumed to contain pointers to the pre-computed
107/// buffer and the function handler table.
108///
109/// - `pre_compute_buf` is the starting pointer of the pre-computed buffer.
110/// - `handlers` is the starting pointer of the table of function pointers of `Handler` type. The
111///   pointer is typeless to avoid self-referential types.
112/// - `pc`, `instret`, `instret_end` are passed as separate arguments for efficiency
113///
114/// `arg` is a runtime constant that we want to keep in register:
115/// - For pure execution it is `instret_end`
116/// - For metered cost execution it is the `max_execution_cost`
117/// - For metered execution it is `segment_check_insns`
118#[cfg(feature = "tco")]
119pub type Handler<F, CTX> = unsafe fn(
120    interpreter: &InterpretedInstance<F, CTX>,
121    instret: u64,
122    pc: u32,
123    arg: u64,
124    exec_state: &mut VmExecState<F, GuestMemory, CTX>,
125);
126
127/// Trait for pure execution via a host interpreter. The trait methods provide the methods to
128/// pre-process the program code into function pointers which operate on `pre_compute` instruction
129/// data.
130// @dev: In the codebase this is sometimes referred to as (E1).
131pub trait Executor<F> {
132    fn pre_compute_size(&self) -> usize;
133
134    #[cfg(not(feature = "tco"))]
135    fn pre_compute<Ctx>(
136        &self,
137        pc: u32,
138        inst: &Instruction<F>,
139        data: &mut [u8],
140    ) -> Result<ExecuteFunc<F, Ctx>, StaticProgramError>
141    where
142        Ctx: ExecutionCtxTrait;
143
144    /// Returns a function pointer with tail call optimization. The handler function assumes that
145    /// the pre-compute buffer it receives is the populated `data`.
146    // NOTE: we could have used `pre_compute` above to populate `data`, but the implementations were
147    // simpler to keep `handler` entirely separate from `pre_compute`.
148    #[cfg(feature = "tco")]
149    fn handler<Ctx>(
150        &self,
151        pc: u32,
152        inst: &Instruction<F>,
153        data: &mut [u8],
154    ) -> Result<Handler<F, Ctx>, StaticProgramError>
155    where
156        Ctx: ExecutionCtxTrait;
157}
158
159/// Trait for metered execution via a host interpreter. The trait methods provide the methods to
160/// pre-process the program code into function pointers which operate on `pre_compute` instruction
161/// data which contains auxiliary data (e.g., corresponding AIR ID) for metering purposes.
162// @dev: In the codebase this is sometimes referred to as (E2).
163pub trait MeteredExecutor<F> {
164    fn metered_pre_compute_size(&self) -> usize;
165
166    #[cfg(not(feature = "tco"))]
167    fn metered_pre_compute<Ctx>(
168        &self,
169        air_idx: usize,
170        pc: u32,
171        inst: &Instruction<F>,
172        data: &mut [u8],
173    ) -> Result<ExecuteFunc<F, Ctx>, StaticProgramError>
174    where
175        Ctx: MeteredExecutionCtxTrait;
176
177    /// Returns a function pointer with tail call optimization. The handler function assumes that
178    /// the pre-compute buffer it receives is the populated `data`.
179    // NOTE: we could have used `metered_pre_compute` above to populate `data`, but the
180    // implementations were simpler to keep `metered_handler` entirely separate from
181    // `metered_pre_compute`.
182    #[cfg(feature = "tco")]
183    fn metered_handler<Ctx>(
184        &self,
185        air_idx: usize,
186        pc: u32,
187        inst: &Instruction<F>,
188        data: &mut [u8],
189    ) -> Result<Handler<F, Ctx>, StaticProgramError>
190    where
191        Ctx: MeteredExecutionCtxTrait;
192}
193
194/// Trait for preflight execution via a host interpreter. The trait methods allow execution of
195/// instructions via enum dispatch within an interpreter. This execution is specialized to record
196/// "records" of execution which will be ingested later for trace matrix generation. The records are
197/// stored in a record arena, which is provided in the [VmStateMut] argument.
198// NOTE: In the codebase this is sometimes referred to as (E3).
199pub trait PreflightExecutor<F, RA = MatrixRecordArena<F>> {
200    /// Runtime execution of the instruction, if the instruction is owned by the
201    /// current instance. May internally store records of this call for later trace generation.
202    fn execute(
203        &self,
204        state: VmStateMut<F, TracingMemory, RA>,
205        instruction: &Instruction<F>,
206    ) -> Result<(), ExecutionError>;
207
208    /// For display purposes. From absolute opcode as `usize`, return the string name of the opcode
209    /// if it is a supported opcode by the present executor.
210    fn get_opcode_name(&self, opcode: usize) -> String;
211}
212
213/// Global VM state accessible during instruction execution.
214/// The state is generic in guest memory `MEM` and additional record arena `RA`.
215/// The host state is execution context specific.
216#[derive(derive_new::new)]
217pub struct VmStateMut<'a, F, MEM, RA> {
218    pub pc: &'a mut u32,
219    pub memory: &'a mut MEM,
220    pub streams: &'a mut Streams<F>,
221    pub rng: &'a mut StdRng,
222    /// Custom public values to be set by the system PublicValuesExecutor
223    pub(crate) custom_pvs: &'a mut Vec<Option<F>>,
224    pub ctx: &'a mut RA,
225    #[cfg(feature = "metrics")]
226    pub metrics: &'a mut VmMetrics,
227}
228
229/// Wrapper type for metered pre-computed data, which is always an AIR index together with the
230/// pre-computed data for pure execution.
231#[derive(Clone, AlignedBytesBorrow)]
232#[repr(C)]
233pub struct E2PreCompute<DATA> {
234    pub chip_idx: u32,
235    pub data: DATA,
236}
237
238#[repr(C)]
239#[derive(Clone, Copy, Debug, PartialEq, Default, AlignedBorrow, Serialize, Deserialize)]
240pub struct ExecutionState<T> {
241    pub pc: T,
242    pub timestamp: T,
243}
244
245#[derive(Clone, Copy, Debug)]
246pub struct ExecutionBus {
247    pub inner: PermutationCheckBus,
248}
249
250impl ExecutionBus {
251    pub const fn new(index: BusIndex) -> Self {
252        Self {
253            inner: PermutationCheckBus::new(index),
254        }
255    }
256
257    #[inline(always)]
258    pub fn index(&self) -> BusIndex {
259        self.inner.index
260    }
261}
262
263#[derive(Copy, Clone, Debug)]
264pub struct ExecutionBridge {
265    execution_bus: ExecutionBus,
266    program_bus: ProgramBus,
267}
268
269pub struct ExecutionBridgeInteractor<AB: InteractionBuilder> {
270    execution_bus: ExecutionBus,
271    program_bus: ProgramBus,
272    opcode: AB::Expr,
273    operands: Vec<AB::Expr>,
274    from_state: ExecutionState<AB::Expr>,
275    to_state: ExecutionState<AB::Expr>,
276}
277
278pub enum PcIncOrSet<T> {
279    Inc(T),
280    Set(T),
281}
282
283impl<T> ExecutionState<T> {
284    pub fn new(pc: impl Into<T>, timestamp: impl Into<T>) -> Self {
285        Self {
286            pc: pc.into(),
287            timestamp: timestamp.into(),
288        }
289    }
290
291    #[allow(clippy::should_implement_trait)]
292    pub fn from_iter<I: Iterator<Item = T>>(iter: &mut I) -> Self {
293        let mut next = || iter.next().unwrap();
294        Self {
295            pc: next(),
296            timestamp: next(),
297        }
298    }
299
300    pub fn flatten(self) -> [T; 2] {
301        [self.pc, self.timestamp]
302    }
303
304    pub fn get_width() -> usize {
305        2
306    }
307
308    pub fn map<U: Clone, F: Fn(T) -> U>(self, function: F) -> ExecutionState<U> {
309        ExecutionState::from_iter(&mut self.flatten().map(function).into_iter())
310    }
311}
312
313impl ExecutionBus {
314    /// Caller must constrain that `enabled` is boolean.
315    pub fn execute_and_increment_pc<AB: InteractionBuilder>(
316        &self,
317        builder: &mut AB,
318        enabled: impl Into<AB::Expr>,
319        prev_state: ExecutionState<AB::Expr>,
320        timestamp_change: impl Into<AB::Expr>,
321    ) {
322        let next_state = ExecutionState {
323            pc: prev_state.pc.clone() + AB::F::ONE,
324            timestamp: prev_state.timestamp.clone() + timestamp_change.into(),
325        };
326        self.execute(builder, enabled, prev_state, next_state);
327    }
328
329    /// Caller must constrain that `enabled` is boolean.
330    pub fn execute<AB: InteractionBuilder>(
331        &self,
332        builder: &mut AB,
333        enabled: impl Into<AB::Expr>,
334        prev_state: ExecutionState<impl Into<AB::Expr>>,
335        next_state: ExecutionState<impl Into<AB::Expr>>,
336    ) {
337        let enabled = enabled.into();
338        self.inner.receive(
339            builder,
340            [prev_state.pc.into(), prev_state.timestamp.into()],
341            enabled.clone(),
342        );
343        self.inner.send(
344            builder,
345            [next_state.pc.into(), next_state.timestamp.into()],
346            enabled,
347        );
348    }
349}
350
351impl ExecutionBridge {
352    pub fn new(execution_bus: ExecutionBus, program_bus: ProgramBus) -> Self {
353        Self {
354            execution_bus,
355            program_bus,
356        }
357    }
358
359    /// If `to_pc` is `Some`, then `pc_inc` is ignored and the `to_state` uses `to_pc`. Otherwise
360    /// `to_pc = from_pc + pc_inc`.
361    pub fn execute_and_increment_or_set_pc<AB: InteractionBuilder>(
362        &self,
363        opcode: impl Into<AB::Expr>,
364        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
365        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
366        timestamp_change: impl Into<AB::Expr>,
367        pc_kind: impl Into<PcIncOrSet<AB::Expr>>,
368    ) -> ExecutionBridgeInteractor<AB> {
369        let to_state = ExecutionState {
370            pc: match pc_kind.into() {
371                PcIncOrSet::Set(to_pc) => to_pc,
372                PcIncOrSet::Inc(pc_inc) => from_state.pc.clone().into() + pc_inc,
373            },
374            timestamp: from_state.timestamp.clone().into() + timestamp_change.into(),
375        };
376        self.execute(opcode, operands, from_state, to_state)
377    }
378
379    pub fn execute_and_increment_pc<AB: InteractionBuilder>(
380        &self,
381        opcode: impl Into<AB::Expr>,
382        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
383        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
384        timestamp_change: impl Into<AB::Expr>,
385    ) -> ExecutionBridgeInteractor<AB> {
386        let to_state = ExecutionState {
387            pc: from_state.pc.clone().into() + AB::Expr::from_canonical_u32(DEFAULT_PC_STEP),
388            timestamp: from_state.timestamp.clone().into() + timestamp_change.into(),
389        };
390        self.execute(opcode, operands, from_state, to_state)
391    }
392
393    pub fn execute<AB: InteractionBuilder>(
394        &self,
395        opcode: impl Into<AB::Expr>,
396        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
397        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
398        to_state: ExecutionState<impl Into<AB::Expr>>,
399    ) -> ExecutionBridgeInteractor<AB> {
400        ExecutionBridgeInteractor {
401            execution_bus: self.execution_bus,
402            program_bus: self.program_bus,
403            opcode: opcode.into(),
404            operands: operands.into_iter().map(Into::into).collect(),
405            from_state: from_state.map(Into::into),
406            to_state: to_state.map(Into::into),
407        }
408    }
409}
410
411impl<AB: InteractionBuilder> ExecutionBridgeInteractor<AB> {
412    /// Caller must constrain that `enabled` is boolean.
413    pub fn eval(self, builder: &mut AB, enabled: impl Into<AB::Expr>) {
414        let enabled = enabled.into();
415
416        // Interaction with program
417        self.program_bus.lookup_instruction(
418            builder,
419            self.from_state.pc.clone(),
420            self.opcode,
421            self.operands,
422            enabled.clone(),
423        );
424
425        self.execution_bus
426            .execute(builder, enabled, self.from_state, self.to_state);
427    }
428}
429
430impl<T: FieldAlgebra> From<(u32, Option<T>)> for PcIncOrSet<T> {
431    fn from((pc_inc, to_pc): (u32, Option<T>)) -> Self {
432        match to_pc {
433            None => PcIncOrSet::Inc(T::from_canonical_u32(pc_inc)),
434            Some(to_pc) => PcIncOrSet::Set(to_pc),
435        }
436    }
437}
438
439/// Phantom sub-instructions affect the runtime of the VM and the trace matrix values.
440/// However they all have no AIR constraints besides advancing the pc by
441/// [DEFAULT_PC_STEP].
442///
443/// They should not mutate memory, but they can mutate the input & hint streams.
444///
445/// Phantom sub-instructions are only allowed to use operands
446/// `a,b` and `c_upper = c.as_canonical_u32() >> 16`.
447#[allow(clippy::too_many_arguments)]
448pub trait PhantomSubExecutor<F>: Send + Sync {
449    fn phantom_execute(
450        &self,
451        memory: &GuestMemory,
452        streams: &mut Streams<F>,
453        rng: &mut StdRng,
454        discriminant: PhantomDiscriminant,
455        a: u32,
456        b: u32,
457        c_upper: u16,
458    ) -> eyre::Result<()>;
459}
openvm_circuit/arch/execution.rs

openvm_circuit/arch/
execution.rs
