// Licensing scope: see ../../LICENSE and this directory's LICENSE and NOTICE.
// Copyright 2023 WebAssembly Community Group participants.
// Retained historical upstream notice; current derivation remains unconfirmed.
// Conservative attribution from pinned Binaryen version_130 counterpart:
// Copyright 2016 WebAssembly Community Group participants
// Counterpart: src/passes/CoalesceLocals.cpp (5d704ad5); origin remains unconfirmed.
// Potentially incorporated Binaryen expression retains Apache-2.0 terms.
// Original Starshine contributions use the scoped MIT grant in ../../LICENSE.
// Modified for Starshine through 2026: implementation and validation use
// Starshine's representations and APIs; this is not an unchanged upstream file.
// Conservative notice retention does not establish copying or independence.
///|
pub fn coalesce_locals_summary() -> String {
"Coalesce compatible same-typed body locals and remove redundant local copies."
}
///|
priv enum CLActionKind {
Get
Set
Tee
}
///|
priv enum CLValueSource {
Unique
Const(String)
Local(Int32)
}
///|
priv struct CLAction {
kind : CLActionKind
local_idx : Int32
source : CLValueSource
}
///|
priv struct CLLiveness {
effective : Array[Bool]
live_at_entry : Array[Bool]
}
///|
priv struct CLBitMatrix {
size : Int32
bits : @bitset.BitSet
row_offsets : Array[Int32]
}
///|
fn CLBitMatrix::new(size : Int32) -> CLBitMatrix {
let row_offsets = Array::make(size, 0)
let mut bit_count = 0
for row = 0; row < size; row = row + 1 {
row_offsets[row] = bit_count
bit_count += size - row - 1
}
{ size, bits: @bitset.BitSet::new(bit_count), row_offsets, }
}
///|
fn CLBitMatrix::length(self : CLBitMatrix) -> Int32 {
self.size
}
///|
fn cl_bit_matrix_index(
matrix : CLBitMatrix,
row : Int32,
column : Int32,
) -> Int32 {
if row == column {
return -1
}
let (lower, upper) = if row < column { (row, column) } else { (column, row) }
matrix.row_offsets[lower] + upper - lower - 1
}
///|
fn cl_bit_matrix_get(matrix : CLBitMatrix, row : Int32, column : Int32) -> Bool {
let index = cl_bit_matrix_index(matrix, row, column)
index >= 0 && matrix.bits[index]
}
///|
fn cl_bit_matrix_set(
matrix : CLBitMatrix,
row : Int32,
column : Int32,
value : Bool,
) -> Unit {
let index = cl_bit_matrix_index(matrix, row, column)
if index >= 0 {
matrix.bits[index] = value
}
}
///|
fn cl_bit_matrix_set_symmetric(
matrix : CLBitMatrix,
lhs : Int32,
rhs : Int32,
value : Bool,
) -> Unit {
cl_bit_matrix_set(matrix, lhs, rhs, value)
}
///|
priv struct CLCopyWeights {
rows : Array[Array[(Int32, Int32)]]
}
///|
fn CLCopyWeights::new(size : Int32) -> CLCopyWeights {
let rows : Array[Array[(Int32, Int32)]] = Array::new(capacity=size)
for _ in 0.. Int32 {
self.rows.length()
}
///|
fn cl_copy_weight_add_one(
weights : CLCopyWeights,
lhs : Int32,
rhs : Int32,
amount : Int32,
) -> Unit {
let row = weights.rows[lhs]
for edge_idx = 0; edge_idx < row.length(); edge_idx = edge_idx + 1 {
let (other, weight) = row[edge_idx]
if other == rhs {
row[edge_idx] = (other, weight + amount)
return
}
}
row.push((rhs, amount))
}
///|
fn cl_copy_weight_add(
weights : CLCopyWeights,
lhs : Int32,
rhs : Int32,
amount : Int32,
) -> Unit {
if lhs == rhs || amount == 0 {
return
}
cl_copy_weight_add_one(weights, lhs, rhs, amount)
cl_copy_weight_add_one(weights, rhs, lhs, amount)
}
///|
fn cl_copy_weight_get(
weights : CLCopyWeights,
lhs : Int32,
rhs : Int32,
) -> Int32 {
for edge in weights.rows[lhs] {
let (other, weight) = edge
if other == rhs {
return weight
}
}
0
}
///|
fn cl_copy_weight_degree(weights : CLCopyWeights, local_idx : Int32) -> Int32 {
let mut degree = 0
for edge in weights.rows[local_idx] {
let (_, weight) = edge
degree += weight
}
degree
}
///|
priv struct CLValueInterner {
ids : @hashmap.HashMap[String, Int32]
mut next_value : Int32
mut numeric_defaults : Array[Int32]?
}
///|
fn CLValueInterner::new() -> CLValueInterner {
{ ids: @hashmap.new(capacity=17), next_value: 0, numeric_defaults: None, }
}
///|
fn CLValueInterner::fresh(self : CLValueInterner) -> Int32 {
let value = self.next_value
self.next_value += 1
value
}
///|
fn CLValueInterner::intern(self : CLValueInterner, key : String) -> Int32 {
match self.ids.get(key) {
Some(value) => value
None => {
let value = self.fresh()
self.ids.set(key, value)
value
}
}
}
///|
priv struct CLColoring {
old_to_new : Array[Int32]
slot_types : Array[@lib.ValType]
removed_copies : Int32
}
///|
priv struct CLFuncRewrite {
func : @lib.Func
changed : Bool
}
///|
fn cl_imported_func_count(mod_ : @lib.Module) -> Int32 {
let mut count = 0
match mod_.import_sec {
Some(@lib.ImportSec(imports)) =>
for import_ in imports {
match import_ {
@lib.Import(_, _, @lib.FuncExternType(_)) => count += 1
_ => ()
}
}
None => ()
}
count
}
///|
fn cl_local_idx_raw(idx : @lib.LocalIdx) -> Int32 {
let @lib.LocalIdx(raw) = idx
raw.reinterpret_as_int()
}
///|
fn cl_local_idx_from_int(idx : Int32) -> @lib.LocalIdx {
@lib.LocalIdx::new(idx.reinterpret_as_uint())
}
///|
fn cl_label_idx_raw(idx : @lib.LabelIdx) -> Int32 {
let @lib.LabelIdx(raw) = idx
raw.reinterpret_as_int()
}
///|
fn cl_flatten_locals(
locals : @lib.Locals,
local_count : Int32,
) -> Array[@lib.ValType] {
let out : Array[@lib.ValType] = Array::new(capacity=local_count)
for run in locals.runs() {
let ty = run.val_type()
let run_len = run.count().reinterpret_as_int()
for _idx = 0; _idx < run_len; _idx = _idx + 1 {
out.push(ty)
}
}
out
}
///|
fn cl_all_local_types(
params : Array[@lib.ValType],
body_locals : @lib.Locals,
) -> Array[@lib.ValType] {
let body_count = body_locals.length()
let out : Array[@lib.ValType] = Array::new(
capacity=params.length() + body_count,
)
for param in params {
out.push(param)
}
for body_ty in cl_flatten_locals(body_locals, body_count) {
out.push(body_ty)
}
out
}
///|
fn cl_simple_const_source(instr : @lib.Instruction) -> CLValueSource? {
match instr {
@lib.I32Const(_)
| @lib.I64Const(_)
| @lib.F32Const(_)
| @lib.F64Const(_)
| @lib.RefNull(_)
| @lib.StringConst(_) => Some(CLValueSource::Const(@debug.to_string(instr)))
_ => None
}
}
///|
fn cl_value_source_before(
instrs : Array[@lib.Instruction],
idx : Int32,
) -> CLValueSource {
if idx <= 0 {
return CLValueSource::Unique
}
match instrs[idx - 1] {
@lib.LocalGet(local_idx) | @lib.LocalTee(local_idx) =>
CLValueSource::Local(cl_local_idx_raw(local_idx))
other =>
match cl_simple_const_source(other) {
Some(source) => source
None => CLValueSource::Unique
}
}
}
///|
fn cl_instr_is_branch_instruction(instr : @lib.Instruction) -> Bool {
match instr {
@lib.Br(_)
| @lib.BrIf(_)
| @lib.BrTable(_, _)
| @lib.BrOnNull(_)
| @lib.BrOnNonNull(_)
| @lib.BrOnCast(_, _, _, _)
| @lib.BrOnCastFail(_, _, _, _)
| @lib.BrOnCastDescEq(_, _, _)
| @lib.BrOnCastDescEqFail(_, _, _) => true
@lib.Resume(_, handlers)
| @lib.ResumeThrow(_, _, handlers)
| @lib.ResumeThrowRef(_, handlers) =>
handlers.any(fn(handler) { handler is @lib.ResumeOnLabel(_, _) })
_ => false
}
}
///|
fn cl_instr_is_terminal(instr : @lib.Instruction) -> Bool {
match instr {
@lib.Unreachable
| @lib.Return
| @lib.ReturnCall(_)
| @lib.ReturnCallIndirect(_, _)
| @lib.ReturnCallRef(_)
| @lib.Throw(_)
| @lib.ThrowRef
| @lib.Rethrow(_) => true
_ => false
}
}
///|
fn cl_instr_is_control_transfer_barrier(instr : @lib.Instruction) -> Bool {
if cl_instr_is_branch_instruction(instr) || cl_instr_is_terminal(instr) {
return true
}
match instr {
@lib.Suspend(_)
| @lib.Resume(_, _)
| @lib.ResumeThrow(_, _, _)
| @lib.ResumeThrowRef(_, _)
| @lib.StackSwitch(_, _) => true
_ => false
}
}
///|
// A scalar packs the no-fallthrough bit and the exclusive escape boundary.
// Sentinels sit outside every raw u32 label depth; shifting a finite boundary
// through a region cannot turn "no escape" into a terminal escape.
const CL_CONTROL_NO_ESCAPE : Int64 = -4294967296L
///|
const CL_CONTROL_TERMINAL_ESCAPE : Int64 = 4294967296L
///|
fn cl_control_pack(boundary : Int64, no_fallthrough : Bool) -> Int64 {
(boundary << 1) | (if no_fallthrough { 1L } else { 0L })
}
///|
fn cl_control_boundary(facts : Int64) -> Int64 {
facts >> 1
}
///|
fn cl_control_no_fallthrough(facts : Int64) -> Bool {
(facts & 1L) != 0L
}
///|
fn cl_control_shift_boundary(boundary : Int64) -> Int64 {
if boundary == CL_CONTROL_NO_ESCAPE || boundary == CL_CONTROL_TERMINAL_ESCAPE {
boundary
} else {
boundary - 1L
}
}
///|
fn cl_control_note_target(label : @lib.LabelIdx, frames : Array[Bool]) -> Unit {
let depth = cl_label_idx_raw(label)
if depth >= 0 && depth < frames.length() {
frames[frames.length() - depth - 1] = true
}
}
///|
fn cl_control_body_boundary(
body : Array[@lib.Instruction],
frames : Array[Bool],
instruction_visits : Array[Int32]?,
control_index~ : CLControlIndex? = None,
) -> Int64 {
let mut previous = cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
let mut last = previous
for child in body {
previous = last
last = cl_control_instruction(
child,
frames,
instruction_visits,
control_index~,
)
}
// A dead unreachable sentinel inherits its preceding transfer's boundary,
// rather than turning a branch to the current label into an escaping trap.
if body.length() > 1 &&
body[body.length() - 1] is @lib.Unreachable &&
cl_control_no_fallthrough(previous) {
cl_control_boundary(previous)
} else {
cl_control_boundary(last)
}
}
///|
priv struct CLControlIndex {
facts : Array[Int64]
ends : Array[Int32]
}
///|
fn CLControlIndex::new() -> CLControlIndex {
{ facts: [], ends: [], }
}
///|
fn cl_control_instruction(
instr : @lib.Instruction,
frames : Array[Bool],
instruction_visits : Array[Int32]?,
control_index~ : CLControlIndex? = None,
) -> Int64 {
match control_index {
None => cl_control_instruction_impl(instr, frames, instruction_visits, None)
Some(index) => {
let position = index.facts.length()
index.facts.push(0L)
index.ends.push(0)
let facts = cl_control_instruction_impl(
instr, frames, instruction_visits, control_index,
)
index.facts[position] = facts
index.ends[position] = index.facts.length()
facts
}
}
}
///|
fn cl_control_instruction_impl(
instr : @lib.Instruction,
frames : Array[Bool],
instruction_visits : Array[Int32]?,
control_index : CLControlIndex?,
) -> Int64 {
if instruction_visits is Some(visits) {
visits[0] += 1
}
if cl_instr_is_terminal(instr) {
return cl_control_pack(CL_CONTROL_TERMINAL_ESCAPE, true)
}
match instr {
@lib.Br(label) => {
cl_control_note_target(label, frames)
cl_control_pack(cl_label_idx_raw(label).to_int64(), true)
}
@lib.BrIf(label)
| @lib.BrOnNull(label)
| @lib.BrOnNonNull(label)
| @lib.BrOnCast(label, _, _, _)
| @lib.BrOnCastFail(label, _, _, _)
| @lib.BrOnCastDescEq(label, _, _)
| @lib.BrOnCastDescEqFail(label, _, _) => {
cl_control_note_target(label, frames)
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
}
@lib.BrTable(labels, default_label) => {
cl_control_note_target(default_label, frames)
let mut boundary = cl_label_idx_raw(default_label).to_int64()
for label in labels {
cl_control_note_target(label, frames)
let depth = cl_label_idx_raw(label).to_int64()
if depth < boundary {
boundary = depth
}
}
cl_control_pack(boundary, true)
}
@lib.Block(_, @lib.Expr(body)) => {
frames.push(false)
let boundary = cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
let self_target = frames.pop().unwrap()
if self_target {
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
} else {
cl_control_pack(cl_control_shift_boundary(boundary), boundary > 0L)
}
}
@lib.If(_, yes, no) => {
frames.push(false)
let yes_boundary = cl_control_body_boundary(
yes,
frames,
instruction_visits,
control_index~,
)
let no_boundary = match no {
Some(body) =>
cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
None => CL_CONTROL_NO_ESCAPE
}
let self_target = frames.pop().unwrap()
let boundary = if yes_boundary < no_boundary {
yes_boundary
} else {
no_boundary
}
if self_target {
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
} else {
cl_control_pack(cl_control_shift_boundary(boundary), boundary > 0L)
}
}
@lib.TryTable(_, catches, @lib.Expr(body)) => {
// Catch labels address the surrounding context, before the try body's
// label is pushed, exactly like the existing branch-target query.
for catch_ in catches {
let label = match catch_ {
@lib.Catch(_, label)
| @lib.CatchRef(_, label)
| @lib.CatchAll(label)
| @lib.CatchAllRef(label) => label
}
cl_control_note_target(label, frames)
}
frames.push(false)
let boundary = cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
let self_target = frames.pop().unwrap()
if self_target {
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
} else {
cl_control_pack(cl_control_shift_boundary(boundary), boundary > 0L)
}
}
@lib.Loop(_, @lib.Expr(body)) => {
frames.push(false)
let _ = cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
let _ = frames.pop()
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
frames.push(false)
let _ = cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
for catch_ in catches {
let @lib.Expr(body) = match catch_ {
@lib.LegacyCatch(_, body) | @lib.LegacyCatchAll(body) => body
}
let _ = cl_control_body_boundary(
body,
frames,
instruction_visits,
control_index~,
)
}
let _ = frames.pop()
cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
}
_ => cl_control_pack(CL_CONTROL_NO_ESCAPE, false)
}
}
///|
fn cl_control_index_budget(
body : Array[@lib.Instruction],
budget : Int32,
visits : Array[Int32]?,
) -> Int32 {
let mut remaining = budget
for instr in body {
if visits is Some(count) {
count[0] += 1
}
remaining -= 1
if remaining <= 0 {
return 0
}
match instr {
@lib.Block(_, @lib.Expr(child))
| @lib.Loop(_, @lib.Expr(child))
| @lib.TryTable(_, _, @lib.Expr(child)) =>
remaining = cl_control_index_budget(child, remaining, visits)
@lib.If(_, yes, no) => {
remaining = cl_control_index_budget(yes, remaining, visits)
if remaining <= 0 {
return 0
}
if no is Some(child) {
remaining = cl_control_index_budget(child, remaining, visits)
}
}
@lib.Try(_, @lib.Expr(child), catches, _) => {
remaining = cl_control_index_budget(child, remaining, visits)
for catch_ in catches {
if remaining <= 0 {
return 0
}
let @lib.Expr(child) = match catch_ {
@lib.LegacyCatch(_, child) | @lib.LegacyCatchAll(child) => child
}
remaining = cl_control_index_budget(child, remaining, visits)
}
}
_ => ()
}
if remaining <= 0 {
return 0
}
}
remaining
}
///|
fn cl_control_index_for_body(
body : Array[@lib.Instruction],
visits : Array[Int32]?,
) -> CLControlIndex? {
if !body.any(fn(instr) {
if visits is Some(count) {
count[0] += 1
}
instr is @lib.Block(_, _) ||
instr is @lib.Loop(_, _) ||
instr is @lib.If(_, _, _) ||
instr is @lib.Try(_, _, _, _) ||
instr is @lib.TryTable(_, _, _)
}) {
return None
}
if cl_control_index_budget(body, 16, visits) > 0 {
return None
}
let index = CLControlIndex::new()
let _ = cl_control_body_boundary(body, [], visits, control_index=Some(index))
Some(index)
}
///|
fn cl_instr_escapes_past_depth(
instr : @lib.Instruction,
boundary_depth : Int32,
) -> Bool {
cl_control_boundary(cl_control_instruction(instr, [], None)) >
boundary_depth.to_int64()
}
///|
fn cl_instrs_end_in_escape_past_depth(
instrs : Array[@lib.Instruction],
boundary_depth : Int32,
) -> Bool {
if instrs.is_empty() {
return false
}
let last = instrs.length() - 1
if last > 0 && instrs[last] is @lib.Unreachable {
let previous = cl_control_instruction(instrs[last - 1], [], None)
if cl_control_boundary(previous) > boundary_depth.to_int64() {
return true
}
if cl_control_no_fallthrough(previous) {
return false
}
}
cl_instr_escapes_past_depth(instrs[last], boundary_depth)
}
///|
fn cl_instr_never_falls_through(
instr : @lib.Instruction,
instruction_visits~ : Array[Int32]? = None,
) -> Bool {
// Keep ordinary leaves allocation-free; the frame stack belongs only to a
// structured query, never to the mutable raw instruction tree.
match instr {
@lib.Block(_, _) | @lib.If(_, _, Some(_)) | @lib.TryTable(_, _, _) =>
cl_control_no_fallthrough(
cl_control_instruction(instr, [], instruction_visits),
)
_ => {
if instruction_visits is Some(visits) {
visits[0] += 1
}
cl_instr_is_terminal(instr) ||
instr is @lib.Br(_) ||
instr is @lib.BrTable(_, _)
}
}
}
///|
fn cl_instr_makes_rest_unreachable(instr : @lib.Instruction) -> Bool {
cl_instr_never_falls_through(instr)
}
///|
fn cl_reachable_prefix_len(
instrs : Array[@lib.Instruction],
instruction_visits~ : Array[Int32]? = None,
) -> Int32 {
for idx = 0; idx < instrs.length(); idx = idx + 1 {
if cl_instr_never_falls_through(instrs[idx], instruction_visits~) {
return idx + 1
}
}
instrs.length()
}
///|
fn cl_dense_coloring_local_limit() -> Int32 {
// Dense interference and copy-weight tables are O(locals^2). Keep the
// current Binaryen-compatible dense coloring path bounded until coalesce-
// locals has a sparse interference representation for huge functions.
4096
}
///|
fn cl_instrs_have_structured_control(instrs : Array[@lib.Instruction]) -> Bool {
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) => {
ignore(body)
return true
}
@lib.If(_, _, _) | @lib.Try(_, _, _, _) => return true
@lib.Br(_) | @lib.BrIf(_) | @lib.BrTable(_, _) | @lib.Return =>
return true
_ => ()
}
}
false
}
///|
fn cl_instrs_have_loop_control(instrs : Array[@lib.Instruction]) -> Bool {
for instr in instrs {
match instr {
@lib.Loop(_, _) => return true
@lib.Block(_, @lib.Expr(body)) | @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_have_loop_control(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_loop_control(then_body) {
return true
}
match else_body {
Some(body) => if cl_instrs_have_loop_control(body) { return true }
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_mark_syntactic_local_accesses(
instrs : Array[@lib.Instruction],
accessed : Array[Bool],
read : Array[Bool],
) -> Unit {
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_mark_syntactic_local_accesses(body, accessed, read)
@lib.Try(_, @lib.Expr(body), catches, _) => {
cl_mark_syntactic_local_accesses(body, accessed, read)
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
cl_mark_syntactic_local_accesses(catch_body, accessed, read)
}
}
}
@lib.If(_, then_body, else_body) => {
cl_mark_syntactic_local_accesses(then_body, accessed, read)
match else_body {
Some(body) => cl_mark_syntactic_local_accesses(body, accessed, read)
None => ()
}
}
@lib.LocalGet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < accessed.length() {
accessed[raw] = true
read[raw] = true
}
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < accessed.length() {
accessed[raw] = true
}
}
_ => ()
}
}
}
///|
fn cl_count_syntactic_local_accesses(
instrs : Array[@lib.Instruction],
gets : Array[Int32],
sets : Array[Int32],
tees : Array[Int32],
) -> Unit {
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_count_syntactic_local_accesses(body, gets, sets, tees)
@lib.Try(_, @lib.Expr(body), catches, _) => {
cl_count_syntactic_local_accesses(body, gets, sets, tees)
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
cl_count_syntactic_local_accesses(catch_body, gets, sets, tees)
}
}
}
@lib.If(_, then_body, else_body) => {
cl_count_syntactic_local_accesses(then_body, gets, sets, tees)
match else_body {
Some(body) =>
cl_count_syntactic_local_accesses(body, gets, sets, tees)
None => ()
}
}
@lib.LocalGet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < gets.length() {
gets[raw] += 1
}
}
@lib.LocalSet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < sets.length() {
sets[raw] += 1
}
}
@lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < tees.length() {
tees[raw] += 1
}
}
_ => ()
}
}
}
///|
fn cl_instr_blocks_loop_copy_through(instr : @lib.Instruction) -> Bool {
match instr {
@lib.Block(_, _)
| @lib.Loop(_, _)
| @lib.If(_, _, _)
| @lib.Try(_, _, _, _)
| @lib.TryTable(_, _, _) => true
_ => cl_instr_is_control_transfer_barrier(instr)
}
}
///|
test "coalesce-locals copy-through barriers include every GC branch family" {
let label = @lib.LabelIdx::new(0U)
let any = @lib.HeapType::abs(@lib.AbsHeapType::any())
let eq = @lib.HeapType::abs(@lib.AbsHeapType::eq())
let nullable_any = @lib.RefType::new(true, any)
let nullable_eq = @lib.RefType::new(true, eq)
for
instr in [
@lib.Instruction::br_on_null(label),
@lib.Instruction::br_on_non_null(label),
@lib.Instruction::br_on_cast(label, true, any, true, eq),
@lib.Instruction::br_on_cast_fail(label, true, any, true, eq),
@lib.Instruction::br_on_cast_desc_eq(label, nullable_any, nullable_eq),
@lib.Instruction::br_on_cast_desc_eq_fail(
label, nullable_any, nullable_eq,
),
] {
assert_true(
cl_instr_blocks_loop_copy_through(instr),
msg="expected GC branch barrier for \{@debug.to_string(instr)}",
)
}
}
///|
fn cl_loop_copy_through_dest_after_set(
instrs : Array[@lib.Instruction],
set_idx : Int32,
temp : Int32,
types : Array[@lib.ValType],
param_count : Int32,
inside_try_table : Bool,
) -> Int32 {
if temp < param_count || temp >= types.length() {
return -1
}
let mut idx = set_idx + 1
while idx < instrs.length() {
let instr = instrs[idx]
match instr {
@lib.LocalGet(read_idx) if cl_local_idx_raw(read_idx) == temp => {
if idx + 1 >= instrs.length() {
return -1
}
match instrs[idx + 1] {
@lib.LocalSet(dest_idx) => {
let dest = cl_local_idx_raw(dest_idx)
if dest < 0 ||
dest >= types.length() ||
dest == temp ||
types[temp] != types[dest] {
return -1
}
for between = set_idx + 1; between < idx; between = between + 1 {
if cl_instr_accesses_local(instrs[between], dest) {
return -1
}
}
return dest
}
_ => return -1
}
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) if cl_local_idx_raw(
local_idx,
) ==
temp => return -1
@lib.Call(_) | @lib.CallIndirect(_, _) | @lib.CallRef(_) if inside_try_table =>
return -1
_ => if cl_instr_blocks_loop_copy_through(instr) { return -1 }
}
idx += 1
}
-1
}
///|
fn cl_mark_loop_adjacent_copy_through_locals(
instrs : Array[@lib.Instruction],
passthrough_dest : Array[Int32],
gets : Array[Int32],
sets : Array[Int32],
tees : Array[Int32],
types : Array[@lib.ValType],
param_count : Int32,
inside_try_table : Bool,
) -> Unit {
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
cl_mark_loop_adjacent_copy_through_locals(
body, passthrough_dest, gets, sets, tees, types, param_count, inside_try_table,
)
@lib.TryTable(_, _, @lib.Expr(body)) =>
cl_mark_loop_adjacent_copy_through_locals(
body, passthrough_dest, gets, sets, tees, types, param_count, true,
)
@lib.If(_, then_body, else_body) => {
cl_mark_loop_adjacent_copy_through_locals(
then_body, passthrough_dest, gets, sets, tees, types, param_count, inside_try_table,
)
match else_body {
Some(body) =>
cl_mark_loop_adjacent_copy_through_locals(
body, passthrough_dest, gets, sets, tees, types, param_count, inside_try_table,
)
None => ()
}
}
_ => ()
}
}
for idx = 0; idx < instrs.length(); idx = idx + 1 {
match instrs[idx] {
@lib.LocalSet(temp_idx) => {
let temp = cl_local_idx_raw(temp_idx)
if temp >= param_count &&
temp < types.length() &&
gets[temp] == 1 &&
sets[temp] == 1 &&
tees[temp] == 0 {
let dest = cl_loop_copy_through_dest_after_set(
instrs, idx, temp, types, param_count, inside_try_table,
)
if dest >= 0 {
passthrough_dest[temp] = dest
}
}
}
_ => ()
}
}
}
///|
fn cl_instr_tree_has_control_transfer(instr : @lib.Instruction) -> Bool {
if cl_instr_is_control_transfer_barrier(instr) {
return true
}
match instr {
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
body.any(cl_instr_tree_has_control_transfer)
@lib.If(_, then_body, else_body) => {
if then_body.any(cl_instr_tree_has_control_transfer) {
return true
}
match else_body {
Some(body) => body.any(cl_instr_tree_has_control_transfer)
None => false
}
}
@lib.Try(_, _, _, _) | @lib.TryTable(_, _, _) => true
_ => false
}
}
///|
fn cl_label_targets_depth(label_idx : @lib.LabelIdx, depth : Int32) -> Bool {
cl_label_idx_raw(label_idx) == depth
}
///|
fn cl_instr_tree_branches_to_depth(
instr : @lib.Instruction,
depth : Int32,
) -> Bool {
match instr {
@lib.Br(label_idx)
| @lib.BrIf(label_idx)
| @lib.BrOnNull(label_idx)
| @lib.BrOnNonNull(label_idx) => cl_label_targets_depth(label_idx, depth)
@lib.BrOnCast(label_idx, _, _, _)
| @lib.BrOnCastFail(label_idx, _, _, _)
| @lib.BrOnCastDescEq(label_idx, _, _)
| @lib.BrOnCastDescEqFail(label_idx, _, _) =>
cl_label_targets_depth(label_idx, depth)
@lib.BrTable(labels, default_label) => {
if cl_label_targets_depth(default_label, depth) {
return true
}
labels.any(fn(label_idx) { cl_label_targets_depth(label_idx, depth) })
}
@lib.TryTable(_, catches, @lib.Expr(body)) => {
for catch_ in catches {
let label = match catch_ {
@lib.Catch(_, label)
| @lib.CatchRef(_, label)
| @lib.CatchAll(label)
| @lib.CatchAllRef(label) => label
}
if cl_label_targets_depth(label, depth) {
return true
}
}
body.any(fn(child) { cl_instr_tree_branches_to_depth(child, depth + 1) })
}
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
body.any(fn(child) { cl_instr_tree_branches_to_depth(child, depth + 1) })
@lib.If(_, then_body, else_body) => {
if then_body.any(fn(child) {
cl_instr_tree_branches_to_depth(child, depth + 1)
}) {
return true
}
match else_body {
Some(body) =>
body.any(fn(child) {
cl_instr_tree_branches_to_depth(child, depth + 1)
})
None => false
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
if body.any(fn(child) {
cl_instr_tree_branches_to_depth(child, depth + 1)
}) {
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 catch_body.any(fn(child) {
cl_instr_tree_branches_to_depth(child, depth + 1)
}) {
return true
}
}
false
}
_ => false
}
}
///|
fn cl_instr_tree_get_count(
instr : @lib.Instruction,
local_idx : Int32,
) -> Int32 {
match instr {
@lib.LocalGet(idx) => if cl_local_idx_raw(idx) == local_idx { 1 } else { 0 }
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) => {
let mut count = 0
for child in body {
count += cl_instr_tree_get_count(child, local_idx)
}
count
}
@lib.If(_, then_body, else_body) => {
let mut count = 0
for child in then_body {
count += cl_instr_tree_get_count(child, local_idx)
}
match else_body {
Some(body) =>
for child in body {
count += cl_instr_tree_get_count(child, local_idx)
}
None => ()
}
count
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
let mut count = 0
for child in body {
count += cl_instr_tree_get_count(child, local_idx)
}
for catch_ in catches {
let catch_body = match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
}
for child in catch_body {
count += cl_instr_tree_get_count(child, local_idx)
}
}
count
}
_ => 0
}
}
///|
fn cl_mark_loop_backedge_copy_aliases(
instrs : Array[@lib.Instruction],
passthrough_dest : Array[Int32],
gets : Array[Int32],
types : Array[@lib.ValType],
param_count : Int32,
) -> Unit {
for instr in instrs {
match instr {
@lib.Loop(_, @lib.Expr(body)) => {
if body.length() >= 3 {
let tail = body.length() - 3
match (body[tail], body[tail + 1], body[tail + 2]) {
(
@lib.LocalGet(source_idx),
@lib.LocalSet(dest_idx),
@lib.Br(label_idx),
) => {
let source = cl_local_idx_raw(source_idx)
let dest = cl_local_idx_raw(dest_idx)
if cl_label_idx_raw(label_idx) == 0 &&
source >= param_count &&
source < types.length() &&
dest >= param_count &&
dest < types.length() &&
source != dest &&
types[source] == types[dest] &&
passthrough_dest[dest] < 0 {
let mut source_write = -1
for idx = 0; idx < tail; idx = idx + 1 {
match body[idx] {
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) =>
if source_write < 0 &&
cl_local_idx_raw(local_idx) == source {
source_write = idx
}
_ => ()
}
}
if source_write >= 0 {
let mut safe = true
let mut has_control_transfer = false
let mut has_bypass_backedge = false
let mut loop_dest_gets = 0
for idx = 0; idx < tail; idx = idx + 1 {
if cl_instr_tree_has_control_transfer(body[idx]) {
has_control_transfer = true
}
if cl_instr_tree_branches_to_depth(body[idx], 0) {
has_bypass_backedge = true
}
loop_dest_gets += cl_instr_tree_get_count(body[idx], dest)
}
for idx = 0; idx < source_write; idx = idx + 1 {
if cl_instr_tree_accesses_local(body[idx], source) {
safe = false
}
}
for idx = source_write + 1; idx < tail; idx = idx + 1 {
if cl_instr_tree_accesses_local(body[idx], dest) {
safe = false
}
}
// Every earlier edge back to this loop skips the final copy.
// Other exits are safe only when all destination reads stay
// inside this loop; otherwise an outer continuation or
// exceptional handler can observe the skipped old value.
if gets[dest] > 0 &&
(
has_bypass_backedge ||
(has_control_transfer && gets[dest] > loop_dest_gets)
) {
safe = false
}
if safe {
// Delay the earlier destination's slot assignment until
// the backedge source has been assigned. Both then reuse
// the source slot and the tail copy becomes a nop.
passthrough_dest[dest] = source
}
}
}
}
_ => ()
}
}
cl_mark_loop_backedge_copy_aliases(
body, passthrough_dest, gets, types, param_count,
)
}
@lib.Block(_, @lib.Expr(body)) | @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_mark_loop_backedge_copy_aliases(
body, passthrough_dest, gets, types, param_count,
)
@lib.If(_, then_body, else_body) => {
cl_mark_loop_backedge_copy_aliases(
then_body, passthrough_dest, gets, types, param_count,
)
match else_body {
Some(body) =>
cl_mark_loop_backedge_copy_aliases(
body, passthrough_dest, gets, types, param_count,
)
None => ()
}
}
_ => ()
}
}
}
///|
fn cl_instrs_write_local(
instrs : Array[@lib.Instruction],
target : Int32,
) -> Bool {
for instr in instrs {
match instr {
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) =>
if cl_local_idx_raw(local_idx) == target {
return true
}
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_write_local(body, target) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_write_local(then_body, target) {
return true
}
match else_body {
Some(body) => if cl_instrs_write_local(body, target) { return true }
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
if cl_instrs_write_local(body, target) {
return true
}
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
if cl_instrs_write_local(catch_body, target) {
return true
}
}
}
}
_ => ()
}
}
false
}
///|
fn cl_instrs_suffix_writes_local(
instrs : Array[@lib.Instruction],
start : Int32,
target : Int32,
suffix_queries~ : Array[Int32]? = None,
) -> Bool {
match suffix_queries {
Some(queries) => queries[0] += 1
None => ()
}
for idx = start; idx < instrs.length(); idx = idx + 1 {
if cl_instrs_write_local([instrs[idx]], target) {
return true
}
}
false
}
///|
fn cl_mark_loop_prefix_copy_aliases(
instrs : Array[@lib.Instruction],
alias_source : Array[Int32],
sets : Array[Int32],
tees : Array[Int32],
types : Array[@lib.ValType],
suffix_queries~ : Array[Int32]? = None,
) -> Unit {
let seen = Array::make(types.length(), false)
let mut idx = 0
while idx < instrs.length() {
match instrs[idx] {
@lib.Block(_, _)
| @lib.Loop(_, _)
| @lib.If(_, _, _)
| @lib.Try(_, _, _, _)
| @lib.TryTable(_, _, _)
| @lib.Br(_)
| @lib.BrIf(_)
| @lib.BrTable(_, _) => return
@lib.LocalGet(source_idx) if idx + 1 < instrs.length() => {
let source = cl_local_idx_raw(source_idx)
match instrs[idx + 1] {
@lib.LocalSet(dest_idx) => {
let dest = cl_local_idx_raw(dest_idx)
if source >= 0 &&
source < types.length() &&
dest >= 0 &&
dest < types.length() &&
source != dest &&
!seen[dest] &&
types[source] == types[dest] &&
sets[dest] == 1 &&
tees[dest] == 0 &&
// Counts cover the whole unchanged body, including handlers.
// An immutable source cannot have a later overwrite; retain the
// exact suffix query for every source with any set or tee.
(
(sets[source] == 0 && tees[source] == 0) ||
!cl_instrs_suffix_writes_local(
instrs,
idx + 2,
source,
suffix_queries~,
)
) {
alias_source[dest] = source
}
if source >= 0 && source < seen.length() {
seen[source] = true
}
if dest >= 0 && dest < seen.length() {
seen[dest] = true
}
idx += 1
}
_ => if source >= 0 && source < seen.length() { seen[source] = true }
}
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < seen.length() {
seen[raw] = true
}
}
_ => ()
}
idx += 1
}
}
///|
fn cl_resolve_loop_alias_source(
local_idx : Int32,
alias_source : Array[Int32],
) -> Int32 {
let mut current = local_idx
let mut steps = 0
while current >= 0 &&
current < alias_source.length() &&
alias_source[current] >= 0 &&
steps < alias_source.length() {
let next = alias_source[current]
if next == current {
return local_idx
}
current = next
steps += 1
}
if steps >= alias_source.length() {
local_idx
} else {
current
}
}
///|
fn cl_resolve_loop_passthrough_dest(
local_idx : Int32,
passthrough_dest : Array[Int32],
) -> Int32 {
let mut current = local_idx
let mut steps = 0
while current >= 0 &&
current < passthrough_dest.length() &&
passthrough_dest[current] >= 0 &&
steps < passthrough_dest.length() {
let next = passthrough_dest[current]
if next == current {
return local_idx
}
current = next
steps += 1
}
if steps >= passthrough_dest.length() {
return local_idx
}
current
}
///|
fn cl_rewrite_loop_func_unused_locals(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, body) = func
let types = cl_all_local_types(params, body_locals)
let total_locals = types.length()
let @lib.Expr(original_instrs) = body
let accessed = Array::make(total_locals, false)
let read = Array::make(total_locals, false)
let gets = Array::make(total_locals, 0)
let sets = Array::make(total_locals, 0)
let tees = Array::make(total_locals, 0)
let passthrough_dest = Array::make(total_locals, -1)
let alias_source = Array::make(total_locals, -1)
cl_mark_syntactic_local_accesses(original_instrs, accessed, read)
cl_count_syntactic_local_accesses(original_instrs, gets, sets, tees)
cl_mark_loop_prefix_copy_aliases(
original_instrs, alias_source, sets, tees, types,
)
cl_mark_loop_adjacent_copy_through_locals(
original_instrs,
passthrough_dest,
gets,
sets,
tees,
types,
params.length(),
false,
)
cl_mark_loop_backedge_copy_aliases(
original_instrs,
passthrough_dest,
gets,
types,
params.length(),
)
let old_to_new = Array::make(total_locals, -1)
let slot_types : Array[@lib.ValType] = []
for idx = 0; idx < params.length(); idx = idx + 1 {
old_to_new[idx] = idx
slot_types.push(types[idx])
}
let mut changed = false
for idx = params.length(); idx < total_locals; idx = idx + 1 {
let ty = types[idx]
let source_alias = cl_resolve_loop_alias_source(idx, alias_source)
let passthrough = cl_resolve_loop_passthrough_dest(idx, passthrough_dest)
if source_alias != idx &&
types[source_alias] == ty &&
old_to_new[source_alias] >= 0 {
old_to_new[idx] = old_to_new[source_alias]
changed = true
} else if passthrough != idx && types[passthrough] == ty {
continue
} else if read[idx] {
let next_idx = slot_types.length()
old_to_new[idx] = next_idx
slot_types.push(ty)
if next_idx != idx {
changed = true
}
} else if accessed[idx] {
// Loop/backedge liveness is intentionally conservative, but a local that
// is written and never read from the local slot cannot carry a loop value.
// Keep those dead writes away from params and read locals, while allowing
// same-typed dead-write locals to share one scratch slot.
let mut slot = -1
for prior = params.length(); prior < idx; prior = prior + 1 {
if accessed[prior] && !read[prior] && types[prior] == ty {
slot = old_to_new[prior]
break
}
}
if slot < 0 {
slot = slot_types.length()
slot_types.push(ty)
}
old_to_new[idx] = slot
if slot != idx {
changed = true
}
} else {
let mut slot = -1
for candidate = 0
candidate < slot_types.length()
candidate = candidate + 1 {
if slot_types[candidate] == ty {
slot = candidate
break
}
}
if slot < 0 {
slot = slot_types.length()
slot_types.push(ty)
}
old_to_new[idx] = slot
if slot != idx {
changed = true
}
}
}
for idx = params.length(); idx < total_locals; idx = idx + 1 {
if old_to_new[idx] >= 0 {
continue
}
let passthrough = cl_resolve_loop_passthrough_dest(idx, passthrough_dest)
if passthrough != idx &&
types[passthrough] == types[idx] &&
old_to_new[passthrough] >= 0 {
// Adjacent `local.set tmp; local.get tmp; local.set dest` copy-through
// chains do not carry values across loop backedges. Reusing the final
// destination slot only moves the overwrite earlier by the immediately
// following `local.get tmp`, and redundant self-copy cleanup removes the
// resulting no-op pairs.
old_to_new[idx] = old_to_new[passthrough]
changed = true
} else {
let next_idx = slot_types.length()
old_to_new[idx] = next_idx
slot_types.push(types[idx])
if next_idx != idx {
changed = true
}
}
}
let body_slot_types : Array[@lib.ValType] = []
for slot = params.length(); slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let rewritten_locals = @lib.Locals::from_types(body_slot_types)
let rewritten_instrs = cl_deep_copy_instrs(original_instrs)
cl_rewrite_all_local_idxs_in_place(rewritten_instrs, old_to_new)
let flattened_control = cl_flatten_terminal_unbranched_void_blocks(
rewritten_instrs,
)
let rewritten_gets = Array::make(
params.length() + body_slot_types.length(),
0,
)
let rewritten_sets = Array::make(rewritten_gets.length(), 0)
let rewritten_tees = Array::make(rewritten_gets.length(), 0)
cl_count_syntactic_local_accesses(
rewritten_instrs, rewritten_gets, rewritten_sets, rewritten_tees,
)
let unread_tee_changed = cl_remove_unread_local_tees(
rewritten_instrs, rewritten_gets,
)
let cleanup_changed = cl_remove_redundant_copy_pairs(rewritten_instrs)
let did_change = changed ||
flattened_control ||
unread_tee_changed ||
cleanup_changed
if !did_change && rewritten_locals == body_locals {
{ func, changed: false, }
} else {
{
func: @lib.Func::new(rewritten_locals, @lib.Expr::new(rewritten_instrs)),
changed: true,
}
}
}
///|
fn cl_rewrite_all_local_idxs_in_place(
instrs : Array[@lib.Instruction],
old_to_new : Array[Int32],
) -> Unit {
for idx = 0; idx < instrs.length(); idx = idx + 1 {
match instrs[idx] {
@lib.Block(block_type, @lib.Expr(body)) => {
cl_rewrite_all_local_idxs_in_place(body, old_to_new)
instrs[idx] = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
cl_rewrite_all_local_idxs_in_place(body, old_to_new)
instrs[idx] = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
cl_rewrite_all_local_idxs_in_place(then_body, old_to_new)
match else_body {
Some(else_instrs) =>
cl_rewrite_all_local_idxs_in_place(else_instrs, old_to_new)
None => ()
}
instrs[idx] = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.Try(block_type, @lib.Expr(body), catches, delegate) => {
cl_rewrite_all_local_idxs_in_place(body, old_to_new)
let rewritten_catches : Array[@lib.LegacyCatch] = []
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(tag_idx, @lib.Expr(catch_body)) => {
cl_rewrite_all_local_idxs_in_place(catch_body, old_to_new)
rewritten_catches.push(
@lib.LegacyCatch::tagged(tag_idx, @lib.Expr::new(catch_body)),
)
}
@lib.LegacyCatchAll(@lib.Expr(catch_body)) => {
cl_rewrite_all_local_idxs_in_place(catch_body, old_to_new)
rewritten_catches.push(
@lib.LegacyCatch::all(@lib.Expr::new(catch_body)),
)
}
}
}
instrs[idx] = @lib.Instruction::try_(
block_type,
@lib.Expr::new(body),
rewritten_catches,
delegate~,
)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
cl_rewrite_all_local_idxs_in_place(body, old_to_new)
instrs[idx] = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
@lib.LocalGet(local_idx) =>
instrs[idx] = @lib.Instruction::local_get(
cl_rewrite_local_idx(local_idx, old_to_new),
)
@lib.LocalSet(local_idx) =>
instrs[idx] = @lib.Instruction::local_set(
cl_rewrite_local_idx(local_idx, old_to_new),
)
@lib.LocalTee(local_idx) =>
instrs[idx] = @lib.Instruction::local_tee(
cl_rewrite_local_idx(local_idx, old_to_new),
)
_ => ()
}
}
}
///|
fn cl_remove_unread_local_tees(
instrs : Array[@lib.Instruction],
gets : Array[Int32],
) -> Bool {
let out : Array[@lib.Instruction] = []
let mut changed = false
let mut idx = 0
while idx < instrs.length() {
let instr = instrs[idx]
let mut rewritten = instr
match instr {
@lib.Block(block_type, @lib.Expr(body)) => {
changed = cl_remove_unread_local_tees(body, gets) || changed
rewritten = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
changed = cl_remove_unread_local_tees(body, gets) || changed
rewritten = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
changed = cl_remove_unread_local_tees(then_body, gets) || changed
match else_body {
Some(body) =>
changed = cl_remove_unread_local_tees(body, gets) || changed
None => ()
}
rewritten = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.Try(block_type, @lib.Expr(body), catches, delegate) => {
changed = cl_remove_unread_local_tees(body, gets) || changed
let rewritten_catches : Array[@lib.LegacyCatch] = []
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(tag_idx, @lib.Expr(catch_body)) => {
changed = cl_remove_unread_local_tees(catch_body, gets) || changed
rewritten_catches.push(
@lib.LegacyCatch::tagged(tag_idx, @lib.Expr::new(catch_body)),
)
}
@lib.LegacyCatchAll(@lib.Expr(catch_body)) => {
changed = cl_remove_unread_local_tees(catch_body, gets) || changed
rewritten_catches.push(
@lib.LegacyCatch::all(@lib.Expr::new(catch_body)),
)
}
}
}
rewritten = @lib.Instruction::try_(
block_type,
@lib.Expr::new(body),
rewritten_catches,
delegate~,
)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
changed = cl_remove_unread_local_tees(body, gets) || changed
rewritten = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
@lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < gets.length() && gets[raw] == 0 {
changed = true
idx += 1
continue
}
}
_ => ()
}
out.push(rewritten)
idx += 1
}
if changed {
instrs.clear()
instrs.append(out)
}
changed
}
///|
fn cl_deep_copy_instrs(
instrs : Array[@lib.Instruction],
) -> Array[@lib.Instruction] {
let out : Array[@lib.Instruction] = []
for instr in instrs {
out.push(
match instr {
@lib.Block(block_type, @lib.Expr(body)) =>
@lib.Instruction::block(
block_type,
@lib.Expr::new(cl_deep_copy_instrs(body)),
)
@lib.Loop(block_type, @lib.Expr(body)) =>
@lib.Instruction::loop_(
block_type,
@lib.Expr::new(cl_deep_copy_instrs(body)),
)
@lib.If(block_type, then_body, else_body) =>
@lib.Instruction::if_(
block_type,
cl_deep_copy_instrs(then_body),
match else_body {
Some(body) => Some(cl_deep_copy_instrs(body))
None => None
},
)
@lib.Try(block_type, @lib.Expr(body), catches, delegate) =>
@lib.Instruction::try_(
block_type,
@lib.Expr::new(cl_deep_copy_instrs(body)),
catches.map(fn(catch_) {
match catch_ {
@lib.LegacyCatch(tag, @lib.Expr(body)) =>
@lib.LegacyCatch::tagged(
tag,
@lib.Expr::new(cl_deep_copy_instrs(body)),
)
@lib.LegacyCatchAll(@lib.Expr(body)) =>
@lib.LegacyCatch::all(
@lib.Expr::new(cl_deep_copy_instrs(body)),
)
}
}),
delegate~,
)
@lib.TryTable(block_type, catches, @lib.Expr(body)) =>
@lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(cl_deep_copy_instrs(body)),
)
other => other
},
)
}
out
}
///|
priv struct CLControlSummary {
branch_depths : Array[Int32]
max_escape_boundary : Int32
never_falls_through : Bool
}
///|
fn cl_control_add_branch_depth(depths : Array[Int32], depth : Int32) -> Unit {
if depth >= 0 && !depths.contains(depth) {
depths.push(depth)
}
}
///|
fn cl_control_merge_branch_depths(
depths : Array[Int32],
source : Array[Int32],
shift_outward : Bool,
) -> Unit {
if source.length() < 8 {
for depth in source {
let next = if shift_outward { depth - 1 } else { depth }
cl_control_add_branch_depth(depths, next)
}
return
}
// Low depths have exact membership; high depths use a negative filter only.
// A high-bit collision still needs the original exact membership check.
let mut low = 0UL
let mut high = 0UL
for depth in depths {
if depth >= 0 {
let bit = 1UL << (depth & 63)
if depth < 64 {
low = low | bit
} else {
high = high | bit
}
}
}
for depth in source {
let next = if shift_outward { depth - 1 } else { depth }
if next >= 0 {
let bit = 1UL << (next & 63)
if next < 64 {
if (low & bit) == 0UL {
depths.push(next)
low = low | bit
}
} else if (high & bit) == 0UL || !depths.contains(next) {
depths.push(next)
high = high | bit
}
}
}
}
///|
fn cl_control_shift_escape(max_escape_boundary : Int32) -> Int32 {
if max_escape_boundary == 0x7fffffff {
return max_escape_boundary
}
if max_escape_boundary >= 1 {
return max_escape_boundary - 1
}
-1
}
///|
fn cl_mark_structured_interval_instruction(
instr : @lib.Instruction,
first : Array[Int32],
last : Array[Int32],
first_is_write : Array[Bool],
first_write_dominates : Array[Bool],
dominates_suffix : Bool,
cursor : Array[Int32],
record_intervals : Bool,
visited_instrs : Array[Int32],
) -> CLControlSummary {
let branch_depths : Array[Int32] = []
match instr {
@lib.LocalGet(local_idx) if record_intervals => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < first.length() {
if first[raw] < 0 {
first[raw] = cursor[0]
}
last[raw] = cursor[0]
cursor[0] += 1
}
}
@lib.LocalSet(local_idx) if record_intervals => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < first.length() {
if first[raw] < 0 {
first[raw] = cursor[0]
first_is_write[raw] = true
first_write_dominates[raw] = dominates_suffix
}
last[raw] = cursor[0]
cursor[0] += 1
}
}
@lib.LocalTee(local_idx) if record_intervals => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < first.length() {
if first[raw] < 0 {
first[raw] = cursor[0]
first_is_write[raw] = true
first_write_dominates[raw] = dominates_suffix
}
last[raw] = cursor[0]
cursor[0] += 1
}
}
_ => ()
}
if cl_instr_is_terminal(instr) {
return {
branch_depths,
max_escape_boundary: 0x7fffffff,
never_falls_through: true,
}
}
match instr {
@lib.Br(label_idx) => {
let depth = cl_label_idx_raw(label_idx)
cl_control_add_branch_depth(branch_depths, depth)
{
branch_depths,
max_escape_boundary: depth - 1,
never_falls_through: true,
}
}
@lib.BrTable(labels, default_label) => {
let mut min_depth = cl_label_idx_raw(default_label)
cl_control_add_branch_depth(branch_depths, min_depth)
for label in labels {
let depth = cl_label_idx_raw(label)
cl_control_add_branch_depth(branch_depths, depth)
if depth < min_depth {
min_depth = depth
}
}
{
branch_depths,
max_escape_boundary: min_depth - 1,
never_falls_through: true,
}
}
@lib.BrIf(label_idx)
| @lib.BrOnNull(label_idx)
| @lib.BrOnNonNull(label_idx) => {
cl_control_add_branch_depth(branch_depths, cl_label_idx_raw(label_idx))
{ branch_depths, max_escape_boundary: -1, never_falls_through: false, }
}
@lib.BrOnCast(label_idx, _, _, _)
| @lib.BrOnCastFail(label_idx, _, _, _)
| @lib.BrOnCastDescEq(label_idx, _, _)
| @lib.BrOnCastDescEqFail(label_idx, _, _) => {
cl_control_add_branch_depth(branch_depths, cl_label_idx_raw(label_idx))
{ branch_depths, max_escape_boundary: -1, never_falls_through: false, }
}
@lib.Block(_, @lib.Expr(body)) => {
let summary = cl_mark_structured_local_interval_summary(
body, first, last, first_is_write, first_write_dominates, dominates_suffix,
cursor, record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(branch_depths, summary.branch_depths, true)
let has_current_branch = summary.branch_depths.contains(0)
let max_escape_boundary = if has_current_branch {
-1
} else {
cl_control_shift_escape(summary.max_escape_boundary)
}
{
branch_depths,
max_escape_boundary,
never_falls_through: !has_current_branch &&
summary.max_escape_boundary >= 0,
}
}
@lib.Loop(_, @lib.Expr(body)) => {
let summary = cl_mark_structured_local_interval_summary(
body, first, last, first_is_write, first_write_dominates, false, cursor,
record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(branch_depths, summary.branch_depths, true)
{ branch_depths, max_escape_boundary: -1, never_falls_through: false, }
}
@lib.If(_, then_body, else_body) => {
let then_summary = cl_mark_structured_local_interval_summary(
then_body, first, last, first_is_write, first_write_dominates, false, cursor,
record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(
branch_depths,
then_summary.branch_depths,
true,
)
let mut never_falls_through = false
let max_escape_boundary = match else_body {
Some(body) => {
let else_summary = cl_mark_structured_local_interval_summary(
body, first, last, first_is_write, first_write_dominates, false, cursor,
record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(
branch_depths,
else_summary.branch_depths,
true,
)
let has_current_branch = then_summary.branch_depths.contains(0) ||
else_summary.branch_depths.contains(0)
never_falls_through = !has_current_branch &&
then_summary.max_escape_boundary >= 0 &&
else_summary.max_escape_boundary >= 0
if has_current_branch {
-1
} else {
cl_control_shift_escape(
Int32::min(
then_summary.max_escape_boundary,
else_summary.max_escape_boundary,
),
)
}
}
None => -1
}
{ branch_depths, max_escape_boundary, never_falls_through, }
}
@lib.TryTable(_, _, @lib.Expr(body)) => {
let summary = cl_mark_structured_local_interval_summary(
body, first, last, first_is_write, first_write_dominates, false, cursor,
record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(branch_depths, summary.branch_depths, true)
let has_current_branch = summary.branch_depths.contains(0)
let max_escape_boundary = if has_current_branch {
-1
} else {
cl_control_shift_escape(summary.max_escape_boundary)
}
{
branch_depths,
max_escape_boundary,
never_falls_through: !has_current_branch &&
summary.max_escape_boundary >= 0,
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
let summary = cl_mark_structured_local_interval_summary(
body, first, last, first_is_write, first_write_dominates, false, cursor,
record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(branch_depths, summary.branch_depths, true)
for catch_ in catches {
let catch_body = match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
}
let catch_summary = cl_mark_structured_local_interval_summary(
catch_body, first, last, first_is_write, first_write_dominates, false,
cursor, record_intervals, visited_instrs,
)
cl_control_merge_branch_depths(
branch_depths,
catch_summary.branch_depths,
true,
)
}
{ branch_depths, max_escape_boundary: -1, never_falls_through: false, }
}
_ => { branch_depths, max_escape_boundary: -1, never_falls_through: false, }
}
}
///|
fn cl_mark_structured_local_interval_summary(
instrs : Array[@lib.Instruction],
first : Array[Int32],
last : Array[Int32],
first_is_write : Array[Bool],
first_write_dominates : Array[Bool],
dominates_suffix : Bool,
cursor : Array[Int32],
record_intervals : Bool,
visited_instrs : Array[Int32],
) -> CLControlSummary {
let branch_depths : Array[Int32] = []
let mut current_dominates_suffix = dominates_suffix
let mut intervals_reachable = record_intervals
let mut last_summary : CLControlSummary = {
branch_depths: [],
max_escape_boundary: -1,
never_falls_through: false,
}
let mut previous_summary = last_summary
let mut last_is_unreachable = false
let mut has_previous = false
for instr in instrs {
visited_instrs[0] += 1
previous_summary = last_summary
let summary = cl_mark_structured_interval_instruction(
instr, first, last, first_is_write, first_write_dominates, current_dominates_suffix,
cursor, intervals_reachable, visited_instrs,
)
cl_control_merge_branch_depths(branch_depths, summary.branch_depths, false)
last_summary = summary
last_is_unreachable = instr == @lib.Instruction::unreachable_()
if intervals_reachable {
match instr {
@lib.BrIf(_)
| @lib.BrOnNull(_)
| @lib.BrOnNonNull(_)
| @lib.BrOnCast(_, _, _, _)
| @lib.BrOnCastFail(_, _, _, _)
| @lib.BrOnCastDescEq(_, _, _)
| @lib.BrOnCastDescEqFail(_, _, _) => current_dominates_suffix = false
_ => ()
}
if summary.never_falls_through {
intervals_reachable = false
}
}
has_previous = true
}
let max_escape_boundary = if last_is_unreachable &&
has_previous &&
previous_summary.never_falls_through {
previous_summary.max_escape_boundary
} else {
last_summary.max_escape_boundary
}
{
branch_depths,
max_escape_boundary,
never_falls_through: max_escape_boundary >= 0,
}
}
///|
fn cl_mark_structured_local_intervals_with_visits(
instrs : Array[@lib.Instruction],
first : Array[Int32],
last : Array[Int32],
first_is_write : Array[Bool],
first_write_dominates : Array[Bool],
dominates_suffix : Bool,
cursor : Array[Int32],
) -> Int32 {
let visited_instrs = [0]
ignore(
cl_mark_structured_local_interval_summary(
instrs, first, last, first_is_write, first_write_dominates, dominates_suffix,
cursor, true, visited_instrs,
),
)
visited_instrs[0]
}
///|
fn cl_mark_structured_local_intervals(
instrs : Array[@lib.Instruction],
first : Array[Int32],
last : Array[Int32],
first_is_write : Array[Bool],
first_write_dominates : Array[Bool],
dominates_suffix : Bool,
cursor : Array[Int32],
) -> Unit {
ignore(
cl_mark_structured_local_intervals_with_visits(
instrs, first, last, first_is_write, first_write_dominates, dominates_suffix,
cursor,
),
)
}
///|
fn cl_rewrite_dense_tee_structured_intervals(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, @lib.Expr(original_instrs)) = func
let types = cl_all_local_types(params, body_locals)
let total_locals = types.length()
let first = Array::make(total_locals, -1)
let last = Array::make(total_locals, -1)
let first_is_write = Array::make(total_locals, false)
let first_write_dominates = Array::make(total_locals, false)
cl_mark_structured_local_intervals(
original_instrs,
first,
last,
first_is_write,
first_write_dominates,
true,
[0],
)
let old_to_new = Array::make(total_locals, -1)
let slot_types : Array[@lib.ValType] = []
let slot_last : Array[Int32] = []
let assigned = Array::make(total_locals, false)
for idx = 0; idx < params.length(); idx = idx + 1 {
old_to_new[idx] = idx
slot_types.push(types[idx])
slot_last.push(-1)
assigned[idx] = true
}
for _remaining = params.length()
_remaining < total_locals
_remaining = _remaining + 1 {
let mut local_idx = -1
let mut earliest = 0x7fffffff
for candidate = params.length()
candidate < total_locals
candidate = candidate + 1 {
if !assigned[candidate] &&
first[candidate] >= 0 &&
first[candidate] < earliest {
local_idx = candidate
earliest = first[candidate]
}
}
if local_idx < 0 {
for candidate = params.length()
candidate < total_locals
candidate = candidate + 1 {
if !assigned[candidate] {
local_idx = candidate
break
}
}
}
if local_idx < 0 {
break
}
assigned[local_idx] = true
let accessed = first[local_idx] >= 0
let mut slot = -1
for candidate = params.length()
candidate < slot_types.length()
candidate = candidate + 1 {
if slot_types[candidate] != types[local_idx] {
continue
}
if !accessed ||
(
first_write_dominates[local_idx] &&
slot_last[candidate] < first[local_idx]
) ||
(!first_write_dominates[local_idx] && slot_last[candidate] < 0) {
slot = candidate
break
}
}
if slot < 0 {
slot = slot_types.length()
slot_types.push(types[local_idx])
slot_last.push(-1)
}
old_to_new[local_idx] = slot
if accessed {
slot_last[slot] = last[local_idx]
}
}
let body_slot_types : Array[@lib.ValType] = []
for slot = params.length(); slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let rewritten_locals = @lib.Locals::from_types(body_slot_types)
let rewritten_instrs = cl_deep_copy_instrs(original_instrs)
cl_rewrite_all_local_idxs_in_place(rewritten_instrs, old_to_new)
let cleanup_changed = cl_remove_redundant_copy_pairs(rewritten_instrs)
let changed = cleanup_changed ||
rewritten_locals != body_locals ||
!cl_old_to_new_is_identity(old_to_new)
if !changed {
{ func, changed: false, }
} else {
{
func: @lib.Func::new(rewritten_locals, @lib.Expr::new(rewritten_instrs)),
changed: true,
}
}
}
///|
fn cl_rewrite_func_structured_conservative(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, body) = func
let body_local_count = body_locals.length()
if body_local_count == 0 {
return { func, changed: false, }
}
let types = cl_all_local_types(params, body_locals)
let total_locals = types.length()
let actions : Array[CLAction] = []
let @lib.Expr(original_instrs) = body
let control_index = cl_control_index_for_body(original_instrs, None)
cl_collect_instrs(original_instrs, actions, total_locals, control_index~)
let liveness = cl_compute_liveness(actions, total_locals)
// Keep flattened liveness for Binaryen-shaped coloring/profitability, but use
// branch-aware effective-write facts when rewriting structured cleanup so one
// arm's live side-carrier write is not dropped by a sibling arm's later write
// in flattened action order.
let (rewrite_liveness, structured_write_hazards, _) = cl_compute_structured_liveness_with_write_hazards(
original_instrs,
actions,
total_locals,
control_index~,
)
let interferences = cl_compute_interferences(
actions,
liveness,
types,
params.length(),
)
cl_add_plain_live_interferences(actions, liveness, interferences)
let weights = cl_copy_weights(
actions,
rewrite_liveness.effective,
total_locals,
)
cl_remove_safe_copy_forward_interferences(
original_instrs,
types,
params.length(),
interferences,
weights,
)
cl_remove_safe_consume_forward_interferences(
original_instrs,
actions,
types,
params.length(),
interferences,
weights,
)
cl_add_structured_write_live_interferences(
structured_write_hazards,
types,
params.length(),
interferences,
)
cl_remove_same_source_fanout_interferences(
original_instrs,
types,
params.length(),
interferences,
)
cl_remove_tail_reuse_interferences(
original_instrs,
actions,
rewrite_liveness.effective,
types,
params.length(),
interferences,
)
cl_remove_path_disjoint_branch_result_interferences(
original_instrs,
actions,
types,
params.length(),
interferences,
)
cl_remove_read_only_default_interferences(
actions,
types,
params.length(),
interferences,
)
// An unassigned path reads the body's default, not the incoming parameter.
// Flat action order loses that path when another arm writes the local.
cl_add_default_entry_param_interferences(
rewrite_liveness.live_at_entry,
params.length(),
interferences,
)
let preferred = cl_preferred_compaction_flags(original_instrs, actions, types)
let retained_copy_destinations = cl_retained_copy_destination_flags(
actions,
types,
params.length(),
)
let structured_scalar_preferred = cl_structured_scalar_compaction_flags(
original_instrs,
actions,
types,
params.length(),
)
let coloring = cl_pick_coloring(
types,
params.length(),
interferences,
weights,
preferred,
retained_copy_destinations,
structured_scalar_preferred,
)
let rewritten_locals = @lib.Locals::from_types(coloring.slot_types)
let rewritten_instrs = cl_deep_copy_instrs(original_instrs)
cl_rewrite_instrs_in_place(
rewritten_instrs,
coloring.old_to_new,
rewrite_liveness.effective,
[0],
control_index~,
)
let ineffective_tee_changed = cl_remove_ineffective_tees(
rewritten_instrs,
original_instrs,
rewrite_liveness.effective,
[0],
control_index~,
)
let rewritten_total_locals = params.length() + coloring.slot_types.length()
let rewritten_gets = Array::make(rewritten_total_locals, 0)
let rewritten_sets = Array::make(rewritten_total_locals, 0)
let rewritten_tees = Array::make(rewritten_total_locals, 0)
cl_count_syntactic_local_accesses(
rewritten_instrs, rewritten_gets, rewritten_sets, rewritten_tees,
)
let rewritten_writes = Array::make(rewritten_total_locals, 0)
for local_idx = 0
local_idx < rewritten_total_locals
local_idx = local_idx + 1 {
rewritten_writes[local_idx] = rewritten_sets[local_idx] +
rewritten_tees[local_idx]
}
let dropped_default_get_changed = cl_remove_dropped_immutable_gets(
rewritten_instrs, rewritten_writes,
)
let flattened_terminal_blocks = cl_flatten_terminal_unbranched_void_blocks(
rewritten_instrs,
)
// ReFinalize-style block cleanup must not turn a nested local rewrite into
// whole-function dead-tail elimination. Binaryen's direct coalesce-locals
// pass preserves unrelated top-level control debris in broad modules.
let dead_tail_changed = false
let cleanup_changed = cl_remove_redundant_copy_pairs(rewritten_instrs)
let changed = cleanup_changed ||
ineffective_tee_changed ||
dropped_default_get_changed ||
flattened_terminal_blocks ||
dead_tail_changed ||
rewritten_instrs != original_instrs ||
!cl_old_to_new_is_identity(coloring.old_to_new) ||
rewritten_locals != body_locals
if !changed {
return { func, changed: false, }
}
let candidate = @lib.Func::new(
rewritten_locals,
@lib.Expr::new(rewritten_instrs),
)
if dropped_default_get_changed {
match cl_rewrite_all_unused_func(candidate, params) {
Some(rewrite) if rewrite.changed => return rewrite
_ => ()
}
}
{ func: candidate, changed: true, }
}
///|
fn cl_collect_instrs(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
total_locals : Int32,
control_visits~ : Array[Int32]? = None,
control_index~ : CLControlIndex? = None,
control_cursor~ : Array[Int32]? = None,
) -> Unit {
let control_index = match control_index {
Some(index) => Some(index)
None => cl_control_index_for_body(instrs, control_visits)
}
let control_cursor = match (control_index, control_cursor) {
(Some(_), None) => Some([0])
(_, cursor) => cursor
}
let mut reachable = true
for idx = 0; idx < instrs.length(); idx = idx + 1 {
let instr = instrs[idx]
let position = match control_cursor {
Some(cursor) => cursor[0]
None => -1
}
if !reachable {
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
continue
}
if control_cursor is Some(cursor) {
cursor[0] += 1
}
match instr {
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
cl_collect_instrs(
body,
actions,
total_locals,
control_visits~,
control_index~,
control_cursor~,
)
@lib.If(_, then_body, else_body) => {
cl_collect_instrs(
then_body,
actions,
total_locals,
control_visits~,
control_index~,
control_cursor~,
)
match else_body {
Some(body) =>
cl_collect_instrs(
body,
actions,
total_locals,
control_visits~,
control_index~,
control_cursor~,
)
None => ()
}
}
@lib.TryTable(_, _, @lib.Expr(body)) =>
cl_collect_instrs(
body,
actions,
total_locals,
control_visits~,
control_index~,
control_cursor~,
)
@lib.LocalGet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < total_locals {
actions.push({
kind: CLActionKind::Get,
local_idx: raw,
source: CLValueSource::Unique,
})
}
}
@lib.LocalSet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < total_locals {
actions.push({
kind: CLActionKind::Set,
local_idx: raw,
source: cl_value_source_before(instrs, idx),
})
}
}
@lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < total_locals {
actions.push({
kind: CLActionKind::Tee,
local_idx: raw,
source: cl_value_source_before(instrs, idx),
})
}
}
_ => ()
}
let no_fallthrough = match control_index {
Some(index) => cl_control_no_fallthrough(index.facts[position])
None =>
cl_instr_never_falls_through(instr, instruction_visits=control_visits)
}
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
if no_fallthrough {
reachable = false
}
}
}
///|
fn cl_compute_liveness(
actions : Array[CLAction],
total_locals : Int32,
) -> CLLiveness {
let effective = Array::make(actions.length(), false)
let live = Array::make(total_locals, false)
let mut idx = actions.length() - 1
while idx >= 0 {
let action = actions[idx]
match action.kind {
CLActionKind::Get => live[action.local_idx] = true
CLActionKind::Set | CLActionKind::Tee => {
if live[action.local_idx] {
effective[idx] = true
}
live[action.local_idx] = false
}
}
idx -= 1
}
{ effective, live_at_entry: live, }
}
///|
fn cl_live_words_to_bools(values : @bitset.BitSet) -> Array[Bool] {
Array::makei(values.length(), fn(i) { values[i] })
}
///|
fn cl_replace_live_words(
live : @bitset.BitSet,
source : @bitset.BitSet,
) -> Unit {
for i = 0; i < live.words.length(); i = i + 1 {
live.words[i] = if i < source.words.length() {
source.words[i]
} else {
0UL
}
}
if source.length() > live.length() && live.length() % 64 != 0 {
let last = live.words.length() - 1
live.words[last] = live.words[last] & ((1UL << (live.length() % 64)) - 1UL)
}
}
///|
fn cl_union_live_words(live : @bitset.BitSet, rhs : @bitset.BitSet) -> Unit {
for i = 0; i < live.words.length() && i < rhs.words.length(); i = i + 1 {
live.words[i] = live.words[i] | rhs.words[i]
}
if rhs.length() > live.length() && live.length() % 64 != 0 {
let last = live.words.length() - 1
live.words[last] = live.words[last] & ((1UL << (live.length() % 64)) - 1UL)
}
}
///|
fn cl_push_label_live_words(
label_live : @bitset.BitSet,
labels : Array[@bitset.BitSet],
) -> Array[@bitset.BitSet] {
let out = [label_live.copy()]
for live in labels {
out.push(live)
}
out
}
///|
fn cl_live_words_for_label(
labels : Array[@bitset.BitSet],
label : @lib.LabelIdx,
size : Int32,
) -> @bitset.BitSet {
let depth = cl_label_idx_raw(label)
if depth >= 0 && depth < labels.length() {
return labels[depth].copy()
}
@bitset.BitSet::new(size)
}
///|
fn cl_live_words_for_br_table(
labels : Array[@bitset.BitSet],
targets : Array[@lib.LabelIdx],
default_label : @lib.LabelIdx,
size : Int32,
) -> @bitset.BitSet {
let out = cl_live_words_for_label(labels, default_label, size)
for label in targets {
cl_union_live_words(out, cl_live_words_for_label(labels, label, size))
}
out
}
///|
fn cl_union_resume_handler_live_words(
live : @bitset.BitSet,
labels : Array[@bitset.BitSet],
handlers : Array[@lib.ResumeHandler],
) -> Unit {
for handler in handlers {
match handler {
@lib.ResumeOnLabel(_, label) =>
cl_union_live_words(
live,
cl_live_words_for_label(labels, label, live.length()),
)
@lib.ResumeOnSwitch(_) => ()
}
}
}
///|
fn cl_mark_structured_live_words_backward(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
effective : Array[Bool],
write_live_hazards : CLBitMatrix,
visited_actions : Array[Int32],
live_after : @bitset.BitSet,
label_lives : Array[@bitset.BitSet],
action_cursor : Array[Int32],
exception_live~ : @bitset.BitSet = @bitset.BitSet::new(0),
control_visits~ : Array[Int32]? = None,
control_index~ : CLControlIndex? = None,
control_start~ : Int32 = 0,
) -> @bitset.BitSet {
let live = live_after.copy()
let control_index = match control_index {
Some(index) => Some(index)
None => cl_control_index_for_body(instrs, control_visits)
}
// A reverse walk needs sibling starts, not a recursive control reproof.
// These short rows contain only the reachable prefix and are body-owned.
let positions : Array[Int32] = []
if control_index is Some(index) {
let mut position = control_start
for instr in instrs {
ignore(instr)
positions.push(position)
let no_fallthrough = cl_control_no_fallthrough(index.facts[position])
position = index.ends[position]
if no_fallthrough {
break
}
}
}
let reachable_len = match control_index {
Some(_) => positions.length()
None => cl_reachable_prefix_len(instrs, instruction_visits=control_visits)
}
let mut idx = instrs.length() - 1
while idx >= 0 {
if idx >= reachable_len {
idx -= 1
continue
}
let child_start = if control_index is Some(_) {
positions[idx] + 1
} else {
0
}
match instrs[idx] {
@lib.Block(_, @lib.Expr(body)) => {
let body_live = cl_mark_structured_live_words_backward(
body,
actions,
effective,
write_live_hazards,
visited_actions,
live,
cl_push_label_live_words(live, label_lives),
action_cursor,
exception_live~,
control_visits~,
control_index~,
control_start=child_start,
)
cl_replace_live_words(live, body_live)
}
@lib.If(_, then_body, else_body) => {
// Each child snapshots its input on entry. Keep this owned row unchanged
// until both children finish; the label head still gets its own copy.
let child_label_lives = cl_push_label_live_words(live, label_lives)
let mut else_start = child_start
if control_index is Some(index) {
for instr in then_body {
ignore(instr)
else_start = index.ends[else_start]
}
}
let else_live = match else_body {
Some(body) =>
cl_mark_structured_live_words_backward(
body,
actions,
effective,
write_live_hazards,
visited_actions,
live,
child_label_lives,
action_cursor,
exception_live~,
control_visits~,
control_index~,
control_start=else_start,
)
None => live
}
let then_live = cl_mark_structured_live_words_backward(
then_body,
actions,
effective,
write_live_hazards,
visited_actions,
live,
child_label_lives,
action_cursor,
exception_live~,
control_visits~,
control_index~,
control_start=child_start,
)
// Child rows retain the same length. For a missing else, else_live is
// this row: each old lane is read before that same lane is overwritten.
for word = 0; word < live.words.length(); word = word + 1 {
live.words[word] = then_live.words[word] | else_live.words[word]
}
}
@lib.Loop(_, @lib.Expr(body)) => {
let body_live = cl_mark_structured_live_words_backward(
body,
actions,
effective,
write_live_hazards,
visited_actions,
live,
cl_push_label_live_words(live, label_lives),
action_cursor,
exception_live~,
control_visits~,
control_index~,
control_start=child_start,
)
cl_replace_live_words(live, body_live)
}
@lib.TryTable(_, catches, @lib.Expr(body)) => {
// Catches target enclosing labels, without the try_table body label.
let caught_live = exception_live.copy()
caught_live.grow(live.length())
for catch_ in catches {
let label = match catch_ {
@lib.Catch(_, label)
| @lib.CatchRef(_, label)
| @lib.CatchAll(label)
| @lib.CatchAllRef(label) => label
}
cl_union_live_words(
caught_live,
cl_live_words_for_label(label_lives, label, live.length()),
)
}
let body_live = cl_mark_structured_live_words_backward(
body,
actions,
effective,
write_live_hazards,
visited_actions,
live,
cl_push_label_live_words(live, label_lives),
action_cursor,
exception_live=caught_live,
control_visits~,
control_index~,
control_start=child_start,
)
cl_replace_live_words(live, body_live)
}
@lib.LocalGet(_) | @lib.LocalSet(_) | @lib.LocalTee(_) => {
let action_idx = action_cursor[0]
if action_idx >= 0 && action_idx < actions.length() {
visited_actions[0] += 1
let action = actions[action_idx]
match action.kind {
CLActionKind::Get => live[action.local_idx] = true
CLActionKind::Set | CLActionKind::Tee => {
if live[action.local_idx] {
effective[action_idx] = true
let copied_dest = match action.source {
CLValueSource::Local(local_idx) => local_idx
_ => -1
}
// Enumerate only live locals. BitSet keeps the unused final
// word bits clear, including copied branch/exception rows.
for word_idx = 0
word_idx < live.words.length()
word_idx = word_idx + 1 {
let mut word = live.words[word_idx]
while word != 0UL {
let other = word_idx * 64 + word.ctz()
word = word & (word - 1UL)
if other != action.local_idx && other != copied_dest {
cl_bit_matrix_set_symmetric(
write_live_hazards,
action.local_idx,
other,
true,
)
}
}
}
}
live[action.local_idx] = false
}
}
}
action_cursor[0] -= 1
}
@lib.Br(label_idx) =>
cl_replace_live_words(
live,
cl_live_words_for_label(label_lives, label_idx, live.length()),
)
@lib.BrIf(label_idx)
| @lib.BrOnNull(label_idx)
| @lib.BrOnNonNull(label_idx)
| @lib.BrOnCast(label_idx, _, _, _)
| @lib.BrOnCastFail(label_idx, _, _, _)
| @lib.BrOnCastDescEq(label_idx, _, _)
| @lib.BrOnCastDescEqFail(label_idx, _, _) =>
cl_union_live_words(
live,
cl_live_words_for_label(label_lives, label_idx, live.length()),
)
@lib.BrTable(labels, default_label) =>
cl_replace_live_words(
live,
cl_live_words_for_br_table(
label_lives,
labels,
default_label,
live.length(),
),
)
@lib.Throw(_)
| @lib.ThrowRef
| @lib.Rethrow(_)
| @lib.ReturnCall(_)
| @lib.ReturnCallIndirect(_, _)
| @lib.ReturnCallRef(_) => cl_replace_live_words(live, exception_live)
@lib.Call(_)
| @lib.CallIndirect(_, _)
| @lib.CallRef(_)
| @lib.Suspend(_)
| @lib.StackSwitch(_, _) => cl_union_live_words(live, exception_live)
@lib.Resume(_, handlers)
| @lib.ResumeThrow(_, _, handlers)
| @lib.ResumeThrowRef(_, handlers) => {
cl_union_live_words(live, exception_live)
cl_union_resume_handler_live_words(live, label_lives, handlers)
}
instr => if cl_instr_is_terminal(instr) { live.fill(false) }
}
idx -= 1
}
live
}
///|
fn cl_compute_structured_liveness_with_write_hazards(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
total_locals : Int32,
control_index~ : CLControlIndex? = None,
) -> (CLLiveness, CLBitMatrix, Int32) {
let effective = Array::make(actions.length(), false)
let write_live_hazards = CLBitMatrix::new(total_locals)
let live_after = @bitset.BitSet::new(total_locals)
let visited_actions = [0]
let live_at_entry = cl_mark_structured_live_words_backward(
instrs,
actions,
effective,
write_live_hazards,
visited_actions,
live_after,
[],
[actions.length() - 1],
control_index~,
)
(
{ effective, live_at_entry: cl_live_words_to_bools(live_at_entry), },
write_live_hazards,
visited_actions[0],
)
}
///|
fn cl_add_interference(
interferences : CLBitMatrix,
lhs : Int32,
rhs : Int32,
) -> Unit {
if lhs == rhs {
return
}
cl_bit_matrix_set_symmetric(interferences, lhs, rhs, true)
}
///|
priv struct CLCopyForwardScan {
ok : Bool
pending : Bool
}
///|
fn cl_instr_accesses_local(instr : @lib.Instruction, local_idx : Int32) -> Bool {
match instr {
@lib.LocalGet(idx) | @lib.LocalSet(idx) | @lib.LocalTee(idx) =>
cl_local_idx_raw(idx) == local_idx
_ => false
}
}
///|
fn cl_copy_forward_scan_failed() -> CLCopyForwardScan {
{ ok: false, pending: false, }
}
///|
fn cl_copy_forward_target_reaches_dest(
instrs : Array[@lib.Instruction],
source : Int32,
target : Int32,
dest : Int32,
depth : Int32,
) -> Bool {
if target == dest {
return true
}
target != source &&
depth > 0 &&
cl_copy_forward_pair_safe_depth(instrs, target, dest, depth - 1)
}
///|
fn cl_scan_copy_forward_instrs(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
pending : Bool,
depth : Int32,
) -> CLCopyForwardScan {
let mut has_pending = pending
let mut idx = 0
while idx < instrs.length() {
let instr = instrs[idx]
match instr {
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == source => {
if has_pending {
return cl_copy_forward_scan_failed()
}
has_pending = true
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == source => {
if has_pending {
return cl_copy_forward_scan_failed()
}
has_pending = true
}
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == source => {
if !has_pending || idx + 1 >= instrs.length() {
return cl_copy_forward_scan_failed()
}
match instrs[idx + 1] {
@lib.LocalSet(next_idx) => {
if !cl_copy_forward_target_reaches_dest(
instrs,
source,
cl_local_idx_raw(next_idx),
dest,
depth,
) {
return cl_copy_forward_scan_failed()
}
has_pending = false
idx += 1
}
@lib.LocalTee(next_idx) => {
if !cl_copy_forward_target_reaches_dest(
instrs,
source,
cl_local_idx_raw(next_idx),
dest,
depth,
) {
return cl_copy_forward_scan_failed()
}
has_pending = false
idx += 1
}
_ => return cl_copy_forward_scan_failed()
}
}
@lib.Block(_, @lib.Expr(body)) => {
if has_pending {
return cl_copy_forward_scan_failed()
}
let scanned = cl_scan_copy_forward_instrs(
body, source, dest, false, depth,
)
if !scanned.ok || scanned.pending {
return cl_copy_forward_scan_failed()
}
}
@lib.If(_, then_body, else_body) => {
if has_pending {
return cl_copy_forward_scan_failed()
}
let then_scanned = cl_scan_copy_forward_instrs(
then_body, source, dest, false, depth,
)
if !then_scanned.ok || then_scanned.pending {
return cl_copy_forward_scan_failed()
}
match else_body {
Some(body) => {
let else_scanned = cl_scan_copy_forward_instrs(
body, source, dest, false, depth,
)
if !else_scanned.ok || else_scanned.pending {
return cl_copy_forward_scan_failed()
}
}
None => ()
}
}
@lib.Br(_) | @lib.BrIf(_) | @lib.BrTable(_, _) | @lib.Return =>
return cl_copy_forward_scan_failed()
@lib.Loop(_, _) | @lib.TryTable(_, _, _) =>
return cl_copy_forward_scan_failed()
_ =>
if has_pending && cl_instr_accesses_local(instr, dest) {
return cl_copy_forward_scan_failed()
}
}
idx += 1
}
{ ok: true, pending: has_pending, }
}
///|
fn cl_copy_forward_pair_safe_depth(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
depth : Int32,
) -> Bool {
let scanned = cl_scan_copy_forward_instrs(instrs, source, dest, false, depth)
scanned.ok && !scanned.pending
}
///|
fn cl_copy_forward_pair_safe(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
) -> Bool {
cl_copy_forward_pair_safe_depth(instrs, source, dest, 4)
}
///|
fn cl_copy_weight_reachable_destinations(
weights : CLCopyWeights,
source : Int32,
depth : Int32,
) -> (Array[Bool], Int32) {
let reachable = Array::make(weights.length(), false)
if source < 0 || source >= weights.length() || depth <= 0 {
return (reachable, 0)
}
let pending_locals : Array[Int32] = [source]
let pending_depths : Array[Int32] = [0]
reachable[source] = true
let mut cursor = 0
let mut visited_edges = 0
while cursor < pending_locals.length() {
let current = pending_locals[cursor]
let current_depth = pending_depths[cursor]
cursor += 1
if current_depth >= depth {
continue
}
for edge in weights.rows[current] {
let (next, _) = edge
visited_edges += 1
if !reachable[next] {
reachable[next] = true
pending_locals.push(next)
pending_depths.push(current_depth + 1)
}
}
}
reachable[source] = false
(reachable, visited_edges)
}
///|
fn cl_copy_weight_reaches(
weights : CLCopyWeights,
source : Int32,
dest : Int32,
depth : Int32,
) -> Bool {
if cl_copy_weight_get(weights, source, dest) > 0 {
return true
}
if depth <= 0 {
return false
}
for edge in weights.rows[source] {
let (mid, _) = edge
if mid != dest && cl_copy_weight_reaches(weights, mid, dest, depth - 1) {
return true
}
}
false
}
///|
fn cl_instr_tree_accesses_local(
instr : @lib.Instruction,
local_idx : Int32,
) -> Bool {
if cl_instr_accesses_local(instr, local_idx) {
return true
}
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
for child in body {
if cl_instr_tree_accesses_local(child, local_idx) {
return true
}
}
@lib.If(_, then_body, else_body) => {
for child in then_body {
if cl_instr_tree_accesses_local(child, local_idx) {
return true
}
}
match else_body {
Some(body) =>
for child in body {
if cl_instr_tree_accesses_local(child, local_idx) {
return true
}
}
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
for child in body {
if cl_instr_tree_accesses_local(child, local_idx) {
return true
}
}
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
for child in catch_body {
if cl_instr_tree_accesses_local(child, local_idx) {
return true
}
}
}
}
}
_ => ()
}
false
}
///|
fn cl_remove_same_source_fanout_interferences(
instrs : Array[@lib.Instruction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
let gets = Array::make(types.length(), 0)
let sets = Array::make(types.length(), 0)
let tees = Array::make(types.length(), 0)
cl_count_syntactic_local_accesses(instrs, gets, sets, tees)
for source = param_count; source < types.length(); source = source + 1 {
let destinations : Array[Int32] = []
for idx = 0; idx + 1 < instrs.length(); idx = idx + 1 {
match (instrs[idx], instrs[idx + 1]) {
(@lib.LocalGet(source_idx), @lib.LocalSet(dest_idx)) => {
if cl_local_idx_raw(source_idx) != source {
continue
}
let dest = cl_local_idx_raw(dest_idx)
if dest < param_count ||
dest >= types.length() ||
dest == source ||
types[dest] != types[source] ||
sets[dest] != 1 ||
tees[dest] != 0 ||
cl_instrs_suffix_writes_local(instrs, idx + 2, source) {
continue
}
let mut accessed_before_copy = false
for before = 0; before < idx; before = before + 1 {
if cl_instr_tree_accesses_local(instrs[before], dest) {
accessed_before_copy = true
}
}
if !accessed_before_copy {
destinations.push(dest)
}
}
_ => ()
}
}
if destinations.length() < 2 {
continue
}
for dest in destinations {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
}
for lhs = 0; lhs < destinations.length(); lhs = lhs + 1 {
for rhs = lhs + 1; rhs < destinations.length(); rhs = rhs + 1 {
let left = destinations[lhs]
let right = destinations[rhs]
cl_bit_matrix_set_symmetric(interferences, left, right, false)
}
}
}
}
///|
fn cl_remove_safe_copy_forward_interferences(
instrs : Array[@lib.Instruction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
weights : CLCopyWeights,
) -> Unit {
// Every pair scan rejects these barriers unconditionally, including inside
// both Block/If arms. Prove that once before repeating the same failed walk.
// Barrier-free candidates still use the complete original pair proof.
let mut checked_barriers = false
for source = param_count; source < types.length(); source = source + 1 {
if weights.rows[source].length() == 0 {
continue
}
if !checked_barriers {
if cl_pair_forward_scans_have_global_barrier(instrs) {
return
}
checked_barriers = true
}
let (reachable, _) = cl_copy_weight_reachable_destinations(
weights, source, 4,
)
for dest = 0; dest < types.length(); dest = dest + 1 {
if reachable[dest] &&
types[source] == types[dest] &&
cl_copy_forward_pair_safe(instrs, source, dest) {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
}
}
}
}
///|
fn cl_pair_forward_scans_have_global_barrier(
instrs : Array[@lib.Instruction],
) -> Bool {
for instr in instrs {
match instr {
@lib.Br(_) | @lib.BrIf(_) | @lib.BrTable(_, _) | @lib.Return =>
return true
@lib.Loop(_, _) | @lib.TryTable(_, _, _) => return true
@lib.Block(_, @lib.Expr(body)) =>
if cl_pair_forward_scans_have_global_barrier(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_pair_forward_scans_have_global_barrier(then_body) {
return true
}
match else_body {
Some(body) =>
if cl_pair_forward_scans_have_global_barrier(body) {
return true
}
None => ()
}
}
_ => ()
}
}
false
}
///|
priv struct CLConsumeForwardScan {
ok : Bool
saw : Bool
clobbered : Bool
initialized : Bool
source_written : Bool
}
///|
fn cl_consume_forward_scan_failed() -> CLConsumeForwardScan {
{
ok: false,
saw: false,
clobbered: false,
initialized: false,
source_written: false,
}
}
///|
fn cl_scan_consume_forward_instrs(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
seen_source : Bool,
clobbered : Bool,
initialized : Bool,
source_written : Bool,
) -> CLConsumeForwardScan {
let mut seen = seen_source
let mut may_be_clobbered = clobbered
let mut has_source_value = initialized
let mut source_may_have_clobbered_dest = source_written
let mut saw = false
for instr in instrs {
match instr {
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == source => {
if may_be_clobbered {
return cl_consume_forward_scan_failed()
}
if has_source_value {
seen = true
}
}
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == dest =>
if source_may_have_clobbered_dest {
return cl_consume_forward_scan_failed()
}
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == dest => {
if seen {
saw = true
may_be_clobbered = true
seen = false
}
source_may_have_clobbered_dest = false
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == dest => {
if seen {
saw = true
may_be_clobbered = true
seen = false
}
source_may_have_clobbered_dest = false
}
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == source => {
may_be_clobbered = false
has_source_value = true
source_may_have_clobbered_dest = true
seen = false
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == source => {
may_be_clobbered = false
has_source_value = true
source_may_have_clobbered_dest = true
seen = false
}
@lib.Block(_, @lib.Expr(body)) => {
let scanned = cl_scan_consume_forward_instrs(
body, source, dest, false, may_be_clobbered, has_source_value, source_may_have_clobbered_dest,
)
if !scanned.ok {
return cl_consume_forward_scan_failed()
}
if scanned.saw {
saw = true
}
may_be_clobbered = scanned.clobbered
has_source_value = scanned.initialized
source_may_have_clobbered_dest = scanned.source_written
seen = false
}
@lib.If(_, then_body, else_body) => {
let then_scanned = cl_scan_consume_forward_instrs(
then_body, source, dest, false, may_be_clobbered, has_source_value, source_may_have_clobbered_dest,
)
if !then_scanned.ok {
return cl_consume_forward_scan_failed()
}
let mut else_clobbered = may_be_clobbered
let mut else_initialized = has_source_value
let mut else_source_written = source_may_have_clobbered_dest
let mut else_saw = false
match else_body {
Some(body) => {
let else_scanned = cl_scan_consume_forward_instrs(
body, source, dest, false, may_be_clobbered, has_source_value, source_may_have_clobbered_dest,
)
if !else_scanned.ok {
return cl_consume_forward_scan_failed()
}
else_clobbered = else_scanned.clobbered
else_initialized = else_scanned.initialized
else_source_written = else_scanned.source_written
else_saw = else_scanned.saw
}
None => ()
}
if then_scanned.saw || else_saw {
saw = true
}
may_be_clobbered = then_scanned.clobbered || else_clobbered
has_source_value = then_scanned.initialized && else_initialized
source_may_have_clobbered_dest = then_scanned.source_written ||
else_source_written
seen = false
}
@lib.Br(_) | @lib.BrIf(_) | @lib.BrTable(_, _) | @lib.Return =>
return cl_consume_forward_scan_failed()
@lib.Loop(_, _) | @lib.TryTable(_, _, _) =>
return cl_consume_forward_scan_failed()
_ => ()
}
}
ignore(seen)
{
ok: true,
saw,
clobbered: may_be_clobbered,
initialized: has_source_value,
source_written: source_may_have_clobbered_dest,
}
}
///|
fn cl_consume_forward_pair_safe(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
) -> Bool {
let scanned = cl_scan_consume_forward_instrs(
instrs, source, dest, false, false, false, false,
)
scanned.ok && scanned.saw
}
///|
fn cl_source_write_is_dest_copy(
instrs : Array[@lib.Instruction],
idx : Int32,
dest : Int32,
) -> Bool {
if idx <= 0 {
return false
}
match instrs[idx - 1] {
@lib.LocalGet(local_idx) => cl_local_idx_raw(local_idx) == dest
_ => false
}
}
///|
fn cl_action_is_effective(effective : Array[Bool], action_idx : Int32) -> Bool {
action_idx >= 0 && action_idx < effective.length() && effective[action_idx]
}
///|
fn cl_skip_source_write_dest_read_actions(
instrs : Array[@lib.Instruction],
effective : Array[Bool],
action_cursor : Array[Int32],
instruction_visits~ : Array[Int32]? = None,
) -> Unit {
for instr in instrs {
match instruction_visits {
Some(count) => count[0] += 1
None => ()
}
match instr {
@lib.LocalGet(_) | @lib.LocalSet(_) | @lib.LocalTee(_) =>
action_cursor[0] += 1
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_skip_source_write_dest_read_actions(
body,
effective,
action_cursor,
instruction_visits~,
)
@lib.If(_, then_body, else_body) => {
cl_skip_source_write_dest_read_actions(
then_body,
effective,
action_cursor,
instruction_visits~,
)
match else_body {
Some(body) =>
cl_skip_source_write_dest_read_actions(
body,
effective,
action_cursor,
instruction_visits~,
)
None => ()
}
}
_ => ()
}
}
ignore(effective)
}
///|
// These steps belong to one immutable body and its effective-action table.
// Keeping only local operations and control boundaries avoids decoding the same
// instruction forest once for every source local.
priv enum CLSourceHazardStep {
Read(Int32)
Write(Int32, Int32)
Branch(Array[CLSourceHazardStep], Array[CLSourceHazardStep])
Barrier
Reset
}
///|
fn cl_compile_source_hazard_steps(
instrs : Array[@lib.Instruction],
effective : Array[Bool],
action_cursor : Array[Int32],
steps : Array[CLSourceHazardStep],
instruction_visits : Array[Int32]?,
) -> Unit {
for idx = 0; idx < instrs.length(); idx = idx + 1 {
match instruction_visits {
Some(count) => count[0] += 1
None => ()
}
match instrs[idx] {
@lib.LocalGet(local_idx) => {
action_cursor[0] += 1
steps.push(Read(cl_local_idx_raw(local_idx)))
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) => {
let action_idx = action_cursor[0]
action_cursor[0] += 1
if cl_action_is_effective(effective, action_idx) {
let copied_dest = if idx > 0 {
match instrs[idx - 1] {
@lib.LocalGet(dest) => cl_local_idx_raw(dest)
_ => -1
}
} else {
-1
}
steps.push(Write(cl_local_idx_raw(local_idx), copied_dest))
}
}
@lib.Block(_, @lib.Expr(body)) =>
cl_compile_source_hazard_steps(
body, effective, action_cursor, steps, instruction_visits,
)
@lib.If(_, then_body, else_body) => {
let yes = []
let no = []
cl_compile_source_hazard_steps(
then_body, effective, action_cursor, yes, instruction_visits,
)
match else_body {
Some(body) =>
cl_compile_source_hazard_steps(
body, effective, action_cursor, no, instruction_visits,
)
None => ()
}
steps.push(Branch(yes, no))
}
@lib.Loop(_, @lib.Expr(body)) | @lib.TryTable(_, _, @lib.Expr(body)) => {
cl_skip_source_write_dest_read_actions(
body,
effective,
action_cursor,
instruction_visits~,
)
steps.push(Barrier)
}
@lib.BrIf(_) | @lib.BrTable(_, _) => steps.push(Barrier)
@lib.Br(_) | @lib.Return => steps.push(Reset)
_ => ()
}
}
}
///|
fn cl_run_source_hazard_steps(
steps : Array[CLSourceHazardStep],
source : Int32,
candidate_dests : Array[Int32],
may_clobber : Array[Bool],
hazards : Array[Bool],
) -> Unit {
for step in steps {
match step {
Read(local_id) =>
if local_id >= 0 && local_id < hazards.length() && may_clobber[local_id] {
hazards[local_id] = true
may_clobber[local_id] = false
}
Write(local_id, copied_dest) =>
if local_id == source {
for dest in candidate_dests {
may_clobber[dest] = dest != copied_dest
}
} else if local_id >= 0 && local_id < may_clobber.length() {
may_clobber[local_id] = false
}
Branch(yes, no) => {
let then_state = may_clobber.copy()
cl_run_source_hazard_steps(
yes, source, candidate_dests, then_state, hazards,
)
cl_run_source_hazard_steps(
no, source, candidate_dests, may_clobber, hazards,
)
for dest in candidate_dests {
may_clobber[dest] = then_state[dest] || may_clobber[dest]
}
}
Barrier =>
for dest in candidate_dests {
if may_clobber[dest] {
hazards[dest] = true
may_clobber[dest] = false
}
}
Reset =>
for dest in candidate_dests {
may_clobber[dest] = false
}
}
}
}
///|
fn cl_mark_source_write_dest_read_hazards(
instrs : Array[@lib.Instruction],
effective : Array[Bool],
source : Int32,
candidate_dests : Array[Int32],
may_clobber : Array[Bool],
hazards : Array[Bool],
action_cursor : Array[Int32],
instruction_visits~ : Array[Int32]? = None,
) -> Unit {
for idx = 0; idx < instrs.length(); idx = idx + 1 {
match instruction_visits {
Some(count) => count[0] += 1
None => ()
}
match instrs[idx] {
@lib.LocalGet(local_idx) => {
action_cursor[0] += 1
let local_id = cl_local_idx_raw(local_idx)
if local_id >= 0 && local_id < hazards.length() && may_clobber[local_id] {
hazards[local_id] = true
may_clobber[local_id] = false
}
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) => {
let action_idx = action_cursor[0]
action_cursor[0] += 1
if cl_action_is_effective(effective, action_idx) {
let local_id = cl_local_idx_raw(local_idx)
if local_id == source {
let copied_dest = if idx > 0 {
match instrs[idx - 1] {
@lib.LocalGet(dest) => cl_local_idx_raw(dest)
_ => -1
}
} else {
-1
}
for dest in candidate_dests {
may_clobber[dest] = dest != copied_dest
}
} else if local_id >= 0 && local_id < may_clobber.length() {
may_clobber[local_id] = false
}
}
}
@lib.Block(_, @lib.Expr(body)) =>
cl_mark_source_write_dest_read_hazards(
body,
effective,
source,
candidate_dests,
may_clobber,
hazards,
action_cursor,
instruction_visits~,
)
@lib.If(_, then_body, else_body) => {
let incoming = may_clobber.copy()
let then_state = incoming.copy()
cl_mark_source_write_dest_read_hazards(
then_body,
effective,
source,
candidate_dests,
then_state,
hazards,
action_cursor,
instruction_visits~,
)
let else_state = incoming
match else_body {
Some(body) =>
cl_mark_source_write_dest_read_hazards(
body,
effective,
source,
candidate_dests,
else_state,
hazards,
action_cursor,
instruction_visits~,
)
None => ()
}
for dest in candidate_dests {
may_clobber[dest] = then_state[dest] || else_state[dest]
}
}
@lib.Loop(_, @lib.Expr(body)) | @lib.TryTable(_, _, @lib.Expr(body)) => {
cl_skip_source_write_dest_read_actions(body, effective, action_cursor)
for dest in candidate_dests {
if may_clobber[dest] {
hazards[dest] = true
may_clobber[dest] = false
}
}
}
@lib.BrIf(_) | @lib.BrTable(_, _) =>
for dest in candidate_dests {
if may_clobber[dest] {
hazards[dest] = true
may_clobber[dest] = false
}
}
@lib.Br(_) | @lib.Return =>
for dest in candidate_dests {
may_clobber[dest] = false
}
_ => ()
}
}
}
///|
fn cl_source_write_dest_read_hazards(
instrs : Array[@lib.Instruction],
effective : Array[Bool],
source : Int32,
candidate_dests : Array[Int32],
total_locals : Int32,
instruction_visits~ : Array[Int32]? = None,
) -> Array[Bool] {
let hazards = Array::make(total_locals, false)
cl_mark_source_write_dest_read_hazards(
instrs,
effective,
source,
candidate_dests,
Array::make(total_locals, false),
hazards,
[0],
instruction_visits~,
)
hazards
}
///|
fn cl_add_structured_write_live_interferences(
write_live_hazards : CLBitMatrix,
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
candidate_visits~ : Array[Int32]? = None,
) -> Unit {
// The triangular matrix stores each symmetric pair once. Walk its occupied
// bits, preserving type and parameter filters without probing every pair.
let mut lower = 0
let size = write_live_hazards.size
for word_idx = 0
word_idx < write_live_hazards.bits.words.length()
word_idx = word_idx + 1 {
let mut word = write_live_hazards.bits.words[word_idx]
while word != 0UL {
let index = word_idx * 64 + word.ctz()
word = word & (word - 1UL)
if index >= write_live_hazards.bits.length() {
break
}
while lower + 1 < size &&
index >= write_live_hazards.row_offsets[lower + 1] {
lower += 1
}
let upper = lower + 1 + index - write_live_hazards.row_offsets[lower]
if candidate_visits is Some(visits) {
visits[0] += 1
}
if lower < types.length() &&
upper < types.length() &&
upper >= param_count &&
types[lower] == types[upper] {
cl_add_interference(interferences, lower, upper)
}
}
}
}
///|
fn cl_compute_linear_interferences(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
liveness : CLLiveness,
types : Array[@lib.ValType],
param_count : Int32,
) -> CLBitMatrix {
let interferences = cl_compute_interferences(
actions, liveness, types, param_count,
)
cl_add_entry_value_interferences(actions, types, param_count, interferences)
// Value-equivalent copy chains may share an abstract value, but a later
// write still cannot reuse that slot while a copied destination remains
// live. Make this semantic hazard authoritative before coloring.
cl_add_linear_source_write_dest_read_interferences(
instrs,
actions,
liveness.effective,
types,
param_count,
interferences,
)
cl_remove_read_only_default_interferences(
actions, types, param_count, interferences,
)
interferences
}
///|
fn cl_local_read_write_flags(
actions : Array[CLAction],
total_locals : Int32,
) -> (Array[Bool], Array[Bool]) {
let reads = Array::make(total_locals, false)
let writes = Array::make(total_locals, false)
for action in actions {
match action.kind {
CLActionKind::Get => reads[action.local_idx] = true
CLActionKind::Set | CLActionKind::Tee => writes[action.local_idx] = true
}
}
(reads, writes)
}
///|
fn cl_source_write_dest_read_active_flags(
actions : Array[CLAction],
effective : Array[Bool],
total_locals : Int32,
) -> (Array[Bool], Array[Bool]) {
let writers = Array::make(total_locals, false)
let readers = Array::make(total_locals, false)
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
let action = actions[action_idx]
match action.kind {
CLActionKind::Get => readers[action.local_idx] = true
CLActionKind::Set | CLActionKind::Tee =>
if cl_action_is_effective(effective, action_idx) {
writers[action.local_idx] = true
}
}
}
(writers, readers)
}
///|
fn cl_source_write_dest_read_candidate_dests(
source : Int32,
readers : Array[Bool],
types : Array[@lib.ValType],
interferences : CLBitMatrix,
first_effective_write : Array[Int32],
latest_get : Array[Int32],
candidate_visits~ : Array[Int32]? = None,
) -> Array[Int32] {
let candidates : Array[Int32] = []
if source < 0 || source >= types.length() || source >= interferences.length() {
return candidates
}
if source >= first_effective_write.length() ||
first_effective_write[source] < 0 {
return candidates
}
for dest = 0; dest < types.length(); dest = dest + 1 {
match candidate_visits {
Some(visits) => visits[0] += 1
None => ()
}
if source != dest &&
dest < readers.length() &&
dest < latest_get.length() &&
readers[dest] &&
latest_get[dest] > first_effective_write[source] &&
types[source] == types[dest] &&
!cl_bit_matrix_get(interferences, source, dest) {
candidates.push(dest)
}
}
candidates
}
///|
fn cl_add_source_write_dest_read_interferences(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
effective : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
instruction_visits~ : Array[Int32]? = None,
candidate_visits~ : Array[Int32]? = None,
indexed_readers~ : Bool = true,
index_builds~ : Array[Int32]? = None,
) -> Unit {
let (writers, readers) = cl_source_write_dest_read_active_flags(
actions,
effective,
types.length(),
)
let reader_index = if indexed_readers &&
cl_source_hazard_reader_index_can_filter(types, readers) {
match index_builds {
Some(count) => count[0] += 1
None => ()
}
Some(cl_source_hazard_reader_index(types, readers))
} else {
None
}
let first_effective_write = Array::make(types.length(), -1)
let latest_get = Array::make(types.length(), -1)
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
let action = actions[action_idx]
match action.kind {
CLActionKind::Get => latest_get[action.local_idx] = action_idx
CLActionKind::Set | CLActionKind::Tee =>
if cl_action_is_effective(effective, action_idx) &&
first_effective_write[action.local_idx] < 0 {
first_effective_write[action.local_idx] = action_idx
}
}
}
let mut compiled : Array[CLSourceHazardStep]? = None
for source = param_count; source < types.length(); source = source + 1 {
if !writers[source] {
continue
}
let candidate_dests = match reader_index {
Some(index) =>
cl_source_write_dest_read_candidate_dests_indexed(
source,
index,
interferences,
first_effective_write,
latest_get,
candidate_visits~,
)
None =>
cl_source_write_dest_read_candidate_dests(
source,
readers,
types,
interferences,
first_effective_write,
latest_get,
candidate_visits~,
)
}
if candidate_dests.length() == 0 {
continue
}
let steps = match compiled {
Some(steps) => steps
None => {
let steps = []
cl_compile_source_hazard_steps(
instrs,
effective,
[0],
steps,
instruction_visits,
)
compiled = Some(steps)
steps
}
}
let hazards = Array::make(types.length(), false)
cl_run_source_hazard_steps(
steps,
source,
candidate_dests,
Array::make(types.length(), false),
hazards,
)
for dest in candidate_dests {
if hazards[dest] {
cl_add_interference(interferences, source, dest)
}
}
}
}
///|
fn cl_collect_action_depths(
instrs : Array[@lib.Instruction],
depths : Array[Int32],
depth : Int32,
control_index~ : CLControlIndex? = None,
control_cursor~ : Array[Int32]? = None,
) -> Unit {
let control_index = match control_index {
Some(index) => Some(index)
None => cl_control_index_for_body(instrs, None)
}
let control_cursor = match (control_index, control_cursor) {
(Some(_), None) => Some([0])
(_, cursor) => cursor
}
let mut reachable = true
for instr in instrs {
let position = match control_cursor {
Some(cursor) => cursor[0]
None => -1
}
if !reachable {
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
continue
}
if control_cursor is Some(cursor) {
cursor[0] += 1
}
match instr {
@lib.LocalGet(_) | @lib.LocalSet(_) | @lib.LocalTee(_) =>
depths.push(depth)
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_collect_action_depths(
body,
depths,
depth + 1,
control_index~,
control_cursor~,
)
@lib.If(_, then_body, else_body) => {
cl_collect_action_depths(
then_body,
depths,
depth + 1,
control_index~,
control_cursor~,
)
match else_body {
Some(body) =>
cl_collect_action_depths(
body,
depths,
depth + 1,
control_index~,
control_cursor~,
)
None => ()
}
}
_ => ()
}
let no_fallthrough = match control_index {
Some(index) => cl_control_no_fallthrough(index.facts[position])
None => cl_instr_makes_rest_unreachable(instr)
}
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
if no_fallthrough {
reachable = false
}
}
}
///|
priv struct CLTailReuseFacts {
last_get : Array[Int32]
first_effective_write : Array[Int32]
source_safe : Array[Bool]
source_read_after_write : Array[Bool]
}
///|
fn cl_tail_reuse_facts_with_visits(
actions : Array[CLAction],
effective : Array[Bool],
depths : Array[Int32],
total_locals : Int32,
) -> (CLTailReuseFacts, Int32) {
let last_get = Array::make(total_locals, -1)
let first_effective_write = Array::make(total_locals, -1)
let source_safe = Array::make(total_locals, true)
let source_read_after_write = Array::make(total_locals, false)
let mut visited_actions = 0
for idx = 0; idx < actions.length(); idx = idx + 1 {
visited_actions += 1
let action = actions[idx]
if action.local_idx < 0 || action.local_idx >= total_locals {
continue
}
match action.kind {
CLActionKind::Get => last_get[action.local_idx] = idx
CLActionKind::Set | CLActionKind::Tee =>
if cl_action_is_effective(effective, idx) &&
first_effective_write[action.local_idx] < 0 {
first_effective_write[action.local_idx] = idx
}
}
}
for idx = 0; idx < actions.length(); idx = idx + 1 {
visited_actions += 1
let action = actions[idx]
let local_idx = action.local_idx
if local_idx < 0 || local_idx >= total_locals {
continue
}
let first_write = first_effective_write[local_idx]
match action.kind {
CLActionKind::Get =>
if first_write < 0 || idx < first_write {
source_safe[local_idx] = false
} else if idx > first_write {
source_read_after_write[local_idx] = true
if idx >= depths.length() || depths[idx] != 0 {
source_safe[local_idx] = false
}
}
CLActionKind::Set | CLActionKind::Tee =>
if cl_action_is_effective(effective, idx) &&
(idx >= depths.length() || depths[idx] != 0) {
source_safe[local_idx] = false
}
}
}
(
{ last_get, first_effective_write, source_safe, source_read_after_write, },
visited_actions,
)
}
///|
fn cl_tail_reuse_pair_safe_from_facts(
facts : CLTailReuseFacts,
source : Int32,
dest : Int32,
) -> Bool {
source >= 0 &&
source < facts.first_effective_write.length() &&
dest >= 0 &&
dest < facts.last_get.length() &&
facts.last_get[dest] >= 0 &&
facts.first_effective_write[source] > facts.last_get[dest] &&
facts.source_safe[source] &&
facts.source_read_after_write[source]
}
///|
fn cl_remove_tail_reuse_interferences(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
effective : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
let depths : Array[Int32] = []
cl_collect_action_depths(instrs, depths, 0)
let (facts, _) = cl_tail_reuse_facts_with_visits(
actions,
effective,
depths,
types.length(),
)
for source = param_count; source < types.length(); source = source + 1 {
for dest = 0; dest < param_count; dest = dest + 1 {
if source != dest &&
types[source] == types[dest] &&
cl_tail_reuse_pair_safe_from_facts(facts, source, dest) {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
}
}
}
}
///|
#valtype
priv struct CLPathDisjointScan {
ok : Bool
saw_source_write : Bool
source_initialized : Bool
source_clobbers_dest : Bool
dest_clobbers_source : Bool
}
///|
fn cl_path_disjoint_scan_failed() -> CLPathDisjointScan {
{
ok: false,
saw_source_write: false,
source_initialized: false,
source_clobbers_dest: false,
dest_clobbers_source: false,
}
}
///|
fn cl_dest_write_is_source_copy(
instrs : Array[@lib.Instruction],
idx : Int32,
source : Int32,
) -> Bool {
if idx <= 0 {
return false
}
match instrs[idx - 1] {
@lib.LocalGet(local_idx) => cl_local_idx_raw(local_idx) == source
_ => false
}
}
///|
fn cl_scan_path_disjoint_branch_result_instrs(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
source_initialized : Bool,
source_clobbers_dest : Bool,
dest_clobbers_source : Bool,
) -> CLPathDisjointScan {
let mut has_source_value = source_initialized
let mut source_may_clobber_dest = source_clobbers_dest
let mut dest_may_clobber_source = dest_clobbers_source
let mut saw_source_write = false
for idx = 0; idx < instrs.length(); idx = idx + 1 {
let instr = instrs[idx]
match instr {
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == source =>
if !has_source_value || dest_may_clobber_source {
return cl_path_disjoint_scan_failed()
}
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == dest =>
if source_may_clobber_dest {
return cl_path_disjoint_scan_failed()
}
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == source => {
has_source_value = true
saw_source_write = true
source_may_clobber_dest = !cl_source_write_is_dest_copy(
instrs, idx, dest,
)
dest_may_clobber_source = false
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == source => {
has_source_value = true
saw_source_write = true
source_may_clobber_dest = !cl_source_write_is_dest_copy(
instrs, idx, dest,
)
dest_may_clobber_source = false
}
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == dest => {
source_may_clobber_dest = false
dest_may_clobber_source = has_source_value &&
!cl_dest_write_is_source_copy(instrs, idx, source)
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == dest => {
source_may_clobber_dest = false
dest_may_clobber_source = has_source_value &&
!cl_dest_write_is_source_copy(instrs, idx, source)
}
@lib.Block(_, @lib.Expr(body)) => {
let scanned = cl_scan_path_disjoint_branch_result_instrs(
body, source, dest, has_source_value, source_may_clobber_dest, dest_may_clobber_source,
)
if !scanned.ok {
return cl_path_disjoint_scan_failed()
}
if scanned.saw_source_write {
saw_source_write = true
}
has_source_value = scanned.source_initialized
source_may_clobber_dest = scanned.source_clobbers_dest
dest_may_clobber_source = scanned.dest_clobbers_source
}
@lib.If(_, then_body, else_body) => {
let then_scanned = cl_scan_path_disjoint_branch_result_instrs(
then_body, source, dest, has_source_value, source_may_clobber_dest, dest_may_clobber_source,
)
if !then_scanned.ok {
return cl_path_disjoint_scan_failed()
}
let mut else_scanned : CLPathDisjointScan = {
ok: true,
saw_source_write: false,
source_initialized: has_source_value,
source_clobbers_dest: source_may_clobber_dest,
dest_clobbers_source: dest_may_clobber_source,
}
match else_body {
Some(body) => {
else_scanned = cl_scan_path_disjoint_branch_result_instrs(
body, source, dest, has_source_value, source_may_clobber_dest, dest_may_clobber_source,
)
if !else_scanned.ok {
return cl_path_disjoint_scan_failed()
}
}
None => ()
}
saw_source_write = saw_source_write ||
then_scanned.saw_source_write ||
else_scanned.saw_source_write
has_source_value = then_scanned.source_initialized &&
else_scanned.source_initialized
source_may_clobber_dest = then_scanned.source_clobbers_dest ||
else_scanned.source_clobbers_dest
dest_may_clobber_source = then_scanned.dest_clobbers_source ||
else_scanned.dest_clobbers_source
}
@lib.Br(_) | @lib.BrIf(_) | @lib.BrTable(_, _) | @lib.Return =>
return cl_path_disjoint_scan_failed()
@lib.Loop(_, _) | @lib.TryTable(_, _, _) =>
return cl_path_disjoint_scan_failed()
_ => ()
}
}
{
ok: true,
saw_source_write,
source_initialized: has_source_value,
source_clobbers_dest: source_may_clobber_dest,
dest_clobbers_source: dest_may_clobber_source,
}
}
///|
fn cl_path_disjoint_branch_result_pair_safe(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
) -> Bool {
let scanned = cl_scan_path_disjoint_branch_result_instrs(
instrs, source, dest, false, false, false,
)
scanned.ok && scanned.saw_source_write
}
///|
fn cl_path_disjoint_candidate_dests(
source : Int32,
writes : Array[Bool],
types : Array[@lib.ValType],
interferences : CLBitMatrix,
) -> Array[Int32] {
let candidates : Array[Int32] = []
if source < 0 ||
source >= writes.length() ||
source >= types.length() ||
source >= interferences.length() ||
!writes[source] {
return candidates
}
for dest = 0; dest < types.length(); dest = dest + 1 {
if source != dest &&
types[source] == types[dest] &&
cl_bit_matrix_get(interferences, source, dest) {
candidates.push(dest)
}
}
candidates
}
///|
fn cl_remove_path_disjoint_branch_result_interferences(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
if cl_pair_forward_scans_have_global_barrier(instrs) {
return
}
let (_, writes) = cl_local_read_write_flags(actions, types.length())
for source = param_count; source < types.length(); source = source + 1 {
for
dest in cl_path_disjoint_candidate_dests(
source, writes, types, interferences,
) {
if cl_path_disjoint_branch_result_pair_safe(instrs, source, dest) {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
}
}
}
}
///|
fn cl_mark_consume_forward_syntactic_candidates(
instrs : Array[@lib.Instruction],
candidates : Array[@bitset.BitSet],
total_locals : Int32,
) -> Unit {
let seen = Array::make(total_locals, false)
let seen_members : Array[Int32] = []
for instr in instrs {
match instr {
@lib.LocalGet(local_idx) => {
let source = cl_local_idx_raw(local_idx)
if source >= 0 && source < total_locals && !seen[source] {
seen[source] = true
seen_members.push(source)
}
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) => {
let dest = cl_local_idx_raw(local_idx)
if dest >= 0 && dest < total_locals {
for source in seen_members {
if source != dest {
candidates[source][dest] = true
}
}
}
}
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) => {
cl_mark_consume_forward_syntactic_candidates(
body, candidates, total_locals,
)
for source in seen_members {
seen[source] = false
}
seen_members.clear()
}
@lib.If(_, then_body, else_body) => {
cl_mark_consume_forward_syntactic_candidates(
then_body, candidates, total_locals,
)
match else_body {
Some(body) =>
cl_mark_consume_forward_syntactic_candidates(
body, candidates, total_locals,
)
None => ()
}
for source in seen_members {
seen[source] = false
}
seen_members.clear()
}
_ => ()
}
}
}
///|
fn cl_consume_forward_syntactic_candidates(
instrs : Array[@lib.Instruction],
total_locals : Int32,
) -> Array[@bitset.BitSet] {
let candidates : Array[@bitset.BitSet] = []
for _ in 0.. Array[Int32] {
let candidates : Array[Int32] = []
ignore(interferences)
if source < 0 ||
source >= reads.length() ||
source >= types.length() ||
source >= first_initialized_get.length() ||
!reads[source] ||
first_initialized_get[source] < 0 {
return candidates
}
for dest = 0; dest < types.length(); dest = dest + 1 {
if source != dest &&
dest < writes.length() &&
dest < latest_write.length() &&
writes[dest] &&
source < syntactic_candidates.length() &&
syntactic_candidates[source][dest] &&
latest_write[dest] > first_initialized_get[source] &&
types[source] == types[dest] {
candidates.push(dest)
}
}
candidates
}
///|
fn cl_remove_safe_consume_forward_interferences(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
weights : CLCopyWeights,
) -> Unit {
if cl_pair_forward_scans_have_global_barrier(instrs) {
return
}
let (reads, writes) = cl_local_read_write_flags(actions, types.length())
let syntactic_candidates = cl_consume_forward_syntactic_candidates(
instrs,
types.length(),
)
let initialized = Array::make(types.length(), false)
let first_initialized_get = Array::make(types.length(), -1)
let latest_write = Array::make(types.length(), -1)
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
let action = actions[action_idx]
match action.kind {
CLActionKind::Get =>
if initialized[action.local_idx] &&
first_initialized_get[action.local_idx] < 0 {
first_initialized_get[action.local_idx] = action_idx
}
CLActionKind::Set | CLActionKind::Tee => {
initialized[action.local_idx] = true
latest_write[action.local_idx] = action_idx
}
}
}
for source = param_count; source < types.length(); source = source + 1 {
for
dest in cl_consume_forward_candidate_dests(
source, reads, writes, types, interferences, first_initialized_get, latest_write,
syntactic_candidates,
) {
if cl_consume_forward_pair_safe(instrs, source, dest) {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
for target = 0; target < types.length(); target = target + 1 {
if source != target &&
types[source] == types[target] &&
cl_copy_weight_reaches(weights, dest, target, 4) {
cl_bit_matrix_set_symmetric(interferences, source, target, false)
}
}
}
}
}
}
///|
fn cl_source_is_explicit_default(
source : CLValueSource,
ty : @lib.ValType,
) -> Bool {
match source {
CLValueSource::Const(key) =>
if ty == @lib.ValType::i32() {
key == @debug.to_string(@lib.Instruction::i32_const(@lib.I32(0)))
} else if ty == @lib.ValType::i64() {
key == @debug.to_string(@lib.Instruction::i64_const(@lib.I64(0L)))
} else if ty == @lib.ValType::f32() {
key == @debug.to_string(@lib.Instruction::f32_const(0.0))
} else if ty == @lib.ValType::f64() {
key == @debug.to_string(@lib.Instruction::f64_const(0.0))
} else {
false
}
_ => false
}
}
///|
fn cl_initial_value(
interner : CLValueInterner,
idx : Int32,
param_count : Int32,
ty : @lib.ValType,
) -> Int32 {
if idx < param_count {
interner.fresh()
} else if @lib.has_default(ty) {
cl_default_identity(interner, ty)
} else {
interner.fresh()
}
}
///|
fn cl_value_for_source(
source : CLValueSource,
current_values : Array[Int32],
interner : CLValueInterner,
) -> Int32 {
match source {
CLValueSource::Unique => interner.fresh()
CLValueSource::Const(key) => interner.intern("const:\{key}")
CLValueSource::Local(src_local) =>
if src_local >= 0 && src_local < current_values.length() {
current_values[src_local]
} else {
interner.fresh()
}
}
}
///|
fn cl_add_default_entry_param_interferences(
live_at_entry : Array[Bool],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
for local_id = param_count
local_id < live_at_entry.length()
local_id = local_id + 1 {
if live_at_entry[local_id] {
for param = 0; param < param_count; param = param + 1 {
cl_add_interference(interferences, local_id, param)
}
}
}
}
///|
fn cl_compute_interferences(
actions : Array[CLAction],
liveness : CLLiveness,
types : Array[@lib.ValType],
param_count : Int32,
live_visits~ : Array[Int32]? = None,
) -> CLBitMatrix {
let total_locals = types.length()
let interferences = CLBitMatrix::new(total_locals)
let interner = CLValueInterner::new()
let current_values = Array::make(total_locals, -1)
for idx = 0; idx < total_locals; idx = idx + 1 {
current_values[idx] = cl_initial_value(
interner,
idx,
param_count,
types[idx],
)
}
for lhs = 0; lhs < param_count; lhs = lhs + 1 {
for rhs = lhs + 1; rhs < param_count; rhs = rhs + 1 {
cl_add_interference(interferences, lhs, rhs)
}
}
for local_idx = param_count
local_idx < total_locals
local_idx = local_idx + 1 {
if liveness.live_at_entry[local_idx] {
for param = 0; param < param_count; param = param + 1 {
cl_add_interference(interferences, local_idx, param)
}
for other = param_count; other < local_idx; other = other + 1 {
if liveness.live_at_entry[other] &&
current_values[local_idx] != current_values[other] {
cl_add_interference(interferences, local_idx, other)
}
}
}
}
let remaining_gets = Array::make(total_locals, 0)
for action in actions {
match action.kind {
CLActionKind::Get => remaining_gets[action.local_idx] += 1
_ => ()
}
}
let live = CLCfgLiveSet::new(total_locals)
for local = 0; local < total_locals; local = local + 1 {
if liveness.live_at_entry[local] {
cl_cfg_live_set_add(live, local)
}
}
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
let action = actions[action_idx]
match action.kind {
CLActionKind::Get => {
cl_cfg_live_set_add(live, action.local_idx)
if live.members.length() > 1 {
for other in live.members {
match live_visits {
Some(visits) => visits[0] += 1
None => ()
}
if other != action.local_idx &&
current_values[other] != current_values[action.local_idx] {
cl_add_interference(interferences, action.local_idx, other)
}
}
}
remaining_gets[action.local_idx] -= 1
if remaining_gets[action.local_idx] == 0 {
cl_cfg_live_set_remove(live, action.local_idx)
}
}
CLActionKind::Set | CLActionKind::Tee => {
let new_value = if cl_source_is_explicit_default(
action.source,
types[action.local_idx],
) {
cl_default_identity(interner, types[action.local_idx])
} else {
cl_value_for_source(action.source, current_values, interner)
}
if liveness.effective[action_idx] {
if live.members.length() > 0 {
for other in live.members {
match live_visits {
Some(visits) => visits[0] += 1
None => ()
}
if other != action.local_idx && current_values[other] != new_value {
cl_add_interference(interferences, action.local_idx, other)
}
}
}
cl_cfg_live_set_add(live, action.local_idx)
} else {
cl_cfg_live_set_remove(live, action.local_idx)
}
current_values[action.local_idx] = new_value
}
}
}
interferences
}
///|
fn cl_remove_read_only_default_interferences(
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
let gets = Array::make(types.length(), 0)
let writes = Array::make(types.length(), 0)
let nondefault_writes = Array::make(types.length(), 0)
for action in actions {
match action.kind {
CLActionKind::Get => gets[action.local_idx] += 1
CLActionKind::Set | CLActionKind::Tee => {
writes[action.local_idx] += 1
if !cl_source_is_explicit_default(
action.source,
types[action.local_idx],
) {
nondefault_writes[action.local_idx] += 1
}
}
}
}
for lhs = param_count; lhs < types.length(); lhs = lhs + 1 {
if gets[lhs] == 0 || writes[lhs] != 0 {
continue
}
for rhs = lhs + 1; rhs < types.length(); rhs = rhs + 1 {
if gets[rhs] > 0 && writes[rhs] == 0 && types[lhs] == types[rhs] {
cl_bit_matrix_set_symmetric(interferences, lhs, rhs, false)
}
}
}
for source = param_count; source < types.length(); source = source + 1 {
if writes[source] == 0 || nondefault_writes[source] != 0 {
continue
}
for dest = param_count; dest < types.length(); dest = dest + 1 {
if source != dest &&
gets[dest] > 0 &&
writes[dest] == 0 &&
types[source] == types[dest] {
cl_bit_matrix_set_symmetric(interferences, source, dest, false)
}
}
}
}
///|
fn cl_add_entry_value_interferences(
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
) -> Unit {
let writes = Array::make(types.length(), 0)
let first_get = Array::make(types.length(), -1)
for idx = 0; idx < actions.length(); idx = idx + 1 {
let action = actions[idx]
match action.kind {
CLActionKind::Get =>
if first_get[action.local_idx] < 0 {
first_get[action.local_idx] = idx
}
CLActionKind::Set | CLActionKind::Tee => writes[action.local_idx] += 1
}
}
for entry_local = param_count
entry_local < types.length()
entry_local = entry_local + 1 {
if first_get[entry_local] < 0 || writes[entry_local] != 0 {
continue
}
for idx = 0; idx < first_get[entry_local]; idx = idx + 1 {
let action = actions[idx]
match action.kind {
CLActionKind::Set | CLActionKind::Tee => {
let written_local = action.local_idx
if written_local != entry_local &&
types[written_local] == types[entry_local] &&
!cl_source_is_explicit_default(action.source, types[entry_local]) {
cl_add_interference(interferences, entry_local, written_local)
}
}
_ => ()
}
}
}
}
///|
fn cl_add_plain_live_interferences(
actions : Array[CLAction],
liveness : CLLiveness,
interferences : CLBitMatrix,
candidate_visits~ : Array[Int32]? = None,
) -> Unit {
let total_locals = interferences.length()
let remaining_gets = Array::make(total_locals, 0)
for action in actions {
if action.kind is CLActionKind::Get {
remaining_gets[action.local_idx] += 1
}
}
let live = CLCfgLiveSet::new(total_locals)
for local = 0; local < total_locals; local = local + 1 {
if liveness.live_at_entry[local] {
cl_cfg_live_set_add(live, local)
}
}
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
let action = actions[action_idx]
if action.kind is CLActionKind::Get {
cl_cfg_live_set_add(live, action.local_idx)
}
for other in live.members {
if candidate_visits is Some(visits) {
visits[0] += 1
}
if other != action.local_idx {
cl_add_interference(interferences, action.local_idx, other)
}
}
match action.kind {
CLActionKind::Get => {
remaining_gets[action.local_idx] -= 1
if remaining_gets[action.local_idx] == 0 {
cl_cfg_live_set_remove(live, action.local_idx)
}
}
CLActionKind::Set | CLActionKind::Tee =>
if liveness.effective[action_idx] {
cl_cfg_live_set_add(live, action.local_idx)
} else {
cl_cfg_live_set_remove(live, action.local_idx)
}
}
}
}
///|
fn cl_copy_weights(
actions : Array[CLAction],
effective : Array[Bool],
total_locals : Int32,
) -> CLCopyWeights {
let weights = CLCopyWeights::new(total_locals)
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
if !effective[action_idx] {
continue
}
let action = actions[action_idx]
match action.source {
CLValueSource::Local(src) =>
if src >= 0 && src < total_locals && src != action.local_idx {
cl_copy_weight_add(weights, action.local_idx, src, 1)
}
_ => ()
}
}
weights
}
///|
fn cl_slot_interferes(
members : Array[Int32],
local_idx : Int32,
interferences : CLBitMatrix,
) -> Bool {
for slot_member in members {
if cl_bit_matrix_get(interferences, local_idx, slot_member) {
return true
}
}
false
}
///|
fn cl_color_with_order(
order : Array[Int32],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
weights : CLCopyWeights,
slot_visits~ : Array[Int32]? = None,
) -> CLColoring {
let total_locals = types.length()
let old_to_new = Array::make(total_locals, -1)
for idx = 0; idx < param_count; idx = idx + 1 {
old_to_new[idx] = idx
}
let slot_types : Array[@lib.ValType] = []
let slot_members : Array[Array[Int32]] = []
for idx = 0; idx < param_count; idx = idx + 1 {
slot_types.push(types[idx])
slot_members.push([idx])
}
let slot_copy_scores = Array::make(total_locals, 0)
let score_marks = Array::make(total_locals, -1)
let mut score_epoch = 0
for local_idx in order {
let ty = types[local_idx]
score_epoch += 1
let mut maximum_score = 0
for edge in weights.rows[local_idx] {
let (other, weight) = edge
let assigned_slot = old_to_new[other]
if assigned_slot >= 0 && assigned_slot < slot_types.length() {
if score_marks[assigned_slot] != score_epoch {
score_marks[assigned_slot] = score_epoch
slot_copy_scores[assigned_slot] = 0
}
slot_copy_scores[assigned_slot] += weight
if slot_copy_scores[assigned_slot] > maximum_score {
maximum_score = slot_copy_scores[assigned_slot]
}
}
}
let mut best_slot = -1
let mut best_score = -1
for slot = 0; slot < slot_types.length(); slot = slot + 1 {
if slot_visits is Some(visits) {
visits[0] += 1
}
if slot_types[slot] == ty &&
!cl_slot_interferes(slot_members[slot], local_idx, interferences) {
let score = if score_marks[slot] == score_epoch {
slot_copy_scores[slot]
} else {
0
}
if score > best_score {
best_score = score
best_slot = slot
// Earlier slots win ties. This upper bound includes every assigned
// copy weight, even slots rejected for type or interference.
if best_score == maximum_score {
break
}
}
}
}
if best_slot < 0 {
best_slot = slot_types.length()
slot_types.push(ty)
slot_members.push([])
}
old_to_new[local_idx] = best_slot
slot_members[best_slot].push(local_idx)
}
let body_slot_types : Array[@lib.ValType] = []
for slot = param_count; slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let mut removed_copies = 0
for lhs = 0; lhs < total_locals; lhs = lhs + 1 {
for edge in weights.rows[lhs] {
let (rhs, weight) = edge
if rhs > lhs && old_to_new[lhs] == old_to_new[rhs] {
removed_copies += weight
}
}
}
{ old_to_new, slot_types: body_slot_types, removed_copies, }
}
///|
fn cl_accessed_compaction_type_eligible(ty : @lib.ValType) -> Bool {
match ty {
@lib.RefTypeValType(_) => true
_ => false
}
}
///|
fn cl_coloring_accessed_slot_score(
coloring : CLColoring,
preferred : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
) -> Int32 {
let mut score = 0
for idx = param_count; idx < preferred.length(); idx = idx + 1 {
if preferred[idx] && cl_accessed_compaction_type_eligible(types[idx]) {
score += coloring.old_to_new[idx]
}
}
score
}
///|
fn cl_coloring_is_better(
candidate : CLColoring,
best : CLColoring,
preferred : Array[Bool],
retained_copy_destinations : Array[Bool],
structured_scalar_preferred : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
) -> Bool {
if candidate.removed_copies != best.removed_copies {
return candidate.removed_copies > best.removed_copies
}
if candidate.slot_types.length() != best.slot_types.length() {
return candidate.slot_types.length() < best.slot_types.length()
}
let candidate_accessed = cl_coloring_accessed_slot_score(
candidate, preferred, types, param_count,
)
let best_accessed = cl_coloring_accessed_slot_score(
best, preferred, types, param_count,
)
if candidate_accessed != best_accessed {
return candidate_accessed < best_accessed
}
let candidate_copy_destination = cl_coloring_flagged_slot_score(
candidate, retained_copy_destinations, param_count,
)
let best_copy_destination = cl_coloring_flagged_slot_score(
best, retained_copy_destinations, param_count,
)
if candidate_copy_destination != best_copy_destination {
return candidate_copy_destination < best_copy_destination
}
cl_coloring_flagged_slot_score(
candidate, structured_scalar_preferred, param_count,
) <
cl_coloring_flagged_slot_score(best, structured_scalar_preferred, param_count)
}
///|
fn cl_local_copy_degree(weights : CLCopyWeights, local_idx : Int32) -> Int32 {
cl_copy_weight_degree(weights, local_idx)
}
///|
fn cl_push_copy_weighted_order_segment(
out : Array[Int32],
weights : CLCopyWeights,
param_count : Int32,
copy_connected : Bool,
reverse : Bool,
) -> Unit {
if reverse {
let mut idx = weights.length() - 1
while idx >= param_count {
if (cl_local_copy_degree(weights, idx) > 0) == copy_connected {
out.push(idx)
}
idx -= 1
}
} else {
for idx = param_count; idx < weights.length(); idx = idx + 1 {
if (cl_local_copy_degree(weights, idx) > 0) == copy_connected {
out.push(idx)
}
}
}
}
///|
fn cl_copy_weighted_order(
weights : CLCopyWeights,
param_count : Int32,
reverse : Bool,
) -> Array[Int32] {
let out : Array[Int32] = []
// Copy-connected locals are the main coalesce-locals profitability surface.
// Let them claim compatible slots before unrelated scratch locals; otherwise
// an unrelated post-branch local can occupy a branch-carrier source slot and
// leave a size-losing cross-local copy that Binaryen removes.
cl_push_copy_weighted_order_segment(out, weights, param_count, true, reverse)
cl_push_copy_weighted_order_segment(out, weights, param_count, false, reverse)
out
}
///|
fn cl_preferred_compaction_order(
preferred : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
) -> Array[Int32] {
let out : Array[Int32] = []
// Binaryen lets accessed concrete GC-ref locals claim the earliest body slots
// even when unrelated unused ref/scalar locals appear before or after them.
// Keep this order candidate narrow: the preferred flags already require a
// direct struct.get use and multiple sets, and copy-count/slot-count scoring
// must still tie before this order can win.
for idx = param_count; idx < types.length(); idx = idx + 1 {
if preferred[idx] && cl_accessed_compaction_type_eligible(types[idx]) {
out.push(idx)
}
}
for idx = param_count; idx < types.length(); idx = idx + 1 {
if !preferred[idx] && cl_accessed_compaction_type_eligible(types[idx]) {
out.push(idx)
}
}
for idx = param_count; idx < types.length(); idx = idx + 1 {
if !cl_accessed_compaction_type_eligible(types[idx]) {
out.push(idx)
}
}
out
}
///|
fn cl_flagged_compaction_order(
preferred : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
) -> Array[Int32] {
let out : Array[Int32] = []
for idx = param_count; idx < types.length(); idx = idx + 1 {
if preferred[idx] {
out.push(idx)
}
}
for idx = param_count; idx < types.length(); idx = idx + 1 {
if !preferred[idx] {
out.push(idx)
}
}
out
}
///|
fn cl_preferred_compaction_flags(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
types : Array[@lib.ValType],
) -> Array[Bool] {
let preferred = Array::make(types.length(), false)
for idx = 0; idx + 1 < instrs.length(); idx = idx + 1 {
match (instrs[idx], instrs[idx + 1]) {
(@lib.LocalGet(local_idx), @lib.StructGet(_, _)) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < types.length() {
preferred[raw] = true
}
}
_ => ()
}
}
let direct_struct_get = preferred.copy()
let sets = cl_local_set_counts(actions, types.length())
for idx = 0; idx < types.length(); idx = idx + 1 {
preferred[idx] = direct_struct_get[idx] && sets[idx] > 1
}
for action in actions {
match action.source {
CLValueSource::Local(source) => {
let destination = action.local_idx
if source >= 0 &&
source < types.length() &&
destination >= 0 &&
destination < types.length() &&
types[source] == types[destination] &&
cl_accessed_compaction_type_eligible(types[source]) {
preferred[source] = true
preferred[destination] = true
}
}
_ => ()
}
}
preferred
}
///|
fn cl_local_set_counts(
actions : Array[CLAction],
total_locals : Int32,
) -> Array[Int32] {
let sets = Array::make(total_locals, 0)
for action in actions {
if action.local_idx >= 0 && action.local_idx < total_locals {
match action.kind {
CLActionKind::Set => sets[action.local_idx] += 1
_ => ()
}
}
}
sets
}
///|
fn cl_local_write_counts(
actions : Array[CLAction],
total_locals : Int32,
) -> Array[Int32] {
let writes = Array::make(total_locals, 0)
for action in actions {
if action.local_idx >= 0 && action.local_idx < total_locals {
match action.kind {
CLActionKind::Set | CLActionKind::Tee => writes[action.local_idx] += 1
_ => ()
}
}
}
writes
}
///|
// A copy destination that remains live across a later source overwrite cannot
// share the source's slot. A subtype-to-base copy also cannot share because this
// pass requires exact local types. Prefer either destination's lower index on
// otherwise equal colorings, matching Binaryen's deterministic orientation;
// cl_color_with_order still owns the exact-type coalescing check.
fn cl_retained_copy_destination_flags_with_visits(
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
) -> (Array[Bool], Int32) {
let preferred = Array::make(types.length(), false)
let next_write = Array::make(types.length(), -1)
let latest_get = Array::make(types.length(), -1)
let mut visited_actions = 0
let mut idx = actions.length() - 1
while idx >= 0 {
visited_actions += 1
let action = actions[idx]
match (action.kind, action.source) {
(CLActionKind::Set | CLActionKind::Tee, CLValueSource::Local(source)) => {
let destination = action.local_idx
if source >= param_count &&
destination >= param_count &&
source < types.length() &&
destination < types.length() {
if types[source] != types[destination] {
preferred[destination] = true
} else if next_write[source] >= 0 &&
latest_get[destination] > next_write[source] {
preferred[destination] = true
}
}
}
_ => ()
}
if action.local_idx >= 0 && action.local_idx < types.length() {
match action.kind {
CLActionKind::Get =>
if latest_get[action.local_idx] < 0 {
latest_get[action.local_idx] = idx
}
CLActionKind::Set | CLActionKind::Tee =>
next_write[action.local_idx] = idx
}
}
idx -= 1
}
(preferred, visited_actions)
}
///|
fn cl_retained_copy_destination_flags(
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
) -> Array[Bool] {
cl_retained_copy_destination_flags_with_visits(actions, types, param_count).0
}
///|
fn cl_structured_scalar_compaction_flags(
instrs : Array[@lib.Instruction],
actions : Array[CLAction],
types : Array[@lib.ValType],
param_count : Int32,
) -> Array[Bool] {
let preferred = Array::make(types.length(), false)
cl_mark_structured_scalar_conditions(instrs, preferred, types, param_count)
let writes = cl_local_write_counts(actions, types.length())
for idx = 0; idx < types.length(); idx = idx + 1 {
preferred[idx] = preferred[idx] && writes[idx] > 1
}
preferred
}
///|
fn cl_type_is_i32(ty : @lib.ValType) -> Bool {
ty == @lib.ValType::i32()
}
///|
fn cl_mark_structured_scalar_conditions(
instrs : Array[@lib.Instruction],
preferred : Array[Bool],
types : Array[@lib.ValType],
param_count : Int32,
) -> Unit {
for idx = 0; idx < instrs.length(); idx = idx + 1 {
if idx + 1 < instrs.length() {
match (instrs[idx], instrs[idx + 1]) {
(@lib.LocalGet(local_idx), @lib.If(_, _, _))
| (@lib.LocalGet(local_idx), @lib.BrIf(_)) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= param_count &&
raw < types.length() &&
cl_type_is_i32(types[raw]) {
preferred[raw] = true
}
}
_ => ()
}
}
match instrs[idx] {
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
cl_mark_structured_scalar_conditions(
body, preferred, types, param_count,
)
@lib.If(_, then_body, else_body) => {
cl_mark_structured_scalar_conditions(
then_body, preferred, types, param_count,
)
match else_body {
Some(body) =>
cl_mark_structured_scalar_conditions(
body, preferred, types, param_count,
)
None => ()
}
}
@lib.TryTable(_, _, @lib.Expr(body)) =>
cl_mark_structured_scalar_conditions(
body, preferred, types, param_count,
)
_ => ()
}
}
}
///|
fn cl_coloring_flagged_slot_score(
coloring : CLColoring,
preferred : Array[Bool],
param_count : Int32,
) -> Int32 {
let mut score = 0
for idx = param_count; idx < preferred.length(); idx = idx + 1 {
if preferred[idx] {
score += coloring.old_to_new[idx]
}
}
score
}
///|
fn cl_distinct_coloring_orders_with_visits(
orders : Array[Array[Int32]],
) -> (Array[Array[Int32]], Int32) {
let distinct : Array[Array[Int32]] = []
let mut visited = 0
for order in orders {
visited += 1
if !distinct.any(fn(seen) { seen == order }) {
distinct.push(order)
}
}
(distinct, visited)
}
///|
fn cl_pick_coloring(
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLBitMatrix,
weights : CLCopyWeights,
preferred : Array[Bool],
retained_copy_destinations : Array[Bool],
structured_scalar_preferred : Array[Bool],
) -> CLColoring {
let natural : Array[Int32] = []
for idx = param_count; idx < types.length(); idx = idx + 1 {
natural.push(idx)
}
let reverse : Array[Int32] = []
let mut idx = types.length() - 1
while idx >= param_count {
reverse.push(idx)
idx -= 1
}
let (orders, _) = cl_distinct_coloring_orders_with_visits([
natural,
reverse,
cl_copy_weighted_order(weights, param_count, false),
cl_copy_weighted_order(weights, param_count, true),
cl_preferred_compaction_order(preferred, types, param_count),
cl_flagged_compaction_order(retained_copy_destinations, types, param_count),
cl_flagged_compaction_order(structured_scalar_preferred, types, param_count),
])
let mut best = cl_color_with_order(
orders[0],
types,
param_count,
interferences,
weights,
)
for order_idx = 1; order_idx < orders.length(); order_idx = order_idx + 1 {
let candidate = cl_color_with_order(
orders[order_idx],
types,
param_count,
interferences,
weights,
)
if cl_coloring_is_better(
candidate, best, preferred, retained_copy_destinations, structured_scalar_preferred,
types, param_count,
) {
best = candidate
}
}
best
}
///|
fn cl_rewrite_local_idx(
idx : @lib.LocalIdx,
old_to_new : Array[Int32],
) -> @lib.LocalIdx {
let raw = cl_local_idx_raw(idx)
if raw < 0 || raw >= old_to_new.length() {
abort("coalesce-locals local remap out of range")
}
cl_local_idx_from_int(old_to_new[raw])
}
///|
fn cl_rewrite_instrs_in_place(
instrs : Array[@lib.Instruction],
old_to_new : Array[Int32],
effective : Array[Bool],
action_cursor : Array[Int32],
control_index~ : CLControlIndex? = None,
control_cursor~ : Array[Int32]? = None,
) -> Unit {
let control_index = match control_index {
Some(index) => Some(index)
None => cl_control_index_for_body(instrs, None)
}
let control_cursor = match (control_index, control_cursor) {
(Some(_), None) => Some([0])
(_, cursor) => cursor
}
let mut reachable = true
for idx = 0; idx < instrs.length(); idx = idx + 1 {
let instr = instrs[idx]
let position = match control_cursor {
Some(cursor) => cursor[0]
None => -1
}
if !reachable {
match instr {
@lib.LocalGet(local_idx) =>
instrs[idx] = @lib.Instruction::local_get(
cl_rewrite_local_idx(local_idx, old_to_new),
)
@lib.LocalSet(local_idx) =>
instrs[idx] = @lib.Instruction::local_set(
cl_rewrite_local_idx(local_idx, old_to_new),
)
@lib.LocalTee(local_idx) =>
instrs[idx] = @lib.Instruction::local_tee(
cl_rewrite_local_idx(local_idx, old_to_new),
)
_ => ()
}
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
continue
}
if control_cursor is Some(cursor) {
cursor[0] += 1
}
match instr {
@lib.Block(block_type, @lib.Expr(body)) => {
cl_rewrite_instrs_in_place(
body,
old_to_new,
effective,
action_cursor,
control_index~,
control_cursor~,
)
instrs[idx] = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
cl_rewrite_instrs_in_place(
body,
old_to_new,
effective,
action_cursor,
control_index~,
control_cursor~,
)
instrs[idx] = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
cl_rewrite_instrs_in_place(
then_body,
old_to_new,
effective,
action_cursor,
control_index~,
control_cursor~,
)
match else_body {
Some(else_instrs) =>
cl_rewrite_instrs_in_place(
else_instrs,
old_to_new,
effective,
action_cursor,
control_index~,
control_cursor~,
)
None => ()
}
instrs[idx] = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
cl_rewrite_instrs_in_place(
body,
old_to_new,
effective,
action_cursor,
control_index~,
control_cursor~,
)
instrs[idx] = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
@lib.LocalGet(local_idx) => {
action_cursor[0] += 1
instrs[idx] = @lib.Instruction::local_get(
cl_rewrite_local_idx(local_idx, old_to_new),
)
}
@lib.LocalSet(local_idx) => {
let action_idx = action_cursor[0]
action_cursor[0] += 1
let rewritten_idx = cl_rewrite_local_idx(local_idx, old_to_new)
if action_idx < effective.length() && !effective[action_idx] {
match idx > 0 {
true =>
match instrs[idx - 1] {
@lib.LocalGet(prev_idx) if prev_idx == rewritten_idx =>
instrs[idx] = @lib.Instruction::local_set(rewritten_idx)
_ => instrs[idx] = @lib.Instruction::drop()
}
false => instrs[idx] = @lib.Instruction::drop()
}
} else {
instrs[idx] = @lib.Instruction::local_set(rewritten_idx)
}
}
@lib.LocalTee(local_idx) => {
action_cursor[0] += 1
instrs[idx] = @lib.Instruction::local_tee(
cl_rewrite_local_idx(local_idx, old_to_new),
)
}
_ => ()
}
let no_fallthrough = match control_index {
Some(index) => cl_control_no_fallthrough(index.facts[position])
None => cl_instr_makes_rest_unreachable(instr)
}
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
if no_fallthrough {
reachable = false
}
}
}
///|
fn cl_instrs_read_local(
instrs : Array[@lib.Instruction],
expected : @lib.LocalIdx,
) -> Bool {
for instr in instrs {
match instr {
@lib.LocalGet(local_idx) => if local_idx == expected { return true }
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_read_local(body, expected) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_read_local(then_body, expected) {
return true
}
match else_body {
Some(body) => if cl_instrs_read_local(body, expected) { return true }
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_suffix_reads_local_before_overwrite(
instrs : Array[@lib.Instruction],
start : Int32,
expected : @lib.LocalIdx,
) -> Bool {
for idx = start; idx < instrs.length(); idx = idx + 1 {
match instrs[idx] {
@lib.LocalGet(local_idx) => if local_idx == expected { return true }
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) =>
if local_idx == expected {
// Raw operands have already run. This same-scope write kills the
// earlier value before any following read can observe it.
return false
}
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_read_local(body, expected) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_read_local(then_body, expected) {
return true
}
match else_body {
Some(body) => if cl_instrs_read_local(body, expected) { return true }
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_remove_ineffective_tees(
rewritten_instrs : Array[@lib.Instruction],
original_instrs : Array[@lib.Instruction],
effective : Array[Bool],
action_cursor : Array[Int32],
control_visits~ : Array[Int32]? = None,
control_index~ : CLControlIndex? = None,
control_cursor~ : Array[Int32]? = None,
) -> Bool {
let out : Array[@lib.Instruction] = []
let mut changed = false
// Local remapping and tee removal cannot change control transfer. Keep one
// immutable preorder index of the original body while descendants are edited.
let control_index = match control_index {
Some(index) => Some(index)
None => cl_control_index_for_body(original_instrs, control_visits)
}
let control_cursor = match (control_index, control_cursor) {
(Some(_), None) => Some([0])
(_, cursor) => cursor
}
let mut reachable = true
for idx = 0; idx < rewritten_instrs.length(); idx = idx + 1 {
// Collection and rewriting assign action ordinals only to reachable code.
let position = match control_cursor {
Some(cursor) => cursor[0]
None => -1
}
if !reachable {
out.push(rewritten_instrs[idx])
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
continue
}
let original = original_instrs[idx]
let no_fallthrough = match control_index {
Some(index) => cl_control_no_fallthrough(index.facts[position])
None =>
cl_instr_never_falls_through(
original,
instruction_visits=control_visits,
)
}
if control_cursor is Some(cursor) {
cursor[0] += 1
}
let mut rewritten = rewritten_instrs[idx]
match original {
@lib.Block(_, @lib.Expr(original_body)) =>
match rewritten {
@lib.Block(block_type, @lib.Expr(body)) => {
changed = cl_remove_ineffective_tees(
body,
original_body,
effective,
action_cursor,
control_visits~,
control_index~,
control_cursor~,
) ||
changed
rewritten = @lib.Instruction::block(
block_type,
@lib.Expr::new(body),
)
}
_ => ()
}
@lib.Loop(_, @lib.Expr(original_body)) =>
match rewritten {
@lib.Loop(block_type, @lib.Expr(body)) => {
changed = cl_remove_ineffective_tees(
body,
original_body,
effective,
action_cursor,
control_visits~,
control_index~,
control_cursor~,
) ||
changed
rewritten = @lib.Instruction::loop_(
block_type,
@lib.Expr::new(body),
)
}
_ => ()
}
@lib.If(_, original_then, original_else) =>
match rewritten {
@lib.If(block_type, then_body, else_body) => {
changed = cl_remove_ineffective_tees(
then_body,
original_then,
effective,
action_cursor,
control_visits~,
control_index~,
control_cursor~,
) ||
changed
match (else_body, original_else) {
(Some(body), Some(original_body)) =>
changed = cl_remove_ineffective_tees(
body,
original_body,
effective,
action_cursor,
control_visits~,
control_index~,
control_cursor~,
) ||
changed
_ => ()
}
rewritten = @lib.Instruction::if_(block_type, then_body, else_body)
}
_ => ()
}
@lib.TryTable(_, _, @lib.Expr(original_body)) =>
match rewritten {
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
changed = cl_remove_ineffective_tees(
body,
original_body,
effective,
action_cursor,
control_visits~,
control_index~,
control_cursor~,
) ||
changed
rewritten = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
_ => ()
}
@lib.LocalGet(_) | @lib.LocalSet(_) => action_cursor[0] += 1
@lib.LocalTee(original_local_idx) => {
let action_idx = action_cursor[0]
action_cursor[0] += 1
if action_idx >= 0 &&
action_idx < effective.length() &&
!effective[action_idx] {
if cl_suffix_reads_local_before_overwrite(
original_instrs,
idx + 1,
original_local_idx,
) {
()
} else {
changed = true
continue
}
}
}
_ => ()
}
out.push(rewritten)
if control_index is Some(index) {
control_cursor.unwrap()[0] = index.ends[position]
}
if no_fallthrough {
reachable = false
}
}
if changed {
rewritten_instrs.clear()
rewritten_instrs.append(out)
}
changed
}
///|
fn cl_remove_dropped_immutable_gets(
instrs : Array[@lib.Instruction],
writes : Array[Int32],
) -> Bool {
let out : Array[@lib.Instruction] = []
let mut changed = false
let mut idx = 0
while idx < instrs.length() {
let mut instr = instrs[idx]
match instr {
@lib.Block(block_type, @lib.Expr(body)) => {
changed = cl_remove_dropped_immutable_gets(body, writes) || changed
instr = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
changed = cl_remove_dropped_immutable_gets(body, writes) || changed
instr = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
changed = cl_remove_dropped_immutable_gets(then_body, writes) || changed
match else_body {
Some(body) =>
changed = cl_remove_dropped_immutable_gets(body, writes) || changed
None => ()
}
instr = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
changed = cl_remove_dropped_immutable_gets(body, writes) || changed
instr = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
_ => ()
}
if idx + 1 < instrs.length() {
match (instr, instrs[idx + 1]) {
(@lib.LocalGet(local_idx), @lib.Drop) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < writes.length() && writes[raw] == 0 {
out.push(@lib.Instruction::nop())
changed = true
idx += 2
continue
}
}
_ => ()
}
}
out.push(instr)
idx += 1
}
if changed {
instrs.clear()
instrs.append(out)
}
changed
}
///|
fn cl_instrs_have_branch_instruction(instrs : Array[@lib.Instruction]) -> Bool {
for instr in instrs {
if cl_instr_is_branch_instruction(instr) {
return true
}
match instr {
@lib.TryTable(_, catches, @lib.Expr(body)) =>
if !catches.is_empty() || cl_instrs_have_branch_instruction(body) {
return true
}
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
if cl_instrs_have_branch_instruction(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_branch_instruction(then_body) {
return true
}
match else_body {
Some(body) =>
if cl_instrs_have_branch_instruction(body) {
return true
}
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, delegate) => {
if delegate is Some(_) || cl_instrs_have_branch_instruction(body) {
return true
}
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
if cl_instrs_have_branch_instruction(catch_body) {
return true
}
}
}
}
_ => ()
}
}
false
}
///|
fn cl_flatten_terminal_unbranched_void_blocks(
instrs : Array[@lib.Instruction],
) -> Bool {
let out : Array[@lib.Instruction] = []
let mut changed = false
for instr in instrs {
let mut rewritten = instr
match instr {
@lib.Block(block_type, @lib.Expr(body)) => {
if cl_flatten_terminal_unbranched_void_blocks(body) {
changed = true
}
if block_type == @lib.BlockType::void_() &&
!cl_instrs_have_branch_instruction(body) {
// Flattening can expose an unconditional exit that was previously
// scoped inside the block. Finish that block-owned cleanup now so a
// second coalesce-locals run is not required, without truncating an
// unrelated parent tail merely because some nested block flattened.
ignore(cl_truncate_dead_tails(body))
out.append(body)
changed = true
continue
}
rewritten = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
if cl_flatten_terminal_unbranched_void_blocks(body) {
changed = true
}
rewritten = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
if cl_flatten_terminal_unbranched_void_blocks(then_body) {
changed = true
}
match else_body {
Some(body) =>
if cl_flatten_terminal_unbranched_void_blocks(body) {
changed = true
}
None => ()
}
rewritten = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
if cl_flatten_terminal_unbranched_void_blocks(body) {
changed = true
}
rewritten = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
_ => ()
}
out.push(rewritten)
}
if changed {
instrs.clear()
instrs.append(out)
}
changed
}
///|
fn cl_truncate_dead_tails(instrs : Array[@lib.Instruction]) -> Bool {
let mut changed = false
let out : Array[@lib.Instruction] = []
for idx = 0; idx < instrs.length(); idx = idx + 1 {
let mut instr = instrs[idx]
match instr {
@lib.Block(block_type, @lib.Expr(body)) => {
if cl_truncate_dead_tails(body) {
changed = true
}
instr = @lib.Instruction::block(block_type, @lib.Expr::new(body))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
if cl_truncate_dead_tails(body) {
changed = true
}
instr = @lib.Instruction::loop_(block_type, @lib.Expr::new(body))
}
@lib.If(block_type, then_body, else_body) => {
if cl_truncate_dead_tails(then_body) {
changed = true
}
match else_body {
Some(else_instrs) =>
if cl_truncate_dead_tails(else_instrs) {
changed = true
}
None => ()
}
instr = @lib.Instruction::if_(block_type, then_body, else_body)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
if cl_truncate_dead_tails(body) {
changed = true
}
instr = @lib.Instruction::try_table(
block_type,
catches,
@lib.Expr::new(body),
)
}
_ => ()
}
out.push(instr)
if cl_instr_makes_rest_unreachable(instr) && idx + 1 < instrs.length() {
if !cl_instr_is_terminal(instr) {
// Keep typed enclosing regions valid. Escape classification looks
// through this dead sentinel and retains the actual branch depth.
out.push(@lib.Instruction::unreachable_())
}
changed = true
break
}
}
if changed {
instrs.clear()
for instr in out {
instrs.push(instr)
}
}
changed
}
///|
fn cl_remove_redundant_copy_pairs(instrs : Array[@lib.Instruction]) -> Bool {
let mut changed = false
let out : Array[@lib.Instruction] = []
let mut idx = 0
while idx < instrs.length() {
match instrs[idx] {
@lib.Block(block_type, @lib.Expr(body)) => {
if cl_remove_redundant_copy_pairs(body) {
changed = true
}
out.push(@lib.Instruction::block(block_type, @lib.Expr::new(body)))
}
@lib.Loop(block_type, @lib.Expr(body)) => {
if cl_remove_redundant_copy_pairs(body) {
changed = true
}
out.push(@lib.Instruction::loop_(block_type, @lib.Expr::new(body)))
}
@lib.If(block_type, then_body, else_body) => {
if cl_remove_redundant_copy_pairs(then_body) {
changed = true
}
match else_body {
Some(else_instrs) =>
if cl_remove_redundant_copy_pairs(else_instrs) {
changed = true
}
None => ()
}
out.push(@lib.Instruction::if_(block_type, then_body, else_body))
}
@lib.Try(block_type, @lib.Expr(body), catches, delegate) => {
if cl_remove_redundant_copy_pairs(body) {
changed = true
}
let rewritten_catches : Array[@lib.LegacyCatch] = []
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(tag_idx, @lib.Expr(catch_body)) => {
if cl_remove_redundant_copy_pairs(catch_body) {
changed = true
}
rewritten_catches.push(
@lib.LegacyCatch::tagged(tag_idx, @lib.Expr::new(catch_body)),
)
}
@lib.LegacyCatchAll(@lib.Expr(catch_body)) => {
if cl_remove_redundant_copy_pairs(catch_body) {
changed = true
}
rewritten_catches.push(
@lib.LegacyCatch::all(@lib.Expr::new(catch_body)),
)
}
}
}
out.push(
@lib.Instruction::try_(
block_type,
@lib.Expr::new(body),
rewritten_catches,
delegate~,
),
)
}
@lib.TryTable(block_type, catches, @lib.Expr(body)) => {
if cl_remove_redundant_copy_pairs(body) {
changed = true
}
out.push(
@lib.Instruction::try_table(block_type, catches, @lib.Expr::new(body)),
)
}
@lib.LocalGet(local_idx) if idx + 1 < instrs.length() =>
match instrs[idx + 1] {
@lib.LocalSet(next_idx) if next_idx == local_idx => {
out.push(@lib.Instruction::nop())
changed = true
idx += 1
}
@lib.LocalTee(next_idx) if next_idx == local_idx => {
out.push(@lib.Instruction::local_get(local_idx))
changed = true
idx += 1
}
_ => out.push(instrs[idx])
}
@lib.Nop if idx + 1 < instrs.length() =>
match instrs[idx + 1] {
@lib.Drop => changed = true
_ => out.push(instrs[idx])
}
_ => out.push(instrs[idx])
}
idx += 1
}
if changed {
instrs.clear()
for instr in out {
instrs.push(instr)
}
}
changed
}
///|
fn cl_old_to_new_is_identity(old_to_new : Array[Int32]) -> Bool {
for idx = 0; idx < old_to_new.length(); idx = idx + 1 {
if old_to_new[idx] != idx {
return false
}
}
true
}
///|
fn cl_instrs_have_legacy_try(instrs : Array[@lib.Instruction]) -> Bool {
for instr in instrs {
match instr {
@lib.Try(_, _, _, _) => return true
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_have_legacy_try(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_legacy_try(then_body) {
return true
}
match else_body {
Some(body) => if cl_instrs_have_legacy_try(body) { return true }
None => ()
}
}
_ => ()
}
}
false
}
///|
priv struct CLLegacyDefAssignFlow {
safe : Bool
falls_through : Bool
assigned : Bool
}
///|
fn cl_legacy_flow(
safe : Bool,
falls_through : Bool,
assigned : Bool,
) -> CLLegacyDefAssignFlow {
{ safe, falls_through, assigned, }
}
///|
fn cl_legacy_merge_fallthrough(
left : CLLegacyDefAssignFlow,
right : CLLegacyDefAssignFlow,
) -> CLLegacyDefAssignFlow {
let falls_through = left.falls_through || right.falls_through
let assigned = if left.falls_through && right.falls_through {
left.assigned && right.assigned
} else if left.falls_through {
left.assigned
} else if right.falls_through {
right.assigned
} else {
false
}
cl_legacy_flow(left.safe && right.safe, falls_through, assigned)
}
///|
fn cl_legacy_definite_assignment_scan(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
assigned_at_entry : Bool,
) -> CLLegacyDefAssignFlow {
let mut assigned = assigned_at_entry
let mut idx = 0
while idx < instrs.length() {
if idx + 1 < instrs.length() {
match (instrs[idx], instrs[idx + 1]) {
(@lib.LocalGet(source_idx), @lib.LocalSet(dest_idx)) if cl_local_idx_raw(
source_idx,
) ==
source &&
cl_local_idx_raw(dest_idx) == dest => {
assigned = true
idx += 2
continue
}
_ => ()
}
}
let instr = instrs[idx]
match instr {
@lib.LocalGet(local_idx) if cl_local_idx_raw(local_idx) == dest =>
if !assigned {
return cl_legacy_flow(false, true, assigned)
}
@lib.Block(_, @lib.Expr(body)) => {
let body_flow = cl_legacy_definite_assignment_scan(
body, source, dest, assigned,
)
if !body_flow.safe {
return body_flow
}
assigned = if cl_instrs_have_branch_instruction(body) {
assigned && body_flow.assigned
} else if body_flow.falls_through {
body_flow.assigned
} else {
assigned
}
}
@lib.Loop(_, @lib.Expr(body)) | @lib.TryTable(_, _, @lib.Expr(body)) => {
let body_flow = cl_legacy_definite_assignment_scan(
body, source, dest, assigned,
)
if !body_flow.safe {
return body_flow
}
assigned = assigned && body_flow.assigned
}
@lib.If(_, then_body, else_body) => {
let then_flow = cl_legacy_definite_assignment_scan(
then_body, source, dest, assigned,
)
let else_flow = match else_body {
Some(body) =>
cl_legacy_definite_assignment_scan(body, source, dest, assigned)
None => cl_legacy_flow(true, true, assigned)
}
let merged = cl_legacy_merge_fallthrough(then_flow, else_flow)
if !merged.safe || !merged.falls_through {
return merged
}
assigned = merged.assigned
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
let mut has_branch_exit = cl_instrs_have_branch_instruction(body)
let mut merged = cl_legacy_definite_assignment_scan(
body, source, dest, assigned,
)
for catch_ in catches {
let catch_body = match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
}
has_branch_exit = has_branch_exit ||
cl_instrs_have_branch_instruction(catch_body)
// A protected-body throw may enter a catch before a copy in the body
// executes. Only facts from before the try dominate catch entry.
let catch_flow = cl_legacy_definite_assignment_scan(
catch_body, source, dest, assigned,
)
merged = cl_legacy_merge_fallthrough(merged, catch_flow)
}
if !merged.safe || !merged.falls_through {
return merged
}
assigned = if has_branch_exit {
assigned && merged.assigned
} else {
merged.assigned
}
}
_ =>
if cl_instr_is_terminal(instr) {
return cl_legacy_flow(true, false, assigned)
}
}
idx += 1
}
cl_legacy_flow(true, true, assigned)
}
///|
fn cl_legacy_copy_dominates_all_reads(
instrs : Array[@lib.Instruction],
source : Int32,
dest : Int32,
) -> Bool {
cl_legacy_definite_assignment_scan(instrs, source, dest, false).safe
}
///|
fn cl_mark_legacy_copy_aliases(
instrs : Array[@lib.Instruction],
alias_source : Array[Int32],
) -> Unit {
let mut idx = 0
while idx < instrs.length() {
if idx + 1 < instrs.length() {
match (instrs[idx], instrs[idx + 1]) {
(@lib.LocalGet(source_idx), @lib.LocalSet(dest_idx)) => {
let source = cl_local_idx_raw(source_idx)
let dest = cl_local_idx_raw(dest_idx)
if source >= 0 &&
source < alias_source.length() &&
dest >= 0 &&
dest < alias_source.length() &&
source != dest {
alias_source[dest] = source
}
}
_ => ()
}
}
match instrs[idx] {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
cl_mark_legacy_copy_aliases(body, alias_source)
@lib.If(_, then_body, else_body) => {
cl_mark_legacy_copy_aliases(then_body, alias_source)
match else_body {
Some(body) => cl_mark_legacy_copy_aliases(body, alias_source)
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
cl_mark_legacy_copy_aliases(body, alias_source)
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
cl_mark_legacy_copy_aliases(catch_body, alias_source)
}
}
}
_ => ()
}
idx += 1
}
}
///|
fn cl_rewrite_legacy_func_safe(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, @lib.Expr(original_instrs)) = func
let types = cl_all_local_types(params, body_locals)
let gets = Array::make(types.length(), 0)
let sets = Array::make(types.length(), 0)
let tees = Array::make(types.length(), 0)
cl_count_syntactic_local_accesses(original_instrs, gets, sets, tees)
let alias_source = Array::make(types.length(), -1)
cl_mark_legacy_copy_aliases(original_instrs, alias_source)
for dest = params.length(); dest < alias_source.length(); dest = dest + 1 {
let source = alias_source[dest]
if source >= 0 &&
!cl_legacy_copy_dominates_all_reads(original_instrs, source, dest) {
alias_source[dest] = -1
}
}
let old_to_new = Array::make(types.length(), -1)
let slot_types : Array[@lib.ValType] = []
for idx = 0; idx < params.length(); idx = idx + 1 {
old_to_new[idx] = idx
slot_types.push(types[idx])
}
let mut changed = false
for idx = params.length(); idx < types.length(); idx = idx + 1 {
let source = alias_source[idx]
let source_writes = if source >= 0 && source < types.length() {
sets[source] + tees[source]
} else {
-1
}
let mut slot = -1
if sets[idx] == 1 &&
tees[idx] == 0 &&
source >= 0 &&
source < idx &&
source_writes == 0 &&
types[source] == types[idx] &&
old_to_new[source] >= 0 {
slot = old_to_new[source]
} else if gets[idx] + sets[idx] + tees[idx] == 0 {
for candidate = 0
candidate < slot_types.length()
candidate = candidate + 1 {
if slot_types[candidate] == types[idx] {
slot = candidate
break
}
}
}
if slot < 0 {
slot = slot_types.length()
slot_types.push(types[idx])
}
old_to_new[idx] = slot
changed = changed || slot != idx
}
let body_slot_types : Array[@lib.ValType] = []
for slot = params.length(); slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let rewritten_instrs = cl_deep_copy_instrs(original_instrs)
cl_rewrite_all_local_idxs_in_place(rewritten_instrs, old_to_new)
let cleanup_changed = cl_remove_redundant_copy_pairs(rewritten_instrs)
let rewritten_locals = @lib.Locals::from_types(body_slot_types)
if !changed && !cleanup_changed && rewritten_locals == body_locals {
{ func, changed: false, }
} else {
{
func: @lib.Func::new(rewritten_locals, @lib.Expr::new(rewritten_instrs)),
changed: true,
}
}
}
///|
fn cl_rewrite_linear_copy_chain_fast(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite? {
let @lib.Func(body_locals, @lib.Expr(instrs)) = func
let types = cl_all_local_types(params, body_locals)
let alias_source = Array::make(types.length(), -1)
let seen = Array::make(types.length(), false)
let mut alias_count = 0
let mut idx = 0
while idx < instrs.length() {
match instrs[idx] {
@lib.LocalGet(source_idx) if idx + 1 < instrs.length() => {
let source = cl_local_idx_raw(source_idx)
match instrs[idx + 1] {
@lib.LocalSet(dest_idx) => {
let dest = cl_local_idx_raw(dest_idx)
if source < 0 ||
source >= types.length() ||
dest < params.length() ||
dest >= types.length() ||
source >= dest ||
seen[dest] ||
types[source] != types[dest] {
return None
}
alias_source[dest] = source
alias_count += 1
seen[source] = true
seen[dest] = true
idx += 2
continue
}
_ => if source >= 0 && source < seen.length() { seen[source] = true }
}
}
@lib.LocalGet(source_idx) => {
let source = cl_local_idx_raw(source_idx)
if source < 0 || source >= seen.length() {
return None
}
seen[source] = true
}
@lib.Drop | @lib.Nop => ()
_ => return None
}
idx += 1
}
if alias_count == 0 {
return None
}
let old_to_new = Array::make(types.length(), -1)
let slot_types : Array[@lib.ValType] = []
for local_idx = 0; local_idx < params.length(); local_idx = local_idx + 1 {
old_to_new[local_idx] = local_idx
slot_types.push(types[local_idx])
}
for local_idx = params.length()
local_idx < types.length()
local_idx = local_idx + 1 {
// Copy-chain sources are required to precede their destinations, so the
// source's final slot is already known. Reusing it directly avoids walking
// the full alias chain once per local (quadratic on long lowered chains).
let source = alias_source[local_idx]
if source >= 0 && source < local_idx && old_to_new[source] >= 0 {
old_to_new[local_idx] = old_to_new[source]
} else {
old_to_new[local_idx] = slot_types.length()
slot_types.push(types[local_idx])
}
}
let body_slot_types : Array[@lib.ValType] = []
for slot = params.length(); slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let rewritten_instrs : Array[@lib.Instruction] = Array::new(
capacity=instrs.length(),
)
let mut rewrite_idx = 0
while rewrite_idx < instrs.length() {
match instrs[rewrite_idx] {
@lib.LocalGet(source_idx) if rewrite_idx + 1 < instrs.length() =>
match instrs[rewrite_idx + 1] {
@lib.LocalSet(dest_idx) => {
let source = cl_local_idx_raw(source_idx)
let dest = cl_local_idx_raw(dest_idx)
let rewritten_source = old_to_new[source]
let rewritten_dest = old_to_new[dest]
if rewritten_source == rewritten_dest {
// Match the general cleanup and Binaryen's direct pass shape.
rewritten_instrs.push(@lib.Instruction::nop())
} else {
rewritten_instrs.push(
@lib.Instruction::local_get(
cl_local_idx_from_int(rewritten_source),
),
)
rewritten_instrs.push(
@lib.Instruction::local_set(
cl_local_idx_from_int(rewritten_dest),
),
)
}
rewrite_idx += 2
continue
}
_ =>
rewritten_instrs.push(
@lib.Instruction::local_get(
cl_local_idx_from_int(old_to_new[cl_local_idx_raw(source_idx)]),
),
)
}
@lib.LocalGet(source_idx) =>
rewritten_instrs.push(
@lib.Instruction::local_get(
cl_local_idx_from_int(old_to_new[cl_local_idx_raw(source_idx)]),
),
)
other => rewritten_instrs.push(other)
}
rewrite_idx += 1
}
Some({
func: @lib.Func::new(
@lib.Locals::from_types(body_slot_types),
@lib.Expr::new(rewritten_instrs),
),
changed: true,
})
}
///|
fn cl_rewrite_all_unused_func(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite? {
let @lib.Func(body_locals, body) = func
let types = cl_all_local_types(params, body_locals)
let @lib.Expr(instrs) = body
let accessed = Array::make(types.length(), false)
let read = Array::make(types.length(), false)
cl_mark_syntactic_local_accesses(instrs, accessed, read)
for idx = params.length(); idx < accessed.length(); idx = idx + 1 {
if accessed[idx] {
return None
}
}
let old_to_new = Array::make(types.length(), -1)
let slot_types : Array[@lib.ValType] = []
for idx = 0; idx < params.length(); idx = idx + 1 {
old_to_new[idx] = idx
slot_types.push(types[idx])
}
let mut changed = false
for idx = params.length(); idx < types.length(); idx = idx + 1 {
let mut slot = -1
for candidate = 0
candidate < slot_types.length()
candidate = candidate + 1 {
if slot_types[candidate] == types[idx] {
slot = candidate
break
}
}
if slot < 0 {
slot = slot_types.length()
slot_types.push(types[idx])
}
old_to_new[idx] = slot
changed = changed || slot != idx
}
let body_slot_types : Array[@lib.ValType] = []
for slot = params.length(); slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let rewritten_locals = @lib.Locals::from_types(body_slot_types)
let rewritten_instrs = cl_deep_copy_instrs(instrs)
let flattened_control = cl_flatten_terminal_unbranched_void_blocks(
rewritten_instrs,
)
let truncated_tail = cl_truncate_dead_tails(rewritten_instrs)
let control_changed = flattened_control || truncated_tail
if !changed && !control_changed && rewritten_locals == body_locals {
Some({ func, changed: false, })
} else {
Some({
func: @lib.Func::new(rewritten_locals, @lib.Expr::new(rewritten_instrs)),
changed: true,
})
}
}
///|
fn cl_remove_linear_dead_tees(
instrs : Array[@lib.Instruction],
total_locals : Int32,
) -> Bool {
if cl_instrs_have_structured_control(instrs) {
return false
}
let live = Array::make(total_locals, false)
let reversed : Array[@lib.Instruction] = []
let mut changed = false
let mut idx = instrs.length() - 1
while idx >= 0 {
let instr = instrs[idx]
match instr {
@lib.LocalGet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < live.length() {
live[raw] = true
}
}
@lib.LocalSet(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < live.length() {
live[raw] = false
}
}
@lib.LocalTee(local_idx) => {
let raw = cl_local_idx_raw(local_idx)
if raw >= 0 && raw < live.length() {
if !live[raw] {
changed = true
idx -= 1
continue
}
live[raw] = false
}
}
_ => ()
}
reversed.push(instr)
idx -= 1
}
if changed {
instrs.clear()
let mut out_idx = reversed.length() - 1
while out_idx >= 0 {
instrs.push(reversed[out_idx])
out_idx -= 1
}
}
changed
}
///|
fn cl_instrs_local_tee_count(instrs : Array[@lib.Instruction]) -> Int32 {
let mut count = 0
for instr in instrs {
match instr {
@lib.LocalTee(_) => count += 1
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
count += cl_instrs_local_tee_count(body)
@lib.If(_, then_body, else_body) => {
count += cl_instrs_local_tee_count(then_body)
match else_body {
Some(body) => count += cl_instrs_local_tee_count(body)
None => ()
}
}
_ => ()
}
}
count
}
///|
fn cl_instrs_have_local_tee(instrs : Array[@lib.Instruction]) -> Bool {
for instr in instrs {
match instr {
@lib.LocalTee(_) => return true
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_have_local_tee(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_local_tee(then_body) {
return true
}
match else_body {
Some(body) => if cl_instrs_have_local_tee(body) { return true }
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
if cl_instrs_have_local_tee(body) {
return true
}
for catch_ in catches {
match catch_ {
@lib.LegacyCatch(_, @lib.Expr(catch_body))
| @lib.LegacyCatchAll(@lib.Expr(catch_body)) =>
if cl_instrs_have_local_tee(catch_body) {
return true
}
}
}
}
_ => ()
}
}
false
}
///|
fn cl_func_may_have_coalesce_candidate(
body_locals : @lib.Locals,
instrs : Array[@lib.Instruction],
) -> Bool {
body_locals.length() > 0 || cl_instrs_have_local_tee(instrs)
}
///|
test "coalesce-locals preflight skips zero-local functions without tee cleanup" {
assert_false(
cl_func_may_have_coalesce_candidate(@lib.Locals::empty(), [
@lib.Instruction::local_get(@lib.LocalIdx::new(0U)),
]),
)
assert_true(
cl_func_may_have_coalesce_candidate(@lib.Locals::empty(), [
@lib.Instruction::block(
@lib.BlockType::void_(),
@lib.Expr::new([
@lib.Instruction::i32_const(@lib.I32(1)),
@lib.Instruction::local_tee(@lib.LocalIdx::new(0U)),
@lib.Instruction::drop(),
]),
),
]),
)
assert_true(
cl_func_may_have_coalesce_candidate(
@lib.Locals::single(1U, @lib.ValType::i32()),
[],
),
)
}
///|
fn cl_cleanup_never_read_tees(
rewrite : CLFuncRewrite,
param_count : Int32,
) -> CLFuncRewrite {
let @lib.Func(locals, @lib.Expr(instrs)) = rewrite.func
if !cl_instrs_have_local_tee(instrs) {
return rewrite
}
let total_locals = param_count + locals.length()
let gets = Array::make(total_locals, 0)
let sets = Array::make(total_locals, 0)
let tees = Array::make(total_locals, 0)
cl_count_syntactic_local_accesses(instrs, gets, sets, tees)
// An unchanged rewrite still borrows its caller's body. Structured bodies
// have no linear dead-tee cleanup, so avoid copying when every tee is read.
let mut has_unread_tee = false
for local_id = 0; local_id < total_locals; local_id = local_id + 1 {
if gets[local_id] == 0 && tees[local_id] > 0 {
has_unread_tee = true
break
}
}
if !has_unread_tee && cl_instrs_have_structured_control(instrs) {
return rewrite
}
let instrs = if rewrite.changed {
instrs
} else {
cl_deep_copy_instrs(instrs)
}
let unread_changed = cl_remove_unread_local_tees(instrs, gets)
let dead_tee_changed = cl_remove_linear_dead_tees(instrs, total_locals)
if unread_changed || dead_tee_changed {
{ func: @lib.Func::new(locals, @lib.Expr::new(instrs)), changed: true, }
} else {
rewrite
}
}
///|
fn cl_should_use_dense_tee_structured_intervals(
body_local_count : Int32,
instrs : Array[@lib.Instruction],
) -> Bool {
if body_local_count <= 0 || body_local_count > 512 {
return false
}
if !cl_instrs_have_structured_control(instrs) ||
cl_instrs_have_loop_control(instrs) ||
cl_instrs_have_legacy_try(instrs) {
return false
}
let tee_count = cl_instrs_local_tee_count(instrs)
tee_count >= 16 || (body_local_count >= 24 && tee_count >= 8)
}
///|
fn cl_cfg_hot_region_slot(op : @ir.HotOp, slot : Int32) -> Bool {
match op {
@ir.HotOp::Block | @ir.HotOp::Loop => true
@ir.HotOp::If => slot == 1 || slot == 2
@ir.HotOp::Try | @ir.HotOp::TryTable => slot == 0 || slot == 1
_ => false
}
}
///|
priv struct CLCfgBlockActions {
actions : Array[CLAction]
node_ids : Array[@ir.NodeId]
}
///|
fn cl_cfg_collect_block_node_actions(
func : @ir.HotFunc,
cfg : @ir.HotCfg,
node_id : @ir.NodeId,
block_id : @ir.BlockId,
seen_stamps : Array[Int32],
actions : Array[CLAction],
action_node_ids : Array[@ir.NodeId],
) -> Unit {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
return
}
let node = @ir.hot_node_get(func, node_id)
if !cfg.operands_expanded {
match @ir.cfg_block_for_node(cfg, node_id) {
Some(owner) if owner != block_id => return
_ => ()
}
if seen_stamps[node_id] == block_id {
return
}
seen_stamps[node_id] = block_id
for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
if cl_cfg_hot_region_slot(node.op, slot) {
continue
}
let child_id = @ir.hot_child_get(func, node_id, slot)
if child_id < 0 || !@ir.hot_node_is_live(func, child_id) {
continue
}
cl_cfg_collect_block_node_actions(
func, cfg, child_id, block_id, seen_stamps, actions, action_node_ids,
)
}
}
let action = match node.op {
@ir.HotOp::LocalGet =>
Some({
kind: CLActionKind::Get,
local_idx: node.imm0,
source: CLValueSource::Unique,
})
@ir.HotOp::LocalSet =>
Some({
kind: CLActionKind::Set,
local_idx: node.imm0,
source: CLValueSource::Unique,
})
@ir.HotOp::LocalTee =>
Some({
kind: CLActionKind::Tee,
local_idx: node.imm0,
source: CLValueSource::Unique,
})
_ => None
}
match action {
Some(action) => {
actions.push(action)
action_node_ids.push(node_id)
}
None => ()
}
}
///|
fn cl_cfg_collect_block_actions(
func : @ir.HotFunc,
cfg : @ir.HotCfg,
) -> Array[CLCfgBlockActions] {
let out : Array[CLCfgBlockActions] = []
let seen_stamps = if cfg.operands_expanded {
[]
} else {
Array::make(@ir.hot_node_count(func), -1)
}
for block_id = 0; block_id < @ir.cfg_block_count(cfg); block_id = block_id + 1 {
let actions : Array[CLAction] = []
let node_ids : Array[@ir.NodeId] = []
for node_id in @ir.cfg_block_get(cfg, block_id).nodes {
cl_cfg_collect_block_node_actions(
func, cfg, node_id, block_id, seen_stamps, actions, node_ids,
)
}
out.push({ actions, node_ids, })
}
out
}
///|
priv struct CLCfgSparseInterferences {
rows : Array[@bitset.BitSet]
}
///|
fn CLCfgSparseInterferences::new(
total_locals : Int32,
) -> CLCfgSparseInterferences {
let rows : Array[@bitset.BitSet] = []
for _ in 0.. Unit {
if lhs == rhs ||
lhs < 0 ||
rhs < 0 ||
lhs >= interferences.rows.length() ||
rhs >= interferences.rows.length() {
return
}
interferences.rows[lhs][rhs] = true
interferences.rows[rhs][lhs] = true
}
///|
fn cl_cfg_sparse_interferes(
interferences : CLCfgSparseInterferences,
lhs : Int32,
rhs : Int32,
) -> Bool {
lhs >= 0 &&
rhs >= 0 &&
lhs < interferences.rows.length() &&
rhs < interferences.rows.length() &&
interferences.rows[lhs][rhs]
}
///|
fn cl_cfg_sparse_add_live_member_interferences(
interferences : CLCfgSparseInterferences,
live_members : Array[Int32],
) -> Int32 {
// Three to fifteen members used pair insertion even for a single word.
// Validate the selected row shapes before any update; noncanonical private
// rows retain the original checked pair path and error/update ordering.
if live_members.length() >= 3 && live_members.length() < 16 {
let size = interferences.rows.length()
if size <= 64 {
let mut mask = 0UL
let mut compatible = true
for member in live_members {
if member >= 0 && member < size {
let row = interferences.rows[member]
if row.size != size || row.words.length() != 1 {
compatible = false
break
}
mask = mask | (1UL << member)
}
}
if compatible {
for member in live_members {
if member >= 0 && member < size {
let row = interferences.rows[member]
// Pair insertion never writes the diagonal. Excluding this bit
// preserves it, including preexisting bits and duplicate members.
let additions = mask & UInt64::lnot(1UL << member)
row.words[0] = row.words[0] | additions
}
}
return 0
}
}
}
// Sparse small sets avoid allocating a mask. Larger cliques update each
// valid row a word at a time; source membership order does not affect bits.
if live_members.length() >= 16 {
let size = interferences.rows.length()
let mask = @bitset.BitSet::new(size)
let words : Array[Int32] = []
for member in live_members {
if member >= 0 && member < size {
let word = member / 64
if mask.words[word] == 0UL {
words.push(word)
}
mask[member] = true
}
}
for member in live_members {
if member >= 0 && member < size {
let row = interferences.rows[member]
for word in words {
row.words[word] = row.words[word] | mask.words[word]
}
row[member] = false
}
}
return 0
}
let mut pair_checks = 0
for lhs_idx = 0; lhs_idx < live_members.length(); lhs_idx = lhs_idx + 1 {
for rhs_idx = lhs_idx + 1
rhs_idx < live_members.length()
rhs_idx = rhs_idx + 1 {
pair_checks += 1
cl_cfg_sparse_add_interference(
interferences,
live_members[lhs_idx],
live_members[rhs_idx],
)
}
}
pair_checks
}
///|
priv struct CLCfgLiveSet {
live : Array[Bool]
members : Array[Int32]
positions : Array[Int32]
}
///|
fn CLCfgLiveSet::new(total_locals : Int32) -> CLCfgLiveSet {
{
live: Array::make(total_locals, false),
members: [],
positions: Array::make(total_locals, -1),
}
}
///|
fn cl_cfg_live_set_add(live : CLCfgLiveSet, local_idx : Int32) -> Unit {
if local_idx < 0 || local_idx >= live.live.length() || live.live[local_idx] {
return
}
live.live[local_idx] = true
live.positions[local_idx] = live.members.length()
live.members.push(local_idx)
}
///|
fn cl_cfg_live_set_remove(live : CLCfgLiveSet, local_idx : Int32) -> Unit {
if local_idx < 0 || local_idx >= live.live.length() || !live.live[local_idx] {
return
}
let position = live.positions[local_idx]
let last = live.members.pop().unwrap()
if position < live.members.length() {
live.members[position] = last
live.positions[last] = position
}
live.positions[local_idx] = -1
live.live[local_idx] = false
}
///|
fn cl_cfg_live_set_from_liveness(
liveness : @ir.HotLiveness,
block_id : @ir.BlockId,
total_locals : Int32,
live_in : Bool,
reuse~ : CLCfgLiveSet? = None,
builds~ : Array[Int32]? = None,
visits~ : Array[Int32]? = None,
) -> CLCfgLiveSet {
let live = match reuse {
Some(live) if live.live.length() == total_locals => {
for local_idx in live.members {
live.live[local_idx] = false
live.positions[local_idx] = -1
}
live.members.clear()
live
}
_ => {
match builds {
Some(count) => count[0] += 1
None => ()
}
CLCfgLiveSet::new(total_locals)
}
}
let bits = if live_in {
@ir.live_in(liveness, block_id)
} else {
@ir.live_out(liveness, block_id)
}
@ir.bitset_for_each_set_bit(bits, fn(local_idx) {
match visits {
Some(count) => count[0] += 1
None => ()
}
cl_cfg_live_set_add(live, local_idx)
})
live
}
///|
priv struct CLCfgSparseWeights {
rows : Array[Array[(Int32, Int32)]]
row_positions : Array[Array[Int32]?]
}
///|
fn CLCfgSparseWeights::new(total_locals : Int32) -> CLCfgSparseWeights {
let rows : Array[Array[(Int32, Int32)]] = []
for _ in 0.. Unit {
let row = weights.rows[lhs]
let positions = match weights.row_positions[lhs] {
Some(positions) => Some(positions)
None =>
if row.length() < 8 {
None
} else {
let positions = Array::make(weights.rows.length(), -1)
for idx = 0; idx < row.length(); idx = idx + 1 {
positions[row[idx].0] = idx
}
weights.row_positions[lhs] = Some(positions)
Some(positions)
}
}
match positions {
Some(positions) => {
let idx = positions[rhs]
if idx >= 0 {
let (other, weight) = row[idx]
row[idx] = (other, weight + 1)
return
}
positions[rhs] = row.length()
row.push((rhs, 1))
return
}
None => ()
}
for idx = 0; idx < row.length(); idx = idx + 1 {
let (other, weight) = row[idx]
if other == rhs {
row[idx] = (other, weight + 1)
return
}
}
row.push((rhs, 1))
}
///|
fn cl_cfg_sparse_weight_add(
weights : CLCfgSparseWeights,
lhs : Int32,
rhs : Int32,
) -> Unit {
if lhs == rhs ||
lhs < 0 ||
rhs < 0 ||
lhs >= weights.rows.length() ||
rhs >= weights.rows.length() {
return
}
cl_cfg_sparse_weight_add_one(weights, lhs, rhs)
cl_cfg_sparse_weight_add_one(weights, rhs, lhs)
}
///|
fn cl_cfg_sparse_copy_weights(
actions : Array[CLAction],
effective : Array[Bool],
total_locals : Int32,
) -> CLCfgSparseWeights {
let weights = CLCfgSparseWeights::new(total_locals)
for action_idx = 0; action_idx < actions.length(); action_idx = action_idx + 1 {
if !effective[action_idx] {
continue
}
let action = actions[action_idx]
match action.source {
CLValueSource::Local(source) =>
cl_cfg_sparse_weight_add(weights, action.local_idx, source)
_ => ()
}
}
weights
}
///|
fn cl_cfg_sparse_slot_interferes(
members : Array[Int32],
local_idx : Int32,
interferences : CLCfgSparseInterferences,
query_steps~ : Array[Int32]? = None,
) -> Bool {
for slot_member in members {
match query_steps {
Some(count) => count[0] += 1
None => ()
}
if cl_cfg_sparse_interferes(interferences, local_idx, slot_member) {
return true
}
}
false
}
///|
fn cl_cfg_sparse_slot_copy_score(
members : Array[Int32],
local_idx : Int32,
weight_values : Array[Int32],
weight_marks : Array[Int32],
) -> Int32 {
let mut score = 0
for slot_member in members {
if weight_marks[slot_member] == local_idx {
score += weight_values[slot_member]
}
}
score
}
///|
fn cl_cfg_sparse_color_with_order(
order : Array[Int32],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLCfgSparseInterferences,
weights : CLCfgSparseWeights,
query_steps~ : Array[Int32]? = None,
) -> CLColoring {
// Small functions retain the compact member-based path. Larger rows scatter
// conflicts and copy weights by assigned slot once for each source local.
if types.length() < 64 {
return cl_cfg_sparse_color_members(
order,
types,
param_count,
interferences,
weights,
query_steps~,
)
}
let old_to_new = Array::make(types.length(), -1)
let slot_types : Array[@lib.ValType] = []
for idx in 0.. count[0] += 1
None => ()
}
let mut word = words[word_idx]
while word != 0UL {
let other = word_idx * 64 + word.ctz()
if other < old_to_new.length() {
let slot = old_to_new[other]
if slot >= 0 {
forbidden[slot] = local_idx
}
}
word = word & (word - 1UL)
}
}
let mut max_score = 0
for edge in weights.rows[local_idx] {
let (other, weight) = edge
let slot = old_to_new[other]
if slot >= 0 {
if score_marks[slot] != local_idx {
score_marks[slot] = local_idx
scores[slot] = 0
}
scores[slot] += weight
if scores[slot] > max_score {
max_score = scores[slot]
}
}
}
let mut best_slot = -1
let mut best_score = -1
for slot in 0.. count[0] += 1
None => ()
}
if slot_types[slot] == types[local_idx] && forbidden[slot] != local_idx {
let score = if score_marks[slot] == local_idx {
scores[slot]
} else {
0
}
if score > best_score {
best_score = score
best_slot = slot
// Earlier slots win equal scores. No later slot can improve on the
// maximum assigned copy weight, including the common zero-weight row.
if best_score == max_score {
break
}
}
}
}
if best_slot < 0 {
best_slot = slot_types.length()
slot_types.push(types[local_idx])
}
old_to_new[local_idx] = best_slot
}
let body_slot_types : Array[@lib.ValType] = []
for slot in param_count.. lhs && old_to_new[lhs] == old_to_new[rhs] {
removed_copies += weight
}
}
}
{ old_to_new, slot_types: body_slot_types, removed_copies, }
}
///|
fn cl_cfg_sparse_color_members(
order : Array[Int32],
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLCfgSparseInterferences,
weights : CLCfgSparseWeights,
query_steps~ : Array[Int32]? = None,
) -> CLColoring {
let old_to_new = Array::make(types.length(), -1)
let slot_types : Array[@lib.ValType] = []
let slot_members : Array[Array[Int32]] = []
for idx = 0; idx < param_count; idx = idx + 1 {
old_to_new[idx] = idx
slot_types.push(types[idx])
slot_members.push([idx])
}
let weight_values = Array::make(types.length(), 0)
let weight_marks = Array::make(types.length(), -1)
for local_idx in order {
for edge in weights.rows[local_idx] {
let (other, weight) = edge
weight_values[other] = weight
weight_marks[other] = local_idx
}
let mut best_slot = -1
let mut best_score = -1
for slot = 0; slot < slot_types.length(); slot = slot + 1 {
if slot_types[slot] == types[local_idx] &&
!cl_cfg_sparse_slot_interferes(
slot_members[slot],
local_idx,
interferences,
query_steps~,
) {
let score = cl_cfg_sparse_slot_copy_score(
slot_members[slot],
local_idx,
weight_values,
weight_marks,
)
if score > best_score {
best_score = score
best_slot = slot
// An empty weight row gives every admissible slot score zero.
// Earlier slots win ties, so later slots cannot improve this choice.
if best_score == 0 && weights.rows[local_idx].length() == 0 {
break
}
}
}
}
if best_slot < 0 {
best_slot = slot_types.length()
slot_types.push(types[local_idx])
slot_members.push([])
}
old_to_new[local_idx] = best_slot
slot_members[best_slot].push(local_idx)
}
let body_slot_types : Array[@lib.ValType] = []
for slot = param_count; slot < slot_types.length(); slot = slot + 1 {
body_slot_types.push(slot_types[slot])
}
let mut removed_copies = 0
for lhs = 0; lhs < weights.rows.length(); lhs = lhs + 1 {
for edge in weights.rows[lhs] {
let (rhs, weight) = edge
if rhs > lhs && old_to_new[lhs] == old_to_new[rhs] {
removed_copies += weight
}
}
}
{ old_to_new, slot_types: body_slot_types, removed_copies, }
}
///|
fn cl_cfg_sparse_copy_degree(
weights : CLCfgSparseWeights,
local_idx : Int32,
) -> Int32 {
let mut degree = 0
for edge in weights.rows[local_idx] {
let (_, weight) = edge
degree += weight
}
degree
}
///|
fn cl_cfg_sparse_push_copy_order_segment(
out : Array[Int32],
weights : CLCfgSparseWeights,
param_count : Int32,
copy_connected : Bool,
reverse : Bool,
) -> Unit {
if reverse {
let mut idx = weights.rows.length() - 1
while idx >= param_count {
if (cl_cfg_sparse_copy_degree(weights, idx) > 0) == copy_connected {
out.push(idx)
}
idx -= 1
}
} else {
for idx = param_count; idx < weights.rows.length(); idx = idx + 1 {
if (cl_cfg_sparse_copy_degree(weights, idx) > 0) == copy_connected {
out.push(idx)
}
}
}
}
///|
fn cl_cfg_sparse_copy_order(
weights : CLCfgSparseWeights,
param_count : Int32,
reverse : Bool,
) -> Array[Int32] {
let out : Array[Int32] = []
cl_cfg_sparse_push_copy_order_segment(
out, weights, param_count, true, reverse,
)
cl_cfg_sparse_push_copy_order_segment(
out, weights, param_count, false, reverse,
)
out
}
///|
fn cl_cfg_sparse_pick_coloring(
types : Array[@lib.ValType],
param_count : Int32,
interferences : CLCfgSparseInterferences,
weights : CLCfgSparseWeights,
) -> CLColoring {
let natural : Array[Int32] = []
for idx = param_count; idx < types.length(); idx = idx + 1 {
natural.push(idx)
}
let reverse : Array[Int32] = []
let mut idx = types.length() - 1
while idx >= param_count {
reverse.push(idx)
idx -= 1
}
let none_preferred = Array::make(types.length(), false)
let mut best = cl_cfg_sparse_color_with_order(
natural, types, param_count, interferences, weights,
)
for
order in [
reverse,
cl_cfg_sparse_copy_order(weights, param_count, false),
cl_cfg_sparse_copy_order(weights, param_count, true),
] {
let candidate = cl_cfg_sparse_color_with_order(
order, types, param_count, interferences, weights,
)
if cl_coloring_is_better(
candidate, best, none_preferred, none_preferred, none_preferred, types, param_count,
) {
best = candidate
}
}
best
}
///|
fn cl_cfg_compute_interferences(
cfg : @ir.HotCfg,
liveness : @ir.HotLiveness,
block_actions : Array[CLCfgBlockActions],
total_locals : Int32,
param_count : Int32,
live_set_builds~ : Array[Int32]? = None,
live_member_visits~ : Array[Int32]? = None,
) -> (CLCfgSparseInterferences, Array[@ir.NodeId], Array[@ir.NodeId]) {
let interferences = CLCfgSparseInterferences::new(total_locals)
for lhs = 0; lhs < param_count; lhs = lhs + 1 {
for rhs = lhs + 1; rhs < param_count; rhs = rhs + 1 {
cl_cfg_sparse_add_interference(interferences, lhs, rhs)
}
}
// A body local read before any write holds its default value at entry.
// An unused parameter still holds its caller-supplied value, so sharing its
// slot would replace that default even when the parameter itself is not live.
for local_id = param_count; local_id < total_locals; local_id = local_id + 1 {
if @ir.local_live_in(liveness, @ir.cfg_entry_block(cfg), local_id) {
for param_id = 0; param_id < param_count; param_id = param_id + 1 {
cl_cfg_sparse_add_interference(interferences, local_id, param_id)
}
}
}
// Share storage between scans, but reload the authoritative block facts.
let live_workspace = CLCfgLiveSet::new(total_locals)
match live_set_builds {
Some(count) => count[0] += 1
None => ()
}
let ineffective_sets : Array[@ir.NodeId] = []
let ineffective_tees : Array[@ir.NodeId] = []
for block_id = 0; block_id < @ir.cfg_block_count(cfg); block_id = block_id + 1 {
let block = block_actions[block_id]
let actions = block.actions
let ends_live_range = Array::make(actions.length(), false)
let effective = Array::make(actions.length(), false)
let live_after = cl_cfg_live_set_from_liveness(
liveness,
block_id,
total_locals,
false,
reuse=Some(live_workspace),
builds=live_set_builds,
visits=live_member_visits,
)
let mut action_idx = actions.length() - 1
while action_idx >= 0 {
let action = actions[action_idx]
match action.kind {
CLActionKind::Get => {
if !live_after.live[action.local_idx] {
ends_live_range[action_idx] = true
}
cl_cfg_live_set_add(live_after, action.local_idx)
}
CLActionKind::Set | CLActionKind::Tee => {
if live_after.live[action.local_idx] {
effective[action_idx] = true
}
cl_cfg_live_set_remove(live_after, action.local_idx)
}
}
action_idx -= 1
}
for idx = 0; idx < actions.length(); idx = idx + 1 {
match actions[idx].kind {
CLActionKind::Set =>
if !effective[idx] {
ineffective_sets.push(block.node_ids[idx])
}
CLActionKind::Tee =>
if !effective[idx] {
ineffective_tees.push(block.node_ids[idx])
}
_ => ()
}
}
let live = cl_cfg_live_set_from_liveness(
liveness,
block_id,
total_locals,
true,
reuse=Some(live_workspace),
builds=live_set_builds,
visits=live_member_visits,
)
ignore(
cl_cfg_sparse_add_live_member_interferences(interferences, live.members),
)
for idx = 0; idx < actions.length(); idx = idx + 1 {
let action = actions[idx]
match action.kind {
CLActionKind::Get =>
if ends_live_range[idx] {
cl_cfg_live_set_remove(live, action.local_idx)
}
CLActionKind::Set | CLActionKind::Tee => {
// Even an ineffective write still executes. Keep its destination
// away from every currently live local so coloring cannot turn a
// dead write into a clobber of a value observed later in the block.
for other in live.members {
cl_cfg_sparse_add_interference(
interferences,
action.local_idx,
other,
)
}
if effective[idx] {
cl_cfg_live_set_add(live, action.local_idx)
} else {
cl_cfg_live_set_remove(live, action.local_idx)
}
}
}
}
}
(interferences, ineffective_sets, ineffective_tees)
}
///|
fn cl_cfg_cleanup_ineffective_writes(
func : @ir.HotFunc,
set_node_ids : Array[@ir.NodeId],
tee_node_ids : Array[@ir.NodeId],
) -> Unit {
for node_id in set_node_ids {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
continue
}
ignore(@ir.hot_replace_local_set_with_drop(func, node_id))
}
for node_id in tee_node_ids {
if node_id < 0 || !@ir.hot_node_is_live(func, node_id) {
continue
}
ignore(@ir.hot_replace_local_tee_with_value(func, node_id))
}
}
///|
fn cl_rewrite_loop_func_cfg(
mod_ : @lib.Module,
func_idx : @lib.FuncIdx,
ctx : @ir.HotModuleContext,
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, @lib.Expr(original_instrs)) = func
if body_locals.length() <= 1 ||
params.length() + body_locals.length() > cl_dense_coloring_local_limit() ||
cl_instrs_have_legacy_try(original_instrs) ||
ssa_full_raw_has_call_in_try_table(original_instrs, false) {
return { func, changed: false, }
}
// CFG/liveness and lowering never query original source-access provenance.
let hot = match
@ir.hot_lift_func_with_context_result(
mod_,
func_idx,
ctx,
record_local_accesses=false,
) {
Ok(hot) => hot
Err(_) => return { func, changed: false, }
}
// Dead-write cleanup is indexed by node ID. It cannot remove only one
// occurrence of a definition inside a repeated entry producer.
if pass_has_repeated_entry_evaluation(hot) {
return { func, changed: false, }
}
// Lifting captures stack values before conflicting accesses and conditional
// operands. Those locals participate in the same liveness and interference
// analysis as source locals, even when the two access counts happen to match.
let total_locals = @ir.hot_local_count(hot)
let types : Array[@lib.ValType] = []
for local_id = 0; local_id < total_locals; local_id = local_id + 1 {
types.push(
match @ir.hot_local_type(hot, local_id) {
Some(ty) => ty
None => abort("coalesce-locals lifted local must have a declared type")
},
)
}
let cfg = @ir.cfg_build(hot, expand_operand_control=true)
// This consumer needs complete block liveness, not node/local use-site rows.
let liveness = @ir.liveness_build_from_func(
hot,
cfg,
include_exceptional_edges=true,
)
let block_actions = cl_cfg_collect_block_actions(hot, cfg)
let raw_actions : Array[CLAction] = []
cl_collect_instrs(original_instrs, raw_actions, total_locals)
let (interferences, ineffective_sets, ineffective_tees) = cl_cfg_compute_interferences(
cfg,
liveness,
block_actions,
total_locals,
params.length(),
)
let raw_liveness = cl_compute_liveness(raw_actions, total_locals)
let coloring = cl_cfg_sparse_pick_coloring(
types,
params.length(),
interferences,
cl_cfg_sparse_copy_weights(
raw_actions,
raw_liveness.effective,
total_locals,
),
)
if ineffective_sets.length() > 0 || ineffective_tees.length() > 0 {
cl_cfg_cleanup_ineffective_writes(hot, ineffective_sets, ineffective_tees)
}
// Apply the coloring to the very body whose lifetimes were analyzed. Applying
// a capture-aware coloring to the source body can clobber a carried read.
let @lib.Func(base_locals, @lib.Expr(base_instrs)) = @ir.hot_lower_func(hot)
let base_types = cl_all_local_types(params, base_locals)
if base_types.length() < total_locals {
abort("coalesce-locals lowering must retain every analyzed local")
}
// Lowering may need additional stack temporaries. Their lifetimes were not
// in this CFG, so append distinct slots instead of indexing past the map or
// merging them using unrelated source-local facts.
for local_id = total_locals
local_id < base_types.length()
local_id = local_id + 1 {
coloring.old_to_new.push(params.length() + coloring.slot_types.length())
coloring.slot_types.push(base_types[local_id])
}
let rewritten_locals = @lib.Locals::from_types(coloring.slot_types)
let rewritten_instrs = cl_copy_remap_instrs(base_instrs, coloring.old_to_new)
ignore(cl_remove_redundant_copy_pairs(rewritten_instrs))
let rewritten = @lib.Func::new(
rewritten_locals,
@lib.Expr::new(rewritten_instrs),
)
{ func: rewritten, changed: rewritten != func, }
}
///|
priv struct CLSingleLocalParamScanFacts {
mut ok : Bool
mut target_writes : Int32
mut target_gets : Int32
mut target_copy_source : Int32
mut target_region_reads_param : Bool
mut visited_instrs : Int32
}
///|
fn cl_scan_single_body_local_param_reuse(
instrs : Array[@lib.Instruction],
param_idx : Int32,
target_idx : Int32,
may_reuse_param : Bool,
must_reuse_param : Bool,
facts : CLSingleLocalParamScanFacts,
) -> (Bool, Bool) {
let mut may_reuse = may_reuse_param
let mut must_reuse = must_reuse_param
let mut region_reads_param = false
let mut region_param_crosses_call = false
for idx = 0; idx < instrs.length(); idx = idx + 1 {
facts.visited_instrs += 1
match instrs[idx] {
@lib.LocalGet(local_idx) => {
let local_id = cl_local_idx_raw(local_idx)
if local_id == target_idx {
facts.target_gets += 1
if !must_reuse {
facts.ok = false
return (false, false)
}
}
if local_id == param_idx {
if may_reuse {
facts.ok = false
return (false, false)
}
region_reads_param = true
}
}
@lib.LocalTee(local_idx) if cl_local_idx_raw(local_idx) == target_idx => {
facts.target_writes += 1
facts.target_region_reads_param = region_param_crosses_call
if idx > 0 {
match instrs[idx - 1] {
@lib.LocalGet(source_idx) => {
let source = cl_local_idx_raw(source_idx)
if source >= 0 && source < target_idx {
facts.target_copy_source = source
}
}
_ => ()
}
}
if facts.target_writes != 1 ||
(idx + 1 < instrs.length() && instrs[idx + 1] is @lib.Drop) {
facts.ok = false
return (false, false)
}
may_reuse = true
must_reuse = true
}
@lib.LocalSet(local_idx) if cl_local_idx_raw(local_idx) == target_idx => {
facts.ok = false
return (false, false)
}
@lib.LocalSet(local_idx) | @lib.LocalTee(local_idx) if cl_local_idx_raw(
local_idx,
) ==
param_idx => {
facts.ok = false
return (false, false)
}
@lib.Block(_, @lib.Expr(body)) => {
let (next_may_reuse, next_must_reuse) = cl_scan_single_body_local_param_reuse(
body, param_idx, target_idx, may_reuse, must_reuse, facts,
)
if !facts.ok {
return (false, false)
}
may_reuse = next_may_reuse
must_reuse = next_must_reuse
}
@lib.If(_, then_body, else_body) => {
let (then_may_reuse, then_must_reuse) = cl_scan_single_body_local_param_reuse(
then_body, param_idx, target_idx, may_reuse, must_reuse, facts,
)
if !facts.ok {
return (false, false)
}
let (else_may_reuse, else_must_reuse) = match else_body {
Some(body) =>
cl_scan_single_body_local_param_reuse(
body, param_idx, target_idx, may_reuse, must_reuse, facts,
)
None => (may_reuse, must_reuse)
}
if !facts.ok {
return (false, false)
}
may_reuse = then_may_reuse || else_may_reuse
must_reuse = then_must_reuse && else_must_reuse
}
@lib.Call(_) => if region_reads_param { region_param_crosses_call = true }
@lib.Br(_) | @lib.BrTable(_, _) | @lib.Return => {
if !must_reuse {
facts.ok = false
}
return (may_reuse, must_reuse)
}
@lib.BrIf(_)
| @lib.BrOnNull(_)
| @lib.BrOnNonNull(_)
| @lib.BrOnCast(_, _, _, _)
| @lib.BrOnCastFail(_, _, _, _)
| @lib.BrOnCastDescEq(_, _, _)
| @lib.BrOnCastDescEqFail(_, _, _) =>
if !must_reuse {
facts.ok = false
return (false, false)
}
@lib.Loop(_, _)
| @lib.Try(_, _, _, _)
| @lib.TryTable(_, _, _)
| @lib.Resume(_, _)
| @lib.ResumeThrow(_, _, _)
| @lib.ResumeThrowRef(_, _) => {
facts.ok = false
return (false, false)
}
_ => ()
}
}
(may_reuse, must_reuse)
}
///|
fn cl_rewrite_single_body_local_param_fast(
func : @lib.Func,
params : Array[@lib.ValType],
) -> (CLFuncRewrite?, Int32) {
let @lib.Func(body_locals, @lib.Expr(instrs)) = func
if body_locals.length() != 1 || params.length() == 0 {
return (None, 0)
}
let body_types = cl_flatten_locals(body_locals, 1)
let target_idx = params.length()
let mut compatible_params = 0
for param_type in params {
if param_type == body_types[0] {
compatible_params += 1
}
}
let mut param_idx = 0
while param_idx < params.length() {
if params[param_idx] != body_types[0] {
param_idx += 1
continue
}
let facts : CLSingleLocalParamScanFacts = {
ok: true,
target_writes: 0,
target_gets: 0,
target_copy_source: -1,
target_region_reads_param: false,
visited_instrs: 0,
}
ignore(
cl_scan_single_body_local_param_reuse(
instrs, param_idx, target_idx, false, false, facts,
),
)
if facts.ok &&
facts.target_writes == 1 &&
facts.target_gets > 0 &&
(facts.target_copy_source < 0 || facts.target_copy_source == param_idx) &&
(
facts.target_copy_source >= 0 ||
!facts.target_region_reads_param ||
compatible_params == 1
) {
let old_to_new : Array[Int32] = []
for idx = 0; idx < params.length(); idx = idx + 1 {
old_to_new.push(idx)
}
old_to_new.push(param_idx)
let rewritten_instrs = cl_deep_copy_instrs(instrs)
cl_rewrite_all_local_idxs_in_place(rewritten_instrs, old_to_new)
ignore(cl_remove_redundant_copy_pairs(rewritten_instrs))
return (
Some({
func: @lib.Func::new(
@lib.Locals::empty(),
@lib.Expr::new(rewritten_instrs),
),
changed: true,
}),
facts.visited_instrs,
)
}
param_idx += 1
}
(None, 0)
}
///|
fn cl_rewrite_func(
func : @lib.Func,
params : Array[@lib.ValType],
) -> CLFuncRewrite {
let @lib.Func(body_locals, body) = func
let body_local_count = body_locals.length()
if body_local_count == 0 {
return { func, changed: false, }
}
let @lib.Expr(original_instrs) = body
match cl_rewrite_single_body_local_param_fast(func, params).0 {
Some(rewrite) => return rewrite
None => ()
}
// Exact linear copy chains are common after lowering and can be rewritten
// without the general all-unused scan or dense interference machinery.
match cl_rewrite_linear_copy_chain_fast(func, params) {
Some(rewrite) => return rewrite
None => ()
}
match cl_rewrite_all_unused_func(func, params) {
Some(rewrite) => return rewrite
None => ()
}
if cl_instrs_have_legacy_try(original_instrs) {
return cl_rewrite_legacy_func_safe(func, params)
}
// The flattened conservative liveness model is not path/iteration-sensitive
// enough for loops. Non-loop structured control uses an extra plain-liveness
// interference pass, so local.tee branch values may still share proven-dead
// compatible slots without admitting path-sensitive overlap.
if cl_instrs_have_loop_control(original_instrs) {
return cl_cleanup_never_read_tees(
cl_rewrite_loop_func_unused_locals(func, params),
params.length(),
)
}
if params.length() + body_local_count > cl_dense_coloring_local_limit() {
return { func, changed: false, }
}
let has_structured_control = cl_instrs_have_structured_control(
original_instrs,
)
if has_structured_control {
if cl_should_use_dense_tee_structured_intervals(
body_local_count, original_instrs,
) {
return cl_rewrite_dense_tee_structured_intervals(func, params)
}
return cl_rewrite_func_structured_conservative(func, params)
}
let types = cl_all_local_types(params, body_locals)
let total_locals = types.length()
let actions : Array[CLAction] = []
cl_collect_instrs(original_instrs, actions, total_locals)
let liveness = cl_compute_liveness(actions, total_locals)
let interferences = cl_compute_linear_interferences(
original_instrs,
actions,
liveness,
types,
params.length(),
)
let weights = cl_copy_weights(actions, liveness.effective, total_locals)
let preferred = cl_preferred_compaction_flags(original_instrs, actions, types)
let retained_copy_destinations = cl_retained_copy_destination_flags(
actions,
types,
params.length(),
)
let structured_scalar_preferred = cl_structured_scalar_compaction_flags(
original_instrs,
actions,
types,
params.length(),
)
let coloring = cl_pick_coloring(
types,
params.length(),
interferences,
weights,
preferred,
retained_copy_destinations,
structured_scalar_preferred,
)
let rewritten_locals = @lib.Locals::from_types(coloring.slot_types)
let rewritten_instrs = original_instrs.copy()
cl_rewrite_instrs_in_place(
rewritten_instrs,
coloring.old_to_new,
liveness.effective,
[0],
)
let ineffective_tee_changed = cl_remove_ineffective_tees(
rewritten_instrs,
original_instrs,
liveness.effective,
[0],
)
let rewrite_changed = rewritten_instrs != original_instrs
let dead_tail_changed = cl_truncate_dead_tails(rewritten_instrs)
let cleanup_changed = cl_remove_redundant_copy_pairs(rewritten_instrs)
let changed = rewrite_changed ||
ineffective_tee_changed ||
dead_tail_changed ||
cleanup_changed ||
!cl_old_to_new_is_identity(coloring.old_to_new) ||
rewritten_locals != body_locals
if !changed {
return { func, changed: false, }
}
{
func: @lib.Func::new(rewritten_locals, @lib.Expr::new(rewritten_instrs)),
changed: true,
}
}
///|
fn cl_module_subtypes(mod_ : @lib.Module) -> Array[@lib.SubType] {
let subtypes : Array[@lib.SubType] = match mod_.type_sec {
Some(@lib.TypeSec(rec_types)) => Array::new(capacity=rec_types.length())
None => []
}
match mod_.type_sec {
Some(@lib.TypeSec(rec_types)) =>
for rec_type in rec_types {
match rec_type {
@lib.SingleRecType(subtype) => subtypes.push(subtype)
@lib.GroupRecType(group) =>
for subtype in group {
subtypes.push(subtype)
}
}
}
None => abort("coalesce-locals missing type section")
}
subtypes
}
///|
fn cl_params_for_type_idx(
subtypes : Array[@lib.SubType],
type_idx : @lib.TypeIdx,
) -> Array[@lib.ValType] {
let subtype = match type_idx {
@lib.TypeIdx(type_pos) =>
match subtypes.get(type_pos.reinterpret_as_int()) {
Some(subtype) => subtype
None => abort("coalesce-locals missing function subtype")
}
@lib.RecIdx(_) =>
// Function-section type references are module-global TypeIdx values after
// decode/validation. A RecIdx here would mean a rec-group-local type
// escaped into the module function declaration table, so keep this as an
// invariant assertion instead of trying to reinterpret it.
abort("coalesce-locals unsupported recursive function type index")
}
match subtype.get_comptype() {
@lib.FuncCompType(params, _) => params
_ => abort("coalesce-locals expected function type")
}
}
///|
fn cl_defined_func_param_cache(
mod_ : @lib.Module,
) -> Array[Array[@lib.ValType]] {
let subtypes = cl_module_subtypes(mod_)
let out : Array[Array[@lib.ValType]] = match mod_.func_sec {
Some(@lib.FuncSec(type_idxs)) => Array::new(capacity=type_idxs.length())
None => []
}
match mod_.func_sec {
Some(@lib.FuncSec(type_idxs)) =>
for type_idx in type_idxs {
out.push(cl_params_for_type_idx(subtypes, type_idx))
}
None => abort("coalesce-locals missing function section")
}
out
}
///|
fn cl_name_sec_without_local_names(name_sec : @lib.NameSec?) -> @lib.NameSec? {
match name_sec {
Some(sec) => {
let {
module_name,
func_names,
label_names,
type_names,
table_names,
memory_names,
global_names,
elem_names,
data_names,
field_names,
tag_names,
..
} = sec
Some(
@lib.NameSec::new(
module_name~,
func_names~,
local_names=None,
label_names~,
type_names~,
table_names~,
memory_names~,
global_names~,
elem_names~,
data_names~,
field_names~,
tag_names~,
),
)
}
None => None
}
}
///|
fn cl_rebuild_module(
mod_ : @lib.Module,
next_code_sec : @lib.CodeSec?,
next_name_sec : @lib.NameSec?,
) -> @lib.Module {
@lib.Module::new(
custom_secs=mod_.custom_secs,
type_sec=mod_.type_sec,
import_sec=mod_.import_sec,
func_annotation_sec=mod_.func_annotation_sec,
func_sec=mod_.func_sec,
table_sec=mod_.table_sec,
mem_sec=mod_.mem_sec,
tag_sec=mod_.tag_sec,
stringrefs_sec=mod_.stringrefs_sec,
global_sec=mod_.global_sec,
export_sec=mod_.export_sec,
start_sec=mod_.start_sec,
elem_sec=mod_.elem_sec,
data_cnt_sec=mod_.data_cnt_sec,
code_sec=next_code_sec,
data_sec=mod_.data_sec,
name_sec=next_name_sec,
)
}
///|
fn cl_validate_rewritten_funcs_with_commits(
mod_ : @lib.Module,
original_funcs : Array[@lib.Func],
rewritten_funcs : Array[@lib.Func],
changed_code_indices : Array[Int32],
) -> (Array[@lib.Func], Array[Int32]) {
if changed_code_indices.length() == 0 {
return (rewritten_funcs, [])
}
let imported_func_count = cl_imported_func_count(mod_)
let candidates : Array[(@lib.FuncIdx, @lib.Func)] = []
for code_idx in changed_code_indices {
if code_idx >= 0 && code_idx < rewritten_funcs.length() {
candidates.push(
(
@lib.FuncIdx::new(
(imported_func_count + code_idx).reinterpret_as_uint(),
),
rewritten_funcs[code_idx],
),
)
}
}
match @validate.validate_defined_funcs_against_module(mod_, candidates) {
Err(_) => (original_funcs.copy(), [])
Ok(errors) => {
if errors.length() == 0 {
return (rewritten_funcs, changed_code_indices.copy())
}
let checked = rewritten_funcs.copy()
let rejected = Array::make(original_funcs.length(), false)
for item in errors {
let (@lib.FuncIdx(raw), _) = item
let code_idx = raw.reinterpret_as_int() - imported_func_count
if code_idx >= 0 && code_idx < original_funcs.length() {
checked[code_idx] = original_funcs[code_idx]
rejected[code_idx] = true
}
}
let committed : Array[Int32] = []
for code_idx in changed_code_indices {
if code_idx >= 0 && code_idx < rejected.length() && !rejected[code_idx] {
committed.push(code_idx)
}
}
(checked, committed)
}
}
}
///|
fn cl_locals_have_nondefaultable_type(locals : @lib.Locals) -> Bool {
for run in locals.runs() {
match run.val_type() {
@lib.RefTypeValType(ref_type) =>
if !@lib.RefType::is_defaultable(ref_type) {
return true
}
@lib.BotValType => return true
_ => ()
}
}
false
}
///|
fn cl_locals_have_dense_v128_carriers(locals : @lib.Locals) -> Bool {
let mut count = 0
for run in locals.runs() {
if run.val_type() == @lib.ValType::v128() {
count = count + run.count().reinterpret_as_int()
if count >= 8 {
return true
}
}
}
false
}
///|
fn cl_snapshot_guard_preflight(
instrs : Array[@lib.Instruction],
parameter_count : Int32,
) -> Bool {
if parameter_count <= 0 {
return false
}
for instr in instrs {
match instr {
@lib.MemorySize(_) => return true
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_snapshot_guard_preflight(body, parameter_count) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_snapshot_guard_preflight(then_body, parameter_count) {
return true
}
match else_body {
Some(body) =>
if cl_snapshot_guard_preflight(body, parameter_count) {
return true
}
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_instrs_have_local_snapshot_across_parameter_write(
instrs : Array[@lib.Instruction],
parameter_count : Int32,
) -> Bool {
if parameter_count <= 0 {
return false
}
let mut max_local = parameter_count - 1
for instr in instrs {
match instr {
@lib.LocalGet(@lib.LocalIdx(raw))
| @lib.LocalSet(@lib.LocalIdx(raw))
| @lib.LocalTee(@lib.LocalIdx(raw)) => {
let local_idx = raw.reinterpret_as_int()
if local_idx > max_local {
max_local = local_idx
}
}
_ => ()
}
}
let latest_read = Array::make(max_local + 1, -1)
let mut next_parameter_write = -1
let mut idx = instrs.length() - 1
while idx >= 0 {
match instrs[idx] {
@lib.LocalGet(@lib.LocalIdx(raw)) => {
let local_idx = raw.reinterpret_as_int()
if latest_read[local_idx] < 0 {
latest_read[local_idx] = idx
}
}
@lib.LocalSet(@lib.LocalIdx(raw)) | @lib.LocalTee(@lib.LocalIdx(raw)) =>
if raw.reinterpret_as_int() < parameter_count {
next_parameter_write = idx
}
_ => ()
}
if idx > 0 {
match (instrs[idx - 1], instrs[idx]) {
(@lib.MemorySize(_), @lib.LocalTee(@lib.LocalIdx(raw_snapshot))) => {
let snapshot = raw_snapshot.reinterpret_as_int()
if snapshot >= parameter_count &&
next_parameter_write >= 0 &&
latest_read[snapshot] > next_parameter_write {
return true
}
}
_ => ()
}
}
idx -= 1
}
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_have_local_snapshot_across_parameter_write(
body, parameter_count,
) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_local_snapshot_across_parameter_write(
then_body, parameter_count,
) {
return true
}
match else_body {
Some(body) =>
if cl_instrs_have_local_snapshot_across_parameter_write(
body, parameter_count,
) {
return true
}
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_instrs_memory_size_tee_parameter_write_facts(
instrs : Array[@lib.Instruction],
parameter_count : Int32,
) -> (Bool, Bool, Bool) {
let mut has_memory_size = false
let mut has_local_tee = false
let mut has_parameter_write = false
for instr in instrs {
match instr {
@lib.MemorySize(_) => has_memory_size = true
@lib.LocalTee(@lib.LocalIdx(raw)) =>
if raw.reinterpret_as_int() < parameter_count {
has_parameter_write = true
} else {
has_local_tee = true
}
@lib.LocalSet(@lib.LocalIdx(raw)) =>
if raw.reinterpret_as_int() < parameter_count {
has_parameter_write = true
}
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) => {
let (memory_size, local_tee, parameter_write) = cl_instrs_memory_size_tee_parameter_write_facts(
body, parameter_count,
)
has_memory_size = has_memory_size || memory_size
has_local_tee = has_local_tee || local_tee
has_parameter_write = has_parameter_write || parameter_write
}
@lib.If(_, then_body, else_body) => {
let (then_memory_size, then_local_tee, then_parameter_write) = cl_instrs_memory_size_tee_parameter_write_facts(
then_body, parameter_count,
)
has_memory_size = has_memory_size || then_memory_size
has_local_tee = has_local_tee || then_local_tee
has_parameter_write = has_parameter_write || then_parameter_write
match else_body {
Some(body) => {
let (else_memory_size, else_local_tee, else_parameter_write) = cl_instrs_memory_size_tee_parameter_write_facts(
body, parameter_count,
)
has_memory_size = has_memory_size || else_memory_size
has_local_tee = has_local_tee || else_local_tee
has_parameter_write = has_parameter_write || else_parameter_write
}
None => ()
}
}
_ => ()
}
}
(has_memory_size, has_local_tee, has_parameter_write)
}
///|
fn cl_instrs_have_memory_size_tee_parameter_write(
instrs : Array[@lib.Instruction],
parameter_count : Int32,
) -> Bool {
let (has_memory_size, has_local_tee, _) = cl_instrs_memory_size_tee_parameter_write_facts(
instrs, parameter_count,
)
has_memory_size && has_local_tee
}
///|
fn cl_instrs_have_stack_carried_tee_parameter_alias(
instrs : Array[@lib.Instruction],
parameter_count : Int32,
) -> Bool {
if parameter_count <= 0 {
return false
}
for tee_idx = 0; tee_idx < instrs.length(); tee_idx = tee_idx + 1 {
let target = match instrs[tee_idx] {
@lib.LocalTee(target) => target
_ => continue
}
let limit = if tee_idx + 9 < instrs.length() {
tee_idx + 9
} else {
instrs.length()
}
for read_idx = tee_idx + 2; read_idx + 1 < limit; read_idx = read_idx + 1 {
match (instrs[read_idx], instrs[read_idx + 1]) {
(@lib.LocalGet(read), @lib.LocalSet(@lib.LocalIdx(raw_parameter))) =>
if read == target &&
raw_parameter.reinterpret_as_int() < parameter_count {
return true
}
_ => ()
}
}
}
for instr in instrs {
match instr {
@lib.Block(_, @lib.Expr(body))
| @lib.Loop(_, @lib.Expr(body))
| @lib.TryTable(_, _, @lib.Expr(body)) =>
if cl_instrs_have_stack_carried_tee_parameter_alias(
body, parameter_count,
) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_stack_carried_tee_parameter_alias(
then_body, parameter_count,
) {
return true
}
match else_body {
Some(body) =>
if cl_instrs_have_stack_carried_tee_parameter_alias(
body, parameter_count,
) {
return true
}
None => ()
}
}
_ => ()
}
}
false
}
///|
fn cl_instrs_have_external_try_table_catch(
instrs : Array[@lib.Instruction],
) -> Bool {
for instr in instrs {
match instr {
@lib.TryTable(_, catches, _) if !catches.is_empty() => return true
@lib.Block(_, @lib.Expr(body)) | @lib.Loop(_, @lib.Expr(body)) =>
if cl_instrs_have_external_try_table_catch(body) {
return true
}
@lib.If(_, then_body, else_body) => {
if cl_instrs_have_external_try_table_catch(then_body) {
return true
}
match else_body {
Some(body) =>
if cl_instrs_have_external_try_table_catch(body) {
return true
}
None => ()
}
}
@lib.Try(_, @lib.Expr(body), catches, _) => {
if cl_instrs_have_external_try_table_catch(body) {
return true
}
for catch_ in catches {
let @lib.Expr(catch_body) = match catch_ {
@lib.LegacyCatch(_, body) | @lib.LegacyCatchAll(body) => body
}
if cl_instrs_have_external_try_table_catch(catch_body) {
return true
}
}
}
_ => ()
}
}
false
}
///|
pub fn coalesce_locals_run_module_pass(mod_ : @lib.Module) -> @lib.Module {
if pass_module_has_offset_sensitive_metadata(mod_) {
return mod_
}
ignore(cl_imported_func_count(mod_))
match mod_.code_sec {
Some(@lib.CodeSec(funcs)) => {
if funcs.is_empty() {
return mod_
}
let defined_func_params = cl_defined_func_param_cache(mod_)
let hot_context = @ir.hot_module_context_from_module(mod_)
let imported_func_count = cl_imported_func_count(mod_)
let observable_assemblyscript_memory = run_hot_pipeline_module_has_assemblyscript_json_exported_memory_runtime(
mod_,
) ||
run_hot_pipeline_module_has_assemblyscript_run_exported_memory_runtime(
mod_,
) ||
run_hot_pipeline_module_has_assemblyscript_startup_exported_memory(mod_)
let rewritten_funcs : Array[@lib.Func] = Array::new(
capacity=funcs.length(),
)
let changed_code_indices : Array[Int32] = []
for code_idx = 0; code_idx < funcs.length(); code_idx = code_idx + 1 {
let params = match defined_func_params.get(code_idx) {
Some(params) => params
None => abort("coalesce-locals missing defined function params")
}
let @lib.Func(body_locals, @lib.Expr(instrs)) = funcs[code_idx]
if !cl_func_may_have_coalesce_candidate(body_locals, instrs) {
rewritten_funcs.push(funcs[code_idx])
continue
}
if cl_instrs_have_external_try_table_catch(instrs) {
rewritten_funcs.push(funcs[code_idx])
continue
}
let has_stack_carried_overwrite = run_hot_pipeline_raw_precompute_has_stack_carried_overwritten_local(
instrs,
)
let has_stack_carried_tee_alias = cl_instrs_have_stack_carried_tee_parameter_alias(
instrs,
params.length(),
)
let has_snapshot_parameter_write = cl_snapshot_guard_preflight(
instrs,
params.length(),
) &&
cl_instrs_have_local_snapshot_across_parameter_write(
instrs,
params.length(),
)
let has_observable_memory_mesh = observable_assemblyscript_memory &&
cl_instrs_have_memory_size_tee_parameter_write(
instrs,
params.length(),
)
if has_stack_carried_overwrite ||
has_stack_carried_tee_alias ||
has_snapshot_parameter_write ||
has_observable_memory_mesh {
rewritten_funcs.push(funcs[code_idx])
continue
}
if params.length() > 0 &&
body_locals.length() <= 32 &&
cl_locals_have_dense_v128_carriers(body_locals) &&
cl_instrs_have_loop_control(instrs) {
rewritten_funcs.push(funcs[code_idx])
continue
}
if funcs.length() >= 32 &&
params.length() > 0 &&
body_locals.length() >= 16 &&
cl_locals_have_nondefaultable_type(body_locals) &&
cl_instrs_have_structured_control(instrs) {
rewritten_funcs.push(funcs[code_idx])
continue
}
let cfg_rewrite = if cl_instrs_have_loop_control(instrs) {
cl_rewrite_loop_func_cfg(
mod_,
@lib.FuncIdx::new(
(imported_func_count + code_idx).reinterpret_as_uint(),
),
hot_context,
funcs[code_idx],
params,
)
} else {
{ func: funcs[code_idx], changed: false, }
}
let rewrite_input = if cfg_rewrite.changed {
cfg_rewrite.func
} else {
funcs[code_idx]
}
let cleanup_rewrite = cl_cleanup_never_read_tees(
cl_rewrite_func(rewrite_input, params),
params.length(),
)
let rewrite : CLFuncRewrite = {
func: cleanup_rewrite.func,
changed: cfg_rewrite.changed || cleanup_rewrite.changed,
}
rewritten_funcs.push(rewrite.func)
if rewrite.changed {
changed_code_indices.push(code_idx)
}
}
if changed_code_indices.length() == 0 {
return mod_
}
let (checked_funcs, committed_code_indices) = cl_validate_rewritten_funcs_with_commits(
mod_, funcs, rewritten_funcs, changed_code_indices,
)
if committed_code_indices.length() == 0 {
return mod_
}
cl_rebuild_module(
mod_,
Some(@lib.CodeSec::new(checked_funcs)),
cl_name_sec_without_local_names(mod_.name_sec),
)
}
None => mod_
}
}
///|
test "coalesce block-only liveness preserves GC loop carriers and removes unused scalar locals" {
let input = pass_test_module_from_wat(
"(module (type $s (struct (field i32))) (func (export \"run\") (param i32) (result i32) (local i32 (ref null $s) i64) local.get 0 i32.const 3 i32.and local.set 1 i32.const 7 struct.new $s local.set 2 block loop local.get 1 i32.eqz br_if 1 local.get 2 struct.get $s 0 drop local.get 1 i32.const 1 i32.sub local.set 1 br 0 end end local.get 2 struct.get $s 0))",
)
let saved = @binary.encode_module(input).unwrap()
let output = coalesce_locals_run_module_pass(input)
@validate.validate_module(output).unwrap()
guard output.code_sec is Some(@lib.CodeSec(funcs)) else {
fail("GC loop function must remain present")
}
let @lib.Func(locals, _) = funcs[0]
assert_true(locals.length() < 3)
assert_eq(@binary.encode_module(input).unwrap(), saved)
}
///|
test "coalesce global copy barrier retains imported effects and active coloring" {
let input = pass_test_module_from_wat(
"(module (import \"host\" \"f\" (func $f (param i32) (result i32))) (func (export \"run\") (param i32) (result i32) (local i32 i32 i32) local.get 0 local.set 1 local.get 1 local.set 2 block local.get 0 br_if 0 local.get 2 call $f local.set 3 end local.get 2))",
)
let saved = @binary.encode_module(input).unwrap()
let output = coalesce_locals_run_module_pass(input)
@validate.validate_module(output).unwrap()
let funcs = match output.code_sec {
Some(@lib.CodeSec(funcs)) => funcs
None => abort("missing code")
}
let @lib.Func(locals, _) = funcs[0]
assert_true(locals.length() < 3)
assert_eq(@binary.encode_module(input).unwrap(), saved)
}