JSRC v8 Turbofan优化框架简述
JSRC v8 Turbofan
优化框架简述
前言
v8是google的一个开源js引擎，应用十分广泛，除了常见的chrome和nodejs外，安卓的WebView，以及很多App都会在内部集成v8用于执行js代码，因此v8的安全影响了大量的下游应用。
研究v8的安全，有助于提前发现未知的风险，做到防患于未然，还可以在处理v8漏洞时做到"知其然知其所以然"，能够真正理解漏洞，做到举一反三。
1 | V8整体架构
v8整体架构与传统的编译器类似，可以划分为前端与后端两部分，下图是v8架构的简介。
-
前端负责把输入的js代码解析为AST，然后把AST翻译为专用于v8虚拟机的ignition字节码。
-
后端两种执行方式：
-解释执行：ignition虚拟机会按部就班的执行字节码，在执行过程中会收集关于变量类型的信息，记录在feedback中。这种执行方式响应速度快，但是执行效率低，适合低频执行的函数。
-优化执行：如果一个函数被执行的很多次，那么就会触发优化执行，turbofan会将字节码翻译为sea-of-node类型的IR，然后根据feedback中记录的信息进行投机性的优化，最后生成底层的汇编代码，这种方式执行效率快但是响应速度慢，适合高频执行的函数。
注意！turbofan是一个投机性的优化编译器。“投机”是因为js是弱类型语言，考虑下面这个例子：
function opt(x) {
return x+1;
}
for(let i=0; i<100000; i++) {
opt(i); // [1]
}
opt(12.345); // [2]
[1]处执行了非常多次opt(i)，根据解释执行时收集到的feedback可知，每次执行x+1时x都是一个整数。那么turbofan在优化opt()时就会直接把x+1当作是两个整数之间的加法并生成汇编指令。因为过去一直是整数加法，那么未来大概率仍然是整数加法，这就是turbofan的惰性。
但实际上js中的加法是很复杂的，考虑在[2]处的调用，此时x为一个浮点数，那么优化后opt()的整数加法指令就不适合与这种情况，此时就会触发反优化：优化假设被打破, opt()会从JIT执行回退到解释执行。
以上就是v8的大致架构，回顾历史，大量的漏洞络绎不绝的出现在turbofan中：
1）因为turbofan代码量庞大，是v8各个组件中最为复杂的一个。
2）turbofan中的错误会导致生成错误的汇编代码，更容易导致RCE，因此turbofan的漏洞更为严重。
v8是十分复杂的, 就算只考虑Turbofan这个组件也有52w行的代码，因此本文简单介绍一下Turbofan整体的框架，主要探讨了：
1）turbofan是如何遍历图IR sea-of-node的。
2）优化器是怎么耦合进turbofan的。
具体的优化机制篇幅有限无法介绍, 希望后续可以抽丝剥茧地带大家领略v8的风采。
2 | Sea-of-node
2.1 简介
Sea-of-node是一种基于图的程序中间表示，是Turbofan的输入，后续各种优化都是对于sea-of-node的修改。
Sea-of-node可以同时表示控制流与数据流，并且让节点之间可以尽量自由的移动，以方便优化器优化。
考虑下面这个程序，对应的SSA-CFG如下。SSA-CFG以指令块为单位，而sea-of-node中以节点为单位，一个节点可以是一个指令，也可以代表一个数据。
下面是转换为sea-of-node的过程。
2.2 Control edge
首先构造控制流相关节点，黄色表示控制节点，黄色节点之间的边被称为control edge，表示控制流。
2.3 Value edge
然后是构造数据流，绿色的节点表示数据节点，绿色节点之间的边被称为value edge，表示数据流；其中phi节点表示数据流的合并。
最后添加上蓝色的操作节点, 表示对于数据的处理。
2.4 Effect edge
然后此时sea-of-node表示的信息还是不够完整，sea-of-node中某些节点可能具有副作用(external effect)。
考虑下面这个例子，在优化opt()时, 假设Call[f1]节点表示调用函数f1()，Call[f2]节点表示调用函数f2()。不难发现Call[f1]与Call[f2]之间既没有数据流之间的关系，也没有控制流之间的关系，但这并不意味着优化时就可以随意重排序Call[f1]和Call[f2]，因为这两个节点都是具有副作用的，必须只能按照程序中的顺序来。
就本例子而言，如果把Call[f2]放在Call[f1]前面，那么优化后opt()的结果就会改变，这显然是一个错误的优化。本例子中的副作用指的就是Call[f1]和Call[f2]会修改全局变量x。
let x = 0;
function f1() {
x = 1;
}
function f2() {
x = 2;
}
function opt(){
f1();
f2();
}
实际上很多节点都可能具有副作用，我们需要告诉优化器不能随意重排序这些节点，因此还需要添加effect edge，如下，这里使用红色边表示。
这样，程序中的信息才算是被sea-of-node完整的表达了出来。
SSA-CFG中的边只表达了控制流关系。sea-of-node将Basic Block拆散，是一种更加细腻的表达方式。
下面会正式进入代码部分，介绍三个问题：
1）turbofan的优化流程
2）turbofan是如何遍历sea-of-node
3）优化器是如何工作的
3 | Turbofan
3.1 优化流水线
turbofan整体优化流程如下。其中每一个函数都会执行多个Phase，每个Phase之间相互独立，一个Phase代表一次对于图的遍历，是优化流水线的基本单位。
class PipelineImpl final {
public:
...
// Step A.1. Initialize the heap broker.
void InitializeHeapBroker();
// Step A.2. Run the graph creation and initial optimization passes.
bool CreateGraph();
// Step B. Run the concurrent optimization passes.
bool OptimizeGraph(Linkage* linkage);
// Substep B.1. Produce a scheduled graph.
void ComputeScheduledGraph();
turboshaft::PipelineData GetTurboshaftPipelineData(turboshaft::TurboshaftPipelineKind kind);
// Substep B.2.turbofan Select instructions from a scheduled graph.
bool SelectInstructions(Linkage* linkage);
// Substep B.2.turboshaft Select instructions from a turboshaft graph.
bool SelectInstructionsTurboshaft(Linkage* linkage);
// Substep B.3. Run register allocation on the instruction sequence.
bool AllocateRegisters(CallDescriptor* call_descriptor,
bool has_dummy_end_block);
// Step C. Run the code assembly pass.
void AssembleCode(Linkage* linkage);
// Step D. Run the code finalization pass.
MaybeHandle FinalizeCode(bool retire_broker = true);
// Step E. Ensure all embedded maps are non-deprecated.
bool CheckNoDeprecatedMaps(Handle code);
// Step F. Install any code dependencies.
bool CommitDependencies(Handle code);
...
};
按照功能，Turbofan的phase可以分为以下几部分：
1）图生成：包含两个phase：
a.GraphBuilderPhase: turbofan基于图类型的IR进行优化，这个phase负责根据ignition字节码生成sea-of-node类型的IR。
b.InliningPhase: 负责进行内联。
2）图优化：
a. EarlyGraphTrimmingPhase: 删除中图中无用的节点(也就是删除无用的语句)。
b. TyperPhase：Typer负责计算图中每一个节点的类型，并且Typer会持续运行，在图中添加新节点时同样会计算他们的类型。
c. TypedLoweringPhase：将比较高层次的类型转化为低层次的类型，更加贴近于底层汇编, 更容易优化。
d. LoopPeelingPhase:
e. LoadEliminationPhase: 消除图中的代表通用js操作的LoadField，LoadElements，...节点，将其优化为直接的内存读语句(js操作需要跳转到Runtime方法进行Map检查，原型链路由等复杂操作，虽然通用但是效率很低，直接优化为内存读语句可以大大提高效率)。
f. EscapeAnalysisPhase: 逃逸分析，避免创建无用的中间对象。
g. SimplifiedLoweringPhase: 将高层次操作的节点优化为更低层次操作的节点, 优化节点的表示方式, 使其更加贴近底层。
h. GenericLoweringPhase: 用于优化是JS操作。
i. ....
3）Node重排序: schedule: Sea-of-Node是基于图的IR，该节点会根据图中的边对节点进行排序，得到Node组成的CFG，这更加贴近于底层汇编，以方便进一步编译。
4）turboshaft，生成后端优化。这是一个新的turbofan后端框架，用于对Node进行机器架构相关的优化并最终生成汇编代码。
a. TurboshaftBuilderGraph: 排序后的Node CFG转换为turboshaft IR CFG。
b. turboshaft相关优化Phase。
c. InstructionSelectionPhase: 选择底层的机器代码。
d. AllocateRegisters: 分配寄存器，生成最终汇编代码。
总结一下Turbofan的架构：
-
Turbofan的输入为sea-of-node。
-
前端: GraphBuilderPhase负责根据ignition字节码生成sea-of-node表示, 除此以外CSA, Torque, wasm等部分也会通过C++ DSL创建sea-of-node从而借助turbofan生成优化后的汇编指令。
-
优化层: 这是turbofan的主体, 包含各种优化Phase, 这里的优化进行的都是与架构无关的优化。
-
后端: 这部分由turboshaft负责, turboshaft负责根据Node与架构相关的优化并生成最终的汇编代码。
3.2 优化目标
可以看出，整个 TurboFan 的流程都在围绕Node进行工作，而Node一般会被分为三个层次：
1）Common Node 自始至终贯穿所有阶段。
2）JavaScript Node：这个层次的节点代表最通用的js操作，最为复杂，比如JSAdd节点，该节点支持所有类型的加法操作，比如{}+1，1.1+1。
3）而在优化的过程中，会有一部分JavaScript Node被降级为 Simplified Node。比如JSAdd被降级为SpeculativeSafeIntegerAdd，就只支持整数之间的加法。
4）在后续进一步的优化中，Simplified Node 也会有一部分被降级为 Machine Node。比如SpeculativeSafeIntegerAdd被降级为Int32Add，这是最贴近底层汇编指令的节点，也是效率最高的。
一个js操作有多种实现方式，对应sea-of-node中不同类型的节点，turbofan的主要工作就是把高层次的js操作经可能优化的贴近汇编，然后生成汇编代码，以提高效率。
4| V8整体架构
GraphReducer
想要优化图, 就必须对图进行遍历, 在Turbofan的设计中图遍历与图优化分拆分开来：
-
为了优化进行图遍历的工作由GraphReducer类实现，该类只负责以特定顺序遍历图并对每个节点顺序调用多个优化器进行优化。
-
具体的优化操作由各种Reducer的子类(优化器)实现，GraphReducer在遍历时会对于每个节点调用多个Reducer进行优化。
turbofan的优化层次如下：
1）Turbofan优化器 = 多个优化Phase
2）一个优化Phase = 一次图优化 = 一次图遍历GraphReducer + 多个优化器Reducer
3）一个Reducer负责对特定节点进行优化
这样每个Phase就只负责特定的任务，而且有些Reducer在多个Phase之间是通用的，可以自由组合， 提高代码复用率。
下面主要研究GraphReducer是如何遍历图的（图片来源: laiyonggao）
4.1 GraphReducer类
GraphReducer中的相关节点和字段如下：
1）Graph* const graph_：graph指针, 指向被优化的sea-of-node图。
2）ZoneStackstack_：一个栈，用于保存要遍历节点；
a. GraphReducer整体是使用栈+循环实现的DFS算法， 按照左右根的顺序遍历图并进行优化, 所以需要一个临时栈保存待访问的节点；
b. 其中input_index代表当前访问的节点是父节点的第几个子节点(也可以说是第几个父节点的第几个输入节点)。
3）ZoneVectorreducers_ : Recuer为一个优化器对象m 该字段为多个优化器组成的数组，一次图优化可能会调用多个优化器对一个节点进行优化。
4）ZoneQueuerevisit_：一个队列，保存需要重新优化的节点。
class V8_EXPORT_PRIVATE GraphReducer: public NON_EXPORTED_BASE(AdvancedReducer::Editor) {
public:
// 获取图对象
Graph* graph() const { return graph_; }
// 添加一个优化器reducer
void AddReducer(Reducer* reducer);
// 对于单个节点进行优化
void ReduceNode(Node* const);
// 优化整个图, 会遍历graph中的节点并调用所有的reducer访问该节点
void ReduceGraph();
private:
enum class State : uint8_t;
struct NodeState {
Node* node;
int input_index;
};
...
Graph* const graph_;
Node* const dead_;
NodeMarkerstate_;
ZoneVectorreducers_;
ZoneQueuerevisit_;
ZoneStackstack_;
...
};
4.2 图遍历过程
GraphReducer整体是使用栈+循环实现的DFS算法， 按照左右根的顺序从end节点遍历图并进行优化。
如果reducer不会删除或者添加节点的话，整体访问过程如下 ：(图片来源: 知乎@赖勇高)
这里n3的input_index=2表示n6是n3的第2个子节点(第2个输入节点)。
图中标注有误, n2的input_index应该还是1。
这里n2的input_index为2代表n4是n2的第二个输入节点。
但实际上优化过程中reducer可能会改变当前节点，改边分为两种情况：
1）inplace reduction: 如果reducer只改变了当前节点中的输入节点或者属性，那么后续新节点会被添加到要待遍历节点的栈中。
2）replacement reduction: 如果reducer将当前节点节点替换成新节点，那么GraphReducer会重新遍历新的子树。
注意：GraphReducer是backwards DFS，是从End节点开始遍历整个图的，以下面这个sea-of-node为例子，从End节点开始变量，最先被处理的叶子节点就是1 Parameter，2 Parameter等节点，然后是处理这些参数的中间节点，最后再优化19:Deoptimize，20: End这种数据流末尾的节点。
4.3 图遍历代码实现
ReduceGraph()会直接调用ReduceNode(graph()->end())从尾节点开始优化整个图。
void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
GraphReducer::ReduceNode()则会
1）循环从stack_中获取栈顶元素并调用ReduceTop()进行优化。
2）在stack_为空时, 会检查revisit_中是否有需要重新访问的节点, 如果有则将其访问stack_中。
3）最后会调用所有Reducer的Finalize()方法。
void GraphReducer::ReduceNode(Node* node) {
Push(node); // 栈中压入当前正在访问的节点: [{node, 0}] <= top
for (;;) {
if (!stack_.empty()) { // stack_非空, 则优化栈顶的元素
ReduceTop(); // 处理栈顶元素时可能会push或者pop这个stack
} else if (!revisit_.empty()) { // 当stack_为空时, 就重新访问revisit_中的所有节点
// 从revisit_中弹出一个节点
Node* const node = revisit_.front();
revisit_.pop();
// 如果需要重新访问, 则重新加入到stack_中
if (state_.Get(node) == State::kRevisit) {
Push(node);
}
} else { // 所有节点遍历结束
// 通知reducer所有节点访问完毕
for (Reducer* const reducer : reducers_) reducer->Finalize();
// reducer->Finalize()可能还会添加新节点, 因此检查一下是否还有要继续重新访问的节点
if (revisit_.empty()) break;
}
}
}
GraphReducer::ReduceTop()的优化过程实现, 大致骨架就是非递归版本的DFS, 并且还进行了一些增强: 每当一个节点被优化器改变时, 会重新遍历所有被影响到的节点, 以保证优化进行的足够彻底
void GraphReducer::ReduceTop() {
NodeState& entry = stack_.top(); // 获取栈顶节点
Node* node = entry.node;
if (node->IsDead()) return Pop(); // 该节点在栈中时被其他优化器优化掉了, 不再处理
Node::Inputs node_inputs = node->inputs(); // 获取node的所有输入节点, 开始向上遍历
// input_index代表之前访问到node的第几个节点了, 跳过已经访问过的节点
// 如果entry.input_index >= node_inputs.count(), 说明node的子节点都已经访问过了, 但是现在需要再重新访问一遍
int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
// 开始遍历所有要处理处理的输入节点
for (int i = start; i < node_inputs.count(); ++i) {
Node* input = node_inputs[i];
// 发现一个要处理的输入节点, 调用Recurse()将其压入栈顶, 以模拟递归实现DFS的效果
if (input != node && Recurse(input)) {
// 再次处理node时, 说明节点input已经处理完毕了, 应该处理下一个输入节点
entry.input_index = i + 1;
return; // stack_状态: [{node, 1}, {input, 0}] <= top
}
}
// 作用未知, 对于重复访问的节点Recurse()会调过
for (int i = 0; i < start; ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}
// 生成节点id
NodeId const max_id = static_cast(graph()->NodeCount() - 1);
// 进入到这里, 说明node没有子节点 or node的所有子节点都处理完毕了, 因此可以优化node节点了
Reduction reduction = Reduce(node); // reduction表示优化结果
// 优化后发现没有改边, 那么可以直接弹出该节点, 对于该节点的优化结束
if (!reduction.Changed()) return Pop();
// node被原地更新, 也就是说节点本身没有改边, 但是输入节点可能改边了
Node* const replacement = reduction.replacement();
if (replacement == node) {
// node处理完毕后, 所有使用node节点的节点也要重新优化 (stack_中所有节点处理完毕才回处理revisit_中的)
for (Node* const user : node->uses()) {
Revisit(user);
}
// 重新遍历node的所有输入节点
Node::Inputs node_inputs = node->inputs();
for (int i = 0; i < node_inputs.count(); ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}
}
// node被优化了, 因此从栈中弹出
Pop();
/* 如果优化后节点node需要被替换为replacement, 那么
1.Replace()方法会在graph中替换节点node为replacement
2.并重新优化replacement对应的子树
*/
if (replacement != node) {
Replace(node, replacement, max_id);
}
}
每一个节点都有如下状态
enum class GraphReducer::State : uint8_t {
kUnvisited, // 还没有访问过
kRevisit, // 需要重新访问
kOnStack, // 在栈中
kVisited // 已经访问过
};
在调用Recurse()尝试递归处理该节点时, 会检查节点的状态, 如果发现节点已经访问过了或者真正栈中, 那么就会跳过
void GraphReducer::Push(Node* const node) {
state_.Set(node, State::kOnStack);
stack_.push({node, 0});
}
bool GraphReducer::Recurse(Node* node) {
if (state_.Get(node) > State::kRevisit) return false;
Push(node);
return true;
}
GraphReducer::Reduce()负责优化一个节点, 优化过程如下
Reduction GraphReducer::Reduce(Node* const node) {
auto skip = reducers_.end();
for (auto i = reducers_.begin(); i != reducers_.end();) { // 遍历所有的优化器
if (i != skip) {
Reduction reduction = (*i)->Reduce(node, observe_node_manager_); // 优化器的Reduce()方法进行优化
if (!reduction.Changed()) { // 没有发生改变, 则继续调用下一个优化器
// No change from this reducer.
} else if (reduction.replacement() == node) { // 对node节点进行了原地优化(改变了node的属性或者输入节点)
...
skip = i; // 重新优化节点node，但是要调过该优化器，保证其他优化器可以匹配到优化后的结果
i = reducers_.begin();
continue;
} else { // node被替换为其他节点, node已经被替换了, 所以无法在node上继续应用其他优化器
return reduction;
}
}
++i;
}
if (skip == reducers_.end()) { // 既没有发生replace reduction也没有发生inplace reduction
return Reducer::NoChange();
}
return Reducer::Changed(node); // 发生了inplace reduction, 返回优化结果
}
5 | 优化器
Reducer
综上，可以看到GraphReducer是Reducer的主要调用方，现在切换到Reducer的视角，看一下Reducer是如何被调用的，因为后续研究优化过程本质上就是在研究各个Reducer的实现。
5.1 Reducer类结构
Reducer类的实现如下.
class V8_EXPORT_PRIVATE Reducer {
public:
// 用于优化node子树, observe_node_manager用于观测节点改边.
// 每当图发生改变时GraphReducer都会调用该方法尽可能的优化
Reduction Reduce(Node* node, ObserveNodeManager* observe_node_manager);
// 在所有节点都处理完毕时GraphReducer会调用该方法, 可以在末尾进行一些额外的优化, 这会导致新一轮的图遍历
virtual void Finalize();
// 三个用于返回结果的助手函数
static Reduction NoChange() { return Reduction(); } // 没有改变
static Reduction Replace(Node* node) { return Reduction(node); } // replacement reduction, 原节点被替换为node
static Reduction Changed(Node* node) { return Reduction(node); } // inplace reduction, 原节点没有被替换, 只是属性或者输入节点被改边了
private:
virtual Reduction Reduce(Node* node) = 0; // 子类要实现的函数
};
Reduce()方法在优化节点时：
-
如果要进行inplace reduction, 那么可以直接修改该节点的属性或者输入节点, 然后调用Changed()/Replace()返回该节点的地址, 只要输入Reduce()方法的节点指针与该方法返回的指针一致, 那么GraphReducer就会认为这是inplace reduction。
-
如果要进行replacement reduction, 那么就不能擅自替换, 需要构建新的子树后调用Changed()/Replace()方法返回新节点的指针, 通知GraphReducer该节点要被替换为什么节点, 由GraphReducer处理sea-of-node中的替换和遍历。
5.2 实现一个Reducer
因此可以尝试编写一个最简单HelloReducer, 只用于输出节点id。
class HelloReducer: public Reducer {
const char* reducer_name() const override { return "HelloReducer"; }
Reduction Reduce(Node* node) {
printf("%d\n", node->id());
return NoChange();
}
};
然后编写一个HelloPhase, 该方法建GraphReducer, 然后添加HelloReducer, 然后遍历图
struct HelloPhase {
DECL_PIPELINE_PHASE_CONSTANTS(Hello)
void Run(PipelineData* data, Zone* temp_zone) {
OptimizedCompilationInfo* info = data->info();
GraphReducer graph_reducer(temp_zone, data->graph(), &info->tick_counter(),
data->broker(), data->jsgraph()->Dead(),
data->observe_node_manager());
HelloReducer reducer;
AddReducer(data, &graph_reducer, &reducer);
graph_reducer.ReduceGraph();
}
};
在src/logging/runtime-call-stats.h中额外添加一个宏, 注册HelloPhase
最后在GraphBuilderPhase后面执行HelloPhase, 就可以输出图刚刚构建完毕时的所有node id。
总结
RECRUIT
综上我们对于Turbofan优化器有了基本的了解：
1）Turbofan的输入为sea-of-node类型的IR。
2）sea-of-node IR是节点组成的图，包含input edge，control edge，effect edge三种边，这些边在维持了程序语义的同时允许更加自由的节点移动，可简化优化器的实现。
3）Turbofan的优化流水线包含多个Phase，每一个Phase代表着一次对于sea-of-node “彻底”的深度优先遍历。
4）每一个Phase中都包含着多个优化器，优化器可能会原地修改节点的属性，也可能会直接替换掉某个节点子树。Phase “彻底”的遍历指的是当优化器修改图中节点时，都会重新遍历所有受影响的节点。
