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 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
211 if (class_ids.length() > 1) { | 160 if (class_ids.length() > 1) { |
212 ic_data.AddCheck(class_ids, function); | 161 ic_data.AddCheck(class_ids, function); |
213 } else { | 162 } else { |
214 ASSERT(class_ids.length() == 1); | 163 ASSERT(class_ids.length() == 1); |
215 ic_data.AddReceiverCheck(class_ids[0], function); | 164 ic_data.AddReceiverCheck(class_ids[0], function); |
216 } | 165 } |
217 call->set_ic_data(&ic_data); | 166 call->set_ic_data(&ic_data); |
218 return true; | 167 return true; |
219 } | 168 } |
220 | 169 |
221 #ifdef DART_PRECOMPILER | |
222 if (FLAG_precompilation && | |
223 (isolate()->object_store()->unique_dynamic_targets() != Array::null())) { | |
224 // Check if the target is unique. | |
225 Function& target_function = Function::Handle(Z); | |
226 Precompiler::GetUniqueDynamicTarget( | |
227 isolate(), call->function_name(), &target_function); | |
228 // Calls with named arguments must be resolved/checked at runtime. | |
229 String& error_message = String::Handle(Z); | |
230 if (!target_function.IsNull() && | |
231 !target_function.HasOptionalNamedParameters() && | |
232 target_function.AreValidArgumentCounts(call->ArgumentCount(), 0, | |
233 &error_message)) { | |
234 const intptr_t cid = Class::Handle(Z, target_function.Owner()).id(); | |
235 const ICData& ic_data = ICData::ZoneHandle(Z, | |
236 ICData::NewFrom(*call->ic_data(), 1)); | |
237 ic_data.AddReceiverCheck(cid, target_function); | |
238 call->set_ic_data(&ic_data); | |
239 return true; | |
240 } | |
241 } | |
242 #endif | |
243 | |
244 // Check if getter or setter in function's class and class is currently leaf. | 170 // Check if getter or setter in function's class and class is currently leaf. |
245 if (FLAG_guess_icdata_cid && | 171 if (FLAG_guess_icdata_cid && |
246 ((call->token_kind() == Token::kGET) || | 172 ((call->token_kind() == Token::kGET) || |
247 (call->token_kind() == Token::kSET))) { | 173 (call->token_kind() == Token::kSET))) { |
248 const Class& owner_class = Class::Handle(Z, function().Owner()); | 174 const Class& owner_class = Class::Handle(Z, function().Owner()); |
249 if (!owner_class.is_abstract() && | 175 if (!owner_class.is_abstract() && |
250 !CHA::HasSubclasses(owner_class) && | 176 !CHA::HasSubclasses(owner_class) && |
251 !CHA::IsImplemented(owner_class)) { | 177 !CHA::IsImplemented(owner_class)) { |
252 const Array& args_desc_array = Array::Handle(Z, | 178 const Array& args_desc_array = Array::Handle(Z, |
253 ArgumentsDescriptor::New(call->ArgumentCount(), | 179 ArgumentsDescriptor::New(call->ArgumentCount(), |
(...skipping 1797 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2051 return true; | 1977 return true; |
2052 } | 1978 } |
2053 } | 1979 } |
2054 return false; | 1980 return false; |
2055 } | 1981 } |
2056 | 1982 |
2057 | 1983 |
2058 bool FlowGraphOptimizer::TryInlineFloat32x4Constructor( | 1984 bool FlowGraphOptimizer::TryInlineFloat32x4Constructor( |
2059 StaticCallInstr* call, | 1985 StaticCallInstr* call, |
2060 MethodRecognizer::Kind recognized_kind) { | 1986 MethodRecognizer::Kind recognized_kind) { |
2061 if (FLAG_precompilation) { | |
2062 // Cannot handle unboxed instructions. | |
2063 return false; | |
2064 } | |
2065 if (!ShouldInlineSimd()) { | 1987 if (!ShouldInlineSimd()) { |
2066 return false; | 1988 return false; |
2067 } | 1989 } |
2068 if (recognized_kind == MethodRecognizer::kFloat32x4Zero) { | 1990 if (recognized_kind == MethodRecognizer::kFloat32x4Zero) { |
2069 Float32x4ZeroInstr* zero = new(Z) Float32x4ZeroInstr(); | 1991 Float32x4ZeroInstr* zero = new(Z) Float32x4ZeroInstr(); |
2070 ReplaceCall(call, zero); | 1992 ReplaceCall(call, zero); |
2071 return true; | 1993 return true; |
2072 } else if (recognized_kind == MethodRecognizer::kFloat32x4Splat) { | 1994 } else if (recognized_kind == MethodRecognizer::kFloat32x4Splat) { |
2073 Float32x4SplatInstr* splat = | 1995 Float32x4SplatInstr* splat = |
2074 new(Z) Float32x4SplatInstr( | 1996 new(Z) Float32x4SplatInstr( |
(...skipping 23 matching lines...) Expand all Loading... |
2098 ReplaceCall(call, cast); | 2020 ReplaceCall(call, cast); |
2099 return true; | 2021 return true; |
2100 } | 2022 } |
2101 return false; | 2023 return false; |
2102 } | 2024 } |
2103 | 2025 |
2104 | 2026 |
2105 bool FlowGraphOptimizer::TryInlineFloat64x2Constructor( | 2027 bool FlowGraphOptimizer::TryInlineFloat64x2Constructor( |
2106 StaticCallInstr* call, | 2028 StaticCallInstr* call, |
2107 MethodRecognizer::Kind recognized_kind) { | 2029 MethodRecognizer::Kind recognized_kind) { |
2108 if (FLAG_precompilation) { | |
2109 // Cannot handle unboxed instructions. | |
2110 return false; | |
2111 } | |
2112 if (!ShouldInlineSimd()) { | 2030 if (!ShouldInlineSimd()) { |
2113 return false; | 2031 return false; |
2114 } | 2032 } |
2115 if (recognized_kind == MethodRecognizer::kFloat64x2Zero) { | 2033 if (recognized_kind == MethodRecognizer::kFloat64x2Zero) { |
2116 Float64x2ZeroInstr* zero = new(Z) Float64x2ZeroInstr(); | 2034 Float64x2ZeroInstr* zero = new(Z) Float64x2ZeroInstr(); |
2117 ReplaceCall(call, zero); | 2035 ReplaceCall(call, zero); |
2118 return true; | 2036 return true; |
2119 } else if (recognized_kind == MethodRecognizer::kFloat64x2Splat) { | 2037 } else if (recognized_kind == MethodRecognizer::kFloat64x2Splat) { |
2120 Float64x2SplatInstr* splat = | 2038 Float64x2SplatInstr* splat = |
2121 new(Z) Float64x2SplatInstr( | 2039 new(Z) Float64x2SplatInstr( |
(...skipping 15 matching lines...) Expand all Loading... |
2137 ReplaceCall(call, cast); | 2055 ReplaceCall(call, cast); |
2138 return true; | 2056 return true; |
2139 } | 2057 } |
2140 return false; | 2058 return false; |
2141 } | 2059 } |
2142 | 2060 |
2143 | 2061 |
2144 bool FlowGraphOptimizer::TryInlineInt32x4Constructor( | 2062 bool FlowGraphOptimizer::TryInlineInt32x4Constructor( |
2145 StaticCallInstr* call, | 2063 StaticCallInstr* call, |
2146 MethodRecognizer::Kind recognized_kind) { | 2064 MethodRecognizer::Kind recognized_kind) { |
2147 if (FLAG_precompilation) { | |
2148 // Cannot handle unboxed instructions. | |
2149 return false; | |
2150 } | |
2151 if (!ShouldInlineSimd()) { | 2065 if (!ShouldInlineSimd()) { |
2152 return false; | 2066 return false; |
2153 } | 2067 } |
2154 if (recognized_kind == MethodRecognizer::kInt32x4BoolConstructor) { | 2068 if (recognized_kind == MethodRecognizer::kInt32x4BoolConstructor) { |
2155 Int32x4BoolConstructorInstr* con = | 2069 Int32x4BoolConstructorInstr* con = |
2156 new(Z) Int32x4BoolConstructorInstr( | 2070 new(Z) Int32x4BoolConstructorInstr( |
2157 new(Z) Value(call->ArgumentAt(1)), | 2071 new(Z) Value(call->ArgumentAt(1)), |
2158 new(Z) Value(call->ArgumentAt(2)), | 2072 new(Z) Value(call->ArgumentAt(2)), |
2159 new(Z) Value(call->ArgumentAt(3)), | 2073 new(Z) Value(call->ArgumentAt(3)), |
2160 new(Z) Value(call->ArgumentAt(4)), | 2074 new(Z) Value(call->ArgumentAt(4)), |
(...skipping 770 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2931 /* with_checks = */ false); | 2845 /* with_checks = */ false); |
2932 instr->ReplaceWith(call, current_iterator()); | 2846 instr->ReplaceWith(call, current_iterator()); |
2933 return; | 2847 return; |
2934 } | 2848 } |
2935 } | 2849 } |
2936 | 2850 |
2937 | 2851 |
2938 // Tries to optimize instance call by replacing it with a faster instruction | 2852 // Tries to optimize instance call by replacing it with a faster instruction |
2939 // (e.g, binary op, field load, ..). | 2853 // (e.g, binary op, field load, ..). |
2940 void FlowGraphOptimizer::VisitInstanceCall(InstanceCallInstr* instr) { | 2854 void FlowGraphOptimizer::VisitInstanceCall(InstanceCallInstr* instr) { |
2941 if (FLAG_precompilation) { | |
2942 InstanceCallNoopt(instr); | |
2943 return; | |
2944 } | |
2945 | |
2946 if (!instr->HasICData() || (instr->ic_data()->NumberOfUsedChecks() == 0)) { | 2855 if (!instr->HasICData() || (instr->ic_data()->NumberOfUsedChecks() == 0)) { |
2947 return; | 2856 return; |
2948 } | 2857 } |
2949 const Token::Kind op_kind = instr->token_kind(); | 2858 const Token::Kind op_kind = instr->token_kind(); |
2950 | 2859 |
2951 // Type test is special as it always gets converted into inlined code. | 2860 // Type test is special as it always gets converted into inlined code. |
2952 if (Token::IsTypeTestOperator(op_kind)) { | 2861 if (Token::IsTypeTestOperator(op_kind)) { |
2953 ReplaceWithInstanceOf(instr); | 2862 ReplaceWithInstanceOf(instr); |
2954 return; | 2863 return; |
2955 } | 2864 } |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3063 unary_kind = MathUnaryInstr::kSin; | 2972 unary_kind = MathUnaryInstr::kSin; |
3064 break; | 2973 break; |
3065 case MethodRecognizer::kMathCos: | 2974 case MethodRecognizer::kMathCos: |
3066 unary_kind = MathUnaryInstr::kCos; | 2975 unary_kind = MathUnaryInstr::kCos; |
3067 break; | 2976 break; |
3068 default: | 2977 default: |
3069 unary_kind = MathUnaryInstr::kIllegal; | 2978 unary_kind = MathUnaryInstr::kIllegal; |
3070 break; | 2979 break; |
3071 } | 2980 } |
3072 if (unary_kind != MathUnaryInstr::kIllegal) { | 2981 if (unary_kind != MathUnaryInstr::kIllegal) { |
3073 if (FLAG_precompilation) { | |
3074 // TODO(srdjan): Adapt MathUnaryInstr to allow tagged inputs as well. | |
3075 return; | |
3076 } | |
3077 MathUnaryInstr* math_unary = | 2982 MathUnaryInstr* math_unary = |
3078 new(Z) MathUnaryInstr(unary_kind, | 2983 new(Z) MathUnaryInstr(unary_kind, |
3079 new(Z) Value(call->ArgumentAt(0)), | 2984 new(Z) Value(call->ArgumentAt(0)), |
3080 call->deopt_id()); | 2985 call->deopt_id()); |
3081 ReplaceCall(call, math_unary); | 2986 ReplaceCall(call, math_unary); |
3082 return; | 2987 return; |
3083 } | 2988 } |
3084 switch (recognized_kind) { | 2989 switch (recognized_kind) { |
3085 case MethodRecognizer::kFloat32x4Zero: | 2990 case MethodRecognizer::kFloat32x4Zero: |
3086 case MethodRecognizer::kFloat32x4Splat: | 2991 case MethodRecognizer::kFloat32x4Splat: |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3149 } | 3054 } |
3150 } | 3055 } |
3151 break; | 3056 break; |
3152 } | 3057 } |
3153 case MethodRecognizer::kMathDoublePow: | 3058 case MethodRecognizer::kMathDoublePow: |
3154 case MethodRecognizer::kMathTan: | 3059 case MethodRecognizer::kMathTan: |
3155 case MethodRecognizer::kMathAsin: | 3060 case MethodRecognizer::kMathAsin: |
3156 case MethodRecognizer::kMathAcos: | 3061 case MethodRecognizer::kMathAcos: |
3157 case MethodRecognizer::kMathAtan: | 3062 case MethodRecognizer::kMathAtan: |
3158 case MethodRecognizer::kMathAtan2: { | 3063 case MethodRecognizer::kMathAtan2: { |
3159 if (FLAG_precompilation) { | |
3160 // No UnboxDouble instructons allowed. | |
3161 return; | |
3162 } | |
3163 // InvokeMathCFunctionInstr requires unboxed doubles. UnboxDouble | 3064 // InvokeMathCFunctionInstr requires unboxed doubles. UnboxDouble |
3164 // instructions contain type checks and conversions to double. | 3065 // instructions contain type checks and conversions to double. |
3165 ZoneGrowableArray<Value*>* args = | 3066 ZoneGrowableArray<Value*>* args = |
3166 new(Z) ZoneGrowableArray<Value*>(call->ArgumentCount()); | 3067 new(Z) ZoneGrowableArray<Value*>(call->ArgumentCount()); |
3167 for (intptr_t i = 0; i < call->ArgumentCount(); i++) { | 3068 for (intptr_t i = 0; i < call->ArgumentCount(); i++) { |
3168 args->Add(new(Z) Value(call->ArgumentAt(i))); | 3069 args->Add(new(Z) Value(call->ArgumentAt(i))); |
3169 } | 3070 } |
3170 InvokeMathCFunctionInstr* invoke = | 3071 InvokeMathCFunctionInstr* invoke = |
3171 new(Z) InvokeMathCFunctionInstr(args, | 3072 new(Z) InvokeMathCFunctionInstr(args, |
3172 call->deopt_id(), | 3073 call->deopt_id(), |
(...skipping 235 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3408 | 3309 |
3409 // Discard the environment from the original instruction because the store | 3310 // Discard the environment from the original instruction because the store |
3410 // can't deoptimize. | 3311 // can't deoptimize. |
3411 instr->RemoveEnvironment(); | 3312 instr->RemoveEnvironment(); |
3412 ReplaceCall(instr, store); | 3313 ReplaceCall(instr, store); |
3413 return true; | 3314 return true; |
3414 } | 3315 } |
3415 | 3316 |
3416 | 3317 |
3417 } // namespace dart | 3318 } // namespace dart |
OLD | NEW |