| 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 345 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 356 public: | 356 public: |
| 357 PolymorphicInliner(CallSiteInliner* owner, | 357 PolymorphicInliner(CallSiteInliner* owner, |
| 358 PolymorphicInstanceCallInstr* call); | 358 PolymorphicInstanceCallInstr* call); |
| 359 | 359 |
| 360 void Inline(); | 360 void Inline(); |
| 361 | 361 |
| 362 private: | 362 private: |
| 363 bool CheckInlinedDuplicate(const Function& target); | 363 bool CheckInlinedDuplicate(const Function& target); |
| 364 bool CheckNonInlinedDuplicate(const Function& target); | 364 bool CheckNonInlinedDuplicate(const Function& target); |
| 365 | 365 |
| 366 bool TryInlining(const Function& target); | 366 bool TryInlining(intptr_t receiver_cid, const Function& target); |
| 367 bool TryInlineRecognizedMethod(const Function& target); | 367 bool TryInlineRecognizedMethod(intptr_t receiver_cid, const Function& target); |
| 368 | 368 |
| 369 TargetEntryInstr* BuildDecisionGraph(); | 369 TargetEntryInstr* BuildDecisionGraph(); |
| 370 | 370 |
| 371 CallSiteInliner* const owner_; | 371 CallSiteInliner* const owner_; |
| 372 PolymorphicInstanceCallInstr* const call_; | 372 PolymorphicInstanceCallInstr* const call_; |
| 373 const intptr_t num_variants_; | 373 const intptr_t num_variants_; |
| 374 GrowableArray<CidTarget> variants_; | 374 GrowableArray<CidTarget> variants_; |
| 375 | 375 |
| 376 GrowableArray<CidTarget> inlined_variants_; | 376 GrowableArray<CidTarget> inlined_variants_; |
| 377 GrowableArray<CidTarget> non_inlined_variants_; | 377 GrowableArray<CidTarget> non_inlined_variants_; |
| (...skipping 648 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1026 // inlined target. This sharing is represented by using three different | 1026 // inlined target. This sharing is represented by using three different |
| 1027 // types of entries in the inlined_entries_ array: | 1027 // types of entries in the inlined_entries_ array: |
| 1028 // | 1028 // |
| 1029 // * GraphEntry: the inlined body is not shared. | 1029 // * GraphEntry: the inlined body is not shared. |
| 1030 // | 1030 // |
| 1031 // * TargetEntry: the inlined body is shared and this is the first variant. | 1031 // * TargetEntry: the inlined body is shared and this is the first variant. |
| 1032 // | 1032 // |
| 1033 // * JoinEntry: the inlined body is shared and this is a subsequent variant. | 1033 // * JoinEntry: the inlined body is shared and this is a subsequent variant. |
| 1034 bool PolymorphicInliner::CheckInlinedDuplicate(const Function& target) { | 1034 bool PolymorphicInliner::CheckInlinedDuplicate(const Function& target) { |
| 1035 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { | 1035 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { |
| 1036 if (target.raw() == inlined_variants_[i].target->raw()) { | 1036 if ((target.raw() == inlined_variants_[i].target->raw()) && |
| 1037 !MethodRecognizer::PolymorphicTarget(target)) { |
| 1037 // The call target is shared with a previous inlined variant. Share | 1038 // The call target is shared with a previous inlined variant. Share |
| 1038 // the graph. This requires a join block at the entry, and edge-split | 1039 // the graph. This requires a join block at the entry, and edge-split |
| 1039 // form requires a target for each branch. | 1040 // form requires a target for each branch. |
| 1040 // | 1041 // |
| 1041 // Represent the sharing by recording a fresh target for the first | 1042 // Represent the sharing by recording a fresh target for the first |
| 1042 // variant and the shared join for all later variants. | 1043 // variant and the shared join for all later variants. |
| 1043 if (inlined_entries_[i]->IsGraphEntry()) { | 1044 if (inlined_entries_[i]->IsGraphEntry()) { |
| 1044 // Convert the old target entry to a new join entry. | 1045 // Convert the old target entry to a new join entry. |
| 1045 TargetEntryInstr* old_target = | 1046 TargetEntryInstr* old_target = |
| 1046 inlined_entries_[i]->AsGraphEntry()->normal_entry(); | 1047 inlined_entries_[i]->AsGraphEntry()->normal_entry(); |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1082 for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) { | 1083 for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) { |
| 1083 if (target.raw() == non_inlined_variants_[i].target->raw()) { | 1084 if (target.raw() == non_inlined_variants_[i].target->raw()) { |
| 1084 return true; | 1085 return true; |
| 1085 } | 1086 } |
| 1086 } | 1087 } |
| 1087 | 1088 |
| 1088 return false; | 1089 return false; |
| 1089 } | 1090 } |
| 1090 | 1091 |
| 1091 | 1092 |
| 1092 bool PolymorphicInliner::TryInlining(const Function& target) { | 1093 bool PolymorphicInliner::TryInlining(intptr_t receiver_cid, |
| 1094 const Function& target) { |
| 1093 if (!target.is_optimizable()) { | 1095 if (!target.is_optimizable()) { |
| 1094 if (TryInlineRecognizedMethod(target)) { | 1096 if (TryInlineRecognizedMethod(receiver_cid, target)) { |
| 1095 owner_->inlined_ = true; | 1097 owner_->inlined_ = true; |
| 1096 return true; | 1098 return true; |
| 1097 } | 1099 } |
| 1098 return false; | 1100 return false; |
| 1099 } | 1101 } |
| 1100 | 1102 |
| 1101 GrowableArray<Value*> arguments(call_->ArgumentCount()); | 1103 GrowableArray<Value*> arguments(call_->ArgumentCount()); |
| 1102 for (int i = 0; i < call_->ArgumentCount(); ++i) { | 1104 for (int i = 0; i < call_->ArgumentCount(); ++i) { |
| 1103 arguments.Add(call_->PushArgumentAt(i)->value()); | 1105 arguments.Add(call_->PushArgumentAt(i)->value()); |
| 1104 } | 1106 } |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1150 Instruction* second) { | 1152 Instruction* second) { |
| 1151 for (intptr_t i = second->InputCount() - 1; i >= 0; --i) { | 1153 for (intptr_t i = second->InputCount() - 1; i >= 0; --i) { |
| 1152 Value* input = second->InputAt(i); | 1154 Value* input = second->InputAt(i); |
| 1153 input->definition()->AddInputUse(input); | 1155 input->definition()->AddInputUse(input); |
| 1154 } | 1156 } |
| 1155 first->LinkTo(second); | 1157 first->LinkTo(second); |
| 1156 return second; | 1158 return second; |
| 1157 } | 1159 } |
| 1158 | 1160 |
| 1159 | 1161 |
| 1160 bool PolymorphicInliner::TryInlineRecognizedMethod(const Function& target) { | 1162 bool PolymorphicInliner::TryInlineRecognizedMethod(intptr_t receiver_cid, |
| 1163 const Function& target) { |
| 1161 FlowGraphOptimizer optimizer(owner_->caller_graph()); | 1164 FlowGraphOptimizer optimizer(owner_->caller_graph()); |
| 1162 TargetEntryInstr* entry; | 1165 TargetEntryInstr* entry; |
| 1163 Definition* last; | 1166 Definition* last; |
| 1164 if (optimizer.TryInlineRecognizedMethod(target, | 1167 if (optimizer.TryInlineRecognizedMethod(receiver_cid, |
| 1168 target, |
| 1165 call_, | 1169 call_, |
| 1166 call_->instance_call()->token_pos(), | 1170 call_->instance_call()->token_pos(), |
| 1167 *call_->instance_call()->ic_data(), | 1171 *call_->instance_call()->ic_data(), |
| 1168 &entry, &last)) { | 1172 &entry, &last)) { |
| 1169 // Create a graph fragment. | 1173 // Create a graph fragment. |
| 1170 InlineExitCollector* exit_collector = | 1174 InlineExitCollector* exit_collector = |
| 1171 new InlineExitCollector(owner_->caller_graph(), call_); | 1175 new InlineExitCollector(owner_->caller_graph(), call_); |
| 1172 | 1176 |
| 1173 ReturnInstr* result = | 1177 ReturnInstr* result = |
| 1174 new ReturnInstr(call_->instance_call()->token_pos(), | 1178 new ReturnInstr(call_->instance_call()->token_pos(), |
| (...skipping 230 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1405 } | 1409 } |
| 1406 return entry; | 1410 return entry; |
| 1407 } | 1411 } |
| 1408 | 1412 |
| 1409 | 1413 |
| 1410 void PolymorphicInliner::Inline() { | 1414 void PolymorphicInliner::Inline() { |
| 1411 // Consider the polymorphic variants in order by frequency. | 1415 // Consider the polymorphic variants in order by frequency. |
| 1412 FlowGraphCompiler::SortICDataByCount(call_->ic_data(), &variants_); | 1416 FlowGraphCompiler::SortICDataByCount(call_->ic_data(), &variants_); |
| 1413 for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) { | 1417 for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) { |
| 1414 const Function& target = *variants_[var_idx].target; | 1418 const Function& target = *variants_[var_idx].target; |
| 1419 const intptr_t receiver_cid = variants_[var_idx].cid; |
| 1415 | 1420 |
| 1416 // First check if this is the same target as an earlier inlined variant. | 1421 // First check if this is the same target as an earlier inlined variant. |
| 1417 if (CheckInlinedDuplicate(target)) { | 1422 if (CheckInlinedDuplicate(target)) { |
| 1418 inlined_variants_.Add(variants_[var_idx]); | 1423 inlined_variants_.Add(variants_[var_idx]); |
| 1419 continue; | 1424 continue; |
| 1420 } | 1425 } |
| 1421 | 1426 |
| 1422 // Also check if this is the same target as an earlier non-inlined | 1427 // Also check if this is the same target as an earlier non-inlined |
| 1423 // variant. If so and since inlining decisions are costly, do not try | 1428 // variant. If so and since inlining decisions are costly, do not try |
| 1424 // to inline this variant. | 1429 // to inline this variant. |
| 1425 if (CheckNonInlinedDuplicate(target)) { | 1430 if (CheckNonInlinedDuplicate(target)) { |
| 1426 non_inlined_variants_.Add(variants_[var_idx]); | 1431 non_inlined_variants_.Add(variants_[var_idx]); |
| 1427 continue; | 1432 continue; |
| 1428 } | 1433 } |
| 1429 | 1434 |
| 1430 // Make an inlining decision. | 1435 // Make an inlining decision. |
| 1431 if (TryInlining(target)) { | 1436 if (TryInlining(receiver_cid, target)) { |
| 1432 inlined_variants_.Add(variants_[var_idx]); | 1437 inlined_variants_.Add(variants_[var_idx]); |
| 1433 } else { | 1438 } else { |
| 1434 non_inlined_variants_.Add(variants_[var_idx]); | 1439 non_inlined_variants_.Add(variants_[var_idx]); |
| 1435 } | 1440 } |
| 1436 } | 1441 } |
| 1437 | 1442 |
| 1438 // If there are no inlined variants, leave the call in place. | 1443 // If there are no inlined variants, leave the call in place. |
| 1439 if (inlined_variants_.is_empty()) return; | 1444 if (inlined_variants_.is_empty()) return; |
| 1440 | 1445 |
| 1441 // Now build a decision tree (a DAG because of shared inline variants) and | 1446 // Now build a decision tree (a DAG because of shared inline variants) and |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1491 OS::Print("After Inlining of %s\n", flow_graph_-> | 1496 OS::Print("After Inlining of %s\n", flow_graph_-> |
| 1492 parsed_function().function().ToFullyQualifiedCString()); | 1497 parsed_function().function().ToFullyQualifiedCString()); |
| 1493 FlowGraphPrinter printer(*flow_graph_); | 1498 FlowGraphPrinter printer(*flow_graph_); |
| 1494 printer.PrintBlocks(); | 1499 printer.PrintBlocks(); |
| 1495 } | 1500 } |
| 1496 } | 1501 } |
| 1497 } | 1502 } |
| 1498 } | 1503 } |
| 1499 | 1504 |
| 1500 } // namespace dart | 1505 } // namespace dart |
| OLD | NEW |