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/js-inlining.h"
6
7#include "src/ast/ast-numbering.h"
8#include "src/ast/ast.h"
9#include "src/ast/scopes.h"
10#include "src/compiler.h"
11#include "src/compiler/ast-graph-builder.h"
12#include "src/compiler/ast-loop-assignment-analyzer.h"
13#include "src/compiler/common-operator.h"
14#include "src/compiler/graph-reducer.h"
15#include "src/compiler/js-operator.h"
16#include "src/compiler/node-matchers.h"
17#include "src/compiler/node-properties.h"
18#include "src/compiler/operator-properties.h"
19#include "src/compiler/type-hint-analyzer.h"
20#include "src/isolate-inl.h"
21#include "src/parsing/parser.h"
22#include "src/parsing/rewriter.h"
23
24namespace v8 {
25namespace internal {
26namespace compiler {
27
28#define TRACE(...)                                      \
29  do {                                                  \
30    if (FLAG_trace_turbo_inlining) PrintF(__VA_ARGS__); \
31  } while (false)
32
33
34// Provides convenience accessors for the common layout of nodes having either
35// the {JSCallFunction} or the {JSCallConstruct} operator.
36class JSCallAccessor {
37 public:
38  explicit JSCallAccessor(Node* call) : call_(call) {
39    DCHECK(call->opcode() == IrOpcode::kJSCallFunction ||
40           call->opcode() == IrOpcode::kJSCallConstruct);
41  }
42
43  Node* target() {
44    // Both, {JSCallFunction} and {JSCallConstruct}, have same layout here.
45    return call_->InputAt(0);
46  }
47
48  Node* receiver() {
49    DCHECK_EQ(IrOpcode::kJSCallFunction, call_->opcode());
50    return call_->InputAt(1);
51  }
52
53  Node* new_target() {
54    DCHECK_EQ(IrOpcode::kJSCallConstruct, call_->opcode());
55    return call_->InputAt(formal_arguments() + 1);
56  }
57
58  Node* frame_state() {
59    // Both, {JSCallFunction} and {JSCallConstruct}, have frame state.
60    return NodeProperties::GetFrameStateInput(call_, 0);
61  }
62
63  int formal_arguments() {
64    // Both, {JSCallFunction} and {JSCallConstruct}, have two extra inputs:
65    //  - JSCallConstruct: Includes target function and new target.
66    //  - JSCallFunction: Includes target function and receiver.
67    return call_->op()->ValueInputCount() - 2;
68  }
69
70 private:
71  Node* call_;
72};
73
74
75Reduction JSInliner::InlineCall(Node* call, Node* new_target, Node* context,
76                                Node* frame_state, Node* start, Node* end) {
77  // The scheduler is smart enough to place our code; we just ensure {control}
78  // becomes the control input of the start of the inlinee, and {effect} becomes
79  // the effect input of the start of the inlinee.
80  Node* control = NodeProperties::GetControlInput(call);
81  Node* effect = NodeProperties::GetEffectInput(call);
82
83  int const inlinee_new_target_index =
84      static_cast<int>(start->op()->ValueOutputCount()) - 3;
85  int const inlinee_arity_index =
86      static_cast<int>(start->op()->ValueOutputCount()) - 2;
87  int const inlinee_context_index =
88      static_cast<int>(start->op()->ValueOutputCount()) - 1;
89
90  // {inliner_inputs} counts JSFunction, receiver, arguments, but not
91  // new target value, argument count, context, effect or control.
92  int inliner_inputs = call->op()->ValueInputCount();
93  // Iterate over all uses of the start node.
94  for (Edge edge : start->use_edges()) {
95    Node* use = edge.from();
96    switch (use->opcode()) {
97      case IrOpcode::kParameter: {
98        int index = 1 + ParameterIndexOf(use->op());
99        DCHECK_LE(index, inlinee_context_index);
100        if (index < inliner_inputs && index < inlinee_new_target_index) {
101          // There is an input from the call, and the index is a value
102          // projection but not the context, so rewire the input.
103          Replace(use, call->InputAt(index));
104        } else if (index == inlinee_new_target_index) {
105          // The projection is requesting the new target value.
106          Replace(use, new_target);
107        } else if (index == inlinee_arity_index) {
108          // The projection is requesting the number of arguments.
109          Replace(use, jsgraph_->Int32Constant(inliner_inputs - 2));
110        } else if (index == inlinee_context_index) {
111          // The projection is requesting the inlinee function context.
112          Replace(use, context);
113        } else {
114          // Call has fewer arguments than required, fill with undefined.
115          Replace(use, jsgraph_->UndefinedConstant());
116        }
117        break;
118      }
119      default:
120        if (NodeProperties::IsEffectEdge(edge)) {
121          edge.UpdateTo(effect);
122        } else if (NodeProperties::IsControlEdge(edge)) {
123          edge.UpdateTo(control);
124        } else if (NodeProperties::IsFrameStateEdge(edge)) {
125          edge.UpdateTo(frame_state);
126        } else {
127          UNREACHABLE();
128        }
129        break;
130    }
131  }
132
133  NodeVector values(local_zone_);
134  NodeVector effects(local_zone_);
135  NodeVector controls(local_zone_);
136  for (Node* const input : end->inputs()) {
137    switch (input->opcode()) {
138      case IrOpcode::kReturn:
139        values.push_back(NodeProperties::GetValueInput(input, 0));
140        effects.push_back(NodeProperties::GetEffectInput(input));
141        controls.push_back(NodeProperties::GetControlInput(input));
142        break;
143      case IrOpcode::kDeoptimize:
144      case IrOpcode::kTerminate:
145      case IrOpcode::kThrow:
146        NodeProperties::MergeControlToEnd(jsgraph_->graph(), jsgraph_->common(),
147                                          input);
148        Revisit(jsgraph_->graph()->end());
149        break;
150      default:
151        UNREACHABLE();
152        break;
153    }
154  }
155  DCHECK_EQ(values.size(), effects.size());
156  DCHECK_EQ(values.size(), controls.size());
157
158  // Depending on whether the inlinee produces a value, we either replace value
159  // uses with said value or kill value uses if no value can be returned.
160  if (values.size() > 0) {
161    int const input_count = static_cast<int>(controls.size());
162    Node* control_output = jsgraph_->graph()->NewNode(
163        jsgraph_->common()->Merge(input_count), input_count, &controls.front());
164    values.push_back(control_output);
165    effects.push_back(control_output);
166    Node* value_output = jsgraph_->graph()->NewNode(
167        jsgraph_->common()->Phi(MachineRepresentation::kTagged, input_count),
168        static_cast<int>(values.size()), &values.front());
169    Node* effect_output = jsgraph_->graph()->NewNode(
170        jsgraph_->common()->EffectPhi(input_count),
171        static_cast<int>(effects.size()), &effects.front());
172    ReplaceWithValue(call, value_output, effect_output, control_output);
173    return Changed(value_output);
174  } else {
175    ReplaceWithValue(call, call, call, jsgraph_->Dead());
176    return Changed(call);
177  }
178}
179
180
181Node* JSInliner::CreateArtificialFrameState(Node* node, Node* outer_frame_state,
182                                            int parameter_count,
183                                            FrameStateType frame_state_type,
184                                            Handle<SharedFunctionInfo> shared) {
185  const FrameStateFunctionInfo* state_info =
186      jsgraph_->common()->CreateFrameStateFunctionInfo(
187          frame_state_type, parameter_count + 1, 0, shared);
188
189  const Operator* op = jsgraph_->common()->FrameState(
190      BailoutId(-1), OutputFrameStateCombine::Ignore(), state_info);
191  const Operator* op0 = jsgraph_->common()->StateValues(0);
192  Node* node0 = jsgraph_->graph()->NewNode(op0);
193  NodeVector params(local_zone_);
194  for (int parameter = 0; parameter < parameter_count + 1; ++parameter) {
195    params.push_back(node->InputAt(1 + parameter));
196  }
197  const Operator* op_param =
198      jsgraph_->common()->StateValues(static_cast<int>(params.size()));
199  Node* params_node = jsgraph_->graph()->NewNode(
200      op_param, static_cast<int>(params.size()), &params.front());
201  return jsgraph_->graph()->NewNode(op, params_node, node0, node0,
202                                    jsgraph_->UndefinedConstant(),
203                                    node->InputAt(0), outer_frame_state);
204}
205
206Node* JSInliner::CreateTailCallerFrameState(Node* node, Node* frame_state) {
207  FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
208  Handle<SharedFunctionInfo> shared;
209  frame_info.shared_info().ToHandle(&shared);
210
211  Node* function = frame_state->InputAt(kFrameStateFunctionInput);
212
213  // If we are inlining a tail call drop caller's frame state and an
214  // arguments adaptor if it exists.
215  frame_state = NodeProperties::GetFrameStateInput(frame_state, 0);
216  if (frame_state->opcode() == IrOpcode::kFrameState) {
217    FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
218    if (frame_info.type() == FrameStateType::kArgumentsAdaptor) {
219      frame_state = NodeProperties::GetFrameStateInput(frame_state, 0);
220    }
221  }
222
223  const FrameStateFunctionInfo* state_info =
224      jsgraph_->common()->CreateFrameStateFunctionInfo(
225          FrameStateType::kTailCallerFunction, 0, 0, shared);
226
227  const Operator* op = jsgraph_->common()->FrameState(
228      BailoutId(-1), OutputFrameStateCombine::Ignore(), state_info);
229  const Operator* op0 = jsgraph_->common()->StateValues(0);
230  Node* node0 = jsgraph_->graph()->NewNode(op0);
231  return jsgraph_->graph()->NewNode(op, node0, node0, node0,
232                                    jsgraph_->UndefinedConstant(), function,
233                                    frame_state);
234}
235
236namespace {
237
238// TODO(mstarzinger,verwaest): Move this predicate onto SharedFunctionInfo?
239bool NeedsImplicitReceiver(Handle<SharedFunctionInfo> shared_info) {
240  DisallowHeapAllocation no_gc;
241  Isolate* const isolate = shared_info->GetIsolate();
242  Code* const construct_stub = shared_info->construct_stub();
243  return construct_stub != *isolate->builtins()->JSBuiltinsConstructStub() &&
244         construct_stub !=
245             *isolate->builtins()->JSBuiltinsConstructStubForDerived() &&
246         construct_stub != *isolate->builtins()->JSConstructStubApi();
247}
248
249bool IsNonConstructible(Handle<SharedFunctionInfo> shared_info) {
250  DisallowHeapAllocation no_gc;
251  Isolate* const isolate = shared_info->GetIsolate();
252  Code* const construct_stub = shared_info->construct_stub();
253  return construct_stub == *isolate->builtins()->ConstructedNonConstructable();
254}
255
256}  // namespace
257
258
259Reduction JSInliner::Reduce(Node* node) {
260  if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
261
262  // This reducer can handle both normal function calls as well a constructor
263  // calls whenever the target is a constant function object, as follows:
264  //  - JSCallFunction(target:constant, receiver, args...)
265  //  - JSCallConstruct(target:constant, args..., new.target)
266  HeapObjectMatcher match(node->InputAt(0));
267  if (!match.HasValue() || !match.Value()->IsJSFunction()) return NoChange();
268  Handle<JSFunction> function = Handle<JSFunction>::cast(match.Value());
269
270  return ReduceJSCall(node, function);
271}
272
273
274Reduction JSInliner::ReduceJSCall(Node* node, Handle<JSFunction> function) {
275  DCHECK(IrOpcode::IsInlineeOpcode(node->opcode()));
276  JSCallAccessor call(node);
277  Handle<SharedFunctionInfo> shared_info(function->shared());
278
279  // Function must be inlineable.
280  if (!shared_info->IsInlineable()) {
281    TRACE("Not inlining %s into %s because callee is not inlineable\n",
282          shared_info->DebugName()->ToCString().get(),
283          info_->shared_info()->DebugName()->ToCString().get());
284    return NoChange();
285  }
286
287  // Constructor must be constructable.
288  if (node->opcode() == IrOpcode::kJSCallConstruct &&
289      IsNonConstructible(shared_info)) {
290    TRACE("Not inlining %s into %s because constructor is not constructable.\n",
291          shared_info->DebugName()->ToCString().get(),
292          info_->shared_info()->DebugName()->ToCString().get());
293    return NoChange();
294  }
295
296  // Class constructors are callable, but [[Call]] will raise an exception.
297  // See ES6 section 9.2.1 [[Call]] ( thisArgument, argumentsList ).
298  if (node->opcode() == IrOpcode::kJSCallFunction &&
299      IsClassConstructor(shared_info->kind())) {
300    TRACE("Not inlining %s into %s because callee is a class constructor.\n",
301          shared_info->DebugName()->ToCString().get(),
302          info_->shared_info()->DebugName()->ToCString().get());
303    return NoChange();
304  }
305
306  // Function contains break points.
307  if (shared_info->HasDebugInfo()) {
308    TRACE("Not inlining %s into %s because callee may contain break points\n",
309          shared_info->DebugName()->ToCString().get(),
310          info_->shared_info()->DebugName()->ToCString().get());
311    return NoChange();
312  }
313
314  // Disallow cross native-context inlining for now. This means that all parts
315  // of the resulting code will operate on the same global object.
316  // This also prevents cross context leaks for asm.js code, where we could
317  // inline functions from a different context and hold on to that context (and
318  // closure) from the code object.
319  // TODO(turbofan): We might want to revisit this restriction later when we
320  // have a need for this, and we know how to model different native contexts
321  // in the same graph in a compositional way.
322  if (function->context()->native_context() !=
323      info_->context()->native_context()) {
324    TRACE("Not inlining %s into %s because of different native contexts\n",
325          shared_info->DebugName()->ToCString().get(),
326          info_->shared_info()->DebugName()->ToCString().get());
327    return NoChange();
328  }
329
330  // TODO(turbofan): TranslatedState::GetAdaptedArguments() currently relies on
331  // not inlining recursive functions. We might want to relax that at some
332  // point.
333  for (Node* frame_state = call.frame_state();
334       frame_state->opcode() == IrOpcode::kFrameState;
335       frame_state = frame_state->InputAt(kFrameStateOuterStateInput)) {
336    FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
337    Handle<SharedFunctionInfo> frame_shared_info;
338    if (frame_info.shared_info().ToHandle(&frame_shared_info) &&
339        *frame_shared_info == *shared_info) {
340      TRACE("Not inlining %s into %s because call is recursive\n",
341            shared_info->DebugName()->ToCString().get(),
342            info_->shared_info()->DebugName()->ToCString().get());
343      return NoChange();
344    }
345  }
346
347  // TODO(turbofan): Inlining into a try-block is not yet supported.
348  if (NodeProperties::IsExceptionalCall(node)) {
349    TRACE("Not inlining %s into %s because of surrounding try-block\n",
350          shared_info->DebugName()->ToCString().get(),
351          info_->shared_info()->DebugName()->ToCString().get());
352    return NoChange();
353  }
354
355  Zone zone(info_->isolate()->allocator());
356  ParseInfo parse_info(&zone, function);
357  CompilationInfo info(&parse_info, function);
358  if (info_->is_deoptimization_enabled()) info.MarkAsDeoptimizationEnabled();
359  if (info_->is_type_feedback_enabled()) info.MarkAsTypeFeedbackEnabled();
360
361  if (!Compiler::ParseAndAnalyze(info.parse_info())) {
362    TRACE("Not inlining %s into %s because parsing failed\n",
363          shared_info->DebugName()->ToCString().get(),
364          info_->shared_info()->DebugName()->ToCString().get());
365    if (info_->isolate()->has_pending_exception()) {
366      info_->isolate()->clear_pending_exception();
367    }
368    return NoChange();
369  }
370
371  if (!Compiler::EnsureDeoptimizationSupport(&info)) {
372    TRACE("Not inlining %s into %s because deoptimization support failed\n",
373          shared_info->DebugName()->ToCString().get(),
374          info_->shared_info()->DebugName()->ToCString().get());
375    return NoChange();
376  }
377
378  // Remember that we inlined this function. This needs to be called right
379  // after we ensure deoptimization support so that the code flusher
380  // does not remove the code with the deoptimization support.
381  info_->AddInlinedFunction(shared_info);
382
383  // ----------------------------------------------------------------
384  // After this point, we've made a decision to inline this function.
385  // We shall not bailout from inlining if we got here.
386
387  TRACE("Inlining %s into %s\n",
388        shared_info->DebugName()->ToCString().get(),
389        info_->shared_info()->DebugName()->ToCString().get());
390
391  // If function was lazily compiled, it's literals array may not yet be set up.
392  JSFunction::EnsureLiterals(function);
393
394  // Create the subgraph for the inlinee.
395  Node* start;
396  Node* end;
397  {
398    // Run the loop assignment analyzer on the inlinee.
399    AstLoopAssignmentAnalyzer loop_assignment_analyzer(&zone, &info);
400    LoopAssignmentAnalysis* loop_assignment =
401        loop_assignment_analyzer.Analyze();
402
403    // Run the type hint analyzer on the inlinee.
404    TypeHintAnalyzer type_hint_analyzer(&zone);
405    TypeHintAnalysis* type_hint_analysis =
406        type_hint_analyzer.Analyze(handle(shared_info->code(), info.isolate()));
407
408    // Run the AstGraphBuilder to create the subgraph.
409    Graph::SubgraphScope scope(graph());
410    AstGraphBuilder graph_builder(&zone, &info, jsgraph(), loop_assignment,
411                                  type_hint_analysis);
412    graph_builder.CreateGraph(false);
413
414    // Extract the inlinee start/end nodes.
415    start = graph()->start();
416    end = graph()->end();
417  }
418
419  Node* frame_state = call.frame_state();
420  Node* new_target = jsgraph_->UndefinedConstant();
421
422  // Inline {JSCallConstruct} requires some additional magic.
423  if (node->opcode() == IrOpcode::kJSCallConstruct) {
424    // Insert nodes around the call that model the behavior required for a
425    // constructor dispatch (allocate implicit receiver and check return value).
426    // This models the behavior usually accomplished by our {JSConstructStub}.
427    // Note that the context has to be the callers context (input to call node).
428    Node* receiver = jsgraph_->UndefinedConstant();  // Implicit receiver.
429    if (NeedsImplicitReceiver(shared_info)) {
430      Node* frame_state_before = NodeProperties::FindFrameStateBefore(node);
431      Node* effect = NodeProperties::GetEffectInput(node);
432      Node* context = NodeProperties::GetContextInput(node);
433      Node* create = jsgraph_->graph()->NewNode(
434          jsgraph_->javascript()->Create(), call.target(), call.new_target(),
435          context, frame_state_before, effect);
436      NodeProperties::ReplaceEffectInput(node, create);
437      // Insert a check of the return value to determine whether the return
438      // value
439      // or the implicit receiver should be selected as a result of the call.
440      Node* check = jsgraph_->graph()->NewNode(
441          jsgraph_->javascript()->CallRuntime(Runtime::kInlineIsJSReceiver, 1),
442          node, context, node, start);
443      Node* select = jsgraph_->graph()->NewNode(
444          jsgraph_->common()->Select(MachineRepresentation::kTagged), check,
445          node, create);
446      NodeProperties::ReplaceUses(node, select, check, node, node);
447      NodeProperties::ReplaceValueInput(select, node, 1);
448      NodeProperties::ReplaceValueInput(check, node, 0);
449      NodeProperties::ReplaceEffectInput(check, node);
450      receiver = create;  // The implicit receiver.
451    }
452
453    // Swizzle the inputs of the {JSCallConstruct} node to look like inputs to a
454    // normal {JSCallFunction} node so that the rest of the inlining machinery
455    // behaves as if we were dealing with a regular function invocation.
456    new_target = call.new_target();  // Retrieve new target value input.
457    node->RemoveInput(call.formal_arguments() + 1);  // Drop new target.
458    node->InsertInput(jsgraph_->graph()->zone(), 1, receiver);
459
460    // Insert a construct stub frame into the chain of frame states. This will
461    // reconstruct the proper frame when deoptimizing within the constructor.
462    frame_state = CreateArtificialFrameState(
463        node, frame_state, call.formal_arguments(),
464        FrameStateType::kConstructStub, info.shared_info());
465  }
466
467  // The inlinee specializes to the context from the JSFunction object.
468  // TODO(turbofan): We might want to load the context from the JSFunction at
469  // runtime in case we only know the SharedFunctionInfo once we have dynamic
470  // type feedback in the compiler.
471  Node* context = jsgraph_->Constant(handle(function->context()));
472
473  // Insert a JSConvertReceiver node for sloppy callees. Note that the context
474  // passed into this node has to be the callees context (loaded above). Note
475  // that the frame state passed to the JSConvertReceiver must be the frame
476  // state _before_ the call; it is not necessary to fiddle with the receiver
477  // in that frame state tho, as the conversion of the receiver can be repeated
478  // any number of times, it's not observable.
479  if (node->opcode() == IrOpcode::kJSCallFunction &&
480      is_sloppy(parse_info.language_mode()) && !shared_info->native()) {
481    const CallFunctionParameters& p = CallFunctionParametersOf(node->op());
482    Node* frame_state_before = NodeProperties::FindFrameStateBefore(node);
483    Node* effect = NodeProperties::GetEffectInput(node);
484    Node* convert = jsgraph_->graph()->NewNode(
485        jsgraph_->javascript()->ConvertReceiver(p.convert_mode()),
486        call.receiver(), context, frame_state_before, effect, start);
487    NodeProperties::ReplaceValueInput(node, convert, 1);
488    NodeProperties::ReplaceEffectInput(node, convert);
489  }
490
491  // If we are inlining a JS call at tail position then we have to pop current
492  // frame state and its potential arguments adaptor frame state in order to
493  // make the call stack be consistent with non-inlining case.
494  // After that we add a tail caller frame state which lets deoptimizer handle
495  // the case when the outermost function inlines a tail call (it should remove
496  // potential arguments adaptor frame that belongs to outermost function when
497  // deopt happens).
498  if (node->opcode() == IrOpcode::kJSCallFunction) {
499    const CallFunctionParameters& p = CallFunctionParametersOf(node->op());
500    if (p.tail_call_mode() == TailCallMode::kAllow) {
501      frame_state = CreateTailCallerFrameState(node, frame_state);
502    }
503  }
504
505  // Insert argument adaptor frame if required. The callees formal parameter
506  // count (i.e. value outputs of start node minus target, receiver, new target,
507  // arguments count and context) have to match the number of arguments passed
508  // to the call.
509  int parameter_count = info.literal()->parameter_count();
510  DCHECK_EQ(parameter_count, start->op()->ValueOutputCount() - 5);
511  if (call.formal_arguments() != parameter_count) {
512    frame_state = CreateArtificialFrameState(
513        node, frame_state, call.formal_arguments(),
514        FrameStateType::kArgumentsAdaptor, shared_info);
515  }
516
517  return InlineCall(node, new_target, context, frame_state, start, end);
518}
519
520Graph* JSInliner::graph() const { return jsgraph()->graph(); }
521
522}  // namespace compiler
523}  // namespace internal
524}  // namespace v8
525