src/v8/src/compiler/js-inlining.cc

   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()), &params.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