fe_mir/ir/
inst.rs

1use std::fmt;
2
3use fe_analyzer::namespace::items::ContractId;
4use id_arena::Id;
5
6use super::{basic_block::BasicBlockId, function::FunctionId, value::ValueId, SourceInfo, TypeId};
7
8pub type InstId = Id<Inst>;
9
10#[derive(Debug, Clone, PartialEq, Eq, Hash)]
11pub struct Inst {
12    pub kind: InstKind,
13    pub source: SourceInfo,
14}
15
16#[derive(Debug, Clone, PartialEq, Eq, Hash)]
17pub enum InstKind {
18    /// This is not a real instruction, just used to tag a position where a
19    /// local is declared.
20    Declare {
21        local: ValueId,
22    },
23
24    /// Unary instruction.
25    Unary {
26        op: UnOp,
27        value: ValueId,
28    },
29
30    /// Binary instruction.
31    Binary {
32        op: BinOp,
33        lhs: ValueId,
34        rhs: ValueId,
35    },
36
37    Cast {
38        kind: CastKind,
39        value: ValueId,
40        to: TypeId,
41    },
42
43    /// Constructs aggregate value, i.e. struct, tuple and array.
44    AggregateConstruct {
45        ty: TypeId,
46        args: Vec<ValueId>,
47    },
48
49    Bind {
50        src: ValueId,
51    },
52
53    MemCopy {
54        src: ValueId,
55    },
56
57    /// Load a primitive value from a ptr
58    Load {
59        src: ValueId,
60    },
61
62    /// Access to aggregate fields or elements.
63    /// # Example
64    ///
65    /// ```fe
66    /// struct Foo:
67    ///     x: i32
68    ///     y: Array<i32, 8>
69    /// ```
70    /// `foo.y` is lowered into `AggregateAccess(foo, [1])' for example.
71    AggregateAccess {
72        value: ValueId,
73        indices: Vec<ValueId>,
74    },
75
76    MapAccess {
77        key: ValueId,
78        value: ValueId,
79    },
80
81    Call {
82        func: FunctionId,
83        args: Vec<ValueId>,
84        call_type: CallType,
85    },
86
87    /// Unconditional jump instruction.
88    Jump {
89        dest: BasicBlockId,
90    },
91
92    /// Conditional branching instruction.
93    Branch {
94        cond: ValueId,
95        then: BasicBlockId,
96        else_: BasicBlockId,
97    },
98
99    Switch {
100        disc: ValueId,
101        table: SwitchTable,
102        default: Option<BasicBlockId>,
103    },
104
105    Revert {
106        arg: Option<ValueId>,
107    },
108
109    Emit {
110        arg: ValueId,
111    },
112
113    Return {
114        arg: Option<ValueId>,
115    },
116
117    Keccak256 {
118        arg: ValueId,
119    },
120
121    AbiEncode {
122        arg: ValueId,
123    },
124
125    Nop,
126
127    Create {
128        value: ValueId,
129        contract: ContractId,
130    },
131
132    Create2 {
133        value: ValueId,
134        salt: ValueId,
135        contract: ContractId,
136    },
137
138    YulIntrinsic {
139        op: YulIntrinsicOp,
140        args: Vec<ValueId>,
141    },
142}
143
144#[derive(Debug, Clone, Default, PartialEq, Eq, Hash)]
145pub struct SwitchTable {
146    values: Vec<ValueId>,
147    blocks: Vec<BasicBlockId>,
148}
149
150impl SwitchTable {
151    pub fn iter(&self) -> impl Iterator<Item = (ValueId, BasicBlockId)> + '_ {
152        self.values.iter().copied().zip(self.blocks.iter().copied())
153    }
154
155    pub fn len(&self) -> usize {
156        debug_assert!(self.values.len() == self.blocks.len());
157        self.values.len()
158    }
159
160    pub fn is_empty(&self) -> bool {
161        debug_assert!(self.values.len() == self.blocks.len());
162        self.values.is_empty()
163    }
164
165    pub fn add_arm(&mut self, value: ValueId, block: BasicBlockId) {
166        self.values.push(value);
167        self.blocks.push(block);
168    }
169}
170
171impl Inst {
172    pub fn new(kind: InstKind, source: SourceInfo) -> Self {
173        Self { kind, source }
174    }
175
176    pub fn unary(op: UnOp, value: ValueId, source: SourceInfo) -> Self {
177        let kind = InstKind::Unary { op, value };
178        Self::new(kind, source)
179    }
180
181    pub fn binary(op: BinOp, lhs: ValueId, rhs: ValueId, source: SourceInfo) -> Self {
182        let kind = InstKind::Binary { op, lhs, rhs };
183        Self::new(kind, source)
184    }
185
186    pub fn intrinsic(op: YulIntrinsicOp, args: Vec<ValueId>, source: SourceInfo) -> Self {
187        let kind = InstKind::YulIntrinsic { op, args };
188        Self::new(kind, source)
189    }
190
191    pub fn nop() -> Self {
192        Self {
193            kind: InstKind::Nop,
194            source: SourceInfo::dummy(),
195        }
196    }
197
198    pub fn is_terminator(&self) -> bool {
199        match self.kind {
200            InstKind::Jump { .. }
201            | InstKind::Branch { .. }
202            | InstKind::Switch { .. }
203            | InstKind::Revert { .. }
204            | InstKind::Return { .. } => true,
205            InstKind::YulIntrinsic { op, .. } => op.is_terminator(),
206            _ => false,
207        }
208    }
209
210    pub fn branch_info(&self) -> BranchInfo {
211        match self.kind {
212            InstKind::Jump { dest } => BranchInfo::Jump(dest),
213            InstKind::Branch { cond, then, else_ } => BranchInfo::Branch(cond, then, else_),
214            InstKind::Switch {
215                disc,
216                ref table,
217                default,
218            } => BranchInfo::Switch(disc, table, default),
219            _ => BranchInfo::NotBranch,
220        }
221    }
222
223    pub fn args(&self) -> ValueIter {
224        use InstKind::*;
225        match &self.kind {
226            Declare { local: arg }
227            | Bind { src: arg }
228            | MemCopy { src: arg }
229            | Load { src: arg }
230            | Unary { value: arg, .. }
231            | Cast { value: arg, .. }
232            | Emit { arg }
233            | Keccak256 { arg }
234            | AbiEncode { arg }
235            | Create { value: arg, .. }
236            | Branch { cond: arg, .. } => ValueIter::one(*arg),
237
238            Switch { disc, table, .. } => {
239                ValueIter::one(*disc).chain(ValueIter::Slice(table.values.iter()))
240            }
241
242            Binary { lhs, rhs, .. }
243            | MapAccess {
244                value: lhs,
245                key: rhs,
246            }
247            | Create2 {
248                value: lhs,
249                salt: rhs,
250                ..
251            } => ValueIter::one(*lhs).chain(ValueIter::one(*rhs)),
252
253            Revert { arg } | Return { arg } => ValueIter::One(*arg),
254
255            Nop | Jump { .. } => ValueIter::Zero,
256
257            AggregateAccess { value, indices } => {
258                ValueIter::one(*value).chain(ValueIter::Slice(indices.iter()))
259            }
260
261            AggregateConstruct { args, .. } | Call { args, .. } | YulIntrinsic { args, .. } => {
262                ValueIter::Slice(args.iter())
263            }
264        }
265    }
266
267    pub fn args_mut(&mut self) -> ValueIterMut {
268        use InstKind::*;
269        match &mut self.kind {
270            Declare { local: arg }
271            | Bind { src: arg }
272            | MemCopy { src: arg }
273            | Load { src: arg }
274            | Unary { value: arg, .. }
275            | Cast { value: arg, .. }
276            | Emit { arg }
277            | Keccak256 { arg }
278            | AbiEncode { arg }
279            | Create { value: arg, .. }
280            | Branch { cond: arg, .. } => ValueIterMut::one(arg),
281
282            Switch { disc, table, .. } => {
283                ValueIterMut::one(disc).chain(ValueIterMut::Slice(table.values.iter_mut()))
284            }
285
286            Binary { lhs, rhs, .. }
287            | MapAccess {
288                value: lhs,
289                key: rhs,
290            }
291            | Create2 {
292                value: lhs,
293                salt: rhs,
294                ..
295            } => ValueIterMut::one(lhs).chain(ValueIterMut::one(rhs)),
296
297            Revert { arg } | Return { arg } => ValueIterMut::One(arg.as_mut()),
298
299            Nop | Jump { .. } => ValueIterMut::Zero,
300
301            AggregateAccess { value, indices } => {
302                ValueIterMut::one(value).chain(ValueIterMut::Slice(indices.iter_mut()))
303            }
304
305            AggregateConstruct { args, .. } | Call { args, .. } | YulIntrinsic { args, .. } => {
306                ValueIterMut::Slice(args.iter_mut())
307            }
308        }
309    }
310}
311
312#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
313pub enum UnOp {
314    /// `not` operator for logical inversion.
315    Not,
316    /// `-` operator for negation.
317    Neg,
318    /// `~` operator for bitwise inversion.
319    Inv,
320}
321
322impl fmt::Display for UnOp {
323    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
324        match self {
325            Self::Not => write!(w, "not"),
326            Self::Neg => write!(w, "-"),
327            Self::Inv => write!(w, "~"),
328        }
329    }
330}
331
332#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
333pub enum BinOp {
334    Add,
335    Sub,
336    Mul,
337    Div,
338    Mod,
339    Pow,
340    Shl,
341    Shr,
342    BitOr,
343    BitXor,
344    BitAnd,
345    LogicalAnd,
346    LogicalOr,
347    Eq,
348    Ne,
349    Ge,
350    Gt,
351    Le,
352    Lt,
353}
354
355impl fmt::Display for BinOp {
356    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
357        match self {
358            Self::Add => write!(w, "+"),
359            Self::Sub => write!(w, "-"),
360            Self::Mul => write!(w, "*"),
361            Self::Div => write!(w, "/"),
362            Self::Mod => write!(w, "%"),
363            Self::Pow => write!(w, "**"),
364            Self::Shl => write!(w, "<<"),
365            Self::Shr => write!(w, ">>"),
366            Self::BitOr => write!(w, "|"),
367            Self::BitXor => write!(w, "^"),
368            Self::BitAnd => write!(w, "&"),
369            Self::LogicalAnd => write!(w, "and"),
370            Self::LogicalOr => write!(w, "or"),
371            Self::Eq => write!(w, "=="),
372            Self::Ne => write!(w, "!="),
373            Self::Ge => write!(w, ">="),
374            Self::Gt => write!(w, ">"),
375            Self::Le => write!(w, "<="),
376            Self::Lt => write!(w, "<"),
377        }
378    }
379}
380
381#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
382pub enum CallType {
383    Internal,
384    External,
385}
386
387impl fmt::Display for CallType {
388    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
389        match self {
390            Self::Internal => write!(w, "internal"),
391            Self::External => write!(w, "external"),
392        }
393    }
394}
395
396#[derive(Debug, Clone, PartialEq, Eq, Hash)]
397pub enum CastKind {
398    /// A cast from a primitive type to a primitive type.
399    Primitive,
400
401    /// A cast from an enum type to its underlying type.
402    Untag,
403}
404
405// TODO: We don't need all yul intrinsics.
406#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
407pub enum YulIntrinsicOp {
408    Stop,
409    Add,
410    Sub,
411    Mul,
412    Div,
413    Sdiv,
414    Mod,
415    Smod,
416    Exp,
417    Not,
418    Lt,
419    Gt,
420    Slt,
421    Sgt,
422    Eq,
423    Iszero,
424    And,
425    Or,
426    Xor,
427    Byte,
428    Shl,
429    Shr,
430    Sar,
431    Addmod,
432    Mulmod,
433    Signextend,
434    Keccak256,
435    Pc,
436    Pop,
437    Mload,
438    Mstore,
439    Mstore8,
440    Sload,
441    Sstore,
442    Msize,
443    Gas,
444    Address,
445    Balance,
446    Selfbalance,
447    Caller,
448    Callvalue,
449    Calldataload,
450    Calldatasize,
451    Calldatacopy,
452    Codesize,
453    Codecopy,
454    Extcodesize,
455    Extcodecopy,
456    Returndatasize,
457    Returndatacopy,
458    Extcodehash,
459    Create,
460    Create2,
461    Call,
462    Callcode,
463    Delegatecall,
464    Staticcall,
465    Return,
466    Revert,
467    Selfdestruct,
468    Invalid,
469    Log0,
470    Log1,
471    Log2,
472    Log3,
473    Log4,
474    Chainid,
475    Basefee,
476    Origin,
477    Gasprice,
478    Blockhash,
479    Coinbase,
480    Timestamp,
481    Number,
482    Prevrandao,
483    Gaslimit,
484}
485impl YulIntrinsicOp {
486    pub fn is_terminator(self) -> bool {
487        matches!(
488            self,
489            Self::Return | Self::Revert | Self::Selfdestruct | Self::Invalid
490        )
491    }
492}
493
494impl fmt::Display for YulIntrinsicOp {
495    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
496        let op = match self {
497            Self::Stop => "__stop",
498            Self::Add => "__add",
499            Self::Sub => "__sub",
500            Self::Mul => "__mul",
501            Self::Div => "__div",
502            Self::Sdiv => "__sdiv",
503            Self::Mod => "__mod",
504            Self::Smod => "__smod",
505            Self::Exp => "__exp",
506            Self::Not => "__not",
507            Self::Lt => "__lt",
508            Self::Gt => "__gt",
509            Self::Slt => "__slt",
510            Self::Sgt => "__sgt",
511            Self::Eq => "__eq",
512            Self::Iszero => "__iszero",
513            Self::And => "__and",
514            Self::Or => "__or",
515            Self::Xor => "__xor",
516            Self::Byte => "__byte",
517            Self::Shl => "__shl",
518            Self::Shr => "__shr",
519            Self::Sar => "__sar",
520            Self::Addmod => "__addmod",
521            Self::Mulmod => "__mulmod",
522            Self::Signextend => "__signextend",
523            Self::Keccak256 => "__keccak256",
524            Self::Pc => "__pc",
525            Self::Pop => "__pop",
526            Self::Mload => "__mload",
527            Self::Mstore => "__mstore",
528            Self::Mstore8 => "__mstore8",
529            Self::Sload => "__sload",
530            Self::Sstore => "__sstore",
531            Self::Msize => "__msize",
532            Self::Gas => "__gas",
533            Self::Address => "__address",
534            Self::Balance => "__balance",
535            Self::Selfbalance => "__selfbalance",
536            Self::Caller => "__caller",
537            Self::Callvalue => "__callvalue",
538            Self::Calldataload => "__calldataload",
539            Self::Calldatasize => "__calldatasize",
540            Self::Calldatacopy => "__calldatacopy",
541            Self::Codesize => "__codesize",
542            Self::Codecopy => "__codecopy",
543            Self::Extcodesize => "__extcodesize",
544            Self::Extcodecopy => "__extcodecopy",
545            Self::Returndatasize => "__returndatasize",
546            Self::Returndatacopy => "__returndatacopy",
547            Self::Extcodehash => "__extcodehash",
548            Self::Create => "__create",
549            Self::Create2 => "__create2",
550            Self::Call => "__call",
551            Self::Callcode => "__callcode",
552            Self::Delegatecall => "__delegatecall",
553            Self::Staticcall => "__staticcall",
554            Self::Return => "__return",
555            Self::Revert => "__revert",
556            Self::Selfdestruct => "__selfdestruct",
557            Self::Invalid => "__invalid",
558            Self::Log0 => "__log0",
559            Self::Log1 => "__log1",
560            Self::Log2 => "__log2",
561            Self::Log3 => "__log3",
562            Self::Log4 => "__log4",
563            Self::Chainid => "__chainid",
564            Self::Basefee => "__basefee",
565            Self::Origin => "__origin",
566            Self::Gasprice => "__gasprice",
567            Self::Blockhash => "__blockhash",
568            Self::Coinbase => "__coinbase",
569            Self::Timestamp => "__timestamp",
570            Self::Number => "__number",
571            Self::Prevrandao => "__prevrandao",
572            Self::Gaslimit => "__gaslimit",
573        };
574
575        write!(w, "{op}")
576    }
577}
578
579impl From<fe_analyzer::builtins::Intrinsic> for YulIntrinsicOp {
580    fn from(val: fe_analyzer::builtins::Intrinsic) -> Self {
581        use fe_analyzer::builtins::Intrinsic;
582        match val {
583            Intrinsic::__stop => Self::Stop,
584            Intrinsic::__add => Self::Add,
585            Intrinsic::__sub => Self::Sub,
586            Intrinsic::__mul => Self::Mul,
587            Intrinsic::__div => Self::Div,
588            Intrinsic::__sdiv => Self::Sdiv,
589            Intrinsic::__mod => Self::Mod,
590            Intrinsic::__smod => Self::Smod,
591            Intrinsic::__exp => Self::Exp,
592            Intrinsic::__not => Self::Not,
593            Intrinsic::__lt => Self::Lt,
594            Intrinsic::__gt => Self::Gt,
595            Intrinsic::__slt => Self::Slt,
596            Intrinsic::__sgt => Self::Sgt,
597            Intrinsic::__eq => Self::Eq,
598            Intrinsic::__iszero => Self::Iszero,
599            Intrinsic::__and => Self::And,
600            Intrinsic::__or => Self::Or,
601            Intrinsic::__xor => Self::Xor,
602            Intrinsic::__byte => Self::Byte,
603            Intrinsic::__shl => Self::Shl,
604            Intrinsic::__shr => Self::Shr,
605            Intrinsic::__sar => Self::Sar,
606            Intrinsic::__addmod => Self::Addmod,
607            Intrinsic::__mulmod => Self::Mulmod,
608            Intrinsic::__signextend => Self::Signextend,
609            Intrinsic::__keccak256 => Self::Keccak256,
610            Intrinsic::__pc => Self::Pc,
611            Intrinsic::__pop => Self::Pop,
612            Intrinsic::__mload => Self::Mload,
613            Intrinsic::__mstore => Self::Mstore,
614            Intrinsic::__mstore8 => Self::Mstore8,
615            Intrinsic::__sload => Self::Sload,
616            Intrinsic::__sstore => Self::Sstore,
617            Intrinsic::__msize => Self::Msize,
618            Intrinsic::__gas => Self::Gas,
619            Intrinsic::__address => Self::Address,
620            Intrinsic::__balance => Self::Balance,
621            Intrinsic::__selfbalance => Self::Selfbalance,
622            Intrinsic::__caller => Self::Caller,
623            Intrinsic::__callvalue => Self::Callvalue,
624            Intrinsic::__calldataload => Self::Calldataload,
625            Intrinsic::__calldatasize => Self::Calldatasize,
626            Intrinsic::__calldatacopy => Self::Calldatacopy,
627            Intrinsic::__codesize => Self::Codesize,
628            Intrinsic::__codecopy => Self::Codecopy,
629            Intrinsic::__extcodesize => Self::Extcodesize,
630            Intrinsic::__extcodecopy => Self::Extcodecopy,
631            Intrinsic::__returndatasize => Self::Returndatasize,
632            Intrinsic::__returndatacopy => Self::Returndatacopy,
633            Intrinsic::__extcodehash => Self::Extcodehash,
634            Intrinsic::__create => Self::Create,
635            Intrinsic::__create2 => Self::Create2,
636            Intrinsic::__call => Self::Call,
637            Intrinsic::__callcode => Self::Callcode,
638            Intrinsic::__delegatecall => Self::Delegatecall,
639            Intrinsic::__staticcall => Self::Staticcall,
640            Intrinsic::__return => Self::Return,
641            Intrinsic::__revert => Self::Revert,
642            Intrinsic::__selfdestruct => Self::Selfdestruct,
643            Intrinsic::__invalid => Self::Invalid,
644            Intrinsic::__log0 => Self::Log0,
645            Intrinsic::__log1 => Self::Log1,
646            Intrinsic::__log2 => Self::Log2,
647            Intrinsic::__log3 => Self::Log3,
648            Intrinsic::__log4 => Self::Log4,
649            Intrinsic::__chainid => Self::Chainid,
650            Intrinsic::__basefee => Self::Basefee,
651            Intrinsic::__origin => Self::Origin,
652            Intrinsic::__gasprice => Self::Gasprice,
653            Intrinsic::__blockhash => Self::Blockhash,
654            Intrinsic::__coinbase => Self::Coinbase,
655            Intrinsic::__timestamp => Self::Timestamp,
656            Intrinsic::__number => Self::Number,
657            Intrinsic::__prevrandao => Self::Prevrandao,
658            Intrinsic::__gaslimit => Self::Gaslimit,
659        }
660    }
661}
662
663pub enum BranchInfo<'a> {
664    NotBranch,
665    Jump(BasicBlockId),
666    Branch(ValueId, BasicBlockId, BasicBlockId),
667    Switch(ValueId, &'a SwitchTable, Option<BasicBlockId>),
668}
669
670impl<'a> BranchInfo<'a> {
671    pub fn is_not_a_branch(&self) -> bool {
672        matches!(self, BranchInfo::NotBranch)
673    }
674
675    pub fn block_iter(&self) -> BlockIter {
676        match self {
677            Self::NotBranch => BlockIter::Zero,
678            Self::Jump(block) => BlockIter::one(*block),
679            Self::Branch(_, then, else_) => BlockIter::one(*then).chain(BlockIter::one(*else_)),
680            Self::Switch(_, table, default) => {
681                BlockIter::Slice(table.blocks.iter()).chain(BlockIter::One(*default))
682            }
683        }
684    }
685}
686
687pub type BlockIter<'a> = IterBase<'a, BasicBlockId>;
688pub type ValueIter<'a> = IterBase<'a, ValueId>;
689pub type ValueIterMut<'a> = IterMutBase<'a, ValueId>;
690
691pub enum IterBase<'a, T> {
692    Zero,
693    One(Option<T>),
694    Slice(std::slice::Iter<'a, T>),
695    Chain(Box<IterBase<'a, T>>, Box<IterBase<'a, T>>),
696}
697
698impl<'a, T> IterBase<'a, T> {
699    fn one(value: T) -> Self {
700        Self::One(Some(value))
701    }
702
703    fn chain(self, rhs: Self) -> Self {
704        Self::Chain(self.into(), rhs.into())
705    }
706}
707
708impl<'a, T> Iterator for IterBase<'a, T>
709where
710    T: Copy,
711{
712    type Item = T;
713
714    fn next(&mut self) -> Option<Self::Item> {
715        match self {
716            Self::Zero => None,
717            Self::One(value) => value.take(),
718            Self::Slice(s) => s.next().copied(),
719            Self::Chain(first, second) => {
720                if let Some(value) = first.next() {
721                    Some(value)
722                } else {
723                    second.next()
724                }
725            }
726        }
727    }
728}
729
730pub enum IterMutBase<'a, T> {
731    Zero,
732    One(Option<&'a mut T>),
733    Slice(std::slice::IterMut<'a, T>),
734    Chain(Box<IterMutBase<'a, T>>, Box<IterMutBase<'a, T>>),
735}
736
737impl<'a, T> IterMutBase<'a, T> {
738    fn one(value: &'a mut T) -> Self {
739        Self::One(Some(value))
740    }
741
742    fn chain(self, rhs: Self) -> Self {
743        Self::Chain(self.into(), rhs.into())
744    }
745}
746
747impl<'a, T> Iterator for IterMutBase<'a, T> {
748    type Item = &'a mut T;
749
750    fn next(&mut self) -> Option<Self::Item> {
751        match self {
752            Self::Zero => None,
753            Self::One(value) => value.take(),
754            Self::Slice(s) => s.next(),
755            Self::Chain(first, second) => {
756                if let Some(value) = first.next() {
757                    Some(value)
758                } else {
759                    second.next()
760                }
761            }
762        }
763    }
764}
fe_mir/ir/inst.rs

fe_mir/ir/
inst.rs
