▷ 浅析 V8-turboFan（上）

void AllocateRegisters(const RegisterConfiguration* config,

CallDescriptor* call_descriptor, bool run_verifier);

OptimizedCompilationInfo* info() const;

Isolate* isolate() const;

CodeGenerator* code_generator() const;

private:

PipelineData* const data_;

};

五、初探optimization phases

1. 简介

与LLVM IR的各种Pass类似，turboFan中使用各类phases进行建图、搜集信息以及简化图。

以下是PipelineImpl::CreateGraph函数源码，其中使用了大量的Phase。这些Phase有些用于建图，有些用于优化（在建图时也会执行一部分简单的优化），还有些为接下来的优化做准备：

bool PipelineImpl::CreateGraph() {

PipelineData* data = this->data_;

data->BeginPhaseKind("graph creation");

if (info()->trace_turbo_json_enabled() ||

info()->trace_turbo_graph_enabled()) {

CodeTracer::Scope tracing_scope(data->GetCodeTracer());

OFStream os(tracing_scope.file());

os << "---------------------------------------------------\n"

<< "Begin compiling method " << info()->GetDebugName().get()

<< " using Turbofan" << std::endl;

}

if (info()->trace_turbo_json_enabled()) {

TurboCfgFile tcf(isolate());

tcf << AsC1VCompilation(info());

}

data->source_positions()->AddDecorator();

if (data->info()->trace_turbo_json_enabled()) {

data->node_origins()->AddDecorator();

}

Run();

RunPrintAndVerify(GraphBuilderPhase::phase_name(), true);

// Perform function context specialization and inlining (if enabled).

Run();

RunPrintAndVerify(InliningPhase::phase_name(), true);

// Remove dead->live edges from the graph.

Run();

RunPrintAndVerify(EarlyGraphTrimmingPhase::phase_name(), true);

// Run the type-sensitive lowerings and optimizations on the graph.

{

// Determine the Typer operation flags.

Typer::Flags flags = Typer::kNoFlags;

if (is_sloppy(info()->shared_info()->language_mode()) &&

info()->shared_info()->IsUserJavaScript()) {

// Sloppy mode functions always have an Object for this.

flags |= Typer::kThisIsReceiver;

}

if (IsClassConstructor(info()->shared_info()->kind())) {

// Class constructors cannot be [[Call]]ed.

flags |= Typer::kNewTargetIsReceiver;

}

// Type the graph and keep the Typer running on newly created nodes within

// this scope; the Typer is automatically unlinked from the Graph once we

// leave this scope below.

Typer typer(isolate(), data->js_heap_broker(), flags, data->graph());

Run(&typer);

RunPrintAndVerify(TyperPhase::phase_name());

// Do some hacky things to prepare for the optimization phase.

// (caching handles, etc.).

Run();

if (FLAG_concurrent_compiler_frontend) {

data->js_heap_broker()->SerializeStandardObjects();

Run();

}

// Lower JSOperators where we can determine types.

Run();

RunPrintAndVerify(TypedLoweringPhase::phase_name());

}

data->EndPhaseKind();

return true;

}

PipelineImpl::OptimizeGraph函数代码如下，该函数将会对所建立的图进行优化：

