OLD | NEW |
---|---|
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_inliner.h" | 5 #include "vm/flow_graph_inliner.h" |
6 | 6 |
7 #include "vm/compiler.h" | 7 #include "vm/compiler.h" |
8 #include "vm/flags.h" | 8 #include "vm/flags.h" |
9 #include "vm/flow_graph.h" | 9 #include "vm/flow_graph.h" |
10 #include "vm/flow_graph_builder.h" | 10 #include "vm/flow_graph_builder.h" |
(...skipping 28 matching lines...) Expand all Loading... | |
39 // Test if a call is recursive by looking in the deoptimization environment. | 39 // Test if a call is recursive by looking in the deoptimization environment. |
40 static bool IsCallRecursive(const Function& function, Definition* call) { | 40 static bool IsCallRecursive(const Function& function, Definition* call) { |
41 Environment* env = call->env(); | 41 Environment* env = call->env(); |
42 while (env != NULL) { | 42 while (env != NULL) { |
43 if (function.raw() == env->function().raw()) return true; | 43 if (function.raw() == env->function().raw()) return true; |
44 env = env->outer(); | 44 env = env->outer(); |
45 } | 45 } |
46 return false; | 46 return false; |
47 } | 47 } |
48 | 48 |
49 // Cached function structure to reuse parsed ASTs for multiple inlining sites. | |
50 class CachedFunction : public ZoneAllocated { | |
Kevin Millikin (Google)
2012/10/22 10:52:16
This seems unnecessary. Couldn't we just make Par
| |
51 public: | |
52 explicit CachedFunction(const ParsedFunction& parsed_function) | |
53 : function_(Function::ZoneHandle(parsed_function.function().raw())), | |
54 node_sequence_(parsed_function.node_sequence()), | |
55 instantiator_(parsed_function.instantiator()), | |
56 default_parameter_values_(Array::ZoneHandle( | |
57 parsed_function.default_parameter_values().raw())), | |
58 expression_temp_var_(parsed_function.has_expression_temp_var() | |
59 ? parsed_function.expression_temp_var() | |
60 : NULL), | |
61 first_parameter_index_(parsed_function.first_parameter_index()), | |
62 first_stack_local_index_(parsed_function.first_stack_local_index()), | |
63 num_copied_params_(parsed_function.num_copied_params()), | |
64 num_stack_locals_(parsed_function.num_stack_locals()) { } | |
65 | |
66 void ParseFunction(ParsedFunction* parsed_function) { | |
67 ASSERT(parsed_function->function().raw() == function_.raw()); | |
68 parsed_function->SetNodeSequence(node_sequence_); | |
69 parsed_function->set_instantiator(instantiator_); | |
70 parsed_function->set_default_parameter_values(default_parameter_values_); | |
71 if (expression_temp_var_ != NULL) { | |
72 parsed_function->set_expression_temp_var(expression_temp_var_); | |
73 } | |
74 parsed_function->first_parameter_index_ = first_parameter_index_; | |
75 parsed_function->first_stack_local_index_ = first_stack_local_index_; | |
76 parsed_function->num_copied_params_ = num_copied_params_; | |
77 parsed_function->num_stack_locals_ = num_stack_locals_; | |
78 // Reset all source labels to null. | |
79 SourceLabelResetter reset; | |
80 node_sequence_->Visit(&reset); | |
81 } | |
82 | |
83 bool Equals(const Function& function) { | |
84 return function_.raw() == function.raw(); | |
85 } | |
86 | |
87 private: | |
88 // TODO(zerny): Remove the following classes once we have moved the label/join | |
89 // map for control flow out of the AST an into the flow graph builder. | |
90 | |
91 // Default visitor to traverse child nodes. | |
92 class ChildrenVisitor : public AstNodeVisitor { | |
93 public: | |
94 ChildrenVisitor() { } | |
95 #define DEFINE_VISIT(type, name) \ | |
96 virtual void Visit##type(type* node) { node->VisitChildren(this); } | |
97 NODE_LIST(DEFINE_VISIT); | |
98 #undef DEFINE_VISIT | |
99 }; | |
100 | |
101 // Visitor to clear each AST node containing source labels. | |
102 class SourceLabelResetter : public ChildrenVisitor { | |
103 public: | |
104 SourceLabelResetter() { } | |
105 void VisitSequenceNode(SequenceNode* node) { Reset(node, node->label()); } | |
106 void VisitCaseNode(CaseNode* node) { Reset(node, node->label()); } | |
107 void VisitSwitchNode(SwitchNode* node) { Reset(node, node->label()); } | |
108 void VisitWhileNode(WhileNode* node) { Reset(node, node->label()); } | |
109 void VisitDoWhileNode(DoWhileNode* node) { Reset(node, node->label()); } | |
110 void VisitForNode(ForNode* node) { Reset(node, node->label()); } | |
111 void VisitJumpNode(JumpNode* node) { Reset(node, node->label()); } | |
112 void Reset(AstNode* node, SourceLabel* lbl) { | |
113 node->VisitChildren(this); | |
114 if (lbl == NULL) return; | |
115 lbl->join_for_break_ = NULL; | |
116 lbl->join_for_continue_ = NULL; | |
117 } | |
118 }; | |
119 | |
120 const Function& function_; | |
121 SequenceNode* node_sequence_; | |
122 AstNode* instantiator_; | |
123 Array& default_parameter_values_; | |
124 LocalVariable* saved_context_var_; | |
125 LocalVariable* expression_temp_var_; | |
126 int first_parameter_index_; | |
127 int first_stack_local_index_; | |
128 int num_copied_params_; | |
129 int num_stack_locals_; | |
130 | |
131 DISALLOW_COPY_AND_ASSIGN(CachedFunction); | |
132 }; | |
49 | 133 |
50 // A collection of call sites to consider for inlining. | 134 // A collection of call sites to consider for inlining. |
51 class CallSites : public FlowGraphVisitor { | 135 class CallSites : public FlowGraphVisitor { |
52 public: | 136 public: |
53 explicit CallSites(FlowGraph* flow_graph) | 137 explicit CallSites(FlowGraph* flow_graph) |
54 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order. | 138 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order. |
55 static_calls_(), | 139 static_calls_(), |
56 closure_calls_(), | 140 closure_calls_(), |
57 instance_calls_() { } | 141 instance_calls_() { } |
58 | 142 |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
116 class CallSiteInliner : public ValueObject { | 200 class CallSiteInliner : public ValueObject { |
117 public: | 201 public: |
118 explicit CallSiteInliner(FlowGraph* flow_graph) | 202 explicit CallSiteInliner(FlowGraph* flow_graph) |
119 : caller_graph_(flow_graph), | 203 : caller_graph_(flow_graph), |
120 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), | 204 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), |
121 inlined_(false), | 205 inlined_(false), |
122 initial_size_(flow_graph->InstructionCount()), | 206 initial_size_(flow_graph->InstructionCount()), |
123 inlined_size_(0), | 207 inlined_size_(0), |
124 inlining_depth_(1), | 208 inlining_depth_(1), |
125 collected_call_sites_(NULL), | 209 collected_call_sites_(NULL), |
126 inlining_call_sites_(NULL) { } | 210 inlining_call_sites_(NULL), |
211 function_cache() { } | |
127 | 212 |
128 void InlineCalls() { | 213 void InlineCalls() { |
129 // If inlining depth is less then one abort. | 214 // If inlining depth is less then one abort. |
130 if (FLAG_inlining_depth_threshold < 1) return; | 215 if (FLAG_inlining_depth_threshold < 1) return; |
131 // Create two call site collections to swap between. | 216 // Create two call site collections to swap between. |
132 CallSites sites1(caller_graph_); | 217 CallSites sites1(caller_graph_); |
133 CallSites sites2(caller_graph_); | 218 CallSites sites2(caller_graph_); |
134 CallSites* call_sites_temp = NULL; | 219 CallSites* call_sites_temp = NULL; |
135 collected_call_sites_ = &sites1; | 220 collected_call_sites_ = &sites1; |
136 inlining_call_sites_ = &sites2; | 221 inlining_call_sites_ = &sites2; |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
213 // Save and clear deopt id. | 298 // Save and clear deopt id. |
214 const intptr_t prev_deopt_id = isolate->deopt_id(); | 299 const intptr_t prev_deopt_id = isolate->deopt_id(); |
215 isolate->set_deopt_id(0); | 300 isolate->set_deopt_id(0); |
216 // Install bailout jump. | 301 // Install bailout jump. |
217 LongJump* base = isolate->long_jump_base(); | 302 LongJump* base = isolate->long_jump_base(); |
218 LongJump jump; | 303 LongJump jump; |
219 isolate->set_long_jump_base(&jump); | 304 isolate->set_long_jump_base(&jump); |
220 if (setjmp(*jump.Set()) == 0) { | 305 if (setjmp(*jump.Set()) == 0) { |
221 // Parse the callee function. | 306 // Parse the callee function. |
222 ParsedFunction parsed_function(function); | 307 ParsedFunction parsed_function(function); |
223 Parser::ParseFunction(&parsed_function); | 308 bool in_cache = ParseFunction(&parsed_function); |
224 parsed_function.AllocateVariables(); | |
225 | 309 |
226 // Load IC data for the callee. | 310 // Load IC data for the callee. |
227 if (function.HasCode()) { | 311 if (function.HasCode()) { |
228 const Code& unoptimized_code = | 312 const Code& unoptimized_code = |
229 Code::Handle(function.unoptimized_code()); | 313 Code::Handle(function.unoptimized_code()); |
230 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); | 314 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); |
231 } | 315 } |
232 | 316 |
233 // Build the callee graph. | 317 // Build the callee graph. |
234 FlowGraphBuilder builder(parsed_function); | 318 FlowGraphBuilder builder(parsed_function); |
(...skipping 15 matching lines...) Expand all Loading... | |
250 callee_graph->ComputeSSA(next_ssa_temp_index_); | 334 callee_graph->ComputeSSA(next_ssa_temp_index_); |
251 callee_graph->ComputeUseLists(); | 335 callee_graph->ComputeUseLists(); |
252 | 336 |
253 // TODO(zerny): Do more optimization passes on the callee graph. | 337 // TODO(zerny): Do more optimization passes on the callee graph. |
254 FlowGraphOptimizer optimizer(callee_graph); | 338 FlowGraphOptimizer optimizer(callee_graph); |
255 optimizer.ApplyICData(); | 339 optimizer.ApplyICData(); |
256 callee_graph->ComputeUseLists(); | 340 callee_graph->ComputeUseLists(); |
257 | 341 |
258 if (FLAG_trace_inlining && FLAG_print_flow_graph) { | 342 if (FLAG_trace_inlining && FLAG_print_flow_graph) { |
259 OS::Print("Callee graph for inlining %s\n", | 343 OS::Print("Callee graph for inlining %s\n", |
260 parsed_function.function().ToFullyQualifiedCString()); | 344 function.ToFullyQualifiedCString()); |
261 FlowGraphPrinter printer(*callee_graph); | 345 FlowGraphPrinter printer(*callee_graph); |
262 printer.PrintBlocks(); | 346 printer.PrintBlocks(); |
263 } | 347 } |
264 | 348 |
265 // If result is more than size threshold then abort. | 349 // If result is more than size threshold then abort. |
266 // TODO(zerny): Do this after CP and dead code elimination. | 350 // TODO(zerny): Do this after CP and dead code elimination. |
267 intptr_t size = callee_graph->InstructionCount(); | 351 intptr_t size = callee_graph->InstructionCount(); |
268 if (size > FLAG_inlining_size_threshold) { | 352 if (size > FLAG_inlining_size_threshold) { |
269 function.set_is_inlinable(false); | 353 function.set_is_inlinable(false); |
270 isolate->set_long_jump_base(base); | 354 isolate->set_long_jump_base(base); |
(...skipping 30 matching lines...) Expand all Loading... | |
301 } | 385 } |
302 } | 386 } |
303 ASSERT(arg_index == arguments->length()); | 387 ASSERT(arg_index == arguments->length()); |
304 | 388 |
305 // Replace callee's null constant with caller's null constant. | 389 // Replace callee's null constant with caller's null constant. |
306 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( | 390 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( |
307 caller_graph_->graph_entry()->constant_null()); | 391 caller_graph_->graph_entry()->constant_null()); |
308 | 392 |
309 TRACE_INLINING(OS::Print(" Success\n")); | 393 TRACE_INLINING(OS::Print(" Success\n")); |
310 | 394 |
395 // Add the function to the cache. | |
396 if (!in_cache) function_cache.Add(new CachedFunction(parsed_function)); | |
397 | |
311 // Check that inlining maintains use lists. | 398 // Check that inlining maintains use lists. |
312 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists()); | 399 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists()); |
313 | 400 |
314 // Build succeeded so we restore the bailout jump. | 401 // Build succeeded so we restore the bailout jump. |
315 inlined_ = true; | 402 inlined_ = true; |
316 inlined_size_ += size; | 403 inlined_size_ += size; |
317 isolate->set_long_jump_base(base); | 404 isolate->set_long_jump_base(base); |
318 isolate->set_deopt_id(prev_deopt_id); | 405 isolate->set_deopt_id(prev_deopt_id); |
319 isolate->set_ic_data_array(prev_ic_data.raw()); | 406 isolate->set_ic_data_array(prev_ic_data.raw()); |
320 return true; | 407 return true; |
321 } else { | 408 } else { |
322 Error& error = Error::Handle(); | 409 Error& error = Error::Handle(); |
323 error = isolate->object_store()->sticky_error(); | 410 error = isolate->object_store()->sticky_error(); |
324 isolate->object_store()->clear_sticky_error(); | 411 isolate->object_store()->clear_sticky_error(); |
325 isolate->set_long_jump_base(base); | 412 isolate->set_long_jump_base(base); |
326 isolate->set_deopt_id(prev_deopt_id); | 413 isolate->set_deopt_id(prev_deopt_id); |
327 isolate->set_ic_data_array(prev_ic_data.raw()); | 414 isolate->set_ic_data_array(prev_ic_data.raw()); |
328 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); | 415 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); |
329 return false; | 416 return false; |
330 } | 417 } |
331 } | 418 } |
332 | 419 |
420 // Parse a function reusing the cache if possible. Returns true if the | |
421 // function was in the cache. | |
422 bool ParseFunction(ParsedFunction* parsed_function) { | |
423 // TODO(zerny): Use a hash map for the cache. | |
424 for (intptr_t i = 0; i < function_cache.length(); ++i) { | |
425 if (function_cache[i]->Equals(parsed_function->function())) { | |
426 function_cache[i]->ParseFunction(parsed_function); | |
427 return true; | |
428 } | |
429 } | |
430 Parser::ParseFunction(parsed_function); | |
431 parsed_function->AllocateVariables(); | |
432 return false; | |
433 } | |
434 | |
333 void InlineStaticCalls() { | 435 void InlineStaticCalls() { |
334 const GrowableArray<StaticCallInstr*>& calls = | 436 const GrowableArray<StaticCallInstr*>& calls = |
335 *inlining_call_sites_->static_calls(); | 437 *inlining_call_sites_->static_calls(); |
336 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length())); | 438 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length())); |
337 for (intptr_t i = 0; i < calls.length(); ++i) { | 439 for (intptr_t i = 0; i < calls.length(); ++i) { |
338 StaticCallInstr* call = calls[i]; | 440 StaticCallInstr* call = calls[i]; |
339 GrowableArray<Value*> arguments(call->ArgumentCount()); | 441 GrowableArray<Value*> arguments(call->ArgumentCount()); |
340 for (int i = 0; i < call->ArgumentCount(); ++i) { | 442 for (int i = 0; i < call->ArgumentCount(); ++i) { |
341 arguments.Add(call->ArgumentAt(i)->value()); | 443 arguments.Add(call->ArgumentAt(i)->value()); |
342 } | 444 } |
(...skipping 26 matching lines...) Expand all Loading... | |
369 void InlineInstanceCalls() { | 471 void InlineInstanceCalls() { |
370 const GrowableArray<PolymorphicInstanceCallInstr*>& calls = | 472 const GrowableArray<PolymorphicInstanceCallInstr*>& calls = |
371 *inlining_call_sites_->instance_calls(); | 473 *inlining_call_sites_->instance_calls(); |
372 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", | 474 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", |
373 calls.length())); | 475 calls.length())); |
374 for (intptr_t i = 0; i < calls.length(); ++i) { | 476 for (intptr_t i = 0; i < calls.length(); ++i) { |
375 PolymorphicInstanceCallInstr* instr = calls[i]; | 477 PolymorphicInstanceCallInstr* instr = calls[i]; |
376 const ICData& ic_data = instr->ic_data(); | 478 const ICData& ic_data = instr->ic_data(); |
377 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); | 479 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); |
378 if (instr->with_checks()) { | 480 if (instr->with_checks()) { |
379 TRACE_INLINING(OS::Print(" Bailout: %"Pd" checks target '%s'\n", | 481 TRACE_INLINING(OS::Print( |
380 ic_data.NumberOfChecks(), | 482 " => %s (deopt count %d)\n Bailout: %"Pd" checks\n", |
381 target.ToCString())); | 483 target.ToCString(), |
484 target.deoptimization_counter(), | |
485 ic_data.NumberOfChecks())); | |
382 continue; | 486 continue; |
383 } | 487 } |
384 GrowableArray<Value*> arguments(instr->ArgumentCount()); | 488 GrowableArray<Value*> arguments(instr->ArgumentCount()); |
385 for (int i = 0; i < instr->ArgumentCount(); ++i) { | 489 for (int i = 0; i < instr->ArgumentCount(); ++i) { |
386 arguments.Add(instr->ArgumentAt(i)->value()); | 490 arguments.Add(instr->ArgumentAt(i)->value()); |
387 } | 491 } |
388 TryInlining(target, &arguments, instr); | 492 TryInlining(target, &arguments, instr); |
389 } | 493 } |
390 } | 494 } |
391 | 495 |
392 FlowGraph* caller_graph_; | 496 FlowGraph* caller_graph_; |
393 intptr_t next_ssa_temp_index_; | 497 intptr_t next_ssa_temp_index_; |
394 bool inlined_; | 498 bool inlined_; |
395 intptr_t initial_size_; | 499 intptr_t initial_size_; |
396 intptr_t inlined_size_; | 500 intptr_t inlined_size_; |
397 intptr_t inlining_depth_; | 501 intptr_t inlining_depth_; |
398 CallSites* collected_call_sites_; | 502 CallSites* collected_call_sites_; |
399 CallSites* inlining_call_sites_; | 503 CallSites* inlining_call_sites_; |
504 GrowableArray<CachedFunction*> function_cache; | |
400 | 505 |
401 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); | 506 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); |
402 }; | 507 }; |
403 | 508 |
404 | 509 |
405 void FlowGraphInliner::Inline() { | 510 void FlowGraphInliner::Inline() { |
406 if ((FLAG_inlining_filter != NULL) && | 511 if ((FLAG_inlining_filter != NULL) && |
407 (strstr(flow_graph_-> | 512 (strstr(flow_graph_-> |
408 parsed_function().function().ToFullyQualifiedCString(), | 513 parsed_function().function().ToFullyQualifiedCString(), |
409 FLAG_inlining_filter) == NULL)) { | 514 FLAG_inlining_filter) == NULL)) { |
(...skipping 21 matching lines...) Expand all Loading... | |
431 OS::Print("After Inlining of %s\n", flow_graph_-> | 536 OS::Print("After Inlining of %s\n", flow_graph_-> |
432 parsed_function().function().ToFullyQualifiedCString()); | 537 parsed_function().function().ToFullyQualifiedCString()); |
433 FlowGraphPrinter printer(*flow_graph_); | 538 FlowGraphPrinter printer(*flow_graph_); |
434 printer.PrintBlocks(); | 539 printer.PrintBlocks(); |
435 } | 540 } |
436 } | 541 } |
437 } | 542 } |
438 } | 543 } |
439 | 544 |
440 } // namespace dart | 545 } // namespace dart |
OLD | NEW |