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