LCOV - code coverage report
Current view: top level - src/compiler - js-inlining-heuristic.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 104 123 84.6 %
Date: 2017-04-26 Functions: 5 10 50.0 %

          Line data    Source code
       1             : // Copyright 2015 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-heuristic.h"
       6             : 
       7             : #include "src/compilation-info.h"
       8             : #include "src/compiler/common-operator.h"
       9             : #include "src/compiler/node-matchers.h"
      10             : #include "src/compiler/simplified-operator.h"
      11             : #include "src/objects-inl.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17             : #define TRACE(...)                                      \
      18             :   do {                                                  \
      19             :     if (FLAG_trace_turbo_inlining) PrintF(__VA_ARGS__); \
      20             :   } while (false)
      21             : 
      22             : namespace {
      23             : 
      24      293431 : int CollectFunctions(Node* node, Handle<JSFunction>* functions,
      25             :                      int functions_size, Handle<SharedFunctionInfo>& shared) {
      26             :   DCHECK_NE(0, functions_size);
      27             :   HeapObjectMatcher m(node);
      28      560946 :   if (m.HasValue() && m.Value()->IsJSFunction()) {
      29      267329 :     functions[0] = Handle<JSFunction>::cast(m.Value());
      30      267329 :     return 1;
      31             :   }
      32       26102 :   if (m.IsPhi()) {
      33        3059 :     int const value_input_count = m.node()->op()->ValueInputCount();
      34        3059 :     if (value_input_count > functions_size) return 0;
      35        1526 :     for (int n = 0; n < value_input_count; ++n) {
      36             :       HeapObjectMatcher m(node->InputAt(n));
      37        6023 :       if (!m.HasValue() || !m.Value()->IsJSFunction()) return 0;
      38        1526 :       functions[n] = Handle<JSFunction>::cast(m.Value());
      39             :     }
      40             :     return value_input_count;
      41             :   }
      42       23043 :   if (m.IsJSCreateClosure()) {
      43        1227 :     CreateClosureParameters const& p = CreateClosureParametersOf(m.op());
      44        1227 :     functions[0] = Handle<JSFunction>::null();
      45        1227 :     shared = p.shared_info();
      46        1227 :     return 1;
      47             :   }
      48             :   return 0;
      49             : }
      50             : 
      51      268833 : bool CanInlineFunction(Handle<SharedFunctionInfo> shared) {
      52             :   // Built-in functions are handled by the JSBuiltinReducer.
      53      268833 :   if (shared->HasBuiltinFunctionId()) return false;
      54             : 
      55             :   // Only choose user code for inlining.
      56      183604 :   if (!shared->IsUserJavaScript()) return false;
      57             : 
      58             :   // Quick check on the size of the AST to avoid parsing large candidate.
      59      121851 :   if (shared->ast_node_count() > FLAG_max_inlined_nodes) {
      60             :     return false;
      61             :   }
      62             : 
      63             :   // Avoid inlining across the boundary of asm.js code.
      64      121118 :   if (shared->asm_function()) return false;
      65      120608 :   return true;
      66             : }
      67             : 
      68             : }  // namespace
      69             : 
      70    32312723 : Reduction JSInliningHeuristic::Reduce(Node* node) {
      71    31530655 :   if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
      72             : 
      73             :   // Check if we already saw that {node} before, and if so, just skip it.
      74      737432 :   if (seen_.find(node->id()) != seen_.end()) return NoChange();
      75      586862 :   seen_.insert(node->id());
      76             : 
      77             :   // Check if the {node} is an appropriate candidate for inlining.
      78             :   Node* callee = node->InputAt(0);
      79             :   Candidate candidate;
      80      293431 :   candidate.node = node;
      81             :   candidate.num_functions = CollectFunctions(
      82      293431 :       callee, candidate.functions, kMaxCallPolymorphism, candidate.shared_info);
      83      293430 :   if (candidate.num_functions == 0) {
      84             :     return NoChange();
      85      268643 :   } else if (candidate.num_functions > 1 && !FLAG_polymorphic_inlining) {
      86           0 :     TRACE(
      87             :         "Not considering call site #%d:%s, because polymorphic inlining "
      88             :         "is disabled\n",
      89             :         node->id(), node->op()->mnemonic());
      90             :     return NoChange();
      91             :   }
      92             : 
      93             :   // Functions marked with %SetForceInlineFlag are immediately inlined.
      94             :   bool can_inline = false, force_inline = true;
      95      268833 :   for (int i = 0; i < candidate.num_functions; ++i) {
      96             :     Handle<SharedFunctionInfo> shared =
      97      268832 :         candidate.functions[i].is_null()
      98             :             ? candidate.shared_info
      99      268832 :             : handle(candidate.functions[i]->shared());
     100      268833 :     if (!shared->force_inline()) {
     101             :       force_inline = false;
     102             :     }
     103      268833 :     if (CanInlineFunction(shared)) {
     104             :       can_inline = true;
     105             :     }
     106             :   }
     107      268644 :   if (force_inline) return InlineCandidate(candidate);
     108      264404 :   if (!can_inline) return NoChange();
     109             : 
     110             :   // Stop inlining once the maximum allowed level is reached.
     111             :   int level = 0;
     112      562692 :   for (Node* frame_state = NodeProperties::GetFrameStateInput(node);
     113             :        frame_state->opcode() == IrOpcode::kFrameState;
     114             :        frame_state = NodeProperties::GetFrameStateInput(frame_state)) {
     115      161425 :     FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
     116      161425 :     if (FrameStateFunctionInfo::IsJSFunctionType(frame_info.type())) {
     117      145290 :       if (++level > FLAG_max_inlining_levels) {
     118          32 :         TRACE(
     119             :             "Not considering call site #%d:%s, because inlining depth "
     120             :             "%d exceeds maximum allowed level %d\n",
     121             :             node->id(), node->op()->mnemonic(), level,
     122             :             FLAG_max_inlining_levels);
     123             :         return NoChange();
     124             :       }
     125             :     }
     126             :   }
     127             : 
     128             :   // Gather feedback on how often this call site has been hit before.
     129      119921 :   if (node->opcode() == IrOpcode::kJSCall) {
     130      117900 :     CallParameters const p = CallParametersOf(node->op());
     131      117900 :     candidate.frequency = p.frequency();
     132             :   } else {
     133        2021 :     ConstructParameters const p = ConstructParametersOf(node->op());
     134        2021 :     candidate.frequency = p.frequency();
     135             :   }
     136             : 
     137             :   // Handling of special inlining modes right away:
     138             :   //  - For restricted inlining: stop all handling at this point.
     139             :   //  - For stressing inlining: immediately handle all functions.
     140      119921 :   switch (mode_) {
     141             :     case kRestrictedInlining:
     142             :       return NoChange();
     143             :     case kStressInlining:
     144           0 :       return InlineCandidate(candidate);
     145             :     case kGeneralInlining:
     146             :       break;
     147             :   }
     148             : 
     149             :   // In the general case we remember the candidate for later.
     150             :   candidates_.insert(candidate);
     151             :   return NoChange();
     152             : }
     153             : 
     154      429073 : void JSInliningHeuristic::Finalize() {
     155      429073 :   if (candidates_.empty()) return;  // Nothing to do without candidates.
     156       58514 :   if (FLAG_trace_turbo_inlining) PrintCandidates();
     157             : 
     158             :   // We inline at most one candidate in every iteration of the fixpoint.
     159             :   // This is to ensure that we don't consume the full inlining budget
     160             :   // on things that aren't called very often.
     161             :   // TODO(bmeurer): Use std::priority_queue instead of std::set here.
     162       65677 :   while (!candidates_.empty()) {
     163      119621 :     if (cumulative_count_ > FLAG_max_inlined_nodes_cumulative) return;
     164             :     auto i = candidates_.begin();
     165       62544 :     Candidate candidate = *i;
     166             :     candidates_.erase(i);
     167             :     // Only include candidates that we've successfully called before.
     168             :     // The candidate list is sorted, so we can exit at the first occurance of
     169             :     // frequency 0 in the list.
     170       62544 :     if (candidate.frequency <= 0.0) return;
     171             :     // Make sure we don't try to inline dead candidate nodes.
     172       81786 :     if (!candidate.node->IsDead()) {
     173       40893 :       Reduction const reduction = InlineCandidate(candidate);
     174       40893 :       if (reduction.Changed()) return;
     175             :     }
     176             :   }
     177             : }
     178             : 
     179       45363 : Reduction JSInliningHeuristic::InlineCandidate(Candidate const& candidate) {
     180       45133 :   int const num_calls = candidate.num_functions;
     181       45363 :   Node* const node = candidate.node;
     182       45133 :   if (num_calls == 1) {
     183             :     Handle<SharedFunctionInfo> shared =
     184             :         candidate.functions[0].is_null()
     185             :             ? candidate.shared_info
     186       45060 :             : handle(candidate.functions[0]->shared());
     187       45060 :     Reduction const reduction = inliner_.ReduceJSCall(node);
     188       45060 :     if (reduction.Changed()) {
     189       37880 :       cumulative_count_ += shared->ast_node_count();
     190             :     }
     191       45060 :     return reduction;
     192             :   }
     193             : 
     194             :   // Expand the JSCall/JSConstruct node to a subgraph first if
     195             :   // we have multiple known target functions.
     196             :   DCHECK_LT(1, num_calls);
     197             :   Node* calls[kMaxCallPolymorphism + 1];
     198             :   Node* if_successes[kMaxCallPolymorphism];
     199          73 :   Node* callee = NodeProperties::GetValueInput(node, 0);
     200          73 :   Node* fallthrough_control = NodeProperties::GetControlInput(node);
     201             : 
     202             :   // Setup the inputs for the cloned call nodes.
     203             :   int const input_count = node->InputCount();
     204         146 :   Node** inputs = graph()->zone()->NewArray<Node*>(input_count);
     205         559 :   for (int i = 0; i < input_count; ++i) {
     206         972 :     inputs[i] = node->InputAt(i);
     207             :   }
     208             : 
     209             :   // Create the appropriate control flow to dispatch to the cloned calls.
     210         230 :   for (int i = 0; i < num_calls; ++i) {
     211             :     // TODO(2206): Make comparison be based on underlying SharedFunctionInfo
     212             :     // instead of the target JSFunction reference directly.
     213         230 :     Node* target = jsgraph()->HeapConstant(candidate.functions[i]);
     214         230 :     if (i != (num_calls - 1)) {
     215             :       Node* check =
     216         157 :           graph()->NewNode(simplified()->ReferenceEqual(), callee, target);
     217             :       Node* branch =
     218         157 :           graph()->NewNode(common()->Branch(), check, fallthrough_control);
     219         157 :       fallthrough_control = graph()->NewNode(common()->IfFalse(), branch);
     220         314 :       if_successes[i] = graph()->NewNode(common()->IfTrue(), branch);
     221             :     } else {
     222          73 :       if_successes[i] = fallthrough_control;
     223             :     }
     224             : 
     225             :     // The first input to the call is the actual target (which we specialize
     226             :     // to the known {target}); the last input is the control dependency.
     227         230 :     inputs[0] = target;
     228         230 :     inputs[input_count - 1] = if_successes[i];
     229             :     calls[i] = if_successes[i] =
     230         230 :         graph()->NewNode(node->op(), input_count, inputs);
     231             :   }
     232             : 
     233             :   // Check if we have an exception projection for the call {node}.
     234          73 :   Node* if_exception = nullptr;
     235          73 :   if (NodeProperties::IsExceptionalCall(node, &if_exception)) {
     236             :     Node* if_exceptions[kMaxCallPolymorphism + 1];
     237           0 :     for (int i = 0; i < num_calls; ++i) {
     238           0 :       if_successes[i] = graph()->NewNode(common()->IfSuccess(), calls[i]);
     239             :       if_exceptions[i] =
     240           0 :           graph()->NewNode(common()->IfException(), calls[i], calls[i]);
     241             :     }
     242             : 
     243             :     // Morph the {if_exception} projection into a join.
     244             :     Node* exception_control =
     245           0 :         graph()->NewNode(common()->Merge(num_calls), num_calls, if_exceptions);
     246           0 :     if_exceptions[num_calls] = exception_control;
     247             :     Node* exception_effect = graph()->NewNode(common()->EffectPhi(num_calls),
     248           0 :                                               num_calls + 1, if_exceptions);
     249             :     Node* exception_value = graph()->NewNode(
     250             :         common()->Phi(MachineRepresentation::kTagged, num_calls), num_calls + 1,
     251           0 :         if_exceptions);
     252             :     ReplaceWithValue(if_exception, exception_value, exception_effect,
     253          73 :                      exception_control);
     254             :   }
     255             : 
     256             :   // Morph the original call site into a join of the dispatched call sites.
     257             :   Node* control =
     258         146 :       graph()->NewNode(common()->Merge(num_calls), num_calls, if_successes);
     259          73 :   calls[num_calls] = control;
     260             :   Node* effect =
     261         219 :       graph()->NewNode(common()->EffectPhi(num_calls), num_calls + 1, calls);
     262             :   Node* value =
     263             :       graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, num_calls),
     264         146 :                        num_calls + 1, calls);
     265             :   ReplaceWithValue(node, value, effect, control);
     266             : 
     267             :   // Inline the individual, cloned call sites.
     268         303 :   for (int i = 0; i < num_calls; ++i) {
     269         230 :     Handle<JSFunction> function = candidate.functions[i];
     270         230 :     Node* node = calls[i];
     271         230 :     Reduction const reduction = inliner_.ReduceJSCall(node);
     272         230 :     if (reduction.Changed()) {
     273             :       // Killing the call node is not strictly necessary, but it is safer to
     274             :       // make sure we do not resurrect the node.
     275         150 :       node->Kill();
     276         150 :       cumulative_count_ += function->shared()->ast_node_count();
     277             :     }
     278             :   }
     279             : 
     280             :   return Replace(value);
     281             : }
     282             : 
     283           0 : bool JSInliningHeuristic::CandidateCompare::operator()(
     284             :     const Candidate& left, const Candidate& right) const {
     285      515220 :   if (left.frequency > right.frequency) {
     286             :     return true;
     287      501753 :   } else if (left.frequency < right.frequency) {
     288             :     return false;
     289             :   } else {
     290     1477500 :     return left.node->id() > right.node->id();
     291             :   }
     292             : }
     293             : 
     294           0 : void JSInliningHeuristic::PrintCandidates() {
     295           0 :   PrintF("Candidates for inlining (size=%zu):\n", candidates_.size());
     296           0 :   for (const Candidate& candidate : candidates_) {
     297             :     PrintF("  #%d:%s, frequency:%g\n", candidate.node->id(),
     298           0 :            candidate.node->op()->mnemonic(), candidate.frequency);
     299           0 :     for (int i = 0; i < candidate.num_functions; ++i) {
     300             :       Handle<SharedFunctionInfo> shared =
     301           0 :           candidate.functions[i].is_null()
     302             :               ? candidate.shared_info
     303           0 :               : handle(candidate.functions[i]->shared());
     304             :       PrintF("  - size:%d, name: %s\n", shared->ast_node_count(),
     305           0 :              shared->DebugName()->ToCString().get());
     306             :     }
     307             :   }
     308           0 : }
     309             : 
     310        1150 : Graph* JSInliningHeuristic::graph() const { return jsgraph()->graph(); }
     311             : 
     312         690 : CommonOperatorBuilder* JSInliningHeuristic::common() const {
     313         690 :   return jsgraph()->common();
     314             : }
     315             : 
     316         157 : SimplifiedOperatorBuilder* JSInliningHeuristic::simplified() const {
     317         157 :   return jsgraph()->simplified();
     318             : }
     319             : 
     320             : }  // namespace compiler
     321             : }  // namespace internal
     322             : }  // namespace v8

Generated by: LCOV version 1.10