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
OsrHelper(CompilationInfo * info)27 OsrHelper::OsrHelper(CompilationInfo* info)
28 : parameter_count_(
29 info->is_optimizing_from_bytecode()
30 ? info->shared_info()->bytecode_array()->parameter_count()
31 : info->scope()->num_parameters()),
32 stack_slot_count_(
33 info->is_optimizing_from_bytecode()
34 ? info->shared_info()->bytecode_array()->register_count() +
35 InterpreterFrameConstants::kExtraSlotCount
36 : info->scope()->num_stack_slots() +
37 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.
PeelOuterLoopsForOsr(Graph * graph,CommonOperatorBuilder * common,Zone * tmp_zone,Node * dead,LoopTree * loop_tree,LoopTree::Loop * osr_loop,Node * osr_normal_entry,Node * osr_loop_entry)54 void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
55 Zone* tmp_zone, Node* dead, LoopTree* loop_tree,
56 LoopTree::Loop* osr_loop, Node* osr_normal_entry,
57 Node* osr_loop_entry) {
58 const size_t original_count = graph->NodeCount();
59 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 for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
66 void* stuff = tmp_zone->New(sizeof(NodeVector));
67 NodeVector* mapping =
68 new (stuff) NodeVector(original_count, sentinel, tmp_zone);
69 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 mapping->at(osr_normal_entry->id()) = dead;
76 mapping->at(osr_loop_entry->id()) = dead;
77
78 // The outer loops are dead in this copy.
79 for (LoopTree::Loop* outer = loop->parent(); outer;
80 outer = outer->parent()) {
81 for (Node* node : loop_tree->HeaderNodes(outer)) {
82 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 for (size_t i = 0; i < all.reachable.size(); i++) {
90 Node* orig = all.reachable[i];
91 Node* copy = mapping->at(orig->id());
92 if (copy != sentinel) {
93 // Mapping already exists.
94 continue;
95 }
96 if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
97 orig->opcode() == IrOpcode::kOsrValue ||
98 orig->opcode() == IrOpcode::kOsrGuard) {
99 // No need to copy leaf nodes or parameters.
100 mapping->at(orig->id()) = orig;
101 continue;
102 }
103
104 // Copy the node.
105 tmp_inputs.clear();
106 for (Node* input : orig->inputs()) {
107 tmp_inputs.push_back(mapping->at(input->id()));
108 }
109 copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
110 if (NodeProperties::IsTyped(orig)) {
111 NodeProperties::SetType(copy, NodeProperties::GetType(orig));
112 }
113 mapping->at(orig->id()) = copy;
114 TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
115 copy->id());
116 }
117
118 // Fix missing inputs.
119 for (Node* orig : all.reachable) {
120 Node* copy = mapping->at(orig->id());
121 for (int j = 0; j < copy->InputCount(); j++) {
122 if (copy->InputAt(j) == sentinel) {
123 copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
124 }
125 }
126 }
127
128 // Construct the entry into this loop from previous copies.
129
130 // Gather the live loop header nodes, {loop_header} first.
131 Node* loop_header = loop_tree->HeaderNode(loop);
132 NodeVector header_nodes(tmp_zone);
133 header_nodes.reserve(loop->HeaderSize());
134 header_nodes.push_back(loop_header); // put the loop header first.
135 for (Node* node : loop_tree->HeaderNodes(loop)) {
136 if (node != loop_header && all.IsLive(node)) {
137 header_nodes.push_back(node);
138 }
139 }
140
141 // Gather backedges from the previous copies of the inner loops of {loop}.
142 NodeVectorVector backedges(tmp_zone);
143 TRACE("Gathering backedges...\n");
144 for (int i = 1; i < loop_header->InputCount(); i++) {
145 if (TRACE_COND) {
146 Node* control = loop_header->InputAt(i);
147 size_t incoming_depth = 0;
148 for (int j = 0; j < control->op()->ControlInputCount(); j++) {
149 Node* k = NodeProperties::GetControlInput(control, j);
150 incoming_depth =
151 std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
152 }
153
154 TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
155 control->op()->mnemonic(), incoming_depth);
156 }
157
158 for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
159 backedges.push_back(NodeVector(tmp_zone));
160 backedges.back().reserve(header_nodes.size());
161
162 NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
163
164 for (Node* node : header_nodes) {
165 Node* input = node->InputAt(i);
166 if (previous_map) input = previous_map->at(input->id());
167 backedges.back().push_back(input);
168 TRACE(" node #%d:%s(@%d) = #%d:%s\n", node->id(),
169 node->op()->mnemonic(), i, input->id(),
170 input->op()->mnemonic());
171 }
172 }
173 }
174
175 int backedge_count = static_cast<int>(backedges.size());
176 if (backedge_count == 1) {
177 // Simple case of single backedge, therefore a single entry.
178 int index = 0;
179 for (Node* node : header_nodes) {
180 Node* copy = mapping->at(node->id());
181 Node* input = backedges[0][index];
182 copy->ReplaceInput(0, input);
183 TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
184 copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
185 index++;
186 }
187 } else {
188 // Complex case of multiple backedges from previous copies requires
189 // merging the backedges to create the entry into the loop header.
190 Node* merge = nullptr;
191 int index = 0;
192 for (Node* node : header_nodes) {
193 // Gather edge inputs into {tmp_inputs}.
194 tmp_inputs.clear();
195 for (int edge = 0; edge < backedge_count; edge++) {
196 tmp_inputs.push_back(backedges[edge][index]);
197 }
198 Node* copy = mapping->at(node->id());
199 Node* input;
200 if (node == loop_header) {
201 // Create the merge for the entry into the loop header.
202 input = merge = graph->NewNode(common->Merge(backedge_count),
203 backedge_count, &tmp_inputs[0]);
204 copy->ReplaceInput(0, merge);
205 } else {
206 // Create a phi that merges values at entry into the loop header.
207 DCHECK_NOT_NULL(merge);
208 DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
209 tmp_inputs.push_back(merge);
210 Node* phi = input = graph->NewNode(
211 common->ResizeMergeOrPhi(node->op(), backedge_count),
212 backedge_count + 1, &tmp_inputs[0]);
213 copy->ReplaceInput(0, phi);
214 }
215
216 // Print the merge.
217 if (TRACE_COND) {
218 TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
219 copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
220 for (size_t i = 0; i < tmp_inputs.size(); i++) {
221 if (i > 0) TRACE(", ");
222 Node* input = tmp_inputs[i];
223 TRACE("#%d:%s", input->id(), input->op()->mnemonic());
224 }
225 TRACE(")\n");
226 }
227
228 index++;
229 }
230 }
231 }
232
233 // Kill the outer loops in the original graph.
234 TRACE("Killing outer loop headers...\n");
235 for (LoopTree::Loop* outer = osr_loop->parent(); outer;
236 outer = outer->parent()) {
237 Node* loop_header = loop_tree->HeaderNode(outer);
238 loop_header->ReplaceUses(dead);
239 TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
240 }
241
242 // Merge the ends of the graph copies.
243 Node* const end = graph->end();
244 int const input_count = end->InputCount();
245 for (int i = 0; i < input_count; ++i) {
246 NodeId const id = end->InputAt(i)->id();
247 for (NodeVector* const copy : copies) {
248 end->AppendInput(graph->zone(), copy->at(id));
249 NodeProperties::ChangeOp(end, common->End(end->InputCount()));
250 }
251 }
252
253 if (FLAG_trace_turbo_graph) { // Simple textual RPO.
254 OFStream os(stdout);
255 os << "-- Graph after OSR duplication -- " << std::endl;
256 os << AsRPO(*graph);
257 }
258 }
259
SetTypeForOsrValue(Node * osr_value,Node * loop,CommonOperatorBuilder * common)260 void SetTypeForOsrValue(Node* osr_value, Node* loop,
261 CommonOperatorBuilder* common) {
262 Node* osr_guard = nullptr;
263 for (Node* use : osr_value->uses()) {
264 if (use->opcode() == IrOpcode::kOsrGuard) {
265 DCHECK_EQ(use->InputAt(0), osr_value);
266 osr_guard = use;
267 break;
268 }
269 }
270
271 OsrGuardType guard_type = OsrGuardType::kAny;
272 // Find the phi that uses the OsrGuard node and get the type from
273 // there. Skip the search if the OsrGuard does not have value use
274 // (i.e., if there is other use beyond the effect use).
275 if (OsrGuardTypeOf(osr_guard->op()) == OsrGuardType::kUninitialized &&
276 osr_guard->UseCount() > 1) {
277 Type* type = nullptr;
278 for (Node* use : osr_guard->uses()) {
279 if (use->opcode() == IrOpcode::kPhi) {
280 if (NodeProperties::GetControlInput(use) != loop) continue;
281 CHECK_NULL(type);
282 type = NodeProperties::GetType(use);
283 }
284 }
285 CHECK_NOT_NULL(type);
286
287 if (type->Is(Type::SignedSmall())) {
288 guard_type = OsrGuardType::kSignedSmall;
289 }
290 }
291
292 NodeProperties::ChangeOp(osr_guard, common->OsrGuard(guard_type));
293 }
294
295 } // namespace
296
Deconstruct(JSGraph * jsgraph,CommonOperatorBuilder * common,Zone * tmp_zone)297 void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
298 Zone* tmp_zone) {
299 Graph* graph = jsgraph->graph();
300 Node* osr_normal_entry = nullptr;
301 Node* osr_loop_entry = nullptr;
302 Node* osr_loop = nullptr;
303
304 for (Node* node : graph->start()->uses()) {
305 if (node->opcode() == IrOpcode::kOsrLoopEntry) {
306 osr_loop_entry = node; // found the OSR loop entry
307 } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
308 osr_normal_entry = node;
309 }
310 }
311
312 CHECK_NOT_NULL(osr_normal_entry); // Should have found the OSR normal entry.
313 CHECK_NOT_NULL(osr_loop_entry); // Should have found the OSR loop entry.
314
315 for (Node* use : osr_loop_entry->uses()) {
316 if (use->opcode() == IrOpcode::kLoop) {
317 CHECK(!osr_loop); // should be only one OSR loop.
318 osr_loop = use; // found the OSR loop.
319 }
320 }
321
322 CHECK(osr_loop); // Should have found the OSR loop.
323
324 for (Node* use : osr_loop_entry->uses()) {
325 if (use->opcode() == IrOpcode::kOsrValue) {
326 SetTypeForOsrValue(use, osr_loop, common);
327 }
328 }
329
330 // Analyze the graph to determine how deeply nested the OSR loop is.
331 LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
332
333 Node* dead = jsgraph->Dead();
334 LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
335 if (loop->depth() > 0) {
336 PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
337 osr_normal_entry, osr_loop_entry);
338 }
339
340 // Replace the normal entry with {Dead} and the loop entry with {Start}
341 // and run the control reducer to clean up the graph.
342 osr_normal_entry->ReplaceUses(dead);
343 osr_normal_entry->Kill();
344 osr_loop_entry->ReplaceUses(graph->start());
345 osr_loop_entry->Kill();
346
347 // Remove the first input to the {osr_loop}.
348 int const live_input_count = osr_loop->InputCount() - 1;
349 CHECK_NE(0, live_input_count);
350 for (Node* const use : osr_loop->uses()) {
351 if (NodeProperties::IsPhi(use)) {
352 use->RemoveInput(0);
353 NodeProperties::ChangeOp(
354 use, common->ResizeMergeOrPhi(use->op(), live_input_count));
355 }
356 }
357 osr_loop->RemoveInput(0);
358 NodeProperties::ChangeOp(
359 osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
360
361 // Run control reduction and graph trimming.
362 // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
363 // nice together with the rest, instead of having this custom stuff here.
364 GraphReducer graph_reducer(tmp_zone, graph);
365 DeadCodeElimination dce(&graph_reducer, graph, common);
366 CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
367 graph_reducer.AddReducer(&dce);
368 graph_reducer.AddReducer(&cor);
369 graph_reducer.ReduceGraph();
370 GraphTrimmer trimmer(tmp_zone, graph);
371 NodeVector roots(tmp_zone);
372 jsgraph->GetCachedNodes(&roots);
373 trimmer.TrimGraph(roots.begin(), roots.end());
374 }
375
376
SetupFrame(Frame * frame)377 void OsrHelper::SetupFrame(Frame* frame) {
378 // The optimized frame will subsume the unoptimized frame. Do so by reserving
379 // the first spill slots.
380 frame->ReserveSpillSlots(UnoptimizedFrameSlots());
381 }
382
383 } // namespace compiler
384 } // namespace internal
385 } // namespace v8
386