// 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.

///|
fn pass_module_has_offset_sensitive_metadata(mod_ : @lib.Module) -> Bool {
  for custom in mod_.custom_secs {
    let @lib.CustomSec(@lib.Name(raw_name), _) = custom
    let name = raw_name.to_owned()
    if name.starts_with("metadata.code.") ||
      name.starts_with("reloc.") ||
      name == "linking" ||
      name == "sourceMappingURL" ||
      name == "external_debug_info" ||
      name.starts_with(".debug_") {
      return true
    }
  }
  false
}

///|
pub fn pass_compute_label_used(func : @ir.HotFunc) -> @bitset.BitSet {
  // No target can pass the scan's bounds check without a declared label.
  // Keep this outside the scan to avoid perturbing its nonempty hot loop.
  if func.labels.is_empty() {
    return @bitset.BitSet::new(0)
  }
  pass_compute_label_used_except(func, -1)
}

///|
fn pass_compute_label_used_except(
  func : @ir.HotFunc,
  excluded_node : Int32,
) -> @bitset.BitSet {
  let label_used = @bitset.BitSet::new(func.labels.length())
  let mark_label = fn(label_id : Int32) {
    if label_id >= 0 && label_id < label_used.length() {
      label_used[label_id] = true
    }
  }
  for node_id = 0; node_id < @ir.hot_node_count(func); node_id = node_id + 1 {
    if node_id == excluded_node || !@ir.hot_node_is_live(func, node_id) {
      continue
    }
    let node = @ir.hot_node_get(func, node_id)
    match node.op {
      @ir.HotOp::Br
      | @ir.HotOp::BrIf
      | @ir.HotOp::BrOnNull
      | @ir.HotOp::BrOnNonNull
      | @ir.HotOp::BrOnCast
      | @ir.HotOp::BrOnCastFail
      | @ir.HotOp::Delegate => mark_label(node.imm0)
      @ir.HotOp::BrTable => {
        mark_label(@ir.hot_branch_table_default_target(func, node.imm0))
        for label_id in @ir.hot_branch_table_targets(func, node.imm0) {
          mark_label(label_id)
        }
      }
      @ir.HotOp::Continuation =>
        for label_id in @ir.hot_continuation_targets(func, node_id) {
          mark_label(label_id)
        }
      @ir.HotOp::TryTable => {
        let info = @ir.hot_catch_info_get(func, node.imm1)
        for catch_ in info.catches {
          let label_id = match catch_ {
            @ir.HotCatchArm::CatchArm(_, label_id)
            | @ir.HotCatchArm::CatchRefArm(_, label_id)
            | @ir.HotCatchArm::CatchAllArm(label_id)
            | @ir.HotCatchArm::CatchAllRefArm(label_id) => label_id
          }
          mark_label(label_id)
        }
      }
      _ => ()
    }
  }
  label_used
}

///|
pub fn pass_label_is_used(
  label_id : Int32,
  label_used : @bitset.BitSet,
) -> Bool {
  label_id >= 0 && label_id < label_used.length() && label_used[label_id]
}

///|
fn pass_effect_masks_can_reorder(
  first : @ir.EffectMask,
  second : @ir.EffectMask,
) -> Bool {
  if @ir.effects_is_pure(first) || @ir.effects_is_pure(second) {
    return true
  }
  let hard_barriers = @ir.EFFECT_MASK_CONTROL |
    @ir.EFFECT_MASK_CALL |
    @ir.EFFECT_MASK_THROW
  if (first & hard_barriers) != 0U || (second & hard_barriers) != 0U {
    return false
  }
  if (first & @ir.EFFECT_MASK_TRAP) != 0U &&
    (second & @ir.EFFECT_MASK_TRAP) != 0U {
    // WebAssembly observes the first trap. Two potentially trapping expressions
    // must not cross even when their state categories are otherwise disjoint.
    return false
  }
  let global_writes = @ir.EFFECT_MASK_GLOBAL_STATE |
    @ir.EFFECT_MASK_MEMORY_WRITE |
    @ir.EFFECT_MASK_TABLE_WRITE
  if ((first & @ir.EFFECT_MASK_TRAP) != 0U && (second & global_writes) != 0U) ||
    ((second & @ir.EFFECT_MASK_TRAP) != 0U && (first & global_writes) != 0U) {
    return false
  }
  if (first & @ir.EFFECT_MASK_LOCAL_STATE) != 0U &&
    (second & @ir.EFFECT_MASK_LOCAL_STATE) != 0U {
    return false
  }
  if (first & @ir.EFFECT_MASK_GLOBAL_STATE) != 0U &&
    (second & @ir.EFFECT_MASK_GLOBAL_STATE) != 0U {
    return false
  }
  let first_memory = first &
    (@ir.EFFECT_MASK_MEMORY_READ | @ir.EFFECT_MASK_MEMORY_WRITE)
  let second_memory = second &
    (@ir.EFFECT_MASK_MEMORY_READ | @ir.EFFECT_MASK_MEMORY_WRITE)
  if first_memory != 0U && second_memory != 0U {
    // This coarse motion check keeps all memory pairs ordered. Precise atomic
    // consumers additionally use the shared directional order masks.
    return false
  }
  let first_table = first &
    (@ir.EFFECT_MASK_TABLE_READ | @ir.EFFECT_MASK_TABLE_WRITE)
  let second_table = second &
    (@ir.EFFECT_MASK_TABLE_READ | @ir.EFFECT_MASK_TABLE_WRITE)
  if first_table != 0U && second_table != 0U {
    return false
  }
  true
}

