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