solar_codegen/backend/evm/
ir.rs

1//! EVM backend IR.
2//!
3//! This module defines the target-specific Machine-IR-like boundary between
4//! MIR lowering and final EVM assembly. EVM IR is intentionally untyped: values
5//! are EVM stack words, not Solidity or MIR values with a [`crate::mir::MirType`].
6//! It models backend basic blocks, opcode-like instructions, explicit physical
7//! stack operations, terminators, and metadata. The parser/printer at the bottom
8//! of the file provide a text format for tests and debugging; the IR itself is
9//! not defined by that serialization.
10
11use alloy_primitives::U256;
12use solar_data_structures::{fmt, index::IndexVec, newtype_index};
13
14mod display;
15mod parse;
16mod passes;
17mod verify;
18
19pub use parse::{EvmIrParseError, parse_evm_ir_module};
20pub use passes::{EVM_IR_PASSES, EvmIrPass};
21pub use verify::{EvmIrVerifyError, verify_evm_ir_module};
22
23newtype_index! {
24    /// A unique identifier for a basic block in EVM IR.
25    pub struct EvmIrBlockId;
26}
27
28newtype_index! {
29    /// A unique identifier for an untyped stack word in EVM IR.
30    pub struct EvmIrValueId;
31}
32
33/// An EVM IR module.
34#[derive(Clone, Debug, Default, PartialEq, Eq)]
35pub struct EvmIrModule {
36    /// Program name used by tools and diagnostics.
37    pub name: String,
38    /// Basic blocks in layout order.
39    pub blocks: IndexVec<EvmIrBlockId, EvmIrBlock>,
40    /// The entry block, if one has been created.
41    pub entry_block: Option<EvmIrBlockId>,
42    /// Untyped stack words known to this program.
43    pub values: IndexVec<EvmIrValueId, EvmIrValue>,
44}
45
46impl EvmIrModule {
47    /// Creates an empty EVM IR program.
48    #[must_use]
49    pub fn new(name: impl Into<String>) -> Self {
50        let name = name.into();
51        assert!(is_valid_ident(&name), "invalid EVM IR program name `{name}`");
52        Self { name, blocks: IndexVec::new(), entry_block: None, values: IndexVec::new() }
53    }
54
55    /// Adds a block to the program.
56    pub fn add_block(&mut self, block: EvmIrBlock) -> EvmIrBlockId {
57        let id = self.blocks.push(block);
58        if self.entry_block.is_none() {
59            self.entry_block = Some(id);
60        }
61        id
62    }
63
64    /// Allocates a named untyped stack word.
65    pub fn add_value(&mut self, name: impl Into<String>) -> EvmIrValueId {
66        let name = name.into();
67        assert!(is_valid_value_name(&name), "invalid EVM IR value name `%{name}`");
68        self.values.push(EvmIrValue { name })
69    }
70
71    /// Returns the block for the given ID.
72    #[must_use]
73    pub fn block(&self, id: EvmIrBlockId) -> &EvmIrBlock {
74        &self.blocks[id]
75    }
76
77    /// Returns a mutable reference to the block for the given ID.
78    pub fn block_mut(&mut self, id: EvmIrBlockId) -> &mut EvmIrBlock {
79        &mut self.blocks[id]
80    }
81
82    /// Returns the value for the given ID.
83    #[must_use]
84    pub fn value(&self, id: EvmIrValueId) -> &EvmIrValue {
85        &self.values[id]
86    }
87}
88
89/// A basic block in EVM IR.
90#[derive(Clone, Debug, PartialEq, Eq)]
91pub struct EvmIrBlock {
92    /// Stable textual label for this block.
93    pub label: String,
94    /// Block metadata. The hot/cold field is present before it is consumed by
95    /// layout or scheduling so fixtures can pin the format early.
96    pub metadata: EvmIrBlockMetadata,
97    /// Non-terminating EVM backend instructions.
98    pub instructions: Vec<EvmIrInstruction>,
99    /// Optional control-flow terminator.
100    pub terminator: Option<EvmIrTerminator>,
101    /// Values present on the stack at block entry, top first.
102    ///
103    /// This is the block's incoming stack-word signature: values produced by a
104    /// predecessor and consumed here. It is empty for the entry block and for
105    /// blocks that begin from a clean stack. Stack scheduling seeds its model
106    /// stack from this so blocks that consume predecessor values can be
107    /// scheduled instead of bailing.
108    pub entry_stack: Vec<EvmIrValueId>,
109}
110
111impl EvmIrBlock {
112    /// Creates an empty hot block.
113    #[must_use]
114    pub fn new(label: impl Into<String>) -> Self {
115        let label = label.into();
116        assert!(is_valid_block_label(&label), "invalid EVM IR block label `{label}`");
117        Self {
118            label,
119            metadata: EvmIrBlockMetadata::default(),
120            instructions: Vec::new(),
121            terminator: None,
122            entry_stack: Vec::new(),
123        }
124    }
125}
126
127/// Block-level metadata.
128#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
129pub struct EvmIrBlockMetadata {
130    /// Estimated block hotness for future layout and scheduling decisions.
131    pub hotness: EvmIrBlockHotness,
132}
133
134/// Block hotness metadata.
135#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
136pub enum EvmIrBlockHotness {
137    /// The block is expected to be frequently executed.
138    #[default]
139    Hot,
140    /// The block is expected to be infrequently executed.
141    Cold,
142}
143
144impl EvmIrBlockHotness {
145    fn parse(value: &str) -> Option<Self> {
146        Some(match value {
147            "hot" => Self::Hot,
148            "cold" => Self::Cold,
149            _ => return None,
150        })
151    }
152}
153
154/// A named untyped stack word.
155#[derive(Clone, Debug, PartialEq, Eq)]
156pub struct EvmIrValue {
157    /// Stable textual stack-word name, without the leading `%`.
158    pub name: String,
159}
160
161/// A non-terminating untyped backend instruction.
162#[derive(Clone, Debug, PartialEq, Eq)]
163pub struct EvmIrInstruction {
164    /// Optional stack word produced by this instruction.
165    pub result: Option<EvmIrValueId>,
166    /// EVM opcode, backend pseudo-op, or physical stack operation.
167    pub kind: EvmIrInstructionKind,
168    /// Instruction operands.
169    pub operands: Vec<EvmIrOperand>,
170    /// Instruction metadata.
171    pub metadata: EvmIrMetadata,
172}
173
174impl EvmIrInstruction {
175    /// Creates an instruction.
176    #[must_use]
177    pub fn new(mnemonic: impl Into<String>, operands: Vec<EvmIrOperand>) -> Self {
178        Self {
179            result: None,
180            kind: EvmIrInstructionKind::Operation(mnemonic.into()),
181            operands,
182            metadata: EvmIrMetadata::default(),
183        }
184    }
185
186    /// Creates a physical stack operation.
187    #[must_use]
188    pub fn stack_op(op: EvmIrStackOp) -> Self {
189        Self {
190            result: None,
191            kind: EvmIrInstructionKind::Stack(op),
192            operands: Vec::new(),
193            metadata: EvmIrMetadata::default(),
194        }
195    }
196
197    /// Returns the instruction mnemonic as printed in EVM IR.
198    #[must_use]
199    pub fn mnemonic(&self) -> impl fmt::Display + '_ {
200        fmt::from_fn(move |f| match &self.kind {
201            EvmIrInstructionKind::Operation(mnemonic) => write!(f, "{mnemonic}"),
202            EvmIrInstructionKind::Stack(op) => write!(f, "{}", op.mnemonic()),
203        })
204    }
205
206    /// Returns whether this instruction materializes a physical EVM stack op.
207    #[must_use]
208    pub const fn is_physical_stack_op(&self) -> bool {
209        matches!(self.kind, EvmIrInstructionKind::Stack(_))
210    }
211}
212
213/// A non-terminating EVM IR instruction kind.
214#[derive(Clone, Debug, PartialEq, Eq, Hash)]
215pub enum EvmIrInstructionKind {
216    /// Untyped EVM opcode or backend pseudo-op mnemonic.
217    Operation(String),
218    /// Materialized physical EVM stack operation.
219    Stack(EvmIrStackOp),
220}
221
222/// A materialized physical EVM stack operation.
223///
224/// These are modeled distinctly from generic operation mnemonics so stack
225/// scheduling can target EVM IR and later EVM IR passes can optimize the exact
226/// `DUP`/`SWAP`/`POP` sequence before final assembly.
227#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
228pub enum EvmIrStackOp {
229    /// EVM `DUP1` through `DUP16`.
230    Dup(u8),
231    /// EVM `SWAP1` through `SWAP16`.
232    Swap(u8),
233    /// EVM `POP`.
234    Pop,
235}
236
237impl EvmIrStackOp {
238    /// Creates a `DUP<N>` operation.
239    #[must_use]
240    pub const fn dup(n: u8) -> Option<Self> {
241        if n >= 1 && n <= 16 { Some(Self::Dup(n)) } else { None }
242    }
243
244    /// Creates a `SWAP<N>` operation.
245    #[must_use]
246    pub const fn swap(n: u8) -> Option<Self> {
247        if n >= 1 && n <= 16 { Some(Self::Swap(n)) } else { None }
248    }
249
250    /// Returns this operation's stack effect.
251    #[must_use]
252    pub const fn stack_effect(self) -> EvmIrStackEffect {
253        match self {
254            Self::Dup(_) => EvmIrStackEffect::new(0, 1),
255            Self::Swap(_) => EvmIrStackEffect::new(0, 0),
256            Self::Pop => EvmIrStackEffect::new(1, 0),
257        }
258    }
259
260    fn parse(mnemonic: &str) -> Option<Self> {
261        if mnemonic == "pop" {
262            return Some(Self::Pop);
263        }
264        if let Some(n) = mnemonic.strip_prefix("dup").and_then(|s| s.parse::<u8>().ok()) {
265            return Self::dup(n);
266        }
267        if let Some(n) = mnemonic.strip_prefix("swap").and_then(|s| s.parse::<u8>().ok()) {
268            return Self::swap(n);
269        }
270        None
271    }
272
273    fn mnemonic(self) -> impl fmt::Display {
274        fmt::from_fn(move |f| match self {
275            Self::Dup(n) => write!(f, "dup{n}"),
276            Self::Swap(n) => write!(f, "swap{n}"),
277            Self::Pop => write!(f, "pop"),
278        })
279    }
280}
281
282/// A control-flow terminator.
283#[derive(Clone, Debug, PartialEq, Eq)]
284pub struct EvmIrTerminator {
285    /// The terminator kind.
286    pub kind: EvmIrTerminatorKind,
287    /// Terminator metadata.
288    pub metadata: EvmIrMetadata,
289}
290
291impl EvmIrTerminator {
292    /// Creates a terminator without metadata.
293    #[must_use]
294    pub const fn new(kind: EvmIrTerminatorKind) -> Self {
295        Self { kind, metadata: EvmIrMetadata::EMPTY }
296    }
297}
298
299/// Control-flow terminators in EVM IR.
300#[derive(Clone, Debug, PartialEq, Eq)]
301pub enum EvmIrTerminatorKind {
302    /// Physical fallthrough into the next laid-out block.
303    Fallthrough(EvmIrBlockId),
304    /// Unconditional jump.
305    Jump(EvmIrBlockId),
306    /// Conditional branch.
307    Branch {
308        /// Branch condition.
309        condition: EvmIrOperand,
310        /// Target when condition is non-zero.
311        then_block: EvmIrBlockId,
312        /// Target when condition is zero.
313        else_block: EvmIrBlockId,
314    },
315    /// Multi-way branch.
316    Switch {
317        /// Discriminant value.
318        value: EvmIrOperand,
319        /// Default target.
320        default: EvmIrBlockId,
321        /// Case value and target pairs.
322        cases: Vec<(EvmIrOperand, EvmIrBlockId)>,
323    },
324    /// EVM `RETURN(offset, size)`.
325    Return {
326        /// Memory offset.
327        offset: EvmIrOperand,
328        /// Byte length.
329        size: EvmIrOperand,
330    },
331    /// EVM `REVERT(offset, size)`.
332    Revert {
333        /// Memory offset.
334        offset: EvmIrOperand,
335        /// Byte length.
336        size: EvmIrOperand,
337    },
338    /// EVM `STOP`.
339    Stop,
340    /// EVM `INVALID`.
341    Invalid,
342    /// EVM `SELFDESTRUCT(recipient)`.
343    SelfDestruct {
344        /// Beneficiary address.
345        recipient: EvmIrOperand,
346    },
347    /// Raw terminal opcode for already stack-scheduled machine-level code.
348    RawOpcode(u8),
349}
350
351/// An instruction or terminator operand.
352#[derive(Clone, Debug, PartialEq, Eq, Hash)]
353pub enum EvmIrOperand {
354    /// Untyped stack-word reference.
355    Value(EvmIrValueId),
356    /// Immediate EVM word.
357    Immediate(U256),
358    /// Basic block reference.
359    Block(EvmIrBlockId),
360    /// Opaque backend symbol, such as a helper, data object, or future label kind.
361    Symbol(String),
362}
363
364/// Generic metadata carried by instructions and terminators.
365#[derive(Clone, Debug, Default, PartialEq, Eq)]
366pub struct EvmIrMetadata {
367    /// Optional stack effect.
368    pub stack: Option<EvmIrStackEffect>,
369    /// Extra key-value metadata fields, in textual order.
370    pub attrs: Vec<EvmIrMetadataItem>,
371}
372
373impl EvmIrMetadata {
374    /// Empty metadata value.
375    pub const EMPTY: Self = Self { stack: None, attrs: Vec::new() };
376
377    /// Returns whether no metadata fields are present.
378    #[must_use]
379    pub fn is_empty(&self) -> bool {
380        self.stack.is_none() && self.attrs.is_empty()
381    }
382}
383
384/// A metadata key-value item.
385#[derive(Clone, Debug, PartialEq, Eq)]
386pub struct EvmIrMetadataItem {
387    /// Metadata key.
388    pub key: String,
389    /// Metadata value, if the field is not a marker.
390    pub value: Option<String>,
391}
392
393/// Stack effect metadata for one EVM IR operation.
394#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
395pub struct EvmIrStackEffect {
396    /// Number of stack items consumed.
397    pub inputs: u16,
398    /// Number of stack items produced.
399    pub outputs: u16,
400}
401
402impl EvmIrStackEffect {
403    /// Creates a stack effect descriptor.
404    #[must_use]
405    pub const fn new(inputs: u16, outputs: u16) -> Self {
406        Self { inputs, outputs }
407    }
408}
409
410pub(super) fn default_instruction_stack_effect(inst: &EvmIrInstruction) -> EvmIrStackEffect {
411    match &inst.kind {
412        EvmIrInstructionKind::Stack(op) => op.stack_effect(),
413        EvmIrInstructionKind::Operation(_) if is_encoded_push_instruction(inst) => {
414            EvmIrStackEffect::new(0, 1)
415        }
416        EvmIrInstructionKind::Operation(_) => EvmIrStackEffect::new(
417            inst.operands.len().try_into().unwrap_or(u16::MAX),
418            u16::from(inst.result.is_some()),
419        ),
420    }
421}
422
423fn default_terminator_stack_effect(kind: &EvmIrTerminatorKind) -> EvmIrStackEffect {
424    match kind {
425        EvmIrTerminatorKind::Branch { .. } => EvmIrStackEffect::new(1, 0),
426        EvmIrTerminatorKind::Switch { .. } => EvmIrStackEffect::new(1, 0),
427        EvmIrTerminatorKind::Return { .. } | EvmIrTerminatorKind::Revert { .. } => {
428            EvmIrStackEffect::new(2, 0)
429        }
430        EvmIrTerminatorKind::SelfDestruct { .. } => EvmIrStackEffect::new(1, 0),
431        EvmIrTerminatorKind::Fallthrough(_)
432        | EvmIrTerminatorKind::Jump(_)
433        | EvmIrTerminatorKind::Stop
434        | EvmIrTerminatorKind::Invalid
435        | EvmIrTerminatorKind::RawOpcode(_) => EvmIrStackEffect::new(0, 0),
436    }
437}
438
439pub(super) fn is_encoded_push_instruction(inst: &EvmIrInstruction) -> bool {
440    matches!(
441        &inst.kind,
442        EvmIrInstructionKind::Operation(mnemonic)
443            if matches!(mnemonic.as_str(), "push" | "push_deferred" | "push_immutable")
444    )
445}
446
447fn is_ident_start(c: char) -> bool {
448    c.is_ascii_alphabetic() || c == '_' || c == '$' || c == '.'
449}
450
451fn is_ident_continue(c: char) -> bool {
452    is_ident_start(c) || c.is_ascii_digit()
453}
454
455fn is_valid_ident(name: &str) -> bool {
456    let mut chars = name.chars();
457    matches!(chars.next(), Some(c) if is_ident_start(c)) && chars.all(is_ident_continue)
458}
459
460fn is_valid_value_name(name: &str) -> bool {
461    let mut chars = name.chars();
462    matches!(chars.next(), Some(c) if is_ident_start(c) || c.is_ascii_digit())
463        && chars.all(is_ident_continue)
464}
465
466fn is_valid_block_label(label: &str) -> bool {
467    let Some(digits) = label.strip_prefix("bb") else {
468        return false;
469    };
470    !digits.is_empty() && digits.bytes().all(|b| b.is_ascii_digit())
471}
solar_codegen/backend/evm/ir.rs

solar_codegen/backend/evm/
ir.rs
