| OLD | NEW |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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/block_scheduler.h" | 7 #include "vm/block_scheduler.h" |
| 8 #include "vm/compiler.h" | 8 #include "vm/compiler.h" |
| 9 #include "vm/flags.h" | 9 #include "vm/flags.h" |
| 10 #include "vm/flow_graph.h" | 10 #include "vm/flow_graph.h" |
| (...skipping 364 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 375 | 375 |
| 376 GrowableArray<CidTarget> inlined_variants_; | 376 GrowableArray<CidTarget> inlined_variants_; |
| 377 GrowableArray<CidTarget> non_inlined_variants_; | 377 GrowableArray<CidTarget> non_inlined_variants_; |
| 378 GrowableArray<BlockEntryInstr*> inlined_entries_; | 378 GrowableArray<BlockEntryInstr*> inlined_entries_; |
| 379 InlineExitCollector* exit_collector_; | 379 InlineExitCollector* exit_collector_; |
| 380 }; | 380 }; |
| 381 | 381 |
| 382 | 382 |
| 383 class CallSiteInliner : public ValueObject { | 383 class CallSiteInliner : public ValueObject { |
| 384 public: | 384 public: |
| 385 explicit CallSiteInliner(FlowGraph* flow_graph) | 385 CallSiteInliner(FlowGraph* flow_graph, |
| 386 GrowableArray<const Field*>* guarded_fields) |
| 386 : caller_graph_(flow_graph), | 387 : caller_graph_(flow_graph), |
| 387 inlined_(false), | 388 inlined_(false), |
| 388 initial_size_(flow_graph->InstructionCount()), | 389 initial_size_(flow_graph->InstructionCount()), |
| 389 inlined_size_(0), | 390 inlined_size_(0), |
| 390 inlining_depth_(1), | 391 inlining_depth_(1), |
| 391 collected_call_sites_(NULL), | 392 collected_call_sites_(NULL), |
| 392 inlining_call_sites_(NULL), | 393 inlining_call_sites_(NULL), |
| 393 function_cache_() { } | 394 function_cache_(), |
| 395 guarded_fields_(guarded_fields) { } |
| 394 | 396 |
| 395 FlowGraph* caller_graph() const { return caller_graph_; } | 397 FlowGraph* caller_graph() const { return caller_graph_; } |
| 396 | 398 |
| 397 // Inlining heuristics based on Cooper et al. 2008. | 399 // Inlining heuristics based on Cooper et al. 2008. |
| 398 bool ShouldWeInline(const Function& callee, | 400 bool ShouldWeInline(const Function& callee, |
| 399 intptr_t instr_count, | 401 intptr_t instr_count, |
| 400 intptr_t call_site_count, | 402 intptr_t call_site_count, |
| 401 intptr_t const_arg_count) { | 403 intptr_t const_arg_count) { |
| 402 if (inlined_size_ > FLAG_inlining_caller_size_threshold) { | 404 if (inlined_size_ > FLAG_inlining_caller_size_threshold) { |
| 403 // Prevent methods becoming humongous and thus slow to compile. | 405 // Prevent methods becoming humongous and thus slow to compile. |
| (...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 535 Array& ic_data_array = Array::Handle(); | 537 Array& ic_data_array = Array::Handle(); |
| 536 if (function.HasCode()) { | 538 if (function.HasCode()) { |
| 537 const Code& unoptimized_code = | 539 const Code& unoptimized_code = |
| 538 Code::Handle(function.unoptimized_code()); | 540 Code::Handle(function.unoptimized_code()); |
| 539 ic_data_array = unoptimized_code.ExtractTypeFeedbackArray(); | 541 ic_data_array = unoptimized_code.ExtractTypeFeedbackArray(); |
| 540 } | 542 } |
| 541 | 543 |
| 542 // Build the callee graph. | 544 // Build the callee graph. |
| 543 InlineExitCollector* exit_collector = | 545 InlineExitCollector* exit_collector = |
| 544 new InlineExitCollector(caller_graph_, call); | 546 new InlineExitCollector(caller_graph_, call); |
| 545 GrowableArray<const Field*> inlined_guarded_fields; | |
| 546 FlowGraphBuilder builder(parsed_function, | 547 FlowGraphBuilder builder(parsed_function, |
| 547 ic_data_array, | 548 ic_data_array, |
| 548 exit_collector, | 549 exit_collector, |
| 549 &inlined_guarded_fields, | |
| 550 Isolate::kNoDeoptId); | 550 Isolate::kNoDeoptId); |
| 551 builder.SetInitialBlockId(caller_graph_->max_block_id()); | 551 builder.SetInitialBlockId(caller_graph_->max_block_id()); |
| 552 FlowGraph* callee_graph; | 552 FlowGraph* callee_graph; |
| 553 { | 553 { |
| 554 TimerScope timer(FLAG_compiler_stats, | 554 TimerScope timer(FLAG_compiler_stats, |
| 555 &CompilerStats::graphinliner_build_timer, | 555 &CompilerStats::graphinliner_build_timer, |
| 556 isolate); | 556 isolate); |
| 557 callee_graph = builder.BuildGraph(); | 557 callee_graph = builder.BuildGraph(); |
| 558 } | 558 } |
| 559 | 559 |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 600 callee_graph->ComputeSSA(caller_graph_->max_virtual_register_number(), | 600 callee_graph->ComputeSSA(caller_graph_->max_virtual_register_number(), |
| 601 param_stubs); | 601 param_stubs); |
| 602 DEBUG_ASSERT(callee_graph->VerifyUseLists()); | 602 DEBUG_ASSERT(callee_graph->VerifyUseLists()); |
| 603 } | 603 } |
| 604 | 604 |
| 605 { | 605 { |
| 606 TimerScope timer(FLAG_compiler_stats, | 606 TimerScope timer(FLAG_compiler_stats, |
| 607 &CompilerStats::graphinliner_opt_timer, | 607 &CompilerStats::graphinliner_opt_timer, |
| 608 isolate); | 608 isolate); |
| 609 // TODO(zerny): Do more optimization passes on the callee graph. | 609 // TODO(zerny): Do more optimization passes on the callee graph. |
| 610 FlowGraphOptimizer optimizer(callee_graph); | 610 FlowGraphOptimizer optimizer(callee_graph, guarded_fields_); |
| 611 optimizer.ApplyICData(); | 611 optimizer.ApplyICData(); |
| 612 DEBUG_ASSERT(callee_graph->VerifyUseLists()); | 612 DEBUG_ASSERT(callee_graph->VerifyUseLists()); |
| 613 } | 613 } |
| 614 | 614 |
| 615 if (FLAG_trace_inlining && | 615 if (FLAG_trace_inlining && |
| 616 (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { | 616 (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { |
| 617 OS::Print("Callee graph for inlining %s\n", | 617 OS::Print("Callee graph for inlining %s\n", |
| 618 function.ToFullyQualifiedCString()); | 618 function.ToFullyQualifiedCString()); |
| 619 FlowGraphPrinter printer(*callee_graph); | 619 FlowGraphPrinter printer(*callee_graph); |
| 620 printer.PrintBlocks(); | 620 printer.PrintBlocks(); |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 661 | 661 |
| 662 // Build succeeded so we restore the bailout jump. | 662 // Build succeeded so we restore the bailout jump. |
| 663 inlined_ = true; | 663 inlined_ = true; |
| 664 inlined_size_ += size; | 664 inlined_size_ += size; |
| 665 isolate->set_long_jump_base(base); | 665 isolate->set_long_jump_base(base); |
| 666 isolate->set_deopt_id(prev_deopt_id); | 666 isolate->set_deopt_id(prev_deopt_id); |
| 667 | 667 |
| 668 call_data->callee_graph = callee_graph; | 668 call_data->callee_graph = callee_graph; |
| 669 call_data->parameter_stubs = param_stubs; | 669 call_data->parameter_stubs = param_stubs; |
| 670 call_data->exit_collector = exit_collector; | 670 call_data->exit_collector = exit_collector; |
| 671 | |
| 672 // When inlined, we add the guarded fields of the callee to the caller's | |
| 673 // list of guarded fields. | |
| 674 for (intptr_t i = 0; i < inlined_guarded_fields.length(); ++i) { | |
| 675 caller_graph_->builder().AddToGuardedFields(*inlined_guarded_fields[i]); | |
| 676 } | |
| 677 | |
| 678 TRACE_INLINING(OS::Print(" Success\n")); | 671 TRACE_INLINING(OS::Print(" Success\n")); |
| 679 return true; | 672 return true; |
| 680 } else { | 673 } else { |
| 681 Error& error = Error::Handle(); | 674 Error& error = Error::Handle(); |
| 682 error = isolate->object_store()->sticky_error(); | 675 error = isolate->object_store()->sticky_error(); |
| 683 isolate->object_store()->clear_sticky_error(); | 676 isolate->object_store()->clear_sticky_error(); |
| 684 isolate->set_long_jump_base(base); | 677 isolate->set_long_jump_base(base); |
| 685 isolate->set_deopt_id(prev_deopt_id); | 678 isolate->set_deopt_id(prev_deopt_id); |
| 686 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); | 679 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); |
| 687 return false; | 680 return false; |
| (...skipping 310 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 998 | 991 |
| 999 | 992 |
| 1000 FlowGraph* caller_graph_; | 993 FlowGraph* caller_graph_; |
| 1001 bool inlined_; | 994 bool inlined_; |
| 1002 intptr_t initial_size_; | 995 intptr_t initial_size_; |
| 1003 intptr_t inlined_size_; | 996 intptr_t inlined_size_; |
| 1004 intptr_t inlining_depth_; | 997 intptr_t inlining_depth_; |
| 1005 CallSites* collected_call_sites_; | 998 CallSites* collected_call_sites_; |
| 1006 CallSites* inlining_call_sites_; | 999 CallSites* inlining_call_sites_; |
| 1007 GrowableArray<ParsedFunction*> function_cache_; | 1000 GrowableArray<ParsedFunction*> function_cache_; |
| 1001 GrowableArray<const Field*>* guarded_fields_; |
| 1008 | 1002 |
| 1009 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); | 1003 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); |
| 1010 }; | 1004 }; |
| 1011 | 1005 |
| 1012 | 1006 |
| 1013 PolymorphicInliner::PolymorphicInliner(CallSiteInliner* owner, | 1007 PolymorphicInliner::PolymorphicInliner(CallSiteInliner* owner, |
| 1014 PolymorphicInstanceCallInstr* call) | 1008 PolymorphicInstanceCallInstr* call) |
| 1015 : owner_(owner), | 1009 : owner_(owner), |
| 1016 call_(call), | 1010 call_(call), |
| 1017 num_variants_(call->ic_data().NumberOfChecks()), | 1011 num_variants_(call->ic_data().NumberOfChecks()), |
| (...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1152 for (intptr_t i = second->InputCount() - 1; i >= 0; --i) { | 1146 for (intptr_t i = second->InputCount() - 1; i >= 0; --i) { |
| 1153 Value* input = second->InputAt(i); | 1147 Value* input = second->InputAt(i); |
| 1154 input->definition()->AddInputUse(input); | 1148 input->definition()->AddInputUse(input); |
| 1155 } | 1149 } |
| 1156 first->LinkTo(second); | 1150 first->LinkTo(second); |
| 1157 return second; | 1151 return second; |
| 1158 } | 1152 } |
| 1159 | 1153 |
| 1160 | 1154 |
| 1161 bool PolymorphicInliner::TryInlineRecognizedMethod(const Function& target) { | 1155 bool PolymorphicInliner::TryInlineRecognizedMethod(const Function& target) { |
| 1162 FlowGraphOptimizer optimizer(owner_->caller_graph()); | 1156 FlowGraphOptimizer optimizer(owner_->caller_graph(), |
| 1157 NULL); // No guarded fields needed. |
| 1163 TargetEntryInstr* entry; | 1158 TargetEntryInstr* entry; |
| 1164 Definition* last; | 1159 Definition* last; |
| 1165 if (optimizer.TryInlineRecognizedMethod(target, | 1160 if (optimizer.TryInlineRecognizedMethod(target, |
| 1166 call_, | 1161 call_, |
| 1167 call_->ic_data(), | 1162 call_->ic_data(), |
| 1168 &entry, &last)) { | 1163 &entry, &last)) { |
| 1169 // Create a graph fragment. | 1164 // Create a graph fragment. |
| 1170 InlineExitCollector* exit_collector = | 1165 InlineExitCollector* exit_collector = |
| 1171 new InlineExitCollector(owner_->caller_graph(), call_); | 1166 new InlineExitCollector(owner_->caller_graph(), call_); |
| 1172 | 1167 |
| (...skipping 300 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1473 flow_graph_->parsed_function().function().ToCString())); | 1468 flow_graph_->parsed_function().function().ToCString())); |
| 1474 | 1469 |
| 1475 if (FLAG_trace_inlining && | 1470 if (FLAG_trace_inlining && |
| 1476 (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { | 1471 (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { |
| 1477 OS::Print("Before Inlining of %s\n", flow_graph_-> | 1472 OS::Print("Before Inlining of %s\n", flow_graph_-> |
| 1478 parsed_function().function().ToFullyQualifiedCString()); | 1473 parsed_function().function().ToFullyQualifiedCString()); |
| 1479 FlowGraphPrinter printer(*flow_graph_); | 1474 FlowGraphPrinter printer(*flow_graph_); |
| 1480 printer.PrintBlocks(); | 1475 printer.PrintBlocks(); |
| 1481 } | 1476 } |
| 1482 | 1477 |
| 1483 CallSiteInliner inliner(flow_graph_); | 1478 CallSiteInliner inliner(flow_graph_, guarded_fields_); |
| 1484 inliner.InlineCalls(); | 1479 inliner.InlineCalls(); |
| 1485 | 1480 |
| 1486 if (inliner.inlined()) { | 1481 if (inliner.inlined()) { |
| 1487 flow_graph_->DiscoverBlocks(); | 1482 flow_graph_->DiscoverBlocks(); |
| 1488 if (FLAG_trace_inlining) { | 1483 if (FLAG_trace_inlining) { |
| 1489 OS::Print("Inlining growth factor: %f\n", inliner.GrowthFactor()); | 1484 OS::Print("Inlining growth factor: %f\n", inliner.GrowthFactor()); |
| 1490 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) { | 1485 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) { |
| 1491 OS::Print("After Inlining of %s\n", flow_graph_-> | 1486 OS::Print("After Inlining of %s\n", flow_graph_-> |
| 1492 parsed_function().function().ToFullyQualifiedCString()); | 1487 parsed_function().function().ToFullyQualifiedCString()); |
| 1493 FlowGraphPrinter printer(*flow_graph_); | 1488 FlowGraphPrinter printer(*flow_graph_); |
| 1494 printer.PrintBlocks(); | 1489 printer.PrintBlocks(); |
| 1495 } | 1490 } |
| 1496 } | 1491 } |
| 1497 } | 1492 } |
| 1498 } | 1493 } |
| 1499 | 1494 |
| 1500 } // namespace dart | 1495 } // namespace dart |
| OLD | NEW |