// Licensing scope: see ../../LICENSE and this directory's LICENSE and NOTICE.
// Copyright 2023 WebAssembly Community Group participants.
// Retained historical upstream notice; current derivation remains unconfirmed.
// Conservative attribution from pinned Binaryen version_130 counterpart:
// Copyright 2015 WebAssembly Community Group participants
// Counterpart: src/passes/MergeBlocks.cpp (5d704ad5); origin remains unconfirmed.
// Potentially incorporated Binaryen expression retains Apache-2.0 terms.
// Original Starshine contributions use the scoped MIT grant in ../../LICENSE.
// Modified for Starshine through 2026: implementation and validation use
// Starshine's representations and APIs; this is not an unchanged upstream file.
// Conservative notice retention does not establish copying or independence.
///|
test "merge blocks retains raw validity through carried values and drops after unreachable" {
let input = pass_test_module_from_wat(
"(module (table 1 funcref) (func (export \"f\") i32.const 0 i32.const 0 table.get 0 i32.const 0 table.fill 0 block (result v128) unreachable end f32.const 2.5 block end drop drop block (result funcref) block ref.null func i32.const 0 br_table 1 1 end unreachable end drop))",
)
let func = @ir.hot_lift_func(input, @lib.FuncIdx::new(0U))
let before = input.with_code_sec(
@lib.CodeSec::new([@ir.hot_lower_func(func)]),
)
@validate.validate_module(before).unwrap()
let ctx = HotPassContext::new(
merge_blocks_descriptor(),
@ir.HotAnalysisCache::new(),
HotPipelineVerifyPolicy::after_each_pass(),
false,
fn(_) { () },
module_ctx=Some(@ir.hot_module_context_from_module(input)),
)
assert_true(merge_blocks_run(ctx, func).changed)
@ir.hot_verify_core(func).unwrap()
@ir.hot_verify_control(func).unwrap()
let after = input.with_code_sec(@lib.CodeSec::new([@ir.hot_lower_func(func)]))
@validate.validate_module(after).unwrap()
let pipeline = run_hot_pipeline(input, HotPipelineOptions::new(), [
"merge-blocks",
]).unwrap()
@validate.validate_module(pipeline).unwrap()
}
///|
pub fn merge_blocks_descriptor() -> @ir.HotPassDescriptor {
@ir.HotPassDescriptor::new("merge-blocks", invalidates=[
@ir.HotAnalysis::cfg(),
@ir.HotAnalysis::dominance(),
@ir.HotAnalysis::liveness(),
@ir.HotAnalysis::use_def(),
@ir.HotAnalysis::effects(),
@ir.HotAnalysis::loop_info(),
@ir.HotAnalysis::ssa(),
])
}
///|
pub fn merge_blocks_summary() -> String {
"Flatten branch-free block roots into their parent regions to expose later branch cleanup."
}
///|
fn merge_blocks_has_candidate(func : @ir.HotFunc) -> Bool {
for node_id = 0; node_id < @ir.hot_node_count(func); node_id = node_id + 1 {
if !@ir.hot_node_is_live(func, node_id) {
continue
}
match @ir.hot_node_get(func, node_id).op {
@ir.HotOp::Block | @ir.HotOp::Loop => return true
_ => ()
}
}
false
}
///|
fn merge_blocks_collect_region_roots(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
roots : Array[Int32],
) -> Unit {
roots.clear()
let root_count = @ir.hot_region_root_count(func, region_ref)
for idx = 0; idx < root_count; idx = idx + 1 {
roots.push(@ir.hot_region_get(func, region_ref, idx))
}
}
///|
fn merge_blocks_control_block_type(
func : @ir.HotFunc,
node_id : Int32,
) -> @lib.BlockType? {
match @ir.hot_type_get(func, @ir.hot_node_get(func, node_id).ty) {
@ir.HotTypeInfo::BlockResult(block_type)
| @ir.HotTypeInfo::BlockResultResolved(block_type, _, _) => Some(block_type)
_ => None
}
}
///|
fn merge_blocks_block_param_count(
func : @ir.HotFunc,
node_id : Int32,
module_ctx : @ir.HotModuleContext?,
) -> Int32 {
match merge_blocks_control_block_type(func, node_id) {
Some(@lib.TypeIdxBlockType(type_idx)) =>
match module_ctx {
Some(ctx) =>
match @ir.hot_module_resolve_type_func_type(ctx, type_idx) {
Some(@lib.FuncType(params, _)) => params.length()
None => 1
}
None => 1
}
_ => 0
}
}
///|
fn merge_blocks_block_has_params(
func : @ir.HotFunc,
node_id : Int32,
module_ctx : @ir.HotModuleContext?,
) -> Bool {
merge_blocks_block_param_count(func, node_id, module_ctx) > 0
}
///|
fn merge_blocks_region_contains_loop(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
workspace~ : MergeBlocksBranchScanWorkspace? = None,
visits~ : Array[Int32]? = None,
) -> Bool {
let scan = match workspace {
Some(value) => value
None => MergeBlocksBranchScanWorkspace::new()
}
scan.loop_begin(func)
merge_blocks_region_contains_loop_memoized(func, region_ref, scan, visits)
}
///|
fn merge_blocks_region_contains_loop_memoized(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
scan : MergeBlocksBranchScanWorkspace,
visits : Array[Int32]?,
) -> Bool {
for idx = 0; idx < @ir.hot_region_root_count(func, region_ref); idx = idx + 1 {
if merge_blocks_node_contains_loop_memoized(
func,
@ir.hot_region_get(func, region_ref, idx),
scan,
visits,
) {
return true
}
}
false
}
///|
fn merge_blocks_node_contains_loop_memoized(
func : @ir.HotFunc,
node_id : Int32,
scan : MergeBlocksBranchScanWorkspace,
visits : Array[Int32]?,
) -> Bool {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
return false
}
if node_id >= scan.loop_states.length() {
scan.loop_begin(func)
}
if scan.loop_revisions[node_id] == scan.loop_revision {
match scan.loop_states[node_id] {
1 | 3 => return true
2 => return false
_ => ()
}
}
scan.loop_revisions[node_id] = scan.loop_revision
scan.loop_states[node_id] = 1
match visits {
Some(count) => count[0] += 1
None => ()
}
let contains = match @ir.hot_node_get(func, node_id).op {
@ir.HotOp::Loop => true
@ir.HotOp::Block =>
merge_blocks_region_contains_loop_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
scan,
visits,
)
@ir.HotOp::If => {
let then_has_loop = merge_blocks_region_contains_loop_memoized(
func,
@ir.hot_region_then_ref(func, node_id),
scan,
visits,
)
if then_has_loop {
true
} else {
match @ir.hot_region_else_ref(func, node_id) {
Some(else_ref) =>
merge_blocks_region_contains_loop_memoized(
func, else_ref, scan, visits,
)
None => false
}
}
}
@ir.HotOp::Try => {
let body_has_loop = merge_blocks_region_contains_loop_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
scan,
visits,
)
if body_has_loop {
true
} else {
match @ir.hot_region_catch_ref(func, node_id) {
Some(catch_ref) =>
merge_blocks_region_contains_loop_memoized(
func, catch_ref, scan, visits,
)
None => false
}
}
}
@ir.HotOp::TryTable =>
merge_blocks_region_contains_loop_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
scan,
visits,
) ||
merge_blocks_region_contains_loop_memoized(
func,
@ir.hot_region_catch_list_ref(func, node_id),
scan,
visits,
)
_ => false
}
scan.loop_states[node_id] = if contains { 3 } else { 2 }
contains
}
///|
fn merge_blocks_rewrite_dead_unreachable_suffix_roots(
func : @ir.HotFunc,
roots : Array[Int32],
) -> Bool {
if roots.length() == 0 {
return true
}
let rewrite_dead_values_before = fn(unreachable_idx : Int32) -> Bool {
if unreachable_idx < 0 || unreachable_idx >= roots.length() {
return true
}
let rewritten : Array[Int32] = []
for idx = 0; idx < unreachable_idx; idx = idx + 1 {
rewritten.push(roots[idx])
}
for idx = unreachable_idx + 1; idx < roots.length(); idx = idx + 1 {
let root_id = roots[idx]
if @ir.hot_node_result_arity(func, root_id) != 1 ||
!@ir.effects_is_pure(@ir.effects_for_node(func, root_id)) {
// HOT can place pending pre-unreachable values after the terminator in
// region-root order. Moving a pure value before the unreachable is
// harmless, but an effectful root may instead be source-level dead code
// that originally followed the trap. Keep the block intact when the
// distinction is not semantically free.
return false
}
rewritten.push(@ir.hot_build_drop(func, root_id))
}
rewritten.push(roots[unreachable_idx])
roots.clear()
for root_id in rewritten {
roots.push(root_id)
}
true
}
match @ir.hot_node_get(func, roots[roots.length() - 1]).op {
@ir.HotOp::Unreachable =>
return rewrite_dead_values_before(roots.length() - 1)
_ => ()
}
for idx = 0; idx < roots.length(); idx = idx + 1 {
match @ir.hot_node_get(func, roots[idx]).op {
@ir.HotOp::Unreachable => return rewrite_dead_values_before(idx)
_ => ()
}
}
true
}
///|
fn merge_blocks_visit_control_node(
func : @ir.HotFunc,
node_id : Int32,
label_used : @bitset.BitSet,
drop_parent_index : MergeBlocksDropParentIndex,
flattened_roots : Array[Int32],
branch_workspace : MergeBlocksBranchScanWorkspace,
module_ctx : @ir.HotModuleContext?,
) -> Bool {
let node = @ir.hot_node_get(func, node_id)
let control_has_params = merge_blocks_block_has_params(
func, node_id, module_ctx,
)
let control_is_loop = match node.op {
@ir.HotOp::Loop => true
_ => false
}
match node.op {
@ir.HotOp::Block | @ir.HotOp::Loop =>
merge_blocks_visit_region(
func,
@ir.hot_region_body_ref(func, node_id),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
module_ctx,
control_has_params,
control_is_loop,
)
@ir.HotOp::If => {
let mut changed = merge_blocks_visit_region(
func,
@ir.hot_region_then_ref(func, node_id),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
module_ctx,
false,
false,
)
match @ir.hot_region_else_ref(func, node_id) {
Some(else_region) =>
changed = merge_blocks_visit_region(
func, else_region, label_used, drop_parent_index, flattened_roots,
branch_workspace, module_ctx, false, false,
) ||
changed
None => ()
}
changed
}
@ir.HotOp::Try => {
let mut changed = merge_blocks_visit_region(
func,
@ir.hot_region_body_ref(func, node_id),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
module_ctx,
control_has_params,
false,
)
match @ir.hot_region_catch_ref(func, node_id) {
Some(catch_region) =>
changed = merge_blocks_visit_region(
func, catch_region, label_used, drop_parent_index, flattened_roots,
branch_workspace, module_ctx, control_has_params, false,
) ||
changed
None => ()
}
changed
}
@ir.HotOp::TryTable => {
let changed = merge_blocks_visit_region(
func,
@ir.hot_region_body_ref(func, node_id),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
module_ctx,
control_has_params,
false,
)
merge_blocks_visit_region(
func,
@ir.hot_region_catch_list_ref(func, node_id),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
module_ctx,
control_has_params,
false,
) ||
changed
}
_ => false
}
}
///|
fn merge_blocks_collect_local_write_sites(
func : @ir.HotFunc,
node_id : Int32,
write_nodes : Array[Int32],
write_locals : Array[Int32],
) -> Unit {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
return
}
let node = @ir.hot_node_get(func, node_id)
match node.op {
@ir.HotOp::LocalSet | @ir.HotOp::LocalTee => {
write_nodes.push(node_id)
write_locals.push(node.imm0)
}
@ir.HotOp::Block | @ir.HotOp::Loop => {
let body_ref = @ir.hot_region_body_ref(func, node_id)
for idx = 0
idx < @ir.hot_region_root_count(func, body_ref)
idx = idx + 1 {
merge_blocks_collect_local_write_sites(
func,
@ir.hot_region_get(func, body_ref, idx),
write_nodes,
write_locals,
)
}
return
}
@ir.HotOp::If => {
merge_blocks_collect_local_write_sites(
func,
@ir.hot_child_get(func, node_id, 0),
write_nodes,
write_locals,
)
let then_ref = @ir.hot_region_then_ref(func, node_id)
for idx = 0
idx < @ir.hot_region_root_count(func, then_ref)
idx = idx + 1 {
merge_blocks_collect_local_write_sites(
func,
@ir.hot_region_get(func, then_ref, idx),
write_nodes,
write_locals,
)
}
match @ir.hot_region_else_ref(func, node_id) {
Some(else_ref) =>
for idx = 0
idx < @ir.hot_region_root_count(func, else_ref)
idx = idx + 1 {
merge_blocks_collect_local_write_sites(
func,
@ir.hot_region_get(func, else_ref, idx),
write_nodes,
write_locals,
)
}
None => ()
}
return
}
_ => ()
}
for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
merge_blocks_collect_local_write_sites(
func,
@ir.hot_child_get(func, node_id, slot),
write_nodes,
write_locals,
)
}
}
///|
fn merge_blocks_collect_min_local_get_node_ids(
func : @ir.HotFunc,
node_id : Int32,
min_get_node_ids : Array[Int32],
) -> Unit {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
return
}
let node = @ir.hot_node_get(func, node_id)
match node.op {
@ir.HotOp::LocalGet if node.imm0 >= 0 &&
node.imm0 < min_get_node_ids.length() => {
let previous = min_get_node_ids[node.imm0]
if previous < 0 || node_id < previous {
min_get_node_ids[node.imm0] = node_id
}
}
@ir.HotOp::Block | @ir.HotOp::Loop => {
let body_ref = @ir.hot_region_body_ref(func, node_id)
for idx = 0
idx < @ir.hot_region_root_count(func, body_ref)
idx = idx + 1 {
merge_blocks_collect_min_local_get_node_ids(
func,
@ir.hot_region_get(func, body_ref, idx),
min_get_node_ids,
)
}
return
}
@ir.HotOp::If => {
merge_blocks_collect_min_local_get_node_ids(
func,
@ir.hot_child_get(func, node_id, 0),
min_get_node_ids,
)
let then_ref = @ir.hot_region_then_ref(func, node_id)
for idx = 0
idx < @ir.hot_region_root_count(func, then_ref)
idx = idx + 1 {
merge_blocks_collect_min_local_get_node_ids(
func,
@ir.hot_region_get(func, then_ref, idx),
min_get_node_ids,
)
}
match @ir.hot_region_else_ref(func, node_id) {
Some(else_ref) =>
for idx = 0
idx < @ir.hot_region_root_count(func, else_ref)
idx = idx + 1 {
merge_blocks_collect_min_local_get_node_ids(
func,
@ir.hot_region_get(func, else_ref, idx),
min_get_node_ids,
)
}
None => ()
}
return
}
_ => ()
}
for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
merge_blocks_collect_min_local_get_node_ids(
func,
@ir.hot_child_get(func, node_id, slot),
min_get_node_ids,
)
}
}
///|
fn merge_blocks_roots_have_stack_carried_local_dependency(
func : @ir.HotFunc,
roots : Array[Int32],
) -> Bool {
let min_later_get_node_ids = Array::make(@ir.hot_local_count(func), -1)
let write_nodes : Array[Int32] = []
let write_locals : Array[Int32] = []
let mut idx = roots.length() - 1
while idx >= 0 {
write_nodes.clear()
write_locals.clear()
merge_blocks_collect_local_write_sites(
func,
roots[idx],
write_nodes,
write_locals,
)
for write_idx = 0
write_idx < write_nodes.length()
write_idx = write_idx + 1 {
let local_id = write_locals[write_idx]
if local_id >= 0 && local_id < min_later_get_node_ids.length() {
let min_get_node_id = min_later_get_node_ids[local_id]
if min_get_node_id >= 0 && min_get_node_id < write_nodes[write_idx] {
return true
}
}
}
merge_blocks_collect_min_local_get_node_ids(
func,
roots[idx],
min_later_get_node_ids,
)
idx = idx - 1
}
false
}
///|
fn merge_blocks_prefix_writes_tail_read(
func : @ir.HotFunc,
prefix : Array[Int32],
tail_id : Int32,
) -> Bool {
let roots = prefix.copy()
roots.push(tail_id)
merge_blocks_roots_have_stack_carried_local_dependency(func, roots)
}
///|
fn merge_blocks_can_lift_block_child(
func : @ir.HotFunc,
block_id : Int32,
label_used : @bitset.BitSet,
module_ctx : @ir.HotModuleContext?,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
if block_id < 0 || !@ir.hot_node_is_live(func, block_id) {
return false
}
match @ir.hot_node_get(func, block_id).op {
@ir.HotOp::Block => ()
_ => return false
}
if pass_label_is_used(@ir.hot_control_node_label(func, block_id), label_used) {
return false
}
if merge_blocks_block_has_params(func, block_id, module_ctx) {
return false
}
let body_ref = @ir.hot_region_body_ref(func, block_id)
if merge_blocks_region_contains_loop(
func,
body_ref,
workspace=Some(workspace),
) {
return false
}
let root_count = @ir.hot_region_root_count(func, body_ref)
if root_count < 2 {
return false
}
let tail_id = @ir.hot_region_get(func, body_ref, root_count - 1)
if @ir.hot_node_result_arity(func, tail_id) != 1 {
return false
}
let block_results = @ir.hot_type_results(
func,
@ir.hot_node_type(func, block_id),
)
let tail_results = @ir.hot_type_results(
func,
@ir.hot_node_type(func, tail_id),
)
block_results == tail_results && block_results.length() == 1
}
///|
fn merge_blocks_lift_expression_block_children(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
label_used : @bitset.BitSet,
module_ctx : @ir.HotModuleContext?,
branch_workspace~ : MergeBlocksBranchScanWorkspace? = None,
) -> Int32 {
let root_id = @ir.hot_region_get(func, region_ref, idx)
if root_id < 0 || !@ir.hot_node_is_live(func, root_id) {
return 0
}
let root_node = @ir.hot_node_get(func, root_id)
match root_node.op {
@ir.HotOp::Block | @ir.HotOp::Loop | @ir.HotOp::Try | @ir.HotOp::TryTable =>
return 0
_ => ()
}
let child_count = @ir.hot_child_count(func, root_id)
if child_count == 0 {
return 0
}
let mut previous_effects = 0U
let lifted_prefixes : Array[Int32] = []
let next_children : Array[Int32] = []
let workspace = match branch_workspace {
Some(value) => value
None => MergeBlocksBranchScanWorkspace::new()
}
let mut branch_epoch_started = false
let mut changed = false
for slot = 0; slot < child_count; slot = slot + 1 {
match root_node.op {
@ir.HotOp::If if slot != 0 => {
next_children.push(@ir.hot_child_get(func, root_id, slot))
continue
}
_ => ()
}
let child_id = @ir.hot_child_get(func, root_id, slot)
if merge_blocks_can_lift_block_child(
func, child_id, label_used, module_ctx, workspace,
) {
if !branch_epoch_started {
workspace.begin(func)
branch_epoch_started = true
}
let body_ref = @ir.hot_region_body_ref(func, child_id)
let root_count = @ir.hot_region_root_count(func, body_ref)
let tail_id = @ir.hot_region_get(func, body_ref, root_count - 1)
let prefix : Array[Int32] = []
let mut prefix_effects = 0U
let mut prefix_has_branch = false
for prefix_idx = 0
prefix_idx < root_count - 1
prefix_idx = prefix_idx + 1 {
let prefix_id = @ir.hot_region_get(func, body_ref, prefix_idx)
prefix.push(prefix_id)
prefix_effects = prefix_effects | @ir.effects_for_node(func, prefix_id)
if merge_blocks_node_has_branch_memoized(func, prefix_id, workspace) {
prefix_has_branch = true
}
}
if !prefix_has_branch &&
!merge_blocks_prefix_writes_tail_read(func, prefix, tail_id) &&
pass_effect_masks_can_reorder(previous_effects, prefix_effects) {
for prefix_id in prefix {
lifted_prefixes.push(prefix_id)
}
next_children.push(tail_id)
@ir.hot_region_replace_body(func, body_ref, [])
previous_effects = previous_effects |
@ir.effects_for_node(func, tail_id)
changed = true
continue
}
}
next_children.push(child_id)
previous_effects = previous_effects | @ir.effects_for_node(func, child_id)
}
if !changed || lifted_prefixes.length() == 0 {
return 0
}
ignore(@ir.hot_replace_child_span(func, root_id, next_children))
ignore(@ir.hot_region_splice(func, region_ref, idx, 0, lifted_prefixes))
lifted_prefixes.length()
}
///|
priv struct MergeBlocksDropParentIndex {
uses : Array[@bitset.BitSet]
mut live_nodes_scanned : Int32
mut drop_child_slots : Int32
}
///|
fn MergeBlocksDropParentIndex::new() -> MergeBlocksDropParentIndex {
{ uses: [], live_nodes_scanned: 0, drop_child_slots: 0, }
}
///|
fn merge_blocks_compute_drop_parent_index(
func : @ir.HotFunc,
) -> (@bitset.BitSet, Int32, Int32) {
let used_by_drop = @bitset.BitSet::new(@ir.hot_node_count(func))
let mut live_nodes_scanned = 0
let mut drop_child_slots = 0
for node_id = 0; node_id < @ir.hot_node_count(func); node_id = node_id + 1 {
if !@ir.hot_node_is_live(func, node_id) {
continue
}
live_nodes_scanned = live_nodes_scanned + 1
match @ir.hot_node_get(func, node_id).op {
@ir.HotOp::Drop =>
for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
let child_id = @ir.hot_child_get(func, node_id, slot)
if child_id >= 0 && child_id < used_by_drop.length() {
used_by_drop[child_id] = true
drop_child_slots = drop_child_slots + 1
}
}
_ => ()
}
}
(used_by_drop, live_nodes_scanned, drop_child_slots)
}
///|
fn merge_blocks_drop_parent_index_contains(
index : MergeBlocksDropParentIndex,
func : @ir.HotFunc,
node_id : Int32,
) -> Bool {
if index.uses.length() == 0 {
let (uses, live_nodes_scanned, drop_child_slots) = merge_blocks_compute_drop_parent_index(
func,
)
index.uses.push(uses)
index.live_nodes_scanned = live_nodes_scanned
index.drop_child_slots = drop_child_slots
}
let uses = index.uses[0]
node_id >= 0 && node_id < uses.length() && uses[node_id]
}
///|
priv struct MergeBlocksBranchScanWorkspace {
states : Array[Int32]
epochs : Array[Int32]
mut epoch : Int32
mut initialized_cells : Int32
loop_states : Array[Int32]
loop_revisions : Array[Int32]
mut loop_revision : Int32
}
///|
fn MergeBlocksBranchScanWorkspace::new() -> MergeBlocksBranchScanWorkspace {
{
states: [],
epochs: [],
epoch: 0,
initialized_cells: 0,
loop_states: [],
loop_revisions: [],
loop_revision: -1,
}
}
///|
fn MergeBlocksBranchScanWorkspace::loop_begin(
self : MergeBlocksBranchScanWorkspace,
func : @ir.HotFunc,
) -> Unit {
while self.loop_states.length() < @ir.hot_node_count(func) {
self.loop_states.push(0)
self.loop_revisions.push(-1)
}
self.loop_revision = @ir.hot_revision_current(func)
}
///|
fn MergeBlocksBranchScanWorkspace::begin(
self : MergeBlocksBranchScanWorkspace,
func : @ir.HotFunc,
) -> Unit {
while self.states.length() < @ir.hot_node_count(func) {
self.states.push(0)
self.epochs.push(0)
self.initialized_cells += 1
}
self.epoch += 1
}
///|
fn merge_blocks_node_has_branch(func : @ir.HotFunc, node_id : Int32) -> Bool {
let workspace = MergeBlocksBranchScanWorkspace::new()
workspace.begin(func)
merge_blocks_node_has_branch_memoized(func, node_id, workspace)
}
///|
fn merge_blocks_node_has_branch_memoized(
func : @ir.HotFunc,
node_id : Int32,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
return false
}
if node_id >= workspace.states.length() {
return true
}
if workspace.epochs[node_id] == workspace.epoch {
match workspace.states[node_id] {
1 => return true
2 => return false
3 => return true
_ => ()
}
}
workspace.epochs[node_id] = workspace.epoch
workspace.states[node_id] = 1
let node = @ir.hot_node_get(func, node_id)
match node.op {
@ir.HotOp::Br
| @ir.HotOp::BrIf
| @ir.HotOp::BrTable
| @ir.HotOp::BrOnNull
| @ir.HotOp::BrOnNonNull
| @ir.HotOp::BrOnCast
| @ir.HotOp::BrOnCastFail
| @ir.HotOp::Delegate => {
workspace.states[node_id] = 3
return true
}
@ir.HotOp::Block | @ir.HotOp::Loop =>
if merge_blocks_region_has_branch_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
workspace,
) {
workspace.states[node_id] = 3
return true
}
@ir.HotOp::Try => {
if merge_blocks_region_has_branch_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
workspace,
) {
workspace.states[node_id] = 3
return true
}
match @ir.hot_region_catch_ref(func, node_id) {
Some(catch_ref) =>
if merge_blocks_region_has_branch_memoized(func, catch_ref, workspace) {
workspace.states[node_id] = 3
return true
}
None => ()
}
}
@ir.HotOp::If => {
if merge_blocks_region_has_branch_memoized(
func,
@ir.hot_region_then_ref(func, node_id),
workspace,
) {
workspace.states[node_id] = 3
return true
}
match @ir.hot_region_else_ref(func, node_id) {
Some(else_ref) =>
if merge_blocks_region_has_branch_memoized(func, else_ref, workspace) {
workspace.states[node_id] = 3
return true
}
None => ()
}
}
@ir.HotOp::TryTable =>
if merge_blocks_region_has_branch_memoized(
func,
@ir.hot_region_body_ref(func, node_id),
workspace,
) ||
merge_blocks_region_has_branch_memoized(
func,
@ir.hot_region_catch_list_ref(func, node_id),
workspace,
) {
workspace.states[node_id] = 3
return true
}
_ => ()
}
for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
if merge_blocks_node_has_branch_memoized(
func,
@ir.hot_child_get(func, node_id, slot),
workspace,
) {
workspace.states[node_id] = 3
return true
}
}
workspace.states[node_id] = 2
false
}
///|
fn merge_blocks_region_has_branch(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
) -> Bool {
let workspace = MergeBlocksBranchScanWorkspace::new()
workspace.begin(func)
merge_blocks_region_has_branch_memoized(func, region_ref, workspace)
}
///|
fn merge_blocks_region_has_branch_memoized(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
for idx = 0; idx < @ir.hot_region_root_count(func, region_ref); idx = idx + 1 {
if merge_blocks_node_has_branch_memoized(
func,
@ir.hot_region_get(func, region_ref, idx),
workspace,
) {
return true
}
}
false
}
///|
fn merge_blocks_flatten_region_root_block(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
label_used : @bitset.BitSet,
drop_parent_index : MergeBlocksDropParentIndex,
flattened_roots : Array[Int32],
module_ctx : @ir.HotModuleContext?,
enclosing_control_has_params : Bool,
enclosing_control_is_loop : Bool,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
let block_id = @ir.hot_region_get(func, region_ref, idx)
if block_id < 0 || !@ir.hot_node_is_live(func, block_id) {
return false
}
let node = @ir.hot_node_get(func, block_id)
match node.op {
@ir.HotOp::Block => ()
_ => return false
}
let label_id = @ir.hot_control_node_label(func, block_id)
let result_count = @ir.hot_type_results(
func,
@ir.hot_node_type(func, block_id),
).length()
if pass_label_is_used(label_id, label_used) {
// Keep live-label blocks intact. Pulling prefixes out of a block that is
// still a branch target can change the active label stack seen by branches
// nested in later roots and make lowering emit branches with the wrong
// result arity.
return false
}
let param_count = merge_blocks_block_param_count(func, block_id, module_ctx)
if param_count > 0 &&
(
!enclosing_control_has_params ||
(param_count != 1 && !(enclosing_control_is_loop && result_count == 0))
) {
return false
}
if param_count == 0 &&
result_count > 1 &&
merge_blocks_drop_parent_index_contains(drop_parent_index, func, block_id) {
// Zero-param multivalue root blocks can be shared with a sibling `drop`
// that discards one lane while another stays live. Flattening the rooted
// copy empties the shared node out from under the drop user and lowers
// invalid stack traffic. Keep that grouped carrier intact.
return false
}
let body_ref = @ir.hot_region_body_ref(func, block_id)
if merge_blocks_region_contains_loop(
func,
body_ref,
workspace=Some(workspace),
) {
return false
}
merge_blocks_collect_region_roots(func, body_ref, flattened_roots)
if merge_blocks_roots_have_stack_carried_local_dependency(
func, flattened_roots,
) ||
!merge_blocks_rewrite_dead_unreachable_suffix_roots(func, flattened_roots) {
return false
}
ignore(@ir.hot_region_splice(func, region_ref, idx, 1, flattened_roots))
@ir.hot_region_replace_body(func, body_ref, [])
true
}
///|
fn merge_blocks_flatten_branch_free_loop_body(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
label_used : @bitset.BitSet,
flattened_roots : Array[Int32],
module_ctx : @ir.HotModuleContext?,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
let loop_id = @ir.hot_region_get(func, region_ref, idx)
if loop_id < 0 || !@ir.hot_node_is_live(func, loop_id) {
return false
}
match @ir.hot_node_get(func, loop_id).op {
@ir.HotOp::Loop => ()
_ => return false
}
if pass_label_is_used(@ir.hot_control_node_label(func, loop_id), label_used) ||
merge_blocks_block_has_params(func, loop_id, module_ctx) ||
@ir.hot_type_results(func, @ir.hot_node_type(func, loop_id)).length() > 0 {
return false
}
let body_ref = @ir.hot_region_body_ref(func, loop_id)
if @ir.hot_region_root_count(func, body_ref) < 2 ||
merge_blocks_region_contains_loop(func, body_ref, workspace=Some(workspace)) {
return false
}
merge_blocks_collect_region_roots(func, body_ref, flattened_roots)
if !merge_blocks_rewrite_dead_unreachable_suffix_roots(func, flattened_roots) {
return false
}
ignore(@ir.hot_region_splice(func, region_ref, idx, 1, flattened_roots))
@ir.hot_region_replace_body(func, body_ref, [])
true
}
///|
fn merge_blocks_flatten_branch_free_loop_block_body(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
label_used : @bitset.BitSet,
flattened_roots : Array[Int32],
module_ctx : @ir.HotModuleContext?,
workspace : MergeBlocksBranchScanWorkspace,
) -> Bool {
let loop_id = @ir.hot_region_get(func, region_ref, idx)
if loop_id < 0 || !@ir.hot_node_is_live(func, loop_id) {
return false
}
match @ir.hot_node_get(func, loop_id).op {
@ir.HotOp::Loop => ()
_ => return false
}
if pass_label_is_used(@ir.hot_control_node_label(func, loop_id), label_used) ||
merge_blocks_block_has_params(func, loop_id, module_ctx) ||
@ir.hot_type_results(func, @ir.hot_node_type(func, loop_id)).length() > 0 {
return false
}
let loop_body_ref = @ir.hot_region_body_ref(func, loop_id)
if @ir.hot_region_root_count(func, loop_body_ref) != 1 {
return false
}
let block_id = @ir.hot_region_get(func, loop_body_ref, 0)
if block_id < 0 || !@ir.hot_node_is_live(func, block_id) {
return false
}
match @ir.hot_node_get(func, block_id).op {
@ir.HotOp::Block => ()
_ => return false
}
if pass_label_is_used(@ir.hot_control_node_label(func, block_id), label_used) ||
merge_blocks_block_has_params(func, block_id, module_ctx) ||
@ir.hot_type_results(func, @ir.hot_node_type(func, block_id)).length() > 0 {
return false
}
let block_body_ref = @ir.hot_region_body_ref(func, block_id)
if merge_blocks_region_contains_loop(
func,
block_body_ref,
workspace=Some(workspace),
) {
return false
}
merge_blocks_collect_region_roots(func, block_body_ref, flattened_roots)
if !merge_blocks_rewrite_dead_unreachable_suffix_roots(func, flattened_roots) {
return false
}
ignore(@ir.hot_region_splice(func, region_ref, idx, 1, flattened_roots))
@ir.hot_region_replace_body(func, block_body_ref, [])
@ir.hot_region_replace_body(func, loop_body_ref, [])
true
}
///|
fn merge_blocks_try_remove_o4z_self_br_if_void_block(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
) -> Bool {
let block_id = @ir.hot_region_get(func, region_ref, idx)
if block_id < 0 || !@ir.hot_node_is_live(func, block_id) {
return false
}
match @ir.hot_node_get(func, block_id).op {
@ir.HotOp::Block => ()
_ => return false
}
if @ir.hot_node_result_arity(func, block_id) != 0 {
return false
}
let body_ref = @ir.hot_region_body_ref(func, block_id)
if @ir.hot_region_root_count(func, body_ref) != 1 {
return false
}
let branch_id = @ir.hot_region_get(func, body_ref, 0)
if branch_id < 0 || !@ir.hot_node_is_live(func, branch_id) {
return false
}
match @ir.hot_node_get(func, branch_id).op {
@ir.HotOp::BrIf => ()
_ => return false
}
if @ir.hot_branch_target(func, branch_id) !=
Some(@ir.hot_control_node_label(func, block_id)) ||
@ir.hot_child_count(func, branch_id) != 1 {
return false
}
if pass_label_is_used(
@ir.hot_control_node_label(func, block_id),
pass_compute_label_used_except(func, branch_id),
) {
return false
}
let condition = @ir.hot_child_get(func, branch_id, 0)
let dropped_condition = @ir.hot_build_drop(func, condition)
ignore(@ir.hot_region_splice(func, region_ref, idx, 1, [dropped_condition]))
@ir.hot_region_replace_body(func, body_ref, [])
true
}
///|
fn merge_blocks_cleanup_o4z_self_br_if_region(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
) -> Bool {
let mut changed = false
let mut idx = 0
while idx < @ir.hot_region_root_count(func, region_ref) {
if merge_blocks_try_remove_o4z_self_br_if_void_block(func, region_ref, idx) {
changed = true
idx += 1
continue
}
let node_id = @ir.hot_region_get(func, region_ref, idx)
if node_id >= 0 && @ir.hot_node_is_live(func, node_id) {
let node = @ir.hot_node_get(func, node_id)
match node.op {
@ir.HotOp::Block | @ir.HotOp::Loop =>
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.hot_region_body_ref(func, node_id),
) ||
changed
@ir.HotOp::If => {
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.hot_region_then_ref(func, node_id),
) ||
changed
match @ir.hot_region_else_ref(func, node_id) {
Some(else_ref) =>
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func, else_ref,
) ||
changed
None => ()
}
}
@ir.HotOp::Try => {
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.hot_region_body_ref(func, node_id),
) ||
changed
match @ir.hot_region_catch_ref(func, node_id) {
Some(catch_ref) =>
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func, catch_ref,
) ||
changed
None => ()
}
}
@ir.HotOp::TryTable => {
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.hot_region_body_ref(func, node_id),
) ||
changed
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.hot_region_catch_list_ref(func, node_id),
) ||
changed
}
_ => ()
}
}
idx += 1
}
changed
}
///|
fn merge_blocks_try_cleanup_dropped_self_branch(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
idx : Int32,
) -> Bool {
let drop_id = @ir.hot_region_get(func, region_ref, idx)
if drop_id < 0 || !@ir.hot_node_is_live(func, drop_id) {
return false
}
match @ir.hot_node_get(func, drop_id).op {
@ir.HotOp::Drop => ()
_ => return false
}
if @ir.hot_child_count(func, drop_id) != 1 {
return false
}
let block_id = @ir.hot_child_get(func, drop_id, 0)
if block_id < 0 || !@ir.hot_node_is_live(func, block_id) {
return false
}
match @ir.hot_node_get(func, block_id).op {
@ir.HotOp::Block => ()
_ => return false
}
if merge_blocks_block_param_count(func, block_id, None) != 0 ||
@ir.hot_node_result_arity(func, block_id) != 1 {
return false
}
let body_ref = @ir.hot_region_body_ref(func, block_id)
if @ir.hot_region_root_count(func, body_ref) != 1 {
return false
}
let branch_id = @ir.hot_region_get(func, body_ref, 0)
if branch_id < 0 || !@ir.hot_node_is_live(func, branch_id) {
return false
}
match @ir.hot_node_get(func, branch_id).op {
@ir.HotOp::Br => ()
_ => return false
}
if @ir.hot_branch_target(func, branch_id) !=
Some(@ir.hot_control_node_label(func, block_id)) ||
@ir.hot_child_count(func, branch_id) != 1 {
return false
}
let payload = @ir.hot_child_get(func, branch_id, 0)
if !@ir.effects_is_pure(@ir.effects_for_node(func, payload)) {
return false
}
let payload_drop = @ir.hot_build_drop(func, payload)
ignore(@ir.hot_replace_child_span(func, branch_id, []))
@ir.hot_control_result_type_set(func, block_id, @ir.hot_type_void(func))
@ir.hot_region_replace_body(func, body_ref, [payload_drop, branch_id])
ignore(@ir.hot_region_splice(func, region_ref, idx, 1, [block_id]))
true
}
///|
fn merge_blocks_visit_region(
func : @ir.HotFunc,
region_ref : @ir.HotRegionRef,
label_used : @bitset.BitSet,
drop_parent_index : MergeBlocksDropParentIndex,
flattened_roots : Array[Int32],
branch_workspace : MergeBlocksBranchScanWorkspace,
module_ctx : @ir.HotModuleContext?,
enclosing_control_has_params : Bool,
enclosing_control_is_loop : Bool,
) -> Bool {
let mut changed = false
let mut idx = 0
while idx < @ir.hot_region_root_count(func, region_ref) {
if merge_blocks_try_cleanup_dropped_self_branch(func, region_ref, idx) {
changed = true
}
if merge_blocks_flatten_branch_free_loop_body(
func, region_ref, idx, label_used, flattened_roots, module_ctx, branch_workspace,
) {
changed = true
continue
}
if merge_blocks_flatten_branch_free_loop_block_body(
func, region_ref, idx, label_used, flattened_roots, module_ctx, branch_workspace,
) {
changed = true
continue
}
let node_id = @ir.hot_region_get(func, region_ref, idx)
if node_id >= 0 && @ir.hot_node_is_live(func, node_id) {
changed = merge_blocks_visit_control_node(
func, node_id, label_used, drop_parent_index, flattened_roots, branch_workspace,
module_ctx,
) ||
changed
}
let lifted_count = merge_blocks_lift_expression_block_children(
func,
region_ref,
idx,
label_used,
module_ctx,
branch_workspace=Some(branch_workspace),
)
if lifted_count > 0 {
changed = true
idx += lifted_count
}
if merge_blocks_flatten_region_root_block(
func, region_ref, idx, label_used, drop_parent_index, flattened_roots, module_ctx,
enclosing_control_has_params, enclosing_control_is_loop, branch_workspace,
) {
changed = true
} else {
idx += 1
}
}
changed
}
///|
fn merge_blocks_run(ctx : HotPassContext, func : @ir.HotFunc) -> HotPassResult {
if !merge_blocks_has_candidate(func) {
return HotPassResult::unchanged()
}
let mut changed = false
if ctx.optimize_level >= 4 && ctx.shrink_level >= 4 {
changed = merge_blocks_cleanup_o4z_self_br_if_region(
func,
@ir.HotRegionRef::root(),
)
}
let label_used = pass_compute_label_used(func)
// Build the function-wide relation lazily on the first zero-param multivalue
// root that can need it. Scalar-only functions avoid the extra full scan;
// functions with relevant roots still build at most one immutable snapshot.
let drop_parent_index = MergeBlocksDropParentIndex::new()
let flattened_roots : Array[Int32] = []
let branch_workspace = MergeBlocksBranchScanWorkspace::new()
changed = merge_blocks_visit_region(
func,
@ir.HotRegionRef::root(),
label_used,
drop_parent_index,
flattened_roots,
branch_workspace,
ctx.module_ctx,
false,
false,
) ||
changed
match ctx.perf {
Some(_) =>
if drop_parent_index.uses.length() > 0 {
(ctx.trace)(
"pass[merge-blocks]:drop-parent-index full_function_scans=1 live_nodes_scanned=\{drop_parent_index.live_nodes_scanned} drop_child_slots=\{drop_parent_index.drop_child_slots}",
)
}
None => ()
}
if !changed {
return HotPassResult::unchanged()
}
pass_mark_mutated(ctx, func)
HotPassResult::changed()
}