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.h" | 5 #include "vm/flow_graph.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/flow_graph_compiler.h" | 10 #include "vm/flow_graph_compiler.h" |
(...skipping 2042 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2053 return changed; | 2053 return changed; |
2054 } | 2054 } |
2055 | 2055 |
2056 | 2056 |
2057 // Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the | 2057 // Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the |
2058 // shift can be a truncating Smi shift-left and result is always Smi. | 2058 // shift can be a truncating Smi shift-left and result is always Smi. |
2059 // Merging occurs only per basic-block. | 2059 // Merging occurs only per basic-block. |
2060 void FlowGraph::TryOptimizePatterns() { | 2060 void FlowGraph::TryOptimizePatterns() { |
2061 if (!FLAG_truncating_left_shift) return; | 2061 if (!FLAG_truncating_left_shift) return; |
2062 GrowableArray<BinarySmiOpInstr*> div_mod_merge; | 2062 GrowableArray<BinarySmiOpInstr*> div_mod_merge; |
2063 GrowableArray<MathUnaryInstr*> sin_cos_merge; | 2063 GrowableArray<InvokeMathCFunctionInstr*> sin_cos_merge; |
2064 for (BlockIterator block_it = reverse_postorder_iterator(); | 2064 for (BlockIterator block_it = reverse_postorder_iterator(); |
2065 !block_it.Done(); | 2065 !block_it.Done(); |
2066 block_it.Advance()) { | 2066 block_it.Advance()) { |
2067 // Merging only per basic-block. | 2067 // Merging only per basic-block. |
2068 div_mod_merge.Clear(); | 2068 div_mod_merge.Clear(); |
2069 sin_cos_merge.Clear(); | 2069 sin_cos_merge.Clear(); |
2070 ForwardInstructionIterator it(block_it.Current()); | 2070 ForwardInstructionIterator it(block_it.Current()); |
2071 for (; !it.Done(); it.Advance()) { | 2071 for (; !it.Done(); it.Advance()) { |
2072 if (it.Current()->IsBinarySmiOp()) { | 2072 if (it.Current()->IsBinarySmiOp()) { |
2073 BinarySmiOpInstr* binop = it.Current()->AsBinarySmiOp(); | 2073 BinarySmiOpInstr* binop = it.Current()->AsBinarySmiOp(); |
2074 if (binop->op_kind() == Token::kBIT_AND) { | 2074 if (binop->op_kind() == Token::kBIT_AND) { |
2075 OptimizeLeftShiftBitAndSmiOp(&it, | 2075 OptimizeLeftShiftBitAndSmiOp(&it, |
2076 binop, | 2076 binop, |
2077 binop->left()->definition(), | 2077 binop->left()->definition(), |
2078 binop->right()->definition()); | 2078 binop->right()->definition()); |
2079 } else if ((binop->op_kind() == Token::kTRUNCDIV) || | 2079 } else if ((binop->op_kind() == Token::kTRUNCDIV) || |
2080 (binop->op_kind() == Token::kMOD)) { | 2080 (binop->op_kind() == Token::kMOD)) { |
2081 if (binop->HasUses()) { | 2081 if (binop->HasUses()) { |
2082 div_mod_merge.Add(binop); | 2082 div_mod_merge.Add(binop); |
2083 } | 2083 } |
2084 } | 2084 } |
2085 } else if (it.Current()->IsBinaryMintOp()) { | 2085 } else if (it.Current()->IsBinaryMintOp()) { |
2086 BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp(); | 2086 BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp(); |
2087 if (mintop->op_kind() == Token::kBIT_AND) { | 2087 if (mintop->op_kind() == Token::kBIT_AND) { |
2088 OptimizeLeftShiftBitAndSmiOp(&it, | 2088 OptimizeLeftShiftBitAndSmiOp(&it, |
2089 mintop, | 2089 mintop, |
2090 mintop->left()->definition(), | 2090 mintop->left()->definition(), |
2091 mintop->right()->definition()); | 2091 mintop->right()->definition()); |
2092 } | 2092 } |
2093 } else if (it.Current()->IsMathUnary()) { | 2093 } else if (it.Current()->IsInvokeMathCFunction()) { |
2094 MathUnaryInstr* math_unary = it.Current()->AsMathUnary(); | 2094 InvokeMathCFunctionInstr* math_unary = |
2095 if ((math_unary->kind() == MathUnaryInstr::kSin) || | 2095 it.Current()->AsInvokeMathCFunction(); |
2096 (math_unary->kind() == MathUnaryInstr::kCos)) { | 2096 if ((math_unary->recognized_kind() == MethodRecognizer::kMathSin) || |
| 2097 (math_unary->recognized_kind() == MethodRecognizer::kMathCos)) { |
2097 if (math_unary->HasUses()) { | 2098 if (math_unary->HasUses()) { |
2098 sin_cos_merge.Add(math_unary); | 2099 sin_cos_merge.Add(math_unary); |
2099 } | 2100 } |
2100 } | 2101 } |
2101 } | 2102 } |
2102 } | 2103 } |
2103 TryMergeTruncDivMod(&div_mod_merge); | 2104 TryMergeTruncDivMod(&div_mod_merge); |
2104 TryMergeMathUnary(&sin_cos_merge); | 2105 TryMergeMathUnary(&sin_cos_merge); |
2105 } | 2106 } |
2106 } | 2107 } |
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2188 } | 2189 } |
2189 for (intptr_t i = 0; i < merge_candidates->length(); i++) { | 2190 for (intptr_t i = 0; i < merge_candidates->length(); i++) { |
2190 BinarySmiOpInstr* curr_instr = (*merge_candidates)[i]; | 2191 BinarySmiOpInstr* curr_instr = (*merge_candidates)[i]; |
2191 if (curr_instr == NULL) { | 2192 if (curr_instr == NULL) { |
2192 // Instruction was merged already. | 2193 // Instruction was merged already. |
2193 continue; | 2194 continue; |
2194 } | 2195 } |
2195 ASSERT((curr_instr->op_kind() == Token::kTRUNCDIV) || | 2196 ASSERT((curr_instr->op_kind() == Token::kTRUNCDIV) || |
2196 (curr_instr->op_kind() == Token::kMOD)); | 2197 (curr_instr->op_kind() == Token::kMOD)); |
2197 // Check if there is kMOD/kTRUNDIV binop with same inputs. | 2198 // Check if there is kMOD/kTRUNDIV binop with same inputs. |
2198 const intptr_t other_kind = (curr_instr->op_kind() == Token::kTRUNCDIV) ? | 2199 const Token::Kind other_kind = (curr_instr->op_kind() == Token::kTRUNCDIV) ? |
2199 Token::kMOD : Token::kTRUNCDIV; | 2200 Token::kMOD : Token::kTRUNCDIV; |
2200 Definition* left_def = curr_instr->left()->definition(); | 2201 Definition* left_def = curr_instr->left()->definition(); |
2201 Definition* right_def = curr_instr->right()->definition(); | 2202 Definition* right_def = curr_instr->right()->definition(); |
2202 for (intptr_t k = i + 1; k < merge_candidates->length(); k++) { | 2203 for (intptr_t k = i + 1; k < merge_candidates->length(); k++) { |
2203 BinarySmiOpInstr* other_binop = (*merge_candidates)[k]; | 2204 BinarySmiOpInstr* other_binop = (*merge_candidates)[k]; |
2204 // 'other_binop' can be NULL if it was already merged. | 2205 // 'other_binop' can be NULL if it was already merged. |
2205 if ((other_binop != NULL) && | 2206 if ((other_binop != NULL) && |
2206 (other_binop->op_kind() == other_kind) && | 2207 (other_binop->op_kind() == other_kind) && |
2207 (other_binop->left()->definition() == left_def) && | 2208 (other_binop->left()->definition() == left_def) && |
2208 (other_binop->right()->definition() == right_def)) { | 2209 (other_binop->right()->definition() == right_def)) { |
(...skipping 26 matching lines...) Expand all Loading... |
2235 // TODO(srdjan): Allow merging of trunc-div/mod into truncDivMod. | 2236 // TODO(srdjan): Allow merging of trunc-div/mod into truncDivMod. |
2236 break; | 2237 break; |
2237 } | 2238 } |
2238 } | 2239 } |
2239 } | 2240 } |
2240 } | 2241 } |
2241 | 2242 |
2242 | 2243 |
2243 // Tries to merge MathUnary operations, in this case sine and cosine. | 2244 // Tries to merge MathUnary operations, in this case sine and cosine. |
2244 void FlowGraph::TryMergeMathUnary( | 2245 void FlowGraph::TryMergeMathUnary( |
2245 GrowableArray<MathUnaryInstr*>* merge_candidates) { | 2246 GrowableArray<InvokeMathCFunctionInstr*>* merge_candidates) { |
2246 if (!FlowGraphCompiler::SupportsSinCos() || !CanUnboxDouble() || | 2247 if (!FlowGraphCompiler::SupportsSinCos() || !CanUnboxDouble() || |
2247 !FLAG_merge_sin_cos) { | 2248 !FLAG_merge_sin_cos) { |
2248 return; | 2249 return; |
2249 } | 2250 } |
2250 if (merge_candidates->length() < 2) { | 2251 if (merge_candidates->length() < 2) { |
2251 // Need at least a SIN and a COS. | 2252 // Need at least a SIN and a COS. |
2252 return; | 2253 return; |
2253 } | 2254 } |
2254 for (intptr_t i = 0; i < merge_candidates->length(); i++) { | 2255 for (intptr_t i = 0; i < merge_candidates->length(); i++) { |
2255 MathUnaryInstr* curr_instr = (*merge_candidates)[i]; | 2256 InvokeMathCFunctionInstr* curr_instr = (*merge_candidates)[i]; |
2256 if (curr_instr == NULL) { | 2257 if (curr_instr == NULL) { |
2257 // Instruction was merged already. | 2258 // Instruction was merged already. |
2258 continue; | 2259 continue; |
2259 } | 2260 } |
2260 const intptr_t kind = curr_instr->kind(); | 2261 const MethodRecognizer::Kind kind = curr_instr->recognized_kind(); |
2261 ASSERT((kind == MathUnaryInstr::kSin) || | 2262 ASSERT((kind == MethodRecognizer::kMathSin) || |
2262 (kind == MathUnaryInstr::kCos)); | 2263 (kind == MethodRecognizer::kMathCos)); |
2263 // Check if there is sin/cos binop with same inputs. | 2264 // Check if there is sin/cos binop with same inputs. |
2264 const intptr_t other_kind = (kind == MathUnaryInstr::kSin) ? | 2265 const MethodRecognizer::Kind other_kind = |
2265 MathUnaryInstr::kCos : MathUnaryInstr::kSin; | 2266 (kind == MethodRecognizer::kMathSin) |
2266 Definition* def = curr_instr->value()->definition(); | 2267 ? MethodRecognizer::kMathCos : MethodRecognizer::kMathSin; |
| 2268 Definition* def = curr_instr->InputAt(0)->definition(); |
2267 for (intptr_t k = i + 1; k < merge_candidates->length(); k++) { | 2269 for (intptr_t k = i + 1; k < merge_candidates->length(); k++) { |
2268 MathUnaryInstr* other_op = (*merge_candidates)[k]; | 2270 InvokeMathCFunctionInstr* other_op = (*merge_candidates)[k]; |
2269 // 'other_op' can be NULL if it was already merged. | 2271 // 'other_op' can be NULL if it was already merged. |
2270 if ((other_op != NULL) && (other_op->kind() == other_kind) && | 2272 if ((other_op != NULL) && (other_op->recognized_kind() == other_kind) && |
2271 (other_op->value()->definition() == def)) { | 2273 (other_op->InputAt(0)->definition() == def)) { |
2272 (*merge_candidates)[k] = NULL; // Clear it. | 2274 (*merge_candidates)[k] = NULL; // Clear it. |
2273 ASSERT(curr_instr->HasUses()); | 2275 ASSERT(curr_instr->HasUses()); |
2274 AppendExtractNthOutputForMerged(curr_instr, | 2276 AppendExtractNthOutputForMerged(curr_instr, |
2275 MergedMathInstr::OutputIndexOf(kind), | 2277 MergedMathInstr::OutputIndexOf(kind), |
2276 kUnboxedDouble, kDoubleCid); | 2278 kUnboxedDouble, kDoubleCid); |
2277 ASSERT(other_op->HasUses()); | 2279 ASSERT(other_op->HasUses()); |
2278 AppendExtractNthOutputForMerged( | 2280 AppendExtractNthOutputForMerged( |
2279 other_op, | 2281 other_op, |
2280 MergedMathInstr::OutputIndexOf(other_kind), | 2282 MergedMathInstr::OutputIndexOf(other_kind), |
2281 kUnboxedDouble, kDoubleCid); | 2283 kUnboxedDouble, kDoubleCid); |
2282 ZoneGrowableArray<Value*>* args = new(Z) ZoneGrowableArray<Value*>(1); | 2284 ZoneGrowableArray<Value*>* args = new(Z) ZoneGrowableArray<Value*>(1); |
2283 args->Add(new(Z) Value(curr_instr->value()->definition())); | 2285 args->Add(new(Z) Value(curr_instr->InputAt(0)->definition())); |
2284 // Replace with SinCos. | 2286 // Replace with SinCos. |
2285 MergedMathInstr* sin_cos = | 2287 MergedMathInstr* sin_cos = |
2286 new(Z) MergedMathInstr(args, | 2288 new(Z) MergedMathInstr(args, |
2287 curr_instr->DeoptimizationTarget(), | 2289 curr_instr->DeoptimizationTarget(), |
2288 MergedMathInstr::kSinCos); | 2290 MergedMathInstr::kSinCos); |
2289 curr_instr->ReplaceWith(sin_cos, NULL); | 2291 curr_instr->ReplaceWith(sin_cos, NULL); |
2290 other_op->ReplaceUsesWith(sin_cos); | 2292 other_op->ReplaceUsesWith(sin_cos); |
2291 other_op->RemoveFromGraph(); | 2293 other_op->RemoveFromGraph(); |
2292 // Only one merge possible. Because canonicalization happens later, | 2294 // Only one merge possible. Because canonicalization happens later, |
2293 // more candidates are possible. | 2295 // more candidates are possible. |
(...skipping 12 matching lines...) Expand all Loading... |
2306 ExtractNthOutputInstr* extract = | 2308 ExtractNthOutputInstr* extract = |
2307 new(Z) ExtractNthOutputInstr(new(Z) Value(instr), index, rep, cid); | 2309 new(Z) ExtractNthOutputInstr(new(Z) Value(instr), index, rep, cid); |
2308 instr->ReplaceUsesWith(extract); | 2310 instr->ReplaceUsesWith(extract); |
2309 InsertAfter(instr, extract, NULL, FlowGraph::kValue); | 2311 InsertAfter(instr, extract, NULL, FlowGraph::kValue); |
2310 } | 2312 } |
2311 | 2313 |
2312 | 2314 |
2313 | 2315 |
2314 | 2316 |
2315 } // namespace dart | 2317 } // namespace dart |
OLD | NEW |