///|
pub fn pass_rewrite_structured_instr(
  instr : @lib.Instruction,
  rewrite_instrs : (Array[@lib.Instruction]) -> (Array[@lib.Instruction], Bool),
) -> (@lib.Instruction, Bool) {
  match instr {
    @lib.Block(block_type, @lib.Expr(body)) => {
      let (next_body, changed) = rewrite_instrs(body)
      if changed {
        (@lib.Instruction::block(block_type, @lib.Expr::new(next_body)), true)
      } else {
        (instr, false)
      }
    }
    @lib.Loop(block_type, @lib.Expr(body)) => {
      let (next_body, changed) = rewrite_instrs(body)
      if changed {
        (@lib.Instruction::loop_(block_type, @lib.Expr::new(next_body)), true)
      } else {
        (instr, false)
      }
    }
    @lib.If(block_type, then_body, else_body) => {
      let (next_then, then_changed) = rewrite_instrs(then_body)
      let (next_else, else_changed) = match else_body {
        Some(body) => {
          let (next, changed) = rewrite_instrs(body)
          (Some(next), changed)
        }
        None => (None, false)
      }
      if then_changed || else_changed {
        (@lib.Instruction::if_(block_type, next_then, next_else), true)
      } else {
        (instr, false)
      }
    }
    @lib.Try(block_type, @lib.Expr(body), catches, delegate) => {
      let (next_body, body_changed) = rewrite_instrs(body)
      let next_catches : Array[@lib.LegacyCatch] = []
      let mut catches_changed = false
      for catch_ in catches {
        match catch_ {
          @lib.LegacyCatch(tag_idx, @lib.Expr(catch_body)) => {
            let (next_catch, changed) = rewrite_instrs(catch_body)
            if changed {
              catches_changed = true
            }
            next_catches.push(
              @lib.LegacyCatch::tagged(tag_idx, @lib.Expr::new(next_catch)),
            )
          }
          @lib.LegacyCatchAll(@lib.Expr(catch_body)) => {
            let (next_catch, changed) = rewrite_instrs(catch_body)
            if changed {
              catches_changed = true
            }
            next_catches.push(@lib.LegacyCatch::all(@lib.Expr::new(next_catch)))
          }
        }
      }
      if body_changed || catches_changed {
        (
          @lib.Instruction::try_(
            block_type,
            @lib.Expr::new(next_body),
            next_catches,
            delegate~,
          ),
          true,
        )
      } else {
        (instr, false)
      }
    }
    @lib.TryTable(block_type, catches, @lib.Expr(body)) => {
      let (next_body, changed) = rewrite_instrs(body)
      if changed {
        (
          @lib.Instruction::try_table(
            block_type,
            catches,
            @lib.Expr::new(next_body),
          ),
          true,
        )
      } else {
        (instr, false)
      }
    }
    _ => (instr, false)
  }
}

///|
fn pass_raw_resume_handlers_have_label(
  handlers : Array[@lib.ResumeHandler],
) -> Bool {
  for handler in handlers {
    match handler {
      @lib.ResumeOnLabel(_, _) => return true
      @lib.ResumeOnSwitch(_) => ()
    }
  }
  false
}

