LCOV - code coverage report
Current view: top level - src/compiler - js-inlining-heuristic.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 214 250 85.6 %
Date: 2019-02-19 Functions: 14 18 77.8 %

          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/compiler/common-operator.h"
       8             : #include "src/compiler/compiler-source-position-table.h"
       9             : #include "src/compiler/node-matchers.h"
      10             : #include "src/compiler/simplified-operator.h"
      11             : #include "src/objects-inl.h"
      12             : #include "src/optimized-compilation-info.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : 
      18             : #define TRACE(...)                                      \
      19             :   do {                                                  \
      20             :     if (FLAG_trace_turbo_inlining) PrintF(__VA_ARGS__); \
      21             :   } while (false)
      22             : 
      23             : namespace {
      24             : 
      25      591065 : int CollectFunctions(Node* node, Handle<JSFunction>* functions,
      26             :                      Handle<BytecodeArray>* bytecode, int functions_size,
      27             :                      Handle<SharedFunctionInfo>& shared, Isolate* isolate) {
      28             :   DCHECK_NE(0, functions_size);
      29             :   HeapObjectMatcher m(node);
      30      786081 :   if (m.HasValue() && m.Value()->IsJSFunction()) {
      31       96628 :     functions[0] = Handle<JSFunction>::cast(m.Value());
      32       96628 :     if (functions[0]->shared()->HasBytecodeArray()) {
      33      168072 :       bytecode[0] = handle(functions[0]->shared()->GetBytecodeArray(), isolate);
      34             :     }
      35             :     return 1;
      36             :   }
      37      494437 :   if (m.IsPhi()) {
      38       21408 :     int const value_input_count = m.node()->op()->ValueInputCount();
      39       21408 :     if (value_input_count > functions_size) return 0;
      40        1274 :     for (int n = 0; n < value_input_count; ++n) {
      41             :       HeapObjectMatcher m(node->InputAt(n));
      42       25034 :       if (!m.HasValue() || !m.Value()->IsJSFunction()) return 0;
      43        1274 :       functions[n] = Handle<JSFunction>::cast(m.Value());
      44        1274 :       if (functions[n]->shared()->HasBytecodeArray()) {
      45             :         bytecode[n] =
      46        2226 :             handle(functions[n]->shared()->GetBytecodeArray(), isolate);
      47             :       }
      48             :     }
      49             :     return value_input_count;
      50             :   }
      51      473029 :   if (m.IsJSCreateClosure()) {
      52       24692 :     CreateClosureParameters const& p = CreateClosureParametersOf(m.op());
      53       24694 :     functions[0] = Handle<JSFunction>::null();
      54       24694 :     shared = p.shared_info();
      55       24694 :     if (shared->HasBytecodeArray()) {
      56       46279 :       bytecode[0] = handle(shared->GetBytecodeArray(), isolate);
      57             :     }
      58             :     return 1;
      59             :   }
      60             :   return 0;
      61             : }
      62             : 
      63      121832 : bool IsSmallInlineFunction(Handle<BytecodeArray> bytecode) {
      64             :   // Forcibly inline small functions.
      65             :   // Don't forcibly inline functions that weren't compiled yet.
      66      229095 :   if (!bytecode.is_null() &&
      67      107263 :       bytecode->length() <= FLAG_max_inlined_bytecode_size_small) {
      68             :     return true;
      69             :   }
      70       98460 :   return false;
      71             : }
      72             : 
      73             : }  // namespace
      74             : 
      75    36829570 : Reduction JSInliningHeuristic::Reduce(Node* node) {
      76    34730806 :   if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
      77             : 
      78             :   // Check if we already saw that {node} before, and if so, just skip it.
      79     1439397 :   if (seen_.find(node->id()) != seen_.end()) return NoChange();
      80     1182136 :   seen_.insert(node->id());
      81             : 
      82             :   // Check if the {node} is an appropriate candidate for inlining.
      83             :   Node* callee = node->InputAt(0);
      84             :   Candidate candidate;
      85      591068 :   candidate.node = node;
      86             :   candidate.num_functions =
      87             :       CollectFunctions(callee, candidate.functions, candidate.bytecode,
      88      591068 :                        kMaxCallPolymorphism, candidate.shared_info, isolate());
      89      591067 :   if (candidate.num_functions == 0) {
      90             :     return NoChange();
      91      121577 :   } else if (candidate.num_functions > 1 && !FLAG_polymorphic_inlining) {
      92           0 :     TRACE(
      93             :         "Not considering call site #%d:%s, because polymorphic inlining "
      94             :         "is disabled\n",
      95             :         node->id(), node->op()->mnemonic());
      96             :     return NoChange();
      97             :   }
      98             : 
      99             :   bool can_inline = false, small_inline = true;
     100      121577 :   candidate.total_size = 0;
     101      121577 :   Node* frame_state = NodeProperties::GetFrameStateInput(node);
     102      243409 :   FrameStateInfo const& frame_info = FrameStateInfoOf(frame_state->op());
     103             :   Handle<SharedFunctionInfo> frame_shared_info;
     104      243408 :   for (int i = 0; i < candidate.num_functions; ++i) {
     105             :     Handle<SharedFunctionInfo> shared =
     106      121831 :         candidate.functions[i].is_null()
     107             :             ? candidate.shared_info
     108      437934 :             : handle(candidate.functions[i]->shared(), isolate());
     109      121832 :     candidate.can_inline_function[i] = shared->IsInlineable();
     110             :     // Do not allow direct recursion i.e. f() -> f(). We still allow indirect
     111             :     // recurion like f() -> g() -> f(). The indirect recursion is helpful in
     112             :     // cases where f() is a small dispatch function that calls the appropriate
     113             :     // function. In the case of direct recursion, we only have some static
     114             :     // information for the first level of inlining and it may not be that useful
     115             :     // to just inline one level in recursive calls. In some cases like tail
     116             :     // recursion we may benefit from recursive inlining, if we have additional
     117             :     // analysis that converts them to iterative implementations. Though it is
     118             :     // not obvious if such an anlysis is needed.
     119      243620 :     if (frame_info.shared_info().ToHandle(&frame_shared_info) &&
     120             :         *frame_shared_info == *shared) {
     121        5816 :       TRACE("Not considering call site #%d:%s, because of recursive inlining\n",
     122             :             node->id(), node->op()->mnemonic());
     123        5816 :       candidate.can_inline_function[i] = false;
     124             :     }
     125      121832 :     Handle<BytecodeArray> bytecode = candidate.bytecode[i];
     126      121832 :     if (candidate.can_inline_function[i]) {
     127             :       can_inline = true;
     128       99838 :       candidate.total_size += bytecode->length();
     129             :     }
     130      121832 :     if (!IsSmallInlineFunction(bytecode)) {
     131             :       small_inline = false;
     132             :     }
     133             :   }
     134      121577 :   if (!can_inline) return NoChange();
     135             : 
     136             :   // Gather feedback on how often this call site has been hit before.
     137       99795 :   if (node->opcode() == IrOpcode::kJSCall) {
     138       92948 :     CallParameters const p = CallParametersOf(node->op());
     139       92948 :     candidate.frequency = p.frequency();
     140             :   } else {
     141        6847 :     ConstructParameters const p = ConstructParametersOf(node->op());
     142        6847 :     candidate.frequency = p.frequency();
     143             :   }
     144             : 
     145             :   // Handling of special inlining modes right away:
     146             :   //  - For restricted inlining: stop all handling at this point.
     147             :   //  - For stressing inlining: immediately handle all functions.
     148       99795 :   switch (mode_) {
     149             :     case kRestrictedInlining:
     150             :       return NoChange();
     151             :     case kStressInlining:
     152           0 :       return InlineCandidate(candidate, false);
     153             :     case kGeneralInlining:
     154             :       break;
     155             :   }
     156             : 
     157             :   // Don't consider a {candidate} whose frequency is below the
     158             :   // threshold, i.e. a call site that is only hit once every N
     159             :   // invocations of the caller.
     160      196285 :   if (candidate.frequency.IsKnown() &&
     161       96815 :       candidate.frequency.value() < FLAG_min_inlining_frequency) {
     162             :     return NoChange();
     163             :   }
     164             : 
     165             :   // Forcibly inline small functions here. In the case of polymorphic inlining
     166             :   // small_inline is set only when all functions are small.
     167       86295 :   if (small_inline &&
     168       14778 :       cumulative_count_ < FLAG_max_inlined_bytecode_size_absolute) {
     169       14075 :     TRACE("Inlining small function(s) at call site #%d:%s\n", node->id(),
     170             :           node->op()->mnemonic());
     171       14075 :     return InlineCandidate(candidate, true);
     172             :   }
     173             : 
     174             :   // In the general case we remember the candidate for later.
     175             :   candidates_.insert(candidate);
     176             :   return NoChange();
     177             : }
     178             : 
     179      508718 : void JSInliningHeuristic::Finalize() {
     180      508718 :   if (candidates_.empty()) return;  // Nothing to do without candidates.
     181       52917 :   if (FLAG_trace_turbo_inlining) PrintCandidates();
     182             : 
     183             :   // We inline at most one candidate in every iteration of the fixpoint.
     184             :   // This is to ensure that we don't consume the full inlining budget
     185             :   // on things that aren't called very often.
     186             :   // TODO(bmeurer): Use std::priority_queue instead of std::set here.
     187       58366 :   while (!candidates_.empty()) {
     188             :     auto i = candidates_.begin();
     189       57442 :     Candidate candidate = *i;
     190             :     candidates_.erase(i);
     191             : 
     192             :     // Make sure we have some extra budget left, so that any small functions
     193             :     // exposed by this function would be given a chance to inline.
     194             :     double size_of_candidate =
     195       57442 :         candidate.total_size * FLAG_reserve_inline_budget_scale_factor;
     196       57442 :     int total_size = cumulative_count_ + static_cast<int>(size_of_candidate);
     197       57442 :     if (total_size > FLAG_max_inlined_bytecode_size_cumulative) {
     198             :       // Try if any smaller functions are available to inline.
     199        5444 :       continue;
     200             :     }
     201             : 
     202             :     // Make sure we don't try to inline dead candidate nodes.
     203       51998 :     if (!candidate.node->IsDead()) {
     204       51998 :       Reduction const reduction = InlineCandidate(candidate, false);
     205       51998 :       if (reduction.Changed()) return;
     206             :     }
     207             :   }
     208             : }
     209             : 
     210             : namespace {
     211             : 
     212             : struct NodeAndIndex {
     213             :   Node* node;
     214             :   int index;
     215             : };
     216             : 
     217          70 : bool CollectStateValuesOwnedUses(Node* node, Node* state_values,
     218             :                                  NodeAndIndex* uses_buffer, size_t* use_count,
     219             :                                  size_t max_uses) {
     220             :   // Only accumulate states that are not shared with other users.
     221          70 :   if (state_values->UseCount() > 1) return true;
     222         189 :   for (int i = 0; i < state_values->InputCount(); i++) {
     223          77 :     Node* input = state_values->InputAt(i);
     224          77 :     if (input->opcode() == IrOpcode::kStateValues) {
     225           0 :       if (!CollectStateValuesOwnedUses(node, input, uses_buffer, use_count,
     226           0 :                                        max_uses)) {
     227             :         return false;
     228             :       }
     229          77 :     } else if (input == node) {
     230          35 :       if (*use_count >= max_uses) return false;
     231          35 :       uses_buffer[*use_count] = {state_values, i};
     232          35 :       (*use_count)++;
     233             :     }
     234             :   }
     235             :   return true;
     236             : }
     237             : 
     238             : }  // namespace
     239             : 
     240         105 : Node* JSInliningHeuristic::DuplicateStateValuesAndRename(Node* state_values,
     241             :                                                          Node* from, Node* to,
     242             :                                                          StateCloneMode mode) {
     243             :   // Only rename in states that are not shared with other users. This needs to
     244             :   // be in sync with the condition in {CollectStateValuesOwnedUses}.
     245         105 :   if (state_values->UseCount() > 1) return state_values;
     246          70 :   Node* copy = mode == kChangeInPlace ? state_values : nullptr;
     247         448 :   for (int i = 0; i < state_values->InputCount(); i++) {
     248         154 :     Node* input = state_values->InputAt(i);
     249             :     Node* processed;
     250         154 :     if (input->opcode() == IrOpcode::kStateValues) {
     251           0 :       processed = DuplicateStateValuesAndRename(input, from, to, mode);
     252         154 :     } else if (input == from) {
     253             :       processed = to;
     254             :     } else {
     255             :       processed = input;
     256             :     }
     257         154 :     if (processed != input) {
     258          70 :       if (!copy) {
     259          35 :         copy = graph()->CloneNode(state_values);
     260             :       }
     261          70 :       copy->ReplaceInput(i, processed);
     262             :     }
     263             :   }
     264          70 :   return copy ? copy : state_values;
     265             : }
     266             : 
     267             : namespace {
     268             : 
     269          70 : bool CollectFrameStateUniqueUses(Node* node, Node* frame_state,
     270             :                                  NodeAndIndex* uses_buffer, size_t* use_count,
     271             :                                  size_t max_uses) {
     272             :   // Only accumulate states that are not shared with other users.
     273          70 :   if (frame_state->UseCount() > 1) return true;
     274          70 :   if (frame_state->InputAt(kFrameStateStackInput) == node) {
     275           0 :     if (*use_count >= max_uses) return false;
     276           0 :     uses_buffer[*use_count] = {frame_state, kFrameStateStackInput};
     277           0 :     (*use_count)++;
     278             :   }
     279          70 :   if (!CollectStateValuesOwnedUses(node,
     280             :                                    frame_state->InputAt(kFrameStateLocalsInput),
     281          70 :                                    uses_buffer, use_count, max_uses)) {
     282             :     return false;
     283             :   }
     284          70 :   return true;
     285             : }
     286             : 
     287             : }  // namespace
     288             : 
     289         140 : Node* JSInliningHeuristic::DuplicateFrameStateAndRename(Node* frame_state,
     290             :                                                         Node* from, Node* to,
     291             :                                                         StateCloneMode mode) {
     292             :   // Only rename in states that are not shared with other users. This needs to
     293             :   // be in sync with the condition in {DuplicateFrameStateAndRename}.
     294         140 :   if (frame_state->UseCount() > 1) return frame_state;
     295         105 :   Node* copy = mode == kChangeInPlace ? frame_state : nullptr;
     296         105 :   if (frame_state->InputAt(kFrameStateStackInput) == from) {
     297           0 :     if (!copy) {
     298           0 :       copy = graph()->CloneNode(frame_state);
     299             :     }
     300           0 :     copy->ReplaceInput(kFrameStateStackInput, to);
     301             :   }
     302             :   Node* locals = frame_state->InputAt(kFrameStateLocalsInput);
     303         105 :   Node* new_locals = DuplicateStateValuesAndRename(locals, from, to, mode);
     304         105 :   if (new_locals != locals) {
     305          35 :     if (!copy) {
     306          35 :       copy = graph()->CloneNode(frame_state);
     307             :     }
     308          35 :     copy->ReplaceInput(kFrameStateLocalsInput, new_locals);
     309             :   }
     310         105 :   return copy ? copy : frame_state;
     311             : }
     312             : 
     313         112 : bool JSInliningHeuristic::TryReuseDispatch(Node* node, Node* callee,
     314             :                                            Candidate const& candidate,
     315             :                                            Node** if_successes, Node** calls,
     316         140 :                                            Node** inputs, int input_count) {
     317             :   // We will try to reuse the control flow branch created for computing
     318             :   // the {callee} target of the call. We only reuse the branch if there
     319             :   // is no side-effect between the call and the branch, and if the callee is
     320             :   // only used as the target (and possibly also in the related frame states).
     321             : 
     322          42 :   int const num_calls = candidate.num_functions;
     323             : 
     324             :   DCHECK_EQ(IrOpcode::kPhi, callee->opcode());
     325             :   DCHECK_EQ(num_calls, callee->op()->ValueInputCount());
     326             : 
     327             :   // We are trying to match the following pattern:
     328             :   //
     329             :   //         C1     C2
     330             :   //          .     .
     331             :   //          |     |
     332             :   //         Merge(merge)  <-----------------+
     333             :   //           ^    ^                        |
     334             :   //  V1  V2   |    |         E1  E2         |
     335             :   //   .  .    |    +----+     .  .          |
     336             :   //   |  |    |         |     |  |          |
     337             :   //  Phi(callee)      EffectPhi(effect_phi) |
     338             :   //     ^                    ^              |
     339             :   //     |                    |              |
     340             :   //     +----+               |              |
     341             :   //     |    |               |              |
     342             :   //     |   StateValues      |              |
     343             :   //     |       ^            |              |
     344             :   //     +----+  |            |              |
     345             :   //     |    |  |            |              |
     346             :   //     |    FrameState      |              |
     347             :   //     |           ^        |              |
     348             :   //     |           |        |          +---+
     349             :   //     |           |        |          |   |
     350             :   //     +----+     Checkpoint(checkpoint)   |
     351             :   //     |    |           ^                  |
     352             :   //     |    StateValues |    +-------------+
     353             :   //     |        |       |    |
     354             :   //     +-----+  |       |    |
     355             :   //     |     |  |       |    |
     356             :   //     |     FrameState |    |
     357             :   //     |             ^  |    |
     358             :   //     +-----------+ |  |    |
     359             :   //                  Call(node)
     360             :   //                   |
     361             :   //                   |
     362             :   //                   .
     363             :   //
     364             :   // The {callee} here is a phi that merges the possible call targets, {node}
     365             :   // is the actual call that we will try to duplicate and connect to the
     366             :   // control that comes into {merge}. There can be a {checkpoint} between
     367             :   // the call and the calle phi.
     368             :   //
     369             :   // The idea is to get rid of the merge, effect phi and phi, then duplicate
     370             :   // the call (with all the frame states and such), and connect the duplicated
     371             :   // calls and states directly to the inputs of the ex-phi, ex-effect-phi and
     372             :   // ex-merge. The tricky part is to make sure that there is no interference
     373             :   // from the outside. In particular, there should not be any unaccounted uses
     374             :   // of the  phi, effect-phi and merge because we will remove them from
     375             :   // the graph.
     376             :   //
     377             :   //     V1              E1   C1  V2   E2               C2
     378             :   //     .                .    .  .    .                .
     379             :   //     |                |    |  |    |                |
     380             :   //     +----+           |    |  +----+                |
     381             :   //     |    |           |    |  |    |                |
     382             :   //     |   StateValues  |    |  |   StateValues       |
     383             :   //     |       ^        |    |  |       ^             |
     384             :   //     +----+  |        |    |  +----+  |             |
     385             :   //     |    |  |        |    |  |    |  |             |
     386             :   //     |    FrameState  |    |  |    FrameState       |
     387             :   //     |           ^    |    |  |           ^         |
     388             :   //     |           |    |    |  |           |         |
     389             :   //     |           |    |    |  |           |         |
     390             :   //     +----+     Checkpoint |  +----+     Checkpoint |
     391             :   //     |    |           ^    |  |    |           ^    |
     392             :   //     |    StateValues |    |  |    StateValues |    |
     393             :   //     |        |       |    |  |        |       |    |
     394             :   //     +-----+  |       |    |  +-----+  |       |    |
     395             :   //     |     |  |       |    |  |     |  |       |    |
     396             :   //     |     FrameState |    |  |     FrameState |    |
     397             :   //     |              ^ |    |  |              ^ |    |
     398             :   //     +-------------+| |    |  +-------------+| |    |
     399             :   //                   Call----+                Call----+
     400             :   //                     |                       |
     401             :   //                     +-------+  +------------+
     402             :   //                             |  |
     403             :   //                             Merge
     404             :   //                             EffectPhi
     405             :   //                             Phi
     406             :   //                              |
     407             :   //                             ...
     408             : 
     409             :   // If there is a control node between the callee computation
     410             :   // and the call, bail out.
     411          42 :   Node* merge = NodeProperties::GetControlInput(callee);
     412          42 :   if (NodeProperties::GetControlInput(node) != merge) return false;
     413             : 
     414             :   // If there is a non-checkpoint effect node between the callee computation
     415             :   // and the call, bail out. We will drop any checkpoint between the call and
     416             :   // the callee phi because the callee computation should have its own
     417             :   // checkpoint that the call can fall back to.
     418          70 :   Node* checkpoint = nullptr;
     419          84 :   Node* effect = NodeProperties::GetEffectInput(node);
     420          42 :   if (effect->opcode() == IrOpcode::kCheckpoint) {
     421             :     checkpoint = effect;
     422          42 :     if (NodeProperties::GetControlInput(checkpoint) != merge) return false;
     423          42 :     effect = NodeProperties::GetEffectInput(effect);
     424             :   }
     425          42 :   if (effect->opcode() != IrOpcode::kEffectPhi) return false;
     426          42 :   if (NodeProperties::GetControlInput(effect) != merge) return false;
     427             :   Node* effect_phi = effect;
     428             : 
     429             :   // The effect phi, the callee, the call and the checkpoint must be the only
     430             :   // users of the merge.
     431         238 :   for (Node* merge_use : merge->uses()) {
     432         252 :     if (merge_use != effect_phi && merge_use != callee && merge_use != node &&
     433          91 :         merge_use != checkpoint) {
     434             :       return false;
     435             :     }
     436             :   }
     437             : 
     438             :   // The effect phi must be only used by the checkpoint or the call.
     439         105 :   for (Node* effect_phi_use : effect_phi->uses()) {
     440          35 :     if (effect_phi_use != node && effect_phi_use != checkpoint) return false;
     441             :   }
     442             : 
     443             :   // We must replace the callee phi with the appropriate constant in
     444             :   // the entire subgraph reachable by inputs from the call (terminating
     445             :   // at phis and merges). Since we do not want to walk (and later duplicate)
     446             :   // the subgraph here, we limit the possible uses to this set:
     447             :   //
     448             :   // 1. In the call (as a target).
     449             :   // 2. The checkpoint between the call and the callee computation merge.
     450             :   // 3. The lazy deoptimization frame state.
     451             :   //
     452             :   // This corresponds to the most common pattern, where the function is
     453             :   // called with only local variables or constants as arguments.
     454             :   //
     455             :   // To check the uses, we first collect all the occurrences of callee in 1, 2
     456             :   // and 3, and then we check that all uses of callee are in the collected
     457             :   // occurrences. If there is an unaccounted use, we do not try to rewire
     458             :   // the control flow.
     459             :   //
     460             :   // Note: With CFG, this would be much easier and more robust - we would just
     461             :   // duplicate all the nodes between the merge and the call, replacing all
     462             :   // occurrences of the {callee} phi with the appropriate constant.
     463             : 
     464             :   // First compute the set of uses that are only reachable from 2 and 3.
     465             :   const size_t kMaxUses = 8;
     466             :   NodeAndIndex replaceable_uses[kMaxUses];
     467          35 :   size_t replaceable_uses_count = 0;
     468             : 
     469             :   // Collect the uses to check case 2.
     470             :   Node* checkpoint_state = nullptr;
     471          35 :   if (checkpoint) {
     472             :     checkpoint_state = checkpoint->InputAt(0);
     473          35 :     if (!CollectFrameStateUniqueUses(callee, checkpoint_state, replaceable_uses,
     474          35 :                                      &replaceable_uses_count, kMaxUses)) {
     475             :       return false;
     476             :     }
     477             :   }
     478             : 
     479             :   // Collect the uses to check case 3.
     480          35 :   Node* frame_state = NodeProperties::GetFrameStateInput(node);
     481          35 :   if (!CollectFrameStateUniqueUses(callee, frame_state, replaceable_uses,
     482          35 :                                    &replaceable_uses_count, kMaxUses)) {
     483             :     return false;
     484             :   }
     485             : 
     486             :   // Bail out if there is a use of {callee} that is not reachable from 1, 2
     487             :   // and 3.
     488         140 :   for (Edge edge : callee->use_edges()) {
     489             :     // Case 1 (use by the call as a target).
     490          70 :     if (edge.from() == node && edge.index() == 0) continue;
     491             :     // Case 2 and 3 - used in checkpoint and/or lazy deopt frame states.
     492             :     bool found = false;
     493           0 :     for (size_t i = 0; i < replaceable_uses_count; i++) {
     494         105 :       if (replaceable_uses[i].node == edge.from() &&
     495          35 :           replaceable_uses[i].index == edge.index()) {
     496             :         found = true;
     497             :         break;
     498             :       }
     499             :     }
     500          35 :     if (!found) return false;
     501             :   }
     502             : 
     503             :   // Clone the call and the framestate, including the uniquely reachable
     504             :   // state values, making sure that we replace the phi with the constant.
     505         105 :   for (int i = 0; i < num_calls; ++i) {
     506             :     // Clone the calls for each branch.
     507             :     // We need to specialize the calls to the correct target, effect, and
     508             :     // control. We also need to duplicate the checkpoint and the lazy
     509             :     // frame state, and change all the uses of the callee to the constant
     510             :     // callee.
     511             :     Node* target = callee->InputAt(i);
     512             :     Node* effect = effect_phi->InputAt(i);
     513             :     Node* control = merge->InputAt(i);
     514             : 
     515          70 :     if (checkpoint) {
     516             :       // Duplicate the checkpoint.
     517             :       Node* new_checkpoint_state = DuplicateFrameStateAndRename(
     518             :           checkpoint_state, callee, target,
     519          70 :           (i == num_calls - 1) ? kChangeInPlace : kCloneState);
     520             :       effect = graph()->NewNode(checkpoint->op(), new_checkpoint_state, effect,
     521             :                                 control);
     522             :     }
     523             : 
     524             :     // Duplicate the call.
     525             :     Node* new_lazy_frame_state = DuplicateFrameStateAndRename(
     526             :         frame_state, callee, target,
     527          70 :         (i == num_calls - 1) ? kChangeInPlace : kCloneState);
     528          70 :     inputs[0] = target;
     529          70 :     inputs[input_count - 3] = new_lazy_frame_state;
     530          70 :     inputs[input_count - 2] = effect;
     531          70 :     inputs[input_count - 1] = control;
     532          70 :     calls[i] = if_successes[i] =
     533          70 :         graph()->NewNode(node->op(), input_count, inputs);
     534             :   }
     535             : 
     536             :   // Mark the control inputs dead, so that we can kill the merge.
     537          35 :   node->ReplaceInput(input_count - 1, jsgraph()->Dead());
     538          35 :   callee->ReplaceInput(num_calls, jsgraph()->Dead());
     539          35 :   effect_phi->ReplaceInput(num_calls, jsgraph()->Dead());
     540          35 :   if (checkpoint) {
     541          35 :     checkpoint->ReplaceInput(2, jsgraph()->Dead());
     542             :   }
     543             : 
     544          35 :   merge->Kill();
     545          35 :   return true;
     546             : }
     547             : 
     548          70 : void JSInliningHeuristic::CreateOrReuseDispatch(Node* node, Node* callee,
     549             :                                                 Candidate const& candidate,
     550             :                                                 Node** if_successes,
     551             :                                                 Node** calls, Node** inputs,
     552          14 :                                                 int input_count) {
     553             :   SourcePositionTable::Scope position(
     554          42 :       source_positions_, source_positions_->GetSourcePosition(node));
     555          42 :   if (TryReuseDispatch(node, callee, candidate, if_successes, calls, inputs,
     556             :                        input_count)) {
     557          42 :     return;
     558             :   }
     559             : 
     560           7 :   Node* fallthrough_control = NodeProperties::GetControlInput(node);
     561           7 :   int const num_calls = candidate.num_functions;
     562             : 
     563             :   // Create the appropriate control flow to dispatch to the cloned calls.
     564          21 :   for (int i = 0; i < num_calls; ++i) {
     565             :     // TODO(2206): Make comparison be based on underlying SharedFunctionInfo
     566             :     // instead of the target JSFunction reference directly.
     567          14 :     Node* target = jsgraph()->HeapConstant(candidate.functions[i]);
     568          14 :     if (i != (num_calls - 1)) {
     569             :       Node* check =
     570           7 :           graph()->NewNode(simplified()->ReferenceEqual(), callee, target);
     571             :       Node* branch =
     572           7 :           graph()->NewNode(common()->Branch(), check, fallthrough_control);
     573           7 :       fallthrough_control = graph()->NewNode(common()->IfFalse(), branch);
     574          21 :       if_successes[i] = graph()->NewNode(common()->IfTrue(), branch);
     575             :     } else {
     576           7 :       if_successes[i] = fallthrough_control;
     577             :     }
     578             : 
     579             :     // Clone the calls for each branch.
     580             :     // The first input to the call is the actual target (which we specialize
     581             :     // to the known {target}); the last input is the control dependency.
     582             :     // We also specialize the new.target of JSConstruct {node}s if it refers
     583             :     // to the same node as the {node}'s target input, so that we can later
     584             :     // properly inline the JSCreate operations.
     585          14 :     if (node->opcode() == IrOpcode::kJSConstruct && inputs[0] == inputs[1]) {
     586           0 :       inputs[1] = target;
     587             :     }
     588          14 :     inputs[0] = target;
     589          14 :     inputs[input_count - 1] = if_successes[i];
     590          14 :     calls[i] = if_successes[i] =
     591          14 :         graph()->NewNode(node->op(), input_count, inputs);
     592             :   }
     593             : }
     594             : 
     595       66073 : Reduction JSInliningHeuristic::InlineCandidate(Candidate const& candidate,
     596             :                                                bool small_function) {
     597       66073 :   int const num_calls = candidate.num_functions;
     598       66073 :   Node* const node = candidate.node;
     599       66073 :   if (num_calls == 1) {
     600       66031 :     Reduction const reduction = inliner_.ReduceJSCall(node);
     601       66031 :     if (reduction.Changed()) {
     602       66020 :       cumulative_count_ += candidate.bytecode[0]->length();
     603             :     }
     604       66031 :     return reduction;
     605             :   }
     606             : 
     607             :   // Expand the JSCall/JSConstruct node to a subgraph first if
     608             :   // we have multiple known target functions.
     609             :   DCHECK_LT(1, num_calls);
     610             :   Node* calls[kMaxCallPolymorphism + 1];
     611             :   Node* if_successes[kMaxCallPolymorphism];
     612          42 :   Node* callee = NodeProperties::GetValueInput(node, 0);
     613             : 
     614             :   // Setup the inputs for the cloned call nodes.
     615             :   int const input_count = node->InputCount();
     616          84 :   Node** inputs = graph()->zone()->NewArray<Node*>(input_count);
     617         336 :   for (int i = 0; i < input_count; ++i) {
     618         588 :     inputs[i] = node->InputAt(i);
     619             :   }
     620             : 
     621             :   // Create the appropriate control flow to dispatch to the cloned calls.
     622             :   CreateOrReuseDispatch(node, callee, candidate, if_successes, calls, inputs,
     623          42 :                         input_count);
     624             : 
     625             :   // Check if we have an exception projection for the call {node}.
     626          42 :   Node* if_exception = nullptr;
     627          42 :   if (NodeProperties::IsExceptionalCall(node, &if_exception)) {
     628             :     Node* if_exceptions[kMaxCallPolymorphism + 1];
     629           0 :     for (int i = 0; i < num_calls; ++i) {
     630           0 :       if_successes[i] = graph()->NewNode(common()->IfSuccess(), calls[i]);
     631             :       if_exceptions[i] =
     632           0 :           graph()->NewNode(common()->IfException(), calls[i], calls[i]);
     633             :     }
     634             : 
     635             :     // Morph the {if_exception} projection into a join.
     636             :     Node* exception_control =
     637           0 :         graph()->NewNode(common()->Merge(num_calls), num_calls, if_exceptions);
     638           0 :     if_exceptions[num_calls] = exception_control;
     639             :     Node* exception_effect = graph()->NewNode(common()->EffectPhi(num_calls),
     640           0 :                                               num_calls + 1, if_exceptions);
     641             :     Node* exception_value = graph()->NewNode(
     642             :         common()->Phi(MachineRepresentation::kTagged, num_calls), num_calls + 1,
     643           0 :         if_exceptions);
     644             :     ReplaceWithValue(if_exception, exception_value, exception_effect,
     645          42 :                      exception_control);
     646             :   }
     647             : 
     648             :   // Morph the original call site into a join of the dispatched call sites.
     649             :   Node* control =
     650          84 :       graph()->NewNode(common()->Merge(num_calls), num_calls, if_successes);
     651          42 :   calls[num_calls] = control;
     652             :   Node* effect =
     653         126 :       graph()->NewNode(common()->EffectPhi(num_calls), num_calls + 1, calls);
     654             :   Node* value =
     655             :       graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, num_calls),
     656          84 :                        num_calls + 1, calls);
     657             :   ReplaceWithValue(node, value, effect, control);
     658             : 
     659             :   // Inline the individual, cloned call sites.
     660         126 :   for (int i = 0; i < num_calls; ++i) {
     661          84 :     Node* node = calls[i];
     662          84 :     if (small_function ||
     663           0 :         (candidate.can_inline_function[i] &&
     664           0 :          cumulative_count_ < FLAG_max_inlined_bytecode_size_cumulative)) {
     665          84 :       Reduction const reduction = inliner_.ReduceJSCall(node);
     666          84 :       if (reduction.Changed()) {
     667             :         // Killing the call node is not strictly necessary, but it is safer to
     668             :         // make sure we do not resurrect the node.
     669          84 :         node->Kill();
     670         168 :         cumulative_count_ += candidate.bytecode[i]->length();
     671             :       }
     672             :     }
     673             :   }
     674             : 
     675             :   return Replace(value);
     676             : }
     677             : 
     678      193744 : bool JSInliningHeuristic::CandidateCompare::operator()(
     679             :     const Candidate& left, const Candidate& right) const {
     680      193744 :   if (right.frequency.IsUnknown()) {
     681        1049 :     if (left.frequency.IsUnknown()) {
     682             :       // If left and right are both unknown then the ordering is indeterminate,
     683             :       // which breaks strict weak ordering requirements, so we fall back to the
     684             :       // node id as a tie breaker.
     685      296620 :       return left.node->id() > right.node->id();
     686             :     }
     687             :     return true;
     688      192695 :   } else if (left.frequency.IsUnknown()) {
     689             :     return false;
     690      192682 :   } else if (left.frequency.value() > right.frequency.value()) {
     691             :     return true;
     692      153060 :   } else if (left.frequency.value() < right.frequency.value()) {
     693             :     return false;
     694             :   } else {
     695      440241 :     return left.node->id() > right.node->id();
     696             :   }
     697             : }
     698             : 
     699           0 : void JSInliningHeuristic::PrintCandidates() {
     700           0 :   StdoutStream os;
     701           0 :   os << "Candidates for inlining (size=" << candidates_.size() << "):\n";
     702           0 :   for (const Candidate& candidate : candidates_) {
     703           0 :     os << "  #" << candidate.node->id() << ":"
     704           0 :        << candidate.node->op()->mnemonic()
     705           0 :        << ", frequency: " << candidate.frequency << std::endl;
     706           0 :     for (int i = 0; i < candidate.num_functions; ++i) {
     707             :       Handle<SharedFunctionInfo> shared =
     708           0 :           candidate.functions[i].is_null()
     709             :               ? candidate.shared_info
     710           0 :               : handle(candidate.functions[i]->shared(), isolate());
     711           0 :       PrintF("  - size:%d, name: %s\n", candidate.bytecode[i]->length(),
     712           0 :              shared->DebugName()->ToCString().get());
     713             :     }
     714           0 :   }
     715           0 : }
     716             : 
     717         420 : Graph* JSInliningHeuristic::graph() const { return jsgraph()->graph(); }
     718             : 
     719         147 : CommonOperatorBuilder* JSInliningHeuristic::common() const {
     720         147 :   return jsgraph()->common();
     721             : }
     722             : 
     723           7 : SimplifiedOperatorBuilder* JSInliningHeuristic::simplified() const {
     724           7 :   return jsgraph()->simplified();
     725             : }
     726             : 
     727             : #undef TRACE
     728             : 
     729             : }  // namespace compiler
     730             : }  // namespace internal
     731      178779 : }  // namespace v8

Generated by: LCOV version 1.10