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