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_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/branch_optimizer.h" | 8 #include "vm/branch_optimizer.h" |
9 #include "vm/cha.h" | 9 #include "vm/cha.h" |
10 #include "vm/compiler.h" | 10 #include "vm/compiler.h" |
11 #include "vm/cpu.h" | 11 #include "vm/cpu.h" |
12 #include "vm/dart_entry.h" | 12 #include "vm/dart_entry.h" |
13 #include "vm/exceptions.h" | 13 #include "vm/exceptions.h" |
14 #include "vm/flow_graph_builder.h" | 14 #include "vm/flow_graph_builder.h" |
15 #include "vm/flow_graph_compiler.h" | 15 #include "vm/flow_graph_compiler.h" |
16 #include "vm/flow_graph_inliner.h" | 16 #include "vm/flow_graph_inliner.h" |
17 #include "vm/flow_graph_range_analysis.h" | 17 #include "vm/flow_graph_range_analysis.h" |
18 #include "vm/hash_map.h" | 18 #include "vm/hash_map.h" |
19 #include "vm/il_printer.h" | 19 #include "vm/il_printer.h" |
20 #include "vm/intermediate_language.h" | 20 #include "vm/intermediate_language.h" |
21 #include "vm/object_store.h" | 21 #include "vm/object_store.h" |
22 #include "vm/parser.h" | 22 #include "vm/parser.h" |
23 #include "vm/precompiler.h" | |
24 #include "vm/resolver.h" | 23 #include "vm/resolver.h" |
25 #include "vm/scopes.h" | 24 #include "vm/scopes.h" |
26 #include "vm/stack_frame.h" | 25 #include "vm/stack_frame.h" |
27 #include "vm/symbols.h" | 26 #include "vm/symbols.h" |
28 | 27 |
29 namespace dart { | 28 namespace dart { |
30 | 29 |
31 DEFINE_FLAG(int, getter_setter_ratio, 13, | |
32 "Ratio of getter/setter usage used for double field unboxing heuristics"); | |
33 DEFINE_FLAG(bool, guess_icdata_cid, true, | |
34 "Artificially create type feedback for arithmetic etc. operations" | |
35 " by guessing the other unknown argument cid"); | |
36 DEFINE_FLAG(int, max_polymorphic_checks, 4, | |
37 "Maximum number of polymorphic check, otherwise it is megamorphic."); | |
38 DEFINE_FLAG(int, max_equality_polymorphic_checks, 32, | |
39 "Maximum number of polymorphic checks in equality operator," | |
40 " otherwise use megamorphic dispatch."); | |
41 DEFINE_FLAG(bool, merge_sin_cos, false, "Merge sin/cos into sincos"); | |
42 DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details."); | |
43 DEFINE_FLAG(bool, truncating_left_shift, true, | |
44 "Optimize left shift to truncate if possible"); | |
45 DEFINE_FLAG(bool, use_cha_deopt, true, | |
46 "Use class hierarchy analysis even if it can cause deoptimization."); | |
47 | |
48 DECLARE_FLAG(bool, precompilation); | |
49 DECLARE_FLAG(bool, polymorphic_with_deopt); | |
50 DECLARE_FLAG(bool, trace_cha); | |
51 DECLARE_FLAG(bool, trace_field_guards); | |
52 | |
53 // Quick access to the current isolate and zone. | 30 // Quick access to the current isolate and zone. |
54 #define I (isolate()) | 31 #define I (isolate()) |
55 #define Z (zone()) | 32 #define Z (zone()) |
56 | 33 |
57 static bool ShouldInlineSimd() { | 34 static bool ShouldInlineSimd() { |
58 return FlowGraphCompiler::SupportsUnboxedSimd128(); | 35 return FlowGraphCompiler::SupportsUnboxedSimd128(); |
59 } | 36 } |
60 | 37 |
61 | 38 |
62 static bool CanUnboxDouble() { | 39 static bool CanUnboxDouble() { |
63 return FlowGraphCompiler::SupportsUnboxedDoubles(); | 40 return FlowGraphCompiler::SupportsUnboxedDoubles(); |
64 } | 41 } |
65 | 42 |
66 | 43 |
67 static bool CanConvertUnboxedMintToDouble() { | 44 static bool CanConvertUnboxedMintToDouble() { |
68 return FlowGraphCompiler::CanConvertUnboxedMintToDouble(); | 45 return FlowGraphCompiler::CanConvertUnboxedMintToDouble(); |
69 } | 46 } |
70 | 47 |
71 | 48 |
72 // Optimize instance calls using ICData. | 49 // Optimize instance calls using ICData. |
73 void FlowGraphOptimizer::ApplyICData() { | 50 void FlowGraphOptimizer::ApplyICData() { |
74 VisitBlocks(); | 51 VisitBlocks(); |
75 } | 52 } |
76 | 53 |
77 | 54 |
78 void FlowGraphOptimizer::PopulateWithICData() { | |
79 ASSERT(current_iterator_ == NULL); | |
80 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | |
81 !block_it.Done(); | |
82 block_it.Advance()) { | |
83 ForwardInstructionIterator it(block_it.Current()); | |
84 for (; !it.Done(); it.Advance()) { | |
85 Instruction* instr = it.Current(); | |
86 if (instr->IsInstanceCall()) { | |
87 InstanceCallInstr* call = instr->AsInstanceCall(); | |
88 if (!call->HasICData()) { | |
89 const Array& arguments_descriptor = | |
90 Array::Handle(zone(), | |
91 ArgumentsDescriptor::New(call->ArgumentCount(), | |
92 call->argument_names())); | |
93 const ICData& ic_data = ICData::ZoneHandle(zone(), ICData::New( | |
94 function(), call->function_name(), | |
95 arguments_descriptor, call->deopt_id(), | |
96 call->checked_argument_count())); | |
97 call->set_ic_data(&ic_data); | |
98 } | |
99 } | |
100 } | |
101 current_iterator_ = NULL; | |
102 } | |
103 } | |
104 | |
105 | |
106 // Optimize instance calls using cid. This is called after optimizer | 55 // Optimize instance calls using cid. This is called after optimizer |
107 // converted instance calls to instructions. Any remaining | 56 // converted instance calls to instructions. Any remaining |
108 // instance calls are either megamorphic calls, cannot be optimized or | 57 // instance calls are either megamorphic calls, cannot be optimized or |
109 // have no runtime type feedback collected. | 58 // have no runtime type feedback collected. |
110 // Attempts to convert an instance call (IC call) using propagated class-ids, | 59 // Attempts to convert an instance call (IC call) using propagated class-ids, |
111 // e.g., receiver class id, guarded-cid, or by guessing cid-s. | 60 // e.g., receiver class id, guarded-cid, or by guessing cid-s. |
112 void FlowGraphOptimizer::ApplyClassIds() { | 61 void FlowGraphOptimizer::ApplyClassIds() { |
113 ASSERT(current_iterator_ == NULL); | 62 ASSERT(current_iterator_ == NULL); |
114 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 63 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
115 !block_it.Done(); | 64 !block_it.Done(); |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 if (class_ids.length() > 1) { | 159 if (class_ids.length() > 1) { |
211 ic_data.AddCheck(class_ids, function); | 160 ic_data.AddCheck(class_ids, function); |
212 } else { | 161 } else { |
213 ASSERT(class_ids.length() == 1); | 162 ASSERT(class_ids.length() == 1); |
214 ic_data.AddReceiverCheck(class_ids[0], function); | 163 ic_data.AddReceiverCheck(class_ids[0], function); |
215 } | 164 } |
216 call->set_ic_data(&ic_data); | 165 call->set_ic_data(&ic_data); |
217 return true; | 166 return true; |
218 } | 167 } |
219 | 168 |
220 #ifdef DART_PRECOMPILER | |
221 if (FLAG_precompilation && | |
222 (isolate()->object_store()->unique_dynamic_targets() != Array::null())) { | |
223 // Check if the target is unique. | |
224 Function& target_function = Function::Handle(Z); | |
225 Precompiler::GetUniqueDynamicTarget( | |
226 isolate(), call->function_name(), &target_function); | |
227 // Calls with named arguments must be resolved/checked at runtime. | |
228 String& error_message = String::Handle(Z); | |
229 if (!target_function.IsNull() && | |
230 !target_function.HasOptionalNamedParameters() && | |
231 target_function.AreValidArgumentCounts(call->ArgumentCount(), 0, | |
232 &error_message)) { | |
233 const intptr_t cid = Class::Handle(Z, target_function.Owner()).id(); | |
234 const ICData& ic_data = ICData::ZoneHandle(Z, | |
235 ICData::NewFrom(*call->ic_data(), 1)); | |
236 ic_data.AddReceiverCheck(cid, target_function); | |
237 call->set_ic_data(&ic_data); | |
238 return true; | |
239 } | |
240 } | |
241 #endif | |
242 | |
243 // Check if getter or setter in function's class and class is currently leaf. | 169 // Check if getter or setter in function's class and class is currently leaf. |
244 if (FLAG_guess_icdata_cid && | 170 if (FLAG_guess_icdata_cid && |
245 ((call->token_kind() == Token::kGET) || | 171 ((call->token_kind() == Token::kGET) || |
246 (call->token_kind() == Token::kSET))) { | 172 (call->token_kind() == Token::kSET))) { |
247 const Class& owner_class = Class::Handle(Z, function().Owner()); | 173 const Class& owner_class = Class::Handle(Z, function().Owner()); |
248 if (!owner_class.is_abstract() && | 174 if (!owner_class.is_abstract() && |
249 !CHA::HasSubclasses(owner_class) && | 175 !CHA::HasSubclasses(owner_class) && |
250 !CHA::IsImplemented(owner_class)) { | 176 !CHA::IsImplemented(owner_class)) { |
251 const Array& args_desc_array = Array::Handle(Z, | 177 const Array& args_desc_array = Array::Handle(Z, |
252 ArgumentsDescriptor::New(call->ArgumentCount(), | 178 ArgumentsDescriptor::New(call->ArgumentCount(), |
(...skipping 1796 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2049 return true; | 1975 return true; |
2050 } | 1976 } |
2051 } | 1977 } |
2052 return false; | 1978 return false; |
2053 } | 1979 } |
2054 | 1980 |
2055 | 1981 |
2056 bool FlowGraphOptimizer::TryInlineFloat32x4Constructor( | 1982 bool FlowGraphOptimizer::TryInlineFloat32x4Constructor( |
2057 StaticCallInstr* call, | 1983 StaticCallInstr* call, |
2058 MethodRecognizer::Kind recognized_kind) { | 1984 MethodRecognizer::Kind recognized_kind) { |
2059 if (FLAG_precompilation) { | |
2060 // Cannot handle unboxed instructions. | |
2061 return false; | |
2062 } | |
2063 if (!ShouldInlineSimd()) { | 1985 if (!ShouldInlineSimd()) { |
2064 return false; | 1986 return false; |
2065 } | 1987 } |
2066 if (recognized_kind == MethodRecognizer::kFloat32x4Zero) { | 1988 if (recognized_kind == MethodRecognizer::kFloat32x4Zero) { |
2067 Float32x4ZeroInstr* zero = new(Z) Float32x4ZeroInstr(); | 1989 Float32x4ZeroInstr* zero = new(Z) Float32x4ZeroInstr(); |
2068 ReplaceCall(call, zero); | 1990 ReplaceCall(call, zero); |
2069 return true; | 1991 return true; |
2070 } else if (recognized_kind == MethodRecognizer::kFloat32x4Splat) { | 1992 } else if (recognized_kind == MethodRecognizer::kFloat32x4Splat) { |
2071 Float32x4SplatInstr* splat = | 1993 Float32x4SplatInstr* splat = |
2072 new(Z) Float32x4SplatInstr( | 1994 new(Z) Float32x4SplatInstr( |
(...skipping 23 matching lines...) Expand all Loading... |
2096 ReplaceCall(call, cast); | 2018 ReplaceCall(call, cast); |
2097 return true; | 2019 return true; |
2098 } | 2020 } |
2099 return false; | 2021 return false; |
2100 } | 2022 } |
2101 | 2023 |
2102 | 2024 |
2103 bool FlowGraphOptimizer::TryInlineFloat64x2Constructor( | 2025 bool FlowGraphOptimizer::TryInlineFloat64x2Constructor( |
2104 StaticCallInstr* call, | 2026 StaticCallInstr* call, |
2105 MethodRecognizer::Kind recognized_kind) { | 2027 MethodRecognizer::Kind recognized_kind) { |
2106 if (FLAG_precompilation) { | |
2107 // Cannot handle unboxed instructions. | |
2108 return false; | |
2109 } | |
2110 if (!ShouldInlineSimd()) { | 2028 if (!ShouldInlineSimd()) { |
2111 return false; | 2029 return false; |
2112 } | 2030 } |
2113 if (recognized_kind == MethodRecognizer::kFloat64x2Zero) { | 2031 if (recognized_kind == MethodRecognizer::kFloat64x2Zero) { |
2114 Float64x2ZeroInstr* zero = new(Z) Float64x2ZeroInstr(); | 2032 Float64x2ZeroInstr* zero = new(Z) Float64x2ZeroInstr(); |
2115 ReplaceCall(call, zero); | 2033 ReplaceCall(call, zero); |
2116 return true; | 2034 return true; |
2117 } else if (recognized_kind == MethodRecognizer::kFloat64x2Splat) { | 2035 } else if (recognized_kind == MethodRecognizer::kFloat64x2Splat) { |
2118 Float64x2SplatInstr* splat = | 2036 Float64x2SplatInstr* splat = |
2119 new(Z) Float64x2SplatInstr( | 2037 new(Z) Float64x2SplatInstr( |
(...skipping 15 matching lines...) Expand all Loading... |
2135 ReplaceCall(call, cast); | 2053 ReplaceCall(call, cast); |
2136 return true; | 2054 return true; |
2137 } | 2055 } |
2138 return false; | 2056 return false; |
2139 } | 2057 } |
2140 | 2058 |
2141 | 2059 |
2142 bool FlowGraphOptimizer::TryInlineInt32x4Constructor( | 2060 bool FlowGraphOptimizer::TryInlineInt32x4Constructor( |
2143 StaticCallInstr* call, | 2061 StaticCallInstr* call, |
2144 MethodRecognizer::Kind recognized_kind) { | 2062 MethodRecognizer::Kind recognized_kind) { |
2145 if (FLAG_precompilation) { | |
2146 // Cannot handle unboxed instructions. | |
2147 return false; | |
2148 } | |
2149 if (!ShouldInlineSimd()) { | 2063 if (!ShouldInlineSimd()) { |
2150 return false; | 2064 return false; |
2151 } | 2065 } |
2152 if (recognized_kind == MethodRecognizer::kInt32x4BoolConstructor) { | 2066 if (recognized_kind == MethodRecognizer::kInt32x4BoolConstructor) { |
2153 Int32x4BoolConstructorInstr* con = | 2067 Int32x4BoolConstructorInstr* con = |
2154 new(Z) Int32x4BoolConstructorInstr( | 2068 new(Z) Int32x4BoolConstructorInstr( |
2155 new(Z) Value(call->ArgumentAt(1)), | 2069 new(Z) Value(call->ArgumentAt(1)), |
2156 new(Z) Value(call->ArgumentAt(2)), | 2070 new(Z) Value(call->ArgumentAt(2)), |
2157 new(Z) Value(call->ArgumentAt(3)), | 2071 new(Z) Value(call->ArgumentAt(3)), |
2158 new(Z) Value(call->ArgumentAt(4)), | 2072 new(Z) Value(call->ArgumentAt(4)), |
(...skipping 770 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2929 /* with_checks = */ false); | 2843 /* with_checks = */ false); |
2930 instr->ReplaceWith(call, current_iterator()); | 2844 instr->ReplaceWith(call, current_iterator()); |
2931 return; | 2845 return; |
2932 } | 2846 } |
2933 } | 2847 } |
2934 | 2848 |
2935 | 2849 |
2936 // Tries to optimize instance call by replacing it with a faster instruction | 2850 // Tries to optimize instance call by replacing it with a faster instruction |
2937 // (e.g, binary op, field load, ..). | 2851 // (e.g, binary op, field load, ..). |
2938 void FlowGraphOptimizer::VisitInstanceCall(InstanceCallInstr* instr) { | 2852 void FlowGraphOptimizer::VisitInstanceCall(InstanceCallInstr* instr) { |
2939 if (FLAG_precompilation) { | |
2940 InstanceCallNoopt(instr); | |
2941 return; | |
2942 } | |
2943 | |
2944 if (!instr->HasICData() || (instr->ic_data()->NumberOfUsedChecks() == 0)) { | 2853 if (!instr->HasICData() || (instr->ic_data()->NumberOfUsedChecks() == 0)) { |
2945 return; | 2854 return; |
2946 } | 2855 } |
2947 const Token::Kind op_kind = instr->token_kind(); | 2856 const Token::Kind op_kind = instr->token_kind(); |
2948 | 2857 |
2949 // Type test is special as it always gets converted into inlined code. | 2858 // Type test is special as it always gets converted into inlined code. |
2950 if (Token::IsTypeTestOperator(op_kind)) { | 2859 if (Token::IsTypeTestOperator(op_kind)) { |
2951 ReplaceWithInstanceOf(instr); | 2860 ReplaceWithInstanceOf(instr); |
2952 return; | 2861 return; |
2953 } | 2862 } |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3061 unary_kind = MathUnaryInstr::kSin; | 2970 unary_kind = MathUnaryInstr::kSin; |
3062 break; | 2971 break; |
3063 case MethodRecognizer::kMathCos: | 2972 case MethodRecognizer::kMathCos: |
3064 unary_kind = MathUnaryInstr::kCos; | 2973 unary_kind = MathUnaryInstr::kCos; |
3065 break; | 2974 break; |
3066 default: | 2975 default: |
3067 unary_kind = MathUnaryInstr::kIllegal; | 2976 unary_kind = MathUnaryInstr::kIllegal; |
3068 break; | 2977 break; |
3069 } | 2978 } |
3070 if (unary_kind != MathUnaryInstr::kIllegal) { | 2979 if (unary_kind != MathUnaryInstr::kIllegal) { |
3071 if (FLAG_precompilation) { | |
3072 // TODO(srdjan): Adapt MathUnaryInstr to allow tagged inputs as well. | |
3073 return; | |
3074 } | |
3075 MathUnaryInstr* math_unary = | 2980 MathUnaryInstr* math_unary = |
3076 new(Z) MathUnaryInstr(unary_kind, | 2981 new(Z) MathUnaryInstr(unary_kind, |
3077 new(Z) Value(call->ArgumentAt(0)), | 2982 new(Z) Value(call->ArgumentAt(0)), |
3078 call->deopt_id()); | 2983 call->deopt_id()); |
3079 ReplaceCall(call, math_unary); | 2984 ReplaceCall(call, math_unary); |
3080 return; | 2985 return; |
3081 } | 2986 } |
3082 switch (recognized_kind) { | 2987 switch (recognized_kind) { |
3083 case MethodRecognizer::kFloat32x4Zero: | 2988 case MethodRecognizer::kFloat32x4Zero: |
3084 case MethodRecognizer::kFloat32x4Splat: | 2989 case MethodRecognizer::kFloat32x4Splat: |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3147 } | 3052 } |
3148 } | 3053 } |
3149 break; | 3054 break; |
3150 } | 3055 } |
3151 case MethodRecognizer::kMathDoublePow: | 3056 case MethodRecognizer::kMathDoublePow: |
3152 case MethodRecognizer::kMathTan: | 3057 case MethodRecognizer::kMathTan: |
3153 case MethodRecognizer::kMathAsin: | 3058 case MethodRecognizer::kMathAsin: |
3154 case MethodRecognizer::kMathAcos: | 3059 case MethodRecognizer::kMathAcos: |
3155 case MethodRecognizer::kMathAtan: | 3060 case MethodRecognizer::kMathAtan: |
3156 case MethodRecognizer::kMathAtan2: { | 3061 case MethodRecognizer::kMathAtan2: { |
3157 if (FLAG_precompilation) { | |
3158 // No UnboxDouble instructons allowed. | |
3159 return; | |
3160 } | |
3161 // InvokeMathCFunctionInstr requires unboxed doubles. UnboxDouble | 3062 // InvokeMathCFunctionInstr requires unboxed doubles. UnboxDouble |
3162 // instructions contain type checks and conversions to double. | 3063 // instructions contain type checks and conversions to double. |
3163 ZoneGrowableArray<Value*>* args = | 3064 ZoneGrowableArray<Value*>* args = |
3164 new(Z) ZoneGrowableArray<Value*>(call->ArgumentCount()); | 3065 new(Z) ZoneGrowableArray<Value*>(call->ArgumentCount()); |
3165 for (intptr_t i = 0; i < call->ArgumentCount(); i++) { | 3066 for (intptr_t i = 0; i < call->ArgumentCount(); i++) { |
3166 args->Add(new(Z) Value(call->ArgumentAt(i))); | 3067 args->Add(new(Z) Value(call->ArgumentAt(i))); |
3167 } | 3068 } |
3168 InvokeMathCFunctionInstr* invoke = | 3069 InvokeMathCFunctionInstr* invoke = |
3169 new(Z) InvokeMathCFunctionInstr(args, | 3070 new(Z) InvokeMathCFunctionInstr(args, |
3170 call->deopt_id(), | 3071 call->deopt_id(), |
(...skipping 235 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3406 | 3307 |
3407 // Discard the environment from the original instruction because the store | 3308 // Discard the environment from the original instruction because the store |
3408 // can't deoptimize. | 3309 // can't deoptimize. |
3409 instr->RemoveEnvironment(); | 3310 instr->RemoveEnvironment(); |
3410 ReplaceCall(instr, store); | 3311 ReplaceCall(instr, store); |
3411 return true; | 3312 return true; |
3412 } | 3313 } |
3413 | 3314 |
3414 | 3315 |
3415 } // namespace dart | 3316 } // namespace dart |
OLD | NEW |