use crate::structure::SsaValue;
use super::*;
use crate::hir::expr_safety::expr_observes_eval_order;
use crate::hir::{HirTableField, HirTableKey};
impl<'a, 'b> StructuredBodyLowerer<'a, 'b> {
pub(crate) fn lower_loop(
&mut self,
block: BlockRef,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let candidate = *self.loop_by_header.get(&block)?;
if !candidate.reducible {
return None;
}
match candidate.kind_hint {
LoopKindHint::WhileLike => {
self.lower_while_loop(candidate, stop, stmts, target_overrides)
}
LoopKindHint::WhileTrueLike => {
self.lower_while_true_loop(candidate, stop, stmts, target_overrides)
}
LoopKindHint::RepeatLike => {
self.lower_repeat_loop(candidate, stop, stmts, target_overrides)
}
LoopKindHint::NumericForLike => {
self.try_lower_numeric_for_init(block, stop, stmts, target_overrides)
}
LoopKindHint::GenericForLike => {
self.try_lower_generic_for_preheader(block, stop, stmts, target_overrides)
}
LoopKindHint::Unknown => {
self.lower_unknown_retry_loop(candidate, stop, stmts, target_overrides)
}
}
}
fn lower_unknown_retry_loop(
&mut self,
candidate: &LoopCandidate,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
if candidate.exits.is_empty() {
return self.lower_infinite_unknown_loop(candidate, stop, stmts, target_overrides);
}
if candidate.exits.len() != 1 {
return None;
}
let post_loop = candidate.exits.iter().next().copied()?;
if let Some(stop) = stop
&& stop != post_loop
&& candidate.blocks.contains(&stop)
{
return None;
}
let preheader = unique_loop_preheader(candidate);
let plan =
self.build_loop_state_plan(candidate, preheader, post_loop, &[], target_overrides)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut loop_context = self.build_active_loop_context(
candidate,
post_loop,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.continue_target = Some(candidate.header);
loop_context.continue_sources.clear();
loop_context.state_slots = plan.states.clone();
self.active_loops.push(loop_context.clone());
let body = self.lower_region_with_suppressed_loop(
candidate.header,
Some(post_loop),
&combined_target_overrides,
Some(candidate.header),
)?;
self.active_loops.pop();
stmts.extend(loop_state_init_stmts(&plan));
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, post_loop, &plan, target_overrides);
stmts.push(HirStmt::While(Box::new(HirWhile {
cond: HirExpr::Boolean(true),
body,
})));
Some(Some(post_loop))
}
fn lower_infinite_unknown_loop(
&mut self,
candidate: &LoopCandidate,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
if let Some(stop) = stop
&& candidate.blocks.contains(&stop)
{
return None;
}
let preheader = unique_loop_preheader(candidate);
let post_loop = self.lowering.cfg.exit_block;
let plan =
self.build_loop_state_plan(candidate, preheader, post_loop, &[], target_overrides)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut loop_context = self.build_active_loop_context(
candidate,
post_loop,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.continue_target = Some(candidate.header);
loop_context.continue_sources.clear();
loop_context.state_slots = plan.states.clone();
self.active_loops.push(loop_context.clone());
let body = self.lower_region_with_suppressed_loop(
candidate.header,
None,
&combined_target_overrides,
Some(candidate.header),
)?;
self.active_loops.pop();
stmts.extend(loop_state_init_stmts(&plan));
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, post_loop, &plan, target_overrides);
stmts.push(HirStmt::While(Box::new(HirWhile {
cond: HirExpr::Boolean(true),
body,
})));
Some(None)
}
fn lower_while_loop(
&mut self,
candidate: &LoopCandidate,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let preheader = unique_loop_preheader(candidate);
let (body_entry, branch_exit) =
loop_branch_body_and_exit(self.lowering, candidate.header, &candidate.blocks)?;
let exit = branch_exit;
if let Some(stop) = stop
&& stop != exit
&& candidate.blocks.contains(&stop)
{
return None;
}
let plan = self.build_loop_state_plan(candidate, preheader, exit, &[], target_overrides)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut loop_context = self.build_active_loop_context(
candidate,
exit,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.state_slots = plan.states.clone();
stmts.extend(loop_state_init_stmts(&plan));
self.visited.insert(candidate.header);
self.install_loop_exit_bindings(candidate, exit, &plan, target_overrides);
self.active_loops.push(loop_context.clone());
let body = self.lower_region(
body_entry,
Some(candidate.header),
&combined_target_overrides,
)?;
self.active_loops.pop();
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
if let Some(continue_target) = loop_context.continue_target {
self.visited.insert(continue_target);
}
let mut cond = self.lower_branch_cond_for_target(candidate.header, body_entry)?;
let (mut cond_expr_overrides, all_prefix_temps) =
self.block_prefix_temp_expr_overrides(candidate.header);
let condition_prefix_temps = self.block_condition_prefix_temps(candidate.header);
let header_prefix_must_stay_in_body = self
.header_prefix_has_live_non_condition_defs(candidate.header, &condition_prefix_temps);
self.remove_reordered_condition_prefix_overrides(
candidate.header,
&cond,
&mut cond_expr_overrides,
);
cond_expr_overrides.extend(temp_expr_overrides(&combined_target_overrides));
rewrite_expr_temps(&mut cond, &cond_expr_overrides);
let unresolvable_prefix_temps: BTreeSet<TempId> = all_prefix_temps
.into_iter()
.filter(|t| !cond_expr_overrides.contains_key(t))
.collect();
if header_prefix_must_stay_in_body
|| expr_has_temp_ref_in(&cond, &unresolvable_prefix_temps)
{
let prefix =
self.lower_block_prefix(candidate.header, true, &combined_target_overrides)?;
let break_cond = cond.negate();
let mut full_body = prefix;
full_body.push(HirStmt::If(Box::new(HirIf {
cond: break_cond,
then_block: HirBlock {
stmts: vec![HirStmt::Break],
},
else_block: None,
})));
full_body.extend(body.stmts);
stmts.push(HirStmt::While(Box::new(HirWhile {
cond: HirExpr::Boolean(true),
body: HirBlock { stmts: full_body },
})));
} else {
stmts.push(HirStmt::While(Box::new(HirWhile { cond, body })));
}
Some(Some(exit))
}
fn remove_reordered_condition_prefix_overrides(
&self,
header: BlockRef,
cond: &HirExpr,
expr_overrides: &mut BTreeMap<TempId, HirExpr>,
) {
let def_order = self.block_prefix_temp_def_order(header);
let mut last_order = None;
let mut reordered = false;
for temp in temp_refs_in_eval_order(cond) {
let Some(expr) = expr_overrides.get(&temp) else {
continue;
};
if !expr_observes_eval_order(expr) {
continue;
}
let Some(order) = def_order.get(&temp).copied() else {
continue;
};
if last_order.is_some_and(|last| order < last) {
reordered = true;
break;
}
last_order = Some(order);
}
if reordered {
expr_overrides.retain(|_, expr| !expr_observes_eval_order(expr));
}
}
fn lower_while_true_loop(
&mut self,
candidate: &LoopCandidate,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let continue_target = candidate.continue_target?;
if let Some(stop) = stop
&& candidate.blocks.contains(&stop)
&& stop != continue_target
{
return None;
}
if self
.lowering
.cfg
.unique_reachable_successor(continue_target)
!= Some(candidate.header)
{
return None;
}
if candidate
.exits
.iter()
.any(|exit| !block_is_terminal_exit(self.lowering, *exit))
{
return None;
}
let preheader = unique_loop_preheader(candidate);
let post_loop = self.lowering.cfg.exit_block;
let plan =
self.build_loop_state_plan(candidate, preheader, post_loop, &[], target_overrides)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut loop_context = self.build_active_loop_context(
candidate,
post_loop,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.state_slots = plan.states.clone();
self.active_loops.push(loop_context.clone());
let mut body = self
.lower_region_with_suppressed_loop(
candidate.header,
Some(continue_target),
&combined_target_overrides,
Some(candidate.header),
)?
.stmts;
body.extend(self.lower_block_prefix(continue_target, false, &combined_target_overrides)?);
self.active_loops.pop();
stmts.extend(loop_state_init_stmts(&plan));
self.visited.insert(continue_target);
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, post_loop, &plan, target_overrides);
stmts.push(HirStmt::While(Box::new(HirWhile {
cond: HirExpr::Boolean(true),
body: HirBlock { stmts: body },
})));
Some(None)
}
fn block_condition_prefix_temps(&self, block: BlockRef) -> BTreeSet<TempId> {
let Some((branch_ref, LowInstr::Branch(_))) = self.block_terminator(block) else {
return BTreeSet::new();
};
let range = self.lowering.cfg.blocks[block.index()].instrs;
let prefix_start = range.start.index();
let prefix_end = branch_ref.index();
let mut temps = BTreeSet::new();
let mut seen_defs = BTreeSet::new();
let mut pending_defs = self
.lowering
.dataflow
.use_values_at(branch_ref)
.values()
.flat_map(|values| values.iter())
.filter_map(|value| match value {
SsaValue::Def(def) => Some(def),
SsaValue::Phi(_) => None,
})
.collect::<Vec<_>>();
while let Some(def) = pending_defs.pop() {
if !seen_defs.insert(def) {
continue;
}
let def_instr = self.lowering.dataflow.def_instr(def);
if (prefix_start..prefix_end).contains(&def_instr.index()) {
temps.insert(self.lowering.bindings.fixed_temps[def.index()]);
}
for values in self.lowering.dataflow.use_values_at(def_instr).values() {
pending_defs.extend(values.iter().filter_map(|value| match value {
SsaValue::Def(upstream) => Some(upstream),
SsaValue::Phi(_) => None,
}));
}
}
temps
}
fn header_prefix_has_live_non_condition_defs(
&self,
block: BlockRef,
condition_prefix_temps: &BTreeSet<TempId>,
) -> bool {
let Some((terminator_ref, LowInstr::Branch(_))) = self.block_terminator(block) else {
return false;
};
let range = self.lowering.cfg.blocks[block.index()].instrs;
let live_out = self.lowering.dataflow.live_out_regs(block);
for instr_index in range.start.index()..terminator_ref.index() {
let instr_ref = InstrRef(instr_index);
if self.overrides.instr_is_suppressed(instr_ref) {
continue;
}
for def in &self.lowering.dataflow.instr_defs[instr_index] {
let temp = self.lowering.bindings.fixed_temps[def.index()];
if condition_prefix_temps.contains(&temp) {
continue;
}
if live_out.contains(&self.lowering.dataflow.def_reg(*def)) {
return true;
}
}
}
false
}
fn lower_repeat_loop(
&mut self,
candidate: &LoopCandidate,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let preheader = unique_loop_preheader(candidate);
let continue_block = candidate.continue_target?;
let (loop_backedge_target, exit) =
loop_branch_body_and_exit(self.lowering, continue_block, &candidate.blocks)?;
if let Some(stop) = stop
&& stop != exit
&& candidate.blocks.contains(&stop)
{
return None;
}
let plan = self.build_loop_state_plan(candidate, preheader, exit, &[], target_overrides)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut loop_context = self.build_active_loop_context(
candidate,
exit,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.state_slots = plan.states.clone();
let backedge_pad = self.repeat_backedge_pad(
candidate.header,
loop_backedge_target,
&combined_target_overrides,
)?;
let suppressed = plan
.states
.iter()
.filter_map(|state| state.phi_id)
.collect::<Vec<_>>();
for phi_id in &suppressed {
self.overrides.suppress_phi(*phi_id);
}
self.active_loops.push(loop_context.clone());
let mut body = self
.lower_region_with_suppressed_loop(
candidate.header,
Some(continue_block),
&combined_target_overrides,
Some(candidate.header),
)?
.stmts;
body.extend(self.lower_block_prefix(continue_block, true, &combined_target_overrides)?);
self.active_loops.pop();
for phi_id in suppressed {
self.overrides.unsuppress_phi(phi_id);
}
stmts.extend(loop_state_init_stmts(&plan));
self.visited.insert(continue_block);
if let Some(backedge_pad) = backedge_pad {
self.visited.insert(backedge_pad);
}
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, exit, &plan, target_overrides);
stmts.push(HirStmt::Repeat(Box::new(HirRepeat {
body: HirBlock { stmts: body },
cond: {
let mut cond = self.lower_branch_cond_for_target(continue_block, exit)?;
rewrite_expr_temps(&mut cond, &temp_expr_overrides(&combined_target_overrides));
cond
},
})));
Some(Some(exit))
}
pub(crate) fn try_lower_numeric_for_init(
&mut self,
block: BlockRef,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let (instr_ref, instr) = self.block_terminator(block)?;
let LowInstr::NumericForInit(init) = instr else {
return None;
};
let init = *init;
let header = self.lowering.cfg.instr_to_block[init.body_target.index()];
let candidate = *self.loop_by_header.get(&header)?;
if !candidate.reducible || candidate.kind_hint != LoopKindHint::NumericForLike {
return None;
}
let exit = self.lowering.cfg.instr_to_block[init.exit_target.index()];
if !candidate.exits.contains(&exit) {
return None;
}
if let Some(stop) = stop
&& stop != exit
&& candidate.blocks.contains(&stop)
{
return None;
}
let binding = self
.lowering
.bindings
.numeric_for_locals
.get(&header)
.copied()?;
let plan = self.build_loop_state_plan(
candidate,
Some(block),
exit,
&[init.index],
target_overrides,
)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
let mut suppressed = plan
.states
.iter()
.filter_map(|state| state.phi_id)
.collect::<Vec<_>>();
suppressed.extend(
Self::header_values(candidate)
.filter(|value| value.reg == init.index)
.map(|value| value.phi_id),
);
self.visited.insert(block);
stmts.extend(self.lower_block_prefix(block, false, target_overrides)?);
stmts.extend(loop_state_init_stmts(&plan));
for phi_id in &suppressed {
self.overrides.suppress_phi(*phi_id);
}
let continue_block = candidate.continue_target.unwrap_or(header);
let mut loop_context = self.build_active_loop_context(
candidate,
exit,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.state_slots = plan.states.clone();
self.active_loops.push(loop_context.clone());
let body = if continue_block == header {
let stmts = self.lower_block_prefix(header, false, &combined_target_overrides)?;
HirBlock { stmts }
} else {
let mut stmts = self
.lower_region_with_suppressed_loop(
header,
Some(continue_block),
&combined_target_overrides,
Some(header),
)?
.stmts;
let prefix =
self.lower_block_prefix(continue_block, false, &combined_target_overrides)?;
stmts.extend(prefix);
HirBlock { stmts }
};
self.active_loops.pop();
for phi_id in suppressed {
self.overrides.unsuppress_phi(phi_id);
}
self.visited.insert(continue_block);
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, exit, &plan, target_overrides);
let mut start = expr_for_reg_use(self.lowering, block, instr_ref, init.index);
let mut limit = expr_for_reg_use(self.lowering, block, instr_ref, init.limit);
let mut step = expr_for_reg_use(self.lowering, block, instr_ref, init.step);
if !target_overrides.is_empty() {
let expr_overrides = temp_expr_overrides(target_overrides);
rewrite_expr_temps(&mut start, &expr_overrides);
rewrite_expr_temps(&mut limit, &expr_overrides);
rewrite_expr_temps(&mut step, &expr_overrides);
}
stmts.push(HirStmt::NumericFor(Box::new(HirNumericFor {
binding,
start,
limit,
step,
body,
})));
Some(Some(exit))
}
pub(crate) fn try_lower_generic_for_preheader(
&mut self,
block: BlockRef,
stop: Option<BlockRef>,
stmts: &mut Vec<HirStmt>,
target_overrides: &BTreeMap<TempId, HirLValue>,
) -> Option<Option<BlockRef>> {
let header = self.lowering.cfg.unique_reachable_successor(block)?;
let candidate = self.loop_by_header.get(&header).copied()?;
if !candidate.reducible
|| candidate.kind_hint != LoopKindHint::GenericForLike
|| candidate.continue_target != Some(header)
|| unique_loop_preheader(candidate)? != block
{
return None;
}
let (call_instr_ref, call, loop_instr) = self.generic_for_header_instrs(header)?;
let exit = self.lowering.cfg.instr_to_block[loop_instr.exit_target.index()];
if !candidate.exits.contains(&exit) {
return None;
}
if let Some(stop) = stop
&& stop != exit
&& candidate.blocks.contains(&stop)
{
return None;
}
let body_entry = self.lowering.cfg.instr_to_block[loop_instr.body_target.index()];
if !candidate.blocks.contains(&body_entry) || body_entry == header {
return None;
}
let bindings = self
.lowering
.bindings
.generic_for_locals
.get(&header)?
.clone();
if bindings.len() != loop_instr.bindings.len {
return None;
}
let mut excluded_regs = vec![loop_instr.control];
excluded_regs.extend(
(0..loop_instr.bindings.len)
.map(|offset| Reg(loop_instr.bindings.start.index() + offset)),
);
let plan = self.build_loop_state_plan(
candidate,
Some(block),
exit,
&excluded_regs,
target_overrides,
)?;
let combined_target_overrides =
merge_target_overrides(target_overrides, &plan.backedge_target_overrides);
self.visited.insert(block);
stmts.extend(self.lower_block_prefix(block, false, target_overrides)?);
stmts.extend(loop_state_init_stmts(&plan));
let mut loop_context = self.build_active_loop_context(
candidate,
exit,
&combined_target_overrides,
&plan.states,
)?;
loop_context.loop_blocks = candidate.blocks.clone();
loop_context.state_slots = plan.states.clone();
self.active_loops.push(loop_context.clone());
let body = self.lower_region(body_entry, Some(header), &combined_target_overrides)?;
self.active_loops.pop();
self.visited.insert(header);
self.visited.extend(
loop_context
.break_exits
.values()
.flat_map(|break_exit| break_exit.blocks.iter().copied()),
);
self.install_loop_exit_bindings(candidate, exit, &plan, target_overrides);
stmts.push(HirStmt::GenericFor(Box::new(HirGenericFor {
bindings,
iterator: self.lower_generic_for_iterator(header, call_instr_ref, call),
body,
})));
Some(Some(exit))
}
}
fn temp_refs_in_eval_order(expr: &HirExpr) -> Vec<TempId> {
let mut refs = Vec::new();
collect_temp_refs_in_eval_order(expr, &mut refs);
refs
}
fn collect_temp_refs_in_eval_order(expr: &HirExpr, refs: &mut Vec<TempId>) {
match expr {
HirExpr::TempRef(temp) => refs.push(*temp),
HirExpr::TableAccess(access) => {
collect_temp_refs_in_eval_order(&access.base, refs);
collect_temp_refs_in_eval_order(&access.key, refs);
}
HirExpr::Unary(unary) => collect_temp_refs_in_eval_order(&unary.expr, refs),
HirExpr::Binary(binary) => {
collect_temp_refs_in_eval_order(&binary.lhs, refs);
collect_temp_refs_in_eval_order(&binary.rhs, refs);
}
HirExpr::LogicalAnd(logical) | HirExpr::LogicalOr(logical) => {
collect_temp_refs_in_eval_order(&logical.lhs, refs);
collect_temp_refs_in_eval_order(&logical.rhs, refs);
}
HirExpr::Decision(decision) => {
for node in &decision.nodes {
collect_temp_refs_in_eval_order(&node.test, refs);
collect_decision_target_temp_refs(&node.truthy, refs);
collect_decision_target_temp_refs(&node.falsy, refs);
}
}
HirExpr::Call(call) => {
collect_temp_refs_in_eval_order(&call.callee, refs);
for arg in &call.args {
collect_temp_refs_in_eval_order(arg, refs);
}
}
HirExpr::TableConstructor(table) => {
for field in &table.fields {
match field {
HirTableField::Array(value) => collect_temp_refs_in_eval_order(value, refs),
HirTableField::Record(record) => {
if let HirTableKey::Expr(key) = &record.key {
collect_temp_refs_in_eval_order(key, refs);
}
collect_temp_refs_in_eval_order(&record.value, refs);
}
}
}
if let Some(trailing) = &table.trailing_multivalue {
collect_temp_refs_in_eval_order(trailing, refs);
}
}
HirExpr::Closure(closure) => {
for capture in &closure.captures {
collect_temp_refs_in_eval_order(&capture.value, refs);
}
}
HirExpr::Nil
| HirExpr::Boolean(_)
| HirExpr::Integer(_)
| HirExpr::Number(_)
| HirExpr::String(_)
| HirExpr::Int64(_)
| HirExpr::UInt64(_)
| HirExpr::Complex { .. }
| HirExpr::ParamRef(_)
| HirExpr::LocalRef(_)
| HirExpr::UpvalueRef(_)
| HirExpr::GlobalRef(_)
| HirExpr::VarArg
| HirExpr::Unresolved(_) => {}
}
}
fn collect_decision_target_temp_refs(target: &HirDecisionTarget, refs: &mut Vec<TempId>) {
if let HirDecisionTarget::Expr(expr) = target {
collect_temp_refs_in_eval_order(expr, refs);
}
}