///|
pub fn pass_raw_instr_is_branch_control(instr : @lib.Instruction) -> Bool {
  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::Return
    | @lib.Instruction::ReturnCall(_)
    | @lib.Instruction::ReturnCallIndirect(_, _)
    | @lib.Instruction::ReturnCallRef(_) => true
    @lib.Instruction::Resume(_, handlers)
    | @lib.Instruction::ResumeThrow(_, _, handlers)
    | @lib.Instruction::ResumeThrowRef(_, handlers) =>
      pass_raw_resume_handlers_have_label(handlers)
    _ => false
  }
}

///|
pub fn pass_raw_instrs_have_branch_control(
  instrs : Array[@lib.Instruction],
) -> Bool {
  for instr in instrs {
    if pass_raw_instr_is_branch_control(instr) {
      return true
    }
    match instr {
      @lib.Instruction::Block(_, @lib.Expr(body))
      | @lib.Instruction::Loop(_, @lib.Expr(body)) =>
        if pass_raw_instrs_have_branch_control(body) {
          return true
        }
      @lib.Instruction::If(_, then_body, Some(else_body)) =>
        if pass_raw_instrs_have_branch_control(then_body) ||
          pass_raw_instrs_have_branch_control(else_body) {
          return true
        }
      @lib.Instruction::If(_, then_body, None) =>
        if pass_raw_instrs_have_branch_control(then_body) {
          return true
        }
      @lib.Instruction::Try(_, @lib.Expr(body), catches, delegate) => {
        if delegate is Some(_) {
          return true
        }
        if pass_raw_instrs_have_branch_control(body) {
          return true
        }
        for catch_ in catches {
          let catch_body = match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(catch_body))
            | @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
          }
          if pass_raw_instrs_have_branch_control(catch_body) {
            return true
          }
        }
      }
      @lib.Instruction::TryTable(_, catches, @lib.Expr(body)) => {
        // Every catch form contains a label depth. Inlining an enclosing block
        // would change that depth's destination; this cleanup does not remap it.
        for catch_ in catches {
          match catch_ {
            @lib.Catch(_, _)
            | @lib.CatchRef(_, _)
            | @lib.CatchAll(_)
            | @lib.CatchAllRef(_) => return true
          }
        }
        if pass_raw_instrs_have_branch_control(body) {
          return true
        }
      }
      _ => ()
    }
  }
  false
}

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

///|
fn pass_module_has_legacy_try(mod_ : @lib.Module) -> Bool {
  match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) =>
      for func in funcs {
        let @lib.Func(_, @lib.Expr(body)) = func
        if pass_raw_instrs_have_legacy_try(body) {
          return true
        }
      }
    None => ()
  }
  false
}

///|
pub fn pass_raw_instrs_end_in_unreachable(
  instrs : Array[@lib.Instruction],
) -> Bool {
  if instrs.length() == 0 {
    return false
  }
  match instrs[instrs.length() - 1] {
    @lib.Instruction::Unreachable => true
    _ => false
  }
}

///|
pub fn pass_raw_dropped_block_has_unreachable_tail(
  instr : @lib.Instruction,
) -> Bool {
  match instr {
    @lib.Instruction::Block(_, @lib.Expr(body)) =>
      pass_raw_instrs_end_in_unreachable(body) &&
      !pass_raw_instrs_have_branch_control(body)
    _ => false
  }
}

///|
pub fn pass_raw_void_block_can_inline_before_unreachable(
  instr : @lib.Instruction,
) -> Bool {
  match instr {
    @lib.Instruction::Block(_, @lib.Expr(body)) =>
      !pass_raw_instrs_have_branch_control(body)
    _ => false
  }
}

///|
pub fn pass_raw_collapse_trailing_unreachable_run(
  instrs : Array[@lib.Instruction],
) -> Array[@lib.Instruction] {
  let out : Array[@lib.Instruction] = []
  let mut end = instrs.length()
  while end > 0 {
    match instrs[end - 1] {
      @lib.Instruction::Unreachable => end -= 1
      _ => break
    }
  }
  if end == instrs.length() {
    for instr in instrs {
      out.push(instr)
    }
    return out
  }
  for idx = 0; idx < end; idx = idx + 1 {
    out.push(instrs[idx])
  }
  out.push(@lib.Instruction::unreachable_())
  out
}

