Add initial support for inlining.

src/compiler/js-inlining.cc

+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/ast-graph-builder.h"
+#include "src/compiler/common-operator.h"
+#include "src/compiler/generic-node-inl.h"
+#include "src/compiler/graph-inl.h"
+#include "src/compiler/graph-visualizer.h"
+#include "src/compiler/js-inlining.h"
+#include "src/compiler/js-operator.h"
+#include "src/compiler/node-aux-data-inl.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/compiler/simplified-operator.h"
+#include "src/compiler/typer.h"
+#include "src/parser.h"
+#include "src/rewriter.h"
+#include "src/scopes.h"
+
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// TODO(titzer): factor this out to a common routine with js-typed-lowering.
+static void ReplaceEffectfulWithValue(Node* node, Node* value) {
+  Node* effect = NULL;
+  if (OperatorProperties::HasEffectInput(node->op())) {
+    effect = NodeProperties::GetEffectInput(node);
+  }
+
+  // Requires distinguishing between value and effect edges.
+  UseIter iter = node->uses().begin();
+  while (iter != node->uses().end()) {
+    if (NodeProperties::IsEffectEdge(iter.edge())) {
+      DCHECK_NE(NULL, effect);
+      iter = iter.UpdateToAndIncrement(effect);
+    } else {
+      iter = iter.UpdateToAndIncrement(value);
+    }
+  }
+}
+
+
+class InlinerVisitor : public NullNodeVisitor {
+ public:
+  explicit InlinerVisitor(JSInliner* spec) : spec_(spec) {}
+
+  GenericGraphVisit::Control Post(Node* node) {
+    switch (node->opcode()) {
+      case IrOpcode::kJSCallFunction:
+        spec_->InlineCall(node);
+        break;
+      default:
+        break;
+    }
+    return GenericGraphVisit::CONTINUE;
+  }
+
+ private:
+  JSInliner* spec_;
+};
+
+
+void JSInliner::Inline() {
+  if (!info_->closure()->PassesFilter(FLAG_turbo_inlining_filter)) {
+    return;
+  }
+  InlinerVisitor visitor(this);
+  jsgraph_->graph()->VisitNodeInputsFromEnd(&visitor);
+}
+
+
+/// Ensure that only a single return reaches the end node.

[Michael Starzinger, 2014/08/12 20:04:46]

nit: Two slashes ought to be enough for everyone. :)

[sigurds, 2014/08/14 09:54:41]

Done.