bool PipelineImpl::OptimizeGraph(Linkage* linkage) {

PipelineData* data = this->data_;

data->BeginPhaseKind("lowering");

if (data->info()->is_loop_peeling_enabled()) {

Run();

RunPrintAndVerify(LoopPeelingPhase::phase_name(), true);

} else {

Run();

RunPrintAndVerify(LoopExitEliminationPhase::phase_name(), true);

}

if (FLAG_turbo_load_elimination) {

Run();

RunPrintAndVerify(LoadEliminationPhase::phase_name());

}

if (FLAG_turbo_escape) {

Run();

if (data->compilation_failed()) {

info()->AbortOptimization(

BailoutReason::kCyclicObjectStateDetectedInEscapeAnalysis);

data->EndPhaseKind();

return false;

}

RunPrintAndVerify(EscapeAnalysisPhase::phase_name());

}

// Perform simplified lowering. This has to run w/o the Typer decorator,

// because we cannot compute meaningful types anyways, and the computed types

// might even conflict with the representation/truncation logic.

Run();

RunPrintAndVerify(SimplifiedLoweringPhase::phase_name(), true);

// From now on it is invalid to look at types on the nodes, because the types

// on the nodes might not make sense after representation selection due to the

// way we handle truncations; if we'd want to look at types afterwards we'd

// essentially need to re-type (large portions of) the graph.

// In order to catch bugs related to type access after this point, we now

// remove the types from the nodes (currently only in Debug builds).

#ifdef DEBUG

Run();

RunPrintAndVerify(UntyperPhase::phase_name(), true);

#endif

// Run generic lowering pass.

Run();

RunPrintAndVerify(GenericLoweringPhase::phase_name(), true);

data->BeginPhaseKind("block building");

// Run early optimization pass.

Run();

RunPrintAndVerify(EarlyOptimizationPhase::phase_name(), true);

Run();

RunPrintAndVerify(EffectControlLinearizationPhase::phase_name(), true);

if (FLAG_turbo_store_elimination) {

Run();

RunPrintAndVerify(StoreStoreEliminationPhase::phase_name(), true);

}

// Optimize control flow.

if (FLAG_turbo_cf_optimization) {

Run();

RunPrintAndVerify(ControlFlowOptimizationPhase::phase_name(), true);

}

// Optimize memory access and allocation operations.

Run();

// TODO(jarin, rossberg): Remove UNTYPED once machine typing works.

RunPrintAndVerify(MemoryOptimizationPhase::phase_name(), true);

// Lower changes that have been inserted before.

Run();

// TODO(jarin, rossberg): Remove UNTYPED once machine typing works.

RunPrintAndVerify(LateOptimizationPhase::phase_name(), true);

data->source_positions()->RemoveDecorator();

if (data->info()->trace_turbo_json_enabled()) {

data->node_origins()->RemoveDecorator();

}

ComputeScheduledGraph();

return SelectInstructions(linkage);

}

由于上面两个函数涉及到的Phase众多，这里请各位自行阅读源码来了解各个Phase的具体功能。

接下来我们只介绍几个比较重要的Phases：GraphBuilderPhase、TyperPhase和SimplifiedLoweringPhase。

2. GraphBuilderPhase

GraphBuilderPhase将遍历字节码，并建一个初始的图，这个图将用于接下来Phase的处理，包括但不限于各种代码优化。

一个简单的例子

3. TyperPhase

TyperPhase将会遍历整个图的所有结点，并给每个结点设置一个Type属性，该操作将在建图完成后被执行给每个结点设置Type的操作是不是极其类似于编译原理中的语义分析呢？ XD

bool PipelineImpl::CreateGraph() {

// ...

Run();

RunPrintAndVerify(GraphBuilderPhase::phase_name(), true);

// ...

// Run the type-sensitive lowerings and optimizations on the graph.

{

// ...

// Type the graph and keep the Typer running on newly created nodes within

// this scope; the Typer is automatically unlinked from the Graph once we

// leave this scope below.

Typer typer(isolate(), data->js_heap_broker(), flags, data->graph());

Run(&typer);

RunPrintAndVerify(TyperPhase::phase_name());

// ...

}

// ...

}

其中，具体执行的是TyperPhase::Run函数：

struct TyperPhase {

static const char* phase_name() { return "typer"; }

void Run(PipelineData* data, Zone* temp_zone, Typer* typer) {

// ...

typer->Run(roots, &induction_vars);

}

};

在该函数中继续调用Typer::Run函数，并在GraphReducer::ReduceGraph函数中最终调用到Typer::Visitor::Reduce函数：

void Typer::Run(const NodeVector& roots,

LoopVariableOptimizer* induction_vars) {

// ...

Visitor visitor(this, induction_vars);

GraphReducer graph_reducer(zone(), graph());

graph_reducer.AddReducer(&visitor);

for (Node* const root : roots) graph_reducer.ReduceNode(root);

graph_reducer.ReduceGraph();

// ...

}

在Typer::Visitor::Reduce函数中存在一个较大的switch结构，通过该switch结构，当Visitor遍历每个node时，即可最终调用到对应的XXXTyper函数。

例如，对于一个JSCall结点，将在TyperPhase中最终调用到Typer::Visitor::JSCallTyper

这里我们简单看一下JSCallTyper函数源码，该函数中存在一个很大的switch结构，该结构将设置每个Builtin函数结点的Type属性，即函数的返回值类型。

