// Licensing scope: see ../../LICENSE and this directory's LICENSE and NOTICE.
// 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 rse_descriptor() -> @ir.HotPassDescriptor {
  @ir.HotPassDescriptor::new("redundant-set-elimination", 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 rse_summary() -> String {
  "Remove redundant same-value local.set/local.tee shells while preserving RHS evaluation."
}

///|
priv enum RseLabelKind {
  RseExitLabel
  RseLoopLabel
}

///|
priv struct RseLabelScope {
  label_id : Int32
  kind : RseLabelKind
  exits : Array[Array[Int32]]
  mut has_loop_branch : Bool
}

///|
fn RseLabelScope::new(label_id : Int32, kind : RseLabelKind) -> RseLabelScope {
  { label_id, kind, exits: [], has_loop_branch: false, }
}

///|
priv struct RseState {
  local_values : Array[Int32]
  mut initialized : Array[Bool]
  value_ids : @hashmap.HashMap[String, Int32]
  scopes : Array[RseLabelScope]
  next_value : Array[Int32]
  captured_values : Array[Int32]
  captured_depths : Array[Int32]
  captured_nodes : Array[Int32]
  previous_captured_values : Array[Int32]
  previous_captured_depths : Array[Int32]
  mut changed : Bool
  mut reachable : Bool
}

///|
fn RseState::new(func : @ir.HotFunc) -> RseState {
  let state = {
    local_values: Array::make(@ir.hot_local_count(func), -1),
    initialized: Array::makei(@ir.hot_local_count(func), fn(local_id) {
      let defaultable = match @ir.hot_local_type(func, local_id) {
        Some(@lib.RefTypeValType(ref_type)) => ref_type.is_nullable()
        _ => true
      }
      local_id < @ir.hot_param_count(func) || defaultable
    }),
    value_ids: @hashmap.new(capacity=@ir.hot_local_count(func) * 2 + 17),
    scopes: [],
    next_value: [0],
    captured_values: Array::make(@ir.hot_node_count(func), -2),
    captured_depths: Array::make(@ir.hot_node_count(func), -1),
    captured_nodes: [],
    previous_captured_values: [],
    previous_captured_depths: [],
    changed: false,
    reachable: true,
  }
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    state.local_values[local_id] = if local_id < @ir.hot_param_count(func) {
      rse_intern_value(state, "local:\{local_id}")
    } else {
      match @ir.hot_local_type(func, local_id) {
        Some(local_type) =>
          match rse_hot_default_key_for_type(func, local_type) {
            Some(key) => rse_intern_value(state, key)
            None => rse_intern_value(state, "local:\{local_id}")
          }
        None => rse_intern_value(state, "local:\{local_id}")
      }
    }
  }
  state
}

///|
fn RseState::clone_from(other : RseState) -> RseState {
  // Branch-local exploration can share the value interner because value ids are
  // immutable once assigned. The allocator must be shared with the dictionary.
  // Only the per-local facts and changed flag need to
  // be copied back explicitly.
  {
    local_values: other.local_values.copy(),
    initialized: other.initialized.copy(),
    value_ids: other.value_ids,
    scopes: other.scopes,
    next_value: other.next_value,
    captured_values: other.captured_values,
    captured_depths: other.captured_depths,
    captured_nodes: other.captured_nodes,
    previous_captured_values: other.previous_captured_values,
    previous_captured_depths: other.previous_captured_depths,
    changed: other.changed,
    reachable: other.reachable,
  }
}

///|
fn rse_sync_interner(dst : RseState, src : RseState) -> Unit {
  if src.changed {
    dst.changed = true
  }
}

///|
fn rse_intern_value(state : RseState, key : String) -> Int32 {
  match state.value_ids.get(key) {
    Some(value) => value
    None => {
      let value = state.next_value[0]
      state.next_value[0] += 1
      state.value_ids.set(key, value)
      value
    }
  }
}

///|
fn rse_fresh_value(state : RseState, node_id : Int32) -> Int32 {
  let value = state.next_value[0]
  state.next_value[0] += 1
  ignore(node_id)
  value
}

///|
fn rse_local_value_get(state : RseState, local_id : Int32) -> Int32 {
  if local_id < 0 || local_id >= state.local_values.length() {
    -1
  } else {
    state.local_values[local_id]
  }
}

///|
fn rse_local_value_set(
  state : RseState,
  local_id : Int32,
  value : Int32,
) -> Unit {
  if local_id >= 0 && local_id < state.local_values.length() {
    state.local_values[local_id] = value
  }
}

///|
fn rse_clear_all_local_values(state : RseState) -> Unit {
  for idx = 0; idx < state.local_values.length(); idx = idx + 1 {
    state.local_values[idx] = -1
  }
}

///|
fn rse_merge_local_value_sources(
  state : RseState,
  sources : Array[Array[Int32]],
) -> Unit {
  if sources.length() == 0 {
    rse_clear_all_local_values(state)
    state.reachable = false
    return
  }
  state.reachable = true
  let count = state.local_values.length()
  for idx = 0; idx < count; idx = idx + 1 {
    let mut first_known = -1
    let mut saw_known = false
    let mut saw_unknown = false
    let mut disagreement = false
    for source in sources {
      let value = source[idx]
      if value < 0 {
        saw_unknown = true
        continue
      }
      if !saw_known {
        first_known = value
        saw_known = true
      } else if value != first_known {
        disagreement = true
      }
    }
    state.local_values[idx] = if disagreement {
      if saw_unknown {
        -1
      } else {
        rse_fresh_value(state, idx)
      }
    } else if saw_known && !saw_unknown {
      first_known
    } else {
      -1
    }
  }
}

///|
fn rse_record_branch_exit(
  state : RseState,
  label_id : Int32,
  unknown~ : Bool = false,
) -> Unit {
  if label_id < 0 {
    return
  }
  let mut idx = state.scopes.length() - 1
  while idx >= 0 {
    let scope = state.scopes[idx]
    if scope.label_id == label_id {
      match scope.kind {
        RseLabelKind::RseLoopLabel => scope.has_loop_branch = true
        RseLabelKind::RseExitLabel =>
          scope.exits.push(
            if unknown {
              Array::make(state.local_values.length(), -1)
            } else {
              state.local_values.copy()
            },
          )
      }
      return
    }
    idx -= 1
  }
}

///|
fn rse_record_branch_table_exits(
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
) -> Unit {
  match @ir.hot_branch_target(func, node_id) {
    Some(label_id) => rse_record_branch_exit(state, label_id)
    None => ()
  }
  for label_id in @ir.hot_branch_table_targets_for_node(func, node_id) {
    rse_record_branch_exit(state, label_id)
  }
}

///|
fn rse_f32_key(value : @lib.F32) -> String {
  "f32:\{value.0.reinterpret_as_uint()}"
}

///|
fn rse_f64_key(value : @lib.F64) -> String {
  "f64:\{value.0.reinterpret_as_uint64()}"
}

///|
fn rse_const_payload_key(payload : @ir.HotConstPayload) -> String {
  match payload {
    @ir.HotConstPayload::F32Const(value) => rse_f32_key(value)
    @ir.HotConstPayload::F64Const(value) => rse_f64_key(value)
    _ => @debug.to_string(payload)
  }
}

///|
fn rse_node_const_key(func : @ir.HotFunc, node : @ir.HotNode) -> String {
  let key = rse_const_payload_key(@ir.hot_const_get(func, node.imm0))
  "const:\{node.ty}:\{key}"
}

///|
fn rse_default_ref_null_type(ref_type : @lib.RefType) -> @lib.RefType {
  match ref_type.get_heap_type() {
    @lib.AbsHeapTypeHeapType(@lib.ExternAbsHeapType) =>
      rse_raw_ref_null_result_type(
        @lib.HeapType::abs(@lib.AbsHeapType::extern_()),
      )
    @lib.AbsHeapTypeHeapType(@lib.FuncAbsHeapType) =>
      rse_raw_ref_null_result_type(@lib.HeapType::abs(@lib.AbsHeapType::func()))
    _ => ref_type.make_nullable()
  }
}

///|
fn rse_hot_default_key_for_type(
  func : @ir.HotFunc,
  ty : @lib.ValType,
) -> String? {
  let type_id = @ir.hot_type_intern_value(func, ty)
  match ty {
    @lib.NumTypeValType(@lib.I32NumType) =>
      Some(
        "const:\{type_id}:\{rse_const_payload_key(@ir.HotConstPayload::i32_const(@lib.I32::new(0)))}",
      )
    @lib.NumTypeValType(@lib.I64NumType) =>
      Some(
        "const:\{type_id}:\{rse_const_payload_key(@ir.HotConstPayload::i64_const(@lib.I64::new(0L)))}",
      )
    @lib.NumTypeValType(@lib.F32NumType) =>
      Some(
        "const:\{type_id}:\{rse_const_payload_key(@ir.HotConstPayload::f32_const(@lib.F32::new(0.0)))}",
      )
    @lib.NumTypeValType(@lib.F64NumType) =>
      Some(
        "const:\{type_id}:\{rse_const_payload_key(@ir.HotConstPayload::f64_const(@lib.F64::new(0.0)))}",
      )
    @lib.RefTypeValType(ref_type) if ref_type.is_nullable() => {
      let default_ref = rse_default_ref_null_type(ref_type)
      Some(
        "ref.null:\{type_id}:\{@debug.to_string(@ir.HotConstPayload::ref_null_const(default_ref))}",
      )
    }
    _ => None
  }
}

///|
fn rse_node_can_structurally_value(func : @ir.HotFunc, node_id : Int32) -> Bool {
  let node = @ir.hot_node_get(func, node_id)
  ignore(func)
  ignore(node_id)
  match node.op {
    @ir.HotOp::Const | @ir.HotOp::RefNull | @ir.HotOp::RefFunc => true
    _ => false
  }
}

///|
fn rse_structural_value(
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
) -> Int32? {
  if !rse_node_can_structurally_value(func, node_id) {
    return None
  }
  let node = @ir.hot_node_get(func, node_id)
  let key = match node.op {
    @ir.HotOp::Const => rse_node_const_key(func, node)
    @ir.HotOp::RefNull =>
      "ref.null:\{node.ty}:\{@debug.to_string(@ir.hot_const_get(func, node.imm0))}"
    @ir.HotOp::RefFunc => "ref.func:\{node.ty}:\{node.imm0}"
    _ => return None
  }
  Some(rse_intern_value(state, key))
}

///|
fn rse_replace_redundant_set(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_id : Int32,
  value_id : Int32,
) -> Unit {
  let replacement_id = @ir.hot_build_drop(func, value_id)
  let replacement = @ir.hot_node_get(func, replacement_id)
  @ir.hot_delete_node(func, replacement_id)
  pass_replace_node(ctx, func, node_id, replacement)
}

///|
fn rse_replace_redundant_tee(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_id : Int32,
  value_id : Int32,
) -> Unit {
  let replacement = @ir.hot_node_get(func, value_id)
  pass_replace_node(ctx, func, node_id, replacement)
}

///|
fn rse_rewind_captures(state : RseState, depth : Int32) -> Unit {
  while state.captured_nodes.length() > depth {
    let node_id = state.captured_nodes.pop().unwrap()
    state.captured_values[node_id] = state.previous_captured_values
      .pop()
      .unwrap()
    state.captured_depths[node_id] = state.previous_captured_depths
      .pop()
      .unwrap()
  }
}

///|
fn rse_visit_region(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  state : RseState,
  region_ref : @ir.HotRegionRef,
) -> Unit {
  // A nested region can establish initialization only inside its own frame.
  let entry_initialized = state.initialized.copy()
  let capture_depth = state.captured_nodes.length()
  let mut idx = 0
  let mut previous_root = -1
  let mut lane = 0
  while idx < @ir.hot_region_root_count(func, region_ref) {
    if !state.reachable {
      break
    }
    let root_id = @ir.hot_region_get(func, region_ref, idx)
    if root_id >= 0 && @ir.hot_node_is_live(func, root_id) {
      let arity = @ir.hot_node_result_arity(func, root_id)
      lane = if previous_root == root_id { lane + 1 } else { 0 }
      let force_eval = arity == 0 ||
        (
          root_id < state.captured_depths.length() &&
          state.captured_depths[root_id] >= capture_depth &&
          (lane == 0 || lane % arity == 0)
        )
      ignore(
        rse_visit_node(ctx, func, state, root_id, capture=true, force_eval~),
      )
      previous_root = root_id
    }
    idx += 1
  }
  rse_rewind_captures(state, capture_depth)
  state.initialized = entry_initialized
}

