openvm_circuit/arch/
execution.rs

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

openvm_circuit/arch/
execution.rs
