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