mod branch_merge;
mod param_alias;
mod rewrite;
use std::collections::{BTreeMap, BTreeSet};
use super::temp_touch::{
TempRefScopeTracker, TempTouchIndex, collect_temp_refs_by_stmt, expr_touches_any_temp,
stmt_consumes_temps_only_in_control_head, stmt_contains_nested_nonlocal_control,
};
use crate::hir::common::{
HirAssign, HirBlock, HirExpr, HirLValue, HirLocalDecl, HirProto, HirStmt, LocalId, TempId,
};
use crate::hir::promotion::{HomeSlotKey, ProtoPromotionFacts};
pub(super) fn promote_temps_to_locals_in_proto_with_facts(
proto: &mut HirProto,
facts: &ProtoPromotionFacts,
) -> bool {
let mut next_local_index = proto.locals.len();
let mut new_locals = Vec::new();
let mut new_local_debug_hints = Vec::new();
let mut ctx = PromotionCtx {
facts,
temp_debug_locals: &proto.temp_debug_locals,
next_local_index: &mut next_local_index,
new_locals: &mut new_locals,
new_local_debug_hints: &mut new_local_debug_hints,
};
let result = promote_block(
&mut ctx,
&mut proto.body,
&BTreeMap::new(),
&BTreeMap::new(),
&BTreeSet::new(),
);
proto.locals.extend(new_locals);
proto.local_debug_hints.extend(new_local_debug_hints);
let alias_changed = param_alias::coalesce_param_aliases_in_proto(proto);
result.changed || alias_changed
}
#[derive(Debug, Clone)]
struct PromotionPlan {
decl_index: usize,
local: LocalId,
home_slot: Option<HomeSlotKey>,
temps: BTreeSet<TempId>,
removable_aliases: BTreeSet<usize>,
init: PromotionInit,
action: PromotionAction,
}
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum PromotionInit {
FromAssign,
Empty,
}
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum PromotionAction {
AllocateLocal,
ReuseExistingLocal,
}
struct PromotionResult {
changed: bool,
trailing_mapping: BTreeMap<TempId, LocalId>,
}
struct PromotionCtx<'a> {
facts: &'a ProtoPromotionFacts,
temp_debug_locals: &'a [Option<String>],
next_local_index: &'a mut usize,
new_locals: &'a mut Vec<LocalId>,
new_local_debug_hints: &'a mut Vec<Option<String>>,
}
struct PlanAllocator<'a> {
temp_debug_locals: &'a [Option<String>],
plans: &'a mut Vec<PromotionPlan>,
reserved_temps: &'a mut BTreeSet<TempId>,
reserved_alias_indices: &'a mut BTreeSet<usize>,
next_local_index: &'a mut usize,
new_locals: &'a mut Vec<LocalId>,
new_local_debug_hints: &'a mut Vec<Option<String>>,
}
impl PlanAllocator<'_> {
fn allocate_local(
&mut self,
decl_index: usize,
home_slot: Option<HomeSlotKey>,
temps: BTreeSet<TempId>,
removable_aliases: BTreeSet<usize>,
init: PromotionInit,
) {
let local = LocalId(*self.next_local_index);
*self.next_local_index += 1;
self.new_locals.push(local);
self.new_local_debug_hints
.push(debug_hint_for_temp_group(self.temp_debug_locals, &temps));
self.reserved_temps.extend(temps.iter().copied());
self.reserved_alias_indices
.extend(removable_aliases.iter().copied());
self.plans.push(PromotionPlan {
decl_index,
local,
home_slot,
temps,
removable_aliases,
init,
action: PromotionAction::AllocateLocal,
});
}
fn reuse_existing_local(
&mut self,
decl_index: usize,
local: LocalId,
home_slot: Option<HomeSlotKey>,
temps: BTreeSet<TempId>,
removable_aliases: BTreeSet<usize>,
init: PromotionInit,
) {
self.reserved_temps.extend(temps.iter().copied());
self.reserved_alias_indices
.extend(removable_aliases.iter().copied());
self.plans.push(PromotionPlan {
decl_index,
local,
home_slot,
temps,
removable_aliases,
init,
action: PromotionAction::ReuseExistingLocal,
});
}
}
fn promote_block(
ctx: &mut PromotionCtx<'_>,
block: &mut HirBlock,
inherited: &BTreeMap<TempId, LocalId>,
inherited_sticky_slots: &BTreeMap<HomeSlotKey, LocalId>,
outer_used_temps: &BTreeSet<TempId>,
) -> PromotionResult {
let stmt_temp_refs = collect_temp_refs_by_stmt(&block.stmts);
let mut temp_refs = TempRefScopeTracker::new(&stmt_temp_refs);
let plans = collect_plans(
ctx,
block,
&stmt_temp_refs,
inherited,
inherited_sticky_slots,
outer_used_temps,
);
let plan_by_decl = plans.iter().fold(
BTreeMap::<usize, Vec<&PromotionPlan>>::new(),
|mut grouped, plan| {
grouped.entry(plan.decl_index).or_default().push(plan);
grouped
},
);
let removable = plans
.iter()
.flat_map(|plan| plan.removable_aliases.iter().copied())
.collect::<BTreeSet<_>>();
let mut changed = !plans.is_empty();
let mut mapping = inherited.clone();
let mut slot_candidates = inherited_sticky_slots.clone();
let mut active_sticky_slots = inherited_sticky_slots.clone();
let original_stmts = std::mem::take(&mut block.stmts);
let mut rewritten = Vec::with_capacity(original_stmts.len());
for (index, mut stmt) in original_stmts.into_iter().enumerate() {
temp_refs.enter_stmt(index);
let mut replaced_stmt = false;
if let Some(plans) = plan_by_decl.get(&index) {
let mapping_before_decl = mapping.clone();
for plan in plans {
if let Some(anchor_stmt) =
rewrite_plan_anchor_stmt(&stmt, plan, &mapping_before_decl)
{
rewritten.push(anchor_stmt);
}
for temp in &plan.temps {
mapping.insert(*temp, plan.local);
}
if let Some(slot) = plan.home_slot
&& matches!(plan.action, PromotionAction::AllocateLocal)
{
slot_candidates.entry(slot).or_insert(plan.local);
}
replaced_stmt |= plan_replaces_original_stmt(plan);
}
}
activate_captured_slots_in_stmt(
&stmt,
ctx.facts,
&slot_candidates,
&mut active_sticky_slots,
);
if replaced_stmt {
temp_refs.leave_stmt(index);
continue;
}
if removable.contains(&index) {
temp_refs.leave_stmt(index);
continue;
}
let child_outer_temps = temp_refs.outer_with_suffix(outer_used_temps);
let stmt_changed = rewrite_stmt(
ctx,
&mut stmt,
&mapping,
&active_sticky_slots,
&child_outer_temps,
);
changed |= stmt_changed;
rewritten.push(stmt);
temp_refs.leave_stmt(index);
}
block.stmts = rewritten;
if mapping.len() > inherited.len() {
for stmt in &mut block.stmts {
rewrite::forward_capture_refs(stmt, &mapping);
}
}
PromotionResult {
changed,
trailing_mapping: mapping,
}
}
fn collect_plans(
ctx: &mut PromotionCtx<'_>,
block: &HirBlock,
stmt_temp_refs: &[BTreeSet<TempId>],
inherited: &BTreeMap<TempId, LocalId>,
inherited_sticky_slots: &BTreeMap<HomeSlotKey, LocalId>,
outer_used_temps: &BTreeSet<TempId>,
) -> Vec<PromotionPlan> {
if block.stmts.iter().any(|stmt| {
matches!(
stmt,
HirStmt::Continue | HirStmt::Goto(_) | HirStmt::Label(_) | HirStmt::Unstructured(_)
)
}) {
return Vec::new();
}
let facts = ctx.facts;
let temp_debug_locals = ctx.temp_debug_locals;
let mut plans = Vec::new();
let temp_touches = TempTouchIndex::new(stmt_temp_refs);
let mut reserved_temps = inherited.keys().copied().collect::<BTreeSet<_>>();
let mut reserved_alias_indices = BTreeSet::new();
let mut slot_candidates = inherited_sticky_slots.clone();
let mut sticky_slots = inherited_sticky_slots.clone();
for (decl_index, stmt) in block.stmts.iter().enumerate() {
if reserved_alias_indices.contains(&decl_index) {
activate_captured_slots_in_stmt(stmt, facts, &slot_candidates, &mut sticky_slots);
continue;
}
let mut sticky_slots_for_stmt = sticky_slots.clone();
activate_captured_slots_in_stmt(stmt, facts, &slot_candidates, &mut sticky_slots_for_stmt);
let Some(root_temp) = simple_temp_assign_target(stmt) else {
sticky_slots = sticky_slots_for_stmt;
continue;
};
if reserved_temps.contains(&root_temp) {
sticky_slots = sticky_slots_for_stmt;
continue;
}
if temp_touches.touches_before(decl_index, root_temp) {
sticky_slots = sticky_slots_for_stmt;
continue;
}
if outer_used_temps.contains(&root_temp) {
sticky_slots = sticky_slots_for_stmt;
continue;
}
if stmt_self_updates_temp(stmt, root_temp) {
sticky_slots = sticky_slots_for_stmt;
continue;
}
let mut group = BTreeSet::from([root_temp]);
let mut removable_aliases = BTreeSet::new();
let mut has_future_touch = false;
for future_index in decl_index + 1..block.stmts.len() {
if removable_aliases.contains(&future_index) {
continue;
}
let future_stmt = &block.stmts[future_index];
if let Some(alias_temp) = alias_temp_for_group(future_stmt, &group)
&& !reserved_temps.contains(&alias_temp)
&& !group.contains(&alias_temp)
&& !temp_touches.touches_in_range(decl_index + 1, future_index, alias_temp)
{
group.insert(alias_temp);
removable_aliases.insert(future_index);
continue;
}
if temp_touches.stmt_touches_any(future_index, &group) {
has_future_touch = true;
}
}
let sticky_local = facts
.home_slot(root_temp)
.and_then(|slot| sticky_slots_for_stmt.get(&slot).copied());
if sticky_local.is_none() && !has_future_touch {
sticky_slots = sticky_slots_for_stmt;
continue;
}
if sticky_local.is_none() {
let touching_stmt_indices = (decl_index + 1..block.stmts.len())
.filter(|future_index| !removable_aliases.contains(future_index))
.filter(|future_index| temp_touches.stmt_touches_any(*future_index, &group))
.collect::<Vec<_>>();
if touching_stmt_indices.len() == 1
&& (stmt_consumes_temps_only_in_control_head(
&block.stmts[touching_stmt_indices[0]],
&group,
) || single_use_seed_can_stay_temp(
stmt,
root_temp,
&block.stmts[touching_stmt_indices[0]],
))
{
sticky_slots = sticky_slots_for_stmt;
continue;
}
if touching_stmt_indices
.iter()
.copied()
.any(|stmt_index| stmt_contains_nested_nonlocal_control(&block.stmts[stmt_index]))
{
sticky_slots = sticky_slots_for_stmt;
continue;
}
}
let mut allocator = PlanAllocator {
temp_debug_locals,
plans: &mut plans,
reserved_temps: &mut reserved_temps,
reserved_alias_indices: &mut reserved_alias_indices,
next_local_index: ctx.next_local_index,
new_locals: ctx.new_locals,
new_local_debug_hints: ctx.new_local_debug_hints,
};
if let Some(local) = sticky_local {
allocator.reuse_existing_local(
decl_index,
local,
facts.home_slot(root_temp),
group.clone(),
removable_aliases,
PromotionInit::FromAssign,
);
} else {
let slot = facts.home_slot(root_temp);
allocator.allocate_local(
decl_index,
slot,
group.clone(),
removable_aliases,
PromotionInit::FromAssign,
);
if let Some(slot) = slot
&& let Some(local) = allocator.plans.last().map(|plan| plan.local)
{
slot_candidates.entry(slot).or_insert(local);
}
}
sticky_slots = sticky_slots_for_stmt;
}
let mut sticky_slots = inherited_sticky_slots.clone();
for (decl_index, stmt) in block.stmts.iter().enumerate() {
let merge_temps =
branch_merge::candidate_temps(stmt, &temp_touches, decl_index, &reserved_temps);
for temp in merge_temps {
let mut allocator = PlanAllocator {
temp_debug_locals,
plans: &mut plans,
reserved_temps: &mut reserved_temps,
reserved_alias_indices: &mut reserved_alias_indices,
next_local_index: ctx.next_local_index,
new_locals: ctx.new_locals,
new_local_debug_hints: ctx.new_local_debug_hints,
};
if let Some(local) = facts
.home_slot(temp)
.and_then(|slot| sticky_slots.get(&slot).copied())
{
allocator.reuse_existing_local(
decl_index,
local,
facts.home_slot(temp),
BTreeSet::from([temp]),
BTreeSet::new(),
PromotionInit::Empty,
);
} else {
let slot = facts.home_slot(temp);
allocator.allocate_local(
decl_index,
slot,
BTreeSet::from([temp]),
BTreeSet::new(),
PromotionInit::Empty,
);
if let Some(slot) = slot
&& let Some(local) = allocator.plans.last().map(|plan| plan.local)
{
slot_candidates.entry(slot).or_insert(local);
}
}
}
activate_captured_slots_in_stmt(stmt, facts, &slot_candidates, &mut sticky_slots);
}
plans
}
fn activate_captured_slots_in_stmt(
stmt: &HirStmt,
facts: &ProtoPromotionFacts,
slot_candidates: &BTreeMap<HomeSlotKey, LocalId>,
sticky_slots: &mut BTreeMap<HomeSlotKey, LocalId>,
) {
let mut captured_slots = BTreeSet::new();
facts.collect_captured_home_slots_in_stmt(stmt, &mut captured_slots);
for slot in captured_slots {
if let Some(local) = slot_candidates.get(&slot).copied() {
sticky_slots.insert(slot, local);
}
}
}
fn simple_temp_assign_target(stmt: &HirStmt) -> Option<TempId> {
let HirStmt::Assign(assign) = stmt else {
return None;
};
let [HirLValue::Temp(temp)] = assign.targets.as_slice() else {
return None;
};
let [_value] = assign.values.as_slice() else {
return None;
};
Some(*temp)
}
fn alias_temp_for_group(stmt: &HirStmt, group: &BTreeSet<TempId>) -> Option<TempId> {
let HirStmt::Assign(assign) = stmt else {
return None;
};
let [HirLValue::Temp(alias)] = assign.targets.as_slice() else {
return None;
};
let [HirExpr::TempRef(source)] = assign.values.as_slice() else {
return None;
};
group.contains(source).then_some(*alias)
}
fn stmt_self_updates_temp(stmt: &HirStmt, temp: TempId) -> bool {
let HirStmt::Assign(assign) = stmt else {
return false;
};
matches!(assign.targets.as_slice(), [HirLValue::Temp(id)] if *id == temp)
&& assign
.values
.iter()
.any(|value| expr_touches_any_temp(value, &BTreeSet::from([temp])))
}
fn single_use_seed_can_stay_temp(def_stmt: &HirStmt, temp: TempId, use_stmt: &HirStmt) -> bool {
let Some(value) = single_temp_assign_value(def_stmt, temp) else {
return false;
};
match value {
HirExpr::GlobalRef(_) => stmt_uses_temp_as_assign_table_base(use_stmt, temp),
HirExpr::String(_) => stmt_uses_temp_as_assign_call_arg(use_stmt, temp),
_ => false,
}
}
fn single_temp_assign_value(stmt: &HirStmt, temp: TempId) -> Option<&HirExpr> {
let HirStmt::Assign(assign) = stmt else {
return None;
};
let [HirLValue::Temp(target)] = assign.targets.as_slice() else {
return None;
};
let [value] = assign.values.as_slice() else {
return None;
};
if *target != temp {
return None;
}
Some(value)
}
fn stmt_uses_temp_as_assign_table_base(stmt: &HirStmt, temp: TempId) -> bool {
let HirStmt::Assign(assign) = stmt else {
return false;
};
assign
.targets
.iter()
.any(|target| lvalue_uses_temp_as_table_base(target, temp))
}
fn lvalue_uses_temp_as_table_base(lvalue: &HirLValue, temp: TempId) -> bool {
let HirLValue::TableAccess(access) = lvalue else {
return false;
};
expr_is_temp_ref(&access.base, temp) || expr_uses_temp_as_table_access_base(&access.base, temp)
}
fn stmt_uses_temp_as_assign_call_arg(stmt: &HirStmt, temp: TempId) -> bool {
let HirStmt::Assign(assign) = stmt else {
return false;
};
assign
.values
.iter()
.any(|value| expr_uses_temp_as_call_arg(value, temp))
}
fn expr_uses_temp_as_call_arg(expr: &HirExpr, temp: TempId) -> bool {
match expr {
HirExpr::Call(call) => call.args.iter().any(|arg| expr_is_temp_ref(arg, temp)),
HirExpr::TableAccess(access) => {
expr_uses_temp_as_call_arg(&access.base, temp)
|| expr_uses_temp_as_call_arg(&access.key, temp)
}
_ => false,
}
}
fn expr_uses_temp_as_table_access_base(expr: &HirExpr, temp: TempId) -> bool {
let HirExpr::TableAccess(access) = expr else {
return false;
};
expr_is_temp_ref(&access.base, temp) || expr_uses_temp_as_table_access_base(&access.base, temp)
}
fn expr_is_temp_ref(expr: &HirExpr, temp: TempId) -> bool {
matches!(expr, HirExpr::TempRef(other) if *other == temp)
}
fn rewrite_plan_anchor_stmt(
stmt: &HirStmt,
plan: &PromotionPlan,
mapping: &BTreeMap<TempId, LocalId>,
) -> Option<HirStmt> {
let values = match plan.init {
PromotionInit::FromAssign => {
let HirStmt::Assign(assign) = stmt else {
return None;
};
let [HirLValue::Temp(_temp)] = assign.targets.as_slice() else {
return None;
};
assign
.values
.iter()
.cloned()
.map(|mut expr| {
rewrite::expr(&mut expr, mapping);
expr
})
.collect::<Vec<_>>()
}
PromotionInit::Empty => Vec::new(),
};
match (plan.action, plan.init) {
(PromotionAction::AllocateLocal, _) => Some(HirStmt::LocalDecl(Box::new(HirLocalDecl {
bindings: vec![plan.local],
values,
}))),
(PromotionAction::ReuseExistingLocal, PromotionInit::FromAssign) => {
Some(HirStmt::Assign(Box::new(HirAssign {
targets: vec![HirLValue::Local(plan.local)],
values,
})))
}
(PromotionAction::ReuseExistingLocal, PromotionInit::Empty) => None,
}
}
fn plan_replaces_original_stmt(plan: &PromotionPlan) -> bool {
matches!(plan.init, PromotionInit::FromAssign)
}
fn rewrite_stmt(
ctx: &mut PromotionCtx<'_>,
stmt: &mut HirStmt,
mapping: &BTreeMap<TempId, LocalId>,
sticky_slots: &BTreeMap<HomeSlotKey, LocalId>,
outer_used_temps: &BTreeSet<TempId>,
) -> bool {
match stmt {
HirStmt::LocalDecl(local_decl) => {
let mut changed = false;
for expr in &mut local_decl.values {
changed |= rewrite::expr(expr, mapping);
}
changed
}
HirStmt::Assign(assign) => {
let mut targets_changed = false;
for target in &mut assign.targets {
targets_changed |= rewrite::lvalue(target, mapping);
}
let mut values_changed = false;
for expr in &mut assign.values {
values_changed |= rewrite::expr(expr, mapping);
}
targets_changed || values_changed
}
HirStmt::TableSetList(set_list) => {
let base_changed = rewrite::expr(&mut set_list.base, mapping);
let mut values_changed = false;
for expr in &mut set_list.values {
values_changed |= rewrite::expr(expr, mapping);
}
let trailing_changed = set_list
.trailing_multivalue
.as_mut()
.is_some_and(|expr| rewrite::expr(expr, mapping));
base_changed || values_changed || trailing_changed
}
HirStmt::ErrNil(err_nil) => rewrite::expr(&mut err_nil.value, mapping),
HirStmt::ToBeClosed(to_be_closed) => rewrite::expr(&mut to_be_closed.value, mapping),
HirStmt::CallStmt(call_stmt) => rewrite::call_expr(&mut call_stmt.call, mapping),
HirStmt::Return(ret) => {
let mut changed = false;
for expr in &mut ret.values {
changed |= rewrite::expr(expr, mapping);
}
changed
}
HirStmt::If(if_stmt) => {
let cond_changed = rewrite::expr(&mut if_stmt.cond, mapping);
let then_changed = promote_block(
ctx,
&mut if_stmt.then_block,
mapping,
sticky_slots,
outer_used_temps,
)
.changed;
let else_changed = if_stmt.else_block.as_mut().is_some_and(|else_block| {
promote_block(ctx, else_block, mapping, sticky_slots, outer_used_temps).changed
});
cond_changed || then_changed || else_changed
}
HirStmt::While(while_stmt) => {
let cond_changed = rewrite::expr(&mut while_stmt.cond, mapping);
let body_changed = promote_block(
ctx,
&mut while_stmt.body,
mapping,
sticky_slots,
outer_used_temps,
)
.changed;
cond_changed || body_changed
}
HirStmt::Repeat(repeat_stmt) => {
let body_result = promote_block(
ctx,
&mut repeat_stmt.body,
mapping,
sticky_slots,
outer_used_temps,
);
let cond_changed = rewrite::expr(&mut repeat_stmt.cond, &body_result.trailing_mapping);
body_result.changed || cond_changed
}
HirStmt::NumericFor(numeric_for) => {
let start_changed = rewrite::expr(&mut numeric_for.start, mapping);
let limit_changed = rewrite::expr(&mut numeric_for.limit, mapping);
let step_changed = rewrite::expr(&mut numeric_for.step, mapping);
let body_changed = promote_block(
ctx,
&mut numeric_for.body,
mapping,
sticky_slots,
outer_used_temps,
)
.changed;
start_changed || limit_changed || step_changed || body_changed
}
HirStmt::GenericFor(generic_for) => {
let mut iterator_changed = false;
for expr in &mut generic_for.iterator {
iterator_changed |= rewrite::expr(expr, mapping);
}
let body_changed = promote_block(
ctx,
&mut generic_for.body,
mapping,
sticky_slots,
outer_used_temps,
)
.changed;
iterator_changed || body_changed
}
HirStmt::Block(block) => {
promote_block(ctx, block, mapping, sticky_slots, outer_used_temps).changed
}
HirStmt::Unstructured(unstructured) => {
promote_block(
ctx,
&mut unstructured.body,
mapping,
sticky_slots,
outer_used_temps,
)
.changed
}
HirStmt::Break
| HirStmt::Close(_)
| HirStmt::Continue
| HirStmt::Goto(_)
| HirStmt::Label(_) => false,
}
}
fn debug_hint_for_temp_group(
temp_debug_locals: &[Option<String>],
temps: &BTreeSet<TempId>,
) -> Option<String> {
temps
.iter()
.find_map(|temp| temp_debug_locals.get(temp.index()).cloned().flatten())
}