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
24namespace v8 {
25namespace internal {
26namespace compiler {
27
28class 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
48void 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).
56static 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.
67class 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
114void 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
162class 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
233void 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.
309class 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
338void 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
348Node* 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
371void 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