mod export;
mod sccp;
mod value;
use crate::error::BytecodeReadError;
use crate::function::BytecodeFunction;
use crate::model::{ConstantIndex, Instruction, InstructionAux, Register};
use crate::opcodes::Opcode;
use std::collections::HashMap;
use value::FunctionGraphBuilder;
macro_rules! bytecode_handle_id {
($visibility:vis $name:ident) => {
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
$visibility struct $name(usize);
impl $name {
$visibility const fn new(index: usize) -> Self {
Self(index)
}
$visibility const fn index(self) -> usize {
self.0
}
$visibility const fn identity_hash(self) -> usize {
self.0
}
}
impl std::fmt::LowerHex for $name {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
std::fmt::LowerHex::fmt(&self.0, formatter)
}
}
};
}
bytecode_handle_id!(pub BytecodeBlockId);
bytecode_handle_id!(pub BytecodeInstructionId);
bytecode_handle_id!(pub InstructionPc);
pub use export::BytecodeWriteError;
pub(crate) use export::encode_function_bytecode;
pub use sccp::{ConstantLattice, Sccp, fold_constants};
pub fn uses<'function>(
function: &'function BytecodeFunction<'_>,
definition: BytecodeOperand,
) -> Option<&'function [BytecodeOperand]> {
match definition {
BytecodeOperand::Instruction(id) => Some(function.graph_instruction(id).users()),
BytecodeOperand::Phi(id) => Some(function.phi(id).users()),
_ => None,
}
}
pub fn count_uses(
function: &BytecodeFunction<'_>,
definition: BytecodeOperand,
consumer: BytecodeOperand,
) -> usize {
uses(function, definition).map_or(0, |uses| {
uses.iter()
.filter(|candidate| **candidate == consumer)
.count()
})
}
pub fn has_use(
function: &BytecodeFunction<'_>,
definition: BytecodeOperand,
consumer: BytecodeOperand,
) -> bool {
count_uses(function, definition, consumer) != 0
}
pub fn verify_use_consistency(function: &BytecodeFunction<'_>) -> bool {
for block in function.blocks().iter().filter(|block| !block.is_dead()) {
for id in block.phis() {
let consumer = BytecodeOperand::Phi(*id);
for operand in function.phi(*id).operands() {
if matches!(
operand,
BytecodeOperand::Instruction(_) | BytecodeOperand::Phi(_)
) && !has_use(function, *operand, consumer)
{
return false;
}
}
}
for id in block.graph_instructions() {
let consumer = BytecodeOperand::Instruction(*id);
for operand in function.graph_instruction(*id).operands() {
if matches!(
operand,
BytecodeOperand::Instruction(_) | BytecodeOperand::Phi(_)
) && !has_use(function, *operand, consumer)
{
return false;
}
}
}
}
true
}
pub(crate) fn build_function_graph(
function: &mut BytecodeFunction<'_>,
code: &[Instruction],
) -> Result<(), BytecodeReadError> {
let stream = BytecodeInstructionStream::new(code);
let BlockGraph {
mut blocks,
block_by_start,
entry,
exit,
instruction_count,
} = rebuild_blocks(code, stream)?;
if blocks.len() > MAX_CFG_BLOCKS {
return Err(BytecodeReadError::FunctionGraphTooLarge {
blocks: blocks.len(),
});
}
let mut builder = FunctionGraphBuilder::new(&blocks, function.num_params, entry);
let mut instructions = Vec::with_capacity(instruction_count);
let mut pc_to_instruction = vec![BytecodeInstructionId::new(0); code.len()];
let mut pc_to_block = vec![exit; code.len()];
let mut current_block = entry;
builder.begin_block(
current_block,
entry,
&blocks[current_block.index()].predecessors,
);
let mut pc = 0usize;
while pc < code.len() {
let instruction_pc = InstructionPc::new(pc);
let instruction = stream.graph_instruction(instruction_pc);
let id = BytecodeInstructionId::new(instructions.len());
pc_to_instruction[pc] = id;
blocks[current_block.index()]
.instructions
.push(instruction_pc);
blocks[current_block.index()].instruction_ids.push(id);
pc_to_block[pc] = current_block;
let operands = builder.operands_for(
id,
instruction_pc,
instruction,
stream,
&block_by_start,
&blocks,
)?;
let opcode = unsafe { instruction.opcode_unchecked() };
instructions.push(BytecodeInstruction {
pc: instruction_pc,
opcode,
line: function.lines.get(pc).copied().unwrap_or_default(),
block: current_block,
operands,
users: Vec::new(),
});
pc += stream.graph_instruction_length(pc);
if let Some(next_block) = block_by_start.get(&pc).copied() {
builder.finish_block(current_block, &blocks);
current_block = next_block;
builder.begin_block(
current_block,
entry,
&blocks[current_block.index()].predecessors,
);
}
}
builder.finish_block(current_block, &blocks);
builder.seal_all_remaining(&blocks);
builder.simplify_phis(&mut instructions);
for (block, phis) in blocks.iter_mut().zip(&builder.block_phis) {
block.phis.clone_from(phis);
}
rebuild_uses(&mut instructions, &mut builder.phis);
function.blocks = blocks;
function.instructions = instructions;
function.immediates = builder.immediates;
function.phis = builder.phis;
function.projections = builder.projections;
function.registers = builder.registers;
function.entry_block = entry;
function.exit_block = exit;
function.pc_to_block = pc_to_block;
function.pc_to_instruction = pc_to_instruction;
Ok(())
}
fn rebuild_uses(instructions: &mut [BytecodeInstruction], phis: &mut [BytecodePhi]) {
for instruction in instructions.iter_mut() {
instruction.users.clear();
}
for phi in phis.iter_mut() {
phi.users.clear();
}
for index in 0..instructions.len() {
let user = BytecodeOperand::Instruction(BytecodeInstructionId::new(index));
let operands = instructions[index].operands.clone();
for operand in operands {
record_use(instructions, phis, operand, user);
}
}
for index in 0..phis.len() {
let user = BytecodeOperand::Phi(BytecodePhiId::new(index));
let operands = phis[index].operands.clone();
for operand in operands {
record_use(instructions, phis, operand, user);
}
}
}
fn record_use(
instructions: &mut [BytecodeInstruction],
phis: &mut [BytecodePhi],
used: BytecodeOperand,
user: BytecodeOperand,
) {
match used {
BytecodeOperand::Instruction(id) => instructions[id.index()].users.push(user),
BytecodeOperand::Phi(id) => phis[id.index()].users.push(user),
_ => {}
}
}
const MAX_CFG_BLOCKS: usize = 1000;
struct BlockGraph {
blocks: Vec<BytecodeBlock>,
block_by_start: HashMap<usize, BytecodeBlockId>,
entry: BytecodeBlockId,
exit: BytecodeBlockId,
instruction_count: usize,
}
fn rebuild_blocks(
code: &[Instruction],
stream: BytecodeInstructionStream<'_>,
) -> Result<BlockGraph, BytecodeReadError> {
let mut blocks = Vec::new();
let mut block_by_start = HashMap::new();
let entry = make_block(&mut blocks, &mut block_by_start, 0);
let exit = make_block(&mut blocks, &mut block_by_start, usize::MAX);
let mut pc = 0usize;
let mut current_block = entry;
let mut instruction_count = 0usize;
while pc < code.len() {
let instruction = code[pc];
let opcode = unsafe { instruction.opcode_unchecked() };
let target = stream.graph_block_target(pc).filter(|target| *target >= 0);
let needs_block =
target.is_some() && !opcode.is_fast_call() && !stream.is_jump_trampoline(pc);
if let Some(target) = target.filter(|_| needs_block) {
let target = target as usize;
if !block_by_start.contains_key(&target) {
let new_block = make_block(&mut blocks, &mut block_by_start, target);
if target < pc {
split_backward_target(&mut blocks, &block_by_start, target, new_block);
}
}
let target_block = block_by_start[&target];
let kind = if opcode.is_loop_jump() {
BytecodeEdgeKind::Loop
} else {
BytecodeEdgeKind::Branch
};
connect_blocks(&mut blocks, current_block, target_block, kind);
}
if opcode == Opcode::Return {
connect_blocks(
&mut blocks,
current_block,
exit,
BytecodeEdgeKind::Fallthrough,
);
}
pc += opcode.length();
if (needs_block || (opcode == Opcode::Return && pc < code.len()))
&& !block_by_start.contains_key(&pc)
{
make_block(&mut blocks, &mut block_by_start, pc);
}
if let Some(next_block) = block_by_start.get(&pc).copied() {
if opcode.is_fallthrough() {
connect_blocks(
&mut blocks,
current_block,
next_block,
BytecodeEdgeKind::Fallthrough,
);
}
current_block = next_block;
}
instruction_count += 1;
}
Ok(BlockGraph {
blocks,
block_by_start,
entry,
exit,
instruction_count,
})
}
fn make_block(
blocks: &mut Vec<BytecodeBlock>,
block_by_start: &mut HashMap<usize, BytecodeBlockId>,
pc: usize,
) -> BytecodeBlockId {
let id = BytecodeBlockId::new(blocks.len());
block_by_start.insert(pc, id);
blocks.push(BytecodeBlock::new(InstructionPc::new(pc)));
id
}
fn split_backward_target(
blocks: &mut [BytecodeBlock],
block_by_start: &HashMap<usize, BytecodeBlockId>,
target: usize,
new_block: BytecodeBlockId,
) {
let Some(previous_start) = (0..target).rev().find(|pc| block_by_start.contains_key(pc)) else {
return;
};
let previous_block = block_by_start[&previous_start];
let stolen_successors = std::mem::take(&mut blocks[previous_block.index()].successors);
blocks[new_block.index()].successors = stolen_successors;
connect_blocks(
blocks,
previous_block,
new_block,
BytecodeEdgeKind::Fallthrough,
);
for successor_index in 0..blocks[new_block.index()].successors.len() {
let edge = blocks[new_block.index()].successors[successor_index];
for predecessor in &mut blocks[edge.target.index()].predecessors {
if predecessor.target == previous_block {
predecessor.target = new_block;
}
}
}
}
#[derive(Clone, Copy)]
pub(super) struct BytecodeInstructionStream<'code> {
code: &'code [Instruction],
}
impl<'code> BytecodeInstructionStream<'code> {
fn new(code: &'code [Instruction]) -> Self {
Self { code }
}
pub(super) fn instruction(&self, pc: InstructionPc) -> Option<Instruction> {
self.code.get(pc.index()).copied()
}
pub(super) fn graph_instruction(&self, pc: InstructionPc) -> Instruction {
if self.is_jump_trampoline(pc.index()) {
self.code[pc.index() + 2]
} else {
self.code[pc.index()]
}
}
pub(super) fn aux_word(&self, pc: InstructionPc) -> Option<InstructionAux> {
let instruction = self.instruction(pc)?;
(unsafe { instruction.opcode_unchecked() }.length() == 2)
.then(|| {
self.code
.get(pc.index() + 1)
.copied()
.map(Instruction::word)
})
.flatten()
.map(InstructionAux::new)
}
pub(super) fn graph_aux_word(&self, pc: InstructionPc) -> Option<InstructionAux> {
if self.is_jump_trampoline(pc.index()) {
self.aux_word(InstructionPc::new(pc.index() + 2))
} else {
self.aux_word(pc)
}
}
pub(super) fn jump_target(&self, pc: usize) -> Option<i32> {
unsafe { self.code.get(pc)?.jump_target_unchecked(pc as u32) }
}
pub(super) fn graph_jump_target(&self, pc: usize) -> Option<i32> {
if self.is_jump_trampoline(pc) {
let long_offset = self.code.get(pc + 1)?.e();
Some(pc as i32 + 2 + long_offset)
} else {
self.jump_target(pc)
}
}
fn graph_block_target(&self, pc: usize) -> Option<i32> {
let target = self.jump_target(pc)?;
if target >= 0
&& self
.code
.get(target as usize)
.is_some_and(|instruction| unsafe {
instruction.opcode_unchecked() == Opcode::JumpX
})
{
return self.jump_target(target as usize);
}
Some(target)
}
fn is_jump_trampoline(&self, pc: usize) -> bool {
self.code
.get(pc)
.is_some_and(|instruction| unsafe { instruction.opcode_unchecked() } == Opcode::Jump)
&& self.code.get(pc + 1).is_some_and(|instruction| unsafe {
instruction.opcode_unchecked() == Opcode::JumpX
})
&& self.code.get(pc + 2).and_then(|instruction| unsafe {
instruction.jump_target_unchecked((pc + 2) as u32)
}) == Some((pc + 1) as i32)
}
pub(super) fn graph_instruction_length(&self, pc: usize) -> usize {
if self.is_jump_trampoline(pc) {
2 + unsafe { self.code[pc + 2].opcode_unchecked() }.length()
} else {
unsafe { self.code[pc].opcode_unchecked() }.length()
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BytecodeBlock {
start_pc: u32,
sort_key: u32,
instructions: Vec<InstructionPc>,
instruction_ids: Vec<BytecodeInstructionId>,
phis: Vec<BytecodePhiId>,
predecessors: Vec<BytecodeEdge>,
successors: Vec<BytecodeEdge>,
dead: bool,
use_count: u32,
}
impl BytecodeBlock {
fn new(start: InstructionPc) -> Self {
let pc = u32::try_from(start.index()).unwrap_or(u32::MAX);
Self {
start_pc: pc,
sort_key: pc,
instructions: Vec::new(),
instruction_ids: Vec::new(),
phis: Vec::new(),
predecessors: Vec::new(),
successors: Vec::new(),
dead: false,
use_count: 0,
}
}
pub fn start(&self) -> InstructionPc {
InstructionPc::new(self.start_pc as usize)
}
pub(crate) fn set_start_pc(&mut self, pc: u32) {
self.start_pc = pc;
}
pub(crate) fn start_pc(&self) -> u32 {
self.start_pc
}
pub(crate) fn sort_key(&self) -> u32 {
self.sort_key
}
pub fn instructions(&self) -> &[InstructionPc] {
&self.instructions
}
pub fn graph_instructions(&self) -> &[BytecodeInstructionId] {
&self.instruction_ids
}
pub fn phis(&self) -> &[BytecodePhiId] {
&self.phis
}
pub fn predecessors(&self) -> &[BytecodeEdge] {
&self.predecessors
}
pub fn successors(&self) -> &[BytecodeEdge] {
&self.successors
}
pub fn is_dead(&self) -> bool {
self.dead
}
pub fn use_count(&self) -> u32 {
self.use_count
}
pub fn terminal_pc(&self) -> Option<InstructionPc> {
self.instructions.last().copied()
}
pub(crate) fn append_graph_instruction(&mut self, id: BytecodeInstructionId) {
self.instruction_ids.push(id);
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BytecodeEdge {
pub kind: BytecodeEdgeKind,
pub target: BytecodeBlockId,
}
impl BytecodeEdge {
fn new(kind: BytecodeEdgeKind, target: BytecodeBlockId) -> Self {
Self { kind, target }
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BytecodeEdgeKind {
Branch,
Fallthrough,
Loop,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BytecodeInstruction {
pc: InstructionPc,
opcode: Opcode,
line: u32,
block: BytecodeBlockId,
operands: Vec<BytecodeOperand>,
users: Vec<BytecodeOperand>,
}
impl BytecodeInstruction {
pub(crate) fn synthetic_jump(block: BytecodeBlockId, target: BytecodeBlockId) -> Self {
Self {
pc: InstructionPc::new(usize::MAX),
opcode: Opcode::Jump,
line: 0,
block,
operands: vec![BytecodeOperand::Block(target)],
users: Vec::new(),
}
}
pub fn pc(&self) -> InstructionPc {
self.pc
}
pub fn opcode(&self) -> Opcode {
self.opcode
}
pub fn line(&self) -> u32 {
self.line
}
pub fn block(&self) -> BytecodeBlockId {
self.block
}
pub fn operands(&self) -> &[BytecodeOperand] {
&self.operands
}
pub fn users(&self) -> &[BytecodeOperand] {
&self.users
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum BytecodeOperand {
Immediate(BytecodeImmediateId),
Instruction(BytecodeInstructionId),
Block(BytecodeBlockId),
Phi(BytecodePhiId),
Projection(BytecodeProjectionId),
VmRegister(Register),
VmConstant(ConstantIndex),
VmUpvalue(u32),
VmProto(u32),
}
bytecode_handle_id!(pub BytecodeImmediateId);
bytecode_handle_id!(pub BytecodePhiId);
bytecode_handle_id!(pub BytecodeProjectionId);
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum BytecodeImmediate {
Boolean(bool),
Int(i32),
Import(u32),
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct BytecodePhi {
operands: Vec<BytecodeOperand>,
users: Vec<BytecodeOperand>,
}
impl BytecodePhi {
pub fn operands(&self) -> &[BytecodeOperand] {
&self.operands
}
pub fn users(&self) -> &[BytecodeOperand] {
&self.users
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct BytecodeProjection {
pub source: BytecodeOperand,
pub index: u32,
}
fn connect_blocks(
blocks: &mut [BytecodeBlock],
source: BytecodeBlockId,
target: BytecodeBlockId,
kind: BytecodeEdgeKind,
) {
blocks[source.index()]
.successors
.push(BytecodeEdge::new(kind, target));
blocks[target.index()]
.predecessors
.push(BytecodeEdge::new(kind, source));
}