| 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_optimizer.h" | 5 #include "vm/flow_graph_optimizer.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/cha.h" | 8 #include "vm/cha.h" |
| 9 #include "vm/flow_graph_builder.h" | 9 #include "vm/flow_graph_builder.h" |
| 10 #include "vm/hash_map.h" | 10 #include "vm/hash_map.h" |
| (...skipping 284 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 295 static void RemovePushArguments(StaticCallInstr* call) { | 295 static void RemovePushArguments(StaticCallInstr* call) { |
| 296 // Remove original push arguments. | 296 // Remove original push arguments. |
| 297 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { | 297 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| 298 PushArgumentInstr* push = call->ArgumentAt(i); | 298 PushArgumentInstr* push = call->ArgumentAt(i); |
| 299 push->ReplaceUsesWith(push->value()->definition()); | 299 push->ReplaceUsesWith(push->value()->definition()); |
| 300 push->RemoveFromGraph(); | 300 push->RemoveFromGraph(); |
| 301 } | 301 } |
| 302 } | 302 } |
| 303 | 303 |
| 304 | 304 |
| 305 // Returns true if all targets are the same. | |
| 306 // TODO(srdjan): if targets are native use their C_function to compare. | |
| 307 static bool HasOneTarget(const ICData& ic_data) { | |
| 308 ASSERT(ic_data.NumberOfChecks() > 0); | |
| 309 const Function& first_target = Function::Handle(ic_data.GetTargetAt(0)); | |
| 310 Function& test_target = Function::Handle(); | |
| 311 for (intptr_t i = 1; i < ic_data.NumberOfChecks(); i++) { | |
| 312 test_target = ic_data.GetTargetAt(i); | |
| 313 if (first_target.raw() != test_target.raw()) { | |
| 314 return false; | |
| 315 } | |
| 316 } | |
| 317 return true; | |
| 318 } | |
| 319 | |
| 320 | |
| 321 static intptr_t ReceiverClassId(InstanceCallInstr* call) { | 305 static intptr_t ReceiverClassId(InstanceCallInstr* call) { |
| 322 if (!call->HasICData()) return kIllegalCid; | 306 if (!call->HasICData()) return kIllegalCid; |
| 323 | 307 |
| 324 const ICData& ic_data = ICData::Handle(call->ic_data()->AsUnaryClassChecks()); | 308 const ICData& ic_data = ICData::Handle(call->ic_data()->AsUnaryClassChecks()); |
| 325 | 309 |
| 326 if (ic_data.NumberOfChecks() == 0) return kIllegalCid; | 310 if (ic_data.NumberOfChecks() == 0) return kIllegalCid; |
| 327 // TODO(vegorov): Add multiple receiver type support. | 311 // TODO(vegorov): Add multiple receiver type support. |
| 328 if (ic_data.NumberOfChecks() != 1) return kIllegalCid; | 312 if (ic_data.NumberOfChecks() != 1) return kIllegalCid; |
| 329 ASSERT(HasOneTarget(ic_data)); | 313 ASSERT(ic_data.HasOneTarget()); |
| 330 | 314 |
| 331 Function& target = Function::Handle(); | 315 Function& target = Function::Handle(); |
| 332 intptr_t class_id; | 316 intptr_t class_id; |
| 333 ic_data.GetOneClassCheckAt(0, &class_id, &target); | 317 ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| 334 return class_id; | 318 return class_id; |
| 335 } | 319 } |
| 336 | 320 |
| 337 | 321 |
| 338 void FlowGraphOptimizer::AddCheckClass(InstanceCallInstr* call, | 322 void FlowGraphOptimizer::AddCheckClass(InstanceCallInstr* call, |
| 339 Value* value) { | 323 Value* value) { |
| (...skipping 309 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 649 if (ic_data.NumberOfChecks() == 0) { | 633 if (ic_data.NumberOfChecks() == 0) { |
| 650 // No type feedback collected. | 634 // No type feedback collected. |
| 651 return false; | 635 return false; |
| 652 } | 636 } |
| 653 Function& target = Function::Handle(); | 637 Function& target = Function::Handle(); |
| 654 GrowableArray<intptr_t> class_ids; | 638 GrowableArray<intptr_t> class_ids; |
| 655 ic_data.GetCheckAt(0, &class_ids, &target); | 639 ic_data.GetCheckAt(0, &class_ids, &target); |
| 656 ASSERT(class_ids.length() == 1); | 640 ASSERT(class_ids.length() == 1); |
| 657 | 641 |
| 658 if (target.kind() == RawFunction::kImplicitGetter) { | 642 if (target.kind() == RawFunction::kImplicitGetter) { |
| 659 if (!HasOneTarget(ic_data)) { | 643 if (!ic_data.HasOneTarget()) { |
| 660 // TODO(srdjan): Implement for mutiple targets. | 644 // TODO(srdjan): Implement for mutiple targets. |
| 661 return false; | 645 return false; |
| 662 } | 646 } |
| 663 // Inline implicit instance getter. | 647 // Inline implicit instance getter. |
| 664 const String& field_name = | 648 const String& field_name = |
| 665 String::Handle(Field::NameFromGetter(call->function_name())); | 649 String::Handle(Field::NameFromGetter(call->function_name())); |
| 666 const Field& field = Field::Handle(GetField(class_ids[0], field_name)); | 650 const Field& field = Field::Handle(GetField(class_ids[0], field_name)); |
| 667 ASSERT(!field.IsNull()); | 651 ASSERT(!field.IsNull()); |
| 668 | 652 |
| 669 if (InstanceCallNeedsClassCheck(call)) { | 653 if (InstanceCallNeedsClassCheck(call)) { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 682 } | 666 } |
| 683 | 667 |
| 684 // Not an implicit getter. | 668 // Not an implicit getter. |
| 685 MethodRecognizer::Kind recognized_kind = | 669 MethodRecognizer::Kind recognized_kind = |
| 686 MethodRecognizer::RecognizeKind(target); | 670 MethodRecognizer::RecognizeKind(target); |
| 687 | 671 |
| 688 // VM objects length getter. | 672 // VM objects length getter. |
| 689 if ((recognized_kind == MethodRecognizer::kObjectArrayLength) || | 673 if ((recognized_kind == MethodRecognizer::kObjectArrayLength) || |
| 690 (recognized_kind == MethodRecognizer::kImmutableArrayLength) || | 674 (recognized_kind == MethodRecognizer::kImmutableArrayLength) || |
| 691 (recognized_kind == MethodRecognizer::kGrowableArrayLength)) { | 675 (recognized_kind == MethodRecognizer::kGrowableArrayLength)) { |
| 692 if (!HasOneTarget(ic_data)) { | 676 if (!ic_data.HasOneTarget()) { |
| 693 // TODO(srdjan): Implement for mutiple targets. | 677 // TODO(srdjan): Implement for mutiple targets. |
| 694 return false; | 678 return false; |
| 695 } | 679 } |
| 696 intptr_t length_offset = -1; | 680 intptr_t length_offset = -1; |
| 697 bool is_immutable = false; | 681 bool is_immutable = false; |
| 698 switch (recognized_kind) { | 682 switch (recognized_kind) { |
| 699 case MethodRecognizer::kObjectArrayLength: | 683 case MethodRecognizer::kObjectArrayLength: |
| 700 case MethodRecognizer::kImmutableArrayLength: | 684 case MethodRecognizer::kImmutableArrayLength: |
| 701 length_offset = Array::length_offset(); | 685 length_offset = Array::length_offset(); |
| 702 is_immutable = true; | 686 is_immutable = true; |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 738 Array::length_offset(), | 722 Array::length_offset(), |
| 739 Type::ZoneHandle(Type::SmiType())); | 723 Type::ZoneHandle(Type::SmiType())); |
| 740 length_load->set_result_cid(kSmiCid); | 724 length_load->set_result_cid(kSmiCid); |
| 741 | 725 |
| 742 call->ReplaceWith(length_load, current_iterator()); | 726 call->ReplaceWith(length_load, current_iterator()); |
| 743 RemovePushArguments(call); | 727 RemovePushArguments(call); |
| 744 return true; | 728 return true; |
| 745 } | 729 } |
| 746 | 730 |
| 747 if (recognized_kind == MethodRecognizer::kStringBaseLength) { | 731 if (recognized_kind == MethodRecognizer::kStringBaseLength) { |
| 748 if (!HasOneTarget(ic_data)) { | 732 if (!ic_data.HasOneTarget()) { |
| 749 // Target is not only StringBase_get_length. | 733 // Target is not only StringBase_get_length. |
| 750 return false; | 734 return false; |
| 751 } | 735 } |
| 752 // Check receiver class. | 736 // Check receiver class. |
| 753 AddCheckClass(call, call->ArgumentAt(0)->value()->Copy()); | 737 AddCheckClass(call, call->ArgumentAt(0)->value()->Copy()); |
| 754 | 738 |
| 755 const bool is_immutable = true; // String length is immutable. | 739 const bool is_immutable = true; // String length is immutable. |
| 756 LoadFieldInstr* load = new LoadFieldInstr( | 740 LoadFieldInstr* load = new LoadFieldInstr( |
| 757 call->ArgumentAt(0)->value(), | 741 call->ArgumentAt(0)->value(), |
| 758 String::length_offset(), | 742 String::length_offset(), |
| 759 Type::ZoneHandle(Type::SmiType()), | 743 Type::ZoneHandle(Type::SmiType()), |
| 760 is_immutable); | 744 is_immutable); |
| 761 load->set_result_cid(kSmiCid); | 745 load->set_result_cid(kSmiCid); |
| 762 call->ReplaceWith(load, current_iterator()); | 746 call->ReplaceWith(load, current_iterator()); |
| 763 RemovePushArguments(call); | 747 RemovePushArguments(call); |
| 764 return true; | 748 return true; |
| 765 } | 749 } |
| 766 return false; | 750 return false; |
| 767 } | 751 } |
| 768 | 752 |
| 769 | 753 |
| 770 // Inline only simple, frequently called core library methods. | 754 // Inline only simple, frequently called core library methods. |
| 771 bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallInstr* call) { | 755 bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallInstr* call) { |
| 772 ASSERT(call->HasICData()); | 756 ASSERT(call->HasICData()); |
| 773 const ICData& ic_data = *call->ic_data(); | 757 const ICData& ic_data = *call->ic_data(); |
| 774 if ((ic_data.NumberOfChecks() == 0) || !HasOneTarget(ic_data)) { | 758 if ((ic_data.NumberOfChecks() == 0) || !ic_data.HasOneTarget()) { |
| 775 // No type feedback collected. | 759 // No type feedback collected. |
| 776 return false; | 760 return false; |
| 777 } | 761 } |
| 778 Function& target = Function::Handle(); | 762 Function& target = Function::Handle(); |
| 779 GrowableArray<intptr_t> class_ids; | 763 GrowableArray<intptr_t> class_ids; |
| 780 ic_data.GetCheckAt(0, &class_ids, &target); | 764 ic_data.GetCheckAt(0, &class_ids, &target); |
| 781 MethodRecognizer::Kind recognized_kind = | 765 MethodRecognizer::Kind recognized_kind = |
| 782 MethodRecognizer::RecognizeKind(target); | 766 MethodRecognizer::RecognizeKind(target); |
| 783 | 767 |
| 784 if ((recognized_kind == MethodRecognizer::kDoubleToDouble) && | 768 if ((recognized_kind == MethodRecognizer::kDoubleToDouble) && |
| (...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 832 PolymorphicInstanceCallInstr* call = | 816 PolymorphicInstanceCallInstr* call = |
| 833 new PolymorphicInstanceCallInstr(instr, unary_checks, | 817 new PolymorphicInstanceCallInstr(instr, unary_checks, |
| 834 call_with_checks); | 818 call_with_checks); |
| 835 instr->ReplaceWith(call, current_iterator()); | 819 instr->ReplaceWith(call, current_iterator()); |
| 836 return; | 820 return; |
| 837 } | 821 } |
| 838 const intptr_t kMaxChecks = 4; | 822 const intptr_t kMaxChecks = 4; |
| 839 if (instr->ic_data()->NumberOfChecks() <= kMaxChecks) { | 823 if (instr->ic_data()->NumberOfChecks() <= kMaxChecks) { |
| 840 bool call_with_checks; | 824 bool call_with_checks; |
| 841 // TODO(srdjan): Add check class instr for mixed smi/non-smi. | 825 // TODO(srdjan): Add check class instr for mixed smi/non-smi. |
| 842 if (HasOneTarget(unary_checks) && | 826 if (unary_checks.HasOneTarget() && |
| 843 (unary_checks.GetReceiverClassIdAt(0) != kSmiCid)) { | 827 (unary_checks.GetReceiverClassIdAt(0) != kSmiCid)) { |
| 844 // Type propagation has not run yet, we cannot eliminate the check. | 828 // Type propagation has not run yet, we cannot eliminate the check. |
| 845 AddCheckClass(instr, instr->ArgumentAt(0)->value()->Copy()); | 829 AddCheckClass(instr, instr->ArgumentAt(0)->value()->Copy()); |
| 846 // Call can still deoptimize, do not detach environment from instr. | 830 // Call can still deoptimize, do not detach environment from instr. |
| 847 call_with_checks = false; | 831 call_with_checks = false; |
| 848 } else { | 832 } else { |
| 849 call_with_checks = true; | 833 call_with_checks = true; |
| 850 } | 834 } |
| 851 PolymorphicInstanceCallInstr* call = | 835 PolymorphicInstanceCallInstr* call = |
| 852 new PolymorphicInstanceCallInstr(instr, unary_checks, | 836 new PolymorphicInstanceCallInstr(instr, unary_checks, |
| (...skipping 23 matching lines...) Expand all Loading... |
| 876 return false; | 860 return false; |
| 877 } | 861 } |
| 878 | 862 |
| 879 ASSERT(instr->HasICData()); | 863 ASSERT(instr->HasICData()); |
| 880 const ICData& unary_ic_data = | 864 const ICData& unary_ic_data = |
| 881 ICData::Handle(instr->ic_data()->AsUnaryClassChecks()); | 865 ICData::Handle(instr->ic_data()->AsUnaryClassChecks()); |
| 882 if (unary_ic_data.NumberOfChecks() == 0) { | 866 if (unary_ic_data.NumberOfChecks() == 0) { |
| 883 // No type feedback collected. | 867 // No type feedback collected. |
| 884 return false; | 868 return false; |
| 885 } | 869 } |
| 886 if (!HasOneTarget(unary_ic_data)) { | 870 if (!unary_ic_data.HasOneTarget()) { |
| 887 // TODO(srdjan): Implement when not all targets are the same. | 871 // TODO(srdjan): Implement when not all targets are the same. |
| 888 return false; | 872 return false; |
| 889 } | 873 } |
| 890 Function& target = Function::Handle(); | 874 Function& target = Function::Handle(); |
| 891 intptr_t class_id; | 875 intptr_t class_id; |
| 892 unary_ic_data.GetOneClassCheckAt(0, &class_id, &target); | 876 unary_ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| 893 if (target.kind() != RawFunction::kImplicitSetter) { | 877 if (target.kind() != RawFunction::kImplicitSetter) { |
| 894 // Not an implicit setter. | 878 // Not an implicit setter. |
| 895 // TODO(srdjan): Inline special setters. | 879 // TODO(srdjan): Inline special setters. |
| 896 return false; | 880 return false; |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 931 // and computation, this helper can go away. | 915 // and computation, this helper can go away. |
| 932 static void HandleRelationalOp(FlowGraphOptimizer* optimizer, | 916 static void HandleRelationalOp(FlowGraphOptimizer* optimizer, |
| 933 RelationalOpInstr* comp, | 917 RelationalOpInstr* comp, |
| 934 Instruction* instr) { | 918 Instruction* instr) { |
| 935 if (!comp->HasICData()) return; | 919 if (!comp->HasICData()) return; |
| 936 | 920 |
| 937 const ICData& ic_data = *comp->ic_data(); | 921 const ICData& ic_data = *comp->ic_data(); |
| 938 if (ic_data.NumberOfChecks() == 0) return; | 922 if (ic_data.NumberOfChecks() == 0) return; |
| 939 // TODO(srdjan): Add multiple receiver type support. | 923 // TODO(srdjan): Add multiple receiver type support. |
| 940 if (ic_data.NumberOfChecks() != 1) return; | 924 if (ic_data.NumberOfChecks() != 1) return; |
| 941 ASSERT(HasOneTarget(ic_data)); | 925 ASSERT(ic_data.HasOneTarget()); |
| 942 | 926 |
| 943 if (HasOnlyTwoSmi(ic_data)) { | 927 if (HasOnlyTwoSmi(ic_data)) { |
| 944 optimizer->InsertBefore( | 928 optimizer->InsertBefore( |
| 945 instr, | 929 instr, |
| 946 new CheckSmiInstr(comp->left()->Copy(), comp->deopt_id()), | 930 new CheckSmiInstr(comp->left()->Copy(), comp->deopt_id()), |
| 947 instr->env(), | 931 instr->env(), |
| 948 Definition::kEffect); | 932 Definition::kEffect); |
| 949 optimizer->InsertBefore( | 933 optimizer->InsertBefore( |
| 950 instr, | 934 instr, |
| 951 new CheckSmiInstr(comp->right()->Copy(), comp->deopt_id()), | 935 new CheckSmiInstr(comp->right()->Copy(), comp->deopt_id()), |
| (...skipping 2095 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3047 | 3031 |
| 3048 if (FLAG_trace_constant_propagation) { | 3032 if (FLAG_trace_constant_propagation) { |
| 3049 OS::Print("\n==== After constant propagation ====\n"); | 3033 OS::Print("\n==== After constant propagation ====\n"); |
| 3050 FlowGraphPrinter printer(*graph_); | 3034 FlowGraphPrinter printer(*graph_); |
| 3051 printer.PrintBlocks(); | 3035 printer.PrintBlocks(); |
| 3052 } | 3036 } |
| 3053 } | 3037 } |
| 3054 | 3038 |
| 3055 | 3039 |
| 3056 } // namespace dart | 3040 } // namespace dart |
| OLD | NEW |