1mod export;
2mod sccp;
3mod value;
4
5use crate::error::BytecodeReadError;
6use crate::function::BytecodeFunction;
7use crate::model::{ConstantIndex, Instruction, InstructionAux, Register};
8use crate::opcodes::Opcode;
9use std::collections::HashMap;
10use value::FunctionGraphBuilder;
11
12macro_rules! bytecode_handle_id {
13 ($visibility:vis $name:ident) => {
14 #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
15 $visibility struct $name(usize);
16
17 impl $name {
18 $visibility const fn new(index: usize) -> Self {
19 Self(index)
20 }
21
22 $visibility const fn index(self) -> usize {
23 self.0
24 }
25
26 $visibility const fn identity_hash(self) -> usize {
27 self.0
28 }
29 }
30
31 impl std::fmt::LowerHex for $name {
32 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33 std::fmt::LowerHex::fmt(&self.0, formatter)
34 }
35 }
36 };
37}
38
39bytecode_handle_id!(pub BytecodeBlockId);
40bytecode_handle_id!(pub BytecodeInstructionId);
41bytecode_handle_id!(pub InstructionPc);
42
43pub use export::BytecodeWriteError;
44pub(crate) use export::encode_function_bytecode;
45pub use sccp::{ConstantLattice, Sccp, fold_constants};
46
47pub fn uses<'function>(
48 function: &'function BytecodeFunction<'_>,
49 definition: BytecodeOperand,
50) -> Option<&'function [BytecodeOperand]> {
51 match definition {
52 BytecodeOperand::Instruction(id) => Some(function.graph_instruction(id).users()),
53 BytecodeOperand::Phi(id) => Some(function.phi(id).users()),
54 _ => None,
55 }
56}
57
58pub fn count_uses(
59 function: &BytecodeFunction<'_>,
60 definition: BytecodeOperand,
61 consumer: BytecodeOperand,
62) -> usize {
63 uses(function, definition).map_or(0, |uses| {
64 uses.iter()
65 .filter(|candidate| **candidate == consumer)
66 .count()
67 })
68}
69
70pub fn has_use(
71 function: &BytecodeFunction<'_>,
72 definition: BytecodeOperand,
73 consumer: BytecodeOperand,
74) -> bool {
75 count_uses(function, definition, consumer) != 0
76}
77
78pub fn verify_use_consistency(function: &BytecodeFunction<'_>) -> bool {
79 for block in function.blocks().iter().filter(|block| !block.is_dead()) {
80 for id in block.phis() {
81 let consumer = BytecodeOperand::Phi(*id);
82 for operand in function.phi(*id).operands() {
83 if matches!(
84 operand,
85 BytecodeOperand::Instruction(_) | BytecodeOperand::Phi(_)
86 ) && !has_use(function, *operand, consumer)
87 {
88 return false;
89 }
90 }
91 }
92
93 for id in block.graph_instructions() {
94 let consumer = BytecodeOperand::Instruction(*id);
95 for operand in function.graph_instruction(*id).operands() {
96 if matches!(
97 operand,
98 BytecodeOperand::Instruction(_) | BytecodeOperand::Phi(_)
99 ) && !has_use(function, *operand, consumer)
100 {
101 return false;
102 }
103 }
104 }
105 }
106 true
107}
108
109pub(crate) fn build_function_graph(
110 function: &mut BytecodeFunction<'_>,
111 code: &[Instruction],
112) -> Result<(), BytecodeReadError> {
113 let stream = BytecodeInstructionStream::new(code);
114 let BlockGraph {
115 mut blocks,
116 block_by_start,
117 entry,
118 exit,
119 instruction_count,
120 } = rebuild_blocks(code, stream)?;
121
122 if blocks.len() > MAX_CFG_BLOCKS {
123 return Err(BytecodeReadError::FunctionGraphTooLarge {
124 blocks: blocks.len(),
125 });
126 }
127
128 let mut builder = FunctionGraphBuilder::new(&blocks, function.num_params, entry);
129 let mut instructions = Vec::with_capacity(instruction_count);
130 let mut pc_to_instruction = vec![BytecodeInstructionId::new(0); code.len()];
131 let mut pc_to_block = vec![exit; code.len()];
132 let mut current_block = entry;
133 builder.begin_block(
134 current_block,
135 entry,
136 &blocks[current_block.index()].predecessors,
137 );
138
139 let mut pc = 0usize;
140 while pc < code.len() {
141 let instruction_pc = InstructionPc::new(pc);
142 let instruction = stream.graph_instruction(instruction_pc);
143 let id = BytecodeInstructionId::new(instructions.len());
144 pc_to_instruction[pc] = id;
145 blocks[current_block.index()]
146 .instructions
147 .push(instruction_pc);
148 blocks[current_block.index()].instruction_ids.push(id);
149 pc_to_block[pc] = current_block;
150
151 let operands = builder.operands_for(
152 id,
153 instruction_pc,
154 instruction,
155 stream,
156 &block_by_start,
157 &blocks,
158 )?;
159 let opcode = unsafe { instruction.opcode_unchecked() };
160 instructions.push(BytecodeInstruction {
161 pc: instruction_pc,
162 opcode,
163 line: function.lines.get(pc).copied().unwrap_or_default(),
164 block: current_block,
165 operands,
166 users: Vec::new(),
167 });
168
169 pc += stream.graph_instruction_length(pc);
170 if let Some(next_block) = block_by_start.get(&pc).copied() {
171 builder.finish_block(current_block, &blocks);
172 current_block = next_block;
173 builder.begin_block(
174 current_block,
175 entry,
176 &blocks[current_block.index()].predecessors,
177 );
178 }
179 }
180 builder.finish_block(current_block, &blocks);
181 builder.seal_all_remaining(&blocks);
182 builder.simplify_phis(&mut instructions);
183
184 for (block, phis) in blocks.iter_mut().zip(&builder.block_phis) {
185 block.phis.clone_from(phis);
186 }
187 rebuild_uses(&mut instructions, &mut builder.phis);
188
189 function.blocks = blocks;
190 function.instructions = instructions;
191 function.immediates = builder.immediates;
192 function.phis = builder.phis;
193 function.projections = builder.projections;
194 function.registers = builder.registers;
195 function.entry_block = entry;
196 function.exit_block = exit;
197 function.pc_to_block = pc_to_block;
198 function.pc_to_instruction = pc_to_instruction;
199 Ok(())
200}
201
202fn rebuild_uses(instructions: &mut [BytecodeInstruction], phis: &mut [BytecodePhi]) {
203 for instruction in instructions.iter_mut() {
204 instruction.users.clear();
205 }
206 for phi in phis.iter_mut() {
207 phi.users.clear();
208 }
209
210 for index in 0..instructions.len() {
211 let user = BytecodeOperand::Instruction(BytecodeInstructionId::new(index));
212 let operands = instructions[index].operands.clone();
213 for operand in operands {
214 record_use(instructions, phis, operand, user);
215 }
216 }
217 for index in 0..phis.len() {
218 let user = BytecodeOperand::Phi(BytecodePhiId::new(index));
219 let operands = phis[index].operands.clone();
220 for operand in operands {
221 record_use(instructions, phis, operand, user);
222 }
223 }
224}
225
226fn record_use(
227 instructions: &mut [BytecodeInstruction],
228 phis: &mut [BytecodePhi],
229 used: BytecodeOperand,
230 user: BytecodeOperand,
231) {
232 match used {
233 BytecodeOperand::Instruction(id) => instructions[id.index()].users.push(user),
234 BytecodeOperand::Phi(id) => phis[id.index()].users.push(user),
235 _ => {}
236 }
237}
238
239const MAX_CFG_BLOCKS: usize = 1000;
240
241struct BlockGraph {
242 blocks: Vec<BytecodeBlock>,
243 block_by_start: HashMap<usize, BytecodeBlockId>,
244 entry: BytecodeBlockId,
245 exit: BytecodeBlockId,
246 instruction_count: usize,
247}
248
249fn rebuild_blocks(
250 code: &[Instruction],
251 stream: BytecodeInstructionStream<'_>,
252) -> Result<BlockGraph, BytecodeReadError> {
253 let mut blocks = Vec::new();
254 let mut block_by_start = HashMap::new();
255
256 let entry = make_block(&mut blocks, &mut block_by_start, 0);
257 let exit = make_block(&mut blocks, &mut block_by_start, usize::MAX);
258
259 let mut pc = 0usize;
260 let mut current_block = entry;
261 let mut instruction_count = 0usize;
262
263 while pc < code.len() {
264 let instruction = code[pc];
265 let opcode = unsafe { instruction.opcode_unchecked() };
266 let target = stream.graph_block_target(pc).filter(|target| *target >= 0);
267 let needs_block =
268 target.is_some() && !opcode.is_fast_call() && !stream.is_jump_trampoline(pc);
269 if let Some(target) = target.filter(|_| needs_block) {
270 let target = target as usize;
271 if !block_by_start.contains_key(&target) {
272 let new_block = make_block(&mut blocks, &mut block_by_start, target);
273 if target < pc {
274 split_backward_target(&mut blocks, &block_by_start, target, new_block);
275 }
276 }
277
278 let target_block = block_by_start[&target];
279 let kind = if opcode.is_loop_jump() {
280 BytecodeEdgeKind::Loop
281 } else {
282 BytecodeEdgeKind::Branch
283 };
284 connect_blocks(&mut blocks, current_block, target_block, kind);
285 }
286
287 if opcode == Opcode::Return {
288 connect_blocks(
289 &mut blocks,
290 current_block,
291 exit,
292 BytecodeEdgeKind::Fallthrough,
293 );
294 }
295
296 pc += opcode.length();
297
298 if (needs_block || (opcode == Opcode::Return && pc < code.len()))
299 && !block_by_start.contains_key(&pc)
300 {
301 make_block(&mut blocks, &mut block_by_start, pc);
302 }
303
304 if let Some(next_block) = block_by_start.get(&pc).copied() {
305 if opcode.is_fallthrough() {
306 connect_blocks(
307 &mut blocks,
308 current_block,
309 next_block,
310 BytecodeEdgeKind::Fallthrough,
311 );
312 }
313 current_block = next_block;
314 }
315
316 instruction_count += 1;
317 }
318
319 Ok(BlockGraph {
320 blocks,
321 block_by_start,
322 entry,
323 exit,
324 instruction_count,
325 })
326}
327
328fn make_block(
329 blocks: &mut Vec<BytecodeBlock>,
330 block_by_start: &mut HashMap<usize, BytecodeBlockId>,
331 pc: usize,
332) -> BytecodeBlockId {
333 let id = BytecodeBlockId::new(blocks.len());
334 block_by_start.insert(pc, id);
335 blocks.push(BytecodeBlock::new(InstructionPc::new(pc)));
336 id
337}
338
339fn split_backward_target(
340 blocks: &mut [BytecodeBlock],
341 block_by_start: &HashMap<usize, BytecodeBlockId>,
342 target: usize,
343 new_block: BytecodeBlockId,
344) {
345 let Some(previous_start) = (0..target).rev().find(|pc| block_by_start.contains_key(pc)) else {
346 return;
347 };
348 let previous_block = block_by_start[&previous_start];
349
350 let stolen_successors = std::mem::take(&mut blocks[previous_block.index()].successors);
351 blocks[new_block.index()].successors = stolen_successors;
352 connect_blocks(
353 blocks,
354 previous_block,
355 new_block,
356 BytecodeEdgeKind::Fallthrough,
357 );
358
359 for successor_index in 0..blocks[new_block.index()].successors.len() {
360 let edge = blocks[new_block.index()].successors[successor_index];
361 for predecessor in &mut blocks[edge.target.index()].predecessors {
362 if predecessor.target == previous_block {
363 predecessor.target = new_block;
364 }
365 }
366 }
367}
368
369#[derive(Clone, Copy)]
370pub(super) struct BytecodeInstructionStream<'code> {
371 code: &'code [Instruction],
372}
373
374impl<'code> BytecodeInstructionStream<'code> {
375 fn new(code: &'code [Instruction]) -> Self {
376 Self { code }
377 }
378
379 pub(super) fn instruction(&self, pc: InstructionPc) -> Option<Instruction> {
380 self.code.get(pc.index()).copied()
381 }
382
383 pub(super) fn graph_instruction(&self, pc: InstructionPc) -> Instruction {
384 if self.is_jump_trampoline(pc.index()) {
385 self.code[pc.index() + 2]
386 } else {
387 self.code[pc.index()]
388 }
389 }
390
391 pub(super) fn aux_word(&self, pc: InstructionPc) -> Option<InstructionAux> {
392 let instruction = self.instruction(pc)?;
393 (unsafe { instruction.opcode_unchecked() }.length() == 2)
394 .then(|| {
395 self.code
396 .get(pc.index() + 1)
397 .copied()
398 .map(Instruction::word)
399 })
400 .flatten()
401 .map(InstructionAux::new)
402 }
403
404 pub(super) fn graph_aux_word(&self, pc: InstructionPc) -> Option<InstructionAux> {
405 if self.is_jump_trampoline(pc.index()) {
406 self.aux_word(InstructionPc::new(pc.index() + 2))
407 } else {
408 self.aux_word(pc)
409 }
410 }
411
412 pub(super) fn jump_target(&self, pc: usize) -> Option<i32> {
413 unsafe { self.code.get(pc)?.jump_target_unchecked(pc as u32) }
414 }
415
416 pub(super) fn graph_jump_target(&self, pc: usize) -> Option<i32> {
417 if self.is_jump_trampoline(pc) {
418 let long_offset = self.code.get(pc + 1)?.e();
419 Some(pc as i32 + 2 + long_offset)
420 } else {
421 self.jump_target(pc)
422 }
423 }
424
425 fn graph_block_target(&self, pc: usize) -> Option<i32> {
426 let target = self.jump_target(pc)?;
427
428 if target >= 0
429 && self
430 .code
431 .get(target as usize)
432 .is_some_and(|instruction| unsafe {
433 instruction.opcode_unchecked() == Opcode::JumpX
434 })
435 {
436 return self.jump_target(target as usize);
437 }
438
439 Some(target)
440 }
441
442 fn is_jump_trampoline(&self, pc: usize) -> bool {
443 self.code
444 .get(pc)
445 .is_some_and(|instruction| unsafe { instruction.opcode_unchecked() } == Opcode::Jump)
446 && self.code.get(pc + 1).is_some_and(|instruction| unsafe {
447 instruction.opcode_unchecked() == Opcode::JumpX
448 })
449 && self.code.get(pc + 2).and_then(|instruction| unsafe {
450 instruction.jump_target_unchecked((pc + 2) as u32)
451 }) == Some((pc + 1) as i32)
452 }
453
454 pub(super) fn graph_instruction_length(&self, pc: usize) -> usize {
455 if self.is_jump_trampoline(pc) {
456 2 + unsafe { self.code[pc + 2].opcode_unchecked() }.length()
457 } else {
458 unsafe { self.code[pc].opcode_unchecked() }.length()
459 }
460 }
461}
462
463#[derive(Debug, Clone, PartialEq, Eq)]
464pub struct BytecodeBlock {
465 start_pc: u32,
466 sort_key: u32,
467 instructions: Vec<InstructionPc>,
468 instruction_ids: Vec<BytecodeInstructionId>,
469 phis: Vec<BytecodePhiId>,
470 predecessors: Vec<BytecodeEdge>,
471 successors: Vec<BytecodeEdge>,
472 dead: bool,
473 use_count: u32,
474}
475
476impl BytecodeBlock {
477 fn new(start: InstructionPc) -> Self {
478 let pc = u32::try_from(start.index()).unwrap_or(u32::MAX);
479 Self {
480 start_pc: pc,
481 sort_key: pc,
482 instructions: Vec::new(),
483 instruction_ids: Vec::new(),
484 phis: Vec::new(),
485 predecessors: Vec::new(),
486 successors: Vec::new(),
487 dead: false,
488 use_count: 0,
489 }
490 }
491
492 pub fn start(&self) -> InstructionPc {
493 InstructionPc::new(self.start_pc as usize)
494 }
495
496 pub(crate) fn set_start_pc(&mut self, pc: u32) {
497 self.start_pc = pc;
498 }
499
500 pub(crate) fn start_pc(&self) -> u32 {
501 self.start_pc
502 }
503
504 pub(crate) fn sort_key(&self) -> u32 {
505 self.sort_key
506 }
507
508 pub fn instructions(&self) -> &[InstructionPc] {
509 &self.instructions
510 }
511
512 pub fn graph_instructions(&self) -> &[BytecodeInstructionId] {
513 &self.instruction_ids
514 }
515
516 pub fn phis(&self) -> &[BytecodePhiId] {
517 &self.phis
518 }
519
520 pub fn predecessors(&self) -> &[BytecodeEdge] {
521 &self.predecessors
522 }
523
524 pub fn successors(&self) -> &[BytecodeEdge] {
525 &self.successors
526 }
527
528 pub fn is_dead(&self) -> bool {
529 self.dead
530 }
531
532 pub fn use_count(&self) -> u32 {
533 self.use_count
534 }
535
536 pub fn terminal_pc(&self) -> Option<InstructionPc> {
537 self.instructions.last().copied()
538 }
539
540 pub(crate) fn append_graph_instruction(&mut self, id: BytecodeInstructionId) {
541 self.instruction_ids.push(id);
542 }
543}
544
545#[derive(Debug, Clone, Copy, PartialEq, Eq)]
546pub struct BytecodeEdge {
547 pub kind: BytecodeEdgeKind,
548 pub target: BytecodeBlockId,
549}
550
551impl BytecodeEdge {
552 fn new(kind: BytecodeEdgeKind, target: BytecodeBlockId) -> Self {
553 Self { kind, target }
554 }
555}
556
557#[derive(Debug, Clone, Copy, PartialEq, Eq)]
558pub enum BytecodeEdgeKind {
559 Branch,
560 Fallthrough,
561 Loop,
562}
563
564#[derive(Debug, Clone, PartialEq, Eq)]
565pub struct BytecodeInstruction {
566 pc: InstructionPc,
567 opcode: Opcode,
568 line: u32,
569 block: BytecodeBlockId,
570 operands: Vec<BytecodeOperand>,
571 users: Vec<BytecodeOperand>,
572}
573
574impl BytecodeInstruction {
575 pub(crate) fn synthetic_jump(block: BytecodeBlockId, target: BytecodeBlockId) -> Self {
576 Self {
577 pc: InstructionPc::new(usize::MAX),
578 opcode: Opcode::Jump,
579 line: 0,
580 block,
581 operands: vec![BytecodeOperand::Block(target)],
582 users: Vec::new(),
583 }
584 }
585
586 pub fn pc(&self) -> InstructionPc {
587 self.pc
588 }
589
590 pub fn opcode(&self) -> Opcode {
591 self.opcode
592 }
593
594 pub fn line(&self) -> u32 {
595 self.line
596 }
597
598 pub fn block(&self) -> BytecodeBlockId {
599 self.block
600 }
601
602 pub fn operands(&self) -> &[BytecodeOperand] {
603 &self.operands
604 }
605
606 pub fn users(&self) -> &[BytecodeOperand] {
607 &self.users
608 }
609}
610
611#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
612pub enum BytecodeOperand {
613 Immediate(BytecodeImmediateId),
614 Instruction(BytecodeInstructionId),
615 Block(BytecodeBlockId),
616 Phi(BytecodePhiId),
617 Projection(BytecodeProjectionId),
618 VmRegister(Register),
619 VmConstant(ConstantIndex),
620 VmUpvalue(u32),
621 VmProto(u32),
622}
623
624bytecode_handle_id!(pub BytecodeImmediateId);
625bytecode_handle_id!(pub BytecodePhiId);
626bytecode_handle_id!(pub BytecodeProjectionId);
627
628#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
629pub enum BytecodeImmediate {
630 Boolean(bool),
631 Int(i32),
632 Import(u32),
633}
634
635#[derive(Debug, Clone, PartialEq, Eq, Hash)]
636pub struct BytecodePhi {
637 operands: Vec<BytecodeOperand>,
638 users: Vec<BytecodeOperand>,
639}
640
641impl BytecodePhi {
642 pub fn operands(&self) -> &[BytecodeOperand] {
643 &self.operands
644 }
645
646 pub fn users(&self) -> &[BytecodeOperand] {
647 &self.users
648 }
649}
650
651#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
652pub struct BytecodeProjection {
653 pub source: BytecodeOperand,
654 pub index: u32,
655}
656
657fn connect_blocks(
658 blocks: &mut [BytecodeBlock],
659 source: BytecodeBlockId,
660 target: BytecodeBlockId,
661 kind: BytecodeEdgeKind,
662) {
663 blocks[source.index()]
664 .successors
665 .push(BytecodeEdge::new(kind, target));
666 blocks[target.index()]
667 .predecessors
668 .push(BytecodeEdge::new(kind, source));
669}