[turbofan] Initial support for polymorphic inlining.

src/compiler/js-inlining-heuristic.cc

 // Copyright 2015 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/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 {
 
+#define TRACE(...)                                      \
+  do {                                                  \
+    if (FLAG_trace_turbo_inlining) PrintF(__VA_ARGS__); \
+  } while (false)
+
+namespace {
+
+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;
+  }
+  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;
+}
+
+bool CanInlineFunction(Handle<JSFunction> function) {
+  // Built-in functions are handled by the JSBuiltinReducer.
+  if (function->shared()->HasBuiltinFunctionId()) return false;
+
+  // Don't inline builtins.
+  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 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);
-  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);
-  }
-
-  // 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;
-  }
-
-  // ---------------------------------------------------------------------------
-  // Everything below this line is part of the inlining heuristic.
-  // ---------------------------------------------------------------------------
-
-  // Built-in functions are handled by the JSBuiltinReducer.
-  if (function->shared()->HasBuiltinFunctionId()) return NoChange();
-
-  // Don't inline builtins.
-  if (function->shared()->IsBuiltin()) return NoChange();
-
-  // Quick check on source code length to avoid parsing large candidate.
-  if (function->shared()->SourceSize() > FLAG_max_inlined_source_size) {
+  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();
   }
 
-  // Quick check on the size of the AST to avoid parsing large candidate.
-  if (function->shared()->ast_node_count() > FLAG_max_inlined_nodes) {
-    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;
+    }
   }
-
-  // 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();
+  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());
     CallConstructParameters p = CallConstructParametersOf(node->op());
     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();
 
   // We inline at most one candidate in every iteration of the fixpoint.
   // This is to ensure that we don't consume the full inlining budget
   // on things that aren't called very often.
   // TODO(bmeurer): Use std::priority_queue instead of std::set here.
   while (!candidates_.empty()) {
     if (cumulative_count_ > FLAG_max_inlined_nodes_cumulative) return;
     auto i = candidates_.begin();
     Candidate candidate = *i;
     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 {
   if (left.calls != right.calls) {
     return left.calls > right.calls;
   }
   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