A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
//! Instruction predicates/properties, shared by various analyses.
use crate::ir::immediates::Offset32;
use crate::ir::{
self, Block, DataFlowGraph, Function, Inst, InstructionData, MemFlagsData, Opcode, Type, Value,
};
/// Test whether the given opcode is unsafe to even consider as side-effect-free.
#[inline(always)]
fn trivially_has_side_effects(opcode: Opcode) -> bool {
opcode.is_call()
|| opcode.is_branch()
|| opcode.is_terminator()
|| opcode.is_return()
|| opcode.can_trap()
|| opcode.other_side_effects()
|| opcode.can_store()
}
/// Load instructions without the `notrap` flag are defined to trap when
/// operating on inaccessible memory, so we can't treat them as side-effect-free even if the loaded
/// value is unused.
#[inline(always)]
fn is_load_with_defined_trapping(
opcode: Opcode,
data: &InstructionData,
dfg: &DataFlowGraph,
) -> bool {
if !opcode.can_load() {
return false;
}
match *data {
InstructionData::Load { flags, .. } => !dfg.mem_flags[flags].notrap(),
_ => true,
}
}
/// Is the given instruction a `volatile` memory access?
///
/// Such an access must happen exactly as written: see
/// [`ir::MemFlagsData::volatile`].
pub fn is_volatile_access(func: &Function, inst: Inst) -> bool {
func.dfg.insts[inst]
.memflags_data(&func.dfg)
.is_some_and(|flags| flags.volatile())
}
/// Does the given instruction have any side-effect that would preclude it from being removed when
/// its value is unused?
///
/// A `volatile` load has one: the access itself is the effect.
#[inline(always)]
fn has_side_effect(func: &Function, inst: Inst) -> bool {
let data = &func.dfg.insts[inst];
let opcode = data.opcode();
trivially_has_side_effects(opcode)
|| is_load_with_defined_trapping(opcode, data, &func.dfg)
|| (opcode.can_load() && is_volatile_access(func, inst))
}
fn load_mem_flags(func: &Function, inst: Inst) -> Option<MemFlagsData> {
match func.dfg.insts[inst] {
InstructionData::Load {
opcode: Opcode::Load,
flags,
..
} => Some(func.dfg.mem_flags[flags]),
_ => None,
}
}
/// Does the given instruction behave as a "pure" node with respect to
/// aegraph semantics?
///
/// - Trivially pure nodes (bitwise arithmetic, etc)
/// - Loads with the `readonly`, `notrap`, and `can_move` flags set
pub fn is_pure_for_egraph(func: &Function, inst: Inst) -> bool {
let is_pure_load = match load_mem_flags(func, inst) {
// `readonly` and `can_move` each imply not `volatile` (the
// verifier rejects the combination), so such a load is never a
// volatile access.
Some(flags) => flags.readonly() && flags.notrap() && flags.can_move(),
None => false,
};
// Multi-value results do not play nicely with much of the egraph
// infrastructure. They are in practice used only for multi-return
// calls and some other odd instructions (e.g. uadd_overflow) which,
// for now, we can afford to leave in place as opaque
// side-effecting ops. So if more than one result, then the inst
// is "not pure". Similarly, ops with zero results can be used
// only for their side-effects, so are never pure. (Or if they
// are, we can always trivially eliminate them with no effect.)
let has_one_result = func.dfg.inst_results(inst).len() == 1;
let op = func.dfg.insts[inst].opcode();
has_one_result && (is_pure_load || (!op.can_load() && !trivially_has_side_effects(op)))
}
/// Can the given instruction be merged into another copy of itself?
/// These instructions may have side-effects, but as long as we retain
/// the first instance of the instruction, the second and further
/// instances are redundant if they would produce the same trap or
/// result.
pub fn is_mergeable_for_egraph(func: &Function, inst: Inst) -> bool {
let op = func.dfg.insts[inst].opcode();
let is_readonly_load = load_mem_flags(func, inst)
.map(|flags| flags.readonly())
.unwrap_or(false);
// We can only merge zero- and one-result operators due to the way that GVN
// is structured in the egraph implementation.
func.dfg.inst_results(inst).len() <= 1
// Loads/stores are handled by alias analysis and not
// otherwise mergeable.
//
// However, `readonly` loads *are* mergeable. Note that
// `is_mergeable` is checked after `is_pure`, and readonly +
// notrap + can_move loads are pure. Loads that are just
// `readonly` are not pure (we must execute them, for their
// potential trap side-effects, and for the same reason we
// cannot hoist them arbitrarily), but one `readonly` load
// subsuming another *is* a valid reason to make the second
// reuse the first's result: `readonly` promises that once we
// do the load, any subsequent load of the same address is
// always the same.
//
// We don't let that case fall back to alias analysis because
// its analysis is strictly more conservative: e.g. it will
// not permit this merging across a call, while `readonly`
// still promises that the value is constant across a call.
&& (!op.can_load() || is_readonly_load)
&& !op.can_store()
// Can only have idempotent side-effects.
&& (!has_side_effect(func, inst) || op.side_effects_idempotent() || is_readonly_load)
}
/// Does the given instruction have any side-effect as per [has_side_effect], or else is a load,
/// but not the get_pinned_reg opcode?
///
/// Loads are included so that lowering colors them as side-effecting, which is
/// what keeps a load from being merged into a consumer across an intervening
/// store. Deciding whether a load has to be *emitted* is a different question;
/// see [`must_lower_even_if_unused`].
pub fn has_lowering_side_effect(func: &Function, inst: Inst) -> bool {
let op = func.dfg.insts[inst].opcode();
op != Opcode::GetPinnedReg && (has_side_effect(func, inst) || op.can_load())
}
/// Must lowering emit the given instruction even when none of its results are
/// used?
///
/// This is [has_lowering_side_effect] without its "or is a load" clause: a load
/// that is defined not to trap has no effect of its own, so if nothing wants the
/// value it read there is no reason to emit it.
pub fn must_lower_even_if_unused(func: &Function, inst: Inst) -> bool {
let op = func.dfg.insts[inst].opcode();
op != Opcode::GetPinnedReg && has_side_effect(func, inst)
}
/// Is the given instruction a constant value (`iconst`, `fconst`) that can be
/// represented in 64 bits?
pub fn is_constant_64bit(func: &Function, inst: Inst) -> Option<u64> {
match &func.dfg.insts[inst] {
&InstructionData::UnaryImm { imm, .. } => Some(imm.bits() as u64),
&InstructionData::UnaryIeee16 { imm, .. } => Some(imm.bits() as u64),
&InstructionData::UnaryIeee32 { imm, .. } => Some(imm.bits() as u64),
&InstructionData::UnaryIeee64 { imm, .. } => Some(imm.bits()),
_ => None,
}
}
/// Get the address, offset, and access type from the given instruction, if any.
pub fn inst_addr_offset_type(func: &Function, inst: Inst) -> Option<(Value, Offset32, Type)> {
match &func.dfg.insts[inst] {
InstructionData::Load { arg, offset, .. } => {
let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
Some((*arg, *offset, ty))
}
InstructionData::LoadNoOffset { arg, .. } => {
let ty = func.dfg.value_type(func.dfg.inst_results(inst)[0]);
Some((*arg, 0.into(), ty))
}
InstructionData::Store { args, offset, .. } => {
let ty = func.dfg.value_type(args[0]);
Some((args[1], *offset, ty))
}
InstructionData::StoreNoOffset { args, .. } => {
let ty = func.dfg.value_type(args[0]);
Some((args[1], 0.into(), ty))
}
_ => None,
}
}
/// Get the store data, if any, from an instruction.
pub fn inst_store_data(func: &Function, inst: Inst) -> Option<Value> {
match &func.dfg.insts[inst] {
InstructionData::Store { args, .. } | InstructionData::StoreNoOffset { args, .. } => {
Some(args[0])
}
_ => None,
}
}
/// Visit all successors of a block with a given visitor closure. The closure
/// arguments are the branch instruction that is used to reach the successor,
/// the successor block itself, and a flag indicating whether the block is
/// reached via an indirect branch.
pub(crate) fn visit_block_succs<F: FnMut(Inst, Block, bool)>(
f: &Function,
block: Block,
mut visit: F,
) {
if let Some(inst) = f.layout.last_inst(block) {
match &f.dfg.insts[inst] {
ir::InstructionData::Jump {
destination: dest, ..
} => {
visit(inst, dest.block(&f.dfg.value_lists), false);
}
ir::InstructionData::Brif {
blocks: [block_then, block_else],
..
} => {
visit(inst, block_then.block(&f.dfg.value_lists), false);
visit(inst, block_else.block(&f.dfg.value_lists), false);
}
ir::InstructionData::BranchTable { table, .. } => {
let pool = &f.dfg.value_lists;
let table = &f.stencil.dfg.jump_tables[*table];
// The default block is also an indirect branch target on
// backends that include it in the jump table (aarch64).
// We visit the default block first explicitly, to mirror the
// traversal order of `JumpTableData::all_branches`, and
// transitively the order of `InstructionData::branch_destination`.
//
// Additionally, this case is why we are unable to replace this
// whole function with a loop over `branch_destination`: we need
// to report which branch targets are reached indirectly.
visit(inst, table.default_block().block(pool), true);
for dest in table.as_slice() {
visit(inst, dest.block(pool), true);
}
}
ir::InstructionData::TryCall { exception, .. }
| ir::InstructionData::TryCallIndirect { exception, .. } => {
let pool = &f.dfg.value_lists;
let exdata = &f.stencil.dfg.exception_tables[*exception];
// Exception handlers are resumed into via an indirect branch
// from the unwinder, so they are indirect branch targets too.
// The last target is the normal-return path, which is reached
// directly after the call returns.
let (normal, handlers) = exdata.all_branches().split_last().unwrap();
for dest in handlers {
visit(inst, dest.block(pool), true);
}
visit(inst, normal.block(pool), false);
}
inst => debug_assert!(!inst.opcode().is_branch()),
}
}
}