+void JSInliner::UnifyReturn(JSGraph* jsgraph) {
+  Graph* graph = jsgraph->graph();
+
+  Node* final_merge = NodeProperties::GetControlInput(graph->end(), 0);
+  if (final_merge->opcode() == IrOpcode::kReturn) {
+    // nothing to do
+    return;
+  }
+  DCHECK_EQ(IrOpcode::kMerge, final_merge->opcode());
+
+  int predecessors =
+      OperatorProperties::GetControlInputCount(final_merge->op());
+  Operator* op_phi = jsgraph->common()->Phi(predecessors);
+  Operator* op_ephi = jsgraph->common()->EffectPhi(predecessors);
+
+  std::vector<Node*> values;
+  std::vector<Node*> effects;
+  // Iterate over all control flow predecessors,
+  // which must be return statements.
+  InputIter iter = final_merge->inputs().begin();
+  while (iter != final_merge->inputs().end()) {
+    Node* input = *iter;
+    switch (input->opcode()) {
+      case IrOpcode::kReturn:
+        values.push_back(NodeProperties::GetValueInput(input, 0));
+        effects.push_back(NodeProperties::GetEffectInput(input));
+        iter.UpdateToAndIncrement(NodeProperties::GetControlInput(input));
+        input->RemoveAllInputs();
+        break;
+      default:
+        UNREACHABLE();
+        ++iter;
+        break;
+    }
+  }
+  values.push_back(final_merge);
+  effects.push_back(final_merge);
+  Node* phi = graph->NewNode(op_phi, values.size(), values.data());
+  Node* ephi = graph->NewNode(op_ephi, effects.size(), effects.data());
+  Node* new_return =
+      graph->NewNode(jsgraph->common()->Return(), phi, ephi, final_merge);
+  graph->end()->ReplaceInput(0, new_return);
+}
+
+
+void moveWithDependencies(JSGraph* graph, Node* node, Node* old_block,

[Michael Starzinger, 2014/08/12 20:04:45]

style: Uppercase "M". Also needs to be static.

[sigurds, 2014/08/14 09:54:42]

Done.

+                          Node* new_block) {
+  if (OperatorProperties::HasControlInput(node->op())) {
+    // Check if we have left the old_block.
+    if (NodeProperties::GetControlInput(node) != old_block) return;
+    // If not, move this node to the new_block.
+    NodeProperties::ReplaceControlInput(node, new_block);
+  }
+  // Independent of whether a node has a control input or not,
+  // it might have a dependency that is pinned to old_block.
+  for (InputIter iter = node->inputs().begin(); iter != node->inputs().end();
+       ++iter) {
+    if (NodeProperties::IsControlEdge(iter.edge())) continue;
+    moveWithDependencies(graph, *iter, old_block, new_block);
+  }
+}
+
+
+static bool IsStackGuard(Node* node) {
+  if (node->opcode() != IrOpcode::kJSCallRuntime) return false;
+  Runtime::FunctionId id = OpParameter<Runtime::FunctionId>(node);
+  return id == Runtime::kStackGuard;
+}
+
+
+static void RemoveStackGuard(Node* stackGuard) {
+  DCHECK(IsStackGuard(stackGuard));
+  DCHECK_EQ(1, stackGuard->UseCount());
+  NodeProperties::ReplaceEffectInput(
+      stackGuard->UseAt(0), NodeProperties::GetEffectInput(stackGuard));
+  stackGuard->RemoveAllInputs();
+}
+
+
+static void moveAllControlNodes(Node* from, Node* to) {

[Michael Starzinger, 2014/08/12 20:04:46]

style: Uppercase "M".

[sigurds, 2014/08/14 09:54:42]

Done.

+  for (UseIter iter = from->uses().begin(); iter != from->uses().end();) {
+    if (NodeProperties::IsControlEdge(iter.edge())) {
+      iter.UpdateToAndIncrement(to);
+    } else {
+      ++iter;
+    }
+  }
+}
+
+
+void DoInline(Zone* zone, Node* call, CompilationInfo* info, JSGraph* jsgraph) {

[Michael Starzinger, 2014/08/12 20:04:46]

Either make this a (private) member method of JSInliner instead of passing
everything around as arguments or at least make this static.

[sigurds, 2014/08/14 09:54:42]

Made it a private method. (Saves Zone* argument)

info and jsgraph belong to the inlinee, so I have to pass it in.

+  Graph* graph = jsgraph->graph();
+  MachineOperatorBuilder machine(zone);
+
+  Node* control = NodeProperties::GetControlInput(call);
+  Node* unified_return = NodeProperties::GetControlInput(graph->end());
+  DCHECK_EQ(IrOpcode::kReturn, unified_return->opcode());
+  Node* inlined_control = NodeProperties::GetControlInput(unified_return);
+  Node* bottom_block = inlined_control;
+  // Move all the nodes to the bottom block.
+  moveAllControlNodes(control, bottom_block);
+  // Now move the ones the call depends on back up.
+  // We have to do this back-and-forth to treat the case where the call is
+  // pinned to the start block.
+  moveWithDependencies(jsgraph, call, bottom_block, control);
+
+  // The inlinee uses the context from the JSFunction object.
+  Node* context = graph->NewNode(
+      machine.Load(kMachineTagged), NodeProperties::GetValueInput(call, 0),
+      jsgraph->Int32Constant(JSFunction::kContextOffset - kHeapObjectTag),
+      NodeProperties::GetEffectInput(call));
+
+  Node* stackGuard = NULL;
+
+  // {inlinee_inputs} counts JSFunction, Receiver, arguments, context,
+  // but not effect, control.
+  int inlinee_inputs = graph->start()->op()->OutputCount();
+  // Context is last argument.
+  int inlinee_context_index = inlinee_inputs - 1;
+  // {inliner_inputs} counts JSFunction, Receiver, arguments, but not
+  // context, effect, control.
+  int inliner_inputs = OperatorProperties::GetValueInputCount(call->op());
+  // Iterate over all uses of the start node.
+  UseIter iter = graph->start()->uses().begin();
+  while (iter != graph->start()->uses().end()) {
+    Node* use = *iter;
+    switch (use->opcode()) {
+      case IrOpcode::kParameter: {
+        int index = 1 + static_cast<Operator1<int>*>(use->op())->parameter();
+        if (index < inliner_inputs && index < inlinee_context_index) {
+          // There is an input from the call, and the index is a value
+          // projection but not the context, so rewire the input.
+          ReplaceEffectfulWithValue(*iter, call->InputAt(index));
+        } else if (index == inlinee_context_index) {
+          // This is the context projection, rewire it to the context from the
+          // JSFunction object.
+          ReplaceEffectfulWithValue(*iter, context);
+        } else if (index < inlinee_context_index) {
+          // Call has fewer arguments than required, fill with undefined.
+          ReplaceEffectfulWithValue(*iter, jsgraph->UndefinedConstant());
+        } else {
+          // We got too many arguments, discard for now.
+          // TODO(sigurds): Fix to treat arguments array correctly.
+        }
+        ++iter;
+        break;
+      }
+      default:
+        if (NodeProperties::IsEffectEdge(iter.edge())) {
+          iter.UpdateToAndIncrement(context);
+          stackGuard = use;
+        } else if (NodeProperties::IsControlEdge(iter.edge())) {
+          iter.UpdateToAndIncrement(control);
+        } else {
+          UNREACHABLE();
+        }
+        break;
+    }
+  }
+
+  // TODO(sigurds) Do not make assumptions about position of stack guard.
+  if (IsStackGuard(stackGuard)) {

[Michael Starzinger, 2014/08/12 20:04:46]

Let's just drop the removal of the stack-guard for now. This will break once we
implement actual stack-guards (instead of runtime calls) and should not affect
correctness.

[sigurds, 2014/08/14 09:54:42]

Done.

+    RemoveStackGuard(stackGuard);
+  }
+
+  // Iterate over all uses of the call node.
+  iter = call->uses().begin();
+  while (iter != call->uses().end()) {
+    if (NodeProperties::IsEffectEdge(iter.edge())) {
+      iter.UpdateToAndIncrement(NodeProperties::GetEffectInput(unified_return));
+    } else if (NodeProperties::IsControlEdge(iter.edge())) {
+      UNREACHABLE();
+    } else {
+      DCHECK(NodeProperties::IsValueEdge(iter.edge()));
+      iter.UpdateToAndIncrement(
+          NodeProperties::GetValueInput(unified_return, 0));
+    }
+  }
+  call->RemoveAllInputs();
+  unified_return->RemoveAllInputs();
+}
+
+
+void JSInliner::InlineCall(Node* node) {
+  DCHECK_EQ(IrOpcode::kJSCallFunction, node->opcode());
+
+  ValueMatcher<Handle<JSFunction> > match(node->InputAt(0));
+  if (!match.HasValue()) {
+    return;
+  }
+
+  Handle<JSFunction> function = match.Value();
+  SmartArrayPointer<char> name = function->shared()->DebugName()->ToCString();

[Michael Starzinger, 2014/08/12 20:04:45]

nit: The "name" is only use for tracing, please move into the tracing blocks
(even though it's duplicated).

[sigurds, 2014/08/14 09:54:42]

Done.

+
+  if (function->shared()->native()) {
+    if (FLAG_trace_turbo_inlining) {
+      printf("Not Inlining %s into %s because inlinee is native\n", name.get(),

[Michael Starzinger, 2014/08/12 20:04:45]

nit: s/printf/PrintF/

[sigurds, 2014/08/14 09:54:42]

Done.

+             info_->shared_info()->DebugName()->ToCString().get());
+    }
+    return;
+  }
+
+  CompilationInfoWithZone info(function);
+
+  CHECK(Parser::Parse(&info));
+  StrictMode strict_mode = info.function()->strict_mode();
+  info.SetStrictMode(strict_mode);
+  info.SetOptimizing(BailoutId::None(), Handle<Code>(function->code()));
+  CHECK(Rewriter::Rewrite(&info));
+  CHECK(Scope::Analyze(&info));
+  CHECK_NE(NULL, info.scope());
+
+  if (info.scope()->arguments() != NULL) {
+    // For now do not inline functions that use their arguments array.
+    if (FLAG_trace_turbo_inlining) {
+      printf(

[Michael Starzinger, 2014/08/12 20:04:46]

nit: s/printf/PrintF/

[sigurds, 2014/08/14 09:54:42]

Done.

+          "Not Inlining %s into %s because inlinee uses arguments "
+          "array\n",
+          name.get(), info_->shared_info()->DebugName()->ToCString().get());
+    }
+    return;
+  }
+
+  if (!info.shared_info().is_null()) {
+    Handle<ScopeInfo> scope_info = ScopeInfo::Create(info.scope(), info.zone());
+    info.shared_info()->set_scope_info(*scope_info);
+  }
+  if (FLAG_trace_turbo_inlining) {
+    printf("Inlining %s into %s\n", name.get(),

[Michael Starzinger, 2014/08/12 20:04:46]

nit: s/printf/PrintF/

[sigurds, 2014/08/14 09:54:42]

Done.

+           info_->shared_info()->DebugName()->ToCString().get());
+  }
+
+  Graph graph(info_->zone());
+  graph.SetNextNodeId(jsgraph_->graph()->NodeCount());

[Michael Starzinger, 2014/08/12 20:04:45]

I assume this is only temporary for now that we don't copy the nodes from the
inlinee but rather create the nodes in place within the surrounding graph.
Correct?

[sigurds, 2014/08/14 09:54:41]

Yes. To copying the graph will follow as a separate cl, and then SetNextNodeId
can be removed again.

+  Typer typer(info_->zone());
+  CommonOperatorBuilder common(info_->zone());
+  JSGraph jsgraph(&graph, &common, &typer);
+  AstGraphBuilder graph_builder(&info, &jsgraph);
+  graph_builder.CreateGraph();
+
+  UnifyReturn(&jsgraph);

[Michael Starzinger, 2014/08/12 20:04:46]

On a high level it is terribly confusing when "jsgraph" and "graph" refers to
the outer or the inner graph. I think this should be cleaned up a bit. One
suggestion would be to have a class around the inner graph (e.g. InnerGraph,
SubGraph, Inlinee, ...) that has helper methods to perform mutations on the
inlinee. Having all of the inlining logic in static top-level methods smells
dangerous.

[sigurds, 2014/08/14 09:54:41]

I agree. Effectively, we are reimplementing the pipeline here, which we should
not. I'd like to integrate this code better with the pipeline, but not in this
CL.

I make it more clear for now who is the inlinee, I introduced the class Inlinee,
which also makes InlineAtCall more readable.

+
+  DoInline(jsgraph_->zone(), node, &info, &jsgraph);
+
+  jsgraph_->graph()->SetNextNodeId(graph.NodeCount());
+}
+}
+}
+}  // namespace v8::internal::compiler