///|
pub fn pass_raw_remove_dropped_unreachable_debris(
  instrs : Array[@lib.Instruction],
) -> (Array[@lib.Instruction], Bool) {
  let out : Array[@lib.Instruction] = []
  let mut changed = false
  let mut i = 0
  while i < instrs.length() {
    match instrs[i] {
      @lib.Instruction::Unreachable | @lib.Instruction::Block(_, _) => {
        let mut j = i + 1
        while j < instrs.length() {
          match instrs[j] {
            @lib.Instruction::Drop => j += 1
            _ => break
          }
        }
        if j < instrs.length() {
          match instrs[j] {
            @lib.Instruction::Unreachable =>
              match instrs[i] {
                @lib.Instruction::Unreachable => {
                  changed = true
                  i = j
                  continue
                }
                @lib.Instruction::Block(_, @lib.Expr(body)) =>
                  if pass_raw_dropped_block_has_unreachable_tail(instrs[i]) {
                    let collapsed = pass_raw_collapse_trailing_unreachable_run(
                      body,
                    )
                    let (cleaned_body, _) = pass_raw_remove_dropped_unreachable_debris(
                      collapsed,
                    )
                    for body_instr in cleaned_body {
                      out.push(body_instr)
                    }
                    changed = true
                    i = j + 1
                    continue
                  } else if pass_raw_void_block_can_inline_before_unreachable(
                      instrs[i],
                    ) {
                    let (cleaned_body, _) = pass_raw_remove_dropped_unreachable_debris(
                      body,
                    )
                    for body_instr in cleaned_body {
                      out.push(body_instr)
                    }
                    changed = true
                    i += 1
                    continue
                  }
                _ => ()
              }
            _ => ()
          }
        }
      }
      _ => ()
    }
    let rewritten_instr = match instrs[i] {
      @lib.Instruction::Block(block_type, @lib.Expr(body)) => {
        let (next_body, body_changed) = pass_raw_remove_dropped_unreachable_debris(
          body,
        )
        if body_changed {
          changed = true
        }
        @lib.Instruction::block(block_type, @lib.Expr::new(next_body))
      }
      @lib.Instruction::Loop(block_type, @lib.Expr(body)) => {
        let (next_body, body_changed) = pass_raw_remove_dropped_unreachable_debris(
          body,
        )
        if body_changed {
          changed = true
        }
        @lib.Instruction::loop_(block_type, @lib.Expr::new(next_body))
      }
      @lib.Instruction::If(block_type, then_body, else_body) => {
        let (next_then, then_changed) = pass_raw_remove_dropped_unreachable_debris(
          then_body,
        )
        let (next_else, else_changed) = match else_body {
          Some(body) => {
            let (body2, changed2) = pass_raw_remove_dropped_unreachable_debris(
              body,
            )
            (Some(body2), changed2)
          }
          None => (None, false)
        }
        if then_changed || else_changed {
          changed = true
        }
        @lib.Instruction::if_(block_type, next_then, next_else)
      }
      @lib.Instruction::Try(block_type, @lib.Expr(body), catches, delegate) => {
        let (next_body, body_changed) = pass_raw_remove_dropped_unreachable_debris(
          body,
        )
        let next_catches : Array[@lib.LegacyCatch] = []
        let mut catches_changed = false
        for catch_ in catches {
          match catch_ {
            @lib.LegacyCatch(tag_idx, @lib.Expr(catch_body)) => {
              let (next_catch, changed2) = pass_raw_remove_dropped_unreachable_debris(
                catch_body,
              )
              if changed2 {
                catches_changed = true
              }
              next_catches.push(
                @lib.LegacyCatch::tagged(tag_idx, @lib.Expr::new(next_catch)),
              )
            }
            @lib.LegacyCatchAll(@lib.Expr(catch_body)) => {
              let (next_catch, changed2) = pass_raw_remove_dropped_unreachable_debris(
                catch_body,
              )
              if changed2 {
                catches_changed = true
              }
              next_catches.push(
                @lib.LegacyCatch::all(@lib.Expr::new(next_catch)),
              )
            }
          }
        }
        if body_changed || catches_changed {
          changed = true
        }
        @lib.Instruction::try_(
          block_type,
          @lib.Expr::new(next_body),
          next_catches,
          delegate~,
        )
      }
      @lib.Instruction::TryTable(block_type, catches, @lib.Expr(body)) => {
        let (next_body, body_changed) = pass_raw_remove_dropped_unreachable_debris(
          body,
        )
        if body_changed {
          changed = true
        }
        @lib.Instruction::try_table(
          block_type,
          catches,
          @lib.Expr::new(next_body),
        )
      }
      other => other
    }
    out.push(rewritten_instr)
    i += 1
  }
  (out, changed)
}

