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 17682 : OsrHelper::OsrHelper(CompilationInfo* info)
28 : : parameter_count_(
29 : info->is_optimizing_from_bytecode()
30 51966 : ? info->shared_info()->bytecode_array()->parameter_count()
31 216 : : info->scope()->num_parameters()),
32 : stack_slot_count_(
33 : info->is_optimizing_from_bytecode()
34 69216 : ? info->shared_info()->bytecode_array()->register_count() +
35 : InterpreterFrameConstants::kExtraSlotCount
36 432 : : info->scope()->num_stack_slots() +
37 87762 : 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 690772 : for (size_t i = 0; i < all.reachable.size(); i++) {
90 1253399 : Node* orig = all.reachable[i];
91 689446 : Node* copy = mapping->at(orig->id());
92 344723 : if (copy != sentinel) {
93 : // Mapping already exists.
94 : continue;
95 : }
96 662247 : if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
97 644688 : orig->opcode() == IrOpcode::kOsrValue ||
98 : orig->opcode() == IrOpcode::kOsrGuard) {
99 : // No need to copy leaf nodes or parameters.
100 46327 : mapping->at(orig->id()) = orig;
101 46327 : continue;
102 : }
103 :
104 : // Copy the node.
105 : tmp_inputs.clear();
106 2211756 : for (Node* input : orig->inputs()) {
107 1919000 : tmp_inputs.push_back(mapping->at(input->id()));
108 : }
109 585512 : copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
110 585512 : 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 690772 : for (Node* orig : all.reachable) {
117 689446 : Node* copy = mapping->at(orig->id());
118 2720658 : for (int j = 0; j < copy->InputCount(); j++) {
119 1015606 : if (copy->InputAt(j) == sentinel) {
120 1338723 : 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 11200 : for (Node* node : loop_tree->HeaderNodes(loop)) {
133 9874 : if (node != loop_header && all.IsLive(node)) {
134 8548 : 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 16374 : for (Node* node : header_nodes) {
162 12862 : Node* input = node->InputAt(i);
163 18838 : if (previous_map) input = previous_map->at(input->id());
164 12862 : 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 8870 : for (Node* node : header_nodes) {
177 14060 : Node* copy = mapping->at(node->id());
178 14060 : Node* input = backedges[0][index];
179 7030 : 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 7030 : 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 55013 : void SetTypeForOsrValue(Node* osr_value, Node* loop,
258 : CommonOperatorBuilder* common) {
259 : Node* osr_guard = nullptr;
260 110026 : for (Node* use : osr_value->uses()) {
261 55013 : if (use->opcode() == IrOpcode::kOsrGuard) {
262 : DCHECK_EQ(use->InputAt(0), osr_value);
263 : osr_guard = use;
264 : break;
265 : }
266 : }
267 :
268 55013 : NodeProperties::ChangeOp(osr_guard, common->OsrGuard(OsrGuardType::kAny));
269 55013 : }
270 :
271 : } // namespace
272 :
273 11644 : void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
274 : Zone* tmp_zone) {
275 11644 : Graph* graph = jsgraph->graph();
276 : Node* osr_normal_entry = nullptr;
277 : Node* osr_loop_entry = nullptr;
278 5822 : Node* osr_loop = nullptr;
279 :
280 438372 : for (Node* node : graph->start()->uses()) {
281 216275 : if (node->opcode() == IrOpcode::kOsrLoopEntry) {
282 : osr_loop_entry = node; // found the OSR loop entry
283 204631 : } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
284 : osr_normal_entry = node;
285 : }
286 : }
287 :
288 5822 : CHECK_NOT_NULL(osr_normal_entry); // Should have found the OSR normal entry.
289 5822 : CHECK_NOT_NULL(osr_loop_entry); // Should have found the OSR loop entry.
290 :
291 260806 : for (Node* use : osr_loop_entry->uses()) {
292 127492 : if (use->opcode() == IrOpcode::kLoop) {
293 5822 : CHECK(!osr_loop); // should be only one OSR loop.
294 : osr_loop = use; // found the OSR loop.
295 : }
296 : }
297 :
298 5822 : CHECK(osr_loop); // Should have found the OSR loop.
299 :
300 315819 : for (Node* use : osr_loop_entry->uses()) {
301 127492 : if (use->opcode() == IrOpcode::kOsrValue) {
302 55013 : SetTypeForOsrValue(use, osr_loop, common);
303 : }
304 : }
305 :
306 : // Analyze the graph to determine how deeply nested the OSR loop is.
307 5822 : LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
308 :
309 5822 : Node* dead = jsgraph->Dead();
310 5822 : LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
311 5822 : 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 5822 : osr_normal_entry->ReplaceUses(dead);
319 5822 : osr_normal_entry->Kill();
320 5822 : osr_loop_entry->ReplaceUses(graph->start());
321 5822 : osr_loop_entry->Kill();
322 :
323 : // Remove the first input to the {osr_loop}.
324 5822 : int const live_input_count = osr_loop->InputCount() - 1;
325 5822 : CHECK_NE(0, live_input_count);
326 103213 : for (Node* const use : osr_loop->uses()) {
327 63422 : if (NodeProperties::IsPhi(use)) {
328 33969 : use->RemoveInput(0);
329 : NodeProperties::ChangeOp(
330 33969 : use, common->ResizeMergeOrPhi(use->op(), live_input_count));
331 : }
332 : }
333 5822 : osr_loop->RemoveInput(0);
334 : NodeProperties::ChangeOp(
335 5822 : 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 5822 : GraphReducer graph_reducer(tmp_zone, graph);
341 5822 : DeadCodeElimination dce(&graph_reducer, graph, common);
342 5822 : CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
343 5822 : graph_reducer.AddReducer(&dce);
344 5822 : graph_reducer.AddReducer(&cor);
345 5822 : graph_reducer.ReduceGraph();
346 11644 : GraphTrimmer trimmer(tmp_zone, graph);
347 : NodeVector roots(tmp_zone);
348 5822 : jsgraph->GetCachedNodes(&roots);
349 11644 : trimmer.TrimGraph(roots.begin(), roots.end());
350 5822 : }
351 :
352 :
353 5822 : 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 5822 : }
358 :
359 : } // namespace compiler
360 : } // namespace internal
361 : } // namespace v8
|
