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

openvm_circuit/arch/
execution.rs