///|
pub fn pass_prepare_requirements(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> Unit {
  for analysis in @ir.hot_pass_requires(ctx.descriptor) {
    match analysis {
      @ir.HotAnalysis::Cfg => ignore(pass_require_cfg(ctx, func))
      @ir.HotAnalysis::Dominance => ignore(pass_require_dom(ctx, func))
      @ir.HotAnalysis::Liveness => ignore(pass_require_liveness(ctx, func))
      @ir.HotAnalysis::UseDef => ignore(pass_require_use_def(ctx, func))
      @ir.HotAnalysis::Effects => ignore(pass_require_effects(ctx, func))
      @ir.HotAnalysis::LoopInfo => ignore(pass_require_loop_info(ctx, func))
      @ir.HotAnalysis::Ssa => ignore(pass_require_ssa(ctx, func))
    }
  }
}

///|
pub fn pass_require_cfg(ctx : HotPassContext, func : @ir.HotFunc) -> @ir.HotCfg {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.cfg {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_cfg(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:cfg")
  let cfg = @ir.cache_get_or_build_cfg(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:cfg", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_cfg_build(perf)
      perf_count_traversal_visit(perf, count=@ir.cfg_block_count(cfg))
      perf_dump_cfg(perf, cfg, "analysis:cfg")
    }
    None => ()
  }
  cfg
}

///|
pub fn pass_require_orders(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotCfgOrders {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.orders {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_orders(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:orders")
  let orders = @ir.cache_get_or_build_orders(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:orders", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "orders")
      perf_count_traversal_visit(perf, count=orders.worklist_seed.length())
    }
    None => ()
  }
  orders
}

///|
pub fn pass_require_dom(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotDominators {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.dom {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_dom(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:dom")
  let dom = @ir.cache_get_or_build_dom(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:dom", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "dom")
      perf_count_traversal_visit(
        perf,
        count=@ir.cfg_block_count(pass_require_cfg(ctx, func)),
      )
    }
    None => ()
  }
  dom
}

///|
pub fn pass_require_postdom(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotPostDominators {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.postdom {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_postdom(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:postdom")
  let postdom = @ir.cache_get_or_build_postdom(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:postdom", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "postdom")
      perf_count_traversal_visit(
        perf,
        count=@ir.cfg_block_count(pass_require_cfg(ctx, func)),
      )
    }
    None => ()
  }
  postdom
}

///|
pub fn pass_require_loop_info(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotLoopInfo {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.loop_info {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_loop_info(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:loop-info")
  let loop_info = @ir.cache_get_or_build_loop_info(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:loop-info", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "loop-info")
      perf_count_traversal_visit(
        perf,
        count=@ir.cfg_block_count(pass_require_cfg(ctx, func)),
      )
    }
    None => ()
  }
  loop_info
}

///|
pub fn pass_require_use_def(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotUseDef {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.use_def {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_use_def(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:use-def")
  let use_def = @ir.cache_get_or_build_use_def(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:use-def", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "use-def")
      perf_count_traversal_visit(perf, count=@ir.hot_node_count(func))
    }
    None => ()
  }
  use_def
}

///|
pub fn pass_require_liveness(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotLiveness {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.liveness {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_liveness(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:liveness")
  let liveness = @ir.cache_get_or_build_liveness(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:liveness", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "liveness")
      perf_count_traversal_visit(
        perf,
        count=@ir.cfg_block_count(pass_require_cfg(ctx, func)),
      )
    }
    None => ()
  }
  liveness
}

///|
pub fn pass_require_effects(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotEffectsSummary {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.effects {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_effects(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:effects")
  let effects = @ir.cache_get_or_build_effects(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:effects", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "effects")
      perf_count_traversal_visit(perf, count=@ir.hot_node_count(func))
    }
    None => ()
  }
  effects
}

///|
pub fn pass_require_ssa(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> @ir.HotLocalSsa {
  let revision = @ir.hot_revision_current(func)
  let is_current = match ctx.cache.ssa {
    Some(entry) => entry.built_at_revision == revision
    None => false
  }
  if is_current {
    return @ir.cache_get_or_build_ssa(ctx.cache, func)
  }
  let start_us = perf_start_timer_opt(ctx.perf, "analysis:ssa")
  let ssa = @ir.cache_get_or_build_ssa(ctx.cache, func)
  perf_stop_timer_opt(ctx.perf, "analysis:ssa", start_us)
  match ctx.perf {
    Some(perf) => {
      perf_count_dataflow_build(perf, "ssa")
      perf_count_traversal_visit(
        perf,
        count=@ir.cfg_block_count(pass_require_cfg(ctx, func)),
      )
    }
    None => ()
  }
  ssa
}

///|
pub fn pass_mark_mutated(ctx : HotPassContext, func : @ir.HotFunc) -> Unit {
  @ir.cache_invalidate_analyses(
    ctx.cache,
    @ir.hot_pass_invalidates(ctx.descriptor),
  )
  if ctx.descriptor.name != "vacuum" {
    pipeline_trace_hook(
      ctx.trace,
      ctx.descriptor.name,
      "mutated",
      payload="revision=\{@ir.hot_revision_current(func)}",
    )
  }
}

///|
pub fn pass_replace_node(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_id : Int32,
  new_node : @ir.HotNode,
  preserve_value_order~ : Bool = false,
) -> Unit {
  @ir.hot_replace_node(func, node_id, new_node, preserve_value_order~)
  pass_mark_mutated(ctx, func)
}

///|
pub fn pass_splice_region(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  region_ref : @ir.HotRegionRef,
  idx : Int32,
  remove_count : Int32,
  node_ids : Array[Int32],
) -> Array[Int32] {
  let removed = @ir.hot_region_splice(
    func, region_ref, idx, remove_count, node_ids,
  )
  if remove_count != 0 || !node_ids.is_empty() {
    match ctx.perf {
      Some(perf) => perf_count_region_splice(perf)
      None => ()
    }
    pass_mark_mutated(ctx, func)
  }
  removed
}

///|
pub fn pass_delete_detached_nodes(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_ids : Array[Int32],
) -> Unit {
  let live_node_ids : Array[Int32] = []
  let seen : @set.Set[Int32] = @set.Set([])
  let mut has_control = false
  for node_id in node_ids {
    if @ir.hot_node_is_live(func, node_id) && !seen.contains(node_id) {
      seen.add(node_id)
      live_node_ids.push(node_id)
      has_control = has_control || @ir.hot_is_control_node(func, node_id)
    }
  }
  if live_node_ids.is_empty() {
    return
  }
  if has_control {
    if !@ir.hot_delete_detached_forest(func, live_node_ids) {
      abort("pass_delete_detached_nodes requires a detached control forest")
    }
  } else {
    @ir.hot_delete_detached_nodes(func, live_node_ids)
  }
  pass_mark_mutated(ctx, func)
}

///|
pub fn pass_node_use_count(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_id : Int32,
) -> Int32 {
  @ir.node_use_count(pass_require_use_def(ctx, func), node_id)
}

///|
pub fn pass_node_is_unused(
  ctx : HotPassContext,
  func : @ir.HotFunc,
  node_id : Int32,
) -> Bool {
  pass_node_use_count(ctx, func, node_id) == 0
}

///|
pub fn pass_verify_before_after(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> Result[Unit, String] {
  pipeline_verify_checkpoint_with_perf(
    ctx.perf,
    ctx.verify_policy,
    "verify after \{ctx.descriptor.name}",
    HotPipelineVerifyTarget::HotFuncWithCacheTarget(func, ctx.cache),
    "verify:after:\{ctx.descriptor.name}",
  )
}

///|
// Control bodies share HOT's child storage with expression operands. Visitors
// that also walk region roots use this count and pass_value_operand_slot to
// include typed control entries without visiting structural region children.
fn pass_value_operand_count(func : @ir.HotFunc, node_id : Int32) -> Int32 {
  let node = @ir.hot_node_get(func, node_id)
  match node.op {
    @ir.HotOp::Block => node.imm1
    @ir.HotOp::Try | @ir.HotOp::TryTable => 0
    @ir.HotOp::Loop =>
      @ir.hot_label_branch_arity(
        func,
        @ir.hot_control_node_label(func, node_id),
      )
    @ir.HotOp::If => node.child_count - 2
    _ => node.child_count
  }
}

///|
fn pass_value_operand_slot(node : @ir.HotNode, index : Int32) -> Int32 {
  if node.op is @ir.HotOp::If {
    // Entry values execute before the condition. Slots 1 and 2 are regions.
    if index < node.child_count - 3 {
      index + 3
    } else {
      0
    }
  } else {
    index
  }
}

///|
fn pass_can_discard_unused_value(func : @ir.HotFunc, node : Int32) -> Bool {
  let op = @ir.hot_node_get(func, node).op
  match op {
    @ir.Nop
    | @ir.Const
    | @ir.LocalGet
    | @ir.GlobalGet
    | @ir.RefNull
    | @ir.RefFunc
    | @ir.Drop
    | @ir.TupleMake
    | @ir.TupleExtract => true
    @ir.Unary | @ir.Compare | @ir.Select | @ir.RefIsNull | @ir.RefTest => true
    @ir.Binary => vacuum_binary_is_nontrapping(func, node)
    @ir.Convert =>
      vacuum_convert_is_nontrapping(@ir.hot_node_exact_instr(func, node))
    @ir.Simd => vacuum_simd_is_nontrapping(@ir.hot_node_exact_instr(func, node))
    _ => false
  }
}

///|
// Constant identity must preserve signed zero and NaN payloads.
fn pass_hot_const_bits_equal(
  lhs : @ir.HotConstPayload,
  rhs : @ir.HotConstPayload,
) -> Bool {
  match (lhs, rhs) {
    (
      @ir.HotConstPayload::F32Const(@lib.F32(a)),
      @ir.HotConstPayload::F32Const(@lib.F32(b)),
    ) => a.reinterpret_as_int() == b.reinterpret_as_int()
    (
      @ir.HotConstPayload::F64Const(@lib.F64(a)),
      @ir.HotConstPayload::F64Const(@lib.F64(b)),
    ) => a.reinterpret_as_int64() == b.reinterpret_as_int64()
    _ => lhs == rhs
  }
}

///|
fn pass_const_instruction_bits_equal(
  lhs : @lib.Instruction,
  rhs : @lib.Instruction,
) -> Bool {
  match (lhs, rhs) {
    (@lib.F32Const(@lib.F32(a)), @lib.F32Const(@lib.F32(b))) =>
      a.reinterpret_as_int() == b.reinterpret_as_int()
    (@lib.F64Const(@lib.F64(a)), @lib.F64Const(@lib.F64(b))) =>
      a.reinterpret_as_int64() == b.reinterpret_as_int64()
    (@lib.Block(a, @lib.Expr(xs)), @lib.Block(b, @lib.Expr(ys)))
    | (@lib.Loop(a, @lib.Expr(xs)), @lib.Loop(b, @lib.Expr(ys))) =>
      a == b && pass_const_instruction_vectors_bits_equal(xs, ys)
    (@lib.If(a, xs, x_else), @lib.If(b, ys, y_else)) => {
      if a != b || !pass_const_instruction_vectors_bits_equal(xs, ys) {
        return false
      }
      match (x_else, y_else) {
        (Some(xs), Some(ys)) =>
          pass_const_instruction_vectors_bits_equal(xs, ys)
        (None, None) => true
        _ => false
      }
    }
    (
      @lib.TryTable(a, catches, @lib.Expr(xs)),
      @lib.TryTable(b, other_catches, @lib.Expr(ys)),
    ) =>
      a == b &&
      catches == other_catches &&
      pass_const_instruction_vectors_bits_equal(xs, ys)
    (
      @lib.Try(a, @lib.Expr(xs), catches, delegate),
      @lib.Try(b, @lib.Expr(ys), other_catches, other_delegate),
    ) => {
      if a != b ||
        delegate != other_delegate ||
        catches.length() != other_catches.length() ||
        !pass_const_instruction_vectors_bits_equal(xs, ys) {
        return false
      }
      for i = 0; i < catches.length(); i = i + 1 {
        let equal = match (catches[i], other_catches[i]) {
          (
            @lib.LegacyCatch::LegacyCatch(tag, @lib.Expr(xs)),
            @lib.LegacyCatch::LegacyCatch(other_tag, @lib.Expr(ys)),
          ) =>
            tag == other_tag &&
            pass_const_instruction_vectors_bits_equal(xs, ys)
          (
            @lib.LegacyCatch::LegacyCatchAll(@lib.Expr(xs)),
            @lib.LegacyCatch::LegacyCatchAll(@lib.Expr(ys)),
          ) => pass_const_instruction_vectors_bits_equal(xs, ys)
          _ => false
        }
        if !equal {
          return false
        }
      }
      true
    }
    _ => lhs == rhs
  }
}

///|
fn pass_const_instruction_vectors_bits_equal(
  lhs : Array[@lib.Instruction],
  rhs : Array[@lib.Instruction],
) -> Bool {
  if lhs.length() != rhs.length() {
    return false
  }
  for i = 0; i < lhs.length(); i = i + 1 {
    if !pass_const_instruction_bits_equal(lhs[i], rhs[i]) {
      return false
    }
  }
  true
}

///|
// Global indices identify module slots, not necessarily distinct storage.
// JS imports of the same WebAssembly.Global share its [[Global]] address.
// https://webassembly.github.io/spec/js-api/#read-the-imports
fn globals_are_provably_disjoint(
  module_ctx : @ir.HotModuleContext?,
  lhs : Int32,
  rhs : Int32,
) -> Bool {
  if lhs == rhs || lhs < 0 || rhs < 0 {
    return false
  }
  let module_ctx = match module_ctx {
    Some(module_ctx) => module_ctx
    None => return false
  }
  let lhs = @lib.GlobalIdx::new(lhs.to_uint())
  let rhs = @lib.GlobalIdx::new(rhs.to_uint())
  if @ir.hot_module_resolve_global_type(module_ctx, lhs) is None ||
    @ir.hot_module_resolve_global_type(module_ctx, rhs) is None {
    return false
  }
  // Defined globals own fresh storage. Two imports can name the same host
  // global instance, regardless of their distinct indices or import names.
  @ir.hot_module_resolve_global_init(module_ctx, lhs) is Some(_) ||
  @ir.hot_module_resolve_global_init(module_ctx, rhs) is Some(_)
}

///|
// One node can be one tuple's several lanes. More lanes than its arity in the
// same entry prefix require another evaluation, which node-indexed rewrites
// cannot select separately. Reuse one sparse count row across controls.
fn pass_has_repeated_entry_evaluation(func : @ir.HotFunc) -> Bool {
  let mut counts : @hashmap.HashMap[@ir.NodeId, Int32]? = None
  let mut retained_width = 0
  for node_id in 0..<@ir.hot_node_count(func) {
    if !@ir.hot_node_is_live(func, node_id) {
      continue
    }
    let node = @ir.hot_node_get(func, node_id)
    let (start, count) = match node.op {
      @ir.HotOp::Block => (0, node.imm1)
      @ir.HotOp::Loop => (0, @ir.hot_label_branch_arity(func, node.imm0))
      @ir.HotOp::If => (3, node.child_count - 3)
      _ => (0, 0)
    }
    if count < 2 {
      continue
    }
    let row = match counts {
      Some(row) if count >= retained_width / 2 => {
        row.clear()
        row
      }
      _ => {
        // clear visits retained capacity. Drop a wide row before narrow
        // prefixes, so every clear remains bounded by this prefix's width.
        let row : @hashmap.HashMap[@ir.NodeId, Int32] = @hashmap.new(
          capacity=count,
        )
        counts = Some(row)
        retained_width = count
        row
      }
    }
    retained_width = retained_width.max(count)
    for slot in start..<(start + count) {
      let producer = @ir.hot_child_get(func, node_id, slot)
      let occurrences = row.get(producer).unwrap_or(0) + 1
      if occurrences > @ir.hot_node_result_arity(func, producer).max(1) {
        return true
      }
      row.set(producer, occurrences)
    }
  }
  false
}

///|
// Capture marks belong to the current region and its enclosing entries.
// Rewind removes branch/body marks while retaining incoming stack producers.
priv struct PassSourceCaptures {
  seen : Array[Bool]
  depths : Array[Int32]
  touched : Array[Int32]
}

///|
fn PassSourceCaptures::new(func : @ir.HotFunc) -> PassSourceCaptures {
  {
    seen: Array::make(@ir.hot_node_count(func), false),
    depths: Array::make(@ir.hot_node_count(func), -1),
    touched: [],
  }
}

///|
fn PassSourceCaptures::contains(
  self : PassSourceCaptures,
  node_id : Int32,
) -> Bool {
  node_id >= 0 && node_id < self.seen.length() && self.seen[node_id]
}

///|
fn PassSourceCaptures::mark(self : PassSourceCaptures, node_id : Int32) -> Unit {
  if node_id < 0 {
    return
  }
  while self.seen.length() <= node_id {
    self.seen.push(false)
    self.depths.push(-1)
  }
  if !self.seen[node_id] {
    self.seen[node_id] = true
    self.depths[node_id] = self.touched.length()
    self.touched.push(node_id)
  }
}

///|
fn PassSourceCaptures::rewind(self : PassSourceCaptures, depth : Int32) -> Unit {
  while self.touched.length() > depth {
    let node_id = self.touched.pop().unwrap()
    self.seen[node_id] = false
    self.depths[node_id] = -1
  }
}

///|
fn PassSourceCaptures::is_region_capture(
  self : PassSourceCaptures,
  node_id : Int32,
  depth : Int32,
) -> Bool {
  self.contains(node_id) && self.depths[node_id] >= depth
}