openvm_circuit/arch/
execution.rs

Help
1use std::{cell::RefCell, rc::Rc};
2
3use openvm_circuit_primitives_derive::AlignedBorrow;
4use openvm_instructions::{
5    instruction::Instruction, program::DEFAULT_PC_STEP, PhantomDiscriminant, VmOpcode,
6};
7use openvm_stark_backend::{
8    interaction::{BusIndex, InteractionBuilder, PermutationCheckBus},
9    p3_field::FieldAlgebra,
10};
11use serde::{Deserialize, Serialize};
12use thiserror::Error;
13
14use super::Streams;
15use crate::system::{memory::MemoryController, program::ProgramBus};
16
17pub type Result<T> = std::result::Result<T, ExecutionError>;
18
19#[derive(Error, Debug)]
20pub enum ExecutionError {
21    #[error("execution failed at pc {pc}")]
22    Fail { pc: u32 },
23    #[error("pc {pc} not found for program of length {program_len}, with pc_base {pc_base} and step = {step}")]
24    PcNotFound {
25        pc: u32,
26        step: u32,
27        pc_base: u32,
28        program_len: usize,
29    },
30    #[error("pc {pc} out of bounds for program of length {program_len}, with pc_base {pc_base} and step = {step}")]
31    PcOutOfBounds {
32        pc: u32,
33        step: u32,
34        pc_base: u32,
35        program_len: usize,
36    },
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}
70
71pub trait InstructionExecutor<F> {
72    /// Runtime execution of the instruction, if the instruction is owned by the
73    /// current instance. May internally store records of this call for later trace generation.
74    fn execute(
75        &mut self,
76        memory: &mut MemoryController<F>,
77        instruction: &Instruction<F>,
78        from_state: ExecutionState<u32>,
79    ) -> Result<ExecutionState<u32>>;
80
81    /// For display purposes. From absolute opcode as `usize`, return the string name of the opcode
82    /// if it is a supported opcode by the present executor.
83    fn get_opcode_name(&self, opcode: usize) -> String;
84}
85
86impl<F, C: InstructionExecutor<F>> InstructionExecutor<F> for RefCell<C> {
87    fn execute(
88        &mut self,
89        memory: &mut MemoryController<F>,
90        instruction: &Instruction<F>,
91        prev_state: ExecutionState<u32>,
92    ) -> Result<ExecutionState<u32>> {
93        self.borrow_mut().execute(memory, instruction, prev_state)
94    }
95
96    fn get_opcode_name(&self, opcode: usize) -> String {
97        self.borrow().get_opcode_name(opcode)
98    }
99}
100
101impl<F, C: InstructionExecutor<F>> InstructionExecutor<F> for Rc<RefCell<C>> {
102    fn execute(
103        &mut self,
104        memory: &mut MemoryController<F>,
105        instruction: &Instruction<F>,
106        prev_state: ExecutionState<u32>,
107    ) -> Result<ExecutionState<u32>> {
108        self.borrow_mut().execute(memory, instruction, prev_state)
109    }
110
111    fn get_opcode_name(&self, opcode: usize) -> String {
112        self.borrow().get_opcode_name(opcode)
113    }
114}
115
116#[repr(C)]
117#[derive(Clone, Copy, Debug, PartialEq, Default, AlignedBorrow, Serialize, Deserialize)]
118pub struct ExecutionState<T> {
119    pub pc: T,
120    pub timestamp: T,
121}
122
123#[derive(Clone, Copy, Debug)]
124pub struct ExecutionBus {
125    pub inner: PermutationCheckBus,
126}
127
128impl ExecutionBus {
129    pub const fn new(index: BusIndex) -> Self {
130        Self {
131            inner: PermutationCheckBus::new(index),
132        }
133    }
134
135    #[inline(always)]
136    pub fn index(&self) -> BusIndex {
137        self.inner.index
138    }
139}
140
141#[derive(Copy, Clone, Debug)]
142pub struct ExecutionBridge {
143    execution_bus: ExecutionBus,
144    program_bus: ProgramBus,
145}
146
147pub struct ExecutionBridgeInteractor<AB: InteractionBuilder> {
148    execution_bus: ExecutionBus,
149    program_bus: ProgramBus,
150    opcode: AB::Expr,
151    operands: Vec<AB::Expr>,
152    from_state: ExecutionState<AB::Expr>,
153    to_state: ExecutionState<AB::Expr>,
154}
155
156pub enum PcIncOrSet<T> {
157    Inc(T),
158    Set(T),
159}
160
161impl<T> ExecutionState<T> {
162    pub fn new(pc: impl Into<T>, timestamp: impl Into<T>) -> Self {
163        Self {
164            pc: pc.into(),
165            timestamp: timestamp.into(),
166        }
167    }
168
169    #[allow(clippy::should_implement_trait)]
170    pub fn from_iter<I: Iterator<Item = T>>(iter: &mut I) -> Self {
171        let mut next = || iter.next().unwrap();
172        Self {
173            pc: next(),
174            timestamp: next(),
175        }
176    }
177
178    pub fn flatten(self) -> [T; 2] {
179        [self.pc, self.timestamp]
180    }
181
182    pub fn get_width() -> usize {
183        2
184    }
185
186    pub fn map<U: Clone, F: Fn(T) -> U>(self, function: F) -> ExecutionState<U> {
187        ExecutionState::from_iter(&mut self.flatten().map(function).into_iter())
188    }
189}
190
191impl ExecutionBus {
192    /// Caller must constrain that `enabled` is boolean.
193    pub fn execute_and_increment_pc<AB: InteractionBuilder>(
194        &self,
195        builder: &mut AB,
196        enabled: impl Into<AB::Expr>,
197        prev_state: ExecutionState<AB::Expr>,
198        timestamp_change: impl Into<AB::Expr>,
199    ) {
200        let next_state = ExecutionState {
201            pc: prev_state.pc.clone() + AB::F::ONE,
202            timestamp: prev_state.timestamp.clone() + timestamp_change.into(),
203        };
204        self.execute(builder, enabled, prev_state, next_state);
205    }
206
207    /// Caller must constrain that `enabled` is boolean.
208    pub fn execute<AB: InteractionBuilder>(
209        &self,
210        builder: &mut AB,
211        enabled: impl Into<AB::Expr>,
212        prev_state: ExecutionState<impl Into<AB::Expr>>,
213        next_state: ExecutionState<impl Into<AB::Expr>>,
214    ) {
215        let enabled = enabled.into();
216        self.inner.receive(
217            builder,
218            [prev_state.pc.into(), prev_state.timestamp.into()],
219            enabled.clone(),
220        );
221        self.inner.send(
222            builder,
223            [next_state.pc.into(), next_state.timestamp.into()],
224            enabled,
225        );
226    }
227}
228
229impl ExecutionBridge {
230    pub fn new(execution_bus: ExecutionBus, program_bus: ProgramBus) -> Self {
231        Self {
232            execution_bus,
233            program_bus,
234        }
235    }
236
237    /// If `to_pc` is `Some`, then `pc_inc` is ignored and the `to_state` uses `to_pc`. Otherwise `to_pc = from_pc + pc_inc`.
238    pub fn execute_and_increment_or_set_pc<AB: InteractionBuilder>(
239        &self,
240        opcode: impl Into<AB::Expr>,
241        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
242        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
243        timestamp_change: impl Into<AB::Expr>,
244        pc_kind: impl Into<PcIncOrSet<AB::Expr>>,
245    ) -> ExecutionBridgeInteractor<AB> {
246        let to_state = ExecutionState {
247            pc: match pc_kind.into() {
248                PcIncOrSet::Set(to_pc) => to_pc,
249                PcIncOrSet::Inc(pc_inc) => from_state.pc.clone().into() + pc_inc,
250            },
251            timestamp: from_state.timestamp.clone().into() + timestamp_change.into(),
252        };
253        self.execute(opcode, operands, from_state, to_state)
254    }
255
256    pub fn execute_and_increment_pc<AB: InteractionBuilder>(
257        &self,
258        opcode: impl Into<AB::Expr>,
259        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
260        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
261        timestamp_change: impl Into<AB::Expr>,
262    ) -> ExecutionBridgeInteractor<AB> {
263        let to_state = ExecutionState {
264            pc: from_state.pc.clone().into() + AB::Expr::from_canonical_u32(DEFAULT_PC_STEP),
265            timestamp: from_state.timestamp.clone().into() + timestamp_change.into(),
266        };
267        self.execute(opcode, operands, from_state, to_state)
268    }
269
270    pub fn execute<AB: InteractionBuilder>(
271        &self,
272        opcode: impl Into<AB::Expr>,
273        operands: impl IntoIterator<Item = impl Into<AB::Expr>>,
274        from_state: ExecutionState<impl Into<AB::Expr> + Clone>,
275        to_state: ExecutionState<impl Into<AB::Expr>>,
276    ) -> ExecutionBridgeInteractor<AB> {
277        ExecutionBridgeInteractor {
278            execution_bus: self.execution_bus,
279            program_bus: self.program_bus,
280            opcode: opcode.into(),
281            operands: operands.into_iter().map(Into::into).collect(),
282            from_state: from_state.map(Into::into),
283            to_state: to_state.map(Into::into),
284        }
285    }
286}
287
288impl<AB: InteractionBuilder> ExecutionBridgeInteractor<AB> {
289    /// Caller must constrain that `enabled` is boolean.
290    pub fn eval(self, builder: &mut AB, enabled: impl Into<AB::Expr>) {
291        let enabled = enabled.into();
292
293        // Interaction with program
294        self.program_bus.lookup_instruction(
295            builder,
296            self.from_state.pc.clone(),
297            self.opcode,
298            self.operands,
299            enabled.clone(),
300        );
301
302        self.execution_bus
303            .execute(builder, enabled, self.from_state, self.to_state);
304    }
305}
306
307impl<T: FieldAlgebra> From<(u32, Option<T>)> for PcIncOrSet<T> {
308    fn from((pc_inc, to_pc): (u32, Option<T>)) -> Self {
309        match to_pc {
310            None => PcIncOrSet::Inc(T::from_canonical_u32(pc_inc)),
311            Some(to_pc) => PcIncOrSet::Set(to_pc),
312        }
313    }
314}
315
316/// Phantom sub-instructions affect the runtime of the VM and the trace matrix values.
317/// However they all have no AIR constraints besides advancing the pc by [DEFAULT_PC_STEP](openvm_instructions::program::DEFAULT_PC_STEP).
318///
319/// They should not mutate memory, but they can mutate the input & hint streams.
320///
321/// Phantom sub-instructions are only allowed to use operands
322/// `a,b` and `c_upper = c.as_canonical_u32() >> 16`.
323pub trait PhantomSubExecutor<F>: Send {
324    fn phantom_execute(
325        &mut self,
326        memory: &MemoryController<F>,
327        streams: &mut Streams<F>,
328        discriminant: PhantomDiscriminant,
329        a: F,
330        b: F,
331        c_upper: u16,
332    ) -> eyre::Result<()>;
333}
openvm_circuit/arch/execution.rs

openvm_circuit/arch/
execution.rs
