Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +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/compiler/access-builder.h" |
| 6 | #include "src/compiler/ast-graph-builder.h" |
| 7 | #include "src/compiler/common-operator.h" |
| 8 | #include "src/compiler/generic-node-inl.h" |
| 9 | #include "src/compiler/graph-inl.h" |
| 10 | #include "src/compiler/graph-visualizer.h" |
| 11 | #include "src/compiler/js-inlining.h" |
| 12 | #include "src/compiler/js-operator.h" |
| 13 | #include "src/compiler/node-aux-data-inl.h" |
| 14 | #include "src/compiler/node-matchers.h" |
| 15 | #include "src/compiler/node-properties-inl.h" |
| 16 | #include "src/compiler/simplified-operator.h" |
| 17 | #include "src/compiler/typer.h" |
| 18 | #include "src/full-codegen.h" |
| 19 | #include "src/parser.h" |
| 20 | #include "src/rewriter.h" |
| 21 | #include "src/scopes.h" |
| 22 | |
| 23 | |
| 24 | namespace v8 { |
| 25 | namespace internal { |
| 26 | namespace compiler { |
| 27 | |
| 28 | class InlinerVisitor : public NullNodeVisitor { |
| 29 | public: |
| 30 | explicit InlinerVisitor(JSInliner* inliner) : inliner_(inliner) {} |
| 31 | |
| 32 | GenericGraphVisit::Control Post(Node* node) { |
| 33 | switch (node->opcode()) { |
| 34 | case IrOpcode::kJSCallFunction: |
| 35 | inliner_->TryInlineCall(node); |
| 36 | break; |
| 37 | default: |
| 38 | break; |
| 39 | } |
| 40 | return GenericGraphVisit::CONTINUE; |
| 41 | } |
| 42 | |
| 43 | private: |
| 44 | JSInliner* inliner_; |
| 45 | }; |
| 46 | |
| 47 | |
| 48 | void JSInliner::Inline() { |
| 49 | InlinerVisitor visitor(this); |
| 50 | jsgraph_->graph()->VisitNodeInputsFromEnd(&visitor); |
| 51 | } |
| 52 | |
| 53 | |
| 54 | // TODO(sigurds) Find a home for this function and reuse it everywhere (esp. in |
| 55 | // test cases, where similar code is currently duplicated). |
| 56 | static void Parse(Handle<JSFunction> function, CompilationInfoWithZone* info) { |
| 57 | CHECK(Parser::Parse(info)); |
| 58 | CHECK(Rewriter::Rewrite(info)); |
| 59 | CHECK(Scope::Analyze(info)); |
| 60 | CHECK(Compiler::EnsureDeoptimizationSupport(info)); |
| 61 | } |
| 62 | |
| 63 | |
| 64 | // A facade on a JSFunction's graph to facilitate inlining. It assumes the |
| 65 | // that the function graph has only one return statement, and provides |
| 66 | // {UnifyReturn} to convert a function graph to that end. |
| 67 | class Inlinee { |
| 68 | public: |
| 69 | Inlinee(Node* start, Node* end) : start_(start), end_(end) {} |
| 70 | |
| 71 | // Returns the last regular control node, that is |
| 72 | // the last control node before the end node. |
| 73 | Node* end_block() { return NodeProperties::GetControlInput(unique_return()); } |
| 74 | |
| 75 | // Return the effect output of the graph, |
| 76 | // that is the effect input of the return statement of the inlinee. |
| 77 | Node* effect_output() { |
| 78 | return NodeProperties::GetEffectInput(unique_return()); |
| 79 | } |
| 80 | // Return the value output of the graph, |
| 81 | // that is the value input of the return statement of the inlinee. |
| 82 | Node* value_output() { |
| 83 | return NodeProperties::GetValueInput(unique_return(), 0); |
| 84 | } |
| 85 | // Return the unique return statement of the graph. |
| 86 | Node* unique_return() { |
| 87 | Node* unique_return = NodeProperties::GetControlInput(end_); |
| 88 | DCHECK_EQ(IrOpcode::kReturn, unique_return->opcode()); |
| 89 | return unique_return; |
| 90 | } |
| 91 | |
| 92 | // Counts JSFunction, Receiver, arguments, context but not effect, control. |
| 93 | size_t total_parameters() { return start_->op()->OutputCount(); } |
| 94 | |
| 95 | // Counts only formal parameters. |
| 96 | size_t formal_parameters() { |
| 97 | DCHECK_GE(total_parameters(), 3); |
| 98 | return total_parameters() - 3; |
| 99 | } |
| 100 | |
| 101 | // Inline this graph at {call}, use {jsgraph} and its zone to create |
| 102 | // any new nodes. |
| 103 | void InlineAtCall(JSGraph* jsgraph, Node* call); |
| 104 | |
| 105 | // Ensure that only a single return reaches the end node. |
| 106 | static void UnifyReturn(JSGraph* jsgraph); |
| 107 | |
| 108 | private: |
| 109 | Node* start_; |
| 110 | Node* end_; |
| 111 | }; |
| 112 | |
| 113 | |
| 114 | void Inlinee::UnifyReturn(JSGraph* jsgraph) { |
| 115 | Graph* graph = jsgraph->graph(); |
| 116 | |
| 117 | Node* final_merge = NodeProperties::GetControlInput(graph->end(), 0); |
| 118 | if (final_merge->opcode() == IrOpcode::kReturn) { |
| 119 | // nothing to do |
| 120 | return; |
| 121 | } |
| 122 | DCHECK_EQ(IrOpcode::kMerge, final_merge->opcode()); |
| 123 | |
| 124 | int predecessors = |
| 125 | OperatorProperties::GetControlInputCount(final_merge->op()); |
| 126 | |
| 127 | const Operator* op_phi = jsgraph->common()->Phi(kMachAnyTagged, predecessors); |
| 128 | const Operator* op_ephi = jsgraph->common()->EffectPhi(predecessors); |
| 129 | |
| 130 | NodeVector values(jsgraph->zone()); |
| 131 | NodeVector effects(jsgraph->zone()); |
| 132 | // Iterate over all control flow predecessors, |
| 133 | // which must be return statements. |
| 134 | InputIter iter = final_merge->inputs().begin(); |
| 135 | while (iter != final_merge->inputs().end()) { |
| 136 | Node* input = *iter; |
| 137 | switch (input->opcode()) { |
| 138 | case IrOpcode::kReturn: |
| 139 | values.push_back(NodeProperties::GetValueInput(input, 0)); |
| 140 | effects.push_back(NodeProperties::GetEffectInput(input)); |
| 141 | iter.UpdateToAndIncrement(NodeProperties::GetControlInput(input)); |
| 142 | input->RemoveAllInputs(); |
| 143 | break; |
| 144 | default: |
| 145 | UNREACHABLE(); |
| 146 | ++iter; |
| 147 | break; |
| 148 | } |
| 149 | } |
| 150 | values.push_back(final_merge); |
| 151 | effects.push_back(final_merge); |
| 152 | Node* phi = |
| 153 | graph->NewNode(op_phi, static_cast<int>(values.size()), &values.front()); |
| 154 | Node* ephi = graph->NewNode(op_ephi, static_cast<int>(effects.size()), |
| 155 | &effects.front()); |
| 156 | Node* new_return = |
| 157 | graph->NewNode(jsgraph->common()->Return(), phi, ephi, final_merge); |
| 158 | graph->end()->ReplaceInput(0, new_return); |
| 159 | } |
| 160 | |
| 161 | |
| 162 | class CopyVisitor : public NullNodeVisitor { |
| 163 | public: |
| 164 | CopyVisitor(Graph* source_graph, Graph* target_graph, Zone* temp_zone) |
| 165 | : copies_(source_graph->NodeCount(), NULL, temp_zone), |
| 166 | sentinels_(source_graph->NodeCount(), NULL, temp_zone), |
| 167 | source_graph_(source_graph), |
| 168 | target_graph_(target_graph), |
| 169 | temp_zone_(temp_zone), |
| 170 | sentinel_op_(IrOpcode::kDead, Operator::kNoProperties, 0, 0, |
| 171 | "sentinel") {} |
| 172 | |
| 173 | GenericGraphVisit::Control Post(Node* original) { |
| 174 | NodeVector inputs(temp_zone_); |
| 175 | for (InputIter it = original->inputs().begin(); |
| 176 | it != original->inputs().end(); ++it) { |
| 177 | inputs.push_back(GetCopy(*it)); |
| 178 | } |
| 179 | |
| 180 | // Reuse the operator in the copy. This assumes that op lives in a zone |
| 181 | // that lives longer than graph()'s zone. |
| 182 | Node* copy = |
| 183 | target_graph_->NewNode(original->op(), static_cast<int>(inputs.size()), |
| 184 | (inputs.empty() ? NULL : &inputs.front())); |
| 185 | copies_[original->id()] = copy; |
| 186 | return GenericGraphVisit::CONTINUE; |
| 187 | } |
| 188 | |
| 189 | Node* GetCopy(Node* original) { |
| 190 | Node* copy = copies_[original->id()]; |
| 191 | if (copy == NULL) { |
| 192 | copy = GetSentinel(original); |
| 193 | } |
| 194 | DCHECK_NE(NULL, copy); |
| 195 | return copy; |
| 196 | } |
| 197 | |
| 198 | void CopyGraph() { |
| 199 | source_graph_->VisitNodeInputsFromEnd(this); |
| 200 | ReplaceSentinels(); |
| 201 | } |
| 202 | |
| 203 | const NodeVector& copies() { return copies_; } |
| 204 | |
| 205 | private: |
| 206 | void ReplaceSentinels() { |
| 207 | for (NodeId id = 0; id < source_graph_->NodeCount(); ++id) { |
| 208 | Node* sentinel = sentinels_[id]; |
| 209 | if (sentinel == NULL) continue; |
| 210 | Node* copy = copies_[id]; |
| 211 | DCHECK_NE(NULL, copy); |
| 212 | sentinel->ReplaceUses(copy); |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | Node* GetSentinel(Node* original) { |
| 217 | Node* sentinel = sentinels_[original->id()]; |
| 218 | if (sentinel == NULL) { |
| 219 | sentinel = target_graph_->NewNode(&sentinel_op_); |
| 220 | } |
| 221 | return sentinel; |
| 222 | } |
| 223 | |
| 224 | NodeVector copies_; |
| 225 | NodeVector sentinels_; |
| 226 | Graph* source_graph_; |
| 227 | Graph* target_graph_; |
| 228 | Zone* temp_zone_; |
| 229 | SimpleOperator sentinel_op_; |
| 230 | }; |
| 231 | |
| 232 | |
| 233 | void Inlinee::InlineAtCall(JSGraph* jsgraph, Node* call) { |
| 234 | // The scheduler is smart enough to place our code; we just ensure {control} |
| 235 | // becomes the control input of the start of the inlinee. |
| 236 | Node* control = NodeProperties::GetControlInput(call); |
| 237 | |
| 238 | // The inlinee uses the context from the JSFunction object. This will |
| 239 | // also be the effect dependency for the inlinee as it produces an effect. |
| 240 | SimplifiedOperatorBuilder simplified(jsgraph->zone()); |
| 241 | Node* context = jsgraph->graph()->NewNode( |
| 242 | simplified.LoadField(AccessBuilder::ForJSFunctionContext()), |
| 243 | NodeProperties::GetValueInput(call, 0), |
| 244 | NodeProperties::GetEffectInput(call)); |
| 245 | |
| 246 | // Context is last argument. |
| 247 | int inlinee_context_index = static_cast<int>(total_parameters()) - 1; |
| 248 | // {inliner_inputs} counts JSFunction, Receiver, arguments, but not |
| 249 | // context, effect, control. |
| 250 | int inliner_inputs = OperatorProperties::GetValueInputCount(call->op()); |
| 251 | // Iterate over all uses of the start node. |
| 252 | UseIter iter = start_->uses().begin(); |
| 253 | while (iter != start_->uses().end()) { |
| 254 | Node* use = *iter; |
| 255 | switch (use->opcode()) { |
| 256 | case IrOpcode::kParameter: { |
| 257 | int index = 1 + OpParameter<int>(use->op()); |
| 258 | if (index < inliner_inputs && index < inlinee_context_index) { |
| 259 | // There is an input from the call, and the index is a value |
| 260 | // projection but not the context, so rewire the input. |
| 261 | NodeProperties::ReplaceWithValue(*iter, call->InputAt(index)); |
| 262 | } else if (index == inlinee_context_index) { |
| 263 | // This is the context projection, rewire it to the context from the |
| 264 | // JSFunction object. |
| 265 | NodeProperties::ReplaceWithValue(*iter, context); |
| 266 | } else if (index < inlinee_context_index) { |
| 267 | // Call has fewer arguments than required, fill with undefined. |
| 268 | NodeProperties::ReplaceWithValue(*iter, jsgraph->UndefinedConstant()); |
| 269 | } else { |
| 270 | // We got too many arguments, discard for now. |
| 271 | // TODO(sigurds): Fix to treat arguments array correctly. |
| 272 | } |
| 273 | ++iter; |
| 274 | break; |
| 275 | } |
| 276 | default: |
| 277 | if (NodeProperties::IsEffectEdge(iter.edge())) { |
| 278 | iter.UpdateToAndIncrement(context); |
| 279 | } else if (NodeProperties::IsControlEdge(iter.edge())) { |
| 280 | iter.UpdateToAndIncrement(control); |
| 281 | } else { |
| 282 | UNREACHABLE(); |
| 283 | } |
| 284 | break; |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | // Iterate over all uses of the call node. |
| 289 | iter = call->uses().begin(); |
| 290 | while (iter != call->uses().end()) { |
| 291 | if (NodeProperties::IsEffectEdge(iter.edge())) { |
| 292 | iter.UpdateToAndIncrement(effect_output()); |
| 293 | } else if (NodeProperties::IsControlEdge(iter.edge())) { |
| 294 | UNREACHABLE(); |
| 295 | } else { |
| 296 | DCHECK(NodeProperties::IsValueEdge(iter.edge())); |
| 297 | iter.UpdateToAndIncrement(value_output()); |
| 298 | } |
| 299 | } |
| 300 | call->RemoveAllInputs(); |
| 301 | DCHECK_EQ(0, call->UseCount()); |
| 302 | // TODO(sigurds) Remove this once we copy. |
| 303 | unique_return()->RemoveAllInputs(); |
| 304 | } |
| 305 | |
| 306 | |
| 307 | // TODO(turbofan) Provide such accessors for every node, possibly even |
| 308 | // generate them. |
| 309 | class JSCallFunctionAccessor { |
| 310 | public: |
| 311 | explicit JSCallFunctionAccessor(Node* call) : call_(call) { |
| 312 | DCHECK_EQ(IrOpcode::kJSCallFunction, call->opcode()); |
| 313 | } |
| 314 | |
| 315 | Node* jsfunction() { return call_->InputAt(0); } |
| 316 | |
| 317 | Node* receiver() { return call_->InputAt(1); } |
| 318 | |
| 319 | Node* formal_argument(size_t index) { |
| 320 | DCHECK(index < formal_arguments()); |
| 321 | return call_->InputAt(static_cast<int>(2 + index)); |
| 322 | } |
| 323 | |
| 324 | size_t formal_arguments() { |
| 325 | // {value_inputs} includes jsfunction and receiver. |
| 326 | size_t value_inputs = OperatorProperties::GetValueInputCount(call_->op()); |
| 327 | DCHECK_GE(call_->InputCount(), 2); |
| 328 | return value_inputs - 2; |
| 329 | } |
| 330 | |
| 331 | Node* frame_state() { return NodeProperties::GetFrameStateInput(call_); } |
| 332 | |
| 333 | private: |
| 334 | Node* call_; |
| 335 | }; |
| 336 | |
| 337 | |
| 338 | void JSInliner::AddClosureToFrameState(Node* frame_state, |
| 339 | Handle<JSFunction> jsfunction) { |
| 340 | FrameStateCallInfo call_info = OpParameter<FrameStateCallInfo>(frame_state); |
| 341 | const Operator* op = jsgraph_->common()->FrameState( |
| 342 | FrameStateType::JS_FRAME, call_info.bailout_id(), |
| 343 | call_info.state_combine(), jsfunction); |
| 344 | frame_state->set_op(op); |
| 345 | } |
| 346 | |
| 347 | |
| 348 | Node* JSInliner::CreateArgumentsAdaptorFrameState(JSCallFunctionAccessor* call, |
| 349 | Handle<JSFunction> jsfunction, |
| 350 | Zone* temp_zone) { |
| 351 | const Operator* op = |
| 352 | jsgraph_->common()->FrameState(FrameStateType::ARGUMENTS_ADAPTOR, |
| 353 | BailoutId(-1), kIgnoreOutput, jsfunction); |
| 354 | const Operator* op0 = jsgraph_->common()->StateValues(0); |
| 355 | Node* node0 = jsgraph_->graph()->NewNode(op0); |
| 356 | NodeVector params(temp_zone); |
| 357 | params.push_back(call->receiver()); |
| 358 | for (size_t argument = 0; argument != call->formal_arguments(); ++argument) { |
| 359 | params.push_back(call->formal_argument(argument)); |
| 360 | } |
| 361 | const Operator* op_param = |
| 362 | jsgraph_->common()->StateValues(static_cast<int>(params.size())); |
| 363 | Node* params_node = jsgraph_->graph()->NewNode( |
| 364 | op_param, static_cast<int>(params.size()), ¶ms.front()); |
| 365 | return jsgraph_->graph()->NewNode(op, params_node, node0, node0, |
| 366 | jsgraph_->UndefinedConstant(), |
| 367 | call->frame_state()); |
| 368 | } |
| 369 | |
| 370 | |
| 371 | void JSInliner::TryInlineCall(Node* call_node) { |
| 372 | JSCallFunctionAccessor call(call_node); |
| 373 | |
| 374 | HeapObjectMatcher<JSFunction> match(call.jsfunction()); |
| 375 | if (!match.HasValue()) { |
| 376 | return; |
| 377 | } |
| 378 | |
| 379 | Handle<JSFunction> function = match.Value().handle(); |
| 380 | |
| 381 | if (function->shared()->native()) { |
| 382 | if (FLAG_trace_turbo_inlining) { |
| 383 | SmartArrayPointer<char> name = |
| 384 | function->shared()->DebugName()->ToCString(); |
| 385 | PrintF("Not Inlining %s into %s because inlinee is native\n", name.get(), |
| 386 | info_->shared_info()->DebugName()->ToCString().get()); |
| 387 | } |
| 388 | return; |
| 389 | } |
| 390 | |
| 391 | CompilationInfoWithZone info(function); |
| 392 | Parse(function, &info); |
| 393 | |
| 394 | if (info.scope()->arguments() != NULL) { |
| 395 | // For now do not inline functions that use their arguments array. |
| 396 | SmartArrayPointer<char> name = function->shared()->DebugName()->ToCString(); |
| 397 | if (FLAG_trace_turbo_inlining) { |
| 398 | PrintF( |
| 399 | "Not Inlining %s into %s because inlinee uses arguments " |
| 400 | "array\n", |
| 401 | name.get(), info_->shared_info()->DebugName()->ToCString().get()); |
| 402 | } |
| 403 | return; |
| 404 | } |
| 405 | |
| 406 | if (FLAG_trace_turbo_inlining) { |
| 407 | SmartArrayPointer<char> name = function->shared()->DebugName()->ToCString(); |
| 408 | PrintF("Inlining %s into %s\n", name.get(), |
| 409 | info_->shared_info()->DebugName()->ToCString().get()); |
| 410 | } |
| 411 | |
| 412 | Graph graph(info.zone()); |
| 413 | Typer typer(info.zone()); |
| 414 | JSGraph jsgraph(&graph, jsgraph_->common(), jsgraph_->javascript(), &typer, |
| 415 | jsgraph_->machine()); |
| 416 | |
| 417 | AstGraphBuilder graph_builder(&info, &jsgraph); |
| 418 | graph_builder.CreateGraph(); |
| 419 | Inlinee::UnifyReturn(&jsgraph); |
| 420 | |
| 421 | CopyVisitor visitor(&graph, jsgraph_->graph(), info.zone()); |
| 422 | visitor.CopyGraph(); |
| 423 | |
| 424 | Inlinee inlinee(visitor.GetCopy(graph.start()), visitor.GetCopy(graph.end())); |
| 425 | |
| 426 | Node* outer_frame_state = call.frame_state(); |
| 427 | // Insert argument adaptor frame if required. |
| 428 | if (call.formal_arguments() != inlinee.formal_parameters()) { |
| 429 | outer_frame_state = |
| 430 | CreateArgumentsAdaptorFrameState(&call, function, info.zone()); |
| 431 | } |
| 432 | |
| 433 | for (NodeVectorConstIter it = visitor.copies().begin(); |
| 434 | it != visitor.copies().end(); ++it) { |
| 435 | Node* node = *it; |
| 436 | if (node != NULL && node->opcode() == IrOpcode::kFrameState) { |
| 437 | AddClosureToFrameState(node, function); |
| 438 | NodeProperties::ReplaceFrameStateInput(node, outer_frame_state); |
| 439 | } |
| 440 | } |
| 441 | |
| 442 | inlinee.InlineAtCall(jsgraph_, call_node); |
| 443 | } |
| 444 | } |
| 445 | } |
| 446 | } // namespace v8::internal::compiler |