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)24 int CollectFunctions(Node* node, Handle<JSFunction>* functions,
25 int functions_size) {
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 return 0;
43 }
44
CanInlineFunction(Handle<JSFunction> function)45 bool CanInlineFunction(Handle<JSFunction> function) {
46 // Built-in functions are handled by the JSBuiltinReducer.
47 if (function->shared()->HasBuiltinFunctionId()) return false;
48
49 // Don't inline builtins.
50 if (function->shared()->IsBuiltin()) return false;
51
52 // Quick check on the size of the AST to avoid parsing large candidate.
53 if (function->shared()->ast_node_count() > FLAG_max_inlined_nodes) {
54 return false;
55 }
56
57 // Avoid inlining across the boundary of asm.js code.
58 if (function->shared()->asm_function()) return false;
59 return true;
60 }
61
62 } // namespace
63
Reduce(Node * node)64 Reduction JSInliningHeuristic::Reduce(Node* node) {
65 if (!IrOpcode::IsInlineeOpcode(node->opcode())) return NoChange();
66
67 // Check if we already saw that {node} before, and if so, just skip it.
68 if (seen_.find(node->id()) != seen_.end()) return NoChange();
69 seen_.insert(node->id());
70
71 // Check if the {node} is an appropriate candidate for inlining.
72 Node* callee = node->InputAt(0);
73 Candidate candidate;
74 candidate.node = node;
75 candidate.num_functions =
76 CollectFunctions(callee, candidate.functions, kMaxCallPolymorphism);
77 if (candidate.num_functions == 0) {
78 return NoChange();
79 } else if (candidate.num_functions > 1 && !FLAG_polymorphic_inlining) {
80 TRACE(
81 "Not considering call site #%d:%s, because polymorphic inlining "
82 "is disabled\n",
83 node->id(), node->op()->mnemonic());
84 return NoChange();
85 }
86
87 // Functions marked with %SetForceInlineFlag are immediately inlined.
88 bool can_inline = false, force_inline = true;
89 for (int i = 0; i < candidate.num_functions; ++i) {
90 Handle<JSFunction> function = candidate.functions[i];
91 if (!function->shared()->force_inline()) {
92 force_inline = false;
93 }
94 if (CanInlineFunction(function)) {
95 can_inline = true;
96 }
97 }
98 if (force_inline) return InlineCandidate(candidate);
99 if (!can_inline) return NoChange();
100
101 // Stop inlining once the maximum allowed level is reached.
102 int level = 0;
103 for (Node* frame_state = NodeProperties::GetFrameStateInput(node);
104 frame_state->opcode() == IrOpcode::kFrameState;
105 frame_state = NodeProperties::GetFrameStateInput(frame_state)) {
106 FrameStateInfo const& frame_info = OpParameter<FrameStateInfo>(frame_state);
107 if (FrameStateFunctionInfo::IsJSFunctionType(frame_info.type())) {
108 if (++level > FLAG_max_inlining_levels) {
109 TRACE(
110 "Not considering call site #%d:%s, because inlining depth "
111 "%d exceeds maximum allowed level %d\n",
112 node->id(), node->op()->mnemonic(), level,
113 FLAG_max_inlining_levels);
114 return NoChange();
115 }
116 }
117 }
118
119 // Gather feedback on how often this call site has been hit before.
120 if (node->opcode() == IrOpcode::kJSCallFunction) {
121 CallFunctionParameters const p = CallFunctionParametersOf(node->op());
122 candidate.frequency = p.frequency();
123 } else {
124 CallConstructParameters const p = CallConstructParametersOf(node->op());
125 candidate.frequency = p.frequency();
126 }
127
128 // Handling of special inlining modes right away:
129 // - For restricted inlining: stop all handling at this point.
130 // - For stressing inlining: immediately handle all functions.
131 switch (mode_) {
132 case kRestrictedInlining:
133 return NoChange();
134 case kStressInlining:
135 return InlineCandidate(candidate);
136 case kGeneralInlining:
137 break;
138 }
139
140 // In the general case we remember the candidate for later.
141 candidates_.insert(candidate);
142 return NoChange();
143 }
144
Finalize()145 void JSInliningHeuristic::Finalize() {
146 if (candidates_.empty()) return; // Nothing to do without candidates.
147 if (FLAG_trace_turbo_inlining) PrintCandidates();
148
149 // We inline at most one candidate in every iteration of the fixpoint.
150 // This is to ensure that we don't consume the full inlining budget
151 // on things that aren't called very often.
152 // TODO(bmeurer): Use std::priority_queue instead of std::set here.
153 while (!candidates_.empty()) {
154 if (cumulative_count_ > FLAG_max_inlined_nodes_cumulative) return;
155 auto i = candidates_.begin();
156 Candidate candidate = *i;
157 candidates_.erase(i);
158 // Make sure we don't try to inline dead candidate nodes.
159 if (!candidate.node->IsDead()) {
160 Reduction const reduction = InlineCandidate(candidate);
161 if (reduction.Changed()) return;
162 }
163 }
164 }
165
InlineCandidate(Candidate const & candidate)166 Reduction JSInliningHeuristic::InlineCandidate(Candidate const& candidate) {
167 int const num_calls = candidate.num_functions;
168 Node* const node = candidate.node;
169 if (num_calls == 1) {
170 Handle<JSFunction> function = candidate.functions[0];
171 Reduction const reduction = inliner_.ReduceJSCall(node, function);
172 if (reduction.Changed()) {
173 cumulative_count_ += function->shared()->ast_node_count();
174 }
175 return reduction;
176 }
177
178 // Expand the JSCallFunction/JSCallConstruct node to a subgraph first if
179 // we have multiple known target functions.
180 DCHECK_LT(1, num_calls);
181 Node* calls[kMaxCallPolymorphism + 1];
182 Node* if_successes[kMaxCallPolymorphism];
183 Node* callee = NodeProperties::GetValueInput(node, 0);
184 Node* fallthrough_control = NodeProperties::GetControlInput(node);
185
186 // Setup the inputs for the cloned call nodes.
187 int const input_count = node->InputCount();
188 Node** inputs = graph()->zone()->NewArray<Node*>(input_count);
189 for (int i = 0; i < input_count; ++i) {
190 inputs[i] = node->InputAt(i);
191 }
192
193 // Create the appropriate control flow to dispatch to the cloned calls.
194 for (int i = 0; i < num_calls; ++i) {
195 Node* target = jsgraph()->HeapConstant(candidate.functions[i]);
196 if (i != (num_calls - 1)) {
197 Node* check =
198 graph()->NewNode(simplified()->ReferenceEqual(), callee, target);
199 Node* branch =
200 graph()->NewNode(common()->Branch(), check, fallthrough_control);
201 fallthrough_control = graph()->NewNode(common()->IfFalse(), branch);
202 if_successes[i] = graph()->NewNode(common()->IfTrue(), branch);
203 } else {
204 if_successes[i] = fallthrough_control;
205 }
206
207 // The first input to the call is the actual target (which we specialize
208 // to the known {target}); the last input is the control dependency.
209 inputs[0] = target;
210 inputs[input_count - 1] = if_successes[i];
211 calls[i] = graph()->NewNode(node->op(), input_count, inputs);
212 if_successes[i] = graph()->NewNode(common()->IfSuccess(), calls[i]);
213 }
214
215 // Check if we have an exception projection for the call {node}.
216 Node* if_exception = nullptr;
217 for (Edge const edge : node->use_edges()) {
218 if (NodeProperties::IsControlEdge(edge) &&
219 edge.from()->opcode() == IrOpcode::kIfException) {
220 if_exception = edge.from();
221 break;
222 }
223 }
224 if (if_exception != nullptr) {
225 // Morph the {if_exception} projection into a join.
226 Node* if_exceptions[kMaxCallPolymorphism + 1];
227 for (int i = 0; i < num_calls; ++i) {
228 if_exceptions[i] =
229 graph()->NewNode(common()->IfException(), calls[i], calls[i]);
230 }
231 Node* exception_control =
232 graph()->NewNode(common()->Merge(num_calls), num_calls, if_exceptions);
233 if_exceptions[num_calls] = exception_control;
234 Node* exception_effect = graph()->NewNode(common()->EffectPhi(num_calls),
235 num_calls + 1, if_exceptions);
236 Node* exception_value = graph()->NewNode(
237 common()->Phi(MachineRepresentation::kTagged, num_calls), num_calls + 1,
238 if_exceptions);
239 ReplaceWithValue(if_exception, exception_value, exception_effect,
240 exception_control);
241 }
242
243 // Morph the call site into the dispatched call sites.
244 Node* control =
245 graph()->NewNode(common()->Merge(num_calls), num_calls, if_successes);
246 calls[num_calls] = control;
247 Node* effect =
248 graph()->NewNode(common()->EffectPhi(num_calls), num_calls + 1, calls);
249 Node* value =
250 graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, num_calls),
251 num_calls + 1, calls);
252 ReplaceWithValue(node, value, effect, control);
253
254 // Inline the individual, cloned call sites.
255 for (int i = 0; i < num_calls; ++i) {
256 Handle<JSFunction> function = candidate.functions[i];
257 Node* node = calls[i];
258 Reduction const reduction = inliner_.ReduceJSCall(node, function);
259 if (reduction.Changed()) {
260 cumulative_count_ += function->shared()->ast_node_count();
261 }
262 }
263
264 return Replace(value);
265 }
266
operator ()(const Candidate & left,const Candidate & right) const267 bool JSInliningHeuristic::CandidateCompare::operator()(
268 const Candidate& left, const Candidate& right) const {
269 if (left.frequency > right.frequency) {
270 return true;
271 } else if (left.frequency < right.frequency) {
272 return false;
273 } else {
274 return left.node->id() > right.node->id();
275 }
276 }
277
PrintCandidates()278 void JSInliningHeuristic::PrintCandidates() {
279 PrintF("Candidates for inlining (size=%zu):\n", candidates_.size());
280 for (const Candidate& candidate : candidates_) {
281 PrintF(" #%d:%s, frequency:%g\n", candidate.node->id(),
282 candidate.node->op()->mnemonic(), candidate.frequency);
283 for (int i = 0; i < candidate.num_functions; ++i) {
284 Handle<JSFunction> function = candidate.functions[i];
285 PrintF(" - size:%d, name: %s\n", function->shared()->ast_node_count(),
286 function->shared()->DebugName()->ToCString().get());
287 }
288 }
289 }
290
graph() const291 Graph* JSInliningHeuristic::graph() const { return jsgraph()->graph(); }
292
common() const293 CommonOperatorBuilder* JSInliningHeuristic::common() const {
294 return jsgraph()->common();
295 }
296
simplified() const297 SimplifiedOperatorBuilder* JSInliningHeuristic::simplified() const {
298 return jsgraph()->simplified();
299 }
300
301 } // namespace compiler
302 } // namespace internal
303 } // namespace v8
304