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 447