OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler.h" | 5 #include "src/compiler.h" |
| 6 #include "src/compiler/all-nodes.h" |
6 #include "src/compiler/common-operator.h" | 7 #include "src/compiler/common-operator.h" |
7 #include "src/compiler/control-reducer.h" | 8 #include "src/compiler/control-reducer.h" |
8 #include "src/compiler/frame.h" | 9 #include "src/compiler/frame.h" |
9 #include "src/compiler/graph.h" | 10 #include "src/compiler/graph.h" |
| 11 #include "src/compiler/graph-visualizer.h" |
10 #include "src/compiler/js-graph.h" | 12 #include "src/compiler/js-graph.h" |
11 #include "src/compiler/loop-analysis.h" | 13 #include "src/compiler/loop-analysis.h" |
12 #include "src/compiler/node.h" | 14 #include "src/compiler/node.h" |
13 #include "src/compiler/node-marker.h" | 15 #include "src/compiler/node-marker.h" |
14 #include "src/compiler/osr.h" | 16 #include "src/compiler/osr.h" |
15 #include "src/scopes.h" | 17 #include "src/scopes.h" |
16 | 18 |
17 namespace v8 { | 19 namespace v8 { |
18 namespace internal { | 20 namespace internal { |
19 namespace compiler { | 21 namespace compiler { |
20 | 22 |
21 OsrHelper::OsrHelper(CompilationInfo* info) | 23 OsrHelper::OsrHelper(CompilationInfo* info) |
22 : parameter_count_(info->scope()->num_parameters()), | 24 : parameter_count_(info->scope()->num_parameters()), |
23 stack_slot_count_(info->scope()->num_stack_slots() + | 25 stack_slot_count_(info->scope()->num_stack_slots() + |
24 info->osr_expr_stack_height()) {} | 26 info->osr_expr_stack_height()) {} |
25 | 27 |
26 | 28 |
| 29 // Peel outer loops and rewire the graph so that control reduction can |
| 30 // produce a properly formed graph. |
| 31 static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common, |
| 32 Zone* tmp_zone, Node* dead, |
| 33 LoopTree* loop_tree, LoopTree::Loop* osr_loop, |
| 34 Node* osr_normal_entry, Node* osr_loop_entry) { |
| 35 const int original_count = graph->NodeCount(); |
| 36 AllNodes all(tmp_zone, graph); |
| 37 NodeVector tmp_inputs(tmp_zone); |
| 38 Node* sentinel = graph->NewNode(dead->op()); |
| 39 |
| 40 // Make a copy of the graph for each outer loop. |
| 41 ZoneVector<NodeVector*> copies(tmp_zone); |
| 42 for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) { |
| 43 void* stuff = tmp_zone->New(sizeof(NodeVector)); |
| 44 NodeVector* mapping = |
| 45 new (stuff) NodeVector(original_count, sentinel, tmp_zone); |
| 46 copies.push_back(mapping); |
| 47 |
| 48 // Prepare the mapping for OSR values and the OSR loop entry. |
| 49 mapping->at(osr_normal_entry->id()) = dead; |
| 50 mapping->at(osr_loop_entry->id()) = dead; |
| 51 // Don't duplicate the OSR values. |
| 52 for (Node* use : osr_loop_entry->uses()) { |
| 53 if (use->opcode() == IrOpcode::kOsrValue) mapping->at(use->id()) = use; |
| 54 } |
| 55 |
| 56 // The outer loops are dead in this copy. |
| 57 for (LoopTree::Loop* outer = loop->parent(); outer; |
| 58 outer = outer->parent()) { |
| 59 for (Node* node : loop_tree->HeaderNodes(outer)) { |
| 60 mapping->at(node->id()) = dead; |
| 61 } |
| 62 } |
| 63 |
| 64 // Copy all nodes. |
| 65 for (size_t i = 0; i < all.live.size(); i++) { |
| 66 Node* orig = all.live[i]; |
| 67 Node* copy = mapping->at(orig->id()); |
| 68 if (copy != sentinel) { |
| 69 // Mapping already exists. |
| 70 continue; |
| 71 } |
| 72 if (orig->InputCount() == 0) { |
| 73 // No need to copy leaf nodes. |
| 74 mapping->at(orig->id()) = orig; |
| 75 continue; |
| 76 } |
| 77 |
| 78 // Copy the node. |
| 79 tmp_inputs.clear(); |
| 80 for (Node* input : orig->inputs()) { |
| 81 tmp_inputs.push_back(mapping->at(input->id())); |
| 82 } |
| 83 copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]); |
| 84 if (NodeProperties::IsTyped(orig)) { |
| 85 NodeProperties::SetBounds(copy, NodeProperties::GetBounds(orig)); |
| 86 } |
| 87 mapping->at(orig->id()) = copy; |
| 88 } |
| 89 |
| 90 // Fix missing inputs. |
| 91 for (size_t i = 0; i < all.live.size(); i++) { |
| 92 Node* orig = all.live[i]; |
| 93 Node* copy = mapping->at(orig->id()); |
| 94 for (int j = 0; j < copy->InputCount(); j++) { |
| 95 Node* input = copy->InputAt(j); |
| 96 if (input == sentinel) |
| 97 copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id())); |
| 98 } |
| 99 } |
| 100 |
| 101 // Construct the transfer from the previous graph copies to the new copy. |
| 102 Node* loop_header = loop_tree->HeaderNode(loop); |
| 103 NodeVector* previous = |
| 104 copies.size() > 1 ? copies[copies.size() - 2] : nullptr; |
| 105 const int backedges = loop_header->op()->ControlInputCount() - 1; |
| 106 if (backedges == 1) { |
| 107 // Simple case. Map the incoming edges to the loop to the previous copy. |
| 108 for (Node* node : loop_tree->HeaderNodes(loop)) { |
| 109 Node* copy = mapping->at(node->id()); |
| 110 Node* backedge = node->InputAt(1); |
| 111 if (previous) backedge = previous->at(backedge->id()); |
| 112 copy->ReplaceInput(0, backedge); |
| 113 } |
| 114 } else { |
| 115 // Complex case. Multiple backedges. Introduce a merge for incoming edges. |
| 116 tmp_inputs.clear(); |
| 117 for (int i = 0; i < backedges; i++) { |
| 118 Node* backedge = loop_header->InputAt(i + 1); |
| 119 if (previous) backedge = previous->at(backedge->id()); |
| 120 tmp_inputs.push_back(backedge); |
| 121 } |
| 122 Node* merge = |
| 123 graph->NewNode(common->Merge(backedges), backedges, &tmp_inputs[0]); |
| 124 for (Node* node : loop_tree->HeaderNodes(loop)) { |
| 125 Node* copy = mapping->at(node->id()); |
| 126 if (node == loop_header) { |
| 127 // The entry to the loop is the merge. |
| 128 copy->ReplaceInput(0, merge); |
| 129 } else { |
| 130 // Merge inputs to the phi at the loop entry. |
| 131 tmp_inputs.clear(); |
| 132 for (int i = 0; i < backedges; i++) { |
| 133 Node* backedge = node->InputAt(i + 1); |
| 134 if (previous) backedge = previous->at(backedge->id()); |
| 135 tmp_inputs.push_back(backedge); |
| 136 } |
| 137 tmp_inputs.push_back(merge); |
| 138 Node* phi = |
| 139 graph->NewNode(common->ResizeMergeOrPhi(node->op(), backedges), |
| 140 backedges + 1, &tmp_inputs[0]); |
| 141 copy->ReplaceInput(0, phi); |
| 142 } |
| 143 } |
| 144 } |
| 145 } |
| 146 |
| 147 // Kill the outer loops in the original graph. |
| 148 for (LoopTree::Loop* outer = osr_loop->parent(); outer; |
| 149 outer = outer->parent()) { |
| 150 loop_tree->HeaderNode(outer)->ReplaceUses(dead); |
| 151 } |
| 152 |
| 153 // Merge the ends of the graph copies. |
| 154 Node* end = graph->end(); |
| 155 tmp_inputs.clear(); |
| 156 for (int i = -1; i < static_cast<int>(copies.size()); i++) { |
| 157 Node* input = end->InputAt(0); |
| 158 if (i >= 0) input = copies[i]->at(input->id()); |
| 159 if (input->opcode() == IrOpcode::kMerge) { |
| 160 for (Node* node : input->inputs()) tmp_inputs.push_back(node); |
| 161 } else { |
| 162 tmp_inputs.push_back(input); |
| 163 } |
| 164 } |
| 165 int count = static_cast<int>(tmp_inputs.size()); |
| 166 Node* merge = graph->NewNode(common->Merge(count), count, &tmp_inputs[0]); |
| 167 end->ReplaceInput(0, merge); |
| 168 |
| 169 if (FLAG_trace_turbo_graph) { // Simple textual RPO. |
| 170 OFStream os(stdout); |
| 171 os << "-- Graph after OSR duplication -- " << std::endl; |
| 172 os << AsRPO(*graph); |
| 173 } |
| 174 } |
| 175 |
| 176 |
27 bool OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, | 177 bool OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, |
28 Zone* tmp_zone) { | 178 Zone* tmp_zone) { |
29 Graph* graph = jsgraph->graph(); | 179 Graph* graph = jsgraph->graph(); |
30 Node* osr_normal_entry = nullptr; | 180 Node* osr_normal_entry = nullptr; |
31 Node* osr_loop_entry = nullptr; | 181 Node* osr_loop_entry = nullptr; |
32 Node* osr_loop = nullptr; | 182 Node* osr_loop = nullptr; |
33 | 183 |
34 for (Node* node : graph->start()->uses()) { | 184 for (Node* node : graph->start()->uses()) { |
35 if (node->opcode() == IrOpcode::kOsrLoopEntry) { | 185 if (node->opcode() == IrOpcode::kOsrLoopEntry) { |
36 osr_loop_entry = node; // found the OSR loop entry | 186 osr_loop_entry = node; // found the OSR loop entry |
(...skipping 13 matching lines...) Expand all Loading... |
50 CHECK(!osr_loop); // should be only one OSR loop. | 200 CHECK(!osr_loop); // should be only one OSR loop. |
51 osr_loop = use; // found the OSR loop. | 201 osr_loop = use; // found the OSR loop. |
52 } | 202 } |
53 } | 203 } |
54 | 204 |
55 CHECK(osr_loop); // Should have found the OSR loop. | 205 CHECK(osr_loop); // Should have found the OSR loop. |
56 | 206 |
57 // Analyze the graph to determine how deeply nested the OSR loop is. | 207 // Analyze the graph to determine how deeply nested the OSR loop is. |
58 LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone); | 208 LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone); |
59 | 209 |
| 210 Node* dead = graph->NewNode(common->Dead()); |
60 LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop); | 211 LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop); |
61 if (loop->depth() > 0) return false; // cannot OSR inner loops yet. | 212 if (loop->depth() > 0) { |
62 | 213 PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop, |
63 // TODO(titzer): perform loop peeling or graph duplication. | 214 osr_normal_entry, osr_loop_entry); |
| 215 } |
64 | 216 |
65 // Replace the normal entry with {Dead} and the loop entry with {Start} | 217 // Replace the normal entry with {Dead} and the loop entry with {Start} |
66 // and run the control reducer to clean up the graph. | 218 // and run the control reducer to clean up the graph. |
67 osr_normal_entry->ReplaceUses(graph->NewNode(common->Dead())); | 219 osr_normal_entry->ReplaceUses(dead); |
68 osr_loop_entry->ReplaceUses(graph->start()); | 220 osr_loop_entry->ReplaceUses(graph->start()); |
69 ControlReducer::ReduceGraph(tmp_zone, jsgraph, common); | 221 ControlReducer::ReduceGraph(tmp_zone, jsgraph, common); |
70 | 222 |
71 return true; | 223 return true; |
72 } | 224 } |
73 | 225 |
74 | 226 |
75 void OsrHelper::SetupFrame(Frame* frame) { | 227 void OsrHelper::SetupFrame(Frame* frame) { |
76 // The optimized frame will subsume the unoptimized frame. Do so by reserving | 228 // The optimized frame will subsume the unoptimized frame. Do so by reserving |
77 // the first spill slots. | 229 // the first spill slots. |
78 frame->ReserveSpillSlots(UnoptimizedFrameSlots()); | 230 frame->ReserveSpillSlots(UnoptimizedFrameSlots()); |
79 // The frame needs to be adjusted by the number of unoptimized frame slots. | 231 // The frame needs to be adjusted by the number of unoptimized frame slots. |
80 frame->SetOsrStackSlotCount(static_cast<int>(UnoptimizedFrameSlots())); | 232 frame->SetOsrStackSlotCount(static_cast<int>(UnoptimizedFrameSlots())); |
81 } | 233 } |
82 | 234 |
83 | 235 |
84 } // namespace compiler | 236 } // namespace compiler |
85 } // namespace internal | 237 } // namespace internal |
86 } // namespace v8 | 238 } // namespace v8 |
OLD | NEW |