///|
fn rse_visit_if(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
) -> Int32 {
  let scope = RseLabelScope::new(
    @ir.hot_control_node_label(func, node_id),
    RseLabelKind::RseExitLabel,
  )
  state.scopes.push(scope)
  let entry_state = RseState::clone_from(state)
  let then_state = RseState::clone_from(entry_state)
  rse_visit_region(
    ctx,
    func,
    then_state,
    @ir.hot_region_then_ref(func, node_id),
  )
  let else_state = match @ir.hot_region_else_ref(func, node_id) {
    Some(else_ref) => {
      let branch_state = RseState::clone_from(entry_state)
      rse_visit_region(ctx, func, branch_state, else_ref)
      branch_state
    }
    None => entry_state
  }
  ignore(state.scopes.pop())
  rse_sync_interner(state, then_state)
  rse_sync_interner(state, else_state)
  let sources : Array[Array[Int32]] = []
  if then_state.reachable {
    sources.push(then_state.local_values.copy())
  }
  if else_state.reachable {
    sources.push(else_state.local_values.copy())
  }
  for exit in scope.exits {
    sources.push(exit)
  }
  rse_merge_local_value_sources(state, sources)
  rse_fresh_value(state, node_id)
}

///|
fn rse_visit_control(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
) -> Int32 {
  let node = @ir.hot_node_get(func, node_id)
  let mut previous_input = -1
  let mut lane = 0
  for index = 0
      index < pass_value_operand_count(func, node_id)
      index = index + 1 {
    let slot = pass_value_operand_slot(node, index)
    let input = @ir.hot_child_get(func, node_id, slot)
    let arity = @ir.hot_node_result_arity(func, input)
    lane = if previous_input == input { lane + 1 } else { 0 }
    let force_eval = arity == 0 || (lane > 0 && lane % arity == 0)
    previous_input = input
    ignore(
      rse_visit_node(
        ctx,
        func,
        state,
        input,
        capture=!(node.op is @ir.HotOp::If && slot == 0),
        force_eval~,
      ),
    )
    if !state.reachable {
      return rse_fresh_value(state, node_id)
    }
  }
  match node.op {
    @ir.HotOp::If => rse_visit_if(ctx, func, state, node_id)
    @ir.HotOp::Block => {
      let scope = RseLabelScope::new(
        @ir.hot_control_node_label(func, node_id),
        RseLabelKind::RseExitLabel,
      )
      state.scopes.push(scope)
      rse_visit_region(ctx, func, state, @ir.hot_region_body_ref(func, node_id))
      ignore(state.scopes.pop())
      let sources : Array[Array[Int32]] = []
      if state.reachable {
        sources.push(state.local_values.copy())
      }
      for exit in scope.exits {
        sources.push(exit)
      }
      rse_merge_local_value_sources(state, sources)
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::Loop => {
      let loop_state = RseState::clone_from(state)
      rse_clear_all_local_values(loop_state)
      let scope = RseLabelScope::new(
        @ir.hot_control_node_label(func, node_id),
        RseLabelKind::RseLoopLabel,
      )
      state.scopes.push(scope)
      rse_visit_region(
        ctx,
        func,
        loop_state,
        @ir.hot_region_body_ref(func, node_id),
      )
      ignore(state.scopes.pop())
      rse_sync_interner(state, loop_state)
      if loop_state.reachable && !scope.has_loop_branch {
        for idx = 0; idx < state.local_values.length(); idx = idx + 1 {
          state.local_values[idx] = loop_state.local_values[idx]
        }
        state.reachable = true
      } else if !loop_state.reachable && !scope.has_loop_branch {
        rse_clear_all_local_values(state)
        state.reachable = false
      } else {
        // Loops with backedges need fixed-point value flow for full Binaryen
        // parity. Keep them conservative instead of trusting one iteration.
        rse_clear_all_local_values(state)
        state.reachable = true
      }
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::Try | @ir.HotOp::TryTable => {
      // Exception edges make local facts path-sensitive. Visit children/regions
      // only for safe nested tee/set rewrites, then discard facts after the node.
      match node.op {
        @ir.HotOp::Try => {
          rse_visit_region(
            ctx,
            func,
            state,
            @ir.hot_region_body_ref(func, node_id),
          )
          match @ir.hot_region_catch_ref(func, node_id) {
            Some(catch_ref) => {
              // A handler can run before any normal-body write. Its entry
              // cannot inherit the normal exit's values or reachability.
              rse_clear_all_local_values(state)
              state.reachable = true
              rse_visit_region(ctx, func, state, catch_ref)
              // Normal completion remains possible even when the catch exits.
              state.reachable = true
            }
            None => ()
          }
        }
        @ir.HotOp::TryTable => {
          // A catch can transfer control after any prefix of the protected
          // body. Join unknown local values at each exceptional destination.
          for arm in @ir.hot_catch_info_get(func, node.imm1).catches {
            let target = match arm {
              @ir.HotCatchArm::CatchArm(_, label)
              | @ir.HotCatchArm::CatchRefArm(_, label)
              | @ir.HotCatchArm::CatchAllArm(label)
              | @ir.HotCatchArm::CatchAllRefArm(label) => label
            }
            rse_record_branch_exit(state, target, unknown=true)
          }
          rse_visit_region(
            ctx,
            func,
            state,
            @ir.hot_region_body_ref(func, node_id),
          )
          rse_visit_region(
            ctx,
            func,
            state,
            @ir.hot_region_catch_list_ref(func, node_id),
          )
        }
        _ => ()
      }
      rse_clear_all_local_values(state)
      rse_fresh_value(state, node_id)
    }
    _ => rse_fresh_value(state, node_id)
  }
}

///|
fn rse_visit_node(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
  capture~ : Bool = false,
  force_eval~ : Bool = false,
) -> Int32 {
  if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
    return -1
  }
  while state.captured_values.length() <= node_id {
    state.captured_values.push(-2)
    state.captured_depths.push(-1)
  }
  if !force_eval && state.captured_values[node_id] != -2 {
    return state.captured_values[node_id]
  }
  let capture_depth = state.captured_nodes.length()
  let value = rse_visit_uncaptured_node(ctx, func, state, node_id)
  rse_rewind_captures(state, capture_depth)
  if capture {
    state.previous_captured_values.push(state.captured_values[node_id])
    state.previous_captured_depths.push(state.captured_depths[node_id])
    state.captured_depths[node_id] = state.captured_nodes.length()
    state.captured_values[node_id] = value
    state.captured_nodes.push(node_id)
  }
  value
}

///|
fn rse_visit_uncaptured_node(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  state : RseState,
  node_id : Int32,
) -> Int32 {
  if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
    return -1
  }
  let node = @ir.hot_node_get(func, node_id)
  match node.op {
    @ir.HotOp::Block
    | @ir.HotOp::Loop
    | @ir.HotOp::If
    | @ir.HotOp::Try
    | @ir.HotOp::TryTable => return rse_visit_control(ctx, func, state, node_id)
    _ => ()
  }

  let child_count = @ir.hot_child_count(func, node_id)
  let mut first_child_value = -1
  for slot = 0; slot < child_count; slot = slot + 1 {
    let value = rse_visit_node(
      ctx,
      func,
      state,
      @ir.hot_child_get(func, node_id, slot),
    )
    if slot == 0 {
      first_child_value = value
    }
  }

  match node.op {
    @ir.HotOp::LocalGet => rse_local_value_get(state, node.imm0)
    @ir.HotOp::LocalSet | @ir.HotOp::LocalTee => {
      if child_count != 1 {
        return rse_fresh_value(state, node_id)
      }
      let value_id = @ir.hot_child_get(func, node_id, 0)
      let value = first_child_value
      let current = rse_local_value_get(state, node.imm0)
      if state.initialized[node.imm0] && value >= 0 && current == value {
        match node.op {
          @ir.HotOp::LocalSet =>
            rse_replace_redundant_set(ctx, func, node_id, value_id)
          @ir.HotOp::LocalTee =>
            rse_replace_redundant_tee(ctx, func, node_id, value_id)
          _ => ()
        }
        state.changed = true
      }
      rse_local_value_set(state, node.imm0, value)
      state.initialized[node.imm0] = true
      value
    }
    @ir.HotOp::Br => {
      match @ir.hot_branch_target(func, node_id) {
        Some(label_id) => rse_record_branch_exit(state, label_id)
        None => ()
      }
      rse_clear_all_local_values(state)
      state.reachable = false
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::BrIf
    | @ir.HotOp::BrOnNull
    | @ir.HotOp::BrOnNonNull
    | @ir.HotOp::BrOnCast
    | @ir.HotOp::BrOnCastFail => {
      match @ir.hot_branch_target(func, node_id) {
        Some(label_id) => rse_record_branch_exit(state, label_id)
        None => ()
      }
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::BrTable => {
      rse_record_branch_table_exits(func, state, node_id)
      rse_clear_all_local_values(state)
      state.reachable = false
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::Continuation => {
      for label_id in @ir.hot_continuation_targets(func, node_id) {
        rse_record_branch_exit(state, label_id)
      }
      rse_fresh_value(state, node_id)
    }
    @ir.HotOp::Return
    | @ir.HotOp::Unreachable
    | @ir.HotOp::Throw
    | @ir.HotOp::Rethrow
    | @ir.HotOp::ThrowRef => {
      rse_clear_all_local_values(state)
      state.reachable = false
      rse_fresh_value(state, node_id)
    }
    _ =>
      match rse_structural_value(func, state, node_id) {
        Some(value) => value
        None => rse_fresh_value(state, node_id)
      }
  }
}

///|
fn rse_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::LocalSet | @ir.HotOp::LocalTee => return true
      _ => ()
    }
  }
  false
}

///|
fn rse_run(ctx : HotPassContext, func : @ir.HotFunc) -> HotPassResult {
  if !rse_has_candidate(func) {
    return HotPassResult::unchanged()
  }
  let state = RseState::new(func)
  rse_visit_region(ctx, func, state, @ir.HotRegionRef::root())
  if state.changed {
    HotPassResult::changed()
  } else {
    HotPassResult::unchanged()
  }
}

///|
priv enum RseRawLabelKind {
  ExitLabel
  LoopLabel
}

///|
priv struct RseRawLabelScope {
  kind : RseRawLabelKind
  exits : Array[Array[Int32]]
  mut has_loop_branch : Bool
}

///|
fn RseRawLabelScope::new(kind : RseRawLabelKind) -> RseRawLabelScope {
  { kind, exits: [], has_loop_branch: false, }
}

///|
priv struct RseRawInterner {
  ids : @hashmap.HashMap[String, Int32]
  mut next_value : Int32
}

///|
fn RseRawInterner::new(capacity : Int32) -> RseRawInterner {
  { ids: @hashmap.new(capacity~), next_value: 0, }
}

///|
priv struct RseRawState {
  local_values : Array[Int32]
  mut candidates_by_value : @hashmap.HashMap[Int32, Array[Int32]]?
  mut initialized : Array[Bool]
  local_types : Array[@lib.ValType]
  interner : RseRawInterner
  env : @validate.Env
  stack : Array[Int32]
  stack_types : Array[@lib.ValType?]
  mut next_unknown : Int32
  mut changed : Bool
  mut reachable : Bool
}

///|
fn RseRawState::new(
  local_types : Array[@lib.ValType],
  param_count : Int32,
  env : @validate.Env,
) -> RseRawState {
  let state = {
    local_values: Array::make(local_types.length(), -1),
    candidates_by_value: None,
    initialized: Array::makei(local_types.length(), fn(local_id) {
      let defaultable = match local_types[local_id] {
        @lib.RefTypeValType(ref_type) => ref_type.is_nullable()
        _ => true
      }
      local_id < param_count || defaultable
    }),
    local_types,
    interner: RseRawInterner::new(local_types.length() * 4 + 17),
    env,
    stack: [],
    stack_types: [],
    next_unknown: 0,
    changed: false,
    reachable: true,
  }
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    state.local_values[local_id] = if local_id < param_count {
      rse_raw_intern_value(state, "local:\{local_id}")
    } else {
      match rse_raw_default_value_for_type(state, local_types[local_id]) {
        Some(value) => value
        None => rse_raw_intern_value(state, "local:\{local_id}")
      }
    }
  }
  state
}

