///|
/// The reference graph between functions and their modelled domination weights.
///
/// The model follows Twiggy: a module is a graph of functions rooted at whatever
/// the outside world can reach — exported functions, the start function and
/// everything the element sections hand to the host or to `call_indirect`. What
/// is not reachable from those roots is unreachable within this model. Recorded
/// diagnostics and the modelling scope limit conclusions about actual execution.
///|
/// How one function refers to another.
pub enum EdgeKind {
/// `call x` or `return_call x`: the target is named outright.
Direct
/// `call_indirect` or `return_call_indirect`: a table supplies the target.
Indirect
/// `ref.func x`: a reference taken without calling, as when building a
/// closure. The function may well run later, so it counts as reachable.
Reference
}
///|
/// One edge of the call graph.
pub struct CallEdge {
caller : Int
callee : Int
kind : EdgeKind
/// Offset of the instruction that makes the reference.
offset : Int
}
///|
/// A `call_indirect` or `return_call_indirect`, with its table's candidates.
pub struct IndirectSite {
caller : Int
/// Table the call reads.
table_index : Int
/// Signature the call selects on.
type_index : Int
/// Offset of the ordinary or tail indirect call instruction.
offset : Int
/// Known element candidates. Dynamic risks are diagnosed separately; a
/// nonempty list is not proof that all possible targets are represented.
candidates : Array[Int]
}
///|
/// A stable category of a detected gap in call-target analysis.
pub enum GraphDiagnosticKind {
/// An ordinary or tail table call has no static element candidates.
NoStaticTableTargets
/// Reference-call target data flow is not modelled yet.
UnmodeledReferenceCall
/// The host supplies or shares the target table's contents.
ImportedTableContents
/// The host can modify an exported target table.
ExportedTableContents
/// A module instruction may write the target table.
RuntimeTableMutation
/// An explicit table initializer has not been evaluated.
UnmodeledTableInitializer
/// A call names a table absent from the parsed context; never assume static.
UnknownTableContents
}
///|
/// Provenance of a gap, distinct from the call instruction's own position.
pub struct GraphDiagnosticSource {
/// Some for a runtime write; None for a declaration/initializer/export.
caller : Int?
/// Absolute writer opcode offset, import/export descriptor kind offset, or
/// explicit initializer expression start, according to the diagnostic kind.
offset : Int
/// Only runtime writer sources carry an opcode.
opcode : Opcode?
}
///|
/// One reason a call site's dependencies may be incomplete. A site can have
/// multiple distinct reasons and multiple runtime writer positions.
pub struct GraphDiagnostic {
kind : GraphDiagnosticKind
/// Full function index, including preceding imports.
caller : Int
/// Instruction offset in the original file.
offset : Int
opcode : Opcode
type_index : Int?
/// None for reference calls.
table_index : Int?
source : GraphDiagnosticSource?
}
///|
/// The reference graph between functions.
pub struct CallGraph {
/// Outgoing references by function index.
calls : Map[Int, Set[Int]]
/// Incoming references by function index.
called_by : Map[Int, Set[Int]]
/// Every ordinary or tail indirect call, with its table's candidates.
indirect_sites : Array[IndirectSite]
/// The subset of those sites whose table gave no candidates at all.
///
/// A module may fill a table at run time — `table.set`, `table.init`, or the
/// host handing it functions —
/// and a table with no element segment tells this tool nothing about who sits
/// in it. Dropping the site would mean dropping every edge it stands for, and
/// a missing edge is a function wrongly called dead, so the sites are kept
/// here and every report says out loud what they cost.
unresolved_indirect : Array[IndirectSite]
/// Analysis reasons, not a count of call sites. Identical sources are deduped.
diagnostics : Array[GraphDiagnostic]
/// Every edge with its kind and site, for export.
edges : Array[CallEdge]
}
///|
/// Whether no gaps were detected within the current analysis scope.
///
/// Missing edges can make dead-code and retained-size results inaccurate.
/// Callers such as `--dead-code`, `--retained` and `--strict` report this hole.
/// A true result does not prove every Wasm call mechanism is fully modelled.
/// Dynamic table risks and reference calls are diagnosed, not solved.
pub fn is_graph_complete(graph : CallGraph) -> Bool {
graph.diagnostics.is_empty()
}
///|
/// The functions an element segment puts in a table, merged over every segment
/// that targets it.
fn table_functions(elements : Array[ElementSegment], table : Int) -> Array[Int] {
let seen : Set[Int] = Set([])
for segment in elements {
if segment.table_index == table {
for function in segment.functions {
seen.add(function)
}
}
}
seen.to_array()
}
///|
/// Build from complete module bytes, parsing canonical bodies, elements and
/// table context internally. Callers cannot supply an empty table context or
/// omit a writer body. Use analyze when sizes and retention are also needed.
///
/// Every body is decoded once: `call` and `return_call` give precise edges,
/// `ref.func` gives a reference edge, and `call_indirect` and
/// `return_call_indirect` give conservative edges to static table candidates
/// plus a record of each site, including sites with no candidates.
/// Reference calls are kept as diagnostics without guessing a target, even when
/// the preceding instruction is ref.func.
pub fn build(data : Bytes) -> Result[CallGraph, WasmError] {
let parsed = match parse_module(data) {
Ok(value) => value
Err(error) => return Err(error)
}
let sections = find_sections(parsed)
let imported = match sections.imports {
Some(section) =>
match count_imported_functions(data, section) {
Ok(value) => value
Err(error) => return Err(error)
}
None => 0
}
let bodies = match sections.code {
Some(section) =>
match parse_code_section(data, section, base_index=imported) {
Ok(value) => value
Err(error) => return Err(error)
}
None => []
}
let elements = match sections.elements {
Some(section) =>
match parse_element_section(data, section) {
Ok(value) => value
Err(error) => return Err(error)
}
None => []
}
let tables = match table_context(data, sections) {
Ok(value) => value
Err(error) => return Err(error)
}
build_graph(data, bodies, elements, tables)
}
///|
/// Internal entry: analyze already has canonical parsed bodies and elements.
/// Decode once, retaining only dependency instructions and writer provenance,
/// then resolve calls with the complete writer set. Even unreachable writes count.
fn build_graph(
data : Bytes,
bodies : Array[FunctionBody],
elements : Array[ElementSegment],
tables : Array[TableInfo],
) -> Result[CallGraph, WasmError] {
let calls : Map[Int, Set[Int]] = Map([])
let called_by : Map[Int, Set[Int]] = Map([])
let edges : Array[CallEdge] = []
let sites : Array[IndirectSite] = []
let unresolved : Array[IndirectSite] = []
let diagnostics : Array[GraphDiagnostic] = []
let events : Array[(Int, Instruction)] = []
let writes : Map[Int, Array[GraphDiagnosticSource]] = Map([])
let seen_writes : Set[Int] = Set([])
for body in bodies {
let start = body.offset + body.total_size - body.body_size
let instructions = match decode_instructions(data, start, body.body_size) {
Ok(instructions) => instructions
Err(error) => return Err(error)
}
for instruction in instructions {
match instruction.opcode {
Call
| ReturnCall
| RefFunc
| CallRef
| ReturnCallRef
| CallIndirect
| ReturnCallIndirect => events.push((body.index, instruction))
_ => ()
}
match written_table(instruction) {
Some(table) =>
if !seen_writes.contains(instruction.offset) {
seen_writes.add(instruction.offset)
let source : GraphDiagnosticSource = {
caller: Some(body.index),
offset: instruction.offset,
opcode: Some(instruction.opcode),
}
match writes.get(table) {
Some(sources) => sources.push(source)
None => writes.set(table, [source])
}
}
None => ()
}
}
}
for (caller, instruction) in events {
match instruction.opcode {
Call | ReturnCall =>
add_edge(
calls,
called_by,
edges,
caller,
instruction.operands[0],
Direct,
instruction.offset,
)
RefFunc =>
add_edge(
calls,
called_by,
edges,
caller,
instruction.operands[0],
Reference,
instruction.offset,
)
CallRef | ReturnCallRef =>
diagnostics.push({
kind: UnmodeledReferenceCall,
caller,
offset: instruction.offset,
opcode: instruction.opcode,
type_index: Some(instruction.operands[0]),
table_index: None,
source: None,
})
CallIndirect | ReturnCallIndirect => {
let type_index = instruction.operands[0]
let table_index = instruction.operands[1]
let candidates = table_functions(elements, table_index)
let site : IndirectSite = {
caller,
table_index,
type_index,
offset: instruction.offset,
candidates,
}
sites.push(site)
// A site with nothing to point at still gets recorded: the report has
// to be able to say how many of them there are, because every one is a
// call this graph cannot follow.
if candidates.length() == 0 {
unresolved.push(site)
diagnostics.push(
table_gap(site, instruction.opcode, NoStaticTableTargets, None),
)
}
table_diagnostics(site, instruction.opcode, tables, writes, diagnostics)
for candidate in candidates {
add_edge(
calls,
called_by,
edges,
caller,
candidate,
Indirect,
instruction.offset,
)
}
}
_ => ()
}
}
Ok({
calls,
called_by,
indirect_sites: sites,
unresolved_indirect: unresolved,
diagnostics,
edges,
})
}
///|
/// Record one edge in both directions.
fn add_edge(
calls : Map[Int, Set[Int]],
called_by : Map[Int, Set[Int]],
edges : Array[CallEdge],
caller : Int,
callee : Int,
kind : EdgeKind,
offset : Int,
) -> Unit {
outgoing(calls, caller).add(callee)
outgoing(called_by, callee).add(caller)
edges.push({ caller, callee, kind, offset, })
}
///|
/// The adjacency set for a node, created on first use.
fn outgoing(map : Map[Int, Set[Int]], node : Int) -> Set[Int] {
match map.get(node) {
Some(set) => set
None => {
let set : Set[Int] = Set([])
map.set(node, set)
set
}
}
}
///|
/// Everything reachable from `roots`, the roots included.
///
/// An explicit stack rather than recursion: real modules nest thousands of calls
/// deep, and the depth of the graph should not be the depth of the C stack.
pub fn reachable_from_roots(graph : CallGraph, roots : Set[Int]) -> Set[Int] {
let seen : Set[Int] = Set([])
let stack : Array[Int] = []
for root in roots {
if !seen.contains(root) {
seen.add(root)
stack.push(root)
}
}
while stack.length() > 0 {
let node = stack[stack.length() - 1]
let _ = stack.pop()
match graph.calls.get(node) {
Some(targets) =>
for target in targets {
if !seen.contains(target) {
seen.add(target)
stack.push(target)
}
}
None => ()
}
}
seen
}
///|
/// The roots of a module: what the outside world can reach without going through
/// code the module already has.
///
/// Exported functions and start are roots. Every function referenced by an
/// element segment is also conservatively rooted, including private, passive
/// and declarative segments. This does not assert that each can actually run.
pub fn roots_of(
exports : Array[Export],
elements : Array[ElementSegment],
start : Int?,
) -> Set[Int] {
let roots : Set[Int] = Set([])
for item in exports {
if item.kind == 0 {
roots.add(item.index)
}
}
for segment in elements {
for function in segment.functions {
roots.add(function)
}
}
match start {
Some(index) => roots.add(index)
None => ()
}
roots
}
///|
/// The functions any ordinary or tail indirect call could reach, for reports.
pub fn indirect_targets(graph : CallGraph) -> Set[Int] {
let targets : Set[Int] = Set([])
for site in graph.indirect_sites {
for candidate in site.candidates {
targets.add(candidate)
}
}
targets
}
///|
/// Encoded function weights in a dominator subtree of the current graph model.
pub struct RetainedSize {
index : Int
/// The function's own encoded bytes, its size prefix included.
own_size : Int
/// Sum of own_size over its modelled dominated functions, including itself.
/// Excludes data, metadata and caller rewrites; not actual recompilation savings.
retained : Int
/// How many other defined functions it dominates in this model.
retained_functions : Int
}
///|
/// Walk to the common dominator of two nodes, using reverse-postorder numbers as
/// the fingers of the classic algorithm.
fn intersect(a : Int, b : Int, idom : Array[Int], order : Array[Int]) -> Int {
let mut x = a
let mut y = b
while x != y {
while order[x] > order[y] {
x = idom[x]
}
while order[y] > order[x] {
y = idom[y]
}
}
x
}
///|
/// The retained size of every reachable function.
///
/// Within the fixed graph/root model, removing a node disconnects its dominated
/// nodes: those every path from a root has to pass through. This is a graph
/// operation, not source removal, relinking or gzip prediction. Computing it with an
/// explicit "remove it and see what dies" walk would be correct but quadratic,
/// and it would still need cycle handling; the dominator tree answers the same
/// question for every function at once, and cycles fall out of the fixpoint
/// without a special case.
pub fn retained_sizes(
graph : CallGraph,
sizes : Map[Int, Int],
roots : Set[Int],
) -> Array[RetainedSize] {
let reachable = reachable_from_roots(graph, roots)
// Only functions with a body have a size, and only those can be dominators.
let nodes : Array[Int] = []
for node in reachable {
if sizes.get(node) is Some(_) {
nodes.push(node)
}
}
let count = nodes.length()
let id_of : Map[Int, Int] = Map([])
let mut i = 0
while i < count {
id_of.set(nodes[i], i)
i = i + 1
}
// A virtual root above the real ones, so a graph with several entry points
// still has a single dominator tree.
let root_id = count
let total = count + 1
let successors : Array[Array[Int]] = []
let predecessors : Array[Array[Int]] = []
let mut i = 0
while i < total {
successors.push([])
predecessors.push([])
i = i + 1
}
for node in nodes {
let from = match id_of.get(node) {
Some(id) => id
None => continue
}
match graph.calls.get(node) {
Some(targets) =>
for target in targets {
match id_of.get(target) {
Some(to) => {
successors[from].push(to)
predecessors[to].push(from)
}
None => ()
}
}
None => ()
}
}
for node in nodes {
match id_of.get(node) {
Some(id) =>
if roots.contains(node) {
successors[root_id].push(id)
predecessors[id].push(root_id)
}
None => ()
}
}
// Reverse postorder from the virtual root, iteratively.
let visited : Array[Bool] = Array::make(total, false)
let next_edge : Array[Int] = Array::make(total, 0)
let stack : Array[Int] = [root_id]
visited[root_id] = true
let postorder : Array[Int] = []
while stack.length() > 0 {
let node = stack[stack.length() - 1]
if next_edge[node] < successors[node].length() {
let target = successors[node][next_edge[node]]
next_edge[node] = next_edge[node] + 1
if !visited[target] {
visited[target] = true
stack.push(target)
}
} else {
postorder.push(node)
let _ = stack.pop()
}
}
let order : Array[Int] = Array::make(total, 0)
let reverse : Array[Int] = []
let mut i = postorder.length() - 1
while i >= 0 {
order[postorder[i]] = reverse.length()
reverse.push(postorder[i])
i = i - 1
}
let idom : Array[Int] = Array::make(total, -1)
idom[root_id] = root_id
let mut changed = true
while changed {
changed = false
let mut i = 1
while i < reverse.length() {
let node = reverse[i]
let mut candidate = -1
for predecessor in predecessors[node] {
if idom[predecessor] != -1 {
candidate = if candidate == -1 {
predecessor
} else {
intersect(predecessor, candidate, idom, order)
}
}
}
if candidate != -1 && idom[node] != candidate {
idom[node] = candidate
changed = true
}
i = i + 1
}
}
let retained : Array[Int] = Array::make(total, 0)
let dominated : Array[Int] = Array::make(total, 0)
for node in nodes {
match id_of.get(node) {
Some(id) => {
retained[id] = match sizes.get(node) {
Some(size) => size
None => 0
}
dominated[id] = 1
}
None => ()
}
}
// Walk the reverse postorder backwards: every node is settled before the
// dominator it hands its total to.
let mut i = reverse.length() - 1
while i > 0 {
let node = reverse[i]
retained[idom[node]] = retained[idom[node]] + retained[node]
dominated[idom[node]] = dominated[idom[node]] + dominated[node]
i = i - 1
}
let out : Array[RetainedSize] = []
for node in nodes {
match id_of.get(node) {
Some(id) =>
out.push({
index: node,
own_size: match sizes.get(node) {
Some(size) => size
None => 0
},
retained: retained[id],
retained_functions: dominated[id] - 1,
})
None => ()
}
}
out
}