// 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 2021 WebAssembly Community Group participants
// Counterpart: src/passes/LocalSubtyping.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.

///|
pub fn local_subtyping_summary() -> String {
  "Narrow reference-typed body locals to the most specific safe supertype of their writes."
}

///|
fn ls_imported_func_count(mod_ : @lib.Module) -> Int32 {
  let mut count = 0
  match mod_.import_sec {
    Some(@lib.ImportSec(imports)) =>
      for import_ in imports {
        match import_ {
          @lib.Import(_, _, @lib.FuncExternType(_)) => count += 1
          _ => ()
        }
      }
    None => ()
  }
  count
}

///|
fn ls_abs_heap_is_subtype(
  source : @lib.AbsHeapType,
  target : @lib.AbsHeapType,
) -> Bool {
  if source == target {
    return true
  }
  match (source, target) {
    (@lib.NoneAbsHeapType, @lib.AnyAbsHeapType)
    | (@lib.NoneAbsHeapType, @lib.EqAbsHeapType)
    | (@lib.NoneAbsHeapType, @lib.I31AbsHeapType)
    | (@lib.NoneAbsHeapType, @lib.StructAbsHeapType)
    | (@lib.NoneAbsHeapType, @lib.ArrayAbsHeapType)
    | (@lib.NoneAbsHeapType, @lib.StringAbsHeapType)
    | (@lib.NoFuncAbsHeapType, @lib.FuncAbsHeapType)
    | (@lib.NoContAbsHeapType, @lib.ContAbsHeapType)
    | (@lib.NoWaitqueueAbsHeapType, @lib.WaitqueueAbsHeapType)
    | (@lib.StringAbsHeapType, @lib.ExternAbsHeapType)
    | (@lib.NoExternAbsHeapType, @lib.ExternAbsHeapType)
    | (@lib.NoExnAbsHeapType, @lib.ExnAbsHeapType)
    | (@lib.I31AbsHeapType, @lib.EqAbsHeapType)
    | (@lib.I31AbsHeapType, @lib.AnyAbsHeapType)
    | (@lib.StructAbsHeapType, @lib.EqAbsHeapType)
    | (@lib.StructAbsHeapType, @lib.AnyAbsHeapType)
    | (@lib.ArrayAbsHeapType, @lib.EqAbsHeapType)
    | (@lib.ArrayAbsHeapType, @lib.AnyAbsHeapType)
    | (@lib.EqAbsHeapType, @lib.AnyAbsHeapType) => true
    _ => false
  }
}

///|
fn ls_comptype_matches_abs(ct : @lib.CompType, abs : @lib.AbsHeapType) -> Bool {
  match ct {
    @lib.StructCompType(_) =>
      abs == @lib.AbsHeapType::struct_() ||
      abs == @lib.AbsHeapType::eq() ||
      abs == @lib.AbsHeapType::any()
    @lib.ArrayCompType(_) =>
      abs == @lib.AbsHeapType::array() ||
      abs == @lib.AbsHeapType::eq() ||
      abs == @lib.AbsHeapType::any()
    @lib.FuncCompType(_, _) => abs == @lib.AbsHeapType::func()
    @lib.ContCompType(_) => abs == @lib.AbsHeapType::cont()
  }
}

///|
fn ls_subtype_as_heap_is_subtype(
  module_ctx : @ir.HotModuleContext,
  subtype : @lib.SubType,
  target : @lib.HeapType,
  fuel : Int32,
) -> Bool {
  if fuel <= 0 {
    return false
  }
  let (is_final, supers, ct) = match subtype {
    @lib.CompTypeSubType(_, ct) => (false, [], ct)
    @lib.SubType(is_final, supers, _, ct) => (is_final, supers, ct)
  }
  match target {
    @lib.AbsHeapTypeHeapType(abs) => {
      if ls_comptype_matches_abs(ct, abs) {
        return true
      }
      if is_final {
        return false
      }
    }
    _ => ()
  }
  for super_idx in supers {
    if ls_heap_is_subtype(
        module_ctx,
        @lib.HeapType::new(super_idx),
        target,
        fuel - 1,
      ) {
      return true
    }
  }
  false
}

///|
fn ls_heap_is_subtype(
  module_ctx : @ir.HotModuleContext,
  source : @lib.HeapType,
  target : @lib.HeapType,
  fuel : Int32,
) -> Bool {
  if source == target {
    return true
  }
  if fuel <= 0 {
    return false
  }
  match (source, target) {
    (@lib.AbsHeapTypeHeapType(source_abs), @lib.AbsHeapTypeHeapType(target_abs)) =>
      ls_abs_heap_is_subtype(source_abs, target_abs)
    (@lib.HeapType(source_idx), _) =>
      match @ir.hot_module_resolve_subtype(module_ctx, source_idx) {
        Some(subtype) =>
          ls_subtype_as_heap_is_subtype(module_ctx, subtype, target, fuel - 1)
        None => false
      }
    (_, @lib.HeapType(target_idx)) =>
      match source {
        @lib.AbsHeapTypeHeapType(@lib.NoneAbsHeapType) =>
          match @ir.hot_module_resolve_subtype(module_ctx, target_idx) {
            Some(subtype) =>
              match subtype.get_comptype() {
                @lib.StructCompType(_) | @lib.ArrayCompType(_) => true
                _ => false
              }
            None => false
          }
        @lib.AbsHeapTypeHeapType(@lib.NoFuncAbsHeapType) =>
          match @ir.hot_module_resolve_subtype(module_ctx, target_idx) {
            Some(subtype) =>
              match subtype.get_comptype() {
                @lib.FuncCompType(_, _) => true
                _ => false
              }
            None => false
          }
        _ => false
      }
    _ => false
  }
}

///|
fn ls_ref_is_subtype(
  module_ctx : @ir.HotModuleContext,
  source : @lib.RefType,
  target : @lib.RefType,
) -> Bool {
  if source.is_nullable() && !target.is_nullable() {
    return false
  }
  if target.is_exact() {
    if source.is_exact() && source.get_heap_type() == target.get_heap_type() {
      return true
    }
    let target_idx = match target.get_heap_type() {
      @lib.HeapType(type_idx) => type_idx
      _ => return false
    }
    let target_comp = match
      @ir.hot_module_resolve_subtype(module_ctx, target_idx) {
      Some(subtype) => subtype.get_comptype()
      None => return false
    }
    return match (source.get_heap_type(), target_comp) {
      (
        @lib.AbsHeapTypeHeapType(@lib.NoneAbsHeapType),
        @lib.StructCompType(_)
        | @lib.ArrayCompType(_),
      )
      | (
        @lib.AbsHeapTypeHeapType(@lib.NoFuncAbsHeapType),
        @lib.FuncCompType(_, _),
      )
      | (@lib.AbsHeapTypeHeapType(@lib.NoContAbsHeapType), @lib.ContCompType(_)) =>
        true
      _ => false
    }
  }
  ls_heap_is_subtype(
    module_ctx,
    source.get_heap_type(),
    target.get_heap_type(),
    512,
  )
}

///|
fn ls_as_ref(vt : @lib.ValType) -> @lib.RefType? {
  match vt {
    @lib.RefTypeValType(ref_type) => Some(ref_type)
    _ => None
  }
}

///|
fn ls_local_idx_raw(idx : @lib.LocalIdx) -> Int32 {
  let @lib.LocalIdx(raw) = idx
  raw.reinterpret_as_int()
}

///|
fn ls_ref_body_local_mask(body_locals : @lib.Locals) -> Array[Bool]? {
  let body_local_count = body_locals.length()
  let mask : Array[Bool] = Array::new(capacity=body_local_count)
  let mut has_ref = false
  for body_idx = 0; body_idx < body_local_count; body_idx = body_idx + 1 {
    match ls_as_ref(body_locals[body_idx]) {
      Some(_) => {
        mask.push(true)
        has_ref = true
      }
      None => mask.push(false)
    }
  }
  if has_ref {
    Some(mask)
  } else {
    None
  }
}