Type Typer::Visitor::JSCallTyper(Type fun, Typer* t) {

if (!fun.IsHeapConstant() || !fun.AsHeapConstant()->Ref().IsJSFunction()) {

return Type::NonInternal();

}

JSFunctionRef function = fun.AsHeapConstant()->Ref().AsJSFunction();

if (!function.shared().HasBuiltinFunctionId()) {

return Type::NonInternal();

}

switch (function.shared().builtin_function_id()) {

case BuiltinFunctionId::kMathRandom:

return Type::PlainNumber();

// ...

而对于一个常数NumberConstant类型，TyperPhase也会打上一个对应的类型

Type Typer::Visitor::TypeNumberConstant(Node* node)

// 注意这里使用的是double，这也就说明了为什么Number.MAX_SAFE_INTEGER = 9007199254740991

double number = OpParameter(node->op());

return Type::NewConstant(number, zone());

}

而在Type::NewConstant函数中，我们会发现一个神奇的设计：

Type Type::NewConstant(double value, Zone* zone) {

// 对于一个正常的整数

if (RangeType::IsInteger(value)) {

// 实际上所设置的Type是一个range！

return Range(value, value, zone);

// 否则如果是一个异常的-0,则返回对应的MinusZero

} else if (IsMinusZero(value)) {

return Type::MinusZero();

// 如果是NAN，则返回NaN

} else if (std::isnan(value)) {

return Type::NaN();

}

DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));

return OtherNumberConstant(value, zone);

}

对于JS代码中的一个NumberConstant，实际上设置的Type是一个Range，只不过这个Range的首尾范围均是该数，例如NumberConstant(3) => Range(3, 3, zone)

以下这张图可以证明TyperPhase正如预期那样执行：

与之相应的，v8采用了SSA。因此对于一个Phi结点，它将设置该节点的Type为几个可能值的Range的并集。

Type Typer::Visitor::TypePhi(Node* node) {

int arity = node->op()->ValueInputCount();

Type type = Operand(node, 0);

for (int i = 1; i < arity; ++i) {

type = Type::Union(type, Operand(node, i), zone());

}

return type;

}

请看以下示例：

4. SimplifiedLoweringPhase

SimplifiedLoweringPhase会遍历结点做一些处理，同时也会对图做一些优化操作。这里我们只关注该Phase优化CheckBound的细节，因为CheckBound通常是用于判断 JS数组（例如ArrayBuffer） 是否越界使用 所设置的结点。

首先我们可以通过以下路径来找到优化CheckBound的目标代码：

SimplifiedLoweringPhase::Run

SimplifiedLowering::LowerAllNodes

RepresentationSelector::Run

RepresentationSelector::VisitNode

目标代码如下:

// Dispatching routine for visiting the node {node} with the usage {use}.

// Depending on the operator, propagate new usage info to the inputs.

void VisitNode(Node* node, Truncation truncation,

SimplifiedLowering* lowering) {

// Unconditionally eliminate unused pure nodes (only relevant if there's

// a pure operation in between two effectful ones, where the last one

// is unused).

// Note: We must not do this for constants, as they are cached and we

// would thus kill the cached {node} during lowering (i.e. replace all

// uses with Dead), but at that point some node lowering might have

// already taken the constant {node} from the cache (while it was in

// a sane state still) and we would afterwards replace that use with

// Dead as well.

if (node->op()->ValueInputCount() > 0 &&

node->op()->HasProperty(Operator::kPure)) {

if (truncation.IsUnused()) return VisitUnused(node);

}

switch (node->opcode()) {

// ...

case IrOpcode::kCheckBounds: {

const CheckParameters& p = CheckParametersOf(node->op());

Type index_type = TypeOf(node->InputAt(0));

Type length_type = TypeOf(node->InputAt(1));

if (index_type.Is(Type::Integral32OrMinusZero())) {

// Map -0 to 0, and the values in the [-2^31,-1] range to the

// [2^31,2^32-1] range, which will be considered out-of-bounds

// as well, because the {length_type} is limited to Unsigned31.

VisitBinop(node, UseInfo::TruncatingWord32(),

MachineRepresentation::kWord32);

if (lower() && lowering->poisoning_level_ ==

PoisoningMitigationLevel::kDontPoison) {

// 可以看到，如果当前索引的最大值小于length的最小值，则表示当前索引的使用没有越界

if (index_type.IsNone() || length_type.IsNone() ||

(index_type.Min() >= 0.0 &&

index_type.Max() < length_type.Min())) {

// The bounds check is redundant if we already know that

// the index is within the bounds of [0.0, length[.

// CheckBound将会被优化

DeferReplacement(node, node->InputAt(0));

}

}

} else {

VisitBinop(

node,

UseInfo::CheckedSigned32AsWord32(kIdentifyZeros, p.feedback()),

UseInfo::TruncatingWord32(), MachineRepresentation::kWord32);

}

return;

}

// ....

}

// ...

}

