use std::collections::{HashMap, HashSet};
use std::sync::atomic::{AtomicU32, Ordering};
use crate::compiler::maglev::ir::{BasicBlock, ControlNode, MaglevGraph, NodeId, ValueNode};
use crate::compiler::maglev::licm;
static OPT_GLOBALS_PROMOTED: AtomicU32 = AtomicU32::new(0);
static OPT_GLOBALS_SKIPPED: AtomicU32 = AtomicU32::new(0);
pub fn globals_promoted_diagnostics() -> (u32, u32) {
(
OPT_GLOBALS_PROMOTED.load(Ordering::Relaxed),
OPT_GLOBALS_SKIPPED.load(Ordering::Relaxed),
)
}
pub fn optimize(graph: &mut MaglevGraph) {
let _block_count = graph.blocks().len();
let _node_count: usize = graph.blocks().iter().map(|b| b.nodes.len()).sum();
fold_constants(graph);
let _truncations = propagate_int32_truncation(graph);
simplify_identities(graph);
reassociate_arithmetic(graph);
strength_reduce(graph);
crate::compiler::maglev::range_analysis::eliminate_overflow_checks(graph);
strength_reduce(graph);
reassociate_arithmetic(graph);
eliminate_trivial_phis(graph);
let _licm_hoisted = crate::compiler::maglev::licm::hoist_loop_invariants(graph);
eliminate_common_subexpressions(graph);
let _globals_promoted = promote_loop_globals_counted(graph);
eliminate_trivial_phis(graph);
let _licm_hoisted2 = crate::compiler::maglev::licm::hoist_loop_invariants(graph);
crate::compiler::maglev::range_analysis::eliminate_overflow_checks(graph);
strength_reduce(graph);
reassociate_arithmetic(graph);
let _inv_chains = crate::compiler::maglev::licm::fold_invariant_addition_chains(graph);
let _truncations2 = propagate_int32_truncation(graph);
eliminate_identity_operations_global(graph);
eliminate_redundant_type_guards(graph);
specialize_closure_calls(graph);
fuse_call_loops(graph);
fuse_all_loops(graph);
mark_inlining_candidates(graph);
remove_redundant_check_maps(graph);
fuse_object_literal_stores(graph);
forward_invariant_object_properties(graph);
eliminate_store_to_load(graph);
fuse_fill_true_loops(graph);
fuse_count_truthy_loops(graph);
fold_constants(graph);
crate::compiler::maglev::licm::fold_invariant_addition_chains(graph);
fold_constants(graph);
eliminate_dead_code(graph);
lower_constant_accumulator_adds(graph);
eliminate_constant_accumulator_loops(graph);
forward_loop_object_properties(graph);
eliminate_dead_object_stores(graph);
eliminate_dead_allocations(graph);
replace_dead_arguments(graph);
unroll_simple_loops(graph);
reassociate_arithmetic(graph);
eliminate_identity_operations_global(graph);
eliminate_dead_code(graph);
eliminate_trivial_phis(graph);
eliminate_dead_counted_loops(graph);
eliminate_dead_code(graph);
}
fn fold_constants(graph: &mut MaglevGraph) {
let mut consts: HashMap<NodeId, ConstVal> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts.insert(*id, ConstVal::I32(*value));
}
ValueNode::Float64Constant { value } => {
consts.insert(*id, ConstVal::F64(*value));
}
_ => {}
}
}
}
for block in graph.blocks_mut() {
fold_block_constants(block, &mut consts);
}
}
#[derive(Clone, Copy)]
enum ConstVal {
I32(i32),
F64(f64),
}
fn fold_block_constants(block: &mut BasicBlock, consts: &mut HashMap<NodeId, ConstVal>) {
for (id, node) in &mut block.nodes {
match node {
ValueNode::Int32Constant { value } => {
consts.insert(*id, ConstVal::I32(*value));
continue;
}
ValueNode::SmiConstant { value } => {
consts.insert(*id, ConstVal::I32(*value));
continue;
}
ValueNode::Float64Constant { value } => {
consts.insert(*id, ConstVal::F64(*value));
continue;
}
_ => {}
}
let folded: Option<ValueNode> = match node {
ValueNode::Int32Add { left, right } | ValueNode::CheckedSmiAdd { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a.wrapping_add(b))
}
ValueNode::Int32Subtract { left, right }
| ValueNode::CheckedSmiSubtract { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a.wrapping_sub(b))
}
ValueNode::Int32Multiply { left, right }
| ValueNode::CheckedSmiMultiply { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a.wrapping_mul(b))
}
ValueNode::Int32Divide { left, right }
| ValueNode::CheckedSmiDivide { left, right } => {
if let (Some(ConstVal::I32(a)), Some(ConstVal::I32(b))) =
(consts.get(left), consts.get(right))
{
let (a, b) = (*a, *b);
if b != 0 {
Some(ValueNode::Int32Constant { value: a / b })
} else {
None
}
} else {
None
}
}
ValueNode::Int32Modulus { left, right }
| ValueNode::CheckedSmiModulus { left, right } => {
if let (Some(ConstVal::I32(a)), Some(ConstVal::I32(b))) =
(consts.get(left), consts.get(right))
{
let (a, b) = (*a, *b);
if b != 0 {
Some(ValueNode::Int32Constant { value: a % b })
} else {
None
}
} else {
None
}
}
ValueNode::Int32Negate { value } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::Int32Constant {
value: v.wrapping_neg(),
})
} else {
None
}
}
ValueNode::Int32Increment { value } | ValueNode::CheckedSmiIncrement { value } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::Int32Constant {
value: v.wrapping_add(1),
})
} else {
None
}
}
ValueNode::Int32Decrement { value } | ValueNode::CheckedSmiDecrement { value } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::Int32Constant {
value: v.wrapping_sub(1),
})
} else {
None
}
}
ValueNode::Float64Add { left, right } => {
fold_f64_bin(left, right, consts, |a, b| a + b)
}
ValueNode::Float64Subtract { left, right } => {
fold_f64_bin(left, right, consts, |a, b| a - b)
}
ValueNode::Float64Multiply { left, right } => {
fold_f64_bin(left, right, consts, |a, b| a * b)
}
ValueNode::Float64Divide { left, right } => {
fold_f64_bin(left, right, consts, |a, b| a / b)
}
ValueNode::Float64Modulus { left, right } => {
fold_f64_bin(left, right, consts, |a, b| a % b)
}
ValueNode::Float64Negate { value } => {
if let Some(ConstVal::F64(v)) = consts.get(value) {
Some(ValueNode::Float64Constant { value: -*v })
} else {
None
}
}
ValueNode::Int32BitwiseOr { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a | b)
}
ValueNode::Int32BitwiseAnd { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a & b)
}
ValueNode::Int32BitwiseXor { left, right } => {
fold_i32_bin(left, right, consts, |a, b| a ^ b)
}
ValueNode::GenericAdd { left, right, .. } => {
fold_smi_bin(left, right, consts, |a, b| a.wrapping_add(b))
}
ValueNode::GenericSubtract { left, right, .. } => {
fold_smi_bin(left, right, consts, |a, b| a.wrapping_sub(b))
}
ValueNode::GenericMultiply { left, right, .. } => {
fold_smi_bin(left, right, consts, |a, b| a.wrapping_mul(b))
}
ValueNode::GenericIncrement { value, .. } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::SmiConstant {
value: v.wrapping_add(1),
})
} else {
None
}
}
ValueNode::GenericDecrement { value, .. } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::SmiConstant {
value: v.wrapping_sub(1),
})
} else {
None
}
}
ValueNode::GenericNegate { value, .. } => {
if let Some(ConstVal::I32(v)) = consts.get(value) {
Some(ValueNode::SmiConstant {
value: v.wrapping_neg(),
})
} else {
None
}
}
_ => None,
};
if let Some(replacement) = folded {
match &replacement {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts.insert(*id, ConstVal::I32(*value));
}
ValueNode::Float64Constant { value } => {
consts.insert(*id, ConstVal::F64(*value));
}
_ => {}
}
*node = replacement;
}
}
}
fn fold_i32_bin(
left: &NodeId,
right: &NodeId,
consts: &HashMap<NodeId, ConstVal>,
op: impl Fn(i32, i32) -> i32,
) -> Option<ValueNode> {
if let (Some(ConstVal::I32(a)), Some(ConstVal::I32(b))) = (consts.get(left), consts.get(right))
{
Some(ValueNode::Int32Constant { value: op(*a, *b) })
} else {
None
}
}
fn fold_smi_bin(
left: &NodeId,
right: &NodeId,
consts: &HashMap<NodeId, ConstVal>,
op: impl Fn(i32, i32) -> i32,
) -> Option<ValueNode> {
if let (Some(ConstVal::I32(a)), Some(ConstVal::I32(b))) = (consts.get(left), consts.get(right))
{
Some(ValueNode::SmiConstant { value: op(*a, *b) })
} else {
None
}
}
fn fold_f64_bin(
left: &NodeId,
right: &NodeId,
consts: &HashMap<NodeId, ConstVal>,
op: impl Fn(f64, f64) -> f64,
) -> Option<ValueNode> {
let lv = match consts.get(left) {
Some(ConstVal::F64(v)) => *v,
Some(ConstVal::I32(v)) => *v as f64,
None => return None,
};
let rv = match consts.get(right) {
Some(ConstVal::F64(v)) => *v,
Some(ConstVal::I32(v)) => *v as f64,
None => return None,
};
Some(ValueNode::Float64Constant { value: op(lv, rv) })
}
fn propagate_int32_truncation(graph: &mut MaglevGraph) -> usize {
let mut use_counts: HashMap<NodeId, usize> = HashMap::new();
for block in graph.blocks() {
for (_, node) in &block.nodes {
if matches!(
node,
ValueNode::CheckSmi { .. } | ValueNode::StoreGlobal { .. }
) {
continue;
}
visit_value_node_inputs(node, &mut |id| {
*use_counts.entry(id).or_insert(0) += 1;
});
}
if let Some(ctrl) = &block.control {
visit_control_inputs(ctrl, &mut |id| {
*use_counts.entry(id).or_insert(0) += 1;
});
}
}
let mut node_map: HashMap<NodeId, ValueNode> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
node_map.insert(*id, node.clone());
}
}
let mut replacements: HashMap<NodeId, ValueNode> = HashMap::new();
for block in graph.blocks() {
for (_node_id, node) in &block.nodes {
match node {
ValueNode::Int32BitwiseOr { left, right }
| ValueNode::Int32BitwiseXor { left, right }
| ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::Int32ShiftLeft { left, right }
| ValueNode::Int32ShiftRight { left, right }
| ValueNode::Int32ShiftRightLogical { left, right }
| ValueNode::GenericBitwiseOr { left, right, .. }
| ValueNode::GenericBitwiseXor { left, right, .. }
| ValueNode::GenericBitwiseAnd { left, right, .. }
| ValueNode::GenericShiftLeft { left, right, .. }
| ValueNode::GenericShiftRight { left, right, .. }
| ValueNode::GenericShiftRightLogical { left, right, .. } => {
mark_truncated(*left, &use_counts, &node_map, &mut replacements);
mark_truncated(*right, &use_counts, &node_map, &mut replacements);
}
_ => {}
}
}
}
let count = replacements.len();
if !replacements.is_empty() {
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
if let Some(new_node) = replacements.remove(id) {
*node = new_node;
}
}
}
}
count
}
fn mark_truncated(
id: NodeId,
use_counts: &HashMap<NodeId, usize>,
node_map: &HashMap<NodeId, ValueNode>,
replacements: &mut HashMap<NodeId, ValueNode>,
) {
if replacements.contains_key(&id) {
return;
}
let uc = use_counts.get(&id);
if uc != Some(&1) {
return;
}
let Some(node) = node_map.get(&id) else {
return;
};
match node {
ValueNode::CheckedSmiAdd { left, right } => {
replacements.insert(
id,
ValueNode::Int32Add {
left: *left,
right: *right,
},
);
mark_truncated(*left, use_counts, node_map, replacements);
mark_truncated(*right, use_counts, node_map, replacements);
return;
}
ValueNode::CheckedSmiSubtract { left, right } => {
replacements.insert(
id,
ValueNode::Int32Subtract {
left: *left,
right: *right,
},
);
mark_truncated(*left, use_counts, node_map, replacements);
mark_truncated(*right, use_counts, node_map, replacements);
return;
}
ValueNode::CheckedSmiMultiply { left, right } => {
replacements.insert(
id,
ValueNode::Int32Multiply {
left: *left,
right: *right,
},
);
mark_truncated(*left, use_counts, node_map, replacements);
mark_truncated(*right, use_counts, node_map, replacements);
return;
}
ValueNode::CheckedSmiIncrement { value } => {
replacements.insert(id, ValueNode::Int32Increment { value: *value });
mark_truncated(*value, use_counts, node_map, replacements);
return;
}
ValueNode::CheckedSmiDecrement { value } => {
replacements.insert(id, ValueNode::Int32Decrement { value: *value });
mark_truncated(*value, use_counts, node_map, replacements);
return;
}
_ => {}
}
match node {
ValueNode::GenericAdd { left, right, .. }
| ValueNode::GenericSubtract { left, right, .. }
| ValueNode::GenericMultiply { left, right, .. } => {
mark_truncated(*left, use_counts, node_map, replacements);
mark_truncated(*right, use_counts, node_map, replacements);
if !is_provably_i32(*left, replacements, node_map)
|| !is_provably_i32(*right, replacements, node_map)
{
return;
}
let new_node = match node {
ValueNode::GenericAdd { left, right, .. } => ValueNode::Int32Add {
left: *left,
right: *right,
},
ValueNode::GenericSubtract { left, right, .. } => ValueNode::Int32Subtract {
left: *left,
right: *right,
},
ValueNode::GenericMultiply { left, right, .. } => ValueNode::Int32Multiply {
left: *left,
right: *right,
},
_ => unreachable!(),
};
replacements.insert(id, new_node);
}
ValueNode::GenericIncrement { value, .. } => {
mark_truncated(*value, use_counts, node_map, replacements);
if !is_provably_i32(*value, replacements, node_map) {
return;
}
replacements.insert(id, ValueNode::Int32Increment { value: *value });
}
ValueNode::GenericDecrement { value, .. } => {
mark_truncated(*value, use_counts, node_map, replacements);
if !is_provably_i32(*value, replacements, node_map) {
return;
}
replacements.insert(id, ValueNode::Int32Decrement { value: *value });
}
_ => {}
}
}
fn is_provably_i32(
id: NodeId,
replacements: &HashMap<NodeId, ValueNode>,
node_map: &HashMap<NodeId, ValueNode>,
) -> bool {
if replacements.contains_key(&id) {
return true;
}
let Some(node) = node_map.get(&id) else {
return false;
};
matches!(
node,
ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Int32Add { .. }
| ValueNode::Int32Subtract { .. }
| ValueNode::Int32Multiply { .. }
| ValueNode::Int32Negate { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::Int32Decrement { .. }
| ValueNode::Int32BitwiseOr { .. }
| ValueNode::Int32BitwiseAnd { .. }
| ValueNode::Int32BitwiseXor { .. }
| ValueNode::Int32ShiftLeft { .. }
| ValueNode::Int32ShiftRight { .. }
| ValueNode::Int32ShiftRightLogical { .. }
| ValueNode::GenericBitwiseOr { .. }
| ValueNode::GenericBitwiseAnd { .. }
| ValueNode::GenericBitwiseXor { .. }
| ValueNode::GenericBitwiseNot { .. }
| ValueNode::Phi { .. }
)
}
#[allow(clippy::too_many_lines)]
fn visit_value_node_inputs(node: &ValueNode, f: &mut impl FnMut(NodeId)) {
match node {
ValueNode::SmiConstant { .. }
| ValueNode::Float64Constant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Uint32Constant { .. }
| ValueNode::BigIntConstant { .. }
| ValueNode::TrueConstant
| ValueNode::FalseConstant
| ValueNode::NullConstant
| ValueNode::UndefinedConstant
| ValueNode::RootConstant { .. }
| ValueNode::ExternalConstant { .. }
| ValueNode::StringConstant { .. }
| ValueNode::ConstantPoolEntry { .. }
| ValueNode::Parameter { .. }
| ValueNode::RegisterInput { .. }
| ValueNode::ArgumentsLength
| ValueNode::RestLength
| ValueNode::LoadGlobal { .. }
| ValueNode::LoadCurrentContextSlot { .. }
| ValueNode::ArgumentsElements { .. }
| ValueNode::RestElements { .. }
| ValueNode::VirtualObject { .. }
| ValueNode::CreateFunctionContext { .. }
| ValueNode::CreateBlockContext { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
| ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateMappedArguments
| ValueNode::CreateUnmappedArguments
| ValueNode::CreateRestParameter
| ValueNode::CreateRegExpLiteral { .. }
| ValueNode::CreateClosure { .. }
| ValueNode::FastCreateClosure { .. }
| ValueNode::GetTemplateObject { .. }
| ValueNode::Debugger
| ValueNode::Abort { .. } => {}
ValueNode::GetArgument { index } => f(*index),
ValueNode::CheckedSmiIncrement { value }
| ValueNode::CheckedSmiDecrement { value }
| ValueNode::Int32Negate { value }
| ValueNode::Int32Increment { value }
| ValueNode::Int32Decrement { value }
| ValueNode::Float64Negate { value }
| ValueNode::Float64Ieee754Unary { value, .. }
| ValueNode::GenericBitwiseNot { value, .. }
| ValueNode::GenericNegate { value, .. }
| ValueNode::GenericIncrement { value, .. }
| ValueNode::GenericDecrement { value, .. }
| ValueNode::ChangeInt32ToFloat64 { input: value }
| ValueNode::ChangeUint32ToFloat64 { input: value }
| ValueNode::ChangeFloat64ToInt32 { input: value }
| ValueNode::CheckedFloat64ToInt32 { input: value }
| ValueNode::ChangeInt32ToTagged { input: value }
| ValueNode::ChangeUint32ToTagged { input: value }
| ValueNode::ChangeFloat64ToTagged { input: value }
| ValueNode::ChangeTaggedToInt32 { input: value }
| ValueNode::ChangeTaggedToUint32 { input: value }
| ValueNode::ChangeTaggedToFloat64 { input: value }
| ValueNode::CheckedTaggedToInt32 { input: value }
| ValueNode::CheckedTaggedToFloat64 { input: value }
| ValueNode::ToBoolean { value }
| ValueNode::TestNullOrUndefined { value }
| ValueNode::ToString { value, .. }
| ValueNode::ToObject { value, .. }
| ValueNode::ToName { value, .. }
| ValueNode::ToNumber { value, .. }
| ValueNode::ToNumberOrNumeric { value, .. }
| ValueNode::TypeOf { value }
| ValueNode::NumberToString { value, .. } => f(*value),
ValueNode::CheckSmi { receiver }
| ValueNode::CheckNumber { receiver }
| ValueNode::CheckHeapObject { receiver }
| ValueNode::CheckSymbol { receiver }
| ValueNode::CheckString { receiver }
| ValueNode::CheckStringOrStringWrapper { receiver }
| ValueNode::CheckSeqOneByteString { receiver }
| ValueNode::CheckMaps { receiver, .. }
| ValueNode::CheckMapsWithMigration { receiver, .. }
| ValueNode::CheckValue { receiver, .. } => f(*receiver),
ValueNode::CheckDynamicValue { receiver, expected } => {
f(*receiver);
f(*expected);
}
ValueNode::CheckInt32IsSmi { input }
| ValueNode::CheckUint32IsSmi { input }
| ValueNode::CheckHoleyFloat64IsSmi { input }
| ValueNode::CheckFloat64IsNan { input } => f(*input),
ValueNode::TestTypeOf { value, .. } | ValueNode::TestUndetectable { value } => f(*value),
ValueNode::LoadField { object, .. }
| ValueNode::LoadTaggedField { object, .. }
| ValueNode::LoadDoubleField { object, .. }
| ValueNode::LoadNamedGeneric { object, .. }
| ValueNode::ForInPrepare {
enumerator: object, ..
}
| ValueNode::StringLength { string: object } => f(*object),
ValueNode::LoadEnumCacheLength { map } => f(*map),
ValueNode::LoadKeyedGeneric { object, key, .. } => {
f(*object);
f(*key);
}
ValueNode::HasInPrototypeChain { object, prototype } => {
f(*object);
f(*prototype);
}
ValueNode::StoreField { object, value, .. } => {
f(*object);
f(*value);
}
ValueNode::StoreCurrentContextSlot { value, .. } | ValueNode::StoreGlobal { value, .. } => {
f(*value)
}
ValueNode::LoadContextSlot { context, .. } => f(*context),
ValueNode::StoreContextSlot { context, value, .. } => {
f(*context);
f(*value);
}
ValueNode::PushContext { context } | ValueNode::PopContext { context } => f(*context),
ValueNode::LoadFixedArrayElement { elements, index }
| ValueNode::LoadFixedDoubleArrayElement { elements, index }
| ValueNode::LoadHoleyFixedDoubleArrayElement { elements, index } => {
f(*elements);
f(*index);
}
ValueNode::StoreFixedArrayElement {
elements,
index,
value,
}
| ValueNode::StoreFixedDoubleArrayElement {
elements,
index,
value,
} => {
f(*elements);
f(*index);
f(*value);
}
ValueNode::StoreNamedGeneric { object, value, .. } => {
f(*object);
f(*value);
}
ValueNode::CreateObjectLiteralWithProperties { values, .. } => {
for &v in values {
f(v);
}
}
ValueNode::StoreKeyedGeneric {
object, key, value, ..
} => {
f(*object);
f(*key);
f(*value);
}
ValueNode::CheckedSmiAdd { left, right }
| ValueNode::CheckedSmiSubtract { left, right }
| ValueNode::CheckedSmiMultiply { left, right }
| ValueNode::CheckedSmiDivide { left, right }
| ValueNode::CheckedSmiModulus { left, right }
| ValueNode::Int32Add { left, right }
| ValueNode::Int32Subtract { left, right }
| ValueNode::Int32Multiply { left, right }
| ValueNode::Int32Divide { left, right }
| ValueNode::Int32Modulus { left, right }
| ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::Int32BitwiseOr { left, right }
| ValueNode::Int32BitwiseXor { left, right }
| ValueNode::Int32ShiftLeft { left, right }
| ValueNode::Int32ShiftRight { left, right }
| ValueNode::Int32ShiftRightLogical { left, right }
| ValueNode::Uint32Add { left, right }
| ValueNode::Uint32Subtract { left, right }
| ValueNode::Uint32Multiply { left, right }
| ValueNode::Uint32Divide { left, right }
| ValueNode::Uint32Modulus { left, right }
| ValueNode::Float64Add { left, right }
| ValueNode::Float64Subtract { left, right }
| ValueNode::Float64Multiply { left, right }
| ValueNode::Float64Divide { left, right }
| ValueNode::Float64Modulus { left, right }
| ValueNode::Float64Exponentiate { left, right }
| ValueNode::Int32Equal { left, right }
| ValueNode::Int32StrictEqual { left, right }
| ValueNode::Int32LessThan { left, right }
| ValueNode::Int32LessThanOrEqual { left, right }
| ValueNode::Int32GreaterThan { left, right }
| ValueNode::Int32GreaterThanOrEqual { left, right }
| ValueNode::Float64Equal { left, right }
| ValueNode::Float64LessThan { left, right }
| ValueNode::Float64LessThanOrEqual { left, right }
| ValueNode::Float64GreaterThan { left, right }
| ValueNode::Float64GreaterThanOrEqual { left, right }
| ValueNode::StringConcat { left, right }
| ValueNode::StringEqual { left, right }
| ValueNode::GenericAdd { left, right, .. }
| ValueNode::GenericSubtract { left, right, .. }
| ValueNode::GenericMultiply { left, right, .. }
| ValueNode::GenericDivide { left, right, .. }
| ValueNode::GenericModulus { left, right, .. }
| ValueNode::GenericExponentiate { left, right, .. }
| ValueNode::GenericBitwiseAnd { left, right, .. }
| ValueNode::GenericBitwiseOr { left, right, .. }
| ValueNode::GenericBitwiseXor { left, right, .. }
| ValueNode::GenericShiftLeft { left, right, .. }
| ValueNode::GenericShiftRight { left, right, .. }
| ValueNode::GenericShiftRightLogical { left, right, .. }
| ValueNode::TaggedEqual { left, right, .. }
| ValueNode::TaggedNotEqual { left, right, .. } => {
f(*left);
f(*right);
}
ValueNode::CheckInt32Condition { left, right, .. } => {
f(*left);
f(*right);
}
ValueNode::CheckCacheIndicesNotCleared { receiver, indices } => {
f(*receiver);
f(*indices);
}
ValueNode::TestInstanceOf {
object, callable, ..
} => {
f(*object);
f(*callable);
}
ValueNode::TestIn { key, object, .. } => {
f(*key);
f(*object);
}
ValueNode::StringAt { string, index } => {
f(*string);
f(*index);
}
ValueNode::ForInNext {
receiver,
cache_index,
cache_array,
..
} => {
f(*receiver);
f(*cache_index);
f(*cache_array);
}
ValueNode::DeleteProperty { object, key, .. } => {
f(*object);
f(*key);
}
ValueNode::CreateCatchContext { exception, .. } => f(*exception),
ValueNode::CreateWithContext { object, .. } => f(*object),
ValueNode::Call {
callee,
receiver,
args,
..
}
| ValueNode::CallWithSpread {
callee,
receiver,
args,
..
}
| ValueNode::CallKnownFunction {
callee,
receiver,
args,
} => {
f(*callee);
f(*receiver);
for a in args {
f(*a);
}
}
ValueNode::CallArrayPush { receiver, args, .. } => {
f(*receiver);
for a in args {
f(*a);
}
}
ValueNode::CallBuiltin { args, .. } | ValueNode::CallRuntime { args, .. } => {
for a in args {
f(*a);
}
}
ValueNode::SpeculativeCallFusion { callee, .. } => f(*callee),
ValueNode::SpeculativeSumFusion { array } => f(*array),
ValueNode::SpeculativePushFusion { array, .. } => f(*array),
ValueNode::SpeculativeFillTrueFusion { array, count } => {
f(*array);
f(*count);
}
ValueNode::SpeculativeCountTruthyFusion { array, count } => {
f(*array);
f(*count);
}
ValueNode::Construct {
constructor, args, ..
}
| ValueNode::ConstructWithSpread {
constructor, args, ..
} => {
f(*constructor);
for a in args {
f(*a);
}
}
ValueNode::Phi { inputs } => {
for id in inputs {
f(*id);
}
}
}
}
fn visit_control_inputs(ctrl: &ControlNode, f: &mut impl FnMut(NodeId)) {
match ctrl {
ControlNode::Return { value } => f(*value),
ControlNode::Branch { condition, .. } => f(*condition),
ControlNode::Jump { .. } | ControlNode::Deoptimize { .. } => {}
}
}
fn eliminate_trivial_phis(graph: &mut MaglevGraph) {
loop {
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for block in graph.blocks() {
for &(id, ref node) in &block.nodes {
if let ValueNode::Phi { inputs } = node {
let mut unique_external = None;
let mut is_trivial = true;
for &inp in inputs {
if inp == id {
continue; }
match unique_external {
None => unique_external = Some(inp),
Some(prev) if prev == inp => {} Some(_) => {
is_trivial = false;
break;
}
}
}
if is_trivial && let Some(replacement) = unique_external {
subst.insert(id, replacement);
}
}
}
}
if subst.is_empty() {
break;
}
for _ in 0..subst.len() {
let mut changed = false;
let keys: Vec<NodeId> = subst.keys().copied().collect();
for key in keys {
if let Some(&further) = subst.get(&subst[&key])
&& subst[&key] != further
{
subst.insert(key, further);
changed = true;
}
}
if !changed {
break;
}
}
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
if subst.contains_key(id) {
*node = ValueNode::UndefinedConstant;
}
}
}
for block in graph.blocks_mut() {
apply_subst_to_block(block, &subst);
}
}
}
fn simplify_identities(graph: &mut MaglevGraph) {
for block in graph.blocks_mut() {
simplify_identities_in_block(block);
}
}
fn simplify_identities_in_block(block: &mut BasicBlock) {
let mut consts: HashMap<NodeId, i32> = HashMap::new();
for (id, node) in &block.nodes {
match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
if consts.is_empty() {
return;
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (id, node) in &mut block.nodes {
let replacement: Option<NodeId> = match node {
ValueNode::Int32Add { left, right } | ValueNode::CheckedSmiAdd { left, right } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else if consts.get(left) == Some(&0) {
Some(*right)
} else {
None
}
}
ValueNode::Int32Subtract { left, right }
| ValueNode::CheckedSmiSubtract { left, right } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else {
None
}
}
ValueNode::Int32Multiply { left, right }
| ValueNode::CheckedSmiMultiply { left, right } => {
if consts.get(right) == Some(&1) {
Some(*left)
} else if consts.get(left) == Some(&1) || consts.get(right) == Some(&0) {
Some(*right)
} else if consts.get(left) == Some(&0) {
Some(*left)
} else {
None
}
}
ValueNode::Int32BitwiseOr { left, right } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else if consts.get(left) == Some(&0) {
Some(*right)
} else {
None
}
}
ValueNode::Int32BitwiseXor { left, right }
| ValueNode::GenericBitwiseXor { left, right, .. } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else if consts.get(left) == Some(&0) {
Some(*right)
} else {
None
}
}
ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::GenericBitwiseAnd { left, right, .. } => {
if consts.get(right) == Some(&-1) {
Some(*left)
} else if consts.get(left) == Some(&-1) {
Some(*right)
} else {
None
}
}
_ => None,
};
if let Some(canonical_id) = replacement {
subst.insert(*id, canonical_id);
*node = ValueNode::UndefinedConstant;
}
}
if !subst.is_empty() {
apply_subst_to_block(block, &subst);
}
}
fn eliminate_identity_operations_global(graph: &mut MaglevGraph) {
let mut consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
}
if consts.is_empty() {
return;
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
let replacement: Option<NodeId> = match node {
ValueNode::Int32BitwiseOr { left, right }
| ValueNode::GenericBitwiseOr { left, right, .. } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else if consts.get(left) == Some(&0) {
Some(*right)
} else {
None
}
}
ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::GenericBitwiseAnd { left, right, .. } => {
if consts.get(right) == Some(&-1) {
Some(*left)
} else if consts.get(left) == Some(&-1) {
Some(*right)
} else {
None
}
}
ValueNode::Int32Add { left, right }
| ValueNode::CheckedSmiAdd { left, right }
| ValueNode::GenericAdd { left, right, .. } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else if consts.get(left) == Some(&0) {
Some(*right)
} else {
None
}
}
ValueNode::Int32Subtract { left, right }
| ValueNode::CheckedSmiSubtract { left, right }
| ValueNode::GenericSubtract { left, right, .. } => {
if consts.get(right) == Some(&0) {
Some(*left)
} else {
None
}
}
ValueNode::Int32Multiply { left, right }
| ValueNode::CheckedSmiMultiply { left, right }
| ValueNode::GenericMultiply { left, right, .. } => {
if consts.get(right) == Some(&1) {
Some(*left)
} else if consts.get(left) == Some(&1) {
Some(*right)
} else {
None
}
}
_ => None,
};
if let Some(canonical_id) = replacement {
subst.insert(*id, canonical_id);
*node = ValueNode::UndefinedConstant;
}
}
}
if subst.is_empty() {
return;
}
for block in graph.blocks_mut() {
apply_subst_to_block(block, &subst);
}
}
fn reassociate_arithmetic(graph: &mut MaglevGraph) {
loop {
let changed = reassociate_arithmetic_once(graph);
if changed == 0 {
break;
}
}
}
fn reassociate_arithmetic_once(graph: &mut MaglevGraph) -> usize {
let mut next_id = graph
.blocks()
.iter()
.flat_map(|b| b.nodes.iter())
.map(|(id, _)| id.0)
.max()
.map_or(0, |m| m + 1);
let mut global_consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if let ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } = node {
global_consts.insert(*id, *value);
}
}
}
let mut count = 0;
for block in graph.blocks_mut() {
count += reassociate_block(block, &mut next_id, &mut global_consts);
}
count
}
struct Reassoc {
pos: usize,
new_node: ValueNode,
prefix: Vec<(NodeId, ValueNode)>,
}
fn reassociate_block(
block: &mut BasicBlock,
next_id: &mut u32,
global_consts: &mut HashMap<NodeId, i32>,
) -> usize {
let mut mul_info: HashMap<NodeId, (NodeId, i32)> = HashMap::new();
let mut node_defs: HashMap<NodeId, ValueNode> = HashMap::new();
for (id, node) in &block.nodes {
if let ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } = node {
global_consts.insert(*id, *value);
}
if let ValueNode::Int32Multiply { left, right } = node {
if let Some(&k) = global_consts.get(right) {
mul_info.insert(*id, (*left, k));
} else if let Some(&k) = global_consts.get(left) {
mul_info.insert(*id, (*right, k));
}
}
node_defs.insert(*id, node.clone());
}
for (pos, (_id, node)) in block.nodes.iter().enumerate() {
if let Some(r) = try_reassociate(node, pos, global_consts, &mul_info, &node_defs, next_id) {
return apply_reassoc(block, r);
}
}
0
}
fn try_reassociate(
node: &ValueNode,
pos: usize,
consts: &HashMap<NodeId, i32>,
mul_info: &HashMap<NodeId, (NodeId, i32)>,
node_defs: &HashMap<NodeId, ValueNode>,
next_id: &mut u32,
) -> Option<Reassoc> {
match node {
ValueNode::Int32Add { left, right } => {
if let Some(&(base, k)) = mul_info.get(left)
&& base == *right
{
return build_multiply_reassoc(pos, base, k + 1, consts, next_id);
}
if let Some(&(base, k)) = mul_info.get(right)
&& base == *left
{
return build_multiply_reassoc(pos, base, k + 1, consts, next_id);
}
if let Some(ValueNode::Int32Subtract {
left: sub_a,
right: sub_x,
}) = node_defs.get(left)
&& let Some(&(base, k)) = mul_info.get(right)
&& base == *sub_x
&& k > 1
{
return build_add_mul_reassoc(pos, *sub_a, base, k - 1, consts, next_id);
}
if let Some(ValueNode::Int32Add {
left: add_a,
right: add_b,
}) = node_defs.get(left)
{
if let Some(&(base, k)) = mul_info.get(add_b)
&& base == *right
{
return build_add_mul_reassoc(pos, *add_a, base, k + 1, consts, next_id);
}
if let Some(&(base, k)) = mul_info.get(add_a)
&& base == *right
{
return build_add_mul_reassoc(pos, *add_b, base, k + 1, consts, next_id);
}
}
if let Some(ValueNode::Int32Add {
left: add_a,
right: add_b,
}) = node_defs.get(right)
{
if let Some(&(base, k)) = mul_info.get(add_b)
&& base == *left
{
return build_add_mul_reassoc(pos, *add_a, base, k + 1, consts, next_id);
}
if let Some(&(base, k)) = mul_info.get(add_a)
&& base == *left
{
return build_add_mul_reassoc(pos, *add_b, base, k + 1, consts, next_id);
}
}
if let Some(ValueNode::Int32Subtract {
left: sub_a,
right: sub_k,
}) = node_defs.get(left)
&& consts.contains_key(sub_k)
{
let add_id = NodeId(*next_id);
*next_id += 1;
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Subtract {
left: add_id,
right: *sub_k,
},
prefix: vec![(
add_id,
ValueNode::Int32Add {
left: *sub_a,
right: *right,
},
)],
});
}
if let Some(ValueNode::Int32Subtract {
left: sub_b,
right: sub_k,
}) = node_defs.get(right)
&& consts.contains_key(sub_k)
{
let add_id = NodeId(*next_id);
*next_id += 1;
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Subtract {
left: add_id,
right: *sub_k,
},
prefix: vec![(
add_id,
ValueNode::Int32Add {
left: *left,
right: *sub_b,
},
)],
});
}
None
}
ValueNode::Int32Subtract { left, right } => {
if let Some(&(base, k)) = mul_info.get(left)
&& base == *right
&& k > 1
{
return build_multiply_reassoc(pos, base, k - 1, consts, next_id);
}
if let Some(&(base_l, k_l)) = mul_info.get(left)
&& let Some(&(base_r, k_r)) = mul_info.get(right)
&& base_l == base_r
&& k_l > k_r
{
return build_multiply_reassoc(pos, base_l, k_l - k_r, consts, next_id);
}
if let Some(&(base_r, k_r)) = mul_info.get(right)
&& let Some(ValueNode::Int32Add {
left: add_a,
right: add_b,
}) = node_defs.get(left)
{
if let Some(&(base_l, k_l)) = mul_info.get(add_b)
&& base_l == base_r
&& k_l >= k_r
{
return build_add_mul_reassoc(pos, *add_a, base_r, k_l - k_r, consts, next_id);
}
if let Some(&(base_l, k_l)) = mul_info.get(add_a)
&& base_l == base_r
&& k_l >= k_r
{
return build_add_mul_reassoc(pos, *add_b, base_r, k_l - k_r, consts, next_id);
}
}
if let Some(&k2) = consts.get(right)
&& let Some(ValueNode::Int32Subtract {
left: sub_a,
right: sub_k1,
}) = node_defs.get(left)
&& let Some(&k1) = consts.get(sub_k1)
{
let combined = k1.wrapping_add(k2);
let (const_id, prefix) = find_or_create_const(combined, consts, next_id);
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Subtract {
left: *sub_a,
right: const_id,
},
prefix,
});
}
if let Some(&k2) = consts.get(right)
&& let Some(ValueNode::Int32Add {
left: add_a,
right: add_k1,
}) = node_defs.get(left)
&& let Some(&k1) = consts.get(add_k1)
{
let diff = k1.wrapping_sub(k2);
if diff == 0 {
} else if diff > 0 {
let (const_id, prefix) = find_or_create_const(diff, consts, next_id);
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Add {
left: *add_a,
right: const_id,
},
prefix,
});
} else {
let (const_id, prefix) = find_or_create_const(-diff, consts, next_id);
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Subtract {
left: *add_a,
right: const_id,
},
prefix,
});
}
}
None
}
_ => None,
}
}
fn build_multiply_reassoc(
pos: usize,
base: NodeId,
new_k: i32,
consts: &HashMap<NodeId, i32>,
next_id: &mut u32,
) -> Option<Reassoc> {
if new_k <= 0 {
return None;
}
let (const_node_id, prefix) = find_or_create_const(new_k, consts, next_id);
Some(Reassoc {
pos,
new_node: ValueNode::Int32Multiply {
left: base,
right: const_node_id,
},
prefix,
})
}
fn build_add_mul_reassoc(
pos: usize,
addend: NodeId,
base: NodeId,
new_k: i32,
consts: &HashMap<NodeId, i32>,
next_id: &mut u32,
) -> Option<Reassoc> {
if new_k <= 0 {
return None;
}
if new_k == 1 {
return Some(Reassoc {
pos,
new_node: ValueNode::Int32Add {
left: addend,
right: base,
},
prefix: Vec::new(),
});
}
let (const_node_id, mut prefix) = find_or_create_const(new_k, consts, next_id);
let mul_id = NodeId(*next_id);
*next_id += 1;
prefix.push((
mul_id,
ValueNode::Int32Multiply {
left: base,
right: const_node_id,
},
));
Some(Reassoc {
pos,
new_node: ValueNode::Int32Add {
left: addend,
right: mul_id,
},
prefix,
})
}
fn find_or_create_const(
k: i32,
consts: &HashMap<NodeId, i32>,
next_id: &mut u32,
) -> (NodeId, Vec<(NodeId, ValueNode)>) {
if let Some((&id, _)) = consts.iter().find(|&(_, &v)| v == k) {
(id, Vec::new())
} else {
let id = NodeId(*next_id);
*next_id += 1;
(id, vec![(id, ValueNode::Int32Constant { value: k })])
}
}
fn apply_reassoc(block: &mut BasicBlock, r: Reassoc) -> usize {
let (node_id, _) = block.nodes[r.pos];
let prefix_len = r.prefix.len();
for (i, entry) in r.prefix.into_iter().enumerate() {
block.nodes.insert(r.pos + i, entry);
}
block.nodes[r.pos + prefix_len] = (node_id, r.new_node);
1
}
fn strength_reduce(graph: &mut MaglevGraph) {
let mut next_id = graph
.blocks()
.iter()
.flat_map(|b| b.nodes.iter())
.map(|(id, _)| id.0)
.max()
.map_or(0, |m| m + 1);
let mut global_consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if let ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } = node {
global_consts.insert(*id, *value);
}
}
}
for block in graph.blocks_mut() {
strength_reduce_block(block, &mut next_id, &global_consts);
}
}
fn strength_reduce_block(
block: &mut BasicBlock,
next_id: &mut u32,
global_consts: &HashMap<NodeId, i32>,
) {
let mut consts = global_consts.clone();
for (id, node) in &block.nodes {
match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
let mut reductions: Vec<(usize, NodeId, u32)> = Vec::new();
let mut shift_add_reductions: Vec<(usize, NodeId, u32, bool)> = Vec::new();
for (pos, (_, node)) in block.nodes.iter().enumerate() {
if let ValueNode::Int32Multiply { left, right } = node {
if let Some((operand, shift)) = find_power_of_two_operand(*left, *right, &consts) {
reductions.push((pos, operand, shift));
} else if let Some((operand, shift, is_add)) =
find_shift_add_decomposition(*left, *right, &consts)
{
shift_add_reductions.push((pos, operand, shift, is_add));
}
}
}
if reductions.is_empty() && shift_add_reductions.is_empty() {
return;
}
for (pos, operand, shift_amt, is_add) in shift_add_reductions.into_iter().rev() {
let shift_const_id = NodeId(*next_id);
*next_id += 1;
let shifted_id = NodeId(*next_id);
*next_id += 1;
let (mul_id, _) = block.nodes[pos];
block.nodes[pos] = (
mul_id,
if is_add {
ValueNode::Int32Add {
left: shifted_id,
right: operand,
}
} else {
ValueNode::Int32Subtract {
left: shifted_id,
right: operand,
}
},
);
block.nodes.insert(
pos,
(
shifted_id,
ValueNode::Int32ShiftLeft {
left: operand,
right: shift_const_id,
},
),
);
block.nodes.insert(
pos,
(
shift_const_id,
ValueNode::Int32Constant {
value: shift_amt as i32,
},
),
);
}
if !reductions.is_empty() {
let mut consts2: HashMap<NodeId, i32> = HashMap::new();
for (id, node) in &block.nodes {
match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
consts2.insert(*id, *value);
}
_ => {}
}
}
let mut pow2_reductions: Vec<(usize, NodeId, u32)> = Vec::new();
for (pos, (_, node)) in block.nodes.iter().enumerate() {
if let ValueNode::Int32Multiply { left, right } = node
&& let Some((operand, shift)) = find_power_of_two_operand(*left, *right, &consts2)
{
pow2_reductions.push((pos, operand, shift));
}
}
for (pos, operand, shift_amt) in pow2_reductions.into_iter().rev() {
let shift_const_id = NodeId(*next_id);
*next_id += 1;
let (mul_id, _) = block.nodes[pos];
block.nodes[pos] = (
mul_id,
ValueNode::Int32ShiftLeft {
left: operand,
right: shift_const_id,
},
);
block.nodes.insert(
pos,
(
shift_const_id,
ValueNode::Int32Constant {
value: shift_amt as i32,
},
),
);
}
}
}
fn find_power_of_two_operand(
left: NodeId,
right: NodeId,
consts: &HashMap<NodeId, i32>,
) -> Option<(NodeId, u32)> {
if let Some(&val) = consts.get(&right)
&& val >= 2
&& val.count_ones() == 1
{
return Some((left, val.trailing_zeros()));
}
if let Some(&val) = consts.get(&left)
&& val >= 2
&& val.count_ones() == 1
{
return Some((right, val.trailing_zeros()));
}
None
}
fn find_shift_add_decomposition(
left: NodeId,
right: NodeId,
consts: &HashMap<NodeId, i32>,
) -> Option<(NodeId, u32, bool)> {
fn try_decompose(val: i32) -> Option<(u32, bool)> {
if val < 3 {
return None;
}
let minus_one = val - 1;
if minus_one >= 2 && minus_one.count_ones() == 1 {
return Some((minus_one.trailing_zeros(), true));
}
let plus_one = val + 1;
if plus_one >= 4 && plus_one.count_ones() == 1 {
return Some((plus_one.trailing_zeros(), false));
}
None
}
if let Some(&val) = consts.get(&right)
&& let Some((shift, is_add)) = try_decompose(val)
{
return Some((left, shift, is_add));
}
if let Some(&val) = consts.get(&left)
&& let Some((shift, is_add)) = try_decompose(val)
{
return Some((right, shift, is_add));
}
None
}
#[derive(Hash, Eq, PartialEq)]
enum CseKey {
Binary(u16, NodeId, NodeId),
Unary(u16, NodeId),
Nullary(u16, u32),
PropertyLoad(u16, NodeId, u32),
}
fn make_cse_key(node: &ValueNode) -> Option<CseKey> {
match node {
ValueNode::Int32Add { left, right } => Some(CseKey::Binary(1, *left, *right)),
ValueNode::Int32Subtract { left, right } => Some(CseKey::Binary(2, *left, *right)),
ValueNode::Int32Multiply { left, right } => Some(CseKey::Binary(3, *left, *right)),
ValueNode::Int32Divide { left, right } => Some(CseKey::Binary(4, *left, *right)),
ValueNode::Int32Modulus { left, right } => Some(CseKey::Binary(5, *left, *right)),
ValueNode::Int32BitwiseAnd { left, right } => Some(CseKey::Binary(6, *left, *right)),
ValueNode::Int32BitwiseOr { left, right } => Some(CseKey::Binary(7, *left, *right)),
ValueNode::Int32BitwiseXor { left, right } => Some(CseKey::Binary(8, *left, *right)),
ValueNode::Int32ShiftLeft { left, right } => Some(CseKey::Binary(9, *left, *right)),
ValueNode::Int32ShiftRight { left, right } => Some(CseKey::Binary(10, *left, *right)),
ValueNode::Int32ShiftRightLogical { left, right } => {
Some(CseKey::Binary(11, *left, *right))
}
ValueNode::Int32Equal { left, right } => Some(CseKey::Binary(12, *left, *right)),
ValueNode::Int32StrictEqual { left, right } => Some(CseKey::Binary(13, *left, *right)),
ValueNode::Int32LessThan { left, right } => Some(CseKey::Binary(14, *left, *right)),
ValueNode::Int32LessThanOrEqual { left, right } => Some(CseKey::Binary(15, *left, *right)),
ValueNode::Int32GreaterThan { left, right } => Some(CseKey::Binary(16, *left, *right)),
ValueNode::Int32GreaterThanOrEqual { left, right } => {
Some(CseKey::Binary(17, *left, *right))
}
ValueNode::Float64Add { left, right } => Some(CseKey::Binary(18, *left, *right)),
ValueNode::Float64Subtract { left, right } => Some(CseKey::Binary(19, *left, *right)),
ValueNode::Float64Multiply { left, right } => Some(CseKey::Binary(20, *left, *right)),
ValueNode::Float64Divide { left, right } => Some(CseKey::Binary(21, *left, *right)),
ValueNode::Float64Modulus { left, right } => Some(CseKey::Binary(22, *left, *right)),
ValueNode::Int32Negate { value } => Some(CseKey::Unary(1, *value)),
ValueNode::Int32Increment { value } => Some(CseKey::Unary(2, *value)),
ValueNode::Int32Decrement { value } => Some(CseKey::Unary(3, *value)),
ValueNode::Float64Negate { value } => Some(CseKey::Unary(4, *value)),
ValueNode::ToBoolean { value } => Some(CseKey::Unary(5, *value)),
ValueNode::LoadGlobal { name, .. } => Some(CseKey::Nullary(1, *name)),
ValueNode::LoadNamedGeneric { object, name, .. } => {
Some(CseKey::PropertyLoad(1, *object, *name))
}
_ => None,
}
}
fn eliminate_common_subexpressions(graph: &mut MaglevGraph) {
for block in graph.blocks_mut() {
cse_in_block(block);
}
}
fn cse_in_block(block: &mut BasicBlock) {
let mut seen: HashMap<CseKey, NodeId> = HashMap::new();
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (id, node) in &mut block.nodes {
if has_side_effects(node) {
continue;
}
if let Some(key) = make_cse_key(node) {
if let Some(&first_id) = seen.get(&key) {
subst.insert(*id, first_id);
*node = ValueNode::UndefinedConstant;
} else {
seen.insert(key, *id);
}
}
}
if !subst.is_empty() {
apply_subst_to_block(block, &subst);
}
}
fn promote_loop_globals_counted(graph: &mut MaglevGraph) -> usize {
let mut loops = licm::detect_loops(graph);
if loops.is_empty() {
return 0;
}
loops.sort_by_key(|lp| lp.body.len());
let loop_stored_globals: Vec<HashSet<u32>> = loops
.iter()
.map(|lp| {
let mut stored = HashSet::new();
for block in graph.blocks() {
if !lp.body.contains(&block.id) {
continue;
}
for (_, node) in &block.nodes {
if let ValueNode::StoreGlobal { name, .. } = node {
stored.insert(*name);
}
}
}
stored
})
.collect();
let mut nested_stored: Vec<HashSet<u32>> = vec![HashSet::new(); loops.len()];
for (i, outer) in loops.iter().enumerate() {
for (j, inner) in loops.iter().enumerate() {
if i == j {
continue;
}
if inner.body.len() < outer.body.len() && inner.body.is_subset(&outer.body) {
for name in &loop_stored_globals[j] {
nested_stored[i].insert(*name);
}
}
}
}
let loop_headers: HashSet<u32> = loops.iter().map(|lp| lp.header).collect();
let conditional_stores: Vec<HashSet<u32>> = loops
.iter()
.map(|lp| conditionally_stored_globals(graph, lp, &loop_headers))
.collect();
let mut count = 0;
for (i, lp) in loops.iter().enumerate() {
let mut exclude_names = nested_stored[i].clone();
if !conditional_stores[i].is_empty() {
OPT_GLOBALS_SKIPPED.fetch_add(1, Ordering::Relaxed);
exclude_names.extend(conditional_stores[i].iter().copied());
}
count += promote_globals_in_loop(graph, lp, &exclude_names);
}
count
}
fn conditionally_stored_globals(
graph: &MaglevGraph,
lp: &licm::NaturalLoop,
loop_headers: &HashSet<u32>,
) -> HashSet<u32> {
let has_conditional_body = lp.body.iter().any(|&block_idx| {
if block_idx == lp.header || loop_headers.contains(&block_idx) {
return false;
}
matches!(
graph
.block(block_idx)
.and_then(|block| block.control.as_ref()),
Some(ControlNode::Branch { .. })
)
});
if !has_conditional_body {
return HashSet::new();
}
let backedge_blocks: HashSet<u32> = lp
.body
.iter()
.copied()
.filter(|&block_idx| {
graph
.block(block_idx)
.is_some_and(|block| licm::control_targets(block).contains(&lp.header))
})
.collect();
let mut names = HashSet::new();
for &block_idx in &lp.body {
if block_idx == lp.header || backedge_blocks.contains(&block_idx) {
continue;
}
let Some(block) = graph.block(block_idx) else {
continue;
};
for (_, node) in &block.nodes {
if let ValueNode::StoreGlobal { name, .. } = node {
names.insert(*name);
}
}
}
names
}
fn is_user_call(node: &ValueNode) -> bool {
matches!(
node,
ValueNode::Call { .. }
| ValueNode::CallKnownFunction { .. }
| ValueNode::CallBuiltin { .. }
| ValueNode::CallRuntime { .. }
| ValueNode::CallWithSpread { .. }
| ValueNode::Construct { .. }
| ValueNode::ConstructWithSpread { .. }
| ValueNode::SpeculativeCallFusion { .. }
| ValueNode::SpeculativeSumFusion { .. }
| ValueNode::SpeculativePushFusion { .. }
| ValueNode::SpeculativeFillTrueFusion { .. }
| ValueNode::SpeculativeCountTruthyFusion { .. }
)
}
struct PromotedGlobal {
name: u32,
feedback_slot: u32,
preheader_load_id: NodeId,
phi_id: NodeId,
store_value_id: NodeId,
original_load_ids: Vec<NodeId>,
original_store_ids: Vec<NodeId>,
}
fn promote_globals_in_loop(
graph: &mut MaglevGraph,
lp: &licm::NaturalLoop,
exclude_names: &HashSet<u32>,
) -> usize {
for block in graph.blocks() {
if !lp.body.contains(&block.id) {
continue;
}
for (_, node) in &block.nodes {
if is_user_call(node) {
OPT_GLOBALS_SKIPPED.fetch_add(1, Ordering::Relaxed);
return 0;
}
}
}
let mut load_names: HashSet<u32> = HashSet::new();
let mut store_names: HashSet<u32> = HashSet::new();
let mut load_info: HashMap<u32, (u32, Vec<NodeId>)> = HashMap::new(); let mut store_info: HashMap<u32, (NodeId, Vec<NodeId>, u32)> = HashMap::new();
for block in graph.blocks() {
if !lp.body.contains(&block.id) {
continue;
}
for (id, node) in &block.nodes {
match node {
ValueNode::LoadGlobal {
name,
feedback_slot,
} => {
load_names.insert(*name);
let entry = load_info
.entry(*name)
.or_insert((*feedback_slot, Vec::new()));
entry.1.push(*id);
}
ValueNode::StoreGlobal {
name,
value,
feedback_slot,
} => {
store_names.insert(*name);
let entry =
store_info
.entry(*name)
.or_insert((*value, Vec::new(), *feedback_slot));
entry.0 = *value;
entry.1.push(*id);
}
_ => {}
}
}
}
let promotable: Vec<u32> = store_names
.iter()
.copied()
.filter(|name| !exclude_names.contains(name))
.collect();
if promotable.is_empty() {
return 0;
}
let preheader_stores: HashMap<u32, NodeId> = {
let mut stores = HashMap::new();
if let Some(pb) = graph.blocks().iter().find(|b| b.id == lp.preheader) {
for (_, node) in &pb.nodes {
if let ValueNode::StoreGlobal { name, value, .. } = node {
stores.insert(*name, *value);
}
}
}
stores
};
let mut promoted: Vec<PromotedGlobal> = Vec::new();
for &name in &promotable {
let (store_value, ref store_ids, store_feedback_slot) = store_info[&name];
let (feedback_slot, load_ids) = match load_info.get(&name) {
Some((fs, ids)) => (*fs, ids.clone()),
None => (store_feedback_slot, Vec::new()),
};
let preheader_load_id = if let Some(&init_value) = preheader_stores.get(&name) {
init_value
} else {
graph
.add_value_node(
lp.preheader,
ValueNode::LoadGlobal {
name,
feedback_slot,
},
)
.expect("preheader block must exist")
};
let phi_id = graph.alloc_node_id();
promoted.push(PromotedGlobal {
name,
feedback_slot,
preheader_load_id,
phi_id,
store_value_id: store_value,
original_load_ids: load_ids.clone(),
original_store_ids: store_ids.clone(),
});
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for pg in &promoted {
for &load_id in &pg.original_load_ids {
subst.insert(load_id, pg.phi_id);
}
}
if let Some(header_block) = graph.block_mut(lp.header) {
for pg in promoted.iter().rev() {
header_block.nodes.insert(
0,
(
pg.phi_id,
ValueNode::Phi {
inputs: vec![pg.preheader_load_id],
},
),
);
}
}
for block in graph.blocks_mut() {
if !lp.body.contains(&block.id) {
continue;
}
for (id, node) in &mut block.nodes {
for pg in &promoted {
if pg.original_load_ids.contains(id) || pg.original_store_ids.contains(id) {
*node = ValueNode::UndefinedConstant;
}
}
}
}
for block in graph.blocks_mut() {
if !lp.body.contains(&block.id) {
continue;
}
apply_subst_to_block(block, &subst);
}
for pg in &mut promoted {
pg.store_value_id = subst
.get(&pg.store_value_id)
.copied()
.unwrap_or(pg.store_value_id);
}
if let Some(header_block) = graph.block_mut(lp.header) {
for pg in &promoted {
for (id, node) in &mut header_block.nodes {
if *id == pg.phi_id {
if let ValueNode::Phi { inputs } = node {
inputs.push(pg.store_value_id);
}
break;
}
}
}
}
let mut exit_blocks: HashSet<u32> = HashSet::new();
for block in graph.blocks() {
if !lp.body.contains(&block.id) {
continue;
}
let targets = licm::control_targets(block);
for &target in &targets {
if !lp.body.contains(&target) {
exit_blocks.insert(target);
}
}
}
for &exit_id in &exit_blocks {
for pg in promoted.iter().rev() {
let store_id = graph.alloc_node_id();
if let Some(exit_block) = graph.block_mut(exit_id) {
exit_block.nodes.insert(
0,
(
store_id,
ValueNode::StoreGlobal {
name: pg.name,
value: pg.phi_id,
feedback_slot: pg.feedback_slot,
},
),
);
}
}
}
OPT_GLOBALS_PROMOTED.fetch_add(promotable.len() as u32, Ordering::Relaxed);
promotable.len()
}
fn eliminate_redundant_type_guards(graph: &mut MaglevGraph) {
let mut known_smi: HashSet<NodeId> = HashSet::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if is_known_smi_producer(node) {
known_smi.insert(*id);
}
}
}
loop {
let mut changed = false;
for block in graph.blocks() {
for (id, node) in &block.nodes {
if known_smi.contains(id) {
continue;
}
if let ValueNode::Phi { inputs } = node
&& !inputs.is_empty()
&& inputs.iter().all(|inp| known_smi.contains(inp))
&& known_smi.insert(*id)
{
changed = true;
}
}
}
if !changed {
break;
}
}
for block in graph.blocks_mut() {
let mut block_guarded: HashSet<NodeId> = HashSet::new();
for (_, node) in &mut block.nodes {
if let ValueNode::CheckSmi { receiver } = node {
if known_smi.contains(receiver) || block_guarded.contains(receiver) {
*node = ValueNode::UndefinedConstant;
} else {
block_guarded.insert(*receiver);
}
}
}
}
}
fn is_known_smi_producer(node: &ValueNode) -> bool {
matches!(
node,
ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::CheckedSmiSubtract { .. }
| ValueNode::CheckedSmiMultiply { .. }
| ValueNode::CheckedSmiDivide { .. }
| ValueNode::CheckedSmiModulus { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::CheckedSmiDecrement { .. }
| ValueNode::Int32Add { .. }
| ValueNode::Int32Subtract { .. }
| ValueNode::Int32Multiply { .. }
| ValueNode::Int32Divide { .. }
| ValueNode::Int32Modulus { .. }
| ValueNode::Int32Negate { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::Int32Decrement { .. }
| ValueNode::Int32BitwiseOr { .. }
| ValueNode::Int32BitwiseAnd { .. }
| ValueNode::Int32BitwiseXor { .. }
| ValueNode::GenericBitwiseNot { .. }
| ValueNode::ChangeInt32ToTagged { .. }
)
}
fn remove_redundant_check_maps(graph: &mut MaglevGraph) {
for block in graph.blocks_mut() {
remove_redundant_check_maps_in_block(block);
}
}
fn remove_redundant_check_maps_in_block(block: &mut BasicBlock) {
let mut seen: HashMap<(NodeId, u32), NodeId> = HashMap::new();
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (id, node) in &mut block.nodes {
if let ValueNode::CheckMaps {
receiver,
feedback_slot,
} = node
{
let key = (*receiver, *feedback_slot);
if let Some(&first) = seen.get(&key) {
subst.insert(*id, first);
*node = ValueNode::UndefinedConstant;
} else {
seen.insert(key, *id);
}
}
}
if subst.is_empty() {
return;
}
apply_subst_to_block(block, &subst);
}
fn specialize_closure_calls(graph: &mut MaglevGraph) {
let mut closure_nodes: HashSet<NodeId> = HashSet::new();
for block in graph.blocks() {
for &(id, ref node) in &block.nodes {
if matches!(
node,
ValueNode::FastCreateClosure { .. } | ValueNode::CreateClosure { .. }
) {
closure_nodes.insert(id);
}
}
}
if closure_nodes.is_empty() {
return;
}
let mut phi_map: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
for block in graph.blocks() {
for &(id, ref node) in &block.nodes {
if let ValueNode::Phi { inputs } = node {
phi_map.insert(id, inputs.clone());
}
}
}
let mut changed = true;
while changed {
changed = false;
for (&phi_id, inputs) in &phi_map {
if closure_nodes.contains(&phi_id) {
continue;
}
let all_closure = inputs
.iter()
.all(|&inp| inp == phi_id || closure_nodes.contains(&inp));
if all_closure && !inputs.is_empty() {
let has_non_self = inputs.iter().any(|&inp| inp != phi_id);
if has_non_self {
closure_nodes.insert(phi_id);
changed = true;
}
}
}
}
for block in graph.blocks_mut() {
for (_id, node) in &mut block.nodes {
if let ValueNode::Call {
callee,
receiver,
args,
..
} = node
&& closure_nodes.contains(callee)
{
*node = ValueNode::CallKnownFunction {
callee: *callee,
receiver: *receiver,
args: args.clone(),
};
}
}
}
}
fn fuse_call_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
if loops.is_empty() {
return;
}
for lp in &loops {
try_fuse_call_loop(graph, lp);
}
}
fn try_fuse_call_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let (condition_id, body_block_idx, header_preds, header_nodes_snapshot);
{
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (cond, body_bi, _exit) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_bi) {
return false;
}
condition_id = cond;
body_block_idx = body_bi;
header_preds = header.predecessors.clone();
header_nodes_snapshot = header
.nodes
.iter()
.map(|(nid, node)| (*nid, node.clone()))
.collect::<Vec<_>>();
}
{
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header_nodes_snapshot {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right),
_ => return false,
}
};
let iv_limit = match find_i32_constant(graph, cmp_right) {
Some(v) => v,
None => return false,
};
let (trip_count, call_node_id, callee_id, iv_global_name) =
if let Some(ValueNode::Phi { inputs }) = graph.node(cmp_left) {
let inputs = inputs.clone();
if inputs.len() != 2 {
return false;
}
let back_pred_pos = match header_preds.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
};
let entry_pos = match header_preds.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_init = match find_i32_constant(graph, inputs[entry_pos]) {
Some(v) => v,
None => return false,
};
let iv_step = find_increment_step(graph, inputs[back_pred_pos], cmp_left);
if iv_step != Some(1) {
return false;
}
let range = (iv_limit as i64) - (iv_init as i64);
if range <= 0 || range > 100_000 {
return false;
}
let mut found_call = None;
for (nid, node) in &header_nodes_snapshot {
if *nid == cmp_left {
continue;
}
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
let back_id = inputs[back_pred_pos];
if let Some(cid) = find_call_callee(graph, back_id) {
found_call = Some((range as u32, back_id, cid));
break;
}
}
}
match found_call {
Some((tc, cn, ci)) => (tc, cn, ci, None),
None => return false,
}
} else if let Some(ValueNode::LoadGlobal { name: iv_name, .. }) = graph.node(cmp_left) {
let iv_name = *iv_name;
let pre = graph.block(lp.preheader);
let iv_init = pre.and_then(|pre| {
pre.nodes.iter().rev().find_map(|(_, node)| {
if let ValueNode::StoreGlobal { name, value, .. } = node
&& *name == iv_name
{
find_i32_constant(graph, *value)
} else {
None
}
})
});
let iv_init = match iv_init {
Some(v) => v,
None => return false,
};
let body = graph.block(body_block_idx).unwrap();
let mut iv_step_ok = false;
for (_, node) in &body.nodes {
if let ValueNode::StoreGlobal { name, value, .. } = node
&& *name == iv_name
{
if let Some(inc_node) = graph.node(*value) {
let base = match inc_node {
ValueNode::GenericIncrement { value, .. }
| ValueNode::Int32Increment { value }
| ValueNode::CheckedSmiIncrement { value } => Some(*value),
_ => None,
};
if let Some(base_id) = base
&& let Some(ValueNode::LoadGlobal { name: bn, .. }) =
graph.node(base_id)
&& *bn == iv_name
{
iv_step_ok = true;
}
}
}
}
if !iv_step_ok {
return false;
}
let range = (iv_limit as i64) - (iv_init as i64);
if range <= 0 || range > 100_000 {
return false;
}
let body = graph.block(body_block_idx).unwrap();
let mut found_call = None;
for (nid, node) in &body.nodes {
if let Some(cid) = find_call_callee_node(node) {
found_call = Some((range as u32, *nid, cid));
break;
}
}
match found_call {
Some((tc, cn, ci)) => (tc, cn, ci, Some(iv_name)),
None => return false,
}
} else {
return false;
};
let loop_body_set: HashSet<u32> = lp.body.iter().copied().collect();
let callee_in_loop = loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == callee_id))
.unwrap_or(false)
});
if callee_in_loop {
let is_invariant_load_global = if let Some(ValueNode::LoadGlobal { name, .. }) =
graph.node(callee_id)
{
let callee_name = *name;
!loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| {
b.nodes.iter().any(|(_, node)| {
matches!(node, ValueNode::StoreGlobal { name, .. } if *name == callee_name)
})
})
.unwrap_or(false)
})
} else {
false
};
if !is_invariant_load_global {
return false;
}
}
let (resolved_slot, resolved_k) = resolve_fusion_pattern(graph, callee_id, lp.preheader);
let fusion_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
fusion_id,
ValueNode::SpeculativeCallFusion {
callee: callee_id,
trip_count,
resolved_slot,
resolved_k,
},
);
}
let body = graph.block(body_block_idx).unwrap();
let mut result_store_name = None;
let mut result_store_slot = None;
for (_, node) in &body.nodes {
if let ValueNode::StoreGlobal {
name,
value,
feedback_slot,
} = node
&& *value == call_node_id
{
result_store_name = Some(*name);
result_store_slot = Some(*feedback_slot);
break;
}
}
if let (Some(store_name), Some(store_fb)) = (result_store_name, result_store_slot) {
let store_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
store_id,
ValueNode::StoreGlobal {
name: store_name,
value: fusion_id,
feedback_slot: store_fb,
},
);
}
}
if let Some(iv_name) = iv_global_name {
let body = graph.block(body_block_idx).unwrap();
let mut iv_fb = None;
for (_, node) in &body.nodes {
if let ValueNode::StoreGlobal {
name,
feedback_slot,
..
} = node
&& *name == iv_name
{
iv_fb = Some(*feedback_slot);
break;
}
}
if let Some(fb) = iv_fb {
let iv_store_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
iv_store_id,
ValueNode::StoreGlobal {
name: iv_name,
value: cmp_right,
feedback_slot: fb,
},
);
}
}
}
if iv_global_name.is_none() {
let back_pred_pos = header_preds.iter().position(|&p| p == body_block_idx);
let entry_pos = header_preds.iter().position(|&p| p == lp.preheader);
if let (Some(bp), Some(ep)) = (back_pred_pos, entry_pos) {
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if *nid == cmp_left {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[ep] = cmp_right;
inputs[bp] = *nid; }
break;
}
}
}
}
let back_pred_pos = header_preds.iter().position(|&p| p == body_block_idx);
let entry_pos = header_preds.iter().position(|&p| p == lp.preheader);
if let (Some(bp), Some(ep)) = (back_pred_pos, entry_pos) {
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
&& inputs[bp] == call_node_id
{
inputs[ep] = fusion_id;
inputs[bp] = *nid; break;
}
}
}
true
}
#[allow(dead_code)] fn fuse_sum_only_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
try_fuse_sum_loop(graph, lp);
}
}
fn fuse_all_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
if !try_fuse_sum_loop(graph, lp) && !try_fuse_push_loop(graph, lp) {
try_fuse_fill_true_loop(graph, lp);
}
}
}
fn fuse_fill_true_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
try_fuse_fill_true_loop(graph, lp);
}
}
fn fuse_count_truthy_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
try_fuse_count_truthy_loop(graph, lp);
}
}
#[allow(dead_code)] fn fuse_sum_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
if loops.is_empty() {
return;
}
for lp in &loops {
if !try_fuse_sum_loop(graph, lp) {
try_fuse_push_loop(graph, lp);
}
}
}
fn try_fuse_sum_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let (condition_id, body_block_idx, header_preds, header_nodes_snapshot);
{
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (cond, body_bi, _exit) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_bi) {
return false;
}
condition_id = cond;
body_block_idx = body_bi;
header_preds = header.predecessors.clone();
header_nodes_snapshot = header
.nodes
.iter()
.map(|(nid, node)| (*nid, node.clone()))
.collect::<Vec<_>>();
}
{
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header_nodes_snapshot {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right),
_ => return false,
}
};
let back_pred_pos = match header_preds.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
};
let entry_pos = match header_preds.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_phi_id = cmp_left;
let iv_inputs = match graph.node(iv_phi_id) {
Some(ValueNode::Phi { inputs }) if inputs.len() == 2 => inputs.clone(),
_ => return false,
};
if find_i32_constant(graph, iv_inputs[entry_pos]) != Some(0) {
return false;
}
if find_increment_step(graph, iv_inputs[back_pred_pos], iv_phi_id) != Some(1) {
return false;
}
let limit_arr_node_id = match graph.node(cmp_right) {
Some(ValueNode::LoadNamedGeneric { object, .. }) => Some(*object),
Some(ValueNode::SmiConstant { .. } | ValueNode::Int32Constant { .. }) => None,
_ => return false,
};
let loop_body_set: HashSet<u32> = lp.body.iter().copied().collect();
if let Some(arr_id) = limit_arr_node_id {
let arr_in_loop = loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == arr_id))
.unwrap_or(false)
});
if arr_in_loop {
return false;
}
}
let mut sum_phi_id = None;
let mut add_node_id = None;
let mut arr_node_id = limit_arr_node_id;
let body_snapshot: Vec<_> = graph
.block(body_block_idx)
.map(|b| b.nodes.iter().map(|(nid, n)| (*nid, n.clone())).collect())
.unwrap_or_default();
let is_iv_key = |key: NodeId| -> bool {
if key == iv_phi_id {
return true;
}
if let Some(ValueNode::Phi { inputs }) = graph.node(key)
&& inputs.len() == 2
&& inputs[entry_pos] == iv_inputs[entry_pos]
{
return true;
}
false
};
let mut keyed_load_id = None;
let mut keyed_load_obj = None;
for (nid, node) in body_snapshot.iter().chain(header_nodes_snapshot.iter()) {
match node {
ValueNode::LoadKeyedGeneric { object, key, .. } if is_iv_key(*key) => {
keyed_load_id = Some(*nid);
keyed_load_obj = Some(*object);
break;
}
ValueNode::LoadFixedArrayElement { elements, index }
| ValueNode::LoadFixedDoubleArrayElement { elements, index }
if is_iv_key(*index) =>
{
keyed_load_id = Some(*nid);
keyed_load_obj = Some(*elements);
break;
}
_ => {}
}
}
if let (Some(kl_id), Some(kl_obj)) = (keyed_load_id, keyed_load_obj) {
let obj_in_loop = loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == kl_obj))
.unwrap_or(false)
});
if !obj_in_loop {
if let Some(expected) = arr_node_id {
if kl_obj != expected {
}
} else {
arr_node_id = Some(kl_obj);
}
}
let resolves_to_load = |operand: NodeId| -> bool {
if operand == kl_id {
return true;
}
if let Some(ValueNode::Phi { inputs }) = graph.node(operand)
&& inputs.len() == 2
&& inputs[back_pred_pos] == kl_id
{
return true;
}
false
};
let mut add_candidates: Vec<(NodeId, NodeId, NodeId)> = Vec::new(); for (nid, node) in &body_snapshot {
let (l, r) = match node {
ValueNode::GenericAdd { left, right, .. }
| ValueNode::Int32Add { left, right }
| ValueNode::CheckedSmiAdd { left, right } => (*left, *right),
_ => continue,
};
add_candidates.push((*nid, l, r));
}
for (a_id, a_left, a_right) in &add_candidates {
let other = if resolves_to_load(*a_left) {
*a_right
} else if resolves_to_load(*a_right) {
*a_left
} else {
continue;
};
for (hid, hnode) in &header_nodes_snapshot {
if *hid == iv_phi_id || *hid == condition_id {
continue;
}
if let ValueNode::Phi { inputs } = hnode
&& inputs.len() == 2
{
if find_i32_constant(graph, inputs[entry_pos]).is_none() {
continue;
}
let back = inputs[back_pred_pos];
if back != *a_id {
continue;
}
let other_matches = other == *hid || {
if let Some(ValueNode::Phi { inputs: oi }) = graph.node(other)
&& oi.len() == 2
{
oi[back_pred_pos] == *a_id
|| oi[back_pred_pos] == *hid
|| oi[entry_pos] == inputs[entry_pos]
} else {
false
}
};
if other_matches {
sum_phi_id = Some(*hid);
add_node_id = Some(*a_id);
break;
}
}
}
if sum_phi_id.is_some() {
break;
}
}
}
let sum_phi_id = match sum_phi_id {
Some(id) => id,
None => return false,
};
let _add_node_id = add_node_id.unwrap();
{
let body = graph.block(body_block_idx).unwrap();
for (_, node) in &body.nodes {
match node {
ValueNode::LoadKeyedGeneric { .. }
| ValueNode::LoadFixedArrayElement { .. }
| ValueNode::LoadFixedDoubleArrayElement { .. }
| ValueNode::LoadHoleyFixedDoubleArrayElement { .. }
| ValueNode::GenericAdd { .. }
| ValueNode::Int32Add { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::GenericIncrement { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::Phi { .. }
| ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Float64Constant { .. }
| ValueNode::LoadGlobal { .. }
| ValueNode::StoreGlobal { .. }
| ValueNode::LoadNamedGeneric { .. }
| ValueNode::Int32LessThan { .. }
| ValueNode::CheckSmi { .. } => {}
_other => return false,
}
}
}
let arr_node_id = match arr_node_id {
Some(id) => id,
None => return false,
};
let fusion_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
fusion_id,
ValueNode::SpeculativeSumFusion { array: arr_node_id },
);
}
{
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[entry_pos] = cmp_right;
inputs[back_pred_pos] = *nid;
}
break;
}
}
}
{
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if *nid == sum_phi_id {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[entry_pos] = fusion_id;
inputs[back_pred_pos] = *nid;
}
break;
}
}
}
true
}
fn try_fuse_push_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let (condition_id, body_block_idx, header_preds, header_nodes_snapshot);
{
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (cond, body_bi, _exit) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_bi) {
return false;
}
condition_id = cond;
body_block_idx = body_bi;
header_preds = header.predecessors.clone();
header_nodes_snapshot = header
.nodes
.iter()
.map(|(nid, node)| (*nid, node.clone()))
.collect::<Vec<_>>();
}
{
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header_nodes_snapshot {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right),
_ => return false,
}
};
let trip_count = match find_i32_constant(graph, cmp_right) {
Some(v) if v > 0 && v <= 100_000 => v as u32,
_ => return false,
};
let back_pred_pos = match header_preds.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
};
let entry_pos = match header_preds.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_phi_id = cmp_left;
let iv_inputs = match graph.node(iv_phi_id) {
Some(ValueNode::Phi { inputs }) if inputs.len() == 2 => inputs.clone(),
_ => return false,
};
if find_i32_constant(graph, iv_inputs[entry_pos]) != Some(0) {
return false;
}
if find_increment_step(graph, iv_inputs[back_pred_pos], iv_phi_id) != Some(1) {
return false;
}
let mut arr_node_id = None;
{
let body = graph.block(body_block_idx).unwrap();
for (_, node) in &body.nodes {
if let ValueNode::CallArrayPush { receiver, args, .. } = node
&& args.len() == 1
&& args[0] == iv_phi_id
{
arr_node_id = Some(*receiver);
break;
}
}
}
let arr_node_id = match arr_node_id {
Some(id) => id,
None => return false,
};
let loop_body_set: HashSet<u32> = lp.body.iter().copied().collect();
let arr_in_loop = loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == arr_node_id))
.unwrap_or(false)
});
if arr_in_loop {
return false;
}
{
let body = graph.block(body_block_idx).unwrap();
for (_, node) in &body.nodes {
match node {
ValueNode::CallArrayPush { .. }
| ValueNode::GenericIncrement { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::GenericAdd { .. }
| ValueNode::Int32Add { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::Phi { .. }
| ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Float64Constant { .. }
| ValueNode::LoadNamedGeneric { .. }
| ValueNode::LoadGlobal { .. }
| ValueNode::StoreGlobal { .. }
| ValueNode::Int32LessThan { .. }
| ValueNode::CheckSmi { .. } => {}
_ => return false,
}
}
}
let fusion_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
fusion_id,
ValueNode::SpeculativePushFusion {
array: arr_node_id,
count: trip_count,
},
);
}
{
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[entry_pos] = cmp_right;
inputs[back_pred_pos] = *nid;
}
break;
}
}
}
true
}
fn try_fuse_fill_true_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let (condition_id, body_block_idx, header_preds, header_nodes_snapshot);
{
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (cond, body_bi, _exit) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_bi) {
return false;
}
condition_id = cond;
body_block_idx = body_bi;
header_preds = header.predecessors.clone();
header_nodes_snapshot = header
.nodes
.iter()
.map(|(nid, node)| (*nid, node.clone()))
.collect::<Vec<_>>();
}
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
let (iv_phi_id, limit_id, inclusive_bound) = {
let mut found = None;
for (nid, node) in &header_nodes_snapshot {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right, false),
Some(ValueNode::Int32LessThanOrEqual { left, right }) => (left, right, true),
_ => return false,
}
};
let back_pred_pos = match header_preds.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
};
let entry_pos = match header_preds.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_inputs = match graph.node(iv_phi_id) {
Some(ValueNode::Phi { inputs }) if inputs.len() == 2 => inputs.clone(),
_ => return false,
};
if find_i32_constant(graph, iv_inputs[entry_pos]) != Some(0) {
return false;
}
if find_increment_step(graph, iv_inputs[back_pred_pos], iv_phi_id) != Some(1) {
return false;
}
let body_snapshot: Vec<_> = body
.nodes
.iter()
.map(|(nid, node)| (*nid, node.clone()))
.collect();
let mut fill_store = None;
for (nid, node) in &body_snapshot {
match node {
ValueNode::StoreKeyedGeneric {
object, key, value, ..
} if *key == iv_phi_id
&& matches!(graph.node(*value), Some(ValueNode::TrueConstant)) =>
{
fill_store = Some((*nid, *object));
break;
}
ValueNode::StoreFixedArrayElement {
elements,
index,
value,
} if *index == iv_phi_id
&& matches!(graph.node(*value), Some(ValueNode::TrueConstant)) =>
{
fill_store = Some((*nid, *elements));
break;
}
_ => {}
}
}
let (store_id, array_id) = match fill_store {
Some(found) => found,
None => return false,
};
if !matches!(
graph.node(array_id),
Some(ValueNode::CreateEmptyArrayLiteral { .. })
) {
return false;
}
let loop_body_set: HashSet<u32> = lp.body.iter().copied().collect();
let arr_in_loop = loop_body_set.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == array_id))
.unwrap_or(false)
});
if arr_in_loop {
return false;
}
for &block_id in &lp.body {
let block = match graph.block(block_id) {
Some(block) => block,
None => return false,
};
for (nid, node) in &block.nodes {
if *nid == store_id {
continue;
}
match node {
ValueNode::GenericIncrement { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::GenericAdd { .. }
| ValueNode::Int32Add { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::Phi { .. }
| ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::TrueConstant
| ValueNode::Int32LessThan { .. }
| ValueNode::Int32LessThanOrEqual { .. }
| ValueNode::CheckSmi { .. } => {}
_ => return false,
}
}
}
let count_id = if inclusive_bound {
let one_id = graph.alloc_node_id();
let count_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(one_id, ValueNode::SmiConstant { value: 1 });
pre.push_with_id(
count_id,
ValueNode::Int32Add {
left: limit_id,
right: one_id,
},
);
}
count_id
} else {
limit_id
};
let fusion_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
fusion_id,
ValueNode::SpeculativeFillTrueFusion {
array: array_id,
count: count_id,
},
);
}
if let Some(header) = graph.block_mut(lp.header) {
for (nid, node) in &mut header.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[entry_pos] = count_id;
inputs[back_pred_pos] = *nid;
}
break;
}
}
}
true
}
fn try_fuse_count_truthy_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
if !lp.body.contains(&lp.header) {
return false;
}
let header = match graph.block(lp.header) {
Some(block) => block,
None => return false,
};
let (condition_id, test_block_idx, exit_block_idx) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&test_block_idx) || lp.body.contains(&exit_block_idx) {
return false;
}
let (iv_phi_id, limit_id, inclusive_bound) = match graph.node(condition_id) {
Some(ValueNode::Int32LessThan { left, right }) => (*left, *right, false),
Some(ValueNode::Int32LessThanOrEqual { left, right }) => (*left, *right, true),
_ => return false,
};
let back_pred_pos = match header
.predecessors
.iter()
.position(|&p| lp.body.contains(&p))
{
Some(pos) => pos,
None => return false,
};
let latch_block_idx = header.predecessors[back_pred_pos];
let entry_pos = match header.predecessors.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_inputs = match graph.node(iv_phi_id) {
Some(ValueNode::Phi { inputs }) if inputs.len() == 2 => inputs.clone(),
_ => return false,
};
if find_i32_constant(graph, iv_inputs[entry_pos]) != Some(0) {
return false;
}
if find_increment_step(graph, iv_inputs[back_pred_pos], iv_phi_id) != Some(1) {
return false;
}
let latch_block = match graph.block(latch_block_idx) {
Some(block) => block,
None => return false,
};
if !matches!(
latch_block.control,
Some(ControlNode::Jump { target }) if target == lp.header
) {
return false;
}
let test_block = match graph.block(test_block_idx) {
Some(block) => block,
None => return false,
};
let (load_id, then_block_idx, false_target_idx) = match &test_block.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => {
let load_id = match graph.node(*condition) {
Some(ValueNode::LoadKeyedGeneric { key, .. }) if *key == iv_phi_id => *condition,
Some(ValueNode::LoadFixedArrayElement { index, .. }) if *index == iv_phi_id => {
*condition
}
Some(ValueNode::ToBoolean { value }) => match graph.node(*value) {
Some(ValueNode::LoadKeyedGeneric { key, .. }) if *key == iv_phi_id => *value,
Some(ValueNode::LoadFixedArrayElement { index, .. }) if *index == iv_phi_id => {
*value
}
_ => return false,
},
_ => return false,
};
(load_id, *if_true, *if_false)
}
_ => return false,
};
if false_target_idx != latch_block_idx || !lp.body.contains(&then_block_idx) {
return false;
}
let array_id = match graph.node(load_id) {
Some(ValueNode::LoadKeyedGeneric { object, .. }) => *object,
Some(ValueNode::LoadFixedArrayElement { elements, .. }) => *elements,
_ => return false,
};
let array_in_loop = lp.body.iter().any(|&bi| {
graph
.block(bi)
.map(|b| b.nodes.iter().any(|(nid, _)| *nid == array_id))
.unwrap_or(false)
});
if array_in_loop {
return false;
}
let then_block = match graph.block(then_block_idx) {
Some(block) => block,
None => return false,
};
if !matches!(
then_block.control,
Some(ControlNode::Jump { target }) if target == latch_block_idx
) {
return false;
}
let mut count_store = None;
for (store_id, node) in &then_block.nodes {
let ValueNode::StoreGlobal {
name,
value,
feedback_slot,
} = node
else {
continue;
};
let Some((left, right)) = add_operands(graph.node(*value)) else {
continue;
};
let other = if find_i32_constant(graph, left) == Some(1) {
right
} else if find_i32_constant(graph, right) == Some(1) {
left
} else {
continue;
};
if matches!(
graph.node(other),
Some(ValueNode::LoadGlobal { name: load_name, .. }) if load_name == name
) {
count_store = Some((*store_id, *name, *feedback_slot));
break;
}
}
let (count_store_id, count_name, count_feedback_slot) = match count_store {
Some(found) => found,
None => return false,
};
let preheader = match graph.block(lp.preheader) {
Some(block) => block,
None => return false,
};
let count_initialized_to_zero = preheader.nodes.iter().any(|(_, node)| {
matches!(
node,
ValueNode::StoreGlobal { name, value, .. }
if *name == count_name && find_i32_constant(graph, *value) == Some(0)
)
});
if !count_initialized_to_zero {
return false;
}
for &block_id in &lp.body {
let block = match graph.block(block_id) {
Some(block) => block,
None => return false,
};
for (nid, node) in &block.nodes {
match node {
ValueNode::StoreGlobal { name, .. } => {
if *nid != count_store_id || *name != count_name {
return false;
}
}
ValueNode::LoadGlobal { name, .. } => {
if *name != count_name {
return false;
}
}
ValueNode::LoadKeyedGeneric { .. } | ValueNode::LoadFixedArrayElement { .. } => {
if *nid != load_id {
return false;
}
}
ValueNode::ToBoolean { value } => {
if *value != load_id {
return false;
}
}
ValueNode::GenericAdd { .. }
| ValueNode::Int32Add { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::GenericIncrement { .. }
| ValueNode::Int32Increment { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::Phi { .. }
| ValueNode::SmiConstant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Int32LessThan { .. }
| ValueNode::Int32LessThanOrEqual { .. }
| ValueNode::CheckSmi { .. } => {}
_ => return false,
}
}
}
let count_id = if inclusive_bound {
let one_id = graph.alloc_node_id();
let count_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(one_id, ValueNode::SmiConstant { value: 1 });
pre.push_with_id(
count_id,
ValueNode::Int32Add {
left: limit_id,
right: one_id,
},
);
}
count_id
} else {
limit_id
};
let fusion_id = graph.alloc_node_id();
let store_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
fusion_id,
ValueNode::SpeculativeCountTruthyFusion {
array: array_id,
count: count_id,
},
);
pre.push_with_id(
store_id,
ValueNode::StoreGlobal {
name: count_name,
value: fusion_id,
feedback_slot: count_feedback_slot,
},
);
}
if let Some(header) = graph.block_mut(lp.header) {
for (nid, node) in &mut header.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
inputs[entry_pos] = count_id;
inputs[back_pred_pos] = *nid;
}
break;
}
}
}
true
}
fn add_operands(node: Option<&ValueNode>) -> Option<(NodeId, NodeId)> {
match node? {
ValueNode::GenericAdd { left, right, .. }
| ValueNode::Int32Add { left, right }
| ValueNode::CheckedSmiAdd { left, right } => Some((*left, *right)),
_ => None,
}
}
fn find_call_callee(graph: &MaglevGraph, node_id: NodeId) -> Option<NodeId> {
find_call_callee_node(graph.node(node_id)?)
}
fn find_call_callee_node(node: &ValueNode) -> Option<NodeId> {
match node {
ValueNode::Call { callee, args, .. } if args.is_empty() => Some(*callee),
ValueNode::CallKnownFunction { callee, args, .. } if args.is_empty() => Some(*callee),
_ => None,
}
}
fn resolve_fusion_pattern(
graph: &MaglevGraph,
callee_id: NodeId,
preheader: u32,
) -> (Option<u32>, Option<i64>) {
let mut target = callee_id;
let mut from_factory_call = false;
for _ in 0..8 {
match graph.node(target) {
Some(ValueNode::CreateClosure {
shared_function_info,
..
})
| Some(ValueNode::FastCreateClosure {
shared_function_info,
..
}) => {
if let Some(&(slot, k)) = graph.closure_fusion_patterns().get(shared_function_info)
{
return (Some(slot), Some(k));
}
if from_factory_call
&& let Some(&(slot, k)) =
graph.factory_fusion_patterns().get(shared_function_info)
{
return (Some(slot), Some(k));
}
return (None, None);
}
Some(ValueNode::Phi { inputs }) => {
if let Some(&inp) = inputs.iter().find(|&&i| i != target) {
target = inp;
continue;
}
return (None, None);
}
Some(ValueNode::LoadGlobal { name, .. }) => {
let callee_name = *name;
return resolve_factory_fusion(graph, callee_name, preheader);
}
Some(ValueNode::Call { callee, args, .. }) if args.is_empty() => {
from_factory_call = true;
target = *callee;
continue;
}
Some(ValueNode::CallKnownFunction { callee, args, .. }) if args.is_empty() => {
from_factory_call = true;
target = *callee;
continue;
}
_ => return (None, None),
}
}
(None, None)
}
fn resolve_factory_fusion(
graph: &MaglevGraph,
global_name: u32,
preheader: u32,
) -> (Option<u32>, Option<i64>) {
let mut stored_value = None;
for bi in (0..=preheader).rev() {
if let Some(blk) = graph.block(bi) {
for (_, node) in blk.nodes.iter().rev() {
if let ValueNode::StoreGlobal { name, value, .. } = node
&& *name == global_name
{
stored_value = Some(*value);
break;
}
}
if stored_value.is_some() {
break;
}
}
}
let stored_value = match stored_value {
Some(v) => v,
None => return (None, None),
};
let call_callee = match graph.node(stored_value) {
Some(ValueNode::Call { callee, args, .. }) if args.is_empty() => *callee,
Some(ValueNode::CallKnownFunction { callee, args, .. }) if args.is_empty() => *callee,
_ => return (None, None),
};
let mut target = call_callee;
for _ in 0..4 {
match graph.node(target) {
Some(ValueNode::CreateClosure {
shared_function_info,
..
})
| Some(ValueNode::FastCreateClosure {
shared_function_info,
..
}) => {
if let Some(&(slot, k)) = graph.factory_fusion_patterns().get(shared_function_info)
{
return (Some(slot), Some(k));
}
return (None, None);
}
Some(ValueNode::Phi { inputs }) => {
if let Some(&inp) = inputs.iter().find(|&&i| i != target) {
target = inp;
continue;
}
return (None, None);
}
Some(ValueNode::LoadGlobal { name, .. }) => {
let gn = *name;
let mut found = None;
for bi in 0..=preheader {
if let Some(blk) = graph.block(bi) {
for (_, node) in blk.nodes.iter().rev() {
if let ValueNode::StoreGlobal { name, value, .. } = node
&& *name == gn
{
found = Some(*value);
break;
}
}
if found.is_some() {
break;
}
}
}
match found {
Some(v) => {
target = v;
continue;
}
None => return (None, None),
}
}
_ => return (None, None),
}
}
(None, None)
}
#[allow(dead_code)]
const INLINE_SIZE_THRESHOLD: usize = 32;
const INLINE_PARAM_THRESHOLD: u32 = 8;
fn mark_inlining_candidates(graph: &mut MaglevGraph) {
let mut candidate_count = 0u32;
for block in graph.blocks_mut() {
for (_id, node) in &mut block.nodes {
if let ValueNode::CallKnownFunction { args, .. } = node {
if args.len() <= INLINE_PARAM_THRESHOLD as usize {
candidate_count += 1;
}
}
}
}
graph.set_inline_candidates(candidate_count);
}
pub const MAX_FUSED_OBJECT_PROPS: usize = 5;
fn fuse_object_literal_stores(graph: &mut MaglevGraph) {
for block in graph.blocks_mut() {
fuse_object_literal_stores_in_block(block);
}
}
fn fuse_object_literal_stores_in_block(block: &mut BasicBlock) {
let mut remove_indices: Vec<usize> = Vec::new();
let mut replacements: Vec<(usize, ValueNode)> = Vec::new();
let nodes = &block.nodes;
let len = nodes.len();
let mut i = 0;
while i < len {
let (create_id, create_node) = &nodes[i];
let (feedback_slot, flags) = match create_node {
ValueNode::CreateObjectLiteral {
feedback_slot,
flags,
..
} => (*feedback_slot, *flags),
ValueNode::CreateEmptyObjectLiteral => (u32::MAX, 0),
_ => {
i += 1;
continue;
}
};
let create_node_id = *create_id;
let mut names: Vec<u32> = Vec::new();
let mut values: Vec<NodeId> = Vec::new();
let mut j = i + 1;
let mut store_indices: Vec<usize> = Vec::new();
while j < len && names.len() < MAX_FUSED_OBJECT_PROPS {
let node = &nodes[j].1;
match node {
ValueNode::StoreNamedGeneric {
object,
name,
value,
..
} if *object == create_node_id => {
if *name > 0xFFF {
break;
}
names.push(*name);
values.push(*value);
store_indices.push(j);
j += 1;
}
_ => {
let mut refs_object = false;
visit_value_node_inputs(node, &mut |id| {
if id == create_node_id {
refs_object = true;
}
});
if refs_object {
break;
}
j += 1;
}
}
}
if names.is_empty() {
i += 1;
continue;
}
remove_indices.extend_from_slice(&store_indices);
replacements.push((
i,
ValueNode::CreateObjectLiteralWithProperties {
feedback_slot,
flags,
names,
values,
},
));
i = j;
}
for (idx, new_node) in replacements {
block.nodes[idx].1 = new_node;
}
remove_indices.sort_unstable();
for &idx in remove_indices.iter().rev() {
block.nodes.remove(idx);
}
}
fn forward_invariant_object_properties(graph: &mut MaglevGraph) {
let mut obj_props: HashMap<NodeId, HashMap<u32, NodeId>> = HashMap::new();
let mut global_to_obj: HashMap<u32, NodeId> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::CreateObjectLiteralWithProperties { names, values, .. } => {
let mut props = HashMap::new();
for (name, value) in names.iter().zip(values.iter()) {
props.insert(*name, *value);
}
obj_props.insert(*id, props);
}
ValueNode::StoreGlobal { name, value, .. } => {
if obj_props.contains_key(value) {
global_to_obj.insert(*name, *value);
}
}
_ => {}
}
}
}
if obj_props.is_empty() {
return;
}
for block in graph.blocks() {
for (_, node) in &block.nodes {
if let ValueNode::StoreNamedGeneric { object, .. } = node {
obj_props.remove(object);
for (&_gname, &obj_id) in &global_to_obj {
if *object == obj_id {
obj_props.remove(&obj_id);
}
}
}
}
}
if obj_props.is_empty() {
return;
}
let mut load_global_alias: HashMap<NodeId, NodeId> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if let ValueNode::LoadGlobal { name, .. } = node
&& let Some(&obj_id) = global_to_obj.get(name)
&& obj_props.contains_key(&obj_id)
{
load_global_alias.insert(*id, obj_id);
}
}
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if let ValueNode::LoadNamedGeneric { object, name, .. } = node {
let mut resolved = load_global_alias.get(object).copied().unwrap_or(*object);
if !obj_props.contains_key(&resolved)
&& let Some(&sub) = subst.get(&resolved)
{
resolved = sub;
}
if let Some(props) = obj_props.get(&resolved)
&& let Some(&value) = props.get(name)
{
subst.insert(*id, value);
}
}
}
}
if subst.is_empty() {
return;
}
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
if subst.contains_key(id) {
*node = ValueNode::UndefinedConstant;
}
}
apply_subst_to_block(block, &subst);
}
}
fn eliminate_store_to_load(graph: &mut MaglevGraph) {
let mut global_subst: HashMap<NodeId, NodeId> = HashMap::new();
let mut block_store_maps: HashMap<u32, HashMap<(NodeId, u32), NodeId>> = HashMap::new();
let mut block_global_maps: HashMap<u32, HashMap<u32, NodeId>> = HashMap::new();
let mut block_alias_maps: HashMap<u32, HashMap<NodeId, NodeId>> = HashMap::new();
for block in graph.blocks() {
let single_pred = if block.predecessors.len() == 1 {
Some(block.predecessors[0])
} else {
None
};
let mut store_map: HashMap<(NodeId, u32), NodeId> = single_pred
.and_then(|p| block_store_maps.get(&p).cloned())
.unwrap_or_default();
let mut global_map: HashMap<u32, NodeId> = single_pred
.and_then(|p| block_global_maps.get(&p).cloned())
.unwrap_or_default();
let mut alias_map: HashMap<NodeId, NodeId> = single_pred
.and_then(|p| block_alias_maps.get(&p).cloned())
.unwrap_or_default();
let subst = compute_store_to_load_subst_with_map(
block,
&mut store_map,
&mut global_map,
&mut alias_map,
);
block_store_maps.insert(block.id, store_map);
block_global_maps.insert(block.id, global_map);
block_alias_maps.insert(block.id, alias_map);
global_subst.extend(subst);
}
if global_subst.is_empty() {
return;
}
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
if global_subst.contains_key(id) {
*node = ValueNode::UndefinedConstant;
}
}
apply_subst_to_block(block, &global_subst);
}
}
fn compute_store_to_load_subst_with_map(
block: &BasicBlock,
store_map: &mut HashMap<(NodeId, u32), NodeId>,
global_map: &mut HashMap<u32, NodeId>,
alias_map: &mut HashMap<NodeId, NodeId>,
) -> HashMap<NodeId, NodeId> {
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (id, node) in &block.nodes {
match node {
ValueNode::CreateObjectLiteralWithProperties { names, values, .. } => {
let obj_id = *id;
for (name, value) in names.iter().zip(values.iter()) {
store_map.insert((obj_id, *name), *value);
}
}
ValueNode::StoreGlobal { name, value, .. } => {
global_map.insert(*name, *value);
}
ValueNode::LoadGlobal { name, .. } => {
if let Some(&stored_value) = global_map.get(name) {
subst.insert(*id, stored_value);
alias_map.insert(*id, stored_value);
}
}
ValueNode::StoreNamedGeneric {
object,
name,
value,
..
} => {
let resolved_obj = alias_map.get(object).copied().unwrap_or(*object);
store_map.insert((resolved_obj, *name), *value);
}
ValueNode::LoadNamedGeneric { object, name, .. } => {
let resolved_obj = alias_map.get(object).copied().unwrap_or(*object);
if let Some(&stored_value) = store_map.get(&(resolved_obj, *name)) {
subst.insert(*id, stored_value);
alias_map.insert(*id, stored_value);
}
}
other => {
if can_invalidate_named_stores(other) {
store_map.clear();
global_map.clear();
} else if has_side_effects(other) {
global_map.clear();
}
}
}
}
subst
}
fn forward_loop_object_properties(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
if loops.is_empty() {
return;
}
let mut consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::SmiConstant { value } | ValueNode::Int32Constant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
}
for lp in &loops {
try_forward_loop_object(graph, lp, &consts);
}
}
fn try_forward_loop_object(
graph: &mut MaglevGraph,
lp: &licm::NaturalLoop,
consts: &HashMap<NodeId, i32>,
) -> bool {
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (condition_id, body_block_idx, exit_block_idx) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_block_idx) {
return false;
}
if lp.body.contains(&exit_block_idx) {
return false;
}
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header.nodes {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match &found {
Some(ValueNode::Int32LessThan { left, right }) => (*left, *right),
_ => return false,
}
};
let iv_phi_id = cmp_left;
let header = graph.block(lp.header).unwrap();
let iv_phi_inputs = {
let mut found = None;
for (nid, node) in &header.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node {
found = Some(inputs.clone());
}
break;
}
}
match found {
Some(inputs) if inputs.len() == 2 => inputs,
_ => return false,
}
};
let back_pred_pos = match header
.predecessors
.iter()
.position(|&p| p == body_block_idx)
{
Some(pos) => pos,
None => return false,
};
let entry_pos = match header.predecessors.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_init = match consts.get(&iv_phi_inputs[entry_pos]) {
Some(&v) => v,
None => match find_i32_constant(graph, iv_phi_inputs[entry_pos]) {
Some(v) => v,
None => return false,
},
};
let iv_limit = match consts.get(&cmp_right) {
Some(&v) => v,
None => match find_i32_constant(graph, cmp_right) {
Some(v) => v,
None => return false,
},
};
let iv_back_id = iv_phi_inputs[back_pred_pos];
let iv_step = match find_increment_step(graph, iv_back_id, iv_phi_id) {
Some(s) if s > 0 => s,
_ => return false,
};
let range = (iv_limit as i64) - (iv_init as i64);
let step = iv_step as i64;
if range <= 0 || range % step != 0 {
return false;
}
if range / step == 0 {
return false;
}
let iv_final = iv_limit - iv_step;
let header = graph.block(lp.header).unwrap();
let mut obj_phi_id: Option<NodeId> = None;
let mut create_obj_id: Option<NodeId> = None;
let mut create_names: Vec<u32> = Vec::new();
let mut create_values: Vec<NodeId> = Vec::new();
for (nid, node) in &header.nodes {
if *nid == iv_phi_id {
continue;
}
if let ValueNode::Phi { inputs } = node
&& inputs.len() == 2
{
let back_edge_id = inputs[back_pred_pos];
if let Some(ValueNode::CreateObjectLiteralWithProperties { names, values, .. }) =
graph.node(back_edge_id)
{
obj_phi_id = Some(*nid);
create_obj_id = Some(back_edge_id);
create_names = names.clone();
create_values = values.clone();
break;
}
}
}
let obj_phi_id = match obj_phi_id {
Some(id) => id,
None => return false,
};
let create_obj_id = create_obj_id.unwrap();
let mut final_values: Vec<Option<i32>> = Vec::new();
for &val_id in &create_values {
final_values.push(eval_at_iv(graph, val_id, iv_phi_id, iv_final, consts));
}
if final_values.iter().any(|v| v.is_none()) {
return false;
}
let mut prop_finals: HashMap<u32, i32> = HashMap::new();
for (name, val) in create_names.iter().zip(final_values.iter()) {
prop_finals.insert(*name, val.unwrap());
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
let mut new_constants: Vec<(NodeId, i32)> = Vec::new();
let mut pending: Vec<(NodeId, i32)> = Vec::new();
for block in graph.blocks() {
if lp.body.contains(&block.id) {
continue;
}
for (nid, node) in &block.nodes {
if let ValueNode::LoadNamedGeneric { object, name, .. } = node
&& *object == obj_phi_id
&& let Some(&final_val) = prop_finals.get(name)
{
pending.push((*nid, final_val));
}
}
}
if pending.is_empty() {
return false;
}
for (load_nid, final_val) in &pending {
let const_id = graph.alloc_node_id();
new_constants.push((const_id, *final_val));
subst.insert(*load_nid, const_id);
}
let replaced_set: HashSet<NodeId> = subst.keys().copied().collect();
let mut exit_store_globals_to_kill: Vec<NodeId> = Vec::new();
let mut truly_escapes = false;
for block in graph.blocks() {
for (nid, node) in &block.nodes {
if replaced_set.contains(nid) || *nid == obj_phi_id {
continue;
}
let refs = node_operands(node);
if refs.contains(&obj_phi_id) {
if !lp.body.contains(&block.id) && matches!(node, ValueNode::StoreGlobal { .. }) {
exit_store_globals_to_kill.push(*nid);
continue;
}
truly_escapes = true;
break;
}
}
if truly_escapes {
break;
}
if let Some(ctrl) = &block.control {
let ctrl_refs = control_operands(ctrl);
if ctrl_refs.contains(&obj_phi_id) {
truly_escapes = true;
break;
}
}
}
if truly_escapes {
return apply_load_replacements_only(graph, lp, exit_block_idx, &new_constants, &subst);
}
if let Some(exit_block) = graph.block_mut(exit_block_idx) {
for (idx, (const_id, val)) in new_constants.iter().enumerate() {
exit_block
.nodes
.insert(idx, (*const_id, ValueNode::SmiConstant { value: *val }));
}
}
for block in graph.blocks_mut() {
if lp.body.contains(&block.id) {
continue;
}
for (nid, node) in &mut block.nodes {
if subst.contains_key(nid) {
*node = ValueNode::UndefinedConstant;
}
if exit_store_globals_to_kill.contains(nid) {
*node = ValueNode::UndefinedConstant;
}
}
apply_subst_to_block(block, &subst);
}
for block in graph.blocks_mut() {
if !lp.body.contains(&block.id) || block.id == lp.header {
continue;
}
for (nid, node) in &mut block.nodes {
if *nid == create_obj_id {
*node = ValueNode::UndefinedConstant;
}
}
}
if let Some(hdr) = graph.block_mut(lp.header) {
for (nid, node) in &mut hdr.nodes {
if *nid == obj_phi_id
&& let ValueNode::Phi { inputs } = node
{
inputs[back_pred_pos] = inputs[entry_pos];
}
}
}
true
}
fn apply_load_replacements_only(
graph: &mut MaglevGraph,
lp: &licm::NaturalLoop,
exit_block_idx: u32,
new_constants: &[(NodeId, i32)],
subst: &HashMap<NodeId, NodeId>,
) -> bool {
if let Some(exit_block) = graph.block_mut(exit_block_idx) {
for (idx, (const_id, val)) in new_constants.iter().enumerate() {
exit_block
.nodes
.insert(idx, (*const_id, ValueNode::SmiConstant { value: *val }));
}
}
for block in graph.blocks_mut() {
if lp.body.contains(&block.id) {
continue;
}
for (nid, node) in &mut block.nodes {
if subst.contains_key(nid) {
*node = ValueNode::UndefinedConstant;
}
}
apply_subst_to_block(block, subst);
}
true
}
fn node_operands(node: &ValueNode) -> Vec<NodeId> {
match node {
ValueNode::Phi { inputs } => inputs.clone(),
ValueNode::Int32Add { left, right }
| ValueNode::Int32Subtract { left, right }
| ValueNode::Int32Multiply { left, right }
| ValueNode::Int32LessThan { left, right }
| ValueNode::Int32BitwiseOr { left, right }
| ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::Int32ShiftLeft { left, right }
| ValueNode::Int32ShiftRight { left, right }
| ValueNode::CheckedSmiAdd { left, right }
| ValueNode::CheckedSmiSubtract { left, right }
| ValueNode::CheckedSmiMultiply { left, right }
| ValueNode::GenericAdd { left, right, .. }
| ValueNode::GenericSubtract { left, right, .. }
| ValueNode::GenericMultiply { left, right, .. } => vec![*left, *right],
ValueNode::LoadNamedGeneric { object, .. } => vec![*object],
ValueNode::StoreNamedGeneric { object, value, .. } => vec![*object, *value],
ValueNode::StoreGlobal { value, .. } => vec![*value],
ValueNode::Call {
callee,
receiver,
args,
..
} => {
let mut v = vec![*callee, *receiver];
v.extend(args);
v
}
ValueNode::CallKnownFunction {
callee,
receiver,
args,
..
} => {
let mut v = vec![*callee, *receiver];
v.extend(args);
v
}
ValueNode::CreateObjectLiteralWithProperties { values, .. } => values.clone(),
ValueNode::CheckMaps { receiver, .. } => vec![*receiver],
_ => Vec::new(),
}
}
fn control_operands(ctrl: &ControlNode) -> Vec<NodeId> {
match ctrl {
ControlNode::Branch { condition, .. } => vec![*condition],
ControlNode::Return { value } => vec![*value],
_ => Vec::new(),
}
}
fn eval_at_iv(
graph: &MaglevGraph,
node_id: NodeId,
iv_phi: NodeId,
iv_value: i32,
consts: &HashMap<NodeId, i32>,
) -> Option<i32> {
if node_id == iv_phi {
return Some(iv_value);
}
if let Some(&v) = consts.get(&node_id) {
return Some(v);
}
let node = graph.node(node_id)?;
match node {
ValueNode::SmiConstant { value } | ValueNode::Int32Constant { value } => Some(*value),
ValueNode::Int32Add { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_add(r)
}
ValueNode::Int32Subtract { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_sub(r)
}
ValueNode::Int32Multiply { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_mul(r)
}
ValueNode::CheckedSmiAdd { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_add(r)
}
ValueNode::CheckedSmiSubtract { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_sub(r)
}
ValueNode::CheckedSmiMultiply { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_mul(r)
}
ValueNode::GenericAdd { left, right, .. } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_add(r)
}
ValueNode::GenericSubtract { left, right, .. } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_sub(r)
}
ValueNode::GenericMultiply { left, right, .. } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
l.checked_mul(r)
}
ValueNode::Int32BitwiseOr { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
Some(l | r)
}
ValueNode::Int32ShiftLeft { left, right } => {
let l = eval_at_iv(graph, *left, iv_phi, iv_value, consts)?;
let r = eval_at_iv(graph, *right, iv_phi, iv_value, consts)?;
Some(l.wrapping_shl(r as u32))
}
_ => None,
}
}
fn eliminate_dead_object_stores(graph: &mut MaglevGraph) {
let mut alloc_ids: HashSet<NodeId> = HashSet::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
if matches!(
node,
ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateObjectLiteralWithProperties { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
) {
alloc_ids.insert(*id);
}
}
}
if alloc_ids.is_empty() {
return;
}
let mut escapes: HashSet<NodeId> = HashSet::new();
let mut stores_per_alloc: HashMap<NodeId, Vec<(u32, usize)>> = HashMap::new();
for block in graph.blocks() {
for (idx, (_id, node)) in block.nodes.iter().enumerate() {
match node {
ValueNode::StoreNamedGeneric { object, .. } if alloc_ids.contains(object) => {
stores_per_alloc
.entry(*object)
.or_default()
.push((block.id, idx));
}
_ => {
visit_value_node_inputs(node, &mut |input| {
if alloc_ids.contains(&input) {
escapes.insert(input);
}
});
}
}
}
if let Some(ctrl) = &block.control {
collect_control_node_inputs(ctrl, &mut escapes);
}
}
for (alloc_id, store_locs) in &stores_per_alloc {
if escapes.contains(alloc_id) {
continue;
}
for &(block_id, node_idx) in store_locs {
if let Some(block) = graph.blocks_mut().iter_mut().find(|b| b.id == block_id) {
block.nodes[node_idx].1 = ValueNode::UndefinedConstant;
}
}
}
}
fn eliminate_dead_allocations(graph: &mut MaglevGraph) {
let live = collect_live_ids(graph);
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
let is_dead_alloc = matches!(
node,
ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateObjectLiteralWithProperties { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
) && !live.contains(id);
if is_dead_alloc {
*node = ValueNode::UndefinedConstant;
}
}
}
}
fn replace_dead_arguments(graph: &mut MaglevGraph) {
let live = collect_live_ids(graph);
for block in graph.blocks_mut() {
for (id, node) in &mut block.nodes {
if matches!(
node,
ValueNode::CreateMappedArguments
| ValueNode::CreateUnmappedArguments
| ValueNode::CreateRestParameter
) && !live.contains(id)
{
*node = ValueNode::UndefinedConstant;
}
}
}
}
fn eliminate_dead_code(graph: &mut MaglevGraph) {
loop {
let live = collect_live_ids(graph);
let mut removed = 0usize;
for block in graph.blocks_mut() {
let before = block.nodes.len();
block.nodes.retain(|(id, node)| {
if has_side_effects(node) {
return true;
}
live.contains(id)
});
removed += before - block.nodes.len();
}
if removed == 0 {
break;
}
}
}
fn collect_live_ids(graph: &MaglevGraph) -> HashSet<NodeId> {
let mut live = HashSet::new();
for block in graph.blocks() {
for (_id, node) in &block.nodes {
collect_value_node_inputs(node, &mut live);
}
if let Some(ctrl) = &block.control {
collect_control_node_inputs(ctrl, &mut live);
}
}
live
}
#[allow(clippy::too_many_lines)]
fn collect_value_node_inputs(node: &ValueNode, live: &mut HashSet<NodeId>) {
match node {
ValueNode::SmiConstant { .. }
| ValueNode::Float64Constant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Uint32Constant { .. }
| ValueNode::BigIntConstant { .. }
| ValueNode::TrueConstant
| ValueNode::FalseConstant
| ValueNode::NullConstant
| ValueNode::UndefinedConstant
| ValueNode::RootConstant { .. }
| ValueNode::ExternalConstant { .. }
| ValueNode::StringConstant { .. }
| ValueNode::ConstantPoolEntry { .. }
| ValueNode::Parameter { .. }
| ValueNode::RegisterInput { .. }
| ValueNode::ArgumentsLength
| ValueNode::RestLength
| ValueNode::LoadGlobal { .. }
| ValueNode::LoadCurrentContextSlot { .. }
| ValueNode::ArgumentsElements { .. }
| ValueNode::RestElements { .. }
| ValueNode::VirtualObject { .. }
| ValueNode::CreateFunctionContext { .. }
| ValueNode::CreateBlockContext { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
| ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateMappedArguments
| ValueNode::CreateUnmappedArguments
| ValueNode::CreateRestParameter
| ValueNode::CreateRegExpLiteral { .. }
| ValueNode::CreateClosure { .. }
| ValueNode::FastCreateClosure { .. }
| ValueNode::GetTemplateObject { .. }
| ValueNode::Debugger
| ValueNode::Abort { .. } => {}
ValueNode::GetArgument { index } => {
live.insert(*index);
}
ValueNode::CheckedSmiIncrement { value }
| ValueNode::CheckedSmiDecrement { value }
| ValueNode::Int32Negate { value }
| ValueNode::Int32Increment { value }
| ValueNode::Int32Decrement { value }
| ValueNode::Float64Negate { value }
| ValueNode::Float64Ieee754Unary { value, .. }
| ValueNode::GenericBitwiseNot { value, .. }
| ValueNode::GenericNegate { value, .. }
| ValueNode::GenericIncrement { value, .. }
| ValueNode::GenericDecrement { value, .. }
| ValueNode::ChangeInt32ToFloat64 { input: value }
| ValueNode::ChangeUint32ToFloat64 { input: value }
| ValueNode::ChangeFloat64ToInt32 { input: value }
| ValueNode::CheckedFloat64ToInt32 { input: value }
| ValueNode::ChangeInt32ToTagged { input: value }
| ValueNode::ChangeUint32ToTagged { input: value }
| ValueNode::ChangeFloat64ToTagged { input: value }
| ValueNode::ChangeTaggedToInt32 { input: value }
| ValueNode::ChangeTaggedToUint32 { input: value }
| ValueNode::ChangeTaggedToFloat64 { input: value }
| ValueNode::CheckedTaggedToInt32 { input: value }
| ValueNode::CheckedTaggedToFloat64 { input: value }
| ValueNode::ToBoolean { value }
| ValueNode::TestNullOrUndefined { value }
| ValueNode::ToString { value, .. }
| ValueNode::ToObject { value, .. }
| ValueNode::ToName { value, .. }
| ValueNode::ToNumber { value, .. }
| ValueNode::ToNumberOrNumeric { value, .. }
| ValueNode::TypeOf { value }
| ValueNode::NumberToString { value, .. } => {
live.insert(*value);
}
ValueNode::CheckSmi { receiver }
| ValueNode::CheckNumber { receiver }
| ValueNode::CheckHeapObject { receiver }
| ValueNode::CheckSymbol { receiver }
| ValueNode::CheckString { receiver }
| ValueNode::CheckStringOrStringWrapper { receiver }
| ValueNode::CheckSeqOneByteString { receiver }
| ValueNode::CheckMaps { receiver, .. }
| ValueNode::CheckMapsWithMigration { receiver, .. }
| ValueNode::CheckValue { receiver, .. } => {
live.insert(*receiver);
}
ValueNode::CheckDynamicValue { receiver, expected } => {
live.insert(*receiver);
live.insert(*expected);
}
ValueNode::CheckInt32IsSmi { input }
| ValueNode::CheckUint32IsSmi { input }
| ValueNode::CheckHoleyFloat64IsSmi { input }
| ValueNode::CheckFloat64IsNan { input } => {
live.insert(*input);
}
ValueNode::LoadField { object, .. }
| ValueNode::LoadTaggedField { object, .. }
| ValueNode::LoadDoubleField { object, .. }
| ValueNode::LoadNamedGeneric { object, .. }
| ValueNode::ForInPrepare {
enumerator: object, ..
}
| ValueNode::StringLength { string: object } => {
live.insert(*object);
}
ValueNode::LoadEnumCacheLength { map } => {
live.insert(*map);
}
ValueNode::LoadKeyedGeneric { object, key, .. } => {
live.insert(*object);
live.insert(*key);
}
ValueNode::HasInPrototypeChain { object, prototype } => {
live.insert(*object);
live.insert(*prototype);
}
ValueNode::StoreField { object, value, .. } => {
live.insert(*object);
live.insert(*value);
}
ValueNode::StoreCurrentContextSlot { value, .. } | ValueNode::StoreGlobal { value, .. } => {
live.insert(*value);
}
ValueNode::LoadContextSlot { context, .. } => {
live.insert(*context);
}
ValueNode::StoreContextSlot { context, value, .. } => {
live.insert(*context);
live.insert(*value);
}
ValueNode::PushContext { context } | ValueNode::PopContext { context } => {
live.insert(*context);
}
ValueNode::LoadFixedArrayElement { elements, index }
| ValueNode::LoadFixedDoubleArrayElement { elements, index }
| ValueNode::LoadHoleyFixedDoubleArrayElement { elements, index } => {
live.insert(*elements);
live.insert(*index);
}
ValueNode::StoreFixedArrayElement {
elements,
index,
value,
}
| ValueNode::StoreFixedDoubleArrayElement {
elements,
index,
value,
} => {
live.insert(*elements);
live.insert(*index);
live.insert(*value);
}
ValueNode::StoreNamedGeneric { object, value, .. } => {
live.insert(*object);
live.insert(*value);
}
ValueNode::CreateObjectLiteralWithProperties { values, .. } => {
for &v in values {
live.insert(v);
}
}
ValueNode::StoreKeyedGeneric {
object, key, value, ..
} => {
live.insert(*object);
live.insert(*key);
live.insert(*value);
}
ValueNode::CheckedSmiAdd { left, right }
| ValueNode::CheckedSmiSubtract { left, right }
| ValueNode::CheckedSmiMultiply { left, right }
| ValueNode::CheckedSmiDivide { left, right }
| ValueNode::CheckedSmiModulus { left, right }
| ValueNode::Int32Add { left, right }
| ValueNode::Int32Subtract { left, right }
| ValueNode::Int32Multiply { left, right }
| ValueNode::Int32Divide { left, right }
| ValueNode::Int32Modulus { left, right }
| ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::Int32BitwiseOr { left, right }
| ValueNode::Int32BitwiseXor { left, right }
| ValueNode::Int32ShiftLeft { left, right }
| ValueNode::Int32ShiftRight { left, right }
| ValueNode::Int32ShiftRightLogical { left, right }
| ValueNode::Uint32Add { left, right }
| ValueNode::Uint32Subtract { left, right }
| ValueNode::Uint32Multiply { left, right }
| ValueNode::Uint32Divide { left, right }
| ValueNode::Uint32Modulus { left, right }
| ValueNode::Float64Add { left, right }
| ValueNode::Float64Subtract { left, right }
| ValueNode::Float64Multiply { left, right }
| ValueNode::Float64Divide { left, right }
| ValueNode::Float64Modulus { left, right }
| ValueNode::Float64Exponentiate { left, right }
| ValueNode::Int32Equal { left, right }
| ValueNode::Int32StrictEqual { left, right }
| ValueNode::Int32LessThan { left, right }
| ValueNode::Int32LessThanOrEqual { left, right }
| ValueNode::Int32GreaterThan { left, right }
| ValueNode::Int32GreaterThanOrEqual { left, right }
| ValueNode::Float64Equal { left, right }
| ValueNode::Float64LessThan { left, right }
| ValueNode::Float64LessThanOrEqual { left, right }
| ValueNode::Float64GreaterThan { left, right }
| ValueNode::Float64GreaterThanOrEqual { left, right }
| ValueNode::StringConcat { left, right }
| ValueNode::StringEqual { left, right }
| ValueNode::GenericAdd { left, right, .. }
| ValueNode::GenericSubtract { left, right, .. }
| ValueNode::GenericMultiply { left, right, .. }
| ValueNode::GenericDivide { left, right, .. }
| ValueNode::GenericModulus { left, right, .. }
| ValueNode::GenericExponentiate { left, right, .. }
| ValueNode::GenericBitwiseAnd { left, right, .. }
| ValueNode::GenericBitwiseOr { left, right, .. }
| ValueNode::GenericBitwiseXor { left, right, .. }
| ValueNode::GenericShiftLeft { left, right, .. }
| ValueNode::GenericShiftRight { left, right, .. }
| ValueNode::GenericShiftRightLogical { left, right, .. }
| ValueNode::TaggedEqual { left, right, .. }
| ValueNode::TaggedNotEqual { left, right, .. } => {
live.insert(*left);
live.insert(*right);
}
ValueNode::CheckInt32Condition { left, right, .. } => {
live.insert(*left);
live.insert(*right);
}
ValueNode::CheckCacheIndicesNotCleared { receiver, indices } => {
live.insert(*receiver);
live.insert(*indices);
}
ValueNode::TestInstanceOf {
object, callable, ..
} => {
live.insert(*object);
live.insert(*callable);
}
ValueNode::TestIn { key, object, .. } => {
live.insert(*key);
live.insert(*object);
}
ValueNode::TestUndetectable { value } | ValueNode::TestTypeOf { value, .. } => {
live.insert(*value);
}
ValueNode::StringAt { string, index } => {
live.insert(*string);
live.insert(*index);
}
ValueNode::ForInNext {
receiver,
cache_index,
cache_array,
..
} => {
live.insert(*receiver);
live.insert(*cache_index);
live.insert(*cache_array);
}
ValueNode::DeleteProperty { object, key, .. } => {
live.insert(*object);
live.insert(*key);
}
ValueNode::CreateCatchContext { exception, .. } => {
live.insert(*exception);
}
ValueNode::CreateWithContext { object, .. } => {
live.insert(*object);
}
ValueNode::Call {
callee,
receiver,
args,
..
}
| ValueNode::CallWithSpread {
callee,
receiver,
args,
..
}
| ValueNode::CallKnownFunction {
callee,
receiver,
args,
} => {
live.insert(*callee);
live.insert(*receiver);
for &a in args {
live.insert(a);
}
}
ValueNode::CallArrayPush { receiver, args, .. } => {
live.insert(*receiver);
for &a in args {
live.insert(a);
}
}
ValueNode::CallBuiltin { args, .. } | ValueNode::CallRuntime { args, .. } => {
for &a in args {
live.insert(a);
}
}
ValueNode::SpeculativeCallFusion { callee, .. } => {
live.insert(*callee);
}
ValueNode::SpeculativeSumFusion { array } => {
live.insert(*array);
}
ValueNode::SpeculativePushFusion { array, .. } => {
live.insert(*array);
}
ValueNode::SpeculativeFillTrueFusion { array, count } => {
live.insert(*array);
live.insert(*count);
}
ValueNode::SpeculativeCountTruthyFusion { array, count } => {
live.insert(*array);
live.insert(*count);
}
ValueNode::Construct {
constructor, args, ..
}
| ValueNode::ConstructWithSpread {
constructor, args, ..
} => {
live.insert(*constructor);
for &a in args {
live.insert(a);
}
}
ValueNode::Phi { inputs } => {
for &inp in inputs {
live.insert(inp);
}
}
}
}
fn collect_control_node_inputs(ctrl: &ControlNode, live: &mut HashSet<NodeId>) {
match ctrl {
ControlNode::Return { value } => {
live.insert(*value);
}
ControlNode::Branch { condition, .. } => {
live.insert(*condition);
}
ControlNode::Jump { .. } | ControlNode::Deoptimize { .. } => {}
}
}
fn has_side_effects(node: &ValueNode) -> bool {
matches!(
node,
ValueNode::StoreField { .. }
| ValueNode::StoreFixedArrayElement { .. }
| ValueNode::StoreFixedDoubleArrayElement { .. }
| ValueNode::StoreNamedGeneric { .. }
| ValueNode::StoreKeyedGeneric { .. }
| ValueNode::StoreGlobal { .. }
| ValueNode::StoreContextSlot { .. }
| ValueNode::StoreCurrentContextSlot { .. }
| ValueNode::Call { .. }
| ValueNode::CallArrayPush { .. }
| ValueNode::CallKnownFunction { .. }
| ValueNode::CallBuiltin { .. }
| ValueNode::CallRuntime { .. }
| ValueNode::CallWithSpread { .. }
| ValueNode::Construct { .. }
| ValueNode::ConstructWithSpread { .. }
| ValueNode::SpeculativeCallFusion { .. }
| ValueNode::SpeculativeSumFusion { .. }
| ValueNode::SpeculativePushFusion { .. }
| ValueNode::SpeculativeFillTrueFusion { .. }
| ValueNode::SpeculativeCountTruthyFusion { .. }
| ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateObjectLiteralWithProperties { .. }
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
| ValueNode::CreateFunctionContext { .. }
| ValueNode::CreateBlockContext { .. }
| ValueNode::CreateCatchContext { .. }
| ValueNode::CreateWithContext { .. }
| ValueNode::PushContext { .. }
| ValueNode::PopContext { .. }
| ValueNode::CreateClosure { .. }
| ValueNode::FastCreateClosure { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateMappedArguments
| ValueNode::CreateUnmappedArguments
| ValueNode::CreateRestParameter
| ValueNode::CreateRegExpLiteral { .. }
| ValueNode::CheckSmi { .. }
| ValueNode::CheckNumber { .. }
| ValueNode::CheckHeapObject { .. }
| ValueNode::CheckSymbol { .. }
| ValueNode::CheckString { .. }
| ValueNode::CheckStringOrStringWrapper { .. }
| ValueNode::CheckSeqOneByteString { .. }
| ValueNode::CheckMaps { .. }
| ValueNode::CheckMapsWithMigration { .. }
| ValueNode::CheckValue { .. }
| ValueNode::CheckDynamicValue { .. }
| ValueNode::CheckInt32IsSmi { .. }
| ValueNode::CheckUint32IsSmi { .. }
| ValueNode::CheckHoleyFloat64IsSmi { .. }
| ValueNode::CheckInt32Condition { .. }
| ValueNode::CheckCacheIndicesNotCleared { .. }
| ValueNode::CheckFloat64IsNan { .. }
| ValueNode::CheckedSmiAdd { .. }
| ValueNode::CheckedSmiSubtract { .. }
| ValueNode::CheckedSmiMultiply { .. }
| ValueNode::CheckedSmiDivide { .. }
| ValueNode::CheckedSmiModulus { .. }
| ValueNode::CheckedSmiIncrement { .. }
| ValueNode::CheckedSmiDecrement { .. }
| ValueNode::CheckedFloat64ToInt32 { .. }
| ValueNode::CheckedTaggedToInt32 { .. }
| ValueNode::CheckedTaggedToFloat64 { .. }
| ValueNode::Debugger
| ValueNode::Abort { .. }
| ValueNode::DeleteProperty { .. }
| ValueNode::ForInPrepare { .. }
| ValueNode::ForInNext { .. }
)
}
fn can_invalidate_named_stores(node: &ValueNode) -> bool {
matches!(
node,
ValueNode::StoreField { .. }
| ValueNode::StoreFixedArrayElement { .. }
| ValueNode::StoreFixedDoubleArrayElement { .. }
| ValueNode::StoreNamedGeneric { .. }
| ValueNode::StoreKeyedGeneric { .. }
| ValueNode::StoreGlobal { .. }
| ValueNode::StoreContextSlot { .. }
| ValueNode::StoreCurrentContextSlot { .. }
| ValueNode::Call { .. }
| ValueNode::CallArrayPush { .. }
| ValueNode::CallKnownFunction { .. }
| ValueNode::CallBuiltin { .. }
| ValueNode::CallRuntime { .. }
| ValueNode::CallWithSpread { .. }
| ValueNode::Construct { .. }
| ValueNode::ConstructWithSpread { .. }
| ValueNode::SpeculativeCallFusion { .. }
| ValueNode::SpeculativeSumFusion { .. }
| ValueNode::SpeculativePushFusion { .. }
| ValueNode::SpeculativeFillTrueFusion { .. }
| ValueNode::SpeculativeCountTruthyFusion { .. }
| ValueNode::DeleteProperty { .. }
| ValueNode::ForInPrepare { .. }
| ValueNode::ForInNext { .. }
)
}
fn apply_subst_to_block(block: &mut BasicBlock, subst: &HashMap<NodeId, NodeId>) {
let resolve = |id: NodeId| *subst.get(&id).unwrap_or(&id);
for (_id, node) in &mut block.nodes {
apply_subst_to_value_node(node, &resolve);
}
if let Some(ctrl) = &mut block.control {
apply_subst_to_control_node(ctrl, &resolve);
}
}
#[allow(clippy::too_many_lines)]
fn apply_subst_to_value_node(node: &mut ValueNode, resolve: &impl Fn(NodeId) -> NodeId) {
match node {
ValueNode::SmiConstant { .. }
| ValueNode::Float64Constant { .. }
| ValueNode::Int32Constant { .. }
| ValueNode::Uint32Constant { .. }
| ValueNode::BigIntConstant { .. }
| ValueNode::TrueConstant
| ValueNode::FalseConstant
| ValueNode::NullConstant
| ValueNode::UndefinedConstant
| ValueNode::RootConstant { .. }
| ValueNode::ExternalConstant { .. }
| ValueNode::StringConstant { .. }
| ValueNode::ConstantPoolEntry { .. }
| ValueNode::Parameter { .. }
| ValueNode::RegisterInput { .. }
| ValueNode::ArgumentsLength
| ValueNode::RestLength
| ValueNode::LoadGlobal { .. }
| ValueNode::LoadCurrentContextSlot { .. }
| ValueNode::ArgumentsElements { .. }
| ValueNode::RestElements { .. }
| ValueNode::VirtualObject { .. }
| ValueNode::CreateFunctionContext { .. }
| ValueNode::CreateBlockContext { .. }
| ValueNode::CreateShallowObjectLiteral { .. }
| ValueNode::CreateShallowArrayLiteral { .. }
| ValueNode::CreateObjectLiteral { .. }
| ValueNode::CreateArrayLiteral { .. }
| ValueNode::CreateEmptyObjectLiteral
| ValueNode::CreateEmptyArrayLiteral { .. }
| ValueNode::CreateMappedArguments
| ValueNode::CreateUnmappedArguments
| ValueNode::CreateRestParameter
| ValueNode::CreateRegExpLiteral { .. }
| ValueNode::CreateClosure { .. }
| ValueNode::FastCreateClosure { .. }
| ValueNode::GetTemplateObject { .. }
| ValueNode::Debugger
| ValueNode::Abort { .. } => {}
ValueNode::GetArgument { index } => *index = resolve(*index),
ValueNode::CheckedSmiIncrement { value }
| ValueNode::CheckedSmiDecrement { value }
| ValueNode::Int32Negate { value }
| ValueNode::Int32Increment { value }
| ValueNode::Int32Decrement { value }
| ValueNode::Float64Negate { value }
| ValueNode::Float64Ieee754Unary { value, .. }
| ValueNode::GenericBitwiseNot { value, .. }
| ValueNode::GenericNegate { value, .. }
| ValueNode::GenericIncrement { value, .. }
| ValueNode::GenericDecrement { value, .. }
| ValueNode::ChangeInt32ToFloat64 { input: value }
| ValueNode::ChangeUint32ToFloat64 { input: value }
| ValueNode::ChangeFloat64ToInt32 { input: value }
| ValueNode::CheckedFloat64ToInt32 { input: value }
| ValueNode::ChangeInt32ToTagged { input: value }
| ValueNode::ChangeUint32ToTagged { input: value }
| ValueNode::ChangeFloat64ToTagged { input: value }
| ValueNode::ChangeTaggedToInt32 { input: value }
| ValueNode::ChangeTaggedToUint32 { input: value }
| ValueNode::ChangeTaggedToFloat64 { input: value }
| ValueNode::CheckedTaggedToInt32 { input: value }
| ValueNode::CheckedTaggedToFloat64 { input: value }
| ValueNode::ToBoolean { value }
| ValueNode::ToString { value, .. }
| ValueNode::ToObject { value, .. }
| ValueNode::ToName { value, .. }
| ValueNode::ToNumber { value, .. }
| ValueNode::ToNumberOrNumeric { value, .. }
| ValueNode::TypeOf { value }
| ValueNode::NumberToString { value, .. }
| ValueNode::TestUndetectable { value }
| ValueNode::TestNullOrUndefined { value }
| ValueNode::TestTypeOf { value, .. } => *value = resolve(*value),
ValueNode::CheckSmi { receiver }
| ValueNode::CheckNumber { receiver }
| ValueNode::CheckHeapObject { receiver }
| ValueNode::CheckSymbol { receiver }
| ValueNode::CheckString { receiver }
| ValueNode::CheckStringOrStringWrapper { receiver }
| ValueNode::CheckSeqOneByteString { receiver }
| ValueNode::CheckMaps { receiver, .. }
| ValueNode::CheckMapsWithMigration { receiver, .. }
| ValueNode::CheckValue { receiver, .. } => *receiver = resolve(*receiver),
ValueNode::CheckDynamicValue { receiver, expected } => {
*receiver = resolve(*receiver);
*expected = resolve(*expected);
}
ValueNode::CheckInt32IsSmi { input }
| ValueNode::CheckUint32IsSmi { input }
| ValueNode::CheckHoleyFloat64IsSmi { input }
| ValueNode::CheckFloat64IsNan { input } => *input = resolve(*input),
ValueNode::LoadField { object, .. }
| ValueNode::LoadTaggedField { object, .. }
| ValueNode::LoadDoubleField { object, .. }
| ValueNode::LoadNamedGeneric { object, .. }
| ValueNode::LoadEnumCacheLength { map: object }
| ValueNode::StringLength { string: object } => *object = resolve(*object),
ValueNode::LoadKeyedGeneric { object, key, .. } => {
*object = resolve(*object);
*key = resolve(*key);
}
ValueNode::HasInPrototypeChain { object, prototype } => {
*object = resolve(*object);
*prototype = resolve(*prototype);
}
ValueNode::StoreField { object, value, .. } => {
*object = resolve(*object);
*value = resolve(*value);
}
ValueNode::StoreCurrentContextSlot { value, .. } | ValueNode::StoreGlobal { value, .. } => {
*value = resolve(*value);
}
ValueNode::LoadContextSlot { context, .. } => *context = resolve(*context),
ValueNode::StoreContextSlot { context, value, .. } => {
*context = resolve(*context);
*value = resolve(*value);
}
ValueNode::PushContext { context } | ValueNode::PopContext { context } => {
*context = resolve(*context);
}
ValueNode::LoadFixedArrayElement { elements, index }
| ValueNode::LoadFixedDoubleArrayElement { elements, index }
| ValueNode::LoadHoleyFixedDoubleArrayElement { elements, index } => {
*elements = resolve(*elements);
*index = resolve(*index);
}
ValueNode::StoreFixedArrayElement {
elements,
index,
value,
}
| ValueNode::StoreFixedDoubleArrayElement {
elements,
index,
value,
} => {
*elements = resolve(*elements);
*index = resolve(*index);
*value = resolve(*value);
}
ValueNode::StoreNamedGeneric { object, value, .. } => {
*object = resolve(*object);
*value = resolve(*value);
}
ValueNode::CreateObjectLiteralWithProperties { values, .. } => {
for v in values {
*v = resolve(*v);
}
}
ValueNode::StoreKeyedGeneric {
object, key, value, ..
} => {
*object = resolve(*object);
*key = resolve(*key);
*value = resolve(*value);
}
ValueNode::CheckedSmiAdd { left, right }
| ValueNode::CheckedSmiSubtract { left, right }
| ValueNode::CheckedSmiMultiply { left, right }
| ValueNode::CheckedSmiDivide { left, right }
| ValueNode::CheckedSmiModulus { left, right }
| ValueNode::Int32Add { left, right }
| ValueNode::Int32Subtract { left, right }
| ValueNode::Int32Multiply { left, right }
| ValueNode::Int32Divide { left, right }
| ValueNode::Int32Modulus { left, right }
| ValueNode::Int32BitwiseAnd { left, right }
| ValueNode::Int32BitwiseOr { left, right }
| ValueNode::Int32BitwiseXor { left, right }
| ValueNode::Int32ShiftLeft { left, right }
| ValueNode::Int32ShiftRight { left, right }
| ValueNode::Int32ShiftRightLogical { left, right }
| ValueNode::Uint32Add { left, right }
| ValueNode::Uint32Subtract { left, right }
| ValueNode::Uint32Multiply { left, right }
| ValueNode::Uint32Divide { left, right }
| ValueNode::Uint32Modulus { left, right }
| ValueNode::Float64Add { left, right }
| ValueNode::Float64Subtract { left, right }
| ValueNode::Float64Multiply { left, right }
| ValueNode::Float64Divide { left, right }
| ValueNode::Float64Modulus { left, right }
| ValueNode::Float64Exponentiate { left, right }
| ValueNode::Int32Equal { left, right }
| ValueNode::Int32StrictEqual { left, right }
| ValueNode::Int32LessThan { left, right }
| ValueNode::Int32LessThanOrEqual { left, right }
| ValueNode::Int32GreaterThan { left, right }
| ValueNode::Int32GreaterThanOrEqual { left, right }
| ValueNode::Float64Equal { left, right }
| ValueNode::Float64LessThan { left, right }
| ValueNode::Float64LessThanOrEqual { left, right }
| ValueNode::Float64GreaterThan { left, right }
| ValueNode::Float64GreaterThanOrEqual { left, right }
| ValueNode::StringConcat { left, right }
| ValueNode::StringEqual { left, right }
| ValueNode::GenericAdd { left, right, .. }
| ValueNode::GenericSubtract { left, right, .. }
| ValueNode::GenericMultiply { left, right, .. }
| ValueNode::GenericDivide { left, right, .. }
| ValueNode::GenericModulus { left, right, .. }
| ValueNode::GenericExponentiate { left, right, .. }
| ValueNode::GenericBitwiseAnd { left, right, .. }
| ValueNode::GenericBitwiseOr { left, right, .. }
| ValueNode::GenericBitwiseXor { left, right, .. }
| ValueNode::GenericShiftLeft { left, right, .. }
| ValueNode::GenericShiftRight { left, right, .. }
| ValueNode::GenericShiftRightLogical { left, right, .. }
| ValueNode::TaggedEqual { left, right, .. }
| ValueNode::TaggedNotEqual { left, right, .. } => {
*left = resolve(*left);
*right = resolve(*right);
}
ValueNode::CheckInt32Condition { left, right, .. } => {
*left = resolve(*left);
*right = resolve(*right);
}
ValueNode::CheckCacheIndicesNotCleared { receiver, indices } => {
*receiver = resolve(*receiver);
*indices = resolve(*indices);
}
ValueNode::TestInstanceOf {
object, callable, ..
} => {
*object = resolve(*object);
*callable = resolve(*callable);
}
ValueNode::TestIn { key, object, .. } => {
*key = resolve(*key);
*object = resolve(*object);
}
ValueNode::StringAt { string, index } => {
*string = resolve(*string);
*index = resolve(*index);
}
ValueNode::ForInPrepare { enumerator, .. } => *enumerator = resolve(*enumerator),
ValueNode::ForInNext {
receiver,
cache_index,
cache_array,
..
} => {
*receiver = resolve(*receiver);
*cache_index = resolve(*cache_index);
*cache_array = resolve(*cache_array);
}
ValueNode::DeleteProperty { object, key, .. } => {
*object = resolve(*object);
*key = resolve(*key);
}
ValueNode::CreateCatchContext { exception, .. } => *exception = resolve(*exception),
ValueNode::CreateWithContext { object, .. } => *object = resolve(*object),
ValueNode::Call {
callee,
receiver,
args,
..
}
| ValueNode::CallArrayPush {
callee,
receiver,
args,
..
}
| ValueNode::CallWithSpread {
callee,
receiver,
args,
..
}
| ValueNode::CallKnownFunction {
callee,
receiver,
args,
} => {
*callee = resolve(*callee);
*receiver = resolve(*receiver);
for a in args.iter_mut() {
*a = resolve(*a);
}
}
ValueNode::CallBuiltin { args, .. } | ValueNode::CallRuntime { args, .. } => {
for a in args.iter_mut() {
*a = resolve(*a);
}
}
ValueNode::SpeculativeCallFusion { callee, .. } => {
*callee = resolve(*callee);
}
ValueNode::SpeculativeSumFusion { array } => {
*array = resolve(*array);
}
ValueNode::SpeculativePushFusion { array, .. } => {
*array = resolve(*array);
}
ValueNode::SpeculativeFillTrueFusion { array, count } => {
*array = resolve(*array);
*count = resolve(*count);
}
ValueNode::SpeculativeCountTruthyFusion { array, count } => {
*array = resolve(*array);
*count = resolve(*count);
}
ValueNode::Construct {
constructor, args, ..
}
| ValueNode::ConstructWithSpread {
constructor, args, ..
} => {
*constructor = resolve(*constructor);
for a in args.iter_mut() {
*a = resolve(*a);
}
}
ValueNode::Phi { inputs } => {
for inp in inputs.iter_mut() {
*inp = resolve(*inp);
}
}
}
}
fn apply_subst_to_control_node(ctrl: &mut ControlNode, resolve: &impl Fn(NodeId) -> NodeId) {
match ctrl {
ControlNode::Return { value } => *value = resolve(*value),
ControlNode::Branch { condition, .. } => *condition = resolve(*condition),
ControlNode::Jump { .. } | ControlNode::Deoptimize { .. } => {}
}
}
fn unroll_simple_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
if !try_unroll_counted_loop(graph, lp, 4) {
try_unroll_counted_loop(graph, lp, 2);
}
}
}
fn try_unroll_counted_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop, factor: u32) -> bool {
if factor < 2 {
return false;
}
let header_idx = lp.header;
let header = match graph.block(header_idx) {
Some(b) => b,
None => return false,
};
let (condition_id, body_block_idx, _exit_block_idx) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_block_idx) {
return false;
}
if lp.body.len() != 2 || !lp.body.contains(&header_idx) {
return false;
}
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == header_idx => {}
_ => return false,
}
let has_method_call = body.nodes.iter().any(|(_, node)| {
matches!(
node,
ValueNode::Call { .. }
| ValueNode::CallKnownFunction { .. }
| ValueNode::CallWithSpread { .. }
| ValueNode::CallBuiltin { .. }
| ValueNode::CallRuntime { .. }
)
});
if has_method_call {
return false;
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header.nodes {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right),
_ => return false,
}
};
let back_edge_pred_pos = {
let h = graph.block(header_idx).unwrap();
match h.predecessors.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
}
};
let preheader_pred_pos = {
let h = graph.block(header_idx).unwrap();
match h.predecessors.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
}
};
let induction_phi_inputs = {
let h = graph.block(header_idx).unwrap();
let mut found = None;
for (nid, node) in &h.nodes {
if *nid == cmp_left {
if let ValueNode::Phi { inputs } = node {
found = Some(inputs.clone());
}
break;
}
}
match found {
Some(inputs) => inputs,
None => return false,
}
};
let init_id = induction_phi_inputs[preheader_pred_pos];
let limit_id = cmp_right;
let init_value = find_i32_constant(graph, init_id);
let limit_value = find_i32_constant(graph, limit_id);
let (init_val, limit_val) = match (init_value, limit_value) {
(Some(i), Some(l)) => (i, l),
_ => return false,
};
let back_edge_input = induction_phi_inputs[back_edge_pred_pos];
let step = find_increment_step(graph, back_edge_input, cmp_left);
let step_val = match step {
Some(s) if s > 0 => s,
_ => return false,
};
let trip_count = (limit_val - init_val) as i64;
if trip_count <= 0 {
return false;
}
let effective_step = (step_val as i64) * (factor as i64);
if trip_count % effective_step != 0 {
return false;
}
if trip_count < effective_step * 2 {
return false;
}
let header_phis: Vec<(NodeId, Vec<NodeId>)> = {
let h = graph.block(header_idx).unwrap();
h.nodes
.iter()
.filter_map(|(nid, node)| {
if let ValueNode::Phi { inputs } = node {
Some((*nid, inputs.clone()))
} else {
None
}
})
.collect()
};
let phi_to_back_input: HashMap<NodeId, NodeId> = header_phis
.iter()
.filter_map(|(phi_id, inputs)| {
inputs
.get(back_edge_pred_pos)
.map(|&back_input| (*phi_id, back_input))
})
.collect();
let body_nodes: Vec<(NodeId, ValueNode)> = graph.block(body_block_idx).unwrap().nodes.clone();
let mut prev_phi_to_output = phi_to_back_input.clone();
for _copy in 1..factor {
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (phi_id, output_id) in &prev_phi_to_output {
subst.insert(*phi_id, *output_id);
}
let mut old_to_new: HashMap<NodeId, NodeId> = HashMap::new();
for (old_id, _node) in &body_nodes {
let new_id = graph.alloc_node_id();
old_to_new.insert(*old_id, new_id);
}
let resolve = |id: NodeId| -> NodeId {
if let Some(&new_id) = old_to_new.get(&id) {
new_id
} else if let Some(&output_id) = subst.get(&id) {
output_id
} else {
id
}
};
let mut cloned_nodes: Vec<(NodeId, ValueNode)> = Vec::new();
for (old_id, node) in &body_nodes {
let new_id = old_to_new[old_id];
let mut cloned = node.clone();
apply_subst_to_value_node(&mut cloned, &resolve);
cloned_nodes.push((new_id, cloned));
}
let body_block = graph.block_mut(body_block_idx).unwrap();
for (id, node) in &cloned_nodes {
body_block.push_with_id(*id, node.clone());
}
let mut new_phi_to_output: HashMap<NodeId, NodeId> = HashMap::new();
for (phi_id, back_input) in &phi_to_back_input {
if let Some(&new_id) = old_to_new.get(back_input) {
new_phi_to_output.insert(*phi_id, new_id);
} else {
new_phi_to_output.insert(*phi_id, *back_input);
}
}
prev_phi_to_output = new_phi_to_output;
}
let header_block = graph.block_mut(header_idx).unwrap();
for (nid, node) in &mut header_block.nodes {
if let ValueNode::Phi { inputs } = node
&& let Some(&new_output) = prev_phi_to_output.get(nid)
&& let Some(back_input) = inputs.get_mut(back_edge_pred_pos)
{
*back_input = new_output;
}
}
true
}
fn find_i32_constant(graph: &MaglevGraph, id: NodeId) -> Option<i32> {
for block in graph.blocks() {
for (nid, node) in &block.nodes {
if *nid == id {
return match node {
ValueNode::Int32Constant { value } | ValueNode::SmiConstant { value } => {
Some(*value)
}
_ => None,
};
}
}
}
None
}
fn find_increment_step(graph: &MaglevGraph, result_id: NodeId, base_id: NodeId) -> Option<i32> {
let node = graph.node(result_id)?;
match node {
ValueNode::Int32Increment { value }
| ValueNode::CheckedSmiIncrement { value }
| ValueNode::GenericIncrement { value, .. } => {
if *value == base_id {
Some(1)
} else {
None
}
}
ValueNode::Int32Add { left, right }
| ValueNode::CheckedSmiAdd { left, right }
| ValueNode::GenericAdd { left, right, .. } => {
if *left == base_id {
find_i32_constant(graph, *right)
} else if *right == base_id {
find_i32_constant(graph, *left)
} else {
None
}
}
_ => None,
}
}
fn extract_affine_addend(
graph: &MaglevGraph,
expr_id: NodeId,
iv_phi_id: NodeId,
consts: &HashMap<NodeId, i32>,
depth: u32,
) -> Option<(i128, i128)> {
if depth > 8 {
return None;
}
if expr_id == iv_phi_id {
return Some((1, 0));
}
if let Some(&k) = consts.get(&expr_id) {
return Some((0, k as i128));
}
if let Some(k) = find_i32_constant(graph, expr_id) {
return Some((0, k as i128));
}
let node = graph.node(expr_id)?.clone();
match &node {
ValueNode::Int32Add { left, right } => {
let (a1, b1) = extract_affine_addend(graph, *left, iv_phi_id, consts, depth + 1)?;
let (a2, b2) = extract_affine_addend(graph, *right, iv_phi_id, consts, depth + 1)?;
Some((a1 + a2, b1 + b2))
}
ValueNode::Int32Subtract { left, right } => {
let (a1, b1) = extract_affine_addend(graph, *left, iv_phi_id, consts, depth + 1)?;
let (a2, b2) = extract_affine_addend(graph, *right, iv_phi_id, consts, depth + 1)?;
Some((a1 - a2, b1 - b2))
}
ValueNode::Int32Multiply { left, right } => {
let (a1, b1) = extract_affine_addend(graph, *left, iv_phi_id, consts, depth + 1)?;
let (a2, b2) = extract_affine_addend(graph, *right, iv_phi_id, consts, depth + 1)?;
if a1 == 0 {
Some((b1 * a2, b1 * b2))
} else if a2 == 0 {
Some((a1 * b2, b1 * b2))
} else {
None }
}
ValueNode::Int32ShiftLeft { left, right } => {
let (a, b) = extract_affine_addend(graph, *left, iv_phi_id, consts, depth + 1)?;
let shift = consts
.get(right)
.copied()
.or_else(|| find_i32_constant(graph, *right))?;
if (0..32).contains(&shift) {
let factor = 1i128 << (shift as u32);
Some((a * factor, b * factor))
} else {
None
}
}
ValueNode::Int32Negate { value } => {
let (a, b) = extract_affine_addend(graph, *value, iv_phi_id, consts, depth + 1)?;
Some((-a, -b))
}
_ => None,
}
}
fn peel_accumulator_addend(
graph: &MaglevGraph,
back_id: NodeId,
phi_acc_id: NodeId,
iv_phi_id: NodeId,
consts: &HashMap<NodeId, i32>,
depth: u32,
) -> Option<(i128, i128)> {
if depth > 4 {
return None;
}
let node = graph.node(back_id)?.clone();
match &node {
ValueNode::Int32Add { left, right } => {
if *left == phi_acc_id {
return extract_affine_addend(graph, *right, iv_phi_id, consts, 0);
}
if *right == phi_acc_id {
return extract_affine_addend(graph, *left, iv_phi_id, consts, 0);
}
if let Some((a, b)) =
peel_accumulator_addend(graph, *left, phi_acc_id, iv_phi_id, consts, depth + 1)
&& let Some((a2, b2)) = extract_affine_addend(graph, *right, iv_phi_id, consts, 0)
{
return Some((a + a2, b + b2));
}
if let Some((a, b)) =
peel_accumulator_addend(graph, *right, phi_acc_id, iv_phi_id, consts, depth + 1)
&& let Some((a2, b2)) = extract_affine_addend(graph, *left, iv_phi_id, consts, 0)
{
return Some((a + a2, b + b2));
}
None
}
ValueNode::Int32Subtract { left, right } => {
let (a, b) =
peel_accumulator_addend(graph, *left, phi_acc_id, iv_phi_id, consts, depth + 1)?;
let (a2, b2) = extract_affine_addend(graph, *right, iv_phi_id, consts, 0)?;
Some((a - a2, b - b2))
}
_ => None,
}
}
fn lower_constant_accumulator_adds(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
if loops.is_empty() {
return;
}
let mut consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::SmiConstant { value } | ValueNode::Int32Constant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
}
let mut rewrites: Vec<(u32, usize, NodeId)> = Vec::new();
for lp in &loops {
let header = &graph.blocks()[lp.header as usize];
let back_pred_pos = match header
.predecessors
.iter()
.position(|&p| lp.body.contains(&p) && p != lp.header)
{
Some(pos) => pos,
None => continue,
};
let entry_pos = if back_pred_pos == 0 { 1 } else { 0 };
let max_iters = estimate_max_iterations(graph, lp, &consts);
for (phi_id, node) in &header.nodes {
let ValueNode::Phi { inputs } = node else {
continue;
};
if inputs.len() != 2 {
continue;
}
let init_id = inputs[entry_pos];
let back_id = inputs[back_pred_pos];
let Some(&init_val) = consts.get(&init_id) else {
continue;
};
let back_node = find_node_in_blocks(graph, &back_id, &lp.body);
let Some((block_idx, node_idx, back_value)) = back_node else {
continue;
};
let addend_val = match &back_value {
ValueNode::GenericAdd { left, right, .. } if *left == *phi_id => {
consts.get(right).copied()
}
ValueNode::GenericAdd { left, right, .. } if *right == *phi_id => {
consts.get(left).copied()
}
_ => None,
};
let Some(k) = addend_val else {
continue;
};
let iters = max_iters.unwrap_or(100_000) as i64;
let total_min = (init_val as i64) + (k as i64) * iters;
let total_max = (init_val as i64) + (k as i64) * iters;
let (lo, hi) = if k >= 0 {
(init_val as i64, total_max)
} else {
(total_min, init_val as i64)
};
if lo < i32::MIN as i64 || hi > i32::MAX as i64 {
continue;
}
rewrites.push((block_idx, node_idx, back_id));
}
}
for (block_idx, node_idx, _back_id) in &rewrites {
if let Some(block) = graph.block_mut(*block_idx)
&& let Some((_, node)) = block.nodes.get_mut(*node_idx)
&& let ValueNode::GenericAdd { left, right, .. } = node
{
*node = ValueNode::Int32Add {
left: *left,
right: *right,
};
}
}
}
fn find_node_in_blocks(
graph: &MaglevGraph,
node_id: &NodeId,
block_indices: &HashSet<u32>,
) -> Option<(u32, usize, ValueNode)> {
for &bi in block_indices {
if let Some(block) = graph.block(bi) {
for (pos, (id, node)) in block.nodes.iter().enumerate() {
if *id == *node_id {
return Some((bi, pos, node.clone()));
}
}
}
}
None
}
fn eliminate_constant_accumulator_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
if loops.is_empty() {
return;
}
let mut consts: HashMap<NodeId, i32> = HashMap::new();
for block in graph.blocks() {
for (id, node) in &block.nodes {
match node {
ValueNode::SmiConstant { value } | ValueNode::Int32Constant { value } => {
consts.insert(*id, *value);
}
_ => {}
}
}
}
for lp in &loops {
try_eliminate_constant_accumulator(graph, lp, &consts);
}
}
fn try_eliminate_constant_accumulator(
graph: &mut MaglevGraph,
lp: &licm::NaturalLoop,
consts: &HashMap<NodeId, i32>,
) -> bool {
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
let (condition_id, body_block_idx, _exit_block_idx) = match &header.control {
Some(ControlNode::Branch {
condition,
if_true,
if_false,
}) => (*condition, *if_true, *if_false),
_ => return false,
};
if !lp.body.contains(&body_block_idx) {
return false;
}
if lp.body.len() != 2 || !lp.body.contains(&lp.header) {
return false;
}
let body = match graph.block(body_block_idx) {
Some(b) => b,
None => return false,
};
match &body.control {
Some(ControlNode::Jump { target }) if *target == lp.header => {}
_ => return false,
}
let (cmp_left, cmp_right) = {
let mut found = None;
for (nid, node) in &header.nodes {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, right }) => (left, right),
_ => return false,
}
};
let back_pred_pos = match header
.predecessors
.iter()
.position(|&p| p == body_block_idx)
{
Some(pos) => pos,
None => return false,
};
let entry_pos = match header.predecessors.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
};
let iv_phi_id = cmp_left;
let iv_phi_inputs = {
let h = graph.block(lp.header).unwrap();
let mut found = None;
for (nid, node) in &h.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node {
found = Some(inputs.clone());
}
break;
}
}
match found {
Some(inputs) if inputs.len() == 2 => inputs,
_ => return false,
}
};
let iv_init_id = iv_phi_inputs[entry_pos];
let iv_limit_id = cmp_right;
let iv_init = match consts.get(&iv_init_id) {
Some(&v) => v,
None => match find_i32_constant(graph, iv_init_id) {
Some(v) => v,
None => return false,
},
};
let iv_limit = match consts.get(&iv_limit_id) {
Some(&v) => v,
None => match find_i32_constant(graph, iv_limit_id) {
Some(v) => v,
None => return false,
},
};
let iv_back_id = iv_phi_inputs[back_pred_pos];
let iv_step = find_increment_step(graph, iv_back_id, iv_phi_id);
let iv_step_val = match iv_step {
Some(s) if s > 0 => s,
_ => return false,
};
let range = (iv_limit as i64) - (iv_init as i64);
let step = iv_step_val as i64;
if range <= 0 || range % step != 0 {
return false;
}
let trip_count = range / step;
let h = graph.block(lp.header).unwrap();
let header_phis: Vec<(NodeId, Vec<NodeId>)> = h
.nodes
.iter()
.filter_map(|(nid, node)| {
if let ValueNode::Phi { inputs } = node {
Some((*nid, inputs.clone()))
} else {
None
}
})
.collect();
let mut accumulators: Vec<(NodeId, i32, i128, i128, NodeId)> = Vec::new();
let mut loop_use_counts: HashMap<NodeId, usize> = HashMap::new();
for &bi in &lp.body {
if let Some(block) = graph.block(bi) {
for (_, node) in &block.nodes {
visit_value_node_inputs(node, &mut |id| {
*loop_use_counts.entry(id).or_insert(0) += 1;
});
}
}
}
for (phi_id, inputs) in &header_phis {
if *phi_id == iv_phi_id {
continue; }
if inputs.len() != 2 {
continue;
}
let init_id = inputs[entry_pos];
let back_id = inputs[back_pred_pos];
let init_val = match consts.get(&init_id) {
Some(&v) => v,
None => match find_i32_constant(graph, init_id) {
Some(v) => v,
None => continue,
},
};
let Some((aff_a, aff_b)) =
peel_accumulator_addend(graph, back_id, *phi_id, iv_phi_id, consts, 0)
else {
continue;
};
let in_loop_uses = loop_use_counts.get(phi_id).copied().unwrap_or(0);
if in_loop_uses > 1 {
continue;
}
let n = trip_count as i128;
let iv0 = iv_init as i128;
let s = iv_step_val as i128;
let result = (init_val as i128) + n * (aff_a * iv0 + aff_b) + aff_a * s * n * (n - 1) / 2;
if result < i32::MIN as i128 || result > i32::MAX as i128 {
continue;
}
accumulators.push((*phi_id, init_val, aff_a, aff_b, back_id));
}
if accumulators.is_empty() {
return false;
}
for (phi_id, init_val, aff_a, aff_b, _back_id) in &accumulators {
let n = trip_count as i128;
let iv0 = iv_init as i128;
let s = iv_step_val as i128;
let result =
(*init_val as i128) + n * (*aff_a * iv0 + *aff_b) + *aff_a * s * n * (n - 1) / 2;
let result_val = result as i32;
let result_node_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(result_node_id, ValueNode::SmiConstant { value: result_val });
}
let h = graph.block_mut(lp.header).unwrap();
for (nid, node) in &mut h.nodes {
if *nid == *phi_id {
if let ValueNode::Phi { inputs } = node {
inputs[entry_pos] = result_node_id;
inputs[back_pred_pos] = *phi_id;
}
break;
}
}
}
let final_iv = (iv_init as i128) + (iv_step_val as i128) * (trip_count as i128);
if (i32::MIN as i128..=i32::MAX as i128).contains(&final_iv) {
let final_iv_id = graph.alloc_node_id();
if let Some(pre) = graph.block_mut(lp.preheader) {
pre.push_with_id(
final_iv_id,
ValueNode::SmiConstant {
value: final_iv as i32,
},
);
}
replace_uses_outside_loop(graph, lp, iv_phi_id, final_iv_id);
}
true
}
fn replace_uses_outside_loop(
graph: &mut MaglevGraph,
lp: &licm::NaturalLoop,
from: NodeId,
to: NodeId,
) {
let subst = HashMap::from([(from, to)]);
for block in graph.blocks_mut() {
if lp.body.contains(&block.id) {
continue;
}
apply_subst_to_block(block, &subst);
}
}
fn estimate_max_iterations(
graph: &MaglevGraph,
lp: &licm::NaturalLoop,
consts: &HashMap<NodeId, i32>,
) -> Option<u64> {
let header = &graph.blocks()[lp.header as usize];
let condition_id = match &header.control {
Some(ControlNode::Branch { condition, .. }) => *condition,
_ => return None,
};
let cmp_node = header
.nodes
.iter()
.find(|(id, _)| *id == condition_id)
.map(|(_, n)| n)?;
let (left, right) = match cmp_node {
ValueNode::Int32LessThan { left, right } => (*left, *right),
_ => return None,
};
let limit = consts.get(&right).or_else(|| consts.get(&left))?;
Some(*limit as u64)
}
#[allow(dead_code)] fn eliminate_dead_counted_loops(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
try_eliminate_dead_loop(graph, lp);
}
}
#[allow(dead_code)] fn try_eliminate_dead_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
let exit_block_idx = {
let header = match graph.block(lp.header) {
Some(b) => b,
None => return false,
};
match &header.control {
Some(ControlNode::Branch {
if_true, if_false, ..
}) => {
if lp.body.contains(if_true) && !lp.body.contains(if_false) {
*if_false
} else if lp.body.contains(if_false) && !lp.body.contains(if_true) {
*if_true
} else {
return false;
}
}
_ => return false,
}
};
let mut loop_node_ids: HashSet<NodeId> = HashSet::new();
for &block_idx in &lp.body {
if let Some(block) = graph.block(block_idx) {
for (id, _) in &block.nodes {
loop_node_ids.insert(*id);
}
}
}
for &block_idx in &lp.body {
if let Some(block) = graph.block(block_idx) {
for (_, node) in &block.nodes {
if has_side_effects(node) {
return false;
}
}
}
}
for block in graph.blocks() {
if lp.body.contains(&block.id) {
continue;
}
for (_, node) in &block.nodes {
let mut refs_loop = false;
visit_value_node_inputs(node, &mut |id| {
if loop_node_ids.contains(&id) {
refs_loop = true;
}
});
if refs_loop {
return false;
}
}
if let Some(ctrl) = &block.control {
let mut live = HashSet::new();
collect_control_node_inputs(ctrl, &mut live);
if live.iter().any(|id| loop_node_ids.contains(id)) {
return false;
}
}
}
if let Some(exit_block) = graph.block(exit_block_idx) {
for (_, node) in &exit_block.nodes {
if matches!(node, ValueNode::Phi { .. }) {
return false;
}
}
}
if let Some(preheader) = graph.block_mut(lp.preheader) {
preheader.control = Some(ControlNode::Jump {
target: exit_block_idx,
});
}
if let Some(exit_block) = graph.block_mut(exit_block_idx) {
exit_block.predecessors.retain(|p| !lp.body.contains(p));
if !exit_block.predecessors.contains(&lp.preheader) {
exit_block.predecessors.push(lp.preheader);
}
}
for &block_idx in &lp.body {
if let Some(block) = graph.block_mut(block_idx) {
block.nodes.clear();
block.is_loop_header = false;
block.control = Some(ControlNode::Jump {
target: exit_block_idx,
});
}
}
true
}
#[allow(dead_code)]
fn strength_reduce_induction_variables(graph: &mut MaglevGraph) {
let loops = licm::detect_loops(graph);
for lp in &loops {
strength_reduce_iv_in_loop(graph, lp);
}
}
#[allow(dead_code)]
fn strength_reduce_iv_in_loop(graph: &mut MaglevGraph, lp: &licm::NaturalLoop) -> bool {
let header_idx = lp.header;
let (condition_id, body_block_idx) = {
let header = match graph.block(header_idx) {
Some(b) => b,
None => return false,
};
match &header.control {
Some(ControlNode::Branch {
condition, if_true, ..
}) => (*condition, *if_true),
_ => return false,
}
};
if !lp.body.contains(&body_block_idx) {
return false;
}
if lp.body.len() != 2 || !lp.body.contains(&header_idx) {
return false;
}
match graph.block(body_block_idx).and_then(|b| b.control.as_ref()) {
Some(ControlNode::Jump { target }) if *target == header_idx => {}
_ => return false,
}
let cmp_left = {
let header = graph.block(header_idx).unwrap();
let mut found = None;
for (nid, node) in &header.nodes {
if *nid == condition_id {
found = Some(node.clone());
break;
}
}
match found {
Some(ValueNode::Int32LessThan { left, .. }) => left,
_ => return false,
}
};
let back_edge_pred_pos = {
let h = graph.block(header_idx).unwrap();
match h.predecessors.iter().position(|&p| p == body_block_idx) {
Some(pos) => pos,
None => return false,
}
};
let preheader_pred_pos = {
let h = graph.block(header_idx).unwrap();
match h.predecessors.iter().position(|&p| p == lp.preheader) {
Some(pos) => pos,
None => return false,
}
};
let iv_phi_id = cmp_left;
let iv_phi_inputs = {
let h = graph.block(header_idx).unwrap();
let mut found = None;
for (nid, node) in &h.nodes {
if *nid == iv_phi_id {
if let ValueNode::Phi { inputs } = node {
found = Some(inputs.clone());
}
break;
}
}
match found {
Some(inputs) => inputs,
None => return false,
}
};
let init_id = iv_phi_inputs[preheader_pred_pos];
let init_val = match find_i32_constant(graph, init_id) {
Some(v) => v,
None => return false,
};
let back_edge_input = iv_phi_inputs[back_edge_pred_pos];
let step_val = match find_increment_step(graph, back_edge_input, iv_phi_id) {
Some(s) if s > 0 => s,
_ => return false,
};
let mut mul_targets: HashMap<i32, Vec<NodeId>> = HashMap::new();
{
let body = graph.block(body_block_idx).unwrap();
for (nid, node) in &body.nodes {
if let ValueNode::Int32Multiply { left, right } = node {
let (const_input, is_iv) = if *left == iv_phi_id {
(*right, true)
} else if *right == iv_phi_id {
(*left, true)
} else {
(NodeId(0), false)
};
if !is_iv {
continue;
}
if let Some(k) = find_i32_constant(graph, const_input)
&& k != 0
&& k != 1
{
mul_targets.entry(k).or_default().push(*nid);
}
}
}
}
if mul_targets.is_empty() {
return false;
}
let mut subst: HashMap<NodeId, NodeId> = HashMap::new();
for (k, mul_ids) in &mul_targets {
let derived_init = init_val.wrapping_mul(*k);
let derived_step = step_val.wrapping_mul(*k);
let init_const_id = graph.alloc_node_id();
let step_const_id = graph.alloc_node_id();
let derived_phi_id = graph.alloc_node_id();
let derived_add_id = graph.alloc_node_id();
let preheader = graph.block_mut(lp.preheader).unwrap();
preheader.push_with_id(
init_const_id,
ValueNode::Int32Constant {
value: derived_init,
},
);
preheader.push_with_id(
step_const_id,
ValueNode::Int32Constant {
value: derived_step,
},
);
let mut phi_inputs = vec![NodeId(0); iv_phi_inputs.len()];
phi_inputs[preheader_pred_pos] = init_const_id;
phi_inputs[back_edge_pred_pos] = derived_add_id;
{
let header = graph.block_mut(header_idx).unwrap();
let insert_pos = header
.nodes
.iter()
.position(|(_, n)| !matches!(n, ValueNode::Phi { .. }))
.unwrap_or(header.nodes.len());
header.nodes.insert(
insert_pos,
(derived_phi_id, ValueNode::Phi { inputs: phi_inputs }),
);
}
let body = graph.block_mut(body_block_idx).unwrap();
body.push_with_id(
derived_add_id,
ValueNode::Int32Add {
left: derived_phi_id,
right: step_const_id,
},
);
for mul_id in mul_ids {
subst.insert(*mul_id, derived_phi_id);
}
}
for block in graph.blocks_mut() {
apply_subst_to_block(block, &subst);
}
true
}
#[cfg(test)]
mod tests {
use super::*;
use crate::compiler::maglev::ir::{BasicBlock, ControlNode, MaglevGraph, ValueNode};
fn total_node_count(graph: &MaglevGraph) -> usize {
graph.blocks().iter().map(|b| b.nodes.len()).sum()
}
fn node_at(graph: &MaglevGraph, pos: usize) -> &ValueNode {
&graph.blocks()[0].nodes[pos].1
}
fn count_store_globals(graph: &MaglevGraph) -> usize {
graph
.blocks()
.iter()
.flat_map(|block| block.nodes.iter())
.filter(|(_, node)| matches!(node, ValueNode::StoreGlobal { .. }))
.count()
}
fn count_store_global_name(graph: &MaglevGraph, expected_name: u32) -> usize {
graph
.blocks()
.iter()
.flat_map(|block| block.nodes.iter())
.filter(|(_, node)| {
matches!(node, ValueNode::StoreGlobal { name, .. } if *name == expected_name)
})
.count()
}
fn graph_has_header_phi(graph: &MaglevGraph, header: u32) -> bool {
graph
.block(header)
.is_some_and(|block| matches!(block.nodes.first(), Some((_, ValueNode::Phi { .. }))))
}
#[test]
fn test_promote_loop_globals_unconditional_loop() {
let mut graph = MaglevGraph::new(0);
for id in 0..4 {
graph.add_block(BasicBlock::new(id));
}
let init = graph
.add_value_node(0, ValueNode::SmiConstant { value: 0 })
.unwrap();
graph
.add_value_node(
0,
ValueNode::StoreGlobal {
name: 7,
value: init,
feedback_slot: 0,
},
)
.unwrap();
graph
.block_mut(0)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
graph.block_mut(1).unwrap().add_predecessor(0);
graph.block_mut(1).unwrap().add_predecessor(2);
let cond = graph.add_value_node(1, ValueNode::TrueConstant).unwrap();
graph
.block_mut(1)
.unwrap()
.set_control(ControlNode::Branch {
condition: cond,
if_true: 2,
if_false: 3,
});
graph.block_mut(2).unwrap().add_predecessor(1);
let load = graph
.add_value_node(
2,
ValueNode::LoadGlobal {
name: 7,
feedback_slot: 0,
},
)
.unwrap();
let inc = graph
.add_value_node(2, ValueNode::Int32Increment { value: load })
.unwrap();
graph
.add_value_node(
2,
ValueNode::StoreGlobal {
name: 7,
value: inc,
feedback_slot: 0,
},
)
.unwrap();
graph
.block_mut(2)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
graph.block_mut(3).unwrap().add_predecessor(1);
let undef = graph
.add_value_node(3, ValueNode::UndefinedConstant)
.unwrap();
graph
.block_mut(3)
.unwrap()
.set_control(ControlNode::Return { value: undef });
assert_eq!(promote_loop_globals_counted(&mut graph), 1);
assert!(graph_has_header_phi(&graph, 1));
}
#[test]
fn test_promote_loop_globals_excludes_conditional_stores() {
let mut graph = MaglevGraph::new(0);
for id in 0..6 {
graph.add_block(BasicBlock::new(id));
}
let init = graph
.add_value_node(0, ValueNode::SmiConstant { value: 0 })
.unwrap();
graph
.add_value_node(
0,
ValueNode::StoreGlobal {
name: 8,
value: init,
feedback_slot: 0,
},
)
.unwrap();
graph
.block_mut(0)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
graph.block_mut(1).unwrap().add_predecessor(0);
graph.block_mut(1).unwrap().add_predecessor(4);
let header_cond = graph.add_value_node(1, ValueNode::TrueConstant).unwrap();
graph
.block_mut(1)
.unwrap()
.set_control(ControlNode::Branch {
condition: header_cond,
if_true: 2,
if_false: 5,
});
graph.block_mut(2).unwrap().add_predecessor(1);
let body_cond = graph.add_value_node(2, ValueNode::TrueConstant).unwrap();
graph
.block_mut(2)
.unwrap()
.set_control(ControlNode::Branch {
condition: body_cond,
if_true: 3,
if_false: 4,
});
graph.block_mut(3).unwrap().add_predecessor(2);
graph
.add_value_node(
3,
ValueNode::StoreGlobal {
name: 9,
value: init,
feedback_slot: 0,
},
)
.unwrap();
graph
.block_mut(3)
.unwrap()
.set_control(ControlNode::Jump { target: 4 });
graph.block_mut(4).unwrap().add_predecessor(2);
graph.block_mut(4).unwrap().add_predecessor(3);
graph
.add_value_node(
4,
ValueNode::StoreGlobal {
name: 8,
value: init,
feedback_slot: 0,
},
)
.unwrap();
graph
.block_mut(4)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
graph.block_mut(5).unwrap().add_predecessor(1);
let undef = graph
.add_value_node(5, ValueNode::UndefinedConstant)
.unwrap();
graph
.block_mut(5)
.unwrap()
.set_control(ControlNode::Return { value: undef });
let stores_before = count_store_globals(&graph);
assert_eq!(promote_loop_globals_counted(&mut graph), 1);
assert_eq!(count_store_globals(&graph), stores_before);
assert_eq!(count_store_global_name(&graph, 9), 1);
assert!(graph_has_header_phi(&graph, 1));
}
#[test]
fn test_fold_int32_add() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c3 = block.push_value(ValueNode::Int32Constant { value: 3 });
let c4 = block.push_value(ValueNode::Int32Constant { value: 4 });
let add = block.push_value(ValueNode::Int32Add {
left: c3,
right: c4,
});
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 7 });
}
#[test]
fn test_fold_int32_subtract() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c10 = block.push_value(ValueNode::Int32Constant { value: 10 });
let c3 = block.push_value(ValueNode::Int32Constant { value: 3 });
let sub = block.push_value(ValueNode::Int32Subtract {
left: c10,
right: c3,
});
block.set_control(ControlNode::Return { value: sub });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 7 });
}
#[test]
fn test_fold_int32_multiply() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c6 = block.push_value(ValueNode::Int32Constant { value: 6 });
let c7 = block.push_value(ValueNode::Int32Constant { value: 7 });
let mul = block.push_value(ValueNode::Int32Multiply {
left: c6,
right: c7,
});
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 42 });
}
#[test]
fn test_fold_int32_divide() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c12 = block.push_value(ValueNode::Int32Constant { value: 12 });
let c4 = block.push_value(ValueNode::Int32Constant { value: 4 });
let div = block.push_value(ValueNode::Int32Divide {
left: c12,
right: c4,
});
block.set_control(ControlNode::Return { value: div });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 3 });
}
#[test]
fn test_fold_int32_divide_by_zero_not_folded() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c5 = block.push_value(ValueNode::Int32Constant { value: 5 });
let c0 = block.push_value(ValueNode::Int32Constant { value: 0 });
let div = block.push_value(ValueNode::Int32Divide {
left: c5,
right: c0,
});
block.set_control(ControlNode::Return { value: div });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert!(matches!(node_at(&graph, 2), ValueNode::Int32Divide { .. }));
assert_eq!(total_node_count(&graph), before);
}
#[test]
fn test_fold_int32_modulus() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c10 = block.push_value(ValueNode::Int32Constant { value: 10 });
let c3 = block.push_value(ValueNode::Int32Constant { value: 3 });
let rem = block.push_value(ValueNode::Int32Modulus {
left: c10,
right: c3,
});
block.set_control(ControlNode::Return { value: rem });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 1 });
}
#[test]
fn test_fold_int32_negate() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c5 = block.push_value(ValueNode::Int32Constant { value: 5 });
let neg = block.push_value(ValueNode::Int32Negate { value: c5 });
block.set_control(ControlNode::Return { value: neg });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: -5 });
}
#[test]
fn test_fold_int32_increment() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c9 = block.push_value(ValueNode::Int32Constant { value: 9 });
let inc = block.push_value(ValueNode::Int32Increment { value: c9 });
block.set_control(ControlNode::Return { value: inc });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 10 });
}
#[test]
fn test_fold_int32_decrement() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c10 = block.push_value(ValueNode::Int32Constant { value: 10 });
let dec = block.push_value(ValueNode::Int32Decrement { value: c10 });
block.set_control(ControlNode::Return { value: dec });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 9 });
}
#[test]
fn test_fold_checked_smi_add() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let a = block.push_value(ValueNode::SmiConstant { value: 2 });
let b = block.push_value(ValueNode::SmiConstant { value: 3 });
let sum = block.push_value(ValueNode::CheckedSmiAdd { left: a, right: b });
block.set_control(ControlNode::Return { value: sum });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 5 });
}
#[test]
fn test_fold_checked_smi_increment() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c = block.push_value(ValueNode::SmiConstant { value: 41 });
let inc = block.push_value(ValueNode::CheckedSmiIncrement { value: c });
block.set_control(ControlNode::Return { value: inc });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 42 });
}
#[test]
fn test_fold_float64_add() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let x = block.push_value(ValueNode::Float64Constant { value: 1.5 });
let y = block.push_value(ValueNode::Float64Constant { value: 2.5 });
let add = block.push_value(ValueNode::Float64Add { left: x, right: y });
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
optimize(&mut graph);
if let ValueNode::Float64Constant { value } = node_at(&graph, 0) {
assert!((value - 4.0).abs() < f64::EPSILON);
} else {
panic!("expected Float64Constant after folding");
}
}
#[test]
fn test_fold_float64_multiply() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let x = block.push_value(ValueNode::Float64Constant { value: 3.0 });
let y = block.push_value(ValueNode::Float64Constant { value: 4.0 });
let mul = block.push_value(ValueNode::Float64Multiply { left: x, right: y });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
if let ValueNode::Float64Constant { value } = node_at(&graph, 0) {
assert!((value - 12.0).abs() < f64::EPSILON);
} else {
panic!("expected Float64Constant after folding");
}
}
#[test]
fn test_fold_float64_negate() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let x = block.push_value(ValueNode::Float64Constant { value: 2.5 });
let neg = block.push_value(ValueNode::Float64Negate { value: x });
block.set_control(ControlNode::Return { value: neg });
graph.add_block(block);
optimize(&mut graph);
if let ValueNode::Float64Constant { value } = node_at(&graph, 0) {
assert!((value - (-2.5)).abs() < f64::EPSILON);
} else {
panic!("expected Float64Constant after folding");
}
}
#[test]
fn test_no_fold_when_operand_is_parameter() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c = block.push_value(ValueNode::Int32Constant { value: 1 });
let add = block.push_value(ValueNode::Int32Add { left: p, right: c });
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
optimize(&mut graph);
assert!(matches!(node_at(&graph, 2), ValueNode::Int32Add { .. }));
}
#[test]
fn test_dce_removes_unused_pure_node() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
block.push_value(ValueNode::Int32Constant { value: 99 });
let ret_val = block.push_value(ValueNode::SmiConstant { value: 0 });
block.set_control(ControlNode::Return { value: ret_val });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert!(total_node_count(&graph) < before);
}
#[test]
fn test_dce_keeps_side_effect_node() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let obj = block.push_value(ValueNode::Parameter { index: 0 });
let val = block.push_value(ValueNode::Int32Constant { value: 1 });
block.push_value(ValueNode::StoreField {
object: obj,
offset: 8,
value: val,
});
let ret_val = block.push_value(ValueNode::UndefinedConstant);
block.set_control(ControlNode::Return { value: ret_val });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert_eq!(total_node_count(&graph), before);
}
#[test]
fn test_dce_keeps_check_maps_node() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let _check = block.push_value(ValueNode::CheckMaps {
receiver: p,
feedback_slot: 0,
});
let field = block.push_value(ValueNode::LoadField {
object: p,
offset: 8,
});
block.set_control(ControlNode::Return { value: field });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert_eq!(total_node_count(&graph), before);
}
#[test]
fn test_redundant_check_maps_removed() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let _check1 = block.push_value(ValueNode::CheckMaps {
receiver: p,
feedback_slot: 0,
});
let _check2 = block.push_value(ValueNode::CheckMaps {
receiver: p,
feedback_slot: 0,
});
let field = block.push_value(ValueNode::LoadField {
object: p,
offset: 8,
});
block.set_control(ControlNode::Return { value: field });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert!(total_node_count(&graph) < before);
}
#[test]
fn test_different_receivers_both_kept() {
let mut graph = MaglevGraph::new(2);
let mut block = BasicBlock::new(0);
let p0 = block.push_value(ValueNode::Parameter { index: 0 });
let p1 = block.push_value(ValueNode::Parameter { index: 1 });
block.push_value(ValueNode::CheckMaps {
receiver: p0,
feedback_slot: 0,
});
block.push_value(ValueNode::CheckMaps {
receiver: p1,
feedback_slot: 0,
});
let f0 = block.push_value(ValueNode::LoadField {
object: p0,
offset: 8,
});
let f1 = block.push_value(ValueNode::LoadField {
object: p1,
offset: 8,
});
let add = block.push_value(ValueNode::Int32Add {
left: f0,
right: f1,
});
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert_eq!(total_node_count(&graph), before);
}
#[test]
fn test_different_slots_both_kept() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
block.push_value(ValueNode::CheckMaps {
receiver: p,
feedback_slot: 0,
});
block.push_value(ValueNode::CheckMaps {
receiver: p,
feedback_slot: 1,
});
let f = block.push_value(ValueNode::LoadField {
object: p,
offset: 8,
});
block.set_control(ControlNode::Return { value: f });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert_eq!(total_node_count(&graph), before);
}
#[test]
fn test_combined_fold_and_dce_reduces_node_count() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c3 = block.push_value(ValueNode::Int32Constant { value: 3 });
let c4 = block.push_value(ValueNode::Int32Constant { value: 4 });
let add = block.push_value(ValueNode::Int32Add {
left: c3,
right: c4,
});
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
let before = total_node_count(&graph); optimize(&mut graph);
let after = total_node_count(&graph);
assert!(after < before, "expected fewer nodes after optimisation");
assert_eq!(after, 1);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 7 });
}
#[test]
fn test_chain_folding() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let c1 = block.push_value(ValueNode::Int32Constant { value: 1 });
let c2 = block.push_value(ValueNode::Int32Constant { value: 2 });
let c3 = block.push_value(ValueNode::Int32Constant { value: 3 });
let c4 = block.push_value(ValueNode::Int32Constant { value: 4 });
let add1 = block.push_value(ValueNode::Int32Add {
left: c1,
right: c2,
});
let add2 = block.push_value(ValueNode::Int32Add {
left: c3,
right: c4,
});
let mul = block.push_value(ValueNode::Int32Multiply {
left: add1,
right: add2,
});
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
assert_eq!(total_node_count(&graph), 1);
assert_eq!(node_at(&graph, 0), &ValueNode::Int32Constant { value: 21 });
}
#[test]
fn test_strength_reduce_multiply_by_2() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c2 = block.push_value(ValueNode::Int32Constant { value: 2 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c2 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
let has_shift = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32ShiftLeft { .. }));
assert!(
has_shift,
"expected Int32ShiftLeft after strength reduction"
);
}
#[test]
fn test_strength_reduce_multiply_by_4() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c4 = block.push_value(ValueNode::Int32Constant { value: 4 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c4 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
let shift_const = graph.blocks()[0].nodes.iter().find_map(|(_, n)| {
if let ValueNode::Int32ShiftLeft { right, .. } = n {
graph.blocks()[0].nodes.iter().find_map(|(id, cn)| {
if *id == *right {
if let ValueNode::Int32Constant { value } = cn {
Some(*value)
} else {
None
}
} else {
None
}
})
} else {
None
}
});
assert_eq!(shift_const, Some(2), "shift amount should be 2 for * 4");
}
#[test]
fn test_strength_reduce_not_applied_to_non_decomposable() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c6 = block.push_value(ValueNode::Int32Constant { value: 6 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c6 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
assert!(
graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Multiply { .. }))
);
}
#[test]
fn test_strength_reduce_multiply_by_1_simplified() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c1 = block.push_value(ValueNode::Int32Constant { value: 1 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c1 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
let has_mul = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Multiply { .. }));
assert!(
!has_mul,
"expected Int32Multiply(x, 1) to be identity-simplified away"
);
}
#[test]
fn test_eliminate_check_smi_on_smi_constant() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let smi = block.push_value(ValueNode::SmiConstant { value: 42 });
let _check = block.push_value(ValueNode::CheckSmi { receiver: smi });
block.set_control(ControlNode::Return { value: smi });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert!(total_node_count(&graph) < before);
}
#[test]
fn test_eliminate_duplicate_check_smi_same_block() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let _c1 = block.push_value(ValueNode::CheckSmi { receiver: p });
let _c2 = block.push_value(ValueNode::CheckSmi { receiver: p });
block.set_control(ControlNode::Return { value: p });
graph.add_block(block);
optimize(&mut graph);
let check_count = graph.blocks()[0]
.nodes
.iter()
.filter(|(_, n)| matches!(n, ValueNode::CheckSmi { .. }))
.count();
assert!(
check_count <= 1,
"expected at most 1 CheckSmi, got {check_count}"
);
}
#[test]
fn test_identity_add_zero_right() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c0 = block.push_value(ValueNode::Int32Constant { value: 0 });
let add = block.push_value(ValueNode::Int32Add { left: p, right: c0 });
block.set_control(ControlNode::Return { value: add });
graph.add_block(block);
optimize(&mut graph);
let has_add = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Add { .. }));
assert!(!has_add, "expected Int32Add to be simplified away");
}
#[test]
fn test_identity_multiply_by_one() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c1 = block.push_value(ValueNode::Int32Constant { value: 1 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c1 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
let has_mul = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Multiply { .. }));
assert!(!has_mul, "expected Int32Multiply(x, 1) to be simplified");
}
#[test]
fn test_identity_multiply_by_zero() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c0 = block.push_value(ValueNode::Int32Constant { value: 0 });
let mul = block.push_value(ValueNode::Int32Multiply { left: p, right: c0 });
block.set_control(ControlNode::Return { value: mul });
graph.add_block(block);
optimize(&mut graph);
let has_mul = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Multiply { .. }));
assert!(!has_mul, "expected Int32Multiply(x, 0) to be simplified");
}
#[test]
fn test_identity_subtract_zero() {
let mut graph = MaglevGraph::new(1);
let mut block = BasicBlock::new(0);
let p = block.push_value(ValueNode::Parameter { index: 0 });
let c0 = block.push_value(ValueNode::Int32Constant { value: 0 });
let sub = block.push_value(ValueNode::Int32Subtract { left: p, right: c0 });
block.set_control(ControlNode::Return { value: sub });
graph.add_block(block);
optimize(&mut graph);
let has_sub = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::Int32Subtract { .. }));
assert!(!has_sub, "expected Int32Subtract(x, 0) to be simplified");
}
#[test]
fn test_cse_duplicate_add_eliminated() {
let mut graph = MaglevGraph::new(2);
let mut block = BasicBlock::new(0);
let p0 = block.push_value(ValueNode::Parameter { index: 0 });
let p1 = block.push_value(ValueNode::Parameter { index: 1 });
let add1 = block.push_value(ValueNode::Int32Add {
left: p0,
right: p1,
});
let add2 = block.push_value(ValueNode::Int32Add {
left: p0,
right: p1,
});
let sum = block.push_value(ValueNode::Int32Add {
left: add1,
right: add2,
});
block.set_control(ControlNode::Return { value: sum });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert!(
total_node_count(&graph) < before,
"expected CSE to reduce node count"
);
}
#[test]
fn test_cse_different_ops_not_eliminated() {
let mut graph = MaglevGraph::new(2);
let mut block = BasicBlock::new(0);
let p0 = block.push_value(ValueNode::Parameter { index: 0 });
let p1 = block.push_value(ValueNode::Parameter { index: 1 });
let add = block.push_value(ValueNode::Int32Add {
left: p0,
right: p1,
});
let sub = block.push_value(ValueNode::Int32Subtract {
left: p0,
right: p1,
});
let result = block.push_value(ValueNode::Int32Add {
left: add,
right: sub,
});
block.set_control(ControlNode::Return { value: result });
graph.add_block(block);
let before = total_node_count(&graph);
optimize(&mut graph);
assert_eq!(
total_node_count(&graph),
before,
"different ops should not be CSE'd"
);
}
#[test]
fn test_eliminate_check_smi_on_checked_smi_add_result() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let a = block.push_value(ValueNode::SmiConstant { value: 1 });
let b = block.push_value(ValueNode::SmiConstant { value: 2 });
let sum = block.push_value(ValueNode::CheckedSmiAdd { left: a, right: b });
let _check = block.push_value(ValueNode::CheckSmi { receiver: sum });
block.set_control(ControlNode::Return { value: sum });
graph.add_block(block);
optimize(&mut graph);
let check_count = graph.blocks()[0]
.nodes
.iter()
.filter(|(_, n)| matches!(n, ValueNode::CheckSmi { .. }))
.count();
assert_eq!(
check_count, 0,
"CheckSmi on CheckedSmiAdd output should be eliminated"
);
}
#[test]
fn test_trivial_phi_self_referencing_eliminated() {
let mut graph = MaglevGraph::new(0);
let mut b0 = BasicBlock::new(0);
let root = graph.alloc_node_id(); b0.push_with_id(root, ValueNode::CreateEmptyObjectLiteral);
b0.set_control(ControlNode::Jump { target: 1 });
graph.add_block(b0);
let mut b1 = BasicBlock::new(1);
b1.predecessors = vec![0, 1]; b1.is_loop_header = true;
let phi_id = graph.alloc_node_id(); b1.push_with_id(
phi_id,
ValueNode::Phi {
inputs: vec![root, phi_id],
},
);
let load = graph.alloc_node_id(); b1.push_with_id(
load,
ValueNode::LoadNamedGeneric {
object: phi_id,
name: 0,
feedback_slot: 0,
},
);
b1.set_control(ControlNode::Return { value: load });
graph.add_block(b1);
optimize(&mut graph);
let load_node = graph.blocks()[1]
.nodes
.iter()
.find(|(_, n)| matches!(n, ValueNode::LoadNamedGeneric { .. }));
if let Some((_, ValueNode::LoadNamedGeneric { object, .. })) = load_node {
assert_eq!(
*object, root,
"LoadNamedGeneric should reference preheader root after Phi elimination"
);
} else {
let load_in_b0 = graph.blocks()[0]
.nodes
.iter()
.any(|(_, n)| matches!(n, ValueNode::LoadNamedGeneric { .. }));
assert!(
load_in_b0,
"LoadNamedGeneric should be hoisted to preheader by LICM"
);
}
}
#[test]
fn test_trivial_phi_non_trivial_preserved() {
let mut graph = MaglevGraph::new(0);
let mut b0 = BasicBlock::new(0);
let zero = graph.alloc_node_id();
b0.push_with_id(zero, ValueNode::SmiConstant { value: 0 });
b0.set_control(ControlNode::Jump { target: 1 });
graph.add_block(b0);
let mut b1 = BasicBlock::new(1);
b1.predecessors = vec![0, 1];
b1.is_loop_header = true;
let phi_id = graph.alloc_node_id();
let inc_id = graph.alloc_node_id();
b1.push_with_id(
phi_id,
ValueNode::Phi {
inputs: vec![zero, inc_id],
},
);
b1.push_with_id(
inc_id,
ValueNode::GenericIncrement {
value: phi_id,
feedback_slot: 0,
},
);
b1.set_control(ControlNode::Return { value: phi_id });
graph.add_block(b1);
optimize(&mut graph);
let phi_exists = graph
.blocks()
.iter()
.flat_map(|b| b.nodes.iter())
.any(|(_, n)| matches!(n, ValueNode::Phi { .. }));
assert!(phi_exists, "Non-trivial Phi should be preserved");
}
#[test]
fn test_store_to_load_forwarding_basic() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let obj = block.push_value(ValueNode::Parameter { index: 0 });
let val = block.push_value(ValueNode::SmiConstant { value: 42 });
let _store = block.push_value(ValueNode::StoreNamedGeneric {
object: obj,
name: 5,
value: val,
feedback_slot: 0,
});
let load = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 5,
feedback_slot: 1,
});
block.set_control(ControlNode::Return { value: load });
graph.add_block(block);
eliminate_store_to_load(&mut graph);
match &graph.blocks()[0].control {
Some(ControlNode::Return { value }) => {
assert_eq!(*value, val, "Load should be forwarded to stored value");
}
other => panic!("Expected Return, got {:?}", other),
}
}
#[test]
fn test_store_to_load_forwarding_fused_create() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let val_x = block.push_value(ValueNode::SmiConstant { value: 10 });
let val_y = block.push_value(ValueNode::SmiConstant { value: 20 });
let obj = block.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: 0,
flags: 0,
names: vec![1, 2],
values: vec![val_x, val_y],
});
let load_x = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 1,
feedback_slot: 1,
});
let load_y = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 2,
feedback_slot: 2,
});
let sum = block.push_value(ValueNode::Int32Add {
left: load_x,
right: load_y,
});
block.set_control(ControlNode::Return { value: sum });
graph.add_block(block);
eliminate_store_to_load(&mut graph);
let add_node = graph.blocks()[0]
.nodes
.iter()
.find(|(_, n)| matches!(n, ValueNode::Int32Add { .. }));
match add_node {
Some((_, ValueNode::Int32Add { left, right })) => {
assert_eq!(*left, val_x, "load_x should be forwarded to val_x");
assert_eq!(*right, val_y, "load_y should be forwarded to val_y");
}
other => panic!("Expected Int32Add, got {:?}", other),
}
}
#[test]
fn test_store_to_load_invalidated_by_call() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let obj = block.push_value(ValueNode::Parameter { index: 0 });
let val = block.push_value(ValueNode::SmiConstant { value: 42 });
let _store = block.push_value(ValueNode::StoreNamedGeneric {
object: obj,
name: 5,
value: val,
feedback_slot: 0,
});
let _call = block.push_value(ValueNode::Call {
callee: obj,
args: vec![],
receiver: obj,
feedback_slot: 0,
});
let load = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 5,
feedback_slot: 1,
});
block.set_control(ControlNode::Return { value: load });
graph.add_block(block);
eliminate_store_to_load(&mut graph);
match &graph.blocks()[0].control {
Some(ControlNode::Return { value }) => {
assert_eq!(*value, load, "Load should NOT be forwarded past a call");
}
other => panic!("Expected Return, got {:?}", other),
}
}
#[test]
fn test_dead_allocation_elimination_after_forwarding() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let val_x = block.push_value(ValueNode::SmiConstant { value: 10 });
let val_y = block.push_value(ValueNode::SmiConstant { value: 20 });
let obj = block.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: 0,
flags: 0,
names: vec![1, 2],
values: vec![val_x, val_y],
});
let load_x = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 1,
feedback_slot: 1,
});
let load_y = block.push_value(ValueNode::LoadNamedGeneric {
object: obj,
name: 2,
feedback_slot: 2,
});
let sum = block.push_value(ValueNode::Int32Add {
left: load_x,
right: load_y,
});
block.set_control(ControlNode::Return { value: sum });
graph.add_block(block);
eliminate_store_to_load(&mut graph);
eliminate_dead_allocations(&mut graph);
let obj_node = graph.blocks()[0].nodes.iter().find(|(id, _)| *id == obj);
match obj_node {
Some((_, ValueNode::UndefinedConstant)) => {} other => panic!(
"Expected dead allocation to be replaced with UndefinedConstant, got {:?}",
other
),
}
}
#[test]
fn test_live_allocation_preserved() {
let mut graph = MaglevGraph::new(0);
let mut block = BasicBlock::new(0);
let val = block.push_value(ValueNode::SmiConstant { value: 42 });
let obj = block.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: 0,
flags: 0,
names: vec![1],
values: vec![val],
});
block.set_control(ControlNode::Return { value: obj });
graph.add_block(block);
eliminate_dead_allocations(&mut graph);
let obj_node = graph.blocks()[0].nodes.iter().find(|(id, _)| *id == obj);
assert!(
matches!(
obj_node,
Some((_, ValueNode::CreateObjectLiteralWithProperties { .. }))
),
"Live allocation should be preserved"
);
}
#[test]
fn test_store_to_load_cross_block_forwarding() {
let mut graph = MaglevGraph::new(0);
let mut b0 = BasicBlock::new(0);
let obj = graph.alloc_node_id();
b0.push_with_id(obj, ValueNode::Parameter { index: 0 });
let val = graph.alloc_node_id();
b0.push_with_id(val, ValueNode::SmiConstant { value: 42 });
let store = graph.alloc_node_id();
b0.push_with_id(
store,
ValueNode::StoreNamedGeneric {
object: obj,
name: 5,
value: val,
feedback_slot: 0,
},
);
b0.set_control(ControlNode::Jump { target: 1 });
graph.add_block(b0);
let mut b1 = BasicBlock::new(1);
b1.predecessors = vec![0];
let load = graph.alloc_node_id();
b1.push_with_id(
load,
ValueNode::LoadNamedGeneric {
object: obj,
name: 5,
feedback_slot: 1,
},
);
b1.set_control(ControlNode::Return { value: load });
graph.add_block(b1);
eliminate_store_to_load(&mut graph);
match &graph.blocks()[1].control {
Some(ControlNode::Return { value }) => {
assert_eq!(
*value, val,
"Cross-block load should be forwarded to stored value"
);
}
other => panic!("Expected Return, got {:?}", other),
}
}
#[test]
fn test_store_to_load_cross_block_merge_conservative() {
let mut graph = MaglevGraph::new(0);
let mut b0 = BasicBlock::new(0);
let obj = graph.alloc_node_id();
b0.push_with_id(obj, ValueNode::Parameter { index: 0 });
let val_a = graph.alloc_node_id();
b0.push_with_id(val_a, ValueNode::SmiConstant { value: 1 });
let store_a = graph.alloc_node_id();
b0.push_with_id(
store_a,
ValueNode::StoreNamedGeneric {
object: obj,
name: 5,
value: val_a,
feedback_slot: 0,
},
);
b0.set_control(ControlNode::Jump { target: 2 });
graph.add_block(b0);
let mut b1 = BasicBlock::new(1);
let val_b = graph.alloc_node_id();
b1.push_with_id(val_b, ValueNode::SmiConstant { value: 2 });
let store_b = graph.alloc_node_id();
b1.push_with_id(
store_b,
ValueNode::StoreNamedGeneric {
object: obj,
name: 5,
value: val_b,
feedback_slot: 0,
},
);
b1.set_control(ControlNode::Jump { target: 2 });
graph.add_block(b1);
let mut b2 = BasicBlock::new(2);
b2.predecessors = vec![0, 1];
let load = graph.alloc_node_id();
b2.push_with_id(
load,
ValueNode::LoadNamedGeneric {
object: obj,
name: 5,
feedback_slot: 1,
},
);
b2.set_control(ControlNode::Return { value: load });
graph.add_block(b2);
eliminate_store_to_load(&mut graph);
match &graph.blocks()[2].control {
Some(ControlNode::Return { value }) => {
assert_eq!(*value, load, "Load at merge point should NOT be forwarded");
}
other => panic!("Expected Return, got {:?}", other),
}
}
#[test]
fn test_loop_unroll_even_trip_count() {
let mut graph = MaglevGraph::new(0);
graph.add_block(BasicBlock::new(0));
let init_i = graph
.add_value_node(0, ValueNode::Int32Constant { value: 0 })
.unwrap();
let init_n = graph
.add_value_node(0, ValueNode::Int32Constant { value: 0 })
.unwrap();
let limit = graph
.add_value_node(0, ValueNode::Int32Constant { value: 10 })
.unwrap();
graph
.block_mut(0)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
let mut b1 = BasicBlock::new(1);
b1.is_loop_header = true;
b1.predecessors = vec![0, 2];
graph.add_block(b1);
let phi_i = graph
.add_value_node(
1,
ValueNode::Phi {
inputs: vec![init_i, NodeId(999)],
},
)
.unwrap();
let phi_n = graph
.add_value_node(
1,
ValueNode::Phi {
inputs: vec![init_n, NodeId(999)],
},
)
.unwrap();
let cmp = graph
.add_value_node(
1,
ValueNode::Int32LessThan {
left: phi_i,
right: limit,
},
)
.unwrap();
graph
.block_mut(1)
.unwrap()
.set_control(ControlNode::Branch {
condition: cmp,
if_true: 2,
if_false: 3,
});
let mut b2 = BasicBlock::new(2);
b2.predecessors = vec![1];
graph.add_block(b2);
let new_n = graph
.add_value_node(
2,
ValueNode::Int32Add {
left: phi_n,
right: phi_i,
},
)
.unwrap();
let new_i = graph
.add_value_node(2, ValueNode::Int32Increment { value: phi_i })
.unwrap();
graph
.block_mut(2)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
let mut b3 = BasicBlock::new(3);
b3.predecessors = vec![1];
graph.add_block(b3);
graph
.block_mut(3)
.unwrap()
.set_control(ControlNode::Return { value: phi_n });
if let ValueNode::Phi { inputs } = &mut graph.block_mut(1).unwrap().nodes[0].1 {
inputs[1] = new_i;
}
if let ValueNode::Phi { inputs } = &mut graph.block_mut(1).unwrap().nodes[1].1 {
inputs[1] = new_n;
}
let body_nodes_before = graph.block(2).unwrap().nodes.len();
unroll_simple_loops(&mut graph);
let body_nodes_after = graph.block(2).unwrap().nodes.len();
assert_eq!(body_nodes_after, body_nodes_before * 2);
if let ValueNode::Phi { inputs } = &graph.block(1).unwrap().nodes[0].1 {
assert_ne!(inputs[1], new_i);
}
if let ValueNode::Phi { inputs } = &graph.block(1).unwrap().nodes[1].1 {
assert_ne!(inputs[1], new_n);
}
}
#[test]
fn test_loop_unroll_skips_odd_trip() {
let mut graph = MaglevGraph::new(0);
graph.add_block(BasicBlock::new(0));
let init_i = graph
.add_value_node(0, ValueNode::Int32Constant { value: 0 })
.unwrap();
let init_n = graph
.add_value_node(0, ValueNode::Int32Constant { value: 0 })
.unwrap();
let limit = graph
.add_value_node(0, ValueNode::Int32Constant { value: 7 })
.unwrap();
graph
.block_mut(0)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
let mut b1 = BasicBlock::new(1);
b1.is_loop_header = true;
b1.predecessors = vec![0, 2];
graph.add_block(b1);
let phi_i = graph
.add_value_node(
1,
ValueNode::Phi {
inputs: vec![init_i, NodeId(999)],
},
)
.unwrap();
let phi_n = graph
.add_value_node(
1,
ValueNode::Phi {
inputs: vec![init_n, NodeId(999)],
},
)
.unwrap();
let cmp = graph
.add_value_node(
1,
ValueNode::Int32LessThan {
left: phi_i,
right: limit,
},
)
.unwrap();
graph
.block_mut(1)
.unwrap()
.set_control(ControlNode::Branch {
condition: cmp,
if_true: 2,
if_false: 3,
});
let mut b2 = BasicBlock::new(2);
b2.predecessors = vec![1];
graph.add_block(b2);
let new_n = graph
.add_value_node(
2,
ValueNode::Int32Add {
left: phi_n,
right: phi_i,
},
)
.unwrap();
let new_i = graph
.add_value_node(2, ValueNode::Int32Increment { value: phi_i })
.unwrap();
graph
.block_mut(2)
.unwrap()
.set_control(ControlNode::Jump { target: 1 });
let mut b3 = BasicBlock::new(3);
b3.predecessors = vec![1];
graph.add_block(b3);
graph
.block_mut(3)
.unwrap()
.set_control(ControlNode::Return { value: phi_n });
if let ValueNode::Phi { inputs } = &mut graph.block_mut(1).unwrap().nodes[0].1 {
inputs[1] = new_i;
}
if let ValueNode::Phi { inputs } = &mut graph.block_mut(1).unwrap().nodes[1].1 {
inputs[1] = new_n;
}
let body_before = graph.block(2).unwrap().nodes.len();
unroll_simple_loops(&mut graph);
assert_eq!(graph.block(2).unwrap().nodes.len(), body_before);
}
#[test]
fn test_forward_invariant_object_properties_via_global() {
let mut graph = MaglevGraph::new(0);
let mut entry = BasicBlock::new(0);
let val_a = entry.push_value(ValueNode::SmiConstant { value: 42 });
let _create = entry.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: 0,
flags: 0,
names: vec![5], values: vec![val_a],
});
entry.push_value(ValueNode::StoreGlobal {
name: 10, value: _create,
feedback_slot: 1,
});
entry.set_control(ControlNode::Jump { target: 1 });
graph.add_block(entry);
let mut body = BasicBlock::new(1);
let obj_load = body.push_value(ValueNode::LoadGlobal {
name: 10, feedback_slot: 2,
});
let prop_load = body.push_value(ValueNode::LoadNamedGeneric {
object: obj_load,
name: 5, feedback_slot: 3,
});
body.set_control(ControlNode::Return { value: prop_load });
graph.add_block(body);
fuse_object_literal_stores(&mut graph);
forward_invariant_object_properties(&mut graph);
let block1 = &graph.blocks()[1];
let ret = block1.control.as_ref().unwrap();
if let ControlNode::Return { value } = ret {
assert_eq!(
*value, val_a,
"Expected LoadNamedGeneric to be forwarded to SmiConstant(42), got {:?}",
value
);
} else {
panic!("Expected Return control node");
}
}
#[test]
fn test_forward_nested_object_properties() {
let mut graph = MaglevGraph::new(0);
let mut entry = BasicBlock::new(0);
let val_b = entry.push_value(ValueNode::SmiConstant { value: 99 });
let inner = entry.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: u32::MAX,
flags: 0,
names: vec![7], values: vec![val_b],
});
let outer = entry.push_value(ValueNode::CreateObjectLiteralWithProperties {
feedback_slot: u32::MAX,
flags: 0,
names: vec![5], values: vec![inner],
});
entry.push_value(ValueNode::StoreGlobal {
name: 10,
value: outer,
feedback_slot: 1,
});
entry.set_control(ControlNode::Jump { target: 1 });
graph.add_block(entry);
let mut body = BasicBlock::new(1);
let root_load = body.push_value(ValueNode::LoadGlobal {
name: 10,
feedback_slot: 2,
});
let load_a = body.push_value(ValueNode::LoadNamedGeneric {
object: root_load,
name: 5, feedback_slot: 3,
});
let load_b = body.push_value(ValueNode::LoadNamedGeneric {
object: load_a,
name: 7, feedback_slot: 4,
});
body.set_control(ControlNode::Return { value: load_b });
graph.add_block(body);
fuse_object_literal_stores(&mut graph);
forward_invariant_object_properties(&mut graph);
let block1 = &graph.blocks()[1];
let ret = block1.control.as_ref().unwrap();
if let ControlNode::Return { value } = ret {
assert_eq!(
*value, val_b,
"Expected nested LoadNamedGeneric to resolve to SmiConstant(99), got {:?}",
value
);
} else {
panic!("Expected Return control node");
}
}
}