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/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" |
| 11 #include "vm/flow_graph_compiler.h" |
11 #include "vm/flow_graph_optimizer.h" | 12 #include "vm/flow_graph_optimizer.h" |
12 #include "vm/il_printer.h" | 13 #include "vm/il_printer.h" |
13 #include "vm/intrinsifier.h" | 14 #include "vm/intrinsifier.h" |
14 #include "vm/longjump.h" | 15 #include "vm/longjump.h" |
15 #include "vm/object.h" | 16 #include "vm/object.h" |
16 #include "vm/object_store.h" | 17 #include "vm/object_store.h" |
17 #include "vm/timer.h" | 18 #include "vm/timer.h" |
18 | 19 |
19 namespace dart { | 20 namespace dart { |
20 | 21 |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
128 // Helper to get the default value of a formal parameter. | 129 // Helper to get the default value of a formal parameter. |
129 static ConstantInstr* GetDefaultValue(intptr_t i, | 130 static ConstantInstr* GetDefaultValue(intptr_t i, |
130 const ParsedFunction& parsed_function) { | 131 const ParsedFunction& parsed_function) { |
131 return new ConstantInstr(Object::ZoneHandle( | 132 return new ConstantInstr(Object::ZoneHandle( |
132 parsed_function.default_parameter_values().At(i))); | 133 parsed_function.default_parameter_values().At(i))); |
133 } | 134 } |
134 | 135 |
135 | 136 |
136 // Pair of an argument name and its value. | 137 // Pair of an argument name and its value. |
137 struct NamedArgument { | 138 struct NamedArgument { |
138 public: | |
139 String* name; | 139 String* name; |
140 Value* value; | 140 Value* value; |
141 NamedArgument(String* name, Value* value) | 141 NamedArgument(String* name, Value* value) |
142 : name(name), value(value) { } | 142 : name(name), value(value) { } |
143 }; | 143 }; |
144 | 144 |
145 | 145 |
146 // Helper to collect information about a callee graph when considering it for | 146 // Helper to collect information about a callee graph when considering it for |
147 // inlining. | 147 // inlining. |
148 class GraphInfoCollector : public ValueObject { | 148 class GraphInfoCollector : public ValueObject { |
(...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
283 private: | 283 private: |
284 GrowableArray<StaticCallInstr*> static_calls_; | 284 GrowableArray<StaticCallInstr*> static_calls_; |
285 GrowableArray<ClosureCallInstr*> closure_calls_; | 285 GrowableArray<ClosureCallInstr*> closure_calls_; |
286 GrowableArray<InstanceCallInfo> instance_calls_; | 286 GrowableArray<InstanceCallInfo> instance_calls_; |
287 GrowableArray<intptr_t> skip_static_call_deopt_ids_; | 287 GrowableArray<intptr_t> skip_static_call_deopt_ids_; |
288 | 288 |
289 DISALLOW_COPY_AND_ASSIGN(CallSites); | 289 DISALLOW_COPY_AND_ASSIGN(CallSites); |
290 }; | 290 }; |
291 | 291 |
292 | 292 |
| 293 struct InlinedCallData { |
| 294 InlinedCallData(Definition* call, GrowableArray<Value*>* arguments) |
| 295 : call(call), |
| 296 arguments(arguments), |
| 297 callee_graph(NULL), |
| 298 parameter_stubs(NULL), |
| 299 exit_collector(NULL) { } |
| 300 |
| 301 Definition* call; |
| 302 GrowableArray<Value*>* arguments; |
| 303 FlowGraph* callee_graph; |
| 304 ZoneGrowableArray<Definition*>* parameter_stubs; |
| 305 InlineExitCollector* exit_collector; |
| 306 }; |
| 307 |
| 308 |
| 309 class CallSiteInliner; |
| 310 |
| 311 class PolymorphicInliner : public ValueObject { |
| 312 public: |
| 313 PolymorphicInliner(CallSiteInliner* owner, |
| 314 PolymorphicInstanceCallInstr* call); |
| 315 |
| 316 void Inline(); |
| 317 |
| 318 private: |
| 319 bool CheckInlinedDuplicate(const Function& target); |
| 320 bool CheckNonInlinedDuplicate(const Function& target); |
| 321 |
| 322 bool TryInlining(const Function& target); |
| 323 |
| 324 TargetEntryInstr* BuildDecisionGraph(); |
| 325 |
| 326 CallSiteInliner* const owner_; |
| 327 PolymorphicInstanceCallInstr* const call_; |
| 328 const intptr_t num_variants_; |
| 329 GrowableArray<CidTarget> variants_; |
| 330 |
| 331 GrowableArray<CidTarget> inlined_variants_; |
| 332 GrowableArray<CidTarget> non_inlined_variants_; |
| 333 GrowableArray<BlockEntryInstr*> inlined_entries_; |
| 334 InlineExitCollector* exit_collector_; |
| 335 }; |
| 336 |
| 337 |
293 class CallSiteInliner : public ValueObject { | 338 class CallSiteInliner : public ValueObject { |
294 public: | 339 public: |
295 CallSiteInliner(FlowGraph* flow_graph, | 340 CallSiteInliner(FlowGraph* flow_graph, |
296 GrowableArray<const Field*>* guarded_fields) | 341 GrowableArray<const Field*>* guarded_fields) |
297 : caller_graph_(flow_graph), | 342 : caller_graph_(flow_graph), |
298 inlined_(false), | 343 inlined_(false), |
299 initial_size_(flow_graph->InstructionCount()), | 344 initial_size_(flow_graph->InstructionCount()), |
300 inlined_size_(0), | 345 inlined_size_(0), |
301 inlining_depth_(1), | 346 inlining_depth_(1), |
302 collected_call_sites_(NULL), | 347 collected_call_sites_(NULL), |
303 inlining_call_sites_(NULL), | 348 inlining_call_sites_(NULL), |
304 function_cache_(), | 349 function_cache_(), |
305 guarded_fields_(guarded_fields) { } | 350 guarded_fields_(guarded_fields) { } |
306 | 351 |
| 352 FlowGraph* caller_graph() const { return caller_graph_; } |
| 353 |
307 // Inlining heuristics based on Cooper et al. 2008. | 354 // Inlining heuristics based on Cooper et al. 2008. |
308 bool ShouldWeInline(intptr_t instr_count, | 355 bool ShouldWeInline(intptr_t instr_count, |
309 intptr_t call_site_count, | 356 intptr_t call_site_count, |
310 intptr_t const_arg_count) { | 357 intptr_t const_arg_count) { |
311 if (instr_count <= FLAG_inlining_size_threshold) { | 358 if (instr_count <= FLAG_inlining_size_threshold) { |
312 return true; | 359 return true; |
313 } | 360 } |
314 if (call_site_count <= FLAG_inlining_callee_call_sites_threshold) { | 361 if (call_site_count <= FLAG_inlining_callee_call_sites_threshold) { |
315 return true; | 362 return true; |
316 } | 363 } |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
352 inlining_call_sites_ = NULL; | 399 inlining_call_sites_ = NULL; |
353 } | 400 } |
354 | 401 |
355 bool inlined() const { return inlined_; } | 402 bool inlined() const { return inlined_; } |
356 | 403 |
357 double GrowthFactor() const { | 404 double GrowthFactor() const { |
358 return static_cast<double>(inlined_size_) / | 405 return static_cast<double>(inlined_size_) / |
359 static_cast<double>(initial_size_); | 406 static_cast<double>(initial_size_); |
360 } | 407 } |
361 | 408 |
362 private: | |
363 struct InlinedCallData { | |
364 public: | |
365 InlinedCallData(Definition* call, GrowableArray<Value*>* arguments) | |
366 : call(call), | |
367 arguments(arguments), | |
368 callee_graph(NULL), | |
369 parameter_stubs(NULL), | |
370 exit_collector(NULL) { } | |
371 | |
372 Definition* call; | |
373 GrowableArray<Value*>* arguments; | |
374 FlowGraph* callee_graph; | |
375 ZoneGrowableArray<Definition*>* parameter_stubs; | |
376 InlineExitCollector* exit_collector; | |
377 }; | |
378 | |
379 bool TryInlining(const Function& function, | 409 bool TryInlining(const Function& function, |
380 const Array& argument_names, | 410 const Array& argument_names, |
381 InlinedCallData* call_data) { | 411 InlinedCallData* call_data) { |
382 TRACE_INLINING(OS::Print(" => %s (deopt count %d)\n", | 412 TRACE_INLINING(OS::Print(" => %s (deopt count %d)\n", |
383 function.ToCString(), | 413 function.ToCString(), |
384 function.deoptimization_counter())); | 414 function.deoptimization_counter())); |
385 | 415 |
386 // Abort if the inlinable bit on the function is low. | 416 // Abort if the inlinable bit on the function is low. |
387 if (!function.IsInlineable()) { | 417 if (!function.IsInlineable()) { |
388 TRACE_INLINING(OS::Print(" Bailout: not inlinable\n")); | 418 TRACE_INLINING(OS::Print(" Bailout: not inlinable\n")); |
(...skipping 207 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
596 error = isolate->object_store()->sticky_error(); | 626 error = isolate->object_store()->sticky_error(); |
597 isolate->object_store()->clear_sticky_error(); | 627 isolate->object_store()->clear_sticky_error(); |
598 isolate->set_long_jump_base(base); | 628 isolate->set_long_jump_base(base); |
599 isolate->set_deopt_id(prev_deopt_id); | 629 isolate->set_deopt_id(prev_deopt_id); |
600 isolate->set_ic_data_array(prev_ic_data.raw()); | 630 isolate->set_ic_data_array(prev_ic_data.raw()); |
601 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); | 631 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); |
602 return false; | 632 return false; |
603 } | 633 } |
604 } | 634 } |
605 | 635 |
| 636 private: |
606 void InlineCall(InlinedCallData* call_data) { | 637 void InlineCall(InlinedCallData* call_data) { |
607 TimerScope timer(FLAG_compiler_stats, | 638 TimerScope timer(FLAG_compiler_stats, |
608 &CompilerStats::graphinliner_subst_timer, | 639 &CompilerStats::graphinliner_subst_timer, |
609 Isolate::Current()); | 640 Isolate::Current()); |
610 | 641 |
611 // Plug result in the caller graph. | 642 // Plug result in the caller graph. |
612 FlowGraph* callee_graph = call_data->callee_graph; | 643 FlowGraph* callee_graph = call_data->callee_graph; |
613 InlineExitCollector* exit_collector = call_data->exit_collector; | 644 InlineExitCollector* exit_collector = call_data->exit_collector; |
614 exit_collector->PrepareGraphs(callee_graph); | 645 exit_collector->PrepareGraphs(callee_graph); |
615 exit_collector->ReplaceCall(callee_graph->graph_entry()->normal_entry()); | 646 exit_collector->ReplaceCall(callee_graph->graph_entry()->normal_entry()); |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
732 InlineCall(&call_data); | 763 InlineCall(&call_data); |
733 } | 764 } |
734 } | 765 } |
735 } | 766 } |
736 | 767 |
737 void InlineInstanceCalls() { | 768 void InlineInstanceCalls() { |
738 const GrowableArray<CallSites::InstanceCallInfo>& call_info = | 769 const GrowableArray<CallSites::InstanceCallInfo>& call_info = |
739 inlining_call_sites_->instance_calls(); | 770 inlining_call_sites_->instance_calls(); |
740 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", | 771 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", |
741 call_info.length())); | 772 call_info.length())); |
742 for (intptr_t i = 0; i < call_info.length(); ++i) { | 773 for (intptr_t call_idx = 0; call_idx < call_info.length(); ++call_idx) { |
743 PolymorphicInstanceCallInstr* call = call_info[i].call; | 774 PolymorphicInstanceCallInstr* call = call_info[call_idx].call; |
| 775 if (call->with_checks()) { |
| 776 PolymorphicInliner inliner(this, call); |
| 777 inliner.Inline(); |
| 778 continue; |
| 779 } |
| 780 |
744 const ICData& ic_data = call->ic_data(); | 781 const ICData& ic_data = call->ic_data(); |
745 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); | 782 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); |
746 if (call->with_checks()) { | 783 if ((call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) { |
747 TRACE_INLINING(OS::Print( | |
748 " => %s (deopt count %d)\n Bailout: %"Pd" checks\n", | |
749 target.ToCString(), | |
750 target.deoptimization_counter(), | |
751 ic_data.NumberOfChecks())); | |
752 continue; | |
753 } | |
754 if ((call_info[i].ratio * 100) < FLAG_inlining_hotness) { | |
755 TRACE_INLINING(OS::Print( | 784 TRACE_INLINING(OS::Print( |
756 " => %s (deopt count %d)\n Bailout: cold %f\n", | 785 " => %s (deopt count %d)\n Bailout: cold %f\n", |
757 target.ToCString(), | 786 target.ToCString(), |
758 target.deoptimization_counter(), | 787 target.deoptimization_counter(), |
759 call_info[i].ratio)); | 788 call_info[call_idx].ratio)); |
760 continue; | 789 continue; |
761 } | 790 } |
762 GrowableArray<Value*> arguments(call->ArgumentCount()); | 791 GrowableArray<Value*> arguments(call->ArgumentCount()); |
763 for (int arg_i = 0; arg_i < call->ArgumentCount(); ++arg_i) { | 792 for (int arg_i = 0; arg_i < call->ArgumentCount(); ++arg_i) { |
764 arguments.Add(call->PushArgumentAt(arg_i)->value()); | 793 arguments.Add(call->PushArgumentAt(arg_i)->value()); |
765 } | 794 } |
766 InlinedCallData call_data(call, &arguments); | 795 InlinedCallData call_data(call, &arguments); |
767 if (TryInlining(target, | 796 if (TryInlining(target, |
768 call->instance_call()->argument_names(), | 797 call->instance_call()->argument_names(), |
769 &call_data)) { | 798 &call_data)) { |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
869 intptr_t inlining_depth_; | 898 intptr_t inlining_depth_; |
870 CallSites* collected_call_sites_; | 899 CallSites* collected_call_sites_; |
871 CallSites* inlining_call_sites_; | 900 CallSites* inlining_call_sites_; |
872 GrowableArray<ParsedFunction*> function_cache_; | 901 GrowableArray<ParsedFunction*> function_cache_; |
873 GrowableArray<const Field*>* guarded_fields_; | 902 GrowableArray<const Field*>* guarded_fields_; |
874 | 903 |
875 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); | 904 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); |
876 }; | 905 }; |
877 | 906 |
878 | 907 |
| 908 PolymorphicInliner::PolymorphicInliner(CallSiteInliner* owner, |
| 909 PolymorphicInstanceCallInstr* call) |
| 910 : owner_(owner), |
| 911 call_(call), |
| 912 num_variants_(call->ic_data().NumberOfChecks()), |
| 913 variants_(num_variants_), |
| 914 inlined_variants_(num_variants_), |
| 915 non_inlined_variants_(num_variants_), |
| 916 inlined_entries_(num_variants_), |
| 917 exit_collector_(new InlineExitCollector(owner->caller_graph(), call)) { |
| 918 } |
| 919 |
| 920 |
| 921 // Inlined bodies are shared if two different class ids have the same |
| 922 // inlined target. This sharing is represented by using three different |
| 923 // types of entries in the inlined_entries_ array: |
| 924 // |
| 925 // * GraphEntry: the inlined body is not shared. |
| 926 // |
| 927 // * TargetEntry: the inlined body is shared and this is the first variant. |
| 928 // |
| 929 // * JoinEntry: the inlined body is shared and this is a subsequent variant. |
| 930 bool PolymorphicInliner::CheckInlinedDuplicate(const Function& target) { |
| 931 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { |
| 932 if (target.raw() == inlined_variants_[i].target->raw()) { |
| 933 // The call target is shared with a previous inlined variant. Share |
| 934 // the graph. This requires a join block at the entry, and edge-split |
| 935 // form requires a target for each branch. |
| 936 // |
| 937 // Represent the sharing by recording a fresh target for the first |
| 938 // variant and the shared join for all later variants. |
| 939 if (inlined_entries_[i]->IsGraphEntry()) { |
| 940 // Convert the old target entry to a new join entry. |
| 941 TargetEntryInstr* old_target = |
| 942 inlined_entries_[i]->AsGraphEntry()->normal_entry(); |
| 943 JoinEntryInstr* new_join = BranchSimplifier::ToJoinEntry(old_target); |
| 944 old_target->ReplaceAsPredecessorWith(new_join); |
| 945 for (intptr_t j = 0; j < old_target->dominated_blocks().length(); ++j) { |
| 946 BlockEntryInstr* block = old_target->dominated_blocks()[j]; |
| 947 new_join->AddDominatedBlock(block); |
| 948 } |
| 949 // Create a new target with the join as unconditional successor. |
| 950 TargetEntryInstr* new_target = |
| 951 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
| 952 old_target->try_index()); |
| 953 new_target->InheritDeoptTarget(new_join); |
| 954 GotoInstr* new_goto = new GotoInstr(new_join); |
| 955 new_goto->InheritDeoptTarget(new_join); |
| 956 new_target->LinkTo(new_goto); |
| 957 new_target->set_last_instruction(new_goto); |
| 958 new_join->predecessors_.Add(new_target); |
| 959 |
| 960 // Record the new target for the first variant. |
| 961 inlined_entries_[i] = new_target; |
| 962 } |
| 963 ASSERT(inlined_entries_[i]->IsTargetEntry()); |
| 964 // Record the shared join for this variant. |
| 965 BlockEntryInstr* join = |
| 966 inlined_entries_[i]->last_instruction()->SuccessorAt(0); |
| 967 ASSERT(join->IsJoinEntry()); |
| 968 inlined_entries_.Add(join); |
| 969 return true; |
| 970 } |
| 971 } |
| 972 |
| 973 return false; |
| 974 } |
| 975 |
| 976 |
| 977 bool PolymorphicInliner::CheckNonInlinedDuplicate(const Function& target) { |
| 978 for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) { |
| 979 if (target.raw() == non_inlined_variants_[i].target->raw()) { |
| 980 return true; |
| 981 } |
| 982 } |
| 983 |
| 984 return false; |
| 985 } |
| 986 |
| 987 |
| 988 bool PolymorphicInliner::TryInlining(const Function& target) { |
| 989 GrowableArray<Value*> arguments(call_->ArgumentCount()); |
| 990 for (int i = 0; i < call_->ArgumentCount(); ++i) { |
| 991 arguments.Add(call_->PushArgumentAt(i)->value()); |
| 992 } |
| 993 InlinedCallData call_data(call_, &arguments); |
| 994 if (!owner_->TryInlining(target, |
| 995 call_->instance_call()->argument_names(), |
| 996 &call_data)) { |
| 997 return false; |
| 998 } |
| 999 |
| 1000 FlowGraph* callee_graph = call_data.callee_graph; |
| 1001 call_data.exit_collector->PrepareGraphs(callee_graph); |
| 1002 inlined_entries_.Add(callee_graph->graph_entry()); |
| 1003 exit_collector_->Union(call_data.exit_collector); |
| 1004 |
| 1005 // Replace parameter stubs and constants. Replace the receiver argument |
| 1006 // with a redefinition to prevent code from the inlined body from being |
| 1007 // hoisted above the inlined entry. |
| 1008 ASSERT(arguments.length() > 0); |
| 1009 Value* actual = arguments[0]; |
| 1010 RedefinitionInstr* redefinition = new RedefinitionInstr(actual->Copy()); |
| 1011 redefinition->set_ssa_temp_index( |
| 1012 owner_->caller_graph()->alloc_ssa_temp_index()); |
| 1013 redefinition->InsertAfter(callee_graph->graph_entry()->normal_entry()); |
| 1014 Definition* stub = (*call_data.parameter_stubs)[0]; |
| 1015 stub->ReplaceUsesWith(redefinition); |
| 1016 |
| 1017 for (intptr_t i = 1; i < arguments.length(); ++i) { |
| 1018 actual = arguments[i]; |
| 1019 if (actual != NULL) { |
| 1020 stub = (*call_data.parameter_stubs)[i]; |
| 1021 stub->ReplaceUsesWith(actual->definition()); |
| 1022 } |
| 1023 } |
| 1024 GrowableArray<Definition*>* defns = |
| 1025 callee_graph->graph_entry()->initial_definitions(); |
| 1026 for (intptr_t i = 0; i < defns->length(); ++i) { |
| 1027 ConstantInstr* constant = (*defns)[i]->AsConstant(); |
| 1028 if ((constant != NULL) && constant->HasUses()) { |
| 1029 constant->ReplaceUsesWith( |
| 1030 owner_->caller_graph()->AddConstantToInitialDefinitions( |
| 1031 constant->value())); |
| 1032 } |
| 1033 } |
| 1034 return true; |
| 1035 } |
| 1036 |
| 1037 |
| 1038 static Instruction* AppendInstruction(Instruction* first, |
| 1039 Instruction* second) { |
| 1040 for (intptr_t i = second->InputCount() - 1; i >= 0; --i) { |
| 1041 Value* input = second->InputAt(i); |
| 1042 input->definition()->AddInputUse(input); |
| 1043 } |
| 1044 first->LinkTo(second); |
| 1045 return second; |
| 1046 } |
| 1047 |
| 1048 |
| 1049 // Build a DAG to dispatch to the inlined function bodies. Load the class |
| 1050 // id of the receiver and make explicit comparisons for each inlined body, |
| 1051 // in frequency order. If all variants are inlined, the entry to the last |
| 1052 // inlined body is guarded by a CheckClassId instruction which can deopt. |
| 1053 // If not all variants are inlined, we add a PolymorphicInstanceCall |
| 1054 // instruction to handle the non-inlined variants. |
| 1055 TargetEntryInstr* PolymorphicInliner::BuildDecisionGraph() { |
| 1056 // Start with a fresh target entry. |
| 1057 TargetEntryInstr* entry = |
| 1058 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
| 1059 call_->GetBlock()->try_index()); |
| 1060 entry->InheritDeoptTarget(call_); |
| 1061 |
| 1062 // This function uses a cursor (a pointer to the 'current' instruction) to |
| 1063 // build the graph. The next instruction will be inserted after the |
| 1064 // cursor. |
| 1065 TargetEntryInstr* current_block = entry; |
| 1066 Instruction* cursor = entry; |
| 1067 |
| 1068 Definition* receiver = call_->ArgumentAt(0); |
| 1069 // There are at least two variants including non-inlined ones, so we have |
| 1070 // at least one branch on the class id. |
| 1071 LoadClassIdInstr* load_cid = new LoadClassIdInstr(new Value(receiver)); |
| 1072 load_cid->set_ssa_temp_index(owner_->caller_graph()->alloc_ssa_temp_index()); |
| 1073 cursor = AppendInstruction(cursor, load_cid); |
| 1074 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { |
| 1075 // 1. Guard the body with a class id check. |
| 1076 if ((i == (inlined_variants_.length() - 1)) && |
| 1077 non_inlined_variants_.is_empty()) { |
| 1078 // If it is the last variant use a check class or check smi |
| 1079 // instruction which can deoptimize, followed unconditionally by the |
| 1080 // body. |
| 1081 if (inlined_variants_[i].cid == kSmiCid) { |
| 1082 CheckSmiInstr* check_smi = |
| 1083 new CheckSmiInstr(new Value(receiver), call_->deopt_id()); |
| 1084 check_smi->InheritDeoptTarget(call_); |
| 1085 cursor = AppendInstruction(cursor, check_smi); |
| 1086 } else { |
| 1087 const ICData& old_checks = call_->ic_data(); |
| 1088 const ICData& new_checks = ICData::ZoneHandle( |
| 1089 ICData::New(Function::Handle(old_checks.function()), |
| 1090 String::Handle(old_checks.target_name()), |
| 1091 old_checks.deopt_id(), |
| 1092 1)); // Number of args tested. |
| 1093 new_checks.AddReceiverCheck(inlined_variants_[i].cid, |
| 1094 *inlined_variants_[i].target); |
| 1095 CheckClassInstr* check_class = |
| 1096 new CheckClassInstr(new Value(receiver), |
| 1097 call_->deopt_id(), |
| 1098 new_checks); |
| 1099 check_class->InheritDeoptTarget(call_); |
| 1100 cursor = AppendInstruction(cursor, check_class); |
| 1101 } |
| 1102 // The next instruction is the first instruction of the inlined body. |
| 1103 // Handle the two possible cases (unshared and shared subsequent |
| 1104 // predecessors) separately. |
| 1105 BlockEntryInstr* callee_entry = inlined_entries_[i]; |
| 1106 if (callee_entry->IsGraphEntry()) { |
| 1107 // Unshared. Graft the normal entry on after the check class |
| 1108 // instruction. |
| 1109 TargetEntryInstr* target = |
| 1110 callee_entry->AsGraphEntry()->normal_entry(); |
| 1111 cursor->LinkTo(target->next()); |
| 1112 target->ReplaceAsPredecessorWith(current_block); |
| 1113 // All blocks that were dominated by the normal entry are now |
| 1114 // dominated by the current block. |
| 1115 for (intptr_t j = 0; |
| 1116 j < target->dominated_blocks().length(); |
| 1117 ++j) { |
| 1118 BlockEntryInstr* block = target->dominated_blocks()[j]; |
| 1119 current_block->AddDominatedBlock(block); |
| 1120 } |
| 1121 } else if (callee_entry->IsJoinEntry()) { |
| 1122 // Shared inlined body and this is a subsequent entry. We have |
| 1123 // already constructed a join and set its dominator. Add a jump to |
| 1124 // the join. |
| 1125 JoinEntryInstr* join = callee_entry->AsJoinEntry(); |
| 1126 ASSERT(join->dominator() != NULL); |
| 1127 GotoInstr* goto_join = new GotoInstr(join); |
| 1128 goto_join->InheritDeoptTarget(join); |
| 1129 cursor->LinkTo(goto_join); |
| 1130 current_block->set_last_instruction(goto_join); |
| 1131 } else { |
| 1132 // There is no possibility of a TargetEntry (the first entry to a |
| 1133 // shared inlined body) because this is the last inlined entry. |
| 1134 UNREACHABLE(); |
| 1135 } |
| 1136 cursor = NULL; |
| 1137 } else { |
| 1138 // For all variants except the last, use a branch on the loaded class |
| 1139 // id. |
| 1140 const Smi& cid = Smi::ZoneHandle(Smi::New(inlined_variants_[i].cid)); |
| 1141 ConstantInstr* cid_constant = new ConstantInstr(cid); |
| 1142 cid_constant->set_ssa_temp_index( |
| 1143 owner_->caller_graph()->alloc_ssa_temp_index()); |
| 1144 StrictCompareInstr* compare = |
| 1145 new StrictCompareInstr(Token::kEQ_STRICT, |
| 1146 new Value(load_cid), |
| 1147 new Value(cid_constant)); |
| 1148 BranchInstr* branch = new BranchInstr(compare); |
| 1149 branch->InheritDeoptTarget(call_); |
| 1150 AppendInstruction(AppendInstruction(cursor, cid_constant), branch); |
| 1151 current_block->set_last_instruction(branch); |
| 1152 cursor = NULL; |
| 1153 |
| 1154 // 2. Handle a match by linking to the inlined body. There are three |
| 1155 // cases (unshared, shared first predecessor, and shared subsequent |
| 1156 // predecessors). |
| 1157 BlockEntryInstr* callee_entry = inlined_entries_[i]; |
| 1158 TargetEntryInstr* true_target = NULL; |
| 1159 if (callee_entry->IsGraphEntry()) { |
| 1160 // Unshared. |
| 1161 true_target = callee_entry->AsGraphEntry()->normal_entry(); |
| 1162 } else if (callee_entry->IsTargetEntry()) { |
| 1163 // Shared inlined body and this is the first entry. We have already |
| 1164 // constructed a join and this target jumps to it. |
| 1165 true_target = callee_entry->AsTargetEntry(); |
| 1166 BlockEntryInstr* join = |
| 1167 true_target->last_instruction()->SuccessorAt(0); |
| 1168 current_block->AddDominatedBlock(join); |
| 1169 } else { |
| 1170 // Shared inlined body and this is a subsequent entry. We have |
| 1171 // already constructed a join. We need a fresh target that jumps to |
| 1172 // the join. |
| 1173 JoinEntryInstr* join = callee_entry->AsJoinEntry(); |
| 1174 ASSERT(join != NULL); |
| 1175 ASSERT(join->dominator() != NULL); |
| 1176 true_target = |
| 1177 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
| 1178 call_->GetBlock()->try_index()); |
| 1179 true_target->InheritDeoptTarget(join); |
| 1180 GotoInstr* goto_join = new GotoInstr(join); |
| 1181 goto_join->InheritDeoptTarget(join); |
| 1182 true_target->LinkTo(goto_join); |
| 1183 true_target->set_last_instruction(goto_join); |
| 1184 } |
| 1185 *branch->true_successor_address() = true_target; |
| 1186 current_block->AddDominatedBlock(true_target); |
| 1187 |
| 1188 // 3. Prepare to handle a match failure on the next iteration or the |
| 1189 // fall-through code below for non-inlined variants. |
| 1190 TargetEntryInstr* false_target = |
| 1191 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
| 1192 call_->GetBlock()->try_index()); |
| 1193 false_target->InheritDeoptTarget(call_); |
| 1194 *branch->false_successor_address() = false_target; |
| 1195 current_block->AddDominatedBlock(false_target); |
| 1196 cursor = current_block = false_target; |
| 1197 } |
| 1198 } |
| 1199 |
| 1200 // Handle any non-inlined variants. |
| 1201 if (!non_inlined_variants_.is_empty()) { |
| 1202 // Move push arguments of the call. |
| 1203 for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) { |
| 1204 PushArgumentInstr* push = call_->PushArgumentAt(i); |
| 1205 push->ReplaceUsesWith(push->value()->definition()); |
| 1206 push->previous()->LinkTo(push->next()); |
| 1207 cursor->LinkTo(push); |
| 1208 cursor = push; |
| 1209 } |
| 1210 const ICData& old_checks = call_->ic_data(); |
| 1211 const ICData& new_checks = ICData::ZoneHandle( |
| 1212 ICData::New(Function::Handle(old_checks.function()), |
| 1213 String::Handle(old_checks.target_name()), |
| 1214 old_checks.deopt_id(), |
| 1215 1)); // Number of args tested. |
| 1216 for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) { |
| 1217 new_checks.AddReceiverCheck(non_inlined_variants_[i].cid, |
| 1218 *non_inlined_variants_[i].target, |
| 1219 non_inlined_variants_[i].count); |
| 1220 } |
| 1221 PolymorphicInstanceCallInstr* fallback_call = |
| 1222 new PolymorphicInstanceCallInstr(call_->instance_call(), |
| 1223 new_checks, |
| 1224 true); // With checks. |
| 1225 fallback_call->set_ssa_temp_index( |
| 1226 owner_->caller_graph()->alloc_ssa_temp_index()); |
| 1227 fallback_call->InheritDeoptTarget(call_); |
| 1228 ReturnInstr* fallback_return = |
| 1229 new ReturnInstr(call_->instance_call()->token_pos(), |
| 1230 new Value(fallback_call)); |
| 1231 fallback_return->InheritDeoptTargetAfter(call_); |
| 1232 AppendInstruction(AppendInstruction(cursor, fallback_call), |
| 1233 fallback_return); |
| 1234 exit_collector_->AddExit(fallback_return); |
| 1235 cursor = NULL; |
| 1236 } else { |
| 1237 // Remove push arguments of the call. |
| 1238 for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) { |
| 1239 PushArgumentInstr* push = call_->PushArgumentAt(i); |
| 1240 push->ReplaceUsesWith(push->value()->definition()); |
| 1241 push->RemoveFromGraph(); |
| 1242 } |
| 1243 } |
| 1244 return entry; |
| 1245 } |
| 1246 |
| 1247 |
| 1248 void PolymorphicInliner::Inline() { |
| 1249 // Consider the polymorphic variants in order by frequency. |
| 1250 FlowGraphCompiler::SortICDataByCount(call_->ic_data(), &variants_); |
| 1251 for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) { |
| 1252 const Function& target = *variants_[var_idx].target; |
| 1253 |
| 1254 // First check if this is the same target as an earlier inlined variant. |
| 1255 if (CheckInlinedDuplicate(target)) { |
| 1256 inlined_variants_.Add(variants_[var_idx]); |
| 1257 continue; |
| 1258 } |
| 1259 |
| 1260 // Also check if this is the same target as an earlier non-inlined |
| 1261 // variant. If so and since inlining decisions are costly, do not try |
| 1262 // to inline this variant. |
| 1263 if (CheckNonInlinedDuplicate(target)) { |
| 1264 non_inlined_variants_.Add(variants_[var_idx]); |
| 1265 continue; |
| 1266 } |
| 1267 |
| 1268 // Make an inlining decision. |
| 1269 if (TryInlining(target)) { |
| 1270 inlined_variants_.Add(variants_[var_idx]); |
| 1271 } else { |
| 1272 non_inlined_variants_.Add(variants_[var_idx]); |
| 1273 } |
| 1274 } |
| 1275 |
| 1276 // If there are no inlined variants, leave the call in place. |
| 1277 if (inlined_variants_.is_empty()) return; |
| 1278 |
| 1279 // Now build a decision tree (a DAG because of shared inline variants) and |
| 1280 // inline it at the call site. |
| 1281 TargetEntryInstr* entry = BuildDecisionGraph(); |
| 1282 exit_collector_->ReplaceCall(entry); |
| 1283 } |
| 1284 |
| 1285 |
879 void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph) { | 1286 void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph) { |
880 GraphInfoCollector info; | 1287 GraphInfoCollector info; |
881 info.Collect(*flow_graph); | 1288 info.Collect(*flow_graph); |
882 const Function& function = flow_graph->parsed_function().function(); | 1289 const Function& function = flow_graph->parsed_function().function(); |
883 function.set_optimized_instruction_count( | 1290 function.set_optimized_instruction_count( |
884 static_cast<uint16_t>(info.instruction_count())); | 1291 static_cast<uint16_t>(info.instruction_count())); |
885 function.set_optimized_call_site_count( | 1292 function.set_optimized_call_site_count( |
886 static_cast<uint16_t>(info.call_site_count())); | 1293 static_cast<uint16_t>(info.call_site_count())); |
887 } | 1294 } |
888 | 1295 |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
922 OS::Print("After Inlining of %s\n", flow_graph_-> | 1329 OS::Print("After Inlining of %s\n", flow_graph_-> |
923 parsed_function().function().ToFullyQualifiedCString()); | 1330 parsed_function().function().ToFullyQualifiedCString()); |
924 FlowGraphPrinter printer(*flow_graph_); | 1331 FlowGraphPrinter printer(*flow_graph_); |
925 printer.PrintBlocks(); | 1332 printer.PrintBlocks(); |
926 } | 1333 } |
927 } | 1334 } |
928 } | 1335 } |
929 } | 1336 } |
930 | 1337 |
931 } // namespace dart | 1338 } // namespace dart |
OLD | NEW |