[turbofan] Initial support for polymorphic inlining.

src/compiler/js-inlining-heuristic.cc

Index: src/compiler/js-inlining-heuristic.cc
diff --git a/src/compiler/js-inlining-heuristic.cc b/src/compiler/js-inlining-heuristic.cc
index 6808c92e901e5be5e9e755b22ce59d1209cdc838..e741813845923a4f9688a169a986c9103bfc49e4 100644
--- a/src/compiler/js-inlining-heuristic.cc
+++ b/src/compiler/js-inlining-heuristic.cc
@@ -5,81 +5,128 @@
 #include "src/compiler/js-inlining-heuristic.h"
 
 #include "src/compilation-info.h"
+#include "src/compiler/common-operator.h"
 #include "src/compiler/node-matchers.h"
+#include "src/compiler/simplified-operator.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-Reduction JSInliningHeuristic::Reduce(Node* node) {
-  if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
+#define TRACE(...)                                      \
+  do {                                                  \
+    if (FLAG_trace_turbo_inlining) PrintF(__VA_ARGS__); \
+  } while (false)
 
-  // Check if we already saw that {node} before, and if so, just skip it.
-  if (seen_.find(node->id()) != seen_.end()) return NoChange();
-  seen_.insert(node->id());
+namespace {
 
-  Node* callee = node->InputAt(0);
-  HeapObjectMatcher match(callee);
-  if (!match.HasValue() || !match.Value()->IsJSFunction()) return NoChange();
-  Handle<JSFunction> function = Handle<JSFunction>::cast(match.Value());
-
-  // Functions marked with %SetForceInlineFlag are immediately inlined.
-  if (function->shared()->force_inline()) {
-    return inliner_.ReduceJSCall(node, function);
+int CollectFunctions(Node* node, Handle<JSFunction>* functions,
+                     int functions_size) {
+  DCHECK_NE(0u, functions_size);
+  HeapObjectMatcher m(node);
+  if (m.HasValue() && m.Value()->IsJSFunction()) {
+    functions[0] = Handle<JSFunction>::cast(m.Value());
+    return 1;
   }
-
-  // Handling of special inlining modes right away:
-  //  - For restricted inlining: stop all handling at this point.
-  //  - For stressing inlining: immediately handle all functions.
-  switch (mode_) {
-    case kRestrictedInlining:
-      return NoChange();
-    case kStressInlining:
-      return inliner_.ReduceJSCall(node, function);
-    case kGeneralInlining:
-      break;
+  if (m.IsPhi()) {
+    int const value_input_count = m.node()->op()->ValueInputCount();
+    if (value_input_count > functions_size) return 0;
+    for (int n = 0; n < value_input_count; ++n) {
+      HeapObjectMatcher m(node->InputAt(n));
+      if (!m.HasValue() || !m.Value()->IsJSFunction()) return 0;
+      functions[n] = Handle<JSFunction>::cast(m.Value());
+    }
+    return value_input_count;
   }
+  return 0;
+}
 
-  // ---------------------------------------------------------------------------
-  // Everything below this line is part of the inlining heuristic.
-  // ---------------------------------------------------------------------------
-
+bool CanInlineFunction(Handle<JSFunction> function) {
   // Built-in functions are handled by the JSBuiltinReducer.
-  if (function->shared()->HasBuiltinFunctionId()) return NoChange();
+  if (function->shared()->HasBuiltinFunctionId()) return false;
 
   // Don't inline builtins.
-  if (function->shared()->IsBuiltin()) return NoChange();
+  if (function->shared()->IsBuiltin()) return false;
 
   // Quick check on source code length to avoid parsing large candidate.
   if (function->shared()->SourceSize() > FLAG_max_inlined_source_size) {
-    return NoChange();
+    return false;
   }
 
   // Quick check on the size of the AST to avoid parsing large candidate.
   if (function->shared()->ast_node_count() > FLAG_max_inlined_nodes) {
+    return false;
+  }
+
+  // Avoid inlining across the boundary of asm.js code.
+  if (function->shared()->asm_function()) return false;
+  return true;
+}
+
+}  // namespace
+
+Reduction JSInliningHeuristic::Reduce(Node* node) {
+  if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
+
+  // Check if we already saw that {node} before, and if so, just skip it.
+  if (seen_.find(node->id()) != seen_.end()) return NoChange();
+  seen_.insert(node->id());
+
+  // Check if the {node} is an appropriate candidate for inlining.
+  Node* callee = node->InputAt(0);
+  Candidate candidate;
+  candidate.node = node;
+  candidate.num_functions =
+      CollectFunctions(callee, candidate.functions, kMaxCallPolymorphism);
+  if (candidate.num_functions == 0) {
+    return NoChange();
+  } else if (candidate.num_functions > 1 && !FLAG_polymorphic_inlining) {
+    TRACE(
+        "Not considering call site #%d:%s, because polymorphic inlining "
+        "is disabled\n",
+        node->id(), node->op()->mnemonic());
     return NoChange();
   }
 
-  // Avoid inlining within or across the boundary of asm.js code.
-  if (info_->shared_info()->asm_function()) return NoChange();
-  if (function->shared()->asm_function()) return NoChange();
+  // Functions marked with %SetForceInlineFlag are immediately inlined.
+  bool can_inline = false, force_inline = true;
+  for (int i = 0; i < candidate.num_functions; ++i) {
+    Handle<JSFunction> function = candidate.functions[i];
+    if (!function->shared()->force_inline()) {
+      force_inline = false;
+    }
+    if (CanInlineFunction(function)) {
+      can_inline = true;
+    }
+  }
+  if (force_inline) return InlineCandidate(candidate);
+  if (!can_inline) return NoChange();
 
   // Stop inlining once the maximum allowed level is reached.
   int level = 0;
   for (Node* frame_state = NodeProperties::GetFrameStateInput(node);
        frame_state->opcode() == IrOpcode::kFrameState;
        frame_state = NodeProperties::GetFrameStateInput(frame_state)) {
-    if (++level > FLAG_max_inlining_levels) return NoChange();
+    FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
+    if (frame_info.type() == FrameStateType::kJavaScriptFunction) {
+      if (++level > FLAG_max_inlining_levels) {
+        TRACE(
+            "Not considering call site #%d:%s, because inlining depth "
+            "%d exceeds maximum allowed level %d\n",
+            node->id(), node->op()->mnemonic(), level,
+            FLAG_max_inlining_levels);
+        return NoChange();
+      }
+    }
   }
 
   // Gather feedback on how often this call site has been hit before.
-  int calls = -1;  // Same default as CallICNexus::ExtractCallCount.
   if (node->opcode() == IrOpcode::kJSCallFunction) {
     CallFunctionParameters p = CallFunctionParametersOf(node->op());
     if (p.feedback().IsValid()) {
       CallICNexus nexus(p.feedback().vector(), p.feedback().slot());
-      calls = nexus.ExtractCallCount();
+      candidate.calls = nexus.ExtractCallCount();
     }
   } else {
     DCHECK_EQ(IrOpcode::kJSCallConstruct, node->opcode());
@@ -87,24 +134,30 @@ Reduction JSInliningHeuristic::Reduce(Node* node) {
     if (p.feedback().IsValid()) {
       int const extra_index =
           p.feedback().vector()->GetIndex(p.feedback().slot()) + 1;
-      Handle<Object> feedback_extra(p.feedback().vector()->get(extra_index),
-                                    function->GetIsolate());
+      Object* feedback_extra = p.feedback().vector()->get(extra_index);
       if (feedback_extra->IsSmi()) {
-        calls = Handle<Smi>::cast(feedback_extra)->value();
+        candidate.calls = Smi::cast(feedback_extra)->value();
       }
     }
   }
 
-  // ---------------------------------------------------------------------------
-  // Everything above this line is part of the inlining heuristic.
-  // ---------------------------------------------------------------------------
+  // Handling of special inlining modes right away:
+  //  - For restricted inlining: stop all handling at this point.
+  //  - For stressing inlining: immediately handle all functions.
+  switch (mode_) {
+    case kRestrictedInlining:
+      return NoChange();
+    case kStressInlining:
+      return InlineCandidate(candidate);
+    case kGeneralInlining:
+      break;
+  }
 
   // In the general case we remember the candidate for later.
-  candidates_.insert({function, node, calls});
+  candidates_.insert(candidate);
   return NoChange();
 }
 
-
 void JSInliningHeuristic::Finalize() {
   if (candidates_.empty()) return;  // Nothing to do without candidates.
   if (FLAG_trace_turbo_inlining) PrintCandidates();
@@ -120,15 +173,110 @@ void JSInliningHeuristic::Finalize() {
     candidates_.erase(i);
     // Make sure we don't try to inline dead candidate nodes.
     if (!candidate.node->IsDead()) {
-      Reduction r = inliner_.ReduceJSCall(candidate.node, candidate.function);
-      if (r.Changed()) {
-        cumulative_count_ += candidate.function->shared()->ast_node_count();
-        return;
-      }
+      Reduction const reduction = InlineCandidate(candidate);
+      if (reduction.Changed()) return;
     }
   }
 }
 
+Reduction JSInliningHeuristic::InlineCandidate(Candidate const& candidate) {
+  int const num_calls = candidate.num_functions;
+  Node* const node = candidate.node;
+  if (num_calls == 1) {
+    Handle<JSFunction> function = candidate.functions[0];
+    Reduction const reduction = inliner_.ReduceJSCall(node, function);
+    if (reduction.Changed()) {
+      cumulative_count_ += function->shared()->ast_node_count();
+    }
+    return reduction;
+  }
+
+  // Expand the JSCallFunction/JSCallConstruct node to a subgraph first if
+  // we have multiple known target functions.
+  DCHECK_LT(1, num_calls);
+  Node* calls[kMaxCallPolymorphism + 1];
+  Node* if_successes[kMaxCallPolymorphism];
+  Node* callee = NodeProperties::GetValueInput(node, 0);
+  Node* control = NodeProperties::GetControlInput(node);
+
+  // Setup the inputs for the cloned call nodes.
+  int const input_count = node->InputCount();
+  Node** inputs = graph()->zone()->NewArray<Node*>(input_count);
+  for (int i = 0; i < input_count; ++i) {
+    inputs[i] = node->InputAt(i);
+  }
+
+  // Create the appropriate control flow to dispatch to the cloned calls.
+  for (int i = 0; i < num_calls; ++i) {
+    Node* target = jsgraph()->HeapConstant(candidate.functions[i]);
+    if (i != (num_calls - 1)) {
+      Node* check =
+          graph()->NewNode(simplified()->ReferenceEqual(), callee, target);
+      Node* branch = graph()->NewNode(common()->Branch(), check, control);
+      control = graph()->NewNode(common()->IfFalse(), branch);
+      if_successes[i] = graph()->NewNode(common()->IfTrue(), branch);
+    } else {
+      if_successes[i] = control;
+    }
+
+    // The first input to the call is the actual target (which we specialize
+    // to the known {target}); the last input is the control dependency.
+    inputs[0] = target;
+    inputs[input_count - 1] = if_successes[i];
+    calls[i] = graph()->NewNode(node->op(), input_count, inputs);
+    if_successes[i] = graph()->NewNode(common()->IfSuccess(), calls[i]);
+  }
+
+  // Check if we have an exception projection for the call {node}.
+  Node* if_exception = nullptr;
+  for (Edge const edge : node->use_edges()) {
+    if (NodeProperties::IsControlEdge(edge) &&
+        edge.from()->opcode() == IrOpcode::kIfException) {
+      if_exception = edge.from();
+      break;
+    }
+  }
+  if (if_exception != nullptr) {
+    // Morph the {if_exception} projection into a join.
+    Node* if_exceptions[kMaxCallPolymorphism + 1];
+    for (int i = 0; i < num_calls; ++i) {
+      if_exceptions[i] =
+          graph()->NewNode(common()->IfException(), calls[i], calls[i]);
+    }
+    Node* control =
+        graph()->NewNode(common()->Merge(num_calls), num_calls, if_exceptions);

[brucedawson, 2016/09/12 18:08:00]

Probably not a bug, but this declaration of 'control' is confusing because there
is an identically named variable in the outer scope which is used before and
after this scope. Consider renaming?

The full set of new variable shadowing warnings from the experimental VC++
/analyze (static code analysis) run for this file is:

v8\src\compiler\js-inlining-heuristic.cc(246) : warning C6246: Local declaration
of 'control' hides declaration of the same name in outer scope. For additional
information, see previous declaration at line '200' of
'c:\src\analyze_chromium\src\v8\src\compiler\js-inlining-heuristic.cc'.
v8\src\compiler\js-inlining-heuristic.cc(271) : warning C6246: Local declaration
of 'node' hides declaration of the same name in outer scope. For additional
information, see previous declaration at line '184' of
'c:\src\analyze_chromium\src\v8\src\compiler\js-inlining-heuristic.cc'.
v8\src\compiler\js-inlining-heuristic.cc(36) : warning C6246: Local declaration
of 'm' hides declaration of the same name in outer scope. For additional
information, see previous declaration at line '27' of
'c:\src\analyze_chromium\src\v8\src\compiler\js-inlining-heuristic.cc'.

Fixing is not required - do what makes sense.

+    if_exceptions[num_calls] = control;
+    Node* effect = graph()->NewNode(common()->EffectPhi(num_calls),
+                                    num_calls + 1, if_exceptions);
+    Node* value = graph()->NewNode(
+        common()->Phi(MachineRepresentation::kTagged, num_calls), num_calls + 1,
+        if_exceptions);
+    ReplaceWithValue(if_exception, value, effect, control);
+  }
+
+  // Morph the call site into the dispatched call sites.
+  control =
+      graph()->NewNode(common()->Merge(num_calls), num_calls, if_successes);
+  calls[num_calls] = control;
+  Node* effect =
+      graph()->NewNode(common()->EffectPhi(num_calls), num_calls + 1, calls);
+  Node* value =
+      graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, num_calls),
+                       num_calls + 1, calls);
+  ReplaceWithValue(node, value, effect, control);
+
+  // Inline the individual, cloned call sites.
+  for (int i = 0; i < num_calls; ++i) {
+    Handle<JSFunction> function = candidate.functions[i];
+    Node* node = calls[i];
+    Reduction const reduction = inliner_.ReduceJSCall(node, function);
+    if (reduction.Changed()) {
+      cumulative_count_ += function->shared()->ast_node_count();
+    }
+  }
+
+  return Replace(value);
+}
 
 bool JSInliningHeuristic::CandidateCompare::operator()(
     const Candidate& left, const Candidate& right) const {
@@ -138,18 +286,31 @@ bool JSInliningHeuristic::CandidateCompare::operator()(
   return left.node < right.node;
 }
 
-
 void JSInliningHeuristic::PrintCandidates() {
   PrintF("Candidates for inlining (size=%zu):\n", candidates_.size());
   for (const Candidate& candidate : candidates_) {
-    PrintF("  id:%d, calls:%d, size[source]:%d, size[ast]:%d / %s\n",
-           candidate.node->id(), candidate.calls,
-           candidate.function->shared()->SourceSize(),
-           candidate.function->shared()->ast_node_count(),
-           candidate.function->shared()->DebugName()->ToCString().get());
+    PrintF("  #%d:%s, calls:%d\n", candidate.node->id(),
+           candidate.node->op()->mnemonic(), candidate.calls);
+    for (int i = 0; i < candidate.num_functions; ++i) {
+      Handle<JSFunction> function = candidate.functions[i];
+      PrintF("  - size[source]:%d, size[ast]:%d, name: %s\n",
+             function->shared()->SourceSize(),
+             function->shared()->ast_node_count(),
+             function->shared()->DebugName()->ToCString().get());
+    }
   }
 }
 
+Graph* JSInliningHeuristic::graph() const { return jsgraph()->graph(); }
+
+CommonOperatorBuilder* JSInliningHeuristic::common() const {
+  return jsgraph()->common();
+}
+
+SimplifiedOperatorBuilder* JSInliningHeuristic::simplified() const {
+  return jsgraph()->simplified();
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8