V8 Turbofan Node_Reduce

参考

Ignition and TurboFan Compiler Pipeline
TurboFan TechTalk presentation
图片都是从这个ppt里截的图

ReduceGraph

优化的一些阶段都会进行graph的reduce操作,以typedlowering阶段为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct TypedLoweringPhase {
static const char* phase_name() { return "V8.TFTypedLowering"; }
void Run(PipelineData* data, Zone* temp_zone) {
GraphReducer graph_reducer(temp_zone, data->graph(),
data->jsgraph()->Dead());
...
AddReducer(data, &graph_reducer, &dead_code_elimination);
AddReducer(data, &graph_reducer, &create_lowering);
AddReducer(data, &graph_reducer, &constant_folding_reducer);
AddReducer(data, &graph_reducer, &typed_lowering);
AddReducer(data, &graph_reducer, &typed_optimization);
AddReducer(data, &graph_reducer, &simple_reducer);
AddReducer(data, &graph_reducer, &checkpoint_elimination);
AddReducer(data, &graph_reducer, &common_reducer);
graph_reducer.ReduceGraph();
}
};

AddReducer会将对应的reducer加入到reducers_中,reducers_是vector.

1
2
3
void GraphReducer::AddReducer(Reducer* reducer) {
reducers_.push_back(reducer);
}

Run的最后会执行graph_reducer.ReduceGraph()

ReducerGraph:

1
void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }

它以graph的End节点开始进行深度优先搜索.

ReduceNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void GraphReducer::ReduceNode(Node* node) {
DCHECK(stack_.empty());
DCHECK(revisit_.empty());
Push(node);//将node push 到 stack_中
for (;;) {
if (!stack_.empty()) { //stack_不为空,则进入该分支
// Process the node on the top of the stack, potentially pushing more or
// popping the node off the stack.
ReduceTop();
} else if (!revisit_.empty()) {//revisit_不为空,则进入该分支
// If the stack becomes empty, revisit any nodes in the revisit queue.
Node* const node = revisit_.front();
revisit_.pop();
if (state_.Get(node) == State::kRevisit) {
// state can change while in queue.
Push(node);
}
} else {
// Run all finalizers.
for (Reducer* const reducer : reducers_) reducer->Finalize();

// Check if we have new nodes to revisit.
if (revisit_.empty()) break;
}
}//for (;;)
DCHECK(revisit_.empty());
DCHECK(stack_.empty());
}

搜索的时候维护了两个栈: stack_,revisit_,revisit_中存放搜索完后需要重新访问的节点.
当stack_不为空的时候会进入以下分支:

1
2
3
4
5
if (!stack_.empty()) { //stack_不为空,则进入该分支
// Process the node on the top of the stack, potentially pushing more or
// popping the node off the stack.
ReduceTop();
} else if

ReduceTop这里开始进行深度优先搜索.
当搜索完后,stack_为空,如果revisit_不为空,则会进入以下分支:

1
2
3
4
5
6
7
8
9
else if (!revisit_.empty()) {//revisit_不为空,则进入该分支
// If the stack becomes empty, revisit any nodes in the revisit queue.
Node* const node = revisit_.front();
revisit_.pop();
if (state_.Get(node) == State::kRevisit) {
// state can change while in queue.
Push(node);
}
}

将需要重新访问的节点压入stack_中,这样stack_又不为空,就又会继续搜索.
当stack_和revisit_都为空时,会进行:

1
2
// Run all finalizers.
for (Reducer* const reducer : reducers_) reducer->Finalize();

ReduceTop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
void GraphReducer::ReduceTop() {
NodeState& entry = stack_.top();
Node* node = entry.node;//获取stack_顶部的node
DCHECK_EQ(State::kOnStack, state_.Get(node));

/*如果栈顶的这个节点是死节点(即该节点没有input节点),则直接将其pop掉,然后返回*/
if (node->IsDead()) return Pop(); // Node was killed while on stack.

Node::Inputs node_inputs = node->inputs();//以该node的input_location和input_count初始化Node::Inputs

// Recurse on an input if necessary.
int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
for (int i = start; i < node_inputs.count(); ++i) { //遍历该节点的input节点
Node* input = node_inputs[i];
if (input != node && Recurse(input)) { //如果该input节点没有访问过或没有在栈上,则将其压入栈中,然后返回
entry.input_index = i + 1; // 压入栈中后,input_index+1 ,下次再遍历的时候就不会再遍历它了.
return;
}
}
for (int i = 0; i < start; ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}

// Remember the max node id before reduction.
NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);

// 所有input节点都被访问过了或者在栈上。则对该节点进行reduce.
Reduction reduction = Reduce(node);//遍历所有的reducer对节点进行reduce

// If there was no reduction, pop {node} and continue.
// 没有对该节点进行reduce,则pop掉它
if (!reduction.Changed()) return Pop();

// Check if the reduction is an in-place update of the {node}.
Node* const replacement = reduction.replacement();
if (replacement == node) { //replacement == node 代表该node被更新过
// In-place update of {node}, may need to recurse on an input.
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;
}
}
}

// After reducing the node, pop it off the stack.
Pop();

// Check if we have a new replacement.
if (replacement != node) {
Replace(node, replacement, max_id);
} else {
// Revisit all uses of the node.
// 重新访问该节点的use节点,将其压入栈中.
for (Node* const user : node->uses()) {
// Don't revisit this node if it refers to itself.
if (user != node) Revisit(user);
}
}
}//ReduceTop

这里开始进行递归操作。对栈顶节点的input节点进行遍历,如果input节点没有被访问过或没有在栈上,则将其压入stack_中,然后函数返回.
如果栈顶节点的所有input节点都被访问过了则对栈顶节点进行reduce.

如果节点之间存在递归调用,例如:

这里n3节点作为n6节点的input节点,此时n3节点已经在栈上了,则这里return false,不会将n3再压入栈中.

1
2
3
4
5
6
bool GraphReducer::Recurse(Node* node) {
/* onStack, visited */
if (state_.Get(node) > State::kRevisit) return false;
Push(node);
return true;
}

当n7,n8,n9已经遍历完,遍历到n3的时候,发现n3已经在栈上,则一样可以对n6节点进行reduce.

当一个节点被成功reduce过后,会重新访问该节点的use节点(use节点就是接受该节点作为input节点的节点),即将use节点压入栈中.

图中,当reduce n3节点后,会重新把n6节点压入栈中.