///|
fn RseRawState::clone_from(other : RseRawState) -> RseRawState {
  {
    local_values: other.local_values.copy(),
    candidates_by_value: None,
    initialized: other.initialized.copy(),
    local_types: other.local_types,
    interner: other.interner,
    env: other.env,
    stack: other.stack.copy(),
    stack_types: other.stack_types.copy(),
    next_unknown: other.next_unknown,
    changed: other.changed,
    reachable: other.reachable,
  }
}

///|
fn rse_raw_intern_value(state : RseRawState, key : String) -> Int32 {
  match state.interner.ids.get(key) {
    Some(value) => value
    None => {
      let value = state.interner.next_value
      state.interner.next_value += 1
      state.interner.ids.set(key, value)
      value
    }
  }
}

///|
fn rse_raw_fresh(state : RseRawState) -> Int32 {
  let value = state.interner.next_value
  state.interner.next_value += 1
  value
}

///|
fn rse_raw_pop(state : RseRawState) -> Int32 {
  ignore(state.stack_types.pop())
  match state.stack.pop() {
    Some(value) => value
    None => -1
  }
}

///|
fn rse_raw_push(
  state : RseRawState,
  value : Int32,
  ty~ : @lib.ValType? = None,
) -> Unit {
  state.stack.push(value)
  state.stack_types.push(ty)
}

///|
fn rse_raw_peek_type(state : RseRawState, depth~ : Int32 = 0) -> @lib.ValType? {
  match state.stack_types.get(state.stack_types.length() - 1 - depth) {
    Some(ty) => ty
    None => None
  }
}

///|
fn rse_raw_clear_stack(state : RseRawState) -> Unit {
  state.stack.clear()
  state.stack_types.clear()
}

///|
fn rse_raw_ref_null_result_type(heap_type : @lib.HeapType) -> @lib.RefType {
  match @lib.Instruction::ref_null(heap_type) {
    @lib.Instruction::RefNull(ref_type) => ref_type
    _ => abort("expected ref.null constructor")
  }
}

///|
fn rse_raw_default_ref_null_type(ref_type : @lib.RefType) -> @lib.RefType {
  rse_default_ref_null_type(ref_type)
}

///|
fn rse_raw_default_key_for_type(ty : @lib.ValType) -> String? {
  match ty {
    @lib.NumTypeValType(@lib.I32NumType) => Some("i32:\{@lib.I32::new(0)}")
    @lib.NumTypeValType(@lib.I64NumType) => Some("i64:\{@lib.I64::new(0L)}")
    @lib.NumTypeValType(@lib.F32NumType) =>
      Some(rse_f32_key(@lib.F32::new(0.0)))
    @lib.NumTypeValType(@lib.F64NumType) =>
      Some(rse_f64_key(@lib.F64::new(0.0)))
    @lib.RefTypeValType(ref_type) if ref_type.is_nullable() =>
      Some("ref.null:\{rse_raw_default_ref_null_type(ref_type)}")
    _ => None
  }
}

///|
fn rse_raw_default_value_for_type(
  state : RseRawState,
  ty : @lib.ValType,
) -> Int32? {
  match rse_raw_default_key_for_type(ty) {
    Some(key) => Some(rse_raw_intern_value(state, key))
    None => None
  }
}

///|
fn rse_raw_default_instr_key(instr : @lib.Instruction) -> String? {
  match instr {
    @lib.Instruction::I32Const(value) => Some("i32:\{value}")
    @lib.Instruction::I64Const(value) => Some("i64:\{value}")
    @lib.Instruction::F32Const(value) => Some(rse_f32_key(value))
    @lib.Instruction::F64Const(value) => Some(rse_f64_key(value))
    @lib.Instruction::RefNull(ref_type) => Some("ref.null:\{ref_type}")
    _ => None
  }
}

///|
fn rse_raw_default_instr_value(
  state : RseRawState,
  instr : @lib.Instruction,
) -> Int32? {
  match rse_raw_default_instr_key(instr) {
    Some(key) => Some(rse_raw_intern_value(state, key))
    None => None
  }
}

///|
priv struct RseRawLoopSummary {
  writes : Array[Int32]
  same_values : Array[Int32]
  disagreed : Array[Bool]
  default_writes : Array[Int32]
  default_values : Array[Int32]
}

///|
fn RseRawLoopSummary::new(state : RseRawState) -> RseRawLoopSummary {
  let count = state.local_values.length()
  let summary : RseRawLoopSummary = {
    writes: Array::make(count, 0),
    same_values: Array::make(count, -1),
    disagreed: Array::make(count, false),
    default_writes: Array::make(count, 0),
    default_values: Array::make(count, -1),
  }
  for local_id = 0; local_id < count; local_id = local_id + 1 {
    match rse_raw_default_value_for_type(state, state.local_types[local_id]) {
      Some(value) => summary.default_values[local_id] = value
      None => ()
    }
  }
  summary
}

///|
fn rse_raw_loop_summary_record_write(
  summary : RseRawLoopSummary,
  local_id : Int32,
  value : Int32,
) -> Unit {
  if local_id < 0 || local_id >= summary.writes.length() {
    return
  }
  summary.writes[local_id] += 1
  if value == -1 {
    summary.disagreed[local_id] = true
  } else if summary.same_values[local_id] == -1 {
    summary.same_values[local_id] = value
  } else if summary.same_values[local_id] != value {
    summary.disagreed[local_id] = true
  }
  if value != -1 && value == summary.default_values[local_id] {
    summary.default_writes[local_id] += 1
  }
}

///|
fn rse_raw_loop_summary_scan(
  state : RseRawState,
  summary : RseRawLoopSummary,
  instrs : Array[@lib.Instruction],
) -> Unit {
  for idx = 0; idx < instrs.length(); idx = idx + 1 {
    let instr = instrs[idx]
    match instr {
      @lib.Instruction::LocalSet(local_idx)
      | @lib.Instruction::LocalTee(local_idx) => {
        let value = if idx > 0 {
          match rse_raw_default_instr_value(state, instrs[idx - 1]) {
            Some(value) => value
            None => -1
          }
        } else {
          -1
        }
        rse_raw_loop_summary_record_write(
          summary,
          rse_raw_local_id(local_idx),
          value,
        )
      }
      @lib.Instruction::Block(_, @lib.Expr(body))
      | @lib.Instruction::Loop(_, @lib.Expr(body))
      | @lib.Instruction::TryTable(_, _, @lib.Expr(body)) =>
        rse_raw_loop_summary_scan(state, summary, body)
      @lib.Instruction::If(_, then_body, else_body) => {
        rse_raw_loop_summary_scan(state, summary, then_body)
        match else_body {
          Some(else_instrs) =>
            rse_raw_loop_summary_scan(state, summary, else_instrs)
          None => ()
        }
      }
      @lib.Instruction::Try(_, @lib.Expr(body), catches, _) => {
        // Delegation has no instruction body. Count every possible write;
        // the normal EH transfer still clears value/control-flow facts.
        rse_raw_loop_summary_scan(state, summary, body)
        for catch_ in catches {
          match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(catch_body))
            | @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
              rse_raw_loop_summary_scan(state, summary, catch_body)
          }
        }
      }
      _ => ()
    }
  }
}

///|
fn rse_raw_loop_summary(
  state : RseRawState,
  body : Array[@lib.Instruction],
) -> RseRawLoopSummary {
  let summary = RseRawLoopSummary::new(state)
  rse_raw_loop_summary_scan(state, summary, body)
  summary
}

///|
fn rse_raw_loop_summary_same_value(
  summary : RseRawLoopSummary,
  local_id : Int32,
) -> Int32 {
  if summary.disagreed[local_id] {
    -1
  } else {
    summary.same_values[local_id]
  }
}

///|
fn rse_raw_probe_push_binary_value(
  state : RseRawState,
  instr : @lib.Instruction,
) -> Bool {
  let rhs = rse_raw_pop(state)
  let lhs = rse_raw_pop(state)
  match rse_raw_fast_binary_tag(instr) {
    Some(tag) =>
      rse_raw_push(state, rse_raw_binary_tag_key(state, tag, lhs, rhs))
    None =>
      match instr {
        @lib.Instruction::I32LtS
        | @lib.Instruction::I32LtU
        | @lib.Instruction::I32GtS
        | @lib.Instruction::I32GtU
        | @lib.Instruction::I32LeS
        | @lib.Instruction::I32LeU
        | @lib.Instruction::I32GeS
        | @lib.Instruction::I32GeU
        | @lib.Instruction::I64LtS
        | @lib.Instruction::I64LtU
        | @lib.Instruction::I64GtS
        | @lib.Instruction::I64GtU
        | @lib.Instruction::I64LeS
        | @lib.Instruction::I64LeU
        | @lib.Instruction::I64GeS
        | @lib.Instruction::I64GeU => rse_raw_push(state, rse_raw_fresh(state))
        _ => return false
      }
  }
  true
}

