1 // Copyright 2014 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/access-builder.h"
6 #include "src/compiler/ast-graph-builder.h"
7 #include "src/compiler/common-operator.h"
8 #include "src/compiler/generic-node-inl.h"
9 #include "src/compiler/graph-inl.h"
10 #include "src/compiler/graph-visualizer.h"
11 #include "src/compiler/js-inlining.h"
12 #include "src/compiler/js-operator.h"
13 #include "src/compiler/node-aux-data-inl.h"
14 #include "src/compiler/node-matchers.h"
15 #include "src/compiler/node-properties-inl.h"
16 #include "src/compiler/simplified-operator.h"
17 #include "src/compiler/typer.h"
18 #include "src/full-codegen.h"
19 #include "src/parser.h"
20 #include "src/rewriter.h"
21 #include "src/scopes.h"
22
23
24 namespace v8 {
25 namespace internal {
26 namespace compiler {
27
28 class InlinerVisitor : public NullNodeVisitor {
29 public:
InlinerVisitor(JSInliner * inliner)30 explicit InlinerVisitor(JSInliner* inliner) : inliner_(inliner) {}
31
Post(Node * node)32 GenericGraphVisit::Control Post(Node* node) {
33 switch (node->opcode()) {
34 case IrOpcode::kJSCallFunction:
35 inliner_->TryInlineCall(node);
36 break;
37 default:
38 break;
39 }
40 return GenericGraphVisit::CONTINUE;
41 }
42
43 private:
44 JSInliner* inliner_;
45 };
46
47
Inline()48 void JSInliner::Inline() {
49 InlinerVisitor visitor(this);
50 jsgraph_->graph()->VisitNodeInputsFromEnd(&visitor);
51 }
52
53
54 // TODO(sigurds) Find a home for this function and reuse it everywhere (esp. in
55 // test cases, where similar code is currently duplicated).
Parse(Handle<JSFunction> function,CompilationInfoWithZone * info)56 static void Parse(Handle<JSFunction> function, CompilationInfoWithZone* info) {
57 CHECK(Parser::Parse(info));
58 CHECK(Rewriter::Rewrite(info));
59 CHECK(Scope::Analyze(info));
60 CHECK(Compiler::EnsureDeoptimizationSupport(info));
61 }
62
63
64 // A facade on a JSFunction's graph to facilitate inlining. It assumes the
65 // that the function graph has only one return statement, and provides
66 // {UnifyReturn} to convert a function graph to that end.
67 class Inlinee {
68 public:
Inlinee(Node * start,Node * end)69 Inlinee(Node* start, Node* end) : start_(start), end_(end) {}
70
71 // Returns the last regular control node, that is
72 // the last control node before the end node.
end_block()73 Node* end_block() { return NodeProperties::GetControlInput(unique_return()); }
74
75 // Return the effect output of the graph,
76 // that is the effect input of the return statement of the inlinee.
effect_output()77 Node* effect_output() {
78 return NodeProperties::GetEffectInput(unique_return());
79 }
80 // Return the value output of the graph,
81 // that is the value input of the return statement of the inlinee.
value_output()82 Node* value_output() {
83 return NodeProperties::GetValueInput(unique_return(), 0);
84 }
85 // Return the unique return statement of the graph.
unique_return()86 Node* unique_return() {
87 Node* unique_return = NodeProperties::GetControlInput(end_);
88 DCHECK_EQ(IrOpcode::kReturn, unique_return->opcode());
89 return unique_return;
90 }
91
92 // Counts JSFunction, Receiver, arguments, context but not effect, control.
total_parameters()93 size_t total_parameters() { return start_->op()->OutputCount(); }
94
95 // Counts only formal parameters.
formal_parameters()96 size_t formal_parameters() {
97 DCHECK_GE(total_parameters(), 3);
98 return total_parameters() - 3;
99 }
100
101 // Inline this graph at {call}, use {jsgraph} and its zone to create
102 // any new nodes.
103 void InlineAtCall(JSGraph* jsgraph, Node* call);
104
105 // Ensure that only a single return reaches the end node.
106 static void UnifyReturn(JSGraph* jsgraph);
107
108 private:
109 Node* start_;
110 Node* end_;
111 };
112
113
UnifyReturn(JSGraph * jsgraph)114 void Inlinee::UnifyReturn(JSGraph* jsgraph) {
115 Graph* graph = jsgraph->graph();
116
117 Node* final_merge = NodeProperties::GetControlInput(graph->end(), 0);
118 if (final_merge->opcode() == IrOpcode::kReturn) {
119 // nothing to do
120 return;
121 }
122 DCHECK_EQ(IrOpcode::kMerge, final_merge->opcode());
123
124 int predecessors =
125 OperatorProperties::GetControlInputCount(final_merge->op());
126
127 const Operator* op_phi = jsgraph->common()->Phi(kMachAnyTagged, predecessors);
128 const Operator* op_ephi = jsgraph->common()->EffectPhi(predecessors);
129
130 NodeVector values(jsgraph->zone());
131 NodeVector effects(jsgraph->zone());
132 // Iterate over all control flow predecessors,
133 // which must be return statements.
134 InputIter iter = final_merge->inputs().begin();
135 while (iter != final_merge->inputs().end()) {
136 Node* input = *iter;
137 switch (input->opcode()) {
138 case IrOpcode::kReturn:
139 values.push_back(NodeProperties::GetValueInput(input, 0));
140 effects.push_back(NodeProperties::GetEffectInput(input));
141 iter.UpdateToAndIncrement(NodeProperties::GetControlInput(input));
142 input->RemoveAllInputs();
143 break;
144 default:
145 UNREACHABLE();
146 ++iter;
147 break;
148 }
149 }
150 values.push_back(final_merge);
151 effects.push_back(final_merge);
152 Node* phi =
153 graph->NewNode(op_phi, static_cast<int>(values.size()), &values.front());
154 Node* ephi = graph->NewNode(op_ephi, static_cast<int>(effects.size()),
155 &effects.front());
156 Node* new_return =
157 graph->NewNode(jsgraph->common()->Return(), phi, ephi, final_merge);
158 graph->end()->ReplaceInput(0, new_return);
159 }
160
161
162 class CopyVisitor : public NullNodeVisitor {
163 public:
CopyVisitor(Graph * source_graph,Graph * target_graph,Zone * temp_zone)164 CopyVisitor(Graph* source_graph, Graph* target_graph, Zone* temp_zone)
165 : copies_(source_graph->NodeCount(), NULL, temp_zone),
166 sentinels_(source_graph->NodeCount(), NULL, temp_zone),
167 source_graph_(source_graph),
168 target_graph_(target_graph),
169 temp_zone_(temp_zone),
170 sentinel_op_(IrOpcode::kDead, Operator::kNoProperties, 0, 0,
171 "sentinel") {}
172
Post(Node * original)173 GenericGraphVisit::Control Post(Node* original) {
174 NodeVector inputs(temp_zone_);
175 for (InputIter it = original->inputs().begin();
176 it != original->inputs().end(); ++it) {
177 inputs.push_back(GetCopy(*it));
178 }
179
180 // Reuse the operator in the copy. This assumes that op lives in a zone
181 // that lives longer than graph()'s zone.
182 Node* copy =
183 target_graph_->NewNode(original->op(), static_cast<int>(inputs.size()),
184 (inputs.empty() ? NULL : &inputs.front()));
185 copies_[original->id()] = copy;
186 return GenericGraphVisit::CONTINUE;
187 }
188
GetCopy(Node * original)189 Node* GetCopy(Node* original) {
190 Node* copy = copies_[original->id()];
191 if (copy == NULL) {
192 copy = GetSentinel(original);
193 }
194 DCHECK_NE(NULL, copy);
195 return copy;
196 }
197
CopyGraph()198 void CopyGraph() {
199 source_graph_->VisitNodeInputsFromEnd(this);
200 ReplaceSentinels();
201 }
202
copies()203 const NodeVector& copies() { return copies_; }
204
205 private:
ReplaceSentinels()206 void ReplaceSentinels() {
207 for (NodeId id = 0; id < source_graph_->NodeCount(); ++id) {
208 Node* sentinel = sentinels_[id];
209 if (sentinel == NULL) continue;
210 Node* copy = copies_[id];
211 DCHECK_NE(NULL, copy);
212 sentinel->ReplaceUses(copy);
213 }
214 }
215
GetSentinel(Node * original)216 Node* GetSentinel(Node* original) {
217 Node* sentinel = sentinels_[original->id()];
218 if (sentinel == NULL) {
219 sentinel = target_graph_->NewNode(&sentinel_op_);
220 }
221 return sentinel;
222 }
223
224 NodeVector copies_;
225 NodeVector sentinels_;
226 Graph* source_graph_;
227 Graph* target_graph_;
228 Zone* temp_zone_;
229 SimpleOperator sentinel_op_;
230 };
231
232
InlineAtCall(JSGraph * jsgraph,Node * call)233 void Inlinee::InlineAtCall(JSGraph* jsgraph, Node* call) {
234 // The scheduler is smart enough to place our code; we just ensure {control}
235 // becomes the control input of the start of the inlinee.
236 Node* control = NodeProperties::GetControlInput(call);
237
238 // The inlinee uses the context from the JSFunction object. This will
239 // also be the effect dependency for the inlinee as it produces an effect.
240 SimplifiedOperatorBuilder simplified(jsgraph->zone());
241 Node* context = jsgraph->graph()->NewNode(
242 simplified.LoadField(AccessBuilder::ForJSFunctionContext()),
243 NodeProperties::GetValueInput(call, 0),
244 NodeProperties::GetEffectInput(call));
245
246 // Context is last argument.
247 int inlinee_context_index = static_cast<int>(total_parameters()) - 1;
248 // {inliner_inputs} counts JSFunction, Receiver, arguments, but not
249 // context, effect, control.
250 int inliner_inputs = OperatorProperties::GetValueInputCount(call->op());
251 // Iterate over all uses of the start node.
252 UseIter iter = start_->uses().begin();
253 while (iter != start_->uses().end()) {
254 Node* use = *iter;
255 switch (use->opcode()) {
256 case IrOpcode::kParameter: {
257 int index = 1 + OpParameter<int>(use->op());
258 if (index < inliner_inputs && index < inlinee_context_index) {
259 // There is an input from the call, and the index is a value
260 // projection but not the context, so rewire the input.
261 NodeProperties::ReplaceWithValue(*iter, call->InputAt(index));
262 } else if (index == inlinee_context_index) {
263 // This is the context projection, rewire it to the context from the
264 // JSFunction object.
265 NodeProperties::ReplaceWithValue(*iter, context);
266 } else if (index < inlinee_context_index) {
267 // Call has fewer arguments than required, fill with undefined.
268 NodeProperties::ReplaceWithValue(*iter, jsgraph->UndefinedConstant());
269 } else {
270 // We got too many arguments, discard for now.
271 // TODO(sigurds): Fix to treat arguments array correctly.
272 }
273 ++iter;
274 break;
275 }
276 default:
277 if (NodeProperties::IsEffectEdge(iter.edge())) {
278 iter.UpdateToAndIncrement(context);
279 } else if (NodeProperties::IsControlEdge(iter.edge())) {
280 iter.UpdateToAndIncrement(control);
281 } else {
282 UNREACHABLE();
283 }
284 break;
285 }
286 }
287
288 // Iterate over all uses of the call node.
289 iter = call->uses().begin();
290 while (iter != call->uses().end()) {
291 if (NodeProperties::IsEffectEdge(iter.edge())) {
292 iter.UpdateToAndIncrement(effect_output());
293 } else if (NodeProperties::IsControlEdge(iter.edge())) {
294 UNREACHABLE();
295 } else {
296 DCHECK(NodeProperties::IsValueEdge(iter.edge()));
297 iter.UpdateToAndIncrement(value_output());
298 }
299 }
300 call->RemoveAllInputs();
301 DCHECK_EQ(0, call->UseCount());
302 // TODO(sigurds) Remove this once we copy.
303 unique_return()->RemoveAllInputs();
304 }
305
306
307 // TODO(turbofan) Provide such accessors for every node, possibly even
308 // generate them.
309 class JSCallFunctionAccessor {
310 public:
JSCallFunctionAccessor(Node * call)311 explicit JSCallFunctionAccessor(Node* call) : call_(call) {
312 DCHECK_EQ(IrOpcode::kJSCallFunction, call->opcode());
313 }
314
jsfunction()315 Node* jsfunction() { return call_->InputAt(0); }
316
receiver()317 Node* receiver() { return call_->InputAt(1); }
318
formal_argument(size_t index)319 Node* formal_argument(size_t index) {
320 DCHECK(index < formal_arguments());
321 return call_->InputAt(static_cast<int>(2 + index));
322 }
323
formal_arguments()324 size_t formal_arguments() {
325 // {value_inputs} includes jsfunction and receiver.
326 size_t value_inputs = OperatorProperties::GetValueInputCount(call_->op());
327 DCHECK_GE(call_->InputCount(), 2);
328 return value_inputs - 2;
329 }
330
frame_state()331 Node* frame_state() { return NodeProperties::GetFrameStateInput(call_); }
332
333 private:
334 Node* call_;
335 };
336
337
AddClosureToFrameState(Node * frame_state,Handle<JSFunction> jsfunction)338 void JSInliner::AddClosureToFrameState(Node* frame_state,
339 Handle<JSFunction> jsfunction) {
340 FrameStateCallInfo call_info = OpParameter<FrameStateCallInfo>(frame_state);
341 const Operator* op = jsgraph_->common()->FrameState(
342 FrameStateType::JS_FRAME, call_info.bailout_id(),
343 call_info.state_combine(), jsfunction);
344 frame_state->set_op(op);
345 }
346
347
CreateArgumentsAdaptorFrameState(JSCallFunctionAccessor * call,Handle<JSFunction> jsfunction,Zone * temp_zone)348 Node* JSInliner::CreateArgumentsAdaptorFrameState(JSCallFunctionAccessor* call,
349 Handle<JSFunction> jsfunction,
350 Zone* temp_zone) {
351 const Operator* op =
352 jsgraph_->common()->FrameState(FrameStateType::ARGUMENTS_ADAPTOR,
353 BailoutId(-1), kIgnoreOutput, jsfunction);
354 const Operator* op0 = jsgraph_->common()->StateValues(0);
355 Node* node0 = jsgraph_->graph()->NewNode(op0);
356 NodeVector params(temp_zone);
357 params.push_back(call->receiver());
358 for (size_t argument = 0; argument != call->formal_arguments(); ++argument) {
359 params.push_back(call->formal_argument(argument));
360 }
361 const Operator* op_param =
362 jsgraph_->common()->StateValues(static_cast<int>(params.size()));
363 Node* params_node = jsgraph_->graph()->NewNode(
364 op_param, static_cast<int>(params.size()), ¶ms.front());
365 return jsgraph_->graph()->NewNode(op, params_node, node0, node0,
366 jsgraph_->UndefinedConstant(),
367 call->frame_state());
368 }
369
370
TryInlineCall(Node * call_node)371 void JSInliner::TryInlineCall(Node* call_node) {
372 JSCallFunctionAccessor call(call_node);
373
374 HeapObjectMatcher<JSFunction> match(call.jsfunction());
375 if (!match.HasValue()) {
376 return;
377 }
378
379 Handle<JSFunction> function = match.Value().handle();
380
381 if (function->shared()->native()) {
382 if (FLAG_trace_turbo_inlining) {
383 SmartArrayPointer<char> name =
384 function->shared()->DebugName()->ToCString();
385 PrintF("Not Inlining %s into %s because inlinee is native\n", name.get(),
386 info_->shared_info()->DebugName()->ToCString().get());
387 }
388 return;
389 }
390
391 CompilationInfoWithZone info(function);
392 Parse(function, &info);
393
394 if (info.scope()->arguments() != NULL) {
395 // For now do not inline functions that use their arguments array.
396 SmartArrayPointer<char> name = function->shared()->DebugName()->ToCString();
397 if (FLAG_trace_turbo_inlining) {
398 PrintF(
399 "Not Inlining %s into %s because inlinee uses arguments "
400 "array\n",
401 name.get(), info_->shared_info()->DebugName()->ToCString().get());
402 }
403 return;
404 }
405
406 if (FLAG_trace_turbo_inlining) {
407 SmartArrayPointer<char> name = function->shared()->DebugName()->ToCString();
408 PrintF("Inlining %s into %s\n", name.get(),
409 info_->shared_info()->DebugName()->ToCString().get());
410 }
411
412 Graph graph(info.zone());
413 Typer typer(info.zone());
414 JSGraph jsgraph(&graph, jsgraph_->common(), jsgraph_->javascript(), &typer,
415 jsgraph_->machine());
416
417 AstGraphBuilder graph_builder(&info, &jsgraph);
418 graph_builder.CreateGraph();
419 Inlinee::UnifyReturn(&jsgraph);
420
421 CopyVisitor visitor(&graph, jsgraph_->graph(), info.zone());
422 visitor.CopyGraph();
423
424 Inlinee inlinee(visitor.GetCopy(graph.start()), visitor.GetCopy(graph.end()));
425
426 Node* outer_frame_state = call.frame_state();
427 // Insert argument adaptor frame if required.
428 if (call.formal_arguments() != inlinee.formal_parameters()) {
429 outer_frame_state =
430 CreateArgumentsAdaptorFrameState(&call, function, info.zone());
431 }
432
433 for (NodeVectorConstIter it = visitor.copies().begin();
434 it != visitor.copies().end(); ++it) {
435 Node* node = *it;
436 if (node != NULL && node->opcode() == IrOpcode::kFrameState) {
437 AddClosureToFrameState(node, function);
438 NodeProperties::ReplaceFrameStateInput(node, outer_frame_state);
439 }
440 }
441
442 inlinee.InlineAtCall(jsgraph_, call_node);
443 }
444 }
445 }
446 } // namespace v8::internal::compiler
447