Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/compiler/osr.h"
6 : #include "src/ast/scopes.h"
7 : #include "src/compilation-info.h"
8 : #include "src/compiler/all-nodes.h"
9 : #include "src/compiler/common-operator-reducer.h"
10 : #include "src/compiler/common-operator.h"
11 : #include "src/compiler/dead-code-elimination.h"
12 : #include "src/compiler/frame.h"
13 : #include "src/compiler/graph-reducer.h"
14 : #include "src/compiler/graph-trimmer.h"
15 : #include "src/compiler/graph-visualizer.h"
16 : #include "src/compiler/graph.h"
17 : #include "src/compiler/js-graph.h"
18 : #include "src/compiler/loop-analysis.h"
19 : #include "src/compiler/node-marker.h"
20 : #include "src/compiler/node.h"
21 : #include "src/objects-inl.h"
22 :
23 : namespace v8 {
24 : namespace internal {
25 : namespace compiler {
26 :
27 17643 : OsrHelper::OsrHelper(CompilationInfo* info)
28 : : parameter_count_(
29 : info->is_optimizing_from_bytecode()
30 51909 : ? info->shared_info()->bytecode_array()->parameter_count()
31 204 : : info->scope()->num_parameters()),
32 : stack_slot_count_(
33 : info->is_optimizing_from_bytecode()
34 69144 : ? info->shared_info()->bytecode_array()->register_count() +
35 : InterpreterFrameConstants::kExtraSlotCount
36 408 : : info->scope()->num_stack_slots() +
37 87603 : info->osr_expr_stack_height()) {}
38 :
39 : #ifdef DEBUG
40 : #define TRACE_COND (FLAG_trace_turbo_graph && FLAG_trace_osr)
41 : #else
42 : #define TRACE_COND false
43 : #endif
44 :
45 : #define TRACE(...) \
46 : do { \
47 : if (TRACE_COND) PrintF(__VA_ARGS__); \
48 : } while (false)
49 :
50 : namespace {
51 :
52 : // Peel outer loops and rewire the graph so that control reduction can
53 : // produce a properly formed graph.
54 9889 : void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
55 920 : Zone* tmp_zone, Node* dead, LoopTree* loop_tree,
56 3166 : LoopTree::Loop* osr_loop, Node* osr_normal_entry,
57 1326 : Node* osr_loop_entry) {
58 : const size_t original_count = graph->NodeCount();
59 920 : AllNodes all(tmp_zone, graph);
60 : NodeVector tmp_inputs(tmp_zone);
61 : Node* sentinel = graph->NewNode(dead->op());
62 :
63 : // Make a copy of the graph for each outer loop.
64 : ZoneVector<NodeVector*> copies(tmp_zone);
65 6224 : for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
66 1326 : void* stuff = tmp_zone->New(sizeof(NodeVector));
67 : NodeVector* mapping =
68 2652 : new (stuff) NodeVector(original_count, sentinel, tmp_zone);
69 1326 : copies.push_back(mapping);
70 : TRACE("OsrDuplication #%zu, depth %zu, header #%d:%s\n", copies.size(),
71 : loop->depth(), loop_tree->HeaderNode(loop)->id(),
72 : loop_tree->HeaderNode(loop)->op()->mnemonic());
73 :
74 : // Prepare the mapping for OSR values and the OSR loop entry.
75 2652 : mapping->at(osr_normal_entry->id()) = dead;
76 2652 : mapping->at(osr_loop_entry->id()) = dead;
77 :
78 : // The outer loops are dead in this copy.
79 1756 : for (LoopTree::Loop* outer = loop->parent(); outer;
80 : outer = outer->parent()) {
81 3418 : for (Node* node : loop_tree->HeaderNodes(outer)) {
82 5976 : mapping->at(node->id()) = dead;
83 : TRACE(" ---- #%d:%s -> dead (header)\n", node->id(),
84 : node->op()->mnemonic());
85 : }
86 : }
87 :
88 : // Copy all nodes.
89 691356 : for (size_t i = 0; i < all.reachable.size(); i++) {
90 1254483 : Node* orig = all.reachable[i];
91 690030 : Node* copy = mapping->at(orig->id());
92 345015 : if (copy != sentinel) {
93 : // Mapping already exists.
94 : continue;
95 : }
96 662823 : if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
97 645250 : orig->opcode() == IrOpcode::kOsrValue ||
98 : orig->opcode() == IrOpcode::kOsrGuard) {
99 : // No need to copy leaf nodes or parameters.
100 46365 : mapping->at(orig->id()) = orig;
101 46365 : continue;
102 : }
103 :
104 : // Copy the node.
105 : tmp_inputs.clear();
106 2214240 : for (Node* input : orig->inputs()) {
107 1921230 : tmp_inputs.push_back(mapping->at(input->id()));
108 : }
109 586020 : copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
110 586020 : mapping->at(orig->id()) = copy;
111 : TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
112 : copy->id());
113 : }
114 :
115 : // Fix missing inputs.
116 691356 : for (Node* orig : all.reachable) {
117 690030 : Node* copy = mapping->at(orig->id());
118 2723596 : for (int j = 0; j < copy->InputCount(); j++) {
119 1016783 : if (copy->InputAt(j) == sentinel) {
120 1339866 : copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
121 : }
122 : }
123 : }
124 :
125 : // Construct the entry into this loop from previous copies.
126 :
127 : // Gather the live loop header nodes, {loop_header} first.
128 1326 : Node* loop_header = loop_tree->HeaderNode(loop);
129 : NodeVector header_nodes(tmp_zone);
130 1326 : header_nodes.reserve(loop->HeaderSize());
131 1326 : header_nodes.push_back(loop_header); // put the loop header first.
132 11214 : for (Node* node : loop_tree->HeaderNodes(loop)) {
133 9888 : if (node != loop_header && all.IsLive(node)) {
134 8562 : header_nodes.push_back(node);
135 : }
136 : }
137 :
138 : // Gather backedges from the previous copies of the inner loops of {loop}.
139 : NodeVectorVector backedges(tmp_zone);
140 : TRACE("Gathering backedges...\n");
141 5304 : for (int i = 1; i < loop_header->InputCount(); i++) {
142 : if (TRACE_COND) {
143 : Node* control = loop_header->InputAt(i);
144 : size_t incoming_depth = 0;
145 : for (int j = 0; j < control->op()->ControlInputCount(); j++) {
146 : Node* k = NodeProperties::GetControlInput(control, j);
147 : incoming_depth =
148 : std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
149 : }
150 :
151 : TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
152 : control->op()->mnemonic(), incoming_depth);
153 : }
154 :
155 4408 : for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
156 1756 : backedges.push_back(NodeVector(tmp_zone));
157 3512 : backedges.back().reserve(header_nodes.size());
158 :
159 2186 : NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
160 :
161 16388 : for (Node* node : header_nodes) {
162 12876 : Node* input = node->InputAt(i);
163 18852 : if (previous_map) input = previous_map->at(input->id());
164 12876 : backedges.back().push_back(input);
165 : TRACE(" node #%d:%s(@%d) = #%d:%s\n", node->id(),
166 : node->op()->mnemonic(), i, input->id(),
167 : input->op()->mnemonic());
168 : }
169 : }
170 : }
171 :
172 2652 : int backedge_count = static_cast<int>(backedges.size());
173 1326 : if (backedge_count == 1) {
174 : // Simple case of single backedge, therefore a single entry.
175 : int index = 0;
176 8884 : for (Node* node : header_nodes) {
177 14088 : Node* copy = mapping->at(node->id());
178 14088 : Node* input = backedges[0][index];
179 7044 : copy->ReplaceInput(0, input);
180 : TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
181 : copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
182 7044 : index++;
183 : }
184 : } else {
185 : // Complex case of multiple backedges from previous copies requires
186 : // merging the backedges to create the entry into the loop header.
187 406 : Node* merge = nullptr;
188 : int index = 0;
189 8938 : for (Node* node : header_nodes) {
190 : // Gather edge inputs into {tmp_inputs}.
191 : tmp_inputs.clear();
192 8676 : for (int edge = 0; edge < backedge_count; edge++) {
193 17496 : tmp_inputs.push_back(backedges[edge][index]);
194 : }
195 5688 : Node* copy = mapping->at(node->id());
196 : Node* input;
197 2844 : if (node == loop_header) {
198 : // Create the merge for the entry into the loop header.
199 : input = merge = graph->NewNode(common->Merge(backedge_count),
200 406 : backedge_count, &tmp_inputs[0]);
201 406 : copy->ReplaceInput(0, merge);
202 : } else {
203 : // Create a phi that merges values at entry into the loop header.
204 : DCHECK_NOT_NULL(merge);
205 : DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
206 2438 : tmp_inputs.push_back(merge);
207 : Node* phi = input = graph->NewNode(
208 : common->ResizeMergeOrPhi(node->op(), backedge_count),
209 4876 : backedge_count + 1, &tmp_inputs[0]);
210 2438 : copy->ReplaceInput(0, phi);
211 : }
212 :
213 : // Print the merge.
214 : if (TRACE_COND) {
215 : TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
216 : copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
217 : for (size_t i = 0; i < tmp_inputs.size(); i++) {
218 : if (i > 0) TRACE(", ");
219 : Node* input = tmp_inputs[i];
220 : TRACE("#%d:%s", input->id(), input->op()->mnemonic());
221 : }
222 : TRACE(")\n");
223 : }
224 :
225 2844 : index++;
226 : }
227 : }
228 : }
229 :
230 : // Kill the outer loops in the original graph.
231 : TRACE("Killing outer loop headers...\n");
232 2246 : for (LoopTree::Loop* outer = osr_loop->parent(); outer;
233 : outer = outer->parent()) {
234 1326 : Node* loop_header = loop_tree->HeaderNode(outer);
235 1326 : loop_header->ReplaceUses(dead);
236 : TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
237 : }
238 :
239 : // Merge the ends of the graph copies.
240 : Node* const end = graph->end();
241 : int const input_count = end->InputCount();
242 6026 : for (int i = 0; i < input_count; ++i) {
243 5106 : NodeId const id = end->InputAt(i)->id();
244 18261 : for (NodeVector* const copy : copies) {
245 24147 : end->AppendInput(graph->zone(), copy->at(id));
246 8049 : NodeProperties::ChangeOp(end, common->End(end->InputCount()));
247 : }
248 : }
249 :
250 920 : if (FLAG_trace_turbo_graph) { // Simple textual RPO.
251 0 : OFStream os(stdout);
252 0 : os << "-- Graph after OSR duplication -- " << std::endl;
253 0 : os << AsRPO(*graph);
254 : }
255 920 : }
256 :
257 54757 : void SetTypeForOsrValue(Node* osr_value, Node* loop,
258 : CommonOperatorBuilder* common) {
259 : Node* osr_guard = nullptr;
260 109514 : for (Node* use : osr_value->uses()) {
261 54757 : if (use->opcode() == IrOpcode::kOsrGuard) {
262 : DCHECK_EQ(use->InputAt(0), osr_value);
263 : osr_guard = use;
264 : break;
265 : }
266 : }
267 :
268 54757 : NodeProperties::ChangeOp(osr_guard, common->OsrGuard(OsrGuardType::kAny));
269 54757 : }
270 :
271 : } // namespace
272 :
273 11626 : void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
274 : Zone* tmp_zone) {
275 11626 : Graph* graph = jsgraph->graph();
276 : Node* osr_normal_entry = nullptr;
277 : Node* osr_loop_entry = nullptr;
278 5813 : Node* osr_loop = nullptr;
279 :
280 435731 : for (Node* node : graph->start()->uses()) {
281 214959 : if (node->opcode() == IrOpcode::kOsrLoopEntry) {
282 : osr_loop_entry = node; // found the OSR loop entry
283 203333 : } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
284 : osr_normal_entry = node;
285 : }
286 : }
287 :
288 5813 : CHECK_NOT_NULL(osr_normal_entry); // Should have found the OSR normal entry.
289 5813 : CHECK_NOT_NULL(osr_loop_entry); // Should have found the OSR loop entry.
290 :
291 259719 : for (Node* use : osr_loop_entry->uses()) {
292 126953 : if (use->opcode() == IrOpcode::kLoop) {
293 5813 : CHECK(!osr_loop); // should be only one OSR loop.
294 : osr_loop = use; // found the OSR loop.
295 : }
296 : }
297 :
298 5813 : CHECK(osr_loop); // Should have found the OSR loop.
299 :
300 314476 : for (Node* use : osr_loop_entry->uses()) {
301 126953 : if (use->opcode() == IrOpcode::kOsrValue) {
302 54757 : SetTypeForOsrValue(use, osr_loop, common);
303 : }
304 : }
305 :
306 : // Analyze the graph to determine how deeply nested the OSR loop is.
307 5813 : LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
308 :
309 5813 : Node* dead = jsgraph->Dead();
310 5813 : LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
311 5813 : if (loop->depth() > 0) {
312 : PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
313 920 : osr_normal_entry, osr_loop_entry);
314 : }
315 :
316 : // Replace the normal entry with {Dead} and the loop entry with {Start}
317 : // and run the control reducer to clean up the graph.
318 5813 : osr_normal_entry->ReplaceUses(dead);
319 5813 : osr_normal_entry->Kill();
320 5813 : osr_loop_entry->ReplaceUses(graph->start());
321 5813 : osr_loop_entry->Kill();
322 :
323 : // Remove the first input to the {osr_loop}.
324 5813 : int const live_input_count = osr_loop->InputCount() - 1;
325 5813 : CHECK_NE(0, live_input_count);
326 102869 : for (Node* const use : osr_loop->uses()) {
327 63176 : if (NodeProperties::IsPhi(use)) {
328 33880 : use->RemoveInput(0);
329 : NodeProperties::ChangeOp(
330 33880 : use, common->ResizeMergeOrPhi(use->op(), live_input_count));
331 : }
332 : }
333 5813 : osr_loop->RemoveInput(0);
334 : NodeProperties::ChangeOp(
335 5813 : osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
336 :
337 : // Run control reduction and graph trimming.
338 : // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
339 : // nice together with the rest, instead of having this custom stuff here.
340 5813 : GraphReducer graph_reducer(tmp_zone, graph);
341 5813 : DeadCodeElimination dce(&graph_reducer, graph, common);
342 5813 : CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
343 5813 : graph_reducer.AddReducer(&dce);
344 5813 : graph_reducer.AddReducer(&cor);
345 5813 : graph_reducer.ReduceGraph();
346 11626 : GraphTrimmer trimmer(tmp_zone, graph);
347 : NodeVector roots(tmp_zone);
348 5813 : jsgraph->GetCachedNodes(&roots);
349 11626 : trimmer.TrimGraph(roots.begin(), roots.end());
350 5813 : }
351 :
352 :
353 5813 : void OsrHelper::SetupFrame(Frame* frame) {
354 : // The optimized frame will subsume the unoptimized frame. Do so by reserving
355 : // the first spill slots.
356 : frame->ReserveSpillSlots(UnoptimizedFrameSlots());
357 5813 : }
358 :
359 : } // namespace compiler
360 : } // namespace internal
361 : } // namespace v8
|