///|
fn rse_raw_probe_expr_scoped(
  instrs : Array[@lib.Instruction],
  state : RseRawState,
  scopes : Array[RseRawLabelScope],
) -> Bool {
  for instr in instrs {
    if !state.reachable {
      continue
    }
    match instr {
      @lib.Instruction::I32Const(_)
      | @lib.Instruction::I64Const(_)
      | @lib.Instruction::F32Const(_)
      | @lib.Instruction::F64Const(_)
      | @lib.Instruction::RefNull(_) =>
        match rse_raw_default_instr_value(state, instr) {
          Some(value) => rse_raw_push(state, value)
          None => return false
        }
      @lib.Instruction::LocalGet(local_idx) => {
        let local_id = rse_raw_local_id(local_idx)
        let value = match rse_raw_local_get(state, local_id) {
          -1 => {
            let fresh = rse_raw_fresh(state)
            rse_raw_local_set(state, local_id, fresh)
            fresh
          }
          known => known
        }
        rse_raw_push(state, value)
      }
      @lib.Instruction::LocalSet(local_idx) => {
        let value = rse_raw_pop(state)
        rse_raw_local_set(state, rse_raw_local_id(local_idx), value)
      }
      @lib.Instruction::LocalTee(local_idx) => {
        let value = match state.stack.last() {
          Some(v) => v
          None => -1
        }
        rse_raw_local_set(state, rse_raw_local_id(local_idx), value)
      }
      @lib.Instruction::Drop => ignore(rse_raw_pop(state))
      @lib.Instruction::I32Eqz | @lib.Instruction::I64Eqz => {
        ignore(rse_raw_pop(state))
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::Br(label_idx) => {
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::BrIf(label_idx)
      | @lib.Instruction::BrOnNull(label_idx)
      | @lib.Instruction::BrOnNonNull(label_idx)
      | @lib.Instruction::BrOnCast(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastFail(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastDescEq(label_idx, _, _)
      | @lib.Instruction::BrOnCastDescEqFail(label_idx, _, _) => {
        ignore(rse_raw_pop(state))
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        rse_raw_clear_stack(state)
      }
      @lib.Instruction::Return | @lib.Instruction::Unreachable => {
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      _ => if !rse_raw_probe_push_binary_value(state, instr) { return false }
    }
  }
  true
}

///|
fn rse_raw_expr_may_branch(instrs : Array[@lib.Instruction]) -> Bool {
  for instr in instrs {
    match instr {
      @lib.Instruction::Br(_)
      | @lib.Instruction::BrIf(_)
      | @lib.Instruction::BrTable(_, _)
      | @lib.Instruction::BrOnNull(_)
      | @lib.Instruction::BrOnNonNull(_)
      | @lib.Instruction::BrOnCast(_, _, _, _)
      | @lib.Instruction::BrOnCastFail(_, _, _, _)
      | @lib.Instruction::BrOnCastDescEq(_, _, _)
      | @lib.Instruction::BrOnCastDescEqFail(_, _, _)
      | @lib.Instruction::Try(_, _, _, _)
      | @lib.Instruction::TryTable(_, _, _)
      | @lib.Instruction::Throw(_)
      | @lib.Instruction::ThrowRef
      | @lib.Instruction::Rethrow(_)
      | @lib.Instruction::Suspend(_)
      | @lib.Instruction::Resume(_, _)
      | @lib.Instruction::ResumeThrow(_, _, _)
      | @lib.Instruction::ResumeThrowRef(_, _)
      | @lib.Instruction::StackSwitch(_, _) => return true
      @lib.Instruction::Block(_, @lib.Expr(body))
      | @lib.Instruction::Loop(_, @lib.Expr(body)) =>
        if rse_raw_expr_may_branch(body) {
          return true
        }
      @lib.Instruction::If(_, then_body, else_body) => {
        if rse_raw_expr_may_branch(then_body) {
          return true
        }
        match else_body {
          Some(body) => if rse_raw_expr_may_branch(body) { return true }
          None => ()
        }
      }
      _ => ()
    }
  }
  false
}

///|
fn rse_raw_loop_stable_entry_values(
  state : RseRawState,
  body : Array[@lib.Instruction],
) -> Array[Bool] {
  let stable = Array::make(state.local_values.length(), false)
  // Without a branch, no path can revisit this loop's entry. The fallback
  // below rewrites nested loops only to discover those backedges.
  if !rse_raw_expr_may_branch(body) {
    return stable
  }
  let probe = RseRawState::clone_from(state)
  rse_raw_clear_stack(probe)
  let probe_scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
  let probe_scopes : Array[RseRawLabelScope] = [probe_scope]
  let scope = if rse_raw_probe_expr_scoped(body, probe, probe_scopes) {
    probe_scope
  } else {
    let fallback_probe = RseRawState::clone_from(state)
    rse_raw_clear_stack(fallback_probe)
    let fallback_scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
    let fallback_scopes : Array[RseRawLabelScope] = [fallback_scope]
    ignore(rse_raw_rewrite_expr_scoped(body, fallback_probe, fallback_scopes))
    fallback_scope
  }
  if !scope.has_loop_branch {
    return stable
  }
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    let entry_value = state.local_values[local_id]
    if entry_value == -1 {
      continue
    }
    let mut agrees = true
    for exit in scope.exits {
      if exit[local_id] != entry_value {
        agrees = false
      }
    }
    if agrees {
      stable[local_id] = true
    }
  }
  stable
}

///|
fn rse_raw_prepare_loop_entry(
  state : RseRawState,
  loop_state : RseRawState,
  body : Array[@lib.Instruction],
  summary : RseRawLoopSummary,
) -> Unit {
  rse_raw_clear_values(loop_state)
  rse_raw_clear_stack(loop_state)
  let stable_entry = rse_raw_loop_stable_entry_values(state, body)
  for local_id = 0
      local_id < loop_state.local_values.length()
      local_id = local_id + 1 {
    let writes = summary.writes[local_id]
    let same_write_value = rse_raw_loop_summary_same_value(summary, local_id)
    if writes == 0 || stable_entry[local_id] {
      loop_state.local_values[local_id] = state.local_values[local_id]
    } else {
      let default_value = summary.default_values[local_id]
      if default_value != -1 &&
        writes == summary.default_writes[local_id] &&
        state.local_values[local_id] == default_value {
        loop_state.local_values[local_id] = default_value
      } else if same_write_value != -1 &&
        state.local_values[local_id] == same_write_value {
        loop_state.local_values[local_id] = same_write_value
      }
    }
  }
}

///|
fn rse_raw_local_get(state : RseRawState, local_id : Int32) -> Int32 {
  if local_id >= 0 && local_id < state.local_values.length() {
    state.local_values[local_id]
  } else {
    -1
  }
}

///|
fn rse_raw_local_set(
  state : RseRawState,
  local_id : Int32,
  value : Int32,
) -> Unit {
  if local_id >= 0 && local_id < state.local_values.length() {
    let previous = state.local_values[local_id]
    if previous != value {
      match state.candidates_by_value {
        Some(index) => {
          match index.get(previous) {
            Some(candidates) =>
              for position = 0
                  position < candidates.length()
                  position = position + 1 {
                if candidates[position] == local_id {
                  ignore(candidates.remove(position))
                  if candidates.length() == 0 {
                    index.remove(previous)
                  }
                  break
                }
              }
            None => ()
          }
          if value != -1 {
            match index.get(value) {
              Some(candidates) => {
                let mut position = 0
                while position < candidates.length() &&
                      candidates[position] < local_id {
                  position = position + 1
                }
                candidates.insert(position, local_id)
              }
              None => index.set(value, [local_id])
            }
          }
        }
        None => ()
      }
    }
    state.local_values[local_id] = value
  }
}

///|
fn rse_raw_candidates_for_value(
  state : RseRawState,
  value : Int32,
  candidate_visits~ : Array[Int32]? = None,
) -> Array[Int32] {
  if state.candidates_by_value is None {
    let index : @hashmap.HashMap[Int32, Array[Int32]] = @hashmap.new(
      capacity=state.local_values.length() * 2 + 1,
    )
    for local_id = 0
        local_id < state.local_values.length()
        local_id = local_id + 1 {
      match candidate_visits {
        Some(visits) => visits[0] = visits[0] + 1
        None => ()
      }
      let local_value = state.local_values[local_id]
      if local_value != -1 {
        match index.get(local_value) {
          Some(candidates) => candidates.push(local_id)
          None => index.set(local_value, [local_id])
        }
      }
    }
    state.candidates_by_value = Some(index)
  }
  match state.candidates_by_value {
    Some(index) =>
      match index.get(value) {
        Some(candidates) => candidates
        None => []
      }
    None => []
  }
}

///|
fn rse_raw_out_ends_with_local_get(
  out : Array[@lib.Instruction],
  local_id : Int32,
) -> Bool {
  match out.last() {
    Some(@lib.Instruction::LocalGet(local_idx)) =>
      rse_raw_local_id(local_idx) == local_id
    _ => false
  }
}

///|
fn rse_raw_local_type(state : RseRawState, local_id : Int32) -> @lib.ValType? {
  if local_id >= 0 && local_id < state.local_types.length() {
    Some(state.local_types[local_id])
  } else {
    None
  }
}

///|
fn rse_raw_is_strict_subtype_local(
  state : RseRawState,
  candidate_id : Int32,
  original_id : Int32,
) -> Bool {
  if candidate_id == original_id {
    return false
  }
  match
    (
      rse_raw_local_type(state, candidate_id),
      rse_raw_local_type(state, original_id),
    ) {
    (Some(candidate), Some(original)) =>
      candidate != original &&
      @validate.Match::matches(candidate, original, state.env)
    _ => false
  }
}

///|
fn rse_raw_concrete_ref_type_idx(ty : @lib.ValType) -> @lib.TypeIdx? {
  match ty {
    @lib.RefTypeValType(@lib.HeapTypeRefType(_, _, @lib.HeapType(type_idx))) =>
      Some(type_idx)
    _ => None
  }
}

///|
fn rse_raw_refined_aggregate_receiver_type(
  state : RseRawState,
  base_type : @lib.TypeIdx,
  receiver_value : Int32,
  receiver_type : @lib.ValType?,
) -> @lib.TypeIdx? {
  let receiver_type = match receiver_type {
    Some(ty) => ty
    None => return None
  }
  if receiver_value == -1 {
    return None
  }
  let original = @lib.ValType::ref_type(
    @lib.RefType::new(true, @lib.HeapType::new(base_type)),
  )
  for candidate_id in rse_raw_candidates_for_value(state, receiver_value) {
    match rse_raw_local_type(state, candidate_id) {
      Some(candidate) =>
        match rse_raw_concrete_ref_type_idx(candidate) {
          Some(candidate_type) =>
            if candidate != original &&
              candidate_type != base_type &&
              @validate.Match::matches(candidate, original, state.env) &&
              @validate.Match::matches(receiver_type, candidate, state.env) {
              return Some(candidate_type)
            }
          _ => ()
        }
      None => ()
    }
  }
  None
}

///|
fn rse_raw_refined_get_local(
  state : RseRawState,
  local_id : Int32,
  candidate_visits~ : Array[Int32]? = None,
) -> Int32 {
  let value = rse_raw_local_get(state, local_id)
  if value == -1 {
    return local_id
  }
  for
    candidate_id in rse_raw_candidates_for_value(
      state,
      value,
      candidate_visits~,
    ) {
    match candidate_visits {
      Some(visits) => visits[0] = visits[0] + 1
      None => ()
    }
    if state.initialized[candidate_id] &&
      state.local_values[candidate_id] == value &&
      rse_raw_is_strict_subtype_local(state, candidate_id, local_id) {
      return candidate_id
    }
  }
  local_id
}

///|
fn rse_raw_clear_values(state : RseRawState) -> Unit {
  state.candidates_by_value = None
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    state.local_values[local_id] = -1
  }
}

///|
fn rse_raw_merge_sources(
  state : RseRawState,
  sources : Array[Array[Int32]],
) -> Unit {
  state.candidates_by_value = None
  rse_raw_clear_stack(state)
  if sources.length() == 0 {
    rse_raw_clear_values(state)
    state.reachable = false
    return
  }
  state.reachable = true
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    let mut first_known = -1
    let mut saw_known = false
    let mut saw_unknown = false
    let mut disagreement = false
    for source in sources {
      let value = source[local_id]
      if value == -1 {
        saw_unknown = true
        continue
      }
      if !saw_known {
        first_known = value
        saw_known = true
      } else if value != first_known {
        disagreement = true
      }
    }
    state.local_values[local_id] = if disagreement {
      if saw_unknown {
        -1
      } else {
        rse_raw_fresh(state)
      }
    } else if saw_known && !saw_unknown {
      first_known
    } else {
      -1
    }
  }
}

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

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

///|
fn rse_raw_record_branch_exit(
  state : RseRawState,
  scopes : Array[RseRawLabelScope],
  label_depth : Int32,
) -> Unit {
  if label_depth < 0 || label_depth >= scopes.length() {
    return
  }
  let scope = scopes[scopes.length() - 1 - label_depth]
  match scope.kind {
    RseRawLabelKind::LoopLabel => {
      scope.has_loop_branch = true
      scope.exits.push(state.local_values.copy())
    }
    _ => scope.exits.push(state.local_values.copy())
  }
}

///|
fn rse_raw_record_resume_handler_exits(
  state : RseRawState,
  scopes : Array[RseRawLabelScope],
  handlers : Array[@lib.ResumeHandler],
) -> Unit {
  for handler in handlers {
    match handler {
      @lib.ResumeOnLabel(_, label) =>
        rse_raw_record_branch_exit(state, scopes, rse_raw_label_depth(label))
      @lib.ResumeOnSwitch(_) => ()
    }
  }
}

///|
fn rse_raw_unary_key(state : RseRawState, op : String, value : Int32) -> Int32 {
  if value == -1 {
    -1
  } else {
    rse_raw_intern_value(state, "\{op}(\{value})")
  }
}

///|
fn rse_raw_binary_key(
  state : RseRawState,
  op : String,
  lhs : Int32,
  rhs : Int32,
) -> Int32 {
  if lhs == -1 || rhs == -1 {
    -1
  } else {
    rse_raw_intern_value(state, "\{op}(\{lhs},\{rhs})")
  }
}

///|
fn rse_raw_unary_tag_key(
  state : RseRawState,
  tag : Int32,
  value : Int32,
) -> Int32 {
  if value == -1 {
    -1
  } else {
    rse_raw_intern_value(state, "u\{tag}:\{value}")
  }
}

///|
fn rse_raw_binary_tag_key(
  state : RseRawState,
  tag : Int32,
  lhs : Int32,
  rhs : Int32,
) -> Int32 {
  if lhs == -1 || rhs == -1 {
    -1
  } else {
    rse_raw_intern_value(state, "b\{tag}:\{lhs}:\{rhs}")
  }
}

///|
fn rse_raw_fast_binary_tag(instr : @lib.Instruction) -> Int32? {
  match instr {
    @lib.Instruction::I32Add => Some(1)
    @lib.Instruction::I32Sub => Some(2)
    @lib.Instruction::I32Mul => Some(3)
    @lib.Instruction::I32And => Some(4)
    @lib.Instruction::I32Or => Some(5)
    @lib.Instruction::I32Xor => Some(6)
    @lib.Instruction::I32Shl => Some(7)
    @lib.Instruction::I32ShrS => Some(8)
    @lib.Instruction::I32ShrU => Some(9)
    @lib.Instruction::I64Add => Some(10)
    @lib.Instruction::I64Sub => Some(11)
    @lib.Instruction::I64Mul => Some(12)
    @lib.Instruction::I64And => Some(13)
    @lib.Instruction::I64Or => Some(14)
    @lib.Instruction::I64Xor => Some(15)
    @lib.Instruction::I64Shl => Some(16)
    @lib.Instruction::I64ShrS => Some(17)
    @lib.Instruction::I64ShrU => Some(18)
    @lib.Instruction::I32Eq => Some(19)
    @lib.Instruction::I32Ne => Some(20)
    @lib.Instruction::I64Eq => Some(21)
    @lib.Instruction::I64Ne => Some(22)
    @lib.Instruction::I32LtS => Some(23)
    @lib.Instruction::I32LtU => Some(24)
    @lib.Instruction::I32GtS => Some(25)
    @lib.Instruction::I32GtU => Some(26)
    @lib.Instruction::I32LeS => Some(27)
    @lib.Instruction::I32LeU => Some(28)
    @lib.Instruction::I32GeS => Some(29)
    @lib.Instruction::I32GeU => Some(30)
    @lib.Instruction::I64LtS => Some(31)
    @lib.Instruction::I64LtU => Some(32)
    @lib.Instruction::I64GtS => Some(33)
    @lib.Instruction::I64GtU => Some(34)
    @lib.Instruction::I64LeS => Some(35)
    @lib.Instruction::I64LeU => Some(36)
    @lib.Instruction::I64GeS => Some(37)
    @lib.Instruction::I64GeU => Some(38)
    _ => None
  }
}

///|
fn rse_raw_rewrite_expr_scoped(
  instrs : Array[@lib.Instruction],
  state : RseRawState,
  scopes : Array[RseRawLabelScope],
) -> Array[@lib.Instruction] {
  let out : Array[@lib.Instruction] = []
  for instr in instrs {
    if !state.reachable {
      out.push(instr)
      continue
    }
    match instr {
      @lib.Instruction::I32Const(value) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, "i32:\{value}"))
      }
      @lib.Instruction::I64Const(value) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, "i64:\{value}"))
      }
      @lib.Instruction::F32Const(value) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, rse_f32_key(value)))
      }
      @lib.Instruction::F64Const(value) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, rse_f64_key(value)))
      }
      @lib.Instruction::RefNull(ref_type) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, "ref.null:\{ref_type}"))
      }
      @lib.Instruction::StringConst(bytes) => {
        out.push(instr)
        rse_raw_push(
          state,
          rse_raw_intern_value(state, "string.const:\{@debug.to_string(bytes)}"),
        )
      }
      @lib.Instruction::RefFunc(func_idx) => {
        out.push(instr)
        rse_raw_push(state, rse_raw_intern_value(state, "ref.func:\{func_idx}"))
      }
      @lib.Instruction::LocalGet(local_idx) => {
        let local_id = rse_raw_local_id(local_idx)
        let refined_id = rse_raw_refined_get_local(state, local_id)
        if refined_id != local_id {
          out.push(
            @lib.Instruction::local_get(
              @lib.LocalIdx::new(refined_id.reinterpret_as_uint()),
            ),
          )
          state.changed = true
        } else {
          out.push(instr)
        }
        let value = match rse_raw_local_get(state, local_id) {
          -1 => {
            let fresh = rse_raw_fresh(state)
            rse_raw_local_set(state, local_id, fresh)
            fresh
          }
          known => known
        }
        rse_raw_push(state, value, ty=rse_raw_local_type(state, refined_id))
      }
      @lib.Instruction::LocalSet(local_idx) => {
        let value = rse_raw_pop(state)
        let local_id = rse_raw_local_id(local_idx)
        if state.initialized[local_id] &&
          value != -1 &&
          rse_raw_local_get(state, local_id) == value {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else if state.initialized[local_id] &&
          value == -1 &&
          rse_raw_out_ends_with_local_get(out, local_id) {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else {
          out.push(instr)
        }
        rse_raw_local_set(state, local_id, value)
        state.initialized[local_id] = true
      }
      @lib.Instruction::LocalTee(local_idx) => {
        let value = match state.stack.last() {
          Some(v) => v
          None => -1
        }
        let local_id = rse_raw_local_id(local_idx)
        if state.initialized[local_id] &&
          value != -1 &&
          rse_raw_local_get(state, local_id) == value {
          state.changed = true
        } else if state.initialized[local_id] &&
          value == -1 &&
          rse_raw_out_ends_with_local_get(out, local_id) {
          state.changed = true
        } else {
          out.push(instr)
          if !state.stack_types.is_empty() {
            state.stack_types[state.stack_types.length() - 1] = rse_raw_local_type(
              state, local_id,
            )
          }
        }
        rse_raw_local_set(state, local_id, value)
        state.initialized[local_id] = true
      }
      @lib.Instruction::Drop => {
        ignore(rse_raw_pop(state))
        out.push(instr)
      }
      @lib.Instruction::RefCastDescEq(nullable, exact, heap_type) => {
        // The descriptor is the second operand; the result retains the object.
        ignore(rse_raw_pop(state))
        let value = rse_raw_pop(state)
        out.push(instr)
        rse_raw_push(
          state,
          value,
          ty=Some(
            @lib.ValType::ref_type(
              @lib.RefType::new(nullable, heap_type, exact~),
            ),
          ),
        )
      }
      @lib.Instruction::RefAsNonNull | @lib.Instruction::RefCast(_, _, _) => {
        let operand_type = rse_raw_peek_type(state)
        let value = rse_raw_pop(state)
        let result_type = match instr {
          @lib.Instruction::RefCast(nullable, exact, heap_type) =>
            Some(
              @lib.ValType::ref_type(
                @lib.RefType::new(nullable, heap_type, exact~),
              ),
            )
          @lib.Instruction::RefAsNonNull =>
            match operand_type {
              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
            }
          _ => None
        }
        out.push(instr)
        rse_raw_push(state, value, ty=result_type)
      }
      @lib.Instruction::AnyConvertExtern | @lib.Instruction::ExternConvertAny => {
        let value = rse_raw_pop(state)
        out.push(instr)
        rse_raw_push(state, rse_raw_unary_key(state, instr.to_string(), value))
      }
      @lib.Instruction::StructGet(type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::struct_get(refined_type, field_idx))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::StructGetS(type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::struct_get_s(refined_type, field_idx))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::StructGetU(type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::struct_get_u(refined_type, field_idx))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::StructAtomicGet(order, type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(
              @lib.Instruction::struct_atomic_get(
                order, refined_type, field_idx,
              ),
            )
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::StructAtomicGetS(order, type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(
              @lib.Instruction::struct_atomic_get_s(
                order, refined_type, field_idx,
              ),
            )
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::StructAtomicGetU(order, type_idx, field_idx) => {
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(
              @lib.Instruction::struct_atomic_get_u(
                order, refined_type, field_idx,
              ),
            )
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::ArrayGet(type_idx) => {
        ignore(rse_raw_pop(state))
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::array_get(refined_type))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::ArrayGetS(type_idx) => {
        ignore(rse_raw_pop(state))
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::array_get_s(refined_type))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::ArrayGetU(type_idx) => {
        ignore(rse_raw_pop(state))
        let receiver_type = rse_raw_peek_type(state)
        let receiver = rse_raw_pop(state)
        match
          rse_raw_refined_aggregate_receiver_type(
            state, type_idx, receiver, receiver_type,
          ) {
          Some(refined_type) => {
            out.push(@lib.Instruction::array_get_u(refined_type))
            state.changed = true
          }
          None => out.push(instr)
        }
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::I32Eqz | @lib.Instruction::I64Eqz => {
        let value = rse_raw_pop(state)
        out.push(instr)
        rse_raw_push(state, rse_raw_unary_key(state, instr.to_string(), value))
      }
      @lib.Instruction::I32Add
      | @lib.Instruction::I32Sub
      | @lib.Instruction::I32Mul
      | @lib.Instruction::I32And
      | @lib.Instruction::I32Or
      | @lib.Instruction::I32Xor
      | @lib.Instruction::I32Shl
      | @lib.Instruction::I32ShrS
      | @lib.Instruction::I32ShrU
      | @lib.Instruction::I64Add
      | @lib.Instruction::I64Sub
      | @lib.Instruction::I64Mul
      | @lib.Instruction::I64And
      | @lib.Instruction::I64Or
      | @lib.Instruction::I64Xor
      | @lib.Instruction::I64Shl
      | @lib.Instruction::I64ShrS
      | @lib.Instruction::I64ShrU
      | @lib.Instruction::I32Eq
      | @lib.Instruction::I32Ne
      | @lib.Instruction::I64Eq
      | @lib.Instruction::I64Ne => {
        let rhs = rse_raw_pop(state)
        let lhs = rse_raw_pop(state)
        out.push(instr)
        rse_raw_push(
          state,
          rse_raw_binary_key(state, instr.to_string(), lhs, rhs),
        )
      }
      @lib.Instruction::If(block_type, then_body, else_body) => {
        ignore(rse_raw_pop(state))
        let entry = RseRawState::clone_from(state)
        let scope = RseRawLabelScope::new(RseRawLabelKind::ExitLabel)
        scopes.push(scope)
        let then_state = RseRawState::clone_from(state)
        let next_then = rse_raw_rewrite_expr_scoped(
          then_body, then_state, scopes,
        )
        let (next_else, else_state) = match else_body {
          Some(else_instrs) => {
            let branch_state = RseRawState::clone_from(entry)
            (
              Some(
                rse_raw_rewrite_expr_scoped(else_instrs, branch_state, scopes),
              ),
              branch_state,
            )
          }
          None => (None, entry)
        }
        ignore(scopes.pop())
        if then_state.next_unknown > state.next_unknown {
          state.next_unknown = then_state.next_unknown
        }
        if else_state.next_unknown > state.next_unknown {
          state.next_unknown = else_state.next_unknown
        }
        if then_state.changed || else_state.changed {
          state.changed = true
        }
        let sources : Array[Array[Int32]] = []
        if then_state.reachable {
          sources.push(then_state.local_values.copy())
        }
        if else_state.reachable {
          sources.push(else_state.local_values.copy())
        }
        for exit in scope.exits {
          sources.push(exit)
        }
        rse_raw_merge_sources(state, sources)
        out.push(@lib.Instruction::if_(block_type, next_then, next_else))
        if state.reachable {
          rse_raw_push(state, rse_raw_fresh(state))
        }
      }
      @lib.Instruction::Try(_, _, _, _) => {
        // Legacy handlers may write locals and branch to enclosing labels.
        // Until their flow is modeled, no incoming value equality survives.
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        for scope in scopes {
          scope.exits.push(state.local_values.copy())
          if scope.kind is RseRawLabelKind::LoopLabel {
            scope.has_loop_branch = true
          }
        }
        out.push(instr)
      }
      @lib.Instruction::TryTable(block_type, catches, @lib.Expr(body)) => {
        // Catch destinations are resolved outside the try_table body label.
        // A throw may follow arbitrary local writes inside the protected body.
        let exceptional = RseRawState::clone_from(state)
        rse_raw_clear_values(exceptional)
        for catch_ in catches {
          let target = match catch_ {
            @lib.Catch(_, label)
            | @lib.CatchRef(_, label)
            | @lib.CatchAll(label)
            | @lib.CatchAllRef(label) => label
          }
          rse_raw_record_branch_exit(
            exceptional,
            scopes,
            rse_raw_label_depth(target),
          )
        }
        let body_state = RseRawState::clone_from(state)
        let scope = RseRawLabelScope::new(RseRawLabelKind::ExitLabel)
        scopes.push(scope)
        let next = rse_raw_rewrite_expr_scoped(body, body_state, scopes)
        ignore(scopes.pop())
        if body_state.changed {
          state.changed = true
        }
        if body_state.next_unknown > state.next_unknown {
          state.next_unknown = body_state.next_unknown
        }
        out.push(
          @lib.Instruction::try_table(block_type, catches, @lib.Expr::new(next)),
        )
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = true
        rse_raw_push(state, rse_raw_fresh(state))
      }
      @lib.Instruction::Block(block_type, @lib.Expr(body)) => {
        // Wasm validation restores the entry initialization set at a control
        // boundary, even when runtime value flow proves the write executes.
        let entry_initialized = state.initialized.copy()
        let scope = RseRawLabelScope::new(RseRawLabelKind::ExitLabel)
        scopes.push(scope)
        let next = rse_raw_rewrite_expr_scoped(body, state, scopes)
        state.initialized = entry_initialized
        ignore(scopes.pop())
        let sources : Array[Array[Int32]] = []
        if state.reachable {
          sources.push(state.local_values.copy())
        }
        for exit in scope.exits {
          sources.push(exit)
        }
        rse_raw_merge_sources(state, sources)
        out.push(@lib.Instruction::block(block_type, @lib.Expr::new(next)))
        if state.reachable {
          rse_raw_push(state, rse_raw_fresh(state))
        }
      }
      @lib.Instruction::Loop(block_type, @lib.Expr(body)) => {
        let loop_summary = rse_raw_loop_summary(state, body)
        let loop_state = RseRawState::clone_from(state)
        rse_raw_prepare_loop_entry(state, loop_state, body, loop_summary)
        let scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
        scopes.push(scope)
        let next = rse_raw_rewrite_expr_scoped(body, loop_state, scopes)
        ignore(scopes.pop())
        if loop_state.changed {
          state.changed = true
        }
        if loop_state.next_unknown > state.next_unknown {
          state.next_unknown = loop_state.next_unknown
        }
        if loop_state.reachable && !scope.has_loop_branch {
          state.candidates_by_value = None
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            state.local_values[local_id] = loop_state.local_values[local_id]
          }
          state.reachable = true
        } else if !loop_state.reachable && !scope.has_loop_branch {
          rse_raw_clear_values(state)
          state.reachable = false
        } else {
          let entry_values = state.local_values.copy()
          rse_raw_clear_values(state)
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            let entry_value = entry_values[local_id]
            if loop_summary.writes[local_id] == 0 {
              state.local_values[local_id] = entry_value
            } else if entry_value != -1 {
              let mut agrees = true
              if loop_state.reachable &&
                loop_state.local_values[local_id] != entry_value {
                agrees = false
              }
              for exit in scope.exits {
                if exit[local_id] != entry_value {
                  agrees = false
                }
              }
              if agrees {
                state.local_values[local_id] = entry_value
              }
            }
          }
          state.reachable = true
        }
        out.push(@lib.Instruction::loop_(block_type, @lib.Expr::new(next)))
        rse_raw_clear_stack(state)
        if state.reachable {
          rse_raw_push(state, rse_raw_fresh(state))
        }
      }
      @lib.Instruction::Br(label_idx) => {
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::BrIf(label_idx)
      | @lib.Instruction::BrOnNull(label_idx)
      | @lib.Instruction::BrOnNonNull(label_idx)
      | @lib.Instruction::BrOnCast(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastFail(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastDescEq(label_idx, _, _)
      | @lib.Instruction::BrOnCastDescEqFail(label_idx, _, _) => {
        ignore(rse_raw_pop(state))
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        rse_raw_clear_stack(state)
      }
      @lib.Instruction::BrTable(label_idxs, fallback) => {
        ignore(rse_raw_pop(state))
        for target in label_idxs {
          rse_raw_record_branch_exit(state, scopes, rse_raw_label_depth(target))
        }
        rse_raw_record_branch_exit(state, scopes, rse_raw_label_depth(fallback))
        out.push(instr)
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::Resume(_, handlers)
      | @lib.Instruction::ResumeThrow(_, _, handlers)
      | @lib.Instruction::ResumeThrowRef(_, handlers) => {
        rse_raw_record_resume_handler_exits(state, scopes, handlers)
        out.push(instr)
        rse_raw_clear_stack(state)
      }
      @lib.Instruction::Return | @lib.Instruction::Unreachable => {
        out.push(instr)
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      _ => {
        out.push(instr)
        // Conservatively forget stack-producing details for unmodeled operations.
        rse_raw_clear_stack(state)
      }
    }
  }
  out
}

///|
fn rse_raw_rewrite_expr(
  instrs : Array[@lib.Instruction],
  state : RseRawState,
) -> Array[@lib.Instruction] {
  let scopes : Array[RseRawLabelScope] = []
  rse_raw_rewrite_expr_scoped(instrs, state, scopes)
}

///|
priv struct RseRawI32UnaryKey {
  tag : Int32
  value : Int32
} derive(Eq, Hash)

///|
fn RseRawI32UnaryKey::new(tag : Int32, value : Int32) -> RseRawI32UnaryKey {
  { tag, value, }
}

///|
priv struct RseRawI32Interner {
  const_ids : @hashmap.HashMap[Int32, Int32]
  unary_ids : @hashmap.HashMap[RseRawI32UnaryKey, Int32]
  mut next_value : Int32
}

///|
fn RseRawI32Interner::new(capacity : Int32) -> RseRawI32Interner {
  {
    const_ids: @hashmap.new(capacity~),
    unary_ids: @hashmap.new(capacity=capacity * 2 + 1),
    next_value: 0,
  }
}

///|
priv struct RseRawI32State {
  local_values : Array[Int32]
  stack : Array[Int32]
  interner : RseRawI32Interner
  mut changed : Bool
  mut reachable : Bool
}

///|
fn RseRawI32State::new(
  local_count : Int32,
  param_count : Int32,
) -> RseRawI32State {
  let state = {
    local_values: Array::make(local_count, -1),
    stack: [],
    interner: RseRawI32Interner::new(local_count * 4 + 17),
    changed: false,
    reachable: true,
  }
  for local_id = 0; local_id < local_count; local_id = local_id + 1 {
    state.local_values[local_id] = if local_id < param_count {
      rse_raw_i32_fresh(state)
    } else {
      rse_raw_i32_const_value(state, 0)
    }
  }
  state
}

///|
fn RseRawI32State::clone_from(other : RseRawI32State) -> RseRawI32State {
  {
    local_values: other.local_values.copy(),
    stack: other.stack.copy(),
    interner: other.interner,
    changed: other.changed,
    reachable: other.reachable,
  }
}

///|
fn rse_raw_i32_fresh(state : RseRawI32State) -> Int32 {
  let value = state.interner.next_value
  state.interner.next_value += 1
  value
}

///|
fn rse_raw_i32_const_value(state : RseRawI32State, raw : Int32) -> Int32 {
  match state.interner.const_ids.get(raw) {
    Some(value) => value
    None => {
      let value = rse_raw_i32_fresh(state)
      state.interner.const_ids.set(raw, value)
      value
    }
  }
}

///|
fn rse_raw_i32_unary_value(
  state : RseRawI32State,
  tag : Int32,
  value : Int32,
) -> Int32 {
  if value == -1 {
    -1
  } else {
    let key = RseRawI32UnaryKey::new(tag, value)
    match state.interner.unary_ids.get(key) {
      Some(result) => result
      None => {
        let result = rse_raw_i32_fresh(state)
        state.interner.unary_ids.set(key, result)
        result
      }
    }
  }
}

///|
fn rse_raw_i32_value_code(value : Int32) -> Int32? {
  let base = 4096
  if value >= 0 && value < base {
    Some(value)
  } else if value <= -2 {
    let code = 0 - value - 2
    if code < base {
      Some(base + code)
    } else {
      None
    }
  } else {
    None
  }
}

///|
fn rse_raw_i32_binary_value(
  state : RseRawI32State,
  tag : Int32,
  lhs : Int32,
  rhs : Int32,
) -> Int32 {
  if lhs == -1 || rhs == -1 {
    -1
  } else {
    match (rse_raw_i32_value_code(lhs), rse_raw_i32_value_code(rhs)) {
      (Some(lhs_code), Some(rhs_code)) => {
        let base = 8192
        0 - 2 - (tag * base * base + lhs_code * base + rhs_code)
      }
      _ => rse_raw_i32_fresh(state)
    }
  }
}

///|
fn rse_raw_i32_pop(state : RseRawI32State) -> Int32 {
  match state.stack.pop() {
    Some(value) => value
    None => -1
  }
}

///|
fn rse_raw_i32_push(state : RseRawI32State, value : Int32) -> Unit {
  state.stack.push(value)
}

///|
fn rse_raw_i32_local_get(state : RseRawI32State, local_id : Int32) -> Int32 {
  if local_id >= 0 && local_id < state.local_values.length() {
    state.local_values[local_id]
  } else {
    -1
  }
}

///|
fn rse_raw_i32_local_set(
  state : RseRawI32State,
  local_id : Int32,
  value : Int32,
) -> Unit {
  if local_id >= 0 && local_id < state.local_values.length() {
    state.local_values[local_id] = value
  }
}

///|
fn rse_raw_i32_clear_values(state : RseRawI32State) -> Unit {
  for local_id = 0
      local_id < state.local_values.length()
      local_id = local_id + 1 {
    state.local_values[local_id] = -1
  }
}

///|
fn rse_raw_i32_record_branch_exit(
  state : RseRawI32State,
  scopes : Array[RseRawLabelScope],
  label_depth : Int32,
) -> Unit {
  if label_depth < 0 || label_depth >= scopes.length() {
    return
  }
  let scope = scopes[scopes.length() - 1 - label_depth]
  match scope.kind {
    RseRawLabelKind::LoopLabel => {
      scope.has_loop_branch = true
      scope.exits.push(state.local_values.copy())
    }
    _ => scope.exits.push(state.local_values.copy())
  }
}

///|
fn rse_raw_i32_const_instr_value(
  state : RseRawI32State,
  instr : @lib.Instruction,
) -> Int32? {
  match instr {
    @lib.Instruction::I32Const(@lib.I32(raw)) =>
      Some(rse_raw_i32_const_value(state, raw))
    _ => None
  }
}

///|
priv struct RseRawI32LoopSummary {
  writes : Array[Int32]
  same_values : Array[Int32]
  disagreed : Array[Bool]
  default_writes : Array[Int32]
  default_values : Array[Int32]
}

///|
fn RseRawI32LoopSummary::new(state : RseRawI32State) -> RseRawI32LoopSummary {
  let count = state.local_values.length()
  let zero = rse_raw_i32_const_value(state, 0)
  {
    writes: Array::make(count, 0),
    same_values: Array::make(count, -1),
    disagreed: Array::make(count, false),
    default_writes: Array::make(count, 0),
    default_values: Array::make(count, zero),
  }
}

///|
fn rse_raw_i32_loop_summary_record_write(
  summary : RseRawI32LoopSummary,
  local_id : Int32,
  value : Int32,
) -> Unit {
  if local_id < 0 || local_id >= summary.writes.length() {
    return
  }
  summary.writes[local_id] += 1
  if value == -1 {
    summary.disagreed[local_id] = true
  } else if summary.same_values[local_id] == -1 {
    summary.same_values[local_id] = value
  } else if summary.same_values[local_id] != value {
    summary.disagreed[local_id] = true
  }
  if value != -1 && value == summary.default_values[local_id] {
    summary.default_writes[local_id] += 1
  }
}

///|
fn rse_raw_i32_loop_summary_same_value(
  summary : RseRawI32LoopSummary,
  local_id : Int32,
) -> Int32 {
  if summary.disagreed[local_id] {
    -1
  } else {
    summary.same_values[local_id]
  }
}

///|
fn rse_raw_i32_binary_tag(instr : @lib.Instruction) -> Int32? {
  match instr {
    @lib.Instruction::I32Add => Some(1)
    @lib.Instruction::I32Sub => Some(2)
    @lib.Instruction::I32Mul => Some(3)
    @lib.Instruction::I32And => Some(4)
    @lib.Instruction::I32Or => Some(5)
    @lib.Instruction::I32Xor => Some(6)
    @lib.Instruction::I32Shl => Some(7)
    @lib.Instruction::I32ShrS => Some(8)
    @lib.Instruction::I32ShrU => Some(9)
    @lib.Instruction::I32Eq => Some(10)
    @lib.Instruction::I32Ne => Some(11)
    @lib.Instruction::I32LtS => Some(12)
    @lib.Instruction::I32LtU => Some(13)
    @lib.Instruction::I32GtS => Some(14)
    @lib.Instruction::I32GtU => Some(15)
    @lib.Instruction::I32LeS => Some(16)
    @lib.Instruction::I32LeU => Some(17)
    @lib.Instruction::I32GeS => Some(18)
    @lib.Instruction::I32GeU => Some(19)
    _ => None
  }
}

///|
fn rse_raw_i32_probe_expr_scoped(
  instrs : Array[@lib.Instruction],
  state : RseRawI32State,
  scopes : Array[RseRawLabelScope],
  summary : RseRawI32LoopSummary?,
) -> Bool {
  for idx = 0; idx < instrs.length(); idx = idx + 1 {
    let instr = instrs[idx]
    if !state.reachable {
      continue
    }
    match instr {
      @lib.Instruction::I32Const(@lib.I32(raw)) =>
        rse_raw_i32_push(state, rse_raw_i32_const_value(state, raw))
      @lib.Instruction::LocalGet(local_idx) => {
        let local_id = rse_raw_local_id(local_idx)
        let value = match rse_raw_i32_local_get(state, local_id) {
          -1 => {
            let fresh = rse_raw_i32_fresh(state)
            rse_raw_i32_local_set(state, local_id, fresh)
            fresh
          }
          known => known
        }
        rse_raw_i32_push(state, value)
      }
      @lib.Instruction::LocalSet(local_idx) => {
        let value = rse_raw_i32_pop(state)
        match summary {
          Some(summary) => {
            let summary_value = if idx > 0 {
              match rse_raw_i32_const_instr_value(state, instrs[idx - 1]) {
                Some(value) => value
                None => -1
              }
            } else {
              -1
            }
            rse_raw_i32_loop_summary_record_write(
              summary,
              rse_raw_local_id(local_idx),
              summary_value,
            )
          }
          None => ()
        }
        rse_raw_i32_local_set(state, rse_raw_local_id(local_idx), value)
      }
      @lib.Instruction::LocalTee(local_idx) => {
        let value = match state.stack.last() {
          Some(v) => v
          None => -1
        }
        match summary {
          Some(summary) => {
            let summary_value = if idx > 0 {
              match rse_raw_i32_const_instr_value(state, instrs[idx - 1]) {
                Some(value) => value
                None => -1
              }
            } else {
              -1
            }
            rse_raw_i32_loop_summary_record_write(
              summary,
              rse_raw_local_id(local_idx),
              summary_value,
            )
          }
          None => ()
        }
        rse_raw_i32_local_set(state, rse_raw_local_id(local_idx), value)
      }
      @lib.Instruction::Drop => ignore(rse_raw_i32_pop(state))
      @lib.Instruction::I32Eqz => {
        let value = rse_raw_i32_pop(state)
        rse_raw_i32_push(state, rse_raw_i32_unary_value(state, 1, value))
      }
      @lib.Instruction::Loop(_, @lib.Expr(body)) => {
        let loop_state = RseRawI32State::clone_from(state)
        let loop_scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
        scopes.push(loop_scope)
        if !rse_raw_i32_probe_expr_scoped(body, loop_state, scopes, summary) {
          return false
        }
        ignore(scopes.pop())
        rse_raw_i32_clear_values(state)
        state.stack.clear()
        state.reachable = true
        rse_raw_i32_push(state, rse_raw_i32_fresh(state))
      }
      @lib.Instruction::Br(label_idx) => {
        rse_raw_i32_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        state.stack.clear()
        rse_raw_i32_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::BrIf(label_idx) => {
        ignore(rse_raw_i32_pop(state))
        rse_raw_i32_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        state.stack.clear()
      }
      @lib.Instruction::Return | @lib.Instruction::Unreachable => {
        state.stack.clear()
        rse_raw_i32_clear_values(state)
        state.reachable = false
      }
      _ =>
        match rse_raw_i32_binary_tag(instr) {
          Some(tag) => {
            let rhs = rse_raw_i32_pop(state)
            let lhs = rse_raw_i32_pop(state)
            rse_raw_i32_push(
              state,
              rse_raw_i32_binary_value(state, tag, lhs, rhs),
            )
          }
          None => return false
        }
    }
  }
  true
}

///|
priv struct RseRawI32LoopEntryAnalysis {
  summary : RseRawI32LoopSummary
  stable_entry : Array[Bool]
}

///|
fn RseRawI32LoopEntryAnalysis::new(
  summary : RseRawI32LoopSummary,
  stable_entry : Array[Bool],
) -> RseRawI32LoopEntryAnalysis {
  { summary, stable_entry, }
}

///|
fn rse_raw_i32_loop_entry_analysis(
  state : RseRawI32State,
  body : Array[@lib.Instruction],
) -> RseRawI32LoopEntryAnalysis? {
  let stable = Array::make(state.local_values.length(), false)
  let summary = RseRawI32LoopSummary::new(state)
  let probe = RseRawI32State::clone_from(state)
  probe.stack.clear()
  let probe_scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
  let probe_scopes : Array[RseRawLabelScope] = [probe_scope]
  if !rse_raw_i32_probe_expr_scoped(body, probe, probe_scopes, Some(summary)) {
    return None
  }
  if probe_scope.has_loop_branch {
    for local_id = 0
        local_id < state.local_values.length()
        local_id = local_id + 1 {
      let entry_value = state.local_values[local_id]
      if entry_value == -1 {
        continue
      }
      let mut agrees = true
      for exit in probe_scope.exits {
        if exit[local_id] != entry_value {
          agrees = false
        }
      }
      if agrees {
        stable[local_id] = true
      }
    }
  }
  Some(RseRawI32LoopEntryAnalysis::new(summary, stable))
}

///|
fn rse_raw_i32_prepare_loop_entry(
  state : RseRawI32State,
  loop_state : RseRawI32State,
  stable_entry : Array[Bool],
  summary : RseRawI32LoopSummary,
) -> Unit {
  rse_raw_i32_clear_values(loop_state)
  loop_state.stack.clear()
  for local_id = 0
      local_id < loop_state.local_values.length()
      local_id = local_id + 1 {
    let writes = summary.writes[local_id]
    let same_write_value = rse_raw_i32_loop_summary_same_value(
      summary, local_id,
    )
    if writes == 0 || stable_entry[local_id] {
      loop_state.local_values[local_id] = state.local_values[local_id]
    } else {
      let default_value = summary.default_values[local_id]
      if writes == summary.default_writes[local_id] &&
        state.local_values[local_id] == default_value {
        loop_state.local_values[local_id] = default_value
      } else if same_write_value != -1 &&
        state.local_values[local_id] == same_write_value {
        loop_state.local_values[local_id] = same_write_value
      }
    }
  }
}

///|
fn rse_raw_i32_rewrite_expr_scoped(
  instrs : Array[@lib.Instruction],
  state : RseRawI32State,
  scopes : Array[RseRawLabelScope],
) -> Array[@lib.Instruction]? {
  let out : Array[@lib.Instruction] = []
  for instr in instrs {
    if !state.reachable {
      out.push(instr)
      continue
    }
    match instr {
      @lib.Instruction::I32Const(@lib.I32(raw)) => {
        out.push(instr)
        rse_raw_i32_push(state, rse_raw_i32_const_value(state, raw))
      }
      @lib.Instruction::LocalGet(local_idx) => {
        out.push(instr)
        let local_id = rse_raw_local_id(local_idx)
        let value = match rse_raw_i32_local_get(state, local_id) {
          -1 => {
            let fresh = rse_raw_i32_fresh(state)
            rse_raw_i32_local_set(state, local_id, fresh)
            fresh
          }
          known => known
        }
        rse_raw_i32_push(state, value)
      }
      @lib.Instruction::LocalSet(local_idx) => {
        let value = rse_raw_i32_pop(state)
        let local_id = rse_raw_local_id(local_idx)
        if value != -1 && rse_raw_i32_local_get(state, local_id) == value {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else if value == -1 && rse_raw_out_ends_with_local_get(out, local_id) {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else {
          out.push(instr)
        }
        rse_raw_i32_local_set(state, local_id, value)
      }
      @lib.Instruction::LocalTee(local_idx) => {
        let value = match state.stack.last() {
          Some(v) => v
          None => -1
        }
        let local_id = rse_raw_local_id(local_idx)
        if value != -1 && rse_raw_i32_local_get(state, local_id) == value {
          state.changed = true
        } else if value == -1 && rse_raw_out_ends_with_local_get(out, local_id) {
          state.changed = true
        } else {
          out.push(instr)
        }
        rse_raw_i32_local_set(state, local_id, value)
      }
      @lib.Instruction::Drop => {
        ignore(rse_raw_i32_pop(state))
        out.push(instr)
      }
      @lib.Instruction::I32Eqz => {
        let value = rse_raw_i32_pop(state)
        out.push(instr)
        rse_raw_i32_push(state, rse_raw_i32_unary_value(state, 1, value))
      }
      @lib.Instruction::Loop(block_type, @lib.Expr(body)) => {
        let loop_analysis = match rse_raw_i32_loop_entry_analysis(state, body) {
          Some(analysis) => analysis
          None => return None
        }
        let loop_summary = loop_analysis.summary
        let loop_state = RseRawI32State::clone_from(state)
        rse_raw_i32_prepare_loop_entry(
          state,
          loop_state,
          loop_analysis.stable_entry,
          loop_summary,
        )
        let scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
        scopes.push(scope)
        let next = match
          rse_raw_i32_rewrite_expr_scoped(body, loop_state, scopes) {
          Some(next) => next
          None => return None
        }
        ignore(scopes.pop())
        if loop_state.changed {
          state.changed = true
        }
        if loop_state.reachable && !scope.has_loop_branch {
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            state.local_values[local_id] = loop_state.local_values[local_id]
          }
          state.reachable = true
        } else if !loop_state.reachable && !scope.has_loop_branch {
          rse_raw_i32_clear_values(state)
          state.reachable = false
        } else {
          let entry_values = state.local_values.copy()
          rse_raw_i32_clear_values(state)
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            let entry_value = entry_values[local_id]
            if loop_summary.writes[local_id] == 0 {
              state.local_values[local_id] = entry_value
            } else if entry_value != -1 {
              let mut agrees = true
              if loop_state.reachable &&
                loop_state.local_values[local_id] != entry_value {
                agrees = false
              }
              for exit in scope.exits {
                if exit[local_id] != entry_value {
                  agrees = false
                }
              }
              if agrees {
                state.local_values[local_id] = entry_value
              }
            }
          }
          state.reachable = true
        }
        out.push(@lib.Instruction::loop_(block_type, @lib.Expr::new(next)))
        state.stack.clear()
        if state.reachable {
          rse_raw_i32_push(state, rse_raw_i32_fresh(state))
        }
      }
      @lib.Instruction::Br(label_idx) => {
        rse_raw_i32_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        state.stack.clear()
        rse_raw_i32_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::BrIf(label_idx) => {
        ignore(rse_raw_i32_pop(state))
        rse_raw_i32_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        state.stack.clear()
      }
      @lib.Instruction::Return | @lib.Instruction::Unreachable => {
        out.push(instr)
        state.stack.clear()
        rse_raw_i32_clear_values(state)
        state.reachable = false
      }
      _ =>
        match rse_raw_i32_binary_tag(instr) {
          Some(tag) => {
            let rhs = rse_raw_i32_pop(state)
            let lhs = rse_raw_i32_pop(state)
            out.push(instr)
            rse_raw_i32_push(
              state,
              rse_raw_i32_binary_value(state, tag, lhs, rhs),
            )
          }
          None => return None
        }
    }
  }
  Some(out)
}

///|
fn rse_raw_i32_rewrite_expr(
  instrs : Array[@lib.Instruction],
  state : RseRawI32State,
) -> Array[@lib.Instruction]? {
  let scopes : Array[RseRawLabelScope] = []
  rse_raw_i32_rewrite_expr_scoped(instrs, state, scopes)
}

///|
fn rse_raw_i32_types_ok(local_types : Array[@lib.ValType]) -> Bool {
  for ty in local_types {
    match ty {
      @lib.NumTypeValType(@lib.I32NumType) => ()
      _ => return false
    }
  }
  true
}

///|
fn rse_raw_fast_type_ok(ty : @lib.ValType) -> Bool {
  match ty {
    @lib.NumTypeValType(_) => true
    _ => false
  }
}

///|
fn rse_raw_fast_types_ok(local_types : Array[@lib.ValType]) -> Bool {
  for ty in local_types {
    if !rse_raw_fast_type_ok(ty) {
      return false
    }
  }
  true
}

///|
fn rse_raw_fast_rewrite_expr_scoped(
  instrs : Array[@lib.Instruction],
  state : RseRawState,
  scopes : Array[RseRawLabelScope],
) -> Array[@lib.Instruction]? {
  let out : Array[@lib.Instruction] = []
  for instr in instrs {
    if !state.reachable {
      out.push(instr)
      continue
    }
    match instr {
      @lib.Instruction::I32Const(_)
      | @lib.Instruction::I64Const(_)
      | @lib.Instruction::F32Const(_)
      | @lib.Instruction::F64Const(_) => {
        out.push(instr)
        match rse_raw_default_instr_value(state, instr) {
          Some(value) => rse_raw_push(state, value)
          None => rse_raw_push(state, rse_raw_fresh(state))
        }
      }
      @lib.Instruction::LocalGet(local_idx) => {
        out.push(instr)
        let local_id = rse_raw_local_id(local_idx)
        let value = match rse_raw_local_get(state, local_id) {
          -1 => {
            let fresh = rse_raw_fresh(state)
            rse_raw_local_set(state, local_id, fresh)
            fresh
          }
          known => known
        }
        rse_raw_push(state, value)
      }
      @lib.Instruction::LocalSet(local_idx) => {
        let value = rse_raw_pop(state)
        let local_id = rse_raw_local_id(local_idx)
        if value != -1 && rse_raw_local_get(state, local_id) == value {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else if value == -1 && rse_raw_out_ends_with_local_get(out, local_id) {
          out.push(@lib.Instruction::drop())
          state.changed = true
        } else {
          out.push(instr)
        }
        rse_raw_local_set(state, local_id, value)
      }
      @lib.Instruction::LocalTee(local_idx) => {
        let value = match state.stack.last() {
          Some(v) => v
          None => -1
        }
        let local_id = rse_raw_local_id(local_idx)
        if value != -1 && rse_raw_local_get(state, local_id) == value {
          state.changed = true
        } else if value == -1 && rse_raw_out_ends_with_local_get(out, local_id) {
          state.changed = true
        } else {
          out.push(instr)
        }
        rse_raw_local_set(state, local_id, value)
      }
      @lib.Instruction::Drop => {
        ignore(rse_raw_pop(state))
        out.push(instr)
      }
      @lib.Instruction::I32Eqz | @lib.Instruction::I64Eqz => {
        let value = rse_raw_pop(state)
        out.push(instr)
        let tag = match instr {
          @lib.Instruction::I32Eqz => 1
          _ => 2
        }
        rse_raw_push(state, rse_raw_unary_tag_key(state, tag, value))
      }
      @lib.Instruction::Loop(block_type, @lib.Expr(body)) => {
        let loop_summary = rse_raw_loop_summary(state, body)
        let loop_state = RseRawState::clone_from(state)
        rse_raw_prepare_loop_entry(state, loop_state, body, loop_summary)
        let scope = RseRawLabelScope::new(RseRawLabelKind::LoopLabel)
        scopes.push(scope)
        let next = match
          rse_raw_fast_rewrite_expr_scoped(body, loop_state, scopes) {
          Some(next) => next
          None => return None
        }
        ignore(scopes.pop())
        if loop_state.changed {
          state.changed = true
        }
        if loop_state.next_unknown > state.next_unknown {
          state.next_unknown = loop_state.next_unknown
        }
        if loop_state.reachable && !scope.has_loop_branch {
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            state.local_values[local_id] = loop_state.local_values[local_id]
          }
          state.reachable = true
        } else if !loop_state.reachable && !scope.has_loop_branch {
          rse_raw_clear_values(state)
          state.reachable = false
        } else {
          let entry_values = state.local_values.copy()
          rse_raw_clear_values(state)
          for local_id = 0
              local_id < state.local_values.length()
              local_id = local_id + 1 {
            let entry_value = entry_values[local_id]
            if loop_summary.writes[local_id] == 0 {
              state.local_values[local_id] = entry_value
            } else if entry_value != -1 {
              let mut agrees = true
              if loop_state.reachable &&
                loop_state.local_values[local_id] != entry_value {
                agrees = false
              }
              for exit in scope.exits {
                if exit[local_id] != entry_value {
                  agrees = false
                }
              }
              if agrees {
                state.local_values[local_id] = entry_value
              }
            }
          }
          state.reachable = true
        }
        out.push(@lib.Instruction::loop_(block_type, @lib.Expr::new(next)))
        rse_raw_clear_stack(state)
        if state.reachable {
          rse_raw_push(state, rse_raw_fresh(state))
        }
      }
      @lib.Instruction::Br(label_idx) => {
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      @lib.Instruction::BrIf(label_idx)
      | @lib.Instruction::BrOnNull(label_idx)
      | @lib.Instruction::BrOnNonNull(label_idx)
      | @lib.Instruction::BrOnCast(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastFail(label_idx, _, _, _)
      | @lib.Instruction::BrOnCastDescEq(label_idx, _, _)
      | @lib.Instruction::BrOnCastDescEqFail(label_idx, _, _) => {
        ignore(rse_raw_pop(state))
        rse_raw_record_branch_exit(
          state,
          scopes,
          rse_raw_label_depth(label_idx),
        )
        out.push(instr)
        rse_raw_clear_stack(state)
      }
      @lib.Instruction::Return | @lib.Instruction::Unreachable => {
        out.push(instr)
        rse_raw_clear_stack(state)
        rse_raw_clear_values(state)
        state.reachable = false
      }
      _ => {
        let rhs = rse_raw_pop(state)
        let lhs = rse_raw_pop(state)
        out.push(instr)
        match rse_raw_fast_binary_tag(instr) {
          Some(tag) =>
            rse_raw_push(state, rse_raw_binary_tag_key(state, tag, lhs, rhs))
          None => return None
        }
      }
    }
  }
  Some(out)
}

///|
fn rse_raw_fast_rewrite_expr(
  instrs : Array[@lib.Instruction],
  state : RseRawState,
) -> Array[@lib.Instruction]? {
  let scopes : Array[RseRawLabelScope] = []
  rse_raw_fast_rewrite_expr_scoped(instrs, state, scopes)
}

///|
fn rse_raw_local_types(
  params : Array[@lib.ValType],
  locals : @lib.Locals,
) -> Array[@lib.ValType] {
  let types = params.copy()
  for local_id = 0; local_id < locals.length(); local_id = local_id + 1 {
    types.push(locals.get(local_id))
  }
  types
}

///|
fn rse_raw_count_local_reads(
  instrs : Array[@lib.Instruction],
  reads : Array[Int32],
) -> Unit {
  for instr in instrs {
    match instr {
      @lib.Instruction::LocalGet(local_idx) => {
        let local_id = rse_raw_local_id(local_idx)
        if local_id >= 0 && local_id < reads.length() {
          reads[local_id] += 1
        }
      }
      @lib.Instruction::Block(_, @lib.Expr(body))
      | @lib.Instruction::Loop(_, @lib.Expr(body))
      | @lib.Instruction::TryTable(_, _, @lib.Expr(body)) =>
        rse_raw_count_local_reads(body, reads)
      @lib.Instruction::If(_, then_body, else_body) => {
        rse_raw_count_local_reads(then_body, reads)
        match else_body {
          Some(body) => rse_raw_count_local_reads(body, reads)
          None => ()
        }
      }
      @lib.Instruction::Try(_, @lib.Expr(body), catches, _) => {
        rse_raw_count_local_reads(body, reads)
        for catch_ in catches {
          match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(catch_body))
            | @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
              rse_raw_count_local_reads(catch_body, reads)
          }
        }
      }
      _ => ()
    }
  }
}

///|
fn rse_raw_unread_set_rhs_is_admitted(
  instrs : Array[@lib.Instruction],
  idx : Int32,
  target_local : Int32,
  local_types : Array[@lib.ValType],
  param_count : Int32,
  env : @validate.Env,
) -> Bool {
  if idx <= 0 || target_local < 0 || target_local >= local_types.length() {
    return false
  }
  match instrs[idx - 1] {
    @lib.Instruction::Block(_, _) => true
    @lib.Instruction::LocalGet(source_idx) => {
      let source_local = rse_raw_local_id(source_idx)
      if source_local < param_count || source_local >= local_types.length() {
        return false
      }
      match
        (
          rse_raw_concrete_ref_type_idx(local_types[source_local]),
          rse_raw_concrete_ref_type_idx(local_types[target_local]),
        ) {
        (Some(_), Some(_)) =>
          local_types[source_local] != local_types[target_local] &&
          @validate.Match::matches(
            local_types[source_local],
            local_types[target_local],
            env,
          )
        _ => false
      }
    }
    _ => false
  }
}

///|
fn rse_raw_remove_unread_local_sets(
  instrs : Array[@lib.Instruction],
  reads : Array[Int32],
  local_types : Array[@lib.ValType],
  param_count : Int32,
  env : @validate.Env,
) -> (Array[@lib.Instruction], Bool) {
  let out : Array[@lib.Instruction] = []
  let mut changed = false
  for idx = 0; idx < instrs.length(); idx = idx + 1 {
    let instr = instrs[idx]
    match instr {
      @lib.Instruction::LocalSet(local_idx) => {
        let local_id = rse_raw_local_id(local_idx)
        if local_id >= 0 &&
          local_id < reads.length() &&
          reads[local_id] == 0 &&
          rse_raw_unread_set_rhs_is_admitted(
            instrs, idx, local_id, local_types, param_count, env,
          ) {
          out.push(@lib.Instruction::drop())
          changed = true
        } else {
          out.push(instr)
        }
      }
      _ => {
        let (rewritten, nested_changed) = pass_rewrite_structured_instr(instr, fn(
          body,
        ) {
          rse_raw_remove_unread_local_sets(
            body, reads, local_types, param_count, env,
          )
        })
        out.push(rewritten)
        if nested_changed {
          changed = true
        }
      }
    }
  }
  (out, changed)
}

///|
fn rse_run_raw_func(
  func : @lib.Func,
  params : Array[@lib.ValType],
  env : @validate.Env,
) -> (@lib.Func, Bool) {
  let @lib.Func(locals, @lib.Expr(instrs)) = func
  let local_types = rse_raw_local_types(params, locals)
  let (rewritten, changed) = if rse_raw_i32_types_ok(local_types) {
    let i32_state = RseRawI32State::new(local_types.length(), params.length())
    match rse_raw_i32_rewrite_expr(instrs, i32_state) {
      Some(rewritten) => (rewritten, i32_state.changed)
      None => {
        let fast_state = RseRawState::new(local_types, params.length(), env)
        match rse_raw_fast_rewrite_expr(instrs, fast_state) {
          Some(rewritten) => (rewritten, fast_state.changed)
          None => {
            let slow_state = RseRawState::new(local_types, params.length(), env)
            (rse_raw_rewrite_expr(instrs, slow_state), slow_state.changed)
          }
        }
      }
    }
  } else if rse_raw_fast_types_ok(local_types) {
    let fast_state = RseRawState::new(local_types, params.length(), env)
    match rse_raw_fast_rewrite_expr(instrs, fast_state) {
      Some(rewritten) => (rewritten, fast_state.changed)
      None => {
        let slow_state = RseRawState::new(local_types, params.length(), env)
        (rse_raw_rewrite_expr(instrs, slow_state), slow_state.changed)
      }
    }
  } else {
    let state = RseRawState::new(local_types, params.length(), env)
    (rse_raw_rewrite_expr(instrs, state), state.changed)
  }
  let reads = Array::make(local_types.length(), 0)
  rse_raw_count_local_reads(rewritten, reads)
  let (cleaned, cleanup_changed) = rse_raw_remove_unread_local_sets(
    rewritten,
    reads,
    local_types,
    params.length(),
    env,
  )
  if changed || cleanup_changed {
    (@lib.Func::new(locals, @lib.Expr::new(cleaned)), true)
  } else {
    (func, false)
  }
}

///|
fn rse_canonicalize_plain_signatures(mod_ : @lib.Module) -> @lib.Module {
  match mod_.type_sec {
    Some(@lib.TypeSec(types)) if types.length() > 1 &&
      types.all(dfe_rec_type_is_unused_suffix_prune_candidate) =>
      // Reuse structural function signatures only. Recursive, GC, indexed-ref,
      // descriptor and supertype identities are outside this cleanup contract.
      dfe_canonicalize_duplicate_simple_type_indices(mod_)
    _ => mod_
  }
}