use petgraph::{algo::dominators::Dominators, graph::NodeIndex};
use std::collections::{BTreeMap, HashMap, HashSet};
use crate::compiler::ir::instruction::Variable;
use crate::compiler::ir::{BlockId, ControlFlowGraph, Instruction, Value};
type VersionStack = HashMap<Variable, Vec<Variable>>;
type BlockVarVersions = HashMap<BlockId, HashMap<Variable, Variable>>;
#[derive(Debug)]
struct VariableInfo {
defs: Vec<(BlockId, usize)>, uses: Vec<(BlockId, usize)>, }
impl VariableInfo {
pub fn new() -> Self {
Self {
defs: Vec::new(),
uses: Vec::new(),
}
}
}
pub struct SSABuilder<'a> {
cfg: &'a mut ControlFlowGraph,
dominators: Dominators<NodeIndex>,
throw_to_handlers: HashMap<BlockId, Vec<BlockId>>,
}
impl<'a> SSABuilder<'a> {
pub fn new(cfg: &'a mut ControlFlowGraph) -> Self {
let dominators = cfg.dominators();
Self {
cfg,
dominators,
throw_to_handlers: HashMap::new(),
}
}
pub fn convert_to_ssa(&mut self) {
self.add_exception_edges_for_throws();
self.dominators = self.cfg.dominators();
let var_info = self.collect_var_def_and_use();
let dominance_frontier = self.cfg.dominance_frontier(&self.dominators);
let phi_placements = self.determine_phi_nodes(&var_info, &dominance_frontier);
let block_phi_vars = Self::build_block_phi_vars(&phi_placements);
self.add_phi_parameters(&block_phi_vars);
let block_var_versions = self.rename_variables(&var_info);
self.handle_jump_args(&block_phi_vars, &block_var_versions);
}
fn build_block_phi_vars(
phi_placements: &HashMap<Variable, Vec<BlockId>>,
) -> BTreeMap<BlockId, Vec<Variable>> {
let mut vars: Vec<Variable> = phi_placements.keys().copied().collect();
vars.sort_by_key(|var| var.as_usize());
let mut result: BTreeMap<BlockId, Vec<Variable>> = BTreeMap::new();
for var in vars {
for block_id in &phi_placements[&var] {
let entry = result.entry(*block_id).or_default();
if !entry.contains(&var) {
entry.push(var);
}
}
}
result
}
fn add_exception_edges_for_throws(&mut self) {
let mut seh_scope: Vec<(BlockId, Option<BlockId>)> = Vec::new();
let mut throw_edges: Vec<(BlockId, BlockId)> = Vec::new();
let mut finally_outer_scope: HashMap<BlockId, Vec<(BlockId, Option<BlockId>)>> =
HashMap::new();
for block in self.cfg.blocks() {
for inst in block.instructions() {
match inst {
Instruction::PushSeh { handler, finally } => {
if let Some(finally_blk) = finally {
finally_outer_scope.insert(*finally_blk, seh_scope.clone());
}
seh_scope.push((*handler, *finally));
}
Instruction::PopSeh => {
seh_scope.pop();
}
Instruction::Throw { .. } => {
for (catch_handler, finally_handler) in &seh_scope {
throw_edges.push((block.id(), *catch_handler));
if let Some(finally_blk) = finally_handler {
throw_edges.push((block.id(), *finally_blk));
}
}
break;
}
Instruction::ResumeException { .. } => {
if let Some(outer_scope) = finally_outer_scope.get(&block.id()) {
for (catch_handler, _) in outer_scope {
throw_edges.push((block.id(), *catch_handler));
}
}
}
_ => {}
}
}
}
let mut exception_blocks: HashSet<BlockId> = HashSet::new();
for (throw_block, handler) in throw_edges {
let successors = self.cfg.get_successors(throw_block);
if !successors.contains(&handler) {
self.cfg.add_edge(throw_block, handler);
}
}
for block in self.cfg.blocks() {
for inst in block.instructions() {
if matches!(
inst,
Instruction::Throw { .. } | Instruction::ResumeException { .. }
) {
exception_blocks.insert(block.id());
break;
}
}
}
for block_id in exception_blocks {
let successors = self.cfg.get_successors(block_id).clone();
self.throw_to_handlers.insert(block_id, successors);
}
}
fn collect_var_def_and_use(&self) -> HashMap<Variable, VariableInfo> {
let mut map = HashMap::new();
for block in self.cfg.blocks() {
for (idx, inst) in block.instructions().iter().enumerate() {
let (defined, used) = inst.defined_and_used_vars();
for var in defined {
map.entry(var)
.or_insert_with(VariableInfo::new)
.defs
.push((block.id(), idx));
}
for var in used {
map.entry(var)
.or_insert_with(VariableInfo::new)
.uses
.push((block.id(), idx));
}
}
}
map
}
fn determine_phi_nodes(
&self,
var_info: &HashMap<Variable, VariableInfo>,
dominance_frontier: &BTreeMap<BlockId, Vec<BlockId>>,
) -> HashMap<Variable, Vec<BlockId>> {
let mut phi_placements: HashMap<Variable, Vec<BlockId>> = HashMap::new();
for (var, info) in var_info {
if info.defs.len() <= 1 {
continue;
}
let def_blocks: HashSet<BlockId> = info.defs.iter().map(|(block, _)| *block).collect();
let mut worklist: Vec<BlockId> = def_blocks.iter().cloned().collect();
worklist.sort_unstable();
let mut visited = HashSet::new();
while let Some(block) = worklist.pop() {
if let Some(df_blocks) = dominance_frontier.get(&block) {
for &df_block in df_blocks {
if !visited.contains(&df_block) {
visited.insert(df_block);
worklist.push(df_block);
phi_placements.entry(*var).or_default().push(df_block);
}
}
}
}
let mut use_blocks: Vec<BlockId> = info.uses.iter().map(|(block, _)| *block).collect();
use_blocks.sort_unstable();
use_blocks.dedup();
for &use_block in &use_blocks {
let predecessors = self.get_block_predecessors(use_block);
let preds_with_def: Vec<_> = predecessors
.iter()
.filter(|&&pred| {
def_blocks.contains(&pred)
|| phi_placements
.get(var)
.is_some_and(|blocks| blocks.contains(&pred)) })
.collect();
if predecessors.len() > 1 && !preds_with_def.is_empty() && !visited.contains(&use_block) {
visited.insert(use_block);
phi_placements.entry(*var).or_default().push(use_block);
worklist.push(use_block);
}
}
}
for blocks in phi_placements.values_mut() {
blocks.sort_unstable();
blocks.dedup();
}
phi_placements
}
fn add_phi_parameters(&mut self, block_phi_vars: &BTreeMap<BlockId, Vec<Variable>>) {
for (block_id, vars) in block_phi_vars {
for var in vars {
self.cfg.append_block_param(*block_id, *var);
}
}
}
fn handle_jump_args(
&mut self,
block_phi_vars: &BTreeMap<BlockId, Vec<Variable>>,
block_var_versions: &BlockVarVersions,
) {
for (block_id, sorted_vars) in block_phi_vars {
let predecessors = self.cfg.get_precedences(*block_id).clone();
for pred_block_id in predecessors {
let arg_values: Vec<Value> = sorted_vars
.iter()
.map(|phi_var| {
match block_var_versions
.get(&pred_block_id)
.and_then(|pred_vars| pred_vars.get(phi_var).copied())
{
Some(var) => Value::Variable(var),
None => Value::Primitive(crate::bytecode::Primitive::Undefined),
}
})
.collect();
self.add_jump_arguments(pred_block_id, *block_id, &arg_values);
}
}
}
fn add_jump_arguments(
&mut self,
pred_block_id: BlockId,
target_block_id: BlockId,
arg_values: &[Value],
) {
let successors: Vec<BlockId> = self.cfg.get_successors(pred_block_id).clone();
let is_successor = successors.contains(&target_block_id);
if let Some(pred_block) = self.cfg.get_block_mut(pred_block_id) {
for inst in pred_block.instructions_mut().iter_mut() {
match inst {
Instruction::Jump { dst, args } if dst.to_block() == target_block_id => {
args.extend(arg_values.iter().copied());
}
Instruction::BrIf {
true_blk,
false_blk,
true_args,
false_args,
..
} if true_blk.to_block() == target_block_id
|| false_blk.to_block() == target_block_id =>
{
if true_blk.to_block() == target_block_id {
true_args.extend(arg_values.iter().copied());
} else {
false_args.extend(arg_values.iter().copied());
}
}
Instruction::Throw { args, .. } => {
if is_successor && args.is_empty() {
args.extend(arg_values.iter().copied());
}
}
Instruction::ResumeException { args } => {
if is_successor && args.is_empty() {
args.extend(arg_values.iter().copied());
}
}
_ => {}
}
}
}
}
fn get_block_predecessors(&self, block_id: BlockId) -> &Vec<BlockId> {
self.cfg.get_precedences(block_id)
}
fn rename_variables(&mut self, var_info: &HashMap<Variable, VariableInfo>) -> BlockVarVersions {
let mut stacks: VersionStack = HashMap::new();
let mut block_var_versions: BlockVarVersions = HashMap::new();
let entry = self.cfg.entry().unwrap();
self.rename_variables_in_block(entry, &mut stacks, var_info, &mut block_var_versions);
block_var_versions
}
fn rename_variables_in_block(
&mut self,
block_id: BlockId,
stacks: &mut VersionStack,
var_info: &HashMap<Variable, VariableInfo>,
block_var_versions: &mut BlockVarVersions,
) {
let initial_snapshot: HashMap<Variable, Vec<Variable>> = stacks
.iter()
.map(|(var_id, stack)| (*var_id, stack.clone()))
.collect();
self.process_block_parameters(block_id, stacks);
self.process_block_instructions(block_id, stacks);
self.record_block_final_versions(block_id, stacks, block_var_versions);
self.process_child_blocks(block_id, stacks, var_info, block_var_versions);
*stacks = initial_snapshot;
}
fn process_block_parameters(&mut self, block_id: BlockId, stacks: &mut VersionStack) {
let param_var_ids: Vec<Variable> = self.cfg.get_block_params(block_id);
let mut new_versions: HashMap<Variable, Variable> = HashMap::new();
for var_id in ¶m_var_ids {
let new_version = self.cfg.create_variable();
let new_var_id = new_version.to_variable();
new_versions.insert(*var_id, new_var_id);
}
{
let block = self.cfg.get_block_mut(block_id).unwrap();
for param in block.params_mut().iter_mut() {
if let Some(new_version) = new_versions.get(param) {
*param = *new_version;
}
}
}
for (var_id, new_var_id) in new_versions {
stacks.entry(var_id).or_default().push(new_var_id);
}
}
fn process_block_instructions(&mut self, block_id: BlockId, stacks: &mut VersionStack) {
let block = self.cfg.get_block_mut(block_id).unwrap();
let mut instructions: Vec<Instruction> = block.instructions_mut().drain(..).collect();
for inst in instructions.iter_mut() {
let (defined, _) = inst.defined_and_used_vars();
let mut new_versions = HashMap::new();
for var in &defined {
let new_ver = self.cfg.create_variable().to_variable();
new_versions.insert(*var, Value::Variable(new_ver));
}
SSABuilder::rename_instruction(inst, &new_versions, stacks);
for var in &defined {
if let Some(new_ver) = new_versions.get(var)
&& let Value::Variable(var_id) = new_ver
{
stacks.entry(*var).or_default().push(*var_id);
}
}
if matches!(inst, Instruction::Jump { .. } | Instruction::BrIf { .. }) {
for var in defined {
if let Some(stack) = stacks.get_mut(&var) {
stack.pop(); }
}
}
}
let block = self.cfg.get_block_mut(block_id).unwrap();
*block.instructions_mut() = instructions;
}
fn record_block_final_versions(
&self,
block_id: BlockId,
stacks: &VersionStack,
block_var_versions: &mut BlockVarVersions,
) {
for (var_id, stack) in stacks.iter() {
if let Some(¤t_version) = stack.last() {
block_var_versions
.entry(block_id)
.or_default()
.insert(*var_id, current_version);
}
}
}
fn process_child_blocks(
&mut self,
block_id: BlockId,
stacks: &mut VersionStack,
var_info: &HashMap<Variable, VariableInfo>,
block_var_versions: &mut BlockVarVersions,
) {
let block_node = self.cfg.graph_node(block_id);
let child_nodes: Vec<_> = self
.cfg
.graph_node_indices()
.iter()
.cloned()
.filter(|node| self.dominators.immediate_dominator(*node) == Some(block_node))
.collect();
for child_node in child_nodes {
let child_block_id = self.cfg.graph_node_weight(child_node);
let child_snapshot: HashMap<Variable, Vec<Variable>> = stacks
.iter()
.map(|(var_id, stack)| (*var_id, stack.clone()))
.collect();
self.rename_variables_in_block(child_block_id, stacks, var_info, block_var_versions);
*stacks = child_snapshot;
}
}
fn rename_instruction(
inst: &mut Instruction,
new_versions: &HashMap<Variable, Value>,
stacks: &VersionStack,
) {
match inst {
Instruction::LoadArg { dst, .. } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::LoadConst { dst, .. } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::LoadEnv { dst, .. } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::Move { dst, src } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(src, stacks);
}
Instruction::UnaryOp { dst, src, .. } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(src, stacks);
}
Instruction::BinaryOp { dst, lhs, rhs, .. } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(lhs, stacks);
SSABuilder::rename_use(rhs, stacks);
}
Instruction::Call { func, args, result } => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(func, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::CallEx {
callable,
args,
result,
} => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(callable, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::CallNative { func, args, result } => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(func, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::PropertyGet {
dst,
object,
property,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(property, stacks);
}
Instruction::PropertyDelete {
dst,
object,
property,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(property, stacks);
}
Instruction::IndexDelete {
dst,
object,
index,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(index, stacks);
}
Instruction::StoreEnv { name, value } => {
SSABuilder::rename_use(name, stacks);
SSABuilder::rename_use(value, stacks);
}
Instruction::Arguments { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::LoadNewTarget { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::LoadCurrentFunction { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::Yield { dst, src } => {
SSABuilder::rename_definition(dst, new_versions);
if let Some(src) = src {
SSABuilder::rename_use(src, stacks);
}
}
Instruction::IteratorClose { iter } => {
SSABuilder::rename_use(iter, stacks);
}
Instruction::ToString { dst, src } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(src, stacks);
}
Instruction::MakeRest { dst, .. } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::CallSpread {
result,
callee,
this,
args,
} => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(callee, stacks);
SSABuilder::rename_use(this, stacks);
SSABuilder::rename_use(args, stacks);
}
Instruction::NewSpread {
dst,
constructor,
args,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(constructor, stacks);
SSABuilder::rename_use(args, stacks);
}
Instruction::CallSuper {
result,
callee,
this,
args,
} => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(callee, stacks);
SSABuilder::rename_use(this, stacks);
SSABuilder::rename_use(args, stacks);
}
Instruction::PropertySet {
object,
property,
value,
} => {
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(property, stacks);
SSABuilder::rename_use(value, stacks);
}
Instruction::PropertyCall {
object,
property,
args,
result,
} => {
SSABuilder::rename_definition(result, new_versions);
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(property, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::Return { value } => {
if let Some(val) = value {
SSABuilder::rename_use(val, stacks);
}
}
Instruction::Jump { dst, args } => {
SSABuilder::rename_use(dst, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::BrIf {
condition,
true_blk,
false_blk,
true_args,
false_args,
} => {
SSABuilder::rename_use(condition, stacks);
SSABuilder::rename_use(true_blk, stacks);
SSABuilder::rename_use(false_blk, stacks);
for arg in true_args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
for arg in false_args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::MakeIterator { src, dst } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(src, stacks);
}
Instruction::IterateNext {
iter,
item,
has_next,
} => {
SSABuilder::rename_definition(item, new_versions);
SSABuilder::rename_definition(has_next, new_versions);
SSABuilder::rename_use(iter, stacks);
}
Instruction::MakeArray { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::ArrayPush { array, value } => {
SSABuilder::rename_use(array, stacks);
SSABuilder::rename_use(value, stacks);
}
Instruction::ArrayPushSpread { array, src } => {
SSABuilder::rename_use(array, stacks);
SSABuilder::rename_use(src, stacks);
}
Instruction::MakeObject { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::IndexGet { dst, object, index } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(index, stacks);
}
Instruction::IndexSet {
object,
index,
value,
} => {
SSABuilder::rename_use(object, stacks);
SSABuilder::rename_use(index, stacks);
SSABuilder::rename_use(value, stacks);
}
Instruction::Halt { value } => {
if let Some(v) = value {
SSABuilder::rename_use(v, stacks);
}
}
Instruction::PushSeh { .. } => {}
Instruction::PopSeh => {}
Instruction::Throw { value, args } => {
SSABuilder::rename_use(value, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::LoadException { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::ResumeException { .. } => {
}
Instruction::DelayedJump { .. } => {
}
Instruction::TypeOf { dst, src } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(src, stacks);
}
Instruction::TypeOfEnv { dst, name } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(name, stacks);
}
Instruction::New {
dst,
constructor,
args,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(constructor, stacks);
for arg in args.iter_mut() {
SSABuilder::rename_use(arg, stacks);
}
}
Instruction::LoadThis { dst } => {
SSABuilder::rename_definition(dst, new_versions);
}
Instruction::MakeFuncObj { dst, func_id } => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(func_id, stacks);
}
Instruction::MakeArrowFuncObj {
dst,
func_id,
captured_this,
} => {
SSABuilder::rename_definition(dst, new_versions);
SSABuilder::rename_use(func_id, stacks);
SSABuilder::rename_use(captured_this, stacks);
}
Instruction::ClosureVar { name: _, value } => {
SSABuilder::rename_use(value, stacks);
}
}
}
fn rename_definition(var: &mut Value, new_versions: &HashMap<Variable, Value>) {
if let Value::Variable(var_id) = var
&& let Some(new_version) = new_versions.get(var_id)
{
*var = *new_version;
}
}
fn rename_use(var: &mut Value, stacks: &VersionStack) {
if let Value::Variable(var_id) = var
&& let Some(stack) = stacks.get(var_id)
&& let Some(current_version) = stack.last()
{
*var = Value::Variable(*current_version);
}
}
pub fn into_throw_to_handlers(self) -> HashMap<BlockId, Vec<BlockId>> {
self.throw_to_handlers
}
}