可以看到，在CheckBound的优化判断逻辑中，如果当前索引的最大值小于length的最小值，则表示当前索引的使用没有越界，此时将会移除CheckBound结点以简化IR图。

需要注意NumberConstant结点的Type是一个Range类型，因此才会有最大值Max和最小值Min的概念。

这里需要解释一下环境搭配中所说的，为什么要添加一个编译参数v8_optimized_debug = false，注意看上面判断条件中的这行条件

if (lower() && lowering->poisoning_level_ ==

PoisoningMitigationLevel::kDontPoison)

visitNode时有三个状态，分别是Phase::PROPAGATE（信息收集）、Phase::RETYPE（从类型反馈中获取类型）以及Phase::LOWER（开始优化）。当真正开始优化时，lower()条件自然成立，因此我们无需处理这个。

但对于下一个条件，通过动态调试可以得知，poisoning_level始终不为PoisoningMitigationLevel::kDontPoison。通过追溯lowering->poisoning_level_，我们可以发现它实际上在PipelineCompilationJob::PrepareJobImpl中被设置

PipelineCompilationJob::Status PipelineCompilationJob::PrepareJobImpl(

Isolate* isolate) {

// ...

// Compute and set poisoning level.

PoisoningMitigationLevel load_poisoning =

PoisoningMitigationLevel::kDontPoison;

if (FLAG_branch_load_poisoning) {

load_poisoning = PoisoningMitigationLevel::kPoisonAll;

} else if (FLAG_untrusted_code_mitigations) {

load_poisoning = PoisoningMitigationLevel::kPoisonCriticalOnly;

}

// ...

}

而FLAG_branch_load_poisoning始终为false，FLAG_untrusted_code_mitigations始终为true

编译参数v8_untrusted_code_mitigations 默认 true，使得宏DISABLE_UNTRUSTED_CODE_MITIGATIONS没有被定义，因此默认设置FLAG_untrusted_code_mitigations = true

// v8/src/flag-definitions.h

// 设置`FLAG_untrusted_code_mitigations`

#ifdef DISABLE_UNTRUSTED_CODE_MITIGATIONS

#define V8_DEFAULT_UNTRUSTED_CODE_MITIGATIONS false

#else

#define V8_DEFAULT_UNTRUSTED_CODE_MITIGATIONS true

#endif

DEFINE_BOOL(untrusted_code_mitigations, V8_DEFAULT_UNTRUSTED_CODE_MITIGATIONS,

"Enable mitigations for executing untrusted code")

#undef V8_DEFAULT_UNTRUSTED_CODE_MITIGATIONS

// 设置`FLAG_branch_load_poisoning`

DEFINE_BOOL(branch_load_poisoning, false, "Mask loads with branch conditions.")

# BUILD.gn

declare_args() {

# ...

# Enable mitigations for executing untrusted code.

# 默认为true

v8_untrusted_code_mitigations = true

# ...

}

# ...

if (!v8_untrusted_code_mitigations) {

defines += [ "DISABLE_UNTRUSTED_CODE_MITIGATIONS" ]

}

# ...

这样就会使得load_poisoning始终为PoisoningMitigationLevel::kPoisonCriticalOnly，因此始终无法执行checkBounds的优化操作。所以我们需要手动设置编译参数v8_untrusted_code_mitigations = false，以启动checkbounds的优化。

以下是一个简单checkbounds优化的例子

function f(x)

{

const arr = new Array(1.1, 2.2, 3.3, 4.4, 5.5);

let t = 1 + 1;

return arr[t];

}

console.log(f(1));

%OptimizeFunctionOnNextCall(f);

console.log(f(1));

优化前发现存在一个checkBounds：

执行完SimplifiedLoweringPhase后，CheckBounds被优化了: