etk_dasm/blocks/
basic.rs

1//! A list of EVM instructions with a single point of entry and a single exit.
2use etk_asm::disasm::Offset;
3
4use etk_ops::shanghai::{Op, Operation};
5
6/// A list of EVM instructions with a single point of entry and a single exit.
7#[derive(Debug, Eq, PartialEq)]
8pub struct BasicBlock {
9    /// Position of the first instruction of this block in the entire program.
10    pub offset: usize,
11
12    /// List of instructions contained in the block.
13    pub ops: Vec<Op<[u8]>>,
14}
15
16impl BasicBlock {
17    /// Sum of the length of every instruction in this block.
18    pub fn size(&self) -> usize {
19        self.ops.iter().map(Op::size).sum()
20    }
21}
22
23/// Separate a sequence of [`Op<[u8]>`] into [`BasicBlock`].
24#[derive(Debug, Default)]
25pub struct Separator {
26    complete_blocks: Vec<BasicBlock>,
27    in_progress: Option<BasicBlock>,
28}
29
30impl Separator {
31    /// Create a default instance.
32    pub fn new() -> Self {
33        Self::default()
34    }
35
36    /// Read instructions from `iter` until it is empty.
37    ///
38    /// Returns `true` if any [`BasicBlock`] are ready.
39    pub fn push_all<I>(&mut self, iter: I) -> bool
40    where
41        I: IntoIterator<Item = Offset<Op<[u8]>>>,
42    {
43        let mut available = false;
44        for item in iter.into_iter() {
45            available |= self.push(item);
46        }
47        available
48    }
49
50    /// Push a single instruction, returns `true` if a [`BasicBlock`] has been
51    /// completed.
52    pub fn push(&mut self, off: Offset<Op<[u8]>>) -> bool {
53        if off.item.is_jump_target() {
54            // If we receive a jumpdest, start a new block beginning with it.
55            let completed = self.in_progress.replace(BasicBlock {
56                offset: off.offset,
57                ops: vec![off.item],
58            });
59
60            if let Some(completed_block) = completed {
61                self.complete_blocks.push(completed_block);
62                return true;
63            } else {
64                return false;
65            }
66        }
67
68        let is_jump = off.item.is_jump() | off.item.is_exit();
69
70        // Append to in-progress block, or start a new block.
71        match self.in_progress {
72            Some(ref mut p) => p.ops.push(off.item),
73            None => {
74                self.in_progress = Some(BasicBlock {
75                    offset: off.offset,
76                    ops: vec![off.item],
77                });
78            }
79        }
80
81        // If we pushed a jump, end the basic block.
82        if is_jump {
83            let in_progress = self.in_progress.take().unwrap();
84            self.complete_blocks.push(in_progress);
85            true
86        } else {
87            false
88        }
89    }
90
91    /// Remove all completed [`BasicBlock`].
92    pub fn take(&mut self) -> Vec<BasicBlock> {
93        std::mem::take(&mut self.complete_blocks)
94    }
95
96    /// Retrieve the last [`BasicBlock`] after all instructions have been
97    /// consumed.
98    #[must_use]
99    pub fn finish(&mut self) -> Option<BasicBlock> {
100        if self.complete_blocks.is_empty() {
101            self.in_progress.take()
102        } else {
103            panic!("not all basic blocks have been taken");
104        }
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use etk_ops::shanghai::*;
111
112    use super::*;
113
114    #[test]
115    fn three_pushes() {
116        let ops = vec![
117            Offset::new(0x00, Op::from(Push1([5]))),
118            Offset::new(0x02, Op::from(Push1([6]))),
119            Offset::new(0x04, Op::from(Push1([7]))),
120        ];
121
122        let blocks = [];
123
124        let last = Some(BasicBlock {
125            offset: 0x00,
126            ops: vec![
127                Op::from(Push1([5])),
128                Op::from(Push1([6])),
129                Op::from(Push1([7])),
130            ],
131        });
132
133        let mut sep = Separator::new();
134        let completed = sep.push_all(ops.into_iter());
135        assert!(!completed);
136        assert_eq!(sep.take(), blocks);
137        assert_eq!(sep.finish(), last);
138    }
139
140    #[test]
141    fn three_jumpdests() {
142        let ops = vec![
143            Offset::new(0x00, Op::from(JumpDest)),
144            Offset::new(0x01, Op::from(JumpDest)),
145            Offset::new(0x02, Op::from(JumpDest)),
146        ];
147
148        let blocks = [
149            BasicBlock {
150                offset: 0x00,
151                ops: vec![Op::from(JumpDest)],
152            },
153            BasicBlock {
154                offset: 0x01,
155                ops: vec![Op::from(JumpDest)],
156            },
157        ];
158
159        let last = Some(BasicBlock {
160            offset: 0x02,
161            ops: vec![Op::from(JumpDest)],
162        });
163
164        let mut sep = Separator::new();
165        let completed = sep.push_all(ops.into_iter());
166        assert!(completed);
167        assert_eq!(sep.take(), blocks);
168        assert_eq!(sep.finish(), last);
169    }
170
171    #[test]
172    fn jumpdest_jump_jumpdest_jump() {
173        let ops = vec![
174            Offset::new(0x00, Op::from(JumpDest)),
175            Offset::new(0x01, Op::from(Jump)),
176            Offset::new(0x02, Op::from(JumpDest)),
177            Offset::new(0x03, Op::from(Jump)),
178        ];
179
180        let blocks = [
181            BasicBlock {
182                offset: 0x00,
183                ops: vec![Op::from(JumpDest), Op::from(Jump)],
184            },
185            BasicBlock {
186                offset: 0x02,
187                ops: vec![Op::from(JumpDest), Op::from(Jump)],
188            },
189        ];
190
191        let last = None;
192
193        let mut sep = Separator::new();
194        let completed = sep.push_all(ops.into_iter());
195        assert!(completed);
196        assert_eq!(sep.take(), blocks);
197        assert_eq!(sep.finish(), last);
198    }
199
200    #[test]
201    fn jump_jumpdest_jump_jumpdest() {
202        let ops = vec![
203            Offset::new(0x00, Op::from(Jump)),
204            Offset::new(0x01, Op::from(JumpDest)),
205            Offset::new(0x02, Op::from(Jump)),
206            Offset::new(0x03, Op::from(JumpDest)),
207        ];
208
209        let blocks = [
210            BasicBlock {
211                offset: 0x00,
212                ops: vec![Op::from(Jump)],
213            },
214            BasicBlock {
215                offset: 0x01,
216                ops: vec![Op::from(JumpDest), Op::from(Jump)],
217            },
218        ];
219
220        let last = Some(BasicBlock {
221            offset: 0x03,
222            ops: vec![Op::from(JumpDest)],
223        });
224
225        let mut sep = Separator::new();
226        let completed = sep.push_all(ops.into_iter());
227        assert!(completed);
228        assert_eq!(sep.take(), blocks);
229        assert_eq!(sep.finish(), last);
230    }
231
232    #[test]
233    fn three_jumps() {
234        let ops = vec![
235            Offset::new(0x00, Op::from(Jump)),
236            Offset::new(0x01, Op::from(Jump)),
237            Offset::new(0x02, Op::from(Jump)),
238        ];
239
240        let blocks = [
241            BasicBlock {
242                offset: 0x00,
243                ops: vec![Op::from(Jump)],
244            },
245            BasicBlock {
246                offset: 0x01,
247                ops: vec![Op::from(Jump)],
248            },
249            BasicBlock {
250                offset: 0x02,
251                ops: vec![Op::from(Jump)],
252            },
253        ];
254
255        let last = None;
256
257        let mut sep = Separator::new();
258        let completed = sep.push_all(ops.into_iter());
259        assert!(completed);
260        assert_eq!(sep.take(), blocks);
261        assert_eq!(sep.finish(), last);
262    }
263}
etk_dasm/blocks/basic.rs

etk_dasm/blocks/
basic.rs
