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
CollectFunctions(Node * node,Handle<JSFunction> * functions,int functions_size,Handle<SharedFunctionInfo> & shared)24 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 if (m.HasValue() && m.Value()->IsJSFunction()) {
29 functions[0] = Handle<JSFunction>::cast(m.Value());
30 return 1;
31 }
32 if (m.IsPhi()) {
33 int const value_input_count = m.node()->op()->ValueInputCount();
34 if (value_input_count > functions_size) return 0;
35 for (int n = 0; n < value_input_count; ++n) {
36 HeapObjectMatcher m(node->InputAt(n));
37 if (!m.HasValue() || !m.Value()->IsJSFunction()) return 0;
38 functions[n] = Handle<JSFunction>::cast(m.Value());
39 }
40 return value_input_count;
41 }
42 if (m.IsJSCreateClosure()) {
43 CreateClosureParameters const& p = CreateClosureParametersOf(m.op());
44 functions[0] = Handle<JSFunction>::null();
45 shared = p.shared_info();
46 return 1;
47 }
48 return 0;
49 }
50
CanInlineFunction(Handle<SharedFunctionInfo> shared)51 bool CanInlineFunction(Handle<SharedFunctionInfo> shared) {
52 // Built-in functions are handled by the JSBuiltinReducer.
53 if (shared->HasBuiltinFunctionId()) return false;
54
55 // Only choose user code for inlining.
56 if (!shared->IsUserJavaScript()) return false;
57
58 // Quick check on the size of the AST to avoid parsing large candidate.
59 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 if (shared->asm_function()) return false;
65 return true;
66 }
67
68 } // namespace
69
Reduce(Node * node)70 Reduction JSInliningHeuristic::Reduce(Node* node) {
71 if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
72
73 // Check if we already saw that {node} before, and if so, just skip it.
74 if (seen_.find(node->id()) != seen_.end()) return NoChange();
75 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 candidate.node = node;
81 candidate.num_functions = CollectFunctions(
82 callee, candidate.functions, kMaxCallPolymorphism, candidate.shared_info);
83 if (candidate.num_functions == 0) {
84 return NoChange();
85 } else if (candidate.num_functions > 1 && !FLAG_polymorphic_inlining) {
86 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 for (int i = 0; i < candidate.num_functions; ++i) {
96 Handle<SharedFunctionInfo> shared =
97 candidate.functions[i].is_null()
98 ? candidate.shared_info
99 : handle(candidate.functions[i]->shared());
100 if (!shared->force_inline()) {
101 force_inline = false;
102 }
103 if (CanInlineFunction(shared)) {
104 can_inline = true;
105 }
106 }
107 if (force_inline) return InlineCandidate(candidate);
108 if (!can_inline) return NoChange();
109
110 // Stop inlining once the maximum allowed level is reached.
111 int level = 0;
112 for (Node* frame_state = NodeProperties::GetFrameStateInput(node);
113 frame_state->opcode() == IrOpcode::kFrameState;
114 frame_state = NodeProperties::GetFrameStateInput(frame_state)) {
115 FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
116 if (FrameStateFunctionInfo::IsJSFunctionType(frame_info.type())) {
117 if (++level > FLAG_max_inlining_levels) {
118 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 if (node->opcode() == IrOpcode::kJSCall) {
130 CallParameters const p = CallParametersOf(node->op());
131 candidate.frequency = p.frequency();
132 } else {
133 ConstructParameters const p = ConstructParametersOf(node->op());
134 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 switch (mode_) {
141 case kRestrictedInlining:
142 return NoChange();
143 case kStressInlining:
144 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
Finalize()154 void JSInliningHeuristic::Finalize() {
155 if (candidates_.empty()) return; // Nothing to do without candidates.
156 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 while (!candidates_.empty()) {
163 if (cumulative_count_ > FLAG_max_inlined_nodes_cumulative) return;
164 auto i = candidates_.begin();
165 Candidate candidate = *i;
166 candidates_.erase(i);
167 // Make sure we don't try to inline dead candidate nodes.
168 if (!candidate.node->IsDead()) {
169 Reduction const reduction = InlineCandidate(candidate);
170 if (reduction.Changed()) return;
171 }
172 }
173 }
174
InlineCandidate(Candidate const & candidate)175 Reduction JSInliningHeuristic::InlineCandidate(Candidate const& candidate) {
176 int const num_calls = candidate.num_functions;
177 Node* const node = candidate.node;
178 if (num_calls == 1) {
179 Handle<SharedFunctionInfo> shared =
180 candidate.functions[0].is_null()
181 ? candidate.shared_info
182 : handle(candidate.functions[0]->shared());
183 Reduction const reduction = inliner_.ReduceJSCall(node);
184 if (reduction.Changed()) {
185 cumulative_count_ += shared->ast_node_count();
186 }
187 return reduction;
188 }
189
190 // Expand the JSCall/JSConstruct node to a subgraph first if
191 // we have multiple known target functions.
192 DCHECK_LT(1, num_calls);
193 Node* calls[kMaxCallPolymorphism + 1];
194 Node* if_successes[kMaxCallPolymorphism];
195 Node* callee = NodeProperties::GetValueInput(node, 0);
196 Node* fallthrough_control = NodeProperties::GetControlInput(node);
197
198 // Setup the inputs for the cloned call nodes.
199 int const input_count = node->InputCount();
200 Node** inputs = graph()->zone()->NewArray<Node*>(input_count);
201 for (int i = 0; i < input_count; ++i) {
202 inputs[i] = node->InputAt(i);
203 }
204
205 // Create the appropriate control flow to dispatch to the cloned calls.
206 for (int i = 0; i < num_calls; ++i) {
207 // TODO(2206): Make comparison be based on underlying SharedFunctionInfo
208 // instead of the target JSFunction reference directly.
209 Node* target = jsgraph()->HeapConstant(candidate.functions[i]);
210 if (i != (num_calls - 1)) {
211 Node* check =
212 graph()->NewNode(simplified()->ReferenceEqual(), callee, target);
213 Node* branch =
214 graph()->NewNode(common()->Branch(), check, fallthrough_control);
215 fallthrough_control = graph()->NewNode(common()->IfFalse(), branch);
216 if_successes[i] = graph()->NewNode(common()->IfTrue(), branch);
217 } else {
218 if_successes[i] = fallthrough_control;
219 }
220
221 // The first input to the call is the actual target (which we specialize
222 // to the known {target}); the last input is the control dependency.
223 inputs[0] = target;
224 inputs[input_count - 1] = if_successes[i];
225 calls[i] = graph()->NewNode(node->op(), input_count, inputs);
226 if_successes[i] = graph()->NewNode(common()->IfSuccess(), calls[i]);
227 }
228
229 // Check if we have an exception projection for the call {node}.
230 Node* if_exception = nullptr;
231 for (Edge const edge : node->use_edges()) {
232 if (NodeProperties::IsControlEdge(edge) &&
233 edge.from()->opcode() == IrOpcode::kIfException) {
234 if_exception = edge.from();
235 break;
236 }
237 }
238 if (if_exception != nullptr) {
239 // Morph the {if_exception} projection into a join.
240 Node* if_exceptions[kMaxCallPolymorphism + 1];
241 for (int i = 0; i < num_calls; ++i) {
242 if_exceptions[i] =
243 graph()->NewNode(common()->IfException(), calls[i], calls[i]);
244 }
245 Node* exception_control =
246 graph()->NewNode(common()->Merge(num_calls), num_calls, if_exceptions);
247 if_exceptions[num_calls] = exception_control;
248 Node* exception_effect = graph()->NewNode(common()->EffectPhi(num_calls),
249 num_calls + 1, if_exceptions);
250 Node* exception_value = graph()->NewNode(
251 common()->Phi(MachineRepresentation::kTagged, num_calls), num_calls + 1,
252 if_exceptions);
253 ReplaceWithValue(if_exception, exception_value, exception_effect,
254 exception_control);
255 }
256
257 // Morph the call site into the dispatched call sites.
258 Node* control =
259 graph()->NewNode(common()->Merge(num_calls), num_calls, if_successes);
260 calls[num_calls] = control;
261 Node* effect =
262 graph()->NewNode(common()->EffectPhi(num_calls), num_calls + 1, calls);
263 Node* value =
264 graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, num_calls),
265 num_calls + 1, calls);
266 ReplaceWithValue(node, value, effect, control);
267
268 // Inline the individual, cloned call sites.
269 for (int i = 0; i < num_calls; ++i) {
270 Handle<JSFunction> function = candidate.functions[i];
271 Node* node = calls[i];
272 Reduction const reduction = inliner_.ReduceJSCall(node);
273 if (reduction.Changed()) {
274 cumulative_count_ += function->shared()->ast_node_count();
275 }
276 }
277
278 return Replace(value);
279 }
280
operator ()(const Candidate & left,const Candidate & right) const281 bool JSInliningHeuristic::CandidateCompare::operator()(
282 const Candidate& left, const Candidate& right) const {
283 if (left.frequency > right.frequency) {
284 return true;
285 } else if (left.frequency < right.frequency) {
286 return false;
287 } else {
288 return left.node->id() > right.node->id();
289 }
290 }
291
PrintCandidates()292 void JSInliningHeuristic::PrintCandidates() {
293 PrintF("Candidates for inlining (size=%zu):\n", candidates_.size());
294 for (const Candidate& candidate : candidates_) {
295 PrintF(" #%d:%s, frequency:%g\n", candidate.node->id(),
296 candidate.node->op()->mnemonic(), candidate.frequency);
297 for (int i = 0; i < candidate.num_functions; ++i) {
298 Handle<SharedFunctionInfo> shared =
299 candidate.functions[i].is_null()
300 ? candidate.shared_info
301 : handle(candidate.functions[i]->shared());
302 PrintF(" - size:%d, name: %s\n", shared->ast_node_count(),
303 shared->DebugName()->ToCString().get());
304 }
305 }
306 }
307
graph() const308 Graph* JSInliningHeuristic::graph() const { return jsgraph()->graph(); }
309
common() const310 CommonOperatorBuilder* JSInliningHeuristic::common() const {
311 return jsgraph()->common();
312 }
313
simplified() const314 SimplifiedOperatorBuilder* JSInliningHeuristic::simplified() const {
315 return jsgraph()->simplified();
316 }
317
318 } // namespace compiler
319 } // namespace internal
320 } // namespace v8
321