///|
fn ls_write_targets_ref_body_local(
  idx : @lib.LocalIdx,
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Bool {
  let raw = ls_local_idx_raw(idx)
  let body_idx = raw - param_count
  body_idx >= 0 &&
  body_idx < ref_body_locals.length() &&
  ref_body_locals[body_idx]
}

///|
fn ls_instrs_write_ref_body_local(
  instrs : Array[@lib.Instruction],
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Bool {
  for instr in instrs {
    match instr {
      @lib.Block(_, body) | @lib.Loop(_, body) | @lib.TryTable(_, _, body) =>
        if ls_expr_writes_ref_body_local(body, param_count, ref_body_locals) {
          return true
        }
      @lib.If(_, then_body, else_body) => {
        if ls_instrs_write_ref_body_local(
            then_body, param_count, ref_body_locals,
          ) {
          return true
        }
        match else_body {
          Some(body) =>
            if ls_instrs_write_ref_body_local(
                body, param_count, ref_body_locals,
              ) {
              return true
            }
          None => ()
        }
      }
      @lib.LocalSet(idx) | @lib.LocalTee(idx) =>
        if ls_write_targets_ref_body_local(idx, param_count, ref_body_locals) {
          return true
        }
      _ => ()
    }
  }
  false
}

///|
fn ls_expr_writes_ref_body_local(
  expr : @lib.Expr,
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Bool {
  let @lib.Expr(instrs) = expr
  ls_instrs_write_ref_body_local(instrs, param_count, ref_body_locals)
}

///|
fn ls_count_ref_body_local_writes_instrs(
  instrs : Array[@lib.Instruction],
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Int32 {
  let mut count = 0
  for instr in instrs {
    match instr {
      @lib.Block(_, body) | @lib.Loop(_, body) | @lib.TryTable(_, _, body) =>
        count += ls_count_ref_body_local_writes_expr(
          body, param_count, ref_body_locals,
        )
      @lib.If(_, then_body, else_body) => {
        count += ls_count_ref_body_local_writes_instrs(
          then_body, param_count, ref_body_locals,
        )
        match else_body {
          Some(body) =>
            count += ls_count_ref_body_local_writes_instrs(
              body, param_count, ref_body_locals,
            )
          None => ()
        }
      }
      @lib.LocalSet(idx) | @lib.LocalTee(idx) =>
        if ls_write_targets_ref_body_local(idx, param_count, ref_body_locals) {
          count += 1
        }
      _ => ()
    }
  }
  count
}

///|
fn ls_count_ref_body_local_writes_expr(
  expr : @lib.Expr,
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Int32 {
  let @lib.Expr(instrs) = expr
  ls_count_ref_body_local_writes_instrs(instrs, param_count, ref_body_locals)
}

///|
fn ls_assignment_count(assignments : Array[Array[@lib.ValType]]) -> Int32 {
  let mut count = 0
  for local_assignments in assignments {
    count += local_assignments.length()
  }
  count
}

///|
fn ls_catches_include_ref_flow(catches : Array[@lib.Catch]) -> Bool {
  for catch_ in catches {
    match catch_ {
      @lib.CatchRef(_, _) | @lib.CatchAllRef(_) => return true
      _ => ()
    }
  }
  false
}

///|
fn ls_instrs_include_ref_catch_flow(instrs : Array[@lib.Instruction]) -> Bool {
  for instr in instrs {
    match instr {
      @lib.TryTable(_, catches, body) => {
        if ls_catches_include_ref_flow(catches) {
          return true
        }
        if ls_expr_includes_ref_catch_flow(body) {
          return true
        }
      }
      @lib.Block(_, body) | @lib.Loop(_, body) =>
        if ls_expr_includes_ref_catch_flow(body) {
          return true
        }
      @lib.If(_, then_body, else_body) => {
        if ls_instrs_include_ref_catch_flow(then_body) {
          return true
        }
        match else_body {
          Some(body) =>
            if ls_instrs_include_ref_catch_flow(body) {
              return true
            }
          None => ()
        }
      }
      _ => ()
    }
  }
  false
}

///|
fn ls_expr_includes_ref_catch_flow(expr : @lib.Expr) -> Bool {
  let @lib.Expr(instrs) = expr
  ls_instrs_include_ref_catch_flow(instrs)
}

///|
fn ls_ref_with_nullable(rt : @lib.RefType, nullable : Bool) -> @lib.RefType {
  @lib.RefType::new(
    nullable || rt.is_nullable(),
    rt.get_heap_type(),
    exact=rt.is_exact(),
  )
}

///|
fn ls_ref_abs_lub_candidate(
  module_ctx : @ir.HotModuleContext,
  left : @lib.RefType,
  right : @lib.RefType,
  nullable : Bool,
  abs : @lib.AbsHeapType,
) -> @lib.RefType? {
  let candidate = @lib.RefType::new(
    nullable,
    @lib.HeapType::abs(abs),
    exact=false,
  )
  if ls_ref_is_subtype(module_ctx, left, candidate) &&
    ls_ref_is_subtype(module_ctx, right, candidate) {
    Some(candidate)
  } else {
    None
  }
}

///|
fn ls_ref_concrete_super_lub(
  module_ctx : @ir.HotModuleContext,
  source_idx : @lib.TypeIdx,
  right : @lib.RefType,
  nullable : Bool,
  fuel : Int32,
) -> @lib.RefType? {
  if fuel <= 0 {
    return None
  }
  let supers = match @ir.hot_module_resolve_subtype(module_ctx, source_idx) {
    Some(@lib.SubType(_, supers, _, _)) => supers
    Some(@lib.CompTypeSubType(_, _)) | None => return None
  }
  for super_idx in supers {
    let candidate = @lib.RefType::new(
      nullable,
      @lib.HeapType::new(super_idx),
      exact=false,
    )
    if ls_ref_is_subtype(module_ctx, right, candidate) {
      return Some(candidate)
    }
    match
      ls_ref_concrete_super_lub(
        module_ctx,
        super_idx,
        right,
        nullable,
        fuel - 1,
      ) {
      Some(common) => return Some(common)
      None => ()
    }
  }
  None
}

///|
fn ls_ref_pair_lub(
  module_ctx : @ir.HotModuleContext,
  left : @lib.RefType,
  right : @lib.RefType,
) -> @lib.RefType? {
  let nullable = left.is_nullable() || right.is_nullable()
  let nullable_left = ls_ref_with_nullable(left, nullable)
  let nullable_right = ls_ref_with_nullable(right, nullable)
  if ls_ref_is_subtype(module_ctx, left, nullable_right) {
    return Some(nullable_right)
  }
  if ls_ref_is_subtype(module_ctx, right, nullable_left) {
    return Some(nullable_left)
  }
  match left.get_heap_type() {
    @lib.HeapType(left_idx) =>
      match
        ls_ref_concrete_super_lub(module_ctx, left_idx, right, nullable, 512) {
        Some(common) => return Some(common)
        None => ()
      }
    _ => ()
  }
  let abstract_candidates = [
    @lib.AbsHeapType::i31(),
    @lib.AbsHeapType::struct_(),
    @lib.AbsHeapType::array(),
    @lib.AbsHeapType::string_(),
    @lib.AbsHeapType::func(),
    @lib.AbsHeapType::cont(),
    @lib.AbsHeapType::exn(),
    @lib.AbsHeapType::extern_(),
    @lib.AbsHeapType::eq(),
    @lib.AbsHeapType::any(),
  ]
  for abs in abstract_candidates {
    match ls_ref_abs_lub_candidate(module_ctx, left, right, nullable, abs) {
      Some(candidate) => return Some(candidate)
      None => ()
    }
  }
  None
}

///|
fn ls_candidate_select_type(
  declared : @lib.ValType?,
  left : @lib.ValType,
  right : @lib.ValType,
  module_ctx : @ir.HotModuleContext,
) -> @lib.ValType? {
  let left_ref = match ls_as_ref(left) {
    Some(ref_type) => ref_type
    None => return None
  }
  let right_ref = match ls_as_ref(right) {
    Some(ref_type) => ref_type
    None => return None
  }
  let candidate = match ls_ref_pair_lub(module_ctx, left_ref, right_ref) {
    Some(ref_type) => @lib.ValType::ref_type(ref_type)
    None => return None
  }
  match declared {
    Some(declared_type) => {
      if candidate == declared_type {
        return None
      }
      let candidate_ref = match ls_as_ref(candidate) {
        Some(ref_type) => ref_type
        None => return None
      }
      let declared_ref = match ls_as_ref(declared_type) {
        Some(ref_type) => ref_type
        None => return None
      }
      if ls_ref_is_subtype(module_ctx, candidate_ref, declared_ref) {
        Some(candidate)
      } else {
        None
      }
    }
    None => Some(candidate)
  }
}

///|
fn ls_candidate_local_type(
  declared : @lib.ValType,
  assigned : Array[@lib.ValType],
  module_ctx : @ir.HotModuleContext,
  allow_non_null : Bool,
) -> @lib.ValType? {
  let declared_ref = match ls_as_ref(declared) {
    Some(ref_type) => ref_type
    None => return None
  }
  if assigned.is_empty() {
    return None
  }
  let mut best : @lib.RefType? = None
  for vt in assigned {
    let assigned_ref = match ls_as_ref(vt) {
      Some(ref_type) => ref_type
      None => return None
    }
    best = match best {
      None => Some(assigned_ref)
      Some(best_ref) => ls_ref_pair_lub(module_ctx, best_ref, assigned_ref)
    }
    if best is None {
      return None
    }
  }
  let best_ref = match best {
    Some(ref_type) => ref_type
    None => return None
  }
  let candidate = @lib.RefType::new(
    if allow_non_null {
      best_ref.is_nullable()
    } else {
      declared_ref.is_nullable() || best_ref.is_nullable()
    },
    best_ref.get_heap_type(),
    exact=declared_ref.is_exact() && best_ref.is_exact(),
  )
  if !ls_ref_is_subtype(module_ctx, candidate, declared_ref) {
    return None
  }
  let result = @lib.ValType::ref_type(candidate)
  if result == declared {
    None
  } else {
    Some(result)
  }
}

///|
fn ls_body_local_idx(
  idx : @lib.LocalIdx,
  param_count : Int32,
  body_local_count : Int32,
) -> Int32? {
  let raw = ls_local_idx_raw(idx)
  let body_idx = raw - param_count
  if body_idx >= 0 && body_idx < body_local_count {
    Some(body_idx)
  } else {
    None
  }
}

///|
fn ls_local_declared_type(
  idx : @lib.LocalIdx,
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
) -> @lib.ValType? {
  let raw = ls_local_idx_raw(idx)
  if raw < 0 {
    return None
  }
  if raw < param_types.length() {
    return Some(param_types[raw])
  }
  let body_idx = raw - param_types.length()
  if body_idx >= 0 && body_idx < body_locals.length() {
    Some(body_locals[body_idx])
  } else {
    None
  }
}

///|
fn ls_select_declared_type(types : Array[@lib.ValType]?) -> @lib.ValType? {
  match types {
    Some([single]) => Some(single)
    _ => None
  }
}

///|
fn ls_label_idx_raw(idx : @lib.LabelIdx) -> Int32 {
  let @lib.LabelIdx(raw) = idx
  raw.reinterpret_as_int()
}

///|
fn ls_refined_control_type(
  declared : @lib.ValType,
  candidates : Array[@lib.ValType],
  module_ctx : @ir.HotModuleContext,
) -> @lib.ValType? {
  let declared_ref = match ls_as_ref(declared) {
    Some(ref_type) => ref_type
    None => return None
  }
  let mut best : @lib.RefType? = None
  for candidate in candidates {
    let candidate_ref = match ls_as_ref(candidate) {
      Some(ref_type) => ref_type
      None => return None
    }
    best = match best {
      None => Some(candidate_ref)
      Some(best_ref) => ls_ref_pair_lub(module_ctx, best_ref, candidate_ref)
    }
    if best is None {
      return None
    }
  }
  let best_ref = match best {
    Some(ref_type) => ref_type
    None => return None
  }
  if !ls_ref_is_subtype(module_ctx, best_ref, declared_ref) {
    return None
  }
  let result = @lib.ValType::ref_type(best_ref)
  if result == declared {
    None
  } else {
    Some(result)
  }
}

///|
fn ls_control_value_stack_apply(
  instr : @lib.Instruction,
  stack : Array[@lib.ValType?],
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
) -> Unit {
  match instr {
    @lib.I32Const(_) => stack.push(Some(@lib.ValType::i32()))
    @lib.I64Const(_) => stack.push(Some(@lib.ValType::i64()))
    @lib.F32Const(_) => stack.push(Some(@lib.ValType::f32()))
    @lib.F64Const(_) => stack.push(Some(@lib.ValType::f64()))
    @lib.LocalGet(idx) =>
      stack.push(ls_local_declared_type(idx, param_types, body_locals))
    @lib.RefI31 => {
      ignore(ls_raw_stack_pop(stack))
      stack.push(
        Some(
          @lib.ValType::ref_type(
            @lib.RefType::new(
              false,
              @lib.HeapType::abs(@lib.AbsHeapType::i31()),
            ),
          ),
        ),
      )
    }
    @lib.Drop => ignore(ls_raw_stack_pop(stack))
    @lib.Block(block_type, _)
    | @lib.Loop(block_type, _)
    | @lib.TryTable(block_type, _, _) => {
      stack.clear()
      match ls_block_type_results(block_type, module_ctx) {
        Some(results) => ls_raw_stack_push_result_types(stack, results)
        None => stack.push(None)
      }
    }
    @lib.If(block_type, _, _) => {
      ignore(ls_raw_stack_pop(stack))
      stack.clear()
      match ls_block_type_results(block_type, module_ctx) {
        Some(results) => ls_raw_stack_push_result_types(stack, results)
        None => stack.push(None)
      }
    }
    _ =>
      match ls_raw_ref_producer_type(instr, module_ctx) {
        Some(vt) => {
          stack.clear()
          stack.push(Some(vt))
        }
        None => stack.clear()
      }
  }
}

///|
fn ls_control_result_candidates(
  instrs : Array[@lib.Instruction],
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
  collect_direct_branches : Bool,
) -> Array[@lib.ValType] {
  let candidates : Array[@lib.ValType] = []
  let stack : Array[@lib.ValType?] = []
  let mut falls_through = true
  for instr in instrs {
    match instr {
      @lib.Br(label_idx) => {
        if collect_direct_branches && ls_label_idx_raw(label_idx) == 0 {
          match stack.last() {
            Some(Some(vt)) => candidates.push(vt)
            _ => ()
          }
        }
        stack.clear()
        falls_through = false
      }
      @lib.Return
      | @lib.ReturnCall(_)
      | @lib.ReturnCallIndirect(_, _)
      | @lib.ReturnCallRef(_)
      | @lib.Throw(_)
      | @lib.ThrowRef
      | @lib.Unreachable => {
        stack.clear()
        falls_through = false
      }
      _ => {
        ls_control_value_stack_apply(
          instr, stack, param_types, body_locals, module_ctx,
        )
        falls_through = true
      }
    }
  }
  if falls_through {
    match stack.last() {
      Some(Some(vt)) => candidates.push(vt)
      _ => ()
    }
  }
  candidates
}

///|
fn ls_control_refinalization_shape_supported(
  instrs : Array[@lib.Instruction],
  allow_direct_branch : Bool,
) -> Bool {
  if instrs.is_empty() {
    return false
  }
  for instr in instrs {
    match instr {
      @lib.I32Const(_) | @lib.RefI31 => ()
      @lib.Br(label_idx) =>
        if !allow_direct_branch || ls_label_idx_raw(label_idx) != 0 {
          return false
        }
      _ => return false
    }
  }
  true
}

///|
fn ls_refine_control_results_instrs(
  instrs : Array[@lib.Instruction],
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
) -> (Array[@lib.Instruction], Bool) {
  let rewritten : Array[@lib.Instruction] = Array::new(capacity=instrs.length())
  let mut changed = false
  for instr in instrs {
    let next = match instr {
      @lib.Block(block_type, @lib.Expr(body)) => {
        let (next_body, body_changed) = ls_refine_control_results_instrs(
          body, param_types, body_locals, module_ctx,
        )
        let next_type = if ls_instrs_include_ref_catch_flow(next_body) ||
          !ls_control_refinalization_shape_supported(next_body, true) {
          None
        } else {
          match block_type {
            @lib.ValTypeBlockType(declared) =>
              ls_refined_control_type(
                declared,
                ls_control_result_candidates(
                  next_body, param_types, body_locals, module_ctx, true,
                ),
                module_ctx,
              )
            _ => None
          }
        }
        if body_changed || next_type is Some(_) {
          changed = true
          @lib.Instruction::block(
            match next_type {
              Some(vt) => @lib.BlockType::val_type(vt)
              None => block_type
            },
            @lib.Expr::new(next_body),
          )
        } else {
          instr
        }
      }
      @lib.Loop(block_type, @lib.Expr(body)) => {
        let (next_body, body_changed) = ls_refine_control_results_instrs(
          body, param_types, body_locals, module_ctx,
        )
        if body_changed {
          changed = true
          @lib.Instruction::loop_(block_type, @lib.Expr::new(next_body))
        } else {
          instr
        }
      }
      @lib.TryTable(block_type, catches, @lib.Expr(body)) => {
        let (next_body, body_changed) = ls_refine_control_results_instrs(
          body, param_types, body_locals, module_ctx,
        )
        if body_changed {
          changed = true
          @lib.Instruction::try_table(
            block_type,
            catches,
            @lib.Expr::new(next_body),
          )
        } else {
          instr
        }
      }
      @lib.If(block_type, then_body, else_body) => {
        let (next_then, then_changed) = ls_refine_control_results_instrs(
          then_body, param_types, body_locals, module_ctx,
        )
        let (next_else, else_changed) = match else_body {
          Some(body) => {
            let (next, next_changed) = ls_refine_control_results_instrs(
              body, param_types, body_locals, module_ctx,
            )
            (Some(next), next_changed)
          }
          None => (None, false)
        }
        let next_type = match (block_type, next_else) {
          (@lib.ValTypeBlockType(declared), Some(else_instrs)) =>
            if ls_control_refinalization_shape_supported(next_then, false) &&
              ls_control_refinalization_shape_supported(else_instrs, false) {
              let candidates = ls_control_result_candidates(
                next_then, param_types, body_locals, module_ctx, false,
              )
              let else_candidates = ls_control_result_candidates(
                else_instrs, param_types, body_locals, module_ctx, false,
              )
              for candidate in else_candidates {
                candidates.push(candidate)
              }
              ls_refined_control_type(declared, candidates, module_ctx)
            } else {
              None
            }
          _ => None
        }
        if then_changed || else_changed || next_type is Some(_) {
          changed = true
          @lib.Instruction::if_(
            match next_type {
              Some(vt) => @lib.BlockType::val_type(vt)
              None => block_type
            },
            next_then,
            next_else,
          )
        } else {
          instr
        }
      }
      _ => instr
    }
    rewritten.push(next)
  }
  (rewritten, changed)
}

///|
fn ls_refine_control_results_expr(
  expr : @lib.Expr,
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
) -> (@lib.Expr, Bool) {
  let @lib.Expr(instrs) = expr
  let (next, changed) = ls_refine_control_results_instrs(
    instrs, param_types, body_locals, module_ctx,
  )
  if changed {
    (@lib.Expr::new(next), true)
  } else {
    (expr, false)
  }
}

///|
priv struct LsFuncShape {
  params : Array[@lib.ValType]
  results : Array[@lib.ValType]
}

///|
fn LsFuncShape::new(
  params : Array[@lib.ValType],
  results : Array[@lib.ValType],
) -> LsFuncShape {
  { params, results, }
}

///|
fn ls_resolve_func_type_idx(
  module_ctx : @ir.HotModuleContext,
  type_idx : @lib.TypeIdx,
) -> LsFuncShape? {
  match @ir.hot_module_resolve_subtype(module_ctx, type_idx) {
    Some(subtype) =>
      match subtype.get_comptype() {
        @lib.FuncCompType(params, results) =>
          Some(LsFuncShape::new(params, results))
        _ => None
      }
    None => None
  }
}

///|
fn ls_val_is_subtype(
  module_ctx : @ir.HotModuleContext,
  source : @lib.ValType,
  target : @lib.ValType,
) -> Bool {
  if source == target {
    return true
  }
  match (ls_as_ref(source), ls_as_ref(target)) {
    (Some(source_ref), Some(target_ref)) =>
      ls_ref_is_subtype(module_ctx, source_ref, target_ref)
    _ => false
  }
}

///|
fn ls_results_are_subtypes(
  module_ctx : @ir.HotModuleContext,
  source : Array[@lib.ValType],
  target : Array[@lib.ValType],
) -> Bool {
  if source.length() != target.length() {
    return false
  }
  for idx = 0; idx < source.length(); idx = idx + 1 {
    if !ls_val_is_subtype(module_ctx, source[idx], target[idx]) {
      return false
    }
  }
  true
}

///|
fn ls_candidate_call_ref_type(
  current_type_idx : @lib.TypeIdx,
  target_type : @lib.ValType,
  module_ctx : @ir.HotModuleContext,
) -> @lib.TypeIdx? {
  let target_ref = match ls_as_ref(target_type) {
    Some(ref_type) => ref_type
    None => return None
  }
  let target_type_idx = match target_ref.get_heap_type() {
    @lib.HeapType(type_idx) => type_idx
    _ => return None
  }
  if target_type_idx == current_type_idx {
    return None
  }
  let current_shape = match
    ls_resolve_func_type_idx(module_ctx, current_type_idx) {
    Some(func_type) => func_type
    None => return None
  }
  let target_shape = match
    ls_resolve_func_type_idx(module_ctx, target_type_idx) {
    Some(func_type) => func_type
    None => return None
  }
  if target_shape.params != current_shape.params {
    return None
  }
  if !ls_results_are_subtypes(
      module_ctx,
      target_shape.results,
      current_shape.results,
    ) {
    return None
  }
  if !ls_heap_is_subtype(
      module_ctx,
      target_ref.get_heap_type(),
      @lib.HeapType::new(current_type_idx),
      512,
    ) {
    return None
  }
  Some(target_type_idx)
}

///|
fn ls_call_ref_has_no_params(
  module_ctx : @ir.HotModuleContext,
  type_idx : @lib.TypeIdx,
) -> Bool {
  match ls_resolve_func_type_idx(module_ctx, type_idx) {
    Some(shape) => shape.params.is_empty()
    None => false
  }
}

///|
fn ls_is_nullable_nofunc_ref(val_type : @lib.ValType) -> Bool {
  match ls_as_ref(val_type) {
    Some(ref_type) =>
      ref_type.is_nullable() &&
      ref_type.get_heap_type() ==
      @lib.HeapType::abs(@lib.AbsHeapType::no_func())
    None => false
  }
}

///|
fn ls_refine_selects_instrs(
  instrs : Array[@lib.Instruction],
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
) -> (Array[@lib.Instruction], Bool) {
  let rewritten : Array[@lib.Instruction] = Array::new(capacity=instrs.length())
  let mut changed = false
  for instr in instrs {
    let next_instr = match instr {
      @lib.Block(block_type, body) => {
        let (next_body, body_changed) = ls_refine_selects_expr(
          body, param_types, body_locals, module_ctx,
        )
        if body_changed {
          changed = true
          @lib.Instruction::block(block_type, next_body)
        } else {
          instr
        }
      }
      @lib.Loop(block_type, body) => {
        let (next_body, body_changed) = ls_refine_selects_expr(
          body, param_types, body_locals, module_ctx,
        )
        if body_changed {
          changed = true
          @lib.Instruction::loop_(block_type, next_body)
        } else {
          instr
        }
      }
      @lib.TryTable(block_type, catches, body) => {
        let (next_body, body_changed) = ls_refine_selects_expr(
          body, param_types, body_locals, module_ctx,
        )
        if body_changed {
          changed = true
          @lib.Instruction::try_table(block_type, catches, next_body)
        } else {
          instr
        }
      }
      @lib.If(block_type, then_body, else_body) => {
        let (next_then, then_changed) = ls_refine_selects_instrs(
          then_body, param_types, body_locals, module_ctx,
        )
        let (next_else, else_changed) = match else_body {
          Some(body) => {
            let (next, changed) = ls_refine_selects_instrs(
              body, param_types, body_locals, module_ctx,
            )
            (Some(next), changed)
          }
          None => (None, false)
        }
        if then_changed || else_changed {
          changed = true
          @lib.Instruction::if_(block_type, next_then, next_else)
        } else {
          instr
        }
      }
      @lib.RefNull(ref_type) =>
        match ls_ref_null_normalized_type(ref_type) {
          @lib.RefTypeValType(next_ref_type) =>
            if next_ref_type == ref_type {
              instr
            } else {
              changed = true
              @lib.Instruction::ref_null_type(next_ref_type)
            }
          _ => instr
        }
      _ => instr
    }
    match next_instr {
      @lib.Select(types) => {
        let len = rewritten.length()
        // The final instruction must independently produce the condition;
        // a unary/binary condition can consume one of the apparent values.
        let independent_condition = if len > 0 {
          match rewritten[len - 1] {
            @lib.I32Const(_) | @lib.LocalGet(_) | @lib.GlobalGet(_) => true
            _ => false
          }
        } else {
          false
        }
        let candidate = if len >= 3 && independent_condition {
          match (rewritten[len - 3], rewritten[len - 2]) {
            (@lib.LocalGet(left_idx), @lib.LocalGet(right_idx)) => {
              let left_type = match
                ls_local_declared_type(left_idx, param_types, body_locals) {
                Some(val_type) => val_type
                None => {
                  rewritten.push(next_instr)
                  continue
                }
              }
              let right_type = match
                ls_local_declared_type(right_idx, param_types, body_locals) {
                Some(val_type) => val_type
                None => {
                  rewritten.push(next_instr)
                  continue
                }
              }
              ls_candidate_select_type(
                ls_select_declared_type(types),
                left_type,
                right_type,
                module_ctx,
              )
            }
            _ => None
          }
        } else {
          None
        }
        match candidate {
          Some(val_type) => {
            rewritten.push(@lib.Instruction::select(types=Some([val_type])))
            changed = true
          }
          None => rewritten.push(next_instr)
        }
      }
      @lib.CallRef(type_idx) => {
        let len = rewritten.length()
        let target_type = if len >= 1 {
          match rewritten[len - 1] {
            @lib.LocalGet(target_idx) =>
              ls_local_declared_type(target_idx, param_types, body_locals)
            _ => None
          }
        } else {
          None
        }
        match target_type {
          Some(val_type) =>
            match ls_candidate_call_ref_type(type_idx, val_type, module_ctx) {
              Some(next_type_idx) => {
                rewritten.push(@lib.Instruction::call_ref(next_type_idx))
                changed = true
              }
              None =>
                if ls_is_nullable_nofunc_ref(val_type) &&
                  ls_call_ref_has_no_params(module_ctx, type_idx) {
                  match rewritten[len - 1] {
                    @lib.LocalGet(target_idx) => {
                      // Retain the target read at the call's evaluation position.
                      // The direct trap discards the pure local.get stack value
                      // while making the remainder of the frame polymorphic.
                      ignore(target_idx)
                      rewritten.push(@lib.Instruction::unreachable_())
                      changed = true
                    }
                    _ => rewritten.push(next_instr)
                  }
                } else {
                  rewritten.push(next_instr)
                }
            }
          None => rewritten.push(next_instr)
        }
      }
      _ => rewritten.push(next_instr)
    }
  }
  (rewritten, changed)
}

///|
fn ls_refine_selects_expr(
  expr : @lib.Expr,
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  module_ctx : @ir.HotModuleContext,
) -> (@lib.Expr, Bool) {
  let @lib.Expr(instrs) = expr
  let (next_instrs, changed) = ls_refine_selects_instrs(
    instrs, param_types, body_locals, module_ctx,
  )
  if changed {
    (@lib.Expr::new(next_instrs), true)
  } else {
    (expr, false)
  }
}

///|
fn ls_raw_assignment_slots(total_locals : Int32) -> Array[Array[@lib.ValType]] {
  let locals : Array[Array[@lib.ValType]] = []
  for idx = 0; idx < total_locals; idx = idx + 1 {
    ignore(idx)
    locals.push([])
  }
  locals
}

///|
fn ls_raw_stack_pop(stack : Array[@lib.ValType?]) -> @lib.ValType? {
  match stack.pop() {
    Some(value) => value
    None => None
  }
}

///|
fn ls_raw_stack_push_result_types(
  stack : Array[@lib.ValType?],
  results : Array[@lib.ValType],
) -> Unit {
  for result in results {
    stack.push(Some(result))
  }
}

///|
fn ls_block_type_results(
  block_type : @lib.BlockType,
  module_ctx : @ir.HotModuleContext,
) -> Array[@lib.ValType]? {
  match block_type {
    @lib.VoidBlockType => Some([])
    @lib.ValTypeBlockType(vt) => Some([vt])
    @lib.TypeIdxBlockType(type_idx) =>
      match ls_resolve_func_type_idx(module_ctx, type_idx) {
        Some(shape) => Some(shape.results)
        None => None
      }
  }
}

///|
fn ls_ref_null_normalized_type(ref_type : @lib.RefType) -> @lib.ValType {
  let heap_type = match ref_type.get_heap_type() {
    @lib.AbsHeapTypeHeapType(@lib.FuncAbsHeapType | @lib.NoFuncAbsHeapType) =>
      @lib.HeapType::abs(@lib.AbsHeapType::no_func())
    @lib.AbsHeapTypeHeapType(@lib.ExternAbsHeapType | @lib.NoExternAbsHeapType) =>
      @lib.HeapType::abs(@lib.AbsHeapType::no_extern())
    @lib.AbsHeapTypeHeapType(@lib.ExnAbsHeapType | @lib.NoExnAbsHeapType) =>
      @lib.HeapType::abs(@lib.AbsHeapType::no_exn())
    @lib.AbsHeapTypeHeapType(@lib.ContAbsHeapType | @lib.NoContAbsHeapType) =>
      @lib.HeapType::abs(@lib.AbsHeapType::no_cont())
    @lib.AbsHeapTypeHeapType(
      @lib.WaitqueueAbsHeapType
      | @lib.NoWaitqueueAbsHeapType
    ) => @lib.HeapType::abs(@lib.AbsHeapType::no_waitqueue())
    @lib.AbsHeapTypeHeapType(_) => @lib.HeapType::abs(@lib.AbsHeapType::none())
    other => other
  }
  @lib.ValType::ref_type(
    @lib.RefType::new(true, heap_type, exact=ref_type.is_exact()),
  )
}

///|
fn ls_raw_ref_producer_type(
  instr : @lib.Instruction,
  module_ctx : @ir.HotModuleContext,
) -> @lib.ValType? {
  match instr {
    @lib.RefNull(ref_type) => Some(ls_ref_null_normalized_type(ref_type))
    @lib.RefFunc(func_idx) =>
      match @ir.hot_module_resolve_func_type_idx(module_ctx, func_idx) {
        Some(type_idx) =>
          Some(
            @lib.ValType::ref_type(
              @lib.RefType::new(false, @lib.HeapType::new(type_idx), exact=true),
            ),
          )
        None => None
      }
    @lib.StructNew(type_idx)
    | @lib.StructNewDefault(type_idx)
    | @lib.StructNewDesc(type_idx)
    | @lib.StructNewDefaultDesc(type_idx) =>
      Some(
        @lib.ValType::ref_type(
          @lib.RefType::new(false, @lib.HeapType::new(type_idx), exact=true),
        ),
      )
    @lib.ArrayNew(type_idx)
    | @lib.ArrayNewDefault(type_idx)
    | @lib.ArrayNewFixed(type_idx, _)
    | @lib.ArrayNewData(type_idx, _)
    | @lib.ArrayNewElem(type_idx, _) =>
      Some(
        @lib.ValType::ref_type(
          @lib.RefType::new(false, @lib.HeapType::new(type_idx), exact=true),
        ),
      )
    _ => None
  }
}

///|
fn ls_record_raw_assignment(
  locals : Array[Array[@lib.ValType]],
  target_idx : @lib.LocalIdx,
  assigned_type : @lib.ValType?,
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  ref_body_locals : Array[Bool],
  unknown_falls_back : Bool,
) -> Unit {
  let local_raw = ls_local_idx_raw(target_idx)
  let body_idx = local_raw - param_types.length()
  if body_idx < 0 ||
    body_idx >= ref_body_locals.length() ||
    !ref_body_locals[body_idx] ||
    local_raw < 0 ||
    local_raw >= locals.length() {
    return
  }
  match assigned_type {
    Some(vt) => locals[local_raw].push(vt)
    None =>
      if unknown_falls_back {
        match ls_local_declared_type(target_idx, param_types, body_locals) {
          Some(vt) => locals[local_raw].push(vt)
          None => ()
        }
      }
  }
}

///|
fn ls_collect_raw_assignments_instrs(
  instrs : Array[@lib.Instruction],
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  ref_body_locals : Array[Bool],
  module_ctx : @ir.HotModuleContext,
  locals : Array[Array[@lib.ValType]],
  unknown_falls_back : Bool,
) -> Unit {
  let stack : Array[@lib.ValType?] = []
  for instr in instrs {
    match instr {
      @lib.I32Const(_) => stack.push(Some(@lib.ValType::i32()))
      @lib.I64Const(_) => stack.push(Some(@lib.ValType::i64()))
      @lib.F32Const(_) => stack.push(Some(@lib.ValType::f32()))
      @lib.F64Const(_) => stack.push(Some(@lib.ValType::f64()))
      @lib.V128Const(_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _) =>
        stack.push(Some(@lib.ValType::v128()))
      @lib.Unreachable => {
        stack.clear()
        // A following reference write can take the polymorphic bottom value.
        // The candidate subtype check rejects this heap for other hierarchies.
        stack.push(
          Some(
            @lib.ValType::ref_type(
              @lib.RefType::new(
                false,
                @lib.HeapType::abs(@lib.AbsHeapType::none()),
              ),
            ),
          ),
        )
      }
      @lib.LocalGet(idx) =>
        stack.push(ls_local_declared_type(idx, param_types, body_locals))
      @lib.LocalSet(idx) =>
        ls_record_raw_assignment(
          locals,
          idx,
          ls_raw_stack_pop(stack),
          param_types,
          body_locals,
          ref_body_locals,
          unknown_falls_back,
        )
      @lib.LocalTee(idx) => {
        let assigned_type = ls_raw_stack_pop(stack)
        ls_record_raw_assignment(
          locals, idx, assigned_type, param_types, body_locals, ref_body_locals,
          unknown_falls_back,
        )
        // local.tee returns its declared storage type, which can be wider
        // than this one value. Another write can keep that storage broad.
        stack.push(ls_local_declared_type(idx, param_types, body_locals))
      }
      @lib.Drop => ignore(ls_raw_stack_pop(stack))
      @lib.RefAsNonNull => {
        let next_type = match ls_raw_stack_pop(stack) {
          Some(@lib.RefTypeValType(ref_type)) =>
            Some(
              @lib.ValType::ref_type(
                @lib.RefType::new(
                  false,
                  ref_type.get_heap_type(),
                  exact=ref_type.is_exact(),
                ),
              ),
            )
          _ => None
        }
        stack.push(next_type)
      }
      @lib.Select(types) => {
        ignore(ls_raw_stack_pop(stack))
        let right = ls_raw_stack_pop(stack)
        let left = ls_raw_stack_pop(stack)
        let candidate = match types {
          Some([declared]) => Some(declared)
          _ =>
            match (left, right) {
              (Some(left_type), Some(right_type)) =>
                ls_candidate_select_type(
                  None,
                  left_type,
                  right_type,
                  module_ctx,
                )
              _ => None
            }
        }
        stack.push(candidate)
      }
      @lib.Block(block_type, @lib.Expr(body))
      | @lib.Loop(block_type, @lib.Expr(body)) => {
        ls_collect_raw_assignments_instrs(
          body, param_types, body_locals, ref_body_locals, module_ctx, locals, unknown_falls_back,
        )
        stack.clear()
        match ls_block_type_results(block_type, module_ctx) {
          Some(results) => ls_raw_stack_push_result_types(stack, results)
          None => stack.push(None)
        }
      }
      @lib.TryTable(block_type, _, @lib.Expr(body)) => {
        ls_collect_raw_assignments_instrs(
          body, param_types, body_locals, ref_body_locals, module_ctx, locals, unknown_falls_back,
        )
        stack.clear()
        match ls_block_type_results(block_type, module_ctx) {
          Some(results) => ls_raw_stack_push_result_types(stack, results)
          None => stack.push(None)
        }
      }
      @lib.If(block_type, then_body, else_body) => {
        ignore(ls_raw_stack_pop(stack))
        ls_collect_raw_assignments_instrs(
          then_body, param_types, body_locals, ref_body_locals, module_ctx, locals,
          unknown_falls_back,
        )
        match else_body {
          Some(body) =>
            ls_collect_raw_assignments_instrs(
              body, param_types, body_locals, ref_body_locals, module_ctx, locals,
              unknown_falls_back,
            )
          None => ()
        }
        stack.clear()
        match ls_block_type_results(block_type, module_ctx) {
          Some(results) => ls_raw_stack_push_result_types(stack, results)
          None => stack.push(None)
        }
      }
      _ =>
        match ls_raw_ref_producer_type(instr, module_ctx) {
          Some(vt) => {
            stack.clear()
            stack.push(Some(vt))
          }
          None => stack.clear()
        }
    }
  }
}

///|
fn ls_collect_raw_assignments(
  body : @lib.Expr,
  param_types : Array[@lib.ValType],
  body_locals : @lib.Locals,
  ref_body_locals : Array[Bool],
  module_ctx : @ir.HotModuleContext,
  unknown_falls_back~ : Bool = true,
) -> Array[Array[@lib.ValType]] {
  let locals = ls_raw_assignment_slots(
    param_types.length() + body_locals.length(),
  )
  let @lib.Expr(instrs) = body
  ls_collect_raw_assignments_instrs(
    instrs, param_types, body_locals, ref_body_locals, module_ctx, locals, unknown_falls_back,
  )
  locals
}

///|
priv struct LsDominanceScanResult {
  valid : Bool
  propagates : Bool
}

///|
fn LsDominanceScanResult::new(
  valid : Bool,
  propagates : Bool,
) -> LsDominanceScanResult {
  { valid, propagates, }
}

///|
fn ls_scan_branch_free_dominance_instrs(
  instrs : Array[@lib.Instruction],
  param_count : Int32,
  ref_body_locals : Array[Bool],
  initialized : Array[Bool],
  safe : Array[Bool],
  allow_return_skip~ : Bool = false,
  allow_throw_skip~ : Bool = false,
  allow_terminal_return~ : Bool = false,
  allow_terminal_throw~ : Bool = false,
  allow_non_final_return_tail~ : Bool = false,
  allow_non_final_throw_tail~ : Bool = false,
) -> LsDominanceScanResult {
  let body_local_count = ref_body_locals.length()
  let mut allow_later_write_init = true
  let mut propagates = true
  for instr_idx = 0; instr_idx < instrs.length(); instr_idx = instr_idx + 1 {
    let instr = instrs[instr_idx]
    match instr {
      @lib.LocalGet(idx) =>
        match ls_body_local_idx(idx, param_count, body_local_count) {
          Some(body_idx) =>
            if ref_body_locals[body_idx] && !initialized[body_idx] {
              ignore(safe.set(body_idx, false))
            }
          None => ()
        }
      @lib.LocalSet(idx) | @lib.LocalTee(idx) =>
        match ls_body_local_idx(idx, param_count, body_local_count) {
          Some(body_idx) =>
            if allow_later_write_init && ref_body_locals[body_idx] {
              ignore(initialized.set(body_idx, true))
            }
          None => ()
        }
      @lib.Block(_, @lib.Expr(body)) => {
        let block_initialized = initialized.copy()
        let block_result = ls_scan_branch_free_dominance_instrs(
          body,
          param_count,
          ref_body_locals,
          block_initialized,
          safe,
          allow_return_skip~,
          allow_throw_skip~,
          allow_terminal_return=allow_terminal_return || allow_return_skip,
          allow_terminal_throw=allow_terminal_throw || allow_throw_skip,
          allow_non_final_return_tail~,
          allow_non_final_throw_tail~,
        )
        if !block_result.valid {
          return LsDominanceScanResult::new(false, false)
        }
        // WebAssembly definite initialization is scoped to each control
        // frame. Even a fallthrough write does not initialize the outer frame.
        // Keep the heap subtype improvement without exporting non-nullness.
      }
      @lib.Loop(_, @lib.Expr(body)) => {
        let loop_initialized = initialized.copy()
        let loop_result = ls_scan_branch_free_dominance_instrs(
          body, param_count, ref_body_locals, loop_initialized, safe,
        )
        if !loop_result.valid {
          return LsDominanceScanResult::new(false, false)
        }
      }
      @lib.TryTable(_, _, @lib.Expr(body)) => {
        let try_initialized = initialized.copy()
        let try_result = ls_scan_branch_free_dominance_instrs(
          body,
          param_count,
          ref_body_locals,
          try_initialized,
          safe,
          allow_terminal_return=true,
          allow_terminal_throw=true,
          allow_non_final_return_tail=true,
          allow_non_final_throw_tail=true,
        )
        if !try_result.valid {
          return LsDominanceScanResult::new(false, false)
        }
      }
      @lib.If(_, then_body, else_body) => {
        let then_initialized = initialized.copy()
        let then_result = ls_scan_branch_free_dominance_instrs(
          then_body,
          param_count,
          ref_body_locals,
          then_initialized,
          safe,
          allow_return_skip=true,
          allow_throw_skip=true,
        )
        if !then_result.valid {
          return LsDominanceScanResult::new(false, false)
        }
        match else_body {
          Some(body) => {
            let else_initialized = initialized.copy()
            let else_result = ls_scan_branch_free_dominance_instrs(
              body,
              param_count,
              ref_body_locals,
              else_initialized,
              safe,
              allow_return_skip=true,
              allow_throw_skip=true,
            )
            if !else_result.valid {
              return LsDominanceScanResult::new(false, false)
            }
          }
          None => ()
        }
      }
      @lib.Unreachable => allow_later_write_init = false
      @lib.BrIf(_) => allow_later_write_init = false
      @lib.Br(_) | @lib.BrTable(_, _) => {
        allow_later_write_init = false
        propagates = false
      }
      @lib.Return
      | @lib.ReturnCall(_)
      | @lib.ReturnCallIndirect(_, _)
      | @lib.ReturnCallRef(_) =>
        if allow_return_skip {
          ()
        } else if allow_terminal_return &&
          (allow_non_final_return_tail || instr_idx + 1 == instrs.length()) {
          allow_later_write_init = false
          propagates = false
        } else {
          return LsDominanceScanResult::new(false, false)
        }
      @lib.Throw(_) | @lib.ThrowRef =>
        if allow_throw_skip {
          ()
        } else if allow_terminal_throw &&
          (allow_non_final_throw_tail || instr_idx + 1 == instrs.length()) {
          allow_later_write_init = false
          propagates = false
        } else {
          return LsDominanceScanResult::new(false, false)
        }
      _ => ()
    }
  }
  LsDominanceScanResult::new(true, propagates)
}

///|
fn ls_non_null_dominated_linear_locals(
  expr : @lib.Expr,
  param_count : Int32,
  ref_body_locals : Array[Bool],
) -> Array[Bool] {
  let body_local_count = ref_body_locals.length()
  let initialized : Array[Bool] = []
  let safe : Array[Bool] = []
  for body_idx = 0; body_idx < body_local_count; body_idx = body_idx + 1 {
    initialized.push(false)
    safe.push(ref_body_locals[body_idx])
  }
  let @lib.Expr(instrs) = expr
  let scan_result = ls_scan_branch_free_dominance_instrs(
    instrs,
    param_count,
    ref_body_locals,
    initialized,
    safe,
    allow_terminal_return=true,
    allow_terminal_throw=true,
    allow_non_final_return_tail=true,
  )
  if !scan_result.valid {
    for body_idx = 0; body_idx < body_local_count; body_idx = body_idx + 1 {
      if ref_body_locals[body_idx] {
        ignore(safe.set(body_idx, false))
      }
    }
  }
  safe
}

///|
fn ls_ref_null_assignment_type(
  func : @ir.HotFunc,
  child : @ir.NodeId,
  fallback : @lib.ValType,
) -> @lib.ValType {
  let child_node = @ir.hot_node_get(func, child)
  match child_node.op {
    @ir.HotOp::RefNull => ()
    _ => return fallback
  }
  match @ir.hot_const_get(func, child_node.imm0) {
    @ir.HotConstPayload::RefNullConst(ref_type) =>
      ls_ref_null_normalized_type(ref_type)
    _ => fallback
  }
}

///|
fn ls_collect_assignments(func : @ir.HotFunc) -> Array[Array[@lib.ValType]] {
  let locals : Array[Array[@lib.ValType]] = []
  for i = 0; i < @ir.hot_local_count(func); i = i + 1 {
    ignore(i)
    locals.push([])
  }
  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
    }
    let node = @ir.hot_node_get(func, node_id)
    match node.op {
      @ir.HotOp::LocalSet | @ir.HotOp::LocalTee => {
        if node.imm0 < 0 || node.imm0 >= locals.length() {
          continue
        }
        if @ir.hot_child_count(func, node_id) != 1 {
          continue
        }
        let child = @ir.hot_child_get(func, node_id, 0)
        let results = @ir.hot_type_results(func, @ir.hot_node_type(func, child))
        if results.length() == 1 {
          locals[node.imm0].push(
            ls_ref_null_assignment_type(func, child, results[0]),
          )
        }
      }
      _ => ()
    }
  }
  locals
}

///|
fn ls_rewrite_func(
  func : @lib.Func,
  func_idx : @lib.FuncIdx,
  mod_ : @lib.Module,
  module_ctx : @ir.HotModuleContext,
) -> (@lib.Func, Bool) {
  let (prepared, descriptor_changed) = pass_refinalize_descriptor_func(
    mod_, func_idx, func, module_ctx,
  )
  let @lib.Func(body_locals, original_body) = prepared
  let (raw_param_count, param_types) = match
    @ir.hot_module_resolve_func_type(module_ctx, func_idx) {
    Some(@lib.FuncType(params, _)) => (params.length(), params)
    None => (-1, [])
  }
  let (body, control_refined) = if raw_param_count >= 0 {
    ls_refine_control_results_expr(
      original_body, param_types, body_locals, module_ctx,
    )
  } else {
    (original_body, false)
  }
  let control_changed = descriptor_changed || control_refined
  let ref_body_locals = match ls_ref_body_local_mask(body_locals) {
    Some(mask) => mask
    None =>
      return if control_changed {
        (@lib.Func::new(body_locals, body), true)
      } else {
        (func, false)
      }
  }
  if raw_param_count >= 0 &&
    !ls_expr_writes_ref_body_local(body, raw_param_count, ref_body_locals) {
    return if control_changed {
      (@lib.Func::new(body_locals, body), true)
    } else {
      (func, false)
    }
  }
  let has_ref_catch_flow = raw_param_count >= 0 &&
    ls_expr_includes_ref_catch_flow(body)
  let (refined_body, select_changed) = if raw_param_count >= 0 {
    ls_refine_selects_expr(body, param_types, body_locals, module_ctx)
  } else {
    (body, false)
  }
  let body_changed = control_changed || select_changed
  let (assignments, param_count, non_null_safe) = if has_ref_catch_flow {
    let fallback : Array[Bool] = []
    for body_idx = 0; body_idx < body_locals.length(); body_idx = body_idx + 1 {
      ignore(body_idx)
      fallback.push(false)
    }
    (
      ls_collect_raw_assignments(
        refined_body, param_types, body_locals, ref_body_locals, module_ctx,
      ),
      raw_param_count,
      fallback,
    )
  } else {
    let (assignments, param_count) = if raw_param_count >= 0 {
      let raw_assignments = ls_collect_raw_assignments(
        refined_body,
        param_types,
        body_locals,
        ref_body_locals,
        module_ctx,
        unknown_falls_back=false,
      )
      let write_count = ls_count_ref_body_local_writes_expr(
        refined_body, raw_param_count, ref_body_locals,
      )
      if ls_assignment_count(raw_assignments) == write_count {
        (raw_assignments, raw_param_count)
      } else {
        let hot_func = @ir.hot_lift_func_with_context(
          mod_, func_idx, module_ctx,
        )
        let assignments = ls_collect_assignments(hot_func)
        let limit = if assignments.length() < raw_assignments.length() {
          assignments.length()
        } else {
          raw_assignments.length()
        }
        for local_idx = 0; local_idx < limit; local_idx = local_idx + 1 {
          if !raw_assignments[local_idx].is_empty() &&
            raw_assignments[local_idx].length() >=
            assignments[local_idx].length() {
            ignore(assignments.set(local_idx, raw_assignments[local_idx]))
          }
        }
        (assignments, raw_param_count)
      }
    } else {
      let hot_func = @ir.hot_lift_func_with_context(mod_, func_idx, module_ctx)
      (ls_collect_assignments(hot_func), @ir.hot_local_param_count(hot_func))
    }
    let non_null_safe = if raw_param_count >= 0 {
      ls_non_null_dominated_linear_locals(
        body, raw_param_count, ref_body_locals,
      )
    } else {
      let fallback : Array[Bool] = []
      for body_idx = 0; body_idx < body_locals.length(); body_idx = body_idx + 1 {
        ignore(body_idx)
        fallback.push(false)
      }
      fallback
    }
    (assignments, param_count, non_null_safe)
  }
  let rewritten_locals = body_locals.copy()
  let mut changed = false
  for body_idx = 0; body_idx < body_locals.length(); body_idx = body_idx + 1 {
    let local_idx = param_count + body_idx
    let declared = match body_locals.at(body_idx) {
      Some(vt) => vt
      None => continue
    }
    let assigned = match assignments.get(local_idx) {
      Some(types) => types
      None => continue
    }
    let allow_non_null = match non_null_safe.get(body_idx) {
      Some(value) => value
      None => false
    }
    match
      ls_candidate_local_type(declared, assigned, module_ctx, allow_non_null) {
      Some(next) => if rewritten_locals.set(body_idx, next) { changed = true }
      None => ()
    }
  }
  if changed || body_changed {
    (@lib.Func::new(rewritten_locals, refined_body), true)
  } else {
    (func, false)
  }
}

///|
fn ls_rebuild_module(
  mod_ : @lib.Module,
  next_code_sec : @lib.CodeSec?,
) -> @lib.Module {
  @lib.Module::new(
    custom_secs=mod_.custom_secs,
    type_sec=mod_.type_sec,
    import_sec=mod_.import_sec,
    func_annotation_sec=mod_.func_annotation_sec,
    func_sec=mod_.func_sec,
    table_sec=mod_.table_sec,
    mem_sec=mod_.mem_sec,
    tag_sec=mod_.tag_sec,
    stringrefs_sec=mod_.stringrefs_sec,
    global_sec=mod_.global_sec,
    export_sec=mod_.export_sec,
    start_sec=mod_.start_sec,
    elem_sec=mod_.elem_sec,
    data_cnt_sec=mod_.data_cnt_sec,
    code_sec=next_code_sec,
    data_sec=mod_.data_sec,
    name_sec=mod_.name_sec,
  )
}

///|
fn ls_ref_body_local_iteration_limit(funcs : Array[@lib.Func]) -> Int32 {
  let mut limit = 1
  for func in funcs {
    let @lib.Func(body_locals, _) = func
    for idx = 0; idx < body_locals.length(); idx = idx + 1 {
      match ls_as_ref(body_locals[idx]) {
        Some(_) => limit += 1
        None => ()
      }
    }
  }
  limit
}

///|
fn ls_label_count(body : Array[@lib.Instruction]) -> UInt32 {
  let mut count = 0U
  for instr in body {
    match instr {
      @lib.Block(_, @lib.Expr(child))
      | @lib.Loop(_, @lib.Expr(child))
      | @lib.TryTable(_, _, @lib.Expr(child)) => {
        count += 1U
        count += ls_label_count(child)
      }
      @lib.If(_, then_body, else_body) => {
        count += 1U
        count += ls_label_count(then_body)
        match else_body {
          Some(child) => count += ls_label_count(child)
          None => ()
        }
      }
      @lib.Try(_, @lib.Expr(child), catches, _) => {
        count += 1U
        count += ls_label_count(child)
        for catch_ in catches {
          let catch_body = match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(catch_body))
            | @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
          }
          count += ls_label_count(catch_body)
        }
      }
      _ => ()
    }
  }
  count
}

///|
// An explicit root return cannot fall through. Keep its entire evaluated prefix
// and only discard the suffix; nested/conditional returns do not prove this.
fn ls_remove_return_suffixes(mod_ : @lib.Module) -> @lib.Module {
  let funcs = match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) => funcs
    None => return mod_
  }
  let label_limits : Map[UInt32, UInt32] = Map([])
  let imported = ls_imported_func_count(mod_)
  let next_funcs = funcs.mapi(fn(index, func) {
    let @lib.Func(locals, @lib.Expr(body)) = func
    for end = 0; end + 1 < body.length(); end = end + 1 {
      if body[end] is @lib.Return {
        let kept = body[0:end + 1].to_array()
        label_limits[(imported + index).to_uint()] = ls_label_count(kept)
        return @lib.Func::new(locals, @lib.Expr::new(kept))
      }
    }
    func
  })
  if label_limits.is_empty() {
    return mod_
  }
  let candidate = ls_rebuild_module(mod_, Some(@lib.CodeSec::new(next_funcs)))
  match mod_.name_sec {
    Some(names) =>
      match names.label_names {
        Some(@lib.IndirectNameMap(entries)) => {
          let label_names = @lib.IndirectNameMap::new(
            entries.map(fn(entry) {
              let @lib.IndirectNameAssoc(index, @lib.NameMap(labels)) = entry
              match label_limits.get(index) {
                Some(limit) =>
                  @lib.IndirectNameAssoc::new(
                    index,
                    @lib.NameMap::new(
                      labels.filter(fn(label) { label.0 < limit }),
                    ),
                  )
                None => entry
              }
            }),
          )
          candidate.with_name_sec(
            @lib.NameSec::new(
              module_name=names.module_name,
              func_names=names.func_names,
              local_names=names.local_names,
              label_names=Some(label_names),
              type_names=names.type_names,
              table_names=names.table_names,
              memory_names=names.memory_names,
              global_names=names.global_names,
              elem_names=names.elem_names,
              data_names=names.data_names,
              field_names=names.field_names,
              tag_names=names.tag_names,
            ),
          )
        }
        None => candidate
      }
    None => candidate
  }
}

