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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/compiler/linear-scheduler.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/zone/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
LinearScheduler::LinearScheduler(Zone* zone, Graph* graph)
: graph_(graph), control_level_(zone), early_schedule_position_(zone) {
ComputeControlLevel();
}
void LinearScheduler::ComputeControlLevel() {
Node* start = graph_->start();
SetControlLevel(start, 0);
// Do BFS from the start node and compute the level of
// each control node.
std::queue<Node*> queue({start});
while (!queue.empty()) {
Node* node = queue.front();
int level = GetControlLevel(node);
queue.pop();
for (Edge const edge : node->use_edges()) {
if (!NodeProperties::IsControlEdge(edge)) continue;
Node* use = edge.from();
if (control_level_.find(use) == control_level_.end() &&
use->opcode() != IrOpcode::kEnd) {
SetControlLevel(use, level + 1);
queue.push(use);
}
}
}
}
Node* LinearScheduler::GetEarlySchedulePosition(Node* node) {
DCHECK(!NodeProperties::IsControl(node));
auto it = early_schedule_position_.find(node);
if (it != early_schedule_position_.end()) return it->second;
std::stack<NodeState> stack;
stack.push({node, nullptr, 0});
Node* early_schedule_position = nullptr;
while (!stack.empty()) {
NodeState& top = stack.top();
if (NodeProperties::IsPhi(top.node)) {
// For phi node, the early schedule position is its control node.
early_schedule_position = NodeProperties::GetControlInput(top.node);
} else if (top.node->InputCount() == 0) {
// For node without inputs, the early schedule position is start node.
early_schedule_position = graph_->start();
} else {
// For others, the early schedule position is one of its inputs' early
// schedule position with maximal level.
if (top.input_index == top.node->InputCount()) {
// All inputs are visited, set early schedule position.
early_schedule_position = top.early_schedule_position;
} else {
// Visit top's input and find its early schedule position.
Node* input = top.node->InputAt(top.input_index);
Node* input_early_schedule_position = nullptr;
if (NodeProperties::IsControl(input)) {
input_early_schedule_position = input;
} else {
auto it = early_schedule_position_.find(input);
if (it != early_schedule_position_.end())
input_early_schedule_position = it->second;
}
if (input_early_schedule_position != nullptr) {
if (top.early_schedule_position == nullptr ||
GetControlLevel(top.early_schedule_position) <
GetControlLevel(input_early_schedule_position)) {
top.early_schedule_position = input_early_schedule_position;
}
top.input_index += 1;
} else {
top.input_index += 1;
stack.push({input, nullptr, 0});
}
continue;
}
}
// Found top's early schedule position, set it to the cache and pop it out
// of the stack.
SetEarlySchedulePosition(top.node, early_schedule_position);
stack.pop();
// Update early schedule position of top's use.
if (!stack.empty()) {
NodeState& use = stack.top();
if (use.early_schedule_position == nullptr ||
GetControlLevel(use.early_schedule_position) <
GetControlLevel(early_schedule_position)) {
use.early_schedule_position = early_schedule_position;
}
}
}
DCHECK(early_schedule_position != nullptr);
return early_schedule_position;
}
bool LinearScheduler::SameBasicBlock(Node* node0, Node* node1) {
Node* early_schedule_position0 = NodeProperties::IsControl(node0)
? node0
: GetEarlySchedulePosition(node0);
Node* early_schedule_position1 = NodeProperties::IsControl(node1)
? node1
: GetEarlySchedulePosition(node1);
return early_schedule_position0 == early_schedule_position1;
}
} // namespace compiler
} // namespace internal
} // namespace v8
|
