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