///|
pub fn local_subtyping_run_module_pass(mod_ : @lib.Module) -> @lib.Module {
  if pass_module_has_offset_sensitive_metadata(mod_) {
    return mod_
  }
  if pass_module_has_legacy_try(mod_) {
    return mod_
  }
  let mut current_mod = ls_remove_return_suffixes(mod_)
  let mut iteration = 0
  let iteration_limit = match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) => ls_ref_body_local_iteration_limit(funcs)
    None => return mod_
  }
  let active = match current_mod.code_sec {
    Some(@lib.CodeSec(funcs)) => Array::make(funcs.length(), true)
    None => return current_mod
  }
  while iteration < iteration_limit {
    let funcs = match current_mod.code_sec {
      Some(@lib.CodeSec(funcs)) => funcs
      None => return current_mod
    }
    let module_ctx = @ir.hot_module_context_from_module(current_mod)
    let imported_func_count = ls_imported_func_count(current_mod)
    let rewritten_funcs : Array[@lib.Func] = Array::new(capacity=funcs.length())
    let mut changed = false
    for code_idx = 0; code_idx < funcs.length(); code_idx = code_idx + 1 {
      if !active[code_idx] {
        rewritten_funcs.push(funcs[code_idx])
        continue
      }
      let func_idx = @lib.FuncIdx::new(
        (imported_func_count + code_idx).reinterpret_as_uint(),
      )
      let (next_func, next_changed) = ls_rewrite_func(
        funcs[code_idx],
        func_idx,
        current_mod,
        module_ctx,
      )
      rewritten_funcs.push(next_func)
      active[code_idx] = next_changed
      if next_changed {
        changed = true
      }
    }
    if !changed {
      return pass_cleanup_unused_type_groups(current_mod)
    }
    current_mod = ls_rebuild_module(
      current_mod,
      Some(@lib.CodeSec::new(rewritten_funcs)),
    )
    iteration += 1
  }
  pass_cleanup_unused_type_groups(current_mod)
}

///|
test "null call rewrite emits valid raw bytes for every result signature" {
  for results in ["", "i32", "i64", "f32", "f64", "i32 i64", "funcref"] {
    let result = if results == "" { "" } else { "(result " + results + ")" }
    let input = pass_test_module_from_wat(
      "(module (type $t (func " +
      result +
      ")) (func " +
      result +
      " (local (ref null $t)) ref.null nofunc local.set 0 local.get 0 call_ref $t))",
    )
    let output = local_subtyping_run_module_pass(input)
    @validate.validate_module(output).unwrap()
    @validate.validate_module(
      @binary.decode_module(@binary.encode_module(output).unwrap()).unwrap(),
    ).unwrap()
    let @lib.Func(_, @lib.Expr(body)) = output.code_sec.unwrap().0[0]
    assert_true(body.any(fn(instr) { instr is @lib.Unreachable }))
    assert_false(body.any(fn(instr) { instr is @lib.CallRef(_) }))
  }
}