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

openvm_circuit/arch/
execution.rs
