v8 KnownNodesAspects 介绍
KnownNodeAspects 是 Maglev 编译器的编译期数据流分析框架,用于跟踪和传播程序中已知的事实(aspects),以便进行激进的优化。
Map
v8 中用 Map 表示对象的 Hidden Class(隐藏类),类似我们的 hclass,对于类型系统而言,比较重要的是 is_unstable 这个 bit 位。KnownNodeAspects 中维护了一个 key -> object -> value 的映射关系优化 load 属性的逻辑,这些优化依赖于一个 stable 的 map。map 可以从 stable 转为 unstable,但是不能从 unstable 转为 stable。发生 transition,normlize 等操作会将 stable 的 map 转为 unstable。
这部分应该能复用现有 hclass 的 stable 逻辑,扩展也比较容易。
NodeType & ValueRepresentation & Feedback
每个对象都属于一个 LEAF_NODE_TYPE,同时还有组合类型 COMBINDED_NODE_TYPE。
NodeType 是语义类型,绑定到具体的 JS 对象上,比如 String JSArray JSFcuntion
ValueRepresentation 是数据的底层表示,比如 Int32 Tagged
enum class ValueRepresentation : uint8_t {
kTagged,
kInt32,
kUint32,
kFloat64,
kHoleyFloat64,
kIntPtr,
kNone,
};
Feedback 是运行时的反馈信息
三者共同作用在 graph-builder 时做一系列优化。
LoadedPropertyMap
// Valid across side-effecting calls, as long as we install a dependency.
LoadedPropertyMap loaded_constant_properties_;
// Flushed after side-effecting calls.
LoadedPropertyMap loaded_properties_;
loaded_constant_properties_ 依赖稳定的 map,即使有副作用操作也会保留。
loaded_properties_ 在副作用操作后会被清空。
KnownNodeAspects
KnownNodeAspects 的结构:
┌───────────────────────────────────────────────────────
│ 1. NodeInfos (node_infos_)
│ 类型推断 + Map 推断 + 表示形式转换
├───────────────────────────────────────────────────────
│ 2. Property Load Elimination
│ - loaded_constant_properties_ (跨副作用)
│ - loaded_properties_ (同基本块内)
├───────────────────────────────────────────────────────
│ 3. Context Slot Caching
│ - loaded_context_constants_ (不可变上下文)
│ - loaded_context_slots_ (可变上下文)
├───────────────────────────────────────────────────────
│ 4. CSE (Common Subexpression Elimination)
│ available_expressions_ + effect_epoch_
├───────────────────────────────────────────────────────
│ 5. Virtual Objects (Escape Analysis)
│ virtual_objects_ (对象标量化)
├───────────────────────────────────────────────────────
│ 6. Map Stability Tracking
│ any_map_for_any_node_is_unstable_
├───────────────────────────────────────────────────────
│ 7. Context Aliasing Tracking
│ may_have_aliasing_contexts_
├───────────────────────────────────────────────────────
│ 8. Effect Epoch Tracking
│ effect_epoch_ (副作用追踪)
└───────────────────────────────────────────────────────
1. 基于 NodeInfos 优化
1.1 NodeType
记录 Node 类型,优化一些 Check 或者 生成 Deopt 节点。
以 VisitToNumber 为例,ValueRepresentation 是更底层的机器表示,如果已经是 Number 类型了,直接返回。如果是 Tagged 类型,需要继续处理,这个时候不知道具体的类型。从 feedback 中拿到 hint 信息,然后验证这个 hint 信息。
验证过程中用到了 NodeType 信息优化 Check 节点生成,如果 NodeType 已经匹配了,就直接返回,如果确定不匹配了直接 Deopt,否则再生成 Check 节点。 基于 Check 点的保证得到了这个 Node 的类型特化信息,保存到 KnownNodeAspects 中。
ReduceResult MaglevGraphBuilder::BuildToNumberOrToNumeric(
Object::Conversion mode) {
ValueNode* value = GetAccumulator();
switch (value->value_representation()) {
case ValueRepresentation::kInt32:
case ValueRepresentation::kUint32:
case ValueRepresentation::kFloat64:
case ValueRepresentation::kIntPtr:
return ReduceResult::Done();
case ValueRepresentation::kHoleyFloat64: {
return SetAccumulator(AddNewNode<HoleyFloat64ToMaybeNanFloat64>({value}));
}
case ValueRepresentation::kTagged:
// We'll insert the required checks depending on the feedback.
break;
case ValueRepresentation::kNone:
UNREACHABLE();
}
FeedbackSlot slot = GetSlotOperand(0);
switch (broker()->GetFeedbackForBinaryOperation(
compiler::FeedbackSource(feedback(), slot))) {
case BinaryOperationHint::kSignedSmall:
RETURN_IF_ABORT(BuildCheckSmi(value));
break;
case BinaryOperationHint::kSignedSmallInputs:
case BinaryOperationHint::kAdditiveSafeInteger:
UNREACHABLE();
case BinaryOperationHint::kNumber:
case BinaryOperationHint::kBigInt:
case BinaryOperationHint::kBigInt64:
if (mode == Object::Conversion::kToNumber &&
EnsureType(value, NodeType::kNumber)) {
return ReduceResult::Done();
}
RETURN_IF_ABORT(AddNewNode<CheckNumber>({value}, mode));
break;
case BinaryOperationHint::kNone:
// TODO(leszeks): Faster ToNumber for kNumberOrOddball
case BinaryOperationHint::kNumberOrOddball:
case BinaryOperationHint::kString:
case BinaryOperationHint::kStringOrStringWrapper:
case BinaryOperationHint::kAny:
if (CheckType(value, NodeType::kNumber)) return ReduceResult::Done();
return SetAccumulator(AddNewNode<ToNumberOrNumeric>({value}, mode));
}
return ReduceResult::Done();
}
NodeType 本质上是基于 Check 点类型转换等操作的保证对 Node 类型化,后面消除再次对于这个 Node 的类型检查。是一个独立的模块,加到方舟中感觉比较简单,可以先实现一套基础的 StaticType,再慢慢补充维护特化类型,顶多一开始消除的 Check 点不那么多。
1.2 Alternative Type
消除类型转换,对于下面的例子,如果 x 是 taggedvalue,在第一次转换的时候 生成了一个 int32 的 Node,Alternative Type 中记录了 (int32, Node) 的映射关系,第二次处理 x * 2 的时候用映射里的信息直接拿到 int32 类型的 Node。
function compute(x) {
let a = x | 0; // 需要Int32
let b = x * 2; // 需要Int32
let c = x + 0.5; // 需要Float64
let d = x ? 1 : 0; // 需要Boolean判断
}
具体做法:
以 VisitToBoolean 为例,首先根据 ValueRepresentation 尝试转换。如果是 Tagged 值尝试获取 NodeInfo,如果 NodeInfo 中保存了其转换为 Int 或者 Float 后的结果,可以靠这个结果快速转化为 Bool 值。否则走到通用转换逻辑。
template <bool flip>
ValueNode* MaglevGraphBuilder::BuildToBoolean(ValueNode* value) {
if (IsConstantNode(value->opcode())) {
return GetBooleanConstant(FromConstantToBool(local_isolate(), value) ^
flip);
}
switch (value->value_representation()) {
case ValueRepresentation::kFloat64:
case ValueRepresentation::kHoleyFloat64:
// The ToBoolean of both the_hole and NaN is false, so we can use the
// same operation for HoleyFloat64 and Float64.
return AddNewNodeNoInputConversion<Float64ToBoolean>({value}, flip);
case ValueRepresentation::kUint32:
// Uint32 has the same logic as Int32 when converting ToBoolean, namely
// comparison against zero, so we can cast it and ignore the signedness.
value = AddNewNodeNoInputConversion<TruncateUint32ToInt32>({value});
[[fallthrough]];
case ValueRepresentation::kInt32:
return AddNewNodeNoInputConversion<Int32ToBoolean>({value}, flip);
case ValueRepresentation::kIntPtr:
return AddNewNodeNoInputConversion<IntPtrToBoolean>({value}, flip);
case ValueRepresentation::kTagged:
break;
case ValueRepresentation::kNone:
UNREACHABLE();
}
NodeInfo* node_info = known_node_aspects().TryGetInfoFor(value);
if (node_info) {
if (ValueNode* as_int32 = node_info->alternative().int32()) {
return AddNewNodeNoInputConversion<Int32ToBoolean>({as_int32}, flip);
}
if (ValueNode* as_float64 = node_info->alternative().float64()) {
return AddNewNodeNoInputConversion<Float64ToBoolean>({as_float64}, flip);
}
}
NodeType value_type;
if (CheckType(value, NodeType::kJSReceiver, &value_type)) {
ValueNode* result = BuildTestUndetectable(value);
// TODO(victorgomes): Check if it is worth to create
// TestUndetectableLogicalNot or to remove ToBooleanLogicalNot, since we
// already optimize LogicalNots by swapping the branches.
if constexpr (!flip) {
result = BuildLogicalNot(result);
}
return result;
}
ValueNode* falsy_value = nullptr;
if (CheckType(value, NodeType::kString)) {
falsy_value = GetRootConstant(RootIndex::kempty_string);
} else if (CheckType(value, NodeType::kSmi)) {
falsy_value = GetSmiConstant(0);
}
if (falsy_value != nullptr) {
return AddNewNodeNoAbort<
std::conditional_t<flip, TaggedEqual, TaggedNotEqual>>(
{value, falsy_value});
}
if (CheckType(value, NodeType::kBoolean)) {
if constexpr (flip) {
value = BuildLogicalNot(value);
}
return value;
}
return AddNewNodeNoAbort<
std::conditional_t<flip, ToBooleanLogicalNot, ToBoolean>>(
{value}, GetCheckType(value_type));
}
Questions?
1. 为什么有了 feedback 后还要有 NodeType
feedback 来自于解释器收集的信息,不保证正确。NodeType 是编译时推导的类型,绝对正确。
ValueNode* x = GetParameter(0);
// 1. 从Feedback获取提示
BinaryOperationHint hint = GetFeedback(); // kSignedSmall
// 2. 但不能直接信任!需要生成检查
if (hint == kSignedSmall) {
RETURN_IF_ABORT(BuildCheckSmi(x)); // 生成检查
// 检查通过后,NodeType才能确定
EnsureType(x, NodeType::kSmi); // ← 现在确定是Smi了
}
feedback 基于每个字节码收集信息,无法在多条字节码之间共享共享值的类型
feedback 也不支持类型收缩